[analyzer] Record nullability implications on getting items from NSDictionary

[george.karpenkov]

Summary

If we get an item from a dictionary, we know that the item is non-null if and only if the key is non-null.

This patch is a rather hacky way to record this implication, because some logic needs to be duplicated from the solver.
And yet, it's pretty simple, performant, and works.

Other possible approaches:

• Record the implication, in future rely on Z3 to pick it up.
• Generalize the current code and move it to the constraint manager.

rdar://34990742

[dcoughlin]

clang/lib/StaticAnalyzer/Checkers/TrustNonnullChecker.cpp

15

"index" --> "key". In Foundation "index" refers to an array index.

33

I think future maintainers would find it helpful it you provided a prose description of the meaning of the data structure here. Something like: "Records an implication about non nullness between symbols. If the key symbol is constrained to be not null then the value symbol will be constrained to be not null as well."

90

It would be good to handle -[NSMutableDictionary setObject:forKey:] here as well. There is a ridiculous amount of code that uses it since the subscript syntax is relatively new.

For the same reason, we should also handle -[NSDictionary objectForKey:] below.

96

Can you explain why this is an if-and-only-if?

In particular, it seems to me that if the key is not null but is not present in the dictionary then the output will be null.

205

I suspect future maintainers would appreciate a more detailed comment about how this causes infinite recursion and how removing the mapping avoids it.

clang/test/Analysis/analyzer-config.cpp

43

What's this about?

[george.karpenkov]

clang/lib/StaticAnalyzer/Checkers/TrustNonnullChecker.cpp

96

The comment is outdated and wrong, will fix

[george.karpenkov]

clang/test/Analysis/analyzer-config.cpp

43

@NoQ would probably want to correct me here, but last time he explained it to me, the configuration dumping is not actually guaranteed to work, and unrelated changes may cause previous (for some reason unshown) changes to propagate. I'm still not sure exactly why.

[NoQ]

clang/test/Analysis/analyzer-config.cpp

43

It means that the provided test now covers a call to shouldIncludeAllocationSiteInLeakDiagnostics(). Which changes the previously not-present key in the analyzer options map to become set to the default value.

It is impossible to list all values in the analyzer options map because they aren't just listed there until they're used. Which is why this test file has some actual code: to trigger reads from the map.

But i've no idea why specifically this code suddenly starts triggering this specific option to be read.

[NoQ]

clang/lib/StaticAnalyzer/Checkers/TrustNonnullChecker.cpp

1

British vs. American English thing.

63–66

Is there anything that prevents us from reducing this method to something like

for (Antecedent in Cond) { // symbol_iterator thingy
  if (SymbolRef Consequent = State->get<ImplicationMap>(Antecedent)) {
    if (State->isNull(Antecedent).isConstrainedTrue()) // somehow avoid infinite recursion
      return State->remove<ImplicationMap>(Antecedent)->assume(Consequent, false);
    if (State->isNull(Antecedent).isConstrainedFalse())
      return State->remove<ImplicationMap>(Antecedent)->assume(Consequent, true);
  }
}

?

[NoQ]

clang/lib/StaticAnalyzer/Checkers/TrustNonnullChecker.cpp

41

<=

136–143

I think there should be at most two remove<>s per dead symbol.

Also because the dead set is deprecated and we plan to remove it, maybe iterate over the map instead?

203

Should we clean both maps up immediately?

[george.karpenkov]

clang/lib/StaticAnalyzer/Checkers/TrustNonnullChecker.cpp

41

Nope, the direction is correct here, assuming antecedent is the key, and consequent is the value

[NoQ]

clang/lib/StaticAnalyzer/Checkers/TrustNonnullChecker.cpp

41

Mmm, aha, ok.

[NoQ]

I hope eventually we'll be able to reduce this code to a single assume() directive.

clang/lib/StaticAnalyzer/Checkers/TrustNonnullChecker.cpp

-//== TrustNonnullChecker.cpp - Checker for trusting annotations -*- C++ -*--==//
+//== TrustNonnullChecker.cpp -------- API nullability modelling -*- C++ -*--==//
 //
 //                     The LLVM Compiler Infrastructure
 //
 // This file is distributed under the University of Illinois Open Source
 // License. See LICENSE.TXT for details.
 //
 //===----------------------------------------------------------------------===//
 //
-// This checker adds an assumption that methods annotated with _Nonnull
+// This checker adds nullability-related assumptions:
+//
+// 1. Methods annotated with _Nonnull
 // which come from system headers actually return a non-null pointer.
 //
