Пересчение автоматов

[Former user]

Originally reported on Google Code with ID 328

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

Reported by eklepilkina on 2015-02-09 08:02:40

[Oleg Sychev]

Можно в отдельном клоне, но только если с остальными проблемами простой. Не забывайте
напоминать Валере.

Нам перед релизом надо как можно чаще смотреть фейлы вместе. +4 фейла от обратных ссылок
в частности, и \b которые. Я в среду после занятий Насте назначил, вы сможете подойти?
Посмотрим имеющиеся фейлы, разберемся кто виноват...

Reported by oasychev on 2015-02-09 23:46:29

[Oleg Sychev]

Можно в отдельном клоне, но только если с остальными проблемами простой. Не забывайте
напоминать Валере.

Нам перед релизом надо как можно чаще смотреть фейлы вместе. +4 фейла от обратных ссылок
в частности, и \b которые. Я в среду после занятий Насте назначил, вы сможете подойти?
Посмотрим имеющиеся фейлы, разберемся кто виноват...

Reported by oasychev on 2015-02-09 23:46:29

[Former user]

Ну если надо, подойду.

Reported by eklepilkina on 2015-02-10 08:30:13

[Former user]

Я начала вспоминать, и у меня возникли вопросы:
1) у меня сейчас что-то не очень складывается связь между сложными утверждениями и
пересечением автоматов. Само утверждение будет представляться отдельным автоматом?
То какой смысл пересекать, если они идут последовательно? на КНПО я как бы работала
в основном с автоматами и о регулярных выражениях задумывалась мало. Сейчас у меня
картинка не складывается
2)Нужно начинать с восстановления старых тестов? Простейшие то работают и сейчас, а
вот для проверки работы тегов и изменившейся структуры ассертов надо переписывать функцию
считывания.
3) Написание кросс-тестов. Я так понимаю тоже надо, т.к. они лучше всего показывают
все проблемы, значительно лучше простых юнит-тестов.
Вообщем вопрос с чего начинать?

Reported by eklepilkina on 2015-02-22 14:45:30

[Oleg Sychev]

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

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

Примеры а...в нам еще и на защите в любом случае понадобятся очень.

Reported by oasychev on 2015-02-22 16:43:01

[Former user]

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

Reported by eklepilkina on 2015-02-22 18:13:19

[Oleg Sychev]

И вот те четыре теста, о которых я говорил а)--г) как кросс-тесты составить - к встрече
через неделю...  Там первые три как раз помогут нам начать готовить сам доклад/пояснительную
записку к диплому...

Reported by oasychev on 2015-02-22 18:41:55

[Former user]

Я начала писать кросс-тесты на пункты a)-в) пока все только на вперед смотрящие позитивные.
Вы можете посмотреть хотя бы по одному тесту? Я правильно поняла?
Вытолкнула в клон https://code.google.com/r/eklepilkina-complex-assertions/.

Reported by eklepilkina on 2015-02-27 16:41:20

[Oleg Sychev]

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

Reported by oasychev on 2015-02-28 20:38:55

[Former user]

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

Reported by eklepilkina on 2015-03-29 14:21:41

[Oleg Sychev]

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

Добавочные кросс-тесты можно построить на основе тех же регексов, что использовались
в функциональных тестах на НКПО, но сделать много строк с проверкой чтобы на каждом
пересеченном шаге проходили нужные символы и только они. В этом смысле сравнение автоматов
все же требует куда меньше проверок, чем сравнение кросс-тестами с детальной проверкой,
совпадает с какими надо строками или где-то ошибки. Но для начала надо в аццептинге
разблокировать эти виды утверждений (если включен мержинг простых конечно) и проверить
имеющиеся юнит-тесты от PCRE с ними - пройдут или что-нибудь накроется? Частичные совпадения
конечно будут различаться, т.к. PCRE ошибку сообщает в месте ассерта; эти можно и отредактировать.
Но полные должны совпасть.

Reported by oasychev on 2015-03-29 21:06:57

[Former user]

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

Reported by eklepilkina on 2015-04-02 18:39:24

[Oleg Sychev]

Ну по большому счету не имеет. Но вот с точки зрения тестирования (проверочка типа "за
пределами 0 тегов consumeschars = false, внутри - наоборот) - может иметь, подумайте...

Reported by oasychev on 2015-04-02 19:16:22

[Former user]

(a|)*(?=(b[cd]+)|)(?<=(a*b[cl])|$). Попробовала такое регулярное выражение в стандартном
матчере. Ругается на * в назад смотрящем "* Lookbehinds need to be zero-width, thus
quantifiers are not allowed". У нас так же должно работать?

