aaa90210 aaa90210 - 1 year ago 89
Python Question

Why does Python's C3 MRO depend on a common base class?

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.


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):

Here the MRO of KID is:
KID, A, B, X

However, if I changed B to be instead:

class B(object):

The MRO of KID becomes:
KID, A, X, B

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

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

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.

Answer Source

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

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

Note that nowhere it is said C3 is breadth first. If anything, it is depth first. See The Python 2.3 Method Resolution Order 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:

L[KID] = KID + merge(L[A], L[B], A, B)

where L[..] is the C3 linearisation of that class (their MRO).

So the linearisation of A comes before B 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.

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

L[KID] = KID + merge((A, X, object), (B, X, object), A, B)
#                        ^  ^^^^^^
#                         \ & \ both removed as they appear in the next list
       = KID + (A,) + (B, X, object)
       = (KID, A, B, X, object)

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

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)