有没有一种方法可以测试JavaScript中的循环引用？

Question

我正在制作一款游戏，遇到了一个问题……当我尝试保存时，JSON报告说在某个地方存在循环引用。我不认为实际上存在循环引用，因为我看不到它。所以，有没有算法或其他东西可以告诉我它到底在哪里（对象之间的哪些位置）？此外，是否有一种JSON替代方案可以保存循环引用？我正在运行一个node.js服务器，我看到了这个，但我无法让它工作（它不是我可以在代码中require()的模块）。

- corazza

Answer 1

如果您想要序列化一个循环引用，以便保存它，那么您需要使该引用“虚拟化”，使其不能被序列化为循环引用，因为这将导致序列化永远序列化相同的一组对象（或者至少直到运行时内存耗尽）。

因此，您只需存储指向对象的指针，而不是存储循环引用本身。指针将只是类似于ref:'#path.to.object'的东西，可以在反序列化时解析，以便将引用指回实际对象。您只需要在序列化时打破引用即可对其进行序列化。

通过递归地迭代所有对象（使用for (x in y)），将x存储在数组中，并为临时数组中的每个z使用恒等运算符（又名严格比较运算符）===将每个x与其进行比较，以发现JavaScript中的循环引用。每当x === z为true时，将对x的引用替换为占位符，该占位符将序列化为上述提到的ref。

一个替代方法是在迭代对象时通过在它们上设置属性来“污染”它们，例如在这个非常简单的示例中：

for (x in y) {
    if (x.visited) {
       continue;
    }

    x.visited = true;
}

- Asbjørn Ulsberg

Answer 2

检测对象的循环引用是没有好方法的，但通过遍历对象树并检查引用是可能的。我编写了一个节点遍历函数，尝试检测一个节点是否已经被其父节点使用。

function isCircularObject(node, parents){
    parents = parents || [];

    if(!node || typeof node != "object"){
        return false;
    }

    var keys = Object.keys(node), i, value;

    parents.push(node); // add self to current path      
    for(i = keys.length-1; i>=0; i--){
        value = node[keys[i]];
        if(value && typeof value == "object"){
            if(parents.indexOf(value)>=0){
                // circularity detected!
                return true;
            }
            // check child nodes
            if(arguments.callee(value, parents)){
                return true;
            }

        }
    }
    parents.pop(node);
    return false;
}

使用方法为 isCircularObject(obj_value)，函数将返回true表示存在循环引用，返回false表示不存在。

// setup test object
var testObj = {
    property_a:1, 
    property_b: {
        porperty_c: 2
        },
    property_d: {
        property_e: {
            property_f: 3
            } 
        }
    }

console.log(isCircularObject(testObj)); // false

// add reference to another node in the same object
testObj.property_d.property_e.property_g = testObj.property_b;
console.log(isCircularObject(testObj)); // false

// add circular node
testObj.property_b.property_c = testObj.property_b;
console.log(isCircularObject(testObj));  // true

重点在于当且仅当一个对象引用相同时，其对象值才与另一个值相等，而不是当它是另一个对象时（即使完全相似）。

- Andris

Answer 3

这是对Andris答案的小扩展，它告诉你第一个循环元素在哪里，这样你就可以相应地处理它。

function findCircularObject(node, parents, tree){
    parents = parents || [];
    tree = tree || [];

    if (!node || typeof node != "object")
        return false;

    var keys = Object.keys(node), i, value;

    parents.push(node); // add self to current path
    for (i = keys.length - 1; i >= 0; i--){
        value = node[keys[i]];
        if (value && typeof value == "object") {
            tree.push(keys[i]);
            if (parents.indexOf(value) >= 0)
                return true;
            // check child nodes
            if (arguments.callee(value, parents, tree))
                return tree.join('.');
            tree.pop();
        }
    }
    parents.pop();
    return false;
}

如果你不想要一个字符串，那么树状数组就没必要了。只需要将原函数修改为:

return value;

对于圆形物体本身或者

return parents.pop();

为其父元素。

- jimmetry

Answer 4

我在思考你根据之前提出的代码所要实现的目标。为什么不尝试这样做呢？

Player = function()
{
    this.UnitTypeXpower = 2
    this.UnitTypeYpower = 7

}

