melt-umn
OOM in finding shift/reduce conflict counterexample
I have been encountering OOM errors from Copper in the counterexample search process:
Exception in thread "main" java.lang.OutOfMemoryError: Java heap space
at java.base/java.util.LinkedList.addAll(LinkedList.java:428)
at java.base/java.util.LinkedList.addAll(LinkedList.java:391)
at edu.umn.cs.melt.copper.compiletime.auxiliary.counterexample.CounterexampleSearch.findShiftConflictPath(CounterexampleSearch.java:431)
at edu.umn.cs.melt.copper.compiletime.auxiliary.counterexample.CounterexampleSearch.counterexampleFromShortestPath(CounterexampleSearch.java:359)
at edu.umn.cs.melt.copper.compiletime.auxiliary.counterexample.CounterexampleSearch.counterexampleFromShortestPath(CounterexampleSearch.java:333)
at edu.umn.cs.melt.copper.compiletime.auxiliary.counterexample.CounterexampleSearch.getExample(CounterexampleSearch.java:177)
at edu.umn.cs.melt.copper.compiletime.logging.messages.CounterexampleMessage.<init>(CounterexampleMessage.java:27)
at edu.umn.cs.melt.copper.compiletime.checkers.ParseTableConflictChecker.checkConflicts(ParseTableConflictChecker.java:101)
at edu.umn.cs.melt.copper.compiletime.checkers.ParseTableConflictChecker.check(ParseTableConflictChecker.java:52)
at edu.umn.cs.melt.copper.compiletime.pipeline.ParserBeanCompiler.compileParserBean(ParserBeanCompiler.java:195)
at edu.umn.cs.melt.copper.compiletime.pipeline.StandardSpecCompiler.compileParser(StandardSpecCompiler.java:18)
at edu.umn.cs.melt.copper.compiletime.pipeline.StandardSpecCompiler.compileParser(StandardSpecCompiler.java:14)
at edu.umn.cs.melt.copper.compiletime.pipeline.StandardPipeline.execute(StandardPipeline.java:87)
at edu.umn.cs.melt.copper.main.ParserCompiler.compile(ParserCompiler.java:220)
at edu.umn.cs.melt.copper.main.ParserCompiler.main(ParserCompiler.java:470)
My copper grammar is attached. I haven't been able to sort out exactly what triggers the crash, yet, but I know that this grammar does contain at least a few conflicts.
@keltono I'm assigning you in case you ever have a chance to take a look at this, since I don't think anyone else really understands that code.
I took a brief look and it appears that the search loop in CounterexampleSearch.findShiftConflictPath() is getting sucked into a death spiral upon encountering a cyclical path. I put in a quick-and-dirty guard statement to stop the search proceeding along cyclical paths and it terminated with the following output -- is this what is expected?
Counterexample (2 parse trees that are the same until the conflict point, and may differ after):
reduce derivation:
^
↳ Root $
↳ GlobalDecls
↳ GlobalDecl GlobalDecls
↳ FnDecl
↳ 'fun' Name '(' Params ')' '->' TypeExpr '{' StmtList '}'
↳ Stmt StmtList
↳ '{' StmtList '}'
↳ Stmt StmtList
↳ Expr '=' Expr ';'
↳ Name •
shift derivation:
^
↳ Root $
↳ GlobalDecls
↳ GlobalDecl GlobalDecls
↳ FnDecl
↳ 'fun' Name '(' Params ')' '->' TypeExpr '{' StmtList '}'
↳ Stmt StmtList
↳ Expr ';'
↳ Expr '||' Expr
↳ Expr '&&' Expr
↳ Expr '>=' Expr
↳ Expr '>' Expr
↳ Expr '<=' Expr
↳ Expr '<' Expr
↳ Expr '!=' Expr
↳ Expr '==' Expr
↳ Expr '/' Expr
↳ Expr '*' Expr
↳ Expr '-' Expr
↳ Expr '+' Expr
↳ Expr '?' Expr ':' Expr
↳ Expr '.' Name
↳ Expr '(' Exprs ')'
↳ '{' FieldExprs '}'
↳ FieldExpr ',' FieldExprs
↳ Name • '=' Expr
Hmm. That does seem to be a valid counterexample, but the long chain of various infix operator expressions in the lower example does not appear to be needed. I don't think the counterexamples are necessarily supposed to be minimal, but it seems like we should be able to better than this?