Skip to content

Beautiful, AI-native markdown IDE and LLM wiki

27.2 KB
Raw Blame
import { type LineEnding, spellLineEndings } from '@inkeep/open-knowledge-core';
import {
  isConfigDoc,
  isEditableTextDoc,
  isExcalidrawDoc,
  isMermaidDoc,
  isSystemDoc,
} from './cc1-broadcast.ts';
import { getLogger } from './logger.ts';
import { mdManager } from './md-manager.ts';
import { incrementReconcileConstructCheckSkipped } from './metrics.ts';

export interface ReconcileInput {
  docName: string;
  base: string;
  ours: string;
  theirs: string;
}

export interface KeptBlockPair {
  blockIndex: number;
  base: string;
  ours: string;
  theirs: string;
  landed: 'both' | 'ours' | 'theirs';
}

export interface KeptBlockCounts {
  readonly duplicated: number;
  readonly restoredDeletedHere: number;
  readonly restoredDeletedOutside: number;
}

export function countKeptBlocks(kept: readonly KeptBlockPair[]): KeptBlockCounts {
  let duplicated = 0;
  let restoredDeletedHere = 0;
  let restoredDeletedOutside = 0;
  for (const pair of kept) {
    if (pair.landed === 'both') duplicated++;
    else if (pair.landed === 'theirs') restoredDeletedHere++;
    else restoredDeletedOutside++;
  }
  return { duplicated, restoredDeletedHere, restoredDeletedOutside };
}

export type ReconcileRefusalReason = 'conflict-markers' | 'no-base' | 'too-large' | 'check-failed';

type MergeSide = 'ours' | 'theirs';

type MergeCheckFailure =
  | { readonly check: 'untouched-verbatim'; readonly baseBlockIndex: number }
  | { readonly check: 'side-bytes'; readonly side: MergeSide; readonly sideBlockIndex: number }
  | { readonly check: 'single-occurrence'; readonly outputBlockIndex: number }
  | { readonly check: 'construct'; readonly outputBlockIndex: number }
  | { readonly check: 'parse' };

export type ReconcileOutcome =
  | { kind: 'clean'; newContent: string }
  | { kind: 'merged'; newContent: string; mergedBlocks: number; dedupSkipped?: true }
  | { kind: 'both-kept'; newContent: string; kept: KeptBlockPair[]; dedupSkipped?: true }
  | { kind: 'refused'; reason: Exclude<ReconcileRefusalReason, 'check-failed'> }
  | { kind: 'refused'; reason: 'check-failed'; failure: MergeCheckFailure }
  | { kind: 'noop' };

export const MAX_LCS_CELLS = 4_000_000;

export const MAX_CONSTRUCT_CHECK_BYTES = 256 * 1024;

export const CONFLICT_MARKER_RE = /^(<{7} |={7}$|>{7} |\|{7} )/m;

export function containsConflictMarkers(content: string): boolean {
  return CONFLICT_MARKER_RE.test(content);
}

export function containsUnresolvedConflictBlock(content: string): boolean {
  const start = /^<{7} /m.exec(content);
  if (!start) return false;
  return /^>{7} /m.test(content.slice(start.index + start[0].length));
}

interface MarkdownBlock {
  readonly separator: string;
  readonly text: string;
}

interface MarkdownBlocks {
  readonly blocks: readonly MarkdownBlock[];
  readonly trailing: string;
}

