106f32e7eSjoerg //== TrustNonnullChecker.cpp --------- API nullability modeling -*- C++ -*--==//
206f32e7eSjoerg //
306f32e7eSjoerg // Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.
406f32e7eSjoerg // See https://llvm.org/LICENSE.txt for license information.
506f32e7eSjoerg // SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception
606f32e7eSjoerg //
706f32e7eSjoerg //===----------------------------------------------------------------------===//
806f32e7eSjoerg //
906f32e7eSjoerg // This checker adds nullability-related assumptions:
1006f32e7eSjoerg //
1106f32e7eSjoerg // 1. Methods annotated with _Nonnull
1206f32e7eSjoerg // which come from system headers actually return a non-null pointer.
1306f32e7eSjoerg //
1406f32e7eSjoerg // 2. NSDictionary key is non-null after the keyword subscript operation
1506f32e7eSjoerg // on read if and only if the resulting expression is non-null.
1606f32e7eSjoerg //
1706f32e7eSjoerg // 3. NSMutableDictionary index is non-null after a write operation.
1806f32e7eSjoerg //
1906f32e7eSjoerg //===----------------------------------------------------------------------===//
2006f32e7eSjoerg
2106f32e7eSjoerg #include "clang/StaticAnalyzer/Checkers/BuiltinCheckerRegistration.h"
2206f32e7eSjoerg #include "clang/Analysis/SelectorExtras.h"
2306f32e7eSjoerg #include "clang/StaticAnalyzer/Core/Checker.h"
2406f32e7eSjoerg #include "clang/StaticAnalyzer/Core/CheckerManager.h"
2506f32e7eSjoerg #include "clang/StaticAnalyzer/Core/PathSensitive/CheckerContext.h"
2606f32e7eSjoerg #include "clang/StaticAnalyzer/Core/PathSensitive/CheckerHelpers.h"
2706f32e7eSjoerg #include "clang/StaticAnalyzer/Core/PathSensitive/CallEvent.h"
2806f32e7eSjoerg
2906f32e7eSjoerg using namespace clang;
3006f32e7eSjoerg using namespace ento;
3106f32e7eSjoerg
3206f32e7eSjoerg /// Records implications between symbols.
3306f32e7eSjoerg /// The semantics is:
3406f32e7eSjoerg /// (antecedent != 0) => (consequent != 0)
3506f32e7eSjoerg /// These implications are then read during the evaluation of the assumption,
3606f32e7eSjoerg /// and the appropriate antecedents are applied.
3706f32e7eSjoerg REGISTER_MAP_WITH_PROGRAMSTATE(NonNullImplicationMap, SymbolRef, SymbolRef)
3806f32e7eSjoerg
3906f32e7eSjoerg /// The semantics is:
4006f32e7eSjoerg /// (antecedent == 0) => (consequent == 0)
4106f32e7eSjoerg REGISTER_MAP_WITH_PROGRAMSTATE(NullImplicationMap, SymbolRef, SymbolRef)
4206f32e7eSjoerg
4306f32e7eSjoerg namespace {
4406f32e7eSjoerg
4506f32e7eSjoerg class TrustNonnullChecker : public Checker<check::PostCall,
4606f32e7eSjoerg check::PostObjCMessage,
4706f32e7eSjoerg check::DeadSymbols,
4806f32e7eSjoerg eval::Assume> {
4906f32e7eSjoerg // Do not try to iterate over symbols with higher complexity.
5006f32e7eSjoerg static unsigned constexpr ComplexityThreshold = 10;
5106f32e7eSjoerg Selector ObjectForKeyedSubscriptSel;
5206f32e7eSjoerg Selector ObjectForKeySel;
5306f32e7eSjoerg Selector SetObjectForKeyedSubscriptSel;
5406f32e7eSjoerg Selector SetObjectForKeySel;
5506f32e7eSjoerg
5606f32e7eSjoerg public:
TrustNonnullChecker(ASTContext & Ctx)5706f32e7eSjoerg TrustNonnullChecker(ASTContext &Ctx)
5806f32e7eSjoerg : ObjectForKeyedSubscriptSel(
5906f32e7eSjoerg getKeywordSelector(Ctx, "objectForKeyedSubscript")),
6006f32e7eSjoerg ObjectForKeySel(getKeywordSelector(Ctx, "objectForKey")),
6106f32e7eSjoerg SetObjectForKeyedSubscriptSel(
6206f32e7eSjoerg getKeywordSelector(Ctx, "setObject", "forKeyedSubscript")),
6306f32e7eSjoerg SetObjectForKeySel(getKeywordSelector(Ctx, "setObject", "forKey")) {}
6406f32e7eSjoerg
evalAssume(ProgramStateRef State,SVal Cond,bool Assumption) const6506f32e7eSjoerg ProgramStateRef evalAssume(ProgramStateRef State,
6606f32e7eSjoerg SVal Cond,
6706f32e7eSjoerg bool Assumption) const {
6806f32e7eSjoerg const SymbolRef CondS = Cond.getAsSymbol();
6906f32e7eSjoerg if (!CondS || CondS->computeComplexity() > ComplexityThreshold)
7006f32e7eSjoerg return State;
7106f32e7eSjoerg
7206f32e7eSjoerg for (auto B=CondS->symbol_begin(), E=CondS->symbol_end(); B != E; ++B) {
7306f32e7eSjoerg const SymbolRef Antecedent = *B;
7406f32e7eSjoerg State = addImplication(Antecedent, State, true);
7506f32e7eSjoerg State = addImplication(Antecedent, State, false);
7606f32e7eSjoerg }
7706f32e7eSjoerg
7806f32e7eSjoerg return State;
7906f32e7eSjoerg }
8006f32e7eSjoerg
checkPostCall(const CallEvent & Call,CheckerContext & C) const8106f32e7eSjoerg void checkPostCall(const CallEvent &Call, CheckerContext &C) const {
8206f32e7eSjoerg // Only trust annotations for system headers for non-protocols.
8306f32e7eSjoerg if (!Call.isInSystemHeader())
8406f32e7eSjoerg return;
8506f32e7eSjoerg
8606f32e7eSjoerg ProgramStateRef State = C.getState();
8706f32e7eSjoerg
8806f32e7eSjoerg if (isNonNullPtr(Call, C))
8906f32e7eSjoerg if (auto L = Call.getReturnValue().getAs<Loc>())
9006f32e7eSjoerg State = State->assume(*L, /*assumption=*/true);
9106f32e7eSjoerg
9206f32e7eSjoerg C.addTransition(State);
9306f32e7eSjoerg }
9406f32e7eSjoerg
checkPostObjCMessage(const ObjCMethodCall & Msg,CheckerContext & C) const9506f32e7eSjoerg void checkPostObjCMessage(const ObjCMethodCall &Msg,
9606f32e7eSjoerg CheckerContext &C) const {
9706f32e7eSjoerg const ObjCInterfaceDecl *ID = Msg.getReceiverInterface();
9806f32e7eSjoerg if (!ID)
9906f32e7eSjoerg return;
10006f32e7eSjoerg
10106f32e7eSjoerg ProgramStateRef State = C.getState();
10206f32e7eSjoerg
10306f32e7eSjoerg // Index to setter for NSMutableDictionary is assumed to be non-null,
10406f32e7eSjoerg // as an exception is thrown otherwise.
10506f32e7eSjoerg if (interfaceHasSuperclass(ID, "NSMutableDictionary") &&
10606f32e7eSjoerg (Msg.getSelector() == SetObjectForKeyedSubscriptSel ||
10706f32e7eSjoerg Msg.getSelector() == SetObjectForKeySel)) {
10806f32e7eSjoerg if (auto L = Msg.getArgSVal(1).getAs<Loc>())
10906f32e7eSjoerg State = State->assume(*L, /*assumption=*/true);
11006f32e7eSjoerg }
11106f32e7eSjoerg
11206f32e7eSjoerg // Record an implication: index is non-null if the output is non-null.
11306f32e7eSjoerg if (interfaceHasSuperclass(ID, "NSDictionary") &&
11406f32e7eSjoerg (Msg.getSelector() == ObjectForKeyedSubscriptSel ||
11506f32e7eSjoerg Msg.getSelector() == ObjectForKeySel)) {
11606f32e7eSjoerg SymbolRef ArgS = Msg.getArgSVal(0).getAsSymbol();
11706f32e7eSjoerg SymbolRef RetS = Msg.getReturnValue().getAsSymbol();
11806f32e7eSjoerg
11906f32e7eSjoerg if (ArgS && RetS) {
12006f32e7eSjoerg // Emulate an implication: the argument is non-null if
12106f32e7eSjoerg // the return value is non-null.
12206f32e7eSjoerg State = State->set<NonNullImplicationMap>(RetS, ArgS);
12306f32e7eSjoerg
12406f32e7eSjoerg // Conversely, when the argument is null, the return value
12506f32e7eSjoerg // is definitely null.
12606f32e7eSjoerg State = State->set<NullImplicationMap>(ArgS, RetS);
12706f32e7eSjoerg }
12806f32e7eSjoerg }
12906f32e7eSjoerg
13006f32e7eSjoerg C.addTransition(State);
13106f32e7eSjoerg }
13206f32e7eSjoerg
checkDeadSymbols(SymbolReaper & SymReaper,CheckerContext & C) const13306f32e7eSjoerg void checkDeadSymbols(SymbolReaper &SymReaper, CheckerContext &C) const {
13406f32e7eSjoerg ProgramStateRef State = C.getState();
13506f32e7eSjoerg
13606f32e7eSjoerg State = dropDeadFromGDM<NullImplicationMap>(SymReaper, State);
13706f32e7eSjoerg State = dropDeadFromGDM<NonNullImplicationMap>(SymReaper, State);
13806f32e7eSjoerg
13906f32e7eSjoerg C.addTransition(State);
14006f32e7eSjoerg }
14106f32e7eSjoerg
14206f32e7eSjoerg private:
14306f32e7eSjoerg
14406f32e7eSjoerg /// \returns State with GDM \p MapName where all dead symbols were
14506f32e7eSjoerg // removed.
14606f32e7eSjoerg template <typename MapName>
dropDeadFromGDM(SymbolReaper & SymReaper,ProgramStateRef State) const14706f32e7eSjoerg ProgramStateRef dropDeadFromGDM(SymbolReaper &SymReaper,
14806f32e7eSjoerg ProgramStateRef State) const {
14906f32e7eSjoerg for (const std::pair<SymbolRef, SymbolRef> &P : State->get<MapName>())
15006f32e7eSjoerg if (!SymReaper.isLive(P.first) || !SymReaper.isLive(P.second))
15106f32e7eSjoerg State = State->remove<MapName>(P.first);
15206f32e7eSjoerg return State;
15306f32e7eSjoerg }
15406f32e7eSjoerg
15506f32e7eSjoerg /// \returns Whether we trust the result of the method call to be
15606f32e7eSjoerg /// a non-null pointer.
isNonNullPtr(const CallEvent & Call,CheckerContext & C) const15706f32e7eSjoerg bool isNonNullPtr(const CallEvent &Call, CheckerContext &C) const {
15806f32e7eSjoerg QualType ExprRetType = Call.getResultType();
15906f32e7eSjoerg if (!ExprRetType->isAnyPointerType())
16006f32e7eSjoerg return false;
16106f32e7eSjoerg
16206f32e7eSjoerg if (getNullabilityAnnotation(ExprRetType) == Nullability::Nonnull)
16306f32e7eSjoerg return true;
16406f32e7eSjoerg
16506f32e7eSjoerg // The logic for ObjC instance method calls is more complicated,
16606f32e7eSjoerg // as the return value is nil when the receiver is nil.
16706f32e7eSjoerg if (!isa<ObjCMethodCall>(&Call))
16806f32e7eSjoerg return false;
16906f32e7eSjoerg
17006f32e7eSjoerg const auto *MCall = cast<ObjCMethodCall>(&Call);
17106f32e7eSjoerg const ObjCMethodDecl *MD = MCall->getDecl();
17206f32e7eSjoerg
17306f32e7eSjoerg // Distrust protocols.
17406f32e7eSjoerg if (isa<ObjCProtocolDecl>(MD->getDeclContext()))
17506f32e7eSjoerg return false;
17606f32e7eSjoerg
17706f32e7eSjoerg QualType DeclRetType = MD->getReturnType();
17806f32e7eSjoerg if (getNullabilityAnnotation(DeclRetType) != Nullability::Nonnull)
17906f32e7eSjoerg return false;
18006f32e7eSjoerg
18106f32e7eSjoerg // For class messages it is sufficient for the declaration to be
18206f32e7eSjoerg // annotated _Nonnull.
18306f32e7eSjoerg if (!MCall->isInstanceMessage())
18406f32e7eSjoerg return true;
18506f32e7eSjoerg
18606f32e7eSjoerg // Alternatively, the analyzer could know that the receiver is not null.
18706f32e7eSjoerg SVal Receiver = MCall->getReceiverSVal();
18806f32e7eSjoerg ConditionTruthVal TV = C.getState()->isNonNull(Receiver);
18906f32e7eSjoerg if (TV.isConstrainedTrue())
19006f32e7eSjoerg return true;
19106f32e7eSjoerg
19206f32e7eSjoerg return false;
19306f32e7eSjoerg }
19406f32e7eSjoerg
19506f32e7eSjoerg /// \return Whether \p ID has a superclass by the name \p ClassName.
interfaceHasSuperclass(const ObjCInterfaceDecl * ID,StringRef ClassName) const19606f32e7eSjoerg bool interfaceHasSuperclass(const ObjCInterfaceDecl *ID,
19706f32e7eSjoerg StringRef ClassName) const {
19806f32e7eSjoerg if (ID->getIdentifier()->getName() == ClassName)
19906f32e7eSjoerg return true;
20006f32e7eSjoerg
20106f32e7eSjoerg if (const ObjCInterfaceDecl *Super = ID->getSuperClass())
20206f32e7eSjoerg return interfaceHasSuperclass(Super, ClassName);
20306f32e7eSjoerg
20406f32e7eSjoerg return false;
20506f32e7eSjoerg }
20606f32e7eSjoerg
20706f32e7eSjoerg
20806f32e7eSjoerg /// \return a state with an optional implication added (if exists)
20906f32e7eSjoerg /// from a map of recorded implications.
21006f32e7eSjoerg /// If \p Negated is true, checks NullImplicationMap, and assumes
21106f32e7eSjoerg /// the negation of \p Antecedent.
21206f32e7eSjoerg /// Checks NonNullImplicationMap and assumes \p Antecedent otherwise.
addImplication(SymbolRef Antecedent,ProgramStateRef InputState,bool Negated) const21306f32e7eSjoerg ProgramStateRef addImplication(SymbolRef Antecedent,
21406f32e7eSjoerg ProgramStateRef InputState,
21506f32e7eSjoerg bool Negated) const {
21606f32e7eSjoerg if (!InputState)
21706f32e7eSjoerg return nullptr;
21806f32e7eSjoerg SValBuilder &SVB = InputState->getStateManager().getSValBuilder();
21906f32e7eSjoerg const SymbolRef *Consequent =
22006f32e7eSjoerg Negated ? InputState->get<NonNullImplicationMap>(Antecedent)
22106f32e7eSjoerg : InputState->get<NullImplicationMap>(Antecedent);
22206f32e7eSjoerg if (!Consequent)
22306f32e7eSjoerg return InputState;
22406f32e7eSjoerg
22506f32e7eSjoerg SVal AntecedentV = SVB.makeSymbolVal(Antecedent);
22606f32e7eSjoerg ProgramStateRef State = InputState;
22706f32e7eSjoerg
22806f32e7eSjoerg if ((Negated && InputState->isNonNull(AntecedentV).isConstrainedTrue())
22906f32e7eSjoerg || (!Negated && InputState->isNull(AntecedentV).isConstrainedTrue())) {
23006f32e7eSjoerg SVal ConsequentS = SVB.makeSymbolVal(*Consequent);
23106f32e7eSjoerg State = InputState->assume(ConsequentS.castAs<DefinedSVal>(), Negated);
23206f32e7eSjoerg if (!State)
23306f32e7eSjoerg return nullptr;
23406f32e7eSjoerg
23506f32e7eSjoerg // Drop implications from the map.
23606f32e7eSjoerg if (Negated) {
23706f32e7eSjoerg State = State->remove<NonNullImplicationMap>(Antecedent);
23806f32e7eSjoerg State = State->remove<NullImplicationMap>(*Consequent);
23906f32e7eSjoerg } else {
24006f32e7eSjoerg State = State->remove<NullImplicationMap>(Antecedent);
24106f32e7eSjoerg State = State->remove<NonNullImplicationMap>(*Consequent);
24206f32e7eSjoerg }
24306f32e7eSjoerg }
24406f32e7eSjoerg
24506f32e7eSjoerg return State;
24606f32e7eSjoerg }
24706f32e7eSjoerg };
24806f32e7eSjoerg
24906f32e7eSjoerg } // end empty namespace
25006f32e7eSjoerg
registerTrustNonnullChecker(CheckerManager & Mgr)25106f32e7eSjoerg void ento::registerTrustNonnullChecker(CheckerManager &Mgr) {
25206f32e7eSjoerg Mgr.registerChecker<TrustNonnullChecker>(Mgr.getASTContext());
25306f32e7eSjoerg }
25406f32e7eSjoerg
shouldRegisterTrustNonnullChecker(const CheckerManager & mgr)255*13fbcb42Sjoerg bool ento::shouldRegisterTrustNonnullChecker(const CheckerManager &mgr) {
25606f32e7eSjoerg return true;
25706f32e7eSjoerg }
258