Class: Stupidedi::Parser::ConstraintTable::ValueBased

Inherits:
ConstraintTable
  • Object
show all
Defined in:
lib/stupidedi/parser/constraint_table.rb

Overview

Chooses the subset of Instruction values based on the distinguishing values allowed by each Schema::SegmentUse. For instance, there are often several loops that begin with NM1, which are distinguished by the qualifier in element NM101.

Instance Method Summary collapse

Constructor Details

#initialize(instructions) ⇒ ValueBased

Returns a new instance of ValueBased.



116
117
118
119
 
# File 'lib/stupidedi/parser/constraint_table.rb', line 116

def initialize(instructions)
  @instructions = instructions
  @__basis      = {}
end

Instance Method Details

#basis(instructions, mode) ⇒ Array(Array<(Integer, Integer, Map)>, Array<(Integer, Integer, Map)>)

Returns:

  • (Array(Array<(Integer, Integer, Map)>, Array<(Integer, Integer, Map)>)) 


306
307
308
309
310
311
312
313
314
315
316
317
318
319
320
321
322
323
324
325
326
327
328
329
330
331
332
333
334
335
336
337
338
339
340
341
342
343
344
345
346
347
348
349
350
351
352
353
354
355
356
357
358
359
360
361
362
363
364
365
366
367
368
369
370
371
372
373
374
375
376
377
378
379
380
381
382
383
384
385
386
387
388
389
390
391
392
393
394
395
396
397
398
399
400
401
402
403
404
 
# File 'lib/stupidedi/parser/constraint_table.rb', line 306

def basis(instructions, mode)
  @__basis[mode] ||= begin
    # When inserting segments, given a choice between two otherwise
    # equivalent instructions, prefer the one with smallest `pop_count`.
    # For example, when inserting an HL*20 in X221 835, the new 2000A
    # loop could potentially go in the current "Table 2 - Billing
    # Provider Detail" (smaller pop_count), or the parser could create
    # a whole new table (larger pop_count).
    #
    # When searching for segments in a parse tree (mode == :read), we
    # need to try both choices. That's because this "Table 2 - Billing
    # Provider Detail" could be followed by a different "Table 2 -
    # Subscriber Detail", which is then followed by another "Table 2 -
    # Billing Provider Detail". Then the next HL*20 would belong to the
    # uncle table, not the current table.
    if mode == :insert
      instructions = shallowest(instructions)
    end

    disjoint_elements = []
    distinct_elements = []

    # The first SegmentUse is used to represent the structure that must
    # be shared by the others: number of elements and type of elements
    element_uses = instructions.head.segment_use.definition.element_uses

    # Iterate over each element across all SegmentUses (think columns)
    #   NM1*[IL]*[  ]*..*..*..*..*..*[  ]*..*..*{..}*..
    #   NM1*[40]*[  ]*..*..*..*..*..*[  ]*..*..*{..}*..
    element_uses.length.times do |n|
      if element_uses.at(n).composite?
        ms = 0 .. element_uses.at(n).definition.component_uses.length - 1
      else
        ms = [nil]
      end

      # If this is a composite element, we iterate over each component.
      # Otherwise this loop iterates once with the index {m} set to nil.
      ms.each do |m|
        last  = nil        # the last subset we examined
        total = Sets.empty # the union of all examined subsets

        distinct = false
        disjoint = true

        instructions.each do |i|
          element_use = i.segment_use.definition.element_uses.at(n)

          unless m.nil?
            element_use = element_use.definition.component_uses.at(m)
          end

          allowed_vals = element_use.allowed_values

          # We want to know if every instruction's set of allowed values
          # is disjoint (with one another). Instead of comparing each set
          # with every other set, which takes (N-1)! comparisons, we can
          # do it in N steps.
          disjoint &&= allowed_vals.disjoint?(total)

          # We also want to know if one instruction's set of allowed vals
          # contains elements that aren't present in at least one other
          # set. The opposite condition is easy to test: all sets contain
          # the same elements (are equal). So we can similarly, check this
          # condition in N steps rather than (N-1)!
          distinct ||= allowed_vals != last unless last.nil?

          total = allowed_vals.union(total)
          last  = allowed_vals
        end

      # puts "#{n}.#{m}: disjoint(#{disjoint}) distinct(#{distinct})"

        if disjoint
          # Since each instruction's set of allowed values is disjoint, we
          # can build a function/hash that returns the single instruction,
          # given one of the values. When given a value outside the set of
          # all (combined) values, it returns nil.
          disjoint_elements << [[n, m], build_disjoint(total, n, m, instructions)]
        elsif distinct
          # Not all instructions have the same set of allowed values. So
          # we can build a function/hash that accepts one of the values
          # and returns the subset of the instructions where that value
          # can occur. This might be some, none, or all of the original
          # instructions, so clearly this provides less information than
          # if each allowed value set was disjoint.

          # Currently disabled (and untested) because it doesn't look like
          # any of the HIPAA schemas would use this -- so testing it would
          # be a pain.
          #
          distinct_elements << [[n, m], build_distinct(total, n, m, instructions)]
        end
      end
    end

    [disjoint_elements, distinct_elements]
  end
