On implementing std::swap in terms of move assignment and move constructor

Question

Here is a possible definition of std::swap:

template<class T>
void swap(T& a, T& b) {
  T tmp(std::move(a));
  a = std::move(b);
  b = std::move(tmp);
}

I believe that

1. std::swap(v,v) is guaranteed to have no effects and
2. std::swap can be implemented as above.

The following quote seems to me to imply that these beliefs are contradictory.

17.6.4.9 Function arguments [res.on.arguments]

1 Each of the following applies to all arguments to functions defined in the C++ standard library, unless explicitly stated otherwise.

...

• If a function argument binds to an rvalue reference parameter, the implementation may assume that this parameter is a unique reference to this argument. [ Note: If the parameter is a generic parameter of the form T&& and an lvalue of type A is bound, the argument binds to an lvalue reference (14.8.2.1) and thus is not covered by the previous sentence. — end note ] [ Note: If a program casts an lvalue to an xvalue while passing that lvalue to a library function (e.g. by calling the function with the argument move(x)), the program is effectively asking that function to treat that lvalue as a temporary. The implementation is free to optimize away aliasing checks which might be needed if the argument was an lvalue. —endnote]

(thanks to Howard Hinnant for providing the quote)

Let v be an object of some movable type taken from the Standard Template Library and consider the call std::swap(v, v). In the line a = std::move(b); above, it is the case inside T::operator=(T&& t) that this == &b, so the parameter is not a unique reference. That is a violation of the requirement made above, so the line a = std::move(b) invokes undefined behavior when called from std::swap(v, v).

What is the explanation here?

Answer 1

[res.on.arguments] is a statement about how the client should use the std::lib. When the client sends an xvalue to a std::lib function, the client has to be willing to pretend that the xvalue is really a prvalue, and expect the std::lib to take advantage of that.

However when the client calls std::swap(x, x), the client isn't sending an xvalue to a std::lib function. It is the implementation that is doing so instead. And so the onus is on the implementation to make std::swap(x, x) work.

That being said, the std has given the implementor a guarantee: X shall satisfy MoveAssignable. Even if in a moved-from state, the client must ensure that X is MoveAssignable. Furthermore, the implementation of std::swap doesn't really care what self-move-assignment does, as long as it is not undefined behavior for X. I.e. as long as it doesn't crash.

a = std::move(b);

When &a == &b, both the source and target of this assignment have an unspecified (moved-from) value. This can be a no-op, or it can do something else. As long as it doesn't crash, std::swap will work correctly. This is because in the next line:

b = std::move(tmp);

Whatever value went into a from the previous line is going to be given a new value from tmp. And tmp has the original value of a. So besides burning up a lot of cpu cycles, swap(a, a) is a no-op.

Update

The latest working draft, N4618 has been modified to clearly state that in the MoveAssignable requirements the expression:

t = rv

(where rv is an rvalue), t need only be the equivalent value of rv prior to the assignment if t and rv do not reference the same object. And regardless, rv's state is unspecified after the assignment. There is an additional note for further clarification:

rv must still meet the requirements of the library component that is using it, whether or not t and rv refer to the same object.

Answer 2

Then the expression a = std::move(b); gets executed, the object is already empty, in a state where only destruction is well defined. That will effectively be a no-op, as the object on the left and right hand sides is already empty. The state of the object after the move is still unknown but destructible. The next statement moves the contents back from tmp and that sets the object back to a known state.

Answer 3

I agree with your analysis, and in fact the libstdc++ Debug Mode has an assertion that will fire on self-swap of standard containers:

#include <vector>
#include <utility>

struct S {
  std::vector<int> v;
};

int main()
{
  S s;
  std::swap(s, s);
}

The wrapper type S is needed because swapping vector directly uses the specialization that calls vector::swap() and so doesn't use the generic std::swap, but S will use the generic one, and when compiled as C++11 that will result in a self-move-assignment of the vector member, which will abort:

/home/toor/gcc/4.8.2/include/c++/4.8.2/debug/vector:159:error: PST.

Objects involved in the operation:
sequence "this" @ 0x0x7fffe8fecc00 {
  type = NSt7__debug6vectorIiSaIiEEE;
}
Aborted (core dumped)

(I don't know what "PST" is supposed to mean there! I think something is wrong with the installation I tested it with.)

I believe GCC's behaviour here is conforming, because the standard says that the implementation can assume that self-move-assignment never happens, therefore the assertion will never fail in a valid program.

However, I agree with Howard that this needs to work (and can be made to work without too much trouble - for libstdc++ we just need to delete the debug mode assertion!), and so we need to fix the standard to make an exception for self-move, or at least self-swap. I have been promising to write a paper about this issue for some time, but haven't done so yet.

I believe that since writing his answer here Howard now agrees there is a problem with the current wording in the standard, and we need to fix it to forbid libstdc++ from making that assertion that fails.

Answer 4

My understanding is that the issue was not thought about until recently, so existing wording in C++20 standard does not really address it.

C++23 working draft N4885 includes Library Working Group issue 2839 resolution at [lib.types.movedfrom]/2:

An object of a type defined in the C++ standard library may be move-assigned (11.4.6 [class.copy.assign]) to itself. Such an assignment places the object in a valid but unspecified state unless otherwise specified.

That makes such std::swap perfectly valid for standard library types.

Answer 5

I believe that is not a valid definition of std::swap because std::swap is defined to take lvalue references, not rvalue references (20.2.2 [utility.swap])