Полностью корректная поддержка ассертов начала/конца строки

[Oleg Sychev]

Originally reported on Google Code with ID 188

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

Предлагаю закрыть этот вопрос сейчас - сложного там ничего нет, нужно только ветки
внимательно выписать...
Что необходимо сделать:
1) добавить поддержку модификаторов m и D, управляющих работой этих ассертов;
2) улучшить (и переименовать?) look_for_circumflex в классе хэндлера, чтобы она (в
зависимости от ассертов и модификаторов) возвращала два флага - якорение относительно
начала строки (пока в true если вообще заякорен чтобы код работал; можно изменить на
только начало) и якорение относительно перевода строки. Функция теперь должна записывать
данные в поле (объект специального класса), а не возвращать их - см. комментарии около
вызова и сам класс.
3) проверить работу ассертов по описанию и добавить поддержку модификаторов в класс
листа-ассерта

Reported by oasychev on 2013-04-06 06:24:11

[Valeriy Streltsov]

Предлагаю все-таки не считать .* якорением. Во-первых, оно зависит от подаваемой строки.
Во-вторых, можно писать сколь угодно вложенное ((((.))))* и подобные вещи, которые
трудно проверять. Из-за этого сейчас есть 6 фейлов из PCRE.

Reported by vostreltsov on 2013-04-06 09:28:33

[Valeriy Streltsov]

Еще есть трудность с $. В режиме multiline он захватывает (!) символ CR, но длина совпадения
при этом не увеличивается. Нужно менять интерфейс match() узлов.

Reported by vostreltsov on 2013-04-06 10:03:09

[Oleg Sychev]

Насчет .* не понял, в чем проблема. Обычное якорение до перевода строки. Если какие-то
более сложные вещи не замечаются, то это на правильность ответа не влияет - только
на производительность. 

Какие тесты из-за этого фейлятся то?

Reported by oasychev on 2013-04-06 17:21:59

[Oleg Sychev]

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

Проблема \n не совсем уж праздная - я подумываю сделать возможность многострочных ответов
с textarea для ввода студенту.

Reported by oasychev on 2013-04-06 17:34:30

[Oleg Sychev]

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

Может проигнорировать этот момент?

Reported by oasychev on 2013-04-06 17:51:51

[Valeriy Streltsov]

3: после изменения якорения появилось несколько такого рода фейлов:
nfa_matcher failed on regex '(.*)\d+\1' and string 'abc123bc' (qtype_preg_cross_tests_from_pcre,
data_for_test_any_character_in_quantifier_in_subexpression_and_digit_in_quantifier_and_back_reference)
FULL:        FALSE
expected:
FULL:        TRUE

nfa_matcher failed on regex '(.*)\d+\1' and string 'abc123bc' (qtype_preg_cross_tests_from_pcre,
data_for_test_any_character_in_quantifier_in_subexpression_and_digit_in_quantifier_and_back_reference)
INDEX_FIRST: 0=>0, 1=>0, 
expected:
INDEX_FIRST: 0=>1, 1=>1, 

nfa_matcher failed on regex '(.*)\d+\1' and string 'abc123bc' (qtype_preg_cross_tests_from_pcre,
data_for_test_any_character_in_quantifier_in_subexpression_and_digit_in_quantifier_and_back_reference)
LENGTH:      0=>1, 1=>1, 
expected:
LENGTH:      0=>7, 1=>2, 

В принципе ситуация довольно жизненная, не такая уж и редкая.

4,5: ваша точка зрения тоже верна; нужно договориться, какова длина совпадения "^abc$"
vs "abc\nd" - 3 или 4? Если 4, то всё хорошо, но тогда consumes() становится априори
неизвестным (хотя поскольку он нужен только при генерации, можно считать его нулевым).

Reported by vostreltsov on 2013-04-06 18:03:38

[Oleg Sychev]

По .* я думаю, вопрос в критериях, при которых оно включается в якорение. Чем более
точные критерии - тем лучше. От более слабых к сильным: наличие обратных ссылок, расположение
.* внутри подвыражения, наличие обратной ссылки именно на то подвыражение, в котором
находится начинающая .*

По $ - я думаю, длина будет 4. Потому что представьте на той же строке выражение "^abc$d".
По изложенным выше правилам в PCRE оно должно совпасть, но иметь длину 4. Мы сильно
заморочимся даже по структуре данных при возврате такого безобразия, указывая какие
конкретно символы выпали из совпадения, или еще не знаю как - в общем случае долларов
может быть несколько или под квантификатором. А никакого особого смысла в этом я найти
не могу, можно только очень хитрый абстрактный тест составить, чтобы другая альтернатива
выиграла по длине, но в такие проблемы ради нее входить глупо...

Reported by oasychev on 2013-04-06 18:45:27

[Oleg Sychev]

Вот перечисление ситуаций, где .* не может приводить к якорению из pcre.txt
However, there are some cases where the optimization  cannot  be  used.
       When .*  is inside capturing parentheses that are the subject of a back
       reference elsewhere in the pattern, a match at the start may fail where
       a later one succeeds. Consider, for example:

         (.*)abc\1

       If  the subject is "xyz123abc123" the match point is the fourth charac-
       ter. For this reason, such a pattern is not implicitly anchored.

       Another case where implicit anchoring is not applied is when the  lead-
       ing  .* is inside an atomic group. Once again, a match at the start may
       fail where a later one succeeds. Consider this pattern:

         (?>.*?a)b

       It matches "ab" in the subject "aab". The use of the backtracking  con-
       trol verbs (*PRUNE) and (*SKIP) also disable this optimization.

Reported by oasychev on 2013-04-13 17:30:33

[Oleg Sychev]

Совпадение с началом строки в PCRE и POSIX

The following table
       lists the different possibilities for matching  newline  characters  in
       PCRE:

                                 Default   Change with

         . matches newline          no     PCRE_DOTALL
         newline matches [^a]       yes    not changeable
         $ matches \n at end        yes    PCRE_DOLLARENDONLY
         $ matches \n in middle     no     PCRE_MULTILINE
         ^ matches \n in middle     no     PCRE_MULTILINE

       This is the equivalent table for POSIX:

                                 Default   Change with

         . matches newline          yes    REG_NEWLINE
         newline matches [^a]       yes    REG_NEWLINE
         $ matches \n at end        no     REG_NEWLINE
         $ matches \n in middle     no     REG_NEWLINE
         ^ matches \n in middle     no     REG_NEWLINE

Reported by oasychev on 2013-05-04 09:14:39

[Oleg Sychev]

m и D следует обсуждать здесь.

Валерий, опять вы пытаетесь ввести поля в узлах там, где этого не требуется. Я же писал
вам, что здесь - как и в случае с точкой - вполне можно обойтись лексером. Например
^ в отсутствии m ведет себя как \A - почему не сгенерировать лексером вместо нее узел
\A (c userinscription ^) - если m не установлена, а если установлена - генерировать
узел ^ ?
Аналогично можно отработать $, \Z и \z - в соответствии с опциями m и D.

И еще вопрос - я давно точу зубы на switch'и в листьях-ассертах. Может уже сделать
дочерние классы вместо них?

Reported by oasychev on 2013-05-05 12:36:07

[Valeriy Streltsov]

На счет m и D не очень уверен. Листья простых ассертов очень редко встречаются, и экономия
получится очень незначительной. Но за то с userinscription будут проблемы:
а) в инструментах авторинга описание из lang берется по значению subtype, так что узел
может и будет отрисован нормально, но его тултип будет кривым;
б) ошибки акцептинга аналогично берутся по subtype, так что тоже могут быть проблемы.

Reported by vostreltsov on 2013-05-05 17:44:15

[Oleg Sychev]

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

А инструменты авторинга могут изменить узлы при генерации своих dst-узлов.

Reported by oasychev on 2013-05-06 06:13:45

[Oleg Sychev]

Теперь бы по-хорошему надо избавиться от switch в ассертах, выделив дочерние классы,
и заняться генерацией следующего символа для всего, кроме \b и \B. (Они - отдельная
тема, но и им этот код понадобится...)

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

Например ^ в обычном режиме должна спросить, были ли уже сгенерированные символы в
строке, и в зависимости от этого вернуть пустую строку или признак невозможности генерации.


В мультистрочном режиме она еще может сгенерировать \n - вот здесь все интереснее,
т.к. многое зависит от того, способен ли следующий переход эту \n съесть. Первое мое
мнение - она должна (если сгенерированные символы есть) вернуть этот \n - а алгоритм
генерации должен учесть, что длина съедаемых у ассерта 0, так что он \n в строку добавляет,
а позицию генерации оставляет прежней. Тогда при генерации следующего символа делаем
пересечение того, что за позицией генерации (\n) и того, что сгенерировал следующий
узел - если оно пустое, то возвращаем невозможность сгенерировать, иначе - пересечение...
Мне кажется, такая адаптация позволит решить эту проблему довольно модульно - но потребует
исправления алгоритма генерации...

Reported by oasychev on 2013-05-14 16:02:14

[Oleg Sychev]

И надо глянуть на тесты - сдается мне, их набор для хорошего тестирования генерации
будет недостаточным. Так что начать можно с рефакторинга и составления набора тестов
на генерацию (с учетом наличия и отсутствия мультистрочного режима).

Reported by oasychev on 2013-05-14 16:13:34

[Oleg Sychev]

Reported by oasychev on 2013-09-05 17:19:11

[Oleg Sychev]

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

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

Вам необходимо начать с разработки тестов на функции совпадения и генерации символа
с учетом ассертов: узлов-ассертов, и узлов-чарсетов в которых заполнено merged assertions.
Когда определитесь с алгоритмами этих функций, поймете - куда надо мержить ассерты:
возможно, что связанные с началом строки ассерты должны мержиться назад и проверяться
после символа, а с концом - вперед. Определяющим фактором служит достаточность данных
для генерации символа или определения невозможности таковой.

Потом необходимо реализовать эти функции для листьев и возможно поправить мержинг этих
ассертов с учетом изменений.

Reported by oasychev on 2013-09-06 13:17:55

[Valeriy Streltsov]

Ассерты отрефакторил, константы добавил в qtype_preg_leaf.

Reported by vostreltsov on 2013-09-06 14:38:34

[Oleg Sychev]

Валерий, если изменить сами строки в константах, то можно сделать еще короче (я думаю
аналогично можно и от массива юникод-свойств в лексере избавиться, он вообще сам себя
дублирует). Можно было также $classname вместо $subtype передавать.

