94 lines · cpp
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-exception6//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 19using namespace llvm;20 21namespace llvm {22 23template <typename T> struct CountedSet {24 using iterator = typename SmallPtrSet<T, 4>::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 39template <typename T> class df_iterator_storage<CountedSet<T>, true> {40public:41 df_iterator_storage(CountedSet<T> &VSet) : Visited(VSet) {}42 43 CountedSet<T> &Visited;44};45 46TEST(DepthFirstIteratorTest, ActuallyUpdateIterator) {47 using StorageT = CountedSet<Graph<3>::NodeType *>;48 using DFIter = df_iterator<Graph<3>, StorageT, true>;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 60static_assert(61 std::is_convertible_v<decltype(*std::declval<df_iterator<Graph<3>>>()),62 df_iterator<Graph<3>>::reference>);63 64// df_iterator should be (at-least) a forward-iterator65static_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 only69// an input-iterator70static_assert(std::is_same_v<df_ext_iterator<Graph<4>>::iterator_category,71 std::input_iterator_tag>);72 73TEST(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