Expand chains of type aliases without repeated occur checks
Why
Each alias in type t1<'a> = t0<('a, int)>, type t2<'a> = t1<('a, int)>, … was checked by expanding the whole chain several times, and every expansion step ran occur checks over arguments that grow along the chain: 200 aliases allocated 850M words and took 1.6 s. They now allocate 19M words and take 0.15 s.
Binding the fresh parameters of an expanded alias skips the occur check, since nothing can contain them yet. The constraint check skips type constructors whose parameters are distinct variables, which accept any arguments, and the cycle check forgets the expansions it memorized.
Review
- What remains superlinear? Expansions memorize each alias in one list shared along the chain, and looking an alias up scans it, a small cubic term: 800 aliases take 6.7 s, 290M words.