Javascript maximum call stack size even though recursive function call itself with an accumulator

Question

I have an object whose value can be any type.

  const data = {
    a: { aa: 50, ab: 'hello', ac: 'xx_1' },
    b: 50,
    c: [
      { ca: 100, cb: 'by', cc: 'xx_2' },
      { ca: 101, cb: 'by1', cc: 'xx_3' },
    ],
    d: [],
    e: {
      ea: 50,
      eb: ['xx_1', 'xx_4'],
    },
}

I need to browse through it and replace values that match with specific pattern. To do that I use a recursive function (exportContractFormatter) and to replace the values I use a non-recursive function (exportContractConverter). To avoid maximum call stack size I use an accumulator (acc) when I do the recursive call. To update the accumulator, I use lodash (update) method, based on the path.

export function exportContractFormatter(
  data: any[],
  exportContractConverter: (data:any, path:string[])=>any,
  acc: Record<string, any> = {},
  path: string[] = [],
  level = [] as number[]
): any {

  if (data.length === 0) return acc;
  const head = data[0];
  const tail = data.slice(1);

  // enter only if not empty array or not empty object
  if (
    typeof head[1] === 'object' &&
    head[1] !== null &&
    ((Array.isArray(head[1]) && head[1].length > 0) ||
      (!Array.isArray(head[1]) && Object.keys(head[1]).length > 0))
  ) {
    //if array use index as key
    const valueFormatted = Array.isArray(head[1])
      ? head[1].map((item, index) => [index, item])
      : Object.entries(head[1]);

    //initialize object or array thank to path
    update(acc, path.concat(head[0]).join('.'), (n) => (Array.isArray(head[1]) ? [] : {}));

    //recurse with one deeper level
    return exportContractFormatter(
      [...valueFormatted, ...tail],
      exportContractConverter,
      acc,
      [...path, head[0]],
      [...level, valueFormatted.length * -1]
    );
  } else {
    if (typeof head[1] === 'object' && head[1] !== null) {
      //empty object or array, no need to convert value
      update(acc, path.concat(head[0]).join('.'), (n) => (Array.isArray(head[1]) ? [] : {}));
    } else {
      //convert value
      update(acc, path.concat(head[0]).join('.'), (n) => {
        return exportContractConverter(head[1], path.concat(head[0]));
      });
    }
    const [newLevel, newPath] = getLevelAndPath(level, path);
    //recurse same level or shallower
    return exportContractFormatter(tail, exportContractConverter, acc, newPath, newLevel);
  }
}

 exportContractFormatter(Object.entries(data), exportContractConverter);

The problem is, if my object is too big (a lot of nested objects or arrays), I get the maximum call stack size error. Something weird, if I trigger twice the recursion : the first fails, the second succeeds.

Do you have any idea about how to deal with this problem ? Thank a lot for your help

More details :

const referentialData = {
    ref_1: [
      {
        value: 'xx_1',
        displayText: 'CONVERTED_1',
      },
      {
        value: 'xx_2',
        displayText: 'NO',
      },
      {
        value: 'xx_3',
        displayText: 'NO',
      },
      {
        value: 'xx_4',
        displayText: 'CONVERTED_4',
      },
    ],
    ref_2: [
      {
        score_id: 'xx_1',
        label: 'NO',
      },
      {
        score_id: 'xx_2',
        label: 'CONVERTED_2',
      },
      {
        score_id: 'xx_3',
        label: 'CONVERTED_3',
      },
    ],
};
const usages = [
    {
      referential_name: 'ref_1',
      path: 'a.ac',
      widget_name: 'widget_1',
      kind: 'simple_referential',
    },
    {
      referential_name: 'ref_2',
      path: 'c.cc',
      widget_name: 'widget_2',
      kind: 'article',
    },
    {
      referential_name: 'ref_1',
      path: 'e.eb',
      widget_name: 'widget_1',
      kind: 'simple_referential',
    },
];
const result = {
    a: { aa: 50, ab: 'hello', ac: 'CONVERTED_1' },
    b: 50,
    c: [
      { ca: 100, cb: 'by', cc: 'CONVERTED_2' },
      { ca: 101, cb: 'by1', cc: 'CONVERTED_3' },
    ],
    d: [],
    e: {
      ea: 50,
      eb: ['CONVERTED_1', 'CONVERTED_4'],
    },
};
const exportContractConverter = exportContractConverterGenerator(referentialData, usages);

export function exportContractConverterGenerator(
  referentialData: Record<string, any[]>,
  usages: Array<Record<string, any>>
) {
  return (data: any, path: string[]): any => {
    if (!data || !usages) return data;
    const _path = path.filter((item) => typeof item !== 'number').join('.');

    const found = usages?.find((item) => item?.path === _path);

    if (!found || !found.referential_name) return data;
    if (found.kind === 'article') {
      return (
        (referentialData[found.referential_name]).find(
          (item) => item.score_id === data
        )?.label || data
      );
    } else {
      return (
        (referentialData[found.referential_name]).find(
          (item) => item.value === data
        )?.displayText || data
      );
    }
  };
}

