Skip to content

Garry's Opinionated OpenClaw/Hermes Agent Brain

TypeScript
11.6 KB
Raw Blame
/**
 * edit_page's retained diff must stay bounded on large pages: past a cell
 * budget only the changed window is line-diffed, and a window that is
 * itself too large becomes one coarse hunk marked `diff_coarse`.
 *
 * 1. Protects: edit_page on large pages (a one-line edit on a 50k-line page
 *    filled a 2.5-billion-cell LCS table before the fix) and the receipt
 *    diff of every ordinary edit, which stays byte-identical.
 * 2. Fails when: editDiff output changes for pages under the budget
 *    (differential vs the old editDiff), a bounded diff stops applying to
 *    the old text to give the new text (strict applier over a seeded
 *    corpus with small budgets), a no-newline marker appears away from
 *    end-of-file, or the LCS table grows past the budget (fill probe).
 * 3. Existing coverage: test/edit-page.test.ts pins the 8 KB cut and the
 *    50k-line case end to end; test/skillpack-apply-hunks.test.ts pins
 *    unifiedDiff itself against its applier.
 * 4. Seam: boundedUnifiedDiff is exported (@internal) so small budgets
 *    reach the windowed and coarse arms without large inputs.
 */
import { describe, expect, test } from 'bun:test';
import {
  EDIT_PAGE_DIFF_CELL_BUDGET,
  EDIT_PAGE_DIFF_MAX_BYTES,
  boundedUnifiedDiff,
  editDiff,
} from '../../src/core/persistence/page-edit.ts';
import { splitLines, unifiedDiff } from '../../src/core/skillpack/diff-text.ts';
import { redactRetrievalOutput } from '../../src/core/search/output-redaction.ts';
import { mulberry32 } from '../helpers/seeded-random.ts';

const MARKER = '\\ No newline at end of file';

/** editDiff before the cell budget. */
function oracleEditDiff(slug: string, before: string, after: string): { diff: string; diff_truncated?: true } {
  const [{ diff: full }] = redactRetrievalOutput([{ diff: unifiedDiff(before, after, { oldPath: `a/${slug}.md`, newPath: `b/${slug}.md` }) }], {}).results;
  const encoded = (text: string) => Buffer.byteLength(JSON.stringify(text));
  if (encoded(full) <= EDIT_PAGE_DIFF_MAX_BYTES) return { diff: full };
  let kept = '';
  for (const line of full.split('\n')) {
    if (encoded(`${kept}${line}\n`) > EDIT_PAGE_DIFF_MAX_BYTES) break;
    kept += `${line}\n`;
  }
  return { diff: kept, diff_truncated: true };
}

/**
 * Apply a unified diff produced by this repo's writer to `before`, checking
 * every context and removed line, hunk counts, hunk order, and that each
 * no-newline marker sits at end-of-file. A hunk starting at `-s` consumes
 * old lines from index s - 1 (the writer's convention, also for empty
 * old ranges). Returns the new text.
 */
function applyStrict(before: string, diff: string): string {
  const a = splitLines(before);
  if (diff === '') return before;
  const lines = diff.split('\n');
  expect(lines.pop()).toBe('');
  expect(lines[0]!.startsWith('--- ')).toBe(true);
  expect(lines[1]!.startsWith('+++ ')).toBe(true);
  const out: string[] = [];
  let cursor = 0;
  let newLacksNewline = false;
  let k = 2;
  while (k < lines.length) {
    const h = /^@@ -(\d+),(\d+) \+(\d+),(\d+) @@$/.exec(lines[k]!);
    expect(h).not.toBeNull();
    const [aStart, aCount, bStart, bCount] = h!.slice(1).map(Number) as [number, number, number, number];
    const at = aStart - 1;
    expect(at).toBeGreaterThanOrEqual(cursor);
    out.push(...a.lines.slice(cursor, at));
    expect(bStart - 1).toBe(out.length);
    let pos = at;
    let added = 0;
    k++;
    while (k < lines.length && !lines[k]!.startsWith('@@ ')) {
      const line = lines[k]!;
      const kind = line[0];
      if (kind === '\\') {
        expect(line).toBe(MARKER);
        const prev = lines[k - 1]![0];
        const twice = lines[k + 1] === MARKER;
        // The marker closes the old side, the new side, or both (twice). A
        // single marker after a context line closes the old side only when
        // that line ended the old text.
        const oldSide = prev === '-' || (prev === ' ' && (twice || (pos === a.lines.length && !a.trailingNewline)));
        const newSide = prev === '+' || (prev === ' ' && (twice || !oldSide));
        if (oldSide) expect({ pos, n: a.lines.length, trailing: a.trailingNewline }).toEqual({ pos: a.lines.length, n: a.lines.length, trailing: false });
        if (newSide) newLacksNewline = true;
        k += twice ? 2 : 1;
        continue;
      }
      const text = line.slice(1);
      if (kind === ' ' || kind === '-') {
        expect(a.lines[pos]).toBe(text);
        pos++;
      }
      if (kind === ' ' || kind === '+') {
        out.push(text);
        added++;
      }
      expect(' -+'.includes(kind!)).toBe(true);
      k++;
    }
    expect(pos - at).toBe(aCount);
    expect(added).toBe(bCount);
    cursor = pos;
  }
  const atEnd = cursor === a.lines.length;
  out.push(...a.lines.slice(cursor));
  if (out.length === 0) return '';
  const trailing = atEnd ? !newLacksNewline : a.trailingNewline;
  return out.join('\n') + (trailing ? '\n' : '');
}

