**Виртуальная машина regex в Python**

Мы уже [говорили](https://t.me/opensource_findings/977) про дополнительные виртуальные машины в CPython. Посмотрели на `pickle`, сегодня настала очередь `re`. Немного не в формате канала, что мы смотрим джуновские штуки, но все равно интересно, может быть какие-то детали будут незнакомы и сениор специалистам.

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

Допустим у нас есть такой паттерн: `re.compile(r'@[a-z&#092;d]&#092;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&#092;&#092;d]&#092;&#092;d{2,}', re.DEBUG)


Все опкоды можно посмотреть тут: [https://github.com/python/cpython/blob/main/Modules/_sre/sre_constants.h](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](https://github.com/python/cpython/blob/e9c9a339035c9b96a5ebca8337a13140725ecf2a/Lib/re/_compiler.py#L34)

Есть куча оптимизаций, кешей, утилит для дебага. Тот же `dis`, вывод которого мы видим при использовании `re.DEBUG` выше. Данная часть довольно чувствительна к перформансу. Буквально сегодня видел свежий баг, когда [ВДРУГ](https://github.com/python/cpython/issues/161125) становится медленнее. 

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

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

Сначала немного интересных фактов:
- Для данной VM в некоторых местах тоже [используются](https://github.com/python/cpython/blob/e9c9a339035c9b96a5ebca8337a13140725ecf2a/Modules/_sre/sre_lib.h#L636) `COMPUTED_GOTO`, если они поддерживаются ([пост](https://t.me/opensource_findings/872) о них)
- Почему-то нет поддержки `_Py_TAIL_CALL_INTERP`, хотя возможно оно тоже дало бы неплохой буст. Очень интересная задачка на подумать. Может кто-то хочет взять и попробовать? ([пост](https://t.me/opensource_findings/892) о нем)
- В Python3.15 произошел глобальный рефакторинг `re` модуля: [удалили](https://github.com/python/cpython/blob/main/Doc/whatsnew/3.15.rst#sre_) модули `sre_compile`, `sre_constants`, `sre_parse`

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


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


Про DSL с `TARGET` и `DISPATCH` я уже [рассказывал](https://t.me/opensource_findings/892) в посте про основную VM в питоне. 
Остальная логика очень простая: если встречаем другой символ, то просто возвращаем `0`, если встречаем нужный - продолжаем. `ptr++` и `pattern++` берут следующий указатель на строку и следующий `pattern` для матча. Таким образом в `DISPATCH` попадет уже следующий опкод. Классика.

Еще интересно глянуть `REPEAT_ONE`, который нам нужен в самом конце. Он довольно большой, я[спрятал его под ссылку](https://github.com/python/cpython/blob/e9c9a339035c9b96a5ebca8337a13140725ecf2a/Modules/_sre/sre_lib.h#L949-L1046). Из интересного там могу выделить оптимизацию под повторение опкода `LITERAL`. Остальное - довольно стандартно. Проверяем размер строки, ее символы внутри.

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

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

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

| [Поддержать](https://boosty.to/sobolevn) | [YouTube](https://youtube.com/@sobolevn) | [GitHub](https://github.com/sobolevn) | [Чат](https://t.me/opensource_findings_chat) |