class ActionDispatch::Journey::GTG::Builder

def build_followpos
  table = Hash.new { |h, k| h[k] = [] }
  @ast.each do |n|
    case n
    when Nodes::Cat
      lastpos(n.left).each do |i|
        table[i] += firstpos(n.right)
      end
    when Nodes::Star
      lastpos(n).each do |i|
        table[i] += firstpos(n)
      end
    end
  end
  table
end

def firstpos(node)
  case node
  when Nodes::Star
    firstpos(node.left)
  when Nodes::Cat
    if nullable?(node.left)
      firstpos(node.left) | firstpos(node.right)
    else
      firstpos(node.left)
    end
  when Nodes::Or
    node.children.flat_map { |c| firstpos(c) }.uniq
  when Nodes::Unary
    firstpos(node.left)
  when Nodes::Terminal
    nullable?(node) ? [] : [node]
  else
    raise ArgumentError, 'unknown firstpos: %s' % node.class.name
  end
end

def followpos(node)
  followpos_table[node]
end

def followpos_table
  @followpos ||= build_followpos
end

def initialize(root)
  @root      = root
  @ast       = Nodes::Cat.new root, DUMMY
  @followpos = nil
end

def lastpos(node)
  case node
  when Nodes::Star
    firstpos(node.left)
  when Nodes::Or
    node.children.flat_map { |c| lastpos(c) }.uniq
  when Nodes::Cat
    if nullable?(node.right)
      lastpos(node.left) | lastpos(node.right)
    else
      lastpos(node.right)
    end
  when Nodes::Terminal
    nullable?(node) ? [] : [node]
  when Nodes::Unary
    lastpos(node.left)
  else
    raise ArgumentError, 'unknown lastpos: %s' % node.class.name
  end
end

def nullable?(node)
  case node
  when Nodes::Group
    true
  when Nodes::Star
    true
  when Nodes::Or
    node.children.any? { |c| nullable?(c) }
  when Nodes::Cat
    nullable?(node.left) && nullable?(node.right)
  when Nodes::Terminal
    !node.left
  when Nodes::Unary
    nullable?(node.left)
  else
    raise ArgumentError, 'unknown nullable: %s' % node.class.name
  end
end

def symbol(edge)
  case edge
  when Journey::Nodes::Symbol
    edge.regexp
  else
    edge.left
  end
end

def transition_table
  dtrans   = TransitionTable.new
  marked   = {}
  state_id = Hash.new { |h,k| h[k] = h.length }
  start   = firstpos(root)
  dstates = [start]
  until dstates.empty?
    s = dstates.shift
    next if marked[s]
    marked[s] = true # mark s
    s.group_by { |state| symbol(state) }.each do |sym, ps|
      u = ps.flat_map { |l| followpos(l) }
      next if u.empty?
      if u.uniq == [DUMMY]
        from = state_id[s]
        to   = state_id[Object.new]
        dtrans[from, to] = sym
        dtrans.add_accepting(to)
        ps.each { |state| dtrans.add_memo(to, state.memo) }
      else
        dtrans[state_id[s], state_id[u]] = sym
        if u.include?(DUMMY)
          to = state_id[u]
          accepting = ps.find_all { |l| followpos(l).include?(DUMMY) }
          accepting.each { |accepting_state|
            dtrans.add_memo(to, accepting_state.memo)
          }
          dtrans.add_accepting(state_id[u])
        end
      end
      dstates << u
    end
  end
  dtrans
end