Python Method Resolution Order

In Python, a class can inherit features and attributes from multiple classes and thus, implements multiple inheritance. MRO or Method Resolution Order is the hierarchy in which base classes are searched when looking for a method in the parent class. The syntax is quite simple, as shown below

An implementation of this is shown below

>>>c = C()
>>>dir(c)
['__doc__', '__module__', 'whereiam', 'whoiam']
>>>c.whoiam()
I am a method
>>>c.whereiam()
I am in A

The above example shows that all the properties of classes A and B are in the directory or scope of class C as it inherits from both and can be seen using the ‘dir’ command. ‘dir’ command gives all the names in the current scope. Now, let us look at a much more complex example of multiple inheritance.

An implementation is shown here

>>>d = D()
>>>d.whereiam()
I am in D

Most of us expected this, but what if we comment or remove the whereiam method in D? Let us do this and understand what happens next.

>>>d = D()
>>>d.whereiam()
I am in B

Pretty easy to guess again, B will be invoked. Here’s an exercise for the readers, remove the method from B and check what happens. It is supposed to print “ I am in A”. Again remove the method from A and you will see it prints “ I am in C”. So, how is the method resolution order working? At this point, be patient, I will give a few more examples and you will appreciate this exercise.

Old and New Style Class

Python 3 by default has new classes. While, if you are using Python 2, you still have two options. New style classes are the ones whose first parent inherits from Python root ‘object’ class. New style classes were introduced in python 2.2, so if by any chance you are using Python 2.1 or earlier, you are bound to use old-style classes.

Let’s create an instance of both these classes and try to understand them.

>>>old_style_class = OldStyleClass()
>>>new_style_class = NewStyleClass()
>>>type(OldStyleClass)
<type 'classobj'>
>>>type(NewStyleClass)
<type 'type'>
 >>> old_style_class.__class__
<class __main__.OldStyleClass at 0x7ff8d8e1f460>
>>> new_style_class.__class__
<class '__main__.NewStyleClass'>

As we know, everything is object, even the classes are object of metaclass in python, so a major motivation to roll out new style classes is to provide object model with a full meta model. You can read more about it here.

But why are we discussing it here? It is because method resolution order in both the declaration style is different. Old style classes use DLR or depth-first left to right algorithm whereas new style classes use C3 Linearization algorithm for method resolution while doing multiple inheritance.

DLR Algorithm

When implementing multiple inheritance, Python builds a list of classes to search as it needs to resolve which method has to be called when one is invoked by an instance. As the name suggests, the method resolution order will search the depth-first, then go left to right.

The algorithm first looks into the instance class for the invoked method. If not present, then it looks into the first parent, if that too is not present then parent of the parent is looked into. This continues till the end of the depth of class and finally, till the end of inherited classes. So, the resolution order in our last example will be D, B, A, C, A. But, A cannot be twice present thus, the order will be D, B, A, C.

But, this algorithm is not monotonic and shows anomalous behavior at times, as shown in the example below

According to the DLR algorithm, the method resolution should be E, C, D, B, A. But the interchange of A & B is very ambiguous and it could be the other way round. Therefore, it was observed that monotonicity property is not preserved in this case. Monotonicity of classes in multiple inheritance is explained in the next section.

Samuele Pedroni first discovered an inconsistency between the documented MRO algorithm and the results that were actually observed in real-code. After much discussion, it was decided that Python should adopt the C3 Linearization algorithm described in the paper “A Monotonic Superclass Linearization for Dylan”.

New style classes use C3 Linearization and in python 3 all the classes are by default declared new style. Also, you can’t declare a class E using new style classes. It will fail with the following TypeError as

TypeError: Error when calling the metaclass bases
    Cannot create a consistent method resolution
order (MRO) for bases B, A

An explanation for this is described in the following section.

C3 Linearization Algorithm

Before going further, it is necessary to mention that C3 linearization algorithm enforces following 2 constraints

1. Children precede their parents
2. If a class inherits from multiple classes, they are kept in the order specified in the tuple of the base class.

Also known as C3 super-class linearization, it is based on 3 rules

1. Consistent extended precedence graph, which in short means how base class is extended from the super class. Inheritance graph determines the structure of method resolution order.
2. Preserving local precedence ordering, i.e., visiting the super class only after the method of the local classes are visited.
3. Monotonicity

An MRO is said to be monotonic if C1 precedes C2 in linearization of C, then C1 precedes C2 in the linearization of any subclass of C. Let us understand it with an example

Now, according to the monotonicity property, it is not possible to derive Class E from C, D as A precedes B in C, but in D, B precedes A. Therefore, the resolution order will be ambiguous in E and it will fail with TypeError as shown in the previous section. Let us now try to understand the algorithm.

Before we go further let’s understand few notations

1. C1 C2 C3...CN are the list of classes [C1, C2, C3..CN]
2. Head of the list is the first element C1
3. Tail of the list is the rest of the list C2...CN
4. The sum of the list [C] + [C1, C2...CN] = C + (C1 C2....CN) = C C1 C2....CN

Consider C in a multiple inheritance hierarchy and inherits from classes B1, B2…..BN. To compute the linearization of C, i.e., L[C], the rule says

the linearization of C is the sum of C plus the merge of the linearizations of the parents and list of parents.
L[C(B1...BN)]= C + merge(L[B1] L[B2].....L[BN])
L[object] = object

The merge is computed according to the following rule

take the head of the first list, i.e L[B1][0]; if this head is not in the tail of any of the 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. Then repeat the operation until all the class are removed or it is impossible to find good heads.

This rule ensures that the merge operation preserves the ordering. If it cannot preserve the order, then the merge will not occur. Let us understand this with a simple example of single inheritance.

So, the method resolution order for this will be

L[B(A)] = B + merge(L[A],A)
L[B(A)] = B + L[A]
L[B(A)] = B + A + L[object]

Hence, the order will be B A O. Let us look into an example of multiple inheritance.

The linearization order for 0, D, E and F will be

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

Now let us compute the linearization of B

L[B] = B + merge([L[D], L[E], L[F])
L[B] = B + merge(DO, EO, DE)
L[B] = B + D + merge(EO, DE)
L[B] = B + D + E + L[0]
L[B] = B + D + E + O

So, the resolution order is B D E O. Same goes for C which will be C D E O. Finally, let’s find it for A.

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

Hence, the method resolution order or MRO is A B C D E F O. One can check the MRO for new style classes and in Python 3 as

>>>A.__mro__
(__main__.A,
 __main__.B,
 __main__.C,
 __main__.D,
 __main__.E,
 __main__.F,
 object)

In this way, the linearization works in the case of multiple inheritance. C3 algorithm preserves monotonicity and it is a great improvement from the previous DLR algorithm. By default, this is used for new style classes and Python 3.

For further readings on Python MRO, you can go here.

Happy Python!