FazBrowse GitHub Viewer | Trending |
URL:
| Home
Tools: [Download Repo ZIP]   [Original HTTPS Page]

util: expose diff function used by the assertion errors · nodejs/node@1b8d1d3 · GitHub

/ node Public

Commit 1b8d1d3

Browse files
Giovanni Bucci
authored and
aduh95
committed
util: expose diff function used by the assertion errors
fix: #51740 PR-URL: #57462 Fixes: #51740 Reviewed-By: James M Snell <jasnell@gmail.com> Reviewed-By: Benjamin Gruenbaum <benjamingr@gmail.com> Reviewed-By: Pietro Marchini <pietro.marchini94@gmail.com> Reviewed-By: Ruben Bridgewater <ruben@bridgewater.de>
1 parent 7b72396 commit 1b8d1d3

6 files changed

Lines changed: 257 additions & 16 deletions

File tree

‎benchmark/util/diff.js‎

Lines changed: 43 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,43 @@
1+
'use strict';
2+
3+
const util = require('util');
4+
const common = require('../common');
5+
6+
const bench = common.createBenchmark(main, {
7+
n: [1e3],
8+
length: [1e3, 2e3],
9+
scenario: ['identical', 'small-diff', 'medium-diff', 'large-diff'],
10+
});
11+
12+
function main({ n, length, scenario }) {
13+
const actual = Array.from({ length }, (_, i) => `${i}`);
14+
let expected;
15+
16+
switch (scenario) {
17+
case 'identical': // 0% difference
18+
expected = Array.from({ length }, (_, i) => `${i}`);
19+
break;
20+
21+
case 'small-diff': // ~5% difference
22+
expected = Array.from({ length }, (_, i) => {
23+
return Math.random() < 0.05 ? `modified-${i}` : `${i}`;
24+
});
25+
break;
26+
27+
case 'medium-diff': // ~25% difference
28+
expected = Array.from({ length }, (_, i) => {
29+
return Math.random() < 0.25 ? `modified-${i}` : `${i}`;
30+
});
31+
break;
32+
33+
case 'large-diff': // ~100% difference
34+
expected = Array.from({ length }, (_, i) => `modified-${i}`);
35+
break;
36+
}
37+
38+
bench.start();
39+
for (let i = 0; i < n; i++) {
40+
util.diff(actual, expected);
41+
}
42+
bench.end(n);
43+
}

‎doc/api/util.md‎

Lines changed: 65 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -325,6 +325,70 @@ The `--throw-deprecation` command-line flag and `process.throwDeprecation`
325325
property take precedence over `--trace-deprecation` and
326326
`process.traceDeprecation`.
327327

328+
## `util.diff(actual, expected)`
329+
330+
<!-- YAML
331+
added: REPLACEME
332+
-->
333+
334+
> Stability: 1 - Experimental
335+
336+
* `actual` {Array|string} The first value to compare
337+
338+
* `expected` {Array|string} The second value to compare
339+
340+
* Returns: {Array} An array of difference entries. Each entry is an array with two elements:
341+
* Index 0: {number} Operation code: `-1` for delete, `0` for no-op/unchanged, `1` for insert
342+
* Index 1: {string} The value associated with the operation
343+
344+
* Algorithm complexity: O(N\*D), where:
345+
346+
* N is the total length of the two sequences combined (N = actual.length + expected.length)
347+
348+
* D is the edit distance (the minimum number of operations required to transform one sequence into the other).
349+
350+
[`util.diff()`][] compares two string or array values and returns an array of difference entries.
351+
It uses the Myers diff algorithm to compute minimal differences, which is the same algorithm
352+
used internally by assertion error messages.
353+
354+
If the values are equal, an empty array is returned.
355+
356+
```js
357+
const { diff } = require('node:util');
358+
359+
// Comparing strings
360+
const actualString = '12345678';
361+
const expectedString = '12!!5!7!';
362+
console.log(diff(actualString, expectedString));
363+
// [
364+
// [0, '1'],
365+
// [0, '2'],
366+
// [1, '3'],
367+
// [1, '4'],
368+
// [-1, '!'],
369+
// [-1, '!'],
370+
// [0, '5'],
371+
// [1, '6'],
372+
// [-1, '!'],
373+
// [0, '7'],
374+
// [1, '8'],
375+
// [-1, '!'],
376+
// ]
377+
// Comparing arrays
378+
const actualArray = ['1', '2', '3'];
379+
const expectedArray = ['1', '3', '4'];
380+
console.log(diff(actualArray, expectedArray));
381+
// [
382+
// [0, '1'],
383+
// [1, '2'],
384+
// [0, '3'],
385+
// [-1, '4'],
386+
// ]
387+
// Equal values return empty array
388+
console.log(diff('same', 'same'));
389+
// []
390+
```
391+
328392
## `util.format(format[, ...args])`
329393

