Allowed memory size of 134217728 bytes exhausted

[npgeorgiou-zz]

Fatal error: Allowed memory size of 134217728 bytes exhausted (tried to allocate 4096 bytes) in /home/parser-generator/vendor/antlr/antlr4-php-runtime/src/Atn/ParserATNSimulator.php on line 2036

Hi, I am trying to use the PHP target, but it throws the above error, while parsing a file using a grammar. The same file and same grammar works fine on the Java target. If I remove the PHP process memory limit, it succeeds after a few seconds, but thats not right, as the file is very simple. Also, it is just a particular rule that creates this memory overuse, every other rule seems to be parsing fine.

I tried to make it so you can relatively easy reproduce the error.
The repo is https://github.com/npgeorgiou/say, and the PHP target experiment is in the parser-generator directory, which also has instructions on how to reproduce the error: https://github.com/npgeorgiou/say/tree/main/parser-generator

Let me know if I can do anything else to make it easier for you.

[npgeorgiou-zz]

Ok, I have more info. This memory bug happens when a subrule starts with itself. For example, here I have a section of my grammar:

expression:
|SAY expression # Say
|EXCLAMATION expression # Prefix
|expression EXCLAMATION # Postfix
;

say !foo will be parsed without issues
say foo! will run out of memory or, if I give it unlimited memory, will be very very slow. Of course this cannot work for big files that contain a few of these expresions.

[marcospassos]

Hi @npgeorgiou!

Thank you for reporting the issue. It seems like a recursion-related bug. I don't have time to track down the problem right now. If you have time to investigate this, PR’s are always welcome.

[npgeorgiou-zz]

I would love to, but I am not smart enough for that. What I can offer to any brave adventurer is these:

A grammar:

expression:
    IDENTIFIER                                    # Identifier
    |param_list? ARROW expression+                # Function_literal
    |EXCLAMATION expression                       # Prefix
    |expression EXCLAMATION                       # Postfix
    |SAY expression                               # Say
    |<assoc=right> expression ASSIGN expression   # Assignment
    |PO expression PC                             # P_expression
;

param_list: params+=function_param (COMMA params+=function_param)* COMMA?;
function_param: IDENTIFIER (ASSIGN defaultValue=expression)?;

A file:

is_leap << (year ->
    say foo!
    say foo!
    say foo!
    say foo!
    say foo!
    say foo!
    say foo!
    say foo!
    say foo!
    say foo!
    say foo!
)

Traveller, observe how the postfix **foo!**s are creating this memory error. The more of them, the slower it goes until it runs out of memory.

Also, observe how changing the postixes to prefixes (!foos) eliminates the bug.
Then, oberve how taking the **foo!**s out of the is_leap function body eliminates the bug as well.
Finally, oberve how, weirdly enough changing the

function_param: IDENTIFIER (ASSIGN defaultValue=expression)?;
to
function_param: IDENTIFIER;

improves the situation, although with enough **foo!**s it appears again.

May the gods of the crossroads and the in-betweens be with you.

[kaby76]

It seems I ran into a similar bug with the aql grammar with input for.aql. I'm trying to track it down, but also ran into #33, which makes the tracing impossible to use.

[kaby76]

In the driver, I turned on the new "tracing" features in v4.11.2 (current dev tip). I also edited the source to output a newline for the standard trace parser visitor.

PHP:

(before parse call)
$parser->setTrace(true);
Antlr\Antlr4\Runtime\Atn\ParserATNSimulator::$traceAtnSimulation = true;

CSharp:

(before parse call)
parser.Trace = true;
ParserATNSimulator.trace_atn_sim = true;

With tracing set, from the command line, the parse completes for PHP! Without trace set, the first call to AdaptivePredict() does not complete, and leads to out of memory exception. Note, regardless of trace set or not, in the XDebug/PHPStorm debugger, the run does not terminate! From the command line, with trace, there are ATN set differences between CSharp, which works fine, and PHP, which terminates because it's at the command line.

As for the diffs, it happens on the first "addDFAState".

PHP:

addDFAState new 0:[(297,1,[71 68 $]), (363,1,[225 126 74 68 $]), (226,1,[126 74 68 $]), (363,1,[290 121 68 $]), (291,1,[121 68 $]), (79,1,[68 $]), (297,2,[155 68 $]), (363,2,[225 126 158 68 $]), (226,2,[126 158 68 $]), (162,2,[68 $]), (169,2,[68 $]), (181,2,[68 $]), (193,2,[68 $]), (204,2,[68 $])]

CSharp:

addDFAState new 0:[(297,1,[71 68 $]), (363,1,[[225 126 74 68 $, 290 121 68 $]]), (226,1,[126 74 68 $]), (291,1,[121 68 $]), (79,1,[68 $]), (297,2,[155 68 $]), (363,2,[225 126 158 68 $]), (226,2,[126 158 68 $]), (162,2,[68 $]), (169,2,[68 $]), (181,2,[68 $]), (193,2,[68 $]), (204,2,[68 $])]

