1
import type { Logger } from "@/worker/common/logger";
2
 
3
import {
4
  compareSelectionSlots,
5
  copySelectionRow,
6
  selectionDependsOn,
7
  type SelectionTable,
8
} from "./shared";
9
 
10
export function collapseUnsafeRedirectOwners(
11
  table: SelectionTable,
12
  deadSlots: Map<number, number>,
13
  log: Logger
14
): number {
15
  let collapsed = 0;
16
 
17
  while (true) {
18
    const rewrites = collectUnsafeRedirectOwnerRewrites(table, deadSlots);
19
    if (rewrites.length === 0) return collapsed;
20
 
21
    rewrites.sort((a, b) => compareSelectionSlots(table, a.targetSel, b.targetSel));
22
 
23
    for (const rewrite of rewrites) {
24
      rewriteSelectionRowFromSource(table, rewrite.targetSel, rewrite.sourceSel);
25
      collapsed++;
26
 
27
      log.debug("rewrite:collapse-unsafe-redirect-owner", {
28
        targetSel: rewrite.targetSel,
29
        sourceSel: rewrite.sourceSel,
30
        packSlot: table.packSlots[rewrite.targetSel],
31
        entryIndex: table.entryIndices[rewrite.targetSel],
32
        typeCode: table.typeCodes[rewrite.targetSel],
33
      });
34
    }
35
  }
36
}
37
 
38
/**
39
 * Remove dead selection slots and remap baseSel references.
40
 *
41
 * Most dead slots are duplicate-OID selections redirected to another already-
42
 * selected owner. The retained-redirect repair pass should already have
43
 * rewritten any topology-sensitive owners before compaction runs, but this
44
 * final graph walk remains as a guardrail around the remap itself.
45
 */
46
export function compactDeadSlots(
47
  table: SelectionTable,
48
  deadSlots: Map<number, number>,
49
  log: Logger
50
): void {
51
  const safeDeadSlots = pruneUnsafeDeadSlotRedirects(table, deadSlots);
52
 
53
  // 1. Redirect baseSel references from dead slots to their targets.
54
  //    Handles chains (dead → dead → live) by following until stable.
55
  function resolve(sel: number): number {
56
    let cur = sel;
57
    for (let depth = 0; depth < safeDeadSlots.size + 1; depth++) {
58
      const next = safeDeadSlots.get(cur);
59
      if (next === undefined) return cur;
60
      cur = next;
61
    }
62
    return cur; // fallback: should not loop
63
  }
64
 
65
  for (let i = 0; i < table.count; i++) {
66
    if (table.baseSlots[i] >= 0) {
67
      table.baseSlots[i] = resolve(table.baseSlots[i]);
68
    }
69
  }
70
 
71
  // 2. Build old → new index remap (skipping dead slots).
72
  const remap = new Int32Array(table.count).fill(-1);
73
  let write = 0;
74
  for (let read = 0; read < table.count; read++) {
75
    if (safeDeadSlots.has(read)) continue;
76
    remap[read] = write;
77
    if (write !== read) {
78
      // The live row's raw OID stays authoritative for owner lookups and
79
      // follow-on duplicate redirects, so compact the full planner row with it.
80
      // `baseSlots` is row state too: move it now, then remap the preserved
81
      // old live indices to their new compacted indices below.
82
      copySelectionRow(table, write, read);
83
    }
84
    write++;
85
  }
86
 
87
  // 3. Remap baseSel references to new indices.
88
  for (let i = 0; i < write; i++) {
89
    const base = table.baseSlots[i];
90
    if (base >= 0) {
91
      table.baseSlots[i] = remap[base];
92
    }
93
  }
94
 
95
  log.debug("rewrite:compact-dead-slots", {
96
    removed: table.count - write,
97
  });
98
  table.count = write;
99
}
100
 
101
/**
102
 * Some duplicate-owner redirects are not safe to compact away.
103
 *
104
 * If the surviving owner already depends on the duplicate being removed,
105
 * redirecting every reference from `dead -> live` would collapse that live
106
 * row's base chain back onto itself and manufacture a cycle. Callers use this
107
 * to find the remaining rows that still need owner-slot rewrites before the
108
 * duplicate can be compacted away safely.
109
 */
110
export function pruneUnsafeDeadSlotRedirects(
111
  table: SelectionTable,
112
  deadSlots: Map<number, number>
113
): Map<number, number> {
114
  const safeDeadSlots = new Map(deadSlots);
115
 
116
  let changed = true;
117
  while (changed) {
118
    changed = false;
119
 
120
    for (const [deadSel] of safeDeadSlots) {
121
      const targetSel = resolveDeadSlotRedirect(deadSel, safeDeadSlots);
122
      if (targetSel === deadSel || selectionDependsOn(table, targetSel, deadSel)) {
123
        safeDeadSlots.delete(deadSel);
124
        changed = true;
125
      }
126
    }
127
  }
128
 
129
  return safeDeadSlots;
130
}
131
 
132
function collectUnsafeRedirectOwnerRewrites(
133
  table: SelectionTable,
134
  deadSlots: Map<number, number>
135
): Array<{ targetSel: number; sourceSel: number }> {
136
  const rewrites: Array<{ targetSel: number; sourceSel: number }> = [];
137
  const plannedTargets = new Set<number>();
138
 
139
  for (const [deadSel] of deadSlots) {
140
    const targetSel = resolveDeadSlotRedirect(deadSel, deadSlots);
141
    if (targetSel === deadSel || !selectionDependsOn(table, targetSel, deadSel)) {
142
      continue;
143
    }
144
    if (plannedTargets.has(targetSel)) continue;
145
 
146
    const sourceSel = findNearestRedirectDependency(table, targetSel, deadSlots);
147
    if (sourceSel === undefined) continue;
148
 
149
    rewrites.push({ targetSel, sourceSel });
150
    plannedTargets.add(targetSel);
151
  }
152
 
153
  return rewrites;
154
}
155
 
156
function findNearestRedirectDependency(
157
  table: SelectionTable,
158
  targetSel: number,
159
  deadSlots: Map<number, number>
160
): number | undefined {
161
  let cur = targetSel;
162
  for (let depth = 0; depth < table.count; depth++) {
163
    const baseSel = table.baseSlots[cur];
164
    if (baseSel < 0) return undefined;
165
    if (resolveDeadSlotRedirect(baseSel, deadSlots) === targetSel) {
166
      return baseSel;
167
    }
168
    cur = baseSel;
169
  }
170
  return undefined;
171
}
172
 
173
function rewriteSelectionRowFromSource(
174
  table: SelectionTable,
175
  targetSel: number,
176
  sourceSel: number
177
): void {
178
  copySelectionRow(table, targetSel, sourceSel, { preserveTargetOfsPinned: true });
179
  // The rewritten owner row already has a resolved header; make sure it never
180
  // re-enters the header-read queue just because the source row had stale state.
181
  table.queuedForHeader[targetSel] = 0;
182
  // Unsafe-redirect collapse can move a pinned dependency into an already
183
  // pinned owner slot, so the merged row keeps either pin requirement.
184
  table.ofsPinned[targetSel] = table.ofsPinned[targetSel] || table.ofsPinned[sourceSel] ? 1 : 0;
185
}
186
 
187
function resolveDeadSlotRedirect(sel: number, deadSlots: Map<number, number>): number {
188
  let cur = sel;
189
  for (let depth = 0; depth < deadSlots.size + 1; depth++) {
190
    const next = deadSlots.get(cur);
191
    if (next === undefined) return cur;
192
    cur = next;
193
  }
194
  return cur;
195
}