Note [Overview of implicit CallStacks]

(See https://gitlab.haskell.org/ghc/ghc/wikis/explicit-call-stack/implicit-locations)

The goal of CallStack evidence terms is to reify locations
in the program source as runtime values, without any support
from the RTS. We accomplish this by assigning a special meaning
to constraints of type GHC.Stack.Types.HasCallStack, an alias

  type HasCallStack = (?callStack :: CallStack)

Implicit parameters of type GHC.Stack.Types.CallStack (the /name/ of the
implicit parameter is not important, see (CS5) below) are solved as follows:

1. Plan NORMAL. Explicit, user-written occurrences of `?stk :: CallStack`, which
   have IPOccOrigin, are solved directly from the given IP, just like any other
   implicit-parameter constraint; see GHC.Tc.Solver.Dict.tryInertDicts. We can
   solve it from a Given or from another Wanted, if the two have the same type.

   For example, the occurrence of `?stk` in

     error :: (?stk :: CallStack) => String -> a
     error s = raise (ErrorCall (s ++ prettyCallStack ?stk))

   will be solved for the `?stk` in `error`s context as before.

2. Plan PUSH.  A /function call/ with a CallStack constraint, such as
   a call to `foo` where
        foo :: (?stk :: CallStack) => a
   will give rise to a Wanted constraint
        [W] d :: (?stk :: CallStack)    CtOrigin = OccurrenceOf "foo"

   We do /not/ solve this constraint from Givens, or from other
   Wanteds.  Rather, have a built-in mechanism in that solves it thus:
        d := EvCsPushCall "foo" <details of call-site of `foo`> d2
        [W] d2 :: (?stk :: CallStack)    CtOrigin = IPOccOrigin

   That is, `d` is a call-stack that has the `foo` call-site pushed on top of
   `d2`, which can now be solved normally (as in (1) above).  This is done as follows:
     - In GHC.Tc.Solver.Dict.canDictCt we do the pushing.
     - We only look up canonical constraints in the inert set

3. For a CallStack constraint, we choose how to solve it based on its CtOrigin:

     * solve it normally (plan NORMAL above)
         - IPOccOrigin (discussed above)
         - GivenOrigin (see (CS1) below)

     * push an item on the stack and emit a new constraint (plan PUSH above)
         - OccurrenceOf "foo" (discused above)
         - anything else      (see (CS1) below)

   This choice is by the predicate isPushCallStackOrigin_maybe

4. We default any insoluble CallStacks to the empty CallStack. Suppose
   `undefined` did not request a CallStack, ie

     undefinedNoStk :: a
     undefinedNoStk = error "undefined!"

   Under the usual IP rules, the new wanted from rule (2) would be
   insoluble as there's no given IP from which to solve it, so we
   would get an "unbound implicit parameter" error.

   We don't ever want to emit an insoluble CallStack IP, so we add a
   defaulting pass to default any remaining wanted CallStacks to the
   empty CallStack with the evidence term

     EvCsEmpty

   (see GHC.Tc.Solver.simplifyTopWanteds and GHC.Tc.Solver.defaultCallStacks)

This provides a lightweight mechanism for building up call-stacks
explicitly, but is notably limited by the fact that the stack will
stop at the first function whose type does not include a CallStack IP.
For example, using the above definition of `undefined`:

  head :: [a] -> a
  head []    = undefined
  head (x:_) = x

  g = head []

the resulting CallStack will include the call to `undefined` in `head`
and the call to `error` in `undefined`, but *not* the call to `head`
in `g`, because `head` did not explicitly request a CallStack.


Wrinkles

(CS1) Which CtOrigins should qualify for plan PUSH?  Certainly ones that arise
   from a function call like (f a b).

   But (see #19918) when RebindableSyntax is involved we can function call whose
   CtOrigin is somethign like `IfThenElseOrigin`. See the defn of fun_orig in
   GHC.Tc.Gen.App.tcInstFun; it is this CtOrigin that is pinned on the
   constraints generated by functions in the "expansion" for rebindable
   syntax. c.f. GHC.Rename.Expr Note [Handling overloaded and rebindable
   constructs].

   So isPushCallStackOrigin_maybe has a fall-through for "anything else", and
   assumes that we should adopt plan PUSH for it.

   However we should /not/ take this fall-through for Given constraints
   (#25675).  So isPushCallStackOrigin_maybe identifies Givens as plan NORMAL.

(CS2) GHC should NEVER report an insoluble CallStack constraint.

(CS3) GHC should NEVER infer a CallStack constraint unless one was requested
  with a partial type signature (See GHC.Tc.Solver..pickQuantifiablePreds).

(CS4) A CallStack (defined in GHC.Stack.Types) is a [(String, SrcLoc)],
  where the String is the name of the binder that is used at the
  SrcLoc. SrcLoc is also defined in GHC.Stack.Types and contains the
  package/module/file name, as well as the full source-span. Both
  CallStack and SrcLoc are kept abstract so only GHC can construct new
  values.

(CS5) We will automatically solve any wanted CallStack regardless of the
  /name/ of the IP, i.e.

    f = show (?stk :: CallStack)
    g = show (?loc :: CallStack)

  are both valid. However, we will only push new SrcLocs onto existing
  CallStacks when the IP names match, e.g. in

    head :: (?loc :: CallStack) => [a] -> a
    head [] = error (show (?stk :: CallStack))

  the printed CallStack will NOT include head's call-site. This reflects the
  standard scoping rules of implicit-parameters.

(CS6) An EvCallStack term desugars to a CoreExpr of type `IP "some str" CallStack`.
  The desugarer will need to unwrap the IP newtype before pushing a new
  call-site onto a given stack (See GHC.HsToCore.Binds.dsEvCallStack)

(CS7) When we emit a new wanted CallStack in plan PUSH we set its origin to
  `IPOccOrigin ip_name` instead of the original `OccurrenceOf func`
  (see GHC.Tc.Solver.Dict.tryInertDicts).

  This is a bit shady, but is how we ensure that the new wanted is
  solved like a regular IP.