Поддержка ассертов при рекурсивных вызовах подмасок

[Oleg Sychev]

Originally reported on Google Code with ID 344

У нас проблемы! Прямо на стыке двух работ: ассертов Лены и рекурсивных вызовов Валеры.
Надо пополнять future_cross_tests и думать.

Для подвыражений типа (\babc\b) часть подвыражения выходит за пределы собственно этой
подвыражения - "ассерт переходы" в данном случае \W. Сейчас это нормально мержится,
но вот при его рекурсивном вызове (который ориентируется на теги) эти выходящие вперед
и назад переходы не сработают. При использовании сложных ассертов внутри рекурсивно
вызываемого подвыражения ситуация будет еще веселее.

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

Первое что приходит на ум - необходимо сохранять в автомате "фантомные" части пересеченных
переходов из ассертов, чтобы они работали при вызове вместо нормальных. Это полностью
снимает проблему для выходящих влево; но не снимает ее для выходящих вправо...

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

Reported by oasychev on 2015-04-16 21:46:59

[Former user]

Проверить захват подвыражений при нерекурсивных вызовах для простых ассертов? Такие
тесты есть. Вот, например, https://code.google.com/r/eklepilkina-preg-intersection/source/browse/question/type/preg/tests/cross_tests_from_preg_merging.php#1648.

Или сложных ассертов?

Reported by eklepilkina on 2015-04-19 14:42:01

[Oleg Sychev]

Там не просто проверить захват подвыражения. Речь идет именно о вызовах подвыражений
- типа (?1) - а вовсе не об их повторении, как в ваших примерах.

Reported by oasychev on 2015-04-19 22:45:30

[Former user]

Добавила пару тестов на вызовы подвыражений со \b. 
https://code.google.com/r/eklepilkina-complex-assertions/source/detail?r=a6210e4440af4926c4d1e3220a629df3d9acfa35
Такое что-то надо было? Добавленные тесты работают правильно.

Reported by eklepilkina on 2015-04-26 17:49:38

[Oleg Sychev]

Да для data_for_test_asserts_subpatterns_2 - это то, что надо. Первый тест этого не
проверяет т.к. там пробел и буква единственный вариант на границе вызова, \b никак
не влияет на его результат ибо он всегда будет границей слова.

Reported by oasychev on 2015-04-26 21:18:07

[Oleg Sychev]

Валерий - два срочных вопроса. Вам эти начальные/конечные состояния по тегам только
для рекурсивных подвыражений нужны или не только? И есть ли у нас сейчас где-то отметки
в дереве и/или карте подвыражений - какие из подвыражений содержат рекурсивные вызовы?

План действий
а) Лена делает два поля - одно для массива начальных и конечных состояний выражения
и подвыражений с точки зрения выполнения, другое - для начальных и конечных состояний
по тегам. По идее их имеет смысл заполнять только для 0-тега и тех, которые рекурсивно
вызываются.
б) Валерий переделывает выполнение как основного автомата, так и подвыражений так,
чтобы они использовали массив настоящих начальных и конечных состояний, а не по тегам
в) массив по тегам остается Лене для корректного пересечения при выходе ассертов за
границы рекурсивно вызываемого подвыражения; больше он вроде ни для чего не нужен.
Если пересекается граница подвыражения по тегу, то к фронту волны должны добавляться
состояния до (после) перехода с рекурсивным вызовом.

Reported by oasychev on 2015-04-27 17:49:56

[Former user]

Я разобралась с тестом на \b и нерекурсивный вызов, который падал. Там состояние, которое
должно быть конечным не определяется как конечное и удаляется.

Reported by eklepilkina on 2015-04-27 18:15:31

[Oleg Sychev]

Значит при фиксинге конечных состояний должен заработать?

Reported by oasychev on 2015-04-27 20:48:06

[Former user]

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

Reported by eklepilkina on 2015-04-28 06:48:08

[Former user]

Написала тесты на ассерты при рекурсии https://code.google.com/r/eklepilkina-complex-assertions/source/detail?r=d55df26bdd9dfcfb30a640afb500efa805554b9a.
\b ожидаемо падает, ^ тоже падает, $ нет, но мне кажется, что это я тест просто неудачный
составила.

Reported by eklepilkina on 2015-04-28 07:21:09

[Oleg Sychev]

Начало того, что нужно сделать вам ясно? (пункт "а").

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

P.S. Валерий, Лена - у нас с вами следующая встреча из-за праздников не удается, а
тут как раз проблемы которые надо обсуждать. Куда переносить будем?

Reported by oasychev on 2015-04-28 12:31:23

[Former user]

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

Reported by eklepilkina on 2015-04-28 16:41:56

[Oleg Sychev]

Я про консультацию через 2 недели - нерабочий день.

Reported by oasychev on 2015-04-28 16:46:35

[Former user]

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

Reported by eklepilkina on 2015-04-28 16:54:28

[Oleg Sychev]

То вы неисправимая пессимистка, то такая же неисправимая оптимистка. У нас меньше двух
месяцев до защиты осталось (т.е. 3-4 встречи всего), и вы предлагаете месяц без встреч
провести? Со всем справитесь, и с подготовкой доклада и с кодом?

Reported by oasychev on 2015-04-28 22:16:14

[Former user]

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

Reported by eklepilkina on 2015-04-29 05:57:49

[Former user]

Я сейчас на примере посмотрела и я не пойму зачем 2 массива, зачем мне массив по тегам?
Этот массив заполняется уже после построения автомата, а менять начальные/конечные
для вызываемых подвыражений мне надо в момент построения, иначе там все смержится/пересечется.
Вот на примере ^ , на рисунке автомат который строится. В момент, когда строится subexpression
call , я записываю в массив под индексом подвыражения этот переход.
Потом достраивается ^, у который есть tag->subpattern равный подвыражению, и т.к. имеется
рекурсивный вызов этого подвыражения, будет добавлен переход 18->6 с ^, а потом к нему
будут скопированы переходы до subexpression call(тут [e\n]) и смержены, в итоге получится
переход 19->6 [e\n] & \n ^. И 19 я запишу в массив начальных состояний. Зачем мне массив
по тегам потом? он записывает в качестве начального состояния для подвыражения 2. В
любом случае для пересечения мне нужны будут переходы, которые стоят до после subexpression
call, а на них этот массив меня не выведет.

Reported by eklepilkina on 2015-04-29 14:44:27

<hr> * Attachment: 2.svg

[Former user]

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

Reported by eklepilkina on 2015-04-29 14:48:42

[Former user]

Я сделала второй массив и перевела работу на него. От Валеры ничего не надо, там у него
используются функции получения начальных и конечных состояний и все вроде, я их поправила.
И проверила на кросс-тестах до правок и после, ничего не упало после правок. Единственное,
в дальнейшем будет проблема с удалением тупиковых состояний, т.к. изначально я удаляла
старую границу при изменении переходов, но при мержинге возникли проблемы, потому что
это состояние может и не оказаться тупиковым и не будет удалено, а должно остаться
границей. Пример на картинке, смерженный eps вел в 19, после мержинга как граница 1
подвыражения добавляется 20, но 19 удалиться не должно. Из-за того, что так происходит
в других случаях, у меня в границах могут остаться тупиковые вершины. Поэтому когда
происходит удаление тупиковых нельзя опираться на эти границы, когда появятся хвосты.
Придется хвостовые состояния как-то отмечать, чтобы не удалить их.

Reported by eklepilkina on 2015-05-01 16:49:25

<hr> * Attachment: fa_merged.svg