Introduction to the new python multiple inheritance algorithm C3

Mro, or method resolution order, is primarily used to determine the path of an attribute (from which class) in case of multiple inheritance.

In python2.2, the basic idea of the algorithm is to compile a list of searched classes and remove duplicates by policy, based on the inheritance structure of each ancestor class. However, there was a failure to maintain monotonicity (save in sequence), so from version 2.3, the new algorithm C3 was adopted.

Why C3

The C3 algorithm was first proposed for Lisp, and was used in Python to solve the problem that the original depth-first search algorithm did not satisfy the local priority and monotonicity.

Local priority: refers to the order in which the parent class is declared, such as C(A,B). If you access the properties of the C class object, you should find the A class first, and then find the B class.

Monotonicity: if A comes before B in the analytic order of C, then this order must also be satisfied in all subclasses of C.

C3 algorithm

The mro is determined by a linear sequence, and the search path is determined by the order of the classes in the sequence. So the C3 algorithm is just generating a linear sequence.

If you inherit to a base class:

class B(A)

In this case, the mro sequence of B is [B,A].

If you inherit more than one base class

class B(A1,A2,A3 ...)

At this time B sequence of mro mro (B) = [B] + merge (mro (A1), mro (A2), mro (A3)... , A1, A2, A3)
The merge operation is at the heart of the C3 algorithm.

If the first element in a sequence is the first element in another sequence or is not present in another sequence, the element is removed from all sequences that perform the merge operation and merged into the current mro.

After the merge operation, continue the merge operation until the merge sequence is empty.

If the sequence of the merge operation cannot be empty, it is illegal.

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, C all inherit to A base class, so the sequence of mro is [A,O], [B,O], [C,O].

mro(E) = [E] + merge(mro(A), mro(B), [A,B])

       = [E] + merge([A,O], [B,O], [A,B])

The sequence of merge operations is [A,O], [B,O], [A,B]

A is the first element in the sequence [A,O], does not appear in the sequence [B,O], and is the first element in the sequence [A,B], so delete A from the sequence ([A,O], [B,O], [A,B]) that performs the merge operation, and merge into the current mro, [E].
Mro (E) = [E,A] + merge([O], [B,O], [B])

Merge again. O is the first element in the sequence [O], but O appears in the sequence [B,O] and is not the first element. Continue to look at the first element B of [B,O]. B satisfies the condition, so delete B from the sequence where the merge operation is performed and merge into [E, A].

mro(E) = [E,A,B] + merge([O], [O])

       = [E,A,B,O]

Implement the code of 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")  

              res.append(candidate)  

              for seq in non_empty:  

                  if seq[0] == candidate:  

                      del seq[0]