XSLT Cookbook

Duplicating a String N Times

Problem

You need to duplicate a string N times, where N is a parameter. For example, you might need to pad out a string with spaces to achieve alignment.

Solution

A nice solution is a recursive approach that doubles the input string until it is the required length while being careful to handle cases in which $count is odd:

<xsl:template name="dup">
     <xsl:param name="input"/>
     <xsl:param name="count" select="1"/>
     <xsl:choose>
          <xsl:when test="not($count) or not($input)"/>
          <xsl:when test="$count = 1">
               <xsl:value-of select="$input"/>
          </xsl:when>
          <xsl:otherwise>
               <!-- If $count is odd append an extra copy of input -->
               <xsl:if test="$count mod 2">
                    <xsl:value-of select="$input"/>
               </xsl:if>
               <!-- Recursively apply template after doubling input and 
               halving count -->
               <xsl:call-template name="dup">
                    <xsl:with-param name="input" 
                         select="concat($input,$input)"/>
                    <xsl:with-param name="count" 
                         select="floor($count div 2)"/>
               </xsl:call-template>     
          </xsl:otherwise>
     </xsl:choose>
</xsl:template>

Discussion

The most obvious way to duplicate a string $count times is to figure out a way to concatenate the string to itself $count-1 times. This can be done recursively by the following code, but this code will be expensive unless $count is small, so it is not recommended:

<xsl:template name="slow-dup">
     <xsl:param name="input"/>
     <xsl:param name="count" select="1"/>
     <xsl:param name="work" select="$input"/>
     <xsl:choose>
          <xsl:when test="not($count) or not($input)"/>
          <xsl:when test="$count=1">
               <xsl:value-of select="$work"/>
          </xsl:when>
          <xsl:otherwise>
               <xsl:call-template name="slow-dup">
                    <xsl:with-param name="input" select="$input"/>
                    <xsl:with-param name="count" select="$count - 1"/>
                    <xsl:with-param name="work"
                         select="concat($work,$input)"/>
               </xsl:call-template>               
          </xsl:otherwise>
     </xsl:choose>
</xsl:template>

A better approach is shown in the “Solution” section. The solution limits the number of recursive calls and concatenation to the order of log2($count) by repeatedly doubling the input and halving the count as long as count is greater than 1. The slow-dup implementation is awkward since it requires an artificial work parameter to keep track of the original input. It may also result in stack growth due to recursion of $count-1 and requires $count-1 calls to concat( ). Contrast this to dup that limits stack growth to floor(log2($count)) and requires only ceiling(log2($count)) calls to concat( ).

Tip

The slow-dup technique has the redeeming quality of also being used to duplicate structure in addition to strings if we replace xsl:value-of with xsl:copy-of. The faster dup has no advantage in this case because the copies are passed around as parameters, which is expensive.

Another solution based on, but not identical to, code from EXSLT str:padding is the following:

<xsl:template name="dup">
  <xsl:param name="input"/>
  <xsl:param name="count" select="1"/>
  <xsl:choose>
    <xsl:when test="not($count) or not($input)" />
    <xsl:otherwise>
      <xsl:variable name="string" 
                      select="concat($input, $input, $input, $input, 
                                     $input, $input, $input, $input,
                                     $input, $input)"/>
      <xsl:choose>
        <xsl:when test="string-length($string) >= 
                         $count * string-length($input)">
          <xsl:value-of select="substring($string, 1, 
                              $count * string-length($input))" />
        </xsl:when>
        <xsl:otherwise>
          <xsl:call-template name="dup">
            <xsl:with-param name="input" select="$string" />
            <xsl:with-param name="count" select="$count div 10" />
          </xsl:call-template>
        </xsl:otherwise>
      </xsl:choose>
    </xsl:otherwise>
  </xsl:choose>
</xsl:template>

This implementation makes ten copies of the input. If this approach accomplishes more than is required, it trims the result to the required size. Otherwise, it applies the template recursively. This solution is slower because it will often do more concatenations than necessary and it uses substring( ), which may be slow on some XSLT implementations. See Recipe 1.7 for an explanation. It does have an advantage for processors that do not optimize tail recursion since it reduces the number of recursive calls significantly.

See Also

The so-called Piez Method can also duplicate a string without recursion. This method is discussed at http://www.xml.org/xml/xslt_efficient_programming_techniques.pdf. It uses a for-each loop on any available source of nodes (often the stylesheet itself). Although this method can be highly effective in practice, I find it deficient because it assumes that enough nodes will be available to satisfy the required iteration.