Class: Ibex::Verify::ActionCorrespondence

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

Overview

Compares resolved ACTION/GOTO behavior over all paired viable prefixes.

Defined Under Namespace

Classes: Difference, Result

Instance Method Summary collapse

Constructor Details

#initialize(canonical, target, max_pairs: nil) ⇒ ActionCorrespondence

Returns a new instance of ActionCorrespondence.

RBS:

  • (IR::Automaton canonical, IR::Automaton target, ?max_pairs: Integer) -> void

Parameters:



47
48
49
50
51
 
# File 'lib/ibex/verify/action_correspondence.rb', line 47

def initialize(canonical, target, max_pairs: nil)
  @canonical = canonical
  @target = target
  @max_pairs = max_pairs || [canonical.states.length * 8, 1].max
end

Instance Method Details

#action_signature(action) ⇒ Array[Object]

RBS:

  • (IR::parser_action) -> Array[Object]

Parameters:

  • (IR::parser_action)

Returns:

  • (Array[Object]) 


127
128
129
130
131
132
133
134
 
# File 'lib/ibex/verify/action_correspondence.rb', line 127

def action_signature(action)
  case action[:type]
  when :shift then [:shift]
  when :reduce then [:reduce, action[:production]]
  when :accept then [:accept]
  else [:error]
  end
end

#compare_gotos(canonical_id, target_id, canonical_state, target_state, differences, queue) ⇒ void

This method returns an undefined value.

RBS:

  • (Integer, Integer, IR::AutomatonState, IR::AutomatonState, Array[Difference], Array[Array[Integer]]) -> void

Parameters:



106
107
108
109
110
111
112
113
114
115
116
117
118
119
 
# File 'lib/ibex/verify/action_correspondence.rb', line 106

def compare_gotos(canonical_id, target_id, canonical_state, target_state, differences, queue)
  @canonical.grammar.nonterminals.each do |nonterminal|
    left = canonical_state.gotos[nonterminal.id]
    right = target_state.gotos[nonterminal.id]
    if left.nil? != right.nil?
      differences << Difference.new(
        kind: :goto, canonical_state: canonical_id, target_state: target_id,
        symbol: nonterminal.id, canonical: left, target: right
      )
    elsif left && right
      queue << [left, right]
    end
  end
end

#compare_terminals(canonical_id, target_id, canonical_state, target_state, differences, queue) ⇒ void

This method returns an undefined value.

RBS:

  • (Integer, Integer, IR::AutomatonState, IR::AutomatonState, Array[Difference], Array[Array[Integer]]) -> void

Parameters:



90
91
92
93
94
95
96
97
98
99
100
101
102
 
# File 'lib/ibex/verify/action_correspondence.rb', line 90

def compare_terminals(canonical_id, target_id, canonical_state, target_state, differences, queue)
  @canonical.grammar.terminals.each do |terminal|
    left = effective_action(canonical_state, terminal.id)
    right = effective_action(target_state, terminal.id)
    if action_signature(left) != action_signature(right)
      differences << Difference.new(
        kind: :action, canonical_state: canonical_id, target_state: target_id,
        symbol: terminal.id, canonical: left, target: right
      )
    end
    queue << [left[:state], right[:state]] if left[:type] == :shift && right[:type] == :shift
  end
end

#effective_action(state, token_id) ⇒ IR::parser_action

RBS:

  • (IR::AutomatonState, Integer) -> IR::parser_action

Parameters:

Returns:

  • (IR::parser_action) 


122
123
124
 
# File 'lib/ibex/verify/action_correspondence.rb', line 122

def effective_action(state, token_id)
  state.actions.fetch(token_id, state.default_action || { type: :error })
end

#verify ⇒ Result

RBS:

  • () -> Result

Returns:



54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
 
# File 'lib/ibex/verify/action_correspondence.rb', line 54

def verify
  queue = @canonical.entry_states.map do |name, canonical_state|
    [canonical_state, @target.entry_states[name]]
  end
  seen = {}
  differences = []
  truncated = false
  until queue.empty?
    canonical_id, target_id = queue.shift
    key = [canonical_id, target_id]
    next if seen[key]

    if seen.length >= @max_pairs
      truncated = true
      break
    end
    seen[key] = true
    canonical_state = @canonical.states[canonical_id]
    target_state = @target.states[target_id]
    unless canonical_state && target_state
      differences << Difference.new(
        kind: :state, canonical_state: canonical_id, target_state: target_id,
        symbol: nil, canonical: canonical_state, target: target_state
      )
      next
    end
    compare_terminals(canonical_id, target_id, canonical_state, target_state, differences, queue)
    compare_gotos(canonical_id, target_id, canonical_state, target_state, differences, queue)
  end
  Result.new(differences: differences.freeze, explored: seen.length, truncated: truncated)
end