blob: 07455673d3c3b923b509264fd31912194c51642d [file] [log] [blame]
Wei Yi Tee543af742022-06-01 06:52:24 -07001// Part of the Crubit project, under the Apache License v2.0 with LLVM
2// Exceptions. See /LICENSE for license information.
3// SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception
4
5#include "nullability_verification/pointer_nullability_analysis.h"
6
Wei Yi Tee543af742022-06-01 06:52:24 -07007#include <string>
8
9#include "common/check.h"
10#include "nullability_verification/pointer_nullability_lattice.h"
11#include "nullability_verification/pointer_nullability_matchers.h"
12#include "clang/AST/ASTContext.h"
13#include "clang/AST/Expr.h"
Wei Yi Tee1cd62af2022-06-09 00:56:46 -070014#include "clang/AST/OperationKinds.h"
15#include "clang/AST/Stmt.h"
16#include "clang/AST/Type.h"
Wei Yi Tee543af742022-06-01 06:52:24 -070017#include "clang/ASTMatchers/ASTMatchFinder.h"
Wei Yi Tee543af742022-06-01 06:52:24 -070018#include "clang/Analysis/FlowSensitive/DataflowEnvironment.h"
19#include "clang/Analysis/FlowSensitive/MatchSwitch.h"
20#include "clang/Analysis/FlowSensitive/Value.h"
21#include "clang/Basic/LLVM.h"
22
23namespace clang {
24namespace tidy {
25namespace nullability {
26
27using ast_matchers::MatchFinder;
28using dataflow::BoolValue;
29using dataflow::Environment;
30using dataflow::MatchSwitchBuilder;
31using dataflow::PointerValue;
32using dataflow::SkipPast;
33using dataflow::TransferState;
34using dataflow::Value;
35
36namespace {
37
Wei Yi Tee85d87372022-06-09 01:01:35 -070038BoolValue& getPointerNotNullProperty(
Wei Yi Tee1cd62af2022-06-09 00:56:46 -070039 const Expr* PointerExpr, TransferState<PointerNullabilityLattice>& State) {
40 auto* PointerVal =
41 cast<PointerValue>(State.Env.getValue(*PointerExpr, SkipPast::Reference));
Wei Yi Tee85d87372022-06-09 01:01:35 -070042 CHECK(State.Lattice.hasPointerNotNullProperty(PointerVal));
43 return *State.Lattice.getPointerNotNullProperty(PointerVal);
Wei Yi Tee1cd62af2022-06-09 00:56:46 -070044}
45
Wei Yi Tee85d87372022-06-09 01:01:35 -070046void initialisePointerNotNullProperty(
Wei Yi Teecebc2262022-06-10 04:27:57 -070047 const Expr* PointerExpr, TransferState<PointerNullabilityLattice>& State,
48 BoolValue* NotNullProperty = nullptr) {
Wei Yi Tee543af742022-06-01 06:52:24 -070049 if (auto* PointerVal = cast_or_null<PointerValue>(
Wei Yi Teef02698e2022-06-10 04:25:48 -070050 State.Env.getValue(*PointerExpr, SkipPast::Reference))) {
Wei Yi Tee85d87372022-06-09 01:01:35 -070051 if (!State.Lattice.hasPointerNotNullProperty(PointerVal)) {
Wei Yi Teecebc2262022-06-10 04:27:57 -070052 State.Lattice.setPointerNotNullProperty(
53 PointerVal,
54 NotNullProperty ? NotNullProperty : &State.Env.makeAtomicBoolValue());
Wei Yi Tee543af742022-06-01 06:52:24 -070055 }
56 }
57}
58
Wei Yi Teef02698e2022-06-10 04:25:48 -070059void transferInitPointerVariableReference(
Wei Yi Teecebc2262022-06-10 04:27:57 -070060 const Expr* PointerExpr, const MatchFinder::MatchResult&,
Wei Yi Teef02698e2022-06-10 04:25:48 -070061 TransferState<PointerNullabilityLattice>& State) {
Wei Yi Teecebc2262022-06-10 04:27:57 -070062 initialisePointerNotNullProperty(PointerExpr, State);
63}
64
65void transferInitCXXThisExpr(const Expr* ThisExpr,
66 const MatchFinder::MatchResult&,
67 TransferState<PointerNullabilityLattice>& State) {
68 initialisePointerNotNullProperty(ThisExpr, State,
69 &State.Env.getBoolLiteralValue(true));
Wei Yi Teef02698e2022-06-10 04:25:48 -070070}
71
Wei Yi Tee1cd62af2022-06-09 00:56:46 -070072void transferNullPointerLiteral(
73 const Expr* NullPointer, const MatchFinder::MatchResult& Result,
74 TransferState<PointerNullabilityLattice>& State) {
75 auto* NullPointerVal = cast_or_null<PointerValue>(
76 State.Env.getValue(*NullPointer, SkipPast::None));
77 if (NullPointerVal == nullptr) {
78 // Create storage location and value for null pointer if it doesn't exist
79 auto& NullPointerLoc = State.Env.createStorageLocation(*NullPointer);
80 NullPointerVal = &State.Env.takeOwnership(
81 std::make_unique<PointerValue>(NullPointerLoc));
82 State.Env.setStorageLocation(*NullPointer, NullPointerLoc);
83 State.Env.setValue(NullPointerLoc, *NullPointerVal);
84 }
Wei Yi Tee85d87372022-06-09 01:01:35 -070085 if (!State.Lattice.hasPointerNotNullProperty(NullPointerVal)) {
Wei Yi Tee1cd62af2022-06-09 00:56:46 -070086 // Set null pointer to be known null if not already set
Wei Yi Tee85d87372022-06-09 01:01:35 -070087 State.Lattice.setPointerNotNullProperty(
88 NullPointerVal, &State.Env.getBoolLiteralValue(false));
Wei Yi Tee1cd62af2022-06-09 00:56:46 -070089 }
90}
91
92void transferAddrOf(const UnaryOperator* UnaryOp,
93 const MatchFinder::MatchResult& Result,
94 TransferState<PointerNullabilityLattice>& State) {
95 auto* PointerVal =
96 cast<PointerValue>(State.Env.getValue(*UnaryOp, SkipPast::None));
Wei Yi Tee85d87372022-06-09 01:01:35 -070097 State.Lattice.setPointerNotNullProperty(PointerVal,
98 &State.Env.getBoolLiteralValue(true));
Wei Yi Tee1cd62af2022-06-09 00:56:46 -070099}
100
Wei Yi Teef02698e2022-06-10 04:25:48 -0700101void transferPointerAccess(const Expr* PointerExpr,
102 TransferState<PointerNullabilityLattice>& State) {
Wei Yi Tee85d87372022-06-09 01:01:35 -0700103 auto& PointerNotNull = getPointerNotNullProperty(PointerExpr, State);
104 if (!State.Env.flowConditionImplies(PointerNotNull)) {
Wei Yi Tee1cd62af2022-06-09 00:56:46 -0700105 State.Lattice.addViolation(PointerExpr);
Wei Yi Tee543af742022-06-01 06:52:24 -0700106 }
Wei Yi Tee543af742022-06-01 06:52:24 -0700107}
108
Wei Yi Teef02698e2022-06-10 04:25:48 -0700109void transferDereference(const UnaryOperator* UnaryOp,
110 const MatchFinder::MatchResult&,
111 TransferState<PointerNullabilityLattice>& State) {
112 transferPointerAccess(UnaryOp->getSubExpr(), State);
113}
114
115void transferMemberExprInvolvingPointers(
116 const MemberExpr* MemberExpr, const MatchFinder::MatchResult&,
117 TransferState<PointerNullabilityLattice>& State) {
118 if (MemberExpr->isArrow()) {
119 // Base expr is a pointer, check that (->) access is safe
120 transferPointerAccess(MemberExpr->getBase(), State);
121 }
122 if (MemberExpr->getType()->isAnyPointerType()) {
123 // Accessed member is a pointer, initialise its nullability
124 initialisePointerNotNullProperty(MemberExpr, State);
125 }
126}
127
Wei Yi Tee543af742022-06-01 06:52:24 -0700128void transferNullCheckComparison(
Wei Yi Tee1cd62af2022-06-09 00:56:46 -0700129 const BinaryOperator* BinaryOp, const MatchFinder::MatchResult& result,
Wei Yi Tee543af742022-06-01 06:52:24 -0700130 TransferState<PointerNullabilityLattice>& State) {
Wei Yi Tee1cd62af2022-06-09 00:56:46 -0700131 // Boolean representing the comparison between the two pointer values,
132 // automatically created by the dataflow framework
133 auto& PointerComparison =
134 *cast<BoolValue>(State.Env.getValue(*BinaryOp, SkipPast::None));
Wei Yi Tee543af742022-06-01 06:52:24 -0700135
Wei Yi Tee1cd62af2022-06-09 00:56:46 -0700136 CHECK(BinaryOp->getOpcode() == BO_EQ || BinaryOp->getOpcode() == BO_NE);
137 auto& PointerEQ = BinaryOp->getOpcode() == BO_EQ
138 ? PointerComparison
139 : State.Env.makeNot(PointerComparison);
140 auto& PointerNE = BinaryOp->getOpcode() == BO_EQ
141 ? State.Env.makeNot(PointerComparison)
142 : PointerComparison;
143
Wei Yi Tee85d87372022-06-09 01:01:35 -0700144 auto& LHSNotNull = getPointerNotNullProperty(BinaryOp->getLHS(), State);
145 auto& RHSNotNull = getPointerNotNullProperty(BinaryOp->getRHS(), State);
Wei Yi Tee1cd62af2022-06-09 00:56:46 -0700146
147 // !LHS && !RHS => LHS == RHS
148 State.Env.addToFlowCondition(State.Env.makeImplication(
Wei Yi Tee85d87372022-06-09 01:01:35 -0700149 State.Env.makeAnd(State.Env.makeNot(LHSNotNull),
150 State.Env.makeNot(RHSNotNull)),
Wei Yi Tee1cd62af2022-06-09 00:56:46 -0700151 PointerEQ));
152 // !LHS && RHS => LHS != RHS
153 State.Env.addToFlowCondition(State.Env.makeImplication(
Wei Yi Tee85d87372022-06-09 01:01:35 -0700154 State.Env.makeAnd(State.Env.makeNot(LHSNotNull), RHSNotNull), PointerNE));
Wei Yi Tee1cd62af2022-06-09 00:56:46 -0700155 // LHS && !RHS => LHS != RHS
156 State.Env.addToFlowCondition(State.Env.makeImplication(
Wei Yi Tee85d87372022-06-09 01:01:35 -0700157 State.Env.makeAnd(LHSNotNull, State.Env.makeNot(RHSNotNull)), PointerNE));
Wei Yi Tee543af742022-06-01 06:52:24 -0700158}
159
160void transferNullCheckImplicitCastPtrToBool(
161 const Expr* CastExpr, const MatchFinder::MatchResult&,
162 TransferState<PointerNullabilityLattice>& State) {
163 if (auto* PointerVal = cast_or_null<PointerValue>(State.Env.getValue(
164 *CastExpr->IgnoreImplicit(), SkipPast::Reference))) {
Wei Yi Tee85d87372022-06-09 01:01:35 -0700165 auto* PointerNotNull = State.Lattice.getPointerNotNullProperty(PointerVal);
166 CHECK(PointerNotNull != nullptr);
Wei Yi Tee543af742022-06-01 06:52:24 -0700167
168 auto& CastExprLoc = State.Env.createStorageLocation(*CastExpr);
Wei Yi Tee85d87372022-06-09 01:01:35 -0700169 State.Env.setValue(CastExprLoc, *PointerNotNull);
Wei Yi Tee543af742022-06-01 06:52:24 -0700170 State.Env.setStorageLocation(*CastExpr, CastExprLoc);
171 }
172}
173
174auto buildTransferer() {
175 return MatchSwitchBuilder<TransferState<PointerNullabilityLattice>>()
Wei Yi Tee1cd62af2022-06-09 00:56:46 -0700176 // Handles initialization of the null states of pointers
Wei Yi Tee85d87372022-06-09 01:01:35 -0700177 .CaseOf<Expr>(isPointerVariableReference(),
Wei Yi Teef02698e2022-06-10 04:25:48 -0700178 transferInitPointerVariableReference)
Wei Yi Teecebc2262022-06-10 04:27:57 -0700179 .CaseOf<Expr>(isCXXThisExpr(), transferInitCXXThisExpr)
Wei Yi Teef02698e2022-06-10 04:25:48 -0700180 // Handles initialization of null states of member pointers and safety of
181 // member access (->) on pointers
182 .CaseOf<MemberExpr>(isMemberExprInvolvingPointers(),
183 transferMemberExprInvolvingPointers)
Wei Yi Tee1cd62af2022-06-09 00:56:46 -0700184 // Handles nullptr
185 .CaseOf<Expr>(isNullPointerLiteral(), transferNullPointerLiteral)
186 // Handles address of operator (&var)
187 .CaseOf<UnaryOperator>(isAddrOf(), transferAddrOf)
188 // Handles pointer dereferencing (*ptr)
Wei Yi Tee543af742022-06-01 06:52:24 -0700189 .CaseOf<UnaryOperator>(isPointerDereference(), transferDereference)
Wei Yi Tee1cd62af2022-06-09 00:56:46 -0700190 // Handles comparison between 2 pointers
191 .CaseOf<BinaryOperator>(isPointerCheckBinOp(),
192 transferNullCheckComparison)
193 // Handles checking of pointer as boolean
194 .CaseOf<Expr>(isImplicitCastPointerToBool(),
Wei Yi Tee543af742022-06-01 06:52:24 -0700195 transferNullCheckImplicitCastPtrToBool)
196 .Build();
197}
198} // namespace
199
200PointerNullabilityAnalysis::PointerNullabilityAnalysis(ASTContext& Context)
201 : DataflowAnalysis<PointerNullabilityAnalysis, PointerNullabilityLattice>(
202 Context),
203 Transferer(buildTransferer()) {}
204
205void PointerNullabilityAnalysis::transfer(const Stmt* Stmt,
206 PointerNullabilityLattice& Lattice,
207 Environment& Env) {
208 TransferState<PointerNullabilityLattice> State(Lattice, Env);
209 Transferer(*Stmt, getASTContext(), State);
210}
211
212bool PointerNullabilityAnalysis::merge(QualType Type, const Value& Val1,
213 const Environment& Env1,
214 const Value& Val2,
215 const Environment& Env2,
216 Value& MergedVal,
217 Environment& MergedEnv) {
218 return false;
219}
220} // namespace nullability
221} // namespace tidy
222} // namespace clang