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.
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>.
First, add some new utility methods to create SubstitutionMaps:
- GenericSignature::getSubstitutionMap() -- provides a new
way to directly build a SubstitutionMap. It takes a
TypeSubstitutionFn and LookupConformanceFn. This is
equivalent to first calling getSubstitutions() with the two
functions to create an ArrayRef<Substitution>, followed by
the old form of getSubstitutionMap() on the result.
- TypeBase::getContextSubstitutionMap() -- replacement for
getContextSubstitutions(), returning a SubstitutionMap.
- TypeBase::getMemberSubstitutionMap() -- replacement for
getMemberSubstitutions(), returning a SubstitutionMap.
With these in place, almost all existing uses of subst() taking
a ModuleDecl can now use the new form taking a SubstitutionMap
instead. The few remaining cases are explicitly written to use a
TypeSubstitutionFn and LookupConformanceFn.
When enumerating requirements, always use the archetype anchors to
express requirements. Unlike "representatives", which are simply there
to maintain the union-find data structure used to track equivalence
classes of potential archetypes, archetype anchors are the
ABI-stable canonical types within a fully-formed generic signature.
The test case churn comes from two places. First, while
representatives are *often* the same as the archetype anchors, they
aren't *always* the same. Where they differ, we'll see a change in
both the printed generic signature and, therefore, it's
mangling.
Additionally, requirement inference now takes much greater
care to make sure that the first types in the requirement follow
archetype anchor ordering, so actual conformance requirements occur in
the requirement list at the archetype anchor---not at the first type
that is equivalent to the anchor---which permits the simplification in
IRGen's emission of polymorphic arguments.
This commit introduces new kind of requirements: layout requirements.
This kind of requirements allows to expose that a type should satisfy certain layout properties, e.g. it should be a trivial type, have a given size and alignment, etc.
Use a syntax that declares the layout's generic parameters and fields,
followed by the generic arguments to apply to the layout:
{ var Int, let String } // A concrete box layout with a mutable Int
// and immutable String field
<T, U> { var T, let U } <Int, String> // A generic box layout,
// applied to Int and String
// arguments
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.
Introduce a new operation on generic signatures,
enumeratePairedRequirements(), which invokes a callback with each
(dependent type, set-of-conformance-requirements) pair that needs to
be recorded within substitutions. Switch the last two remaining
consumers of witness markers (GenericSignature::getAllDependentTypes()
and GenericSignature::getSubstitutions()) over to this new entrypoint.
This gives us a concept we can eventually use to cache the lowered physical layout of fragile structs and classes, and more immediately, concretize the layout of closure boxes in a way that lets us represent the capture of generic environments and multiple captured values without compromising the "nominal" nature of box layouts. To start exercising the basic implementation, change the representation of SILBoxType to be in terms of a SILLayout, though avoid any immediate functionality change by preserving the single-boxed-type interface for now.
Now that the previous patches have shaken out implicit assumptions
about the order of generic requirements and substitutions, we can
make a more radical change, dropping redundant protocol requirements
when building the original generic signature.
This means that the canonical ordering and minimization that we
used to only perform when building the mangling signature is done
all of the time, and hence getCanonicalManglingSignature() can go
away.
Usages now either call getCanonicalSignature(), or operate on the
original signature directly.
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.
Now that SILFunctions no longer reference a GenericParamList, we
don't need to de-serialize cross-module references to archetypes
anymore.
This was the last remaining usage of AllArchetypes, so we can
finally rip it out.
This is the opposite of GenericSignature::getSubstitutionMap(),
transforming an interface type substitution mapping into
a Substitution array.
Previously, Substitution arrays were built with hand-rolled
logic, usually relying on a GenericParamList's AllArchetypes
list. We want to stop using the AllArchetypes list, instead
using the requirements array from a GenericSignature.
Nothing calls this method yet; existing code will be refactored
to call it in the next few patches.
This is obviously the right thing to do in terms of ensuring
that two different expressions of the same signature always result
in the same type. It also has the pleasant side-effect of causing
the canonical function type to never be expressed in terms of type
parameters which have been equated with concrete types, which means
that various consumers that work primarily with canonical types
(such as SILGen and IRGen) no longer have to worry about such types,
at least when decomposing a generic function signature.
from the witness tables for their associations rather than passing
them separately.
This drastically reduces the number of physical arguments required
to invoke a generic function with a complex protocol hierarchy. It's
also an important step towards allowing recursive protocol
constraints. However, it may cause some performance problems in
generic code that we'll have to figure out ways to remediate.
There are still a few places in IRGen that rely on recursive eager
expansion of associated types and protocol witnesses. For example,
passing generic arguments requires us to map from a dependent type
back to an index into the all-dependent-types list in order to
find the right Substitution; that's something we'll need to fix
more generally. Specific to IRGen, there are still a few abstractions
like NecessaryBindings that use recursive expansion and are therefore
probably extremely expensive under this patch; I intend to fix those
up in follow-ups to the greatest extent possible.
There are also still a few things that could be made lazier about
type fulfillment; for example, we eagerly project the dynamic type
metadata of class parameters rather than waiting for the first place
we actually need to do so. We should be able to be lazier about
that, at least when the parameter is @guaranteed.
Technical notes follow. Most of the basic infrastructure I set up
for this over the last few months stood up, although there were
some unanticipated complexities:
The first is that the all-dependent-types list still does not
reliably contain all the dependent types in the minimized signature,
even with my last patch, because the primary type parameters aren't
necessarily representatives. It is, unfortunately, important to
give the witness marker to the primary type parameter because
otherwise substitution won't be able to replace that parameter at all.
There are better representations for all of that, but it's not
something I wanted to condition this patch on; therefore, we have to
do a significantly more expensive check in order to figure out a
dependent type's index in the all-dependent-types list.
The second is that the ability to add requirements to associated
types in protocol refinements means that we have to find the *right*
associatedtype declaration in order to find the associated witness
table. There seems to be relatively poor AST support for this
operation; maybe I just missed it.
The third complexity (so far) is that the association between an
archetype and its parent isn't particularly more important than
any other association it has. We need to be able to recover
witness tables linked with *all* of the associations that lead
to an archetype. This is, again, not particularly well-supported
by the AST, and we may run into problems here when we eliminate
recursive associated type expansion in signatures.
Finally, it's a known fault that this potentially leaves debug
info in a bit of a mess, since we won't have any informaton for
a type parameter unless we actually needed it somewhere.
When a dependent type is mapped into context, the result will either be
an archetype or a concrete type. The latter occurs if a same-type
constraint exists between the dependent type and the concrete type.
The logic to decide if a type should be passed directly or indirectly
was not handling this case if an interface type was passed down -- we
would just check if there was a class constraint present.
This resulted in mismatching conventions between an interface type and
its corresponding contextual type, which would trigger assertions.
Note that same-type constraints between generic parameters and concrete
types are still not supported for other reasons; the subject of the
constraint must still be an associated type of a generic parameter.
Fixes <rdar://problem/24687460>.
This class formalizes the common case of the "trailing allocation" idiom we use
frequently. I didn't spot any true bugs while making this change, but I did see
places where we were using the wrong pointer type or casting through void* for
no good reason. This will keep us honest.
I'll get to the other libraries soon.
Extend GenericSignature to be able to answer queries about the
requirements placed on dependent types, e.g, are the class-bound, to
what protocols must they conform, etc. Implement this using a
lazily-created ArchetypeBuilder on the canonical generic signature.
NFC and as-yet-untested; this is staging for reducing our dependence
on the "all archetypes" list.
Swift SVN r32340
GenericSignature's factory method determining whether the signature
was canonical based solely on whether the types in the parameters and
requirments were canonical. While that is currently true (for legacy
reasons), it is wrong: canonicalization also needs to canonicalize
requirements, including same-type requirements, as is currently done
in the canonical signature "for mangling". Move the "this is
canonical" dependency to the point where the canonical signature is
actually computed, so we can change the definition of canonical
signatures later.
While we're here, don't eagerly compute the canonical generic
signature in GenericSignature::getASTContext().
Swift SVN r32309
