[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

1040–1041

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

1040–1041

Good point, will do.

1084

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

1084

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

1081–1084

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

1081–1084

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

1064–1066

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

union {
     RootLeaf leaf;
     RootBranchData branchData;
   };
 
   // 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;
 
   const RootLeaf &rootLeaf() const {
     assert(!branched() && "Cannot acces leaf data in branched root");
     return leaf;
   }
   RootLeaf &rootLeaf() {
     assert(!branched() && "Cannot acces leaf data in branched root");
     return leaf;
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;
     new (&rootBranchData()) RootBranchData();
   }
 
   void switchRootToLeaf() {
     rootBranchData().~RootBranchData();
     height = 0;
     new(&rootLeaf()) RootLeaf();
   }
 
   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) {
-    new(&rootLeaf()) RootLeaf();
+  explicit IntervalMap(Allocator &a) : allocator(&a) {
+    new (&rootLeaf()) RootLeaf();
   }
 
-  // The default copy/move constructors and assignment operators would perform
-  // a shallow copy, leading to an incorrect internal state. To prevent
-  // accidental use, explicitly delete these operators.
-  // If necessary, implement them to perform a deep copy.
-  IntervalMap(const IntervalMap &Other) = delete;
-  IntervalMap(IntervalMap &&Other) = delete;
-  // Note: these are already implicitly deleted, because RootLeaf (union
-  // member) has a non-trivial assignment operator (because of std::pair).
-  IntervalMap &operator=(const IntervalMap &Other) = delete;
-  IntervalMap &operator=(IntervalMap &&Other) = delete;
+  ///@{
+  /// NOTE: The moved-from or copied-from object's allocator needs to have a
+  /// lifetime equal to or exceeding the moved-to or copied-to object to avoid
+  /// undefined behaviour.
+  IntervalMap(IntervalMap const &RHS) : IntervalMap(*RHS.allocator) {
+    // Future-proofing assertion: this function assumes the IntervalMap
+    // constructor doesn't add any nodes.
+    assert(empty() && "Expected emptry tree");
+    *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) : IntervalMap(*RHS.allocator) {
+    // Future-proofing assertion: this function assumes the IntervalMap
+    // constructor doesn't add any nodes.
+    assert(empty() && "Expected emptry tree");
+    *this = std::move(RHS);
+  }
+  IntervalMap &operator=(IntervalMap &&RHS) {
+    // Calling clear deallocates memory and switches to rootLeaf.
+    clear();
+    // Destroy the new rootLeaf.
+    rootLeaf().~RootLeaf();
+
+    height = RHS.height;
+    rootSize = RHS.rootSize;
+    allocator = RHS.allocator;
+
+    // rootLeaf and rootBranch are both uninitialized. Move RHS data into
+    // appropriate field.
+    if (RHS.branched()) {
+      rootBranch() = std::move(RHS.rootBranch());
+      // Prevent RHS deallocating memory LHS now owns by replacing RHS
+      // rootBranch with a new rootLeaf.
+      RHS.rootBranch().~RootBranch();
+      RHS.height = 0;
+      new (&RHS.rootLeaf()) RootLeaf();
+    } else {
+      rootLeaf() = std::move(RHS.rootLeaf());
+    }
+    return *this;
+  }
+  ///@}
 
   ~IntervalMap() {
     clear();
     rootLeaf().~RootLeaf();
   }
 
   /// empty -  Return true when no intervals are mapped.
   bool empty() const {

llvm/unittests/ADT/IntervalMapTest.cpp

 using namespace llvm;
 
 namespace {
 
 typedef IntervalMap<unsigned, unsigned, 4> UUMap;
 typedef IntervalMap<unsigned, unsigned, 4,
                     IntervalMapHalfOpenInfo<unsigned>> UUHalfOpenMap;
 
-static_assert(!std::is_copy_constructible<UUMap>::value,
-              "IntervalMap copy constructor should be deleted");
-static_assert(!std::is_move_constructible<UUMap>::value,
-              "IntervalMap move constructor should be deleted");
-static_assert(!std::is_copy_assignable<UUMap>::value,
-              "IntervalMap copy assignment should be deleted");
-static_assert(!std::is_move_assignable<UUMap>::value,
-              "IntervalMap move assignment should be deleted");
-
 // Empty map tests
 TEST(IntervalMapTest, EmptyMap) {
   UUMap::Allocator allocator;
   UUMap map(allocator);
   EXPECT_TRUE(map.empty());
 
   // Lookup on empty map.
   EXPECT_EQ(0u, map.lookup(0));
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()));
 
 }
 
+static void setupOverlaps(UUMap &M) {
+  M.insert(10, 20, 0);
+  M.insert(30, 40, 0);
+  M.insert(50, 60, 0);
+  // Add extra nodes to force allocations.
+  for (int i = 70; i < 100; i += 2)
+    M.insert(i, i + 1, i);
+}
+
+static 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);