Поддержка ассертов границы слова (\b \B)

[Oleg Sychev]

Originally reported on Google Code with ID 232

Обсуждение лучше вести в отдельной задаче.

eklepilkina:
Возникли вопросы по поводу мержинга \b. С раскрытием понятно, а вот как избавляться
от полученных \w и \W. Ведь они захватывают символы. Мне нарисовали, как должно быть
в регулярном выражении, но там смотрящие в разные стороны ассерты. Я не представляю,
как это представляется в автомате.



Лена - мержинг \b и \B подчиняется тем же законам, что и мержинг сложных ассертов,
с которого вы начали на НКПО. Т.е. переходы пересекаются, если не с чем пересекать
в основном автомате - образуют дополнительные "ассертные" переходы, специально помеченные.
Разница в том, что здесь для добавляемого автомата (раскрытого \b) пересечение начинается
не с начала и не с конца, а с середины; причем это 4 узла сразу - зато влево и вправо
от каждого из этих узлов ведет ровно по одной дуге. Поэтому алгоритм мержинга лучше
построить отдельный; по смыслу же он ничем ни отличается от пересечения автоматов для
мержинга сложных ассертов. Такие же пересечения дуг из разных автоматов с теми же последствиями.

Reported by oasychev on 2013-10-03 13:06:04

[Former user]

Все равно остались вопросы.
1. Первый автомат для пересечения - это автомат с полученной развилкой в 4 узла вместо
\b, а второй какой? По тому какое регулярное выражение должно получаться по идее должны
пересекаться части автомата, полученные от развертывания и существовавшие раннее в
разные стороны. Так должно получаться на совсем простых автоматах как на картинках?
2. \B оно же разворачиваться должно по другому. Что-то \w-\w и \W-\W.

Reported by eklepilkina on 2013-10-03 14:54:16

<hr> * Attachment: b.png<br> * Attachment: bResult.png<br> * Attachment: ex.png<br> * Attachment: exResult.png<br>

[Oleg Sychev]

Первым автоматом для пересечения (основным) является сам регекс, у которого "закорочена"
связь с \b - полученный при удалении этой связи узел является точкой начала пересечения
- т.е. на рисунках b.png и ex.png это слитые вместе вершины 1 и 2. А вторым является
автомат с развилкой в 4 узла, причем именно эти 4 узла совмещаются с тем слитым узлом
из первого автомата.

На рисунках результаты примерно правильны, но переходы ^\t ^c и $a можно обрывать,
т.к. шансов на совпадение они не имеют - ведь ^ мержится назад, а $ - вперед.  ^ и
$ в \b работают реально тогда, когда регекс им начинается или заканчивается. ex.png
вообще не имеет шансов на совпадение, ибо какая такая граница слова возможна между
двумя буквами?

Кстати, поскольку \n это вариант \W то вместо ^\w можно использовать \A\w, перевод
строки пройдет по ветке \W\w. Аналогично с $, который можно заменить на самую строгую
версию \z.

\B это отрицание \b и тоже разворачивается на четыре альтернативы - \w\w \W\W ^\W и
\W$

Reported by oasychev on 2013-10-03 15:05:56

[Oleg Sychev]

Проверил ваши тесты на \b - стало лучше, но есть еще проблемы и ошибки - можете в понедельник
забрать, у меня лаба в 902 до 15 часов; если есть возможность подойти часов в 17...17-30
стоило бы поговорить о проблемах при слиянии ассертов начала и конца строки, я хочу
сесть с вами и помочь кросс-тесты на них сделать...

Reported by oasychev on 2013-11-08 14:48:15

[Former user]

Олег Александрович, возник при переводе тестов в вид кросс-тестов вопрос, касающихся
подобных автоматов. В них получается первый переход \w незахватывающий и он как бы
должен дать совпадение на строке a\tcat. Но что там должно генерироваться, просто Валера
говорит, что он с подобными переходами не работал, и что там должно получаться не знает.

Reported by eklepilkina on 2014-04-21 18:10:29

<hr> * Attachment: s.png<br> * Attachment: s1.png<br>

[Oleg Sychev]

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

Такие переходы описаны в issue #114 - посмотрите сами его/связанный код. Если сами
не поймете, Валерию это issue точно должно напомнить о чем речь. Больше года назад
я про эти переходы уже ему говорил.

Reported by oasychev on 2014-04-21 20:14:46

[Former user]

Какие сейчас проблемы с \b.

Reported by eklepilkina on 2014-11-16 11:38:16

