Module: Ast::Merge::TrailingGroups::Core

Included in:
DestIterate
Defined in:
lib/ast/merge/trailing_groups/core.rb

Overview

Core primitives for position-aware template-only node interleaving.

This module provides three stateless methods that form the backbone of the trailing-groups algorithm. They operate on plain data structures (hashes, sets, arrays) and yield to caller-supplied blocks for format-specific emission — no emitter API coupling.

Algorithm overview

  1. Build — Walk template nodes in template order. Each node is classified as matched (present in destination) or template-only via a caller-supplied predicate. Consecutive template-only nodes are grouped under the index of the preceding matched node (:prefix for nodes before the first match).

  2. Flush — After each destination node is consumed during the dest iteration loop, check whether any interior trailing groups are now ready. A group anchored at template index K is ready when all matched template indices ≤ K have been consumed. This deferred-flush approach handles destination reordering correctly.

  3. Emit remaining — After the dest loop, emit any trailing groups that were never flushed (tail groups, safety net for edge cases).

Examples:

Direct usage (rare — prefer DestIterate wrapper)

include Ast::Merge::TrailingGroups::Core

groups, matched = build_trailing_groups(
  template_nodes: nodes,
  matched_predicate: ->(node, idx) { dest_sigs.include?(sig(node)) },
)

See Also:

Instance Method Summary collapse

Instance Method Details

#build_trailing_groups(template_nodes:, matched_predicate:, entry_builder: nil) ⇒ Array(Hash{Symbol,Integer => Array<Hash>}, Set<Integer>)

Build a map of trailing groups for position-aware insertion.

Walks template_nodes in order. For each node the matched_predicate is called with (node, index). Matched nodes become group anchors; consecutive unmatched nodes accumulate in the current group.

Each group entry is a Hash with at least :node and :index keys. Callers may supply entry_builder to add extra keys (e.g. :item for sequence items in psych-merge).

Parameters:

  • template_nodes (Array) —

    Ordered template nodes

  • matched_predicate (#call) —

    Lambda receiving (node, index), returns truthy when the node is matched in the destination

  • entry_builder (#call, nil) (defaults to: nil) —

    Optional lambda receiving (node, index) that returns the Hash to store in the buffer. Defaults to { node: node, index: index }.

Returns:

  • (Array(Hash{Symbol,Integer => Array<Hash>}, Set<Integer>)) —

    Tuple of [trailing_groups, matched_indices]. trailing_groups is keyed by :prefix or the Integer index of the preceding matched template node.



61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
 
# File 'lib/ast/merge/trailing_groups/core.rb', line 61

def build_trailing_groups(template_nodes:, matched_predicate:, entry_builder: nil)
  groups = {}
  matched_indices = ::Set.new
  current_anchor = :prefix
  current_buffer = []

  template_nodes.each_with_index do |node, idx|
    if matched_predicate.call(node, idx)
      matched_indices << idx
      groups[current_anchor] = current_buffer unless current_buffer.empty?
      current_anchor = idx
      current_buffer = []
    else
      entry = entry_builder ? entry_builder.call(node, idx) : { node: node, index: idx }
      current_buffer << entry
    end
  end

  groups[current_anchor] = current_buffer unless current_buffer.empty?
  [groups, matched_indices]
end

#emit_remaining_trailing_groups(trailing_groups:, consumed_indices:) {|info| ... } ⇒ void

This method returns an undefined value.

Emit any trailing groups not yet flushed (tail + safety net).

This is called after the destination iteration loop completes. Groups are emitted in ascending anchor order, skipping :prefix (which is always handled before the loop).

Parameters:

  • trailing_groups (Hash{Symbol,Integer => Array<Hash>})
  • consumed_indices (Set<Integer>) —

    Template indices consumed so far

Yields:

  • (info) —

    Called for each entry that should be emitted

Yield Parameters:

  • info (Hash) —

    The entry hash



139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
 
# File 'lib/ast/merge/trailing_groups/core.rb', line 139

def emit_remaining_trailing_groups(trailing_groups:, consumed_indices:, &emit_block)
  sorted_anchors(trailing_groups).each do |anchor|
    next if anchor == :prefix # already emitted before the loop

    group = trailing_groups[anchor]
    next unless group

    group.each do |info|
      next if consumed_indices.include?(info[:index])

      emit_block.call(info)
      consumed_indices << info[:index]
    end
  end
end

#flush_ready_trailing_groups(trailing_groups:, matched_indices:, consumed_indices:) {|info| ... } ⇒ void

This method returns an undefined value.

Flush interior trailing groups whose prerequisites are met.

An interior group is one whose anchor is strictly less than the largest matched template index (tail groups are deferred to #emit_remaining_trailing_groups).

A group anchored at template index K is ready when every matched template index in the range 0..K has been consumed. This prevents premature emission when the destination reorders matched items relative to the template.

Parameters:

  • trailing_groups (Hash{Symbol,Integer => Array<Hash>}) —

    The groups built by #build_trailing_groups

  • matched_indices (Set<Integer>) —

    All matched template indices

  • consumed_indices (Set<Integer>) —

    Template indices consumed so far

Yields:

  • (info) —

    Called for each entry that should be emitted

Yield Parameters:

  • info (Hash) —

    The entry hash (contains at least :node, :index)



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
 
# File 'lib/ast/merge/trailing_groups/core.rb', line 101

def flush_ready_trailing_groups(trailing_groups:, matched_indices:, consumed_indices:, &emit_block)
  return if matched_indices.empty?

  last_matched = matched_indices.max

  sorted_anchors(trailing_groups).each do |anchor|
    next if anchor == :prefix
    next if anchor >= last_matched # tail group — defer to remaining pass

    group = trailing_groups[anchor]
    next if group.nil? || group.all? { |info| consumed_indices.include?(info[:index]) }

    # Check if all matched template indices 0..anchor have been consumed
    ready = matched_indices
            .select { |idx| idx <= anchor }
            .all? { |idx| consumed_indices.include?(idx) }
    next unless ready

    group.each do |info|
      next if consumed_indices.include?(info[:index])

      emit_block.call(info)
      consumed_indices << info[:index]
    end
  end
end