src/lib/metalua/walk/id.mlua

   1 --------------------------------------------------------------------------------
   2 --
   3 -- This library walks AST to gather information about the identifiers
   4 -- in it. It classifies them between free variables and bound
   5 -- variables, and keeps track of which AST node created a given bound
   6 -- variable occurence.
   7 --
   8 -- walk_id (kind, ast)
   9 --
  10 -- Input:
  11 -- * an AST kind: 'expr', 'stat', 'block', 'expr_list', 'binder_list', 'guess'
  12 -- * an AST of the corresponding kind.
  13 --
  14 -- > string, AST
  15 --
  16 -- Output: a table with two fields, 'bound' and 'free';
  17 -- * free associates the name of each free variable with the list of
  18 --   all its occurences in the AST. That list is never empty.
  19 -- * bound associates each stat or expr binding a new variable with
  20 --   the occurences of that/those new variable(s).
  21 --
  22 -- > { free  = table (string, AST and `Id{ });
  23 -- >   bound = table (AST, table(AST and `Id{ })) }
  24 --
  25 -- How it works
  26 -- ============
  27 -- Walk the tree to:
  28 -- * locate open variables, and keep pointers on them so that they can
  29 --   be alpha converted.
  30 -- * locate variable bindings, so that we can find bound variables
  31 -- * locate bound variables, keep them in association with their
  32 --   binder, again in order to alpha-convert them.
  33 --
  34 -- Special treatments:
  35 -- * `Function `Local `Localrec `Fornum `Forin have binders;
  36 --   `Local takes effect from the next statement,
  37 --   `Localrec from the current statement,
  38 --   `Function and other statments inside their bodies.
  39 -- * `Repeat has a special scoping rule for its condition.
  40 -- * blocks create temporary scopes
  41 -- * `Splice must stop the walking, so that user code won't be
  42 --   converted
  43 --
  44 --------------------------------------------------------------------------------
  45
  46 -{ extension 'match' }
  47 -{ extension 'log' }
  48
  49 require 'metalua.walk'
  50 require 'metalua.walk.scope'
  51
  52 -- variable lists auto-create empty list as values by default.
  53 local varlist_mt = { __index = function (self, key)
  54                                   local x={ }; self[key] = x; return x
  55                                end }
  56
  57 local function _walk_id (kind, supercfg, ast, ...)
  58
  59    assert(walk[kind], "Inbalid AST kind selector")
  60    assert(type(supercfg=='table'), "Config table expected")
  61    assert(type(ast)=='table', "AST expected")
  62
  63    local cfg = { expr = { }; block = { }; stat = { } }
  64    local scope = scope:new()
  65
  66    local visit_bound_var, visit_free_var
  67    if not supercfg.id then
  68       printf("Warning, you're using the id walker without id visitor. "..
  69              "If you know what you want do to, then you're probably doing "..
  70              "something else...")
  71       visit_bound_var = || nil
  72       visit_free_var  = || nil
  73    else
  74       visit_free_var  = supercfg.id.free  or || nil
  75       visit_bound_var = supercfg.id.bound or || nil
  76    end
  77
  78    -----------------------------------------------------------------------------
  79    -- Check identifiers; add functions parameters to scope
  80    -----------------------------------------------------------------------------
  81    function cfg.expr.down(x, ...)
  82       -- Execute the generic expression walker; if it breaks.
  83       -- don't do the id walking.
  84       if supercfg.expr and  supercfg.expr.down then
  85          local r = supercfg.expr.down(x, ...)
  86          if r then return r end
  87       end
  88       match x with
  89       | `Id{ name } ->
  90          local binder, r = scope.current[name] -- binder :: ast which bound var
  91          if binder then
  92             --$log( 'walk.id found a bound var:', x, binder)
  93             r = visit_bound_var(x, binder, ...)
  94          else
  95             --$log( 'walk.id found a free var:', x, scope.current)
  96             r = visit_free_var(x, ...)
  97          end
  98          if r then return r end
  99       | `Function{ params, _ } -> scope:push (params, x)
 100       | `Stat{ block, expr }   ->
 101          -------------------------------------------------------------
 102          -- 'expr' is in the scope of 'block': create the scope and
 103          -- walk the block 'manually', then prevent automatic walk
 104          -- by returning 'break'.
 105          -------------------------------------------------------------
 106          scope:push()
 107          for stat in values (block) do walk.stat(cfg, stat, x, ...) end
 108          walk.expr(cfg, expr, x, ...)
 109          scope:pop()
 110          return 'break'
 111       | _ -> -- pass
 112       end
 113
 114    end
 115
 116    -----------------------------------------------------------------------------
 117    -- Close the function scope opened by 'down()'
 118    -----------------------------------------------------------------------------
 119    function cfg.expr.up(x, ...)
 120       match x with `Function{...} -> scope:pop() | _ -> end
 121       if supercfg.expr and supercfg.expr.up then supercfg.expr.up(x, ...) end
 122    end
 123
 124    -----------------------------------------------------------------------------
 125    -- Create a new scope and register loop variable[s] in it
 126    -----------------------------------------------------------------------------
 127    function cfg.stat.down(x, ...)
 128       -- Execute the generic statement walker; if it breaks.
 129       -- don't do the id walking.
 130       if supercfg.stat and supercfg.stat.down then
 131          local r = supercfg.stat.down(x, ...)
 132          if r then return r end
 133       end
 134       match x with
 135       | `Forin{ vars, ... }    -> scope:push (vars,  x)
 136       | `Fornum{ var, ... }    -> scope:push ({var}, x)
 137       | `Localrec{ vars, ... } -> scope:add  (vars,  x)
 138       | `Repeat{ block, expr } ->
 139          -------------------------------------------------------------
 140          -- 'expr' is in the scope of 'block': create the scope and
 141          -- walk the block 'manually', then prevent automatic walk
 142          -- by returning 'break'.
 143          -------------------------------------------------------------
 144          scope:push()
 145          for stat in values (block) do walk.stat(cfg, stat, x, ...) end
 146          walk.expr(cfg, expr, x, ...)
 147          scope:pop()
 148          return 'break'
 149       | _ -> -- pass
 150       end
 151    end
 152
 153    -----------------------------------------------------------------------------
 154    -- Close the scopes opened by 'up()'
 155    -----------------------------------------------------------------------------
 156    function cfg.stat.up(x, ...)
 157       match x with
 158       | `Forin{ ... } | `Fornum{ ... } -> scope:pop()
 159       | `Local{ vars, ... }            -> scope:add(vars, x)
 160       | _                              -> -- pass
 161       -- `Repeat has no up(), because it 'break's.
 162       end
 163       if supercfg.stat and supercfg.stat.up then supercfg.stat.up(x, ...) end
 164    end
 165
 166    -----------------------------------------------------------------------------
 167    -- Create a separate scope for each block
 168    -----------------------------------------------------------------------------
 169    function cfg.block.down(x, ...)
 170       if supercfg.block and supercfg.block.down then
 171          local r = supercfg.block.down(x, ...)
 172          if r then return r end
 173       end
 174       scope:push()
 175    end
 176    function cfg.block.up(x, ...)
 177       scope:pop()
 178       if supercfg.block and supercfg.block.up then supercfg.block.up(x, ...) end
 179    end
 180    cfg.binder = supercfg.binder
 181    walk[kind](cfg, ast, ...)
 182 end
 183
 184 local mt = { __index = |_,k| |...| _walk_id(k, ...) }
 185 walk_id = setmetatable({ }, mt)