5

Why after searching B, it does not go deeper to search Y OR z but go to search A?

Y is the parent of A, if should search A first, but Y is the parent of B so it should search Y first, why this does not throw a MRO error?

Can someone explain how this lookup works?

class X(object):pass
class Y(object): pass
class Z(object): pass
class A(X,Y): pass
class B(Y,Z):pass
class M(B,A,Z):pass
print M.__mro__

gives

(<class '__main__.M'>, <class '__main__.B'>, <class '__main__.A'>, <class '__main__.X'>, <class '__main__.Y'>, <class '__main__.Z'>, <type 'object'>)

enter image description here

Lisa
  • 4,126
  • 12
  • 42
  • 71

1 Answers1

2

In your specific example, after searching B, we can't consider Y immediately because it is a child of A. We can't consider Z immediately because M inherits from A before it inherits from Z.

Python uses C3 method resolution order details here .

C3 resolution order solves the diamond inheritance problem well

In the example below, we have a very generic class Object that's a superclass of B and C. We only want method implementations (say of __repr__ or something) in Object to be considered if neither B nor C have an implementation.

         Object
         /   \
        B     C
         \   /
           A

In other words, each possible parent in the transitive closure of the parent classes of A is considered, but the classes are ordered according to the "latest" path from the base class to the class in question.

There are two paths to object:

A -> B -> Object
A -> C -> Object

The "latest" path is A -> C -> Object because A -> B -> Object would be earlier in a left-biased depth-first search.

C3 linearization satisfies two key invariants:

  • if X inherits from Y, X is checked before Y.
  • if Z inherits from U and then V in that order, U is checked before V.

Indeed C3 linearization guarantees that both of those properties hold.

It's possible to construct hierarchies that can't be linearized, in which case you get an exception at class definition time.

running inherit.py

class E: pass      
class F: pass
class A(E, F): pass
class B(F, E): pass
class Z(A, B): pass

produces the following error.

Traceback (most recent call last):
  File "inherit.py", line 5, in <module>
    class Z(A, B): pass
TypeError: Cannot create a consistent method resolution
order (MRO) for bases E, F
Greg Nisbet
  • 6,710
  • 3
  • 25
  • 65
  • Would you please speak to the example I give?@Gregory Nisbet? what is the reason that after checking B, it checks A instead of Y? After reading your explanation my understanding is: A inherits from X and Y, so we have to check A, not Y, is it? – Lisa Apr 15 '19 at 18:08
  • @Lisa ... Yes. We have to delay checking `Y` because `A` inherits from `Y` as well. classes with multiple inheritance paths to them are checked as late as possible. – Greg Nisbet Apr 16 '19 at 00:42
  • @Lisa Think of it this way: `M` is "more" like `A` because it inherits from `A` directly, unlike `Y`, which is only inherited indirectly (via `B` and `A`), which means we'd like to use a method definition from `A` in preference to one from `Y`. – chepner Apr 16 '19 at 00:56
  • @chepner I may be misinterpreting your comment, but it seems to suggest that we're traversing the inheritance hierarchy in a breadth first manner to look for method implementations, which isn't how C3 works. – Greg Nisbet Apr 17 '19 at 06:04
  • I just wanted to provided some intuition for *why* C3 puts `A` before `Y`. (Although, does C3 devolve to BFS as long as you never explicitly inherit from one of your parent's ancestors? Ten whole second's thought didn't provide a counterexample :)) – chepner Apr 17 '19 at 11:07
  • @chepner ... C3 devolves to DFS if we're in a tree. If `A < B, C` and `B < D < E` ... then we will check `A, B, D, E, C`. With the notation `X < P1, P2` meaning `X` inherits from `P1` and then `P2`. – Greg Nisbet Apr 17 '19 at 16:08
  • Ah, [this answer](https://stackoverflow.com/a/47118463/1126841) gives an example where C3 diverges from breadth-first, for reasons my comment doesn't cover. – chepner Apr 17 '19 at 17:01