检测和修复 JavaScript 中的循环引用

Detecting and fixing circular references in JavaScript

提问by Mads Mob?k

Given I have a circular reference in a large JavaScript object

鉴于我在一个大型 JavaScript 对象中有一个循环引用

And I try JSON.stringify(problematicObject)

我尝试 JSON.stringify(problematicObject)

And the browser throws

浏览器抛出

"TypeError: Converting circular structure to JSON"

“类型错误：将圆形结构转换为 JSON”

(which is expected)

（这是预期的）

Then I want to find the cause of this circular reference, preferably using Chrome developer tools? Is this possible? How do you find and fix circular references in a large object?

那我想找到这个循环引用的原因，最好使用Chrome开发者工具？这可能吗？如何在大对象中查找和修复循环引用？

回答by Trey Mack

Pulled from http://blog.vjeux.com/2011/javascript/cyclic-object-detection.html. One line added to detect where the cycle is. Paste this into the Chrome dev tools:

摘自http://blog.vjeux.com/2011/javascript/cyclic-object-detection.html。添加了一行以检测循环的位置。将其粘贴到 Chrome 开发工具中：

function isCyclic (obj) {
  var seenObjects = [];

  function detect (obj) {
    if (obj && typeof obj === 'object') {
      if (seenObjects.indexOf(obj) !== -1) {
        return true;
      }
      seenObjects.push(obj);
      for (var key in obj) {
        if (obj.hasOwnProperty(key) && detect(obj[key])) {
          console.log(obj, 'cycle at ' + key);
          return true;
        }
      }
    }
    return false;
  }

  return detect(obj);
}

Here's the test:

这是测试：

> a = {}
> b = {}
> a.b = b; b.a = a;
> isCyclic(a)
  Object {a: Object}
   "cycle at a"
  Object {b: Object}
   "cycle at b"
  true

回答by Aaron V

@tmack's answer is definitely what I was looking for when I found this question!

@tmack 的答案绝对是我发现这个问题时所寻找的！

Unfortunately it returns many false positives - it returns true if an object is replicated in the JSON, which isn't the sameas circularity. Circularity means that an object is its own child, e.g.

不幸的是，它返回许多误报 - 如果对象在 JSON 中复制，则返回 true，这与循环性不同。循环意味着一个对象是它自己的孩子，例如

obj.key1.key2.[...].keyX === obj

I modified the original answer, and this is working for me:

我修改了原始答案，这对我有用：

function isCyclic(obj) {
  var keys = [];
  var stack = [];
  var stackSet = new Set();
  var detected = false;

  function detect(obj, key) {
    if (obj && typeof obj != 'object') { return; }

    if (stackSet.has(obj)) { // it's cyclic! Print the object and its locations.
      var oldindex = stack.indexOf(obj);
      var l1 = keys.join('.') + '.' + key;
      var l2 = keys.slice(0, oldindex + 1).join('.');
      console.log('CIRCULAR: ' + l1 + ' = ' + l2 + ' = ' + obj);
      console.log(obj);
      detected = true;
      return;
    }

    keys.push(key);
    stack.push(obj);
    stackSet.add(obj);
    for (var k in obj) { //dive on the object's children
      if (Object.prototype.hasOwnProperty.call(obj, k)) { detect(obj[k], k); }
    }

    keys.pop();
    stack.pop();
    stackSet.delete(obj);
    return;
  }

  detect(obj, 'obj');
  return detected;
}

Here are a few very simple tests:

下面是一些非常简单的测试：

var root = {}
var leaf = {'isleaf':true};
var cycle2 = {l:leaf};
var cycle1 = {c2: cycle2, l:leaf};
cycle2.c1 = cycle1
root.leaf = leaf

isCyclic(cycle1); // returns true, logs "CIRCULAR: obj.c2.c1 = obj"
isCyclic(cycle2); // returns true, logs "CIRCULAR: obj.c1.c2 = obj"
isCyclic(leaf); // returns false
isCyclic(root); // returns false

回答by Aaron V

