James Clark
James Clark
It seems like this technique is successfully stressing our recursive types implementation!
I think this shows algorithm in #1065 isn't right.
Can you add a test case for this? It should only run if long-running tests are enabled.
As of Update 2 and with regex fixes, reproduce the problem by doing `make` in `extra/regex` and then running: ``` java -Xss100M -jar ../../build/extra/bin/nballerina.regex.jar "BDGB(gSUNd(Pp(xMsTI(TcnBE)*ke)*)*S)*v" "BDGB(gSUNd(Pp(xMsTI((CvGb)*TcnBE)*ke)*)*S)*v" ```
This pair completes in a second: ``` "BD(gS(Pp(xM(Tc)*ke)*)*S)*v" "BD(gS(Pp(xM((CvGb)*Tc)*ke)*)*S)*v" ``` But changing Tc to Tcn in the innermost part i.e. ``` "BD(gS(Pp(xM(Tcn)*ke)*)*S)*v" "BD(gS(Pp(xM((CvGb)*Tcn)*ke)*)*S)*v" ``` causes execution time to explode to...
I am wondering if the problem is that we are creating new BDDs that combine provisionally empty BDDs, but we are not using the provisional emptiness to simplify the BDDs...
New example from @heshanpadmasiri ``` "((P(x(Tcn)*ke)*)*ab)*" "((P(x((CvGb)*Tcn)*ke)*)*ab)*" ```
I tried this: ``` time java -Xss100M -jar ../../build/extra/bin/nballerina.regex.jar "ab(cd(ef(gh(ijABCDEFGHI)*lm)*)*n)*o" "ab(cd(ef(gh((pqrs)*ijABCDEFGHI)*lm)*)*n)*o" ``` and it got a stack overflow after about 100 minutes.
It starts off with `diff(j0, i1|b1|a1)`, so I think we need to handle unions.
Draft PR in #1040