| 1 |
.. _python_2.3_mro: |
| 2 |
|
| 3 |
The Python 2.3 Method Resolution Order |
| 4 |
====================================== |
| 5 |
|
| 6 |
.. note:: |
| 7 |
|
| 8 |
This is a historical document, provided as an appendix to the official |
| 9 |
documentation. |
| 10 |
The Method Resolution Order discussed here was *introduced* in Python 2.3, |
| 11 |
but it is still used in later versions -- including Python 3. |
| 12 |
|
| 13 |
By `Michele Simionato <https://www.phyast.pitt.edu/~micheles/>`__. |
| 14 |
|
| 15 |
:Abstract: |
| 16 |
|
| 17 |
*This document is intended for Python programmers who want to |
| 18 |
understand the C3 Method Resolution Order used in Python 2.3. |
| 19 |
Although it is not intended for newbies, it is quite pedagogical with |
| 20 |
many worked out examples. I am not aware of other publicly available |
| 21 |
documents with the same scope, therefore it should be useful.* |
| 22 |
|
| 23 |
Disclaimer: |
| 24 |
|
| 25 |
*I donate this document to the Python Software Foundation, under the |
| 26 |
Python 2.3 license. As usual in these circumstances, I warn the |
| 27 |
reader that what follows* should *be correct, but I don't give any |
| 28 |
warranty. Use it at your own risk and peril!* |
| 29 |
|
| 30 |
Acknowledgments: |
| 31 |
|
| 32 |
*All the people of the Python mailing list who sent me their support. |
| 33 |
Paul Foley who pointed out various imprecisions and made me to add the |
| 34 |
part on local precedence ordering. David Goodger for help with the |
| 35 |
formatting in reStructuredText. David Mertz for help with the editing. |
| 36 |
Finally, Guido van Rossum who enthusiastically added this document to |
| 37 |
the official Python 2.3 home-page.* |
| 38 |
|
| 39 |
The beginning |
| 40 |
------------- |
| 41 |
|
| 42 |
*Felix qui potuit rerum cognoscere causas* -- Virgilius |
| 43 |
|
| 44 |
Everything started with a post by Samuele Pedroni to the Python |
| 45 |
development mailing list [#]_. In his post, Samuele showed that the |
| 46 |
Python 2.2 method resolution order is not monotonic and he proposed to |
| 47 |
replace it with the C3 method resolution order. Guido agreed with his |
| 48 |
arguments and therefore now Python 2.3 uses C3. The C3 method itself |
| 49 |
has nothing to do with Python, since it was invented by people working |
| 50 |
on Dylan and it is described in a paper intended for lispers [#]_. The |
| 51 |
present paper gives a (hopefully) readable discussion of the C3 |
| 52 |
algorithm for Pythonistas who want to understand the reasons for the |
| 53 |
change. |
| 54 |
|
| 55 |
First of all, let me point out that what I am going to say only applies |
| 56 |
to the *new style classes* introduced in Python 2.2: *classic classes* |
| 57 |
maintain their old method resolution order, depth first and then left to |
| 58 |
right. Therefore, there is no breaking of old code for classic classes; |
| 59 |
and even if in principle there could be breaking of code for Python 2.2 |
| 60 |
new style classes, in practice the cases in which the C3 resolution |
| 61 |
order differs from the Python 2.2 method resolution order are so rare |
| 62 |
that no real breaking of code is expected. Therefore: |
| 63 |
|
| 64 |
*Don't be scared!* |
| 65 |
|
| 66 |
Moreover, unless you make strong use of multiple inheritance and you |
| 67 |
have non-trivial hierarchies, you don't need to understand the C3 |
| 68 |
algorithm, and you can easily skip this paper. On the other hand, if |
| 69 |
you really want to know how multiple inheritance works, then this paper |
| 70 |
is for you. The good news is that things are not as complicated as you |
| 71 |
might expect. |
| 72 |
|
| 73 |
Let me begin with some basic definitions. |
| 74 |
|
| 75 |
1) Given a class C in a complicated multiple inheritance hierarchy, it |
| 76 |
is a non-trivial task to specify the order in which methods are |
| 77 |
overridden, i.e. to specify the order of the ancestors of C. |
| 78 |
|
| 79 |
2) The list of the ancestors of a class C, including the class itself, |
| 80 |
ordered from the nearest ancestor to the furthest, is called the |
| 81 |
class precedence list or the *linearization* of C. |
| 82 |
|
| 83 |
3) The *Method Resolution Order* (MRO) is the set of rules that |
| 84 |
construct the linearization. In the Python literature, the idiom |
| 85 |
"the MRO of C" is also used as a synonymous for the linearization of |
| 86 |
the class C. |
| 87 |
|
| 88 |
4) For instance, in the case of single inheritance hierarchy, if C is a |
| 89 |
subclass of C1, and C1 is a subclass of C2, then the linearization of |
| 90 |
C is simply the list [C, C1 , C2]. However, with multiple |
| 91 |
inheritance hierarchies, the construction of the linearization is |
| 92 |
more cumbersome, since it is more difficult to construct a |
| 93 |
linearization that respects *local precedence ordering* and |
| 94 |
*monotonicity*. |
| 95 |
|
| 96 |
5) I will discuss the local precedence ordering later, but I can give |
| 97 |
the definition of monotonicity here. A MRO is monotonic when the |
| 98 |
following is true: *if C1 precedes C2 in the linearization of C, |
| 99 |
then C1 precedes C2 in the linearization of any subclass of C*. |
| 100 |
Otherwise, the innocuous operation of deriving a new class could |
| 101 |
change the resolution order of methods, potentially introducing very |
| 102 |
subtle bugs. Examples where this happens will be shown later. |
| 103 |
|
| 104 |
6) Not all classes admit a linearization. There are cases, in |
| 105 |
complicated hierarchies, where it is not possible to derive a class |
| 106 |
such that its linearization respects all the desired properties. |
| 107 |
|
| 108 |
Here I give an example of this situation. Consider the hierarchy |
| 109 |
|
| 110 |
>>> O = object |
| 111 |
>>> class X(O): pass |
| 112 |
>>> class Y(O): pass |
| 113 |
>>> class A(X,Y): pass |
| 114 |
>>> class B(Y,X): pass |
| 115 |
|
| 116 |
which can be represented with the following inheritance graph, where I |
| 117 |
have denoted with O the ``object`` class, which is the beginning of any |
| 118 |
hierarchy for new style classes: |
| 119 |
|
| 120 |
.. code-block:: text |
| 121 |
|
| 122 |
----------- |
| 123 |
| | |
| 124 |
| O | |
| 125 |
| / \ | |
| 126 |
- X Y / |
| 127 |
| / | / |
| 128 |
| / |/ |
| 129 |
A B |
| 130 |
\ / |
| 131 |
? |
| 132 |
|
| 133 |
In this case, it is not possible to derive a new class C from A and B, |
| 134 |
since X precedes Y in A, but Y precedes X in B, therefore the method |
| 135 |
resolution order would be ambiguous in C. |
| 136 |
|
| 137 |
Python 2.3 raises an exception in this situation (TypeError: MRO |
| 138 |
conflict among bases Y, X) forbidding the naive programmer from creating |
| 139 |
ambiguous hierarchies. Python 2.2 instead does not raise an exception, |
| 140 |
but chooses an *ad hoc* ordering (CABXYO in this case). |
| 141 |
|
| 142 |
The C3 Method Resolution Order |
| 143 |
------------------------------ |
| 144 |
|
| 145 |
Let me introduce a few simple notations which will be useful for the |
| 146 |
following discussion. I will use the shortcut notation:: |
| 147 |
|
| 148 |
C1 C2 ... CN |
| 149 |
|
| 150 |
to indicate the list of classes [C1, C2, ... , CN]. |
| 151 |
|
| 152 |
The *head* of the list is its first element:: |
| 153 |
|
| 154 |
head = C1 |
| 155 |
|
| 156 |
whereas the *tail* is the rest of the list:: |
| 157 |
|
| 158 |
tail = C2 ... CN. |
| 159 |
|
| 160 |
I shall also use the notation:: |
| 161 |
|
| 162 |
C + (C1 C2 ... CN) = C C1 C2 ... CN |
| 163 |
|
| 164 |
to denote the sum of the lists [C] + [C1, C2, ... ,CN]. |
| 165 |
|
| 166 |
Now I can explain how the MRO works in Python 2.3. |
| 167 |
|
| 168 |
Consider a class C in a multiple inheritance hierarchy, with C |
| 169 |
inheriting from the base classes B1, B2, ... , BN. We want to |
| 170 |
compute the linearization L[C] of the class C. The rule is the |
| 171 |
following: |
| 172 |
|
| 173 |
*the linearization of C is the sum of C plus the merge of the |
| 174 |
linearizations of the parents and the list of the parents.* |
| 175 |
|
| 176 |
In symbolic notation:: |
| 177 |
|
| 178 |
L[C(B1 ... BN)] = C + merge(L[B1] ... L[BN], B1 ... BN) |
| 179 |
|
| 180 |
In particular, if C is the ``object`` class, which has no parents, the |
| 181 |
linearization is trivial:: |
| 182 |
|
| 183 |
L[object] = object. |
| 184 |
|
| 185 |
However, in general one has to compute the merge according to the following |
| 186 |
prescription: |
| 187 |
|
| 188 |
*take the head of the first list, i.e L[B1][0]; if this head is not in |
| 189 |
the tail of any of the other lists, then add it to the linearization |
| 190 |
of C and remove it from the lists in the merge, otherwise look at the |
| 191 |
head of the next list and take it, if it is a good head. Then repeat |
| 192 |
the operation until all the class are removed or it is impossible to |
| 193 |
find good heads. In this case, it is impossible to construct the |
| 194 |
merge, Python 2.3 will refuse to create the class C and will raise an |
| 195 |
exception.* |
| 196 |
|
| 197 |
This prescription ensures that the merge operation *preserves* the |
| 198 |
ordering, if the ordering can be preserved. On the other hand, if the |
| 199 |
order cannot be preserved (as in the example of serious order |
| 200 |
disagreement discussed above) then the merge cannot be computed. |
| 201 |
|
| 202 |
The computation of the merge is trivial if C has only one parent |
| 203 |
(single inheritance); in this case:: |
| 204 |
|
| 205 |
L[C(B)] = C + merge(L[B],B) = C + L[B] |
| 206 |
|
| 207 |
However, in the case of multiple inheritance things are more cumbersome |
| 208 |
and I don't expect you can understand the rule without a couple of |
| 209 |
examples ;-) |
| 210 |
|
| 211 |
Examples |
| 212 |
-------- |
| 213 |
|
| 214 |
First example. Consider the following hierarchy: |
| 215 |
|
| 216 |
>>> O = object |
| 217 |
>>> class F(O): pass |
| 218 |
>>> class E(O): pass |
| 219 |
>>> class D(O): pass |
| 220 |
>>> class C(D,F): pass |
| 221 |
>>> class B(D,E): pass |
| 222 |
>>> class A(B,C): pass |
| 223 |
|
| 224 |
In this case the inheritance graph can be drawn as: |
| 225 |
|
| 226 |
.. code-block:: text |
| 227 |
|
| 228 |
6 |
| 229 |
--- |
| 230 |
Level 3 | O | (more general) |
| 231 |
/ --- \ |
| 232 |
/ | \ | |
| 233 |
/ | \ | |
| 234 |
/ | \ | |
| 235 |
--- --- --- | |
| 236 |
Level 2 3 | D | 4| E | | F | 5 | |
| 237 |
--- --- --- | |
| 238 |
\ \ _ / | | |
| 239 |
\ / \ _ | | |
| 240 |
\ / \ | | |
| 241 |
--- --- | |
| 242 |
Level 1 1 | B | | C | 2 | |
| 243 |
--- --- | |
| 244 |
\ / | |
| 245 |
\ / \ / |
| 246 |
--- |
| 247 |
Level 0 0 | A | (more specialized) |
| 248 |
--- |
| 249 |
|
| 250 |
|
| 251 |
The linearizations of O,D,E and F are trivial:: |
| 252 |
|
| 253 |
L[O] = O |
| 254 |
L[D] = D O |
| 255 |
L[E] = E O |
| 256 |
L[F] = F O |
| 257 |
|
| 258 |
The linearization of B can be computed as:: |
| 259 |
|
| 260 |
L[B] = B + merge(DO, EO, DE) |
| 261 |
|
| 262 |
We see that D is a good head, therefore we take it and we are reduced to |
| 263 |
compute ``merge(O,EO,E)``. Now O is not a good head, since it is in the |
| 264 |
tail of the sequence EO. In this case the rule says that we have to |
| 265 |
skip to the next sequence. Then we see that E is a good head; we take |
| 266 |
it and we are reduced to compute ``merge(O,O)`` which gives O. Therefore:: |
| 267 |
|
| 268 |
L[B] = B D E O |
| 269 |
|
| 270 |
Using the same procedure one finds:: |
| 271 |
|
| 272 |
L[C] = C + merge(DO,FO,DF) |
| 273 |
= C + D + merge(O,FO,F) |
| 274 |
= C + D + F + merge(O,O) |
| 275 |
= C D F O |
| 276 |
|
| 277 |
Now we can compute:: |
| 278 |
|
| 279 |
L[A] = A + merge(BDEO,CDFO,BC) |
| 280 |
= A + B + merge(DEO,CDFO,C) |
| 281 |
= A + B + C + merge(DEO,DFO) |
| 282 |
= A + B + C + D + merge(EO,FO) |
| 283 |
= A + B + C + D + E + merge(O,FO) |
| 284 |
= A + B + C + D + E + F + merge(O,O) |
| 285 |
= A B C D E F O |
| 286 |
|
| 287 |
In this example, the linearization is ordered in a pretty nice way |
| 288 |
according to the inheritance level, in the sense that lower levels (i.e. |
| 289 |
more specialized classes) have higher precedence (see the inheritance |
| 290 |
graph). However, this is not the general case. |
| 291 |
|
| 292 |
I leave as an exercise for the reader to compute the linearization for |
| 293 |
my second example: |
| 294 |
|
| 295 |
>>> O = object |
| 296 |
>>> class F(O): pass |
| 297 |
>>> class E(O): pass |
| 298 |
>>> class D(O): pass |
| 299 |
>>> class C(D,F): pass |
| 300 |
>>> class B(E,D): pass |
| 301 |
>>> class A(B,C): pass |
| 302 |
|
| 303 |
The only difference with the previous example is the change B(D,E) --> |
| 304 |
B(E,D); however even such a little modification completely changes the |
| 305 |
ordering of the hierarchy: |
| 306 |
|
| 307 |
.. code-block:: text |
| 308 |
|
| 309 |
6 |
| 310 |
--- |
| 311 |
Level 3 | O | |
| 312 |
/ --- \ |
| 313 |
/ | \ |
| 314 |
/ | \ |
| 315 |
/ | \ |
| 316 |
--- --- --- |
| 317 |
Level 2 2 | E | 4 | D | | F | 5 |
| 318 |
--- --- --- |
| 319 |
\ / \ / |
| 320 |
\ / \ / |
| 321 |
\ / \ / |
| 322 |
--- --- |
| 323 |
Level 1 1 | B | | C | 3 |
| 324 |
--- --- |
| 325 |
\ / |
| 326 |
\ / |
| 327 |
--- |
| 328 |
Level 0 0 | A | |
| 329 |
--- |
| 330 |
|
| 331 |
|
| 332 |
Notice that the class E, which is in the second level of the hierarchy, |
| 333 |
precedes the class C, which is in the first level of the hierarchy, i.e. |
| 334 |
E is more specialized than C, even if it is in a higher level. |
| 335 |
|
| 336 |
A lazy programmer can obtain the MRO directly from Python 2.2, since in |
| 337 |
this case it coincides with the Python 2.3 linearization. It is enough |
| 338 |
to invoke the :meth:`~type.mro` method of class A: |
| 339 |
|
| 340 |
>>> A.mro() # doctest: +NORMALIZE_WHITESPACE |
| 341 |
[<class 'A'>, <class 'B'>, <class 'E'>, |
| 342 |
<class 'C'>, <class 'D'>, <class 'F'>, |
| 343 |
<class 'object'>] |
| 344 |
|
| 345 |
Finally, let me consider the example discussed in the first section, |
| 346 |
involving a serious order disagreement. In this case, it is |
| 347 |
straightforward to compute the linearizations of O, X, Y, A and B: |
| 348 |
|
| 349 |
.. code-block:: text |
| 350 |
|
| 351 |
L[O] = 0 |
| 352 |
L[X] = X O |
| 353 |
L[Y] = Y O |
| 354 |
L[A] = A X Y O |
| 355 |
L[B] = B Y X O |
| 356 |
|
| 357 |
However, it is impossible to compute the linearization for a class C |
| 358 |
that inherits from A and B:: |
| 359 |
|
| 360 |
L[C] = C + merge(AXYO, BYXO, AB) |
| 361 |
= C + A + merge(XYO, BYXO, B) |
| 362 |
= C + A + B + merge(XYO, YXO) |
| 363 |
|
| 364 |
At this point we cannot merge the lists XYO and YXO, since X is in the |
| 365 |
tail of YXO whereas Y is in the tail of XYO: therefore there are no |
| 366 |
good heads and the C3 algorithm stops. Python 2.3 raises an error and |
| 367 |
refuses to create the class C. |
| 368 |
|
| 369 |
Bad Method Resolution Orders |
| 370 |
---------------------------- |
| 371 |
|
| 372 |
A MRO is *bad* when it breaks such fundamental properties as local |
| 373 |
precedence ordering and monotonicity. In this section, I will show |
| 374 |
that both the MRO for classic classes and the MRO for new style classes |
| 375 |
in Python 2.2 are bad. |
| 376 |
|
| 377 |
It is easier to start with the local precedence ordering. Consider the |
| 378 |
following example: |
| 379 |
|
| 380 |
>>> F=type('Food',(),{'remember2buy':'spam'}) |
| 381 |
>>> E=type('Eggs',(F,),{'remember2buy':'eggs'}) |
| 382 |
>>> G=type('GoodFood',(F,E),{}) # under Python 2.3 this is an error! # doctest: +SKIP |
| 383 |
|
| 384 |
with inheritance diagram |
| 385 |
|
| 386 |
.. code-block:: text |
| 387 |
|
| 388 |
O |
| 389 |
| |
| 390 |
(buy spam) F |
| 391 |
| \ |
| 392 |
| E (buy eggs) |
| 393 |
| / |
| 394 |
G |
| 395 |
|
| 396 |
(buy eggs or spam ?) |
| 397 |
|
| 398 |
|
| 399 |
We see that class G inherits from F and E, with F *before* E: therefore |
| 400 |
we would expect the attribute *G.remember2buy* to be inherited by |
| 401 |
*F.remember2buy* and not by *E.remember2buy*: nevertheless Python 2.2 |
| 402 |
gives |
| 403 |
|
| 404 |
>>> G.remember2buy # doctest: +SKIP |
| 405 |
'eggs' |
| 406 |
|
| 407 |
This is a breaking of local precedence ordering since the order in the |
| 408 |
local precedence list, i.e. the list of the parents of G, is not |
| 409 |
preserved in the Python 2.2 linearization of G:: |
| 410 |
|
| 411 |
L[G,P22]= G E F object # F *follows* E |
| 412 |
|
| 413 |
One could argue that the reason why F follows E in the Python 2.2 |
| 414 |
linearization is that F is less specialized than E, since F is the |
| 415 |
superclass of E; nevertheless the breaking of local precedence ordering |
| 416 |
is quite non-intuitive and error prone. This is particularly true since |
| 417 |
it is a different from old style classes: |
| 418 |
|
| 419 |
>>> class F: remember2buy='spam' |
| 420 |
>>> class E(F): remember2buy='eggs' |
| 421 |
>>> class G(F,E): pass # doctest: +SKIP |
| 422 |
>>> G.remember2buy # doctest: +SKIP |
| 423 |
'spam' |
| 424 |
|
| 425 |
In this case the MRO is GFEF and the local precedence ordering is |
| 426 |
preserved. |
| 427 |
|
| 428 |
As a general rule, hierarchies such as the previous one should be |
| 429 |
avoided, since it is unclear if F should override E or vice-versa. |
| 430 |
Python 2.3 solves the ambiguity by raising an exception in the creation |
| 431 |
of class G, effectively stopping the programmer from generating |
| 432 |
ambiguous hierarchies. The reason for that is that the C3 algorithm |
| 433 |
fails when the merge:: |
| 434 |
|
| 435 |
merge(FO,EFO,FE) |
| 436 |
|
| 437 |
cannot be computed, because F is in the tail of EFO and E is in the tail |
| 438 |
of FE. |
| 439 |
|
| 440 |
The real solution is to design a non-ambiguous hierarchy, i.e. to derive |
| 441 |
G from E and F (the more specific first) and not from F and E; in this |
| 442 |
case the MRO is GEF without any doubt. |
| 443 |
|
| 444 |
.. code-block:: text |
| 445 |
|
| 446 |
O |
| 447 |
| |
| 448 |
F (spam) |
| 449 |
/ | |
| 450 |
(eggs) E | |
| 451 |
\ | |
| 452 |
G |
| 453 |
(eggs, no doubt) |
| 454 |
|
| 455 |
|
| 456 |
Python 2.3 forces the programmer to write good hierarchies (or, at |
| 457 |
least, less error-prone ones). |
| 458 |
|
| 459 |
On a related note, let me point out that the Python 2.3 algorithm is |
| 460 |
smart enough to recognize obvious mistakes, as the duplication of |
| 461 |
classes in the list of parents: |
| 462 |
|
| 463 |
>>> class A(object): pass |
| 464 |
>>> class C(A,A): pass # error |
| 465 |
Traceback (most recent call last): |
| 466 |
File "<stdin>", line 1, in ? |
| 467 |
TypeError: duplicate base class A |
| 468 |
|
| 469 |
Python 2.2 (both for classic classes and new style classes) in this |
| 470 |
situation, would not raise any exception. |
| 471 |
|
| 472 |
Finally, I would like to point out two lessons we have learned from this |
| 473 |
example: |
| 474 |
|
| 475 |
1. despite the name, the MRO determines the resolution order of |
| 476 |
attributes, not only of methods; |
| 477 |
|
| 478 |
2. the default food for Pythonistas is spam ! (but you already knew |
| 479 |
that ;-) |
| 480 |
|
| 481 |
Having discussed the issue of local precedence ordering, let me now |
| 482 |
consider the issue of monotonicity. My goal is to show that neither the |
| 483 |
MRO for classic classes nor that for Python 2.2 new style classes is |
| 484 |
monotonic. |
| 485 |
|
| 486 |
To prove that the MRO for classic classes is non-monotonic is rather |
| 487 |
trivial, it is enough to look at the diamond diagram: |
| 488 |
|
| 489 |
.. code-block:: text |
| 490 |
|
| 491 |
|
| 492 |
C |
| 493 |
/ \ |
| 494 |
/ \ |
| 495 |
A B |
| 496 |
\ / |
| 497 |
\ / |
| 498 |
D |
| 499 |
|
| 500 |
One easily discerns the inconsistency:: |
| 501 |
|
| 502 |
L[B,P21] = B C # B precedes C : B's methods win |
| 503 |
L[D,P21] = D A C B C # B follows C : C's methods win! |
| 504 |
|
| 505 |
On the other hand, there are no problems with the Python 2.2 and 2.3 |
| 506 |
MROs, they give both:: |
| 507 |
|
| 508 |
L[D] = D A B C |
| 509 |
|
| 510 |
Guido points out in his essay [#]_ that the classic MRO is not so bad in |
| 511 |
practice, since one can typically avoids diamonds for classic classes. |
| 512 |
But all new style classes inherit from ``object``, therefore diamonds are |
| 513 |
unavoidable and inconsistencies shows up in every multiple inheritance |
| 514 |
graph. |
| 515 |
|
| 516 |
The MRO of Python 2.2 makes breaking monotonicity difficult, but not |
| 517 |
impossible. The following example, originally provided by Samuele |
| 518 |
Pedroni, shows that the MRO of Python 2.2 is non-monotonic: |
| 519 |
|
| 520 |
>>> class A(object): pass |
| 521 |
>>> class B(object): pass |
| 522 |
>>> class C(object): pass |
| 523 |
>>> class D(object): pass |
| 524 |
>>> class E(object): pass |
| 525 |
>>> class K1(A,B,C): pass |
| 526 |
>>> class K2(D,B,E): pass |
| 527 |
>>> class K3(D,A): pass |
| 528 |
>>> class Z(K1,K2,K3): pass |
| 529 |
|
| 530 |
Here are the linearizations according to the C3 MRO (the reader should |
| 531 |
verify these linearizations as an exercise and draw the inheritance |
| 532 |
diagram ;-) :: |
| 533 |
|
| 534 |
L[A] = A O |
| 535 |
L[B] = B O |
| 536 |
L[C] = C O |
| 537 |
L[D] = D O |
| 538 |
L[E] = E O |
| 539 |
L[K1]= K1 A B C O |
| 540 |
L[K2]= K2 D B E O |
| 541 |
L[K3]= K3 D A O |
| 542 |
L[Z] = Z K1 K2 K3 D A B C E O |
| 543 |
|
| 544 |
Python 2.2 gives exactly the same linearizations for A, B, C, D, E, K1, |
| 545 |
K2 and K3, but a different linearization for Z:: |
| 546 |
|
| 547 |
L[Z,P22] = Z K1 K3 A K2 D B C E O |
| 548 |
|
| 549 |
It is clear that this linearization is *wrong*, since A comes before D |
| 550 |
whereas in the linearization of K3 A comes *after* D. In other words, in |
| 551 |
K3 methods derived by D override methods derived by A, but in Z, which |
| 552 |
still is a subclass of K3, methods derived by A override methods derived |
| 553 |
by D! This is a violation of monotonicity. Moreover, the Python 2.2 |
| 554 |
linearization of Z is also inconsistent with local precedence ordering, |
| 555 |
since the local precedence list of the class Z is [K1, K2, K3] (K2 |
| 556 |
precedes K3), whereas in the linearization of Z K2 *follows* K3. These |
| 557 |
problems explain why the 2.2 rule has been dismissed in favor of the C3 |
| 558 |
rule. |
| 559 |
|
| 560 |
The end |
| 561 |
------- |
| 562 |
|
| 563 |
This section is for the impatient reader, who skipped all the previous |
| 564 |
sections and jumped immediately to the end. This section is for the |
| 565 |
lazy programmer too, who didn't want to exercise her/his brain. |
| 566 |
Finally, it is for the programmer with some hubris, otherwise s/he would |
| 567 |
not be reading a paper on the C3 method resolution order in multiple |
| 568 |
inheritance hierarchies ;-) These three virtues taken all together (and |
| 569 |
*not* separately) deserve a prize: the prize is a short Python 2.2 |
| 570 |
script that allows you to compute the 2.3 MRO without risk to your |
| 571 |
brain. Simply change the last line to play with the various examples I |
| 572 |
have discussed in this paper.:: |
| 573 |
|
| 574 |
#<mro.py> |
| 575 |
|
| 576 |
"""C3 algorithm by Samuele Pedroni (with readability enhanced by me).""" |
| 577 |
|
| 578 |
class __metaclass__(type): |
| 579 |
"All classes are metamagically modified to be nicely printed" |
| 580 |
__repr__ = lambda cls: cls.__name__ |
| 581 |
|
| 582 |
class ex_2: |
| 583 |
"Serious order disagreement" #From Guido |
| 584 |
class O: pass |
| 585 |
class X(O): pass |
| 586 |
class Y(O): pass |
| 587 |
class A(X,Y): pass |
| 588 |
class B(Y,X): pass |
| 589 |
try: |
| 590 |
class Z(A,B): pass #creates Z(A,B) in Python 2.2 |
| 591 |
except TypeError: |
| 592 |
pass # Z(A,B) cannot be created in Python 2.3 |
| 593 |
|
| 594 |
class ex_5: |
| 595 |
"My first example" |
| 596 |
class O: pass |
| 597 |
class F(O): pass |
| 598 |
class E(O): pass |
| 599 |
class D(O): pass |
| 600 |
class C(D,F): pass |
| 601 |
class B(D,E): pass |
| 602 |
class A(B,C): pass |
| 603 |
|
| 604 |
class ex_6: |
| 605 |
"My second example" |
| 606 |
class O: pass |
| 607 |
class F(O): pass |
| 608 |
class E(O): pass |
| 609 |
class D(O): pass |
| 610 |
class C(D,F): pass |
| 611 |
class B(E,D): pass |
| 612 |
class A(B,C): pass |
| 613 |
|
| 614 |
class ex_9: |
| 615 |
"Difference between Python 2.2 MRO and C3" #From Samuele |
| 616 |
class O: pass |
| 617 |
class A(O): pass |
| 618 |
class B(O): pass |
| 619 |
class C(O): pass |
| 620 |
class D(O): pass |
| 621 |
class E(O): pass |
| 622 |
class K1(A,B,C): pass |
| 623 |
class K2(D,B,E): pass |
| 624 |
class K3(D,A): pass |
| 625 |
class Z(K1,K2,K3): pass |
| 626 |
|
| 627 |
def merge(seqs): |
| 628 |
print '\n\nCPL[%s]=%s' % (seqs[0][0],seqs), |
| 629 |
res = []; i=0 |
| 630 |
while 1: |
| 631 |
nonemptyseqs=[seq for seq in seqs if seq] |
| 632 |
if not nonemptyseqs: return res |
| 633 |
i+=1; print '\n',i,'round: candidates...', |
| 634 |
for seq in nonemptyseqs: # find merge candidates among seq heads |
| 635 |
cand = seq[0]; print ' ',cand, |
| 636 |
nothead=[s for s in nonemptyseqs if cand in s[1:]] |
| 637 |
if nothead: cand=None #reject candidate |
| 638 |
else: break |
| 639 |
if not cand: raise "Inconsistent hierarchy" |
| 640 |
res.append(cand) |
| 641 |
for seq in nonemptyseqs: # remove cand |
| 642 |
if seq[0] == cand: del seq[0] |
| 643 |
|
| 644 |
def mro(C): |
| 645 |
"Compute the class precedence list (mro) according to C3" |
| 646 |
return merge([[C]]+map(mro,C.__bases__)+[list(C.__bases__)]) |
| 647 |
|
| 648 |
def print_mro(C): |
| 649 |
print '\nMRO[%s]=%s' % (C,mro(C)) |
| 650 |
print '\nP22 MRO[%s]=%s' % (C,C.mro()) |
| 651 |
|
| 652 |
print_mro(ex_9.Z) |
| 653 |
|
| 654 |
#</mro.py> |
| 655 |
|
| 656 |
That's all folks, |
| 657 |
|
| 658 |
enjoy ! |
| 659 |
|
| 660 |
|
| 661 |
Resources |
| 662 |
--------- |
| 663 |
|
| 664 |
.. [#] The thread on python-dev started by Samuele Pedroni: |
| 665 |
https://mail.python.org/pipermail/python-dev/2002-October/029035.html |
| 666 |
|
| 667 |
.. [#] The paper *A Monotonic Superclass Linearization for Dylan*: |
| 668 |
https://doi.org/10.1145/236337.236343 |
| 669 |
|
| 670 |
.. [#] Guido van Rossum's essay, *Unifying types and classes in Python 2.2*: |
| 671 |
https://web.archive.org/web/20140210194412/http://www.python.org/download/releases/2.2.2/descrintro |