| ------------------------------------------------------------------------------- |
| -- Copyright (c) 2006-2013 Fabien Fleutot and others. |
| -- |
| -- All rights reserved. |
| -- |
| -- This program and the accompanying materials are made available |
| -- under the terms of the Eclipse Public License v1.0 which |
| -- accompanies this distribution, and is available at |
| -- http://www.eclipse.org/legal/epl-v10.html |
| -- |
| -- This program and the accompanying materials are also made available |
| -- under the terms of the MIT public license which accompanies this |
| -- distribution, and is available at http://www.lua.org/license.html |
| -- |
| -- Contributors: |
| -- Fabien Fleutot - API and implementation |
| -- |
| ------------------------------------------------------------------------------- |
| |
| -- Low level AST traversal library. |
| -- |
| -- This library is a helper for the higher-level `treequery` library. |
| -- It walks through every node of an AST, depth-first, and executes |
| -- some callbacks contained in its `cfg` config table: |
| -- |
| -- * `cfg.down(...)` is called when it walks down a node, and receive as |
| -- parameters the node just entered, followed by its parent, grand-parent |
| -- etc. until the root node. |
| -- |
| -- * `cfg.up(...)` is called when it walks back up a node, and receive as |
| -- parameters the node just entered, followed by its parent, grand-parent |
| -- etc. until the root node. |
| -- |
| -- * `cfg.occurrence(binder, id_node, ...)` is called when it visits |
| -- an `` `Id{ }`` node which isn't a local variable creator. binder |
| -- is a reference to its binder with its context. The binder is the |
| -- `` `Id{ }`` node which created this local variable. By "binder |
| -- and its context", we mean a list starting with the `` `Id{ }``, |
| -- and followed by every ancestor of the binder node, up until the |
| -- common root node. `binder` is nil if the variable is global. |
| -- `id_node` is followed by its ancestor, up until the root node. |
| -- |
| -- `cfg.scope` is maintained during the traversal, associating a |
| -- variable name to the binder which creates it in the context of the |
| -- node currently visited. |
| -- |
| -- `walk.traverse.xxx` functions are in charge of the recursive |
| -- descent into children nodes. They're private helpers. They are also |
| -- in charge of calling appropriate `cfg.xxx` callbacks. |
| |
| -{ extension ("match", ...) } |
| |
| local pp = require 'metalua.pprint' |
| |
| local M = { traverse = { }; tags = { }; debug = false } |
| |
| local function table_transpose(t) |
| local tt = { }; for a, b in pairs(t) do tt[b]=a end; return tt |
| end |
| |
| -------------------------------------------------------------------------------- |
| -- Standard tags: can be used to guess the type of an AST, or to check |
| -- that the type of an AST is respected. |
| -------------------------------------------------------------------------------- |
| M.tags.stat = table_transpose{ |
| 'Do', 'Set', 'While', 'Repeat', 'Local', 'Localrec', 'Return', |
| 'Fornum', 'Forin', 'If', 'Break', 'Goto', 'Label', |
| 'Call', 'Invoke' } |
| M.tags.expr = table_transpose{ |
| 'Paren', 'Call', 'Invoke', 'Index', 'Op', 'Function', 'Stat', |
| 'Table', 'Nil', 'Dots', 'True', 'False', 'Number', 'String', 'Id' } |
| |
| -------------------------------------------------------------------------------- |
| -- These [M.traverse.xxx()] functions are in charge of actually going through |
| -- ASTs. At each node, they make sure to call the appropriate walker. |
| -------------------------------------------------------------------------------- |
| |
| function M.traverse.stat (cfg, x, ...) |
| if M.debug then pp.printf("traverse stat %s", x) end |
| local ancestors = {...} |
| local B = |y| M.block (cfg, y, x, unpack(ancestors)) -- Block |
| local S = |y| M.stat (cfg, y, x, unpack(ancestors)) -- Statement |
| local E = |y| M.expr (cfg, y, x, unpack(ancestors)) -- Expression |
| local EL = |y| M.expr_list (cfg, y, x, unpack(ancestors)) -- Expression List |
| local IL = |y| M.binder_list (cfg, y, x, unpack(ancestors)) -- Id binders List |
| local OS = || cfg.scope :save() -- Open scope |
| local CS = || cfg.scope :restore() -- Close scope |
| |
| match x with |
| | {...} if x.tag == nil -> for _, y in ipairs(x) do M.stat(cfg, y, ...) end |
| -- no tag --> node not inserted in the history ancestors |
| | `Do{...} -> OS(x); for _, y in ipairs(x) do S(y) end; CS(x) |
| | `Set{ lhs, rhs } -> EL(lhs); EL(rhs) |
| | `While{ cond, body } -> E(cond); OS(); B(body); CS() |
| | `Repeat{ body, cond } -> OS(body); B(body); E(cond); CS(body) |
| | `Local{ lhs } -> IL(lhs) |
| | `Local{ lhs, rhs } -> EL(rhs); IL(lhs) |
| | `Localrec{ lhs, rhs } -> IL(lhs); EL(rhs) |
| | `Fornum{ i, a, b, body } -> E(a); E(b); OS(); IL{i}; B(body); CS() |
| | `Fornum{ i, a, b, c, body } -> E(a); E(b); E(c); OS(); IL{i}; B(body); CS() |
| | `Forin{ i, rhs, body } -> EL(rhs); OS(); IL(i); B(body); CS() |
| | `If{...} -> |
| for i=1, #x-1, 2 do |
| E(x[i]); OS(); B(x[i+1]); CS() |
| end |
| if #x%2 == 1 then |
| OS(); B(x[#x]); CS() |
| end |
| | `Call{...}|`Invoke{...}|`Return{...} -> EL(x) |
| | `Break | `Goto{ _ } | `Label{ _ } -> -- nothing |
| | { tag=tag, ...} if M.tags.stat[tag]-> |
| M.malformed (cfg, x, unpack (ancestors)) |
| | _ -> |
| M.unknown (cfg, x, unpack (ancestors)) |
| end |
| end |
| |
| function M.traverse.expr (cfg, x, ...) |
| if M.debug then pp.printf("traverse expr %s", x) end |
| local ancestors = {...} |
| local B = |y| M.block (cfg, y, x, unpack(ancestors)) -- Block |
| local S = |y| M.stat (cfg, y, x, unpack(ancestors)) -- Statement |
| local E = |y| M.expr (cfg, y, x, unpack(ancestors)) -- Expression |
| local EL = |y| M.expr_list (cfg, y, x, unpack(ancestors)) -- Expression List |
| local IL = |y| M.binder_list (cfg, y, x, unpack(ancestors)) -- Id binders list |
| local OS = || cfg.scope :save() -- Open scope |
| local CS = || cfg.scope :restore() -- Close scope |
| |
| match x with |
| | `Paren{ e } -> E(e) |
| | `Call{...} | `Invoke{...} -> EL(x) |
| | `Index{ a, b } -> E(a); E(b) |
| | `Op{ opid, ... } -> E(x[2]); if #x==3 then E(x[3]) end |
| | `Function{ params, body } -> OS(body); IL(params); B(body); CS(body) |
| | `Stat{ b, e } -> OS(b); B(b); E(e); CS(b) |
| | `Id{ name } -> M.occurrence(cfg, x, unpack(ancestors)) |
| | `Table{ ... } -> |
| for i = 1, #x do match x[i] with |
| | `Pair{ k, v } -> E(k); E(v) |
| | v -> E(v) |
| end end |
| | `Nil|`Dots|`True|`False|`Number{_}|`String{_} -> -- terminal node |
| | { tag=tag, ...} if M.tags.expr[tag]-> M.malformed (cfg, x, unpack (ancestors)) |
| | _ -> M.unknown (cfg, x, unpack (ancestors)) |
| end |
| end |
| |
| function M.traverse.block (cfg, x, ...) |
| assert(type(x)=='table', "traverse.block() expects a table") |
| if x.tag then M.malformed(cfg, x, ...) |
| else for _, y in ipairs(x) do M.stat(cfg, y, x, ...) end |
| end |
| end |
| |
| function M.traverse.expr_list (cfg, x, ...) |
| assert(type(x)=='table', "traverse.expr_list() expects a table") |
| -- x doesn't appear in the ancestors |
| for _, y in ipairs(x) do M.expr(cfg, y, ...) end |
| end |
| |
| function M.malformed(cfg, x, ...) |
| local f = cfg.malformed or cfg.error |
| if f then f(x, ...) else |
| error ("Malformed node of tag "..(x.tag or '(nil)')) |
| end |
| end |
| |
| function M.unknown(cfg, x, ...) |
| local f = cfg.unknown or cfg.error |
| if f then f(x, ...) else |
| error ("Unknown node tag "..(x.tag or '(nil)')) |
| end |
| end |
| |
| function M.occurrence(cfg, x, ...) |
| if cfg.occurrence then cfg.occurrence(cfg.scope :get(x[1]), x, ...) end |
| end |
| |
| -- TODO: Is it useful to call each error handling function? |
| function M.binder_list (cfg, id_list, ...) |
| local f = cfg.binder |
| local ferror = cfg.error or cfg.malformed or cfg.unknown |
| for i, id_node in ipairs(id_list) do |
| local down, up = cfg.down, cfg.up |
| if id_node.tag == 'Id' then |
| cfg.scope :set (id_node[1], { id_node, ... }) |
| if down then down(id_node, ...) end |
| if f then f(id_node, ...) end |
| if up then up(id_node, ...) end |
| elseif i==#id_list and id_node.tag=='Dots' then |
| if down then down(id_node, ...) end |
| if up then up(id_node, ...) end |
| -- Do nothing, those are valid `Dots |
| elseif ferror then |
| -- Traverse error handling function |
| ferror(id_node, ...) |
| else |
| error("Invalid binders list") |
| end |
| end |
| end |
| |
| ---------------------------------------------------------------------- |
| -- Generic walker generator. |
| -- * if `cfg' has an entry matching the tree name, use this entry |
| -- * if not, try to use the entry whose name matched the ast kind |
| -- * if an entry is a table, look for 'up' and 'down' entries |
| -- * if it is a function, consider it as a `down' traverser. |
| ---------------------------------------------------------------------- |
| local walker_builder = function(traverse) |
| assert(traverse) |
| return function (cfg, ...) |
| if not cfg.scope then cfg.scope = M.newscope() end |
| local down, up = cfg.down, cfg.up |
| local broken = down and down(...) |
| if broken ~= 'break' then M.traverse[traverse] (cfg, ...) end |
| if up then up(...) end |
| end |
| end |
| |
| ---------------------------------------------------------------------- |
| -- Declare [M.stat], [M.expr], [M.block]. |
| -- `M.binder_list` is not here, because `cfg.up` and `cfg.down` must |
| -- be called on individual binders, not on the list itself. |
| -- It's therefore handled in `traverse.binder_list()` |
| ---------------------------------------------------------------------- |
| for _, w in ipairs{ "stat", "expr", "block" } do --, "malformed", "unknown" } do |
| M[w] = walker_builder (w, M.traverse[w]) |
| end |
| |
| -- Don't call up/down callbacks on expr lists |
| M.expr_list = M.traverse.expr_list |
| |
| |
| ---------------------------------------------------------------------- |
| -- Try to guess the type of the AST then choose the right walkker. |
| ---------------------------------------------------------------------- |
| function M.guess (cfg, x, ...) |
| assert(type(x)=='table', "arg #2 in a walker must be an AST") |
| if M.tags.expr[x.tag] then return M.expr(cfg, x, ...) end |
| if M.tags.stat[x.tag] then return M.stat(cfg, x, ...) end |
| if not x.tag then return M.block(cfg, x, ...) end |
| error ("Can't guess the AST type from tag "..(x.tag or '<none>')) |
| end |
| |
| local S = { }; S.__index = S |
| |
| function M.newscope() |
| local instance = { current = { } } |
| instance.stack = { instance.current } |
| setmetatable (instance, S) |
| return instance |
| end |
| |
| function S :save(...) |
| local current_copy = { } |
| for a, b in pairs(self.current) do current_copy[a]=b end |
| table.insert (self.stack, current_copy) |
| if ... then return self :add(...) end |
| end |
| |
| function S :restore() self.current = table.remove (self.stack) end |
| function S :get (var_name) return self.current[var_name] end |
| function S :set (key, val) self.current[key] = val end |
| |
| return M |