多继承,顾名思义即子类继承了多个父类,实际情况父类可能也继承自多个基类,那么子类都可能存在多个父类及祖先类。实现多继承的难点在于:如何计算子类继承父类及祖先类方法和属性的顺序。
阅读dojo的源码偶然发现dojo.declare实现的多继承源自于python c3算法。实测发现dojo.declare解析出来的顺序,无法满足“局部优先级”和“单调性”两条原则,和python c3算法不一致,因此本文按照python c3算法来计算方法解析顺序,借鉴dojo.declare实现了自己的declare方法。
Python C3 算法介绍
我们约定一些简单的符号来简化某些描述,其中:
C1C2C3…CN
用来代表类列表[C1, C2, C3…, CN]。
列表的头(head)是它的第一个元素,尾(tail)是余下的部分:
head = C1
tail = [C2, C3…, CN]
用:
C + (C1C2C3…CN) = CC1C2C3…CN
来表示列表的和[C] + [C1, C2, C3, … , CN]。
用:
L[C]
表示类C的方法解析顺序。
考虑一个复杂继承层级中的类C,C继承自基类B1, B2, B3, … , BN。我们想要计算C的方法解析顺序(MRO),基于以上记号,可以将C3算法描述如下:
C的线性化是C加上其父类线性化的合并(merge)以及其父类列表的和。
用符号来表示为:
L[C(B1B2…BN)] = C + merge(L(B1)L(B2)…L(BN), B1B2…BN)
特别地,如果C是object类,该类没有任何父类,则其线性化很简单:
L(object) = object
可见C3算法的核心在于如何合并父类的线性华,C3算法合并规则如下:
取出第一个列表的头,也就是L[B1][0];如果该头不在其他列表的尾中,那么将该头添加到C的线性化中,并将其从merge操作的所有列表中删除,否则查看下一个列表的头并操作它,加入它符合要求。然后,重复该操作直到所有的类都被删掉或者无法再找到符合要求的头。在这种情况下,合并操作(merge)无法进行下去,python2.3将会拒绝创建类C并抛出一个错误。
现有A B C D E F X共7个类,其继承关系记为:
F(X) // F继承X
E(X) // E继承X
D(X) // D继承X
C(D, F) // C继承D, F
B(E, D) // F继承E, D
A(B, C) // A继承B, C
那么A的线性化计算过程可记为:
L[X] = X
L[D] = D X
L[E] = E X
L[F] = F X
L[B] = B + merge(EX, DX, ED) = B + E + merge(X, DX, D) = B + E + D + X
L[C] = C + merge(DX, FX, DF) = C + D + merge(X, FX, F) = C + D + F + X
L[A] = A + merge(BEDX, CDFX, BC)
L[A] = A + B + merge(EDX, CDFX, C) // B是一个合适的头
L[A] = A + B + E + merge(DX, CDFX, C) // E是一个合适的头
L[A] = A + B + E + C + merge(DX, DFX) // D不是一个合适的头,移动到第二个序列取头C,C是一个合适的头,返回第一个序列
L[A] = A + B + E + C + D + merge(X, FX) // D是一个合适的头
L[A] = A + B + E + C + D + F + merge(X, X) // X不是一个合适的头, 取F并返回当前第一个序列
L[A] = A + B + E + C + D + F + X // X是一个合适的头, 解析结束
C3算法更多详细内容参见:
英文 https://www.python.org/download/releases/2.3/mro/
中文 http://www.nanerbang.com/article/40/
JavaScript C3算法实现
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105 106 107 108 109 110 111 112 113 114 115 116 |
function c3mro(bases, cls) { var seqs = []; var clsnum = 0; var clsmap = {}; var tail = { pos: 0, map: {}, refs: [] }; // console.log(cls + ' mro =================') // build a proper data structure for (var i = 0, l = bases.length; i < l; ++i) { var base = bases[i]; var meta = base[cmeta]; var refs = meta ? meta.bases.slice(0) : []; var clsname = base.prototype[cname]; var seq = { pos: 0, map: {}, refs: refs }; tail.refs.push(base); tail.map[clsname] = true; for (var j = 0, s = refs.length; j < s; ++j) { clsname = refs[j].prototype[cname]; seq.map[clsname] = true; if (!clsmap[clsname]) { clsnum++; clsmap[clsname] = true; } } seqs.push(seq); } if (l > 1) { seqs.push(tail); } // console.log(seqs.slice(0), clsnum, seqs.length); // merge resolution order var linear = []; for (var i = 0;;) { if (!clsnum || i === seqs.length) { // end of seqs, or can not build linear mro break; } // console.log(['current seq ', i, ' of ', seqs.length].join('')) var seq = seqs[i]; var head = seq.refs[0]; // take head var clsname = head.prototype[cname]; // console.log('check head ' + clsname +' at ' + i); // test if it is a good head for (var j = 0; j < seqs.length; ++j) { if (i !== j) { var q = seqs[j]; if ((clsname in q.map) && q.refs[0].prototype[cname] !== clsname) { // console.log(clsname + ' is a bad head'); head = false; break; } } } // find a good head if (head) { // once we find a good head, go back to the head of seqs i = 0; clsnum--; linear.push(head); // console.log(clsname + ' is a good head'); // delete ref from all seqs for (var j = 0; j < seqs.length; ++j) { var q = seqs[j]; // delete it from current seq map delete q.map[clsname]; // delete it from current seq if (q.refs.length > 0 && q.refs[0].prototype[cname] === clsname) { q.refs.shift(); } // delete empty seq from seqs if (q.refs.length === 0) { // console.log(['splice ' + j]); if (j < i) { i--; } seqs.splice(j--, 1); continue; } // console.log(['seq refs ', j, q.refs.length]) } } // not a good head, move to next seq else { i++; } } if (clsnum) { throw new Error('can not build a consistent and linear method resolution order'); } // console.log(linear); return linear; } |
declare.js 基于C3算法给JavaScript扩展多继承能力
declare.js 在线测试:https://yessky.github.io/declare.js/example.html
declare.js 项目地址: https://github.com/yessky/declare.js
用 declare.js 实现以上A B C D E F X类多继承的过程:
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 |
var X = declare('X', null, { constructor: function() { this.name = 'X'; console.log('X'); }, protoName: 'X', protoFn: function() { console.log('X fn'); } }); var F = declare('F', [X], { constructor: function() { this.name = 'F'; console.log('F'); }, protoName: 'F', protoFn: function() { this.inherited(arguments); console.log('F fn'); }, protoF2: function() { console.log('F protoF2'); } }); var E = declare('E', [X], { constructor: function() { this.name = 'E'; console.log('E'); }, protoName: 'E' }); var D = declare('D', [X], { constructor: function() { this.name = 'D'; console.log('D'); }, protoName: 'D' }); var C = declare('C', [D, F], { constructor: function() { this.name = 'C'; console.log('C'); }, protoName: 'C' }); var B = declare('B', [E, D], { constructor: function() { this.name = 'B'; console.log('B'); }, protoName: 'B', protoFn: function() { this.inherited(arguments); console.log('B fn'); } }); var A = declare('A', [B, C], { constructor: function() { this.name = 'A'; console.log('A'); }, protoName: 'A', protoF2: function() { this.inherited(arguments); console.log('A protoF2'); } }); |