| 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 |
i++; |
| 249 |
} |
| 250 |
ASSERT_EQ(0, i); |
| 251 |
|
| 252 |
i = 3; |
| 253 |
for (ImmutableList<Wrapper<long>>::iterator I = L2.begin(), E = L2.end(); |
| 254 |
I != E; ++I) { |
| 255 |
ASSERT_EQ(i, *I); |
| 256 |
i++; |
| 257 |
} |
| 258 |
ASSERT_EQ(6, i); |
| 259 |
|
| 260 |
i = 0; |
| 261 |
for (ImmutableList<Wrapper<long>>::iterator I = L3.begin(), E = L3.end(); |
| 262 |
I != E; ++I) { |
| 263 |
ASSERT_EQ(i, *I); |
| 264 |
i++; |
| 265 |
} |
| 266 |
ASSERT_EQ(6, i); |
| 267 |
} |
| 268 |
|
| 269 |
static_assert(std::is_trivially_copyable_v<ImmutableList<Wrapper<long>>>, |
| 270 |
"trivially copyable"); |
| 271 |
|
| 272 |
} // namespace |