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