fix: Fixes for https://github.com/antlr/antlr4/issues/3718 #3818

jimidle · 2022-08-13T10:16:33Z

fix: #3718 Implement generic collections and fiux LA(*) optimizer

o Implements collections using generics to solve has conflicts in previous implementation of
DFAState collections and alt conflict resolution
o Change alt and config to use correct hash and equals as per Java
o Fix LA()*) runtime optimization routine
o A few tidy ups on comments etc

NB: There are now extra hash() and equals() routines that I had to leave there unless I wanted to go through
all the code and rationalize and refactor. Not worth it if we are going to rewrite. The generic collections work for this
purpose but the make up of the currents structs etc, forces a few hacks that won't be needed with better structure.

Sending this PR without tests for the collections as:

o they can't be worse than what is there, that doesn't work
o they are tested with real grammars anyway
o it is Saturday and time to get ready for EPL to start in England - come on Leeds

@kaby76

o Implement collections with generics to solve hash collisions o Fix type casting in LL start parser simulation optimization o General minor tidy ups Acknowledgements to @kaby76 for help with tracing errors Signed-off-by: Jim.Idle <jimi@gatherstars.com>

jimidle · 2022-08-13T10:23:42Z

I will have to remember the DCO. I think some of the builds are failing because the tests are failing. Somebody changed a test somewhere it seems.

kaby76 · 2022-08-13T15:23:40Z

Please check that this fixes the original SimpleBoolean.g4, input p15.txt performance. I don't see the perf improvement. Looks like it should.

parrt · 2022-08-13T18:07:36Z

runtime/Java/src/org/antlr/v4/runtime/atn/ATNConfigSet.java

-
-	/** Track the elements as they are added to the set; supports get(i) */
-	public final ArrayList<ATNConfig> configs = new ArrayList<ATNConfig>(7);
+	public AbstractConfigHashSet configLo


Looks like a mistaken chop chop here :)

parrt · 2022-08-13T18:17:58Z

I get 5 failures running the tests:

critter:~/antlr/code/antlr4/runtime-testsuite $ mvn -Dtest=go.** test
...

parrt · 2022-08-13T18:24:12Z

@jimidle I changed CI for hosted github actions to 1.19 Go.

jimidle · 2022-08-14T01:27:29Z

Sorry for the Java file. It’s the kind of thing that happens in a mono repo. Obviously a keyboard slip in IntelliJ while single stepping there and in goland at the same time. I normally don’t submit so many code changes at once.

…

On Sun, Aug 14, 2022 at 02:13 Terence Parr ***@***.***> wrote: I pull in, fix the java file booboo, but get Go compile errors: critter:~/antlr/code/antlr4/runtime-testsuite $ mvn -Dtest=go.** test ... # antlr /var/folders/w1/_nr4stn13lq0rvjdkwh7q8cc0000gn/T/ANTLR-runtime-testsuite-cache/Go/src/antlr/atn_config.go:23:27: syntax error: unexpected [, expecting comma or ) /var/folders/w1/_nr4stn13lq0rvjdkwh7q8cc0000gn/T/ANTLR-runtime-testsuite-cache/Go/src/antlr/atn_config.go:140:33: syntax error: unexpected [, expecting ) /var/folders/w1/_nr4stn13lq0rvjdkwh7q8cc0000gn/T/ANTLR-runtime-testsuite-cache/Go/src/antlr/atn_config.go:145:46: syntax error: unexpected [, expecting comma or ) /var/folders/w1/_nr4stn13lq0rvjdkwh7q8cc0000gn/T/ANTLR-runtime-testsuite-cache/Go/src/antlr/atn_config.go:152:2: syntax error: non-declaration statement outside function body /var/folders/w1/_nr4stn13lq0rvjdkwh7q8cc0000gn/T/ANTLR-runtime-testsuite-cache/Go/src/antlr/atn_config.go:158:2: syntax error: non-declaration statement outside function body /var/folders/w1/_nr4stn13lq0rvjdkwh7q8cc0000gn/T/ANTLR-runtime-testsuite-cache/Go/src/antlr/atn_config.go:171:2: syntax error: non-declaration statement outside function body /var/folders/w1/_nr4stn13lq0rvjdkwh7q8cc0000gn/T/ANTLR-runtime-testsuite-cache/Go/src/antlr/atn_config.go:270:37: syntax error: unexpected [, expecting ) /var/folders/w1/_nr4stn13lq0rvjdkwh7q8cc0000gn/T/ANTLR-runtime-testsuite-cache/Go/src/antlr/atn_config.go:273:51: syntax error: unexpected [, expecting comma or ) /var/folders/w1/_nr4stn13lq0rvjdkwh7q8cc0000gn/T/ANTLR-runtime-testsuite-cache/Go/src/antlr/atn_config.go:276:2: syntax error: non-declaration statement outside function body /var/folders/w1/_nr4stn13lq0rvjdkwh7q8cc0000gn/T/ANTLR-runtime-testsuite-cache/Go/src/antlr/atn_config.go:286:2: syntax error: non-declaration statement outside function body /var/folders/w1/_nr4stn13lq0rvjdkwh7q8cc0000gn/T/ANTLR-runtime-testsuite-cache/Go/src/antlr/atn_config.go:286:2: too many errors — Reply to this email directly, view it on GitHub <#3818 (comment)>, or unsubscribe <https://github.com/notifications/unsubscribe-auth/AAJ7TMDIHZDLN3PUDXOEJ3TVY7QSXANCNFSM56N5CZTQ> . You are receiving this because you authored the thread.Message ID: ***@***.***>

