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-12692] Conditional conformance of generics and specialized algorithms is broken. #55136

Open
dabrahams opened this issue Apr 28, 2020 · 3 comments

Comments

@dabrahams
Copy link
Collaborator

@dabrahams dabrahams commented Apr 28, 2020

Previous ID SR-12692
Radar rdar://problem/62895065
Original Reporter @dabrahams
Type Bug
Additional Detail from JIRA
Votes 5
Component/s Compiler
Labels Bug
Assignee None
Priority Medium

md5: 822582f2db61889e5af168490d06a19e

Issue Description:

If I am the author of a generic library—e.g. the Swift Standard Library—and I have an algorithm for one of my protocols (e.g. Collection) that I know can have a lower complexity bound for a refined protocol (e.g. RandomAccessCollection), the prescription is to make the algorithm a requirement of the base protocol Collection and implement it in extensions of both Collection and RandomAccessCollection. I can then document the complexity of the algorithm as dependent on the conformance of the model to RandomAccessCollection, right?

Wrong!! I have to say the complexity depends on the conformance to RandomAccessCollection unless the model is a generic type and its most general form conforms to Collection, in which case the complexity depends on whether the conformance to RandomAccessCollection is statically known at the point where the algorithm is invoked. In other words, there's nothing I can say about it that's both intelligible and accurate.

Furthermore, in this case, as far as I can tell, there's no way at all to access the specialized version of the algorithm from generic code or for the author of the conditionally-conforming type to be explicit about getting the specialized algorithm implementation.

This gist demonstrates.

IMO this model is untenable, and is clearly incompatible with Swift's goals for supporting generic programming.

@dabrahams
Copy link
Collaborator Author

@dabrahams dabrahams commented Apr 28, 2020

Here's an even simpler example, that shows how it trips up expert generic programmers:

extension Sequence {
  var array: Array<Element> {
    print("preallocating", self.underestimatedCount)
    return Array(self)
  }
}

_ = Array(0..<1000).reversed().array                 // preallocating 1000
_ = repeatElement(1..<10, count: 200).joined().array // preallocating 0

Because the result of `joined()` is a type that only conditionally conforms to `Collection`, `Array.init` will not find the `underestimatedCount` for collections, and instead of preallocating storage for all elements as it is supposed to, it will make log(N) allocations growing the array's buffer exponentially.

Oh, wow, it's worse than a trip-up: there's no way to fix this! Even if `FlattenSequence` implemented `underestimatedCount` in its conditional conformance to `Collection`, it wouldn't get used.

/cc kylemacomber (JIRA User)

@swift-ci
Copy link
Collaborator

@swift-ci swift-ci commented May 4, 2020

Comment by Daryle Walker (JIRA)

From the first comment, what if you overrode underestimatedCount at the Sequence level the best you can?

@beccadax
Copy link
Contributor

@beccadax beccadax commented May 5, 2020

@swift-ci create

@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
Projects
None yet
Development

No branches or pull requests

3 participants