Только почему у нас \Z и \z приводят к одному узлу?  Они несколько разные...
         \A     matches at the start of the subject
         \Z     matches at the end of the subject
                 also matches before a newline at the end of the subject
         \z     matches only at the end of the subject
         \G     matches at the first matching position in the subject
Я так понимаю, надо добавить класс типа esc_bigz и поправить лексер соответственно...

И еще почему не отрефакторена tohr?

Reported by oasychev on 2013-09-06 17:20:52

[Former user]

Моменты, которые я не понимаю.
1. У меня был переход 0->1[label=ab] и следующий 1->2[label=^]. Нужно перед крышкой
сгенерировать \n, но он же захватывающий и тогда в автомате должно быть так 0->1[label=ab]
и следующий 1->2[label=\n^]?
2. Как смерженные ассерты могут влиять на генерацию следущего символа в next_character?
3. Какие символы должны генерировать ассерты, если \n, то почему next_character ведь
^ генерировать должна \n как предыдущий?
4. И нужно ли добавлять ассерты? т.е. было ab^c. Должно генерироваться ab\n^c или ab$\n^c?

Reported by eklepilkina on 2013-09-10 10:18:49

[Oleg Sychev]

Нет, Лена, вы неправильно подходите с самого начала. Если предыдущий переход [ab] а
следующий ^ - то эта ветка непроходима в принципе, и ее можно сразу обрывать. А вот
если предыдущий переход [ab\n] а следующий ^, то из предыдущего перехода может совпасть
только \n, остальные символы можно убирать (если, конечно, из состояния 1 не ведет
другой ветки, в обход ассерта).

И именно поэтому ассерты типа ^ и \A должны мержится назад, чтобы иметь возможность
повлиять именно на предыдущий переход.

