addons/isl/src/__tests__/linelog.test.tsblame
View source
b69ab311/**
b69ab312 * Portions Copyright (c) Meta Platforms, Inc. and affiliates.
b69ab313 *
b69ab314 * This source code is licensed under the MIT license found in the
b69ab315 * LICENSE file in the root directory of this source tree.
b69ab316 */
b69ab317
b69ab318/*
b69ab319
b69ab3110Copyright (c) 2020 Jun Wu
b69ab3111
b69ab3112Permission is hereby granted, free of charge, to any person obtaining a copy
b69ab3113of this software and associated documentation files (the "Software"), to deal
b69ab3114in the Software without restriction, including without limitation the rights
b69ab3115to use, copy, modify, merge, publish, distribute, sublicense, and/or sell
b69ab3116copies of the Software, and to permit persons to whom the Software is
b69ab3117furnished to do so, subject to the following conditions:
b69ab3118
b69ab3119The above copyright notice and this permission notice shall be included in all
b69ab3120copies or substantial portions of the Software.
b69ab3121
b69ab3122THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR
b69ab3123IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY,
b69ab3124FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT. IN NO EVENT SHALL THE
b69ab3125AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER
b69ab3126LIABILITY, WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING FROM,
b69ab3127OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN THE
b69ab3128SOFTWARE.
b69ab3129
b69ab3130*/
b69ab3131
b69ab3132// @lint-ignore-every SPELL
b69ab3133
b69ab3134import type {LineIdx, Rev} from '../linelog';
b69ab3135
b69ab3136import {describe, expect, it} from '@jest/globals';
b69ab3137import * as Immutable from 'immutable';
b69ab3138import {splitLines} from 'shared/diff';
b69ab3139import {LineLog, executeCache} from '../linelog';
b69ab3140
b69ab3141describe('LineLog', () => {
b69ab3142 it('can be empty', () => {
b69ab3143 const log = new LineLog();
b69ab3144 expect(log.maxRev).toBe(0);
b69ab3145 expect(log.checkOut(0)).toBe('');
b69ab3146 });
b69ab3147
b69ab3148 it('supports a single edit', () => {
b69ab3149 let log = new LineLog();
b69ab3150 log = log.recordText('c\nd\ne');
b69ab3151 expect(log.maxRev).toBe(1);
b69ab3152 expect(log.checkOut(1)).toBe('c\nd\ne');
b69ab3153
b69ab3154 expect(log.checkOutLines(1)).toMatchObject([
b69ab3155 {data: 'c\n', rev: 1},
b69ab3156 {data: 'd\n', rev: 1},
b69ab3157 {data: 'e', rev: 1},
b69ab3158 {data: '', rev: 0},
b69ab3159 ]);
b69ab3160 });
b69ab3161
b69ab3162 it('supports modifying rev 0', () => {
b69ab3163 let log = new LineLog();
b69ab3164 log = log.recordText('c\n', 0);
b69ab3165 expect(log.maxRev).toBe(0);
b69ab3166 expect(log.checkOut(0)).toBe('c\n');
b69ab3167 expect(log.checkOutLines(0)[0]).toMatchObject({rev: 0});
b69ab3168 log = log.recordText('c\nd', 1);
b69ab3169 expect(log.checkOutLines(1)[1]).toMatchObject({rev: 1});
b69ab3170 expect(log.checkOut(0)).toBe('c\n');
b69ab3171 expect(log.checkOutLines(0)[0]).toMatchObject({rev: 0});
b69ab3172 });
b69ab3173
b69ab3174 it('supports multiple edits', () => {
b69ab3175 let log = new LineLog();
b69ab3176 log = log.recordText('c\nd\ne\n');
b69ab3177 log = log.recordText('d\ne\nf\n');
b69ab3178 expect(log.maxRev).toBe(2);
b69ab3179 expect(log.checkOut(2)).toBe('d\ne\nf\n');
b69ab3180 expect(log.checkOutLines(2)).toMatchObject([
b69ab3181 {data: 'd\n', rev: 1, deleted: false},
b69ab3182 {data: 'e\n', rev: 1, deleted: false},
b69ab3183 {data: 'f\n', rev: 2, deleted: false},
b69ab3184 {data: '', rev: 0, deleted: false},
b69ab3185 ]);
b69ab3186 });
b69ab3187
b69ab3188 it('supports checkout', () => {
b69ab3189 let log = new LineLog();
b69ab3190 log = log.recordText('c\nd\ne\n');
b69ab3191 log = log.recordText('d\ne\nf\n');
b69ab3192 expect(log.checkOut(1)).toBe('c\nd\ne\n');
b69ab3193 expect(log.checkOutLines(1)[0].deleted).toBe(false);
b69ab3194 expect(log.checkOut(0)).toBe('');
b69ab3195 expect(log.checkOutLines(0)).toMatchObject([{data: ''}]);
b69ab3196 expect(log.checkOut(2)).toBe('d\ne\nf\n');
b69ab3197 expect(log.checkOutLines(2)[2].deleted).toBe(false);
b69ab3198 });
b69ab3199
b69ab31100 it('supports checkout range', () => {
b69ab31101 const log = new LineLog()
b69ab31102 .recordText('c\nd\ne\n') // rev 1
b69ab31103 .recordText('d\ne\nf\n') // rev 2
b69ab31104 .recordText('e\ng\nf\n'); // rev 3
b69ab31105
b69ab31106 expect(log.checkOutLines(2, 1)).toMatchObject([
b69ab31107 {data: 'c\n', rev: 1, deleted: true}, // 'c' not in rev 2
b69ab31108 {data: 'd\n', rev: 1, deleted: false},
b69ab31109 {data: 'e\n', rev: 1, deleted: false},
b69ab31110 {data: 'f\n', rev: 2, deleted: false},
b69ab31111 {data: '', rev: 0, deleted: false}, // END
b69ab31112 ]);
b69ab31113
b69ab31114 expect(log.checkOutLines(3, 0)).toMatchObject([
b69ab31115 {data: 'c\n', rev: 1, deleted: true}, // 'c' not in rev 3
b69ab31116 {data: 'd\n', rev: 1, deleted: true}, // 'd' not in rev 3
b69ab31117 {data: 'e\n', rev: 1, deleted: false}, // 'e' in rev 3
b69ab31118 {data: 'g\n', rev: 3, deleted: false},
b69ab31119 {data: 'f\n', rev: 2, deleted: false},
b69ab31120 {data: '', rev: 0, deleted: false},
b69ab31121 ]);
b69ab31122
b69ab31123 // should not reuse cache
b69ab31124 expect(log.checkOut(3)).toBe('e\ng\nf\n');
b69ab31125
b69ab31126 expect(log.checkOutLines(3, 2)).toMatchObject([
b69ab31127 {data: 'd\n', rev: 1, deleted: true},
b69ab31128 {data: 'e\n', rev: 1, deleted: false},
b69ab31129 {data: 'g\n', rev: 3, deleted: false},
b69ab31130 {data: 'f\n', rev: 2, deleted: false},
b69ab31131 {data: ''},
b69ab31132 ]);
b69ab31133 });
b69ab31134
b69ab31135 it('bumps rev when recording the same content', () => {
b69ab31136 let log = new LineLog();
b69ab31137 log = log.recordText('a\n');
b69ab31138 expect(log.maxRev).toBe(1);
b69ab31139 log = log.recordText('a\n');
b69ab31140 expect(log.maxRev).toBe(2);
b69ab31141 log = log.recordText('a\n');
b69ab31142 expect(log.maxRev).toBe(3);
b69ab31143 });
b69ab31144
b69ab31145 it('avoids checkout/execute calls for common edits', () => {
b69ab31146 const log = new LineLog().recordText('a\nb\nc\nd\ne\n', 1);
b69ab31147
b69ab31148 // Modifies 3 chunks. This does not introduce new cache
b69ab31149 // miss, because:
b69ab31150 // - checkout (calls execute) used by recordText can
b69ab31151 // reuse cache populated by the previous recordText.
b69ab31152 // This contributes a cache hit.
b69ab31153 // - checkout used by editChunk is skipped, because
b69ab31154 // recordText passes in `aLinesCache`. This does not
b69ab31155 // change cache miss or hit.
b69ab31156 const stats = (executeCache.stats = {miss: 0, hit: 0});
b69ab31157 log.recordText('A\nb\nC\nd\nE\n', 3);
b69ab31158 expect(stats).toMatchObject({miss: 0, hit: 1});
b69ab31159 });
b69ab31160
b69ab31161 it('works with immutable.is', () => {
b69ab31162 const log1 = new LineLog().recordText('a').recordText('b');
b69ab31163 const log2 = new LineLog({code: log1.code, maxRev: log1.maxRev});
b69ab31164 const log3 = new LineLog().recordText('a').recordText('b');
b69ab31165
b69ab31166 expect(Object.is(log1, log2)).toBeFalsy();
b69ab31167 expect(Immutable.is(log1, log2)).toBeTruthy();
b69ab31168 expect(Immutable.is(log1, log3)).toBeTruthy();
b69ab31169 });
b69ab31170
b69ab31171 it('provides human readable instructions', () => {
b69ab31172 const log = logFromTextList(['a\n', 'b\n']);
b69ab31173 // The instructions are internal details. For example, an
b69ab31174 // optimization pass might remove unconditional jumps.
b69ab31175 // Shall the output change, just update the test here.
b69ab31176 expect(log.code.describeHumanReadableInstructions()).toEqual([
b69ab31177 '0: J 1',
b69ab31178 '1: JL 1 3',
b69ab31179 '2: J 4',
b69ab31180 '3: END',
b69ab31181 '4: JL 2 6',
b69ab31182 '5: LINE 2 "b"',
b69ab31183 '6: JGE 2 3',
b69ab31184 '7: LINE 1 "a"',
b69ab31185 '8: J 3',
b69ab31186 ]);
b69ab31187 });
b69ab31188
b69ab31189 describe('provides human readable insertion and deletion stacks', () => {
b69ab31190 const show = (texts: string[]) =>
b69ab31191 logFromTextList(texts).code.describeHumanReadableInsDelStacks();
b69ab31192
b69ab31193 it('interleaved insertion and deletion trees', () => {
b69ab31194 // First 3 revs are from https://sapling-scm.com/docs/internals/linelog
b69ab31195 expect(show(['a\nb\nc\n', 'a\nb\n1\n2\nc\n', 'a\n2\nc\n', 'c\n', ''])).toEqual([
b69ab31196 '+----Insert (rev 1) ',
b69ab31197 '| Delete (rev 4) ----+',
b69ab31198 '| Line: a |',
b69ab31199 '| Delete (rev 3) ---+|',
b69ab31200 '| Line: b ||',
b69ab31201 '|+---Insert (rev 2) ||',
b69ab31202 '|| Line: 1 ||',
b69ab31203 '|| ---+|',
b69ab31204 '|| Line: 2 |',
b69ab31205 '|+--- |',
b69ab31206 '| ----+',
b69ab31207 '| Delete (rev 5) ----+',
b69ab31208 '| Line: c |',
b69ab31209 '| ----+',
b69ab31210 '+---- ',
b69ab31211 ]);
b69ab31212 });
b69ab31213
b69ab31214 it('insertions at the beginning and end are not nested', () => {
b69ab31215 expect(show(['b\n', 'a\nb\n', 'a\nb\nc\n'])).toEqual([
b69ab31216 '+---Insert (rev 2) ',
b69ab31217 '| Line: a ',
b69ab31218 '+--- ',
b69ab31219 '+---Insert (rev 1) ',
b69ab31220 '| Line: b ',
b69ab31221 '+--- ',
b69ab31222 '+---Insert (rev 3) ',
b69ab31223 '| Line: c ',
b69ab31224 '+--- ',
b69ab31225 ]);
b69ab31226 });
b69ab31227
b69ab31228 it('insertion between old new revs is not nested', () => {
b69ab31229 expect(show(['a\n', 'a\nc\n', 'a\nb\nc\n'])).toEqual([
b69ab31230 '+---Insert (rev 1) ',
b69ab31231 '| Line: a ',
b69ab31232 '+--- ',
b69ab31233 '+---Insert (rev 3) ',
b69ab31234 '| Line: b ',
b69ab31235 '+--- ',
b69ab31236 '+---Insert (rev 2) ',
b69ab31237 '| Line: c ',
b69ab31238 '+--- ',
b69ab31239 ]);
b69ab31240 });
b69ab31241
b69ab31242 it('insertion between new old revs is not nested', () => {
b69ab31243 expect(show(['c\n', 'a\nc\n', 'a\nb\nc\n'])).toEqual([
b69ab31244 '+---Insert (rev 2) ',
b69ab31245 '| Line: a ',
b69ab31246 '+--- ',
b69ab31247 '+---Insert (rev 3) ',
b69ab31248 '| Line: b ',
b69ab31249 '+--- ',
b69ab31250 '+---Insert (rev 1) ',
b69ab31251 '| Line: c ',
b69ab31252 '+--- ',
b69ab31253 ]);
b69ab31254 });
b69ab31255 });
b69ab31256
b69ab31257 describe('supports editing previous revisions', () => {
b69ab31258 it('edits stack bottom', () => {
b69ab31259 const textList = ['a\n', 'a\nb\n', 'z\na\nb\n'];
b69ab31260 let log = logFromTextList(textList);
b69ab31261
b69ab31262 log = log.recordText('1\n2\n', 1); // replace rev 1 from "a" to "1 2"
b69ab31263 expect(log.checkOut(1)).toBe('1\n2\n');
b69ab31264 expect(log.checkOut(2)).toBe('1\n2\nb\n');
b69ab31265 expect(log.checkOut(3)).toBe('z\n1\n2\nb\n');
b69ab31266
b69ab31267 log = log.recordText('', 1); // replace rev 1 to ""
b69ab31268 expect(log.checkOut(1)).toBe('');
b69ab31269 expect(log.checkOut(2)).toBe('b\n');
b69ab31270 expect(log.checkOut(3)).toBe('z\nb\n');
b69ab31271 });
b69ab31272
b69ab31273 it('edits stack middle', () => {
b69ab31274 const textList = ['c\nd\ne\n', 'b\nc\nd\n', 'a\nb\nc\nz\n'];
b69ab31275 let log = logFromTextList(textList);
b69ab31276
b69ab31277 log = log.recordText('b\nd\n', 2); // remove "c" from "b c d" in rev 2
b69ab31278 expect(log.checkOut(1)).toBe('c\nd\ne\n'); // rev 1 is unchanged, despite "c" comes from rev 1
b69ab31279 expect(log.checkOut(2)).toBe('b\nd\n');
b69ab31280 expect(log.checkOut(3)).toBe('a\nb\nz\n'); // "c" in rev 3 is also removed
b69ab31281
b69ab31282 log = logFromTextList(textList);
b69ab31283 log = log.recordText('b\nc\ny\ny\n', 2); // change "d" to "y y" from rev 2.
b69ab31284 expect(log.checkOut(3)).toBe('a\nb\nc\nz\n'); // rev 3 is unchanged, since "d" was deleted
b69ab31285
b69ab31286 log = logFromTextList(textList);
b69ab31287 log = log.recordText('k\n', 2); // replace rev 2 with "k", this is a tricky case
b69ab31288 expect(log.checkOut(3)).toBe('a\nk\n'); // "a k" is the current implementation, "a k z" might be better
b69ab31289 });
b69ab31290 });
b69ab31291
b69ab31292 it('calculates dependencies using linelog instructions', () => {
b69ab31293 const deps = (textList: string[]): (number | number[])[][] => {
b69ab31294 const insertEOL = (text: string): string =>
b69ab31295 text
b69ab31296 .split('')
b69ab31297 .map(c => `${c}\n`)
b69ab31298 .join('');
b69ab31299 const log = logFromTextList(textList.map(insertEOL));
b69ab31300 return flattenDepMap(log.calculateDepMap());
b69ab31301 };
b69ab31302
b69ab31303 expect(deps([])).toEqual([]);
b69ab31304
b69ab31305 // Insertions.
b69ab31306 expect(deps(['a'])).toEqual([[1, [0]]]);
b69ab31307 expect(deps(['a', 'b'])).toEqual([
b69ab31308 [1, [0]],
b69ab31309 [2, [1]],
b69ab31310 ]);
b69ab31311 expect(deps(['a', 'ab'])).toEqual([
b69ab31312 [1, [0]],
b69ab31313 [2, [0]],
b69ab31314 ]);
b69ab31315 expect(deps(['b', 'ab'])).toEqual([
b69ab31316 [1, [0]],
b69ab31317 [2, [0]],
b69ab31318 ]);
b69ab31319 expect(deps(['ad', 'abd', 'abcd'])).toEqual([
b69ab31320 [1, [0]],
b69ab31321 [2, [1]],
b69ab31322 [3, [1]],
b69ab31323 ]);
b69ab31324 expect(deps(['ad', 'acd', 'abcd'])).toEqual([
b69ab31325 [1, [0]],
b69ab31326 [2, [1]],
b69ab31327 [3, [1]],
b69ab31328 ]);
b69ab31329
b69ab31330 // Deletions.
b69ab31331 expect(deps(['abcd', 'abd', 'ad', 'a'])).toEqual([
b69ab31332 [1, [0]],
b69ab31333 [2, [1]],
b69ab31334 [3, [1]],
b69ab31335 [4, [1]],
b69ab31336 ]);
b69ab31337 expect(deps(['abcd', 'acd', 'ad', 'd'])).toEqual([
b69ab31338 [1, [0]],
b69ab31339 [2, [1]],
b69ab31340 [3, [1]],
b69ab31341 [4, [1]],
b69ab31342 ]);
b69ab31343
b69ab31344 // Multi-rev insertion, then delete.
b69ab31345 expect(deps(['abc', 'abcdef', '']).at(-1)).toEqual([3, [1, 2]]);
b69ab31346 expect(deps(['abc', 'abcdef', 'af']).at(-1)).toEqual([3, [1, 2]]);
b69ab31347 expect(deps(['abc', 'abcdef', 'cd']).at(-1)).toEqual([3, [1, 2]]);
b69ab31348
b69ab31349 // Another test case.
b69ab31350 const textList = ['abc', 'abcd', 'zabcd', 'zad', 'ad', 'adef', 'ade', 'ad1e', 'xyz'];
b69ab31351 expect(deps(textList)).toStrictEqual([
b69ab31352 [1, [0]],
b69ab31353 [2, [0]],
b69ab31354 [3, [0]],
b69ab31355 // deletes "bc" added by rev 1
b69ab31356 [4, [1]],
b69ab31357 // deletes "z" added by rev 3
b69ab31358 [5, [3]],
b69ab31359 // appends after "d" added by rev 2, considered as independent
b69ab31360 [6, [0]],
b69ab31361 // deletes "f" added by rev 6
b69ab31362 [7, [6]],
b69ab31363 // inserts "1" between "d" (rev 2) and "e" (rev 6), still considered as independent
b69ab31364 [8, [0]],
b69ab31365 // replaces all: "a" (rev 1), "d" (rev 2), "1" (rev 8), "e" (rev 6)
b69ab31366 // rev 4 is also a dependent for nested deletions.
b69ab31367 [9, [1, 2, 4, 6, 8]],
b69ab31368 ]);
b69ab31369 });
b69ab31370
b69ab31371 it('produces flatten lines', () => {
b69ab31372 const textList = ['a\nb\nc\n', 'b\nc\nd\ne\n', 'a\nc\nd\nf\n'];
b69ab31373 const log = logFromTextList(textList);
b69ab31374 const lines = log.flatten();
b69ab31375 expect(lines.toJS()).toEqual(
b69ab31376 [
b69ab31377 ['a', [1]],
b69ab31378 ['a', [3]],
b69ab31379 ['b', [1, 2]],
b69ab31380 ['c', [1, 2, 3]],
b69ab31381 ['d', [2, 3]],
b69ab31382 ['f', [3]],
b69ab31383 ['e', [2]],
b69ab31384 ].map(([line, revs]) => ({revs, data: `${line}\n`})),
b69ab31385 );
b69ab31386 // Verify the flatten lines against definition - if "revs" contains the rev,
b69ab31387 // then the line is included in "rev".
b69ab31388 for (let rev = 1; rev <= textList.length; rev++) {
b69ab31389 const text = lines
b69ab31390 .filter(line => line.revs.has(rev))
b69ab31391 .map(line => line.data)
b69ab31392 .join('');
b69ab31393 expect(text).toBe(textList[rev - 1]);
b69ab31394 }
b69ab31395 });
b69ab31396
b69ab31397 it('supports truncation', () => {
b69ab31398 const textList = ['a\nb\nc\n', 'b\nc\nd\n', 'b\nd\ne\n', 'f\n'];
b69ab31399 const log = logFromTextList(textList);
b69ab31400 // Note: rev 0 is empty.
b69ab31401 for (let truncateRev = 0; truncateRev < textList.length; truncateRev++) {
b69ab31402 const truncatedLog = log.truncate(truncateRev);
b69ab31403 expect(truncatedLog.maxRev).toBe(Math.max(0, truncateRev - 1));
b69ab31404 for (let rev = 0; rev < textList.length; rev++) {
b69ab31405 const text = truncatedLog.checkOut(rev);
b69ab31406 if (rev < truncateRev) {
b69ab31407 expect(text).toBe(rev < 1 ? '' : textList[rev - 1]);
b69ab31408 } else {
b69ab31409 // By contract, rev >= truncateRev are removed, so their content should be the same as truncateRev - 1.
b69ab31410 expect(text).toBe(truncateRev <= 1 ? '' : log.checkOut(truncateRev - 1));
b69ab31411 }
b69ab31412 }
b69ab31413 // We can still append content to the truncatedLog.
b69ab31414 const text = 'a\nc\ne\n';
b69ab31415 const modifiedLog = truncatedLog.recordText(text);
b69ab31416 expect(modifiedLog.checkOut(modifiedLog.maxRev)).toBe(text);
b69ab31417 for (let rev = 0; rev < truncateRev; rev++) {
b69ab31418 expect(modifiedLog.checkOut(rev)).toBe(log.checkOut(rev));
b69ab31419 }
b69ab31420 }
b69ab31421 });
b69ab31422
b69ab31423 // Ported from test-linelog-edits.py (D3709431)
b69ab31424 // Compare LineLog.editChunk against List<string>.splice edits.
b69ab31425 it('stress tests against random edits', () => {
b69ab31426 const maxDeltaA = 10; // max(a2 - a1)
b69ab31427 const maxDeltaB = 10; // max(b2 - b1)
b69ab31428 const maxB1 = 0xffffff;
b69ab31429
b69ab31430 function randInt(min: number, max: number): number {
b69ab31431 return Math.floor(Math.random() * (max - min + 1) + min);
b69ab31432 }
b69ab31433
b69ab31434 function randBool(): boolean {
b69ab31435 return Math.random() < 0.5;
b69ab31436 }
b69ab31437
b69ab31438 function* generateCases(
b69ab31439 endRev = 1000,
b69ab31440 ): Generator<[Immutable.List<string>, Rev, LineIdx, LineIdx, LineIdx, LineIdx, string[]]> {
b69ab31441 // Maintain `lines` as an alternative to LineLog
b69ab31442 let lines: Immutable.List<string> = Immutable.List();
b69ab31443 for (let rev = 0; rev <= endRev; ++rev) {
b69ab31444 const n = lines.size;
b69ab31445 const a1 = randInt(0, n);
b69ab31446 const a2 = randInt(a1, Math.min(n, a1 + maxDeltaA));
b69ab31447 const b1 = randInt(0, maxB1);
b69ab31448 const b2 = randInt(b1, b1 + maxDeltaB);
b69ab31449 const bLines: string[] = [];
b69ab31450 for (let bIdx = b1; bIdx < b2; bIdx++) {
b69ab31451 const line = randBool() ? '\n' : `${rev}:${bIdx}\n`;
b69ab31452 bLines.push(line);
b69ab31453 }
b69ab31454 lines = lines.splice(a1, a2 - a1, ...bLines);
b69ab31455 yield [lines, rev, a1, a2, b1, b2, bLines];
b69ab31456 }
b69ab31457 }
b69ab31458
b69ab31459 const cases = [...generateCases()];
b69ab31460 let log = new LineLog();
b69ab31461
b69ab31462 // The use of aLines cache prevents cache miss.
b69ab31463 // It can reduce editChunk time for 100 revs from 240ms to 8ms.
b69ab31464 const aLines = [...log.checkOutLines(0)];
b69ab31465 executeCache.stats = {miss: 0};
b69ab31466 cases.forEach(([_lines, rev, a1, a2, _b1, _b2, bLines]) => {
b69ab31467 log = log.editChunk(log.maxRev, a1, a2, rev, bLines, aLines);
b69ab31468 });
b69ab31469 expect(executeCache.stats).toMatchObject({miss: 0});
b69ab31470
b69ab31471 // Check that every rev can be checked out fine.
b69ab31472 cases.forEach(([lines, rev, _a1, _a2, _b1, _b2, _bLines]) => {
b69ab31473 expect(log.checkOut(rev)).toBe(lines.join(''));
b69ab31474 });
b69ab31475 });
b69ab31476
b69ab31477 describe('supports remapping revisions', () => {
b69ab31478 it('updates maxRev up', () => {
b69ab31479 const log = logFromTextList(['a', 'b']).remapRevs(new Map([[1, 10]]));
b69ab31480 expect(log.maxRev).toBe(10);
b69ab31481 });
b69ab31482
b69ab31483 it('updates maxRev down', () => {
b69ab31484 const log = new LineLog().recordText('a\n', 10).remapRevs(new Map([[10, 5]]));
b69ab31485 expect(log.maxRev).toBe(5);
b69ab31486 });
b69ab31487
b69ab31488 it('invalidates previous checkout', () => {
b69ab31489 let log = logFromTextList(['b\n', 'b\nc\n', 'a\nb\nc\n']);
b69ab31490 expect(log.checkOut(2)).toBe('b\nc\n');
b69ab31491 log = log.remapRevs(
b69ab31492 new Map([
b69ab31493 [2, 3],
b69ab31494 [3, 2],
b69ab31495 ]),
b69ab31496 );
b69ab31497 expect(log.checkOut(2)).not.toBe('b\nc\n');
b69ab31498 });
b69ab31499
b69ab31500 describe('can reorder changes', () => {
b69ab31501 const defaultSwap: [Rev, Rev] = [2, 3];
b69ab31502
b69ab31503 /** Follow the swap. For example, mapSwap(2, [2, 3]) is 3. */
b69ab31504 const mapSwap = (rev: Rev, swap: [Rev, Rev] = defaultSwap) =>
b69ab31505 rev === swap[0] ? swap[1] : rev === swap[1] ? swap[0] : rev;
b69ab31506
b69ab31507 /**
b69ab31508 * Swap revs from revs to newRevs. All "line"s are added, by different revs.
b69ab31509 * For example, when lines = ['a\n', 'b\n', 'c\n'], lineAddedOrder = [1, 3, 2],
b69ab31510 * it means 'a' was added by rev 1, 'b' by rev 3, 'c' by rev 2, so the 3 revs
b69ab31511 * are ['a\n', 'a\nc\n', 'a\nb\n'].
b69ab31512 *
b69ab31513 * By default, this test takes 3 revs and swap rev 2 and 3.
b69ab31514 */
b69ab31515 function testReorderInsertions(
b69ab31516 lines: string[],
b69ab31517 lineAddedOrder: Rev[],
b69ab31518 opts?: {
b69ab31519 swap?: [Rev, Rev] /* 2 revs to swap, default: [2, 3] */;
b69ab31520 join?: string /* join character, default: '' */;
b69ab31521 expectedDepMapOverride?: [Rev, Rev[]][] /* override the expected depMap */;
b69ab31522 expectedTextOverride?: string[] /* override the expected texts after swapping */;
b69ab31523 },
b69ab31524 ) {
b69ab31525 expect(lines.length).toBe(lineAddedOrder.length);
b69ab31526 const revs = Array.from({length: lines.length}, (_, i) => i + 1); /* ex. [1, 2, 3] */
b69ab31527 const swap = opts?.swap ?? defaultSwap;
b69ab31528 const optJoin = opts?.join ?? '';
b69ab31529 const getTexts = (revOrder: Rev[], join = optJoin): string[] => {
b69ab31530 const revSet = new Set<Rev>();
b69ab31531 return revOrder.map(rev => {
b69ab31532 revSet.add(rev);
b69ab31533 return lines.filter((_l, i) => revSet.has(lineAddedOrder[i])).join(join);
b69ab31534 });
b69ab31535 };
b69ab31536 const texts = getTexts(revs);
b69ab31537 const log = logFromTextList(texts);
b69ab31538
b69ab31539 // Nothing depends on each other.
b69ab31540 expect(flattenDepMap(log.calculateDepMap())).toEqual(
b69ab31541 opts?.expectedDepMapOverride ?? revs.map(r => [r, [0]]),
b69ab31542 );
b69ab31543
b69ab31544 // Reorder.
b69ab31545 const reorderedLog = log.remapRevs(new Map([swap, [swap[1], swap[0]]]));
b69ab31546
b69ab31547 // Check reorder result.
b69ab31548 // Remove "join" for easier comparison.
b69ab31549 const removeJoin = (text: string) =>
b69ab31550 splitLines(text)
b69ab31551 .filter(t => t !== optJoin)
b69ab31552 .join('');
b69ab31553 const reorderedRevs = revs.map(r => mapSwap(r, swap));
b69ab31554 const expectedReorderedText = opts?.expectedTextOverride ?? getTexts(reorderedRevs, '');
b69ab31555 revs.forEach((rev, i) => {
b69ab31556 expect(removeJoin(reorderedLog.checkOut(rev))).toBe(expectedReorderedText[i]);
b69ab31557 });
b69ab31558
b69ab31559 return reorderedLog;
b69ab31560 }
b69ab31561
b69ab31562 const threeRevPermutations = [
b69ab31563 [1, 2, 3],
b69ab31564 [1, 3, 2],
b69ab31565 [2, 1, 3],
b69ab31566 [2, 3, 1],
b69ab31567 [3, 1, 2],
b69ab31568 [3, 2, 1],
b69ab31569 ];
b69ab31570
b69ab31571 /** Make the test a bit more interesting with multi-line input. */
b69ab31572 const charToFunction = (c: string): string => `function ${c} () {\n return '${c}';\n}\n`;
b69ab31573
b69ab31574 const abcTexts = ['a\n', 'b\n', 'c\n'];
b69ab31575 const functionTexts = ['a', 'b', 'c'].map(charToFunction);
b69ab31576
b69ab31577 threeRevPermutations.forEach(revOrder => {
b69ab31578 it(`insert 'a','b','c' in ${revOrder} order`, () => {
b69ab31579 const log = testReorderInsertions(abcTexts, revOrder);
b69ab31580 expect(log.checkOutLines(3)).toMatchObject([
b69ab31581 {data: 'a\n', rev: mapSwap(revOrder[0])},
b69ab31582 {data: 'b\n', rev: mapSwap(revOrder[1])},
b69ab31583 {data: 'c\n', rev: mapSwap(revOrder[2])},
b69ab31584 {data: '', rev: 0},
b69ab31585 ]);
b69ab31586 });
b69ab31587
b69ab31588 it(`insert 3 functions in ${revOrder} order`, () => {
b69ab31589 testReorderInsertions(functionTexts, revOrder);
b69ab31590 });
b69ab31591
b69ab31592 it(`insert 3 functions with new line join, in ${revOrder} order`, () => {
b69ab31593 testReorderInsertions(abcTexts, revOrder, {join: '\n'});
b69ab31594 });
b69ab31595 });
b69ab31596 });
b69ab31597
b69ab31598 it('takes a mapping function', () => {
b69ab31599 const log = logFromTextList(['a\n', 'a\nb\n']).remapRevs(r =>
b69ab31600 r === 2 ? 1 : r === 1 ? 2 : r,
b69ab31601 );
b69ab31602 expect(log.checkOut(1)).toBe('b\n');
b69ab31603 expect(log.checkOut(2)).toBe('a\nb\n');
b69ab31604 });
b69ab31605
b69ab31606 it('can merge changes', () => {
b69ab31607 const log = logFromTextList(['b\n', 'b\nc\n', 'a\nb\nc\n']).remapRevs(new Map([[2, 1]]));
b69ab31608 expect(log.checkOut(1)).toBe('b\nc\n');
b69ab31609 expect(log.checkOut(2)).toBe('b\nc\n');
b69ab31610 expect(log.checkOut(3)).toBe('a\nb\nc\n');
b69ab31611 });
b69ab31612
b69ab31613 it('can insert changes', () => {
b69ab31614 const log = logFromTextList(['b\n', 'b\nc\n'])
b69ab31615 .remapRevs(new Map([[2, 3]]))
b69ab31616 .recordText('a\nb\n', 2);
b69ab31617 expect(log.checkOut(3)).toBe('a\nb\nc\n');
b69ab31618 });
b69ab31619
b69ab31620 it('does not check dependencies or conflicts', () => {
b69ab31621 // rev 2: +b between a and c. rev 2 depends on rev 1.
b69ab31622 const log = logFromTextList(['a\nc\n', 'a\nb\nc\n']).remapRevs(
b69ab31623 new Map([
b69ab31624 [1, 2],
b69ab31625 [2, 1],
b69ab31626 ]),
b69ab31627 );
b69ab31628 // rev 1 is now empty, not 'b'.
b69ab31629 expect(log.checkOut(1)).toBe('');
b69ab31630 expect(log.checkOut(2)).toBe('a\nb\nc\n');
b69ab31631 });
b69ab31632 });
b69ab31633});
b69ab31634
b69ab31635function logFromTextList(textList: string[]): LineLog {
b69ab31636 let log = new LineLog();
b69ab31637 textList.forEach(text => (log = log.recordText(text)));
b69ab31638 return log;
b69ab31639}
b69ab31640
b69ab31641function flattenDepMap(depMap: Map<Rev, Set<Rev>>): [Rev, Rev[]][] {
b69ab31642 return [...depMap.entries()].map(([rev, set]) => [rev, [...set].sort()] as [Rev, Rev[]]).sort();
b69ab31643}