parrt · 2022-08-14T01:28:59Z

No prob. I do crazy stuff like that all the time. Can you check on the go test failures?

jimidle · 2022-08-14T01:30:49Z

Will do. Hopefully it’s the tests that are incorrect

…

On Sun, Aug 14, 2022 at 09:29 Terence Parr ***@***.***> wrote: No prob. I do crazy stuff like that all the time. Can you check on the go test failures? — Reply to this email directly, view it on GitHub <#3818 (comment)>, or unsubscribe <https://github.com/notifications/unsubscribe-auth/AAJ7TMBLYY5VXB2MLCHWTMDVZBDWNANCNFSM56N5CZTQ> . You are receiving this because you were mentioned.Message ID: ***@***.***>

parrt · 2022-08-14T01:32:22Z

Possibly but we have a general test mechanism that gens tests across targets. You can check the antlr doc dir and see testing file

parrt · 2022-08-14T01:33:25Z

The checks dialog here should also give the results though I just tuned off all but github hosted CI and circleci

Signed-off-by: Jim.Idle <jimi@gatherstars.com>

With older versions of go, there was no good way to tell the compiler to use your local development copy of a particular package instead of the one installed in GOPATH/src/... However, we are now using modules, which allows us to tell the compiler that instead of a module downloaded to GOPATH/pkg, to use a local copy on disk. Hence this change removes the need to copy the whole of the go installation to a tempoorary location, then put the antlr go runtime in to the go installation as if it was part of the compiler. Hence the execution time for the go tests is now faster than before. This works because when the generated code is placed in the temporary location, we create a go.mod file for it, tell the module to replace the online module for the go runtime with the local copy on disk, then ro a go mod tidy to add the dependencies from the code (which avoids network access, so it is instant), which adds the ANTLR dependency itself (which is then replaced at compile time). All go runtime tests now pass. Signed-off-by: Jim.Idle <jimi@gatherstars.com>

jimidle · 2022-08-15T07:20:28Z

Please check that this fixes the original SimpleBoolean.g4, input p15.txt performance. I don't see the perf improvement. Looks like it should.

It does, but you need to make sure you are actually compiling with this code. You cannot do a go get with my fork because of the way go get works - it is defect in using fork with go code. You have to clone my repo, then either use GOWORK, which is my preference, to tell the compiler to use that code for your build, or use a replace in the go mod for the test code. Or just wait for Ter to merge the PR and use:

go get -u github.com/antlr/antlr4/runtime/Go/antlr@dev

But let me double check - I am using the project that was supplied in github at the top of the original report. I will see if what you are pointing to is actually the same thing.

OK - I double checked - the grammar is exactly the same and the input I am using actually has a couple of extra 1 EQ 2 OR statements.

jimidle · 2022-08-15T07:22:31Z

Hmmm - seems to be a syntax error in the push - not sure how that happened... ah, it didn't, the go compiler being used for that test is too old. Easy fix I presume Ter.

jimidle · 2022-08-15T07:25:05Z

Ah - the ci go testing the runtime is using a go compiler that is too old. That test also needs updating to use go 1.18 or go 1.19 (preferable).

