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算法实现

 

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

 

 

 

 

 

 

发表回复

您的电子邮箱地址不会被公开。 必填项已用*标注