end

#build_disjoint(total, n, m, instructions) ⇒ Hash<String, Array<Instruction>>

Returns:



407
408
409
410
411
412
413
414
415
416
417
418
419
420
421
422
423
424
425
426
427
428
429
430
431
432
433
434
435
436
437
438
439
440
441
442
443
444
445
446
447
448
 
# File 'lib/stupidedi/parser/constraint_table.rb', line 407

def build_disjoint(total, n, m, instructions)
  if total.finite?
    # The sum of all allowed value sets is finite, so we know that each
    # individual allowed value set is finite (we can iterate over it).
    map = Hash.new

    instructions.each do |i|
      element_use = i.segment_use.definition.element_uses.at(n)

      unless m.nil?
        element_use = element_use.definition.component_uses.at(m)
      end

      allowed_vals = element_use.allowed_values
      allowed_vals.each{|v| map[v] = i.cons }
    end

    map
  else
    # At least one of allowed value sets is infinite. This happens when
    # it is RelativeComplement, which declares the values that are *not*
    # allowed in the set.
    map = Hash.new{|h,k| h[k] = instructions }

    instructions.each do |i|
      element_use = i.segment_use.definition.element_uses.at(n)
      unless m.nil?
        element_use = element_use.definition.component_uses.at(m)
      end

      allowed_vals = element_use.allowed_values

      unless allowed_vals.finite?
        allowed_vals.complement.each{|v| map[v] -= i }
      end
    end

    # Clear the default_proc so accesses don't change the Hash
    map.default = instructions
    map
  end
end

#build_distinct(total, n, m, instructions) ⇒ Hash<String, Array<Instruction>>

Returns:



451
452
453
454
455
456
457
458
459
460
461
462
463
464
465
466
467
468
469
470
471
472
473
474
475
476
477
478
479
480
481
482
483
484
485
486
487
488
489
490
491
492
493
494
495
 
# File 'lib/stupidedi/parser/constraint_table.rb', line 451

def build_distinct(total, n, m, instructions)
  if total.finite?
    # The sum of all allowed value sets is finite, so we know that each
    # individual allowed value set is finite (we can iterate over it).
    map = Hash.new{|h,k| h[k] = [] }

    instructions.each do |i|
      element_use  = i.segment_use.definition.element_uses.at(n)

      unless m.nil?
        element_use = element_use.definition.component_uses.at(m)
      end

      allowed_vals = element_use.allowed_values
      allowed_vals.each{|v| map[v] << i }
    end

    # Clear the default_proc so accesses don't change the Hash
    map.default = []
    map
  else
    # At least one of allowed value sets is infinite. This happens when
    # it is RelativeComplement, which declares the values that are *not*
    # allowed in the set.
    map = Hash.new{|h,k| h[k] = instructions }

    instructions.each do |i|
      element_use  = i.segment_use.definition.element_uses.at(n)

      unless m.nil?
        element_use = element_use.definition.component_uses.at(m)
      end

      allowed_vals = element_use.allowed_values

      unless allowed_vals.finite?
        allowed_vals.complement.each{|v| map[v] -= i }
      end
    end

    # Clear the default_proc so accesses don't change the Hash
    map.default = instructions
    map
  end
