[libc++][ranges] Implement `std::sortable`.

[var-const]

Use the actual patch link.

[• Quuxplusone]

LGTM except for the tests. Thanks for working on this — you're very close to completing all the iterator concepts! :)

libcxx/include/__iterator/sortable.h

31–32

As usual, I'd prefer 2-space indents, even though clang-format disagrees.

libcxx/test/std/iterators/iterator.requirements/alg.req.sortable/sortable.compile.pass.cpp

16

#include <functional> for ranges::less (which I guess isn't used right now, but probably should be)

34

It occurs to me that you're missing tests for when _Comp is not ranges::less and/or _Proj is not std::identity.
Then, looking closer at this test, all sorts of problems pop into view.

static_assert( std::indirect_strict_weak_order<CompInt, AllConstraintsSatisfied>);
static_assert( std::sortable<AllConstraintsSatisfied>);

Maybe you meant either-or-both of these instead?

static_assert( std::indirect_strict_weak_order<ranges::less, AllConstraintsSatisfied>);
static_assert( std::sortable<AllConstraintsSatisfied>);
static_assert( std::indirect_strict_weak_order<CompInt, AllConstraintsSatisfied>);
static_assert( std::sortable<AllConstraintsSatisfied, CompInt>);

And then on line 32,

static_assert(!std::indirect_strict_weak_order<CompInt, NoIndirectStrictWeakOrder>);

is true, but has nothing to do with why !std::sortable<NoIndirectStrictWeakOrder>.

So, some more work is needed on this test.
This might also cause retroactive changes to mergeable.compile.pass.cpp, assuming it's missing the same kinds of coverage.

[var-const]

Address feedback, rebase on main, guard sortable on NO_INCOMPLETE_RANGES
(because ranges::less is now also guarded on it).

[var-const]

libcxx/include/__iterator/sortable.h

31–32

Thinking more about this, I can buy an argument in favor of a 2-space indent for concepts. The general spirit is to use a narrower indent for continuation of constructs that are expected to normally be multiline (e.g. a function body) and a wider, more noticeable indent for constructs that are normally a single line but had to be split into multiple lines. For concepts, clearly the former is more applicable than the latter. Thus, treating the && and || more like ; in a function seems reasonable in this case.

libcxx/test/std/iterators/iterator.requirements/alg.req.sortable/sortable.compile.pass.cpp

34

Should be fixed, PTAL.

[ldionne]

LGTM except for the missing coverage for projections. I don't think I need to see this again.

libcxx/test/std/iterators/iterator.requirements/alg.req.sortable/sortable.compile.pass.cpp

28

You seem to be missing coverage for passing a projection. I think this also means you won't be able to use int if you want the projection to be non-trivial. You could define something like struct Point { int x; int y; }; and have your projection be a function Point -> int.

[var-const]

Test a non-default projection.

[• Quuxplusone]

libcxx/test/std/iterators/iterator.requirements/alg.req.sortable/sortable.compile.pass.cpp

39

I think it would be useful (in the sense of self-documentation) to add

static_assert(!std::sortable<Foo*, CompInt>);

[var-const]

For non-default projections, assert that using the default projection doesn't work.

libcxx/docs/Status/RangesPaper.csv

 | `indirectly_movable_storable <https://llvm.org/D102639>`_
 | `indirectly_copyable <https://llvm.org/D118432>`_
 | `indirectly_copyable_storable <https://llvm.org/D118432>`_",[iterator.concepts],Zoe Carver and Konstantin Varlamov,✅
 `[alg.req] <https://wg21.link/alg.req>`_: pt. 2,`indirectly_swappable <https://llvm.org/D105304>`_,"| [iterator.concepts]
 | [iterator.cust.swap]",Zoe Carver,✅
 `[alg.req] <https://wg21.link/alg.req>`_: pt. 3,`indirectly_comparable <https://llvm.org/D116268>`_,[projected],Nikolas Klauser,✅
 `[alg.req] <https://wg21.link/alg.req>`_: pt. 4,"| `permutable <https://llvm.org/D119222>`_
 | `mergeable <https://llvm.org/D119489>`_
