CODEWITHSUNDEEP
javascript
Elliot Bonneville
Elliot Bonneville

Reputation: 53351

Infinite loop when attempting to search an object

I recently saw this question being asked in which the OP wanted to find the path to a property of an object, so I answered it in psuedocode, stating that I didn't have enough time to actually write a solution. However, the question was so interesting to me that I wound up attempting to write a solution anyways. Here's what I've come up with so far:

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

The idea is that I would call this.searchNode() on Node objects which represented each of the object's properties. searchNode() would call itself on each of the resulting property nodes, passing in the current object as the parent on each of the children nodes. If I found the function to search for, I would call reconstructPathRecursive(), which pretty much does that, using the parent property on each of the nodes.

However, I get a 'Maximum call stack size exceeded.' error when I run this live test. I assume it means I accidentally wrote an infinite loop somehow. Where's the flaw in my logic, and where did that infinite loop sneak in? console.log shows that searchNode is being called over and over again, whereas I'm only calling it if the object isn't empty, and I'm not giving the object a reference to itself anywhere (I don't think...), so I'm really kind of stumped here.

Edit: I updated the code somewhat to change isEmpty from a Node function to a global function, so that I could call it on this.obj in the searchNode() function. Previously, it would only call it on Nodes (which will always have at least two properties, thus resulting in an infinite loop), not the objects the referenced. That's fixed, but the error persists.

Another edit: Found and corrected another error (see Satyajit's answer). Still getting the infinite loop, though.

Upvotes: 3

Views: 371

Answers (2)

Mike Samuel
Mike Samuel

Reputation: 120546

This will fail on

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

because it contains itself as a child. The Node function ends up creating an unbounded list of nodes where the parent is the same as the child.

To handle cyclic object graphs, you need to keep track of what you've already visited and avoid revisiting it. This is difficult in JavaScript because you don't have object sets.

You can either keep a list of objects you've visited, and check whether obj appears in it, or you could try to use a special object property (breadcrumb) to tell whether you've visited an object. The breadcrumb fails if you don't clean up properly or someone else uses that property, or other code uses EcmaScript 5 freezing.

EDIT:

You should also break out of the child loop when you actually find a path in a child.

path = children[i].searchNode();

should be

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

EDIT:

As Satyajit points out, "gotcha" is a property value.

Since "gotcha"[0] === "g" and "g"[0] === "g" it doesn't take long before you reach a cycle.

When I do

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

in a recent Chrome, I get alerts "true", "0", "1", ..., "5".

This is standard behavior on modern browsers as outlined in section 15.5.5.2:

String objects use a variation of the [[GetOwnProperty]] internal method used for other native ECMAScript objects (8.12.1). This special internal method is used to add access for named properties corresponding to individual characters of String objects.

and these properties are enumerable due to bullet 9 in that section.

Upvotes: 1

Satyajit
Satyajit

Reputation: 3859

The property nullRoot is a string and not a javascript object. Running your isEmpty function on that will never return false and throw it into an infinite loop. It's almost prophetic that you put "gotcha" as its value though.

Upvotes: 2

Related Questions