class Racc::States

# File racc/state.rb, line 25
def initialize(grammar, debug_flags = DebugFlags.new)
  @grammar = grammar
  @symboltable = grammar.symboltable
  @d_state = debug_flags.state
  @d_la    = debug_flags.la
  @d_prec  = debug_flags.prec
  @states = []
  @statecache = {}
  @actions = ActionTable.new(@grammar, self)
  @nfa_computed = false
  @dfa_computed = false
end

# File racc/state.rb, line 51
def [](i)
  @states[i]
end

# File racc/state.rb, line 196
def dfa
  return self if @dfa_computed
  nfa
  compute_dfa
  @dfa_computed = true
  self
end

# File racc/state.rb, line 61
def each_index(&block)
  @states.each_index(&block)
end

# File racc/state.rb, line 55
def each_state(&block)
  @states.each(&block)
end

# File racc/state.rb, line 45
def inspect
  '#<state table>'
end

# File racc/state.rb, line 88
def n_rrconflicts
  @n_rrconflicts ||= inject(0) {|sum, st| sum + st.n_rrconflicts }
end

# File racc/state.rb, line 80
def n_srconflicts
  @n_srconflicts ||= inject(0) {|sum, st| sum + st.n_srconflicts }
end

# File racc/state.rb, line 102
def nfa
  return self if @nfa_computed
  compute_nfa
  @nfa_computed = true
  self
end

# File racc/state.rb, line 84
def rrconflict_exist?
  n_rrconflicts() != 0
end

# File racc/state.rb, line 71
def should_report_srconflict?
  srconflict_exist? and
      (n_srconflicts() != @grammar.n_expected_srconflicts)
end

# File racc/state.rb, line 41
def size
  @states.size
end

# File racc/state.rb, line 76
def srconflict_exist?
  n_srconflicts() != 0
end

# File racc/state.rb, line 92
def state_transition_table
  @state_transition_table ||= StateTransitionTable.generate(self.dfa)
end

# File racc/state.rb, line 317
def addrel(tbl, i, item)
  if a = tbl[i]
    a.push item
  else
    tbl[i] = [item]
  end
end

# File racc/state.rb, line 154
def addsym(table, sym, ptr)
  unless s = table[sym]
    table[sym] = s = ISet.new
  end
  s.add ptr
end

# File racc/state.rb, line 586
def check_useless
  used = []
  @actions.each_reduce do |act|
    if not act or act.refn == 0
      act.rule.useless = true
    else
      t = act.rule.target
      used[t.ident] = t
    end
  end
  @symboltable.nt_base.upto(@symboltable.nt_max - 1) do |n|
    unless used[n]
      @symboltable[n].useless = true
    end
  end
end

# File racc/state.rb, line 206
def compute_dfa
  la = lookahead()
  @states.each do |state|
    state.la = la
    resolve state
  end
  set_accept
  @states.each do |state|
    pack state
  end
  check_useless
end

# File racc/state.rb, line 111
def compute_nfa
  @grammar.init
  # add state 0
  core_to_state  [ @grammar[0].ptrs[0] ]
  # generate LALR states
  cur = 0
  @gotos = []
  while cur < @states.size
    generate_states @states[cur]   # state is added here
    cur += 1
  end
  @actions.init
end

# File racc/state.rb, line 161
def core_to_state(core)
  #
  # convert CORE to a State object.
  # If matching state does not exist, create it and add to the table.
  #

  k = fingerprint(core)
  unless dest = @statecache[k]
    # not registered yet
    dest = State.new(@states.size, core)
    @states.push dest

    @statecache[k] = dest

    puts "core_to_state: create state   ID #{dest.ident}" if @d_state
  else
    if @d_state
      puts "core_to_state: dest is cached ID #{dest.ident}"
      puts "core_to_state: dest core #{dest.core.join(' ')}"
    end
  end

  dest
end

# File racc/state.rb, line 313
def create_tmap(size)
  Array.new(size, 0)   # use Integer as bitmap
end

# File racc/state.rb, line 348
def digraph(map, relation)
  n = relation.size
  index    = Array.new(n, nil)
  vertices = []
  @infinity = n + 2

  index.each_index do |i|
    if not index[i] and relation[i]
      traverse i, index, vertices, map, relation
    end
  end
end

