class ABNF

# File lib/abnf/abnf.rb, line 5
def initialize
  @names = []
  @rules = {}
  @start = nil
end

# File lib/abnf/parser.rb, line 456
def ABNF.parse(desc, dont_merge_core_rules=false)
  grammar = ABNF.new
  Parser.new(grammar).parse(desc)
  grammar.merge(CoreRules) unless dont_merge_core_rules
  grammar
end

# File lib/abnf/regexp.rb, line 8
def ABNF.regexp(desc, name=nil)
  ABNF.regexp_tree(desc, name).regexp
end

# File lib/abnf/regexp.rb, line 12
def ABNF.regexp_tree(desc, name=nil)
  ABNF.parse(desc).regexp_tree(name)
end

# File lib/abnf/abnf.rb, line 31
def [](name)
  @rules[name]
end

# File lib/abnf/abnf.rb, line 35
def []=(name, rhs)
  @names << name unless @rules.include? name
  @rules[name] = rhs
end

# File lib/abnf/abnf.rb, line 40
def add(name, rhs)
  if @rules.include? name
    @rules[name] |= rhs
  else
    @names << name
    @rules[name] = rhs
  end
end

# File lib/abnf/abnf.rb, line 59
def delete_unreachable!(starts)
  rules = {}
  id_map = {}
  stack = []
  starts.each {|name|
    next if id_map.include? name
    each_strongly_connected_component_from(name, id_map, stack) {|syms|
      syms.each {|sym|
        rules[sym] = @rules[sym] if @rules.include? sym
      }
    }
  }
  @rules = rules
  @names.reject! {|name| !@rules.include?(name)}
  self
end

# File lib/abnf/abnf.rb, line 76
def delete_useless!(starts=nil)
  if starts
    starts = [starts] if Symbol === starts
    delete_unreachable!(starts)
  end

  useful_names = {}
  using_names = {}

  @rules.each {|name, rhs|
    useful_names[name] = true if rhs.useful?(useful_names)
    rhs.each_var {|n|
      (using_names[n] ||= {})[name] = true
    }
  }

  queue = useful_names.keys
  until queue.empty?
    n = queue.pop
    next unless using_names[n]
    using_names[n].keys.each {|name|
      if useful_names[name]
        using_names[n].delete name
      elsif @rules[name].useful?(useful_names)
        using_names[n].delete name
        useful_names[name] = true
        queue << name
      end
    }
  end

  rules = {}
  @rules.each {|name, rhs|
    rhs = rhs.subst_var {|n| useful_names[n] ? nil : EmptySet}
    rules[name] = rhs unless rhs.empty_set?
  }

  #xxx: raise if some of start symbol becomes empty set?

  @rules = rules
  @names.reject! {|name| !@rules.include?(name)}
  self
end

# File lib/abnf/abnf.rb, line 53
def each(&block)
  @names.each {|name|
    yield name, @rules[name]
  }
end

# File lib/abnf/abnf.rb, line 49
def include?(name)
  @rules.include? name
end

# File lib/abnf/abnf.rb, line 25
def merge(g)
  g.each {|name, rhs|
    self.add(name, rhs)
  }
end

# File lib/abnf/abnf.rb, line 21
def names
  @names.dup
end

# File lib/abnf/regexp.rb, line 16
def regexp(name=start_symbol)
  regexp_tree(name).regexp
end

