utils.spec.ts

/*---------------------------------------------------------------------------------------------
 *  Copyright (c) Microsoft Corporation. All rights reserved.
 *  Licensed under the MIT License. See License.txt in the project root for license information.
 *--------------------------------------------------------------------------------------------*/

import * as assert from 'assert';
import { expect, suite, test } from 'vitest';
import { EditSurvivalTracker, applyEditsToRanges, compute4GramTextSimilarity } from '../../../platform/editSurvivalTracking/common/editSurvivalTracker';
import { ISerializedStringEdit, StringEdit, StringReplacement } from '../../../util/vs/editor/common/core/edits/stringEdit';
import { OffsetRange } from '../../../util/vs/editor/common/core/ranges/offsetRange';

suite('OffsetEdit.join', () => {
	for (let seed = 0; seed < 50; seed++) {
		test('test' + seed, () => {
			runTest(seed);
		});
	}
});

function runTest(seed: number) {
	const rng = new MersenneTwister(seed);

	const s0 = 'abcde\nfghij\nklmno\npqrst\n';

	const edits1 = getRandomEdits(s0, rng.nextIntRange(1, 4), rng);
	const s1 = edits1.apply(s0);

	const edits2 = getRandomEdits(s1, rng.nextIntRange(1, 4), rng);
	const s2 = edits2.apply(s1);

	const combinedEdits = edits1.compose(edits2);
	const s2C = combinedEdits.apply(s0);

	assert.strictEqual(s2C, s2);
}

function getRandomEdits(str: string, count: number, rng: MersenneTwister): StringEdit {
	const edits: StringReplacement[] = [];
	let i = 0;
	for (let j = 0; j < count; j++) {
		if (i >= str.length) {
			break;
		}
		edits.push(getRandomEdit(str, i, rng));
		i = edits[j].replaceRange.endExclusive + 1;
	}
	return new StringEdit(edits);
}

function getRandomEdit(str: string, rangeOffsetStart: number, rng: MersenneTwister): StringReplacement {
	const offsetStart = rng.nextIntRange(rangeOffsetStart, str.length);
	const offsetEnd = rng.nextIntRange(offsetStart, str.length);

	const textStart = rng.nextIntRange(0, str.length);
	const textLen = rng.nextIntRange(0, Math.min(7, str.length - textStart));

	return new StringReplacement(
		new OffsetRange(offsetStart, offsetEnd),
		str.substring(textStart, textStart + textLen)
	);
}

// Generated by copilot
class MersenneTwister {
	private readonly mt = new Array(624);
	private index = 0;

	constructor(seed: number) {
		this.mt[0] = seed >>> 0;
		for (let i = 1; i < 624; i++) {
			const s = this.mt[i - 1] ^ (this.mt[i - 1] >>> 30);
			this.mt[i] = (((((s & 0xffff0000) >>> 16) * 0x6c078965) << 16) + (s & 0x0000ffff) * 0x6c078965 + i) >>> 0;
		}
	}

	public nextInt() {
		if (this.index === 0) {
			this.generateNumbers();
		}

		let y = this.mt[this.index];
		y = y ^ (y >>> 11);
		y = y ^ ((y << 7) & 0x9d2c5680);
		y = y ^ ((y << 15) & 0xefc60000);
		y = y ^ (y >>> 18);

		this.index = (this.index + 1) % 624;

		return y >>> 0;
	}

	public nextIntRange(start: number, endExclusive: number) {
		const range = endExclusive - start;
		return Math.floor(this.nextInt() / (0x100000000 / range)) + start;
	}

	private generateNumbers() {
		for (let i = 0; i < 624; i++) {
			const y = (this.mt[i] & 0x80000000) + (this.mt[(i + 1) % 624] & 0x7fffffff);
			this.mt[i] = this.mt[(i + 397) % 624] ^ (y >>> 1);
			if ((y % 2) !== 0) {
				this.mt[i] = this.mt[i] ^ 0x9908b0df;
			}
		}
	}
}

const loremIpsum = `Lorem ipsum dolor sit amet, consectetur adipiscing elit. Sed non risus. Suspendisse lectus tortor, dignissim sit amet, adipiscing nec, ultricies sed, dolor. Cras elementum ultrices diam. Maecenas ligula massa, varius a, semper congue, euismod non, mi.`;

