unittests/ADT/ImmutableListTest.cpp

   1 //===--------- ImmutableListTest.cpp - ImmutableList unit tests --*- C++ -*-==//
   2 //
   3 // Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.
   4 // See https://llvm.org/LICENSE.txt for license information.
   5 // SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception
   6 //
   7 //===----------------------------------------------------------------------===//
   8
   9 #include "llvm/ADT/ImmutableList.h"
  10 #include "gtest/gtest.h"
  11
  12 using namespace llvm;
  13
  14 namespace {
  15
  16 template <typename Fundamental> struct Wrapper : llvm::FoldingSetNode {
  17   Fundamental F;
  18
  19   Wrapper(Fundamental F) : F(F) {}
  20
  21   operator Fundamental() const { return F; }
  22
  23   void Profile(FoldingSetNodeID &ID) const { ID.AddInteger(F); }
  24 };
  25
  26 class ImmutableListTest : public testing::Test {};
  27
  28 void concat(const ImmutableList<Wrapper<char>> &L, char *Buffer) {
  29   int Index = 0;
  30   for (ImmutableList<Wrapper<char>>::iterator It = L.begin(), End = L.end();
  31        It != End; ++It) {
  32     Buffer[Index++] = *It;
  33   }
  34   Buffer[Index] = '\0';
  35 }
  36
  37 TEST_F(ImmutableListTest, EmptyIntListTest) {
  38   ImmutableList<Wrapper<int>>::Factory f;
  39
  40   EXPECT_TRUE(f.getEmptyList() == f.getEmptyList());
  41   EXPECT_TRUE(f.getEmptyList().isEqual(f.getEmptyList()));
  42   EXPECT_TRUE(f.getEmptyList().isEmpty());
  43
  44   ImmutableList<Wrapper<int>> L = f.getEmptyList();
  45   EXPECT_EQ(nullptr, L.getTail().getInternalPointer());
  46   EXPECT_TRUE(L.getTail().isEmpty());
  47   EXPECT_TRUE(L.begin() == L.end());
  48 }
  49
  50 TEST_F(ImmutableListTest, OneElemIntListTest) {
  51   ImmutableList<Wrapper<int>>::Factory f;
  52   ImmutableList<Wrapper<int>> L = f.getEmptyList();
  53
  54   ImmutableList<Wrapper<int>> L2 = f.add(3, L);
  55   EXPECT_TRUE(L.isEmpty());
  56   EXPECT_FALSE(L2.isEmpty());
  57   EXPECT_TRUE(L2.getTail().isEmpty());
  58
  59   EXPECT_FALSE(L == L2);
  60   EXPECT_TRUE(L == L2.getTail());
  61   EXPECT_FALSE(L.isEqual(L2));
  62   EXPECT_TRUE(L.isEqual(L2.getTail()));
  63   EXPECT_FALSE(L2.begin() == L2.end());
  64   EXPECT_TRUE(L2.begin() != L2.end());
  65
  66   EXPECT_FALSE(L.contains(3));
  67   EXPECT_EQ(3, L2.getHead());
  68   EXPECT_TRUE(L2.contains(3));
  69
  70   ImmutableList<Wrapper<int>> L3 = f.add(2, L);
  71   EXPECT_TRUE(L.isEmpty());
  72   EXPECT_FALSE(L3.isEmpty());
  73   EXPECT_FALSE(L == L3);
  74   EXPECT_FALSE(L.contains(2));
  75   EXPECT_TRUE(L3.contains(2));
  76   EXPECT_EQ(2, L3.getHead());
  77
  78   EXPECT_FALSE(L2 == L3);
  79   EXPECT_FALSE(L2.contains(2));
  80 }
  81
  82 // We'll store references to objects of this type.
  83 struct Unmodifiable {
  84   Unmodifiable() = default;
  85
  86   // We'll delete all of these special member functions to make sure no copy or
  87   // move happens during insertation.
  88   Unmodifiable(const Unmodifiable &) = delete;
  89   Unmodifiable(const Unmodifiable &&) = delete;
  90   Unmodifiable &operator=(const Unmodifiable &) = delete;
  91   Unmodifiable &operator=(const Unmodifiable &&) = delete;
  92
  93   void doNothing() const {}
  94
  95   void Profile(FoldingSetNodeID &ID) const { ID.AddPointer(this); }
  96 };
  97
  98 // Mostly just a check whether ImmutableList::iterator can be instantiated
  99 // with a reference type as a template argument.
 100 TEST_F(ImmutableListTest, ReferenceStoringTest) {
 101   ImmutableList<const Unmodifiable &>::Factory f;
 102
 103   Unmodifiable N;
 104   ImmutableList<const Unmodifiable &> L = f.create(N);
 105   for (ImmutableList<const Unmodifiable &>::iterator It = L.begin(),
 106                                                      E = L.end();
 107        It != E; ++It) {
 108     It->doNothing();
 109   }
 110 }
 111
 112 TEST_F(ImmutableListTest, CreatingIntListTest) {
 113   ImmutableList<Wrapper<int>>::Factory f;
 114
 115   ImmutableList<Wrapper<int>> L = f.getEmptyList();
 116   ImmutableList<Wrapper<int>> L2 = f.create(3);
 117
 118   EXPECT_FALSE(L2.isEmpty());
 119   EXPECT_TRUE(L2.getTail().isEmpty());
 120   EXPECT_EQ(3, L2.getHead());
 121   EXPECT_TRUE(L.isEqual(L2.getTail()));
 122   EXPECT_TRUE(L2.getTail().isEqual(L));
 123 }
 124
 125 TEST_F(ImmutableListTest, MultiElemIntListTest) {
 126   ImmutableList<Wrapper<int>>::Factory f;
 127
 128   ImmutableList<Wrapper<int>> L = f.getEmptyList();
 129   ImmutableList<Wrapper<int>> L2 = f.add(5, f.add(4, f.add(3, L)));
 130   ImmutableList<Wrapper<int>> L3 = f.add(43, f.add(20, f.add(9, L2)));
 131   ImmutableList<Wrapper<int>> L4 = f.add(9, L2);
 132   ImmutableList<Wrapper<int>> L5 = f.add(9, L2);
 133
 134   EXPECT_TRUE(L.isEmpty());
 135   EXPECT_FALSE(L2.isEmpty());
 136   EXPECT_FALSE(L3.isEmpty());
 137   EXPECT_FALSE(L4.isEmpty());
 138
 139   EXPECT_FALSE(L.contains(3));
 140   EXPECT_FALSE(L.contains(9));
 141
 142   EXPECT_TRUE(L2.contains(3));
 143   EXPECT_TRUE(L2.contains(4));
 144   EXPECT_TRUE(L2.contains(5));
 145   EXPECT_FALSE(L2.contains(9));
 146   EXPECT_FALSE(L2.contains(0));
 147
 148   EXPECT_EQ(5, L2.getHead());
 149   EXPECT_EQ(4, L2.getTail().getHead());
 150   EXPECT_EQ(3, L2.getTail().getTail().getHead());
 151
 152   EXPECT_TRUE(L3.contains(43));
 153   EXPECT_TRUE(L3.contains(20));
 154   EXPECT_TRUE(L3.contains(9));
 155   EXPECT_TRUE(L3.contains(3));
 156   EXPECT_TRUE(L3.contains(4));
 157   EXPECT_TRUE(L3.contains(5));
 158   EXPECT_FALSE(L3.contains(0));
 159
 160   EXPECT_EQ(43, L3.getHead());
 161   EXPECT_EQ(20, L3.getTail().getHead());
 162   EXPECT_EQ(9, L3.getTail().getTail().getHead());
 163
 164   EXPECT_TRUE(L3.getTail().getTail().getTail() == L2);
 165   EXPECT_TRUE(L2 == L3.getTail().getTail().getTail());
 166   EXPECT_TRUE(L3.getTail().getTail().getTail().isEqual(L2));
 167   EXPECT_TRUE(L2.isEqual(L3.getTail().getTail().getTail()));
 168
 169   EXPECT_TRUE(L4.contains(9));
 170   EXPECT_TRUE(L4.contains(3));
 171   EXPECT_TRUE(L4.contains(4));
 172   EXPECT_TRUE(L4.contains(5));
 173   EXPECT_FALSE(L4.contains(20));
 174   EXPECT_FALSE(L4.contains(43));
 175   EXPECT_TRUE(L4.isEqual(L4));
 176   EXPECT_TRUE(L4.isEqual(L5));
 177
 178   EXPECT_TRUE(L5.isEqual(L4));
 179   EXPECT_TRUE(L5.isEqual(L5));
 180 }
 181
 182 template <typename Fundamental>
 183 struct ExplicitCtorWrapper : public Wrapper<Fundamental> {
 184   explicit ExplicitCtorWrapper(Fundamental F) : Wrapper<Fundamental>(F) {}
 185   ExplicitCtorWrapper(const ExplicitCtorWrapper &) = delete;
 186   ExplicitCtorWrapper(ExplicitCtorWrapper &&) = default;
 187   ExplicitCtorWrapper &operator=(const ExplicitCtorWrapper &) = delete;
 188   ExplicitCtorWrapper &operator=(ExplicitCtorWrapper &&) = default;
 189 };
 190
 191 TEST_F(ImmutableListTest, EmplaceIntListTest) {
 192   ImmutableList<ExplicitCtorWrapper<int>>::Factory f;
 193
 194   ImmutableList<ExplicitCtorWrapper<int>> L = f.getEmptyList();
 195   ImmutableList<ExplicitCtorWrapper<int>> L2 = f.emplace(L, 3);
 196
 197   ImmutableList<ExplicitCtorWrapper<int>> L3 =
 198       f.add(ExplicitCtorWrapper<int>(2), L2);
 199
 200   ImmutableList<ExplicitCtorWrapper<int>> L4 =
 201       f.emplace(L3, ExplicitCtorWrapper<int>(1));
 202
 203   ImmutableList<ExplicitCtorWrapper<int>> L5 =
 204       f.add(ExplicitCtorWrapper<int>(1), L3);
 205
 206   EXPECT_FALSE(L2.isEmpty());
 207   EXPECT_TRUE(L2.getTail().isEmpty());
 208   EXPECT_EQ(3, L2.getHead());
 209   EXPECT_TRUE(L.isEqual(L2.getTail()));
 210   EXPECT_TRUE(L2.getTail().isEqual(L));
 211
 212   EXPECT_FALSE(L3.isEmpty());
 213   EXPECT_FALSE(L2 == L3);
 214   EXPECT_EQ(2, L3.getHead());
 215   EXPECT_TRUE(L2 == L3.getTail());
 216
 217   EXPECT_FALSE(L4.isEmpty());
 218   EXPECT_EQ(1, L4.getHead());
 219   EXPECT_TRUE(L3 == L4.getTail());
 220
 221   EXPECT_TRUE(L4 == L5);
 222   EXPECT_TRUE(L3 == L5.getTail());
 223 }
 224
 225 TEST_F(ImmutableListTest, CharListOrderingTest) {
 226   ImmutableList<Wrapper<char>>::Factory f;
 227   ImmutableList<Wrapper<char>> L = f.getEmptyList();
 228
 229   ImmutableList<Wrapper<char>> L2 = f.add('i', f.add('e', f.add('a', L)));
 230   ImmutableList<Wrapper<char>> L3 = f.add('u', f.add('o', L2));
 231
 232   char Buffer[10];
 233   concat(L3, Buffer);
 234
 235   ASSERT_STREQ("uoiea", Buffer);
 236 }
 237
 238 TEST_F(ImmutableListTest, LongListOrderingTest) {
 239   ImmutableList<Wrapper<long>>::Factory f;
 240   ImmutableList<Wrapper<long>> L = f.getEmptyList();
 241
 242   ImmutableList<Wrapper<long>> L2 = f.add(3, f.add(4, f.add(5, L)));
 243   ImmutableList<Wrapper<long>> L3 = f.add(0, f.add(1, f.add(2, L2)));
 244
 245   int i = 0;
 246   for (ImmutableList<Wrapper<long>>::iterator I = L.begin(), E = L.end();
 247        I != E; ++I) {
 248     ASSERT_EQ(i, *I);
 249     i++;
 250   }
 251   ASSERT_EQ(0, i);
 252
 253   i = 3;
 254   for (ImmutableList<Wrapper<long>>::iterator I = L2.begin(), E = L2.end();
 255        I != E; ++I) {
 256     ASSERT_EQ(i, *I);
 257     i++;
 258   }
 259   ASSERT_EQ(6, i);
 260
 261   i = 0;
 262   for (ImmutableList<Wrapper<long>>::iterator I = L3.begin(), E = L3.end();
 263        I != E; ++I) {
 264     ASSERT_EQ(i, *I);
 265     i++;
 266   }
 267   ASSERT_EQ(6, i);
 268 }
 269
 270 static_assert(is_trivially_copyable<ImmutableList<Wrapper<long>>>::value,
 271               "trivially copyable");
 272
 273 } // namespace