The substitution only replaces archetypes with abstract generic parameters, so no conformance lookup is necessary, and we can provide a "lookup" callback now that just vends abstract conformances.
(Ideally, we'd be able to do this for mapTypeIntoContext too, but we run into problems with generic signatures with same-type constraints on associated types with protocol requirements. Mapping `t_0_0.AssocType` into such a context will require conformance lookup for the concrete type replacement, since same-type Requirements don't preserve the conformances that satisfy the protocol requirements for the same-type relationship.)
This is a more flexible interface that allows substitution operations to avoid needing an eager SubstitutionMap without relying on module-based conformance lookup. NFC yet.
While not strictly needed for type checking, it's extremely useful for
debugging and verification to know what context a particular generic
environment is associated with. This information was in a kludgy side
table, but it's worth a pointer in GenericEnvironment to always have
it available.
We no longer need a separate "pass" that creates an archetype builder
that inherits context archetypes, because we no longer ever inherit
context archetypes.
Store the archetype-to-interface-type mapping (which is used to map
*out* of a generic environment) is a tail-allocated array of
(archetype, generic type parameter) pairs. This array is built up
lazily, as we compute the context types for generic parameters.
Searching in this array is linear while it is being constructed. Once
it is complete, it is sorted so that future searches are logarithmic.
Aside from the space savings of not having a DenseMap lying around,
this means we no longer need to register a destructor of a
GenericEnvironment with the ASTContext, which saves us tear-down
time.
Teach GenericEnvironment to lazily populate its mapping from generic
parameters to context types when queried (e.g., during
substitutition) rather than assuming that will be pre-populated before
any queries occur.
We're still forcing all of the archetypes when the generic environment
is created by the archetype builder; baby steps!
Rather than storing a heavyweight DenseMap for the mapping from
interface types (which are always generic type parameters) to their
corresponding context types, tail-allocate the array of context types
as an array parallel to the generic type parameters array. Use
GenericParamKey's lookup facilities and the new
type-substitution-function-based version of Type::subst() to handle
queries efficiently.
The "core" data structure used to record the substitutions to be
performed is a TypeSubstitutionMap, which is a DenseMap. This is a
fairly heavyweight, static data structure for something where
* We occasionally want a more dynamic, lazily-populated data structure, and
* We can usually provide more efficient storage than a DenseMap.
So, introduce a Type::subst() variant that takes a TypeSubstitutionFn,
which is just a function that maps a SubstitutableType * to a Type (or
nothing). Use this as the core variant of subst(). with an adapter for
existing TypeSubstitutionMaps. Over time, TypeSubstitutionMap should
go away.
This eliminates the really gross registration of archetype builders
within the ASTContext, and is another little step toward lazily
constructing archetypes.
The root potential archetypes in an archetype builder are associated
with generic parameters. Start decoupling potential archetypes from a
specific GenericTypeParamType and instead work with the abstracted
depth/index. The goal here is to allow the same archetype builder to
be used within different generic environments (which includes both
different generic parameters and different archetypes).
As part of this, boost the archetype builder's GenericTypeParamKey
from a local type to a more generic GenericParamKey that can be used
in other interfaces that want to work with abstracted generic
parameters.
Stop recording specific archetypes anywhere in
PotentialArchetype. Instead, use a GenericEnvironment to record/query
the archetype that corresponds to that PotentialArchetype, making it
possible to use the same archetype builder (and its potential
archetypes) to build multiple generic environments.
GenericEnvironment walked its input mapping in DenseMap order while
populating a reverse mapping from archetypes to interface
types. However, this mapping is not unique, because two generic
parameters can end up mapping to the same archetype. In such cases,
which generic parameter we mapped to was nondeterministic.
Make this deterministic by preferring to map back to the earlier
generic parameter.
ASTContext-allocated objects don't get destructed unless they are
registered; make sure to do that for GenericEnvironments, because
we're leaking them like crazy.
Type substitution works on a fairly narrow set of types: generic type
parameters (to, e.g., use a generic) and archetypes (to map out of a
generic context). Historically, it was also used with
DependentMemberTypes, but recent refactoring to eliminate witness
markers eliminate that code path.
Therefore, narrow TypeSubstitutionMap's keys to SubstitutableType,
which covers archetypes and generic type parameters. NFC
An environment is always associated with a location with a signature, so
having them separate is pointless duplication. This patch also updates
the serialization to round-trip the signature data.
Sugared GenericTypeParamTypes point to GenericTypeParamDecls,
allowing the name of the parameter as written by the user to be
recovered. Canonical GenericTypeParamTypes on the other hand
only store a depth and index, without referencing the original
declaration.
When printing SIL, we wish to output the original generic parameter
names, even though SIL only uses canonical types. Previously,
we used to accomplish this by mapping the generic parameter to an
archetype and printing the name of the archetype. This was not
adequate if multiple generic parameters mapped to the same
archetype, or if a generic parameter was mapped to a concrete type.
The new approach preserves the original sugared types in the
GenericEnvironment, adding a new GenericEnvironment::getSugaredType()
method.
There are also some other assorted simplifications made possible
by this.
Unfortunately this makes GenericEnvironments use a bit more memory,
however I have more improvements coming that will offset the gains,
in addition to making substitution lists smaller also.
Type::subst()'s "IgnoreMissing" option was fairly unprincipled, dropping
unsubstituted types into the resulting AST without any indication
whatsoever that anything went wrong. Replace this notion with a new
form of ErrorType that explicitly tracks which substituted type caused
the problem. It's still an ErrorType, but it prints like the
substituted type (which is important for code completion) and allows
us to step back to the substituted type if needed (which is used by
associated type inference). Then, allow Type::subst(), when the new
UseErrorTypes flag is passed, to form partially-substituted types that
contain errors, which both code completion and associated type
inference relied on.
Over time, I hope we can use error-types-with-original-types more
often to eliminate "<<error type>>" from diagnostics and teach
Type::subst() never to return a "null" type. Clients can check
"hasError()" to deal with failure cases rather than checking null.
There's a bit of a hack to deal with generic typealiases, but
overall this makes things more logical.
This is the last big refactoring before we can allow constrained
extensions to make generic parameters concrete. All that remains
is a small set of changes to SIL type lowering, and retooling
some diagnostics in Sema.
Applying a substitution list to a Substitution is done in two
steps:
1) First, apply the substitution list to the original replacement
type R to get the substituted replacement type R'.
2) Second, for each abstract conformance of R from the original
substitution, look up a concrete conformance of R' from the
substitution list.
With minimized generic signatures, we would omit conformances of
a nested type T.A if they could be derived from some other
conformance already in the substitution list.
However, the derivation process was incorrect, because it would
only look at the canonical parent type T, and not any other parent
type that had a child A which was same-type equivalent to T.A.
For example, consider the following code:
protocol P1 { associatedtype A : P3 }
protocol P2 { associatedtype A : P4 }
protocol P3 {}
protocol P4 {}
func doSomething<T : P4>(...) {}
func doSomethingElse<T1 : P1, T2 : P2>(...) where T1.A == T2.A {
doSomething(...)
}
If we specialize doSomethingElse() with a pair of concrete types
to replace T1 and T2, we would need to find a concrete conformance
to replace the abstract conformance T2.A : P4 in the call to
doSomething().
Since the conformance of T2.A : P4 is a redundant requirement,
it does not appear in the conformance map; furthermore, T1.A and
T2.A are same-type equivalent, so they map to the same archetype.
We would therefore look at the canonical parent of T2.A, which is
T1, and look up the conformance of T1 : P1 in the substitution list.
However, the only requirement P1 imposes on A is the conformance
A : P3. There's no conformance A : P4 inside T1 : P1, so we would
hit an assertion.
Indeed, the conformance T1.A : P4 must be recovered from the
conformance of T2 : P2, because P2 requires that A : P4.
This patch ensures that the conformance can be found by changing
the ArchetypeConformanceMap from a simple mapping of archetypes
to conformances into a structure that records same-type constraints
as well.
So instead of just looking at the canonical parent of the archetype
T1.A, we consult the structure to check all archetypes that have
T1.A as a child, in this case both T1 and T2.
T2 : P2 contains the conformance we need, allowing the above code
to be specialized correctly.
These will be more useful once substitutions in protocol conformances
are moved to use interface types.
At first, these are only going to be used by the SIL optimizer.
This patch is rather large, since it was hard to make this change
incrementally, but most of the changes are mechanical.
Now that we have a lighter-weight data structure in the AST for mapping
interface types to archetypes and vice versa, use that in SIL instead of
a GenericParamList.
This means that when serializing a SILFunction body, we no longer need to
serialize references to archetypes from other modules.
Several methods used for forming substitutions can now be moved from
GenericParamList to GenericEnvironment.
Also, GenericParamList::cloneWithOuterParameters() and
GenericParamList::getEmpty() can now go away, since they were only used
when SILGen-ing witness thunks.
Finally, when printing generic parameters with identical names, the
SIL printer used to number them from highest depth to lowest, by
walking generic parameter lists starting with the innermost one.
Now, ambiguous generic parameters are numbered from lowest depth
to highest, by walking the generic signature, which means test
output in one of the SILGen tests has changed.
A GenericEnvironment stores the mapping between GenericTypeParamTypes
and context archetypes (or eventually, concrete types, once we allow
extensions to constrain a generic parameter to a concrete type).
The goals here are two-fold:
- Eliminate the GenericTypeParamDecl::getArchetype() method, and
always use mapTypeIntoContext() instead
- Replace SILFunction::ContextGenericParams with a GenericEnvironment
This patch adds the new data type as well as serializer and AST
verifier support. but nothing else uses it yet.
Note that GenericSignature::get() now asserts if there are no
generic parameters, instead of returning null. This requires a
few tweaks here and there.
