[ADT] Add deduction guide for iterator_range

[steakhal]

I have also considered adding ADL lookup support part of this patch, but that's slightly more complicated if you want to keep the ubiquitously included iterator_range header "small", I cannot simply include STLExtras here to gain the adl_begin() and adl_end().
I have considered to basically "duplicate" the adl_begin and adl_end code, but I'm still not sure.

To do that, I'd need the type_traits header for sure for the SFINAE, which again would bloat this header. It would look something like this that way:

adl-support.patch4 KBDownload

[steakhal]

I haven't measured the impact of this on the build times.

[dblaikie]

In D152891#4420105, @steakhal wrote:

I have also considered adding ADL lookup support part of this patch, but that's slightly more complicated if you want to keep the ubiquitously included iterator_range header "small", I cannot simply include STLExtras here to gain the adl_begin() and adl_end().
I have considered to basically "duplicate" the adl_begin and adl_end code, but I'm still not sure.

I'd be more in favor of pulling adl_begin/end into a separate header and reusing it from both places, if STLExtras is too big of a dumping ground.

To do that, I'd need the type_traits header for sure for the SFINAE, which again would bloat this header. It would look something like this that way:

adl-support.patch4 KBDownload

A question would be: How many translation units include iterator_range and don't transitively include type_traits somewhere along the way anyway?

[steakhal]

• Factor out ADL utilities
• Add SFINAE check for iterator_range constructor

I measured the clean build time before and after the patch on my Ubuntu 22.04.1 system.
I used gcc (Ubuntu 11.3.0-1ubuntu1~22.04.1) 11.3.0 with the mold linker.

Baseline:

time cmake -S llvm -B build/rel-old -DLLVM_ENABLE_PROJECTS="clang;clang-tools-extra" -DCMAKE_BUILD_TYPE=Release
real    0m8.446s
user    0m6.587s
sys     0m1.691s

time ninja -C build/rel-old/
[5445/5445]
real    19m23.414s   1163.414s
user    431m9.467s
sys     18m20.037s

With this patch:

time cmake -S llvm -B build/rel-new -DLLVM_ENABLE_PROJECTS="clang;clang-tools-extra" -DCMAKE_BUILD_TYPE=Release
real    0m8.943s
user    0m6.956s
sys     0m1.818s

time ninja -C build/rel-new/
[5445/5445]
real    19m32.817s   1172.817s
user    433m30.939s
sys     18m20.295s

This means that we would have 0.808224759 % compile time regression with this patch. Is it acceptable?
(I only run the measurement once)

[steakhal]

@IncludeGuardian, I've just seen a patch about improving compile times. I have no clue how to properly measure such things.
Could you also have a look at this patch, if I can include new headers from the iterator_range header?

[dblaikie]

Seesm fine to me - measurement's probably in the noise.

[steakhal]

@asb This commit might be interesting for LLVM-weekly.

[barannikov88]

llvm/include/llvm/ADT/iterator_range.h

28

Would go in line with the standard name https://en.cppreference.com/w/cpp/types/is_convertible

[steakhal]

llvm/include/llvm/ADT/iterator_range.h

28

I tried to use the llvm's implementation (libcxx) of std::is_convertible here but it didn't work.
I managed to replace the requires with plain-old SFINAE, and make my implementation pass all the libcxx tests but still failed to compile the llvm-project after this.

About the typo, yea, my bad. I should have fixed that.
How about if we wait for some time to see if at least the bots won't find any semantic issues? After a couple of days, we can fix the typo as well. Otherwise, we would risk merge conflicts in case we need to revert this.

[barannikov88]

llvm/include/llvm/ADT/iterator_range.h

28

Yeah, sounds fine. I missed it was closed.

[steakhal]

llvm/include/llvm/ADT/iterator_range.h

28

Fixed by NFC: Fix typo explicitly_convertable -> explicitly_convertible

[mehdi_amini]

This breaks gcc build apparently: https://github.com/llvm/llvm-project/issues/63843#issuecomment-1633866756

[tahonermann]

llvm/include/llvm/ADT/iterator_range.h

49–51

Static analysis flagged this code because c is forwarded twice thereby introducing the possibility that the second callee attempts to move from a moved-from object.

In practice, this code is unlikely to be problematic because a container/range that supports moving an rvalue object into the iterator returned by its associated begin() and which has an end() that is sensitive to the identity or state of the range object would be a very strange thing indeed (I can imagine a range that models an input-range that supports moving a range object into the iterator returned by begin(), but then end() would almost certainly return a sentinel that is independent of the identity or state of the range object). Still, a double forward like this is quite strange.

There is some offline discussion happening that might result in a code review being submitted to remove one or both of the std::forward() calls.

[steakhal]

llvm/include/llvm/ADT/iterator_range.h

49–51