UnitTypeXAdd = function(owner)
{
    owner.UnitTypeXpower++;   
}

这样你就不必使用循环引用，而且它可以达到同样的效果。

- Logos

---

我使用的实际对象要复杂得多，我只是将“power”作为占位符，因为把整个代码放在那里是一个不好的主意... - corazza

Answer 5

这是我用来检测循环引用的代码，它使用了asbjornu所建议的方法，通过遍历每个值并在数组中维护其引用，以便将来可以与之前遍历过的值进行比较。

function isCircular(obj, arr) {
    "use strict";

    var type = typeof obj,
        propName,
        //keys,
        thisVal,
        //iterKeys,
        iterArr,
        lastArr;

    if (type !== "object" && type !== "function") {
        return false;
    }

    if (Object.prototype.toString.call(arr) !== '[object Array]') {
    //if (!Array.isArray(arr)) {
        type = typeof arr; // jslint sake
        if (!(type === "undefined" || arr === null)) {
            throw new TypeError("Expected attribute to be an array");
        }

        arr = [];
    }

    arr.push(obj);
    lastArr = arr.length - 1;

    for (propName in obj) {
    //keys = Object.keys(obj);
    //propName = keys[iterKeys];
    //for (iterKeys = keys.length - 1; iterKeys >= 0; iterKeys -= 1) {
        thisVal = obj[propName];
        //thisVal = obj[keys[iterKeys]];
        type = typeof thisVal;

        if (type === "object" || type === "function") {
            for (iterArr = lastArr; iterArr >= 0; iterArr -= 1) {
                if (thisVal === arr[iterArr]) {
                    return true;
                }
            }

            // alternative to the above for loop
            /*
            if (arr.indexOf(obj[propName]) >= 0) {
                return true;
            }
            */

            if (isCircular(thisVal, arr)) {
                return true;
            }

        }
    }

    arr.pop();

    return false;
}

这段代码可以在jsfiddle上找到，您可以自行测试。 我还进行了一些性能测试，可在jsperf上查看。 Array.indexOf仅在Javascript 1.6中引入，请参见MDN页面 Array.isArray仅在Javascript 1.8.5中引入，请参见MDN页面 Object.keys仅在Javascript 1.8.5中引入，请参见MDN页面 值得注意的是，在严格模式下，命名函数优先于使用arguments.callee，而后者已被废弃并禁止使用。

- Xotic750

---

你的代码可以像这样简化：try { JSON.stringify(obj); return true; } catch (e) { return false; } - V. Sambor

OP写道：“我正在制作一款游戏，但遇到了一个问题...当我尝试保存时，JSON失败并报告说某处正在进行循环引用。我不认为实际上是这样的，因为我看不到它，所以有没有算法或其他东西可以告诉我它确切的位置（在哪些对象和东西之间）？此外，是否有一种JSON替代方案可以保存循环引用？我正在运行一个node.js服务器，我看到了这个，但我无法让它工作（它不是作为我可以在代码中require()的模块制作的）。” - Xotic750

Answer 6

这个线程已经包含了一些很好的答案。如果你正在寻找一种检测循环引用或比较两个值同时处理循环引用的方法，你应该查看这个库：

https://www.npmjs.com/package/@enio.ai/data-ferret

它具有以下方法：

hasCircularReference(someValue) // A predicate that returns true when it detects circular reference.
isIdentical(valueA, valueB) // By calling setConfig(options) opt-in circular reference support, this function does an equality check that does not fall into an infinite recursion trap.

在底层，它使用了与@Asbjørn Ulsberg描述的类似算法，但通过删除所有插入的标志来清理自己。

然而，这里讨论的算法与建议之间的主要区别是它可以处理任意数量的本地/自定义、可迭代/非可迭代类，这意味着它支持超出JSON规范和JavaScript的Object和Array的循环检测和值比较。

它处理其他类所需的全部内容就是调用：

registerClassTypes()
registerIterableClass()

这个库具有100%的代码覆盖率，因此您可以通过阅读.spec文件来了解如何使用API，如果您访问GitHub页面。

免责声明：我编写了这个库，但我认为有合法的理由提到它，因为它提供了您在处理循环依赖时可能需要的其他功能。

- Andrew Redican