// TODO:
// * eventually impl. JumpTable, Interleave

ometa NullOptimization {
  setHelped = !(this._didSomething = true),
  helped    = ?this._didSomething,
  trans     = [:t ?(this[t] != undefined) apply(t):ans] -> ans,
  optimize  = trans:x helped                            -> x,

  App        :rule anything*:args          -> ['App', rule].concat(args),
  Act        :expr                         -> ['Act', expr],
  Ans        :expr                         -> ['Ans', expr],
  Pred       :expr                         -> ['Pred', expr],
  Or         trans*:xs                     -> ['Or'].concat(xs),
  XOr        trans*:xs                     -> ['XOr'].concat(xs),
  And        trans*:xs                     -> ['And'].concat(xs),
  Opt        trans:x                       -> ['Opt',  x],
  Many       trans:x                       -> ['Many',  x],
  Many1      trans:x                       -> ['Many1', x],
  Set        :n trans:v                    -> ['Set', n, v],
  Not        trans:x                       -> ['Not',       x],
  Lookahead  trans:x                       -> ['Lookahead', x],
  Form       trans:x                       -> ['Form',      x],
  ConsBy     trans:x                       -> ['ConsBy',    x],
  IdxConsBy  trans:x                       -> ['IdxConsBy', x],
  JumpTable  ([:c trans:e] -> [c, e])*:ces -> ['JumpTable'].concat(ces),
  Interleave ([:m trans:p] -> [m, p])*:xs  -> ['Interleave'].concat(xs),
  Rule       :name :ls trans:body          -> ['Rule', name, ls, body]
}
NullOptimization.initialize = function() { this._didSomething = false }

ometa AssociativeOptimization <: NullOptimization {
  And trans:x end           setHelped -> x,
  And transInside('And'):xs           -> ['And'].concat(xs),
  Or  trans:x end           setHelped -> x,
  Or  transInside('Or'):xs            -> ['Or'].concat(xs),
  XOr trans:x end           setHelped -> x,
  XOr transInside('XOr'):xs           -> ['XOr'].concat(xs),

  transInside :t = [exactly(t) transInside(t):xs] transInside(t):ys setHelped -> xs.concat(ys)
                 | trans:x                        transInside(t):xs           -> [x].concat(xs)
                 |                                                            -> []
}

ometa OMetaOptimizer {
  optimizeGrammar = ['Grammar' :n :sn optimizeRule*:rs]          -> ['Grammar', n, sn].concat(rs),
  optimizeRule    = :r (AssociativeOptimization.optimize(r):r)*  -> r
}

