How Lodash isEqual Handles Cyclic Object Graphs

This article provides a concise overview of how the Lodash JavaScript library safely compares cyclic object graphs using its _.isEqual function. You will learn about the internal stack-tracking mechanism Lodash employs to detect circular references, how it avoids infinite recursion, and how it accurately determines structural equality between complex, self-referential data structures.

The Challenge of Cyclic References

A circular reference occurs when an object references itself directly or indirectly through a chain of properties. In a standard recursive deep-comparison implementation, traversing such an object causes an infinite loop, eventually terminating with a RangeError: Maximum call stack size exceeded.

const a = {};
a.self = a;

const b = {};
b.self = b;

// A naive recursive equality function would loop forever here.

To prevent this, an equality algorithm must keep track of references it has already encountered during traversal.

The Internal Stack Tracking Mechanism

Lodash solves the circular reference problem within its internal functions—primarily baseIsEqual and baseIsEqualDeep—by maintaining an internal state cache, historically implemented via paired arrays (stackA and stackB) or a custom Stack memoization class (leveraging Map where available).

When _.isEqual evaluates two objects, it follows these steps:

1. Cycle Detection via Stack Lookup

Before traversing the nested properties of an object, _.isEqual checks whether the current object pair has already been traversed. It searches its stack to see if the first object exists in the tracking cache. If found, it verifies whether the corresponding entry matches the second object.

• If both objects exist at matching positions in the stack history, Lodash recognizes that this path has already been entered and assumes equality for that specific reference edge (returning true). This breaks the cycle and prevents infinite recursion.
• If one object exists in the stack but the other does not match the historical pair, the objects have different cycle topologies, and the comparison resolves to false.

2. Pushing to the Stack

If the objects have not yet been evaluated, Lodash adds the current pair to the traversal stack. This registers them as "currently being inspected" for any downstream recursive calls.

3. Property Enumeration

Lodash iterates through the keys of both objects, recursively calling the comparison function on each corresponding pair of values. If any child property points back to a parent object higher up in the branch, the lookup step (Step 1) catches the reference and immediately returns true instead of recursing deeper.

4. Stack Cleanup (Unwinding)

Once all properties of the current object pair have been compared, Lodash pops them off the traversal stack. This ensures that the memory allocated for tracking paths is cleared and prevents false positives across sibling branches that are not part of the active traversal path.

Practical Example

Consider the following cyclic structures:

const _ = require('lodash');

// Object graph 1
const nodeA1 = { id: 1 };
const nodeA2 = { id: 2 };
nodeA1.next = nodeA2;
nodeA2.next = nodeA1; // Cycle

// Object graph 2 (identical structure, different references)
const nodeB1 = { id: 1 };
const nodeB2 = { id: 2 };
nodeB1.next = nodeB2;
nodeB2.next = nodeB1; // Cycle

console.log(_.isEqual(nodeA1, nodeB1)); // Returns: true

During this comparison:

1. Lodash pushes (nodeA1, nodeB1) onto the stack.
2. It compares nodeA1.id and nodeB1.id (both are 1).
3. It moves to nodeA1.next and nodeB1.next, pushing (nodeA2, nodeB2) onto the stack.
4. It compares nodeA2.id and nodeB2.id (both are 2).
5. It inspects nodeA2.next and nodeB2.next, which point back to nodeA1 and nodeB1.
6. Lodash inspects the stack, discovers that (nodeA1, nodeB1) is already being processed, and immediately resolves this reference check as true.
7. The recursion safely unwinds, and the top-level call returns true.

If one graph contains a cycle while the other terminates with null, the stack check fails to match the pair, and _.isEqual correctly returns false.