# File lib/abnf/regexp.rb, line 24
def regexp_tree(name=nil)
  name ||= start_symbol
  env = {}
  each_strongly_connected_component_from(name) {|ns|
    rules = {}
    ns.each {|n|
      rules[n] = @rules[n]
    }

    resolved_rules = {}
    updated = true
    while updated
      updated = false
      ns.reject! {|n| !rules.include?(n)}

      rs = {}
      ns.reverse_each {|n|
        e = rules[n]
        if !e
          raise ABNFError.new("no rule defined: #{n}")
        end
        rs[n] = e.recursion(ns, n)
        if rs[n] & OtherRecursion != 0
          raise TooComplex.new("too complex to convert to regexp: #{n} (#{ns.join(', ')})")
        end
      }

      ns.reverse_each {|n|
        e = rules[n]
        r = rs[n]
        if r & SelfRecursion == 0
          resolved_rules[n] = e
          rules.delete n
          rules.each {|n2, e2| rules[n2] = e2.subst_var {|n3| n3 == n ? e : nil}}
          updated = true
          break
        end
      }
      next if updated

      # X = Y | a
      # Y = X | b
      # =>
      # Y = Y | a | b
      ns.reverse_each {|n|
        e = rules[n]
        r = rs[n]
        if r & JustRecursion != 0 && r & ~(NonRecursion|JustRecursion) == 0
          e = e.remove_just_recursion(n)
          resolved_rules[n] = e
          rules.delete n
          rules.each {|n2, e2| rules[n2] = e2.subst_var {|n3| n3 == n ? e : nil}}
          updated = true
          break
        end
      }
      next if updated

      # X = X a | b
      # =>
      # X = b a*
      ns.reverse_each {|n|
        e = rules[n]
        r = rs[n]
        if r & LeftRecursion != 0 && r & ~(NonRecursion|JustRecursion|LeftRecursion|SelfRecursion) == 0
          e = e.remove_left_recursion(n)
          resolved_rules[n] = e
          rules.delete n
          rules.each {|n2, e2| rules[n2] = e2.subst_var {|n3| n3 == n ? e : nil}}
          updated = true
          break
        end
      }
      next if updated

      # X = a X | b
      # =>
      # X = a* b
      ns.reverse_each {|n|
        e = rules[n]
        r = rs[n]
        if r & RightRecursion != 0 && r & ~(NonRecursion|JustRecursion|RightRecursion|SelfRecursion) == 0
          e = e.remove_right_recursion(n)
          resolved_rules[n] = e
          rules.delete n
          rules.each {|n2, e2| rules[n2] = e2.subst_var {|n3| n3 == n ? e : nil}}
          updated = true
          break
        end
      }
      next if updated
    end

    if 1 < rules.length
      raise TooComplex.new("too complex to convert to regexp: (#{ns.join(', ')})")
    end

    if rules.length == 1
      n, e = rules.shift
      r = e.recursion(ns, n)
      if r & OtherRecursion != 0
        raise TooComplex.new("too complex to convert to regexp: #{n} (#{ns.join(', ')})")
      end
      if r == NonRecursion
        resolved_rules[n] = e
      else
        # X = a X | b | X c
        # =>
        # X = a* b c*
        left, middle, right = e.split_recursion(n)
        resolved_rules[n] = Seq.new(Alt.new(left).rep, Alt.new(middle), Alt.new(right).rep)
      end
    end

    class << resolved_rules
      include TSort
      alias tsort_each_node each_key
      def tsort_each_child(n, &block)
        self[n].each_var {|n2|
          yield n2 if self.include? n2
        }
      end
    end

    resolved_rules.tsort_each {|n|
      env[n] = resolved_rules[n].subst_var {|n2|
        unless env[n2]
          raise Exception.new("unresolved nonterminal: #{n}") # bug
        end
        env[n2]
      }
    }
  }
  env[name].regexp_tree
end

# File lib/abnf/abnf.rb, line 15
def start_symbol
  return @start if @start
  raise StandardError.new("no symbol defined") if @names.empty?
  @names.first
end

# File lib/abnf/abnf.rb, line 11
def start_symbol=(name)
  @start = name
end

# File lib/abnf/abnf.rb, line 130
def tsort_each_child(name)
  return unless @rules.include? name
  @rules.fetch(name).each_var {|n| yield n}
end

# File lib/abnf/abnf.rb, line 127
def tsort_each_node(&block)
  @names.each(&block)
end