Python Method Resolution Order(MRO) in-case of Multiple-Inheritance¶

What is MRO?¶

MRO stands for Method Resolution Order. It defines an order in which to search for classes to find out which method to use in case of multiple-inheritance. Python till version 2.2 had different MRO algorithm which had some issues and was replaced by a new MRO algorithm from Python 2.3 onwards. We'll below explain how both algorithms work internally along with examples.

Old MRO Algorithm (depth-First, left-to-right) [<= Python v2.2]¶

Python interpreter before python 2.3 used an algorithm called depth-first, left-to-right for method resolution order in case of multiple inheritances where the same method names are present in more than one superclasses.

New MRO Algorithm (C3 Linearization) [> Python v2.2]¶

Python interpreter introduced an algorithm called C3 Linearization for method resolution order in case of multiple inheritances in Python v2.3 as the previous algorithm had some issues.

We'll be explaining algorithms in detail below but before that, we need to understand 2 different kinds of class formats present in Python 2.

Python 2 has 2 kinds of class formats:¶

Old Class format: Old python class format does not inherit from the object class and hence uses the old MRO algorithm.

## Old Class format in Python 2
class A:
    pass
class B:
    pass
class C(A, B):
    pass

New Class format: New python classes inherit from the object class and hence uses the new MRO algorithm. The new class format was introduced to force classes to use the new MRO method in Python 2.

## New Class format in Python 2
class A(object):
    pass
class B(object):
    pass
class C(A, B):
    pass

Python 3 classes inherit from object class by default hence no need to separately add it in parenthesis.¶

As Python 3 classes already inherits from object class by default, it uses the new MRO method to resolve method order in multiple-inheritance.

How Old MRO works in Python?¶

We'll take a simple example to explain how old MRO works. It's based on the concept of looking for a method in depth-first, left-to-right order.

Example 1:

class A:
    def whichclass(self):
        print("I am from A")

class B(A):
    def whichclass(self):
        print("I am from B")

class C(A):
    def whichclass(self):
        print("I am from C")

class D(B, C):
    def whichclass(self):
        print("I am from D")

d = D()
d.whichclass()

In above scenario Old MRO algorithm will go depth-first,left-to-right. It'll follow below order of class for searching of method in it:

$D -> B -> A -> C -> A$

Let’s remove duplicates.

$D -> B -> A -> C$

• We'll first look for the method in class D
• If the method is not present in class D then we'll look for it in class B
• If the method is not present in class B then we'll look for it in class A.
• If the method is not present in class A then we'll look for it in class C.

Example 2:

class A:
    def whichclass(self):
        print("I am from A")

class B(A):
    def whichclass(self):
        print("I am from B")

class C(A):
    def whichclass(self):
        print("I am from C")

class D(C, B):
    def whichclass(self):
        print("I am from D")

d = D()
d.whichclass()

In the above scenario, the old MRO algorithm will go depth-first,left-to-right. It'll follow below order of class for searching of the method in it:

$D -> C -> A -> B -> A$

Let’s remove duplicates

$D -> C -> A -> B$

The problem with the above behavior is that it is not monotonic. Monotonic means that MRO of the subclass is just an extension of MRO of superclass without re-ordering of MROs of super-classes. It can result in different MRO for the same set of class inheritance with a different order. This can create inconsistent behavior as we can see above for example 1 and example 2.(see another example below)

Example of Non-Monotonic Behavior:

In the above scenario, we can clearly see that we can't decide the order of inheritance of classes A and B in class X. To resolve the above problem and introduce monotonicity, a new MRO algorithm was introduced.

How New MRO algorithm works in Python?¶

The new MRO algorithm also called the C3 Linearization algorithm is based on maths algorithm C3.

Few Notations: For a list of classes

$C1 C2 C3 C4 C5....CN$

$C1$ is called head of classes and all other classes from $(C2,...CN)$ are called the tail.

Definition: C3 Linearization defines MRO of any class C as the sum of C plus the merge of the linearizations of the parents and the list of parents.

$L(C(B1,...BN)) = C + merge(L[B1],...,L[Bn], B1...BN)$

Above $B1...BN$ are ancestors of C. The merge is defined as below:

• take the head of the first list ($L[B1]...L[Bn]$)
• If the head is not in the tail of any other lists, then add it to the linearization of C and remove it from the lists in the merge.
• Otherwise look at the head of the next list and take it, if it is a good head.
• repeat the operation until all class are removed or it is impossible to find good heads

Let’s try to understand the above-mentioned steps with simple examples.

class F(object):
    pass
class E(object):
    pass
class D(object):
    pass
class C(D, F):
    pass
class B(D, E):
    pass
class A(B, C):
    pass

We'll below explain MRO for each class.

MRO of O(object),D,E,F is very straight forward as mentioned below:¶

• $L[O] = O$
• $L[D] = D O$
• $L[E] = E O$
• $L[F] = F O$

MRO of B¶

We'll now explain the process for finding MRO of B:

We'll first organize things according to the definition of MRO.

$L[B] = B + merge(L[D], L[E], DE)$

We already have MRO of $L[D]$ and $L[E]$.

$L[B] = B + merge(DO, EO, DE)$

We'll now start with the head of the first list which is D and check whether it exists in the tail of any other list. We can see that it does not hence we can take it out of the list and add it to the linearization of class B. Please make a note that we'll remove D from all other lists as well.

$L[B] = B + D + merge(O, EO, E)$

We'll now take O into consideration. We can see that O exists in the tail of the 2nd list hence we'll ignore it and move on.

We'll now take E into consideration. We can see that E does not exist into the tail of any other list hence can be added to the linearization of B. Please make a note that the last list has only one element E which will be considered head with no tail list.

$L[B] = B + D + E + merge(O, O)$

We'll now take O and it can be added to linearization B because it does not exist in the tail of any other list.

$L[B] = B + D + E + O$

$L[B] = B D E O$

MRO of C¶

We'll now explain the process of deriving MRO for class C.

$L[C] = C + merge(L[D], L[F], DF)$

$L[C] = C + merge(DO, FO, DF)$

$L[C] = C + D + merge(O, FO, F)$

$L[C] = C + D + F + merge(O, O)$

$L[C] = C + D + F + O$

$L[C] = C D F O$

MRO of A¶

We'll now explain the process of deriving MRO for class C.

$L[A] = A + merge(L[B], L[C], BC)$

$L[A] = A + merge(BDEO, CDFO, BC)$

$L[A] = A + B + merge(DEO, CDFO, C)$

$L[A] = A + B + C + merge(DEO, DFO)$

$L[A] = A + B + C + D + merge(EO, FO)$

$L[A] = A + B + C + D + E + merge(O, FO)$

$L[A] = A + B + C + D + E + F + merge(O, O)$

$L[A] = A + B + C + D + E + F + O$

$L[A] = A B C D E F O$

We can force Python 2 classes to use this new MRO algorithm by inheriting from object class in all of them. Python 3 already uses this MRO algorithm as it’s classes by default extend root object class.

Let's understand how the new MRO algorithm will handle the scenario with non-monotonic versions discussed above when explaining the old MRO algorithm.

As we can see that the above code fails for Python 3. New MRO algorithm forces ordering of classes in inheritance to be in the same order for all classes otherwise it'll fail. If we try to run the above example in Python 2 then it'll work because it uses the old algorithm which does not enforce inheritance order.

Let's try another example with parent classes A and B extending object class.

The above example will fail with both Python 2 and Python 3. In Python 2, it'll force a new MRO algorithm because both main parent classes A and B are extending root object class.

Let's try another example with the same ordering and use it to find out MRO.

As we can see, the above examples complete successfully because the order of inheritance for A and B is the same in both C and D which is monotonic and acceptable behavior.

We can also print MRO of all classes by calling method mro() or __mro__ property on each class to see the order.

Note: mro() method is available when you use the new class format in Python 2.

Conclusion¶

It's advisable to use a new MRO algorithm to avoid any discrepancies which can arise when using multiple inheritances in python. New MRO algorithm can be forced in Python 2 by using new class formats as explained above else use Python 3 which already uses the new MRO algorithm. The above explanation of the internal working of the new MRO was for understanding purposes only. One can directly use the mro() method to find out MRO for each class.

References¶

Amit Kumar: Demystifying Python Method Resolution Order - PyCon APAC 2016