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

Опубликовано 12 September 2017 в 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.

Хотя, как я уже говорил, походить по сишному коду может быть интересным занятием, мы воспользуемся коротким путем. Если просмотреть документ "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.

---
Возник вопрос? Мне всегда можно написать в Twitter: avkorablev

Наслаждайся