Class: Ibex::Runtime::RepairSearch

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

Overview

Bounded Dijkstra search over LR state stacks. Semantic actions never run. rubocop:disable Metrics/ClassLength -- queue policy and LR transitions form one bounded search invariant.

Defined Under Namespace

Classes: Configuration

Constant Summary collapse

NEED_INPUT =

RBS:

  • type configuration_key = [Array[Integer], Integer, Integer, bool]
type priority = Array[untyped]
type lookup_table = Tables::action_table | Tables::goto_table
type lookup_value = IR::runtime_action | Integer?

Returns:

  • (Object) 
Object.new.freeze
LIMIT =

Signature:

  • Object

Returns:

  • (Object) 
Object.new.freeze

Instance Method Summary collapse

Constructor Details

#initialize(tables, policy, tokens, complete:) ⇒ RepairSearch

Returns a new instance of RepairSearch.

RBS:

  • (Hash[Symbol, Object?] tables, RepairPolicy policy, Array[RepairInput] tokens, complete: bool) -> void

Parameters:



40
41
42
43
44
45
46
47
48
49
50
51
 
# File 'lib/ibex/runtime/repair_search.rb', line 40

def initialize(tables, policy, tokens, complete:)
  @tables = tables
  @policy = policy
  @tokens = tokens
  @complete = complete
  @configurations = 0
  @heap = RepairPriorityQueue.new
  @best = {}
  reserved = [Parser::EOF_TOKEN, Parser::ERROR_TOKEN]
  token_names = tables.fetch(:token_names) #: Hash[Integer, String]
  @candidate_ids = token_names.keys.reject { |id| reserved.include?(id) }.sort.freeze
end

Instance Method Details

#action_for(state, token_id) ⇒ IR::runtime_action

RBS:

  • (Integer state, Integer token_id) -> IR::runtime_action

Parameters:

  • state (Integer)
  • token_id (Integer)

Returns:

  • (IR::runtime_action) 


271
272
273
274
275
276
277
278
 
# File 'lib/ibex/runtime/repair_search.rb', line 271

def action_for(state, token_id)
  actions = @tables.fetch(:actions) #: Tables::action_table
  explicit = action_table_lookup(actions, state, token_id)
  return explicit if explicit

  defaults = @tables.fetch(:default_actions, Parser::EMPTY_ROW) #: Array[IR::runtime_action?]
  defaults[state] || [:error]
end

#action_table_lookup(table, row, column) ⇒ IR::runtime_action?

RBS:

  • (Tables::action_table table, Integer row, Integer column) -> IR::runtime_action?

Parameters:

  • table (Tables::action_table)
  • row (Integer)
  • column (Integer)

Returns:

  • (IR::runtime_action, nil) 


281
282
283
284
285
286
287
288
289
290
 
# File 'lib/ibex/runtime/repair_search.rb', line 281

def action_table_lookup(table, row, column)
  if table.is_a?(Tables::CompactActions)
    value = table.__send__(:lookup, row, column)
    return value #: IR::runtime_action?
  end

  rows = table #: Array[Hash[Integer, IR::runtime_action]]
  empty_row = Parser::EMPTY_ROW #: Hash[Integer, IR::runtime_action]
  rows.fetch(row, empty_row)[column]
end

#advance(stack, token_id) ⇒ RepairAdvance, ...

RBS:

  • (Array[Integer] stack, Integer token_id) -> (RepairAdvance | Object | nil)

Parameters:

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

Returns:



222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
242
243
244
245
246
247
248
249
250
251
 
# File 'lib/ibex/runtime/repair_search.rb', line 222

def advance(stack, token_id)
  states = stack.dup
  seen = {} #: Hash[Array[Integer], bool]
  loop do
    return nil if seen[states]

    seen[states.dup.freeze] = true
    @configurations += 1
    return LIMIT if @configurations > @policy.max_configurations

    action = action_for(states.last, token_id)
    case action.first
    when :shift
      target = action.fetch(1)
      return nil unless target.is_a?(Integer)

      states << target
      return nil if states.length > @policy.max_stack

      return RepairAdvance.new(status: :shift, stack: states.freeze)
    when :reduce
      production_id = action.fetch(1)
      return nil unless production_id.is_a?(Integer)

      return nil unless apply_reduction(states, production_id)
    when :accept then return RepairAdvance.new(status: :accept, stack: states.freeze)
    else return nil
    end
  end
end

#apply_reduction(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) 


254
255
256
257
258
259
260
261
262
263
264
265
266
267
268
 
# File 'lib/ibex/runtime/repair_search.rb', line 254