Reported by eklepilkina on 2015-04-07 12:18:13

[Former user]

И еще не пойму, почему вот этот регекс (?m)a(?=$)$[bc\n]^(?<=^) не дает в стандарте
совпадения со строкой "a\n"

Reported by eklepilkina on 2015-04-07 12:25:59

[Former user]

А все последнее поняла

Reported by eklepilkina on 2015-04-07 12:27:51

[Oleg Sychev]

14 - не, это недостаток PCRE

Reported by oasychev on 2015-04-09 15:24:51

[Former user]

Текущие вопросы:
1. accept не знает о том, включен мержинг или нет, ему такой параметр в отличие от
методов построения не передается.
2. Карту с состояниями для пересечения я, наверное, сделаю как поле автомата, чтобы
не таскать по всем функциям еще один параметр. И в карту еще надо будет добавить направление
пересечения. Плюс хранить как характеристику автомата карту с ассертами будет правильней
для сложных ассертов внутри ассертов. Типо такого(?=a(?=b)b)ab.

Reported by eklepilkina on 2015-04-13 16:10:01

[Former user]

А ну еще карта должна быть многомерной, потому что у одного состояния может быть несколько
автоматов.ab(?<=ab)(?=cd)cd

Reported by eklepilkina on 2015-04-13 16:50:02

[Oleg Sychev]

Про аццептинг создать на меня (с owner мной) отдельное issue чтобы не забыл - сделаю
как только дойдут руки от совсем уже срочных дел. Остальное согласен.

Reported by oasychev on 2015-04-13 20:48:29

[Former user]

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

Reported by eklepilkina on 2015-04-14 04:32:54

[Former user]

И еще насчет цикла в одном автомате. Я начала разбираться. Посмотрите первый пример
(t1, t2, t5)пересекается вперед, начиная с вершины 1. Во-первых, тут получается, что
при пересечении опять попадаем в ветку с ассертом, нужно еще раз начинать пересекать?
Во-вторых, по моему тут тоже неправильно с циклом. По идеи вместо перехода 1,9 6 3
0->3,7 4 1, он должен вести в 1,0. И тут предложенная вчера логика не сработает, потому
что там предлагалось искать вершину 1,.
Во втором примере (t3, t4, t6) вообще добавляется вершина, чтобы зациклить, но это
пересечение назад. Я немного запуталась, но по моему, там тоже цикл должен идти не
так.

Reported by eklepilkina on 2015-04-14 06:25:47

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

[Oleg Sychev]

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

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

Примеры посмотрю чуть позже.

Reported by oasychev on 2015-04-15 17:16:14

[Former user]

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

Reported by eklepilkina on 2015-04-15 17:48:43

[Oleg Sychev]

Начальные и конечные должны быть в любом автомате (в том числе скорее всего и в частичных,
которые создаются на стеке - и в автоматах ассерта тоже). Их роль другая, чем у тегов.
Они не могут определяться по тегам. Иначе даже \b в самом начале создаст переход левее
открывающего 0-тега - и что, этот переход не будет выполняться что-ли, потому что 0-тег
стоит после него? Это глюки будут.

Попробуйте регекс типа \babc и строки вида xabc - они дадут фейл? Если дадут, значит
переход который \W, расположенный левее 0-тега выполнился и значит начальным считается
состояние слева от него, а не то, которое перед 0-тегов.
А если не будет фейла - то это глюк, который надо фиксить.

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

Reported by oasychev on 2015-04-15 17:57:08

[Oleg Sychev]

Лена, что значит конкретно "определяются по тегам"? Каким образом? Работает вроде нормально,
так что это явно не состояние непосредственно перед переходом с 0-тегом.

Reported by oasychev on 2015-04-15 18:23:09

[Former user]

Без мержинга?
https://code.google.com/r/eklepilkina-preg-intersection/source/browse/question/type/preg/fa_matcher/fa_matcher.php#1107
Вот функция, в которой устанавливаются начальные и конечные состояния.
А вот она сама https://code.google.com/r/eklepilkina-preg-intersection/source/browse/question/type/preg/preg_fa.php#770.

Reported by eklepilkina on 2015-04-15 18:34:54

[Former user]

Начальные и конечные сделала. Все строится.

Reported by eklepilkina on 2015-04-21 07:38:02

[Former user]

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

Reported by eklepilkina on 2015-04-28 08:22:59

<hr> * Attachment: IMG.jpg

[Former user]

И я думаю делать это последовательно, а не пытаться пересекать n автоматов параллельно.

Reported by eklepilkina on 2015-04-28 08:29:03

[Former user]