Я собственно предложил в комменте сделать вместо mergedassertions два массива - assertionsbefore
and assertionsafter - если сливали изменения из моего клона, то он у вас есть - так
проще обрабатывать те ассерты, которые были слиты из следующих (и должны быть проверены
позже - ^ \A - и те, что слиты из предыдущих и должны быть проверены перед символов
- $, \Z \z

Ассерты сами по себе символы не генерируют, они только накладывают ограничения на символы,
генерируемые другими переходами. В генерируемую строку они тем более не попадают.
P.S. Если не очень понятно, я в среду с 15 часов пересдачи принимаю, ближе к конце
(17-18 часов)можете подойти, обсудим на примерах.

Reported by oasychev on 2013-09-10 19:29:42

[Former user]

Мне в принципе понятно. Давайте я попробую нарисовать тесты к match и next_character.
И тогда уже будут конкретные замечания.

Reported by eklepilkina on 2013-09-11 04:56:34

[Former user]

Прийти не смогу сегодня. Как тесты будут готовы выложу их сюда.

Reported by eklepilkina on 2013-09-11 04:58:57

[Former user]

Моя версия тестов.

Reported by eklepilkina on 2013-09-13 14:04:33

<hr> * Attachment: test_match_next.docx

[Oleg Sychev]

Не совсем то. ^ дает совпадение в начале строки и после \n. Тестов на начало строки
(там слева вообще не будет переходов, так что ^ в листе будет не слитой) не вижу. Как
и на конец строки (для $). Обратите внимание, что в начале (конце) строки чтобы совпасть
переход с ^ ($) должен быть первым (последним), и соответственно мержится ему будет
не с чем. Так можно определить при генерации для $ например надо ли закончить здесь
строку (там есть вариант ENDS_HERE) или нельзя сгененрировать. Аналогично ^ ни с чем
не смерженная не должна генерировать ничего - после нее можно и символы другие ставить.

Я бы вообще подправил мержинг простых ассертов так, чтобы дуги типа [^ab] не создавались
вообще - все равно они ни с чем совпасть не могут, а от [ab\n] при мержинге с крышкой
получался бы [^\n] ибо других вариантов нет. Тогда и тут с тестами будет проще...

Далее в тесте 6 матчинга много непонятного: шансы на возникновение узла чисто $^ нулевые,
т.к. крышка мержится назад, а доллар - вперед - и мержинг не может идти в другой простой
ассерт, для мержинга надо искать съедающий переход (кстати, надо внести поправку в
алгоритм). Вот если в регексе было типа $[ab\n]^ - тогда они могут оказаться вместе
- но только вместе с символом. И перевод строки в таком месте регекса вполне допустим.
А у вас - false.
Тесты 9 и 10 - количество одинаковых ассертов не имеет значения, потому что это просто
несколько раз проверить одно и тоже условие в одном и том же месте. По строке они не
сдвигаются.  Точно также и надписи ^$ и $^ одинаковы - порядок нескольких записанных
подряд ассертов ни на что не влияет, т.к. все условия в одном месте проверяются...

По генерации - 6-й тест тоже описывает ситуацию, которая возникать не должна: если
уж $ и ^ оказались рядом и ничего больше нет, (т.е. весь регекс из них двух и состоит),
то они должны остаться двумя разными переходами... 9 и 10 аналогично

Reported by oasychev on 2013-09-13 15:04:49

[Former user]

Вроде исправила основные замечания.
Добавила тесты на начало строки только я не пойму как задавать в таком случае позицию.
В комментариях к функциям написано, что в случае незахватывающего перехода передаем
позицию предшествующего захватывающего символа. Т.е. для ^ в самом начале передадим
-1?
Мержинг поправлю, чтобы не было [^ab], но, я думаю, что тесты на такие случаи нужны
потому что они могут получиться после пересечения.

Reported by eklepilkina on 2013-09-14 14:07:46

<hr> * Attachment: test_match_next.docx

[Oleg Sychev]

На match к 7-му тесту нужно наверное пару, где будет \n в чарсете - тогда же он совпадет
по идее. А к 8-му аналогичную без \n что не совпадет.

С next_character вроде нормально все.

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

Reported by oasychev on 2013-09-14 21:33:14

[Former user]

Добавила. Тогда в таком виде их можно добавлять в проект и править функции?

Reported by eklepilkina on 2013-09-15 05:04:37

<hr> * Attachment: test_match_next.docx

[Oleg Sychev]

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

В узле я думаю поняли - надо вместо одного mergedassertions сделать два поля -  я в
TODO записал - см выше комментарий 20. Так будет удобнее обрабатывать ассерты...

Reported by oasychev on 2013-09-15 16:53:32

[Oleg Sychev]

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

Тесты очень странно написаны. Во-первых, в данном случае не стоит использовать лексер.
Создайте объект листа самостоятельно, это не так сложно. В крайнем случае Валерий вас
проконсультирует, но для ваших листьев там все очевидно. Во-вторых, вы и для лексера
написали то странно - вместо [ab]\n с последующим объединением можно было написать
[ab\n].

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

И еще $length возвращаемая из match насколько я помню - это длина совпадения с данным
узлом. Больше 1 она может быть у обратных ссылок, но никак не у чарсетов...

Reported by oasychev on 2013-09-19 14:07:16

[Oleg Sychev]

Лена, а зачем вы сделали такой страшненький switch-case в preg_fa.php для создания новых
ассертов в read_fa()? Да еще в нескольких экземплярах - можно было создать хотя бы
функцию, чтобы его не дублировать.

Два момента странных: \A и \G по своей сути похожи на ^ и должны мержится в том же
направлении - это ассерты начала; а вот \z \Z - мержаться в направлении доллара, это
ассерты конца. У вас не совсем так, крышка держится как-то обособленно от других.

Не уверен, что есть смысл мержить таким способом \b \B - они должны мержится отдельным
кодом, разбиваясь на 4 альтернативных пути. А пока пусть лучше побудут отдельными переходами
- их в обе стороны надо мержить. Этим двум ассертам в assertionsbefore, assertionsafter
делать нечего...

И второй момент - около switch идет цикл по $j, но в самом switch анализируется $asserts[0],
а $j внутри цикла так и не используется - это нормально? Или просто теста более чем
на 1 ассерт не было?

Такие вещи гораздо лучше работают используя массив - строку как ключ, строку с именем
класса как значение - но тут проблемы из-за true/false - Валерий

Reported by oasychev on 2013-09-20 22:16:57

[Oleg Sychev]

P.S. 
Лена - есть такая очень полезная ссылка pcre.org/pcre.txt Целиком читать не нужно,
он огромный - но поиском там можно найти детальную и подробную информацию, как должна
работать любая часть перл-совместимых регексов. Советую научиться работать и сверяться
по сути действий с логикой этого файла.

Валерий - как видите, параметр в листах-ассертах типа esc_z не очень хорош - фабрика
при считывании из-за него вырождается в switch, т.к. сделать массив типа "надпись"
=> "имя класса" не получится. Не имеет смысл все-таки все отдельными сделать? Или как-то
еще фабрику упростить...

Reported by oasychev on 2013-09-20 22:21:06

[Former user]

read_fa - функция Никиты, я ее старалась не трогать, просто исправила во всех местах,
где надо mergedassertions на 2 массива и создание ассертов, т.к. они теперь отдельные
классы, чтобы иметь возможность запускать тесты. Что там творится в read_fa подробно
не знаю.
Насчет ассертов \A, я думала, что хоть он и похож на ^, но для него без разницы, куда
мержится. Насколько я о нем читала это начало данных в многострочном режиме и он может
стоять только в самом начале и таких проблем как с ^, что она может что-то генерировать
вроде нет. Или не так. 
Про \G хорошо перенесу к ^.  Только я не пойму, как он может влиять на генерацию символа.
\В остался там, как это было при начальной версии программы. Мержится они будут отдельно.

Reported by eklepilkina on 2013-09-21 05:13:53

[Oleg Sychev]

Подробно не надо, я как раз ваши правки имел ввиду в этой функции.

На самом деле всем будет удобнее, если все ассерты, проверяющие начало, будут мержится
в одну сторону. Потому что ^ тоже проверяет на начало, а не только на перевод строки;
писать этот код по разному потому что одно проверяется после символа, а другое - до
- неудобно и странно.

Я бы вообще, избегая дублирования кода, поигрался бы больше с наследованием - унаследовал
например ^ от \A, т.к. это частный ее случай: можно вызывать родительскую функцию и
добавить потом свое. Аналогично \z \Z и $ могут быть связаны наследованием. Но для
этого они должны мержится в один массив ^ \A \G, в другой - \Z \z и $.

А для \b \B я бы ввел правило, что они как ассерты внутрь других переходов не мержатся,
и выкидывал бы исключение при попытке такое создать (в частности в read_fa), что они
должны быть отдельными переходами, либо раскладываться на более простые. Иначе придется
прописывать next_character с их учетом, а это очень сложно, если вообще возможно.

Reported by oasychev on 2013-09-21 12:41:29

[Former user]

Насчет правок у Никиты все было аналогично, я просто заменяла, а структуру реализации
не трогала.
Мне сейчас менять классы ассертов? Делать их с наследованием? 
По разделению на массивы поняла, сделаю.

Reported by eklepilkina on 2013-09-21 16:03:18

[Former user]

И еще хотела спросить. В справках написано \Z     matches at the end of the subject
also matches before a newline at the end of the subject
Получается, что \Z эквивалентен $ в том, что ставится в конце строки? Но при этом \Z
ставится и в конце данных, а $ может не стоять в конце данных? Так?

Reported by eklepilkina on 2013-09-21 16:25:25

[Oleg Sychev]

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

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

Reported by oasychev on 2013-09-21 16:39:11

[Former user]

Я думаю о таком наследовании.

Reported by eklepilkina on 2013-09-22 10:01:47

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

[Oleg Sychev]

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

Общее направление наследования от меньших проверок к большим, чтобы наследник позволял
больше случаев. Поэтому я бы наследовал ассерты конца по тройной цепочке - \z -> \Z
-> $ С наследованием ^ от \A согласен.

Reported by oasychev on 2013-09-22 18:09:29

[Oleg Sychev]

Лена, в qtype_preg_leaf_assert уже есть функции is_start_anchor и is_end_anchor с тем
же примерно смыслом, что и is_afterassertion/is_beforeassertion только они их код устарел
- не надо дублировать функции, перенесите свой код в старые функции.

И я думаю, в новом варианте классам ассертов не нужен $negative кроме \b, поэтому из
конкретных конструкторов его можно убрать, оставить в родительском и \b.

И еще у меня вызывает вопросы ситуация с индексом проверяемого символа для \n. Вы сделали
его разным в разных ассертах - в явном рассчете на то, что они находятся в разных массивах
и одни проверяются до, другие - после символа ($pos и $pos - 1). Но вы помните, что
ассерт может и остаться несмерженным, если он первый (ассерт начала) или последний
(ассерт конца)? В таком случае могут быть проблемы с проверкой, нет? Если такие проблемы
есть, надо индексацию делать везде одинаковой, а разницу до/после учитывать, когда
вызываете match(next_character) ассерта из такой же функции чарсета, с которым он смержен
- можно же позицию как хочешь передать...

Reported by oasychev on 2013-09-23 20:12:53

[Former user]

Вы имеете в виду про проблемы с проверками, что обращение будет к несуществующему элементу,
т.е. допустим к позиции в строке -1? Там вроде не должно быть таких проблем, ведь,
сначала вызываются родительские классы, которые проверяют на начало(конец) всего объекта,
и если они вернут true, то в условие дальше проверятся не будет, там же дизъюнкция
везде. Разве нет?

Reported by eklepilkina on 2013-09-24 05:40:33

[Oleg Sychev]

Я имею ввиду, что ассерт должен работать одинаково и когда он смержен, и когда нет -
потому что смержить всегда не получится. И проверять всегда одинаковые символы относительно
$pos. А если при мержинге он сдвигается так, что начинает проверять не то место - можно
учесть это при вызове, передавая другое значение как $pos,  а не внутри кода ассерта.

Если непонятно, можете коротко с Клевцовым в четверг подойти, только попозже - между
10-10 (это время их начала) и 11-50 (дальше у меня пары).

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

Reported by oasychev on 2013-09-25 18:59:57

[Former user]

"Если у вас есть несколько строк для проверки на одном переходе, проверку может сделать
одна функция: создайте узел и последовательно проверяйте разные строки, чтобы не повторять
работу по его созданию." Т.е. несколько тестов объединять в один?

Reported by eklepilkina on 2013-09-27 15:44:31

[Former user]

И все-таки я не очень понимаю, почему плохо использовать лексер в тестах? Просто придется
или дублировать код, или писать функцию-аналог функции получения charset лексера.

Reported by eklepilkina on 2013-09-27 15:53:04

[Oleg Sychev]

На 42 - да, нет четких границ что такое "один тест" в смысле одной функции. Можно считать
одним тестом один переход с несколькими строками например. Единственное - если PHPUnit
встречает зафейленный ассерт, он переходит к следующей функции. Эта функция далее не
выполняется. Но обычно это не такая уж проблема, все равно фейлы надо обходить...

По 43 - хорошо, используйте лексер - так тест понятнее - только сделайте нормально;
зачем вы делаете [ab]\n а потом два узла объединяете? Вполне можно сразу написать [ab\n]
и получить готовый чарсет из лексера.

Reported by oasychev on 2013-09-27 19:26:11

[Former user]

У меня вроде нет одинаковых узлов в тестах. Они там отличаются либо символами, либо
смерженными ассертами. Или мне внутри теста после первой проверки менять ассерты и
проверять снова?
Сейчас все тесты для match и для next_character проходят.

Reported by eklepilkina on 2013-09-29 14:42:51

[Former user]

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

Reported by eklepilkina on 2013-10-03 09:52:13

[Oleg Sychev]

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

\Z может сгенерировать перевод строки - но только если за ним не будут сгенерированы
еще символы.

Лена - такие тесты были? Что если последний то может, а если далее еще есть символы
- то не генерирует?

Есть мнения, как решать? Валерий - прошу присоединится...

Reported by oasychev on 2013-10-17 19:33:46

[Former user]

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

Reported by eklepilkina on 2013-10-18 04:38:06

[Former user]

Только вот там все на leaf построено, но без автомата, мне кажется не получится.

Reported by eklepilkina on 2013-10-18 05:12:51

[Former user]

А можно передавать в next_character еще один параметр - флаг, принадлежит ли данный
leaf к переходу, являющимся последним, и по нему тогда уже определять возможность генерации
\Z.
Но это усложнит вызов функции.

Reported by eklepilkina on 2013-10-18 06:10:32

[Oleg Sychev]

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

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

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

Поэтому я все-таки хочу услышать мнение Валерия.

Лена, а вы пока тесты добавьте... И в кросс-тесты тут нужно будет несколько ситуаций
- когда следующий переход генерирует символы, когда это последний переход в автомате,
когда есть еще ассерт-переходы после текущего; и когда есть развилка - можно сгенерировать
символ или можно не генерировать.

Сам переход принимающий последний \n - если он есть - будет неизбежно смержен с ассертом.
Т.е. \Z должен генерировать \n только если смержен в переход, его допускающий - сам
по себе он генерирует "закончить тут" - так короче получается строка. Значит наверное
нужен специальный параметр в next, который позволял бы знать, смержен ассерт или нет...

Reported by oasychev on 2013-10-18 12:40:44

[Valeriy Streltsov]

Ну вместо "еще одного флага" можно добавить метод в интерфейс qtype_preg_matcher_state.
Но я за решение объект с "отдельно символом и флагом". Нужные флаги еще добавим...

Reported by vostreltsov on 2013-10-18 13:30:54

[Oleg Sychev]

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

В Moodle это часто решается возвратом массива (только это должен быть всегда массив)
и вызовом типа:
list ($a, $b) = fn(...);

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

Reported by oasychev on 2013-10-18 13:42:32

[Oleg Sychev]

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

Надо дополнить тесты и переработать мержинг.

Reported by oasychev on 2013-11-07 12:28:03

[Former user]

Я посмотрела тесты с НКПО, там такие тесты есть, но они неправильные.
Вопрос еще про тесты вида как на merge1. Должен же получится автомат как на merge2.
merge3 как делалось в тестах НКПО неправильно ведь?
И еще вопрос, а есть смысл переписывать мержинг со слиянием? Просто мержинг без слияния
вершин дает всегда правильные результаты.

Reported by eklepilkina on 2013-11-08 13:45:07

<hr> * Attachment: merge1.png<br> * Attachment: merge2.png<br> * Attachment: merge3.png<br>

[Oleg Sychev]

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

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

Reported by oasychev on 2013-11-08 14:46:41

[Former user]

Я про метод go_round_transition, который использовался в случае, если в автомате были
переходы, ведущие не через состояние, предназначенное для пересечения.
Он выполнит мержинг, просто тогда одна вершина станет тупиковой и удалится. Будет так.
и После мержинга при вызове удаления тупиковых вершина 2 (merge2) удалится.

Reported by eklepilkina on 2013-11-08 16:10:08

<hr> * Attachment: merge1.png<br> * Attachment: merge2.png<br>

[Oleg Sychev]

Что касается мержинга, то первый эксперимент который вам надо провести вместе со Стрельцовым
- это сохранить текущее состояние фейлов кросс-тестов, далее сделать в НКА-матчере
вызов функции удаления эпсилон-переходов (но не ассертов пока) - и посмотреть какие
фейлы добавятся - скорее всего с тегами возникут какие-то проблемы... Для этого кросс-тестов
должно быть достаточно...

После этого мы втроем сможем встретится и обсудить, как это решить. Оно же поможет
нам и понять, как мержить простые ассерты.

Reported by oasychev on 2013-11-08 18:09:37

[Former user]

Начет того, что дали кросс-тесты. Там много проваленных тестов, но если с пустыми переходами
это решаемо, либо в зависимости от того, какой тег, открывающийся или закрывающийся
переносить его либо в следующий, либо в предыдущей переход при возможности. Либо заносить
теги в узлы, но я так поняла, это вызовет очень большие проблемы для матчинга.
Для ассертов ситуация хуже. Я так понимаю, что чаще встречаются такие ситуации как
(^ и $). Если просто переносить теги ( пойдет в следующий переход ^ мержится назад,
и внутренности тега меняется. С $ наоборот он вперед, а ) назад. Если заносить теги
в узлы, то ассерт тоже выйдет за границу тега, т.к. сам переход тоже сливается с предыдущим(следующим)захватывающим.
Получается, что ассерты с тегами мержить нельзя.
И второе, На НКПО было 2 варианта мержинга, и был выбор внутри основной функции. Если
запускать такой вариант, то он работает значительно дольше, чем вариант простого мержинга
без слияния вершин, но с последующим удалением тупиковых. Я хочу полностью перейти
на него, при том, что там не возникает проблемы с разворачиванием циклов и ветвлений.

Reported by eklepilkina on 2013-11-11 11:05:27

[Oleg Sychev]

С тегами для ассертов есть одна хорошая закономерность: если ассерт находится около
тега, все равно с какой стороны тег от него окажется после мержинга, т.к. ассерт не
захватывает символов.

Reported by oasychev on 2013-11-11 12:55:39

[Former user]

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

Reported by eklepilkina on 2013-11-11 15:18:23

[Valeriy Streltsov]

В состояния не получится. Контр-пример: (a|())
Если мёржить тег пустого подвыражения в начальное состояние, то захват a будет всегда
происходить после захвата пустого подвыражения, что не соответствует действительности.

Возможно, стоит как-то клонировать состояния, в которые идёт мёржинг. Надо думать.

Reported by vostreltsov on 2013-11-11 18:06:35

[Former user]

Может пока стоит оставить теги в переходах?
И мне нужно все-таки решение о методе мержинга.
И для \b нужны же тесты для тегов?  

Reported by eklepilkina on 2013-11-12 06:52:52

[Oleg Sychev]

Насколько я понимаю, ситуации типа ....(a|()).... ....(a|(\z)).... и ....(a|(\b))....
ставят под сомнение вообще - сможем ли мы всегда избавиться от эпсилон-переходов, сохранив
корректную работу тегов или нет. Я бы начал с решения этого вопроса - он влияет на
многое, мы от эпсилонов избавлялись то не зря....

Reported by oasychev on 2013-11-12 14:29:06

[Oleg Sychev]

Лена - если плохо понятно, считайте для начала что каждая открывающая круглая скобка
ставит открывающий тег, закрывающая - соответствующий закрывающий.
И попробуйте нарисовать автоматы для  ....(a|()).... ....(a|(\z)).... и ....(a|(\b))....
- как они у вас буду смержены и как сделать так, чтобы тегами было зафиксировано, прошел
через пустоту (ассерт) - вторые скобки - или нет.  Скорее всего из таких примеров и
надо подбирать алгоритм

Reported by oasychev on 2013-11-12 14:49:02

[Former user]

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

Reported by eklepilkina on 2013-11-12 15:00:21

[Oleg Sychev]

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

Reported by oasychev on 2013-11-12 20:03:29

[Oleg Sychev]

Есть мнение, что открывающие теги в эпсилон-переходах следует мержить влево - как ^,
а закрывающие - вправо - как $. Возможно это поможет решить существующие проблемы...

Reported by oasychev on 2013-11-13 19:00:13

[Former user]

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

Reported by eklepilkina on 2013-11-14 04:33:59

[Oleg Sychev]

Разумеется не только можно, но и нужно - смерженные влево выполняются после; смерженные
вправо - перед своим переходом.

Если некуда мержить в начале (влево) или конце (вправо) автомата это не проблема.

Reported by oasychev on 2013-11-14 10:21:47

[Former user]

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

Reported by eklepilkina on 2013-11-16 07:46:03

<hr> * Attachment: tag.png<br> * Attachment: tagresult.png<br>

[Oleg Sychev]

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

Reported by oasychev on 2013-11-16 16:10:23

[Former user]

(a|()) - рис.1
(a|(\Z)) - рис.2. Вы по моему говорили, что неважно, с какой стороны от тега стоит
ассерт. Если это так, то такой рисунок. Если нет, то сливать вообще не получиться.
(a|(\b)). Вот тут же переходы, в которые развернется \b нужно пересекать с захватывающими
до тега и после, только с развилкой, т.к. не всегда проходит через \b. Так? А в случае,
если только так, я думаю, что как-то так рис.3

Reported by eklepilkina on 2013-11-27 18:08:30

<hr> * Attachment: tag.png<br> * Attachment: tagz.png<br> * Attachment: tagb.png<br>

[Oleg Sychev]

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

А что с измерением производительности при включенном/выключенном мержинге эпсилонов?
Какова разница сейчас?

Reported by oasychev on 2013-11-27 20:54:58

[Former user]

Я не знаю, как заставить dot не пересекать эти связи, но автомат такой:
0->1[label = "("];
1->3[label = "a"];
3->4[label = ")"];
0->2[label = "\w((", style = dotted];
2->4[label = "))\W", style = dotted];
0->5[label = "\W((", style = dotted];
5->4[label = "))\w", style = dotted];
0->6[label = "^(("];
6->4[label = "))\w", style = dotted];
0->7[label = "\w((", style = dotted];
7->4[label = "))$"];

Насчет времени. У меня с мержингом сейчас даже меньше затрачивается,видимо, за счет
того, что много тестов фейлится.

Результаты с мержингом:
======================
PASSED:     1780
FAILED:     157
SKIPPED:    518
EXCEPTIONS: 372
======================

Time: 08:13, Memory: 142.25Mb

А просто тесты:
======================
PASSED:     2259
FAILED:     50
SKIPPED:    518
EXCEPTIONS: 0
======================

Time: 10:50, Memory: 142.25Mb

Reported by eklepilkina on 2013-11-28 13:44:48

[Former user]

Я попробовала поправить тесты по замечаниям.
Правда по вашему замечанию на 7 тест, я так понимаю, нет разницы между "\n^" и "^\n".
И я не поняла нужны вообще те тесты с 16 по 25, к которым еще строки написаны. Вы в
прошлый раз сказали, что эти случаи оттестированы в основном.

Reported by eklepilkina on 2014-01-21 16:53:26

<hr> * Attachment: cross.docx

[Oleg Sychev]

Разница между "\n^" и "^\n" есть - с первым регексом совпадет строка в которое есть
один перевод строки, со вторым чтобы было совпадение нужно два перевода строки подряд.
Тесты с 16 по 25 нужны, в точности таких тестов не было, а когда дело касается матчинга
регексов никогда нельзя быть слишком уверенным, что все хорошо - мы уже много раз на
это нарывались. 

Reported by oasychev on 2014-01-21 20:27:29

[Former user]

Написала варианты строк на регексы с 16 по 25.

Reported by eklepilkina on 2014-01-22 16:00:11

<hr> * Attachment: cross.docx

[Oleg Sychev]

28-го буду в универе; с 10-10 принимаю досдачи; если успею проверить до этого в электронном
виде - напишу - обсудим результаты, но будет тяжеловато без страниц предыдущей проверки
- много времени прошло с тех пор; если не успею - желательно принести или передать
в бумаге со старыми вариантами как обычно.
Подходите ближе к 13..14 часам, когда основная масса досдающих рассосется...

Reported by oasychev on 2014-01-26 20:17:07

[Former user]

Олег Александрович, Вы сказали, чтобы я поговорила с Валерием и после этого как-то перерабатывала
код. Я поговорила и, как я поняла, все будет делаться(в том числе и \b) при построении
автомата, и написанные функции мержинга теперь не нужны совсем. Что конкретно, Вы хотели,
чтобы я делала?

Reported by eklepilkina on 2014-01-28 15:37:48

[Valeriy Streltsov]

Вставлю свои 5 копеек: \b при построении можно убрать только те, которые по краям автомата,
т.е. эквивалентны ^ или $

Reported by vostreltsov on 2014-01-28 15:56:25

[Former user]

Эквиваленты ^ и $, но почему по краям автомата? А многострочный режим? Они мержатся
к \n.

Reported by eklepilkina on 2014-01-28 17:12:34

[Oleg Sychev]

Куда вы все лезете в бутылку с далеко идущими планами?? Не трогаем пока \b  - дожить
надо. Без нормальной ^ и $ и устранения несъедающих в середине автомата он работать
не будет в любом случае. Давайте сосредоточимся на этой задаче!

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

Вы сейчас передумали по каким-то причинам или забыли? Если у вас какие-то новые предложения
- донесите их вразумительным образом... И думайте пожалуйста внимательно (для справки
 - \b по краям автомата не эквивалентны ^ или $ даже в однострочном режиме - они эквивалентны
ТОЛЬКО если матчинг exact, в противном случае при старте совпадения не в начале строки
они ведут себя совсем иначе...)

Reported by oasychev on 2014-01-29 10:10:23

[Former user]

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

Reported by eklepilkina on 2014-01-29 16:06:36

[Former user]

Олег Александрович, я вроде подправила тесты. Когда их Вам можно отдать?

Reported by eklepilkina on 2014-02-19 16:27:43

[Oleg Sychev]

На кафедре висит мое расписание, я буду в четверг и пятницу с 11-50... Модификаторы
уже к нормальным в PHP приведены?

Reported by oasychev on 2014-02-19 18:05:51

[Valeriy Streltsov]

При мержинге вперед нужно будет копировать tag set'ы в конец массива tag set'ов съедающего
перехода. При мержинге назад - препендить в начало массива.

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

Reported by vostreltsov on 2014-02-22 17:07:44

[Oleg Sychev]

Лена, ситуация с пустотой вроде в основном разрешена, пробуйте интегрировать код мержинга
ассертов

Reported by oasychev on 2014-02-22 17:08:54

[Valeriy Streltsov]

Я попробую сделать proof-of-concept мёржинга пустоты используя нативные php айдишники
объектов. Но они там вроде строковые, поэтому если всё будет работать - добавим в переход
целочисленное поле id и будем создавать переходы через статическую функцию, которая
эти айдишники будет раздавать

Reported by vostreltsov on 2014-02-23 13:47:41

[Former user]

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

Reported by eklepilkina on 2014-02-23 14:14:46

[Former user]

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

Reported by eklepilkina on 2014-02-23 14:16:56

[Oleg Sychev]

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

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

Reported by oasychev on 2014-02-23 17:26:20

[Former user]

Вообщем я отладочной печатью проверяла каждый шаг алгоритма мержинга. К чему я пришла:
там, где зацикливаются тесты, они зацикливаются не по вине мержинга. По моему он работает,
тот тест на котором проверяла внутри документа. Зацикливается выполнение тегов, когда
несколько setов у перехода-цикла (чистого цикла 1-1, 3-3). Мержинг отрабатывает полностью,
конечно, неидеально сейчас, я там поправлю, там пустые переходы 0->3 и 3->4 не слились,
но в принципе по моему он правильный.

Reported by eklepilkina on 2014-02-25 15:40:00

<hr> * Attachment: res.pdf

[Valeriy Streltsov]

Нет. Достаточно запускать fa_building_test.php и смотреть что на выходе. Там функция
матчинга не вызывается, да и зависать она не может в принципе до тех пор пока в регексе
нет обратных ссылок.

Reported by vostreltsov on 2014-02-25 17:20:56

[Former user]

Проблемы, которые остались по мержингу eps и которые я решить не могу:
1. Зацикливание одного теста с обратными ссылками. Автомат очень большой около 1000
состояний, как его отлаживать не знаю. Причем, когда вместо обратных ссылок из-за функции
intersect_asserts проставлялись пустые переходы, тест не зацикливался. Мержинг завершает
работу, переходы, получающиеся после исправления функции такие же по состояниям и тегам,
только внутри теперь правильные обратные ссылки, а не eps. Но потом почему-то автомат
не выполняется. Я думала, что после мержинга в нем получаются зацикленные вершины,
но, я проверила, явных циклов нет. Почему зависает теперь понять не могу.
2. Непонятные для меня фейлы. Автоматы эквивалентные, картинки приложены...Теги стоят
правильно, но тесты не проходят. И таких фейлов несколько, в основном все очень простые
автоматы без обратных ссылок, циклов и т.п. Что не так тоже не знаю, поэтому что править
тоже не знаю.

Насчет ассертов я еще не все тесты прогнала,тесты att проходят кроме одного.
По нему такой вопрос, он выдвет такой фейл.
nfa_matcher failed on regex '$^' and string '' (qtype_preg_cross_tests_from_att_basic,
data_for_test_att_basic_18):
IS_MATCH:        FALSE
FULL:            FALSE
INDEX_FIRST:     0=>-1, 
LENGTH:          0=>-1, 
expected:
IS_MATCH:        TRUE
FULL:            TRUE
INDEX_FIRST:     0=>0, 
LENGTH:          0=>0, 
Разве такой регекс не подразумевает, что между ними должен быть перевод строки? Или
это только в многострочном режиме? Просто, когда в октябре правилась функция совпадения
для смерженных ассертов, там режимы не учитывались. Как правильно?
pcre и preg еще не проверяла.

Reported by eklepilkina on 2014-03-13 16:21:20

<hr> * Attachment: graph1.png<br> * Attachment: graph2.png<br>

[Oleg Sychev]

$^ должны давать совпадение с пустой строкой: ассерты ведь просто проверяют условие,
но не трогают позицию совпадения. Поэтому $ проверяет пустую строку и видит, что он
в ее конце - истина; потом крышка проверяет и видит что в начале - тоже истина. Начните
с того что выясните, какой из них дает false на пустой строке в этой позиции. И как
выглядит автомат?

Reported by oasychev on 2014-03-13 17:54:10

[Oleg Sychev]

Еще я советовал бы добавить в preg_leaf функцию типа is_capturing, определяющую является
ли переход "съедающим" возвращающую true/false/null. Последний вариант null - может
быть, а может нет - применяется для обратных ссылок и рекурсии, которые nullable -
т.е. могут совпасть с пустотой (Лена - Валерий вам объяснит про это свойство).

Такая функция могла бы использоваться вместо условий типа "если чарсет или обратная
ссылка" - которые склонны к ошибкам (например забыли про лист рекурсии). В случае столкновения
с null необходимо будет сделать специальное исключение, что ассерты рядом с такими
операндами не поддерживаются (Валерий - с тегами может быть хуже, если вы их описываете
для всех подмасок, они очень часто там окажутся рядом; какие мысли?). Только сравнивать
на true/false/null надо через === а не через ==

Reported by oasychev on 2014-03-13 18:21:31

[Former user]

Насчет ^ и $ я нашла ошибку. Видимо, это я неправильно поправила match в октябре. Теперь
тест проходит.
Вы считаете условие "если чарсет или обратная ссылка" в intersect_asserts приводит
к зацикливанию? 

Reported by eklepilkina on 2014-03-13 18:36:55

[Oleg Sychev]

Я считаю что это условие приводит к проблемам. И еще приведет, когда будем окончательно
доделывать и активировать рекурсию например - новый вид листа, который обычно съедающий,
но может быть и нет. Забудем туда его дописать наверняка...

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

Reported by oasychev on 2014-03-13 18:39:22

[Former user]

Олег Александрович, а может не будем мержить пустые переходы и ассерты с обратными ссылками
вообще?

Reported by eklepilkina on 2014-03-14 15:05:49

[Oleg Sychev]

Ну почему? Как минимум можно мержить с теми обратными ссылками, чьи соответствующие
подмаски не допускают пустого совпадения. Это легко определяется - Валерий уже написал
функции, прописывающие каждому узлу дерева некоторые его свойства - в т.ч. nullable
- т.е. возможность совпадать с пустотой (Валерий - надеюсь по обратным ссылкам они
берут эти данные из соответствующей подмаски? И учитывают повторение подмасок...)

А то, что вы предлагаете, нас сильно ограничит без особой надобности.

Reported by oasychev on 2014-03-14 15:12:07

[Former user]

Возник еще вопрос. Я должна мержить условные подвыражения? Я всегда все тесты, все делала
вроде на ^, $, \Z, \z, \A. \G я при мержинге не трогаю.

Reported by eklepilkina on 2014-03-15 04:51:16

[Oleg Sychev]

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

Валерий, если в условном подвыражении две ветки, там получается у вас два этих "псевдо-ассерта"
или один? По идее надо бы два (противоположных), чтобы мержить в разные ветки...

Reported by oasychev on 2014-03-15 09:53:05

[Valeriy Streltsov]

Естессно, два ассерта и две ветки

Reported by vostreltsov on 2014-03-15 10:14:02

[Former user]

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

Reported by eklepilkina on 2014-03-15 16:30:22

<hr> * Attachment: graph1.png<br> * Attachment: graph2.png<br>

[Oleg Sychev]

Смысл тот, что переходы с условиями - типа (1) и !(1) в вашем примере, являются несъедающими
- по сути они эквивалентны ассертам и должны мержится так же, как и ассерты - но всегда
вперед по прикидке. А ваша программа похоже считает их съедающими и мержит что-то в
них.

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

Валерий - сделайте быстро эту consume или Лене объясните, как надо переделать!

Reported by oasychev on 2014-03-15 19:49:56

[Former user]

Нет, она не считает их съедающими, она признает их ассертами, и получается переход из
11->21 типа ассерт \Z со смерженным условным ассертом.
Почему я не могу мержить ассерт с ассертом? Переход у меня итоговый типа leaf_assert
не захватывающий, все правильно.У меня полно таких тестов...
Там, все таки он идет не по той ветке при генерации. Он должен генерировать скобку,
а проходит по \Z  со смерженным условным.

Reported by eklepilkina on 2014-03-16 04:27:01

[Oleg Sychev]

Вы можете мержить ассерт с ассертом (через И), но получившийся переход несъедающий -
сам по себе ассерт, и должен быть смержен далее вправо если это был \Z - ведь цель
мержинга избавиться от переходов-ассертов, чтобы мог работать механизм мержинга больших
ассертов.

Хуже если первый ассерт (1) а второй ^ - который мержится влево, тогда они должны обменяться
местами - ^ уйти в левый съедающий узел, а (1) - в правый, ни в коем случае смержится
вместе они не должны! Аналогично $^ не должны смержится вместе ввиду разнонаправленности
мержнинга.

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

Reported by oasychev on 2014-03-16 18:08:49

[Former user]

Я поняла. Насчет условных ассертов и мержащихся назад обычных я подумаю. А вот насчет
$^ при однострочном режиме в любом случае совпадут с пустой строкой, такой тест проходит.
А при многострочном, они совпадут только, если дойдут до \n в мержинге.
И да "^ уйти в левый съедающий узел, а (1) - в правый" такая ситуация по алгоритму
в принципе не возможна, если ассерты склеились, они так и будут склеенные, даже если
переход дальше будет мержится.
Но проблема будет такая, если у меня получится ^, смерженная с (1), сольется с переходом
[a], то получится, что (1) будет выполняться до a, хотя должен был после.
Ну и еще проблемы с модификатором D такие же вроде получаются из-за выполнения до.
Может стоит перекидывать в таком случае, beforeasserts в afterasserts?

Reported by eklepilkina on 2014-03-16 18:55:54

[Oleg Sychev]

Для того чтобы лучше понять ситуацию с $^ представьте ее окруженной другими символами
\n$^\n
грубо говоря. Доллар должен уйти в правый \n, а крышка - в левый.
Аналогично и в других ситуациях - алгоритм не должен сцеплять (мержить один в другой)
ассерты, которые мержаться в разные стороны - только в одинаковые; если они мержаться
в разные (и при этом друг в друга, а не расходящимся образом) то он должен обменять
их местами (с учетом возможных развилок между ними, конечно), после чего заново попробовать
смержить.

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

Алгоритм это средство а не цель, если он не соответствует цели то его надо менять,
а не ссылаться на него.

Reported by oasychev on 2014-03-16 19:02:06

[Oleg Sychev]

Я думаю что в классы узлов-ассертов надо добавить еще функцию, возвращающую направление
мержинга (вперед/назад). Так оно будет удобнее и программировать, и экспериментировать
с направлениями.

Reported by oasychev on 2014-03-16 19:33:19

[Former user]

Насчет мержинга разнонаправленных ассертов я все-таки склоняюсь к обмену их местами.
Потому что, если мержить до ближайшего съедающего много останется не смерженного. Даже
в том примере, что я кидала, когда оба ассерта мержатся вперед они будут при таком
варианте не смержены. Единственное в развилках придется добавлять дополнительные вершины.
И я не уверена, нормально ли отразится смена на условных ассертах.
А вот с циклами такого типа как на картинке не знаю, что делать. Оно ни с чем не сматчися
вроде, но теоретически он же возможен.

Reported by eklepilkina on 2014-03-17 18:18:10

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

[Oleg Sychev]

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

Поэтому мне кажется наиболее перспективным вариант "мержить то, что можно легко смержить,
после чего делать еще проход если оставались несмерженные (можно даже массив таких
дуг провести).

В случае циклов из чисто ассертов они могут быть устранены, т.к. им хоть одно повторение,
хоть двадцать пять  - одно и тоже (позиция то не сдвигается, какая разница сколько
раз проверять одно и тоже условие в одном и том же месте?). Т.е. ваш вариант a$(^$)*b
можно раскрыть как a$(^$)?b - они будут абсолютно эквивалентны.

Хуже когда в цикле помимо ассертов есть хоть один съедающий переход, но и два ассерта
тоже  - тогда уже надо оставлять цикл. В таких случаях есть проблемы?

Reported by oasychev on 2014-03-17 20:52:23

[Former user]

Ну я предполагала, что развилки нужно разворачивать, как на картинке допустим, а потом
уже можно менять. Циклы тоже один переход нужно выносить, а потом менять внутри цикла
можно.
Я вот не очень понимаю, если делать мержинг в съедающий переход, то какой смысл потом
возвращаться? Если они не в том порядке, то мержинг не возможен будет. Случаи типа
такого \n$^\n все равно не смержатся. Через переход мержить не получиться.
Я вот думаю, что нельзя ли делать как делается сейчас, только, если я мержу переход
типа ассерт, который содержит оба типа ассертов, то мержить его сразу в двух направлениях?
Т.е. пусть у меня $^. При мержинге я все равно запихиваю основной ассерт в массив ассертов.
Ну так ведь можно проверять, если оба массива заполнены, то assertionsafter перекидывать
в предыдущие переходы вместе с тегами, у которых флаг AFTER, а beforeassertions перекидывать
вперед. Тогда не нужно ничего разворачивать: ни развилки, ни циклы. Тем более, что
тут явно видно, что куда. Так не пойдет?

Reported by eklepilkina on 2014-03-18 14:40:23

<hr> * Attachment: 1.png<br> * Attachment: 2.png<br>

[Oleg Sychev]

Насчет невозможности постадийного мержинга согласен.

Если я правильно понял, вы предлагаете мержить сначала ассерт1 в ассерт2, а потом при
мержинге этого ассерта2 проверять его массивы assertionsbefore/assertionsafter и мержить
отдельно (если направление не совпадает, то в предыдущий переход; если совпадает -
то в тот же, что и ассерт2 - чтобы не вводить древовидных структур). В принципе, по
идее должно сработать - на первый взгляд проблем не вижу. Надо попробовать.

Reported by oasychev on 2014-03-18 14:55:13

[Former user]

Я запустила свои кросс-тесты. И в них есть какие-то странные фейлы. Почему-то не матчится
автомат (см. b1 (b до мержинга)). Причем, я когда правила другое, у меня случайно получился
автомат access и он проходит этот тест. Я посмотрела match ^, но там ошибок не вижу.
И тесты просто для узлов со смерженными ^$ проходят. А этот тест выдает 2 фейла. Он
почему-то генерирует полное совпадение. Я не знаю, где там нужно искать ошибку.
nfa_matcher failed on regex '(?m)(^ab$\n)+' and string 'ab' (qtype_preg_cross_tests_from_pcre,
data_for_test_assertions_modifier_21):
FULL:            TRUE
LENGTH:          0=>0, 1=>-1, 
NEXT:            
LEFT:            0
expected:
FULL:            FALSE
LENGTH:          0=>2, 
NEXT:            \n
LEFT:            1

nfa_matcher failed on regex '(?m)(^ab$\n)+' and string '' (qtype_preg_cross_tests_from_pcre,
data_for_test_assertions_modifier_21):
IS_MATCH:        TRUE
FULL:            TRUE
INDEX_FIRST:     0=>0, 1=>-1, 
LENGTH:          0=>0, 1=>-1, 
NEXT:            
LEFT:            0
expected:
IS_MATCH:        FALSE
FULL:            FALSE
INDEX_FIRST:     
LENGTH:          
NEXT:            a
LEFT:            3


Очень похожие фейлы другого теста. Правда он тут видит, что совпадение нет или оно
неполное.
nfa_matcher failed on regex '(?m)(^a$\n)*' and string '
a
' (qtype_preg_cross_tests_from_pcre, data_for_test_assertions_modifier_24):
INDEX_FIRST:     0=>0, 1=>-1, 
LENGTH:          0=>0, 1=>-1, 
expected:
INDEX_FIRST:     0=>1, 
LENGTH:          0=>2, 

nfa_matcher failed on regex '(?m)(^a$\n)*' and string '' (qtype_preg_cross_tests_from_pcre,
data_for_test_assertions_modifier_24):
INDEX_FIRST:     0=>0, 1=>-1, 
LENGTH:          0=>0, 1=>-1, 
expected:
INDEX_FIRST:     
LENGTH:          

nfa_matcher failed on regex '(?m)(^a$\n)*' and string '
a
a' (qtype_preg_cross_tests_from_pcre, data_for_test_assertions_modifier_24):
INDEX_FIRST:     0=>0, 1=>-1, 
LENGTH:          0=>0, 1=>-1, 
expected:
INDEX_FIRST:     0=>1, 
LENGTH:          0=>2, 

Автоматы (a и а1)

Еще. Пояление отрицательных индексов.
nfa_matcher failed on regex '(?m)\A(^a|)b($\n)*\z' and string 'b' (qtype_preg_cross_tests_from_pcre,
data_for_test_assertions_modifier_25):
INDEX_FIRST:     0=>0, 1=>0, 2=>-1, 
LENGTH:          0=>1, 1=>0, 2=>-1, 
expected:
INDEX_FIRST:     0=>0, 
LENGTH:          0=>1, 

Автоматы s и s1

И еще в регексе (?D)\Aabc\n$a он везде генерирует, что не может. Это правильно? Просто
он наперед просматривает весь автомат и понимает, что регекс ни с чем не совпадет?

Reported by eklepilkina on 2014-03-25 07:46:28

<hr> * Attachment: b.png<br> * Attachment: b1.png<br> * Attachment: a.png<br> * Attachment: a1.png<br> * Attachment: access.png<br> * Attachment: s.png<br> * Attachment: s1.png<br>

[Oleg Sychev]

"И еще в регексе (?D)\Aabc\n$a он везде генерирует, что не может. Это правильно?" -
правильно. D - "If this modifier is set, a dollar metacharacter in the pattern matches
only at the end of the subject string. "

Остальное позже, устал уже...

Reported by oasychev on 2014-03-25 22:17:09

[Former user]

Я поправила мержинг, теперь мержится все, что возможно. Зацикливание  data_for_test_brute_force_methods_perfomance
ушло само после этих правок.

Reported by eklepilkina on 2014-04-06 14:19:28

[Former user]

Нашла тест, про который говорила. Ну почти такой как рисовала. Но проблема в нем та,
что обсуждалась.
Регекс (a(b)?)+.

Reported by eklepilkina on 2014-04-08 15:18:36

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

[Former user]

Насчет производительности. Я запускала не все тесты. У меня на виртуалке они все подтормаживают.
Запускала файл с тестами att_interpretation,там 93 небольших теста и вот тот большой
тест data_for_test_brute_force_methods_perfomance_1.
Проверяла 3 ситуации:
1. Без мержинга.
2. С мержингом.
3. С мержингом, но выполнялся потом начальный автомат. Ну т.е. 
            $t = clone $result;
            $t->merge_uncapturing_transitions(qtype_preg_fa_transition::TYPE_TRANSITION_BOTH);
            return $result;
Результаты:
а) att_interpretation
1. ======================
PASSED:     93
FAILED:     0
SKIPPED:    0
======================


