[Python-Dev] perplexed by mro

[Samuele Pedroni]

[me]
> >>> cpl.ex5(globals())
> class a(object): pass
> class b(object): pass
> class c(object): pass
> class x(a): pass
> class y(a): pass
> class z(x,b,y,c): pass
> >>> cpl.names(z.__mro__) # just the class names, real 2.2 mro algo
> ['z', 'x', 'y', 'a', 'b', 'c', 'object']
> >>> cpl.names(cpl.keeplast(cpl.lrdfs(z))) # descrintro simple algo
> ['z', 'x', 'b', 'y', 'a', 'c', 'object']
>
> I was not able to find a new rule. My intuition is that when the result of
the
> real mro has something to do with the dfs, it is sure from the beginning of
it
> not the end, so the relation of the two algos is unclear.

to clarify this point: even in the absence of any kind of inconsistency, if a
class INB (e.g. b above) get ordered as INB > R wrt to a class R recurring
multiple times in the different superclasses' mros (e.g. a above) in between
the first and last recurrence of that class R, the class INB will appear after
R in the final order, while the simple algo (see also example) would put INB
before R.
In fact in the example:  b follows a using the 2.2 mro; and b precedes a wrt
the simple algo. Although in the example there's no kind of inconsistency. The
mros of the superclasses of z being:

x a object [mro x]
b object [mro b]
y a object [mro y]
c object [mro c]

The mro 2.2 algo merges these mros successively, also mro x is merged with mro
b and the result is then merged with mro y and finally what has been obtained
so far is merged with mro c.

The merge step is as follows [python version of the c code in typeobject.c]

def conservative_merge(left,right):
    while 1:
        left_size = len(left)
        right_size = len(right)
        eq = 0
        for i in xrange(left_size):
            for j in xrange(right_size):
                if left[i] == right[j]:
                    print i,j
                    eq = 1
                    break
            if eq: break
        if eq:
            temp = []
            for r in range(j):
                rr = right[r]
                if rr not in left:
                    temp.append(rr)
            left[i:i] = temp
            right[0:j+1] = []
            continue
        break
    left.extend(right)

The algorithm move portions of right to left before merge points [shared
elements], the rest of right is attached at the end of left. That's way the
behavior explained above.

The algorithm merges left and right as sorted sequences, favoring left in the
case of a tie (assuming no incosistencies).


Btw: the algorithms in the paper I have cited all use some kind of parallel
merge of the superclasses' mros or some other constraints, not a sequential one
as the 2.2 mro algo.

regards.