DEV Community

Search through a JSON object using JavaScript

killants on January 31, 2019

As my opening contribution, i leave here a method i developed to search inside a JSON object for a specific value (could be or not the name of the ...

Read full post

Mihail Malo • Feb 4 '19 • Edited

Without changing the structure, I would do the following:

const charSeparator = "/"
/**
 * searches deep into an object recursively...
 * @param {Object} obj object to be searched
 * @param {any} searchValue the value/key to search for
 * @param {boolean} [valuesOnly=false] whether to skip comparing object keys
 * @param {number} [maxDepth=20] maximum recursion depth (to avoid "Maximum call stack size exceeded")
 * @returns {string[]} Paths on the object to the matching results
 */
function getValuePathInObject(
  obj,
  searchValue,
  valuesOnly = false,
  maxDepth = 20
) {
  if (!maxDepth) return []

  const paths = []

  for (const [curr, currElem] of Object.entries(obj)) {

    if (!valuesOnly && curr === searchValue) {
      // To search for property name too...
      paths.push(curr)
    }

    if (typeof currElem == "object") {
      // object is "object" and "array" is also in the eyes of `typeof`
      // search again :D
      const deepPaths = getValuePathInObject(
        currElem,
        searchValue,
        valuesOnly,
        maxDepth - 1
      )
      const currDir = curr + charSeparator
      for (const path of deepPaths) {
        paths.push(currDir + path)
      }
      continue
    }
    // it's something else... probably the value we are looking for
    // compares with `searchValue`
    if (currElem === searchValue) {
      // return index AND/OR property name
      paths.push(curr)
    }
  }
  return paths
}

Use const and let, never var.
Use for of loops instead of imperative key and numeric index iteration.
Remove the debug logging
Hoist the constant charSeparator out of the function (or you could inline the "/" literal)
Only concatenate curr and charSeparator once, not in the loop.
Remove unused variable i.
Use early return (or rather, continue).
Use JSDoc, LMAO xD
Use down-counting depth limit to pass only one number.
Use defaults in the function parameters. These only check for undefined, not truthiness, so passing false and 0 won't trigger them.

Mihail Malo • Feb 4 '19 • Edited

Otherwise, I'd use an inner recursive function so that I can do option parsing once, and then close over one array I will always append to, to avoid allocating intermediate arrays:

/**
 * searches deep into an object recursively...
 * @param {Object} obj object to be searched
 * @param {any} searchValue the value/key to search for
 * @param {Object} [options]
 * @param {boolean} options.[searchKeys] whether to search object keys as well as values. Defaults to `true` if `serchValue` is a string, `false` otherwise.
 * @param {number} options.[maxDepth=20] maximum recursion depth (to avoid "Maximum call stack size exceeded")
 * @returns {string[]} Paths on the object to the matching results
 */
const findPaths = (
  obj,
  searchValue,
  { searchKeys = typeof searchValue === "string", maxDepth = 20 } = {}
) => {
  const paths = []
  const notObject = typeof searchValue !== "object"
  const gvpio = (obj, maxDepth, prefix) => {
    if (!maxDepth) return

    for (const [curr, currElem] of Object.entries(obj)) {
      if (searchKeys && curr === searchValue) {
        // To search for property name too ...
        paths.push(prefix + curr)
      }

      if (typeof currElem === "object") {
        // object is "object" and "array" is also in the eyes of "typeof"
        // search again :D
        gvpio(currElem, maxDepth - 1, prefix + curr + "/")
        if (notObject) continue
      }
      // it's something else... probably the value we are looking for
      // compares with "searchValue"
      if (currElem === searchValue) {
        // return index AND/OR property name
        paths.push(prefix + curr)
      }
    }
  }
  gvpio(obj, maxDepth, "")
  return paths
}

Here, I'm also using an options object for convenience, with a smart default for searchKeys, since object keys are always strings, even in arrays:

console.log(findPaths([[[]],[[]]],0)) // []
console.log(findPaths([[[]],[[]]],'0')) // [ '0', '0/0', '1/0' ]

I'm also building the path string with no duplication. This includes eliminating the inner loop, since we never return an intermediary array back up. The reason prefix + curr occurs in 3 places is because in a real search, on most keys none of those conditions will happen, and almost never will two happen together.

Mihail Malo • Feb 4 '19 • Edited

Finally, at the cost of a tiny bit of memory, you can keep a Set of visited objects so you can prevent infinite recursion without a counter.

Before:

const obj = {
  a: 0,
  b: 1,
  c: [[]]
}
const obj2 = {t:obj}
obj.c[0].push(obj2, 't')
console.log(findPaths(obj,"t"));
[ 'c/0/0/t',
  'c/0/0/t/c/0/0/t',
  'c/0/0/t/c/0/0/t/c/0/0/t',
  'c/0/0/t/c/0/0/t/c/0/0/t/c/0/0/t',
  'c/0/0/t/c/0/0/t/c/0/0/t/c/0/0/t/c/0/0/t',
  'c/0/0/t/c/0/0/t/c/0/0/t/c/0/0/t/c/0/1',
  'c/0/0/t/c/0/0/t/c/0/0/t/c/0/1',
  'c/0/0/t/c/0/0/t/c/0/1',
  'c/0/0/t/c/0/1',
  'c/0/1' ]

After:

Output:

[ 'c/0/0/t', 'c/0/1' ]

Code:

/**
 * searches deep into an object recursively...
 * @param {Object} obj object to be searched
 * @param {any} searchValue the value/key to search for
 * @param {boolean} [searchKeys] whether to search object keys as well as values. Defaults to `true` if `serchValue` is a string, `false` otherwise.
 * @returns {string[]} Paths on the object to the matching results
 */
const findPaths = (
  obj,
  searchValue,
  searchKeys = typeof searchValue === "string"
) => {
  const paths = []
  const visited = new Set()
  const notObject = typeof searchValue !== "object"
  const gvpio = (obj, prefix) => {
    for (const [curr, currElem] of Object.entries(obj)) {
      if (searchKeys && curr === searchValue) {
        paths.push(prefix + curr)
      }

      if (typeof currElem === "object") {
        if (visited.has(currElem)) continue
        visited.add(currElem)
        gvpio(currElem, prefix + curr + "/")
        if (notObject) continue
      }
      if (currElem === searchValue) {
        paths.push(prefix + curr)
      }
    }
  }
  gvpio(obj, "")
  return paths
}

Disclaimer:

Be careful though, it won't always include the shortest path!

const obj = {
  t: "t"
}
const obj2 = {
  a: [{ a: [{ a: [{ obj }] }] }],
  b: obj
}
console.log(findPaths(obj2, "t"));
[ 'a/0/a/0/a/0/obj/t', 'a/0/a/0/a/0/obj/t' ] // :(

killants • Feb 4 '19 • Edited

Not used to see many arrow function (without being small ones, in array.map for example) so i got a bit confused with the parameter line :
{ searchKeys = typeof searchValue === "string", maxDepth = 20 } = {}

Would you mind to explain in a few words why it is there? :)

