[analyzer] Correctly model iteration through "nil" objects

[george.karpenkov]

Summary

Previously, iteration through nil objects which resulted from objc-messages being set to nil were modeled incorrectly.

There are a couple of notes about this patch:

• In principle, ExprEngineObjC might be left untouched IFF osx.loops checker is enabled. I however think that we should not do something completely incorrect depending on what checkers are left on.
• We should evaluate and potentially remove altogether the isConsumedExpr performance heuristic, as it seems very fragile.

rdar://22205149

[NoQ]

lib/StaticAnalyzer/Core/ExprEngineObjC.cpp

58

Uhm. Why does this code bind a value to a non-expression. This old/legacy code would love some cleanup. Could you add a FIXME here? ("We shouldn't bind a value to a non-statement.").

lib/AST/ParentMap.cpp

 //  This file defines the ParentMap class.
 //
 //===----------------------------------------------------------------------===//
 
 #include "clang/AST/ParentMap.h"
 #include "clang/AST/Decl.h"
 #include "clang/AST/Expr.h"
 #include "clang/AST/ExprCXX.h"
+#include "clang/AST/StmtObjC.h"
 #include "llvm/ADT/DenseMap.h"
 
 using namespace clang;
 
 typedef llvm::DenseMap<Stmt*, Stmt*> MapTy;
 
 enum OpaqueValueMode {
   OV_Transparent,
switch (P->getStmtClass()) {
     case Stmt::DoStmtClass:
       return DirectChild == cast<DoStmt>(P)->getCond();
     case Stmt::IfStmtClass:
       return DirectChild == cast<IfStmt>(P)->getCond();
     case Stmt::IndirectGotoStmtClass:
       return DirectChild == cast<IndirectGotoStmt>(P)->getTarget();
     case Stmt::SwitchStmtClass:
       return DirectChild == cast<SwitchStmt>(P)->getCond();
+    case Stmt::ObjCForCollectionStmtClass:
+      return DirectChild == cast<ObjCForCollectionStmt>(P)->getCollection();
     case Stmt::ReturnStmtClass:
       return true;
   }
 }
 

lib/StaticAnalyzer/Core/ExprEngineObjC.cpp

 }
 
 void ExprEngine::VisitObjCAtSynchronizedStmt(const ObjCAtSynchronizedStmt *S,
                                              ExplodedNode *Pred,
                                              ExplodedNodeSet &Dst) {
   getCheckerManager().runCheckersForPreStmt(Dst, Pred, S, *this);
 }
 
