[clang][dataflow] Add convenience function for analysing and `FunctionDecl` and diagnosing it.

[ymandel]

Summary

The convenience function captures running the analysis and then collecting
diagnostics based on a Diagnoser object. This pattern is valuable to
clang-tidy checks which analyze a function at a time, though it could be more
generally useful for analysis clients.

[mboehme]

clang/include/clang/Analysis/FlowSensitive/DataflowAnalysis.h

245

Can you document what the function signature for this should be?

Also, I'm wondering if DiagnoserT even needs to be a template argument. Shouldn't the Diagnostic type be the only "variable" in the type of DiagnoserT?

Or is it that you don't want to force the caller to pass a std::function for Diagnoser? In that case, you could consider `function_ref'.

246–247

260

Does this need to be passed by non-const reference?

std::function::operator() is const, so a const reference should be fine for that. Non-const reference looks like we might be assigning to the reference (which we aren't).

262–266

268–269

Nit: Of the two variables Solver and SolverView, Solver sounds like the more canonical name and the one to "go for". Granted, this is a short function with little potential for confusion, but maybe call the unique pointer OwnedSolver (or similar) and the raw pointer Solver?

This would also eliminate the "view", which to me sounds like there's more going on than just a simple pointer.

274–289

clang/unittests/Analysis/FlowSensitive/TypeErasedDataflowAnalysisTest.cpp

95–98

101–103

I think this gives us a stronger and more explicit check for little extra effort.

[ymandel]

address comments

[ymandel]

address comment

[ymandel]

clang/include/clang/Analysis/FlowSensitive/DataflowAnalysis.h

262–266

Nice! I wasn't aware of moveInto. Sadly, though, it doesn't work because CFC lacks a default constructor.

clang/unittests/Analysis/FlowSensitive/TypeErasedDataflowAnalysisTest.cpp

101–103

Agreed! Great suggestion.

[ymandel]

This broke one of the builds.
https://lab.llvm.org/buildbot/#/builders/121/builds/32939/steps/4/logs/stdio.
Working on a fix now.

• smime.p7s3 KBDownload

clang/include/clang/Analysis/FlowSensitive/DataflowAnalysis.h

 #include <utility>
 #include <vector>
 
 #include "clang/AST/ASTContext.h"
 #include "clang/Analysis/CFG.h"
 #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/ADT/STLFunctionalExtras.h"
+#include "llvm/Support/Errc.h"
 #include "llvm/Support/Error.h"
 
 namespace clang {
 namespace dataflow {
 
 /// Base class template for dataflow analyses built on a single lattice type.
 ///
 /// Requirements:
llvm::transform(
                   llvm::any_cast<typename AnalysisT::Lattice>(
                       std::move(State.Lattice.Value)),
                   std::move(State.Env)};
             });
       });
   return std::move(BlockStates);
 }
 
+/// Runs a dataflow analysis over the given function and then runs `Diagnoser`
+/// over the results. Returns a list of diagnostics for `FuncDecl` or 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 <typename AnalysisT, typename Diagnostic>
+llvm::Expected<std::vector<Diagnostic>> diagnoseFunction(
+    const FunctionDecl &FuncDecl, ASTContext &ASTCtx,
+    llvm::function_ref<std::vector<Diagnostic>(
+        const CFGElement &, ASTContext &,
+        const TransferStateForDiagnostics<typename AnalysisT::Lattice> &)>
+        Diagnoser,
+    std::int64_t MaxSATIterations = 1'000'000'000) {
+  llvm::Expected<ControlFlowContext> Context =
+      ControlFlowContext::build(FuncDecl);
+  if (!Context)
+    return Context.takeError();
+
+  auto OwnedSolver = std::make_unique<WatchedLiteralsSolver>(MaxSATIterations);
+  const WatchedLiteralsSolver *Solver = OwnedSolver.get();
+  DataflowAnalysisContext AnalysisContext(std::move(OwnedSolver));
+  Environment Env(AnalysisContext, FuncDecl);
+  AnalysisT Analysis(ASTCtx);
+  std::vector<Diagnostic> Diagnostics;
+  if (llvm::Error Err =
+          runTypeErasedDataflowAnalysis(
+              *Context, Analysis, Env,
+              [&ASTCtx, &Diagnoser, &Diagnostics](
+                  const CFGElement &Elt,
+                  const TypeErasedDataflowAnalysisState &State) mutable {
+                auto EltDiagnostics = Diagnoser(
+                    Elt, ASTCtx,
+                    TransferStateForDiagnostics<typename AnalysisT::Lattice>(
+                        llvm::any_cast<const typename AnalysisT::Lattice &>(
+                            State.Lattice.Value),
+                        State.Env));
+                llvm::move(EltDiagnostics, std::back_inserter(Diagnostics));
+              })
+              .takeError())
+    return Err;
+
+  if (Solver->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.
 class DataflowModel : public Environment::ValueModel {
 public:
   /// Return value indicates whether the model processed the `Element`.
   virtual bool transfer(const CFGElement &Element, Environment &Env) = 0;
 };
 
 } // namespace dataflow
 } // namespace clang
 
 #endif // LLVM_CLANG_ANALYSIS_FLOWSENSITIVE_DATAFLOWANALYSIS_H

