Module: Ibex::Analysis::Digraph

Defined in:
lib/ibex/analysis/digraph.rb

Overview

Computes the transitive bit-set closure used by the LR lookahead algorithms. The implementation is iterative so a large grammar cannot exhaust Ruby's call stack merely because its dependency graph is deep.

Class Method Summary collapse

Class Method Details

.closure(initial, edges) ⇒ Object

Raises:

  • (ArgumentError) 


18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
 
# File 'lib/ibex/analysis/digraph.rb', line 18

def closure(initial, edges)
  raise ArgumentError, "digraph edge count does not match values" unless initial.length == edges.length

  values = initial.dup
  components = strongly_connected_components(edges)
  component_edges = Array.new(components.length) { [] }
  component_for = Array.new(edges.length)
  components.each_with_index do |members, component_id|
    members.each { |vertex| component_for[vertex] = component_id }
  end
  edges.each_with_index do |successors, vertex|
    source = component_for.fetch(vertex)
    successors.each do |successor|
      target = component_for.fetch(successor)
      component_edges[source] << target if source != target
    end
  end
  component_edges.each(&:uniq!)

  order = topological_order(component_edges)
  order.reverse_each do |component_id|
    members = components.fetch(component_id)
    merged = members.reduce(0) { |bits, vertex| bits | values.fetch(vertex) }
    component_edges.fetch(component_id).each do |successor|
      merged |= values.fetch(components.fetch(successor).first)
    end
    members.each { |vertex| values[vertex] = merged }
  end
  values
end