Using Recursion to Do Most Anything (XSLT)

4.6.1. Implementing a String Replace Function

To demonstrate how to use recursion to solve problems, we'll write a string replace function. This is sometimes useful when you need to escape certain characters or substrings in your output. The stylesheet we'll develop here transforms an XML document into a set of SQL statements that will be executed at a Windows command prompt. We have to do several things:

Put a caret (^) in front of all ampersands (&)

4.6.1.1. Procedural design

Three functions we could use in our template are concat(), substring-before(), and substring-after(). To replace an ampersand with a caret and an ampersand, this would do the trick:

<xsl:value-of select="concat(substring-before(., '&amp;'), '^&amp;', 
                             substring-after(., '&amp;'))"/>

The obvious problem with this step is that it only replaces the first occurrence of the ampersand. If there are two ampersands, or three, or three hundred, we need to call this method once for each ampersand in the original string. Because of the way variables work, we can't do what we'd do in a procedural language:

private static String strChange(String string, String from, String to)
{
  String before = "", after = "";
  int    index;

  index = string.indexOf(from);
  while (index >= 0)
  {
    before = string.substring(0, index);
    after = string.substring(index + from.length());
    string = before + to + after;

    index = string.indexOf(from, index + to.length());
  }

  return string;
}

4.6.1.2. Recursive design

To implement a string replace function with recursion, we take a modified version of the approach we used here. We build the replaced string in three pieces:

Everything up to the first occurrence of the substring we're replacing. If the substring doesn't exist in the main string, then this is the entire string.
The replacement substring. If the substring we're replacing doesn't exist in the main string, then this is blank.
Everything after the first occurrence of the substring. If the substring doesn't exist in the main string, then this is blank.

The third portion is where we use recursion. If the substring we're replacing occurs in that part of the main string, we call the substring replace function on the last of the string. The key here, as with all recursive functions, is that we have an exit case, a condition in which we don't recurse. If the substring doesn't occur in the last portion of the string, we're done.

Here's the design in pseudocode:

replaceSubstring(originalString, substring, replacementString)
{
  if (contains(originalString, substring))
    firstOfString = substring-before(originalString, substring)
  else
    firstOfString = originalString

  if (contains(originalString, substring))
    middleOfString = replacementString
  else
    middleOfString = ""

  if (contains(originalString, substring))
  {
    if (contains(substring-after(originalString, substring), substring))
     lastOfString = replaceString(substring-after(originalString, substring), 
                                  substring, replacementString)
    else
      lastOfString = substring-after(originalString, substring)
  }
  concat(firstOfString, middleOfString, lastOfString)
}

In the recursive approach, the function calls itself whenever there's at least one more occurrence of the substring. Each time the function calls itself, the originalString parameter is a little smaller, until eventually we've processed the complete string. Here's the complete template:

<xsl:template name="replace-substring">
  <xsl:param name="original"/>
  <xsl:param name="substring"/>
  <xsl:param name="replacement" select="''"/>
  <xsl:variable name="first">
    <xsl:choose>
      <xsl:when test="contains($original, $substring)">
        <xsl:value-of select="substring-before($original, $substring)"/>
      </xsl:when>
      <xsl:otherwise>
        <xsl:value-of select="$original"/>
      </xsl:otherwise>
    </xsl:choose>
  </xsl:variable>
  <xsl:variable name="middle">
    <xsl:choose>
      <xsl:when test="contains($original, $substring)">
        <xsl:value-of select="$replacement"/>
      </xsl:when>
      <xsl:otherwise>
        <xsl:text></xsl:text>
      </xsl:otherwise>
    </xsl:choose>
  </xsl:variable>
  <xsl:variable name="last">
    <xsl:choose>
      <xsl:when test="contains($original, $substring)">
        <xsl:choose>
          <xsl:when test="contains(substring-after($original, $substring), 
                                   $substring)">
            <xsl:call-template name="replace-substring">
              <xsl:with-param name="original">
                <xsl:value-of select="substring-after($original, $substring)"/>
              </xsl:with-param>
              <xsl:with-param name="substring">
                <xsl:value-of select="$substring"/>
              </xsl:with-param>
              <xsl:with-param name="replacement">
                <xsl:value-of select="$replacement"/>
              </xsl:with-param>
            </xsl:call-template>
          </xsl:when>
          <xsl:otherwise>
            <xsl:value-of select="substring-after($original, $substring)"/>
          </xsl:otherwise>
        </xsl:choose>
      </xsl:when>
      <xsl:otherwise>
        <xsl:text></xsl:text>
      </xsl:otherwise>
    </xsl:choose>
  </xsl:variable>
  <xsl:value-of select="concat($first, $middle, $last)"/>
</xsl:template>

This style of programming takes some getting used to, but whatever you want to do can usually be done. Our example here is a good illustration of the techniques we've discussed in this chapter, including branching statements, variables, invoking templates by name, and passing parameters.

4.6. Using Recursion to Do Most Anything

4.6.1. Implementing a String Replace Function

4.6.1.1. Procedural design

4.6.1.2. Recursive design