photoml 0.28-0ubuntu1 / usr / share / photoml / xsl / defaults / merge.xsl

<?xml version="1.0"?>
<xsl:stylesheet xmlns:xsl="http://www.w3.org/1999/XSL/Transform"
                xmlns:exslt="http://exslt.org/common" 
                xmlns:str="http://exslt.org/strings"
                xmlns:func="http://exslt.org/functions"
                xmlns:debug="http://wohlberg.net/xml/debug"
                xmlns:merge="http://wohlberg.net/xml/merge"
                xmlns:dflts="http://wohlberg.net/xml/defaults"
                xmlns:vldt="http://search.cpan.org/~wohl/XML-DTD/validate"
                extension-element-prefixes="exslt str func"
                version="1.0">


<!-- 
     This file contains templates and extension functions for merging
     subtrees of element nodes. The complexity of this operations
     arises from the necessity to maintain validity with respect to
     some DTD after the merge operation. The DTD content model
     restriction is specified as an XPath expression for each subtree
     root node which may be involved in a merge. See the notes at the
     end of this file for further details.

     Copyright © 2005-2010 Brendt Wohlberg <photoml@wohlberg.net>

     This is free software; you can redistribute it and/or modify it 
     under the terms of version 2 of the GNU General Public License 
     at http://www.gnu.org/licenses/gpl-2.0.txt.

     This software is distributed in the hope that it will be useful,
     but WITHOUT ANY WARRANTY; without even the implied warranty of
     MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the 
     GNU General Public License for more details.
 -->


  <!-- Include debugging functions and templates -->
  <xsl:include href="debug.xsl"/>



  <!-- Stylesheet parameter controlling debug trace messages -->
  <xsl:param name="debug-merge">0</xsl:param>



<!-- *****************************************************************
     Named template calling extension function merge:merge-subtrees. 
     ***************************************************************** -->
  <xsl:template name="merge-subtrees">
    <xsl:param name="x" select="/.."/>
    <xsl:param name="y" select="/.."/>
    <xsl:copy-of select="merge:merge-subtrees($x, $y)"/>
  </xsl:template>



