src/lib/metalua/ast_to_string.mlua

   1 -{ extension 'match' }
   2
   3 local M = { }
   4 M.__index = M
   5
   6 ast_to_string = |x| M.run(x)
   7
   8 --------------------------------------------------------------------------------
   9 -- Instanciate a new AST->source synthetizer
  10 --------------------------------------------------------------------------------
  11 function M.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, M)
  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 `M.run (ast)'; in this case,
  23 -- a temporary Metizer is instanciated on the fly.
  24 --------------------------------------------------------------------------------
  25 function M:run (ast)
  26    if not ast then
  27       self, ast = M.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 M: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 M: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 M: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 M: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 M:node (node)
 141    assert (self~=M and self._acc)
 142    if not node.tag then -- tagless block.
 143       self:list (node, self.nl)
 144    else
 145       local f = M[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 M: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 M: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 M: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 M: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 M: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 M: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 M: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 M: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 M:Local (node, lhs, rhs)
 338    if next (lhs) then
 339       self:acc     "local "
 340       self:list    (lhs, ", ")
 341       if rhs[1] then
 342          self:acc  " = "
 343          self:list (rhs, ", ")
 344       end
 345    else -- Can't create a local statement with 0 variables in plain Lua
 346       self:acc (table.tostring (node, 'nohash', 80))
 347    end
 348 end
 349
 350 function M:Localrec (node, lhs, rhs)
 351    match node with
 352    | `Localrec{ { `Id{name} }, { `Function{ params, body } } }
 353          if is_ident (name) ->
 354       -- ``local function name() ... end'' --
 355       self:acc      "local function "
 356       self:acc      (name)
 357       self:acc      " ("
 358       self:list     (params, ", ")
 359       self:acc      ")"
 360       self:nlindent ()
 361       self:list     (body, self.nl)
 362       self:nldedent ()
 363       self:acc      "end"
 364
 365    | _ ->
 366       -- Other localrec are unprintable ==> splice them --
 367           -- This cannot happen in a plain Lua AST. --
 368       self:acc "-{ "
 369       self:acc (table.tostring (node, 'nohash', 80))
 370       self:acc " }"
 371    end
 372 end
 373
 374 function M:Call (node, f)
 375    -- single string or table literal arg ==> no need for parentheses. --
 376    local parens
 377    match node with
 378    | `Call{ _, `String{_} }
 379    | `Call{ _, `Table{...}} -> parens = false
 380    | _ -> parens = true
 381    end
 382    self:node (f)
 383    self:acc  (parens and " (" or  " ")
 384    self:list (node, ", ", 2) -- skip `f'.
 385    self:acc  (parens and ")")
 386 end
 387
 388 function M:Invoke (node, f, method)
 389    -- single string or table literal arg ==> no need for parentheses. --
 390    local parens
 391    match node with
 392    | `Invoke{ _, _, `String{_} }
 393    | `Invoke{ _, _, `Table{...}} -> parens = false
 394    | _ -> parens = true
 395    end
 396    self:node   (f)
 397    self:acc    ":"
 398    self:acc    (method[1])
 399    self:acc    (parens and " (" or  " ")
 400    self:list   (node, ", ", 3) -- Skip args #1 and #2, object and method name.
 401    self:acc    (parens and ")")
 402 end
 403
 404 function M:Return (node)
 405    self:acc  "return "
 406    self:list (node, ", ")
 407 end
 408
 409 M.Break = "break"
 410 M.Nil   = "nil"
 411 M.False = "false"
 412 M.True  = "true"
 413 M.Dots  = "..."
 414
 415 function M:Number (node, n)
 416    self:acc (tostring (n))
 417 end
 418
 419 function M:String (node, str)
 420    -- format "%q" prints '\n' in an umpractical way IMO,
 421    -- so this is fixed with the :gsub( ) call.
 422    self:acc (string.format ("%q", str):gsub ("\\\n", "\\n"))
 423 end
 424
 425 function M:Function (node, params, body)
 426    self:acc      "function ("
 427    self:list     (params, ", ")
 428    self:acc      ")"
 429    self:nlindent ()
 430    self:list     (body, self.nl)
 431    self:nldedent ()
 432    self:acc      "end"
 433 end
 434
 435 function M:Table (node)
 436    if not node[1] then self:acc "{ }" else
 437       self:acc "{"
 438       if #node > 1 then self:nlindent () else self:acc " " end
 439       for i, elem in ipairs (node) do
 440          match elem with
 441          | `Pair{ `String{ key }, value } if is_ident (key) ->
 442             -- ``key = value''. --
 443             self:acc  (key)
 444             self:acc  " = "
 445             self:node (value)
 446
 447          | `Pair{ key, value } ->
 448             -- ``[key] = value''. --
 449             self:acc  "["
 450             self:node (key)
 451             self:acc  "] = "
 452             self:node (value)
 453
 454          | _ ->
 455             -- ``value''. --
 456             self:node (elem)
 457          end
 458          if node [i+1] then
 459             self:acc ","
 460             self:nl  ()
 461          end
 462       end
 463       if #node > 1 then self:nldedent () else self:acc " " end
 464       self:acc       "}"
 465    end
 466 end
 467
 468 function M:Op (node, op, a, b)
 469    -- Transform ``not (a == b)'' into ``a ~= b''. --
 470    match node with
 471    | `Op{ "not", `Op{ "eq", _a, _b } }
 472    | `Op{ "not", `Paren{ `Op{ "eq", _a, _b } } } ->
 473       op, a, b = "ne", _a, _b
 474    | _ ->
 475    end
 476
 477    if b then -- binary operator.
 478       local left_paren, right_paren
 479       match a with
 480       | `Op{ op_a, ...} if op_prec[op] >= op_prec[op_a] -> left_paren = true
 481       | _ -> left_paren = false
 482       end
 483
 484       match b with -- FIXME: might not work with right assoc operators ^ and ..
 485       | `Op{ op_b, ...} if op_prec[op] >= op_prec[op_b] -> right_paren = true
 486       | _ -> right_paren = false
 487       end
 488
 489       self:acc  (left_paren and "(")
 490       self:node (a)
 491       self:acc  (left_paren and ")")
 492
 493       self:acc  (op_symbol [op])
 494
 495       self:acc  (right_paren and "(")
 496       self:node (b)
 497       self:acc  (right_paren and ")")
 498
 499    else -- unary operator.
 500       local paren
 501       match a with
 502       | `Op{ op_a, ... } if op_prec[op] >= op_prec[op_a] -> paren = true
 503       | _ -> paren = false
 504       end
 505       self:acc  (op_symbol[op])
 506       self:acc  (paren and "(")
 507       self:node (a)
 508       self:acc  (paren and ")")
 509    end
 510 end
 511
 512 function M:Paren (node, content)
 513    self:acc  "("
 514    self:node (content)
 515    self:acc  ")"
 516 end
 517
 518 function M:Index (node, table, key)
 519    local paren_table
 520    -- Check precedence, see if parens are needed around the table --
 521    match table with
 522    | `Op{ op, ... } if op_prec[op] < op_prec.index -> paren_table = true
 523    | _ -> paren_table = false
 524    end
 525
 526    self:acc  (paren_table and "(")
 527    self:node (table)
 528    self:acc  (paren_table and ")")
 529
 530    match key with
 531    | `String{ field } if is_ident (field) ->
 532       -- ``table.key''. --
 533       self:acc "."
 534       self:acc (field)
 535    | _ ->
 536       -- ``table [key]''. --
 537       self:acc   "["
 538       self:node (key)
 539       self:acc   "]"
 540    end
 541 end
 542
 543 function M:Id (node, name)
 544    if is_ident (name) then
 545       self:acc (name)
 546    else -- Unprintable identifier, fall back to splice representation.
 547         -- This cannot happen in a plain Lua AST.
 548       self:acc    "-{`Id "
 549       self:String (node, name)
 550       self:acc    "}"
 551    end
 552 end
 553