Class: Dendroid::Parsing::ChartWalker

Inherits:
Object
  • Object
show all
Defined in:
lib/dendroid/parsing/chart_walker.rb

Instance Attribute Summary collapse

Instance Method Summary collapse

Constructor Details

#initialize(theChart) ⇒ ChartWalker

rubocop: disable Metrics/AbcSize rubocop: disable Metrics/CyclomaticComplexity rubocop: disable Metrics/PerceivedComplexity



15
16
17
 
# File 'lib/dendroid/parsing/chart_walker.rb', line 15

def initialize(theChart)
  @chart = theChart
end

Instance Attribute Details

#chart ⇒ Object (readonly)

Returns the value of attribute chart.



8
9
10
 
# File 'lib/dendroid/parsing/chart_walker.rb', line 8

def chart
  @chart
end

#last_item ⇒ Object (readonly)

Returns the value of attribute last_item.



9
10
11
 
# File 'lib/dendroid/parsing/chart_walker.rb', line 9

def last_item
  @last_item
end

Instance Method Details

#completer_backwards(walk_progress, paths, entry2node, sharing, predecessors) ⇒ Object 



233
234
235
236
237
238
239
240
241
242
243
244
245
246
247
248
249
250
251
252
253
254
255
256
257
258
259
260
261
262
263
264
265
266
267
268
269
270
271
272
273
274
275
276
277
278
279
280
281
 
# File 'lib/dendroid/parsing/chart_walker.rb', line 233

def completer_backwards(walk_progress, paths, entry2node, sharing, predecessors)
  # Trying to remove some predecessors with some disambiguation technique
  forerunners = disambiguate(walk_progress, predecessors)

  if forerunners.size == 1
    pred = forerunners[0]
    if entry2node.include? pred
      shared_node = entry2node[pred]
      if sharing.include? shared_node
        sharing[shared_node] << walk_progress
      else
        sharing[shared_node] = [walk_progress]
      end
      walk_progress.add_child_node(shared_node)
      walk_progress.parents.push(shared_node)
      walk_progress.state = :Delegating

    elsif pred.predecessors.size == 1
      new_node = walk_progress.push_and_node(pred)
      walk_progress.curr_item = pred
      entry2node[pred] = new_node
    else
      pre_forerunners = disambiguate(walk_progress, pred.predecessors)
      index_empty = pre_forerunners.find_index { |entry| entry.dotted_item.empty? }
      if index_empty
        entry_empty = pre_forerunners.delete_at(index_empty)
        walk_progress.add_node_empty(entry_empty)
        walk_progress.curr_item = entry_empty.predecessors[0] # Assuming only one predecessor
      end
      if pre_forerunners.size == 1
        pred = forerunners[0]
        new_node = walk_progress.push_and_node(pre_forerunners[0])
        walk_progress.curr_item = pred
        entry2node[pred] = new_node
      else
        prepreds = sort_predecessors(pre_forerunners)
        new_node = walk_progress.push_or_node(pred.origin, prepreds.size)
        walk_progress.curr_item = pred
        entry2node[pred] = new_node
        fork(walk_progress, paths, prepreds)
      end
    end
  else
    # AMBIGUITY: multiple valid predecessors
    preds = sort_predecessors(forerunners)
    walk_progress.push_or_node(preds)
    fork(walk_progress, paths, preds)
  end
end

#disambiguate(_progress, predecessors) ⇒ Object 



208
209
210
 
# File 'lib/dendroid/parsing/chart_walker.rb', line 208

def disambiguate(_progress, predecessors)
  predecessors
end

#fork(walk_progress, paths, sorted_predecessors) ⇒ Object 



283
284
285
286
287
288
289
290
291
292
293
294
 
# File 'lib/dendroid/parsing/chart_walker.rb', line 283

def fork(walk_progress, paths, sorted_predecessors)
  progs = [walk_progress]
  walk_progress.fork(sorted_predecessors[0])
  sorted_predecessors[1..].each do |prd|
    alternate = walk_progress.dup
    alternate.fork(prd)
    paths << alternate
    progs << alternate
  end

  progs.each { |pg| pg.push_and_node(pg.curr_item) }
end

#predecessors_of(anEItem, parents) ⇒ Object 



216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
 
# File 'lib/dendroid/parsing/chart_walker.rb', line 216

def predecessors_of(anEItem, parents)
  # Rule: if anEItem has itself as predecessor AND parents contains
  # only a start item, then remove anEItem from its own predecessor(s).
  if (parents.size == 1) && anEItem.predecessors.include?(anEItem)
    # raise StandardError unless parents[0].match(anEItem)
    unless parents[0].match(anEItem)
      raise StandardError

    end
    preds = anEItem.predecessors.dup
    preds.delete(anEItem)
    preds
  else
    anEItem.predecessors
  end
end

#sort_predecessors(predecessors) ⇒ Object 



212
213
214
 
# File 'lib/dendroid/parsing/chart_walker.rb', line 212

def sort_predecessors(predecessors)
  predecessors
end

#step_back(walk_progress, paths, token2node, entry2node, sharing, or_nodes_crossed) ⇒ Object 



72
73
74
75
76
77
78
79
80
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
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
136
137
138
139
140
141
142
143
144
145
146
147
148
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
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
 
# File 'lib/dendroid/parsing/chart_walker.rb', line 72

