A TyClGroup represents a strongly connected component of type/class/instance
decls, together with the role annotations and standalone kind signatures for the
type/class declarations. The renamer uses strongly connected component analysis
to build these groups. We do this for a number of reasons:
* Improve kind error messages. Consider
data T f a = MkT f a
data S f a = MkS f (T f a)
This has a kind error, but the error message is better if you
check T first, (fixing its kind) and *then* S. If you do kind
inference together, you might get an error reported in S, which
is jolly confusing. See #4875
* Increase kind polymorphism. See GHC.Tc.TyCl
Note [Grouping of type and class declarations]
What about instances? Based on a number of tickets (#12088, #12239, #14668,
#15561, #16410, #16448, #16693, #19611, #20875, #21172, #22257, #25238, #25834,
etc) we concluded that we cannot handle them at this stage.
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.