Как работает парсер Mediawiki


    Перевод статьи The MediaWiki parser, uncovered.

    Актуальность перевода статьи 2009 года в том, что, во-первых, костяк парсера с тех пор существенно не поменялся, и во-вторых, с ним приходится ежедневно сталкиваться тем, кто пишет расширения для Mediawiki, на котором крутятся их корпоративные сайты.
    


    Парсер Mediawiki — фундаментальная часть кода движка Mediawiki. Без него вы бы не смогли вставлять в свои статьи Википедии различные метки: секции, ссылки или картинки. Вы даже не смогли бы увидеть или быстро изменить разметку других статей. Вики-разметка достаточно гибка, чтобы дать возможность одинаково легко писать статьи как новичкам, так и HTML-экспертам. Из-за этого код парсера несколько сложноват, и с годами проходил через множество попыток его улучшить. Тем не менее, даже сегодня он все еще достаточно быстро работает для Википедии, одного из самых больших веб-сайтов в мире. Давайте взглянем на внутренности этого ценного (но чуть-чуть заумного) куска кода.


    Краткая история

    Дисклеймер. Эта история, как я ее понимаю, в основном почерпнута из обсуждений, в которых я участвовал в течение долгих лет в рассылке Викимедии, а также из обсуждений на конференции Викимания 2006. До 2008 года парсер Mediawiki сильно страдал от необычайной сложности, которая проистекала из необходимости уложиться в один проход (для скорости), но также и из-за того, что в существующий код всё время добавляли новые правила. С течением времени код парсера стал настоящим спагетти-кодом, который было очень сложно отлаживать, и еще сложнее улучшать. Переписать его было практически невозможно, т.к. он относится к ядру движка. Миллионы страниц Википедии могли полететь в один момент, если бы в каком-то месте нового кода произошла ошибка.

    Что делать

    Разразилось множество дискуссий о том, как решить эту проблему. Кто-то предлагал переписать парсер на C, который бы сделал парсер быстрее, что позволило бы разрешить парсеру разбирать текст не за один проход, а в цикле — этого требовало нарастающее число шаблонов и подшаблонов, которые включались на страницах Википедии. Были также и предложения изменить синтаксис Mediawiki так, чтобы устранить неопределенности при разборе некоторых конструкций (как, например, '''''жирный или курсив?''жирный или курсив?''''' или отношения между тройными и двойными фигурными скобками в шаблонах).
    В конце концов было решено, и я считаю это блестящей идеей, оставить парсер на PHP (т.к. переписывание его на C привело бы к разделению разработчиков Mediawiki на 2 класса) и разделению парсинга на два этапа, препроцессинг и парсинг. Работой препроцессора стало представление викитекста в виде XML DOM. На этапе собственно парсинга происходила обработка дерева DOM в цикле из стольких итераций, сколько требовалось (для подстановки шаблонов. к примеру), чтобы получить валидный статический HTML. Прохождение в цикле по DOM невероятно быстро, и кроме того это очень естественно с точки зрения XHTML. И в PHP такую обработку тоже очень хорошо поддерживает.

    Препроцессор

    В папке исходников Mediawiki вы найдете две версии препроцессора, версию Hash и DOM, их можно найти соответственно по адресам /includes/parser/Preprocessor_Hash.php и /includes/parser/Preprocessor_DOM.php.
    Мы сконцентрируемся на DOM-версии, так как она практически идентична Hash-версии, но работает быстрее, потому что пользуется PHP XML-поддержкой, опциональной компонентой PHP. Самая важная функция в классе препроцессора назвается preprocessToObj(). Внутри файла Preprocessor_DOM.php лежат несколько других важных классов, которые использует препроцессор: PPDStack, PPDStackElement, PPDPart, PPFrame_DOM и PPNode_DOM.

    Препроцессор делает меньше, чем вы думаете

    Итак, на что же походит Mediawiki XML? Вот пример того, как викитекст "{{МойШаблон}} это [[тест]]" выглядит в XML-представлении:
    <root>
      <template>
        <title>mytemplate</title>
       </template>
      this is a [[test]]
    </root>
    


    Заметим. что внутренняя ссылка вообще не обрабатывается. Код препроцессора избегает той работы, которую можно сделать на более позднем этапе (и у него есть для этого основания), так что единственной настоящей работой препроцессора является создание XML элементов для шаблонов и парочки других вещей. Вот эти вещи, т.е. базовые узлы (полный перечень): template, tplarg, comment, ext, ignore, h.

    Если вы когда-либо работали с викитекстом, то уже знаете, какая разметка соответствует этим базовым узлам. На всякий случай, вот она:

    • template = двойные фигурные скобки {{...}}
    • tplarg = тройные фигурные скобки {{{...}}}
    • comment = HTML-комментарий любого типа
    • ext = Всё, что должно разбираться в отдельном расширении
    • ignore = теги типа noinclude, а также теги includeonly и содержимое внутри них
    • h = секции


    Вот и все. Все остальное игнорируется и возвращается как исходный викитекст в парсер.

    Как работает препроцессор

    Тут нет ничего особенного, но стоит сказать несколько слов. Для того, чтобы получить XML-представление, нужное нам, препроцессор проходит викитекст в цикле столько раз, сколько символов содержит этот текст. Нет другого способа для корректной обработки рекурсивных шаблонов, которые могут быть представлены как угодно в тексте благодаря синтаксису. Так что, если статья в Википедии содержит 40 000 знаков, то вероятно, что цикл будет состоять из 40 000 итераций. Теперь понятно, почему скорость так важна для парсера.

    Собственно парсинг

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

    Вот типичное дерево вызовов парсера для текущей версии страницы, начиная от объекта Article.
    01. Article->view
    02. --Article->getContent
    03. ----Article->loadContent
    04. ------Article->fetchContent->возвращает викитекст, извлеченный из БД
    05. --Article->outputWikiText->prepare for the parse
    06. ----Parser->parse
    07. ------Parser->internalParse
    08. --------Parser->replaceVariables
    09. ----------Parser->preprocessToDom
    10. ------------Preprocessor->preprocessToObj
    11. ----------Frame->expand
    12. --------Parser->doTableStuff
    13. --------Parser->replaceInternalLinks
    14. --------Parser->replaceExternalLinks
    15. ------Parser->doBlockLevels
    16. ------Parser->replaceLinkHolders


    Давайте взлянем на эти функции. Снова, это главные функции, а не все, которые вызываются в данном примере. Пункты 2-4 извлекают и возвращают викитекст статьи из базы данных. Этот текст передается объекту outputWikiText, который подготавливает его для передачи функции Parser::parse().
    Далее снова интересно становится на пунктах 8-11. Внутри функции replaceVariables текст превращается в представление DOM, в цикле по каждому символу статьи ищутся начальные и конечные метки шаблонов, подшаблонов и других узлов, упомянутых выше.

    Пункт номер 11 — интересный шаг, который я сейчас пропущу, потому что он требует некоторых знаний о других классах из файла Preprocessor_DOM.php (упомянутых выше). Expand — очень важная функция, делает кучу вещей (среди которых её рекурсивный вызов), но достаточно сказать, что она выполняет работу по фактическому извлечению текста из узлов DOM (мы помним. что шаблоны могут быть вложенными — так что вы не всегда получите полный текст из каждой включенной статьи) и воврату валидного HTML-текста, в котором раскрыты все вики-метки, за исключением трех видов: таблиц, ссылок и списков. Так что, в примере выше, "{{МойШаблон}} это [[тест]]" expand() вернет текст вида:

    «Я включил [[текст]] из моего шаблона, это [[тест]]»

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

    Ссылки — это особенный случай

    Да, у ссылок есть своя отдельная секция. И не только потому, что они, пожалуй, самая существенная часть того, что делает из wiki её саму (помимо возможности редактирования). Но еще и потому, что они разбираются совершенно особенным от всей остальной разметки образом в коде парсера. Особенными их делает то, что они обрабатываются в два этапа: на первом этапе каждой ссылке присваивается уникальный id, а на втором этапе её валидный HTML вставляется на место «заместителя ссылки» (link holder). В нашем примере вот какой результат получается после первого этапа:

    «Я включил <!--LINK 0--> из моего шаблона, это <!--LINK 1-->».

    Как вы можете представить, существует также массив, который сопоставляет текст ссылок с их ID вида LINK #ID, это переменная класса Parser с именем mLinkHolders. Помимо сопоставления, эта переменная также хранит объекты Title для каждой ссылки.

    Так что на втором этапе разбора ссылок мы используем этот массив для простого поиска и замены. Теперь всё! Отправляем готовый текст за дверь!

    Следующий этап

    В следующем посте я сконцентрируюсь больше на препроцессоре и деталях классов из файла Preprocessor__DOM.php, а именно как они используются для построения первоначального дерева DOM XML. Я также расскажу о том, как я воспользовался ими для кеширования инфобоксов в расширении Unbox.
    Поделиться публикацией

    Похожие публикации

    Комментарии 17
      +2
      > Переписать его было практически невозможно, т.к. он относится к ядру движка. Миллионы страниц Википедии могли полететь в один момент, если бы в каком-то месте нового кода произошла ошибка.

      Довольно странный аргумент.

      Статья не оформлена как перевод.

      А где ссылка на сам парсер?
        +2
        Спасибо за замечания.

        Я добавила ссылки на документацию к парсеру и текущий релиз Mediawiki в начале статьи. На всякий случай привожу их здесь:

        svn.wikimedia.org/doc/classParser.html — документация к классу Parser
        www.mediawiki.org/wiki/Download — текущий релиз Mediawiki

        Что касается ошибки оформления — я пробую её исправить, но безуспешно. Тип существующей статьи, похоже изменить нельзя — только убирать эту и создавать новую. Но ведь её уже кто-то добавил в избранное — и ссылка будет не работать… Подскажете, как исправить ситуацию?

        Забавно, что в данном случае возникает намек на ту же проблему, что и в процитированном тексте. Вот его оригинал:
        Rewriting it was made almost impossible by the fact that it was so essential to the software. Millions of pages on Wikipedia could have easily been made garbldy-gook in an instant if changes were not handled correctly.

        Мой перевод был, возможно, слишком вольным. Здесь, видимо, имеется в виду больше не проблема случайного бага, а непродуманный отказ от поддержки какой-нибудь из устаревших функций или синтаксических конструкций викитекста.
          –1
          Не нужно ничего менять. Администрация, по крайней мере, на сентябрь 2011, не имеет ничего против переводов, оформленных как топики. В обоих случаях для автора есть и плюсы, и минусы. Те, кто считают, что в оформлении перевода как обычного топика, есть какой-то сакральный смысл и корыстный умысел автора, должны навестить психиатра.
          Сам публиковал пару переводов, вышедших в топ-1 за сутки, как топики. Меня просто засрали ЛСками с замечаниями по этому поводу. Идиоты.
            +1
            > и корыстный умысел автора

            Ну как же! Вдвое больше бабла можно заработать :-)
              0
              Мне, например, просто так удобнее и эстетически приятнее. Зато топик позже переходит в «захабренные».
              И публиковал я таким образом не третьесортный надмозг, а большие, размашистые и очень качественно переведенные статьи.
              А в монетизации я и не учавствую.
            0
            А, всё понятно, спасибо.
            +8
            При том, что Википедия — одно из величайших изобретений, MediaWiki — угрёбищное порождение php-дегенератов.

            Не верите? Цитирую небольшую программку (реальный шаблон), написанную на их markup-language:

            {{rq/|{{{1|}}}|{{{nocat|}}}}}{{rq/|{{{2|}}}|{{{nocat|}}}}}{{rq/|{{{3|}}}|{{{nocat|}}}}}{{rq/|{{{4|}}}|{{{nocat|}}}}}{{rq/|{{{5|}}}|{{{nocat|}}}}}{{rq/|{{{6|}}}|{{{nocat|}}}}}{{rq/|{{{7|}}}|{{{nocat|}}}}}{{rq/|{{{8|}}}|{{{nocat|}}}}}{{rq/|{{{9|}}}|{{{nocat|}}}}}{{rq/|{{{10|}}}|{{{nocat|}}}}}{{rq/|{{{11|}}}|{{{nocat|}}}}}{{rq/|{{{12|}}}|{{{nocat|}}}}}{{rq/|{{{13|}}}|{{{nocat|}}}}}{{rq/|{{{14|}}}|{{{nocat|}}}}}{{rq/|{{{15|}}}|{{{nocat|}}}}}{{rq/|{{{16|}}}|{{{nocat|}}}}}

            Всего то делает:

            if exists rq/$1: include $1
            if exists rq/$2: include $2


              0
              Взяли бы исходники Blitz и допилили под свой синтаксис. Я думаю это вполне реально.
                0
                Можете объяснить, как этот шаблон работает? %)
                  0
                  Всё-таки не совсем это, а вот такие вызовы подшаблонов:

                  rq/(1, nocat)
                  rq/(2, nocat)


                  (Да, это я всё это писал.)
                    +1
                    Только когда используешь всё это, другим юзерам-непрограммистам вся эта викиразметка снится в страшном сне и кажется, что всё можно было бы сделать намного проще. Но вот, что на самом деле скрывается под одной строчкой псевдокода if exists rq/$1: include rq/($1, nocat):

                    if 1 in args and args[1].strip():
                        if exist('Шаблон:Rq/' + args[1]):
                            include_template('Шаблон:Rq/' + args[1], args['nocat'] if args.get('nocat', '').strip() else ''):
                        else:
                            print("<span style=\"color:#F00\">'''Неверный параметр шаблона {{tl|rq}} — ''[[Шаблон:rq/%1|%1]]''. Проверьте исходный текст и обратитесь к [[Шаблон:rq/doc|документации]].'''</span>" % args[1])
                    
                            if not args.get('nocat', '').strip() and parser.namespace == 0:
                                print("[[Категория:Википедия:Статьи с некорректным использованием шаблона rq]]")
                    

                    При всём желании на lua не получится написать изящнее, чем на python. Хотя как вспомогательный язык, lua будет хорошим дополнением.
                  0
                  Либо перевод неточный/неправильный, либо я что-то не понимаю. Двойной парсинг это же просто пипец как тормозно будет. Видимо всётаки они не «парсят в xml» а просто строят дом-дерево на основе лексики вики и на самом деле никакого xml нет. Есть структура в памяти.
                    +2
                    Парсеру не нужно работать правильно, ему нужно работать правильно на всех существующих страницах. Так что можно написать новый парсер и прогнать его на всех страницах. Расхождения исправить в одном из парсеров или на странице.
                    Про 40000 проходов для статьи в 40000 символов я что-то не понял. Практические языки обычно парсят за линейное время. Для подстановок нужно столько проходов, какова их максимальная глубина.
                      0
                      > Так что можно написать новый парсер и прогнать его на всех страницах.
                      > Практические языки обычно парсят за линейное время.

                      Беда в том, что нет даже полного словесного описания грамматики, не говоря уже о формальном описании, а вносимые изменения не документируются, их просто негде документировать. Да и в целом, нет какого-то принципа согласно которому развивается язык.

                      Если бы это было, уже бы понаписали 9000 и 1 парсер на всяких разных языках, хотя бы один уж точно оказался удачным. А так, чёрт его знает, какого типа парсер писать, как восстановить грамматику из PHP-лапши, как это всё потом поддерживать и что делать если вдруг бравые кодеры Mediawiki внесут изменения в язык, непереносимые в наш замечательный парсер, и придётся всё начинать заново.
                        0
                        Речь идет о том, чтобы просто убедиться, что на существующих страницах новый парсер дает в точности тот же результат, что и старый.
                      0
                      Ну вот, только разогнался, а тут конец поста! :)

                      Ранее имел опыт написания расширений MediaWiki, частично постиг творящуюся там магию, но на полное освоение меня не хватило — разбираться в возникающих в последствии странностях я не стал. :)
                        0
                        Только Markdown, только хардкор!

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

                        Самое читаемое