[antlr-interest] [C runtime] Rewrite rules consuming *tons* of memory

[Jim Idle]

On Thu, 2008-08-28 at 15:36 -0600, Kurt Otte wrote:

> Jim,
> 
> Sorry to add another thing to the list, but I think I may have found
> another bug or perhaps there is a better way to construct the rewrite
> rule to avoid making lots of AST copies.  Do you know of a way to
> avoid rewrite rules doing lots of copies?
> 
> I have boiled my grammar down to show the problem using toy input.
> When the parser is fed a nested block such as the one below it
> consumes over 2GB of memory and crashes when it runs out of memory.


That looks like a bug - in fact, I think I remember saying to myself
"now I have put in factories for everything, I should not call dup on
the trees! However, I also remember doing that, so perhaps it is
something to do with your grammar) Sorry, but I still won't be able to
look in to this until the weekend :-(

Jim

> 
> 
> conditional
>   : 'if' '(' constant ')' ifblock=block
>      // This rewrite rule kills conditionals
>       -> ^(CONDITIONAL constant ^(IF $ifblock))
>   ;
> 
> 
> if (0)
> {
>   if (0)
>   {
>     if (0)
>     {
>       if (0)
>       {
>         if (0)
>         {
>           if (0)
>           {
>             if (0)
>             {
>               boo;
>             }
>           }
>         }
>       }
>     }
>   }
> }
> 
> When digging into it a bit with a profiler, it appears that the
> problem is in the rewrite rule.  The rewrite rule for 'conditional' is
> calling ADAPTOR->addChild()  and dupTree() recursively millions of
> times which in effect continuously allocates memory until it runs out.
>  Is there some way from a syntax point of view that I can construct a
> rewrite rule such that it minimizes the tree dups?
> 
> Attached is a zip file, with this toy example to reproduce the problem.
> 
> Thanks in advance for any thoughts or advice,
> 
> Kurt
-------------- next part --------------
An HTML attachment was scrubbed...
URL: http://www.antlr.org/pipermail/antlr-interest/attachments/20080828/8c04a371/attachment.html