[IntervalMap] Add move and copy ctors and assignment operators

[Orlando]

Summary

And update the unittest.

---

These changes will be used by an upcoming patch.

[dblaikie]

Sounds good

llvm/include/llvm/ADT/IntervalMap.h

1044

could drop the height and rootSize initializations now that they're initialized at the member declaration

[Orlando]

Thanks @dblaikie. I was about to land this and noticed some potential UB - I have put a question inline.

llvm/include/llvm/ADT/IntervalMap.h

1044

Good point, will do.

1059

Hmmm. Thinking about it, should I construct data in the move constructor like in the explicit constructor ? Since IntervalMap's dtor explicitly calls data's dtor (rootLeaf().~RootLeaf()). Otherwise the RHS map containing the swapped data will try to call the RootLeaf dtor explicitly on an object that hasn't been constructed, which... feels like UB territory to me?

[dblaikie]

llvm/include/llvm/ADT/IntervalMap.h

1059

Yep, sounds problematic (any chance you can test under sanitizers and see if they detect the problem? Otherwise I guess manually stepping through with a debugger might verify the behavior). Could use a forwarding ctor, perhaps?

Same would be true of the copy constructor too? Since that calls the assignment operator which calls clear, which presumably tries to destroy some things. Hmm, maybe it skates through OK - because it 's not-branched and just sets the size to zero?