<hr> * Attachment: b

[Oleg Sychev]

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

Reported by oasychev on 2014-11-16 14:00:17

[Former user]

Вообщем возникла такая проблема с циклами. Допустим в этом регексе ([a!]\b)+, в конечное
состояние должны вести 3 незахватывающих перехода \W, \w и $. Для этого при построении
цикла эти переходы не должны удаляться, а в регексе ([a!]\b)+с их быть не должно, т.е.
их надо удалить. В процессе построения автомата не понятно, является цикл последним
или нет. Аналогичная ситуация будет с начальным состоянием.

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

Reported by eklepilkina on 2014-11-29 13:56:23

[Oleg Sychev]

Лена, вы похоже где-то сильно не так понимаете. По логике постепенного построения когда
вы строите "([a!]\b)+" у вас остаются в конце незахватывающие переходы. Потом когда
вы при построении "([a!]\b)+с" делаете конкатенацию с "с" у вас эти три перехода пересекаются
с "с", в результате чего остается только один и теперь уже захватывающий.

При этом все логично и естественно получается.

Reported by oasychev on 2014-11-29 16:02:17

[Former user]

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

Reported by eklepilkina on 2014-11-29 16:59:30

[Oleg Sychev]

Тогда давайте краткий словесный алгоритм генерации для ассерт-перехода в конце цикла.
Считаем что внутрицикловая конкатенация уже сгенерирована и из нее торчат вправо три
незахватывающих перехода. Теперь вы генерируете цикл для +.

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

Распишите подробно ваш алгоритм действий для этого момента, почему там у вас что-то
повторно пересекается?

Reported by oasychev on 2014-11-29 18:17:09

[Oleg Sychev]

Если описать долго, сделайте описание к встрече в среду; а сейчас отлаживайте те случаи
с ^ $ и эпсами которые еще не работают

Reported by oasychev on 2014-12-01 23:38:03

[Former user]

А у нас консультация завтра или через 2 недели?

Reported by eklepilkina on 2014-12-02 10:03:50

[Oleg Sychev]

Завтра, она по второй неделе.

Reported by oasychev on 2014-12-02 10:32:38

[Valeriy Streltsov]

fa_matcher failed on regex '([a!?]|)\b([c+]|)' and string 'c' (qtype_preg_cross_tests_from_preg_merging,
data_for_test_assertions_wordboundary_20):
INDEX_FIRST:     0=>1, 1=>0, 2=>1, 
LENGTH:          0=>0, 1=>0, 2=>0, 
expected:
INDEX_FIRST:     0=>0, 1=>0, 2=>0, 
LENGTH:          0=>1, 1=>0, 2=>1, 

Reported by vostreltsov on 2015-01-01 19:19:26

<hr> * Attachment: fa_unmerged.svg * Attachment: fa_merged.svg

[Oleg Sychev]

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

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

Reported by oasychev on 2015-01-01 23:45:19

[Former user]

Почему много? Там просто все проходимые варианты, там 2 развилки, причем в обоих случаях
там символьные классы. Причем из-за пустот в альтернативе, все переходы в развилке
для \b тоже уходят в альтернативу. Там нет ничего лишнего.

Ну в этом пути нет 4 тега открывающегося, я не знаю в этом причина или нет. Я посмотрю,
куда делся тег.

Reported by eklepilkina on 2015-01-02 06:17:22

[Former user]

У меня кстати этого фейла нет, но я поправила насчет 4 тега.

Reported by eklepilkina on 2015-01-02 11:59:18

[Oleg Sychev]

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

Reported by oasychev on 2015-01-02 16:20:55

[Former user]

Просто явно остались тесты, где падает из-за захвата в длину переходов незахватывающих.
Типо таких.
fa_matcher failed on regex '([a!?]|)\b([c+]|)' and string 'a ' (qtype_preg_cross_tests_from_preg_merging,
data_for_test_assertions_wordboundary_20):
LENGTH:          0=>1, 1=>1, 2=>1, 
expected:
LENGTH:          0=>1, 1=>1, 2=>0, 

 А так по остальным тестам (я Вам писала в другом issue), я особо не знаю, где проблемы.

Reported by eklepilkina on 2015-01-02 17:19:59

[Oleg Sychev]

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

Reported by oasychev on 2015-01-02 18:54:16

[Valeriy Streltsov]

Лен, судя по всему проблема в переходе 12-7. Там теги 7 и 5 соответствуют пустоте и
второму подвыражению соответственно, они ведь должны быть в смёрженном переходе.

