5
\$\begingroup\$

I am trying to find the path of property in an object in JavaScript. For example, given

var myObj = { 'a': {'b': {'c': {'x': 1, 'y': 2 }}} }

the path of 'x' in myObj would be a.b.c.x (dot notation).

I wrote the code below using a recursive mechanism.

function findPropPath(obj, name, currentPath) {
    var currentPath = currentPath || '';

    for (var i in obj)
    {
        if (i == name)
        {
            return name;
        }
        else if (obj[i] && typeof obj[i] == "object")
        {
            var result = findPropPath(obj[i], name, currentPath + '.' + i);
            if (result == name)
            {
                return currentPath += '.' + name;
            }
            else if (result && result.endsWith('.' + name)) {
                return result;
            }
        }
    }
}

It works as expected, I would like to know if it can be optimized or other better ways find property path. Also I assume the call stack size would grow for enormous object. Any review would be of great help!

\$\endgroup\$
  • \$\begingroup\$ How deep could these objects be nested? Stack growth would not be my main concern, unless it turns out to be a real problem. \$\endgroup\$ – 200_success Aug 25 '17 at 21:13
  • \$\begingroup\$ When i do findPropPath(myObj,"c") it skips b and returns .a.c How so..? Besides if you have objects with same property names you will probably get only the path for the first one. Imagine arrays they all have same index values as per keys (properties) \$\endgroup\$ – Redu Aug 27 '17 at 17:33
  • \$\begingroup\$ I'm glad nobody can down-vote comments, because in this specific case I think a well written RegExp and eval is more terse, safer and more bullet-proof route. As long as the string contains just valid characters for property names and dots, eval is not so evil. \$\endgroup\$ – Greg Burghardt Aug 28 '17 at 18:00
4
\$\begingroup\$

Cyclic reference danger

Recursive property searches are dangerous because many objects used in javascript at some point have a reference to themselves. Eg the global object console.log(this.window === this); // displays true

You need to check or be sure that there are no cyclic references. A common method is to use the JSON.stringify function that will throw if an object is cyclic. This is a very inelegant method and will prevent you from finding the information you are after as you will not search if this fails.

The best way (unfortunately) is to store each object you iterate and then check every other object against that array of objects, ignoring all object you have already iterated.

More than one result

The second problem you have is that the search will find only one path, while there could be many paths that satisfy the requirement, the first result may not be the one you are after. If you use a callback to determine the matching result you can be a lot more adaptable. The callback can accept not only the key name, but the current path and the current object the key belongs to.

The function should return all paths that satisfy the condition set by the callback function.

Modernise

ES6 has been available in the majority of browsers for some time. It is best to use ES6 as it is a major improvement on ES5, not using it is a major No No if you plan on an IT career. If you are concerned about legacy browsers (especially that annoying thorn called IE11) you should use a transpiler (for example Babel) to ensure backward compatibility.

A rewrite

I present a modification that is safer and more versity and in two forms. One as a standalone function and the other as a prototype of Object.

function findPropPaths(obj, predicate) {  // The function 
    const discoveredObjects = []; // For checking for cyclic object
    const path = [];    // The current path being searched
    const results = []; // The array of paths that satify the predicate === true
    if (!obj && (typeof obj !== "object" || Array.isArray(obj))) {
        throw new TypeError("First argument of finPropPath is not the correct type Object");
    }
    if (typeof predicate !== "function") {
        throw new TypeError("Predicate is not a function");
    }
    (function find(obj) {
        for (const key of Object.keys(obj)) {  // use only enumrable own properties.
            if (predicate(key, path, obj) === true) {     // Found a path
                path.push(key);                // push the key
                results.push(path.join("."));  // Add the found path to results
                path.pop();                    // remove the key.
            }
            const o = obj[key];                 // The next object to be searched
            if (o && typeof o === "object" && ! Array.isArray(o)) {   // check for null then type object
                if (! discoveredObjects.find(obj => obj === o)) {  // check for cyclic link
                    path.push(key);
                    discoveredObjects.push(o);
                    find(o);
                    path.pop();
                }
            }
        }
    } (obj));
    return results;
}

Usage

Usage is simple

