Remove `_IsMoveConstructible` from `__pattern_sort` impls + add preconditions checks into sorting algorithms

[SergeyKopienko]

In this PR we doing the next things:

• remove _IsMoveConstructible template param from __pattern_sort implementations as not required.

~The proper way of fixing implemented in https://github.com/oneapi-src/oneDPL/pull/1604.~ According to comment https://github.com/oneapi-src/oneDPL/pull/1604#issuecomment-2141701447 from @akukanov, we return to this patch again.

[SergeyKopienko]

Should we implement, for example, the documented preconditions for

template<class ExecutionPolicy,
class ForwardIterator1, class ForwardIterator2, class T, class BinaryOperation1, class BinaryOperation2>
T
transform_reduce(ExecutionPolicy&& exec, ForwardIterator1 first1, ForwardIterator1 last1, ForwardIterator2 first2,
T init, BinaryOperation1 binary_op1, BinaryOperation2 binary_op2)

too ?

They are described at https://www.open-std.org/jtc1/sc22/wg21/docs/papers/2023/n4928.pdf, paragraph 27.10.6 Transform reduce:

Preconditions:
(4.1) — T meets the Cpp17MoveConstructible (Table 32) requirements.
(4.2) — Neither binary_op1 nor binary_op2 invalidates subranges, nor modifies elements in the ranges
[first1, last1] and [first2, first2 + (last1 - first1)]

and so far and so on...

[MikeDvorskiy]

After reading the standard and cppreference a little bit more deeply and keeping in mind oneDPL implementation, I would conclude following:

1. The requirement ValueSwappable for iterators for std::sort entails MoveContructable and MoveAssignable for value types. See https://en.cppreference.com/w/cpp/algorithm/swap. A standard-compliance implementation of std::sort relies on two comparing values.
2. For the oneDPL host policies we have the implementation (quick sort or merge sort) based on swapping two comparing values. So, if a user type doesn't meet Swappable requirement we have got a compile time error on std::swap call.
3. For the oneDPL device policies we have also a radix sort implementation where swappable property is not needed. Due to there is not radix sort in the standard, propagation the requirement from bullet 1 for a radix sort is not correct. However a radix sort still uses MoveContructable and MoveAssignable properties.

So, having MoveContructable tag and fallback to serial sort if the tag false_type looks weird because the serial sort (we use std::sort) uses std::swap and it entails MoveContructable in particular. So, removing MoveContructable tag looks right way.

Regarding the static asserts: I would suggest to add a static assert just in the pattern where we had MoveContructable tag to be ensure that previous fallback (if MoveContructable is false_type) is not a case.

Regarding the big comments: I am not sure that it makes sense to keep so big quotes (any quotes, actually) from the C++ standard. OneDPL has a documentation which contains a reference to the standard (in the parallel algorithms description). Moreover, with c++ concepts compile time diagnostic will be generated by compiler in any case.

[MikeDvorskiy]

hould we implement, for example, the documented preconditions for

Basically, oneDPL has not such practice and introducing such checks just for a couple of algorithms is not consistent approach. And I am not sure that we need it in total. Moreover with c++ concepts compile time diagnostic will be generated by compiler in any case. But I assume that can be some excepting cases where it can really help with a diagnostic error.

[SergeyKopienko]

After reading the standard and cppreference a little bit more deeply and keeping in mind oneDPL implementation, I would conclude following....

@MikeDvorskiy, your comment has been fixed.

[akukanov]

There are two things to note.

First, enforcing C++17 requirements with static asserts might result in breaking some codes that work now. We want our algorithms to be usable beyond the requirements of C++17, in particular, with C++20 ranges which iterators may not meet the legacy iterator requirements. Moreover, oneDPL special iterators also do not meet those legacy requirements. Adding assertions just "because we can", without a clear user value, makes no sense to me. And if we do add assertions, these should not be based on formal requirements but should enforce the actual expectations of our implementation to the input data types.

Second, while std::swap requires a type to be movable, std::is_swappable does not; instead, it checks if ADL-discoverable swap or std::swap work for the type. Both std::sort and our implementation of comparison sorts can use ADL-discoverable swap, so in theory both could work with types that are swappable yet not movable.

I guess our host implementation uses move operations directly (you can check it), and so it used _IsMoveConstructible in the dispatch to fall back to serial execution for non-movable types. The patch that introduced tag dispatching did not take it into account though, and added a tag type assertion which in retrospective does not seem correct. I think this assertion should be removed or reworked, while _IsMoveConstructible should be kept intact. Additionally, we should check if our documentation states anywhere that for execution policies to take effect with sort, the types should be move constructible (and perhaps also move assignable, if the implementation uses that as well).

Added: it appears that the C++ standard requirements for std::sort state both ValueSwappable for iterators and MoveConstructible and MoveAssignable for values. I do not quite understand why, and I still think our implementation should fall back to std::sort for non-movable types and let the standard library handle it.

Added-2: I was incorrect, the tag dispatching patch does not introduce the problem, its assertion matches the previous condition /*is_parallel==*/std::false_type. It's unclear when (if ever) that condition was added.

[akukanov]

Second, while std::swap requires a type to be movable, std::is_swappable does not; instead, it checks if ADL-discoverable swap or std::swap work for the type. Both std::sort and our implementation of comparison sorts can use ADL-discoverable swap, so in theory both could work with types that are swappable yet not movable.

Added: it appears that the C++ standard requirements for std::sort state both ValueSwappable for iterators and MoveConstructible and MoveAssignable for values. I do not quite understand why, and I still think our implementation should fall back to std::sort for non-movable types and let the standard library handle it.

After checking the behavior of the major standard library implementations at godbolt.org and finding out that their versions std::sort use move operations directly, I withdraw the above concern; having some extra code to delegate a decision to std::sort, which will anyway fail, it's not worth it.

[SergeyKopienko]

@akukanov, @MikeDvorskiy, @rarutyun please take a look at this PR again. Thanks.

[SergeyKopienko]

@MikeDvorskiy Should we propagate the changes from this PR to our up stream?