Time: 6 seconds, Memory: 75.25Mb

2. ======================
PASSED:     86
FAILED:     7
SKIPPED:    0
======================


Time: 8 seconds, Memory: 74.75Mb

3. ======================
PASSED:     93
FAILED:     0
SKIPPED:    0
======================


Time: 6 seconds, Memory: 75.25Mb

б) data_for_test_brute_force_methods_perfomance_1
1. ======================
PASSED:     2
FAILED:     0
SKIPPED:    0
======================
tests with slow matcher building:
qtype_preg_cross_tests_from_att_interpretation : data_for_test_brute_force_methods_perfomance_1
======================


Time: 17 seconds, Memory: 77.00Mb

2.======================
PASSED:     1
FAILED:     1
SKIPPED:    0
======================
tests with slow matcher building:
qtype_preg_cross_tests_from_att_interpretation : data_for_test_brute_force_methods_perfomance_1
======================
tests with slow matching:
qtype_preg_cross_tests_from_att_interpretation : data_for_test_brute_force_methods_perfomance_1
======================


Time: 02:04, Memory: 100.25Mb

3. ======================
PASSED:     2
FAILED:     0
SKIPPED:    0
======================
tests with slow matcher building:
qtype_preg_cross_tests_from_att_interpretation : data_for_test_brute_force_methods_perfomance_1
======================


