Есть ли способ проверить циклическую ссылку в JavaScript?
Я делаю игру, и я столкнулся с проблемой... Когда я пытаюсь сохранить, JSON не работает и сообщает, что где-то делается циклическая ссылка. Я не думаю, что это на самом деле, я не вижу этого, так есть ли алгоритм или что-нибудь, что могло бы сказать мне, где это точно (между какими объектами и вещами)? Кроме того, есть ли альтернатива JSON, которая может сохранить циклическую ссылку? Я запускаю сервер node.js, я видел это, но я не могу заставить его работать (это не сделано как модуль, который я могу требовать () в моем коде).
6 ответов
Если вы хотите сериализовать циклическую ссылку, чтобы сохранить ее, вам нужно сделать ссылку "виртуальной", чтобы ее нельзя было сериализовать как циклическую ссылку, поскольку это приведет к тому, что сериализация сериализует один и тот же круг объектов навсегда (или, по крайней мере, до тех пор, пока во время выполнения не закончится память).
Поэтому вместо того, чтобы хранить саму циклическую ссылку, вы просто сохраняете указатель на объект. Указатель будет просто что-то вроде 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;
}
Нет хорошего способа обнаружить округлость в объектах, но это возможно, хотя, обходя дерево объектов и проверяя ссылки. Я запустил функцию обхода узла, которая пытается определить, был ли узел уже использован в качестве его родителя.
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
Ключевым моментом является то, что значение объекта равно другому значению, только если это та же ссылка на объект, а не когда это другой объект (даже если он полностью похож).
Это небольшое дополнение к ответу Андриса, в котором говорится, где находится первый круговой элемент, чтобы вы могли соответственно с ним справиться.
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();
для его родителя.
Вот код, который я использую для обнаружения циклических ссылок, он использует технику, которая была предложена в принятом ответе 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 устарел и запрещен в строгом режиме по сравнению с использованием именованных функций
Я думал о том, чего вы пытаетесь достичь, основываясь на исходном коде из вашего другого вопроса. Почему бы не сделать что-то подобное.
Player = function()
{
this.UnitTypeXpower = 2
this.UnitTypeYpower = 7
}
UnitTypeXAdd = function(owner)
{
owner.UnitTypeXpower++;
}
Таким образом, вам не нужно использовать циклическую ссылку, и она выполняет то же самое.
Эта ветка уже содержит несколько хороших ответов. Если вы ищете способ обнаружения циклических ссылок или сравнения двух значений при работе с циклическими ссылками, вам следует проверить эту библиотеку:
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. .
Все, что требуется для обработки других классов, это вызвать:
registerClassTypes()
registerIterableClass()
Эта библиотека поставляется со 100% покрытием кода, поэтому вы можете узнать, как использовать API, прочитав файлы .spec, если вы посетите страницу GitHub.
Отказ от ответственности: я написал эту библиотеку, но я думаю, что есть законная причина упомянуть ее, поскольку она предоставляет дополнительные функции, которые могут вам понадобиться при работе с циклическими зависимостями.