467 lines · cpp
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-exception6//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 23namespace clang {24namespace analysis {25namespace {26 27// Constructing a CFG for a range-based for over a dependent type fails (but28// should not crash).29TEST(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 39TEST(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 should56// not crash.57TEST(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 type66// should not crash.67TEST(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.76TEST(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 96TEST(CFG, SwitchCoveredEnumNoDefault) {97 const char *Code = R"(98 enum class E {E1, E2};99 int f(E e) {100 switch(e) {101 case E::E1:102 return 1;103 case E::E2:104 return 2;105 }106 return 0;107 }108 )";109 CFG::BuildOptions Options;110 Options.AssumeReachableDefaultInSwitchStatements = true;111 BuildResult B = BuildCFG(Code, Options);112 ASSERT_EQ(BuildResult::BuiltCFG, B.getStatus());113 114 // [B5 (ENTRY)]115 // Succs (1): B2116 //117 // [B1]118 // 1: 0119 // 2: return [B1.1];120 // Preds (1): B2121 // Succs (1): B0122 //123 // [B2]124 // 1: e (ImplicitCastExpr, LValueToRValue, E)125 // T: switch [B2.1]126 // Preds (1): B5127 // Succs (3): B3 B4 B1128 //129 // [B3]130 // case E::E2:131 // 1: 2132 // 2: return [B3.1];133 // Preds (1): B2134 // Succs (1): B0135 //136 // [B4]137 // case E::E1:138 // 1: 1139 // 2: return [B4.1];140 // Preds (1): B2141 // Succs (1): B0142 //143 // [B0 (EXIT)]144 // Preds (3): B1 B3 B4145 146 auto *CFG = B.getCFG();147 const auto &Entry = CFG->getEntry();148 ASSERT_EQ(1u, Entry.succ_size());149 // First successor of Entry is the switch150 CFGBlock *SwitchBlock = *Entry.succ_begin();151 ASSERT_EQ(3u, SwitchBlock->succ_size());152 // Last successor of the switch is after the switch153 auto NoCaseSucc = SwitchBlock->succ_rbegin();154 EXPECT_TRUE(NoCaseSucc->isReachable());155 156 // Checking that the same node is Unreachable without this setting157 Options.AssumeReachableDefaultInSwitchStatements = false;158 B = BuildCFG(Code, Options);159 ASSERT_EQ(BuildResult::BuiltCFG, B.getStatus());160 161 const auto &Entry2 = B.getCFG()->getEntry();162 ASSERT_EQ(1u, Entry2.succ_size());163 CFGBlock *SwitchBlock2 = *Entry2.succ_begin();164 ASSERT_EQ(3u, SwitchBlock2->succ_size());165 auto NoCaseSucc2 = SwitchBlock2->succ_rbegin();166 EXPECT_FALSE(NoCaseSucc2->isReachable());167}168 169TEST(CFG, SwitchCoveredEnumWithDefault) {170 const char *Code = R"(171 enum class E {E1, E2};172 int f(E e) {173 switch(e) {174 case E::E1:175 return 1;176 case E::E2:177 return 2;178 default:179 return 0;180 }181 return -1;182 }183 )";184 CFG::BuildOptions Options;185 Options.AssumeReachableDefaultInSwitchStatements = true;186 BuildResult B = BuildCFG(Code, Options);187 ASSERT_EQ(BuildResult::BuiltCFG, B.getStatus());188 189 // [B6 (ENTRY)]190 // Succs (1): B2191 //192 // [B1]193 // 1: -1194 // 2: return [B1.1];195 // Succs (1): B0196 //197 // [B2]198 // 1: e (ImplicitCastExpr, LValueToRValue, E)199 // T: switch [B2.1]200 // Preds (1): B6201 // Succs (3): B4 B5 B3202 //203 // [B3]204 // default:205 // 1: 0206 // 2: return [B3.1];207 // Preds (1): B2208 // Succs (1): B0209 //210 // [B4]211 // case E::E2:212 // 1: 2213 // 2: return [B4.1];214 // Preds (1): B2215 // Succs (1): B0216 //217 // [B5]218 // case E::E1:219 // 1: 1220 // 2: return [B5.1];221 // Preds (1): B2222 // Succs (1): B0223 //224 // [B0 (EXIT)]225 // Preds (4): B1 B3 B4 B5226 227 const auto &Entry = B.getCFG()->getEntry();228 ASSERT_EQ(1u, Entry.succ_size());229 // First successor of Entry is the switch230 CFGBlock *SwitchBlock = *Entry.succ_begin();231 ASSERT_EQ(3u, SwitchBlock->succ_size());232 // Last successor of the switch is the default branch233 auto defaultBlock = SwitchBlock->succ_rbegin();234 EXPECT_TRUE(defaultBlock->isReachable());235 236 // Checking that the same node is Unreachable without this setting237 Options.AssumeReachableDefaultInSwitchStatements = false;238 B = BuildCFG(Code, Options);239 ASSERT_EQ(BuildResult::BuiltCFG, B.getStatus());240 241 const auto &Entry2 = B.getCFG()->getEntry();242 ASSERT_EQ(1u, Entry2.succ_size());243 CFGBlock *SwitchBlock2 = *Entry2.succ_begin();244 ASSERT_EQ(3u, SwitchBlock2->succ_size());245 auto defaultBlock2 = SwitchBlock2->succ_rbegin();246 EXPECT_FALSE(defaultBlock2->isReachable());247}248 249TEST(CFG, IsLinear) {250 auto expectLinear = [](bool IsLinear, const char *Code) {251 BuildResult B = BuildCFG(Code);252 EXPECT_EQ(BuildResult::BuiltCFG, B.getStatus());253 EXPECT_EQ(IsLinear, B.getCFG()->isLinear());254 };255 256 expectLinear(true, "void foo() {}");257 expectLinear(true, "void foo() { if (true) return; }");258 expectLinear(true, "void foo() { if constexpr (false); }");259 expectLinear(false, "void foo(bool coin) { if (coin) return; }");260 expectLinear(false, "void foo() { for(;;); }");261 expectLinear(false, "void foo() { do {} while (true); }");262 expectLinear(true, "void foo() { do {} while (false); }");263 expectLinear(true, "void foo() { foo(); }"); // Recursion is not our problem.264}265 266TEST(CFG, ElementRefIterator) {267 const char *Code = R"(void f() {268 int i;269 int j;270 i = 5;271 i = 6;272 j = 7;273 })";274 275 BuildResult B = BuildCFG(Code);276 EXPECT_EQ(BuildResult::BuiltCFG, B.getStatus());277 CFG *Cfg = B.getCFG();278 279 // [B2 (ENTRY)]280 // Succs (1): B1281 282 // [B1]283 // 1: int i;284 // 2: int j;285 // 3: i = 5286 // 4: i = 6287 // 5: j = 7288 // Preds (1): B2289 // Succs (1): B0290 291 // [B0 (EXIT)]292 // Preds (1): B1293 CFGBlock *MainBlock = *(Cfg->begin() + 1);294 295 constexpr CFGBlock::ref_iterator::difference_type MainBlockSize = 4;296 297 // The rest of this test looks totally insane, but there iterators are298 // templates under the hood, to it's important to instantiate everything for299 // proper converage.300 301 // Non-reverse, non-const version302 size_t Index = 0;303 for (CFGBlock::CFGElementRef ElementRef : MainBlock->refs()) {304 EXPECT_EQ(ElementRef.getParent(), MainBlock);305 EXPECT_EQ(ElementRef.getIndexInBlock(), Index);306 EXPECT_TRUE(ElementRef->getAs<CFGStmt>());307 EXPECT_TRUE((*ElementRef).getAs<CFGStmt>());308 EXPECT_EQ(ElementRef.getParent(), MainBlock);309 ++Index;310 }311 EXPECT_TRUE(*MainBlock->ref_begin() < *(MainBlock->ref_begin() + 1));312 EXPECT_TRUE(*MainBlock->ref_begin() == *MainBlock->ref_begin());313 EXPECT_FALSE(*MainBlock->ref_begin() != *MainBlock->ref_begin());314 315 EXPECT_TRUE(MainBlock->ref_begin() < MainBlock->ref_begin() + 1);316 EXPECT_TRUE(MainBlock->ref_begin() == MainBlock->ref_begin());317 EXPECT_FALSE(MainBlock->ref_begin() != MainBlock->ref_begin());318 EXPECT_EQ(MainBlock->ref_end() - MainBlock->ref_begin(), MainBlockSize + 1);319 EXPECT_EQ(MainBlock->ref_end() - MainBlockSize - 1, MainBlock->ref_begin());320 EXPECT_EQ(MainBlock->ref_begin() + MainBlockSize + 1, MainBlock->ref_end());321 EXPECT_EQ(MainBlock->ref_begin()++, MainBlock->ref_begin());322 EXPECT_EQ(++(MainBlock->ref_begin()), MainBlock->ref_begin() + 1);323 324 // Non-reverse, non-const version325 const CFGBlock *CMainBlock = MainBlock;326 Index = 0;327 for (CFGBlock::ConstCFGElementRef ElementRef : CMainBlock->refs()) {328 EXPECT_EQ(ElementRef.getParent(), CMainBlock);329 EXPECT_EQ(ElementRef.getIndexInBlock(), Index);330 EXPECT_TRUE(ElementRef->getAs<CFGStmt>());331 EXPECT_TRUE((*ElementRef).getAs<CFGStmt>());332 EXPECT_EQ(ElementRef.getParent(), MainBlock);333 ++Index;334 }335 EXPECT_TRUE(*CMainBlock->ref_begin() < *(CMainBlock->ref_begin() + 1));336 EXPECT_TRUE(*CMainBlock->ref_begin() == *CMainBlock->ref_begin());337 EXPECT_FALSE(*CMainBlock->ref_begin() != *CMainBlock->ref_begin());338 339 EXPECT_TRUE(CMainBlock->ref_begin() < CMainBlock->ref_begin() + 1);340 EXPECT_TRUE(CMainBlock->ref_begin() == CMainBlock->ref_begin());341 EXPECT_FALSE(CMainBlock->ref_begin() != CMainBlock->ref_begin());342 EXPECT_EQ(CMainBlock->ref_end() - CMainBlock->ref_begin(), MainBlockSize + 1);343 EXPECT_EQ(CMainBlock->ref_end() - MainBlockSize - 1, CMainBlock->ref_begin());344 EXPECT_EQ(CMainBlock->ref_begin() + MainBlockSize + 1, CMainBlock->ref_end());345 EXPECT_EQ(CMainBlock->ref_begin()++, CMainBlock->ref_begin());346 EXPECT_EQ(++(CMainBlock->ref_begin()), CMainBlock->ref_begin() + 1);347 348 // Reverse, non-const version349 Index = MainBlockSize;350 for (CFGBlock::CFGElementRef ElementRef : MainBlock->rrefs()) {351 EXPECT_EQ(ElementRef.getParent(), MainBlock);352 EXPECT_EQ(ElementRef.getIndexInBlock(), Index);353 EXPECT_TRUE(ElementRef->getAs<CFGStmt>());354 EXPECT_TRUE((*ElementRef).getAs<CFGStmt>());355 EXPECT_EQ(ElementRef.getParent(), MainBlock);356 --Index;357 }358 EXPECT_FALSE(*MainBlock->rref_begin() < *(MainBlock->rref_begin() + 1));359 EXPECT_TRUE(*MainBlock->rref_begin() == *MainBlock->rref_begin());360 EXPECT_FALSE(*MainBlock->rref_begin() != *MainBlock->rref_begin());361 362 EXPECT_TRUE(MainBlock->rref_begin() < MainBlock->rref_begin() + 1);363 EXPECT_TRUE(MainBlock->rref_begin() == MainBlock->rref_begin());364 EXPECT_FALSE(MainBlock->rref_begin() != MainBlock->rref_begin());365 EXPECT_EQ(MainBlock->rref_end() - MainBlock->rref_begin(), MainBlockSize + 1);366 EXPECT_EQ(MainBlock->rref_end() - MainBlockSize - 1, MainBlock->rref_begin());367 EXPECT_EQ(MainBlock->rref_begin() + MainBlockSize + 1, MainBlock->rref_end());368 EXPECT_EQ(MainBlock->rref_begin()++, MainBlock->rref_begin());369 EXPECT_EQ(++(MainBlock->rref_begin()), MainBlock->rref_begin() + 1);370 371 // Reverse, const version372 Index = MainBlockSize;373 for (CFGBlock::ConstCFGElementRef ElementRef : CMainBlock->rrefs()) {374 EXPECT_EQ(ElementRef.getParent(), CMainBlock);375 EXPECT_EQ(ElementRef.getIndexInBlock(), Index);376 EXPECT_TRUE(ElementRef->getAs<CFGStmt>());377 EXPECT_TRUE((*ElementRef).getAs<CFGStmt>());378 EXPECT_EQ(ElementRef.getParent(), MainBlock);379 --Index;380 }381 EXPECT_FALSE(*CMainBlock->rref_begin() < *(CMainBlock->rref_begin() + 1));382 EXPECT_TRUE(*CMainBlock->rref_begin() == *CMainBlock->rref_begin());383 EXPECT_FALSE(*CMainBlock->rref_begin() != *CMainBlock->rref_begin());384 385 EXPECT_TRUE(CMainBlock->rref_begin() < CMainBlock->rref_begin() + 1);386 EXPECT_TRUE(CMainBlock->rref_begin() == CMainBlock->rref_begin());387 EXPECT_FALSE(CMainBlock->rref_begin() != CMainBlock->rref_begin());388 EXPECT_EQ(CMainBlock->rref_end() - CMainBlock->rref_begin(),389 MainBlockSize + 1);390 EXPECT_EQ(CMainBlock->rref_end() - MainBlockSize - 1,391 CMainBlock->rref_begin());392 EXPECT_EQ(CMainBlock->rref_begin() + MainBlockSize + 1,393 CMainBlock->rref_end());394 EXPECT_EQ(CMainBlock->rref_begin()++, CMainBlock->rref_begin());395 EXPECT_EQ(++(CMainBlock->rref_begin()), CMainBlock->rref_begin() + 1);396}397 398TEST(CFG, Worklists) {399 const char *Code = "int f(bool cond) {\n"400 " int a = 5;\n"401 " while (a < 6)\n"402 " ++a;\n"403 " if (cond)\n"404 " a += 1;\n"405 " return a;\n"406 "}\n";407 BuildResult B = BuildCFG(Code);408 EXPECT_EQ(BuildResult::BuiltCFG, B.getStatus());409 const FunctionDecl *Func = B.getFunc();410 AnalysisDeclContext AC(nullptr, Func);411 auto *CFG = AC.getCFG();412 413 std::vector<const CFGBlock *> ReferenceOrder;414 for (const auto *B : *AC.getAnalysis<PostOrderCFGView>())415 ReferenceOrder.push_back(B);416 417 {418 ForwardDataflowWorklist ForwardWorklist(*CFG, AC);419 for (const auto *B : *CFG)420 ForwardWorklist.enqueueBlock(B);421 422 std::vector<const CFGBlock *> ForwardNodes;423 while (const CFGBlock *B = ForwardWorklist.dequeue())424 ForwardNodes.push_back(B);425 426 EXPECT_EQ(ForwardNodes.size(), ReferenceOrder.size());427 EXPECT_TRUE(std::equal(ReferenceOrder.begin(), ReferenceOrder.end(),428 ForwardNodes.begin()));429 }430 431 {432 using ::testing::ElementsAreArray;433 std::optional<WeakTopologicalOrdering> WTO = getIntervalWTO(*CFG);434 ASSERT_TRUE(WTO);435 WTOCompare WCmp(*WTO);436 WTODataflowWorklist WTOWorklist(*CFG, WCmp);437 for (const auto *B : *CFG)438 WTOWorklist.enqueueBlock(B);439 440 std::vector<const CFGBlock *> WTONodes;441 while (const CFGBlock *B = WTOWorklist.dequeue())442 WTONodes.push_back(B);443 444 EXPECT_THAT(WTONodes, ElementsAreArray(*WTO));445 }446 447 std::reverse(ReferenceOrder.begin(), ReferenceOrder.end());448 449 {450 BackwardDataflowWorklist BackwardWorklist(*CFG, AC);451 for (const auto *B : *CFG)452 BackwardWorklist.enqueueBlock(B);453 454 std::vector<const CFGBlock *> BackwardNodes;455 while (const CFGBlock *B = BackwardWorklist.dequeue())456 BackwardNodes.push_back(B);457 458 EXPECT_EQ(BackwardNodes.size(), ReferenceOrder.size());459 EXPECT_TRUE(std::equal(ReferenceOrder.begin(), ReferenceOrder.end(),460 BackwardNodes.begin()));461 }462}463 464} // namespace465} // namespace analysis466} // namespace clang467