Генерация следующего символа при наличии merged assertions
Issue #38
closed
Originally reported on Google Code with ID 38
Классы-листья могут теперь иметь слитые с ними утверждения (массив).
Необходимо доработать функцию генерации следующего символа так, чтобы она учитывала
эти утверждения. Это приведет нас к корректной генерации следующего символа для простых
утверждений.
Начать стоит с тестовых примеров. Не мешает также подумать как сделать это избегая
дублирования кода (возможно какой-то код надо разместить в классе самого утверждения).
Если ни один следующий символ не подходит (актуально главным образом для ^ и $, но
возможно и при a\bc) то следует вместо символа выдать сообщение (длинное, понятное)
через get_string (чтобы могло переводится), желательно с объяснением почему продолжить
нельзя...
Работу вести в отдельном клоне, чтобы можно было вытянуть эти изменения отдельно от
вашего матчера.
Reported by oasychev on 2011-09-09 13:26:00
Comments (23)
-
reporter
-
``` Предлагаю передавать в функцию: -последний сгенерированный символ для работы простых ассертов. Если я правильно понял, вы предлагали передавать строку (входную?) и позицию конца совпадения. Ассертам-то нужно знать последний совпавший символ, а в нашем случае он уже сгенерирован, а не взят из строки... -массив сгенерированных подмасок для работы обратных ссылок.
Может возникнуть ситуация, когда нет простого ассерта и может подойти символ любого типа - буква\цифра\другой символ. При этом один из вариантов может привести к удачному завершению генерации строки, а другой-нет. Поэтому нужно либо передавать в функцию нужный тип символа, либо возвращать массив символов разного типа, чтобы функция матчера пробовала разные пути. Как лучше сделать? (Мне кажется, массив предпочтительнее - тогда в функции матчера можно будет просто в цикле перебрать этот массив, не задумываясь о типе символов) ```
Reported by `vostreltsov` on 2011-09-25 05:58:23
-
reporter
``` Я предложил строку и позицию, потому что это общая информация по которой большинство (в том числе перспективных) видов узлов сможет ориентироваться... К тому же ее удобно передавать, она же передается и при матчине. Вы предлагаете частную информацию, которая может изменится. А править интерфейс вызываемой из разных мест функции лучше всего как можно реже...
Наоборот массив подмасок требуется только обратным ссылкам и кое-кому еще. А некоторые матчеры вообще могут не поддерживать подмасок. Поэтому в данном случае обратной ссылке лучше воспользоваться имеющейся у нее ссылкой на матчер.
Насчет позиции вопрос немножко сложнее: их на самом деле две, хотя часто они совпадают - последний совпавший символ и символ с которого начал совпадение последний узел (несовпавший). Они могут быть различными как раз для обратных ссылок, рассмотрите ситуации когда половина ссылки совпала, а потом - нет. Узел то один, а символов много...
Насчет второго вопроса до конца не понял. Приведите пример. Я бы предпочел локализовать определение символа в узле - для того туда и ассерты в частности мержатся. По идее матчер должен предварительно пробежать автомат, найти кратчайший путь к ответу из точки облома совпадения, и у первого узла этого пути вызвать функцию опрпделения символа... Проблема возникает если дальше следует ассерт?
Я бы не хотел использовать массив, если это возможно, потому что они могут быть большими, особенно для Unicode. А \w и т.д. работают через функции (посмотрите метод match для preg_leaf_meta), как планируете массив составлять?! Если по другому не выйдет, нужна более сложная структура... ```
Reported by `oasychev` on 2011-09-26 10:26:32
-
``` Да, проблема возникает для символьных классов, если дальше стоит ассерт. Пример - [a-z ?!]\b[a-z] Если в первом листе сгенерировать букву, будет тупик.
они могут быть большими, особенно для Unicode.
Я имел ввиду массив из 3 символов разного типа - буква\цифра\служебный символ - зачем больше? Нужно только добавить в нынешнюю реализацию character() для символьного класса проверку на алфавитно-циферность+ассерты и возвратить 3 символа вместо одного. ```
Reported by `vostreltsov` on 2011-09-26 18:38:11
-
``` А у preg_leaf_meta функция character() вообще возвращает константные символы для разных подтипов листа. Там проблем не будет. При учете ассертов там получится либо тот же самый константный символ, либо сообщение о невозможности генерирования символа из-за нарушения ассерта...
В общем, 3 символа будут возвращаться только из символьного класса, т.к. только там однозначно не определен тип символа и возможны варианты... ```
Reported by `vostreltsov` on 2011-09-26 18:59:05
-
reporter
``` По первому комменту - "зачем больше?" Рассмотрите вариант когда у вас в примере не a-z а слева a-l а справа h-v? Какую букву должен возврщать левый класс не зная правого?
Насчет meta не согласен. Рассмотрите отрицательный случай \D\b[a-z.?] Как \D уложится в 3 символа? Все опять сложнее....
А потенциально есть еще \L{} - unicode properties, там вообще труба.... ```
Reported by `oasychev` on 2011-09-27 08:09:03
-
``` [a-l ?!]\b[h-v] Первый лист сгенерирует array('a','?'), второй array('h'). Функция матчера попробует пути "a\bh" и "?\bh" и возвратит второй путь. Если листы будут [a-l] и [h-v] то возвратится по букве и матчер выдаст сообщение о невозможности подобрать следующий символ...
\D записывается как [^0123456789]. Тут можно возвратить вообще два символа - букву и какой-нибудь служебный символ, например, тот же array('a', '?').
А что такое \L{} пока только разбираюсь... ```
Reported by `vostreltsov` on 2011-09-28 16:14:53
-
reporter
``` Ну а если [a-l ?!]\B[h-v] - \B - не граница слова? как первому классу догадываться, какая буква устроит второй? Не выкрутится так просто...
\D технически не эквивалентно [^0123456789], в каких-то кодировках могут быть другие цифры. А уж \W вообще не предскажешь, буквы какой кодировки должны использоваться... Посмотрите на их реализацию, они работают через функции...
Я бы подумал в сторону работы через match/character следующего узла, но этот код должен быть в character абстрактного класса
P.S. С кросс-тестированием все готово?
```
Reported by `oasychev` on 2011-09-29 09:32:54
-
```
как первому классу догадываться
Дык, именно поэтому и возвращается массив - потому что первый лист не может угадать. В случае \B возвратится то же самое, но пройдет уже "a\Bh". Задача листа - возвратить символы всех возможных ТИПОВ (причем максимум возвратится 3 символа), а уже матчер будет пробовать разные их комбинации. На счёт этого я точно уверен - я так делал в семестровой.
А \D и \W можно же организовать цикл, вызывая проверку очередного символа на алфавито-циферность? Или это будет долго? Извиняюсь, если пишу глупость - с юникодом пока что не сталкивался...
По кросс-тестированию: все замечания исправил. Ошибки вынесены в отдельный файл, классы переименованы. Единственное, непонятен пункт:
4) при ассертах в тестах на матчинг и ошибках не забывать включать в сообщение имя
тестируемого матчера какие ассерты имеются ввиду? ```
Reported by `vostreltsov` on 2011-09-29 10:40:22
-
reporter
``` В юникоде - сотни тысяч символов. Как бы циклом перебирать ... я бы не стал. Да и кодировка там своеобразная. И \s есть и еще много подобного. Там не 3 класса на самом деле.
Насчет типов надо подумать, но шаткая это конструкция. Про \L{} точно можно забыть... И возможно не только про нее
Ассерты имеются ввиду проверяющие правильность возвращаемых ответов. Но об этом лучше писать в соответствующей ветке ```
Reported by `oasychev` on 2011-09-29 10:48:23
-
``` Предложение по поводу match\character.
match() оставить таким же - в $length в любом случае записывать количество совпавших символов. Это же количество символов передавать в character, дав ему значение по умолчанию 0:
public function character($length = 0)
Вызовы для листьев кроме обратных ссылок править не придется. А обратная ссылка возьмет $length-й символ из подмаски... ```
Reported by `vostreltsov` on 2011-10-23 15:09:55
-
``` Да, ещё нужно знать последний совпавший\сгенерированный символ для работы простых ассертов.
public function character($previouschar, $length = 0)
Так всё же придется править вызовы для всех листьев. ```
Reported by `vostreltsov` on 2011-10-23 15:13:56
-
``` Ещё в функции consumes() я бы поменял возвращаемое значение. Чтобы на вопрос "сколько символов ты съедаешь?" она отвечала не "да\нет", а говорила сколько конкретно:) Это для вычисления длины оставшегося пути с обратными ссылками... ```
Reported by `vostreltsov` on 2011-10-23 15:18:55
-
reporter
``` Может быть лучше передать в character строку, позицию и длину? Мало ли что понадобится для след. символа... Так надежнее ИМХО. И заодно переименовать ее в next_character - поскольку все равно править вызовы, и роль ее теперь меняется.
Насчет consumes сначала надо подумать - что она должна возвращать в случае, если обратная ссылка указывает на подмаску, совпадение с которой не завершилось до того, как отказала match ? Тогда при вычислении кратчайшего пути надо вовремя снабжать матчер информацией о кратчайшей длине совпадений с подмасками... ```
Reported by `oasychev` on 2011-10-23 15:44:02
-
``` Вообще да, для обратных ссылок нужна будет строка. Придется копировать строку для каждого варианта обхода автомата и перезаписывать символы в ней на сгенерированные. Пока нет идей на счет реализации отрицательных символьных классов, могу внести изменения в интерфейс этих функций и потихоньку реализовывать обычные символьные классы.
надо вовремя снабжать матчер информацией о кратчайшей длине совпадений с подмасками...
Само собой, и это несложно сделать. ```
Reported by `vostreltsov` on 2011-10-23 17:21:10
-
reporter
``` Комментарий к next_character не корректен: $pos это не позиция последнего верного символа, а позиция начала матчинга текущего узла (для обратной ссылки будут различными значениями). Позиция последнего верного символа равна $pos + $length
Насчет кратчайшей длины совпадений с подмасками: не уверен что все так просто. Волна идет несколькими путями сразу, и нет уверенности в том, какой в результате окажется кратчайшим. Уверены что невозможно построить выражение, в котором в некоторый момент времени неясно, какую именно из возможных длин совпадений с подмасками выбирать?
Начните с тестовых примеров, особенно хитрых - а не с кода. Как и в случае генерации следующего символа. Составьте и разберите внимательно тестовые примеры, а потом уже исправляйте код... Не торопитесь - время есть, но лучше разобраться до того как сделаешь - чем переделывать потом... ```
Reported by `oasychev` on 2011-10-23 22:10:53
-
reporter
``` Валерий, давайте договоримся что все изменения в базовом классе матчера будут предварительно согласованы со мной, а потом уже коммитится в код!
И уж тем более недопустимо увязывать их в одном коммите с другими изменениями.
Чтобы вы усвоили, пожалуйста, откатите последний коммит и сделайте коммит без изменений в preg_matcher.php (кроме добавления функции если она очень вам нужна). Не первый раз это делаете уже! Пора остановится, если просто объяснений не понимаете - будем учится на опыте...
P.S. Не обижайтесь, вы молодец что работаете - лучше многих - но надо научится сначала думать и договариваться, потом делать. Напишите мне сначала свои идеи по общему устройству класса по-русски (возможно с примерами кода) и убедитесь что я не против, а потом уже кодируйте... В рамках вашего матчера у вас руки более развязаны. Но научитесь уважать области ответственности. Да и опыта у вас мало...
Зачем вам например стандартизовывать внутреннее поведение матчеров, когда match в состоянии гораздо надежнее стандартизовать его снаружи?! И даже если они внутри стандартизованы, лишний уровень проверки не помешает. Зато проблемы матчера не повлияют на работу всего вопроса, а вы делаете его код более уязвимым...
P.S. Вы проверку на количество узлов/переходов в свой матчер дописали? И добейтесь, чтобы она возвращалась так же в виде объекта ошибки (отдельный класс ошибки) и попадала в общий список ошибок (причем без вызова match, сразу после конструктора). Вот это сделать можно и нужно... ```
Reported by `oasychev` on 2011-10-26 20:49:48
-
reporter
``` Валерий, вы когда переименовывали next_character dfa подправили соответственно? Хотел вытянуть ваш код, но не вижу изменений в DFA.... Нельзя нарушать работу другого матчера (не забывайте перезапускать кросс-тесты для обоих)... ```
Reported by `oasychev` on 2011-10-29 17:55:11
-
``` Да, переименовывал. В ревизии f7496a8331f1 видно, что изменен файл dfa_preg_matcher. Кросс-тесты я временно не запускаю для дфа, потому как он зависает на циклах нулевой длины(ждем фикс от Дмитрия). Родные тесты дфа проходит. ```
Reported by `vostreltsov` on 2011-10-29 20:11:01
-
reporter
``` Извиняюсь, не заметил. ```
Reported by `oasychev` on 2011-10-29 20:28:55
-
reporter
``` Работа с изменением структуры автомата (слияние простых ассертов) откладывается до реализации общего класса конечного автомата и функций его юнит-тестирования.
Обсуждение реализации обратных ссылок должно идти в рамках issue 29.
```
Reported by `oasychev` on 2011-11-11 17:16:28 - Labels removed: Milestone-Release2.1
-
reporter
Работа с ассертами пока отходит к ЛепилкинойReported by
oasychevon 2013-08-30 19:42:21 -
reporter
Сделано, отлично.Reported by
oasychevon 2015-03-01 22:28:21 - Status changed:Done - Log in to comment
Reported by `oasychev` on 2011-09-14 14:26:42 - Labels added: Milestone-Release2.1