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 TEST(CFG, IsLinear) {
  74   auto expectLinear = [](bool IsLinear, const char *Code) {
  75     BuildResult B = BuildCFG(Code);
  76     EXPECT_EQ(BuildResult::BuiltCFG, B.getStatus());
  77     EXPECT_EQ(IsLinear, B.getCFG()->isLinear());
  78   };
  79
  80   expectLinear(true, "void foo() {}");
  81   expectLinear(true, "void foo() { if (true) return; }");
  82   expectLinear(true, "void foo() { if constexpr (false); }");
  83   expectLinear(false, "void foo(bool coin) { if (coin) return; }");
  84   expectLinear(false, "void foo() { for(;;); }");
  85   expectLinear(false, "void foo() { do {} while (true); }");
  86   expectLinear(true, "void foo() { do {} while (false); }");
  87   expectLinear(true, "void foo() { foo(); }"); // Recursion is not our problem.
  88 }
  89
  90 TEST(CFG, ElementRefIterator) {
  91   const char *Code = R"(void f() {
  92                           int i;
  93                           int j;
  94                           i = 5;
  95                           i = 6;
  96                           j = 7;
  97                         })";
  98
  99   BuildResult B = BuildCFG(Code);
 100   EXPECT_EQ(BuildResult::BuiltCFG, B.getStatus());
 101   CFG *Cfg = B.getCFG();
 102
 103   // [B2 (ENTRY)]
 104   //   Succs (1): B1
 105
 106   // [B1]
 107   //   1: int i;
 108   //   2: int j;
 109   //   3: i = 5
 110   //   4: i = 6
 111   //   5: j = 7
 112   //   Preds (1): B2
 113   //   Succs (1): B0
 114
 115   // [B0 (EXIT)]
 116   //   Preds (1): B1
 117   CFGBlock *MainBlock = *(Cfg->begin() + 1);
 118
 119   constexpr CFGBlock::ref_iterator::difference_type MainBlockSize = 4;
 120
 121   // The rest of this test looks totally insane, but there iterators are
 122   // templates under the hood, to it's important to instantiate everything for
 123   // proper converage.
 124
 125   // Non-reverse, non-const version
 126   size_t Index = 0;
 127   for (CFGBlock::CFGElementRef ElementRef : MainBlock->refs()) {
 128     EXPECT_EQ(ElementRef.getParent(), MainBlock);
 129     EXPECT_EQ(ElementRef.getIndexInBlock(), Index);
 130     EXPECT_TRUE(ElementRef->getAs<CFGStmt>());
 131     EXPECT_TRUE((*ElementRef).getAs<CFGStmt>());
 132     EXPECT_EQ(ElementRef.getParent(), MainBlock);
 133     ++Index;
 134   }
 135   EXPECT_TRUE(*MainBlock->ref_begin() < *(MainBlock->ref_begin() + 1));
 136   EXPECT_TRUE(*MainBlock->ref_begin() == *MainBlock->ref_begin());
 137   EXPECT_FALSE(*MainBlock->ref_begin() != *MainBlock->ref_begin());
 138
 139   EXPECT_TRUE(MainBlock->ref_begin() < MainBlock->ref_begin() + 1);
 140   EXPECT_TRUE(MainBlock->ref_begin() == MainBlock->ref_begin());
 141   EXPECT_FALSE(MainBlock->ref_begin() != MainBlock->ref_begin());
 142   EXPECT_EQ(MainBlock->ref_end() - MainBlock->ref_begin(), MainBlockSize + 1);
 143   EXPECT_EQ(MainBlock->ref_end() - MainBlockSize - 1, MainBlock->ref_begin());
 144   EXPECT_EQ(MainBlock->ref_begin() + MainBlockSize + 1, MainBlock->ref_end());
 145   EXPECT_EQ(MainBlock->ref_begin()++, MainBlock->ref_begin());
 146   EXPECT_EQ(++(MainBlock->ref_begin()), MainBlock->ref_begin() + 1);
 147
 148   // Non-reverse, non-const version
 149   const CFGBlock *CMainBlock = MainBlock;
 150   Index = 0;
 151   for (CFGBlock::ConstCFGElementRef ElementRef : CMainBlock->refs()) {
 152     EXPECT_EQ(ElementRef.getParent(), CMainBlock);
 153     EXPECT_EQ(ElementRef.getIndexInBlock(), Index);
 154     EXPECT_TRUE(ElementRef->getAs<CFGStmt>());
 155     EXPECT_TRUE((*ElementRef).getAs<CFGStmt>());
 156     EXPECT_EQ(ElementRef.getParent(), MainBlock);
 157     ++Index;
 158   }
 159   EXPECT_TRUE(*CMainBlock->ref_begin() < *(CMainBlock->ref_begin() + 1));
 160   EXPECT_TRUE(*CMainBlock->ref_begin() == *CMainBlock->ref_begin());
 161   EXPECT_FALSE(*CMainBlock->ref_begin() != *CMainBlock->ref_begin());
 162
 163   EXPECT_TRUE(CMainBlock->ref_begin() < CMainBlock->ref_begin() + 1);
 164   EXPECT_TRUE(CMainBlock->ref_begin() == CMainBlock->ref_begin());
 165   EXPECT_FALSE(CMainBlock->ref_begin() != CMainBlock->ref_begin());
 166   EXPECT_EQ(CMainBlock->ref_end() - CMainBlock->ref_begin(), MainBlockSize + 1);
 167   EXPECT_EQ(CMainBlock->ref_end() - MainBlockSize - 1, CMainBlock->ref_begin());
 168   EXPECT_EQ(CMainBlock->ref_begin() + MainBlockSize + 1, CMainBlock->ref_end());
 169   EXPECT_EQ(CMainBlock->ref_begin()++, CMainBlock->ref_begin());
 170   EXPECT_EQ(++(CMainBlock->ref_begin()), CMainBlock->ref_begin() + 1);
 171
 172   // Reverse, non-const version
 173   Index = MainBlockSize;
 174   for (CFGBlock::CFGElementRef ElementRef : MainBlock->rrefs()) {
 175     llvm::errs() << Index << '\n';
 176     EXPECT_EQ(ElementRef.getParent(), MainBlock);
 177     EXPECT_EQ(ElementRef.getIndexInBlock(), Index);
 178     EXPECT_TRUE(ElementRef->getAs<CFGStmt>());
 179     EXPECT_TRUE((*ElementRef).getAs<CFGStmt>());
 180     EXPECT_EQ(ElementRef.getParent(), MainBlock);
 181     --Index;
 182   }
 183   EXPECT_FALSE(*MainBlock->rref_begin() < *(MainBlock->rref_begin() + 1));
 184   EXPECT_TRUE(*MainBlock->rref_begin() == *MainBlock->rref_begin());
 185   EXPECT_FALSE(*MainBlock->rref_begin() != *MainBlock->rref_begin());
 186
 187   EXPECT_TRUE(MainBlock->rref_begin() < MainBlock->rref_begin() + 1);
 188   EXPECT_TRUE(MainBlock->rref_begin() == MainBlock->rref_begin());
 189   EXPECT_FALSE(MainBlock->rref_begin() != MainBlock->rref_begin());
 190   EXPECT_EQ(MainBlock->rref_end() - MainBlock->rref_begin(), MainBlockSize + 1);
 191   EXPECT_EQ(MainBlock->rref_end() - MainBlockSize - 1, MainBlock->rref_begin());
 192   EXPECT_EQ(MainBlock->rref_begin() + MainBlockSize + 1, MainBlock->rref_end());
 193   EXPECT_EQ(MainBlock->rref_begin()++, MainBlock->rref_begin());
 194   EXPECT_EQ(++(MainBlock->rref_begin()), MainBlock->rref_begin() + 1);
 195
 196   // Reverse, const version
 197   Index = MainBlockSize;
 198   for (CFGBlock::ConstCFGElementRef ElementRef : CMainBlock->rrefs()) {
 199     EXPECT_EQ(ElementRef.getParent(), CMainBlock);
 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(*CMainBlock->rref_begin() < *(CMainBlock->rref_begin() + 1));
 207   EXPECT_TRUE(*CMainBlock->rref_begin() == *CMainBlock->rref_begin());
 208   EXPECT_FALSE(*CMainBlock->rref_begin() != *CMainBlock->rref_begin());
 209
 210   EXPECT_TRUE(CMainBlock->rref_begin() < CMainBlock->rref_begin() + 1);
 211   EXPECT_TRUE(CMainBlock->rref_begin() == CMainBlock->rref_begin());
 212   EXPECT_FALSE(CMainBlock->rref_begin() != CMainBlock->rref_begin());
 213   EXPECT_EQ(CMainBlock->rref_end() - CMainBlock->rref_begin(),
 214             MainBlockSize + 1);
 215   EXPECT_EQ(CMainBlock->rref_end() - MainBlockSize - 1,
 216             CMainBlock->rref_begin());
 217   EXPECT_EQ(CMainBlock->rref_begin() + MainBlockSize + 1,
 218             CMainBlock->rref_end());
 219   EXPECT_EQ(CMainBlock->rref_begin()++, CMainBlock->rref_begin());
 220   EXPECT_EQ(++(CMainBlock->rref_begin()), CMainBlock->rref_begin() + 1);
 221 }
 222
 223 TEST(CFG, Worklists) {
 224   const char *Code = "int f(bool cond) {\n"
 225                      "  int a = 5;\n"
 226                      "  if (cond)\n"
 227                      "    a += 1;\n"
 228                      "  return a;\n"
 229                      "}\n";
 230   BuildResult B = BuildCFG(Code);
 231   EXPECT_EQ(BuildResult::BuiltCFG, B.getStatus());
 232   const FunctionDecl *Func = B.getFunc();
 233   AnalysisDeclContext AC(nullptr, Func);
 234   auto *CFG = AC.getCFG();
 235
 236   std::vector<const CFGBlock *> ReferenceOrder;
 237   for (const auto *B : *AC.getAnalysis<PostOrderCFGView>())
 238     ReferenceOrder.push_back(B);
 239
 240   {
 241     ForwardDataflowWorklist ForwardWorklist(*CFG, AC);
 242     for (const auto *B : *CFG)
 243       ForwardWorklist.enqueueBlock(B);
 244
 245     std::vector<const CFGBlock *> ForwardNodes;
 246     while (const CFGBlock *B = ForwardWorklist.dequeue())
 247       ForwardNodes.push_back(B);
 248
 249     EXPECT_EQ(ForwardNodes.size(), ReferenceOrder.size());
 250     EXPECT_TRUE(std::equal(ReferenceOrder.begin(), ReferenceOrder.end(),
 251                            ForwardNodes.begin()));
 252   }
 253
 254   std::reverse(ReferenceOrder.begin(), ReferenceOrder.end());
 255
 256   {
 257     BackwardDataflowWorklist BackwardWorklist(*CFG, AC);
 258     for (const auto *B : *CFG)
 259       BackwardWorklist.enqueueBlock(B);
 260
 261     std::vector<const CFGBlock *> BackwardNodes;
 262     while (const CFGBlock *B = BackwardWorklist.dequeue())
 263       BackwardNodes.push_back(B);
 264
 265     EXPECT_EQ(BackwardNodes.size(), ReferenceOrder.size());
 266     EXPECT_TRUE(std::equal(ReferenceOrder.begin(), ReferenceOrder.end(),
 267                            BackwardNodes.begin()));
 268   }
 269 }
 270
 271 } // namespace
 272 } // namespace analysis
 273 } // namespace clang