def apply_reduction(states, production_id)
  productions = @tables.fetch(:productions) #: Array[Hash[Symbol, Object?]]
  production = productions.fetch(production_id)
  length = production.fetch(:length) #: Integer
  return if length >= states.length

  states.pop(length)
  gotos = @tables.fetch(:gotos) #: Tables::goto_table
  lhs = production.fetch(:lhs) #: Integer
  goto = goto_table_lookup(gotos, states.last, lhs)
  return unless goto.is_a?(Integer)

  states << goto
  states if states.length <= @policy.max_stack
end

#candidate_edits(configuration, kind, token_id, cost) ⇒ Array[RepairEdit]

RBS:

  • (Configuration configuration, Symbol kind, Integer token_id, Integer cost) -> Array[RepairEdit]

Parameters:

  • configuration (Configuration)
  • kind (Symbol)
  • token_id (Integer)
  • cost (Integer)

Returns:



189
190
191
192
193
194
195
196
197
198
 
# File 'lib/ibex/runtime/repair_search.rb', line 189

def candidate_edits(configuration, kind, token_id, cost)
  edit = RepairEdit.new(
    kind: kind,
    position: configuration.input_index,
    token_id: token_id,
    token_name: token_name(token_id),
    cost: cost
  )
  (configuration.edits + [edit]).freeze
end

#configuration_with(source, stack: source.stack, input_index: source.input_index, shifts: source.shifts, cost: source.cost, edits: source.edits, goal: source.goal) ⇒ Configuration

RBS:

  • (Configuration source, ?stack: Array[Integer], ?input_index: Integer, ?shifts: Integer, ?cost: Integer, ?edits: Array[RepairEdit], ?goal: bool) -> Configuration

Parameters:

  • source (Configuration)
  • stack: (Array[Integer]) (defaults to: source.stack)
  • input_index: (Integer) (defaults to: source.input_index)
  • shifts: (Integer) (defaults to: source.shifts)
  • cost: (Integer) (defaults to: source.cost)
  • edits: (Array[RepairEdit]) (defaults to: source.edits)
  • goal: (Boolean) (defaults to: source.goal)

Returns:



306
307
308
309
310
311
 
# File 'lib/ibex/runtime/repair_search.rb', line 306

def configuration_with(source, stack: source.stack, input_index: source.input_index, shifts: source.shifts,
                       cost: source.cost, edits: source.edits, goal: source.goal)
  Configuration.new(
    stack: stack, input_index: input_index, shifts: shifts, cost: cost, edits: edits, goal: goal
  )
end

#expand(configuration) ⇒ RepairPlan, ...

RBS:

  • (Configuration configuration) -> (RepairPlan | Object | nil)

Parameters:

Returns:



107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
 
# File 'lib/ibex/runtime/repair_search.rb', line 107

def expand(configuration)
  current = @tokens.fetch(configuration.input_index)
  unchanged = advance(configuration.stack, current.token_id)
  return LIMIT if unchanged.equal?(LIMIT)

  if unchanged.is_a?(RepairAdvance)
    if unchanged.status == :accept && !configuration.edits.empty?
      push(configuration_with(configuration, stack: unchanged.stack, goal: true))
      return
    end

    if unchanged.status == :shift
      shifts = configuration.shifts + 1
      if shifts >= @policy.success_shifts && !configuration.edits.empty?
        push(configuration_with(configuration, stack: unchanged.stack, shifts: shifts, goal: true))
        return
      end

      push(
        configuration_with(
          configuration, stack: unchanged.stack, input_index: configuration.input_index + 1, shifts: shifts
        )
      )
    end
  end
  return unless configuration.cost < @policy.max_cost

  expand_edits(configuration, current)
end

#expand_candidate(configuration, kind, token_id, cost) ⇒ Object?

RBS:

  • (Configuration configuration, :insert | :replace kind, Integer token_id, Integer cost) -> Object?

Parameters:

  • configuration (Configuration)
  • kind (:insert, :replace)
  • token_id (Integer)
  • cost (Integer)

Returns:

  • (Object, nil) 


164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
 
# File 'lib/ibex/runtime/repair_search.rb', line 164

def expand_candidate(configuration, kind, token_id, cost)
  advanced = advance(configuration.stack, token_id)
  return LIMIT if advanced.equal?(LIMIT)
  return unless advanced

  edits = candidate_edits(configuration, kind, token_id, cost)
  return unless advanced.is_a?(RepairAdvance)

  shifts = kind == :replace ? configuration.shifts + 1 : configuration.shifts
  input_index = kind == :replace ? configuration.input_index + 1 : configuration.input_index
  push(
    configuration_with(
      configuration,
      stack: advanced.stack,
      input_index: input_index,
      shifts: shifts,
      cost: configuration.cost + cost,
      edits: edits,
      goal: advanced.status == :accept || shifts >= @policy.success_shifts
    )
  )
  nil
