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
274