metalua/treequery/walk.mlua

   1 -------------------------------------------------------------------------------
   2 -- Copyright (c) 2006-2013 Fabien Fleutot and others.
   3 --
   4 -- All rights reserved.
   5 --
   6 -- This program and the accompanying materials are made available
   7 -- under the terms of the Eclipse Public License v1.0 which
   8 -- accompanies this distribution, and is available at
   9 -- http://www.eclipse.org/legal/epl-v10.html
  10 --
  11 -- This program and the accompanying materials are also made available
  12 -- under the terms of the MIT public license which accompanies this
  13 -- distribution, and is available at http://www.lua.org/license.html
  14 --
  15 -- Contributors:
  16 --     Fabien Fleutot - API and implementation
  17 --
  18 -------------------------------------------------------------------------------
  19
  20 -- Low level AST traversal library.
  21 -- This library is a helper for the higher-level treequery library.
  22 -- It walks through every node of an AST, depth-first, and executes
  23 -- some callbacks contained in its cfg config table:
  24 --
  25 -- * cfg.down(...) is called when it walks down a node, and receive as
  26 --   parameters the node just entered, followed by its parent, grand-parent
  27 --   etc. until the root node.
  28 --
  29 -- * cfg.up(...) is called when it walks back up a node, and receive as
  30 --   parameters the node just entered, followed by its parent, grand-parent
  31 --   etc. until the root node.
  32 --
  33 -- * cfg.occurrence(binder, id_node, ...) is called when it visits an `Id{ }
  34 --   node which isn't a local variable creator. binder is a reference to its
  35 --   binder with its context. The binder is the `Id{ } node which created
  36 --   this local variable. By "binder and its context", we mean a list starting
  37 --   with the `Id{ }, and followed by every ancestor of the binder node, up until
  38 --   the common root node.
  39 --   binder is nil if the variable is global.
  40 --   id_node is followed by its ancestor, up until the root node.
  41 --
  42 -- cfg.scope is maintained during the traversal, associating a
  43 -- variable name to the binder which creates it in the context of the
  44 -- node currently visited.
  45 --
  46 -- walk.traverse.xxx functions are in charge of the recursive descent into
  47 -- children nodes. They're private helpers.
  48 --
  49 -- corresponding walk.xxx functions also take care of calling cfg callbacks.
  50
  51 -{ extension ("match", ...) }
  52
  53 local pp = require 'metalua.pprint'
  54
  55 local M = { traverse = { }; tags = { }; debug = false }
  56
  57 local function table_transpose(t)
  58     local tt = { }; for a, b in pairs(t) do tt[b]=a end; return tt
  59 end
  60
  61 --------------------------------------------------------------------------------
  62 -- Standard tags: can be used to guess the type of an AST, or to check
  63 -- that the type of an AST is respected.
  64 --------------------------------------------------------------------------------
  65 M.tags.stat = table_transpose{
  66    'Do', 'Set', 'While', 'Repeat', 'Local', 'Localrec', 'Return',
  67    'Fornum', 'Forin', 'If', 'Break', 'Goto', 'Label',
  68    'Call', 'Invoke' }
  69 M.tags.expr = table_transpose{
  70    'Paren', 'Call', 'Invoke', 'Index', 'Op', 'Function', 'Stat',
  71    'Table', 'Nil', 'Dots', 'True', 'False', 'Number', 'String', 'Id' }
  72
  73 --------------------------------------------------------------------------------
  74 -- These [M.traverse.xxx()] functions are in charge of actually going through
  75 -- ASTs. At each node, they make sure to call the appropriate walker.
  76 --------------------------------------------------------------------------------
  77 function M.traverse.stat (cfg, x, ...)
  78    if M.debug then pp.printf("traverse stat %s", x) end
  79    local ancestors = {...}
  80    local B  = |y| M.block       (cfg, y, x, unpack(ancestors)) -- Block
  81    local S  = |y| M.stat        (cfg, y, x, unpack(ancestors)) -- Statement
  82    local E  = |y| M.expr        (cfg, y, x, unpack(ancestors)) -- Expression
  83    local EL = |y| M.expr_list   (cfg, y, x, unpack(ancestors)) -- Expression List
  84    local IL = |y| M.binder_list (cfg, y, x, unpack(ancestors)) -- Id binders List
  85    local OS = || cfg.scope :save()                             -- Open scope
  86    local CS = || cfg.scope :restore()                          -- Close scope
  87
  88    match x with
  89    | {...} if x.tag == nil -> for _, y in ipairs(x) do M.stat(cfg, y, ...) end
  90                           -- no tag --> node not inserted in the history ancestors
  91    | `Do{...}                    -> OS(x); for _, y in ipairs(x) do S(y) end; CS(x)
  92    | `Set{ lhs, rhs }            -> EL(lhs); EL(rhs)
  93    | `While{ cond, body }        -> E(cond); OS(); B(body); CS()
  94    | `Repeat{ body, cond }       -> OS(body); B(body); E(cond); CS(body)
  95    | `Local{ lhs }               -> IL(lhs)
  96    | `Local{ lhs, rhs }          -> EL(rhs); IL(lhs)
  97    | `Localrec{ lhs, rhs }       -> IL(lhs); EL(rhs)
  98    | `Fornum{ i, a, b, body }    -> E(a); E(b); OS(); IL{i}; B(body); CS()
  99    | `Fornum{ i, a, b, c, body } -> E(a); E(b); E(c); OS(); IL{i}; B(body); CS()
 100    | `Forin{ i, rhs, body }      -> EL(rhs); OS(); IL(i); B(body); CS()
 101    | `If{...}                    ->
 102        for i=1, #x-1, 2 do
 103            E(x[i]); OS(); B(x[i+1]); CS()
 104        end
 105        if #x%2 == 1 then
 106            OS(); B(x[#x]); CS()
 107        end
 108    | `Call{...}|`Invoke{...}|`Return{...} -> EL(x)
 109    | `Break | `Goto{ _ } | `Label{ _ }    -> -- nothing
 110    | { tag=tag, ...} if M.tags.stat[tag]->
 111       M.malformed (cfg, x, unpack (ancestors))
 112    | _ ->
 113       M.unknown (cfg, x, unpack (ancestors))
 114    end
 115 end
 116
 117 function M.traverse.expr (cfg, x, ...)
 118    if M.debug then pp.printf("traverse expr %s", x) end
 119    local ancestors = {...}
 120    local B  = |y| M.block       (cfg, y, x, unpack(ancestors)) -- Block
 121    local S  = |y| M.stat        (cfg, y, x, unpack(ancestors)) -- Statement
 122    local E  = |y| M.expr        (cfg, y, x, unpack(ancestors)) -- Expression
 123    local EL = |y| M.expr_list   (cfg, y, x, unpack(ancestors)) -- Expression List
 124    local IL = |y| M.binder_list (cfg, y, x, unpack(ancestors)) -- Id binders list
 125    local OS = || cfg.scope :save()                             -- Open scope
 126    local CS = || cfg.scope :restore()                          -- Close scope
 127
 128    match x with
 129    | `Paren{ e }               -> E(e)
 130    | `Call{...} | `Invoke{...} -> EL(x)
 131    | `Index{ a, b }            -> E(a); E(b)
 132    | `Op{ opid, ... }          -> E(x[2]); if #x==3 then E(x[3]) end
 133    | `Function{ params, body } -> OS(body); IL(params); B(body); CS(body)
 134    | `Stat{ b, e }             -> OS(b); B(b); E(e); CS(b)
 135    | `Id{ name }               -> M.occurrence(cfg, x, unpack(ancestors))
 136    | `Table{ ... }             ->
 137       for i = 1, #x do match x[i] with
 138          | `Pair{ k, v } -> E(k); E(v)
 139          | v             -> E(v)
 140       end end
 141    | `Nil|`Dots|`True|`False|`Number{_}|`String{_} -> -- terminal node
 142    | { tag=tag, ...} if M.tags.expr[tag]-> M.malformed (cfg, x, unpack (ancestors))
 143    | _ -> M.unknown (cfg, x, unpack (ancestors))
 144    end
 145 end
 146
 147 function M.traverse.block (cfg, x, ...)
 148    assert(type(x)=='table', "traverse.block() expects a table")
 149    if x.tag then M.malformed(cfg, x, ...)
 150    else for _, y in ipairs(x) do M.stat(cfg, y, x, ...) end
 151    end
 152 end
 153
 154 function M.traverse.expr_list (cfg, x, ...)
 155    assert(type(x)=='table', "traverse.expr_list() expects a table")
 156    -- x doesn't appear in the ancestors
 157    for _, y in ipairs(x) do M.expr(cfg, y, ...) end
 158 end
 159
 160 function M.malformed(cfg, x, ...)
 161     local f = cfg.malformed or cfg.error
 162     if f then f(x, ...) else
 163         error ("Malformed node of tag "..(x.tag or '(nil)'))
 164     end
 165 end
 166
 167 function M.unknown(cfg, x, ...)
 168     local f = cfg.unknown or cfg.error
 169     if f then f(x, ...) else
 170         error ("Unknown node tag "..(x.tag or '(nil)'))
 171     end
 172 end
 173
 174 function M.occurrence(cfg, x, ...)
 175     if cfg.occurrence then cfg.occurrence(cfg.scope :get(x[1]),  x, ...) end
 176 end
 177
 178 -- TODO: Is it useful to call each error handling function?
 179 function M.binder_list (cfg, id_list, ...)
 180     local f = cfg.binder
 181     local ferror = cfg.error or cfg.malformed or cfg.unknown
 182     for i, id_node in ipairs(id_list) do
 183       if id_node.tag == 'Id' then
 184          cfg.scope :set (id_node[1], { id_node, ... })
 185          if f then f(id_node, ...) end
 186       elseif i==#id_list and id_node.tag=='Dots' then
 187          -- Do nothing, those are valid `Dots
 188       elseif ferror then
 189          -- Traverse error handling function
 190          ferror(id_node, ...)
 191       else
 192          error("Invalid binders list")
 193       end
 194    end
 195 end
 196
 197 ----------------------------------------------------------------------
 198 -- Generic walker generator.
 199 -- * if `cfg' has an entry matching the tree name, use this entry
 200 -- * if not, try to use the entry whose name matched the ast kind
 201 -- * if an entry is a table, look for 'up' and 'down' entries
 202 -- * if it is a function, consider it as a `down' traverser.
 203 ----------------------------------------------------------------------
 204 local walker_builder = function(traverse)
 205    assert(traverse)
 206    return function (cfg, ...)
 207       if not cfg.scope then cfg.scope = M.newscope() end
 208       local down, up = cfg.down, cfg.up
 209       local broken = down and down(...)
 210       if broken ~= 'break' then M.traverse[traverse] (cfg, ...) end
 211       if up then up(...) end
 212    end
 213 end
 214
 215 ----------------------------------------------------------------------
 216 -- Declare [M.stat], [M.expr], [M.block] and [M.expr_list]
 217 ----------------------------------------------------------------------
 218 for _, w in ipairs{ "stat", "expr", "block" } do --, "malformed", "unknown" } do
 219    M[w] = walker_builder (w, M.traverse[w])
 220 end
 221
 222 -- Don't call up/down callbacks on expr lists
 223 M.expr_list = M.traverse.expr_list
 224
 225
 226 ----------------------------------------------------------------------
 227 -- Try to guess the type of the AST then choose the right walkker.
 228 ----------------------------------------------------------------------
 229 function M.guess (cfg, x, ...)
 230    assert(type(x)=='table', "arg #2 in a walker must be an AST")
 231    if M.tags.expr[x.tag] then return M.expr(cfg, x, ...)  end
 232    if M.tags.stat[x.tag] then return M.stat(cfg, x, ...)  end
 233    if not x.tag          then return M.block(cfg, x, ...) end
 234    error ("Can't guess the AST type from tag "..(x.tag or '<none>'))
 235 end
 236
 237 local S = { }; S.__index = S
 238
 239 function M.newscope()
 240     local instance = { current = { } }
 241     instance.stack = { instance.current }
 242     setmetatable (instance, S)
 243     return instance
 244 end
 245
 246 function S :save(...)
 247     local current_copy = { }
 248     for a, b in pairs(self.current) do current_copy[a]=b end
 249     table.insert (self.stack, current_copy)
 250     if ... then return self :add(...) end
 251 end
 252
 253 function S :restore() self.current = table.remove (self.stack) end
 254 function S :get (var_name) return self.current[var_name] end
 255 function S :set (key, val) self.current[key] = val end
 256
 257 return M