[libc++][ranges] Implement `permutable`.

[var-const]

Fill in the link to the patch on the Ranges status page.

[var-const]

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

20

Please let me know if these subsumption tests aren't applicable.

[• Quuxplusone]

LGTM % nits!

libcxx/docs/Status/RangesPaper.csv

69

Could mark this "In Progress" now.

libcxx/include/__iterator/permutable.h

28–30

Perhaps 2-space indent?
Personally I'd use _Ip for the template parameter name, but whatever.

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

39

Instead of customizing iter_swap for forward_iterator, I'd prefer to see a hidden-friend swap for NonCopyable. That would still satisfy all your requirements for this test, right?

46–49

I agree with your logic. Spelling it out here doesn't seem useful, though, because it's not the form of the argument that's difficult; it's whether all of the premises are (still) factually correct. The reader has to visit cppreference to find that out, which means they're not reading your comment after the first sentence anyway.

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

20

Works for me.
I would have done a single overload set, like

template<class I> void test_subsumption() requires std::forward_iterator<I>;
template<class I> void test_subsumption() requires std::indirectly_movable_storable<I, I>;
template<class I> void test_subsumption() requires std::indirectly_swappable<I, I>;
template<class I> constexpr bool test_subsumption() requires std::permutable<I> { return true; }
static_assert(test_subsumption<int*>()); // unambiguous

but I could believe that's too "clever." Whatever you want to do here is okay, AFAIC.

[ldionne]

LGTM with comments.

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

46–49

I personally dislike "cryptic" or "clever" comments that state something without explaining it at all. It assumes that the reader will immediately understand why the statement is true.

This comment saves me time because I can read and understand the reasoning without having to work it out myself.

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

20

I think this is a shorter, more copy-pastable and generally simpler way to test for subsumption than what we seem to do elsewhere. I would encourage @var-const to use something like this.

I thought it out, and I *think* this is 100% equivalent to the tests we have right now. If I missed a difference, it might be worth pointing it out @Quuxplusone .

37

I would add a test for subsumption of forward_iterator, like you're doing for the other ones.

[var-const]

Address feedback

libcxx/include/__iterator/permutable.h

28–30

The indent width for split lines doesn't seem to be specified in the LLVM style guide, but clang-format thinks it's 4: https://github.com/llvm/llvm-project/blob/07486395d2d05c9c567994456774cafdcc1611d0/clang/lib/Format/Format.cpp#L1163
I think there is some convenience in having regular indentation differ from indentation for split lines. If you feel otherwise, let me know.

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

39

Done. Yes, I think it's better this way.

46–49

I'd prefer to keep the comment (I'm open to shortening the explanation if you have any specific suggestions). I think it would make it easier for the reader to verify my logic if they don't have to make any assumptions, and should also make cross-checking with cppreference faster.

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

20

Thanks! I like this a lot -- it's more concise and easier to copy and/or extend.

[• Quuxplusone]

libcxx/include/__iterator/permutable.h

28–30

I think there is some convenience in having regular indentation differ from indentation for split lines

Huh, I'd think the exact opposite, because the notion of what counts as "one line, split," versus "two lines," is completely fluid in C++. I don't see any logic to having 4-space indents on

concept permutable =
    x;

but only 2-space indents on

concept otherable =
  requires (T x) {
    x;
  };

I see LLVM's default style sets the various indent widths to 2 or 4 in what I would characterize as an arbitrary fashion, and maybe it's even worth nailing them all to 2 in our .clang-format.

LLVMStyle.IndentWidth = 2;
LLVMStyle.ObjCBlockIndentWidth = 2;
LLVMStyle.ConstructorInitializerIndentWidth = 4;
LLVMStyle.ContinuationIndentWidth = 4;

So, yes I feel otherwise; but not a blocker.

[var-const]

libcxx/include/__iterator/permutable.h

28–30

I don't think these values are arbitrary -- the regular indent width is 2 (not sure why Objective-C blocks have a separate setting, but it makes sense for the code within blocks to be indented by 2 just like regular functions and lambdas) and the indent width for continuations is 4 (and they treat constructor initializer lists as continuations).

but only 2-space indents on

It should be

concept otherable =
    requires (T x) {
      x;
    };

Having requires on a separate line is a continuation; however, the contents of the requires clause should be formatted as usual, even though they are within a continuation.

[var-const]

The CI failure in modular build looks unrelated (the failure is

Failed Tests (1):
  llvm-libc++-shared.cfg.in :: libcxx/selftest/dsl/dsl.sh.py

)

libcxx/docs/Status/RangesPaper.csv

 `[projected] <https://wg21.link/projected>`_,`ranges::projected <https://llvm.org/D101277>`_,[iterator.concepts],Louis Dionne,✅
 `[common.alg.req] <https://wg21.link/common.alg.req>`_: pt. 1,"| `indirectly_movable <https://llvm.org/D102639>`_
 | `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,✅
 `[common.alg.req] <https://wg21.link/common.alg.req>`_: pt. 2,`indirectly_swappable <https://llvm.org/D105304>`_,"| [iterator.concepts]
 | [iterator.cust.swap]",Zoe Carver,✅
 `[common.alg.req] <https://wg21.link/common.alg.req>`_: pt. 3,`indirectly_comparable <https://llvm.org/D116268>`_,[projected],Nikolas Klauser,✅
