The renamer

Here are the expressions that we transform in this way. Some are uniform,
but several have a little bit of special treatment:

* HsIf (if-the-else)
     if b then e1 else e2  ==>  ifThenElse b e1 e2
  We do this /only/ if rebindable syntax is on, because the coverage
  checker looks for HsIf (see GHC.HsToCore.Ticks.addTickHsExpr)
  That means the typechecker and desugarer need to understand HsIf
  for the non-rebindable-syntax case.

* OverLabel (overloaded labels, #lbl)
     #lbl  ==>  fromLabel @"lbl"
  As ever, we use lookupSyntaxName to look up 'fromLabel'
  See Note [Overloaded labels] below

* ExplicitList (explicit lists [a,b,c])
  When (and only when) OverloadedLists is on
     [e1,e2]  ==>  fromListN 2 [e1,e2]
  NB: the type checker and desugarer still see ExplicitList,
      but to them it always means the built-in lists.

* SectionL and SectionR (left and right sections)
     (`op` e) ==> rightSection op e
     (e `op`) ==> leftSection  (op e)
  where `leftSection` and `rightSection` are representation-polymorphic
  wired-in Ids. See Note [Left and right sections]

* To understand why expansions for `OpApp` is done in `GHC.Tc.Gen.Head.splitHsApps`
  see Note [Doing XXExprGhcRn in the Renamer vs Typechecker] below.

* RecordUpd: we desugar record updates into case expressions,
  in GHC.Tc.Gen.Expr.tcExpr.

  Example:

    data T p q = T1 { x :: Int, y :: Bool, z :: Char }
               | T2 { v :: Char }
               | T3 { x :: Int }
               | T4 { p :: Float, y :: Bool, x :: Int }
               | T5

    e { x=e1, y=e2 }
      ===>
    let { x' = e1; y' = e2 } in
    case e of
       T1 _ _ z -> T1 x' y' z
       T4 p _ _ -> T4 p y' x'

  See Note [Record Updates] in GHC.Tc.Gen.Expr for more details.

  To understand Why is this done in the typechecker, and not in the renamer
  see Note [Doing XXExprGhcRn in the Renamer vs Typechecker]

* HsDo: We expand `HsDo` statements in `Ghc.Tc.Gen.Do`.

    - For example, a user written code:

                  do { x <- e1 ; g x ; return (f x) }

      is expanded to:

                   (>>=) e1
                         (\x -> ((>>) (g x)
                                      (return (f x))))

     See Note [Expanding HsDo with XXExprGhcRn] in `Ghc.Tc.Gen.Do` for more details.
     To understand why is this done in the typechecker and not in the renamer.
     See Note [Doing XXExprGhcRn in the Renamer vs Typechecker]

It is not possible, by looking at the free variables of a declaration, to
determine which instances a declaration depends on; furthermore, it is not
possible to discover dependencies between instances, for the same reason.

Previously GHC inserted instances at the earliest positions where their FVs are
bound, but it only helped with a subset of tickets. The current approach is to
accept that the dependency analysis here is incomplete and recover in the kind
checker with a retrying mechanism. See Note [Retrying TyClGroups] in GHC.Tc.TyCl


So much for why we want SCCs.  What about how and when we construct them?

First, an overview:
  (TCDEP1) Flatten TyClGroups from the parser
  (TCDEP2) Rename the type/class declarations, standalone kind signatures, role
           declarations, and instances individually
  (TCDEP3) Preprocess FVs and build a dependency graph
  (TCDEP4) Find strongly connected components (SCCs) of declarations
  (TCDEP5) Attach roles and kind signatures to the appropriate SCC
  (TCDEP6) Create one singleton "SCC" per instance and put them at the end

And now the deep dive:

(TCDEP1) We start with a `HsGroup GhcPs`, containing a `[TyClGroup GhcPs]`:
  a big pile of declarations. It is not important how the parser distributes
  declarations across those TyClGroups, as the first thing we do in `rnTyClDecls`
  is flatten them using a few helpers:

    tyClGroupTyClDecls = Data.List.concatMap group_tyclds
    tyClGroupInstDecls = Data.List.concatMap group_instds
    tyClGroupRoleDecls = Data.List.concatMap group_roles
    tyClGroupKindSigs  = Data.List.concatMap group_kisigs

  In practice, the parser just puts all declarations in a single `TyClGroup`,
  so the `concatMap` is a no-op.

(TCDEP2) Rename each declaration separately, yielding the following lists
  in `rnTyClDecls`:

    tycls_w_fvs  :: [(LTyClDecl GhcRn, FreeVars)]
    instds_w_fvs :: [(LInstDecl GhcRn, FreeVars)]
    kisigs_w_fvs :: [(LStandaloneKindSig GhcRn, FreeVars)]
    role_annots  :: [LRoleAnnotDecl GhcRn]

  The `FreeVars` are the free type/data constructors of the decl. For example:

    type family F (a :: k)        -- FVs: {}
    data X = MkX Char (Maybe X)   -- FVs: {Char, Maybe, X}
    data Y = MkY X (Maybe Y)      -- FVs: {Maybe, Y, X}
    type instance F MkX = X       -- FVs: {F, MkX, X}
    type instance F MkY = Int     -- FVs: {F, MkY, Int}

(TCDEP3) Build a graph where each node is a `TyClDecl` keyed by its name, and
  its `FreeVars` give rise to edges. Happens in `depAnalTyClDecls`. Examples:

    data A x = MkA x       -- node `A`, edges: {}
    data B x = MkB (A x)   -- node `B`, edges: {B -> A}
    data C = MkC (B C)     -- node `C`, edges: {C -> B, C -> C}

  The `FreeVars` are not used "as is" to create the edges. They first undergo a
  few transformations.

  (TCDEP3.fvs_kisig) If a standalone kind signature is present, add its free
    variables to those of the declaration. Consider:

      data A = MkA
      data B = MkB

      type P :: A -> Type           -- sig  FVs: {A, Type}
      data P x = MkP (Proxy MkB)    -- decl FVs: {Proxy, MkB}

    By adding the sig and decl FVs together, we get {A, Type, Proxy, MkB}.
    Then proceed to the next step.

  (TCDEP3.fvs_parent) Replace any mention of a (promoted) data constructor
    with its parent TyCon. Consider the FVs from the previous step:

      the name set {A, Type, Proxy, MkB}
      turns into   {A, Type, Proxy, B}

    MkB does not get its own node in the graph, so an edge to it must actually
    point to B.

  (TCDEP3.fvs_nogbl) Filter out references to type constructors outside this
    `HsGroup`. They just clutter things up:

      the name set {A, Type, Proxy, B}
      turns into   {A, B}

  Note [Prepare TyClGroup FVs] describes these transformations in more detail.
  Back to our `P` example, the final nodes and edges are as follows:

      data A = MkA    -- node `A`, edges: {}
      data B = MkB    -- node `B`, edges: {}

      type P :: A -> Type
      data P x = MkP (Proxy MkB)  -- node `P`, edges: {P -> A, P -> B}

(TCDEP4) Find strongly connected components (SCCs) of `TyClDecl`s.
  This happens immediately after building the dependency graph in
  `depAnalTyClDecls`. As the result, in `rnTyClDecls` we get

    tycl_sccs :: [SCC (LTyClDecl GhcRn, NameSet)]

  These SCCs are topologically sorted, but only according to lexical
  dependencies (i.e. dependencies that can be found by looking at the FVs).
  Non-lexical dependencies (i.e. dependencies on instances) are ignored because
  they can't be reliably found prior to type checking.

  More on that in Note [Retrying TyClGroups] in GHC.Tc.TyCl.

(TCDEP5) For each SCC, create a `TyClGroup GhcRn`. Standalone kind signatures
  and role annotations are looked up by name and included in the same
  `TyClGroup` as the corresponding type/class declarations.

  The extension field `group_ext` of `TyClGroup GhcRn` contains the dependencies
  of the SCC computed from FVs in step (TCDEP3), but /excluding/ the type
  constructors bound by the group itself. Example:

     TyClGroup: binds {Z}
                depends on {}
     data Z = MkZ      -- FVs: {}

     TyClGroup: binds {X, Y}
                depends on {Z} rather than {X, Y, Z}
     data X = MkX Y Z  -- FVs: {Y, Z}
     data Y = MkY X Z  -- FVs: {X, Z}

  Reason: `isReadyTyClGroup` in GHC.Tc.TyCl is a function that checks whether
  all of a TyClGroup's dependencies are present in the type checking env, and we
  wouldn't want it to consider a group to be "blocked" on its own declarations.

(TCDEP6) For each instance, create a singleton `TyClGroup GhcRn`, and put them
  all at the end, where their lexical dependencies are surely satisfied.
  More on that in Note [Put instances at the end].

  The `group_ext` field in an instance TyClGroup is set to the FVs of the
  instance, preprocessed much in the same way as declaration FVs in step
  (TCDEP3). See Note [Prepare TyClGroup FVs] for details.