XSLT for flat to nested/hierarchical, with level i

Given this source XML document: input.xml

<body>
  <p ilvl="1">content</p>
  <p ilvl="1">content</p>
  <p ilvl="2">content</p>
  <p ilvl="3">content</p>

  <p ilvl="1">content</p>
  <p ilvl="2">content</p>
  <p ilvl="2">content</p>
  <p ilvl="3">content</p>
  <p ilvl="1">content</p>
  <p ilvl="1">content</p>
  <p ilvl="3">content</p>
</body>

I'd like to transform to output.xml:

<list>
  <item>
    <list>
      <item>
        <p ilvl="1">content</p>
      </item>
      <item>
        <p ilvl="1">content</p>
        <list>
          <item>
            <p ilvl="2">content</p>
            <list>
              <item>
                <p ilvl="3">content</p>
              </item>
            </list>
          </item>
        </list>
      </item>
    </list>
  </item>
  <item>
    <p ilvl="1">content</p>
    <list>
      <item>
        <p ilvl="2">content</p>

etc

Attribute ilvl is the list level; its a zero-based index.

I tried adapting https://stackoverflow.com/a/11117548/1031689 and got output:

<rs>
   <p ilvl="1"/>
   <p ilvl="1">
      <p ilvl="2">
         <p ilvl="3"/>
      </p>
   </p>
   <p ilvl="1">
      <p ilvl="2"/>
      <p ilvl="2">
         <p ilvl="3"/>
      </p>
   </p>
   <p ilvl="1"/>
   <p ilvl="1">
      <p ilvl="3"/>
   </p>
</rs>

I have 2 issues with it:

It doesn't create structure for any missing level (eg missing level 2 between 1 and 3), and
The starting param level must match the first entry (ie 1 here). If you pass 0, the nesting is wrong.

Before I tried this, I was using my own XSLT 1.0 code, attached below.

The tricky part is how to handle a decrease in nesting eg level 3 to 1:

  <p ilvl="3">content</p>
  <p ilvl="1">content</p>

Updated

I try to handle this in the addList template, as the recursion is "unwound", but its not quite right yet; in my output when it gets back to level 1 a new list is being inserted, but if I correct that, I drop the last 3 content items... If anyone can solve this, I'll be impressed :-)

Yeah, I know my code is way more complicated, so if there is any easy fix to the for-each-group approach above, it'd be great to have suggestions.

<?xml version="1.0" encoding="utf-8"?>
<xsl:stylesheet version="1.0" xmlns:xsl="http://www.w3.org/1999/XSL/Transform"
    xmlns:msxsl="urn:schemas-microsoft-com:xslt" exclude-result-prefixes="msxsl"