function randomPage(rand: () => number, alphabet: string[]): string[] {
  return Array.from({ length: Math.floor(rand() * 30) }, () => alphabet[Math.floor(rand() * alphabet.length)]!);
}

function mutate(rand: () => number, lines: string[], alphabet: string[]): string[] {
  const out = [...lines];
  const edits = 1 + Math.floor(rand() * 4);
  for (let e = 0; e < edits; e++) {
    const at = Math.floor(rand() * (out.length + 1));
    const del = Math.floor(rand() * 3);
    const ins = Array.from({ length: Math.floor(rand() * 3) }, () => alphabet[Math.floor(rand() * alphabet.length)]!);
    out.splice(at, del, ...ins);
  }
  return out;
}

describe('editDiff stays identical under the budget', () => {
  test('ordinary edits produce the old editDiff byte for byte', () => {
    const rand = mulberry32(0x0b16_d1ff);
    const alphabet = ['alpha', 'beta', 'gamma', '', 'alice-example met acme-example', 'x'.repeat(400)];
    for (let k = 0; k < 2_000; k++) {
      const before = randomPage(rand, alphabet);
      const after = mutate(rand, before, alphabet);
      const a = before.join('\n') + (rand() < 0.8 ? '\n' : '');
      const b = after.join('\n') + (rand() < 0.8 ? '\n' : '');
      expect(editDiff('notes/x', a, b)).toEqual(oracleEditDiff('notes/x', a, b));
    }
  });
});

describe('boundedUnifiedDiff over budget (seeded corpus, small budgets)', () => {
  test('every windowed or coarse diff applies strictly and reproduces the new text', () => {
    const rand = mulberry32(0x0b16_d1ff ^ 0x5eed);
    const alphabet = ['a', 'b', 'c', '', ' a', '-a', '+a'];
    let windowed = 0;
    let coarse = 0;
    for (let k = 0; k < 20_000; k++) {
      const beforeLines = randomPage(rand, alphabet);
      const afterLines = mutate(rand, beforeLines, alphabet);
      const aTrailing = rand() < 0.7;
      const bTrailing = rand() < 0.5 ? aTrailing : rand() < 0.7;
      const before = beforeLines.length ? beforeLines.join('\n') + (aTrailing ? '\n' : '') : '';
      const after = afterLines.length ? afterLines.join('\n') + (bTrailing ? '\n' : '') : '';
      const budget = [1, 4, 12, 30, 80, 200][k % 6]!;
      const { diff, coarse: isCoarse } = boundedUnifiedDiff(before, after, 'a/p.md', 'b/p.md', budget);
      const aSplit = splitLines(before);
      const bSplit = splitLines(after);
      const n = aSplit.lines.length;
      const m = bSplit.lines.length;
      if ((n + 1) * (m + 1) <= budget) {
        expect({ diff, isCoarse }).toEqual({ diff: unifiedDiff(before, after, { oldPath: 'a/p.md', newPath: 'b/p.md' }), isCoarse: false });
        continue;
      }
      if (isCoarse) coarse++;
      else windowed++;
      if (aSplit.trailingNewline === bSplit.trailingNewline || before === '' || after === '') {
        expect(applyStrict(before, diff)).toBe(after);
      } else {
        // A change of the final newline alone is no line change to
        // unifiedDiff, so only the lines are compared here.
        expect(splitLines(applyStrict(before.endsWith('\n') ? before : before + '\n', diff.split('\n').filter(l => l !== MARKER).join('\n'))).lines)
          .toEqual(splitLines(after).lines);
      }
    }
    // The corpus reaches both arms.
    expect(windowed).toBeGreaterThan(1_000);
    expect(coarse).toBeGreaterThan(1_000);
  });

  test('a far-from-end edit in files without a final newline carries no marker', () => {
    const lines = Array.from({ length: 40 }, (_, i) => `line ${i}`);
    const before = lines.join('\n');
    const after = lines.map((l, i) => (i === 5 ? 'edited' : l)).join('\n');
    const { diff, coarse } = boundedUnifiedDiff(before, after, 'a', 'b', 100);
    expect(coarse).toBe(false);
    expect(diff).toBe(['--- a', '+++ b', '@@ -3,7 +3,7 @@', ' line 2', ' line 3', ' line 4', '-line 5', '+edited', ' line 6', ' line 7', ' line 8', ''].join('\n'));
    expect(applyStrict(before, diff)).toBe(after);
  });

  test('a near-end edit keeps both markers at end-of-file', () => {
    const lines = Array.from({ length: 40 }, (_, i) => `line ${i}`);
    const before = lines.join('\n');
    const after = lines.map((l, i) => (i === 38 ? 'edited' : l)).join('\n');
    const { diff } = boundedUnifiedDiff(before, after, 'a', 'b', 100);
    expect(diff.endsWith(` line 39\n${MARKER}\n${MARKER}\n`)).toBe(true);
    expect(applyStrict(before, diff)).toBe(after);
  });

  test('identical lines return an empty diff, like unifiedDiff', () => {
    const page = Array.from({ length: 100 }, (_, i) => `l${i}`).join('\n');
    expect(boundedUnifiedDiff(page, page, 'a', 'b', 10)).toEqual({ diff: '', coarse: false });
    expect(boundedUnifiedDiff(`${page}\n`, page, 'a', 'b', 10)).toEqual({ diff: unifiedDiff(`${page}\n`, page), coarse: false });
  });
});

