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

Loutag
November 30, 2023
149 views
0 votes
2 Answers

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
      );
    }
  };
}

Answers

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.

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.

There is complexity here because of how your input data is structured, but I’m not sure if you have control over that.
You won’t have any issues with stack size depth since object-scan is entirely recursion free.
The added benefit is that you can now use wildcards and the other extended object-scan syntax in your path selectors!
The library is fully documented, so it’s easy to look up how that part works

import objectScan from 'object-scan';

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

Disclaimer: I’m the author of object-scan

Please signup or login to give your own answer.

Click here to cancel reply.