Use the dataflow analysis framework to propagate the nullability of expressions.
Consider the following code:
```
template<typename T0, typename T1>
struct Pair{
T0 f;
T1 s;
};
void target(Pair<int*, int * _Nullable> p) {
*p.f;
}
```
We want to know whether `*p.f` is a null-safe operation. If `p` were a concrete structure, it would suffice to look at its type. However, since p is not concrete, its type signature has no nullability annotations: all sugar has been stripped away during template instantiation.
The base expression of `p.f` is `p`. If we look at the AST of `p.f`, we will find a `DeclRefExpr` of `p`, which looks roughly like this:
```DeclRefExpr 0x55... <col:x> 'Pair<int *, int * _Nullable>':'Pair<int *, int *>' lvalue ParmVar 0x55... 'p' 'Pair<int *, int * _Nullable>':'Pair<int *, int *>'```
Note that the nullability annotation that we wrote when declaring `p` is present in the `DeclRefExpr`. What is the nullability of `p`? Well, we can go over all the pointer types “inside” `p`'s `DeclRefExpr` and keep track of each of their nullabilities. We could even go ahead and store this information in some kind of data structure. Here, `p` is a `Pair` specialization with one non-annotated pointer and one pointer annotated as nullable. We can thus construct a *nullability vector* for `p` that looks like this: `{Unknown, _Nullable}`.
If we know that `p` has nullability `{Unknown, _Nullable}`, and if we know that the return type of `.f` is the first type argument of `p`, we can find that the nullability of `p.f` is `Unknown`, so the dereference above is safe.
Up until now, we have been uncovering the nullability of class template specializations as described above: we would find the expression's "base type" (in the case above, a `DeclRefExpr`), and use that to find the expression's nullability.
Now, consider a slightly more complex member access:
```
template<typename T0, typename T1>
struct Pair{
T0 f;
T1 s;
};
void target(Pair<Pair<int*, int * _Nullable>, int* _Nonnull> p) {
*p.f.s;
}
```
Again, we would want to look into the base expression of `p.f.s` to find its nullability. However, the base of `p.f.s` is `p.f`, which is itself also a `MemberExpr`. Like `.s`, `.f` does not contain type sugar. We would thus have to go one level further to find the `DeclRefExpr` of `p`. From there, we can compute the nullability of `p.f`, and use that to compute the nullability of `p.f.s`.
To search for the nullability of a templated expression as described above, we could recursively pattern match over different expression shapes. From a given expression, we would dive all the way down to its `Decl`, read its nullability, and then move up the AST, at each stage using the nullability of the "previous" expression to compute that of the one being visited. This is what we have been doing for a limited range of expression shapes. However, this process of traversing an AST in post-order is already done by our static analysis. Therefore, we could add this construction of nullability annotations as a step in relevant transfer functions. This is what this CL introduces.
Now, when processing a CFG element, we do the following:
1) If the element is a `DeclRefExpr` (e.g., `p`), construct its nullability vector from the type annotations (in this case, `{Unknown, _Nullable, _Nonnull}`), and store that in the `ExprToNullability` map in the dataflow lattice.
2) If the element is a `MemberExpr` (e.g., `.f` or `.s`), find the element’s base (in this case, `p` and `.f`, respectively), search for its nullability in the lattice maps, and use information about its type and the base type to construct its own nullability vector (`{Unknown, _Nullable}` and `{_Nullable}`, respectively). Store this vector in the `ExprToNullability` map.
This allows us to find the nullability of expressions whose base types have been desugared, without having to pattern match over specific expression shapes.
We currently process `MemberExpr` and `DeclRefExpr` CFG elements as defined above, but such a construction would also be useful for other expression types. For example, adding support for `MemberCallExpr`s would allow us to correctly assess the nullability of concatenated member *function* calls, such as `x.getArg0().getArg1()`.
PiperOrigin-RevId: 496120804
diff --git a/nullability_verification/pointer_nullability_analysis.cc b/nullability_verification/pointer_nullability_analysis.cc
index 9c9e9ad..eb8a639 100644
--- a/nullability_verification/pointer_nullability_analysis.cc
+++ b/nullability_verification/pointer_nullability_analysis.cc
@@ -127,6 +127,18 @@
Visit(TA.getAsType());
}
}
+
+ void VisitRecordType(const RecordType* RT) {
+ if (auto* CTSD = dyn_cast<ClassTemplateSpecializationDecl>(RT->getDecl())) {
+ for (auto& TA : CTSD->getTemplateArgs().asArray()) {
+ Visit(TA);
+ }
+ }
+ }
+
+ void VisitTemplateSpecializationType(const TemplateSpecializationType* TST) {
+ Visit(TST->desugar());
+ }
};
unsigned countPointersInType(QualType T) {
@@ -164,13 +176,22 @@
ArrayRef<NullabilityKind> BaseNullabilityAnnotations, QualType BaseType) {
unsigned PointerCount = 0;
unsigned ArgIndex = STTPT->getIndex();
- if (auto TST = BaseType->getAs<TemplateSpecializationType>()) {
- for (auto TA : TST->template_arguments().take_front(ArgIndex)) {
- PointerCount += countPointersInType(TA);
+ if (auto RT = BaseType->getAs<RecordType>()) {
+ if (auto CTSD = dyn_cast<ClassTemplateSpecializationDecl>(RT->getDecl())) {
+ auto TemplateArgs = CTSD->getTemplateArgs().asArray();
+ for (auto TA : TemplateArgs.take_front(ArgIndex)) {
+ PointerCount += countPointersInType(TA);
+ }
+ unsigned SliceSize = countPointersInType(TemplateArgs[ArgIndex]);
+ if (BaseNullabilityAnnotations.size() < PointerCount + SliceSize) {
+ // TODO: Currently, BaseNullabilityAnnotations can be erroneously empty
+ // due to lack of expression coverage. Use the dataflow lattice to
+ // retrieve correct base type annotations. Then, remove this fallback.
+ return {};
+ } else {
+ return BaseNullabilityAnnotations.slice(PointerCount, SliceSize);
+ }
}
- unsigned SliceSize =
- countPointersInType(TST->template_arguments()[ArgIndex]);
- return BaseNullabilityAnnotations.slice(PointerCount, SliceSize);
}
return ArrayRef<NullabilityKind>();
}
@@ -264,11 +285,11 @@
QualType getBaseType(const Expr* E) {
if (auto ME = dyn_cast<MemberExpr>(E)) {
- return getBaseType(ME->getBase());
+ return ME->getBase()->getType();
} else if (auto MC = dyn_cast<CXXMemberCallExpr>(E)) {
- return getBaseType(MC->getImplicitObjectArgument());
- } else if (auto DRE = dyn_cast<DeclRefExpr>(E)) {
- return DRE->getType();
+ return MC->getImplicitObjectArgument()->getType();
+ } else if (auto ICE = dyn_cast<ImplicitCastExpr>(E)) {
+ return ICE->getSubExpr()->getType();
}
// TODO: Handle other expression shapes and base types.
else {
@@ -299,30 +320,45 @@
return NullabilityAnnotations[0];
}
-NullabilityKind getPointerNullability(const Expr* E, ASTContext& Ctx) {
+NullabilityKind getPointerNullability(const Expr* E, ASTContext& Ctx,
+ PointerNullabilityAnalysis::Lattice& L) {
QualType ExprType = E->getType();
- NullabilityKind Nullability =
- ExprType->getNullability(Ctx).value_or(NullabilityKind::Unspecified);
- if (Nullability == NullabilityKind::Unspecified) {
- // If the type does not contain nullability information, try to gather it
- // from the expression itself.
+ Optional<NullabilityKind> Nullability = ExprType->getNullability(Ctx);
+
+ // If the expression's type does not contain nullability information, it may
+ // be a template instantiation. Look up the nullability in the
+ // `ExprToNullability` map.
+ if (Nullability.value_or(NullabilityKind::Unspecified) ==
+ NullabilityKind::Unspecified) {
+ if (auto MaybeNullability = L.getExprNullability(E)) {
+ if (!MaybeNullability->empty()) {
+ // Return the nullability of the topmost pointer in the type.
+ Nullability = (*MaybeNullability)[0];
+ }
+ }
+ }
+ // TODO: Expand the dataflow analysis algorithm to propagate the nullability
+ // of more expression shapes (e.g., method calls), and then delete
+ // getNullabilityFromTemplatedExpression.
+ if (!Nullability.has_value()) {
Nullability = getNullabilityFromTemplatedExpression(E);
}
- return Nullability;
+ return Nullability.value_or(NullabilityKind::Unspecified);
}
void initPointerFromAnnotations(PointerValue& PointerVal, const Expr* E,
- Environment& Env, ASTContext& Ctx) {
- NullabilityKind Nullability = getPointerNullability(E, Ctx);
+ TransferState<PointerNullabilityLattice>& State,
+ ASTContext& Ctx) {
+ NullabilityKind Nullability = getPointerNullability(E, Ctx, State.Lattice);
switch (Nullability) {
case NullabilityKind::NonNull:
- initNotNullPointer(PointerVal, Env);
+ initNotNullPointer(PointerVal, State.Env);
break;
case NullabilityKind::Nullable:
- initNullablePointer(PointerVal, Env);
+ initNullablePointer(PointerVal, State.Env);
break;
default:
- initUnknownPointer(PointerVal, Env);
+ initUnknownPointer(PointerVal, State.Env);
}
}
@@ -346,7 +382,7 @@
const MatchFinder::MatchResult& Result,
TransferState<PointerNullabilityLattice>& State) {
if (auto* PointerVal = getPointerValueFromExpr(PointerExpr, State.Env)) {
- initPointerFromAnnotations(*PointerVal, PointerExpr, State.Env,
+ initPointerFromAnnotations(*PointerVal, PointerExpr, State,
*Result.Context);
}
}
@@ -422,10 +458,51 @@
State.Env.setValue(CallExprLoc, *PointerVal);
State.Env.setStorageLocation(*CallExpr, CallExprLoc);
}
- initPointerFromAnnotations(*PointerVal, CallExpr, State.Env, *Result.Context);
+ initPointerFromAnnotations(*PointerVal, CallExpr, State, *Result.Context);
}
-auto buildTransferer() {
+void transferDeclRefExpr(const DeclRefExpr* DRE,
+ const MatchFinder::MatchResult& MR,
+ TransferState<PointerNullabilityLattice>& State) {
+ State.Lattice.insertExprNullabilityIfAbsent(
+ DRE, [&]() { return getNullabilityAnnotationsFromType(DRE->getType()); });
+ if (DRE->getType()->isPointerType()) {
+ transferPointer(DRE, MR, State);
+ }
+}
+
+void transferMemberExpr(const MemberExpr* ME,
+ const MatchFinder::MatchResult& MR,
+ TransferState<PointerNullabilityLattice>& State) {
+ State.Lattice.insertExprNullabilityIfAbsent(ME, [&]() {
+ auto BaseNullability = State.Lattice.getExprNullability(ME->getBase());
+ if (BaseNullability.has_value()) {
+ return substituteNullabilityAnnotationsInTemplate(
+ ME->getType(), *BaseNullability, ME->getBase()->getType());
+ } else {
+ // Since we process child nodes before parents, we should already have
+ // computed the base (child) nullability. However, this is not true in all
+ // test cases. So, we return unspecified nullability annotations.
+ // TODO: Fix this issue, add ._has_value() as a CHECK statement and remove
+ // else branch.
+ return std::vector<NullabilityKind>(countPointersInType(ME->getType()),
+ NullabilityKind::Unspecified);
+ }
+ });
+ if (ME->getType()->isPointerType()) {
+ transferPointer(ME, MR, State);
+ }
+}
+
+auto buildNonFlowSensitiveTransferer() {
+ return CFGMatchSwitchBuilder<TransferState<PointerNullabilityLattice>>()
+ .CaseOfCFGStmt<DeclRefExpr>(ast_matchers::declRefExpr(),
+ transferDeclRefExpr)
+ .CaseOfCFGStmt<MemberExpr>(ast_matchers::memberExpr(), transferMemberExpr)
+ .Build();
+}
+
+auto buildFlowSensitiveTransferer() {
return CFGMatchSwitchBuilder<TransferState<PointerNullabilityLattice>>()
// Handles initialization of the null states of pointers.
.CaseOfCFGStmt<Expr>(isCXXThisExpr(), transferNotNullPointer)
@@ -446,13 +523,15 @@
PointerNullabilityAnalysis::PointerNullabilityAnalysis(ASTContext& Context)
: DataflowAnalysis<PointerNullabilityAnalysis, PointerNullabilityLattice>(
Context),
- Transferer(buildTransferer()) {}
+ NonFlowSensitiveTransferer(buildNonFlowSensitiveTransferer()),
+ FlowSensitiveTransferer(buildFlowSensitiveTransferer()) {}
void PointerNullabilityAnalysis::transfer(const CFGElement* Elt,
PointerNullabilityLattice& Lattice,
Environment& Env) {
TransferState<PointerNullabilityLattice> State(Lattice, Env);
- Transferer(*Elt, getASTContext(), State);
+ NonFlowSensitiveTransferer(*Elt, getASTContext(), State);
+ FlowSensitiveTransferer(*Elt, getASTContext(), State);
}
BoolValue& mergeBoolValues(BoolValue& Bool1, const Environment& Env1,
