1
\$\begingroup\$

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
           }
 */
\$\endgroup\$
0

2 Answers 2

3
\$\begingroup\$

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.
\$\endgroup\$
1
\$\begingroup\$
  • 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));

\$\endgroup\$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.