Author: george.karpenkov Date: Fri Aug 10 15:27:04 2018 New Revision: 339482
URL: http://llvm.org/viewvc/llvm-project?rev=339482&view=rev Log: [analyzer] Record nullability implications on getting items from NSDictionary If we get an item from a dictionary, we know that the item is non-null if and only if the key is non-null. This patch is a rather hacky way to record this implication, because some logic needs to be duplicated from the solver. And yet, it's pretty simple, performant, and works. Other possible approaches: - Record the implication, in future rely on Z3 to pick it up. - Generalize the current code and move it to the constraint manager. rdar://34990742 Differential Revision: https://reviews.llvm.org/D50124 Modified: cfe/trunk/lib/StaticAnalyzer/Checkers/TrustNonnullChecker.cpp cfe/trunk/test/Analysis/Inputs/system-header-simulator-for-nullability.h cfe/trunk/test/Analysis/trustnonnullchecker_test.m Modified: cfe/trunk/lib/StaticAnalyzer/Checkers/TrustNonnullChecker.cpp URL: http://llvm.org/viewvc/llvm-project/cfe/trunk/lib/StaticAnalyzer/Checkers/TrustNonnullChecker.cpp?rev=339482&r1=339481&r2=339482&view=diff ============================================================================== --- cfe/trunk/lib/StaticAnalyzer/Checkers/TrustNonnullChecker.cpp (original) +++ cfe/trunk/lib/StaticAnalyzer/Checkers/TrustNonnullChecker.cpp Fri Aug 10 15:27:04 2018 @@ -1,4 +1,4 @@ -//== TrustNonnullChecker.cpp - Checker for trusting annotations -*- C++ -*--==// +//== TrustNonnullChecker.cpp --------- API nullability modeling -*- C++ -*--==// // // The LLVM Compiler Infrastructure // @@ -7,12 +7,20 @@ // //===----------------------------------------------------------------------===// // -// This checker adds an assumption that methods annotated with _Nonnull +// This checker adds nullability-related assumptions: +// +// 1. Methods annotated with _Nonnull // which come from system headers actually return a non-null pointer. // +// 2. NSDictionary key is non-null after the keyword subscript operation +// on read if and only if the resulting expression is non-null. +// +// 3. NSMutableDictionary index is non-null after a write operation. +// //===----------------------------------------------------------------------===// #include "ClangSACheckers.h" +#include "SelectorExtras.h" #include "clang/StaticAnalyzer/Core/Checker.h" #include "clang/StaticAnalyzer/Core/CheckerManager.h" #include "clang/StaticAnalyzer/Core/PathSensitive/CheckerContext.h" @@ -22,10 +30,129 @@ using namespace clang; using namespace ento; +/// Records implications between symbols. +/// The semantics is: +/// (antecedent != 0) => (consequent != 0) +/// These implications are then read during the evaluation of the assumption, +/// and the appropriate antecedents are applied. +REGISTER_MAP_WITH_PROGRAMSTATE(NonNullImplicationMap, SymbolRef, SymbolRef) + +/// The semantics is: +/// (antecedent == 0) => (consequent == 0) +REGISTER_MAP_WITH_PROGRAMSTATE(NullImplicationMap, SymbolRef, SymbolRef) + namespace { -class TrustNonnullChecker : public Checker<check::PostCall> { +class TrustNonnullChecker : public Checker<check::PostCall, + check::PostObjCMessage, + check::DeadSymbols, + eval::Assume> { + // Do not try to iterate over symbols with higher complexity. + static unsigned constexpr ComplexityThreshold = 10; + Selector ObjectForKeyedSubscriptSel; + Selector ObjectForKeySel; + Selector SetObjectForKeyedSubscriptSel; + Selector SetObjectForKeySel; + +public: + TrustNonnullChecker(ASTContext &Ctx) + : ObjectForKeyedSubscriptSel( + getKeywordSelector(Ctx, "objectForKeyedSubscript")), + ObjectForKeySel(getKeywordSelector(Ctx, "objectForKey")), + SetObjectForKeyedSubscriptSel( + getKeywordSelector(Ctx, "setObject", "forKeyedSubscript")), + SetObjectForKeySel(getKeywordSelector(Ctx, "setObject", "forKey")) {} + + ProgramStateRef evalAssume(ProgramStateRef State, + SVal Cond, + bool Assumption) const { + const SymbolRef CondS = Cond.getAsSymbol(); + if (!CondS || CondS->computeComplexity() > ComplexityThreshold) + return State; + + for (auto B=CondS->symbol_begin(), E=CondS->symbol_end(); B != E; ++B) { + const SymbolRef Antecedent = *B; + State = addImplication(Antecedent, State, true); + State = addImplication(Antecedent, State, false); + } + + return State; + } + + void checkPostCall(const CallEvent &Call, CheckerContext &C) const { + // Only trust annotations for system headers for non-protocols. + if (!Call.isInSystemHeader()) + return; + + ProgramStateRef State = C.getState(); + + if (isNonNullPtr(Call, C)) + if (auto L = Call.getReturnValue().getAs<Loc>()) + State = State->assume(*L, /*Assumption=*/true); + + C.addTransition(State); + } + + void checkPostObjCMessage(const ObjCMethodCall &Msg, + CheckerContext &C) const { + const ObjCInterfaceDecl *ID = Msg.getReceiverInterface(); + if (!ID) + return; + + ProgramStateRef State = C.getState(); + + // Index to setter for NSMutableDictionary is assumed to be non-null, + // as an exception is thrown otherwise. + if (interfaceHasSuperclass(ID, "NSMutableDictionary") && + (Msg.getSelector() == SetObjectForKeyedSubscriptSel || + Msg.getSelector() == SetObjectForKeySel)) { + if (auto L = Msg.getArgSVal(1).getAs<Loc>()) + State = State->assume(*L, /*Assumption=*/true); + } + + // Record an implication: index is non-null if the output is non-null. + if (interfaceHasSuperclass(ID, "NSDictionary") && + (Msg.getSelector() == ObjectForKeyedSubscriptSel || + Msg.getSelector() == ObjectForKeySel)) { + SymbolRef ArgS = Msg.getArgSVal(0).getAsSymbol(); + SymbolRef RetS = Msg.getReturnValue().getAsSymbol(); + + if (ArgS && RetS) { + // Emulate an implication: the argument is non-null if + // the return value is non-null. + State = State->set<NonNullImplicationMap>(RetS, ArgS); + + // Conversely, when the argument is null, the return value + // is definitely null. + State = State->set<NullImplicationMap>(ArgS, RetS); + } + } + + C.addTransition(State); + } + + void checkDeadSymbols(SymbolReaper &SymReaper, CheckerContext &C) const { + ProgramStateRef State = C.getState(); + + State = dropDeadFromGDM<NullImplicationMap>(SymReaper, State); + State = dropDeadFromGDM<NonNullImplicationMap>(SymReaper, State); + + C.addTransition(State); + } + private: + + /// \returns State with GDM \p MapName where all dead symbols were + // removed. + template <typename MapName> + ProgramStateRef dropDeadFromGDM(SymbolReaper &SymReaper, + ProgramStateRef State) const { + for (const std::pair<SymbolRef, SymbolRef> &P : State->get<MapName>()) + if (!SymReaper.isLive(P.first) || !SymReaper.isLive(P.second)) + State = State->remove<MapName>(P.first); + return State; + } + /// \returns Whether we trust the result of the method call to be /// a non-null pointer. bool isNonNullPtr(const CallEvent &Call, CheckerContext &C) const { @@ -66,19 +193,51 @@ private: return false; } -public: - void checkPostCall(const CallEvent &Call, CheckerContext &C) const { - // Only trust annotations for system headers for non-protocols. - if (!Call.isInSystemHeader()) - return; + /// \return Whether \p ID has a superclass by the name \p ClassName. + bool interfaceHasSuperclass(const ObjCInterfaceDecl *ID, + StringRef ClassName) const { + if (ID->getIdentifier()->getName() == ClassName) + return true; - ProgramStateRef State = C.getState(); + if (const ObjCInterfaceDecl *Super = ID->getSuperClass()) + return interfaceHasSuperclass(Super, ClassName); - if (isNonNullPtr(Call, C)) - if (auto L = Call.getReturnValue().getAs<Loc>()) - State = State->assume(*L, /*Assumption=*/true); + return false; + } - C.addTransition(State); + + /// \return a state with an optional implication added (if exists) + /// from a map of recorded implications. + /// If \p Negated is true, checks NullImplicationMap, and assumes + /// the negation of \p Antecedent. + /// Checks NonNullImplicationMap and assumes \p Antecedent otherwise. + ProgramStateRef addImplication(SymbolRef Antecedent, + ProgramStateRef State, + bool Negated) const { + SValBuilder &SVB = State->getStateManager().getSValBuilder(); + const SymbolRef *Consequent = + Negated ? State->get<NonNullImplicationMap>(Antecedent) + : State->get<NullImplicationMap>(Antecedent); + if (!Consequent) + return State; + + SVal AntecedentV = SVB.makeSymbolVal(Antecedent); + if ((Negated && State->isNonNull(AntecedentV).isConstrainedTrue()) + || (!Negated && State->isNull(AntecedentV).isConstrainedTrue())) { + SVal ConsequentS = SVB.makeSymbolVal(*Consequent); + State = State->assume(ConsequentS.castAs<DefinedSVal>(), Negated); + + // Drop implications from the map. + if (Negated) { + State = State->remove<NonNullImplicationMap>(Antecedent); + State = State->remove<NullImplicationMap>(*Consequent); + } else { + State = State->remove<NullImplicationMap>(Antecedent); + State = State->remove<NonNullImplicationMap>(*Consequent); + } + } + + return State; } }; @@ -86,5 +245,5 @@ public: void ento::registerTrustNonnullChecker(CheckerManager &Mgr) { - Mgr.registerChecker<TrustNonnullChecker>(); + Mgr.registerChecker<TrustNonnullChecker>(Mgr.getASTContext()); } Modified: cfe/trunk/test/Analysis/Inputs/system-header-simulator-for-nullability.h URL: http://llvm.org/viewvc/llvm-project/cfe/trunk/test/Analysis/Inputs/system-header-simulator-for-nullability.h?rev=339482&r1=339481&r2=339482&view=diff ============================================================================== --- cfe/trunk/test/Analysis/Inputs/system-header-simulator-for-nullability.h (original) +++ cfe/trunk/test/Analysis/Inputs/system-header-simulator-for-nullability.h Fri Aug 10 15:27:04 2018 @@ -9,6 +9,8 @@ NS_ASSUME_NONNULL_BEGIN typedef struct _NSZone NSZone; +typedef unsigned long NSUInteger; +@class NSCoder, NSEnumerator; @protocol NSObject + (instancetype)alloc; @@ -24,6 +26,22 @@ typedef struct _NSZone NSZone; - (id)mutableCopyWithZone:(nullable NSZone *)zone; @end +@protocol NSCoding +- (void)encodeWithCoder:(NSCoder *)aCoder; +@end + +@protocol NSSecureCoding <NSCoding> +@required ++ (BOOL)supportsSecureCoding; +@end + +typedef struct { + unsigned long state; + id *itemsPtr; + unsigned long *mutationsPtr; + unsigned long extra[5]; +} NSFastEnumerationState; + __attribute__((objc_root_class)) @interface NSObject<NSObject> @@ -52,3 +70,36 @@ NSString* _Nonnull getString(); @end NS_ASSUME_NONNULL_END + +@interface NSDictionary : NSObject <NSCopying, NSMutableCopying, NSSecureCoding> + +- (NSUInteger)count; +- (id)objectForKey:(id)aKey; +- (NSEnumerator *)keyEnumerator; +- (id)objectForKeyedSubscript:(id)aKey; + +@end + +@interface NSDictionary (NSDictionaryCreation) + ++ (id)dictionary; ++ (id)dictionaryWithObject:(id)object forKey:(id <NSCopying>)key; ++ (instancetype)dictionaryWithObjects:(const id [])objects forKeys:(const id <NSCopying> [])keys count:(NSUInteger)cnt; + +@end + +@interface NSMutableDictionary : NSDictionary + +- (void)removeObjectForKey:(id)aKey; +- (void)setObject:(id)anObject forKey:(id <NSCopying>)aKey; + +@end + +@interface NSMutableDictionary (NSExtendedMutableDictionary) + +- (void)addEntriesFromDictionary:(NSDictionary *)otherDictionary; +- (void)removeAllObjects; +- (void)setDictionary:(NSDictionary *)otherDictionary; +- (void)setObject:(id)obj forKeyedSubscript:(id <NSCopying>)key __attribute__((availability(macosx,introduced=10.8))); + +@end Modified: cfe/trunk/test/Analysis/trustnonnullchecker_test.m URL: http://llvm.org/viewvc/llvm-project/cfe/trunk/test/Analysis/trustnonnullchecker_test.m?rev=339482&r1=339481&r2=339482&view=diff ============================================================================== --- cfe/trunk/test/Analysis/trustnonnullchecker_test.m (original) +++ cfe/trunk/test/Analysis/trustnonnullchecker_test.m Fri Aug 10 15:27:04 2018 @@ -1,7 +1,9 @@ -// RUN: %clang_analyze_cc1 -fblocks -analyze -analyzer-checker=core,nullability,apiModeling -verify %s +// RUN: %clang_analyze_cc1 -fblocks -analyze -analyzer-checker=core,nullability,apiModeling,debug.ExprInspection -verify %s #include "Inputs/system-header-simulator-for-nullability.h" +void clang_analyzer_warnIfReached(); + NSString* _Nonnull trust_nonnull_framework_annotation() { NSString* out = [NSString generateString]; if (out) {} @@ -67,3 +69,104 @@ NSString * _Nonnull distrustProtocol(id< return out; // expected-warning{{}} } +// If the return value is non-nil, the index is non-nil. +NSString *_Nonnull retImpliesIndex(NSString *s, + NSDictionary *dic) { + id obj = dic[s]; + if (s) {} + if (obj) + return s; // no-warning + return @"foo"; +} + +NSString *_Nonnull retImpliesIndexOtherMethod(NSString *s, + NSDictionary *dic) { + id obj = [dic objectForKey:s]; + if (s) {} + if (obj) + return s; // no-warning + return @"foo"; +} + +NSString *_Nonnull retImpliesIndexOnRHS(NSString *s, + NSDictionary *dic) { + id obj = dic[s]; + if (s) {} + if (nil != obj) + return s; // no-warning + return @"foo"; +} + +NSString *_Nonnull retImpliesIndexReverseCheck(NSString *s, + NSDictionary *dic) { + id obj = dic[s]; + if (s) {} + if (!obj) + return @"foo"; + return s; // no-warning +} + +NSString *_Nonnull retImpliesIndexReverseCheckOnRHS(NSString *s, + NSDictionary *dic) { + id obj = dic[s]; + if (s) {} + if (nil == obj) + return @"foo"; + return s; // no-warning +} + +NSString *_Nonnull retImpliesIndexWrongBranch(NSString *s, + NSDictionary *dic) { + id obj = dic[s]; + if (s) {} + if (!obj) + return s; // expected-warning{{}} + return @"foo"; +} + +NSString *_Nonnull retImpliesIndexWrongBranchOnRHS(NSString *s, + NSDictionary *dic) { + id obj = dic[s]; + if (s) {} + if (nil == obj) + return s; // expected-warning{{}} + return @"foo"; +} + +// The return value could still be nil for a non-nil index. +NSDictionary *_Nonnull indexDoesNotImplyRet(NSString *s, + NSDictionary *dic) { + id obj = dic[s]; + if (obj) {} + if (s) + return obj; // expected-warning{{}} + return [[NSDictionary alloc] init]; +} + +// The return value could still be nil for a non-nil index. +NSDictionary *_Nonnull notIndexImpliesNotRet(NSString *s, + NSDictionary *dic) { + id obj = dic[s]; + if (!s) { + if (obj != nil) { + clang_analyzer_warnIfReached(); // no-warning + } + } + return [[NSDictionary alloc] init]; +} + +NSString *_Nonnull checkAssumeOnMutableDictionary(NSMutableDictionary *d, + NSString *k, + NSString *val) { + d[k] = val; + if (k) {} + return k; // no-warning +} + +NSString *_Nonnull checkAssumeOnMutableDictionaryOtherMethod(NSMutableDictionary *d, + NSString *k, + NSString *val) { + [d setObject:val forKey:k]; + if (k) {} + return k; // no-warning +} _______________________________________________ cfe-commits mailing list cfe-commits@lists.llvm.org http://lists.llvm.org/cgi-bin/mailman/listinfo/cfe-commits
