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
23namespace clang {
24namespace analysis {
25namespace {
26
27// Constructing a CFG for a range-based for over a dependent type fails (but
28// 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 should
56// 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 type
66// 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, 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
113TEST(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
246TEST(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(x: 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(x: B);
291
292 EXPECT_THAT(WTONodes, ElementsAreArray(*WTO));
293 }
294
295 std::reverse(first: ReferenceOrder.begin(), last: 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(x: 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
315

source code of clang/unittests/Analysis/CFGTest.cpp