Allow binding nullability of decls to SAT variables, to support inference.
The idea is that instead of nullable/nonnull/unspecified, the nullability of a
decl (typically parameter) can be a variable.
The analysis will determine how that variable interacts with e.g. the
nullability of expressions that are dereferenced, and we can then add SAT
assertions that the function body is safe, and solve for the param nullability.
For now, we only support top-level nullability of pointer-valued params, and
only apply constraints when directly loading pointer values from the param.
This info is stored ad-hoc and doesn't interact with nullability vectors.
A more general solution would store a full nullability-vector of variables
for the decl, and allow nullability-vectors for exprs to contain variables.
However this upgrade will be quite intrusive, so start small.
PiperOrigin-RevId: 540942832
diff --git a/nullability/BUILD b/nullability/BUILD
index 17696cb..3c2eb9f 100644
--- a/nullability/BUILD
+++ b/nullability/BUILD
@@ -11,6 +11,7 @@
"@absl//absl/container:flat_hash_map",
"@absl//absl/log:check",
"@llvm-project//clang:analysis",
+ "@llvm-project//clang:ast",
],
)
@@ -42,6 +43,24 @@
],
)
+cc_test(
+ name = "pointer_nullability_analysis_test",
+ srcs = ["pointer_nullability_analysis_test.cc"],
+ deps = [
+ ":pointer_nullability",
+ ":pointer_nullability_analysis",
+ ":pointer_nullability_lattice",
+ "@llvm-project//clang:analysis",
+ "@llvm-project//clang:ast",
+ "@llvm-project//clang:basic",
+ "@llvm-project//clang:testing",
+ "@llvm-project//llvm:Support",
+ "@llvm-project//third-party/unittest:gmock",
+ "@llvm-project//third-party/unittest:gtest",
+ "@llvm-project//third-party/unittest:gtest_main",
+ ],
+)
+
cc_library(
name = "pointer_nullability_diagnosis",
srcs = ["pointer_nullability_diagnosis.cc"],
diff --git a/nullability/pointer_nullability_analysis.cc b/nullability/pointer_nullability_analysis.cc
index a1ae8d0..a2e8109 100644
--- a/nullability/pointer_nullability_analysis.cc
+++ b/nullability/pointer_nullability_analysis.cc
@@ -265,11 +265,32 @@
}
}
+const PointerTypeNullability* getOverriddenNullability(
+ const Expr* E, PointerNullabilityLattice& Lattice) {
+ if (const auto* DRE = dyn_cast<DeclRefExpr>(E))
+ return Lattice.getDeclNullability(DRE->getDecl());
+ if (const auto* ME = dyn_cast<MemberExpr>(E))
+ return Lattice.getDeclNullability(ME->getMemberDecl());
+ return nullptr;
+}
+
void transferFlowSensitivePointer(
const Expr* PointerExpr, const MatchFinder::MatchResult& Result,
TransferState<PointerNullabilityLattice>& State) {
- if (auto* PointerVal = getPointerValueFromExpr(PointerExpr, State.Env)) {
- initPointerFromAnnotations(*PointerVal, PointerExpr, State);
+ auto& Env = State.Env;
+ if (auto* PointerVal = getPointerValueFromExpr(PointerExpr, Env)) {
+ if (auto* Override = getOverriddenNullability(PointerExpr, State.Lattice)) {
+ // is_known = (nonnull | nullable)
+ initPointerNullState(
+ *PointerVal, Env,
+ &Env.makeOr(*Override->Nonnull, *Override->Nullable));
+ // nonnull => !is_null
+ auto [IsKnown, IsNull] = getPointerNullState(*PointerVal);
+ Env.addToFlowCondition(
+ Env.makeImplication(*Override->Nonnull, Env.makeNot(IsNull)));
+ } else {
+ initPointerFromAnnotations(*PointerVal, PointerExpr, State);
+ }
}
}
@@ -675,6 +696,16 @@
NonFlowSensitiveTransferer(buildNonFlowSensitiveTransferer()),
FlowSensitiveTransferer(buildFlowSensitiveTransferer()) {}
+PointerTypeNullability PointerNullabilityAnalysis::assignNullabilityVariable(
+ const ValueDecl* D, dataflow::Arena& A) {
+ auto [It, Inserted] = NFS.DeclTopLevelNullability.try_emplace(D);
+ if (Inserted) {
+ It->second.Nonnull = &A.create<dataflow::AtomicBoolValue>();
+ It->second.Nullable = &A.create<dataflow::AtomicBoolValue>();
+ }
+ return It->second;
+}
+
void PointerNullabilityAnalysis::transfer(const CFGElement& Elt,
PointerNullabilityLattice& Lattice,
Environment& Env) {
diff --git a/nullability/pointer_nullability_analysis.h b/nullability/pointer_nullability_analysis.h
index 0b88497..81d2bb9 100644
--- a/nullability/pointer_nullability_analysis.h
+++ b/nullability/pointer_nullability_analysis.h
@@ -6,8 +6,11 @@
#define CRUBIT_NULLABILITY_POINTER_NULLABILITY_ANALYSIS_H_
#include "nullability/pointer_nullability_lattice.h"
+#include "nullability/type_nullability.h"
#include "clang/AST/ASTContext.h"
+#include "clang/AST/Decl.h"
#include "clang/AST/Type.h"
+#include "clang/Analysis/FlowSensitive/Arena.h"
#include "clang/Analysis/FlowSensitive/CFGMatchSwitch.h"
#include "clang/Analysis/FlowSensitive/DataflowAnalysis.h"
#include "clang/Analysis/FlowSensitive/DataflowEnvironment.h"
@@ -23,16 +26,42 @@
: public dataflow::DataflowAnalysis<PointerNullabilityAnalysis,
PointerNullabilityLattice> {
private:
- absl::flat_hash_map<const Expr*, std::vector<NullabilityKind>>
- ExprToNullability;
+ PointerNullabilityLattice::NonFlowSensitiveState NFS;
public:
explicit PointerNullabilityAnalysis(ASTContext& context);
PointerNullabilityLattice initialElement() {
- return PointerNullabilityLattice(ExprToNullability);
+ return PointerNullabilityLattice(NFS);
}
+ // Instead of fixing D's nullability invariants from its annotations,
+ // bind them to symbolic variables, and return those variables.
+ // This is useful to infer the annotations that should be present on D.
+ //
+ // For example, given the following program:
+ // void target(int* p) {
+ // int* q = p;
+ // *q;
+ // }
+ //
+ // By default, p is treated as having unspecified nullability.
+ // When we reach the dereference, our flow condition will say:
+ // is_known = false
+ //
+ // However, if we bind p's nullability to a variable:
+ // [p_nonnull, p_nullable] = assignNullabilityVariable(p)
+ // Then the flow condition at dereference includes:
+ // is_known = (p_nonnull | p_nullable)
+ // p_nonnull => !is_null
+ // Logically connecting dereferenced values and possible invariants on p
+ // allows us to infer p's proper annotations (here: Nonnull).
+ //
+ // For now, only the top-level nullability is assigned, and the returned
+ // variables are only associated with direct reads of pointer values from D.
+ PointerTypeNullability assignNullabilityVariable(const ValueDecl* D,
+ dataflow::Arena&);
+
void transfer(const CFGElement& Elt, PointerNullabilityLattice& Lattice,
dataflow::Environment& Env);
diff --git a/nullability/pointer_nullability_analysis_test.cc b/nullability/pointer_nullability_analysis_test.cc
new file mode 100644
index 0000000..8c4d8aa
--- /dev/null
+++ b/nullability/pointer_nullability_analysis_test.cc
@@ -0,0 +1,92 @@
+// Part of the Crubit project, under the Apache License v2.0 with LLVM
+// Exceptions. See /LICENSE for license information.
+// SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception
+
+#include "nullability/pointer_nullability_analysis.h"
+
+#include <memory>
+#include <optional>
+
+#include "nullability/pointer_nullability.h"
+#include "nullability/pointer_nullability_lattice.h"
+#include "clang/AST/Decl.h"
+#include "clang/AST/DeclBase.h"
+#include "clang/Analysis/CFG.h"
+#include "clang/Analysis/FlowSensitive/ControlFlowContext.h"
+#include "clang/Analysis/FlowSensitive/DataflowAnalysis.h"
+#include "clang/Analysis/FlowSensitive/DataflowAnalysisContext.h"
+#include "clang/Analysis/FlowSensitive/DataflowEnvironment.h"
+#include "clang/Analysis/FlowSensitive/TypeErasedDataflowAnalysis.h"
+#include "clang/Analysis/FlowSensitive/Value.h"
+#include "clang/Analysis/FlowSensitive/WatchedLiteralsSolver.h"
+#include "clang/Basic/LLVM.h"
+#include "clang/Testing/TestAST.h"
+#include "llvm/Support/Error.h"
+#include "third_party/llvm/llvm-project/third-party/unittest/googletest/include/gtest/gtest.h"
+
+namespace clang::tidy::nullability {
+namespace {
+
+NamedDecl *lookup(StringRef Name, const DeclContext &DC) {
+ auto Result = DC.lookup(&DC.getParentASTContext().Idents.get(Name));
+ EXPECT_TRUE(Result.isSingleResult()) << Name;
+ return Result.front();
+}
+
+std::optional<bool> evaluate(dataflow::BoolValue &B,
+ dataflow::Environment &Env) {
+ if (Env.flowConditionImplies(B)) return true;
+ if (Env.flowConditionImplies(Env.makeNot(B))) return false;
+ return std::nullopt;
+}
+
+TEST(PointerNullabilityAnalysis, AssignNullabilityVariable) {
+ // Annotations on p constrain nullabiilty of the return value.
+ // This tests we can compute that relationship symbolically.
+ TestAST AST(R"cpp(
+ int *target(int *p) {
+ int *q = p;
+ return q;
+ }
+ )cpp");
+ auto *Target = cast<FunctionDecl>(
+ lookup("target", *AST.context().getTranslationUnitDecl()));
+ auto *P = Target->getParamDecl(0);
+
+ // Run the analysis, with p's annotations bound to variables.
+ dataflow::DataflowAnalysisContext::Options Opts;
+ // Track return values, but don't actually descend into callees
+ Opts.ContextSensitiveOpts.emplace();
+ Opts.ContextSensitiveOpts->Depth = 0;
+ dataflow::DataflowAnalysisContext DACtx(
+ std::make_unique<dataflow::WatchedLiteralsSolver>(), Opts);
+ auto &A = DACtx.arena();
+ auto CFCtx = dataflow::ControlFlowContext::build(*Target);
+ PointerNullabilityAnalysis Analysis(AST.context());
+ auto [PNonnull, PNullable] = Analysis.assignNullabilityVariable(P, A);
+ auto ExitState =
+ *cantFail(dataflow::runDataflowAnalysis(
+ *CFCtx, Analysis, dataflow::Environment(DACtx, *Target)))
+ .front();
+ // Get the nullability model of the return value.
+ auto *Ret =
+ dyn_cast_or_null<dataflow::PointerValue>(ExitState.Env.getReturnValue());
+ ASSERT_NE(Ret, nullptr);
+ auto [RetKnown, RetNull] = getPointerNullState(*Ret);
+
+ // The param nullability hasn't been fixed.
+ EXPECT_EQ(std::nullopt, evaluate(*PNonnull, ExitState.Env));
+ EXPECT_EQ(std::nullopt, evaluate(*PNullable, ExitState.Env));
+ // Nor has the the nullability of the returned pointer.
+ EXPECT_EQ(std::nullopt, evaluate(RetKnown, ExitState.Env));
+ EXPECT_EQ(std::nullopt, evaluate(RetNull, ExitState.Env));
+ // However, the two are linked as expected.
+ EXPECT_EQ(true, evaluate(A.makeImplies(*PNonnull, A.makeNot(RetNull)),
+ ExitState.Env));
+ EXPECT_EQ(true,
+ evaluate(A.makeEquals(A.makeOr(*PNonnull, *PNullable), RetKnown),
+ ExitState.Env));
+}
+
+} // namespace
+} // namespace clang::tidy::nullability
diff --git a/nullability/pointer_nullability_lattice.h b/nullability/pointer_nullability_lattice.h
index 0164267..407d785 100644
--- a/nullability/pointer_nullability_lattice.h
+++ b/nullability/pointer_nullability_lattice.h
@@ -11,7 +11,7 @@
#include "absl/container/flat_hash_map.h"
#include "absl/log/check.h"
#include "nullability/type_nullability.h"
-#include "clang/Analysis/FlowSensitive/DataflowAnalysis.h"
+#include "clang/AST/Expr.h"
#include "clang/Analysis/FlowSensitive/DataflowAnalysisContext.h"
#include "clang/Analysis/FlowSensitive/DataflowLattice.h"
@@ -21,18 +21,20 @@
class PointerNullabilityLattice {
private:
- // Owned by the PointerNullabilityAnalysis object, shared by all lattice
- // elements within one analysis run.
- absl::flat_hash_map<const Expr *, TypeNullability> &ExprToNullability;
public:
- PointerNullabilityLattice(
- absl::flat_hash_map<const Expr *, TypeNullability> &ExprToNullability)
- : ExprToNullability(ExprToNullability) {}
+ struct NonFlowSensitiveState {
+ absl::flat_hash_map<const Expr *, TypeNullability> ExprToNullability;
+ // Overridden symbolic nullability for pointer-typed decls.
+ absl::flat_hash_map<const ValueDecl *, PointerTypeNullability>
+ DeclTopLevelNullability;
+ };
+
+ PointerNullabilityLattice(NonFlowSensitiveState &NFS) : NFS(NFS) {}
const TypeNullability *getExprNullability(const Expr *E) const {
- auto I = ExprToNullability.find(&dataflow::ignoreCFGOmittedNodes(*E));
- return I == ExprToNullability.end() ? nullptr : &I->second;
+ auto I = NFS.ExprToNullability.find(&dataflow::ignoreCFGOmittedNodes(*E));
+ return I == NFS.ExprToNullability.end() ? nullptr : &I->second;
}
// If the `ExprToNullability` map already contains an entry for `E`, does
@@ -42,20 +44,35 @@
const TypeNullability &insertExprNullabilityIfAbsent(
const Expr *E, const std::function<TypeNullability()> &GetNullability) {
E = &dataflow::ignoreCFGOmittedNodes(*E);
- if (auto It = ExprToNullability.find(E); It != ExprToNullability.end())
+ if (auto It = NFS.ExprToNullability.find(E);
+ It != NFS.ExprToNullability.end())
return It->second;
// Deliberately perform a separate lookup after calling GetNullability.
// It may invalidate iterators, e.g. inserting missing vectors for children.
- auto [Iterator, Inserted] = ExprToNullability.insert({E, GetNullability()});
+ auto [Iterator, Inserted] =
+ NFS.ExprToNullability.insert({E, GetNullability()});
CHECK(Inserted) << "GetNullability inserted same " << E->getStmtClassName();
return Iterator->second;
}
+ // Returns overridden nullability information associated with a declaration.
+ // For now we only track top-level decl nullability symbolically.
+ const PointerTypeNullability *getDeclNullability(const ValueDecl *D) const {
+ auto It = NFS.DeclTopLevelNullability.find(D);
+ if (It == NFS.DeclTopLevelNullability.end()) return nullptr;
+ return &It->second;
+ }
+
bool operator==(const PointerNullabilityLattice &Other) const { return true; }
dataflow::LatticeJoinEffect join(const PointerNullabilityLattice &Other) {
return dataflow::LatticeJoinEffect::Unchanged;
}
+
+ private:
+ // Owned by the PointerNullabilityAnalysis object, shared by all lattice
+ // elements within one analysis run.
+ NonFlowSensitiveState &NFS;
};
inline std::ostream &operator<<(std::ostream &OS,
diff --git a/nullability/type_nullability.h b/nullability/type_nullability.h
index 031d821..3a12dbf 100644
--- a/nullability/type_nullability.h
+++ b/nullability/type_nullability.h
@@ -33,6 +33,9 @@
#include "clang/Basic/LLVM.h"
#include "clang/Basic/Specifiers.h"
+namespace clang::dataflow {
+class BoolValue;
+}
namespace clang::tidy::nullability {
/// Externalized nullability of a clang::Type.
@@ -52,6 +55,17 @@
/// PointerType encountered in a preorder traversal of the canonical type.
using TypeNullability = std::vector<NullabilityKind>;
+/// Describes the nullability of a pointer "slot" within a type.
+///
+/// This may represent a concrete NullabilityKind,
+/// e.g. NullabilityKind::NonNull = {Nonnull=true, Nullable=false}
+/// Or it may be symbolic: e.g. Nonnull may be an AtomicBoolValue which we want
+/// to infer, and which may be connected to SAT constraints.
+struct PointerTypeNullability {
+ dataflow::BoolValue* Nonnull; // True if this slot is marked non-null.
+ dataflow::BoolValue* Nullable; // True if this slot is marked nullable.
+};
+
/// Returns the `NullabilityKind` corresponding to the nullability annotation on
/// `Type` if present. Otherwise, returns `NullabilityKind::Unspecified`.
NullabilityKind getNullabilityKind(QualType Type, ASTContext& Ctx);
