Rework the Implicit CallStack solver to handle local lets.
ClosedPublic

Authored by gridaphobe on Nov 2 2015, 1:31 AM.

Details

Summary

We can't just solve CallStack constraints indiscriminately when they occur in the RHS of a let-binder. The top-level given CallStack (if any) will not be in scope, so I've re-worked the CallStack solver as follows:

  1. CallStacks are treated like regular IPs unless one of the following two rules apply.
  2. In a function call, we push the call-site onto a NEW wanted CallStack, which GHC will solve as a regular IP (either directly from a given, or by quantifying over it in a local let).
  3. If, after the constraint solver is done, any wanted CallStacks remain, we default them to the empty CallStack. This rule exists mainly to clean up after rule 2 in a top-level binder with no given CallStack.

In rule (2) we have to be careful to emit the new wanted with an IPOccOrigin instead of an OccurrenceOf origin, so rule (2) doesn't fire again. This is a bit shady but I've updated the Note to explain the trick.

Test Plan

validate

Diff Detail

Repository
rGHC Glasgow Haskell Compiler
Lint
Automatic diff as part of commit; lint not applicable.
Unit
Automatic diff as part of commit; unit tests not applicable.
There are a very large number of changes, so older changes are hidden. Show Older Changes

rebased against master, and updated the CallStack note to motivate the defaulting pass.

simonpj requested changes to this revision.Nov 3 2015, 7:40 AM

See comment:13 on the Trac ticket.

compiler/typecheck/TcSimplify.hs
168

You aren't missing anything. Up to now the deal is: defaulting may unify some type variables and then we try again to solve the original constraint. But here you are actually solving the entire constraint, which is quite different.

And what you have is not so terrible. And it'll get simpler (see my comment on the Trac ticket)

This revision now requires changes to proceed.Nov 3 2015, 7:40 AM
gridaphobe updated this revision to Diff 5376.Nov 30 2015, 5:17 PM
gridaphobe retitled this revision from Add a defaulting handler for CallStacks to Rework the Implicit CallStack solver to handle local lets..
gridaphobe updated this object.

rework the callstack solver based on http://ghc.haskell.org/trac/ghc/ticket/10845#comment:15

gridaphobe updated this revision to Diff 5377.Nov 30 2015, 5:19 PM

add an inline comment about changing the origin of the new wanted

gridaphobe updated this revision to Diff 5380.Nov 30 2015, 10:57 PM

default *all* remaining CallStacks, update test output

One important thing to note about this revision: there are cases where we will now infer CallStacks even for top-level binders, as evidenced by the updated test output.

I think this is OK though because GHC would infer a regular IP for these functions as well, ie it's a consequence of making Implicit CallStacks less magical.

compiler/typecheck/TcInteract.hs
2108

I'm not very happy with this function, it's doing far too much. It should just return the necessary data to solve the callstack, ie checkOrigins functionality should be split between the two call-sites in TcInteract.interactDict and TcSimplify.defaultCallStacks.

The problem is that it takes quite a few pieces of data to solve the call-stack, particularly for the "push" case. So the option appears to be to return a giant tuple or extract the data from the Ct twice, both of which seem a bit silly. Perhaps this is just a case of premature optimization..

I'll take another look at restructuring this tomorrow.

testsuite/tests/th/T1849.stderr
2 ↗(On Diff #5380)

Self note: this updated output is technically correct, but I probably want to change the test case so it does not trigger an error. Need to check Trac #1849 to see what it's supposed to test.

gridaphobe updated this revision to Diff 5382.Nov 30 2015, 11:20 PM

oops, delete T1849.stderr

gridaphobe marked an inline comment as done.Nov 30 2015, 11:21 PM

Generally looks good to me.

compiler/typecheck/TcInteract.hs
2108

I agree this is nasty.

Why not return the Ct; or CtEvidence? It has all the info, doesn't it?

2129

Refer to the Note that explains

gridaphobe updated this revision to Diff 5401.Dec 1 2015, 3:30 PM

remove isCallStackIP and split the solving logic between the two call-sites

gridaphobe marked 3 inline comments as done.Dec 1 2015, 3:52 PM
gridaphobe updated this revision to Diff 5406.Dec 1 2015, 4:12 PM

merge master and resolve a conflict in expected test output

gridaphobe updated this revision to Diff 5407.Dec 1 2015, 4:40 PM

add a test-case for Trac #10846, which appears to be fixed as of 1e041b7, thanks @simonpj!

gridaphobe updated this revision to Diff 5410.Dec 1 2015, 10:08 PM

Hrm, my laptop seems to be disagreeing with Harbormaster on the order of tyvars in ExtraConstraints3... I'll assume Harbormaster is correct :)

I'd like to get this merged before the 8.0 branch, if possible. Let me know if there's anything I can do to help.

simonpj accepted this revision.Dec 3 2015, 5:26 PM

Let's land this

This revision is now accepted and ready to land.Dec 3 2015, 5:26 PM
gridaphobe updated this revision to Diff 5449.Dec 3 2015, 11:32 PM

update the docs and make CallStack abstract again.

bgamari requested changes to this revision.Dec 7 2015, 4:26 AM

@gridaphobe, I believe validation may be failing on this. I've restarted the Harbormaster build just to be sure, but do you suppose you could have a look at this?

This revision now requires changes to proceed.Dec 7 2015, 4:26 AM
gridaphobe updated this revision to Diff 5536.Dec 7 2015, 11:08 AM

merge master, fix a broken test, update docs

gridaphobe updated this revision to Diff 5540.Dec 7 2015, 12:10 PM

rename showCallStack to prettyCallStack, export everything from GHC.Stack, clean up docs.

hvr requested changes to this revision.Dec 7 2015, 12:24 PM
hvr added inline comments.
libraries/base/GHC/Stack/Types.hs
103

@since 4.9.0.0 seems missing here

This revision now requires changes to proceed.Dec 7 2015, 12:24 PM
hvr added a comment.Dec 7 2015, 12:25 PM

rename showCallStack to prettyCallStack, export everything from GHC.Stack, clean up docs.

please don't forget to add a base/changelog.md entry

gridaphobe updated this revision to Diff 5552.Dec 7 2015, 5:18 PM

update base/changelog.md

In D1422#46768, @hvr wrote:

rename showCallStack to prettyCallStack, export everything from GHC.Stack, clean up docs.

please don't forget to add a base/changelog.md entry

Ack, I didn't even realize base had a changelog separate from the one in the User's Guide, thanks!

@bgamari @hvr, if there's nothing else, can we mark this as accepted again and land it? Thanks!

bgamari accepted this revision.Dec 11 2015, 10:52 AM

@bgamari @hvr, if there's nothing else, can we mark this as accepted again and land it? Thanks!

Thanks for the ping! Looks good to me other than one small objection. I'll merge but perhaps you could fix up the inline comment in a later commit.

compiler/typecheck/TcEvidence.hs
572

My only complaint here is that it's a bit unclear from this text which of the above definitions of undefined you are referring to. Perhaps you could name the non-callstack-aware variant undefined' or something similar to prevent confusion?

gridaphobe updated this revision to Diff 5626.Dec 11 2015, 8:24 PM

merge master and update examples in the Note

gridaphobe marked an inline comment as done.Dec 11 2015, 8:25 PM
This revision was automatically updated to reflect the committed changes.