Есть ли способ проверить циклическую ссылку в JavaScript?

Question

Я создаю игру, и я столкнулся с проблемой ... Когда я пытаюсь сохранить, JSON завершается неудачно и сообщает, что где-то делается циклическая ссылка. Я не думаю, что это на самом деле, я не вижу этого, так есть ли алгоритм или что-нибудь, что могло бы сказать мне, где это точно (между какими объектами и вещами)? Кроме того, есть ли альтернатива JSON, которая может сохранить циклическую ссылку? Я запускаю сервер node.js, я видел this , но я не могу заставить его работать (он не сделан как модуль, который я могу требовать () в своем коде).

Answer 1

Если вы хотите сериализовать циклическую ссылку, чтобы сохранить ее, вам нужно сделать ссылку "виртуальной", чтобы ее нельзя было сериализовать как циклическую ссылку, поскольку это приведет к сериализации сериализации того же круга. объекты навсегда (или, по крайней мере, до тех пор, пока во время выполнения не закончится память).

Таким образом, вместо сохранения самой циклической ссылки, вы просто сохраняете указатель на объект. Указатель будет просто похож на ref : '#path.to.object', который может быть разрешен при десериализации, поэтому вы указываете ссылку на реальный объект. Вам просто нужно разорвать ссылку на сериализацию, чтобы иметь возможность ее сериализовать.

Обнаружение циклической ссылки в JavaScript может быть выполнено путем рекурсивной итерации по всем объектам (с for (x in y)), сохранения x в массиве и сравнения каждого x с оператором идентификации (он же оператор строгого сравнения). ) === для каждого z во временном массиве. Когда x === z равно true, замените ссылку на x заполнителем, который будет сериализован в вышеупомянутый ref.

Альтернативой хранению массива над «посещаемыми» объектами является «испачкать» объекты, через которые вы перебираете объекты, установив для них свойство, как в этом очень наивном примере:

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

    x.visited = true;
}

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

Ключевым моментом является то, что значение объекта равно другому значению только , если это та же ссылка на объект, а не когда это другой объект (даже если полностью похожи).

Answer 3

Это небольшое расширение к ответу Андриса, в котором указано, где находится первый круговой элемент, чтобы вы могли с ним соответственно справиться.

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();

для его родителя.

Answer 4

Вот код, который я использую для обнаружения циклических ссылок, он использует технику, которая была предложена в принятом ответе 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 устарело и запрещено в строгом режиме по сравнению с использованием именованных функций

Answer 5

Я думал о том, чего вы пытаетесь достичь, основываясь на исходном коде из вашего другого вопроса.Почему бы не сделать что-то вроде этого.

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

}

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

Таким образом, вам не нужно использовать круговую ссылку, и она выполняет то же самое.