[Issue 21044] [CTFE] Infinite loop in ForStatement::interpret

[d-bugmail at puremagic.com]

https://issues.dlang.org/show_bug.cgi?id=21044

--- Comment #3 from Iain Buclaw <ibuclaw at gdcproject.org> ---
(In reply to Bruce Carneal from comment #2)
> (In reply to Iain Buclaw from comment #0)
> > Found on one iteration of mechanically reduced code (still dozens of files,
> > thousands of lines of code). Will copy it and reduce it further, but I
> > suspect that the final product will be code that looks like:
> > 
> > ---
> > int foo()
> > {
> >     for (;;) { }
> >     return 0;
> > }
> > 
> > static assert(foo() == 0);
> > ---
> > 
> > If that is the case, then the compiler really should have proper detection
> > for this, to bail and error out if it finds a loop that never exits during
> > CTFE.
> 
> As you noted during beerconf, dlang is Turing complete at compile time,
> which leaves us with the halting problem. (yes, indeed, we're working with
> power tools)
> 
> Per Stefan's comments at beerconf the current approach to this includes a
> limit on recursion at compile time.  From your experience, and anticipating
> recursion rewrites to iterative forms in the future, something more is
> needed.
> 
> Is there some notion of "progress" at compile time that is readily
> available?  A count of the source level symbols resolved perhaps?  There's
> no "solving" the halting problem of course, just looking for a practical
> bound.
> 
> Seems like current CTFE practice and implementation generate a number of
> intermediate structures that ultimately collapse to something roughly the
> size of the source input.

There's already some rudimentary code flow analysis in place.  I can't imagine
it being too expensive to determine the likelihood of a branch returning.  And
if the answer is never (infinite loop), then bail and error before executing
the code.

--