From 219103d76a10b35b5a1e8d2b6737cf724a7cfee7 Mon Sep 17 00:00:00 2001 From: Jordan Rose Date: Fri, 8 Nov 2013 01:15:35 +0000 Subject: [PATCH] [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. git-svn-id: https://llvm.org/svn/llvm-project/cfe/trunk@194235 91177308-0d34-0410-b5e6-96231b3b80d8 --- .../Checkers/BasicObjCFoundationChecks.cpp | 101 +++++++++++-- test/Analysis/objc-for.m | 137 +++++++++++++++++- 2 files changed, 216 insertions(+), 22 deletions(-) diff --git a/lib/StaticAnalyzer/Checkers/BasicObjCFoundationChecks.cpp b/lib/StaticAnalyzer/Checkers/BasicObjCFoundationChecks.cpp index d6ebbefc19..f66f8b75ed 100644 --- a/lib/StaticAnalyzer/Checkers/BasicObjCFoundationChecks.cpp +++ b/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 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(CollectionS); - if (!CountS) - return State; + if (!CountS) { + const bool *KnownNonEmpty = State->get(CollectionS); + if (!KnownNonEmpty) + return State->set(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(ContainerS, CountS); + + if (const bool *NonEmpty = State->get(ContainerS)) { + State = State->remove(ContainerS); + State = assumeCollectionNonEmpty(C, State, ContainerS, *NonEmpty); + } + C.addTransition(State); } return; } +static SymbolRef getMethodReceiverIfKnownImmutable(const CallEvent *Call) { + const ObjCMethodCall *Message = dyn_cast_or_null(Call); + if (!Message) + return 0; + + const ObjCMethodDecl *MD = Message->getDecl(); + if (!MD) + return 0; + + const ObjCInterfaceDecl *StaticClass; + if (isa(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(Sym); + State = State->remove(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(Sym); + State = State->remove(Sym); + } } C.addTransition(State); diff --git a/test/Analysis/objc-for.m b/test/Analysis/objc-for.m index dc855aaada..2f14b8ad1a 100644 --- a/test/Analysis/objc-for.m +++ b/test/Analysis/objc-for.m @@ -7,6 +7,7 @@ void clang_analyzer_eval(int); typedef unsigned long NSUInteger; @protocol NSFastEnumeration - (int)countByEnumeratingWithState:(void *)state objects:(id *)objects count:(unsigned)count; +- (void)protocolMethod; @end @interface NSObject @@ -23,9 +24,19 @@ typedef unsigned long NSUInteger; @interface NSDictionary : NSObject - (NSUInteger)count; +- (id)objectForKey:(id)key; +@end + +@interface NSDictionary (SomeCategory) +- (void)categoryMethodOnNSDictionary; @end @interface NSMutableDictionary : NSDictionary +- (void)setObject:(id)obj forKey:(id)key; +@end + +@interface NSMutableArray : NSArray +- (void)addObject:(id)obj; @end @interface NSSet : NSObject @@ -169,10 +180,13 @@ void onlySuppressLoopExitAfterZeroIterations_WithBreak(NSMutableDictionary *D) { } } -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 consistencyBetweenLoopsWhenCountIsUnconstrained(NSMutableDictionary *D, + int shouldUseCount) { + // Test with or without an initial count. + int count; + if (shouldUseCount) + count = [D count]; + int i; int j = 0; for (NSString *key in D) { @@ -185,8 +199,12 @@ int consistencyBetweenLoopsWhenCountIsUnconstrained(NSMutableDictionary *D) { return 0; } -int consistencyBetweenLoopsWhenCountIsUnconstrained_dual(NSMutableDictionary *D) { - int count = [D count]; +int consistencyBetweenLoopsWhenCountIsUnconstrained_dual(NSMutableDictionary *D, + int shouldUseCount) { + int count; + if (shouldUseCount) + count = [D count]; + int i = 8; int j = 1; for (NSString *key in D) { @@ -199,3 +217,110 @@ int consistencyBetweenLoopsWhenCountIsUnconstrained_dual(NSMutableDictionary *D) } return 5/i; } + +int consistencyCountThenLoop(NSArray *array) { + if ([array count] == 0) + return 0; + + int x; + for (id y in array) + x = 0; + return x; // no-warning +} + +int consistencyLoopThenCount(NSArray *array) { + int x; + for (id y in array) + x = 0; + + if ([array count] == 0) + return 0; + + return x; // no-warning +} + +void nonMutatingMethodsDoNotInvalidateCountDictionary(NSMutableDictionary *dict, + NSMutableArray *other) { + if ([dict count]) + return; + + for (id key in dict) + clang_analyzer_eval(0); // no-warning + + (void)[dict objectForKey:@""]; + + for (id key in dict) + clang_analyzer_eval(0); // no-warning + + [dict categoryMethodOnNSDictionary]; + + for (id key in dict) + clang_analyzer_eval(0); // no-warning + + [dict setObject:@"" forKey:@""]; + + for (id key in dict) + clang_analyzer_eval(0); // expected-warning{{FALSE}} + + // Reset. + if ([dict count]) + return; + + for (id key in dict) + clang_analyzer_eval(0); // no-warning + + [other addObject:dict]; + + for (id key in dict) + clang_analyzer_eval(0); // expected-warning{{FALSE}} +} + +void nonMutatingMethodsDoNotInvalidateCountArray(NSMutableArray *array, + NSMutableArray *other) { + if ([array count]) + return; + + for (id key in array) + clang_analyzer_eval(0); // no-warning + + (void)[array objectEnumerator]; + + for (id key in array) + clang_analyzer_eval(0); // no-warning + + [array addObject:@""]; + + for (id key in array) + clang_analyzer_eval(0); // expected-warning{{FALSE}} + + // Reset. + if ([array count]) + return; + + for (id key in array) + clang_analyzer_eval(0); // no-warning + + [other addObject:array]; + + for (id key in array) + clang_analyzer_eval(0); // expected-warning{{FALSE}} +} + +void protocolMethods(NSMutableArray *array) { + if ([array count]) + return; + + for (id key in array) + clang_analyzer_eval(0); // no-warning + + NSArray *immutableArray = array; + [immutableArray protocolMethod]; + + for (id key in array) + clang_analyzer_eval(0); // no-warning + + [array protocolMethod]; + + for (id key in array) + clang_analyzer_eval(0); // expected-warning{{FALSE}} +} -- 2.50.0