> On Dec 3, 2017, at 2:39 PM, Jens Persson <[email protected]> wrote:
>
> Would this help sorting out the behavior of typealiases in constrained
> extensions?
Sadly, no.
>
> If not, please ignore the following and accept my apologies for posting OT.
>
> Typealiases in constrained extensions are - and have been, for a long time -
> very broken.
> The following program (which is clearly crazy in several ways) compiles and
> runs using the latest version of the compiler:
>
> struct S<T> {
> var v: This
> }
> extension S where T == Int {
> typealias This = Is
> }
> extension S where T == Bool {
> typealias Is = Fine
> }
> extension S where T == String {
> typealias Fine = T
> }
> let x = S<Float80>(v: "uh")
> print(x.v) // uh
>
> ( SR-5440 )
> The current behavior is so allowing and strange that I'm having trouble
> seeing what the correct behavior would be if things worked as intended.
I’d said that “var v: This”, “typealias This = Is”, and “typealias Is = Fine”
are ill-formed and the compiler should reject them. You should only be able to
use types from another extension if your extra constraints imply the
constraints of that extension. I *think* it’s actually a simple model, but it
didn’t get implemented.
> For example should the following program still compile, and if so, should the
> last line also compile (if uncommented)?
>
> protocol P {
> associatedtype A = Int
> associatedtype B = Bool
> typealias C = Float
> }
> extension P where B == A {
> typealias C = String
> }
I think this should be ill-formed, because we shouldn’t allow two typealiases
with the same name to “overload” within the same type.
> struct S<A, B> : P {
> var v: (A, B, C)
> }
> extension S where A == Int, B == Bool {
> typealias C = [String]
> }
> let s1 = S(v: (1, true, [""]))
> // let s2 = S(v: ("a", "b", "c")) // Not (currently) ok.
>
> Again, sorry for the noise if this is unrelated to the discussion.
- Doug
> /Jens
>
>
> On Sun, Dec 3, 2017 at 6:23 AM, Dave Abrahams via swift-evolution
> <[email protected] <mailto:[email protected]>> wrote:
>
> On Nov 30, 2017, at 2:28 PM, Douglas Gregor via swift-evolution
> <[email protected] <mailto:[email protected]>> wrote:
>
>> Hello Swift community,
>>
>> Associated type inference, which is the process by which the Swift compiler
>> attempts to infer typealiases to satisfy associated-type requirements based
>> on other requirements, has caused both implementation problems and user
>> confusion for a long time. Some of you might remember a previous (failed)
>> attempt to remove this feature from the Swift language, in SE-0108 “Remove
>> associated type inference”.
>> <https://github.com/apple/swift-evolution/blob/master/proposals/0108-remove-assoctype-inference.md>
>>
>>
>> I’m not sure we can remove this feature outright (i.e., the concerns that
>> sank that proposal are still absolutely valid), because it is so very
>> convenient and a lot of user code likely depends on it in some form or
>> other. So, here I’d like to describe the uses of the feature, its current
>> (very problematic) implementation approach, and a half-baked proposal to
>> narrow the scope of associated type inference to something that I think is
>> more tractable. I need help with the design of this feature, because I feel
>> like it’s going to be a delicate balance between implementability and
>> expressiveness.
>
> Aloha, Doug!
>
>>
>> A Motivating Example
>> As a motivating example, let’s consider a “minimal” random access collection:
>>
>> struct MyCollection<T> {
>> var contents: [T]
>> }
>>
>> extension MyCollection: RandomAccessCollection {
>> var startIndex: Int { return contents.startIndex }
>> var endIndex: Int { return contents.endIndex }
>> subscript(index: Int) -> T { return contents[index] }
>> }
>>
>> This is actually pretty awesome: by providing just two properties and a
>> subscript, we get the full breadth of the random access collection API! This
>> is relying heavily on associated type inference (for associated type
>> requirements) and default implementations specified on protocol extensions.
>> Without associated type inference, we would have had to write:
>>
>>
>> extension MyCollection: RandomAccessCollection {
>> typealias Element = T
>> typealias Index = Int
>> typealias Indices = CountableRange<Int>
>> typealias Iterator = IndexingIterator<MyCollection<T>>
>> typealias SubSequence = RandomAccessSlice<MyCollection<T>>
>>
>> var startIndex: Int { return contents.startIndex }
>> var endIndex: Int { return contents.endIndex }
>> subscript(index: Int) -> T { return contents[index] }
>> }
>>
>> where the bolded typealiases are currently inferred. It was worse back when
>> we reviewed SE-0108, because IIRC there were a few underscored associated
>> types (e.g., _Element) that have since been removed. Still, that’s a bit of
>> additional work to define a “minimal” collection, and requires quite a bit
>> more understanding: how do I know to choose IndexingIterator, and
>> CountableRange, and RandomAccessSlice?
>>
>> The issue would get worse with, e.g., SE-0174 “Change filter to return an
>> associated type”
>> <https://github.com/apple/swift-evolution/blob/master/proposals/0174-filter-range-replaceable.md>,
>> which adds an associated type Filtered that almost nobody will ever
>> customize, and isn’t really fundamental to the way collections work. Adding
>> Filtered to the standard library would be a source-breaking change, because
>> users would have to write a typealias giving it its default.
>>
>> Associated Type Defaults
>> One of the ways in which we avoid having to specify typealiases is to use
>> associated type defaults. For example, the standard library contains
>> associated type defaults for Indices, Iterator, and SubSequence. Let’s focus
>> on Indices:
>>
>> protocol Collection : Sequence {
>> associatedtype Indices = DefaultIndices<Self>
>> // ...
>> }
>>
>> protocol BidirectionalCollection : Collection {
>> associatedtype Indices = DefaultBidirectionalIndices<Self>
>> // ...
>> }
>>
>> protocol RandomAccessCollection : BidirectionalCollection {
>> associatedtype Indices = DefaultRandomAccessIndices<Self>
>> // ...
>> }
>>
>> The basic idea here is that different protocols in the hierarchy provide
>> different defaults, and you presumably want the default from the most
>> specific protocol. If I define a type and make it conform to
>> BidirectionalCollection, I’d expect to get DefaultBidirectionalIndices<Self>
>> for Indices. If a define a type and make it conform to RandomAccessIterator,
>> I’d expect to get DefaultRandomAccessIndices<Self>.
>>
>> (Aside: DefaultRandomAccessIndices and DefaultBidirectionalIndices got
>> collapsed into DefaultIndices now that we have conditional conformances for
>> the standard library <https://github.com/apple/swift/pull/12913>, but the
>> issues I’m describing remain).
>>
>> Associated type defaults seem like a reasonable feature that fits well
>> enough into the design. However, it’s not the only thing in place with our
>> MyCollection example, for which Indices was inferred to CountableRange.
>> How’s that happen?
>>
>> Associated Type Inference
>> Associated type inference attempts to look at the requirements of a
>> protocol, and then looks into the conforming type for declarations that
>> might satisfy those requirements, and infers associated types from the types
>> of those declarations. Let’s look at some examples. RandomAccessCollection
>> has some requirements that mention the Index and Element types:
>>
>> protocol RandomAccessCollection : BidirectionalCollection {
>> associatedtype Element
>> associatedtype Index
>>
>> var startIndex: Index { get }
>> var endIndex: Index { get }
>> subscript (i: Index) -> Element { get }
>> }
>>
>> Associated type inference wil try to satisfy those requirements for
>> MyCollection, and will find these declarations:
>>
>> extension MyCollection: RandomAccessCollection {
>> var startIndex: Int { return contents.startIndex }
>> var endIndex: Int { return contents.endIndex }
>> subscript(index: Int) -> T { return contents[index] }
>> }
>>
>> and match them up. From startIndex, we infer Index := Int. From endIndex, we
>> infer Index := Int. From subscript, we infer Index := Int and Element := T.
>> Those results are all consistent, so we’ve properly inferred Index and
>> Element. Yay.
>>
>> Associated type inference often has to deal with ambiguities. For example,
>> there is an extension of Collection that provides a range subscript operator:
>>
>> extension Collection {
>> subscript (bounds: Range<Index>) -> Slice<Self> { … }
>> }
>>
>> When we look at that and match it to the subscript requirement in
>> RandomAccessCollection (remembering that argument labels aren’t significant
>> for subscripts by default!), we infer Index := Range<Index> (admittedly
>> weird) and Element := Slice<Self> (could be legitimate). We have to discard
>> this candidate because the deduction from startIndex/endIndex (Index := Int)
>> collides with this deduction (Index := Range<Index>).
>>
>> In our initial example, we saw that Indices was inferred to
>> CountableRange<Int>. Let’s look at another slice of the
>> RandomAccessCollection protocol that’s relevant to this associated type:
>>
>> protocol RandomAccessCollection : BidirectionalCollection {
>> associatedtype Index
>> associatedtype Indices: RandomAccessCollection where Indices.Element ==
>> Index
>>
>> var indices: Indices { get }
>> }
>>
>> We will match that requirement for an “indices” property against a member of
>> a constrained protocol extension of RandomAccessCollection:
>>
>> extension RandomAccessCollection where Index : Strideable, Index.Stride ==
>> IndexDistance, Indices == CountableRange<Index> {
>> public var indices: CountableRange<Index> {
>> return startIndex..<endIndex
>> }
>> }
>>
>> Associated type inference can determine here that Indices :=
>> CountableRange<Index>, but only when Index: Strideable and Index.Stride ==
>> IndexDistance. In other words, there are a whole bunch of other constraints
>> to verify before we can accept this inference for Indices.
>
> So, what’s the problem? ;-)
>
>> What’s a Good Solution Look Like?
>> Our current system for associated type inference and associated type
>> defaults is buggy and complicated.
>
> Well, that’s the problem, then. Don’t worry, I won’t suggest that you simply
> fix the implementation, because even if there weren’t bugs and the system
> were predictable I’d still think we could improve the situation for users by
> making associated type default declarations more explicit.
>
>> The compiler gets it right often enough that people depend on it, but I
>> don’t think anyone can reasonably be expected to puzzle out what’s going to
>> happen, and this area is rife with bugs. If we were to design a new solution
>> from scratch, what properties should it have?
>>
>> It should allow the author of a protocol to provide reasonable defaults, so
>> the user doesn’t have to write them
>> It shouldn’t require users to write typealiases for “obvious” cases, even
>> when they aren’t due to defaults
>> It shouldn’t infer an inconsistent set of typealiases
>> It should be something that a competent Swift programmer could reason about
>> when it will succeed, when and why it will fail, and what the resulting
>> inferred typealiases would be
>> It should admit a reasonable implementation in the compiler that is
>> performant and robust
> • It should cover all of the existing use cases.
> • It should not break code at this point.
> • We should have a migration strategy for existing code that avoids traps
> like silent semantic changes.
>
> My bullet is important to me; I don’t think existing use cases are
> (inherently) so complex that we can sacrifice almost any of them and still
> end up with a sufficiently useful system. At the very least, existing use
> cases provide the only guidance we really have as to what the feature should
> do.
>
> I think we need to acknowledge that my second bullet is unattainable, at
> least if we want to improve type checking performance. Not breaking any code
> means that given any existing code, the compiler would have to explore the
> same solution space it currently does, and come up with the same answers.
> Improving performance would require new declarations to use totally optional
> explicit syntax to prevent some explorations, and that’s an untenable user
> experience.
>
> Which brings me to my third bullet: unless we are willing to break the code
> of protocol users (as opposed to vendors) we need to ensure that vendors can
> confidently convert code to use the new system without changing semantics.
>
>>
>> A Rough Proposal
>> I’ve been thinking about this for a bit, and I think there are three ways in
>> which we should be able to infer an associated type witness:
>>
>> Associated type defaults, which are specified with the associated type
>> itself, e.g.,
>>
>> associatedtype Indices = DefaultIndices<Self>
>>
>> These are easy to reason about for both the programmer and the compiler.
>> Typealiases in (possibly constrained) protocol extensions, e.g.,
>>
>> extension RandomAccessCollection where Index : Strideable, Index.Stride ==
>> IndexDistance {
>> typealias RandomAccessCollection.Indices = CountableRange<Index>
>> }
>>
>> I’m intentionally using some odd ‘.’ syntax here to indicate that this
>> typealias is intended only to be found when trying to satisfy an associated
>> type requirement, and is not a general typealias that could be found by
>> normal name lookup. Let’s set the syntax bike shed aside for the moment. The
>> primary advantage of this approach (vs. inferring Indices from “var Indices:
>> CountableRange<Index>” in a constrained protocol extension) is that there’s
>> a real typealias declaration that compiler and programmer alike can look at
>> and reason about based just on the name “Indices”.
>>
>> Note that this mechanism technically obviates the need for (1), in the same
>> sense that default implementations in protocols
>> <https://github.com/apple/swift/blob/master/docs/GenericsManifesto.md#default-implementations-in-protocols->
>> are merely syntactic sugar.
>> Declarations within the nominal type declaration or extension that declares
>> conformance to the protocol in question. This is generally the same approach
>> as described in “associated type inference” above, where we match
>> requirements of the protocol against declarations that could satisfy those
>> requirements and infer associated types from there. However, I want to turn
>> it around: instead of starting with the requirements of the protocol any
>> looking basically anywhere in the type or any protocol to which it conforms
>> (for implementations in protocol extensions), start with the declarations
>> that the user explicitly wrote at the point of the conformance and look for
>> requirements they might satisfy. For example, consider our initial example:
>>
>> extension MyCollection: RandomAccessCollection {
>> var startIndex: Int { return contents.startIndex }
>> var endIndex: Int { return contents.endIndex }
>> subscript(index: Int) -> T { return contents[index] }
>> }
>>
>> Since startIndex, endIndex, and subscript(_:) are declared in the same
>> extension that declares conformance to RandomAccessIterator, we should look
>> for requirements with the same name as these properties and subscript within
>> RandomAccessCollection (or any protocol it inherits) and infer Index := Int
>> and Element := T by matching the type signatures. This is still the most
>> magical inference rule, because there is no declaration named “Index” or
>> “Element” to look at. However, it is much narrower in scope than the current
>> implementation, because it’s only going to reason from the (probably small)
>> set of declarations that the user wrote alongside the conformance, so it’s
>> more likely to be intentional. Note that this is again nudging programmers
>> toward the style of programming where one puts one protocol conformance per
>> extension, which is admittedly my personal preference.
>>
>> Thoughts?
>
> The thing that strikes me most about these is that the first two are explicit
> declarations of intent: “In the absences of an explicit declaration, deduce
> this associated type as follows,” while the third is still extremely
> indirect. While it hints to the compiler about which conformances’
> associated type requirements we are trying to satisfy, it never comes out and
> says straight out what the associated type should be, even though it needs to
> be mentioned. As a generic programmer, I don’t value the concision gained
> over the clarity lost, and I’d like to see the solutions to these problems
> follow the explicit-declaration-of-intent pattern. However, the code in #3
> is not written by the protocol vendor, and for me it is (at least currently)
> a stretch to think of breaking the code of protocol users, so I grudgingly
> accept it.
>
> If we were really starting from scratch I might suggest requiring that
> conformances use the associated type name rather than some concrete type,
> e.g.
>
> extension MyCollection: RandomAccessCollection {
> typealias RandomAccessCollection.Index = Int
> var startIndex: Index { return contents.startIndex }
> var endIndex: Index { return contents.endIndex }
> subscript(index: Index) -> Element { return contents[index] }
> }
>
> But I suspect we’re well past the point in the language’s evolution where
> that sort of change is possible.
>
> As for migration of protocol user code, I think we’d need to run both the new
> and the old slow inference in the migrator and flag any differences. I don’t
> know what to do about protocol vendors’ code though.
>
>> I think this approach is more predictable and more implementable than the
>> current model. I’m curious whether the above makes sense to someone other
>> than me, and whether it covers existing use cases well enough. Thoughts?
>
> Well, covering the use cases is definitely still a concern for me. I don’t
> think we’ll know for sure until we try it, but have you thought about how to
> migrate each piece of code in the standard library? Does it cover those
> cases?
>
> -Dave
>
>
>
> Sent from my iPad
>
>
> _______________________________________________
> swift-evolution mailing list
> [email protected] <mailto:[email protected]>
> https://lists.swift.org/mailman/listinfo/swift-evolution
> <https://lists.swift.org/mailman/listinfo/swift-evolution>
>
>
_______________________________________________
swift-evolution mailing list
[email protected]
https://lists.swift.org/mailman/listinfo/swift-evolution
