some non-determinism in testExprAmbiguity_2(org.antlr.v4.test.runtime.go.TestFullContextParsing)?

[jwkohnen]

Two test runs of the same test had different output, yielding in a pass and a fail. Maybe that is due to non-determinism of a Go map or something?

The failed test run put out ambigAlts={2, 1} instead of ambigAlts={1, 2}. Revision is 439a3b7. Apparently we'll have to run all tests a few hundred times, yay! Now I've run this test a dozen times and could not reproduce the fail.

I have arbitrarily chosen this test for debugging my git-bisect runner script. This is one of the tests that we've turned green in the last few days. Or maybe it was green all along and I just had some bad entropy in my test history? :)

Running org.antlr.v4.test.runtime.go.TestFullContextParsing
dir /tmp/TestFullContextParsing-1464523216232/parser
exec stderrVacuum: line 1:1 reportAttemptingFullContext d=1 (expr), input='+'
line 1:2 reportContextSensitivity d=1 (expr), input='+b'
line 1:3 reportAttemptingFullContext d=1 (expr), input='*'
line 1:5 reportAmbiguity d=1 (expr): ambigAlts={2, 1}, input='*c'

Tests run: 1, Failures: 1, Errors: 0, Skipped: 0, Time elapsed: 12.103 sec <<< FAILURE!
testExprAmbiguity_2(org.antlr.v4.test.runtime.go.TestFullContextParsing)  Time elapsed: 11.799 sec  <<< FAILURE!
org.junit.ComparisonFailure: expected:<... (expr): ambigAlts={[1, 2]}, input='*c'
> but was:<... (expr): ambigAlts={[2, 1]}, input='*c'
>
    at org.junit.Assert.assertEquals(Assert.java:115)
    at org.junit.Assert.assertEquals(Assert.java:144)
    at org.antlr.v4.test.runtime.go.TestFullContextParsing.testExprAmbiguity_2(TestFullContextParsing.java:208)
    at sun.reflect.NativeMethodAccessorImpl.invoke0(Native Method)
    at sun.reflect.NativeMethodAccessorImpl.invoke(NativeMethodAccessorImpl.java:62)
    at sun.reflect.DelegatingMethodAccessorImpl.invoke(DelegatingMethodAccessorImpl.java:43)
    at java.lang.reflect.Method.invoke(Method.java:498)
    at org.junit.runners.model.FrameworkMethod$1.runReflectiveCall(FrameworkMethod.java:47)
    at org.junit.internal.runners.model.ReflectiveCallable.run(ReflectiveCallable.java:12)
    at org.junit.runners.model.FrameworkMethod.invokeExplosively(FrameworkMethod.java:44)
    at org.junit.internal.runners.statements.InvokeMethod.evaluate(InvokeMethod.java:17)
    at org.junit.internal.runners.statements.RunBefores.evaluate(RunBefores.java:26)
    at org.junit.rules.TestWatcher$1.evaluate(TestWatcher.java:55)
    at org.junit.rules.RunRules.evaluate(RunRules.java:20)
    at org.junit.runners.ParentRunner.runLeaf(ParentRunner.java:271)
    at org.junit.runners.BlockJUnit4ClassRunner.runChild(BlockJUnit4ClassRunner.java:70)
    at org.junit.runners.BlockJUnit4ClassRunner.runChild(BlockJUnit4ClassRunner.java:50)
    at org.junit.runners.ParentRunner$3.run(ParentRunner.java:238)
    at org.junit.runners.ParentRunner$1.schedule(ParentRunner.java:63)
    at org.junit.runners.ParentRunner.runChildren(ParentRunner.java:236)
    at org.junit.runners.ParentRunner.access$000(ParentRunner.java:53)
    at org.junit.runners.ParentRunner$2.evaluate(ParentRunner.java:229)
    at org.junit.runners.ParentRunner.run(ParentRunner.java:309)
    at org.apache.maven.surefire.junit4.JUnit4Provider.execute(JUnit4Provider.java:242)
    at org.apache.maven.surefire.junit4.JUnit4Provider.executeTestSet(JUnit4Provider.java:137)
    at org.apache.maven.surefire.junit4.JUnit4Provider.invoke(JUnit4Provider.java:112)
    at sun.reflect.NativeMethodAccessorImpl.invoke0(Native Method)
    at sun.reflect.NativeMethodAccessorImpl.invoke(NativeMethodAccessorImpl.java:62)
    at sun.reflect.DelegatingMethodAccessorImpl.invoke(DelegatingMethodAccessorImpl.java:43)
    at java.lang.reflect.Method.invoke(Method.java:498)
    at org.apache.maven.surefire.util.ReflectionUtils.invokeMethodWithArray(ReflectionUtils.java:189)
    at org.apache.maven.surefire.booter.ProviderFactory$ProviderProxy.invoke(ProviderFactory.java:165)
    at org.apache.maven.surefire.booter.ProviderFactory.invokeProvider(ProviderFactory.java:85)
    at org.apache.maven.surefire.booter.ForkedBooter.runSuitesInProcess(ForkedBooter.java:115)
    at org.apache.maven.surefire.booter.ForkedBooter.main(ForkedBooter.java:75)

Results :

Failed tests:   testExprAmbiguity_2(org.antlr.v4.test.runtime.go.TestFullContextParsing): expected:<... (expr): ambigAlts={[1, 2]}, input='*c'(..)

[jwkohnen]

Amendment: I've updated the script's gist. The above test already had a mvn -Pgen "generate-test-sources". Update: I did reproduce the fail once more.

[pboyer]

This data is ultimately extracted from BitSet's data field, which, as you suspect, is a map. We can probably sort this field in BitSet's String method.

[jwkohnen]

It is still a bit hard to grasp what does what where and why. I've seen that code and wondered if we should reimplement BitSet using uint and binary operations (just like Java's BitSet under the hood) -- but sorting String() is probably the easier way for now.

[jwkohnen]

... or is it sparse? Edit: Oh lala, I've just reviewed Java's BitSet and it is a lot different than I remembered. Let's sort String(). :D