Thank you in advance.

Mihail Malo • Feb 4 '19

Sure, this doesn't depend on it being an arrow function, can be in a function just as well.

This is the equivalent function:

function fn(arg) {
  if (arg === undefined) arg = {}
  let searchKeys = arg.searchKeys
  if (searchKeys === undefined) searchKeys = typeof searchValue === "string"
  let maxDepth = arg.maxDepth
  if (maxDepth === undefined) maxDepth = 20
  /* ... */
}

First, we replace the point access with destructuring:

function fn(arg) {
  if (arg === undefined) arg = {}
  let { searchKeys, maxDepth } = arg
  if (searchKeys === undefined) searchKeys = typeof searchValue === "string"
  if (maxDepth === undefined) maxDepth = 20
  /* ... */
}

Next, we replace the conditional expressions for defaults with defaults in destructuring AND default in parameter:

function fn(arg = {}) {
  const { // we can use const now because we won't be reassigning
    searchKeys = typeof searchValue === "string",
    maxDepth = 20
  } = arg
  /* ... */
}

Finally, to avoid having to think of a name for the short-lived arg binding, we can just YEET it right into the parameter list:

function fn({
  searchKeys = typeof searchValue === "string",
  maxDepth = 20
} = {}) {
  /* ... */
}

We could write it like this:

function fn(
  { 
    searchKeys = typeof searchValue === "string",
    maxDepth = 20
  } = {
    searchKeys: typeof searchValue === "string",
    maxDepth: 20
  }
) {
  /* ... */
}

But that's just more verbose. Destructuring an empty object (if undefined is provided) is perfectly adequate, and gives defaults for all keys.

function fn(
  searchValue, // this is the v below that we are depending on, it has to come first.
  { searchKeys = typeof searchValue === "string", maxDepth = 20 } = {}
) {
  /* ... */
}

killants • Feb 4 '19

Hasn't use "let" before to declare variables, will definitely use now ( Thanks to Sarah Chima for her post "dev.to/sarah_chima/var-let-and-con..." )! :D

Is "for of" more optimized for this kind of methods (recursive), instead of indexed ones ?

I had that "charSeparator" declared inside because at the time i made it i though leaving the option to choose the char used to be received in parameter (but then i just forgot it XD)

That variable "i" .... I just can't even remember why was there ?? :/ My bad !

Tonight i won't be able, but tomorrow right after work, will fix it ! ;)

Thanks a lot for your feedback Mihail :D

Mihail Malo • Feb 4 '19

If you look in the replies to my above comment, I replied to myself (and then replied again to that comment) with new versions of the code.

Lukas Siemon • Apr 21 '19

I had a similar idea last year :) Take a look at object-scan and the filterFn function. Shows where requirements ultimately go haha

killants • May 27 '19

a look where ? sorry not finding "object-scan" as told... Would you mind sharing a link, please?
Thanks

Lukas Siemon • May 27 '19 • Edited

Of course! Here you go github.com/blackflux/object-scan

killants • Feb 4 '19

I added to the gist, the optimized function provided by "Mihail Malostanidis" (dev.to/qm3ster) since it is way more "clean". I leaved the old one so you can compare with my first attempt and see the difference. You can always check Mihail comments on this post since he explains his approach to this.

Big thanks to Mihail for his help!!! :)

Mihail Malo • Feb 3 '19 • Edited

Was a fully single-recursive implementation part of the goal?

killants • Feb 4 '19

Was my way of thinking, i made this method just to fecth the path in some object which value i knew it exists somewhere. :)