Beautiful, AI-native markdown IDE and LLM wiki
TypeScript 2nd-brainagent-skillsclaudecodexcompany-braindocsknowledge-knowledge-baseknowledge-managementllmllm-wikillm-wiki-karpathymarkdownmarkdown-editormdmdxnotespkmsecond-brainskills
import { MarkdownManager, sharedExtensions } from '@inkeep/open-knowledge-core';
import type { JSONContent } from '@tiptap/core';
import { describe, expect, test } from 'vitest';
import {
computeMapDrivenBodySplice,
createEditorMdastMemo,
type EditorMdastMemo,
} from './map-driven-splice.ts';
import type { MapDrivenSpliceMemoSkipReason } from './metrics.ts';
import { createCountingManager } from './parse-counting.test-helper.ts';
const mdManager = new MarkdownManager({ extensions: sharedExtensions });
function applySplice(
oldBody: string,
splice: { spliceStart: number; spliceEnd: number; newSlice: string },
): string {
return oldBody.slice(0, splice.spliceStart) + splice.newSlice + oldBody.slice(splice.spliceEnd);
}
function pmFromMd(md: string): JSONContent {
return mdManager.parse(md);
}
describe('computeMapDrivenBodySplice', () => {
describe('byte preservation outside the splice', () => {
test('single-block edit produces splice covering only the edited block', () => {
const oldBody = '# Heading\n\nFirst paragraph.\n\nSecond paragraph.\n';
const newBody = '# Heading\n\nFirst paragraph EDITED.\n\nSecond paragraph.\n';
const splice = computeMapDrivenBodySplice(oldBody, pmFromMd(newBody), mdManager);
expect(splice).not.toBeNull();
if (!splice) return;
const headingEnd = oldBody.indexOf('# Heading') + '# Heading'.length;
expect(splice.spliceStart).toBeGreaterThanOrEqual(headingEnd);
const secondParaStart = oldBody.indexOf('Second paragraph');
expect(splice.spliceEnd).toBeLessThanOrEqual(secondParaStart);
expect(oldBody.slice(0, splice.spliceStart)).toBe(
applySplice(oldBody, splice).slice(0, splice.spliceStart),
);
const reconstructed = applySplice(oldBody, splice);
expect(reconstructed.slice(splice.spliceStart + splice.newSlice.length)).toBe(
oldBody.slice(splice.spliceEnd),
);
});
test('result of applying splice equals the canonical newBody serialization', () => {
const oldBody = '# Heading\n\nFirst.\n\nSecond.\n';
const newPm = pmFromMd('# Heading\n\nFirst CHANGED.\n\nSecond.\n');
const splice = computeMapDrivenBodySplice(oldBody, newPm, mdManager);
expect(splice).not.toBeNull();
if (!splice) return;
const reconstructed = applySplice(oldBody, splice);
const canonicalNew = mdManager.serialize(newPm);
const reconstructedMdast = mdManager.parseToMdast(reconstructed);
const canonicalMdast = mdManager.parseToMdast(canonicalNew);
expect(reconstructedMdast.children.length).toBe(canonicalMdast.children.length);
});
});
describe('source-form preservation through structural equality', () => {
test('an untouched block whose canonical form would canonicalize bytes is excluded from splice', () => {
const oldBody = '*italic one*\n\nuntouched two\n';
const newPmJson = pmFromMd('*italic one* EDIT\n\nuntouched two\n');
const splice = computeMapDrivenBodySplice(oldBody, newPmJson, mdManager);
expect(splice).not.toBeNull();
if (!splice) return;
const result = applySplice(oldBody, splice);
expect(result).toContain('untouched two');
const oldUntouched = oldBody.slice(oldBody.indexOf('untouched two'));
const newUntouched = result.slice(result.indexOf('untouched two'));
expect(newUntouched).toBe(oldUntouched);
});
test('block matching the structural shape but canonicalized in newBody is NOT spliced', () => {
const oldBody = '*italic*\n\nplain\n';
const newPmJson = pmFromMd('*italic*\n\nplain CHANGED\n');
const splice = computeMapDrivenBodySplice(oldBody, newPmJson, mdManager);
expect(splice).not.toBeNull();
if (!splice) return;
const result = applySplice(oldBody, splice);
expect(result.startsWith('*italic*\n\n')).toBe(true);
});
});
describe('insertions and deletions at boundaries', () => {
test('append a new paragraph at end', () => {
const oldBody = 'First.\n';
const newPmJson = pmFromMd('First.\n\nSecond.\n');
const splice = computeMapDrivenBodySplice(oldBody, newPmJson, mdManager);
expect(splice).not.toBeNull();
if (!splice) return;
const result = applySplice(oldBody, splice);
expect(result).toContain('First.');
expect(result).toContain('Second.');
expect(result.indexOf('First.')).toBe(0);
});
test('prepend a new paragraph at start', () => {
const oldBody = 'Second.\n';
const newPmJson = pmFromMd('First.\n\nSecond.\n');
const splice = computeMapDrivenBodySplice(oldBody, newPmJson, mdManager);
expect(splice).not.toBeNull();
if (!splice) return;
const result = applySplice(oldBody, splice);
expect(result).toContain('First.');
expect(result).toContain('Second.');
expect(result.indexOf('First.')).toBeLessThan(result.indexOf('Second.'));
});
test('insert a paragraph in the middle preserves surrounding blocks byte-identically', () => {
const oldBody = '*Pre*\n\nPost.\n';
const newPmJson = pmFromMd('*Pre*\n\nMiddle.\n\nPost.\n');
const splice = computeMapDrivenBodySplice(oldBody, newPmJson, mdManager);
expect(splice).not.toBeNull();
if (!splice) return;
const result = applySplice(oldBody, splice);
expect(result.startsWith('*Pre*')).toBe(true);
expect(result).toContain('Middle.');
expect(result.endsWith('Post.\n')).toBe(true);
});
test('delete a middle block', () => {
const oldBody = 'A.\n\nB.\n\nC.\n';
const newPmJson = pmFromMd('A.\n\nC.\n');
const splice = computeMapDrivenBodySplice(oldBody, newPmJson, mdManager);
expect(splice).not.toBeNull();
if (!splice) return;
const result = applySplice(oldBody, splice);
expect(result).toContain('A.');
expect(result).toContain('C.');
expect(result).not.toContain('B.');
});
});
describe('synthetic / empty inputs', () => {
test('empty oldBody + new content produces splice that yields the new content', () => {
const oldBody = '';
const newPmJson = pmFromMd('A new paragraph.\n');
const splice = computeMapDrivenBodySplice(oldBody, newPmJson, mdManager);
expect(splice).not.toBeNull();
if (!splice) return;
const result = applySplice(oldBody, splice);
expect(result).toContain('A new paragraph.');
});
test('no-change input produces no-op splice', () => {
const oldBody = 'A.\n\nB.\n';
const newPmJson = pmFromMd(oldBody);
const splice = computeMapDrivenBodySplice(oldBody, newPmJson, mdManager);
expect(splice).not.toBeNull();
if (!splice) return;
const result = applySplice(oldBody, splice);
const oldChildren = mdManager.parseToMdast(oldBody).children;
const resultChildren = mdManager.parseToMdast(result).children;
expect(resultChildren.length).toBe(oldChildren.length);
});
});
describe('contiguous multi-block edits', () => {
test('editing two adjacent blocks unions their splice ranges', () => {
const oldBody = 'first.\n\nsecond.\n\nthird.\n';
const newPmJson = pmFromMd('first EDITED.\n\nsecond EDITED.\n\nthird.\n');
const splice = computeMapDrivenBodySplice(oldBody, newPmJson, mdManager);
expect(splice).not.toBeNull();
if (!splice) return;
const result = applySplice(oldBody, splice);
expect(result.endsWith('third.\n')).toBe(true);
const thirdStartOld = oldBody.indexOf('third.');
expect(splice.spliceEnd).toBeLessThanOrEqual(thirdStartOld);
});
test('non-contiguous multi-block edits collapse into one over-wide splice (documented AC2 degradation)', () => {
const oldBody = 'first.\n\nmiddle.\n\nthird.\n';
const newPmJson = pmFromMd('first EDITED.\n\nmiddle.\n\nthird EDITED.\n');
const splice = computeMapDrivenBodySplice(oldBody, newPmJson, mdManager);
expect(splice).not.toBeNull();
if (!splice) return;
const middleStart = oldBody.indexOf('middle.');
expect(splice.spliceStart).toBeLessThanOrEqual(middleStart);
expect(splice.spliceEnd).toBeGreaterThanOrEqual(middleStart + 'middle.'.length);
const result = applySplice(oldBody, splice);
expect(result).toContain('first EDITED.');
expect(result).toContain('middle.');
expect(result).toContain('third EDITED.');
});
});
describe('robustness to parse failure', () => {
test('returns null when serialize throws on schema-rejected JSON', () => {
const oldBody = 'A.\n';
const malformed = { type: 'not-a-real-node-type' } as JSONContent;
const splice = computeMapDrivenBodySplice(oldBody, malformed, mdManager);
expect(splice).toBeNull();
});
});
});
describe('CRLF bodies keep their line endings through the splice (PRD-9139)', () => {
const crlf = (lf: string): string => lf.replaceAll('\n', '\r\n');
test('a uniformly CRLF body stays uniformly CRLF', () => {
const oldBody = crlf('# Heading\n\nFirst paragraph.\n\n## Second\n\n+ un\n+ deux\n');
const newPm = pmFromMd('# Heading\n\nFirst paragraph.\n\n## XSecond\n\n+ un\n+ deux\n');
const splice = computeMapDrivenBodySplice(oldBody, newPm, mdManager);
expect(splice).not.toBeNull();
if (!splice) return;
expect(applySplice(oldBody, splice)).toBe(
crlf('# Heading\n\nFirst paragraph.\n\n## XSecond\n\n+ un\n+ deux\n'),
);
expect(oldBody.slice(0, splice.spliceStart)).not.toContain('Second');
});
test('a mixed body keeps every byte outside the splice and spells the slice in its majority ending', () => {
const oldBody = 'Alpha.\r\n\r\nBeta.\r\n\r\nGamma.\n';
const splice = computeMapDrivenBodySplice(
oldBody,
pmFromMd('Alpha.\n\nBeta edited.\n\nGamma.\n'),
mdManager,
);
expect(splice).not.toBeNull();
if (!splice) return;
expect(applySplice(oldBody, splice)).toBe('Alpha.\r\n\r\nBeta edited.\r\n\r\nGamma.\n');
});
test('consecutive CRLF keystrokes still parse each body once', () => {
const { manager: counted, parses } = createCountingManager();
const memo = createEditorMdastMemo();
const bodyA = crlf('# H\n\nalpha\n');
const first = computeMapDrivenBodySplice(bodyA, counted.parse('# H\n\nalphaX\n'), counted, {
memo,
});
expect(first).not.toBeNull();
if (!first) return;
const bodyB = applySplice(bodyA, first);
expect(bodyB).toBe(crlf('# H\n\nalphaX\n'));
const afterFirst = parses();
const second = computeMapDrivenBodySplice(bodyB, counted.parse('# H\n\nalphaXY\n'), counted, {
memo,
});
expect(parses() - afterFirst).toBe(1);
expect(second && applySplice(bodyB, second)).toBe(crlf('# H\n\nalphaXY\n'));
});
});
describe('editor-mdast parse memo (PRD-8273)', () => {
test('a repeated body is parsed once, not once per call', () => {
const { manager: counted, parses } = createCountingManager();
const memo = createEditorMdastMemo();
const bodyA = '# H\n\nalpha\n';
const first = computeMapDrivenBodySplice(bodyA, counted.parse('# H\n\nalphaX\n'), counted, {
memo,
});
expect(first).not.toBeNull();
if (!first) return;
const bodyB = applySplice(bodyA, first);
const afterFirst = parses();
computeMapDrivenBodySplice(bodyB, counted.parse('# H\n\nalphaXY\n'), counted, { memo });
expect(parses() - afterFirst).toBe(1);
});
test('a body changed out from under the memo misses rather than serving a stale parse', () => {
const { manager: counted, parses } = createCountingManager();
const memo = createEditorMdastMemo();
const primed = '# H\n\nalpha\n';
computeMapDrivenBodySplice(primed, counted.parse('# H\n\nalphaX\n'), counted, { memo });
const afterPrime = parses();
const external = '# DIFFERENT\n\nomega\n\ntail\n';
const splice = computeMapDrivenBodySplice(
external,
counted.parse('# DIFFERENT\n\nomega EDITED\n\ntail\n'),
counted,
{ memo },
);
expect(splice).not.toBeNull();
if (!splice) return;
expect(parses() - afterPrime).toBe(2);
const result = applySplice(external, splice);
expect(result).toContain('omega EDITED');
expect(result).toContain('# DIFFERENT');
expect(result.endsWith('tail\n')).toBe(true);
});
test('a splice built from a memo hit equals one built from a fresh parse', () => {
const { manager: counted, parses } = createCountingManager();
const memo = createEditorMdastMemo();
const bodyA = '# H\n\none\n\ntwo\n\nthree\n';
const first = computeMapDrivenBodySplice(
bodyA,
counted.parse('# H\n\none EDITED\n\ntwo\n\nthree\n'),
counted,
{ memo },
);
expect(first).not.toBeNull();
if (!first) return;
const bodyB = applySplice(bodyA, first);
const newPm = counted.parse('# H\n\none EDITED\n\ntwo CHANGED\n\nthree\n');
const before = parses();
const fromHit = computeMapDrivenBodySplice(bodyB, newPm, counted, { memo });
expect(parses() - before).toBe(1);
const fromFreshParse = computeMapDrivenBodySplice(bodyB, newPm, counted);
expect(fromHit).toEqual(fromFreshParse);
expect(fromHit).not.toBeNull();
});
test('preserved bytes the serializer would not emit still hit the next drain', () => {
const { manager: counted, parses } = createCountingManager();
const memo = createEditorMdastMemo();
const bodyA = 'one \n\ntwo\n\nthree\n';
const first = computeMapDrivenBodySplice(
bodyA,
counted.parse('one \n\ntwo A\n\nthree\n'),
counted,
{ memo },
);
expect(first).not.toBeNull();
if (!first) return;
const bodyB = applySplice(bodyA, first);
expect(bodyB).not.toBe(counted.serialize(counted.parse(bodyB)));
expect(memo.entry?.body).toBe(bodyB);
const newPm = counted.parse('one \n\ntwo B\n\nthree\n');
const before = parses();
const fromHit = computeMapDrivenBodySplice(bodyB, newPm, counted, { memo });
expect(parses() - before).toBe(1);
expect(fromHit).toEqual(computeMapDrivenBodySplice(bodyB, newPm, counted));
});
test('a same-length body with different content misses — the key is bytes, not length', () => {
const { manager: counted, parses } = createCountingManager();
const memo = createEditorMdastMemo();
const primed = counted.serialize(counted.parse('one\n\ntwo\n\nthree\n'));
const actual = 'one two\n\nthreeX\n';
expect(actual.length).toBe(primed.length);
expect(actual).not.toBe(primed);
computeMapDrivenBodySplice('zzz\n', counted.parse(primed), counted, { memo });
const newPm = counted.parse('one two\n\nthreeY\n');
const before = parses();
const withMemo = computeMapDrivenBodySplice(actual, newPm, counted, { memo });
expect(parses() - before).toBe(2);
const withoutMemo = computeMapDrivenBodySplice(actual, newPm, counted);
expect(withMemo).toEqual(withoutMemo);
expect(withMemo).not.toBeNull();
});
});
describe('caller-supplied serialization', () => {
test('a body serialized from the same PM JSON is reused instead of re-serialized', () => {
const { manager: counted, serializes } = createCountingManager();
const memo = createEditorMdastMemo();
const oldBody = '# H\n\none\n\ntwo\n';
const newPm = counted.parse('# H\n\none EDITED\n\ntwo\n');
const body = counted.serialize(newPm);
const before = serializes();
const reused = computeMapDrivenBodySplice(oldBody, newPm, counted, {
memo,
serializedNewPm: { json: newPm, body, opts: undefined },
});
expect(serializes() - before).toBe(0);
expect(reused).toEqual(computeMapDrivenBodySplice(oldBody, newPm, counted));
});
test('a body carried from different PM JSON is ignored and the splice serializes itself', () => {
const { manager: counted, serializes } = createCountingManager();
const oldBody = '# H\n\none\n\ntwo\n';
const newPm = counted.parse('# H\n\none EDITED\n\ntwo\n');
const stale = counted.parse('# H\n\nSTALE\n\ntwo\n');
const staleBody = counted.serialize(stale);
const before = serializes();
const splice = computeMapDrivenBodySplice(oldBody, newPm, counted, {
serializedNewPm: { json: stale, body: staleBody, opts: undefined },
});
const selfSerializes = serializes() - before;
expect(selfSerializes).toBe(1);
expect(splice).toEqual(computeMapDrivenBodySplice(oldBody, newPm, counted));
});
});
describe('spliced-body memo fidelity', () => {
const DIRTY_PREFIX = 'preserved \n\n';
const NARROWABLE_SHAPES = new Set(['list', 'blockquote', 'loose-list']);
const CORPUS: Array<[string, string]> = [
['paragraphs', 'one\n\ntwo\n\nthree\n\nfour\n'],
['headings', '# H\n\npara\n\n## H2\n\npara two\n\ntail\n'],
['list', '# H\n\n- one\n- two\n- three\n\npara\n\ntail\n'],
['blockquote', '# H\n\n> one\n>\n> two\n\npara\n\ntail\n'],
['table', '# H\n\n| a | b |\n|---|---|\n| 1 | 2 |\n\npara\n\ntail\n'],
['code-fence', '# H\n\n```js\nconst a = 1;\n```\n\npara\n\ntail\n'],
['setext', 'Title\n=====\n\npara\n\ntail\n'],
['definitions', '# H\n\n[a]: http://example.com\n\nsee [a]\n\npara two\n\ntail\n'],
['footnote', '# H\n\ntext[^1]\n\n[^1]: note\n\npara two\n\ntail\n'],
['dirty-bytes', 'one \n\ntwo\n\nthree\n\nfour\n'],
['blank-runs', 'one\n\n\n\ntwo\n\nthree\n\nfour\n'],
['thematic-break', 'one\n\n---\n\ntwo\n\nthree\n'],
['loose-list', '# H\n\n- one\n\n- two\n\npara\n\ntail\n'],
[
'many-blocks',
`${Array.from({ length: 60 }, (_, i) => `Paragraph ${i} body text.`).join('\n\n')}\n`,
],
];
const EDITS: Array<[string, (text: string) => string]> = [
['append-char', (text) => `${text}Z`],
['prepend-char', (text) => `Z${text}`],
['emphasis-marker', (text) => `${text} *em*`],
['dash-run', (text) => `${text} ---`],
];
function editFirstLeaf(
json: JSONContent,
blockIndex: number,
edit: (text: string) => string,
): JSONContent | null {
const clone = structuredClone(json) as JSONContent;
const block = clone.content?.[blockIndex];
if (!block) return null;
const stack: JSONContent[] = [block];
while (stack.length > 0) {
const node = stack.pop();
if (!node) continue;
if (typeof node.text === 'string') {
node.text = edit(node.text);
return clone;
}
for (const child of node.content ?? []) stack.push(child);
}
return null;
}
function appendToFirstLeaf(json: JSONContent, blockIndex: number): JSONContent | null {
return editFirstLeaf(json, blockIndex, (text) => `${text}Z`);
}
for (const [label, canonicalDoc] of CORPUS) {
for (const [form, doc] of [
['canonical', canonicalDoc],
['non-canonical', `${DIRTY_PREFIX}${canonicalDoc}`],
] as const) {
test(`${label} (${form}): every composed entry equals a fresh parse of the spliced body`, () => {
const pm = mdManager.parse(doc);
const blockCount = pm.content?.length ?? 0;
expect(blockCount).toBeGreaterThan(0);
const firstEditable = form === 'canonical' ? 0 : 1;
let composed = 0;
let attempted = 0;
const skips: MapDrivenSpliceMemoSkipReason[] = [];
for (let index = firstEditable; index < blockCount; index++) {
for (const [, edit] of EDITS) {
const edited = editFirstLeaf(pm, index, edit);
if (!edited) continue;
attempted++;
const memo = createEditorMdastMemo();
const newBody = mdManager.serialize(edited);
const splice = computeMapDrivenBodySplice(doc, edited, mdManager, {
memo,
onMemoSkip: (reason) => skips.push(reason),
});
expect(splice).not.toBeNull();
if (!splice) continue;
const applied = applySplice(doc, splice);
expect(memo.entry).not.toBeNull();
if (applied === newBody) {
expect(memo.entry?.body).toBe(newBody);
continue;
}
if (memo.entry?.body !== applied) continue;
composed++;
expect(JSON.stringify(memo.entry.children)).toBe(
JSON.stringify(mdManager.parseToEditorMdast(applied).children),
);
}
}
const narrowedSkips = skips.filter((reason) => reason === 'narrowed').length;
const alreadyCurrentSkips = skips.filter(
(reason) => reason === 'entry-already-current',
).length;
expect(attempted).toBeGreaterThan(0);
expect(skips.filter((r) => r !== 'narrowed' && r !== 'entry-already-current')).toEqual([]);
expect(composed).toBe(attempted - narrowedSkips - alreadyCurrentSkips);
if (form === 'canonical') {
expect(alreadyCurrentSkips).toBeGreaterThan(0);
} else {
expect(composed).toBeGreaterThan(0);
}
if (NARROWABLE_SHAPES.has(label)) {
expect(narrowedSkips).toBeGreaterThan(0);
} else {
expect(narrowedSkips).toBe(0);
}
});
}
}
test('a container-narrowed splice leaves the constructed entry unwritten', () => {
const doc = 'para \n\n- one\n- two\n- three\n\ntail\n';
const pm = mdManager.parse(doc);
const edited = appendToFirstLeaf(pm, 1);
expect(edited).not.toBeNull();
if (!edited) return;
const memo = createEditorMdastMemo();
const splice = computeMapDrivenBodySplice(doc, edited, mdManager, { memo });
expect(splice).not.toBeNull();
if (!splice) return;
const applied = applySplice(doc, splice);
const newBody = mdManager.serialize(edited);
expect(applied).not.toBe(newBody);
expect(applied.startsWith('para ')).toBe(true);
expect(splice.spliceStart).toBeGreaterThan(doc.indexOf('- one'));
expect(memo.entry?.body).toBe(newBody);
});
});
describe('spliced-body memo failure isolation', () => {
test('a throwing memo write costs the optimization, not the splice', () => {
const oldBody = 'preserved \n\none\n\ntwo\n\nthree\n';
const newPm = mdManager.parse('preserved \n\none EDITED\n\ntwo\n\nthree\n');
const reasons: MapDrivenSpliceMemoSkipReason[] = [];
const errors: unknown[] = [];
const composeFailure = new Error('synthetic composition regression');
let stored: EditorMdastMemo['entry'] = null;
let writes = 0;
const hostileMemo = {
get entry() {
return stored;
},
set entry(value: EditorMdastMemo['entry']) {
writes++;
if (writes > 2) throw composeFailure;
stored = value;
},
} as EditorMdastMemo;
const splice = computeMapDrivenBodySplice(oldBody, newPm, mdManager, {
memo: hostileMemo,
onMemoSkip: (reason, err) => {
reasons.push(reason);
errors.push(err);
},
});
expect(splice).not.toBeNull();
expect(splice).toEqual(computeMapDrivenBodySplice(oldBody, newPm, mdManager));
expect(writes).toBe(3);
expect(reasons).toEqual(['compose-failed']);
expect(errors).toEqual([composeFailure]);
});
});