end

#expand_candidates(configuration, kind) ⇒ RepairPlan, ...

RBS:

  • (Configuration configuration, :insert | :replace kind) -> (RepairPlan | Object | nil)

Parameters:

Returns:



152
153
154
155
156
157
158
159
160
161
 
# File 'lib/ibex/runtime/repair_search.rb', line 152

def expand_candidates(configuration, kind)
  cost = kind == :insert ? @policy.insert_cost : @policy.replace_cost
  return if configuration.cost + cost > @policy.max_cost

  @candidate_ids.each do |token_id|
    result = expand_candidate(configuration, kind, token_id, cost)
    return LIMIT if result.equal?(LIMIT)
  end
  nil
end

#expand_edits(configuration, current) ⇒ RepairPlan, ...

RBS:

  • (Configuration configuration, RepairInput current) -> (RepairPlan | Object | nil)

Parameters:

Returns:



138
139
140
141
142
143
144
145
146
147
148
 
# File 'lib/ibex/runtime/repair_search.rb', line 138

def expand_edits(configuration, current)
  push_delete(configuration, current) unless current.eof?
  inserted = expand_candidates(configuration, :insert)
  return inserted if inserted

  unless current.eof?
    replaced = expand_candidates(configuration, :replace)
    return replaced if replaced
  end
  nil
end

#goto_table_lookup(table, row, column) ⇒ Integer?

RBS:

  • (Tables::goto_table table, Integer row, Integer column) -> Integer?

Parameters:

  • table (Tables::goto_table)
  • row (Integer)
  • column (Integer)

Returns:

  • (Integer, nil) 


293
294
295
296
297
298
299
300
301
302
 
# File 'lib/ibex/runtime/repair_search.rb', line 293

def goto_table_lookup(table, row, column)
  if table.is_a?(Tables::Compact)
    value = table.__send__(:lookup, row, column)
    return value #: Integer?
  end

  rows = table #: Array[Hash[Integer, Integer]]
  empty_row = Parser::EMPTY_ROW #: Hash[Integer, Integer]
  rows.fetch(row, empty_row)[column]
end

#outcome(status, plan: nil) ⇒ RepairSearchResult

RBS:

  • (Symbol status, ?plan: RepairPlan?) -> RepairSearchResult

Parameters:

  • status (Symbol)
  • plan: (RepairPlan, nil) (defaults to: nil)

Returns:



319
320
321
 
# File 'lib/ibex/runtime/repair_search.rb', line 319

def outcome(status, plan: nil)
  RepairSearchResult.new(status: status, plan: plan, configurations: @configurations)
end

#plan(edits) ⇒ RepairPlan

RBS:

  • (Array[RepairEdit] edits) -> RepairPlan

Parameters:

Returns:



314
315
316
 
# File 'lib/ibex/runtime/repair_search.rb', line 314

def plan(edits)
  RepairPlan.new(edits: edits, configurations: @configurations)
end

#pop ⇒ Configuration, Object

RBS:

  • () -> (Configuration | Object)

Returns:



343
344
345
346
347
348
349
350
351
352
353
354
355
 
# File 'lib/ibex/runtime/repair_search.rb', line 343

def pop
  loop do
    entry = @heap.pop
    return LIMIT unless entry

    priority, configuration = entry
    return LIMIT unless configuration.is_a?(Configuration)

    key = [configuration.stack, configuration.input_index, configuration.shifts,
           configuration.goal] #: configuration_key
    return configuration if @best[key] == priority
  end
end

#priority_for(configuration) ⇒ priority

RBS:

  • (Configuration configuration) -> priority

Parameters:

Returns:

  • (priority) 


358
359
360
361
362
363
364
365
366
367
368
369
 
# File 'lib/ibex/runtime/repair_search.rb', line 358

def priority_for(configuration)
  edit_key = configuration.edits.map do |edit|
    rank = { delete: 0, insert: 1, replace: 2 }.fetch(edit.kind)
    [edit.position, rank, edit.token_id] #: [Integer, Integer, Integer]
  end
  goal_rank = configuration.goal ? 0 : 1
  risk = configuration.edits.sum { |edit| semantic_value_risk(edit) }
  [
    configuration.cost, risk, edit_key, goal_rank, -configuration.shifts,
    configuration.input_index, configuration.stack
  ] #: priority
