[ADT] Make mapped_iterator copy assignable

[jplayer-nv]

Summary

As mentioned in https://discourse.llvm.org/t/rfc-extend-ranges-infrastructure-to-better-match-c-20/65377

Lambda objects are not copy assignable, and therefore neither are iterator types which hold a lambda. STL code require iterators be copy assignable. Users may not use mapped_iterator with a std::deque for example: https://godbolt.org/z/4Px7odEEd

This blog post explains the problem and solution. We define a wrapper class to store callable objects with two specialization.

1. Specialization for non-function types
   • Use a std::optional as storage for non-function callable.
   • Define operator=() implementation(s) which use std::optional::emplace() instead of the assignment operator.
2. Specialization for function types
   • Store as a pointer (even if template argument is a function reference).
   • Default construct pointer to nullptr.

This Callable wrapper class is now default constructible (with invalid state) and copy/move assignable.

With these new properties available on the callable object, mapped_iterator can define a default constructor as well.

[jplayer-nv]

Thanks for the review @kazu

I don't have commit access, would you please shepherd the change? I rebased locally and ran testing today (all pass). Thanks again!

[jplayer-nv]

Ping @kazu for commit. If you're not the right person to ask, could you kindly suggest someone else?

[kazu]

In D134675#3881276, @jplayer-nv wrote:

Ping @kazu for commit. If you're not the right person to ask, could you kindly suggest someone else?

Sorry for the delay. I am working on committing this patch. What author name and email address should I use?

[jplayer-nv]

Thanks @kazu

Author name = James Player
Email = [e-mail]

[nickdesaulniers]

llvm/unittests/ADT/MappedIteratorTest.cpp

177

When I configure with -DLLVM_ENABLE_EXPENSIVE_CHECKS=ON, build this test with ninja ADTTests then run this, I get the following crash from this statement:

/usr/lib/gcc/x86_64-linux-gnu/12/../../../../include/c++/12/debug/safe_iterator.h:472:
In function:
    bool gnu_debug::operator==(const _Self &, const _Self &)

Error: attempt to compare a singular iterator to a 
dereferenceable (start-of-sequence) iterator.

Objects involved in the operation:
    iterator "lhs" @ 0x7ffcc2f77420 {
      state = singular;
    }
    iterator "rhs" @ 0x7ffcc2f77450 {
      state = dereferenceable (start-of-sequence);
      references sequence @ 0x7ffcc2f772f0
    }

Any ideas how best to fix this?

[jplayer-nv]

llvm/unittests/ADT/MappedIteratorTest.cpp

177

I think this line is a mistake. It should be:

EXPECT_EQ(I3, I1);

The test is currently reading a moved-from object (I2).

llvm/include/llvm/ADT/STLExtras.h

 #include <cstddef>
 #include <cstdint>
 #include <cstdlib>
 #include <functional>
 #include <initializer_list>
 #include <iterator>
 #include <limits>
 #include <memory>
+#include <optional>
 #include <tuple>
 #include <type_traits>
 #include <utility>
 
 #ifdef EXPENSIVE_CHECKS
 #include <random> // for std::mt19937
 #endif
 

 constexpr auto addEnumValues(EnumTy1 LHS, EnumTy2 RHS) {
   return static_cast<UT1>(LHS) + static_cast<UT2>(RHS);
 }
 
 //===----------------------------------------------------------------------===//
 //     Extra additions to <iterator>
 //===----------------------------------------------------------------------===//
 
