Re: [xsl] reproducing the hierarchical structure of a subset of nodes from a document

Subject: Re: [xsl] reproducing the hierarchical structure of a subset of nodes from a document
From: Brandon Ibach <brandon.ibach@xxxxxxxxxxxxxxxxxxx>
Date: Fri, 10 Jun 2011 14:34:28 -0400
Since you specifically mentioned XSLT 1.0, I'll assume that your
environment keeps you from using an XSLT 2.0 processor, in some way.
If this is not the case, then there are certainly better solutions
within the capabilities of the newer standard.  (There's also the
added advantage that you wouldn't have to put up with the grief that
you might get on this list simply because you don't have the option of
using the newer language, even if you'd like to.)

The following uses recursion, but just to iterate through the list of
elements supplied as a parameter to the transform (such that the list
can be calculated by a non-XSLT process, as you suggested).  It does
traverse parts of the list multiple times (once to find and nest
lower-level elements and again to walk past them to get to
"siblings"), but it should, hopefully, still be more efficient than
recursion through the entire input document.

If I've understood your goal, this produces the correct results for
your sample.  I haven't tested it beyond that, so more complicated
structures could fail, though the adjustments that might be needed
would probably be fairly minor.  I'm certainly interested in hearing
about how it works on real data.

Hope this helps.

-Brandon :)

<?xml version="1.0" encoding="utf-8"?>
<xsl:stylesheet xmlns:xsl="http://www.w3.org/1999/XSL/Transform";
version="1.0">
  <xsl:output method="xml" version="1.0" encoding="utf-8"/>

  <!-- Pass in the "target group" of elements from outside the transform -->
  <xsl:param name="group" select="//foo/bar"/>

  <xsl:template match="/">
    <tree>
      <!-- Iterate (via recursion) through the group -->
      <xsl:call-template name="process-element">
        <xsl:with-param name="group" select="$group"/>
      </xsl:call-template>
    </tree>
  </xsl:template>

  <!-- Identity template to copy content of element in the group -->
  <xsl:template match="node() | @*">
    <xsl:copy>
      <xsl:apply-templates select="@*"/>
      <xsl:apply-templates select="node()"/>
    </xsl:copy>
  </xsl:template>

  <!-- Process the group one element at a time, nesting appropriately
based on relative depth -->
  <xsl:template name="process-element">
    <xsl:param name="group" select="/.."/>
    <xsl:param name="cur-depth" select="-1"/>
    <xsl:param name="max-depth" select="999999"/>
    <!-- Process first element if its depth is greater than the
"current" depth and less -
       - than or equal to the "maximum" (skiping nodes already
processed during nesting) -->
    <xsl:variable name="first" select="$group[1][count(ancestor::*)
&gt; $cur-depth]"/>
    <xsl:if test="$first[count(ancestor::*) &lt;= $max-depth]">
      <!-- Copy the element, its attributes and its content -->
      <xsl:element name="{name($first)}">
        <xsl:apply-templates select="$first/@*"/>
        <xsl:apply-templates select="$first/node()"/>
        <!-- Process the rest of the group for elements that should be
nested -->
        <xsl:call-template name="process-element">
          <xsl:with-param name="group" select="$group[position() &gt; 1]"/>
          <xsl:with-param name="cur-depth"
select="count($first/ancestor::*)"/>
        </xsl:call-template>
      </xsl:element>
      <!-- Process those elements in the rest of the group that should
be siblings -->
      <xsl:call-template name="process-element">
        <xsl:with-param name="group" select="$group[position() &gt; 1]"/>
        <xsl:with-param name="cur-depth" select="$cur-depth"/>
        <xsl:with-param name="max-depth" select="count($first/ancestor::*)"/>
      </xsl:call-template>
    </xsl:if>
    <!-- Skip over the first element if it was already processed -->
    <xsl:if test="$group[1][count(ancestor::*) &gt; $max-depth]">
      <xsl:call-template name="process-element">
        <xsl:with-param name="group" select="$group[position() &gt; 1]"/>
        <xsl:with-param name="cur-depth" select="$cur-depth"/>
        <xsl:with-param name="max-depth" select="$max-depth"/>
      </xsl:call-template>
    </xsl:if>
  </xsl:template>
</xsl:stylesheet>


On Fri, Jun 10, 2011 at 10:26 AM, trubliphone
<trubliphone@xxxxxxxxxxxxxx> wrote:
> Hello,
>
> I have an algorithmic problem I haven't been able to solve.  I was
> hoping somebody on this list could offer me some advice.
>
> I do have a solution in pure XQuery, but that requires recursion
> through a potentially massive XML document which is too inefficient
> for production use.  So, I am trying to come up with another way and I
> wondered if XSL might do the trick.
>
> Suppose I have some arbitrary XML file:
>
> <?xml version="1.0" encoding="UTF-8"?>
> <root>
>   <foo>
>       <bar>one</bar>
>       <foo>
>           <bar>two</bar>
>       </foo>
>       <foo>
>           <bar>three</bar>
>       </foo>
>   </foo>
>   <foo>
>       <bar>four</bar>
>       <foo>
>           <foo>
>               <bar>five</bar>
>           </foo>
>       </foo>
>   </foo>
> </root>
>
> Now, suppose there is a user-provided XPath expression to find
> particular nodes in that file:
>
> $query := "//foo/bar"
>
> I understand that I cannot, in pure XSLT v1.0, easily evaluate that
> string against the document and return the desired nodes.  That's
> okay, I can do it in other languages.
>
> After evaluating that string, I wind up with the following node sequence:
>
> (<bar>one</bar>, <bar>two</bar>, <bar>three</bar>, <bar>four</bar>,
> <bar>five</bar>)
>
> But I need to recreate the original hierarchical structure of those
> nodes.  So what I really want is this:
>
> <bar>one
>  <bar>two</bar>
>  <bar>three</bar>
> </bar>
> <bar>four
>  <bar>five</bar>
> </bar>
>
> To help, I can get the "context path" of each node as follows:
>
> one:   /root[1]/foo[1]/bar[1]
> two:   /root[1]/foo[1]/foo[1]/bar[1]
> three: /root[1]/foo[1]/foo[2]/bar[1]
> four:  /root[1]/foo[2]/bar[1]
> five:   /root[1]/foo[2]/foo[1]/foo[1]/bar[1]
>
> So I have the following sequence to work with that I can run an XSL template
on:
>
> (
>  <node cp="/root[1]/foo[1]/bar[1]"><bar>one</bar></node>,
>  <node cp="/root[1]/foo[1]/foo[1]/bar[1]"><bar>two</bar></node>,
>  <node cp="/root[1]/foo[1]/foo[2]/bar[1]"><bar>three</bar></node>,
>  <node cp="/root[1]/foo[2]/bar[1]"><bar>four</bar></node>,
>  <node cp="/root[1]/foo[2]/foo[1]/foo[1]/bar[1]"><bar>five</bar></node>
> )
>
> My question is how to turn that into a tree that recreates the
> original hierarchical structure?
>
> Many thanks for your help.

Current Thread