Fix errors in `__pattern_sort` implementations and its calls

[SergeyKopienko]

In this PR we implement another approach for the problem found in https://github.com/oneapi-src/oneDPL/pull/1599

What we doing in this PR:

• remove static_assert check of tag type from __pattern_sort + tag implemetation.
• pass real sign of is_move_constructible value into __pattern_sort from __pattern_partial_sort_copy + hetero impl.

Looks like this approach fixing all topics described by @akukanov at https://github.com/oneapi-src/oneDPL/pull/1599#issuecomment-2129859538

The approach from this PR is compatible with implementation of __pattern_sort from our up-stream: https://github.com/search?q=repo%3Allvm%2Fllvm-project%20path%3A%2F%5Epstl%5C%2Finclude%5C%2Fpstl%5C%2F%2F%20__pattern_sort(&type=code where each call of __pattern_sort for non-move_constructible data types is processed by serial implementation:

template <class _Tag, class _ExecutionPolicy, class _RandomAccessIterator, class _Compare, class _IsMoveConstructible>
void
__pattern_sort(_Tag, _ExecutionPolicy&&, _RandomAccessIterator __first, _RandomAccessIterator __last, _Compare __comp,
               _IsMoveConstructible) noexcept
{
    std::sort(__first, __last, __comp);
}

Before this PR the idea that "each call of __pattern_sort for non-move_constructible data types is processed by serial implementation" has been broken in oneDPL implementation.

Just for note

I think oneDPL implementation still doesn't support preconditions for std::sort : 1) The preconditions from https://en.cppreference.com/w/cpp/algorithm/sort requirements: If any of the following conditions is satisfied, the behavior is undefined: (until C++11) The type of first is not Swappable.
(since C++11) RandomIt is not ValueSwappable. The type of first is not MoveConstructible. The type of first is not MoveAssignable. 2) The preconditions from https://www.open-std.org/jtc1/sc22/wg21/docs/papers/2023/n4971.pdf, paragraph 27.8.2.1 sort [sort]: Preconditions: The range [first, last) is a valid heap with respect to comp and proj. For the overloads in namespace std, RandomAccessIterator meets the Cpp17ValueSwappable requirements (16.4.4.3) and the type of first meets the Cpp17MoveConstructible (Table 31) and Cpp17MoveAssignable (Table 33) requirements.

Also, looks like the same preconditions has place for std::sort with ranges too.

[akukanov]

I think oneDPL implementation still doesn't support preconditions for std::sort :

I do not understand this comment. First of all, let's see what the term "Preconditions" means. Citing the C++ standard (see e.g. https://eel.is/c++draft/structure.specifications#3.3):

Preconditions: the conditions that the function assumes to hold whenever it is called; violation of any preconditions results in undefined behavior.

In other words, preconditions are what an implementation of the C++ standard library can assume about the function arguments. There is no obligation for an implementation to check all the preconditions of a function, neither to somehow react if these are not met. Undefined behavior really means any behavior - including correct processing in accordance with the function semantics.

Our implementation would violate the standard in case if it had other expectations (requirements) to the arguments. Is this the case?

[SergeyKopienko]

I do not understand this comment. First of all, let's see what the term "Preconditions" means. Citing the C++ standard (see e.g. https://eel.is/c++draft/structure.specifications#3.3):

I trying to highlight that the logic why we checking IsMoveConstructible and dispatching by it's state is unclear for me. Requirements (preconditions) for std::sort from https://en.cppreference.com/w/cpp/algorithm/sort and from https://www.open-std.org/jtc1/sc22/wg21/docs/papers/2023/n4971.pdf means from my point of view that if some sorting data type isn't IsMoveConstructible then we have UB.

So why we shouldn't simple remove any dispatching from sort implementations by IsMoveConstructible state at all?

[akukanov]

I trying to highlight that the logic why we checking IsMoveConstructible and dispatching by it's state is unclear for me.

This is very different from "our implementation does not support preconditions of std::sort". Thanks for clarification.

Requirements (preconditions) for std::sort from https://en.cppreference.com/w/cpp/algorithm/sort and from https://www.open-std.org/jtc1/sc22/wg21/docs/papers/2023/n4971.pdf means from my point of view that if some sorting data type isn't IsMoveConstructible then we have UB.

That's correct. Remember though that undefined behavior is not an error of any kind.

So why we shouldn't simple remove any dispatching from sort implementations by IsMoveConstructible state at all?

We can. I preferred, however, to delegate dealing with non-movable types to the standard library instead, at least for the host policies for which executing serially is always correct.

But in practice (checked at godbolt.org) all the 3 major standard library implementations really require the type to be movable and will fail to compile otherwise. So such delegation makes no practical sense, and therefore I withdraw this concern. Let's return to the original patch #1599.

[SergeyKopienko]

Close this PR and continue works on https://github.com/oneapi-src/oneDPL/pull/1599