TransWikia.com

Handling Circular References Without Recursion

Code Review Asked by Kittoes0124 on January 27, 2021

Despite the many decent answers to this question, one was unable to find an iterative solution. Here’s what I came up with:

Code:

type CircularReferenceHandler = (parentKey: IndexKey, parentValue: Dictionary<IndexKey, any>, childKey: IndexKey, childValue: Dictionary<IndexKey, any>) => void;
type Dictionary<TKey extends IndexKey, TValue> = Record<TKey, TValue>;
type IndexKey = (number | string);

const processCircularReferences = <T extends object>(input: T, handler: CircularReferenceHandler, initialPathValue = "o"): T => {
    const objectStack = [{ k: initialPathValue, v: input, },];
    const objectTracker = new WeakSet<Dictionary<IndexKey, any>>();

    objectTracker.add(input);

    while (objectStack.length) {
        const { k: parentKey, v: parentValue } = objectStack.shift()!;

        for (const [childKey, childValue] of Object.entries(parentValue)) {
            if ((childValue && ("object" === typeof childValue))) {
                if (objectTracker.has(childValue)) {
                    handler(parentKey, parentValue, childKey, childValue);
                }
                else {
                    objectStack.push({ k: `${parentKey}.${childKey}`, v: childValue, });
                    objectTracker.add(childValue);
                }
            }
        }
    }

    return input;
}

Usage:

let o: any = { x: 0, y: 1, };

o.me = {};
o.me.self = o;
o.self = o;

processCircularReferences(o, (pK, pV, cK, _cV) => {
    console.log(`${pK}.${cK}`);

    pV[cK] = undefined;
});

console.log(o);

/*
    [log]: o.me.self
    [log]: o.self
    [log]: { 
               me: { 
                   self: undefined
               },
               self: undefined,
               x: 0,
               y: 1
           }
 */

2 Answers

  • dot-separated path's aren't the best as the keys aren't always alpha-numeric. I would suggest preserving the list of keys instead of trying to format them for the callback. If the callback want's to .join('.') the list, or do something else, it's up to the callback. An added bonus: You can get rid of the initialPathValue parameter since that just has to do with formatting the result, not the business logic.
  • As @tsh mentions, Your algorithm is finding duplicate elements inside the data structure instead of finding circular references (some of the answers to the linked question suffer from the same issue). To fix this, make each entry in your stack keep its own list of its ancestors. To check for a circular dependency, you just need to check if the object you're looking at also appears in one of your ancestors.
  • The callback seems a little weird to me as you're not doing any async logic in here. Why not just return the found results? If you're worried about performance and are wanting to handle the results as soon as you find them, use a generator instead - that way the user of this function can decide if they want all of the results at once (by turning your generator into a list), or to handle them when they're available (by iterating over the generator).

Here's an example (in javascript) that applies the above suggestions:

const topOfStack = array => array[array.length - 1];

function* findCircularReferences(rootObj) {
  const stack = [{ path: [], objectsInPath: [rootObj] }];
  while (stack.length) {
    const { path, objectsInPath } = stack.pop();
    for (const [childKey, childObj] of Object.entries(topOfStack(objectsInPath))) {
      if (typeof childObj !== 'object' || childObj === null) continue;

      const nextStackEntry = {
        path: [...path, childKey],
        objectsInPath: [...objectsInPath, childObj],
      };

      if (objectsInPath.includes(childObj)) {
        yield nextStackEntry;
      } else {
        stack.push(nextStackEntry);
      }
    }
  }
}

// Should find two circular references
const obj1 = { obj3: null };
const obj2 = { obj1, 'obj1-again': obj1 };
const obj3 = { obj2 };
obj1.obj3 = obj3;
console.log([...findCircularReferences(obj1)].map(({ path }) => path));

// Should not find any circular references
const dupEntry = { x: 2 };
console.log([...findCircularReferences([dupEntry, dupEntry])].map(({ path }) => path));

Answered by Scotty Jamison on January 27, 2021

Correctness

Following testcase breaks your code:

const o={};
o.x = o.y = {};

This is due to objectTracker tracks all seen values not all parent values.

Interface Design

  • initialPathValue looks strange to me. The parameter has no meaning to this function as far as I can tell.
  • Dot separated path won't work if any .s in keys. For example: { "a.b": {}, "a": { "b": {} } }. To avoid any confusion, I would suggest use string[] instead.

Implementation

  • objectStack is named as Stack, but you are using it as a Queue. I believe there should be a mistake here. Maybe you want pop() instead of shift().
  • parentValue is a WeakSet. But I cannot find a reason why any objects in it will be garbage collected during the functions life cycle. So maybe a simple Set would fint your requirement.

Answered by tsh on January 27, 2021

Add your own answers!

Ask a Question

Get help from others!

© 2024 TransWikia.com. All rights reserved. Sites we Love: PCI Database, UKBizDB, Menu Kuliner, Sharing RPP