Реализация
Предложенный в данной статье язык модификации XML-документов был реализован фукнциональными методами программирования на языке функционального программирования Scheme.
Необходимо заметить, что функциональный стиль программирования подразумевает определенные правила, накладываемые на сделанную реализацию. А именно, чистый функциональный стиль запрещает использование в программе таких побочных эффектов, как изменение значений, однажды связанных с глобальными идентификаторами. В контексте выполненной реализации языка модификации функциональный стиль программирования означает сохранение в неизменном виде документа, подлежащего модификации, и конструирование нового документа, выражающего собой результат вычисление требуемого запроса на модификацию к исходному документу.
В отличие от процедурной и объектно-ориентированной парадигм программирования, в которых модификация обычно реализуется как принудительное изменение исходных данных, функциональная парадигма программирования позволяет гарантировать, что данные, однажды связанные с идентификатором, останутся постоянными на протяжении всего времени, пока к этим данным есть доступ из какой-либо области программы[]. Это свойство функционального программирования обладает тем важным преимуществом, что конструирование дерева модифицированного документа не требует глубокого копирования дерева исходного документа, и части, являющиеся общими для обоих деревьев, автоматически хранятся в единственной физической копии.
Возможность использования физически разделяемого поддерева, общего для нескольких деревьев, иллюстрируется на рис. 2. Предположим, что некоторый запрос на модификацию затрагивает узел, обозначенный на рис. 2 буквой О. Тогда в результате выполнения запроса на модификацию будут переконструированы только те части дерева обрабатываемого документа, которые обозначены на рис. 2 жирными линиями, а остальные части дерева останутся неизменными и, таким образом, будут существовать в разделяемой физической копии для исходного и сконструированного деревьев.
Из рис. 2 легко видеть, что модификация в SXML-документе некоторого узла затрагивает изменение этого узла и всех его узлов-предков. Поскольку на практике глубина XML-документов и соответствующих им SXML-документов обычно бывает небольшой, выполнение запроса на модификацию, выбирающего в документе лишь несколько узлов в качестве обрабатываемых, требует переконструирования только небольшой части модифицируемого документа. Узлы, остающиеся неизменными для исходной и модифицированной версий документа, существуют в единственной физической копии, и обе версии документа адресуются к этим узлам по ссылкам.
Рис. 2: Пример дерева SXML-документа, в которым производится модификация узла. Буквой O обозначен обрабатываемый узел, жирными линиями выделены те части дерева, которые изменяются в результате модификации
В зависимости от конкретной прикладной задачи, приложение, использующее функциональную реализацию предлагаемого языка запросов, само определяет, каким образом обрабатывать исходную и сконструированную новую версию модифицируемого SXML-документа. Например, приложение может использовать исходную версию документа только в локальном блоке своего кода, и тогда узлы, специфичные для исходной версии документа и не используемые в других местах прикладной программы, будут освобождены автоматическим сборщиком мусора []. Соображения по вопросу обеспечения конкурентной обработки общего SXML-документа несколькими приложениями обсуждается в разделе .
В сделанной реализации вычисление запроса на модификацию SXML-документа осуществляется в следующие два этапа:
На первом этапе все обработчики сопоставляются с соответствующими им обрабатываемыми узлами, т.е. для каждой операции модификации вычисляется выражение_XPath этой операции относительно соответствующего базового узла. Заметим, что выработанный способ задания базовых узлов позволяет не вызывать ни одного обработчика при определении базовых узлов для всех операций модификации.
На втором этапе осуществляется обход дерева SXML-документа, для обрабатываемых узлов вызываются обработчики, и в соответствии с возвращаемыми результатами обработчиков конструируется дерево нового SXML-документа, соответствующего результату выполнения запроса на модификацию над исходным документом.
При вычислении выражений XPath, производимом на первом этапе обработки запроса на модификацию, желательно для каждого узла, выбранного выражением XPath, получить также все его узлы-предки, поскольку, как отмечалось выше, предков обрабатываемого узла в новой версии SXML-документа необходимо переконструировать. Для получения предков для узлов, адресуемых с помощью выражения XPath, была выбрана реализация XPath функциональными методами, обеспечивающая хранение предков контекстного узла в контексте вычисления и, благодаря этому, оптимизирующая вычисление обратных осей XPath []. Упомянутая реализация XPath позволяет получить результат вычисления выражения XPath в форме наборов контекстов, которые содержат всех предков для каждого из выбранных узлов SXML-документа.
Наличие известных предков каждого из обрабатываемых узлов позволяет организовать целенаправленный обход дерева SXML-документа на втором этапе обработки запроса на модификацию. А именно, благодаря тому, что корень дерева обрабатываемого документа является предком для каждого из обрабатываемого узлов, и обход дерева осуществляется сверху вниз, для любого поддерева можно сразу же установить, какие из обрабатываемых узлов располагаются внутри данного поддерева. Если в некотором поддереве не содержится ни одного обрабатываемого узла, то обход поддерева вниз может быть прекращен, потому что поддерево остается неизменным в результате выполнения запроса на модификацию.
Необходимо отметить, что семантика предлагаемого языка модификаций не противоречит тому, чтобы с одним и тем же узлом документа было ассоциировано сразу несколько обработчиков. Когда имеется несколько обработчиков, ассоциированных с одним узлом, результатом обработки данного узла служит суперпозиция применения обработчиков, и принимается следующая очередность применения обработчиков к узлу:
Если какие-то два обработчика относятся к разным операциям модификации, то эти обработчики применяются в том порядке, в каком они записаны в запросе на модификацию;
Если два обработчика относятся к одной операции модификации, то ввиду отсутствия совпадающих узлов в результате вычисления выражения XPath этим обработчикам с необходимостью соответствуют разные базовые узлы. Для обработчиков, относящихся к одной операции модификации, очередность их применения принимается совпадающей с очередностью, которую имеют соответствующие обработчикам базовые узлы в порядке документа [], подлежащего модификации.
Введенная очередность применения обработчиков позволяет ввести логичную и интуитивно ясную семантику операции перемещения поддеревьев. А именно, ситуации, когда с одним узлом ассоциировано несколько обработчиков одной и той же операции модификации, соответствует такой запрос на перемещение, при котором несколько разных поддеревьев перемещается на общее новое место. Например, если все сноски в электронном представлении некоторой книги перемещаются в главу “Приложение”, то в соответствии с принятым соглашением об очередности применения обработчиков сноски попадут в эту главу в точности в том порядке, в котором они встречались по тексту, что полностью согласуется с интуитивным представлением об ожидаемом результате перемещения.
Выполненная реализация языка модификаций обеспечивает проверку корректности производимых модификаций в соответствии с условиями правильной сформированности XML-документов (XML well-formedness) []. В частности, производится проверка на отсутствие дублирующих атрибутов у данного элемента и атомарность значений атрибутов. По аналогии с языком запросов к XML-документам XQuery [], сделанная реализация языка модификаций разрешает приложению в результате модификации элемента записывать его атрибуты и прочее содержимое в произвольном порядке. Поскольку в синтаксисе SXML атрибуты данного элемента должны быть вложены в общий список атрибутов, непосредственно следующий за именем элемента, реализация производит объединение списков атрибутов, если в результате модификации у данного элемента их получилось несколько, и переносит список объединенных атрибутов в позицию, непосредственно следующую за именем элемента и предшествующую всему прочего содержимому.