И еще, т.к. работы много, то что я должна сделать.
1. Адаптировать код, чтобы работал пропуск ^, $, eps, когда они в начале или в конце.(у
меня пока таких тестов не было, так что ничего не падало на это).
2. Тестирую вперед смотрящие на более длинных и сложных примерах, отлаживаю их.
3. Меняю алгоритм, так чтобы можно было задавать не одну вершину для начала пересечения,
а n (для поддержки \b).
4. Переделываю начальные и конечные состояния для подвыражений.
5. Поддержка назад смотрящих. 
6. Тестирование вперед+назад смотрящих.
7. Проверка и отладка вложенных ассертов.
8. Переписываю код для циклов, которые короче ассертов(то, что в комментах выше).
9. Поддержка рекурсии.

В таком порядке делаю же, чтобы простое все пораньше было работоспособным? а то я не
знаю, за что хвататься.

Reported by eklepilkina on 2015-04-28 08:37:22

[Former user]

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

Reported by eklepilkina on 2015-04-28 08:45:42

[Oleg Sychev]

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

Кроме того, я думаю пункты 7 и 8 точно в приоритетах неверно стоят. Пункт 4 желательно
согласовать с Валерой - когда он сможет оперативно сделать свою часть; там работы чуть
и если Валерий может сейчас - то тянуть с ним не стоит.

Reported by oasychev on 2015-04-29 00:06:21

[Former user]

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

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

[Former user]

Случайно нашла следующую проблему. При создании вопроса, если указывать точное совпадение,
то автоматически добавляется ^ и $. Причем к основному автомату сразу. И получается,
что нельзя задавать утверждения, где остается хвост. Самое простое a(?=b) превращается
в ^a(?=b)$, которое ни с чем совпасть не может.

Reported by eklepilkina on 2015-05-10 16:12:05

[Former user]

Еще проблема, никак не могу почему фейлы наблюдаются на вроде корректном автомате. Все
теги вроде так. Если убрать из пересеченных теги, то падающие тесты начинают проходить,
значит, проблема где-то там.
Результирующий, первый и второй автоматы на картинках.
Фейлы.
fa_matcher failed on regex 'a(?=b*)(\w?)*' and string 'ab' (qtype_preg_cross_tests_from_preg_intersection,
data_for_test_assertions_lookahead_8), merging is on:
INDEX_FIRST:     0=>0, 1=>1, 
LENGTH:          0=>2, 1=>1, 
expected:
INDEX_FIRST:     0=>0, 1=>2, 
LENGTH:          0=>2, 1=>0, 

fa_matcher failed on regex 'a(?=b*)(\w?)*' and string 'a' (qtype_preg_cross_tests_from_preg_intersection,
data_for_test_assertions_lookahead_8), merging is on:
INDEX_FIRST:     0=>0, 1=>-1, 
LENGTH:          0=>1, 1=>-1, 
expected:
INDEX_FIRST:     0=>0, 1=>1, 
LENGTH:          0=>1, 1=>0, 

Reported by eklepilkina on 2015-05-11 15:11:15

<hr> * Attachment: fa_1.svg * Attachment: fa_2.svg * Attachment: fa_3.svg

[Former user]

Первый фейл ушел. Второй остался.

Reported by eklepilkina on 2015-05-15 16:09:14

[Former user]

Такой еще вопрос при генерации должны генерироваться символы из утверждения? Вот например
тест. Тест правильный? Или генерация так и должна работать?
fa_matcher failed on regex '(?<=ab)cd' and string 'cd' (qtype_preg_cross_tests_from_preg_intersection,
data_for_test_assertions_lookbehind_3), merging is on:
NEXT:            cd
FULL STR:        abcd
expected:
NEXT:            a

Reported by eklepilkina on 2015-05-15 16:17:12

[Oleg Sychev]

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

А как работает генерация для варианта типа \b! ? Она тоже должна сначала символ слова
сгененрировать если не многострочный режим.

Reported by oasychev on 2015-05-15 16:45:05

[Former user]

С \b в начале тоже с генерацией плохо.Хотя вот FULL STR он правильно пишет во всех случаях.

Reported by eklepilkina on 2015-05-15 18:17:36

[Former user]

Вообщем я не знаю, что там не так при генерации хвостов. FULL STR и LEFT правильно определяется.
next character вызывается для незахватывающего перехода и дает правильный результат.
Причем "!\b" работает нормально на "!"
NEXT:            0
LEFT:            1
FULL STR:        !0
Т.е. проблемы только с начальными хвостами.

Reported by eklepilkina on 2015-05-16 07:31:57

[Former user]

