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

[GoogleCodeExporter]

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

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

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

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

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

Original issue reported on code.google.com by oasyc...@gmail.com on 16 Apr 2015 at 9:46

[GoogleCodeExporter]

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

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

Original comment by eklepilkina@gmail.com on 19 Apr 2015 at 2:42

[GoogleCodeExporter]

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

Original comment by oasyc...@gmail.com on 19 Apr 2015 at 10:45

[GoogleCodeExporter]

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

Original comment by eklepilkina@gmail.com on 26 Apr 2015 at 5:49

[GoogleCodeExporter]

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

Original comment by oasyc...@gmail.com on 26 Apr 2015 at 9:18

[GoogleCodeExporter]

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

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

Original comment by oasyc...@gmail.com on 27 Apr 2015 at 5:49

[GoogleCodeExporter]

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

Original comment by eklepilkina@gmail.com on 27 Apr 2015 at 6:15

[GoogleCodeExporter]

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

Original comment by oasyc...@gmail.com on 27 Apr 2015 at 8:48

[GoogleCodeExporter]

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

Original comment by eklepilkina@gmail.com on 28 Apr 2015 at 6:48

[GoogleCodeExporter]

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

Original comment by eklepilkina@gmail.com on 28 Apr 2015 at 7:21

[GoogleCodeExporter]

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

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

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

Original comment by oasyc...@gmail.com on 28 Apr 2015 at 12:31

[GoogleCodeExporter]

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

Original comment by eklepilkina@gmail.com on 28 Apr 2015 at 4:41

[GoogleCodeExporter]

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

Original comment by oasyc...@gmail.com on 28 Apr 2015 at 4:46

[GoogleCodeExporter]

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

Original comment by eklepilkina@gmail.com on 28 Apr 2015 at 4:54

[GoogleCodeExporter]

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

Original comment by oasyc...@gmail.com on 28 Apr 2015 at 10:16

[GoogleCodeExporter]

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

Original comment by eklepilkina@gmail.com on 29 Apr 2015 at 5:57

[GoogleCodeExporter]

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

Original comment by eklepilkina@gmail.com on 29 Apr 2015 at 2:44

Attachments:

• 2.svg

[GoogleCodeExporter]

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

Original comment by eklepilkina@gmail.com on 29 Apr 2015 at 2:48

[GoogleCodeExporter]

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

Original comment by eklepilkina@gmail.com on 1 May 2015 at 4:49

Attachments:

• fa_merged.svg