CODEWITHSUNDEEP
c++loopsrecursionlanguage-lawyerundefined-behavior
463035818_is_not_an_ai
463035818_is_not_an_ai

Reputation: 122830

Infinite loop vs infinite recursion. Are both undefined?

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...

Upvotes: 8

Views: 1433

Answers (3)

Jan Schultke
Jan Schultke

Reputation: 39773

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.

Upvotes: 2

supercat
supercat

Reputation: 81217

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.

Upvotes: 0

Rakete1111
Rakete1111

Reputation: 48998

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.

Upvotes: 12

Related Questions