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

assert: make myers_diff function more performant · nodejs/node@334a3ac · GitHub

/ node Public

Commit 334a3ac

Browse files
Giovanni Bucci
authored and
aduh95
committed
assert: make myers_diff function more performant
PR-URL: #56303 Refs: #54862 Reviewed-By: Antoine du Hamel <duhamelantoine1995@gmail.com> Reviewed-By: Xuguang Mei <meixuguang@gmail.com> Reviewed-By: Ruben Bridgewater <ruben@bridgewater.de> Reviewed-By: Pietro Marchini <pietro.marchini94@gmail.com> Reviewed-By: James M Snell <jasnell@gmail.com>
1 parent c8d1dcb commit 334a3ac

1 file changed

Lines changed: 35 additions & 27 deletions

File tree

‎lib/internal/assert/myers_diff.js‎

Lines changed: 35 additions & 27 deletions
Original file line numberDiff line numberDiff line change
@@ -1,10 +1,9 @@
11
'use strict';
22

33
const {
4-
Array,
5-
ArrayPrototypeFill,
64
ArrayPrototypePush,
75
ArrayPrototypeSlice,
6+
Int32Array,
87
StringPrototypeEndsWith,
98
} = primordials;
109

@@ -26,7 +25,7 @@ function myersDiff(actual, expected, checkCommaDisparity = false) {
2625
const actualLength = actual.length;
2726
const expectedLength = expected.length;
2827
const max = actualLength + expectedLength;
29-
const v = ArrayPrototypeFill(Array(2 * max + 1), 0);
28+
const v = new Int32Array(2 * max + 1);
3029

3130
const trace = [];
3231

@@ -35,22 +34,24 @@ function myersDiff(actual, expected, checkCommaDisparity = false) {
3534
ArrayPrototypePush(trace, newTrace);
3635

3736
for (let diagonalIndex = -diffLevel; diagonalIndex <= diffLevel; diagonalIndex += 2) {
38-
let x;
39-
if (diagonalIndex === -diffLevel ||
40-
(diagonalIndex !== diffLevel && v[diagonalIndex - 1 + max] < v[diagonalIndex + 1 + max])) {
41-
x = v[diagonalIndex + 1 + max];
42-
} else {
43-
x = v[diagonalIndex - 1 + max] + 1;
44-
}
45-
37+
const offset = diagonalIndex + max;
38+
const previousOffset = v[offset - 1];
39+
const nextOffset = v[offset + 1];
40+
let x = diagonalIndex === -diffLevel || (diagonalIndex !== diffLevel && previousOffset < nextOffset) ?
41+
nextOffset :
42+
previousOffset + 1;
4643
let y = x - diagonalIndex;
4744

48-
while (x < actualLength && y < expectedLength && areLinesEqual(actual[x], expected[y], checkCommaDisparity)) {
45+
while (
46+
x < actualLength &&
47+
y < expectedLength &&
48+
areLinesEqual(actual[x], expected[y], checkCommaDisparity)
49+
) {
4950
x++;
5051
y++;
5152
}
5253

53-
v[diagonalIndex + max] = x;
54+
v[offset] = x;
5455

5556
if (x >= actualLength && y >= expectedLength) {
5657
return backtrack(trace, actual, expected, checkCommaDisparity);
@@ -71,10 +72,13 @@ function backtrack(trace, actual, expected, checkCommaDisparity) {
7172
for (let diffLevel = trace.length - 1; diffLevel >= 0; diffLevel--) {
7273
const v = trace[diffLevel];
7374
const diagonalIndex = x - y;
74-
let prevDiagonalIndex;
75+
const offset = diagonalIndex + max;
7576

76-
if (diagonalIndex === -diffLevel ||
77-
(diagonalIndex !== diffLevel && v[diagonalIndex - 1 + max] < v[diagonalIndex + 1 + max])) {
77+
let prevDiagonalIndex;
78+
if (
79+
diagonalIndex === -diffLevel ||
80+
(diagonalIndex !== diffLevel && v[offset - 1] < v[offset + 1])
81+
) {
7882
prevDiagonalIndex = diagonalIndex + 1;
7983
} else {
8084
prevDiagonalIndex = diagonalIndex - 1;
@@ -84,8 +88,11 @@ function backtrack(trace, actual, expected, checkCommaDisparity) {
8488
const prevY = prevX - prevDiagonalIndex;
8589

8690
while (x > prevX && y > prevY) {
87-
const value = !checkCommaDisparity ||
88-
StringPrototypeEndsWith(actual[x - 1], ',') ? actual[x - 1] : expected[y - 1];
91+
const actualItem = actual[x - 1];
92+
const value =
93+
!checkCommaDisparity || StringPrototypeEndsWith(actualItem, ',') ?
94+
actualItem :
95+
expected[y - 1];
8996
ArrayPrototypePush(result, { __proto__: null, type: 'nop', value });
9097
x--;
9198
y--;
@@ -110,13 +117,15 @@ function printSimpleMyersDiff(diff) {
110117

111118
for (let diffIdx = diff.length - 1; diffIdx >= 0; diffIdx--) {
112119
const { type, value } = diff[diffIdx];
120+
let color = colors.white;
121+
113122
if (type === 'insert') {
114-
message += `${colors.green}${value}${colors.white}`;
123+
color = colors.green;
115124
} else if (type === 'delete') {
116-
message += `${colors.red}${value}${colors.white}`;
117-
} else {
118-
message += `${colors.white}${value}${colors.white}`;
125+
color = colors.red;
119126
}
127+
128+
message += `${color}${value}${colors.white}`;
120129
}
121130

122131
return `\n${message}`;
@@ -129,17 +138,16 @@ function printMyersDiff(diff, operator) {
129138

130139
for (let diffIdx = diff.length - 1; diffIdx >= 0; diffIdx--) {
131140
const { type, value } = diff[diffIdx];
132-
const previousType = (diffIdx < (diff.length - 1)) ? diff[diffIdx + 1].type : null;
133-
const typeChanged = previousType && (type !== previousType);
141+
const previousType = diffIdx < diff.length - 1 ? diff[diffIdx + 1].type : null;
134142

135-
if (typeChanged && previousType === 'nop') {
136-
// Avoid grouping if only one line would have been grouped otherwise
143+
// Avoid grouping if only one line would have been grouped otherwise
144+
if (previousType === 'nop' && type !== previousType) {
137145
if (nopCount === kNopLinesToCollapse + 1) {
138146
message += `${colors.white} ${diff[diffIdx + 1].value}\n`;
139147
} else if (nopCount === kNopLinesToCollapse + 2) {
140148
message += `${colors.white} ${diff[diffIdx + 2].value}\n`;
141149
message += `${colors.white} ${diff[diffIdx + 1].value}\n`;
142-
} if (nopCount >= (kNopLinesToCollapse + 3)) {
150+
} else if (nopCount >= kNopLinesToCollapse + 3) {
143151
message += `${colors.blue}...${colors.white}\n`;
144152
message += `${colors.white} ${diff[diffIdx + 1].value}\n`;
145153
skipped = true;

0 commit comments

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