lib/StaticAnalyzer/Checkers/RetainCountChecker/RetainCountChecker.cpp

   1 //==-- RetainCountChecker.cpp - Checks for leaks and other issues -*- C++ -*--//
   2 //
   3 //                     The LLVM Compiler Infrastructure
   4 //
   5 // This file is distributed under the University of Illinois Open Source
   6 // License. See LICENSE.TXT for details.
   7 //
   8 //===----------------------------------------------------------------------===//
   9 //
  10 //  This file defines the methods for RetainCountChecker, which implements
  11 //  a reference count checker for Core Foundation and Cocoa on (Mac OS X).
  12 //
  13 //===----------------------------------------------------------------------===//
  14
  15 #include "RetainCountChecker.h"
  16
  17 using namespace clang;
  18 using namespace ento;
  19 using namespace retaincountchecker;
  20 using llvm::StrInStrNoCase;
  21
  22 REGISTER_MAP_WITH_PROGRAMSTATE(RefBindings, SymbolRef, RefVal)
  23
  24 namespace clang {
  25 namespace ento {
  26 namespace retaincountchecker {
  27
  28 const RefVal *getRefBinding(ProgramStateRef State, SymbolRef Sym) {
  29   return State->get<RefBindings>(Sym);
  30 }
  31
  32 ProgramStateRef setRefBinding(ProgramStateRef State, SymbolRef Sym,
  33                                      RefVal Val) {
  34   assert(Sym != nullptr);
  35   return State->set<RefBindings>(Sym, Val);
  36 }
  37
  38 ProgramStateRef removeRefBinding(ProgramStateRef State, SymbolRef Sym) {
  39   return State->remove<RefBindings>(Sym);
  40 }
  41
  42 class UseAfterRelease : public RefCountBug {
  43 public:
  44   UseAfterRelease(const CheckerBase *checker)
  45       : RefCountBug(checker, "Use-after-release") {}
  46
  47   const char *getDescription() const override {
  48     return "Reference-counted object is used after it is released";
  49   }
  50 };
  51
  52 class BadRelease : public RefCountBug {
  53 public:
  54   BadRelease(const CheckerBase *checker) : RefCountBug(checker, "Bad release") {}
  55
  56   const char *getDescription() const override {
  57     return "Incorrect decrement of the reference count of an object that is "
  58            "not owned at this point by the caller";
  59   }
  60 };
  61
  62 class DeallocNotOwned : public RefCountBug {
  63 public:
  64   DeallocNotOwned(const CheckerBase *checker)
  65       : RefCountBug(checker, "-dealloc sent to non-exclusively owned object") {}
  66
  67   const char *getDescription() const override {
  68     return "-dealloc sent to object that may be referenced elsewhere";
  69   }
  70 };
  71
  72 class OverAutorelease : public RefCountBug {
  73 public:
  74   OverAutorelease(const CheckerBase *checker)
  75       : RefCountBug(checker, "Object autoreleased too many times") {}
  76
  77   const char *getDescription() const override {
  78     return "Object autoreleased too many times";
  79   }
  80 };
  81
  82 class ReturnedNotOwnedForOwned : public RefCountBug {
  83 public:
  84   ReturnedNotOwnedForOwned(const CheckerBase *checker)
  85       : RefCountBug(checker, "Method should return an owned object") {}
  86
  87   const char *getDescription() const override {
  88     return "Object with a +0 retain count returned to caller where a +1 "
  89            "(owning) retain count is expected";
  90   }
  91 };
  92
  93 class Leak : public RefCountBug {
  94 public:
  95   Leak(const CheckerBase *checker, StringRef name) : RefCountBug(checker, name) {
  96     // Leaks should not be reported if they are post-dominated by a sink.
  97     setSuppressOnSink(true);
  98   }
  99
 100   const char *getDescription() const override { return ""; }
 101
 102   bool isLeak() const override { return true; }
 103 };
 104
 105 } // end namespace retaincountchecker
 106 } // end namespace ento
 107 } // end namespace clang
 108
 109 void RefVal::print(raw_ostream &Out) const {
 110   if (!T.isNull())
 111     Out << "Tracked " << T.getAsString() << " | ";
 112
 113   switch (getKind()) {
 114     default: llvm_unreachable("Invalid RefVal kind");
 115     case Owned: {
 116       Out << "Owned";
 117       unsigned cnt = getCount();
 118       if (cnt) Out << " (+ " << cnt << ")";
 119       break;
 120     }
 121
 122     case NotOwned: {
 123       Out << "NotOwned";
 124       unsigned cnt = getCount();
 125       if (cnt) Out << " (+ " << cnt << ")";
 126       break;
 127     }
 128
 129     case ReturnedOwned: {
 130       Out << "ReturnedOwned";
 131       unsigned cnt = getCount();
 132       if (cnt) Out << " (+ " << cnt << ")";
 133       break;
 134     }
 135
 136     case ReturnedNotOwned: {
 137       Out << "ReturnedNotOwned";
 138       unsigned cnt = getCount();
 139       if (cnt) Out << " (+ " << cnt << ")";
 140       break;
 141     }
 142
 143     case Released:
 144       Out << "Released";
 145       break;
 146
 147     case ErrorDeallocNotOwned:
 148       Out << "-dealloc (not-owned)";
 149       break;
 150
 151     case ErrorLeak:
 152       Out << "Leaked";
 153       break;
 154
 155     case ErrorLeakReturned:
 156       Out << "Leaked (Bad naming)";
 157       break;
 158
 159     case ErrorUseAfterRelease:
 160       Out << "Use-After-Release [ERROR]";
 161       break;
 162
 163     case ErrorReleaseNotOwned:
 164       Out << "Release of Not-Owned [ERROR]";
 165       break;
 166
 167     case RefVal::ErrorOverAutorelease:
 168       Out << "Over-autoreleased";
 169       break;
 170
 171     case RefVal::ErrorReturnedNotOwned:
 172       Out << "Non-owned object returned instead of owned";
 173       break;
 174   }
 175
 176   switch (getIvarAccessHistory()) {
 177   case IvarAccessHistory::None:
 178     break;
 179   case IvarAccessHistory::AccessedDirectly:
 180     Out << " [direct ivar access]";
 181     break;
 182   case IvarAccessHistory::ReleasedAfterDirectAccess:
 183     Out << " [released after direct ivar access]";
 184   }
 185
 186   if (ACnt) {
 187     Out << " [autorelease -" << ACnt << ']';
 188   }
 189 }
 190
 191 namespace {
 192 class StopTrackingCallback final : public SymbolVisitor {
 193   ProgramStateRef state;
 194 public:
 195   StopTrackingCallback(ProgramStateRef st) : state(std::move(st)) {}
 196   ProgramStateRef getState() const { return state; }
 197
 198   bool VisitSymbol(SymbolRef sym) override {
 199     state = state->remove<RefBindings>(sym);
 200     return true;
 201   }
 202 };
 203 } // end anonymous namespace
 204
 205 //===----------------------------------------------------------------------===//
 206 // Handle statements that may have an effect on refcounts.
 207 //===----------------------------------------------------------------------===//
 208
 209 void RetainCountChecker::checkPostStmt(const BlockExpr *BE,
 210                                        CheckerContext &C) const {
 211
 212   // Scan the BlockDecRefExprs for any object the retain count checker
 213   // may be tracking.
 214   if (!BE->getBlockDecl()->hasCaptures())
 215     return;
 216
 217   ProgramStateRef state = C.getState();
 218   auto *R = cast<BlockDataRegion>(C.getSVal(BE).getAsRegion());
 219
 220   BlockDataRegion::referenced_vars_iterator I = R->referenced_vars_begin(),
 221                                             E = R->referenced_vars_end();
 222
 223   if (I == E)
 224     return;
 225
 226   // FIXME: For now we invalidate the tracking of all symbols passed to blocks
 227   // via captured variables, even though captured variables result in a copy
 228   // and in implicit increment/decrement of a retain count.
 229   SmallVector<const MemRegion*, 10> Regions;
 230   const LocationContext *LC = C.getLocationContext();
 231   MemRegionManager &MemMgr = C.getSValBuilder().getRegionManager();
 232
 233   for ( ; I != E; ++I) {
 234     const VarRegion *VR = I.getCapturedRegion();
 235     if (VR->getSuperRegion() == R) {
 236       VR = MemMgr.getVarRegion(VR->getDecl(), LC);
 237     }
 238     Regions.push_back(VR);
 239   }
 240
 241   state = state->scanReachableSymbols<StopTrackingCallback>(Regions).getState();
 242   C.addTransition(state);
 243 }
 244
 245 void RetainCountChecker::checkPostStmt(const CastExpr *CE,
 246                                        CheckerContext &C) const {
 247   const ObjCBridgedCastExpr *BE = dyn_cast<ObjCBridgedCastExpr>(CE);
 248   if (!BE)
 249     return;
 250
 251   ArgEffect AE = ArgEffect(IncRef, ObjKind::ObjC);
 252
 253   switch (BE->getBridgeKind()) {
 254     case OBC_Bridge:
 255       // Do nothing.
 256       return;
 257     case OBC_BridgeRetained:
 258       AE = AE.withKind(IncRef);
 259       break;
 260     case OBC_BridgeTransfer:
 261       AE = AE.withKind(DecRefBridgedTransferred);
 262       break;
 263   }
 264
 265   ProgramStateRef state = C.getState();
 266   SymbolRef Sym = C.getSVal(CE).getAsLocSymbol();
 267   if (!Sym)
 268     return;
 269   const RefVal* T = getRefBinding(state, Sym);
 270   if (!T)
 271     return;
 272
 273   RefVal::Kind hasErr = (RefVal::Kind) 0;
 274   state = updateSymbol(state, Sym, *T, AE, hasErr, C);
 275
 276   if (hasErr) {
 277     // FIXME: If we get an error during a bridge cast, should we report it?
 278     return;
 279   }
 280
 281   C.addTransition(state);
 282 }
 283
 284 void RetainCountChecker::processObjCLiterals(CheckerContext &C,
 285                                              const Expr *Ex) const {
 286   ProgramStateRef state = C.getState();
 287   const ExplodedNode *pred = C.getPredecessor();
 288   for (const Stmt *Child : Ex->children()) {
 289     SVal V = pred->getSVal(Child);
 290     if (SymbolRef sym = V.getAsSymbol())
 291       if (const RefVal* T = getRefBinding(state, sym)) {
 292         RefVal::Kind hasErr = (RefVal::Kind) 0;
 293         state = updateSymbol(state, sym, *T,
 294                              ArgEffect(MayEscape, ObjKind::ObjC), hasErr, C);
 295         if (hasErr) {
 296           processNonLeakError(state, Child->getSourceRange(), hasErr, sym, C);
 297           return;
 298         }
 299       }
 300   }
 301
 302   // Return the object as autoreleased.
 303   //  RetEffect RE = RetEffect::MakeNotOwned(ObjKind::ObjC);
 304   if (SymbolRef sym =
 305         state->getSVal(Ex, pred->getLocationContext()).getAsSymbol()) {
 306     QualType ResultTy = Ex->getType();
 307     state = setRefBinding(state, sym,
 308                           RefVal::makeNotOwned(ObjKind::ObjC, ResultTy));
 309   }
 310
 311   C.addTransition(state);
 312 }
 313
 314 void RetainCountChecker::checkPostStmt(const ObjCArrayLiteral *AL,
 315                                        CheckerContext &C) const {
 316   // Apply the 'MayEscape' to all values.
 317   processObjCLiterals(C, AL);
 318 }
 319
 320 void RetainCountChecker::checkPostStmt(const ObjCDictionaryLiteral *DL,
 321                                        CheckerContext &C) const {
 322   // Apply the 'MayEscape' to all keys and values.
 323   processObjCLiterals(C, DL);
 324 }
 325
 326 void RetainCountChecker::checkPostStmt(const ObjCBoxedExpr *Ex,
 327                                        CheckerContext &C) const {
 328   const ExplodedNode *Pred = C.getPredecessor();
 329   ProgramStateRef State = Pred->getState();
 330
 331   if (SymbolRef Sym = Pred->getSVal(Ex).getAsSymbol()) {
 332     QualType ResultTy = Ex->getType();
 333     State = setRefBinding(State, Sym,
 334                           RefVal::makeNotOwned(ObjKind::ObjC, ResultTy));
 335   }
 336
 337   C.addTransition(State);
 338 }
 339
 340 void RetainCountChecker::checkPostStmt(const ObjCIvarRefExpr *IRE,
 341                                        CheckerContext &C) const {
 342   Optional<Loc> IVarLoc = C.getSVal(IRE).getAs<Loc>();
 343   if (!IVarLoc)
 344     return;
 345
 346   ProgramStateRef State = C.getState();
 347   SymbolRef Sym = State->getSVal(*IVarLoc).getAsSymbol();
 348   if (!Sym || !dyn_cast_or_null<ObjCIvarRegion>(Sym->getOriginRegion()))
 349     return;
 350
 351   // Accessing an ivar directly is unusual. If we've done that, be more
 352   // forgiving about what the surrounding code is allowed to do.
 353
 354   QualType Ty = Sym->getType();
 355   ObjKind Kind;
 356   if (Ty->isObjCRetainableType())
 357     Kind = ObjKind::ObjC;
 358   else if (coreFoundation::isCFObjectRef(Ty))
 359     Kind = ObjKind::CF;
 360   else
 361     return;
 362
 363   // If the value is already known to be nil, don't bother tracking it.
 364   ConstraintManager &CMgr = State->getConstraintManager();
 365   if (CMgr.isNull(State, Sym).isConstrainedTrue())
 366     return;
 367
 368   if (const RefVal *RV = getRefBinding(State, Sym)) {
 369     // If we've seen this symbol before, or we're only seeing it now because
 370     // of something the analyzer has synthesized, don't do anything.
 371     if (RV->getIvarAccessHistory() != RefVal::IvarAccessHistory::None ||
 372         isSynthesizedAccessor(C.getStackFrame())) {
 373       return;
 374     }
 375
 376     // Note that this value has been loaded from an ivar.
 377     C.addTransition(setRefBinding(State, Sym, RV->withIvarAccess()));
 378     return;
 379   }
 380
 381   RefVal PlusZero = RefVal::makeNotOwned(Kind, Ty);
 382
 383   // In a synthesized accessor, the effective retain count is +0.
 384   if (isSynthesizedAccessor(C.getStackFrame())) {
 385     C.addTransition(setRefBinding(State, Sym, PlusZero));
 386     return;
 387   }
 388
 389   State = setRefBinding(State, Sym, PlusZero.withIvarAccess());
 390   C.addTransition(State);
 391 }
 392
 393 void RetainCountChecker::checkPostCall(const CallEvent &Call,
 394                                        CheckerContext &C) const {
 395   RetainSummaryManager &Summaries = getSummaryManager(C);
 396
 397   // Leave null if no receiver.
 398   QualType ReceiverType;
 399   if (const auto *MC = dyn_cast<ObjCMethodCall>(&Call)) {
 400     if (MC->isInstanceMessage()) {
 401       SVal ReceiverV = MC->getReceiverSVal();
 402       if (SymbolRef Sym = ReceiverV.getAsLocSymbol())
 403         if (const RefVal *T = getRefBinding(C.getState(), Sym))
 404           ReceiverType = T->getType();
 405     }
 406   }
 407
 408   const RetainSummary *Summ = Summaries.getSummary(Call, ReceiverType);
 409
 410   if (C.wasInlined) {
 411     processSummaryOfInlined(*Summ, Call, C);
 412     return;
 413   }
 414   checkSummary(*Summ, Call, C);
 415 }
 416
 417 RefCountBug *
 418 RetainCountChecker::getLeakWithinFunctionBug(const LangOptions &LOpts) const {
 419   if (!leakWithinFunction)
 420     leakWithinFunction.reset(new Leak(this, "Leak"));
 421   return leakWithinFunction.get();
 422 }
 423
 424 RefCountBug *
 425 RetainCountChecker::getLeakAtReturnBug(const LangOptions &LOpts) const {
 426   if (!leakAtReturn)
 427     leakAtReturn.reset(new Leak(this, "Leak of returned object"));
 428   return leakAtReturn.get();
 429 }
 430
 431 /// GetReturnType - Used to get the return type of a message expression or
 432 ///  function call with the intention of affixing that type to a tracked symbol.
 433 ///  While the return type can be queried directly from RetEx, when
 434 ///  invoking class methods we augment to the return type to be that of
 435 ///  a pointer to the class (as opposed it just being id).
 436 // FIXME: We may be able to do this with related result types instead.
 437 // This function is probably overestimating.
 438 static QualType GetReturnType(const Expr *RetE, ASTContext &Ctx) {
 439   QualType RetTy = RetE->getType();
 440   // If RetE is not a message expression just return its type.
 441   // If RetE is a message expression, return its types if it is something
 442   /// more specific than id.
 443   if (const ObjCMessageExpr *ME = dyn_cast<ObjCMessageExpr>(RetE))
 444     if (const ObjCObjectPointerType *PT = RetTy->getAs<ObjCObjectPointerType>())
 445       if (PT->isObjCQualifiedIdType() || PT->isObjCIdType() ||
 446           PT->isObjCClassType()) {
 447         // At this point we know the return type of the message expression is
 448         // id, id<...>, or Class. If we have an ObjCInterfaceDecl, we know this
 449         // is a call to a class method whose type we can resolve.  In such
 450         // cases, promote the return type to XXX* (where XXX is the class).
 451         const ObjCInterfaceDecl *D = ME->getReceiverInterface();
 452         return !D ? RetTy :
 453                     Ctx.getObjCObjectPointerType(Ctx.getObjCInterfaceType(D));
 454       }
 455
 456   return RetTy;
 457 }
 458
 459 static Optional<RefVal> refValFromRetEffect(RetEffect RE,
 460                                             QualType ResultTy) {
 461   if (RE.isOwned()) {
 462     return RefVal::makeOwned(RE.getObjKind(), ResultTy);
 463   } else if (RE.notOwned()) {
 464     return RefVal::makeNotOwned(RE.getObjKind(), ResultTy);
 465   }
 466
 467   return None;
 468 }
 469
 470 static bool isPointerToObject(QualType QT) {
 471   QualType PT = QT->getPointeeType();
 472   if (!PT.isNull())
 473     if (PT->getAsCXXRecordDecl())
 474       return true;
 475   return false;
 476 }
 477
 478 /// Whether the tracked value should be escaped on a given call.
 479 /// OSObjects are escaped when passed to void * / etc.
 480 static bool shouldEscapeOSArgumentOnCall(const CallEvent &CE, unsigned ArgIdx,
 481                                        const RefVal *TrackedValue) {
 482   if (TrackedValue->getObjKind() != ObjKind::OS)
 483     return false;
 484   if (ArgIdx >= CE.parameters().size())
 485     return false;
 486   return !isPointerToObject(CE.parameters()[ArgIdx]->getType());
 487 }
 488
 489 // We don't always get the exact modeling of the function with regards to the
 490 // retain count checker even when the function is inlined. For example, we need
 491 // to stop tracking the symbols which were marked with StopTrackingHard.
 492 void RetainCountChecker::processSummaryOfInlined(const RetainSummary &Summ,
 493                                                  const CallEvent &CallOrMsg,
 494                                                  CheckerContext &C) const {
 495   ProgramStateRef state = C.getState();
 496
 497   // Evaluate the effect of the arguments.
 498   for (unsigned idx = 0, e = CallOrMsg.getNumArgs(); idx != e; ++idx) {
 499     SVal V = CallOrMsg.getArgSVal(idx);
 500
 501     if (SymbolRef Sym = V.getAsLocSymbol()) {
 502       bool ShouldRemoveBinding = Summ.getArg(idx).getKind() == StopTrackingHard;
 503       if (const RefVal *T = getRefBinding(state, Sym))
 504         if (shouldEscapeOSArgumentOnCall(CallOrMsg, idx, T))
 505           ShouldRemoveBinding = true;
 506
 507       if (ShouldRemoveBinding)
 508         state = removeRefBinding(state, Sym);
 509     }
 510   }
 511
 512   // Evaluate the effect on the message receiver.
 513   if (const auto *MsgInvocation = dyn_cast<ObjCMethodCall>(&CallOrMsg)) {
 514     if (SymbolRef Sym = MsgInvocation->getReceiverSVal().getAsLocSymbol()) {
 515       if (Summ.getReceiverEffect().getKind() == StopTrackingHard) {
 516         state = removeRefBinding(state, Sym);
 517       }
 518     }
 519   }
 520
 521   // Consult the summary for the return value.
 522   RetEffect RE = Summ.getRetEffect();
 523
 524   if (SymbolRef Sym = CallOrMsg.getReturnValue().getAsSymbol()) {
 525     if (RE.getKind() == RetEffect::NoRetHard)
 526       state = removeRefBinding(state, Sym);
 527   }
 528
 529   C.addTransition(state);
 530 }
 531
 532 static bool shouldEscapeRegion(const MemRegion *R) {
 533
 534   // We do not currently model what happens when a symbol is
 535   // assigned to a struct field, so be conservative here and let the symbol
 536   // go. TODO: This could definitely be improved upon.
 537   return !R->hasStackStorage() || !isa<VarRegion>(R);
 538 }
 539
 540 static SmallVector<ProgramStateRef, 2>
 541 updateOutParameters(ProgramStateRef State, const RetainSummary &Summ,
 542                     const CallEvent &CE) {
 543
 544   SVal L = CE.getReturnValue();
 545
 546   // Splitting is required to support out parameters,
 547   // as out parameters might be created only on the "success" branch.
 548   // We want to avoid eagerly splitting unless out parameters are actually
 549   // needed.
 550   bool SplitNecessary = false;
 551   for (auto &P : Summ.getArgEffects())
 552     if (P.second.getKind() == RetainedOutParameterOnNonZero ||
 553         P.second.getKind() == RetainedOutParameterOnZero)
 554       SplitNecessary = true;
 555
 556   ProgramStateRef AssumeNonZeroReturn = State;
 557   ProgramStateRef AssumeZeroReturn = State;
 558
 559   if (SplitNecessary) {
 560     if (auto DL = L.getAs<DefinedOrUnknownSVal>()) {
 561       AssumeNonZeroReturn = AssumeNonZeroReturn->assume(*DL, true);
 562       AssumeZeroReturn = AssumeZeroReturn->assume(*DL, false);
 563     }
 564   }
 565
 566   for (unsigned idx = 0, e = CE.getNumArgs(); idx != e; ++idx) {
 567     SVal ArgVal = CE.getArgSVal(idx);
 568     ArgEffect AE = Summ.getArg(idx);
 569
 570     auto *ArgRegion = dyn_cast_or_null<TypedValueRegion>(ArgVal.getAsRegion());
 571     if (!ArgRegion)
 572       continue;
 573
 574     QualType PointeeTy = ArgRegion->getValueType();
 575     SVal PointeeVal = State->getSVal(ArgRegion);
 576     SymbolRef Pointee = PointeeVal.getAsLocSymbol();
 577     if (!Pointee)
 578       continue;
 579
 580     if (shouldEscapeRegion(ArgRegion))
 581       continue;
 582
 583     auto makeNotOwnedParameter = [&](ProgramStateRef St) {
 584       return setRefBinding(St, Pointee,
 585                            RefVal::makeNotOwned(AE.getObjKind(), PointeeTy));
 586     };
 587     auto makeOwnedParameter = [&](ProgramStateRef St) {
 588       return setRefBinding(St, Pointee,
 589                            RefVal::makeOwned(ObjKind::OS, PointeeTy));
 590     };
 591
 592     switch (AE.getKind()) {
 593     case UnretainedOutParameter:
 594       AssumeNonZeroReturn = makeNotOwnedParameter(AssumeNonZeroReturn);
 595       AssumeZeroReturn = makeNotOwnedParameter(AssumeZeroReturn);
 596       break;
 597     case RetainedOutParameter:
 598       AssumeNonZeroReturn = makeOwnedParameter(AssumeNonZeroReturn);
 599       AssumeZeroReturn = makeOwnedParameter(AssumeZeroReturn);
 600       break;
 601     case RetainedOutParameterOnNonZero:
 602       AssumeNonZeroReturn = makeOwnedParameter(AssumeNonZeroReturn);
 603       break;
 604     case RetainedOutParameterOnZero:
 605       AssumeZeroReturn = makeOwnedParameter(AssumeZeroReturn);
 606       break;
 607     default:
 608       break;
 609     }
 610   }
 611
 612   if (SplitNecessary) {
 613     return {AssumeNonZeroReturn, AssumeZeroReturn};
 614   } else {
 615     assert(AssumeZeroReturn == AssumeNonZeroReturn);
 616     return {AssumeZeroReturn};
 617   }
 618 }
 619
 620 void RetainCountChecker::checkSummary(const RetainSummary &Summ,
 621                                       const CallEvent &CallOrMsg,
 622                                       CheckerContext &C) const {
 623   ProgramStateRef state = C.getState();
 624
 625   // Evaluate the effect of the arguments.
 626   RefVal::Kind hasErr = (RefVal::Kind) 0;
 627   SourceRange ErrorRange;
 628   SymbolRef ErrorSym = nullptr;
 629
 630   // Helper tag for providing diagnostics: indicate whether dealloc was sent
 631   // at this location.
 632   static CheckerProgramPointTag DeallocSentTag(this, DeallocTagDescription);
 633   bool DeallocSent = false;
 634
 635   for (unsigned idx = 0, e = CallOrMsg.getNumArgs(); idx != e; ++idx) {
 636     SVal V = CallOrMsg.getArgSVal(idx);
 637
 638     ArgEffect Effect = Summ.getArg(idx);
 639     if (SymbolRef Sym = V.getAsLocSymbol()) {
 640       if (const RefVal *T = getRefBinding(state, Sym)) {
 641
 642         if (shouldEscapeOSArgumentOnCall(CallOrMsg, idx, T))
 643           Effect = ArgEffect(StopTrackingHard, ObjKind::OS);
 644
 645         state = updateSymbol(state, Sym, *T, Effect, hasErr, C);
 646         if (hasErr) {
 647           ErrorRange = CallOrMsg.getArgSourceRange(idx);
 648           ErrorSym = Sym;
 649           break;
 650         } else if (Effect.getKind() == Dealloc) {
 651           DeallocSent = true;
 652         }
 653       }
 654     }
 655   }
 656
 657   // Evaluate the effect on the message receiver / `this` argument.
 658   bool ReceiverIsTracked = false;
 659   if (!hasErr) {
 660     if (const auto *MsgInvocation = dyn_cast<ObjCMethodCall>(&CallOrMsg)) {
 661       if (SymbolRef Sym = MsgInvocation->getReceiverSVal().getAsLocSymbol()) {
 662         if (const RefVal *T = getRefBinding(state, Sym)) {
 663           ReceiverIsTracked = true;
 664           state = updateSymbol(state, Sym, *T,
 665                                Summ.getReceiverEffect(), hasErr, C);
 666           if (hasErr) {
 667             ErrorRange = MsgInvocation->getOriginExpr()->getReceiverRange();
 668             ErrorSym = Sym;
 669           } else if (Summ.getReceiverEffect().getKind() == Dealloc) {
 670             DeallocSent = true;
 671           }
 672         }
 673       }
 674     } else if (const auto *MCall = dyn_cast<CXXMemberCall>(&CallOrMsg)) {
 675       if (SymbolRef Sym = MCall->getCXXThisVal().getAsLocSymbol()) {
 676         if (const RefVal *T = getRefBinding(state, Sym)) {
 677           state = updateSymbol(state, Sym, *T, Summ.getThisEffect(),
 678                                hasErr, C);
 679           if (hasErr) {
 680             ErrorRange = MCall->getOriginExpr()->getSourceRange();
 681             ErrorSym = Sym;
 682           }
 683         }
 684       }
 685     }
 686   }
 687
 688   // Process any errors.
 689   if (hasErr) {
 690     processNonLeakError(state, ErrorRange, hasErr, ErrorSym, C);
 691     return;
 692   }
 693
 694   // Consult the summary for the return value.
 695   RetEffect RE = Summ.getRetEffect();
 696
 697   if (RE.getKind() == RetEffect::OwnedWhenTrackedReceiver) {
 698     if (ReceiverIsTracked)
 699       RE = getSummaryManager(C).getObjAllocRetEffect();
 700     else
 701       RE = RetEffect::MakeNoRet();
 702   }
 703
 704   if (SymbolRef Sym = CallOrMsg.getReturnValue().getAsSymbol()) {
 705     QualType ResultTy = CallOrMsg.getResultType();
 706     if (RE.notOwned()) {
 707       const Expr *Ex = CallOrMsg.getOriginExpr();
 708       assert(Ex);
 709       ResultTy = GetReturnType(Ex, C.getASTContext());
 710     }
 711     if (Optional<RefVal> updatedRefVal = refValFromRetEffect(RE, ResultTy))
 712       state = setRefBinding(state, Sym, *updatedRefVal);
 713   }
 714
 715   SmallVector<ProgramStateRef, 2> Out =
 716       updateOutParameters(state, Summ, CallOrMsg);
 717
 718   for (ProgramStateRef St : Out) {
 719     if (DeallocSent) {
 720       C.addTransition(St, C.getPredecessor(), &DeallocSentTag);
 721     } else {
 722       C.addTransition(St);
 723     }
 724   }
 725 }
 726
 727 ProgramStateRef RetainCountChecker::updateSymbol(ProgramStateRef state,
 728                                                  SymbolRef sym, RefVal V,
 729                                                  ArgEffect AE,
 730                                                  RefVal::Kind &hasErr,
 731                                                  CheckerContext &C) const {
 732   bool IgnoreRetainMsg = (bool)C.getASTContext().getLangOpts().ObjCAutoRefCount;
 733   if (AE.getObjKind() == ObjKind::ObjC && IgnoreRetainMsg) {
 734     switch (AE.getKind()) {
 735     default:
 736       break;
 737     case IncRef:
 738       AE = AE.withKind(DoNothing);
 739       break;
 740     case DecRef:
 741       AE = AE.withKind(DoNothing);
 742       break;
 743     case DecRefAndStopTrackingHard:
 744       AE = AE.withKind(StopTracking);
 745       break;
 746     }
 747   }
 748
 749   // Handle all use-after-releases.
 750   if (V.getKind() == RefVal::Released) {
 751     V = V ^ RefVal::ErrorUseAfterRelease;
 752     hasErr = V.getKind();
 753     return setRefBinding(state, sym, V);
 754   }
 755
 756   switch (AE.getKind()) {
 757     case UnretainedOutParameter:
 758     case RetainedOutParameter:
 759     case RetainedOutParameterOnZero:
 760     case RetainedOutParameterOnNonZero:
 761       llvm_unreachable("Applies to pointer-to-pointer parameters, which should "
 762                        "not have ref state.");
 763
 764     case Dealloc: // NB. we only need to add a note in a non-error case.
 765       switch (V.getKind()) {
 766         default:
 767           llvm_unreachable("Invalid RefVal state for an explicit dealloc.");
 768         case RefVal::Owned:
 769           // The object immediately transitions to the released state.
 770           V = V ^ RefVal::Released;
 771           V.clearCounts();
 772           return setRefBinding(state, sym, V);
 773         case RefVal::NotOwned:
 774           V = V ^ RefVal::ErrorDeallocNotOwned;
 775           hasErr = V.getKind();
 776           break;
 777       }
 778       break;
 779
 780     case MayEscape:
 781       if (V.getKind() == RefVal::Owned) {
 782         V = V ^ RefVal::NotOwned;
 783         break;
 784       }
 785
 786       LLVM_FALLTHROUGH;
 787
 788     case DoNothing:
 789       return state;
 790
 791     case Autorelease:
 792       // Update the autorelease counts.
 793       V = V.autorelease();
 794       break;
 795
 796     case StopTracking:
 797     case StopTrackingHard:
 798       return removeRefBinding(state, sym);
 799
 800     case IncRef:
 801       switch (V.getKind()) {
 802         default:
 803           llvm_unreachable("Invalid RefVal state for a retain.");
 804         case RefVal::Owned:
 805         case RefVal::NotOwned:
 806           V = V + 1;
 807           break;
 808       }
 809       break;
 810
 811     case DecRef:
 812     case DecRefBridgedTransferred:
 813     case DecRefAndStopTrackingHard:
 814       switch (V.getKind()) {
 815         default:
 816           // case 'RefVal::Released' handled above.
 817           llvm_unreachable("Invalid RefVal state for a release.");
 818
 819         case RefVal::Owned:
 820           assert(V.getCount() > 0);
 821           if (V.getCount() == 1) {
 822             if (AE.getKind() == DecRefBridgedTransferred ||
 823                 V.getIvarAccessHistory() ==
 824                   RefVal::IvarAccessHistory::AccessedDirectly)
 825               V = V ^ RefVal::NotOwned;
 826             else
 827               V = V ^ RefVal::Released;
 828           } else if (AE.getKind() == DecRefAndStopTrackingHard) {
 829             return removeRefBinding(state, sym);
 830           }
 831
 832           V = V - 1;
 833           break;
 834
 835         case RefVal::NotOwned:
 836           if (V.getCount() > 0) {
 837             if (AE.getKind() == DecRefAndStopTrackingHard)
 838               return removeRefBinding(state, sym);
 839             V = V - 1;
 840           } else if (V.getIvarAccessHistory() ==
 841                        RefVal::IvarAccessHistory::AccessedDirectly) {
 842             // Assume that the instance variable was holding on the object at
 843             // +1, and we just didn't know.
 844             if (AE.getKind() == DecRefAndStopTrackingHard)
 845               return removeRefBinding(state, sym);
 846             V = V.releaseViaIvar() ^ RefVal::Released;
 847           } else {
 848             V = V ^ RefVal::ErrorReleaseNotOwned;
 849             hasErr = V.getKind();
 850           }
 851           break;
 852       }
 853       break;
 854   }
 855   return setRefBinding(state, sym, V);
 856 }
 857
 858 void RetainCountChecker::processNonLeakError(ProgramStateRef St,
 859                                              SourceRange ErrorRange,
 860                                              RefVal::Kind ErrorKind,
 861                                              SymbolRef Sym,
 862                                              CheckerContext &C) const {
 863   // HACK: Ignore retain-count issues on values accessed through ivars,
 864   // because of cases like this:
 865   //   [_contentView retain];
 866   //   [_contentView removeFromSuperview];
 867   //   [self addSubview:_contentView]; // invalidates 'self'
 868   //   [_contentView release];
 869   if (const RefVal *RV = getRefBinding(St, Sym))
 870     if (RV->getIvarAccessHistory() != RefVal::IvarAccessHistory::None)
 871       return;
 872
 873   ExplodedNode *N = C.generateErrorNode(St);
 874   if (!N)
 875     return;
 876
 877   RefCountBug *BT;
 878   switch (ErrorKind) {
 879     default:
 880       llvm_unreachable("Unhandled error.");
 881     case RefVal::ErrorUseAfterRelease:
 882       if (!useAfterRelease)
 883         useAfterRelease.reset(new UseAfterRelease(this));
 884       BT = useAfterRelease.get();
 885       break;
 886     case RefVal::ErrorReleaseNotOwned:
 887       if (!releaseNotOwned)
 888         releaseNotOwned.reset(new BadRelease(this));
 889       BT = releaseNotOwned.get();
 890       break;
 891     case RefVal::ErrorDeallocNotOwned:
 892       if (!deallocNotOwned)
 893         deallocNotOwned.reset(new DeallocNotOwned(this));
 894       BT = deallocNotOwned.get();
 895       break;
 896   }
 897
 898   assert(BT);
 899   auto report = llvm::make_unique<RefCountReport>(
 900       *BT, C.getASTContext().getLangOpts(), N, Sym);
 901   report->addRange(ErrorRange);
 902   C.emitReport(std::move(report));
 903 }
 904
 905 //===----------------------------------------------------------------------===//
 906 // Handle the return values of retain-count-related functions.
 907 //===----------------------------------------------------------------------===//
 908
 909 bool RetainCountChecker::evalCall(const CallExpr *CE, CheckerContext &C) const {
 910   // Get the callee. We're only interested in simple C functions.
 911   ProgramStateRef state = C.getState();
 912   const FunctionDecl *FD = C.getCalleeDecl(CE);
 913   if (!FD)
 914     return false;
 915
 916   RetainSummaryManager &SmrMgr = getSummaryManager(C);
 917   QualType ResultTy = CE->getCallReturnType(C.getASTContext());
 918
 919   // See if the function has 'rc_ownership_trusted_implementation'
 920   // annotate attribute. If it does, we will not inline it.
 921   bool hasTrustedImplementationAnnotation = false;
 922
 923   const LocationContext *LCtx = C.getLocationContext();
 924
 925   using BehaviorSummary = RetainSummaryManager::BehaviorSummary;
 926   Optional<BehaviorSummary> BSmr =
 927       SmrMgr.canEval(CE, FD, hasTrustedImplementationAnnotation);
 928
 929   // See if it's one of the specific functions we know how to eval.
 930   if (!BSmr)
 931     return false;
 932
 933   // Bind the return value.
 934   if (BSmr == BehaviorSummary::Identity ||
 935       BSmr == BehaviorSummary::IdentityOrZero) {
 936     SVal RetVal = state->getSVal(CE->getArg(0), LCtx);
 937
 938     // If the receiver is unknown or the function has
 939     // 'rc_ownership_trusted_implementation' annotate attribute, conjure a
 940     // return value.
 941     if (RetVal.isUnknown() ||
 942         (hasTrustedImplementationAnnotation && !ResultTy.isNull())) {
 943       SValBuilder &SVB = C.getSValBuilder();
 944       RetVal =
 945           SVB.conjureSymbolVal(nullptr, CE, LCtx, ResultTy, C.blockCount());
 946     }
 947     state = state->BindExpr(CE, LCtx, RetVal, /*Invalidate=*/false);
 948
 949     if (BSmr == BehaviorSummary::IdentityOrZero) {
 950       // Add a branch where the output is zero.
 951       ProgramStateRef NullOutputState = C.getState();
 952
 953       // Assume that output is zero on the other branch.
 954       NullOutputState = NullOutputState->BindExpr(
 955           CE, LCtx, C.getSValBuilder().makeNull(), /*Invalidate=*/false);
 956
 957       C.addTransition(NullOutputState);
 958
 959       // And on the original branch assume that both input and
 960       // output are non-zero.
 961       if (auto L = RetVal.getAs<DefinedOrUnknownSVal>())
 962         state = state->assume(*L, /*Assumption=*/true);
 963
 964     }
 965   }
 966
 967   C.addTransition(state);
 968   return true;
 969 }
 970
 971 ExplodedNode * RetainCountChecker::processReturn(const ReturnStmt *S,
 972                                                  CheckerContext &C) const {
 973   ExplodedNode *Pred = C.getPredecessor();
 974
 975   // Only adjust the reference count if this is the top-level call frame,
 976   // and not the result of inlining.  In the future, we should do
 977   // better checking even for inlined calls, and see if they match
 978   // with their expected semantics (e.g., the method should return a retained
 979   // object, etc.).
 980   if (!C.inTopFrame())
 981     return Pred;
 982
 983   if (!S)
 984     return Pred;
 985
 986   const Expr *RetE = S->getRetValue();
 987   if (!RetE)
 988     return Pred;
 989
 990   ProgramStateRef state = C.getState();
 991   SymbolRef Sym =
 992     state->getSValAsScalarOrLoc(RetE, C.getLocationContext()).getAsLocSymbol();
 993   if (!Sym)
 994     return Pred;
 995
 996   // Get the reference count binding (if any).
 997   const RefVal *T = getRefBinding(state, Sym);
 998   if (!T)
 999     return Pred;
1000
1001   // Change the reference count.
1002   RefVal X = *T;
1003
1004   switch (X.getKind()) {
1005     case RefVal::Owned: {
1006       unsigned cnt = X.getCount();
1007       assert(cnt > 0);
1008       X.setCount(cnt - 1);
1009       X = X ^ RefVal::ReturnedOwned;
1010       break;
1011     }
1012
1013     case RefVal::NotOwned: {
1014       unsigned cnt = X.getCount();
1015       if (cnt) {
1016         X.setCount(cnt - 1);
1017         X = X ^ RefVal::ReturnedOwned;
1018       } else {
1019         X = X ^ RefVal::ReturnedNotOwned;
1020       }
1021       break;
1022     }
1023
1024     default:
1025       return Pred;
1026   }
1027
1028   // Update the binding.
1029   state = setRefBinding(state, Sym, X);
1030   Pred = C.addTransition(state);
1031
1032   // At this point we have updated the state properly.
1033   // Everything after this is merely checking to see if the return value has
1034   // been over- or under-retained.
1035
1036   // Did we cache out?
1037   if (!Pred)
1038     return nullptr;
1039
1040   // Update the autorelease counts.
1041   static CheckerProgramPointTag AutoreleaseTag(this, "Autorelease");
1042   state = handleAutoreleaseCounts(state, Pred, &AutoreleaseTag, C, Sym, X, S);
1043
1044   // Have we generated a sink node?
1045   if (!state)
1046     return nullptr;
1047
1048   // Get the updated binding.
1049   T = getRefBinding(state, Sym);
1050   assert(T);
1051   X = *T;
1052
1053   // Consult the summary of the enclosing method.
1054   RetainSummaryManager &Summaries = getSummaryManager(C);
1055   const Decl *CD = &Pred->getCodeDecl();
1056   RetEffect RE = RetEffect::MakeNoRet();
1057
1058   // FIXME: What is the convention for blocks? Is there one?
1059   if (const ObjCMethodDecl *MD = dyn_cast<ObjCMethodDecl>(CD)) {
1060     const RetainSummary *Summ = Summaries.getMethodSummary(MD);
1061     RE = Summ->getRetEffect();
1062   } else if (const FunctionDecl *FD = dyn_cast<FunctionDecl>(CD)) {
1063     if (!isa<CXXMethodDecl>(FD)) {
1064       const RetainSummary *Summ = Summaries.getFunctionSummary(FD);
1065       RE = Summ->getRetEffect();
1066     }
1067   }
1068
1069   return checkReturnWithRetEffect(S, C, Pred, RE, X, Sym, state);
1070 }
1071
1072 ExplodedNode * RetainCountChecker::checkReturnWithRetEffect(const ReturnStmt *S,
1073                                                   CheckerContext &C,
1074                                                   ExplodedNode *Pred,
1075                                                   RetEffect RE, RefVal X,
1076                                                   SymbolRef Sym,
1077                                                   ProgramStateRef state) const {
1078   // HACK: Ignore retain-count issues on values accessed through ivars,
1079   // because of cases like this:
1080   //   [_contentView retain];
1081   //   [_contentView removeFromSuperview];
1082   //   [self addSubview:_contentView]; // invalidates 'self'
1083   //   [_contentView release];
1084   if (X.getIvarAccessHistory() != RefVal::IvarAccessHistory::None)
1085     return Pred;
1086
1087   // Any leaks or other errors?
1088   if (X.isReturnedOwned() && X.getCount() == 0) {
1089     if (RE.getKind() != RetEffect::NoRet) {
1090       if (!RE.isOwned()) {
1091
1092         // The returning type is a CF, we expect the enclosing method should
1093         // return ownership.
1094         X = X ^ RefVal::ErrorLeakReturned;
1095
1096         // Generate an error node.
1097         state = setRefBinding(state, Sym, X);
1098
1099         static CheckerProgramPointTag ReturnOwnLeakTag(this, "ReturnsOwnLeak");
1100         ExplodedNode *N = C.addTransition(state, Pred, &ReturnOwnLeakTag);
1101         if (N) {
1102           const LangOptions &LOpts = C.getASTContext().getLangOpts();
1103           auto R = llvm::make_unique<RefLeakReport>(
1104               *getLeakAtReturnBug(LOpts), LOpts, N, Sym, C);
1105           C.emitReport(std::move(R));
1106         }
1107         return N;
1108       }
1109     }
1110   } else if (X.isReturnedNotOwned()) {
1111     if (RE.isOwned()) {
1112       if (X.getIvarAccessHistory() ==
1113             RefVal::IvarAccessHistory::AccessedDirectly) {
1114         // Assume the method was trying to transfer a +1 reference from a
1115         // strong ivar to the caller.
1116         state = setRefBinding(state, Sym,
1117                               X.releaseViaIvar() ^ RefVal::ReturnedOwned);
1118       } else {
1119         // Trying to return a not owned object to a caller expecting an
1120         // owned object.
1121         state = setRefBinding(state, Sym, X ^ RefVal::ErrorReturnedNotOwned);
1122
1123         static CheckerProgramPointTag
1124             ReturnNotOwnedTag(this, "ReturnNotOwnedForOwned");
1125
1126         ExplodedNode *N = C.addTransition(state, Pred, &ReturnNotOwnedTag);
1127         if (N) {
1128           if (!returnNotOwnedForOwned)
1129             returnNotOwnedForOwned.reset(new ReturnedNotOwnedForOwned(this));
1130
1131           auto R = llvm::make_unique<RefCountReport>(
1132               *returnNotOwnedForOwned, C.getASTContext().getLangOpts(), N, Sym);
1133           C.emitReport(std::move(R));
1134         }
1135         return N;
1136       }
1137     }
1138   }
1139   return Pred;
1140 }
1141
1142 //===----------------------------------------------------------------------===//
1143 // Check various ways a symbol can be invalidated.
1144 //===----------------------------------------------------------------------===//
1145
1146 void RetainCountChecker::checkBind(SVal loc, SVal val, const Stmt *S,
1147                                    CheckerContext &C) const {
1148   // Are we storing to something that causes the value to "escape"?
1149   bool escapes = true;
1150
1151   // A value escapes in three possible cases (this may change):
1152   //
1153   // (1) we are binding to something that is not a memory region.
1154   // (2) we are binding to a memregion that does not have stack storage
1155   ProgramStateRef state = C.getState();
1156
1157   if (auto regionLoc = loc.getAs<loc::MemRegionVal>()) {
1158     escapes = shouldEscapeRegion(regionLoc->getRegion());
1159   }
1160
1161   // If we are storing the value into an auto function scope variable annotated
1162   // with (__attribute__((cleanup))), stop tracking the value to avoid leak
1163   // false positives.
1164   if (const auto *LVR = dyn_cast_or_null<VarRegion>(loc.getAsRegion())) {
1165     const VarDecl *VD = LVR->getDecl();
1166     if (VD->hasAttr<CleanupAttr>()) {
1167       escapes = true;
1168     }
1169   }
1170
1171   // If our store can represent the binding and we aren't storing to something
1172   // that doesn't have local storage then just return and have the simulation
1173   // state continue as is.
1174   if (!escapes)
1175       return;
1176
1177   // Otherwise, find all symbols referenced by 'val' that we are tracking
1178   // and stop tracking them.
1179   state = state->scanReachableSymbols<StopTrackingCallback>(val).getState();
1180   C.addTransition(state);
1181 }
1182
1183 ProgramStateRef RetainCountChecker::evalAssume(ProgramStateRef state,
1184                                                SVal Cond,
1185                                                bool Assumption) const {
1186   // FIXME: We may add to the interface of evalAssume the list of symbols
1187   //  whose assumptions have changed.  For now we just iterate through the
1188   //  bindings and check if any of the tracked symbols are NULL.  This isn't
1189   //  too bad since the number of symbols we will track in practice are
1190   //  probably small and evalAssume is only called at branches and a few
1191   //  other places.
1192   RefBindingsTy B = state->get<RefBindings>();
1193
1194   if (B.isEmpty())
1195     return state;
1196
1197   bool changed = false;
1198   RefBindingsTy::Factory &RefBFactory = state->get_context<RefBindings>();
1199
1200   for (RefBindingsTy::iterator I = B.begin(), E = B.end(); I != E; ++I) {
1201     // Check if the symbol is null stop tracking the symbol.
1202     ConstraintManager &CMgr = state->getConstraintManager();
1203     ConditionTruthVal AllocFailed = CMgr.isNull(state, I.getKey());
1204     if (AllocFailed.isConstrainedTrue()) {
1205       changed = true;
1206       B = RefBFactory.remove(B, I.getKey());
1207     }
1208   }
1209
1210   if (changed)
1211     state = state->set<RefBindings>(B);
1212
1213   return state;
1214 }
1215
1216 ProgramStateRef
1217 RetainCountChecker::checkRegionChanges(ProgramStateRef state,
1218                                        const InvalidatedSymbols *invalidated,
1219                                        ArrayRef<const MemRegion *> ExplicitRegions,
1220                                        ArrayRef<const MemRegion *> Regions,
1221                                        const LocationContext *LCtx,
1222                                        const CallEvent *Call) const {
1223   if (!invalidated)
1224     return state;
1225
1226   llvm::SmallPtrSet<SymbolRef, 8> WhitelistedSymbols;
1227   for (ArrayRef<const MemRegion *>::iterator I = ExplicitRegions.begin(),
1228        E = ExplicitRegions.end(); I != E; ++I) {
1229     if (const SymbolicRegion *SR = (*I)->StripCasts()->getAs<SymbolicRegion>())
1230       WhitelistedSymbols.insert(SR->getSymbol());
1231   }
1232
1233   for (SymbolRef sym :
1234        llvm::make_range(invalidated->begin(), invalidated->end())) {
1235     if (WhitelistedSymbols.count(sym))
1236       continue;
1237     // Remove any existing reference-count binding.
1238     state = removeRefBinding(state, sym);
1239   }
1240   return state;
1241 }
1242
1243 ProgramStateRef
1244 RetainCountChecker::handleAutoreleaseCounts(ProgramStateRef state,
1245                                             ExplodedNode *Pred,
1246                                             const ProgramPointTag *Tag,
1247                                             CheckerContext &Ctx,
1248                                             SymbolRef Sym,
1249                                             RefVal V,
1250                                             const ReturnStmt *S) const {
1251   unsigned ACnt = V.getAutoreleaseCount();
1252
1253   // No autorelease counts?  Nothing to be done.
1254   if (!ACnt)
1255     return state;
1256
1257   unsigned Cnt = V.getCount();
1258
1259   // FIXME: Handle sending 'autorelease' to already released object.
1260
1261   if (V.getKind() == RefVal::ReturnedOwned)
1262     ++Cnt;
1263
1264   // If we would over-release here, but we know the value came from an ivar,
1265   // assume it was a strong ivar that's just been relinquished.
1266   if (ACnt > Cnt &&
1267       V.getIvarAccessHistory() == RefVal::IvarAccessHistory::AccessedDirectly) {
1268     V = V.releaseViaIvar();
1269     --ACnt;
1270   }
1271
1272   if (ACnt <= Cnt) {
1273     if (ACnt == Cnt) {
1274       V.clearCounts();
1275       if (V.getKind() == RefVal::ReturnedOwned) {
1276         V = V ^ RefVal::ReturnedNotOwned;
1277       } else {
1278         V = V ^ RefVal::NotOwned;
1279       }
1280     } else {
1281       V.setCount(V.getCount() - ACnt);
1282       V.setAutoreleaseCount(0);
1283     }
1284     return setRefBinding(state, Sym, V);
1285   }
1286
1287   // HACK: Ignore retain-count issues on values accessed through ivars,
1288   // because of cases like this:
1289   //   [_contentView retain];
1290   //   [_contentView removeFromSuperview];
1291   //   [self addSubview:_contentView]; // invalidates 'self'
1292   //   [_contentView release];
1293   if (V.getIvarAccessHistory() != RefVal::IvarAccessHistory::None)
1294     return state;
1295
1296   // Woah!  More autorelease counts then retain counts left.
1297   // Emit hard error.
1298   V = V ^ RefVal::ErrorOverAutorelease;
1299   state = setRefBinding(state, Sym, V);
1300
1301   ExplodedNode *N = Ctx.generateSink(state, Pred, Tag);
1302   if (N) {
1303     SmallString<128> sbuf;
1304     llvm::raw_svector_ostream os(sbuf);
1305     os << "Object was autoreleased ";
1306     if (V.getAutoreleaseCount() > 1)
1307       os << V.getAutoreleaseCount() << " times but the object ";
1308     else
1309       os << "but ";
1310     os << "has a +" << V.getCount() << " retain count";
1311
1312     if (!overAutorelease)
1313       overAutorelease.reset(new OverAutorelease(this));
1314
1315     const LangOptions &LOpts = Ctx.getASTContext().getLangOpts();
1316     auto R = llvm::make_unique<RefCountReport>(*overAutorelease, LOpts, N, Sym,
1317                                             os.str());
1318     Ctx.emitReport(std::move(R));
1319   }
1320
1321   return nullptr;
1322 }
1323
1324 ProgramStateRef
1325 RetainCountChecker::handleSymbolDeath(ProgramStateRef state,
1326                                       SymbolRef sid, RefVal V,
1327                                     SmallVectorImpl<SymbolRef> &Leaked) const {
1328   bool hasLeak;
1329
1330   // HACK: Ignore retain-count issues on values accessed through ivars,
1331   // because of cases like this:
1332   //   [_contentView retain];
1333   //   [_contentView removeFromSuperview];
1334   //   [self addSubview:_contentView]; // invalidates 'self'
1335   //   [_contentView release];
1336   if (V.getIvarAccessHistory() != RefVal::IvarAccessHistory::None)
1337     hasLeak = false;
1338   else if (V.isOwned())
1339     hasLeak = true;
1340   else if (V.isNotOwned() || V.isReturnedOwned())
1341     hasLeak = (V.getCount() > 0);
1342   else
1343     hasLeak = false;
1344
1345   if (!hasLeak)
1346     return removeRefBinding(state, sid);
1347
1348   Leaked.push_back(sid);
1349   return setRefBinding(state, sid, V ^ RefVal::ErrorLeak);
1350 }
1351
1352 ExplodedNode *
1353 RetainCountChecker::processLeaks(ProgramStateRef state,
1354                                  SmallVectorImpl<SymbolRef> &Leaked,
1355                                  CheckerContext &Ctx,
1356                                  ExplodedNode *Pred) const {
1357   // Generate an intermediate node representing the leak point.
1358   ExplodedNode *N = Ctx.addTransition(state, Pred);
1359
1360   if (N) {
1361     for (SmallVectorImpl<SymbolRef>::iterator
1362          I = Leaked.begin(), E = Leaked.end(); I != E; ++I) {
1363
1364       const LangOptions &LOpts = Ctx.getASTContext().getLangOpts();
1365       RefCountBug *BT = Pred ? getLeakWithinFunctionBug(LOpts)
1366                           : getLeakAtReturnBug(LOpts);
1367       assert(BT && "BugType not initialized.");
1368
1369       Ctx.emitReport(
1370           llvm::make_unique<RefLeakReport>(*BT, LOpts, N, *I, Ctx));
1371     }
1372   }
1373
1374   return N;
1375 }
1376
1377 static bool isISLObjectRef(QualType Ty) {
1378   return StringRef(Ty.getAsString()).startswith("isl_");
1379 }
1380
1381 void RetainCountChecker::checkBeginFunction(CheckerContext &Ctx) const {
1382   if (!Ctx.inTopFrame())
1383     return;
1384
1385   RetainSummaryManager &SmrMgr = getSummaryManager(Ctx);
1386   const LocationContext *LCtx = Ctx.getLocationContext();
1387   const FunctionDecl *FD = dyn_cast<FunctionDecl>(LCtx->getDecl());
1388
1389   if (!FD || SmrMgr.isTrustedReferenceCountImplementation(FD))
1390     return;
1391
1392   ProgramStateRef state = Ctx.getState();
1393   const RetainSummary *FunctionSummary = SmrMgr.getFunctionSummary(FD);
1394   ArgEffects CalleeSideArgEffects = FunctionSummary->getArgEffects();
1395
1396   for (unsigned idx = 0, e = FD->getNumParams(); idx != e; ++idx) {
1397     const ParmVarDecl *Param = FD->getParamDecl(idx);
1398     SymbolRef Sym = state->getSVal(state->getRegion(Param, LCtx)).getAsSymbol();
1399
1400     QualType Ty = Param->getType();
1401     const ArgEffect *AE = CalleeSideArgEffects.lookup(idx);
1402     if (AE && AE->getKind() == DecRef && isISLObjectRef(Ty)) {
1403       state = setRefBinding(
1404           state, Sym, RefVal::makeOwned(ObjKind::Generalized, Ty));
1405     } else if (isISLObjectRef(Ty)) {
1406       state = setRefBinding(
1407           state, Sym,
1408           RefVal::makeNotOwned(ObjKind::Generalized, Ty));
1409     }
1410   }
1411
1412   Ctx.addTransition(state);
1413 }
1414
1415 void RetainCountChecker::checkEndFunction(const ReturnStmt *RS,
1416                                           CheckerContext &Ctx) const {
1417   ExplodedNode *Pred = processReturn(RS, Ctx);
1418
1419   // Created state cached out.
1420   if (!Pred) {
1421     return;
1422   }
1423
1424   ProgramStateRef state = Pred->getState();
1425   RefBindingsTy B = state->get<RefBindings>();
1426
1427   // Don't process anything within synthesized bodies.
1428   const LocationContext *LCtx = Pred->getLocationContext();
1429   if (LCtx->getAnalysisDeclContext()->isBodyAutosynthesized()) {
1430     assert(!LCtx->inTopFrame());
1431     return;
1432   }
1433
1434   for (RefBindingsTy::iterator I = B.begin(), E = B.end(); I != E; ++I) {
1435     state = handleAutoreleaseCounts(state, Pred, /*Tag=*/nullptr, Ctx,
1436                                     I->first, I->second);
1437     if (!state)
1438       return;
1439   }
1440
1441   // If the current LocationContext has a parent, don't check for leaks.
1442   // We will do that later.
1443   // FIXME: we should instead check for imbalances of the retain/releases,
1444   // and suggest annotations.
1445   if (LCtx->getParent())
1446     return;
1447
1448   B = state->get<RefBindings>();
1449   SmallVector<SymbolRef, 10> Leaked;
1450
1451   for (RefBindingsTy::iterator I = B.begin(), E = B.end(); I != E; ++I)
1452     state = handleSymbolDeath(state, I->first, I->second, Leaked);
1453
1454   processLeaks(state, Leaked, Ctx, Pred);
1455 }
1456
1457 void RetainCountChecker::checkDeadSymbols(SymbolReaper &SymReaper,
1458                                           CheckerContext &C) const {
1459   ExplodedNode *Pred = C.getPredecessor();
1460
1461   ProgramStateRef state = C.getState();
1462   RefBindingsTy B = state->get<RefBindings>();
1463   SmallVector<SymbolRef, 10> Leaked;
1464
1465   // Update counts from autorelease pools
1466   for (const auto &I: state->get<RefBindings>()) {
1467     SymbolRef Sym = I.first;
1468     if (SymReaper.isDead(Sym)) {
1469       static CheckerProgramPointTag Tag(this, "DeadSymbolAutorelease");
1470       const RefVal &V = I.second;
1471       state = handleAutoreleaseCounts(state, Pred, &Tag, C, Sym, V);
1472       if (!state)
1473         return;
1474
1475       // Fetch the new reference count from the state, and use it to handle
1476       // this symbol.
1477       state = handleSymbolDeath(state, Sym, *getRefBinding(state, Sym), Leaked);
1478     }
1479   }
1480
1481   if (Leaked.empty()) {
1482     C.addTransition(state);
1483     return;
1484   }
1485
1486   Pred = processLeaks(state, Leaked, C, Pred);
1487
1488   // Did we cache out?
1489   if (!Pred)
1490     return;
1491
1492   // Now generate a new node that nukes the old bindings.
1493   // The only bindings left at this point are the leaked symbols.
1494   RefBindingsTy::Factory &F = state->get_context<RefBindings>();
1495   B = state->get<RefBindings>();
1496
1497   for (SmallVectorImpl<SymbolRef>::iterator I = Leaked.begin(),
1498                                             E = Leaked.end();
1499        I != E; ++I)
1500     B = F.remove(B, *I);
1501
1502   state = state->set<RefBindings>(B);
1503   C.addTransition(state, Pred);
1504 }
1505
1506 void RetainCountChecker::printState(raw_ostream &Out, ProgramStateRef State,
1507                                     const char *NL, const char *Sep) const {
1508
1509   RefBindingsTy B = State->get<RefBindings>();
1510
1511   if (B.isEmpty())
1512     return;
1513
1514   Out << Sep << NL;
1515
1516   for (RefBindingsTy::iterator I = B.begin(), E = B.end(); I != E; ++I) {
1517     Out << I->first << " : ";
1518     I->second.print(Out);
1519     Out << NL;
1520   }
1521 }
1522
1523 //===----------------------------------------------------------------------===//
1524 // Checker registration.
1525 //===----------------------------------------------------------------------===//
1526
1527 void ento::registerRetainCountChecker(CheckerManager &Mgr) {
1528   auto *Chk = Mgr.registerChecker<RetainCountChecker>();
1529   Chk->TrackObjCAndCFObjects = true;
1530 }
1531
1532 // FIXME: remove this, hack for backwards compatibility:
1533 // it should be possible to enable the NS/CF retain count checker as
1534 // osx.cocoa.RetainCount, and it should be possible to disable
1535 // osx.OSObjectRetainCount using osx.cocoa.RetainCount:CheckOSObject=false.
1536 static bool hasPrevCheckOSObjectOptionDisabled(AnalyzerOptions &Options) {
1537   auto I = Options.Config.find("osx.cocoa.RetainCount:CheckOSObject");
1538   if (I != Options.Config.end())
1539     return I->getValue() == "false";
1540   return false;
1541 }
1542
1543 void ento::registerOSObjectRetainCountChecker(CheckerManager &Mgr) {
1544   auto *Chk = Mgr.registerChecker<RetainCountChecker>();
1545   if (!hasPrevCheckOSObjectOptionDisabled(Mgr.getAnalyzerOptions()))
1546     Chk->TrackOSObjects = true;
1547 }