Python: Method Resolution Order
Priyank Pulumati
January 08, 2019Why
When dealing with multi level inheritance and method overriding, Python has an algorithm to determine which class’ method to be called. It’s important to know this when dealing with multi level inheritance scenarios.
What
When the same method is present in multiple classes and all the classes in question are at play then Python’s method resolution order algorithm determines which method gets called.
Problem
class A:
def whoami(self):
print "I am A"
class B:
def whoami(self):
print "I am B"
class C(A, B):
pass
object_c = C()
object_c.whoami()
>> Output ?Note
Python 2.2 was shipped with new style classes. New style classes have super() functionality, new MRO implementation, __slots__ feature and descriptors.
Scenario 1: Python < 2.2 == Old Style Classes Only
Scenario 2: 2.2 < Python < 3.x == Old Style and New Style Classes
Scenario 3: Python > 3.x == New Style Classes Only
In Scenario 2, how to use the different class styles?
class OldExample():
pass # old style
class NewExample(object):
pass # New Style, very easy, just inherit from objectOld Style Classes and Old Algorithm
Old style classes implement an algorithm which I’d like to call the Depth first, left to right (DFLR) path. Let’s look at an example as to what this means.
The above example is called the diamond pattern situation. When we apply DFLR to the diamond pattern let’s see how the MRO looks like. Let’s assume there is an object of class D created and we have called a method on it.
Step 1: Look for method in class D
MRO = [ D ]
Step 2: Look for method in class B (since left to right )
MRO = [ D B ]
Step 3: Look for method in class A ( since depth first )
MRO = [ D B A ]
Step 4: Look for method in class C (since left to right of class D)
MRO = [ D B A C ]
Step 5: Look for method in class A ( since depth first )
MRO = [ D B A C A ]
Step 6: Remove duplicates from the end
MRO = [ D B A C ]
Lets say class C has the whoami() method. Even though the method is available at a much nearer parent the old style MRO approach traverses much more to find whoami.
New Style Classes and New Algorithm
The new style implements a much more complicated algorithm called the C3 algorithm.
The C3 algorithm is more math oriented and might seem complicated in the first glance but let’s break it down step by step.
The C3 algorithm states that the MRO of a class is the “The given class itself plus the merge of the linearization of the parents of the given class plus the parents themselves”
How does that look like?
MRO/ Linearization of C = C + merge(L(p1), L(p2)….L(pn) , p1, p2 ..pn)
Stay with me, let’s look at an example to understand what this means.
First let’s look at some of the terminologies
Merge =
- List of classes C1 C2 C3 C4 …. CN
- C1 is the head, C2 … CN is the tail
- Take the head of the list
- If this head is not in the tail of any of the other lists then add it to the linearization of the class and remove it from the lists in the merge
- Otherwise look at the head of the next list
- Repeat this until all the classes inside the merge are removed or until it’s impossible to find any other heads.
Let’s look at a multi level inheritance tree
L(O) = O (Root Class)
L(D) = DO ( D first then O )
L(E) = EO ( E first then O )
L(F) = FO ( F first then O )
These are the simple cases since its a single level inheritance.
Now comes the more complicated scenarios, linearization of B:
L(B) = B + merge (L(D) + L(E), DE )
~ The class itself + merge ( Linearization of parents of B + list of parents of B )
= B + merge ( DO, EO, DE )
~ Substituting L(D) and L(E) with the lists we found earlier )
= B + D + merge (O, EO, E )
~ Let’s start with the DO list and D, D is not in the tail of any of the other lists so we can add to the linearization of B
= B + D + E + merge ( O, O)
~ We move onto O next, O is present in the tail of the second list, hence its not a good head. So we move to the next list and consider E. E can be linearized because in the third list its all alone.
= B + D + E + O
~ Since O is the only remaining class.
Therefore L(B) = B D E O
In a very similar fashion
L(C) = C + merge(L(D), L(F), DF)
Following the process of L(B)
L(C) = C D F O
Going one level further
L(A) = A + merge( L(B), L(C), BC)
= A + merge ( BDEO, CDFO, BC )
~ Substituting L(B) and L(C) with the lists we found earlier
= A + B + merge ( DEO, CDFO, C )
~ Since B is not present in the tail of any of the lists
= A + B + C + merge ( DEO, DFO )
~ Since D is in the tail of the second list, we move on to the next list, first class, C, its present in the third list and C is the only class, so C can be added to the linearization
= A + B + C + D + merge ( EO, FO )
~ Since D is not present in the tail of any of the lists
= A + B + C + D + E + merge ( O , O )
~ Since E is not present in the tail of any of the lists
= A + B + C + D + E + O
~ Since O is the only remaining class
Therefore L(A) = A B C D E O
Why use New Style Classes / Monotonic Problem
class A: pass
class B: pass
class C(A, B): pass
class D(B, A): pass
class E(C, D): pass
print "Success"
Old Style:
>> Success
New Style:
>> Cannot create a consistent MRO for bases A, BThe tree which we have here should not exist in the first place since it’s wrong.
But in old style classes, this gets executed. Where as in the new style classes Python throws an error.
Takeaway
When dealing with multi level inheritance situations it’s always important to keep in mind the MRO to structure your classes well.
In Python3, the mro() method is available to check the MRO of a given class.
References
https://www.youtube.com/watch?v=cuonAMJjHow