Class: Ibex::Codegen::Explain

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

Overview

Renders a selected conflict explanation from Automaton IR and counterexamples. rubocop:disable Metrics/ClassLength -- inline contracts and two stable output formats stay near selection policy.

Constant Summary collapse

SCHEMA_VERSION =

Signature:

  • Integer

Returns:

  • (Integer) 
1

Instance Method Summary collapse

Constructor Details

#initialize(automaton, state: nil, token: nil, max_tokens: LALR::Counterexample::DEFAULT_MAX_TOKENS, max_configurations: LALR::Counterexample::DEFAULT_MAX_CONFIGURATIONS) ⇒ Explain

Returns a new instance of Explain.

RBS:

  • (IR::Automaton automaton, ?state: Integer?, ?token: String?, ?max_tokens: Integer, ?max_configurations: Integer) -> void

Parameters:

  • automaton (IR::Automaton)
  • state: (Integer, nil) (defaults to: nil)
  • token: (String, nil) (defaults to: nil)
  • max_tokens: (Integer) (defaults to: LALR::Counterexample::DEFAULT_MAX_TOKENS)
  • max_configurations: (Integer) (defaults to: LALR::Counterexample::DEFAULT_MAX_CONFIGURATIONS) 


28
29
30
31
32
33
34
35
36
37
38
39
40
 
# File 'lib/ibex/codegen/explain.rb', line 28

def initialize(automaton, state: nil, token: nil, max_tokens: LALR::Counterexample::DEFAULT_MAX_TOKENS,
               max_configurations: LALR::Counterexample::DEFAULT_MAX_CONFIGURATIONS)
  @automaton = automaton
  @grammar = automaton.grammar
  @state_selector = state
  @token_query = token
  @max_tokens = max_tokens
  @max_configurations = max_configurations
  @labels = SymbolLabels.build(@grammar)
  @token_selector = resolve_token(token)
  validate_state!
  @entries = select_entries
end

Instance Method Details

#alternative_text(alternative) ⇒ String

RBS:

  • (Hash[Symbol, untyped] alternative) -> String

Parameters:

  • alternative (Hash[Symbol, untyped])

Returns:

  • (String) 


272
273
274
275
276
 
# File 'lib/ibex/codegen/explain.rb', line 272

def alternative_text(alternative)
  return "shift to state #{alternative.fetch(:state)}" if alternative.fetch(:kind) == "shift"

  "reduce by production #{alternative.fetch(:production)}"
end

#append_conflict(lines, entry, number) ⇒ void

This method returns an undefined value.

RBS:

  • (Array[String] lines, explain_entry entry, Integer number) -> void

Parameters:

  • lines (Array[String])
  • entry (explain_entry)
  • number (Integer) 


221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
 
# File 'lib/ibex/codegen/explain.rb', line 221

def append_conflict(lines, entry, number)
  state = entry.fetch(:state)
  conflict = entry.fetch(:conflict)
  example = entry.fetch(:example)
  token = @grammar.symbol(conflict.fetch(:symbol))
  token_text = token ? token_label(token) : conflict.fetch(:symbol)
  type = conflict.fetch(:type).to_s.tr("_", "/")
  lines << "Conflict #{number}: state #{state.id}, #{type}, token #{token_text}"
  append_midrule_origins(lines, conflict)
  append_witness_steps(lines, state, conflict, example)
  append_interpretations(lines, example)
  unless example.fetch(:unifying)
    lines << "  The search found no shared sentence within the configured budget; this witness is deterministic."
  end
  lines << ""
end

#append_interpretations(lines, example) ⇒ void

This method returns an undefined value.

RBS:

  • (Array[String] lines, IR::counterexample example) -> void

Parameters:

  • lines (Array[String])
  • example (IR::counterexample) 


263
264
265
266
267
268
269
 
# File 'lib/ibex/codegen/explain.rb', line 263

def append_interpretations(lines, example)
  lines << "  Competing derivations:"
  example.fetch(:interpretations).each_with_index do |interpretation, index|
    lines << "    #{index + 1}. #{interpretation.fetch(:kind)}"
    append_tree(lines, interpretation.fetch(:tree), "       ", "")
  end
end

#append_midrule_origins(lines, conflict) ⇒ void

This method returns an undefined value.

RBS:

  • (Array[String] lines, IR::conflict conflict) -> void

Parameters:

  • lines (Array[String])
  • conflict (IR::conflict) 


239
240
241
242
243
244
245
246
 