+// 2. NSDictionary key is non-null after the keyword subscript operation
+// on read if and only if the resulting expression is non-null.
+//
+// 3. NSMutableDictionary index is non-null after a write operation.
+//
 //===----------------------------------------------------------------------===//
 
 #include "ClangSACheckers.h"
+#include "SelectorExtras.h"
 #include "clang/StaticAnalyzer/Core/Checker.h"
 #include "clang/StaticAnalyzer/Core/CheckerManager.h"
 #include "clang/StaticAnalyzer/Core/PathSensitive/CheckerContext.h"
 #include "clang/StaticAnalyzer/Core/PathSensitive/CheckerHelpers.h"
 #include "clang/StaticAnalyzer/Core/PathSensitive/CallEvent.h"
 
 using namespace clang;
 using namespace ento;
 
+/// Records implications between symbols.
+/// The semantics is:
+///    (key != 0) => (value != 0)
+/// These implications are then read during the evaluation of the assumption,
+/// and the appropriate antecedents are applied.
+REGISTER_MAP_WITH_PROGRAMSTATE(ImplicationMap, SymbolRef, SymbolRef)
+
 namespace {
 
-class TrustNonnullChecker : public Checker<check::PostCall> {
+class TrustNonnullChecker : public Checker<check::PostCall,
+                                           check::PostObjCMessage,
+                                           check::DeadSymbols,
+                                           eval::Assume> {
+  Selector ObjectForKeyedSubscriptSel;
+  Selector ObjectForKeySel;
+  Selector SetObjectForKeyedSubscriptSel;
+  Selector SetObjectForKeySel;
+
+public:
+  TrustNonnullChecker(ASTContext &Ctx)
+      : ObjectForKeyedSubscriptSel(
+            getKeywordSelector(Ctx, "objectForKeyedSubscript")),
+        ObjectForKeySel(getKeywordSelector(Ctx, "objectForKey")),
+        SetObjectForKeyedSubscriptSel(
+            getKeywordSelector(Ctx, "setObject", "forKeyedSubscript")),
+        SetObjectForKeySel(getKeywordSelector(Ctx, "setObject", "forKey")) {}
+
+  ProgramStateRef evalAssume(ProgramStateRef State,
+                             SVal Cond,
+                             bool Assumption) const {
+    if (const SymbolRef Antecedent = Cond.getAsSymbol())
+      State = addConsequentForCheck(State, Antecedent, Assumption);
+
+    return State;
+  }
+
+  void checkPostCall(const CallEvent &Call, CheckerContext &C) const {
+    // Only trust annotations for system headers for non-protocols.
+    if (!Call.isInSystemHeader())
+      return;
+
+    ProgramStateRef State = C.getState();
+
+    if (isNonNullPtr(Call, C))
+      if (auto L = Call.getReturnValue().getAs<Loc>())
+        State = State->assume(*L, /*Assumption=*/true);
+
+    C.addTransition(State);
+  }
+
+  void checkPostObjCMessage(const ObjCMethodCall &Msg,
+                            CheckerContext &C) const {
+    const ObjCInterfaceDecl *ID = Msg.getReceiverInterface();
+    if (!ID)
+      return;
+
+    ProgramStateRef State = C.getState();
+
+    // Index to setter for NSMutableDictionary is assumed to be non-null,
+    // as an exception is thrown otherwise.
+    if (interfaceHasSuperclass(ID, "NSMutableDictionary") &&
+        (Msg.getSelector() == SetObjectForKeyedSubscriptSel ||
+         Msg.getSelector() == SetObjectForKeySel)) {
+      if (auto L = Msg.getArgSVal(1).getAs<Loc>())
+        State = State->assume(*L, /*Assumption=*/true);
+    }
+
+    // Record an implication: index is non-null if the output is non-null.
+    if (interfaceHasSuperclass(ID, "NSDictionary") &&
+        (Msg.getSelector() == ObjectForKeyedSubscriptSel ||
+         Msg.getSelector() == ObjectForKeySel)) {
+      SymbolRef ArgS = Msg.getArgSVal(0).getAsSymbol();
+      SymbolRef RetS = Msg.getReturnValue().getAsSymbol();
+
+      // Emulate an implication: the argument is non-null if
+      // the return value is non-null.
+      if (ArgS && RetS)
+        State = State->set<ImplicationMap>(RetS, ArgS);
+    }
+
+    C.addTransition(State);
+  }
+
+  void checkDeadSymbols(SymbolReaper &SymReaper, CheckerContext &C) const {
+    ProgramStateRef State = C.getState();
+
+    // Remove the implication if either symbol is dead.
+    for (SymbolReaper::dead_iterator I = SymReaper.dead_begin(),
+         E = SymReaper.dead_end(); I != E; ++I) {
+      if (const SymbolRef *SImpl = State->get<ImplicationMap>(*I))
+        State = State->remove<ImplicationMap>(*SImpl);
+
+      State = State->remove<ImplicationMap>(*I);
+    }
+    C.addTransition(State);
+  }
+
 private:
   /// \returns Whether we trust the result of the method call to be
   /// a non-null pointer.
   bool isNonNullPtr(const CallEvent &Call, CheckerContext &C) const {
     QualType ExprRetType = Call.getResultType();
     if (!ExprRetType->isAnyPointerType())
       return false;
 
     if (getNullabilityAnnotation(ExprRetType) == Nullability::Nonnull)
       return true;
 
     // The logic for ObjC instance method calls is more complicated,
     // as the return value is nil when the receiver is nil.
     if (!isa<ObjCMethodCall>(&Call))
       return false;
 
     const auto *MCall = cast<ObjCMethodCall>(&Call);
     const ObjCMethodDecl *MD = MCall->getDecl();
 
     // Distrust protocols.
     if (isa<ObjCProtocolDecl>(MD->getDeclContext()))
       return false;
bool isNonNullPtr(const CallEvent &Call, CheckerContext &C) const {
     SVal Receiver = MCall->getReceiverSVal();
     ConditionTruthVal TV = C.getState()->isNonNull(Receiver);
     if (TV.isConstrainedTrue())
       return true;
 
     return false;
   }
 
-public:
-  void checkPostCall(const CallEvent &Call, CheckerContext &C) const {
-    // Only trust annotations for system headers for non-protocols.
-    if (!Call.isInSystemHeader())
-      return;
+  /// \return Whether \p ID has a superclass by the name \p ClassName.
+  bool interfaceHasSuperclass(const ObjCInterfaceDecl *ID,
+                         StringRef ClassName) const {
+    if (ID->getIdentifier()->getName() == ClassName)
+      return true;
 
-    ProgramStateRef State = C.getState();
+    if (const ObjCInterfaceDecl *Super = ID->getSuperClass())
+      return interfaceHasSuperclass(Super, ClassName);
 
-    if (isNonNullPtr(Call, C))
-      if (auto L = Call.getReturnValue().getAs<Loc>())
-        State = State->assume(*L, /*Assumption=*/true);
+    return false;
+  }
 
-    C.addTransition(State);
+
+  /// Add assumptions resulting from stored implications.
+  /// Implication semantics:
+  ///    (antecedent != 0) => (consequent != 0)
+  ProgramStateRef addConsequentForCheck(ProgramStateRef State,
+                                            SymbolRef Antecedent,
+                                            bool Assumption) const {
+    SValBuilder &SVB = State->getStateManager().getSValBuilder();
+
+    // Parse comparison to zero.
+    if (const SymIntExpr *SIE = dyn_cast<SymIntExpr>(Antecedent))
+      return matchNonNullComparision(State,
+                                     SIE->getOpcode(),
+                                     SIE->getLHS(), SIE->getRHS(), Assumption);
+
+    if (const IntSymExpr *ISE = dyn_cast<IntSymExpr>(Antecedent))
+      return matchNonNullComparision(State,
+                                     ISE->getOpcode(),
+                                     ISE->getRHS(), ISE->getLHS(), Assumption);
+
+    if (const SymbolRef *Consequent = State->get<ImplicationMap>(Antecedent)) {
+
+      // Note that the "assume" call below is recursive and calls this method
+      // again. We are removing the implication from map
+      // first to avoid infinite recursion.
+      State = State->remove<ImplicationMap>(Antecedent);
+      SVal ConsequentS = SVB.makeSymbolVal(*Consequent);
+      State = State->assume(ConsequentS.castAs<DefinedSVal>(), Assumption);
+    }
+    return State;
+  }
+
+  /// A helper matcher to see whether the comparison states that the symbol
+  /// is non-null.
+  ProgramStateRef matchNonNullComparision(ProgramStateRef State,
+                                          BinaryOperator::Opcode Op,
+                                          SymbolRef LHS,
+                                          const llvm::APSInt &RHS,
+                                          bool Assumption) const {
+    if (((Op == BO_NE && Assumption) || (Op == BO_EQ && !Assumption)) &&
+        RHS == 0)
+      return addConsequentForCheck(State, LHS, /*Assumption=*/true);
+    return State;
   }
 };
 
 } // end empty namespace
 
 
 void ento::registerTrustNonnullChecker(CheckerManager &Mgr) {
-  Mgr.registerChecker<TrustNonnullChecker>();
+  Mgr.registerChecker<TrustNonnullChecker>(Mgr.getASTContext());
 }

clang/test/Analysis/Inputs/system-header-simulator-for-nullability.h

 #pragma clang system_header
 
 #define nil 0
 #define BOOL int
 
 #define NS_ASSUME_NONNULL_BEGIN _Pragma("clang assume_nonnull begin")
 #define NS_ASSUME_NONNULL_END   _Pragma("clang assume_nonnull end")
 
 NS_ASSUME_NONNULL_BEGIN
 
 typedef struct _NSZone NSZone;
+typedef unsigned long NSUInteger;
+@class NSCoder, NSEnumerator;
 
 @protocol NSObject
 + (instancetype)alloc;
 - (instancetype)init;
 - (instancetype)autorelease;
 @end
 
 @protocol NSCopying
 - (id)copyWithZone:(nullable NSZone *)zone;
 @end
 
 @protocol NSMutableCopying
 - (id)mutableCopyWithZone:(nullable NSZone *)zone;
 @end
 
+@protocol NSCoding
+- (void)encodeWithCoder:(NSCoder *)aCoder;
+@end
+
+@protocol NSSecureCoding <NSCoding>
+@required
++ (BOOL)supportsSecureCoding;
+@end
+
+typedef struct {
+  unsigned long state;
+  id *itemsPtr;
+  unsigned long *mutationsPtr;
+  unsigned long extra[5];
+} NSFastEnumerationState;
+
 __attribute__((objc_root_class))
 @interface
 NSObject<NSObject>
 @end
 
 @interface NSString : NSObject<NSCopying>
 - (BOOL)isEqualToString : (NSString *)aString;
 - (NSString *)stringByAppendingString:(NSString *)aString;

 NSString* _Nullable getPossiblyNullString();
 NSString* _Nonnull  getString();
 
 @protocol MyProtocol
 - (NSString * _Nonnull) getString;
 @end
 
 NS_ASSUME_NONNULL_END
+
+@interface NSDictionary : NSObject <NSCopying, NSMutableCopying, NSSecureCoding>
+
+- (NSUInteger)count;
+- (id)objectForKey:(id)aKey;
+- (NSEnumerator *)keyEnumerator;
+- (id)objectForKeyedSubscript:(id)aKey;
+
+@end
+
+@interface NSDictionary (NSDictionaryCreation)
+
++ (id)dictionary;
++ (id)dictionaryWithObject:(id)object forKey:(id <NSCopying>)key;
++ (instancetype)dictionaryWithObjects:(const id [])objects forKeys:(const id <NSCopying> [])keys count:(NSUInteger)cnt;
+
+@end
+
+@interface NSMutableDictionary : NSDictionary
+
+- (void)removeObjectForKey:(id)aKey;
+- (void)setObject:(id)anObject forKey:(id <NSCopying>)aKey;
+
+@end
+
+@interface NSMutableDictionary (NSExtendedMutableDictionary)
+
+- (void)addEntriesFromDictionary:(NSDictionary *)otherDictionary;
+- (void)removeAllObjects;
+- (void)setDictionary:(NSDictionary *)otherDictionary;
+- (void)setObject:(id)obj forKeyedSubscript:(id <NSCopying>)key __attribute__((availability(macosx,introduced=10.8)));
+
+@end

clang/test/Analysis/analyzer-config.c

 // CHECK-NEXT: cfg-temporary-dtors = true
 // CHECK-NEXT: elide-constructors = true
 // CHECK-NEXT: exploration_strategy = unexplored_first_queue
 // CHECK-NEXT: faux-bodies = true
 // CHECK-NEXT: graph-trim-interval = 1000
 // CHECK-NEXT: inline-lambdas = true
 // CHECK-NEXT: ipa = dynamic-bifurcate
 // CHECK-NEXT: ipa-always-inline-size = 3
+// CHECK-NEXT: leak-diagnostics-reference-allocation = false
 // CHECK-NEXT: max-inlinable-size = 100
 // CHECK-NEXT: max-nodes = 225000
 // CHECK-NEXT: max-times-inline-large = 32
 // CHECK-NEXT: min-cfg-size-treat-functions-as-large = 14
 // CHECK-NEXT: mode = deep
 // CHECK-NEXT: region-store-small-struct-limit = 2
 // CHECK-NEXT: serialize-stats = false
 // CHECK-NEXT: unroll-loops = false
 // CHECK-NEXT: widen-loops = false
 // CHECK-NEXT: [stats]
-// CHECK-NEXT: num-entries = 23
+// CHECK-NEXT: num-entries = 24

clang/test/Analysis/analyzer-config.cpp

 // CHECK-NEXT: elide-constructors = true
 // CHECK-NEXT: experimental-enable-naive-ctu-analysis = false
 // CHECK-NEXT: exploration_strategy = unexplored_first_queue
 // CHECK-NEXT: faux-bodies = true
 // CHECK-NEXT: graph-trim-interval = 1000
 // CHECK-NEXT: inline-lambdas = true
 // CHECK-NEXT: ipa = dynamic-bifurcate
 // CHECK-NEXT: ipa-always-inline-size = 3
+// CHECK-NEXT: leak-diagnostics-reference-allocation = false
 // CHECK-NEXT: max-inlinable-size = 100
 // CHECK-NEXT: max-nodes = 225000
 // CHECK-NEXT: max-times-inline-large = 32
 // CHECK-NEXT: min-cfg-size-treat-functions-as-large = 14
 // CHECK-NEXT: mode = deep
 // CHECK-NEXT: region-store-small-struct-limit = 2
 // CHECK-NEXT: serialize-stats = false
 // CHECK-NEXT: unroll-loops = false
 // CHECK-NEXT: widen-loops = false
 // CHECK-NEXT: [stats]
-// CHECK-NEXT: num-entries = 30
+// CHECK-NEXT: num-entries = 31

clang/test/Analysis/trustnonnullchecker_test.m

 }
 
 NSString * _Nonnull distrustProtocol(id<MyProtocol> o) {
   NSString* out = [o getString];
   if (out) {};
   return out; // expected-warning{{}}
 }
 
+// If the return value is non-nil, the index is non-nil.
+NSString *_Nonnull retImpliesIndex(NSString *s,
+                                   NSDictionary *dic) {
+  id obj = dic[s];
+  if (s) {}
+  if (obj)
+    return s; // no-warning
+  return @"foo";
+}
+
+NSString *_Nonnull retImpliesIndexOtherMethod(NSString *s,
+                                   NSDictionary *dic) {
+  id obj = [dic objectForKey:s];
+  if (s) {}
+  if (obj)
+    return s; // no-warning
+  return @"foo";
+}
+
+NSString *_Nonnull retImpliesIndexOnRHS(NSString *s,
+                                        NSDictionary *dic) {
+  id obj = dic[s];
+  if (s) {}
+  if (nil != obj)
+    return s; // no-warning
+  return @"foo";
+}
+
+NSString *_Nonnull retImpliesIndexReverseCheck(NSString *s,
+                                               NSDictionary *dic) {
+  id obj = dic[s];
+  if (s) {}
+  if (!obj)
+    return @"foo";
+  return s; // no-warning
+}
+
+NSString *_Nonnull retImpliesIndexReverseCheckOnRHS(NSString *s,
+                                                    NSDictionary *dic) {
+  id obj = dic[s];
+  if (s) {}
+  if (nil == obj)
+    return @"foo";
+  return s; // no-warning
+}
+
+NSString *_Nonnull retImpliesIndexWrongBranch(NSString *s,
+                                              NSDictionary *dic) {
+  id obj = dic[s];
+  if (s) {}
+  if (!obj)
+    return s; // expected-warning{{}}
+  return @"foo";
+}
+
+NSString *_Nonnull retImpliesIndexWrongBranchOnRHS(NSString *s,
+                                                   NSDictionary *dic) {
+  id obj = dic[s];
+  if (s) {}
+  if (nil == obj)
+    return s; // expected-warning{{}}
+  return @"foo";
+}
+
+// The return value could still be nil for a non-nil index.
+NSDictionary *_Nonnull indexDoesNotImplyRet(NSString *s,
+                                            NSDictionary *dic) {
+  id obj = dic[s];
+  if (obj) {}
+  if (s)
+    return obj; // expected-warning{{}}
+  return [[NSDictionary alloc] init];
+}
+
+NSString *_Nonnull checkAssumeOnMutableDictionary(NSMutableDictionary *d,
+                                                  NSString *k,
+                                                  NSString *val) {
+  d[k] = val;
+  if (k) {}
+  return k; // no-warning
+}
+
+NSString *_Nonnull checkAssumeOnMutableDictionaryOtherMethod(NSMutableDictionary *d,
+                                                             NSString *k,
+                                                             NSString *val) {
+  [d setObject:val forKey:k];
+  if (k) {}
+  return k; // no-warning
+}