Skip to content

Commit dd43d30

Browse files
wraithgarwraithgar
committed
1 parent d5ce7ca commit dd43d30

6 files changed

Lines changed: 256 additions & 93 deletions

File tree

‎node_modules/just-diff/index.cjs‎

Lines changed: 118 additions & 39 deletions
Original file line numberDiff line numberDiff line change
@@ -79,18 +79,32 @@ function diff(obj1, obj2, pathConverter) {
7979
return arr;
8080
});
8181

82-
function getDiff(obj1, obj2, basePath, diffs) {
82+
// we will gather all permutations and return the one with the fewest diffs
83+
var permutations = [{remove: [], replace: [], add: []}];
84+
85+
function getDiff({obj1, obj2, basePath, basePathForRemoves, permutation}) {
8386
var obj1Keys = Object.keys(obj1);
8487
var obj1KeysLength = obj1Keys.length;
8588
var obj2Keys = Object.keys(obj2);
8689
var obj2KeysLength = obj2Keys.length;
8790
var path;
8891

92+
var newPermutation;
93+
94+
var lengthDelta = obj1.length - obj2.length;
95+
// if both objects are arrays and obj1 length > obj2 length
96+
// we create an additional permutation that trims obj1 from left
97+
if (Array.isArray(obj1) && Array.isArray(obj2) && lengthDelta > 0) {
98+
newPermutation = clonePermutation(permutation);
99+
permutations.push(newPermutation);
100+
}
101+
102+
// trim from right
89103
for (var i = 0; i < obj1KeysLength; i++) {
90104
var key = Array.isArray(obj1) ? Number(obj1Keys[i]) : obj1Keys[i];
91105
if (!(key in obj2)) {
92-
path = basePath.concat(key);
93-
diffs.remove.push({
106+
path = basePathForRemoves.concat(key);
107+
permutation.remove.push({
94108
op: 'remove',
95109
path: pathConverter(path),
96110
});
@@ -99,55 +113,120 @@ function diff(obj1, obj2, pathConverter) {
99113

100114
for (var i = 0; i < obj2KeysLength; i++) {
101115
var key = Array.isArray(obj2) ? Number(obj2Keys[i]) : obj2Keys[i];
102-
var obj1AtKey = obj1[key];
103-
var obj2AtKey = obj2[key];
104-
if (!(key in obj1)) {
105-
path = basePath.concat(key);
106-
var obj2Value = obj2[key];
107-
diffs.add.push({
108-
op: 'add',
116+
pushReplaces({
117+
key,
118+
obj1,
119+
obj2,
120+
path: basePath.concat(key),
121+
pathForRemoves: basePath.concat(key),
122+
permutation,
123+
});
124+
}
125+
126+
// if we created a new permutation above it means we should also try trimming from left
127+
if (newPermutation) {
128+
for (var i = 0; i < lengthDelta; i++) {
129+
path = basePathForRemoves.concat(i);
130+
newPermutation.remove.push({
131+
op: 'remove',
109132
path: pathConverter(path),
110-
value: obj2Value,
111133
});
112-
} else if (obj1AtKey !== obj2AtKey) {
113-
if (
114-
Object(obj1AtKey) !== obj1AtKey ||
115-
Object(obj2AtKey) !== obj2AtKey
116-
) {
117-
path = pushReplace(path, basePath, key, diffs, pathConverter, obj2);
118-
} else {
119-
if (
120-
!Object.keys(obj1AtKey).length &&
121-
!Object.keys(obj2AtKey).length &&
122-
String(obj1AtKey) != String(obj2AtKey)
123-
) {
124-
path = pushReplace(path, basePath, key, diffs, pathConverter, obj2);
125-
} else {
126-
getDiff(obj1[key], obj2[key], basePath.concat(key), diffs);
127-
}
128-
}
129134
}
130-
}
131135

132-
return diffs;
136+
// now make a copy of obj1 with excess elements left trimmed and see if there any replaces
137+
var obj1Trimmed = obj1.slice(lengthDelta);;
138+
for (var i = 0; i < obj2KeysLength; i++) {
139+
pushReplaces({
140+
key: i,
141+
obj1: obj1Trimmed,
142+
obj2,
143+
path: basePath.concat(i),
144+
// since list of removes are reversed before presenting result,
145+
// we need to ignore existing parent removes when doing nested removes
146+
pathForRemoves: basePath.concat(i + lengthDelta),
147+
permutation: newPermutation,
148+
});
149+
}
150+
}
133151
}
134-
const finalDiffs = getDiff(obj1, obj2, [], {remove: [], replace: [], add: []});
152+
153+
getDiff({
154+
obj1,
155+
obj2,
156+
basePath: [],
157+
basePathForRemoves: [],
158+
permutation: permutations[0],
159+
});
160+
161+
// find the shortest permutation
162+
var finalDiffs = permutations.sort(
163+
(a, b) => diffStepCount(a) > diffStepCount(b) ? 1 : -1
164+
)[0];
165+
166+
// reverse removes since we want to maintain indexes
135167
return finalDiffs.remove
136168
.reverse()
137169
.concat(finalDiffs.replace)
138170
.concat(finalDiffs.add);
171+
172+
function pushReplaces({key, obj1, obj2, path, pathForRemoves, permutation}) {
173+
var obj1AtKey = obj1[key];
174+
var obj2AtKey = obj2[key];
175+
176+
if(!(key in obj1) && obj2AtKey) {
177+
var obj2Value = obj2AtKey;
178+
permutation.add.push({
179+
op: 'add',
180+
path: pathConverter(path),
181+
value: obj2Value,
182+
});
183+
} else if(obj1AtKey !== obj2AtKey) {
184+
if(Object(obj1AtKey) !== obj1AtKey ||
185+
Object(obj2AtKey) !== obj2AtKey || differentTypes(obj1AtKey, obj2AtKey)
186+
) {
187+
pushReplace(path, permutation, obj2AtKey);
188+
} else {
189+
if(!Object.keys(obj1AtKey).length &&
190+
!Object.keys(obj2AtKey).length &&
191+
String(obj1AtKey) != String(obj2AtKey)) {
192+
pushReplace(path, permutation, obj2AtKey);
193+
} else {
194+
getDiff({
195+
obj1: obj1[key],
196+
obj2: obj2[key],
197+
basePath: path,
198+
basePathForRemoves: pathForRemoves,
199+
permutation});
200+
}
201+
}
202+
}
203+
}
204+
205+
function pushReplace(path, diffs, newValue) {
206+
diffs.replace.push({
207+
op: 'replace',
208+
path: pathConverter(path),
209+
value: newValue,
210+
});
211+
}
139212
}
140213

141-
function pushReplace(path, basePath, key, diffs, pathConverter, obj2) {
142-
path = basePath.concat(key);
143-
diffs.replace.push({
144-
op: 'replace',
145-
path: pathConverter(path),
146-
value: obj2[key],
147-
});
148-
return path;
214+
function clonePermutation(permutation) {
215+
return {
216+
remove: permutation.remove.slice(0),
217+
replace: permutation.replace.slice(0),
218+
add: permutation.add.slice(0),
219+
};
220+
}
221+
222+
function diffStepCount(permutation) {
223+
return permutation.remove.length + permutation.replace.length + permutation.add.length;
149224
}
150225

151226
function jsonPatchPathConverter(arrayPath) {
152227
return [''].concat(arrayPath).join('/');
153228
}
229+
230+
function differentTypes(a, b) {
231+
return Object.prototype.toString.call(a) != Object.prototype.toString.call(b);
232+
}

‎node_modules/just-diff/index.mjs‎

Lines changed: 117 additions & 39 deletions
Original file line numberDiff line numberDiff line change
@@ -74,18 +74,32 @@ function diff(obj1, obj2, pathConverter) {
7474
return arr;
7575
});
7676

77-
function getDiff(obj1, obj2, basePath, diffs) {
77+
// we will gather all permutations and return the one with the fewest diffs
78+
var permutations = [{remove: [], replace: [], add: []}];
79+
80+
function getDiff({obj1, obj2, basePath, basePathForRemoves, permutation}) {
7881
var obj1Keys = Object.keys(obj1);
7982
var obj1KeysLength = obj1Keys.length;
8083
var obj2Keys = Object.keys(obj2);
8184
var obj2KeysLength = obj2Keys.length;
8285
var path;
8386

87+
var newPermutation;
88+
89+
var lengthDelta = obj1.length - obj2.length;
90+
// if both objects are arrays and obj1 length > obj2 length
91+
// we create an additional permutation that trims obj1 from left
92+
if (Array.isArray(obj1) && Array.isArray(obj2) && lengthDelta > 0) {
93+
newPermutation = clonePermutation(permutation);
94+
permutations.push(newPermutation);
95+
}
96+
97+
// trim from right
8498
for (var i = 0; i < obj1KeysLength; i++) {
8599
var key = Array.isArray(obj1) ? Number(obj1Keys[i]) : obj1Keys[i];
86100
if (!(key in obj2)) {
87-
path = basePath.concat(key);
88-
diffs.remove.push({
101+
path = basePathForRemoves.concat(key);
102+
permutation.remove.push({
89103
op: 'remove',
90104
path: pathConverter(path),
91105
});
@@ -94,57 +108,121 @@ function diff(obj1, obj2, pathConverter) {
94108

95109
for (var i = 0; i < obj2KeysLength; i++) {
96110
var key = Array.isArray(obj2) ? Number(obj2Keys[i]) : obj2Keys[i];
97-
var obj1AtKey = obj1[key];
98-
var obj2AtKey = obj2[key];
99-
if (!(key in obj1)) {
100-
path = basePath.concat(key);
101-
var obj2Value = obj2[key];
102-
diffs.add.push({
103-
op: 'add',
111+
pushReplaces({
112+
key,
113+
obj1,
114+
obj2,
115+
path: basePath.concat(key),
116+
pathForRemoves: basePath.concat(key),
117+
permutation,
118+
});
119+
}
120+
121+
// if we created a new permutation above it means we should also try trimming from left
122+
if (newPermutation) {
123+
for (var i = 0; i < lengthDelta; i++) {
124+
path = basePathForRemoves.concat(i);
125+
newPermutation.remove.push({
126+
op: 'remove',
104127
path: pathConverter(path),
105-
value: obj2Value,
106128
});
107-
} else if (obj1AtKey !== obj2AtKey) {
108-
if (
109-
Object(obj1AtKey) !== obj1AtKey ||
110-
Object(obj2AtKey) !== obj2AtKey
111-
) {
112-
path = pushReplace(path, basePath, key, diffs, pathConverter, obj2);
113-
} else {
114-
if (
115-
!Object.keys(obj1AtKey).length &&
116-
!Object.keys(obj2AtKey).length &&
117-
String(obj1AtKey) != String(obj2AtKey)
118-
) {
119-
path = pushReplace(path, basePath, key, diffs, pathConverter, obj2);
120-
} else {
121-
getDiff(obj1[key], obj2[key], basePath.concat(key), diffs);
122-
}
123-
}
124129
}
125-
}
126130

127-
return diffs;
131+
// now make a copy of obj1 with excess elements left trimmed and see if there any replaces
132+
var obj1Trimmed = obj1.slice(lengthDelta); for (var i = 0; i < obj2KeysLength; i++) {
133+
pushReplaces({
134+
key: i,
135+
obj1: obj1Trimmed,
136+
obj2,
137+
path: basePath.concat(i),
138+
// since list of removes are reversed before presenting result,
139+
// we need to ignore existing parent removes when doing nested removes
140+
pathForRemoves: basePath.concat(i + lengthDelta),
141+
permutation: newPermutation,
142+
});
143+
}
144+
}
128145
}
129-
const finalDiffs = getDiff(obj1, obj2, [], {remove: [], replace: [], add: []});
146+
147+
getDiff({
148+
obj1,
149+
obj2,
150+
basePath: [],
151+
basePathForRemoves: [],
152+
permutation: permutations[0],
153+
});
154+
155+
// find the shortest permutation
156+
var finalDiffs = permutations.sort(
157+
(a, b) => diffStepCount(a) > diffStepCount(b) ? 1 : -1
158+
)[0];
159+
160+
// reverse removes since we want to maintain indexes
130161
return finalDiffs.remove
131162
.reverse()
132163
.concat(finalDiffs.replace)
133164
.concat(finalDiffs.add);
165+
166+
function pushReplaces({key, obj1, obj2, path, pathForRemoves, permutation}) {
167+
var obj1AtKey = obj1[key];
168+
var obj2AtKey = obj2[key];
169+
170+
if(!(key in obj1) && obj2AtKey) {
171+
var obj2Value = obj2AtKey;
172+
permutation.add.push({
173+
op: 'add',
174+
path: pathConverter(path),
175+
value: obj2Value,
176+
});
177+
} else if(obj1AtKey !== obj2AtKey) {
178+
if(Object(obj1AtKey) !== obj1AtKey ||
179+
Object(obj2AtKey) !== obj2AtKey || differentTypes(obj1AtKey, obj2AtKey)
180+
) {
181+
pushReplace(path, permutation, obj2AtKey);
182+
} else {
183+
if(!Object.keys(obj1AtKey).length &&
184+
!Object.keys(obj2AtKey).length &&
185+
String(obj1AtKey) != String(obj2AtKey)) {
186+
pushReplace(path, permutation, obj2AtKey);
187+
} else {
188+
getDiff({
189+
obj1: obj1[key],
190+
obj2: obj2[key],
191+
basePath: path,
192+
basePathForRemoves: pathForRemoves,
193+
permutation});
194+
}
195+
}
196+
}
197+
}
198+
199+
function pushReplace(path, diffs, newValue) {
200+
diffs.replace.push({
201+
op: 'replace',
202+
path: pathConverter(path),
203+
value: newValue,
204+
});
205+
}
134206
}
135207

136-
function pushReplace(path, basePath, key, diffs, pathConverter, obj2) {
137-
path = basePath.concat(key);
138-
diffs.replace.push({
139-
op: 'replace',
140-
path: pathConverter(path),
141-
value: obj2[key],
142-
});
143-
return path;
208+
function clonePermutation(permutation) {
209+
return {
210+
remove: permutation.remove.slice(0),
211+
replace: permutation.replace.slice(0),
212+
add: permutation.add.slice(0),
213+
};
214+
}
215+
216+
function diffStepCount(permutation) {
217+
return permutation.remove.length + permutation.replace.length + permutation.add.length;
144218
}
145219

146220
function jsonPatchPathConverter(arrayPath) {
147221
return [''].concat(arrayPath).join('/');
148222
}
149223

224+
function differentTypes(a, b) {
225+
return Object.prototype.toString.call(a) != Object.prototype.toString.call(b);
226+
}
227+
150228
export {diff, jsonPatchPathConverter};

‎node_modules/just-diff/package.json‎

Lines changed: 1 addition & 1 deletion
Original file line numberDiff line numberDiff line change
@@ -1,6 +1,6 @@
11
{
22
"name": "just-diff",
3-
"version": "5.2.0",
3+
"version": "6.0.0",
44
"description": "Return an object representing the diffs between two objects. Supports jsonPatch protocol",
55
"type": "module",
66
"exports": {

0 commit comments

Comments
 (0)