function getRandomString(rng: MersenneTwister): string {
	let result = '';
	for (let i = 0; i < 4; i++) {
		const start = rng.nextIntRange(0, loremIpsum.length);
		const end = rng.nextIntRange(start, loremIpsum.length);
		result += loremIpsum.substring(start, end);
	}
	return result;
}

suite('applyEditsToRanges', () => {
	test('edit after ranges', () => {
		const ranges = [
			new OffsetRange(10, 20),
			new OffsetRange(30, 40),
			new OffsetRange(50, 60),
		];

		const edits = new StringEdit([
			new StringReplacement(new OffsetRange(100, 110), 'abc'),
		]);

		const newRanges = applyEditsToRanges(ranges, edits);
		assert.deepStrictEqual(newRanges.map(r => r.toString()), [
			'[10, 20)',
			'[30, 40)',
			'[50, 60)',
		]);
	});

	test('edit before ranges', () => {
		const ranges = [
			new OffsetRange(10, 20),
			new OffsetRange(30, 40),
			new OffsetRange(50, 60),
		];

		const edits = new StringEdit([
			new StringReplacement(new OffsetRange(5, 6), 'abc'),
		]);

		const newRanges = applyEditsToRanges(ranges, edits);
		assert.deepStrictEqual(newRanges.map(r => r.toString()), [
			'[12, 22)',
			'[32, 42)',
			'[52, 62)',
		]);
	});

	test('edit in range', () => {
		const ranges = [
			new OffsetRange(10, 20),
			new OffsetRange(30, 40),
			new OffsetRange(50, 60),
		];

		const edits = new StringEdit([
			new StringReplacement(new OffsetRange(11, 19), 'x'),
		]);

		const newRanges = applyEditsToRanges(ranges, edits);
		assert.deepStrictEqual(newRanges.map(r => r.toString()), [
			'[10, 13)',
			'[23, 33)',
			'[43, 53)',
		]);
	});

	test('edit in multiple ranges', () => {
		const ranges = [
			new OffsetRange(10, 20),
			new OffsetRange(30, 40),
			new OffsetRange(50, 60),
		];

		const edits = new StringEdit([
			new StringReplacement(new OffsetRange(15, 55), 'x'),
		]);

		const newRanges = applyEditsToRanges(ranges, edits);
		assert.deepStrictEqual(newRanges.map(r => r.toString()), [
			'[10, 16)',
			'[16, 16)',
			'[16, 21)',
		]);
	});

	test('edit in multiple ranges 2', () => {
		const ranges = [
			new OffsetRange(10, 20),
			new OffsetRange(30, 40),
			new OffsetRange(50, 60),
		];

		const edits = new StringEdit([
			new StringReplacement(new OffsetRange(15, 55), 'x'),
			new StringReplacement(new OffsetRange(58, 59), 'yy'),
		]);

		const newRanges = applyEditsToRanges(ranges, edits);
		assert.deepStrictEqual(newRanges.map(r => r.toString()), [
			'[10, 16)',
			'[16, 16)',
			'[16, 22)',
		]);
	});

	test('touching edit', () => {
		const ranges = [
			new OffsetRange(10, 20),
			new OffsetRange(30, 40),
			new OffsetRange(50, 60),
		];

		const edits = new StringEdit([
			new StringReplacement(new OffsetRange(40, 40), 'x'),
			new StringReplacement(new OffsetRange(50, 50), 'x'),
		]);

		const newRanges = applyEditsToRanges(ranges, edits);
		assert.deepStrictEqual(newRanges.map(r => r.toString()), [
			'[10, 20)',
			'[30, 41)',
			'[51, 62)'
		]);
	});
});


function projectableValue_editable<T>(arg: T): T {
	return arg;
}


suite('compute4GramTextSimilarity', () => {
	for (let seed = 0; seed < 50; seed++) {
		test('test' + seed, () => {
			runTest(seed);
		});
	}

	function runTest(seed: number) {
		const rng = new MersenneTwister(seed);

		const s1 = getRandomString(rng);
		const s2 = getRandomString(rng);

		const similarity = compute4GramTextSimilarity(s1, s2);

		assert.ok(similarity >= 0 && similarity <= 1, `similarity should be between 0 and 1, but was ${similarity}`);
	}
});

