[clang][dataflow] Add modeling of Chromium's CHECK functionality

[ymandel]

Summary

Chromium's implementation of assertions (CHECK, DCHECK, etc.) are not
annotated with "noreturn", by default. This patch adds a model of the logical
implications of successfully executing one of these assertions.

[gribozavr2]

clang/lib/Analysis/FlowSensitive/Models/ChromiumCheckModel.cpp

17–18

Please don't repeat the comment from the header in the cc file.

36

clang/unittests/Analysis/FlowSensitive/ChromiumCheckModelTest.cpp

207

Sorry, could you explain how this works? I think the flow condition should not be implying 'Foo' since we're supposed to ignore this unrelated Check() call.

[ymandel]

fix test

[ymandel]

clang/unittests/Analysis/FlowSensitive/ChromiumCheckModelTest.cpp

207

Good catch -- that was a typo (and the test was failing -- I'd gone back and forth on the formulation and uploaded at the wrong point).

[ymandel]

removed lattice dependency.

[xazax.hun]

clang/unittests/Analysis/FlowSensitive/ChromiumCheckModelTest.cpp

123

I wonder whether the models should actually be called by the framework at some point.
E.g. imagine the following scenario:

void f()
{
    std::optional<int> o(5);
    if (o)
    {
        // dead code here;
    }
}

In an ideal case, an analysis could use the std::optional modeling to realize that the code in the if statement is dead and use this fact to improve its precision. Explicitly request the modeling in the transfer function works OK when we only have a couple things to model. But it might not scale in the future. When we model dozens of standard types and functions we would not want all the analysis clients to invoke all the transfers for all the models individually.

[ymandel]

Thanks for the review!

clang/unittests/Analysis/FlowSensitive/ChromiumCheckModelTest.cpp

123

Agreed. It seems similar the problems that motivated DLLs back in the day. there's clearly a lot to be worked out here in terms of how best to support composition. It's probably worth a RFC or somesuch to discuss in more depth.

[xazax.hun]

clang/unittests/Analysis/FlowSensitive/ChromiumCheckModelTest.cpp

123

Having an RFC and some deeper discussions would be great. I also wonder whether modeling arbitrary Stmts is the right approach. The peculiarities of the language should probably be modelled by the framework itself without any extensions. Maybe we only want the modeling of certain function calls to be customizable?

[sgatev]

clang/include/clang/Analysis/FlowSensitive/Models/ChromiumCheckModel.h

16

This is unnecessary.

clang/lib/Analysis/FlowSensitive/Models/ChromiumCheckModel.cpp

50–56

52

Shouldn't this be part of isCheckLikeMethod?

53

58

clang/unittests/Analysis/FlowSensitive/ChromiumCheckModelTest.cpp

91

Perhaps "Incorrect" instead of "Bad" and comment on what makes it incorrect?

134

We're not testing with other standards so remove this?

[ymandel]

address comments

[ymandel]

address comments

[ymandel]

clang/unittests/Analysis/FlowSensitive/ChromiumCheckModelTest.cpp

123

Good question. It would be really nice if we could draw this line, but I have a bad feeling that it won't be so simple. :) Still, worth looking at our existing models, and new ones that we're developing, to see if we can find a clear "bounding box".

What does CSA do in this regard?

[xbolva00]

Why this should be maintained and developed by LLVM/Clang developers and not by Chromium?

[ymandel]

In D121797#3392444, @xbolva00 wrote:

Why this should be maintained and developed by LLVM/Clang developers and not by Chromium?

That's a good question. I think the short answer, that skirts around the issue, is that this is targeted for use in an upcoming clang-tidy check, and we don't have any framework for clients developing their own pluggable models for individual checks. Chromium could find some way to patch their clang-tidy source, I suppose, but we'd rather not encourage that. This framework is new and under development and the benefit of accomodating Chromium (in this very small way) seems worth the feedback from them applying it to their codebase.

That said, we are *also* in discussions with them to change their implement of CHECK, etc. so as to obviate the need for this model at all.

[xazax.hun]

clang/unittests/Analysis/FlowSensitive/ChromiumCheckModelTest.cpp

123

In the CSA, there is no clear distinction between modeling and diagnostics, each check can do both. Historically, this turned out to be a bad idea. When we have a check that is doing both modeling and diagnostics, users can end up turning the check off due to some false positives and end up getting worse results from other checks because some critical piece of modeling is also turned off. (E.g., even if there are a couple of false positives from a std::optional check, it might still be beneficial to do the modeling in the background without the diagnostics because it might help discover infeasible paths and that can improve the precision of other checks).

Nowadays, we try to make the distinction clear, some checks are modeling only and others are diagnostic only (they might still have their own modeling but they do not affect the global analysis state, i.e., the diagnostic only checks should not be able to affect each other). This distinction is currently a best effort approach and not enforced by any of the APIs.

In CSA, the checker APIs are very powerful. E.g., if there is a pointer with an unknown value and we see a dereference, we can continue the analysis with the assumption that the pointer is not-null. These assumptions could be added by the framework itself or just a regular check. Over time, we are trying to move as much modeling to (non-diagnostic) checks as possible to keep the framework lightweight but most of the meat is still in the framework.

To model libraries, we are using the evalCall callback: https://github.com/llvm/llvm-project/blob/main/clang/lib/StaticAnalyzer/Checkers/CheckerDocumentation.cpp#L229

Roughly speaking the model looks like this:

• The analyzer encounters a function call, so it asks all the checks in a sequence if any of them wants to model it
• A check gets the evalCall callback and can do whatever it wants to do. Most of them will return false most of the time as they are only expected to handle a small subset of the functions.
• This first check returning true will short-circuit this process.
• If none of the checks returned true, the framework will fall back to a default modeling which is a conservative approximation of the call, i.e., invalidating the bindings that could be changes by the function (globals, output arguments, return values etc.)

The model above assumes that when a check return true it will end up modeling all the aspects of a function (like invalidation). A downside might be that it will not solve the composition, when multiple checks want to model the same function, well, the framework will just pick one of them. Also, modeling types is really challenging. E.g., if a modeling check models the constructor of a type but does not model the destructor, the framework will end up using the default modeling for the dtor. The problem is that, in that case the ctor was not modeled by the framework (but the modeling checker) so some invariants were not established. This can result in false positives or even crashes. Overall, it looks like modeling types is almost an all or nothing endeavor. If a check models at least one method of a type it is really likely that it will need to model at least a bunch more to ensure a good experience.

At Microsoft, we have a similar framework to CSA called EspXEngine. In EspXEngine, we have different APIs for modeling and diagnostic so the API enforce that diagnostic checks cannot influence each other. Our model for the modeling checks is very similar to CSA but the idea is that the modeling checks are maintained by the authors of EspXEngine (while diagnostic checks could be written by anyone), so conflicting models are less of a problem.

Both EspXEngine and CSA has problems chaining modeling checks. E.g., if CSA has modeling for unique_ptr and optional, optional<unique_ptr<int>> or unique_ptr<optional<int>> will not model every aspects of the inner type out of the box.

[ymandel]

Thanks, Gabor -- that's a really helpful summary!

clang/include/clang/Analysis/FlowSensitive/Models/ChromiumCheckModel.h

+//===-- ChromiumCheckModel.h ------------------------------------*- C++ -*-===//
+//
+// 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
+//
+//===----------------------------------------------------------------------===//
+//
+// This file defines a dataflow model for Chromium's family of CHECK functions.
+//
+//===----------------------------------------------------------------------===//
+#ifndef CLANG_ANALYSIS_FLOWSENSITIVE_MODELS_CHROMIUMCHECKMODEL_H
+#define CLANG_ANALYSIS_FLOWSENSITIVE_MODELS_CHROMIUMCHECKMODEL_H
+
+#include "clang/AST/DeclCXX.h"
+#include "clang/AST/Stmt.h"
+#include "clang/Analysis/FlowSensitive/DataflowAnalysis.h"
+#include "clang/Analysis/FlowSensitive/DataflowEnvironment.h"
+#include "llvm/ADT/DenseSet.h"
+
+namespace clang {
+namespace dataflow {
+
+/// Models the behavior of Chromium's CHECK, DCHECK, etc. macros, so that code
+/// after a call to `*CHECK` can rely on the condition being true.
+class ChromiumCheckModel : public DataflowModel {
+public:
+  ChromiumCheckModel() = default;
+  bool transfer(const Stmt *Stmt, Environment &Env) override;
+
+private:
+  /// Declarations for `::logging::CheckError::.*Check`, lazily initialized.
+  llvm::SmallDenseSet<const CXXMethodDecl *> CheckDecls;
+};
+
+} // namespace dataflow
+} // namespace clang
+
+#endif // CLANG_ANALYSIS_FLOWSENSITIVE_MODELS_CHROMIUMCHECKMODEL_H

clang/lib/Analysis/FlowSensitive/Models/CMakeLists.txt

 add_clang_library(clangAnalysisFlowSensitiveModels
+  ChromiumCheckModel.cpp
   UncheckedOptionalAccessModel.cpp
 
   LINK_LIBS
   clangAnalysis
   clangAnalysisFlowSensitive
   clangAST
   clangASTMatchers
   clangBasic
   )

clang/lib/Analysis/FlowSensitive/Models/ChromiumCheckModel.cpp

+//===-- ChromiumCheckModel.cpp ----------------------------------*- C++ -*-===//
+//
+// 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/Analysis/FlowSensitive/Models/ChromiumCheckModel.h"
+#include "clang/AST/Decl.h"
+#include "clang/AST/DeclCXX.h"
+#include "llvm/ADT/DenseSet.h"
+
+namespace clang {
+namespace dataflow {
+
+/// Determines whether `D` is one of the methods used to implement Chromium's
+/// `CHECK` macros. Populates `CheckDecls`, if empty.
+bool isCheckLikeMethod(llvm::SmallDenseSet<const CXXMethodDecl *> &CheckDecls,
+                       const CXXMethodDecl &D) {
+  // All of the methods of interest are static, so avoid any lookup for
+  // non-static methods (the common case).
+  if (!D.isStatic())
+    return false;
+
+  if (CheckDecls.empty()) {
+    // Attempt to initialize `CheckDecls` with the methods in class
+    // `CheckError`.
+    const CXXRecordDecl *ParentClass = D.getParent();
+    if (ParentClass == nullptr || !ParentClass->getDeclName().isIdentifier() ||
+        ParentClass->getName() != "CheckError")
+      return false;
+
+    // Check whether namespace is "logging".
+    const auto *N =
+        dyn_cast_or_null<NamespaceDecl>(ParentClass->getDeclContext());
+    if (N == nullptr || !N->getDeclName().isIdentifier() ||
+        N->getName() != "logging")
+      return false;
+
+    // Check whether "logging" is a top-level namespace.
+    if (N->getParent() == nullptr || !N->getParent()->isTranslationUnit())
+      return false;
+
+    for (const CXXMethodDecl *M : ParentClass->methods())
+      if (M->getDeclName().isIdentifier() && M->getName().endswith("Check"))
+        CheckDecls.insert(M);
+  }
+
+  return CheckDecls.contains(&D);
+}
+
+bool ChromiumCheckModel::transfer(const Stmt *Stmt, Environment &Env) {
+  if (const auto *Call = dyn_cast<CallExpr>(Stmt)) {
+    if (const auto *M = dyn_cast<CXXMethodDecl>(Call->getDirectCallee())) {
+      if (isCheckLikeMethod(CheckDecls, *M)) {
+        // Mark this branch as unreachable.
+        Env.addToFlowCondition(Env.getBoolLiteralValue(false));
+        return true;
+      }
+    }
+  }
+  return false;
+}
+
+} // namespace dataflow
+} // namespace clang

clang/unittests/Analysis/FlowSensitive/CMakeLists.txt

 set(LLVM_LINK_COMPONENTS
   FrontendOpenMP
   Support
   )
 
 add_clang_unittest(ClangAnalysisFlowSensitiveTests
+  ChromiumCheckModelTest.cpp
   DataflowAnalysisContextTest.cpp
   DataflowEnvironmentTest.cpp
   MapLatticeTest.cpp
   MatchSwitchTest.cpp
   MultiVarConstantPropagationTest.cpp
   SingleVarConstantPropagationTest.cpp
   SourceLocationsLatticeTest.cpp
   TestingSupport.cpp

clang/unittests/Analysis/FlowSensitive/ChromiumCheckModelTest.cpp

+//===- ChromiumCheckModelTest.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
+//
+//===----------------------------------------------------------------------===//
+// FIXME: Move this to clang/unittests/Analysis/FlowSensitive/Models.
+
+#include "clang/Analysis/FlowSensitive/Models/ChromiumCheckModel.h"
+#include "NoopAnalysis.h"
+#include "TestingSupport.h"
+#include "clang/AST/ASTContext.h"
+#include "clang/ASTMatchers/ASTMatchers.h"
+#include "clang/Tooling/Tooling.h"
+#include "llvm/ADT/ArrayRef.h"
+#include "llvm/ADT/StringExtras.h"
+#include "llvm/Support/Error.h"
+#include "llvm/Testing/Support/Error.h"
+#include "gmock/gmock.h"
+#include "gtest/gtest.h"
+#include <string>
+
+using namespace clang;
+using namespace dataflow;
+using namespace test;
+
+namespace {
+using ::testing::_;
+using ::testing::ElementsAre;
+using ::testing::NotNull;
+using ::testing::Pair;
+
+static constexpr char ChromiumCheckHeader[] = R"(
+namespace std {
+class ostream;
+} // namespace std
+
+namespace logging {
+class VoidifyStream {
+ public:
+  VoidifyStream() = default;
+  void operator&(std::ostream&) {}
+};
+
+class CheckError {
+ public:
+  static CheckError Check(const char* file, int line, const char* condition);
+  static CheckError DCheck(const char* file, int line, const char* condition);
+  static CheckError PCheck(const char* file, int line, const char* condition);
+  static CheckError PCheck(const char* file, int line);
+  static CheckError DPCheck(const char* file, int line, const char* condition);
+
+  std::ostream& stream();
+
+  ~CheckError();
+
+  CheckError(const CheckError& other) = delete;
+  CheckError& operator=(const CheckError& other) = delete;
+  CheckError(CheckError&& other) = default;
+  CheckError& operator=(CheckError&& other) = default;
+};
+
+} // namespace logging
+
+#define LAZY_CHECK_STREAM(stream, condition) \
+  !(condition) ? (void)0 : ::logging::VoidifyStream() & (stream)
+
+#define CHECK(condition)                                                     \
+  LAZY_CHECK_STREAM(                                                         \
+      ::logging::CheckError::Check(__FILE__, __LINE__, #condition).stream(), \
+      !(condition))
+
+#define PCHECK(condition)                                                     \
+  LAZY_CHECK_STREAM(                                                          \
+      ::logging::CheckError::PCheck(__FILE__, __LINE__, #condition).stream(), \
+      !(condition))
+
+#define DCHECK(condition)                                                     \
+  LAZY_CHECK_STREAM(                                                          \
+      ::logging::CheckError::DCheck(__FILE__, __LINE__, #condition).stream(), \
+      !(condition))
+
+#define DPCHECK(condition)                                                     \
+  LAZY_CHECK_STREAM(                                                           \
+      ::logging::CheckError::DPCheck(__FILE__, __LINE__, #condition).stream(), \
+      !(condition))
+)";
+
+// A definition of the `CheckError` class that looks like the Chromium one, but
+// is actually something else.
+static constexpr char OtherCheckHeader[] = R"(
+namespace other {
+namespace logging {
+class CheckError {
+ public:
+  static CheckError Check(const char* file, int line, const char* condition);
+};
+} // namespace logging
+} // namespace other
+)";
+
+/// Replaces all occurrences of `Pattern` in `S` with `Replacement`.
+std::string ReplacePattern(std::string S, const std::string &Pattern,
+                           const std::string &Replacement) {
+  size_t Pos = 0;
+  Pos = S.find(Pattern, Pos);
+  if (Pos != std::string::npos)
+    S.replace(Pos, Pattern.size(), Replacement);
+  return S;
+}
+
+template <typename Model>
+class ModelAdaptorAnalysis
+    : public DataflowAnalysis<ModelAdaptorAnalysis<Model>, NoopLattice> {
+public:
+  explicit ModelAdaptorAnalysis(ASTContext &Context)
+      : DataflowAnalysis<ModelAdaptorAnalysis, NoopLattice>(
+            Context, /*ApplyBuiltinTransfer=*/true) {}
+
+  static NoopLattice initialElement() { return NoopLattice(); }
+
+  void transfer(const Stmt *S, NoopLattice &, Environment &Env) {
+    M.transfer(S, Env);
+  }
+
+private:
+  Model M;
+};
+
+class ChromiumCheckModelTest : public ::testing::TestWithParam<std::string> {
+protected:
+  template <typename Matcher>
+  void runDataflow(llvm::StringRef Code, Matcher Match) {
+    const tooling::FileContentMappings FileContents = {
+        {"check.h", ChromiumCheckHeader}, {"othercheck.h", OtherCheckHeader}};
+
+    ASSERT_THAT_ERROR(
+        test::checkDataflow<ModelAdaptorAnalysis<ChromiumCheckModel>>(
+            Code, "target",
+            [](ASTContext &C, Environment &) {
+              return ModelAdaptorAnalysis<ChromiumCheckModel>(C);
+            },
+            [&Match](
+                llvm::ArrayRef<
+                    std::pair<std::string, DataflowAnalysisState<NoopLattice>>>
+                    Results,
+                ASTContext &ASTCtx) { Match(Results, ASTCtx); },
+            {"-fsyntax-only", "-fno-delayed-template-parsing", "-std=c++17"},
+            FileContents),
+        llvm::Succeeded());
+  }
+};
+
+TEST_F(ChromiumCheckModelTest, CheckSuccessImpliesConditionHolds) {
+  auto Expectations =
+      [](llvm::ArrayRef<
+             std::pair<std::string, DataflowAnalysisState<NoopLattice>>>
+             Results,
+         ASTContext &ASTCtx) {
+        ASSERT_THAT(Results, ElementsAre(Pair("p", _)));
+        const Environment &Env = Results[0].second.Env;
+
+        const ValueDecl *FooDecl = findValueDecl(ASTCtx, "Foo");
+        ASSERT_THAT(FooDecl, NotNull());
+
+        auto *FooVal = cast<BoolValue>(Env.getValue(*FooDecl, SkipPast::None));
+
+        EXPECT_TRUE(Env.flowConditionImplies(*FooVal));
+      };
+
+  std::string Code = R"(
+    #include "check.h"
+
+    void target(bool Foo) {
+      $check(Foo);
+      bool X = true;
+      (void)X;
+      // [[p]]
+    }
+  )";
+  runDataflow(ReplacePattern(Code, "$check", "CHECK"), Expectations);
+  runDataflow(ReplacePattern(Code, "$check", "DCHECK"), Expectations);
+  runDataflow(ReplacePattern(Code, "$check", "PCHECK"), Expectations);
+  runDataflow(ReplacePattern(Code, "$check", "DPCHECK"), Expectations);
+}
+
+TEST_F(ChromiumCheckModelTest, UnrelatedCheckIgnored) {
+  auto Expectations =
+      [](llvm::ArrayRef<
+             std::pair<std::string, DataflowAnalysisState<NoopLattice>>>
+             Results,
+         ASTContext &ASTCtx) {
+        ASSERT_THAT(Results, ElementsAre(Pair("p", _)));
+        const Environment &Env = Results[0].second.Env;
+
+        const ValueDecl *FooDecl = findValueDecl(ASTCtx, "Foo");
+        ASSERT_THAT(FooDecl, NotNull());
+
+        auto *FooVal = cast<BoolValue>(Env.getValue(*FooDecl, SkipPast::None));
+
+        EXPECT_FALSE(Env.flowConditionImplies(*FooVal));
+      };
+
+  std::string Code = R"(
+    #include "othercheck.h"
+
+    void target(bool Foo) {
+      if (!Foo) {
+        (void)other::logging::CheckError::Check(__FILE__, __LINE__, "Foo");
+      }
+      bool X = true;
+      (void)X;
+      // [[p]]
+    }
+  )";
+  runDataflow(Code, Expectations);
+}
+} // namespace