Subtype check for some complex, nested recursive types takes excessive time and stack space

[heshanpadmasiri]

Running the program in extra/regex with the following arguments

• BDGB(gSUNd(Pp(xMsTI(TcnBE)*ke)*)*S)*v
• BDGB(gSUNd(Pp(xMsTI((CvGb)*TcnBE)*ke)*)*S)*v

(which tests whether the first regex is a subtype of the second) uses a lot of time and stack space.

It caused the memo table to grow to 243 (checked after this line) and provisional empty count to change between 21 and 22 (checked after this line)

Could be the same cause as #1074 but didn't caused at stack overflow in about 10-20 minutes (#1074 will cause it within few minutes)

[jclark]

It seems like this technique is successfully stressing our recursive types implementation!

[jclark]

I think this shows algorithm in #1065 isn't right.

[jclark]

Can you add a test case for this? It should only run if long-running tests are enabled.

[heshanpadmasiri]

One problem we have in the current implementation is that if we mark one type as provisional it will make every subsequent provisional if that type is empty. This don't take into account the fact the subsequent type may have no dependency on any provisionally empty type.

One idea on how to deal with this is for a given Bdd (that comes after a provisionally empty type and we think is empty), if all the child nodes in the bdd are known to be nonprovisional then that type must be nonprovisional as well.

[jclark]

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"