From ddbc7620d46f7bed51abc3eb80f51007e88e2732 Mon Sep 17 00:00:00 2001 From: Balazs Benics Date: Mon, 3 Jul 2023 09:29:37 +0200 Subject: [PATCH] [ADT] Add deduction guide for iterator_range This commit also enhances the container overload constructor so that it now considers the `begin` and `end` free functions, and performs ADL lookups to find the best match. To make this possible, I had to split-off the ADL helper functions from the STLExtras header so that the iterator_range still remains pretty cheap to include. Differential Revision: https://reviews.llvm.org/D152891 --- llvm/include/llvm/ADT/ADL.h | 103 +++++++++++++++++++++++++++++++++ llvm/include/llvm/ADT/STLExtras.h | 85 +-------------------------- llvm/include/llvm/ADT/iterator_range.h | 25 ++++++-- 3 files changed, 124 insertions(+), 89 deletions(-) create mode 100644 llvm/include/llvm/ADT/ADL.h diff --git a/llvm/include/llvm/ADT/ADL.h b/llvm/include/llvm/ADT/ADL.h new file mode 100644 index 0000000..ab1f28f --- /dev/null +++ b/llvm/include/llvm/ADT/ADL.h @@ -0,0 +1,103 @@ +//===- llvm/ADT/ADL.h - Argument dependent lookup utilities -----*- 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 LLVM_ADT_ADL_H +#define LLVM_ADT_ADL_H + +#include +#include +#include + +namespace llvm { + +// Only used by compiler if both template types are the same. Useful when +// using SFINAE to test for the existence of member functions. +template struct SameType; + +namespace adl_detail { + +using std::begin; + +template +constexpr auto begin_impl(RangeT &&range) + -> decltype(begin(std::forward(range))) { + return begin(std::forward(range)); +} + +using std::end; + +template +constexpr auto end_impl(RangeT &&range) + -> decltype(end(std::forward(range))) { + return end(std::forward(range)); +} + +using std::swap; + +template +constexpr void swap_impl(T &&lhs, + T &&rhs) noexcept(noexcept(swap(std::declval(), + std::declval()))) { + swap(std::forward(lhs), std::forward(rhs)); +} + +using std::size; + +template +constexpr auto size_impl(RangeT &&range) + -> decltype(size(std::forward(range))) { + return size(std::forward(range)); +} + +} // end namespace adl_detail + +/// Returns the begin iterator to \p range using `std::begin` and +/// function found through Argument-Dependent Lookup (ADL). +template +constexpr auto adl_begin(RangeT &&range) + -> decltype(adl_detail::begin_impl(std::forward(range))) { + return adl_detail::begin_impl(std::forward(range)); +} + +/// Returns the end iterator to \p range using `std::end` and +/// functions found through Argument-Dependent Lookup (ADL). +template +constexpr auto adl_end(RangeT &&range) + -> decltype(adl_detail::end_impl(std::forward(range))) { + return adl_detail::end_impl(std::forward(range)); +} + +/// Swaps \p lhs with \p rhs using `std::swap` and functions found through +/// Argument-Dependent Lookup (ADL). +template +constexpr void adl_swap(T &&lhs, T &&rhs) noexcept( + noexcept(adl_detail::swap_impl(std::declval(), std::declval()))) { + adl_detail::swap_impl(std::forward(lhs), std::forward(rhs)); +} + +/// Returns the size of \p range using `std::size` and functions found through +/// Argument-Dependent Lookup (ADL). +template +constexpr auto adl_size(RangeT &&range) + -> decltype(adl_detail::size_impl(std::forward(range))) { + return adl_detail::size_impl(std::forward(range)); +} + +namespace detail { + +template +using IterOfRange = decltype(adl_begin(std::declval())); + +template +using ValueOfRange = + std::remove_reference_t()))>; + +} // namespace detail +} // namespace llvm + +#endif // LLVM_ADT_ADL_H diff --git a/llvm/include/llvm/ADT/STLExtras.h b/llvm/include/llvm/ADT/STLExtras.h index 6f4c06b..7edc582 100644 --- a/llvm/include/llvm/ADT/STLExtras.h +++ b/llvm/include/llvm/ADT/STLExtras.h @@ -17,6 +17,7 @@ #ifndef LLVM_ADT_STLEXTRAS_H #define LLVM_ADT_STLEXTRAS_H +#include "llvm/ADT/ADL.h" #include "llvm/ADT/Hashing.h" #include "llvm/ADT/STLForwardCompat.h" #include "llvm/ADT/STLFunctionalExtras.h" @@ -46,90 +47,6 @@ namespace llvm { -// Only used by compiler if both template types are the same. Useful when -// using SFINAE to test for the existence of member functions. -template struct SameType; - -namespace adl_detail { - -using std::begin; - -template -constexpr auto begin_impl(RangeT &&range) - -> decltype(begin(std::forward(range))) { - return begin(std::forward(range)); -} - -using std::end; - -template -constexpr auto end_impl(RangeT &&range) - -> decltype(end(std::forward(range))) { - return end(std::forward(range)); -} - -using std::swap; - -template -constexpr void swap_impl(T &&lhs, - T &&rhs) noexcept(noexcept(swap(std::declval(), - std::declval()))) { - swap(std::forward(lhs), std::forward(rhs)); -} - -using std::size; - -template -constexpr auto size_impl(RangeT &&range) - -> decltype(size(std::forward(range))) { - return size(std::forward(range)); -} - -} // end namespace adl_detail - -/// Returns the begin iterator to \p range using `std::begin` and -/// function found through Argument-Dependent Lookup (ADL). -template -constexpr auto adl_begin(RangeT &&range) - -> decltype(adl_detail::begin_impl(std::forward(range))) { - return adl_detail::begin_impl(std::forward(range)); -} - -/// Returns the end iterator to \p range using `std::end` and -/// functions found through Argument-Dependent Lookup (ADL). -template -constexpr auto adl_end(RangeT &&range) - -> decltype(adl_detail::end_impl(std::forward(range))) { - return adl_detail::end_impl(std::forward(range)); -} - -/// Swaps \p lhs with \p rhs using `std::swap` and functions found through -/// Argument-Dependent Lookup (ADL). -template -constexpr void adl_swap(T &&lhs, T &&rhs) noexcept( - noexcept(adl_detail::swap_impl(std::declval(), std::declval()))) { - adl_detail::swap_impl(std::forward(lhs), std::forward(rhs)); -} - -/// Returns the size of \p range using `std::size` and functions found through -/// Argument-Dependent Lookup (ADL). -template -constexpr auto adl_size(RangeT &&range) - -> decltype(adl_detail::size_impl(std::forward(range))) { - return adl_detail::size_impl(std::forward(range)); -} - -namespace detail { - -template -using IterOfRange = decltype(adl_begin(std::declval())); - -template -using ValueOfRange = - std::remove_reference_t()))>; - -} // end namespace detail - //===----------------------------------------------------------------------===// // Extra additions to //===----------------------------------------------------------------------===// diff --git a/llvm/include/llvm/ADT/iterator_range.h b/llvm/include/llvm/ADT/iterator_range.h index a9b46a3..4f33a27 100644 --- a/llvm/include/llvm/ADT/iterator_range.h +++ b/llvm/include/llvm/ADT/iterator_range.h @@ -18,10 +18,22 @@ #ifndef LLVM_ADT_ITERATOR_RANGE_H #define LLVM_ADT_ITERATOR_RANGE_H +#include "llvm/ADT/ADL.h" +#include #include namespace llvm { +template +struct explicitly_convertable : std::false_type {}; + +template +struct explicitly_convertable< + From, To, + std::void_t( + std::declval>()))>> : std::true_type { +}; + /// A range adaptor for a pair of iterators. /// /// This just wraps two iterators into a range-compatible interface. Nothing @@ -31,12 +43,12 @@ class iterator_range { IteratorT begin_iterator, end_iterator; public: - //TODO: Add SFINAE to test that the Container's iterators match the range's - // iterators. - template + template , IteratorT>::value> * = nullptr> iterator_range(Container &&c) - //TODO: Consider ADL/non-member begin/end calls. - : begin_iterator(c.begin()), end_iterator(c.end()) {} + : begin_iterator(adl_begin(std::forward(c))), + end_iterator(adl_end(std::forward(c))) {} iterator_range(IteratorT begin_iterator, IteratorT end_iterator) : begin_iterator(std::move(begin_iterator)), end_iterator(std::move(end_iterator)) {} @@ -46,6 +58,9 @@ public: bool empty() const { return begin_iterator == end_iterator; } }; +template +iterator_range(Container &&) -> iterator_range>; + /// Convenience function for iterating over sub-ranges. /// /// This provides a bit of syntactic sugar to make using sub-ranges -- 2.7.4