[antlr-interest] Problem rewriting AST in a tree parser (OutOfMemoryError)

[Arnaud de Bossoreille de Ribou]

Hi,

I was trying to write a quite simple AST rewriter using a tree parser 
and I faced with an unexpected issue.

First of all, "The Definitive ANTLR reference" claims that activating 
the "rewrite" option works only for the "template" output. I suppose 
that this point has changed since 3.1 (I am using output=AST). The fact 
that it is handled specifically in the generated code tells me that I am 
right, if I am wrong, I will just go to hell :-).

So my goal is to insert a tree node provided a condition is fulfilled. 
Somewhere in my tree parser I have:

-----
rule: s=sub
     -> { condition }? ^(NODE $s)
     -> $s
;
-----

Unfortunately, when I came to the test phase, I faced with an 
OutOfMemoryError. This seems due to the java generated code which looks 
like this (I use the "java" target):

-----
if ( contition ) {
     {
         CommonTree root_1 = (CommonTree)adaptor.nil();
         root_1 = 
(CommonTree)adaptor.becomeRoot((CommonTree)adaptor.create(NODE, "NODE"), 
root_1);
         adaptor.addChild(root_1, stream_s.nextTree());
         adaptor.addChild(root_0, root_1);
     }
}
else
{
     adaptor.addChild(root_0, stream_q.nextTree());
}

retval.tree = (CommonTree)adaptor.rulePostProcessing(root_0);
input.replaceChildren(adaptor.getParent(retval.start),
         adaptor.getChildIndex(retval.start),
         adaptor.getChildIndex(_last),
         retval.tree);
-----

The problem is that the parent of retval.start has changed because of 
one of the previous calls to addChild(). So the replaceChildren() call 
does something which leads to OutOfMemoryError (most probably a 
reference cycle or something like that).

I wonder whether we have to backup the parent and indices at the 
beginning of the rule or to duplicate the sub-tree before adding it as a 
child of the inserted node. In my case it has not been duplicated or the 
error would not have raised.

ANTLR 3.2 is impacted so as 3.1.3 is.

I attached my attempt to write a junit test to this e-mail. It probably 
can reach a smaller size but this is a good start since the OOME raises. 
The "rewrite=true" option is mandatory.

Could someone tell me whether I am doing something wrong or that my 
analysis is not that bad?

Thank you for your time.

PS: I do not known whether the other targets are impacted by such an issue.

Regards,

-- 
Arnaud
-------------- next part --------------
A non-text attachment was scrubbed...
Name: TestTreeGrammarRewriteAST2.java
Type: text/x-java
Size: 3302 bytes
Desc: not available
Url : http://www.antlr.org/pipermail/antlr-interest/attachments/20091208/73436de5/attachment.bin