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.
Comment #1 by ibuclaw — 2020-07-13T08:57:55Z
Reduction is indeed close to what I anticipated.
---
@property empty(T)(T a)
{
return !a;
}
auto cmp(R1, R2)(R1 , R2 r2)
{
for (;;)
if (r2.empty) return int();
}
auto caseEnclose()
{
unicode.LC;
}
struct unicode
{
auto opDispatch(string name)() {
static if (cmp(name, ""))
return ;
}
}
---
In the original, there would have been a popFront() call, but I suspect that the body of popFront was removed during reduction.
Comment #2 by bcarneal11 — 2020-07-13T14:09:00Z
(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.
Comment #3 by ibuclaw — 2020-09-03T08:37:53Z
(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.
Comment #4 by robert.schadek — 2024-12-13T19:10:10Z