DLR Algorithm
The DLR (Depth-Limited Recursion) algorithm is one of the first ways Python determined the MRO in the context of multiple inheritance. This approach is simple and checks each parent class from left to right in a depth-first manner, meaning it first checks the method of the immediate parent and then recursively checks the method of the next parent.
However, the DLR algorithm had its limitations, especially in complex hierarchies. It often resulted in a method resolution order that didn’t always align with what a programmer might expect in cases of conflicting methods.
Example for DLR Algorithm
Python provides a useful tool for inspecting the MRO of a class hierarchy. We can access the MRO by using the `mro()` method or the `__mro__` attribute on a class. For example:
class A:
pass
class B(A):
pass
class C(A):
pass
class D(B, C):
pass
print(D.mro())
print(D.__mro__)
You can also try this code with Online Python Compiler
Output:
[<class '__main__.D'>, <class '__main__.B'>, <class '__main__.C'>, <class '__main__.A'>, <class 'object'>]
(<class '__main__.D'>, <class '__main__.B'>, <class '__main__.C'>, <class '__main__.A'>, <class 'object'>)
In this example, we define four classes: A, B, C, & D. Class B & C inherit from A, while D inherits from both B & C. When we print the MRO of class D using `mro()` or `__mro__`, we get the linearized order in which methods & attributes will be searched.
The output shows that the MRO for class D is: [D, B, C, A, object]. This means that when a method or attribute is accessed on an instance of class D, Python will first look in class D itself, then in class B, followed by class C, then class A, & finally in the built-in object class.
C3 Linearization Algorithm
The C3 linearization algorithm is the modern algorithm used by Python to resolve the method resolution order. It is a more sophisticated approach than DLR and solves several problems that arose from the earlier approach. The C3 algorithm ensures that classes are resolved in a consistent order, respecting the class hierarchy and avoiding conflicts.
Key Features of C3 Linearization
- It respects the inheritance hierarchy and prevents conflicts that may arise when multiple base classes have the same method.
- It ensures that the MRO is calculated in a consistent and predictable way.
- It resolves the method resolution order in such a way that it avoids issues that occur in more complex inheritance chains.
Let’s take a look at an example where the C3 linearization algorithm is applied:
class A:
def method(self):
print("Method in A")
class B(A):
def method(self):
print("Method in B")
class C(A):
def method(self):
print("Method in C")
class D(B, C):
pass
d = D()
d.method()
You can also try this code with Online Python Compiler
Output:
Method in B
Here, Python uses the C3 algorithm to determine the MRO, which results in class B’s method being called because it is the first class in the order after class D.
Rules of C3 Linearization Algorithm
The C3 linearization algorithm, used by Python to compute the MRO, follows a set of rules to ensure a consistent & predictable ordering. The key rules are:
1. The inheritance graph must be a Directed Acyclic Graph (DAG). This means there should be no circular inheritance dependencies.
2. The MRO of a class must include the class itself as the first element, followed by its parent classes in a specific order.
3. If a class inherits from multiple parent classes, the MRO should preserve the order in which the parent classes are listed in the class declaration.
4. If a class is inherited by multiple subclasses, it should appear in the MRO of each subclass only once.
5. The MRO should maintain monotonicity, meaning that the relative ordering of classes in the MRO should be consistent with the inheritance hierarchy.
Let’s look at an example to look at how to apply these rules:
class A:
pass
class B:
pass
class C(A, B):
pass
class D(C, A):
pass
print(D.mro())
You can also try this code with Online Python Compiler
Output:
[<class '__main__.D'>, <class '__main__.C'>, <class '__main__.A'>, <class '__main__.B'>, <class 'object'>]
In this example, class C inherits from both A & B, while class D inherits from C & A. The MRO of class D is computed as [D, C, A, B, object] based on the C3 linearization rules.
The MRO includes the class itself (D) as the first element, followed by its parent classes (C & A) in the order specified in the class declaration. Class A appears before class B in the MRO of class C, & this relative order is maintained in the MRO of class D. Additionally, class A appears only once in the MRO, even though it is inherited by both C & D.
How C3 Works?
The C3 algorithm uses a process of merging the method resolution lists of the parent classes, ensuring that the most specific classes are chosen first. If there are conflicting choices, the algorithm tries to merge them in a way that respects the hierarchy.
Methods for Method Resolution Order (MRO) of a Class
In Python, the mro() method is used to explicitly determine the method resolution order of a class. This method provides a list of the classes in the order in which they are searched when looking for a method.
You can call the mro() method on a class to see the order in which the classes are checked:
class A(object):
def method(self):
print("Method in A")
class B(A):
def method(self):
print("Method in B")
class C(B):
pass
print(C.mro())
You can also try this code with Online Python Compiler
Output:
[<class '__main__.C'>, <class '__main__.B'>, <class '__main__.A'>, <class 'object'>]
In this example, the mro() method returns a list showing the order of classes that Python follows when resolving methods for class C. The MRO order is C -> B -> A -> object.
Frequently Asked Questions
What is the difference between old-style and new-style classes in Python?
Old-style classes did not inherit from object, while new-style classes do. The major difference is that new-style classes use a more sophisticated and predictable method resolution order, thanks to the C3 linearization algorithm.
What is the mro() method in Python?
The mro() method returns the method resolution order of a class. It is used to see the sequence of classes Python will check when searching for a method, starting from the current class.
How does the C3 linearization algorithm improve method resolution order?
The C3 linearization algorithm resolves inheritance conflicts more effectively by respecting the inheritance hierarchy and ensuring that the method resolution is done in a consistent order, unlike the older DLR algorithm.
Conclusion
In this article, we discussed the concept of Method Resolution Order (MRO) in Python, including its importance in multiple inheritance scenarios. We also looked at the differences between old-style and new-style classes, how the DLR algorithm works, and how Python's modern C3 linearization algorithm resolves inheritance conflicts.
You can also check out our other blogs on Code360.
7+ registered 
