[analyzer] Add better tracking for RetainCountChecker leak warnings

[vsavchenko]

Summary

RetainCountChecker models a group of calls that are interpreted as
"identity" functions. bugreporter::Tracker couldn't see through
such calls and pick the right argument for tracking.

This commit introduces a new tag that helps to keep this information
from the actual analysis and reuse it later for tracking purposes.

So, in short, when we see a call foo(x) that we model as
"identity", we now add a tag that is saying that the result of
foo(x) is essentially x. When the tracker, later on, tries to
track value from foo(x), we point out that it should track x.

[NoQ]

clang/lib/StaticAnalyzer/Checkers/RetainCountChecker/RetainCountDiagnostics.cpp

953–957

I guess this part should ultimately be written in one place, eg. ExplodedNode::findTag() or something like that.

I'd also really like to explore the possibility to further limit the variety of nodes traversed here. What nodes are typically traversed here? Is it checker-tagged nodes or is it purge dead symbol nodes or something else?

[vsavchenko]

Rebase

clang/lib/StaticAnalyzer/Checkers/RetainCountChecker/RetainCountDiagnostics.cpp

953–957

Yes, ExplodedNode::findTag() sounds like a great idea!

I mean it is hard to tell without calculating statistics right here and running it on a bunch of projects. However, it is always possible to write the code that will have it the other way. My take on it is that it is probably a mix of things.

I'd also prefer to traverse less, do you have any specific ideas here?

[Szelethus]

Aha, alright! So the tracker tracked back to where the tracked expression got computed in node N, which is the return value of some identity function. Unless its explicitly told that there is a link in between the return value and the parameter, the tracker can't figure this out that it could track further (why would it, right?). So it asks its handlers whether they want to do anything with N, which IdentityHandler does -- it digs out the node where the parameter was evaluated, and tells the tracker to go on with that. Awesome!

I guess we could put IdentityHandler in an anonymous namespace?

clang/lib/StaticAnalyzer/Checkers/RetainCountChecker/RetainCountChecker.cpp

945–947

I don't know ObjC at all, but is this identity obvious? Do you not need a NoteTag to say that "Foo is an identity function, its return value equals the parameter"? Or, in the possession of the actual PathSensitiveBugReport that you can retrieve in the handler, you could drop a note there, maybe?

[vsavchenko]

In D104136#2823834, @Szelethus wrote:

Aha, alright! So the tracker tracked back to where the tracked expression got computed in node N, which is the return value of some identity function. Unless its explicitly told that there is a link in between the return value and the parameter, the tracker can't figure this out that it could track further (why would it, right?). So it asks its handlers whether they want to do anything with N, which IdentityHandler does -- it digs out the node where the parameter was evaluated, and tells the tracker to go on with that. Awesome!

That's exactly it!

I guess we could put IdentityHandler in an anonymous namespace?

Sure thing!

clang/lib/StaticAnalyzer/Checkers/RetainCountChecker/RetainCountChecker.cpp

945–947

These are usually some type of casts. And we already provide notes when this value gets into some other region (like 'newPtr' initialized to the value of 'originalPtr'). I think that they are enough. And if we want something better, I think we need to tweak that messaging (StoreHandler now allows that) instead of crowding user with even more notes.

[vsavchenko]

Move IdentityHandler into the anonymous namespace

[Szelethus]

clang/lib/StaticAnalyzer/Checkers/RetainCountChecker/RetainCountChecker.cpp

945–947

Fair enough!

clang/lib/StaticAnalyzer/Checkers/RetainCountChecker/RetainCountDiagnostics.cpp

953–957

I'd also really like to explore the possibility to further limit the variety of nodes traversed here. What nodes are typically traversed here? Is it checker-tagged nodes or is it purge dead symbol nodes or something else?

Is there something I'm not seeing here? Trackers basically ascend a path from the error node to at most the root of the ExplodedGraph (not the trimmed version, as Tracker::track() is called before any of that process happens), so its not much slower than trackExpressionValue, right?

Or does this, and likely many other future handlers run such a loop more often then what I imagine?

[vsavchenko]

clang/lib/StaticAnalyzer/Checkers/RetainCountChecker/RetainCountDiagnostics.cpp

