[ADT] ImmutableList no longer requires elements to be copy constructible

[Szelethus]

Summary

I'm refactoring my Static Analyzer checker UninitializedObjectChecker, and I need to store lightweight polymorphic objects in llvm::ImmutableList. I wish to use std::unique_ptrs, but llvm::ImmutableList requires it's elements to be copy constructible for no good reason. This patch aims to fix this.

[dblaikie]

Test coverage?

(& also, maybe rather than modifying concat's signature (& causing its
arguments to reverse in a way that might be confusing), just take the
argument by value and move into the destination?)

& does changing these signatures (of concat and add) not break any existing
code?

[NoQ]

I strongly support argument order swap because it's consistent with other immutable data structures.

Not sure if i support turning add into some sort of emplace. I'd rather just restrict it to a move-constructor by accepting a single rvalue, because it'll make caller code easy to understand. Maybe add another emplace-like method if you need it. I think it's an important distinction to make.

In D49985#1180850, @dblaikie wrote:

Test coverage?
...
& does changing these signatures (of concat and add) not break any existing
code?

This is used only in clang and there's D49986 and there should be no functional change here.

Not sure why didn't we ever write unit tests for these data structures. But it should more or less work as tested by clang lit tests.

[dblaikie]

In D49985#1181018, @NoQ wrote:

I strongly support argument order swap because it's consistent with other immutable data structures.

Not sure I follow - which examples of argument order are you comparing here?

It looks like concat orders the arguments in the same way that the output would be (so concat(X, list) produces [X, list]) - so preserving that argument order seems like it improves/retains readability compared to switching them around so 'concat(list, X)' produces '[X, list]'.

In D49985#1180850, @dblaikie wrote:

Test coverage?
...
& does changing these signatures (of concat and add) not break any existing
code?

This is used only in clang and there's D49986 and there should be no functional change here.

There's a functional change as described by the patch description - this data structure is getting new features/functionality and that can be unit tested. Also, it's best to test it in LLVM so that it doesn't get broken by LLVM developers who may not be compiling/testing Clang.

Not sure why didn't we ever write unit tests for these data structures. But it should more or less work as tested by clang lit tests.

Yeah, often the older corners don't have unit tests - but when they're improved/changed, it's a good chance to correct that & start putting in unit tests. The overhead/work involved in making the first unit test isn't high enough that I feel like it's a great imposition to ask the next developer to start it.

[NoQ]

In D49985#1181564, @dblaikie wrote:

In D49985#1181018, @NoQ wrote:

I strongly support argument order swap because it's consistent with other immutable data structures.

Not sure I follow - which examples of argument order are you comparing here?

ImmutableMap and ImmutableSet both have add(Collection, Item) argument order, but ImmutableList writes the same thing as add(Item, Collection).

It looks like concat orders the arguments in the same way that the output would be (so concat(X, list) produces [X, list]) - so preserving that argument order seems like it improves/retains readability compared to switching them around so 'concat(list, X)' produces '[X, list]'.

Yeah, i guess that might have been the motivation behind such inconsistency. I'll be fine with fixing the order for other data structures.

In D49985#1181564, @dblaikie wrote:

In D49985#1181018, @NoQ wrote:

In D49985#1180850, @dblaikie wrote:

Test coverage?
...
& does changing these signatures (of concat and add) not break any existing
code?

This is used only in clang and there's D49986 and there should be no functional change here.

There's a functional change as described by the patch description - this data structure is getting new features/functionality and that can be unit tested. Also, it's best to test it in LLVM so that it doesn't get broken by LLVM developers who may not be compiling/testing Clang.

Yup, that makes sense.

[Szelethus]

Added a new emplace method, and the rest of the factory methods now take the data argument by value.
I also added a unittest file. It does contain code unrelated to this patch, but since the file didn't exist, I though it's okay to hit two birds with one stone.

On a somewhat unrelated note, is there a need for concat to be public? Also, to me, when I think if the word concatenation, I would first think that it would work similar to std::list<T>::append().

[Szelethus]

Forgot -U9999.

[Szelethus]

I ran into a serious problem. It seems like ImmutableList doesn't run the destructor for std::unique_ptrs or std::shared_ptrs:

struct Obj {
  ~Obj() { llvm_unreachable(""); } // never called
};

