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 =

Signature:

  • Object

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, untyped] tables, RepairPolicy policy, Array[RepairInput] tokens, complete: bool) -> void

Parameters:



26
27
28
29
30
31
32
33
34
35
36
 
# File 'lib/ibex/runtime/repair_search.rb', line 26

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]
  @candidate_ids = tables.fetch(:token_names).keys.reject { |id| reserved.include?(id) }.sort.freeze
end

Instance Method Details

#action_for(state, token_id) ⇒ Object

RBS:

  • (Integer state, Integer token_id) -> untyped

Parameters:

  • state (Integer)
  • token_id (Integer)

Returns:

  • (Object) 


235
236
237
238
239
240
 
# File 'lib/ibex/runtime/repair_search.rb', line 235

def action_for(state, token_id)
  explicit = table_lookup(@tables.fetch(:actions), state, token_id)
  return explicit if explicit

  @tables.fetch(:default_actions, Parser::EMPTY_ROW)[state] || [:error]
end

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

RBS:

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

Parameters:

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

Returns:



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

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
      states << action.fetch(1)
      return nil if states.length > @policy.max_stack

      return RepairAdvance.new(status: :shift, stack: states.freeze)
    when :reduce then return nil unless apply_reduction(states, action.fetch(1))
    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) 


221
222
223
224
225
226
227
228
229
230
231
232
 
# File 'lib/ibex/runtime/repair_search.rb', line 221

def apply_reduction(states, production_id)
  production = @tables.fetch(:productions).fetch(production_id)
  length = production.fetch(:length)
  return if length >= states.length

  states.pop(length)
  goto = table_lookup(@tables.fetch(:gotos), states.last, production.fetch(:lhs))
  return unless goto

  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:



163
164
165
166
167
168
169
170
171
172
 
# File 'lib/ibex/runtime/repair_search.rb', line 163

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:



251
252
253
254
255
256
 
# File 'lib/ibex/runtime/repair_search.rb', line 251

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:



81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
 
# File 'lib/ibex/runtime/repair_search.rb', line 81

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) 


138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
 
# File 'lib/ibex/runtime/repair_search.rb', line 138

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:



126
127
128
129
130
131
132
133
134
135
 
# File 'lib/ibex/runtime/repair_search.rb', line 126

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:



112
113
114
115
116
117
118
119
120
121
122
 
# File 'lib/ibex/runtime/repair_search.rb', line 112

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

#plan(edits) ⇒ RepairPlan

RBS:

  • (Array[RepairEdit] edits) -> RepairPlan

Parameters:

Returns:



259
260
261
 
# File 'lib/ibex/runtime/repair_search.rb', line 259

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

#pop ⇒ Configuration, Object

RBS:

  • () -> (Configuration | Object)

Returns:



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

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]
    return configuration if @best[key] == priority
  end
end

#priority_for(configuration) ⇒ Array[untyped]

RBS:

  • (Configuration configuration) -> Array[untyped]

Parameters:

Returns:

  • (Array[untyped]) 


295
296
297
298
299
300
301
302
303
304
305
306
 
# File 'lib/ibex/runtime/repair_search.rb', line 295

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]
  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
  ]
end

#push(configuration) ⇒ void

This method returns an undefined value.

RBS:

  • (Configuration configuration) -> void

Parameters:



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

def push(configuration)
  priority = priority_for(configuration)
  key = [configuration.stack, configuration.input_index, configuration.shifts, configuration.goal]
  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:



175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
 
# File 'lib/ibex/runtime/repair_search.rb', line 175

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, ...

RBS:

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

Parameters:

  • state_stack (Array[Integer])

Returns:



39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
 
# File 'lib/ibex/runtime/repair_search.rb', line 39

def search(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 nil if configuration.equal?(LIMIT)
    next unless configuration.is_a?(Configuration)

    result = visit(configuration)
    return nil if result.equal?(LIMIT)
    return result if result.is_a?(RepairPlan)

    needs_input = true if result.equal?(NEED_INPUT)
  end
  needs_input ? NEED_INPUT : nil
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) 


312
313
314
 
# File 'lib/ibex/runtime/repair_search.rb', line 312

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

#table_lookup(table, row, column) ⇒ Object

RBS:

  • (untyped table, Integer row, Integer column) -> untyped

Parameters:

  • table (Object)
  • row (Integer)
  • column (Integer)

Returns:

  • (Object) 


243
244
245
246
247
 
# File 'lib/ibex/runtime/repair_search.rb', line 243

def table_lookup(table, row, column)
  return table.lookup(row, column) if table.respond_to?(:lookup)

  table.fetch(row, Parser::EMPTY_ROW)[column]
end

#token_name(token_id) ⇒ String

RBS:

  • (Integer token_id) -> String

Parameters:

  • token_id (Integer)

Returns:

  • (String) 


264
265
266
 
# File 'lib/ibex/runtime/repair_search.rb', line 264

def token_name(token_id)
  @tables.fetch(:token_names).fetch(token_id, token_id.to_s)
end

#visit(configuration) ⇒ RepairPlan, ...

RBS:

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

Parameters:

Returns:



69
70
71
72
73
74
75
76
77
78
 
# File 'lib/ibex/runtime/repair_search.rb', line 69

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