Connect OpenTG to ChatGPT or Claude in 60 seconds

Try it

Виртуальная машина regex в Python Мы уже говорили про дополнительные виртуальные машины в CPython.

Находки в опенсорсе

Находки в опенсорсе

@opensource_findings

Привет! Меня зовут Никита Соболев. Я занимаюсь опенсорс разработкой полный рабочий день. Тут я рассказываю про #python, #c, #opensource и тд. Поддержать: https://boosty.to/sobolevn РКН: https://vk.cc/cOzn36 Связь: @sobolev_nikita

12,872 subscribers
Open in Telegram
Виртуальная машина regex в Python

Мы уже говорили про дополнительные виртуальные машины в CPython. Посмотрели на pickle, сегодня настала очередь re. Немного не в формате канала, что мы смотрим джуновские штуки, но все равно интересно, может быть какие-то детали будут незнакомы и сениор специалистам.

Документация: https://docs.python.org/3/library/re.html
Исходник: https://github.com/python/cpython/blob/main/Modules/_sre/sre.c

Допустим у нас есть такой паттерн: re.compile(r'@[a-z\d]\d{2,}').
Начинается с @, далее буква латиницей в нижнем регистре или цифра, далее как минимум две цифры.

И мы можем посмотреть opcod'ы для данного выражения:


LITERAL 64
IN
RANGE (97, 122)
CATEGORY CATEGORY_DIGIT
MAX_REPEAT 2 MAXREPEAT
CATEGORY CATEGORY_DIGIT

0. INFO 8 0b1 4 MAXREPEAT (to 9)
prefix_skip 1
prefix [0x40] ('@')
overlap [0]
9: LITERAL 0x40 ('@')
11. IN 7 (to 19)
13. RANGE 0x61 0x7a ('a'-'z')
16. CATEGORY UNI_DIGIT
18. FAILURE
19: REPEAT_ONE 6 2 MAXREPEAT (to 26)
23. CATEGORY UNI_DIGIT
25. SUCCESS
26: SUCCESS
re.compile('@[a-z\\d]\\d{2,}', re.DEBUG)


Все опкоды можно посмотреть тут: https://github.com/python/cpython/blob/main/Modules/_sre/sre_constants.h

Процесс компиляции

Сам процесс компиляции написан на Python, он довольно понятный: https://github.com/python/cpython/blob/e9c9a339035c9b96a5ebca8337a13140725ecf2a/Lib/re/_compiler.py#L34

Есть куча оптимизаций, кешей, утилит для дебага. Тот же dis, вывод которого мы видим при использовании re.DEBUG выше. Данная часть довольно чувствительна к перформансу. Буквально сегодня видел свежий баг, когда ВДРУГ становится медленнее.

Выполнение опкодов

Раз мы можем скомпилировать инструкции для VM, то мы можем их и выполнить.
Исходники самой VM: https://github.com/python/cpython/blob/main/Modules/_sre/sre_lib.h

Сначала немного интересных фактов:
- Для данной VM в некоторых местах тоже используются COMPUTED_GOTO, если они поддерживаются (пост о них)
- Почему-то нет поддержки _Py_TAIL_CALL_INTERP, хотя возможно оно тоже дало бы неплохой буст. Очень интересная задачка на подумать. Может кто-то хочет взять и попробовать? (пост о нем)
- В Python3.15 произошел глобальный рефакторинг re модуля: удалили модули sre_compile, sre_constants, sre_parse

А вот так выглядят обработчик LITERAL опкодов:


TARGET(SRE_OP_LITERAL):
/* match literal string */
/* <LITERAL> <code> */
TRACE(("|%p|%p|LITERAL %d\n", pattern,
ptr, *pattern));
if (ptr >= end || (SRE_CODE) ptr[0] != pattern[0])
RETURN_FAILURE;
pattern++;
ptr++;
DISPATCH;


Про DSL с TARGET и DISPATCH я уже рассказывал в посте про основную VM в питоне.
Остальная логика очень простая: если встречаем другой символ, то просто возвращаем 0, если встречаем нужный - продолжаем. ptr++ и pattern++ берут следующий указатель на строку и следующий pattern для матча. Таким образом в DISPATCH попадет уже следующий опкод. Классика.

Еще интересно глянуть REPEAT_ONE, который нам нужен в самом конце. Он довольно большой, я спрятал его под ссылку. Из интересного там могу выделить оптимизацию под повторение опкода LITERAL. Остальное - довольно стандартно. Проверяем размер строки, ее символы внутри.

Оказывается, что регулярные выражения - довольно простые и понятные, если смотреть на них как на инструкции для выполнения. А не как на текст. И помните:

> Если у вас есть проблема, и вы решили использовать регулярные выражения, чтобы её решить... Теперь у вас две проблемы

Обсуждение: Любите ли вы писать regex? Поможет ли вам данный пост в дебаге сложных выражений? Есть ли у вас какие-то хитрые оптимизации на уме, которые можно было бы добавить в CPython?

| Поддержать | YouTube | GitHub | Чат |
Open post in Telegram