Какой самый эффективный способ найти относительный XPath между двумя элементами?

Question

Изучив различные популярные модули для работы с XML / XPath, мне еще предстоит найти простой способ добиться этого.

По сути, интерфейс будет выглядеть примерно так:

my $xpath = get_path($node1, $node2);

... который возвращает относительный путь от $ node1 до $ node2.

Я включаю свое собственное время в вычисление «эффективности» - я приму любое существующее решение этой проблемы. Если это не удастся, я хотел бы знать некоторые подводные камни, с которыми можно столкнуться в любых «очевидных» отечественных решениях.

Вдобавок ко всему, я мог бы вообразить, что сначала просто ищу $ node2 в потомках $ node1, а затем не удается выполнить итерацию предков $ node1, делающих то же самое. Будет ли это столь же ресурсоемким, как я боюсь?

Для моего конкретного случая использования я могу предположить, что абсолютные пути как $ node1, так и $ node2 известны. Учитывая это, я хотел бы подумать, что есть некоторая «математика XPath», которая может быть сделана между двумя полными путями без необходимости бегать по всему дереву, но я не знаю, как будет выглядеть этот процесс.

Подведем итог:

1) Какие-нибудь существующие модули CPAN облегчают то, что я хочу сделать?

2) Если нет, какой эффективный способ это сделать?

Answer 1

Найдите абсолютный путь для обоих узлов.

ref:    root foo bar[2] baz[1] moo
target: root foo bar[2] baz[2] moo

Удалите общие ведущие сегменты.

ref:    baz[1] moo
target: baz[2] moo

Для каждого сегмента в ссылке перед целевым объектом должен стоять сегмент ...

.. .. baz[2] moo

Преобразовать в XPath.

../../baz[2]/moo

---

Код:

use XML::LibXML qw( XML_ATTRIBUTE_NODE XML_ELEMENT_NODE );

sub get_path_segs {
   my ($node) = @_;
   my @path = split(/\//, $node->nodePath());
   shift(@path);
   return @path;
}

sub get_path {
   my ($ref, $targ) = @_;

   die if $ref->nodeType()  != XML_ELEMENT_NODE && $ref->nodeType()  != XML_ATTRIBUTE_NODE;
   die if $targ->nodeType() != XML_ELEMENT_NODE && $targ->nodeType() != XML_ATTRIBUTE_NODE;

   my @ref  = get_path_segs($ref);
   my @targ = get_path_segs($targ);

   while (@ref && @targ && $ref[0] eq $targ[0]) {
      shift(@ref);
      shift(@targ);
   }

   while (@ref) {
      pop(@ref);
      unshift(@targ, '..');
   }

   return @targ ? join('/', @targ) : '.';
}

В настоящее время он поддерживает узлы элементов и атрибутов.Он может быть расширен для поддержки других типов узлов, возможно, тривиально.

Answer 2

Есть два возможных результата

• два узла имеют общего предка
• один узел является потомком другого

Логический курс действий будет

• Пройдите по родительским узлам каждого узла и посмотрите, нет ли общего предка.
• При этом проверьте, действительно ли один из предков идентичен другому узлу.

В любом случае результирующий путь будет самым коротким.

Создает относительное выражение XPath из цепочек родительских узлов. Поиск привлекательного представления может быть даже самой сложной частью всей проблемы.