using ObjRef = std::unique_ptr<Obj>; // same with std::shared_ptr

namespace llvm {

// Specializing FoldingSetTrait so we can store ObjRef objects in ImmutableList.
template <>
struct FoldingSetTrait<ObjRef> : public DefaultFoldingSetTrait<ObjRef> {

  static void Profile(const ObjRef &FN, FoldingSetNodeID &ID) {
    ID.AddPointer(FN.get());
  }
};

} // end of namespace llvm

TEST_F(ImmutableListTest, UniquePtrTest) {
  ImmutableList<ObjRef>::Factory f;
  ImmutableList<ObjRef> L = f.create(ObjRef(new Obj));
}

What is very interesting though, a simple wrapper works perfectly:

struct ObjRef {
  Obj *ptr;
  ObjRef(Obj *ptr) : ptr(ptr) {}
  ~ObjRef() { delete ptr; }
  Obj *get() const { return ptr; }
};
// llvm_unreachable is actually reached in Obj::~Obj().

I've been stuck on this issue for a while now. Do you know anything about why this could happen?

[george.karpenkov]

requires it's elements to be copy constructible for no good reason
It seems like ImmutableList doesn't run the destructor for std::unique_ptrs

Seems there was a reason: and ImmutableList and its members are assumed to be a POD (plain old datatype), which do not need destructors.

E.g. see the code at the bottom of ImmutableList.h:

template <typename T> struct isPodLike;
template <typename T>
struct isPodLike<ImmutableList<T>> { static const bool value = true; };

@NoQ might want to correct me here, but I'm not sure how achievable is your use case, or whether it makes sense.
The point of functional ImmutableList is that you can copy them by value at O(1) cost everywhere.
If your list contains unique_ptr you can no longer copy it at all without violating unique_ptr semantics.

[george.karpenkov]

Would it make more sense to store references in ImmutableList for your use case instead?

[NoQ]

In D49985#1189306, @Szelethus wrote:

What is very interesting though, a simple wrapper works perfectly:

struct ObjRef {
  Obj *ptr;
  ObjRef(Obj *ptr) : ptr(ptr) {}
  ~ObjRef() { delete ptr; }
  Obj *get() const { return ptr; }
};
// llvm_unreachable is actually reached in Obj::~Obj().

I've been stuck on this issue for a while now. Do you know anything about why this could happen?

My guess is, in your wrapper code the destructor for the temporary ObjRef at the end of the full-expression f.create(ObjRef(new Obj)) deletes the object, and the copy of ObjRef within the immutable list now contains a dangling pointer to the object (from which it won't be deleted again because immutable list doesn't call destructors; your code also doesn't dereference the pointer).

Your custom wrapper doesn't define any reasonable copy/move constructors, so a default copy is used.

[NoQ]

But generally, yeah, i guess the main problem with putting non-POD objects into the immutable list is that you cannot easily make the factory call destructors when it dies because the allocator within it is only good in providing chunks of memory, not tracking them.

Putting smart pointers into an immutable list doesn't make it non-POD or harder to copy, but we are still unable to recall what we need to destroy when time comes.

[Szelethus]

Thanks for the quick and well detailed replies!

In D49985#1189582, @george.karpenkov wrote:

requires it's elements to be copy constructible for no good reason
It seems like ImmutableList doesn't run the destructor for std::unique_ptrs

Seems there was a reason: and ImmutableList and its members are assumed to be a POD (plain old datatype), which do not need destructors.

E.g. see the code at the bottom of ImmutableList.h:

template <typename T> struct isPodLike;
template <typename T>
struct isPodLike<ImmutableList<T>> { static const bool value = true; };

Oh wow. Thank you so much for pointing this out, I was stuck on this one for days. However, to me, it seems like, T doesn't need to be llvm::isPodLike type, just std::is_trivially_destructible.

Would it make more sense to store references in ImmutableList for your use case instead?

Yes, dynamic memory management has a way too great overhead, and since my algorithm relies on recursion, using references should be fine. Great idea!

[george.karpenkov]

In any case, tests are great, I really appreciate those, but I think we have established that the overall direction here does not make too much sense (or would require much more invasive changes)

[Szelethus]

• Moved tests to D50646
• Changed ordering back to how it was
• Added a static_assert, so only trivially destructible types can be stored in ImmutableList.

[george.karpenkov]

include/llvm/ADT/ImmutableList.h

169

Shouldn't we have && here as well for Head?

191–197

And for Data?

[Szelethus]

In D49985#1195588, @george.karpenkov wrote:

In any case, tests are great, I really appreciate those, but I think we have established that the overall direction here does not make too much sense (or would require much more invasive changes)

I still don't see why we wouldn't like to remove the copy constructability restriction, to me the changes for it seem relatively non-invasive. However, can we at least add static_assert(std::is_trivially_destructible<T>::value, ...) to maybe save a developer from falling in the same pit?

[Szelethus]

Re-uploaded with unittests.

include/llvm/ADT/ImmutableList.h

169

I intentionally left it like this, because one can just std::move to it. That does achieve the same thing, right?

[george.karpenkov]

include/llvm/ADT/ImmutableList.h

169

In my understanding, one creates an extra copy, and one does not, but my c++fu is not that strong for templates+references.
I'm pretty sure you want to use universal references here (https://isocpp.org/blog/2012/11/universal-references-in-c11-scott-meyers)

@NoQ might clarify

[Szelethus]

Polite ping :)

