16

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?

Peter Mortensen
  • 30,738
  • 21
  • 105
  • 131
Tim
  • 1
  • 141
  • 372
  • 590
  • Correct as far as I know. See https://youtu.be/EiOglTERPEo?t=32m32s – xaav Nov 05 '17 at 01:37
  • Also, depth-first really doesn't make sense. You could potentially have low-level objects calling high-level objects. – xaav Nov 05 '17 at 01:38
  • 1
    Here's a nice explanation of [C3 linearization method used in Python 2.3+](https://www.python.org/download/releases/2.3/mro/). – randomir Nov 05 '17 at 02:37
  • The issue with your quote is the word _"essentially"_. It means: For cases where there are no shared superclasses that are inherited more than once. As soon as that case happens, things become more complicated; see [donkopotamus' answer](https://stackoverflow.com/a/47117600). – Lutz Prechelt Jun 01 '21 at 08:02

1 Answers1

24

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.

donkopotamus
  • 22,114
  • 2
  • 48
  • 60
  • 1
    For completeness, the canonical document on Python's mro is this: https://www.python.org/download/releases/2.3/mro/ (up to today (python 3.8), despite Python 2.3 figuring in the article's title) – jsbueno Jul 09 '19 at 05:23