Answer 1

Here is a solution using object-scan. A library will make your code a bit more maintainable, especially since it abstracts all the traversal logic.

1. There is complexity here because of how your input data is structured, but I'm not sure if you have control over that.

2. You won't have any issues with stack size depth since object-scan is entirely recursion free.

3. The added benefit is that you can now use wildcards and the other extended object-scan syntax in your path selectors!

4. The library is fully documented, so it's easy to look up how that part works

.as-console-wrapper {max-height: 100% !important; top: 0}

<script type="module">
import objectScan from 'https://cdn.jsdelivr.net/npm/object-scan@19.0.5/lib/index.min.js';

const data = {
  a: { aa: 50, ab: 'hello', ac: 'xx_1' },
  b: 50,
  c: [
    { ca: 100, cb: 'by', cc: 'xx_2' },
    { ca: 101, cb: 'by1', cc: 'xx_3' }
  ],
  d: [],
  e: {
    ea: 50,
    eb: ['xx_1', 'xx_4']
  }
};

// / -----------------

const referentialData = {
  ref_1: [
    { value: 'xx_1', displayText: 'CONVERTED_1' },
    { value: 'xx_2', displayText: 'NO' },
    { value: 'xx_3', displayText: 'NO' },
    { value: 'xx_4', displayText: 'CONVERTED_4' }
  ],
  ref_2: [
    { score_id: 'xx_1', label: 'NO' },
    { score_id: 'xx_2', label: 'CONVERTED_2' },
    { score_id: 'xx_3', label: 'CONVERTED_3' }
  ]
};
const usages = [
  { referential_name: 'ref_1', path: 'a.ac', widget_name: 'widget_1', kind: 'simple_referential' },
  { referential_name: 'ref_2', path: 'c.cc', widget_name: 'widget_2', kind: 'article' },
  { referential_name: 'ref_1', path: 'e.eb', widget_name: 'widget_1', kind: 'simple_referential' }
];

const rewriter = objectScan(usages.map(({ path }) => path), {
  useArraySelector: false,
  rtn: 'bool',
  filterFn: ({ matchedBy, value, parent, property }) => {
    let result = false;
    const relevantUsages = usages.filter(({ path }) => matchedBy.includes(path));
    for (let i = 0; i < relevantUsages.length; i += 1) {
      const { referential_name: refName, kind } = relevantUsages[i];
      const [nameField, valueField] = kind === 'article'
        ? ['score_id', 'label']
        : ['value', 'displayText'];
      const replacements = referentialData[refName];
      for (let j = 0; j < replacements.length; j += 1) {
        const repl = replacements[j];
        if (repl[nameField] === value) {
          parent[property] = repl[valueField];
          result = true;
          // return here if only first replacement needed
          // ...
        }
      }
      // return here if only first usage needed
      // ...
    }
    return result;
  }
});

console.log(rewriter(data)); // returns true because data has been changed
// => true
console.log(data);
/* => {
    a: { aa: 50, ab: 'hello', ac: 'CONVERTED_1' },
    b: 50,
    c: [
      { ca: 100, cb: 'by', cc: 'CONVERTED_2' },
      { ca: 101, cb: 'by1', cc: 'CONVERTED_3' }
    ],
    d: [],
    e: {
      ea: 50,
      eb: [ 'CONVERTED_1', 'CONVERTED_4' ]
    }
} */

console.log(rewriter(data)); // returns false because no data has been changed
// => false
</script>

Disclaimer: I'm the author of object-scan

Answer 2

I found the initial code hard to follow and created my own approach. It should not have any recursion depth issues, unless your object itself is deeper than the that limit. If so, you have bigger problems to worry about!

I found traversing your configuration data difficult, so my solution converts it to the following pathMap format before returning a function which will that data and your object to create the results:

{
    "a.ac": {xx_1: "CONVERTED_1", xx_2: "NO", xx_3: "NO", xx_4: "CONVERTED_4"},
    "c.cc": {xx_1: "NO", xx_2: "CONVERTED_2", xx_3: "CONVERTED_3"},
    "e.eb": {xx_1: "CONVERTED_1", xx_2: "NO", xx_3: "NO", xx_4: "CONVERTED_4"}
}

I have in my personal library several utility functions which make writing this easier. pathEntries is much like Object.entries except that instead of string keys, it uses an array of strings and integers representing the full path to a node, turning you sample input into something like this:

