How Lodash isEqual Handles Cyclic References

Lodash’s _.isEqual performs deep value comparisons across complex data structures while avoiding infinite recursion and call stack exhaustion on cyclic graphs. It accomplishes this by tracking active object pairs using an internal stack memoization mechanism, short-circuiting redundant traversals whenever an already-visited reference cycle is detected.

The Internal Architecture: baseIsEqual and Stack

When _.isEqual(value, other) is invoked, it delegates the comparison to internal functions: baseIsEqual and baseIsEqualDeep. To handle deeply nested objects and cycles without overflowing the JavaScript runtime call stack, Lodash initializes an internal Stack cache (typically backed by Map or a dual-array fallback for older engines).

This Stack instance is passed down as an argument through every recursive branch of the comparison.

Step-by-Step Cycle Detection and Bypass

When traversing non-primitive objects, Lodash applies the following sequence:

  1. Stack Lookup: Before inspecting properties or prototype chains, Lodash queries the Stack using stack.get(value).
  2. Cycle Resolution: If value is found in the stack, Lodash checks if its associated value matches other.
    • If stack.get(value) === other, a cycle is confirmed where both graph nodes loop back to previously evaluated counterparts. Lodash immediately returns true for this branch, breaking the loop.
    • If value is present but paired with a different node, it returns false, terminating the invalid branch early.
  3. Registering the Pair: If the pair has not been visited, Lodash registers it using stack.set(value, other) before diving into the object's keys, entries, or array indices.
  4. Recursive Traversal: Lodash proceeds to recursively compare each key/property pair, passing the updated Stack reference to all child calls.
  5. Stack Lifecycle: The Stack preserves the ancestor traversal path for the lifetime of that specific evaluation tree, guaranteeing that circular references along any path terminate in \(O(1)\) operations once re-encountered.

Why This Prevents Call Stack Overflow

A standard recursive traversal creates a new execution context on the JavaScript call stack for every nested property. In a cyclic graph (e.g., a.self = a), this leads to an infinite chain of nested calls, eventually throwing a RangeError: Maximum call stack size exceeded.

By intercepting the traversal at step 2, Lodash prevents the invocation of any further recursive frames for an already-active node pair. The maximum depth of the JavaScript call stack is strictly bounded by the number of unique, non-repeating object references along any single branch, effectively flattening the infinite loop into a finite graph traversal.