ometa BCPLOMetaParser <: Parser {
  fromTo :x :y   = seq(x) (~seq(y) char)* seq(y), 
  space          = ^space | fromTo('//', '\n') | fromTo('/*', '*/'),
  nameFirst      = '_' | letter,
  nameRest       = nameFirst | digit,
  tsName         = firstAndRest(#nameFirst, #nameRest):xs              -> xs.join(''),
  name           = spaces tsName,
  eChar          = '\\' char:c                                         -> unescape('\\' +c)
                 | char,
  tsString       = '\'' (~'\'' eChar)*:xs '\''                         -> xs.join(''),
  characters     = '`' '`' (~('\'' '\'') eChar)*:xs '\'' '\''          -> [#App, #seq,     xs.join('').toProgramString()],
  sCharacters    = '"'     (~'"'         eChar)*:xs '"'                -> [#App, #token,   xs.join('').toProgramString()],
  string         = (('#' | '`') tsName | tsString):xs                  -> [#App, #exactly, "settypeof(" + xs.toProgramString() +
                                                                                                     ", $string)"],
  character      = '$' eChar:x                                         -> [#App, #exactly, x.charCodeAt(0).toString()],
  number         = ('-' | empty -> ''):sign digit+:ds                  -> [#App, #exactly, sign + ds.join('')],
  keyword :xs    = token(xs) ~letterOrDigit                            -> xs,
  args           = '(' listOf(#hostExpr, ','):xs ")"                   -> xs
                 | empty                                               -> [],
  application    = "^"          name:rule args:as                      -> [#App, "super",        "'" + rule + "'"].concat(as)
                 | name:grm "." name:rule args:as                      -> [#App, "foreign", grm, "'" + rule + "'"].concat(as)
                 |              name:rule args:as                      -> [#App, rule].concat(as),
  hostExpr       = "[[[" <(~``]]]'' char)*>:e ``]]]''                  -> e,
  semAction      = hostExpr:x                                          -> [#Act, x]
                 | "!"  hostExpr:x                                     -> [#Act, x],
  arrSemAction   = "->" hostExpr:x                                     -> [#Ans, x],
  semPred        = "?"  hostExpr:x                                     -> [#Pred, x],
  expr           = expr5(true):x ("|"  expr5(true))+:xs                -> [#Or,  x].concat(xs)
                 | expr5(true):x ("||" expr5(true))+:xs                -> [#XOr, x].concat(xs)
                 | expr5(false),
  expr5 :ne      = interleavePart:x ("&&" interleavePart)+:xs          -> [#Interleave, x].concat(xs)
                 | expr4(ne),
  interleavePart = "(" expr4(true):part ")"                            -> ["1", part]
                 | expr4(true):part modedIPart(part),
  modedIPart     = [#And [#Many  :part]]                               -> ["*", part]
                 | [#And [#Many1 :part]]                               -> ["+", part]
                 | [#And [#Opt   :part]]                               -> ["?", part]
                 | :part                                               -> ["1", part],
  expr4 :ne      =                expr3*:xs arrSemAction:act           -> [#And].concat(xs).concat([act])
                 | ?ne            expr3+:xs                            -> [#And].concat(xs)
                 | ?(ne == false) expr3*:xs                            -> [#And].concat(xs),
  optIter :x     = '*'                                                 -> [#Many,  x]
                 | '+'                                                 -> [#Many1, x]
                 | '?'                                                 -> [#Opt,   x]
                 | empty                                               -> x,
  optBind :x     = ':' name:n                                          -> { this.locals.push(n); [#Set, n, x] }
                 | empty                                               -> x,
  expr3          = ":" name:n                                          -> { this.locals.push(n); [#Set, n, [#App, #anything]] }
                 | (expr2:x optIter(x) | semAction):e optBind(e)
                 | semPred,
  expr2          = "~" expr2:x                                         -> [#Not,       x]
                 | "&" expr1:x                                         -> [#Lookahead, x]
                 | expr1,
  expr1          = application 
                 | ( keyword('undefined') | keyword('nil')
                   | keyword('true')      | keyword('false') ):x       -> [#App, #exactly, x]
                 | spaces (characters | sCharacters | string | character | number)
                 | "["  expr:x "]"                                     -> [#Form,      x]
                 | "<"  expr:x ">"                                     -> [#ConsBy,    x]
                 | "@<" expr:x ">"                                     -> [#IdxConsBy, x]
                 | "("  expr:x ")"                                     -> x,
  ruleName       = name
                 | spaces tsString,
  rule           = &(ruleName:n) !(this.locals = ['_ans = true'])
                     rulePart(n):x ("," rulePart(n))*:xs               -> [#Rule, n, this.locals, [#Or, x].concat(xs)],
  rulePart :rn   = ruleName:n ?(n == rn) expr4:b1 ( "=" expr:b2        -> [#And, b1, b2]
                                                  | empty              -> b1
                                                  ),
  grammar        = keyword('ometa') name:n
                     ( "<:" name | empty -> 'ometa' ):sn
                     "{" listOf(#rule, ','):rs "}"                        OMetaOptimizer.optimizeGrammar(
                                                                            [#Grammar, n, sn].concat(rs)
                                                                          )
}

// By dispatching on the head of a list, the following idiom allows translators to avoid doing a linear search.
// (Note that the "=" in a rule definition is optional, so you can give your rules an "ML feel".)
ometa BCPLOMetaTranslator {
  // TODO: super
  App        :rule   anything*:args        -> this.emitApp(rule, args),
  Ans        :expr                         -> this.emitAns(expr),
  Act        :expr                         -> this.emitAct(expr),
  Pred       :expr                         -> this.emitPred(expr),
  Or         trans*:xs                     -> this.emitOr(xs),
  XOr        trans*:xs                     -> this.emitXOr(xs),
  And        trans*:xs                     -> this.emitAnd(xs),
  Opt        trans:x                       -> this.emitOpt(x),
  Many       trans:x                       -> this.emitMany(x),
  Many1      trans:x                       -> this.emitMany1(x),
  Set        :n trans:v                    -> this.emitSet(n, v),
  Not        trans:x                       -> this.emitNot(x),
  Lookahead  trans:x                       -> this.emitLookahead(x),
  Form       trans:x                       -> this.emitForm(x),
  ConsBy     trans:x                       -> this.emitConsBy(x),
  IdxConsBy  trans:x                       -> this.emitIdxConsBy(x),
  JumpTable  jtCase*:cases                 -> this.emitJumpTable(cases),
  Interleave intPart*:xs                   -> ['this._interleave(', xs.join(','), ')']                             .join(''),
  
  Rule       :name {this.rName = name}
             locals:ls trans:body          -> this.emitRule(ls, body),
  Grammar    :name :sName
             {this.name = name}
             {this.sName = sName}
             trans*:rules                  -> this.emitGrammar(rules),
  intPart  = [:mode trans:part]            -> (mode.toProgramString()  + "," + part),
  jtCase   = [:x trans:e]                  -> [x.toProgramString(), e],
  locals   = [string+:vs]                  -> this.emitLocals(vs),
  trans    = [:t apply(t):ans]             -> ans
}

BCPLOMetaTranslator.nestWithDecls = function(decls, x) {
  return [
    '      {\n',
    '      let ', decls, '\n',
    x,
    '      }\n'
  ].join('')
}
BCPLOMetaTranslator.emitMany = function(x) {
  return this.nestWithDecls('_ans2 = vector..new()', [
    '      while true do\n',
    '      { let _old_input = this._input\n',
    x,
    '        test _ans \\= undefined then\n',
    '        { _ans2..push(_ans)\n',
    '          _old_input := this._input }\n',
    '        or\n',
    '        { _ans := _ans2..to_array()\n',
    '          this._input := _old_input\n',
    '          break } }\n'
  ].join(''))
}
BCPLOMetaTranslator.emitMany1 = function(x) {
  return [
    '      {\n',
    x,
    '      unless _ans = undefined do {\n',
    this.nestWithDecls('_ans2 = vector..new()', [
    '        _ans2..push(_ans)\n',
    '        while true do\n',
    '        { let _old_input = this._input\n',
    x,
    '          test _ans \\= undefined then\n',
    '          { _ans2..push(_ans)\n',
    '            _old_input := this._input }\n',
    '          or\n',
    '          { _ans := _ans2..to_array()\n',
    '            this._input := _old_input\n',
    '            break } }\n'
    ].join('')),
    '      }\n',
    '      }\n'
  ].join('')
}
BCPLOMetaTranslator.emitOpt = function(x) {
  return this.nestWithDecls('_old_input = this._input', [
    x,
    '      if _ans = undefined then\n',
    '      { _ans := nil\n',
    '        this._input := _old_input }\n'
  ].join(''))
}
BCPLOMetaTranslator.emitConsBy = function(x) {
  return this.nestWithDecls('_old_input = this._input', [
    x,
    '      if _ans \\= undefined then\n',
    '        _ans := this._str_from_to(_old_input, this._input)\n'
  ].join(''))
}
BCPLOMetaTranslator.emitIdxConsBy = function(x) {
  return this.nestWithDecls('_old_input = this._input', [
    x,
    '      if _ans \\= undefined then\n',
    '        _ans := this._idx_from_to(_old_input, this._input)\n'
  ].join(''))
}
BCPLOMetaTranslator.emitNot = function(x) {
  return this.nestWithDecls('_old_input = this._input', [
    x,
    '      test _ans = undefined then\n',
    '        this._input := _old_input\n',
    '      or\n',
    '        _ans := undefined\n'
  ].join(''))
}
BCPLOMetaTranslator.emitLookahead = function(x) {
  return this.nestWithDecls('_old_input = this._input', [
    x,
    '      this._input := _old_input\n'
  ].join(''))
}
BCPLOMetaTranslator.emitForm = function(x) {
  return [
    '      {\n',
    '      let _obj = this._apply(thisar, \"anything\")\n',
    '      if _obj \\= undefined /\\ typeof(_obj) = $vec do\n',
    '      { let _old_input = this._input\n',
    '        this._input := vecinputstream.constructor~(_obj, 0)\n',
    x,
    '        unless _ans = undefined do\n',
    '        { _ans := this._apply(thisar, \"end\")\n',
    '          unless _ans = undefined do\n',
    '          { _ans := _obj\n',
    '            this._input := _old_input } }\n',
    '      }\n',
    '      }\n'
  ].join('')
}
BCPLOMetaTranslator.emitPred = function(x) {
  return [
    '      {\n',
    '      _ans := ', x, '\n',
    '      if not _ans then\n',
    '        _ans := undefined\n',
    '      }\n'
   ].join('')
}
BCPLOMetaTranslator.emitAct = function(x) {
  return [
    '      { ', x, ' }\n'
  ].join('')
}
BCPLOMetaTranslator.emitAns = function(x) {
  return [
    '      _ans := ', x, '\n'
  ].join('')
}
BCPLOMetaTranslator.emitOr = function(xs) {
  return this.nestWithDecls('_old_input = this._input', [
    xs[0],
    this.emitOrHelper(xs.splice(1))
  ].join(''))
}
BCPLOMetaTranslator.emitOrHelper = function(xs) {
  if (xs.length == 0)
    return ''
  return [
    '      if _ans = undefined do {\n',
    '        this._input := _old_input\n',
    xs[0],
    this.emitOrHelper(xs.splice(1)),
    '      }\n'
  ].join('')
}
BCPLOMetaTranslator.emitXOr = function(xs) {
  return this.nestWithDecls('_old_input, _the_ans, _the_input, _failed = this._input, undefined, undefined, false', this.emitXOrHelper(xs))
}
BCPLOMetaTranslator.emitXOrHelper = function(xs) {
  if (xs.length == 0)
    return [
      '      test _failed then\n',
      '        _ans := undefined\n',
      '      or\n',
      '      { _ans := _the_ans\n',
      '        this._input := _the_input }\n'
    ].join('')
  else
    return [
      '      if not _failed then\n',
      '      { this._input := _old_input\n',
      xs[0],
      '        if _ans \\= undefined then\n',
      '        { test _the_ans = undefined then\n',
      '          { _the_ans := _ans\n',
      '            _the_input := this._input }\n',
      '          or\n',
      '            _failed := true } }\n',
      this.emitXOrHelper(xs.splice(1))
    ].join('')
}
BCPLOMetaTranslator.emitAnd = function(xs) {
  if (xs.length == 0)
    // this case is only used by empty Ands
    return '      _ans = undefined\n'
  if (xs.length == 1)
    return xs[0]
  return [
    '      {\n',
    xs[0],
    '      unless _ans = undefined do\n',
    this.emitAnd(xs.splice(1)),
    '      }\n'
  ].join('')
}
BCPLOMetaTranslator.emitSet = function(name, value) {
  return [
    '      {\n',
    value,
    '      if _ans \\= undefined then \n',
    '        ', name, ' := _ans\n',
    '      }\n'
  ].join('')
}
BCPLOMetaTranslator.emitApp = function(rule, args) {
  return [
    '      _ans := this._apply(', ['thisar', '"' + rule + '"'].concat(args).join(', '), ')\n'
  ].join('')
}
BCPLOMetaTranslator.emitLocals = function(varNames) {
  return varNames.map(function(varName) {
    return '      let ' + varName
  }).join('\n') + '\n'
}
BCPLOMetaTranslator.emitRule = function(locals, body) {
  return [
    '  { let g_', this.rName, '(this, failar) = valof {\n',
    locals,
    body, '\n',
/*
    // The following is commented out b/c it would be useless
    '      if _ans = undefined do\n',
    '        returnto failar\n',
*/
    '      resultis _ans }\n',
    '    _grammar.', this.rName, ' := g_', this.rName, '}\n'
  ].join('')
}
BCPLOMetaTranslator.emitGrammar = function(rules) {
  return [
    'let make_', this.name, '() = valof {\n',
    '  static { _grammar, vector, vecinputstream }\n',
    '  unless _grammar = undefined do\n',
    '    resultis _grammar\n',
    '  vector := !(lookup "vector")\n',
    '  vecinputstream := !(lookup "vecinputstream")\n',
    '  { let super_grammar = !(lookup "', this.sName, '")\n',
    '    _grammar := newhtfluis(0, super_grammar)\n',
    '    _grammar._super := super_grammar }\n',
    rules.join('\n'),
    '  resultis _grammar }\n'
  ].join('')
}

tree = BCPLOMetaParser.matchAll("ometa g {
                                   digit = :x ?[[[x >= '0' /\\ x <= '9']]] -> [[[x - '0']]],
                                   digits = digit*:ds -> [[[ds]]],
                                   letter = :x ?[[[x = '5']]] -> [[[5]]] || digit,
                                   main = $a $b $c
                                 }", "grammar")
code = BCPLOMetaTranslator.match(tree, "trans")

/*
tree = BCPLOMetaParser.matchAll("ometa g {
                                   digit = :x ?[[[x >= '0' /\\ x <= '9']]] -> [[[x - '0']]],
                                   number = number:n digit:d -> [[[n * 10 + d]]]
                                          | &digit digit
                                 }", "grammar")
code = BCPLOMetaTranslator.match(tree, "trans")
*/