Return path to a value in a nested object

Question

Description:

Its not a programming challenge but I though to write a small utility which will return the path to a primitive value in a possibly nested object. The idea is not original.

Code:

console.clear();

function each(obj, cb, path) {
  path = path || [];
  for (let k in obj) {
    let val = obj[k];
    if (isLeaf(val)) {
      if (cb(val, path.concat(k)) === false) return false;
    }
    else {
      if (each(val, cb, path.concat(k)) === false) return false;
    }
  }
  return true;
}

let deep = {foo: {bar: true}, baz: 2, blurg: {fop: {hif: []}}};

// If the value is one of the primitive type?
function isLeaf(val) {
  return val !== Object(val) || Array.isArray(val);
}

each(deep, (val, path) => {
  console.log(val);
  console.log(path);
  //return false;
});

/*
          { }
    (foo) / \  (baz)
{bar: true} {2}
  (bar) /
  {true} 
*/

Note:

Initially I had no return statement and it worked fine but I thought to give client code to give opportunity to stop the iteration once it finds the desired path/value so after fiddling a bit I had to add couple to return statement and it worked. So, I gained an useful insight on how to unroll the recursive call from any level.

Questions:

As always I had trouble designing the recursive solution and it was done after some hit and try. I need to know if there is some mental model to keep in mind while doing these kinds of problems?

Having said that I would like to know if the solution is readable, clear and concise?

What modifications I need to make if need to make it part of open source library?

Answer 1

Recursion & JavaScript don't mix.

I am a big fan of recursion, but with JavaScript there are some issues that make recursion a dangerous animal to play with.

Call stack limit

One of JavaScript's limitations, lack of proper tail calls, (ES6 has it slated but there is a world of noncompliance out there) is both a saving grace and a curse.

Consider the object

var cyclic = {me : null};

Your function deals with it and exits. But there are many objects in the JavaScript environment that are self referencing. It is perfectly normal for me to do,

cyclic.me = cyclic;

and your code will thankfully bail with the lovely

RangeError: Maximum call stack size exceeded at Object (native)

This is because there is a limit to the depth of the call stack. It is also why recursion is not always safe. It may be ridiculous in this example but a recursive function can not be said to be safe. You can not know when you will exceed the call stack, especially if you are calling the recursive function innocently from within another recursive function. You can not enforce calling conditions so recursion is really something to be avoided in JavaScript.

As for the cyclic object. You will have to implement a check to ensure you are not chasing your own tail.

So the rest will ignore the fact that you should not be writing recursive code in JavaScript unless you extremely careful.

Some problems

Not so much about recursion, you have the understanding of how they work.

• Bad naming. Functions each and isLeaf to findPrimitives and isPrimitive
• It is not immediately clear what the callback function is for, and its return type is a ambiguous. See below for more.
• Memory usage. Don't use Array.concat inside recursive code, if you can avoid it. Array.concat creates a new reference to the array, so each step into the recursion you create a new reference that is closed over, effectively creating may similar copies of the same data.
• isleaf now isPrimitive is failing. There is a more robust way to test if the current "leaf" is a primitive type. See rewrite at bottom.

The callback function is ambiguous. One of JavaScript's flaws is no way to force a return type for a function. Many people consider undefined == false, and not undefined !== false and would expect that the unspecified return value (functions return undefined by default) to mean false. I would remove the ambiguity and require that the callback function answer the question "Has the object you are looking for been found?" and return true to exit from the recursion"

So by changing the callback return requirement to true to exit early the findPrimitive return value makes more sense.

