Тесты, которые проваливает DFA

[Valeriy Streltsov]

Originally reported on Google Code with ID 39

^abc|def$
на строке 'def' не находит совпадение вообще

^[a-z 0-9]\b[a-z 0-9]\B[a-z 0-9]
на строке ' abc' неправильно определяет последний индекс совпавшей части.
на строке ' 9bc' неправильно определяет последний индекс совпавшей части.
на строке '  b' неправильно определяет следующий символ (хотя тут, скорее всего, уже
моя работа - переписывать character)

^abc[a-z.?!]\b[a-zA-Z]
на строке 'abcaa' неправильно определяет следующий символ(он здесь невозможен) и количество
оставшихся символов (такое ощущение, что ассерты прибавляют по единице к длине. Хотя
вообще спорный вопрос - что возвращать, если следующего символа нет)

Reported by vostreltsov on 2011-09-30 11:31:49

[Oleg Sychev]

``` Если следующего символа нет, то надо возвращать пустую строку: '' И только ее - вопрос не спорный.

Дмитрий, ваше мнение? ```

Reported by `oasychev` on 2011-10-03 05:32:24 - Labels added: Component-Preg, Milestone-Release2.1

[Valeriy Streltsov]

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

Reported by `vostreltsov` on 2011-10-03 10:28:42

[Oleg Sychev]

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

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

На самом деле если путь непроходимый, то логично длину выставить побольше, уходя в бесконечность, потому что она используется для подбора наиболее подходящего ответа из нескольких возможных. Я думаю 100000 будет достаточно ;) Но это проще и надежнее сделать в главном классе матчера после вызова match_inner перед сохранением результатов, чем заставлять так себя вести каждый матчер. Условием типа "если поддерживаются следующий символ и длина и следующего символа нет (строка пуста)" то записываем в длину большое число. ```

Reported by `oasychev` on 2011-10-04 09:23:50

[Oleg Sychev]

``` Валерий, ваше отношение к изменениям в preg_node.php и кросс-тестах от nfa внесенных в коммите http://code.google.com/r/xapuyc7-refactoring-dfa/source/detail?r=f59f5640fb54db4cf164eb0c8f46bb689330687f

```

Reported by `oasychev` on 2011-11-25 09:30:49

[Valeriy Streltsov]

``` По тестам: первое изменения я и сам делал в своем клоне, там была опечатка; второе сути теста не меняет, цикл нулевой длины всё равно остается, так что всё хорошо; за третье изменение Дмитрию спасибо, пробел действительно один из возможных символов.

В preg_nodes.php внесены точно такие же изменения, какие вносил и я - только в немного другой форме... Надо будет это аккуратно смёржить.

```

Reported by `vostreltsov` on 2011-11-25 11:45:05

[Oleg Sychev]

``` Дмитрий, все-таки непонятно почему вы перенесли * после ^ в тесте. Эта ситуация все еще составляет проблемы или в чем дело? ```

Reported by `oasychev` on 2011-11-25 18:38:26

[Oleg Sychev]

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

И давайте обойдемся без упрощения "неудобных" регексов в тестах! Это уже нехорошими словами называется... ```

Reported by `oasychev` on 2011-11-25 23:13:35

[Oleg Sychev]

Reported by `oasychev` on 2011-11-28 17:06:22 - Labels added: Priority-Critical - Labels removed: Priority-Medium

[Former user]

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

Некоторые однотипные ошибки опущены, однако присутствуют все типы ошибок

Кривая реализация частично пересекающихся символьных классов, очень кривая, она ломает весь автомат, в некоторых случаях dfa_preg_matcher failed on regex 'ab+[a-z]*bacd' and string 'abacd' dfa_preg_matcher failed on regex 'ab+[a-z]*bacd' and string 'abacd'один и тот же тест фром нка и фром бэктрэк dfa_preg_matcher failed on regex 'abcd([a-z]|[A-Z])+Az' and string 'abcdaaaabcdZz'

dfa_preg_matcher failed 'full' check on regex 'ab+[a-z]{1,6}bacd' and string 'abbbbbacd'

dfa_preg_matcher failed 'next' check on regex 'ab+[a-z]{1,6}bacd' and string 'abbbbbacd' dfa_preg_matcher failed 'left' check on regex 'ab+[a-z]{1,6}bacd' and string 'abbbbbacd' dfa_preg_matcher failed on regex 'ab+[a-z]{1,6}bacd' and string 'abacd' dfa_preg_matcher failed 'is_match' check on regex 'abcd([a-z]|[A-Z]){3,10}Az' and string 'abcdAADFEDAzAz' dfa_preg_matcher failed 'full' check on regex '^(?:/\+.*abc\*)$' and string '/+fghjhj4587abc*'

