metalua

don't yield across C/Lua boundaries · is

treequery()
treequery
Q
$()

local Q = require 'metalua.treequery'

ast = +{ block: 

    local x=1

    for y=1,10 do

        print (x+i)

    end

    return math.cos(x) }

all_nodes = Q(ast)

+{...}
-{...}
ast

ast = { 

    `Local{ { `Id "x" }, { `Number 1 } },

    `Fornum{ `Id "y", `Number 1, `Number 10, {

        `Call{ `Id "print", `Op{ "add", `Id "x", `Id "i" } }

    }

    `Return{ `Call{ `Index{ `Id "math", `String "cos" }, `Id "x" } } }

`Foo{bar}
{tag='Foo', bar}
Q(ast)
:filter()

call_nodes = Q(ast) :filter (function(node) return node.tag=='Call' end)

+{print(x+i)}
+{math.cos(x)}

call_stats = Q(ast) :filter (function(node, parent)

    return node.tag=='Call' and parent and parent.tag==nil

end)
Q.has_tag(tag_1, tag_2, ... tag_n)

call_nodes = Q(ast) :filter(Q.has_tag 'Call')

call_nodes = Q(ast) :filter 'Call'

Q.parent()
Q.is_block
Q.parent(Q.is_block)

call_stats = Q(ast) :filter 'Call' :filter (Q.parent(Q.is_block))

:filter()
:after(), :not_after(), :under(), not_under(), :under_or_after(), :not_under_or_after()

not_in_func = Q(ast) :not_under (function(x) x.tag=='Function' end)

not_in_func = Q(ast) :not_under (Q.has_tag 'Function')

not_in_func = Q(ast) :not_under 'Function'

ast = +{block: 

    if foo then return a end 

    local function bar() 

         return b 

    end}

return a
return b
function bar

my_returns = Q(ast) 

    :filter(Q.has_tag('Return'))  

    :not_under(Q.has_tag('Function'))

my_returns = Q(ast) :filter 'Return' :not_under 'Function'

for x=... end
local x
function (x)... end
print(x)
nil
Q.binder(occurrence, ast_root)
Q.is_occurrence_of(binder)
Q.is_binder(...)
Q.is_nth(n)(node, ...)
Q.is_nth(a, b)(node, ...)
n
a <= n <= b
Q.is_stat(), Q.is_expr(), Q.is.block()
Q.parent()
Q.child(n, P)
n
P
Q.child(n1, n2, P)
P
n2
n1
:list()
a(b1(c11,c12),b2(c21,c22))
{a, b1, c11, c12, b2, c21, c22}
:first()
Q(+{print(1+2*3)}) :filter 'Op' :first()
+{1+2*3}, +{print(1+2*3)}
:foreach()
down()
up()
down()
up()
down()
down()
up()
up()
down()
up()
:foreach()
down()
up()
:foreach()
:list()
:first()
:map(p1, p2, ..., pn, f)
N
p1,...pn
f(N)
f
f()
:map()

for x, x_parent in Q(ast) :filter 'Call' do 

     various_stuff_on_call_nodes(x, x_parent) 

end

Q(ast) :filter 'Call' :foreach (function (x, x_parent) 

     various_stuff_on_call_nodes(x, x_parent) 

end)

synth
:acc()
:nl()
:nlindent()
:nldedent()
:node()
:list()
:node()
synth:Foo(ast, ...)
:node()
:acc()
:nl()
:nlindent()
:nldedent()
:node()
:list()
foo['bar']
foo.bar
x.y.z = function() ... end
function x.y.z() ... end
x.y.z.methodname = function (self, ...) end
function x.y.z:methodname (...) end
{ ['foo'] = bar }
{ foo = bar }
foo('bar')"
foo({bar})
foo:bar('gnat')
foo:bar({gnat})
foo 'bar'
foo{ bar }
foo:bar 'gnat'
foo:bar{ gnat }
"for i=1,10 do print(i) end"
`For{ `Id "i", `Number 1, `Number 10, 
      { `Call{ `Id "print", `Id "i" } } }
`For
`Id "i"
`Call
`Id "print"
`Id "print"
`Index{ `Id "_G", `String "print" }
ast [4] [1] = +{_G.print}
for [ ] = [ ], [ ] do [ ] end
+{_G.print}
weaveable
ast_children
require 'walk'

function weave_ast (src, ast, name)
   local ast_children, weaveable, node_cfg = { }, { }, { }

   function node_cfg.down(ast, parent)
      if   not ast.lineinfo 
      then weaveable [parent] = nil
      else weaveable [ast] = true end
      ast_children [ast] = { }
      if parent then table.insert (ast_children [parent], ast) end
   end

   local cfg = { expr=node_cfg; stat=node_cfg; block=node_cfg }
   walk.block (cfg, ast)