Reported by vostreltsov on 2015-01-02 20:32:59

[Former user]

Я не могу понять, почему фейлится следующий тест.
fa_matcher failed on regex '([a!]\b)+' and string '!a!a' (qtype_preg_cross_tests_from_preg_merging,
data_for_test_assertions_wordboundary_42):
INDEX_FIRST:     0=>0, 1=>2, 
LENGTH:          0=>3, 1=>1, 
expected:
INDEX_FIRST:     0=>0, 1=>3, 
LENGTH:          0=>4, 1=>1, 

Результирующий и начальный автомат на картинках. В смерженном есть путь для !a!a -
это 0->6->5->6->7->4. Но он почему-то по нему не идет. С тегами тоже все вроде также
как на исходном.

Reported by eklepilkina on 2015-01-22 07:38:37

<hr> * Attachment: t3.png<br> * Attachment: t4.png<br>

[Former user]

Вот тут тоже не знаю, что не так с тегами. В первом случае путь 0->13->7. Во втором
- 0->12->7
fa_matcher failed on regex '([a!?]|)\b([c+]|)' and string ' c' (qtype_preg_cross_tests_from_preg_merging,
data_for_test_assertions_wordboundary_20):
INDEX_FIRST:     0=>1, 1=>0, 2=>1,
expected:
INDEX_FIRST:     0=>1, 1=>1, 2=>1,

fa_matcher failed on regex '([a!?]|)\b([c+]|)' and string 'b ' (qtype_preg_cross_tests_from_preg_merging,
data_for_test_assertions_wordboundary_20):
INDEX_FIRST:     0=>1, 1=>0, 2=>1,
expected:
INDEX_FIRST:     0=>0, 1=>0, 2=>0,

Reported by eklepilkina on 2015-01-22 10:29:58

<hr> * Attachment: t2.png<br>

[Former user]

Короче, я не знаю, что не так в этих случаях, и тех, что из другого issue. Мне нужно,
чтобы Вы посмотрели и сказали, что не так. Остальное работает.

Reported by eklepilkina on 2015-01-24 11:21:32

[Former user]

То, что сегодня записывала, все относится к разным issue, но пока все здесь:
1. Выбор пути при незахватывающем переходе проходит неправильно.
2. Пустота  при пересечении незахватывающих должна уходить в mergedafter, иначе в before
3. При мержинге закрывающиеся теги в ^ и пустые все переносятся после ^, $ - открывающиеся
теги и пустые до.

Reported by eklepilkina on 2015-02-11 18:27:08

[Oleg Sychev]

2 - она точно в незахватывающих? Или дело зависит от того, в каком направлении она мержится?

Reported by oasychev on 2015-02-11 20:37:25

[Valeriy Streltsov]

Пофиксил wb20 и wb42

Reported by vostreltsov on 2015-02-12 14:44:23

[Former user]

Те фейлы в 20, которые на этой неделе я поправила, но там выявились, новые.
fa_matcher failed on regex '([a!?]|)\b([c+]|)' and string ' a' (qtype_preg_cross_tests_from_preg_merging,
data_for_test_assertions_wordboundary_20):
INDEX_FIRST:     0=>1, 1=>1, 2=>1, 
LENGTH:          0=>0, 1=>0, 2=>0, 
expected:
INDEX_FIRST:     0=>1, 1=>1, 2=>2, 
LENGTH:          0=>1, 1=>1, 2=>0, 
Судя по фейлу, матчится путь полностью незахватывающий, почему так не могу понять.
А второй фейл
fa_matcher failed on regex '([a!?]|)\b([c+]|)' and string 'b+' (qtype_preg_cross_tests_from_preg_merging,
data_for_test_assertions_wordboundary_20):
INDEX_FIRST:     0=>1, 1=>1, 2=>1, 
LENGTH:          0=>1, 1=>0, 2=>1, 
expected:
INDEX_FIRST:     0=>0, 1=>0, 2=>0, 
LENGTH:          0=>0, 1=>0, 2=>0, 
Во втором подвыражении захватывается +, я не очень понимаю, почему там должна быть
пустота.

Reported by eklepilkina on 2015-02-14 18:13:13

<hr> * Attachment: fa.svg

[Valeriy Streltsov]

Это тоже fixed?

Reported by vostreltsov on 2015-03-07 20:24:23

[Oleg Sychev]

Всех поздравляю, спасибо!

Reported by oasychev on 2015-03-09 02:05:22 - Status changed: Done