| .. _python_2.3_mro: |
| |
| The Python 2.3 Method Resolution Order |
| ====================================== |
| |
| .. note:: |
| |
| This is a historical document, provided as an appendix to the official |
| documentation. |
| The Method Resolution Order discussed here was *introduced* in Python 2.3, |
| but it is still used in later versions -- including Python 3. |
| |
| By `Michele Simionato <https://www.phyast.pitt.edu/~micheles/>`__. |
| |
| :Abstract: |
| |
| *This document is intended for Python programmers who want to |
| understand the C3 Method Resolution Order used in Python 2.3. |
| Although it is not intended for newbies, it is quite pedagogical with |
| many worked out examples. I am not aware of other publicly available |
| documents with the same scope, therefore it should be useful.* |
| |
| Disclaimer: |
| |
| *I donate this document to the Python Software Foundation, under the |
| Python 2.3 license. As usual in these circumstances, I warn the |
| reader that what follows* should *be correct, but I don't give any |
| warranty. Use it at your own risk and peril!* |
| |
| Acknowledgments: |
| |
| *All the people of the Python mailing list who sent me their support. |
| Paul Foley who pointed out various imprecisions and made me to add the |
| part on local precedence ordering. David Goodger for help with the |
| formatting in reStructuredText. David Mertz for help with the editing. |
| Finally, Guido van Rossum who enthusiastically added this document to |
| the official Python 2.3 home-page.* |
| |
| The beginning |
| ------------- |
| |
| *Felix qui potuit rerum cognoscere causas* -- Virgilius |
| |
| Everything started with a post by Samuele Pedroni to the Python |
| development mailing list [#]_. In his post, Samuele showed that the |
| Python 2.2 method resolution order is not monotonic and he proposed to |
| replace it with the C3 method resolution order. Guido agreed with his |
| arguments and therefore now Python 2.3 uses C3. The C3 method itself |
| has nothing to do with Python, since it was invented by people working |
| on Dylan and it is described in a paper intended for lispers [#]_. The |
| present paper gives a (hopefully) readable discussion of the C3 |
| algorithm for Pythonistas who want to understand the reasons for the |
| change. |
| |
| First of all, let me point out that what I am going to say only applies |
| to the *new style classes* introduced in Python 2.2: *classic classes* |
| maintain their old method resolution order, depth first and then left to |
| right. Therefore, there is no breaking of old code for classic classes; |
| and even if in principle there could be breaking of code for Python 2.2 |
| new style classes, in practice the cases in which the C3 resolution |
| order differs from the Python 2.2 method resolution order are so rare |
| that no real breaking of code is expected. Therefore: |
| |
| *Don't be scared!* |
| |
| Moreover, unless you make strong use of multiple inheritance and you |
| have non-trivial hierarchies, you don't need to understand the C3 |
| algorithm, and you can easily skip this paper. On the other hand, if |
| you really want to know how multiple inheritance works, then this paper |
| is for you. The good news is that things are not as complicated as you |
| might expect. |
| |
| Let me begin with some basic definitions. |
| |
| 1) Given a class C in a complicated multiple inheritance hierarchy, it |
| is a non-trivial task to specify the order in which methods are |
| overridden, i.e. to specify the order of the ancestors of C. |
| |
| 2) The list of the ancestors of a class C, including the class itself, |
| ordered from the nearest ancestor to the furthest, is called the |
| class precedence list or the *linearization* of C. |
| |
| 3) The *Method Resolution Order* (MRO) is the set of rules that |
| construct the linearization. In the Python literature, the idiom |
| "the MRO of C" is also used as a synonymous for the linearization of |
| the class C. |
| |
| 4) For instance, in the case of single inheritance hierarchy, if C is a |
| subclass of C1, and C1 is a subclass of C2, then the linearization of |
| C is simply the list [C, C1 , C2]. However, with multiple |
| inheritance hierarchies, the construction of the linearization is |
| more cumbersome, since it is more difficult to construct a |
| linearization that respects *local precedence ordering* and |
| *monotonicity*. |
| |
| 5) I will discuss the local precedence ordering later, but I can give |
| the definition of monotonicity here. A MRO is monotonic when the |
| following is true: *if C1 precedes C2 in the linearization of C, |
| then C1 precedes C2 in the linearization of any subclass of C*. |
| Otherwise, the innocuous operation of deriving a new class could |
| change the resolution order of methods, potentially introducing very |
| subtle bugs. Examples where this happens will be shown later. |
| |
| 6) Not all classes admit a linearization. There are cases, in |
| complicated hierarchies, where it is not possible to derive a class |
| such that its linearization respects all the desired properties. |
| |
| Here I give an example of this situation. Consider the hierarchy |
| |
| >>> O = object |
| >>> class X(O): pass |
| >>> class Y(O): pass |
| >>> class A(X,Y): pass |
| >>> class B(Y,X): pass |
| |
| which can be represented with the following inheritance graph, where I |
| have denoted with O the ``object`` class, which is the beginning of any |
| hierarchy for new style classes: |
| |
| .. code-block:: text |
| |
| ----------- |
| | | |
| | O | |
| | / \ | |
| - X Y / |
| | / | / |
| | / |/ |
| A B |
| \ / |
| ? |
| |
| In this case, it is not possible to derive a new class C from A and B, |
| since X precedes Y in A, but Y precedes X in B, therefore the method |
| resolution order would be ambiguous in C. |
| |
| Python 2.3 raises an exception in this situation (TypeError: MRO |
| conflict among bases Y, X) forbidding the naive programmer from creating |
| ambiguous hierarchies. Python 2.2 instead does not raise an exception, |
| but chooses an *ad hoc* ordering (CABXYO in this case). |
| |
| The C3 Method Resolution Order |
| ------------------------------ |
| |
| Let me introduce a few simple notations which will be useful for the |
| following discussion. I will use the shortcut notation:: |
| |
| C1 C2 ... CN |
| |
| to indicate the list of classes [C1, C2, ... , CN]. |
| |
| The *head* of the list is its first element:: |
| |
| head = C1 |
| |
| whereas the *tail* is the rest of the list:: |
| |
| tail = C2 ... CN. |
| |
| I shall also use the notation:: |
| |
| C + (C1 C2 ... CN) = C C1 C2 ... CN |
| |
| to denote the sum of the lists [C] + [C1, C2, ... ,CN]. |
| |
| Now I can explain how the MRO works in Python 2.3. |
| |
| Consider a class C in a multiple inheritance hierarchy, with C |
| inheriting from the base classes B1, B2, ... , BN. We want to |
| compute the linearization L[C] of the class C. The rule is the |
| following: |
| |
| *the linearization of C is the sum of C plus the merge of the |
| linearizations of the parents and the list of the parents.* |
| |
| In symbolic notation:: |
| |
| L[C(B1 ... BN)] = C + merge(L[B1] ... L[BN], B1 ... BN) |
| |
| In particular, if C is the ``object`` class, which has no parents, the |
| linearization is trivial:: |
| |
| L[object] = object. |
| |
| However, in general one has to compute the merge according to the following |
| prescription: |
| |
| *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. In this case, it is impossible to construct the |
| merge, Python 2.3 will refuse to create the class C and will raise an |
| exception.* |
| |
| This prescription ensures that the merge operation *preserves* the |
| ordering, if the ordering can be preserved. On the other hand, if the |
| order cannot be preserved (as in the example of serious order |
| disagreement discussed above) then the merge cannot be computed. |
| |
| The computation of the merge is trivial if C has only one parent |
| (single inheritance); in this case:: |
| |
| L[C(B)] = C + merge(L[B],B) = C + L[B] |
| |
| However, in the case of multiple inheritance things are more cumbersome |
| and I don't expect you can understand the rule without a couple of |
| examples ;-) |
| |
| Examples |
| -------- |
| |
| First example. Consider the following hierarchy: |
| |
| >>> O = object |
| >>> 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 |
| |
| In this case the inheritance graph can be drawn as: |
| |
| .. code-block:: text |
| |
| 6 |
| --- |
| Level 3 | O | (more general) |
| / --- \ |
| / | \ | |
| / | \ | |
| / | \ | |
| --- --- --- | |
| Level 2 3 | D | 4| E | | F | 5 | |
| --- --- --- | |
| \ \ _ / | | |
| \ / \ _ | | |
| \ / \ | | |
| --- --- | |
| Level 1 1 | B | | C | 2 | |
| --- --- | |
| \ / | |
| \ / \ / |
| --- |
| Level 0 0 | A | (more specialized) |
| --- |
| |
| |
| The linearizations of O,D,E and F are trivial:: |
| |
| L[O] = O |
| L[D] = D O |
| L[E] = E O |
| L[F] = F O |
| |
| The linearization of B can be computed as:: |
| |
| L[B] = B + merge(DO, EO, DE) |
| |
| We see that D is a good head, therefore we take it and we are reduced to |
| compute ``merge(O,EO,E)``. Now O is not a good head, since it is in the |
| tail of the sequence EO. In this case the rule says that we have to |
| skip to the next sequence. Then we see that E is a good head; we take |
| it and we are reduced to compute ``merge(O,O)`` which gives O. Therefore:: |
| |
| L[B] = B D E O |
| |
| Using the same procedure one finds:: |
| |
| L[C] = C + merge(DO,FO,DF) |
| = C + D + merge(O,FO,F) |
| = C + D + F + merge(O,O) |
| = C D F O |
| |
| Now we can compute:: |
| |
| L[A] = A + merge(BDEO,CDFO,BC) |
| = A + B + merge(DEO,CDFO,C) |
| = A + B + C + merge(DEO,DFO) |
| = A + B + C + D + merge(EO,FO) |
| = A + B + C + D + E + merge(O,FO) |
| = A + B + C + D + E + F + merge(O,O) |
| = A B C D E F O |
| |
| In this example, the linearization is ordered in a pretty nice way |
| according to the inheritance level, in the sense that lower levels (i.e. |
| more specialized classes) have higher precedence (see the inheritance |
| graph). However, this is not the general case. |
| |
| I leave as an exercise for the reader to compute the linearization for |
| my second example: |
| |
| >>> O = object |
| >>> 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 |
| |
| The only difference with the previous example is the change B(D,E) --> |
| B(E,D); however even such a little modification completely changes the |
| ordering of the hierarchy: |
| |
| .. code-block:: text |
| |
| 6 |
| --- |
| Level 3 | O | |
| / --- \ |
| / | \ |
| / | \ |
| / | \ |
| --- --- --- |
| Level 2 2 | E | 4 | D | | F | 5 |
| --- --- --- |
| \ / \ / |
| \ / \ / |
| \ / \ / |
| --- --- |
| Level 1 1 | B | | C | 3 |
| --- --- |
| \ / |
| \ / |
| --- |
| Level 0 0 | A | |
| --- |
| |
| |
| Notice that the class E, which is in the second level of the hierarchy, |
| precedes the class C, which is in the first level of the hierarchy, i.e. |
| E is more specialized than C, even if it is in a higher level. |
| |
| A lazy programmer can obtain the MRO directly from Python 2.2, since in |
| this case it coincides with the Python 2.3 linearization. It is enough |
| to invoke the .mro() method of class A: |
| |
| >>> A.mro() # doctest: +NORMALIZE_WHITESPACE |
| [<class 'A'>, <class 'B'>, <class 'E'>, |
| <class 'C'>, <class 'D'>, <class 'F'>, |
| <class 'object'>] |
| |
| Finally, let me consider the example discussed in the first section, |
| involving a serious order disagreement. In this case, it is |
| straightforward to compute the linearizations of O, X, Y, A and B: |
| |
| .. code-block:: text |
| |
| L[O] = 0 |
| L[X] = X O |
| L[Y] = Y O |
| L[A] = A X Y O |
| L[B] = B Y X O |
| |
| However, it is impossible to compute the linearization for a class C |
| that inherits from A and B:: |
| |
| L[C] = C + merge(AXYO, BYXO, AB) |
| = C + A + merge(XYO, BYXO, B) |
| = C + A + B + merge(XYO, YXO) |
| |
| At this point we cannot merge the lists XYO and YXO, since X is in the |
| tail of YXO whereas Y is in the tail of XYO: therefore there are no |
| good heads and the C3 algorithm stops. Python 2.3 raises an error and |
| refuses to create the class C. |
| |
| Bad Method Resolution Orders |
| ---------------------------- |
| |
| A MRO is *bad* when it breaks such fundamental properties as local |
| precedence ordering and monotonicity. In this section, I will show |
| that both the MRO for classic classes and the MRO for new style classes |
| in Python 2.2 are bad. |
| |
| It is easier to start with the local precedence ordering. Consider the |
| following example: |
| |
| >>> F=type('Food',(),{'remember2buy':'spam'}) |
| >>> E=type('Eggs',(F,),{'remember2buy':'eggs'}) |
| >>> G=type('GoodFood',(F,E),{}) # under Python 2.3 this is an error! # doctest: +SKIP |
| |
| with inheritance diagram |
| |
| .. code-block:: text |
| |
| O |
| | |
| (buy spam) F |
| | \ |
| | E (buy eggs) |
| | / |
| G |
| |
| (buy eggs or spam ?) |
| |
| |
| We see that class G inherits from F and E, with F *before* E: therefore |
| we would expect the attribute *G.remember2buy* to be inherited by |
| *F.rembermer2buy* and not by *E.remember2buy*: nevertheless Python 2.2 |
| gives |
| |
| >>> G.remember2buy # doctest: +SKIP |
| 'eggs' |
| |
| This is a breaking of local precedence ordering since the order in the |
| local precedence list, i.e. the list of the parents of G, is not |
| preserved in the Python 2.2 linearization of G:: |
| |
| L[G,P22]= G E F object # F *follows* E |
| |
| One could argue that the reason why F follows E in the Python 2.2 |
| linearization is that F is less specialized than E, since F is the |
| superclass of E; nevertheless the breaking of local precedence ordering |
| is quite non-intuitive and error prone. This is particularly true since |
| it is a different from old style classes: |
| |
| >>> class F: remember2buy='spam' |
| >>> class E(F): remember2buy='eggs' |
| >>> class G(F,E): pass # doctest: +SKIP |
| >>> G.remember2buy # doctest: +SKIP |
| 'spam' |
| |
| In this case the MRO is GFEF and the local precedence ordering is |
| preserved. |
| |
| As a general rule, hierarchies such as the previous one should be |
| avoided, since it is unclear if F should override E or vice-versa. |
| Python 2.3 solves the ambiguity by raising an exception in the creation |
| of class G, effectively stopping the programmer from generating |
| ambiguous hierarchies. The reason for that is that the C3 algorithm |
| fails when the merge:: |
| |
| merge(FO,EFO,FE) |
| |
| cannot be computed, because F is in the tail of EFO and E is in the tail |
| of FE. |
| |
| The real solution is to design a non-ambiguous hierarchy, i.e. to derive |
| G from E and F (the more specific first) and not from F and E; in this |
| case the MRO is GEF without any doubt. |
| |
| .. code-block:: text |
| |
| O |
| | |
| F (spam) |
| / | |
| (eggs) E | |
| \ | |
| G |
| (eggs, no doubt) |
| |
| |
| Python 2.3 forces the programmer to write good hierarchies (or, at |
| least, less error-prone ones). |
| |
| On a related note, let me point out that the Python 2.3 algorithm is |
| smart enough to recognize obvious mistakes, as the duplication of |
| classes in the list of parents: |
| |
| >>> class A(object): pass |
| >>> class C(A,A): pass # error |
| Traceback (most recent call last): |
| File "<stdin>", line 1, in ? |
| TypeError: duplicate base class A |
| |
| Python 2.2 (both for classic classes and new style classes) in this |
| situation, would not raise any exception. |
| |
| Finally, I would like to point out two lessons we have learned from this |
| example: |
| |
| 1. despite the name, the MRO determines the resolution order of |
| attributes, not only of methods; |
| |
| 2. the default food for Pythonistas is spam ! (but you already knew |
| that ;-) |
| |
| Having discussed the issue of local precedence ordering, let me now |
| consider the issue of monotonicity. My goal is to show that neither the |
| MRO for classic classes nor that for Python 2.2 new style classes is |
| monotonic. |
| |
| To prove that the MRO for classic classes is non-monotonic is rather |
| trivial, it is enough to look at the diamond diagram: |
| |
| .. code-block:: text |
| |
| |
| C |
| / \ |
| / \ |
| A B |
| \ / |
| \ / |
| D |
| |
| One easily discerns the inconsistency:: |
| |
| L[B,P21] = B C # B precedes C : B's methods win |
| L[D,P21] = D A C B C # B follows C : C's methods win! |
| |
| On the other hand, there are no problems with the Python 2.2 and 2.3 |
| MROs, they give both:: |
| |
| L[D] = D A B C |
| |
| Guido points out in his essay [#]_ that the classic MRO is not so bad in |
| practice, since one can typically avoids diamonds for classic classes. |
| But all new style classes inherit from ``object``, therefore diamonds are |
| unavoidable and inconsistencies shows up in every multiple inheritance |
| graph. |
| |
| The MRO of Python 2.2 makes breaking monotonicity difficult, but not |
| impossible. The following example, originally provided by Samuele |
| Pedroni, shows that the MRO of Python 2.2 is non-monotonic: |
| |
| >>> class A(object): pass |
| >>> class B(object): pass |
| >>> class C(object): pass |
| >>> class D(object): pass |
| >>> class E(object): pass |
| >>> class K1(A,B,C): pass |
| >>> class K2(D,B,E): pass |
| >>> class K3(D,A): pass |
| >>> class Z(K1,K2,K3): pass |
| |
| Here are the linearizations according to the C3 MRO (the reader should |
| verify these linearizations as an exercise and draw the inheritance |
| diagram ;-) :: |
| |
| L[A] = A O |
| L[B] = B O |
| L[C] = C O |
| L[D] = D O |
| L[E] = E O |
| L[K1]= K1 A B C O |
| L[K2]= K2 D B E O |
| L[K3]= K3 D A O |
| L[Z] = Z K1 K2 K3 D A B C E O |
| |
| Python 2.2 gives exactly the same linearizations for A, B, C, D, E, K1, |
| K2 and K3, but a different linearization for Z:: |
| |
| L[Z,P22] = Z K1 K3 A K2 D B C E O |
| |
| It is clear that this linearization is *wrong*, since A comes before D |
| whereas in the linearization of K3 A comes *after* D. In other words, in |
| K3 methods derived by D override methods derived by A, but in Z, which |
| still is a subclass of K3, methods derived by A override methods derived |
| by D! This is a violation of monotonicity. Moreover, the Python 2.2 |
| linearization of Z is also inconsistent with local precedence ordering, |
| since the local precedence list of the class Z is [K1, K2, K3] (K2 |
| precedes K3), whereas in the linearization of Z K2 *follows* K3. These |
| problems explain why the 2.2 rule has been dismissed in favor of the C3 |
| rule. |
| |
| The end |
| ------- |
| |
| This section is for the impatient reader, who skipped all the previous |
| sections and jumped immediately to the end. This section is for the |
| lazy programmer too, who didn't want to exercise her/his brain. |
| Finally, it is for the programmer with some hubris, otherwise s/he would |
| not be reading a paper on the C3 method resolution order in multiple |
| inheritance hierarchies ;-) These three virtues taken all together (and |
| *not* separately) deserve a prize: the prize is a short Python 2.2 |
| script that allows you to compute the 2.3 MRO without risk to your |
| brain. Simply change the last line to play with the various examples I |
| have discussed in this paper.:: |
| |
| #<mro.py> |
| |
| """C3 algorithm by Samuele Pedroni (with readability enhanced by me).""" |
| |
| class __metaclass__(type): |
| "All classes are metamagically modified to be nicely printed" |
| __repr__ = lambda cls: cls.__name__ |
| |
| class ex_2: |
| "Serious order disagreement" #From Guido |
| class O: pass |
| class X(O): pass |
| class Y(O): pass |
| class A(X,Y): pass |
| class B(Y,X): pass |
| try: |
| class Z(A,B): pass #creates Z(A,B) in Python 2.2 |
| except TypeError: |
| pass # Z(A,B) cannot be created in Python 2.3 |
| |
| class ex_5: |
| "My first example" |
| class O: pass |
| 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 |
| |
| class ex_6: |
| "My second example" |
| class O: pass |
| 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 |
| |
| class ex_9: |
| "Difference between Python 2.2 MRO and C3" #From Samuele |
| class O: pass |
| 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 |
| |
| def merge(seqs): |
| print '\n\nCPL[%s]=%s' % (seqs[0][0],seqs), |
| res = []; i=0 |
| while 1: |
| nonemptyseqs=[seq for seq in seqs if seq] |
| if not nonemptyseqs: return res |
| i+=1; print '\n',i,'round: candidates...', |
| for seq in nonemptyseqs: # find merge candidates among seq heads |
| cand = seq[0]; print ' ',cand, |
| nothead=[s for s in nonemptyseqs if cand in s[1:]] |
| if nothead: cand=None #reject candidate |
| else: break |
| if not cand: raise "Inconsistent hierarchy" |
| res.append(cand) |
| for seq in nonemptyseqs: # remove cand |
| if seq[0] == cand: del seq[0] |
| |
| def mro(C): |
| "Compute the class precedence list (mro) according to C3" |
| return merge([[C]]+map(mro,C.__bases__)+[list(C.__bases__)]) |
| |
| def print_mro(C): |
| print '\nMRO[%s]=%s' % (C,mro(C)) |
| print '\nP22 MRO[%s]=%s' % (C,C.mro()) |
| |
| print_mro(ex_9.Z) |
| |
| #</mro.py> |
| |
| That's all folks, |
| |
| enjoy ! |
| |
| |
| Resources |
| --------- |
| |
| .. [#] The thread on python-dev started by Samuele Pedroni: |
| https://mail.python.org/pipermail/python-dev/2002-October/029035.html |
| |
| .. [#] The paper *A Monotonic Superclass Linearization for Dylan*: |
| https://doi.org/10.1145/236337.236343 |
| |
| .. [#] Guido van Rossum's essay, *Unifying types and classes in Python 2.2*: |
| https://web.archive.org/web/20140210194412/http://www.python.org/download/releases/2.2.2/descrintro |
