[XSL-LIST Mailing List Archive Home]
[By Thread]
[By Date]
RE: [xsl] Parser implemented in XSL -- stack overflow
Subject: RE: [xsl] Parser implemented in XSL -- stack overflow From: "Michael Kay" <mhk@xxxxxxxxx> Date: Wed, 2 Apr 2003 10:22:05 +0100 |
> > 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. The call: <xsl:apply-templates select="following-sibling::*[1]" mode="sn5"> <xsl:with-param name="parents" select="concat($ID, ',', $adjustedParents)" /> </xsl:apply-templates> will generate a new stack frame for each sibling that is processed. A system that optimizes tail recursion can avoid this, but not many systems do. Saxon optimizes tail calls only for a self-recursive call-template, not for apply-templates. There's no inherent reason for this, it's just the way it is. Michael Kay Software AG home: Michael.H.Kay@xxxxxxxxxxxx work: Michael.Kay@xxxxxxxxxxxxxx > > 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()[@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="{@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 > XSL-List info and archive: http://www.mulberrytech.com/xsl/xsl-list
Current Thread |
---|
|
<- Previous | Index | Next -> |
---|---|---|
[xsl] Parser implemented in XSL -- , Bill Cohagan | Thread | RE: [xsl] Parser implemented in XSL, Bill Cohagan |
Re: [xsl] Replacing DTD reference w, David Carlisle | Date | RE: [xsl] Sort doesn't seem to sort, Michael Kay |
Month |