Time: 22 seconds, Memory: 77.00Mb

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

Reported by eklepilkina on 2014-04-08 15:42:52

[Former user]

Насчет сложности. Кол-во полученных в результате мержинга переходов будет такм. Если
в узел входит m переходов, среди них m1 незахватывающий, а справа  n переходов(без
разницы каких), то в результате получиться m1*n+(m-m1)+n переходов. Единственное, если
m == m1, эта вершина удалится и будет m1*n.

Reported by eklepilkina on 2014-04-08 16:07:13

[Former user]

Из непонятных фейлов. Дублирование результата.
fa_matcher failed on regex 'a|(b$)c' and string 'bc' (qtype_preg_cross_tests_from_preg,
data_for_test_assertions_simple_7):
INDEX_FIRST: 0=>0, 1=>0, 
LENGTH: 0=>1, 1=>1, 
expected:
INDEX_FIRST: 0=>0, 
LENGTH: 0=>1,

Reported by eklepilkina on 2014-05-06 17:09:50

<hr> * Attachment: 1.jpg

[Oleg Sychev]

Это очень даже легко понятный фейл. Значит у вас получилось так, что тег подвыражения
(b$) закрылся из-за мержинга ассерта несмотря на фейл ассерта, хотя закрыться подвыражение
должно было не после матчинга b а только после матчинга ассерта.