+/// Generate a node in \p Bldr for an iteration statement using ObjC
+/// for-loop iterator.
+static void populateObjCForDestinationSet(
+    ExplodedNodeSet &dstLocation, SValBuilder &svalBuilder,
+    const ObjCForCollectionStmt *S, const Stmt *elem, SVal elementV,
+    SymbolManager &SymMgr, const NodeBuilderContext *currBldrCtx,
+    StmtNodeBuilder &Bldr, bool hasElements) {
+
+  for (ExplodedNode *Pred : dstLocation) {
+    ProgramStateRef state = Pred->getState();
+    const LocationContext *LCtx = Pred->getLocationContext();
+
+    SVal hasElementsV = svalBuilder.makeTruthVal(hasElements);
+
+    // FIXME: S is not an expression. We should not be binding values to it.
+    ProgramStateRef nextState = state->BindExpr(S, LCtx, hasElementsV);
+
+    if (auto MV = elementV.getAs<loc::MemRegionVal>())
+      if (const auto *R = dyn_cast<TypedValueRegion>(MV->getRegion())) {
+        // FIXME: The proper thing to do is to really iterate over the
+        //  container.  We will do this with dispatch logic to the store.
+        //  For now, just 'conjure' up a symbolic value.
+        QualType T = R->getValueType();
+        assert(Loc::isLocType(T));
+
+        SVal V;
+        if (hasElements) {
+          SymbolRef Sym = SymMgr.conjureSymbol(elem, LCtx, T,
+                                               currBldrCtx->blockCount());
+          V = svalBuilder.makeLoc(Sym);
+        } else {
+          V = svalBuilder.makeIntVal(0, T);
+        }
+
+        nextState = nextState->bindLoc(elementV, V, LCtx);
+      }
+
+    Bldr.generateNode(S, Pred, nextState);
+  }
+}
+
 void ExprEngine::VisitObjCForCollectionStmt(const ObjCForCollectionStmt *S,
                                             ExplodedNode *Pred,
                                             ExplodedNodeSet &Dst) {
 
   // ObjCForCollectionStmts are processed in two places.  This method
   // handles the case where an ObjCForCollectionStmt* occurs as one of the
   // statements within a basic block.  This transfer function does two things:
   //
void ExprEngine::VisitObjCForCollectionStmt(const ObjCForCollectionStmt *S,
   //   we can test if the SVal is 0 or if the MemRegion is null (depending
   //   on what approach we take).
   //
   //  For now: simulate (1) by assigning either a symbol or nil if the
   //    container is empty.  Thus this transfer function will by default
   //    result in state splitting.
 
   const Stmt *elem = S->getElement();
+  const Stmt *collection = S->getCollection();
   ProgramStateRef state = Pred->getState();
-  SVal elementV;
+  SVal collectionV = state->getSVal(collection, Pred->getLocationContext());
 
-  if (const DeclStmt *DS = dyn_cast<DeclStmt>(elem)) {
+  SVal elementV;
+  if (const auto *DS = dyn_cast<DeclStmt>(elem)) {
     const VarDecl *elemD = cast<VarDecl>(DS->getSingleDecl());
     assert(elemD->getInit() == nullptr);
     elementV = state->getLValue(elemD, Pred->getLocationContext());
-  }
-  else {
+  } else {
     elementV = state->getSVal(elem, Pred->getLocationContext());
   }
 
+  bool isContainerNull = state->isNull(collectionV).isConstrainedTrue();
+
   ExplodedNodeSet dstLocation;
   evalLocation(dstLocation, S, elem, Pred, state, elementV, nullptr, false);
 
   ExplodedNodeSet Tmp;
   StmtNodeBuilder Bldr(Pred, Tmp, *currBldrCtx);
 
-  for (ExplodedNodeSet::iterator NI = dstLocation.begin(),
-       NE = dstLocation.end(); NI!=NE; ++NI) {
-    Pred = *NI;
-    ProgramStateRef state = Pred->getState();
-    const LocationContext *LCtx = Pred->getLocationContext();
-
-    // Handle the case where the container still has elements.
-    SVal TrueV = svalBuilder.makeTruthVal(1);
-    ProgramStateRef hasElems = state->BindExpr(S, LCtx, TrueV);
-
-    // Handle the case where the container has no elements.
-    SVal FalseV = svalBuilder.makeTruthVal(0);
-    ProgramStateRef noElems = state->BindExpr(S, LCtx, FalseV);
-
-    if (Optional<loc::MemRegionVal> MV = elementV.getAs<loc::MemRegionVal>())
-      if (const TypedValueRegion *R =
-          dyn_cast<TypedValueRegion>(MV->getRegion())) {
-        // FIXME: The proper thing to do is to really iterate over the
-        //  container.  We will do this with dispatch logic to the store.
-        //  For now, just 'conjure' up a symbolic value.
-        QualType T = R->getValueType();
-        assert(Loc::isLocType(T));
-        SymbolRef Sym = SymMgr.conjureSymbol(elem, LCtx, T,
-                                             currBldrCtx->blockCount());
-        SVal V = svalBuilder.makeLoc(Sym);
-        hasElems = hasElems->bindLoc(elementV, V, LCtx);
-
-        // Bind the location to 'nil' on the false branch.
-        SVal nilV = svalBuilder.makeIntVal(0, T);
-        noElems = noElems->bindLoc(elementV, nilV, LCtx);
-      }
-
-    // Create the new nodes.
-    Bldr.generateNode(S, Pred, hasElems);
-    Bldr.generateNode(S, Pred, noElems);
-  }
+  if (!isContainerNull)
+    populateObjCForDestinationSet(dstLocation, svalBuilder, S, elem, elementV,
+                                  SymMgr, currBldrCtx, Bldr,
+                                  /*hasElements=*/true);
+
+  populateObjCForDestinationSet(dstLocation, svalBuilder, S, elem, elementV,
+                                SymMgr, currBldrCtx, Bldr,
+                                /*hasElements=*/false);
 
   // Finally, run any custom checkers.
   // FIXME: Eventually all pre- and post-checks should live in VisitStmt.
   getCheckerManager().runCheckersForPostStmt(Dst, Tmp, S, *this);
 }
 
 void ExprEngine::VisitObjCMessage(const ObjCMessageExpr *ME,
                                   ExplodedNode *Pred,

test/Analysis/objc-for.m

 @interface NSDictionary : NSObject <NSFastEnumeration>
 - (NSUInteger)count;
 - (id)objectForKey:(id)key;
 + (id)dictionaryWithObjects:(const id [])objects forKeys:(const id /* <NSCopying> */ [])keys count:(NSUInteger)count;
 @end
 
 @interface NSDictionary (SomeCategory)
 - (void)categoryMethodOnNSDictionary;
+- (id) allKeys;
 @end
 
 @interface NSMutableDictionary : NSDictionary
 - (void)setObject:(id)obj forKey:(id)key;
 @end
 
 @interface NSMutableArray : NSArray
 - (void)addObject:(id)obj;
for (id key in array)
     clang_analyzer_warnIfReached(); // expected-warning{{REACHABLE}}
 
   if ([array count])
     return;
   globalDictionary = @{ @"array" : array };
   for (id key in array)
     clang_analyzer_warnIfReached(); // expected-warning{{REACHABLE}}
 }
+
+int not_reachable_on_iteration_through_nil() {
+  NSDictionary* d = nil;
+  for (NSString* s in [d allKeys])
+    clang_analyzer_warnIfReached(); // no-warning
+  return 0;
+}