Fix #12919 by making the flattener homogeneous.

Authored by goldfire on Aug 14 2017, 3:18 PM.


Trac Issues

This changes a key invariant of the flattener. Previously,
flattening a type meant flattening its kind as well. But now,
flattening is always homogeneous -- that is, the kind of the
flattened type is the same as the kind of the input type.
This is achieved by various wizardry in the TcFlatten.flatten_many
function, as described in Note [flatten_many].

There are several knock-on effects, including some refactoring
in the canonicalizer to take proper advantage of the flattener's
changed behavior. In particular, the tyvar case of can_eq_nc' no
longer needs to take casts into account.

Another effect is that flattening a tyconapp might change it
into a casted tyconapp. This might happen if the result kind
of the tycon contains a variable, and that variable changes
during flattening. Because the flattener is homogeneous, it tacks
on a cast to keep the tyconapp kind the same. However, this
is problematic when flattening CFunEqCans, which need to have
an uncasted tyconapp on the LHS and must remain homogeneous.
The solution is a more involved canCFunEqCan, described in
Note [canCFunEqCan].

This patch fixes Trac #13643 (as tested in typecheck/should_compile/T13643)
and the panic in typecheck/should_compile/T13822 (as reported in Trac #14024).
Actually, there were two bugs in T13822: the first was just some
incorrect logic in tryFill (part of the unflattener) -- also fixed
in this patch -- and the other was the main bug fixed in this ticket.

The changes in this patch exposed a long-standing flaw in OptCoercion,
in that breaking apart an AppCo sometimes has unexpected effects on
kinds. See new Note [EtaAppCo] in OptCoercion, which explains the
problem and fix.

Also here is a reversion of the major change in
09bf135ace55ce2572bf4168124d631e386c64bb, affecting ctEvCoercion.
It turns out that making the flattener homogeneous changes the
invariants on the algorithm, making the change in that patch
no longer necessary.

Test Plan


goldfire created this revision.Aug 14 2017, 3:18 PM

I expect this patch to cause breakage of performance tests, but I wanted to make sure the general approach was good before spending lots of time on performance.

I don't have a detailed review other than that there's a typo in the title of this Diff (homegeneous -> homogeneous).

goldfire planned changes to this revision.Sep 7 2017, 6:06 PM
goldfire retitled this revision from Fix #12919 by making the flattener homegeneous. to Fix #12919 by making the flattener homogeneous..

@simonpj and I went over this briefly in person at ICFP. He suggested improvements, which I will apply in due course.

goldfire updated this revision to Diff 14186.Sep 28 2017, 2:51 PM

Apply Simon's comments from ICFP.

simonpj added inline comments.Sep 29 2017, 10:21 AM

Reproduce F2 here for reference


not just functions!


Also point out that the obvious solution (flattened types have flattened kinds) doesn't work, pointing to a note that explains why not.

bgamari requested changes to this revision.Oct 3 2017, 12:27 PM

I'll readily admit that I'm not very confident in my ability to review this.

If I'm not mistaken we don't actually ever ASSERT that the new invariant is actually held. It seems like this may be a useful (if, perhaps, expensive) thing to do.

Regardless, bumping out of the review queue.


This could use some clarification.

This revision now requires changes to proceed.Oct 3 2017, 12:27 PM
austin resigned from this revision.Nov 9 2017, 5:37 PM
dfeuer updated the Trac tickets for this revision.Dec 12 2017, 12:13 PM