TestFailure: testInvalidATNStateRemoval

[jwkohnen]

This is an odd one and frankly I haven't got a foggiest what is going on. The test testInvalidATNStateRemoval's Test binary occupies 100% CPU and doesn't terminate. I have isolated the generated code and ran a pprof session. This is the (slightly modified) code of Test.go:

type TreeShapeListener struct {
        *parser.BaseTListener
}

func NewTreeShapeListener() *TreeShapeListener {
        return new(TreeShapeListener)
}

func (this *TreeShapeListener) EnterEveryRule(ctx antlr4.ParserRuleContext) {
        for i := 0; i < ctx.GetChildCount(); i++ {
                child := ctx.GetChild(i)
                parentR, ok := child.GetParent().(antlr4.RuleNode)
                if !ok || parentR.GetBaseRuleContext() != ctx.GetBaseRuleContext() {
                        panic("Invalid parse tree shape detected.")
                }
        }
}

func main() {
        f, err := os.Create("/tmp/pprof")
        if err != nil {
                panic(err)
        }
        pprof.StartCPUProfile(f)
        go func() {
                timer := time.NewTimer(2 * time.Minute)
                <-timer.C
                pprof.StopCPUProfile()
                f.Close()
                os.Exit(0)
        }()

        input := antlr4.NewFileStream("input")
        lexer := parser.NewTLexer(input)
        stream := antlr4.NewCommonTokenStream(lexer, 0)
        p := parser.NewTParser(stream)
        p.BuildParseTrees = true
        tree := p.Start()
        antlr4.ParseTreeWalkerDefault.Walk(NewTreeShapeListener(), tree)
}

Code after tree := doesn't seem to ever be reached and so EnterEveryRule is never called. The profiler shows, that the ParserATNSimulatortries to put a lot into some Set which results into a lot of equals calls.

Now the two things that confuse me the most are that apparently I am the only one who observes this(?) and when I try to debug this with Delve the binary does(!) terminate.

This is the CPU profile:

and the test grammar:

grammar T;
start : ID ':' expr;
expr : primary expr? {} | expr '->' ID;
primary : ID;
ID : [a-z]+;

The input file:

x:x

Can anyone else reproduce this? What does this code path try to accomplish in the first place? (I am not an expert in augmented transition networks.)

Because delve session terminates I figured there migth be a race condition. Running the binary with -race for two hours did not offer any insight.

[jwkohnen]

Note to self from gitter:

The only thing I know is that tons of almost the same ATNConfig values get added to the set. They differ only in their reachesIntoOuterContext value that gets counted + 1 ad infinitum. There is only one place where an increment happens, that is (*ParserANTSimulator).closureWork.

[pboyer]

The call stack, for reference.

testInvalidATNStateRemoval(org.antlr.v4.test.runtime.go.TestParserErrors)  Time elapsed: 60.004 sec  <<< ERROR!
java.lang.Exception: test timed out after 60000 milliseconds
    at java.lang.Object.wait(Native Method)
    at java.lang.Object.wait(Object.java:502)
    at java.lang.UNIXProcess.waitFor(UNIXProcess.java:181)
    at org.antlr.v4.test.runtime.go.BaseTest.execModule(BaseTest.java:463)
    at org.antlr.v4.test.runtime.go.BaseTest.execRecognizer(BaseTest.java:447)
    at org.antlr.v4.test.runtime.go.BaseTest.execParser(BaseTest.java:394)
    at org.antlr.v4.test.runtime.go.TestParserErrors.testInvalidATNStateRemoval(TestParserErrors.java:152)
    at sun.reflect.NativeMethodAccessorImpl.invoke0(Native Method)
    at sun.reflect.NativeMethodAccessorImpl.invoke(NativeMethodAccessorImpl.java:57)
    at sun.reflect.DelegatingMethodAccessorImpl.invoke(DelegatingMethodAccessorImpl.java:43)
    at java.lang.reflect.Method.invoke(Method.java:622)
    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.internal.runners.statements.FailOnTimeout$StatementThread.run(FailOnTimeout.java:74)

[sridharxp]

Following the trail of error testInvalidATNStateRemoval ....... In parser package (folder) in t_parser.go I could print debug statements upto line 336 _alt := p.GetInterpreter().AdaptivePredict(p.GetTokenStream(), 1, p.GetParserRuleContext()) Executing this line test hangs. I hope this is of some help.