学习笔记：深入理解 JavaScript 中的循环引用检测

深入探讨如何检测 JavaScript 对象中的循环引用问题。

1. 问题背景：什么是循环引用？

循环引用（Circular Reference）指的是一个对象的属性，直接或间接地引用了自身或其任何一个父级对象。这种情况在处理复杂数据结构时需要特别注意。

常见场景：

• 直接引用：对象的一个属性直接指向自己。

  const obj = { a: 1 };
  obj.c = obj; // obj.c 引用了 obj 本身

• 间接引用：对象的深层嵌套属性引用了任意一个上层对象。

  const obj = { a: { b: 1 } };
  obj.a.e = obj; // obj.a.e 引用了顶层的 obj

• 非循环引用（但易混淆）：一个对象的两个不同属性引用了同一个子对象。这不属于循环引用。

  const obj = { a: { b: 1 } };
  obj.c = obj.a; // obj.c 和 obj.a 指向同一个对象，但没有形成向上引用

为什么需要检测循环引用？

如果不进行处理，在对这类对象进行深度遍历操作时（如深拷贝、JSON.stringify、Vue 的 watch 深度监听等），会陷入无限递归，最终导致程序崩溃并抛出 "Maximum call stack size exceeded" (栈溢出) 错误。

2. 核心思路：利用 "记忆" 来打破循环

要判断是否存在循环，关键在于在遍历对象的过程中"记住"我们已经访问过的父级对象。

如果在向下遍历时，遇到了一个我们"记忆"中已经存在的对象，那就证明出现了循环。

最适合用来实现这种"记忆"功能的数据结构是 Set，因为它具有两个关键特性：

1. 成员唯一：可以存储不重复的值，无论是原始值还是对象引用。
2. 高效查找：Set.prototype.has() 方法可以快速判断一个元素是否存在于 Set 中。

3. 实现方案的演进

版本一：朴素递归（错误示范）

最直观的想法是使用递归来遍历对象的所有属性。

// 错误示范：会导致栈溢出
function isCircular(target) {
  // 仅考虑对象
  if (typeof target !== 'object' || target === null) {
    return false;
  }

  for (const key in target) {
    // 递归检查子属性
    isCircular(target[key]); 
  }
  return false;
}

问题：当遇到循环引用时，isCircular(target[key]) 会无限调用自身，直到调用栈被耗尽。

版本二：共享"记忆袋"（有缺陷的尝试）

为了解决无限递归，我们引入一个 Set 来充当"记忆袋"，记录所有遍历过的对象。

// 缺陷版本
function isCircular(target, memory = new Set()) {
  if (typeof target !== 'object' || target === null) {
    return false;
  }

  // 检查：当前对象是否在"记忆袋"里？
  if (memory.has(target)) {
    return true; // 如果在，说明是循环引用
  }

  // 记忆：把当前对象放入"记忆袋"
  memory.add(target);

  for (const key in target) {
    if (isCircular(target[key], memory)) { // 把"记忆袋"传下去
      return true;
    }
  }
  return false;
}

这个版本能解决简单的循环引用问题，但存在一个缺陷。

缺陷分析：它会错误地将"同级重复引用"识别为"循环引用"。

const obj = { a: { value: 1 } };
obj.c = obj.a; // 这不是循环引用

isCircular(obj); // true (错误的结果)

原因：memory 这个 Set 在整个递归过程中是共享的。

1. 遍历 obj.a 时，obj.a 被加入 memory。
2. 遍历 obj.c 时，由于 obj.c 和 obj.a 指向同一个对象，memory.has(obj.c) 会返回 true，导致函数错误地判断为循环引用。

版本三：独立的"记忆路径"（正确实现）

正确的逻辑是，循环引用特指子级引用了其路径上的父级。兄弟节点之间共享对象不应被误判。

因此，我们需要为每一个遍历路径维护一个独立的"记忆"。

