| ... |
... |
@@ -13,6 +13,67 @@ information directly into every AST node to allow the tree to be reprinted _exac |
|
13
|
13
|
original source, byte-for-byte (modulo tab expansion). When a tool modifies the AST it adjusts
|
|
14
|
14
|
only the annotations it needs to change; all surrounding nodes reprint themselves unchanged.
|
|
15
|
15
|
|
|
|
16
|
+## Background: the syntax tree
|
|
|
17
|
+
|
|
|
18
|
+The AST of the source program is represented using the data types defined in `Language.Haskell.Syntax.*`.
|
|
|
19
|
+This data type uses the "Trees That Grow (TTG)" plan;
|
|
|
20
|
+see [Implementing trees that grow](https://gitlab.haskell.org/ghc/ghc/-/wikis/implementing-trees-that-grow)
|
|
|
21
|
+
|
|
|
22
|
+For example, in (GHC-independent) `Language.Haskell.Syntax.Expr`:
|
|
|
23
|
+```
|
|
|
24
|
+data HsExpr p
|
|
|
25
|
+ = ... many constructors including ...
|
|
|
26
|
+ | HsLet (XLet p)
|
|
|
27
|
+ (HsLocalBinds p)
|
|
|
28
|
+ (LHsExpr p)
|
|
|
29
|
+
|
|
|
30
|
+type family XLet p
|
|
|
31
|
+type LHsExpr p = XRec p (HsExpr p)
|
|
|
32
|
+
|
|
|
33
|
+```
|
|
|
34
|
+Note that
|
|
|
35
|
+* The `(XLet p)` field is the *extension field* of the `HsLet` data constructor,
|
|
|
36
|
+ where `XLet` is a type family.
|
|
|
37
|
+* Almost every node is wrapped in an `XRec`, another type family. That makes it easy
|
|
|
38
|
+ for clients to attach arbitrary information to each node.
|
|
|
39
|
+
|
|
|
40
|
+GHC specialises this data a type in `GHC.Hs.*`, as follows:
|
|
|
41
|
+```
|
|
|
42
|
+data Pass = Parsed | Renamed | Typechecked
|
|
|
43
|
+
|
|
|
44
|
+data GhcPass (c :: Pass) where
|
|
|
45
|
+ GhcPs :: GhcPass 'Parsed
|
|
|
46
|
+ GhcRn :: GhcPass 'Renamed
|
|
|
47
|
+ GhcTc :: GhcPass 'Typechecked
|
|
|
48
|
+
|
|
|
49
|
+type family XRec p a = r | r -> a
|
|
|
50
|
+type instance XRec (GhcPass p) t = XRecGhc t
|
|
|
51
|
+
|
|
|
52
|
+-- (XRecGhc tree) wraps `tree` in a GHC-specific,
|
|
|
53
|
+-- but pass-independent, source location
|
|
|
54
|
+type XRecGhc t = GenLocated (Anno t) t
|
|
|
55
|
+
|
|
|
56
|
+data GenLocated l e = L l e
|
|
|
57
|
+type family Anno t
|
|
|
58
|
+```
|
|
|
59
|
+So, via `XRec`, every node `e :: t` in the GHC-specific version of HsSyn is wrapped in
|
|
|
60
|
+a `L ann e`, where `ann :: Anno t` is the annotation on the node.
|
|
|
61
|
+
|
|
|
62
|
+Notice that there are two places we can hang information:
|
|
|
63
|
+* (EXT) **Constructor-specific punctuation**: the extension field of each data constructor
|
|
|
64
|
+ can contain information that is specific to that constructor. Example: the location
|
|
|
65
|
+ of the keywords `let` and `in` for the `HsLet` construct.
|
|
|
66
|
+
|
|
|
67
|
+* (XREC) **Entire-node information**: the `Anno t` field that wraps almost every node in the
|
|
|
68
|
+ syntax tree can contain information that is needed for *every* node. Classic example:
|
|
|
69
|
+ the `SrcSpan` of the node.
|
|
|
70
|
+
|
|
|
71
|
+**NOTE**: currently there is information in (XREC) that more properly belongs in (EXT).
|
|
|
72
|
+A refactoring project is under way to put this right.
|
|
|
73
|
+
|
|
|
74
|
+
|
|
|
75
|
+## File layout
|
|
|
76
|
+
|
|
16
|
77
|
The subsystem lives primarily in `utils/check-exact/` and is exposed through three main layers:
|
|
17
|
78
|
|
|
18
|
79
|
| Layer | Key operation | Purpose |
|