Makes sense. The intention was to select the right overload, but indeed, its confusing.
Submit a patch for simply removing both forwards. I don't expect constructing an iterator to suddenly consume the container anyway. It wouldn't make sense.

[andrew.w.kaylor]

llvm/include/llvm/ADT/iterator_range.h

49–51

I've uploaded D157453 to remove the std::forward.

llvm/include/llvm/ADT/ADL.h

+//===- 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 <type_traits>
+#include <iterator>
+#include <utility>
+
+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 <typename T, T> struct SameType;
+
+namespace adl_detail {
+
+using std::begin;
+
+template <typename RangeT>
+constexpr auto begin_impl(RangeT &&range)
+    -> decltype(begin(std::forward<RangeT>(range))) {
+  return begin(std::forward<RangeT>(range));
+}
+
+using std::end;
+
+template <typename RangeT>
+constexpr auto end_impl(RangeT &&range)
+    -> decltype(end(std::forward<RangeT>(range))) {
+  return end(std::forward<RangeT>(range));
+}
+
+using std::swap;
+
+template <typename T>
+constexpr void swap_impl(T &&lhs,
+                         T &&rhs) noexcept(noexcept(swap(std::declval<T>(),
+                                                         std::declval<T>()))) {
+  swap(std::forward<T>(lhs), std::forward<T>(rhs));
+}
+
+using std::size;
+
+template <typename RangeT>
+constexpr auto size_impl(RangeT &&range)
+    -> decltype(size(std::forward<RangeT>(range))) {
+  return size(std::forward<RangeT>(range));
+}
+
+} // end namespace adl_detail
+
+/// Returns the begin iterator to \p range using `std::begin` and
+/// function found through Argument-Dependent Lookup (ADL).
+template <typename RangeT>
+constexpr auto adl_begin(RangeT &&range)
+    -> decltype(adl_detail::begin_impl(std::forward<RangeT>(range))) {
+  return adl_detail::begin_impl(std::forward<RangeT>(range));
+}
+
+/// Returns the end iterator to \p range using `std::end` and
+/// functions found through Argument-Dependent Lookup (ADL).
+template <typename RangeT>
+constexpr auto adl_end(RangeT &&range)
+    -> decltype(adl_detail::end_impl(std::forward<RangeT>(range))) {
+  return adl_detail::end_impl(std::forward<RangeT>(range));
+}
+
+/// Swaps \p lhs with \p rhs using `std::swap` and functions found through
+/// Argument-Dependent Lookup (ADL).
+template <typename T>
+constexpr void adl_swap(T &&lhs, T &&rhs) noexcept(
+    noexcept(adl_detail::swap_impl(std::declval<T>(), std::declval<T>()))) {
+  adl_detail::swap_impl(std::forward<T>(lhs), std::forward<T>(rhs));
+}
+
+/// Returns the size of \p range using `std::size` and functions found through
+/// Argument-Dependent Lookup (ADL).
+template <typename RangeT>
+constexpr auto adl_size(RangeT &&range)
+    -> decltype(adl_detail::size_impl(std::forward<RangeT>(range))) {
+  return adl_detail::size_impl(std::forward<RangeT>(range));
+}
+
+namespace detail {
+
+template <typename RangeT>
+using IterOfRange = decltype(adl_begin(std::declval<RangeT &>()));
+
+template <typename RangeT>
+using ValueOfRange =
+    std::remove_reference_t<decltype(*adl_begin(std::declval<RangeT &>()))>;
+
+} // namespace detail
+} // namespace llvm
+
+#endif // LLVM_ADT_ADL_H

llvm/include/llvm/ADT/STLExtras.h

 ///
 /// No library is required when using these functions.
 ///
 //===----------------------------------------------------------------------===//
 
 #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"
 #include "llvm/ADT/identity.h"
 #include "llvm/ADT/iterator.h"
 #include "llvm/ADT/iterator_range.h"
 #include "llvm/Config/abi-breaking.h"
 #include "llvm/Support/ErrorHandling.h"

 #include <utility>
 
 #ifdef EXPENSIVE_CHECKS
 #include <random> // for std::mt19937
 #endif
 
 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 <typename T, T> struct SameType;
