javascriptfunctionrecursioncallstacktail-call-optimization

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


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

Solution

  • 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.