Self-moves break several sorting algorithms

[Morwenn]

I tweaked the move_only test in the test suite to also check that self-moves don't happen. It is reasonable to require that no self-move happens when sorting, and thus to support types for which self-move is an error/might destroy the value. This matters because even std::string might destruct its value on a self-move. The result is a bit saddening, I will at least have to fix the following sorters:

• block_sorter (at least with a fixed buffer of size 0)
• drop_merge_sorter (see also Strange benchmark results with std::string adrian17/cpp-drop-merge-sort#4)
• quick_merge_sorter
• selection_sorter

In the meantime I'll be marking the test as [!mayfail]. It's not a regression: we simply never tried to check that self-move worked.

Note: see the comments below to understand the striked-through bullet items.

[Morwenn]

quick_merge_sorter was apparently fixed when I fixed selection_sorter, which isn't surprising considering the former uses the latter.

[Morwenn]

I was forced to do a bit of research to make a few things clear about who's responsible about what when it comes to self-move and self-swap in generic libraries and algorithms. As far as I can tell, here is the standard's take:

• Class authors have the responsibility to write move operations in a way which leaves a self-moved object in a valid but unspecified state. The defect report LWG2468 adds a bit of wording for C++17, and LWG2839 intends to make it a rule for standard library types. What self-move does for non-standard library types is unspecified, so standard library algorithms are required to avoid self-moves.
• Class authors have the responsibility to make the expression using std::swap; swap(x, x); work: it can be done either by writing a move assignment operation that works as expected with std::swap (Eric Niebler gives a nice example of such a type), or by providing an ADL-found swap function that makes the self-swap work. The C++20 Swappable concept apparently blesses self-swaps as safe too.
• Generic algorithms authors can assume that self-swap is a safe operation, but should otherwise guard against self-moves.

Now I'm pretty sure I need to avoid self-moves in the library but I'm not sure whether I should be conservative or not when it comes to self-swap. It actually matters for algorithms like selection_sort that can easily perform a self-swap. Having a guarantee that trivially copyable types don't change the value of a self-moved object would be nice too.

[Morwenn]

More on this: a note in Swappable actually makes it clear that the two operands of swap(t1, u1) can denote the same object:

[ Note: t1 and u1 can denote distinct objects, or the same object. — end note ]

This means that ensuring that the expression using std::swap; swap(x, x); is the responsibility of the author of the class whose x is an instance, and that generic algorithms can assume that the expression just works and does the right thing. There are still no guarantees for self-move, even for standard library types (even though they should soon be guaranteed to leave the self-moved object in a valid but unspecified state, meaning that assigning to such an object is still a valid operation).

In our case, it means that we need to:

• Change the move_only type in the test suite by adding an ADL-found swap operation to it which doesn't throw an exception on self-swap.
• Remove the code that makes selection_sort safe against self-swap.
• Remove a check before performing a potential self-swap in split_sort.
• Document in the library introduction the expected semantics for self-move and self-swap, which is: algorithms expect self-swap to be a valid operation and rely on it, but otherwise strive to avoid raw self-moves. Mention the Swappable concept.

it's worth noting that if self-move are eventually guaranteed to leave an object in a valid but unspecified state, it might be safe to perform "reference-rotation" operations on a same object (swap just rotates the values of two objects).

[Morwenn]

Everything item in this issue has been fixed, it was almost fast. Closing the issue.