suite('EditSurvivalTracker', () => {
	function renameProps<T extends object>(obj: T, map: { [K in keyof T]?: string }): any {
		const result: any = {};
		for (const key of Object.keys(obj) as (keyof T)[]) {
			const newKey = map[key] || key;
			result[newKey] = obj[key];
		}
		return result;
	}

	function getScore(input: { text: string; edits: ISerializedStringEdit[] }): unknown {
		const originalText = input.text;
		const t = new EditSurvivalTracker(originalText, StringEdit.fromJson(input.edits[0]));
		t.handleEdits(StringEdit.fromJson(input.edits[1]));
		const score = t.computeTrackedEditsSurvivalScore();
		return renameProps(score, {
			textBeforeAiEdits: 'text1BeforeAiEdits',
			textAfterAiEdits: 'text2AfterAiEdits',
			textAfterUserEdits: 'text3AfterUserEdits',
		});
	}

	test('simple', async () => {
		expect(
			getScore(projectableValue_editable({
				'text': 'console.log(123456);',
				'edits': [
					[
						{
							'pos': 12,
							'len': 6,
							'txt': `'hello'`
						}
					],
					[
						{
							'pos': 12,
							'len': 7,
							'txt': `'Hello'`
						}
					]
				],
				'x-editor': 'edit-editor'
			})),
		).toMatchInlineSnapshot(`
			{
			  "fourGram": 0.5,
			  "noRevert": 1,
			  "text1BeforeAiEdits": [
			    "123456",
			  ],
			  "text2AfterAiEdits": [
			    "'hello'",
			  ],
			  "text3AfterUserEdits": [
			    "'Hello'",
			  ],
			}
		`);
	});

	test('multi edit', async () => {
		expect(
			getScore(projectableValue_editable({
				'text': 'console.log(123456);',
				'edits': [
					[
						{
							'pos': 0,
							'len': 0,
							'txt': '// comment\\n'
						},
						{
							'pos': 12,
							'len': 6,
							'txt': `'hello'`
						}
					],
					[
						{
							'pos': 0,
							'len': 2,
							'txt': '/*'
						},
						{
							'pos': 10,
							'len': 2,
							'txt': ' */'
						},
						{
							'pos': 25,
							'len': 7,
							'txt': 'Hello'
						}
					]
				],
				'x-editor': 'edit-editor'
			})),
		).toMatchInlineSnapshot(`
			{
			  "fourGram": 0.4376731301939058,
			  "noRevert": 1,
			  "text1BeforeAiEdits": [
			    "",
			    "123456",
			  ],
			  "text2AfterAiEdits": [
			    "// comment\\n",
			    "'hello'",
			  ],
			  "text3AfterUserEdits": [
			    "/* comment */",
			    "'Hello",
			  ],
			}
		`);
	});

	test('realistic example', async () => {
		expect(
			getScore(projectableValue_editable({
				'text': `import {\r\n\tTextDocument,\r\n\tWebviewPanel,\r\n\tCancellationToken,\r\n\tworkspace,\r\n\tWorkspaceEdit,\r\n\tRange,\r\n\tCustomTextEditorProvider,\r\n} from "vscode";\r\nimport { WebviewInitializer } from "./WebviewInitializer";\r\n\r\ninterface EditableDocument {\r\n\t"x-editable"?: {\r\n\t\tkind: string;\r\n\t\tdefaultUrl: string;\r\n\t};\r\n}\r\n\r\nexport class TextEditorProvider implements CustomTextEditorProvider {\r\n\tconstructor(private readonly webviewInitializer: WebviewInitializer) {}\r\n\r\n\tpublic async resolveCustomTextEditor(\r\n\t\tdocument: TextDocument,\r\n\t\twebviewPanel: WebviewPanel,\r\n\t\ttoken: CancellationToken\r\n\t): Promise<void> {\r\n\t\tlet isThisEditorSaving = false;\r\n\r\n\t\tconst text = document.getText();\r\n\t\tconst doc = JSON.parse(text) as EditableDocument;\r\n\t\tconst args = doc["x-editable"];\r\n\r\n\r\n\t\tconst bridge = this.webviewInitializer.setupWebview(\r\n\t\t\t{ editorUrl: args.defaultUrl },\r\n\t\t\twebviewPanel.webview\r\n\t\t);\r\n\r\n\t\tconst setContentFromDocument = () => {\r\n\t\t\tconst newText = document.getText();\r\n\t\t\tconst content = JSON.parse(newText);\r\n\t\t\tbridge.setContent(content);\r\n\t\t};\r\n\r\n\t\tworkspace.onDidChangeTextDocument(async (evt) => {\r\n\t\t\tif (evt.document !== document) {\r\n\t\t\t\treturn;\r\n\t\t\t}\r\n\t\t\tif (isThisEditorSaving) {\r\n\t\t\t\t// We don't want to integrate our own changes\r\n\t\t\t\treturn;\r\n\t\t\t}\r\n\t\t\tif (evt.contentChanges.length === 0) {\r\n\t\t\t\t// Sometimes VS Code reports a document change without a change.\r\n\t\t\t\treturn;\r\n\t\t\t}\r\n\r\n\t\t\tsetContentFromDocument();\r\n\t\t});\r\n\r\n\t\tbridge.onChange.sub(async ({ newContent }) => {\r\n\t\t\tconst workspaceEdit = new WorkspaceEdit();\r\n\t\t\tconst data = newContent as EditableDocument;\r\n\t\t\tif (!data['x-editable']) {\r\n\t\t\t\tdata['x-editable'] = args;\r\n\t\t\t}\r\n\t\t\tconst output = JSON.stringify(newContent, undefined, 4);\r\n\t\t\tworkspaceEdit.replace(\r\n\t\t\t\tdocument.uri,\r\n\t\t\t\tnew Range(0, 0, document.lineCount, 0),\r\n\t\t\t\toutput\r\n\t\t\t);\r\n\r\n\t\t\tisThisEditorSaving = true;\r\n\t\t\ttry {\r\n\t\t\t\tawait workspace.applyEdit(workspaceEdit);\r\n\t\t\t} finally {\r\n\t\t\t\tisThisEditorSaving = false;\r\n\t\t\t}\r\n\t\t});\r\n\r\n\t\tbridge.onInit.sub(() => {\r\n\t\t\tsetContentFromDocument();\r\n\t\t});\r\n\t}\r\n}\r\n`,
				'edits': [
					[
						{
							'pos': 762,
							'len': 2,
							'txt': '\r\n\r\n\t\tif (!args) {\r\n\t\t\tthrow new Error("invalid json document!");\r\n\t\t}'
						}
					],
					[
						{
							'pos': 801,
							'len': 24,
							'txt': '""'
						}
					]
				],
				'x-editor': 'edit-editor'
			}))).toMatchInlineSnapshot(
				`
				{
				  "fourGram": 0.75,
				  "noRevert": 1,
				  "text1BeforeAiEdits": [
				    "
				",
				  ],
				  "text2AfterAiEdits": [
				    "

						if (!args) {
							throw new Error("invalid json document!");
						}",
				  ],
				  "text3AfterUserEdits": [
				    "

						if (!args) {
							throw new Error("");
						}",
				  ],
				}
			`);
	});
});

suite('OffsetEdits', () => {
	suite('removeCommonSuffixPrefix', () => {
		test('simple', () => {
			const str = 'abcde';

			const e = new StringEdit([
				new StringReplacement(new OffsetRange(0, 2), 'ax'),
				new StringReplacement(new OffsetRange(2, 5), 'cye'),
			]);

			const e2 = e.removeCommonSuffixPrefix(str);

			assert.deepStrictEqual(e2.apply(str), e.apply(str));
			assert.deepStrictEqual(e2.toString(), '[[1, 2) -> "x", [3, 4) -> "y"]');
		});

		for (let seed = 0; seed < 50; seed++) {
			test('test' + seed, () => {
				const rng = new MersenneTwister(seed);

				const s0 = loremIpsum;

				const edits = getRandomEdits(s0, rng.nextIntRange(1, 4), rng);
				const edits2 = edits.removeCommonSuffixPrefix(s0);

				assert.deepStrictEqual(edits2.apply(s0), edits.apply(s0));
			});
		}
	});
});