[Python-Dev] perplexed by mro (original) (raw)

Samuele Pedroni pedronis@bluewin.ch
Wed, 2 Oct 2002 00:45:39 +0200

[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.