动态调度之道——方法解析顺序

本文也是原博客的搬运重写,主要拿 Python 历代的 MRO (Method Resolution Order) 算法实现来介绍。

其实这玩意儿到底叫什么我也比较懵逼,我只是简单的按照 Wikipedia 给出的几个条目写点东西而已(逃), Wikipedia 上, Python 动态调度被归类到 Smalltalk 一类,但是 Smalltalk 的具体实现我不了解,所以这里选择性无视 Smalltalk 。

对于支持自省 (Introspection) 甚至反射的语言来说,可以甚至必要在运行时查找父类的成员再去调用之。在单继承的语言中(如 JS 的原型链)只需要往上不停回溯查找直到继承树的顶端即可,但是在多继承的语言中,找到合适的父类并不是一件简单的事情。下面就从 Python 的 MRO 解析发展历史来说一说为什么不简单。

MRO 列表在 Python 的各个版本都可以使用 inspect 库中的 getmro 函数获取。

旧式深搜

在 Python 2.1 及之前的旧式类中,还没有公共父类 object 这东西,但是仍然允许多继承,所以也有菱形继承的问题。旧式类的 MRO 解析算法,也就是简单深搜对于菱形继承的处理很不符合直觉。

执行查找的函数在文件 /Objects/classobject.c 的 class_getattr 函数中进行,然后调用 class_lookup ,这个函数是深搜,贴一下代码:

static PyObject *
class_lookup(PyClassObject *cp, PyObject *name, PyClassObject **pclass)
{
    int i, n;
    PyObject *value = PyDict_GetItem(cp->cl_dict, name);
    if (value != NULL) {
        *pclass = cp;
        return value;
    }
    n = PyTuple_Size(cp->cl_bases);
    for (i = 0; i < n; i++) {
        /* XXX What if one of the bases is not a class? */
        PyObject *v = class_lookup(
            (PyClassObject *)
            PyTuple_GetItem(cp->cl_bases, i), name, pclass);
        if (v != NULL)
            return v;
    }
    return NULL;
}

static PyObject *
class_getattr(register PyClassObject *op, PyObject *name)
{
    register PyObject *v;
    register char *sname = PyString_AsString(name);
    PyClassObject *class;
    if (sname[0] == '_' && sname[1] == '_') {
        if (strcmp(sname, "__dict__") == 0) {
            if (PyEval_GetRestricted()) {
                PyErr_SetString(PyExc_RuntimeError,
               "class.__dict__ not accessible in restricted mode");
                return NULL;
            }
            Py_INCREF(op->cl_dict);
            return op->cl_dict;
        }
        if (strcmp(sname, "__bases__") == 0) {
            Py_INCREF(op->cl_bases);
            return op->cl_bases;
        }
        if (strcmp(sname, "__name__") == 0) {
            if (op->cl_name == NULL)
                v = Py_None;
            else
                v = op->cl_name;
            Py_INCREF(v);
            return v;
        }
    }
    v = class_lookup(op, name, &class);
    if (v == NULL) {
        PyErr_SetObject(PyExc_AttributeError, name);
        return NULL;
    }
    Py_INCREF(v);
    if (PyFunction_Check(v)) {
        PyObject *w = PyMethod_New(v, (PyObject *)NULL,
                            (PyObject *)class);
        Py_DECREF(v);
        v = w;
    }
    return v;
}

cp->cl_dict 就是类的 .__dict__ 成员,通过在其中搜索 PyObject *name ,实际上就是需要 getattr 的成员的 PyString 。如果找到了想要的成员就直接返回,否则继续搜索保存着直接基类的 PyTuple 中的下一项,直到找到为止。如果没找到返回的是一个 NULL ,并且抛出一个 PyExc_AttributeError

直接深搜带来的问题是搜索继承树的时候,第一个直接基类的基类们将会成为第一批被搜索的对象,于是在遇到菱形继承的时候,这种算法就会暴露出问题,举个例子:

class Ancestor:
    def foo(self):
        print 'Ancestor'

class Father(Ancestor):
    pass

class Mother(Ancestor):
    def foo(self):
        print 'Mother'

class Child(Father, Mother):
    pass

Child().foo()

