[analyzer] Use output form collections’ count to decide if ObjC for loop should be entered
This fixes false positives by allowing us to know that a loop is always entered if
the collection count method returns a positive value and vice versa.
Addresses radar://14169391.
git-svn-id: https://llvm.org/svn/llvm-project/cfe/trunk@184618 91177308-0d34-0410-b5e6-96231b3b80d8
diff --git a/lib/StaticAnalyzer/Checkers/BasicObjCFoundationChecks.cpp b/lib/StaticAnalyzer/Checkers/BasicObjCFoundationChecks.cpp
index ba779ff..96f3f93 100644
--- a/lib/StaticAnalyzer/Checkers/BasicObjCFoundationChecks.cpp
+++ b/lib/StaticAnalyzer/Checkers/BasicObjCFoundationChecks.cpp
@@ -786,12 +786,30 @@
// Improves the modeling of loops over Cocoa collections.
//===----------------------------------------------------------------------===//
+// 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)
+
namespace {
class ObjCLoopChecker
- : public Checker<check::PostStmt<ObjCForCollectionStmt> > {
-
+ : public Checker<check::PostStmt<ObjCForCollectionStmt>,
+ check::PostObjCMessage,
+ check::DeadSymbols,
+ check::PointerEscape > {
+ mutable IdentifierInfo *CountSelectorII;
+
+ bool isCollectionCountMethod(const ObjCMethodCall &M,
+ CheckerContext &C) const;
+
public:
+ ObjCLoopChecker() : CountSelectorII(0) {}
void checkPostStmt(const ObjCForCollectionStmt *FCS, CheckerContext &C) const;
+ void checkPostObjCMessage(const ObjCMethodCall &M, CheckerContext &C) const;
+ void checkDeadSymbols(SymbolReaper &SymReaper, CheckerContext &C) const;
+ ProgramStateRef checkPointerEscape(ProgramStateRef State,
+ const InvalidatedSymbols &Escaped,
+ const CallEvent *Call,
+ PointerEscapeKind Kind) const;
};
}
@@ -876,23 +894,172 @@
return State->assume(Val.castAs<DefinedOrUnknownSVal>(), true);
}
+/// 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)
+ return State;
+ const SymbolRef *CountS = State->get<ContainerCountMap>(CollectionS);
+ if (!CountS)
+ return State;
+
+ SValBuilder &SvalBuilder = C.getSValBuilder();
+ SVal CountGreaterThanZeroVal =
+ SvalBuilder.evalBinOp(State, BO_GT,
+ nonloc::SymbolVal(*CountS),
+ SvalBuilder.makeIntVal(0, (*CountS)->getType()),
+ SvalBuilder.getConditionType());
+ Optional<DefinedSVal> CountGreaterThanZero =
+ CountGreaterThanZeroVal.getAs<DefinedSVal>();
+ if (!CountGreaterThanZero) {
+ // The SValBuilder cannot construct a valid SVal for this condition.
+ // This means we cannot properly reason about it.
+ return State;
+ }
+
+ return State->assume(*CountGreaterThanZero, Assumption);
+}
+
+/// If the fist block edge is a back edge, we are reentering the loop.
+static bool alreadyExecutedAtLeastOneLoopIteration(const ExplodedNode *N,
+ const ObjCForCollectionStmt *FCS) {
+ if (!N)
+ return false;
+
+ ProgramPoint P = N->getLocation();
+ if (Optional<BlockEdge> BE = P.getAs<BlockEdge>()) {
+ if (BE->getSrc()->getLoopTarget() == FCS)
+ return true;
+ return false;
+ }
+
+ // Keep looking for a block edge.
+ for (ExplodedNode::const_pred_iterator I = N->pred_begin(),
+ E = N->pred_end(); I != E; ++I) {
+ if (alreadyExecutedAtLeastOneLoopIteration(*I, FCS))
+ return true;
+ }
+
+ return false;
+}
+
void ObjCLoopChecker::checkPostStmt(const ObjCForCollectionStmt *FCS,
CheckerContext &C) const {
+ ProgramStateRef State = C.getState();
+
// Check if this is the branch for the end of the loop.
SVal CollectionSentinel = C.getSVal(FCS);
- if (CollectionSentinel.isZeroConstant())
- return;
+ if (CollectionSentinel.isZeroConstant()) {
+ if (!alreadyExecutedAtLeastOneLoopIteration(C.getPredecessor(), FCS))
+ State = assumeCollectionNonEmpty(C, State, FCS, /*Assumption*/false);
- ProgramStateRef State = C.getState();
- State = checkCollectionNonNil(C, State, FCS);
- State = checkElementNonNil(C, State, FCS);
-
+ // Otherwise, this is a branch that goes through the loop body.
+ } else {
+ State = checkCollectionNonNil(C, State, FCS);
+ State = checkElementNonNil(C, State, FCS);
+ State = assumeCollectionNonEmpty(C, State, FCS, /*Assumption*/true);
+ }
+
if (!State)
C.generateSink();
else if (State != C.getState())
C.addTransition(State);
}
+bool ObjCLoopChecker::isCollectionCountMethod(const ObjCMethodCall &M,
+ CheckerContext &C) const {
+ Selector S = M.getSelector();
+ // Initialize the identifiers on first use.
+ if (!CountSelectorII)
+ CountSelectorII = &C.getASTContext().Idents.get("count");
+
+ // If the method returns collection count, record the value.
+ if (S.isUnarySelector() &&
+ (S.getIdentifierInfoForSlot(0) == CountSelectorII))
+ return true;
+
+ return false;
+}
+
+void ObjCLoopChecker::checkPostObjCMessage(const ObjCMethodCall &M,
+ CheckerContext &C) const {
+ if (!M.isInstanceMessage())
+ return;
+
+ const ObjCInterfaceDecl *ClassID = M.getReceiverInterface();
+ if (!ClassID)
+ return;
+
+ FoundationClass Class = findKnownClass(ClassID);
+ if (Class != FC_NSDictionary &&
+ Class != FC_NSArray &&
+ Class != FC_NSSet)
+ return;
+
+ SymbolRef ContainerS = M.getReceiverSVal().getAsSymbol();
+ if (!ContainerS)
+ return;
+
+ // If we are processing a call to "count", get the symbolic value returned by
+ // a call to "count" and add it to the map.
+ if (!isCollectionCountMethod(M, C))
+ return;
+
+ const Expr *MsgExpr = M.getOriginExpr();
+ SymbolRef CountS = C.getSVal(MsgExpr).getAsSymbol();
+ if (CountS) {
+ ProgramStateRef State = C.getState();
+ C.getSymbolManager().addSymbolDependency(ContainerS, CountS);
+ State = State->set<ContainerCountMap>(ContainerS, CountS);
+ C.addTransition(State);
+ }
+ return;
+}
+
+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.
+
+ // Remove the invalidated symbols form the collection count map.
+ for (InvalidatedSymbols::const_iterator I = Escaped.begin(),
+ E = Escaped.end();
+ I != E; ++I) {
+ SymbolRef Sym = *I;
+
+ // The symbol escaped. Pessimistically, assume that the count could have
+ // changed.
+ State = State->remove<ContainerCountMap>(Sym);
+ }
+ return State;
+}
+
+void ObjCLoopChecker::checkDeadSymbols(SymbolReaper &SymReaper,
+ CheckerContext &C) const {
+ ProgramStateRef State = C.getState();
+
+ // Remove the dead symbols from the collection count map.
+ ContainerCountMapTy Tracked = State->get<ContainerCountMap>();
+ for (ContainerCountMapTy::iterator I = Tracked.begin(),
+ E = Tracked.end(); I != E; ++I) {
+ SymbolRef Sym = I->first;
+ if (SymReaper.isDead(Sym))
+ State = State->remove<ContainerCountMap>(Sym);
+ }
+
+ C.addTransition(State);
+}
+
namespace {
/// \class ObjCNonNilReturnValueChecker
/// \brief The checker restricts the return values of APIs known to
diff --git a/test/Analysis/NSContainers.m b/test/Analysis/NSContainers.m
index 959f367..d31c7b1 100644
--- a/test/Analysis/NSContainers.m
+++ b/test/Analysis/NSContainers.m
@@ -1,4 +1,4 @@
-// RUN: %clang_cc1 -analyze -analyzer-checker=core,osx.cocoa.NonNilReturnValue,osx.cocoa.NilArg -verify -Wno-objc-root-class %s
+// RUN: %clang_cc1 -analyze -analyzer-checker=core,osx.cocoa.NonNilReturnValue,osx.cocoa.NilArg,osx.cocoa.Loops -verify -Wno-objc-root-class %s
typedef unsigned long NSUInteger;
typedef signed char BOOL;
typedef struct _NSZone NSZone;
@@ -14,8 +14,6 @@
@protocol NSCoding
- (void)encodeWithCoder:(NSCoder *)aCoder;
@end
-@protocol NSFastEnumeration
-@end
@protocol NSSecureCoding <NSCoding>
@required
+ (BOOL)supportsSecureCoding;
@@ -24,11 +22,20 @@
- (id)init;
+ (id)alloc;
@end
-@interface NSArray : NSObject <NSCopying, NSMutableCopying, NSSecureCoding, NSFastEnumeration>
+typedef struct {
+ unsigned long state;
+ id *itemsPtr;
+ unsigned long *mutationsPtr;
+ unsigned long extra[5];
+} NSFastEnumerationState;
+@protocol NSFastEnumeration
+- (NSUInteger)countByEnumeratingWithState:(NSFastEnumerationState *)state objects:(id [])buffer count:(NSUInteger)len;
+@end
+
+@interface NSArray : NSObject <NSCopying, NSMutableCopying, NSSecureCoding, NSFastEnumeration>
- (NSUInteger)count;
- (id)objectAtIndex:(NSUInteger)index;
-
@end
@interface NSArray (NSExtendedArray)
@@ -243,4 +250,14 @@
}
}
+void testCollectionIsNotEmptyWhenCountIsGreaterThanZero(NSMutableDictionary *D){
+ if ([D count] > 0) { // Count is greater than zero.
+ NSString *s = 0;
+ for (NSString *key in D) {
+ s = key; // Loop is always entered.
+ }
+ [D removeObjectForKey:s]; // no warning
+ }
+}
+
diff --git a/test/Analysis/objc-for.m b/test/Analysis/objc-for.m
index ef149c4..dc855aa 100644
--- a/test/Analysis/objc-for.m
+++ b/test/Analysis/objc-for.m
@@ -4,6 +4,7 @@
#define nil ((id)0)
+typedef unsigned long NSUInteger;
@protocol NSFastEnumeration
- (int)countByEnumeratingWithState:(void *)state objects:(id *)objects count:(unsigned)count;
@end
@@ -16,21 +17,27 @@
@end
@interface NSArray : NSObject <NSFastEnumeration>
+- (NSUInteger)count;
- (NSEnumerator *)objectEnumerator;
@end
@interface NSDictionary : NSObject <NSFastEnumeration>
+- (NSUInteger)count;
@end
@interface NSMutableDictionary : NSDictionary
@end
@interface NSSet : NSObject <NSFastEnumeration>
+- (NSUInteger)count;
@end
@interface NSPointerArray : NSObject <NSFastEnumeration>
@end
+@interface NSString : NSObject
+@end
+
void test() {
id x;
for (x in [NSArray testObject])
@@ -68,3 +75,127 @@
clang_analyzer_eval(b != nil); // expected-warning{{FALSE}}
}
+void collectionIsEmpty(NSMutableDictionary *D){
+ if ([D count] == 0) { // Count is zero.
+ NSString *s = 0;
+ for (NSString *key in D) {
+ s = key; // Loop is never entered.
+ }
+ clang_analyzer_eval(s == 0); //expected-warning{{TRUE}}
+ }
+}
+
+void processCollection(NSMutableDictionary *D);
+void collectionIsEmptyCollectionIsModified(NSMutableDictionary *D){
+ if ([D count] == 0) { // Count is zero.
+ NSString *s = 0;
+ processCollection(D); // However, the collection has changed.
+ for (NSString *key in D) {
+ s = key; // Loop might be entered.
+ }
+ clang_analyzer_eval(s == 0); //expected-warning{{FALSE}} //expected-warning{{TRUE}}
+ }
+}
+
+int collectionIsEmptyNSSet(NSSet *S){
+ if ([S count] == 2) { // Count is non zero.
+ int tapCounts[2];
+ int i = 0;
+ for (NSString *elem in S) {
+ tapCounts[i]= 1; // Loop is entered.
+ i++;
+ }
+ return (tapCounts[0]); //no warning
+ }
+ return 0;
+}
+
+int collectionIsNotEmptyNSArray(NSArray *A) {
+ int count = [A count];
+ if (count > 0) {
+ int i;
+ int j;
+ for (NSString *a in A) {
+ i = 1;
+ j++;
+ }
+ clang_analyzer_eval(i == 1); // expected-warning {{TRUE}}
+ }
+ return 0;
+}
+
+void onlySuppressExitAfterZeroIterations(NSMutableDictionary *D) {
+ if (D.count > 0) {
+ int *x;
+ int i;
+ for (NSString *key in D) {
+ x = 0;
+ i++;
+ }
+ // Test that this is reachable.
+ int y = *x; // expected-warning {{Dereference of null pointer}}
+ y++;
+ }
+}
+
+void onlySuppressLoopExitAfterZeroIterations_WithContinue(NSMutableDictionary *D) {
+ if (D.count > 0) {
+ int *x;
+ int i;
+ for (NSString *key in D) {
+ x = 0;
+ i++;
+ continue;
+ }
+ // Test that this is reachable.
+ int y = *x; // expected-warning {{Dereference of null pointer}}
+ y++;
+ }
+}
+
+int* getPtr();
+void onlySuppressLoopExitAfterZeroIterations_WithBreak(NSMutableDictionary *D) {
+ if (D.count > 0) {
+ int *x;
+ int i;
+ for (NSString *key in D) {
+ x = 0;
+ break;
+ x = getPtr();
+ i++;
+ }
+ int y = *x; // expected-warning {{Dereference of null pointer}}
+ y++;
+ }
+}
+
+int consistencyBetweenLoopsWhenCountIsUnconstrained(NSMutableDictionary *D) {
+ // Note, The current limitation is that we need to have a count.
+ // TODO: This should work even when we do not call count.
+ int count = [D count];
+ int i;
+ int j = 0;
+ for (NSString *key in D) {
+ i = 5;
+ j++;
+ }
+ for (NSString *key in D) {
+ return i; // no-warning
+ }
+ return 0;
+}
+
+int consistencyBetweenLoopsWhenCountIsUnconstrained_dual(NSMutableDictionary *D) {
+ int count = [D count];
+ int i = 8;
+ int j = 1;
+ for (NSString *key in D) {
+ i = 0;
+ j++;
+ }
+ for (NSString *key in D) {
+ i = 5;
+ j++;
+ }
+ return 5/i;
+}