Order of evaluation in v != std::exchange(v, predecessor(v))

Question

I keep finding more idioms that lend themselves to std::exchange.

Today I found myself writing this in an answer:

do {
    path.push_front(v);
} while (v != std::exchange(v, pmap[v]));

I like it a lot more than, say

do {
    path.push_front(v);
    if (v == pmap[v])
        break;
    v= pmap[v];
} while (true);

Hopefully for obvious reasons.

However, I'm not big on standardese and I can't help but worry that lhs != rhs doesn't guarantee that the right-hand side expression isn't fully evaluated before the left-hand-side. That would make it a tautologous comparison - which would by definition return true.

The code, however, does run correctly, apparently evaluating lhs first.

Does anyone know

• whether the standard guarantees this evaluation order
• if it has changed in recent standards, which standard version first specified it?

---

PS. I realize that this is a special case of f(a,b) where f is operator!=. I've tried to answer my own query using the information found here but have failed to reach a conclusion to date:

• https://en.cppreference.com/w/cpp/language/eval_order
• https://en.wikipedia.org/wiki/Sequence_point
• Order of evaluation in C++ function parameters
• What are the evaluation order guarantees introduced by C++17?

Answer 1

C++17 introduced rules on sequences. What was UB before is now well defined. This applies to arguments to function calls as well as a select assortment of operators:

sequenced before is an asymmetric, transitive, pair-wise relationship between evaluations within the same thread.

• If A is sequenced before B (or, equivalently, B is sequenced after A), then evaluation of A will be complete before evaluation of B begins.

The built-in != however is not sequenced (see link above). A function call would be sequenced but the order of evaluation is not guaranteed:

15. In a function call, value computations and side effects of the initialization of every parameter are indeterminately sequenced with respect to value computations and side effects of any other parameter.

(emphasis added)

To my reading, even if you wrote a wrapper function, your compiler would not be required to evaluate v first, then std::exchange(v, pmap[v]) and finally equal(..). And reversing the evaluation order, I believe, would change semantics in your example.

So sadly, as nice as std::exchange is, in this case, it is not guaranteed to do what you need it to.

Answer 2

If != calls an overloaded comparison operator that takes the left argument (v) by reference, the order of evaluation here does not really matter: binding a reference (directly) does not access the object denoted by the initializer. The actual comparison (in the body of the operator function) takes place after both operands are evaluated ([intro.execution]/11):

When calling a function [...], every value computation and side effect associated with any argument expression [...] is sequenced before execution of every expression or statement in the body of the called function.

In other words, the comparison is guaranteed behave as you expect here.

---

This does not hold if evaluating the left side involves reading the value of v, as in the case of the built-in != operator, or an overload taking it by value (or requiring a conversion to bind a reference).

In that case, it becomes significant that the two operands are unsequenced ([intro.execution]/10):

Except where noted, evaluations of operands of individual operators and of subexpressions of individual expressions are unsequenced.

(The != operator does not have any special sequencing properties.)

There is potential for UB here:

If a side effect on a memory location is unsequenced relative to either another side effect on the same memory location or a value computation using the value of any object in the same memory location, and they are not potentially concurrent, the behavior is undefined.

However, [intro.execution]/11 applies:

For each function invocation or evaluation of an await-expression F, each evaluation that does not occur within F but is evaluated on the same thread and as part of the same signal handler (if any) is either sequenced before all evaluations that occur within F or sequenced after all evaluations that occur within F.

Summarized by a footnote:

In other words, function executions do not interleave with each other.

Which means the read of v on the left and its modification on the right (which occurs within std::exchange) can't conflict, and are effectively indeterminately sequenced: there's no UB, but no guarantee of consistent results either.

---

C++17 made some changes to the rules of evaluation order, but none are relevant here: this answer holds pre-C++17 as well.

Answer 3

Regardless of whether or not this works, it is almost completely unreadable code -- and remember that we write code mostly for humans, not compilers!

As a general rule, using conditionals that have side effects are often hard to read and understand because our brains are not equipped to do two things at once: Understand whether the condition is true or false, and also keep track of what changes. Do one thing at a time if you want others to easily understand what is happening. In your case, you are adding a third dimension to it: when something changes; using conditionals in which you have a function call that changes something, and comparing the changed result against something else is just impossible to read :-)

If you absolutely must use this idiom, separate the three parts:

do {
    path.push_front(v);
} while ([&v,&pmap]() mutable
         {
           auto old_v = v;  
           v = pmap[v];
           return v != old_v;
         } ());

This code is equivalent, of course, but I think it is far easier to read. Although I will claim that it is still harder to read than your alternative code without using std::exchange() :-)