Diff 409852

libcxx/docs/Status/RangesPaper.csv

	Show First 20 Lines • Show All 60 Lines • ▼ Show 20 Lines
	\| `indirectly_movable_storable <https://llvm.org/D102639>`_			\| `indirectly_movable_storable <https://llvm.org/D102639>`_
	\| `indirectly_copyable <https://llvm.org/D118432>`_			\| `indirectly_copyable <https://llvm.org/D118432>`_
	\| `indirectly_copyable_storable <https://llvm.org/D118432>`_",[iterator.concepts],Zoe Carver and Konstantin Varlamov,✅			\| `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]			`[alg.req] <https://wg21.link/alg.req>`_: pt. 2,`indirectly_swappable <https://llvm.org/D105304>`_,"\| [iterator.concepts]
	\| [iterator.cust.swap]",Zoe Carver,✅			\| [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. 3,`indirectly_comparable <https://llvm.org/D116268>`_,[projected],Nikolas Klauser,✅
	`[alg.req] <https://wg21.link/alg.req>`_: pt. 4,"\| `permutable <https://llvm.org/D119222>`_			`[alg.req] <https://wg21.link/alg.req>`_: pt. 4,"\| `permutable <https://llvm.org/D119222>`_
	\| `mergeable <https://llvm.org/D119489>`_			\| `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>`_			`[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_concept specialization for pointers <https://llvm.org/rG45d048c20440989df2b4e1be1f9343225e7741ab>`_
	",[iterator.traits],Eric Fiselier,✅			",[iterator.traits],Eric Fiselier,✅
	`[range.iter.ops] <https://wg21.link/range.iter.ops>`_,"\| `ranges::advance <https://llvm.org/D101922>`_			`[range.iter.ops] <https://wg21.link/range.iter.ops>`_,"\| `ranges::advance <https://llvm.org/D101922>`_
	\| `ranges::distance <https://llvm.org/D102789>`_			\| `ranges::distance <https://llvm.org/D102789>`_
	\| `ranges::next <https://llvm.org/D102563>`_			\| `ranges::next <https://llvm.org/D102563>`_
	\| `ranges::prev <https://llvm.org/D102564>`_",[iterator.concepts],Christopher Di Bella and Arthur O'Dwyer,✅			\| `ranges::prev <https://llvm.org/D102564>`_",[iterator.concepts],Christopher Di Bella and Arthur O'Dwyer,✅
	`[predef.iterators] <https://wg21.link/predef.iterators>`_,"			`[predef.iterators] <https://wg21.link/predef.iterators>`_,"
	▲ Show 20 Lines • Show All 84 Lines • Show Last 20 Lines

libcxx/include/CMakeLists.txt