+namespace callable_detail {
+
+/// Templated storage wrapper for a callable.
+///
+/// This class is consistently default constructible, copy / move
+/// constructible / assignable.
+///
+/// Supported callable types:
+///  - Function pointer
+///  - Function reference
+///  - Lambda
+///  - Function object
+template <typename T,
+          bool = std::is_function_v<std::remove_pointer_t<remove_cvref_t<T>>>>
+class Callable {
+  using value_type = std::remove_reference_t<T>;
+  using reference = value_type &;
+  using const_reference = value_type const &;
+
+  std::optional<value_type> Obj;
+
+  static_assert(!std::is_pointer_v<value_type>,
+                "Pointers to non-functions are not callable.");
+
+public:
+  Callable() = default;
+  Callable(T const &O) : Obj(std::in_place, O) {}
+
+  Callable(Callable const &Other) = default;
+  Callable(Callable &&Other) = default;
+
+  Callable &operator=(Callable const &Other) {
+    Obj = std::nullopt;
+    if (Other.Obj)
+      Obj.emplace(*Other.Obj);
+    return *this;
+  }
+
+  Callable &operator=(Callable &&Other) {
+    Obj = std::nullopt;
+    if (Other.Obj)
+      Obj.emplace(std::move(*Other.Obj));
+    return *this;
+  }
+
+  template <typename... Pn,
+            std::enable_if_t<std::is_invocable_v<T, Pn...>, int> = 0>
+  decltype(auto) operator()(Pn &&...Params) {
+    return (*Obj)(std::forward<Pn>(Params)...);
+  }
+
+  template <typename... Pn,
+            std::enable_if_t<std::is_invocable_v<T const, Pn...>, int> = 0>
+  decltype(auto) operator()(Pn &&...Params) const {
+    return (*Obj)(std::forward<Pn>(Params)...);
+  }
+
+  bool valid() const { return Obj != std::nullopt; }
+  bool reset() { return Obj = std::nullopt; }
+
+  operator reference() { return *Obj; }
+  operator const_reference() const { return *Obj; }
+};
+
+// Function specialization.  No need to waste extra space wrapping with a
+// std::optional.
+template <typename T> class Callable<T, true> {
+  static constexpr bool IsPtr = std::is_pointer_v<remove_cvref_t<T>>;
+
+  using StorageT = std::conditional_t<IsPtr, T, std::remove_reference_t<T> *>;
+  using CastT = std::conditional_t<IsPtr, T, T &>;
+
+private:
+  StorageT Func = nullptr;
+
+private:
+  template <typename In> static constexpr auto convertIn(In &&I) {
+    if constexpr (IsPtr) {
+      // Pointer... just echo it back.
+      return I;
+    } else {
+      // Must be a function reference.  Return its address.
+      return &I;
+    }
+  }
+
+public:
+  Callable() = default;
+
+  // Construct from a function pointer or reference.
+  //
+  // Disable this constructor for references to 'Callable' so we don't violate
+  // the rule of 0.
+  template < // clang-format off
+    typename FnPtrOrRef,
+    std::enable_if_t<
+      !std::is_same_v<remove_cvref_t<FnPtrOrRef>, Callable>, int
+    > = 0
+  > // clang-format on
+  Callable(FnPtrOrRef &&F) : Func(convertIn(F)) {}
+
+  template <typename... Pn,
+            std::enable_if_t<std::is_invocable_v<T, Pn...>, int> = 0>
+  decltype(auto) operator()(Pn &&...Params) const {
+    return Func(std::forward<Pn>(Params)...);
+  }
+
+  bool valid() const { return Func != nullptr; }
+  void reset() { Func = nullptr; }
+
+  operator T const &() const {
+    if constexpr (IsPtr) {
+      // T is a pointer... just echo it back.
+      return Func;
+    } else {
+      static_assert(std::is_reference_v<T>,
+                    "Expected a reference to a function.");
+      // T is a function reference... dereference the stored pointer.
+      return *Func;
+    }
+  }
+};
+
+} // namespace callable_detail
+
 namespace adl_detail {
 
 using std::begin;
 
 template <typename ContainerTy>
 decltype(auto) adl_begin(ContainerTy &&container) {
   return begin(std::forward<ContainerTy>(container));
 }

 class mapped_iterator
     : public iterator_adaptor_base<
           mapped_iterator<ItTy, FuncTy>, ItTy,
           typename std::iterator_traits<ItTy>::iterator_category,
           std::remove_reference_t<ReferenceTy>,
           typename std::iterator_traits<ItTy>::difference_type,
           std::remove_reference_t<ReferenceTy> *, ReferenceTy> {
 public:
+  mapped_iterator() = default;
   mapped_iterator(ItTy U, FuncTy F)
     : mapped_iterator::iterator_adaptor_base(std::move(U)), F(std::move(F)) {}
 
   ItTy getCurrent() { return this->I; }
 
   const FuncTy &getFunction() const { return F; }
 
   ReferenceTy operator*() const { return F(*this->I); }
 
 private:
-  FuncTy F;
+  callable_detail::Callable<FuncTy> F{};
 };
 
 // map_iterator - Provide a convenient way to create mapped_iterators, just like
 // make_pair is useful for creating pairs...
 template <class ItTy, class FuncTy>
 inline mapped_iterator<ItTy, FuncTy> map_iterator(ItTy I, FuncTy F) {
   return mapped_iterator<ItTy, FuncTy>(std::move(I), std::move(F));
 }

llvm/unittests/ADT/MappedIteratorTest.cpp

 //===------ MappedIteratorTest.cpp - Unit tests for mapped_iterator -------===//
 //
 // 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
 //
 //===----------------------------------------------------------------------===//
 
 #include "llvm/ADT/STLExtras.h"
 #include "gtest/gtest.h"
 
 using namespace llvm;
 
 namespace {
 
-TEST(MappedIteratorTest, ApplyFunctionOnDereference) {
+template <typename T> class MappedIteratorTestBasic : public testing::Test {};
+
+struct Plus1Lambda {
+  auto operator()() const {
+    return [](int X) { return X + 1; };
+  }
+};
+
+struct Plus1LambdaWithCapture {
+  const int One = 1;
+
+  auto operator()() const {
+    return [=](int X) { return X + One; };
+  }
+};
+
+struct Plus1FunctionRef {
+  static int plus1(int X) { return X + 1; }
+
+  using FuncT = int (&)(int);
+
+  FuncT operator()() const { return *plus1; }
+};
+
+struct Plus1FunctionPtr {
+  static int plus1(int X) { return X + 1; }
+
+  using FuncT = int (*)(int);
+
+  FuncT operator()() const { return plus1; }
+};
+
+struct Plus1Functor {
+  struct Plus1 {
+    int operator()(int X) const { return X + 1; }
+  };
+
+  auto operator()() const { return Plus1(); }
+};
+
+struct Plus1FunctorNotDefaultConstructible {
+  class PlusN {
+    const int N;
+
+  public:
+    PlusN(int NArg) : N(NArg) {}
+
+    int operator()(int X) const { return X + N; }
+  };
+
+  auto operator()() const { return PlusN(1); }
+};
+
+// clang-format off
+using FunctionTypes =
+  ::testing::Types<
+    Plus1Lambda,
+    Plus1LambdaWithCapture,
+    Plus1FunctionRef,
+    Plus1FunctionPtr,
+    Plus1Functor,
+    Plus1FunctorNotDefaultConstructible
+  >;
+// clang-format on
+
+TYPED_TEST_SUITE(MappedIteratorTestBasic, FunctionTypes, );
+
+template <typename T> using GetFuncT = decltype(std::declval<T>().operator()());
+
+TYPED_TEST(MappedIteratorTestBasic, DefaultConstruct) {
+  using FuncT = GetFuncT<TypeParam>;
+  using IterT = mapped_iterator<typename std::vector<int>::iterator, FuncT>;
+  TypeParam GetCallable;
+
+  auto Func = GetCallable();
+  (void)Func;
+  constexpr bool DefaultConstruct =
+      std::is_default_constructible_v<callable_detail::Callable<FuncT>>;
+  EXPECT_TRUE(DefaultConstruct);
+  EXPECT_TRUE(std::is_default_constructible_v<IterT>);
+
+  if constexpr (std::is_default_constructible_v<IterT>) {
+    IterT I;
+    (void)I;
+  }
+}
+
+TYPED_TEST(MappedIteratorTestBasic, CopyConstruct) {
+  std::vector<int> V({0});
+
+  using FuncT = GetFuncT<TypeParam>;
+  using IterT = mapped_iterator<decltype(V)::iterator, FuncT>;
+
+  EXPECT_TRUE(std::is_copy_constructible_v<IterT>);
+
+  if constexpr (std::is_copy_constructible_v<IterT>) {
+    TypeParam GetCallable;
+
+    IterT I1(V.begin(), GetCallable());
+    IterT I2(I1);
+
+    EXPECT_EQ(I2, I1) << "copy constructed iterator is a different position";
+  }
+}
+
+TYPED_TEST(MappedIteratorTestBasic, MoveConstruct) {
+  std::vector<int> V({0});
+
+  using FuncT = GetFuncT<TypeParam>;
+  using IterT = mapped_iterator<decltype(V)::iterator, FuncT>;
+
+  EXPECT_TRUE(std::is_move_constructible_v<IterT>);
+
+  if constexpr (std::is_move_constructible_v<IterT>) {
+    TypeParam GetCallable;
+
+    IterT I1(V.begin(), GetCallable());
+    IterT I2(V.begin(), GetCallable());
+    IterT I3(std::move(I2));
+
+    EXPECT_EQ(I3, I1) << "move constructed iterator is a different position";
+  }
+}
+
+TYPED_TEST(MappedIteratorTestBasic, CopyAssign) {
+  std::vector<int> V({0});
+
+  using FuncT = GetFuncT<TypeParam>;
+  using IterT = mapped_iterator<decltype(V)::iterator, FuncT>;
+
+  EXPECT_TRUE(std::is_copy_assignable_v<IterT>);
+
+  if constexpr (std::is_copy_assignable_v<IterT>) {
+    TypeParam GetCallable;
+
+    IterT I1(V.begin(), GetCallable());
+    IterT I2(V.end(), GetCallable());
+
+    I2 = I1;
+
+    EXPECT_EQ(I2, I1) << "copy assigned iterator is a different position";
+  }
+}
+
+TYPED_TEST(MappedIteratorTestBasic, MoveAssign) {
+  std::vector<int> V({0});
+
+  using FuncT = GetFuncT<TypeParam>;
+  using IterT = mapped_iterator<decltype(V)::iterator, FuncT>;
+
+  EXPECT_TRUE(std::is_move_assignable_v<IterT>);
+
+  if constexpr (std::is_move_assignable_v<IterT>) {
+    TypeParam GetCallable;
+
+    IterT I1(V.begin(), GetCallable());
+    IterT I2(V.begin(), GetCallable());
+    IterT I3(V.end(), GetCallable());
+
+    I3 = std::move(I2);
+
+    EXPECT_EQ(I2, I1) << "move assigned iterator is a different position";
+  }
+}
+
+TYPED_TEST(MappedIteratorTestBasic, GetFunction) {
+  std::vector<int> V({0});
+
+  using FuncT = GetFuncT<TypeParam>;
+  using IterT = mapped_iterator<decltype(V)::iterator, FuncT>;
+
+  TypeParam GetCallable;
+  IterT I(V.begin(), GetCallable());
+
+  EXPECT_EQ(I.getFunction()(200), 201);
+}
+
+TYPED_TEST(MappedIteratorTestBasic, GetCurrent) {
+  std::vector<int> V({0});
+
+  using FuncT = GetFuncT<TypeParam>;
+  using IterT = mapped_iterator<decltype(V)::iterator, FuncT>;
+
+  TypeParam GetCallable;
+  IterT I(V.begin(), GetCallable());
+
+  EXPECT_EQ(I.getCurrent(), V.begin());
+  EXPECT_EQ(std::next(I).getCurrent(), V.end());
+}
+
+TYPED_TEST(MappedIteratorTestBasic, ApplyFunctionOnDereference) {
   std::vector<int> V({0});
+  TypeParam GetCallable;
 
-  auto I = map_iterator(V.begin(), [](int X) { return X + 1; });
+  auto I = map_iterator(V.begin(), GetCallable());
 
   EXPECT_EQ(*I, 1) << "should have applied function in dereference";
 }
 
 TEST(MappedIteratorTest, ApplyFunctionOnArrow) {
   struct S {
     int Z = 0;
   };
 
   std::vector<int> V({0});
   S Y;
-  S* P = &Y;
+  S *P = &Y;
 
-  auto I = map_iterator(V.begin(), [&](int X) -> S& { return *(P + X); });
+  auto I = map_iterator(V.begin(), [&](int X) -> S & { return *(P + X); });
 
   I->Z = 42;
 
   EXPECT_EQ(Y.Z, 42) << "should have applied function during arrow";
 }
 
 TEST(MappedIteratorTest, FunctionPreservesReferences) {
   std::vector<int> V({1});
-  std::map<int, int> M({ {1, 1} });
+  std::map<int, int> M({{1, 1}});
 
-  auto I = map_iterator(V.begin(), [&](int X) -> int& { return M[X]; });
+  auto I = map_iterator(V.begin(), [&](int X) -> int & { return M[X]; });
   *I = 42;
 
   EXPECT_EQ(M[1], 42) << "assignment should have modified M";
 }
 
 TEST(MappedIteratorTest, CustomIteratorApplyFunctionOnDereference) {
   struct CustomMapIterator
       : public llvm::mapped_iterator_base<CustomMapIterator,