end

local src = ???
local ast = mlc.luastring_to_ast (src, name)
weave_ast (src, ast)
gen_source
function weave_ast (src, ast, name)
   local gen_source, ast_children, weaveable, node_cfg = { }, { }, { }, { }

   function node_cfg.down(ast, parent) ... end

   function node_cfg.up(ast)
      local function weave_skeleton (ast)
         local buffer = { }
         local a, d = ast.lineinfo.first[3], ast.lineinfo.last[3]
         for child in ivalues (ast_children [ast]) do
            local b, c = child.lineinfo.first[3], child.lineinfo.last[3]
            table.insert (buffer, acc (src:sub (a, b-1)) .. acc (gen_source [child]))
            a = c+1
         end
         gen_source [ast] = table.concat (buffer) .. src:sub (a, d)
      end
      if weaveable [ast] then weave (ast)
      else error "Can't handle nodes without proper lineinfo yet" end
   end

   local cfg = { expr=node_cfg; stat=node_cfg; block=node_cfg }
   walk.block (cfg, ast)
   return gen_source [ast]
end
print( -{ `Stat{ +{block: local x = 21}, +{expr: 2*x} })
mlp.lexer:add{ "stat" }
mlp.expr:add{ "stat", mlp.block, "end", builder = stat_builder }
function stat_builder(x)
  local returned_expr
  local walker_cfg = { ... } -- Here the magic happens
  walk.block (walker_cfg, x[1])
  return `Stat{ x[1], expr }
end
print(stat 
   local x=21; 
   if foo then return foo else return 2*x end
end)
print(stat
   local $1=nil
   local x=21
   if foo then $1=foo; goto 'retval'
   else $1=2*x; goto 'retval' end
   label 'retval'
   return $1
end)
-{ extension 'xmatch' }

require 'walk'

local function stat_builder (x)
   local body, result = x[1]

   -- Accumulate direct return statements in `return_stats' list
   local return_stats = { }
   local walker_cfg = { expr={ }, stat={ } }
   match function walker_cfg.stat.up
   | `Return{ _ } == x -> table.insert (return_stats, x) 
   | `Return{   } == x -> x[1] = +{nil}; table.insert (return_stats, x) 
   | `Return{...} -> error "No multi-returns in stat blocks!"
   | _ -> 
   end
   match function walker_cfg.expr.down
   | `Function{...} -> return 'break' | _ -> 
   end
   walk.block (walker_cfg, x[1])

   match return_stats with
   -- No return statement -> resulting value is nil, don't change the body
   | { } -> result = +{ nil }
   -- One return statement at the end -> just extract it
   | { ret } if body[#body] == ret -> result = table.remove (body) [1]
   -- Several returns -> use variable and goto statements
   | _ -> 
      local retvar = mlp.gensym 'stat_value' 
      local label  = mlp.gensym 'end_of_stat'
      table.insert (body, 1, `Local{ {retvar}, { } })
      table.insert (body, `Label{ label })
      for ret in ivalues (return_stats) do
         ret.tag = nil
         ret <- { `Set{ {retvar}, {ret[1]} }, `Goto{ label } }
      end
      result = retvar
   end
   return `Stat{ body, result }
end

mlp.lexer:add{ "stat" }
mlp.expr:add{ "stat", mlp.block, "end", builder = stat_builder }
function stat_builder (x)
   local body, result = x[1], +{ nil }
   if body[#body].tag == 'Return' then 
      result = table.remove (body) [1]
   end
   return `Stat{ body, result }
end

mlp.lexer:add{ "stat" }
mlp.expr:add{ "stat", mlp.block, "end", builder = stat_builder }

-{ extension 'xmatch' }

require 'walk'

local multireturn_tags = table.transpose{ 'Dots', 'Call', 'Invoke' }

local function stat_builder (x)
   local body, result = x[1]

   -- Accumulate direct return statements in `return_stats' list
   local multireturn  = false
   local return_stats = { }
   local walker_cfg = { expr={ }, stat={ } }
   match function walker_cfg.stat.up
   | `Return{...} == x ->
      if #x>1 or multireturn_tags[x[#x].tag] then multireturn = true end
      table.insert (return_stats, x) 
   | _ -> 
   end
   match function walker_cfg.expr.down
   | `Function{...} -> return 'break' | _ -> 
   end
   walk.block (walker_cfg, x[1])

   match return_stats with
   -- No return statement -> resulting value is nil, don't change the body
   | { } -> result = +{ nil }; assert(not multireturn)
   -- One return statement at the end -> just extract it
   | { ret } if body[#body] == ret -> 
      if multireturn then
         result     = table.remove (body) 
         result.tag = 'Table' -- change return stat into list
      else
         result     = table.remove (body) [1]
      end
   -- Several returns -> use variable and goto statements
   | _ -> 
      local retvar = mlp.gensym 'stat_value' 
      local label  = mlp.gensym 'end_of_stat'
      table.insert (body, 1, `Local{ {retvar}, { multireturn and `Table } })
      table.insert (body, `Label{ label })
      for ret in ivalues (return_stats) do
         local this_result
         if multireturn then 
            this_result = table.shallow_copy(ret)
            this_result.tag = 'Table'
         else 
            this_result = ret[1] 
         end 
         ret.tag = nil
         ret <- { `Set{ {retvar}, {this_result} }, `Goto{ label } }
      end
      result = retvar
   end
   if multireturn then
      return `Call{ `Id "unpack", `Stat{ body, result } }
   else
      return `Stat{ body, result }
   end
end

mlp.lexer:add{ "stat" }
mlp.expr:add{ "stat", mlp.block, "end", builder = stat_builder }
-{ extension 'withdo' }

function run (fmt, ...)
   with h = io.popen(string.format(fmt, ...), 'r') do
      return h:read '*a'
   end
end

function run (fmt, ...)
   do
      local h
      try 
         h = io.popen(string.format(fmt, ...), 'r') do
         return h:read '*a'
      finally
         h:close()
      end
   end
end

function run (fmt, ...)
   do
      local h
      local args = {...}
      local caught_return
      local user_success, user_error = pcall( function()
         h = io.popen(string.format(fmt, unpack(args)), 'r')
         caught_return =  { h:read '*a' }
      end)
      h:close()
      if user_success then
         if caught_return then return unpack(caught_return) end
      else
         error (user_error)
      end
   end
end

for i=0,9 for j=0,90,10 do
  print (i+j)
end
for i=0, 9 do
   for j=0, 90, 10 do
      print (i+j)
   end
end
function f(a, b, c)
  match a, b, c with
  | x1, y1, z1 -> foo()
  | x2, y2, z2 -> bar()
  end
end
match function f
| x1, y1, z1 -> foo()
| x2, y2, z2 -> bar()
end
f = match function
| x if x%2==0 -> return 'even'
| _ -> return 'odd'
end
assert(x.tag=='If')
cond = x[1]
stat = x[2][1]
-- Syntax sugar:
try
  $FOOBAR
catch $X ->
  $EXCEPTION_HANDLING
end

-- Developped version:
do
  local status, $x = pcall(function() $FOOBAR end)
  if not status then $EXCEPTION_HANDLING
end

-- Metalua macro doing this:
function trycatch_builder(x)
  local try_block, exn_name, catch_block = unpack(x)
  return +{ stat: do
     local status, -{exn_name} = pcall(function() -{try_block} end)
     if not status then -{catch_block} end
  end }
end

mlp.lexer:add{ "try", "catch", "end" }     -- new keywords.
mlp.stat:add{ "try", mlp.block, "catch", mlp.id, "->", mlp.block, "end",
             builder = trycatch_builder } -- new statement.

function f()
  try
     return 42
  catch x -> print("An error occured: "..x) end
end

local function d(x)
  match x with
  | `Return{...}   -> transform_return_statement(x); return 'break'
  | `Function{...} -> return 'break'
  | _ -> -- pass
  end
end
replace_returns = |x| walk.block({stat={down=d}, expr={down=d}}, x)

-- Syntactical version:
try
  $TRY_BLOCK
catch $EXN_NAME ->
  $CATCH_BLOCK
finally
  $FINALLY_BLOCK
end

-- Transformed version
do
  local returned_values = nil
  local try_success, $EXN_NAME =
     pcall(function() $TRY_BLOCK_WITH_PARSED_RETURNS end)
  local catch_success, catch_error
  if not user_success then
     catch_success, catch_error =
        pcall(function() $CATCH_BLOCK_WITH_PARSED_RETURNS end)
  end
  $FINALLY_BLOCK
  if not user_success and not catch_success then
     error (catch_error)
  end
  if returned_values then
     return unpack(returned_values)
  end
end

-- In the code above, _PARSED_RETURNS means that "return $RESULTS"
-- is replaced with "returned_values = { $RESULTS }; return"

mlp.lexer:add{ 'try', 'catch', 'finally', '->' }
mlp.block.terminators:add{ 'catch', 'finally' }
table.insert(match_cases_list_parser.terminators, 'finally')

mlp.stat:add{
  'try',
  mlp.block,
  gg.onkeyword{ 'catch', match_cases_list_parser },
  gg.onkeyword{ 'finally', mlp.block },
  'end',
  builder = trycatch_builder }

match <some_value> with
| <pattern_1> -> <block_1>
| <pattern_2> -> <block_2>
...
| <pattern_n> -> <block_n>
end
match <some_value> with
| <pattern_1> | <pattern_1_bis > -> <block_1>
...
end
match x with
| 1 -> print 'x is one'
| 2 -> print 'x is two'
end
match stat with
| `Local{ identifiers, values } -> table.foreach(identifiers, |x| print(x[1])
... -- other cases
end
match x with
| n if n%2 == 0 -> print 'odd'
| _ -> print 'even'
end
match x with
| n | {n} if n%2 == 0 -> print 'odd'
| _ -> print 'even'
end
match {a,b} with
| {pattern_for_a, pattern_for_b} -> block
...
end
match a, b with
| pattern_for_a, pattern_for_b -> block
...
end
mlp.stat:add{ name = "match statement",
   "match", mlp.expr_list, "with",
   gg.optkeyword "|",
   gg.list{ name  = "match cases list",
      primary     = gg.sequence{ name = "match case",
         gg.list{ name  = "patterns",
            primary     = mlp.expr_list,
            separators  = "|",
            terminators = { "->", "if" } },
         gg.onkeyword{ "if", mlp.expr },
         "->",
         mlp.block },
      separators  = "|",
      terminators = "end" },
   "end",
   builder = |x| match_builder (x[1], x[3]) }
function traverse(node)
   down(node)
   for c in children(node) do
      traverse(node)
   end
   up(node)
end

cfg = { }
walker = walk.block(cfg)

cfg.stat = {
   pred = 'Call',
   down = function(x)
      match x with
      | `Call{ `Id 'assert', ... } ->
         x.tag=nil; for i=1,#x do x[i]=nil end -- function call erased
      | `Call{ ... } -> -- nothing to do, it's a normal call
      | _ -> assert(false) -- impossible, pred filtered those out
      end
   end }

cfg.expr = {
   pred = 'Call',
   down = function(x)
      match x with
      | `Call{ `Id 'assert', ... } ->
         x.tag='Nil'; for i=1,#x do x[i]=nil end -- node is now `Nil
      | `Call{ ... } -> -- nothing to do, it's a normal call
      | _ -> assert(false) -- impossible, pred filtered those out
      end
   end }

-- [...]
match x with
| `Call{ `Id 'assert', ... } -> table.override(x, `Nil)
-- [...]

require 'std'
require 'walk'

-{ extension 'match' }

--------------------------------------------------------------------------------
-- Scope handling: ':push()' saves the current scope, ':pop()'
-- restores the previously saved one. ':add(identifiers_list)' adds
-- identifiers to the current scope. Current scope is stored in
-- '.current', as a string->boolean hashtable.
--------------------------------------------------------------------------------

local scope = { }
scope.__index = scope

function scope:new()
   local ret = { current = { } }
   ret.stack = { ret.current }
   setmetatable (ret, self)
   return ret
end

function scope:push()
   table.insert (self.stack, table.shallow_copy (self.current))
end

function scope:pop()
   self.current = table.remove (self.stack)
end

function scope:add (vars)
   for id in values (vars) do
      match id with `Id{ x } -> self.current[x] = true end
   end
end

local function fv (term)
   local freevars = { }
   local scope    = scope:new()
   local cfg = { expr  = { pred = "Id" } }

   function cfg.expr.down(x)
      match x with
      | `Id{ name } -> if not scope.current[name] then freevars[name] = true end
      end
   end

   walk.block(cfg)(term)
   return freevars
end

  local cfg = { expr  = { pred = "Id"  },
             stat  = { pred = "Local" },
             block = { } }
   [...]
   function cfg.stat.up(x)
      match x with
      | `Local{ vars, ... } -> scope:add(vars)
      end
   end

   -----------------------------------------------------------------------------
   -- Create a separate scope for each block, close it when leaving.
   -----------------------------------------------------------------------------
   function cfg.block.down() scope:push() end
   function cfg.block.up()   scope:pop()  end

local function fv (term)
   local freevars = { }
   local scope    = scope:new()
   local cfg = { expr  = { pred = { "Function", "Id" } },
                 stat  = { pred = { "Forin", "Fornum", "Local", "Localrec" } } }

   -----------------------------------------------------------------------------
   -- Check identifiers; add functions parameters to newly created scope.
   -----------------------------------------------------------------------------
   function cfg.expr.down(x)
      match x with
      | `Id{ name } -> if not scope.current[name] then freevars[name] = true end
      | `Function{ params, _ } -> scope:push(); scope:add (params)
      end
   end

   -----------------------------------------------------------------------------
   -- Close the function scope opened by 'down()'.
   -----------------------------------------------------------------------------
   function cfg.expr.up(x)  
      match x with
      | `Function{ ... } -> scope:pop()
      | `Id{ ... }       -> -- pass
      end
   end

   -----------------------------------------------------------------------------
   -- Create a new scope and register loop variable[s] in it
   -----------------------------------------------------------------------------
   function cfg.stat.down(x)
      match x with
      | `Forin{ vars, ... }    -> scope:push(); scope:add(vars)
      | `Fornum{ var, ... }    -> scope:push(); scope:add{var}
      | `Localrec{ vars, ... } -> scope:add(vars)
      | `Local{ ... }          -> -- 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)
      | `Localrec{ ... }               -> -- pass
      end
   end

   -----------------------------------------------------------------------------
   -- Create a separate scope for each block, close it when leaving.
   -----------------------------------------------------------------------------
   function cfg.block.down() scope:push() end
   function cfg.block.up()   scope:pop()  end

   walk.block(cfg)(term)
   return freevars
end

  local cfg  = { expr  = { pred = { "Function", "Id" } },
                 stat = { pred = { "Forin", "Fornum", "Local",
                                "Localrec", "Repeat" } },
                 block = { } }

   [...]

   -----------------------------------------------------------------------------
   -- Create a new scope and register loop variable[s] in it
   -----------------------------------------------------------------------------
   function cfg.stat.down(x)
      match x with
      | `Forin{ vars, ... }    -> scope:push(); scope:add(vars)
      | `Fornum{ var, ... }    -> scope:push(); scope:add{var}
      | `Localrec{ vars, ... } -> scope:add(vars)
      | `Local{ ... }          -> -- pass
      | `Repeat{ block, cond } -> -- 'cond' is in the scope of 'block'
         scope:push()
         for s in values (block) do walk.stat(cfg)(s) end -- no new scope
         walk.expr(cfg)(cond)
         scope:pop()
         return 'break' -- No automatic walking of subparts 'cond' and 'body'
      end
   end

function expr.Stat (fs, ast, v)
   local save_nactvar = fs.nactvar
   local dest_reg = fs.freereg
   local save_actvar = { }
   local last_unreg_var = #fs.actvar
   if last_unreg_var > 0 or fs.actvar[0] then
      for i = fs.nactvar, last_unreg_var do
         save_actvar[i] = fs.actvar[i]
      end
   end
   fs.nactvar = fs.freereg
   enterblock (fs, { }, false)
   chunk (fs, ast[1])
   expr.expr (fs, ast[2], v)
   luaK:exp2nextreg (fs, v)
   leaveblock (fs)
   luaK:exp2reg (fs, v, dest_reg)
   fs.freereg = fs.freereg+1
   fs.nactvar = save_nactvar
   for i, j in pairs(save_actvar) do fs.actvar[i] = j end
end

metalua

TreeQuery: a DSL for syntax tree exploration

Source code

Part I: selecting nodes in an AST

Queries

:filter(pred), selecting a node according to its properties

Testing the parents

Positional filtering methods

Variables and scopes

Miscelaneous predicates

Q.child() predicate transformer

Part II: Acting on selected nodes

Extracting a list with :list()

Extracting the first node with :first()

Iterating on nodes with :foreach()

(Not implemented) Mapping transformations on nodes with :map()

(Not implemented) for loop iterators

The other facet of Metalua: making IDEs smarter

Refactoring Lua with Metalua: source generation

Metalua moves to Github

Refactoring Lua code with Metalua

Statements as expressions

One more catch

shorter lambdas

Syntax experiments

xloop

xmatch

match functions

anonymous match functions

expression match

Destructuring bind

Metalua 0.4.1 (rc1)

Metalua 0.4 released

A 'simple' extension with a catch

Git repository

Pattern matching in metalua

Prerequisites

Purpose

match statement

Patterns

Litterals

Tables

Identifiers

Guards

Multi-match

Examples

Implementation hints

Code walkers

Principles

API

First example

Cuts

Advenced example: free variables listing

About Dylan

Ping

Bug again

Metalua isn't Lisp

bug fix in pattern matching

Eating my own (DSL) dogfood

Lazy streams

Type checking, reloaded

Release 0.3

Blog creation