1 //=== llvm/unittest/ADT/DepthFirstIteratorTest.cpp - DFS iterator 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/DepthFirstIterator.h" 10 #include "TestGraph.h" 11 #include "gtest/gtest.h" 12 13 #include <array> 14 #include <iterator> 15 #include <type_traits> 16 17 #include <cstddef> 18 19 using namespace llvm; 20 21 namespace llvm { 22 23 template <typename T> struct CountedSet { 24 typedef typename SmallPtrSet<T, 4>::iterator iterator; 25 26 SmallPtrSet<T, 4> S; 27 int InsertVisited = 0; 28 29 std::pair<iterator, bool> insert(const T &Item) { 30 InsertVisited++; 31 return S.insert(Item); 32 } 33 34 size_t count(const T &Item) const { return S.count(Item); } 35 36 void completed(T) { } 37 }; 38 39 template <typename T> class df_iterator_storage<CountedSet<T>, true> { 40 public: 41 df_iterator_storage(CountedSet<T> &VSet) : Visited(VSet) {} 42 43 CountedSet<T> &Visited; 44 }; 45 46 TEST(DepthFirstIteratorTest, ActuallyUpdateIterator) { 47 typedef CountedSet<Graph<3>::NodeType *> StorageT; 48 typedef df_iterator<Graph<3>, StorageT, true> DFIter; 49 50 Graph<3> G; 51 G.AddEdge(0, 1); 52 G.AddEdge(0, 2); 53 StorageT S; 54 for (auto N : make_range(DFIter::begin(G, S), DFIter::end(G, S))) 55 (void)N; 56 57 EXPECT_EQ(3, S.InsertVisited); 58 } 59 60 static_assert( 61 std::is_convertible_v<decltype(*std::declval<df_iterator<Graph<3>>>()), 62 typename df_iterator<Graph<3>>::reference>); 63 64 // df_iterator should be (at-least) a forward-iterator 65 static_assert(std::is_base_of_v<std::forward_iterator_tag, 66 df_iterator<Graph<4>>::iterator_category>); 67 68 // df_ext_iterator cannot provide multi-pass guarantee, therefore its only 69 // an input-iterator 70 static_assert(std::is_same_v<df_ext_iterator<Graph<4>>::iterator_category, 71 std::input_iterator_tag>); 72 73 TEST(DepthFirstIteratorTest, MultiPassSafeWithInternalSet) { 74 Graph<4> G; 75 G.AddEdge(0, 1); 76 G.AddEdge(1, 2); 77 G.AddEdge(1, 3); 78 79 std::array<decltype(G)::NodeType *, 4> NodesFirstPass, NodesSecondPass; 80 81 auto B = df_begin(G), E = df_end(G); 82 83 std::size_t I = 0; 84 for (auto It = B; It != E; ++It) 85 NodesFirstPass[I++] = *It; 86 87 I = 0; 88 for (auto It = B; It != E; ++It) 89 NodesSecondPass[I++] = *It; 90 91 EXPECT_EQ(NodesFirstPass, NodesSecondPass); 92 } 93 } 94