llvm/unittests/ADT/IListIteratorTest.cpp

   1 //===- unittests/ADT/IListIteratorTest.cpp - ilist_iterator unit tests ----===//
   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/simple_ilist.h"
  10 #include "gtest/gtest.h"
  11
  12 using namespace llvm;
  13
  14 namespace {
  15
  16 class Parent {};
  17
  18 struct Node : ilist_node<Node> {};
  19 struct ParentNode : ilist_node<ParentNode, ilist_parent<Parent>> {};
  20
  21 TEST(IListIteratorTest, DefaultConstructor) {
  22   simple_ilist<Node>::iterator I;
  23   simple_ilist<Node>::reverse_iterator RI;
  24   simple_ilist<Node>::const_iterator CI;
  25   simple_ilist<Node>::const_reverse_iterator CRI;
  26   EXPECT_EQ(nullptr, I.getNodePtr());
  27   EXPECT_EQ(nullptr, CI.getNodePtr());
  28   EXPECT_EQ(nullptr, RI.getNodePtr());
  29   EXPECT_EQ(nullptr, CRI.getNodePtr());
  30   EXPECT_EQ(I, I);
  31   EXPECT_EQ(I, CI);
  32   EXPECT_EQ(CI, I);
  33   EXPECT_EQ(CI, CI);
  34   EXPECT_EQ(RI, RI);
  35   EXPECT_EQ(RI, CRI);
  36   EXPECT_EQ(CRI, RI);
  37   EXPECT_EQ(CRI, CRI);
  38   EXPECT_EQ(I, RI.getReverse());
  39   EXPECT_EQ(RI, I.getReverse());
  40 }
  41
  42 TEST(IListIteratorTest, Empty) {
  43   simple_ilist<Node> L;
  44
  45   // Check iterators of L.
  46   EXPECT_EQ(L.begin(), L.end());
  47   EXPECT_EQ(L.rbegin(), L.rend());
  48
  49   // Reverse of end should be rend (since the sentinel sits on both sides).
  50   EXPECT_EQ(L.end(), L.rend().getReverse());
  51   EXPECT_EQ(L.rend(), L.end().getReverse());
  52
  53   // Iterators shouldn't match default constructors.
  54   simple_ilist<Node>::iterator I;
  55   simple_ilist<Node>::reverse_iterator RI;
  56   EXPECT_NE(I, L.begin());
  57   EXPECT_NE(I, L.end());
  58   EXPECT_NE(RI, L.rbegin());
  59   EXPECT_NE(RI, L.rend());
  60 }
  61
  62 TEST(IListIteratorTest, OneNodeList) {
  63   simple_ilist<Node> L;
  64   Node A;
  65   L.insert(L.end(), A);
  66
  67   // Check address of reference.
  68   EXPECT_EQ(&A, &*L.begin());
  69   EXPECT_EQ(&A, &*L.rbegin());
  70
  71   // Check that the handle matches.
  72   EXPECT_EQ(L.rbegin().getNodePtr(), L.begin().getNodePtr());
  73
  74   // Check iteration.
  75   EXPECT_EQ(L.end(), ++L.begin());
  76   EXPECT_EQ(L.begin(), --L.end());
  77   EXPECT_EQ(L.rend(), ++L.rbegin());
  78   EXPECT_EQ(L.rbegin(), --L.rend());
  79
  80   // Check conversions.
  81   EXPECT_EQ(L.rbegin(), L.begin().getReverse());
  82   EXPECT_EQ(L.begin(), L.rbegin().getReverse());
  83 }
  84
  85 TEST(IListIteratorTest, TwoNodeList) {
  86   simple_ilist<Node> L;
  87   Node A, B;
  88   L.insert(L.end(), A);
  89   L.insert(L.end(), B);
  90
  91   // Check order.
  92   EXPECT_EQ(&A, &*L.begin());
  93   EXPECT_EQ(&B, &*++L.begin());
  94   EXPECT_EQ(L.end(), ++++L.begin());
  95   EXPECT_EQ(&B, &*L.rbegin());
  96   EXPECT_EQ(&A, &*++L.rbegin());
  97   EXPECT_EQ(L.rend(), ++++L.rbegin());
  98
  99   // Check conversions.
 100   EXPECT_EQ(++L.rbegin(), L.begin().getReverse());
 101   EXPECT_EQ(L.rbegin(), (++L.begin()).getReverse());
 102   EXPECT_EQ(++L.begin(), L.rbegin().getReverse());
 103   EXPECT_EQ(L.begin(), (++L.rbegin()).getReverse());
 104 }
 105
 106 TEST(IListIteratorTest, CheckEraseForward) {
 107   simple_ilist<Node> L;
 108   Node A, B;
 109   L.insert(L.end(), A);
 110   L.insert(L.end(), B);
 111
 112   // Erase nodes.
 113   auto I = L.begin();
 114   EXPECT_EQ(&A, &*I);
 115   L.remove(*I++);
 116   EXPECT_EQ(&B, &*I);
 117   L.remove(*I++);
 118   EXPECT_EQ(L.end(), I);
 119 }
 120
 121 TEST(IListIteratorTest, CheckEraseReverse) {
 122   simple_ilist<Node> L;
 123   Node A, B;
 124   L.insert(L.end(), A);
 125   L.insert(L.end(), B);
 126
 127   // Erase nodes.
 128   auto RI = L.rbegin();
 129   EXPECT_EQ(&B, &*RI);
 130   L.remove(*RI++);
 131   EXPECT_EQ(&A, &*RI);
 132   L.remove(*RI++);
 133   EXPECT_EQ(L.rend(), RI);
 134 }
 135
 136 TEST(IListIteratorTest, ReverseConstructor) {
 137   simple_ilist<Node> L;
 138   const simple_ilist<Node> &CL = L;
 139   Node A, B;
 140   L.insert(L.end(), A);
 141   L.insert(L.end(), B);
 142
 143   // Save typing.
 144   typedef simple_ilist<Node>::iterator iterator;
 145   typedef simple_ilist<Node>::reverse_iterator reverse_iterator;
 146   typedef simple_ilist<Node>::const_iterator const_iterator;
 147   typedef simple_ilist<Node>::const_reverse_iterator const_reverse_iterator;
 148
 149   // Check conversion values.
 150   EXPECT_EQ(L.begin(), iterator(L.rend()));
 151   EXPECT_EQ(++L.begin(), iterator(++L.rbegin()));
 152   EXPECT_EQ(L.end(), iterator(L.rbegin()));
 153   EXPECT_EQ(L.rbegin(), reverse_iterator(L.end()));
 154   EXPECT_EQ(++L.rbegin(), reverse_iterator(++L.begin()));
 155   EXPECT_EQ(L.rend(), reverse_iterator(L.begin()));
 156
 157   // Check const iterator constructors.
 158   EXPECT_EQ(CL.begin(), const_iterator(L.rend()));
 159   EXPECT_EQ(CL.begin(), const_iterator(CL.rend()));
 160   EXPECT_EQ(CL.rbegin(), const_reverse_iterator(L.end()));
 161   EXPECT_EQ(CL.rbegin(), const_reverse_iterator(CL.end()));
 162
 163   // Confirm lack of implicit conversions.
 164   static_assert(!std::is_convertible_v<iterator, reverse_iterator>,
 165                 "unexpected implicit conversion");
 166   static_assert(!std::is_convertible_v<reverse_iterator, iterator>,
 167                 "unexpected implicit conversion");
 168   static_assert(!std::is_convertible_v<const_iterator, const_reverse_iterator>,
 169                 "unexpected implicit conversion");
 170   static_assert(!std::is_convertible_v<const_reverse_iterator, const_iterator>,
 171                 "unexpected implicit conversion");
 172 }
 173
 174 TEST(IListIteratorTest, GetParent) {
 175   simple_ilist<ParentNode, ilist_parent<Parent>> L;
 176   Parent P;
 177   ParentNode A;
 178   const simple_ilist<ParentNode, ilist_parent<Parent>> &CL = L;
 179
 180   // Parents are not set automatically.
 181   A.setParent(&P);
 182   L.insert(L.end(), A);
 183   L.end().getNodePtr()->setParent(&P);
 184
 185   // Check we can get the node parent from all iterators, including for the
 186   // sentinel.
 187   EXPECT_EQ(&P, L.begin().getNodeParent());
 188   EXPECT_EQ(&P, L.end().getNodeParent());
 189   EXPECT_EQ(&P, L.rbegin().getNodeParent());
 190   EXPECT_EQ(&P, L.rend().getNodeParent());
 191
 192   using VarParentTy =
 193       std::remove_pointer_t<decltype(L.begin().getNodeParent())>;
 194   using ConstParentTy =
 195       std::remove_pointer_t<decltype(CL.begin().getNodeParent())>;
 196   static_assert(
 197       std::is_const_v<ConstParentTy> &&
 198           std::is_same_v<VarParentTy, std::remove_const_t<ConstParentTy>>,
 199       "`getNodeParent() const` adds const to parent type");
 200 }
 201
 202 } // end namespace