Silvester Party XSLT

After finishing my Code Cop Journeyman Tour last month I am free for new adventures. My backlog of insights I want to share is huge, but today I will celebrate the turn of the year. In Austria we usually celebrate the New Year's Eve with a party so let's see the results of my Silvester "party".

Last Global Day of Coderetreat, one participant used MSBuild to implement the rules of Conway's Game of Life. Maybe it did not improve his grasp of object orientation but surely trained his skills of writing build scripts and besides all it looked like a lot of fun. I have worked on the Game of Life in many mainstream programming languages, e.g. Java, JavaScript, Ruby and Scala as well some as less common languages like Dart, Pascal or even good old BASIC. MSBuild seemed like a perfect change from the usual and made me think about unfamiliar or even bizarre approaches, e.g. using Apache Ant or even XSLT (XSL transformations).

Over the years I have implemented the Prime Factors kata and the FizzBuzz kata in XSLT but never anything more elaborate. Although XSLT is a Turing complete language, I was not sure it would work out. On the other hand, the representation of the universe, i.e. the cells and their neighbours, might be some basic XML structure removing the need to implement any complex data structures. I even chose an HTML table to make visualization trivial.

<table>
  <tr><td>_</td><td>X</td><td>_</td></tr>
  <tr><td>_</td><td>X</td><td>_</td></tr>
  <tr><td>_</td><td>X</td><td>_</td></tr>
</table>

Based on this data structure I started writing XSLTunit test cases for evolving a 3x3 grid:

• dead cells should stay dead
• a single living cell in the middle should die
• the 2x2 block in the upper left should stay alive
• the 2x2 block in the lower right should stay alive
• two single cells in the upper left should die

By triangulating the fake implementations I approached a solution, at least that was what I thought. It turned out that I did not nearly know enough about XPath and most of my selectors using parent, preceding-sibling or following-sibling were wrong but happened to return an expected result in my test cases. When I thought I had finished the code nothing worked as expected. Now how would I debug my XSLT code? No, I hate debugging and took a step back to write some tests to verify the selection of the living neighbours alone:

<xsl:template match="td" mode="countLiveNeighbours">
  <xsl:variable name="currentX"
                select="count(preceding-sibling::td) + 1" />
  <xsl:variable name="precedingRow"
                select="parent::tr/preceding-sibling::tr[1]" />
  <xsl:variable name="followingRow"
                select="parent::tr/following-sibling::tr[1]" />

  <xsl:variable name="neighbours"
                select="$precedingRow/td[$currentX - 1] |
                        $precedingRow/td[$currentX] |
                        $precedingRow/td[$currentX + 1] |
                        preceding-sibling::td[1] |
                        following-sibling::td[1] |
                        $followingRow/td[$currentX - 1] |
                        $followingRow/td[$currentX] |
                        $followingRow/td[$currentX + 1]" />

  <xsl:value-of select="count($neighbours[text() = 'X'])" />
</xsl:template>

As soon as I finished the countLiveNeighbours template, my previously created solution worked as expected.

<xsl:template match="td">
  <xsl:variable name="liveNeighbours">
    <xsl:apply-templates select="current()" mode="countLiveNeighbours" />
  </xsl:variable>

  <xsl:choose>
    <xsl:when test="(current() = 'X' and $liveNeighbours = 2) or
                    $liveNeighbours = 3">
      <xsl:call-template name="live" />
    </xsl:when>
    <xsl:otherwise>
      <xsl:call-template name="die" />
    </xsl:otherwise>
  </xsl:choose>
</xsl:template>

I had chosen XSLT as bizarre approach on purpose, so I guess it is ok that it took me eight hours of Silvester to figure out the above solution ;-)

XSLTunit Ant Support

Last year I did the Prime Factors Kata in XSLT. Using XSLTunit I created a test case that applied the template to a number to calculate its prime factors. I focused on the coding problem and ignored the testing infrastructure, calling the XSLT processor from the command line and looking into the generated XML test result to see if any assert had failed. When I felt like playing with XSLT again, I first had to fix the infrastructure and make it ready for Continuous Integration.

Ant Support
CI tools like Jenkins are able to call any script, but my first idea for build automation is always Ant. I have some history with Ant but most likely I use it because I am an old school Java developer ;-). Fortunately Ant has build-in XSLT support which I can use to apply the XSLTunit template.

<property name="test_prefix" value="tst_" />
<property name="test_result_suffix" value=".test_result.xml" />

