This is implementated in naming.{h,cc}.
STG does not contain full type names for every type node in the graph. In order to meaningfully describe type changes, STG needs to be able to render C and C++ type names back into source-level syntax.
The STG type Name is the basic entity representing the human-friendly name of a graph node. Values of this type are computed recursively by Describe and are memoised in a NameCache.
Name copes with the inside-out C type syntax in a fairly uniform fashion. There is some slightly special code for Qualifier decoration.
Infinite recursion prevention in Describe is done in the most straightforward fashion possible. One consequence of this is that if there is a naming cycle, the memoised names for nodes in the cycle will depend on where it was entered.
The rest of this document covers the concepts and design principles.
In sensible operator grammars, composition can be done using precedence levels.
Example with binary operators (there are minor adjustments needed if operators have left or right associativity):
| op | precedence |
|---|---|
+ | 0 |
* | 1 |
| num | 2 |
data Expr = Number Int | Times Expr Expr | Plus Expr Expr show_paren p x = if p then "(" ++ x ++ ")" else x shows_prec p (Number n) = show n shows_prec p (Times e1 e2) = show_paren (p > 1) $ shows_prec 2 e1 ++ "*" ++ shows_prec 2 e2 shows_prec p (Plus e1 e2) = show_paren (p > 0) $ shows_prec 1 e1 ++ "+" ++ shows_prec 1 e2
The central idea is that expressions are rendered in the context of a precedence level. Parentheses are needed if the context precedence is higher than the expression's own precedence. Atomic values can be viewed as expressions having maximal precedence. The default precedence context for printing an expression is the minimal one; no parentheses will be emitted.
C's type syntax is closely related to the inside-out declaration syntax it uses and has the same precedence rules. A simplified, partial precedence table for types might look like this.
| thing | precedence |
|---|---|
int | 0 |
refer * | 1 |
elt[N] | 2 |
ret(args) | 2 |
identifier | 3 |
The basic (lowest precedence) elements are:
The “operators” in increasing precedence level order are:
The atomic (highest precedence) elements are:
The qualifiers const, volatile and restrict appear to the right of the pointer-to operator * and are idiomatically placed to the left of the basic elements.[^1] They can be considered as transparent to precedence.
[^1]: They can be idiomatically placed to the right, but that's a different idiom.
Struct, union and enum types can be named or anonymous. The normal case is a named type. Anonymous types are given structural descriptions.
To declare x as a pointer to type t, we declare the dereferencing of x as t.
t * x;
To declare x as an array of type t and size n, we declare the nth element of x as t.
t x[n];
To declare x as a function returning type t and taking args n, we declare the result of applying x to n as t.
t x(n);
The context precedence level for rendering x, which may be a complex thing in its own right, is 2 in the case of arrays and functions and 1 in the case of pointers.
We need to do things inside-out now, because the outer type is a leaf of the type expression tree. Instead we say x has a precedence and the leaf type wraps around it, using parentheses if x's precedence is less than the leaf type (which typically happens if x is a pointer type).
In each of these cases x has been replaced by another type that mentions y.
t * * y; // y is a pointer to pointer to t t * y[m]; // y is an array of pointer to t t * y(m); // y is a function returning pointer to t t (* y)[n]; // y is a pointer to an array of t t y[m][n]; // y is an array of arrays of t t y(m)[n]; // if a function could return an array, this is what it would look like t (* y)(n); // y is a pointer to a function returning t t y[m](n); // if an array could contain functions, this is what it would look like t y(m)(n); // if a function could return a function, this is what it would look like
This builds a type recursively, so that outside bits will be rendered first. The recursion needs to keep track of a left piece, a right piece and the precedence level of the hole in the middle.
data LR = L | R deriving Eq data Type = Basic String | Ptr Type | Function Type [Type] | Array Type Int | Decl String Type render_final expr = ll ++ rr where (ll, _, rr) = render expr render (Basic name) = (name, 0, "") render (Ptr ref) = add L 1 "*" (render ref) render (Function ret args) = add R 2 ("(" ++ intercalate ", " (map final_render args) ++ ")") (render ret) render (Array elt size) = add R 2 ("[" ++ show size ++ "]") (render elt) render (Decl name t) = add L 3 name (render t) add side prec text (l, p, r) = case side of L -> (ll ++ text, prec, rr) R -> (ll, prec, text ++ rr) where paren = prec < p ll = if paren then l ++ "(" else if side == L then l ++ " " else l rr = if paren then ")" ++ r else r
To finally print something, just print the left and right pieces in sequence.
The cunning bit about structuring the pretty printer this way is that render can be memoised. With the expectation that any given type will appear many times in typical output, this is a big win.
NOTE: C type qualifiers are a significant extra complication and are omitted from this sketch. They must appear to the left or right of (the left part of) a type name. Which side can be determined by the current precendence.
NOTE: Whitespace can be emitted sparingly as specific side / precedence contexts can imply the impossibility of inadvertently joining two words.