Wei Yi Tee | 543af74 | 2022-06-01 06:52:24 -0700 | [diff] [blame] | 1 | // 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 Tee | 543af74 | 2022-06-01 06:52:24 -0700 | [diff] [blame] | 7 | #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 Tee | 1cd62af | 2022-06-09 00:56:46 -0700 | [diff] [blame] | 14 | #include "clang/AST/OperationKinds.h" |
| 15 | #include "clang/AST/Stmt.h" |
| 16 | #include "clang/AST/Type.h" |
Wei Yi Tee | 543af74 | 2022-06-01 06:52:24 -0700 | [diff] [blame] | 17 | #include "clang/ASTMatchers/ASTMatchFinder.h" |
Wei Yi Tee | 543af74 | 2022-06-01 06:52:24 -0700 | [diff] [blame] | 18 | #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 | |
| 23 | namespace clang { |
| 24 | namespace tidy { |
| 25 | namespace nullability { |
| 26 | |
| 27 | using ast_matchers::MatchFinder; |
| 28 | using dataflow::BoolValue; |
| 29 | using dataflow::Environment; |
| 30 | using dataflow::MatchSwitchBuilder; |
| 31 | using dataflow::PointerValue; |
| 32 | using dataflow::SkipPast; |
| 33 | using dataflow::TransferState; |
| 34 | using dataflow::Value; |
| 35 | |
| 36 | namespace { |
| 37 | |
Wei Yi Tee | 85d8737 | 2022-06-09 01:01:35 -0700 | [diff] [blame] | 38 | BoolValue& getPointerNotNullProperty( |
Wei Yi Tee | 1cd62af | 2022-06-09 00:56:46 -0700 | [diff] [blame] | 39 | const Expr* PointerExpr, TransferState<PointerNullabilityLattice>& State) { |
| 40 | auto* PointerVal = |
| 41 | cast<PointerValue>(State.Env.getValue(*PointerExpr, SkipPast::Reference)); |
Wei Yi Tee | 85d8737 | 2022-06-09 01:01:35 -0700 | [diff] [blame] | 42 | CHECK(State.Lattice.hasPointerNotNullProperty(PointerVal)); |
| 43 | return *State.Lattice.getPointerNotNullProperty(PointerVal); |
Wei Yi Tee | 1cd62af | 2022-06-09 00:56:46 -0700 | [diff] [blame] | 44 | } |
| 45 | |
Wei Yi Tee | 85d8737 | 2022-06-09 01:01:35 -0700 | [diff] [blame] | 46 | void initialisePointerNotNullProperty( |
Wei Yi Tee | cebc226 | 2022-06-10 04:27:57 -0700 | [diff] [blame] | 47 | const Expr* PointerExpr, TransferState<PointerNullabilityLattice>& State, |
| 48 | BoolValue* NotNullProperty = nullptr) { |
Wei Yi Tee | 543af74 | 2022-06-01 06:52:24 -0700 | [diff] [blame] | 49 | if (auto* PointerVal = cast_or_null<PointerValue>( |
Wei Yi Tee | f02698e | 2022-06-10 04:25:48 -0700 | [diff] [blame] | 50 | State.Env.getValue(*PointerExpr, SkipPast::Reference))) { |
Wei Yi Tee | 85d8737 | 2022-06-09 01:01:35 -0700 | [diff] [blame] | 51 | if (!State.Lattice.hasPointerNotNullProperty(PointerVal)) { |
Wei Yi Tee | cebc226 | 2022-06-10 04:27:57 -0700 | [diff] [blame] | 52 | State.Lattice.setPointerNotNullProperty( |
| 53 | PointerVal, |
| 54 | NotNullProperty ? NotNullProperty : &State.Env.makeAtomicBoolValue()); |
Wei Yi Tee | 543af74 | 2022-06-01 06:52:24 -0700 | [diff] [blame] | 55 | } |
| 56 | } |
| 57 | } |
| 58 | |
Wei Yi Tee | f02698e | 2022-06-10 04:25:48 -0700 | [diff] [blame] | 59 | void transferInitPointerVariableReference( |
Wei Yi Tee | cebc226 | 2022-06-10 04:27:57 -0700 | [diff] [blame] | 60 | const Expr* PointerExpr, const MatchFinder::MatchResult&, |
Wei Yi Tee | f02698e | 2022-06-10 04:25:48 -0700 | [diff] [blame] | 61 | TransferState<PointerNullabilityLattice>& State) { |
Wei Yi Tee | cebc226 | 2022-06-10 04:27:57 -0700 | [diff] [blame] | 62 | initialisePointerNotNullProperty(PointerExpr, State); |
| 63 | } |
| 64 | |
| 65 | void transferInitCXXThisExpr(const Expr* ThisExpr, |
| 66 | const MatchFinder::MatchResult&, |
| 67 | TransferState<PointerNullabilityLattice>& State) { |
| 68 | initialisePointerNotNullProperty(ThisExpr, State, |
| 69 | &State.Env.getBoolLiteralValue(true)); |
Wei Yi Tee | f02698e | 2022-06-10 04:25:48 -0700 | [diff] [blame] | 70 | } |
| 71 | |
Wei Yi Tee | 1cd62af | 2022-06-09 00:56:46 -0700 | [diff] [blame] | 72 | void 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 Tee | 85d8737 | 2022-06-09 01:01:35 -0700 | [diff] [blame] | 85 | if (!State.Lattice.hasPointerNotNullProperty(NullPointerVal)) { |
Wei Yi Tee | 1cd62af | 2022-06-09 00:56:46 -0700 | [diff] [blame] | 86 | // Set null pointer to be known null if not already set |
Wei Yi Tee | 85d8737 | 2022-06-09 01:01:35 -0700 | [diff] [blame] | 87 | State.Lattice.setPointerNotNullProperty( |
| 88 | NullPointerVal, &State.Env.getBoolLiteralValue(false)); |
Wei Yi Tee | 1cd62af | 2022-06-09 00:56:46 -0700 | [diff] [blame] | 89 | } |
| 90 | } |
| 91 | |
| 92 | void 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 Tee | 85d8737 | 2022-06-09 01:01:35 -0700 | [diff] [blame] | 97 | State.Lattice.setPointerNotNullProperty(PointerVal, |
| 98 | &State.Env.getBoolLiteralValue(true)); |
Wei Yi Tee | 1cd62af | 2022-06-09 00:56:46 -0700 | [diff] [blame] | 99 | } |
| 100 | |
Wei Yi Tee | f02698e | 2022-06-10 04:25:48 -0700 | [diff] [blame] | 101 | void transferPointerAccess(const Expr* PointerExpr, |
| 102 | TransferState<PointerNullabilityLattice>& State) { |
Wei Yi Tee | 85d8737 | 2022-06-09 01:01:35 -0700 | [diff] [blame] | 103 | auto& PointerNotNull = getPointerNotNullProperty(PointerExpr, State); |
| 104 | if (!State.Env.flowConditionImplies(PointerNotNull)) { |
Wei Yi Tee | 1cd62af | 2022-06-09 00:56:46 -0700 | [diff] [blame] | 105 | State.Lattice.addViolation(PointerExpr); |
Wei Yi Tee | 543af74 | 2022-06-01 06:52:24 -0700 | [diff] [blame] | 106 | } |
Wei Yi Tee | 543af74 | 2022-06-01 06:52:24 -0700 | [diff] [blame] | 107 | } |
| 108 | |
Wei Yi Tee | f02698e | 2022-06-10 04:25:48 -0700 | [diff] [blame] | 109 | void transferDereference(const UnaryOperator* UnaryOp, |
| 110 | const MatchFinder::MatchResult&, |
| 111 | TransferState<PointerNullabilityLattice>& State) { |
| 112 | transferPointerAccess(UnaryOp->getSubExpr(), State); |
| 113 | } |
| 114 | |
| 115 | void 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 Tee | 543af74 | 2022-06-01 06:52:24 -0700 | [diff] [blame] | 128 | void transferNullCheckComparison( |
Wei Yi Tee | 1cd62af | 2022-06-09 00:56:46 -0700 | [diff] [blame] | 129 | const BinaryOperator* BinaryOp, const MatchFinder::MatchResult& result, |
Wei Yi Tee | 543af74 | 2022-06-01 06:52:24 -0700 | [diff] [blame] | 130 | TransferState<PointerNullabilityLattice>& State) { |
Wei Yi Tee | 1cd62af | 2022-06-09 00:56:46 -0700 | [diff] [blame] | 131 | // 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 Tee | 543af74 | 2022-06-01 06:52:24 -0700 | [diff] [blame] | 135 | |
Wei Yi Tee | 1cd62af | 2022-06-09 00:56:46 -0700 | [diff] [blame] | 136 | 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 Tee | 85d8737 | 2022-06-09 01:01:35 -0700 | [diff] [blame] | 144 | auto& LHSNotNull = getPointerNotNullProperty(BinaryOp->getLHS(), State); |
| 145 | auto& RHSNotNull = getPointerNotNullProperty(BinaryOp->getRHS(), State); |
Wei Yi Tee | 1cd62af | 2022-06-09 00:56:46 -0700 | [diff] [blame] | 146 | |
| 147 | // !LHS && !RHS => LHS == RHS |
| 148 | State.Env.addToFlowCondition(State.Env.makeImplication( |
Wei Yi Tee | 85d8737 | 2022-06-09 01:01:35 -0700 | [diff] [blame] | 149 | State.Env.makeAnd(State.Env.makeNot(LHSNotNull), |
| 150 | State.Env.makeNot(RHSNotNull)), |
Wei Yi Tee | 1cd62af | 2022-06-09 00:56:46 -0700 | [diff] [blame] | 151 | PointerEQ)); |
| 152 | // !LHS && RHS => LHS != RHS |
| 153 | State.Env.addToFlowCondition(State.Env.makeImplication( |
Wei Yi Tee | 85d8737 | 2022-06-09 01:01:35 -0700 | [diff] [blame] | 154 | State.Env.makeAnd(State.Env.makeNot(LHSNotNull), RHSNotNull), PointerNE)); |
Wei Yi Tee | 1cd62af | 2022-06-09 00:56:46 -0700 | [diff] [blame] | 155 | // LHS && !RHS => LHS != RHS |
| 156 | State.Env.addToFlowCondition(State.Env.makeImplication( |
Wei Yi Tee | 85d8737 | 2022-06-09 01:01:35 -0700 | [diff] [blame] | 157 | State.Env.makeAnd(LHSNotNull, State.Env.makeNot(RHSNotNull)), PointerNE)); |
Wei Yi Tee | 543af74 | 2022-06-01 06:52:24 -0700 | [diff] [blame] | 158 | } |
| 159 | |
| 160 | void 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 Tee | 85d8737 | 2022-06-09 01:01:35 -0700 | [diff] [blame] | 165 | auto* PointerNotNull = State.Lattice.getPointerNotNullProperty(PointerVal); |
| 166 | CHECK(PointerNotNull != nullptr); |
Wei Yi Tee | 543af74 | 2022-06-01 06:52:24 -0700 | [diff] [blame] | 167 | |
| 168 | auto& CastExprLoc = State.Env.createStorageLocation(*CastExpr); |
Wei Yi Tee | 85d8737 | 2022-06-09 01:01:35 -0700 | [diff] [blame] | 169 | State.Env.setValue(CastExprLoc, *PointerNotNull); |
Wei Yi Tee | 543af74 | 2022-06-01 06:52:24 -0700 | [diff] [blame] | 170 | State.Env.setStorageLocation(*CastExpr, CastExprLoc); |
| 171 | } |
| 172 | } |
| 173 | |
| 174 | auto buildTransferer() { |
| 175 | return MatchSwitchBuilder<TransferState<PointerNullabilityLattice>>() |
Wei Yi Tee | 1cd62af | 2022-06-09 00:56:46 -0700 | [diff] [blame] | 176 | // Handles initialization of the null states of pointers |
Wei Yi Tee | 85d8737 | 2022-06-09 01:01:35 -0700 | [diff] [blame] | 177 | .CaseOf<Expr>(isPointerVariableReference(), |
Wei Yi Tee | f02698e | 2022-06-10 04:25:48 -0700 | [diff] [blame] | 178 | transferInitPointerVariableReference) |
Wei Yi Tee | cebc226 | 2022-06-10 04:27:57 -0700 | [diff] [blame] | 179 | .CaseOf<Expr>(isCXXThisExpr(), transferInitCXXThisExpr) |
Wei Yi Tee | f02698e | 2022-06-10 04:25:48 -0700 | [diff] [blame] | 180 | // Handles initialization of null states of member pointers and safety of |
| 181 | // member access (->) on pointers |
| 182 | .CaseOf<MemberExpr>(isMemberExprInvolvingPointers(), |
| 183 | transferMemberExprInvolvingPointers) |
Wei Yi Tee | 1cd62af | 2022-06-09 00:56:46 -0700 | [diff] [blame] | 184 | // 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 Tee | 543af74 | 2022-06-01 06:52:24 -0700 | [diff] [blame] | 189 | .CaseOf<UnaryOperator>(isPointerDereference(), transferDereference) |
Wei Yi Tee | 1cd62af | 2022-06-09 00:56:46 -0700 | [diff] [blame] | 190 | // Handles comparison between 2 pointers |
| 191 | .CaseOf<BinaryOperator>(isPointerCheckBinOp(), |
| 192 | transferNullCheckComparison) |
| 193 | // Handles checking of pointer as boolean |
| 194 | .CaseOf<Expr>(isImplicitCastPointerToBool(), |
Wei Yi Tee | 543af74 | 2022-06-01 06:52:24 -0700 | [diff] [blame] | 195 | transferNullCheckImplicitCastPtrToBool) |
| 196 | .Build(); |
| 197 | } |
| 198 | } // namespace |
| 199 | |
| 200 | PointerNullabilityAnalysis::PointerNullabilityAnalysis(ASTContext& Context) |
| 201 | : DataflowAnalysis<PointerNullabilityAnalysis, PointerNullabilityLattice>( |
| 202 | Context), |
| 203 | Transferer(buildTransferer()) {} |
| 204 | |
| 205 | void PointerNullabilityAnalysis::transfer(const Stmt* Stmt, |
| 206 | PointerNullabilityLattice& Lattice, |
| 207 | Environment& Env) { |
| 208 | TransferState<PointerNullabilityLattice> State(Lattice, Env); |
| 209 | Transferer(*Stmt, getASTContext(), State); |
| 210 | } |
| 211 | |
| 212 | bool 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 |