Simon Peyton Jones authored 1 year ago and Marge Bot committed 1 year ago

This refactoring makes a substantial improvement in the
structure of the type-checker's constraint solver: #23070.

Specifically:

* Introduced the SolverStage monad.   See GHC.Tc.Solver.Monad
  Note [The SolverStage monad]

* Make each solver pipeline (equalities, dictionaries, irreds etc)
  deal with updating the inert set, as a separate SolverStage.  There
  is sometimes special stuff to do, and it means that each full
  pipeline can have type SolverStage Void, indicating that they never
  return anything.

* Made GHC.Tc.Solver.Equality.zonkEqTypes into a SolverStage.  Much nicer.

* Combined the remnants of GHC.Tc.Solver.Canonical and
  GHC.Tc.Solver.Interact into a new module GHC.Tc.Solver.Solve.
  (Interact and Canonical are removed.)

* Gave the same treatment to dictionary and irred constraints
  as I have already done for equality constraints:
    * New types (akin to EqCt): IrredCt and DictCt
    * Ct is now just a simple sum type
          data Ct
            = CDictCan      DictCt
            | CIrredCan     IrredCt
            | CEqCan        EqCt
            | CQuantCan     QCInst
            | CNonCanonical CtEvidence
    * inert_dicts can now have the better type DictMap DictCt, instead of
      DictMap Ct; and similarly inert_irreds.

* Significantly simplified the treatment of implicit parameters.
  Previously we had a number of special cases
    * interactGivenIP, an entire function
    * special case in maybeKickOut
    * special case in findDict, when looking up dictionaries
  But actually it's simpler than that. When adding a new Given, implicit
  parameter constraint to the InertSet, we just need to kick out any
  existing inert constraints that mention that implicit parameter.

  The main work is done in GHC.Tc.Solver.InertSet.delIPDict, along with
  its auxiliary GHC.Core.Predicate.mentionsIP.

  See Note [Shadowing of implicit parameters] in GHC.Tc.Solver.Dict.

* Add a new fast-path in GHC.Tc.Errors.Hole.tcCheckHoleFit.
  See Note [Fast path for tcCheckHoleFit].  This is a big win in some cases:
  test hard_hole_fits gets nearly 40% faster (at compile time).

* Add a new fast-path for solving /boxed/ equality constraints
  (t1 ~ t2).  See Note [Solving equality classes] in GHC.Tc.Solver.Dict.
  This makes a big difference too: test T17836 compiles 40% faster.

* Implement the PermissivePlan of #23413, which concerns what happens with
  insoluble Givens.   Our previous treatment was wildly inconsistent as that
  ticket pointed out.

  A part of this, I simplified GHC.Tc.Validity.checkAmbiguity: now we simply
  don't run the ambiguity check at all if -XAllowAmbiguousTypes is on.

Smaller points:

* In `GHC.Tc.Errors.misMatchOrCND` instead of having a special case for
  insoluble /occurs/ checks, broaden in to all insouluble constraints.
  Just generally better. See Note [Insoluble mis-match] in that module.

As noted above, compile time perf gets better.  Here are the changes
over 0.5% on Fedora.  (The figures are slightly larger on Windows for
some reason.)

Metrics: compile_time/bytes allocated
-------------------------------------
                LargeRecord(normal)   -0.9%
MultiLayerModulesTH_OneShot(normal)   +0.5%
                     T11822(normal)   -0.6%
                     T12227(normal)   -1.8% GOOD
                     T12545(normal)   -0.5%
                     T13035(normal)   -0.6%
                     T15703(normal)   -1.4% GOOD
                     T16875(normal)   -0.5%
                     T17836(normal)  -40.7% GOOD
                    T17836b(normal)  -12.3% GOOD
                    T17977b(normal)   -0.5%
                      T5837(normal)   -1.1%
                      T8095(normal)   -2.7% GOOD
                      T9020(optasm)   -1.1%
             hard_hole_fits(normal)  -37.0% GOOD

                          geo. mean   -1.3%
                          minimum    -40.7%
                          maximum     +0.5%

Metric Decrease:
    T12227
    T15703
    T17836
    T17836b
    T8095
    hard_hole_fits
    LargeRecord
    T9198
    T13035