13dd7877bSStanislav Gatev //===--- TestingSupport.h - Testing utils for dataflow analyses -*- C++ -*-===//
23dd7877bSStanislav Gatev //
33dd7877bSStanislav Gatev // Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.
43dd7877bSStanislav Gatev // See https://llvm.org/LICENSE.txt for license information.
53dd7877bSStanislav Gatev // SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception
63dd7877bSStanislav Gatev //
73dd7877bSStanislav Gatev //===----------------------------------------------------------------------===//
83dd7877bSStanislav Gatev //
93dd7877bSStanislav Gatev // This file defines utilities to simplify testing of dataflow analyses.
103dd7877bSStanislav Gatev //
113dd7877bSStanislav Gatev //===----------------------------------------------------------------------===//
123dd7877bSStanislav Gatev
133dd7877bSStanislav Gatev #ifndef LLVM_CLANG_ANALYSIS_FLOW_SENSITIVE_TESTING_SUPPORT_H_
143dd7877bSStanislav Gatev #define LLVM_CLANG_ANALYSIS_FLOW_SENSITIVE_TESTING_SUPPORT_H_
153dd7877bSStanislav Gatev
16632de855SWei Yi Tee #include <functional>
17632de855SWei Yi Tee #include <memory>
18a1580d7bSKazu Hirata #include <optional>
19632de855SWei Yi Tee #include <ostream>
20632de855SWei Yi Tee #include <string>
21632de855SWei Yi Tee #include <utility>
22632de855SWei Yi Tee #include <vector>
23632de855SWei Yi Tee
243dd7877bSStanislav Gatev #include "clang/AST/ASTContext.h"
253dd7877bSStanislav Gatev #include "clang/AST/Decl.h"
263dd7877bSStanislav Gatev #include "clang/AST/Stmt.h"
273dd7877bSStanislav Gatev #include "clang/ASTMatchers/ASTMatchFinder.h"
283dd7877bSStanislav Gatev #include "clang/ASTMatchers/ASTMatchers.h"
293dd7877bSStanislav Gatev #include "clang/ASTMatchers/ASTMatchersInternal.h"
303dd7877bSStanislav Gatev #include "clang/Analysis/CFG.h"
3159ff3adcSmartinboehme #include "clang/Analysis/FlowSensitive/AdornedCFG.h"
323dd7877bSStanislav Gatev #include "clang/Analysis/FlowSensitive/DataflowAnalysis.h"
33264976d9SYitzhak Mandelbaum #include "clang/Analysis/FlowSensitive/DataflowAnalysisContext.h"
343dd7877bSStanislav Gatev #include "clang/Analysis/FlowSensitive/DataflowEnvironment.h"
3582d50fefSDani Ferreira Franco Moura #include "clang/Analysis/FlowSensitive/MatchSwitch.h"
36f3dd8f10SYitzhak Mandelbaum #include "clang/Analysis/FlowSensitive/NoopLattice.h"
373dd7877bSStanislav Gatev #include "clang/Analysis/FlowSensitive/WatchedLiteralsSolver.h"
383dd7877bSStanislav Gatev #include "clang/Basic/LLVM.h"
393dd7877bSStanislav Gatev #include "clang/Serialization/PCHContainerOperations.h"
403dd7877bSStanislav Gatev #include "clang/Tooling/ArgumentsAdjusters.h"
413dd7877bSStanislav Gatev #include "clang/Tooling/Tooling.h"
423dd7877bSStanislav Gatev #include "llvm/ADT/ArrayRef.h"
433dd7877bSStanislav Gatev #include "llvm/ADT/DenseMap.h"
448dd14c42SWei Yi Tee #include "llvm/ADT/StringMap.h"
453dd7877bSStanislav Gatev #include "llvm/ADT/StringRef.h"
46fc9821a8SSam McCall #include "llvm/Support/Allocator.h"
473dd7877bSStanislav Gatev #include "llvm/Support/Errc.h"
483dd7877bSStanislav Gatev #include "llvm/Support/Error.h"
493432f4bfSJordan Rupprecht #include "llvm/Testing/Annotations/Annotations.h"
503dd7877bSStanislav Gatev
513dd7877bSStanislav Gatev namespace clang {
523dd7877bSStanislav Gatev namespace dataflow {
533dd7877bSStanislav Gatev
543dd7877bSStanislav Gatev // Requires a `<<` operator for the `Lattice` type.
553dd7877bSStanislav Gatev // FIXME: move to a non-test utility library.
563dd7877bSStanislav Gatev template <typename Lattice>
573dd7877bSStanislav Gatev std::ostream &operator<<(std::ostream &OS,
583dd7877bSStanislav Gatev const DataflowAnalysisState<Lattice> &S) {
593dd7877bSStanislav Gatev // FIXME: add printing support for the environment.
603dd7877bSStanislav Gatev return OS << "{lattice=" << S.Lattice << ", environment=...}";
613dd7877bSStanislav Gatev }
623dd7877bSStanislav Gatev
633dd7877bSStanislav Gatev namespace test {
643dd7877bSStanislav Gatev
65f3dd8f10SYitzhak Mandelbaum // Caps the number of block visits in any individual analysis. Given that test
66f3dd8f10SYitzhak Mandelbaum // code is typically quite small, we set a low number to help catch any problems
67f3dd8f10SYitzhak Mandelbaum // early. But, the choice is arbitrary.
68f3dd8f10SYitzhak Mandelbaum constexpr std::int32_t MaxBlockVisitsInAnalysis = 2'000;
69f3dd8f10SYitzhak Mandelbaum
7014757d5bSWei Yi Tee /// Returns the environment at the program point marked with `Annotation` from
7114757d5bSWei Yi Tee /// the mapping of annotated program points to analysis state.
7214757d5bSWei Yi Tee ///
7314757d5bSWei Yi Tee /// Requirements:
7414757d5bSWei Yi Tee ///
7514757d5bSWei Yi Tee /// `Annotation` must be present as a key in `AnnotationStates`.
7614757d5bSWei Yi Tee template <typename LatticeT>
getEnvironmentAtAnnotation(const llvm::StringMap<DataflowAnalysisState<LatticeT>> & AnnotationStates,llvm::StringRef Annotation)7714757d5bSWei Yi Tee const Environment &getEnvironmentAtAnnotation(
7814757d5bSWei Yi Tee const llvm::StringMap<DataflowAnalysisState<LatticeT>> &AnnotationStates,
7914757d5bSWei Yi Tee llvm::StringRef Annotation) {
8014757d5bSWei Yi Tee auto It = AnnotationStates.find(Annotation);
8114757d5bSWei Yi Tee assert(It != AnnotationStates.end());
8214757d5bSWei Yi Tee return It->getValue().Env;
8314757d5bSWei Yi Tee }
8414757d5bSWei Yi Tee
85db898d43SWei Yi Tee /// Contains data structures required and produced by a dataflow analysis run.
86db898d43SWei Yi Tee struct AnalysisOutputs {
87db898d43SWei Yi Tee /// Input code that is analyzed. Points within the code may be marked with
88db898d43SWei Yi Tee /// annotations to facilitate testing.
89db898d43SWei Yi Tee ///
90db898d43SWei Yi Tee /// Example:
91db898d43SWei Yi Tee /// void target(int *x) {
92db898d43SWei Yi Tee /// *x; // [[p]]
93db898d43SWei Yi Tee /// }
94db898d43SWei Yi Tee /// From the annotation `p`, the line number and analysis state immediately
95db898d43SWei Yi Tee /// after the statement `*x` can be retrieved and verified.
96db898d43SWei Yi Tee llvm::Annotations Code;
97db898d43SWei Yi Tee /// AST context generated from `Code`.
98db898d43SWei Yi Tee ASTContext &ASTCtx;
99db898d43SWei Yi Tee /// The function whose body is analyzed.
100db898d43SWei Yi Tee const FunctionDecl *Target;
101db898d43SWei Yi Tee /// Contains the control flow graph built from the body of the `Target`
102db898d43SWei Yi Tee /// function and is analyzed.
10359ff3adcSmartinboehme const AdornedCFG &ACFG;
104db898d43SWei Yi Tee /// The analysis to be run.
105db898d43SWei Yi Tee TypeErasedDataflowAnalysis &Analysis;
106db898d43SWei Yi Tee /// Initial state to start the analysis.
107db898d43SWei Yi Tee const Environment &InitEnv;
108db898d43SWei Yi Tee // Stores the state of a CFG block if it has been evaluated by the analysis.
109db898d43SWei Yi Tee // The indices correspond to the block IDs.
1106ad0788cSKazu Hirata llvm::ArrayRef<std::optional<TypeErasedDataflowAnalysisState>> BlockStates;
111db898d43SWei Yi Tee };
112db898d43SWei Yi Tee
113*cfd20214Smartinboehme /// A callback to be called with the state before or after visiting a CFG
114*cfd20214Smartinboehme /// element.
115*cfd20214Smartinboehme /// This differs from `DiagnosisCallback` in that the return type is void.
116*cfd20214Smartinboehme template <typename AnalysisT>
117*cfd20214Smartinboehme using DiagnosisCallbackForTesting = std::function<void(
118*cfd20214Smartinboehme ASTContext &, const CFGElement &,
119*cfd20214Smartinboehme const TransferStateForDiagnostics<typename AnalysisT::Lattice> &)>;
120*cfd20214Smartinboehme
121*cfd20214Smartinboehme /// A pair of callbacks to be called with the state before and after visiting a
122*cfd20214Smartinboehme /// CFG element.
123*cfd20214Smartinboehme /// Either or both of the callbacks may be null.
124*cfd20214Smartinboehme template <typename AnalysisT> struct DiagnosisCallbacksForTesting {
125*cfd20214Smartinboehme DiagnosisCallbackForTesting<AnalysisT> Before;
126*cfd20214Smartinboehme DiagnosisCallbackForTesting<AnalysisT> After;
127*cfd20214Smartinboehme };
128*cfd20214Smartinboehme
129db898d43SWei Yi Tee /// Arguments for building the dataflow analysis.
130db898d43SWei Yi Tee template <typename AnalysisT> struct AnalysisInputs {
131db898d43SWei Yi Tee /// Required fields are set in constructor.
132db898d43SWei Yi Tee AnalysisInputs(
133db898d43SWei Yi Tee llvm::StringRef CodeArg,
134db898d43SWei Yi Tee ast_matchers::internal::Matcher<FunctionDecl> TargetFuncMatcherArg,
135db898d43SWei Yi Tee std::function<AnalysisT(ASTContext &, Environment &)> MakeAnalysisArg)
136db898d43SWei Yi Tee : Code(CodeArg), TargetFuncMatcher(std::move(TargetFuncMatcherArg)),
137db898d43SWei Yi Tee MakeAnalysis(std::move(MakeAnalysisArg)) {}
138db898d43SWei Yi Tee
139db898d43SWei Yi Tee /// Optional fields can be set with methods of the form `withFieldName(...)`.
140db898d43SWei Yi Tee AnalysisInputs<AnalysisT> &&
1415a4aece7SWei Yi Tee withSetupTest(std::function<llvm::Error(AnalysisOutputs &)> Arg) && {
1425a4aece7SWei Yi Tee SetupTest = std::move(Arg);
1435a4aece7SWei Yi Tee return std::move(*this);
1445a4aece7SWei Yi Tee }
145*cfd20214Smartinboehme AnalysisInputs<AnalysisT> &&
146*cfd20214Smartinboehme withDiagnosisCallbacks(DiagnosisCallbacksForTesting<AnalysisT> Arg) && {
147*cfd20214Smartinboehme Callbacks = std::move(Arg);
148*cfd20214Smartinboehme return std::move(*this);
149*cfd20214Smartinboehme }
150*cfd20214Smartinboehme /// Provided for backwards compatibility. New callers should use
151*cfd20214Smartinboehme /// `withDiagnosisCallbacks()`.
152*cfd20214Smartinboehme AnalysisInputs<AnalysisT> &&
153*cfd20214Smartinboehme withPostVisitCFG(DiagnosisCallbackForTesting<AnalysisT> Arg) && {
154*cfd20214Smartinboehme Callbacks.After = std::move(Arg);
15582d50fefSDani Ferreira Franco Moura return std::move(*this);
15682d50fefSDani Ferreira Franco Moura }
157db898d43SWei Yi Tee AnalysisInputs<AnalysisT> &&withASTBuildArgs(ArrayRef<std::string> Arg) && {
158db898d43SWei Yi Tee ASTBuildArgs = std::move(Arg);
159db898d43SWei Yi Tee return std::move(*this);
160db898d43SWei Yi Tee }
161db898d43SWei Yi Tee AnalysisInputs<AnalysisT> &&
162db898d43SWei Yi Tee withASTBuildVirtualMappedFiles(tooling::FileContentMappings Arg) && {
163db898d43SWei Yi Tee ASTBuildVirtualMappedFiles = std::move(Arg);
164db898d43SWei Yi Tee return std::move(*this);
165db898d43SWei Yi Tee }
16601ccf7b3SYitzhak Mandelbaum AnalysisInputs<AnalysisT> &&
167264976d9SYitzhak Mandelbaum withBuiltinOptions(DataflowAnalysisContext::Options Options) && {
168264976d9SYitzhak Mandelbaum BuiltinOptions = std::move(Options);
16901ccf7b3SYitzhak Mandelbaum return std::move(*this);
17001ccf7b3SYitzhak Mandelbaum }
1718bc13c88SMartin Braenne AnalysisInputs<AnalysisT> &&
1728bc13c88SMartin Braenne withSolverFactory(std::function<std::unique_ptr<Solver>()> Factory) && {
1738bc13c88SMartin Braenne assert(Factory);
1748bc13c88SMartin Braenne SolverFactory = std::move(Factory);
1758bc13c88SMartin Braenne return std::move(*this);
1768bc13c88SMartin Braenne }
177db898d43SWei Yi Tee
178db898d43SWei Yi Tee /// Required. Input code that is analyzed.
179db898d43SWei Yi Tee llvm::StringRef Code;
180c8b31da1SDmitri Gribenko /// Required. All functions that match this matcher are analyzed.
181db898d43SWei Yi Tee ast_matchers::internal::Matcher<FunctionDecl> TargetFuncMatcher;
182db898d43SWei Yi Tee /// Required. The analysis to be run is constructed with this function that
183db898d43SWei Yi Tee /// takes as argument the AST generated from the code being analyzed and the
184db898d43SWei Yi Tee /// initial state from which the analysis starts with.
185db898d43SWei Yi Tee std::function<AnalysisT(ASTContext &, Environment &)> MakeAnalysis;
1865a4aece7SWei Yi Tee /// Optional. If provided, this function is executed immediately before
1875a4aece7SWei Yi Tee /// running the dataflow analysis to allow for additional setup. All fields in
1885a4aece7SWei Yi Tee /// the `AnalysisOutputs` argument will be initialized except for the
1895a4aece7SWei Yi Tee /// `BlockStates` field which is only computed later during the analysis.
1905a4aece7SWei Yi Tee std::function<llvm::Error(AnalysisOutputs &)> SetupTest = nullptr;
191*cfd20214Smartinboehme /// Callbacks to run on each CFG element after the analysis has been run.
192*cfd20214Smartinboehme DiagnosisCallbacksForTesting<AnalysisT> Callbacks;
193db898d43SWei Yi Tee
194db898d43SWei Yi Tee /// Optional. Options for building the AST context.
195db898d43SWei Yi Tee ArrayRef<std::string> ASTBuildArgs = {};
196db898d43SWei Yi Tee /// Optional. Options for building the AST context.
197db898d43SWei Yi Tee tooling::FileContentMappings ASTBuildVirtualMappedFiles = {};
198264976d9SYitzhak Mandelbaum /// Configuration options for the built-in model.
199264976d9SYitzhak Mandelbaum DataflowAnalysisContext::Options BuiltinOptions;
2008bc13c88SMartin Braenne /// SAT solver factory.
2018bc13c88SMartin Braenne std::function<std::unique_ptr<Solver>()> SolverFactory = [] {
2028bc13c88SMartin Braenne return std::make_unique<WatchedLiteralsSolver>();
2038bc13c88SMartin Braenne };
204db898d43SWei Yi Tee };
205db898d43SWei Yi Tee
206db898d43SWei Yi Tee /// Returns assertions based on annotations that are present after statements in
207db898d43SWei Yi Tee /// `AnnotatedCode`.
2083dd7877bSStanislav Gatev llvm::Expected<llvm::DenseMap<const Stmt *, std::string>>
2093dd7877bSStanislav Gatev buildStatementToAnnotationMapping(const FunctionDecl *Func,
2103dd7877bSStanislav Gatev llvm::Annotations AnnotatedCode);
2113dd7877bSStanislav Gatev
212c8b31da1SDmitri Gribenko /// Returns line numbers and content of the annotations in `AnnotatedCode`
213c8b31da1SDmitri Gribenko /// within the token range `BoundingRange`.
214c8b31da1SDmitri Gribenko llvm::DenseMap<unsigned, std::string> buildLineToAnnotationMapping(
215c8b31da1SDmitri Gribenko const SourceManager &SM, const LangOptions &LangOpts,
216c8b31da1SDmitri Gribenko SourceRange BoundingRange, llvm::Annotations AnnotatedCode);
217db898d43SWei Yi Tee
218*cfd20214Smartinboehme /// Runs dataflow specified from `AI.MakeAnalysis` and `AI.Callbacks` on all
219c8b31da1SDmitri Gribenko /// functions that match `AI.TargetFuncMatcher` in `AI.Code`. Given the
220c8b31da1SDmitri Gribenko /// analysis outputs, `VerifyResults` checks that the results from the analysis
221c8b31da1SDmitri Gribenko /// are correct.
2229e842dd4SWei Yi Tee ///
2239e842dd4SWei Yi Tee /// Requirements:
2249e842dd4SWei Yi Tee ///
2259e842dd4SWei Yi Tee /// `AnalysisT` contains a type `Lattice`.
226db898d43SWei Yi Tee ///
227db898d43SWei Yi Tee /// `Code`, `TargetFuncMatcher` and `MakeAnalysis` must be provided in `AI`.
228db898d43SWei Yi Tee ///
229db898d43SWei Yi Tee /// `VerifyResults` must be provided.
2303dd7877bSStanislav Gatev template <typename AnalysisT>
2315a4aece7SWei Yi Tee llvm::Error
2325a4aece7SWei Yi Tee checkDataflow(AnalysisInputs<AnalysisT> AI,
2335a4aece7SWei Yi Tee std::function<void(const AnalysisOutputs &)> VerifyResults) {
234db898d43SWei Yi Tee // Build AST context from code.
235db898d43SWei Yi Tee llvm::Annotations AnnotatedCode(AI.Code);
2363dd7877bSStanislav Gatev auto Unit = tooling::buildASTFromCodeWithArgs(
237db898d43SWei Yi Tee AnnotatedCode.code(), AI.ASTBuildArgs, "input.cc", "clang-dataflow-test",
2383dd7877bSStanislav Gatev std::make_shared<PCHContainerOperations>(),
239db898d43SWei Yi Tee tooling::getClangStripDependencyFileAdjuster(),
240db898d43SWei Yi Tee AI.ASTBuildVirtualMappedFiles);
2413dd7877bSStanislav Gatev auto &Context = Unit->getASTContext();
2423dd7877bSStanislav Gatev
2433dd7877bSStanislav Gatev if (Context.getDiagnostics().getClient()->getNumErrors() != 0) {
2443dd7877bSStanislav Gatev return llvm::make_error<llvm::StringError>(
2453dd7877bSStanislav Gatev llvm::errc::invalid_argument, "Source file has syntax or type errors, "
2463dd7877bSStanislav Gatev "they were printed to the test log");
2473dd7877bSStanislav Gatev }
2483dd7877bSStanislav Gatev
249*cfd20214Smartinboehme CFGEltCallbacksTypeErased PostAnalysisCallbacks;
250*cfd20214Smartinboehme if (AI.Callbacks.Before) {
251*cfd20214Smartinboehme PostAnalysisCallbacks.Before =
252*cfd20214Smartinboehme [&AI, &Context](const CFGElement &Element,
25358fe7f96SSam Estep const TypeErasedDataflowAnalysisState &State) {
254*cfd20214Smartinboehme AI.Callbacks.Before(
255*cfd20214Smartinboehme Context, Element,
256*cfd20214Smartinboehme TransferStateForDiagnostics<typename AnalysisT::Lattice>(
257*cfd20214Smartinboehme llvm::any_cast<const typename AnalysisT::Lattice &>(
258*cfd20214Smartinboehme State.Lattice.Value),
259*cfd20214Smartinboehme State.Env));
260*cfd20214Smartinboehme };
261*cfd20214Smartinboehme }
262*cfd20214Smartinboehme if (AI.Callbacks.After) {
263*cfd20214Smartinboehme PostAnalysisCallbacks.After =
264*cfd20214Smartinboehme [&AI, &Context](const CFGElement &Element,
265*cfd20214Smartinboehme const TypeErasedDataflowAnalysisState &State) {
266*cfd20214Smartinboehme AI.Callbacks.After(
267*cfd20214Smartinboehme Context, Element,
26882d50fefSDani Ferreira Franco Moura TransferStateForDiagnostics<typename AnalysisT::Lattice>(
26982d50fefSDani Ferreira Franco Moura llvm::any_cast<const typename AnalysisT::Lattice &>(
27082d50fefSDani Ferreira Franco Moura State.Lattice.Value),
27182d50fefSDani Ferreira Franco Moura State.Env));
27258fe7f96SSam Estep };
27358fe7f96SSam Estep }
27458fe7f96SSam Estep
275967604a0Smartinboehme SmallVector<ast_matchers::BoundNodes, 1> MatchResult = ast_matchers::match(
276967604a0Smartinboehme ast_matchers::functionDecl(ast_matchers::hasBody(ast_matchers::stmt()),
277c8b31da1SDmitri Gribenko AI.TargetFuncMatcher)
278c8b31da1SDmitri Gribenko .bind("target"),
279967604a0Smartinboehme Context);
280967604a0Smartinboehme if (MatchResult.empty())
281967604a0Smartinboehme return llvm::createStringError(llvm::inconvertibleErrorCode(),
282967604a0Smartinboehme "didn't find any matching target functions");
283967604a0Smartinboehme for (const ast_matchers::BoundNodes &BN : MatchResult) {
284c8b31da1SDmitri Gribenko // Get the AST node of the target function.
285c8b31da1SDmitri Gribenko const FunctionDecl *Target = BN.getNodeAs<FunctionDecl>("target");
286c8b31da1SDmitri Gribenko if (Target == nullptr)
287c8b31da1SDmitri Gribenko return llvm::make_error<llvm::StringError>(
288c8b31da1SDmitri Gribenko llvm::errc::invalid_argument, "Could not find the target function.");
289c8b31da1SDmitri Gribenko
290c8b31da1SDmitri Gribenko // Build the control flow graph for the target function.
29159ff3adcSmartinboehme auto MaybeACFG = AdornedCFG::build(*Target);
29259ff3adcSmartinboehme if (!MaybeACFG)
29359ff3adcSmartinboehme return MaybeACFG.takeError();
29459ff3adcSmartinboehme auto &ACFG = *MaybeACFG;
295c8b31da1SDmitri Gribenko
296c8b31da1SDmitri Gribenko // Initialize states for running dataflow analysis.
2978bc13c88SMartin Braenne DataflowAnalysisContext DACtx(AI.SolverFactory(),
298c8b31da1SDmitri Gribenko {/*Opts=*/AI.BuiltinOptions});
299c8b31da1SDmitri Gribenko Environment InitEnv(DACtx, *Target);
300c8b31da1SDmitri Gribenko auto Analysis = AI.MakeAnalysis(Context, InitEnv);
301c8b31da1SDmitri Gribenko
30259ff3adcSmartinboehme AnalysisOutputs AO{AnnotatedCode, Context, Target, ACFG,
3035a4aece7SWei Yi Tee Analysis, InitEnv, {}};
304c8b31da1SDmitri Gribenko
305c8b31da1SDmitri Gribenko // Additional test setup.
3065a4aece7SWei Yi Tee if (AI.SetupTest) {
307c8b31da1SDmitri Gribenko if (auto Error = AI.SetupTest(AO)) return Error;
3085a4aece7SWei Yi Tee }
3095a4aece7SWei Yi Tee
3105a4aece7SWei Yi Tee // If successful, the dataflow analysis returns a mapping from block IDs to
3115a4aece7SWei Yi Tee // the post-analysis states for the CFG blocks that have been evaluated.
3125c9013e2SKazu Hirata llvm::Expected<std::vector<std::optional<TypeErasedDataflowAnalysisState>>>
313f3dd8f10SYitzhak Mandelbaum MaybeBlockStates =
31459ff3adcSmartinboehme runTypeErasedDataflowAnalysis(ACFG, Analysis, InitEnv,
315*cfd20214Smartinboehme PostAnalysisCallbacks,
316f3dd8f10SYitzhak Mandelbaum MaxBlockVisitsInAnalysis);
317c8b31da1SDmitri Gribenko if (!MaybeBlockStates) return MaybeBlockStates.takeError();
3185a4aece7SWei Yi Tee AO.BlockStates = *MaybeBlockStates;
3193dd7877bSStanislav Gatev
320db898d43SWei Yi Tee // Verify dataflow analysis outputs.
3215a4aece7SWei Yi Tee VerifyResults(AO);
322c8b31da1SDmitri Gribenko }
323c8b31da1SDmitri Gribenko
3245a4aece7SWei Yi Tee return llvm::Error::success();
3253dd7877bSStanislav Gatev }
3263dd7877bSStanislav Gatev
327c8b31da1SDmitri Gribenko /// Runs dataflow specified from `AI.MakeAnalysis` and `AI.PostVisitCFG` on all
328c8b31da1SDmitri Gribenko /// functions that match `AI.TargetFuncMatcher` in `AI.Code`. Given the
329c8b31da1SDmitri Gribenko /// annotation line numbers and analysis outputs, `VerifyResults` checks that
330c8b31da1SDmitri Gribenko /// the results from the analysis are correct.
331db898d43SWei Yi Tee ///
332db898d43SWei Yi Tee /// Requirements:
333db898d43SWei Yi Tee ///
334db898d43SWei Yi Tee /// `AnalysisT` contains a type `Lattice`.
335db898d43SWei Yi Tee ///
336db898d43SWei Yi Tee /// `Code`, `TargetFuncMatcher` and `MakeAnalysis` must be provided in `AI`.
337db898d43SWei Yi Tee ///
338db898d43SWei Yi Tee /// `VerifyResults` must be provided.
339db898d43SWei Yi Tee template <typename AnalysisT>
340db898d43SWei Yi Tee llvm::Error
341db898d43SWei Yi Tee checkDataflow(AnalysisInputs<AnalysisT> AI,
342db898d43SWei Yi Tee std::function<void(const llvm::DenseMap<unsigned, std::string> &,
343db898d43SWei Yi Tee const AnalysisOutputs &)>
344db898d43SWei Yi Tee VerifyResults) {
345db898d43SWei Yi Tee return checkDataflow<AnalysisT>(
3465a4aece7SWei Yi Tee std::move(AI), [&VerifyResults](const AnalysisOutputs &AO) {
347c8b31da1SDmitri Gribenko auto AnnotationLinesAndContent = buildLineToAnnotationMapping(
348c8b31da1SDmitri Gribenko AO.ASTCtx.getSourceManager(), AO.ASTCtx.getLangOpts(),
349c8b31da1SDmitri Gribenko AO.Target->getSourceRange(), AO.Code);
350db898d43SWei Yi Tee VerifyResults(AnnotationLinesAndContent, AO);
351db898d43SWei Yi Tee });
352db898d43SWei Yi Tee }
353db898d43SWei Yi Tee
354c8b31da1SDmitri Gribenko /// Runs dataflow specified from `AI.MakeAnalysis` and `AI.PostVisitCFG` on all
355c8b31da1SDmitri Gribenko /// functions that match `AI.TargetFuncMatcher` in `AI.Code`. Given the state
356c8b31da1SDmitri Gribenko /// computed at each annotated statement and analysis outputs, `VerifyResults`
357c8b31da1SDmitri Gribenko /// checks that the results from the analysis are correct.
358db898d43SWei Yi Tee ///
359db898d43SWei Yi Tee /// Requirements:
360db898d43SWei Yi Tee ///
361db898d43SWei Yi Tee /// `AnalysisT` contains a type `Lattice`.
362db898d43SWei Yi Tee ///
363db898d43SWei Yi Tee /// `Code`, `TargetFuncMatcher` and `MakeAnalysis` must be provided in `AI`.
364db898d43SWei Yi Tee ///
365db898d43SWei Yi Tee /// `VerifyResults` must be provided.
366db898d43SWei Yi Tee ///
367db898d43SWei Yi Tee /// Any annotations appearing in `Code` must come after a statement.
368db898d43SWei Yi Tee ///
369db898d43SWei Yi Tee /// There can be at most one annotation attached per statement.
370db898d43SWei Yi Tee ///
371db898d43SWei Yi Tee /// Annotations must not be repeated.
3729e842dd4SWei Yi Tee template <typename AnalysisT>
3738dd14c42SWei Yi Tee llvm::Error
3748dd14c42SWei Yi Tee checkDataflow(AnalysisInputs<AnalysisT> AI,
3758dd14c42SWei Yi Tee std::function<void(const llvm::StringMap<DataflowAnalysisState<
3768dd14c42SWei Yi Tee typename AnalysisT::Lattice>> &,
377db898d43SWei Yi Tee const AnalysisOutputs &)>
378db898d43SWei Yi Tee VerifyResults) {
3795a4aece7SWei Yi Tee // Compute mapping from nodes of annotated statements to the content in the
3805a4aece7SWei Yi Tee // annotation.
3815a4aece7SWei Yi Tee llvm::DenseMap<const Stmt *, std::string> StmtToAnnotations;
3825a4aece7SWei Yi Tee auto SetupTest = [&StmtToAnnotations,
3835a4aece7SWei Yi Tee PrevSetupTest = std::move(AI.SetupTest)](
3845a4aece7SWei Yi Tee AnalysisOutputs &AO) -> llvm::Error {
38580d9ae9cSSamira Bazuzi auto MaybeStmtToAnnotations =
38680d9ae9cSSamira Bazuzi buildStatementToAnnotationMapping(AO.InitEnv.getCurrentFunc(), AO.Code);
3875a4aece7SWei Yi Tee if (!MaybeStmtToAnnotations) {
3885a4aece7SWei Yi Tee return MaybeStmtToAnnotations.takeError();
3899e842dd4SWei Yi Tee }
3905a4aece7SWei Yi Tee StmtToAnnotations = std::move(*MaybeStmtToAnnotations);
3915a4aece7SWei Yi Tee return PrevSetupTest ? PrevSetupTest(AO) : llvm::Error::success();
3925a4aece7SWei Yi Tee };
3935a4aece7SWei Yi Tee
3945a4aece7SWei Yi Tee using StateT = DataflowAnalysisState<typename AnalysisT::Lattice>;
3955a4aece7SWei Yi Tee
3965a4aece7SWei Yi Tee // Save the states computed for program points immediately following annotated
3975a4aece7SWei Yi Tee // statements. The saved states are keyed by the content of the annotation.
3988dd14c42SWei Yi Tee llvm::StringMap<StateT> AnnotationStates;
399*cfd20214Smartinboehme DiagnosisCallbacksForTesting<AnalysisT> Callbacks;
400*cfd20214Smartinboehme Callbacks.Before = std::move(AI.Callbacks.Before);
401*cfd20214Smartinboehme Callbacks.After =
40282d50fefSDani Ferreira Franco Moura [&StmtToAnnotations, &AnnotationStates,
403*cfd20214Smartinboehme PrevCallbackAfter = std::move(AI.Callbacks.After)](
4045a4aece7SWei Yi Tee ASTContext &Ctx, const CFGElement &Elt,
40582d50fefSDani Ferreira Franco Moura const TransferStateForDiagnostics<typename AnalysisT::Lattice>
40682d50fefSDani Ferreira Franco Moura &State) {
407*cfd20214Smartinboehme if (PrevCallbackAfter) {
408*cfd20214Smartinboehme PrevCallbackAfter(Ctx, Elt, State);
4095a4aece7SWei Yi Tee }
4105a4aece7SWei Yi Tee // FIXME: Extend retrieval of state for non statement constructs.
4115a4aece7SWei Yi Tee auto Stmt = Elt.getAs<CFGStmt>();
4125a4aece7SWei Yi Tee if (!Stmt)
4135a4aece7SWei Yi Tee return;
4145a4aece7SWei Yi Tee auto It = StmtToAnnotations.find(Stmt->getStmt());
4155a4aece7SWei Yi Tee if (It == StmtToAnnotations.end())
4165a4aece7SWei Yi Tee return;
41782d50fefSDani Ferreira Franco Moura auto [_, InsertSuccess] = AnnotationStates.insert(
418c2bb6807SSam McCall {It->second, StateT{State.Lattice, State.Env.fork()}});
419bb72d0ddSGabor Marton (void)_;
4208dd14c42SWei Yi Tee (void)InsertSuccess;
4218dd14c42SWei Yi Tee assert(InsertSuccess);
4225a4aece7SWei Yi Tee };
4235a4aece7SWei Yi Tee return checkDataflow<AnalysisT>(
4245a4aece7SWei Yi Tee std::move(AI)
4255a4aece7SWei Yi Tee .withSetupTest(std::move(SetupTest))
426*cfd20214Smartinboehme .withDiagnosisCallbacks(std::move(Callbacks)),
4275a4aece7SWei Yi Tee [&VerifyResults, &AnnotationStates](const AnalysisOutputs &AO) {
428db898d43SWei Yi Tee VerifyResults(AnnotationStates, AO);
429c8b31da1SDmitri Gribenko
430c8b31da1SDmitri Gribenko // `checkDataflow()` can analyze more than one function. Reset the
431c8b31da1SDmitri Gribenko // variables to prepare for analyzing the next function.
432c8b31da1SDmitri Gribenko AnnotationStates.clear();
433db898d43SWei Yi Tee });
4349e842dd4SWei Yi Tee }
4359e842dd4SWei Yi Tee
436f2123af1SMartin Braenne using BuiltinOptions = DataflowAnalysisContext::Options;
437f2123af1SMartin Braenne
43852d06963SStanislav Gatev /// Runs dataflow on function named `TargetFun` in `Code` with a `NoopAnalysis`
43952d06963SStanislav Gatev /// and calls `VerifyResults` to verify the results.
440d0be47c5SMartin Braenne llvm::Error checkDataflowWithNoopAnalysis(
441d0be47c5SMartin Braenne llvm::StringRef Code,
442d0be47c5SMartin Braenne std::function<
443d0be47c5SMartin Braenne void(const llvm::StringMap<DataflowAnalysisState<NoopLattice>> &,
444d0be47c5SMartin Braenne ASTContext &)>
445a1a63d68SMartin Braenne VerifyResults = [](const auto &, auto &) {},
446a1a63d68SMartin Braenne DataflowAnalysisOptions Options = {BuiltinOptions()},
447f2123af1SMartin Braenne LangStandard::Kind Std = LangStandard::lang_cxx17,
448d0be47c5SMartin Braenne llvm::StringRef TargetFun = "target");
449f2123af1SMartin Braenne
45052d06963SStanislav Gatev /// Runs dataflow on function matched by `TargetFuncMatcher` in `Code` with a
45152d06963SStanislav Gatev /// `NoopAnalysis` and calls `VerifyResults` to verify the results.
45252d06963SStanislav Gatev llvm::Error checkDataflowWithNoopAnalysis(
45352d06963SStanislav Gatev llvm::StringRef Code,
45452d06963SStanislav Gatev ast_matchers::internal::Matcher<FunctionDecl> TargetFuncMatcher,
45552d06963SStanislav Gatev std::function<
45652d06963SStanislav Gatev void(const llvm::StringMap<DataflowAnalysisState<NoopLattice>> &,
45752d06963SStanislav Gatev ASTContext &)>
45852d06963SStanislav Gatev VerifyResults = [](const auto &, auto &) {},
45952d06963SStanislav Gatev DataflowAnalysisOptions Options = {BuiltinOptions()},
46071f2ec2dSmartinboehme LangStandard::Kind Std = LangStandard::lang_cxx17,
46171f2ec2dSmartinboehme std::function<llvm::StringMap<QualType>(QualType)> SyntheticFieldCallback =
46271f2ec2dSmartinboehme {});
46352d06963SStanislav Gatev
4643dd7877bSStanislav Gatev /// Returns the `ValueDecl` for the given identifier.
465128780b0Smartinboehme /// The returned pointer is guaranteed to be non-null; the function asserts if
466128780b0Smartinboehme /// no `ValueDecl` with the given name is found.
4673dd7877bSStanislav Gatev ///
4683dd7877bSStanislav Gatev /// Requirements:
4693dd7877bSStanislav Gatev ///
4703dd7877bSStanislav Gatev /// `Name` must be unique in `ASTCtx`.
4713dd7877bSStanislav Gatev const ValueDecl *findValueDecl(ASTContext &ASTCtx, llvm::StringRef Name);
4723dd7877bSStanislav Gatev
473d04b1989SMartin Braenne /// Returns the `IndirectFieldDecl` for the given identifier.
474d04b1989SMartin Braenne ///
475d04b1989SMartin Braenne /// Requirements:
476d04b1989SMartin Braenne ///
477d04b1989SMartin Braenne /// `Name` must be unique in `ASTCtx`.
478d04b1989SMartin Braenne const IndirectFieldDecl *findIndirectFieldDecl(ASTContext &ASTCtx,
479d04b1989SMartin Braenne llvm::StringRef Name);
480d04b1989SMartin Braenne
481f2123af1SMartin Braenne /// Returns the storage location (of type `LocT`) for the given identifier.
482f2123af1SMartin Braenne /// `LocT` must be a subclass of `StorageLocation` and must be of the
483f2123af1SMartin Braenne /// appropriate type.
484f2123af1SMartin Braenne ///
485f2123af1SMartin Braenne /// Requirements:
486f2123af1SMartin Braenne ///
487f2123af1SMartin Braenne /// `Name` must be unique in `ASTCtx`.
4889ba6961cSmartinboehme template <class LocT = StorageLocation>
489f2123af1SMartin Braenne LocT &getLocForDecl(ASTContext &ASTCtx, const Environment &Env,
490f2123af1SMartin Braenne llvm::StringRef Name) {
491f2123af1SMartin Braenne const ValueDecl *VD = findValueDecl(ASTCtx, Name);
492f2123af1SMartin Braenne assert(VD != nullptr);
493f2123af1SMartin Braenne return *cast<LocT>(Env.getStorageLocation(*VD));
494f2123af1SMartin Braenne }
495f2123af1SMartin Braenne
4965acd29ebSMartin Braenne /// Returns the value (of type `ValueT`) for the given identifier.
4975acd29ebSMartin Braenne /// `ValueT` must be a subclass of `Value` and must be of the appropriate type.
4985acd29ebSMartin Braenne ///
4995acd29ebSMartin Braenne /// Requirements:
5005acd29ebSMartin Braenne ///
5015acd29ebSMartin Braenne /// `Name` must be unique in `ASTCtx`.
5029ba6961cSmartinboehme template <class ValueT = Value>
5035acd29ebSMartin Braenne ValueT &getValueForDecl(ASTContext &ASTCtx, const Environment &Env,
5045acd29ebSMartin Braenne llvm::StringRef Name) {
5055acd29ebSMartin Braenne const ValueDecl *VD = findValueDecl(ASTCtx, Name);
5065acd29ebSMartin Braenne assert(VD != nullptr);
5070c852dc8SMartin Braenne return *cast<ValueT>(Env.getValue(*VD));
5085acd29ebSMartin Braenne }
5095acd29ebSMartin Braenne
510128780b0Smartinboehme /// Returns the storage location for the field called `Name` of `Loc`.
511128780b0Smartinboehme /// Optionally casts the field storage location to `T`.
512128780b0Smartinboehme template <typename T = StorageLocation>
513128780b0Smartinboehme std::enable_if_t<std::is_base_of_v<StorageLocation, T>, T &>
514128780b0Smartinboehme getFieldLoc(const RecordStorageLocation &Loc, llvm::StringRef Name,
515128780b0Smartinboehme ASTContext &ASTCtx) {
516128780b0Smartinboehme return *cast<T>(Loc.getChild(*findValueDecl(ASTCtx, Name)));
517128780b0Smartinboehme }
518128780b0Smartinboehme
5192902ea3dSMartin Braenne /// Returns the value of a `Field` on the record referenced by `Loc.`
5202902ea3dSMartin Braenne /// Returns null if `Loc` is null.
5219ecdbe38SMartin Braenne inline Value *getFieldValue(const RecordStorageLocation *Loc,
5222902ea3dSMartin Braenne const ValueDecl &Field, const Environment &Env) {
5232902ea3dSMartin Braenne if (Loc == nullptr)
5242902ea3dSMartin Braenne return nullptr;
52544f98d01SMartin Braenne StorageLocation *FieldLoc = Loc->getChild(Field);
52644f98d01SMartin Braenne if (FieldLoc == nullptr)
52744f98d01SMartin Braenne return nullptr;
52844f98d01SMartin Braenne return Env.getValue(*FieldLoc);
5292902ea3dSMartin Braenne }
5302902ea3dSMartin Braenne
531128780b0Smartinboehme /// Returns the value of a `Field` on the record referenced by `Loc.`
532128780b0Smartinboehme /// Returns null if `Loc` is null.
533128780b0Smartinboehme inline Value *getFieldValue(const RecordStorageLocation *Loc,
534128780b0Smartinboehme llvm::StringRef Name, ASTContext &ASTCtx,
535128780b0Smartinboehme const Environment &Env) {
536128780b0Smartinboehme return getFieldValue(Loc, *findValueDecl(ASTCtx, Name), Env);
537128780b0Smartinboehme }
538128780b0Smartinboehme
539632de855SWei Yi Tee /// Creates and owns constraints which are boolean values.
540632de855SWei Yi Tee class ConstraintContext {
541fc9821a8SSam McCall unsigned NextAtom = 0;
542fc9821a8SSam McCall llvm::BumpPtrAllocator A;
543fc9821a8SSam McCall
544fc9821a8SSam McCall const Formula *make(Formula::Kind K,
545fc9821a8SSam McCall llvm::ArrayRef<const Formula *> Operands) {
546fc9821a8SSam McCall return &Formula::create(A, K, Operands);
547fc9821a8SSam McCall }
548fc9821a8SSam McCall
549632de855SWei Yi Tee public:
550fc9821a8SSam McCall // Returns a reference to a fresh atomic variable.
551fc9821a8SSam McCall const Formula *atom() {
552fc9821a8SSam McCall return &Formula::create(A, Formula::AtomRef, {}, NextAtom++);
553632de855SWei Yi Tee }
554632de855SWei Yi Tee
5557338eb56SSam McCall // Returns a reference to a literal boolean value.
5567338eb56SSam McCall const Formula *literal(bool B) {
5577338eb56SSam McCall return &Formula::create(A, Formula::Literal, {}, B);
5587338eb56SSam McCall }
5597338eb56SSam McCall
560fc9821a8SSam McCall // Creates a boolean conjunction.
561fc9821a8SSam McCall const Formula *conj(const Formula *LHS, const Formula *RHS) {
562fc9821a8SSam McCall return make(Formula::And, {LHS, RHS});
56371579569SSam McCall }
56471579569SSam McCall
565fc9821a8SSam McCall // Creates a boolean disjunction.
566fc9821a8SSam McCall const Formula *disj(const Formula *LHS, const Formula *RHS) {
567fc9821a8SSam McCall return make(Formula::Or, {LHS, RHS});
56839b9d4f1SYitzhak Mandelbaum }
56939b9d4f1SYitzhak Mandelbaum
570fc9821a8SSam McCall // Creates a boolean negation.
571fc9821a8SSam McCall const Formula *neg(const Formula *Operand) {
572fc9821a8SSam McCall return make(Formula::Not, {Operand});
573632de855SWei Yi Tee }
574632de855SWei Yi Tee
575fc9821a8SSam McCall // Creates a boolean implication.
576fc9821a8SSam McCall const Formula *impl(const Formula *LHS, const Formula *RHS) {
577fc9821a8SSam McCall return make(Formula::Implies, {LHS, RHS});
578632de855SWei Yi Tee }
579632de855SWei Yi Tee
580fc9821a8SSam McCall // Creates a boolean biconditional.
581fc9821a8SSam McCall const Formula *iff(const Formula *LHS, const Formula *RHS) {
582fc9821a8SSam McCall return make(Formula::Equal, {LHS, RHS});
583632de855SWei Yi Tee }
584632de855SWei Yi Tee };
585632de855SWei Yi Tee
586bbd61d80Smartinboehme /// Parses a list of formulas, separated by newlines, and returns them.
587bbd61d80Smartinboehme /// On parse errors, calls `ADD_FAILURE()` to fail the current test.
588bbd61d80Smartinboehme std::vector<const Formula *> parseFormulas(Arena &A, StringRef Lines);
589bbd61d80Smartinboehme
5903dd7877bSStanislav Gatev } // namespace test
5913dd7877bSStanislav Gatev } // namespace dataflow
5923dd7877bSStanislav Gatev } // namespace clang
5933dd7877bSStanislav Gatev
5943dd7877bSStanislav Gatev #endif // LLVM_CLANG_ANALYSIS_FLOW_SENSITIVE_TESTING_SUPPORT_H_
595