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

[glessard]

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]

@swift-ci create

[lorentey]

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]

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]

#38161

[glessard]

Check with the release version of 5.5 before closing.

[glessard]

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]

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]

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]

I see. Thanks for responding.