<!-- apply style to XMLs in suite -->
<xslt basedir="${suite}" destdir="${suite}" style="${suite}/${style}">
  <include name="*.xml" />
  <exclude name="*${test_result_suffix}" />
</xslt>

<!-- apply test -->
<xslt basedir="${suite}" destdir="${suite}" style="${suite}/${test_prefix}${style}"
      extension="${test_result_suffix}">
  <include name="*.xsl" />
  <exclude name="${test_prefix}*.xsl" />
</xslt>

<!-- create readable HTML test report -->
<xslt basedir="${suite}" destdir="${suite}" style="${basedir}/lib/xsltunit_report.xsl">
  <include name="*${test_result_suffix}" />
  <param name="testname" expression="${style}" />
</xslt>

My approach contains a lot of "convention over configuration". For example I assume that each template ${style} is located inside its own folder ${suite}. The given Ant target first transforms sample data with the template under test for manual review, then applies the test case to the template and finally generates a readable report out of the test result. The first and last step is optional but useful during development. In the end the test result is checked for the text "failed" which shows a failed assertion.

<dirname property="suite" file="${testResult}" />
<loadfile property="test_failed" srcFile="${testResult}" />
<fail message="Test ${suite} failed!">
  <condition>
    <contains string="${test_failed}"
              substring="outcome=&quot;failed&quot;" />
  </condition>
</fail>

Testing and checking the result is done for all templates in the source folder ${src} by using <foreach> from Ant-Contrib.

<foreach target="-testFolder" param="foreach">
  <path>
    <fileset dir="${src}">
      <include name="**/*.xsl" />
      <exclude name="**/${test_prefix}*.xsl" />
    </fileset>
  </path>
</foreach>

<foreach target="-verifyResult" param="foreach">
  <path>
    <fileset dir="${src}">
      <include name="**/*${test_result_suffix}" />
    </fileset>
  </path>
</foreach>

FizzBuzz Kata
After the unit tests were executed by Continuous Integration for each commit, I went for some XSLT exercise. Unfortunately adding the Ant support had taken too much of my scheduled learning time and I had to work with the smallest kata available, the FizzBuzz question: Write a program that prints the numbers from 1 to 100. But for multiples of three print "Fizz" instead of the number and for the multiples of five print "Buzz". For numbers which are multiples of both three and five print "FizzBuzz". I wrote the following template by following a few XSLTunit tests.

<xsl:template match="value" mode="fizzbuzz">
  <xsl:choose>
    <xsl:when test="number(current()) mod 15 = 0">FizzBuzz</xsl:when>
    <xsl:when test="number(current()) mod 3 = 0">Fizz</xsl:when>
    <xsl:when test="number(current()) mod 5 = 0">Buzz</xsl:when>
    <xsl:otherwise><xsl:value-of select="." /></xsl:otherwise>
  </xsl:choose>
</xsl:template>

To solve the complete question I applied the template to the values of 1 till 100,

<numbers>
  <number><value>1</value></number>
  <number><value>2</value></number>
  <number><value>3</value></number>
  <number><value>4</value></number>
  ...
  <number><value>100</value></number>
</numbers>

which generated a HTML file with the answer of the FizzBuzz question.

• for 1 say 1
• for 2 say 2
• for 3 say Fizz
• for 4 say 4
• ...
• for 100 say Buzz

Prime Factors XSLT

Here is a short conversation we had at Hackergarten Vienna yesterday:

I did the Prime Factors Kata in XSLT. Would you like to review it?
You did WHAT?
You know, this small program. It's calculating the prime factors of a number.
But what? In XSLT? Why XSLT?
I know that it sounds a bit crazy. I had performed the kata in all programming languages which I know, e.g. Java, Ruby and even old BASIC or Turbo Pascal, but not using XSL transformations. So I just had to do it.

Initial Version
Using XSLTunit I created a test case that would apply the template to <value> to calculate the prime factors of the given source.

<xsltu:test id="test-template-factors-one">
  <xsl:variable name="source">
  <value>1</value>
  </xsl:variable>
  <xsl:call-template name="xsltu:assertEqual">
  <xsl:with-param name="id" select="'template factors 1'" />
  <xsl:with-param name="nodes1">
    <xsl:apply-templates select="exsl:node-set($source)/value" />
  </xsl:with-param>
  <xsl:with-param name="nodes2"></xsl:with-param>
  </xsl:call-template>
</xsltu:test>

...