953–957

Essentially, yes. trackExpressionValue (and Tracker::track) ascend the graph searching for a node where the give expression is evaluated. The problem here is that whenever we ask to track some expression, not only trackExpressionValue will do its traversal (much longer), but also this handler will do its (shorter). It would be better not to do this altogether, but I personally don't see any solutions how we can cut on this part.
At the same time, I don't think that it is performance critical, considering that the part of the graph where N->getStmtForDiagnostics() == E is small.

[Szelethus]

clang/lib/StaticAnalyzer/Checkers/RetainCountChecker/RetainCountDiagnostics.cpp

953–957

Ah, so, this is your patch:

E: Error Node
C: Identity function call
V: Argument evaluation
A: Origin of the argument value
---->: Nodes traversed by the tracker
====>: Nodes traversed by the handler

*              *           *           *
E->O->O->O->O->C->O->O->O->V->O->O->O->A->X->X->X

--------------->          
               ============>----------->

This is fine, because its just a single ascend, made a little worse by the fact that we do it for each tracked variable. But later, with more handlers, it might get worse (per variable):

*              *           *           *
E->O->O->O->O->C->O->O->O->V->O->O->O->A->X->X->X

--------------->           
               ============>----------->
               ===============>----->
               ==============>------------------>
               =================================>
               ======================>

Now, I can't immediately imagine a case where someone would add THAT many handlers, or track that many variables, even in extreme circumstances, but I don't posses a crystal ball either :^)

clang/lib/StaticAnalyzer/Checkers/RetainCountChecker/RetainCountChecker.h

void Profile(llvm::FoldingSetNodeID& ID) const {
     ID.AddInteger(ACnt);
     ID.AddInteger(RawObjectKind);
     ID.AddInteger(RawIvarAccessHistory);
   }
 
   void print(raw_ostream &Out) const;
 };
 
+/// A special tag to mark calls to identity functions.
+///
+/// It helps checker to produce better notes.
+class IdentityTag : public DataTag {
+private:
+  static int Kind;
+  const CallExpr *IdentityCall;
+  const Expr *Source;
+
+  IdentityTag(const CallExpr *IdentityCall, const Expr *Source)
+      : DataTag(&Kind), IdentityCall(IdentityCall), Source(Source) {}
+
+public:
+  static bool classof(const ProgramPointTag *T) {
+    return T->getTagKind() == &Kind;
+  }
+
+  /// Return a call to identity function.
+  const CallExpr *getIdentityCall() const { return IdentityCall; }
+
+  /// Return the argument expression that is equal to the call's return value.
+  const Expr *getSource() const { return Source; }
+
+  friend class Factory;
+};
+
 class RetainCountChecker
   : public Checker< check::Bind,
                     check::DeadSymbols,
                     check::BeginFunction,
                     check::EndFunction,
                     check::PostStmt<BlockExpr>,
                     check::PostStmt<CastExpr>,
                     check::PostStmt<ObjCArrayLiteral>,

clang/lib/StaticAnalyzer/Checkers/RetainCountChecker/RetainCountChecker.cpp

 const RefVal *getRefBinding(ProgramStateRef State, SymbolRef Sym) {
   return State->get<RefBindings>(Sym);
 }
 
 } // end namespace retaincountchecker
 } // end namespace ento
 } // end namespace clang
 
