Note [The Unification Level Flag]
Consider a deep tree of implication constraints
forall[1] a. -- Outer-implic
C alpha[1] -- Simple
forall[2] c. ....(C alpha[1]).... -- Implic-1
forall[2] b. ....(alpha[1] ~ Int).... -- Implic-2
The (C alpha) is insoluble until we know alpha. We solve alpha
by unifying alpha:=Int somewhere deep inside Implic-2. But then we
must try to solve the Outer-implic all over again. This time we can
solve (C alpha) both in Outer-implic, and nested inside Implic-1.
When should we iterate solving a level-n implication?
Answer: if any unification of a tyvar at level n takes place
in the ic_implics of that implication.
* What if a unification takes place at level n-1? Then don't iterate
level n, because we'll iterate level n-1, and that will in turn iterate
level n.
* What if a unification takes place at level n, in the ic_simples of
level n? No need to track this, because the kick-out mechanism deals
with it. (We can't drop kick-out in favour of iteration, because kick-out
works for skolem-equalities, not just unifications.)
So the monad-global Unification Level Flag, kept in tcs_unif_lvl keeps
track of
- Whether any unifications at all have taken place (Nothing => no unifications)
- If so, what is the outermost level that has seen a unification (Just lvl)
The iteration is done in the simplify_loop/maybe_simplify_again loop in GHC.Tc.Solver.
It helpful not to iterate unless there is a chance of progress. #8474 is
an example:
* There's a deeply-nested chain of implication constraints.
?x:alpha => ?y1:beta1 => ... ?yn:betan => [W] ?x:Int
* From the innermost one we get a [W] alpha[1] ~ Int,
so we can unify.
* It's better not to iterate the inner implications, but go all the
way out to level 1 before iterating -- because iterating level 1
will iterate the inner levels anyway.
(In the olden days when we "floated" thse Derived constraints, this was
much, much more important -- we got exponential behaviour, as each iteration
produced the same Derived constraint.) References 0
This Note does not link to any other.
Referenced by 6
- GivenInv GHC.Tc.Utils.TcType ×2
- Solve by unification GHC.Tc.Solver.Equality
- kickOutRewritable GHC.Tc.Solver.InertSet
- GHC.Tc.Solver.Monad call site
- GHC.Tc.Solver.Solve call site