jimidle · 2022-08-15T07:34:13Z

@jimidle I changed CI for hosted github actions to 1.19 Go.

Also needs changing for the ci test of the go runtime using the test suite. That is failing because the compiler is too old

kaby76 · 2022-08-15T10:00:42Z

This isn't fixing the Go performance problem for me.

I am cleaning out my ~/go cache, wherever it may be on Ubuntu 20.04.4 LTS and Windows 10.
I am using "go version" 1.17.2 on both Ubuntu and Windows
I am using "go get github.com/antlr/antlr4/runtime/Go/antlr@dev".
I am using the executable on both Linux and Windows.
I am doing a fresh "git clone https://github.com/kaby76/issue-3718; cd issue-3718/original-grammar/".
Here is my complete work, all the sources and makefiles that I used to build and test the code, and the output. https://github.com/kaby76/issue-3718/tree/c3ba6e60e18f0bbba19b5113fd5f07b71e9cb869/original-grammar
Here's the output from "test.sh 2>&1 1> out-win.txt" on Windows. https://github.com/kaby76/issue-3718/blob/c3ba6e60e18f0bbba19b5113fd5f07b71e9cb869/original-grammar/out-win.txt
Here's the output from "test.sh 2>&1 1> out-linux.txt" on WSL Ubuntu https://github.com/kaby76/issue-3718/blob/c3ba6e60e18f0bbba19b5113fd5f07b71e9cb869/original-grammar/out-linux.txt
The runtimes (Windows) are: CSharp 0.05s, Java 0.017s, Go 38s . Similar result for Ubuntu.
The old 4.10.1 Go runtime ran in Windows 38s, WSL2 Ubuntu 36s (only one run). I don't see the difference in runtime. The Go target still takes orders of magnitude longer than either Java or CSharp targets, runs in the same amount of time as 4.10.1.

Someone else, please verify.

jimidle · 2022-08-15T10:49:38Z

Ken That isn’t the correct runtime. Wait for Ter to merge the PR

…

On Mon, Aug 15, 2022 at 18:00 Ken Domino ***@***.***> wrote: This isn't fixing the Go performance problem for me. - I am cleaning out my ~/go cache, wherever it may be on Ubuntu 20.04.4 LTS and Windows 10. - I am using go 1.17.2 on both Ubuntu and Windows - I am using "go get ***@***.***". - I am using the executable on both Linux and Windows. - I am doing a fresh "git clone https://github.com/kaby76/issue-3718; cd issue-3718/original-grammar/". - Here is my complete work, all the sources and makefiles that I used to build and test the code, and the output. https://github.com/kaby76/issue-3718/tree/c3ba6e60e18f0bbba19b5113fd5f07b71e9cb869/original-grammar - Here's the output from "test.sh 2>&1 1> out-win.txt" on Windows. https://github.com/kaby76/issue-3718/blob/c3ba6e60e18f0bbba19b5113fd5f07b71e9cb869/original-grammar/out-win.txt - Here's the output from "test.sh 2>&1 1> out-linux.txt" on WSL Ubuntu https://github.com/kaby76/issue-3718/blob/c3ba6e60e18f0bbba19b5113fd5f07b71e9cb869/original-grammar/out-linux.txt - The runtimes (Windows) are: CSharp 0.05s <https://github.com/kaby76/issue-3718/blob/c3ba6e60e18f0bbba19b5113fd5f07b71e9cb869/original-grammar/out-win.txt#L39>, Java 0.017s <https://github.com/kaby76/issue-3718/blob/c3ba6e60e18f0bbba19b5113fd5f07b71e9cb869/original-grammar/out-win.txt#L52>, Go 38s <https://github.com/kaby76/issue-3718/blob/c3ba6e60e18f0bbba19b5113fd5f07b71e9cb869/original-grammar/out-win.txt#L103> . Similar result for Ubuntu. Someone else, please verify. — Reply to this email directly, view it on GitHub <#3818 (comment)>, or unsubscribe <https://github.com/notifications/unsubscribe-auth/AAJ7TMAT7OL4T5YE2PYPVFDVZIINJANCNFSM56N5CZTQ> . You are receiving this because you were mentioned.Message ID: ***@***.***>

kaby76 · 2022-08-15T13:55:08Z

