Class: Ibex::ErrorMessages::SentenceSearch

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

Overview

Finds deterministic shortest token sentences that reach each syntax error state without running semantic actions.

Defined Under Namespace

Classes: Witness

Constant Summary collapse

DEFAULT_MAX_TOKENS =

Signature:

  • Integer

Returns:

  • (Integer) 
LALR::ConflictSearchLimits::DEFAULT_MAX_TOKENS
DEFAULT_MAX_CONFIGURATIONS =

Signature:

  • Integer

Returns:

  • (Integer) 
LALR::ConflictSearchLimits::DEFAULT_MAX_CONFIGURATIONS

Instance Method Summary collapse

Constructor Details

#initialize(automaton, max_tokens: DEFAULT_MAX_TOKENS, max_configurations: DEFAULT_MAX_CONFIGURATIONS) ⇒ SentenceSearch

Returns a new instance of SentenceSearch.

RBS:

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

Parameters:

  • automaton (IR::Automaton)
  • max_tokens: (Integer) (defaults to: DEFAULT_MAX_TOKENS)
  • max_configurations: (Integer) (defaults to: DEFAULT_MAX_CONFIGURATIONS) 


29
30
31
32
33
34
35
36
37
38
39
40
41
 
# File 'lib/ibex/error_messages/sentence_search.rb', line 29

def initialize(automaton, max_tokens: DEFAULT_MAX_TOKENS,
               max_configurations: DEFAULT_MAX_CONFIGURATIONS)
  LALR::ConflictSearchLimits.validate!(
    max_tokens: max_tokens, max_configurations: max_configurations
  )
  @automaton = automaton
  @grammar = automaton.grammar
  @max_tokens = max_tokens
  @max_configurations = max_configurations
  @candidates = grammar_terminals
  @input_candidates = @candidates.reject { |symbol| symbol.id.zero? }
  @explored = 0
end

Instance Method Details

#advance(initial, token_id) ⇒ [ Symbol, Array[Integer] | Integer | nil ]

RBS:

  • (Array[Integer] initial, Integer token_id) -> [Symbol, Array[Integer] | Integer | nil]

Parameters:

  • initial (Array[Integer])
  • token_id (Integer)

Returns:

  • ([ Symbol, Array[Integer] | Integer | nil ]) 


149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
 
# File 'lib/ibex/error_messages/sentence_search.rb', line 149

def advance(initial, token_id)
  states = initial
  visited = {} #: Hash[Array[Integer], bool]
  loop do
    return [:invalid, nil] if visited[states]

    visited[states] = true
    state = @automaton.states.fetch(states.last)
    action = state.actions[token_id] || state.default_action
    return [:error, state.id] if action.nil? || action[:type] == :error

    case action[:type]
    when :shift
      shift = action #: IR::shift_action
      return [:shift, (states + [shift[:state]]).freeze]
    when :reduce
      reduce = action #: IR::reduce_action
      states = reduce_stack(states, reduce[:production])
      return [:invalid, nil] unless states
    when :accept
      return [:accept, nil]
    else
      return [:invalid, nil]
    end
  end
end

#all ⇒ Hash[Integer, Witness]

RBS:

  • () -> Hash[Integer, Witness]

Returns:



44
45
46
47
48
49
50
51
52
 
# File 'lib/ibex/error_messages/sentence_search.rb', line 44

def all
  targets = ErrorMessages.error_states(@automaton).to_h { |state| [state.id, true] }
  witnesses = {} #: Hash[Integer, Witness]
  @automaton.entry_states.each do |entry, initial_state|
    search_entry(entry, initial_state, targets, witnesses)
    break if witnesses.length == targets.length
  end
  witnesses.sort.to_h.freeze
end

#collect_errors(entry, states, prefix, targets, witnesses) ⇒ void

This method returns an undefined value.

RBS:

  • (String entry, Array[Integer] states, Array[String] prefix, Hash[Integer, bool] targets, Hash[Integer, Witness] witnesses) -> void

Parameters:

  • entry (String)
  • states (Array[Integer])
  • prefix (Array[String])
  • targets (Hash[Integer, bool])
  • witnesses (Hash[Integer, Witness]) 


119
120
121
122
123
124
125
126
127
128
129
130
131
 
# File 'lib/ibex/error_messages/sentence_search.rb', line 119

def collect_errors(entry, states, prefix, targets, witnesses)
  @candidates.each do |symbol|
    status, state = advance(states, symbol.id)
    next unless status == :error && state.is_a?(Integer)

    error_state = state #: Integer
    next unless targets[error_state] && !witnesses[error_state]

    witnesses[error_state] = Witness.new(
      entry: entry, tokens: (prefix + [symbol.name]).freeze, state: error_state
    ).freeze
  end
end

#consume_sentence_token(states, name, final) ⇒ [ Symbol, Array[Integer] | Integer | nil ]

RBS:

  • (Array[Integer] states, String name, bool final) -> [Symbol, Array[Integer] | Integer | nil]

Parameters:

  • states (Array[Integer])
  • name (String)
  • final (Boolean)

Returns:

  • ([ Symbol, Array[Integer] | Integer | nil ]) 


77
78
79
80
81
82
83
84
85
86
 
# File 'lib/ibex/error_messages/sentence_search.rb', line 77

