Module: Ibex::NormalizeInlineValidation

Included in:
Normalizer
Defined in:
lib/ibex/normalize/inline_validation.rb,
sig/ibex/normalize/inline_validation.rbs

Overview

Static validation and collection for rules eliminated by inline expansion.

Instance Method Summary collapse

Instance Method Details

#collect_inline_edges(item, formals, names, edges, liveness) ⇒ void

This method returns an undefined value.

Structural AST traversal necessarily branches once for each public item shape. rubocop:disable Metrics/CyclomaticComplexity

RBS:

  • (Frontend::AST::item item, Array[String] formals, Set[String] names, Array[[String, Frontend::Location]] edges, Hash[String, Set[Integer]] liveness) -> void

Parameters:

  • item (Frontend::AST::item)
  • formals (Array[String])
  • names (Set[String])
  • edges (Array[[ String, Frontend::Location ]])
  • liveness (Hash[String, Set[Integer]]) 


116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
 
# File 'lib/ibex/normalize/inline_validation.rb', line 116

def collect_inline_edges(item, formals, names, edges, liveness)
  # @type self: Normalizer
  case item
  when Frontend::AST::SymbolReference
    edges << [item.name, item.loc] if !formals.include?(item.name) && names.include?(item.name)
  when Frontend::AST::ParameterizedReference
    edges << [item.name, item.loc] if names.include?(item.name)
    liveness.fetch(item.name, Set.new).each do |index|
      collect_inline_edges(item.arguments.fetch(index), formals, names, edges, liveness)
    end
  when Frontend::AST::Group
    item.alternatives.flatten.each do |child|
      collect_inline_edges(child, formals, names, edges, liveness)
    end
  when Frontend::AST::Optional, Frontend::AST::Star, Frontend::AST::Plus
    collect_inline_edges(item.item, formals, names, edges, liveness)
  when Frontend::AST::SeparatedList
    collect_inline_edges(item.item, formals, names, edges, liveness)
    collect_inline_edges(item.separator, formals, names, edges, liveness)
  end
end

#collect_live_formals(item, formals, liveness, found) ⇒ void

This method returns an undefined value.

RBS:

  • (Frontend::AST::item item, Array[String] formals, Hash[String, Set[Integer]] liveness, Set[Integer] found) -> void

Parameters:

  • item (Frontend::AST::item)
  • formals (Array[String])
  • liveness (Hash[String, Set[Integer]])
  • found (Set[Integer]) 


92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
 
# File 'lib/ibex/normalize/inline_validation.rb', line 92

def collect_live_formals(item, formals, liveness, found)
  # @type self: Normalizer
  case item
  when Frontend::AST::SymbolReference
    index = formals.index(item.name)
    found << index if index
  when Frontend::AST::ParameterizedReference
    liveness.fetch(item.name, Set.new).each do |index|
      collect_live_formals(item.arguments.fetch(index), formals, liveness, found)
    end
  when Frontend::AST::Group
    item.alternatives.flatten.each { |child| collect_live_formals(child, formals, liveness, found) }
  when Frontend::AST::Optional, Frontend::AST::Star, Frontend::AST::Plus
    collect_live_formals(item.item, formals, liveness, found)
  when Frontend::AST::SeparatedList
    collect_live_formals(item.item, formals, liveness, found)
    collect_live_formals(item.separator, formals, liveness, found)
  end
end

#gather_inline_rules ⇒ void

This method returns an undefined value.

RBS:

  • () -> void



9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
 
# File 'lib/ibex/normalize/inline_validation.rb', line 9

def gather_inline_rules
  # @type self: Normalizer
  @inline_rule_names = Set.new #: Set[String]
  markings = {} #: Hash[String, bool]
  @ast.rules.each do |rule|
    previous = markings[rule.lhs]
    if !previous.nil? && previous != rule.inline
      fail_at(rule.loc, "rule #{rule.lhs} has both inline and ordinary definitions")
    end
    markings[rule.lhs] = rule.inline
    @inline_rule_names << rule.lhs if rule.inline
  end
  validate_inline_terminal_collisions
  validate_inline_start
  validate_inline_cycles
end

#parameter_formal_liveness ⇒ Hash[String, Set[Integer]]

A formal is live for cycle analysis only when substituting its actual can introduce a grammar reference. Calls propagate liveness through their callee's live positions until the finite formal set reaches a fixed point.