You're right. It does fix the perf problem. I upgraded to 1.18.3, "learned" about workspaces, and tried it out. I modeled the changes after this, and it works great.

(I do not understand yet how a go build finds all the workspace code because go.work can in theory have "use" to Go modules anywhere on the entire file system. But, those modules do not have pointers back to the go.work file to pick up all the modified modules in the workspace. If it's relative, then what happens if I copy a stray go.work into "~"?)

parrt · 2022-08-15T16:46:42Z

Also needs changing for the ci test of the go runtime using the test suite. That is failing because the compiler is too old

I'm not sure where are you mean by ci as the dev branch shows for hosted CI:

    - name: Setup Go 1.19
      if: matrix.target == 'go'
      uses: actions/setup-go@v3
      with:
        go-version: '^1.19'

Do you mean something in our test rig (Java) code for antlr itself refers to a Go version?

Oh, sorry. CIRCLE ci. Let me check

parrt · 2022-08-15T18:40:08Z

I think master works but dev doesn't for go on circlei, though we might be able to dump circleci now that github hosted CI works.

Thanks for all the hard work, @jimidle !!!

jimidle · 2022-08-16T02:05:59Z

I think master works but dev doesn't for go on circlei, though we might be able to dump circleci now that github hosted CI works.

Thanks for all the hard work, @jimidle !!!

Yes - sorry I was not sure which build test were running where. You are correct that it was the circleci that was trying to use the old compiler and hence that trigger failed.

I will delete this branch once I verify that the dev branch is in sync

jimidle · 2022-10-11T07:27:50Z

Ah right. Sorry - just getting back in to it, and a lot has been built and changed - I will get there

…

On Aug 14, 2022 at 9:32:32 AM, Terence Parr ***@***.***> wrote: Possibly but we have a general test mechanism that gens tests across targets. You can check the antlr doc dir and see testing file — Reply to this email directly, view it on GitHub <#3818 (comment)>, or unsubscribe <https://github.com/notifications/unsubscribe-auth/AAJ7TMDHG26JITKLIDOHIGTVZBEDBANCNFSM56N5CZTQ> . You are receiving this because you were mentioned.Message ID: ***@***.***>

jimidle · 2022-10-11T07:48:26Z

You can tell it isn’t the correct runtime because my changes require at least go 1.18. See my comment in the PR on how you can use my version if you want to try before Ter merges the PR. By getting @dev, you are pulling in the old runtime. Upgrade your go to go 1.19 as you will need it for the new runtime.

…

On Mon, Aug 15, 2022 at 18:00 Ken Domino ***@***.***> wrote: This isn't fixing the Go performance problem for me. - I am cleaning out my ~/go cache, wherever it may be on Ubuntu 20.04.4 LTS and Windows 10. - I am using go 1.17.2 on both Ubuntu and Windows - I am using "go get ***@***.***". - I am using the executable on both Linux and Windows. - I am doing a fresh "git clone https://github.com/kaby76/issue-3718; cd issue-3718/original-grammar/". - Here is my complete work, all the sources and makefiles that I used to build and test the code, and the output. https://github.com/kaby76/issue-3718/tree/c3ba6e60e18f0bbba19b5113fd5f07b71e9cb869/original-grammar - Here's the output from "test.sh 2>&1 1> out-win.txt" on Windows. https://github.com/kaby76/issue-3718/blob/c3ba6e60e18f0bbba19b5113fd5f07b71e9cb869/original-grammar/out-win.txt - Here's the output from "test.sh 2>&1 1> out-linux.txt" on WSL Ubuntu https://github.com/kaby76/issue-3718/blob/c3ba6e60e18f0bbba19b5113fd5f07b71e9cb869/original-grammar/out-linux.txt - The runtimes (Windows) are: CSharp 0.05s <https://github.com/kaby76/issue-3718/blob/c3ba6e60e18f0bbba19b5113fd5f07b71e9cb869/original-grammar/out-win.txt#L39>, Java 0.017s <https://github.com/kaby76/issue-3718/blob/c3ba6e60e18f0bbba19b5113fd5f07b71e9cb869/original-grammar/out-win.txt#L52>, Go 38s <https://github.com/kaby76/issue-3718/blob/c3ba6e60e18f0bbba19b5113fd5f07b71e9cb869/original-grammar/out-win.txt#L103> . Similar result for Ubuntu. Someone else, please verify. — Reply to this email directly, view it on GitHub <#3818 (comment)>, or unsubscribe <https://github.com/notifications/unsubscribe-auth/AAJ7TMAT7OL4T5YE2PYPVFDVZIINJANCNFSM56N5CZTQ> . You are receiving this because you were mentioned.Message ID: ***@***.***>

parrt · 2022-10-13T16:59:00Z

This one has been merged... Maybe you meant to comment on a different PR?

fix: Fixes for #3718

833b198

o Implement collections with generics to solve hash collisions o Fix type casting in LL start parser simulation optimization o General minor tidy ups Acknowledgements to @kaby76 for help with tracing errors Signed-off-by: Jim.Idle <jimi@gatherstars.com>

parrt added type:bug target:go type:cleanup labels Aug 13, 2022

parrt added this to the 4.10.2 milestone Aug 13, 2022

parrt reviewed Aug 13, 2022

View reviewed changes

Jim.Idle added 3 commits August 14, 2022 10:19

fix: #3718 Revert accidental keyboard error in Java target

6e611a7

Signed-off-by: Jim.Idle <jimi@gatherstars.com>

fix: #3718 Correct DFAState index in Lexer ATN Simulator

f19dc0e

Signed-off-by: Jim.Idle <jimi@gatherstars.com>

parrt merged commit ef65951 into antlr:dev Aug 15, 2022

admin-token-bot mentioned this pull request Jul 7, 2024

[Snyk] Upgrade antlr4 from 4.7.2 to 4.13.1 mongodb-js/compass#6001

Closed

ThatGhostToast mentioned this pull request Nov 7, 2024

[Snyk] Upgrade antlr4 from 4.8.0 to 4.13.2 NextechSystems/fhirpath.js#3

Closed

fix: Fixes for https://github.com/antlr/antlr4/issues/3718 #3818

fix: Fixes for https://github.com/antlr/antlr4/issues/3718 #3818

Uh oh!

Conversation

jimidle commented Aug 13, 2022

Uh oh!

jimidle commented Aug 13, 2022

Uh oh!

kaby76 commented Aug 13, 2022 • edited Loading Uh oh! There was an error while loading. Please reload this page.

Uh oh!

Uh oh!

parrt Aug 13, 2022

Choose a reason for hiding this comment

Uh oh!

parrt commented Aug 13, 2022

Uh oh!

parrt commented Aug 13, 2022

Uh oh!

jimidle commented Aug 14, 2022 via email

Uh oh!

parrt commented Aug 14, 2022

Uh oh!

jimidle commented Aug 14, 2022 via email

Uh oh!

parrt commented Aug 14, 2022

Uh oh!

parrt commented Aug 14, 2022

Uh oh!

jimidle commented Aug 15, 2022 • edited Loading Uh oh! There was an error while loading. Please reload this page.

Uh oh!

Uh oh!

jimidle commented Aug 15, 2022 • edited Loading Uh oh! There was an error while loading. Please reload this page.

Uh oh!

Uh oh!

jimidle commented Aug 15, 2022

Uh oh!

jimidle commented Aug 15, 2022

Uh oh!

kaby76 commented Aug 15, 2022 • edited Loading Uh oh! There was an error while loading. Please reload this page.

Uh oh!

Uh oh!

jimidle commented Aug 15, 2022 via email

Uh oh!

kaby76 commented Aug 15, 2022 • edited Loading Uh oh! There was an error while loading. Please reload this page.

Uh oh!

Uh oh!

parrt commented Aug 15, 2022 • edited Loading Uh oh! There was an error while loading. Please reload this page.

Uh oh!

Uh oh!

parrt commented Aug 15, 2022

Uh oh!

jimidle commented Aug 16, 2022

Uh oh!

jimidle commented Oct 11, 2022 via email

Uh oh!

jimidle commented Oct 11, 2022 via email

Uh oh!

parrt commented Oct 13, 2022

Uh oh!

Uh oh!

kaby76 commented Aug 13, 2022 •

edited

Loading

jimidle commented Aug 15, 2022 •

edited

Loading

jimidle commented Aug 15, 2022 •

edited

Loading

kaby76 commented Aug 15, 2022 •

edited

Loading

kaby76 commented Aug 15, 2022 •

edited

Loading

parrt commented Aug 15, 2022 •

edited

Loading