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?

Olly

What is the explanation? What is that which needs explaining? – Dekeles

@DavidRodríguez-dribeas I assumed two things and arrived at a contradiction - std::move(v,v) is guaranteed to do nothing and also it is undefined behavior. Those two statements cannot both be right. So something is wrong with my reasoning or with the assumptions. Which thing is wrong? – Olly

You mean std::swap(v,v), not std::move(v,v), right? – Dekeles

@DavidRodríguez-dribeas Yes, you are right, I mean std::swap(v,v). – Olly

I think it is relevant that this passage form the Standard does not mention undefined behavior, while it easily could have (of the two other items in the same list, suppressed in the citation, the first explicitly says UB, the second implicitly does so by using "shall"). And note that every time an argument of the form std::move(x) is passed to a s.l. function, the parameter is not a unique reference (since x the caller still exists); apparently the uniqueness assumption is only among the references the implementation can see. If UB had been invoked here, it would cast a lot of doubt – Eisinger

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.

Easternmost

I agree that the library implementer controls both std::swap and operator=(T&&) so he can do what he wants as long as the external interface is fulfilled, so in that sense the contradiction is resolved. However, you are then also saying that to implement std::swap in the way shown, it is necessary to make assumptions about the implementation of the standard library that are not guaranteed by the C++11 standard, but that can only be done safely by the implementer of the entire library? Or are you saying that MoveAssignable implies that v = std::move(v) must work, or at least not crash? – Olly

std::vector need not be MoveAssignable for swapping vectors because swap is specialized for vectors. However surely one ought to be able to std::sort a vector<vector<T>> and in that case std::sort requires that vector<T> be MoveAssignable, whether it has been moved from or not. The sort implementor is allowed to self-move-assign this vector<T> (or do whatever it takes to make the algorithm slower). However I don't believe the sort implementor is allowed to assume what the resulting value of a self-move-assignment is, or that it is a no-op. – Easternmost

So you are saying that for a type to be MoveAssignable it must allow self move assignment and so cannot assume non-aliasing between this and the parameter in the move assignment operator? That would resolve the contradiction in the question. – Olly

For a type to be MoveAssignable it must allow for self-move-assignment. But it doesn't have to guarantee what the resulting value is. Although there is a statement about what value the lhs has after move assignment, the value of the rhs after move assignment is allowed to be unspecified. When the lhs and the rhs are the same object, take your pick about which of those contradicting requirements to meet. Clients of self-move-assignment should assume the worst (the object is left in an unspecified - but valid - state). – Easternmost

My personal guideline is: If someone points out a self-move-assignment or self-swap in my code, I consider it at the very least a performance bug, and except in the case of std::swap, it probably indicates a correctness bug as well. But that's my personal guideline, not what the standard says. – Easternmost

I believe that Table 22 in this draft is the complete definition of what it means to be MoveAssignable. It does not specifically allow aliases or even say anything about aliases. By what reasoning do you believe that "v is MoveAssignable" implies "the quote in the question does not apply to v"? If it is not necessary to explicitly point out that aliases are allowed to duck out of the quote in the question, then are there any circumstances at all where that quote applies? – Olly

@HowardHinnant: Your second comment seems to make a basic logic error. If two requirements are given, one must meet the logical conjuction (and) of the requirements. You cannot "take your pick" about which requirement to meet (logical disjunction). In this case there is a strong requirement on the lhs (equivalence), and a weak requirement on the rhs (valid but unspecified state). If lhs and rhs are the same, the requirement becomes: a valid state, and a value equivalent to its own previous value. In other words x=std::move(x) is required to have no effect. – Eisinger

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.

Improvisator

How does the object being empty resolve the contradiction in the question? The quote in the question does not seem to me to allow an exception for empty objects. – Olly

@BjarkeH.Roune: Consider the code: int i; i=i; i=5;. The middle statement reads an uninitialized variable, but that does not affect the correctness of the declaration or the later assignment. The quote states that the implementation is allowed to assume that there is no aliasing (i.e. this and rhs to be different objects), that in turn means that it can freely release the resources and then grab them from the argument, which would be problematic in the general case, but in this case the previous line has already taken the resources. – Dekeles

@BjarkeH.Roune: [...] Note that the quote does not even say that it is undefined behavior to pass aliased objects, only that the implementation can freely assume that aliasing did not happen. By the time the second line executes the real contents are held somewhere else, so they are not affected by the expression. The guarantees on the object before and after the expression are exactly the same and must be maintained regardless of potential aliasing: the object must be destructible, and that is all that is needed for the third statement. – Dekeles

I think assuming no aliasing is only an implication, not the entire statement. I read the quote in the question to allow an implementation to do if (this == &t) exit(1); inside operator=(T&&). If that is allowed then it is not relevant if t is moved from or not, right? – Olly

If you tell me I can assume a statement P then you are also telling me I can do if (!P) exit(1). In other words, if I can assume P but P is not actually true, then that is undefined behavior. Or is that wrong? – Olly

Surely in the standard, "the implementation may assume X" is code for, "if the program arranges for X to be false then behavior is undefined"? – Allegorize

@DavidRodríguez-dribeas: Your comment includes the snippet int i; i=i; i=5; but the rest of it is wrong. int i; i = i; is undefined behavior (performs lvalue-to-rvalue conversion on an indeterminate value which is not a narrow character). After that all bets are off. If the result were a new indeterminate value (as would be the case for a narrow character), then the subsequent assignment, which doesn't care about the prior value, would restore normality. But with int, it's UB, and no subsequent code can make the execution well-defined again. – Rothko

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.

Homesteader

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.

Oxus

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])

Rebozo

Thanks for pointing out the error. I updated the question. However, correcting the error does not seem to me to answer the problem. – Olly

Same difference: template <typename T> void swap(T&a,T&b) { T tmp(std::move(a)); a=std::move(b); b=std::move(tmp); } – Dekeles