diff --git a/clang/include/clang/Analysis/FlowSensitive/DataflowAnalysis.h b/clang/include/clang/Analysis/FlowSensitive/DataflowAnalysis.h --- a/clang/include/clang/Analysis/FlowSensitive/DataflowAnalysis.h +++ b/clang/include/clang/Analysis/FlowSensitive/DataflowAnalysis.h @@ -25,9 +25,12 @@ #include "clang/Analysis/FlowSensitive/ControlFlowContext.h" #include "clang/Analysis/FlowSensitive/DataflowEnvironment.h" #include "clang/Analysis/FlowSensitive/DataflowLattice.h" +#include "clang/Analysis/FlowSensitive/MatchSwitch.h" #include "clang/Analysis/FlowSensitive/TypeErasedDataflowAnalysis.h" +#include "clang/Analysis/FlowSensitive/WatchedLiteralsSolver.h" #include "llvm/ADT/Any.h" #include "llvm/ADT/STLExtras.h" +#include "llvm/Support/Errc.h" #include "llvm/Support/Error.h" namespace clang { @@ -238,6 +241,59 @@ return std::move(BlockStates); } +/// Runs a dataflow analysis over the given function and then runs `Diagnoser` +/// over the results. If the analysis is successful, returns a list of +/// diagnostics for `FuncDecl`. Otherwise, returns an error. Currently, errors +/// can occur (at least) because the analysis requires too many iterations over +/// the CFG or the SAT solver times out. +/// +/// The default value of `MaxSATIterations` was chosen based on the following +/// observations: +/// - Non-pathological calls to the solver typically require only a few hundred +/// iterations. +/// - This limit is still low enough to keep runtimes acceptable (on typical +/// machines) in cases where we hit the limit. +template +llvm::Expected> +diagnoseFunction(const FunctionDecl &FuncDecl, ASTContext &ASTCtx, + DiagnoserT &Diagnoser, + std::int64_t MaxSATIterations = 1'000'000'000) { + using ::llvm::Expected; + + Expected Context = ControlFlowContext::build(FuncDecl); + if (!Context) + return Context.takeError(); + + auto Solver = std::make_unique(MaxSATIterations); + const WatchedLiteralsSolver *SolverView = Solver.get(); + DataflowAnalysisContext AnalysisContext(std::move(Solver)); + Environment Env(AnalysisContext, FuncDecl); + AnalysisT Analysis(ASTCtx); + std::vector Diagnostics; + auto BlockToOutputState = runTypeErasedDataflowAnalysis( + *Context, Analysis, Env, + [&ASTCtx, &Diagnoser, + &Diagnostics](const CFGElement &Elt, + const TypeErasedDataflowAnalysisState &State) mutable { + auto EltDiagnostics = + Diagnoser(Elt, ASTCtx, + TransferStateForDiagnostics( + llvm::any_cast( + State.Lattice.Value), + State.Env)); + llvm::move(EltDiagnostics, std::back_inserter(Diagnostics)); + }); + + if (!BlockToOutputState) + return BlockToOutputState.takeError(); + + if (SolverView->reachedLimit()) + return llvm::createStringError(llvm::errc::interrupted, + "SAT solver timed out"); + + return Diagnostics; +} + /// Abstract base class for dataflow "models": reusable analysis components that /// model a particular aspect of program semantics in the `Environment`. For /// example, a model may capture a type and its related functions. diff --git a/clang/include/clang/Analysis/FlowSensitive/MatchSwitch.h b/clang/include/clang/Analysis/FlowSensitive/MatchSwitch.h --- a/clang/include/clang/Analysis/FlowSensitive/MatchSwitch.h +++ b/clang/include/clang/Analysis/FlowSensitive/MatchSwitch.h @@ -48,6 +48,10 @@ }; /// A read-only version of TransferState. +/// +/// FIXME: this type is being used as a general (typed) view type for untyped +/// dataflow analysis state, rather than strictly for transfer-function +/// purposes. Move it (and rename it) to DataflowAnalysis.h. template struct TransferStateForDiagnostics { TransferStateForDiagnostics(const LatticeT &Lattice, const Environment &Env) : Lattice(Lattice), Env(Env) {} diff --git a/clang/include/clang/Analysis/FlowSensitive/NoopAnalysis.h b/clang/include/clang/Analysis/FlowSensitive/NoopAnalysis.h --- a/clang/include/clang/Analysis/FlowSensitive/NoopAnalysis.h +++ b/clang/include/clang/Analysis/FlowSensitive/NoopAnalysis.h @@ -24,6 +24,9 @@ class NoopAnalysis : public DataflowAnalysis { public: + NoopAnalysis(ASTContext &Context) + : DataflowAnalysis(Context) {} + /// Deprecated. Use the `DataflowAnalysisOptions` constructor instead. NoopAnalysis(ASTContext &Context, bool ApplyBuiltinTransfer) : DataflowAnalysis(Context, diff --git a/clang/unittests/Analysis/FlowSensitive/TypeErasedDataflowAnalysisTest.cpp b/clang/unittests/Analysis/FlowSensitive/TypeErasedDataflowAnalysisTest.cpp --- a/clang/unittests/Analysis/FlowSensitive/TypeErasedDataflowAnalysisTest.cpp +++ b/clang/unittests/Analysis/FlowSensitive/TypeErasedDataflowAnalysisTest.cpp @@ -47,6 +47,7 @@ using namespace ast_matchers; using llvm::IsStringMapEntry; using ::testing::DescribeMatcher; +using ::testing::ElementsAre; using ::testing::IsEmpty; using ::testing::NotNull; using ::testing::Test; @@ -84,6 +85,28 @@ EXPECT_TRUE(BlockStates[1].has_value()); } +// Basic test that `diagnoseFunction` calls the Diagnoser function for the +// number of elements expected. +TEST(DataflowAnalysisTest, DiagnoseFunctionDiagnoserCalledOnEachElement) { + std::string Code = R"(void target() { int x = 0; ++x; })"; + std::unique_ptr AST = + tooling::buildASTFromCodeWithArgs(Code, {"-std=c++11"}); + + auto *Func = selectFirst( + "func", match(functionDecl(ast_matchers::hasName("target")).bind("func"), + AST->getASTContext())); + ASSERT_THAT(Func, NotNull()); + + int Count = 0; + auto Diagnoser = [&Count](const CFGElement &, ASTContext &, + const TransferStateForDiagnostics &) { + return std::vector({++Count}); + }; + auto Result = diagnoseFunction(*Func, AST->getASTContext(), + Diagnoser); + EXPECT_THAT_EXPECTED(Result, llvm::HasValue(ElementsAre(1, 2, 3, 4))); +} + struct NonConvergingLattice { int State;