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       local parents = {...}
  89       match x with
  90       | `Id{ name } ->
  91          local binder, r = scope.current[name] -- binder :: ast which bound var
  92          if binder then
  93             --$log( 'walk.id found a bound var:', x, binder)
  94             r = visit_bound_var(x, binder, unpack(parents))
  95          else
  96             --$log( 'walk.id found a free var:', x, scope.current)
  97             r = visit_free_var(x, unpack(parents))
  98          end
  99          if r then return r end
 100       | `Function{ params, _ } -> scope:push (params, x)
 101       | `Stat{ block, expr }   ->
 102          -------------------------------------------------------------
 103          -- 'expr' is in the scope of 'block': create the scope and
 104          -- walk the block 'manually', then prevent automatic walk
 105          -- by returning 'break'.
 106          -------------------------------------------------------------
 107          scope:push()
 108          for stat in values (block) do walk.stat(cfg, stat, x, ...) end
 109          walk.expr(cfg, expr, x, unpack(parents))
 110          scope:pop()
 111          return 'break'
 112       | _ -> -- pass
 113       end
 114
 115    end
 116
 117    -----------------------------------------------------------------------------
 118    -- Close the function scope opened by 'down()'
 119    -----------------------------------------------------------------------------
 120    function cfg.expr.up(x, ...)
 121       match x with `Function{...} -> scope:pop() | _ -> end
 122       if supercfg.expr and supercfg.expr.up then supercfg.expr.up(x, ...) end
 123    end
 124
 125    -----------------------------------------------------------------------------
 126    -- Create a new scope and register loop variable[s] in it
 127    -----------------------------------------------------------------------------
 128    function cfg.stat.down(x, ...)
 129       -- Execute the generic statement walker; if it breaks.
 130       -- don't do the id walking.
 131       if supercfg.stat and supercfg.stat.down then
 132          local r = supercfg.stat.down(x, ...)
 133          if r then return r end
 134       end
 135       match x with
 136       | `Forin{ vars, ... }    -> scope:push (vars,  x)
 137       | `Fornum{ var, ... }    -> scope:push ({var}, x)
 138       | `Localrec{ vars, ... } -> scope:add  (vars,  x)
 139       | `Repeat{ block, expr } ->
 140          -------------------------------------------------------------
 141          -- 'expr' is in the scope of 'block': create the scope and
 142          -- walk the block 'manually', then prevent automatic walk
 143          -- by returning 'break'.
 144          -------------------------------------------------------------
 145          scope:push()
 146          for stat in values (block) do walk.stat(cfg, stat, x, ...) end
 147          walk.expr(cfg, expr, x, ...)
 148          scope:pop()
 149          return 'break'
 150       | _ -> -- pass
 151       end
 152    end
 153
 154    -----------------------------------------------------------------------------
 155    -- Close the scopes opened by 'up()'
 156    -----------------------------------------------------------------------------
 157    function cfg.stat.up(x, ...)
 158       match x with
 159       | `Forin{ ... } | `Fornum{ ... } -> scope:pop()
 160       | `Local{ vars, ... }            -> scope:add(vars, x)
 161       | _                              -> -- pass
 162       -- `Repeat has no up(), because it 'break's.
 163       end
 164       if supercfg.stat and supercfg.stat.up then supercfg.stat.up(x, ...) end
 165    end
 166
 167    -----------------------------------------------------------------------------
 168    -- Create a separate scope for each block
 169    -----------------------------------------------------------------------------
 170    function cfg.block.down(x, ...)
 171       if supercfg.block and supercfg.block.down then
 172          local r = supercfg.block.down(x, ...)
 173          if r then return r end
 174       end
 175       scope:push()
 176    end
 177    function cfg.block.up(x, ...)
 178       scope:pop()
 179       if supercfg.block and supercfg.block.up then supercfg.block.up(x, ...) end
 180    end
 181    cfg.binder = supercfg.binder
 182    walk[kind](cfg, ast, ...)
 183 end
 184
 185 local mt = { __index = |_,k| |...| _walk_id(k, ...) }
 186 walk_id = setmetatable({ }, mt)