# File racc/state.rb, line 523
def do_resolve_sr(stok, rtok)
  puts "resolve_sr: s/r conflict: rtok=#{rtok}, stok=#{stok}" if @d_prec

  unless rtok and rtok.precedence
    puts "resolve_sr: no prec for #{rtok}(R)" if @d_prec
    return :CantResolve
  end
  rprec = rtok.precedence

  unless stok and stok.precedence
    puts "resolve_sr: no prec for #{stok}(S)" if @d_prec
    return :CantResolve
  end
  sprec = stok.precedence

  ret = if rprec == sprec
          ASSOC[rtok.assoc] or
              raise "racc: fatal: #{rtok}.assoc is not Left/Right/Nonassoc"
        else
          (rprec > sprec) ? (:Reduce) : (:Shift)
        end

  puts "resolve_sr: resolved as #{ret.id2name}" if @d_prec
  ret
end

# File racc/state.rb, line 422
def each_t(tbl, set)
  0.upto( set.size ) do |i|
    (0..7).each do |ii|
      if set[idx = i * 8 + ii] == 1
        yield tbl[idx]
      end
    end
  end
end

# File racc/state.rb, line 186
def fingerprint(arr)
  arr.map {|i| i.ident }.pack('L*')
end

# File racc/state.rb, line 125
def generate_states(state)
  puts "dstate: #{state}" if @d_state

  table = {}
  state.closure.each do |ptr|
    if sym = ptr.dereference
      addsym table, sym, ptr.next
    end
  end
  table.each do |sym, core|
    puts "dstate: sym=#{sym} ncore=#{core}" if @d_state

    dest = core_to_state(core.to_a)
    state.goto_table[sym] = dest
    id = sym.nonterminal?() ? @gotos.size : nil
    g = Goto.new(id, sym, state, dest)
    @gotos.push g if sym.nonterminal?
    state.gotos[sym] = g
    puts "dstate: #{state.ident} --#{sym}--> #{dest.ident}" if @d_state

    # check infinite recursion
    if state.ident == dest.ident and state.closure.size == 1
      raise CompileError,
          sprintf("Infinite recursion: state %d, with rule %d",
                  state.ident, state.ptrs[0].rule.ident)
    end
  end
end

# File racc/state.rb, line 219
def lookahead
  #
  # lookahead algorithm ver.3 -- from bison 1.26
  #

  gotos = @gotos
  if @d_la
    puts "\n--- goto ---"
    gotos.each_with_index {|g, i| print i, ' '; p g }
  end

  ### initialize_LA()
  ### set_goto_map()
  la_rules = []
  @states.each do |state|
    state.check_la la_rules
  end

  ### initialize_F()
  f     = create_tmap(gotos.size)
  reads = []
  edge  = []
  gotos.each do |goto|
    goto.to_state.goto_table.each do |t, st|
      if t.terminal?
        f[goto.ident] |= (1 << t.ident)
      elsif t.nullable?
        edge.push goto.to_state.gotos[t].ident
      end
    end
    if edge.empty?
      reads.push nil
    else
      reads.push edge
      edge = []
    end
  end
  digraph f, reads
  if @d_la
    puts "\n--- F1 (reads) ---"
    print_tab gotos, reads, f
  end

  ### build_relations()
  ### compute_FOLLOWS
  path = nil
  edge = []
  lookback = Array.new(la_rules.size, nil)
  includes = []
  gotos.each do |goto|
    goto.symbol.heads.each do |ptr|
      path = record_path(goto.from_state, ptr.rule)
      lastgoto = path.last
      st = lastgoto ? lastgoto.to_state : goto.from_state
      if st.conflict?
        addrel lookback, st.rruleid(ptr.rule), goto
      end
      path.reverse_each do |g|
        break if     g.symbol.terminal?
        edge.push    g.ident
        break unless g.symbol.nullable?
      end
    end
    if edge.empty?
      includes.push nil
    else
      includes.push edge
      edge = []
    end
  end
  includes = transpose(includes)
  digraph f, includes
  if @d_la
    puts "\n--- F2 (includes) ---"
    print_tab gotos, includes, f
  end

  ### compute_lookaheads
  la = create_tmap(la_rules.size)
  lookback.each_with_index do |arr, i|
    if arr
      arr.each do |g|
        la[i] |= f[g.ident]
      end
    end
  end
  if @d_la
    puts "\n--- LA (lookback) ---"
    print_tab la_rules, lookback, la
  end

  la
end

# File racc/state.rb, line 564
def pack(state)
  ### find most frequently used reduce rule
  act = state.action
  arr = Array.new(@grammar.size, 0)
  act.each do |t, a|
    arr[a.ruleid] += 1  if a.kind_of?(Reduce)
  end
  i = arr.max
  s = (i > 0) ? arr.index(i) : nil

  ### set & delete default action
  if s
    r = @actions.reduce(s)
    if not state.defact or state.defact == r
      act.delete_if {|t, a| a == r }
      state.defact = r
    end
  else
    state.defact ||= @actions.error
  end
