Debian Codegraph @

llvm-project/clang/unittests/Analysis/FlowSensitive/TestingSupport.h

raw
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 <optional>
19 #include <ostream>
20 #include <string>
21 #include <utility>
22 #include <vector>
23
24 #include "clang/AST/ASTContext.h"
25 #include "clang/AST/Decl.h"
26 #include "clang/AST/Stmt.h"
27 #include "clang/ASTMatchers/ASTMatchFinder.h"
28 #include "clang/ASTMatchers/ASTMatchers.h"
29 #include "clang/ASTMatchers/ASTMatchersInternal.h"
30 #include "clang/Analysis/CFG.h"
31 #include "clang/Analysis/FlowSensitive/ControlFlowContext.h"
32 #include "clang/Analysis/FlowSensitive/DataflowAnalysis.h"
33 #include "clang/Analysis/FlowSensitive/DataflowAnalysisContext.h"
34 #include "clang/Analysis/FlowSensitive/DataflowEnvironment.h"
35 #include "clang/Analysis/FlowSensitive/MatchSwitch.h"
36 #include "clang/Analysis/FlowSensitive/WatchedLiteralsSolver.h"
37 #include "clang/Basic/LLVM.h"
38 #include "clang/Serialization/PCHContainerOperations.h"
39 #include "clang/Tooling/ArgumentsAdjusters.h"
40 #include "clang/Tooling/Tooling.h"
41 #include "llvm/ADT/ArrayRef.h"
42 #include "llvm/ADT/DenseMap.h"
43 #include "llvm/ADT/StringMap.h"
44 #include "llvm/ADT/StringRef.h"
45 #include "llvm/Support/Errc.h"
46 #include "llvm/Support/Error.h"
47 #include "llvm/Testing/Annotations/Annotations.h"
48
49 namespace clang {
50 namespace dataflow {
51
52 // Requires a `<<` operator for the `Lattice` type.
53 // FIXME: move to a non-test utility library.
54 template <typename Lattice>
55 std::ostream &operator<<(std::ostream &OS,
56 const DataflowAnalysisState<Lattice> &S) {
57 // FIXME: add printing support for the environment.
58 return OS << "{lattice=" << S.Lattice << ", environment=...}";
59 }
60
61 namespace test {
62
63 /// Returns the environment at the program point marked with `Annotation` from
64 /// the mapping of annotated program points to analysis state.
65 ///
66 /// Requirements:
67 ///
68 /// `Annotation` must be present as a key in `AnnotationStates`.
69 template <typename LatticeT>
70 const Environment &getEnvironmentAtAnnotation(
71 const llvm::StringMap<DataflowAnalysisState<LatticeT>> &AnnotationStates,
72 llvm::StringRef Annotation) {
73 auto It = AnnotationStates.find(Annotation);
74 assert(It != AnnotationStates.end());
75 return It->getValue().Env;
76 }
77
78 /// Contains data structures required and produced by a dataflow analysis run.
79 struct AnalysisOutputs {
80 /// Input code that is analyzed. Points within the code may be marked with
81 /// annotations to facilitate testing.
82 ///
83 /// Example:
84 /// void target(int *x) {
85 /// *x; // [[p]]
86 /// }
87 /// From the annotation `p`, the line number and analysis state immediately
88 /// after the statement `*x` can be retrieved and verified.
89 llvm::Annotations Code;
90 /// AST context generated from `Code`.
91 ASTContext &ASTCtx;
92 /// The function whose body is analyzed.
93 const FunctionDecl *Target;
94 /// Contains the control flow graph built from the body of the `Target`
95 /// function and is analyzed.
96 const ControlFlowContext &CFCtx;
97 /// The analysis to be run.
98 TypeErasedDataflowAnalysis &Analysis;
99 /// Initial state to start the analysis.
100 const Environment &InitEnv;
101 // Stores the state of a CFG block if it has been evaluated by the analysis.
102 // The indices correspond to the block IDs.
103 llvm::ArrayRef<std::optional<TypeErasedDataflowAnalysisState>> BlockStates;
104 };
105
106 /// Arguments for building the dataflow analysis.
107 template <typename AnalysisT> struct AnalysisInputs {
108 /// Required fields are set in constructor.
109 AnalysisInputs(
110 llvm::StringRef CodeArg,
111 ast_matchers::internal::Matcher<FunctionDecl> TargetFuncMatcherArg,
112 std::function<AnalysisT(ASTContext &, Environment &)> MakeAnalysisArg)
113 : Code(CodeArg), TargetFuncMatcher(std::move(TargetFuncMatcherArg)),
114 MakeAnalysis(std::move(MakeAnalysisArg)) {}
115
116 /// Optional fields can be set with methods of the form `withFieldName(...)`.
117 AnalysisInputs<AnalysisT> &&
118 withSetupTest(std::function<llvm::Error(AnalysisOutputs &)> Arg) && {
119 SetupTest = std::move(Arg);
120 return std::move(*this);
121 }
122 AnalysisInputs<AnalysisT> &&withPostVisitCFG(
123 std::function<void(
124 ASTContext &, const CFGElement &,
125 const TransferStateForDiagnostics<typename AnalysisT::Lattice> &)>
126 Arg) && {
127 PostVisitCFG = std::move(Arg);
128 return std::move(*this);
129 }
130 AnalysisInputs<AnalysisT> &&withASTBuildArgs(ArrayRef<std::string> Arg) && {
131 ASTBuildArgs = std::move(Arg);
132 return std::move(*this);
133 }
134 AnalysisInputs<AnalysisT> &&
135 withASTBuildVirtualMappedFiles(tooling::FileContentMappings Arg) && {
136 ASTBuildVirtualMappedFiles = std::move(Arg);
137 return std::move(*this);
138 }
139 AnalysisInputs<AnalysisT> &&
140 withBuiltinOptions(DataflowAnalysisContext::Options Options) && {
141 BuiltinOptions = std::move(Options);
142 return std::move(*this);
143 }
144
145 /// Required. Input code that is analyzed.
146 llvm::StringRef Code;
147 /// Required. All functions that match this matcher are analyzed.
148 ast_matchers::internal::Matcher<FunctionDecl> TargetFuncMatcher;
149 /// Required. The analysis to be run is constructed with this function that
150 /// takes as argument the AST generated from the code being analyzed and the
151 /// initial state from which the analysis starts with.
152 std::function<AnalysisT(ASTContext &, Environment &)> MakeAnalysis;
153 /// Optional. If provided, this function is executed immediately before
154 /// running the dataflow analysis to allow for additional setup. All fields in
155 /// the `AnalysisOutputs` argument will be initialized except for the
156 /// `BlockStates` field which is only computed later during the analysis.
157 std::function<llvm::Error(AnalysisOutputs &)> SetupTest = nullptr;
158 /// Optional. If provided, this function is applied on each CFG element after
159 /// the analysis has been run.
160 std::function<void(
161 ASTContext &, const CFGElement &,
162 const TransferStateForDiagnostics<typename AnalysisT::Lattice> &)>
163 PostVisitCFG = nullptr;
164
165 /// Optional. Options for building the AST context.
166 ArrayRef<std::string> ASTBuildArgs = {};
167 /// Optional. Options for building the AST context.
168 tooling::FileContentMappings ASTBuildVirtualMappedFiles = {};
169 /// Configuration options for the built-in model.
170 DataflowAnalysisContext::Options BuiltinOptions;
171 };
172
173 /// Returns assertions based on annotations that are present after statements in
174 /// `AnnotatedCode`.
175 llvm::Expected<llvm::DenseMap<const Stmt *, std::string>>
176 buildStatementToAnnotationMapping(const FunctionDecl *Func,
177 llvm::Annotations AnnotatedCode);
178
179 /// Returns line numbers and content of the annotations in `AnnotatedCode`
180 /// within the token range `BoundingRange`.
181 llvm::DenseMap<unsigned, std::string> buildLineToAnnotationMapping(
182 const SourceManager &SM, const LangOptions &LangOpts,
183 SourceRange BoundingRange, llvm::Annotations AnnotatedCode);
184
185 /// Runs dataflow specified from `AI.MakeAnalysis` and `AI.PostVisitCFG` on all
186 /// functions that match `AI.TargetFuncMatcher` in `AI.Code`. Given the
187 /// analysis outputs, `VerifyResults` checks that the results from the analysis
188 /// are correct.
189 ///
190 /// Requirements:
191 ///
192 /// `AnalysisT` contains a type `Lattice`.
193 ///
194 /// `Code`, `TargetFuncMatcher` and `MakeAnalysis` must be provided in `AI`.
195 ///
196 /// `VerifyResults` must be provided.
197 template <typename AnalysisT>
198 llvm::Error
199 checkDataflow(AnalysisInputs<AnalysisT> AI,
200 std::function<void(const AnalysisOutputs &)> VerifyResults) {
201 // Build AST context from code.
202 llvm::Annotations AnnotatedCode(AI.Code);
203 auto Unit = tooling::buildASTFromCodeWithArgs(
204 AnnotatedCode.code(), AI.ASTBuildArgs, "input.cc", "clang-dataflow-test",
205 std::make_shared<PCHContainerOperations>(),
206 tooling::getClangStripDependencyFileAdjuster(),
207 AI.ASTBuildVirtualMappedFiles);
208 auto &Context = Unit->getASTContext();
209
210 if (Context.getDiagnostics().getClient()->getNumErrors() != 0) {
211 return llvm::make_error<llvm::StringError>(
212 llvm::errc::invalid_argument, "Source file has syntax or type errors, "
213 "they were printed to the test log");
214 }
215
216 std::function<void(const CFGElement &,
217 const TypeErasedDataflowAnalysisState &)>
218 TypeErasedPostVisitCFG = nullptr;
219 if (AI.PostVisitCFG) {
220 TypeErasedPostVisitCFG = [&AI, &Context](
221 const CFGElement &Element,
222 const TypeErasedDataflowAnalysisState &State) {
223 AI.PostVisitCFG(Context, Element,
224 TransferStateForDiagnostics<typename AnalysisT::Lattice>(
225 llvm::any_cast<const typename AnalysisT::Lattice &>(
226 State.Lattice.Value),
227 State.Env));
228 };
229 }
230
231 for (const ast_matchers::BoundNodes &BN :
232 ast_matchers::match(ast_matchers::functionDecl(
233 ast_matchers::hasBody(ast_matchers::stmt()),
234 AI.TargetFuncMatcher)
235 .bind("target"),
236 Context)) {
237 // Get the AST node of the target function.
238 const FunctionDecl *Target = BN.getNodeAs<FunctionDecl>("target");
239 if (Target == nullptr)
240 return llvm::make_error<llvm::StringError>(
241 llvm::errc::invalid_argument, "Could not find the target function.");
242
243 // Build the control flow graph for the target function.
244 auto MaybeCFCtx =
245 ControlFlowContext::build(Target, *Target->getBody(), Context);
246 if (!MaybeCFCtx) return MaybeCFCtx.takeError();
247 auto &CFCtx = *MaybeCFCtx;
248
249 // Initialize states for running dataflow analysis.
250 DataflowAnalysisContext DACtx(std::make_unique<WatchedLiteralsSolver>(),
251 {/*Opts=*/AI.BuiltinOptions});
252 Environment InitEnv(DACtx, *Target);
253 auto Analysis = AI.MakeAnalysis(Context, InitEnv);
254
255 AnalysisOutputs AO{AnnotatedCode, Context, Target, CFCtx,
256 Analysis, InitEnv, {}};
257
258 // Additional test setup.
259 if (AI.SetupTest) {
260 if (auto Error = AI.SetupTest(AO)) return Error;
261 }
262
263 // If successful, the dataflow analysis returns a mapping from block IDs to
264 // the post-analysis states for the CFG blocks that have been evaluated.
265 llvm::Expected<std::vector<llvm::Optional<TypeErasedDataflowAnalysisState>>>
266 MaybeBlockStates = runTypeErasedDataflowAnalysis(
267 CFCtx, Analysis, InitEnv, TypeErasedPostVisitCFG);
268 if (!MaybeBlockStates) return MaybeBlockStates.takeError();
269 AO.BlockStates = *MaybeBlockStates;
270
271 // Verify dataflow analysis outputs.
272 VerifyResults(AO);
273 }
274
275 return llvm::Error::success();
276 }
277
278 /// Runs dataflow specified from `AI.MakeAnalysis` and `AI.PostVisitCFG` on all
279 /// functions that match `AI.TargetFuncMatcher` in `AI.Code`. Given the
280 /// annotation line numbers and analysis outputs, `VerifyResults` checks that
281 /// the results from the analysis are correct.
282 ///
283 /// Requirements:
284 ///
285 /// `AnalysisT` contains a type `Lattice`.
286 ///
287 /// `Code`, `TargetFuncMatcher` and `MakeAnalysis` must be provided in `AI`.
288 ///
289 /// `VerifyResults` must be provided.
290 template <typename AnalysisT>
291 llvm::Error
292 checkDataflow(AnalysisInputs<AnalysisT> AI,
293 std::function<void(const llvm::DenseMap<unsigned, std::string> &,
294 const AnalysisOutputs &)>
295 VerifyResults) {
296 return checkDataflow<AnalysisT>(
297 std::move(AI), [&VerifyResults](const AnalysisOutputs &AO) {
298 auto AnnotationLinesAndContent = buildLineToAnnotationMapping(
299 AO.ASTCtx.getSourceManager(), AO.ASTCtx.getLangOpts(),
300 AO.Target->getSourceRange(), AO.Code);
301 VerifyResults(AnnotationLinesAndContent, AO);
302 });
303 }
304
305 /// Runs dataflow specified from `AI.MakeAnalysis` and `AI.PostVisitCFG` on all
306 /// functions that match `AI.TargetFuncMatcher` in `AI.Code`. Given the state
307 /// computed at each annotated statement and analysis outputs, `VerifyResults`
308 /// checks that the results from the analysis are correct.
309 ///
310 /// Requirements:
311 ///
312 /// `AnalysisT` contains a type `Lattice`.
313 ///
314 /// `Code`, `TargetFuncMatcher` and `MakeAnalysis` must be provided in `AI`.
315 ///
316 /// `VerifyResults` must be provided.
317 ///
318 /// Any annotations appearing in `Code` must come after a statement.
319 ///
320 /// There can be at most one annotation attached per statement.
321 ///
322 /// Annotations must not be repeated.
323 template <typename AnalysisT>
324 llvm::Error
325 checkDataflow(AnalysisInputs<AnalysisT> AI,
326 std::function<void(const llvm::StringMap<DataflowAnalysisState<
327 typename AnalysisT::Lattice>> &,
328 const AnalysisOutputs &)>
329 VerifyResults) {
330 // Compute mapping from nodes of annotated statements to the content in the
331 // annotation.
332 llvm::DenseMap<const Stmt *, std::string> StmtToAnnotations;
333 auto SetupTest = [&StmtToAnnotations,
334 PrevSetupTest = std::move(AI.SetupTest)](
335 AnalysisOutputs &AO) -> llvm::Error {
336 auto MaybeStmtToAnnotations = buildStatementToAnnotationMapping(
337 cast<FunctionDecl>(AO.InitEnv.getDeclCtx()), AO.Code);
338 if (!MaybeStmtToAnnotations) {
339 return MaybeStmtToAnnotations.takeError();
340 }
341 StmtToAnnotations = std::move(*MaybeStmtToAnnotations);
342 return PrevSetupTest ? PrevSetupTest(AO) : llvm::Error::success();
343 };
344
345 using StateT = DataflowAnalysisState<typename AnalysisT::Lattice>;
346
347 // Save the states computed for program points immediately following annotated
348 // statements. The saved states are keyed by the content of the annotation.
349 llvm::StringMap<StateT> AnnotationStates;
350 auto PostVisitCFG =
351 [&StmtToAnnotations, &AnnotationStates,
352 PrevPostVisitCFG = std::move(AI.PostVisitCFG)](
353 ASTContext &Ctx, const CFGElement &Elt,
354 const TransferStateForDiagnostics<typename AnalysisT::Lattice>
355 &State) {
356 if (PrevPostVisitCFG) {
357 PrevPostVisitCFG(Ctx, Elt, State);
358 }
359 // FIXME: Extend retrieval of state for non statement constructs.
360 auto Stmt = Elt.getAs<CFGStmt>();
361 if (!Stmt)
362 return;
363 auto It = StmtToAnnotations.find(Stmt->getStmt());
364 if (It == StmtToAnnotations.end())
365 return;
366 auto [_, InsertSuccess] = AnnotationStates.insert(
367 {It->second, StateT{State.Lattice, State.Env}});
368 (void)_;
369 (void)InsertSuccess;
370 assert(InsertSuccess);
371 };
372 return checkDataflow<AnalysisT>(
373 std::move(AI)
374 .withSetupTest(std::move(SetupTest))
375 .withPostVisitCFG(std::move(PostVisitCFG)),
376 [&VerifyResults, &AnnotationStates](const AnalysisOutputs &AO) {
377 VerifyResults(AnnotationStates, AO);
378
379 // `checkDataflow()` can analyze more than one function. Reset the
380 // variables to prepare for analyzing the next function.
381 AnnotationStates.clear();
382 });
383 }
384
385 /// Returns the `ValueDecl` for the given identifier.
386 ///
387 /// Requirements:
388 ///
389 /// `Name` must be unique in `ASTCtx`.
390 const ValueDecl *findValueDecl(ASTContext &ASTCtx, llvm::StringRef Name);
391
392 /// Creates and owns constraints which are boolean values.
393 class ConstraintContext {
394 public:
395 // Creates an atomic boolean value.
396 BoolValue *atom() {
397 Vals.push_back(std::make_unique<AtomicBoolValue>());
398 return Vals.back().get();
399 }
400
401 // Creates an instance of the Top boolean value.
402 BoolValue *top() {
403 Vals.push_back(std::make_unique<TopBoolValue>());
404 return Vals.back().get();
405 }
406
407 // Creates a boolean conjunction value.
408 BoolValue *conj(BoolValue *LeftSubVal, BoolValue *RightSubVal) {
409 Vals.push_back(
410 std::make_unique<ConjunctionValue>(*LeftSubVal, *RightSubVal));
411 return Vals.back().get();
412 }
413
414 // Creates a boolean disjunction value.
415 BoolValue *disj(BoolValue *LeftSubVal, BoolValue *RightSubVal) {
416 Vals.push_back(
417 std::make_unique<DisjunctionValue>(*LeftSubVal, *RightSubVal));
418 return Vals.back().get();
419 }
420
421 // Creates a boolean negation value.
422 BoolValue *neg(BoolValue *SubVal) {
423 Vals.push_back(std::make_unique<NegationValue>(*SubVal));
424 return Vals.back().get();
425 }
426
427 // Creates a boolean implication value.
428 BoolValue *impl(BoolValue *LeftSubVal, BoolValue *RightSubVal) {
429 Vals.push_back(
430 std::make_unique<ImplicationValue>(*LeftSubVal, *RightSubVal));
431 return Vals.back().get();
432 }
433
434 // Creates a boolean biconditional value.
435 BoolValue *iff(BoolValue *LeftSubVal, BoolValue *RightSubVal) {
436 Vals.push_back(
437 std::make_unique<BiconditionalValue>(*LeftSubVal, *RightSubVal));
438 return Vals.back().get();
439 }
440
441 private:
442 std::vector<std::unique_ptr<BoolValue>> Vals;
443 };
444
445 } // namespace test
446 } // namespace dataflow
447 } // namespace clang
448
449 #endif // LLVM_CLANG_ANALYSIS_FLOW_SENSITIVE_TESTING_SUPPORT_H_