[
  [["a", "aa"], 50], 
  [["a", "ab"], "hello"], 
  [["a", "ac"], "xx_1"], 
  [["b"], 50], 
  [["c", 0, "ca"], 100], 
  // ...
  [["e", "eb", 0], "xx_1"], 
  [["e", "eb", 1], "xx_4"]
]

hydrate does the reverse, taking an array of these path entries and turning them back into an object, using the setPath utility function. My version uses these by calling pathEntries, mapping the result into new versions based on what's in pathMap and in the values, then calling, hydrate. It looks like this:

// Utility functions
const pathEntries = (obj) => Object (obj) === obj
  ? Object .entries (obj) .flatMap (([k, x]) => pathEntries (x) .map (
      ([p, v]) => [[Array .isArray (obj) ? Number (k) : k, ... p], v] 
    )) 
  : [[[], obj]]

const setPath = ([p, ...ps]) => (v) => (o) =>
  p == undefined ? v : Object .assign (
    Array .isArray (o) || Number .isInteger (p) ? [] : {},
    {...o, [p]: setPath (ps) (v) ((o || {}) [p])}
  )

const hydrate = (xs) =>
  xs .reduce ((a, [p, v]) => setPath (p) (v) (a), {})

// Main function
const convert = (
  referentialData, usages,
  mappings = Object.fromEntries(Object.entries(referentialData).map(
      ([k, v]) => [k, Object.fromEntries(v.map(Object.values))]
  )),
  pathMap = Object.fromEntries(usages.map(
    ({path, referential_name}) => [path, mappings[referential_name]]
  ))
) => (o) => hydrate(pathEntries(o).map(([p, v], _, __, 
  path = p.filter(s => typeof s !== 'number').join('.')
) => path in pathMap
  ? [p, pathMap[path][v] || v]
  : [p, v]
))

// Sample data
const referentialData = {ref_1: [{value: "xx_1", displayText: "CONVERTED_1"}, {value: "xx_2", displayText: "NO"}, {value: "xx_3", displayText: "NO"}, {value: "xx_4", displayText: "CONVERTED_4"}], ref_2: [{score_id: "xx_1", label: "NO"}, {score_id: "xx_2", label: "CONVERTED_2"}, {score_id: "xx_3", label: "CONVERTED_3"}]}
const usages = [{referential_name: "ref_1", path: "a.ac", widget_name: "widget_1", kind: "simple_referential"}, {referential_name: "ref_2", path: "c.cc", widget_name: "widget_2", kind: "article"}, {referential_name: "ref_1", path: "e.eb", widget_name: "widget_1", kind: "simple_referential"}]
const data = {a: {aa: 50, ab: "hello", ac: "xx_1"}, b: 50, c: [{ca: 100, cb: "by", cc: "xx_2"}, {ca: 101, cb: "by1", cc: "xx_3"}], d: [], e: {ea: 50, eb: ["xx_1", "xx_4"]}}

// Demo
console.log(convert(referentialData, usages)(data))

.as-console-wrapper {max-height: 100% !important; top: 0}

The only other thing to call out is that the pathEntry format is designed to capture the full structure of the object, but your rules run equally for all elements of an array; you don't need the array indices to apply a rule. To handle this, we filter out the numbers representing array indices before we join the path into a string. So ['c', 0, 'a'] becomes c.a instead of c.0.a; this is the key we use to look up in pathMap.

Note that this is a two-call API. We first pass the two configuration pieces, and then to the resulting function we pass our object. If we're going to do this multiple times, this helps by letting us create a reusable function from the configuration and apply it to many objects.

---

This does not answer why your function is running into depth limits. I have no idea. But I didn't look deeply. Between this and the other answers, you should be able to find something that works how you like.

Answer 3

There's a much simpler code for achieving your goal, please see the script below:

  const data = {
        a: { aa: 50, ab: 'hello', ac: 'xx_1' },
        b: 50,
        c: [
            { ca: 100, cb: 'by', cc: 'xx_2' },
            { ca: 101, cb: 'by1', cc: 'xx_3' },
        ],
        d: [],
        e: {
            ea: 50,
            eb: ['xx_1', 'xx_4'],
        },
    };

    const isObject = target => target instanceof Object;

    const traverse = (target, process) => {
        Object.entries(target).forEach(([key, value]) => {
            if (isObject(value)) {
                traverse(value, process);
            }
            else {
                const set = (value) => target[key] = value;
                process(key, value, set);
            }
        });
    };

    traverse(data, (key, value, set) => {
        // can be improved by passing an array of {key, value, newVaue}
        if (key === "cc" && value === "xx_2") {
            set("xx_2_replaced");
        }

        if (key === "ac" && value === "xx_1"){
            set("xx_1_replaced");
        }
    });

    console.info(data.c[0].cc);
    console.info(data.a.ac);

I'd strongly recommend learning JS before looking into TS, the power of the latter can lead to confusion sometime.