1 //===--- TestingSupport.h - Testing utils for dataflow analyses -*- C++ -*-===//
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 // This file defines utilities to simplify testing of dataflow analyses.
10 //
11 //===----------------------------------------------------------------------===//
12 
13 #ifndef LLVM_CLANG_ANALYSIS_FLOW_SENSITIVE_TESTING_SUPPORT_H_
14 #define LLVM_CLANG_ANALYSIS_FLOW_SENSITIVE_TESTING_SUPPORT_H_
15 
16 #include <functional>
17 #include <memory>
18 #include <ostream>
19 #include <string>
20 #include <utility>
21 #include <vector>
22 
23 #include "clang/AST/ASTContext.h"
24 #include "clang/AST/Decl.h"
25 #include "clang/AST/Stmt.h"
26 #include "clang/ASTMatchers/ASTMatchFinder.h"
27 #include "clang/ASTMatchers/ASTMatchers.h"
28 #include "clang/ASTMatchers/ASTMatchersInternal.h"
29 #include "clang/Analysis/CFG.h"
30 #include "clang/Analysis/FlowSensitive/ControlFlowContext.h"
31 #include "clang/Analysis/FlowSensitive/DataflowAnalysis.h"
32 #include "clang/Analysis/FlowSensitive/DataflowEnvironment.h"
33 #include "clang/Analysis/FlowSensitive/WatchedLiteralsSolver.h"
34 #include "clang/Basic/LLVM.h"
35 #include "clang/Serialization/PCHContainerOperations.h"
36 #include "clang/Tooling/ArgumentsAdjusters.h"
37 #include "clang/Tooling/Tooling.h"
38 #include "llvm/ADT/ArrayRef.h"
39 #include "llvm/ADT/DenseMap.h"
40 #include "llvm/ADT/StringRef.h"
41 #include "llvm/Support/Errc.h"
42 #include "llvm/Support/Error.h"
43 #include "llvm/Testing/Support/Annotations.h"
44 
45 namespace clang {
46 namespace dataflow {
47 
48 // Requires a `<<` operator for the `Lattice` type.
49 // FIXME: move to a non-test utility library.
50 template <typename Lattice>
51 std::ostream &operator<<(std::ostream &OS,
52                          const DataflowAnalysisState<Lattice> &S) {
53   // FIXME: add printing support for the environment.
54   return OS << "{lattice=" << S.Lattice << ", environment=...}";
55 }
56 
57 namespace test {
58 
59 // Returns assertions based on annotations that are present after statements in
60 // `AnnotatedCode`.
61 llvm::Expected<llvm::DenseMap<const Stmt *, std::string>>
62 buildStatementToAnnotationMapping(const FunctionDecl *Func,
63                                   llvm::Annotations AnnotatedCode);
64 
65 struct AnalysisData {
66   ASTContext &ASTCtx;
67   const ControlFlowContext &CFCtx;
68   const Environment &Env;
69   TypeErasedDataflowAnalysis &Analysis;
70   llvm::DenseMap<const clang::Stmt *, std::string> &Annotations;
71   std::vector<llvm::Optional<TypeErasedDataflowAnalysisState>> &BlockStates;
72 };
73 
74 template <typename AnalysisT>
75 llvm::Error checkDataflow(
76     llvm::StringRef Code,
77     ast_matchers::internal::Matcher<FunctionDecl> TargetFuncMatcher,
78     std::function<AnalysisT(ASTContext &, Environment &)> MakeAnalysis,
79     std::function<void(ASTContext &, const Stmt *,
80                        const TypeErasedDataflowAnalysisState &)>
81         PostVisitStmt,
82     std::function<void(AnalysisData)> VerifyResults, ArrayRef<std::string> Args,
83     const tooling::FileContentMappings &VirtualMappedFiles = {}) {
84   llvm::Annotations AnnotatedCode(Code);
85   auto Unit = tooling::buildASTFromCodeWithArgs(
86       AnnotatedCode.code(), Args, "input.cc", "clang-dataflow-test",
87       std::make_shared<PCHContainerOperations>(),
88       tooling::getClangStripDependencyFileAdjuster(), VirtualMappedFiles);
89   auto &Context = Unit->getASTContext();
90 
91   if (Context.getDiagnostics().getClient()->getNumErrors() != 0) {
92     return llvm::make_error<llvm::StringError>(
93         llvm::errc::invalid_argument, "Source file has syntax or type errors, "
94                                       "they were printed to the test log");
95   }
96 
97   const FunctionDecl *F = ast_matchers::selectFirst<FunctionDecl>(
98       "target",
99       ast_matchers::match(ast_matchers::functionDecl(
100                               ast_matchers::isDefinition(), TargetFuncMatcher)
101                               .bind("target"),
102                           Context));
103   if (F == nullptr)
104     return llvm::make_error<llvm::StringError>(
105         llvm::errc::invalid_argument, "Could not find target function.");
106 
107   auto CFCtx = ControlFlowContext::build(F, F->getBody(), &F->getASTContext());
108   if (!CFCtx)
109     return CFCtx.takeError();
110 
111   DataflowAnalysisContext DACtx(std::make_unique<WatchedLiteralsSolver>());
112   Environment Env(DACtx, *F);
113   auto Analysis = MakeAnalysis(Context, Env);
114 
115   std::function<void(const Stmt *, const TypeErasedDataflowAnalysisState &)>
116       PostVisitStmtClosure = nullptr;
117   if (PostVisitStmt != nullptr) {
118     PostVisitStmtClosure = [&PostVisitStmt, &Context](
119                                const Stmt *Stmt,
120                                const TypeErasedDataflowAnalysisState &State) {
121       PostVisitStmt(Context, Stmt, State);
122     };
123   }
124 
125   llvm::Expected<llvm::DenseMap<const clang::Stmt *, std::string>>
126       StmtToAnnotations = buildStatementToAnnotationMapping(F, AnnotatedCode);
127   if (!StmtToAnnotations)
128     return StmtToAnnotations.takeError();
129   auto &Annotations = *StmtToAnnotations;
130 
131   llvm::Expected<std::vector<llvm::Optional<TypeErasedDataflowAnalysisState>>>
132       MaybeBlockStates = runTypeErasedDataflowAnalysis(*CFCtx, Analysis, Env,
133                                                        PostVisitStmtClosure);
134   if (!MaybeBlockStates)
135     return MaybeBlockStates.takeError();
136   auto &BlockStates = *MaybeBlockStates;
137 
138   AnalysisData AnalysisData{Context,  *CFCtx,      Env,
139                             Analysis, Annotations, BlockStates};
140   VerifyResults(AnalysisData);
141   return llvm::Error::success();
142 }
143 
144 // Runs dataflow on the body of the function that matches `TargetFuncMatcher` in
145 // code snippet `Code`. Requires: `AnalysisT` contains a type `Lattice`.
146 template <typename AnalysisT>
147 llvm::Error checkDataflow(
148     llvm::StringRef Code,
149     ast_matchers::internal::Matcher<FunctionDecl> TargetFuncMatcher,
150     std::function<AnalysisT(ASTContext &, Environment &)> MakeAnalysis,
151     std::function<void(
152         llvm::ArrayRef<std::pair<
153             std::string, DataflowAnalysisState<typename AnalysisT::Lattice>>>,
154         ASTContext &)>
155         VerifyResults,
156     ArrayRef<std::string> Args,
157     const tooling::FileContentMappings &VirtualMappedFiles = {}) {
158   using StateT = DataflowAnalysisState<typename AnalysisT::Lattice>;
159 
160   return checkDataflow(
161       Code, std::move(TargetFuncMatcher), std::move(MakeAnalysis),
162       /*PostVisitStmt=*/nullptr,
163       [&VerifyResults](AnalysisData AnalysisData) {
164         if (AnalysisData.BlockStates.empty()) {
165           VerifyResults({}, AnalysisData.ASTCtx);
166           return;
167         }
168 
169         auto &Annotations = AnalysisData.Annotations;
170 
171         // Compute a map from statement annotations to the state computed for
172         // the program point immediately after the annotated statement.
173         std::vector<std::pair<std::string, StateT>> Results;
174         for (const CFGBlock *Block : AnalysisData.CFCtx.getCFG()) {
175           // Skip blocks that were not evaluated.
176           if (!AnalysisData.BlockStates[Block->getBlockID()])
177             continue;
178 
179           transferBlock(
180               AnalysisData.CFCtx, AnalysisData.BlockStates, *Block,
181               AnalysisData.Env, AnalysisData.Analysis,
182               [&Results,
183                &Annotations](const clang::CFGStmt &Stmt,
184                              const TypeErasedDataflowAnalysisState &State) {
185                 auto It = Annotations.find(Stmt.getStmt());
186                 if (It == Annotations.end())
187                   return;
188                 auto *Lattice = llvm::any_cast<typename AnalysisT::Lattice>(
189                     &State.Lattice.Value);
190                 Results.emplace_back(It->second, StateT{*Lattice, State.Env});
191               });
192         }
193         VerifyResults(Results, AnalysisData.ASTCtx);
194       },
195       Args, VirtualMappedFiles);
196 }
197 
198 // Runs dataflow on the body of the function named `target_fun` in code snippet
199 // `code`.
200 template <typename AnalysisT>
201 llvm::Error checkDataflow(
202     llvm::StringRef Code, llvm::StringRef TargetFun,
203     std::function<AnalysisT(ASTContext &, Environment &)> MakeAnalysis,
204     std::function<void(
205         llvm::ArrayRef<std::pair<
206             std::string, DataflowAnalysisState<typename AnalysisT::Lattice>>>,
207         ASTContext &)>
208         VerifyResults,
209     ArrayRef<std::string> Args,
210     const tooling::FileContentMappings &VirtualMappedFiles = {}) {
211   return checkDataflow(Code, ast_matchers::hasName(TargetFun),
212                        std::move(MakeAnalysis), std::move(VerifyResults), Args,
213                        VirtualMappedFiles);
214 }
215 
216 /// Returns the `ValueDecl` for the given identifier.
217 ///
218 /// Requirements:
219 ///
220 ///  `Name` must be unique in `ASTCtx`.
221 const ValueDecl *findValueDecl(ASTContext &ASTCtx, llvm::StringRef Name);
222 
223 /// Creates and owns constraints which are boolean values.
224 class ConstraintContext {
225 public:
226   // Creates an atomic boolean value.
atom()227   BoolValue *atom() {
228     Vals.push_back(std::make_unique<AtomicBoolValue>());
229     return Vals.back().get();
230   }
231 
232   // Creates a boolean conjunction value.
conj(BoolValue * LeftSubVal,BoolValue * RightSubVal)233   BoolValue *conj(BoolValue *LeftSubVal, BoolValue *RightSubVal) {
234     Vals.push_back(
235         std::make_unique<ConjunctionValue>(*LeftSubVal, *RightSubVal));
236     return Vals.back().get();
237   }
238 
239   // Creates a boolean disjunction value.
disj(BoolValue * LeftSubVal,BoolValue * RightSubVal)240   BoolValue *disj(BoolValue *LeftSubVal, BoolValue *RightSubVal) {
241     Vals.push_back(
242         std::make_unique<DisjunctionValue>(*LeftSubVal, *RightSubVal));
243     return Vals.back().get();
244   }
245 
246   // Creates a boolean negation value.
neg(BoolValue * SubVal)247   BoolValue *neg(BoolValue *SubVal) {
248     Vals.push_back(std::make_unique<NegationValue>(*SubVal));
249     return Vals.back().get();
250   }
251 
252   // Creates a boolean implication value.
impl(BoolValue * LeftSubVal,BoolValue * RightSubVal)253   BoolValue *impl(BoolValue *LeftSubVal, BoolValue *RightSubVal) {
254     Vals.push_back(
255         std::make_unique<ImplicationValue>(*LeftSubVal, *RightSubVal));
256     return Vals.back().get();
257   }
258 
259   // Creates a boolean biconditional value.
iff(BoolValue * LeftSubVal,BoolValue * RightSubVal)260   BoolValue *iff(BoolValue *LeftSubVal, BoolValue *RightSubVal) {
261     Vals.push_back(
262         std::make_unique<BiconditionalValue>(*LeftSubVal, *RightSubVal));
263     return Vals.back().get();
264   }
265 
266 private:
267   std::vector<std::unique_ptr<BoolValue>> Vals;
268 };
269 
270 } // namespace test
271 } // namespace dataflow
272 } // namespace clang
273 
274 #endif // LLVM_CLANG_ANALYSIS_FLOW_SENSITIVE_TESTING_SUPPORT_H_
275