>
  <xsl:output method="xml" indent="yes"/>

  <!-- works, except makes new list for siblings -->

  <xsl:template name="listSection">
    <xsl:param name="last-level">-1</xsl:param>
    <xsl:param name="items"/>

    <xsl:variable name="currentItem" select="$items[1]"/>
    <xsl:variable name="currentLevel">
      <xsl:value-of select="number($currentItem/@ilvl)"/>
    </xsl:variable>

    <xsl:variable name="nextItems" select="$items[position() > 1]"/>


    <xsl:choose>

      <xsl:when test="$currentLevel = $last-level">
        <!-- just add an item -->
        <xsl:call-template name="addItem">
          <xsl:with-param name="currentItem"  select="$currentItem"/>
          <xsl:with-param name="nextItems"  select="$nextItems"/>
        </xsl:call-template>
        <!-- that handles next level higher case, and level same case-->

        <!-- level lower is handled is addList template-->

      </xsl:when>

      <xsl:when test="$currentLevel &gt; $last-level">

        <xsl:call-template name="addList">
          <xsl:with-param name="currentLevel"  select="$last-level"/>
          <xsl:with-param name="nextItems"  select="$items"/> <!-- since haven't handled current item yet -->
        </xsl:call-template>

      </xsl:when>

      <xsl:otherwise> this level &lt; last level: should not happen?</xsl:otherwise>

    </xsl:choose>

  </xsl:template>




  <xsl:template name="addItem">

    <xsl:param name="currentItem"/>
    <xsl:param name="nextItems"/>


    <xsl:variable name="currentLevel">
      <xsl:value-of select="number($currentItem/@ilvl)"/>
    </xsl:variable>

    <item>
      <xsl:apply-templates select="$currentItem"/>

      <!-- is the next level higher?-->

      <xsl:if test="(count($nextItems) &gt; 0) and
                                        (number($nextItems[1]/@ilvl) &gt; $currentLevel)">
        <!-- insert list/item to the necessary depth-->
        <xsl:call-template name="addList">
          <xsl:with-param name="currentLevel"  select="$currentLevel"/>
          <xsl:with-param name="nextItems"  select="$nextItems"/>
        </xsl:call-template>
      </xsl:if>
    </item>

    <!-- next level same-->
    <xsl:if test="(count($nextItems) &gt; 0) and
                                        (number($nextItems[1]/@ilvl) = $currentLevel)">

      <xsl:call-template name="addItem">
        <xsl:with-param name="currentItem"  select="$nextItems[1]"/>
        <xsl:with-param name="nextItems"  select="$nextItems[position() > 1]"/>
      </xsl:call-template>

    </xsl:if>

  </xsl:template>



  <xsl:template name="addList">

    <xsl:param name="currentLevel">-1</xsl:param>
    <xsl:param name="nextItems"/>

    <xsl:variable name="targetLevel">
      <xsl:value-of select="number($nextItems[1]/@ilvl)"/>
    </xsl:variable>

    <xsl:choose>

      <xsl:when test="$targetLevel - $currentLevel &gt; 1">
        <!-- interpolate -->
        <list>
          <xsl:variable name="stuff">
          <item>
            <xsl:call-template name="addList">
              <xsl:with-param name="currentLevel"  select="$currentLevel+1"/>
              <xsl:with-param name="nextItems"  select="$nextItems"/>
            </xsl:call-template>
          </item>
          </xsl:variable>

          <xsl:copy-of select="$stuff"/>

          <xsl:variable name="currentPos" select="count(msxsl:node-set($stuff)//p)" />

          <xsl:variable name="ascentLevel">
            <xsl:value-of select="number($nextItems[$currentPos]/@ilvl)"/>
          </xsl:variable>

          <xsl:variable name="ascentItems" select="$nextItems[position() > $currentPos]"/>

          <xsl:variable name="aftertargetLevel">
            <xsl:value-of select="number($ascentItems[1]/@ilvl)"/>
          </xsl:variable>

      <xsl:if test="(count($ascentItems) &gt; 1) and
                                    ($aftertargetLevel - $currentLevel = 1)">    
            <xsl:call-template name="listSection">
              <xsl:with-param name="last-level"  select="$currentLevel"/>
              <xsl:with-param name="items"  select="$ascentItems"/> 
            </xsl:call-template>

          </xsl:if>
        </list>


      </xsl:when>

      <xsl:when test="$targetLevel - $currentLevel = 1">
        <!-- insert real item -->

        <xsl:variable name="stuff">
          <list>
          <xsl:call-template name="addItem">
            <xsl:with-param name="currentItem"  select="$nextItems[1]"/>
            <xsl:with-param name="nextItems"  select="$nextItems[position() > 1]"/>
          </xsl:call-template>

        </list>
        </xsl:variable>

        <!-- might be items on the way out -->
        <xsl:copy-of select="$stuff"/>

        <xsl:variable name="currentPos" select="count(msxsl:node-set($stuff)//p)" />

        <xsl:variable name="ascentLevel">
          <xsl:value-of select="number($nextItems[$currentPos]/@ilvl)"/>
        </xsl:variable>

        <xsl:variable name="ascentItems" select="$nextItems[position() > $currentPos]"/>

        <xsl:variable name="aftertargetLevel">
          <xsl:value-of select="number($ascentItems[1]/@ilvl)"/>
        </xsl:variable>

      <xsl:if test="(count($ascentItems) &gt; 1) and
                                    ($aftertargetLevel - $currentLevel = 1)">    
          <xsl:call-template name="listSection">
            <xsl:with-param name="last-level"  select="$currentLevel"/> 
            <xsl:with-param name="items"  select="$ascentItems"/>
          </xsl:call-template>

        </xsl:if>


      </xsl:when>

      <xsl:otherwise>
        <!--should not happen!-->
      </xsl:otherwise>

    </xsl:choose>

  </xsl:template>


  <xsl:template match="@* | node()">
    <xsl:copy>
      <xsl:apply-templates select="@* | node()"/>
    </xsl:copy>
  </xsl:template>

  <xsl:template match="body">
    <xsl:call-template  name="listSection">
      <xsl:with-param name="items"  select="*"/>
    </xsl:call-template>


  </xsl:template>