end

# File racc/state.rb, line 390
def print_atab(idx, tab)
  tab.each_with_index do |i,ii|
    printf '%-20s', idx[ii].inspect
    p i
  end
end

# File racc/state.rb, line 397
def print_tab(idx, rel, tab)
  tab.each_with_index do |bin,i|
    print i, ' ', idx[i].inspect, ' << '; p rel[i]
    print '  '
    each_t(@symboltable, bin) {|t| print ' ', t }
    puts
  end
end

# File racc/state.rb, line 407
def print_tab_i(idx, rel, tab, i)
  bin = tab[i]
  print i, ' ', idx[i].inspect, ' << '; p rel[i]
  print '  '
  each_t(@symboltable, bin) {|t| print ' ', t }
end

# File racc/state.rb, line 415
def printb(i)
  each_t(@symboltable, i) do |t|
    print t, ' '
  end
  puts
end

# File racc/state.rb, line 325
def record_path(begst, rule)
  st = begst
  path = []
  rule.symbols.each do |t|
    goto = st.gotos[t]
    path.push goto
    st = goto.to_state
  end
  path
end

# File racc/state.rb, line 436
def resolve(state)
  if state.conflict?
    resolve_rr state, state.ritems
    resolve_sr state, state.stokens
  else
    if state.rrules.empty?
      # shift
      state.stokens.each do |t|
        state.action[t] = @actions.shift(state.goto_table[t])
      end
    else
      # reduce
      state.defact = @actions.reduce(state.rrules[0])
    end
  end
end

# File racc/state.rb, line 453
def resolve_rr(state, r)
  r.each do |item|
    item.each_la(@symboltable) do |t|
      act = state.action[t]
      if act
        unless act.kind_of?(Reduce)
          raise "racc: fatal: #{act.class} in action table"
        end
        # Cannot resolve R/R conflict (on t).
        # Reduce with upper rule as default.
        state.rr_conflict act.rule, item.rule, t
      else
        # No conflict.
        state.action[t] = @actions.reduce(item.rule)
      end
    end
  end
end

# File racc/state.rb, line 472
def resolve_sr(state, s)
  s.each do |stok|
    goto = state.goto_table[stok]
    act = state.action[stok]

    unless act
      # no conflict
      state.action[stok] = @actions.shift(goto)
    else
      unless act.kind_of?(Reduce)
        puts 'DEBUG -------------------------------'
        p stok
        p act
        state.action.each do |k,v|
          print k.inspect, ' ', v.inspect, "\n"
        end
        raise "racc: fatal: #{act.class} in action table"
      end

      # conflict on stok

      rtok = act.rule.precedence
      case do_resolve_sr(stok, rtok)
      when :Reduce
        # action is already set

      when :Shift
        # overwrite
        act.decref
        state.action[stok] = @actions.shift(goto)

      when :Error
        act.decref
        state.action[stok] = @actions.error

      when :CantResolve
        # shift as default
        act.decref
        state.action[stok] = @actions.shift(goto)
        state.sr_conflict stok, act.rule
      end
    end
  end
end

# File racc/state.rb, line 553
def set_accept
  anch = @symboltable.anchor
  init_state = @states[0].goto_table[@grammar.start]
  targ_state = init_state.action[anch].goto_state
  acc_state  = targ_state.action[anch].goto_state

  acc_state.action.clear
  acc_state.goto_table.clear
  acc_state.defact = @actions.accept
end

# File racc/state.rb, line 336
def transpose(rel)
  new = Array.new(rel.size, nil)
  rel.each_with_index do |arr, idx|
    if arr
      arr.each do |i|
        addrel new, i, idx
      end
    end
  end
  new
end

# File racc/state.rb, line 361
def traverse(i, index, vertices, map, relation)
  vertices.push i
  index[i] = height = vertices.size

  if rp = relation[i]
    rp.each do |proci|
      unless index[proci]
        traverse proci, index, vertices, map, relation
      end
      if index[i] > index[proci]
        # circulative recursion !!!
        index[i] = index[proci]
      end
      map[i] |= map[proci]
    end
  end

  if index[i] == height
    while true
      proci = vertices.pop
      index[proci] = @infinity
      break if i == proci

      map[proci] |= map[i]
    end
  end
end