Skip to content
New issue

Have a question about this project? Sign up for a free GitHub account to open an issue and contact its maintainers and the community.

By clicking “Sign up for GitHub”, you agree to our terms of service and privacy statement. We’ll occasionally send you account related emails.

Already on GitHub? Sign in to your account

[SR-14848] A Collection without any subscript[Range<Index>] can compile #57195

Closed
glessard opened this issue Jun 29, 2021 · 9 comments
Closed
Assignees
Labels
bug A deviation from expected or documented behavior. Also: expected but undesirable behavior. compiler The Swift compiler in itself standard library Area: Standard library umbrella

Comments

@glessard
Copy link
Contributor

Previous ID SR-14848
Radar rdar://problem/79891982
Original Reporter @glessard
Type Bug
Status Closed
Resolution Done

Attachment: Download

Environment

swift-driver version: 1.26 Apple Swift version 5.5 (swiftlang-1300.0.20.104 clang-1300.0.21.1)
Target: arm64-apple-macosx11.0

Additional Detail from JIRA
Votes 0
Component/s Compiler, Standard Library
Labels Bug
Assignee @glessard
Priority Medium

md5: e982e40416288e077649666cd5387791

Issue Description:

Collection has the following requirement:

subscript(bounds: Range<Index>) -> SubSequence { get }

Its only default implementation is in an extension Collection where SubSequence == Slice<Self>. Therefore it should be required to supply such a subscript in order to compile a Collection whose SubSequence is not Slice. Somehow, it isn't! However, trying to access such an un-defined subscript results in a crash at runtime, even though it had compiled successfully.

struct MyRange {
  public let start: Int
  public let count: Int

  public init(_ range: Range<Int>) {
    start = range.lowerBound
    count = range.count
  }
}

extension MyRange: Sequence {
  public struct Iterator: IteratorProtocol {
    public mutating func next() -> Int? { nil }
  }

  public func makeIterator() -> Iterator { Iterator() }
}

extension MyRange: Collection {
  public typealias Index = Int
  public typealias SubSequence = Self

  public var startIndex: Index { start }
  public var endIndex: Index { start + count }

  public func index(after i: Index) -> Index {
    i.advanced(by: 1)
  }

  public subscript(position: Index) -> Int {
    get {
      precondition(position < endIndex)
      return position
    }
  }

//  public subscript(bounds: Range<Index>) -> SubSequence {
//    get {
//      precondition(bounds.lowerBound >= startIndex)
//      precondition(bounds.upperBound <= endIndex)
//      return SubSequence(bounds)
//    }
//  }
}

var rb: MyRange
rb = MyRange(0..<48)

let subseq: MyRange.SubSequence = rb[16..<24]
assert(subseq.start == 16)
assert(subseq.count == 8)

// The following doesn't compile, as expected.
//let slice: Slice<MyRange> = rb[16..<24]
//_ = slice

Instructions:
$ swiftc myrange.swift
$ ./myrange
Segmentation fault: 11

The .swift file is included, for convenience.

@glessard
Copy link
Contributor Author

@swift-ci create

@lorentey
Copy link
Member

It looks like this is because the `Collection.init<R: RangeExpression>(r: R)` extension technically satisfies the `Collection.init(bounds: Range)` requirement, so it leads to infinite recursion. Aaargh.

Something like the solution we applied to the `RandomNumberGenerator.next()` case could perhaps resolve this.

@glessard
Copy link
Contributor Author

I see. For reference, from stdlib's Range.swift:

extension Collection {
  public subscript<R: RangeExpression>(r: R)
  -> SubSequence where R.Bound == Index {
    return self[r.relative(to: self)] // <- accidental recursion when
                                      // there is no other range subscript
  }
}

@glessard
Copy link
Contributor Author

#38161

@glessard
Copy link
Contributor Author

glessard commented Jul 2, 2021

Check with the release version of 5.5 before closing.

@glessard
Copy link
Contributor Author

This standard library bug allowed incomplete Collection conformances to compile. There are 4 essential conditions for a project to stop compiling due to this:

  1. It must implement a custom Collection type,
  2. That Collection must define a non-default SubSequence (that is, it declares that it doesn't want to use Slice),
  3. That Collection must fail to define the slicing subscript (subscript(bounds: Range<Index>)),
  4. The slicing subscript is not used or tested.

The first 3 meant that a utility subscript (subscript<R: RangeExpression>(_ range: R)) was inadvertently getting picked up to satisfy the requirement, and with those conditions combined would simply call itself at runtime, resulting in a stack overflow.

The fix therefore converts a latent runtime bug to a compilation error.

@Shortoz
Copy link

Shortoz commented Jul 20, 2021

I just ran into this bug while working on a personal project. Using the latest development snapshot, the fix for the getter on Collection works, however, it seems like the bug is still present for the setter on MutableCollection.

@glessard
Copy link
Contributor Author

The MutableCollection issue has a slightly different root cause, and is tracked by https://bugs.swift.org/browse/SR-14850.
The fix was delayed by a higher priority issue, but it's coming.

@Shortoz
Copy link

Shortoz commented Jul 20, 2021

I see. Thanks for responding.

@swift-ci swift-ci transferred this issue from apple/swift-issues Apr 25, 2022
This issue was closed.
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment
Labels
bug A deviation from expected or documented behavior. Also: expected but undesirable behavior. compiler The Swift compiler in itself standard library Area: Standard library umbrella
Projects
None yet
Development

No branches or pull requests

3 participants