# File 'lib/ibex/codegen/explain.rb', line 239

def append_midrule_origins(lines, conflict)
  origins = conflict[:midrule_origins]
  return unless origins

  origins.each do |origin|
    lines << "  Midrule action origin: #{origin.fetch(:file)}:#{origin.fetch(:line)}:#{origin.fetch(:column)}"
  end
end

#append_tree(lines, tree, prefix, connector) ⇒ void

This method returns an undefined value.

RBS:

  • (Array[String] lines, untyped tree, String prefix, String connector) -> void

Parameters:

  • lines (Array[String])
  • tree (Object)
  • prefix (String)
  • connector (String) 


279
280
281
282
283
284
285
286
287
288
289
290
291
292
293
294
295
 
# File 'lib/ibex/codegen/explain.rb', line 279

def append_tree(lines, tree, prefix, connector)
  unless tree.is_a?(Hash)
    lines << "#{prefix}#{connector}#{display_name(tree.to_s)}"
    return
  end

  name = tree[:symbol] || tree[:token]
  production = tree[:production] ? " (production #{tree[:production]})" : ""
  lines << "#{prefix}#{connector}#{display_name(name.to_s)}#{production}"
  children = tree.fetch(:children, [])
  continuation = { "" => "", "|- " => "|  " }.fetch(connector, "   ")
  child_prefix = "#{prefix}#{continuation}"
  children.each_with_index do |child, index|
    branch = index == children.length - 1 ? "`- " : "|- "
    append_tree(lines, child, child_prefix, branch)
  end
end

#append_witness_steps(lines, state, conflict, example) ⇒ void

This method returns an undefined value.

RBS:

  • (Array[String] lines, IR::AutomatonState state, IR::conflict conflict, IR::counterexample example) -> void

Parameters:

  • lines (Array[String])
  • state (IR::AutomatonState)
  • conflict (IR::conflict)
  • example (IR::counterexample) 


250
251
252
253
254
255
256
257
258
259
260
 
# File 'lib/ibex/codegen/explain.rb', line 250

def append_witness_steps(lines, state, conflict, example)
  lines << "  1. Reach state #{state.id} with the witness prefix."
  sentence = example.fetch(:sentence).map { |name| display_name(name) }
  sentence.insert(example.fetch(:lookahead_index), "•")
  kind = example.fetch(:unifying) ? "Unifying counterexample" : "Nonunifying reachability witness"
  lines << "     #{kind}: #{sentence.join(' ')}"
  lines << "  2. The lookahead permits these competing actions:"
  conflict_alternatives(conflict).each { |alternative| lines << "     - #{alternative_text(alternative)}" }
  resolution = conflict.fetch(:resolution)
  lines << "  3. Resolution: #{resolution.fetch(:by)} chose #{resolution.fetch(:chose)}."
end

#conflict_alternatives(conflict) ⇒ Array[Hash[Symbol, untyped]]

RBS:

  • (IR::conflict conflict) -> Array[Hash[Symbol, untyped]]

Parameters:

  • conflict (IR::conflict)

Returns:

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


165
166
167
168
169
170
171
172
173
174
175
176
 
# File 'lib/ibex/codegen/explain.rb', line 165

def conflict_alternatives(conflict)
  case conflict[:type]
  when :shift_reduce
    [{ kind: "shift", state: conflict.fetch(:shift_to) },
     { kind: "reduce", production: conflict.fetch(:reduce) }]
  when :reduce_reduce
    reduce_reduce = conflict #: IR::reduce_reduce_conflict
    reduce_reduce[:reductions].map { |production| { kind: "reduce", production: production } }
  else
    []
  end
end

#conflict_document(entry) ⇒ Hash[Symbol, untyped]

RBS:

  • (explain_entry entry) -> Hash[Symbol, untyped]

Parameters:

  • entry (explain_entry)

Returns:

  • (Hash[Symbol, untyped]) 


142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
 
# File 'lib/ibex/codegen/explain.rb', line 142