Еще вопрос. А частичное совпадение считается для незахватывающих переходов?
(?m)^(?<=a\n)d на строке ad должен дать частичное? или нет, потому что там 0 длина?
Валера считает что второй вариант. но тогда как-то странно придется генерировать символ,
который уже был введен заново.

Reported by eklepilkina on 2015-05-16 08:08:33

[Former user]

Непонятный для меня фейл. Автомат простейший.
fa_matcher failed on regex 'b(a|c)$(?<=b[ac])' and string 'bac' (qtype_preg_cross_tests_from_preg_intersection,
data_for_test_assertions_lookbehind_16), merging is on:
INDEX_FIRST:     0=>0, 1=>-1, 
LENGTH:          0=>1, 1=>-1, 
LEFT:            999999999
expected:
INDEX_FIRST:     0=>0, 1=>1, 
LENGTH:          0=>2, 1=>1, 
LEFT:            0

Reported by eklepilkina on 2015-05-17 16:43:56

<hr> * Attachment: fa_1.svg * Attachment: fa_2.svg * Attachment: fa_3.svg

[Former user]

Еще есть вполне логичные фейлы на захват пустых подвыражений при частичном совпадении.
Пустота мержится в предыдущий переход до ассерта, и поэтому выдает совпадение, когда
ассерт фейлится.
Например
fa_matcher failed on regex 'a(?=b)(\w?)*' and string 'a' (qtype_preg_cross_tests_from_preg_intersection,
data_for_test_assertions_lookahead_7), merging is on:
INDEX_FIRST:     0=>0, 1=>1, 
LENGTH:          0=>1, 1=>0, 
expected:
INDEX_FIRST:     0=>0, 
LENGTH:          0=>1,

fa_matcher failed on regex 'a(?=[b-d])(|\s)(?<=[a-z])' and string 'az' (qtype_preg_cross_tests_from_preg_intersection,
data_for_test_both_assertions_2), merging is on:
INDEX_FIRST:     0=>0, 1=>1, 
LENGTH:          0=>1, 1=>0, 
expected:
INDEX_FIRST:     0=>0, 
LENGTH:          0=>1,

Reported by eklepilkina on 2015-05-18 15:52:58

[Former user]

Я посмотрела, что там конкретно генерируется в тестах с незахватывающими переходами
в начале. Вот пример (?<=[a-k][a-z])(?<=[a-d][c-x])[d-y][x-z].
Фейл fa_matcher failed on regex '(?<=[a-k][a-z])(?<=[a-d][c-x])[d-y][x-z]' and string
'aayy' (qtype_preg_cross_tests_from_preg_intersection, data_for_test_assertions_lookbehind_start),
merging is on:
NEXT:            yy
FULL STR:        acyy
expected:
NEXT:            c
Выдает следующие результаты.
class qtype_preg_matching_results#13049 (9) {
  public $full =>
  bool(false)
  public $indexfirst =>
  array(1) {
    [0] =>
    int(-1)
  }
  public $length =>
  array(1) {
    [0] =>
    int(-1)
  }
  public $left =>
  int(3)
  public $extendedmatch =>
  class qtype_preg_matching_results#13069 (9) {
    public $full =>
    bool(true)
    public $indexfirst =>
    array(2) {
      [-2] =>
      int(-1)
      [0] =>
      int(2)
    }
    public $length =>
    array(2) {
      [-2] =>
      int(-1)
      [0] =>
      int(2)
    }
    public $left =>
    int(0)
    public $extendedmatch =>
    NULL
    public $extensionstart =>
    int(2)
    protected $str =>
    class qtype_poasquestion\string#13062 (2) {
      private $fstring =>
      string(4) "acyy"
      private $flength =>
      int(4)
    }
    protected $maxsubexpr =>
    int(0)
    protected $subexprmap =>
    array(0) {
    }
  }
  public $extensionstart =>
  int(-1)
  protected $str =>
  class qtype_poasquestion\string#13097 (2) {
    private $fstring =>
    string(4) "aayy"
    private $flength =>
    int(4)
  }
  protected $maxsubexpr =>
  int(0)
  protected $subexprmap =>
  array(0) {
  }
}

В extendedmatch там indexfirst 2 для 0 тега, что правильно в принципе, и еще extensionstart
какой-то тоже 2.

Reported by eklepilkina on 2015-05-22 10:19:13

[Former user]

Пометки для себя:
1. Незахватывающие хвосты автомата утверждения пересекать в другую сторону
2. Незахватывающие хвосты основного автомата при повторном пересечении пропускать
3. Перенести мержинг в класс автомата, и дописать мержинг и после построения автомата
для ситуаций, когда ассертов много.
4. Одиночный \b развернуть.

