1

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?

davidhigh
  • 14,652
  • 2
  • 44
  • 75

3 Answers3

2

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.

defube
  • 2,395
  • 1
  • 22
  • 34
  • what about `recurse(std::vector(10,1.0),9)`? The template parameter `VectorType` gets deduced to `std::vector`, and the `std::forward` behaves identical to a `std::move`. Now if the vector is moved before `operator[]` is evaluated, doesn't it lead to a problem? – davidhigh Nov 13 '14 at 04:40
  • Actually, that's still an r-value. – defube Nov 13 '14 at 04:46
  • yes, and as such the content of the vector gets moved to the next `recurse` function, leaving the current vector object in an unspecified state in which one cannot dereference it ... at least if I understand [this answer](http://stackoverflow.com/a/7028318/2412846) correctly. What do you mean? – davidhigh Nov 13 '14 at 04:59
  • "std::vector{10, 1.0}" binds as an R-value. It the un-named result of an expression. – defube Nov 13 '14 at 05:00
  • Relax, I don't feel offended. On the contrary, this was a thing I really wasn't completely aware of ... only move into *objects* leads to an unspecified state, whereas one can have as many rvalue references as you want (as long as one keeps track if one of these is moved). So thanks! – davidhigh Nov 13 '14 at 06:12
  • Many welcomes! You might imagine how much fun this was with early VS support, which didn't do this right when I was building an AD framework (buffer slicing, everywhere!). – defube Nov 13 '14 at 06:16
  • This answer is wrong in one small corner case -- You assume that there is no operation here that moves from `vec`, but we don't know what `VectorType` is, so we can't know whether it has an `operator[]` that is destructive when applied to an rvalue. – Ben Voigt Nov 13 '14 at 14:19
  • @BenVoigt Come to think of it, a non-const `operator[]` in general would do that (or even touch mutable state within in the const case). I've updated my answer. – defube Nov 13 '14 at 21:17
1

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.

Ben Voigt
  • 277,958
  • 43
  • 419
  • 720
1

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.

orm
  • 2,835
  • 2
  • 22
  • 35
  • Same comment as in the answer of Ben Voigt: What is if some `class MyCustomVector` contains a `std::unique_ptr` holding the data and I call the function like `recurse(MyCustomVector,100)`. Then it should be what you call mutating, and therefore won't work as intended, or? – davidhigh Nov 13 '14 at 04:34
  • We are calling operator[] on vec and operator+ on vec[i] and the result from recurse(), which I think is a temporary of type decltype(vec[i]) (and perhaps some implicit conversions). Unless they are mutating things, no matter what the type of the vec[i], is, I can see no problem. Even if the container holds unique_ptrs, it is possible to acess them read-only. This depends on the types of operator[]. – orm Nov 13 '14 at 04:35
  • For stl vectors at least, operator[] returns a reference and does not mutate anything. So, again, it depends on what the operator[] does. Not so much on what type the container holds. – orm Nov 13 '14 at 04:52
  • but according to [this answer](http://stackoverflow.com/a/7028318/2412846), one cannot dereference a moved vector. So if the vector content is gone to the next `recurse`, I would have thought that the current object `vec` is in an unspecified state (and thus mutated), such that I can't access its content? – davidhigh Nov 13 '14 at 04:57
  • 2
    There is no contradiction here. Moving from x, perhaps counter-intuitively, is not the same as calling as std::move on x. You still need some code that will take x and mutate it. Normally move constructors or move assignemnts do this mutation. In this case, recurse takes its input by reference (this is important). Then, once inside recurse, in the base case, there is no mutation (unless operator[] mutates the vector). So it doesn't happen. – orm Nov 13 '14 at 05:18