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

Поддержка якорения выражения

Issue #5 closed
Oleg Sychev repo owner created an issue

Originally reported on Google Code with ID 5

Существующая поддержка якорей учитывает лишь заякорение всего выражения. Это необязательно,
ср. например выражение:
^abc$|123|^ijk|xyz$
Оно содержит набор альтернатив, не все из которых заякорены. Существующая система не
поддерживает такие выражения!

Reported by oasychev on 2010-09-20 09:12:50

Comments (26)

  1. Oleg Sychev reporter

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

    Это также может означать что удобнее будет предварительно провести рефакторинг DFA-matcher. ```

    Reported by `oasychev` on 2010-09-20 09:51:04 - Blocked on: #

  2. Oleg Sychev reporter

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

    Reported by `oasychev` on 2010-09-21 11:29:50

  3. Oleg Sychev reporter

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

    Reported by `oasychev` on 2010-09-28 20:26:26 - Labels added: Priority-High, Functionality - Labels removed: Priority-Critical, Usability

  4. Former user Account Deleted

    ``` Удобнее всего будет исправить это в конце рефакторинга или сразу после него, это уже вопрос терминологии. Кстати, у меня .* автоматически не якорится, это можно сделать, но выигрыш в производительности будет невелик, т.к. основное время занимает построение ДКА. ```

    Reported by `Xapuyc7` on 2010-09-29 06:21:14

  5. Oleg Sychev reporter

    ``` Согласен, что в процессе рефакторинга оно легко станет на место.

    Выигрыш в производительности может быть: вы замеряли производительность когда все ваши выражения были заякорены автоматически, цикла перебора тогда еще не было. С циклом перебора .* в начале выражения может отнять довольно серьезное время.

    Но это можно чуть позже сделать. Главное сейчас - рефакторинг. ```

    Reported by `oasychev` on 2010-09-30 09:54:54

  6. Oleg Sychev reporter

    ``` В абстрактный класс матчера добавлена функция look_for_anchors() которая должна выполнить оставшуюся работу: определить наличие глобального якорения для всего выражения путем анализа дерева. ```

    Reported by `oasychev` on 2011-05-06 23:15:17

  7. Oleg Sychev reporter

    ``` Задача стала более общей, поэтому переименовываю issue и выношу на общий уровень. Общие задачи будем распределять равномерно...

    Необходимо в базовом классе матчера реализовать определение якорения выражения. Выражение считается заякоренным в начале если все его альтернативы верхнего уровня начинаются с ^ или .* (аналогично в конце - оканчиваются на $ или .*).

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

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

    Reported by `oasychev` on 2011-09-06 21:01:14

  8. Oleg Sychev reporter

    Reported by `oasychev` on 2011-09-06 21:04:52 - Labels added: Performance - Labels removed: Functionality

  9. Oleg Sychev reporter

    ``` Теме задан новый владелец в соответствии с распределением задач. Собственно задача описана в комментарии 7.

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

    P.S. Тесты (касается всех) можно передать мне на любом моем занятии - см. расписание 2 и 4 курса. Если занятие последнее и потом нет пересдачи, то можно и сразу обсудить... ```

    Reported by `oasychev` on 2011-09-09 13:08:03 - Labels added: Type-Enhancement - Labels removed: Type-Defect

  10. Oleg Sychev reporter

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

    Reported by `oasychev` on 2011-09-09 13:13:00

  12. Oleg Sychev reporter

    ``` Мы хотя бы к 2.2 это получим, Алексей? ```

    Reported by `oasychev` on 2011-11-20 10:16:31 - Labels added: Milestone-Release2.2 - Labels removed: Milestone-Release2.1

  13. Oleg Sychev reporter

    ``` Спасибо Валерию за реализацию поиска якорения начала выражения. Вот только юнит-тесты на это дело есть? ```

    Reported by `oasychev` on 2012-08-06 22:11:32 - Status changed: `InProgress` - Blocked on: #3 - No longer blocked on: #3

  15. Oleg Sychev reporter

    ``` Добавил тесты на фейлы якорения - а то только на истину слишком легко. Запустить пока неначем - проверьте сами.

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

    Reported by `oasychev` on 2012-09-25 09:17:21

  16. Valeriy Streltsov

    ``` Ваши тесты прошли. На счет закомменченного теста вы правы, я доработал функцию в хендлере, раскомментил этот тест и добавил еще один на вложенный случай типа a|b|(|c).

    (Кстати, я пофиксил парсер - допускаются конструкции вида (|a|) - правда тесты матчера запустить не получилось - вы переименовали метод в вопросе и теперь PHP ругается, что наш вопрос абстрактный. Тесты парсера прошли успешно) ```

    Reported by `vostreltsov` on 2012-09-25 16:20:59

  17. Oleg Sychev reporter

    ``` Вот теперь сделано... ```

    Reported by `oasychev` on 2012-09-28 12:04:09 - Status changed: `Done`

  18. Valeriy Streltsov 
    Проблема с (abc|)ef была вызвана как раз ситуацией альтернативы с пустотой: дальше первого
символа в строке "abcdef" оно просто не искало совпадение. Оно и верно - альтернатива-то
совпала с пустотой, дальше нужно совпадение с ef в автомате... А дальше первого символа
строка не просматривается. Ставлю пока fixed, если согласны - переводите обратно в
done.

    Reported by vostreltsov on 2012-11-05 15:14:59 - Status changed: Fixed

  19. Oleg Sychev reporter 
    Я догадывался что там может быть проблема с якорением. 

Альтернатива с пустотой при якорении должна работать только в ситуации, когда все выражение
совпадает с пустотой, а не только начало.

    Reported by oasychev on 2012-11-07 08:08:09

  20. Oleg Sychev reporter 
    Можете подправить якорение с пустотой так, как в комментарии 19?

    Reported by oasychev on 2012-11-07 08:12:31

  23. Oleg Sychev reporter 
    Валерий, а не лучше ли сделать передаваемый флажок в рекурсивную функцию "была ли конкатенация"
($wasconcat да/нет), вместо массива предыдущих узлов то? При первом вызове ложь (можно
по умолчанию сделать), все узлы передают что приняли, кроме конкатенации которая устанавливает
в true.

    Reported by oasychev on 2012-11-08 15:38:05

  24. Valeriy Streltsov 
    Спасибо, исправил. Сразу как-то не додумался так сделать.

    Reported by vostreltsov on 2012-11-08 15:58:08

  26. Oleg Sychev reporter 
    Валерий:
Перед тем, как проверять подтип, следовало проверить и тип узла, а то не у всех операторов
подтипы есть. В НКА это выжило благодаря особой структуре дерева, а в ДКА при удалении
подмасок вызывало исключение...

    Reported by oasychev on 2012-11-12 14:29:12

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