</xsl:stylesheet>

This is my second attempt to provide solution to the problem which, in its current state forces people (at least me) to guess what is wanted:

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:param name="pStartLevel" select="1"/>

 <xsl:key name="kChildren" match="p"
  use="generate-id(preceding-sibling::p
                            [not(@ilvl >= current()/@ilvl)][1])"/>

 <xsl:template match="/*">
  <list>
    <item>
      <xsl:apply-templates select="key('kChildren', '')[1]" mode="start">
        <xsl:with-param name="pParentLevel" select="$pStartLevel"/>
        <xsl:with-param name="pSiblings" select="key('kChildren', '')"/>
      </xsl:apply-templates>
    </item>
  </list>
 </xsl:template>

 <xsl:template match="p" mode="start">
   <xsl:param name="pParentLevel"/>
   <xsl:param name="pSiblings"/>
   <list>
    <xsl:apply-templates select="$pSiblings">
      <xsl:with-param name="pParentLevel" select="$pParentLevel"/>
    </xsl:apply-templates>
  </list>
 </xsl:template>

 <xsl:template match="p">
   <xsl:param name="pParentLevel"/>
   <xsl:apply-templates select="self::*[@ilvl - $pParentLevel > 1]" 
                        mode="buildMissingLevels">
     <xsl:with-param name="pParentLevel" select="$pParentLevel"/>
   </xsl:apply-templates>
   <xsl:apply-templates select="self::*[not(@ilvl - $pParentLevel > 1)]" mode="normal">
     <xsl:with-param name="pParentLevel" select="$pParentLevel"/>
   </xsl:apply-templates>
 </xsl:template>

 <xsl:template match="p" mode="normal">
   <xsl:param name="pParentLevel"/>
   <item>
     <xsl:copy-of select="."/>
     <xsl:apply-templates mode="start"
             select="key('kChildren',generate-id())[1]">
        <xsl:with-param name="pParentLevel" select="@ilvl"/>
        <xsl:with-param name="pSiblings" 
             select="key('kChildren',generate-id())"/>
     </xsl:apply-templates>
   </item>
 </xsl:template>

 <xsl:template match="p" mode="buildMissingLevels">
   <xsl:param name="pParentLevel"/>
       <item>
         <p ilvl="{$pParentLevel +1}"/>
         <list>
           <xsl:apply-templates select=".">
             <xsl:with-param name="pParentLevel" select="$pParentLevel +1"/>
           </xsl:apply-templates>
         </list>
       </item>   
 </xsl:template>
</xsl:stylesheet>

when applied to the provided XML document:

<body>
  <p ilvl="1">content</p>
  <p ilvl="1">content</p>
  <p ilvl="2">content</p>
  <p ilvl="3">content</p>

  <p ilvl="1">content</p>
  <p ilvl="2">content</p>
  <p ilvl="2">content</p>
  <p ilvl="3">content</p>
  <p ilvl="1">content</p>
  <p ilvl="1">content</p>
  <p ilvl="3">content</p>
</body>

produces what I believe is wanted:

<list>
   <item>
      <list>
         <item>
            <p ilvl="1">content</p>
         </item>
         <item>
            <p ilvl="1">content</p>
            <list>
               <item>
                  <p ilvl="2">content</p>
                  <list>
                     <item>
                        <p ilvl="3">content</p>
                     </item>
                  </list>
               </item>
            </list>
         </item>
         <item>
            <p ilvl="1">content</p>
            <list>
               <item>
                  <p ilvl="2">content</p>
               </item>
               <item>
                  <p ilvl="2">content</p>
                  <list>
                     <item>
                        <p ilvl="3">content</p>
                     </item>
                  </list>
               </item>
            </list>
         </item>
         <item>
            <p ilvl="1">content</p>
         </item>
         <item>
            <p ilvl="1">content</p>
            <list>
               <item>
                  <p ilvl="2"/>
                  <list>
                     <item>
                        <p ilvl="3">content</p>
                     </item>
                  </list>
               </item>
            </list>
         </item>
      </list>
   </item>
</list>