115 lines · cpp
1//===- PostOrderIteratorTest.cpp - PostOrderIterator 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-exception6//7//===----------------------------------------------------------------------===//8#include "llvm/ADT/PostOrderIterator.h"9#include "llvm/IR/BasicBlock.h"10#include "llvm/IR/CFG.h"11#include "gtest/gtest.h"12#include "TestGraph.h"13 14#include <array>15#include <iterator>16#include <type_traits>17 18#include <cstddef>19 20using namespace llvm;21 22namespace {23 24// Whether we're able to compile25TEST(PostOrderIteratorTest, Compiles) {26 using ExtSetTy = SmallPtrSet<void *, 4>;27 28 // Tests that template specializations are kept up to date29 void *Null = nullptr;30 po_iterator_storage<std::set<void *>, false> PIS;31 PIS.insertEdge(std::optional<void *>(), Null);32 ExtSetTy Ext;33 po_iterator_storage<ExtSetTy, true> PISExt(Ext);34 PIS.insertEdge(std::optional<void *>(), Null);35 36 // Test above, but going through po_iterator (which inherits from template37 // base)38 BasicBlock *NullBB = nullptr;39 auto PI = po_end(NullBB);40 PI.insertEdge(std::optional<BasicBlock *>(), NullBB);41 auto PIExt = po_ext_end(NullBB, Ext);42 PIExt.insertEdge(std::optional<BasicBlock *>(), NullBB);43}44 45static_assert(46 std::is_convertible_v<decltype(*std::declval<po_iterator<Graph<3>>>()),47 po_iterator<Graph<3>>::reference>);48 49// Test post-order and reverse post-order traversals for simple graph type.50TEST(PostOrderIteratorTest, PostOrderAndReversePostOrderTraverrsal) {51 Graph<6> G;52 G.AddEdge(0, 1);53 G.AddEdge(0, 2);54 G.AddEdge(0, 3);55 G.AddEdge(1, 4);56 G.AddEdge(2, 5);57 G.AddEdge(5, 2);58 G.AddEdge(2, 4);59 G.AddEdge(1, 4);60 61 SmallVector<int> FromIterator;62 for (auto N : post_order(G))63 FromIterator.push_back(N->first);64 EXPECT_EQ(6u, FromIterator.size());65 EXPECT_EQ(4, FromIterator[0]);66 EXPECT_EQ(1, FromIterator[1]);67 EXPECT_EQ(5, FromIterator[2]);68 EXPECT_EQ(2, FromIterator[3]);69 EXPECT_EQ(3, FromIterator[4]);70 EXPECT_EQ(0, FromIterator[5]);71 FromIterator.clear();72 73 ReversePostOrderTraversal<Graph<6>> RPOT(G);74 for (auto N : RPOT)75 FromIterator.push_back(N->first);76 EXPECT_EQ(6u, FromIterator.size());77 EXPECT_EQ(0, FromIterator[0]);78 EXPECT_EQ(3, FromIterator[1]);79 EXPECT_EQ(2, FromIterator[2]);80 EXPECT_EQ(5, FromIterator[3]);81 EXPECT_EQ(1, FromIterator[4]);82 EXPECT_EQ(4, FromIterator[5]);83}84 85// po_iterator should be (at-least) a forward-iterator86static_assert(std::is_base_of_v<std::forward_iterator_tag,87 po_iterator<Graph<4>>::iterator_category>);88 89// po_ext_iterator cannot provide multi-pass guarantee, therefore its only90// an input-iterator91static_assert(std::is_same_v<po_ext_iterator<Graph<4>>::iterator_category,92 std::input_iterator_tag>);93 94TEST(PostOrderIteratorTest, MultiPassSafeWithInternalSet) {95 Graph<4> G;96 G.AddEdge(0, 1);97 G.AddEdge(1, 2);98 G.AddEdge(1, 3);99 100 std::array<decltype(G)::NodeType *, 4> NodesFirstPass, NodesSecondPass;101 102 auto B = po_begin(G), E = po_end(G);103 104 std::size_t I = 0;105 for (auto It = B; It != E; ++It)106 NodesFirstPass[I++] = *It;107 108 I = 0;109 for (auto It = B; It != E; ++It)110 NodesSecondPass[I++] = *It;111 112 EXPECT_EQ(NodesFirstPass, NodesSecondPass);113}114}115