Method Resolution Order (MRO) in new-style classes?

Python's method resolution order is actually more complex than just understanding the diamond pattern. To really understand it, take a look at C3 linearization. I've found it really helps to use print statements when extending methods to track the order. For example, what do you think the output of this pattern would be? (Note: the 'X' is suppose to be two crossing edges, not a node and ^ signifies methods that call super())

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

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

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

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

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

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

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


#      A^
#     / \
#    B^  C^
#   /| X
# D^ E^ F^
#  \ | /
#    G

Did you get A B D C E F G?

x = A()
x.m()

After a lot of trial an error, I came up with an informal graph theory interpretation of C3 linearization as follows: (Someone please let me know if this is wrong.)

Consider this example:

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

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

class G(H):
    def m(self):
        print("G")
        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()

# Algorithm:

# 1. Build an inheritance graph such that the children point at the parents (you'll have to imagine the arrows are there) and
#    keeping the correct left to right order. (I've marked methods that call super with ^)

#          A^
#       /  |  \
#     /    |    \
#   B^     C^    D^  I^
#        / | \  /   /
#       /  |  X    /   
#      /   |/  \  /     
#    E^    F^   G^
#     \    |    /
#       \  |  / 
#          H
# (In this example, A is a child of B, so imagine an edge going FROM A TO B)

# 2. Remove all classes that aren't eventually inherited by A

#          A^
#       /  |  \
#     /    |    \
#   B^     C^    D^
#        / | \  /  
#       /  |  X    
#      /   |/  \ 
#    E^    F^   G^
#     \    |    /
#       \  |  / 
#          H

# 3. For each level of the graph from bottom to top
#       For each node in the level from right to left
#           Remove all of the edges coming into the node except for the right-most one
#           Remove all of the edges going out of the node except for the left-most one

# Level {H}
#
#          A^
#       /  |  \
#     /    |    \
#   B^     C^    D^
#        / | \  /  
#       /  |  X    
#      /   |/  \ 
#    E^    F^   G^
#               |
#               |
#               H

# Level {G F E}
#
#         A^
#       / |  \
#     /   |    \
#   B^    C^   D^
#         | \ /  
#         |  X    
#         | | \
#         E^F^ G^
#              |
#              |
#              H

# Level {D C B}
#
#      A^
#     /| \
#    / |  \
#   B^ C^ D^
#      |  |  
#      |  |    
#      |  |  
#      E^ F^ G^
#            |
#            |
#            H

# Level {A}
#
#   A^
#   |
#   |
#   B^  C^  D^
#       |   |
#       |   |
#       |   |
#       E^  F^  G^
#               |
#               |
#               H

# The resolution order can now be determined by reading from top to bottom, left to right.  A B C E D F G H

x = A()
x.m()

The crucial difference between resolution order for legacy vs new-style classes comes when the same ancestor class occurs more than once in the "naive", depth-first approach -- e.g., consider a "diamond inheritance" case:

>>> class A: x = 'a'
... 
>>> class B(A): pass
... 
>>> class C(A): x = 'c'
... 
>>> class D(B, C): pass
... 
>>> D.x
'a'

here, legacy-style, the resolution order is D - B - A - C - A : so when looking up D.x, A is the first base in resolution order to solve it, thereby hiding the definition in C. While:

>>> class A(object): x = 'a'
... 
>>> class B(A): pass
... 
>>> class C(A): x = 'c'
... 
>>> class D(B, C): pass
... 
>>> D.x
'c'
>>> 

here, new-style, the order is:

>>> D.__mro__
(<class '__main__.D'>, <class '__main__.B'>, <class '__main__.C'>, 
    <class '__main__.A'>, <type 'object'>)

with A forced to come in resolution order only once and after all of its subclasses, so that overrides (i.e., C's override of member x) actually work sensibly.

It's one of the reasons that old-style classes should be avoided: multiple inheritance with "diamond-like" patterns just doesn't work sensibly with them, while it does with new-style.