Skip to content

Commit a6e23ae

Browse files
jgonggrijpjgonggrijp
committed
Make _.isEqual nonrecursive
1 parent f2b5164 commit a6e23ae

7 files changed

Lines changed: 481 additions & 385 deletions

‎modules/isEqual.js‎

Lines changed: 118 additions & 94 deletions
Original file line numberDiff line numberDiff line change
@@ -12,127 +12,151 @@ import toBufferView from './_toBufferView.js';
1212
// We use this string twice, so give it a name for minification.
1313
var tagDataView = '[object DataView]';
1414

15-
// Internal recursive comparison function for `_.isEqual`.
16-
function eq(a, b, aStack, bStack) {
17-
// Identical objects are equal. `0 === -0`, but they aren't identical.
18-
// See the [Harmony `egal` proposal](https://wiki.ecmascript.org/doku.php?id=harmony:egal).
19-
if (a === b) return a !== 0 || 1 / a === 1 / b;
20-
// `null` or `undefined` only equal to itself (strict comparison).
21-
if (a == null || b == null) return false;
22-
// `NaN`s are equivalent, but non-reflexive.
23-
if (a !== a) return b !== b;
24-
// Exhaust primitive checks
25-
var type = typeof a;
26-
if (type !== 'function' && type !== 'object' && typeof b != 'object') return false;
27-
return deepEq(a, b, aStack, bStack);
28-
}
15+
// Perform a deep comparison to check if two objects are equal.
16+
export default function isEqual(a, b) {
17+
// Keep track of which pairs of values need to be compared. We will be
18+
// trampolining on this stack instead of using function recursion.
19+
var todo = [{a: a, b: b}];
20+
// Initializing stacks of traversed objects for cycle detection.
21+
var aStack = [], bStack = [];
2922

30-
// Internal recursive comparison function for `_.isEqual`.
31-
function deepEq(a, b, aStack, bStack) {
32-
// Unwrap any wrapped objects.
33-
if (a instanceof _) a = a._wrapped;
34-
if (b instanceof _) b = b._wrapped;
35-
// Compare `[[Class]]` names.
36-
var className = toString.call(a);
37-
if (className !== toString.call(b)) return false;
38-
// Work around a bug in IE 10 - Edge 13.
39-
if (hasDataViewBug && className == '[object Object]' && isDataView(a)) {
40-
if (!isDataView(b)) return false;
41-
className = tagDataView;
42-
}
43-
switch (className) {
44-
// These types are compared by value.
23+
// Keep traversing pairs until there is nothing left to compare.
24+
while (todo.length) {
25+
var frame = todo.pop();
26+
// As a special case, a single `true` on the todo means that we can
27+
// unwind the cycle detection stacks.
28+
if (frame === true) {
29+
// Remove the first object from the stack of traversed objects.
30+
aStack.pop();
31+
bStack.pop();
32+
continue;
33+
}
34+
a = frame.a;
35+
b = frame.b;
36+
37+
// Identical objects are equal. `0 === -0`, but they aren't identical.
38+
// See the [Harmony `egal` proposal](https://wiki.ecmascript.org/doku.php?id=harmony:egal).
39+
if (a === b) {
40+
if (a !== 0 || 1 / a === 1 / b) continue;
41+
return false;
42+
}
43+
// `null` or `undefined` only equal to itself (strict comparison).
44+
if (a == null || b == null) return false;
45+
// `NaN`s are equivalent, but non-reflexive.
46+
if (a !== a) {
47+
if (b !== b) continue;
48+
return false;
49+
}
50+
// Exhaust primitive checks
51+
var type = typeof a;
52+
if (type !== 'function' && type !== 'object' && typeof b != 'object') return false;
53+
54+
// Unwrap any wrapped objects.
55+
if (a instanceof _) a = a._wrapped;
56+
if (b instanceof _) b = b._wrapped;
57+
// Compare `[[Class]]` names.
58+
var className = toString.call(a);
59+
if (className !== toString.call(b)) return false;
60+
// Work around a bug in IE 10 - Edge 13.
61+
if (hasDataViewBug && className == '[object Object]' && isDataView(a)) {
62+
if (!isDataView(b)) return false;
63+
className = tagDataView;
64+
}
65+
switch (className) {
66+
// These types are compared by value.
4567
case '[object RegExp]':
4668
// RegExps are coerced to strings for comparison (Note: '' + /a/i === '/a/i')
4769
case '[object String]':
4870
// Primitives and their corresponding object wrappers are equivalent; thus, `"5"` is
4971
// equivalent to `new String("5")`.
50-
return '' + a === '' + b;
72+
if ('' + a === '' + b) continue;
73+
return false;
5174
case '[object Number]':
52-
// `NaN`s are equivalent, but non-reflexive.
53-
// Object(NaN) is equivalent to NaN.
54-
if (+a !== +a) return +b !== +b;
55-
// An `egal` comparison is performed for other numeric values.
56-
return +a === 0 ? 1 / +a === 1 / b : +a === +b;
75+
todo.push({a: +a, b: +b});
76+
continue;
5777
case '[object Date]':
5878
case '[object Boolean]':
5979
// Coerce dates and booleans to numeric primitive values. Dates are compared by their
6080
// millisecond representations. Note that invalid dates with millisecond representations
6181
// of `NaN` are not equivalent.
62-
return +a === +b;
82+
if (+a === +b) continue;
83+
return false;
6384
case '[object Symbol]':
64-
return SymbolProto.valueOf.call(a) === SymbolProto.valueOf.call(b);
85+
if (SymbolProto.valueOf.call(a) === SymbolProto.valueOf.call(b)) continue;
86+
return false;
6587
case '[object ArrayBuffer]':
6688
case tagDataView:
6789
// Coerce to typed array so we can fall through.
68-
return deepEq(toBufferView(a), toBufferView(b), aStack, bStack);
69-
}
90+
todo.push({a: toBufferView(a), b: toBufferView(b)});
91+
continue;
92+
}
7093

71-
var areArrays = className === '[object Array]';
72-
if (!areArrays && isTypedArray(a)) {
94+
var areArrays = className === '[object Array]';
95+
if (!areArrays && isTypedArray(a)) {
7396
var byteLength = getByteLength(a);
7497
if (byteLength !== getByteLength(b)) return false;
75-
if (a.buffer === b.buffer && a.byteOffset === b.byteOffset) return true;
98+
if (a.buffer === b.buffer && a.byteOffset === b.byteOffset) continue;
7699
areArrays = true;
77-
}
78-
if (!areArrays) {
79-
if (typeof a != 'object' || typeof b != 'object') return false;
80-
81-
// Objects with different constructors are not equivalent, but `Object`s or `Array`s
82-
// from different frames are.
83-
var aCtor = a.constructor, bCtor = b.constructor;
84-
if (aCtor !== bCtor && !(isFunction(aCtor) && aCtor instanceof aCtor &&
85-
isFunction(bCtor) && bCtor instanceof bCtor)
86-
&& ('constructor' in a && 'constructor' in b)) {
87-
return false;
88100
}
89-
}
90-
// Assume equality for cyclic structures. The algorithm for detecting cyclic
91-
// structures is adapted from ES 5.1 section 15.12.3, abstract operation `JO`.
101+
if (!areArrays) {
102+
if (typeof a != 'object' || typeof b != 'object') return false;
92103

93-
// Initializing stack of traversed objects.
94-
// It's done here since we only need them for objects and arrays comparison.
95-
aStack = aStack || [];
96-
bStack = bStack || [];
97-
var length = aStack.length;
98-
while (length--) {
99-
// Linear search. Performance is inversely proportional to the number of
100-
// unique nested structures.
101-
if (aStack[length] === a) return bStack[length] === b;
102-
}
104+
// Objects with different constructors are not equivalent, but `Object`s or `Array`s
105+
// from different frames are.
106+
var aCtor = a.constructor, bCtor = b.constructor;
107+
if (aCtor !== bCtor && !(isFunction(aCtor) && aCtor instanceof aCtor &&
108+
isFunction(bCtor) && bCtor instanceof bCtor)
109+
&& ('constructor' in a && 'constructor' in b)) {
110+
return false;
111+
}
112+
}
103113

104-
// Add the first object to the stack of traversed objects.
105-
aStack.push(a);
106-
bStack.push(b);
114+
// Assume equality for cyclic structures. The algorithm for detecting cyclic
115+
// structures is adapted from ES 5.1 section 15.12.3, abstract operation `JO`.
107116

108-
// Recursively compare objects and arrays.
109-
if (areArrays) {
110-
// Compare array lengths to determine if a deep comparison is necessary.
111-
length = a.length;
112-
if (length !== b.length) return false;
113-
// Deep compare the contents, ignoring non-numeric properties.
117+
var length = aStack.length;
114118
while (length--) {
115-
if (!eq(a[length], b[length], aStack, bStack)) return false;
119+
// Linear search. Performance is inversely proportional to the number of
120+
// unique nested structures.
121+
if (aStack[length] === a) {
122+
// Cycle detected. Break out of the inner loop and continue the outer
123+
// loop. Step 1:
124+
if (bStack[length] === b) break;
125+
return false;
126+
}
116127
}
117-
} else {
118-
// Deep compare objects.
119-
var _keys = keys(a), key;
120-
length = _keys.length;
121-
// Ensure that both objects contain the same number of properties before comparing deep equality.
122-
if (keys(b).length !== length) return false;
123-
while (length--) {
124-
// Deep compare each member
125-
key = _keys[length];
126-
if (!(has(b, key) && eq(a[key], b[key], aStack, bStack))) return false;
128+
// Step 2, use `length` to verify whether we detected a cycle:
129+
if (length >= 0) continue;
130+
131+
// Add the first object to the stack of traversed objects.
132+
aStack.push(a);
133+
bStack.push(b);
134+
// Remember to remove them again after the recursion below.
135+
todo.push(true);
136+
137+
// Recursively compare objects and arrays.
138+
if (areArrays) {
139+
// Compare array lengths to determine if a deep comparison is necessary.
140+
length = a.length;
141+
if (length !== b.length) return false;
142+
// Deep compare the contents, ignoring non-numeric properties.
143+
while (length--) {
144+
todo.push({a: a[length], b: b[length]});
145+
}
146+
} else {
147+
// Deep compare objects.
148+
var _keys = keys(a), key;
149+
length = _keys.length;
150+
// Ensure that both objects contain the same number of properties before comparing deep equality.
151+
if (keys(b).length !== length) return false;
152+
while (length--) {
153+
// Deep compare each member
154+
key = _keys[length];
155+
if (!has(b, key)) return false;
156+
todo.push({a: a[key], b: b[key]});
157+
}
127158
}
128159
}
129-
// Remove the first object from the stack of traversed objects.
130-
aStack.pop();
131-
bStack.pop();
160+
// We made it to the end and found no differences.
132161
return true;
133162
}
134-
135-
// Perform a deep comparison to check if two objects are equal.
136-
export default function isEqual(a, b) {
137-
return eq(a, b);
138-
}

0 commit comments

Comments
 (0)