def consume_sentence_token(states, name, final)
  symbol = sentence_symbol(name, final)
  return [:invalid, nil] unless symbol

  status, value = advance(states, symbol.id)
  return [:error, value] if status == :error && final && value.is_a?(Integer)
  return [:continue, value] if status == :shift && value.is_a?(Array)

  [:invalid, nil]
end

#count_configuration! ⇒ void

This method returns an undefined value.

RBS:

  • () -> void



187
188
189
190
191
192
193
 
# File 'lib/ibex/error_messages/sentence_search.rb', line 187

def count_configuration!
  @explored += 1
  return if @explored <= @max_configurations

  raise Ibex::Error,
        "(messages):1:1: error-sentence search exceeded #{@max_configurations} configurations"
end

#enqueue_shifts(queue, visited, states, prefix) ⇒ void

This method returns an undefined value.

RBS:

  • (Array[[Array[Integer], Array[String]]] queue, Hash[Array[Integer], bool] visited, Array[Integer] states, Array[String] prefix) -> void

Parameters:

  • queue (Array[[ Array[Integer], Array[String] ]])
  • visited (Hash[Array[Integer], bool])
  • states (Array[Integer])
  • prefix (Array[String]) 


135
136
137
138
139
140
141
142
143
144
145
146
 
# File 'lib/ibex/error_messages/sentence_search.rb', line 135

def enqueue_shifts(queue, visited, states, prefix)
  @input_candidates.each do |symbol|
    status, shifted = advance(states, symbol.id)
    next unless status == :shift && shifted.is_a?(Array)

    shifted_states = shifted #: Array[Integer]
    next if visited[shifted_states]

    visited[shifted_states] = true
    queue << [shifted_states, prefix + [symbol.name]]
  end
end

#grammar_terminals ⇒ Array[IR::GrammarSymbol]

RBS:

  • () -> Array[IR::GrammarSymbol]

Returns:



98
99
100
101
102
 
# File 'lib/ibex/error_messages/sentence_search.rb', line 98

def grammar_terminals
  @grammar.terminals
          .reject { |symbol| symbol.name == "error" }
          .sort_by { |symbol| [symbol.id.zero? ? 1 : 0, symbol.name] }
end

#reduce_stack(states, production_id) ⇒ Array[Integer]?

RBS:

  • (Array[Integer] states, Integer production_id) -> Array[Integer]?

Parameters:

  • states (Array[Integer])
  • production_id (Integer)

Returns:

  • (Array[Integer], nil) 


177
178
179
180
181
182
183
184
 
# File 'lib/ibex/error_messages/sentence_search.rb', line 177

def reduce_stack(states, production_id)
  production = @grammar.productions.fetch(production_id)
  return nil if production.rhs.length >= states.length

  remaining = states.take(states.length - production.rhs.length)
  target = @automaton.states.fetch(remaining.last).gotos[production.lhs]
  target && (remaining + [target]).freeze
end

#search_entry(entry, initial_state, targets, witnesses) ⇒ void

This method returns an undefined value.

RBS:

  • (String entry, Integer initial_state, Hash[Integer, bool] targets, Hash[Integer, Witness] witnesses) -> void

Parameters:

  • entry (String)
  • initial_state (Integer)
  • targets (Hash[Integer, bool])
  • witnesses (Hash[Integer, Witness]) 


106
107
108
109
110
111
112
113
114
115
 
# File 'lib/ibex/error_messages/sentence_search.rb', line 106

def search_entry(entry, initial_state, targets, witnesses)
  queue = [[[initial_state], Array.new(0)]] #: Array[[Array[Integer], Array[String]]]
  visited = { [initial_state] => true }
  until queue.empty? || witnesses.length == targets.length
    states, prefix = queue.shift
    count_configuration!
    collect_errors(entry, states, prefix, targets, witnesses)
    enqueue_shifts(queue, visited, states, prefix) if prefix.length < @max_tokens - 1
  end
end

#sentence_symbol(name, final) ⇒ IR::GrammarSymbol?

RBS:

  • (String name, bool final) -> IR::GrammarSymbol?

Parameters:

  • name (String)
  • final (Boolean)

Returns:



89
90
91
92
93
94
95
 
# File 'lib/ibex/error_messages/sentence_search.rb', line 89

def sentence_symbol(name, final)
  symbol = @grammar.symbol(name)
  return nil unless symbol&.terminal?
  return nil if symbol.name == "error" || (symbol.id.zero? && !final)

  symbol
end

#state_for(tokens, entry: nil) ⇒ Integer?

RBS:

  • (Array[String] tokens, ?entry: String?) -> Integer?

Parameters:

  • tokens (Array[String])
  • entry: (String, nil) (defaults to: nil)

Returns:

  • (Integer, nil) 


55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
 
# File 'lib/ibex/error_messages/sentence_search.rb', line 55

def state_for(tokens, entry: nil)
  return nil if tokens.empty?

  start = entry || @grammar.start
  initial = @automaton.entry_states[start]
  return nil unless initial

  states = [initial]
  tokens.each_with_index do |name, index|
    status, value = consume_sentence_token(states, name, index == tokens.length - 1)
    return value if status == :error && value.is_a?(Integer)
    return nil unless status == :continue && value.is_a?(Array)

    states = value
  end
  nil
end