Module: Ibex::Analysis::Digraph

Defined in:
lib/ibex/analysis/digraph.rb,
sig/ibex/analysis/digraph.rbs

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

Instance Method Summary collapse

Class Method Details

.closure(initial, edges) ⇒ Object

RBS:

  • (Array[Integer] initial, Array[Array[Integer]] edges) -> Array[Integer]

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

Instance Method Details

#self?.closure ⇒ Array[Integer]

RBS:

  • (Array[Integer] initial, Array[Array[Integer]] edges) -> Array[Integer]

Parameters:

  • initial (Array[Integer])
  • edges (Array[Array[Integer]])

Returns:

  • (Array[Integer]) 


10
 
# File 'sig/ibex/analysis/digraph.rbs', line 10

def self?.closure: (Array[Integer] initial, Array[Array[Integer]] edges) -> Array[Integer]

#self?.strongly_connected_components ⇒ Array[Array[Integer]]

RBS:

  • (Array[Array[Integer]] edges) -> Array[Array[Integer]]

Parameters:

  • edges (Array[Array[Integer]])

Returns:

  • (Array[Array[Integer]]) 


13
 
# File 'sig/ibex/analysis/digraph.rbs', line 13

def self?.strongly_connected_components: (Array[Array[Integer]] edges) -> Array[Array[Integer]]

#self?.topological_order ⇒ Array[Integer]

RBS:

  • (Array[Array[Integer]]) -> Array[Integer]

Parameters:

  • (Array[Array[Integer]])

Returns:

  • (Array[Integer]) 


16
 
# File 'sig/ibex/analysis/digraph.rbs', line 16

def self?.topological_order: (Array[Array[Integer]]) -> Array[Integer]