def conflict_document(entry)
  state = entry.fetch(:state)
  conflict = entry.fetch(:conflict)
  example = entry.fetch(:example)
  document = {
    state: state.id,
    type: conflict.fetch(:type).to_s,
    token: symbol_reference(conflict.fetch(:symbol)),
    alternatives: conflict_alternatives(conflict),
    resolution: string_values(conflict.fetch(:resolution)),
    witness: {
      kind: example.fetch(:unifying) ? "unifying_counterexample" : "nonunifying_witness",
      sentence: example.fetch(:sentence).map { |name| symbol_reference(name) },
      lookahead_index: example.fetch(:lookahead_index),
      symbol_path: example.fetch(:symbol_path).map { |name| symbol_reference(name) },
      interpretations: example.fetch(:interpretations).map { |item| interpretation_document(item) }
    }
  } #: Hash[Symbol, untyped]
  document[:midrule_origins] = conflict[:midrule_origins] if conflict[:midrule_origins]
  document
end

#display_name(name) ⇒ String

RBS:

  • (String name) -> String

Parameters:

  • name (String)

Returns:

  • (String) 


308
 
# File 'lib/ibex/codegen/explain.rb', line 308

def display_name(name) = @grammar.symbol(name)&.then { |symbol| @labels.fetch(symbol.id, symbol.name) } || name

#interpretation_document(interpretation) ⇒ Hash[Symbol, untyped]

RBS:

  • (IR::interpretation interpretation) -> Hash[Symbol, untyped]

Parameters:

  • interpretation (IR::interpretation)

Returns:

  • (Hash[Symbol, untyped]) 


179
180
181
182
183
184
185
 
# File 'lib/ibex/codegen/explain.rb', line 179

def interpretation_document(interpretation)
  value = { kind: interpretation.fetch(:kind).to_s,
            tree: tree_document(interpretation.fetch(:tree)) } #: Hash[Symbol, untyped]
  value[:state] = interpretation[:state] if interpretation.key?(:state)
  value[:production] = interpretation[:production] if interpretation.key?(:production)
  value
end

#render_text ⇒ String

RBS:

  • () -> String

Returns:

  • (String) 


64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
 
# File 'lib/ibex/codegen/explain.rb', line 64

def render_text
  lines = [
    "Ibex conflict explanation v#{SCHEMA_VERSION}",
    "Algorithm: #{@automaton.algorithm}",
    "State selector: #{@state_selector || 'all'}",
    "Token selector: #{@token_selector ? token_label(@token_selector, query: @token_query) : 'all'}",
    "Search budget: #{@max_tokens} tokens, #{@max_configurations} configurations",
    "Matched conflicts: #{@entries.length}",
    ""
  ]
  if @entries.empty?
    lines << "No conflicts matched the selectors."
  else
    @entries.each_with_index { |entry, index| append_conflict(lines, entry, index + 1) }
  end
  "#{lines.join("\n")}\n"
end

#resolve_token(query) ⇒ IR::GrammarSymbol?

RBS:

  • (String? query) -> IR::GrammarSymbol?

Parameters:

  • query (String, nil)

Returns:



85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
 
# File 'lib/ibex/codegen/explain.rb', line 85

def resolve_token(query)
  return unless query

  canonical = @grammar.terminals.find { |symbol| symbol.name == query }
  return canonical if canonical

  displayed = @grammar.terminals.select { |symbol| symbol.display_name == query }
  return displayed.first if displayed.one?

  if displayed.length > 1
    names = displayed.map(&:name).sort.join(", ")
    raise Ibex::Error, "(cli):1:1: token display name #{query.inspect} is ambiguous; use one of: #{names}"
  end

  raise Ibex::Error,
        "(cli):1:1: unknown token #{query.inspect}; use a grammar token name or an exact display name"
end

#select_entries ⇒ Array[explain_entry]

RBS:

  • () -> Array[explain_entry]

Returns:

  • (Array[explain_entry]) 


112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
 
# File 'lib/ibex/codegen/explain.rb', line 112

def select_entries
  selections = selected_conflicts
  return [] if selections.empty?

  counterexamples = LALR::Counterexample.new(
    @automaton, max_tokens: @max_tokens, max_configurations: @max_configurations
  )
  selections.map do |selection|
    state = selection.fetch(:state)
    {
      state: state,
      conflict: selection.fetch(:conflict),
      example: counterexamples.for_conflict(state.id, selection.fetch(:conflict_index))
    }
  end
end

#selected_conflicts ⇒ Array[explain_selection]

RBS:

  • () -> Array[explain_selection]

Returns:

  • (Array[explain_selection]) 


130
131
132
133
134
135
136
137
138
139
 
# File 'lib/ibex/codegen/explain.rb', line 130

def selected_conflicts
  @automaton.states.flat_map do |state|
    state.conflicts.each_with_index.filter_map do |conflict, conflict_index|
      next if @state_selector && state.id != @state_selector
      next if @token_selector && conflict[:symbol] != @token_selector.name

      { state: state, conflict: conflict, conflict_index: conflict_index }
    end
  end
