class Racc::StateTransitionTableGenerator

def act2actid(act)
  case act
  when Shift  then act.goto_id
  when Reduce then -act.ruleid
  when Accept then @states.shift_n
  when Error  then @states.reduce_n * -1
  else
    raise "racc: fatal: wrong act type #{act.class} in action table"
  end
end

def addent(all, arr, chkval, ptr)
  max = arr.size
  min = nil
  arr.each_with_index do |item, idx|
    if item
      min ||= idx
    end
  end
  ptr.push(-7777)    # mark
  arr = arr[min...max]
  all.push [arr, chkval, mkmapexp(arr), min, ptr.size - 1]
end

def gen_action_tables(t, states)
  t.action_table = yytable  = []
  t.action_check = yycheck  = []
  t.action_default = yydefact = []
  t.action_pointer = yypact   = []
  e1 = []
  e2 = []
  states.each do |state|
    yydefact.push act2actid(state.defact)
    if state.action.empty?
      yypact.push nil
      next
    end
    vector = []
    state.action.each do |tok, act|
      vector[tok.ident] = act2actid(act)
    end
    addent e1, vector, state.ident, yypact
  end
  set_table e1, e2, yytable, yycheck, yypact
end

def gen_goto_tables(t, grammar)
  t.goto_table   = yytable2  = []
  t.goto_check   = yycheck2  = []
  t.goto_pointer = yypgoto   = []
  t.goto_default = yydefgoto = []
  e1 = []
  e2 = []
  grammar.each_nonterminal do |tok|
    tmp = []
    # decide default
    freq = Array.new(@states.size, 0)
    @states.each do |state|
      st = state.goto_table[tok]
      if st
        st = st.ident
        freq[st] += 1
      end
      tmp[state.ident] = st
    end
    max = freq.max
    if max > 1
      default = freq.index(max)
      tmp.map! {|i| default == i ? nil : i }
    else
      default = nil
    end
    yydefgoto.push default
    # delete default value
    tmp.pop until tmp.last or tmp.empty?
    if tmp.compact.empty?
      # only default
      yypgoto.push nil
      next
    end
    addent e1, tmp, (tok.ident - grammar.nonterminal_base), yypgoto
  end
  set_table e1, e2, yytable2, yycheck2, yypgoto
end

def generate
  t = StateTransitionTable.new(@states)
  gen_action_tables t, @states
  gen_goto_tables t, @grammar
  t.token_table = token_table(@grammar)
  t.reduce_table = reduce_table(@grammar)
  t.reduce_n = @states.reduce_n
  t.shift_n = @states.shift_n
  t.nt_base = @grammar.nonterminal_base
  t.token_to_s_table = @grammar.symbols.map {|sym| sym.to_s }
  t
end

def initialize(states)
  @states = states
  @grammar = states.grammar
end

def mkmapexp(arr)
  i = ii = 0
  as = arr.size
  map = String.new
  maxdup = RE_DUP_MAX
  curr = nil
  while i < as
    ii = i + 1
    if arr[i]
      ii += 1 while ii < as and arr[ii]
      curr = '-'
    else
      ii += 1 while ii < as and not arr[ii]
      curr = '.'
    end
    offset = ii - i
    if offset == 1
      map << curr
    else
      while offset > maxdup
        map << "#{curr}{#{maxdup}}"
        offset -= maxdup
      end
      map << "#{curr}{#{offset}}" if offset > 1
    end
    i = ii
  end
  Regexp.compile(map, Regexp::NOENCODING)
end

def reduce_table(grammar)
  t = [0, 0, :racc_error]
  grammar.each_with_index do |rule, idx|
    next if idx == 0
    t.push rule.size
    t.push rule.target.ident
    t.push(if rule.action.empty?   # and @params.omit_action_call?
           then :_reduce_none
           else "_reduce_#{idx}".intern
           end)
  end
  t
end

def set_table(entries, dummy, tbl, chk, ptr)
  upper = 0
  map = '-' * 10240
  # sort long to short
  entries.sort_by!.with_index {|a,i| [-a[0].size, i] }
  entries.each do |arr, chkval, expr, min, ptri|
    if upper + arr.size > map.size
      map << '-' * (arr.size + 1024)
    end
    idx = map.index(expr)
    ptr[ptri] = idx - min
    arr.each_with_index do |item, i|
      if item
        i += idx
        tbl[i] = item
        chk[i] = chkval
        map[i] = ?o
      end
    end
    upper = idx + arr.size
  end
end

def token_table(grammar)
  h = {}
  grammar.symboltable.terminals.each do |t|
    h[t] = t.ident
  end
  h
end