xsl-list
[Top] [All Lists]

Parser implemented in XSL -- stack overflow

2003-04-01 15:36:22
I am experiencing stack overflow with an XSL program and don't understand
why. Following is a description of the program and some sample code.

I have an application that generates XSL code that is intended to implement
a "parser" (actually a Deterministic Finite State Transducer). This parser
accepts a "flat" sequence of elements and transforms it into a nested
structure according to a grammar (XSD) that is used by my app to generate
the XSL. Obviously there are other ways to do this, one being simply to
implement a DFST interpreter in Java, VB, etc. Being an XSL fan however I
decided to try it in XSL.

The two problems to be solved were to process the input "left to right" and
to implement "states" somehow. I avoided generating/using named templates
due to past experience with stack overflow. So what I did was to use
template modes to specify state and to use a select expression on my
apply-templates calls so that only the "next" input element would be
considered. Here's a "typical" template from my XSL program:


  <xsl:template match="node()[(_at_)Style = 'H-stage-level']" mode="sn1">
    <xsl:param name="parents" />
    <!--Push-->
    <xsl:variable name="adjustedParents" select="$parents" />
    <xsl:variable name="ID" select="generate-id()" />
    <MaturityStage Style="H-stage-level" ParaNumber="{(_at_)ParaNumber}"
id="{$ID}" parent="{substring-before($adjustedParents, ',')}" />
    <xsl:apply-templates select="following-sibling::*[1]" mode="sn5">
      <xsl:with-param name="parents" select="concat($ID, ',',
$adjustedParents)" />
    </xsl:apply-templates>
  </xsl:template>



So this template matches an input element that has the indicated Style
attribute. In DFST terms this template corresponds to the action to take if
you encounter an H-stage-level input while in state "sn1". That action is to
emit a MaturityStage element and transition to state "sn5". Note the use of
following-sibling::[1] to restrict the match to the next element in the
input. The "parents" paramater is a csv string used like a stack to control
creation of "parent pointers" in the emitted elements.

All of the templates are of this general form, although some of them do a
"pop" on the csv; e.g., 

  <xsl:variable name="adjustedParents" select="substring-after($parents,
',')" />

Again, there are NO call-template elements in the XSL, only
xsl:apply-templates calls of the general form above. It is also the case
that all such apply-template calls are tail recursive.

I have experienced stack overflow with MSXML4, with the MS .Net XSL engine
and with Saxon6.5.2 (which I believe implements proper tail recursion.) The
stack growth appears to be proportional to the XML input size; i.e., for
files up to a "certain size" there is no overflow and the transformation
works as expected.

Can anyone explain to me why this "style" of XSL should cause stack growth
proportional to input size? Obviously it is not generally the case that
stack growth is proportional to input size -- or XSL wouldn't be very
interesting!

Thanks in advance,
 Bill Cohagan


 XSL-List info and archive:  http://www.mulberrytech.com/xsl/xsl-list



<Prev in Thread] Current Thread [Next in Thread>