Python内置的"in"运算符的源代码

Question

我在尝试查找(C)Python源代码中内置的in操作符的实现。我已经在内置函数源代码和bltinmodule.c中搜索过，但是不能找到这个操作符的实现。请问我该在哪里找到这个实现呢？

我的目标是通过扩展不同的C实现来改进Python中的子字符串搜索算法，尽管我不确定Python是否已经使用了我想要的想法。

- Michael

Answer 1

要找到任何Python运算符的实现，首先需要使用dis.dis函数查找Python生成的字节码：

>>> dis.dis("'0' in ()")
  1           0 LOAD_CONST               0 ('0')
              2 LOAD_CONST               1 (())
              4 COMPARE_OP               6 (in)
              6 RETURN_VALUE

“in”运算符成为一个“COMPARE_OP”字节码。现在你可以追踪这个操作码在Python评估循环中的处理方式，具体请参见Python/ceval.c。

TARGET(COMPARE_OP)
    PyObject *right = POP();
    PyObject *left = TOP();
    PyObject *res = cmp_outcome(oparg, left, right);
    Py_DECREF(left);
    Py_DECREF(right);
    SET_TOP(res);
    if (res == NULL)
        goto error;
    PREDICT(POP_JUMP_IF_FALSE);
    PREDICT(POP_JUMP_IF_TRUE);
    DISPATCH();

cmp_outcome()在同一文件中被定义, 而in操作符是其中的一个开关:

case PyCmp_IN:
    res = PySequence_Contains(w, v);
    if (res < 0)
         return NULL;
    break;

快速使用grep命令可以找到PySequence_Contains的定义位置，在Objects/abstract.c文件中：

int
PySequence_Contains(PyObject *seq, PyObject *ob)
{
    Py_ssize_t result;
    PySequenceMethods *sqm = seq->ob_type->tp_as_sequence;
    if (sqm != NULL && sqm->sq_contains != NULL)
        return (*sqm->sq_contains)(seq, ob);
    result = _PySequence_IterSearch(seq, ob, PY_ITERSEARCH_CONTAINS);
    return Py_SAFE_DOWNCAST(result, Py_ssize_t, int);
}

PySequence_Contains会使用Sequence对象结构上的sq_contains插槽或者迭代搜索来处理Python C对象。

对于Python 3 Unicode字符串对象，这个插槽被实现为Objects/unicodeobject.c中的PyUnicode_Contains，在Python 2中，你也可以查看Objects/stringobject.c中的string_contains。基本上只需要在Objects/子目录中使用grep命令搜索sq_contains，就可以找到不同Python类型的各种实现。

对于通用的Python对象，值得注意的是Objects/typeobject.c将其推迟到自定义类上定义了__contains__方法。

- Martijn Pieters

---

@Martijn Pieters：我查看了Python 2.7的字符串包含代码，它使用PyUnicode_Contains，该函数使用stringlib_contains_obj，该函数使用stringlib_find，该函数使用fastsearch仅比较子字符串的第一个字母，这里可能有问题或者我漏掉了什么（并且它没有使用Boyer-Moore算法，就像我想的那样）？ - Michael

@Michael：它没有使用Boyer-Moore算法，而是使用了一种受B-M启发的算法，请参见http://effbot.org/zone/stringlib.htm。它是简化版的B-M算法，加入了一些Horspool和Sunday算法。 - Martijn Pieters

Answer 2

在Python 3.9中，字节码COMPARE_OP被拆分为四个不同的指令，并引入了CONTAINS_OP用于'in'和'not in'测试。

这并没有改变in运算符的实现方式，它仍然直接在Python/ceval.c中处理，调用PySequence_Contains()。

• 文档：https://github.com/python/cpython/blob/main/Doc/whatsnew/3.9.rst#cpython-bytecode-changes
• 相关问题：https://bugs.python.org/issue39156

- ofey404