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 parameter and return the source as 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          self:acc " -{ "
 152          self:acc (table.tostring (node, "nohash"), 80)
 153          self:acc " }"
 154       end
 155    end
 156 end
 157
 158 --------------------------------------------------------------------------------
 159 -- Convert every node in the AST list `list' passed as 1st arg.
 160 -- `sep' is an optional separator to be accumulated between each list element,
 161 -- it can be a string or a synth method.
 162 -- `start' is an optional number (default == 1), indicating which is the
 163 -- first element of list to be converted, so that we can skip the begining
 164 -- of a list.
 165 --------------------------------------------------------------------------------
 166 function synth:list (list, sep, start)
 167    for i = start or 1, # list do
 168       self:node (list[i])
 169       if list[i + 1] then
 170          if not sep then
 171          elseif type (sep) == "function" then sep (self)
 172          elseif type (sep) == "string"   then self:acc (sep)
 173          else   error "Invalid list separator" end
 174       end
 175    end
 176 end
 177
 178 --------------------------------------------------------------------------------
 179 -- Specific AST node dumping methods, associated to their node kinds
 180 -- by their name, which is the corresponding AST tag.
 181 -- synth:node() is in charge of delegating a node's treatment to the
 182 -- appropriate tag method.
 183 --
 184 -- Such tag methods are called with the AST node as 1st arg.
 185 -- As a convenience, the n node's children are passed as args #2 ... n+1.
 186 --
 187 -- There are several things that could be refactored into common subroutines
 188 -- here: statement blocks dumping, function dumping...
 189 -- However, given their small size and linear execution, it seems more
 190 -- readable to avoid multiplication of such tiny functions.
 191 --------------------------------------------------------------------------------
 192
 193 function synth:Do (node)
 194    self:acc      "do"
 195    self:nlindent ()
 196    self:list     (node, self.nl)
 197    self:nldedent ()
 198    self:acc      "end"
 199 end
 200
 201 function synth:Set (node)
 202    match node with
 203    | `Set{ { `Index{ lhs, `String{ method } } },
 204            { `Function{ { `Id "self", ... } == params, body } } }
 205       if is_idx_stack (lhs) and is_ident (method) ->
 206
 207       -- ``function foo:bar(...) ... end'' --
 208       self:acc      "function "
 209       self:node     (lhs)
 210       self:acc      ":"
 211       self:acc      (method)
 212       self:acc      " ("
 213       self:list     (params, ", ", 2)
 214       self:acc      ")"
 215       self:nlindent ()
 216       self:list     (body, self.nl)
 217       self:nldedent ()
 218       self:acc      "end"
 219
 220    | `Set{ { lhs }, { `Function{ params, body } } } if is_idx_stack (lhs) ->
 221
 222    -- ``function foo(...) ... end'' --
 223       self:acc      "function "
 224       self:node     (lhs)
 225       self:acc      " ("
 226       self:list     (params, ", ")
 227       self:acc      ")"
 228       self:nlindent ()
 229       self:list    (body, self.nl)
 230       self:nldedent ()
 231       self:acc      "end"
 232
 233    | `Set{ { `Id{ lhs1name } == lhs1, ... } == lhs, rhs }
 234          if not is_ident (lhs1name) ->
 235
 236       -- ``foo, ... = ...'' when foo is *not* a valid identifier.
 237       -- In that case, the spliced 1st variable must get parentheses
 238       -- to be distinguished from a statement splice.
 239       self:acc      "("
 240       self:node     (lhs1)
 241       self:acc      ")"
 242       if lhs[2] then -- more than one lhs variable
 243          self:acc   ", "
 244          self:list  (lhs, ", ", 2)
 245       end
 246       self:acc      " = "
 247       self:list     (rhs, ", ")
 248
 249    | `Set{ lhs, rhs } ->
 250
 251       -- ``... = ...'', no syntax sugar --
 252       self:list  (lhs, ", ")
 253       self:acc   " = "
 254       self:list  (rhs, ", ")
 255    end
 256 end
 257
 258 function synth:While (node, cond, body)
 259    self:acc      "while "
 260    self:node     (cond)
 261    self:acc      " do"
 262    self:nlindent ()
 263    self:list     (body, self.nl)
 264    self:nldedent ()
 265    self:acc      "end"
 266 end
 267
 268 function synth:Repeat (node, body, cond)
 269    self:acc      "repeat"
 270    self:nlindent ()
 271    self:list     (body, self.nl)
 272    self:nldedent ()
 273    self:acc      "until "
 274    self:node     (cond)
 275 end
 276
 277 function synth:If (node)
 278    for i = 1, #node-1, 2 do
 279       -- for each ``if/then'' and ``elseif/then'' pair --
 280       local cond, body = node[i], node[i+1]
 281       self:acc      (i==1 and "if " or "elseif ")
 282       self:node     (cond)
 283       self:acc      " then"
 284       self:nlindent ()
 285       self:list     (body, self.nl)
 286       self:nldedent ()
 287    end
 288    -- odd number of children --> last one is an `else' clause --
 289    if #node%2 == 1 then
 290       self:acc      "else"
 291       self:nlindent ()
 292       self:list     (node[#node], self.nl)
 293       self:nldedent ()
 294    end
 295    self:acc "end"
 296 end
 297
 298 function synth:Fornum (node, var, first, last)
 299    local body = node[#node]
 300    self:acc      "for "
 301    self:node     (var)
 302    self:acc      " = "
 303    self:node     (first)
 304    self:acc      ", "
 305    self:node     (last)
 306    if #node==5 then -- 5 children --> child #4 is a step increment.
 307       self:acc   ", "
 308       self:node  (node[4])
 309    end
 310    self:acc      " do"
 311    self:nlindent ()
 312    self:list     (body, self.nl)
 313    self:nldedent ()
 314    self:acc      "end"
 315 end
 316
 317 function synth:Forin (node, vars, generators, body)
 318    self:acc      "for "
 319    self:list     (vars, ", ")
 320    self:acc      " in "
 321    self:list     (generators, ", ")
 322    self:acc      " do"
 323    self:nlindent ()
 324    self:list     (body, self.nl)
 325    self:nldedent ()
 326    self:acc      "end"
 327 end
 328
 329 function synth:Local (node, lhs, rhs)
 330    self:acc     "local "
 331    self:list    (lhs, ", ")
 332    if rhs[1] then
 333       self:acc  " = "
 334       self:list (rhs, ", ")
 335    end
 336 end
 337
 338 function synth:Localrec (node, lhs, rhs)
 339    match node with
 340    | `Localrec{ { `Id{name} }, { `Function{ params, body } } }
 341          if is_ident (name) ->
 342       -- ``local function name() ... end'' --
 343       self:acc      "local function "
 344       self:acc      (name)
 345       self:acc      " ("
 346       self:list     (params, ", ")
 347       self:acc      ")"
 348       self:nlindent ()
 349       self:list     (body, self.nl)
 350       self:nldedent ()
 351       self:acc      "end"
 352
 353    | _ ->
 354       -- Other localrec are unprintable ==> splice them --
 355       self:acc "-{ "
 356       self:acc (table.tostring (node, 'nohash', 80))
 357       self:acc " }"
 358    end
 359 end
 360
 361 function synth:Call (node, f)
 362    -- single string or table literal arg ==> no need for parentheses. --
 363    local parens
 364    match node with
 365    | `Call{ _, `String{_} }
 366    | `Call{ _, `Table{...}} -> parens = false
 367    | _ -> parens = true
 368    end
 369    self:node (f)
 370    self:acc  (parens and " (" or  " ")
 371    self:list (node, ", ", 2)
 372    self:acc  (parens and ")")
 373 end
 374
 375 function synth:Invoke (node, f, method)
 376    -- single string or table literal arg ==> no need for parentheses. --
 377    local parens
 378    match node with
 379    | `Invoke{ _, _, `String{_} }
 380    | `Invoke{ _, _, `Table{...}} -> parens = false
 381    | _ -> parens = true
 382    end
 383    self:node   (f)
 384    self:acc    ":"
 385    self:acc    (method[1])
 386    self:acc    (parens and " (" or  " ")
 387    self:list   (node, ", ", 3) -- skip object and method name
 388    self:acc    (parens and ")")
 389 end
 390
 391 function synth:Return (node)
 392    self:acc  "return "
 393    self:list (node, ", ")
 394 end
 395
 396 synth.Break = "break"
 397 synth.Nil   = "nil"
 398 synth.False = "false"
 399 synth.True  = "true"
 400 synth.Dots  = "..."
 401
 402 function synth:Number (node, n)
 403    self:acc (tostring (n))
 404 end
 405
 406 function synth:String (node, str)
 407    -- format "%q" prints '\n' in an umpractical way IMO,
 408    -- so this is fixed with the :gsub( ) call.
 409    self:acc (string.format ("%q", str):gsub ("\\\n", "\\n"))
 410 end
 411
 412 function synth:Function (node, params, body)
 413    self:acc      "function "
 414    self:acc      " ("
 415    self:list     (params, ", ")
 416    self:acc      ")"
 417    self:nlindent ()
 418    self:list     (body, self.nl)
 419    self:nldedent ()
 420    self:acc      "end"
 421 end
 422
 423 function synth:Table (node)
 424    if not node[1] then self:acc "{ }" else
 425       self:acc "{"
 426       self:nlindent ()
 427       for i, elem in ipairs (node) do
 428          match elem with
 429          | `Pair{ `String{ key }, value } if is_ident (key) ->
 430             -- ``key = value''. --
 431             self:acc  (key)
 432             self:acc  " = "
 433             self:node (value)
 434
 435          | `Pair{ key, value } ->
 436             -- ``[key] = value''. --
 437             self:acc  "["
 438             self:node (key)
 439             self:acc  "] = "
 440             self:node (value)
 441
 442          | _ ->
 443             -- ``value''. --
 444             self:node (elem)
 445          end
 446          if node [i+1] then
 447             self:acc ","
 448             self:nl  ()
 449          end
 450       end
 451       self:nldedent  ()
 452       self:acc       "}"
 453    end
 454 end
 455
 456 function synth:Op (node, op, a, b)
 457    -- Transform ``not (a == b)'' into ``a ~= b''. --
 458    match node with
 459    | `Op{ "not", `Op{ "eq", _a, _b } }
 460    | `Op{ "not", `Paren{ `Op{ "eq", _a, _b } } } ->
 461       op, a, b = "ne", _a, _b
 462    | _ ->
 463    end
 464
 465    if b then -- binary operator.
 466       local left_paren, right_paren
 467       match a with
 468       | `Op{ op_a, ...} if op_prec[op] >= op_prec[op_a] -> left_paren = true
 469       | _ -> left_paren = false
 470       end
 471
 472       match b with -- FIXME: might not work with right assoc operators ^ and ..
 473       | `Op{ op_b, ...} if op_prec[op] >= op_prec[op_b] -> right_paren = true
 474       | _ -> right_paren = false
 475       end
 476
 477       self:acc  (left_paren and "(")
 478       self:node (a)
 479       self:acc  (left_paren and ")")
 480
 481       self:acc  (op_symbol [op])
 482
 483       self:acc  (right_paren and "(")
 484       self:node (b)
 485       self:acc  (right_paren and ")")
 486
 487    else -- unary operator.
 488       local paren
 489       match a with
 490       | `Op{ op_a, ... } if op_prec[op] >= op_prec[op_a] -> paren = true
 491       | _ -> paren = false
 492       end
 493       self:acc  (op_symbol[op])
 494       self:acc  (paren and "(")
 495       self:node (a)
 496       self:acc  (paren and ")")
 497    end
 498 end
 499
 500 function synth:Paren (node, content)
 501    self:acc  "("
 502    self:node (content)
 503    self:acc  ")"
 504 end
 505
 506 function synth:Index (node, table, key)
 507    local paren_table
 508    -- Check precedence, see if parens are needed around the table --
 509    match table with
 510    | `Op{ op, ... } if op_prec[op] < op_prec.index -> paren_table = true
 511    | _ -> paren_table = false
 512    end
 513
 514    self:acc  (paren_table and "(")
 515    self:node (table)
 516    self:acc  (paren_table and ")")
 517
 518    match key with
 519    | `String{ field } if is_ident (field) ->
 520       -- ``table.key''. --
 521       self:acc "."
 522       self:acc (field)
 523    | _ ->
 524       -- ``table [key]''. --
 525       self:acc   "["
 526       self:node (key)
 527       self:acc   "]"
 528    end
 529 end
 530
 531 function synth:Id (node, name)
 532    if is_ident (name) then
 533       self:acc (name)
 534    else -- unprintable identifier, fall back to splice representation
 535       self:acc    "-{`Id "
 536       self:String (node, name)
 537       self:acc    "}"
 538    end
 539 end
 540
 541
 542 --------------------------------------------------------------------------------
 543 -- Read a file, get its AST, use synth to regenerate sources
 544 -- from that AST
 545 --------------------------------------------------------------------------------
 546 require 'mlc'
 547 local filename = (arg[2] or arg[1]) or arg[0]
 548 local ast = mlc.luafile_to_ast (filename)
 549
 550 print(synth.run(ast))