Open Bug 138183 Opened 22 years ago Updated 2 years ago

Improve handling of recursive template invocation

Categories

(Core :: XSLT, enhancement)

Product:
Core
Component:
XSLT
Type:
enhancement

Tracking

()

Milestone:
Future

People

(Reporter: axel, Unassigned)

References

(Blocks 1 open bug,
URL
)

Details

Attachments

(1 obsolete file) 

XSLT has the ability of circular references thru
<xsl:apply-templates select="some reference to non-child nodes" />.

We might not get all, but we might wanna catch at least obvious ones like
select="." without changing the mode.

As the spec doesn't require this, it's just an enhancement.
The only (non-insane-complicated) way i can think of to fully fix this is to 
count the template-recursion-depth and stop at, say, 500. Should be pretty easy 
to hook into XSLTProcessor::processTemplate.

We can't just catch select="." in apply-templates since that can be legal, for 
example:

<template match="foo">
  <param name="value" select="500"/>
  <if test="$value &gt; 500">
    <apply-templates select="."/>
  </if>
  <if test="$value &lt;= 500 and $value &gt; 0">
    <value-of select="$value"/>
    <apply-templates select=".">
      <with-param select="$value - 1"/>
    </apply-templates>
  </if>
</template>

counts from param "value" (limited and defaulted to 500) down to 1
I don't think we should vaguely catch all recursions, but instead just
catch easy-to-detect short loops. At least in the first pass.
Those are:
<xsl:apply-templates /> and <xsl:call-template /> could check if
xslTemplate is the current template and if (actualParams->isEmpty()) in
XSLTProcessor::processAction if we add the template to the TemplateRule

This one is indeed pretty easy, huh? And should catch at least the typos or 
easy to solve stylesheet errors.
Everything that goes further would require us to hold a stack, and presumably on
every Nth run check the stack for the current template and compare the variable
bindings. I don't feel too good about such a thing, I'm afraid it'll get costly.
Blocks: 112622
> I don't think we should vaguely catch all recursions, but instead just
> catch easy-to-detect short loops. At least in the first pass.
> Those are:
> <xsl:apply-templates /> and <xsl:call-template /> could check if
> xslTemplate is the current template and if (actualParams->isEmpty()) in
> XSLTProcessor::processAction if we add the template to the TemplateRule

Nope, that will not work. Calling the current template without providing any 
parameters is legal as shown in my example.

What we can catch is if apply-templates/call-template invoces the current 
template *and* the current template is without parameters *and* the 
apply-templates/call-template doesn't have any with-param.

However I think it would be easier to just do

if (aPs->mTemplateRecursionLevel++ > 500) {
    // report error
    return;
}
// execute template
aPs->mTemplateRecursionLevel--;

in XSLTProcessor::processTemplate
(we could wrap the member in add/decrease functions)
I don't like the counting approach. Basically, because it's not an error.
If we had a way to ask the user, I'd be fine with that. But I don't see that 
on the horizon. Though I bet I'm not the only one who would like to keep the UI
responsive during transforms (which is the base to display a dialog, right?)
Can we inspect the parameters of this template instantiation and the previous?
And bail if the parameters didn't change?
If we don't do the counting approch we have to do some serious rearchitecturing 
to compleatly avoid crashes.

Even if we did check for same-template-same-parameters all the way up 
the "template recursion stack" we would still crash for something like:

<template name="foo">
  <param name="val" select="1"/>
  <call-template name="foo">
    <with-param name="val" select="$val + 1"/>
  </call-template>
</template>


I don't like the counting way either since it can make perfectly valid 
stylesheets fail, however i can't see any other not-insane-complicated way.


The insane-complicated way would be to make all the processXXX functions non-
recursive and manually build stacks with everything we need. I think that this 
is what the js-engine does to prevent crashes for things like
function a() { return b(); }
function b() { return a(); }
the insane-complicated way might be worth looking into when we start compiling 
the stylesheets...
*** Bug 163476 has been marked as a duplicate of this bug. ***
fwiw, IE stops at template-depth 16383 where xsl:for-each counts as template
(nice round number 'ey :-) )
Regarding #4.

You could:
- stop processing at 500th recursion level;
- render what you got so far;
- display dialog stating "Processing of XML document was not finished due to
very deep recursion. If you choose to reprocess with deeper recursion <red>YOU
COULD CRASH</red> your browser!", and two buttons: <<CANCEL>> (default) and
<Reprocess with deeper recursion>. 
- If user chooses to reprocess - "are you sure?" dialog could be helpfull.
Attached file stack overflow catch demo (obsolete) — 
Demo, how to catch stack overflow. 

Limitations:
1) does not take into account systems where stack grows in other direction than
Linux/x86;
2) does not take into account threads, but with litle help of thread creating
code that should be possible;
Comment on attachment 97151 [details]
stack overflow catch demo 

This looks completely unportable, and is pretty off-topic
Attachment #97151 - Attachment is obsolete: true
Attachment #97151 - Attachment mime type: application/octet-stream → text/plain
re, off-topic.

#163476 is duplicate of this bug. And comment #8 by Jonas Sickings reads 
<...>unfortunatly I don't know of any way to check for out-of-stackspace.<...>

re, portability.

This demo is not supposed to demonstrate how to learn how much of stack space we
are given. It is supposed to demonstrate check _if we are running out of it_.
And this could be minimized to check of relation of address of local variable to
some long number. Yes, relation (< or >) depends on how stack on that platform
grows. But this is the same platform dependency as is endianness or the way how
to put button in the window. Both latter problems are solved by making API which
 hides gorry details. I am sure, this could be done to this problem also.
*** Bug 180321 has been marked as a duplicate of this bug. ***
I thought about this bug in the post-compilation world. Even though we in theory
could run the transformation until we run out of memory and then bail I don't
think we really want to do that. First of all we would most likly end up
thrasing harddrive for quite a while before actually running out of memory.
Second eating up all the heapmemory will probably crash mozilla (no matter how
hard we try not to crash on OOM i doubt that we actually won't crash) as well as
unstablaize ever other app running on the clients computer since they will run
low on memory too.

So I think we need to put a cap on the level of recursiondepth even in the new
world. The number could probably be higher now that we're eating heap rather
then stack though. MS uses a cap of 16383 and i think we could have a number as
high up there, say 20000?
*** Bug 196447 has been marked as a duplicate of this bug. ***
The depth limit of 20k has landed.
I still think we should investigate something more friendly, and in cases of
just wrong selects, more responsive.
Any means to check for recursion beyond what we have now might end up with
a performance toll, though, so I vote for keeping this open and evaluate which
schema costs what once we have landed a few other optims. Like walker, at least.
(blame me, so reassigning)
Assignee: peterv → axel
Target Milestone: --- → Future
*** Bug 272565 has been marked as a duplicate of this bug. ***
could you just share the spidermonkey stack handling stuff?
that's not an issue any more since we no longer use up stack to do recursion,
instead we use up heap.
My use case is that I have a manager webapp (using java and tomcat) that monitors and/or filters XML files that are called into a client side XSL transformation using the document function. I was doing a simple response.sendRedirect which was sending a 302 code. I have worked around this by using a RequestDispatcher and forwarding the request. I would prefer to do the simple redirect as I now have to get the context of a child webapp and forward to it.
The last message was sent to the wrong bug. Don't know how I got here??
QA Contact: keith → xslt
Assignee: axel → nobody
Severity: normal → S3
You need to log in before you can comment on or make changes to this bug.

Attachment

General

Creator:
Created:
Updated:
Size: