[analyzer][NFC] Add unittest for FalsePositiveRefutationBRVisitor

[steakhal]

Summary

Adds the test infrastructure for testing the FalsePositiveRefutationBRVisitor.

It will be extended in the D78457 patch, which demonstrates and fixes a bug in
the visitor.

[steakhal]

Upload the right diff.

[xazax.hun]

Thanks! Having more tests is always welcome!

I mentioned some nits inline, but I wonder if you actually need to add a new check. Can't you just reuse existing debug checks?
We have the expr inspeciton checker that supports the following functions:

clang_analyzer_warnIfReached
clang_analyzer_eval

clang/unittests/StaticAnalyzer/FalsePositiveRefutationBRVisitorTest.cpp

25

I think this might not be the idiomatic way to skip a test. Consider using GTEST_SKIP();.

66

Maybe reportIfArgCanBeZero?

116

Wasn't runCheckerOnCodeWithArgs created for this purpose?

[martong]

I like it! Nice work! I have some minor comments.

clang/unittests/StaticAnalyzer/CheckerRegistration.h

93

Do you use this function template anywhere?

clang/unittests/StaticAnalyzer/FalsePositiveRefutationBRVisitorTest.cpp

139

There is no need to have Diags2. You could reuse Diags if in runFalsePositiveGeneratorOnCode you cleared the diag param.

[martong]

clang/unittests/StaticAnalyzer/FalsePositiveRefutationBRVisitorTest.cpp

56

It this not used in the test?

[martong]

clang/unittests/StaticAnalyzer/FalsePositiveRefutationBRVisitorTest.cpp

66

Perhaps a generic reportIfTrue would be more useful. For that you must use another eval function instead of evalEQ

[steakhal]

I addressed most of the comments.

clang/unittests/StaticAnalyzer/CheckerRegistration.h

93

No, I'm just following the pattern of the twin-functions above.
To be honest, I don't know what is the purpose of the variadic template here.

clang/unittests/StaticAnalyzer/FalsePositiveRefutationBRVisitorTest.cpp

25

I agree, though that is not yet supported in the gtest in the repository.
Should we update that to benefit from this macro?

There are several places where we could use that like:

• llvm/unittests/ExecutionEngine/MCJIT/MCJITTestAPICommon.h:29 (expanded 37 times in the codebase)
• llvm/unittests/Support/ThreadPool.cpp:81 (expanded 7 times in the file)
• llvm/unittests/Support/MemoryTest.cpp:89 (expanded 10 time in the file)

56

Now I'm using it :) Thx.

66

I like it! Fixed.

116

Somewhat yes.
For testing purposes, it's valuable to encode the testcase's name into the FileName, to be visible in the exploded graph enabled for debugging.

I have updated the runCheckerOnCodeWithArgs function to address your comment.
Please note that it introduced a dependency between the corresponding header and the gtest header.

139

I would doubt whether that is more readable.
Btw, I moved the declaration closer to the usage.

[xazax.hun]

clang/unittests/StaticAnalyzer/FalsePositiveRefutationBRVisitorTest.cpp

25

I think you should check who updated gtest the last time and ping them what is the process to update it again.

[xazax.hun]

I think this should not be blocked on the gtest update. If getting an updated gtest into the repo takes to much time and the reviewers are happy, I'm fine with doing that change as a follow-up.

Overall it looks good to me but wait for some more reviews before committing.

[whisperity]

clang/unittests/StaticAnalyzer/FalsePositiveRefutationBRVisitorTest.cpp

25

Still maybe this could warrant a // FIXME: Update GTest and use GTEST_SKIP() ?

[martong]

Other than Whispy's nits, LGTM!

clang/unittests/StaticAnalyzer/FalsePositiveRefutationBRVisitorTest.cpp

25

+1

[steakhal]

• added GTEST_SKIP FIXME comment
• reformatted the summary of the patch

[gribozavr2]

I reverted your commit because it seemed to have broken the build:

FalsePositiveRefutationBRVisitorTest.cpp:112:3: error: use of undeclared identifier 'LLVM_WITH_Z3'

https://github.com/llvm/llvm-project/commit/a44425f25b5ca417e7ecee6e7e00040224e50a69

[mgorny]

This commit breaks standalone clang builds.

clang/unittests/StaticAnalyzer/FalsePositiveRefutationBRVisitorTest.cpp

19

config.h is a private LLVM header and must not be used from clang.

[steakhal]

clang/unittests/StaticAnalyzer/FalsePositiveRefutationBRVisitorTest.cpp

19

I'm not a CMake profession, but shouldn't it be declared private to the LLVM target in the corresponding CMakeLists file then?

How do you query whether clang has built with Z3 or not @mgorny?
I'm including that header only for that.

[whisperity]

clang/unittests/StaticAnalyzer/FalsePositiveRefutationBRVisitorTest.cpp

19

I've did a quick skim of the code, and it seems there is no way in it currently to query this.
Your best bet would be either adding an extra flag to Clang's CMake generated Config header that inherits this flag, or checking llvm::CreateZ3Solver() - right now, this method reports a fatal error, but you could create a bool function in the header which reports constant true or false, and turn the test's skip into a runtime condition?

[steakhal]

clang/unittests/StaticAnalyzer/FalsePositiveRefutationBRVisitorTest.cpp

19

How could I use a private header in the first place?

[steakhal]

clang/unittests/StaticAnalyzer/FalsePositiveRefutationBRVisitorTest.cpp

19

The fix is on the way: D84929

clang/lib/StaticAnalyzer/Core/BugReporterVisitors.cpp

 #include "clang/StaticAnalyzer/Core/PathSensitive/SVals.h"
 #include "llvm/ADT/ArrayRef.h"
 #include "llvm/ADT/None.h"
 #include "llvm/ADT/Optional.h"
 #include "llvm/ADT/STLExtras.h"
 #include "llvm/ADT/SmallPtrSet.h"
 #include "llvm/ADT/SmallString.h"
 #include "llvm/ADT/SmallVector.h"
+#include "llvm/ADT/Statistic.h"
 #include "llvm/ADT/StringExtras.h"
 #include "llvm/ADT/StringRef.h"
 #include "llvm/Support/Casting.h"
 #include "llvm/Support/ErrorHandling.h"
 #include "llvm/Support/raw_ostream.h"
 #include <cassert>
 #include <deque>
 #include <memory>
UndefOrNullArgVisitor::VisitNode(const ExplodedNode *N, BugReporterContext &BRC,
   }
   return nullptr;
 }
 
 //===----------------------------------------------------------------------===//
 // Implementation of FalsePositiveRefutationBRVisitor.
 //===----------------------------------------------------------------------===//
 
