187 lines
7.1 KiB
Plaintext
Executable File
187 lines
7.1 KiB
Plaintext
Executable File
--------------------------------------------------------------------------------
|
|
--
|
|
-- This library walks AST to gather information about the identifiers
|
|
-- in it. It classifies them between free variables and bound
|
|
-- variables, and keeps track of which AST node created a given bound
|
|
-- variable occurence.
|
|
--
|
|
-- walk_id (kind, ast)
|
|
--
|
|
-- Input:
|
|
-- * an AST kind: 'expr', 'stat', 'block', 'expr_list', 'binder_list', 'guess'
|
|
-- * an AST of the corresponding kind.
|
|
--
|
|
-- > string, AST
|
|
--
|
|
-- Output: a table with two fields, 'bound' and 'free';
|
|
-- * free associates the name of each free variable with the list of
|
|
-- all its occurences in the AST. That list is never empty.
|
|
-- * bound associates each stat or expr binding a new variable with
|
|
-- the occurences of that/those new variable(s).
|
|
--
|
|
-- > { free = table (string, AST and `Id{ });
|
|
-- > bound = table (AST, table(AST and `Id{ })) }
|
|
--
|
|
-- How it works
|
|
-- ============
|
|
-- Walk the tree to:
|
|
-- * locate open variables, and keep pointers on them so that they can
|
|
-- be alpha converted.
|
|
-- * locate variable bindings, so that we can find bound variables
|
|
-- * locate bound variables, keep them in association with their
|
|
-- binder, again in order to alpha-convert them.
|
|
--
|
|
-- Special treatments:
|
|
-- * `Function `Local `Localrec `Fornum `Forin have binders;
|
|
-- `Local takes effect from the next statement,
|
|
-- `Localrec from the current statement,
|
|
-- `Function and other statments inside their bodies.
|
|
-- * `Repeat has a special scoping rule for its condition.
|
|
-- * blocks create temporary scopes
|
|
-- * `Splice must stop the walking, so that user code won't be
|
|
-- converted
|
|
--
|
|
--------------------------------------------------------------------------------
|
|
|
|
-{ extension 'match' }
|
|
-{ extension 'log' }
|
|
|
|
require 'metalua.walk'
|
|
require 'metalua.walk.scope'
|
|
|
|
-- variable lists auto-create empty list as values by default.
|
|
local varlist_mt = { __index = function (self, key)
|
|
local x={ }; self[key] = x; return x
|
|
end }
|
|
|
|
local function _walk_id (kind, supercfg, ast, ...)
|
|
|
|
assert(walk[kind], "Inbalid AST kind selector")
|
|
assert(type(supercfg=='table'), "Config table expected")
|
|
assert(type(ast)=='table', "AST expected")
|
|
|
|
local cfg = { expr = { }; block = { }; stat = { } }
|
|
local scope = scope:new()
|
|
|
|
local visit_bound_var, visit_free_var
|
|
if not supercfg.id then
|
|
printf("Warning, you're using the id walker without id visitor. "..
|
|
"If you know what you want do to, then you're probably doing "..
|
|
"something else...")
|
|
visit_bound_var = || nil
|
|
visit_free_var = || nil
|
|
else
|
|
visit_free_var = supercfg.id.free or || nil
|
|
visit_bound_var = supercfg.id.bound or || nil
|
|
end
|
|
|
|
-----------------------------------------------------------------------------
|
|
-- Check identifiers; add functions parameters to scope
|
|
-----------------------------------------------------------------------------
|
|
function cfg.expr.down(x, ...)
|
|
-- Execute the generic expression walker; if it breaks.
|
|
-- don't do the id walking.
|
|
if supercfg.expr and supercfg.expr.down then
|
|
local r = supercfg.expr.down(x, ...)
|
|
if r then return r end
|
|
end
|
|
local parents = {...}
|
|
match x with
|
|
| `Id{ name } ->
|
|
local binder, r = scope.current[name] -- binder :: ast which bound var
|
|
if binder then
|
|
--$log( 'walk.id found a bound var:', x, binder)
|
|
r = visit_bound_var(x, binder, unpack(parents))
|
|
else
|
|
--$log( 'walk.id found a free var:', x, scope.current)
|
|
r = visit_free_var(x, unpack(parents))
|
|
end
|
|
if r then return r end
|
|
| `Function{ params, _ } -> scope:push (params, x)
|
|
| `Stat{ block, expr } ->
|
|
-------------------------------------------------------------
|
|
-- 'expr' is in the scope of 'block': create the scope and
|
|
-- walk the block 'manually', then prevent automatic walk
|
|
-- by returning 'break'.
|
|
-------------------------------------------------------------
|
|
scope:push()
|
|
for stat in values (block) do walk.stat(cfg, stat, x, ...) end
|
|
walk.expr(cfg, expr, x, unpack(parents))
|
|
scope:pop()
|
|
return 'break'
|
|
| _ -> -- pass
|
|
end
|
|
|
|
end
|
|
|
|
-----------------------------------------------------------------------------
|
|
-- Close the function scope opened by 'down()'
|
|
-----------------------------------------------------------------------------
|
|
function cfg.expr.up(x, ...)
|
|
match x with `Function{...} -> scope:pop() | _ -> end
|
|
if supercfg.expr and supercfg.expr.up then supercfg.expr.up(x, ...) end
|
|
end
|
|
|
|
-----------------------------------------------------------------------------
|
|
-- Create a new scope and register loop variable[s] in it
|
|
-----------------------------------------------------------------------------
|
|
function cfg.stat.down(x, ...)
|
|
-- Execute the generic statement walker; if it breaks.
|
|
-- don't do the id walking.
|
|
if supercfg.stat and supercfg.stat.down then
|
|
local r = supercfg.stat.down(x, ...)
|
|
if r then return r end
|
|
end
|
|
match x with
|
|
| `Forin{ vars, ... } -> scope:push (vars, x)
|
|
| `Fornum{ var, ... } -> scope:push ({var}, x)
|
|
| `Localrec{ vars, ... } -> scope:add (vars, x)
|
|
| `Repeat{ block, expr } ->
|
|
-------------------------------------------------------------
|
|
-- 'expr' is in the scope of 'block': create the scope and
|
|
-- walk the block 'manually', then prevent automatic walk
|
|
-- by returning 'break'.
|
|
-------------------------------------------------------------
|
|
scope:push()
|
|
for stat in values (block) do walk.stat(cfg, stat, x, ...) end
|
|
walk.expr(cfg, expr, x, ...)
|
|
scope:pop()
|
|
return 'break'
|
|
| _ -> -- pass
|
|
end
|
|
end
|
|
|
|
-----------------------------------------------------------------------------
|
|
-- Close the scopes opened by 'up()'
|
|
-----------------------------------------------------------------------------
|
|
function cfg.stat.up(x, ...)
|
|
match x with
|
|
| `Forin{ ... } | `Fornum{ ... } -> scope:pop()
|
|
| `Local{ vars, ... } -> scope:add(vars, x)
|
|
| _ -> -- pass
|
|
-- `Repeat has no up(), because it 'break's.
|
|
end
|
|
if supercfg.stat and supercfg.stat.up then supercfg.stat.up(x, ...) end
|
|
end
|
|
|
|
-----------------------------------------------------------------------------
|
|
-- Create a separate scope for each block
|
|
-----------------------------------------------------------------------------
|
|
function cfg.block.down(x, ...)
|
|
if supercfg.block and supercfg.block.down then
|
|
local r = supercfg.block.down(x, ...)
|
|
if r then return r end
|
|
end
|
|
scope:push()
|
|
end
|
|
function cfg.block.up(x, ...)
|
|
scope:pop()
|
|
if supercfg.block and supercfg.block.up then supercfg.block.up(x, ...) end
|
|
end
|
|
cfg.binder = supercfg.binder
|
|
walk[kind](cfg, ast, ...)
|
|
end
|
|
|
|
local mt = { __index = |_,k| |...| _walk_id(k, ...) }
|
|
walk_id = setmetatable({ }, mt)
|