<!-- *****************************************************************
     Extension function for merging subtree in parameter $y into
     subtree in parameter $x. The parent nodes of both subtrees must
     be elements with the same name (and are therefore subject to the
     same content model). The correct insertion position as a child of
     $x for each child of $y is controlled by a content model
     specification in a template matching the parent element, and with
     mode "validate". A child of $y is not merged into $x if all merge
     positions violate the content model.
     ***************************************************************** -->
  <func:function name="merge:merge-subtrees">
    <xsl:param name="x" select="/.."/>
    <xsl:param name="y" select="/.."/>

    <!-- ******** BEGIN DEBUGGING TRACE ******** -->
    <xsl:if test="$debug-merge&gt;0">
      <xsl:message>
        <xsl:text>---merge-&gt; </xsl:text>
        <xsl:text>Called merge:merge-subtrees:&#10;</xsl:text>
        <xsl:value-of select="debug:debug-node-set($x,'x:',
                              $debug-merge&gt;2)"/>
        <xsl:value-of select="debug:debug-node-set($y,'y:',
                              $debug-merge&gt;2)"/>
        <xsl:text>&lt;--merge--&#10;</xsl:text>
      </xsl:message>
    </xsl:if>
    <!-- ********* END DEBUGGING TRACE ********* -->

    <!-- Check that parameters have required structure -->
    <xsl:choose>
      <!-- One of the parameters is not a subtree -->
      <xsl:when test="count($x)&gt;1 or count($y)&gt;1">
        <xsl:message>
          <xsl:text>Warning: function merge-subtrees called with </xsl:text>
          <xsl:text>a node set (parameters must be subtrees).</xsl:text>
        </xsl:message>
      </xsl:when>
      <!-- One of the parameters is a subtree with null root name -->
      <xsl:when test="(name($x)='' and count($x[1]/*)&gt;0) or 
                      (name($y)='' and count($y[1]/*)&gt;0)">
        <xsl:message>
          <xsl:text>Warning: function merge-subtrees called with </xsl:text>
          <xsl:text>subtree with a null root name.</xsl:text>
        </xsl:message>
      </xsl:when>
    </xsl:choose>
    <!-- Call the merge:merge-subtrees-recursive function -->
    <func:result select="merge:merge-subtrees-recursive(/.., $x, $y)"/>
  </func:function>



 <!-- *****************************************************************
     Recursive subtree merging function, merging the subtree in
     parameter $y into the subtree in parameter $xrt. The insertion
     position of each child of $y is determined by validating the
     subtree with inserted node using a template matching the parent
     element, and with mode "validate". The temporary subtree checked
     for validity is constructed as the sequence of child nodes
     consisting of all the children of $xlt, the first child of $y,
     and all of the children of $xrt.
     ***************************************************************** -->
   <func:function name="merge:merge-subtrees-recursive">
    <xsl:param name="xlt" select="/.."/>
    <xsl:param name="xrt" select="/.."/>
    <xsl:param name="y" select="/.."/>

    <!-- ******** BEGIN DEBUGGING TRACE ******** -->
    <xsl:if test="$debug-merge&gt;0">
      <xsl:message>
        <xsl:text>---merge-&gt; </xsl:text>
        <xsl:text>Called merge:merge-subtrees-recursive:&#10;</xsl:text>
        <xsl:value-of select="debug:debug-node-set($xlt,'xlt:',
                              $debug-merge&gt;2)"/>
        <xsl:value-of select="debug:debug-node-set($xrt,'xrt:',
                              $debug-merge&gt;2)"/>
        <xsl:value-of select="debug:debug-node-set($y,'y:',
                              $debug-merge&gt;2)"/>
        <xsl:text>&lt;--merge--&#10;</xsl:text>
      </xsl:message>
    </xsl:if>
    <!-- ********* END DEBUGGING TRACE ********* -->

    <xsl:variable name="result">
      <xsl:choose>
        <!-- #### Begin branch: A #### -->
        <xsl:when test="count($xlt) = 0">
          <!-- When $xlt is null, this is the initial call to
               merge:merge-subtrees-recursive. -->
          <xsl:choose>
            <!-- #### Begin branch: AA #### -->
            <xsl:when test="count($y) = 0">
              <!-- When $y is also null, there is nothing to
                   do. Return a copy of $xrt. -->
              <!-- ******** BEGIN DEBUGGING TRACE ******** -->
              <xsl:if test="$debug-merge&gt;0">
                <xsl:message>---merge-- ### Entered branch AA</xsl:message>
              </xsl:if>
              <!-- ********* END DEBUGGING TRACE ********* -->
              <xsl:copy-of select="$xrt"/>
            </xsl:when>
            <!-- #### End branch: AA #### -->
            <!-- #### Begin branch: AB #### -->
            <xsl:when test="$xrt/processing-instruction('merge-reject')">
              <!-- A processing instruction with name 'merge-reject'
                   and content consisting of a list of element names
                   and/or attribute names (each attribute name must be
                   preceded by the '@' character) indicates that the
                   named nodes occuring as children of the subtree in
                   $y should be rejected when merging $y into $xrt. Do
                   a recursive call to merge:merge-subtrees-recursive
                   with null $xlt (since it must be null in this
                   decision branch), $xrt with the merge-reject
                   processing instructions removed, and $y with the
                   identified nodes removed. -->
              <!-- ******** BEGIN DEBUGGING TRACE ******** -->
              <xsl:if test="$debug-merge&gt;0">
                <xsl:message>---merge-- ### Entered branch AB</xsl:message>
              </xsl:if>
              <!-- ********* END DEBUGGING TRACE ********* -->
              <xsl:copy-of select="merge:merge-subtrees-recursive(
                                   /.., 
                                   merge:prune-merge-reject-pi($xrt),
                                   merge:apply-merge-rejection($y, $xrt))"/>
            </xsl:when>
            <!-- #### End branch: AB #### -->
            <!-- #### Begin branch: AC #### -->
           <xsl:when test="count($xrt/*) = 0 and $xrt/text() and
                           count($y/*) = 0 and $y/text()">
             <!-- When $xrt and $y each have text children, and no
                  element children, the content in $xrt takes
                  precedence over that in $y. Return the content of
                  $xrt, with only the attributes of $y appended. -->
              <!-- ******** BEGIN DEBUGGING TRACE ******** -->
              <xsl:if test="$debug-merge&gt;0">
                <xsl:message>---merge-- ### Entered branch AC</xsl:message>
              </xsl:if>
              <!-- ********* END DEBUGGING TRACE ********* -->
               <xsl:copy-of select="merge:append-children($xrt, 
                                        merge:prune-non-attributes($y)
                                                         )"/>
            </xsl:when>
            <!-- #### End branch: AC #### -->
            <!-- #### Begin branch: AD #### -->
           <xsl:when test="count($xrt/*) = 0 and count($y/*) &gt; 0">
             <!-- When $y has element children and $xrt does not, the
                  subtrees may be merged without testing for valid
                  insertion positions. Return the subtree containing
                  first the (non-element) children of $xrt, followed
                  by the children of $y. -->
              <!-- ******** BEGIN DEBUGGING TRACE ******** -->
              <xsl:if test="$debug-merge&gt;0">
                <xsl:message>---merge-- ### Entered branch AD</xsl:message>
              </xsl:if>
              <!-- ********* END DEBUGGING TRACE ********* -->
               <xsl:copy-of select="merge:append-children($xrt, $y)"/>
            </xsl:when>
            <!-- #### End branch: AD #### -->
            <!-- #### Begin branch: AE #### -->
            <xsl:otherwise>
              <!-- When $y is not null, some initial processing is
                   required. Do a recursive call with $xlt consisting
                   of the same subtree root as $xrt, and with the
                   attributes copied from $xrt and $y, and with the
                   subtree root attributes stripped from $xrt and $y. -->
              <!-- ******** BEGIN DEBUGGING TRACE ******** -->
              <xsl:if test="$debug-merge&gt;0">
                <xsl:message>---merge-- ### Entered branch AE</xsl:message>
              </xsl:if>
              <!-- ********* END DEBUGGING TRACE ********* -->
              <xsl:copy-of select="merge:merge-subtrees-recursive(
                                     merge:append-attributes($xrt, $y),
                                     merge:prune-attributes($xrt),
                                     merge:prune-attributes($y))"/>
            </xsl:otherwise>
            <!-- #### End branch: AE #### -->
          </xsl:choose>
        </xsl:when>
        <!-- #### End branch: A #### -->
        <!-- #### Begin branch: B #### -->
        <xsl:when test="count($y[1]/node()) = 0">
          <!-- When $y is an empty subtree, the recursion is done
               since there are no more insertion tests to
               perform. Construct the final result by appending the
               children of $xrt onto those of $xlt, and emit it. (If
               $xrt is also an empty subtree, this is the same as just
               emitting $xlt.) -->
          <!-- ******** BEGIN DEBUGGING TRACE ******** -->
          <xsl:if test="$debug-merge&gt;0">
            <xsl:message>---merge-- ### Entered branch B</xsl:message>
          </xsl:if>
          <!-- ********* END DEBUGGING TRACE ********* -->
          <xsl:copy-of select="merge:append-children($xlt, $xrt)"/>
        </xsl:when>
        <!-- #### End branch: B #### -->
        <!-- #### Begin branch: C #### -->
        <xsl:otherwise>
          <!-- When $y is not an empty subtree, there are insertion
               tests remaining to be performed. -->
          <!-- ******** BEGIN DEBUGGING TRACE ******** -->
          <xsl:if test="$debug-merge&gt;0">
            <xsl:message>
              <xsl:text>---merge-- ### Doing test for branch CA</xsl:text>
            </xsl:message>
          </xsl:if>
          <!-- ********* END DEBUGGING TRACE ********* -->
          <xsl:choose>
            <!-- #### Begin branch: CA #### -->
            <xsl:when test="merge:insertion-valid($xlt, 
                            merge:prune-trailing-children($y), $xrt)">
              <!-- If the insertion of the first child element in $y
                   is valid, do a recursive call with $xlt having that
                   child element appended, $xrt unchanged, and $y
                   having its first child element removed. -->
              <!-- ******** BEGIN DEBUGGING TRACE ******** -->
              <xsl:if test="$debug-merge&gt;0">
                <xsl:message>---merge-- ### Entered branch CA</xsl:message>
              </xsl:if>
              <!-- ********* END DEBUGGING TRACE ********* -->
              <xsl:copy-of select="merge:merge-subtrees-recursive(
                                   merge:append-children(
                                         $xlt, 
                                         merge:prune-trailing-children($y)
                                   ),
                                   $xrt,
                                   merge:prune-first-child($y))"/>
            </xsl:when>
            <!-- #### End branch: CA #### -->
            <!-- #### Begin branch: CB #### -->
            <xsl:otherwise>
             <!-- If the insertion of the first child element in $y
                  is invalid, check whether it should be discarded or
                  merged with the first child element in $xrt. -->
              <xsl:choose>
                <!-- #### Begin branch: CBA #### -->
                <xsl:when test="name($xrt/*[1]) = name($y/*[1])">
                  <!-- When the first element children in $xrt and $y
                       have the same name, these elements should be
                       merged if the first element child in $xrt is
                       not empty or contains only a text node.
                       Specifically, the subtrees consisting of the
                       first elements in $xrt and $y need to be
                       merged. Descend down a subtree level by doing a
                       recursive call with empty $xlt, and $xrt and $y
                       containing these subtrees. This result is then
                       used as $xlt within another recursive call,
                       with $xrt and $y with their first child
                       elements removed. To summarise (since this is
                       rather confusing): the first recursive call
                       merges the lower level subtrees with matching
                       root element names, and the second recursive
                       call continues at the current level, inserting
                       the result of the first call.  -->
                  <!-- ******** BEGIN DEBUGGING TRACE ******** -->
                  <xsl:if test="$debug-merge&gt;0">
                    <xsl:message>---merge-- ### Entered branch CBA</xsl:message>
                  </xsl:if> 
                  <!-- ********* END DEBUGGING TRACE ********* -->
                  <xsl:copy-of select="merge:merge-subtrees-recursive(
                         merge:append-to-children($xlt,
                           $xrt/node()[not(preceding-sibling::* or self::*)],
                           merge:merge-subtrees-recursive(/..,
                           merge:prune-trailing-children($xrt)/*[1],
                              merge:prune-trailing-children($y)/*[1]
                              )
                           ),
                           merge:prune-first-child($xrt),
                           merge:prune-first-child($y))"/>
                </xsl:when>
                <!-- #### End branch: CBA #### -->
                <!-- #### Begin branch: CBB #### -->
                <xsl:otherwise>
                  <!-- Insertion of the first child element in $y is
                       invalid, and the first child elements in $xrt
                       and $y do not have matching names. Since the
                       first child element in $y could neither be
                       inserted nor merged at the current position,
                       processing is moved to the next position by
                       appending the first child element in $xrt onto
                       the children of $xlt. If $xrt has no remaining
                       child elements, the remaining children of $y
                       cannot be inserted, and must be discarded. -->
                  <xsl:choose>
                    <!-- #### Begin branch: CBBA #### -->
                    <xsl:when test="count($xrt[1]/node()) = 0">
                      <!-- The remaining children of $y must be
                           discarded since $xrt has no remaining child
                           elements. (The test is, in fact, for
                           remaining child nodes, since one additional
                           recursive call is then able to take care of
                           any remaining non-element children of
                           $xrt.) -->
                      <!-- ******** BEGIN DEBUGGING TRACE ******** -->
                      <xsl:if test="$debug-merge&gt;0">
                        <xsl:message>---merge-- ### Entered branch CBBA</xsl:message>
                      </xsl:if>
                      <!-- ********* END DEBUGGING TRACE ********* -->
                      <xsl:copy-of select="$xlt"/>
                    </xsl:when>
                    <!-- #### End branch: CBBA #### -->
                    <!-- #### Begin branch: CBBB #### -->
                    <xsl:otherwise>  
                    <!-- Processing is moved to the next position by
                         appending the first child element in $xrt
                         onto the children of $xlt. Do a recursive
                         call with $xlt having the first child element
                         of $xrt appended, $xrt havings its first
                         child element removed, and $y unchanged. -->
                      <!-- ******** BEGIN DEBUGGING TRACE ******** -->
                      <xsl:if test="$debug-merge&gt;0">
                        <xsl:message>---merge-- ### Entered branch CBBB</xsl:message>
                      </xsl:if>
                      <!-- ********* END DEBUGGING TRACE ********* -->
                      <xsl:copy-of select="merge:merge-subtrees-recursive(
                                   merge:append-children(
                                         $xlt, 
                                         merge:prune-trailing-children($xrt)
                                   ),
                                   merge:prune-first-child($xrt),
                                   $y)"/>
                    </xsl:otherwise>
                    <!-- #### End branch: CBBB #### -->
                  </xsl:choose>
                </xsl:otherwise>
                <!-- #### End branch: CBB #### -->
              </xsl:choose>
            </xsl:otherwise>
            <!-- #### End branch: CB #### -->
          </xsl:choose>
        </xsl:otherwise>
        <!-- #### End branch: C #### -->
      </xsl:choose>
    </xsl:variable>

    <func:result select="exslt:node-set($result)/node()"/>
  </func:function>



<!-- *****************************************************************
     Append the children in the subtree in $y to those in the subtree
     in $x and return the result.
     ***************************************************************** -->
  <func:function name="merge:append-children">
    <xsl:param name="x" select="/.."/>
    <xsl:param name="y" select="/.."/>

    <!-- ******** BEGIN DEBUGGING TRACE ******** -->
    <xsl:if test="$debug-merge&gt;1">
      <xsl:message>
        <xsl:text>---merge-&gt; Called merge:append-children:&#10;</xsl:text>
        <xsl:value-of select="debug:debug-node-set($x,'x:',
                              $debug-merge&gt;3)"/>
        <xsl:value-of select="debug:debug-node-set($y,'y:',
                              $debug-merge&gt;3)"/>
        <xsl:text>&lt;--merge--&#10;</xsl:text>
      </xsl:message>
    </xsl:if>
    <!-- ********* END DEBUGGING TRACE ********* -->

    <xsl:variable name="xy">
      <xsl:choose>
        <xsl:when test="count($x[1]) = 0">
          <xsl:copy-of select="$y"/>
        </xsl:when>
        <xsl:when test="count($y[1]) = 0">
          <xsl:copy-of select="$x"/>
        </xsl:when>
        <xsl:otherwise>
          <xsl:element name="{name($x[position()=1 and self::*])}">
            <!-- Copy attributes in $x -->
            <xsl:copy-of select="$x/@*"/>
            <!-- Emit attributes in $y that are not also in $x -->
            <xsl:for-each select="$y/@*">
              <xsl:if test="not($x/@*[name()=name(current())])">
                <xsl:copy-of select="."/>
              </xsl:if>
            </xsl:for-each>
            <!-- Copy all child nodes in $x, except for a final 
                 whitespace-only text node -->
            <xsl:copy-of select="$x/node()[not(position()=last() and 
                                 self::text() and normalize-space()='')]"/>
            <!-- Copy all child nodes in $y -->
            <xsl:copy-of select="$y/node()"/>
          </xsl:element>
        </xsl:otherwise>
      </xsl:choose>
    </xsl:variable>

    <func:result select="exslt:node-set($xy)/node()"/>
  </func:function>



<!-- *****************************************************************
     Append the nodes in $y and $z to the children in subtree $x, and
     return the result.
     ***************************************************************** -->
  <func:function name="merge:append-to-children">
    <xsl:param name="x" select="/.."/>
    <xsl:param name="y" select="/.."/>
    <xsl:param name="z" select="/.."/>

    <!-- ******** BEGIN DEBUGGING TRACE ******** -->
    <xsl:if test="$debug-merge&gt;1">
      <xsl:message>
        <xsl:text>---merge-&gt; </xsl:text>
        <xsl:text>Called merge:append-to-children:&#10;</xsl:text>
        <xsl:value-of select="debug:debug-node-set($x,'x:',
                              $debug-merge&gt;3)"/>
        <xsl:value-of select="debug:debug-node-set($y,'y:',
                              $debug-merge&gt;3)"/>
        <xsl:value-of select="debug:debug-node-set($z,'z:',
                              $debug-merge&gt;3)"/>
        <xsl:text>&lt;--merge--&#10;</xsl:text>
      </xsl:message>
    </xsl:if>
    <!-- ********* END DEBUGGING TRACE ********* -->

    <xsl:variable name="xyz">
      <xsl:choose>
        <xsl:when test="count($x[1]) = 0 or 
                        (count($y[1]) = 0 and count($z[1]) = 0)">
          <xsl:copy-of select="$x"/>
        </xsl:when>
        <xsl:otherwise>
          <xsl:element name="{name($x[position()=1 and self::*])}">
            <!-- Copy attributes in $x -->
            <xsl:copy-of select="$x/@*"/>
            <!-- Copy all child nodes in $x, except for a final 
                 whitespace-only text node -->
            <xsl:copy-of select="$x/node()[not(position()=last() and 
                                 self::text() and normalize-space()='')]"/>
            <!-- Copy all nodes in $y -->
            <xsl:copy-of select="$y"/>
            <!-- Copy all nodes in $z -->
            <xsl:copy-of select="$z"/>
          </xsl:element>
        </xsl:otherwise>
      </xsl:choose>
    </xsl:variable>

    <func:result select="exslt:node-set($xyz)/node()"/>
  </func:function>



<!-- *****************************************************************
     Remove the first child element (and any other nodes preceding it)
     from the subtree in $x, and return the result.
     ***************************************************************** -->
  <func:function name="merge:prune-first-child">
    <xsl:param name="x" select="/.."/>

    <!-- ******** BEGIN DEBUGGING TRACE ******** -->
    <xsl:if test="$debug-merge&gt;1">
      <xsl:message>
        <xsl:text>---merge-&gt; Called merge:prune-first-child:&#10;</xsl:text>
        <xsl:value-of select="debug:debug-node-set($x,'x:',
                              $debug-merge&gt;3)"/>
        <xsl:text>&lt;--merge--&#10;</xsl:text>
      </xsl:message>
    </xsl:if>
    <!-- ********* END DEBUGGING TRACE ********* -->
    
    <xsl:variable name="px">
      <xsl:element name="{name($x[position()=1 and self::*])}">
        <!-- Copy attributes in $x -->
        <xsl:copy-of select="$x/@*"/>
        <!-- Copy child nodes in $x following the first child element -->
        <xsl:copy-of select="$x/node()[preceding-sibling::*]"/>
      </xsl:element>
    </xsl:variable>

    <func:result select="exslt:node-set($px)/node()"/>
  </func:function>



<!-- *****************************************************************
     Remove all nodes following the first child element from the
     subtree in $x, and return the result.
     ***************************************************************** -->
  <func:function name="merge:prune-trailing-children">
    <xsl:param name="x" select="/.."/>

    <!-- ******** BEGIN DEBUGGING TRACE ******** -->
    <xsl:if test="$debug-merge&gt;1">
      <xsl:message>
        <xsl:text>---merge-&gt; </xsl:text>
        <xsl:text>Called merge:prune-trailing-children:&#10;</xsl:text>
        <xsl:value-of select="debug:debug-node-set($x,'x:',
                              $debug-merge&gt;3)"/>
        <xsl:text>&lt;--merge--&#10;</xsl:text>
      </xsl:message>
    </xsl:if>
    <!-- ********* END DEBUGGING TRACE ********* -->

    <xsl:variable name="px">
      <xsl:element name="{name($x[position()=1 and self::*])}">
        <!-- Copy attributes in $x -->
        <xsl:copy-of select="$x/@*"/>
        <!-- Copy child nodes in $x up to and including the first
             child element -->
        <xsl:copy-of select="$x/node()[not(preceding-sibling::*)]"/>
      </xsl:element>
    </xsl:variable>

    <func:result select="exslt:node-set($px)/node()"/>
  </func:function>



<!-- *****************************************************************
     Return a subtree with root element having the same name as the
     subtree root element in $x, and with the subtree root attributes
     from $x and $y. If necessary to avoid duplication, attributes in
     $x take precedence over those in $y.
     ***************************************************************** -->
  <func:function name="merge:append-attributes">
    <xsl:param name="x" select="/.."/>
    <xsl:param name="y" select="/.."/>

    <!-- ******** BEGIN DEBUGGING TRACE ******** -->
    <xsl:if test="$debug-merge&gt;1">
      <xsl:message>
        <xsl:text>---merge-&gt; Called merge:append-attributes:&#10;</xsl:text>
        <xsl:value-of select="debug:debug-node-set($x,'x:',
                              $debug-merge&gt;3)"/>
        <xsl:value-of select="debug:debug-node-set($y,'y:',
                              $debug-merge&gt;3)"/>
        <xsl:text>&lt;--merge--&#10;</xsl:text>
      </xsl:message>
    </xsl:if>
    <!-- ********* END DEBUGGING TRACE ********* -->

    <xsl:variable name="xy">
      <xsl:element name="{name($x[position()=1 and self::*])}">
        <!-- Copy attributes in $x -->
        <xsl:copy-of select="$x/@*"/>
        <!-- Emit attributes in $y that are not also in $x -->
        <xsl:for-each select="$y/@*">
          <xsl:if test="not($x/@*[name()=name(current())])">
            <xsl:copy-of select="."/>
          </xsl:if>
        </xsl:for-each>
      </xsl:element>
    </xsl:variable>

    <func:result select="exslt:node-set($xy)/node()"/>
  </func:function>



<!-- *****************************************************************
     Remove attributes from the subtree root element in $x and return
     the result.
     ***************************************************************** -->
  <func:function name="merge:prune-attributes">
    <xsl:param name="x" select="/.."/>

    <!-- ******** BEGIN DEBUGGING TRACE ******** -->
    <xsl:if test="$debug-merge&gt;1">
      <xsl:message>
        <xsl:text>---merge-&gt; Called merge:prune-attributes:&#10;</xsl:text>
        <xsl:value-of select="debug:debug-node-set($x,'x:',
                              $debug-merge&gt;3)"/>
        <xsl:text>&lt;--merge--&#10;</xsl:text>
      </xsl:message>
    </xsl:if>
    <!-- ********* END DEBUGGING TRACE ********* -->
    
    <xsl:variable name="px">
      <xsl:element name="{name($x[position()=1 and self::*])}">
        <xsl:copy-of select="$x/node()"/>
      </xsl:element>
    </xsl:variable>

    <func:result select="exslt:node-set($px)/node()"/>
  </func:function>



<!-- *****************************************************************
     Remove non-attribute nodes from the subtree root element in $x
     and return the result.
     ***************************************************************** -->
  <func:function name="merge:prune-non-attributes">
    <xsl:param name="x" select="/.."/>

    <!-- ******** BEGIN DEBUGGING TRACE ******** -->
    <xsl:if test="$debug-merge&gt;1">
      <xsl:message>
        <xsl:text>---merge-&gt; Called merge:prune-non-attributes:&#10;</xsl:text>
        <xsl:value-of select="debug:debug-node-set($x,'x:',
                              $debug-merge&gt;3)"/>
        <xsl:text>&lt;--merge--&#10;</xsl:text>
      </xsl:message>
    </xsl:if>
    <!-- ********* END DEBUGGING TRACE ********* -->
    
    <xsl:variable name="px">
      <xsl:element name="{name($x[position()=1 and self::*])}">
        <xsl:copy-of select="$x/@*"/>
      </xsl:element>
    </xsl:variable>

    <func:result select="exslt:node-set($px)/node()"/>
  </func:function>



<!-- *****************************************************************
     Remove all occurrences of the merge-reject processing instruction
     from the subtree root element in $x and return the result.
     ***************************************************************** -->
  <func:function name="merge:prune-merge-reject-pi">
    <xsl:param name="x" select="/.."/>

    <!-- ******** BEGIN DEBUGGING TRACE ******** -->
    <xsl:if test="$debug-merge&gt;1">
      <xsl:message>
        <xsl:text>---merge-&gt; Called merge:prune-merge-reject-pi:</xsl:text>
        <xsl:text>&#10;</xsl:text>
        <xsl:value-of select="debug:debug-node-set($x,'x:',
                              $debug-merge&gt;3)"/>
        <xsl:text>&lt;--merge--&#10;</xsl:text>
      </xsl:message>
    </xsl:if>
    <!-- ********* END DEBUGGING TRACE ********* -->
    
    <xsl:variable name="px">
      <xsl:element name="{name($x[position()=1 and self::*])}">
        <xsl:copy-of select="$x/@*"/>
        <xsl:copy-of select="$x/node()
          [not(self::processing-instruction('merge-reject') or 
               (self::text() and 
                following-sibling::node()[1]
                   [self::processing-instruction('merge-reject')])
              )]"/>
      </xsl:element>
    </xsl:variable>
    <func:result select="exslt:node-set($px)/node()"/>
  </func:function>



<!-- *****************************************************************
     Parse merge-reject processing instructions in the subtree in $y
     and remove the identified attributes and elements from the
     subtree in $x.
     ***************************************************************** -->
  <func:function name="merge:apply-merge-rejection">
    <xsl:param name="x" select="/.."/>
    <xsl:param name="y" select="/.."/>

    <!-- ******** BEGIN DEBUGGING TRACE ******** -->
    <xsl:if test="$debug-merge&gt;1">
      <xsl:message>
        <xsl:text>---merge-&gt; Called merge:apply-merge-rejection:</xsl:text>
        <xsl:text>&#10;</xsl:text>
        <xsl:value-of select="debug:debug-node-set($x,'x:',
                              $debug-merge&gt;3)"/>
        <xsl:value-of select="debug:debug-node-set($y,'y:',
                              $debug-merge&gt;3)"/>
        <xsl:text>&lt;--merge--&#10;</xsl:text>
      </xsl:message>
    </xsl:if>
    <!-- ********* END DEBUGGING TRACE ********* -->
    
    <xsl:variable name="tkn">
      <xsl:for-each select="$y/processing-instruction('merge-reject')">
        <xsl:copy-of select="str:tokenize(.)"/>
      </xsl:for-each> 
    </xsl:variable>
    <xsl:variable name="tknns" select="exslt:node-set($tkn)"/>
    <xsl:variable name="px">
      <xsl:element name="{name($x[position()=1 and self::*])}">
        <xsl:copy-of select="$x/@*[not($tknns/token = concat('@',name(.)))]"/>
        <xsl:copy-of select="$x/node()[not($tknns/token = name(.) or 
          ((self::text() or self::comment()) and 
               following-sibling::*[1][$tknns/token = name(.)])
                             )]"/>
      </xsl:element>
    </xsl:variable>

    <func:result select="exslt:node-set($px)/node()"/>
  </func:function>



<!-- *****************************************************************
     Return a boolean value indicating whether the insertion of the
     children in the subtree in $y between those in $xlt and $xrt is
     valid with respect to the root element content model, as
     determined by calling relevant the "validate" mode template.
     ***************************************************************** -->
  <func:function name="merge:insertion-valid">
    <xsl:param name="xlt" select="/.."/>
    <xsl:param name="y" select="/.."/>
    <xsl:param name="xrt" select="/.."/>

    <!-- ******** BEGIN DEBUGGING TRACE ******** -->
    <xsl:if test="$debug-merge&gt;1">
      <xsl:message>
        <xsl:text>---merge-&gt; Called merge:insertion-valid:&#10;</xsl:text>
        <xsl:value-of select="debug:debug-node-set($xlt,'xlt:',
                              $debug-merge&gt;3)"/>
        <xsl:value-of select="debug:debug-node-set($y,'y:',
                              $debug-merge&gt;3)"/>
        <xsl:value-of select="debug:debug-node-set($xrt,'xrt:',
                              $debug-merge&gt;3)"/>
        <xsl:text>&lt;--merge--&#10;</xsl:text>
      </xsl:message>
    </xsl:if>
    <!-- ********* END DEBUGGING TRACE ********* -->

    <func:result select="vldt:valid(exslt:node-set(
           merge:append-children($xlt, merge:append-children($y, $xrt))
                                                  ))"/>

  </func:function>



 <!--
     Some important issues regarding the merging implementation:

     * It is not clear that a coherent merge operation may be
       defined for all content models. This code will probably
       fail for sufficiently complex content models.

     * This code requires the EXSLT extensions exslt:node-set and
       func:function. While the same algorithm could have been
       implemented using templates rather than extension functions,
       the exslt:node-set extension is essential for this approach,
       and it appears that most XSLT processors that support
       exslt:node-set also support extension functions.


     The merging algorithm attempts to merge nodes in parameter $y
     into those in parameter $x by trying all possible insertion
     positions in $x of the first node in $y, then the second node in
     $y, and so on. Given the necessity of a recursive implementation
     (imposed by the use of XSLT), the current insertion position in
     $x is maintained by splitting $x into two variables, $xlt
     (preceding the current insertion position) and $xrt (following
     the current insertion position). This algorithm is outlined
     below.



    function merge_subtrees($x, $y) {

      Confirm that $x and $y are subtrees (not node sets) with
         the same valid root element name
      Call merge_subtrees_recursive({empty}, $x, $y)

    }


    function merge_subtrees_recursive($xlt, $xrt, $y) {
       
      if ($xlt is empty) {
        # [A]: Initial call to merge_subtrees_recursive
        if ($y is empty) {
          # [AA]: Since $xlt and $y are null, there is nothing to do. 
          #       Return a copy of $xrt
          Emit $xrt
        } elsif($xrt has any processing instruction children with name 
                'merge-reject') {
          # [AB]: A processing instruction with name 'merge-reject'
          #       and content consisting of a list of element names
          #       and/or attribute names (each attribute name must be
          #       preceded by the '@' character) indicates that the
          #       named nodes occuring as children of the subtree in
          #       $y should be rejected when merging $y into $xrt. Do
          #       a recursive call to merge:merge-subtrees-recursive
          #       with null $xlt (since it must be null in this
          #       decision branch), $xrt with the merge-reject
          #       processing instructions removed, and $y with the
          #       identified nodes removed.
          Call merge_subtrees_recursive(null,
                 {$xrt with all merge-reject processing instructions removed},
                 {$y with identified attributes and elements removed})
        } elsif($xrt has text children and no element children, and
                $y has text children and no element children) {
          # [AC]: When $xrt and $y each have text children, and no
          #       element children, the content in $xrt takes
          #       precedence over that in $y. Return the content of
          #       $xrt, with only the attributes of $y appended.
          Emit {$xrt subtree with the attributes of $y appended}
        } elsif($xrt has no child elements, and $y has at least one 
                child element) {
          # [AD]: When $y has element children and $xrt does not, the
          #       subtrees may be merged without testing for valid
          #       insertion positions. Return the subtree containing
          #       first the (non-element) children of $xrt, followed
          #       by the children of $y.
          Emit {$xrt subtree with the children of $y appended}
        } else {
          # [AE]: Since $xlt is null and $y is not, some processing 
          #       is required.
          Call merge_subtrees_recursive(
                 {subtree root of $xrt, with no children except the
                  attributes of $xrt and $y},
                 {$xrt with the subtree root attributes stripped},
                 {$y with the subtree root attributes stripped})
        }
      } elsif($y subtree has no children) {
        # [B]: Since $y is an empty subtree, the recursion is done
        #      as there are no more insertion tests to perform.
        Emit {$xlt subtree with the children of $xrt appended}
      } else {
        # [C]: Since $y is not an empty subtree, there are insertion
        #      tests remaining to be performed.
        if (insertion_valid($xlt, {first element child of $y}, $xrt)) {
          # [CA]: Current insertion is valid
          Call merge_subtrees_recursive(
	         {$xlt with the first child of $y appended},
	         $xrt, {$y with the first child removed})
        } else {
          # [CB]: Current insertion is invalid
          if (name match for first children in $xrt and $y subtrees) {
            # [CBA]: When the first element children in $xrt and $y
            #        have the same name, the subtrees consisting of the
            #        first elements in $xrt and $y need to be merged.
            $m = {Call merge_subtrees_recursive({empty}, 
                         {first child in $xrt}, 
                         {first child in $y})}
            Call merge_subtrees_recursive(
                   {$xlt with $m appended},
	           {$xrt with the first child removed},
	           {$y with the first child removed})
          } else {
            # [CBB]: Insertion of the first child element in $y is
            #        invalid, and the first child elements in $xrt
            #        and $y do not have matching names. Since the
            #        first child element in $y could neither be
            #        inserted nor merged at the current position,
            #        processing is moved to the next position
            if ($xrt subtree has no children) {
              # [CBBA]: The remaining children of $y must be discarded 
              #         since $xrt has no remaining children.
              Emit $xlt
            } else {
              # [CBBB]: Processing is moved to the next position by
              #         appending the first child element in $xrt
              #         onto the children of $xlt.
              Call merge_subtrees_recursive(
	             {$xlt with the first child of $xrt appended},
	             {$xrt with the first child removed}, $y)
            }
          }
        }
      }
    }     



    function insertion_valid($lt, $in, $rt) {
      $union = {subtree with the root element of $in and having as its
                children, in order, the element children of $lt, $in, 
                and $rt}
      if ($union is valid with respect to the root element content model) {
         return 1
      } else {
         return 0
      }
    }




  Assume element z has content model (b?,c?,d?,e?,f?,g?), the $x
  subtree consists of z as a parent element with children c,e,f,g, 
  and the $y subtree consists of z as a parent element with children
  b,d,f,h. The resulting recursive call sequence is illustrated below:

     $xlt                $xrt            $y
                         c e f g         b d f h
     b                   c e f g         d f h
     b c                 d e f g         f h
     b c d               e f g           f h
     b c d e             f g             f h
     b c d e f           g               h
     b c d e f g                         h
     b c d e f g h

-->

</xsl:stylesheet>