TTG: Resolving even more TTG-related orphan type-class instances
TTG: Resolving orphan type-class instances after AST separation
Introduction
The Trees that Grow (TTG) migration relocated the Haskell abstract syntax tree (AST) into the
Language.Haskell.Syntax (L.H.S) namespace and left GHC's instantiation of it in the
GHC namespace. While the data types moved, their instances largely did not. The
result is a population of orphan type-class instances, declared in modules that define neither the class nor the type. These modules contain a -Wno-orphans pragma which hides/suppresses technical debt.
Now that the two namespaces have been partitioned, it is possible to resolve many of the orphan type-class instances that remain as either an artifact or temporary kludge of the TTG project. This merge request retires the movable portion of that debt. It changes no AST semantics: every migrated body preserves its original encoding, pretty-printed output and ordering behavior.
Addresses issue #27755
Scope of Work
Orphan counts are measured on master from .hie interface files for modules with a -Wno-orphans pragma. Prior to this MR, master carries 663 orphan class instances across 53 suppressing modules:
Universe of Orphan Instances
| Type-class | On master |
Within TTG-decoupled modules |
|---|---|---|
Binary |
37 | 16 |
BooleanFormulaDefault |
1 | 1 |
Data |
425 | 9 |
Diagnostic |
6 | 0 |
Eq |
35 | 24 |
Fractional |
1 | 0 |
HasDefaultDiagnosticOpts |
4 | 0 |
HasLoc |
5 | 5 |
HasOccName |
1 | 1 |
Instruction |
5 | 0 |
MonadUnique |
1 | 0 |
NFData |
1 | 1 |
Num |
1 | 0 |
Ord |
6 | 6 |
Outputable |
120 | 98 |
OutputableBndr |
9 | 6 |
Show |
4 | 4 |
WrapXRec |
1 | 1 |
| Total | 663 | 172 |
Several categories of orphan type-class instances are set aside before any migration is considered:
-
66 orphan instances are unrelated to the TTG changes, predating the AST separation:
Click to expand table of unrelated orphan type-class instances by module
Module Quantity GHC.StgToJS.Object21 GHC.Core.Ppr12 GHC.Driver.Errors.Ppr4 GHC.Tc.Errors.Ppr4 GHC.Core.Map.Expr2 GHC.Core.Ppr—.hs-boot2 GHC.Hs.Expr—.hs-boot2 GHC.Iface.Errors.Ppr2 GHC.JS.Make2 GHC.JS.Ppr2 GHC.CmmToAsm.AArch641 GHC.CmmToAsm.AArch64.Instr1 GHC.CmmToAsm.LA641 GHC.CmmToAsm.LA64.Instr1 GHC.CmmToAsm.PPC1 GHC.CmmToAsm.RV641 GHC.CmmToAsm.RV64.Instr1 GHC.CmmToAsm.X861 GHC.Hs.Pat—.hs-boot1 GHC.HsToCore.Errors.Ppr1 GHC.Parser.Errors.Ppr1 GHC.Tc.Utils.Monad1 GHC.Types.Hint.Ppr1 Total 66 -
425 orphan
Datainstances are intentionally inGHC.Hs.Instances; this module collects these instances to control compile times. A further 9Dataorphans sit inside the TTG-decoupled modules and are set aside on the same grounds. -
30 orphan
EqandOrdinstances have their class inbase, so the only available “non-orphan home” for the instance is the data-type's module. MovingEqandOrddefinitions fromGHC.*toL.H.Swill invariable introduce subtle, semantic changes for the TTG extension points.
This leaves 9 type-classes totaling 133 instances “in scope” as technical debt from the TTG project.
Candidate Orphan Instances
| Type-class | On master |
|---|---|
Binary |
16 |
BooleanFormulaDefault |
1 |
HasLoc |
5 |
HasOccName |
1 |
NFData |
1 |
Outputable |
98 |
OutputableBndr |
6 |
Show |
4 |
WrapXRec |
1 |
| Total | 133 |
Methodology
Seven techniques were applied. The first is the default. the remainder exist because a verbatim migration fails.
-
Migration to type-class module verbatim. Move the instance directly into the module declaring the class. Applies where the body is already independent of the pass index.
-
Migration to data-type module. Where the class is in
baseordeepseq, or its module is cyclically unreachable from the class module, the data-type's module inL.H.Sis the only admissible home. -
Constraint generalization over the pass. Restate the instance at an arbitrary index
pand replace eachGhcPasstype-family equation the body relied on with a constraint. Two forms recur: anXXFoo p ~equality againstDataConCantHappen, required for the pattern-match coverage checker to prove the extension constructor unreachable, andUnXRec pin place of a directunLoc. This is what allows a printer or serializer to live in the class module without that module gaining any knowledge ofGhcPass. -
Dispatch elimination. A
case ghcPass @p of …whose branches are identical, or which exists only so that GHC can reduce a family and find an instance, is a symptom of a missing payload instance rather than a genuine obstacle. Replacing it with a constraint on the payload — and declaring the payload's instance in the payload's own module, where it is a non-orphan — removes theIsPassrequirement instead of satisfying it. -
Dependency inversion. Where a module's only obstacle is that it imports the class module, invert the edge: move its instances out to the class module and reduce it to a leaf. Applied to
GHC.Types.SourceTextandGHC.Utils.Lexeme. -
Shared-accessor lifting. Where two candidate homes each need the same pure accessor, define it once in
L.H.Sand have both use it.ieWrappedLIdPand theHsDocStringrender chain are the two cases. -
Referential-transparency expansion. In order to relocate
pprPrefixFastStringtoGHC.Utils.Outputable, the helper's definition was expanded by substitution, reduced the closed sub-expressions, and repeated until the residual expression contains only symbolsGHC.Utils.Outputablecan import. Eleven substitution steps reducepprPrefixOcc . mkVarUnqualto a form whose only external needs areisLexConSym/isLexVarSym.Click to expand referential transparency proof
{- pprPrefixFastString = pprPrefixOcc . mkVarUnqual = pprPrefixOcc . (\n -> Unqual (mkVarOccFS n)) = pprPrefixOcc . Unqual . mkVarOccFS = pprPrefixOcc . Unqual . (\fs -> mkOccNameFS VarName fs) = pprPrefixOcc . Unqual . mkOccNameFS VarName = pprPrefixOcc . Unqual . ((\occ_sp fs -> OccName occ_sp fs) VarName) = pprPrefixOcc . Unqual . OccName VarName = \fs -> pprPrefixOcc (Unqual (OccName (VarName fs))) = \fs -> (\rdr -> pprPrefixVar (isSymOcc (rdrNameOcc rdr)) (ppr rdr)) (Unqual (OccName VarName fs)) = \fs -> pprPrefixVar (isSymOcc (rdrNameOcc (Unqual (OccName VarName fs))) (ppr (Unqual (OccName VarName fs)))) = \fs -> pprPrefixVar (isSymOcc ((OccName VarName fs)) (ppr (Unqual (OccName VarName fs)))) = \fs -> pprPrefixVar (\(OccName VarName fs) -> isLexSym fs) (ppr (Unqual (OccName VarName fs)))) = \fs -> pprPrefixVar (isLexSym fs) (ppr (Unqual (OccName VarName fs)))) = \fs -> pprPrefixVar (isLexConSym fs || isLexVarSym fs) (ppr (Unqual (OccName VarName fs)))) = \fs -> pprPrefixVar (isLexConSym fs || isLexVarSym fs) (\(Unqual (OccName VarName fs)) -> ppr (OccName VarName fs)) = \fs -> pprPrefixVar (isLexConSym fs || isLexVarSym fs) (ppr (OccName VarName fs)) = \fs -> pprPrefixVar (isLexConSym fs || isLexVarSym fs) (pprOccName (OccName VarName fs)) = \fs -> pprPrefixVar (isLexConSym fs || isLexVarSym fs) (docWithStyle (ztext (zEncodeFS fs)) (\_ -> ftext fs <> whenPprDebug (braces (pprNameSpaceBrief VarName)))) = \fs -> pprPrefixVar (isLexConSym fs || isLexVarSym fs) (docWithStyle (ztext (zEncodeFS fs)) (\_ -> ftext fs <> whenPprDebug (braces (char 'v')))) -} pprPrefixFastString :: FastString -> SDoc pprPrefixFastString = \fs -> pprPrefixVar (Lex.isLexConSym fs || Lex.isLexVarSym fs) (docWithStyle (ztext (zEncodeFS fs)) (\_ -> ftext fs <> whenPprDebug (braces (char 'v'))))
Architectural Changes
A new module, GHC.Hs.Extension.Instances, now holds the GhcPass
instantiation of the TTG extension points that were previously
declared in GHC.Hs.Extension.Pass — the XRec/Anno equations, the
HsDocString extension points, and the UnXRec/MapXRec
instances.
The effect is to concentrate the orphans that necessarily accompany those
equations into one module in order to avoid module import cycles. Now GHC.Hs.Extension.Pass can be imported by other modules without transitively depending on modules required for the instances. GHC.Hs.Extension.Pass also gains the IsPass class and
the NoGhcTcPass family, moved down from GHC.Hs.Extension with no new imports,
on the grounds that both are about GhcPass.
Conclusion
82 of the 133 in-scope orphan class instances are resolved!
Results
| Type-class | Before | After |
|---|---|---|
Binary |
16 | 1 |
BooleanFormulaDefault † |
1 | 1 |
HasLoc |
5 | 1 |
HasOccName |
1 | 0 |
NFData |
1 | 0 |
Outputable |
98 | 47 |
OutputableBndr |
6 | 0 |
Show |
4 | 0 |
WrapXRec † |
1 | 1 |
| Total | 133 | 51 |
† See the Other migrations section below.
This constitutes a 61.7% reduction in TTG-related orphan type-class instances (82 of 133). The two daggered rows are migrated but not un-orphaned, so they count against the total rather than towards it.
Resolved Orphan Instances
The table below aggregates all 82 resolved orphan type-class instances.
Click to expand table of resolved orphan type-class instances (all instances)
Remaining Orphan Instances
The 51 in-scope instances below remain. They are not arbitrary residue: each was searched individually against both admissible homes, including by the substitution procedure of technique (8), and each is blocked by one of the causes below.
-
A — AST printer layer. The body delegates to pretty-printing logic in
GHC.Hs.*(pprExpr,pprPat,ppr_sig,ppr_monobind,pprConDecland similar) and also the instance is constrained byOutputableBndrId. SinceOutputableBndrIdis a constraint synonym involvingIdGhcPwhichGHC.Utils.Outputablecannot import. Without moving the vast amount of the printer definitions intoGHC.Utils.Outputable(or an importable) module, or further reorganizing module structure so thatOutputableBndrIdcan be imported byGHC.Utils.Outputable, these orphan instances cannot be resolved. An attempt at resolving these instances is far beyond the request of this MR. -
B — GHC-side payload or annotation. The instance requires a concrete type from
GHC.Parser.Annotation,GHC.Types.SrcLoc, or a GHC-specific extension payload; none of which the type-class module can import. -
† — Relocated, not resolved. No module both declares a name in the instance head and can express the body, so the instance was moved to the most defensible home available instead. See the Other migrations section below.
Click to expand table of remaining in-scope orphan type-class instances
Of the unresolved type-class instances, 40 / 51 of them are blocked by Cause A. If these are to be resolved, they should be addressed in a separate MR, though at this time I cannot present what the best best way to resolve this blocker would be, nor can I provided a sketch of what such an MR would look like. The 9 / 51 orphans blocked by Cause B will likely each need a bespoke solution if resolving those orphan instances is pursued.
Other migrations
-
The
WrapXRec (GhcPass p)orphan instance has been moved fromGHC.Hs.ExprtoGHC.Hs.Extension. While this is still an orphan instance, it is closer to the “logical” definition of theGhcPassdata-type, and if theGHC.Hs.Extensionis thought of as the “user facing API” then the instance is no longer orphaned under that viewpoint. -
The
BooleanFormulaDefault (GhcPass p)orphan instance has been moved fromGHC.Data.BooleanFormulatoGHC.Hs.Extension.Instances. As withWrapXRec (GhcPass p)above, this does not remove the orphan instance, but it does place the instance beside the otherGhcPassinstantiations of TTG extension points, next to theXRec/Annoequations and theUnXRec/MapXRecinstances, in the module whose-Wno-orphanspragma exists precisely to cover them. The same "user-facing API" viewpoint postulated forWrapXRec (GhcPass p)applied here.
A.I. Usage disclosure
An LLM was used to ensure consistent Markdown formatting, collate type-class instance tables, and add Haddock hyperlinks throughout the description of this MR. I have carefully reviewed and revised the submitted material and take responsibility for it.