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
Wrapper__anon489e82070111::Wrapper19 Wrapper(Fundamental F) : F(F) {}
20
operator Fundamental__anon489e82070111::Wrapper21 operator Fundamental() const { return F; }
22
Profile__anon489e82070111::Wrapper23 void Profile(FoldingSetNodeID &ID) const { ID.AddInteger(F); }
24 };
25
26 class ImmutableListTest : public testing::Test {};
27
concat(const ImmutableList<Wrapper<char>> & L,char * Buffer)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
TEST_F(ImmutableListTest,EmptyIntListTest)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
TEST_F(ImmutableListTest,OneElemIntListTest)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
doNothing__anon489e82070111::Unmodifiable93 void doNothing() const {}
94
Profile__anon489e82070111::Unmodifiable95 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.
TEST_F(ImmutableListTest,ReferenceStoringTest)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
TEST_F(ImmutableListTest,CreatingIntListTest)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
TEST_F(ImmutableListTest,MultiElemIntListTest)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> {
ExplicitCtorWrapper__anon489e82070111::ExplicitCtorWrapper184 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
TEST_F(ImmutableListTest,EmplaceIntListTest)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
TEST_F(ImmutableListTest,CharListOrderingTest)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
TEST_F(ImmutableListTest,LongListOrderingTest)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(std::is_trivially_copyable<ImmutableList<Wrapper<long>>>::value,
271 "trivially copyable");
272
273 } // namespace
274