Class: Ibex::Metrics

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

Overview

Deterministic structural metrics over normalized Grammar and Automaton IR.

Instance Method Summary collapse

Constructor Details

#initialize(automaton) ⇒ Metrics

Returns a new instance of Metrics.

RBS:

  • (IR::Automaton automaton) -> void

Parameters:



13
14
15
16
 
# File 'lib/ibex/metrics.rb', line 13

def initialize(automaton)
  @automaton = automaton
  @grammar = automaton.grammar
end

Instance Method Details

#automaton_metrics ⇒ Hash[Symbol, report_value]

RBS:

  • () -> Hash[Symbol, report_value]

Returns:

  • (Hash[Symbol, report_value]) 


53
54
55
56
57
58
59
60
61
62
63
64
65
66
 
# File 'lib/ibex/metrics.rb', line 53

def automaton_metrics
  {
    states: @automaton.states.length,
    transitions: @automaton.states.sum { |state| state.transitions.length },
    action_cells: @automaton.states.sum { |state| state.actions.length },
    goto_cells: @automaton.states.sum { |state| state.gotos.length },
    default_reductions: @automaton.states.count(&:default_action),
    conflicts: {
      shift_reduce: @automaton.conflict_summary.fetch(:sr),
      precedence_resolved_shift_reduce: @automaton.conflict_summary.fetch(:resolved_sr),
      reduce_reduce: @automaton.conflict_summary.fetch(:rr)
    }
  }
end

#average(values) ⇒ Float

RBS:

  • (Array[Integer] values) -> Float

Parameters:

  • values (Array[Integer])

Returns:

  • (Float) 


69
70
71
72
73
 
# File 'lib/ibex/metrics.rb', line 69

def average(values)
  return 0.0 if values.empty?

  values.sum.fdiv(values.length).round(6)
end

#dependency_graph ⇒ Hash[Integer, Array[Integer]]

RBS:

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

Returns:

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


76
77
78
79
80
81
82
83
84
85
86
87
88
 
# File 'lib/ibex/metrics.rb', line 76

def dependency_graph
  @dependency_graph ||= begin
    graph = {} #: Hash[Integer, Array[Integer]]
    @grammar.nonterminals.each { |symbol| graph[symbol.id] = [] }
    @grammar.productions.each do |production|
      production.rhs.each do |id|
        symbol = @grammar.symbol_by_id(id)
        graph.fetch(production.lhs) << id if symbol&.nonterminal?
      end
    end
    graph.transform_values { |targets| targets.uniq.sort }
  end
end

#grammar_metrics ⇒ Hash[Symbol, report_value]

RBS:

  • () -> Hash[Symbol, report_value]

Returns:

  • (Hash[Symbol, report_value]) 


38
39
40
41
42
43
44
45
46
47
48
49
50
 
# File 'lib/ibex/metrics.rb', line 38

def grammar_metrics
  rule_counts = @grammar.productions.group_by(&:lhs).transform_values(&:length)
  {
    rules: rule_counts.length,
    alternatives: @grammar.productions.length,
    average_alternatives_per_rule: average(rule_counts.values),
    maximum_branching: rule_counts.values.max || 0,
    epsilon_productions: @grammar.productions.count { |production| production.rhs.empty? },
    recursive_nonterminals: recursive_nonterminal_ids.map { |id| symbol_name(id) }.sort,
    recursion_component_depth: recursion_component_depth,
    warnings: @grammar.warnings.length
  }
end

#longest_dag_path(edges) ⇒ Integer

RBS:

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

Parameters:

  • edges (Array[Set[Integer]])

Returns:

  • (Integer) 


152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
 
# File 'lib/ibex/metrics.rb', line 152

def longest_dag_path(edges)
  indegree = Array.new(edges.length, 0)
  edges.each { |targets| targets.each { |target| indegree[target] += 1 } }
  depths = Array.new(edges.length, 1)
  queue = indegree.each_index.select { |index| indegree[index].zero? }
  cursor = 0
  while cursor < queue.length
    source = queue.fetch(cursor)
    edges.fetch(source).each do |target|
      depths[target] = [depths[target], depths[source] + 1].max
      indegree[target] -= 1
      queue << target if indegree[target].zero?
    end
    cursor += 1
  end
  depths.max || 0
