Deep function causes Dafny Visual Studio extension to hang

[jaylorch]

Opening a file with a deep nested function in Visual Studio causes the Dafny extension to hang. Here's an example:

datatype List = Cons(hd:int, tl:List) | Nil

function DeepFunction() : List
{
Cons(32,Cons(31,Cons(30,Cons(29,Cons(28,Cons(27,Cons(26,Cons(25,Cons(24,Cons(23,Cons(22,Cons(21,Cons(20,Cons(19,Cons(18,Cons(17,Cons(16,Cons(15,Cons(14,Cons(13,Cons(12,Cons(11,Cons(10,Cons(9,Cons(8,Cons(7,Cons(6,Cons(5,Cons(4,Cons(3,Cons(2,Cons(1, Nil))))))))))))))))))))))))))))))))
}

Breaking into the debugger while this is happening reveals the cause to be a call to ExprRegions that happens in ComputeIdentifierRegions. It appears that because the expression corresponding to each Cons is an ApplySuffix, ExprRegions is called both on its Lhs and on each of its subexpressions. But, since the Lhs is itself a subexpression, each call to ExprRegions causes two invocations of ExprRegions. Thus, in a 32-deep function, we get 2^32 calls to ExprRegions.

I believe the fix is just to comment out the following lines in ExprRegions:

  } else if (expr is ApplySuffix) {

/* I propose cutting these because the Lhs will be visited by the for loop below
var e = (ApplySuffix)expr;
if (e.Lhs != null) {
ExprRegions(e.Lhs, regions, prog, module);
}
*/
} else if (expr is LetExpr) {