Is mro order depth-first or breadth-first?

Question

From Python in a Nutshell

The lookup of an attribute name in a class essentially occurs by visiting ancestor classes in left-to-right, depth-first order

However,

>>> class A(object): x = 'a'
... 
>>> class B(A): pass
... 
>>> class C(A): x = 'c'
... 
>>> class D(B, C): pass
... 
>>> D.x
'c'
>>> D.__mro__
(<class '__main__.D'>, <class '__main__.B'>, <class '__main__.C'>, 
    <class '__main__.A'>, <type 'object'>)

D.__mro__ lists the classes not in depth-first order, but breadth-first order. So do I misunderstand something? Thanks.

Answer 1

Ignoring classic classes, Python resolves method and attribute lookups using the C3 linearisation of the class and its parents. The C3 linearisation is neither depth-first nor breadth-first in complex multiple inheritance hierarchies. In some sense, it is:

depth-first until classes are encountered that will share a parent, and then breadth-first over those

although that is a very loose characterisation.

In particular however, in simple multiple inheritance hierarchies that do not share a parent, it is depth-first (conveniently ignoring object of course, which is always shared)

Simple Example – Depth First

>>> class a_0(object): pass
>>> class a_1(object): pass
>>> class b_0(a_0): pass
>>> class b_1(a_1): pass
>>> class c(b_0, b_1): pass

Then

>>> [x.__name__ for x in c.__mro__]
['c', 'b_0', 'a_0', 'b_1', 'a_1', 'object']

Shared Base Example – Depth then Breadth First

Note that in your example, you have a shared parent (A) which causes B and C to be traversed in a breadth first fashion. If you instead have an evern more complex hierarchy:

>>> class A(object): pass
>>> class B(A): pass
>>> class C(A): pass
>>> class D_0(B, C): pass
>>> class D_1(B, C): pass
>>> class E_0(D_0): pass
>>> class E_1(D_1): pass
>>> class F(E_0, E_1): pass

Then

>>> [x.__name__ for x in F.__mro__]
['F', 'E_0', 'D_0', 'E_1', 'D_1', 'B', 'C', 'A', 'object']

And you will observe that the search is depth first F, E_0, D_0 until it strikes the point where shared base classes are encountered (B and C that are also bases of D_1, at which point the depth first goes sideways to E_1 and depth first from there again.