1 //===- unittests/Analysis/CFGTest.cpp - CFG 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 "clang/Analysis/CFG.h" 10 #include "CFGBuildResult.h" 11 #include "clang/AST/Decl.h" 12 #include "clang/ASTMatchers/ASTMatchFinder.h" 13 #include "clang/Analysis/Analyses/IntervalPartition.h" 14 #include "clang/Analysis/AnalysisDeclContext.h" 15 #include "clang/Analysis/FlowSensitive/DataflowWorklist.h" 16 #include "clang/Tooling/Tooling.h" 17 #include "gmock/gmock.h" 18 #include "gtest/gtest.h" 19 #include <algorithm> 20 #include <string> 21 #include <vector> 22 23 namespace clang { 24 namespace analysis { 25 namespace { 26 27 // Constructing a CFG for a range-based for over a dependent type fails (but 28 // should not crash). 29 TEST(CFG, RangeBasedForOverDependentType) { 30 const char *Code = "class Foo;\n" 31 "template <typename T>\n" 32 "void f(const T &Range) {\n" 33 " for (const Foo *TheFoo : Range) {\n" 34 " }\n" 35 "}\n"; 36 EXPECT_EQ(BuildResult::SawFunctionBody, BuildCFG(Code).getStatus()); 37 } 38 39 TEST(CFG, StaticInitializerLastCondition) { 40 const char *Code = "void f() {\n" 41 " int i = 5 ;\n" 42 " static int j = 3 ;\n" 43 "}\n"; 44 CFG::BuildOptions Options; 45 Options.AddStaticInitBranches = true; 46 Options.setAllAlwaysAdd(); 47 BuildResult B = BuildCFG(Code, Options); 48 EXPECT_EQ(BuildResult::BuiltCFG, B.getStatus()); 49 EXPECT_EQ(1u, B.getCFG()->getEntry().succ_size()); 50 CFGBlock *Block = *B.getCFG()->getEntry().succ_begin(); 51 EXPECT_TRUE(isa<DeclStmt>(Block->getTerminatorStmt())); 52 EXPECT_EQ(nullptr, Block->getLastCondition()); 53 } 54 55 // Constructing a CFG containing a delete expression on a dependent type should 56 // not crash. 57 TEST(CFG, DeleteExpressionOnDependentType) { 58 const char *Code = "template<class T>\n" 59 "void f(T t) {\n" 60 " delete t;\n" 61 "}\n"; 62 EXPECT_EQ(BuildResult::BuiltCFG, BuildCFG(Code).getStatus()); 63 } 64 65 // Constructing a CFG on a function template with a variable of incomplete type 66 // should not crash. 67 TEST(CFG, VariableOfIncompleteType) { 68 const char *Code = "template<class T> void f() {\n" 69 " class Undefined;\n" 70 " Undefined u;\n" 71 "}\n"; 72 EXPECT_EQ(BuildResult::BuiltCFG, BuildCFG(Code).getStatus()); 73 } 74 75 // Constructing a CFG with a dependent base should not crash. 76 TEST(CFG, DependantBaseAddImplicitDtors) { 77 const char *Code = R"( 78 template <class T> 79 struct Base { 80 virtual ~Base() {} 81 }; 82 83 template <typename T> 84 struct Derived : public Base<T> { 85 virtual ~Derived() {} 86 }; 87 )"; 88 CFG::BuildOptions Options; 89 Options.AddImplicitDtors = true; 90 Options.setAllAlwaysAdd(); 91 EXPECT_EQ(BuildResult::BuiltCFG, 92 BuildCFG(Code, Options, ast_matchers::hasName("~Derived<T>")) 93 .getStatus()); 94 } 95 96 TEST(CFG, IsLinear) { 97 auto expectLinear = [](bool IsLinear, const char *Code) { 98 BuildResult B = BuildCFG(Code); 99 EXPECT_EQ(BuildResult::BuiltCFG, B.getStatus()); 100 EXPECT_EQ(IsLinear, B.getCFG()->isLinear()); 101 }; 102 103 expectLinear(true, "void foo() {}"); 104 expectLinear(true, "void foo() { if (true) return; }"); 105 expectLinear(true, "void foo() { if constexpr (false); }"); 106 expectLinear(false, "void foo(bool coin) { if (coin) return; }"); 107 expectLinear(false, "void foo() { for(;;); }"); 108 expectLinear(false, "void foo() { do {} while (true); }"); 109 expectLinear(true, "void foo() { do {} while (false); }"); 110 expectLinear(true, "void foo() { foo(); }"); // Recursion is not our problem. 111 } 112 113 TEST(CFG, ElementRefIterator) { 114 const char *Code = R"(void f() { 115 int i; 116 int j; 117 i = 5; 118 i = 6; 119 j = 7; 120 })"; 121 122 BuildResult B = BuildCFG(Code); 123 EXPECT_EQ(BuildResult::BuiltCFG, B.getStatus()); 124 CFG *Cfg = B.getCFG(); 125 126 // [B2 (ENTRY)] 127 // Succs (1): B1 128 129 // [B1] 130 // 1: int i; 131 // 2: int j; 132 // 3: i = 5 133 // 4: i = 6 134 // 5: j = 7 135 // Preds (1): B2 136 // Succs (1): B0 137 138 // [B0 (EXIT)] 139 // Preds (1): B1 140 CFGBlock *MainBlock = *(Cfg->begin() + 1); 141 142 constexpr CFGBlock::ref_iterator::difference_type MainBlockSize = 4; 143 144 // The rest of this test looks totally insane, but there iterators are 145 // templates under the hood, to it's important to instantiate everything for 146 // proper converage. 147 148 // Non-reverse, non-const version 149 size_t Index = 0; 150 for (CFGBlock::CFGElementRef ElementRef : MainBlock->refs()) { 151 EXPECT_EQ(ElementRef.getParent(), MainBlock); 152 EXPECT_EQ(ElementRef.getIndexInBlock(), Index); 153 EXPECT_TRUE(ElementRef->getAs<CFGStmt>()); 154 EXPECT_TRUE((*ElementRef).getAs<CFGStmt>()); 155 EXPECT_EQ(ElementRef.getParent(), MainBlock); 156 ++Index; 157 } 158 EXPECT_TRUE(*MainBlock->ref_begin() < *(MainBlock->ref_begin() + 1)); 159 EXPECT_TRUE(*MainBlock->ref_begin() == *MainBlock->ref_begin()); 160 EXPECT_FALSE(*MainBlock->ref_begin() != *MainBlock->ref_begin()); 161 162 EXPECT_TRUE(MainBlock->ref_begin() < MainBlock->ref_begin() + 1); 163 EXPECT_TRUE(MainBlock->ref_begin() == MainBlock->ref_begin()); 164 EXPECT_FALSE(MainBlock->ref_begin() != MainBlock->ref_begin()); 165 EXPECT_EQ(MainBlock->ref_end() - MainBlock->ref_begin(), MainBlockSize + 1); 166 EXPECT_EQ(MainBlock->ref_end() - MainBlockSize - 1, MainBlock->ref_begin()); 167 EXPECT_EQ(MainBlock->ref_begin() + MainBlockSize + 1, MainBlock->ref_end()); 168 EXPECT_EQ(MainBlock->ref_begin()++, MainBlock->ref_begin()); 169 EXPECT_EQ(++(MainBlock->ref_begin()), MainBlock->ref_begin() + 1); 170 171 // Non-reverse, non-const version 172 const CFGBlock *CMainBlock = MainBlock; 173 Index = 0; 174 for (CFGBlock::ConstCFGElementRef ElementRef : CMainBlock->refs()) { 175 EXPECT_EQ(ElementRef.getParent(), CMainBlock); 176 EXPECT_EQ(ElementRef.getIndexInBlock(), Index); 177 EXPECT_TRUE(ElementRef->getAs<CFGStmt>()); 178 EXPECT_TRUE((*ElementRef).getAs<CFGStmt>()); 179 EXPECT_EQ(ElementRef.getParent(), MainBlock); 180 ++Index; 181 } 182 EXPECT_TRUE(*CMainBlock->ref_begin() < *(CMainBlock->ref_begin() + 1)); 183 EXPECT_TRUE(*CMainBlock->ref_begin() == *CMainBlock->ref_begin()); 184 EXPECT_FALSE(*CMainBlock->ref_begin() != *CMainBlock->ref_begin()); 185 186 EXPECT_TRUE(CMainBlock->ref_begin() < CMainBlock->ref_begin() + 1); 187 EXPECT_TRUE(CMainBlock->ref_begin() == CMainBlock->ref_begin()); 188 EXPECT_FALSE(CMainBlock->ref_begin() != CMainBlock->ref_begin()); 189 EXPECT_EQ(CMainBlock->ref_end() - CMainBlock->ref_begin(), MainBlockSize + 1); 190 EXPECT_EQ(CMainBlock->ref_end() - MainBlockSize - 1, CMainBlock->ref_begin()); 191 EXPECT_EQ(CMainBlock->ref_begin() + MainBlockSize + 1, CMainBlock->ref_end()); 192 EXPECT_EQ(CMainBlock->ref_begin()++, CMainBlock->ref_begin()); 193 EXPECT_EQ(++(CMainBlock->ref_begin()), CMainBlock->ref_begin() + 1); 194 195 // Reverse, non-const version 196 Index = MainBlockSize; 197 for (CFGBlock::CFGElementRef ElementRef : MainBlock->rrefs()) { 198 EXPECT_EQ(ElementRef.getParent(), MainBlock); 199 EXPECT_EQ(ElementRef.getIndexInBlock(), Index); 200 EXPECT_TRUE(ElementRef->getAs<CFGStmt>()); 201 EXPECT_TRUE((*ElementRef).getAs<CFGStmt>()); 202 EXPECT_EQ(ElementRef.getParent(), MainBlock); 203 --Index; 204 } 205 EXPECT_FALSE(*MainBlock->rref_begin() < *(MainBlock->rref_begin() + 1)); 206 EXPECT_TRUE(*MainBlock->rref_begin() == *MainBlock->rref_begin()); 207 EXPECT_FALSE(*MainBlock->rref_begin() != *MainBlock->rref_begin()); 208 209 EXPECT_TRUE(MainBlock->rref_begin() < MainBlock->rref_begin() + 1); 210 EXPECT_TRUE(MainBlock->rref_begin() == MainBlock->rref_begin()); 211 EXPECT_FALSE(MainBlock->rref_begin() != MainBlock->rref_begin()); 212 EXPECT_EQ(MainBlock->rref_end() - MainBlock->rref_begin(), MainBlockSize + 1); 213 EXPECT_EQ(MainBlock->rref_end() - MainBlockSize - 1, MainBlock->rref_begin()); 214 EXPECT_EQ(MainBlock->rref_begin() + MainBlockSize + 1, MainBlock->rref_end()); 215 EXPECT_EQ(MainBlock->rref_begin()++, MainBlock->rref_begin()); 216 EXPECT_EQ(++(MainBlock->rref_begin()), MainBlock->rref_begin() + 1); 217 218 // Reverse, const version 219 Index = MainBlockSize; 220 for (CFGBlock::ConstCFGElementRef ElementRef : CMainBlock->rrefs()) { 221 EXPECT_EQ(ElementRef.getParent(), CMainBlock); 222 EXPECT_EQ(ElementRef.getIndexInBlock(), Index); 223 EXPECT_TRUE(ElementRef->getAs<CFGStmt>()); 224 EXPECT_TRUE((*ElementRef).getAs<CFGStmt>()); 225 EXPECT_EQ(ElementRef.getParent(), MainBlock); 226 --Index; 227 } 228 EXPECT_FALSE(*CMainBlock->rref_begin() < *(CMainBlock->rref_begin() + 1)); 229 EXPECT_TRUE(*CMainBlock->rref_begin() == *CMainBlock->rref_begin()); 230 EXPECT_FALSE(*CMainBlock->rref_begin() != *CMainBlock->rref_begin()); 231 232 EXPECT_TRUE(CMainBlock->rref_begin() < CMainBlock->rref_begin() + 1); 233 EXPECT_TRUE(CMainBlock->rref_begin() == CMainBlock->rref_begin()); 234 EXPECT_FALSE(CMainBlock->rref_begin() != CMainBlock->rref_begin()); 235 EXPECT_EQ(CMainBlock->rref_end() - CMainBlock->rref_begin(), 236 MainBlockSize + 1); 237 EXPECT_EQ(CMainBlock->rref_end() - MainBlockSize - 1, 238 CMainBlock->rref_begin()); 239 EXPECT_EQ(CMainBlock->rref_begin() + MainBlockSize + 1, 240 CMainBlock->rref_end()); 241 EXPECT_EQ(CMainBlock->rref_begin()++, CMainBlock->rref_begin()); 242 EXPECT_EQ(++(CMainBlock->rref_begin()), CMainBlock->rref_begin() + 1); 243 } 244 245 TEST(CFG, Worklists) { 246 const char *Code = "int f(bool cond) {\n" 247 " int a = 5;\n" 248 " while (a < 6)\n" 249 " ++a;\n" 250 " if (cond)\n" 251 " a += 1;\n" 252 " return a;\n" 253 "}\n"; 254 BuildResult B = BuildCFG(Code); 255 EXPECT_EQ(BuildResult::BuiltCFG, B.getStatus()); 256 const FunctionDecl *Func = B.getFunc(); 257 AnalysisDeclContext AC(nullptr, Func); 258 auto *CFG = AC.getCFG(); 259 260 std::vector<const CFGBlock *> ReferenceOrder; 261 for (const auto *B : *AC.getAnalysis<PostOrderCFGView>()) 262 ReferenceOrder.push_back(B); 263 264 { 265 ForwardDataflowWorklist ForwardWorklist(*CFG, AC); 266 for (const auto *B : *CFG) 267 ForwardWorklist.enqueueBlock(B); 268 269 std::vector<const CFGBlock *> ForwardNodes; 270 while (const CFGBlock *B = ForwardWorklist.dequeue()) 271 ForwardNodes.push_back(B); 272 273 EXPECT_EQ(ForwardNodes.size(), ReferenceOrder.size()); 274 EXPECT_TRUE(std::equal(ReferenceOrder.begin(), ReferenceOrder.end(), 275 ForwardNodes.begin())); 276 } 277 278 { 279 using ::testing::ElementsAreArray; 280 std::optional<WeakTopologicalOrdering> WTO = getIntervalWTO(*CFG); 281 ASSERT_TRUE(WTO); 282 WTOCompare WCmp(*WTO); 283 WTODataflowWorklist WTOWorklist(*CFG, WCmp); 284 for (const auto *B : *CFG) 285 WTOWorklist.enqueueBlock(B); 286 287 std::vector<const CFGBlock *> WTONodes; 288 while (const CFGBlock *B = WTOWorklist.dequeue()) 289 WTONodes.push_back(B); 290 291 EXPECT_THAT(WTONodes, ElementsAreArray(*WTO)); 292 } 293 294 std::reverse(ReferenceOrder.begin(), ReferenceOrder.end()); 295 296 { 297 BackwardDataflowWorklist BackwardWorklist(*CFG, AC); 298 for (const auto *B : *CFG) 299 BackwardWorklist.enqueueBlock(B); 300 301 std::vector<const CFGBlock *> BackwardNodes; 302 while (const CFGBlock *B = BackwardWorklist.dequeue()) 303 BackwardNodes.push_back(B); 304 305 EXPECT_EQ(BackwardNodes.size(), ReferenceOrder.size()); 306 EXPECT_TRUE(std::equal(ReferenceOrder.begin(), ReferenceOrder.end(), 307 BackwardNodes.begin())); 308 } 309 } 310 311 } // namespace 312 } // namespace analysis 313 } // namespace clang 314