273 lines · cpp
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-exception6//7//===----------------------------------------------------------------------===//8 9#include "llvm/ADT/ImmutableList.h"10#include "gtest/gtest.h"11 12using namespace llvm;13 14namespace {15 16template <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 26class ImmutableListTest : public testing::Test {};27 28void 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 37TEST_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 50TEST_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.83struct Unmodifiable {84 Unmodifiable() = default;85 86 // We'll delete all of these special member functions to make sure no copy or87 // 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 instantiated99// with a reference type as a template argument.100TEST_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 112TEST_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 125TEST_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 182template <typename Fundamental>183struct 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 191TEST_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 225TEST_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 238TEST_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 269static_assert(std::is_trivially_copyable_v<ImmutableList<Wrapper<long>>>,270 "trivially copyable");271 272} // namespace273