// 正确的版本
function isCircular(target, memory = new Set()) {
  if (typeof target !== 'object' || target === null) {
    return false;
  }

  if (memory.has(target)) {
    return true;
  }

  // 为当前路径创建一个新的、独立的"记忆"
  // new Set(memory) 创建了父级路径记忆的"快照"
  const newMemory = new Set(memory); 
  newMemory.add(target); // 将当前对象加入到"当前路径的记忆"中

  for (const key in target) {
    // 将新的、独立的记忆传递给下一次递归
    if (isCircular(target[key], newMemory)) {
      return true;
    }
  }

  return false;
}

工作流程解析：

1. 当 isCircular 被调用时，它会基于传入的 memory 创建一个副本 newMemory。
2. 它将当前 target 添加到这个副本 newMemory 中。
3. 在递归调用其子属性时，它传递的是这个副本 newMemory。
4. 这样，当遍历兄弟节点时（例如 obj.a 和 obj.c），它们各自的递归调用会从同一个父级的 memory 状态开始，但它们后续添加的记忆不会互相影响。只有当一个节点的子节点引用了该节点自身的父级链条上的对象时，才会被正确判定为循环。

4. 代码优化：函数式风格

我们可以使用 Object.values() 和 Array.prototype.some() 来让代码更加简洁和现代化。

Array.prototype.some() 方法测试数组中是否至少有一个元素能通过我们提供的函数测试。它会在找到第一个"真"值后立即停止遍历并返回 true，非常适合这个场景。

/**
 * 判断一个对象是否存在循环引用。
 * @param {object} target - 需要检查的目标对象。
 * @param {Set<object>} [memory=new Set()] - 用于在递归中记录父级路径上的对象。
 * @returns {boolean} - 如果存在循环引用，则返回 true，否则返回 false。
 */
function isCircular(target, memory = new Set()) {
  // 非对象类型不可能存在循环引用
  if (typeof target !== 'object' || target === null) {
    return false;
  }

  // 如果当前对象已经存在于父级路径中，则说明存在循环引用
  if (memory.has(target)) {
    return true;
  }

  // 为当前遍历路径创建一个新的记忆集合，并加入当前对象
  const pathMemory = new Set(memory);
  pathMemory.add(target);

  // 遍历对象的所有值（子节点）
  return Object.values(target).some(value => 
    // 对每一个值为对象的子节点进行递归检查
    // 如果任何一个子节点的检查结果为 true，some 方法会立即返回 true
    isCircular(value, pathMemory)
  );
}

// --- 测试 ---

// 1. 直接循环引用 -> true
const obj1 = { name: 'obj1' };
obj1.self = obj1;
console.log('直接循环引用:', isCircular(obj1)); // true

// 2. 间接循环引用 -> true
const obj2 = { a: { b: {} } };
obj2.a.b.parent = obj2;
console.log('间接循环引用:', isCircular(obj2)); // true

// 3. 同级重复引用（非循环） -> false
const obj3 = { child: { name: 'child' } };
obj3.c1 = obj3.child;
obj3.c2 = obj3.child;
console.log('同级重复引用:', isCircular(obj3)); // false

// 4. 无循环的普通对象 -> false
const obj4 = { a: 1, b: { c: 2 } };
console.log('普通对象:', isCircular(obj4)); // false

// 5. null 或非对象 -> false
console.log('null:', isCircular(null)); // false
console.log('原始值:', isCircular(123)); // false

5. 总结

• 核心问题：防止因循环引用导致的无限递归和栈溢出。
• 核心解法：在递归遍历时，记录下当前路径访问过的所有父级对象（使用 Set）。
• 关键技巧：为每个递归分支创建独立的路径记录 (new Set(parentMemory))，这是为了正确区分"循环引用"（子引用父）和"重复引用"（兄弟引用同一对象）。
• 代码优化：使用 Object.values().some() 可以写出更简洁、高效且意图明确的代码。