Reported by eklepilkina on 2015-05-22 10:56:43

[Former user]

Reported by eklepilkina on 2015-05-25 15:19:17

<hr> * Attachment: preg_matcher.php

[Valeriy Streltsov]

Фейлов не прибавилось, вытолкнул

Reported by vostreltsov on 2015-05-25 15:58:14

[Former user]

У меня на данный момент очень много вопросов по тестам.

1. Из-за мержинга назад пустота совпадает до утверждения хотя должна после
Пример.
fa_matcher failed on regex 'a(?=b)(\w?)*' and string 'a' (qtype_preg_cross_tests_from_preg_intersection,
data_for_test_assertions_lookahead_7), merging is on:
INDEX_FIRST:     0=>0, 1=>1, 
LENGTH:          0=>1, 1=>0, 
expected:
INDEX_FIRST:     0=>0, 
LENGTH:          0=>1, 


2. Проблемы с $. Вроде строятся правильные автоматы 16 и 17 картинка соответственно
для 16 и 17 теста, а тесты падают.
fa_matcher failed on regex 'b(a|c)$(?<=b[ac])' and string 'bac' (qtype_preg_cross_tests_from_preg_intersection,
data_for_test_assertions_lookbehind_16), merging is on:
INDEX_FIRST:     0=>0, 1=>-1, 
LENGTH:          0=>1, 1=>-1, 
LEFT:            999999999
expected:
INDEX_FIRST:     0=>0, 1=>1, 
LENGTH:          0=>2, 1=>1, 
LEFT:            0

fa_matcher failed on regex 'b(a|c$)(?<=b[ac]$)' and string 'bca' (qtype_preg_cross_tests_from_preg_intersection,
data_for_test_assertions_lookbehind_17), merging is on:
LENGTH:          0=>1, 1=>-1, 
NEXT:            a
LEFT:            1
FULL STR:        ba
expected:
LENGTH:          0=>2, 
NEXT:            -1
LEFT:            0

3. Судя по всему не находится совпадение с незахватывающими переходами в начале. Автомат
картинка 20
fa_matcher failed on regex '(?m)^(?<=a\n)d' and string 'ad' (qtype_preg_cross_tests_from_preg_intersection,
data_for_test_assertions_lookbehind_20), merging is on:
IS_MATCH:        FALSE
INDEX_FIRST:     0=>-1, 
LENGTH:          0=>-1, 
expected:
IS_MATCH:        TRUE
INDEX_FIRST:     0=>0, 
LENGTH:          0=>1, 

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

Reported by eklepilkina on 2015-05-29 16:20:23

<hr> * Attachment: 16_1.svg * Attachment: 17.svg * Attachment: 20.svg

[Valeriy Streltsov]

Лен, то что картинки вроде правильные не значит что вся структура данных правильная.
Помнишь случай с minopentag? Там есть еще куча полей, проверь сначала что все там выставляется
корректно. Глянь на комменты к полям в классе перехода, а потом оцени в каких местах
и как их нужно вычислять.

Ты можешь также раскомментировать echo в матчере, посмотреть что там происходит.

Остальное постараюсь глянуть завтра-послезавтра.

Reported by vostreltsov on 2015-05-29 19:39:56

[Former user]

Еще странный фейл. Один почему-то не находит подвыражение со \b. Тег там 6 за это подвыражение
отвечает и стоит правильно. Единственное minopentag стоит с номером 1, потому что как
раз пересекаются переходы из 2 подвыражений.
Что там можно посмотреть, что не так?

Reported by eklepilkina on 2015-06-04 09:43:05

<hr> * Attachment: fa_1.svg * Attachment: fa_2.svg * Attachment: fa_4.svg

[Former user]

Ой, сам фейл вот. fa_matcher failed on regex 'a(b|=)(?=(\b|.)[!c]d)c[cd]d' and string
'a=cdd' (qtype_preg_cross_tests_from_preg_intersection, data_for_test_assertions_lookahead_35),
merging is on:
INDEX_FIRST:     0=>0, 1=>1, 2=>-1, 
LENGTH:          0=>5, 1=>1, 2=>-1, 
expected:
INDEX_FIRST:     0=>0, 1=>1, 2=>2, 
LENGTH:          0=>5, 1=>1, 2=>0, 

Reported by eklepilkina on 2015-06-04 09:43:31

[Former user]

