[libc++][ranges] Add indirectly_comparable concept

[philnik]

Summary

Add indirectly_comparable concept

[philnik]

• Updated synopsis

[• Quuxplusone]

🎄😄

libcxx/include/__iterator/iter_swap.h

102–103 ↗

(On Diff #396156)

This code looks fine, but why on earth is it in iter_swap.h?
It should be in __iterator/concepts.h, or (because I think that would create a cycle) just put it in __iterator/indirectly_comparable.h.

Somewhat tangential query: Is this the last of the <iterator> concepts? or are we still missing some?

libcxx/test/std/iterators/iterator.requirements/indirectcallable/indirectinvocable/indirectly_comparable.compile.pass.cpp

19–20

Direct inclusion of <__iterator/readable_traits.h> will fail the modules build.
I've never seen libcxx/test/support/indirectly_readable.h before but it looks crazy complicated; can we avoid using it here? I think all you actually need for this test would be something like

struct Deref {
    int operator()(int*) const;
};

static_assert(!std::indirectly_comparable<int, int, std::less<int>>);  // not dereferenceable
static_assert(!std::indirectly_comparable<int*, int*, int>);  // not a predicate
static_assert( std::indirectly_comparable<int*, int*, std::less<int>>);
static_assert(!std::indirectly_comparable<int**, int*, std::less<int>>);
static_assert( std::indirectly_comparable<int**, int*, std::less<int>, Deref>);
static_assert(!std::indirectly_comparable<int**, int*, std::less<int>, Deref, Deref>);
static_assert(!std::indirectly_comparable<int**, int*, std::less<int>, std::identity, Deref>);
static_assert( std::indirectly_comparable<int*, int**, std::less<int>, std::identity, Deref>);

And then a subsumption test in each direction:

template<class F> requires std::indirectly_comparable<int*, char*, F> && true
constexpr bool subsumes(F f) { return true; }

template<class F> requires std::indirect_binary_predicate<F, std::projected<int*, std::identity>, std::projected<char*, std::identity>>
void subsumes(F f);

template<class F> requires std::indirect_binary_predicate<F, std::projected<int*, std::identity>, std::projected<char*, std::identity>> && true
constexpr bool is_subsumed(F f) { return true; }

template<class F> requires std::indirectly_comparable<int*, char*, F>
void is_subsumed(F f);

static_assert(subsumes(std::less<int>()));
static_assert(is_subsumed(std::less<int>()));

https://godbolt.org/z/c9rEh8e8c

[philnik]

• Updated test
• Moved indirectly_comparable into its own header

[philnik]

libcxx/include/__iterator/iter_swap.h

102–103 ↗

(On Diff #396156)

There are at least permutable, mergable and sortable missing, probably more.

libcxx/test/std/iterators/iterator.requirements/indirectcallable/indirectinvocable/indirectly_comparable.compile.pass.cpp

19–20

Why does it make a difference if there is the && true at the end? Is there some "this has more requirements, so it must be stricter"?

[• Quuxplusone]

libcxx/test/std/iterators/iterator.requirements/indirectcallable/indirectinvocable/indirectly_comparable.compile.pass.cpp

19–20

Yep. See circa 20m–35m in my "Concepts As She Is Spoke" (CppCon 2018). The idea here is that subsumes #2 is constrained by a bunch of stuff, and then subsumes #1 is constrained by all that same stuff plus one additional atomic constraint of "true (line 1, column 73)." So subsumes #1 is strictly more constrained.

Note that Concepts does not treat the keywords true and false as magic.

FWIW, I find the linebreak positions on lines 30–31 and 39–40 to be weird. Doesn't really matter, though.

[• Quuxplusone]

LGTM % comments

libcxx/include/__iterator/indirectly_comparable.h

23

libcxx/include/__iterator/iter_swap.h

17 ↗

(On Diff #396212)

These two includes can vanish again.

[Mordante]

LGTM modulo some nits. Make sure it passes the CI before committing. (I know the CI isn't working at the moment.)

libcxx/docs/Status/RangesPaper.csv

66

Maybe update the name ;-)

libcxx/include/module.modulemap

597

I don't see the generated test for this header.

libcxx/test/std/iterators/iterator.requirements/indirectcallable/indirectinvocable/indirectly_comparable.compile.pass.cpp

22

Is there a reason not to include static_assert(!std::indirectly_comparable<int, int, std::less<int>>); // not dereferenceable?
I would like to see the suggested comment copied.

32

I think this can use comment, it looks like magic. (And yes I read the reason for it above.)

[• Quuxplusone]

libcxx/test/std/iterators/iterator.requirements/indirectcallable/indirectinvocable/indirectly_comparable.compile.pass.cpp

22

+1, also the one before it:

static_assert(!std::indirectly_comparable<int, int, std::less<int>>);  // not dereferenceable
static_assert(!std::indirectly_comparable<int*, int*, int>);  // not a predicate

FYI I'm not married to those specific code comments. I put them because I thought otherwise it was a little subtle (particularly because these are the first couple of lines, where the reader is still getting a handle on what we're doing here). After the first two lines, the "not a..." explanations get really complicated to explain, plus the reader should have gained a little experience decoding the earlier lines, so I figured comments were more pain than gain at that point.

[philnik]

• Updated name
• Added line-break
• Removed headers
• Added header test
• Added missing assertions
• Added comment

libcxx/test/std/iterators/iterator.requirements/indirectcallable/indirectinvocable/indirectly_comparable.compile.pass.cpp

22

The reason is that they are not in the godbolt link and I copied the code from there :).

[Mordante]

Thanks for the update.

[philnik]

Rebased to trigger CI

[philnik]

Why is the CI failing? I ran all the generator scripts, but it didn't change anything.

[• Quuxplusone]

In D116268#3218468, @philnik wrote:

Why is the CI failing? I ran all the generator scripts, but it didn't change anything.

https://buildkite.com/llvm-project/libcxx-ci/builds/7566#fbd04c3f-dcc1-45dd-993c-a9fd09735bdf says:

+ grep -rn '[^ -~]' libcxx/include/
libcxx/include/iterator:145:  concept indirectly_­comparable =
libcxx/include/iterator:146:    indirect_­binary_­predicate<R, projected<I1, P1>, projected<I2, P2>>; // since C++20

This means there's some non-ASCII character in there (on each of those lines). If you copied from eel.is, it's probably a zero-width space character in the vicinity of one of the underscores. A sufficiently dumb text editor will be able to show you exactly where.

[philnik]

• Removed whitespaces

[philnik]

• Include <__iterator/concepts.h>

[philnik]

• Include <functional> in test

libcxx/docs/Status/RangesPaper.csv

 | `indirectly_strict_weak_order <https://llvm.org/D101277>`_",[readable.traits],Louis Dionne,✅
 `[projected] <http://wg21.link/projected>`_,`ranges::projected <https://llvm.org/D101277>`_,[iterator.concepts],Louis Dionne,✅
 `[common.alg.req] <http://wg21.link/common.alg.req>`_: pt. 1,"| `indirectly_movable <https://llvm.org/D102639>`_
 | `indirectly_movable_storable <https://llvm.org/D102639>`_
 | indirectly_copyable
 | indirectly_copyable_storable",[iterator.concepts],Zoe Carver,In progress
 [common.alg.req]: pt. 2,indirectly_swappable,"| [iterator.concepts]
 | [iterator.cust.swap]",Zoe Carver,✅
-[common.alg.req]: pt. 3,indirectly_comparable,[projected],Louis Dionne,Not started
+[common.alg.req]: pt. 3,indirectly_comparable,[projected],Nikolas Klauser,✅
 [common.alg.req]: pt. 4,"| permutable
 | mergeable
 | sortable",[iterator.concepts],Unassigned,Not started
 [std.iterator.tags],,[iterator.traits],Unassigned,Not started
 `[range.iter.ops] <http://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,In progress

libcxx/include/CMakeLists.txt

set(files
   __iterator/counted_iterator.h
   __iterator/data.h
   __iterator/default_sentinel.h
   __iterator/distance.h
   __iterator/empty.h
   __iterator/erase_if_container.h
   __iterator/front_insert_iterator.h
   __iterator/incrementable_traits.h
+  __iterator/indirectly_comparable.h
   __iterator/insert_iterator.h
   __iterator/istream_iterator.h
   __iterator/istreambuf_iterator.h
   __iterator/iter_move.h
   __iterator/iter_swap.h
   __iterator/iterator_traits.h
   __iterator/iterator.h
   __iterator/move_iterator.h

libcxx/include/__iterator/indirectly_comparable.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_INDIRECTLY_COMPARABLE_H
+#define _LIBCPP___ITERATOR_INDIRECTLY_COMPARABLE_H
+
+#include <__config>
+#include <__functional/identity.h>
+#include <__iterator/concepts.h>
+#include <__iterator/projected.h>
+
+_LIBCPP_BEGIN_NAMESPACE_STD
+
+#ifndef _LIBCPP_HAS_NO_RANGES
+
+template <class _I1, class _I2, class _Rp, class _P1 = identity, class _P2 = identity>
+concept indirectly_comparable =
+  indirect_binary_predicate<_Rp, projected<_I1, _P1>, projected<_I2, _P2>>;
+
+#endif // _LIBCPP_HAS_NO_RANGES
+
+_LIBCPP_END_NAMESPACE_STD
+
+#endif // _LIBCPP___ITERATOR_INDIRECTLY_COMPARABLE_H

libcxx/include/iterator

 
 template<class In, class Out>
   concept indirectly_movable_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
+
 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/counted_iterator.h>
 #include <__iterator/data.h>
 #include <__iterator/default_sentinel.h>
 #include <__iterator/distance.h>
 #include <__iterator/empty.h>
 #include <__iterator/erase_if_container.h>
 #include <__iterator/front_insert_iterator.h>
 #include <__iterator/incrementable_traits.h>
+#include <__iterator/indirectly_comparable.h>
 #include <__iterator/insert_iterator.h>
 #include <__iterator/istreambuf_iterator.h>
 #include <__iterator/istream_iterator.h>
 #include <__iterator/iterator.h>
 #include <__iterator/iterator_traits.h>
 #include <__iterator/iter_move.h>
 #include <__iterator/iter_swap.h>
 #include <__iterator/move_iterator.h>

libcxx/include/module.modulemap

module __iterator {
       module counted_iterator      { private header "__iterator/counted_iterator.h" }
       module data                  { private header "__iterator/data.h" }
       module default_sentinel      { private header "__iterator/default_sentinel.h" }
       module distance              { private header "__iterator/distance.h" }
       module empty                 { private header "__iterator/empty.h" }
       module erase_if_container    { private header "__iterator/erase_if_container.h" }
       module front_insert_iterator { private header "__iterator/front_insert_iterator.h" }
       module incrementable_traits  { private header "__iterator/incrementable_traits.h" }
+      module indirectly_comparable { private header "__iterator/indirectly_comparable.h" }
       module insert_iterator       { private header "__iterator/insert_iterator.h" }
       module istream_iterator      { private header "__iterator/istream_iterator.h" }
       module istreambuf_iterator   { private header "__iterator/istreambuf_iterator.h" }
       module iter_move             { private header "__iterator/iter_move.h" }
       module iter_swap             { private header "__iterator/iter_swap.h" }
       module iterator              { private header "__iterator/iterator.h" }
       module iterator_traits       { private header "__iterator/iterator_traits.h" }
       module move_iterator         { private header "__iterator/move_iterator.h" }

libcxx/test/libcxx/diagnostics/detail.headers/iterator/indirectly_comparable.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/indirectly_comparable.h'}}
+#include <__iterator/indirectly_comparable.h>

libcxx/test/std/iterators/iterator.requirements/indirectcallable/indirectinvocable/indirectly_comparable.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 I1, class I2, class R, class P1, class P2>
+// concept indirectly_­comparable;
+
+#include <functional>
+#include <iterator>
+#include <type_traits>
+
+struct Deref {
+    int operator()(int*) const;
+};
+
+static_assert(!std::indirectly_comparable<int, int, std::less<int>>);  // not dereferenceable
+static_assert(!std::indirectly_comparable<int*, int*, int>);  // not a predicate
+static_assert( std::indirectly_comparable<int*, int*, std::less<int>>);
+static_assert(!std::indirectly_comparable<int**, int*, std::less<int>>);
+static_assert( std::indirectly_comparable<int**, int*, std::less<int>, Deref>);
+static_assert(!std::indirectly_comparable<int**, int*, std::less<int>, Deref, Deref>);
+static_assert(!std::indirectly_comparable<int**, int*, std::less<int>, std::identity, Deref>);
+static_assert( std::indirectly_comparable<int*, int**, std::less<int>, std::identity, Deref>);
+
+template<class F>
+  requires std::indirectly_comparable<int*, char*, F>
+           && true // This true is an additional atomic constraint as a tie breaker
+constexpr bool subsumes(F) { return true; }
+
+template<class F>
+  requires std::indirect_binary_predicate<F, std::projected<int*, std::identity>, std::projected<char*, std::identity>>
+void subsumes(F);
+
+template<class F>
+  requires std::indirect_binary_predicate<F, std::projected<int*, std::identity>, std::projected<char*, std::identity>>
+           && true // This true is an additional atomic constraint as a tie breaker
+constexpr bool is_subsumed(F) { return true; }
+
+template<class F>
+  requires std::indirectly_comparable<int*, char*, F>
+void is_subsumed(F);
+
+static_assert(subsumes(std::less<int>()));
+static_assert(is_subsumed(std::less<int>()));