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是一个合适的头，解析结束

中文 http://www.nanerbang.com/article/40/

JavaScript C3算法实现

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类多继承的过程：

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');

}

});

VeryOS

探索前端工程化

C3 Method Resolution Order与Javascript多继承

Python C3 算法介绍

JavaScript C3算法实现

declare.js 基于C3算法给JavaScript扩展多继承能力

发表回复取消回复

Python C3 算法介绍

JavaScript C3算法实现

declare.js 基于C3算法给JavaScript扩展多继承能力

发表回复 取消回复

发表回复取消回复