Move separator elements upwards in xml hierarchy

Question

I have an xml document with separators deep down in the hierarchy.

<A>
  <B>
    <C id='1'/>
    <separator/>
    <C id='2'/>
  </B>
  <B>
    <C id='3'/>
    <separator/>
  </B>
  <B>
    <C id='4'/>
  </B>
</A>

I want to move the separators upwards, keeping elements in order. So the desired output is

<A>
  <B>
    <C id='1'/>
  </B>
</A>
<separator/>
<A>
  <B>
    <C id='2'/>
  </B>
  <B>
    <C id='3'/>
  </B>
</A>
<separator/>
<A>
  <B>
    <C id='4'/>
  </B>
</A>

How can it be done using xslt 1.0 only? Can it be done without for-each, using template match only?

UPDATE: I actually got 4 brilliant answers of different levels of generality, thank you, guys.

Answer 1

This stylesheet:

<xsl:stylesheet version="1.0" xmlns:xsl="http://www.w3.org/1999/XSL/Transform">
    <xsl:key name="kCByFollSep" match="C"
             use="generate-id(following::separator[1])"/>
    <xsl:template match="A">
        <xsl:for-each select="B/separator|B[last()]/*[last()]">
            <A>
                <xsl:apply-templates
                     select="key('kCByFollSep',
                                 substring(generate-id(),
                                           1 div boolean(self::separator)))"/>
            </A>
            <xsl:copy-of select="self::separator"/>
        </xsl:for-each>
    </xsl:template>
    <xsl:template match="C">
        <B>
            <xsl:copy-of select="."/>
        </B>
    </xsl:template>
</xsl:stylesheet>

Output:

<A>
    <B>
        <C id="1" />
    </B>
</A>
<separator />
<A>
    <B>
        <C id="2" />
    </B>
    <B>
        <C id="3" />
    </B>
</A>
<separator />
<A>
    <B>
        <C id="4" />
    </B>
</A>

Note: Grouping by following separator, adding last third level element for posible C without following separator.

Edit: More pull style, more schema agnostic, this stylesheet:

<xsl:stylesheet version="1.0" xmlns:xsl="http://www.w3.org/1999/XSL/Transform">
    <xsl:key name="kCByFollSep" match="C"
             use="generate-id(following::separator[1])"/>
    <xsl:template match="text()"/>
    <xsl:template match="separator|*[not(*)][not(following::*)]">
        <A>
            <xsl:apply-templates
                     select="key('kCByFollSep',
                                 substring(generate-id(),
                                           1 div boolean(self::separator)))"
                     mode="output"/>
        </A>
        <xsl:copy-of select="self::separator"/>
    </xsl:template>
    <xsl:template match="C" mode="output">
        <B>
            <xsl:copy-of select="."/>
        </B>
    </xsl:template>
</xsl:stylesheet>

EDIT 2: More general solution (one thing I do not trust, ja!)

<xsl:stylesheet version="1.0" xmlns:xsl="http://www.w3.org/1999/XSL/Transform">
    <xsl:template match="node()|@*" name="identity">
        <xsl:param name="pRemains"/>
        <xsl:copy>
            <xsl:apply-templates select="node()[descendant-or-self::node()
                                                   [not(self::separator)]
                                                   [count(following::separator)
                                                    = $pRemains]
                                               ][1]|@*">
                <xsl:with-param name="pRemains" select="$pRemains"/>
            </xsl:apply-templates>
        </xsl:copy>
        <xsl:apply-templates select="following-sibling::node()
                                        [descendant-or-self::node()
                                           [not(self::separator)]
                                           [count(following::separator)
                                            = $pRemains]
                                        ][1]">
            <xsl:with-param name="pRemains" select="$pRemains"/>
        </xsl:apply-templates>
    </xsl:template>
    <xsl:template match="/*">
        <xsl:variable name="vCurrent" select="."/>
        <xsl:for-each select="descendant::separator|node()[last()]">
            <xsl:variable name="vRemains" select="last()-position()"/>
            <xsl:for-each select="$vCurrent">
                <xsl:copy>
                    <xsl:apply-templates
                         select="node()[descendant::node()
                                          [not(self::separator)]
                                          [count(following::separator)
                                           = $vRemains]
                                       ][1]">
                        <xsl:with-param name="pRemains" select="$vRemains"/>
                    </xsl:apply-templates>
                </xsl:copy>
            </xsl:for-each>
            <xsl:copy-of select="self::separator"/>
        </xsl:for-each>
    </xsl:template>
    <xsl:template match="separator"/>
</xsl:stylesheet>

Note: Mostly a fine grained traversal. A floor hierarchy rule (in this case root element) copying itself and separator (dummy node for last group without following separator) passing remainder separators to process first child with enough following separators to process. A modified fine grained traversal identity rule, copying itself and again processing first child and following sibling with enough following separators to process. At last, a separator rule breaking the process.

Edit 3: Other more general solution, now with recursive identity rule

