Puzzling OO design problem

[Dirk Thierbach]

Dirk Thierbach <dthierbach at usenet.arcornews.de> wrote:

> Ok. Multiple inheritance can often select priority for conflicting
> methods. If you can specify yhat tou want "column priority" for
> each class, you're fine.

On second thought, I had doubts. Consider the following scenario:

   A2 | f   <-   A3 
   ^             ^    
   |             |    
   B2 | f   <-   B3   
   ^             ^    
   |             |    
   C2       <-   C3 | g

Assume g calls f. Since f is defined in B version 2, it should taken
over unchanged into B version 3, and that should be the version g
calls. However, with multiple inheritance doing depth-first search,
giving the "upper" class priority over the "left", the first path
searched is B3 - A3 - A2, and hence it finds f at A2. A quick test
confirms this for old-style classes, which failed in exactly that
way. But with new-style classes, it works, and finds f at B2 instead.

So I dug through the documentation and found that new-style classes
compute a monotonic linearization of the inheritance graph, observing
local precedence order, using the algorithm also used in Dylan
described here:

http://www.webcom.com/haahr/dylan/linearization-oopsla96.html

And this algorithm will even work correctly if one leaves out B3
in the example above, inheriting directly as in C3(A3,C2), because
the ordering constraint that A2 comes before B2 will still be
valid in the linearization for C3. 

However, in the following case (shortening the notation even more)
it will fail, if a method defined at C3 is looked up at D4:

   A1 - A2 - A3 - A4 - ...
   |    |    |    |
   B1 - B2 - +  - B4 - ...
   |    |    |    |
   C1 - +  - C3 - +  - ...
   |    |    |    |
   D1 - D2 - +  - D4 - ...
   |    |    |    |

The solution is simply to include C3 in the list of parents of D4, as
in D4(C3,B4,D2). So for every hole in a column, you have to include
the first class (or classes, if the hole spans multiple rows) to the
left of the hole as parents if the class just below the hole, in order
from bottom to top. This adds the missing constraints, and should
solve the problem without any need to write __metaclass__ stuff.

Interesting question. I learned a lot while thinking about that.

- Dirk