+#define DEBUG_TYPE "FalsePositiveRefutationBRVisitor"
+STATISTIC(CrosscheckedBugReports,
+          "The # of bug reports which were checked for infeasible constraints");
+STATISTIC(CrosscheckInvalidatedBugReports,
+          "The # of bug reports invalidated due to infeasible constraints");
+
 FalsePositiveRefutationBRVisitor::FalsePositiveRefutationBRVisitor()
     : Constraints(ConstraintRangeTy::Factory().getEmptyMap()) {}
 
 void FalsePositiveRefutationBRVisitor::finalizeVisitor(
     BugReporterContext &BRC, const ExplodedNode *EndPathNode,
     PathSensitiveBugReport &BR) {
+  ++CrosscheckedBugReports;
   // Collect new constraints
   VisitNode(EndPathNode, BRC, BR);
 
   // Create a refutation manager
   llvm::SMTSolverRef RefutationSolver = llvm::CreateZ3Solver();
   ASTContext &Ctx = BRC.getASTContext();
 
   // Add constraints to the solver
for (const auto &I : Constraints) {
     RefutationSolver->addConstraint(Constraints);
   }
 
   // And check for satisfiability
   Optional<bool> isSat = RefutationSolver->check();
   if (!isSat.hasValue())
     return;
 
-  if (!isSat.getValue())
+  if (!isSat.getValue()) {
+    ++CrosscheckInvalidatedBugReports;
     BR.markInvalid("Infeasible constraints", EndPathNode->getLocationContext());
   }
+}
 
 PathDiagnosticPieceRef FalsePositiveRefutationBRVisitor::VisitNode(
     const ExplodedNode *N, BugReporterContext &, PathSensitiveBugReport &) {
   // Collect new constraints
   const ConstraintRangeTy &NewCs = N->getState()->get<ConstraintRange>();
   ConstraintRangeTy::Factory &CF =
       N->getState()->get_context<ConstraintRange>();
 

clang/unittests/StaticAnalyzer/CMakeLists.txt

 set(LLVM_LINK_COMPONENTS
   FrontendOpenMP
   Support
   )
 
 add_clang_unittest(StaticAnalysisTests
   AnalyzerOptionsTest.cpp
   CallDescriptionTest.cpp
   CallEventTest.cpp
+  FalsePositiveRefutationBRVisitorTest.cpp
   ParamRegionTest.cpp
   RangeSetTest.cpp
   RegisterCustomCheckersTest.cpp
   StoreTest.cpp 
   SymbolReaperTest.cpp
   TestReturnValueUnderConstruction.cpp
   )
 

clang/unittests/StaticAnalyzer/CheckerRegistration.h

 //===- unittests/StaticAnalyzer/RegisterCustomCheckersTest.cpp ------------===//
 //
 // Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.
 // See https://llvm.org/LICENSE.txt for license information.
 // SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception
 //
 //===----------------------------------------------------------------------===//
 
 #include "clang/Frontend/CompilerInstance.h"
 #include "clang/StaticAnalyzer/Core/BugReporter/BugReporter.h"
 #include "clang/StaticAnalyzer/Core/BugReporter/BugType.h"
 #include "clang/StaticAnalyzer/Core/Checker.h"
 #include "clang/StaticAnalyzer/Core/PathSensitive/AnalysisManager.h"
 #include "clang/StaticAnalyzer/Frontend/AnalysisConsumer.h"
 #include "clang/StaticAnalyzer/Frontend/CheckerRegistry.h"
 #include "clang/Tooling/Tooling.h"
+#include "gtest/gtest.h"
 
 namespace clang {
 namespace ento {
 
 class DiagConsumer : public PathDiagnosticConsumer {
   llvm::raw_ostream &Output;
 
 public:
std::unique_ptr<ASTConsumer> CreateASTConsumer(CompilerInstance &Compiler,
     std::unique_ptr<AnalysisASTConsumer> AnalysisConsumer =
         CreateAnalysisConsumer(Compiler);
     AnalysisConsumer->AddDiagnosticConsumer(new DiagConsumer(DiagsOutput));
     addChecker<Fns...>(*AnalysisConsumer, *Compiler.getAnalyzerOpts());
     return std::move(AnalysisConsumer);
   }
 };
 
+inline SmallString<80> getCurrentTestNameAsFileName() {
+  const ::testing::TestInfo *Info =
+      ::testing::UnitTest::GetInstance()->current_test_info();
+
+  SmallString<80> FileName;
+  (Twine{Info->name()} + ".cc").toVector(FileName);
+  return FileName;
+}
+
 template <AddCheckerFn... Fns>
 bool runCheckerOnCode(const std::string &Code, std::string &Diags) {
+  const SmallVectorImpl<char> &FileName = getCurrentTestNameAsFileName();
   llvm::raw_string_ostream OS(Diags);
-  return tooling::runToolOnCode(std::make_unique<TestAction<Fns...>>(OS), Code);
+  return tooling::runToolOnCode(std::make_unique<TestAction<Fns...>>(OS), Code,
+                                FileName);
 }
 
 template <AddCheckerFn... Fns>
 bool runCheckerOnCode(const std::string &Code) {
   std::string Diags;
   return runCheckerOnCode<Fns...>(Code, Diags);
 }
 
+template <AddCheckerFn... Fns>
+bool runCheckerOnCodeWithArgs(const std::string &Code,
+                              const std::vector<std::string> &Args,
+                              std::string &Diags) {
+  const SmallVectorImpl<char> &FileName = getCurrentTestNameAsFileName();
+  llvm::raw_string_ostream OS(Diags);
+  return tooling::runToolOnCodeWithArgs(
+      std::make_unique<TestAction<Fns...>>(OS), Code, Args, FileName);
+}
+
+template <AddCheckerFn... Fns>
+bool runCheckerOnCodeWithArgs(const std::string &Code,
+                              const std::vector<std::string> &Args) {
+  std::string Diags;
+  return runCheckerOnCodeWithArgs<Fns...>(Code, Args, Diags);
+}
+
 } // namespace ento
 } // namespace clang

clang/unittests/StaticAnalyzer/FalsePositiveRefutationBRVisitorTest.cpp

+//===- unittests/StaticAnalyzer/FalsePositiveRefutationBRVisitorTest.cpp --===//
+//
+// Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.
+// See https://llvm.org/LICENSE.txt for license information.
+// SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception
+//
+//===----------------------------------------------------------------------===//
+
+#include "CheckerRegistration.h"
+#include "Reusables.h"
+#include "clang/Frontend/CompilerInstance.h"
+#include "clang/StaticAnalyzer/Core/BugReporter/BugReporter.h"
+#include "clang/StaticAnalyzer/Core/BugReporter/BugType.h"
+#include "clang/StaticAnalyzer/Core/Checker.h"
+#include "clang/StaticAnalyzer/Core/PathSensitive/CallEvent.h"
+#include "clang/StaticAnalyzer/Core/PathSensitive/CheckerContext.h"
+#include "clang/StaticAnalyzer/Frontend/AnalysisConsumer.h"
+#include "clang/StaticAnalyzer/Frontend/CheckerRegistry.h"
+#include "llvm/Config/config.h"
+#include "gtest/gtest.h"
+
+// FIXME: Use GTEST_SKIP() instead if GTest is updated to version 1.10.0
+#define SKIP_WITHOUT_Z3                                                        \
+  do                                                                           \
+    if (!LLVM_WITH_Z3)                                                         \
+      return;                                                                  \
+  while (0)
+
+namespace clang {
+namespace ento {
+namespace {
+
+class FalsePositiveGenerator : public Checker<eval::Call> {
+  using Self = FalsePositiveGenerator;
+  const BuiltinBug FalsePositiveGeneratorBug{this, "FalsePositiveGenerator"};
+  using HandlerFn = bool (Self::*)(const CallEvent &Call,
+                                   CheckerContext &) const;
+  CallDescriptionMap<HandlerFn> Callbacks = {
+      {{"reachedWithContradiction", 0}, &Self::reachedWithContradiction},
+      {{"reachedWithNoContradiction", 0}, &Self::reachedWithNoContradiction},
+      {{"reportIfCanBeTrue", 1}, &Self::reportIfCanBeTrue},
+  };
+
+  bool report(CheckerContext &C, ProgramStateRef State,
+              StringRef Description) const {
+    ExplodedNode *Node = C.generateNonFatalErrorNode(State);
+    if (!Node)
+      return false;
+
+    auto Report = std::make_unique<PathSensitiveBugReport>(
+        FalsePositiveGeneratorBug, Description, Node);
+    C.emitReport(std::move(Report));
+    return true;
+  }
+
+  bool reachedWithNoContradiction(const CallEvent &, CheckerContext &C) const {
+    return report(C, C.getState(), "REACHED_WITH_NO_CONTRADICTION");
+  }
+
+  bool reachedWithContradiction(const CallEvent &, CheckerContext &C) const {
+    return report(C, C.getState(), "REACHED_WITH_CONTRADICTION");
+  }
+
+  // Similar to ExprInspectionChecker::analyzerEval except it emits warning only
+  // if the argument can be true. The report emits the report in the state where
+  // the assertion true.
+  bool reportIfCanBeTrue(const CallEvent &Call, CheckerContext &C) const {
+    // A specific instantiation of an inlined function may have more constrained
+    // values than can generally be assumed. Skip the check.
+    if (C.getPredecessor()->getLocationContext()->getStackFrame()->getParent())
+      return false;
+
+    SVal AssertionVal = Call.getArgSVal(0);
+    if (AssertionVal.isUndef())
+      return false;
+
+    ProgramStateRef State = C.getPredecessor()->getState();
+    ProgramStateRef StTrue;
+    std::tie(StTrue, std::ignore) =
+        State->assume(AssertionVal.castAs<DefinedOrUnknownSVal>());
+    if (StTrue)
+      return report(C, StTrue, "CAN_BE_TRUE");
+    return false;
+  }
+
+public:
+  bool evalCall(const CallEvent &Call, CheckerContext &C) const {
+    if (const HandlerFn *Callback = Callbacks.lookup(Call))
+      return (this->*(*Callback))(Call, C);
+    return false;
+  }
+};
+
+void addFalsePositiveGenerator(AnalysisASTConsumer &AnalysisConsumer,
+                               AnalyzerOptions &AnOpts) {
+  AnOpts.CheckersAndPackages = {{"test.FalsePositiveGenerator", true},
+                                {"debug.ViewExplodedGraph", false}};
+  AnalysisConsumer.AddCheckerRegistrationFn([](CheckerRegistry &Registry) {
+    Registry.addChecker<FalsePositiveGenerator>(
+        "test.FalsePositiveGenerator", "EmptyDescription", "EmptyDocsUri");
+  });
+}
+
+// C++20 use constexpr below.
+const std::vector<std::string> LazyAssumeArgs{
+    "-Xclang", "-analyzer-config", "-Xclang", "eagerly-assume=false"};
+const std::vector<std::string> LazyAssumeAndCrossCheckArgs{
+    "-Xclang", "-analyzer-config", "-Xclang", "eagerly-assume=false",
+    "-Xclang", "-analyzer-config", "-Xclang", "crosscheck-with-z3=true"};
+
+TEST(FalsePositiveRefutationBRVisitor, UnSatInTheMiddleNoReport) {
+  SKIP_WITHOUT_Z3;
+  constexpr auto Code = R"(
+     void reachedWithContradiction();
+     void reachedWithNoContradiction();
+     void test(int x, int y) {
+       if (x * y == 0)
+         return;
+       reachedWithNoContradiction();
+       if (x == 0) {
+         reachedWithContradiction();
+         // x * y != 0  =>  x != 0 && y != 0  => contradict with x == 0
+       }
+     })";
+
+  std::string Diags;
+  EXPECT_TRUE(runCheckerOnCodeWithArgs<addFalsePositiveGenerator>(
+      Code, LazyAssumeAndCrossCheckArgs, Diags));
+  EXPECT_EQ(Diags,
+            "test.FalsePositiveGenerator:REACHED_WITH_NO_CONTRADICTION\n");
+  // Single warning. The second report was invalidated by the visitor.
+
+  // Without enabling the crosscheck-with-z3 both reports are displayed.
+  std::string Diags2;
+  EXPECT_TRUE(runCheckerOnCodeWithArgs<addFalsePositiveGenerator>(
+      Code, LazyAssumeArgs, Diags2));
+  EXPECT_EQ(Diags2,
+            "test.FalsePositiveGenerator:REACHED_WITH_NO_CONTRADICTION\n"
+            "test.FalsePositiveGenerator:REACHED_WITH_CONTRADICTION\n");
+}
+
+TEST(FalsePositiveRefutationBRVisitor, UnSatAtErrorNodeWithNewSymbolNoReport) {
+  SKIP_WITHOUT_Z3;
+  constexpr auto Code = R"(
+    void reportIfCanBeTrue(bool);
+    void reachedWithNoContradiction();
+    void test(int x, int y) {
+      if (x * y == 0)
+       return;
+      // We know that 'x * y': {[MIN,-1], [1,MAX]}
+      reachedWithNoContradiction();
+      reportIfCanBeTrue(x == 0); // contradiction
+      // The function introduces the 'x == 0' constraint in the ErrorNode which
+      // leads to contradiction with the constraint of 'x * y'.
+      // Note that the new constraint was bound to a new symbol 'x'.
+    })";
+  std::string Diags;
+  EXPECT_TRUE(runCheckerOnCodeWithArgs<addFalsePositiveGenerator>(
+      Code, LazyAssumeAndCrossCheckArgs, Diags));
+  EXPECT_EQ(Diags,
+            "test.FalsePositiveGenerator:REACHED_WITH_NO_CONTRADICTION\n");
+  // Single warning. The second report was invalidated by the visitor.
+
+  // Without enabling the crosscheck-with-z3 both reports are displayed.
+  std::string Diags2;
+  EXPECT_TRUE(runCheckerOnCodeWithArgs<addFalsePositiveGenerator>(
+      Code, LazyAssumeArgs, Diags2));
+  EXPECT_EQ(Diags2,
+            "test.FalsePositiveGenerator:REACHED_WITH_NO_CONTRADICTION\n"
+            "test.FalsePositiveGenerator:CAN_BE_TRUE\n");
+}
+
+} // namespace
+} // namespace ento
+} // namespace clang