1. Oleg Sychev Avatar Oleg Sychev
  2. POAS Moodle plugins
  3. Moodle Plugins
  4. Issues

Изменения в основном коде, необходимые для работы nfa

Issue #31 closed
Valeriy Streltsov created an issue

Originally reported on Google Code with ID 31 ``` Изменения в основном коде, необходимые для работы nfa ```

Reported by `vostreltsov` on 2011-07-12 10:14:27

Comments (50)

  1. Oleg Sychev repo owner

    ``` 1. Расставляйте метки - компонент, владелец. 2. Перечислите сами изменения - а лучше отдельное issue для каждого... ```

    Reported by `oasychev` on 2011-07-12 10:20:42 - Labels added: Component-Preg

  3. Valeriy Streltsov reporter

    ``` preg_leaf_meta::match_inner() В первой строчке исправить ">=" на ">", так как в конце автомата может стоять переход по пустоте, не съедающий символы. Там же, в switch, матчинг eps-перехода.

    ```

    Reported by `vostreltsov` on 2011-07-12 10:36:09

  5. Oleg Sychev repo owner

    ``` Дмитрий, ваше мнение насчет правки >= на > в preg_leaf_meta::match_inner()? Вы ведь исходный автор этого кода... ```

    Reported by `oasychev` on 2011-07-15 19:04:45

  6. Former user Account Deleted

    ``` Мы сошлись во мнениях на вариантое: >= && !SUBTYPE_EMPTY Для других типов не имеет смысла проверять их в конце, да и нехорошо будет str[i], при i==strlen($str), а так только при пустоте пройдёт при последнем символе. ```

    Reported by `Xapuyc7` on 2011-07-17 12:08:23

  7. Oleg Sychev repo owner

    ``` Я так понимаю что в условии должно быть > || (== && SUBTYPE_EMPTY) ? ```

    Reported by `oasychev` on 2011-07-17 17:27:57

  8. Valeriy Streltsov reporter

    ``` $pos>=strlen($str) && $this->subtype != preg_leaf_meta::SUBTYPE_EMPTY ```

    Reported by `vostreltsov` on 2011-07-17 18:09:39

  9. Oleg Sychev repo owner

    ``` Пишу в эту тему, т.к. здесь все собрались. По окончании пересдач предлагаю организовать встречу всех участников разработки preg по пятницам 2-й недели с 15-10. По расписанию вы все можете.

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

    Если кто не может - прошу сообщить, в противном случае считаю встречу назначенной ```

    Reported by `oasychev` on 2011-09-06 18:26:25

  11. Oleg Sychev repo owner

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

    Reported by `oasychev` on 2011-10-26 21:03:48

  12. Valeriy Streltsov reporter

    ``` Матчер вылетает в ситуациях, подобных такой: (?:(ab)|(cd))\1 и строке "cd" В функциях first_correct_character_index и last_correct_character_index нужно условие

    $subpattern > $this->count_subpatterns() поменять на !array_key_exists($subpattern, $this->index_last) ```

    Reported by `vostreltsov` on 2011-10-27 03:23:39

  13. Oleg Sychev repo owner

    ``` С этим согласен (хотя заносить пустые строки в индексы подмасок где не было совпадения матчер вполне в состоянии, лучше инициализировать массив пустыми строками по количеству подмасок (+1 на общее совпадение) перед поиском совпадения).

    P.S. Из ваших правок возражения вызывали изменения match где вы убрали условия... Кстати, еще один наглядный пример почему коммиты должны быть атомарными - в тот коммит вы не меньше 3-х различный изменений внесли... ```

    Reported by `oasychev` on 2011-10-27 08:41:59

  14. Oleg Sychev repo owner

    ```

    • инициализировать массив не пустыми строками, конечно, а индексами описывающими отсутствие совпадения... ```

    Reported by `oasychev` on 2011-10-27 08:44:38

  15. Oleg Sychev repo owner

    ``` Мне все-таки не нравится изменения, сделанные в комментарии 12. Если запрашивается потенциально существовавшая, но не совпавшая подмаска - это не должно выбрасывать исключение (тем более с таким сообщением).

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

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

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

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

    Reported by `oasychev` on 2011-10-29 22:10:46

  16. Valeriy Streltsov reporter

    ``` Не нашел ни в одном файле, что есть такое count_subpatterns. Если вы имеете ввиду nfa-шную функцию numerate_subpatterns(), то у нее есть обновляемый параметр $cnt. В конце рекурсии он как раз равен количеству подмасок. Его можно запомнить в матчере - нужно сделать отдельное поле для него... ```

    Reported by `vostreltsov` on 2011-10-30 13:26:16

  17. Oleg Sychev repo owner

    ``` preg_matcher.php preg_matcher::count_subpatterns() строка 240 Она была рассчитана на то, что все будет заполнено, и соответственно считала количество элементов в массиве. Если отсутствующие совпадения не будут заполняться специальным значением, то ее надо переписать. Но я бы все-таки заполнил массив спец-индексами, обозначающими отсутствие совпадения, так проще...

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

    Reported by `oasychev` on 2011-10-30 20:51:42

  18. Valeriy Streltsov reporter

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

    Reported by `vostreltsov` on 2011-10-31 03:00:08

  19. Oleg Sychev repo owner

    ``` Видели добавленную функцию preg_matcher::matched_part() ? См. последнее изменение...

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

    Reported by `oasychev` on 2011-10-31 13:02:52

  20. Valeriy Streltsov reporter

    ``` Ок, для несовпавших подмасок я сделал index_first[i] == -1 и index_last[i] == -2.

    Кстати, не стоит ли перенести функцию nfa_preg_matcher::numerate_subpatterns() в абстрактный матчер? Мне кажется, так было бы удобнее, да и backtracking'у нужна будет подобная функция - зачем их делать в наследниках... ```

    Reported by `vostreltsov` on 2011-10-31 14:01:33

  21. Oleg Sychev repo owner

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

    Кстати, пятница у нас праздник на этот раз. Попробуйте подойти во вторник, после своих занятий - возможно в 15 часов я еще буду на кафедре. Если нет - в четверг посмотрите мои занятия по расписанию 4-го курса, там А-5хх если я правильно помню. Немного подождете - выберу момент вам это все показать... ```

    Reported by `oasychev` on 2011-10-31 14:47:11

  22. Valeriy Streltsov reporter

    ``` Вытолкнул изменения, касающиеся нумерации подмасок. Подмаски перевести на SUBTYPE не получилось, да и Дмитрий против этого. Тесты на лексер\парсер разделил на два файла и сделал утверждения простыми, без &&. ```

    Reported by `vostreltsov` on 2011-11-01 14:28:02

  23. Oleg Sychev repo owner

    ``` Вы бы уже учились работать публично через трекер.

    Что именно не получилось у вас с SUBTYPE? И почему Дмитрий против этого где-то там, за кулисами? К тому же не очень понимаю как эта внутренняя проблема парсера может мешать чьему-то матчеру и с чего тут можно быть против, когда результат одинаковый...

    Если неудачно выбрано значение константы, так ведь его легко заменить...

    Давайте разберемся нормально. Вы напишите, какие проблемы возникли у вас. А Дмитрий пусть напишет свои возражения. Здесь... ```

    Reported by `oasychev` on 2011-11-01 17:04:47

  24. Valeriy Streltsov reporter

    ``` Вы правы, неудачно выбрано значение preg_node_subpatt::SUBTYPE_SUBPATT. Поставил наобум 33 - работает. Только теперь вопрос - какое именно значение присвоить. Я не пойму по какому принципу у другой константы выбрано 22. Тогда дождемся ответа Дмитрия, и я сделаю коммит... ```

    Reported by `vostreltsov` on 2011-11-01 17:48:25

  25. Oleg Sychev repo owner

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

    Например (навскидку): типы - десятки (10,20...), подтипы - единицы (подтипы 10 будут 11, 12 ...). Можно, наверное, и лучше придумать - поэтому предлагаю подумать 2-3 дня и всем высказать свои предложения. Потом перенумеруем все по единой схеме.

    P.S. Это наглядный пример полезности именования констант в сложных программах.

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

    Reported by `oasychev` on 2011-11-01 17:55:10

  26. Valeriy Streltsov reporter

    ``` Можно чуть-чуть обобщить - нумеровать подтипы относительно типов. preg_node::TYPE_SUBPATT = 30; preg_node_subpatt::SUBTYPE_SUBPATT = preg_node::TYPE_SUBPATT + 1; и т.д.

    Тогда необязательно типы будут десятками, а подтипы единицами. ```

    Reported by `vostreltsov` on 2011-11-01 19:26:07

  27. Oleg Sychev repo owner

    ``` Ну я собственно относительную нумерацию и предлагал. Вопрос в том, хватит ли 10 подтипов кому угодно...

    Лучше задать константу preg_node::MAX_SUBTYPES, с некоторым запасом (на 1 больше обязательно), например 10. Тогда типы будут нумероваться MAX_SUBTYPES, MAX_SUBTYPES*2, MAX_SUBTYPES*3 и т.д.; а подтипы MAX_SUBTYPES*х+1, MAX_SUBTYPES*х+2

    Тогда при необходимости можно будет без проблем перенастроить множитель... ```

    Reported by `oasychev` on 2011-11-01 20:22:34

  28. Valeriy Streltsov reporter

    ``` Задаю константу так: const MAX_SUBTYPES = 10; const TYPE_ABSTRACT = MAX_SUBTYPES; const TYPE_LEAF_CHARSET = MAX_SUBTYPES * 2;

    На последней строчке получаю ошибку. Parse error: syntax error, unexpected '*', expecting ',' or ';' Неужели в php так объявлять константы нельзя? Какие тогда есть варианты? ```

    Reported by `vostreltsov` on 2011-11-02 13:27:15

  29. Oleg Sychev repo owner

    ``` Да, PHP запрещает операции в константах не пытаясь проверить, константные у них аргументы или нет...

    Значит надо либо брать достаточно большой множитель, либо думать еще... Можно, конечно, использовать статические функции вместо констант, но надо взять какой-то достаточно большой тестовый пример чтобы замерить, насколько это отражается на производительности... ```

    Reported by `oasychev` on 2011-11-02 16:58:16

  30. Valeriy Streltsov reporter

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

    Reported by `vostreltsov` on 2011-11-02 17:18:29

  31. Oleg Sychev repo owner

    ``` Давайте подумаем пару дней.

    Еще вариант - делать подтипы дробными (целая часть - тип, дробная - подтип). Тут ограничений в количестве подтипов не будет... Но надо проверить что дробное число пройдет в лексере в качестве типа лексемы. ```

    Reported by `oasychev` on 2011-11-02 20:28:14

  32. Valeriy Streltsov reporter

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

    А с дробной частью придется помнить, что нельзя записать две константы 0.1 и 0.10. Да и вообще странно это, имхо. ```

    Reported by `vostreltsov` on 2011-11-11 09:50:43

  33. Oleg Sychev repo owner

    ``` Есть еще вариант хранить константы строками, через точку или другой разделитель, тогда можно будет вписывать любые значения (только проверять через === если точка чтобы не иметь проблем с преобразованием типов - а лучше просто запятую или другой разделитель кроме точки) и иметь произвольную вложенность, вводя (под-)*типы :) по мере надобности, как в IP-адресах. Но надо проверить, насколько строки пойдут в качестве значений, возвращаемых из лексера, или там числа надо иметь...

    Если там только числа допустимы, то согласен с предложением 100 на тип... ```

    Reported by `oasychev` on 2011-11-11 17:04:49

  34. Valeriy Streltsov reporter

    ``` Строки работают. Непонятно только, зачем вложенность? Вроде бы не нужно выделять подтипы именно из строки, константы должны быть просто уникальными. Мне кажется, можно сделать что-то вроде:

    const TYPE_LEAF_ASSERT = "leafassert"; const SUBTYPE_CIRCUMFLEX = "circumflexleafassert"; ```

    Reported by `vostreltsov` on 2011-11-11 19:21:12

  35. Oleg Sychev repo owner

    ``` Не хотелось уходить от чисел. Есть еще вариант - нумеровать типы отрицательными числами, а под-типы - положительными.

    Или брать ваш вариант по 100 на каждое...

    Реализация возврата ошибки неудачная: вместо бесконечных проверок на возвращаемое значение лучше использовать выброс исключения, которое будет ловится на уровне nfa_preg_matcher. Ошибка в рекурсии как раз классический случай преимуществ исключений перед возвратом ошибки...

    P.S. В текущем состоянии ваши изменения работают или для работоспособности нужен коммит с перенумерацией констант? ```

    Reported by `oasychev` on 2011-11-12 16:07:09

  36. Valeriy Streltsov reporter

    ``` Переделаю на исключения.

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

    ```

    Reported by `vostreltsov` on 2011-11-12 17:44:23

  37. Oleg Sychev repo owner

    ``` Вы так спрашиваете, как будто я его видел... Там какая схема нумерации принята? ```

    Reported by `oasychev` on 2011-11-12 18:17:42

  38. Valeriy Streltsov reporter

    ``` Есть два файла: со строками как я приводил пример в 34 комментарии и с сотнями на подтип, обе версии работают. ```

    Reported by `vostreltsov` on 2011-11-12 18:35:15

  39. Oleg Sychev repo owner

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

    Reported by `oasychev` on 2011-11-12 18:53:52

  40. Oleg Sychev repo owner

    ``` Валерий, мы закончили с совершенствованием базовых классов для работы с NFA-матчером? ```

    Reported by `oasychev` on 2011-11-20 15:48:59

  41. Valeriy Streltsov reporter

    ``` Да, закончили. Обратную ссылку я, вроде бы, хорошо протестировал - но все равно не помешало бы ещё побольше тестов от Медникова... С остальными классами точно все закончено. ```

    Reported by `vostreltsov` on 2011-11-20 15:53:40

  42. Oleg Sychev repo owner

    ``` Тесты для выражений типа (a|b\1)+ есть? ```

    Reported by `oasychev` on 2011-11-20 16:22:09

  43. Valeriy Streltsov reporter

    ``` Да, подобный тест есть, и этот я сейчас дополнительно добавлю. Появился вопрос: eps-переход должен всегда возвращать true? Даже если мы вышли за пределы строки или строка пустая? Что делать, если юзер ничего не ввел? ```

    Reported by `vostreltsov` on 2011-11-20 17:17:13

  44. Oleg Sychev repo owner

    ``` По тесту - надо серию строк добавить, он забавный. В http://pcre.org/pcre.txt можно найти несколько примеров строк, совпадающих с этим выражением - скопируйте оттуда чтобы быть уверенным, что все поняли правильно.

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

    ```

    Reported by `oasychev` on 2011-11-20 18:04:16

  45. Valeriy Streltsov reporter

    ``` Ок, сейчас доделаю все эти мелочи...

    P.S. с git разобрался, сделал локальный репозиторий, но мудл 2.1 почему-то не ставится на денвер... завтра на свежую голову буду делать - сегодня уже часов 10 подряд сижу... ```

    Reported by `vostreltsov` on 2011-11-20 18:08:19

  46. Oleg Sychev repo owner

    ``` Возможно денвер старый и версия PHP не проходит. Я под 2.1 скачал последний денвер, на него все нормально ставится.... ```

    Reported by `oasychev` on 2011-11-20 18:13:20

  47. Valeriy Streltsov reporter

    ``` Тест (a|b\1)+ добавил, работает корректно. Хорошо бы было добавить в основной класс константу - количество символов при непроходимом пути. Вы когда-то писали что-то вроде 100000 - если нетрудно, добавьте потом туда, где ей логичнее быть... ```

    Reported by `vostreltsov` on 2011-11-20 19:49:53

  48. Oleg Sychev repo owner

    ``` Т.е. если нельзя закончить путь никаким символом, что ставить в left?

    Вопрос интересный, он коррелирует с содержанием next при этом - я бы ориентировался на next даже наверное... Я думал заняться стандартизацией поведения при невозможности продолжить совпадение до конца - но не прямо сейчас... Думаю в 2.2 пойдет.

    Создайте для этого отдельное issue и подпишите всех... Меня - owner'ом.

    Удалось поставить 2.1? ```

    Reported by `oasychev` on 2011-11-20 20:08:19

  49. Oleg Sychev repo owner

    ``` ВСЕМ: воздержаться от внесения изменений в класс preg_matcher до перехода на 2.1, т.к. в новой версии он разбит на два класса и слияние будет проблематичным.

    Валерий, если изменения в матчере NFA устраивают, переведите состояние в Done. ```

    Reported by `oasychev` on 2011-11-21 11:27:57 - Status changed: `Fixed`

  51. Log in to comment
Assignee
Type
bug
Priority
minor
Status
closed
Component
–
Votes
0
Watchers
0
Jira: the preferred issue tracker for Bitbucket. Join the team!