Why does Python's C3 MRO depend on a common base class?
<p>When I read about Python's C3 method resolution order, I often hear it reduced to "children come before parents, and the order of subclasses is respected". Yet that only seems to hold true if all the subclasses inherit from the same ancestor.</p>

<p>E.g.</p>

<pre><code>class X():
    def FOO(self):
        return 11

class A(X):
    def doIt(self):
        return super().FOO()        
    def FOO(self):
        return 42

class B(X):
    def doIt(self):
        return super().FOO()        
    def FOO(self):
        return 52

class KID(A,B):
    pass
</code></pre>

<p>Here the MRO of KID is:
KID, A, B, X</p>

<p>However, if I changed B to be instead:</p>

<pre><code>class B(object):
</code></pre>

<p>The MRO of KID becomes:
KID, A, X, B</p>

<p>It seems we are searching A's superclass before we have finished searching all KID's parents.</p>

<p>So it seems a bit less intuitive now than "kids first, breadth first" to "kids first, breadth first if common ancestor else depth first".</p>

<p>It would be quite the gotcha that if a class stopped using a common ancestor the MRO changes (even though the overall hierarchy is the same apart from that one link), and you started calling a deeper ancestor method rather than the one in that class.</p>

<p>All classes in Python 3 have a common base class, <code>object</code>. You can omit the class from the <code>class</code> definition, but it is there unless you already indirectly inherit from <code>object</code>. (In Python 2 you have to explicitly inherit from <code>object</code> to even have the use of <code>super()</code> as this is a new-style class feature).</p>

<p>You changed the base class of <code>B</code> from <code>X</code> to <code>object</code>, but <code>X</code> <em>also</em> inherits from <code>object</code>. The MRO changed to take this into account. The same simplification of the C3 rules (<em>children come before parents, and the order of subclasses is respected</em>) is still applicable here. <code>B</code> comes before <code>object</code>, as does <code>X</code>, and <code>A</code> and <code>B</code> are still listed in the same order. However, <code>X</code> should come before <code>B</code>, as both inherit from <code>object</code> and the subclass <code>A(X)</code> comes before <code>B</code> in <code>KID</code>.</p>

<p>Note that nowhere it is said C3 is breadth first. If anything, it is <strong>depth first</strong>. See <a href="https://www.python.org/download/releases/2.3/mro/" rel="nofollow"><em>The Python 2.3 Method Resolution Order</em></a> for an in-depth description of the algorithm and how it applies to Python, but the linearisation of any class is the result of merging the linearisations of the base classes plus the base classes themselves:</p>

<pre><code>L[KID] = KID + merge(L[A], L[B], (A, B))
</code></pre>

<p>where <code>L[..]</code> is the C3 linearisation of that class (their MRO).</p>

<p>So the linearisation of <code>A</code> comes before <code>B</code> when merging, making C3 look at hierarchies in depth rather than in breadth. Merging starts with the left-most list and takes any element that doesn't appear in the tails of the other lists (so everything but the first element), then takes the next, etc.</p>

<p>In your first example, <code>L[A]</code> and <code>L[B]</code> are almost the same (they both end in <code>(X, object)</code> as their MRO, with only the first element differing), so merging is  simple; you merge <code>(A, X, object)</code> and <code>(B, X, object)</code>, and merging these gives you only <code>A</code> from the first list, then the whole second list, ending up with <code>(KID, A, B, X, object)</code> after prepending <code>KID</code>:</p>

<pre><code>L[KID] = KID + merge((A, X, object), (B, X, object), (A, B))
#                        ^  ^^^^^^
#                         \ &amp; \ both removed as they appear in the next list
       = KID + (A,) + (B, X, object)
       = (KID, A, B, X, object)
</code></pre>

<p>In your second example, <code>L[A]</code> is <em>unchanged</em>, but <code>L[B]</code> is now <code>(B, object)</code> (dropping <code>X</code>), so merging prefers <code>X</code> before <code>B</code> as <code>(A, X, object)</code> comes first when merging and <code>X</code> doesn't appear in the second list. Thus </p>

<pre><code>L[KID] = KID + merge((A, X, object), (B, object), (A, B))
#                           ^^^^^^
#                            \removed as it appears in the next list
       = KID + (A, X) + (B, object)
       = (KID, A, X, B, object)
</code></pre>

python multiple-inheritance method-resolution-order