clang/lib/StaticAnalyzer/Checkers/TrustNonnullChecker.cpp

   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 (auto B=CondS->symbol_begin(), E=CondS->symbol_end(); B != E; ++B) {
  73       const SymbolRef Antecedent = *B;
  74       State = addImplication(Antecedent, State, true);
  75       State = addImplication(Antecedent, State, false);
  76     }
  77
  78     return State;
  79   }
  80
  81   void checkPostCall(const CallEvent &Call, CheckerContext &C) const {
  82     // Only trust annotations for system headers for non-protocols.
  83     if (!Call.isInSystemHeader())
  84       return;
  85
  86     ProgramStateRef State = C.getState();
  87
  88     if (isNonNullPtr(Call, C))
  89       if (auto L = Call.getReturnValue().getAs<Loc>())
  90         State = State->assume(*L, /*assumption=*/true);
  91
  92     C.addTransition(State);
  93   }
  94
  95   void checkPostObjCMessage(const ObjCMethodCall &Msg,
  96                             CheckerContext &C) const {
  97     const ObjCInterfaceDecl *ID = Msg.getReceiverInterface();
  98     if (!ID)
  99       return;
 100
 101     ProgramStateRef State = C.getState();
 102
 103     // Index to setter for NSMutableDictionary is assumed to be non-null,
 104     // as an exception is thrown otherwise.
 105     if (interfaceHasSuperclass(ID, "NSMutableDictionary") &&
 106         (Msg.getSelector() == SetObjectForKeyedSubscriptSel ||
 107          Msg.getSelector() == SetObjectForKeySel)) {
 108       if (auto L = Msg.getArgSVal(1).getAs<Loc>())
 109         State = State->assume(*L, /*assumption=*/true);
 110     }
 111
 112     // Record an implication: index is non-null if the output is non-null.
 113     if (interfaceHasSuperclass(ID, "NSDictionary") &&
 114         (Msg.getSelector() == ObjectForKeyedSubscriptSel ||
 115          Msg.getSelector() == ObjectForKeySel)) {
 116       SymbolRef ArgS = Msg.getArgSVal(0).getAsSymbol();
 117       SymbolRef RetS = Msg.getReturnValue().getAsSymbol();
 118
 119       if (ArgS && RetS) {
 120         // Emulate an implication: the argument is non-null if
 121         // the return value is non-null.
 122         State = State->set<NonNullImplicationMap>(RetS, ArgS);
 123
 124         // Conversely, when the argument is null, the return value
 125         // is definitely null.
 126         State = State->set<NullImplicationMap>(ArgS, RetS);
 127       }
 128     }
 129
 130     C.addTransition(State);
 131   }
 132
 133   void checkDeadSymbols(SymbolReaper &SymReaper, CheckerContext &C) const {
 134     ProgramStateRef State = C.getState();
 135
 136     State = dropDeadFromGDM<NullImplicationMap>(SymReaper, State);
 137     State = dropDeadFromGDM<NonNullImplicationMap>(SymReaper, State);
 138
 139     C.addTransition(State);
 140   }
 141
 142 private:
 143
 144   /// \returns State with GDM \p MapName where all dead symbols were
 145   // removed.
 146   template <typename MapName>
 147   ProgramStateRef dropDeadFromGDM(SymbolReaper &SymReaper,
 148                                   ProgramStateRef State) const {
 149     for (const std::pair<SymbolRef, SymbolRef> &P : State->get<MapName>())
 150       if (!SymReaper.isLive(P.first) || !SymReaper.isLive(P.second))
 151         State = State->remove<MapName>(P.first);
 152     return State;
 153   }
 154
 155   /// \returns Whether we trust the result of the method call to be
 156   /// a non-null pointer.
 157   bool isNonNullPtr(const CallEvent &Call, CheckerContext &C) const {
 158     QualType ExprRetType = Call.getResultType();
 159     if (!ExprRetType->isAnyPointerType())
 160       return false;
 161
 162     if (getNullabilityAnnotation(ExprRetType) == Nullability::Nonnull)
 163       return true;
 164
 165     // The logic for ObjC instance method calls is more complicated,
 166     // as the return value is nil when the receiver is nil.
 167     if (!isa<ObjCMethodCall>(&Call))
 168       return false;
 169
 170     const auto *MCall = cast<ObjCMethodCall>(&Call);
 171     const ObjCMethodDecl *MD = MCall->getDecl();
 172
 173     // Distrust protocols.
 174     if (isa<ObjCProtocolDecl>(MD->getDeclContext()))
 175       return false;
 176
 177     QualType DeclRetType = MD->getReturnType();
 178     if (getNullabilityAnnotation(DeclRetType) != Nullability::Nonnull)
 179       return false;
 180
 181     // For class messages it is sufficient for the declaration to be
 182     // annotated _Nonnull.
 183     if (!MCall->isInstanceMessage())
 184       return true;
 185
 186     // Alternatively, the analyzer could know that the receiver is not null.
 187     SVal Receiver = MCall->getReceiverSVal();
 188     ConditionTruthVal TV = C.getState()->isNonNull(Receiver);
 189     if (TV.isConstrainedTrue())
 190       return true;
 191
 192     return false;
 193   }
 194
 195   /// \return Whether \p ID has a superclass by the name \p ClassName.
 196   bool interfaceHasSuperclass(const ObjCInterfaceDecl *ID,
 197                          StringRef ClassName) const {
 198     if (ID->getIdentifier()->getName() == ClassName)
 199       return true;
 200
 201     if (const ObjCInterfaceDecl *Super = ID->getSuperClass())
 202       return interfaceHasSuperclass(Super, ClassName);
 203
 204     return false;
 205   }
 206
 207
 208   /// \return a state with an optional implication added (if exists)
 209   /// from a map of recorded implications.
 210   /// If \p Negated is true, checks NullImplicationMap, and assumes
 211   /// the negation of \p Antecedent.
 212   /// Checks NonNullImplicationMap and assumes \p Antecedent otherwise.
 213   ProgramStateRef addImplication(SymbolRef Antecedent,
 214                                  ProgramStateRef InputState,
 215                                  bool Negated) const {
 216     if (!InputState)
 217       return nullptr;
 218     SValBuilder &SVB = InputState->getStateManager().getSValBuilder();
 219     const SymbolRef *Consequent =
 220         Negated ? InputState->get<NonNullImplicationMap>(Antecedent)
 221                 : InputState->get<NullImplicationMap>(Antecedent);
 222     if (!Consequent)
 223       return InputState;
 224
 225     SVal AntecedentV = SVB.makeSymbolVal(Antecedent);
 226     ProgramStateRef State = InputState;
 227
 228     if ((Negated && InputState->isNonNull(AntecedentV).isConstrainedTrue())
 229         || (!Negated && InputState->isNull(AntecedentV).isConstrainedTrue())) {
 230       SVal ConsequentS = SVB.makeSymbolVal(*Consequent);
 231       State = InputState->assume(ConsequentS.castAs<DefinedSVal>(), Negated);
 232       if (!State)
 233         return nullptr;
 234
 235       // Drop implications from the map.
 236       if (Negated) {
 237         State = State->remove<NonNullImplicationMap>(Antecedent);
 238         State = State->remove<NullImplicationMap>(*Consequent);
 239       } else {
 240         State = State->remove<NullImplicationMap>(Antecedent);
 241         State = State->remove<NonNullImplicationMap>(*Consequent);
 242       }
 243     }
 244
 245     return State;
 246   }
 247 };
 248
 249 } // end empty namespace
 250
 251 void ento::registerTrustNonnullChecker(CheckerManager &Mgr) {
 252   Mgr.registerChecker<TrustNonnullChecker>(Mgr.getASTContext());
 253 }
 254
 255 bool ento::shouldRegisterTrustNonnullChecker(const CheckerManager &mgr) {
 256   return true;
 257 }