Recursive Filter/Search function

Question

JSFiddle: https://jsfiddle.net/EddTally/jsa69f7r/3/#&togetherjs=zMFpAQcRTt

Those who cannot access JSFiddle:

/**
 * Utilizes recursion to search through an item of any type (currently accepted types are object, array and string)
 * to find if it contains such a value.
 * 
 * @param item
 * @param value
 */
 function filterItem(item, value){
 // Isn't object
 if(typeof item == 'string'){
 return filterString(item, value) 
 } // Is Array
 else if(Array.isArray(item)){
 return filterArray(item, value)
 } // Is Object
 else{
 return filterObj(item, value)
 }
 }
/**
 * Checks if an object contains the value by recursively calling the filterItem function to work it's way through the obj.
 * 
 * @param obj
 * @param value
 */
 const filterObj = (obj, value) => {
 let contains = false;
 for(let [key, val] of Object.entries(obj)){
 if(key.toString().toLowerCase().includes(value)){
 contains = true
 break;
 }else{
 if(filterItem(val, value)){
 contains = true
 break;
 }
 }
 }
 return contains
 }
 /**
 * Used in the recursive function above, goes all the way down until it reaches the base string, then would return 
 * the result of the .includes() funtion.
 * 
 * @param array
 * @param value
 */
 const filterArray = (array, value) => {
 let contains = false;
 for(let x of array){
 if(filterItem(x, value)){
 contains = true
 break;
 }
 }
 return contains
 }
 /**
 * Checks if an string contains the value
 * @param string
 * @param value
 */
 const filterString = (string, value) => {
 return string.toString().toLowerCase().includes(value)
 }
 
 let exampleObj = {"hi": ["five", "twenty", {"11": 44, "eggs": ["egge"]}]}
 console.log(filterItem(exampleObj, "egge")) //Should come back true

I am wondering if this search/filter function is good or not, any potential things I may have missed out on or things to make it better.

Answer 1

From a short review;

• The function name is a bit misleading, it does not filter anything really. Could be named hasValue, or even hasString

• You could also just return the occurrence(s) of where the string is found, this could be more useful

• typeof returns more than you handle

• Personally, I would make the toLowerCase() call only if requested by the caller

• filterObj should call filterString instead of toString().toLowerCase().includes

• Your ratio of comments vs. code is too high in places like this;

   /**
   * Checks if an string contains the value
   * @param string
   * @param value
   **/
   const filterString = (string, value) => {
   return string.toString().toLowerCase().includes(value)
   }
  

My rewrite would be something like this; This one actually filters/returns all matches

function filterString(haystack, needle){
 let type = typeof haystack; //"undefined", "object", "boolean", "number", "bigint", "string", "symbol", "function"
 //JS.. null is an object
 type = haystack===null?"undefined":type;
 
 if(Array.isArray(haystack)){
 return haystack.map(v => filterString(v, needle)).flat();
 }else if(type == "object"){
 return Object.keys(haystack).concat(Object.values(haystack)).map(v => filterString(v, needle)).flat();
 }else if(type == "undefined"){
 return (haystack+'').includes(needle)?[haystack]:[];
 }else{
 return haystack.toString().includes(needle)?[haystack]:[];
 }
}
 
let example = {"hi": [console.log,{ thisIsNull:null, thisIsUndefined:undefined } ,4044, "five", "twenty", {"11": 44, "eggs": ["egge"]}]}
console.log(filterString(example, "egg"));
console.log(filterString(example, "console"));
console.log(filterString(example, 44));
console.log(filterString(example, null));
console.log(filterString(example, undefined));

• konijn: You need Node 11 or higher
• Blindman67: Warning your function will convert functions to strings including the source in the search, EG filterString({test(){var B=0}}, "B")) will return the function test(){var B=0}
• konijn: Yep, I thought that was kind of cool
• Tally: Yes, the function name is misleading. Too much duplicated code, check. In terms of ratio for comments vs code, I enjoy the practice of having the JSDoc popup when I hover over the function I'm using, but I should remove this if the code itself is too small? Thank you.
• konijn: @Tally I would, I seem to parse faster the code than the comment.

Answer 2

Bugs

Your code will throw errors if you include null, or undefined in the data.

And your code does not check for cyclic data structures.

First some review points.

---

Review

Some general review points regarding code style and language feature use.

Use RegExp

Rather than use String.includes convert the search term to a RegExp with the case insensitive flag. You can then test without the need to convert to lower case. Eg const match = new RegExp(value, "gi"); See example for more.

