Welcome, guest | Sign In | My Account | Store | Cart

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.

Python, 111 lines
 ``` 1 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 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 == candidate: del seq ### 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:

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().

#### 1 comment Steven D'Aprano (author) 10 years, 5 months ago

This has been written for Python 3, but also works in any version of Python from 2.3 onwards. Created by Steven D'Aprano on Sat, 11 Jun 2011 (MIT)

### Required Modules

• (none specified)