John McCall 12b8a92e9d In generic functions, derive local type data for associated types ...

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.

2016-02-22 01:02:31 -08:00

19 KiB

Raw Permalink Blame History

View Raw