RBS:

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

Returns:

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


67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
 
# File 'lib/ibex/normalize/inline_validation.rb', line 67

def parameter_formal_liveness
  # @type self: Normalizer
  liveness = @parameter_formals.to_h { |name, _formals| [name, Set.new] } #: Hash[String, Set[Integer]]
  loop do
    changed = false
    @parameter_templates.each do |name, rules|
      formals = @parameter_formals.fetch(name)
      found = Set.new #: Set[Integer]
      rules.each do |rule|
        rule.alternatives.each do |alternative|
          alternative.items.each { |item| collect_live_formals(item, formals, liveness, found) }
        end
      end
      additions = found - liveness.fetch(name)
      next if additions.empty?

      liveness.fetch(name).merge(additions)
      changed = true
    end
    return liveness unless changed
  end
end

#validate_inline_cycles ⇒ void

This method returns an undefined value.

RBS:

  • () -> void



47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
 
# File 'lib/ibex/normalize/inline_validation.rb', line 47

def validate_inline_cycles
  # @type self: Normalizer
  names = @ast.rules.to_set(&:lhs)
  liveness = parameter_formal_liveness
  graph = Hash.new { |hash, name| hash[name] = [] } #: Hash[String, Array[[String, Frontend::Location]]]
  @ast.rules.each do |rule|
    rule.alternatives.each do |alternative|
      alternative.items.each do |item|
        collect_inline_edges(item, rule.parameters, names, graph[rule.lhs], liveness)
      end
    end
  end
  states = {} #: Hash[String, Symbol]
  names.each { |name| visit_inline_cycle(name, graph, states) unless states.key?(name) }
end

#validate_inline_start ⇒ void

This method returns an undefined value.

RBS:

  • () -> void



38
39
40
41
42
43
44
 
# File 'lib/ibex/normalize/inline_validation.rb', line 38

def validate_inline_start
  # @type self: Normalizer
  inline_start = @explicit_starts&.find { |name| @inline_rule_names.include?(name) }
  return unless inline_start

  fail_at(@start_location || @ast.loc, "inline rule #{inline_start} cannot be the start symbol")
end

#validate_inline_terminal_collisions ⇒ void

This method returns an undefined value.

RBS:

  • () -> void



27
28
29
30
31
32
33
34
35
 
# File 'lib/ibex/normalize/inline_validation.rb', line 27

def validate_inline_terminal_collisions
  # @type self: Normalizer
  @ast.rules.each do |rule|
    next unless rule.inline
    next unless @declared_tokens.key?(rule.lhs) || @precedence.key?(rule.lhs)

    fail_at(rule.loc, "inline rule #{rule.lhs} collides with terminal #{rule.lhs}")
  end
end

#visit_inline_cycle(name, graph, states) ⇒ void

This method returns an undefined value.

RBS:

  • (String name, Hash[String, Array[[String, Frontend::Location]]] graph, Hash[String, Symbol] states) -> void

Parameters:

  • name (String)
  • graph (Hash[String, Array[[ String, Frontend::Location ]]])
  • states (Hash[String, Symbol]) 


141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
 
# File 'lib/ibex/normalize/inline_validation.rb', line 141

def visit_inline_cycle(name, graph, states)
  # @type self: Normalizer
  states[name] = :visiting
  path = [name] #: Array[String]
  positions = { name => 0 } #: Hash[String, Integer]
  worklist = [[name, 0]] #: Array[[String, Integer]]
  until worklist.empty?
    current, edge_index = worklist.fetch(-1)
    edges = graph[current]
    if edge_index >= edges.length
      worklist.pop
      positions.delete(path.pop || raise(Ibex::Error, "internal inline cycle path underflow"))
      states[current] = :visited
      next
    end

    worklist[-1] = [current, edge_index + 1]
    target, location = edges.fetch(edge_index)
    if states[target] == :visiting
      cycle = path.drop(positions.fetch(target))
      next unless cycle.any? { |entry| @inline_rule_names.include?(entry) }

      fail_at(location, "inline expansion cycle: #{(cycle + [target]).join(' -> ')}")
    end
    next if states.key?(target)

    states[target] = :visiting
    positions[target] = path.length
    path << target
    worklist << [target, 0]
  end
end