— видимость лямбды ограничена функцией `matcher_accept`
— в коде не хватает проверок на `#ifdef NEXT_OP ...`

Не, я не спорю, макросы иногда очень выручают, но данный код был бы гораздо лучше без них. Тем более отказавшись от них, код, как мне кажется, стал бы чуть более безопасным и выразительным.

VlK Dec 17 2018 at 15:59

Ну, сложно сказать. Привычку для таких операций я приобрел, читая код популярных интепретаторов вроде Питона :-) Вот ifdef-ы я точно бы не стал здесь вносить, их совсем тяжело бывает читать.

Наверное, в плюсах я бы подумал над лямбда-функциями, но… Просто маленькие функции, которые легко заинлайнятся, тут сработали бы даже лучше.

potan Dec 14 2018 at 14:05

Чем это отличается от конечного автомата?

VlK Dec 14 2018 at 14:17

Ничем :-)

Это сериализованный в байт-код недетерменированный конечный автомат. «Недетерминированность» здесь означает именно тот факт, что автомат может одновременно несколькими путям, эм, идти.

qw1 Dec 14 2018 at 20:32

Чисто теоретически, можно подобрать такое регулярное выражение, и такой вход, что каждый поток будет форкаться на каждом шаге, т.е. кол-во потоков будет удваиваться. Тогда программа либо упадёт из-за исчерпания лимита потоков, либо будет сильно тормозить, если лимит потоков довольно большой, а входная строка специально удерживает кол-во работающих потоков почти на пределе.

VlK Dec 14 2018 at 21:11

Вопрос хороший, да. :-)

В практической реализации при добавлении потоков инструкцией SPLIT или любым другим способом мы будем проверять, нет ли уже потока с данной инструкцией. Добавлять новый не имеет смысла — у него то же самое состояние (единственный указатель на текущую инструкцию).

То есть при длине сессии N и длине байт-кода M мы будем иметь максимум M потоков. Для целой сессии мы максимум O(N*M) раз побеспокоим наши потоки.

qw1 Dec 14 2018 at 22:18

Интересное решение. К сожалению, оно не работает, если в регулярном выражении есть группы и после окончания сопоставления нужно будет также вернуть позицию каждой группы в строке.

VlK Dec 15 2018 at 14:47

в моей задаче был нужен сам факт достижения определенной точки регулярного выражения плюс, возможно, счетчик числа достижений, поиск групп там был скорее теоретической возможностью.

Однако, если, допустим, добавить инструкции SAVE, сохраняющие массив, почему вдруг мы не можем извлечь подгруппы..?

qw1 Dec 15 2018 at 17:10

Потому что сейчас у каждого потока в контексте есть только текущий Instruction Pointer, а если делать с группами, то форк, который делает поток на уже существующий Instruction Pointer, должен иметь свои данные, и сжать два потока в один будет нельзя.

VlK Dec 17 2018 at 11:14

Вы не против, если я подумаю вслух?

У потока, строго говоря, три значения в контексте: instruction pointer, текущее событие, массив подгрупп. На каждом шаге обработки потоков текущее событие будет одинаково. Различаются IP и массивы подгрупп.

Пускай у нас регулярное выражение вида "(a*)b", которое соответствует байт-коду

SAVE 1
splitlabel:
SPLIT label1 label2
label1:
NEXT
EVENT a
JUMP splitlabel
label2:
SAVE 2
NEXT
EVENT b
MATCH

Предположим, мы матчим строку aab. На втором шаге у нас будет два потока, один из которых уже сматчил первое событие a. Надо добавить второй поток, у котрого тот же IP и будет то же текущее событие. Разница в том, что первый поток уже сохранил историю в виде SAVE 1. Дальше они будут работать одинаково.

То есть у потоков разная история, но одинаковое будущее. Выходит, что мы
, к примеру, можем решить, какая история потоков нас будет интересовать. Например, более длинная группа будет выигрывать.

Я согласен с вами в том смысле, что тут масса тонкостей, но по крайней мере часть из вопросов решить можно.

qw1 Dec 17 2018 at 13:12

