How to find nearest common ancestor class of two objects?

Question

^{This question is basically the JavaScript equivalent of How do I find the nearest common superclass of two non-interface classes}

TL;DR: Given two objects and an extensive inheritance setup, how can I find their most "recent" common class?

---

Suppose, there is a couple of related classes in the program, and their hierarchy is as follows:

class A {}

class B extends A {}

class C extends B {}

class D extends B {}

class E extends D {}

Given a reference to an instance of C and an instance of E, I want to get a reference to B, because this is their closest common ancestor.

function getClosestCommonAncestorClass(c: C, e: E): typeof B;

^{Link to TypeScript playground}

How do I do that?

Answer 1

This is a tree problem (Lowest common ancestor), where edges are determined by Object.getPrototypeOf.

The idea is to get the paths from the root for the two given nodes, and then compare the entries in those two paths starting at the root. The last node that is the same is the common node. Finally get the constructor of that prototype object, which is the "class":

function getPath(o) {
    const path = [];

    while (o) {
        path.push(o);
        o = Object.getPrototypeOf(o);
    }

    return path.reverse();
}

function getClosestCommonAncestorClass(x, y) {
    const xPath = getPath(x);
    const yPath = getPath(y);
    const steps = Math.min(xPath.length, yPath.length);

    let i = 0;

    for (; i < steps; i++) {
        if (xPath[i] !== yPath[i]) break;
    }

    return xPath[i - 1]?.constructor;
}

class A {}
class B extends A {}
class C extends B {}
class D extends B {}
class E extends D {}

console.log(getClosestCommonAncestorClass(new C(), new E())); // class B

Answer 2

1. Walk each of the prototypes of left and right up the chain and keep track of all visited prototypes.
2. At each step see if you have already visited this prototype.
3. At some point there would be a crossover hit upon a prototype that is common to both. Return it.
4. (edge case) Where there truly are no common prototypes in the chain (most likely because at least one object is created via Object.create(null)) then return null as the common ancestor;

function getClosestCommonAncestorClass(left, right) {
  let protoLeft = Object.getPrototypeOf(left);
  let protoRight = Object.getPrototypeOf(right);
  
  const visited = new Set();
  while (protoLeft !== null || protoRight !== null) {
    if (protoLeft === protoRight)
      return protoLeft?.constructor;

    visited
      .add(protoLeft)
      .add(protoRight);
      
    protoLeft = protoLeft && Object.getPrototypeOf(protoLeft);
    protoRight = protoRight && Object.getPrototypeOf(protoRight);
    
    if (protoLeft !== null && visited.has(protoLeft))
      return protoLeft.constructor;
      
    if (protoRight !== null && visited.has(protoRight))
      return protoRight.constructor;
  }
  
  return null;
}

class A {}
class B extends A {}
class C extends B {}
class D extends C {}
class E extends B {}

const c = new C();
const e = new E();

const closestCommonAncestor = getClosestCommonAncestorClass(c, e);
console.log(closestCommonAncestor.name);
console.assert(closestCommonAncestor.name === "B");

const d = new D();

const closestCommonAncestor2 = getClosestCommonAncestorClass(d, e);
console.log(closestCommonAncestor2.name);
console.assert(closestCommonAncestor2.name === "B");

const closestCommonAncestor3 = getClosestCommonAncestorClass(d, c);
console.log(closestCommonAncestor3.name);
console.assert(closestCommonAncestor3.name === "C");

class Z {};
const z = new Z();

const closestCommonAncestor4 = getClosestCommonAncestorClass(z, d);
console.log(closestCommonAncestor4.name);
console.assert(closestCommonAncestor4 === Object);

const nullObj = Object.create(null);
const closestCommonAncestor5 = getClosestCommonAncestorClass(nullObj, d);
console.log(closestCommonAncestor5);
console.assert(closestCommonAncestor5 === null);

Answer 3

Both @trincot's and @VLAZ's answers have their pros and cons, but I think I have achieved to amalgamate them together.

The approach here would be: for each parent class (closest to furthest) of one object (doesn't matter which one), check if another object is an instance of that class; if that's true, return the class; otherwise if the list is exhausted, return null.

Note, that getParentClassesOf is defined as a generator to avoid creating unused values (further common classes are not needed), but it should be easy enough to implement it as a plain array-returning function if needed.

function * getParentClassesOf(object) {
    let current = object;
    let prototype;

    while (prototype = Object.getPrototypeOf(current)) {
        yield prototype.constructor; // or classes.push(prototype.constructor)

        current = prototype;
    }
}

function getClosestCommonAncestorClass(left, right) {
    for (const parentClass of getParentClassesOf(left))
        if (right instanceof parentClass)
            return parentClass;

    return null;
}

function * getParentClassesOf(object) {
    let current = object;
    let prototype;

    while (prototype = Object.getPrototypeOf(current)) {
        yield prototype.constructor; // or classes.push(prototype.constructor)

        current = prototype;
    }
}

function getClosestCommonAncestorClass(left, right) {
    for (const parentClass of getParentClassesOf(left))
        if (right instanceof parentClass)
            return parentClass;

    return null;
}

// *** 

class A {}
class B extends A {}
class C extends B {}
class D extends B {}
class E extends D {}

const closestCommonAncestor = getClosestCommonAncestorClass(new C(), new E());
console.log(closestCommonAncestor.name);
console.assert(closestCommonAncestor.name === "B");

See more examples