const FENCE_OPEN_RE = /^(`{3,}|~{3,})/;
const BLANK_LINE_RE = /^[ \t]*$/;

export function splitMarkdownDocument(md: string): MarkdownBlocks {
  const blocks: MarkdownBlock[] = [];
  let fenceChar: string | null = null;
  let separatorStart = 0;
  let blockStart = -1;
  let blockEnd = -1;
  let lineStart = 0;

  while (lineStart < md.length) {
    const newline = md.indexOf('\n', lineStart);
    const lineEnd = newline === -1 ? md.length : newline + 1;
    const contentEnd =
      newline === -1
        ? md.length
        : newline > lineStart && md[newline - 1] === '\r'
          ? newline - 1
          : newline;
    const content = md.slice(lineStart, contentEnd);

    const fenceMatch = FENCE_OPEN_RE.exec(content);
    if (fenceMatch) {
      const char = fenceMatch[1][0];
      if (!fenceChar) fenceChar = char;
      else if (char === fenceChar) fenceChar = null;
    }
    const blank = BLANK_LINE_RE.test(content);

    if (!fenceMatch && fenceChar === null && blank) {
      if (blockStart !== -1) {
        blocks.push({
          separator: md.slice(separatorStart, blockStart),
          text: md.slice(blockStart, blockEnd),
        });
        separatorStart = blockEnd;
        blockStart = -1;
      }
    } else {
      if (blockStart === -1) blockStart = lineStart;
      if (!blank) blockEnd = contentEnd;
    }
    lineStart = lineEnd;
  }

  if (blockStart !== -1) {
    blocks.push({
      separator: md.slice(separatorStart, blockStart),
      text: md.slice(blockStart, blockEnd),
    });
    separatorStart = blockEnd;
  }
  return { blocks, trailing: md.slice(separatorStart) };
}

export function splitMarkdownBlocks(md: string): string[] {
  return splitMarkdownDocument(md).blocks.map((block) => block.text);
}

interface BlockDocument extends MarkdownBlocks {
  readonly keys: readonly string[];
}

function blockIdentity(bytes: string): string {
  return spellLineEndings(bytes, '\n');
}

function readBlockDocument(md: string): BlockDocument {
  const split = splitMarkdownDocument(md);
  return { ...split, keys: split.blocks.map((block) => blockIdentity(block.text)) };
}

type LineEndingConvention = 'crlf' | 'lf' | 'mixed' | 'none';

function lineEndingConvention(text: string): LineEndingConvention {
  let crlf = 0;
  let lf = 0;
  for (let i = text.indexOf('\n'); i !== -1; i = text.indexOf('\n', i + 1)) {
    if (i > 0 && text[i - 1] === '\r') crlf++;
    else lf++;
  }
  if (crlf === 0 && lf === 0) return 'none';
  if (lf === 0) return 'crlf';
  if (crlf === 0) return 'lf';
  return 'mixed';
}

function uniformLineEnding(convention: LineEndingConvention): LineEnding | null {
  if (convention === 'crlf') return '\r\n';
  if (convention === 'lf') return '\n';
  return null;
}

function mergeOutputLineEnding(base: string, ours: string, theirs: string): LineEnding | null {
  const baseConvention = lineEndingConvention(base);
  const theirConvention = lineEndingConvention(theirs);
  if (theirConvention !== baseConvention) {
    const converted = uniformLineEnding(theirConvention);
    if (converted) return converted;
  }
  const ourConvention = lineEndingConvention(ours);
  if (ourConvention !== baseConvention) return uniformLineEnding(ourConvention);
  return null;
}

export function reconcile(input: ReconcileInput): ReconcileOutcome {
  if (
    isSystemDoc(input.docName) ||
    isConfigDoc(input.docName) ||
    isMermaidDoc(input.docName) ||
    isExcalidrawDoc(input.docName) ||
    isEditableTextDoc(input.docName)
  )
    return { kind: 'noop' };
  const { base, ours, theirs } = input;

  if (containsConflictMarkers(theirs)) {
    return { kind: 'refused', reason: 'conflict-markers' };
  }

  if (theirs === base) {
    return { kind: 'noop' };
  }

  if (ours === base) {
    return { kind: 'clean', newContent: theirs };
  }

  const baseDoc = readBlockDocument(base);
  if (baseDoc.blocks.every((block) => block.text.trim() === '')) {
    return { kind: 'refused', reason: 'no-base' };
  }

  const ourDoc = readBlockDocument(ours);
  const theirDoc = readBlockDocument(theirs);

  if (
    (baseDoc.blocks.length + 1) * (ourDoc.blocks.length + 1) > MAX_LCS_CELLS ||
    (baseDoc.blocks.length + 1) * (theirDoc.blocks.length + 1) > MAX_LCS_CELLS
  ) {
    return { kind: 'refused', reason: 'too-large' };
  }

  const merge = mergeBlocks(baseDoc, ourDoc, theirDoc, mergeOutputLineEnding(base, ours, theirs));

  const verdict = verifyMergeOutput({
    base,
    ours,
    theirs,
    newContent: merge.newContent,
    dedupSkipped: merge.dedupSkipped,
  });
  if (verdict.failure) return { kind: 'refused', reason: 'check-failed', failure: verdict.failure };
  if (verdict.constructCheck !== 'ran') {
    reportConstructCheckSkipped(input.docName, verdict.constructCheck);
  }

  if (merge.kept.length > 0) {
    return merge.dedupSkipped
      ? { kind: 'both-kept', newContent: merge.newContent, kept: merge.kept, dedupSkipped: true }
      : { kind: 'both-kept', newContent: merge.newContent, kept: merge.kept };
  }

  return merge.dedupSkipped
    ? {
        kind: 'merged',
        newContent: merge.newContent,
        mergedBlocks: merge.mergedBlocks,
        dedupSkipped: true,
      }
    : { kind: 'merged', newContent: merge.newContent, mergedBlocks: merge.mergedBlocks };
}

interface EmittedBlock {
  readonly text: string;
  readonly separator: string | null;
}

interface BlockMerge {
  readonly newContent: string;
  readonly mergedBlocks: number;
  readonly kept: KeptBlockPair[];
  readonly dedupSkipped: boolean;
}

function interBlockSeparator(doc: BlockDocument, index: number): string | null {
  return index === 0 ? null : doc.blocks[index].separator;
}

function sameModuloLineEndings(a: string | null, b: string | null): boolean {
  if (a === null || b === null) return a === b;
  return blockIdentity(a) === blockIdentity(b);
}

function pickThreeWay<T extends string | null>(
  base: T,
  ours: T | undefined,
  theirs: T | undefined,
): T {
  if (theirs !== undefined && !sameModuloLineEndings(theirs, base)) return theirs;
  if (ours !== undefined) return ours;
  return theirs ?? base;
}

function sideSeparator(doc: BlockDocument, op: EditOp): string | null | undefined {
  return op.editIndex === undefined ? undefined : interBlockSeparator(doc, op.editIndex);
}

function firstInterBlockSeparator(docs: readonly BlockDocument[], fallback: string): string {
  for (const doc of docs) {
    if (doc.blocks.length > 1) return doc.blocks[1].separator;
  }
  return fallback;
}

function mergeBlocks(
  base: BlockDocument,
  ours: BlockDocument,
  theirs: BlockDocument,
  outputLineEnding: LineEnding | null,
): BlockMerge {
  const ourEdits = computeEditOps(base.keys, ours.keys);
  const theirEdits = computeEditOps(base.keys, theirs.keys);

  const emitted: EmittedBlock[] = [];
  const kept: KeptBlockPair[] = [];
  let dedupSkipped = false;

  for (let i = 0; i < base.blocks.length; i++) {
    const ourOp = ourEdits.blockOps[i];
    const theirOp = theirEdits.blockOps[i];

    if (pushInsertGroupDeduped(emitted, ours, ourOp.insertsBefore, theirs, theirOp.insertsBefore))
      dedupSkipped = true;

    const anchored = (text: string): void => {
      emitted.push({
        text,
        separator: pickThreeWay(
          interBlockSeparator(base, i),
          sideSeparator(ours, ourOp),
          sideSeparator(theirs, theirOp),
        ),
      });
    };
    const ourText = ourOp.action === 'modify' ? ours.blocks[ourOp.editIndex].text : null;
    const theirText = theirOp.action === 'modify' ? theirs.blocks[theirOp.editIndex].text : null;

    if (ourOp.action === 'keep' && theirOp.action === 'keep') {
      anchored(base.blocks[i].text);
    } else if (ourOp.action === 'keep') {
      if (theirText !== null) anchored(theirText);
    } else if (theirOp.action === 'keep') {
      if (ourText !== null) anchored(ourText);
    } else {
      const ourKey = ourText === null ? null : blockIdentity(ourText);
      const theirKey = theirText === null ? null : blockIdentity(theirText);
      if (ourText !== null) anchored(ourText);
      if (ourKey !== theirKey) {
        let landed: KeptBlockPair['landed'] = 'ours';
        if (theirText !== null) {
          if (ourText === null) {
            landed = 'theirs';
            anchored(theirText);
          } else {
            landed = 'both';
            emitted.push({ text: theirText, separator: sideSeparator(theirs, theirOp) ?? null });
          }
        }
        kept.push({
          blockIndex: i,
          base: base.blocks[i].text,
          ours: ourText ?? '',
          theirs: theirText ?? '',
          landed,
        });
      }
    }
  }

  if (
    pushInsertGroupDeduped(
      emitted,
      ours,
      ourEdits.trailingInserts,
      theirs,
      theirEdits.trailingInserts,
    )
  )
    dedupSkipped = true;

  const leading = pickThreeWay(
    base.blocks[0]?.separator ?? '',
    ours.blocks[0]?.separator ?? '',
    theirs.blocks[0]?.separator ?? '',
  );
  const trailing = pickThreeWay(base.trailing, ours.trailing, theirs.trailing);
  const fallbackSeparator = firstInterBlockSeparator(
    [base, ours, theirs],
    base.trailing.startsWith('\r\n') ? '\r\n\r\n' : '\n\n',
  );

  let assembled = '';
  if (emitted.length > 0) {
    emitted.forEach((block, index) => {
      assembled += index === 0 ? leading : (block.separator ?? fallbackSeparator);
      assembled += block.text;
    });
    assembled += trailing;
  }

  return {
    newContent: outputLineEnding ? spellLineEndings(assembled, outputLineEnding) : assembled,
    mergedBlocks: emitted.length,
    kept,
    dedupSkipped,
  };
}

function pushInsertGroupDeduped(
  target: EmittedBlock[],
  ours: BlockDocument,
  ourInserts: readonly number[],
  theirs: BlockDocument,
  theirInserts: readonly number[],
): boolean {
  const pushOurs = (index: number): void => {
    target.push({ text: ours.blocks[index].text, separator: interBlockSeparator(ours, index) });
  };
  const pushTheirs = (index: number): void => {
    target.push({ text: theirs.blocks[index].text, separator: interBlockSeparator(theirs, index) });
  };
  if ((ourInserts.length + 1) * (theirInserts.length + 1) > MAX_LCS_CELLS) {
    for (const index of ourInserts) pushOurs(index);
    for (const index of theirInserts) pushTheirs(index);
    return true;
  }
  const spine = longestCommonSubsequence(
    ourInserts.map((index) => ours.keys[index]),
    theirInserts.map((index) => theirs.keys[index]),
  );
  let ourCursor = 0;
  let theirCursor = 0;
  for (const [ourMatch, theirMatch] of spine) {
    while (ourCursor < ourMatch) pushOurs(ourInserts[ourCursor++]);
    while (theirCursor < theirMatch) pushTheirs(theirInserts[theirCursor++]);
    pushOurs(ourInserts[ourMatch]);
    ourCursor = ourMatch + 1;
    theirCursor = theirMatch + 1;
  }
  while (ourCursor < ourInserts.length) pushOurs(ourInserts[ourCursor++]);
  while (theirCursor < theirInserts.length) pushTheirs(theirInserts[theirCursor++]);
  return false;
}

type EditOp =
  | { action: 'keep'; editIndex: number; insertsBefore: number[] }
  | { action: 'modify'; editIndex: number; insertsBefore: number[] }
  | { action: 'delete'; editIndex?: undefined; insertsBefore: number[] };

interface EditScript {
  readonly blockOps: readonly EditOp[];
  readonly trailingInserts: readonly number[];
}

function computeEditOps(baseKeys: readonly string[], editedKeys: readonly string[]): EditScript {
  const lcs = longestCommonSubsequence(baseKeys, editedKeys);
  const editOfBase = new Array<number>(baseKeys.length).fill(-1);
  const matchedEdit = new Array<boolean>(editedKeys.length).fill(false);
  for (const [bi, ei] of lcs) {
    editOfBase[bi] = ei;
    matchedEdit[ei] = true;
  }
  const nextAnchorEdit = new Array<number>(baseKeys.length + 1).fill(editedKeys.length);
  for (let bi = baseKeys.length - 1; bi >= 0; bi--) {
    nextAnchorEdit[bi] = editOfBase[bi] === -1 ? nextAnchorEdit[bi + 1] : editOfBase[bi];
  }

  const blockOps: EditOp[] = [];
  let prevEditAnchor = -1;

  for (let bi = 0; bi < baseKeys.length; bi++) {
    const editIdx = editOfBase[bi];
    if (editIdx !== -1) {
      const inserts: number[] = [];
      for (let ei = prevEditAnchor + 1; ei < editIdx; ei++) {
        if (!matchedEdit[ei]) inserts.push(ei);
      }
      blockOps.push({ action: 'keep', editIndex: editIdx, insertsBefore: inserts });
      prevEditAnchor = editIdx;
      continue;
    }
    let candidate = -1;
    for (let ei = prevEditAnchor + 1; ei < nextAnchorEdit[bi + 1]; ei++) {
      if (!matchedEdit[ei]) {
        candidate = ei;
        break;
      }
    }
    if (candidate === -1) {
      blockOps.push({ action: 'delete', insertsBefore: [] });
    } else {
      matchedEdit[candidate] = true;
      blockOps.push({ action: 'modify', editIndex: candidate, insertsBefore: [] });
    }
  }

  const trailingInserts: number[] = [];
  for (let ei = prevEditAnchor + 1; ei < editedKeys.length; ei++) {
    if (!matchedEdit[ei]) trailingInserts.push(ei);
  }
  return { blockOps, trailingInserts };
}

function longestCommonSubsequence(a: readonly string[], b: readonly string[]): [number, number][] {
  const m = a.length;
  const n = b.length;
  const stride = n + 1;
  const dp = new Uint32Array((m + 1) * stride);

  for (let i = 1; i <= m; i++) {
    const rowBase = i * stride;
    const prevRowBase = (i - 1) * stride;
    for (let j = 1; j <= n; j++) {
      if (a[i - 1] === b[j - 1]) {
        dp[rowBase + j] = dp[prevRowBase + (j - 1)] + 1;
      } else {
        const top = dp[prevRowBase + j];
        const left = dp[rowBase + (j - 1)];
        dp[rowBase + j] = top > left ? top : left;
      }
    }
  }

  const pairs: [number, number][] = [];
  let i = m;
  let j = n;
  while (i > 0 && j > 0) {
    if (a[i - 1] === b[j - 1]) {
      pairs.push([i - 1, j - 1]);
      i--;
      j--;
    } else if (dp[(i - 1) * stride + j] >= dp[i * stride + (j - 1)]) {
      i--;
    } else {
      j--;
    }
  }

  return pairs.reverse();
}

interface MergeCheckInput {
  readonly base: string;
  readonly ours: string;
  readonly theirs: string;
  readonly newContent: string;
  readonly dedupSkipped: boolean;
}

type ConstructCheckRun = 'ran' | 'skipped-oversized' | 'skipped-unparsed-source';

interface MergeVerdict {
  readonly failure: MergeCheckFailure | null;
  readonly constructCheck: ConstructCheckRun;
}

type CheckedDocument = 'base' | MergeSide | 'output';

interface BlockSource {
  readonly document: CheckedDocument;
  readonly index: number;
}

interface SideAlignment {
  readonly sideOfBase: readonly number[];
  readonly gapStart: readonly number[];
  readonly gapEnd: readonly number[];
  readonly unmatched: readonly number[];
}

interface Occurrence {
  readonly key: string;
  readonly expected: readonly string[];
  readonly sources: readonly BlockSource[];
  readonly side: MergeSide;
  readonly sideBlockIndex: number;
  consumed: boolean;
}

function alignToBase(baseKeys: readonly string[], sideKeys: readonly string[]): SideAlignment {
  const sideOfBase = new Array<number>(baseKeys.length).fill(-1);
  const baseOfSide = new Array<number>(sideKeys.length).fill(-1);
  for (const [bi, si] of longestCommonSubsequence(baseKeys, sideKeys)) {
    sideOfBase[bi] = si;
    baseOfSide[si] = bi;
  }
  const gapStart = new Array<number>(sideKeys.length).fill(-1);
  const gapEnd = new Array<number>(sideKeys.length).fill(baseKeys.length);
  const unmatched: number[] = [];
  let previous = -1;
  for (let si = 0; si < sideKeys.length; si++) {
    if (baseOfSide[si] === -1) {
      gapStart[si] = previous;
      unmatched.push(si);
    } else previous = baseOfSide[si];
  }
  let next = baseKeys.length;
  for (let si = sideKeys.length - 1; si >= 0; si--) {
    if (baseOfSide[si] === -1) gapEnd[si] = next;
    else next = baseOfSide[si];
  }
  return { sideOfBase, gapStart, gapEnd, unmatched };
}

function gapsOverlap(a: SideAlignment, ai: number, b: SideAlignment, bi: number): boolean {
  return Math.max(a.gapStart[ai], b.gapStart[bi]) < Math.min(a.gapEnd[ai], b.gapEnd[bi]);
}

function indexByKey(keys: readonly string[], indices: readonly number[]): Map<string, number[]> {
  const byKey = new Map<string, number[]>();
  for (const index of indices) {
    const bucket = byKey.get(keys[index]);
    if (bucket) bucket.push(index);
    else byKey.set(keys[index], [index]);
  }
  return byKey;
}

function collectOccurrences(
  ours: BlockDocument,
  ourAlignment: SideAlignment,
  theirs: BlockDocument,
  theirAlignment: SideAlignment,
  pairIdentical: boolean,
  expectBytes: (raw: string) => string,
): Map<string, Occurrence[]> {
  const occurrences = new Map<string, Occurrence[]>();
  const add = (occurrence: Occurrence): void => {
    const bucket = occurrences.get(occurrence.key);
    if (bucket) bucket.push(occurrence);
    else occurrences.set(occurrence.key, [occurrence]);
  };
  const theirsByKey = indexByKey(theirs.keys, theirAlignment.unmatched);
  const pairedTheirs = new Set<number>();
  for (const oi of ourAlignment.unmatched) {
    const key = ours.keys[oi];
    const ourBytes = expectBytes(ours.blocks[oi].text);
    const twin = pairIdentical
      ? theirsByKey
          .get(key)
          ?.find((ti) => !pairedTheirs.has(ti) && gapsOverlap(ourAlignment, oi, theirAlignment, ti))
      : undefined;
    if (twin !== undefined) pairedTheirs.add(twin);
    add({
      key,
      expected: twin === undefined ? [ourBytes] : [ourBytes, expectBytes(theirs.blocks[twin].text)],
      sources:
        twin === undefined
          ? [{ document: 'ours', index: oi }]
          : [
              { document: 'ours', index: oi },
              { document: 'theirs', index: twin },
            ],
      side: 'ours',
      sideBlockIndex: oi,
      consumed: false,
    });
  }
  for (const ti of theirAlignment.unmatched) {
    if (pairedTheirs.has(ti)) continue;
    add({
      key: theirs.keys[ti],
      expected: [expectBytes(theirs.blocks[ti].text)],
      sources: [{ document: 'theirs', index: ti }],
      side: 'theirs',
      sideBlockIndex: ti,
      consumed: false,
    });
  }
  return occurrences;
}

export function checkMergeOutput(input: MergeCheckInput): MergeCheckFailure | null {
  return verifyMergeOutput(input).failure;
}

function failed(failure: MergeCheckFailure): MergeVerdict {
  return { failure, constructCheck: 'ran' };
}

function verifyMergeOutput(input: MergeCheckInput): MergeVerdict {
  const outputLineEnding = mergeOutputLineEnding(input.base, input.ours, input.theirs);
  const expectBytes = (raw: string): string =>
    outputLineEnding ? spellLineEndings(raw, outputLineEnding) : raw;
  const base = readBlockDocument(input.base);
  const ours = readBlockDocument(input.ours);
  const theirs = readBlockDocument(input.theirs);
  const output = readBlockDocument(input.newContent);
  const ourAlignment = alignToBase(base.keys, ours.keys);
  const theirAlignment = alignToBase(base.keys, theirs.keys);

  const untouched: number[] = [];
  for (let bi = 0; bi < base.keys.length; bi++) {
    if (ourAlignment.sideOfBase[bi] !== -1 && theirAlignment.sideOfBase[bi] !== -1)
      untouched.push(bi);
  }

  const sources = new Array<readonly BlockSource[]>(output.blocks.length).fill([]);
  const rest: number[] = [];
  let nextUntouched = 0;
  for (let k = 0; k < output.blocks.length; k++) {
    const bi = untouched[nextUntouched];
    if (bi === undefined || output.keys[k] !== base.keys[bi]) {
      rest.push(k);
      continue;
    }
    if (output.blocks[k].text !== expectBytes(base.blocks[bi].text)) {
      return failed({ check: 'untouched-verbatim', baseBlockIndex: bi });
    }
    sources[k] = [
      { document: 'base', index: bi },
      { document: 'ours', index: ourAlignment.sideOfBase[bi] },
      { document: 'theirs', index: theirAlignment.sideOfBase[bi] },
    ];
    nextUntouched++;
  }
  if (nextUntouched < untouched.length) {
    return failed({ check: 'untouched-verbatim', baseBlockIndex: untouched[nextUntouched] });
  }

  const occurrences = collectOccurrences(
    ours,
    ourAlignment,
    theirs,
    theirAlignment,
    !input.dedupSkipped,
    expectBytes,
  );

  const unclaimed: number[] = [];
  for (const k of rest) {
    const candidates = (occurrences.get(output.keys[k]) ?? []).filter(
      (occurrence) => !occurrence.consumed,
    );
    if (candidates.length === 0) {
      unclaimed.push(k);
      continue;
    }
    const bytes = output.blocks[k].text;
    const exact = candidates.find((c) => c.expected.includes(bytes));
    if (!exact) {
      return failed({
        check: 'side-bytes',
        side: candidates[0].side,
        sideBlockIndex: candidates[0].sideBlockIndex,
      });
    }
    exact.consumed = true;
    sources[k] = exact.sources;
  }

  for (const bucket of occurrences.values()) {
    const missing = bucket.find((occurrence) => !occurrence.consumed);
    if (missing) {
      return failed({
        check: 'side-bytes',
        side: missing.side,
        sideBlockIndex: missing.sideBlockIndex,
      });
    }
  }
  if (unclaimed.length > 0) {
    return failed({ check: 'single-occurrence', outputBlockIndex: unclaimed[0] });
  }

  return checkConstructs(
    { base: input.base, ours: input.ours, theirs: input.theirs, output: input.newContent },
    sources,
  );
}

interface RootSpan {
  readonly type: string;
  readonly startLine: number;
  readonly endLine: number;
}

interface ParsedDocument {
  readonly spans: readonly RootSpan[];
  readonly blockLines: readonly (readonly [number, number])[];
}

function parseDocument(md: string): ParsedDocument | null {
  let root: ReturnType<typeof mdManager.parseToMdast>;
  try {
    root = mdManager.parseToMdast(md);
  } catch {
    return null;
  }
  const spans: RootSpan[] = [];
  for (const child of root.children) {
    if (!child.position) continue;
    spans.push({
      type: child.type,
      startLine: child.position.start.line,
      endLine: child.position.end.line,
    });
  }
  return { spans, blockLines: blockLineRanges(md) };
}

const LINE_ENDING_RE = /\r\n|\r|\n/g;

function blockLineRanges(md: string): (readonly [number, number])[] {
  const lineStarts = [0];
  for (const match of md.matchAll(LINE_ENDING_RE)) lineStarts.push(match.index + match[0].length);
  const lineOf = (offset: number): number => {
    let lo = 0;
    let hi = lineStarts.length - 1;
    while (lo < hi) {
      const mid = (lo + hi + 1) >>> 1;
      if (lineStarts[mid] <= offset) lo = mid;
      else hi = mid - 1;
    }
    return lo + 1;
  };
  const ranges: (readonly [number, number])[] = [];
  let offset = 0;
  for (const block of splitMarkdownDocument(md).blocks) {
    offset += block.separator.length;
    ranges.push([lineOf(offset), lineOf(offset + block.text.length - 1)]);
    offset += block.text.length;
  }
  return ranges;
}

function coveringTypes(
  spans: readonly RootSpan[],
  [startLine, endLine]: readonly [number, number],
): string {
  let lo = 0;
  let hi = spans.length;
  while (lo < hi) {
    const mid = (lo + hi) >>> 1;
    if (spans[mid].endLine < startLine) lo = mid + 1;
    else hi = mid;
  }
  const types: string[] = [];
  for (let i = lo; i < spans.length && spans[i].startLine <= endLine; i++)
    types.push(spans[i].type);
  return types.join(' ');
}

function reportConstructCheckSkipped(
  docName: string,
  reason: Exclude<ConstructCheckRun, 'ran'>,
): void {
  incrementReconcileConstructCheckSkipped();
  getLogger('reconcile').info(
    { docName, reason, limitBytes: MAX_CONSTRUCT_CHECK_BYTES },
    `[reconcile] ${docName} construct check skipped (${reason}); the byte checks still ran`,
  );
}

function checkConstructs(
  texts: Readonly<Record<CheckedDocument, string>>,
  sources: readonly (readonly BlockSource[])[],
): MergeVerdict {
  const largestBytes = Math.max(...Object.values(texts).map((text) => Buffer.byteLength(text)));
  if (largestBytes > MAX_CONSTRUCT_CHECK_BYTES) {
    return { failure: null, constructCheck: 'skipped-oversized' };
  }
  const base = parseDocument(texts.base);
  const ours = parseDocument(texts.ours);
  const theirs = parseDocument(texts.theirs);
  if (!base || !ours || !theirs)
    return { failure: null, constructCheck: 'skipped-unparsed-source' };
  const output = parseDocument(texts.output);
  if (!output) return failed({ check: 'parse' });
  const parsed: Readonly<Record<CheckedDocument, ParsedDocument>> = { base, ours, theirs, output };

  const constructAt = (source: BlockSource): string | null => {
    const document = parsed[source.document];
    const lines = document.blockLines[source.index];
    return lines ? coveringTypes(document.spans, lines) : null;
  };

  for (let k = 0; k < sources.length; k++) {
    const merged = constructAt({ document: 'output', index: k });
    const stable =
      merged !== null &&
      sources[k].some((source) => source.index !== -1 && constructAt(source) === merged);
    if (!stable) return failed({ check: 'construct', outputBlockIndex: k });
  }
  return { failure: null, constructCheck: 'ran' };
}