(I suspect there's some other "technical" UB around here - like calling rootLeaf to /then/ construct it in the Allocator ctor is probably UB because we've bound a reference to an object before we ran the ctor on it - but that's pre-existing. Probably the right thing to do is to get a void pointer to the storage, call the ctor on that)

[Orlando]

It turns out my base commit was old and was missing some changes. Notably, the AlignedCharArrayUnion<RootLeaf, RootBranchData> data member has since been replaced with a union. Apologies for the noise and additional review required as a result.

Due to the use of an anonymous union and the already tangled object lifetime situation I've changed from using the std::swap idiom, opting for instead explicitly cleaning up the moved-into object before the move (see destroyTree and createTree).

No issues are reported when running the unittest built with -fsanitize=address,undefined (are there any other sanitizers I should be using?).

[dblaikie]

llvm/include/llvm/ADT/IntervalMap.h

1055–1058

This leaves the leaves the rootBranch/rootLeaf in a moved-from state, what does that mean for the state of the object?

What's the state of a moved-from IntervalMap? Is there some test coverage for that? I'd expect to need to change the height/rootSize for the moved-from object in some way?

[Orlando]

This is somewhat fiddly - I think I've got it this time though.

I have used forwarding constructors this time. There's a gottcha - the move/copy constructors set the allocator field before calling the assignment operator, which calls clear. If the IntervalMap constructor was ever changed to allocate nodes then that clear call would deallocate using the wrong allocator. I've added an assertion to the move/copy constructors to help catch this.

I've slightly updated the test (see the inline comment).

I've added a few comments this time round, including a method group docu-comment explaining a requirement of the lifetime of the allocator of RHS.

[Orlando]

llvm/include/llvm/ADT/IntervalMap.h

1055–1058

This leaves the leaves the rootBranch/rootLeaf in a moved-from state, what does that mean for the state of the object?

Yep you're right, my mistake. Setting RHS.height = 0 stops the allocated data now owned by moved-into being deallocated by moved-from upon destruction, but that it doesn't stop the leaf destructor explicitly being called in the IntervalMap destructor. In the case where moved-from (RHS) was using branchData instead of leaf the destructor of the wrong type is being called.

I think I've fixed this now!

What's the state of a moved-from IntervalMap? Is there some test coverage for that?

I had intended for the test to cover this but it turns out that not enough intervals were added to trigger a change from rootLeaf to rootBranch (see MoveAssignmentDst in the unittests). This meant that no nodes were heap allocated, so asan didn't catch this mistake. Adding more intervals causes asan to find this issue.

[dblaikie]

That all looks about right to me.

llvm/include/llvm/ADT/IntervalMap.h

1070–1072

This /probably/ isn't needed - seems pretty unlikely that an allocator-constructer IntervalMap would be anything other than empty, but no worries if you feel strongly about keeping it.

[Orlando]

Thanks for the review

llvm/include/llvm/ADT/IntervalMap.h

 public:
   using Allocator = typename Sizer::Allocator;
   using KeyType = KeyT;
   using ValueType = ValT;
   using KeyTraits = Traits;
 
 private:
   // The root data is either a RootLeaf or a RootBranchData instance.
-  AlignedCharArrayUnion<RootLeaf, RootBranchData> data;
+  AlignedCharArrayUnion<RootLeaf, RootBranchData> data = {};
 
   // Tree height.
   // 0: Leaves in root.
   // 1: Root points to leaf.
   // 2: root->branch->leaf ...
-  unsigned height;
+  unsigned height = 0;
 
   // Number of entries in the root node.
-  unsigned rootSize;
+  unsigned rootSize = 0;
 
   // Allocator used for creating external nodes.
-  Allocator &allocator;
+  Allocator *allocator = nullptr;
 
   /// Represent data as a node type without breaking aliasing rules.
   template <typename T> T &dataAs() const { return *bit_cast<T *>(&data); }
 
   const RootLeaf &rootLeaf() const {
     assert(!branched() && "Cannot acces leaf data in branched root");
     return dataAs<RootLeaf>();
   }
private:
   }
 
   const RootBranch &rootBranch() const { return rootBranchData().node; }
   RootBranch &rootBranch()             { return rootBranchData().node; }
   KeyT rootBranchStart() const { return rootBranchData().start; }
   KeyT &rootBranchStart()      { return rootBranchData().start; }
 
   template <typename NodeT> NodeT *newNode() {
-    return new(allocator.template Allocate<NodeT>()) NodeT();
+    return new (allocator->template Allocate<NodeT>()) NodeT();
   }
 
   template <typename NodeT> void deleteNode(NodeT *P) {
     P->~NodeT();
-    allocator.Deallocate(P);
+    allocator->Deallocate(P);
   }
 
   IdxPair branchRoot(unsigned Position);
   IdxPair splitRoot(unsigned Position);
 
   void switchRootToBranch() {
     rootLeaf().~RootLeaf();
     height = 1;
private:
   bool branched() const { return height > 0; }
 
   ValT treeSafeLookup(KeyT x, ValT NotFound) const;
   void visitNodes(void (IntervalMap::*f)(IntervalMapImpl::NodeRef,
                   unsigned Level));
   void deleteNode(IntervalMapImpl::NodeRef Node, unsigned Level);
 
 public:
-  explicit IntervalMap(Allocator &a) : height(0), rootSize(0), allocator(a) {
+  explicit IntervalMap(Allocator &a) : height(0), rootSize(0), allocator(&a) {
     assert((uintptr_t(&data) & (alignof(RootLeaf) - 1)) == 0 &&
            "Insufficient alignment");
     new(&rootLeaf()) RootLeaf();
   }
 
+  IntervalMap(IntervalMap const &RHS) { *this = RHS; }
+  IntervalMap &operator=(IntervalMap const &RHS) {
+    clear();
+    allocator = RHS.allocator;
+    for (auto It = RHS.begin(), End = RHS.end(); It != End; ++It)
+      insert(It.start(), It.stop(), It.value());
+    return *this;
+  }
+
+  IntervalMap(IntervalMap &&RHS) { *this = std::move(RHS); }
+  IntervalMap &operator=(IntervalMap &&RHS) {
+    std::swap(data, RHS.data);
+    std::swap(height, RHS.height);
+    std::swap(rootSize, RHS.rootSize);
+    std::swap(allocator, RHS.allocator);
+    return *this;
+  }
+
   ~IntervalMap() {
     clear();
     rootLeaf().~RootLeaf();
   }
 
   /// empty -  Return true when no intervals are mapped.
   bool empty() const {
     return rootSize == 0;
   }
 
   /// start - Return the smallest mapped key in a non-empty map.
   KeyT start() const {
     assert(!empty() && "Empty IntervalMap has no start");

llvm/unittests/ADT/IntervalMapTest.cpp

TEST(IntervalMapTest, RandomCoalescing) {
   // Map should be fully coalesced after that exercise.
   EXPECT_FALSE(map.empty());
   EXPECT_EQ(0u, map.start());
   EXPECT_EQ(40959u, map.stop());
   EXPECT_EQ(1, std::distance(map.begin(), map.end()));
 
 }
 
+void setupOverlaps(UUMap &M) {
+  M.insert(10, 20, 0);
+  M.insert(30, 40, 0);
+  M.insert(50, 60, 0);
+}
+
+void checkOverlaps(UUMap &M) {
+  EXPECT_FALSE(M.overlaps(0, 9));
+  EXPECT_TRUE(M.overlaps(0, 10));
+  EXPECT_TRUE(M.overlaps(0, 15));
+  EXPECT_TRUE(M.overlaps(0, 25));
+  EXPECT_TRUE(M.overlaps(0, 45));
+  EXPECT_TRUE(M.overlaps(10, 45));
+  EXPECT_TRUE(M.overlaps(30, 45));
+  EXPECT_TRUE(M.overlaps(35, 36));
+  EXPECT_TRUE(M.overlaps(40, 45));
+  EXPECT_FALSE(M.overlaps(45, 45));
+  EXPECT_TRUE(M.overlaps(60, 60));
+  EXPECT_TRUE(M.overlaps(60, 66));
+  EXPECT_FALSE(M.overlaps(66, 66));
+}
+
+TEST(IntervalMapTest, Copy) {
+  // Test that copy assignment and initialization works.
+  UUHalfOpenMap::Allocator Allocator;
+  UUMap Src(Allocator);
+  setupOverlaps(Src);
+
+  UUMap CopyAssignmentDst(Allocator);
+  CopyAssignmentDst = Src;
+
+  UUMap CopyInitDst(Src);
+
+  checkOverlaps(Src);
+  Src.clear();
+
+  checkOverlaps(CopyAssignmentDst);
+  checkOverlaps(CopyInitDst);
+}
+
+TEST(IntervalMapTest, Move) {
+  // Test that move assignment and initialization works.
+  UUHalfOpenMap::Allocator Allocator;
+  // Double check that MoveAssignmentDst owns all its data by moving from an
+  // object that is destroyed before we call checkOverlaps.
+  UUMap MoveAssignmentDst(Allocator);
+  {
+    UUMap Src(Allocator);
+    setupOverlaps(Src);
+    MoveAssignmentDst = std::move(Src);
+  }
+  checkOverlaps(MoveAssignmentDst);
+
+  UUMap MoveInitSrc(Allocator);
+  setupOverlaps(MoveInitSrc);
+  UUMap MoveInitDst(std::move(MoveInitSrc));
+  checkOverlaps(MoveInitDst);
+}
+
 TEST(IntervalMapTest, Overlaps) {
   UUMap::Allocator allocator;
   UUMap map(allocator);
-  map.insert(10, 20, 0);
-  map.insert(30, 40, 0);
-  map.insert(50, 60, 0);
-
-  EXPECT_FALSE(map.overlaps(0, 9));
-  EXPECT_TRUE(map.overlaps(0, 10));
-  EXPECT_TRUE(map.overlaps(0, 15));
-  EXPECT_TRUE(map.overlaps(0, 25));
-  EXPECT_TRUE(map.overlaps(0, 45));
-  EXPECT_TRUE(map.overlaps(10, 45));
-  EXPECT_TRUE(map.overlaps(30, 45));
-  EXPECT_TRUE(map.overlaps(35, 36));
-  EXPECT_TRUE(map.overlaps(40, 45));
-  EXPECT_FALSE(map.overlaps(45, 45));
-  EXPECT_TRUE(map.overlaps(60, 60));
-  EXPECT_TRUE(map.overlaps(60, 66));
-  EXPECT_FALSE(map.overlaps(66, 66));
+  setupOverlaps(map);
+  checkOverlaps(map);
 }
 
 TEST(IntervalMapTest, OverlapsHalfOpen) {
   UUHalfOpenMap::Allocator allocator;
   UUHalfOpenMap map(allocator);
   map.insert(10, 20, 0);
   map.insert(30, 40, 0);
   map.insert(50, 60, 0);