Еще проблема. a(?=b[!e](\b|.))be(=|t) на строке abe=. В стандарте у первого подвыражения
длина 0, а прег выбирает другой путь где длина у первого подвыражения 1.
Автомат на картинке.
Фейл.
fa_matcher failed on regex 'a(?=b[!e](\b|.))be(=|t)' and string 'abe=' (qtype_preg_cross_tests_from_preg_intersection,
data_for_test_assertions_lookahead_34), merging is on:
LENGTH:          0=>4, 1=>1, 2=>1, 
expected:
LENGTH:          0=>4, 1=>0, 2=>1,

Reported by eklepilkina on 2015-06-04 09:57:50

<hr> * Attachment: fa_1.svg

[Former user]

Аналогичные фейлы и с назад смотрящими с \b на краю.

Reported by eklepilkina on 2015-06-05 15:03:56

[Former user]

1. Почему-то кое-где при ассертах матчинг идет по короткому пути, а не по длинному.
Например, тест data_for_test_assertions_lookahead_8, автомат там большой, смысла, наверное
нет прикладывать. Если поставить в конце $ захватывает как надо.
2. Следующая проблема https://code.google.com/p/oasychev-moodle-plugins/issues/detail?id=328#c51
https://code.google.com/p/oasychev-moodle-plugins/issues/detail?id=328#c52
3. И вопрос такой с циклами, важно ли построение так как оно сейчас происходит?

Reported by eklepilkina on 2015-06-08 15:58:34

[Valeriy Streltsov]

Лен, осталась еще пара странных фейлов. _36 это список фейлов в "стабильной версии",
без пересечений.

data_for_test_subexpr_tricky не должен фейлиться

data_for_test_222 раньше не фейлился, но там ленивые квантификаторы, это не так критично

Все фейлы, где есть DEFINE - это нормально, не обращай внимания.

Reported by vostreltsov on 2015-06-09 07:19:28

<hr> * Attachment: test_all_36 * Attachment: test_all

[Former user]

Возникла ОЧЕНЬ большая проблема с наличием только ассерта внутри цикла или ?. Например,(?<=(abc))?xyz.
В голову не идет ни одно универсальное решение.

Reported by eklepilkina on 2015-06-09 12:52:23

[Oleg Sychev]

А что за очень большая проблема? По идее любой цикл не допускающий 0 совпадений с только
ассертом внутри можно удалить, а цикл допускающий 0 совпадений свести к ?

? означает прокинутый эпсилон мимо ассерта. И что именно за проблема?

Reported by oasychev on 2015-06-09 15:47:35

[Former user]

Я не знаю, как сделать автомат для регекса типо такого (?<=(abc))?xyz. Основной автомат
получается x->y->z. И начинается пересечение назад с 0 состояния. Оно достраивается,
но надо еще весь ассерт охватить пустым переходом от ? причем с правильными тегами.
Изначально этот пустой переход смержился. И это простой случай. А можно накрутить очень
сильно подобные регексы.

Reported by eklepilkina on 2015-06-09 15:52:24

[Valeriy Streltsov]

Пример регекса с ошибкой, которую не видит форма: (a)\b\1 - тут пересечение с обратной
ссылкой. Кросс-тестер видит и пропускает такой тест.

Reported by vostreltsov on 2015-06-10 18:42:46

[Former user]

Олег Александрович а ПЗ, ТЗ и презентацию надо тогда внести изменения для алгоритма
пересечения? появились же новые входные данные.

Reported by eklepilkina on 2015-06-14 10:32:09

[Former user]

Еще вопрос.Вот такой фейл.
fa_matcher failed on regex 'b(a|c)$(?<=b[ac])' and string 'bac' (qtype_preg_cross_tests_from_preg_intersection,
data_for_test_assertions_lookbehind_16), merging is on:
NEXT:            a
LEFT:            1
FULL STR:        baa
expected:
NEXT:            -1
LEFT:            0

Вообще не могу понять откуда берется вторая a, если автомат такой.

Reported by eklepilkina on 2015-06-14 15:01:47

<hr> * Attachment: fa_1.svg

[Former user]

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

Reported by eklepilkina on 2015-06-15 16:50:05

[Former user]

Еще проблемы:
1. Почему-то когда совпадает только ассерт, то это вообще не считается за совпадение.
При этом генерация идет правильно.

fa_matcher failed on regex '(?<=[^f])X' and string '** Failers' (qtype_preg_cross_tests_from_preg_intersection1,
data_for_test_630), merging is on:
IS_MATCH:        FALSE
INDEX_FIRST:     0=>-1, 
LENGTH:          0=>-1, 
expected:
IS_MATCH:        TRUE
INDEX_FIRST:     0=>1, 
LENGTH:          0=>0, 