end

#push(configuration) ⇒ void

This method returns an undefined value.

RBS:

  • (Configuration configuration) -> void

Parameters:



330
331
332
333
334
335
336
337
338
339
340
 
# File 'lib/ibex/runtime/repair_search.rb', line 330

def push(configuration)
  priority = priority_for(configuration)
  key = [configuration.stack, configuration.input_index, configuration.shifts,
         configuration.goal] #: configuration_key
  previous = @best[key]
  comparison = previous <=> priority if previous
  return if comparison && comparison <= 0

  @best[key] = priority
  @heap.push(priority, configuration)
end

#push_delete(configuration, current) ⇒ void

This method returns an undefined value.

RBS:

  • (Configuration configuration, RepairInput current) -> void

Parameters:



201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
 
# File 'lib/ibex/runtime/repair_search.rb', line 201

def push_delete(configuration, current)
  cost = configuration.cost + @policy.delete_cost
  return if cost > @policy.max_cost

  edit = RepairEdit.new(
    kind: :delete,
    position: configuration.input_index,
    token_id: current.token_id,
    token_name: current.token_name,
    cost: @policy.delete_cost
  )
  push(
    configuration_with(
      configuration, input_index: configuration.input_index + 1,
                     cost: cost,
                     edits: (configuration.edits + [edit]).freeze
    )
  )
end

#search(state_stack) ⇒ RepairPlan, ...

Compatibility projection used by the semantic runtime path.

RBS:

  • (Array[Integer] state_stack) -> (RepairPlan | Object | nil)

Parameters:

  • state_stack (Array[Integer])

Returns:



55
56
57
58
59
60
61
 
# File 'lib/ibex/runtime/repair_search.rb', line 55

def search(state_stack)
  result = search_result(state_stack)
  return result.plan if result.selected?
  return NEED_INPUT if result.status == :need_input

  nil
end

#search_result(state_stack) ⇒ RepairSearchResult

Preserve the bounded outcome for syntax tooling and diagnostics.

RBS:

  • (Array[Integer] state_stack) -> RepairSearchResult

Parameters:

  • state_stack (Array[Integer])

Returns:



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

def search_result(state_stack)
  empty_edits = [] #: Array[RepairEdit]
  push(
    Configuration.new(
      stack: state_stack.dup.freeze,
      input_index: 0,
      shifts: 0,
      cost: 0,
      edits: empty_edits.freeze,
      goal: false
    )
  )
  needs_input = false
  until @heap.empty?
    configuration = pop
    return outcome(:exhausted) if configuration.equal?(LIMIT)
    next unless configuration.is_a?(Configuration)

    result = visit(configuration)
    return outcome(:exhausted) if result.equal?(LIMIT)
    return outcome(:selected, plan: result) if result.is_a?(RepairPlan)

    needs_input = true if result.equal?(NEED_INPUT)
  end
  outcome(needs_input ? :need_input : :not_found)
end

#semantic_value_risk(edit) ⇒ Integer

Prefer punctuation edits when equal-cost repairs are otherwise ambiguous; inventing or discarding a word-like token is more likely to fabricate or lose an application semantic value.

RBS:

  • (RepairEdit edit) -> Integer

Parameters:

Returns:

  • (Integer) 


375
376
377
 
# File 'lib/ibex/runtime/repair_search.rb', line 375

def semantic_value_risk(edit)
  edit.token_name.delete_prefix(":").match?(/\A[A-Za-z_][A-Za-z0-9_]*\z/) ? 1 : 0
end

#token_name(token_id) ⇒ String

RBS:

  • (Integer token_id) -> String

Parameters:

  • token_id (Integer)

Returns:

  • (String) 


324
325
326
327
 
# File 'lib/ibex/runtime/repair_search.rb', line 324

def token_name(token_id)
  token_names = @tables.fetch(:token_names) #: Hash[Integer, String]
  token_names.fetch(token_id, token_id.to_s)
end

#visit(configuration) ⇒ RepairPlan, ...

RBS:

  • (Configuration configuration) -> (RepairPlan | Object | nil)

Parameters:

Returns:



95
96
97
98
99
100
101
102
103
104
 
# File 'lib/ibex/runtime/repair_search.rb', line 95

def visit(configuration)
  @configurations += 1
  return LIMIT if @configurations > @policy.max_configurations
  return plan(configuration.edits) if configuration.goal
  if configuration.input_index >= @tokens.length
    return @complete ? nil : NEED_INPUT
  end

  expand(configuration)
end