Reported by oasychev on 2014-05-06 20:27:38

[Former user]

Вы имеете в виду, что второй тег закрывается до \Zc? Но вы же говорили, что вынос ассертов
за теги ничего не меняет. Вот он и выносится. Я по другому не смержу с сохранением
тегов.

Reported by eklepilkina on 2014-05-07 04:55:48

[Oleg Sychev]

Ну оказывается это надо все-таки уточнить. Он не влияет по части границ совпадения,
но влияет на захват подмаски (было/не было).
А можно там тегу сказать - срабатывать до или после ассерта? Тогда должно получиться...

Reported by oasychev on 2014-05-07 15:35:48

[Former user]

Ну по идеи это сработает, но я же теги не поправлю. Там же матчинг по этому флагу нужно
править. Это опять Валеру просить? Ему и так вроде много чего делать надо...а времени
совсем мало осталось.

Reported by eklepilkina on 2014-05-07 17:29:47

[Valeriy Streltsov]

Я поправлю матчинг. На данный момент все теги в позиции BEFORE_TRANSITION считаются
отработавшими в любом случае. Это было бы верно для эпсов, но не для ассертов.

Нужно проверять, что матчатся pregnode'ы, записанные во всех тегах, привязанных к листам.
А это кстати удар по обсуждавшейся оптимизации количества тегов в ситуациях типа ($).
С точки зрения leftmost longest тег для $ не нужен, но матчить лист, записанный в этом
теге, всё равно нужно.

