contrib/llvm/tools/clang/lib/StaticAnalyzer/Checkers/TrustNonnullChecker.cpp

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