C++ multiple access to rvalue reference in the same statement as perfect forwarding

Question

Is the following code safe? Particularly, if vec is an rvalue reference, does the last line do what it should (namely a recursion in which the elements of vec are correctly summed up)?

template<typename VectorType>
auto recurse(VectorType&& vec, int i)
{
     if(i<0)
          return decltype(vec[i])();
     return vec[i] + recurse(std::forward<VectorType>(vec), i-1); //is this line safe?
}

My doubts are related to the fact that since the order of evaluation is unspecified, the vector could have been moved before operator[] is evaluated, and therefore the latter could fail.

Is this fear justified, or is there some rule that prevents this?

Answer 1

Consider the following:

std::vector<int> things;

// fill things here

const auto i = static_cast<int>(things.size()) - 1;

// "VectorType &&" resolves to "std::vector<int> &&" -- forwarded indirectly
recurse(move(things), i);

// "VectorType &&" resolves to "std::vector<int> &" -- also forwarded indirectly
recurse(things, i);

// "VectorType &&" resolves to "const std::vector<int> &" -- again, forwarded indirectly
recurse(static_cast<const std::vector<int> &>(things), i);

Even after all 3 calls to recurse in the example above, the things vector would still be intact.

If the recursion were changed to:

return vec[i] + recurse(forward<VectorType>(vec), --i);

the results would then be undefined, as either vec[i] or --i could be evaluated in either order.

Function calls are like sequence points: The results of argument expressions must be computed before the function is called. The order in which this happens, however, is undefined -- even with respect to sub-expressions within the same statement.

Forcing the construction of an intermediate within the recursion statement would also result in undefined behavior.

For example:

template<typename VectorType>
auto recurse(VectorType &&vec, int i)
{
    using ActualType = typename std::decay<VectorType>::type;
    if(i < 0){
        return decltype(vec[i]){};
    }
    return vec[i] + recurse(ActualType{forward<VectorType>(vec)}, i - 1);
}

Here, vec[i] or ActualType{forward<VectorType>(vec)} could be evaluated in either order. The latter would either copy-construct or move-construct a new instance of ActualType, which is why this is undefined.

In Summary

Yes, your example will sum the contents of the vector.

There is no reason for the compiler to construct an intermediate, so successive invocations of recurse each receive an indirect reference to the same, unchanging instance.

Addendum

As pointed out in a comment, it is possible for a non-const operator[] to mutate the instance of VectorType, whatever that might be. In this case, the result of the recursion would be undefined.

Answer 2

You are correct, evaluation of vec[i] and the recursive call is indeterminately ordered (they can't actually overlap, but can happen in either of the two possible orders).

I don't see why you're taking an rvalue reference, though, because you don't ever actually move from vec.

Unless VectorType has operator[](index_type) &&, I don't see how the indeterminate execution actually leads to failure. (On the other hand, the infinite recursion ildjarn spotted will cause a failure). Actually, operator[](index_type) && would lead to failure with all execution orders.

This function should work just fine with a const& parameter type, and then you wouldn't be worrying.

Answer 3

std::forward won't mutate your object by itself. It will cast vec to the same value category that was deduced when the parent call to recurse was made. For that matter, std::move also won't by itself mutate its argument.

However, casting to the rvalue category can indirectly enable mutation to happen (and this is the whole point, it enables some optimizations based on mutating the moved from object). If the rvalue overload for the function you are calling mutates its argument.

In this case it looks like no-one is mutating things (as long as vec[i] or operator+ isn't mutating things), so I think you would be safe here no matter what the order of evaluation is.

As another answerer pointed out, passing by const ref means the compiler would complain if mutation could be happening somewhere (eg operator[] for the current vector type is non const, or operator+ is non-const, etc). This would allow you to worry less.