Rewrote the python MRO (C3 method resolution order) in python, just as an exercise in understanding it

pymroinpy.py

# toy example re-implementing C3 method resolution order
# (MRO, as used for python multi-inheritance)
#
# Algorithm snippets in comments come from:
#      https://www.python.org/download/releases/2.3/mro/
# and are notated as [2.3MRO]
#

# A Hier represents a class hierarchy, with a name, and a possibly-empty
# list of bases (each base itself also a Hier).
#
# Examples: two base classes, C1 and C2, that do not inherit:
#
#         C1 = Hier('C1')
#         C2 = Hier('C2')
#
# A subclass with single inheritance:
#
#         D1 = Hier('D1', C1)
#
# A subclass with multiple inheritance:
#
#         D2 = Hier('D2', C1, C2)
#
# Illegal python class hierarchies can be represented as Hiers:
#
#   class X: pass
#   class Y: pass
#   class A(X, Y): pass
#   class B(Y, X): pass
#   class C(A, B): pass     # raises TypeError, no MRO
#
# But this works:
#
#    _O = Hier('object')    # implicit
#    X = Hier('X', _O)
#    Y = Hier('Y', _O)
#    A = Hier('A', X, Y)
#    B = Hier('B', Y, X)
#    C = Hier('C', A, B)
#
# though, of course, L(C) will raise an exception (for the same reason
# that the python interpreter does for this hierarchy). But this is why
# why Hiers are used instead of simply using dummy python classes - so
# these situations can be modeled and explored.
#
class Hier:
    def __init__(self, token, *bases):
        self.token = token
        # allow naked strings in bases (shorthand for Hier('foo'))
        self.bases = [b if hasattr(b, 'token') else Hier(b) for b in bases]

    def __repr__(self):
        if self.bases:
            breps = ", " + ", ".join(repr(x) for x in self.bases)
        else:
            breps = ""
        return f"Hier('{self.token}'{breps})"

    def __eq__(self, other):
        try:
            return self.token == other.token
        except AttributeError:
            return NotImplemented

    def __str__(self):
        if not self.bases:
            return self.token
        btoks = ""
        sep = ""
        for b in self.bases:
            btoks += sep + b.token
            sep = ", "
        return f"{self.token}({btoks})"


def L(c):
    # from [2.3MRO]:
    #         L[C(B1 ... BN)] = C + merge(L[B1], ... L[BN], B1 ... BN)

    # NOTE: the (trivial/degenerate) case of c.bases=[] results in empty
    #       lists, which _merge already has to handle in general anyway.
    return [c] + _merge(*[L(b) for b in c.bases], c.bases)


# Return a list of the tokens instead of a list of the Hiers; essentially
# this is a "list of strings" version of L() better for printing results
def sL(c):
    return [x.token for x in L(c)]


def _strict_find_good_head(hierlists):
    # from [2.3MRO] -- (paraphrasing)
    #   Find the first "good" head, defined as: the first head
    #   of a list that is not in the tail of any (other) list
    #
    # Question: [2.3MRO] explicitly says (quoting):
    #                if this head is not in the tail of any of
    #                the other lists, then add it to the linearization
    # **NOTE THIS**    ^^^^^^^^^
    #
    # Not sure how important this 'other lists' qualifier really is.
    # A list of subclasses of a class cannot (well, should not) contain
    # the class itself. Ignoring that qualifier would simplify this code.
    for i, cx in enumerate(hierlists):
        otherlists = (x for j, x in enumerate(hierlists) if i != j)
        candidate, *_ = cx
        if all(candidate not in tail for _, *tail in otherlists):
            return candidate
    raise ValueError("Could not complete merge")


# version of _find_good_head that ignores the "other lists" qualifier
def _lax_find_good_head(hierlists):
    for candidate, *_ in hierlists:
        if all(candidate not in tail for _, *tail in hierlists):
            return candidate
    raise ValueError("Could not complete merge")


_find_good_head = _lax_find_good_head


def _merge(*lists):
    merged = []

    # loop until nothing but empties are left
    while lists := [lz for lz in lists if lz]:

        # from [2.3MRO] --
        #   find a good head, use it, remove it from all lists
        #   If can't find a good head, can't resolve an MRO
        #        ... ValueError raised in _find_good_head
        #   Then remove this one from all candidate lists.
        #   When nothing but empties are left (handled in 'while'), done.

        head = _find_good_head(lists)
        merged.append(head)
        lists = [[b for b in lz if b != head] for lz in lists]

    return merged


