C3 Method Resolution Order与Javascript多继承

admin

多继承，顾名思义即子类继承了多个父类，实际情况父类可能也继承自多个基类，那么子类都可能存在多个父类及祖先类。实现多继承的难点在于：如何计算子类继承父类及祖先类方法和属性的顺序。

阅读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');
  }
});

 

 

 

 

 

 

发表评论