[Python-Dev] perplexed by mro

[Guido van Rossum]

> > Now let's assume m is *also* overridden in a, so that y.m overrides
> > a.m overrides object.m.  Now if we searched b before y (naive algo),
> > it is arguably strange if the 'super' call chain went from y.m via b.m
> > to a.m.
> 
> I don't understand that. According to the diagram I just
> scribbled, the mro from the documented algorithm comes out as
> 
>   z, x, b, y, a, c, object
> 
> so the super chain would be b.m, y.m, a.m, object.m.

Sorry, I misread my own scribbled diagram.  That's indeed the correct
order using the naive algorithm.  And I now agree that this is a fine
call chain.

> (Which is *also* wrong according to my intuition, by the way --
> I would expect a super call inside b.m to go to object.m,
> and not depend on z's inheritance structure -- but that's a
> separate issue.)

No, the whole point here is that the most inherited class's MRO
(i.e. z) can insert things in a base class's MRO.  Have a look at the
explanation of the diamond diagram in
http://python.org/2.2.1/descrintro.html

> Anyway, why not just use the algorithm you said you were
> using in the docs -- i.e. traverse the inheritance hierarchy
> and build the mro afresh each time, rather than trying to
> merge the mro's of the superclasses.

I would still construct a linearized MRO out of it -- many places
benefit from having it as a list rather than having to recurse down
the inheritance lattice.  But I agree that the naive algorithm seems
to have some nice properties -- at the very least, it is easy to
explain. :-)

If Samuele agrees that the naive algorithm works better, I'll try to
make it so in 2.3.

> If it's an issue of which algorithm is the one that should
> be used, I vote for the documented one, because it's
> simple and easy to explain! If it leads to odd things
> happening in some cases, at least it's clear what odd
> things will happen and why -- as opposed to other odd
> things happening for mysterious reasons.

Yes.  Here's how this happened: I had read and implemented the book's
algorithm without really visualizing what it did in more complex
cases.  In the few cases that I cared about it worked fine.  When I
had to document it, I realized that the description in the book is
very complicated, and I tried to come up with a simpler description.
That's how I stumbled upon the naive algorithm -- at first I believed
that it was really the same thing, but later I found a counter-example
with an order disagreements, so I added that.

Now Samuele has found another counter-example that does not involve an
order disagreement.  It does have a somewhat strange smell to it, 
but I can't pinpoint the quality of that smell, and it certainly
doesn't have an order disagreement.

I've updated the descrintro.html page to acknowledge the problems.

--Guido van Rossum (home page: http://www.python.org/~guido/)