end

#deconstruct(element_toks, m, n) ⇒ String?

Return the value of the m-th elemnt, or if n is not nil, return the value of the n-th component from the n-th element. When the value is blank, the function returns nil.

Parameters:

Returns:

  • (String, nil) 


506
507
508
509
510
511
512
513
514
515
516
517
518
519
520
521
522
523
 
# File 'lib/stupidedi/parser/constraint_table.rb', line 506

def deconstruct(element_toks, m, n)
  element_tok = element_toks.at(m)
  element_tok = element_tok.element_toks.at(0) if element_tok.try(:repeated?)

  if element_tok.blank?
    nil
  elsif n.nil?
    element_tok.value
  else
    element_tok = element_tok.component_toks.at(n)

    if element_tok.blank?
      nil
    else
      element_tok.value
    end
  end
end

#disambiguate_sibling_slots(instructions, state = nil) ⇒ Array<Instruction>

When ValueBased filtering leaves multiple Instructions whose SegmentUses are sibling slots in the same parent loop sharing a segment id, pick the slot whose ancestor structure has actually been entered in the current parse tree. Concretely: among the candidate sibling positions, keep only those greater than the highest-position segment already consumed in the parent loop; then pick the earliest among those. If state (and thus the parse tree) is not available, fall back to picking the earliest position outright (Variant B). Falls back to the input unchanged when the precondition fails, preserving the existing non- determinism error for genuinely ambiguous cases (e.g. survivors in different parent loops).

