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

Question

In the book Python in a Nutshell (2nd Edition) there is an example which uses
old style classes to demonstrate how methods are resolved in classic resolution order and
how is it different with the new order.

I tried the same example by rewriting the example in new style but the result is no different than what was obtained with old style classes. The python version I am using to run the example is 2.5.2. Below is the example:

class Base1(object):  
    def amethod(self): print "Base1"  

class Base2(Base1):  
    pass

class Base3(object):  
    def amethod(self): print "Base3"

class Derived(Base2,Base3):  
    pass

instance = Derived()  
instance.amethod()  
print Derived.__mro__  

The call instance.amethod() prints Base1, but as per my understanding of the MRO with new style of classes the output should have been Base3. The call Derived.__mro__ prints:

(<class '__main__.Derived'>, <class '__main__.Base2'>, <class '__main__.Base1'>, <class '__main__.Base3'>, <type 'object'>)

I am not sure if my understanding of MRO with new style classes is incorrect or that I am doing a silly mistake which I am not able to detect. Please help me in better understanding of MRO.

Stitch

Answer 1

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.

Franciscofranciska

"[the ancestor class] A [is] 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." -- Epiphany! Thanks to this sentence, I can do MRO in my head again. \o/ Thank you very much. – Stimulate

Answer 2

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()

Gaitskell

You should correct your second code : you have put class "I" as first line and also used super so it finding the super class "G" but "I" is first class so it will never able to find "G" class because there is no "G" upper "I" . Put class "I" between "G" and "F" :) – Allenaallenby

The example code is incorrect. super has required arguments. – Sapper

Inside a class definition super() doesn't require arguments. See https://docs.python.org/3/library/functions.html#super – Gaitskell

Your graph theory is needlessly complicated. After step 1, insert edges from classes on the left to classes on the right (in any inheritance list), and then do a topological sort and you're done. – Transceiver

@Transceiver I don't think that's correct. Following my example, wouldn't A C D B E F G H be a valid topological sort? But that's not the resolution order. – Gaitskell

@Ben: No. That is not a valid topo sort because it puts C before B. C is to the right of B so it must appear after. – Transceiver

@Transceiver from the article you linked, it says a topological sort is one "such that for every directed edge uv from vertex u to vertex v, u comes before v in the ordering". How does my counterexample contradict that definition? (Note the examples section of your article where it says "The graph shown to the left has many valid topological sorts") – Gaitskell

@Ben: I said to introduce an edge from B to C ("insert edges from classes on the left to classes on the right"), which requires that B come before C in any toposort. Your alleged counterexample has C before B, so it must not be a real toposort. – Transceiver

@Transceiver ah, I totally missed that. Thanks for clarifying. – Gaitskell

Answer 3

The result you get is correct. Try changing base class of Base3 to Base1 and compare with the same hierarchy for classic classes:

class Base1(object):
    def amethod(self): print "Base1"

class Base2(Base1):
    pass

class Base3(Base1):
    def amethod(self): print "Base3"

class Derived(Base2,Base3):
    pass

instance = Derived()
instance.amethod()


class Base1:
    def amethod(self): print "Base1"

class Base2(Base1):
    pass

class Base3(Base1):
    def amethod(self): print "Base3"

class Derived(Base2,Base3):
    pass

instance = Derived()
instance.amethod()

Now it outputs:

Base3
Base1

Read this explanation for more information.

Lashanda

Answer 4

You're seeing that behavior because method resolution is depth-first, not breadth-first. Dervied's inheritance looks like

         Base2 -> Base1
        /
Derived - Base3

So instance.amethod()

1. Checks Base2, doesn't find amethod.
2. Sees that Base2 has inherited from Base1, and checks Base1. Base1 has a amethod, so it gets called.

This is reflected in Derived.__mro__. Simply iterate over Derived.__mro__ and stop when you find the method being looked for.

Gentleness

I doubt that the reason I get "Base1" as answer is because method resolution is depth-first,I think there is more to it than a depth-first approach. See Denis's example, if it were depth first o/p should have been "Base1". Also refer to the first example in the link you have provided, there also the MRO shown indicates that the method resolution is not just determined by traversing in depth-first order. – Stitch

Sorry the link to the document on MRO is provided by Denis. Please check that, I mistook that you provided me the link to python.org. – Stitch

It's generally depth-first, but there are smarts to handle diamond-like inheritance as Alex explained. – Gentleness