Кстати, во избежание дублирования информации - из transition можно выкинуть поле pregleaf.
Все теги, содержащие объект qtype_preg_leaf, нужно матчить. Согласны?

Reported by vostreltsov on 2014-05-07 17:45:15

[Valeriy Streltsov]

Гм. Логично вроде как матчить все теги (до, во время и после) перехода, но получатся
кривые частичные совпадения. Типа, если бы в примере выше доллар мёржился назад и был
бы переход b$, то переход в целом бы считался зафейленным и частичного совпадения бы
не было.

Reported by vostreltsov on 2014-05-08 07:50:16

[Oleg Sychev]

Доллар должен мержится вправо, а не влево. Так он влияет на совпадение.

Reported by oasychev on 2014-05-08 19:00:08

[Former user]

Начала вспоминать и смотреть тесты. На одном тесте видно, что \n воспринимается как
обычный символ и после него ^ не матчится, потому что на тесте 
$test1 = array( 'str'=>"\na\n",
                        'is_match'=>true,
                        'full'=>true,
                        'index_first'=>array(0=>1, 1=>1),
                        'length'=>array(0=>2, 1=>2));

дает следующий результат fa_matcher failed on regex '(?m)(^a$\n)*' and string '
a
' (qtype_preg_cross_tests_from_att_austin, data_for_test_assertions_modifier_24):
INDEX_FIRST:     0=>0, 1=>-1, 
LENGTH:          0=>0, 1=>-1, 
expected:
INDEX_FIRST:     0=>1, 
LENGTH:          0=>2, 

точно такой же результат на строке ba\n
fa_matcher failed on regex '(?m)(^a$\n)*' and string 'ba
' (qtype_preg_cross_tests_from_att_austin, data_for_test_assertions_modifier_24):
INDEX_FIRST:     0=>0, 1=>-1, 
LENGTH:          0=>0, 1=>-1, 
expected:
INDEX_FIRST:     0=>1, 
LENGTH:          0=>2, 
А если убрать \n и оставить просто a\n, то проходит, a\na\n тоже проходит
Не проходит на этом же автомате почему-то '' 
fa_matcher failed on regex '(?m)(^a$\n)*' and string '' (qtype_preg_cross_tests_from_att_austin,
data_for_test_assertions_modifier_24):
INDEX_FIRST:     0=>0, 1=>-1, 
LENGTH:          0=>0, 1=>-1, 
expected:
INDEX_FIRST:     
LENGTH:     
У меня ощущение, что ошибка именно в ^ после \n.
Автомат ниже на картинке.

Reported by eklepilkina on 2014-07-11 11:11:37

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

[Oleg Sychev]

Автомат на картинке до или после мержинга?

Reported by oasychev on 2014-07-11 13:26:32

[Former user]

После. Там \n печатается как перевод строки.

Reported by eklepilkina on 2014-07-11 16:57:51

[Oleg Sychev]

Я что-то не понял - на картинке простые ассерты не смержены вроде. А насчет \n - вы
же работали с кодом leaf_assert - проверьте, вызывается ли он (вставьте распечатку
вызовов временно) и правильно ли работает (есть ли там \n, в двойных ли кавычках и
т.д.)

Reported by oasychev on 2014-07-11 16:59:48

[Former user]

Из 4 в 2 и из 4 в 7 смерженны. Просто другие тесты проходят. Достаточно убрать первую
\n и все начинает проходить. Ну я посмотрю.

Reported by eklepilkina on 2014-07-11 17:34:32

[Former user]

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

Reported by eklepilkina on 2014-07-12 08:33:31

[Former user]

C этим тестом разобрались, остальные посмотрела, нашла проблему с последовательным мержингом
как на рис. a и a1. Там из-за повторного мержинга нарушается порядок тегов. Но это
проблема уйдет, когда будет сделан массив смерженных переходов, а не листьев, там теги
будут жестко привязаны и не сдвинутся.
Остался вроде один тест, в котором не пойму, что происходит и почему он фейлится.
автоматы b и b1 (после и до мержинга). Различий вроде нет. Теги в правильном порядке.
Фейл
fa_matcher failed on regex '(bc+d$|ef*g.|h?i(j|k))' string 'ADCDCDE' and modifiers
'i' (qtype_preg_cross_tests_from_att_austin, data_for_test_469):
NEXT:            IJ
expected:
NEXT:            [gG]

Reported by eklepilkina on 2014-07-12 13:26:50

<hr> * Attachment: a.png<br> * Attachment: a1.png<br> * Attachment: b.png<br> * Attachment: b1.png<br>

[Oleg Sychev]

Валерий, тест требует вашего внимания сразу по двум причинам
а) похоже что тут два варианта next - что если мы считаем совпадение с e по второй
ветке - g+еще один символ надо сгенерировать для точки; что если без этого по третьей
ветке можно два символа сгенерировать ij или ik. Длина сгенерированной части одинакова
- два символа. Согласны что next надо расширить?
б) в сообщении от Лены не сходится имя класса тестов и метода: класс att_austin, сам
же тест из PCRE (в austin 469 тестов просто нет) - метод правильный а класс нет - какой-то
баг в кросс-тестере, исправьте уже...

Reported by oasychev on 2014-07-16 22:25:12

[Former user]

С кросс-тестером все нормально, это я просто для удобства отладки, переносила тест.

Reported by eklepilkina on 2014-07-17 05:00:37

[Former user]

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

Reported by eklepilkina on 2014-07-24 07:07:40

[Oleg Sychev]

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

Reported by oasychev on 2014-07-24 09:11:42

[Former user]

Я не очень понимаю, почему равноценно для E есть совпадение, а в ветке h?i(j|k) нет
совпадения, совпасть может как бы только пустота, но разве она приоритетней совпадения
e? Пустота разве совпадает не только в том случае, если другого нет совпадения?

И еще. Я так понимаю, мне сейчас в преге делать нечего? С $  и ^ осталось править теги,
дописывать \b сейчас смысла нет, перенос тегов сильно затронет мой код, многое придется
переносить на другой уровень в переходы. Я не вижу смысла писать сейчас код, который
в скором времени придется переписывать.

Reported by eklepilkina on 2014-07-24 10:06:26

[Oleg Sychev]

Лена, там есть две части - совпадение (матчинг) и генерация. Причем генерация может
начинаться не с той точки, на которой закончилось совпадение, а раньше по строке -
если так выгодно (например меньше символов надо сгенерировать для завершения - чтобы
студент по подсказкам пришел кратчайшим путем к правильному ответу).
Оно ведь и дает фейл на генерации - next это следующий сгенерированный символ. А вот
с точки зрения длины сгенерированного совпадения там все равно по какой ветке идти
- см. мой коммент 138.

Относительно фронта работ - тут есть серьезные вопросы к Валерию. Вчера был релиз -
так что теперь смело можно все переписывать и ломать. Однако он в последнее время что-то
пошел по стопам Колесова - обещаний много, а дело практически стоит. :( Вот даже про
тест не отозвался... Попробую с ним еще раз поговорить, но вы и сами можете ему написать
или позвонить - может вам он честнее расскажет, вместо того чтобы "завтраками" кормить
как меня...

Reported by oasychev on 2014-07-24 12:39:18

[Valeriy Streltsov]

Поправил 469 тест

Reported by vostreltsov on 2014-07-24 20:38:49

[Former user]

Так тест то все равно при мержинге проходит неправильно, разве нет? там даже нет символьного
класса.

Reported by eklepilkina on 2014-07-25 07:17:03

[Oleg Sychev]

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

Reported by oasychev on 2014-07-25 20:41:05

[Former user]

Да все, проходит. Я просто тест поправленный не туда перенесла.

Reported by eklepilkina on 2014-07-26 05:56:33

[Former user]

Проблема явно возникающая при новой структуре. Регекс типа \n(($)^)\n. Ассерты идут
не в том порядке. Поменять их местами нельзя, получится \n((^)$)\n - ассерты уйдут
за пределы своих тегов.

Reported by eklepilkina on 2014-09-04 17:22:48

[Former user]

Олег Александрович, Вы просили файл с текущими фейлами. Прикрепляю его сюда, там комментариями
у каждого теста написано, что я могу сказать об этих фейлах.У тех тестов, у которых
нет комментариев падают и без мержинга. В моих тестах неправильно работают 3 теста,
но они на откаты, которых нет пока.

Reported by eklepilkina on 2014-10-30 18:26:38

<hr> * Attachment: 3

[Oleg Sychev]

№148 - видимо теги тоже должны учитывать те цифирки по порядку выполнения о которых
мы говорили на последней встрече (Валерий, обратите внимание)
#149 - 
Лена - на тесты с ленивыми квантификаторами без ассертов пока внимания не обращаем,
это не ваша проблема
data_for_test_anchors_1 - тут вроде все нормально: многострочный режим не включен (см.
теги) - никаких переводов строки там нет, так что регекс работает в однострочном режиме
и совпасть может с пустой строкой (только). На пустой строке ^ и $ должны работать
при любом порядке по идее. Так что надо смотреть проблему в генерации - почему она
не видит возможности совпадения пустой строки а выдает невозможность генерации вместо
этого. Скорее всего надо дописывать случай пустого совпадения в next для ассертов.

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

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

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

data_for_test_26 - Валерий, не объясните смысл таких next и left? Вообще при откатах
нам надо как-то договориться, с какой позиции считать left...

data_for_test_136 - Валерий, тоже кривой тест? Там ведь реально достаточно взять 11
символов и обрезать строку, ибо точка под [^k] подходит и зачем генерировать ее?

data_for_test_505 - Лена, посмотрите какой именно переход автомата генерирует невозможность.

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

Reported by oasychev on 2014-11-03 23:45:51

[Oleg Sychev]

data_for_test_assertions_simple_9 - сорри, тест как раз верный. Лена - как оно там может
смерженное с "с" давать символ при генерации если слева отнюдь не перевод строки?

Reported by oasychev on 2014-11-04 20:47:31

[Valeriy Streltsov]

data_for_test_26 и data_for_test_136 - можно сделать left 0. Там будет полное совпадение
если удалять символы справа.

Reported by vostreltsov on 2014-11-04 20:56:50

[Former user]

data_for_test_assertions_simple_9 я просто в самом фейле перепутала, что ожидалось,
а что выдал тест. Я поправила.

Reported by eklepilkina on 2014-11-05 05:23:51

[Former user]

Насчет fa_matcher failed on regex '$()^\1' and string 'faily days' (qtype_preg_cross_tests_from_att_austin,
data_for_test_anchors_1):
LEFT:            999999999
expected:
LEFT:            0

Я немного не поняла, т.к. тут однострочный режим $ заменяется \Z, который совпадает
только в конце данных(ну или перед последним \n, но тут не этот случай). С пустой строкой
в чистом виде этот регекс совпадает все правильно. А с faily days \Z дает фейл. Или
Вы хотите, чтобы было условие, если однострочный режим и переход \Z\A, то совпадает
в любом случае?

Reported by eklepilkina on 2014-11-05 05:41:34

[Oleg Sychev]

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

Reported by oasychev on 2014-11-05 21:56:49

[Former user]

Насчет data_for_test_anchors_1. Там при генерации в позиции 0 выдается пустая строка
array(2) {
  [0] =>
  int(1)
  [1] =>
  class qtype_poasquestion_string#12890 (2) {
    private $fstring =>
    string(0) ""
    private $flength =>
    int(0)
  }
}
Но он не останавливается, а проходит до 10 позиции, и на них фейлится. Результат на
них логично такой,по идеи он должен был остановиться или нет?
array(2) {
  [0] =>
  int(2)
  [1] =>
  NULL
}

