Infinite loop vs infinite recursion. Are both undefined?

Question

Infinite loops without side effect are undefined behaviour. See here for the example from cppreference. Much simpler example:

int foo() {
    while(true) {}
    return 42;
}

Now consider the almost equivalent

int bar() {
    if (true) return bar();
    return 42;
}

Does this invoke undefined behaviour as well?

Or phrased differently: What class of error is infinite recursion according to the language?

PS: note that I am aware of the implications at runtime: The loop in principle could run forever, while the recursion will eventually result in a stackoverflow. Though I am mainly interested in what the compiler does to them. Maybe a quite academic question...

Judie

"The loop in principle could run forever, while the recursion will eventually result in a stackoverflow." – Actually, since it is UB it could do anything. And it doesn't have to recurse in the first place on actual hardware because of the as-if rule. In particular, if optimizations are enabled, the compiler is likely to replace your recursive example with effectively a loop (tail call optimization) even if it has side effects. – Myungmyxedema

@ArneVogel Yes the code is contrived but in practice most C++ code has no objects with non trivial dtors and cannot be tail optimized most of the time – Archetype

@ArneVogel read "in principle" as "what would happen if it wasnt ub" – Judie

@user463035818: I'd say if it wasn't UB I'd say an implementation should be expected to refrain from performing any action which wouldn't occur if the loop were omitted, or any action which would have a non-hoistable data dependency on anything in the loop, but may perform any actions which would occur if the loop were omitted, unless or until it encounters a non-hoistable data dependency. – Blastosphere

Answer 1

No there is no difference. [basic.progress]p1:

The implementation may assume that any thread will eventually do one of the following:

• terminate,

• make a call to a library I/O function,

• perform an access through a volatile glvalue, or

• perform a synchronization operation or an atomic operation.

It doesn't matter how you have your infinite loop; if it doesn't do any of the points above, you get UB. Including the following:

int bar(int cond) {
    if (cond == 42) bar(cond);
    return 42;
}
bar(some_user_input);

The compiler is allowed to assume that some_user_input will never be 42.

Outgoing

ah now I remember that this is the actual phrasing, I didnt find it anymore (i mean somewhere else than in the standard itself). cppreference is a bit short on ub – Judie

Where is it defined UB? Doesn't the standard states about loop removal? – Mesnalty

@Jean-BaptisteYunès It's in the "may assume" part. If your program doesn't do that you're violating the compiler's assumption which is the same thing as UB. It does but that's just an example of what could happen. – Outgoing

i am a bit confused. Naively put: Compiler knows that my stacksize is limited, infinite recursion will result in stack overflow, thread will terminate, all fine. Where am I wrong? – Judie

@user463035818 In the C++ abstract machine there is no stack size. That's one of those implementation defined limits, but it doesn't count as a program terminating if that makes sense. – Outgoing

@Outgoing you want to tell me stackoverflow isnt real ? :P Seriously, what is a stackoverflow in terms of the c++ language? It simply does not exist and therefore is undefined by definition? – Judie

@user463035818 Well yeah, it is not something the language is concerned about. It's not necessarily undefined though, it's just that that concept doesn't exist in the abstract machine. – Outgoing

Is there already an answer to why a compiler may assume that infinite loop is not a busy waiting for a signal to arrive? – Whisk

@LanguageLawyer Well if you want this waiting you would mark the variable denoting that with volatile, which would fall into the conditions above. You'd do that anyway so that the compiler doesn't optimize it away in some other context. – Outgoing

@Outgoing it is not an answer. – Whisk

@LanguageLawyer: Given func1(); func2(); any portions of func2(); which may be affected by actions performed in func1() must behave as though executed after those actions, but any actions in func1() and func2() that do not interact with each other and have no observable side-effects may be performed in any order. I think the Standard's language about assuming that loops terminate is intended to say that a failure of func1() to terminate would not in and of itself be a "side-effect" that must be sequenced prior to func2(). – Blastosphere

Answer 2

Yes, there is now a difference. P2809R3: Trivial infinite loops are not Undefined Behavior was accepted into C++ as a defect report, meaning all standards are changed retroactively, and some infinite loops are no longer undefined behavior.

