Debian Codegraph @

Doc/howto/mro.rst

raw
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