+int IdentityTag::Kind = 0;
+
 static ProgramStateRef setRefBinding(ProgramStateRef State, SymbolRef Sym,
                                      RefVal Val) {
   assert(Sym != nullptr);
   return State->set<RefBindings>(Sym, Val);
 }
 
 static ProgramStateRef removeRefBinding(ProgramStateRef State, SymbolRef Sym) {
   return State->remove<RefBindings>(Sym);
bool RetainCountChecker::evalCall(const CallEvent &Call,
   using BehaviorSummary = RetainSummaryManager::BehaviorSummary;
   Optional<BehaviorSummary> BSmr =
       SmrMgr.canEval(CE, FD, hasTrustedImplementationAnnotation);
 
   // See if it's one of the specific functions we know how to eval.
   if (!BSmr)
     return false;
 
+  const ProgramPointTag *Tag = nullptr;
+
   // Bind the return value.
   if (BSmr == BehaviorSummary::Identity ||
       BSmr == BehaviorSummary::IdentityOrZero ||
       BSmr == BehaviorSummary::IdentityThis) {
 
     const Expr *BindReturnTo =
         (BSmr == BehaviorSummary::IdentityThis)
             ? cast<CXXMemberCallExpr>(CE)->getImplicitObjectArgument()
             : CE->getArg(0);
     SVal RetVal = state->getSVal(BindReturnTo, LCtx);
 
     // If the receiver is unknown or the function has
     // 'rc_ownership_trusted_implementation' annotate attribute, conjure a
     // return value.
     // FIXME: this branch is very strange.
     if (RetVal.isUnknown() ||
         (hasTrustedImplementationAnnotation && !ResultTy.isNull())) {
       SValBuilder &SVB = C.getSValBuilder();
       RetVal =
           SVB.conjureSymbolVal(nullptr, CE, LCtx, ResultTy, C.blockCount());
     }
 
     // Bind the value.
     state = state->BindExpr(CE, LCtx, RetVal, /*Invalidate=*/false);
+    ExprEngine &Eng = C.getStateManager().getOwningEngine();
+    // Let's mark this place with a special tag.
+    Tag = Eng.getDataTags().make<IdentityTag>(CE, BindReturnTo);
 
     if (BSmr == BehaviorSummary::IdentityOrZero) {
       // Add a branch where the output is zero.
       ProgramStateRef NullOutputState = C.getState();
 
       // Assume that output is zero on the other branch.
       NullOutputState = NullOutputState->BindExpr(
           CE, LCtx, C.getSValBuilder().makeNull(), /*Invalidate=*/false);
       C.addTransition(NullOutputState, &getCastFailTag());
 
       // And on the original branch assume that both input and
       // output are non-zero.
       if (auto L = RetVal.getAs<DefinedOrUnknownSVal>())
         state = state->assume(*L, /*assumption=*/true);
-
     }
   }
 
-  C.addTransition(state);
+  C.addTransition(state, Tag);
   return true;
 }
 
 ExplodedNode * RetainCountChecker::processReturn(const ReturnStmt *S,
                                                  CheckerContext &C) const {
   ExplodedNode *Pred = C.getPredecessor();
 
   // Only adjust the reference count if this is the top-level call frame,

clang/lib/StaticAnalyzer/Checkers/RetainCountChecker/RetainCountDiagnostics.cpp

if (RegionDescription) {
     os << " stored into '" << *RegionDescription << '\'';
   } else {
 
     // If we can't figure out the name, just supply the type information.
     os << " of type '" << getPrettyTypeName(Sym->getType()) << "'";
   }
 }
 
+// A handler designed to help the tracker with identity function calls.
+//
+// The checker models a good number of functions as "identity", i.e.
+// returning the same value it was given.  The tracker doesn't understand
+// these semantics and calls to such functions are opaque.  Here we aid
+// the tracker by promoting the tracking process through such calls.
+class IdentityHandler final : public bugreporter::ExpressionHandler {
+public:
+  using bugreporter::ExpressionHandler::ExpressionHandler;
+
+  bugreporter::Tracker::Result
+  handle(const Expr *E, const ExplodedNode *Original,
+         const ExplodedNode *ExprNode,
+         bugreporter::TrackingOptions Opts) override {
+    // We care only for calls.
+    if (const auto *CE = dyn_cast<CallExpr>(E)) {
+      // Let's traverse...
+      for (const ExplodedNode *N = ExprNode;
+           // ...all the nodes corresponding to the given expression...
+           N != nullptr && N->getStmtForDiagnostics() == E;
+           N = N->getFirstPred()) {
+
+        ProgramPoint PP = N->getLocation();
+        // ...looking for a node that was marked as a call to identity function.
+        if (const IdentityTag *T = dyn_cast_or_null<IdentityTag>(PP.getTag())) {
+          // Validate (just in case) that it was indeed about this call.
+          if (T->getIdentityCall() != CE)
+            continue;
+
+          // And keep tracker going!
+          return getParentTracker().track(T->getSource(), N, Opts);
+        }
+      }
+    }
+    return {};
+  }
+};
+
 void RefLeakReport::findBindingToReport(CheckerContext &Ctx,
                                         ExplodedNode *Node) {
   if (!AllocFirstBinding)
     // If we don't have any bindings, we won't be able to find any
     // better binding to report.
     return;
 
   // If the original region still contains the leaking symbol...
if (!AllVarBindings.empty() &&
     // 'AllocFirstBinding', we need to explain how the leaking object
     // got from one to another.
     //
     // NOTE: We use the actual SVal stored in AllocBindingToReport here because
     //       trackStoredValue compares SVal's and it can get trickier for
     //       something like derived regions if we want to construct SVal from
     //       Sym. Instead, we take the value that is definitely stored in that
     //       region, thus guaranteeing that trackStoredValue will work.
-    bugreporter::trackStoredValue(AllVarBindings[0].second.castAs<KnownSVal>(),
-                                  AllocBindingToReport, *this);
+    auto AllocatedValueTracker = bugreporter::Tracker::create(*this);
+    AllocatedValueTracker->addHighPriorityHandler<IdentityHandler>();
+    AllocatedValueTracker->track(AllVarBindings[0].second,
+                                 AllocBindingToReport);
   } else {
     AllocBindingToReport = AllocFirstBinding;
   }
 }
 
 RefLeakReport::RefLeakReport(const RefCountBug &D, const LangOptions &LOpts,
                              ExplodedNode *N, SymbolRef Sym,
                              CheckerContext &Ctx)

clang/test/Analysis/Inputs/expected-plists/retain-release.m.objc.plist

<array>
      </array>
      <key>depth</key><integer>0</integer>
      <key>extended_message</key>
      <string>Call to function &apos;CFCreateSomething&apos; returns a Core Foundation object of type &apos;CFTypeRef&apos; with a +1 retain count</string>
      <key>message</key>
      <string>Call to function &apos;CFCreateSomething&apos; returns a Core Foundation object of type &apos;CFTypeRef&apos; with a +1 retain count</string>
     </dict>
     <dict>
+     <key>kind</key><string>event</string>
+     <key>location</key>
+     <dict>
+      <key>line</key><integer>2285</integer>
+      <key>col</key><integer>3</integer>
+      <key>file</key><integer>0</integer>
+     </dict>
+     <key>ranges</key>
+     <array>
+       <array>
+        <dict>
+         <key>line</key><integer>2285</integer>
+         <key>col</key><integer>3</integer>
+         <key>file</key><integer>0</integer>
+        </dict>
+        <dict>
+         <key>line</key><integer>2285</integer>
+         <key>col</key><integer>15</integer>
+         <key>file</key><integer>0</integer>
+        </dict>
+       </array>
+     </array>
+     <key>depth</key><integer>0</integer>
+     <key>extended_message</key>
+     <string>&apos;obj&apos; initialized here</string>
+     <key>message</key>
+     <string>&apos;obj&apos; initialized here</string>
+    </dict>
+    <dict>
      <key>kind</key><string>control</string>
      <key>edges</key>
       <array>
        <dict>
         <key>start</key>
          <array>
           <dict>
            <key>line</key><integer>2285</integer>
<array>
      </array>
      <key>depth</key><integer>0</integer>
      <key>extended_message</key>
      <string>Call to function &apos;CFArrayCreateMutable&apos; returns a Core Foundation object of type &apos;CFMutableArrayRef&apos; with a +1 retain count</string>
      <key>message</key>
      <string>Call to function &apos;CFArrayCreateMutable&apos; returns a Core Foundation object of type &apos;CFMutableArrayRef&apos; with a +1 retain count</string>
     </dict>
     <dict>
+     <key>kind</key><string>event</string>
+     <key>location</key>
+     <dict>
+      <key>line</key><integer>2305</integer>
+      <key>col</key><integer>3</integer>
+      <key>file</key><integer>0</integer>
+     </dict>
+     <key>ranges</key>
+     <array>
+       <array>
+        <dict>
+         <key>line</key><integer>2305</integer>
+         <key>col</key><integer>3</integer>
+         <key>file</key><integer>0</integer>
+        </dict>
+        <dict>
+         <key>line</key><integer>2305</integer>
+         <key>col</key><integer>16</integer>
+         <key>file</key><integer>0</integer>
+        </dict>
+       </array>
+     </array>
+     <key>depth</key><integer>0</integer>
+     <key>extended_message</key>
+     <string>&apos;arr&apos; initialized here</string>
+     <key>message</key>
+     <string>&apos;arr&apos; initialized here</string>
+    </dict>
+    <dict>
      <key>kind</key><string>control</string>
      <key>edges</key>
       <array>
        <dict>
         <key>start</key>
          <array>
           <dict>
            <key>line</key><integer>2305</integer>

clang/test/Analysis/Inputs/expected-plists/retain-release.m.objcpp.plist

<array>
      </array>
      <key>depth</key><integer>0</integer>
      <key>extended_message</key>
      <string>Call to function &apos;CFCreateSomething&apos; returns a Core Foundation object of type &apos;CFTypeRef&apos; with a +1 retain count</string>
      <key>message</key>
      <string>Call to function &apos;CFCreateSomething&apos; returns a Core Foundation object of type &apos;CFTypeRef&apos; with a +1 retain count</string>
     </dict>
     <dict>
+     <key>kind</key><string>event</string>
+     <key>location</key>
+     <dict>
+      <key>line</key><integer>2285</integer>
+      <key>col</key><integer>3</integer>
+      <key>file</key><integer>0</integer>
+     </dict>
+     <key>ranges</key>
+     <array>
+       <array>
+        <dict>
+         <key>line</key><integer>2285</integer>
+         <key>col</key><integer>3</integer>
+         <key>file</key><integer>0</integer>
+        </dict>
+        <dict>
+         <key>line</key><integer>2285</integer>
+         <key>col</key><integer>15</integer>
+         <key>file</key><integer>0</integer>
+        </dict>
+       </array>
+     </array>
+     <key>depth</key><integer>0</integer>
+     <key>extended_message</key>
+     <string>&apos;obj&apos; initialized here</string>
+     <key>message</key>
+     <string>&apos;obj&apos; initialized here</string>
+    </dict>
+    <dict>
      <key>kind</key><string>control</string>
      <key>edges</key>
       <array>
        <dict>
         <key>start</key>
          <array>
           <dict>
            <key>line</key><integer>2285</integer>
<array>
      </array>
      <key>depth</key><integer>0</integer>
      <key>extended_message</key>
      <string>Call to function &apos;CFArrayCreateMutable&apos; returns a Core Foundation object of type &apos;CFMutableArrayRef&apos; with a +1 retain count</string>
      <key>message</key>
      <string>Call to function &apos;CFArrayCreateMutable&apos; returns a Core Foundation object of type &apos;CFMutableArrayRef&apos; with a +1 retain count</string>
     </dict>
     <dict>
+     <key>kind</key><string>event</string>
+     <key>location</key>
+     <dict>
+      <key>line</key><integer>2305</integer>
+      <key>col</key><integer>3</integer>
+      <key>file</key><integer>0</integer>
+     </dict>
+     <key>ranges</key>
+     <array>
+       <array>
+        <dict>
+         <key>line</key><integer>2305</integer>
+         <key>col</key><integer>3</integer>
+         <key>file</key><integer>0</integer>
+        </dict>
+        <dict>
+         <key>line</key><integer>2305</integer>
+         <key>col</key><integer>16</integer>
+         <key>file</key><integer>0</integer>
+        </dict>
+       </array>
+     </array>
+     <key>depth</key><integer>0</integer>
+     <key>extended_message</key>
+     <string>&apos;arr&apos; initialized here</string>
+     <key>message</key>
+     <string>&apos;arr&apos; initialized here</string>
+    </dict>
+    <dict>
      <key>kind</key><string>control</string>
      <key>edges</key>
       <array>
        <dict>
         <key>start</key>
          <array>
           <dict>
            <key>line</key><integer>2305</integer>

clang/test/Analysis/osobject-retain-release.cpp

OSArray *arr = OSDynamicCast(OSArray, OSObject::generateObject(1)); // expected-note{{Call to method 'OSObject::generateObject' returns an OSObject}}
                                                                       // expected-note@-3{{Assuming dynamic cast returns null due to type mismatch}}
   if (!arr)
     return;
   arr->release();
 }
 
 void check_dynamic_cast_alias() {
   OSObject *originalPtr = OSObject::generateObject(1);   // expected-note {{Call to method 'OSObject::generateObject' returns an OSObject}}
+                                                         // expected-note@-1 {{'originalPtr' initialized here}}
   OSArray *newPtr = OSDynamicCast(OSArray, originalPtr); // expected-note {{'newPtr' initialized to the value of 'originalPtr'}}
   if (newPtr) {                                          // expected-note {{'newPtr' is non-null}}
                                                          // expected-note@-1 {{Taking true branch}}
     originalPtr = OSObject::generateObject(42);
     (void)newPtr;
   }
   originalPtr->release(); // expected-warning {{Potential leak of an object stored into 'newPtr'}}
                           // expected-note@-1 {{Object leaked: object allocated and stored into 'newPtr' is not referenced later in this execution path and has a retain count of +1}}
 }
 
 void check_dynamic_cast_alias_cond() {
   OSObject *originalPtr = OSObject::generateObject(1); // expected-note {{Call to method 'OSObject::generateObject' returns an OSObject}}
+                                                       // expected-note@-1 {{'originalPtr' initialized here}}
   OSArray *newPtr = 0;
   if ((newPtr = OSDynamicCast(OSArray, originalPtr))) { // expected-note {{The value of 'originalPtr' is assigned to 'newPtr'}}
                                                         // expected-note@-1 {{'newPtr' is non-null}}
                                                         // expected-note@-2 {{Taking true branch}}
     originalPtr = OSObject::generateObject(42);
     (void)newPtr;
   }
   originalPtr->release(); // expected-warning {{Potential leak of an object stored into 'newPtr'}}
                           // expected-note@-1 {{Object leaked: object allocated and stored into 'newPtr' is not referenced later in this execution path and has a retain count of +1}}
 }
 
 void check_dynamic_cast_alias_intermediate() {
   OSObject *originalPtr = OSObject::generateObject(1); // expected-note {{Call to method 'OSObject::generateObject' returns an OSObject of type 'OSObject' with a +1 retain count}}
-  OSObject *intermediate = originalPtr;                // TODO: add note here as well
+                                                       // expected-note@-1 {{'originalPtr' initialized here}}
+  OSObject *intermediate = originalPtr;                // expected-note {{'intermediate' initialized to the value of 'originalPtr'}}
   OSArray *newPtr = 0;
   if ((newPtr = OSDynamicCast(OSArray, intermediate))) { // expected-note {{The value of 'intermediate' is assigned to 'newPtr'}}
                                                          // expected-note@-1 {{'newPtr' is non-null}}
                                                          // expected-note@-2 {{Taking true branch}}
     intermediate = OSObject::generateObject(42);
     (void)newPtr;
   }
   intermediate->release(); // expected-warning {{Potential leak of an object stored into 'newPtr'}}
                            // expected-note@-1 {{Object leaked: object allocated and stored into 'newPtr' is not referenced later in this execution path and has a retain count of +1}}
 }
 
 void check_dynamic_cast_alias_intermediate_2() {
   OSObject *originalPtr = OSObject::generateObject(1); // expected-note {{Call to method 'OSObject::generateObject' returns an OSObject of type 'OSObject' with a +1 retain count}}
-  OSObject *intermediate = originalPtr;                // TODO: add note here as well
+                                                       // expected-note@-1 {{'originalPtr' initialized here}}
+  OSObject *intermediate = originalPtr;                // expected-note {{'intermediate' initialized to the value of 'originalPtr'}}
   OSArray *newPtr = 0;
   if ((newPtr = OSDynamicCast(OSArray, intermediate))) { // expected-note {{Value assigned to 'newPtr'}}
                                                          // expected-note@-1 {{'newPtr' is non-null}}
                                                          // expected-note@-2 {{Taking true branch}}
     intermediate = OSObject::generateObject(42);
     (void)originalPtr;
   }
   (void)newPtr;