Show First 20 Lines • Show All 249 Lines • ▼ Show 20 Lines	set(files
__iterator/ostreambuf_iterator.h		__iterator/ostreambuf_iterator.h
__iterator/permutable.h		__iterator/permutable.h
__iterator/prev.h		__iterator/prev.h
__iterator/projected.h		__iterator/projected.h
__iterator/readable_traits.h		__iterator/readable_traits.h
__iterator/reverse_access.h		__iterator/reverse_access.h
__iterator/reverse_iterator.h		__iterator/reverse_iterator.h
__iterator/size.h		__iterator/size.h
		__iterator/sortable.h
__iterator/unreachable_sentinel.h		__iterator/unreachable_sentinel.h
__iterator/wrap_iter.h		__iterator/wrap_iter.h
__libcpp_version		__libcpp_version
__locale		__locale
__mbstate_t.h		__mbstate_t.h
__memory/addressof.h		__memory/addressof.h
__memory/allocation_guard.h		__memory/allocation_guard.h
__memory/allocator.h		__memory/allocator.h
▲ Show 20 Lines • Show All 337 Lines • Show Last 20 Lines

libcxx/include/__iterator/sortable.h

This file was added.

				// -- 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>>;

				QuuxplusoneUnsubmitted Done Reply Inline Actions As usual, I'd prefer 2-space indents, even though clang-format disagrees. Quuxplusone: As usual, I'd prefer 2-space indents, even though clang-format disagrees.
				var-constAuthorUnsubmitted Done Reply Inline Actions 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. var-const: Thinking more about this, I can buy an argument in favor of a 2-space indent for concepts. The…
				#endif // !defined(_LIBCPP_HAS_NO_CONCEPTS) && !defined(_LIBCPP_HAS_NO_INCOMPLETE_RANGES)

				_LIBCPP_END_NAMESPACE_STD

				#endif // _LIBCPP___ITERATOR_SORTABLE_H

libcxx/include/iterator

	Show First 20 Lines • Show All 132 Lines • ▼ Show 20 Lines
	template<class In, class Out>			template<class In, class Out>
	concept indirectly_movable = see below; // since C++20			concept indirectly_movable = see below; // since C++20

	template<class In, class Out>			template<class In, class Out>
	concept indirectly_movable_storable = see below; // since C++20			concept indirectly_movable_storable = see below; // since C++20

	// [alg.req.ind.copy], concept indirectly_copyable			// [alg.req.ind.copy], concept indirectly_copyable
	template<class In, class Out>			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>			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			// [alg.req.ind.swap], concept indirectly_swappable
	template<class I1, class I2 = I1>			template<class I1, class I2 = I1>
	concept indirectly_swappable = see below; // since C++20			concept indirectly_swappable = see below; // since C++20

	template<class I1, class I2, class R, class P1 = identity,			template<class I1, class I2, class R, class P1 = identity,
	class P2 = identity>			class P2 = identity>
	concept indirectly_comparable =			concept indirectly_comparable =
	indirect_binary_predicate<R, projected<I1, P1>, projected<I2, P2>>; // since C++20			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>			template<class I>
	concept permutable = see below;			concept permutable = see below; // since C++20

	// [alg.req.mergeable], concept mergeable			// [alg.req.mergeable], concept mergeable
	template<class I1, class I2, class Out,			template<class I1, class I2, class Out,
	class R = ranges::less, class P1 = identity, class P2 = identity>			class R = ranges::less, class P1 = identity, class P2 = identity>
	concept mergeable = see below; // since C++20			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>			template<input_or_output_iterator I, sentinel_for<I> S>
	requires (!same_as<I, S> && copyable<I>)			requires (!same_as<I, S> && copyable<I>)
	class common_iterator; // since C++20			class common_iterator; // since C++20

	template<class Category, class T, class Distance = ptrdiff_t,			template<class Category, class T, class Distance = ptrdiff_t,
	class Pointer = T*, class Reference = T&>			class Pointer = T*, class Reference = T&>
	struct iterator // deprecated in C++17			struct iterator // deprecated in C++17
	{			{
	▲ Show 20 Lines • Show All 463 Lines • ▼ Show 20 Lines
	#include <__iterator/ostreambuf_iterator.h>			#include <__iterator/ostreambuf_iterator.h>
	#include <__iterator/permutable.h>			#include <__iterator/permutable.h>
	#include <__iterator/prev.h>			#include <__iterator/prev.h>
	#include <__iterator/projected.h>			#include <__iterator/projected.h>
	#include <__iterator/readable_traits.h>			#include <__iterator/readable_traits.h>
	#include <__iterator/reverse_access.h>			#include <__iterator/reverse_access.h>
	#include <__iterator/reverse_iterator.h>			#include <__iterator/reverse_iterator.h>
	#include <__iterator/size.h>			#include <__iterator/size.h>
				#include <__iterator/sortable.h>
	#include <__iterator/unreachable_sentinel.h>			#include <__iterator/unreachable_sentinel.h>
	#include <__iterator/wrap_iter.h>			#include <__iterator/wrap_iter.h>
	#include <__memory/addressof.h>			#include <__memory/addressof.h>
	#include <__memory/pointer_traits.h>			#include <__memory/pointer_traits.h>
	#include <compare>			#include <compare>
	#include <concepts> // Mandated by the Standard.			#include <concepts> // Mandated by the Standard.
	#include <cstddef>			#include <cstddef>
	#include <initializer_list>			#include <initializer_list>
	Show All 22 Lines

libcxx/include/module.modulemap

Show First 20 Lines • Show All 634 Lines • ▼ Show 20 Lines	module __iterator {
module ostreambuf_iterator { private header "__iterator/ostreambuf_iterator.h" }		module ostreambuf_iterator { private header "__iterator/ostreambuf_iterator.h" }
module permutable { private header "__iterator/permutable.h" }		module permutable { private header "__iterator/permutable.h" }
module prev { private header "__iterator/prev.h" }		module prev { private header "__iterator/prev.h" }
module projected { private header "__iterator/projected.h" }		module projected { private header "__iterator/projected.h" }
module readable_traits { private header "__iterator/readable_traits.h" }		module readable_traits { private header "__iterator/readable_traits.h" }
module reverse_access { private header "__iterator/reverse_access.h" }		module reverse_access { private header "__iterator/reverse_access.h" }
module reverse_iterator { private header "__iterator/reverse_iterator.h" }		module reverse_iterator { private header "__iterator/reverse_iterator.h" }
module size { private header "__iterator/size.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 unreachable_sentinel { private header "__iterator/unreachable_sentinel.h" }
module wrap_iter { private header "__iterator/wrap_iter.h" }		module wrap_iter { private header "__iterator/wrap_iter.h" }
}		}
}		}
module latch {		module latch {
requires cplusplus14		requires cplusplus14
header "latch"		header "latch"
export *		export *
▲ Show 20 Lines • Show All 452 Lines • Show Last 20 Lines

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

This file was added.

				//===----------------------------------------------------------------------===//
				//
				// 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.			// Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.
	// See https://llvm.org/LICENSE.txt for license information.			// See https://llvm.org/LICENSE.txt for license information.
	// SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception			// SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception
	//			//
	//===----------------------------------------------------------------------===//			//===----------------------------------------------------------------------===//

	// UNSUPPORTED: c++03, c++11, c++14, c++17			// UNSUPPORTED: c++03, c++11, c++14, c++17
	// UNSUPPORTED: libcpp-no-concepts			// UNSUPPORTED: libcpp-no-concepts

	// template<class I>			// template<class I>
	// concept permutable = see below; // Since C++20			// concept permutable = see below; // Since C++20

	#include <iterator>			#include <iterator>

	#include "MoveOnly.h"
	#include "test_iterators.h"			#include "test_iterators.h"
	#include "test_macros.h"

	using AllConstraintsSatisfied = forward_iterator<int*>;			using AllConstraintsSatisfied = forward_iterator<int*>;
	static_assert( std::forward_iterator<AllConstraintsSatisfied>);			static_assert( std::forward_iterator<AllConstraintsSatisfied>);
	static_assert( std::indirectly_movable_storable<AllConstraintsSatisfied, AllConstraintsSatisfied>);			static_assert( std::indirectly_movable_storable<AllConstraintsSatisfied, AllConstraintsSatisfied>);
	static_assert( std::indirectly_swappable<AllConstraintsSatisfied>);			static_assert( std::indirectly_swappable<AllConstraintsSatisfied>);
	static_assert( std::permutable<AllConstraintsSatisfied>);			static_assert( std::permutable<AllConstraintsSatisfied>);

	using NotAForwardIterator = cpp20_input_iterator<int*>;			using NotAForwardIterator = cpp20_input_iterator<int*>;
	Show All 21 Lines

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

This file was added.

				//===----------------------------------------------------------------------===//
				//
				// 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>
				QuuxplusoneUnsubmitted Done Reply Inline Actions `#include <functional>` for `ranges::less` (which I guess isn't used right now, but probably should be) Quuxplusone: `#include <functional>` for `ranges::less` (which I guess isn't used right now, but probably…

				#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>);
				ldionneUnsubmitted Done Reply Inline Actions 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`. ldionne: You seem to be missing coverage for passing a projection. I think this also means you won't be…

				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>>);
				QuuxplusoneUnsubmitted Done Reply Inline Actions 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. Quuxplusone: It occurs to me that you're missing tests for when `_Comp` is not `ranges::less` and/or `_Proj`…
				var-constAuthorUnsubmitted Done Reply Inline Actions Should be fixed, PTAL. var-const: Should be fixed, PTAL.
				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>);
				QuuxplusoneUnsubmitted Done Reply Inline Actions I think it would be useful (in the sense of self-documentation) to add static_assert(!std::sortable<Foo, CompInt>); Quuxplusone:* I think it would be useful (in the sense of self-documentation) to add ``` static_assert(!std…
				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

This file was added.

				//===----------------------------------------------------------------------===//
				//
				// 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>());

This is an archive of the discontinued LLVM Phabricator instance.

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

Details

Diff Detail

Event Timeline

Revision Contents

Diff 409852

libcxx/docs/Status/RangesPaper.csv

libcxx/include/CMakeLists.txt

libcxx/include/__iterator/sortable.h

libcxx/include/iterator

libcxx/include/module.modulemap

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

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

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

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

This is an archive of the discontinued LLVM Phabricator instance.

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

Details

Diff Detail

Event Timeline

Revision Contents

Diff 409852

libcxx/docs/Status/RangesPaper.csv

libcxx/include/CMakeLists.txt

libcxx/include/__iterator/sortable.h

libcxx/include/iterator

libcxx/include/module.modulemap

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

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

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

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

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