Reported by eklepilkina on 2014-11-06 16:55:51

[Former user]

data_for_test_backrefs_7. Я так понимаю, что он не генерирует пустоту, т.к. эта пустота
смержилась(см. рисунок). Этот переход просто не совпал, видимо,и генерация идет по
верхней ветке.

Reported by eklepilkina on 2014-11-06 17:13:31

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

[Former user]

Провал из-за последнего перехода. 42->43[label = "o:7, \Z c:7,0,", color = violet, penwidth
= 2];array(2) {
  [0] =>
  int(4)
  [1] =>
  NULL
}

\Z генерирует NEXT_CHAR_END_HERE, а не то, что он не может генерировать.

Reported by eklepilkina on 2014-11-06 17:30:53

[Former user]

data_for_test_656 тут скорее всего пустой смержился со следующим и за счет этого пустой
переход не совпадает (1->6)

Reported by eklepilkina on 2014-11-06 18:15:44

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

[Former user]

По времени, с мержингом проходит почти в 2 раза медленнее. Без мержинга  - Time: 1.31
minutes. С мержингом - Time: 2.57 minutes.

Reported by eklepilkina on 2014-11-06 18:31:29

[Oleg Sychev]

#156 - до какой "десятой позиции" он проходит при ГЕНЕРАЦИИ? это при совпадении он по
строке проходить может. А при генерации он по идее должен увидеть что по пустоте сразу
в конечное состояние попадает и все. У вас этот переход сохранился или куда делся при
мержинге? Бывает, ведь, что и пустоту некуда мержить по той простой причине что ни
слева ни справа ничего нет (примерно как крышку в начале или доллар в конце).

#157 - Лена, посмотрите внимательно на смержененный автомат вы не находите что он странный
и кривой? В оригинальном регексе пустота закорачивала только одну букву - "s" - в смерженном
почему-то две "ts". Как такое могло получиться? Глюки, имхо исправлять надо...

#158 - это про какой тест было?

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

Reported by oasychev on 2014-11-06 21:46:26

[Oleg Sychev]

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

Если есть возможность выделять цветом или как-то еще теги и/или наоборот сами символы
чтобы легче читались - еще лучше...

Reported by oasychev on 2014-11-06 21:49:56

[Former user]

#156 - до 10 позиции он двигается по строке. Это та позиция, которая передается в next_character.

#157 - не кажется, там все правильно. Посмотрите рисунок без мержинга(прикрепленный
файл). Эпсилон мержится с t, а еще остается путь через ts. там даже по тегам все праильно.

#158 - data_for_test_505

Reported by eklepilkina on 2014-11-07 07:01:32

<hr> * Attachment: 7w.png<br>

[Oleg Sychev]

#156 - Валерий, там откат к самому началу происходит по текущим правилам?

#157 - а, вижу - надо все-таки хотя бы перевод строки между смерженными переходами
вставлять при вывод в dot, а то совсем плохо читаются. Но тогда почему при генерации
она идет длинным путем 10-12-16 вместо прямого 10-16? Что генерирует переход 10-16?

#158 - там вроде это последний переход в автомате должен быть (\Z же вправо мержится?),
если так то NEXT_CHAR_END_HERE должно быть нормально. Валерий, как реагирует автомат
на такую генерацию в последнем переходе? Или не последнем, но за которым нет символов?

Reported by oasychev on 2014-11-07 10:12:50

[Former user]

Олег Александрович, Вы просили посмотреть тесты. я посмотрела, там осталось 11, из тех,
что писались под мержинг. Если подключить мержинг во всех тестах падают еще где-то
20. В основном там теги не там стоят,где должны. И еще много падает условных. Ну там
еще есть с исключениями тесты. Но там та же проблема с расстановками тегов. То, что
смогла поправила. Остальное, не знаю.

Reported by eklepilkina on 2014-12-29 19:12:50

[Former user]

С мержингом условных много фейлов достаточно. Вот такой фейл.
fa_matcher failed on regex '^(a(?(1)\1)){4}$' and string 'aaaaaaaaaa' (qtype_preg_cross_tests_from_pcre_testinput1,
data_for_test_516):
FULL:            FALSE
INDEX_FIRST:     0=>0, 1=>0, 
LENGTH:          0=>1, 1=>1, 
expected:
FULL:            TRUE
INDEX_FIRST:     0=>0, 1=>6, 
LENGTH:          0=>10, 1=>4, 

Автоматы исходный и смерженный.

Reported by eklepilkina on 2015-01-22 08:22:40

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

[Valeriy Streltsov]

Если я правильно понял, в смерженном автомате в главном переходе 2-12 лишний закрывающий
тег 3 - это первое подвыражение. Оно же не закрывается после захвата "a". Поэтому там
фейлится смерженное условие !(1) и так далее.

Reported by vostreltsov on 2015-01-29 13:43:03

[Former user]

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

Reported by eklepilkina on 2015-01-30 07:15:37

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

[Valeriy Streltsov]

Может, стоит вызывать мержинг после склеивания автоматов? запомнить состояние-границу
автоматов-операндов по идее нетрудно. Что думаешь, Лен?

Reported by vostreltsov on 2015-02-03 12:37:58

[Oleg Sychev]

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

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

Reported by oasychev on 2015-02-05 00:15:17

[Former user]

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

Reported by eklepilkina on 2015-02-05 05:49:59

[Oleg Sychev]

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

Reported by oasychev on 2015-02-05 18:17:40

[Former user]

Вообщем, я ошиблась насчет обратных ссылок, там все нормально, фейлы видимо были из-за
того, что остались какие-то эксперименты в папке на локальном хосте. Я вытянула заново
реп с сервера, нет тех 4 фейлов.
Мне тогда надо завтра приходить?

Reported by eklepilkina on 2015-02-10 18:49:40

[Oleg Sychev]

Если по простым ассертам (включая \b) есть фейлы, которые не связаны с условными подмасками
- то надо, давайте их решать.

Reported by oasychev on 2015-02-10 19:01:17

[Valeriy Streltsov]

516 фиксед

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

[Oleg Sychev]

Лена, прошу протестить еще раз и отписаться, есть ли проблемы здесь и в 232.

Reported by oasychev on 2015-02-12 20:56:30

[Former user]

Вообщем на текущий момент 6 очень странных фейлов, автоматы идентичны, там очень простой
мержинг, Валере я отправила несколько и тут пример ниже. +2 фейла, связанных с последним
коммитом: один я попробую исправить сегодня-завтра, второй на частичное совпадение,
получается так, что там зависит правильность от того, куда пойдет смерженный эпсилон,
что странно вообще-то. Ну и из моего файла 4 фейла, я их тоже постараюсь поправить
в ближайшие дни.
Насчет последнего коммита я не очень уверена, теперь получается, что в конце могут
остаться несмерженные эпсилоны. Но я сегодня полдня эксперементировала, никак не получается
достичь тех показателей, что с помощью последней правки для условных и рекурсии.

Reported by eklepilkina on 2015-02-13 16:23:01

<hr> * Attachment: fa.svg * Attachment: fa1.svg

[Former user]

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

Reported by eklepilkina on 2015-02-13 16:31:08

[Valeriy Streltsov]

qtype_preg_cross_tests_from_pcre_testinput1, data_for_test_822 в целом понятный
вот рекурсивное подвыражение раньше заканчивалось допустим переходом 6-10, обратная
ссылка. сейчас в него смержен \Z, поэтому во всех рекурсиях оно проверяет и его, и
естественно фейлится. я подумаю как этого избежать. пока в голову приходит только запоминать
начальные переходы вместо состояний (как я уже мноооого раз предлагал), и делать во
время рекурсии условия остановки матчинга смерженных переходов при достижении конечного
перехода.

Reported by vostreltsov on 2015-02-19 20:04:33

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

[Valeriy Streltsov]

Ок, -3 фейла, пофиксил подобные ситуации.

Reported by vostreltsov on 2015-02-21 13:54:47

[Valeriy Streltsov]

Ну что, fixed?

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

[Oleg Sychev]

Разберемся с выводом ошибки разрыва автомата - и fixed...

Reported by oasychev on 2015-03-08 02:26:23

[Oleg Sychev]

Не совсем fixed оказывается. В future_cross_tests есть изрядное количество тестов связанных
с этими ассертами, их надо перенести в обычные файлы и убедиться что они теперь проходят.

Reported by oasychev on 2015-03-08 13:16:46

[Former user]

future_cross_tests уже давно нет, я туда изначально писала свои тесты, потом этот файл
переименовали в preg_merging. У меня нет future_cross_tests в репозитории.
https://code.google.com/r/eklepilkina-preg-intersection/source/browse#hg%2Fquestion%2Ftype%2Fpreg%2Ftests

Reported by eklepilkina on 2015-03-08 17:45:37

[Oleg Sychev]

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

Reported by oasychev on 2015-03-08 20:39:40

[Oleg Sychev]

На самом деле это немалое достижение. Поздравляю!

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