Index: unittests/Analysis/LazyCallGraphTest.cpp =================================================================== --- unittests/Analysis/LazyCallGraphTest.cpp +++ unittests/Analysis/LazyCallGraphTest.cpp @@ -9,12 +9,13 @@ #include "llvm/Analysis/LazyCallGraph.h" #include "llvm/AsmParser/Parser.h" -#include "llvm/IR/Instructions.h" #include "llvm/IR/Function.h" +#include "llvm/IR/Instructions.h" #include "llvm/IR/LLVMContext.h" #include "llvm/IR/Module.h" #include "llvm/Support/ErrorHandling.h" #include "llvm/Support/SourceMgr.h" +#include "gmock/gmock.h" #include "gtest/gtest.h" #include @@ -22,6 +23,17 @@ namespace { +using testing::ElementsAre; +using testing::Eq; +using testing::Ne; +using testing::Not; +using testing::AnyOf; +using testing::NotNull; +using testing::IsNull; +using testing::Ref; +using testing::UnorderedElementsAre; +using testing::_; + std::unique_ptr parseAssembly(LLVMContext &Context, const char *Assembly) { SMDiagnostic Error; @@ -216,6 +228,65 @@ " ret void\n" "}\n"; +MATCHER_P(IsNode, Name, "") { + std::string ArgName = arg.getFunction().getName().str(); + *result_listener << "named '" << ArgName << "'"; + return ArgName == Name; +} + +class EdgeToMatcher + : public testing::MatcherInterface { +public: + enum Kind { Call, Ref, Any }; + + EdgeToMatcher(Kind K, LazyCallGraph::Node &N) : K(K), N(N) {} + + bool MatchAndExplain(const LazyCallGraph::Edge &E, + testing::MatchResultListener *Listener) const override { + *Listener << "a " << (E.isCall() ? "call" : "ref") << " edge to '" + << E.getFunction().getName().str() << "' @" << E.getNode(); + if (K == Call && !E.isCall()) + return false; + if (K == Ref && E.isCall()) + return false; + + return &N == E.getNode(); + } + + void DescribeTo(::std::ostream *OS) const override { + std::string Name = N.getFunction().getName().str(); + switch (K) { + case Call: + *OS << "is a call edge to '" << Name << "'"; + break; + case Ref: + *OS << "is a ref edge to '" << Name << "'"; + break; + case Any: + *OS << "is an edge to '" << Name << "'"; + break; + } + *OS << " @" << &N; + } + +private: + Kind K; + LazyCallGraph::Node &N; +}; + +static testing::Matcher +IsEdgeTo(LazyCallGraph::Node &N) { + return testing::MakeMatcher(new EdgeToMatcher(EdgeToMatcher::Any, N)); +} +static testing::Matcher +IsCallEdgeTo(LazyCallGraph::Node &N) { + return testing::MakeMatcher(new EdgeToMatcher(EdgeToMatcher::Call, N)); +} +static testing::Matcher +IsRefEdgeTo(LazyCallGraph::Node &N) { + return testing::MakeMatcher(new EdgeToMatcher(EdgeToMatcher::Ref, N)); +} + TEST(LazyCallGraphTest, BasicGraphFormation) { LLVMContext Context; std::unique_ptr M = parseAssembly(Context, DiamondOfTriangles); @@ -226,152 +297,98 @@ // build variables for each node. auto I = CG.begin(); LazyCallGraph::Node &A1 = (I++)->getNode(CG); - EXPECT_EQ("a1", A1.getFunction().getName()); + EXPECT_THAT(A1.getFunction().getName(), Eq("a1")); LazyCallGraph::Node &A2 = (I++)->getNode(CG); - EXPECT_EQ("a2", A2.getFunction().getName()); + EXPECT_THAT(A2.getFunction().getName(), Eq("a2")); LazyCallGraph::Node &A3 = (I++)->getNode(CG); - EXPECT_EQ("a3", A3.getFunction().getName()); + EXPECT_THAT(A3.getFunction().getName(), Eq("a3")); LazyCallGraph::Node &B1 = (I++)->getNode(CG); - EXPECT_EQ("b1", B1.getFunction().getName()); + EXPECT_THAT(B1.getFunction().getName(), Eq("b1")); LazyCallGraph::Node &B2 = (I++)->getNode(CG); - EXPECT_EQ("b2", B2.getFunction().getName()); + EXPECT_THAT(B2.getFunction().getName(), Eq("b2")); LazyCallGraph::Node &B3 = (I++)->getNode(CG); - EXPECT_EQ("b3", B3.getFunction().getName()); + EXPECT_THAT(B3.getFunction().getName(), Eq("b3")); LazyCallGraph::Node &C1 = (I++)->getNode(CG); - EXPECT_EQ("c1", C1.getFunction().getName()); + EXPECT_THAT(C1.getFunction().getName(), Eq("c1")); LazyCallGraph::Node &C2 = (I++)->getNode(CG); - EXPECT_EQ("c2", C2.getFunction().getName()); + EXPECT_THAT(C2.getFunction().getName(), Eq("c2")); LazyCallGraph::Node &C3 = (I++)->getNode(CG); - EXPECT_EQ("c3", C3.getFunction().getName()); + EXPECT_THAT(C3.getFunction().getName(), Eq("c3")); LazyCallGraph::Node &D1 = (I++)->getNode(CG); - EXPECT_EQ("d1", D1.getFunction().getName()); + EXPECT_THAT(D1.getFunction().getName(), Eq("d1")); LazyCallGraph::Node &D2 = (I++)->getNode(CG); - EXPECT_EQ("d2", D2.getFunction().getName()); + EXPECT_THAT(D2.getFunction().getName(), Eq("d2")); LazyCallGraph::Node &D3 = (I++)->getNode(CG); - EXPECT_EQ("d3", D3.getFunction().getName()); - EXPECT_EQ(CG.end(), I); + EXPECT_THAT(D3.getFunction().getName(), Eq("d3")); + EXPECT_THAT(I, Eq(CG.end())); - // Build vectors and sort them for the rest of the assertions to make them - // independent of order. - std::vector Nodes; + // Resolve edges to the call graph nodes instead of functions. + for (LazyCallGraph::Edge &RootE : CG) + for (LazyCallGraph::Edge &E : *RootE.getNode()) + E.getNode(CG); + + EXPECT_THAT(A1, + UnorderedElementsAre(IsEdgeTo(A2), IsEdgeTo(B2), IsEdgeTo(C3))); + EXPECT_THAT(A2, UnorderedElementsAre(IsEdgeTo(A3))); + EXPECT_THAT(A3, UnorderedElementsAre(IsEdgeTo(A1))); + + EXPECT_THAT(B1, UnorderedElementsAre(IsEdgeTo(B2), IsEdgeTo(D3))); + EXPECT_THAT(B2, UnorderedElementsAre(IsEdgeTo(B3))); + EXPECT_THAT(B3, UnorderedElementsAre(IsEdgeTo(B1))); - for (LazyCallGraph::Edge &E : A1) - Nodes.push_back(E.getFunction().getName()); - std::sort(Nodes.begin(), Nodes.end()); - EXPECT_EQ("a2", Nodes[0]); - EXPECT_EQ("b2", Nodes[1]); - EXPECT_EQ("c3", Nodes[2]); - Nodes.clear(); - - EXPECT_EQ(A2.end(), std::next(A2.begin())); - EXPECT_EQ("a3", A2.begin()->getFunction().getName()); - EXPECT_EQ(A3.end(), std::next(A3.begin())); - EXPECT_EQ("a1", A3.begin()->getFunction().getName()); - - for (LazyCallGraph::Edge &E : B1) - Nodes.push_back(E.getFunction().getName()); - std::sort(Nodes.begin(), Nodes.end()); - EXPECT_EQ("b2", Nodes[0]); - EXPECT_EQ("d3", Nodes[1]); - Nodes.clear(); - - EXPECT_EQ(B2.end(), std::next(B2.begin())); - EXPECT_EQ("b3", B2.begin()->getFunction().getName()); - EXPECT_EQ(B3.end(), std::next(B3.begin())); - EXPECT_EQ("b1", B3.begin()->getFunction().getName()); - - for (LazyCallGraph::Edge &E : C1) - Nodes.push_back(E.getFunction().getName()); - std::sort(Nodes.begin(), Nodes.end()); - EXPECT_EQ("c2", Nodes[0]); - EXPECT_EQ("d2", Nodes[1]); - Nodes.clear(); - - EXPECT_EQ(C2.end(), std::next(C2.begin())); - EXPECT_EQ("c3", C2.begin()->getFunction().getName()); - EXPECT_EQ(C3.end(), std::next(C3.begin())); - EXPECT_EQ("c1", C3.begin()->getFunction().getName()); - - EXPECT_EQ(D1.end(), std::next(D1.begin())); - EXPECT_EQ("d2", D1.begin()->getFunction().getName()); - EXPECT_EQ(D2.end(), std::next(D2.begin())); - EXPECT_EQ("d3", D2.begin()->getFunction().getName()); - EXPECT_EQ(D3.end(), std::next(D3.begin())); - EXPECT_EQ("d1", D3.begin()->getFunction().getName()); + EXPECT_THAT(C1, UnorderedElementsAre(IsEdgeTo(C2), IsEdgeTo(D2))); + EXPECT_THAT(C2, UnorderedElementsAre(IsEdgeTo(C3))); + EXPECT_THAT(C3, UnorderedElementsAre(IsEdgeTo(C1))); + + EXPECT_THAT(D1, UnorderedElementsAre(IsEdgeTo(D2))); + EXPECT_THAT(D2, UnorderedElementsAre(IsEdgeTo(D3))); + EXPECT_THAT(D3, ElementsAre(IsEdgeTo(D1))); // Now lets look at the RefSCCs and SCCs. auto J = CG.postorder_ref_scc_begin(); LazyCallGraph::RefSCC &D = *J++; - ASSERT_EQ(1, D.size()); - for (LazyCallGraph::Node &N : *D.begin()) - Nodes.push_back(N.getFunction().getName()); - std::sort(Nodes.begin(), Nodes.end()); - EXPECT_EQ(3u, Nodes.size()); - EXPECT_EQ("d1", Nodes[0]); - EXPECT_EQ("d2", Nodes[1]); - EXPECT_EQ("d3", Nodes[2]); - Nodes.clear(); + EXPECT_THAT(D, UnorderedElementsAre(UnorderedElementsAre( + IsNode("d1"), IsNode("d2"), IsNode("d3")))); EXPECT_FALSE(D.isParentOf(D)); EXPECT_FALSE(D.isChildOf(D)); EXPECT_FALSE(D.isAncestorOf(D)); EXPECT_FALSE(D.isDescendantOf(D)); - EXPECT_EQ(&D, &*CG.postorder_ref_scc_begin()); + EXPECT_THAT(&*CG.postorder_ref_scc_begin(), Eq(&D)); LazyCallGraph::RefSCC &C = *J++; - ASSERT_EQ(1, C.size()); - for (LazyCallGraph::Node &N : *C.begin()) - Nodes.push_back(N.getFunction().getName()); - std::sort(Nodes.begin(), Nodes.end()); - EXPECT_EQ(3u, Nodes.size()); - EXPECT_EQ("c1", Nodes[0]); - EXPECT_EQ("c2", Nodes[1]); - EXPECT_EQ("c3", Nodes[2]); - Nodes.clear(); + EXPECT_THAT(C, UnorderedElementsAre(UnorderedElementsAre( + IsNode("c1"), IsNode("c2"), IsNode("c3")))); EXPECT_TRUE(C.isParentOf(D)); EXPECT_FALSE(C.isChildOf(D)); EXPECT_TRUE(C.isAncestorOf(D)); EXPECT_FALSE(C.isDescendantOf(D)); - EXPECT_EQ(&C, &*std::next(CG.postorder_ref_scc_begin())); + EXPECT_THAT(&*std::next(CG.postorder_ref_scc_begin()), Eq(&C)); LazyCallGraph::RefSCC &B = *J++; - ASSERT_EQ(1, B.size()); - for (LazyCallGraph::Node &N : *B.begin()) - Nodes.push_back(N.getFunction().getName()); - std::sort(Nodes.begin(), Nodes.end()); - EXPECT_EQ(3u, Nodes.size()); - EXPECT_EQ("b1", Nodes[0]); - EXPECT_EQ("b2", Nodes[1]); - EXPECT_EQ("b3", Nodes[2]); - Nodes.clear(); + EXPECT_THAT(B, UnorderedElementsAre(UnorderedElementsAre( + IsNode("b1"), IsNode("b2"), IsNode("b3")))); EXPECT_TRUE(B.isParentOf(D)); EXPECT_FALSE(B.isChildOf(D)); EXPECT_TRUE(B.isAncestorOf(D)); EXPECT_FALSE(B.isDescendantOf(D)); EXPECT_FALSE(B.isAncestorOf(C)); EXPECT_FALSE(C.isAncestorOf(B)); - EXPECT_EQ(&B, &*std::next(CG.postorder_ref_scc_begin(), 2)); + EXPECT_THAT(&*std::next(CG.postorder_ref_scc_begin(), 2), Eq(&B)); LazyCallGraph::RefSCC &A = *J++; - ASSERT_EQ(1, A.size()); - for (LazyCallGraph::Node &N : *A.begin()) - Nodes.push_back(N.getFunction().getName()); - std::sort(Nodes.begin(), Nodes.end()); - EXPECT_EQ(3u, Nodes.size()); - EXPECT_EQ("a1", Nodes[0]); - EXPECT_EQ("a2", Nodes[1]); - EXPECT_EQ("a3", Nodes[2]); - Nodes.clear(); + EXPECT_THAT(A, UnorderedElementsAre(UnorderedElementsAre( + IsNode("a1"), IsNode("a2"), IsNode("a3")))); EXPECT_TRUE(A.isParentOf(B)); EXPECT_TRUE(A.isParentOf(C)); EXPECT_FALSE(A.isParentOf(D)); EXPECT_TRUE(A.isAncestorOf(B)); EXPECT_TRUE(A.isAncestorOf(C)); EXPECT_TRUE(A.isAncestorOf(D)); - EXPECT_EQ(&A, &*std::next(CG.postorder_ref_scc_begin(), 3)); + EXPECT_THAT(&*std::next(CG.postorder_ref_scc_begin(), 3), Eq(&A)); - EXPECT_EQ(CG.postorder_ref_scc_end(), J); - EXPECT_EQ(J, std::next(CG.postorder_ref_scc_begin(), 4)); + EXPECT_THAT(J, Eq(CG.postorder_ref_scc_end())); + EXPECT_THAT(std::next(CG.postorder_ref_scc_begin(), 4), Eq(J)); } static Function &lookupFunction(Module &M, StringRef Name) { @@ -401,32 +418,28 @@ LazyCallGraph::Node &A = CG.get(lookupFunction(*M, "a")); LazyCallGraph::Node &B = CG.get(lookupFunction(*M, "b")); - EXPECT_EQ(2, std::distance(A.begin(), A.end())); - EXPECT_EQ(0, std::distance(B.begin(), B.end())); + EXPECT_THAT(std::distance(A.begin(), A.end()), Eq(2)); + EXPECT_THAT(std::distance(B.begin(), B.end()), Eq(0)); CG.insertEdge(B, lookupFunction(*M, "c"), LazyCallGraph::Edge::Call); - EXPECT_EQ(1, std::distance(B.begin(), B.end())); + EXPECT_THAT(B, ElementsAre(_)); LazyCallGraph::Node &C = B.begin()->getNode(CG); - EXPECT_EQ(0, std::distance(C.begin(), C.end())); + EXPECT_THAT(C, ElementsAre()); CG.insertEdge(C, B.getFunction(), LazyCallGraph::Edge::Call); - EXPECT_EQ(1, std::distance(C.begin(), C.end())); - EXPECT_EQ(&B, C.begin()->getNode()); + EXPECT_THAT(C, ElementsAre(IsEdgeTo(B))); CG.insertEdge(C, C.getFunction(), LazyCallGraph::Edge::Call); - EXPECT_EQ(2, std::distance(C.begin(), C.end())); - EXPECT_EQ(&B, C.begin()->getNode()); - EXPECT_EQ(&C, std::next(C.begin())->getNode()); + EXPECT_THAT(C, ElementsAre(IsEdgeTo(B), IsEdgeTo(C))); CG.removeEdge(C, B.getFunction()); - EXPECT_EQ(1, std::distance(C.begin(), C.end())); - EXPECT_EQ(&C, C.begin()->getNode()); + EXPECT_THAT(C, ElementsAre(IsEdgeTo(C))); CG.removeEdge(C, C.getFunction()); - EXPECT_EQ(0, std::distance(C.begin(), C.end())); + EXPECT_THAT(C, ElementsAre()); CG.removeEdge(B, C.getFunction()); - EXPECT_EQ(0, std::distance(B.begin(), B.end())); + EXPECT_THAT(C, ElementsAre()); } TEST(LazyCallGraphTest, InnerSCCFormation) { @@ -446,51 +459,27 @@ // We should build a single RefSCC for the entire graph. auto I = CG.postorder_ref_scc_begin(); LazyCallGraph::RefSCC &RC = *I++; - EXPECT_EQ(CG.postorder_ref_scc_end(), I); + EXPECT_THAT(I, Eq(CG.postorder_ref_scc_end())); // Now walk the four SCCs which should be in post-order. auto J = RC.begin(); LazyCallGraph::SCC &D = *J++; - for (LazyCallGraph::Node &N : D) - Nodes.push_back(N.getFunction().getName()); - std::sort(Nodes.begin(), Nodes.end()); - EXPECT_EQ(3u, Nodes.size()); - EXPECT_EQ("d1", Nodes[0]); - EXPECT_EQ("d2", Nodes[1]); - EXPECT_EQ("d3", Nodes[2]); - Nodes.clear(); + EXPECT_THAT(D, + UnorderedElementsAre(IsNode("d1"), IsNode("d2"), IsNode("d3"))); LazyCallGraph::SCC &B = *J++; - for (LazyCallGraph::Node &N : B) - Nodes.push_back(N.getFunction().getName()); - std::sort(Nodes.begin(), Nodes.end()); - EXPECT_EQ(3u, Nodes.size()); - EXPECT_EQ("b1", Nodes[0]); - EXPECT_EQ("b2", Nodes[1]); - EXPECT_EQ("b3", Nodes[2]); - Nodes.clear(); + EXPECT_THAT(B, + UnorderedElementsAre(IsNode("b1"), IsNode("b2"), IsNode("b3"))); LazyCallGraph::SCC &C = *J++; - for (LazyCallGraph::Node &N : C) - Nodes.push_back(N.getFunction().getName()); - std::sort(Nodes.begin(), Nodes.end()); - EXPECT_EQ(3u, Nodes.size()); - EXPECT_EQ("c1", Nodes[0]); - EXPECT_EQ("c2", Nodes[1]); - EXPECT_EQ("c3", Nodes[2]); - Nodes.clear(); + EXPECT_THAT(C, + UnorderedElementsAre(IsNode("c1"), IsNode("c2"), IsNode("c3"))); LazyCallGraph::SCC &A = *J++; - for (LazyCallGraph::Node &N : A) - Nodes.push_back(N.getFunction().getName()); - std::sort(Nodes.begin(), Nodes.end()); - EXPECT_EQ(3u, Nodes.size()); - EXPECT_EQ("a1", Nodes[0]); - EXPECT_EQ("a2", Nodes[1]); - EXPECT_EQ("a3", Nodes[2]); - Nodes.clear(); - - EXPECT_EQ(RC.end(), J); + EXPECT_THAT(A, + UnorderedElementsAre(IsNode("a1"), IsNode("a2"), IsNode("a3"))); + + EXPECT_THAT(J, Eq(RC.end())); } TEST(LazyCallGraphTest, MultiArmSCC) { @@ -530,27 +519,27 @@ // Force the graph to be fully expanded. auto I = CG.postorder_ref_scc_begin(); LazyCallGraph::RefSCC &RC = *I++; - EXPECT_EQ(CG.postorder_ref_scc_end(), I); + EXPECT_THAT(I, Eq(CG.postorder_ref_scc_end())); LazyCallGraph::Node &N1 = *CG.lookup(lookupFunction(*M, "f1")); LazyCallGraph::Node &N2 = *CG.lookup(lookupFunction(*M, "f2")); LazyCallGraph::Node &N3 = *CG.lookup(lookupFunction(*M, "f3")); LazyCallGraph::Node &N4 = *CG.lookup(lookupFunction(*M, "f4")); LazyCallGraph::Node &N5 = *CG.lookup(lookupFunction(*M, "f4")); - EXPECT_EQ(&RC, CG.lookupRefSCC(N1)); - EXPECT_EQ(&RC, CG.lookupRefSCC(N2)); - EXPECT_EQ(&RC, CG.lookupRefSCC(N3)); - EXPECT_EQ(&RC, CG.lookupRefSCC(N4)); - EXPECT_EQ(&RC, CG.lookupRefSCC(N5)); + EXPECT_THAT(CG.lookupRefSCC(N1), Eq(&RC)); + EXPECT_THAT(CG.lookupRefSCC(N2), Eq(&RC)); + EXPECT_THAT(CG.lookupRefSCC(N3), Eq(&RC)); + EXPECT_THAT(CG.lookupRefSCC(N4), Eq(&RC)); + EXPECT_THAT(CG.lookupRefSCC(N5), Eq(&RC)); - ASSERT_EQ(1, RC.size()); + ASSERT_THAT(RC.size(), Eq(1)); LazyCallGraph::SCC &C = *RC.begin(); - EXPECT_EQ(&C, CG.lookupSCC(N1)); - EXPECT_EQ(&C, CG.lookupSCC(N2)); - EXPECT_EQ(&C, CG.lookupSCC(N3)); - EXPECT_EQ(&C, CG.lookupSCC(N4)); - EXPECT_EQ(&C, CG.lookupSCC(N5)); + EXPECT_THAT(CG.lookupSCC(N1), Eq(&C)); + EXPECT_THAT(CG.lookupSCC(N2), Eq(&C)); + EXPECT_THAT(CG.lookupSCC(N3), Eq(&C)); + EXPECT_THAT(CG.lookupSCC(N4), Eq(&C)); + EXPECT_THAT(CG.lookupSCC(N5), Eq(&C)); } TEST(LazyCallGraphTest, OutgoingEdgeMutation) { @@ -610,13 +599,9 @@ EXPECT_TRUE(DRC.isChildOf(CRC)); EXPECT_TRUE(DC.isChildOf(CC)); - EXPECT_EQ(2, std::distance(A.begin(), A.end())); + EXPECT_THAT(A, ElementsAre(IsEdgeTo(B), IsEdgeTo(C))); ARC.insertOutgoingEdge(A, D, LazyCallGraph::Edge::Call); - EXPECT_EQ(3, std::distance(A.begin(), A.end())); - const LazyCallGraph::Edge &NewE = A[D]; - EXPECT_TRUE(NewE); - EXPECT_TRUE(NewE.isCall()); - EXPECT_EQ(&D, NewE.getNode()); + EXPECT_THAT(A, ElementsAre(IsEdgeTo(B), IsEdgeTo(C), IsCallEdgeTo(D))); // Only the parent and child tests sholud have changed. The rest of the graph // remains the same. @@ -628,17 +613,17 @@ EXPECT_TRUE(DC.isChildOf(AC)); EXPECT_TRUE(DRC.isDescendantOf(ARC)); EXPECT_TRUE(DC.isDescendantOf(AC)); - EXPECT_EQ(&AC, CG.lookupSCC(A)); - EXPECT_EQ(&BC, CG.lookupSCC(B)); - EXPECT_EQ(&CC, CG.lookupSCC(C)); - EXPECT_EQ(&DC, CG.lookupSCC(D)); - EXPECT_EQ(&ARC, CG.lookupRefSCC(A)); - EXPECT_EQ(&BRC, CG.lookupRefSCC(B)); - EXPECT_EQ(&CRC, CG.lookupRefSCC(C)); - EXPECT_EQ(&DRC, CG.lookupRefSCC(D)); + EXPECT_THAT(CG.lookupSCC(A), Eq(&AC)); + EXPECT_THAT(CG.lookupSCC(B), Eq(&BC)); + EXPECT_THAT(CG.lookupSCC(C), Eq(&CC)); + EXPECT_THAT(CG.lookupSCC(D), Eq(&DC)); + EXPECT_THAT(CG.lookupRefSCC(A), Eq(&ARC)); + EXPECT_THAT(CG.lookupRefSCC(B), Eq(&BRC)); + EXPECT_THAT(CG.lookupRefSCC(C), Eq(&CRC)); + EXPECT_THAT(CG.lookupRefSCC(D), Eq(&DRC)); ARC.switchOutgoingEdgeToRef(A, D); - EXPECT_FALSE(NewE.isCall()); + EXPECT_THAT(A, ElementsAre(IsEdgeTo(B), IsEdgeTo(C), IsRefEdgeTo(D))); // Verify the reference graph remains the same but the SCC graph is updated. EXPECT_TRUE(ARC.isParentOf(DRC)); @@ -649,17 +634,17 @@ EXPECT_FALSE(DC.isChildOf(AC)); EXPECT_TRUE(DRC.isDescendantOf(ARC)); EXPECT_TRUE(DC.isDescendantOf(AC)); - EXPECT_EQ(&AC, CG.lookupSCC(A)); - EXPECT_EQ(&BC, CG.lookupSCC(B)); - EXPECT_EQ(&CC, CG.lookupSCC(C)); - EXPECT_EQ(&DC, CG.lookupSCC(D)); - EXPECT_EQ(&ARC, CG.lookupRefSCC(A)); - EXPECT_EQ(&BRC, CG.lookupRefSCC(B)); - EXPECT_EQ(&CRC, CG.lookupRefSCC(C)); - EXPECT_EQ(&DRC, CG.lookupRefSCC(D)); + EXPECT_THAT(CG.lookupSCC(A), Eq(&AC)); + EXPECT_THAT(CG.lookupSCC(B), Eq(&BC)); + EXPECT_THAT(CG.lookupSCC(C), Eq(&CC)); + EXPECT_THAT(CG.lookupSCC(D), Eq(&DC)); + EXPECT_THAT(CG.lookupRefSCC(A), Eq(&ARC)); + EXPECT_THAT(CG.lookupRefSCC(B), Eq(&BRC)); + EXPECT_THAT(CG.lookupRefSCC(C), Eq(&CRC)); + EXPECT_THAT(CG.lookupRefSCC(D), Eq(&DRC)); ARC.switchOutgoingEdgeToCall(A, D); - EXPECT_TRUE(NewE.isCall()); + EXPECT_THAT(A, ElementsAre(IsEdgeTo(B), IsEdgeTo(C), IsCallEdgeTo(D))); // Verify the reference graph remains the same but the SCC graph is updated. EXPECT_TRUE(ARC.isParentOf(DRC)); @@ -670,17 +655,17 @@ EXPECT_TRUE(DC.isChildOf(AC)); EXPECT_TRUE(DRC.isDescendantOf(ARC)); EXPECT_TRUE(DC.isDescendantOf(AC)); - EXPECT_EQ(&AC, CG.lookupSCC(A)); - EXPECT_EQ(&BC, CG.lookupSCC(B)); - EXPECT_EQ(&CC, CG.lookupSCC(C)); - EXPECT_EQ(&DC, CG.lookupSCC(D)); - EXPECT_EQ(&ARC, CG.lookupRefSCC(A)); - EXPECT_EQ(&BRC, CG.lookupRefSCC(B)); - EXPECT_EQ(&CRC, CG.lookupRefSCC(C)); - EXPECT_EQ(&DRC, CG.lookupRefSCC(D)); + EXPECT_THAT(CG.lookupSCC(A), Eq(&AC)); + EXPECT_THAT(CG.lookupSCC(B), Eq(&BC)); + EXPECT_THAT(CG.lookupSCC(C), Eq(&CC)); + EXPECT_THAT(CG.lookupSCC(D), Eq(&DC)); + EXPECT_THAT(CG.lookupRefSCC(A), Eq(&ARC)); + EXPECT_THAT(CG.lookupRefSCC(B), Eq(&BRC)); + EXPECT_THAT(CG.lookupRefSCC(C), Eq(&CRC)); + EXPECT_THAT(CG.lookupRefSCC(D), Eq(&DRC)); ARC.removeOutgoingEdge(A, D); - EXPECT_EQ(2, std::distance(A.begin(), A.end())); + EXPECT_THAT(A, ElementsAre(IsEdgeTo(B), IsEdgeTo(C))); // Now the parent and child tests fail again but the rest remains the same. EXPECT_FALSE(ARC.isParentOf(DRC)); @@ -691,14 +676,14 @@ EXPECT_FALSE(DC.isChildOf(AC)); EXPECT_TRUE(DRC.isDescendantOf(ARC)); EXPECT_TRUE(DC.isDescendantOf(AC)); - EXPECT_EQ(&AC, CG.lookupSCC(A)); - EXPECT_EQ(&BC, CG.lookupSCC(B)); - EXPECT_EQ(&CC, CG.lookupSCC(C)); - EXPECT_EQ(&DC, CG.lookupSCC(D)); - EXPECT_EQ(&ARC, CG.lookupRefSCC(A)); - EXPECT_EQ(&BRC, CG.lookupRefSCC(B)); - EXPECT_EQ(&CRC, CG.lookupRefSCC(C)); - EXPECT_EQ(&DRC, CG.lookupRefSCC(D)); + EXPECT_THAT(CG.lookupSCC(A), Eq(&AC)); + EXPECT_THAT(CG.lookupSCC(B), Eq(&BC)); + EXPECT_THAT(CG.lookupSCC(C), Eq(&CC)); + EXPECT_THAT(CG.lookupSCC(D), Eq(&DC)); + EXPECT_THAT(CG.lookupRefSCC(A), Eq(&ARC)); + EXPECT_THAT(CG.lookupRefSCC(B), Eq(&BRC)); + EXPECT_THAT(CG.lookupRefSCC(C), Eq(&CRC)); + EXPECT_THAT(CG.lookupRefSCC(D), Eq(&DRC)); } TEST(LazyCallGraphTest, IncomingEdgeInsertion) { @@ -742,15 +727,15 @@ LazyCallGraph::RefSCC &BRC = *CG.lookupRefSCC(B1); LazyCallGraph::RefSCC &CRC = *CG.lookupRefSCC(C1); LazyCallGraph::RefSCC &DRC = *CG.lookupRefSCC(D1); - ASSERT_EQ(&ARC, CG.lookupRefSCC(A2)); - ASSERT_EQ(&ARC, CG.lookupRefSCC(A3)); - ASSERT_EQ(&BRC, CG.lookupRefSCC(B2)); - ASSERT_EQ(&BRC, CG.lookupRefSCC(B3)); - ASSERT_EQ(&CRC, CG.lookupRefSCC(C2)); - ASSERT_EQ(&CRC, CG.lookupRefSCC(C3)); - ASSERT_EQ(&DRC, CG.lookupRefSCC(D2)); - ASSERT_EQ(&DRC, CG.lookupRefSCC(D3)); - ASSERT_EQ(1, std::distance(D2.begin(), D2.end())); + ASSERT_THAT(&ARC, Eq(CG.lookupRefSCC(A2))); + ASSERT_THAT(&ARC, Eq(CG.lookupRefSCC(A3))); + ASSERT_THAT(&BRC, Eq(CG.lookupRefSCC(B2))); + ASSERT_THAT(&BRC, Eq(CG.lookupRefSCC(B3))); + ASSERT_THAT(&CRC, Eq(CG.lookupRefSCC(C2))); + ASSERT_THAT(&CRC, Eq(CG.lookupRefSCC(C3))); + ASSERT_THAT(&DRC, Eq(CG.lookupRefSCC(D2))); + ASSERT_THAT(&DRC, Eq(CG.lookupRefSCC(D3))); + ASSERT_THAT(1, Eq(std::distance(D2.begin(), D2.end()))); // Add an edge to make the graph: // @@ -766,43 +751,32 @@ // / \ | // a3--a2 | auto MergedRCs = CRC.insertIncomingRefEdge(D2, C2); - // Make sure we connected the nodes. - for (LazyCallGraph::Edge E : D2) { - if (E.getNode() == &D3) - continue; - EXPECT_EQ(&C2, E.getNode()); - } + EXPECT_THAT(D2, ElementsAre(IsEdgeTo(D3), IsEdgeTo(C2))); + // And marked the D ref-SCC as no longer valid. - EXPECT_EQ(1u, MergedRCs.size()); - EXPECT_EQ(&DRC, MergedRCs[0]); + EXPECT_THAT(MergedRCs, ElementsAre(Eq(&DRC))); // Make sure we have the correct nodes in the SCC sets. - EXPECT_EQ(&ARC, CG.lookupRefSCC(A1)); - EXPECT_EQ(&ARC, CG.lookupRefSCC(A2)); - EXPECT_EQ(&ARC, CG.lookupRefSCC(A3)); - EXPECT_EQ(&BRC, CG.lookupRefSCC(B1)); - EXPECT_EQ(&BRC, CG.lookupRefSCC(B2)); - EXPECT_EQ(&BRC, CG.lookupRefSCC(B3)); - EXPECT_EQ(&CRC, CG.lookupRefSCC(C1)); - EXPECT_EQ(&CRC, CG.lookupRefSCC(C2)); - EXPECT_EQ(&CRC, CG.lookupRefSCC(C3)); - EXPECT_EQ(&CRC, CG.lookupRefSCC(D1)); - EXPECT_EQ(&CRC, CG.lookupRefSCC(D2)); - EXPECT_EQ(&CRC, CG.lookupRefSCC(D3)); + EXPECT_THAT(CG.lookupRefSCC(A1), Eq(&ARC)); + EXPECT_THAT(CG.lookupRefSCC(A2), Eq(&ARC)); + EXPECT_THAT(CG.lookupRefSCC(A3), Eq(&ARC)); + EXPECT_THAT(CG.lookupRefSCC(B1), Eq(&BRC)); + EXPECT_THAT(CG.lookupRefSCC(B2), Eq(&BRC)); + EXPECT_THAT(CG.lookupRefSCC(B3), Eq(&BRC)); + EXPECT_THAT(CG.lookupRefSCC(C1), Eq(&CRC)); + EXPECT_THAT(CG.lookupRefSCC(C2), Eq(&CRC)); + EXPECT_THAT(CG.lookupRefSCC(C3), Eq(&CRC)); + EXPECT_THAT(CG.lookupRefSCC(D1), Eq(&CRC)); + EXPECT_THAT(CG.lookupRefSCC(D2), Eq(&CRC)); + EXPECT_THAT(CG.lookupRefSCC(D3), Eq(&CRC)); // And that ancestry tests have been updated. EXPECT_TRUE(ARC.isParentOf(CRC)); EXPECT_TRUE(BRC.isParentOf(CRC)); // And verify the post-order walk reflects the updated structure. - auto I = CG.postorder_ref_scc_begin(), E = CG.postorder_ref_scc_end(); - ASSERT_NE(I, E); - EXPECT_EQ(&CRC, &*I) << "Actual RefSCC: " << *I; - ASSERT_NE(++I, E); - EXPECT_EQ(&BRC, &*I) << "Actual RefSCC: " << *I; - ASSERT_NE(++I, E); - EXPECT_EQ(&ARC, &*I) << "Actual RefSCC: " << *I; - EXPECT_EQ(++I, E); + EXPECT_THAT(CG.postorder_ref_sccs(), + ElementsAre(Ref(CRC), Ref(BRC), Ref(ARC))); } TEST(LazyCallGraphTest, IncomingEdgeInsertionMidTraversal) { @@ -814,59 +788,59 @@ // Walk the RefSCCs until we find the one containing 'c1'. auto I = CG.postorder_ref_scc_begin(), E = CG.postorder_ref_scc_end(); - ASSERT_NE(I, E); + ASSERT_THAT(I, Ne(E)); LazyCallGraph::RefSCC &DRC = *I; - ASSERT_NE(&DRC, nullptr); + ASSERT_THAT(&DRC, NotNull()); ++I; - ASSERT_NE(I, E); + ASSERT_THAT(I, Ne(E)); LazyCallGraph::RefSCC &CRC = *I; - ASSERT_NE(&CRC, nullptr); - - ASSERT_EQ(nullptr, CG.lookup(lookupFunction(*M, "a1"))); - ASSERT_EQ(nullptr, CG.lookup(lookupFunction(*M, "a2"))); - ASSERT_EQ(nullptr, CG.lookup(lookupFunction(*M, "a3"))); - ASSERT_EQ(nullptr, CG.lookup(lookupFunction(*M, "b1"))); - ASSERT_EQ(nullptr, CG.lookup(lookupFunction(*M, "b2"))); - ASSERT_EQ(nullptr, CG.lookup(lookupFunction(*M, "b3"))); + ASSERT_THAT(&CRC, NotNull()); + + ASSERT_THAT(nullptr, Eq(CG.lookup(lookupFunction(*M, "a1")))); + ASSERT_THAT(nullptr, Eq(CG.lookup(lookupFunction(*M, "a2")))); + ASSERT_THAT(nullptr, Eq(CG.lookup(lookupFunction(*M, "a3")))); + ASSERT_THAT(nullptr, Eq(CG.lookup(lookupFunction(*M, "b1")))); + ASSERT_THAT(nullptr, Eq(CG.lookup(lookupFunction(*M, "b2")))); + ASSERT_THAT(nullptr, Eq(CG.lookup(lookupFunction(*M, "b3")))); LazyCallGraph::Node &C1 = *CG.lookup(lookupFunction(*M, "c1")); LazyCallGraph::Node &C2 = *CG.lookup(lookupFunction(*M, "c2")); LazyCallGraph::Node &C3 = *CG.lookup(lookupFunction(*M, "c3")); LazyCallGraph::Node &D1 = *CG.lookup(lookupFunction(*M, "d1")); LazyCallGraph::Node &D2 = *CG.lookup(lookupFunction(*M, "d2")); LazyCallGraph::Node &D3 = *CG.lookup(lookupFunction(*M, "d3")); - ASSERT_EQ(&CRC, CG.lookupRefSCC(C1)); - ASSERT_EQ(&CRC, CG.lookupRefSCC(C2)); - ASSERT_EQ(&CRC, CG.lookupRefSCC(C3)); - ASSERT_EQ(&DRC, CG.lookupRefSCC(D1)); - ASSERT_EQ(&DRC, CG.lookupRefSCC(D2)); - ASSERT_EQ(&DRC, CG.lookupRefSCC(D3)); - ASSERT_EQ(1, std::distance(D2.begin(), D2.end())); + ASSERT_THAT(&CRC, Eq(CG.lookupRefSCC(C1))); + ASSERT_THAT(&CRC, Eq(CG.lookupRefSCC(C2))); + ASSERT_THAT(&CRC, Eq(CG.lookupRefSCC(C3))); + ASSERT_THAT(&DRC, Eq(CG.lookupRefSCC(D1))); + ASSERT_THAT(&DRC, Eq(CG.lookupRefSCC(D2))); + ASSERT_THAT(&DRC, Eq(CG.lookupRefSCC(D3))); + ASSERT_THAT(1, Eq(std::distance(D2.begin(), D2.end()))); auto MergedRCs = CRC.insertIncomingRefEdge(D2, C2); // Make sure we connected the nodes. for (LazyCallGraph::Edge E : D2) { if (E.getNode() == &D3) continue; - EXPECT_EQ(&C2, E.getNode()); + EXPECT_THAT(E.getNode(), Eq(&C2)); } // And marked the D ref-SCC as no longer valid. - EXPECT_EQ(1u, MergedRCs.size()); - EXPECT_EQ(&DRC, MergedRCs[0]); + EXPECT_THAT(MergedRCs.size(), Eq(1u)); + EXPECT_THAT(MergedRCs[0], Eq(&DRC)); // Make sure we have the correct nodes in the RefSCCs. - EXPECT_EQ(&CRC, CG.lookupRefSCC(C1)); - EXPECT_EQ(&CRC, CG.lookupRefSCC(C2)); - EXPECT_EQ(&CRC, CG.lookupRefSCC(C3)); - EXPECT_EQ(&CRC, CG.lookupRefSCC(D1)); - EXPECT_EQ(&CRC, CG.lookupRefSCC(D2)); - EXPECT_EQ(&CRC, CG.lookupRefSCC(D3)); + EXPECT_THAT(CG.lookupRefSCC(C1), Eq(&CRC)); + EXPECT_THAT(CG.lookupRefSCC(C2), Eq(&CRC)); + EXPECT_THAT(CG.lookupRefSCC(C3), Eq(&CRC)); + EXPECT_THAT(CG.lookupRefSCC(D1), Eq(&CRC)); + EXPECT_THAT(CG.lookupRefSCC(D2), Eq(&CRC)); + EXPECT_THAT(CG.lookupRefSCC(D3), Eq(&CRC)); // Verify that the post-order walk reflects the updated but still incomplete // structure. auto J = CG.postorder_ref_scc_begin(); EXPECT_NE(J, E); EXPECT_EQ(&CRC, &*J) << "Actual RefSCC: " << *J; - EXPECT_EQ(I, J); + EXPECT_THAT(J, Eq(I)); // Check that we can form the last two RefSCCs now, and even that we can do // it with alternating iterators. @@ -874,12 +848,12 @@ EXPECT_NE(J, E); LazyCallGraph::RefSCC &BRC = *J; EXPECT_NE(&BRC, nullptr); - EXPECT_EQ(&BRC, CG.lookupRefSCC(*CG.lookup(lookupFunction(*M, "b1")))); - EXPECT_EQ(&BRC, CG.lookupRefSCC(*CG.lookup(lookupFunction(*M, "b2")))); - EXPECT_EQ(&BRC, CG.lookupRefSCC(*CG.lookup(lookupFunction(*M, "b3")))); + EXPECT_THAT(CG.lookupRefSCC(*CG.lookup(lookupFunction(*M, "b1"))), Eq(&BRC)); + EXPECT_THAT(CG.lookupRefSCC(*CG.lookup(lookupFunction(*M, "b2"))), Eq(&BRC)); + EXPECT_THAT(CG.lookupRefSCC(*CG.lookup(lookupFunction(*M, "b3"))), Eq(&BRC)); EXPECT_TRUE(BRC.isParentOf(CRC)); ++I; - EXPECT_EQ(J, I); + EXPECT_THAT(I, Eq(J)); EXPECT_EQ(&BRC, &*I) << "Actual RefSCC: " << *I; // Increment I this time to form the new RefSCC, flopping back to the first @@ -888,17 +862,17 @@ EXPECT_NE(I, E); LazyCallGraph::RefSCC &ARC = *I; EXPECT_NE(&ARC, nullptr); - EXPECT_EQ(&ARC, CG.lookupRefSCC(*CG.lookup(lookupFunction(*M, "a1")))); - EXPECT_EQ(&ARC, CG.lookupRefSCC(*CG.lookup(lookupFunction(*M, "a2")))); - EXPECT_EQ(&ARC, CG.lookupRefSCC(*CG.lookup(lookupFunction(*M, "a3")))); + EXPECT_THAT(CG.lookupRefSCC(*CG.lookup(lookupFunction(*M, "a1"))), Eq(&ARC)); + EXPECT_THAT(CG.lookupRefSCC(*CG.lookup(lookupFunction(*M, "a2"))), Eq(&ARC)); + EXPECT_THAT(CG.lookupRefSCC(*CG.lookup(lookupFunction(*M, "a3"))), Eq(&ARC)); EXPECT_TRUE(ARC.isParentOf(CRC)); ++J; - EXPECT_EQ(I, J); + EXPECT_THAT(J, Eq(I)); EXPECT_EQ(&ARC, &*J) << "Actual RefSCC: " << *J; ++I; - EXPECT_EQ(E, I); + EXPECT_THAT(I, Eq(E)); ++J; - EXPECT_EQ(E, J); + EXPECT_THAT(J, Eq(E)); } TEST(LazyCallGraphTest, IncomingEdgeInsertionRefGraph) { @@ -929,15 +903,15 @@ LazyCallGraph::RefSCC &BRC = *CG.lookupRefSCC(B1); LazyCallGraph::RefSCC &CRC = *CG.lookupRefSCC(C1); LazyCallGraph::RefSCC &DRC = *CG.lookupRefSCC(D1); - ASSERT_EQ(&ARC, CG.lookupRefSCC(A2)); - ASSERT_EQ(&ARC, CG.lookupRefSCC(A3)); - ASSERT_EQ(&BRC, CG.lookupRefSCC(B2)); - ASSERT_EQ(&BRC, CG.lookupRefSCC(B3)); - ASSERT_EQ(&CRC, CG.lookupRefSCC(C2)); - ASSERT_EQ(&CRC, CG.lookupRefSCC(C3)); - ASSERT_EQ(&DRC, CG.lookupRefSCC(D2)); - ASSERT_EQ(&DRC, CG.lookupRefSCC(D3)); - ASSERT_EQ(1, std::distance(D2.begin(), D2.end())); + ASSERT_THAT(&ARC, Eq(CG.lookupRefSCC(A2))); + ASSERT_THAT(&ARC, Eq(CG.lookupRefSCC(A3))); + ASSERT_THAT(&BRC, Eq(CG.lookupRefSCC(B2))); + ASSERT_THAT(&BRC, Eq(CG.lookupRefSCC(B3))); + ASSERT_THAT(&CRC, Eq(CG.lookupRefSCC(C2))); + ASSERT_THAT(&CRC, Eq(CG.lookupRefSCC(C3))); + ASSERT_THAT(&DRC, Eq(CG.lookupRefSCC(D2))); + ASSERT_THAT(&DRC, Eq(CG.lookupRefSCC(D3))); + ASSERT_THAT(1, Eq(std::distance(D2.begin(), D2.end()))); // Add an edge to make the graph: // @@ -957,25 +931,25 @@ for (LazyCallGraph::Edge E : D2) { if (E.getNode() == &D3) continue; - EXPECT_EQ(&C2, E.getNode()); + EXPECT_THAT(E.getNode(), Eq(&C2)); } // And marked the D ref-SCC as no longer valid. - EXPECT_EQ(1u, MergedRCs.size()); - EXPECT_EQ(&DRC, MergedRCs[0]); + EXPECT_THAT(MergedRCs.size(), Eq(1u)); + EXPECT_THAT(MergedRCs[0], Eq(&DRC)); // Make sure we have the correct nodes in the SCC sets. - EXPECT_EQ(&ARC, CG.lookupRefSCC(A1)); - EXPECT_EQ(&ARC, CG.lookupRefSCC(A2)); - EXPECT_EQ(&ARC, CG.lookupRefSCC(A3)); - EXPECT_EQ(&BRC, CG.lookupRefSCC(B1)); - EXPECT_EQ(&BRC, CG.lookupRefSCC(B2)); - EXPECT_EQ(&BRC, CG.lookupRefSCC(B3)); - EXPECT_EQ(&CRC, CG.lookupRefSCC(C1)); - EXPECT_EQ(&CRC, CG.lookupRefSCC(C2)); - EXPECT_EQ(&CRC, CG.lookupRefSCC(C3)); - EXPECT_EQ(&CRC, CG.lookupRefSCC(D1)); - EXPECT_EQ(&CRC, CG.lookupRefSCC(D2)); - EXPECT_EQ(&CRC, CG.lookupRefSCC(D3)); + EXPECT_THAT(CG.lookupRefSCC(A1), Eq(&ARC)); + EXPECT_THAT(CG.lookupRefSCC(A2), Eq(&ARC)); + EXPECT_THAT(CG.lookupRefSCC(A3), Eq(&ARC)); + EXPECT_THAT(CG.lookupRefSCC(B1), Eq(&BRC)); + EXPECT_THAT(CG.lookupRefSCC(B2), Eq(&BRC)); + EXPECT_THAT(CG.lookupRefSCC(B3), Eq(&BRC)); + EXPECT_THAT(CG.lookupRefSCC(C1), Eq(&CRC)); + EXPECT_THAT(CG.lookupRefSCC(C2), Eq(&CRC)); + EXPECT_THAT(CG.lookupRefSCC(C3), Eq(&CRC)); + EXPECT_THAT(CG.lookupRefSCC(D1), Eq(&CRC)); + EXPECT_THAT(CG.lookupRefSCC(D2), Eq(&CRC)); + EXPECT_THAT(CG.lookupRefSCC(D3), Eq(&CRC)); // And that ancestry tests have been updated. EXPECT_TRUE(ARC.isParentOf(CRC)); @@ -983,13 +957,13 @@ // And verify the post-order walk reflects the updated structure. auto I = CG.postorder_ref_scc_begin(), E = CG.postorder_ref_scc_end(); - ASSERT_NE(I, E); + ASSERT_THAT(I, Ne(E)); EXPECT_EQ(&CRC, &*I) << "Actual RefSCC: " << *I; - ASSERT_NE(++I, E); + ASSERT_THAT(++I, Ne(E)); EXPECT_EQ(&BRC, &*I) << "Actual RefSCC: " << *I; - ASSERT_NE(++I, E); + ASSERT_THAT(++I, Ne(E)); EXPECT_EQ(&ARC, &*I) << "Actual RefSCC: " << *I; - EXPECT_EQ(++I, E); + EXPECT_THAT(E, Eq(++I)); } TEST(LazyCallGraphTest, IncomingEdgeInsertionLargeCallCycle) { @@ -1036,32 +1010,32 @@ auto MergedRCs = ARC.insertIncomingRefEdge(D, A); // Make sure we connected the nodes. EXPECT_NE(D.begin(), D.end()); - EXPECT_EQ(&A, D.begin()->getNode()); + EXPECT_THAT(D.begin()->getNode(), Eq(&A)); // Check that we have the dead RCs, but ignore the order. - EXPECT_EQ(3u, MergedRCs.size()); + EXPECT_THAT(MergedRCs.size(), Eq(3u)); EXPECT_NE(find(MergedRCs, &BRC), MergedRCs.end()); EXPECT_NE(find(MergedRCs, &CRC), MergedRCs.end()); EXPECT_NE(find(MergedRCs, &DRC), MergedRCs.end()); // Make sure the nodes point to the right place now. - EXPECT_EQ(&ARC, CG.lookupRefSCC(A)); - EXPECT_EQ(&ARC, CG.lookupRefSCC(B)); - EXPECT_EQ(&ARC, CG.lookupRefSCC(C)); - EXPECT_EQ(&ARC, CG.lookupRefSCC(D)); + EXPECT_THAT(CG.lookupRefSCC(A), Eq(&ARC)); + EXPECT_THAT(CG.lookupRefSCC(B), Eq(&ARC)); + EXPECT_THAT(CG.lookupRefSCC(C), Eq(&ARC)); + EXPECT_THAT(CG.lookupRefSCC(D), Eq(&ARC)); // Check that the SCCs are in postorder. - EXPECT_EQ(4, ARC.size()); - EXPECT_EQ(&DC, &ARC[0]); - EXPECT_EQ(&CC, &ARC[1]); - EXPECT_EQ(&BC, &ARC[2]); - EXPECT_EQ(&AC, &ARC[3]); + EXPECT_THAT(ARC.size(), Eq(4)); + EXPECT_THAT(&ARC[0], Eq(&DC)); + EXPECT_THAT(&ARC[1], Eq(&CC)); + EXPECT_THAT(&ARC[2], Eq(&BC)); + EXPECT_THAT(&ARC[3], Eq(&AC)); // And verify the post-order walk reflects the updated structure. auto I = CG.postorder_ref_scc_begin(), E = CG.postorder_ref_scc_end(); - ASSERT_NE(I, E); + ASSERT_THAT(I, Ne(E)); EXPECT_EQ(&ARC, &*I) << "Actual RefSCC: " << *I; - EXPECT_EQ(++I, E); + EXPECT_THAT(E, Eq(++I)); } TEST(LazyCallGraphTest, IncomingEdgeInsertionLargeRefCycle) { @@ -1109,25 +1083,25 @@ auto MergedRCs = ARC.insertIncomingRefEdge(D, A); // Make sure we connected the nodes. EXPECT_NE(D.begin(), D.end()); - EXPECT_EQ(&A, D.begin()->getNode()); + EXPECT_THAT(D.begin()->getNode(), Eq(&A)); // Check that we have the dead RCs, but ignore the order. - EXPECT_EQ(3u, MergedRCs.size()); + EXPECT_THAT(MergedRCs.size(), Eq(3u)); EXPECT_NE(find(MergedRCs, &BRC), MergedRCs.end()); EXPECT_NE(find(MergedRCs, &CRC), MergedRCs.end()); EXPECT_NE(find(MergedRCs, &DRC), MergedRCs.end()); // Make sure the nodes point to the right place now. - EXPECT_EQ(&ARC, CG.lookupRefSCC(A)); - EXPECT_EQ(&ARC, CG.lookupRefSCC(B)); - EXPECT_EQ(&ARC, CG.lookupRefSCC(C)); - EXPECT_EQ(&ARC, CG.lookupRefSCC(D)); + EXPECT_THAT(CG.lookupRefSCC(A), Eq(&ARC)); + EXPECT_THAT(CG.lookupRefSCC(B), Eq(&ARC)); + EXPECT_THAT(CG.lookupRefSCC(C), Eq(&ARC)); + EXPECT_THAT(CG.lookupRefSCC(D), Eq(&ARC)); // And verify the post-order walk reflects the updated structure. auto I = CG.postorder_ref_scc_begin(), End = CG.postorder_ref_scc_end(); - ASSERT_NE(I, End); + ASSERT_THAT(I, Ne(End)); EXPECT_EQ(&ARC, &*I) << "Actual RefSCC: " << *I; - EXPECT_EQ(++I, End); + EXPECT_THAT(End, Eq(++I)); } TEST(LazyCallGraphTest, InlineAndDeleteFunction) { @@ -1172,15 +1146,15 @@ LazyCallGraph::RefSCC &BRC = *CG.lookupRefSCC(B1); LazyCallGraph::RefSCC &CRC = *CG.lookupRefSCC(C1); LazyCallGraph::RefSCC &DRC = *CG.lookupRefSCC(D1); - ASSERT_EQ(&ARC, CG.lookupRefSCC(A2)); - ASSERT_EQ(&ARC, CG.lookupRefSCC(A3)); - ASSERT_EQ(&BRC, CG.lookupRefSCC(B2)); - ASSERT_EQ(&BRC, CG.lookupRefSCC(B3)); - ASSERT_EQ(&CRC, CG.lookupRefSCC(C2)); - ASSERT_EQ(&CRC, CG.lookupRefSCC(C3)); - ASSERT_EQ(&DRC, CG.lookupRefSCC(D2)); - ASSERT_EQ(&DRC, CG.lookupRefSCC(D3)); - ASSERT_EQ(1, std::distance(D2.begin(), D2.end())); + ASSERT_THAT(&ARC, Eq(CG.lookupRefSCC(A2))); + ASSERT_THAT(&ARC, Eq(CG.lookupRefSCC(A3))); + ASSERT_THAT(&BRC, Eq(CG.lookupRefSCC(B2))); + ASSERT_THAT(&BRC, Eq(CG.lookupRefSCC(B3))); + ASSERT_THAT(&CRC, Eq(CG.lookupRefSCC(C2))); + ASSERT_THAT(&CRC, Eq(CG.lookupRefSCC(C3))); + ASSERT_THAT(&DRC, Eq(CG.lookupRefSCC(D2))); + ASSERT_THAT(&DRC, Eq(CG.lookupRefSCC(D3))); + ASSERT_THAT(D2, ElementsAre(_)); // Delete d2 from the graph, as if it had been inlined. // @@ -1200,24 +1174,24 @@ CallInst *C1Call = nullptr, *D1Call = nullptr; for (User *U : D2F.users()) { CallInst *CI = dyn_cast(U); - ASSERT_TRUE(CI) << "Expected a call: " << *U; + ASSERT_THAT(CI, NotNull()) << "Expected a call: " << *U; if (CI->getParent()->getParent() == &C1.getFunction()) { - ASSERT_EQ(nullptr, C1Call) << "Found too many C1 calls: " << *CI; + ASSERT_THAT(C1Call, IsNull()) << "Found too many C1 calls: " << *CI; C1Call = CI; } else if (CI->getParent()->getParent() == &D1.getFunction()) { - ASSERT_EQ(nullptr, D1Call) << "Found too many D1 calls: " << *CI; + ASSERT_THAT(D1Call, IsNull()) << "Found too many D1 calls: " << *CI; D1Call = CI; } else { FAIL() << "Found an unexpected call instruction: " << *CI; } } - ASSERT_NE(C1Call, nullptr); - ASSERT_NE(D1Call, nullptr); - ASSERT_EQ(&D2F, C1Call->getCalledFunction()); - ASSERT_EQ(&D2F, D1Call->getCalledFunction()); + ASSERT_THAT(C1Call, NotNull()); + ASSERT_THAT(D1Call, NotNull()); + ASSERT_THAT(&D2F, Eq(C1Call->getCalledFunction())); + ASSERT_THAT(&D2F, Eq(D1Call->getCalledFunction())); C1Call->setCalledFunction(&D3.getFunction()); D1Call->setCalledFunction(&D3.getFunction()); - ASSERT_EQ(0u, D2F.getNumUses()); + ASSERT_THAT(0u, Eq(D2F.getNumUses())); // Insert new edges first. CRC.insertTrivialCallEdge(C1, D3); @@ -1226,17 +1200,17 @@ // Then remove the old ones. LazyCallGraph::SCC &DC = *CG.lookupSCC(D2); auto NewCs = DRC.switchInternalEdgeToRef(D1, D2); - EXPECT_EQ(&DC, CG.lookupSCC(D2)); - EXPECT_EQ(NewCs.end(), std::next(NewCs.begin())); + EXPECT_THAT(CG.lookupSCC(D2), Eq(&DC)); + EXPECT_THAT(std::next(NewCs.begin()), Eq(NewCs.end())); LazyCallGraph::SCC &NewDC = *NewCs.begin(); - EXPECT_EQ(&NewDC, CG.lookupSCC(D1)); - EXPECT_EQ(&NewDC, CG.lookupSCC(D3)); + EXPECT_THAT(CG.lookupSCC(D1), Eq(&NewDC)); + EXPECT_THAT(CG.lookupSCC(D3), Eq(&NewDC)); auto NewRCs = DRC.removeInternalRefEdge(D1, D2); - EXPECT_EQ(&DRC, CG.lookupRefSCC(D2)); - EXPECT_EQ(NewRCs.end(), std::next(NewRCs.begin())); + EXPECT_THAT(CG.lookupRefSCC(D2), Eq(&DRC)); + EXPECT_THAT(std::next(NewRCs.begin()), Eq(NewRCs.end())); LazyCallGraph::RefSCC &NewDRC = **NewRCs.begin(); - EXPECT_EQ(&NewDRC, CG.lookupRefSCC(D1)); - EXPECT_EQ(&NewDRC, CG.lookupRefSCC(D3)); + EXPECT_THAT(CG.lookupRefSCC(D1), Eq(&NewDRC)); + EXPECT_THAT(CG.lookupRefSCC(D3), Eq(&NewDRC)); EXPECT_FALSE(NewDRC.isParentOf(DRC)); EXPECT_TRUE(CRC.isParentOf(DRC)); EXPECT_TRUE(CRC.isParentOf(NewDRC)); @@ -1250,30 +1224,30 @@ CG.removeDeadFunction(D2F); // Check that the graph still looks the same. - EXPECT_EQ(&ARC, CG.lookupRefSCC(A1)); - EXPECT_EQ(&ARC, CG.lookupRefSCC(A2)); - EXPECT_EQ(&ARC, CG.lookupRefSCC(A3)); - EXPECT_EQ(&BRC, CG.lookupRefSCC(B1)); - EXPECT_EQ(&BRC, CG.lookupRefSCC(B2)); - EXPECT_EQ(&BRC, CG.lookupRefSCC(B3)); - EXPECT_EQ(&CRC, CG.lookupRefSCC(C1)); - EXPECT_EQ(&CRC, CG.lookupRefSCC(C2)); - EXPECT_EQ(&CRC, CG.lookupRefSCC(C3)); - EXPECT_EQ(&NewDRC, CG.lookupRefSCC(D1)); - EXPECT_EQ(&NewDRC, CG.lookupRefSCC(D3)); + EXPECT_THAT(CG.lookupRefSCC(A1), Eq(&ARC)); + EXPECT_THAT(CG.lookupRefSCC(A2), Eq(&ARC)); + EXPECT_THAT(CG.lookupRefSCC(A3), Eq(&ARC)); + EXPECT_THAT(CG.lookupRefSCC(B1), Eq(&BRC)); + EXPECT_THAT(CG.lookupRefSCC(B2), Eq(&BRC)); + EXPECT_THAT(CG.lookupRefSCC(B3), Eq(&BRC)); + EXPECT_THAT(CG.lookupRefSCC(C1), Eq(&CRC)); + EXPECT_THAT(CG.lookupRefSCC(C2), Eq(&CRC)); + EXPECT_THAT(CG.lookupRefSCC(C3), Eq(&CRC)); + EXPECT_THAT(CG.lookupRefSCC(D1), Eq(&NewDRC)); + EXPECT_THAT(CG.lookupRefSCC(D3), Eq(&NewDRC)); EXPECT_TRUE(CRC.isParentOf(NewDRC)); // Verify the post-order walk hasn't changed. auto I = CG.postorder_ref_scc_begin(), E = CG.postorder_ref_scc_end(); - ASSERT_NE(I, E); + ASSERT_THAT(I, Ne(E)); EXPECT_EQ(&NewDRC, &*I) << "Actual RefSCC: " << *I; - ASSERT_NE(++I, E); + ASSERT_THAT(++I, Ne(E)); EXPECT_EQ(&CRC, &*I) << "Actual RefSCC: " << *I; - ASSERT_NE(++I, E); + ASSERT_THAT(++I, Ne(E)); EXPECT_EQ(&BRC, &*I) << "Actual RefSCC: " << *I; - ASSERT_NE(++I, E); + ASSERT_THAT(++I, Ne(E)); EXPECT_EQ(&ARC, &*I) << "Actual RefSCC: " << *I; - EXPECT_EQ(++I, E); + EXPECT_THAT(E, Eq(++I)); } TEST(LazyCallGraphTest, InlineAndDeleteFunctionMidTraversal) { @@ -1300,33 +1274,33 @@ // Walk the RefSCCs until we find the one containing 'c1'. auto I = CG.postorder_ref_scc_begin(), E = CG.postorder_ref_scc_end(); - ASSERT_NE(I, E); + ASSERT_THAT(I, Ne(E)); LazyCallGraph::RefSCC &DRC = *I; - ASSERT_NE(&DRC, nullptr); + ASSERT_THAT(&DRC, NotNull()); ++I; - ASSERT_NE(I, E); + ASSERT_THAT(I, Ne(E)); LazyCallGraph::RefSCC &CRC = *I; - ASSERT_NE(&CRC, nullptr); - - ASSERT_EQ(nullptr, CG.lookup(lookupFunction(*M, "a1"))); - ASSERT_EQ(nullptr, CG.lookup(lookupFunction(*M, "a2"))); - ASSERT_EQ(nullptr, CG.lookup(lookupFunction(*M, "a3"))); - ASSERT_EQ(nullptr, CG.lookup(lookupFunction(*M, "b1"))); - ASSERT_EQ(nullptr, CG.lookup(lookupFunction(*M, "b2"))); - ASSERT_EQ(nullptr, CG.lookup(lookupFunction(*M, "b3"))); + ASSERT_THAT(&CRC, NotNull()); + + ASSERT_THAT(nullptr, Eq(CG.lookup(lookupFunction(*M, "a1")))); + ASSERT_THAT(nullptr, Eq(CG.lookup(lookupFunction(*M, "a2")))); + ASSERT_THAT(nullptr, Eq(CG.lookup(lookupFunction(*M, "a3")))); + ASSERT_THAT(nullptr, Eq(CG.lookup(lookupFunction(*M, "b1")))); + ASSERT_THAT(nullptr, Eq(CG.lookup(lookupFunction(*M, "b2")))); + ASSERT_THAT(nullptr, Eq(CG.lookup(lookupFunction(*M, "b3")))); LazyCallGraph::Node &C1 = *CG.lookup(lookupFunction(*M, "c1")); LazyCallGraph::Node &C2 = *CG.lookup(lookupFunction(*M, "c2")); LazyCallGraph::Node &C3 = *CG.lookup(lookupFunction(*M, "c3")); LazyCallGraph::Node &D1 = *CG.lookup(lookupFunction(*M, "d1")); LazyCallGraph::Node &D2 = *CG.lookup(lookupFunction(*M, "d2")); LazyCallGraph::Node &D3 = *CG.lookup(lookupFunction(*M, "d3")); - ASSERT_EQ(&CRC, CG.lookupRefSCC(C1)); - ASSERT_EQ(&CRC, CG.lookupRefSCC(C2)); - ASSERT_EQ(&CRC, CG.lookupRefSCC(C3)); - ASSERT_EQ(&DRC, CG.lookupRefSCC(D1)); - ASSERT_EQ(&DRC, CG.lookupRefSCC(D2)); - ASSERT_EQ(&DRC, CG.lookupRefSCC(D3)); - ASSERT_EQ(1, std::distance(D2.begin(), D2.end())); + ASSERT_THAT(&CRC, Eq(CG.lookupRefSCC(C1))); + ASSERT_THAT(&CRC, Eq(CG.lookupRefSCC(C2))); + ASSERT_THAT(&CRC, Eq(CG.lookupRefSCC(C3))); + ASSERT_THAT(&DRC, Eq(CG.lookupRefSCC(D1))); + ASSERT_THAT(&DRC, Eq(CG.lookupRefSCC(D2))); + ASSERT_THAT(&DRC, Eq(CG.lookupRefSCC(D3))); + ASSERT_THAT(1, Eq(std::distance(D2.begin(), D2.end()))); // Delete d2 from the graph, as if it had been inlined. // @@ -1357,13 +1331,13 @@ FAIL() << "Found an unexpected call instruction: " << *CI; } } - ASSERT_NE(C1Call, nullptr); - ASSERT_NE(D1Call, nullptr); - ASSERT_EQ(&D2F, C1Call->getCalledFunction()); - ASSERT_EQ(&D2F, D1Call->getCalledFunction()); + ASSERT_THAT(C1Call, NotNull()); + ASSERT_THAT(C1Call->getCalledFunction(), Eq(&D2F)); + ASSERT_THAT(D1Call, NotNull()); + ASSERT_THAT(D1Call->getCalledFunction(), Eq(&D2F)); C1Call->setCalledFunction(&D3.getFunction()); D1Call->setCalledFunction(&D3.getFunction()); - ASSERT_EQ(0u, D2F.getNumUses()); + ASSERT_THAT(D2F.uses(), ElementsAre()); // Insert new edges first. CRC.insertTrivialCallEdge(C1, D3); @@ -1372,17 +1346,17 @@ // Then remove the old ones. LazyCallGraph::SCC &DC = *CG.lookupSCC(D2); auto NewCs = DRC.switchInternalEdgeToRef(D1, D2); - EXPECT_EQ(&DC, CG.lookupSCC(D2)); - EXPECT_EQ(NewCs.end(), std::next(NewCs.begin())); + EXPECT_THAT(CG.lookupSCC(D2), Eq(&DC)); + ASSERT_THAT(NewCs, ElementsAre(_)); LazyCallGraph::SCC &NewDC = *NewCs.begin(); - EXPECT_EQ(&NewDC, CG.lookupSCC(D1)); - EXPECT_EQ(&NewDC, CG.lookupSCC(D3)); + EXPECT_THAT(CG.lookupSCC(D1), Eq(&NewDC)); + EXPECT_THAT(CG.lookupSCC(D3), Eq(&NewDC)); auto NewRCs = DRC.removeInternalRefEdge(D1, D2); - EXPECT_EQ(&DRC, CG.lookupRefSCC(D2)); - EXPECT_EQ(NewRCs.end(), std::next(NewRCs.begin())); + EXPECT_THAT(CG.lookupRefSCC(D2), Eq(&DRC)); + ASSERT_THAT(NewRCs, ElementsAre(_)); LazyCallGraph::RefSCC &NewDRC = **NewRCs.begin(); - EXPECT_EQ(&NewDRC, CG.lookupRefSCC(D1)); - EXPECT_EQ(&NewDRC, CG.lookupRefSCC(D3)); + EXPECT_THAT(CG.lookupRefSCC(D1), Eq(&NewDRC)); + EXPECT_THAT(CG.lookupRefSCC(D3), Eq(&NewDRC)); EXPECT_FALSE(NewDRC.isParentOf(DRC)); EXPECT_TRUE(CRC.isParentOf(DRC)); EXPECT_TRUE(CRC.isParentOf(NewDRC)); @@ -1396,11 +1370,11 @@ CG.removeDeadFunction(D2F); // Check that the graph still looks the same. - EXPECT_EQ(&CRC, CG.lookupRefSCC(C1)); - EXPECT_EQ(&CRC, CG.lookupRefSCC(C2)); - EXPECT_EQ(&CRC, CG.lookupRefSCC(C3)); - EXPECT_EQ(&NewDRC, CG.lookupRefSCC(D1)); - EXPECT_EQ(&NewDRC, CG.lookupRefSCC(D3)); + EXPECT_THAT(CG.lookupRefSCC(C1), Eq(&CRC)); + EXPECT_THAT(CG.lookupRefSCC(C2), Eq(&CRC)); + EXPECT_THAT(CG.lookupRefSCC(C3), Eq(&CRC)); + EXPECT_THAT(CG.lookupRefSCC(D1), Eq(&NewDRC)); + EXPECT_THAT(CG.lookupRefSCC(D3), Eq(&NewDRC)); EXPECT_TRUE(CRC.isParentOf(NewDRC)); // Verify that the post-order walk reflects the updated but still incomplete @@ -1411,7 +1385,7 @@ ++J; EXPECT_NE(J, E); EXPECT_EQ(&CRC, &*J) << "Actual RefSCC: " << *J; - EXPECT_EQ(I, J); + EXPECT_THAT(J, Eq(I)); // Check that we can form the last two RefSCCs now, and even that we can do // it with alternating iterators. @@ -1419,12 +1393,12 @@ EXPECT_NE(J, E); LazyCallGraph::RefSCC &BRC = *J; EXPECT_NE(&BRC, nullptr); - EXPECT_EQ(&BRC, CG.lookupRefSCC(*CG.lookup(lookupFunction(*M, "b1")))); - EXPECT_EQ(&BRC, CG.lookupRefSCC(*CG.lookup(lookupFunction(*M, "b2")))); - EXPECT_EQ(&BRC, CG.lookupRefSCC(*CG.lookup(lookupFunction(*M, "b3")))); + EXPECT_THAT(CG.lookupRefSCC(*CG.lookup(lookupFunction(*M, "b1"))), Eq(&BRC)); + EXPECT_THAT(CG.lookupRefSCC(*CG.lookup(lookupFunction(*M, "b2"))), Eq(&BRC)); + EXPECT_THAT(CG.lookupRefSCC(*CG.lookup(lookupFunction(*M, "b3"))), Eq(&BRC)); EXPECT_TRUE(BRC.isParentOf(NewDRC)); ++I; - EXPECT_EQ(J, I); + EXPECT_THAT(I, Eq(J)); EXPECT_EQ(&BRC, &*I) << "Actual RefSCC: " << *I; // Increment I this time to form the new RefSCC, flopping back to the first @@ -1433,18 +1407,18 @@ EXPECT_NE(I, E); LazyCallGraph::RefSCC &ARC = *I; EXPECT_NE(&ARC, nullptr); - EXPECT_EQ(&ARC, CG.lookupRefSCC(*CG.lookup(lookupFunction(*M, "a1")))); - EXPECT_EQ(&ARC, CG.lookupRefSCC(*CG.lookup(lookupFunction(*M, "a2")))); - EXPECT_EQ(&ARC, CG.lookupRefSCC(*CG.lookup(lookupFunction(*M, "a3")))); + EXPECT_THAT(CG.lookupRefSCC(*CG.lookup(lookupFunction(*M, "a1"))), Eq(&ARC)); + EXPECT_THAT(CG.lookupRefSCC(*CG.lookup(lookupFunction(*M, "a2"))), Eq(&ARC)); + EXPECT_THAT(CG.lookupRefSCC(*CG.lookup(lookupFunction(*M, "a3"))), Eq(&ARC)); EXPECT_TRUE(ARC.isParentOf(BRC)); EXPECT_TRUE(ARC.isParentOf(CRC)); ++J; - EXPECT_EQ(I, J); + EXPECT_THAT(J, Eq(I)); EXPECT_EQ(&ARC, &*J) << "Actual RefSCC: " << *J; ++I; - EXPECT_EQ(E, I); + EXPECT_THAT(I, Eq(E)); ++J; - EXPECT_EQ(E, J); + EXPECT_THAT(J, Eq(E)); } TEST(LazyCallGraphTest, InternalEdgeMutation) { @@ -1467,51 +1441,47 @@ LazyCallGraph CG(*M); // Force the graph to be fully expanded. - auto I = CG.postorder_ref_scc_begin(); - LazyCallGraph::RefSCC &RC = *I++; - EXPECT_EQ(CG.postorder_ref_scc_end(), I); + ASSERT_THAT(CG.postorder_ref_sccs(), ElementsAre(_)); + LazyCallGraph::RefSCC &RC = *CG.postorder_ref_scc_begin(); LazyCallGraph::Node &A = *CG.lookup(lookupFunction(*M, "a")); LazyCallGraph::Node &B = *CG.lookup(lookupFunction(*M, "b")); LazyCallGraph::Node &C = *CG.lookup(lookupFunction(*M, "c")); - EXPECT_EQ(&RC, CG.lookupRefSCC(A)); - EXPECT_EQ(&RC, CG.lookupRefSCC(B)); - EXPECT_EQ(&RC, CG.lookupRefSCC(C)); - EXPECT_EQ(1, RC.size()); - EXPECT_EQ(&*RC.begin(), CG.lookupSCC(A)); - EXPECT_EQ(&*RC.begin(), CG.lookupSCC(B)); - EXPECT_EQ(&*RC.begin(), CG.lookupSCC(C)); + EXPECT_THAT(CG.lookupRefSCC(A), Eq(&RC)); + EXPECT_THAT(CG.lookupRefSCC(B), Eq(&RC)); + EXPECT_THAT(CG.lookupRefSCC(C), Eq(&RC)); + ASSERT_THAT(RC, ElementsAre(_)); + EXPECT_THAT(CG.lookupSCC(A), Eq(&*RC.begin())); + EXPECT_THAT(CG.lookupSCC(B), Eq(&*RC.begin())); + EXPECT_THAT(CG.lookupSCC(C), Eq(&*RC.begin())); // Insert an edge from 'a' to 'c'. Nothing changes about the graph. RC.insertInternalRefEdge(A, C); - EXPECT_EQ(2, std::distance(A.begin(), A.end())); - EXPECT_EQ(&RC, CG.lookupRefSCC(A)); - EXPECT_EQ(&RC, CG.lookupRefSCC(B)); - EXPECT_EQ(&RC, CG.lookupRefSCC(C)); - EXPECT_EQ(1, RC.size()); - EXPECT_EQ(&*RC.begin(), CG.lookupSCC(A)); - EXPECT_EQ(&*RC.begin(), CG.lookupSCC(B)); - EXPECT_EQ(&*RC.begin(), CG.lookupSCC(C)); + EXPECT_THAT(A, ElementsAre(IsCallEdgeTo(B), IsRefEdgeTo(C))); + EXPECT_THAT(CG.lookupRefSCC(A), Eq(&RC)); + EXPECT_THAT(CG.lookupRefSCC(B), Eq(&RC)); + EXPECT_THAT(CG.lookupRefSCC(C), Eq(&RC)); + ASSERT_THAT(RC, ElementsAre(_)); + EXPECT_THAT(CG.lookupSCC(A), Eq(&*RC.begin())); + EXPECT_THAT(CG.lookupSCC(B), Eq(&*RC.begin())); + EXPECT_THAT(CG.lookupSCC(C), Eq(&*RC.begin())); // Switch the call edge from 'b' to 'c' to a ref edge. This will break the // call cycle and cause us to form more SCCs. The RefSCC will remain the same // though. auto NewCs = RC.switchInternalEdgeToRef(B, C); - EXPECT_EQ(&RC, CG.lookupRefSCC(A)); - EXPECT_EQ(&RC, CG.lookupRefSCC(B)); - EXPECT_EQ(&RC, CG.lookupRefSCC(C)); - auto J = RC.begin(); + EXPECT_THAT(B, ElementsAre(IsRefEdgeTo(C))); + EXPECT_THAT(CG.lookupRefSCC(A), Eq(&RC)); + EXPECT_THAT(CG.lookupRefSCC(B), Eq(&RC)); + EXPECT_THAT(CG.lookupRefSCC(C), Eq(&RC)); // The SCCs must be in *post-order* which means successors before // predecessors. At this point we have call edges from C to A and from A to // B. The only valid postorder is B, A, C. - EXPECT_EQ(&*J++, CG.lookupSCC(B)); - EXPECT_EQ(&*J++, CG.lookupSCC(A)); - EXPECT_EQ(&*J++, CG.lookupSCC(C)); - EXPECT_EQ(RC.end(), J); + EXPECT_THAT(RC, ElementsAre(Ref(*CG.lookupSCC(B)), Ref(*CG.lookupSCC(A)), + Ref(*CG.lookupSCC(C)))); // And the returned range must be the slice of this sequence containing new // SCCs. - EXPECT_EQ(RC.begin(), NewCs.begin()); - EXPECT_EQ(std::prev(RC.end()), NewCs.end()); + EXPECT_THAT(NewCs, ElementsAre(Ref(*CG.lookupSCC(B)), Ref(*CG.lookupSCC(A)))); // Test turning the ref edge from A to C into a call edge. This will form an // SCC out of A and C. Since we previously had a call edge from C to A, the @@ -1520,15 +1490,12 @@ LazyCallGraph::SCC &AC = *CG.lookupSCC(A); LazyCallGraph::SCC &CC = *CG.lookupSCC(C); auto InvalidatedSCCs = RC.switchInternalEdgeToCall(A, C); - ASSERT_EQ(1u, InvalidatedSCCs.size()); - EXPECT_EQ(&AC, InvalidatedSCCs[0]); - EXPECT_EQ(2, CC.size()); - EXPECT_EQ(&CC, CG.lookupSCC(A)); - EXPECT_EQ(&CC, CG.lookupSCC(C)); - J = RC.begin(); - EXPECT_EQ(&*J++, CG.lookupSCC(B)); - EXPECT_EQ(&*J++, CG.lookupSCC(C)); - EXPECT_EQ(RC.end(), J); + EXPECT_THAT(A, ElementsAre(IsCallEdgeTo(B), IsCallEdgeTo(C))); + EXPECT_THAT(InvalidatedSCCs, ElementsAre(&AC)); + EXPECT_THAT(CC, UnorderedElementsAre(Ref(A), Ref(C))); + EXPECT_THAT(CG.lookupSCC(A), Eq(&CC)); + EXPECT_THAT(CG.lookupSCC(C), Eq(&CC)); + EXPECT_THAT(RC, ElementsAre(Ref(*CG.lookupSCC(B)), Ref(CC))); } TEST(LazyCallGraphTest, InternalEdgeRemoval) { @@ -1559,49 +1526,36 @@ LazyCallGraph CG(*M); // Force the graph to be fully expanded. - auto I = CG.postorder_ref_scc_begin(), E = CG.postorder_ref_scc_end(); - LazyCallGraph::RefSCC &RC = *I; - EXPECT_EQ(E, std::next(I)); + EXPECT_THAT(CG.postorder_ref_sccs(), ElementsAre(_)); + LazyCallGraph::RefSCC &RC = *CG.postorder_ref_scc_begin(); LazyCallGraph::Node &A = *CG.lookup(lookupFunction(*M, "a")); LazyCallGraph::Node &B = *CG.lookup(lookupFunction(*M, "b")); LazyCallGraph::Node &C = *CG.lookup(lookupFunction(*M, "c")); - EXPECT_EQ(&RC, CG.lookupRefSCC(A)); - EXPECT_EQ(&RC, CG.lookupRefSCC(B)); - EXPECT_EQ(&RC, CG.lookupRefSCC(C)); + EXPECT_THAT(CG.lookupRefSCC(A), Eq(&RC)); + EXPECT_THAT(CG.lookupRefSCC(B), Eq(&RC)); + EXPECT_THAT(CG.lookupRefSCC(C), Eq(&RC)); // Remove the edge from b -> a, which should leave the 3 functions still in // a single connected component because of a -> b -> c -> a. - SmallVector NewRCs = - RC.removeInternalRefEdge(B, A); - EXPECT_EQ(0u, NewRCs.size()); - EXPECT_EQ(&RC, CG.lookupRefSCC(A)); - EXPECT_EQ(&RC, CG.lookupRefSCC(B)); - EXPECT_EQ(&RC, CG.lookupRefSCC(C)); - auto J = CG.postorder_ref_scc_begin(); - EXPECT_EQ(I, J); - EXPECT_EQ(&RC, &*J); - EXPECT_EQ(E, std::next(J)); + auto NewRCs = RC.removeInternalRefEdge(B, A); + EXPECT_THAT(NewRCs, ElementsAre()); + EXPECT_THAT(CG.lookupRefSCC(A), Eq(&RC)); + EXPECT_THAT(CG.lookupRefSCC(B), Eq(&RC)); + EXPECT_THAT(CG.lookupRefSCC(C), Eq(&RC)); + EXPECT_THAT(CG.postorder_ref_sccs(), ElementsAre(Ref(RC))); // Remove the edge from c -> a, which should leave 'a' in the original RefSCC // and form a new RefSCC for 'b' and 'c'. NewRCs = RC.removeInternalRefEdge(C, A); - EXPECT_EQ(1u, NewRCs.size()); - EXPECT_EQ(&RC, CG.lookupRefSCC(A)); - EXPECT_EQ(1, std::distance(RC.begin(), RC.end())); - LazyCallGraph::RefSCC &RC2 = *CG.lookupRefSCC(B); - EXPECT_EQ(&RC2, CG.lookupRefSCC(C)); - EXPECT_EQ(&RC2, NewRCs[0]); - J = CG.postorder_ref_scc_begin(); - EXPECT_NE(I, J); - EXPECT_EQ(&RC2, &*J); - ++J; - EXPECT_EQ(I, J); - EXPECT_EQ(&RC, &*J); - ++I; - EXPECT_EQ(E, I); - ++J; - EXPECT_EQ(E, J); + ASSERT_THAT(NewRCs, ElementsAre(_)); + LazyCallGraph::RefSCC &RC2 = *NewRCs[0]; + EXPECT_THAT(RC2, ElementsAre(Ref(*CG.lookupSCC(C)), Ref(*CG.lookupSCC(B)))); + EXPECT_THAT(CG.lookupRefSCC(B), Eq(&RC2)); + EXPECT_THAT(CG.lookupRefSCC(C), Eq(&RC2)); + EXPECT_THAT(RC, ElementsAre(Ref(*CG.lookupSCC(A)))); + EXPECT_THAT(CG.lookupRefSCC(A), Eq(&RC)); + EXPECT_THAT(CG.postorder_ref_sccs(), ElementsAre(Ref(RC2), Ref(RC))); } TEST(LazyCallGraphTest, InternalNoOpEdgeRemoval) { @@ -1633,53 +1587,45 @@ LazyCallGraph CG(*M); // Force the graph to be fully expanded. - auto I = CG.postorder_ref_scc_begin(), E = CG.postorder_ref_scc_end(); - LazyCallGraph::RefSCC &RC = *I; - EXPECT_EQ(E, std::next(I)); - + EXPECT_THAT(CG.postorder_ref_sccs(), ElementsAre(_)); + LazyCallGraph::RefSCC &RC = *CG.postorder_ref_scc_begin(); + EXPECT_THAT(RC, ElementsAre(_)); LazyCallGraph::SCC &C = *RC.begin(); - EXPECT_EQ(RC.end(), std::next(RC.begin())); LazyCallGraph::Node &AN = *CG.lookup(lookupFunction(*M, "a")); LazyCallGraph::Node &BN = *CG.lookup(lookupFunction(*M, "b")); LazyCallGraph::Node &CN = *CG.lookup(lookupFunction(*M, "c")); - EXPECT_EQ(&RC, CG.lookupRefSCC(AN)); - EXPECT_EQ(&RC, CG.lookupRefSCC(BN)); - EXPECT_EQ(&RC, CG.lookupRefSCC(CN)); - EXPECT_EQ(&C, CG.lookupSCC(AN)); - EXPECT_EQ(&C, CG.lookupSCC(BN)); - EXPECT_EQ(&C, CG.lookupSCC(CN)); + EXPECT_THAT(CG.lookupRefSCC(AN), Eq(&RC)); + EXPECT_THAT(CG.lookupRefSCC(BN), Eq(&RC)); + EXPECT_THAT(CG.lookupRefSCC(CN), Eq(&RC)); + EXPECT_THAT(CG.lookupSCC(AN), Eq(&C)); + EXPECT_THAT(CG.lookupSCC(BN), Eq(&C)); + EXPECT_THAT(CG.lookupSCC(CN), Eq(&C)); // Remove the edge from a -> c which doesn't change anything. - SmallVector NewRCs = - RC.removeInternalRefEdge(AN, CN); - EXPECT_EQ(0u, NewRCs.size()); - EXPECT_EQ(&RC, CG.lookupRefSCC(AN)); - EXPECT_EQ(&RC, CG.lookupRefSCC(BN)); - EXPECT_EQ(&RC, CG.lookupRefSCC(CN)); - EXPECT_EQ(&C, CG.lookupSCC(AN)); - EXPECT_EQ(&C, CG.lookupSCC(BN)); - EXPECT_EQ(&C, CG.lookupSCC(CN)); - auto J = CG.postorder_ref_scc_begin(); - EXPECT_EQ(I, J); - EXPECT_EQ(&RC, &*J); - EXPECT_EQ(E, std::next(J)); + auto NewRCs = RC.removeInternalRefEdge(AN, CN); + EXPECT_THAT(NewRCs, ElementsAre()); + EXPECT_THAT(CG.lookupRefSCC(AN), Eq(&RC)); + EXPECT_THAT(CG.lookupRefSCC(BN), Eq(&RC)); + EXPECT_THAT(CG.lookupRefSCC(CN), Eq(&RC)); + EXPECT_THAT(CG.lookupSCC(AN), Eq(&C)); + EXPECT_THAT(CG.lookupSCC(BN), Eq(&C)); + EXPECT_THAT(CG.lookupSCC(CN), Eq(&C)); + EXPECT_THAT(CG.postorder_ref_sccs(), ElementsAre(Ref(RC))); // Remove the edge from b -> a and c -> b; again this doesn't change // anything. NewRCs = RC.removeInternalRefEdge(BN, AN); + EXPECT_THAT(NewRCs, ElementsAre()); NewRCs = RC.removeInternalRefEdge(CN, BN); - EXPECT_EQ(0u, NewRCs.size()); - EXPECT_EQ(&RC, CG.lookupRefSCC(AN)); - EXPECT_EQ(&RC, CG.lookupRefSCC(BN)); - EXPECT_EQ(&RC, CG.lookupRefSCC(CN)); - EXPECT_EQ(&C, CG.lookupSCC(AN)); - EXPECT_EQ(&C, CG.lookupSCC(BN)); - EXPECT_EQ(&C, CG.lookupSCC(CN)); - J = CG.postorder_ref_scc_begin(); - EXPECT_EQ(I, J); - EXPECT_EQ(&RC, &*J); - EXPECT_EQ(E, std::next(J)); + EXPECT_THAT(NewRCs, ElementsAre()); + EXPECT_THAT(CG.lookupRefSCC(AN), Eq(&RC)); + EXPECT_THAT(CG.lookupRefSCC(BN), Eq(&RC)); + EXPECT_THAT(CG.lookupRefSCC(CN), Eq(&RC)); + EXPECT_THAT(CG.lookupSCC(AN), Eq(&C)); + EXPECT_THAT(CG.lookupSCC(BN), Eq(&C)); + EXPECT_THAT(CG.lookupSCC(CN), Eq(&C)); + EXPECT_THAT(CG.postorder_ref_sccs(), ElementsAre(Ref(RC))); } TEST(LazyCallGraphTest, InternalCallEdgeToRef) { @@ -1709,64 +1655,47 @@ LazyCallGraph CG(*M); // Force the graph to be fully expanded. - auto I = CG.postorder_ref_scc_begin(); - LazyCallGraph::RefSCC &RC = *I++; - EXPECT_EQ(CG.postorder_ref_scc_end(), I); - - EXPECT_EQ(1, RC.size()); + EXPECT_THAT(CG.postorder_ref_sccs(), ElementsAre(_)); + LazyCallGraph::RefSCC &RC = *CG.postorder_ref_scc_begin(); + EXPECT_THAT(RC, ElementsAre(_)); LazyCallGraph::SCC &AC = *RC.begin(); LazyCallGraph::Node &AN = *CG.lookup(lookupFunction(*M, "a")); LazyCallGraph::Node &BN = *CG.lookup(lookupFunction(*M, "b")); LazyCallGraph::Node &CN = *CG.lookup(lookupFunction(*M, "c")); - EXPECT_EQ(&AC, CG.lookupSCC(AN)); - EXPECT_EQ(&AC, CG.lookupSCC(BN)); - EXPECT_EQ(&AC, CG.lookupSCC(CN)); + EXPECT_THAT(CG.lookupSCC(AN), Eq(&AC)); + EXPECT_THAT(CG.lookupSCC(BN), Eq(&AC)); + EXPECT_THAT(CG.lookupSCC(CN), Eq(&AC)); // Remove the call edge from b -> a to a ref edge, which should leave the // 3 functions still in a single connected component because of a -> b -> // c -> a. auto NewCs = RC.switchInternalEdgeToRef(BN, AN); - EXPECT_EQ(NewCs.begin(), NewCs.end()); - EXPECT_EQ(1, RC.size()); - EXPECT_EQ(&AC, CG.lookupSCC(AN)); - EXPECT_EQ(&AC, CG.lookupSCC(BN)); - EXPECT_EQ(&AC, CG.lookupSCC(CN)); + EXPECT_THAT(NewCs, ElementsAre()); + EXPECT_THAT(RC, ElementsAre(Ref(AC))); + EXPECT_THAT(CG.lookupSCC(AN), Eq(&AC)); + EXPECT_THAT(CG.lookupSCC(BN), Eq(&AC)); + EXPECT_THAT(CG.lookupSCC(CN), Eq(&AC)); // Remove the edge from c -> a, which should leave 'a' in the original SCC // and form a new SCC for 'b' and 'c'. NewCs = RC.switchInternalEdgeToRef(CN, AN); - EXPECT_EQ(1, std::distance(NewCs.begin(), NewCs.end())); - EXPECT_EQ(2, RC.size()); - EXPECT_EQ(&AC, CG.lookupSCC(AN)); - LazyCallGraph::SCC &BC = *CG.lookupSCC(BN); - EXPECT_NE(&BC, &AC); - EXPECT_EQ(&BC, CG.lookupSCC(CN)); - auto J = RC.find(AC); - EXPECT_EQ(&AC, &*J); - --J; - EXPECT_EQ(&BC, &*J); - EXPECT_EQ(RC.begin(), J); - EXPECT_EQ(J, NewCs.begin()); + EXPECT_THAT(CG.lookupSCC(AN), Eq(&AC)); + EXPECT_THAT(NewCs, ElementsAre(Not(Ref(AC)))); + LazyCallGraph::SCC &BC = *NewCs.begin(); + EXPECT_THAT(CG.lookupSCC(BN), Eq(&BC)); + EXPECT_THAT(CG.lookupSCC(CN), Eq(&BC)); + EXPECT_THAT(RC, ElementsAre(Ref(BC), Ref(AC))); // Remove the edge from c -> b, which should leave 'b' in the original SCC // and form a new SCC for 'c'. It shouldn't change 'a's SCC. NewCs = RC.switchInternalEdgeToRef(CN, BN); - EXPECT_EQ(1, std::distance(NewCs.begin(), NewCs.end())); - EXPECT_EQ(3, RC.size()); - EXPECT_EQ(&AC, CG.lookupSCC(AN)); - EXPECT_EQ(&BC, CG.lookupSCC(BN)); - LazyCallGraph::SCC &CC = *CG.lookupSCC(CN); - EXPECT_NE(&CC, &AC); - EXPECT_NE(&CC, &BC); - J = RC.find(AC); - EXPECT_EQ(&AC, &*J); - --J; - EXPECT_EQ(&BC, &*J); - --J; - EXPECT_EQ(&CC, &*J); - EXPECT_EQ(RC.begin(), J); - EXPECT_EQ(J, NewCs.begin()); + EXPECT_THAT(CG.lookupSCC(AN), Eq(&AC)); + EXPECT_THAT(CG.lookupSCC(BN), Eq(&BC)); + EXPECT_THAT(NewCs, ElementsAre(Not(AnyOf(Ref(AC), Ref(BC))))); + LazyCallGraph::SCC &CC = *NewCs.begin(); + EXPECT_THAT(CG.lookupSCC(CN), Eq(&CC)); + EXPECT_THAT(RC, ElementsAre(Ref(CC), Ref(BC), Ref(AC))); } TEST(LazyCallGraphTest, InternalRefEdgeToCall) { @@ -1801,9 +1730,8 @@ LazyCallGraph CG(*M); // Force the graph to be fully expanded. - auto I = CG.postorder_ref_scc_begin(); - LazyCallGraph::RefSCC &RC = *I++; - EXPECT_EQ(CG.postorder_ref_scc_end(), I); + EXPECT_THAT(CG.postorder_ref_sccs(), ElementsAre(_)); + LazyCallGraph::RefSCC &RC = *CG.postorder_ref_scc_begin(); LazyCallGraph::Node &A = *CG.lookup(lookupFunction(*M, "a")); LazyCallGraph::Node &B = *CG.lookup(lookupFunction(*M, "b")); @@ -1816,43 +1744,27 @@ // Check the initial post-order. Note that B and C could be flipped here (and // in our mutation) without changing the nature of this test. - ASSERT_EQ(4, RC.size()); - EXPECT_EQ(&DC, &RC[0]); - EXPECT_EQ(&BC, &RC[1]); - EXPECT_EQ(&CC, &RC[2]); - EXPECT_EQ(&AC, &RC[3]); + ASSERT_THAT(RC, ElementsAre(Ref(DC), Ref(BC), Ref(CC), Ref(AC))); // Switch the ref edge from A -> D to a call edge. This should have no // effect as it is already in postorder and no new cycles are formed. auto MergedCs = RC.switchInternalEdgeToCall(A, D); - EXPECT_EQ(0u, MergedCs.size()); - ASSERT_EQ(4, RC.size()); - EXPECT_EQ(&DC, &RC[0]); - EXPECT_EQ(&BC, &RC[1]); - EXPECT_EQ(&CC, &RC[2]); - EXPECT_EQ(&AC, &RC[3]); + EXPECT_THAT(MergedCs, ElementsAre()); + EXPECT_THAT(RC, ElementsAre(Ref(DC), Ref(BC), Ref(CC), Ref(AC))); // Switch B -> C to a call edge. This doesn't form any new cycles but does // require reordering the SCCs. MergedCs = RC.switchInternalEdgeToCall(B, C); - EXPECT_EQ(0u, MergedCs.size()); - ASSERT_EQ(4, RC.size()); - EXPECT_EQ(&DC, &RC[0]); - EXPECT_EQ(&CC, &RC[1]); - EXPECT_EQ(&BC, &RC[2]); - EXPECT_EQ(&AC, &RC[3]); + EXPECT_THAT(MergedCs, ElementsAre()); + EXPECT_THAT(RC, ElementsAre(Ref(DC), Ref(CC), Ref(BC), Ref(AC))); // Switch C -> B to a call edge. This forms a cycle and forces merging SCCs. MergedCs = RC.switchInternalEdgeToCall(C, B); - ASSERT_EQ(1u, MergedCs.size()); - EXPECT_EQ(&CC, MergedCs[0]); - ASSERT_EQ(3, RC.size()); - EXPECT_EQ(&DC, &RC[0]); - EXPECT_EQ(&BC, &RC[1]); - EXPECT_EQ(&AC, &RC[2]); - EXPECT_EQ(2, BC.size()); - EXPECT_EQ(&BC, CG.lookupSCC(B)); - EXPECT_EQ(&BC, CG.lookupSCC(C)); + EXPECT_THAT(MergedCs, ElementsAre(&CC)); + EXPECT_THAT(RC, ElementsAre(Ref(DC), Ref(BC), Ref(AC))); + EXPECT_THAT(BC, UnorderedElementsAre(Ref(B), Ref(C))); + EXPECT_THAT(CG.lookupSCC(B), Eq(&BC)); + EXPECT_THAT(CG.lookupSCC(C), Eq(&BC)); } TEST(LazyCallGraphTest, InternalRefEdgeToCallNoCycleInterleaved) { @@ -1913,9 +1825,8 @@ LazyCallGraph CG(*M); // Force the graph to be fully expanded. - auto I = CG.postorder_ref_scc_begin(); - LazyCallGraph::RefSCC &RC = *I++; - EXPECT_EQ(CG.postorder_ref_scc_end(), I); + EXPECT_THAT(CG.postorder_ref_sccs(), ElementsAre(_)); + LazyCallGraph::RefSCC &RC = *CG.postorder_ref_scc_begin(); LazyCallGraph::Node &A = *CG.lookup(lookupFunction(*M, "a")); LazyCallGraph::Node &B1 = *CG.lookup(lookupFunction(*M, "b1")); @@ -1944,30 +1855,16 @@ // Check the initial post-order. We ensure this order with the extra edges // that are nuked above. - ASSERT_EQ(8, RC.size()); - EXPECT_EQ(&DC, &RC[0]); - EXPECT_EQ(&C3C, &RC[1]); - EXPECT_EQ(&B3C, &RC[2]); - EXPECT_EQ(&C2C, &RC[3]); - EXPECT_EQ(&B2C, &RC[4]); - EXPECT_EQ(&C1C, &RC[5]); - EXPECT_EQ(&B1C, &RC[6]); - EXPECT_EQ(&AC, &RC[7]); + ASSERT_THAT(RC, ElementsAre(Ref(DC), Ref(C3C), Ref(B3C), Ref(C2C), Ref(B2C), + Ref(C1C), Ref(B1C), Ref(AC))); // Switch C3 -> B1 to a call edge. This doesn't form any new cycles but does // require reordering the SCCs in the face of tricky internal node // structures. auto MergedCs = RC.switchInternalEdgeToCall(C3, B1); - EXPECT_EQ(0u, MergedCs.size()); - ASSERT_EQ(8, RC.size()); - EXPECT_EQ(&DC, &RC[0]); - EXPECT_EQ(&B3C, &RC[1]); - EXPECT_EQ(&B2C, &RC[2]); - EXPECT_EQ(&B1C, &RC[3]); - EXPECT_EQ(&C3C, &RC[4]); - EXPECT_EQ(&C2C, &RC[5]); - EXPECT_EQ(&C1C, &RC[6]); - EXPECT_EQ(&AC, &RC[7]); + EXPECT_THAT(MergedCs, ElementsAre()); + EXPECT_THAT(RC, ElementsAre(Ref(DC), Ref(B3C), Ref(B2C), Ref(B1C), Ref(C3C), + Ref(C2C), Ref(C1C), Ref(AC))); } TEST(LazyCallGraphTest, InternalRefEdgeToCallBothPartitionAndMerge) { @@ -2043,9 +1940,8 @@ LazyCallGraph CG(*M); // Force the graph to be fully expanded. - auto I = CG.postorder_ref_scc_begin(); - LazyCallGraph::RefSCC &RC = *I++; - EXPECT_EQ(CG.postorder_ref_scc_end(), I); + EXPECT_THAT(CG.postorder_ref_sccs(), ElementsAre(_)); + LazyCallGraph::RefSCC &RC = *CG.postorder_ref_scc_begin(); LazyCallGraph::Node &A = *CG.lookup(lookupFunction(*M, "a")); LazyCallGraph::Node &B = *CG.lookup(lookupFunction(*M, "b")); @@ -2068,14 +1964,8 @@ // Check the initial post-order. We ensure this order with the extra edges // that are nuked above. - ASSERT_EQ(7, RC.size()); - EXPECT_EQ(&GC, &RC[0]); - EXPECT_EQ(&FC, &RC[1]); - EXPECT_EQ(&EC, &RC[2]); - EXPECT_EQ(&DC, &RC[3]); - EXPECT_EQ(&CC, &RC[4]); - EXPECT_EQ(&BC, &RC[5]); - EXPECT_EQ(&AC, &RC[6]); + ASSERT_THAT(RC, ElementsAre(Ref(GC), Ref(FC), Ref(EC), Ref(DC), Ref(CC), + Ref(BC), Ref(AC))); // Switch F -> B to a call edge. This merges B, D, and F into a single SCC, // and has to place the C and E SCCs on either side of it: @@ -2089,18 +1979,11 @@ // \ / \ / | // G G | auto MergedCs = RC.switchInternalEdgeToCall(F, B); - ASSERT_EQ(2u, MergedCs.size()); - EXPECT_EQ(&FC, MergedCs[0]); - EXPECT_EQ(&DC, MergedCs[1]); - EXPECT_EQ(3, BC.size()); + EXPECT_THAT(MergedCs, UnorderedElementsAre(&DC, &FC)); + EXPECT_THAT(BC, UnorderedElementsAre(Ref(B), Ref(D), Ref(F))); // And make sure the postorder was updated. - ASSERT_EQ(5, RC.size()); - EXPECT_EQ(&GC, &RC[0]); - EXPECT_EQ(&CC, &RC[1]); - EXPECT_EQ(&BC, &RC[2]); - EXPECT_EQ(&EC, &RC[3]); - EXPECT_EQ(&AC, &RC[4]); + EXPECT_THAT(RC, ElementsAre(Ref(GC), Ref(CC), Ref(BC), Ref(EC), Ref(AC))); } // Test for IR containing constants using blockaddress constant expressions. @@ -2122,15 +2005,14 @@ "}\n"); LazyCallGraph CG(*M); - auto I = CG.postorder_ref_scc_begin(); - LazyCallGraph::RefSCC &FRC = *I++; - LazyCallGraph::RefSCC &GRC = *I++; - EXPECT_EQ(CG.postorder_ref_scc_end(), I); + // Force the graph to be fully expanded. + EXPECT_THAT(CG.postorder_ref_sccs(), ElementsAre(_, _)); LazyCallGraph::Node &F = *CG.lookup(lookupFunction(*M, "f")); + LazyCallGraph::RefSCC &FRC = *CG.lookupRefSCC(F); LazyCallGraph::Node &G = *CG.lookup(lookupFunction(*M, "g")); - EXPECT_EQ(&FRC, CG.lookupRefSCC(F)); - EXPECT_EQ(&GRC, CG.lookupRefSCC(G)); + LazyCallGraph::RefSCC &GRC = *CG.lookupRefSCC(G); + EXPECT_THAT(CG.postorder_ref_sccs(), ElementsAre(Ref(FRC), Ref(GRC))); EXPECT_TRUE(GRC.isParentOf(FRC)); }