Class: Ibex::Impact::Graph

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

Overview

Combines reference, FIRST, and FOLLOW propagation dependencies.

Constant Summary collapse

EDGE_KINDS =

Signature:

  • Array[Symbol]

Returns:

  • (Array[Symbol]) 
%i[reference first follow_lhs follow_first].freeze
KIND_ALIASES =

Returns:

  • (Hash[Symbol, Array[Symbol]]) 
{
  all: EDGE_KINDS, reference: [:reference], first: [:first], follow: %i[follow_lhs follow_first],
  follow_lhs: [:follow_lhs], follow_first: [:follow_first]
}.freeze

Instance Attribute Summary collapse

Instance Method Summary collapse

Constructor Details

#initialize(grammar, sets: nil) ⇒ Graph

Returns a new instance of Graph.

RBS:

  • (IR::Grammar grammar, ?sets: Analysis::Sets) -> void

Parameters:



44
45
46
47
48
49
 
# File 'lib/ibex/impact/graph.rb', line 44

def initialize(grammar, sets: nil)
  @grammar = grammar
  @sets = sets || Analysis::Sets.new(grammar)
  @edges = build_edges
  freeze_edges
end

Instance Attribute Details

#grammar ⇒ IR::Grammar (readonly)

Signature:

  • Hash[Symbol, Array[Symbol]]

Returns:



40
41
42
 
# File 'lib/ibex/impact/graph.rb', line 40

def grammar
  @grammar
end

#sets ⇒ Analysis::Sets (readonly)

Signature:

  • Analysis::Sets

Returns:



41
42
43
 
# File 'lib/ibex/impact/graph.rb', line 41

def sets
  @sets
end

Instance Method Details

#add_first_edge(result, production, symbol_id, position) ⇒ void

This method returns an undefined value.

RBS:

  • (Hash[Symbol, Array[Edge]], IR::Production, Integer, Integer) -> void

Parameters:



91
92
93
94
95
96
97
 
# File 'lib/ibex/impact/graph.rb', line 91

def add_first_edge(result, production, symbol_id, position)
  prefix = production.rhs[0...position] || []
  return unless @sets.sequence_nullable?(prefix)
  return unless @sets.first_dependencies.fetch(symbol_id).include?(production.lhs)

  result[:first] << edge(symbol_id, production.lhs, :first, production, position)
end

#add_follow_edges(result, production, symbol_id, position) ⇒ void

This method returns an undefined value.

RBS:

  • (Hash[Symbol, Array[Edge]], IR::Production, Integer, Integer) -> void

Parameters:



100
101
102
103
104
105
106
 
# File 'lib/ibex/impact/graph.rb', line 100

def add_follow_edges(result, production, symbol_id, position)
  suffix = production.rhs[(position + 1)..] || []
  if @sets.sequence_nullable?(suffix) && @sets.follow_dependencies.fetch(production.lhs).include?(symbol_id)
    result[:follow_lhs] << edge(production.lhs, symbol_id, :follow_lhs, production, position)
  end
  add_follow_first_edges(result, production, symbol_id, position)
end

#add_follow_first_edges(result, production, symbol_id, position) ⇒ void

This method returns an undefined value.

RBS:

  • (Hash[Symbol, Array[Edge]], IR::Production, Integer, Integer) -> void

Parameters:



109
110
111
112
113
114
115
116
117
118
 
# File 'lib/ibex/impact/graph.rb', line 109

def add_follow_first_edges(result, production, symbol_id, position)
  suffix = production.rhs[(position + 1)..] || []
  suffix.each_with_index do |candidate, offset|
    candidate_prefix = suffix[0...offset] || []
    break unless @sets.sequence_nullable?(candidate_prefix)
    break unless @grammar.symbol_by_id(candidate)&.nonterminal?

    result[:follow_first] << edge(candidate, symbol_id, :follow_first, production, position + 1 + offset)
  end
end

#add_production_edges(result, production) ⇒ void

This method returns an undefined value.

RBS:

  • (Hash[Symbol, Array[Edge]], IR::Production) -> void

Parameters:



80
81
82
83
84
85
86
87
88
 
# File 'lib/ibex/impact/graph.rb', line 80

def add_production_edges(result, production)
  production.rhs.each_with_index do |symbol_id, position|
    next unless @grammar.symbol_by_id(symbol_id)&.nonterminal?

    result[:reference] << edge(symbol_id, production.lhs, :reference, production, position)
    add_first_edge(result, production, symbol_id, position)
    add_follow_edges(result, production, symbol_id, position)
  end
end

#adjacency(kind) ⇒ Array[Array[Integer]]

RBS:

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

Parameters:

  • kind (Symbol)

Returns:

  • (Array[Array[Integer]]) 


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

def adjacency(kind)
  result = Array.new(@grammar.symbols.length) { [] }
  edges(kind).each { |edge| result[edge.source] << edge.target }
  result.each(&:uniq!)
  result
end

#build_edges ⇒ Hash[Symbol, Array[Edge]]

RBS:

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

Returns:

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


70
71
72
73
74
75
76
77
 
# File 'lib/ibex/impact/graph.rb', line 70

def build_edges
  result = EDGE_KINDS.to_h { |kind| [kind, []] }
  @grammar.productions.each do |production|
    add_production_edges(result, production)
  end
  result.each_value { |edges| edges.sort_by!(&:sort_key) }
  result
end

#edge(source, target, kind, production, position) ⇒ Edge

RBS:

  • (Integer source, Integer target, Symbol kind, IR::Production production, Integer position) -> Edge

Parameters:

  • source (Integer)
  • target (Integer)
  • kind (Symbol)
  • production (IR::Production)
  • position (Integer)

Returns:



121
122
123
 
# File 'lib/ibex/impact/graph.rb', line 121

def edge(source, target, kind, production, position)
  Edge.new(source: source, target: target, kind: kind, production: production.id, position: position)
end

#edges(kind = :all) ⇒ Object

RBS:

  • (?Symbol kind) -> untyped

Parameters:

  • kind (Symbol) (defaults to: :all)

Returns:

  • (Object) 


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

def edges(kind = :all)
  selected = KIND_ALIASES.fetch(kind.to_sym) { raise ArgumentError, "unknown impact edge kind #{kind}" }
  return selected.flat_map { |name| @edges.fetch(name) }.sort_by(&:sort_key) if selected.length > 1

  @edges.fetch(selected.fetch(0))
end

#freeze_edges ⇒ void

This method returns an undefined value.

RBS:

  • () -> void



126
127
128
129
 
# File 'lib/ibex/impact/graph.rb', line 126

def freeze_edges
  @edges.each_value(&:freeze)
  @edges.freeze
end