-| sortable",[iterator.concepts],Konstantin Varlamov,In progress
+| `sortable <https://llvm.org/D119619>`_",[iterator.concepts],Konstantin Varlamov,✅
 `[std.iterator.tags] <https://wg21.link/std.iterator.tags>`_,"| `contiguous_iterator_tag <https://llvm.org/rG45d048c20440989df2b4e1be1f9343225e7741ab>`_
 | `iterator_concept specialization for pointers <https://llvm.org/rG45d048c20440989df2b4e1be1f9343225e7741ab>`_
 ",[iterator.traits],Eric Fiselier,✅
 `[range.iter.ops] <https://wg21.link/range.iter.ops>`_,"| `ranges::advance <https://llvm.org/D101922>`_
 | `ranges::distance <https://llvm.org/D102789>`_
 | `ranges::next <https://llvm.org/D102563>`_
 | `ranges::prev <https://llvm.org/D102564>`_",[iterator.concepts],Christopher Di Bella and Arthur O'Dwyer,✅
 `[predef.iterators] <https://wg21.link/predef.iterators>`_,"

libcxx/include/CMakeLists.txt

set(files
   __iterator/ostreambuf_iterator.h
   __iterator/permutable.h
   __iterator/prev.h
   __iterator/projected.h
   __iterator/readable_traits.h
   __iterator/reverse_access.h
   __iterator/reverse_iterator.h
   __iterator/size.h
+  __iterator/sortable.h
   __iterator/unreachable_sentinel.h
   __iterator/wrap_iter.h
   __libcpp_version
   __locale
   __mbstate_t.h
   __memory/addressof.h
   __memory/allocation_guard.h
   __memory/allocator.h

libcxx/include/__iterator/sortable.h

+// -*- C++ -*-
+//===----------------------------------------------------------------------===//
+//
+// Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.
+// See https://llvm.org/LICENSE.txt for license information.
+// SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception
+//
+//===----------------------------------------------------------------------===//
+
+#ifndef _LIBCPP___ITERATOR_SORTABLE_H
+#define _LIBCPP___ITERATOR_SORTABLE_H
+
+#include <__config>
+#include <__functional/identity.h>
+#include <__functional/ranges_operations.h>
+#include <__iterator/concepts.h>
+#include <__iterator/permutable.h>
+#include <__iterator/projected.h>
+
+#if !defined(_LIBCPP_HAS_NO_PRAGMA_SYSTEM_HEADER)
+#  pragma GCC system_header
+#endif
+
+_LIBCPP_BEGIN_NAMESPACE_STD
+
+#if !defined(_LIBCPP_HAS_NO_CONCEPTS) && !defined(_LIBCPP_HAS_NO_INCOMPLETE_RANGES)
+
+template <class _Iter, class _Comp = ranges::less, class _Proj = identity>
+concept sortable =
+  permutable<_Iter> &&
+  indirect_strict_weak_order<_Comp, projected<_Iter, _Proj>>;
+
+#endif // !defined(_LIBCPP_HAS_NO_CONCEPTS) && !defined(_LIBCPP_HAS_NO_INCOMPLETE_RANGES)
+
+_LIBCPP_END_NAMESPACE_STD
+
+#endif // _LIBCPP___ITERATOR_SORTABLE_H

libcxx/include/iterator

 template<class In, class Out>
   concept indirectly_movable = see below;                  // since C++20
 
 template<class In, class Out>
   concept indirectly_movable_storable = see below;         // since C++20
 
 // [alg.req.ind.copy], concept indirectly_copyable
 template<class In, class Out>
-  concept indirectly_copyable = see below;                  // since C++20
+  concept indirectly_copyable = see below;                 // since C++20
 
 template<class In, class Out>
-  concept indirectly_copyable_storable = see below;         // since C++20
+  concept indirectly_copyable_storable = see below;        // since C++20
 
 // [alg.req.ind.swap], concept indirectly_swappable
 template<class I1, class I2 = I1>
   concept indirectly_swappable = see below;                // since C++20
 
 template<class I1, class I2, class R, class P1 = identity,
          class P2 = identity>
   concept indirectly_comparable =
     indirect_binary_predicate<R, projected<I1, P1>, projected<I2, P2>>; // since C++20
 
-// [alg.req.permutable], concept permutable                // since C++20
+// [alg.req.permutable], concept permutable
 template<class I>
-  concept permutable = see below;
+  concept permutable = see below;                          // since C++20
 
  // [alg.req.mergeable], concept mergeable
 template<class I1, class I2, class Out,
     class R = ranges::less, class P1 = identity, class P2 = identity>
   concept mergeable = see below;                           // since C++20
 
+// [alg.req.sortable], concept sortable
+template<class I, class R = ranges::less, class P = identity>
+  concept sortable = see below;                            // since C++20
+
 template<input_or_output_iterator I, sentinel_for<I> S>
   requires (!same_as<I, S> && copyable<I>)
 class common_iterator;                                     // since C++20
 
 template<class Category, class T, class Distance = ptrdiff_t,
          class Pointer = T*, class Reference = T&>
 struct iterator                                            // deprecated in C++17
 {

 #include <__iterator/ostreambuf_iterator.h>
 #include <__iterator/permutable.h>
 #include <__iterator/prev.h>
 #include <__iterator/projected.h>
 #include <__iterator/readable_traits.h>
 #include <__iterator/reverse_access.h>
 #include <__iterator/reverse_iterator.h>
 #include <__iterator/size.h>
+#include <__iterator/sortable.h>
 #include <__iterator/unreachable_sentinel.h>
 #include <__iterator/wrap_iter.h>
 #include <__memory/addressof.h>
 #include <__memory/pointer_traits.h>
 #include <compare>
 #include <concepts> // Mandated by the Standard.
 #include <cstddef>
 #include <initializer_list>

libcxx/include/module.modulemap

module __iterator {
       module ostreambuf_iterator   { private header "__iterator/ostreambuf_iterator.h" }
       module permutable            { private header "__iterator/permutable.h" }
       module prev                  { private header "__iterator/prev.h" }
       module projected             { private header "__iterator/projected.h" }
       module readable_traits       { private header "__iterator/readable_traits.h" }
       module reverse_access        { private header "__iterator/reverse_access.h" }
       module reverse_iterator      { private header "__iterator/reverse_iterator.h" }
       module size                  { private header "__iterator/size.h" }
+      module sortable              { private header "__iterator/sortable.h" }
       module unreachable_sentinel  { private header "__iterator/unreachable_sentinel.h" }
       module wrap_iter             { private header "__iterator/wrap_iter.h" }
     }
   }
   module latch {
     requires cplusplus14
     header "latch"
     export *

libcxx/test/libcxx/diagnostics/detail.headers/iterator/sortable.module.verify.cpp

+//===----------------------------------------------------------------------===//
+//
+// Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.
+// See https://llvm.org/LICENSE.txt for license information.
+// SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception
+//
+//===----------------------------------------------------------------------===//
+
+// REQUIRES: modules-build
+
+// WARNING: This test was generated by 'generate_private_header_tests.py'
+// and should not be edited manually.
+
+// expected-error@*:* {{use of private header from outside its module: '__iterator/sortable.h'}}
+#include <__iterator/sortable.h>

libcxx/test/std/iterators/iterator.requirements/alg.req.permutable/permutable.compile.pass.cpp

 //===----------------------------------------------------------------------===//
 //
 // Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.
 // See https://llvm.org/LICENSE.txt for license information.
 // SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception
 //
 //===----------------------------------------------------------------------===//
 
 // UNSUPPORTED: c++03, c++11, c++14, c++17
 // UNSUPPORTED: libcpp-no-concepts
 
 // template<class I>
 //   concept permutable = see below; // Since C++20
 
 #include <iterator>
 
-#include "MoveOnly.h"
 #include "test_iterators.h"
-#include "test_macros.h"
 
 using AllConstraintsSatisfied = forward_iterator<int*>;
 static_assert( std::forward_iterator<AllConstraintsSatisfied>);
 static_assert( std::indirectly_movable_storable<AllConstraintsSatisfied, AllConstraintsSatisfied>);
 static_assert( std::indirectly_swappable<AllConstraintsSatisfied>);
 static_assert( std::permutable<AllConstraintsSatisfied>);
 
 using NotAForwardIterator = cpp20_input_iterator<int*>;

libcxx/test/std/iterators/iterator.requirements/alg.req.sortable/sortable.compile.pass.cpp

+//===----------------------------------------------------------------------===//
+//
+// Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.
+// See https://llvm.org/LICENSE.txt for license information.
+// SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception
+//
+//===----------------------------------------------------------------------===//
+
+// UNSUPPORTED: c++03, c++11, c++14, c++17
+// UNSUPPORTED: libcpp-no-concepts
+// UNSUPPORTED: libcpp-has-no-incomplete-ranges
+
+// template<class I, class R = ranges::less, class P = identity>
+//   concept sortable = see below;                            // since C++20
+
+#include <iterator>
+
+#include <functional>
+
+using CompInt = bool(*)(int, int);
+using CompDefault = std::ranges::less;
+
+using AllConstraintsSatisfied = int*;
+static_assert( std::permutable<AllConstraintsSatisfied>);
+static_assert( std::indirect_strict_weak_order<CompDefault, AllConstraintsSatisfied>);
+static_assert( std::sortable<AllConstraintsSatisfied>);
+static_assert( std::indirect_strict_weak_order<CompInt, AllConstraintsSatisfied>);
+static_assert( std::sortable<AllConstraintsSatisfied, CompInt>);
+
+struct Foo {};
+using Proj = int(*)(Foo);
+static_assert( std::permutable<Foo*>);
+static_assert(!std::indirect_strict_weak_order<CompDefault, Foo*>);
+static_assert( std::indirect_strict_weak_order<CompDefault, std::projected<Foo*, Proj>>);
+static_assert(!std::sortable<Foo*, CompDefault>);
+static_assert( std::sortable<Foo*, CompDefault, Proj>);
+static_assert(!std::indirect_strict_weak_order<CompInt, Foo*>);
+static_assert( std::indirect_strict_weak_order<CompInt, std::projected<Foo*, Proj>>);
+static_assert(!std::sortable<Foo*, CompInt>);
+static_assert( std::sortable<Foo*, CompInt, Proj>);
+
+using NotPermutable = const int*;
+static_assert(!std::permutable<NotPermutable>);
+static_assert( std::indirect_strict_weak_order<CompInt, NotPermutable>);
+static_assert(!std::sortable<NotPermutable, CompInt>);
+
+struct Empty {};
+using NoIndirectStrictWeakOrder = Empty*;
+static_assert( std::permutable<NoIndirectStrictWeakOrder>);
+static_assert(!std::indirect_strict_weak_order<CompInt, NoIndirectStrictWeakOrder>);
+static_assert(!std::sortable<NoIndirectStrictWeakOrder, CompInt>);

libcxx/test/std/iterators/iterator.requirements/alg.req.sortable/sortable.subsumption.compile.pass.cpp

+//===----------------------------------------------------------------------===//
+//
+// Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.
+// See https://llvm.org/LICENSE.txt for license information.
+// SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception
+//
+//===----------------------------------------------------------------------===//
+
+// UNSUPPORTED: c++03, c++11, c++14, c++17
+// UNSUPPORTED: libcpp-no-concepts
+// UNSUPPORTED: libcpp-has-no-incomplete-ranges
+
+// template<class I, class R = ranges::less, class P = identity>
+//   concept sortable = see below;                            // since C++20
+
+#include <iterator>
+
+#include <functional>
+
+template <class I, class R, class P> void test_subsumption() requires std::permutable<I>;
+
+template <class I, class R, class P> void test_subsumption()
+    requires std::indirect_strict_weak_order<R, std::projected<I, P>>;
+
+template <class I, class R, class P> constexpr bool test_subsumption() requires std::sortable<I, R, P> { return true; }
+
+static_assert(test_subsumption<int*, std::ranges::less, std::identity>());