Бесконечный цикл при попытке поиска объекта

Question

Недавно я увидел this question, в котором OP хотел найти путь к объекту объекта, поэтому я ответил на него в psuedocode, заявив, что мне не хватило времени на на самом деле написать решение. Однако вопрос был настолько интересным для меня, что я все-таки пытался написать решение. Вот что я придумал до сих пор:

function isEmpty(obj) { 
    for (var prop in obj) { 
     if (Object.prototype.hasOwnProperty.call(obj, prop)) { 
      return false; 
     } 
    } 
    return true; 
} 

function Node(obj, parent, searchTarget) { 
    this.parent = parent; 
    this.obj = obj; 
    this.searchTarget = searchTarget; 

    this.searchNode = function() { 
     if(this.obj == this.searchTarget) { 

      //return this.reconstructPathRecursive(); 
     } 

     if (!isEmpty(this.obj)) { 
      var children = []; 

      for (prop in this.obj) { 
       if (this.obj.hasOwnProperty(prop)) { 
        children.push(new Node(this.obj[prop], this, searchTarget)); 
       } 
      } 

      var path; 
      for(var i = 0, len = children.length; i < len; i++) { 
       path = children[i].searchNode(); 
       if(path) return path; 
      } 
     } 
    } 

    this.reconstructPathRecursive = function() { 
     var path = [this], curObj = this.parent; 

     while (curObj != undefined) { 
      path.push(curObj); 
      curObj = curObj.parent; 
      if(curObj == undefined) break; 
     } 

     return path; 
    } 

    this.findPath = function() { 
     return this.searchNode(); 
    } 
} 

var myObj = { 
    nullRoot: "gotcha!", 
    path1: { 
     myFunc: function() { 
      alert("Success!"); 
     } 
    } 
} 

function findFunctionPath(obj, func) { 
    return new Node(obj, undefined, func).findPath(); 
} 
var thisFunc = myObj.path1.myFunc; 
    console.log("--"); 

console.log(findFunctionPath(myObj, thisFunc)); 

Идея заключается в том, что я бы назвал this.searchNode() на объектах Node, которые представляли каждый из свойств объекта. searchNode() будет называть себя на каждом из полученных узлов свойств, передавая текущий объект как parent на каждом из дочерних узлов. Если бы я нашел функцию для поиска, я бы назвал reconstructPathRecursive(), что в значительной степени делает это, используя родительское свойство на каждом из узлов.

Однако, я получаю «Максимальный размер стека вызовов». ошибка, когда я запускаю этот live test. Я предполагаю, что это означает, что я случайно написал бесконечный цикл. Где ошибка в моей логике, и где этот бесконечный цикл прокрался? console.log показывает, что searchNode вызывается снова и снова, тогда как я вызываю его только в том случае, если объект не пуст, и я не даю объекту ссылку на себя где-нибудь (я не думаю ...) , так что я действительно немного здесь.

Edit: Я обновил код немного изменить isEmpty из функции узла в глобальной функции, так что я мог бы назвать его this.obj в функции searchNode(). Раньше он вызывал бы это только на узлах (которые всегда будут иметь как минимум два свойства, что приводит к бесконечному циклу), а не к объектам, на которые они ссылаются. Это исправлено, но ошибка сохраняется.

Другое редактирование: Найден и исправлена ​​другая ошибка (см. Ответ Сатьяджита). Тем не менее, все еще получая бесконечный цикл.

Answer 1

Это потерпит неудачу на

var arr = []; 
arr[0] = arr; 

, потому что он содержит себя, как ребенок. Функция Node заканчивается созданием неограниченного списка узлов, где родительский элемент совпадает с родительским.

Чтобы обрабатывать графики циклических объектов, вам необходимо отслеживать, что вы уже посетили, и не пересматривать его. Это сложно в JavaScript, потому что у вас нет объектов.

Вы можете сохранить список объектов, которые вы посетили, и проверьте, отображается ли obj в нем, или вы могли бы попытаться использовать специальное свойство объекта () строки навигации, чтобы сказать уже посещали ли вы объект. Патч терпит неудачу, если вы не очистите его правильно, или кто-то другой использует это свойство, или другой код использует замораживание EcmaScript 5.

---

EDIT:

Вы также должны выйти из цикла ребенка, когда вы на самом деле найти путь в ребенке.

path = children[i].searchNode(); 

должно быть

path = children[i].searchNode(); 
if (path) { return path; } 

---

РЕДАКТИРОВАТЬ:

В Сатьяджит указывает, "gotcha" это значение свойства.

С "gotcha"[0] === "g" и "g"[0] === "g" это займет немного времени, прежде чем вы достигнете цикла.

Когда я

alert("gotcha".hasOwnProperty(0)); 
for (var k in "gotcha") { alert(k); } 

в недавнем Chrome, я получаю сигналы "истина", "0", "1", ..., "5".

Это стандартное поведение на современных браузерах, как это описано в разделе 15.5.5.2:

объекты строк используют изменение внутреннего метода [[GetOwnProperty]] используется для других встроенных объектов ECMAScript (8.12.1). Этот специальный внутренний метод используется для добавления доступа для именованных свойств, соответствующих отдельным символам объектов String.

, и эти свойства перечислены из-за пули 9 в этом разделе.

Answer 2

Свойство nullRoot - это строка, а не объект javascript. Запуск функции isEmpty на этом никогда не вернет false и выбросит его в бесконечный цикл. Это почти пророчество, что вы поставили «gotcha» в качестве своей ценности.