Resolving the classic diamond problem: a perspective on C3 linearization
While creating software from scratch to solve our problems, we often face many design choices. One of them that an object-oriented programmer invariably has to deal with is how to structure the polymorphic behaviour of their classes and subclasses. It is here that we start to appreciate the famous diamond problem and its many nuances.
You probably got a lot of your features from your mother, and also a lot of them from your father. In biological systems, this process of choosing which feature is inherited from whom is inherently random, and that causes the vast diversity in the world that we celebrate (or at least, should celebrate). However, as software engineers, our task is cut out and we cannot have our child classes behaving randomly, with their attributes a chaotic amalgamation of similar attributes defined in their parent classes. So we need to find a way to address this problem and define, deterministically, which attribute is inherited from which class.
Suppose we have the above class design. B is a child of A, C is a child of A, and D is a child of both B and C. This is a classic case of multiple inheritance. In the case that B and C have some common methods which are defined differently, how do we decide which implementation D should inherit? In other words, how do we implement a deterministic order in which the methods in the child classes are resolved?
Python does this through a special object called the Method Resolution Order. The MRO is a list of classes and subclasses which tells us the order in which to look for any method (which is being called) of a child class in all the classes in its inheritance hierarchy. As an example, let us implement the very simple inheritance structure A -> B -> C:
class A:
def func():
pass
class B(A):
def func():
pass
class C(B):
pass
Printing C.mro gives me <built-in method mro of type object at 0x5685f2d2d910> and calling the object with C.mro() gives us the order [C, B, A], which is intuitively expected. Now, in the case of a much more complex inheritance hierarchy, how do we define a deterministic MRO?
In Python, this is done using an algorithm called C3 Linearization. This is a linearization technique which takes into account the depth of each parent class in the inheritance hierarchy. The output of this algorithm is such that superclasses lower down in the inheritance hierarchy are searched first when looking for a method in the child class. The main step of the algorithm looks like a simple divide-and-conquer step:
C3_Linearization(C) = [C] + merge(C3_Linearization(Parents(C)), Parents(C))
The merge of Parents’ linearizations and Parents list is done by selecting the first head (the first entry of a list) of the lists which does not appear in the tail (all elements of a list except the first) of any of the lists. A singleton list is simply a head by itself. The rationale behind this first step is that any superclass that is just a head without appearing in any tail is much closer to the child semantically than any other parent which is also a parent of the child class’s parent (which is what appearing in the tail implies). Note, that a good head may appear as the first element in multiple lists at the same time, but it is forbidden to appear anywhere else.
The selected element is removed from all the lists where it appears as a head and appended to the output list. This is repeated until all remaining lists are exhausted. If at some point no good head can be selected, because the heads of all remaining lists appear in any one tail of the lists, then our algorithm fails because:
- A class X appearing as head means that it is a parent of some layer of child classes at the given step in the algorithm
- A class X appearing in the tail of a list implies that it is above the head of the list in the inheritance hierarchy.
Thus, if the heads of all remaining lists appear in any one tail of the lists, this implies a cyclic class hierarchy which, simply, cannot be resolved. In that case we might still run our algorithm with the additional check of not re-entering an already visited class.
Let us have an example.
In this reasonably complex class hierarchy, we have
class O
class A extends O
class B extends O
class C extends O
class D extends O
class E extends O
class K1 extends C, A, B
class K3 extends A, D
class K2 extends B, D, E
class Z extends K1, K3, K2
the linearization of Z is computed as
L(O) := [O]
// the linearization of O is trivially the singleton list [O],
// because O is the ultimate base class
L(A) := [A] + merge(L(O), [O])
= [A] + merge([O], [O])
= [A, O]
L(B) := [B, O] // linearizations of B, C, D and E are computed similarly as A
L(C) := [C, O]
L(D) := [D, O]
L(E) := [E, O]
L(K1) := [K1] + merge(L(C), L(B), L(A), [C, A, B])
// first, find the linearization of K1's parents, L(C), L(B), and L(A)
// and merge them with the parent list [C, A, B]
= [K1] + merge([C, O], [B, O], [A, O], [C, A, B])
// class C is a good head for the first merge step, because it only
// appears as the head of the first and last lists
= [K1, C] + merge([O], [B, O], [A, O], [A, B])
// class O is not a good candidate for the next merge step, because it
// also appears in the tails of list 2 and 3. Class B is also not good;
// but class A is a good candidate.
= [K1, C, A] + merge([O], [B, O], [O], [B])
// class B is a good candidate; class O still appears in the tail of list 2
= [K1, C, A, B] + merge([O], [O], [O])
// finally, class O is a valid candidate, which also exhausts all
// remaining lists and gives us our final linearization
= [K1, C, A, B, O]
L(K3) := [K3] + merge(L(A), L(D), [A, D])
= [K3] + merge([A, O], [D, O], [A, D]) // select A
= [K3, A] + merge([O], [D, O], [D]) // select D
= [K3, A, D] + merge([O], [O]) // select O
= [K3, A, D, O]
L(K2) := [K2] + merge(L(B), L(D), L(E), [B, D, E])
= [K2] + merge([B, O], [D, O], [E, O], [B, D, E]) // select B
= [K2, B] + merge([O], [D, O], [E, O], [D, E]) // select D
= [K2, B, D] + merge([O], [O], [E, O], [E]) // select E
= [K2, B, D, E] + merge([O], [O], [O]) // select O
= [K2, B, D, E, O]
L(Z) := [Z] + merge(L(K1), L(K3), L(K2), [K1, K3, K2])
= [Z] + merge([K1, C, A, B, O], [K3, A, D, O], [K2, B, D, E, O], [K1, K3, K2]) // select K1
= [Z, K1] + merge([C, A, B, O], [K3, A, D, O], [K2, B, D, E, O], [K3, K2]) // select C
= [Z, K1, C] + merge([A, B, O], [K3, A, D, O], [K2, B, D, E, O], [K3, K2]) // select K3
= [Z, K1, C, K3] + merge([A, B, O], [A, D, O], [K2, B, D, E, O], [K2]) // select A
= [Z, K1, C, K3, A] + merge([B, O], [D, O], [K2, B, D, E, O], [K2]) // select K2
= [Z, K1, C, K3, A, K2] + merge([B, O], [D, O], [B, D, E, O]) // select B
= [Z, K1, C, K3, A, K2, B] + merge([O], [D, O], [D, E, O]) // select D
= [Z, K1, C, K3, A, K2, B, D] + merge([O], [O], [E, O]) // select E
= [Z, K1, C, K3, A, K2, B, D, E] + merge([O], [O], [O]) // select O
= [Z, K1, C, K3, A, K2, B, D, E, O]
Now for another example!
The output of this algorithm is such that superclasses lower down in the inheritance hierarchy are searched first when looking for a method in the child class.
We’ll now understand this line using the following example:
Now D inherits from both C, placed at depth 2, and B, which is placed at depth 1. In this case the linearization of D will be calculated as:
L(O) := [O]
L(A) := [A] + merge(L(O), [O])
= [A] + merge([O], [O])
= [A, O]
L(B) := [B, O]
L(C) := [C] + merge(L(B), L(A), [B, A])
= [C] + merge([B, O], [A, O], [B, A])
= [C, B] + merge([O], [A, O], [A]) // choose B
= [C, B, A] + merge([O], [O]) // choose A
= [C, B, A, O]
L(D) := [D] + merge(L(B), L(C), [C, B])
= [D] + merge([B, O], [C, B, A, O], [C, B])
= [D, C] + merge([B, O], [B, A, O], [B]) // choose C
= [D, C, B] + merge([O], [A, O]) // choose B
= [D, C, B, A] + merge([O], [O]) // choose A
= [D, C, B, A, O]
As we see, the superclass C comes first in the MRO generated by our algorithm since C is below B in the inheritance hierarchy. A crucial point to note is that the exact form of MRO depends on the order of the classes in the definition of our inheritance relationship. So writing
class B(A, O):
pass
# and
class B(O, A):
pass
should be expected to return different behaviour for the MRO, and can be tested readily in Python.
If you have some previous experience in algorithms, you would be curious about the time complexity of the algorithm. The algorithm is linear in the number of classes in the final MRO, plus the total number of relationships that we define from one class to another, since during the merge step we find the linearizations of the parents which recursively visits all the superclasses till the base class exactly once and traverses each relationship once. A new perspective can be found if we simply realize that the inheritance hierarchy, when visualised, is simply a directed graph, with nodes as classes and edges as relationships!
The C3 linearization algorithm can simply be represented as a topological sorting of the directed graph of the inheritance hierarchy. Also, the fact that a cyclic inheritance relationship cannot be formed into an MRO without additional conditions and compromises, is a direct analogue of the fact that only Directed ACYCLIC graphs can be linearized using topological sorting. This also gives credence to the claim of linear O(n + m) complexity in n, the number of nodes, plus m, the number of edges.
Concluding thoughts
But are complex inheritance structures actually useful? Consider the following structure:
Here, we model a GradTeachingFellow as both a Student and a Teacher. But picture this: how would you want to inherit getDepartment() for GradTeachingFellow? They might be student in one department and teach in another one. This calls for a decision to be taken for each such attribute, which is now equivalent to simply implementing all the methods of the GradTeachingFellow class using overrides, thus reducing the inheritance structure purely down to semantic significance.
We conclude with the air that having a complicated inheritance structure as the ones described above must be readily avoided for the sake of maintainability and cleanliness of code. A good software design bypasses the need for complex relationships such as circular inheritance and heavy calculations like these are best left for academic purposes!
References:
- https://en.wikipedia.org/wiki/C3_linearization
- https://stackoverflow.com/questions/561729/can-the-diamond-problem-be-really-solved
(Migrated from Medium on 17 August 2026)