# The C3 linearization algorithm for method resolution in multiple inheritance OO languages: Looking for a justification for some implementation detail

According to this description of Python's method resolution order (mro), a.k.a. C3 linearization, the algorithm can be described recursively as follows:

L(O) = <O>
L(C) = <C> + merge(L(B1),..., L(Bn), <B1,...,Bn>)


where

• O is the class from which every class inherits.
• C is a class that inherits directly from B1, ..., Bn, in this order.
• < and > are list delimiters.
• + is the list-concatenation operator.
• merge merges its list arguments into a single list, in a manner to be described below.

The above can be rephrased in words (quoted from the above Python document):

the linearization of C is the sum of C plus the merge of the linearizations of the parents and the list of the parents.

The merge algorithm is described as follows (essentially quoted from the Python document, but slightly reworded):

Consider the head of the first list, i.e L(B1)[0]: if it is a good head, i.e. if it is not in the proper tail of any of the other lists, add it to the linearization of C, and remove it from all the lists in the merge. Otherwise, consider the head of the next list, etc. Repeat until no more classes, or no good heads. In the latter case, it is impossible to construct the merge.

The following example is given as an illustration. Suppose A inherits directly from B and C, in this order, and suppose that the linearizations of B and C are

L(B) = <B, D, E, O>
L(C) = <C, D, F, O>


Then A's linearization is

L(A) = <A> + merge(<B,D,E,O>, <C,D,F,O>, <B,C>)
= <A, B> + merge(<D,E,O>, <C,D,F,O>, <C>)
= <A, B, C> + merge(<D,E,O>, <D,F,O>)
= <A, B, C, D> + merge(<E,O>, <F,O>)
= <A, B, C, D, E> + merge(<O>, <F,O>)
= <A, B, C, D, E, F> + merge(<O>, <O>)
= <A, B, C, D, E, F, O>


My question is: in terms of the original description of the algorithm, what purpose does it serve to give the list <B1,...,Bn> of direct parents as an argument to merge? Will the algorithm produce different results if this argument is omitted?

Without the last list:

merge(<B,D,O>, <C,F,O>, <D,O>) =
<B,D,C,F,O>


With the last list:

merge(<B,D,O>, <C,F,O>, <D,O>, <B,C,D>) =
<B> + merge(<D,O>, <C,F,O>, <D,O>, <C,D>) =
<B,C> + merge(<D,O>, <F,O>, <D,O>, <D>) =
<B,C,D,F,O>


Without the last list:

merge(<B,D,C,O>, <C,F,O>, <D,O>) =
<B,D,C,F,O>


With the last list:

merge(<B,D,C,O>, <C,F,O>, <D,O>, <B,C,D>) =
<B> + merge(<D,C,O>, <C,F,O>, <D,O>, <C,D>) =
no-merge


Intuitively, the last list forces the final result to be compatible with the ordering <B1,...,Bn>. That might change the order, or make the merge fail.