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(Data: 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(Data: 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(Ptr: 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(Data&: 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(Data: 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(Data: 5, L: f.add(Data: 4, L: f.add(Data: 3, L))); |
130 | ImmutableList<Wrapper<int>> L3 = f.add(Data: 43, L: f.add(Data: 20, L: f.add(Data: 9, L: L2))); |
131 | ImmutableList<Wrapper<int>> L4 = f.add(Data: 9, L: L2); |
132 | ImmutableList<Wrapper<int>> L5 = f.add(Data: 9, L: 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(Tail: L, Args: 3); |
196 | |
197 | ImmutableList<ExplicitCtorWrapper<int>> L3 = |
198 | f.add(Data: ExplicitCtorWrapper<int>(2), L: L2); |
199 | |
200 | ImmutableList<ExplicitCtorWrapper<int>> L4 = |
201 | f.emplace(Tail: L3, Args: ExplicitCtorWrapper<int>(1)); |
202 | |
203 | ImmutableList<ExplicitCtorWrapper<int>> L5 = |
204 | f.add(Data: ExplicitCtorWrapper<int>(1), L: 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(Data: 'i', L: f.add(Data: 'e', L: f.add(Data: 'a', L))); |
230 | ImmutableList<Wrapper<char>> L3 = f.add(Data: 'u', L: f.add(Data: 'o', L: L2)); |
231 | |
232 | char Buffer[10]; |
233 | concat(L: 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(Data: 3, L: f.add(Data: 4, L: f.add(Data: 5, L))); |
243 | ImmutableList<Wrapper<long>> L3 = f.add(Data: 0, L: f.add(Data: 1, L: f.add(Data: 2, L: 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 |
273 | |