2. Почему-то не работает модификатор (?i) в ассерте.
fa_matcher failed on regex '(?=a(?i)b)\w\wc' and string 'aBC' (qtype_preg_cross_tests_from_preg_intersection1,
data_for_test_250), merging is on:
LENGTH:          0=>1, 
NEXT:            bc
LEFT:            2
FULL STR:        abc
expected:
LENGTH:          0=>2, 
NEXT:            c
LEFT:            1

Reported by eklepilkina on 2015-06-16 05:59:56

[Valeriy Streltsov]

1. IS_MATCH == FULL || LENGTH > 0
2. Подозреваю, что при пересечении листов мы забыли про модификаторы? caseless и прочие
поля в листах

Reported by vostreltsov on 2015-06-16 15:07:21

[Former user]

Спасибо.

Reported by eklepilkina on 2015-06-16 15:38:50

[Former user]

А еще ассерты внутри условных подвыражений их же надо как-то отдельно обрабатывать?

Reported by eklepilkina on 2015-06-16 16:39:42

[Former user]

Какая-то очень странная ошибка. У меня зацикливается на добавлении перехода, а именно
на строке $this->adjacencymatrix[$transition->from][$transition->to][] = $transition;
при обработке циклов с назад смотрящими ассертами. from, to и сам переход полностью
валидны. Если не добавлять один переход на которым происходит зацикливание то все работает.
Не могу понять в чем дело. Абсолютно аналогичные тесты на вперед смотрящие не зависают.

Reported by eklepilkina on 2015-06-17 10:40:35

[Valeriy Streltsov]

Я вытолкнул исправление, которое должно было бы пофиксить неправильный next в lookbehind_16,
но там сейчас фейлится совпадение как в комменте #c49

Reported by vostreltsov on 2015-06-21 08:21:17

[Former user]

После Валериного коммита lookbehind_16, lookbehind_17 заработали

Reported by eklepilkina on 2015-06-23 16:51:37

[Former user]

Есть проблема зацикливания назад смотрящих утверждений, когда ассерт в цикле. Там скорее
всего не хватает loopsback, я поправлю. Но вроде он на матчинг не влияет. Скорее всего
ошибка в автомате, но что может влиять на зацикливание? автомат для примера на рисунке.
На нем зацикливается матчинг.
Я поищу проблему, но, наверное, только числа 30.

Reported by eklepilkina on 2015-06-26 17:45:46

<hr> * Attachment: fa_1.svg

[Oleg Sychev]

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

Reported by oasychev on 2015-06-26 19:56:03

[Oleg Sychev]

И вообще напишите точный тест на котором зацикливается то, а не только автомат.

Reported by oasychev on 2015-06-26 19:57:04

[Oleg Sychev]

Первое что предлагает сделать Валерий - закомментировать содержимое условия на https://code.google.com/r/vostreltsov-preg-28/source/browse/question/type/preg/fa_matcher/fa_matcher.php#933

Это отключает генерацию и позволит понять где повисание - в матчинге (если останется)
или в генерации (если исчезнет).

Reported by oasychev on 2015-06-26 19:58:19

[Former user]

Давайте по очереди с багами, а то сложно все сразу.
Мой клон вот https://code.google.com/r/eklepilkina-complex-assertions/.
Насчет бага с \b. Я переписала, тест перестал выбрасывать исключение, но фейлится,
хотя автомат правильный вроде. Второй сиреневый переход пересечение с \n. Но тест вообще
ни с чем что-то не совпадает. Я не уверена, что при матчинге потом правильно ранги
высчитываются для пересеченных.

Reported by eklepilkina on 2015-06-27 07:34:42

<hr> * Attachment: fa_1.svg

[Former user]

Насчет зацикливания, тест lookbehind 12, у меня из-за правок почему-то 4 теста упало
в пересечении, я попозже посмотрю. Проверю генерация или матчинг тоже позже

Reported by eklepilkina on 2015-06-27 07:36:22

[Former user]

Насчет https://code.google.com/p/oasychev-moodle-plugins/issues/detail?id=328#c75
Закомментировала, все равно виснет.

Reported by eklepilkina on 2015-06-27 17:53:37

[Oleg Sychev]

У меня виснет даже с закомментированной генерацией и пустой строкой на вход. Это что-то
уже совсем кислое....

Reported by oasychev on 2015-06-27 18:44:11

[Oleg Sychev]

Интересная подробность: если подождать с зависанием, вылетает по out of memory

Fatal error: Out of memory (allocated 1796210688) (tried to allocate 268435456 bytes)
in Z:\home\moodle\www\question\type\preg\fa_matcher\fa_matcher.php on line 1164

Reported by oasychev on 2015-06-27 19:08:44

