1 --------------------------------------------------------------------------------
\r
3 -- "Make everything as simple as possible, but not simpler".
\r
5 -- This library offers a generic way to write AST transforming
\r
6 -- functions. Macros can take bits of AST as parameters and generate a
\r
7 -- more complex AST with them; but modifying an AST a posteriori is
\r
8 -- much more difficult; typical tasks requiring code walking are
\r
9 -- transformation such as lazy evaluation or Continuation Passing
\r
10 -- Style, but more mundane operations are required in more macros than
\r
11 -- one would thing, such as "transform all returns which aren't inside
\r
12 -- a nested function into an error throwing".
\r
14 -- AST walking is an intrinsically advanced operation, and the
\r
15 -- interface of this library, although it tries to remain as simple as
\r
16 -- possible, is not trivial. You'll probably need to write a couple of
\r
17 -- walkers with it before feeling comfortable.
\r
20 -- We deal here with 3 important kinds of AST: statements, expressions
\r
21 -- and blocks. Code walkers for these three kinds for AST are called
\r
22 -- [walk.stat (cfg, ast)], [walk.expr (cfg, ast)] and [walk.block
\r
23 -- (cfg, ast)] respectively. the [cfg] parameter describes what shall
\r
24 -- happen as the AST is traversed by the walker, and [ast] is the tree
\r
27 -- An aparte to fellow functional programmers: although Lua has
\r
28 -- got all the features that constitute a functional language, its
\r
29 -- heart, and in particular it table data, is imperative. It's often
\r
30 -- asking for trouble to work against the host language's nature, so
\r
31 -- code walkers are imperative, cope with it. Or use table.deep_copy()
\r
32 -- if you don't want issues with shared state.
\r
34 -- Since walkers are imperative (i.e. they transform the tree in
\r
35 -- place, rather than returning a fresh variant of it), you'll often
\r
36 -- want to override a node, i.e. keep its "pointer identity", but
\r
37 -- replace its content with a new one; this is done by
\r
38 -- table.override(), and is conveniently abbreviated as
\r
39 -- "target <- new_content".
\r
41 -- So, [cfg] can contain a series of sub-tables fields 'expr', 'stat',
\r
42 -- 'block'. each of them can contain a function up() and/or a function
\r
45 -- * down() is called when the walker starts visiting a node of the
\r
46 -- matching kind, i.e. before any of its sub-nodes have been
\r
47 -- visited. down() is allowed to return either the string "break",
\r
48 -- which means "don't go further down this tree, don't try to walk
\r
49 -- its children", or nil, i.e. "please process with the children
\r
52 -- There are two reasons why you might want down() to return
\r
53 -- "break": either because you really weren't interested into the
\r
54 -- children nodes,or because you wanted to walk through them in a
\r
55 -- special way, and down() already performed this special walking.
\r
57 -- * up() is called just before the node is left, i.e. after all of
\r
58 -- its children nodes have been completely parsed, down and up. This
\r
59 -- is a good place to put treatments which rely on sub-nodes being
\r
60 -- already treated. Notice that if down() returned 'break', up() is
\r
61 -- run immediately after.
\r
63 -- In previous versions of this library, there were plenty of fancy
\r
64 -- configurable ways to decide whether an up() or down() functions
\r
65 -- would be triggered or not. Experience suggested that the best way
\r
66 -- is to keep it simpler, as done by the current design: the functions
\r
67 -- in sub-table expr are run on each expression node, and ditto for
\r
68 -- stat and block; the user is expected to use the pattern matching
\r
69 -- extension to decide whether to act or not on a given node.
\r
71 -- Advanced features
\r
72 -- =================
\r
74 -- The version above is a strict subset of the truth: there are a
\r
75 -- couple of other, more advanced features in the library.
\r
77 -- Paths in visitor functions
\r
78 -- --------------------------
\r
79 -- First, up() and down() don't take only one node as a parameter, but
\r
80 -- a series thereof: all the nested expr/stat/block nodes on the way
\r
81 -- up to the ast's root. For instance, when a walker works on
\r
82 -- +{ foo(bar*2+1) } an is on the node +{2}, up() and down() are called
\r
83 -- with arguments (+{bar*2}, +{bar*2+1}, +{foo(bar*2+1)}).
\r
85 -- `Call and `Invoke as statements
\r
86 -- -------------------------------
\r
87 -- `Call and `Invoke are normally expressions, but they can also
\r
88 -- appear as statements. In this case, the cfg.expr.xxx() visitors
\r
89 -- aren't called on them. Sometimes you want to consider tham as
\r
90 -- expressions, sometimes not, and it's much easier to add a special
\r
91 -- case in cfg.stat.xxx() visitors than to determine whether we're in
\r
92 -- a statament's context in cfg.expr.xxx(),
\r
96 -- There are some second class walkers: walk.expr_list() and walk.guess().
\r
98 -- * The first one walks through a list of expressions. Although used
\r
99 -- internally by the other walkers, it remains a second class
\r
100 -- citizen: the list it works on won't appear in the path of nested
\r
101 -- ASTs that's passed to up() and down(). This design choice has
\r
102 -- been made because there's no clear definition of what is or isn't
\r
103 -- an expr list in an AST, and anyway such lists are probably not
\r
104 -- part of metacoders' mental image of an AST, so it's been thought
\r
105 -- best to let people pretend they don't exist.
\r
107 -- * walk.guess() tries to guess the type of the AST it receives,
\r
108 -- according to its tag, and runs the appropriate walker. Node which
\r
109 -- can be both stats and exprs (`Call and `Invoke) are considered as
\r
112 -- These three walkers, although used internally by the other walkers,
\r
113 -- remain second class citizens: the lists they work on won't appear
\r
114 -- in the path of nested ASTs that's passed to up() and down().
\r
116 -- Tag dictionaries
\r
117 -- ----------------
\r
118 -- There are two public dictionaries, walk.tags.stat and
\r
119 -- walk.tags.expr, which keep the set of all tags that can start a
\r
120 -- statement or an expression AST. They're used by walk.guess, and
\r
121 -- users sometimes need them as well, so they've been kept available.
\r
125 -- Finally, there's one last field in [cfg]: binder(). This function
\r
126 -- is called on identifiers in a binder position, i.e. `Id{ } nodes
\r
127 -- which create a scoped local variable, in `Function, `Fornum, `Local
\r
128 -- etc. The main use case for that function is to keep track of
\r
129 -- variables, captures, etc. and perform alpha conversions. In many
\r
130 -- cases that work is best done through the library 'walk.id', which
\r
131 -- understands the notions of scope, free variable, bound variable
\r
134 -- Binder visitors are called just before the variable's scope starts,
\r
135 -- e.g. they're called after the right-hand-side has been visited in a
\r
136 -- `Local node, but before in a `Localrec node.
\r
138 --------------------------------------------------------------------------------
\r
140 -{ extension "match" }
\r
142 walk = { traverse = { }; tags = { }; debug = false }
\r
144 --------------------------------------------------------------------------------
\r
145 -- Standard tags: can be used to guess the type of an AST, or to check
\r
146 -- that the type of an AST is respected.
\r
147 --------------------------------------------------------------------------------
\r
148 walk.tags.stat = table.transpose{
\r
149 'Do', 'Set', 'While', 'Repeat', 'Local', 'Localrec', 'Return',
\r
150 'Fornum', 'Forin', 'If', 'Break', 'Goto', 'Label',
\r
152 walk.tags.expr = table.transpose{
\r
153 'Paren', 'Call', 'Invoke', 'Index', 'Op', 'Function', 'Stat',
\r
154 'Table', 'Nil', 'Dots', 'True', 'False', 'Number', 'String', 'Id' }
\r
156 --------------------------------------------------------------------------------
\r
157 -- These [walk.traverse.xxx()] functions are in charge of actually going through
\r
158 -- ASTs. At each node, they make sure to call the appropriate walker.
\r
159 --------------------------------------------------------------------------------
\r
160 function walk.traverse.stat (cfg, x, ...)
\r
161 if walk.debug then printf("traverse stat %s", table.tostring(x)) end
\r
163 local B = |y| walk.block (cfg, y, x, unpack(log))
\r
164 local S = |y| walk.stat (cfg, y, x, unpack(log))
\r
165 local E = |y| walk.expr (cfg, y, x, unpack(log))
\r
166 local EL = |y| walk.expr_list (cfg, y, x, unpack(log))
\r
167 local I = |y| walk.binder_list (cfg, y, x, unpack(log))
\r
169 | {...} if x.tag == nil -> for y in ivalues(x) do walk.stat(cfg, y, ...) end
\r
170 -- no tag --> node not inserted in the history log
\r
172 | `Set{ lhs, rhs } -> EL(lhs); EL(rhs)
\r
173 | `While{ cond, body } -> E(cond); B(body)
\r
174 | `Repeat{ body, cond } -> B(body); E(cond)
\r
175 | `Local{ lhs } -> I(lhs)
\r
176 | `Local{ lhs, rhs } -> EL(rhs); I(lhs)
\r
177 | `Localrec{ lhs, rhs } -> I(lhs); EL(rhs)
\r
178 | `Fornum{ i, a, b, body } -> E(a); E(b); I{i}; B(body)
\r
179 | `Fornum{ i, a, b, c, body } -> E(a); E(b); E(c); I{i}; B(body)
\r
180 | `Forin{ i, rhs, body } -> EL(rhs); I(i); B(body)
\r
181 | `If{...} -> for i=1, #x-1, 2 do E(x[i]); B(x[i+1]) end
\r
182 if #x%2 == 1 then B(x[#x]) end
\r
183 | `Call{...}|`Invoke{...}|`Return{...} -> EL(x)
\r
184 | `Break | `Goto{ _ } | `Label{ _ } -> -- nothing
\r
185 | {...} if walk.tags.stat[x.tag]->
\r
186 printf("Warning: walk: malformed %s stat node: %s", x.tag, table.tostring(x,80))
\r
187 | {...} -> print("Warning: walk: unknown stat node: "..table.tostring(x,80))
\r
188 | _ -> print("Warning: walk: unexpected stat node of type "..type(x)
\r
189 ..": "..table.tostring(x,80))
\r
193 function walk.traverse.expr (cfg, x, ...)
\r
194 if walk.debug then printf("traverse expr %s", table.tostring(x)) end
\r
196 local B = |y| walk.block (cfg, y, x, unpack(log))
\r
197 local S = |y| walk.stat (cfg, y, x, unpack(log))
\r
198 local E = |y| walk.expr (cfg, y, x, unpack(log))
\r
199 local EL = |y| walk.expr_list (cfg, y, x, unpack(log))
\r
200 local I = |y| walk.binder_list (cfg, y, x, unpack(log))
\r
202 | `Paren{ e } -> E(e)
\r
203 | `Call{...} | `Invoke{...} -> EL(x)
\r
204 | `Index{ a, b } -> E(a); E(b)
\r
205 | `Op{ opid, ... } -> E(x[2]); if #x==3 then E(x[3]) end
\r
206 | `Function{ params, body } -> I(params); B(body)
\r
207 | `Stat{ b, e } -> B(b); E(e)
\r
209 for i = 1, #x do match x[i] with
\r
210 | `Pair{ k, v } -> E(k); E(v)
\r
213 |`Nil|`Dots|`True|`False|`Number{_}|`String{_}|`Id{_} -> -- nothing
\r
214 | {...} if walk.tags.expr[x.tag]->
\r
215 printf("Warning: walk: malformed %s expr node: %s", x.tag, table.tostring(x,80))
\r
216 | {...} -> print("Warning: walk: unknown expr node: "..table.tostring(x,80))
\r
217 | _ -> print("Warning: walk: unexpected expr node of type "..type(x)
\r
218 ..": "..table.tostring(x,80))
\r
222 function walk.traverse.block (cfg, x, ...)
\r
223 assert(type(x)=='table', "traverse.block() expects a table")
\r
224 for y in ivalues(x) do walk.stat(cfg, y, x, ...) end
\r
227 function walk.traverse.expr_list (cfg, x, ...)
\r
228 assert(type(x)=='table', "traverse.expr_list() expects a table")
\r
229 -- x doesn't appear in the log
\r
230 for y in ivalues(x) do walk.expr(cfg, y, ...) end
\r
233 ----------------------------------------------------------------------
\r
234 -- Generic walker generator.
\r
235 ----------------------------------------------------------------------
\r
236 local walker_builder = |cfg_field, traverse| function (cfg, x, ...)
\r
237 local sub_cfg = cfg[cfg_field] or { }
\r
238 local broken = false
\r
239 if sub_cfg.down then
\r
240 if sub_cfg.down=='break' then broken='break'
\r
241 else broken = sub_cfg.down (x, ...) end
\r
242 assert(not broken or broken=='break',
\r
243 "Map functions must return 'break' or nil")
\r
245 if not broken then traverse (cfg, x, ...) end
\r
246 if sub_cfg.up then sub_cfg.up (x, ...) end
\r
249 ----------------------------------------------------------------------
\r
250 -- Declare [walk.stat], [walk.expr], [walk.block] and [walk.expr_list]
\r
251 ----------------------------------------------------------------------
\r
252 for w in values{ "stat", "expr", "block", "expr_list" } do
\r
253 walk[w] = walker_builder (w, walk.traverse[w])
\r
256 ----------------------------------------------------------------------
\r
257 -- Walk a list of `Id{...} (mainly a helper function actually).
\r
258 ----------------------------------------------------------------------
\r
259 function walk.binder_list (cfg, x, ...)
\r
260 local f = cfg.binder
\r
261 if f then for v in ivalues(x) do f(v, ...) end end
\r
264 ----------------------------------------------------------------------
\r
265 -- Tries to guess the type of the AST then choose the right walkker.
\r
266 ----------------------------------------------------------------------
\r
267 function walk.guess (cfg, x, ...)
\r
268 assert(type(x)=='table', "arg #2 in a walker must be an AST")
\r
269 if walk.tags.expr[x.tag] then return walk.expr(cfg, x, ...) end
\r
270 if walk.tags.stat[x.tag] then return walk.stat(cfg, x, ...) end
\r
271 if not x.tag then return walk.block(cfg, x, ...) end
\r
272 error ("Can't guess the AST type from tag "..(x.tag or '<none>'))
\r