△ Click on the above “Python cat ” Focus on , reply “1” Get an e-book
Flower cat language ： Hello everyone , I'm brother cat , The article shared today is the contribution of a group friend , It introduces Python In multiple inheritance “ Black magic ”. The original blog post was very thoughtful in typesetting , I lost some effects when I edited it to official account , therefore , If you feel something wrong when reading , Or want a better reading experience , Please jump to the original .
author ：WH-2099
original text ：https://blog.wh2099.com/python/c3-mro
object-oriented programming （OOP） One of the important characteristics of is polymorphism （ Or subclass attributes / Method override ）, It is generally realized by searching the attributes and methods of objects in a specific order , This order is called Method Resolution Order (MRO).
This article shows Python in MRO The specific implementation of the generation algorithm , The algorithm logic is analyzed .
Not from 0 Is it difficult to start 1 Start ？ You know what? , There is only 10 people of the same race , Programmers and non programmers :)
Keep it simple, stupid !
To represent only one's point of view , Inevitably, there are omissions , Welcome to correct
This article assumes that you've learned about Python Master the basic content of object-oriented in
This article has a clear theme , Therefore, the default top-level base class is object（ Don't involve type About ）
Method parsing order （Method Resolution Order, MRO） Is in object-oriented programming in , When inheritance is applied to an instance object , causing polymorphic features , compile / Interpreter Find and determine the order of specific instance methods .
Distinguish according to the number of parent classes inherited by subclasses ,MRO There will be two situations ：
（1） In single inheritance MRO —— This is a relatively simple case .
（2） In multiple inheritance MRO —— This situation is relatively complex , And with the chaos of class inheritance hierarchy , Complexity is often beyond imagination .
Generally speaking MRO Basically, it refers to complex multiple inheritance MRO , Its essence is One order , It can be expressed by sequences in specific programming languages （Python The middle is collections.abc.Sequence）, This article is the same as the general situation .
Implementation method overload
structure OOP polymorphic
Ensure that inheritance is valid
In short ,MRO yes OOP（ object-oriented programming ） A top beam column of , Didn't it ,OOP Its features and advantages will be greatly discounted .
About MRO The role of , You can review OOP About China heavy load 、 Inherit 、 polymorphic The content of .
C3 superclass linearization（C3 Super class linearization algorithm ）, Its essence is a sort algorithm , Mainly used to generate multiple inheritance MRO（ Method parsing order ）.
1996 Year of OOPSLA The meeting , The paper "A Monotonic Superclass Linearization for Dylan" For the first time C3 Super class linearization algorithm . Then it was applied to Python 2.3 Medium and new type MRO analysis .
For the sake of narration , In this paper, it is called C3-MRO Algorithm （ Hyphenated suffixes indicate their practical application ）.
Python 2.2 Version to 2.3 When the version is excessive , In order to implement OOP Language level design , Existing Classic class On the basis of the new The new class .
Python 3 Classic classes are abandoned in , Only new types , so to speak The new type is Python 3 The default class used in .
The specific contents of the two types are not discussed here , But an important feature of the new class is that it inherits from... By default without explicitly declaring the inheritance parent class object class , coordination Python Syntax design that allows multiple inheritance , The initial stage has brought many problems to developers . A lot of reclusive bigwigs showed up in the Jianghu with all kinds of dark magic treasures , Unfortunately, they have not achieved enough results ：
PEP-253 The Python 2.3 Method Resolution Order (https://www.python.org/dev/peps/pep-0253/)
[Python-Dev] perplexed by mro (https://mail.python.org/pipermail/python-dev/2002-October/029035.html)
Finally, the developers found that , In fact, some scholars have long developed appropriate solutions ：1992 Apple launched Dylan Language ,1996 In, the related papers put forward C3 Algorithm .
therefore C3 Algorithm in 2003 In the year of , Took the solution Python 2.3 In the version The new class MRO What a mess .
these 2021 Year of Python 3.9.6 edition ,C3 The algorithm is still Python Solve multiple inheritance MRO The core algorithm of the problem .
( I really haven't heard of this Dylan Language XD )
in fact , stay Python in , You can use cls.__mro__ perhaps cls.mro() Get the MRO Sequence , And this is based on C3-MRO Algorithm ：
class A(object):
pass
class B(A):
pass
print(B.__mro__)
# (<class '__main__.B'>, <class '__main__.A'>, <class 'object'>)
print(b.mro())
# [<class '__main__.B'>, <class '__main__.A'>, <class 'object'>]
# The difference between the two is that they return tuple and listThe following is based on the author's understanding , With strong personal color , Unavoidably lack of objectivity .
But I think this way of thinking Relatively natural , I hope I can give you some inspiration ！
Let's put our thoughts aside first , have a look C3-MRO The specific content of the algorithm .
First of all, for the convenience of discussion , We agreed on some symbols ：
An ordered set of elements is called Sequence , Write it down as []
class C Of MRO Also known as C Linearization of , Write it down as L(C)=[C1,C2,⋯,CN]
stay L(C)=[C1,C2,⋯,CN] in , Call the first item C1 by L(C) Of head , Write it down as L(C)head
stay L(C)=[C1,C2,⋯,CN] in , Call the sequence of subsequent elements that remove the first item [C2,⋯,CN]（ Can be null ） by L(C) Of tail , Write it down as L(C)tail
Heads that do not appear in the tails of other sequences , We call it Good start , Write it down as H
The operation of connecting two sequences is recorded as +
meanwhile , according to OOP My general knowledge ：
remember object by The root class （ That is, the earliest Class in class inheritance , It is also a superclass of all other classes ）：
L(object)=[object]
If one class C Inherited from base class B1,B2,⋯,BN that C3-MRO The formula of the algorithm is ：
L(C)=[C]+merge(L(B1),L(B2),⋯,L(BN),[B1,B2,⋯,BN])
C3-MRO The main formula of the method is very clear , But there is also a self defining operation merge To be explained .
merge Is a special sequence merging operation , Accept multiple sequence inputs , Output a new sequence .
Take the main form as an example , The process is ：
First input sequence L(B1), take head L(B1)head
Check In the last step, take the tail of the input sequence after the header sequence Is there a relationship with The head removed in the previous step Same element ： If No, , explain L(B_1)head by Good start H , Extract it to the outer layer , Then delete the from all sequences Good start , go back to step 1 continue ; If Yes , take The head of the next input sequence L(B_2)head , From step 2 continue .
Repeat the above steps , Until the sequence is empty or no good head can be found ：
If The sequence is empty , Then the algorithm ends ;
If The sequence is not empty , And can't find the elements that can be output , that Python Will throw out TypeError abnormal .
It's no use saying more , Let's actually get started ：
It is strongly recommended that you read and try to derive this example yourself , This will help you understand the following .
This picture is taken from Wikipedia
# Here is the pseudo code representation
O=object
class A(O)
class B(O)
class C(O)
class D(O)
class E(O)
class K1(A, B, C)
class K2(D, B, E)
class K3(D, A)
class Z(K1, K2, K3)Don't worry , Don't be afraid of , It's not complicated , It just looks longer , Let's go step by step .
Let's try the simple , From being a root class O（ That is to say object） How about the beginning ：
L(O) := [O] OK, let's make it a little more difficult , Let's see A ：
L(A) := [A] + merge(L(O), [O]) # First expand the main formula
= [A] + merge([O], [O]) # Then expand the linearization operation on the right L(O)=O
= [A, O] # head O Not in the tail of other sequences , Put forward OHave you found a feeling ？ Try to complete the following by yourself ：
L(B) := [B, O]
L(C) := [C, O]
L(D) := [D, O]
L(E) := [E, O]Do you think the above calculations are actually a bit of a fuss ？
This is mainly because up to now, it is only Single inheritance , With intuitive feeling is completely enough .
But then it's time for this algorithm to show its magic , Let's see Multiple inheritance The situation of ：
# Here is more complicated
# take your time , Don't worry
L(K1) := [K1] + merge(L(A), L(B), L(C), [A, B, C]) # First expand the main formula
= [K1] + merge([A, O], [B, O], [C, O], [A, B, C]) # Then expand the linearization operation in which we have obtained the result
= [K1, A] + merge([O], [B, O], [C, O], [B, C]) # Start with the first sequence ：A It's a good start , Bring it out
= [K1, A, B] + merge([O], [O], [C, O], [C]) # O Not a good start , No problem , Start with the next sequence ,B It's a good start , extracted
= [K1, A, B, C] + merge([O], [O], [O]) # C ditto
= [K1, A, B, C, O] # It's obvious here , There is even no tail that can compare with the head （ All empty tails ）, Put forward O
######### The next step is to repeat the process
L(K2) := [K2] + merge(L(D), L(B), L(E), [D, B, E])
= [K2] + merge([D, O], [B, O], [E, O], [D, B, E])
= [K2, D] + merge([O], [B, O], [E, O], [B, E])
= [K2, D, B] + merge([O], [O], [E, O], [E])
= [K2, D, B, E] + merge([O], [O], [O])
= [K2, D, B, E, O]
L(K3) := [K3] + merge(L(D), L(A), [D, A])
= [K3] + merge([D, O], [A, O], [D, A])
= [K3, D] + merge([O], [A, O], [A])
= [K3, D, A] + merge([O], [O])
= [K3, D, A, O]
L(Z) := [Z] + merge(L(K1), L(K2), L(K3), [K1, K2, K3])
= [Z] + merge([K1, A, B, C, O], [K2, D, B, E, O], [K3, D, A, O], [K1, K2, K3])
= [Z, K1] + merge([A, B, C, O], [K2, D, B, E, O], [K3, D, A, O], [K2, K3])
= [Z, K1, K2] + merge([A, B, C, O], [D, B, E, O], [K3, D, A, O], [K3])
= [Z, K1, K2, K3] + merge([A, B, C, O], [D, B, E, O], [D, A, O])
= [Z, K1, K2, K3, D] + merge([A, B, C, O], [B, E, O], [A, O])
= [Z, K1, K2, K3, D, A] + merge([B, C, O], [B, E, O], [O])
= [Z, K1, K2, K3, D, A, B] + merge([C, O], [E, O], [O])
= [Z, K1, K2, K3, D, A, B, C] + merge([O], [E, O], [O])
= [Z, K1, K2, K3, D, A, B, C, E] + merge([O], [O], [O])
= [Z, K1, K2, K3, D, A, B, C, E, O]MRO The essence is The order , And for generating this order C3-MRO Algorithm , In essence, it is a Sorting algorithm .
Individual is from Multi attribute sorting To understand from the perspective of C3-MRO Algorithm .
The core problem in multi-attribute sorting , In fact, that is Determine the priority between attributes .
know of Three laws of robotics Do you ? If you see it for the first time . You might as well know .
As a programmer , This is the problem we will face sooner or later XD
Personally think that , We can put C3-MRO The core idea of the algorithm is summarized as MRO The three law ：
Ⅰ. MRO Ensure that the subclass is in front of the parent .
Ⅱ. MRO Monotonicity should be maintained , But it cannot be violated Ⅰ.
Ⅲ. MRO Local priority should be followed , But it cannot be violated Ⅰ or Ⅱ .
that ,MRO The three law How is it embodied in the specific algorithm ？
This is the basic foothold of inheritance and polymorphism .
example ： Subclasses can overload the properties and methods of the parent class （ This feature is called polymorphism ）
This law is mainly reflected in the algorithm ：
（1）C It is its own subclass , So in the main formula of the algorithm, we will first put C Pull it out , Then recursively call its parent class in order
L(C)=[C]+merge(L(B1),L(B2),⋯,L(BN),[B1,B2,⋯,BN])
This operation is trivial , It seems a little unworthy of its highest status as the first law ？
No , On the contrary , The greatest truths are the simplest ！
it is to be noted that , The algorithm is recursive Of , This Small operation It will build a whole in layers of recursion step by step Great order .
We can think about the process of recursion ：
Recursion calls itself again and again , The last layer recurses in object return .
The outer layer of recursion takes out the current class （ That is to say object Subclasses of ）, Put it at the front .
The outer layer of recursion takes out the current class （object Subclasses of subclasses of ）, Put it at the front .
The outer layer of recursion takes out the current class （object Subclasses of subclasses of subclasses of ）, Put it at the front .
⋯⋯
⋯
The call starts at the bottom of the inheritance structure tree （ Now up ）, Recursive return is in the reverse order of the call （ The first reversal , Now down ）;
Each time the current class is placed at the top of the sequence , It will construct a sequence opposite to the traversal order （ The second reversal , Now up ）;
So the final generated sequence is in the same direction as the recursive call （ The truth that the opposite is the right ）.
This little operation , Actually, let's finish Traverse up the inheritance structure tree .
（2）merge Search for good heads and extract （ Judgment not included in the native parent sequence at the end ）
L(C)=[C]+merge(L(B1),L[B2],⋯,L[BN],[B1,B2,⋯,BN])
(1) It determines that our general direction is to follow the inheritance structure all the way up , But there's a problem , That is how to choose the direction of the next step when the concrete inheritance generates bifurcation ：
Here we assume that class C(A, B)
C -> A Then what should we do next ,C -> A -> B -> O still C-> A -> O -> B ？
Obviously , To ensure subclasses B In his father's class O In front of , Our decision should be C -> A -> B -> O .
As the winner of the dark magic war ,C3-MRO The algorithm can naturally make the same smart decisions .
We judge by visual observation of graphics , So how does the algorithm do it ？
Let's take a look at the specific derivation ：
O Appear in other sequences as headers （ Does not contain the last native parent sequence ） In the tail of
⇕
O The rest are still not inherited （ The inherited ones have been extracted out ） The parent class of the class
The above two lines are essentially the same , therefore merge Pass through Find a good header in the sequence that does not contain the last native parent The operation of is completed The choice at the bifurcation of the inheritance structure . In fact, I prefer to name this operation * Recognize one's family * XD
A class of MRO Maintained and contained in any of its subclasses MRO in .
example ：C Of MRO in B1 and B2, And B1 stay B2 Before , It's in C Of any subclass of MRO in , Also exist B1 and B2, And B1 stay B2 Before .
Monotonicity ensures the most basic MRO Of stability , It will not change due to different query starting points .
in fact ,C3-MRO The algorithm can finally stand out , The main reason is that Python 2.3 The first part of the version is candidate Black magic in , Only it shows good monotony .
The rest of the dark magic can deal with most of the multi inheritance problems , However, monotony cannot be maintained under certain circumstances .
This law is mainly reflected in the algorithm ： The equality form of the main formula of the algorithm and the logic of its recursive traversal .
L(C)= [C]+merge(L(B1),L(B2),⋯,L(BN),[B1,B2,⋯,BN])
L(C) := [C] + merge(L(A), L(B), [A, B])
= [C] + merge([A, O], [B, O], [A, B])
= [C, A] + merge([O], [B, O], [B]) # We found that O Not a good start , So I skipped it
= [C, A, B] + merge([O], [O],)
= [C, A, B, O]in fact , this Similar to mathematical induction , Any subsequent round of calculation is based on the results of the previous round , Nature can keep monotony . Of course ,merge The specific operation is also very important , But it's really hard to illustrate , So I won't state it here .
The base class higher in the inheritance sequence , The higher the priority .
example ：
class C(A, B)Contains semantics ： Build type C, Inherit first A, Secondly, inheritance B.
This is a Python Basic syntax design of multiple inheritance , In order to Ensure programmer control over inheritance .
No matter what language it is , It is necessary to ensure that users have full control .
This law is mainly reflected in the algorithm ：merge The last native parent sequence in .
L(C)=[C]+merge(L(B1),L(B2),⋯,L(BN),[B1,B2,⋯,BN])
actually merge The last native parent sequence only works in some cases .
If you don't believe it, you can look back 3.0 An example at the end of the section , In the process of actual derivation, remove merge The native parent sequence at the end , Eventually you will find that the results have not been affected .
So when will it work ？ Let's take a special example ：
It is assumed here that class B(O, A)
L(B) := [B] + merge(L(O), L(A), [O,A])
= [B] + merge([O], [A,O], [O,A])
# Here we first take O For the head , But it clearly appears at the end of the second sequence , Not a good start
# We start with the head of the second sequence A continue , But what we found was that , It's not a good start
# Then take the head of the third sequence O , unfortunately , It's not . Final , There is no good beginning , trigger TypeError Here suddenly jumped out TypeError yes Python The painstaking efforts of designers , The purpose is to prevent developers from creating this kind of in OOP A conceptually logically chaotic inheritance system , Solve the problem of multiple inheritance from the root .
But here we don't talk about OOP Related issues of concept , Just for “MRO The three law ” Say the reason ：
First , In consideration of local priority , We should choose B -> O -> A, But that's what it's all about In violation of article Ⅰ The laws of .
ok , Let's just leave it alone The first Ⅲ The laws of 了 , go B -> A -> O got . However, in some complex structures （ In view of the length , No show here , Its essence is that programmers cannot effectively control inheritance priority ） There will be again Monotony is broken , The first Ⅱ The law is violated The situation of .
stay 1 in , The most important part Ⅰ The law is broken ; stay 2 in , The first Ⅱ Law and article Ⅲ The law is broken at the same time .
In fact? , And Three laws of robotics The same thing ,MRO The three law Under certain circumstances Generate confrontation between laws .
Although we have designed priorities between laws to deal with , But confrontation will definitely be a Bad situation , Because it must Violate at least one of these laws .
We just TypeError In the case of , All three laws are threatened , So we need to avoid this happening .
Python Language designers take this into account , Just throw it out TypeError, Prevent developers from creating ambiguous and confusing inheritance structures .
Have to say , Even close 20 Looking back on today, years later , This algorithm is still elegant and efficient .
Please note that ： Thought and algorithm are essentially one and two sides , Complete decoupling is unrealistic , Therefore, the author here only selects the easy to understand part to say , More content is left for you to comprehend .
Talk is cheap. Show me the code.
Don't talk nonsense , Put it in code. .
The author wrote C3-MRO Of Python Code implementation , Please refer to the notes for specific instructions .
Wikipedia The content on is also edited and updated by the author
def c3_mro(cls):
if cls is object:
# The discussion assumes that the top-level base class is object , Recursive termination
return [object]
# structure C3-MRO The general formula of the algorithm , Recursion begins
merge_list = [c3_mro(base_cls) for base_cls in cls.__bases__]
merge_list.append(list(cls.__bases__))
mro = [cls] + merge(merge_list)
return mro
def merge(in_lists):
if not in_lists:
# If the merged content is empty , Returns an empty list
# Cooperate with the exclusion space below list operation , Recursive termination
return []
# Traverse to merge MRO
for mro_list in in_lists:
# Take the head
head = mro_list[0]
# Traverse to merge MRO（ Same as the outer layer ）, Check whether there is a head in the tail
for cmp_list in in_lists:
if cmp_list is mro_list:
continue
if head in cmp_list[1:]:
break
else:
# Select the good head
next_list = []
for merge_item in in_lists:
if head in merge_item:
merge_item.remove(head)
if merge_item:
# Exclude empty list
next_list.append(merge_item)
# Recursion begins
return [head] + merge(next_list)
else:
# There is no good beginning , Cause the wrong type
raise TypeErrorNext I will give two Open questions , If you are interested, you can leave your views on these two issues in the comment area .q(≧▽≦q)
There is a base class
O, Defines the methodf,AClass inheritedOclass ,BClass inheritedOClasses andAclass . So there's a problem ,BClassfHow to call ？
Horror diamond inheritance problem ：
There is a base class
O, Defines the methodf,AClasses andBClass inheritedOclass ,CClass inheritedAandBclass . So there's a problem ,DClassfHow methods should be called ？
stay Python3 Popular today , This is the most normal operation .
（ hold O regard as object ,Python 3 All classes inherit from by default object ）
But in the use of Python 2.2 A typical class Of 21 At the beginning of the century , These two problems do not know how many developers Brilliant XD！
Some people are afraid of it , In the name of devil and terror .
Of course ,C3-MRO These two problems have been well solved .
But if the context of specific language implementation is stripped , Look at it purely from the perspective of object-oriented design , The answers to these two questions are completely open .
Discussion and exchange are the necessary ways of knowledge dissemination , You may wish to leave your views on these two issues in the comment area .(～￣▽￣)～
The Python 2.3 Method Resolution Order
The paper A Monotonic Superclass Linearization for Dylan
C3 Linearization algorithm and MRO—— understand Python More inheritance in
C3 linearization
The thread on python-dev started by Samuele Pedroni
PEP 253 -- Subtyping Built-in Types
Python Method parsing order MRO-C3 Algorithm
Python The cat technology exchange group is open ！ In the group, there are in-service employees of the first and second tier large factories in China , There are also students at home and abroad , There are more than ten years old programming birds , There are also new people who have just entered primary and secondary schools , The learning atmosphere is good ！ Students who want to join the group , Please reply in the public number 『 Communication group 』, Get brother cat's wechat （ No advertising party , If you are the one ！）~
Not yet ？ Try them
▲8.5K Star! Python Code memory analysis tool
▲Python Where did the metaclass design of come from ？
▲80 An example , To master thoroughly Python Date time processing ！
▲pip 20.3 New version released ！ To abandon Python 2.x
▲ Tired of conventional class definition writing ？ Give you six alternatives ！
▲Python Cat Recommendation System IV ：《Python Source analysis 》
If you find this article helpful
Please share generously and give the thumbs-up , Thank you ！