clang/include/clang/Analysis/FlowSensitive/MatchSwitch.h

TransferState(LatticeT &Lattice, Environment &Env)
       : Lattice(Lattice), Env(Env) {}
 
   /// Current lattice element.
   LatticeT &Lattice;
   Environment &Env;
 };
 
 /// 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 <typename LatticeT> struct TransferStateForDiagnostics {
   TransferStateForDiagnostics(const LatticeT &Lattice, const Environment &Env)
       : Lattice(Lattice), Env(Env) {}
 
   /// Current lattice element.
   const LatticeT &Lattice;
   const Environment &Env;
 };

clang/include/clang/Analysis/FlowSensitive/NoopAnalysis.h

 #include "clang/Analysis/FlowSensitive/DataflowEnvironment.h"
 #include "clang/Analysis/FlowSensitive/NoopLattice.h"
 
 namespace clang {
 namespace dataflow {
 
 class NoopAnalysis : public DataflowAnalysis<NoopAnalysis, NoopLattice> {
 public:
+  NoopAnalysis(ASTContext &Context)
+      : DataflowAnalysis<NoopAnalysis, NoopLattice>(Context) {}
+
   /// Deprecated. Use the `DataflowAnalysisOptions` constructor instead.
   NoopAnalysis(ASTContext &Context, bool ApplyBuiltinTransfer)
       : DataflowAnalysis<NoopAnalysis, NoopLattice>(Context,
                                                     ApplyBuiltinTransfer) {}
 
   /// `ApplyBuiltinTransfer` controls whether to run the built-in transfer
   /// functions that model memory during the analysis. Their results are not
   /// used by `NoopAnalysis`, but tests that need to inspect the environment

clang/unittests/Analysis/FlowSensitive/TypeErasedDataflowAnalysisTest.cpp

 namespace {
 
 using namespace clang;
 using namespace dataflow;
 using namespace test;
 using namespace ast_matchers;
 using llvm::IsStringMapEntry;
 using ::testing::DescribeMatcher;
+using ::testing::ElementsAre;
 using ::testing::IsEmpty;
 using ::testing::NotNull;
 using ::testing::Test;
 using ::testing::UnorderedElementsAre;
 
 template <typename AnalysisT>
 llvm::Expected<std::vector<
     std::optional<DataflowAnalysisState<typename AnalysisT::Lattice>>>>
auto BlockStates = llvm::cantFail(
       runAnalysis<NoopAnalysis>("void target() {}", [](ASTContext &C) {
         return NoopAnalysis(C, false);
       }));
   EXPECT_EQ(BlockStates.size(), 2u);
   EXPECT_TRUE(BlockStates[0].has_value());
   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<ASTUnit> AST =
+      tooling::buildASTFromCodeWithArgs(Code, {"-std=c++11"});
+
+  auto *Func =
+      cast<FunctionDecl>(findValueDecl(AST->getASTContext(), "target"));
+  auto Diagnoser = [](const CFGElement &Elt, ASTContext &,
+                      const TransferStateForDiagnostics<NoopLattice> &) {
+    std::vector<std::string> Diagnostics(1);
+    llvm::raw_string_ostream OS(Diagnostics.front());
+    Elt.dumpToStream(OS);
+    return Diagnostics;
+  };
+  auto Result = diagnoseFunction<NoopAnalysis, std::string>(
+      *Func, AST->getASTContext(), Diagnoser);
+  // `diagnoseFunction` provides no guarantees about the order in which elements
+  // are visited, so we use `UnorderedElementsAre`.
+  EXPECT_THAT_EXPECTED(Result, llvm::HasValue(UnorderedElementsAre(
+                                   "0\n", "int x = 0;\n", "x\n", "++x\n")));
+}
+
 struct NonConvergingLattice {
   int State;
 
   bool operator==(const NonConvergingLattice &Other) const {
     return State == Other.State;
   }
 
   LatticeJoinEffect join(const NonConvergingLattice &Other) {