Хэш-функция для функции в Python

Пару недель назад один из моих коллег задал вопрос: можно ли использовать функцию в качестве ключа словаря? Да, можно. У каждой функции в Python есть хеш. Но как он считается? На основе имени функции? На основе байт‑кода? В действительности хэш считается как трансформация над указателем на объект функции. Тем не менее не так‑то легко отыскать эти расчёты в коде CPython.

Навигация по C‑коду — довольно интересный опыт, хотя делать это совсем непросто: все эти макросы делают простой поиск нужных переходов довольно сложным. Конечно, я уверен, что вы сможете с этим справиться и найти все вызываемые функции при запросе хеша для объекта функции.

Но давайте поступим немного по‑другому. Мы пройдём всего пару вызовов, чтобы понять, как CPython работает, а затем поговорим об устройстве CPython, чтобы не нужно было искать потерянные вызовы в куче макросов.

Я буду использовать master‑ветку официального репозитория CPython. Вы можете его клонировать или исследовать в браузере. Объект функции описан в файле funcobject.c. Наиболее интересная нам часть — вот эта:

PyTypeObject PyFunction_Type = {
    PyVarObject_HEAD_INIT(&PyType_Type, 0)
    "function",
    sizeof(PyFunctionObject),
    0,
    (destructor)func_dealloc,                   /* tp_dealloc */
    0,                                          /* tp_print */
    0,                                          /* tp_getattr */
    0,                                          /* tp_setattr */
    0,                                          /* tp_reserved */
    (reprfunc)func_repr,                     /* tp_repr */
    0,                                          /* tp_as_number */
    0,                                          /* tp_as_sequence */
    0,                                          /* tp_as_mapping */
    0,                                          /* tp_hash */
    function_call,                           /* tp_call */
    0,                                          /* tp_str */
    0,                                          /* tp_getattro */
    0,                                          /* tp_setattro */
    0,                                          /* tp_as_buffer */
    Py_TPFLAGS_DEFAULT | Py_TPFLAGS_HAVE_GC,    /* tp_flags */
    func_new__doc__,                         /* tp_doc */
    (traverseproc)func_traverse,             /* tp_traverse */
    0,                                          /* tp_clear */
    0,                                          /* tp_richcompare */
    offsetof(PyFunctionObject, func_weakreflist), /* tp_weaklistoffset */
    0,                                          /* tp_iter */
    0,                                          /* tp_iternext */
    0,                                          /* tp_methods */
    func_memberlist,                         /* tp_members */
    func_getsetlist,                       /* tp_getset */
    0,                                          /* tp_base */
    0,                                          /* tp_dict */
    func_descr_get,                       /* tp_descr_get */
    0,                                          /* tp_descr_set */
    offsetof(PyFunctionObject, func_dict),    /* tp_dictoffset */
    0,                                          /* tp_init */
    0,                                          /* tp_alloc */
    func_new,                               /* tp_new */
};

Это декларация типа функции. Каждая строка, помеченная комментарием tp_something, — указатель на C‑функцию, которая делает что‑либо специфичное для заданного типа. При этом если указан 0, то это значит, что будет вызываться унаследованная функция. В нашем случае для tp_hash указан именно 0.

Найти функцию, которая будет вызываться по умолчанию, непросто. В файле есть всего одно место, где используется структура PyFunction_Type: она фигурирует в качестве параметра вызова макроса PyObject_GC_New внутри PyFunction_NewWithQualName.

Хотя, как я уже говорил, походить по C‑коду может быть интересным занятием, мы воспользуемся коротким путём. Если просмотреть документ «CPython’s PyTypeObject», то становится более или менее понятно, как организован и как работает PyTypeObject. В этом же документе можно узнать, что функцию по умолчанию для tp_hash нужно искать в PyBaseObject_Type.tp_hash, и что значение по умолчанию равно _Py_HashPointer.

Теперь мы легко найдём нужную нам функцию:

Py_hash_t
_Py_HashPointer(void *p)
{
    Py_hash_t x;
    size_t y = (size_t)p;
    /* bottom 3 or 4 bits are likely to be 0; rotate y by 4 to avoid
       excessive hash collisions for dicts and sets */
    y = (y >> 4) | (y << (8 * SIZEOF_VOID_P - 4));
    x = (Py_hash_t)y;
    if (x == -1)
        x = -2;
    return x;
}

Как видно, никакого полного имени функции не используется. Хэш функции — это всего лишь значение, зависящее от значения указателя на объект функции.

Это было довольно интересное погружение в CPython. Конечно, я использовал «короткий путь». Тем не менее даже он требует некоторых знаний о том, как устроен интерпретатор изнутри. Пожалуй, лучший способ разобраться с этим — посмотреть видео CPython Internals.