[analyzer] Track whether an ObjC for-in loop had zero iterations.

An Objective-C for-in loop will have zero iterations if the collection is
empty. Previously, we could only detect this case if the program asked for
the collection's -count /before/ the for-in loop. Now, the analyzer
distinguishes for-in loops that had zero iterations from those with at
least one, and can use this information to constrain the result of calling
-count after the loop.

In order to make this actually useful, teach the checker that methods on
NSArray, NSDictionary, and the other immutable collection classes don't
change the count.

<rdar://problem/14992886>

llvm-svn: 194235

1 files changed, 85 insertions, 16 deletions

diff --git a/clang/lib/StaticAnalyzer/Checkers/BasicObjCFoundationChecks.cpp b/clang/lib/StaticAnalyzer/Checkers/BasicObjCFoundationChecks.cpp
index d6ebbefc193..f66f8b75ed3 100644
--- a/clang/lib/StaticAnalyzer/Checkers/BasicObjCFoundationChecks.cpp
+++ b/clang/lib/StaticAnalyzer/Checkers/BasicObjCFoundationChecks.cpp
@@ -64,7 +64,8 @@ enum FoundationClass {
   FC_NSString
 };
 
-static FoundationClass findKnownClass(const ObjCInterfaceDecl *ID) {
+static FoundationClass findKnownClass(const ObjCInterfaceDecl *ID,
+                                      bool IncludeSuperclasses = true) {
   static llvm::StringMap<FoundationClass> Classes;
   if (Classes.empty()) {
     Classes["NSArray"] = FC_NSArray;
@@ -78,7 +79,7 @@ static FoundationClass findKnownClass(const ObjCInterfaceDecl *ID) {
 
   // FIXME: Should we cache this at all?
   FoundationClass result = Classes.lookup(ID->getIdentifier()->getName());
-  if (result == FC_None)
+  if (result == FC_None && IncludeSuperclasses)
     if (const ObjCInterfaceDecl *Super = ID->getSuperClass())
       return findKnownClass(Super);
 
@@ -789,6 +790,7 @@ void VariadicMethodTypeChecker::checkPreObjCMessage(const ObjCMethodCall &msg,
 // The map from container symbol to the container count symbol.
 // We currently will remember the last countainer count symbol encountered.
 REGISTER_MAP_WITH_PROGRAMSTATE(ContainerCountMap, SymbolRef, SymbolRef)
+REGISTER_MAP_WITH_PROGRAMSTATE(ContainerNonEmptyMap, SymbolRef, bool)
 
 namespace {
 class ObjCLoopChecker
@@ -896,19 +898,19 @@ static ProgramStateRef checkElementNonNil(CheckerContext &C,
 
 /// Returns NULL state if the collection is known to contain elements
 /// (or is known not to contain elements if the Assumption parameter is false.)
-static ProgramStateRef assumeCollectionNonEmpty(CheckerContext &C,
-                                            ProgramStateRef State,
-                                            const ObjCForCollectionStmt *FCS,
-                                            bool Assumption = false) {
-  if (!State)
-    return NULL;
-
-  SymbolRef CollectionS = C.getSVal(FCS->getCollection()).getAsSymbol();
-  if (!CollectionS)
+static ProgramStateRef
+assumeCollectionNonEmpty(CheckerContext &C, ProgramStateRef State,
+                         SymbolRef CollectionS, bool Assumption) {
+  if (!State || !CollectionS)
     return State;
+
   const SymbolRef *CountS = State->get<ContainerCountMap>(CollectionS);
-  if (!CountS)
-    return State;
+  if (!CountS) {
+    const bool *KnownNonEmpty = State->get<ContainerNonEmptyMap>(CollectionS);
+    if (!KnownNonEmpty)
+      return State->set<ContainerNonEmptyMap>(CollectionS, Assumption);
+    return (Assumption == *KnownNonEmpty) ? State : NULL;
+  }
 
   SValBuilder &SvalBuilder = C.getSValBuilder();
   SVal CountGreaterThanZeroVal =
@@ -927,6 +929,19 @@ static ProgramStateRef assumeCollectionNonEmpty(CheckerContext &C,
   return State->assume(*CountGreaterThanZero, Assumption);
 }
 
+static ProgramStateRef
+assumeCollectionNonEmpty(CheckerContext &C, ProgramStateRef State,
+                         const ObjCForCollectionStmt *FCS,
+                         bool Assumption) {
+  if (!State)
+    return NULL;
+
+  SymbolRef CollectionS =
+    State->getSVal(FCS->getCollection(), C.getLocationContext()).getAsSymbol();
+  return assumeCollectionNonEmpty(C, State, CollectionS, Assumption);
+}
+
+
 /// If the fist block edge is a back edge, we are reentering the loop.
 static bool alreadyExecutedAtLeastOneLoopIteration(const ExplodedNode *N,
                                              const ObjCForCollectionStmt *FCS) {
@@ -1017,20 +1032,64 @@ void ObjCLoopChecker::checkPostObjCMessage(const ObjCMethodCall &M,
   SymbolRef CountS = C.getSVal(MsgExpr).getAsSymbol();
   if (CountS) {
     ProgramStateRef State = C.getState();
+
     C.getSymbolManager().addSymbolDependency(ContainerS, CountS);
     State = State->set<ContainerCountMap>(ContainerS, CountS);
+
+    if (const bool *NonEmpty = State->get<ContainerNonEmptyMap>(ContainerS)) {
+      State = State->remove<ContainerNonEmptyMap>(ContainerS);
+      State = assumeCollectionNonEmpty(C, State, ContainerS, *NonEmpty);
+    }
+
     C.addTransition(State);
   }
   return;
 }
 
+static SymbolRef getMethodReceiverIfKnownImmutable(const CallEvent *Call) {
+  const ObjCMethodCall *Message = dyn_cast_or_null<ObjCMethodCall>(Call);
+  if (!Message)
+    return 0;
+
+  const ObjCMethodDecl *MD = Message->getDecl();
+  if (!MD)
+    return 0;
+
+  const ObjCInterfaceDecl *StaticClass;
+  if (isa<ObjCProtocolDecl>(MD->getDeclContext())) {
+    // We can't find out where the method was declared without doing more work.
+    // Instead, see if the receiver is statically typed as a known immutable
+    // collection.
+    StaticClass = Message->getOriginExpr()->getReceiverInterface();
+  } else {
+    StaticClass = MD->getClassInterface();
+  }
+
+  if (!StaticClass)
+    return 0;
+
+  switch (findKnownClass(StaticClass, /*IncludeSuper=*/false)) {
+  case FC_None:
+    return 0;
+  case FC_NSArray:
+  case FC_NSDictionary:
+  case FC_NSEnumerator:
+  case FC_NSNull:
+  case FC_NSOrderedSet:
+  case FC_NSSet:
+  case FC_NSString:
+    break;
+  }
+
+  return Message->getReceiverSVal().getAsSymbol();
+}
+
 ProgramStateRef
 ObjCLoopChecker::checkPointerEscape(ProgramStateRef State,
                                     const InvalidatedSymbols &Escaped,
                                     const CallEvent *Call,
                                     PointerEscapeKind Kind) const {
-  // TODO: If we know that the call cannot change the collection count, there
-  // is nothing to do, just return.
+  SymbolRef ImmutableReceiver = getMethodReceiverIfKnownImmutable(Call);
 
   // Remove the invalidated symbols form the collection count map.
   for (InvalidatedSymbols::const_iterator I = Escaped.begin(),
@@ -1038,9 +1097,17 @@ ObjCLoopChecker::checkPointerEscape(ProgramStateRef State,
        I != E; ++I) {
     SymbolRef Sym = *I;
 
+    // Don't invalidate this symbol's count if we know the method being called
+    // is declared on an immutable class. This isn't completely correct if the
+    // receiver is also passed as an argument, but in most uses of NSArray,
+    // NSDictionary, etc. this isn't likely to happen in a dangerous way.
+    if (Sym == ImmutableReceiver)
+      continue;
+
     // The symbol escaped. Pessimistically, assume that the count could have
     // changed.
     State = State->remove<ContainerCountMap>(Sym);
+    State = State->remove<ContainerNonEmptyMap>(Sym);
   }
   return State;
 }
@@ -1054,8 +1121,10 @@ void ObjCLoopChecker::checkDeadSymbols(SymbolReaper &SymReaper,
   for (ContainerCountMapTy::iterator I = Tracked.begin(),
                                      E = Tracked.end(); I != E; ++I) {
     SymbolRef Sym = I->first;
-    if (SymReaper.isDead(Sym))
+    if (SymReaper.isDead(Sym)) {
       State = State->remove<ContainerCountMap>(Sym);
+      State = State->remove<ContainerNonEmptyMap>(Sym);
+    }
   }
 
   C.addTransition(State);