I don't know enough about the output to understand this, but it seems one is an aggregate because it contains two '[' in CSharp, but only one '[' for PHP. This sounds like the runtime is written with a misinterpretation of the data structure.

@parrt Is there a detailed description of this output?

I plan to add to the output the name of the type it is printing out (ATN, ATNSet, etc.). Again, my guess is that there is a data structure that isn't conforming to the expected type.

All of this point to some serious problems with PHP:

• The ATN sets differ when executed from the command line.
• PHP in the debugger vs command line differ in termination.

[kaby76]

Since I can't tell what a [ opens for a type (ATNConfig, ArrayPredicateConfig, ....), I decided to add identifiers to the "ToString()" output methods to tell me the object type it is trying to print out. I now am starting to see WTH is going on.

PHP:

addDFAState new 0:[atncs(ac297,1,[ac71 68 $]ac)ac, (ac363,1,[ac225 126 74 68 $]ac)ac, (ac226,1,[ac126 74 68 $]ac)ac, (ac363,1,[ac290 121 68 $]ac)ac, (ac291,1,[ac121 68 $]ac)ac, (ac79,1,[ac68 $]ac)ac, (ac297,2,[ac155 68 $]ac)ac, (ac363,2,[ac225 126 158 68 $]ac)ac, (ac226,2,[ac126 158 68 $]ac)ac, (ac162,2,[ac68 $]ac)ac, (ac169,2,[ac68 $]ac)ac, (ac181,2,[ac68 $]ac)ac, (ac193,2,[ac68 $]ac)ac, (ac204,2,[ac68 $]ac)ac]atncs

CSharp:

addDFAState new 0:[atncs(ac297,1,[ac71 68 $]ac)ac, (ac363,1,[ac[apc225 126 74 68 $, 290 121 68 $]apc]ac)ac, (ac226,1,[ac126 74 68 $]ac)ac, (ac291,1,[ac121 68 $]ac)ac, (ac79,1,[ac68 $]ac)ac, (ac297,2,[ac155 68 $]ac)ac, (ac363,2,[ac225 126 158 68 $]ac)ac, (ac226,2,[ac126 158 68 $]ac)ac, (ac162,2,[ac68 $]ac)ac, (ac169,2,[ac68 $]ac)ac, (ac181,2,[ac68 $]ac)ac, (ac193,2,[ac68 $]ac)ac, (ac204,2,[ac68 $]ac)ac]atncs

Notice the missing "[apc" tag. Whatever object PHP is printing, it is NOT an ArrayPredictionContext in PHP (but it is in CSharp) because I specifically modified the toString() method with tags. I will now debug toString() and see what the heck the object is.

@parrt Please, please, please add some kind of tagging system to note what type of object is being printed in the ATN trace output. I cannot tell what '[' opens.

[parrt]

hi @kaby76 thanks for the heads up. As usual an excellent analysis. The issue is that there are lots of different types that represent the same abstract concept of context. Not a bad idea, but the real issue here is that we don't have find enough granularity on the simulation trace. Is all of the output perfect up until that add the first DFA state? If so, then we need to add more output to the targets so that they identify why it is not generating the right stuff. Given the grammar, I can see that it is the left recursive stuff that's the problem. That will involve the precedence semantic predicates.

My head is stuck in something else at the moment so I don't have time to dig into this but maybe this gives you a bit of a clue? There's definitely a flaw in the ATN sim here. You might try reducing the offending rule to have one left recursive call and one non-recursive call. Also try using the recursive rule as the start symbol and then have a symbol above it. That could give a clue or at least a smaller test set.

[kaby76]

The first DFAState added between C# and PHP may be different.

C# in VC2022, for "D" at this line, first time hit, for dev branch, for.aql file input. The "configSet.configs" field doesn't even contain the same number of items. In C#, it's 13 elements.

PHP in PHPStorm, at this line, the configSet.configs field has 14 items. This is bad.

[kaby76]

CSharp and PHP code look completely different--missing "else" in PHP code. But, this is where the ArrayPredictionContext is create in CSharp, but it's never called in PHP.

So, there's more than one error likely.

[kaby76]

Found the problem. Or, in all likelihood, it may be only one of several.

In ATNConfigSet, there is a table called configLookup. It is a Dictionary<ATNConfig, ATNConfig> in C#, but a Set of ATNConfig in PHP. (Note, we've seen this difference in implementation before, between other targets.)

In C#, the code calls "GetOrAdd()", which is here. That table has a special comparer and hash function set for the class. The hash function that is executed is in class ConfigEqualityComparer, which has code that uses three fields of the ATNConfig.

Over in PHP, the code uses a generic Set implementation for $configLookup. That set is allocated here. Notice the hash function defined in this anonymous class here. That calls the standard hash function for ATNConfig. That computes the hash value using four fields--which is wrong!

I've verified that the call stack is indeed calling the wrong hash function for ATNConfig for this table in ParserATNSimulator. This is quite serious.

[parrt]

hahah. it's ALWAYS the hash function. @marcospassos looks like there might be an issue. We need a map from X->X not a set so we can reuse the same instance.

[kaby76]

I have an initial set of changes that seems to get past some of the parser tracing diffs.
diffs.txt

Essentially, as per note by @parrt I replaced the Set type for $configLookup in ATNConfigSet.php with Map as done with Java and CSharp. I also corrected the hash function/comparsion class for the map to be identical in CSharp. The Map interface needed some changes in the API for getOrAdd() and isEmpty()--which is just a hack to move past the first problem. It also contains some "print()'s" that end trace output with a new line ("echo()" does not write a newline!!). #33. People can wordsmith the "correct" design.

The trace is starting to now look better, getting past the diff with "addDFAState" in the output. But I still notice diffs. There are more problems.