Replace two prominent uses of SubstitutionList, in ConcreteDeclRef and
Witness, with SubstitutionMap. Deal with the myriad places where we
now have substitution maps and need substitution lists (or vice versa)
caused by this change.
Overall, removes ~50 explicit uses of SubstitutionList (of ~400).
Replace manual substitution mapping by using the existing ProtocolConformanceRef::getAssociatedConformance helper to look up the Equatable conformance from Hashable. Replace use of manual Substitution construction with SubstitutionMaps.
The key path pattern needs to include a reference to the external descriptor, along with hooks for lowering its type arguments and indices, if any. The runtime will need to instantiate and interpolate the external component when the key path object is instantiated.
While we're here, let's also reserve some more component header bytes for future expansion, since this is an ABI we're going to be living with for a while.
This will allow key paths to resiliently reference public properties from other binaries by referencing a descriptor vended by the originating binary. NFC yet, this just provides printing/parsing/verification of the new component.
Except GenericEnvironment.h, because you can't meaningfully use a
GenericEnvironment without its signature. Lots less depends on
GenericSignature.h now. NFC
We shouldn’t need a potential archetype to map an interface type to a
contextual type. Port `getTypeInContext()` over to `EquivalenceClass`,
largely unchanged, so we don’t directly form archetypes.
Kills a few more uses of `GenericSignatureBuilder::resolveArchetype()`.
SubstitutionMap::lookupConformance() would map archetypes out
of context to compute a conformance path. Do the same thing
in SubstitutionMap::lookupSubstitution().
The DenseMap of replacement types in a SubstitutionMap now
always has GenericTypeParamTypes as keys.
This simplifies some code and brings us one step closer to
a more efficient representation of SubstitutionMaps.
The core substitution routine for the archetypes-to-interface types
substitution was attempting to provide mappings for nested archetypes,
when in fact these archetypes would (1) always be resolvable via their
parent, and (2) could in fact cause infinite recursion, as with the
new test case. Fixes SR-4617 / rdar://problem/31673819.
Rather than detecting recursion and bailing early, delay requirements
that would form recursive types. Note that we aren't actually
processing them later.
When looking for a conformance for an archetype, map it out of context
to compute the conformance access path, then do the actual lookups
based on mapping the starting type back into the context. Eliminate
the parent map and "walk the conformances" functionality.
Substitution maps are effectively tied to a particular generic
signature or environment; keep track of that signature/environment so
that we can (eventually) use it to find conformances.
This was a remnant of the old generics implementation, where
all nested types were expanded into an AllArchetypes list.
For quite some time, this method no longer returned *all*
dependent types, only those with generic requirements on
them, and all if its remaining uses were a bit convoluted.
- In the generic specialization code, we used this to mangle
substitutions for generic parameters that are not subject
to a concrete same-type constraint.
A new GenericSignature::getSubstitutableParams()
function handles this use-case instead. It is similar
to getGenericParams(), but only returns generic parameters
which require substitution.
In the future, SubstitutionLists will only store replacement
types for these generic parameters, instead of the list of
types that we used to produce from getAllDependentTypes().
- In specialization mangling and speculative devirtualization,
we relied on SubstitutionLists having the same size and
order as getAllDependentTypes(). It's better to turn the
SubstitutionList into a SubstitutionMap instead, and do lookups
into the map.
- In the SIL parser, we were making a pass over the generic
requirements before looking at getAllDependentTypes();
enumeratePairedRequirements() gives the correct information
upfront.
- In SIL box serialization, we don't serialize the size of the
substitution list, since it's available from the generic
signature. Add a GenericSignature::getSubstitutionListSize()
method, but that will go away soon once SubstitionList
serialization only serializes replacement types for generic
parameters.
- A few remaining uses now call enumeratePairedRequirements()
directly.
It turns out that GenericSignature::getAllDependentTypes() sometimes
includes generic type parameter types that have been made
concrete. Tolerate this for now, because fixing it causes issues
elsewhere.
These are no longer necessary now that we have combineSubstitutionMaps(),
and will not make sense once we switch to a more compact representation
for SubstitutionMap.
This method maps interface types to archetypes, which in general
requires a module for performing conformance lookups, if mapping
a member type of a generic parameter which has been made concrete.
However, in practice the types we are mapping here are all canonical
with respect to the generic signature, because they came from
GenericSignature::getAllDependentTypes(), so we actually don't need
to do conformance lookups.
This allows some code to be simplified.
SubstitutionList is going to be a more compact representation of
a SubstitutionMap, suitable for inline allocation inside another
object.
For now, it's just a typedef for ArrayRef<Substitution>.
Just like the recently-added GenericSignature::getSubstitutionMap(),
this takes a type substitution function and conformance lookup
function and produces a new SubstitionMap.
Introduce an algorithm to canonicalize and minimize same-type
constraints. The algorithm itself computes the equivalence classes
that would exist if all explicitly-provided same-type constraints are
ignored, and then forms a minimal, canonical set of explicit same-type
constraints to reform the actual equivalence class known to the type
checker. This should eliminate a number of problems we've seen with
inconsistently-chosen same-type constraints affecting
canonicalization.
Instead of creating an archetype builder with a module---which was
only used for protocol conformance lookups of concrete types
anyway---create it with a LookupConformanceFn. This is NFC for now,
but moves us closer to making archetype builders more canonicalizable
and reusable.
Teach the serialized form of ArchetypeType about its owning generic
environment, so we can wire up the generic environment of (primary)
archetypes eagerly (at the point of deserialization) rather than when
we form the generic environment. This ensures that there is no point
at which we have a (non-opened-existential) archetype without a
generic environment.
... except that the type reconstruction code creates such archetypes.
Fixes assertion failures in SILGen and the optimizer with this
exotic setup:
protocol P {
associatedtype T : Q
}
protocol Q {
func requirement<U : P>(u: U) where U.T == Self
}
Here, we only have a U : P conformance, and not Self : Q,
because Self : Q is available as U.T : Q.
There were three problems here:
- The SIL verifier was too strict in verifying the generic signature.
All that matters is we can get the Self parameter conformance, not
that it's the first requirement, etc.
- GenericSignature::getSubstitutionMap() had a TODO concerning handling
of same-type constraints -- this is the first test-case I've found
that triggered the problem.
- GenericEnvironment::getSubstitutionMap() incorrectly ignored
same-type constraints where one of the two types was a generic
parameter.
Fixes <https://bugs.swift.org/browse/SR-3321>.
- The DeclContext versions of these methods have equivalents
on the DeclContext class; use them instead.
- The GenericEnvironment versions of these methods are now
static methods on the GenericEnvironment class. Note that
these are not made redundant by the instance methods on
GenericEnvironment, since the static methods can also be
called with a null GenericEnvironment, in which case they
just assert that the type is fully concrete.
- Remove some unnecessary #includes of ArchetypeBuilder.h
and GenericEnvironment.h. Now changes to these files
result in a lot less recompilation.
Serialize generic environments via a generic environment ID with a
separte offset table, so we have identity for the generic environments
and will share generic environments on deserialization.
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.