const arrayOfPaths = findPropPaths(myObj, key => key === "x");

The predicate takes the form of

function(key, path, obj) { 

Where key is the property name being tested, path is an array of property names up to the current object. obj is the current object the property key belongs to.

The function returns true if the test passes, and any other value if the test fails. Only paths that the predicate returns true for are returned in the array of paths found.

Example code

The function is very versatile and below it will find all paths to properties that are named "x" and the second search will find all paths named x and contain a string

    function findPropPaths(obj, predicate) {  // The function 
        const discoveredObjects = []; // For checking for cyclic object
        const path = [];    // The current path being searched
        const results = []; // The array of paths that satify the predicate === true
        if (!obj && (typeof obj !== "object" || Array.isArray(obj))) {
            throw new TypeError("First argument of finPropPath is not the correct type Object");
        }
        if (typeof predicate !== "function") {
            throw new TypeError("Predicate is not a function");
        }
        (function find(obj) {
            for (const key of Object.keys(obj)) {  // use only enumrable own properties.
                if (predicate(key, path, obj) === true) {     // Found a path
                    path.push(key);                // push the key
                    results.push(path.join("."));  // Add the found path to results
                    path.pop();                    // remove the key.
                }
                const o = obj[key];                 // The next object to be searched
                if (o && typeof o === "object" && ! Array.isArray(o)) {   // check for null then type object
                    if (! discoveredObjects.find(obj => obj === o)) {  // check for cyclic link
                        path.push(key);
                        discoveredObjects.push(o);
                        find(o);
                        path.pop();
                    }
                }
            }
        } (obj));
        return results;
    }

    // create test object. Sorry but for brevity I have made it all one line
    const myObj = { a:0, g : [0, 1, 2, 3, "x", {x : 0}], d : null, z: {  b: {  c: { x: { a : {x : 0, } },  y: 2  }, d: { x: "0", y: 2 } } } };
    // add self reference to test cyclic protection
    myObj.f = myObj;
    
    // find all paths to property name "x"
    const arrayOfPaths = findPropPaths(myObj,key => key === "x");
    console.log("All unique paths to 'x'");
    arrayOfPaths.forEach(path => console.log(path));
    

    // find all paths to property name "x" that has a string
    const res1 = findPropPaths(myObj,(key, path, obj) => key === "x" && typeof obj[key] === "string");
    console.log("All unique paths to property 'x' holding a string");
    res1.forEach(path => console.log(path));

As Object.prototype

As you are after a fundamental function you can chose to add it to the Object prototype thus making it available to all object.

Many here will throw their hands up and say "NO WAY", I expect this answer to get more downvotes than up simply because of this. But it is a valid way of using the language, and is better understood than hidden behind gasps of "No" and "Run for the hills the end is now".

If you do it the following way you make it easier to use in your code. But there are warnings.

Warning when adding to the prototype of basic objects

If you do however you must take some precautions. Do not use the function if it already exists as the source may be unknown thus unsafe. Ensure that the function can not be overwritten as the object prototype is global and could be hijacked. Ensure that it works, the last thing you want to do is add a prototype to a basic object that requires some form of vetting before use. It should be bulletproof or it should not end up on the object's prototype.

The object prototype form

if (Object.prototype.findPropPaths !== undefined) {
    throw new ReferenceError("The object prototype 'findPropPaths` already exists and may be of unknown origin and thus unsafe to use.");
} else {
    Object.defineProperty(Object.prototype, 'findPropPaths', {
        writable : false,       // During development you should have this as true if you are working
                                // in an environment that does not reset, or this will throw an error
        enumerable : false,     // You don't want this to be seen
        configurable : false,   // You don't want this to be changed.
        value : function(predicate) {  // The function 
            const discoveredObjects = []; // For checking for cyclic object
            const path = [];    // The current path being searched
            const results = []; // The array of paths that satify the predicate === true
            if (typeof predicate !== "function") { 
                throw new TypeError("Predicate is not a function");
            }
            (function find(obj) {
                for (const key of Object.keys(obj)) {  // use only enumerable own properties.
                    if (predicate(key, path, obj) === true) {     // Found a path
                        path.push(key);                // push the key
                        results.push(path.join("."));  // Add the found path to results
                        path.pop();                    // remove the key.
                    }
                    const o = obj[key];                 // The next object to be searched
                    if (o && typeof o === "object" && ! Array.isArray(o)) {   // check for null then type object
                        if (! discoveredObjects.find(obj => obj === o)) {  // check for cyclic link
                            path.push(key);
                            discoveredObjects.push(o);
                            find(o);
                            path.pop();
                        }
                    }
                }
            } (this));
            return results;
        }
    });
}
\$\endgroup\$
  • \$\begingroup\$ ES6 is not yet supported on any released version of Safari, which includes iOS. \$\endgroup\$ – 200_success Aug 26 '17 at 17:42
  • \$\begingroup\$ @200_success Safari is not a majority, and that why people should become familiar with and use libraries like "babel" Time will make the need for legacy code redundant, so it is my opinion that coders are better of using (learning) the current and future standards. \$\endgroup\$ – Blindman67 Aug 26 '17 at 18:07
2
\$\begingroup\$

Please pick a consistent brace style.

i has the connotation of being an integer counter. I would pick a different variable name for iterating over the properties of an object.

I don't see any need for obj[i] && in the else if test.

If you use recursion properly, you shouldn't need to have a third parameter at all.

function findPropPath(obj, name) {
    for (var prop in obj) {
        if (prop == name) {
            return name;
        } else if (typeof obj[prop] == "object") {
            var result = findPropPath(obj[prop], name);
            if (result) {
                return prop + '.' + result;
            }
        }
    }
    return null;    // Not strictly needed, but good style
}

var myObj = {'a': {'b': {'c': {'x': 1, 'y': 2 }}}};
console.log(findPropPath(myObj, 'x'));

\$\endgroup\$
  • \$\begingroup\$ Some issues 1)Why the inconsistent use of quote and apostrophe? I believe that is just as important as constant brace style. 2) Why return null, this is unneeded complexity, return or just the default is the more constant and less complex style 3) Why use var where constants should be used (eg prop and result clearly intended as immutable and should be constants) 4) And no warning or check for cyclic reference, which is more than good reason to mark this answer as dangerous code. At least a warning in the answer to that effect as the error can go unnoticed without rigorous testing. \$\endgroup\$ – Blindman67 Aug 26 '17 at 14:33
  • \$\begingroup\$ 1) Because it was carried over from the original. You can point that out by writing a new answer. 2) I believe that if a function sometimes returns a value, then I'd rather have an explicit return. But, as I pointed out myself, it's optional. 3) For compatibility. Not all JS interpreters support const, and since it wasn't used in the original, I wasn't going to assume it would be safe to use. 4) That's an issue that was present in the original code. Point that out in your own answer. \$\endgroup\$ – 200_success Aug 26 '17 at 15:44
  • \$\begingroup\$ 1)Yet you corrected the blocks?? 2) You pointed it out but you are returning a null not undefined, this is not good style, especially when you say it is not needed, what is the expectation null or undefined 3)No not all interpreters support const but there should be an encouragement towards the present and for legacy some information on how to deal with it (ie babel). 4)Yes it was but you did not even mention it, it is unlikely that the author is aware of the problem. This is a review is it not? \$\endgroup\$ – Blindman67 Aug 26 '17 at 17:21
  • \$\begingroup\$ @Blindman67 Answers need only suggest one or more improvements; they need not be comprehensive or perfect. \$\endgroup\$ – 200_success Aug 26 '17 at 17:40
  • \$\begingroup\$ I do not believe in downvoting without an explanation, I gave some of the reason I down voted, i do not believe that the reasons are frivolous and deserve at least a right of reply by you. I was going to remove the downvote after your reply but discovered there is an hour limit (unfortunate) \$\endgroup\$ – Blindman67 Aug 26 '17 at 18:14
0
\$\begingroup\$

You gave a very helpful a.b.c.x example in English. Thank you. We can think of it as a unit test of sorts.

There are at least three cases you handle. You might offer unit tests that cover them.

Rather than accumulating currentPath as a string (with delimiters), you might prefer to accumulate it as a list of strings, and fill in dot delimiters as the last step, to reduce special casing.

\$\endgroup\$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.