This function allows you to calculate the Method Resolution Order (MRO, or sometimes linearization) of a class or base classes. This is the so-called "C3" algorithm, as used by Python (new-style classes, from version 2.3 and higher). The MRO is the order of base classes that Python uses to search for methods and attributes. For single inheritance, the MRO is obvious and straight-forward and not very exciting, but for multiple inheritance it's not always obvious what the MRO should be.
Download
Copy to clipboard1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105 106 107 108 109 110 111 | def mro(*bases):
"""Calculate the Method Resolution Order of bases using the C3 algorithm.
Suppose you intended creating a class K with the given base classes. This
function returns the MRO which K would have, *excluding* K itself (since
it doesn't yet exist), as if you had actually created the class.
Another way of looking at this, if you pass a single class K, this will
return the linearization of K (the MRO of K, *including* itself).
"""
seqs = [list(C.__mro__) for C in bases] + [list(bases)]
res = []
while True:
non_empty = list(filter(None, seqs))
if not non_empty:
# Nothing left to process, we're done.
return tuple(res)
for seq in non_empty: # Find merge candidates among seq heads.
candidate = seq[0]
not_head = [s for s in non_empty if candidate in s[1:]]
if not_head:
# Reject the candidate.
candidate = None
else:
break
if not candidate:
raise TypeError("inconsistent hierarchy, no C3 MRO is possible")
res.append(candidate)
for seq in non_empty:
# Remove candidate.
if seq[0] == candidate:
del seq[0]
###
if __name__ == '__main__':
# Run self-tests. Prints nothing if they succeed.
O = object
class SeriousOrderDisagreement:
class X(O): pass
class Y(O): pass
class A(X, Y): pass
class B(Y, X): pass
bases = (A, B)
try:
x = mro(*SeriousOrderDisagreement.bases)
except TypeError:
pass
else:
print("failed test, mro should have raised but got %s instead" % (x,))
class Example0: # Trivial single inheritance case.
class A(O): pass
class B(A): pass
class C(B): pass
class D(C): pass
tester = D
expected = (D, C, B, A, O)
class Example1:
class F(O): pass
class E(O): pass
class D(O): pass
class C(D, F): pass
class B(D, E): pass
class A(B, C): pass
tester = A
expected = (A, B, C, D, E, F, O)
class Example2:
class F(O): pass
class E(O): pass
class D(O): pass
class C(D, F): pass
class B(E, D): pass
class A(B, C): pass
tester = A
expected = (A, B, E, C, D, F, O)
class Example3:
class A(O): pass
class B(O): pass
class C(O): pass
class D(O): pass
class E(O): pass
class K1(A, B, C): pass
class K2(D, B, E): pass
class K3(D, A): pass
class Z(K1, K2, K3): pass
assert mro(A) == (A, O)
assert mro(B) == (B, O)
assert mro(C) == (C, O)
assert mro(D) == (D, O)
assert mro(E) == (E, O)
assert mro(K1) == (K1, A, B, C, O)
assert mro(K2) == (K2, D, B, E, O)
assert mro(K3) == (K3, D, A, O)
tester = Z
expected = (Z, K1, K2, K3, D, A, B, C, E, O)
for example in [Example0, Example1, Example2, Example3]:
# First test that the expected result is the same as what Python
# actually generates.
assert example.expected == example.tester.__mro__
# Now check the calculated MRO.
assert mro(example.tester) == example.expected
|
Particularly when dealing with multiple inheritance, you need a way to determine in which order to search a class and its superclasses. Normally Python handles that automatically, but on occasion you might need to generate this Method Resolution Order yourself, without (or before) creating the class. This function will do this.
Historically, Python has used three different algorithms. Two of them are obsolete.
Python 1.x and 2.x classic classes use an algorithm which can give buggy results for certain inheritance relationships. In Python 3, classic classes are gone.
With the introduction of new-style classes in Python 2.2, a new algorithm was used. Unfortunately that also turned out to be buggy, and it was replaced in Python 2.3 with the proven C3 algorithm. This function calculates the C3 MRO of a list of base classes.
For a detailed (and rather technical) discussion of the C3 algorithm and why it is preferred, see Michele Simionato's excellent essay here:
http://www.python.org/download/releases/2.3/mro/
I had need of this when writing a metaclass that needed to interrogate the base classes, and all of their superclasses, before creating the new class. I initially tried a trick, using
type('fake name', bases, {}).__mro__
to have Python create a throw-away class with the same base classes, but that turned out to fragile and hard to use, leading to RecursionError in my metaclass. So I wrote this to calculate the MRO of the base classes without relying on type().
This has been written for Python 3, but also works in any version of Python from 2.3 onwards.