#!/usr/bin/luajit

--[[ Simple rope macro system for Lua.

This solves the problem where Lua strings are immutable, but a loop
like this takes O(N²) time:

    s = ''
    for i = 1, N do s = s .. 'x' end

ROPEs, from Cedar, support constant-time concatenation and
logarithmic-time indexing; a ROPE is either a (car, cdr) pair
or a leafnode containing some bytes.  (In Cedar it might also
refer to part of a file on disk.)

This class is slightly different: it doesn’t support indexing, but it
supports constant-time concatenation and linear-time conversion to a
flat string, and it additionally has “variable” and “environment” node
types, amounting to a very simple macro system.  Environment nodes
define variables (as strings or macropes) which variable nodes beneath
them will refer to.  A convenient syntax is provided for constructing
environment nodes by calling a macrope as a function on a table
argument.

As a simple example:

    > macrope = require 'macrope'
    > v = macrope.var 'name'
    > s = v .. ' is the best friend of ' .. v
    > = s { name='Bob' }
    Bob is the best friend of Bob

Or we can build up a 32-mebibyte string by concatenation:

    > x = macrope.macrope 'x'
    > for i = 1, 25 do x = x .. x end
    > =#tostring(x)
    33554432

The first two lines execute instantaneously; the third line takes
about 30–40 seconds on my laptop.  No attempt is made to cache the
results.

You can fix the example code above with macrope as follows:

    s = macrope.macrope ''
    for i = 1, N do s = s .. 'x' end
    s = tostring(s)

Now it’s O(N) instead of O(N²), though the crossover point where
it’s faster is around 10k (50 milliseconds on my laptop).

--]]

local catmeta, envmeta, varmeta, constmeta, const, macrope

local function meta()
   return {
      __index = {is_macrope = true},

      __concat = function(car, cdr)
         return setmetatable({car=macrope(car), cdr=macrope(cdr)}, catmeta)
      end,

      __call = function(self, vars)
         local nvars = {}
         for k, v in pairs(vars) do nvars[k] = macrope(v) end
         return setmetatable({vars=nvars, child=self}, envmeta)
      end,

      __tostring = function(self)
         -- Use an explicit stack to avoid stack overflow.
         -- Unfortunately this has a time penalty of about 2.5×
         -- in the worst case.
         local items, stack, env = {}, {}, {}
         local function put(item) table.insert(items, item) end

         self:visit(put, stack, env)

         while #stack > 0 do
            local item = table.remove(stack)
            item(put, stack, env)
         end

         return table.concat(items)
      end,
   }
end

catmeta = meta()
function catmeta.__index.visit(self, put, stack, env)
   table.insert(stack, function(...) self.cdr:visit(...) end)
   return self.car:visit(put, stack, env)
end

envmeta = meta()
function envmeta.__index.visit(self, put, stack, env)
   local saved = {}
   for k, v in pairs(self.vars) do
      saved[k] = env[k]
      env[k] = v
   end

   table.insert(stack, function(put, stack, env)
                   for k in pairs(self.vars) do env[k] = saved[k] end
   end)
   return self.child:visit(put, stack, env)
end

varmeta = meta()
function varmeta.__index.visit(self, put, stack, env)
   local val = env[self.name]
   if val == nil then error("name not found: " .. self.name) end
   return val:visit(put, stack, env)
end

local function var(name)
   return setmetatable({name=name}, varmeta)
end

constmeta = meta()
function constmeta.__index.visit(self, put, stack, env)
   put(self.value)
end

const = function(value)
   return setmetatable({value=value}, constmeta)
end

macrope = function(thing)
   if type(thing) == 'string' then return const(thing) end
   if type(thing) == 'number' then return const(tostring(thing)) end
   if thing.is_macrope then return thing end
   -- XXX maybe try to invoke tostring on it?
   error("not a macrope or string: " .. thing)
end

return { macrope = macrope, var = var }