<xsltu:test id="test-template-factors-four">
  <xsl:variable name="source">
  <value>9</value>
  </xsl:variable>
  <xsl:call-template name="xsltu:assertEqual">
  <xsl:with-param name="id" select="'template factors 4'" />
  <xsl:with-param name="nodes1">
    <xsl:apply-templates select="exsl:node-set($source)/value" />
  </xsl:with-param>
  <xsl:with-param name="nodes2">3 3</xsl:with-param>
  </xsl:call-template>
</xsltu:test>

and so on. The result looked like that:

<xsl:template match="value">
  <xsl:call-template name="generate">
  <xsl:with-param name="number" select="number(current())" />
  <xsl:with-param name="candidate" select="number(2)" />
  </xsl:call-template>
</xsl:template>

<xsl:template name="generate">
  <xsl:param name="number" />
  <xsl:param name="candidate" />
  <xsl:choose>
  <!-- one is no prime and does not have any factors -->
  <xsl:when test="$number = 1"></xsl:when>
  <!-- candidate == number, so number is a prime -->
  <xsl:when test="$candidate = $number">
    <xsl:value-of select="$number" />
  </xsl:when>
  <!-- number is factored by the candidate, factor it -->
  <xsl:when test="$number mod $candidate = 0">
    <xsl:value-of select="$candidate" />
    <xsl:text> </xsl:text>
    <xsl:call-template name="generate">
    <xsl:with-param name="number" select="$number div $candidate" />
      <xsl:with-param name="candidate" select="$candidate" />
      </xsl:call-template>
    </xsl:when>
    <!-- try again with the next factor -->
    <xsl:otherwise>
      <xsl:call-template name="generate">
        <xsl:with-param name="number" select="$number" />
        <xsl:with-param name="candidate" select="$candidate + 1" />
      </xsl:call-template>
    </xsl:otherwise>
  </xsl:choose>
</xsl:template>

StackOverflowError
Using javax.xml.transform.TransformerFactory from Java 6 to run the XSLT transformation, the last prime that was processed successfully was 7351. Calling generate with the following prime (7369) caused a StackOverflowError inside Apache Xalan due to the recursion. As there was no need to try candidates larger than the square root of number, I replaced the test for $candidate = $number with $candidate * $candidate > $number. This brought me as far as 54184313.

Reducing the Stack Depth
XSLT is a functional language, there are no loops, the only way to iterate is recursion. So the size of the largest prime to process is limited by the size of the stack. Still half of the recursions are useless because no even number larger than two can be a prime.

<!-- try again with the next factor -->
  <xsl:otherwise>
    <xsl:choose>
      <xsl:when test="$candidate = 2">
        <xsl:call-template name="generate">
          <xsl:with-param name="number" select="$number" />
          <xsl:with-param name="candidate" select="$candidate + 1" />
        </xsl:call-template>
      </xsl:when>
      <xsl:otherwise>
        <xsl:call-template name="generate">
          <xsl:with-param name="number" select="$number" />
          <xsl:with-param name="candidate" select="$candidate + 2" />
        </xsl:call-template>
      </xsl:otherwise>
    </xsl:choose>
  </xsl:otherwise>

This can be improved further by unrolling the (recursive) loop. If number is not factored by candidate + 2 then the next one is candidate + 4 and so on.

<!-- try again with the next factor -->
  <xsl:otherwise>
    <xsl:choose>
      <xsl:when test="$candidate = 2">
        <xsl:call-template name="generate">
          <xsl:with-param name="number" select="$number" />
          <xsl:with-param name="candidate" select="$candidate + 1" />
        </xsl:call-template>
      </xsl:when>
      <xsl:when test="$number mod ($candidate + 2) = 0">
        <xsl:call-template name="generate">
          <xsl:with-param name="number" select="$number" />
          <xsl:with-param name="candidate" select="$candidate + 2" />
        </xsl:call-template>
      </xsl:when>
      <xsl:when test="$number mod ($candidate + 4) = 0">
        <xsl:call-template name="generate">
          <xsl:with-param name="number" select="$number" />
          <xsl:with-param name="candidate" select="$candidate + 4" />
        </xsl:call-template>
      </xsl:when>
      <xsl:otherwise>
        <xsl:call-template name="generate">
          <xsl:with-param name="number" select="$number" />
          <xsl:with-param name="candidate" select="$candidate + 6" />
        </xsl:call-template>
      </xsl:otherwise>
    </xsl:choose>
  </xsl:otherwise>