Тут есть над чем подумать. Я полагал, что недетерминированные автоматы всегда будут иметь экспоненциальные затраты памяти, но оказывается, что не всегда. Вопрос только, это частный случай или любой автомат можно так оптимизировать.

VlK Dec 17 2018 at 13:37

Я вот честно скажу, что тут надо смотреть детали, и этот прототип скорее сделан для проверки идеи.

В простом случае, который я с самого начала указал (нет подгрупп, просто не больше одного потока на каждый конкретный IP), такой недетерминированный автомат соответствует конечному, и это легко показать: пускай каждое состояние недетерминированного автомата в виде распределения потоков по разным IP соответствует одному состоянию конечного автомата. Обозначим его числом 1.Каждое следующее событие будет как-то менять распределение событий, и будет это делать предсказуемым способом. То есть мы можем и это новое состояние тоже поставить в соответствие одному распределению потоков, и обозначить числом. И т.д.

Словом, это один из стандартных методов построения DFA из NFA.

А вот если мы хотим и группы сохранить, и еще всякую логику выбора интересных нам историй прикрутить, то, конечно, DFA не будет, но вот прям страстей по потреблению памяти можно попробовать избежать.

А вы интересуетесь темой?

qw1 Dec 17 2018 at 16:57

Я интересуюсь алгоритмами поиска (автоматы, суффиксные деревья).

Стандартный способ построения DFA из NFA — это каждому множеству состояний NFA сопоставить одно состояние нового DFA. В общем случае, если у NFA n состояний, то у DFA их будет 2^n (кол-во подмножеств множества 1..n) и потребление памяти на хранение номера состояния будет расти экспоненциально.

Если в лоб сконвертировать NFA, получится DFA с большим кол-вом состояний и переходов, которые в явном виде хранить будет тяжко. А тут выходит какая-то хитрость, что состояние DFA не является классическим числом, а размазано по нескольким переменным (списку потоков), и это позволяет уменьшить накладные расходы. Этот подход интересно изучить подробнее, всегда ли можно его применять.

VlK Dec 17 2018 at 17:37

Стандартных способов несколько.

В данном случае, опять же если не обсуждать вопрос групп и других вещей, которые очень легко делать именно на NFA, то это называется «создание DFA на лету». Т.е. мы в каком-то смысле можем закешировать те состояния, при не обязательно сразу строить весь автомат.

Если кеш — пара ключ-значение, то ключом будет пара из состояния списка потоков и входного события, а значением — следующее состояние списка потоков. Если пронумеровать состояния списка потока, и построить эти состояния для всех корректных входных событий, то получим DFA в кеше.

Профит — не обязательно строить полный DFA, можно просто частично его генерировать по мере необходимости.

Но лично меня интересует не DFA, а возможность слегка облегчить страдания NFA, на которую мы тут с вами обратили внимание.

Вообще, вот здесь очень много об этом и не только: swtch.com/~rsc/regexp

Обратите внимание на пункт «Caching the NFA to build a DFA» в первой части статьи.

VlK Dec 14 2018 at 21:11

Кроме того, мы ж в данном случае контролируем компилятор, то есть генерация адекватного байт-кода — наша ответственность.

qw1 Dec 14 2018 at 22:21

Тут ничего не сделаешь, это проблема самого принципа.
Например, регулярное выражение (a|a|a)* и входная строка aaaaaaaaaaa… будут утраивать число потоков на каждом шаге.

VlK Dec 15 2018 at 15:16

Конкретно в данном случае регулярное выражение можно сжать на этапе преобразования дерева.

Опять же, предложенная оптимизация здесь будет работать, нет?

qw1 Dec 15 2018 at 17:11

Сжатия — это эвристики, которые всегда можно обмануть. Например, если удаляются одинаковые под-выражения, то (a|a*)* уже не сожмёшь, потому что формально подвыражения неодинаковые.

VlK Dec 17 2018 at 11:18

Эт точно.

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

Но все равно будет какая-нибудь засада, да. В нашей системе все устроено так, что обработка регулярки происходит в процессе-воркере, у которого есть четкие ограничения на ресурсы. При превышении потребления ресурсов процесс будет убит, система же в целом продложит работу.