这样的代码,从直觉上来说, MotherAncestor 更泛化,在调用 Child().foo() 的时候自然应当先调用 Mother().foo() 。但是实际上输出的是反直觉的 Ancestor

另一个令人蛋疼的是,每次需要动态调度的时候, Python 都会调用一遍这个 class_getattr ,也就是每次都会深搜一遍,这在类的继承结构变得复杂的时候消耗是很大的。

新式深搜

考虑到这些问题, Python 在 2.2 使用了一种新的算法和新的全局基类 object ,所有新式类都继承自 object ,为了向后兼容而保留了旧式类,也就是使用简单深搜的类。

在相应的增强提案 (PEP 253) 中提到了这方面的更新:

Using the classic lookup rule, construct the list of classes that would be searched, including duplicates. Now for each class that occurs in the list multiple times, remove all occurrences except for the last.

这段话的含义是对于每个直接或间接基类,只保留其于深搜序中最后一次出现的为止。但是实际上在我自己的测试中发现, Python 2.2 使用的完全不是这个方法,按注释中所说,是模仿一本书上的算法实现的,代码在 Object/typeobject.c 中,大致由两个函数 mro_implementationconservation_merge 组成:

/* Method resolution order algorithm from "Putting Metaclasses to Work"
   by Forman and Danforth (Addison-Wesley 1999). */

static int
conservative_merge(PyObject *left, PyObject *right)
{
  int left_size;
  int right_size;
  int i, j, r, ok;
  PyObject *temp, *rr;

  assert(PyList_Check(left));
  assert(PyList_Check(right));

  again:
  left_size = PyList_GET_SIZE(left);
  right_size = PyList_GET_SIZE(right);
  for (i = 0; i < left_size; i++) {
    for (j = 0; j < right_size; j++) {
      if (PyList_GET_ITEM(left, i) ==
          PyList_GET_ITEM(right, j)) {
        /* found a merge point */
        temp = PyList_New(0);
        if (temp == NULL)
          return -1;
        for (r = 0; r < j; r++) {
          rr = PyList_GET_ITEM(right, r);
          ok = PySequence_Contains(left, rr);
          if (ok < 0) {
            Py_DECREF(temp);
            return -1;
          }
          if (!ok) {
            ok = PyList_Append(temp, rr);
            if (ok < 0) {
              Py_DECREF(temp);
              return -1;
            }
          }
        }
        ok = PyList_SetSlice(left, i, i, temp);
        Py_DECREF(temp);
        if (ok < 0)
          return -1;
        ok = PyList_SetSlice(right, 0, j+1, NULL);
        if (ok < 0)
          return -1;
        goto again;
      }
    }
  }
  return PyList_SetSlice(left, left_size, left_size, right);
}

static PyObject *
mro_implementation(PyTypeObject *type)
{
    int i, n, ok;
    PyObject *bases, *result;

    if(type->tp_dict == NULL) {
        if(PyType_Ready(type) < 0)
            return NULL;
    }

    bases = type->tp_bases;
    n = PyTuple_GET_SIZE(bases);
    result = Py_BuildValue("[O]", (PyObject *)type);
    if (result == NULL)
        return NULL;
    for (i = 0; i < n; i++) {
        PyObject *base = PyTuple_GET_ITEM(bases, i);
        PyObject *parentMRO;
        if (PyType_Check(base))
            parentMRO = PySequence_List(
                ((PyTypeObject*)base)->tp_mro);
        else
            parentMRO = classic_mro(base);
        if (parentMRO == NULL) {
            Py_DECREF(result);
            return NULL;
        }
        if (serious_order_disagreements(result, parentMRO)) {
            Py_DECREF(result);
            return NULL;
        }
        ok = conservative_merge(result, parentMRO);
        Py_DECREF(parentMRO);
        if (ok < 0) {
            Py_DECREF(result);
            return NULL;
        }
    }
    return result;
}

源码虽然有点长,不过其实很多都是错误检查处理,它的逻辑还是简单的(毕竟是暴力)。在 Python 2.2 中开始在定义类的时候就计算出 .__mro__ ,之后再 getattr 的时候就直接从 .__mro__ 中搜索了,在上面的代码中 mro_implementation 函数就是用来计算类的 .__mro__ 的。