[george.karpenkov]

@Szelethus I'm still not sure why do you pass by value instead of using a universal reference.

[NoQ]

include/llvm/ADT/ImmutableList.h

169

I intentionally left it like this, because one can just std::move to it. That does achieve the same thing, right?

Nah, it doesn't achieve the same thing.

Reference is always a reference, passing it into a function is always free-of-charge, i.e. never invokes a constructor. Also std::move doesn't invoke move-constructor on its own, it simply marks the object as movable, i.e. move is simply an lvalue-to-xvalue-cast.

But initialization of a value-type argument is a non-elidable constructor, which will be copy-constructor if the object is not movable and move-constructor if the object is movable. So if you omit && for Head, you are losing the benefits of a free-of-charge pass-by-reference and instead have to deal with an actual constructor call.

[Szelethus]

Now using universal references.

[george.karpenkov]

Thanks!

include/llvm/ADT/ImmutableList.h

 
 template <typename T>
 class ImmutableListImpl : public FoldingSetNode {
   friend class ImmutableListFactory<T>;
 
   T Head;
   const ImmutableListImpl* Tail;
 
-  ImmutableListImpl(const T& head, const ImmutableListImpl* tail = nullptr)
-    : Head(head), Tail(tail) {}
+  ImmutableListImpl(T &&head, const ImmutableListImpl *tail = nullptr)
+    : Head(std::move(head)), Tail(tail) {}
 
 public:
   ImmutableListImpl(const ImmutableListImpl &) = delete;
   ImmutableListImpl &operator=(const ImmutableListImpl &) = delete;
 
   const T& getHead() const { return Head; }
   const ImmutableListImpl* getTail() const { return Tail; }
 
public:
 
   ImmutableListFactory(BumpPtrAllocator& Alloc)
   : Allocator(reinterpret_cast<uintptr_t>(&Alloc) | 0x1) {}
 
   ~ImmutableListFactory() {
     if (ownsAllocator()) delete &getAllocator();
   }
 
-  LLVM_NODISCARD ImmutableList<T> concat(const T &Head, ImmutableList<T> Tail) {
+  LLVM_NODISCARD ImmutableList<T> concat(ImmutableList<T> Tail, T Head) {
     // Profile the new list to see if it already exists in our cache.
     FoldingSetNodeID ID;
     void* InsertPos;
 
     const ListTy* TailImpl = Tail.getInternalPointer();
     ListTy::Profile(ID, Head, TailImpl);
     ListTy* L = Cache.FindNodeOrInsertPos(ID, InsertPos);
 
     if (!L) {
       // The list does not exist in our cache.  Create it.
       BumpPtrAllocator& A = getAllocator();
       L = (ListTy*) A.Allocate<ListTy>();
-      new (L) ListTy(Head, TailImpl);
+      new (L) ListTy(std::move(Head), TailImpl);
 
       // Insert the new list into the cache.
       Cache.InsertNode(L, InsertPos);
     }
 
     return L;
   }
 
-  LLVM_NODISCARD ImmutableList<T> add(const T& D, ImmutableList<T> L) {
-    return concat(D, L);
+  LLVM_NODISCARD ImmutableList<T> add(ImmutableList<T> L, T Data) {
+    return concat(L, std::move(Data));
+  }
+
+  template <typename ...CtorArgs>
+  LLVM_NODISCARD ImmutableList<T> emplace(ImmutableList<T> Tail, CtorArgs &&...Args) {
+    return concat(Tail, T(std::forward<CtorArgs>(Args)...));
   }
 
   ImmutableList<T> getEmptyList() const {
     return ImmutableList<T>(nullptr);
   }
 
-  ImmutableList<T> create(const T& X) {
-    return Concat(X, getEmptyList());
+  ImmutableList<T> create(T Data) {
+    return concat(getEmptyList(), std::move(Data));
   }
 };
 
 //===----------------------------------------------------------------------===//
 // Partially-specialized Traits.
 //===----------------------------------------------------------------------===//
 
 template<typename T> struct DenseMapInfo;

unittests/ADT/CMakeLists.txt

add_llvm_unittest(ADTTests
   FunctionRefTest.cpp
   HashingTest.cpp
   IListBaseTest.cpp
   IListIteratorTest.cpp
   IListNodeBaseTest.cpp
   IListNodeTest.cpp
   IListSentinelTest.cpp
   IListTest.cpp
+  ImmutableListTest.cpp
   ImmutableMapTest.cpp
   ImmutableSetTest.cpp
   IntEqClassesTest.cpp
   IntervalMapTest.cpp
   IntrusiveRefCntPtrTest.cpp
   IteratorTest.cpp
   MakeUniqueTest.cpp
   MappedIteratorTest.cpp

unittests/ADT/ImmutableListTest.cpp

+//===--------- ImmutableListTest.cpp - ImmutableList unit tests --*- C++ -*-==//
+//
+//                     The LLVM Compiler Infrastructure
+//
+// This file is distributed under the University of Illinois Open Source
+// License. Lee LICENSE.TXT for details.
+//
+//===----------------------------------------------------------------------===//
+
+#include "llvm/ADT/ImmutableList.h"
+#include "gtest/gtest.h"
+
+using namespace llvm;
+
+namespace {
+
+template <typename Fundamental> struct Wrapper : llvm::FoldingSetNode {
+  Fundamental F;
+
+  Wrapper(Fundamental F) : F(F) {}
+
+  operator Fundamental() const { return F; }
+
+  void Profile(FoldingSetNodeID &ID) const { ID.AddInteger(F); }
+};
+
+class ImmutableListTest : public testing::Test {};
+
+void concat(const ImmutableList<Wrapper<char>> &L, char *Buffer) {
+  int Index = 0;
+  for (ImmutableList<Wrapper<char>>::iterator It = L.begin(), End = L.end();
+       It != End; ++It) {
+    Buffer[Index++] = *It;
+  }
+  Buffer[Index] = '\0';
+}
+
+TEST_F(ImmutableListTest, EmptyIntListTest) {
+  ImmutableList<Wrapper<int>>::Factory f;
+
+  EXPECT_TRUE(f.getEmptyList() == f.getEmptyList());
+  EXPECT_TRUE(f.getEmptyList().isEqual(f.getEmptyList()));
+  EXPECT_TRUE(f.getEmptyList().isEmpty());
+
+  ImmutableList<Wrapper<int>> L = f.getEmptyList();
+  EXPECT_EQ(nullptr, L.getTail().getInternalPointer());
+  EXPECT_TRUE(L.getTail().isEmpty());
+  EXPECT_TRUE(L.begin() == L.end());
+}
+
+TEST_F(ImmutableListTest, OneElemIntListTest) {
+  ImmutableList<Wrapper<int>>::Factory f;
+  ImmutableList<Wrapper<int>> L = f.getEmptyList();
+
+  ImmutableList<Wrapper<int>> L2 = f.add(L, 3);
+  EXPECT_TRUE(L.isEmpty());
+  EXPECT_FALSE(L2.isEmpty());
+  EXPECT_TRUE(L2.getTail().isEmpty());
+
+  EXPECT_FALSE(L == L2);
+  EXPECT_TRUE(L == L2.getTail());
+  EXPECT_FALSE(L.isEqual(L2));
+  EXPECT_TRUE(L.isEqual(L2.getTail()));
+  EXPECT_FALSE(L2.begin() == L2.end());
+  EXPECT_TRUE(L2.begin() != L2.end());
+
+  EXPECT_FALSE(L.contains(3));
+  EXPECT_EQ(3, L2.getHead());
+  EXPECT_TRUE(L2.contains(3));
+
+  ImmutableList<Wrapper<int>> L3 = f.add(L, 2);
+  EXPECT_TRUE(L.isEmpty());
+  EXPECT_FALSE(L3.isEmpty());
+  EXPECT_FALSE(L == L3);
+  EXPECT_FALSE(L.contains(2));
+  EXPECT_TRUE(L3.contains(2));
+  EXPECT_EQ(2, L3.getHead());
+
+  EXPECT_FALSE(L2 == L3);
+  EXPECT_FALSE(L2.contains(2));
+}
+
+TEST_F(ImmutableListTest, CreatingIntListTest) {
+  ImmutableList<Wrapper<int>>::Factory f;
+
+  ImmutableList<Wrapper<int>> L = f.getEmptyList();
+  ImmutableList<Wrapper<int>> L2 = f.create(3);
+
+  EXPECT_FALSE(L2.isEmpty());
+  EXPECT_TRUE(L2.getTail().isEmpty());
+  EXPECT_EQ(3, L2.getHead());
+  EXPECT_TRUE(L.isEqual(L2.getTail()));
+  EXPECT_TRUE(L2.getTail().isEqual(L));
+}
+
+TEST_F(ImmutableListTest, MultiElemIntListTest) {
+  ImmutableList<Wrapper<int>>::Factory f;
+
+  ImmutableList<Wrapper<int>> L = f.getEmptyList();
+  ImmutableList<Wrapper<int>> L2 = f.add(f.add(f.add(L, 3), 4), 5);
+  ImmutableList<Wrapper<int>> L3 = f.add(f.add(f.add(L2, 9), 20), 43);
+  ImmutableList<Wrapper<int>> L4 = f.add(L2, 9);
+  ImmutableList<Wrapper<int>> L5 = f.add(L2, 9);
+
+  EXPECT_TRUE(L.isEmpty());
+  EXPECT_FALSE(L2.isEmpty());
+  EXPECT_FALSE(L3.isEmpty());
+  EXPECT_FALSE(L4.isEmpty());
+
+  EXPECT_FALSE(L.contains(3));
+  EXPECT_FALSE(L.contains(9));
+
+  EXPECT_TRUE(L2.contains(3));
+  EXPECT_TRUE(L2.contains(4));
+  EXPECT_TRUE(L2.contains(5));
+  EXPECT_FALSE(L2.contains(9));
+  EXPECT_FALSE(L2.contains(0));
+
+  EXPECT_EQ(5, L2.getHead());
+  EXPECT_EQ(4, L2.getTail().getHead());
+  EXPECT_EQ(3, L2.getTail().getTail().getHead());
+
+  EXPECT_TRUE(L3.contains(43));
+  EXPECT_TRUE(L3.contains(20));
+  EXPECT_TRUE(L3.contains(9));
+  EXPECT_TRUE(L3.contains(3));
+  EXPECT_TRUE(L3.contains(4));
+  EXPECT_TRUE(L3.contains(5));
+  EXPECT_FALSE(L3.contains(0));
+
+  EXPECT_EQ(43, L3.getHead());
+  EXPECT_EQ(20, L3.getTail().getHead());
+  EXPECT_EQ(9, L3.getTail().getTail().getHead());
+
+  EXPECT_TRUE(L3.getTail().getTail().getTail() == L2);
+  EXPECT_TRUE(L2 == L3.getTail().getTail().getTail());
+  EXPECT_TRUE(L3.getTail().getTail().getTail().isEqual(L2));
+  EXPECT_TRUE(L2.isEqual(L3.getTail().getTail().getTail()));
+
+  EXPECT_TRUE(L4.contains(9));
+  EXPECT_TRUE(L4.contains(3));
+  EXPECT_TRUE(L4.contains(4));
+  EXPECT_TRUE(L4.contains(5));
+  EXPECT_FALSE(L4.contains(20));
+  EXPECT_FALSE(L4.contains(43));
+  EXPECT_TRUE(L4.isEqual(L4));
+  EXPECT_TRUE(L4.isEqual(L5));
+
+  EXPECT_TRUE(L5.isEqual(L4));
+  EXPECT_TRUE(L5.isEqual(L5));
+}
+
+template <typename Fundamental>
+struct ExplicitCtorWrapper : public Wrapper<Fundamental> {
+  explicit ExplicitCtorWrapper(Fundamental F) : Wrapper<Fundamental>(F) {}
+  ExplicitCtorWrapper(const ExplicitCtorWrapper &) = delete;
+  ExplicitCtorWrapper(ExplicitCtorWrapper &&) = default;
+  ExplicitCtorWrapper &operator=(const ExplicitCtorWrapper &) = delete;
+  ExplicitCtorWrapper &operator=(ExplicitCtorWrapper &&) = default;
+};
+
+TEST_F(ImmutableListTest, EmplaceIntListTest) {
+  ImmutableList<ExplicitCtorWrapper<int>>::Factory f;
+
+  ImmutableList<ExplicitCtorWrapper<int>> L = f.getEmptyList();
+  ImmutableList<ExplicitCtorWrapper<int>> L2 = f.emplace(L, 3);
+
+  ImmutableList<ExplicitCtorWrapper<int>> L3 =
+      f.add(L2, ExplicitCtorWrapper<int>(2));
+
+  ImmutableList<ExplicitCtorWrapper<int>> L4 =
+      f.emplace(L3, ExplicitCtorWrapper<int>(1));
+
+  ImmutableList<ExplicitCtorWrapper<int>> L5 =
+      f.add(L3, ExplicitCtorWrapper<int>(1));
+
+  EXPECT_FALSE(L2.isEmpty());
+  EXPECT_TRUE(L2.getTail().isEmpty());
+  EXPECT_EQ(3, L2.getHead());
+  EXPECT_TRUE(L.isEqual(L2.getTail()));
+  EXPECT_TRUE(L2.getTail().isEqual(L));
+
+  EXPECT_FALSE(L3.isEmpty());
+  EXPECT_FALSE(L2 == L3);
+  EXPECT_EQ(2, L3.getHead());
+  EXPECT_TRUE(L2 == L3.getTail());
+
+  EXPECT_FALSE(L4.isEmpty());
+  EXPECT_EQ(1, L4.getHead());
+  EXPECT_TRUE(L3 == L4.getTail());
+
+  EXPECT_TRUE(L4 == L5);
+  EXPECT_TRUE(L3 == L5.getTail());
+}
+
+TEST_F(ImmutableListTest, CharListOrderingTest) {
+  ImmutableList<Wrapper<char>>::Factory f;
+  ImmutableList<Wrapper<char>> L = f.getEmptyList();
+
+  ImmutableList<Wrapper<char>> L2 = f.add(f.add(f.add(L, 'a'), 'e'), 'i');
+  ImmutableList<Wrapper<char>> L3 = f.add(f.add(L2, 'o'), 'u');
+
+  char Buffer[10];
+  concat(L3, Buffer);
+
+  ASSERT_STREQ("uoiea", Buffer);
+}
+
+TEST_F(ImmutableListTest, LongListOrderingTest) {
+  ImmutableList<Wrapper<long>>::Factory f;
+  ImmutableList<Wrapper<long>> L = f.getEmptyList();
+
+  ImmutableList<Wrapper<long>> L2 = f.add(f.add(f.add(L, 5), 4), 3);
+  ImmutableList<Wrapper<long>> L3 = f.add(f.add(f.add(L2, 2), 1), 0);
+
+  int i = 0;
+  for (ImmutableList<Wrapper<long>>::iterator I = L.begin(), E = L.end();
+       I != E; ++I) {
+    ASSERT_EQ(i, *I);
+    i++;
+  }
+  ASSERT_EQ(0, i);
+
+  i = 3;
+  for (ImmutableList<Wrapper<long>>::iterator I = L2.begin(), E = L2.end();
+       I != E; ++I) {
+    ASSERT_EQ(i, *I);
+    i++;
+  }
+  ASSERT_EQ(6, i);
+
+  i = 0;
+  for (ImmutableList<Wrapper<long>>::iterator I = L3.begin(), E = L3.end();
+       I != E; ++I) {
+    ASSERT_EQ(i, *I);
+    i++;
+  }
+  ASSERT_EQ(6, i);
+}
+
+} // namespace