local module = {}
setmetatable(module, {__index=_G})
setfenv(1, module)


local Grammar = {}

function module.createGrammar(nonterminals, triggers)
  local self = {
    nonterminals = nonterminals,
    triggers = triggers,
    context = {},
  }
  setmetatable(self, {__index=Grammar})
  return self
end


function Grammar.pushContext(self)
  local newContext = {}
  setmetatable(newContext, {__index=self.context})
  self.context = newContext
end
function Grammar.popContext(self)
  local mt = getmetatable(self.context)
  local oldContext = (mt and mt.__index) or {}
  self.context = oldContext
end


function Grammar.expandSymbol(self, sequence, index, expansion)
  table.remove(sequence, index)
  for i=1,#expansion do
    table.insert(sequence, index+i-1, expansion[i])
  end
end


function Grammar.expandSequence(self, sequence, n)
  local i = 1
  while i <= #sequence do
    local choices = self.nonterminals[sequence[i]] or self.context[sequence[i]]
    if choices then
      local trigger = self.triggers[sequence[i]]
      if trigger then trigger(self) end
      if #choices == 1 then
        self:expandSymbol(sequence, i, choices[1])
        return true, 0
      else
        local choice = choices[1 + (n % #choices)]
        self:expandSymbol(sequence, i, choice)
        return true, 1
      end
    else
      i = i+1
    end
  end
  return false, 0
end


function Grammar.expand(self, genome, geneIndex, maxLoops)
  geneIndex = 0
  maxLoops = maxLoops or 2
  local sequence = { '<start>' }
  local count = 0
  local continue = true
  while continue do
    local gene
    if (count > maxLoops * #genome) then
      gene = 0
    else
      gene = genome[1 + (geneIndex % #genome)]
    end
    local increment
    continue, increment = self:expandSequence(sequence, gene)
    if not continue then break end
    geneIndex = geneIndex+increment
    count = count + 1
  end
  local result = ''
  for _, s in ipairs(sequence) do
    result = result .. s
  end
  return result
end


return module