简单介绍一下这两个函数的流程,在 mro_implementation 中会对直接基类进行迭代,通过检查该类是不是类 type 或其派生类的实例(也就是元类是不是 type 或其派生类)来区分新式类或旧式类,并分别使用不同的方式获取 mro 。旧式类用 classic_mro 函数,也就是简单深搜,细节就略过了,具体的实现在同文件下相应的函数中。对于新式类而言,已经在创建的时候计算出了它的 mro ,所以可以直接获取,这里将其拷贝了一份传入了 conservation_merge 函数。

获取 parentMRO 之后有一个 serious_order_disagreements 检查,不过这个函数是空的,永远返回 0 ,略过不提。

然后就会对当前类已经计算出的 mro 和直接基类的 mro 进行合并,使用的是 conservation_merge 函数。这个函数的作用是把 parentMRO 分成几段分别插入到当前类的 mro 列表中。算法的流程大概是:

  1. 获取派生类已经计算出了的 mro 中的首个类;

  2. 在基类 mro 列表中寻找派生类 mro 中获取的类;

  3. 如果不存在,获取派生类 mro 列表中的下一个类并返回步骤 2 ,如果已经获取完则到步骤 7 ;

  4. 否则将找到的类设为基类 mro 列表两段之间的分界点;

  5. 从基类 mro 列表中的上一个分界点开始到当前分界点之间的所有类与派生类 mro 列表中的所有类比较去重;

  6. 将去重后的整段插入到派生类 mro 中当前获取类之前的位置并返回步骤 1 ;

  7. 将基类 mro 列表中剩下来的类都插入到派生类 mro 列表的最后,结束。

不过这个算法还是有不尽人意的地方,不然也不会仅仅在一个版本号之后就被弃用了。在 Python 邮件列表中提到一个比较复杂的例子,还有一个更简单的例子可以举:

class A(object): pass
class B(object, A): pass
print B.__mro__

Python 2.2 中的输出是 B A object ,如果按照邮件列表中提到的 monotonic ,也就是单调性要求, 在定义类 B 的时候 object 排在 A 之前,那么在 __mro__ 中也应该保持相同的顺序。(如果觉得 object 太特殊,可以自己再定义一个类直接继承 object ,其它类继承它,结果也是一样的。)

考虑到这些问题,邮件中提到了一个新的解决方法,也就是 C3 线性化算法。于是在 2.3 以后的版本均采用了 C3 作为默认解析算法(仍然保留旧式搜索以向后兼容, Python 3 完全使用 C3 ,抛弃深搜)。

C3 线性化算法

C3 的论文中提到有三个基本规则:(对不起不会翻译)

  • Consistent extended precedence graph;

  • Local precedence order;

  • Monotonicity.

大意是: MRO 列表由继承树构造,其中派生类永远在其对应的基类之前,同级顺序应当和每一个同时派生自它们的类的继承列表相同。

当以上条件无法被满足时, C3 无法进行,停止构造 MRO 。

C3 的构造方法描述如下:定义 head 元素为列表的第一项, tail 为列表中除了 head 剩下的元素。派生类 MRO 列表中一开始只有自身,将所有直接基类的 MRO 依序排好,再在最后放一个直接基类的列表。首先取第一个列表中的 head ,如果它不属于任何列表的 tail ,将其加入 MRO 列表并从其它列表中移除。如果是某个列表的 tail 则继续搜索下一个列表的直到找到一个不属于其它列表 tailhead 。如果一轮循环没能找到,则说明无法线性化,构造失败。

这样重复到所有直接基类的列表为空就构造成功了。在 Python 3.6 中具体的实现在 Objects/typeobject.c 中的 mro_implrmentationpmerge 函数,两个函数加起来有将近 150 行,如果去掉错误处理,配合上面的逻辑其实不难理解,这里也直接贴上来:

static int
pmerge(PyObject *acc, PyObject* to_merge)
{
    int res = 0;
    Py_ssize_t i, j, to_merge_size, empty_cnt;
    int *remain;

    to_merge_size = PyList_GET_SIZE(to_merge);

    /* 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 = (int *)PyMem_MALLOC(SIZEOF_INT*to_merge_size);
    if (remain == NULL) {
        PyErr_NoMemory();
        return -1;
    }
    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_list = PyList_GET_ITEM(to_merge, i);

        if (remain[i] >= PyList_GET_SIZE(cur_list)) {
            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 = PyList_GET_ITEM(cur_list, remain[i]);
        for (j = 0; j < to_merge_size; j++) {
            PyObject *j_lst = PyList_GET_ITEM(to_merge, j);
            if (tail_contains(j_lst, remain[j], candidate))
                goto skip; /* continue outer loop */
        }
        res = PyList_Append(acc, candidate);
        if (res < 0)
            goto out;

        for (j = 0; j < to_merge_size; j++) {
            PyObject *j_lst = PyList_GET_ITEM(to_merge, j);
            if (remain[j] < PyList_GET_SIZE(j_lst) &&
                PyList_GET_ITEM(j_lst, remain[j]) == candidate) {
                remain[j]++;
            }
        }
        goto again;
      skip: ;
    }

    if (empty_cnt != to_merge_size) {
        set_mro_error(to_merge, remain);
        res = -1;
    }

  out:
    PyMem_FREE(remain);

    return res;
}

static PyObject *
mro_implementation(PyTypeObject *type)
{
    PyObject *result = NULL;
    PyObject *bases;
    PyObject *to_merge, *bases_aslist;
    int res;
    Py_ssize_t i, n;

    if (type->tp_dict == NULL) {
        if (PyType_Ready(type) < 0)
            return NULL;
    }

    /* Find a superclass linearization that honors the constraints
       of the explicit lists of bases and the constraints implied by
       each base class.

       to_merge is a list of lists, where each list is a superclass
       linearization implied by a base class.  The last element of
       to_merge is the declared list of bases.
    */

    bases = type->tp_bases;
    n = PyTuple_GET_SIZE(bases);

    to_merge = PyList_New(n+1);
    if (to_merge == NULL)
        return NULL;

    for (i = 0; i < n; i++) {
        PyTypeObject *base;
        PyObject *base_mro_aslist;

        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);
            goto out;
        }

        base_mro_aslist = PySequence_List(base->tp_mro);
        if (base_mro_aslist == NULL)
            goto out;

        PyList_SET_ITEM(to_merge, i, base_mro_aslist);
    }

    bases_aslist = PySequence_List(bases);
    if (bases_aslist == NULL)
        goto out;
    /* This is just a basic sanity check. */
    if (check_duplicates(bases_aslist) < 0) {
        Py_DECREF(bases_aslist);
        goto out;
    }
    PyList_SET_ITEM(to_merge, n, bases_aslist);

    result = Py_BuildValue("[O]", (PyObject *)type);
    if (result == NULL)
        goto out;

    res = pmerge(result, to_merge);
    if (res < 0)
        Py_CLEAR(result);

  out:
    Py_DECREF(to_merge);

    return result;
}

拿上面简单深搜无法处理的情况举例而言:

class A(object): pass
class B(object, A): pass

object 的 MRO 为 [object]A 的 MRO 为 [A, object] ,那么 B 的 MRO 应当为 [B] + merge([object], [A, object], [object, A]) ,第一个合适的 head 就找不到,构造失败,会抛出一个异常。

有一个比较复杂的 Python 2.2 处理错误,但是 C3 可以正确处理的结构,就是邮件列表中提到的:

class A(object): pass
class B(object): pass
class C(object): pass
class D(object): pass
class E(object): pass
class K1(A, B, C): pass
class K2(D, B, E): pass
class K3(D, A): pass
class Z(K1, K2, K3): pass
print(Z.__mro__)

这个在 Python 2.2 的输出顺序应当是 Z K1 K3 A K2 D B C E object ,有明显违背原则的地方有 K3K2 之前, A DK3 中和 Z 中的顺序不一致。

而在 Python 2.3 之后的输出顺序是 Z K1 K2 K3 D A B C E object ,没有问题。

现在默认使用 C3 的常见语言有 Perl 和 Python ,除此以外还有一堆我不认识的。

发表评论

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