From 2ffcd18b845d4f855074ff7011c46e20616e08fd Mon Sep 17 00:00:00 2001 From: Anna Zaks Date: Sat, 22 Jun 2013 00:23:26 +0000 Subject: [PATCH] =?utf8?q?[analyzer]=20Use=20output=20form=20collections?= =?utf8?q?=E2=80=99=20count=20to=20decide=20if=20ObjC=20for=20loop=20shoul?= =?utf8?q?d=20be=20entered?= MIME-Version: 1.0 Content-Type: text/plain; charset=utf8 Content-Transfer-Encoding: 8bit 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 --- .../Checkers/BasicObjCFoundationChecks.cpp | 183 +++++++++++++++++- test/Analysis/NSContainers.m | 27 ++- test/Analysis/objc-for.m | 131 +++++++++++++ 3 files changed, 328 insertions(+), 13 deletions(-) diff --git a/lib/StaticAnalyzer/Checkers/BasicObjCFoundationChecks.cpp b/lib/StaticAnalyzer/Checkers/BasicObjCFoundationChecks.cpp index ba779ff191..96f3f93021 100644 --- a/lib/StaticAnalyzer/Checkers/BasicObjCFoundationChecks.cpp +++ b/lib/StaticAnalyzer/Checkers/BasicObjCFoundationChecks.cpp @@ -786,12 +786,30 @@ void VariadicMethodTypeChecker::checkPreObjCMessage(const ObjCMethodCall &msg, // 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 > { - + : public Checker, + 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 @@ static ProgramStateRef checkElementNonNil(CheckerContext &C, return State->assume(Val.castAs(), 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(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 CountGreaterThanZero = + CountGreaterThanZeroVal.getAs(); + 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 BE = P.getAs()) { + 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; - - ProgramStateRef State = C.getState(); - State = checkCollectionNonNil(C, State, FCS); - State = checkElementNonNil(C, State, FCS); + if (CollectionSentinel.isZeroConstant()) { + if (!alreadyExecutedAtLeastOneLoopIteration(C.getPredecessor(), FCS)) + State = assumeCollectionNonEmpty(C, State, FCS, /*Assumption*/false); + // 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(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(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(); + for (ContainerCountMapTy::iterator I = Tracked.begin(), + E = Tracked.end(); I != E; ++I) { + SymbolRef Sym = I->first; + if (SymReaper.isDead(Sym)) + State = State->remove(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 959f367d28..d31c7b1ff0 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 @@ typedef struct _NSZone NSZone; @protocol NSCoding - (void)encodeWithCoder:(NSCoder *)aCoder; @end -@protocol NSFastEnumeration -@end @protocol NSSecureCoding @required + (BOOL)supportsSecureCoding; @@ -24,11 +22,20 @@ typedef struct _NSZone NSZone; - (id)init; + (id)alloc; @end -@interface NSArray : NSObject +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 - (NSUInteger)count; - (id)objectAtIndex:(NSUInteger)index; - @end @interface NSArray (NSExtendedArray) @@ -243,4 +250,14 @@ void testAssumeNSNullNullReturnsNonNil(NSMutableDictionary *Table, id Object, } } +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 ef149c4b14..dc855aaada 100644 --- a/test/Analysis/objc-for.m +++ b/test/Analysis/objc-for.m @@ -4,6 +4,7 @@ void clang_analyzer_eval(int); #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 @@ void clang_analyzer_eval(int); @end @interface NSArray : NSObject +- (NSUInteger)count; - (NSEnumerator *)objectEnumerator; @end @interface NSDictionary : NSObject +- (NSUInteger)count; @end @interface NSMutableDictionary : NSDictionary @end @interface NSSet : NSObject +- (NSUInteger)count; @end @interface NSPointerArray : NSObject @end +@interface NSString : NSObject +@end + void test() { id x; for (x in [NSArray testObject]) @@ -68,3 +75,127 @@ void testNonNil(id a, id b) { 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; +} -- 2.40.0