сочетание ЧСК и простых ассертов dfa_preg_matcher failed 'next' check on regex '[A-Z0-5 ]+\b[0-5A-R ]+' and string 'ABDEDSGR 0357'ЧСК, как ни странно, автомат захватывает всё как 1-й СК dfa_preg_matcher failed 'index_last' check on regex '^[a-z 0-9]\b[a-z 0-9]\B[a-z 0-9]' and string ' abc'наверное, по крайней мере получается нечто ужасное вместо автомата dfa_preg_matcher failed 'left' check on regex '^abc[a-z.?!]\b[a-zA-Z]' and string 'abcaa'

Ошибка в тесте dfa_preg_matcher failed on regex '(?:a{3,5}a)+b' and string 'aaaaaaaaaaa'тест требовал следующим символом а, хотя наискорешим завершением будет b dfa_preg_matcher failed 'left' check on regex '(^abc)|(def$)' and string 'deff'данный путь не является непроходимым!!! совпадает def, приписываем конец строки!!! dfa_preg_matcher failed 'index_first' check on regex '[^A-Z][A-Z][dfg][^0-9]' and string 'TTff' захват частиного совпадения в виде первой f или второй f, впринципе равноцны, насколько я знаю, 1-я f более соответствует стандартам, тест требует только 2-ю , а первую неприемлет. dfa_preg_matcher failed 'next' check on regex '[A-Z0-5 ]+\b[0-5A-R ]+' and string 'ABDEDSGR'тест требует только пробел, хотя 0, так же является корректным следующим символом dfa_preg_matcher failed 'left' check on regex 'abc$' and string 'abca'тест считает путь непроходимым dfa_preg_matcher failed 'left' check on regex '^abc|def$' and string 'deff' dfa_preg_matcher failed 'left' check on regex '^a[^b]cd$' and string 'aacde'obtained result '0' for 'left' is очень даже correct dfa_preg_matcher failed 'left' check on regex '(?:a|b)*abb$' and string 'ab'obtained result '1' for 'left' is очень даже correct

проблемы с непроходимыми путями кстати, примененные в тестах регексы непропустяться валидацией, если применять вопрос целиком, а не отдельно матчер. dfa_preg_matcher failed 'next' check on regex 'a|(b$)c' and string 'bc' dfa_preg_matcher failed 'is_match' check on regex '$abca' and string 'abca' dfa_preg_matcher failed 'next' check on regex 'abc^' and string 'abca'

наличие кривой реализации больших ассертов, работающей однако в более простых случаях dfa_preg_matcher failed 'index_last' check on regex 'a(?:(?=[^b])[xcvbnm])+' and string 'axcv' dfa_preg_matcher failed 'index_last' check on regex 'a(?:(?=[^b])[xcvbnm])+' and string 'axacav' dfa_preg_matcher failed 'full' check on regex 'a(?:(?=[^b])[xcvbnm])+' and string 'ab'

проблемы с пустой строкой на входе либо с допустимость пустоты в выражении dfa_preg_matcher failed 'is_match' check on regex '^the matcher works' and string '' dfa_preg_matcher failed 'is_match' check on regex '(abcd|)' and string '' dfa_preg_matcher failed 'is_match' check on regex '(?:abc)*' and string 'ab'

проблемы с пустыми ассертами, в частности с генерацией следующего символа dfa_preg_matcher failed 'next' check on regex 'ab\b cd' and string 'abc'

серьезные проблемы с ассертом, действующим за пределами выражения, ведь отделение захваченного самим выражением, от проверенного ассертом равнозначна проблеме подмасок dfa_preg_matcher failed 'index_last' check on regex 'ab(?=cd)' and string 'abcd' dfa_preg_matcher failed 'next' check on regex 'ab(?=cd)' and string 'abcd dfa_preg_matcher failed 'full' check on regex 'ab(?=cd)' and string 'abcd' ```

Reported by `Xapuyc7` on 2011-12-04 17:31:54

[Oleg Sychev]

