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

Jump to bottom

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

Open
karwa opened this issue Nov 18, 2020 · 2 comments
Open

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

karwa opened this issue Nov 18, 2020 · 2 comments
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

@karwa
Copy link
Contributor

karwa commented Nov 18, 2020

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 #&#8203;1, queue = 'com.apple.main-thread', stop reason = Fatal error: Only BidirectionalCollections can be advanced by a negative amount
    frame #&#8203;0: 0x00007fff6c894380 libswiftCore.dylib`_swift_runtime_on_report
    frame #&#8203;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
Copy link

@swift-ci create

@karwa
Copy link
Contributor Author

karwa commented Aug 25, 2021

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:

@swift-ci swift-ci transferred this issue from apple/swift-issues Apr 25, 2022
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment
Assignees
No one assigned
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
Milestone
No milestone
Development

No branches or pull requests
2 participants
@karwa @typesanitizer