[ADT] Let MapVector handle non-copyable values.

[jlebar]

Summary

The keys must still be copyable, because we store two copies of them.

[timshen]

llvm/include/llvm/ADT/MapVector.h

113

std::move(KV)?

117

Do you want to static_assert on random_access_iterator_tag in the class?

159

This O(n) behavior is unfortunate. It could have been O(1), by swapping the to-be-erased element with back(), then pop_back().

Just a comment, no change required. :)

[jlebar]

llvm/include/llvm/ADT/MapVector.h

117

I think that should be a separate change -- it's the same as the other insert() function.

159

Except that wouldn't preserve order.

[jlebar]

https://github.com/llvm-mirror/llvm/commit/f086ef8c8bc8eec1f850d867d2ce1a43da5569e6

llvm/include/llvm/ADT/MapVector.h

ValueT &operator[](const KeyT &Key) {
     unsigned &I = Result.first->second;
     if (Result.second) {
       Vector.push_back(std::make_pair(Key, ValueT()));
       I = Vector.size() - 1;
     }
     return Vector[I].second;
   }
 
+  // Returns a copy of the value.  Only allowed if ValueT is copyable.
   ValueT lookup(const KeyT &Key) const {
+    static_assert(std::is_copy_constructible<ValueT>::value,
+                  "Cannot call lookup() if ValueT is not copyable.");
     typename MapType::const_iterator Pos = Map.find(Key);
     return Pos == Map.end()? ValueT() : Vector[Pos->second].second;
   }
 
   std::pair<iterator, bool> insert(const std::pair<KeyT, ValueT> &KV) {
     std::pair<KeyT, unsigned> Pair = std::make_pair(KV.first, 0);
     std::pair<typename MapType::iterator, bool> Result = Map.insert(Pair);
     unsigned &I = Result.first->second;
     if (Result.second) {
       Vector.push_back(std::make_pair(KV.first, KV.second));
       I = Vector.size() - 1;
       return std::make_pair(std::prev(end()), true);
     }
     return std::make_pair(begin() + I, false);
   }
 
+  std::pair<iterator, bool> insert(std::pair<KeyT, ValueT> &&KV) {
+    // Copy KV.first into the map, then move it into the vector.
+    std::pair<KeyT, unsigned> Pair = std::make_pair(KV.first, 0);
+    std::pair<typename MapType::iterator, bool> Result = Map.insert(Pair);
+    unsigned &I = Result.first->second;
+    if (Result.second) {
+      Vector.push_back(
+          std::make_pair(std::move(KV.first), std::move(KV.second)));
+      I = Vector.size() - 1;
+      return std::make_pair(std::prev(end()), true);
+    }
+    return std::make_pair(begin() + I, false);
+  }
+
   size_type count(const KeyT &Key) const {
     typename MapType::const_iterator Pos = Map.find(Key);
     return Pos == Map.end()? 0 : 1;
   }
 
   iterator find(const KeyT &Key) {
     typename MapType::const_iterator Pos = Map.find(Key);
     return Pos == Map.end()? Vector.end() :
public:
   typename VectorType::iterator erase(typename VectorType::iterator Iterator) {
     Map.erase(Iterator->first);
     auto Next = Vector.erase(Iterator);
     if (Next == Vector.end())
       return Next;
 
     // Update indices in the map.
     size_t Index = Next - Vector.begin();
     for (auto &I : Map) {
       assert(I.second != Index && "Index was already erased!");
       if (I.second > Index)
         --I.second;
     }
     return Next;
   }
 
   /// \brief Remove all elements with the key value Key.

llvm/unittests/ADT/MapVectorTest.cpp

TEST(MapVectorTest, iteration_test) {
 
   count = 6;
   for (auto P : make_range(MV.rbegin(), MV.rend())) {
     ASSERT_EQ(P.first, count);
     count--;
   }
 }
 
+TEST(MapVectorTest, NonCopyable) {
+  MapVector<int, std::unique_ptr<int>> MV;
+  MV.insert(std::make_pair(1, llvm::make_unique<int>(1)));
+  MV.insert(std::make_pair(2, llvm::make_unique<int>(2)));
+
+  ASSERT_EQ(MV.count(1), 1u);
+  ASSERT_EQ(*MV.find(2)->second, 2);
+}
+
 TEST(SmallMapVectorSmallTest, insert_pop) {
   SmallMapVector<int, int, 32> MV;
   std::pair<SmallMapVector<int, int, 32>::iterator, bool> R;
 
   R = MV.insert(std::make_pair(1, 2));
   ASSERT_EQ(R.first, MV.begin());
   EXPECT_EQ(R.first->first, 1);
   EXPECT_EQ(R.first->second, 2);
TEST(SmallMapVectorSmallTest, iteration_test) {
 
   count = 6;
   for (auto P : make_range(MV.rbegin(), MV.rend())) {
     ASSERT_EQ(P.first, count);
     count--;
   }
 }
 
+TEST(SmallMapVectorSmallTest, NonCopyable) {
+  SmallMapVector<int, std::unique_ptr<int>, 8> MV;
+  MV.insert(std::make_pair(1, llvm::make_unique<int>(1)));
+  MV.insert(std::make_pair(2, llvm::make_unique<int>(2)));
+
+  ASSERT_EQ(MV.count(1), 1u);
+  ASSERT_EQ(*MV.find(2)->second, 2);
+}
+
 TEST(SmallMapVectorLargeTest, insert_pop) {
   SmallMapVector<int, int, 1> MV;
   std::pair<SmallMapVector<int, int, 1>::iterator, bool> R;
 
   R = MV.insert(std::make_pair(1, 2));
   ASSERT_EQ(R.first, MV.begin());
   EXPECT_EQ(R.first->first, 1);
   EXPECT_EQ(R.first->second, 2);