/** Cells written by Array.prototype.fill (the LCS table rows) while `fn` runs. */
function countFilledCells(fn: () => void): number {
  const fill = Array.prototype.fill;
  let cells = 0;
  Array.prototype.fill = function (this: unknown[], ...args: unknown[]) {
    cells += this.length;
    return (fill as (...a: unknown[]) => unknown[]).apply(this, args);
  } as typeof Array.prototype.fill;
  try {
    fn();
  } finally {
    Array.prototype.fill = fill;
  }
  return cells;
}

describe('editDiff cell-budget probe', () => {
  const page = (n: number, tag = '') => Array.from({ length: n }, (_, i) => `Row ${i}${tag} of the page.`);

  test('a one-line edit just past the budget fills a window-sized table; the old diff filled the full one', () => {
    const before = page(2_000);
    const after = before.map((l, i) => (i === 1_000 ? 'Row 1000 was edited.' : l));
    const a = before.join('\n') + '\n';
    const b = after.join('\n') + '\n';
    let result: ReturnType<typeof editDiff> = { diff: '' };
    const cells = countFilledCells(() => { result = editDiff('notes/p', a, b); });
    expect(cells).toBeLessThanOrEqual(100);
    expect(result.diff_coarse).toBeUndefined();
    expect(applyStrict(a, result.diff)).toBe(b);
    const oldCells = countFilledCells(() => { oracleEditDiff('notes/p', a, b); });
    expect(oldCells).toBeGreaterThan(EDIT_PAGE_DIFF_CELL_BUDGET);
  });

  test('a rewrite of every line past the budget is one coarse hunk with no table at all', () => {
    const a = Array.from({ length: 2_100 }, (_, i) => `r${i}`).join('\n') + '\n';
    const b = Array.from({ length: 2_100 }, (_, i) => `s${i}`).join('\n') + '\n';
    let result: ReturnType<typeof editDiff> = { diff: '' };
    const cells = countFilledCells(() => { result = editDiff('notes/p', a, b); });
    expect(cells).toBe(0);
    expect(result.diff_coarse).toBe(true);
    expect(result.diff_truncated).toBe(true);
    expect(result.diff.split('\n').slice(0, 4)).toEqual(['--- a/notes/p.md', '+++ b/notes/p.md', '@@ -1,2100 +1,2100 @@', '-r0']);
    const full = boundedUnifiedDiff(a, b, 'a/notes/p.md', 'b/notes/p.md');
    expect(full.coarse).toBe(true);
    expect(applyStrict(a, full.diff)).toBe(b);
  });
});