330394
<!-- YAML
@@ -3612,6 +3676,7 @@ util.isArray({});
36123676
[`napi_create_external()`]: n-api.md#napi_create_external
36133677
[`target` and `handler`]: https://developer.mozilla.org/en-US/docs/Web/JavaScript/Reference/Global_Objects/Proxy#Terminology
36143678
[`tty.hasColors()`]: tty.md#writestreamhascolorscount-env
3679+
[`util.diff()`]: #utildiffactual-expected
36153680
[`util.format()`]: #utilformatformat-args
36163681
[`util.inspect()`]: #utilinspectobject-options
36173682
[`util.promisify()`]: #utilpromisifyoriginal

‎lib/internal/assert/myers_diff.js‎

Lines changed: 21 additions & 16 deletions
Original file line numberDiff line numberDiff line change
@@ -9,6 +9,11 @@ const {
99
const colors = require('internal/util/colors');
1010

1111
const kNopLinesToCollapse = 5;
12+
const kOperations = {
13+
DELETE: -1,
14+
NOP: 0,
15+
INSERT: 1,
16+
};
1217

1318
function areLinesEqual(actual, expected, checkCommaDisparity) {
1419
if (actual === expected) {
@@ -87,16 +92,16 @@ function backtrack(trace, actual, expected, checkCommaDisparity) {
8792
while (x > prevX && y > prevY) {
8893
const actualItem = actual[x - 1];
8994
const value = checkCommaDisparity && !StringPrototypeEndsWith(actualItem, ',') ? expected[y - 1] : actualItem;
90-
ArrayPrototypePush(result, { __proto__: null, type: 'nop', value });
95+
ArrayPrototypePush(result, [ kOperations.NOP, value ]);
9196
x--;
9297
y--;
9398
}
9499

95100
if (diffLevel > 0) {
96101
if (x > prevX) {
97-
ArrayPrototypePush(result, { __proto__: null, type: 'insert', value: actual[--x] });
102+
ArrayPrototypePush(result, [ kOperations.INSERT, actual[--x] ]);
98103
} else {
99-
ArrayPrototypePush(result, { __proto__: null, type: 'delete', value: expected[--y] });
104+
ArrayPrototypePush(result, [ kOperations.DELETE, expected[--y] ]);
100105
}
101106
}
102107
}
@@ -108,12 +113,12 @@ function printSimpleMyersDiff(diff) {
108113
let message = '';
109114

110115
for (let diffIdx = diff.length - 1; diffIdx >= 0; diffIdx--) {
111-
const { type, value } = diff[diffIdx];
116+
const { 0: operation, 1: value } = diff[diffIdx];
112117
let color = colors.white;
113118

114-
if (type === 'insert') {
119+
if (operation === kOperations.INSERT) {
115120
color = colors.green;
116-
} else if (type === 'delete') {
121+
} else if (operation === kOperations.DELETE) {
117122
color = colors.red;
118123
}
119124

@@ -129,33 +134,33 @@ function printMyersDiff(diff, operator) {
129134
let nopCount = 0;
130135

131136
for (let diffIdx = diff.length - 1; diffIdx >= 0; diffIdx--) {
132-
const { type, value } = diff[diffIdx];
133-
const previousType = diffIdx < diff.length - 1 ? diff[diffIdx + 1].type : null;
137+
const { 0: operation, 1: value } = diff[diffIdx];
138+
const previousOperation = diffIdx < diff.length - 1 ? diff[diffIdx + 1][0] : null;
134139

135140
// Avoid grouping if only one line would have been grouped otherwise
136-
if (previousType === 'nop' && type !== previousType) {
141+
if (previousOperation === kOperations.NOP && operation !== previousOperation) {
137142
if (nopCount === kNopLinesToCollapse + 1) {
138-
message += `${colors.white} ${diff[diffIdx + 1].value}\n`;
143+
message += `${colors.white} ${diff[diffIdx + 1][1]}\n`;
139144
} else if (nopCount === kNopLinesToCollapse + 2) {
140-
message += `${colors.white} ${diff[diffIdx + 2].value}\n`;
141-
message += `${colors.white} ${diff[diffIdx + 1].value}\n`;
145+
message += `${colors.white} ${diff[diffIdx + 2][1]}\n`;
146+
message += `${colors.white} ${diff[diffIdx + 1][1]}\n`;
142147
} else if (nopCount >= kNopLinesToCollapse + 3) {
143148
message += `${colors.blue}...${colors.white}\n`;
144-
message += `${colors.white} ${diff[diffIdx + 1].value}\n`;
149+
message += `${colors.white} ${diff[diffIdx + 1][1]}\n`;
145150
skipped = true;
146151
}
147152
nopCount = 0;
148153
}
149154

150-
if (type === 'insert') {
155+
if (operation === kOperations.INSERT) {
151156
if (operator === 'partialDeepStrictEqual') {
152157
message += `${colors.gray}${colors.hasColors ? ' ' : '+'} ${value}${colors.white}\n`;
153158
} else {
154159
message += `${colors.green}+${colors.white} ${value}\n`;
155160
}
156-
} else if (type === 'delete') {
161+
} else if (operation === kOperations.DELETE) {
157162
message += `${colors.red}-${colors.white} ${value}\n`;
158-
} else if (type === 'nop') {
163+
} else if (operation === kOperations.NOP) {
159164
if (nopCount < kNopLinesToCollapse) {
160165
message += `${colors.white} ${value}\n`;
161166
}

‎lib/internal/util/diff.js‎

Lines changed: 42 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,42 @@
1+
'use strict';
2+
3+
const {
4+
ArrayIsArray,
5+
ArrayPrototypeReverse,
6+
} = primordials;
7+
8+
const { validateStringArray, validateString } = require('internal/validators');
9+
const { myersDiff } = require('internal/assert/myers_diff');
10+
11+
function validateInput(value, name) {
12+
if (!ArrayIsArray(value)) {
13+
validateString(value, name);
14+
return;
15+
}
16+
17+
validateStringArray(value, name);
18+
}
19+
20+
/**
21+
* Generate a difference report between two values
22+
* @param {Array | string} actual - The first value to compare
23+
* @param {Array | string} expected - The second value to compare
24+
* @returns {Array} - An array of differences between the two values.
25+
* The returned data is an array of arrays, where each sub-array has two elements:
26+
* 1. The operation to perform: -1 for delete, 0 for no-op, 1 for insert
27+
* 2. The value to perform the operation on
28+
*/
29+
function diff(actual, expected) {
30+
if (actual === expected) {
31+
return [];
32+
}
33+
34+
validateInput(actual, 'actual');
35+
validateInput(expected, 'expected');
36+
37+
return ArrayPrototypeReverse(myersDiff(actual, expected));
38+
}
39+
40+
module.exports = {
41+
diff,
42+
};

‎lib/util.js‎

Lines changed: 6 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -483,3 +483,9 @@ defineLazyProperties(
483483
'internal/mime',
484484
['MIMEType', 'MIMEParams'],
485485
);
486+
487+
defineLazyProperties(
488+
module.exports,
489+
'internal/util/diff',
490+
['diff'],
491+
);

‎test/parallel/test-diff.js‎

Lines changed: 80 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,80 @@
1+
'use strict';
2+
require('../common');
3+
4+
const { describe, it } = require('node:test');
5+
const { deepStrictEqual, throws } = require('node:assert');
6+
7+
const { diff } = require('util');
8+
9+
describe('diff', () => {
10+
it('throws because actual is nor an array nor a string', () => {
11+
const actual = {};
12+
const expected = 'foo';
13+
14+
throws(() => diff(actual, expected), {
15+
message: 'The "actual" argument must be of type string. Received an instance of Object'
16+
});
17+
});
18+
19+
it('throws because expected is nor an array nor a string', () => {
20+
const actual = 'foo';
21+
const expected = {};
22+
23+
throws(() => diff(actual, expected), {
24+
message: 'The "expected" argument must be of type string. Received an instance of Object'
25+
});
26+
});
27+
28+
29+
it('throws because the actual array does not only contain string', () => {
30+
const actual = ['1', { b: 2 }];
31+
const expected = ['1', '2'];
32+
33+
throws(() => diff(actual, expected), {
34+
message: 'The "actual[1]" argument must be of type string. Received an instance of Object'
35+
});
36+
});
37+
38+
it('returns an empty array because actual and expected are the same', () => {
39+
const actual = 'foo';
40+
const expected = 'foo';
41+
42+
const result = diff(actual, expected);
43+
deepStrictEqual(result, []);
44+
});
45+
46+
it('returns the diff for strings', () => {
47+
const actual = '12345678';
48+
const expected = '12!!5!7!';
49+
const result = diff(actual, expected);
50+
51+
deepStrictEqual(result, [
52+
[0, '1'],
53+
[0, '2'],
54+
[1, '3'],
55+
[1, '4'],
56+
[-1, '!'],
57+
[-1, '!'],
58+
[0, '5'],
59+
[1, '6'],
60+
[-1, '!'],
61+
[0, '7'],
62+
[1, '8'],
63+
[-1, '!'],
64+
]);
65+
});
66+
67+
it('returns the diff for arrays', () => {
68+
const actual = ['1', '2', '3'];
69+
const expected = ['1', '3', '4'];
70+
const result = diff(actual, expected);
71+
72+
deepStrictEqual(result, [
73+
[0, '1'],
74+
[1, '2'],
75+
[0, '3'],
76+
[-1, '4'],
77+
]
78+
);
79+
});
80+
});

0 commit comments

Comments
 (0)
Back | FazBrowse Home | New Git URL