Bug 4984 – Recursive template constraint results in dmd running out of memory

This lovely little program: import std.algorithm; import std.range; immutable string[] tokens = [null, ";", "{", "}", "\"", "\\", "//", "/+", "+/", "/*", "*/", "unittest", "import"]; string findTokensStr(string varName, string rangeName) { string findClause = "auto " ~ varName ~ " = find(" ~ rangeName; foreach(string token; tokens[1..$]) { if(token.startsWith("\"") || token.startsWith("\\")) findClause ~= ", \"\\" ~ token ~ "\""; else findClause ~= ", \"" ~ token ~ "\""; } return findClause ~ ");"; } void main() { string str = "my string"; mixin(findTokensStr("found", "str")); } causes dmd to exit with Error: out of memory This may or may not be due to bug # 1382, but it certainly means that this fairly simple string-constructing function can't be used with CTFE. Hopefully it can be done with an eponymous template, but depending on the exact cause, that may not work either. Regardless, this is a serious bug. It runs just fine if yo just print the string instead of mixing it in, but as soon as you mix it in, both the CPU and memory consumption blossom until dmd runs out of memory.

This is worse than I thought. The problem has nothing to do with the mixin at all. Maybe constructing the string for the mixin helps make dmd run out of memory, maybe not, but the find() is enough to do it. Take this program for instance import std.algorithm; void main() { string str = "my string"; auto found = find(str, ";", "{", "}", "\\\"", "\"", "//", "/+", "+/", "/*", "*/", "unittest", "import"); } It runs out of memory just fine on its own, without the mixin. find() is going to be rather limiting if it can't be used with more than a few possible needles. Granted, the most typical use case is a single needle, but dmd really should be able to handle a more or less arbitrary number of needles (though obviously something like 100 needles wouldn't necessarily be reasonable). In any case, 12 needles is enough. If I remove one and make it 11, then a ridiculous amount of memory is used, but at least dmd doesn't run out. With 12, it does.

This is likely due to the recursive template constraint used in std.algorithm.startsWith. A reduced test case: --------------- void x(U...)(U args) if ( is(typeof( x(args[1..$]) )) ) { } void x(U)(U u) { } void main() { x(1,2,3,4,5,6,7,8,9,10,11,12,13,14,15,16,17,18,19,20); } --------------- Similar test case: --------------- void x(int n)() if (n > 0 && is(typeof(x!(n-1) ()))) { } void x(int n : 0)() { } void main() { x!20(); } --------------- Phobos could workaround this by moving the recursive part into a static-if/static-assert. (Note: I only check if it consumes an unusually large amount memory and does not stop. I didn't wait until it runs out of memory.)

Wow. A fix for this one? This'll be huge! Anything that causes dmd to use less memory is big - especially if templates are involved. Thanks!