clang/unittests/Analysis/CFGTest.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-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     llvm::errs() << Index << '\n';
 199     EXPECT_EQ(ElementRef.getParent(), MainBlock);
 200     EXPECT_EQ(ElementRef.getIndexInBlock(), Index);
 201     EXPECT_TRUE(ElementRef->getAs<CFGStmt>());
 202     EXPECT_TRUE((*ElementRef).getAs<CFGStmt>());
 203     EXPECT_EQ(ElementRef.getParent(), MainBlock);
 204     --Index;
 205   }
 206   EXPECT_FALSE(*MainBlock->rref_begin() < *(MainBlock->rref_begin() + 1));
 207   EXPECT_TRUE(*MainBlock->rref_begin() == *MainBlock->rref_begin());
 208   EXPECT_FALSE(*MainBlock->rref_begin() != *MainBlock->rref_begin());
 209
 210   EXPECT_TRUE(MainBlock->rref_begin() < MainBlock->rref_begin() + 1);
 211   EXPECT_TRUE(MainBlock->rref_begin() == MainBlock->rref_begin());
 212   EXPECT_FALSE(MainBlock->rref_begin() != MainBlock->rref_begin());
 213   EXPECT_EQ(MainBlock->rref_end() - MainBlock->rref_begin(), MainBlockSize + 1);
 214   EXPECT_EQ(MainBlock->rref_end() - MainBlockSize - 1, MainBlock->rref_begin());
 215   EXPECT_EQ(MainBlock->rref_begin() + MainBlockSize + 1, MainBlock->rref_end());
 216   EXPECT_EQ(MainBlock->rref_begin()++, MainBlock->rref_begin());
 217   EXPECT_EQ(++(MainBlock->rref_begin()), MainBlock->rref_begin() + 1);
 218
 219   // Reverse, const version
 220   Index = MainBlockSize;
 221   for (CFGBlock::ConstCFGElementRef ElementRef : CMainBlock->rrefs()) {
 222     EXPECT_EQ(ElementRef.getParent(), CMainBlock);
 223     EXPECT_EQ(ElementRef.getIndexInBlock(), Index);
 224     EXPECT_TRUE(ElementRef->getAs<CFGStmt>());
 225     EXPECT_TRUE((*ElementRef).getAs<CFGStmt>());
 226     EXPECT_EQ(ElementRef.getParent(), MainBlock);
 227     --Index;
 228   }
 229   EXPECT_FALSE(*CMainBlock->rref_begin() < *(CMainBlock->rref_begin() + 1));
 230   EXPECT_TRUE(*CMainBlock->rref_begin() == *CMainBlock->rref_begin());
 231   EXPECT_FALSE(*CMainBlock->rref_begin() != *CMainBlock->rref_begin());
 232
 233   EXPECT_TRUE(CMainBlock->rref_begin() < CMainBlock->rref_begin() + 1);
 234   EXPECT_TRUE(CMainBlock->rref_begin() == CMainBlock->rref_begin());
 235   EXPECT_FALSE(CMainBlock->rref_begin() != CMainBlock->rref_begin());
 236   EXPECT_EQ(CMainBlock->rref_end() - CMainBlock->rref_begin(),
 237             MainBlockSize + 1);
 238   EXPECT_EQ(CMainBlock->rref_end() - MainBlockSize - 1,
 239             CMainBlock->rref_begin());
 240   EXPECT_EQ(CMainBlock->rref_begin() + MainBlockSize + 1,
 241             CMainBlock->rref_end());
 242   EXPECT_EQ(CMainBlock->rref_begin()++, CMainBlock->rref_begin());
 243   EXPECT_EQ(++(CMainBlock->rref_begin()), CMainBlock->rref_begin() + 1);
 244 }
 245
 246 TEST(CFG, Worklists) {
 247   const char *Code = "int f(bool cond) {\n"
 248                      "  int a = 5;\n"
 249                      "  while (a < 6)\n"
 250                      "    ++a;\n"
 251                      "  if (cond)\n"
 252                      "    a += 1;\n"
 253                      "  return a;\n"
 254                      "}\n";
 255   BuildResult B = BuildCFG(Code);
 256   EXPECT_EQ(BuildResult::BuiltCFG, B.getStatus());
 257   const FunctionDecl *Func = B.getFunc();
 258   AnalysisDeclContext AC(nullptr, Func);
 259   auto *CFG = AC.getCFG();
 260
 261   std::vector<const CFGBlock *> ReferenceOrder;
 262   for (const auto *B : *AC.getAnalysis<PostOrderCFGView>())
 263     ReferenceOrder.push_back(B);
 264
 265   {
 266     ForwardDataflowWorklist ForwardWorklist(*CFG, AC);
 267     for (const auto *B : *CFG)
 268       ForwardWorklist.enqueueBlock(B);
 269
 270     std::vector<const CFGBlock *> ForwardNodes;
 271     while (const CFGBlock *B = ForwardWorklist.dequeue())
 272       ForwardNodes.push_back(B);
 273
 274     EXPECT_EQ(ForwardNodes.size(), ReferenceOrder.size());
 275     EXPECT_TRUE(std::equal(ReferenceOrder.begin(), ReferenceOrder.end(),
 276                            ForwardNodes.begin()));
 277   }
 278
 279   {
 280     using ::testing::ElementsAreArray;
 281     std::optional<WeakTopologicalOrdering> WTO = getIntervalWTO(*CFG);
 282     ASSERT_TRUE(WTO);
 283     WTOCompare WCmp(*WTO);
 284     WTODataflowWorklist WTOWorklist(*CFG, WCmp);
 285     for (const auto *B : *CFG)
 286       WTOWorklist.enqueueBlock(B);
 287
 288     std::vector<const CFGBlock *> WTONodes;
 289     while (const CFGBlock *B = WTOWorklist.dequeue())
 290       WTONodes.push_back(B);
 291
 292     EXPECT_THAT(WTONodes, ElementsAreArray(*WTO));
 293   }
 294
 295   std::reverse(ReferenceOrder.begin(), ReferenceOrder.end());
 296
 297   {
 298     BackwardDataflowWorklist BackwardWorklist(*CFG, AC);
 299     for (const auto *B : *CFG)
 300       BackwardWorklist.enqueueBlock(B);
 301
 302     std::vector<const CFGBlock *> BackwardNodes;
 303     while (const CFGBlock *B = BackwardWorklist.dequeue())
 304       BackwardNodes.push_back(B);
 305
 306     EXPECT_EQ(BackwardNodes.size(), ReferenceOrder.size());
 307     EXPECT_TRUE(std::equal(ReferenceOrder.begin(), ReferenceOrder.end(),
 308                            BackwardNodes.begin()));
 309   }
 310 }
 311
 312 } // namespace
 313 } // namespace analysis
 314 } // namespace clang