[Oleg Sychev]

Ага, строка расположена в функции check_for_infinite_recursion. Конкретно строка у меня
$front[] = $transition->to;

Reported by oasychev on 2015-06-27 19:09:40

[Valeriy Streltsov]

Лена, мне кажется там что-то с отрезками.
Как минимум нужно заменить свой велосипед в intersect_with_ranges на использование
этого: https://code.google.com/r/oasychev-preg-28/source/browse/question/type/preg/preg_nodes.php#854

Оно также используется при генерации и матчинге. Возможно ее можно оптимизировать,
но использовать нужно именно её.

Я постараюсь проверить ее правильность.

Reported by vostreltsov on 2015-06-30 21:20:40

[Valeriy Streltsov]

Я вытолкнул исправление в ranges, тест теперь должен проходить.

Пожелание: попробовать заменить велосипед в intersect_with_ranges на использование
этого: https://code.google.com/r/oasychev-preg-28/source/browse/question/type/preg/preg_nodes.php#854

Reported by vostreltsov on 2015-06-30 21:37:20

[Former user]

Да все работает, спасибо.  intersect_with_ranges переписала, она писалась очень давно
2 года назад. Теперь по простым вроде все проблемы решены. Сложные закомментировала,
код в клоне со сложными ассертами.

Reported by eklepilkina on 2015-07-01 12:48:56

[Oleg Sychev]

Лена - СРОЧНО - у меня на вашей версии слетел question_test.php - выявление ошибок пустого
автомата, дает фейл на (b$)*c - что мол 1 ошибка есть...

Reported by oasychev on 2015-07-02 13:01:40

[Former user]

Я вроде сделала расстановку тегов, принадлежащих сложному ассерту в основном автомате.
Насколько я помню рассматривали на данном примере. И надо было, чтобы теги 5 стояли
не у эпсилона, а охватывали всю часть пересечения с ассертом. Теперь все так вроде.
Но фейл не ушел пока что.
Сам тест и фейл.
fa_matcher failed on regex 'a(b|=)(?=(\b|.)[!c]d)c[cd]d' and string 'a=cdd' (qtype_preg_cross_tests_from_preg_intersection,
data_for_test_assertions_lookahead_35), merging is on:
INDEX_FIRST:     0=>0, 1=>1, 2=>-1, 
LENGTH:          0=>5, 1=>1, 2=>-1, 
expected:
INDEX_FIRST:     0=>0, 1=>1, 2=>2, 
LENGTH:          0=>5, 1=>1, 2=>0, 

Reported by eklepilkina on 2015-07-20 17:17:38

<hr> * Attachment: fa_before.svg * Attachment: fa_1.svg

[Former user]

Насчет зацикливания. Большинство тестов перестало зацикливаться при установке флага
loopsback. Но есть тест, который скорее всего повисает при построении. В связи с этим
придется улучшать пересечение при циклах.
1. Необходимо удалять повторяющиеся вершины. Вершина 6,3,2,3 == 6,3,2.
2. Ввести понятие эквивалентности типа 6,2,3 == 6,3,2.
По моему эти 2 пункта не нарушают логику с точки зрения ассертов. Может Вы увидите
какие-то проблемы.

Reported by eklepilkina on 2015-07-30 13:09:50

[Oleg Sychev]

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

2. Если эти вершины реально эквивалентны (можете придумать пример в котором образуются
они обе? Не обязательно с конкретно цифрами 6,2 и 3) - можно хранить в порядке возрастания.
Но желательно посмотреть на каком-нибудь разумном примере, как могут образоваться 2
таких вершины чтобы удостовериться, что они и вправду эквивалентны..

Reported by oasychev on 2015-07-30 22:37:04

[Oleg Sychev]

Еще - этот сайт может скоро стать readonly, Лена - пишите в личку если что - пока на
bitbucket переползем...

Reported by oasychev on 2015-07-30 23:46:18

[Former user]

Первое число - это из первого автомата, остальные из второго.
Ну да, но проблема в том, что опять заходя цикл должен начинаться новый ассерт, а предыдущий
еще не дошел до конца, а за счет начала нового ассерта - это в принципе не та же вершина,
но потом все равно будут браться переходы во втором автомате из 2 и 3 одновременно,
так что неважно сколько одинаковых чисел, т.е. неважно сколько реально ассертов началось
и идет. То же самое с порядком - переходы то для пересечения одни и те же.
Я брала это все из теста, который зацикливается a(bc(?<=([a-z][a-k])+)d)+.

Reported by eklepilkina on 2015-07-31 06:09:12

[Oleg Sychev]

Артем, иссью по пересечение автоматов.