Конструирующий XPath? Алгоритмический XPath? Ничего, кроме XPath

    Здравствуйте, уважаемые читатели. В этой публикации речь пойдет о немного нестандартных применениях такого хорошо известного формализма как XPath. Все знают, что он очень удобен для извлечения информации из XML- или HTML- или еще каких-нибудь *ML-документов (как простых текстовых, так и каких-нибудь виртуальных, которые являются верхним слоем представления какой-либо сложной информации), то есть для того, чтобы задавать этим документам какие-либо вопросы. Однако известно, что чем лучше сформулирован вопрос, тем большую часть ответа он уже содержит. Поэтому напрашивается простая мысль – а нельзя ли использовать записанные на XPath выражения как утверждающие, то есть достраивающие документ таким образом, чтобы это XPath-выражение было истинным? Думаю можно, и это первое, о чем здесь пойдет речь. И второе – если уж мы научимся путем прямого применения XPath создавать новые элементы в документе, то нельзя ли превратить XPath в простой алгоритмический язык программирования? В самом деле, обращаться к данным умеет, создавать данные умеет. Несложно представить, как на нем описать последовательность операторов и оператор ветвления, остается подумать о циклах в нем и о функциях. Это интересно, ну хотя бы, теоретически. И об этом тоже пойдет речь.

    Конструирующий XPath


    Итак, обычный XPath описывает последовательность шагов продвижения по дереву документа, причем на каждый шаг может быть наложен фильтр-условие (предикат, записываемый в квадратных скобках). В результате получаем какое-то конечное множество узлов или число или строку или логическое значение. Нас интересует, прежде всего, случай множества узлов. Обычный XPath выдает узлы, которые уже существуют в документе. Рассмотрим гипотетический конструирующий XPath, который будет не только возвращать уже имеющиеся узлы, но еще и достраивать новые узлы таким образом, чтобы они полностью соответствовали запросу.

    Идея очень проста – на очередном шаге XPath-запроса будем анализировать фильтр-предикат и составлять варианты данных, которые под этот фильтр подпадают. А потом будем проверять, какие из этих вариантов уже существуют и достраивать несуществующие.

    Например, вот запрос:

    /OBJS/Var[@A=1 and @B=1 or @A=2 or @A=3]/X
    

    Если рассматривать его как конструирующий, то прежде всего проверим, существует ли корневой элемент <OBJS>, и, если нет – создадим. Далее идет шаг Var с фильтром. Я не буду описывать правила, по которым обрабатывается фильтр-предикат, чтобы не усложнять изложение, скажу только, что этот фильтр четко описывает три набора данных, на которых он истинен:

    1. <Var A=”1” B=”1” />
    2. <Var A=”2” />
    3. <Var A=”3” />

    Значит, нам надо сделать так, чтобы в элементе <OBJS> были дочерние элементы <Var> с такими данными. И, наконец, далее идет шаг X без условия – это означает, что необходимо, чтобы в каждом элементе Var был дочерний элемент <X>.

    Итак, все просто. В результате применения такого конструирующего XPath, например, к документу

    <OBJS>
    	<Var A=”2” />
    </OBJS>
    

    получим выходной документ:

    <OBJS>
    	<Var A=”2”>
    		<X/>
    	</Var>
    	<Var A=”1” B=”1”>
    		<X/>
    	</Var>
    	<Var A=”3”>
    		<X/>
    	</Var>
    </OBJS>
    

    И при этом мы обошлись исключительно средствами XPath, без XSL или еще чего-либо в этом роде.

    Алгоритмический XPath


    Итак, мы научили XPath создавать данные. Теперь поучим его (немного) их алгоритмически обрабатывать.

    Последовательность операторов можно описать обычным логическим AND-выражением. Оно вычисляется строго слева направо, это и есть то, что нужно. Если оно должно быть выполнено полностью, то надо просто позаботиться, чтобы все его элементы возвращали истинное выражение.

    A and B and C … and Z
    

    Условный оператор вида if(A) then B else С, разумеется (и здесь я ничего нового не скажу), можно описать логическим выражением
    A and B or C
    

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

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

    Приведу пример. Допустим, у нас есть документ, содержащих два списка чисел, описанных сериями вложенных элементов <list>:

       <a>
          <b>
             <list data="1"><list data="2"></list></list>
          </b>
          <c>
             <list data="3"><list data="4"></list></list></c>
       </a>
    

    Пусть надо сцепить списки из элемента <b> и элемента <c> и поместить результат прямо в <a>. Для этого необходимо ввести три XPath-функции:

    concat_list($#, $##): add_list(#/self::*) and add_list(##/self::*)
    
    add_list($#): count(list) = 0 and copy_list(#/self::*) or list[add_list(#/self::*)] or true()
    
    copy_list($#): count(#/list) = 0 or create(list[@data = #/list/@data]) and (list[copy_list(#/list)] or true())
    

    и добавить к ним вызывающий XPath:

    concat_list(/a/b,/a/c)
    

    Я надеюсь, что вам, уважаемые читатели, будет немного интересно разобраться в таком «коде». Единственное, что я обязательно упомяну – create(XPATH) – это системная функция, которая исполняет свой аргумент XPATH в конструирующем режиме.

    А теперь о том, что все это, конечно, интересно, но программировать так, без переменных, все- таки довольно сложно. Понимая это, я ввел полноценные переменные, которые, собственно, в XPath уже есть – они начинаются со знака «$», но я добавил возможность присваивания им значения новой функцией set. Пожалуйста, вот пример функции depth_list с двумя аргументами – ссылкой на начальный элемент, содержащий вложенный список из элементов (как в примере выше), и выходной переменной, в которую помещается длина списка:

    depth_list($#, &$OUT1): set($OUT1,0) and (#/list[set($OUT1,1) and depth_list(#/list,$OUT0) and set($OUT1,max($OUT0+1,$OUT1))]) or true()
    

    Заключение


    В появившийся в результате микроязык, который я прозвал XPath Defender, я добавил еще некоторые необходимые функции и воспользовался им в своей системе распознавания и порождения программ PGEN++ для выполнения такой важной задачи, как автоматическое достраивание модели программы, представленной в виде XML-документа. Иными словами, если есть текстовое описание некоторой задачи (для определенности — на русском языке), для решения которой надо сгенерировать программу, то это описание распознается и превращается в упорядоченный набор элементов постановки задачи (объектов с параметрами). Это первичная постановка, которая еще не содержит плана решения задачи. Распознанные элементы помещаются в XML-документ и к ним применяются правила, записанные как в виде простых ограничивающих или порождающих XPath-утверждений, так и в виде фрагментов на XPath Defender (это один из вариантов рабочего процесса). Эти правила проверяют и дополняют XML-документ-модель элементами плана решения. И уже потом по полученной модели система строит решающую программу. Эта схема успешно опробована на простых задачах математической обработки векторных данных.

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

    Подробнее
    Реклама

    Комментарии 19

      +1
      Валидационный xpath: посмотреть нет ли каких то условий, вроде:

      all(/OBJS/Var[@A is int and @A > 5] )

      и использование условий типа

      if all(/OBJS/Var[@A is int and @A > 5] ):
      /OBJS/Var[@A]
      else:
      /OBJS/Var[@B]


      concat_list($#, $##): add_list(#/self::*) and add_list(##/self::*)
      что за вырвиглаз с этим $##, не лучше просто встроить тривиальные операторы

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

      all(.objs.var.(a == 1 and b== 1). x)

      ненадо плодить лишние @#/[]<> там где можно обобйтись без.

        0
        Синтаксис — вопрос абсолютно открытый (я на своем варианте не настаиваю), если вдруг когда-нибудь эта идея дойдет до какого-то промышленного воплощения. Меня же интересовал почти исключительно вопрос о том, насколько возможна реализация идей, изложенных в посте.
          –1
          конечно возможно. Это похоже на то что проскакивало в моём хобби проэкте правда там вроде XPATHA по обьектным данным то есть а.b это b поле обьекта a но вообщем сгодится и можно расширить на любые типа структурированных данных, приходит на ум кроме XML и обьектов ещё и URI.

          Встраиваем функции типа exec (stmt) -> исполнить стейтмент, validate(stmt) -> свалидировать стейтмент, all, any, cat, etc…

          остальное легко сделать на Питоне с использованием разных плюшек типа оверлоада точки (__getitem__)
          Можен побыдлокожу так как часть этого у меня есть, только тогда будет Питоний перегруженый, то есть мой синтаксис без ненужных символов.
        +2
        достраивать новые узлы таким образом, чтобы они полностью соответствовали запросу.

        • Предикат сводит информацию, содержащуюся в документе, к True/False. C  [@A=2 or @A=3] вы что-то придумали, а как будете восстанавливать [@A>1]?
        • Выражение XPath сводит структуру элемента к списку, положим, элементов. Как будете обрабатывать // и * ?
          0
          а как будете восстанавливать [@A>1]?

          а в чём проблема, если путь привёл меня к конкретному значению a?

          Выражение XPath сводит структуру элемента к списку, положим, элементов.
          для агрегации условий по множеству значений могут использоваться any, all, notall, none или использование булевого массива как вилки в if/else которая возвращает массив значений оттуда или оттуда

          вообщем принцип как в Numpy индексировании приходит на ум.
            0
            C [@A=2 or @A=3] вы что-то придумали, а как будете восстанавливать [@A>1]?

            Такой элемент выражения может присутствовать в конструирующем XPath. Но используется он только для фильтрации на очередном шаге, порождать новых вариантов такая часть, разумеется, не будет. Она просто отсечет порожденные варианты с @A>1, если они появятся, например, [(@A=1 or @A=6) and (@A>1)] просто тогда даст единственный вариант с @A=6.
            Как будете обрабатывать // и *

            Они присутствовать могут, и рассматриваться при интерпретации/продвижении по выражению тоже будут, здесь противоречий нет. Но, конечно, "*" ничего создать не может.
              0
              Но используется он только для фильтрации на очередном шаге, порождать новых вариантов такая часть, разумеется, не будет.

              Но, конечно, "*" ничего создать не может.

              можешь поподробнее обьяснить разницу?

                +1
                Мне кажется, тут лучше быть более последовательным. Например, при использовании [@A>1], // и * кидать исключение «Порождаемый документ бесконечен из-за элемента ...».

                Кстати, Вы не думали, как формально поставить задачу, который решает Ваш инструмент? Очевидно, речь идёт не о генерации минимального XML, удовлетворяющего XPath, потому что нужно перебирать все члены дизъюнкции под [ ], но и не максимальный XML, потому что другие атрибуты и дочерние узлы, кроме упоминаемых в запросе, не добавляются.
                  0
                  Относительно формальной постановки. Думаю, так:
                  Генерация минимальных дополнений исходного XML, таких, что:
                  1. Гарантированно истиннен каждый шаг заданного XPath;
                  2. Если на шаг был наложен логический предикат [], то полученный XML удовлетворяет ВСЕМ случаям из его таблицы истинности, дающим в результате истинное значение.
                    0
                    полученный XML удовлетворяет ВСЕМ случаям из его таблицы истинности, дающим в результате истинное значение.
                    Не всем же.
                    Например, Var[@A=1 or @A=2] сгенерирует <Var A=«1»> и <Var A=«2»>, но не <Var A=«1» B=«5»>, хотя он тоже является случаем из таблицы истинности.
                    Или: Var[@A=1 or @B=2] что породит? Входит ли <Var A=«1» B=«2»> в результат? Ответ должен следовать из постановки задачи.
                      0
                      В случае Var[@A=1 or @A=2] таблица истинности предиката включает единственную переменную A, при чем же здесь B?
                      А случай Var[@A=1 or @B=2] породит три варианта:
                      A=«1»
                      B=«2»
                      A=«1» B=«2»
                        0
                        В случае Var[@A=1 or @A=2] таблица истинности предиката включает единственную переменную A, при чем же здесь B?
                        В моём понимании таблица истинности — эта таблица из двух колонок, в первой перечислены все объекты из области определения предиката (все возможные узлы в нашем случае, в т.ч. содержащие другие атрибуты, дочерние узлы и т.п.), а во второй — True/False.
                        В остальном Ваше отношение понятно.
              0
              Это вы не XQuery случайно изобрели?
                +1

                Напоминает Emmet, только вместо CSS селекторов у автора XPath.

                  0
                  Нет, по-моему, не похоже. И конструирующего XPath там нет, да и синтаксис там другой, разработчики XQuery явно не стремились к минимализму средств и разработали вполне классический алгоритмический язык.
                    0
                    Я не про синтаксис — он конечно не похожий. На самом деле было бы интересно, если бы вы прокомментировали, чем это отличается от множества известных технологий.
                      0
                      Отличается, повторюсь, применением XPath в конструирующем смысле, и минимализмом средств.
                    0

                    Полностью поддерживаю.

                    0
                    В условном «кровавом энтрепрайзе»™ мне довольно часто встречалась задача «пропатчить» буквально один узел в XML-документе (в том числе, не существующий в исходном документе). Писать для этого полноценное XSL-преобразование (или делать десериализацию в объект) совершенно не хочется. И «конструирующий XPath» здесь — то, что доктор прописал.

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

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