src/samples/synth.mlua

   1 require 'strict'
   2
   3 -{ extension 'match' }
   4
   5 synth = { }
   6 synth.__index = synth
   7
   8 --------------------------------------------------------------------------------
   9 -- Instanciate a new AST->source synthetizer
  10 --------------------------------------------------------------------------------
  11 function synth.new ()
  12    local self = {
  13       _acc           = { },  -- Accumulates pieces of source as strings
  14       current_indent = 0,    -- Current level of line indentation
  15       indent_step    = "   " -- Indentation symbol, normally spaces or '\t'
  16    }
  17    return setmetatable (self, synth)
  18 end
  19
  20 --------------------------------------------------------------------------------
  21 -- Run a synthetizer on the `ast' arg and return the source as a string.
  22 -- Can also be used as a static method `synth.run (ast)'; in this case,
  23 -- a temporary synthetizer is instanciated on the fly.
  24 --------------------------------------------------------------------------------
  25 function synth:run (ast)
  26    if not ast then
  27       self, ast = synth.new(), self
  28    end
  29    self._acc = { }
  30    self:node (ast)
  31    return table.concat (self._acc)
  32 end
  33
  34 --------------------------------------------------------------------------------
  35 -- Accumulate a piece of source file in the synthetizer.
  36 --------------------------------------------------------------------------------
  37 function synth:acc (x)
  38    if x then table.insert (self._acc, x) end
  39 end
  40
  41 --------------------------------------------------------------------------------
  42 -- Accumulate an indented newline.
  43 -- Jumps an extra line if indentation is 0, so that
  44 -- toplevel definitions are separated by an extra empty line.
  45 --------------------------------------------------------------------------------
  46 function synth:nl ()
  47    if self.current_indent == 0 then self:acc "\n"  end
  48    self:acc ("\n" .. self.indent_step:rep (self.current_indent))
  49 end
  50
  51 --------------------------------------------------------------------------------
  52 -- Increase indentation and accumulate a new line.
  53 --------------------------------------------------------------------------------
  54 function synth:nlindent ()
  55    self.current_indent = self.current_indent + 1
  56    self:nl ()
  57 end
  58
  59 --------------------------------------------------------------------------------
  60 -- Decrease indentation and accumulate a new line.
  61 --------------------------------------------------------------------------------
  62 function synth:nldedent ()
  63    self.current_indent = self.current_indent - 1
  64    self:acc ("\n" .. self.indent_step:rep (self.current_indent))
  65 end
  66
  67 --------------------------------------------------------------------------------
  68 -- Keywords, which are illegal as identifiers.
  69 --------------------------------------------------------------------------------
  70 local keywords = table.transpose {
  71    "and",    "break",   "do",    "else",   "elseif",
  72    "end",    "false",   "for",   "function", "if",
  73    "in",     "local",   "nil",   "not",    "or",
  74    "repeat", "return",  "then",  "true",   "until",
  75    "while" }
  76
  77 --------------------------------------------------------------------------------
  78 -- Return true iff string `id' is a legal identifier name.
  79 --------------------------------------------------------------------------------
  80 local function is_ident (id)
  81    return id:strmatch "^[%a_][%w_]*$" and not keywords[id]
  82 end
  83
  84 --------------------------------------------------------------------------------
  85 -- Return true iff ast represents a legal function name for
  86 -- syntax sugar ``function foo.bar.gnat() ... end'':
  87 -- a series of nested string indexes, with an identifier as
  88 -- the innermost node.
  89 --------------------------------------------------------------------------------
  90 local function is_idx_stack (ast)
  91    match ast with
  92    | `Id{ _ }                     -> return true
  93    | `Index{ left, `String{ _ } } -> return is_idx_stack (left)
  94    | _                            -> return false
  95    end
  96 end
  97
  98 --------------------------------------------------------------------------------
  99 -- Operator precedences, in increasing order.
 100 -- This is not directly used, it's used to generate op_prec below.
 101 --------------------------------------------------------------------------------
 102 local op_preprec = {
 103    { "or", "and" },
 104    { "lt", "le", "eq", "ne" },
 105    { "concat" },
 106    { "add", "sub" },
 107    { "mul", "div", "mod" },
 108    { "unary", "not", "len" },
 109    { "pow" },
 110    { "index" } }
 111
 112 --------------------------------------------------------------------------------
 113 -- operator --> precedence table, generated from op_preprec.
 114 --------------------------------------------------------------------------------
 115 local op_prec = { }
 116
 117 for prec, ops in ipairs (op_preprec) do
 118    for op in ivalues (ops) do
 119       op_prec[op] = prec
 120    end
 121 end
 122
 123 --------------------------------------------------------------------------------
 124 -- operator --> source representation.
 125 --------------------------------------------------------------------------------
 126 local op_symbol = {
 127    add    = " + ",   sub     = " - ",   mul     = " * ",
 128    div    = " / ",   mod     = " % ",   pow     = " ^ ",
 129    concat = " .. ",  eq      = " == ",  ne      = " ~= ",
 130    lt     = " < ",   le      = " <= ",  ["and"] = " and ",
 131    ["or"] = " or ",  ["not"] = "not ",  len     = "# " }
 132
 133 --------------------------------------------------------------------------------
 134 -- Accumulate the source representation of AST `node' in
 135 -- the synthetizer. Most of the work is done by delegating to
 136 -- the method having the name of the AST tag.
 137 -- If something can't be converted to normal sources, it's
 138 -- instead dumped as a `-{ ... }' splice in the source accumulator.
 139 --------------------------------------------------------------------------------
 140 function synth:node (node)
 141    assert (self~=synth and self._acc)
 142    if not node.tag then -- tagless block.
 143       self:list (node, self.nl)
 144    else
 145       local f = synth[node.tag]
 146       if type (f) == "function" then -- Delegate to tag method.
 147          f (self, node, unpack (node))
 148       elseif type (f) == "string" then -- tag string.
 149          self:acc (f)
 150       else -- No appropriate method, fall back to splice dumping.
 151            -- This cannot happen in a plain Lua AST.
 152          self:acc " -{ "
 153          self:acc (table.tostring (node, "nohash"), 80)
 154          self:acc " }"
 155       end
 156    end
 157 end
 158
 159 --------------------------------------------------------------------------------
 160 -- Convert every node in the AST list `list' passed as 1st arg.
 161 -- `sep' is an optional separator to be accumulated between each list element,
 162 -- it can be a string or a synth method.
 163 -- `start' is an optional number (default == 1), indicating which is the
 164 -- first element of list to be converted, so that we can skip the begining
 165 -- of a list.
 166 --------------------------------------------------------------------------------
 167 function synth:list (list, sep, start)
 168    for i = start or 1, # list do
 169       self:node (list[i])
 170       if list[i + 1] then
 171          if not sep then
 172          elseif type (sep) == "function" then sep (self)
 173          elseif type (sep) == "string"   then self:acc (sep)
 174          else   error "Invalid list separator" end
 175       end
 176    end
 177 end
 178
 179 --------------------------------------------------------------------------------
 180 --
 181 -- Tag methods.
 182 -- ------------
 183 --
 184 -- Specific AST node dumping methods, associated to their node kinds
 185 -- by their name, which is the corresponding AST tag.
 186 -- synth:node() is in charge of delegating a node's treatment to the
 187 -- appropriate tag method.
 188 --
 189 -- Such tag methods are called with the AST node as 1st arg.
 190 -- As a convenience, the n node's children are passed as args #2 ... n+1.
 191 --
 192 -- There are several things that could be refactored into common subroutines
 193 -- here: statement blocks dumping, function dumping...
 194 -- However, given their small size and linear execution
 195 -- (they basically perform series of :acc(), :node(), :list(),
 196 -- :nl(), :nlindent() and :nldedent() calls), it seems more readable
 197 -- to avoid multiplication of such tiny functions.
 198 --
 199 -- To make sense out of these, you need to know metalua's AST syntax, as
 200 -- found in the reference manual or in metalua/doc/ast.txt.
 201 --
 202 --------------------------------------------------------------------------------
 203
 204 function synth:Do (node)
 205    self:acc      "do"
 206    self:nlindent ()
 207    self:list     (node, self.nl)
 208    self:nldedent ()
 209    self:acc      "end"
 210 end
 211
 212 function synth:Set (node)
 213    match node with
 214    | `Set{ { `Index{ lhs, `String{ method } } },
 215            { `Function{ { `Id "self", ... } == params, body } } }
 216          if is_idx_stack (lhs) and is_ident (method) ->
 217       -- ``function foo:bar(...) ... end'' --
 218       self:acc      "function "
 219       self:node     (lhs)
 220       self:acc      ":"
 221       self:acc      (method)
 222       self:acc      " ("
 223       self:list     (params, ", ", 2)
 224       self:acc      ")"
 225       self:nlindent ()
 226       self:list     (body, self.nl)
 227       self:nldedent ()
 228       self:acc      "end"
 229
 230    | `Set{ { lhs }, { `Function{ params, body } } } if is_idx_stack (lhs) ->
 231       -- ``function foo(...) ... end'' --
 232       self:acc      "function "
 233       self:node     (lhs)
 234       self:acc      " ("
 235       self:list     (params, ", ")
 236       self:acc      ")"
 237       self:nlindent ()
 238       self:list    (body, self.nl)
 239       self:nldedent ()
 240       self:acc      "end"
 241
 242    | `Set{ { `Id{ lhs1name } == lhs1, ... } == lhs, rhs }
 243          if not is_ident (lhs1name) ->
 244       -- ``foo, ... = ...'' when foo is *not* a valid identifier.
 245       -- In that case, the spliced 1st variable must get parentheses,
 246       -- to be distinguished from a statement splice.
 247       -- This cannot happen in a plain Lua AST.
 248       self:acc      "("
 249       self:node     (lhs1)
 250       self:acc      ")"
 251       if lhs[2] then -- more than one lhs variable
 252          self:acc   ", "
 253          self:list  (lhs, ", ", 2)
 254       end
 255       self:acc      " = "
 256       self:list     (rhs, ", ")
 257
 258    | `Set{ lhs, rhs } ->
 259       -- ``... = ...'', no syntax sugar --
 260       self:list  (lhs, ", ")
 261       self:acc   " = "
 262       self:list  (rhs, ", ")
 263    end
 264 end
 265
 266 function synth:While (node, cond, body)
 267    self:acc      "while "
 268    self:node     (cond)
 269    self:acc      " do"
 270    self:nlindent ()
 271    self:list     (body, self.nl)
 272    self:nldedent ()
 273    self:acc      "end"
 274 end
 275
 276 function synth:Repeat (node, body, cond)
 277    self:acc      "repeat"
 278    self:nlindent ()
 279    self:list     (body, self.nl)
 280    self:nldedent ()
 281    self:acc      "until "
 282    self:node     (cond)
 283 end
 284
 285 function synth:If (node)
 286    for i = 1, #node-1, 2 do
 287       -- for each ``if/then'' and ``elseif/then'' pair --
 288       local cond, body = node[i], node[i+1]
 289       self:acc      (i==1 and "if " or "elseif ")
 290       self:node     (cond)
 291       self:acc      " then"
 292       self:nlindent ()
 293       self:list     (body, self.nl)
 294       self:nldedent ()
 295    end
 296    -- odd number of children --> last one is an `else' clause --
 297    if #node%2 == 1 then
 298       self:acc      "else"
 299       self:nlindent ()
 300       self:list     (node[#node], self.nl)
 301       self:nldedent ()
 302    end
 303    self:acc "end"
 304 end
 305
 306 function synth:Fornum (node, var, first, last)
 307    local body = node[#node]
 308    self:acc      "for "
 309    self:node     (var)
 310    self:acc      " = "
 311    self:node     (first)
 312    self:acc      ", "
 313    self:node     (last)
 314    if #node==5 then -- 5 children --> child #4 is a step increment.
 315       self:acc   ", "
 316       self:node  (node[4])
 317    end
 318    self:acc      " do"
 319    self:nlindent ()
 320    self:list     (body, self.nl)
 321    self:nldedent ()
 322    self:acc      "end"
 323 end
 324
 325 function synth:Forin (node, vars, generators, body)
 326    self:acc      "for "
 327    self:list     (vars, ", ")
 328    self:acc      " in "
 329    self:list     (generators, ", ")
 330    self:acc      " do"
 331    self:nlindent ()
 332    self:list     (body, self.nl)
 333    self:nldedent ()
 334    self:acc      "end"
 335 end
 336
 337 function synth:Local (node, lhs, rhs)
 338    self:acc     "local "
 339    self:list    (lhs, ", ")
 340    if rhs[1] then
 341       self:acc  " = "
 342       self:list (rhs, ", ")
 343    end
 344 end
 345
 346 function synth:Localrec (node, lhs, rhs)
 347    match node with
 348    | `Localrec{ { `Id{name} }, { `Function{ params, body } } }
 349          if is_ident (name) ->
 350       -- ``local function name() ... end'' --
 351       self:acc      "local function "
 352       self:acc      (name)
 353       self:acc      " ("
 354       self:list     (params, ", ")
 355       self:acc      ")"
 356       self:nlindent ()
 357       self:list     (body, self.nl)
 358       self:nldedent ()
 359       self:acc      "end"
 360
 361    | _ ->
 362       -- Other localrec are unprintable ==> splice them --
 363           -- This cannot happen in a plain Lua AST. --
 364       self:acc "-{ "
 365       self:acc (table.tostring (node, 'nohash', 80))
 366       self:acc " }"
 367    end
 368 end
 369
 370 function synth:Call (node, f)
 371    -- single string or table literal arg ==> no need for parentheses. --
 372    local parens
 373    match node with
 374    | `Call{ _, `String{_} }
 375    | `Call{ _, `Table{...}} -> parens = false
 376    | _ -> parens = true
 377    end
 378    self:node (f)
 379    self:acc  (parens and " (" or  " ")
 380    self:list (node, ", ", 2) -- skip `f'.
 381    self:acc  (parens and ")")
 382 end
 383
 384 function synth:Invoke (node, f, method)
 385    -- single string or table literal arg ==> no need for parentheses. --
 386    local parens
 387    match node with
 388    | `Invoke{ _, _, `String{_} }
 389    | `Invoke{ _, _, `Table{...}} -> parens = false
 390    | _ -> parens = true
 391    end
 392    self:node   (f)
 393    self:acc    ":"
 394    self:acc    (method[1])
 395    self:acc    (parens and " (" or  " ")
 396    self:list   (node, ", ", 3) -- Skip args #1 and #2, object and method name.
 397    self:acc    (parens and ")")
 398 end
 399
 400 function synth:Return (node)
 401    self:acc  "return "
 402    self:list (node, ", ")
 403 end
 404
 405 synth.Break = "break"
 406 synth.Nil   = "nil"
 407 synth.False = "false"
 408 synth.True  = "true"
 409 synth.Dots  = "..."
 410
 411 function synth:Number (node, n)
 412    self:acc (tostring (n))
 413 end
 414
 415 function synth:String (node, str)
 416    -- format "%q" prints '\n' in an umpractical way IMO,
 417    -- so this is fixed with the :gsub( ) call.
 418    self:acc (string.format ("%q", str):gsub ("\\\n", "\\n"))
 419 end
 420
 421 function synth:Function (node, params, body)
 422    self:acc      "function "
 423    self:acc      " ("
 424    self:list     (params, ", ")
 425    self:acc      ")"
 426    self:nlindent ()
 427    self:list     (body, self.nl)
 428    self:nldedent ()
 429    self:acc      "end"
 430 end
 431
 432 function synth:Table (node)
 433    if not node[1] then self:acc "{ }" else
 434       self:acc "{"
 435       self:nlindent ()
 436       for i, elem in ipairs (node) do
 437          match elem with
 438          | `Pair{ `String{ key }, value } if is_ident (key) ->
 439             -- ``key = value''. --
 440             self:acc  (key)
 441             self:acc  " = "
 442             self:node (value)
 443
 444          | `Pair{ key, value } ->
 445             -- ``[key] = value''. --
 446             self:acc  "["
 447             self:node (key)
 448             self:acc  "] = "
 449             self:node (value)
 450
 451          | _ ->
 452             -- ``value''. --
 453             self:node (elem)
 454          end
 455          if node [i+1] then
 456             self:acc ","
 457             self:nl  ()
 458          end
 459       end
 460       self:nldedent  ()
 461       self:acc       "}"
 462    end
 463 end
 464
 465 function synth:Op (node, op, a, b)
 466    -- Transform ``not (a == b)'' into ``a ~= b''. --
 467    match node with
 468    | `Op{ "not", `Op{ "eq", _a, _b } }
 469    | `Op{ "not", `Paren{ `Op{ "eq", _a, _b } } } ->
 470       op, a, b = "ne", _a, _b
 471    | _ ->
 472    end
 473
 474    if b then -- binary operator.
 475       local left_paren, right_paren
 476       match a with
 477       | `Op{ op_a, ...} if op_prec[op] >= op_prec[op_a] -> left_paren = true
 478       | _ -> left_paren = false
 479       end
 480
 481       match b with -- FIXME: might not work with right assoc operators ^ and ..
 482       | `Op{ op_b, ...} if op_prec[op] >= op_prec[op_b] -> right_paren = true
 483       | _ -> right_paren = false
 484       end
 485
 486       self:acc  (left_paren and "(")
 487       self:node (a)
 488       self:acc  (left_paren and ")")
 489
 490       self:acc  (op_symbol [op])
 491
 492       self:acc  (right_paren and "(")
 493       self:node (b)
 494       self:acc  (right_paren and ")")
 495
 496    else -- unary operator.
 497       local paren
 498       match a with
 499       | `Op{ op_a, ... } if op_prec[op] >= op_prec[op_a] -> paren = true
 500       | _ -> paren = false
 501       end
 502       self:acc  (op_symbol[op])
 503       self:acc  (paren and "(")
 504       self:node (a)
 505       self:acc  (paren and ")")
 506    end
 507 end
 508
 509 function synth:Paren (node, content)
 510    self:acc  "("
 511    self:node (content)
 512    self:acc  ")"
 513 end
 514
 515 function synth:Index (node, table, key)
 516    local paren_table
 517    -- Check precedence, see if parens are needed around the table --
 518    match table with
 519    | `Op{ op, ... } if op_prec[op] < op_prec.index -> paren_table = true
 520    | _ -> paren_table = false
 521    end
 522
 523    self:acc  (paren_table and "(")
 524    self:node (table)
 525    self:acc  (paren_table and ")")
 526
 527    match key with
 528    | `String{ field } if is_ident (field) ->
 529       -- ``table.key''. --
 530       self:acc "."
 531       self:acc (field)
 532    | _ ->
 533       -- ``table [key]''. --
 534       self:acc   "["
 535       self:node (key)
 536       self:acc   "]"
 537    end
 538 end
 539
 540 function synth:Id (node, name)
 541    if is_ident (name) then
 542       self:acc (name)
 543    else -- Unprintable identifier, fall back to splice representation.
 544         -- This cannot happen in a plain Lua AST.
 545       self:acc    "-{`Id "
 546       self:String (node, name)
 547       self:acc    "}"
 548    end
 549 end
 550
 551
 552 --------------------------------------------------------------------------------
 553 -- Read a file, get its AST, use synth to regenerate sources
 554 -- from that AST
 555 --------------------------------------------------------------------------------
 556 require 'mlc'
 557 local filename = (arg[2] or arg[1]) or arg[0]
 558 local ast = mlc.luafile_to_ast (filename)
 559
 560 print(synth.run(ast))