``` Дмитрий, будьте добры нумеровать пункты чтобы было проще отвечать...

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

• '(?:a{3,5}a)+b' and string 'aaaaaaaaaaa' - пока делаем два варианта next и пишем TODO разобраться и внести изменения позже, ситуация спорная и искусственная
• '(^abc)|(def$)' and string 'deff' - согласен, совпадение def next пустой, left=0
• 'index_first' check on regex '[^A-Z][A-Z][dfg][^0-9]' берем левую
• regex '[A-Z0-5 ]+\b[0-5A-R ]+' and string 'ABDEDSGR' - тест прав требуя пробел, т.к. для \b цифры являются символами слова вместе с буквами и подчеркиванием (она работает через \w) - исправляйте у себя и обязательно к релизу
• 'abc$' and string 'abca' - см выше, здесь нулевой left, с двумя последующими тоже согласен

4)"проблемы с непроходимыми путями" - валидация все пропустит, если не будет введен правильный ответ. Так что обрабатываем эти случаи. Значение next там возможно просто стандартизовано для невозможности продолжения, сделайте как в тесте; failed 'is_match' check on regex '$abca' and string 'abca' тоже надо поправить. Частичное совпадение с ассертом нулевой длины с самого конца строки присутствует, выражение же не заякорено.

5) большие ассерты - пока ставим непринятие этих узлов в accept, т.к. корректно поддерживать не можем;

6) "проблемы с пустой строкой на входе либо с допустимость пустоты в выражении" - исправить; случаи когда введена пустая строка достаточно часты; они не должны вызывать проблем у матчера! А если и выражение допускает пустоту - ситуация странная - но не вижу причин не иметь полное совпадение нулевой длины.

7) next при простых ассертах оставляем до следующих релизов ```

Reported by `oasychev` on 2011-12-04 20:59:56

[Oleg Sychev]

``` Валерий - правит тесты из 3) где было принято решение об исправлении и выталкивает их.

Дмитрий:

• правим поломанные модификаторы и перезапускаем все(!) тесты - особо проверяем работу глобального i - выталкиваем срочно!;
• мержим исправления в тестах - не забывайте выполнять и коммитить слияния!
• исправляем 5 (непринятие); потом 6, потом тест из 3 где вы неправы;
• правим 1 - допустимо частичное решение, но большую часть ситуаций надо устранить к этому релизу

Релиз определяется скоростью интеграции http://tracker.moodle.org/browse/MDL-30562 но учитывая что изменения очень просты это должно быть быстро. ```

Reported by `oasychev` on 2011-12-04 21:08:58

[Former user]

``` Поломанный i исправлен, фаталок больше нет, изменения в моем клоне, по остальнеым пунктам вытолкну изменения завтра, по тем которые это предполагют, естественно. По поводу 1, хотелось бы знать что есть воркараунд, то что есть сейчас справляется со многими ситуациями, но в случаях где много ЧСК подряд, возникают нехорошие вещи, я буду, что можно сделать. ```

Reported by `Xapuyc7` on 2011-12-04 22:39:09

[Oleg Sychev]

``` "Поломанный i исправлен, фаталок больше нет, изменения в моем клоне" - об этом логичнее было бы написать в 32... ```

Reported by `oasychev` on 2011-12-04 22:45:43

[Former user]

``` У меня есть мысль по поводу ЧСК, а что если ВСЕ чСК разбить еще в дереве? Решение некрасивое, с лишними разбиениями (например [abcd]t[cdef] превратиться в (?:[ab]|[cd])t(?:[cd]|ef]), что вообще-то не нужно) но такое решение решит все проблемы с ЧСК (включая те которых на самом деле нету) и скорее всего будет работать. Но это либо потребует вноса \w\d... в чарсет, либо породит множество уродцев preg_leaf_combo. Как мне кажется сойдет в качестве времянки. Ваше мнение по этому поводу? ```

Reported by `Xapuyc7` on 2011-12-05 22:33:34

[Oleg Sychev]

``` Мне не очень нравится такой вариант. Вообще вы все предыдущие - 5,6 и проваленный тест с 0 вместо пробела из 3 исправили? Я просил заниматься 1 только после этого... ```

Reported by `oasychev` on 2011-12-06 18:09:11

[Oleg Sychev]

``` 5 и 6 должно быть несложно пофиксить, я надеюсь это долго не займет... ```

Reported by `oasychev` on 2011-12-07 19:35:30

[Former user]

``` Пофиксил матчинг в строке с нулевой длинной. Изменения в клоне. ```

Reported by `Xapuyc7` on 2011-12-09 16:36:11

[Oleg Sychev]

