mro is method resolution order, which is mainly used to determine the path of an attribute (from which class) in the case of multiple inheritance.
In python version 2.2, the basic idea of the algorithm was to compile a list, including the searched classes, based on the inheritance structure of each ancestor class, and remove duplicates according to a strategy. However, it has failed in maintaining monotonicity (order preservation), so from version 2.3, a new algorithm, C3, is used.
Why the C3 algorithm
The C3 algorithm was first proposed for Lisp, and was applied to Python to solve the problem that the original depth-first search-based algorithm did not satisfy local prioritization, and monotonicity.
Local Priority: refers to the order of the parent class at the time of declaration, for example, C(A,B), if accessing the attributes of the object of class C, it should be prioritized to look for class A and then class B according to the order of declaration.
Monotonicity: if A comes before B in the order of resolution of C, then this order must be satisfied in all subclasses of C as well.
C3 algorithm
To determine the mro a linear sequence has to be determined first and then the lookup path is determined by by the order of the classes in the sequence. So C3 algorithm is to generate a linear sequence.
If inheriting to a base class.
class B(A)
At this point the mro sequence of B is [B,A]
If you inherit to more than one base class
class B(A1,A2,A3 ...)
At this point the mro sequence of B mro(B) = [B] + merge(mro(A1), mro(A2), mro(A3) ... , [A1,A2,A3])
The merge operation is the heart of the C3 algorithm.
Iterates through the sequences that perform merge operations, if the first element of a sequence, is the first element in other sequences, or does not appear in other sequences, then removes this element from all sequences that perform merge operations and merges it into the current mro.
The sequence after the merge operation continues to perform the merge operation until the sequence of the merge operation is empty.
If the sequence of merge operations cannot be empty, it is not legal.
Example:
class A(O):pass
class B(O):pass
class C(O):pass
class E(A,B):pass
class F(B,C):pass
class G(E,F):pass
A, B, and C all inherit to a base class, so the mro sequence is [A,O], [B,O], [C,O] in that order
mro(E) = [E] + merge(mro(A), mro(B), [A,B])
= [E] + merge([A,O], [B,O], [A,B])
The sequence to perform the merge operation is [A,O], [B,O], [A,B]
A is the first element in the sequence [A,O], which does not appear in the sequence [B,O], and is also the first element in the sequence [A,B], so A is deleted from the sequences ([A,O], [B,O], [A,B]) in which the merge operation is performed and merged into the current mro, [E].
mro(E) = [E,A] + merge([O], [B,O], [B])
Perform the merge operation again, O is the first element in the sequence [O], but O appears in the sequence [B,O] and is not the first element in it. Continuing to look at the first element B of [B,O], B satisfies the condition, so B is removed from the sequence where the merge operation was performed and merged into [E, A].
mro(E) = [E,A,B] + merge([O], [O])
= [E,A,B,O]
Code to implement the C3 algorithm
#-*- encoding:GBK -*-#
def mro_C3(*cls):
if len(cls)==1:
if not cls[0].__bases__:
return cls
else:
return cls+ mro_C3(*cls[0].__bases__)
else:
seqs = [list(mro_C3(C)) for C in cls ] +[list(cls)]
res = []
while True:
non_empty = list(filter(None, seqs))
if not non_empty:
return tuple(res)
for seq in non_empty:
candidate = seq[0]
not_head = [s for s in non_empty if candidate in s[1:]]
if not_head:
candidate = None
else:
break
if not candidate:
raise TypeError("inconsistent hierarchy, no C3 MRO is possible")
(candidate)
for seq in non_empty:
if seq[0] == candidate:
del seq[0]