This is a fix for both @Trey Mackand @Freddie Nfbnmanswers on the typeof obj != 'object'condition. Instead it should test if the objvalue is not instance of object, so that it can also work when checking values with object familiarity (for example, functions and symbols(symbols aren't instance of object, but still addressed, btw.)).

这是对@Trey Mack和@Freddie Nfbnm在typeof obj != 'object'条件下回答的修复。相反，它应该测试obj值是否不是对象的实例，以便在检查具有对象熟悉度的值时它也可以工作（例如，函数和符号（符号不是对象的实例，但仍然被寻址，顺便说一句））。

I'm posting this as an answer since I can't comment in this StackExchange account yet.

我将此作为答案发布，因为我还无法在此 StackExchange 帐户中发表评论。

PS.: feel free to request me to delete this answer.

PS.：请随时要求我删除此答案。

function isCyclic(obj) {
  var keys = [];
  var stack = [];
  var stackSet = new Set();
  var detected = false;

  function detect(obj, key) {
    if (!(obj instanceof Object)) { return; } // Now works with other
                                              // kinds of object.

    if (stackSet.has(obj)) { // it's cyclic! Print the object and its locations.
      var oldindex = stack.indexOf(obj);
      var l1 = keys.join('.') + '.' + key;
      var l2 = keys.slice(0, oldindex + 1).join('.');
      console.log('CIRCULAR: ' + l1 + ' = ' + l2 + ' = ' + obj);
      console.log(obj);
      detected = true;
      return;
    }

    keys.push(key);
    stack.push(obj);
    stackSet.add(obj);
    for (var k in obj) { //dive on the object's children
      if (obj.hasOwnProperty(k)) { detect(obj[k], k); }
    }

    keys.pop();
    stack.pop();
    stackSet.delete(obj);
    return;
  }

  detect(obj, 'obj');
  return detected;
}

回答by Thomas

CircularReferenceDetector

循环参考检测器

Here is my CircularReferenceDetectorclass which outputs all the property stack information where the circularly referenced value is actually located at and also shows where the culprit references are.

这是我的CircularReferenceDetector类，它输出循环引用值实际所在的所有属性堆栈信息，还显示了罪魁祸首引用的位置。

This is especially useful for huge structures where it is not obvious by the key which value is the source of the harm.

这对于巨大的结构特别有用，其中关键是哪个值是损害的来源并不明显。

It outputs the circularly referenced value stringified but all references to itself replaced by "[Circular object --- fix me]".

它输出字符串化的循环引用值，但对自身的所有引用都替换为“[循环对象 --- 修复我]”。

Usage:
CircularReferenceDetector.detectCircularReferences(value);

用法：
CircularReferenceDetector.detectCircularReferences(value);

Note:Remove the Logger.* statements if you do not want to use any logging or do not have a logger available.

注意：如果您不想使用任何日志记录或没有可用的记录器，请删除 Logger.* 语句。

Technical Explanation:
The recursive function goes through all properties of the object and tests if JSON.stringify succeeds on them or not. If it does not succeed (circular reference), then it tests if it succeeds by replacing value itself with some constant string. This would mean that if it succeeds using this replacer, this value is the being circularly referenced value. If it is not, it recursively goes through all properties of that object.

技术说明：
递归函数遍历对象的所有属性并测试 JSON.stringify 是否成功。如果它不成功（循环引用），则它通过用某个常量字符串替换 value 本身来测试它是否成功。这意味着如果它成功使用这个替换器，这个值就是被循环引用的值。如果不是，它将递归遍历该对象的所有属性。

Meanwhile it also tracks the property stack to give you information where the culprit value is located at.

同时，它还跟踪属性堆栈，为您提供罪魁祸首值所在的信息。

Typescript

打字稿

import {Logger} from "../Logger";

export class CircularReferenceDetector {

    static detectCircularReferences(toBeStringifiedValue: any, serializationKeyStack: string[] = []) {
        Object.keys(toBeStringifiedValue).forEach(key => {
            var value = toBeStringifiedValue[key];

            var serializationKeyStackWithNewKey = serializationKeyStack.slice();
            serializationKeyStackWithNewKey.push(key);
            try {
                JSON.stringify(value);
                Logger.debug(`path "${Util.joinStrings(serializationKeyStack)}" is ok`);
            } catch (error) {
                Logger.debug(`path "${Util.joinStrings(serializationKeyStack)}" JSON.stringify results in error: ${error}`);

                var isCircularValue:boolean;
                var circularExcludingStringifyResult:string = "";
                try {
                    circularExcludingStringifyResult = JSON.stringify(value, CircularReferenceDetector.replaceRootStringifyReplacer(value), 2);
                    isCircularValue = true;
                } catch (error) {
                    Logger.debug(`path "${Util.joinStrings(serializationKeyStack)}" is not the circular source`);
                    CircularReferenceDetector.detectCircularReferences(value, serializationKeyStackWithNewKey);
                    isCircularValue = false;
                }
                if (isCircularValue) {
                    throw new Error(`Circular reference detected:\nCircularly referenced value is value under path "${Util.joinStrings(serializationKeyStackWithNewKey)}" of the given root object\n`+
                        `Calling stringify on this value but replacing itself with [Circular object --- fix me] ( <-- search for this string) results in:\n${circularExcludingStringifyResult}\n`);
                }
            }
        });
    }

    private static replaceRootStringifyReplacer(toBeStringifiedValue: any): any {
        var serializedObjectCounter = 0;

        return function (key: any, value: any) {
            if (serializedObjectCounter !== 0 && typeof(toBeStringifiedValue) === 'object' && toBeStringifiedValue === value) {
                Logger.error(`object serialization with key ${key} has circular reference to being stringified object`);
                return '[Circular object --- fix me]';
            }

            serializedObjectCounter++;

            return value;
        }
    }
}

export class Util {

    static joinStrings(arr: string[], separator: string = ":") {
        if (arr.length === 0) return "";
        return arr.reduce((v1, v2) => `${v1}${separator}${v2}`);
    }

}

Compiled JavaScript from TypeScript

从 TypeScript 编译的 JavaScript

"use strict";
const Logger_1 = require("../Logger");
class CircularReferenceDetector {
    static detectCircularReferences(toBeStringifiedValue, serializationKeyStack = []) {
        Object.keys(toBeStringifiedValue).forEach(key => {
            var value = toBeStringifiedValue[key];
            var serializationKeyStackWithNewKey = serializationKeyStack.slice();
            serializationKeyStackWithNewKey.push(key);
            try {
                JSON.stringify(value);
                Logger_1.Logger.debug(`path "${Util.joinStrings(serializationKeyStack)}" is ok`);
            }
            catch (error) {
                Logger_1.Logger.debug(`path "${Util.joinStrings(serializationKeyStack)}" JSON.stringify results in error: ${error}`);
                var isCircularValue;
                var circularExcludingStringifyResult = "";
                try {
                    circularExcludingStringifyResult = JSON.stringify(value, CircularReferenceDetector.replaceRootStringifyReplacer(value), 2);
                    isCircularValue = true;
                }
                catch (error) {
                    Logger_1.Logger.debug(`path "${Util.joinStrings(serializationKeyStack)}" is not the circular source`);
                    CircularReferenceDetector.detectCircularReferences(value, serializationKeyStackWithNewKey);
                    isCircularValue = false;
                }
                if (isCircularValue) {
                    throw new Error(`Circular reference detected:\nCircularly referenced value is value under path "${Util.joinStrings(serializationKeyStackWithNewKey)}" of the given root object\n` +
                        `Calling stringify on this value but replacing itself with [Circular object --- fix me] ( <-- search for this string) results in:\n${circularExcludingStringifyResult}\n`);
                }
            }
        });
    }
    static replaceRootStringifyReplacer(toBeStringifiedValue) {
        var serializedObjectCounter = 0;
        return function (key, value) {
            if (serializedObjectCounter !== 0 && typeof (toBeStringifiedValue) === 'object' && toBeStringifiedValue === value) {
                Logger_1.Logger.error(`object serialization with key ${key} has circular reference to being stringified object`);
                return '[Circular object --- fix me]';
            }
            serializedObjectCounter++;
            return value;
        };
    }
}
exports.CircularReferenceDetector = CircularReferenceDetector;
class Util {
    static joinStrings(arr, separator = ":") {
        if (arr.length === 0)
            return "";
        return arr.reduce((v1, v2) => `${v1}${separator}${v2}`);
    }
}
exports.Util = Util;

回答by dkurzaj

Here is a Node ES6 version mixed from the answers from @Aaron Vand @user4976005, it fixes the problem with the call to hasOwnProperty:

这是一个从@Aaron V和@user4976005的答案混合而成的 Node ES6 版本，它解决了调用 hasOwnProperty 的问题：

const isCyclic = (obj => {
  const keys = []
  const stack = []
  const stackSet = new Set()
  let detected = false

  const detect = ((object, key) => {
    if (!(object instanceof Object))
      return

    if (stackSet.has(object)) { // it's cyclic! Print the object and its locations.
      const oldindex = stack.indexOf(object)
      const l1 = `${keys.join('.')}.${key}`
      const l2 = keys.slice(0, oldindex + 1).join('.')
      console.log(`CIRCULAR: ${l1} = ${l2} = ${object}`)
      console.log(object)
      detected = true
      return
    }

    keys.push(key)
    stack.push(object)
    stackSet.add(object)
    Object.keys(object).forEach(k => { // dive on the object's children
      if (k && Object.prototype.hasOwnProperty.call(object, k))
        detect(object[k], k)
    })

    keys.pop()
    stack.pop()
    stackSet.delete(object)
  })

  detect(obj, 'obj')
  return detected
})

回答by darksinge

There's a lot of answers here, but I thought I'd add my solution to the mix. It's similar to @Trey Mack's answer, but that solution takes O(n^2). This version uses WeakMapinstead of an array, improving the time to O(n).

这里有很多答案，但我想我会将我的解决方案添加到组合中。它类似于@Trey Mack的答案，但该解决方案需要 O(n^2)。此版本使用WeakMap而不是数组，将时间缩短到 O(n)。

function isCyclic(object) {
   const seenObjects = new WeakMap(); // use to keep track of which objects have been seen.

   function detectCycle(obj) {
      // If 'obj' is an actual object (i.e., has the form of '{}'), check
      // if it's been seen already.
      if (Object.prototype.toString.call(obj) == '[object Object]') {

         if (seenObjects.has(obj)) {
            return true;
         }

         // If 'obj' hasn't been seen, add it to 'seenObjects'.
         // Since 'obj' is used as a key, the value of 'seenObjects[obj]'
         // is irrelevent and can be set as literally anything you want. I 
         // just went with 'undefined'.
         seenObjects.set(obj, undefined);

         // Recurse through the object, looking for more circular references.
         for (var key in obj) {
            if (detectCycle(obj[key])) {
               return true;
            }
         }

      // If 'obj' is an array, check if any of it's elements are
      // an object that has been seen already.
      } else if (Array.isArray(obj)) {
         for (var i in obj) {
            if (detectCycle(obj[i])) {
               return true;
            }
         }
      }

      return false;
   }

   return detectCycle(object);
}

And this is what it looks like in action.

这就是它在行动中的样子。

> var foo = {grault: {}};
> detectCycle(foo);
false
> foo.grault = foo;
> detectCycle(foo);
true
> var bar = {};
> detectCycle(bar);
false
> bar.plugh = [];
> bar.plugh.push(bar);
> detectCycle(bar);
true

回答by gurvinder372

You can also use JSON.stringifywith try/catch

您也可以JSON.stringify与try/catch 一起使用

function hasCircularDependency(obj)
{
    try
    {
        JSON.stringify(obj);
    }
    catch(e)
    {
        return e.includes("Converting circular structure to JSON"); 
    }
    return false;
}

Demo

演示

function hasCircularDependency(obj) {
  try {
    JSON.stringify(obj);
  } catch (e) {
    return String(e).includes("Converting circular structure to JSON");
  }
  return false;
}

var a = {b:{c:{d:""}}};
console.log(hasCircularDependency(a));
a.b.c.d = a;
console.log(hasCircularDependency(a));

回答by Mattb150

Here is MDN's approach to detecting and fixing circular references when using JSON.stringify()on circular objects: https://developer.mozilla.org/en-US/docs/Web/JavaScript/Reference/Errors/Cyclic_object_value:

以下是 MDNJSON.stringify()在循环对象上使用时检测和修复循环引用的方法：https: //developer.mozilla.org/en-US/docs/Web/JavaScript/Reference/Errors/Cyclic_object_value：

In a circular structure like the following

在如下所示的圆形结构中

var circularReference = {otherData: 123};
circularReference.myself = circularReference;

JSON.stringify()will fail:

JSON.stringify()将失败：

JSON.stringify(circularReference);
// TypeError: cyclic object value

To serialize circular references you can use a library that supports them (e.g. cycle.js) or implement a solution by yourself, which will require finding and replacing (or removing) the cyclic references by serializable values.

The snippet below illustrates how to find and filter (thus causing data loss) a cyclic reference by using the replacer parameter of JSON.stringify():

要序列化循环引用，您可以使用支持它们的库（例如cycle.js）或自己实现解决方案，这将需要通过可序列化值查找和替换（或删除）循环引用。

下面的代码片段说明了如何使用的替换器参数查找和过滤（从而导致数据丢失）循环引用：JSON.stringify()

const getCircularReplacer = () => {
      const seen = new WeakSet();
      return (key, value) => {
        if (typeof value === "object" && value !== null) {
          if (seen.has(value)) {
            return;
          }
          seen.add(value);
        }
        return value;
      };
    };

JSON.stringify(circularReference, getCircularReplacer());
// {"otherData":123}

回答by SzybkiSasza

You can also use Symbols - thanks to that approach you won't have to mutate properties of the original object, apart from adding symbol for marking visited node.

您还可以使用符号 - 由于这种方法，除了添加用于标记访问节点的符号之外，您不必改变原始对象的属性。

It's cleaner and should be faster than gathering node properties and comparing with the object. It also has optional depth limitation if you don't want to serialize big nested values:

它更干净，应该比收集节点属性并与对象进行比较更快。如果您不想序列化大嵌套值，它还具有可选的深度限制：

// Symbol used to mark already visited nodes - helps with circular dependencies
const visitedMark = Symbol('VISITED_MARK');

const MAX_CLEANUP_DEPTH = 10;

function removeCirculars(obj, depth = 0) {
  if (!obj) {
    return obj;
  }

  // Skip condition - either object is falsy, was visited or we go too deep
  const shouldSkip = !obj || obj[visitedMark] || depth > MAX_CLEANUP_DEPTH;

  // Copy object (we copy properties from it and mark visited nodes)
  const originalObj = obj;
  let result = {};

  Object.keys(originalObj).forEach((entry) => {
    const val = originalObj[entry];

    if (!shouldSkip) {
      if (typeof val === 'object') { // Value is an object - run object sanitizer
        originalObj[visitedMark] = true; // Mark current node as "seen" - will stop from going deeper into circulars
        const nextDepth = depth + 1;
        result[entry] = removeCirculars(val, nextDepth);
      } else {
        result[entry] = val;
      }
    } else {
      result = 'CIRCULAR';
    }
  });

  return result;
}

This will result in an object that has all the circular dependencies stripped and also does not go deeper than given MAX_CLEANUP_DEPTH.

这将导致一个对象去除了所有的循环依赖，并且不会比给定的更深MAX_CLEANUP_DEPTH。

Using symbols is safe as long as you don't do any meta-programming stuff on the object - they are transparent and they are not enumerable, hence - they will not show in any standard operations on the object.

使用符号是安全的，只要你不在对象上做任何元编程的东西——它们是透明的，它们是不可枚举的，因此——它们不会显示在对象的任何标准操作中。

Also, returning a new, cleaned up object has an advantage of not mutating the original one if you need to perform any additional operations on it.

此外，如果您需要对其执行任何其他操作，返回一个新的、清理过的对象的优点是不会改变原始对象。

If you don't want CIRCULARmarking, you can just modify the code a bit, hence skipping object before actually performing operations on it (inside the loop):

如果你不想CIRCULAR标记，你可以稍微修改一下代码，因此在实际对其执行操作之前跳过对象（在循环内）：

 originalObj[visitedMark] = true; // Mark current node as "seen" - will stop from going deeper into circulars
 const val = originalObj[entry];

 // Skip condition - either object is falsy, was visited or we go too deep
 const shouldSkip = val[visitedMark] || depth > MAX_SANITIZATION_DEPTH;

 if (!shouldSkip) {
   if (typeof val === 'object') { // Value is an object - run object sanitizer
    const nextDepth = depth + 1;
    result[entry] = removeCirculars(val, nextDepth);
  } else {
    result[entry] = val;
  }
 }

回答by Campbeln

Just to throw my version into the mix... below is a remix of @dkurzaj 's code(which is itself a remix of @Aaron V 's, @user4976005 's, @Trey Mack 's and finally @Freddie Nfbnm 's [removed?] code) plus @darksinge 's WeakMapidea. So... this thread's Megamix, I guess :)

只是为了将我的版本加入混合……下面是@dkurzaj 代码的混音（它本身就是 @Aaron V 的、@user4976005 的、@Trey Mack 的和最后 @Freddie Nfbnm 的混音） s [removed?] 代码）加上@darksinge 的WeakMap想法。所以...这个线程的 Megamix，我猜 :)

In my version, a report (rather than console.log'ed entries) is optionally returned as an array of objects. If a report is not required, testing stops on the first sighting of a circular reference (a'la @darksinge 's code).

在我的版本中，报告（而不是console.log'ed 条目）可以选择作为对象数组返回。如果不需要报告，则在第一次看到循环引用时停止测试（a'la @darksinge 的代码）。

Further, hasOwnPropertyhas been removed as Object.keysreturns only hasOwnPropertyproperties (see: https://developer.mozilla.org/en-US/docs/Web/JavaScript/Reference/Global_Objects/Object/keys).

此外，hasOwnProperty已作为Object.keys仅返回hasOwnProperty属性删除（请参阅：https: //developer.mozilla.org/en-US/docs/Web/JavaScript/Reference/Global_Objects/Object/keys）。

function isCyclic(x, bReturnReport) {
    var a_sKeys = [],
        a_oStack = [],
        wm_oSeenObjects = new WeakMap(), //# see: https://developer.mozilla.org/en-US/docs/Web/JavaScript/Reference/Global_Objects/WeakMap
        oReturnVal = {
            found: false,
            report: []
        }
    ;

    //# Setup the recursive logic to locate any circular references while kicking off the initial call
    (function doIsCyclic(oTarget, sKey) {
        var a_sTargetKeys, sCurrentKey, i;

        //# If we've seen this oTarget before, flip our .found to true
        if (wm_oSeenObjects.has(oTarget)) {
            oReturnVal.found = true;

            //# If we are to bReturnReport, add the entries into our .report
            if (bReturnReport) {
                oReturnVal.report.push({
                    instance: oTarget,
                    source: a_sKeys.slice(0, a_oStack.indexOf(oTarget) + 1).join('.'),
                    duplicate: a_sKeys.join('.') + "." + sKey
                });
            }
        }
        //# Else if oTarget is an instanceof Object, determine the a_sTargetKeys and .set our oTarget into the wm_oSeenObjects
        else if (oTarget instanceof Object) {
            a_sTargetKeys = Object.keys(oTarget);
            wm_oSeenObjects.set(oTarget /*, undefined*/);

            //# If we are to bReturnReport, .push the  current level's/call's items onto our stacks
            if (bReturnReport) {
                if (sKey) { a_sKeys.push(sKey) };
                a_oStack.push(oTarget);
            }

            //# Traverse the a_sTargetKeys, pulling each into sCurrentKey as we go
            //#     NOTE: If you want all properties, even non-enumerables, see Object.getOwnPropertyNames() so there is no need to call .hasOwnProperty (per: https://developer.mozilla.org/en-US/docs/Web/JavaScript/Reference/Global_Objects/Object/keys)
            for (i = 0; i < a_sTargetKeys.length; i++) {
                sCurrentKey = a_sTargetKeys[i];

                //# If we've already .found a circular reference and we're not bReturnReport, fall from the loop
                if (oReturnVal.found && !bReturnReport) {
                    break;
                }
                //# Else if the sCurrentKey is an instanceof Object, recurse to test
                else if (oTarget[sCurrentKey] instanceof Object) {
                    doIsCyclic(oTarget[sCurrentKey], sCurrentKey);
                }
            }

            //# .delete our oTarget into the wm_oSeenObjects
            wm_oSeenObjects.delete(oTarget);

            //# If we are to bReturnReport, .pop the current level's/call's items off our stacks
            if (bReturnReport) {
                if (sKey) { a_sKeys.pop() };
                a_oStack.pop();
            }
        }
    }(x, '')); //# doIsCyclic

    return (bReturnReport ? oReturnVal.report : oReturnVal.found);
}