def step_back(walk_progress, paths, token2node, entry2node, sharing, or_nodes_crossed)
  loop do
    case walk_progress.state
    when :Waiting, :New
      predecessors = predecessors_of(walk_progress.curr_item, walk_progress.parents)
      last_parent = walk_progress.parents.last
      if sharing.include? last_parent
        delegating = sharing[last_parent]
        unless delegating.include? walk_progress
          delegating.each do |dlg|
            dlg.curr_rank = walk_progress.curr_rank
            dlg.curr_item = walk_progress.curr_item
            dlg.state = :Waiting
          end
          sharing.delete(last_parent)
        end
      end
      walk_progress.state = :Running

    when :Running
      predecessors = predecessors_of(walk_progress.curr_item, walk_progress.parents)

    when :Forking
      # predecessors = [walk_progress.curr_item]
      predecessors = [walk_progress.predecessor]
      walk_progress.predecessor = nil
      walk_progress.state = :Running
    end

    if predecessors.empty?
      walk_progress.state = :Complete
      break
    end

    case walk_progress.curr_item.algo
    when :completer
      completer_backwards(walk_progress, paths, entry2node, sharing, predecessors)
      break if walk_progress.state == :Delegating

    when :scanner
      curr_token = chart.tokens[walk_progress.curr_rank - 1]
      if token2node.include? curr_token
        walk_progress.add_child_node(token2node[curr_token])
        walk_progress.curr_rank -= 1
      else
        new_node = walk_progress.add_terminal_node(chart.tokens[walk_progress.curr_rank - 1])
        token2node[curr_token] = new_node
      end
      if predecessors.size == 1
        walk_progress.curr_item = predecessors[0]
        walk_progress.state = :Waiting
        break
      else
        # TODO: challenge assumption single predecessor
        raise StandardError
      end

    when :predictor
      unless walk_progress.parents.last.partial?
        last_parent = walk_progress.parents.pop
        if sharing.include? last_parent
          delegating = sharing[last_parent]
          unless delegating.include? walk_progress
            delegating.each do |dlg|
              dlg.curr_rank = walk_progress.curr_rank
              dlg.curr_item = walk_progress.curr_item
              dlg.state = :Running
            end
            sharing.delete(last_parent)
          end
        end
        if last_parent.is_a?(OrNode)
          if or_nodes_crossed.include?(last_parent)
            walk_progress.state = :Complete
            break
          else
            or_nodes_crossed[last_parent] = true
          end
        end
      end
      index_empty = predecessors.find_index { |entry| entry.dotted_item.empty? }
      if index_empty
        entry_empty = predecessors.delete_at(index_empty)
        walk_progress.add_node_empty(entry_empty)
        raise StandardError unless predecessors.empty? # Uncovered case

        walk_progress.curr_item = entry_empty
        next
      end
      if predecessors.size == 1
        walk_progress.curr_item = predecessors[0]
      else
        # curr_item has multiple predecessors from distinct rules
        # look in lineage the latest entry that matches one of the ancestors AND
        # has a free slot for the current symbol
        matches = walk_progress.match_parent?(predecessors, true)
        if matches.empty?
          walk_progress.state = :Complete
          break
        end
        (matching_pred, stack_offset) = matches.first
        walk_progress.curr_item = matching_pred
        unless stack_offset.zero?
          removed = walk_progress.parents.pop(stack_offset)
          if removed.is_a?(Array)
            or_nodes = removed.select { |entry| entry.is_a?(OrNode) }
            unless or_nodes.empty?
              or_nodes.reverse_each do |or_nd|
                if or_nodes_crossed.include?(or_nd)
                  walk_progress.state = :Complete
                  break
                else
                  or_nodes_crossed[or_nd] = true
                end
              end
              break if walk_progress.state == :Complete

            end
          elsif removed.is_a?(OrNode)
            if or_nodes_crossed.include?(removed)
              walk_progress.state = :Complete
              break
            else
              or_nodes_crossed[removed] = true
            end
          end
        end
      end
    else
      raise StandardError
    end
  end

  walk_progress
end

#walk(start_item) ⇒ Object 



19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
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
65
66
67
68
69
70
 
# File 'lib/dendroid/parsing/chart_walker.rb', line 19

def walk(start_item)
  curr_rank = chart.size - 1

  parents = []
  progress = WalkProgress.new(curr_rank, start_item, parents)
  paths = [progress]

  if start_item.predecessors.size > 1
    # Create n times start_item as predecessors, then for each path initialize to its unique own predecessor
    forerunners = disambiguate(progress, start_item.predecessors)
    if forerunners.size == 1
      parents << AndNode.new(start_item, curr_rank)
    else
      preds = sort_predecessors(forerunners)
      if start_item.rule.rhs.size == 1
        parents << AndNode.new(start_item, curr_rank)
        progress.push_or_node(start_item.origin, preds.size)
      else
        parents << OrNode.new(start_item.lhs, start_item.origin, curr_rank, preds.size)
      end
      progress.curr_item = start_item
      fork(progress, paths, preds)
    end
  else
    parents << AndNode.new(start_item, curr_rank)
  end
  token2node = {}
  entry2node = {}
  sharing = {}
  or_nodes_crossed = {}

  loop do # Iterate over rank values
    pass = :primary
    loop do # Iterate over paths until all are ready for previous rank
      paths.each do |prg|
        next if prg.state == :Complete || prg.state == :Delegating
        next if pass == :secondary && prg.state == :Waiting

        step_back(prg, paths, token2node, entry2node, sharing, or_nodes_crossed)
      end
      # TODO: handle path removal
      break if paths.none? { |pg| pg.state == :Running || pg.state == :Forking }

      pass = :secondary
    end
    break if paths.all? { |prg| prg.state == :Complete }

    entry2node.clear
  end

  parents[0]
end