Re: [xsl] Can I use xsl:key to select elements up to certain ancestor

Subject: Re: [xsl] Can I use xsl:key to select elements up to certain ancestor
From: "Michael Kay mike@xxxxxxxxxxxx" <xsl-list-service@xxxxxxxxxxxxxxxxxxxxxx>
Date: Wed, 30 Aug 2017 22:20:00 -0000
> And then I was doing the following to find all ancestors that share the same
"topic ancestor":
>
> <xsl:variable name="ancestors-in-topic"
>  select="ancestor-or-self::*[ancestor-or-self::* = $topic]"
as="element()*"/>
>
> This did not what I expected and also wasted a lot of resources because the
predicate was true for all or most elements. After some testing I went with
this:
>
> <xsl:variable name="ancestors-in-topic"
>  select="ancestor-or-self::*[ancestor-or-self::*/generate-id() =
generate-id($topic)]" as="element()*"/>

You're looking for ancestors of the context item that are descendants of
$topic (with a possible -or-self thrown in).

The challenge here is to avoid making this quadratic in the length of the
ancestor axis. Your code is effectively saying "for every ancestor, find every
ancestor and test it".

Use of the "=" operator is a bad mistake: this compares string values of
nodes, which involves examining all the descendants: it's not only
inefficient, it also gives the wrong answer.

I think the simplest solution is (ancestor-or-self::* except
$topic/ancestor::*) but this is still rather inefficient (it will also return
nodes in document order so you may need to reverse() the result). I've often
wished there was an "until" operator in XPath that selects all items in a
sequence up to the first where a condition is true:

ancestor-or-self::* until (self::* is $topic)

and you can write this yourself as a higher-order extension function in 3.0:

<xsl:function name="f:until" as="item()*">
  <xsl:param name="seq" as="item()*"/>
  <xsl:param name="condition" as="function(item()) as xs:boolean"/>
  <xsl:sequence select="
     if (empty($seq))
     then ()
     else if ($condition(head($seq))
     then head($seq)
     else (head($seq), f:until(tail($seq), $condition))"/>
</xsl:function>

and you could invoke this as

f:until(ancestor-or-self::*, function($x){$x is $topic})

Of course you could also write a less generic recursive function:

<xsl:function name="nodes-until" as="item()*">
  <xsl:param name="seq" as="item()*"/>
  <xsl:param name="target" as="node()"/>
  <xsl:sequence select="
     if (empty($seq))
     then ()
     else if ($target is head($seq))
     then head($seq)
     else (head($seq), nodes-until(tail($seq), $target))"/>
</xsl:function>

f:nodes-until(ancestor::*, $topic)

Michael Kay
Saxonica


> <xsl:variable name="ancestors-in-topic"
>  select="ancestor-or-self::*[some $ancestor-or-self::* is $topic)]"
as="element()*"/>


>
> Since that calculation is done very often I am wondering if xsl:key could be
used to speed things up?
>
> Any pointers are very welcome, as always, thanks,
>
> - Michael
>
> PS: My sample XML and XSLT below.
>
> <?xml version="1.0" encoding="UTF-8"?>
> <bars id="x0">
>  <bar id="x1">
>    <bar id="x11">
>      <bar id="x12">
>        <div>
>          <bar id="x13">
>            <div>
>              <p/>
>            </div>
>          </bar>
>        </div>
>      </bar>
>    </bar>
>  </bar>
> </bars>
>
>
> <?xml version="1.0" encoding="UTF-8"?>
> <xsl:stylesheet xmlns:xsl="http://www.w3.org/1999/XSL/Transform";
xmlns:xs="http://www.w3.org/2001/XMLSchema"; version="2.0">
>  <xsl:output method="xml" indent="yes" omit-xml-declaration="no"/>
>  <xsl:strip-space elements="*"/>
>
>  <xsl:template match="p">
>    <xsl:variable name="topic" select="ancestor-or-self::*[@id][1]"
as="element()"/>
>    <xsl:variable name="ancestors-in-topic"
select="ancestor-or-self::*[ancestor-or-self::*/generate-id() =
generate-id($topic)]" as="element()*"/>
>    <xsl:copy>
>      <xsl:attribute name="topic" select="$topic/@id"/>
>      <xsl:text>Ancestors: </xsl:text>
>       <xsl:sequence select="$ancestors-in-topic/name()"/>
>    </xsl:copy>
>  </xsl:template>
>
>  <xsl:template match="* | @*">
>    <xsl:copy>
>      <xsl:apply-templates select="@*, node()"/>
>    </xsl:copy>
>  </xsl:template>
> </xsl:stylesheet>
>
>
> Expected output for <p>: <p topic="x13">Ancestors: bar div p</p>

Current Thread