end

#reachability ⇒ Hash[Integer, Set[Integer]]

RBS:

  • () -> Hash[Integer, Set[Integer]]

Returns:

  • (Hash[Integer, Set[Integer]]) 


91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
 
# File 'lib/ibex/metrics.rb', line 91

def reachability
  @reachability ||= dependency_graph.to_h do |source, _targets|
    found = Set[source]
    queue = [source]
    cursor = 0
    while cursor < queue.length
      dependency_graph.fetch(queue.fetch(cursor)).each do |target|
        next if found.include?(target)

        found << target
        queue << target
      end
      cursor += 1
    end
    [source, found]
  end
end

#recursion_component_depth ⇒ Integer

Longest path after collapsing mutually recursive nonterminals.

RBS:

  • () -> Integer

Returns:

  • (Integer) 


136
137
138
139
140
141
142
143
144
145
146
147
148
149
 
# File 'lib/ibex/metrics.rb', line 136

def recursion_component_depth
  components = recursion_components
  component_for = {} #: Hash[Integer, Integer]
  components.each_with_index { |ids, index| ids.each { |id| component_for[id] = index } }
  edges = Array.new(components.length) { Set.new } #: Array[Set[Integer]]
  dependency_graph.each do |source, targets|
    targets.each do |target|
      from = component_for.fetch(source)
      to = component_for.fetch(target)
      edges.fetch(from) << to unless from == to
    end
  end
  longest_dag_path(edges)
end

#recursion_components ⇒ Array[Array[Integer]]

RBS:

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

Returns:

  • (Array[Array[Integer]]) 


110
111
112
113
114
115
116
117
118
119
120
121
122
 
# File 'lib/ibex/metrics.rb', line 110

def recursion_components
  remaining = dependency_graph.keys.sort
  components = [] #: Array[Array[Integer]]
  until remaining.empty?
    source = remaining.fetch(0)
    component = remaining.select do |candidate|
      reachability.fetch(source).include?(candidate) && reachability.fetch(candidate).include?(source)
    end
    components << component
    remaining -= component
  end
  components
end

#recursive_nonterminal_ids ⇒ Array[Integer]

RBS:

  • () -> Array[Integer]

Returns:

  • (Array[Integer]) 


125
126
127
128
129
130
131
132
 
# File 'lib/ibex/metrics.rb', line 125

def recursive_nonterminal_ids
  recursion_components.flat_map do |component|
    next component if component.length > 1

    id = component.fetch(0)
    dependency_graph.fetch(id).include?(id) ? component : []
  end
end

#symbol_metrics ⇒ Hash[Symbol, Integer]

RBS:

  • () -> Hash[Symbol, Integer]

Returns:

  • (Hash[Symbol, Integer]) 


33
34
35
 
# File 'lib/ibex/metrics.rb', line 33

def symbol_metrics
  { terminals: @grammar.terminals.length, nonterminals: @grammar.nonterminals.length }
end

#symbol_name(id) ⇒ String

RBS:

  • (Integer id) -> String

Parameters:

  • id (Integer)

Returns:

  • (String) 


171
172
173
 
# File 'lib/ibex/metrics.rb', line 171

def symbol_name(id)
  @grammar.symbol_by_id(id)&.name || id.to_s
end

#to_h ⇒ Hash[Symbol, report_value]

RBS:

  • () -> Hash[Symbol, report_value]

Returns:

  • (Hash[Symbol, report_value]) 


19
20
21
22
23
24
25
26
27
28
 
# File 'lib/ibex/metrics.rb', line 19

def to_h
  {
    ibex_report: "metrics", schema_version: 1,
    algorithm: @automaton.algorithm,
    grammar_digest: @automaton.grammar_digest,
    symbols: symbol_metrics,
    grammar: grammar_metrics,
    automaton: automaton_metrics
  }
end