if(findPrimitives(deep,report) === false){  // did not find what I am looking for

Neither right or wrong.

• There are some differing schools of thought as to the use of the let token and the importance of block scope. When I see it being used inconsistently and interchangeably with either const or (in this case) var, I consider that it is not being correctly used and must consider if in fact the author has sound logic for creating block scoped variables or just using a trendy new feature because it is there.
• There were many ways to make the function fail, though it is only an exercise, testing is still very important. Bad habits can form and incorrect assumption made when you don't test your experiments to their destruction.
• I am not a fan of anonymous functions if they can be avoided as it make debugging so much more difficult. I have seen traces that are just anon calling anon all the way from the top,the only way to trace the actual path is to step out one by one.
• For all of us JavaScript programmers it is a time of transition. Some will use ES6 to the full, and others avoid it because of the legacy browsers (Dam you IE for freezing just as ES6 was adopted!). But with ES6 it's in for a penny, in for a pound. You have clearly opted in for ES6 so you should use it to the full. Currently your code is a mixture of ES5 and ES6, being incompatible to ES5 only environments and not getting the full benefit of ES6.

Style

Your style is not horrible, but it's not excellent either.

There are two issues. Your use of let and naming as noted above. And the following

If you can say that you have never ever had to look for a bug caused by

if(bar){
    if(blah) foo = true;
    boo = false;
}

that was meant to be

if(bar){
    if (blah) {
        foo = true;
        boo = false;
    }
}

then ignore this point. If you have you will know how hard they are to spot, especially when you have masses of complex code. There is one way to avoid this frustration. All conditional statements are blocks and blocks require the embrace of {curlies}. You can still keep the single line space saving style if ( blah ) { foo=true; }

The rewrite.

This was hard to do as I would implement this type of function completely differently. So it is a compromise between your implied requirements (from your code) and my A.D.D. driving me to start it from scratch.

I changed the arguments. Separating out the current object / property name. I keep the same path array reference rather than create a new one each time. I use Object.keys to get an array of property names rather than for(k in obj) I vet for callback function. I vet for obj being a primitive or not having properties. I changed isPrimitive to a more suitable solution.

"use strict"; // make code run quicker and helps catch many potencial bugs
              // that otherwise may go unnoticed until it's to late.
function isPrimitive (val) {
    // typeof null returns object but for this null is a primitive
    return val === null || ["object","function"].indexOf(typeof val) === -1;
}
// added propName as argument. It is the name of the object being examined
// ES6 default argument assignment. Rather than in the function having 
// path = path || [] put it in
// the function argument declaration
function findPrimitives (obj, callback, propName, path = []) {
    var keys, name;                 // don't use let if the variables are just one block 
                              // in from the function scope on entry and exit.
    if(typeof callback !== "function"){ // no point if there is no callback
        return undefined;     // Return neither true or false as the question 
                              // has not been asked.
    }
    if (typeof obj === "object") {
        keys = Object.keys(obj); // As this is ES6 code Object.keys can be used
                                 // to get all the own properties
    } else {
        if( isPrimitive(obj) ) {
            return callback(obj, propName, path); 
        }
        return false;
    }
    path.push(propName);
    for(name of keys){
        if (isPrimitive(obj[name]) ) {
            if (callback(obj[name], name, path) === true) {  // explictly true to exit
                return true; // This is early exit not popping values 
                             // of the path to keep it intact
            }
        } else {
            if (findPrimitives(obj[name], callback, name,  path)) { // implied true
                return true; // This is early exit not popping values of 
                             // the path to keep it intact
            }
        }
    }
    path.pop();  // done with this branch pop it from the path
    return false;
}

and debugging code, is just a quick run test and is not an example of how to test code. It is to help debug and refine the code.

var deep = {
    foo: {
        bar: true
    }, 
    baz: 2, 
    blurg: {
        fop: {
            hif: [],
            hof: /hi/g, // regExp
            now : new Date(),
            what : "String",
            undef : undefined,
            nulls : null,
            nan : NaN,
        }
    },
    verb : function(){return "hi"},
    cur : 10,

};
var cyclic = {}
cyclic.me = cyclic; 

function report(value,name,path){  // avoiding anon function for callback
    log(path.join(".")+"."+name + "=" + value + " type ("+(typeof value)+")")
}
findPrimitives(deep,report);
findPrimitives(deep,report,"deep");
findPrimitives(deep,report,"deep",["window"]);

// the following will be inconsistant with expectations
findPrimitives(deep);
findPrimitives("hi");
findPrimitives("hi",report);

// the following will crash and burn.... 
findPrimitives(cyclic,report);