-`[common.alg.req] <https://wg21.link/common.alg.req>`_: pt. 4,"| permutable
+`[common.alg.req] <https://wg21.link/common.alg.req>`_: pt. 4,"| `permutable <https://llvm.org/TODO>`_
 | mergeable
 | sortable",[iterator.concepts],Unassigned,Not started
 `[std.iterator.tags] <https://wg21.link/std.iterator.tags>`_,"| `contiguous_iterator_tag <https://reviews.llvm.org/rG45d048c20440989df2b4e1be1f9343225e7741ab>`_
 | `iterator_concept specialization for pointers <https://reviews.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/iter_move.h
   __iterator/iter_swap.h
   __iterator/iterator.h
   __iterator/iterator_traits.h
   __iterator/move_iterator.h
   __iterator/next.h
   __iterator/ostream_iterator.h
   __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/unreachable_sentinel.h
   __iterator/wrap_iter.h

libcxx/include/__iterator/permutable.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_PERMUTABLE_H
+#define _LIBCPP___ITERATOR_PERMUTABLE_H
+
+#include <__config>
+#include <__iterator/concepts.h>
+#include <__iterator/iter_swap.h>
+
+#if !defined(_LIBCPP_HAS_NO_PRAGMA_SYSTEM_HEADER)
+#  pragma GCC system_header
+#endif
+
+_LIBCPP_BEGIN_NAMESPACE_STD
+
+#if !defined(_LIBCPP_HAS_NO_CONCEPTS)
+
+template <class _Iterator>
+concept permutable =
+    forward_iterator<_Iterator> &&
+    indirectly_movable_storable<_Iterator, _Iterator> &&
+    indirectly_swappable<_Iterator, _Iterator>;
+
+#endif // !defined(_LIBCPP_HAS_NO_CONCEPTS)
+
+_LIBCPP_END_NAMESPACE_STD
+
+#endif // _LIBCPP___ITERATOR_PERMUTABLE_H

libcxx/include/iterator

 
 template<class In, class Out>
   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
 
+// [alg.req.permutable], concept permutable                // since C++20
+template<class I>
+  concept permutable = see below;
+
 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

 #include <__iterator/iter_move.h>
 #include <__iterator/iter_swap.h>
 #include <__iterator/iterator.h>
 #include <__iterator/iterator_traits.h>
 #include <__iterator/move_iterator.h>
 #include <__iterator/next.h>
 #include <__iterator/ostream_iterator.h>
 #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/unreachable_sentinel.h>
 #include <__iterator/wrap_iter.h>

libcxx/include/module.modulemap

module __iterator {
       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" }
       module next                  { private header "__iterator/next.h" }
       module ostream_iterator      { private header "__iterator/ostream_iterator.h" }
       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 unreachable_sentinel  { private header "__iterator/unreachable_sentinel.h" }
       module wrap_iter             { private header "__iterator/wrap_iter.h" }

libcxx/test/libcxx/diagnostics/detail.headers/iterator/permutable.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/permutable.h'}}
+#include <__iterator/permutable.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*>;
+static_assert(!std::forward_iterator<NotAForwardIterator>);
+static_assert( std::indirectly_movable_storable<NotAForwardIterator, NotAForwardIterator>);
+static_assert( std::indirectly_swappable<NotAForwardIterator>);
+static_assert(!std::permutable<NotAForwardIterator>);
+
+struct NonCopyable {
+  NonCopyable(const NonCopyable&) = delete;
+  NonCopyable& operator=(const NonCopyable&) = delete;
+};
+using NotIMS = forward_iterator<NonCopyable*>;
+void iter_swap(const NotIMS&, const NotIMS&);
+
+static_assert( std::forward_iterator<NotIMS>);
+static_assert(!std::indirectly_movable_storable<NotIMS, NotIMS>);
+static_assert( std::indirectly_swappable<NotIMS>);
+static_assert(!std::permutable<NotIMS>);
+
+// Note: it is impossible for an iterator to satisfy `indirectly_movable_storable` but not `indirectly_swappable`:
+// `indirectly_swappable` requires both iterators to be `indirectly_readable` and for `ranges::iter_swap` to be
+// well-formed for both iterators. `indirectly_movable_storable` also requires the iterator to be `indirectly_readable`.
+// `ranges::iter_swap` is always defined for `indirectly_movable_storable` iterators.

libcxx/test/std/iterators/iterator.requirements/alg.req.permutable/permutable.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
+
+// template<class I>
+//   concept permutable = see below; // Since C++20
+
+#include <iterator>
+
+template<class I>
+  requires std::indirectly_movable_storable<I, I>
+constexpr bool subsumes_indirectly_movable_storable() {
+  return false;
+}
+
+template<class I>
+  requires std::permutable<I>
+constexpr bool subsumes_indirectly_movable_storable() {
+  return true;
+}
+
+static_assert(subsumes_indirectly_movable_storable<int*>());
+
+template<class I>
+  requires std::indirectly_swappable<I, I>
+constexpr bool subsumes_indirectly_swappable() {
+  return false;
+}
+
+template<class I>
+  requires std::permutable<I>
+constexpr bool subsumes_indirectly_swappable() {
+  return true;
+}
+
+static_assert(subsumes_indirectly_swappable<int*>());