Re: [xsl] Spotting "cousin marriages" in a tree

[Jeni Tennison <jeni@xxxxxxxxxxxxxxxx>]

Hi Phil,

I think that you've covered the possible solutions here, so just a
couple of suggestions that might help you with the problems you
identified with this solution:

> I can do a multi-pass process using exsl:node-set(), generating the
> tree with the duplicates in it and then deleting them if they are
> duplicates, i.e. something like this:
[snip]
> There are two problems with this. First, generating the intermediate
> result could run forever if the input is seriously malformed (e.g. a
> loop, child refers to parent); checking as it is generated would
> avoid this.

You could avoid re-entry problems by keeping track of the ancestors of
a particular <tree> element through a parameter, something like:

<xsl:key name="things-by-id" match="thing" use="@id"/>

<xsl:template match="thing">
  <xsl:param name="ancestors" select="/.." />
  <tree>
    <xsl:for-each select="child">
      <xsl:choose>
        <xsl:when test="@idref = $ancestors">
          <error />
        </xsl:when>
        <xsl:otherwise>
          <xsl:apply-templates select="key('things-by-id',@idref)">
            <xsl:with-param name="ancestors"
                            select="$ancestors | @idref" />
          </xsl:apply-templates>
        </xsl:otherwise>
      </xsl:choose>
    </xsl:for-each>
  </tree>
</xsl:template>

> Second, the test "preceding::tree[@id=current/@id]" is O(n^2). Can I
> use a key to avoid this? How can a key be applied to an
> exsl:node-set() result?

In just the same way as you use keys with other documents. The key
returns nodes in the same document as the node you're on. It doesn't
make a difference that document has been generated from a result-tree
fragment. So you can do:

<xsl:key name="tree-by-id" match="tree" use="@id" />

<xsl:template match="tree" mode="remove-dupes">
   <xsl:choose>
     <xsl:when test="generate-id(key('tree-by-id', @id)[1]) !=
                     generate-id(.)">
       <error/>
     </xsl:when>
     <xsl:otherwise>
       <tree id="{@id}">
         <xsl:apply-templates mode="remove-dupes"/>
       </tree>
     </xsl:otherwise>
   </xsl:choose>
</xsl:template>

Cheers,

Jeni

---
Jeni Tennison
http://www.jenitennison.com/