end

#string_values(value) ⇒ Hash[Symbol, untyped]

RBS:

  • (Hash[Symbol, untyped] value) -> Hash[Symbol, untyped]

Parameters:

  • value (Hash[Symbol, untyped])

Returns:

  • (Hash[Symbol, untyped]) 


200
201
202
 
# File 'lib/ibex/codegen/explain.rb', line 200

def string_values(value)
  value.transform_values { |item| item.is_a?(Symbol) ? item.to_s : item }
end

#symbol_reference(name) ⇒ Hash[Symbol, untyped]

RBS:

  • (String name) -> Hash[Symbol, untyped]

Parameters:

  • name (String)

Returns:

  • (Hash[Symbol, untyped]) 


205
206
207
208
209
210
 
# File 'lib/ibex/codegen/explain.rb', line 205

def symbol_reference(name)
  symbol = @grammar.symbol(name)
  return { name: name, display_name: nil, label: name } unless symbol

  token_reference(symbol)
end

#to_h ⇒ Hash[Symbol, untyped]

RBS:

  • () -> Hash[Symbol, untyped]

Returns:

  • (Hash[Symbol, untyped]) 


43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
 
# File 'lib/ibex/codegen/explain.rb', line 43

def to_h
  unifying = @entries.count { |entry| entry.fetch(:example).fetch(:unifying) }
  {
    ibex_explain: "conflicts",
    schema_version: SCHEMA_VERSION,
    algorithm: @automaton.algorithm,
    selectors: {
      state: @state_selector,
      token: @token_selector && token_reference(@token_selector, query: @token_query)
    },
    search: { max_tokens: @max_tokens, max_configurations: @max_configurations },
    summary: {
      matched_conflicts: @entries.length,
      unifying_counterexamples: unifying,
      nonunifying_witnesses: @entries.length - unifying
    },
    conflicts: @entries.map { |entry| conflict_document(entry) }
  }
end

#token_label(symbol, query: nil) ⇒ String

RBS:

  • (IR::GrammarSymbol symbol, ?query: String?) -> String

Parameters:

Returns:

  • (String) 


298
299
300
301
302
303
304
305
 
# File 'lib/ibex/codegen/explain.rb', line 298

def token_label(symbol, query: nil)
  label = if symbol.display_name && symbol.display_name != symbol.name
            "#{symbol.name} (display #{symbol.display_name.inspect})"
          else
            symbol.name
          end
  query && query != symbol.name ? "#{label}, selected by #{query.inspect}" : label
end

#token_reference(symbol, query: nil) ⇒ Hash[Symbol, untyped]

RBS:

  • (IR::GrammarSymbol symbol, ?query: String?) -> Hash[Symbol, untyped]

Parameters:

Returns:

  • (Hash[Symbol, untyped]) 


213
214
215
216
217
218
 
# File 'lib/ibex/codegen/explain.rb', line 213

def token_reference(symbol, query: nil)
  value = { name: symbol.name, display_name: symbol.display_name,
            label: @labels.fetch(symbol.id, symbol.name) } #: Hash[Symbol, untyped]
  value[:query] = query if query
  value
end

#tree_document(tree) ⇒ Object

RBS:

  • (untyped tree) -> untyped

Parameters:

  • tree (Object)

Returns:

  • (Object) 


188
189
190
191
192
193
194
195
196
197
 
# File 'lib/ibex/codegen/explain.rb', line 188

def tree_document(tree)
  return symbol_reference(tree.to_s) unless tree.is_a?(Hash)

  value = {} #: Hash[Symbol, untyped]
  value[:symbol] = symbol_reference(tree[:symbol]) if tree[:symbol]
  value[:token] = symbol_reference(tree[:token]) if tree[:token]
  value[:production] = tree[:production] if tree[:production]
  value[:children] = tree[:children].map { |child| tree_document(child) } if tree[:children]
  value
end

#validate_state! ⇒ void

This method returns an undefined value.

RBS:

  • () -> void



104
105
106
107
108
109
 
# File 'lib/ibex/codegen/explain.rb', line 104

def validate_state!
  return unless @state_selector
  return if @state_selector >= 0 && @automaton.states.any? { |state| state.id == @state_selector }

  raise Ibex::Error, "(cli):1:1: unknown automaton state #{@state_selector}"
end