14.4 KB533 lines
Blame
1/**
2 * Copyright (c) Meta Platforms, Inc. and affiliates.
3 *
4 * This source code is licensed under the MIT license found in the
5 * LICENSE file in the root directory of this source tree.
6 */
7
8import type {Block} from '../diff';
9
10import {
11 collapseContextBlocks,
12 diffBlocks,
13 mergeBlocks,
14 readableDiffBlocks,
15 splitLines,
16} from '../diff';
17
18describe('diffBlocks', () => {
19 it('returns a "=" block for unchanged content', () => {
20 const lines = splitLines('a\nb\nc\nd\ne\n');
21 expect(diffBlocks(lines, lines)).toMatchObject([['=', [0, 5, 0, 5]]]);
22 });
23
24 it('returns a "!" block for totally different contents', () => {
25 const aLines = splitLines('x\ny\n');
26 const bLines = splitLines('a\nb\nc\n');
27 expect(diffBlocks(aLines, bLines)).toMatchObject([['!', [0, 2, 0, 3]]]);
28 });
29
30 it('returns "= ! =" blocks when a line was changed in the middle', () => {
31 const aLines = splitLines('a\nb\nc\nd\ne\n');
32 const bLines = splitLines('a\nb\nc\nd1\nd2\ne\n');
33 expect(diffBlocks(aLines, bLines)).toMatchObject([
34 ['=', [0, 3, 0, 3]],
35 ['!', [3, 4, 3, 5]],
36 ['=', [4, 5, 5, 6]],
37 ]);
38 });
39
40 it('matches mdiff.blocks (known good diff algorithm), excluding empty blocks', () => {
41 // Test cases are generated by:
42 //
43 // ```
44 // #!sl dbsh
45 // import json
46 // allblocks = e.mdiff.allblocks
47 // cases = []
48 // for bits in range(16):
49 // a = ['a\n', 'b\n', 'c\n', 'd\n']
50 // b = [bits & (1 << i) and c.upper() or c for i, c in enumerate(a)]
51 // a = ''.join(a)
52 // b = ''.join(b)
53 // blocks = [[s, l] for l, s in allblocks(a, b) if l[0] < l[1] or l[2] < l[3]] # skip empty blocks
54 // cases.append(json.dumps(blocks).replace(' ', ''))
55 // print(' '.join(cases))
56 // ```
57 //
58 // String is used to prettier from wrapping lines.
59 const testCaseStr =
60 '[["=",[0,4,0,4]]] [["!",[0,1,0,1]],["=",[1,4,1,4]]] [["=",[0,1,0,1]],["!",[1,2,1,2]],["=",[2,4,2,4]]] [["!",[0,2,0,2]],["=",[2,4,2,4]]] [["=",[0,2,0,2]],["!",[2,3,2,3]],["=",[3,4,3,4]]] [["!",[0,1,0,1]],["=",[1,2,1,2]],["!",[2,3,2,3]],["=",[3,4,3,4]]] [["=",[0,1,0,1]],["!",[1,3,1,3]],["=",[3,4,3,4]]] [["!",[0,3,0,3]],["=",[3,4,3,4]]] [["=",[0,3,0,3]],["!",[3,4,3,4]]] [["!",[0,1,0,1]],["=",[1,3,1,3]],["!",[3,4,3,4]]] [["=",[0,1,0,1]],["!",[1,2,1,2]],["=",[2,3,2,3]],["!",[3,4,3,4]]] [["!",[0,2,0,2]],["=",[2,3,2,3]],["!",[3,4,3,4]]] [["=",[0,2,0,2]],["!",[2,4,2,4]]] [["!",[0,1,0,1]],["=",[1,2,1,2]],["!",[2,4,2,4]]] [["=",[0,1,0,1]],["!",[1,4,1,4]]] [["!",[0,4,0,4]]]';
61 const testCases: Array<Block[]> = testCaseStr.split(' ').map(s => JSON.parse(s));
62 testCases.forEach((expected, bits) => {
63 // eslint-disable-next-line no-bitwise
64 const hasBit = (i: number): boolean => (bits & (1 << i)) > 0;
65 const a = ['a\n', 'b\n', 'c\n', 'd\n'];
66 const b = a.map((s, i) => (hasBit(i) ? s.toUpperCase() : s));
67 const actual = diffBlocks(a, b);
68 expect(actual).toEqual(expected);
69 });
70 });
71});
72
73describe('readableDiffBlocks', () => {
74 it('prefers changing insignificant lines to insignificant lines 1', () => {
75 // https://stackoverflow.com/questions/40550751/unexpected-result-in-git-diff
76 const a = `sub _process_message {
77 my ($self, $message) = @_;
78
79 my $method = ref($message) eq 'HASH' ? $message->{method} : undef;
80
81 return $self->send_error(ERROR_REQUEST_INVALID)
82 unless defined($method);
83`;
84 const b = `sub _process_message {
85 my ($self, $message) = @_;
86
87 my $time = [ gettimeofday ];
88
89 my $method = ref($message) eq 'HASH' ? $message->{method} : undef;
90 return $self->send_error(ERROR_REQUEST_INVALID)
91 unless defined($method);
92`;
93 // Does not produce this:
94 // sub _process_message {
95 // my ($self, $message) = @_;
96 //
97 // - my $method = ref($message) eq 'HASH' ? $message->{method} : undef;
98 // + my $time = [ gettimeofday ];
99 //
100 // + my $method = ref($message) eq 'HASH' ? $message->{method} : undef;
101 // return $self->send_error(ERROR_REQUEST_INVALID)
102 // unless defined($method);
103 expect(renderDiff(a, b, readableDiffBlocks)).toMatchInlineSnapshot(`
104 " sub _process_message {
105 my ($self, $message) = @_;
106
107 + my $time = [ gettimeofday ];
108 +
109 my $method = ref($message) eq 'HASH' ? $message->{method} : undef;
110 -
111 return $self->send_error(ERROR_REQUEST_INVALID)
112 unless defined($method);
113 "
114 `);
115 });
116
117 it('prefers changing insignificant lines to insignificant lines 2', () => {
118 // https://gitlab.com/jssfr/diffsample/-/compare/bob...alice
119 const a = `void Chunk_copy(Chunk *src, size_t src_start, Chunk *dst, size_t dst_start, size_t n)
120{
121 if (!Chunk_bounds_check(src, src_start, n)) return;
122 if (!Chunk_bounds_check(dst, dst_start, n)) return;
123
124 memcpy(dst->data + dst_start, src->data + src_start, n);
125}
126
127int Chunk_bounds_check(Chunk *chunk, size_t start, size_t n)
128{
129 if (chunk == NULL) return 0;
130
131 return start <= chunk->length && n <= chunk->length - start;
132}
133`;
134 const b = `int Chunk_bounds_check(Chunk *chunk, size_t start, size_t n)
135{
136 if (chunk == NULL) return 0;
137
138 return start <= chunk->length && n <= chunk->length - start;
139}
140
141void Chunk_copy(Chunk *src, size_t src_start, Chunk *dst, size_t dst_start, size_t n)
142{
143 if (!Chunk_bounds_check(src, src_start, n)) return;
144 if (!Chunk_bounds_check(dst, dst_start, n)) return;
145
146 memcpy(dst->data + dst_start, src->data + src_start, n);
147}
148`;
149 // Does not produce this:
150 // -void Chunk_copy(Chunk *src, size_t src_start, Chunk *dst, size_t dst_start, size_t n)
151 // +int Chunk_bounds_check(Chunk *chunk, size_t start, size_t n)
152 // {
153 // - if (!Chunk_bounds_check(src, src_start, n)) return;
154 // - if (!Chunk_bounds_check(dst, dst_start, n)) return;
155 // + if (chunk == NULL) return 0;
156 //
157 // - // copy the bytes
158 // - memcpy(dst->data + dst_start, src->data + src_start, n);
159 // + return start <= chunk->length && n <= chunk->length - start;
160 // }
161 //
162 // -int Chunk_bounds_check(Chunk *chunk, size_t start, size_t n)
163 // +void Chunk_copy(Chunk *src, size_t src_start, Chunk *dst, size_t dst_start, size_t n)
164 // {
165 // - if (chunk == NULL) return 0;
166 // + if (!Chunk_bounds_check(src, src_start, n)) return;
167 // + if (!Chunk_bounds_check(dst, dst_start, n)) return;
168 //
169 // - return start <= chunk->length && n <= chunk->length - start;
170 // + memcpy(dst->data + dst_start, src->data + src_start, n);
171 // }
172 expect(renderDiff(a, b, readableDiffBlocks)).toMatchInlineSnapshot(`
173 "+int Chunk_bounds_check(Chunk *chunk, size_t start, size_t n)
174 +{
175 + if (chunk == NULL) return 0;
176 +
177 + return start <= chunk->length && n <= chunk->length - start;
178 +}
179 +
180 void Chunk_copy(Chunk *src, size_t src_start, Chunk *dst, size_t dst_start, size_t n)
181 {
182 if (!Chunk_bounds_check(src, src_start, n)) return;
183 if (!Chunk_bounds_check(dst, dst_start, n)) return;
184
185 memcpy(dst->data + dst_start, src->data + src_start, n);
186 }
187 -
188 -int Chunk_bounds_check(Chunk *chunk, size_t start, size_t n)
189 -{
190 - if (chunk == NULL) return 0;
191 -
192 - return start <= chunk->length && n <= chunk->length - start;
193 -}
194 "
195 `);
196 expect(renderDiff(b, a, readableDiffBlocks)).toMatchInlineSnapshot(`
197 "-int Chunk_bounds_check(Chunk *chunk, size_t start, size_t n)
198 -{
199 - if (chunk == NULL) return 0;
200 -
201 - return start <= chunk->length && n <= chunk->length - start;
202 -}
203 -
204 void Chunk_copy(Chunk *src, size_t src_start, Chunk *dst, size_t dst_start, size_t n)
205 {
206 if (!Chunk_bounds_check(src, src_start, n)) return;
207 if (!Chunk_bounds_check(dst, dst_start, n)) return;
208
209 memcpy(dst->data + dst_start, src->data + src_start, n);
210 }
211 +
212 +int Chunk_bounds_check(Chunk *chunk, size_t start, size_t n)
213 +{
214 + if (chunk == NULL) return 0;
215 +
216 + return start <= chunk->length && n <= chunk->length - start;
217 +}
218 "
219 `);
220 });
221
222 it('sometimes produces non-minimal diff', () => {
223 const a = `b
224{
225 b1
226}
227
228a
229{
230 a1
231}
232`;
233 const b = `a
234{
235 a1
236}
237
238b
239{
240 b1
241}
242`;
243 // The regular diff produces the minimal diff with 8 changed lines.
244 expect(renderDiff(a, b, diffBlocks)).toMatchInlineSnapshot(`
245 "-b
246 +a
247 {
248 - b1
249 + a1
250 }
251
252 -a
253 +b
254 {
255 - a1
256 + b1
257 }
258 "
259 `);
260 // The "readable" diff has 10 changed lines, but is easier to read by a human.
261 expect(renderDiff(a, b, readableDiffBlocks)).toMatchInlineSnapshot(`
262 "-b
263 -{
264 - b1
265 -}
266 -
267 a
268 {
269 a1
270 }
271 +
272 +b
273 +{
274 + b1
275 +}
276 "
277 `);
278 });
279
280 it('avoids the pitfall of the patience diff flaw', () => {
281 // Textbook patience diff will match the unique line "x" unconditionally,
282 // and produces suboptimal result deleting and inserting multiple
283 // insignificant lines. Our diff uses a simple heuristic to avoid that.
284 const a = `{
285{
286{
287x
288`;
289 const b = `x
290{
291{
292{
293`;
294
295 expect(renderDiff(a, b, readableDiffBlocks)).toMatchInlineSnapshot(`
296 "+x
297 {
298 {
299 {
300 -x
301 "
302 `);
303 });
304});
305
306describe('collapseContextBlocks', () => {
307 it('collapses everything in a "=" block', () => {
308 expect(collapseContextBlocks([['=', [0, 5, 0, 5]]], () => false)).toMatchObject([
309 ['~', [0, 5, 0, 5]],
310 ]);
311 });
312
313 it('collapses the top part of a "=" block', () => {
314 expect(
315 collapseContextBlocks(
316 [
317 ['=', [0, 5, 0, 5]],
318 ['!', [5, 6, 5, 7]],
319 ],
320 () => false,
321 ),
322 ).toMatchObject([
323 ['~', [0, 2, 0, 2]],
324 ['=', [2, 5, 2, 5]],
325 ['!', [5, 6, 5, 7]],
326 ]);
327 });
328
329 it('collapses the bottom part of a "=" block', () => {
330 expect(
331 collapseContextBlocks(
332 [
333 ['!', [0, 2, 0, 3]],
334 ['=', [2, 8, 3, 9]],
335 ],
336 () => false,
337 ),
338 ).toMatchObject([
339 ['!', [0, 2, 0, 3]],
340 ['=', [2, 5, 3, 6]],
341 ['~', [5, 8, 6, 9]],
342 ]);
343 });
344
345 it('splits a "=" block in 3 blocks on demand', () => {
346 expect(
347 collapseContextBlocks(
348 [
349 ['!', [0, 1, 0, 2]],
350 ['=', [1, 10, 2, 11]],
351 ['!', [10, 11, 11, 12]],
352 ],
353 () => false,
354 ),
355 ).toMatchObject([
356 ['!', [0, 1, 0, 2]],
357 ['=', [1, 4, 2, 5]],
358 ['~', [4, 7, 5, 8]],
359 ['=', [7, 10, 8, 11]],
360 ['!', [10, 11, 11, 12]],
361 ]);
362 });
363
364 it('respects isExpanded function', () => {
365 expect(
366 collapseContextBlocks(
367 [
368 ['!', [0, 1, 0, 2]],
369 ['=', [1, 10, 2, 11]],
370 ['!', [10, 11, 11, 12]],
371 ],
372 (aLine, _bLine) => aLine === 4,
373 ),
374 ).toMatchObject([
375 ['!', [0, 1, 0, 2]],
376 ['=', [1, 10, 2, 11]],
377 ['!', [10, 11, 11, 12]],
378 ]);
379 });
380
381 it('skips "~" if "=" block is too small', () => {
382 expect(
383 collapseContextBlocks(
384 [
385 ['!', [0, 1, 0, 2]],
386 ['=', [1, 7, 2, 8]],
387 ['!', [7, 8, 8, 9]],
388 ],
389 () => false,
390 ),
391 ).toMatchObject([
392 ['!', [0, 1, 0, 2]],
393 ['=', [1, 7, 2, 8]],
394 ['!', [7, 8, 8, 9]],
395 ]);
396 });
397
398 it('preserves context around empty ! block', () => {
399 expect(
400 collapseContextBlocks(
401 [
402 ['=', [0, 5, 0, 5]],
403 ['!', [5, 5, 5, 5]],
404 ['=', [5, 6, 5, 6]],
405 ],
406 () => false,
407 ),
408 ).toEqual([
409 ['~', [0, 2, 0, 2]],
410 ['=', [2, 5, 2, 5]],
411 ['!', [5, 5, 5, 5]],
412 ['=', [5, 6, 5, 6]],
413 ]);
414 });
415
416 it('handles adjacent "=" blocks', () => {
417 expect(
418 collapseContextBlocks(
419 [
420 ['=', [0, 2, 0, 2]],
421 ['=', [2, 8, 2, 8]],
422 ],
423 () => false,
424 ),
425 ).toMatchObject([
426 ['~', [0, 2, 0, 2]],
427 ['~', [2, 8, 2, 8]],
428 ]);
429 });
430});
431
432describe('mergeBlocks', () => {
433 it('should handle empty blocks', () => {
434 const result = mergeBlocks([], []);
435 expect(result).toEqual([]);
436 });
437
438 it('should merge blocks', () => {
439 const abBlocks: Array<Block> = [
440 ['!', [0, 0, 0, 1]],
441 ['!', [0, 0, 1, 4]],
442 ['!', [0, 0, 4, 7]],
443 ];
444 const cbBlocks: Array<Block> = [
445 ['!', [0, 0, 0, 2]],
446 ['!', [0, 0, 2, 3]],
447 ['!', [0, 0, 3, 6]],
448 ['!', [0, 0, 6, 7]],
449 ];
450 const result = mergeBlocks(abBlocks, cbBlocks);
451 expect(result).toEqual([['!', [0, 7, 0, 7]]]);
452 });
453
454 it('should handle blocks with different signs', () => {
455 let abBlocks: Array<Block> = [
456 ['!', [0, 1, 0, 1]],
457 ['!', [1, 2, 1, 2]],
458 ['=', [2, 5, 3, 6]],
459 ];
460 let cbBlocks: Array<Block> = [
461 ['!', [0, 2, 0, 3]],
462 ['=', [2, 3, 3, 4]],
463 ['=', [3, 5, 4, 6]],
464 ];
465 let result = mergeBlocks(abBlocks, cbBlocks);
466 expect(result).toEqual([
467 ['!', [0, 3, 0, 3]],
468 ['=', [3, 6, 3, 6]],
469 ]);
470
471 abBlocks = [
472 ['!', [0, 0, 0, 3]],
473 ['=', [0, 4, 3, 7]],
474 ];
475 cbBlocks = [
476 ['=', [0, 1, 0, 1]],
477 ['=', [1, 4, 1, 4]],
478 ['!', [4, 4, 4, 6]],
479 ['=', [4, 5, 6, 7]],
480 ];
481 result = mergeBlocks(abBlocks, cbBlocks);
482 expect(result).toEqual([
483 ['!', [0, 3, 0, 3]],
484 ['=', [3, 4, 3, 4]],
485 ['!', [4, 6, 4, 6]],
486 ['=', [6, 7, 6, 7]],
487 ]);
488 });
489
490 it('should preserve empty ranges', () => {
491 const abBlocks: Array<Block> = [
492 ['=', [0, 1, 0, 1]],
493 ['!', [1, 2, 1, 1]],
494 ['=', [2, 6, 1, 5]],
495 ];
496 const cbBlocks: Array<Block> = [
497 ['=', [0, 4, 0, 4]],
498 ['!', [4, 5, 4, 4]],
499 ['=', [5, 6, 4, 5]],
500 ];
501 const result = mergeBlocks(abBlocks, cbBlocks);
502 expect(result).toEqual([
503 ['=', [0, 1, 0, 1]],
504 ['!', [1, 1, 1, 1]],
505 ['=', [1, 4, 1, 4]],
506 ['!', [4, 4, 4, 4]],
507 ['=', [4, 5, 4, 5]],
508 ]);
509 });
510});
511
512function renderDiff(
513 a: string,
514 b: string,
515 diffFunc: (aLines: string[], bLines: string[]) => Array<Block>,
516): string {
517 const aLines = splitLines(a);
518 const bLines = splitLines(b);
519 const blocks = diffFunc(aLines, bLines);
520 return blocks
521 .flatMap(([sign, [a1, a2, b1, b2]]) => {
522 if (sign === '=') {
523 return aLines.slice(a1, a2).map(l => ` ${l}`);
524 } else {
525 return aLines
526 .slice(a1, a2)
527 .map(l => `-${l}`)
528 .concat(bLines.slice(b1, b2).map(l => `+${l}`));
529 }
530 })
531 .join('');
532}
533