-
-namespace adl_detail {
-
-using std::begin;
-
-template <typename RangeT>
-constexpr auto begin_impl(RangeT &&range)
-    -> decltype(begin(std::forward<RangeT>(range))) {
-  return begin(std::forward<RangeT>(range));
-}
-
-using std::end;
-
-template <typename RangeT>
-constexpr auto end_impl(RangeT &&range)
-    -> decltype(end(std::forward<RangeT>(range))) {
-  return end(std::forward<RangeT>(range));
-}
-
-using std::swap;
-
-template <typename T>
-constexpr void swap_impl(T &&lhs,
-                         T &&rhs) noexcept(noexcept(swap(std::declval<T>(),
-                                                         std::declval<T>()))) {
-  swap(std::forward<T>(lhs), std::forward<T>(rhs));
-}
-
-using std::size;
-
-template <typename RangeT>
-constexpr auto size_impl(RangeT &&range)
-    -> decltype(size(std::forward<RangeT>(range))) {
-  return size(std::forward<RangeT>(range));
-}
-
-} // end namespace adl_detail
-
-/// Returns the begin iterator to \p range using `std::begin` and
-/// function found through Argument-Dependent Lookup (ADL).
-template <typename RangeT>
-constexpr auto adl_begin(RangeT &&range)
-    -> decltype(adl_detail::begin_impl(std::forward<RangeT>(range))) {
-  return adl_detail::begin_impl(std::forward<RangeT>(range));
-}
-
-/// Returns the end iterator to \p range using `std::end` and
-/// functions found through Argument-Dependent Lookup (ADL).
-template <typename RangeT>
-constexpr auto adl_end(RangeT &&range)
-    -> decltype(adl_detail::end_impl(std::forward<RangeT>(range))) {
-  return adl_detail::end_impl(std::forward<RangeT>(range));
-}
-
-/// Swaps \p lhs with \p rhs using `std::swap` and functions found through
-/// Argument-Dependent Lookup (ADL).
-template <typename T>
-constexpr void adl_swap(T &&lhs, T &&rhs) noexcept(
-    noexcept(adl_detail::swap_impl(std::declval<T>(), std::declval<T>()))) {
-  adl_detail::swap_impl(std::forward<T>(lhs), std::forward<T>(rhs));
-}
-
-/// Returns the size of \p range using `std::size` and functions found through
-/// Argument-Dependent Lookup (ADL).
-template <typename RangeT>
-constexpr auto adl_size(RangeT &&range)
-    -> decltype(adl_detail::size_impl(std::forward<RangeT>(range))) {
-  return adl_detail::size_impl(std::forward<RangeT>(range));
-}
-
-namespace detail {
-
-template <typename RangeT>
-using IterOfRange = decltype(adl_begin(std::declval<RangeT &>()));
-
-template <typename RangeT>
-using ValueOfRange =
-    std::remove_reference_t<decltype(*adl_begin(std::declval<RangeT &>()))>;
-
-} // end namespace detail
-
 //===----------------------------------------------------------------------===//
 //     Extra additions to <type_traits>
 //===----------------------------------------------------------------------===//
 
 template <typename T> struct make_const_ptr {
   using type = std::add_pointer_t<std::add_const_t<T>>;
 };
 

llvm/include/llvm/ADT/iterator_range.h

 /// Note that code here follows more standards-based coding conventions as it
 /// is mirroring proposed interfaces for standardization.
 ///
 //===----------------------------------------------------------------------===//
 
 #ifndef LLVM_ADT_ITERATOR_RANGE_H
 #define LLVM_ADT_ITERATOR_RANGE_H
 
+#include "llvm/ADT/ADL.h"
+#include <type_traits>
 #include <utility>
 
 namespace llvm {
 
+template <typename From, typename To, typename = void>
+struct explicitly_convertable : std::false_type {};
+
+template <typename From, typename To>
+struct explicitly_convertable<
+    From, To,
+    std::void_t<decltype(static_cast<To>(
+        std::declval<std::add_rvalue_reference_t<From>>()))>> : std::true_type {
+};
+
 /// A range adaptor for a pair of iterators.
 ///
 /// This just wraps two iterators into a range-compatible interface. Nothing
 /// fancy at all.
 template <typename IteratorT>
 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 <typename Container>
+  template <typename Container,
+            std::enable_if_t<explicitly_convertable<
+                detail::IterOfRange<Container>, 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<Container>(c))),
+        end_iterator(adl_end(std::forward<Container>(c))) {}
   iterator_range(IteratorT begin_iterator, IteratorT end_iterator)
       : begin_iterator(std::move(begin_iterator)),
         end_iterator(std::move(end_iterator)) {}
 
   IteratorT begin() const { return begin_iterator; }
   IteratorT end() const { return end_iterator; }
   bool empty() const { return begin_iterator == end_iterator; }
 };
 
+template <typename Container>
+iterator_range(Container &&) -> iterator_range<detail::IterOfRange<Container>>;
+
 /// Convenience function for iterating over sub-ranges.
 ///
 /// This provides a bit of syntactic sugar to make using sub-ranges
 /// in for loops a bit easier. Analogous to std::make_pair().
 template <class T> iterator_range<T> make_range(T x, T y) {
   return iterator_range<T>(std::move(x), std::move(y));
 }
 
 template <typename T> iterator_range<T> make_range(std::pair<T, T> p) {
   return iterator_range<T>(std::move(p.first), std::move(p.second));
 }
 
 }
 
 #endif