The undefined behavior stems from the following paragraph:

The implementation may assume that any thread will eventually do one of the following:

• terminate,
• invoke the function std​::​this_thread​::​yield ([thread.thread.this]),
• make a call to a library I/O function,
• perform an access through a volatile glvalue,
• perform a synchronization operation or an atomic operation, or
• continue execution of a trivial infinite loop ([stmt.iter.general]).

- [intro.progress] p1

Firstly, note that your loop while (true) {} is a trivially empty iteration statement because it is of the form while (/* ... */) {}.

Furthermore, the definition of trivial infinite loop states:

A trivial infinite loop is a trivially empty iteration statement for which the converted controlling expression is a constant expression, when interpreted as a constant-expression ([expr.const]), and evaluates to true.

true obviously satisfies this, so while (true) {} is a trivial infinite loop and thus one of the things that any thread has to do eventually. By comparison, infinite recursion like if (true) recursive_call() isn't considered to be a trivial infinite loop, so it is undefined behavior.

Counterword

wow, I was involved in rather heavy discussions on the interpretation of this section in the standard and I never came to a conclusion (not a language lawyer myself). There were some guys who told me that this paragraph does not imply a simple infinite loop would be UB in contrast to the mainstream interpretation. This is the first time I hear about something that adds clarity to this kind of discussions. – Judie

"accepted into C++ as a defect report, meaning all standards are changed retroactively..." Defect report only applies to(/affect) the last published standard.This means that say if a DR is accepted for say C++26 then it would also be a DR against the last version which is C++23 in this example.Like for example, template<typename T> struct C{C<T>(){};}; was made invalid in C++20 as DR then it means that it will also be a DR against C++17 but not any earlier standard. But in C++14 and C++11, C<T>(); is still valid. It is up to implementation whether they apply the DR to previous standards. – Checkroom

...continued. As far as the standard is concerned, DR can only affect the last standard afaik. – Checkroom

@Checkroom I'm not entirely sure whether this is in line with ISO policy, but defect reports in C++ always date back to a specific version of C++, even withdrawn ones. This is important because users actively use all versions (e.g. via -std=c++11). On en.cppreference.com/w/cpp/26, you can see that the issues are marked DR98, DR11, etc. to denote a DR which goes back in time only to a specific standard, whereas DR means that it applies to all (I think?). – Counterword

In one of the discussions, one of the committee members once said that and I quote "we can't accept defect reports against older standards." – Checkroom

That's probably right in terms of ISO policy, and the DRs that go back further can be considered a message to compiler vendors that tell them what we want in older standards without formally changing those older versions of the standard. – Counterword

Answer 3

In most real-world situations, an invitation to assume something will happen implies that one is not obligated to take any special measures to allow for the possibility that it doesn't, but is not a license to behave in arbitrary fashion if one discovers that the event in question won't occur.

Under fashionable interpretations of the C Standard, however, there is no reason to expect that implementations will refrain from totally nonsensical fashion if any assumption the Standard would invite them to make proves incorrect.

I don't think the authors of the Standard intended that C compilers would use complicated inference engines which cascade assumptions to the point that a compiler given e.g.

if (x > 1000) foo(x);
while ( x <= 1000)
  somethingWithNoSideEffectsThatCantAffectX();

would conclude that foo should be executed unconditionally regardless of the value of x. More likely, they intended that a compiler given something like:

volatile int yy;
void test(int x, int *restrict arr)
{
  int y;
  do
    x=arr[x];
  while(x & 1);
  y=yy;
  if (y)
    printf("%d\n",x);
}

would be allowed to use the fact that the final value of x may or may not be needed to rearrange the code to be more efficient in the cases where it isn't (by skipping its calculation altogether). Essentially, the fact that a piece of code takes time to execute--even if infinite--should not be considered a side-effect in and of itself, and if a compiler can prove that a piece of code cannot execute any side-effects that would be visible before it reaches a certain place, it need not wait for that piece of code to finish before executing code at that place.

Unfortunately, the authors of the Standard rely upon compiler writers to recognize what kinds of actions may be usefully taken on the basis of certain assumptions, while compiler writers assume that any possible inference they can draw should be presumed useful.

Blastosphere