All survivors share a segment id by construction (instructions are grouped by segment_id in InstructionTable#constraints before ConstraintTable.build is called).

Returns:



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
 
# File 'lib/stupidedi/parser/constraint_table.rb', line 253

def disambiguate_sibling_slots(instructions, state = nil)
  return instructions if instructions.length <= 1

  collapsed = shallowest(instructions)
  return collapsed if collapsed.length <= 1

  uses = collapsed.map(&:segment_use)
  parent = uses.first.parent
  return instructions if parent.nil?
  return instructions unless uses.all?{|u| u.parent.equal?(parent) }

  reachable = collapsed
  highest   = highest_consumed_position(state, parent) if state
  if highest
    # Strict `>` assumes non-repeating sibling slots: a candidate
    # whose position equals `highest` is excluded because that
    # slot has already been consumed. If a partner grammar exposes
    # repeating sibling slots, this may need to relax to `>=`.
    ahead = collapsed.select{|i| i.segment_use.position > highest }
    reachable = ahead unless ahead.empty?
  end

  min_pos = reachable.map{|i| i.segment_use.position }.min
  reachable.select{|i| i.segment_use.position == min_pos }
end

#highest_consumed_position(state, parent) ⇒ Integer?

Walks up from the state's value-tree zipper to find the LoopVal/ TableVal whose definition matches parent (object identity), then returns the highest usage.position among its already-consumed segment children. Returns nil when the matching container can't be found (e.g. the loop hasn't been opened yet) or has no consumed segments — both of which mean we have no structural signal to use.

Returns:

  • (Integer, nil) 


287
288
289
290
291
292
293
294
295
296
297
298
299
300
301
302
303
 
# File 'lib/stupidedi/parser/constraint_table.rb', line 287

def highest_consumed_position(state, parent)
  return nil if state.nil?
  z = state.zipper
  while z
    node = z.node
    if (node.loop? or node.table?) and node.definition.equal?(parent)
      positions = node.children
        .select{|c| c.segment? and c.usage }
        .map{|c| c.usage.position }
      return positions.max if positions.any?
      return nil
    end
    break if z.root?
    z = z.up
  end
  nil
end

#matches(segment_tok, strict, mode, state = nil) ⇒ Array<Instruction>

Returns:



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
207
208
209
210
211
212
213
214
215
216
217
218
219
220
 
# File 'lib/stupidedi/parser/constraint_table.rb', line 122

def matches(segment_tok, strict, mode, state = nil)
  invalid = true  # Were all present possibly distinguishing elements invalid?
  present = false # Were any possibly distinguishing elements present?

  disjoint, distinct = basis(@instructions, mode)

  # First check single elements that can narrow the search space to
  # a single matching Instruction.
  disjoint.each do |(n, m), map|
    value = deconstruct(segment_tok.element_toks, n, m)

    case value
    when nil, :not_used, :default
      # value wasn't present in segment_tok, can't use it to decide
    else
      singleton = map.at(value)
      present   = true

      unless singleton.nil?
        # Success, search is terminated
        return singleton
      else
        if strict
          designator = "#{segment_tok.id}#{"%02d" % (n + 1)}"
          designator = designator + "-%02d" % (m + 1) unless m.nil?

          raise ArgumentError,
            "value #{value.to_s} is not allowed in element #{designator}"
        end
      end
    end
  end

  # If we reach this line, none of the present elements could, on its
  # own, narrow the search space to a single Instruction. We now test
  # the combination of elements to iteratively narrow the search space
  space = @instructions

  # @todo: These filters could be ordered by probable effectiveness,
  # so we narrow the search space by the largest amount in the fewest
  # number of steps.
  distinct.each do |(n, m), map|
    value = deconstruct(segment_tok.element_toks, n, m)

    unless value.nil?
      # Lookup which instructions are compatible with this input
      subset  = map.at(value)
      present = true

      unless subset.blank?
        invalid = false
        space  &= subset

        if space.length <= 1
          # Success, search is terminated
          return space
        end
      else
        # This value isn't compatible with any instruction
        if strict
          designator = "#{segment_tok.id}#{"%02d" % (n + 1)}"
          designator = designator + "-%02d" % (m + 1) unless m.nil?

          raise ArgumentError,
            "value #{value.to_s} is not allowed in element #{designator}"
        end
      end
    end
  end

  if invalid and present
    # Some elements were present, but all contained invalid values, and
    # even ignoring those we could not narrow the matches to a single
    # instruction.
    #
    # We could return the remaining search space, but it is safest to
    # mark this as an invalid segment and avoid the non-determinism
    []
  else
    # Some elements were present and none were invalid, but it was not
    # possible to narrow the set of matches to a single instruction.
    #
    # When the survivors are sibling slots in the same loop sharing a
    # segment id (e.g. two N3 slots in a partner-customised 4010 PO850
    # N1 loop), use the parser's current parse tree to pick the slot
    # whose preceding-sibling structure has actually been entered
    # (Variant A — structural reachability). The :insert gate skips
    # disambiguation during :find navigation, where the caller wants
    # the full set of candidates a segment could be bound to. For
    # genuinely ambiguous cases (different parent loops, or different
    # segment ids) the helper bails out to the full search space,
    # which will cause non-determinism in the parser.
    if mode == :insert
      disambiguate_sibling_slots(space, state)
    else
      space
    end
  end
end

#shallowest(instructions) ⇒ Array<Instruction>

Resolve conflicts between instructions that have identical SegmentUse values. For each SegmentUse, this chooses the Instruction that pops the fewest number of states.

Returns:



227
228
229
230
231
232
233
 
# File 'lib/stupidedi/parser/constraint_table.rb', line 227

def shallowest(instructions)
  grouped = instructions.group_by{|i| i.segment_use.object_id }
  grouped.flat_map do |k, is|
    shallowest = is.map(&:pop_count).min
    is.select{|i| i.pop_count == shallowest }
  end
end