In this case RegExp has additional functionality that will help solve the bugs.

Use === not ==

Alwyas use === (Strict equality) and !== (Strict inequality) rather than == (Equality) and != (Inequality)

const

Use const for variables that do not change. For example the line for(let [key, val] of Object.entries(obj)){ should be for(const [key, val] of Object.entries(obj)){

Reduce code noise

Don't add else / else if statements after you return in the previous statement block.

Example

if (foo) {
 return 0;
} else {
 return 1;
}
// should be
if (foo) {
 return 0;
}
return 1;

Use the language

Your code has not utilized appropriate language features.

You can use Array.some to check the content of an array of at least one match. That includes the array of entries from Object.entries

Rewrite

Thus it could be rewritten as follows..

function filterItem(item, value){
 const match = new RegExp(value, "gi"); 
 return (function filter(item){ 
 if (item === null) { return false }
 if (typeof item !== 'object') { return match.test(item) }
 return Array.isArray(item) ? 
 item.some(item => filter(item)) :
 Object.entries(item).some(([key, item]) => filter(key) || filter(item));
 })(item);
}

The code checks for null assuming that you will not be searching for such. This is needed because null is a type of Object.

The code also does the string match for any item that is not an Object this is because the call RegExp.test will automatically call the item's toString function for you.

---

Cyclic bug

However the above code and your code has a dangerous bug that can cause the page to hang, and chew up a lot of memory (depending on the object being searched)

Take for example the following object..

const a = [];
a[0] = [a];

This will throw a call stack overflow because the data is cyclic.

Example of call stack overflow error

const a = [];
a[0] = [a];
console.log(filterItem(a, "c")); // Will throw 
/****************************************************************/
/* Cleaned up version of original code as example of cyclic bug */
/****************************************************************/
function filterItem(item, value) {
 if (typeof item == 'string') { return filterString(item, value) }
 if (Array.isArray(item)) { return filterArray(item, value) } 
 return filterObj(item, value);
}
function filterObj(obj, value) {
 for (const [key, val] of Object.entries(obj)) {
 if (key.toLowerCase().includes(value)) { return true }
 if (filterItem(val, value)) { return true }
 }
 return false;
}
function filterArray(array, value) {
 for (const item of array) {
 if (filterItem(item, value)) { return true }
 }
 return false;
}
function filterString(string, value) {
 return string.toString().toLowerCase().includes(value);
}

Preventing call stack overflow

It is very important that you always protect against this situation. You can use a Set to check if you have encountered an object before you search it. Each time you search an item you first add it to the set.

Example using Set

const a = []; a[0] = [a]; console.log(filterItem1(a, "c")); // Will throw

The following is protected against cyclic data but be warned. Any time you call a function in JS you run the risk of running out of space on the call stack.

function filterItem(item, value){
 const match = new RegExp(value, "gi"); 
 const tested = new Set();
 return (function filter(item){ 
 if (!tested.has(item)) {
 tested.add(item); 
 if (item === null) { return false }
 if (typeof item !== 'object') { return match.test(item) }
 return Array.isArray(item) ? 
 item.some(item => filter(item)) :
 Object.entries(item).some(([key, item]) => filter(key) || filter(item));
 }
 })(item);
}

You can improve the efficiency by using a WeakSet but you will need to ensure that you don`t try and add strings, numbers and anything that is not an Object

WeakSets do not store the object, only the reference to the hash and thus are quicker and use much less memory.

Example using WeakSet

Note that only objects are added to the weak set.

function filterItem(item, value){
 const match = new RegExp(value, "gi"); 
 const tested = new WeakSet();
 return (function filter(item){ 
 if (!tested.has(item)) {
 if (item === null) { return false }
 if (typeof item !== 'object') { return match.test(item) }
 tested.add(item); 
 return Array.isArray(item) ? 
 item.some(item => filter(item)) :
 Object.entries(item).some(([key, item]) => filter(key) || filter(item));
 }
 })(item);
}

• Tally: Since there will be a vast amount of things in the search I will use the WeakSet version. I've always been scared of RegExp, today I will finally learn. Thank you!

Answer 3

I think you are overcomplicating things. You do not need separate logic for objects and arrays. The following should do the job:

function filterItem(item, value) {
 if (typeof item == 'object' || Array.isArray(item)) {
 for (let i in item) {
 if (filterItem(i, value) || filterItem(item[i], value))
 return true;
 }
 return false;
 }
 if (typeof item == 'string')
 return item.toLowerCase().includes(value.toLowerCase());
 return false;
}