``` Есть 4 конкретных проблемы, которые необходимо устранить к релизу СРОЧНО: 1) убрать все (!) исключения при юнит-тестировании. Там много исключений, но однотипные - всего где-то три-четыре вида проблемы. Но это серьезные ошибки!

• Undefined offset: 1 - обращение по несуществующему индексу;
• Invalid argument supplied for foreach() - циклу передан не массив (объект), а непонятно что
• reset() expects parameter 1 to be array, null given - опять null вместо массива
• Undefined property: stdClass::$nextstep - используется отсутствующее свойство

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

2) Я могу понять провалы на индексы, next и left из-за проблем с частично пересекающимися классами. Ну full еще могу понять... Провалы кросс-тестов на is_match - это что-то сверх странное. Ваш матчер не может даже определить, сматчилась ли хоть одна буква или нет?! Тут ваши проблемы не должны так активно мешаться. К тому же есть подозрение что is_match в этих ситуациях не получает значения - равен null или пустой строке. Иногда там 1 вместо true оказывается почему-то. Проверить, отписаться в чем проблема.

3)пофиксить issue 53 - там вроде совсем на ровном месте ошибка. ```

Reported by `oasychev` on 2011-12-09 18:09:42

[Oleg Sychev]

``` По техническим причинам я должен сделать релиз на этих выходных. Так что вышеперечисленное исправить совершенно СРОЧНО! По 2 и 3 - если нет серьезных препятствий - должен быть фикс. В случае серьезных препятствий буду думать, включать ли ДКА в новый релиз. Но не должно быть вроде... ```

Reported by `oasychev` on 2011-12-09 18:11:54

[Former user]

``` 1 и 2 исправил, отключил кривую обработку ЧСК, от неё было больше проблем, чем пользы, кол-во ошибок осталось прежним, но ошибки на изматч исчезли и пропали исключения. Для исправления 3, нужно реализовать нормальную обработку ЧСК, проблема возникает на пересечении метаточки с а, б, и с. Изменения в клоне. ```

Reported by `Xapuyc7` on 2011-12-11 17:32:09

[Oleg Sychev]

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

2 Будьте добры ПЕРЕД началом своих изменений вытягивать изменения из основного репозитория. Это значительно уменьшит количество слияний в репозитории! ```

Reported by `oasychev` on 2011-12-12 10:22:45

[Oleg Sychev]

``` Оставшиеся ошибки должны быть строго поправлены к 2.2, в противном случае ДКА матчер придется выключать :( ```

Reported by `oasychev` on 2011-12-12 12:48:18 - Labels added: Milestone-Release2.2 - Labels removed: Milestone-Release2.1

[Oleg Sychev]

``` 1. Значение полей is_match и full иногда 1 или пустое - оно может быть неправильным, но пусть хотя бы будет true или false. См. например (хотя не только) dfa_preg_matcher failed 'is_match' check on regex 'a|(b$)c' and string 'bc'

2. Осталось исключение на кросс-тестах из НКА Unexpected PHP error [Undefined offset: 1] severity [E_NOTICE] in [Z:\home\moodle\www\question\type\preg\dfa_preg_matcher.php line 553] ```

Reported by `oasychev` on 2011-12-13 10:38:37

[Valeriy Streltsov]

``` Кросс-тесты исправлены, появилось огромное количество фейлов ДКА. Большинство из них такие: obtained result '0' for 'next' is incorrect. ```

Reported by `vostreltsov` on 2012-01-01 21:34:56

[Oleg Sychev]

``` Я бы эту проблему обсуждал в 80, она относится скорее всего к конвертации...

Дмитрий, теперь (слив клон Валерия) вы можете протестить свою конвертацию. Посмотрите, в чем там дело. Желательно в ближайшую пару дней! ```

Reported by `oasychev` on 2012-01-01 21:38:00

[Oleg Sychev]

``` Дмитрий, жду от вас описания текущего положения дел по фейлам ДКА... ```

Reported by `oasychev` on 2012-07-24 14:49:51

[Former user]

``` There are a lot of fails on simple asserts circumflex and dollar, include tests which was pass, Something broken. Fix for firth time, because many fails. There are few fails on simple assert wordbreak, impossible to fix now. There is one exeption from wave, fix to second time. May be this list will be changed on fixing time.

P.S. Sorry for english (especially sorry fo MY english), I am not set locale on my linux yet.

P.P.S. hotyabi bez translita :D ```

Reported by `Xapuyc7` on 2012-07-26 00:04:44

[Oleg Sychev]

Reported by oasychev on 2013-01-27 15:57:01 - Status changed: Duplicate - Merged into: #165