[ADT] Add copy constructor to IntervalMap

[kparzysz]

Summary

IntervalMap has a union with a member of type RootLeaf, and RootLeaf contains an array of std::pair. On FreeBSD 13- std::pair has a non-trivial copy constructor, which causes the implicitly declared copy constructor for IntervalMap to be deleted. As a result, code that attempts to copy construct an IntervalMap fails to compile.

For more information see https://reviews.llvm.org/rG0d8cb8b399ad, and https://reviews.llvm.org/D125611.

This fixes https://github.com/llvm/llvm-project/issues/55414.

[kparzysz]

This is a shallow copy. Let me change it to a deep one.

[kparzysz]

Changed the copy to a deep one.

[dblaikie]

In D125899#3522879, @kparzysz wrote:

Changed the copy to a deep one.

Ah, if the type wasn't deep copying before - ie: its default copy operation wasn't actually valid/probably would've resulted in duplicate free/delete/etc and generally been broken. Then my use case was just getting lucky because it was copying empty maps.

If that's the case, then maybe that does argue in favor of the unique_ptr solution/marking the broken copy ctor as deleted. (or figuring out some way to do the construction in-place in my case without using copying)

I'll take a closer look.

[dim]

In D125899#3522946, @dblaikie wrote:

In D125899#3522879, @kparzysz wrote:

Changed the copy to a deep one.

Ah, if the type wasn't deep copying before - ie: its default copy operation wasn't actually valid/probably would've resulted in duplicate free/delete/etc and generally been broken. Then my use case was just getting lucky because it was copying empty maps.

If that's the case, then maybe that does argue in favor of the unique_ptr solution/marking the broken copy ctor as deleted. (or figuring out some way to do the construction in-place in my case without using copying)

I'll take a closer look.

There's a subtle difference between the two std::vector constructors, mentioned at https://en.cppreference.com/w/cpp/container/vector/vector, where variant 3 is "Constructs the container with count copies of elements with value value" (so it needs a copy constructor), and variant 4 is "Constructs the container with count default-inserted instances of T. No copies are made". E.g. the latter should not require a copy constructor, but just a default constructor.

However, I'm unsure how you can 'choose' between those two variants. :-)

[dim]

In D125899#3529158, @dim wrote:

...

There's a subtle difference between the two std::vector constructors, mentioned at https://en.cppreference.com/w/cpp/container/vector/vector, where variant 3 is "Constructs the container with count copies of elements with value value" (so it needs a copy constructor), and variant 4 is "Constructs the container with count default-inserted instances of T. No copies are made". E.g. the latter should not require a copy constructor, but just a default constructor.

Ah, and now I see that variant 4 (the default-insert one) can't be used, because IntervalMap has no default constructor. It always requires an Allocator as parameter. As far as I can see, this is to allow allocators to be specified outside the IntervalMap itself, but maybe adding a default constructor, which would also use a default Allocator, would help instead?

[zero9178]

If we are implementing a copy constructor now, shouldn't we be following the Rule of 5 (or at least Rule of 3)? In this case that'd mean also implementing the copy assignment operator and ideally move constructor and move assignment operator. This would be especially important if the interval map were to be inside a vector for performance reasons.

[kparzysz]

If we decide that this is the way to go, I'll add the other functions.

[kpn]

Will this fix FreeBSD 12 (and maybe 11?). FreeBSD 12 is still very much supported.

[dim]

In D125899#3531250, @kpn wrote:

Will this fix FreeBSD 12 (and maybe 11?). FreeBSD 12 is still very much supported.

Yes, we have been carrying the _LIBCPP_TRIVIAL_PAIR_COPY_CTOR define since ~2013, so this copy constructor workaround will work for pretty old FreeBSD versions.

That said, we do want to get rid of this wart for FreeBSD 14.0, so I'm planning a libc++ review to make the define optional. Then we can turn it off in time for 14.0, and bump libc++.so to .2, so we don't get stuck with it for another few years. :)

[brooks]

I can verify this fixes the build on FreeBSD 13.

[dblaikie]

Looking at this further, if we were going to add a copy, it'd be good for it to be more efficient & probably suitable to have an efficient move operation too - but that's all a bit complicated/bigger project than I think we should dive into right now - so let's go with the D125611 solution for now.

[kpn]

I've verified that it fixes the build on FreeBSD 11.1 and the current version of FreeBSD 12.

[kparzysz]

Closing in favor of https://reviews.llvm.org/D125611.

llvm/include/llvm/ADT/IntervalMap.h

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();
   }
 
+  IntervalMap(const IntervalMap &Other) : IntervalMap(Other.allocator) {
+    for (auto i = Other.begin(), e = Other.end(); i != e; ++i)
+      insert(i.start(), i.stop(), i.value());
+  }
+
   ~IntervalMap() {
     clear();
     rootLeaf().~RootLeaf();
   }
 
   /// empty -  Return true when no intervals are mapped.
   bool empty() const {
     return rootSize == 0;