If we failed to construct a rewrite system for a protocol, either because
the Knuth-Bendix algorithm failed or because of a request cycle while
resolving requirements, we would end up in a situation where the resulting
rewrite system didn't include all conformance requirements and associated
types, so name lookup would find declarations whose interface types are
not valid type parameters.
Fix this by propagating failure better and just doing nothing in
getReducedTypeParameter().
Fixes rdar://147277543.
The concrete nesting limit, which defaults to 30, catches
things like A == G<A>. However, with something like
A == (A, A), you end up with an exponential problem size
before you hit the limit.
Add two new limits.
The first is the total size of the concrete type, counting
all leaves, which defaults to 4000. It can be set with the
-requirement-machine-max-concrete-size= frontend flag.
The second avoids an assertion in addTypeDifference() which
can be hit if a certain counter overflows before any other
limit is breached. This also defaults to 4000 and can be set
with the -requirement-machine-max-type-differences= frontend flag.
Convert a bunch of places where we're dumping to stderr and calling
`abort` over to using `ABORT` such that the message gets printed to
the pretty stack trace. This ensures it gets picked up by
CrashReporter.
Although I don't plan to bring over new assertions wholesale
into the current qualification branch, it's entirely possible
that various minor changes in main will use the new assertions;
having this basic support in the release branch will simplify that.
(This is why I'm adding the includes as a separate pass from
rewriting the individual assertions)
We want `T.A == U.B` to imply `shape(T) == shape(U)` if T (and thus U)
is a parameter pack.
To do this, we introduce some new rewrite rules:
1) For each associated type symbol `[P:A]`, a rule `([P:A].[shape] => [P:A])`.
2) For each non-pack generic parameter `τ_d_i`, a rule `τ_d_i.[shape] => [shape]`.
Now consider a rewrite rule `(τ_d_i.[P:A] => τ_D_I.[Q:B])`. The left-hand
side overlaps with the rule `([P:A].[shape] => [shape])` on the term
`τ_d_i.[P:A].[shape]`. Resolving the overlap gives us a new rule
t_d_i.[shape] => T_D_I.[shape]
If T is a term corresponding to some type parameter, we say that `T.[shape]` is
a shape term. If `T'.[shape]` is a reduced term, we say that T' is the reduced
shape of T.
Recall that shape requirements are represented as rules of the form:
τ_d_i.[shape] => τ_D_I.[shape]
Now, the rules of the first kind reduce our shape term `T.[shape]` to
`τ_d_i.[shape]`, where `τ_d_i` is the root generic parameter of T.
If `τ_d_i` is not a pack, a rule of the second kind reduces it to `[shape]`,
so the reduced shape of a non-pack parameter T is the empty term.
Otherwise, if `τ_d_i` is a pack, `τ_d_i.[shape]` might reduce to `τ_D_I.[shape]`
via a shape requirement. In this case, `τ_D_I` is the reduced shape of T.
Fixes rdar://problem/101813873.
This basically undoes 3da6fe9c0d, which in hindsight was wrong.
There were no other usages of TypeArrayView anywhere else except for
GenericSignature::getGenericParams(), and it was almost never what
you want, so callers had to convert back and forth to an ArrayRef.
Remove it.
We had two notions of canonical types, one is the structural property
where it doesn't contain sugared types, the other one where it does
not contain reducible type parameters with respect to a generic
signature.
Rename the second one to a 'reduced type'.
initializing a RequirementMachine for a written protocol signature.
These generic parameters are used for re-sugaring when computing a
type from a term, so if the recorded 'Self' parameter is canonicalized,
it shows up in diagnostics as 'tau_0_0'.
A requirement machine built from existing protocol requirement signatures only
exists to cache those rules and allow them to be inherited by other machines.
Recording loops is unnecessary in this case, since no minimization will be
performed.
Completion has a maximum rule limit since the Knuth-Bendix algorithm
is a semi-decision procedure that does not terminate on all inputs.
However, this means that generic signatures which import a large
number of complex protocols can hit the limit even if they are
convergent.
Since imported rules are essentially free, ignore them here, to
avoid having to increase the limit by hand.
Now the default limit is 4000 local rules per requirement machine;
it seems implausible that you would exceed this, but if anyone has
an example we can bump the limit again.
initialization of the rewrite system.
Instead, the rewrite system can determine trivially redundant requirements
by finding structural requirements with no associated rewrite rules.
- Rename StepLimit to MaxRuleCount, DepthLimit to MaxRuleLength
- Rename command line flags to -requirement-machine-max-rule-{count,length}=
- Check limits outside of PropertyMap::buildPropertyMap()
- Simplify the logic in RequirementMachine::computeCompletion()
Conditional requirement inference needs to be able to add rewrite rules
from the requirement signatures of hitherto-unseen protocols, so to
help with that, extract out the RuleBuilder's ProtocolMap and move it
into the RewriteSystem.
When minimizing a generic signature, we only care about loops
where the basepoint is a generic parameter symbol.
When minimizing protocol requirement signatures in a connected
component, we only care about loops where the basepoint is a
protocol symbol or associated type symbol whose protocol is
part of the connected component.
All other loops can be discarded since they do not encode
redundancies that are relevant to us.
We assert when building a rewrite system for an existing generic
signature, or in AbstractGenericSignatureRequest, where there is no
source location.
In RequirementSignatureRequest and InferredGenericSignatureRequest
we now produce a diagnostic.
