The canonical order on associated types compares the name before the
protocol, so for example T.[P2:A] < T.[P1:B]. Make sure the reduction
order does the same so that we correctly compute canonical types in
this case.
The left and right hand side of a merged associated type candidate rule
have a common prefix except for the associated type symbol at the end.
Instead of passing two MutableTerms, we can pass a single uniqued
Term and a Symbol.
Also, we can compute the merged symbol before pushing the candidate
onto the vector. This avoids unnecessary work if the merged symbol
is equal to the right hand side's symbol.
If we have a rule
X.[P:A] => X.[Q:A]
And Q inherits from P, then the merged symbol is [Q:A] and not [P&Q:A].
In this case, the merge operation won't produce any new rules, so we can
just skip it entirely.
If we have a rewrite rule of the form
X.[P:A] => X.[Q:A]
We introduce a pair of rules
X.[P:A] => X.[P&Q:A]
X.[Q:A] => X.[P&Q:A]
But in reality only the second one is necessary. The first one is redundant
because you obtain the same result by applying the original rule followed by
the second rule.
In a confluent rewrite system, if the left hand side of a rule
X => Y can be reduced by some other rule X' => Y', then it is
permissible to delete the original rule X => Y altogether.
Confluence means that rewrite rules can be applied in any
order, so it is always valid to apply X' => Y' first, thus
X => Y is obsolete.
This was previously done in the completion procedure via a
quadratic algorithm that attempted to reduce each existing
rule via the newly-added rule obtained by resolving a critical
pair. Instead, we can do this in the post-processing pass
where we reduce right hand sides using a trie to speed up
the lookup.
This increases the amount of work performed by the
completion procedure, but eliminates the quadratic algorithm,
saving time overall.
The PropertyMap wants to use a try to map to PropertyBags, and it
needs longest-suffix rather than shortest-prefix matching.
Implement both by making Trie into a template class with two
parameters; the ValueType, and the MatchKind.
Note that while the MatchKind encodes the longest vs shortest
match part, matching on the prefix vs suffix of a term is up
to the caller, since the find() and insert() methods of Trie
take a pair of iterators, so simply passing in begin()/end() vs
rbegin()/rend() selects the direction.
Previously RewriteSystem::simplify() would attempt to apply every
rewrite rule at every position in the original term, which was
obviously a source of overhead.
The trie itself is somewhat unoptimized; for example, with a bit of
effort it could merge a node with its only child, if nodes stored
a range of elements to compare rather than a single element.
RewriteSystem::addRule() did two things before adding the rewrite rule:
- Simplify both sides. If both sides are now equal, discard the rule.
- If the last symbol on the left hand side was a superclass or concrete type
symbol, simplify the substitution terms in that symbol.
The problem is that the second step can produce a term which can be further
simplified, and in particular, one that is exactly equal to the left hand
side of some other rule.
To fix this, swap the order of the two steps. The only wrinkle is now we
have to check for a concrete type symbol at the end of _both_ the left hand
side and right hand side, since we don't orient the rule until we simplify
both sides.
I don't have a reduced test case for this one, but it was revealed by
compiler_crashers_2_fixed/0109-sr4737.swift after I introduced the trie.
protocol Q {
associatedtype T where T == Self?
}
func foo<X, Y : Q>(_: X, _: Y) {}
This generates the rewrite system
[Q:T].[concrete: Optional<τ_0_0> with <[Q]>]
τ_0_1.[Q] => τ_0_1
With this property map:
[Q:T] => { [concrete: Optional<τ_0_0> with <[Q]>] }
τ_0_1 => { [Q] }
Suppose we're resolving the concrete type τ_0_1.[Q:T]. The property map
entry is keyed by [Q:T], so the prefix τ_0_1 must be prepended to the
concrete substitutions of [concrete: Optional<τ_0_0> with <[Q]>].
However, [Q] is just the protocol Self type, and τ_0_0.[Q] is not a
valid type-like term. We could simplify the term before building the
Swift type which would apply the second rewrite rule, but it's easier
to just drop the protocol symbol in this case.
Just as with concrete types, if we find that the same suffix has two
different superclass symbols in the property map, we need to introduce
same-type requirements between their generic parameters.
The added wrinkle is that the classes might be different; in this case,
one must be a superclass of the other, and we repeatedly substitute
the generic arguments until we get the generic arguments of the
superclass before we unify.
Also, introduce the layout requirement implied by a superclass requirement
when lowering requirements, instead of when building the property map.
Right now this is functionally equivalent, but if we ever start to
test properties by checking for joinability of T with T.[p] instead of
looking at the property map entry of T, this new formulation is the
right one.
The property map stores the concrete type or superclass bound for all
terms whose suffix is equal to some key, so eg if you have
protocol P {
associatedtype T where T == U?
associatedtype U
}
Then you have this rewrite system
[P].T => [P:T]
[P].U => [P:U]
[P:T].[concrete: Optional<τ_0_0> with <[P:U]>] => [P:T]
Which creates this property map
[P:T] => { [concrete: Optional<τ_0_0> with <[P:U]>] }
Now if I start with a generic signature like
<T, U where U : P>
This produces the following rewrite system:
τ_0_1.[U] => τ_0_1
τ_0_1.T => τ_0_1.[P:T]
τ_0_1.U => τ_0_1.[P:U]
Consider the computation of the canonical type of τ_0_1.T. This term
reduces to τ_0_1.[P:T]. The suffix [P:T] has a concrete type symbol in
the property map, [concrete: Optional<τ_0_0> with <[P:U]>].
However it would not be correct to canonicalize τ_0_1.[P:T] to
Optional<τ_0_0>.subst { τ_0_0 => getTypeForTerm([P:T]) }; this
produces the type Optional<τ_0_0.T>, and not Optional<τ_0_1.T> as
expected.
The reason is that the substitution τ_0_0 => getTypeForTerm([P:T])
is "relative" to the protocol Self type of P, since domain([P:T]) = {P}.
Indeed, the right solution here is to note that τ_0_1.[P:T] has a suffix
equal to the key of the property map entry, [P:T]. If we strip off the
suffix, we get τ_0_1. If we then prepend τ_0_1 to the substitution term,
we get the term τ_0_1.[P:U], whose canonical type is τ_0_1.U.
Now, applying the substitution τ_0_0 => τ_0_1.U to Optional<τ_0_0>
produces the desired result, Optional<τ_0_1.U>.
Note that this is the same "prepend a prefix to each substitution of
a concrete type symbol" operation that is performed in checkForOverlap()
and PropertyBag::copyPropertiesFrom(), however we can simplify things
slightly by open-coding it instead of calling the utility method
prependPrefixToConcreteSubstitutions(), since the latter creates a
new symbol, which we don't actually need.
