Bug 14419 – [CTFE] Need infinite loop detection?

This was noticed and raised in GDC Bugzilla #178 because of a typo in the code. http://bugzilla.gdcproject.org/show_bug.cgi?id=178 What it boils down to is this: --- int foo() { while (true) { } return 1; } enum bar = foo; // User meant to type '&foo' --- Perfectly valid code causing an infinite loop in CTFE. Obviously this is a bug vs. feature argument, but infinite loop detection should really be a feature of CTFE to avoid accidental build bugs from occurring.

Luckily you just prevented me from pressing "Submit Issue" in filing a duplicate by approximately 1 second! Some further thoughts: In the particular code snippet, my 'Reset_Handler' does not return a value. Since D specifies that a void is the same as int returning 0, then it would make sense to completely avoid evaluating functions that return 'void', and just insert a 0 in the array instead, possibly giving an error or warning. This would also speed up build time for other functions. -Thinking a bit further: What if something else was initialized by a list of functions returning void in an array - that's abusing the functionality and I do not know if it's possible to do so.

(In reply to Iain Buclaw from comment #0) > This was noticed and raised in GDC Bugzilla #178 because of a typo in the > code. > > http://bugzilla.gdcproject.org/show_bug.cgi?id=178 > > > What it boils down to is this: > --- > int foo() { while (true) { } return 1; } > enum bar = foo; // User meant to type '&foo' > --- > > Perfectly valid code causing an infinite loop in CTFE. Obviously this is a > bug vs. feature argument, but infinite loop detection should really be a > feature of CTFE to avoid accidental build bugs from occurring. How to do it for a complex code? int foo(int n = 0) { while (true) { ++n; if (n > 1_000_000) break; } return 1; } enum bar = foo; // User meant to type '&foo' Using while(true) for the limited loop is usual. And limiting loop repetition to arbitrary count is problematic (a million repetition is too big?). The idea sounds good, but implementing it would be difficult.

at least there is sense to make CTFE fail early when it tries to evaluate function with inappropriate return value. the original sample was this: alias extern(C) immutable void function () VectorFunc; VectorFunc[3] g_pfnVectors = [ Reset_Handler, ]; extern(C) void Reset_Handler () { while (true) {} } there is no sense to evaluate `Reset_Handler`, as it's return value (actually, absense of) is not suitable as array element.

ah, Jens already wrote about it. i really have to learn to read all the answers three times before posting my own!

(In reply to Ketmar Dark from comment #3) > alias extern(C) immutable void function () VectorFunc; > VectorFunc[3] g_pfnVectors = [ > Reset_Handler, > ]; > > extern(C) void Reset_Handler () { > while (true) {} > } It's another issue in the process of initializer semantic. Essentially it should make a type error: Reset_Handler() is void and has no value, but current dmd prematurely runs CTFE.

(In reply to Kenji Hara from comment #2) > How to do it for a complex code? > > int foo(int n = 0) > { > while (true) > { > ++n; > if (n > 1_000_000) > break; > } > return 1; > } > enum bar = foo; // User meant to type '&foo' I would check if the 'exit' condition changes. When the code is compiled, it boils down to two or three interesting assembly-languge instructions: 1: compare 2: conditional branch forward 3: branch always backward If the argument to 'compare' changes, then the loop would most likely not be infinite and thus most likely be safe to execute. There might be multiple conditions, though, which makes things a bit more complex. However, I sense that there might be possible ways that the condition could change on every compare, where it wouldn't be safe to just check for changes. Example: int Init_element(n) { l = 17; while(1) { n = 3 - n; if(n == 0) break; l *= 31415927; } return(l); } Because of the 'toggling', the compiler might not be able to predict that this keeps going on for eternity. Such cases are of course rare, but should still be considered.

(In reply to Kenji Hara from comment #2) > (In reply to Iain Buclaw from comment #0) > > This was noticed and raised in GDC Bugzilla #178 because of a typo in the > > code. > > > > http://bugzilla.gdcproject.org/show_bug.cgi?id=178 > > > > > > What it boils down to is this: > > --- > > int foo() { while (true) { } return 1; } > > enum bar = foo; // User meant to type '&foo' > > --- > > > > Perfectly valid code causing an infinite loop in CTFE. Obviously this is a > > bug vs. feature argument, but infinite loop detection should really be a > > feature of CTFE to avoid accidental build bugs from occurring. > > How to do it for a complex code? > > int foo(int n = 0) > { > while (true) > { > ++n; > if (n > 1_000_000) > break; > } > return 1; > } > enum bar = foo; // User meant to type '&foo' > > Using while(true) for the limited loop is usual. And limiting loop > repetition to arbitrary count is problematic (a million repetition is too > big?). > > The idea sounds good, but implementing it would be difficult. Branch exit (BE) prediction might be sufficient (and fast) for this. I'll have to double check whether or not we hold enough information though.

determining finiteness of arbitrary algorithm is one of the greatest problems of current AI research. ;-) i believe that it's better to not start. the code for checking various cases will grow and grow and grow, and there allways will be much more cases that it can't detect. and people will open bug reports for "bug in infinite loop detection", and more special cases will be added. this process is infinite. ;-) i think it's better to simply don't do that, and document the fact that CTFE engine doesn't do infinite loop detection.

For an AST interpreter this would mean you'd need to snapshot loop conditions to compare them, right? Sounds like slowing down interpretation and making a JITed interpreter much harder for a hacky fix to an unsolvable problem (http://en.wikipedia.org/wiki/Halting_problem). If you really think we should fix this, then a time limit for CTFE execution might be feasible.

(In reply to Martin Nowak from comment #9) > If you really think we should fix this, then a time limit for CTFE execution > might be feasible. I think it would be a good thing to at least implement a 'general-case' fix. 1: on dlang.org, there's an on-line compiler. It wouldn't take much effort to bring it to the knees. 2: When the users of D grow, the number of bug-reports will grow very quickly. Believe me; I worked on a Web-browser for the Mac platform, which had 200000 downloads the first week. At the time, we were 2 developers on the Mac platform. -Needless to say (but I'll do it anyway): Those people did not know much about bug-reporting. 200000 people - many of them 'novice' againt 2 developers = a whole load of bug reports that could never be marked 'fixed' - many because we could never keep up. (This particular web-browser actually *had* a loop detection on the Javascript, and it was impossible for me to trick it). Fortunately, the D compiler team have better conditions. The users are developers, so most of them know what it's all about - but there are still people writing code, who should not wear the title "developer"; simply because their only agenda is "to make damage".

(In reply to Jens Bauer from comment #10) > (This particular web-browser > actually *had* a loop detection on the Javascript, and it was impossible for > me to trick it). it's very easy to trick any endless loop detection code: just start computing PI. ;-)

(In reply to Ketmar Dark from comment #3) > alias extern(C) immutable void function () VectorFunc; > VectorFunc[3] g_pfnVectors = [ > Reset_Handler, > ]; > > extern(C) void Reset_Handler () { > while (true) {} > } > > there is no sense to evaluate `Reset_Handler`, as it's return value > (actually, absense of) is not suitable as array element. There is another detail here, which I just noticed: In the array, I do not give the function any arguments / parameters. -Shouldn't that be reported as an error, or is it intended that functions are callable like this: a = printf; ... ? In C, a would be a pointer to the function printf, however in D, a would contain the result of the execution.

(In reply to Jens Bauer from comment #12) > There is another detail here, which I just noticed: > In the array, I do not give the function any arguments / parameters. > > -Shouldn't that be reported as an error, or is it intended that functions > are callable like this: > a = printf; > > ... ? > > In C, a would be a pointer to the function printf, however in D, a would > contain the result of the execution. That is intended, you can call a function without parameters by omitting any parentheses. To get the address of a function, you must use the & operator.

(In reply to Martin Nowak from comment #9) > If you really think we should fix this, then a time limit for CTFE execution > might be feasible. An iteration limit would be better than a time limit, because it will not be dependent on environmental conditions. This would need to be configurable from the command line etc. The compilation would terminate with a nice stack trace, making it easy to debug. (In reply to Jens Bauer from comment #10) > 1: on dlang.org, there's an on-line compiler. It wouldn't take much effort > to bring it to the knees. It's trival to make a D program that will take a very very long time to compile, even without infinite loops.

(In reply to yebblies from comment #14) > (In reply to Martin Nowak from comment #9) > > If you really think we should fix this, then a time limit for CTFE execution > > might be feasible. > > An iteration limit would be better than a time limit, because it will not be > dependent on environmental conditions. This would need to be configurable > from the command line etc. > > The compilation would terminate with a nice stack trace, making it easy to > debug. > So then you just need to decide what is a suitable iteration limit, short.max? ushort.max?

(In reply to Iain Buclaw from comment #15) > So then you just need to decide what is a suitable iteration limit, > short.max? ushort.max? If it's just to make sure that "we're not stuck forever", the size of the returned argument might be suitable. I believe this is very much a matter of opinion, though. But consider this. Combining with my previous idea of checking the exit-conditions. All sources for the exit-conditions should be saved (the stack would be fine): All minimum values for the exit conditions All maximum values for the exit conditions A minimumHit counter A maximumHit counter Each time the same minimum for all exit conditions are hit, then the minimumHit counter is incremented. If a new minimum is found, the minimumHit counter is cleared. Same thing for the maximumHit counter. Now if any of those two counters reach a value above - say 10, then we'll exit the loop. As a fail-safe, an unsigned 32-bit counter could be used as an 'absolutely maximum limit'. This is just an idea, but I believe it would be fairly good at catching more than 99% of the lockups.

(In reply to Jens Bauer from comment #16) > As a fail-safe, an unsigned 32-bit counter could be used as an 'absolutely > maximum limit'. ... and if the 32-bit counter wraps, then an error message should be given to the user, for instance: "Error: Please write better code." ;)

THIS ISSUE HAS BEEN MOVED TO GITHUB https://github.com/dlang/dmd/issues/17703 DO NOT COMMENT HERE ANYMORE, NOBODY WILL SEE IT, THIS ISSUE HAS BEEN MOVED TO GITHUB