1 //== TrustNonnullChecker.cpp --------- API nullability modeling -*- C++ -*--==//
2 //
3 // Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.
4 // See https://llvm.org/LICENSE.txt for license information.
5 // SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception
6 //
7 //===----------------------------------------------------------------------===//
8 //
9 // This checker adds nullability-related assumptions:
10 //
11 // 1. Methods annotated with _Nonnull
12 // which come from system headers actually return a non-null pointer.
13 //
14 // 2. NSDictionary key is non-null after the keyword subscript operation
15 // on read if and only if the resulting expression is non-null.
16 //
17 // 3. NSMutableDictionary index is non-null after a write operation.
18 //
19 //===----------------------------------------------------------------------===//
20 
21 #include "clang/StaticAnalyzer/Checkers/BuiltinCheckerRegistration.h"
22 #include "clang/Analysis/SelectorExtras.h"
23 #include "clang/StaticAnalyzer/Core/Checker.h"
24 #include "clang/StaticAnalyzer/Core/CheckerManager.h"
25 #include "clang/StaticAnalyzer/Core/PathSensitive/CheckerContext.h"
26 #include "clang/StaticAnalyzer/Core/PathSensitive/CheckerHelpers.h"
27 #include "clang/StaticAnalyzer/Core/PathSensitive/CallEvent.h"
28 
29 using namespace clang;
30 using namespace ento;
31 
32 /// Records implications between symbols.
33 /// The semantics is:
34 ///    (antecedent != 0) => (consequent != 0)
35 /// These implications are then read during the evaluation of the assumption,
36 /// and the appropriate antecedents are applied.
37 REGISTER_MAP_WITH_PROGRAMSTATE(NonNullImplicationMap, SymbolRef, SymbolRef)
38 
39 /// The semantics is:
40 ///    (antecedent == 0) => (consequent == 0)
41 REGISTER_MAP_WITH_PROGRAMSTATE(NullImplicationMap, SymbolRef, SymbolRef)
42 
43 namespace {
44 
45 class TrustNonnullChecker : public Checker<check::PostCall,
46                                            check::PostObjCMessage,
47                                            check::DeadSymbols,
48                                            eval::Assume> {
49   // Do not try to iterate over symbols with higher complexity.
50   static unsigned constexpr ComplexityThreshold = 10;
51   Selector ObjectForKeyedSubscriptSel;
52   Selector ObjectForKeySel;
53   Selector SetObjectForKeyedSubscriptSel;
54   Selector SetObjectForKeySel;
55 
56 public:
57   TrustNonnullChecker(ASTContext &Ctx)
58       : ObjectForKeyedSubscriptSel(
59             getKeywordSelector(Ctx, "objectForKeyedSubscript")),
60         ObjectForKeySel(getKeywordSelector(Ctx, "objectForKey")),
61         SetObjectForKeyedSubscriptSel(
62             getKeywordSelector(Ctx, "setObject", "forKeyedSubscript")),
63         SetObjectForKeySel(getKeywordSelector(Ctx, "setObject", "forKey")) {}
64 
65   ProgramStateRef evalAssume(ProgramStateRef State,
66                              SVal Cond,
67                              bool Assumption) const {
68     const SymbolRef CondS = Cond.getAsSymbol();
69     if (!CondS || CondS->computeComplexity() > ComplexityThreshold)
70       return State;
71 
72     for (SymbolRef Antecedent : CondS->symbols()) {
73       State = addImplication(Antecedent, State, true);
74       State = addImplication(Antecedent, State, false);
75     }
76 
77     return State;
78   }
79 
80   void checkPostCall(const CallEvent &Call, CheckerContext &C) const {
81     // Only trust annotations for system headers for non-protocols.
82     if (!Call.isInSystemHeader())
83       return;
84 
85     ProgramStateRef State = C.getState();
86 
87     if (isNonNullPtr(Call, C))
88       if (auto L = Call.getReturnValue().getAs<Loc>())
89         State = State->assume(*L, /*assumption=*/true);
90 
91     C.addTransition(State);
92   }
93 
94   void checkPostObjCMessage(const ObjCMethodCall &Msg,
95                             CheckerContext &C) const {
96     const ObjCInterfaceDecl *ID = Msg.getReceiverInterface();
97     if (!ID)
98       return;
99 
100     ProgramStateRef State = C.getState();
101 
102     // Index to setter for NSMutableDictionary is assumed to be non-null,
103     // as an exception is thrown otherwise.
104     if (interfaceHasSuperclass(ID, "NSMutableDictionary") &&
105         (Msg.getSelector() == SetObjectForKeyedSubscriptSel ||
106          Msg.getSelector() == SetObjectForKeySel)) {
107       if (auto L = Msg.getArgSVal(1).getAs<Loc>())
108         State = State->assume(*L, /*assumption=*/true);
109     }
110 
111     // Record an implication: index is non-null if the output is non-null.
112     if (interfaceHasSuperclass(ID, "NSDictionary") &&
113         (Msg.getSelector() == ObjectForKeyedSubscriptSel ||
114          Msg.getSelector() == ObjectForKeySel)) {
115       SymbolRef ArgS = Msg.getArgSVal(0).getAsSymbol();
116       SymbolRef RetS = Msg.getReturnValue().getAsSymbol();
117 
118       if (ArgS && RetS) {
119         // Emulate an implication: the argument is non-null if
120         // the return value is non-null.
121         State = State->set<NonNullImplicationMap>(RetS, ArgS);
122 
123         // Conversely, when the argument is null, the return value
124         // is definitely null.
125         State = State->set<NullImplicationMap>(ArgS, RetS);
126       }
127     }
128 
129     C.addTransition(State);
130   }
131 
132   void checkDeadSymbols(SymbolReaper &SymReaper, CheckerContext &C) const {
133     ProgramStateRef State = C.getState();
134 
135     State = dropDeadFromGDM<NullImplicationMap>(SymReaper, State);
136     State = dropDeadFromGDM<NonNullImplicationMap>(SymReaper, State);
137 
138     C.addTransition(State);
139   }
140 
141 private:
142 
143   /// \returns State with GDM \p MapName where all dead symbols were
144   // removed.
145   template <typename MapName>
146   ProgramStateRef dropDeadFromGDM(SymbolReaper &SymReaper,
147                                   ProgramStateRef State) const {
148     for (const std::pair<SymbolRef, SymbolRef> &P : State->get<MapName>())
149       if (!SymReaper.isLive(P.first) || !SymReaper.isLive(P.second))
150         State = State->remove<MapName>(P.first);
151     return State;
152   }
153 
154   /// \returns Whether we trust the result of the method call to be
155   /// a non-null pointer.
156   bool isNonNullPtr(const CallEvent &Call, CheckerContext &C) const {
157     QualType ExprRetType = Call.getResultType();
158     if (!ExprRetType->isAnyPointerType())
159       return false;
160 
161     if (getNullabilityAnnotation(ExprRetType) == Nullability::Nonnull)
162       return true;
163 
164     // The logic for ObjC instance method calls is more complicated,
165     // as the return value is nil when the receiver is nil.
166     if (!isa<ObjCMethodCall>(&Call))
167       return false;
168 
169     const auto *MCall = cast<ObjCMethodCall>(&Call);
170     const ObjCMethodDecl *MD = MCall->getDecl();
171 
172     // Distrust protocols.
173     if (isa<ObjCProtocolDecl>(MD->getDeclContext()))
174       return false;
175 
176     QualType DeclRetType = MD->getReturnType();
177     if (getNullabilityAnnotation(DeclRetType) != Nullability::Nonnull)
178       return false;
179 
180     // For class messages it is sufficient for the declaration to be
181     // annotated _Nonnull.
182     if (!MCall->isInstanceMessage())
183       return true;
184 
185     // Alternatively, the analyzer could know that the receiver is not null.
186     SVal Receiver = MCall->getReceiverSVal();
187     ConditionTruthVal TV = C.getState()->isNonNull(Receiver);
188     if (TV.isConstrainedTrue())
189       return true;
190 
191     return false;
192   }
193 
194   /// \return Whether \p ID has a superclass by the name \p ClassName.
195   bool interfaceHasSuperclass(const ObjCInterfaceDecl *ID,
196                          StringRef ClassName) const {
197     if (ID->getIdentifier()->getName() == ClassName)
198       return true;
199 
200     if (const ObjCInterfaceDecl *Super = ID->getSuperClass())
201       return interfaceHasSuperclass(Super, ClassName);
202 
203     return false;
204   }
205 
206 
207   /// \return a state with an optional implication added (if exists)
208   /// from a map of recorded implications.
209   /// If \p Negated is true, checks NullImplicationMap, and assumes
210   /// the negation of \p Antecedent.
211   /// Checks NonNullImplicationMap and assumes \p Antecedent otherwise.
212   ProgramStateRef addImplication(SymbolRef Antecedent,
213                                  ProgramStateRef InputState,
214                                  bool Negated) const {
215     if (!InputState)
216       return nullptr;
217     SValBuilder &SVB = InputState->getStateManager().getSValBuilder();
218     const SymbolRef *Consequent =
219         Negated ? InputState->get<NonNullImplicationMap>(Antecedent)
220                 : InputState->get<NullImplicationMap>(Antecedent);
221     if (!Consequent)
222       return InputState;
223 
224     SVal AntecedentV = SVB.makeSymbolVal(Antecedent);
225     ProgramStateRef State = InputState;
226 
227     if ((Negated && InputState->isNonNull(AntecedentV).isConstrainedTrue())
228         || (!Negated && InputState->isNull(AntecedentV).isConstrainedTrue())) {
229       SVal ConsequentS = SVB.makeSymbolVal(*Consequent);
230       State = InputState->assume(ConsequentS.castAs<DefinedSVal>(), Negated);
231       if (!State)
232         return nullptr;
233 
234       // Drop implications from the map.
235       if (Negated) {
236         State = State->remove<NonNullImplicationMap>(Antecedent);
237         State = State->remove<NullImplicationMap>(*Consequent);
238       } else {
239         State = State->remove<NullImplicationMap>(Antecedent);
240         State = State->remove<NonNullImplicationMap>(*Consequent);
241       }
242     }
243 
244     return State;
245   }
246 };
247 
248 } // end empty namespace
249 
250 void ento::registerTrustNonnullChecker(CheckerManager &Mgr) {
251   Mgr.registerChecker<TrustNonnullChecker>(Mgr.getASTContext());
252 }
253 
254 bool ento::shouldRegisterTrustNonnullChecker(const CheckerManager &mgr) {
255   return true;
256 }
257