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