Does Python's MRO, C3 linearization work depth-first? Empirically it does not

Question

I was reading Python Multiple Inheritance (on Programiz) and then I found this StackOverflow question, Method Resolution Order (MRO) in new-style classes? but in this question some programmers like Alex Martelli said it uses the depth-first approach, and I have a doubt.

Example:

class H():
    def m(self):
        print("H")

class G(H):
    def m(self):
        print("G")
        super().m()

class I(G):
    def m(self):
        print("I")
        super().m()


class F(H):
    def m(self):
        print("F")
        super().m()

class E(H):
    def m(self):
        print("E")
        super().m()

class D(F):
    def m(self):
        print("D")
        super().m()

class C(E, F, G):
    def m(self):
        print("C")
        super().m()

class B():
    def m(self):
        print("B")
        super().m()

class A(B, C, D):
    def m(self):
        print("A")
        super().m()

x = A()
x.m()

So if I build a graph based on the MRO then according to depth-first it should follow this:

and path should be:

A-->B-->C-->E-->F-->G-->D-->H

But if you run above code you will get:

A
B
C
E
D
F
G
H

Because it is following this path:

A-->B-->C-->E-->D-->F-->G-->H

Now I have confusion about node "D" or class "D" in depth first it comes when earlier and in MRO it comes later.

What's going on here?

Answer 1

and path should be:

A-->B-->C-->E-->F-->G-->D-->H

F cannot come before D - that would be a contradiction - see class D.

The way the C3 linearization algorithm works, you have to linearize the parents, then, as long as there isn't a contradiction, you can linearize the child. So I linearized these one at a time, starting with the parents. Most are trivial until we get to C and then A:

class PrettyType(type):
    """make the repr of the classes look nice when finally listed"""
    def __repr__(self):
        return self.__name__

# subclasses of O will also have the metaclass:
class O(metaclass=PrettyType): 'O, object'

class H(O): 'H, O, object'
# H's parent is O

class G(H): 'G, H, O, object'
# G's linearization is itself followed by its parent's linearization.

class I(G): 'I, G, H, O, object'
# I's linearization is I followed by G's

class F(H): 'F, H, O, object'

class E(H): 'E, H, O, object'

class D(F): 'D, F, H, O, object'

class C(E, F, G): 'C, E, F, G, H, O, object' 
# C's linearization is C followed by a consistent linearization of 
# its parents, left to right. 
# First C, then E - then you might be tempted to put H after E,
# but H must come after F and G (see class F and G)
# so we try F's linearization, noting that H comes after G,
# so we try G's linearization, H then consistently comes next, then object

class B(O): 'B, O, object'

And A is:

class A(B, C, D): 'A, B, C, E, D, F, G, H, O, object'
# final complex case -      ^--^ can't go from E to F 
#                                D must come before F (see class D)
#                              ^--^ After D, can do F, 
#                                    then finish with C's MRO 
#                                    with no contradictions 

The 3 Criteria are, as I would paraphrase it:

1. The parents MRO's remain consistent
2. The local MRO's remain consistent
3. No cyclicality

The algorithm, as I would put it, is that you respect parents left to right, but go depth first unless you would get to a shared parent blocked by a child (e.g. F blocked by it's child, D) in which case you would look for other candidates (D then, not being a contradiction, is fine, then you can select F and the remainder of C's MRO.)

>>> A.mro()
[A, B, C, E, D, F, G, H, O, <class 'object'>]

Direct linearization without linearizing the parents first

We can work through the linearization by avoiding contradictions.

Again,

• Left to Right
• Depth first - Unless shared parent is blocked (must be able to come back)
• No cyclical relationship allowed