<xsl:stylesheet version="1.0" xmlns:xsl="http://www.w3.org/1999/XSL/Transform">
    <xsl:output indent="yes"/>
    <xsl:key name="kNodeByFolSep" match="node()[not(self::separator)]"
          use="generate-id((descendant::separator|following::separator)[1])"/>
    <xsl:template match="node()|@*" name="identity">
        <xsl:param name="pGroup"/>
        <xsl:copy>
            <xsl:apply-templates
               select="node()[descendant-or-self::node()[count(.|$pGroup)
                                                         = count($pGroup)]]|@*">
                <xsl:with-param name="pGroup" select="$pGroup"/>
            </xsl:apply-templates>
        </xsl:copy>
    </xsl:template>
    <xsl:template match="/*">
        <xsl:variable name="vCurrent" select="."/>
        <xsl:for-each select="descendant::separator|node()[last()]">
            <xsl:variable name="vGroup"
                 select="key('kNodeByFolSep',generate-id(self::separator))"/>
            <xsl:for-each select="$vCurrent">
                <xsl:call-template name="identity">
                    <xsl:with-param name="pGroup" select="$vGroup"/>
                </xsl:call-template>
            </xsl:for-each>
            <xsl:copy-of select="self::separator"/>
        </xsl:for-each>
    </xsl:template>
    <xsl:template match="separator"/>
</xsl:stylesheet>

Edit 4: Now just the same as before but with key test instead of node set intersection.

<xsl:stylesheet version="1.0" xmlns:xsl="http://www.w3.org/1999/XSL/Transform">
    <xsl:output indent="yes"/>
    <xsl:key name="kNodeByFolSep" match="node()[not(self::separator)]"
          use="concat(generate-id(),'+',
                      generate-id((descendant::separator|
                                   following::separator)[1]))"/>
    <xsl:template match="node()|@*" name="identity">
        <xsl:param name="pSeparator"/>
        <xsl:copy>
            <xsl:apply-templates
               select="@*|node()[descendant-or-self::node()
                                    [key('kNodeByFolSep',
                                         concat(generate-id(),
                                                '+',
                                                $pSeparator))]]">
                <xsl:with-param name="pSeparator" select="$pSeparator"/>
            </xsl:apply-templates>
        </xsl:copy>
    </xsl:template>
    <xsl:template match="/*">
        <xsl:variable name="vCurrent" select="."/>
        <xsl:for-each select="descendant::separator|node()[last()]">
            <xsl:variable name="vSeparator"
                          select="generate-id(self::separator)"/>
            <xsl:for-each select="$vCurrent">
                <xsl:call-template name="identity">
                    <xsl:with-param name="pSeparator" select="$vSeparator"/>
                </xsl:call-template>
            </xsl:for-each>
            <xsl:copy-of select="self::separator"/>
        </xsl:for-each>
    </xsl:template>
    <xsl:template match="separator"/>
</xsl:stylesheet>

Answer 2

This transformation:

<xsl:stylesheet version="1.0"
    xmlns:xsl="http://www.w3.org/1999/XSL/Transform">
    <xsl:output omit-xml-declaration="yes" indent="yes"/>
    <xsl:strip-space elements="*"/>

    <xsl:key name="kFollowing" match="C"
         use="generate-id(preceding::separator[1])"/>

 <xsl:template match="/">
  <xsl:apply-templates select="*/*/separator"/>
 </xsl:template>

 <xsl:template match="separator" name="commonSep">
  <separator/>
  <xsl:call-template name="genAncestors">
   <xsl:with-param name="pAncs" select="ancestor::*"/>
   <xsl:with-param name="pLeaves"
        select="key('kFollowing', generate-id())"/>
  </xsl:call-template>
 </xsl:template>

 <xsl:template match="separator[not(preceding::separator)]">
  <xsl:call-template name="genAncestors">
   <xsl:with-param name="pAncs" select="ancestor::*"/>
   <xsl:with-param name="pLeaves"
        select="key('kFollowing', '')"/>
  </xsl:call-template>
  <xsl:call-template name="commonSep"/>
 </xsl:template>

 <xsl:template name="genAncestors">
   <xsl:param name="pAncs" select="ancestor::*"/>
   <xsl:param name="pLeaves" select="."/>

   <xsl:choose>
    <xsl:when test="not($pAncs[2])">
     <xsl:apply-templates select="$pLeaves" mode="gen"/>
    </xsl:when>
    <xsl:otherwise>
     <xsl:for-each select="$pAncs[1]">
      <xsl:copy>
        <xsl:copy-of select="@*"/>
        <xsl:call-template name="genAncestors">
               <xsl:with-param name="pAncs" select="$pAncs[position()>1]"/>
               <xsl:with-param name="pLeaves" select="$pLeaves"/>
        </xsl:call-template>
      </xsl:copy>
     </xsl:for-each>
    </xsl:otherwise>
   </xsl:choose>
 </xsl:template>

 <xsl:template match="C" mode="gen">
  <xsl:variable name="vCur" select="."/>
  <xsl:for-each select="..">
   <xsl:copy>
    <xsl:copy-of select="@*|$vCur"/>
   </xsl:copy>
  </xsl:for-each>
 </xsl:template>
</xsl:stylesheet>

when applied on the provided XML document:

<A>
  <B>
    <C id='1'/>
    <separator/>
    <C id='2'/>
  </B>
  <B>
    <C id='3'/>
    <separator/>
  </B>
  <B>
    <C id='4'/>
  </B>
</A>

produces the wanted, correct result:

<A>
   <B>
      <C id="1"/>
   </B>
</A>
<separator/>
<A>
   <B>
      <C id="2"/>
   </B>
   <B>
      <C id="3"/>
   </B>
</A>
<separator/>
<A>
   <B>
      <C id="4"/>
   </B>
</A>