C3 Method Resolution Order与Javascript多继承
多继承,顾名思义即子类继承了多个父类,实际情况父类可能也继承自多个基类,那么子类都可能存在多个父类及祖先类。实现多继承的难点在于:如何计算子类继承父类及祖先类方法和属性的顺序。
阅读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算法实现
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类多继承的过程:
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'); } });