[swift-dev] SubstitutionMap questions
Slava Pestov
spestov at apple.com
Fri Dec 30 18:09:33 CST 2016
Hi Jacob,
> On Dec 30, 2016, at 12:14 PM, Jacob Bandes-Storch <jtbandes at gmail.com> wrote:
>
> Happy holidays :-)
>
> I started looking at this bug to see if I could figure out how to fix it: https://bugs.swift.org/browse/SR-3500 <https://bugs.swift.org/browse/SR-3500>
>
> As the bug author points out, there is a TODO in GenericSignature::getSubstitutionMap, saying it needs to handle same-type requirements: https://github.com/apple/swift/blob/474096b9cbd6ff7ac998d7cea41d629512e25570/lib/AST/GenericSignature.cpp#L276 <https://github.com/apple/swift/blob/474096b9cbd6ff7ac998d7cea41d629512e25570/lib/AST/GenericSignature.cpp#L276>
This TODO is actually not the problem here, but I’ll answer your questions below first before explaining my theory.
>
> Most of the stuff going on here is way over my head right now, but maybe I can get there by asking some questions. Here is my repro case:
>
> protocol P { associatedtype Pmember }
>
> struct Bar {}
> struct Foo: P { typealias Pmember = Bar }
>
> protocol A {
> associatedtype Amember: P
> func doSomething() -> Amember.Pmember
> }
>
> extension A where Amember == Foo {
> func extensionFunc() {
> doSomething() // crash occurs when trying to subst() this call's return type
> }
> }
Yep, this is exactly right.
>
> Ultimately the problem is that, during SILFunctionType::substGenericArgs, getMemberForBaseType() returns null when called on the DependentMemberType (the function result type), because the result of lookupConformances is not concrete: https://github.com/apple/swift/blob/474096b9cbd6ff7ac998d7cea41d629512e25570/lib/AST/Type.cpp#L2843-L2845 <https://github.com/apple/swift/blob/474096b9cbd6ff7ac998d7cea41d629512e25570/lib/AST/Type.cpp#L2843-L2845>
Yep.
>
> Here are some things I don't understand:
>
> 1. Why does LookupConformanceFn return only a single conformance? Couldn't there be more than one conformance for a particular generic param?
LookupConformanceFn takes the original type parameter, the replacement type, and a protocol, and returns the conformance of the replacement type to the protocol. To get the protocols that a type parameter conforms to, you can query the GenericSignature (see enumeratePairedRequirements()).
>
> 2. Why does finding an abstract conformance constitute a failure of getMemberForBaseType?
By this point in getMemberForBaseType(), we’ve eliminated these two cases:
- Member type lookup on a type parameter (either a generic parameter or a DependentMemberType thereof) — this doesn’t do any kind of real lookup at all — it just produces a new DependentMemberType with the given base.
- Member type lookup on an archetype, which gets the nested type directly out of the archetype to produce either a concrete type or another archetype.
The remaining case is where the base is a nominal or generic nominal, and we must do a conformance lookup using the provided LookupConformanceFn to get the nested type out.
In your example, the base type is ‘Foo’ and the member type is ‘Pmember’. We first get the conformance of ‘Foo : P’ by calling the LookupConformanceFn, and then get the type witness for ‘Pmember’ from the concrete conformance (subclasses of ProtocolConformance, such as NormalProtocolConformance).
When called with a type parameter that maps to a concrete type, LookupConformanceFn returns a concrete conformance. When called with a type parameter that maps to another type parameter or archetype, LookupConformanceFn returns an abstract conformance.
Abstract conformances (ProtocolConformanceRef where isConcrete() returns false) don’t store any information beyond the protocol being conformed to. There’s no conforming type, no nested types, and no nested type conformances. Abstract conformances are just a placeholder that says “this type parameter or archetype conforms to protocol P, but I can’t give you any details until you replace me with a concrete type.”
The two cases where LookupConformanceFn legitimately returns an abstract conformance are handled already by this point in getMemberForBaseType(), so that’s why we fail if we get an abstract conformance back — there’s not enough information to proceed.
Indeed, the if (!conformance->isConcrete()) failed(); here should probably be an assert — a well-formed SubstitutionMap should not vend an abstract conformance for a concrete type. So as you can guess, our SubstitutionMap here is missing information...
>
> 3. At the lookupConformances call <https://github.com/apple/swift/blob/474096b9cbd6ff7ac998d7cea41d629512e25570/lib/AST/Type.cpp#L2843-L2845>, origBase is "τ_0_0.Amember", and substBase is the concrete type "Foo". However, the LookUpConformanceInSubstitutionMap drops the substBase ( <https://github.com/apple/swift/blob/474096b9cbd6ff7ac998d7cea41d629512e25570/lib/AST/Type.cpp#L2891>conformingReplacementType) on the floor <https://github.com/apple/swift/blob/474096b9cbd6ff7ac998d7cea41d629512e25570/lib/AST/Type.cpp#L2891>. Why?
The SubstitutionMap consists of three pieces:
- a replacement map, mapping the original type parameters to substituted types
- a conformance map, mapping the original type parameters to lists of conformances, one for each protocol
- the same-type map
Since the keys of the conformance map are original types, the callback ignores the replacement type (it’s needed in another case). We have to use τ_0_0.Amember and not ‘Foo’ as the lookup key. It’s just an artifact of how the substitution map is stored.
The LookupConformanceFn typedef is used in a few different places, and not just with SubstitutionMaps, which is why it’s more general than needed here.
>
> 4. Finally, is SubstitutionMap really the right place for same-type requirements? Maybe getMemberForBaseType would need more context passed to it than just the LookupConformanceFn?
So there are two kinds of same-type requirements in Swift:
- same-type requirements making a type parameter concrete
- same-type requirements making two type parameters equivalent, but both remain abstract
This bug is with the first case. The TODO in GenericSignature.cpp that you found, as well as the same-type map in SubstitutionMap concerns the second case. I’m not convinced the TODO there is actually possible to hit right now, unlike the similar case in GenericEnvironment::getSubstitutionMap(). It has to do with how the ArchetypeBuilder chooses “archetype anchors”. I won’t explain the details in this e-mail, sorry :)
Let’s look at your example again:
protocol P { associatedtype Pmember }
struct Bar {}
struct Foo: P { typealias Pmember = Bar }
protocol A {
associatedtype Amember: P
func doSomething() -> Amember.Pmember
}
extension A where Amember == Foo {
func extensionFunc() {
doSomething() // crash occurs when trying to subst() this call's return type
}
}
A.doSomething() has type ‘<T_0_0 where T_0_0 : P> (T_0_0) -> () -> (T_0_0.Amember.Pmember)’. There are three general ways in which doSomething() can be called — on a concrete type conforming to P, on ’self’ from an unconstrained protocol extension, or the final bad case, ‘self’ from a constrained protocol extension:
1) Let’s say we also have a concrete type conforming to A:
struct Baz : A {
typealias Amember = Foo
func doSomething() -> Bar { return Bar() }
}
You can think of the concrete conformance 'Baz : A' as being a sort of map from requirements to witness declarations, with nested conformances for each of the associated types that have protocol requirements:
{
// value requirements
A.doSomething = Baz.doSomething
// associated type requirements
A.Amember = Foo
// conformances for associated type requirements
(A.Amember : P) = { // conformance of Foo to P
// associated type requirements
P.Pmember = Bar
// P.Pmember has no conformance requirements, so there are no nested conformances here
}
}
In fact this is how a NormalProtocolConformance is stored.
What happens when I call doSomething() on a ‘Baz’? We need to build the substituted type for the call. The substitution map here is built from the generic signature of A.doSomething(), which is just <T_0_0 where T_0_0 : P>’. So the replacement map has one entry mapping ’T_0_0’ to a concrete type:
- T_0_0 = Baz
And the conformance map also has one entry:
- (T_0_0 : A) = { … } // the above conformance
When Type::subst() walks to Self.Amember.Pmember, it notes that Pmember is an associated type in protocol ‘P’. It first checks if the conformance map has an entry for (Self.Amember : P). There is no entry for that. So it then gets the parent type of Self.Amember, which is Self, and the parent protocol containing the associated type Pmember, which is ‘A’, and looks up (Self : A). We do have an entry for that. It walks back down, getting the type witness for A.Amember from the conformance (Self : A), which produces the concrete type ‘Foo’ together with the conformance ‘Foo : P'. It then looks up the type witness for Pmember from ‘Foo : P’, which yields ‘Bar’.
This all works correctly, as you can try for yourself.
2) Now, let’s consider an *unconstrained* protocol extension:
extension A {
func extensionFunc() {
doSomething() // this also works
}
}
Here, the type of ’self’ inside the function body is an archetype. The archetype “knows” that it conforms to A, and that it has a nested type “Amember” which is another archetype conforming to “P”, which in turn has a nested type “Pmember”, which now is an unconstrained archetype, since the associated type Pmember has no protocol requirements.
The substitution map looks like this:
- T_0_0 = Self archetype from the unconstrained extension
- (T_0_0 : A) = abstract conformance to A
When we call Type::subst() with the type of doSomething() and this substitution map, it sees that the replacement for T_0_0 is an archetype, and gets the nested type ‘Amember’ out, which is another archetype, and gets the nested type ‘Pmember’ out of that. All these nested types exist because the ArchetypeBuilder constructed the Self archetype in this way, since it was built with the generic signature <T_0_0 : A>. So again, we’re done.
3) Here’s the constrained case.
The generic signature is the following:
<T_0_0 : A where A.Pmember == Foo>
Again, the type of ‘self’ is an archetype. However, it’s nested type ‘Pmember’ is not an archetype anymore — it’s the concrete type Foo. The substitution map looks the same — we still have an abstract conformance for T_0_0 : A:
- T_0_0 = Self archetype from the constrained extension
- (T_0_0 : A) = abstract conformance to A
So the problem is that the "abstract conformance” representation is lacking — while the Self archetype here knows that it has a concrete nested type ‘Foo’, we’ve lost the connection to the concrete conformance ‘Foo : P’. Archetypes don’t store the *conformances* of their nested types to protocols, only the nested types themselves. And abstract conformances don’t store information about their nested type conformances either. So we’re stuck.
Note that everything works if your constrained extension constraints an associated type that has no further protocol requirements. Here the abstract conformance of ‘Self’ is not missing anything. So ‘extension Array where Element == Int’, ‘extension Collection where Iterator.Element == String’, etc are OK.
The old way of doing substitutions is that you would pass in the replacement map alone, and Type::subst() would call ModuleDecl::lookupConformance() to pull conformances “from thin air”. For various reasons it is better to look up and compute conformances once, and pass them around together with substitutions.
Joe recently changed SILType::subst() to use the new SubstitutionMap, so this is why this bug came up as a regression now. But the representational issue was always there — it was just harder to hit. I refactored SubstitutionMap from similar logic that was already in place in 3.0, it was just not used as much, but the SIL specializer for instance used it.
I think the solution is to have archetypes store conformances for their nested types, and populate them lazily when we first access a nested type of an archetype. The question is which conformances.
The ArchetypeBuilder minimizes generic signatures, so conformance requirements on an archetype are dropped once they become subject to a concrete same-type constraint — eg, if I write
protocol P {}
struct S : P {}
extension Array where Element == S, Element : P {
func doSomething() {}
}
The ‘Element : P’ requirement is redundant and is dropped from the signature, and ‘doSomething’ has the same exact type as if we had written:
extension Array where Element == S {
func doSomething() {}
}
I think these ‘redundant’ conformances are never going to be needed by substitution, though. The ‘interesting’ ones that archetypes need to store are the cases where a type parameter has conformance requirements imposed on it by an associated type of a protocol, *and* it is made concrete.
In our case, the signature <T_0_0 : A where A.Pmember == Foo> requires that A.Pmember conforms to P — since it is made concrete, the archetype should store that concrete conformance alongside the nested type mapping ‘Pmember = Foo’.
Even if Foo conforms to other protocols, we don’t care — they’re not “reachable” from T_0_0 or its constraints recursively.
The nested type list in an ArchetypeType is populated lazily on first access by the ArchetypeBuilder that produced the archetype — it walks the members of the protocols that the archetype conforms to, and also looks at same-type constraints from the context generic signature to produce the list of nested members. Since ArchetypeBuilders are associated with a ModuleDecl and can perform conformance lookups into the module, it should be possible to do those lookups and add them to the nested type list in some form as well.
Once that is in place, we can make SubstitutionMap::lookupConformance() find such conformances in the parent archetype instead of just giving up.
Incidentally this is also the change we will need to make so that GenericEnvironment::mapTypeIntoContext() no longer has to take a Module for conformance lookups, which is currently a big hole in our “produce conformances once” model.
The complementary mapTypeOutOfContext() maps archetypes to type parameters, so it can vend abstract conformances for all nested type lookups, and doesn’t have to call lookupConformance() or take a ModuleDecl parameter.
But mapTypeIntoContext() can map a type parameter to a concrete type — which would hit a similar crash as in your example, were it not for the fact that we use an “escape hatch” LookupConformanceFn that looks up in the module. But really we shouldn’t have to pass in a ModuleDecl in such places at all, and do the right thing in the representation instead.
We can iron out the kinks over time — once the old representation is gone completely it should simplify a lot of things. Let me know if you’re interested in helping :-)
Slava
>
> Thanks,
> Jacob
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <https://lists.swift.org/pipermail/swift-dev/attachments/20161230/4d56abfc/attachment.html>
More information about the swift-dev
mailing list