Реализация рекурсии

[Valeriy Streltsov]

Originally reported on Google Code with ID 255

В общем-то делается достаточно элементарно, по идее.

1) После построения автомата создаем карту: номер подвыражения => массивы начальных
и конечных состояний
2) Во внутреннюю функцию матчинга передаем номер подвыражения
3) Интерфейс, с которым работают листья, расширяем функцией матчинга - рекурсивный
лист будет её использовать
4) При генерации рекурсия всегда возвращает невозможность генерации, так ведь?

Reported by vostreltsov on 2014-01-20 09:45:41

[Valeriy Streltsov]

Да, можно еще передавать в функцию матчинга текущий уровень рекурсии и контролировать
его... Соответственно сделать настройку в самом вопросе.

Reported by vostreltsov on 2014-01-20 09:48:24

[Oleg Sychev]

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

Reported by oasychev on 2014-01-20 17:18:29

[Oleg Sychev]

1-3 примерно так; полагаю будет полезным иметь карту подвыражение=>начальный узел -
не искать же его каждый раз по автомату...

Но это после релиза наверное? Или думаете сделать быстро совсем?

Reported by oasychev on 2014-01-21 20:00:12

[Valeriy Streltsov]

На днях посмотрю, матчинг по идее точно быстро делается, генерация не знаю

Reported by vostreltsov on 2014-01-21 20:44:21

[Oleg Sychev]

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

Reported by oasychev on 2014-01-21 22:06:43

[Valeriy Streltsov]

PCRE ведет себя странновато при вызове подвыражений.

[valeriy@homepc ~]$ pcretest in
PCRE version 8.34 2013-12-15

/^(?|(abc)|(def))(?1)/
    abcabc\P
 0: abcabc
 1: abc

[valeriy@homepc ~]$ pcretest in
PCRE version 8.34 2013-12-15

/^(?|(abc)|(def))(?1)/
    def\P
Partial match: def
[valeriy@homepc ~]$

[valeriy@homepc ~]$ pcretest in
PCRE version 8.34 2013-12-15

/^(?|(abc)|(def))(?1)/
    defdef\P
No match

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

Добавляем флаг дублированности в узлы?

Reported by vostreltsov on 2014-01-30 13:33:57

[Valeriy Streltsov]

Кстати говоря предлагаю тогда флаги узлов хранить тоже побитово. Caseless туда же...

Reported by vostreltsov on 2014-01-30 13:35:29

[Valeriy Streltsov]

Пишу сюда выясненные подробности работы рекурсии в PCRE. На верхних уровнях рекурсии
оно не запоминает, что совпало на вложенных уровнях. Пример:

$matches = array();
preg_match('/(a(?1)|(b))(c)/', 'abc', $matches, PREG_OFFSET_CAPTURE);
var_dump($matches);

array(4) {
  [0]=>
  array(2) {
    [0]=>
    string(3) "abc"
    [1]=>
    int(0)
  }
  [1]=>
  array(2) {
    [0]=>
    string(2) "ab"
    [1]=>
    int(0)
  }
  [2]=>
  array(2) {
    [0]=>
    string(0) ""
    [1]=>
    int(-1)
  }
  [3]=>
  array(2) {
    [0]=>
    string(1) "c"
    [1]=>
    int(2)
  }
}

Это очень хорошо. При расстановке индексов\длин в массиве $matches в qtype_preg_fa_exec_state
мы имеем дело только с тем, что совпало на текущем уровне рекурсии.

Reported by vostreltsov on 2014-11-16 18:01:00

[Valeriy Streltsov]

Аналогично касается и дублированных номеров подвыражений:

$matches = array();
preg_match('/(?|(a)(?R)|(b))/', 'ab', $matches, PREG_OFFSET_CAPTURE);
var_dump($matches);

array(2) {
  [0]=>
  array(2) {
    [0]=>
    string(2) "ab"
    [1]=>
    int(0)
  }
  [1]=>
  array(2) {
    [0]=>
    string(1) "a"
    [1]=>
    int(0)
  }
}

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

Reported by vostreltsov on 2014-11-16 18:05:13

[Valeriy Streltsov]

Ок, изменяем всё на уровне qtype_preg_fa_exec_state.

В этом классе оставляем $matcher, $startpos, $length, $flags, $left, $extendedmatch,
$str - это либо глобальные данные.

Дополнительно добавляем поле $stack. Оно будет состоять минимум из одного объекта нового
класса qtype_preg_fa_exec_state_stack_item. На каждый уровень рекурсии или вызова подвыражения
- один item. В этом классе будут поля $state, $matches, $subexpr_to_subpatt, $last_transition,
$last_match_len, $backtrack_states.

Reported by vostreltsov on 2014-11-16 18:07:19

[Valeriy Streltsov]

Теперь вопрос - как собственно сделать рекурсивный вызов используя узлы?

Вот есть curstate, он смотрит на переход по рекурсивному вызову. В результате нужно
получить массив новых состояний, поскольку у нас может быть несколько начальных состояний
для одного подвыражения. Внутри функции match это сделать легко, но хотелось бы через
имеющийся интерфейс https://code.google.com/r/vostreltsov-preg-28/source/browse/question/type/preg/preg_nodes.php#228
 и узлы.

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

Reported by vostreltsov on 2014-11-27 12:50:36

[Oleg Sychev]

Я не думаю, что preg_nodes.php должен что-то знать про состояния автомата - с точки
зрения инкапсуляции это должно находится как минимум в потомках их уже в КА-узлах.

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

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

Reported by oasychev on 2014-11-27 21:54:34

[Valeriy Streltsov]

Новая проблема из-за смёрженных Лениных переходов. Не получится взять и все подряд их
сматчить, потому что для обычных переходов это вызов листовой функции, а рекурсия вообще
размазывается по уже запущенной match_from_pos. С вариантом рекурсивных вызовов match_from_pos
было бы всё-таки проще.

Reported by vostreltsov on 2014-11-28 08:50:26

[Valeriy Streltsov]

Reported by vostreltsov on 2014-12-04 09:16:06 - Status changed: Fixed

[Oleg Sychev]

Fixed будет когда простестим хорошо с помощью шаблонов и разберемся полностью с теорией
приоритета рекурсивных тегов.

Reported by oasychev on 2015-03-01 22:35:52 - Status changed: InProgress

[Valeriy Streltsov]

(b(?1)?)(b*) на строке "bbbbbb" должно все символы отдать рекурсии, правильно?

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

Reported by vostreltsov on 2015-03-02 19:33:09

[Valeriy Streltsov]

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

Reported by vostreltsov on 2015-03-02 20:08:16

[Valeriy Streltsov]

Имелось ввиду (b?(?1)?)

Reported by vostreltsov on 2015-03-02 20:27:16

[Oleg Sychev]

Done? Или зацикливание на (b?(?1)?) осталось?

Reported by oasychev on 2015-07-03 19:22:03 - Status changed: Fixed

[Valeriy Streltsov]

Не зависает. Но строка bbbb... длиной 40 символов обрабатывается секунд 5. Я думаю это
просто один из worst case'ов.

Reported by vostreltsov on 2015-07-03 19:41:31

[Valeriy Streltsov]

Reported by vostreltsov on 2015-07-03 20:01:17 - Status changed: Done