[SR-13874] "Collection.formIndex(_, offsetBy:, limitedBy:)" crashes for conditionally-bidirectional collections

[karwa]

Previous ID	SR-13874
Radar	rdar://problem/71590291
Original Reporter	@karwa
Type	Bug

Attachment: Download

Environment

Xcode Version 12.2 (12B45b), macOS 10.15.6 (19G2021)

Additional Detail from JIRA

Votes	0
Component/s	Compiler, Standard Library
Labels	Bug
Assignee	None
Priority	Medium

md5: 39085f935dfa8699815d2eee20a72358

Issue Description:

The following is a reduced test-case which demonstrates the bug:

struct BugDemo<T>: Collection {
  struct Index: Comparable {
    var wrapped: Int
    static func < (lhs: Self, rhs: Self) -> Bool {
      return lhs.wrapped < rhs.wrapped
    }
  }
  
  let startIndex: Index
  let endIndex: Index
  
  subscript(position: Index) -> Int {
    return position.wrapped
  }
  func index(after i: Index) -> Index {
    return Index(wrapped: i.wrapped + 1)
  }
  func formIndex(after i: inout Index) {
    i.wrapped += 1
  }
}

extension BugDemo: BidirectionalCollection where T == Int {
  func index(before i: Index) -> Index {
    return Index(wrapped: i.wrapped - 1)
  }
  func formIndex(before i: inout Index) {
    i.wrapped -= 1
  }
}

@inline(never)
func testBidi<C: BidirectionalCollection>(_ c: C) {
  var i = c.endIndex
  let _ = c.formIndex(&i, offsetBy: -1, limitedBy: c.startIndex)
}

func testBug() {
  let demo = BugDemo<Int>(startIndex: .init(wrapped: 0), endIndex: .init(wrapped: 10))
  testBidi(demo)
}

testBug()

Here, we have a very simple collection which conditionally conforms to BidirectionalCollection. The generic function `testBidi` takes a single generic parameter, constrained to BidirectionalCollection, and calls `formIndex(_:, offsetSet: limitedBy🙂` with a negative offset.

Unfortunately the code crashes with a fatal error: "Only BidirectionalCollections can be advanced by a negative amount". This is error should not happen: the type does conform to BidirectionalCollection, and the generic constraints all statically enforce that it conforms.

* thread #​1, queue = 'com.apple.main-thread', stop reason = Fatal error: Only BidirectionalCollections can be advanced by a negative amount
    frame #​0: 0x00007fff6c894380 libswiftCore.dylib`_swift_runtime_on_report
    frame #​1: 0x00007fff6c90e243 libswiftCore.dylib`_swift_stdlib_reportFatalErrorInFile + 211
    frame #&#8203;2: 0x00007fff6c5d51dd libswiftCore.dylib`closure #&#8203;1 (Swift.UnsafeBufferPointer<Swift.UInt8>) -> () in closure #&#8203;1 (Swift.UnsafeBufferPointer<Swift.UInt8>) -> () in closure #&#8203;1 (Swift.UnsafeBufferPointer<Swift.UInt8>) -> () in Swift._assertionFailure(_: Swift.StaticString, _: Swift.StaticString, file: Swift.StaticString, line: Swift.UInt, flags: Swift.UInt32) -> Swift.Never + 525
    frame #&#8203;3: 0x00007fff6c5d4cf7 libswiftCore.dylib`closure #&#8203;1 (Swift.UnsafeBufferPointer<Swift.UInt8>) -> () in closure #&#8203;1 (Swift.UnsafeBufferPointer<Swift.UInt8>) -> () in Swift._assertionFailure(_: Swift.StaticString, _: Swift.StaticString, file: Swift.StaticString, line: Swift.UInt, flags: Swift.UInt32) -> Swift.Never + 87
    frame #&#8203;4: 0x00007fff6c5d49c3 libswiftCore.dylib`closure #&#8203;1 (Swift.UnsafeBufferPointer<Swift.UInt8>) -> () in Swift._assertionFailure(_: Swift.StaticString, _: Swift.StaticString, file: Swift.StaticString, line: Swift.UInt, flags: Swift.UInt32) -> Swift.Never + 99
    frame #&#8203;5: 0x00007fff6c5d45d5 libswiftCore.dylib`Swift._assertionFailure(_: Swift.StaticString, _: Swift.StaticString, file: Swift.StaticString, line: Swift.UInt, flags: Swift.UInt32) -> Swift.Never + 533
    frame #&#8203;6: 0x00007fff6c5e683f libswiftCore.dylib`(extension in Swift):Swift.Collection.index(_: A.Index, offsetBy: Swift.Int, limitedBy: A.Index) -> Swift.Optional<A.Index> + 479
    frame #&#8203;7: 0x0000000107b58cb9 WebURLTests`protocol witness for Collection.index(_:offsetBy:limitedBy:) in conformance BugDemo<A> at <compiler-generated>:0
    frame #&#8203;8: 0x00007fff6c5e6c02 libswiftCore.dylib`(extension in Swift):Swift.Collection.formIndex(_: inout A.Index, offsetBy: Swift.Int, limitedBy: A.Index) -> Swift.Bool + 178
  * frame #&#8203;9: 0x0000000107b58518 WebURLTests`testBidi<C>(c=WebURLTests.BugDemo<Swift.Int> @ 0x00007ffeefbfd850) at ASCIITests.swift:95:13

   ...

We can see in Frame 8 that this is going in to plain `Collection` witnesses, not `BidirectionalCollection`. It seems that BidirectionalCollection only overrides the regular `index(_:offsetBy:limitedBy🙂` family of methods, and forgot the `formIndex` variants. Indeed, changing the implementation of `testBidi` to the following bypasses the fatal error:

@inline(never)
func testBidi<C: BidirectionalCollection>(_ c: C) {
  let i = c.endIndex
  let _ = c.index(i, offsetBy: -1, limitedBy: c.startIndex) // changed from 'formIndex'
}

But there is another way to bypass the error, which is kind of fascinating. You may have noticed that the condition which makes BugDemo conform to BidirectionalCollection (`T == Int`) is not actually necessary - BugDemo could just as well unconditionally conform. That also fixes the issue.

What I mean is that when the conformance to BidirectionalCollection is conditional, the `formIndex` function fails and raises a fatal error. But while trying to build a reduced test case and creating a simple type which unconditionally conforms, I found that `formIndex` did something else entirely and somehow bypassed the error.

Which is extremely spooky to me, and why I think this might also be some kind of compiler error, as well as potentially some missing overloads in the standard library.

[typesanitizer]

@swift-ci create

[karwa]

Also, it seems that FlattenSequence does some funky stuff for BidirectionalCollections, which can also surface this bug.

I'm tempted to look at creating a patch, but seeing stuff like that makes me think that most of the standard library's generic wrapper collections will need auditing and tests to ensure they correctly handle bidirectional (and conditionally-bidirectional) collections. And I just don't have that kind of time right now.

But it's important. Of the standard library bugs I've seen or know about, this is the most egregious. You can get in to situations where you have an object, statically constrained to be a BidirectionalCollection, yet the standard library will freak out and tell you that it isn't: