Class: Ibex::Impact::Propagation

Inherits:
Object
  • Object
show all
Defined in:
lib/ibex/impact/propagation.rb,
sig/ibex/impact/propagation.rbs

Overview

Performs deterministic forward propagation over a dependency graph.

Instance Method Summary collapse

Constructor Details

#initialize(graph) ⇒ Propagation

Returns a new instance of Propagation.

RBS:

  • @graph: Graph

  • (Graph graph) -> void

Parameters:



31
32
33
 
# File 'lib/ibex/impact/propagation.rb', line 31

def initialize(graph)
  @graph = graph
end

Instance Method Details

#build_nodes(component_nodes, components, kind, witnesses) ⇒ Hash[Integer, Node]

RBS:

  • (Hash[Integer, Integer], Array[Array[Integer]], Symbol, Hash[Integer, Array[Edge]]) -> Hash[Integer, Node]

Parameters:

  • (Hash[Integer, Integer])
  • (Array[Array[Integer]])
  • (Symbol)
  • (Hash[Integer, Array[Edge]])

Returns:

  • (Hash[Integer, Node]) 


133
134
135
136
137
138
139
140
141
142
143
144
 
# File 'lib/ibex/impact/propagation.rb', line 133

def build_nodes(component_nodes, components, kind, witnesses)
  result = {} #: Hash[Integer, Node]
  component_nodes.each do |component, distance|
    members = components.fetch(component).sort
    members.each do |symbol|
      result[symbol] = Node.new(
        symbol: symbol, distance: distance, witness: witnesses.fetch(symbol), kind: kind, component: members
      )
    end
  end
  result.sort.to_h
end

#component_adjacency(adjacency, component_for, component_count) ⇒ Array[Array[Integer]]

RBS:

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

Parameters:

  • (Array[Array[Integer]])
  • (Array[Integer])
  • (Integer)

Returns:

  • (Array[Array[Integer]]) 


77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
 
# File 'lib/ibex/impact/propagation.rb', line 77

def component_adjacency(adjacency, component_for, component_count)
  result = Array.new(component_count) { [] } #: Array[Array[Integer]]
  adjacency.each_with_index do |successors, source|
    source_component = component_for.fetch(source)
    successors.each do |target|
      target_component = component_for.fetch(target)
      next if source_component == target_component

      result[source_component] << target_component
    end
  end
  result.each do |successors|
    successors.uniq!
    successors.sort!
  end
  result
end

#component_index(components, size) ⇒ Array[Integer]

RBS:

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

Parameters:

  • (Array[Array[Integer]])
  • (Integer)

Returns:

  • (Array[Integer]) 


70
71
72
73
74
 
# File 'lib/ibex/impact/propagation.rb', line 70

def component_index(components, size)
  result = Array.new(size, 0) #: Array[Integer]
  components.each_with_index { |members, id| members.each { |member| result[member] = id } }
  result
end

#normalize_seeds(seeds) ⇒ Array[Integer]

RBS:

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

Parameters:

  • (Array[Integer])

Returns:

  • (Array[Integer]) 


60
61
62
63
64
65
66
67
 
# File 'lib/ibex/impact/propagation.rb', line 60

def normalize_seeds(seeds)
  seeds.uniq.sort.each do |id|
    unless @graph.grammar.symbol_by_id(id)
      raise ArgumentError,
            "impact seed #{id.inspect} is not a grammar symbol"
    end
  end
end

#propagate(seeds, kind = :all, max_depth: nil) ⇒ Hash[Integer, Node] Also known as: call

RBS:

  • (Array[Integer] seeds, Symbol kind, ?max_depth: Integer?) -> Hash[Integer, Node]

Parameters:

  • seeds (Array[Integer])
  • kind (Symbol) (defaults to: :all)
  • max_depth: (Integer, nil) (defaults to: nil)

Returns:

  • (Hash[Integer, Node]) 


36
37
38
39
40
41
42
43
44
45
46
 
# File 'lib/ibex/impact/propagation.rb', line 36

def propagate(seeds, kind = :all, max_depth: nil)
  validate_depth(max_depth)
  selected = normalize_seeds(seeds)
  adjacency = @graph.adjacency(kind)
  components = Analysis::Digraph.send(:strongly_connected_components, adjacency)
  component_for = component_index(components, adjacency.length)
  component_edges = component_adjacency(adjacency, component_for, components.length)
  component_nodes = traverse_components(selected, component_for, component_edges, max_depth)
  witnesses = symbol_witnesses(selected, adjacency, kind)
  build_nodes(component_nodes, components, kind, witnesses)
end

#symbol_witnesses(seeds, adjacency, kind) ⇒ Hash[Integer, Array[Edge]]

RBS:

  • (Array[Integer], Array[Array[Integer]], Symbol) -> Hash[Integer, Array[Edge]]

Parameters:

  • (Array[Integer])
  • (Array[Array[Integer]])
  • (Symbol)

Returns:

  • (Hash[Integer, Array[Edge]]) 


115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
 
# File 'lib/ibex/impact/propagation.rb', line 115

def symbol_witnesses(seeds, adjacency, kind)
  edges = @graph.edges(kind).group_by { |edge| [edge.source, edge.target] }
  queue = seeds.uniq.sort.map { |seed| [seed, []] } #: Array[[Integer, Array[Edge]]]
  result = {} #: Hash[Integer, Array[Edge]]
  until queue.empty?
    symbol, witness = queue.shift
    next if result.key?(symbol)

    result[symbol] = witness
    adjacency.fetch(symbol).each do |target|
      edge = edges.fetch([symbol, target]).fetch(0)
      queue << [target, witness + [edge]]
    end
  end
  result
end

#traverse_components(seeds, component_for, component_edges, max_depth) ⇒ Hash[Integer, Integer]

RBS:

  • (Array[Integer], Array[Integer], Array[Array[Integer]], Integer?) -> Hash[Integer, Integer]

Parameters:

  • (Array[Integer])
  • (Array[Integer])
  • (Array[Array[Integer]])
  • (Integer, nil)

Returns:

  • (Hash[Integer, Integer]) 


96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
 
# File 'lib/ibex/impact/propagation.rb', line 96

def traverse_components(seeds, component_for, component_edges, max_depth)
  queue = seeds.uniq.sort.map do |seed|
    [component_for.fetch(seed), 0]
  end #: Array[[Integer, Integer]]
  result = {} #: Hash[Integer, Integer]
  until queue.empty?
    component, distance = queue.shift
    next if result.key?(component)
    next if max_depth && distance > max_depth

    result[component] = distance
    component_edges.fetch(component).each do |target|
      queue << [target, distance + 1]
    end
  end
  result
end

#validate_depth(max_depth) ⇒ void

This method returns an undefined value.

RBS:

  • (Integer?) -> void

Parameters:

  • (Integer, nil) 


53
54
55
56
57
 
# File 'lib/ibex/impact/propagation.rb', line 53

def validate_depth(max_depth)
  return if max_depth.nil? || (max_depth.is_a?(Integer) && max_depth >= 0)

  raise ArgumentError, "impact depth must be a non-negative integer"
end