共计 10789 个字符，预计需要花费 27 分钟才能阅读完成。
深刻了解 python 虚拟机：多继承与 mro
在本篇文章当中将次要给大家介绍 python 当中的多继承和 mro，通过介绍在多继承当中存在的问题就可能了解在 cpython 当中引入 c3 算法的起因了，从而可能帮忙大家更好的了了解 mro。
python 继承的问题
继承是一种面向对象编程的概念，它能够让一个类（子类）继承另一个类（父类）的属性和办法。子类能够重写父类的办法，或者增加本人的办法和属性。这种机制使得代码能够更加模块化和易于保护。在 Python 中，继承是通过在子类的定义中指定父类来实现的。例如：
class Animal:
def __init__(self, name):
self.name = name
def speak(self):
raise NotImplementedError("Subclass must implement abstract method")
class Dog(Animal):
def speak(self):
return "woof" 在这个例子中，咱们定义了一个 Animal 类和一个 Dog 类。Dog 类继承了 Animal 类，并且重写了 speak 办法。此时，如果咱们创立一个 Dog 实例并调用 speak 办法，它将返回 "woof"。
父类的批改会影响子类
当你批改父类的代码时，可能会影响到继承自它的子类。这是因为子类继承了父类的所有属性和办法，包含它们的实现。如果你批改了父类的实现，可能会导致子类的行为发生变化。因而，在批改父类代码时，你须要认真思考这个问题，并尽量避免对子类的影响。
多层继承的复杂性
在面向对象编程中，有时须要多层继承，即一个类继承自另一个继承自另一个类。这会导致代码的复杂性减少，因为你须要思考每个类之间的关系和可能呈现的命名抵触。另外，多层继承也会减少代码的耦合性，使得代码难以重构和保护。
多继承当中一个十分经典的问题就是棱形继承，菱形继承是指一个子类继承了两个父类，而这两个父类又继承自同一个基类的状况，如下图所示：
A
/ \
B C
\ /
D 在这种状况下，子类 D 会继承两份来自基类 A 的属性和办法，这可能会导致一些不必要的问题。例如，如果基类 A 中有一个名为 foo() 的办法，而基类 B 和 C 都别离重写了这个办法，并在子类 D 中调用了这个办法，那么子类 D 就无奈确定应该调用哪个版本的 foo() 办法。
另外一种状况就是在多继承的时候不同的基类定义了同样的办法，那么子类就无奈确定应该应用哪个父类的实现。例如，思考上面这个示例：
class A:
def method(self):
print('A')
class B:
def method(self):
print('B')
class C(A, B):
pass
c = C()
c.method() # 输入什么？ 在这个示例中，类 C 继承了类 A 和类 B 的 method 办法，然而这两个办法具备雷同的办法名和参数列表。因而，当咱们调用 c.method() 办法时，Python 将无奈确定应该应用哪个父类的实现。
为了解决下面所提到的问题，Python 提供了办法解析程序（Method Resolution Order，MRO）算法，这个算法能够帮忙 Python 确定办法的调用程序，也就是在调用的时候确定调用哪个基类的办法。
MRO
在 Python 中，多重继承会引起 MRO（Method Resolution Order，办法解析程序）问题。当一个类继承自多个父类时，Python 须要确定办法调用的程序，即优先调用哪个父类的办法。为了解决这个问题，Python 实现了一种称为 C3 算法的 MRO 算法，它是一种确定办法解析程序的算法。
咱们先来体验应用一下 python 的 mro 的后果是什么样的，上面是一个应用多重继承的示例：
class A:
pass
class B(A):
pass
class C(A):
pass
class D(B, C):
pass 在这个示例中，D 类继承自 B 类和 C 类，而 B 和 C 又都继承自 A 类。因而，D 类的 MRO 列表如下所示：
[D, B, C, A] 这个列表的解析程序为 D -> B -> C -> A，也就是说，当咱们调用 D 类的办法时，Python 会首先查找 D 类的办法，而后查找 B 类的办法，再查找 C 类的办法，最初查找 A 类的办法。
你可能会有疑难，为什么 cpython 须要这样去进行解析，为什么不在解析完类 B 之后间接解析 A，还要解析完类 C 之后再去解析 A，咱们来看上面的代码：
class A:
def method_a(self):
print("In class A")
class B(A):
pass
class C(A):
def method_a(self):
print("In class C")
class D(B, C):
pass
if __name__ == '__main__':
obj = D()
print(D.mro())
obj.method_a()下面的代码输入后果如下所示：
[<class '__main__.D'>, <class '__main__.C'>, <class '__main__.B'>, <class '__main__.A'>, <class 'object'>]
In class C 在下面的代码当中继承体系也是棱形继承，在类 A 当中有一个办法 method_a 其中类 B 继承了 A 然而没有重写这个办法，类 B 继承自 A 然而重写了这个办法，类 D 同时继承了类 B 和类 C，当对象 obj 调用办法 method_a 的时候发现在类 B 当中没有这个办法，这个时候如果间接在类 A 查找这个办法在很多状况下并不是咱们想要的，因为 D 继承了 C 如果 C 重写了这个办法的话咱们应该须要调用类 C 的 method_a 办法，而不是调用类 A 的 method_a。
从下面的案例咱们能够晓得，一个子类不可能跨过他的间接父类（D 的间接父类就是 B 和 C）调用更下层的办法，而是先须要在所有的间接父类查看是否有这个办法，在 cpython 的 mro 实现当中是可能保障这一点的，这种性质叫做“枯燥性”（monotonicity）。
C3 算法
C3 算法是 Python 中应用的 MRO 算法，它能够用来确定一个类的办法解析程序。首先咱们须要晓得的就是，当一个类所继承的多个类当中有雷同的基类或者定义了名字雷同的办法，会是一个问题。mro 就是我给他一个对象，他会给咱们返回一个类的序列，当咱们打算从对象当中获取一个属性或者办法的时候就会顺着这个序列从左往右进行查找，若查找胜利则返回，否则持续查找后续的类。
当初咱们来具体介绍一下 C3 算法的实现细节，这个算法的次要流程是一个递归求解 mro 的过程，假如 A 继承自 [B, C, D, E, F]，那么 C3 算法求 mro 的实现流程如下所示：
- mro(A) = [A] + merge(mro(B), mro(C), mro(D), mro(E), mro(F), [B, C, D, E, F] )
- merge 函数的原理是遍历传入的序列，找到一个这样的序列，序列的第一个类型只能在其余序列的头部，或者没有在其余序列呈现，并且将这个序列退出到 merge 函数的返回序列当中，并且将这个类从所有序列当中删除，反复这个步骤直到所有的序列都为空。
class O
class A extends O
class B extends O
class C extends O
class D extends O
class E extends O
class K1 extends A, B, C
class K2 extends D, B, E对 K2 求 mro 序列的后果如下所示：
L(K2) := [K2] + merge(L(D), L(B), L(E), [D, B, E])
= [K2] + merge([D, O], [B, O], [E, O], [D, B, E]) // 抉择 D
= [K2, D] + merge([O], [B, O], [E, O], [B, E]) // 不选 O，抉择 B 因为 O 在 [B, O] 和 [E, O] 当中呈现了而且不是第一个
= [K2, D, B] + merge([O], [O], [E, O], [E]) // 不选 O，抉择 E 因为 O 在 [E, O] 当中呈现了而且不是第一个
= [K2, D, B, E] + merge([O], [O], [O]) // 抉择 O
= [K2, D, B, E, O]咱们本人实现的 mro 算法如下所示：
from typing import Iterable
class A:
pass
class B(A):
pass
class C(A):
pass
class D(B, C):
pass
def mro(_type: type):
bases = _type.__bases__
lin_bases = []
for base in bases:
lin_bases.append(mro(base))
lin_bases.append(list(bases))
return [_type] + merge(lin_bases)
def merge(types: Iterable[Iterable[type]]):
res = []
seqs = types
while True:
seqs = [s for s in seqs if s]
if not seqs:
# if seqs is empty
return res
for seq in seqs:
head = seq[0]
if not [s for s in seqs if head in s[1:]]:
break
else:
# 如果遍历完所有的类还是找不到一个非法的类 则阐明 mro 算法失败 这个继承关系不满足 C3 算法的要求
raise Exception('can not find mro sequence')
res.append(head)
for s in seqs:
if s[0] == head:
del s[0]
if __name__ == '__main__':
print(D.mro())
print(mro(D))
assert D.mro() == mro(D)下面的程序的输入后果如下所示：
[<class '__main__.D'>, <class '__main__.B'>, <class '__main__.C'>, <class '__main__.A'>, <class 'object'>]
[<class '__main__.D'>, <class '__main__.B'>, <class '__main__.C'>, <class '__main__.A'>, <class 'object'>]只须要了解求解 mro 序列的过程，下面的代码比拟容易了解，首先就是递归求解各个父类的 mro 序列，而后将他们依照从左到右的程序放入到一个列表当中，最终将父类的 mro 序列进行 merge 操作，返回后果即可。
merge 函数的次要操作为，依照从左到右的程序遍历各个父类的 mro 序列，如果第一个类没有在其余父类的 mro 序列当中呈现，或者是其余父类 mro 序列当中的第一个类的话就能够将这个类退出到返回的 mro 列表当中，否则抉择下一个类的 mro 序列进行雷同的操作，直到找到一个合乎下面条件的类，如果遍历完所有的父类还是没有找到的话那么就报错。
Mypy 针对 mro 实现
mypy 是一个 python 类型的动态剖析工具，它也实现了 C3 算法用于计算 mro，上面是它的代码实现。
class MroError(Exception):
"""Raised if a consistent mro cannot be determined for a class."""
def linearize_hierarchy(info: TypeInfo, obj_type: Callable[[], Instance] | None = None
) -> list[TypeInfo]:
# TODO describe
if info.mro:
return info.mro
bases = info.direct_base_classes()
if not bases and info.fullname != "builtins.object" and obj_type is not None:
# Probably an error, add a dummy `object` base class,
# otherwise MRO calculation may spuriously fail.
bases = [obj_type().type]
lin_bases = []
for base in bases:
assert base is not None, f"Cannot linearize bases for {info.fullname} {bases}"
lin_bases.append(linearize_hierarchy(base, obj_type))
lin_bases.append(bases)
return [info] + merge(lin_bases)
def merge(seqs: list[list[TypeInfo]]) -> list[TypeInfo]:
seqs = [s.copy() for s in seqs]
result: list[TypeInfo] = []
while True:
seqs = [s for s in seqs if s]
if not seqs:
return result
for seq in seqs:
head = seq[0]
if not [s for s in seqs if head in s[1:]]:
break
else:
raise MroError()
result.append(head)
for s in seqs:
if s[0] is head:
del s[0] 下面的函数 linearize_hierarchy 就是用于求解 mro 的函数，下面的实现整体过程和咱们本人实现的 C3 算法是一样的，首先递归调用 linearize_hierarchy 计算失去父类的 mro 序列，最初将失去的 mro 进行 merge 操作。
cpython 虚拟机 mro 实现
在本大节当中次要给大家介绍一下在 cpython 当中 C 语言层面是如何实现 mro 的。须要晓得的 cpython 对于 mro 的实现也是应用咱们在下面提到的算法，算法原理也是一样的。
static PyObject *
mro_implementation(PyTypeObject *type)
{
PyObject *result;
PyObject *bases;
PyObject **to_merge;
Py_ssize_t i, n;
if (type->tp_dict == NULL) {if (PyType_Ready(type) < 0)
return NULL;
}
// 获取类型 type 的所有父类
bases = type->tp_bases;
// bases 的数据类型为 tuple
assert(PyTuple_Check(bases));
n = PyTuple_GET_SIZE(bases);
// 查看基类的 mro 序列是否计算出来了
for (i = 0; i < n; i++) {PyTypeObject *base = (PyTypeObject *)PyTuple_GET_ITEM(bases, i);
if (base->tp_mro == NULL) {
PyErr_Format(PyExc_TypeError,
"Cannot extend an incomplete type'%.100s'",
base->tp_name);
return NULL;
}
assert(PyTuple_Check(base->tp_mro));
}
// 如果是单继承 也就是只继承了一个类 那么就能够走 fast path
if (n == 1) {
/* Fast path: if there is a single base, constructing the MRO
* is trivial.
*/
PyTypeObject *base = (PyTypeObject *)PyTuple_GET_ITEM(bases, 0);
Py_ssize_t k = PyTuple_GET_SIZE(base->tp_mro);
result = PyTuple_New(k + 1);
if (result == NULL) {return NULL;}
// 间接将父类的 mro 序列加在 以后类的前面 即 mro = [以后类, 父类的 mro 序列]
Py_INCREF(type);
PyTuple_SET_ITEM(result, 0, (PyObject *) type);
for (i = 0; i < k; i++) {PyObject *cls = PyTuple_GET_ITEM(base->tp_mro, i);
Py_INCREF(cls);
PyTuple_SET_ITEM(result, i + 1, cls);
}
return result;
}
/* This is just a basic sanity check. */
if (check_duplicates(bases) < 0) {return NULL;}
/* Find a superclass linearization that honors the constraints
of the explicit tuples of bases and the constraints implied by
each base class.
to_merge is an array of tuples, where each tuple is a superclass
linearization implied by a base class. The last element of
to_merge is the declared tuple of bases.
*/
// 如果是多继承就要依照 C3 算法进行实现了
to_merge = PyMem_New(PyObject *, n + 1);
if (to_merge == NULL) {PyErr_NoMemory();
return NULL;
}
// 失去所有父类的 mro 序列，并将其保留到 to_merge 数组当中
for (i = 0; i < n; i++) {PyTypeObject *base = (PyTypeObject *)PyTuple_GET_ITEM(bases, i);
to_merge[i] = base->tp_mro;
}
// 和后面咱们本人实现的算法一样 也要将所有基类放在数组的最初
to_merge[n] = bases;
result = PyList_New(1);
if (result == NULL) {PyMem_Del(to_merge);
return NULL;
}
Py_INCREF(type);
PyList_SET_ITEM(result, 0, (PyObject *)type);
// 合并数组
if (pmerge(result, to_merge, n + 1) < 0) {Py_CLEAR(result);
}
PyMem_Del(to_merge);
// 将失去的后果返回
return result;
}在下面函数当中咱们能够剖析进去整个代码的流程和咱们在后面提到的 C3 算法一样，
static int
pmerge(PyObject *acc, PyObject **to_merge, Py_ssize_t to_merge_size)
{
int res = 0;
Py_ssize_t i, j, empty_cnt;
int *remain;
// remain[i] 示意 to_merge[i] 当中下一个可用的类 也就是说 0 - i-1 的类曾经被解决合并了
/* remain stores an index into each sublist of to_merge.
remain[i] is the index of the next base in to_merge[i]
that is not included in acc.
*/
remain = PyMem_New(int, to_merge_size);
if (remain == NULL) {PyErr_NoMemory();
return -1;
}
// 初始化的时候都是从第一个类开始的 所以下标初始化成 0
for (i = 0; i < to_merge_size; i++)
remain[i] = 0;
again:
empty_cnt = 0;
for (i = 0; i < to_merge_size; i++) {
PyObject *candidate;
PyObject *cur_tuple = to_merge[i];
if (remain[i] >= PyTuple_GET_SIZE(cur_tuple)) {
empty_cnt++;
continue;
}
/* Choose next candidate for MRO.
The input sequences alone can determine the choice.
If not, choose the class which appears in the MRO
of the earliest direct superclass of the new class.
*/
// 失去候选的类
candidate = PyTuple_GET_ITEM(cur_tuple, remain[i]);
// 查看各个基类的 mro 序列的尾部当中是否蕴含 condidate 尾部就是除去剩下的 mro 序列当中的第一个 剩下的类就是尾部当中含有的类 tail_contains 就是查看尾部当中是否蕴含 condidate
for (j = 0; j < to_merge_size; j++) {PyObject *j_lst = to_merge[j];
if (tail_contains(j_lst, remain[j], candidate))
// 如果尾部当中蕴含 condidate 则阐明以后的 candidate 不符合要求须要查看下一个 mro 序列的第一个类 看看是否符合要求 如果还不合乎就须要找下一个 再进行反复操作
goto skip; /* continue outer loop */
}
// 找到了则将 condidate 退出的返回的后果当中
res = PyList_Append(acc, candidate);
if (res < 0)
goto out;
// 更新 remain 数组，在后面咱们提到了当退出一个 candidate 到返回值当中的时候须要将这个类从所有的基类的 mro 序列当中删除（事实上只可能删除各个 mro 序列当中的第一个类）因而须要更新 remain 数组
for (j = 0; j < to_merge_size; j++) {PyObject *j_lst = to_merge[j];
if (remain[j] < PyTuple_GET_SIZE(j_lst) &&
PyTuple_GET_ITEM(j_lst, remain[j]) == candidate) {remain[j]++;
}
}
goto again;
skip: ;
}
if (empty_cnt != to_merge_size) {set_mro_error(to_merge, to_merge_size, remain);
res = -1;
}
out:
PyMem_Del(remain);
return res;
}
static int
tail_contains(PyObject *tuple, int whence, PyObject *o)
{
Py_ssize_t j, size;
size = PyTuple_GET_SIZE(tuple);
for (j = whence+1; j < size; j++) {if (PyTuple_GET_ITEM(tuple, j) == o)
return 1;
}
return 0;
}再谈 MRO
在本篇文章当中次要给大家介绍了多继承存在的问题，以及介绍了在 python 当中的解决方案 C3 算法。之所以被称作 C3 算法，次要是因为这个算法有以下三点个性：
- a consistent extended precedence graph
- preservation of local precedence order
- fitting a monotonicity criterion
咱们应用下面的图来剖析一下下面的三个个性是在阐明什么，在下面的继承关系当中类 A 当中有一个办法 method，类 B 和类 C 继承自类 A 并且类 C 重写了 method 办法，类 D 继承了 B 和 C。
- monotonicity 枯燥性，这个个性次要是阐明子类不可能跨过父类间接调用父类的父类的办法，比方在下面的类当中，当类 D 调用 method 办法的时候，调用的是类 C 的 method 办法而不是类 A 的 method 办法，尽管类 B 没有 method 而且类 A 有 method 办法，然而子类 D 不可能跨过父类 B 间接调用 类 A 的办法，必须查看类 C 是否有这个办法，如果有就调用 C 的，如果 B C 都没有才调用 A 的。
- preservation of local precedence order（保留部分优先程序），这一点示意 mro 要保障依照继承先后的程序去查找，也就是说先继承的先查找，比方 D(B, C) 那么如果同一个办法类 B 和类 C 都有，那么就会优先应用 B 当中的办法。
- a consistent extended precedence graph，这一点是相对来说比较复杂的，这个个性也是一个对于优先级的个性，是之前部分优先的扩大，他的意思是如果两个类 A B 有雷同的办法，如果 A 或者 A 的子类呈现在 B 或者 B 的子类之前，那么 A 的优先级比 B 高。比如说对于下图当中的继承关系 editable-scrollable-pane 继承自 scrollable-pane 和 editable-pane，editable-pane 继承自 editing-mixin 和 pane，scrollable-pane 继承自 scrolling-mixin 和 pane。当初有一个 editable-scrollable-pane 对象调用一个办法，如果这个办法只在 scrolling-mixin 和 editing-mixin 当中呈现，那么会调用 scrolling-mixin 当中的办法，不会调用 editing-mixin 当中的办法。这是因为对于 editable-scrollable-pane 对象来说 scrollable-pane 在 editable-pane 后面，而前者是 scrolling-mixin 的子类，后者是 editing-mixin 的子类，这是合乎后面咱们所谈到的规定。
上图来自论文 A Monotonic Superclass Linearization for Dylan，这篇论文便是 C3 算法的出处。如果你对这篇论文感兴趣的话，论文下载地址为 https://opendylan.org/_static/c3-linearization.pdf。
总结
在本篇文章当中次要给大家详细分析了 python 当中是如何解决多继承存在的问题的，并且详细分析了 C3 算法以及他在 python 和虚拟机层面的实现，最初简要介绍了 C3 算法的三个个性，通过仔细分析这三个个性能够帮忙咱们深刻了解整个继承树的调用链，当然在理论编程当中最好应用更简洁的继承形式，这也能够防止很多问题。
本篇文章是深刻了解 python 虚拟机系列文章之一，文章地址：https://github.com/Chang-LeHung/dive-into-cpython
更多精彩内容合集可拜访我的项目：https://github.com/Chang-LeHung/CSCore
关注公众号：一无是处的钻研僧，理解更多计算机（Java、Python、计算机系统根底、算法与数据结构）常识。