if __name__ == "__main__":
    import unittest

    class TestMethods(unittest.TestCase):
        def test1(self):
            # some trivial cases
            _O = Hier('_O')
            self.assertEqual(sL(_O), ['_O'])

            A = Hier('A', _O)
            self.assertEqual(sL(A), ['A', '_O'])

        def test2(self):
            # test case taken directly from [2.3MRO]
            _O = Hier('_O')
            F = Hier('F', _O)
            E = Hier('E', _O)
            D = Hier('D', _O)
            C = Hier('C', D, F)
            B = Hier('B', D, E)
            A = Hier('A', B, C)
            self.assertEqual(sL(A), ['A', 'B', 'C', 'D', 'E', 'F', '_O'])

        def test3(self):
            # test case taken directly from [2.3MRO]
            # Same as prior test except B is (E, D) instead of (D, E)
            # This changes the result, per discussion in [2.3MRO]
            _O = Hier('_O')
            F = Hier('F', _O)
            E = Hier('E', _O)
            D = Hier('D', _O)
            C = Hier('C', D, F)
            B = Hier('B', E, D)
            A = Hier('A', B, C)
            self.assertEqual(sL(A), ['A', 'B', 'E', 'C', 'D', 'F', '_O'])

        def test4(self):
            # test case taken directly from [2.3MRO]
            _O = Hier('_O')
            A = Hier('A', _O)
            B = Hier('B', _O)
            C = Hier('C', _O)
            D = Hier('D', _O)
            E = Hier('E', _O)
            K1 = Hier('K1', A, B, C)
            K2 = Hier('K2', D, B, E)
            K3 = Hier('K3', D, A)
            Z = Hier('Z', K1, K2, K3)
            self.assertEqual(sL(Z), ['Z', 'K1', 'K2', 'K3',
                                     'D', 'A', 'B', 'C', 'E', '_O'])

        def test5(self):
            # test case taken directly from [2.3MRO]
            _O = Hier('_O')
            X = Hier('X', _O)
            Y = Hier('Y', _O)
            A = Hier('A', X, Y)
            B = Hier('B', Y, X)
            self.assertEqual(sL(A), ['A', 'X', 'Y', '_O'])
            self.assertEqual(sL(B), ['B', 'Y', 'X', '_O'])
            C = Hier('C', A, B)
            self.assertRaises(ValueError, sL, C)

        def test6(self):
            # test case taken directly from [2.3MRO]
            F = Hier('F')
            E = Hier('E', F)
            G = Hier('G', F, E)
            # this is ambiguous, so raises an exception
            self.assertRaises(ValueError, sL, G)

            # interestingly, this example is one of the very few that
            # is affected by the inclusion of B1 ... BN as the last list
            # in the expansion:
            #        L[C(B1 ... BN)] = C + merge(L[B1] ... L[BN], B1 ... BN)
            # This was discovered when earlier versions of the code
            # inadvertently omitted that argument yet it made no
            # difference in any of the other tests (!)
            #
            # To demonstrate that... :
            def badL(c):
                # leaves out the final B1 .. BN list compared to correct L
                return [c] + _merge(*[L(b) for b in c.bases])

            # this will return something, whereas the correct L bombs:
            self.assertTrue(badL(G))     # i.e., it returns something

        def test7(self):
            # test case taken from C3 OOPSLA paper
            Pane = Hier('Pane')
            ScrollingMixin = Hier('ScrollingMixin')
            EditingMixin = Hier('EditingMixin')
            ScrollablePane = Hier('ScrollablePane', Pane, ScrollingMixin)
            EditablePane = Hier('EditablePane', Pane, EditingMixin)
            ESPane = Hier('ESPane', ScrollablePane, EditablePane)
            self.assertEqual(sL(ESPane), ['ESPane',
                                          'ScrollablePane',
                                          'EditablePane',
                                          'Pane',
                                          'ScrollingMixin',
                                          'EditingMixin'])

        def test8(self):
            # test case taken from C3 OOPSLA paper
            Obj = Hier('Obj')
            Boat = Hier('Boat', Obj)
            DayBoat = Hier('DayBoat', Boat)
            WheelBoat = Hier('WheelBoat', Boat)
            EngineLess = Hier('EngineLess', DayBoat)
            SmallMultiHull = Hier('SmallMultiHull', DayBoat)
            PedalWheel = Hier('PedalWheel', EngineLess, WheelBoat)
            SmallCat = Hier('SmallCat', SmallMultiHull)
            Pedalo = Hier('Pedalo', PedalWheel, SmallCat)
            self.assertEqual(sL(Pedalo), ['Pedalo',
                                          'PedalWheel',
                                          'EngineLess',
                                          'SmallCat',
                                          'SmallMultiHull',
                                          'DayBoat',
                                          'WheelBoat',
                                          'Boat',
                                          'Obj'])

        def test9(self):
            # test case taken from stackoverflow (lol, where else?!?)
            _O = Hier('_O')
            A = Hier('A', _O)
            B = Hier('B', A)
            C = Hier('C', A)
            D = Hier('D', A)
            E = Hier('E', B, C)
            F = Hier('F', B, D)
            G = Hier('G', C, D)
            H = Hier('H', E, F, G)
            self.assertEqual(sL(H), ['H', 'E', 'F', 'B', 'G',
                                     'C', 'D', 'A', '_O'])

        # try the tests again with the other find_good_head algorithm
        def test_alternate_head(self):
            # yeah, this is a questionable hack, justified in the
            # name of "all of this is just for demonstration/learning"
            global _find_good_head
            prev = _find_good_head
            if _find_good_head == _strict_find_good_head:
                _find_good_head = _lax_find_good_head
            else:
                _find_good_head = _strict_find_good_head

            for test in [f for f in dir(self) if f.startswith('test')]:
                if test != 'test_alternate_head':
                    getattr(self, test)()

            _find_good_head = prev

    unittest.main()