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.

[kaby76]

The trace output for "for.aql" now diverges with the first "mergeArrays" line.

CSharp:

mergeArrays a=[385 232 126 74 68 $, 467 396 232 126 74 68 $],b=[311 232 126 74 68 $] -> [311 232 126 74 68 $, 385 232 126 74 68 $, 467 396 232 126 74 68 $]

PHP:

mergeArrays a=[385 232 126 74 68 $, 467 396 232 126 74 68 $],b=[311 232 126 74 68 $] -> M

"M". Really? The code seems wrong. That formatting code should be {M} not M. But, it should even be here. This line fails..

[kaby76]

I fixed the missing "else" problem (https://github.com/antlr/antlr4/blob/539ffaf63d312d38c98eb57099a4b6a735233fb8/runtime/CSharp/src/Atn/PredictionContext.cs#L212) and the string interpolation formatting problem in PHP, but that didn't fix the diff. There's something more wrong with merging of the prediction cache arrays.

[kaby76]

Found it. This code in PHP is wrong. In CSharp and java, these two arrays are allocated with nulls of the expected size, which is 3. After running through the code that assign to these arrays, this test in PHP fails because k=2 but the size of $mergeParents is 2, not 3. The length of the array should be 3 as in Java and CSharp. The solution is to assign the array with the correct number of nulls. Fixed this, but there are still more problems.

Sorry for the following flaming, but.... This is endless. People really need to go side by side with multiple debuggers/multiple targets, single step, and check their code. Granted, PHPStorm is terrible. Just setting up PHP for debugging required installing Xdebug with a manual .dll copy then modifying php.ini. I guess there's no global cache like in C#, or classpath as in Java, for PHP. Terrible. In PHPStorm, there doesn't seem to be a "Watch" pane as in VS2022, which automatically computes an expression when a breakpoint is reached. I have to manually evaluate "toString()" on all these data structures. Really slows everything down. Does anyone if there's a "Watch" pane in PHPStorm?

[marcospassos]

Hi @kaby76, great debugging work!

Most of these problems seem to be related to the PHP target being ported from JavaScript by the developer who started it. Therefore, these problems may exist there too.

Do you intend to open a PR with the fixes? I have an extensive test suite here that I want to test against. Also, I want to run some benchmarks to understand the impact on performance (positive or negative).

Granted, PHPStorm is terrible. Just setting up PHP for debugging required installing Xdebug with a manual .dll copy then modifying php.ini. I guess there's no global cache like in C#, or classpath as in Java, for PHP. Terrible. In PHPStorm, there doesn't seem to be a "Watch" pane as in VS2022, which automatically computes an expression when a breakpoint is reached. I have to manually evaluate "toString()" on all these data structures. Really slows everything down. Does anyone if there's a "Watch" pane in PHPStorm?

I use both IDEs and they have feature pairing. Here's how you add a watcher:

Screen.Recording.2022-12-19.at.11.31.00.mov

[kaby76]

Excellent! That watch works.

Not sure on the PR yet. Let's find all the bugs till the traces are exactly the same. I'll get the diffs on my mods, and post them here.

Looks like there's another problem here. This code is a Dictionary<PredictionContext, PredictionContext> over in C#. That means it calls the GetHashCode() and Equals() methods per PredictionContext class, which there's a whole bunch of them. This code in PHP doesn't call any of the hash() or equals() methods. I verified that nothing is called in PHP using the debugger. It must just do a pointer comparison for "contains()". The PHP doc for contains() doesn't say a thing about hash values or equality. Not good.

[marcospassos]

The PHP doc for contains() doesn't say a thing about hash values or equality. Not good.

The SplObjectStorage does not rely on value equality but on identity. So two objects are only considered the same if they are the same instance.

[kaby76]

Lot's of wrong. Someone got pointer comparisons vs equals() vs hash value compares all wrong. What a mess.

• Incorrect pointer compare, should be equals(). PHP CSharp
• (ditto). PHP CSharp
• Missing hash value check. Not here in PHP, but is here in CSharp
• Comparing arrays of ints, but if equal, returns FALSE WHEN IT SHOULD NOT RETURN. IF THE ARRAYS ARE DIFFERENT, RETURN FALSE. JFC.! PHP

[kaby76]

The SplObjectStorage does not rely on value equality but on identity. So two objects are only considered the same if they are the same instance.

It does not work because the comparison does not work. It does not compare ArrayPredictionContext correctly. But, you can debug this and prove to yourself this does not work: The ATN computation diverges between CSharp/Java and PHP.

[marcospassos]

I'm not saying that is right or wrong. I'm just contributing to your understanding of how it currently works. As soon as you open a PR or report all these differences I'll help fix the bugs.

[marcospassos]

Also, keep in mind that the evolution of the targets is not in sync. Targets have different numbers of contributors and development time. The CS target is much more mature and battle-tested than PHP.

Anyway, I'm glad you're finding theses bugs. I'd bet it's affecting the performance as well.

[kaby76]

OK, thanks @marcospassos .

OK, inching closer!! I'm up to line ~1208 in the ATN parser trace comparison. Lots more now working, and it's starting to get exciting, I guess.

Divergence here PHP:

computeReachSet [(505,1,[467 396 452 [448 471 467 396 232 126 74 68 $, 471 467 396 232 126 74 68 $]]), (457,1,[396 452 [448 471 467 396 232 126 74 68 $, 471 467 396 232 126 74 68 $]]), (458,1,[396 452 [448 471 467 396 232 126 74 68 $, 471 467 396 232 126 74 68 $]]), (503,1,[467 396 452 [448 471 467 396 232 126 74 68 $, 471 467 396 232 126 74 68 $]]), (468,1,[467 396 452 [448 471 467 396 232 126 74 68 $, 471 467 396 232 126 74 68 $]]), (474,1,[467 396 452 [448 471 467 396 232 126 74 68 $, 471 467 396 232 126 74 68 $]]), (462,1,[396 452 [448 471 467 396 232 126 74 68 $, 471 467 396 232 126 74 68 $]]), (369,1,[[385 452 [448 471 467 396 232 126 74 68 $, 471 467 396 232 126 74 68 $], 467 396 452 [448 471 467 396 232 126 74 68 $, 471 467 396 232 126 74 68 $]]]), (464,1,[396 452 [448 471 467 396 232 126 74 68 $, 471 467 396 232 126 74 68 $]]), (371,1,[467 396 452 [448 471 467 396 232 126 74 68 $, 471 467 396 232 126 74 68 $]]), (375,1,[452 [448 471 467 396 232 126 74 68 $, 471 467 396 232 126 74 68 $]]), (382,1,[452 [448 471 467 396 232 126 74 68 $, 471 467 396 232 126 74 68 $]]), (389,1,[452 [448 471 467 396 232 126 74 68 $, 471 467 396 232 126 74 68 $]]), (505,2,[467 396 452 [448 471 467 396 232 126 158 68 $, 471 467 396 232 126 158 68 $]]), (457,2,[396 452 [448 471 467 396 232 126 158 68 $, 471 467 396 232 126 158 68 $]]), (458,2,[396 452 [448 471 467 396 232 126 158 68 $, 471 467 396 232 126 158 68 $]]), (503,2,[467 396 452 [448 471 467 396 232 126 158 68 $, 471 467 396 232 126 158 68 $]]), (468,2,[467 396 452 [448 471 467 396 232 126 158 68 $, 471 467 396 232 126 158 68 $]]), (474,2,[467 396 452 [448 471 467 396 232 126 158 68 $, 471 467 396 232 126 158 68 $]]), (462,2,[396 452 [448 471 467 396 232 126 158 68 $, 471 467 396 232 126 158 68 $]]), (369,2,[[385 452 [448 471 467 396 232 126 158 68 $, 471 467 396 232 126 158 68 $], 467 396 452 [448 471 467 396 232 126 158 68 $, 471 467 396 232 126 158 68 $]]]), (464,2,[396 452 [448 471 467 396 232 126 158 68 $, 471 467 396 232 126 158 68 $]]), (371,2,[467 396 452 [448 471 467 396 232 126 158 68 $, 471 467 396 232 126 158 68 $]]), (375,2,[452 [448 471 467 396 232 126 158 68 $, 471 467 396 232 126 158 68 $]]), (382,2,[452 [448 471 467 396 232 126 158 68 $, 471 467 396 232 126 158 68 $]]), (389,2,[452 [448 471 467 396 232 126 158 68 $, 471 467 396 232 126 158 68 $]])] -> [(398,1,[[448 471 467 396 232 126 74 68 $, 471 467 396 232 126 74 68 $]]), (401,1,[[448 471 467 396 232 126 74 68 $, 471 467 396 232 126 74 68 $]]), (404,1,[[448 471 467 396 232 126 74 68 $, 471 467 396 232 126 74 68 $]]), (407,1,[[448 471 467 396 232 126 74 68 $, 471 467 396 232 126 74 68 $]]), (410,1,[[448 471 467 396 232 126 74 68 $, 471 467 396 232 126 74 68 $]]), (414,1,[[448 471 467 396 232 126 74 68 $, 471 467 396 232 126 74 68 $]]), (420,1,[[448 471 467 396 232 126 74 68 $, 471 467 396 232 126 74 68 $]]), (423,1,[[448 471 467 396 232 126 74 68 $, 471 467 396 232 126 74 68 $]]), (426,1,[[448 471 467 396 232 126 74 68 $, 471 467 396 232 126 74 68 $]]), (429,1,[[448 471 467 396 232 126 74 68 $, 471 467 396 232 126 74 68 $]]), (432,1,[[448 471 467 396 232 126 74 68 $, 471 467 396 232 126 74 68 $]]), (435,1,[[448 471 467 396 232 126 74 68 $, 471 467 396 232 126 74 68 $]]), (438,1,[[448 471 467 396 232 126 74 68 $, 471 467 396 232 126 74 68 $]]), (445,1,[[448 471 467 396 232 126 74 68 $, 471 467 396 232 126 74 68 $]]), (472,1,[467 396 232 126 74 68 $]), (472,1,[467 396 232 126 74 68 $]), (398,2,[[448 471 467 396 232 126 158 68 $, 471 467 396 232 126 158 68 $]]), (401,2,[[448 471 467 396 232 126 158 68 $, 471 467 396 232 126 158 68 $]]), (404,2,[[448 471 467 396 232 126 158 68 $, 471 467 396 232 126 158 68 $]]), (407,2,[[448 471 467 396 232 126 158 68 $, 471 467 396 232 126 158 68 $]]), (410,2,[[448 471 467 396 232 126 158 68 $, 471 467 396 232 126 158 68 $]]), (414,2,[[448 471 467 396 232 126 158 68 $, 471 467 396 232 126 158 68 $]]), (420,2,[[448 471 467 396 232 126 158 68 $, 471 467 396 232 126 158 68 $]]), (423,2,[[448 471 467 396 232 126 158 68 $, 471 467 396 232 126 158 68 $]]), (426,2,[[448 471 467 396 232 126 158 68 $, 471 467 396 232 126 158 68 $]]), (429,2,[[448 471 467 396 232 126 158 68 $, 471 467 396 232 126 158 68 $]]), (432,2,[[448 471 467 396 232 126 158 68 $, 471 467 396 232 126 158 68 $]]), (435,2,[[448 471 467 396 232 126 158 68 $, 471 467 396 232 126 158 68 $]]), (438,2,[[448 471 467 396 232 126 158 68 $, 471 467 396 232 126 158 68 $]]), (445,2,[[448 471 467 396 232 126 158 68 $, 471 467 396 232 126 158 68 $]]), (472,2,[467 396 232 126 158 68 $]), (472,2,[467 396 232 126 158 68 $])]

CSharp:

computeReachSet [(505,1,[467 396 452 [448 471 467 396 232 126 74 68 $, 471 467 396 232 126 74 68 $]]), (457,1,[396 452 [448 471 467 396 232 126 74 68 $, 471 467 396 232 126 74 68 $]]), (458,1,[396 452 [448 471 467 396 232 126 74 68 $, 471 467 396 232 126 74 68 $]]), (503,1,[467 396 452 [448 471 467 396 232 126 74 68 $, 471 467 396 232 126 74 68 $]]), (468,1,[467 396 452 [448 471 467 396 232 126 74 68 $, 471 467 396 232 126 74 68 $]]), (474,1,[467 396 452 [448 471 467 396 232 126 74 68 $, 471 467 396 232 126 74 68 $]]), (462,1,[396 452 [448 471 467 396 232 126 74 68 $, 471 467 396 232 126 74 68 $]]), (369,1,[[385 452 [448 471 467 396 232 126 74 68 $, 471 467 396 232 126 74 68 $], 467 396 452 [448 471 467 396 232 126 74 68 $, 471 467 396 232 126 74 68 $]]]), (464,1,[396 452 [448 471 467 396 232 126 74 68 $, 471 467 396 232 126 74 68 $]]), (371,1,[467 396 452 [448 471 467 396 232 126 74 68 $, 471 467 396 232 126 74 68 $]]), (375,1,[452 [448 471 467 396 232 126 74 68 $, 471 467 396 232 126 74 68 $]]), (382,1,[452 [448 471 467 396 232 126 74 68 $, 471 467 396 232 126 74 68 $]]), (389,1,[452 [448 471 467 396 232 126 74 68 $, 471 467 396 232 126 74 68 $]]), (505,2,[467 396 452 [448 471 467 396 232 126 158 68 $, 471 467 396 232 126 158 68 $]]), (457,2,[396 452 [448 471 467 396 232 126 158 68 $, 471 467 396 232 126 158 68 $]]), (458,2,[396 452 [448 471 467 396 232 126 158 68 $, 471 467 396 232 126 158 68 $]]), (503,2,[467 396 452 [448 471 467 396 232 126 158 68 $, 471 467 396 232 126 158 68 $]]), (468,2,[467 396 452 [448 471 467 396 232 126 158 68 $, 471 467 396 232 126 158 68 $]]), (474,2,[467 396 452 [448 471 467 396 232 126 158 68 $, 471 467 396 232 126 158 68 $]]), (462,2,[396 452 [448 471 467 396 232 126 158 68 $, 471 467 396 232 126 158 68 $]]), (369,2,[[385 452 [448 471 467 396 232 126 158 68 $, 471 467 396 232 126 158 68 $], 467 396 452 [448 471 467 396 232 126 158 68 $, 471 467 396 232 126 158 68 $]]]), (464,2,[396 452 [448 471 467 396 232 126 158 68 $, 471 467 396 232 126 158 68 $]]), (371,2,[467 396 452 [448 471 467 396 232 126 158 68 $, 471 467 396 232 126 158 68 $]]), (375,2,[452 [448 471 467 396 232 126 158 68 $, 471 467 396 232 126 158 68 $]]), (382,2,[452 [448 471 467 396 232 126 158 68 $, 471 467 396 232 126 158 68 $]]), (389,2,[452 [448 471 467 396 232 126 158 68 $, 471 467 396 232 126 158 68 $]])] -> [(398,1,[[448 471 467 396 232 126 74 68 $, 471 467 396 232 126 74 68 $]]), (401,1,[[448 471 467 396 232 126 74 68 $, 471 467 396 232 126 74 68 $]]), (404,1,[[448 471 467 396 232 126 74 68 $, 471 467 396 232 126 74 68 $]]), (407,1,[[448 471 467 396 232 126 74 68 $, 471 467 396 232 126 74 68 $]]), (410,1,[[448 471 467 396 232 126 74 68 $, 471 467 396 232 126 74 68 $]]), (414,1,[[448 471 467 396 232 126 74 68 $, 471 467 396 232 126 74 68 $]]), (420,1,[[448 471 467 396 232 126 74 68 $, 471 467 396 232 126 74 68 $]]), (423,1,[[448 471 467 396 232 126 74 68 $, 471 467 396 232 126 74 68 $]]), (426,1,[[448 471 467 396 232 126 74 68 $, 471 467 396 232 126 74 68 $]]), (429,1,[[448 471 467 396 232 126 74 68 $, 471 467 396 232 126 74 68 $]]), (432,1,[[448 471 467 396 232 126 74 68 $, 471 467 396 232 126 74 68 $]]), (435,1,[[448 471 467 396 232 126 74 68 $, 471 467 396 232 126 74 68 $]]), (438,1,[[448 471 467 396 232 126 74 68 $, 471 467 396 232 126 74 68 $]]), (445,1,[[448 471 467 396 232 126 74 68 $, 471 467 396 232 126 74 68 $]]), (472,1,[467 396 232 126 74 68 $]), (398,2,[[448 471 467 396 232 126 158 68 $, 471 467 396 232 126 158 68 $]]), (401,2,[[448 471 467 396 232 126 158 68 $, 471 467 396 232 126 158 68 $]]), (404,2,[[448 471 467 396 232 126 158 68 $, 471 467 396 232 126 158 68 $]]), (407,2,[[448 471 467 396 232 126 158 68 $, 471 467 396 232 126 158 68 $]]), (410,2,[[448 471 467 396 232 126 158 68 $, 471 467 396 232 126 158 68 $]]), (414,2,[[448 471 467 396 232 126 158 68 $, 471 467 396 232 126 158 68 $]]), (420,2,[[448 471 467 396 232 126 158 68 $, 471 467 396 232 126 158 68 $]]), (423,2,[[448 471 467 396 232 126 158 68 $, 471 467 396 232 126 158 68 $]]), (426,2,[[448 471 467 396 232 126 158 68 $, 471 467 396 232 126 158 68 $]]), (429,2,[[448 471 467 396 232 126 158 68 $, 471 467 396 232 126 158 68 $]]), (432,2,[[448 471 467 396 232 126 158 68 $, 471 467 396 232 126 158 68 $]]), (435,2,[[448 471 467 396 232 126 158 68 $, 471 467 396 232 126 158 68 $]]), (438,2,[[448 471 467 396 232 126 158 68 $, 471 467 396 232 126 158 68 $]]), (445,2,[[448 471 467 396 232 126 158 68 $, 471 467 396 232 126 158 68 $]]), (472,2,[467 396 232 126 158 68 $])]

Here's the current source code diffs.
diffs.txt

[kaby76]

The parse ATN trace debugging output has taken me far, but not far enough. However, the feature has been absolutely invaluable in getting this far. Thank you @parrt !!

I added more debugging output and have traced the computation to here. The after value of "configs" from the add() is not the same across targets. I suspect that the mergeCache structure isn't working. That's a little surprising because it does use Map and not Set.

[kaby76]

Ah, this test isn't right:

	if ($existing->equals($config)) { <<<<<<<
		$this->cachedHashCode = null;

Over in C#, the code is this:

	if (existing == config)
	{ // we added this new one
		cachedHashCode = -1;

In the C# code, the ==-operator is not overriden and the default just checks whether the references (aka pointers) are the same.

So, calling equals() is wrong. It should be '===' or '=='.

And, it looks like it now working! Trees look good.

Code changes:
diffs.txt

[marcospassos]

Can you open a PR with the fixes?

[kaby76]

I can certainly do that. I would like to spend some time and test it on everything grammar in grammars-v4. I want to really check out the parser ATN tracing an all.

[kaby76]

The trees are the same, but there's some unusual diffs in the parser ATN traces with some numbers.

addDFAState new 0:[(398,1,[$]), (401,1,[$]), (404,1,[$]), (407,1,[$]), (410,1,[$]), (414,1,[$]), (420,1,[$]), (423,1,[$]), (426,1,[$]), (429,1,[$]), (432,1,[$]), (435,1,[$]), (438,1,[$]), (445,1,[$]), (99,2,[$],up=1), (369,2,[311 305 103 $],up=1), (309,2,[305 103 $],up=1), (104,2,[$],up=1), (363,2,[$],up=3), (242,2,[$],up=2), (220,2,[[116 $, 283 $, 348 $]],up=2), (291,2,[$],up=3), (63,2,[$],up=3), (380,2,[$],up=2), (171,2,[$],up=1), (183,2,[$],up=1), (195,2,[$],up=1), (206,2,[$],up=1), (208,2,[$],up=1), (210,2,[$],up=1), (279,2,[235 $],up=1), (312,2,[125 $],up=2), (250,2,[$],up=2), (270,2,[$],up=3), (349,2,[149 $],up=3), (226,2,[$],up=3), (162,2,[$],up=3), (169,2,[$],up=3), (181,2,[$],up=3), (193,2,[$],up=3), (204,2,[$],up=3), (284,2,[[254 $, 258 $]],up=1), (255,2,[$],up=1), (314,2,[$],up=1), (319,2,[$],up=1), (327,2,[$],up=1), (358,2,[338 $],up=1), (351,2,[$],up=1), (336,2,[$],up=2), (398,2,[$],up=7), (401,2,[$],up=7), (404,2,[$],up=7), (407,2,[$],up=7), (410,2,[$],up=7), (414,2,[$],up=7), (420,2,[$],up=7), (423,2,[$],up=7), (426,2,[$],up=7), (429,2,[$],up=7), (432,2,[$],up=7), (435,2,[$],up=7), (438,2,[$],up=7), (445,2,[$],up=7), (387,2,[$],up=2), (416,2,[$],up=3), (443,2,[$],up=4), (472,2,[$],up=8), (489,2,[$],up=9), (486,2,[$],up=10)],dipsIntoOuterContext
execATN decision 63, DFA state 0:[(398,1,[$]), (401,1,[$]), (404,1,[$]), (407,1,[$]), (410,1,[$]), (414,1,[$]), (420,1,[$]), (423,1,[$]), (426,1,[$]), (429,1,[$]), (432,1,[$]), (435,1,[$]), (438,1,[$]), (445,1,[$]), (99,2,[$],up=1), (369,2,[311 305 103 $],up=1), (309,2,[305 103 $],up=1), (104,2,[$],up=1), (363,2,[$],up=3), (242,2,[$],up=2), (220,2,[[116 $, 283 $, 348 $]],up=2), (291,2,[$],up=3), (63,2,[$],up=3), (380,2,[$],up=2), (171,2,[$],up=1), (183,2,[$],up=1), (195,2,[$],up=1), (206,2,[$],up=1), (208,2,[$],up=1), (210,2,[$],up=1), (279,2,[235 $],up=1), (312,2,[125 $],up=2), (250,2,[$],up=2), (270,2,[$],up=3), (349,2,[149 $],up=3), (226,2,[$],up=3), (162,2,[$],up=3), (169,2,[$],up=3), (181,2,[$],up=3), (193,2,[$],up=3), (204,2,[$],up=3), (284,2,[[254 $, 258 $]],up=1), (255,2,[$],up=1), (314,2,[$],up=1), (319,2,[$],up=1), (327,2,[$],up=1), (358,2,[338 $],up=1), (351,2,[$],up=1), (336,2,[$],up=2), (398,2,[$],up=7), (401,2,[$],up=7), (404,2,[$],up=7), (407,2,[$],up=7), (410,2,[$],up=7), (414,2,[$],up=7), (420,2,[$],up=7), (423,2,[$],up=7), (426,2,[$],up=7), (429,2,[$],up=7), (432,2,[$],up=7), (435,2,[$],up=7), (438,2,[$],up=7), (445,2,[$],up=7), (387,2,[$],up=2), (416,2,[$],up=3), (443,2,[$],up=4), (472,2,[$],up=8), (489,2,[$],up=9), (486,2,[$],up=10)],dipsIntoOuterContext, LA(1)=='..'<64> line 1:12

vs

addDFAState new 0:[(398,1,[$]), (401,1,[$]), (404,1,[$]), (407,1,[$]), (410,1,[$]), (414,1,[$]), (420,1,[$]), (423,1,[$]), (426,1,[$]), (429,1,[$]), (432,1,[$]), (435,1,[$]), (438,1,[$]), (445,1,[$]), (99,2,[$],up=1073741825), (369,2,[311 305 103 $],up=1073741825), (309,2,[305 103 $],up=1073741825), (104,2,[$],up=1073741825), (363,2,[$],up=1073741827), (242,2,[$],up=1073741826), (220,2,[[116 $, 283 $, 348 $]],up=1073741826), (291,2,[$],up=1073741827), (63,2,[$],up=1073741827), (380,2,[$],up=1073741826), (171,2,[$],up=1073741825), (183,2,[$],up=1073741825), (195,2,[$],up=1073741825), (206,2,[$],up=1073741825), (208,2,[$],up=1073741825), (210,2,[$],up=1073741825), (279,2,[235 $],up=1073741825), (312,2,[125 $],up=1073741826), (250,2,[$],up=1073741826), (270,2,[$],up=1073741827), (349,2,[149 $],up=1073741827), (226,2,[$],up=1073741827), (162,2,[$],up=1073741827), (169,2,[$],up=1073741827), (181,2,[$],up=1073741827), (193,2,[$],up=1073741827), (204,2,[$],up=1073741827), (284,2,[[254 $, 258 $]],up=1073741825), (255,2,[$],up=1073741825), (314,2,[$],up=1073741825), (319,2,[$],up=1073741825), (327,2,[$],up=1073741825), (358,2,[338 $],up=1073741825), (351,2,[$],up=1073741825), (336,2,[$],up=1073741826), (398,2,[$],up=1073741831), (401,2,[$],up=1073741831), (404,2,[$],up=1073741831), (407,2,[$],up=1073741831), (410,2,[$],up=1073741831), (414,2,[$],up=1073741831), (420,2,[$],up=1073741831), (423,2,[$],up=1073741831), (426,2,[$],up=1073741831), (429,2,[$],up=1073741831), (432,2,[$],up=1073741831), (435,2,[$],up=1073741831), (438,2,[$],up=1073741831), (445,2,[$],up=1073741831), (387,2,[$],up=1073741826), (416,2,[$],up=1073741827), (443,2,[$],up=1073741828), (472,2,[$],up=1073741832), (489,2,[$],up=1073741833), (486,2,[$],up=1073741834)],dipsIntoOuterContext
execATN decision 63, DFA state 0:[(398,1,[$]), (401,1,[$]), (404,1,[$]), (407,1,[$]), (410,1,[$]), (414,1,[$]), (420,1,[$]), (423,1,[$]), (426,1,[$]), (429,1,[$]), (432,1,[$]), (435,1,[$]), (438,1,[$]), (445,1,[$]), (99,2,[$],up=1073741825), (369,2,[311 305 103 $],up=1073741825), (309,2,[305 103 $],up=1073741825), (104,2,[$],up=1073741825), (363,2,[$],up=1073741827), (242,2,[$],up=1073741826), (220,2,[[116 $, 283 $, 348 $]],up=1073741826), (291,2,[$],up=1073741827), (63,2,[$],up=1073741827), (380,2,[$],up=1073741826), (171,2,[$],up=1073741825), (183,2,[$],up=1073741825), (195,2,[$],up=1073741825), (206,2,[$],up=1073741825), (208,2,[$],up=1073741825), (210,2,[$],up=1073741825), (279,2,[235 $],up=1073741825), (312,2,[125 $],up=1073741826), (250,2,[$],up=1073741826), (270,2,[$],up=1073741827), (349,2,[149 $],up=1073741827), (226,2,[$],up=1073741827), (162,2,[$],up=1073741827), (169,2,[$],up=1073741827), (181,2,[$],up=1073741827), (193,2,[$],up=1073741827), (204,2,[$],up=1073741827), (284,2,[[254 $, 258 $]],up=1073741825), (255,2,[$],up=1073741825), (314,2,[$],up=1073741825), (319,2,[$],up=1073741825), (327,2,[$],up=1073741825), (358,2,[338 $],up=1073741825), (351,2,[$],up=1073741825), (336,2,[$],up=1073741826), (398,2,[$],up=1073741831), (401,2,[$],up=1073741831), (404,2,[$],up=1073741831), (407,2,[$],up=1073741831), (410,2,[$],up=1073741831), (414,2,[$],up=1073741831), (420,2,[$],up=1073741831), (423,2,[$],up=1073741831), (426,2,[$],up=1073741831), (429,2,[$],up=1073741831), (432,2,[$],up=1073741831), (435,2,[$],up=1073741831), (438,2,[$],up=1073741831), (445,2,[$],up=1073741831), (387,2,[$],up=1073741826), (416,2,[$],up=1073741827), (443,2,[$],up=1073741828), (472,2,[$],up=1073741832), (489,2,[$],up=1073741833), (486,2,[$],up=1073741834)],dipsIntoOuterContext, LA(1)=='..'<64> line 1:12

up=1073741825 vs up=1??

Looks like I need to fix equivalent()--build failed.

[kaby76]

1073741825 in hex = 0x40000001. Where do we see that in the code? here.

The problem is that in C#, "int" is 32 bits. https://learn.microsoft.com/en-us/dotnet/csharp/language-reference/builtin-types/integral-numeric-types#characteristics-of-the-integral-types

In PHP, it's 64-bits (or depends on your OS). https://www.w3schools.com/php/php_numbers.asp#:~:text=PHP%20Integers&text=An%20integer%20data%20type%20is,the%20limit%20of%20an%20integer.

The constant is wrong, but changing that doesn't fix the diffs in the numbers seen in the trace. Something more here....

[kaby76]

There is actually an error in the code w.r.t. the use of reachesIntoOuterContext and the associated accessor that uses a bitmap SUPPRESS_PRECEDENCE_FILTER.

Over in Java, there are several locations that very carefully choose the accessor or the variable, which over in PHP are incorrect.

• Java ATNConfigSet.add() Must be accessor with bitmap.
• Java ParserATNSimulator.getAltThatFinishedDecisionEntryRule() Must be accessor with bitmap.
• ATNConfig.toString().

In PHP, this reference wrong:

• PHP ATNConfigSet.add() This should be through accessor function that uses the bitmap. bit instead uses the raw field, without any bitmap adjustments.

It turns out that several other targets get it wrong, including CSharp.

[marcospassos]

It's becoming one of the greatest contributions ever. Looking forward to the conclusion!

[kaby76]

Thank you kindly.

The ATN parser trace is exactly the same now. I had to change some code over in CSharp--bug. Need to fix the build problems and check the fixes against a few grammars in grammars-v4 with parser ATN tracing.

[kaby76]

I'm testing the target on one of the worse grammars in grammars-v4: tsql. Poorly written, very ambiguous. The parser works fine for most tests, but fails for built_in_functions_metadata.sql with out of memory.

I have checked the ATN trace for the abb grammar--works fine, and, of course the aql grammar.

[parrt]

The parse ATN trace debugging output has taken me far, but not far enough. However, the feature has been absolutely invaluable in getting this far. Thank you @parrt !!

Thanks @kaby76 sorry for the delay in my jumping in here. Really glad that the trace is now useful. Sounds like what we need to do is update the tracing so that we catch many more of these differences in an obvious way. We should make a separate PR to update the tracing in all of the target to be more fine grained. I'm happy to do that, but I'm not sure what extra instrumentation we need. Happy to work together on that. I am able to work on open source now until after New Year's, although in principal I need to let my tendinitis cool off with less typing in mousing!

[kaby76]

@parrt This tracing is absolutely fantastic! Finding all sorts of things--sorry to wreck people's holidays!! I have some bugs/issues to create. Currently, I'm only diffing C# and PHP traces, but might now to need to add in Java in order to know which target is correct. Diffing 3GB files of the html grammar on abc.com.html.

[parrt]

Woot! Seems like you had to work much harder because everything looked OK until you got to adding a DFA state. If we had finer grained tracing it might have shown a difference earlier which would be easier to track down.

It would definitely be nice to have a Java vs target X comparison that would run for all of the grammars-v4 with all inputs. That would be a fun way to use a few hundred hours of CPU time! ;)

[marcospassos]

What would bring a lot of confidence to all target maintainers is a CI that performs cross-target checking. We could generate relevant tracing files and check against every PR, so diffing from it would cause the build to fail.

[parrt]

Yes could be pretty expensive however. I guess we could add some basic tests as part of the github actions we do now

[marcospassos]

@kaby76, any guess on the cause of the memory overflow?

[marcospassos]

Yes could be pretty expensive however. I guess we could add some basic tests as part of the github actions we do now

I don't think so. We can generate the tracing only once and then just run the parsing and check on every for a given target.

[parrt]

oh that's a good point. Generate for some sample tests from the java "truth" and then anytime somebody changes Target we compare to that?

[parrt]

we could simply add a new flag to the runtime test mechanism that says to compare the tracing output.

[marcospassos]

oh that's a good point. Generate for some sample tests from the java "truth" and then anytime somebody changes Target we compare to that?

Exactly. It would help to ensure all targets work as expected. We can even add these trace files to the grammar repository as a ground truth.

[marcospassos]

Providing a built-in target-independent check would be amazing. However, running it on the PHP repository would allow for faster feedback and error prevention.

[parrt]

Sounds good. Let me think about this more. I'd like to get more find grand trace information out first and then we can figure out what sort of testing to do. There are about 350 runtime tests. I wonder if it makes sense to simply always compare the output of the trace with the known good output. It makes some sense and they trace output would not be that big.

[parrt]

oh right. can't capture stdout unless we run in single-threaded mode...all tracing sends to stdout.

[kaby76]

I added some code to the trgen template driver generator with a switch for ATN tracing. But it's just for C# and PHP right now. Unfortunately, many of the v4 grammars just aren't PHP compatible because the grammars contain common names between lexer and parser rules (e.g., "COMMENT"/"comment"; see this and this). I plan to add the switch to the other templates today (Cpp, Dart, Go, Java, JavaScript, Python3). Eventually, I'll try to test all v4 grammars with ATN trace diffing. It can't be done in the CI builds because it'll take many hours of CPU time, but at least I can run it once in a while.

Dealing with large trace files can become quite cumbersome. MSYS diff craps out on 1.5GB files, giving bad results. GNU Emacs definitely helps because it can load large files, and offers a "compare-windows" command. Ironically, for the html grammar with abc.com.html, the traces differ pretty much in the beginning of the 1.5GB files, at line 733. (Note, PHP doesn't stop parsing, so I have to kill the process when it reaches 1.5GB.)

A problem with the trace in PHP is that I added a print("\n") to the code. That's not an OS-dependent "newline". So, I have to use dos2unix to standardize the files for comparison. I'm not sure what the call is in PHP to just write a newline customary for the OS.

If a full run of the parser isn't needed to find ATN trace differences, then I might use trwdog, head, tail, split to create a window on the output that I can compare. I could then work in chunks of ~10MB.

Ideally, it would be best if there was some way of stepping through two parsers side-by-size, "one rule at a time" or some standardized step increment, so I can compare two targets side-by-side and not have to run to completion the parse of each target in order to find the first ATN trace difference. I think it's possible with a program that spawns a command-line debugger for each target.

I really don't know the cause of the memory-overflow condition in PHP. I had to start somewhere and decided to just start with ATN trace diffing. My philosophy is to do white-box testing of the internals. I don't think it's enough to test for identical parse trees between targets.

[kaby76]

Looks like ATN tracing is not available for Cpp and Dart.

[marcospassos]

A problem with the trace in PHP is that I added a print("\n") to the code. That's not an OS-dependent "newline". So, I have to use dos2unix to standardize the files for comparison. I'm not sure what the call is in PHP to just write a newline customary for the OS.

@kaby76, just use echo \PHP_EOL;

[parrt]

Should be. maybe a weird name for the var? I remember C++ tracing for sure.

…

On Fri, Dec 23, 2022 at 6:21 AM Ken Domino ***@***.***> wrote: Looks like ATN tracing is not available for Cpp and Dart. — Reply to this email directly, view it on GitHub <#12 (comment)>, or unsubscribe <https://github.com/notifications/unsubscribe-auth/AABLUWJD6WVTCHPNKQCM7CLWOWYNRANCNFSM43ELAOPA> . You are receiving this because you were mentioned.Message ID: ***@***.***>

-- Dictation in use. Please excuse homophones, malapropisms, and nonsense.

[parrt]

Oh yeah, maybe not dart, but definitely C++. The issue with C++ is that it's a macro TRACE_ATN_SIM that must be set during the runtime build. Here is the argument to the build file. It's annoying that it is not changeable at runtime but we have no choice since it's set up as a macro and C++ people are obsessed with speed.

IF(TRACE_ATN)
    ADD_DEFINITIONS(-DTRACE_ATN_SIM=1)
ENDIF(TRACE_ATN)

I think this means that I manually run a build with cmake TRACE_ATN=ON or whatever then run traceatn.sh.