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<ImmutableList<Wrapper<long>>>::value,
270               "trivially copyable");
271 
272 } // namespace
273