[analyzer][NFC] Add different interestingness kinds

[Szelethus]

Summary

We defined (on the mailing list and here on phabricator) 2 different cases where retrieving information about a control dependency condition is very important:

1. When the condition's last write happened in a different stack frame
2. When the collapse point of the condition (when we can constrain it to be true/false) didn't happen in the actual condition.

It seems like we solved this problem with the help of expression value tracking, and have started working on better diagnostics notes about this process.

Expression value tracking is nothing more than registering a variety of visitors to construct reports about it. Each of the registered visitors (ReturnVisitor, FindLastStoreVisitor, NoStoreFuncVisitor, etc) have something to go by: a MemRegion, an SVal, an ExplodedNode, etc. For this reason, better explaining a last write is super simple, we can always just pass on some more information to the visitor in question (as seen in D65575).

ConditionBRVisitor is a different beast, as it was built for a different purpose. It is responsible for constructing events at, well, conditions, and is registered only once, and isn't a part of the "expression value tracking family". Unfortunately, it is also the visitor to tinker with for constructing better diagnostics about the collapse point problem.

This creates a need for alternative way to communicate with ConditionBRVisitor that a specific condition is being tracked for for the reason of being a control dependency. Since at almost all PathDiagnosticEventPiece construction the visitor checks interestingness, it makes sense to pair interestingness with a reason as to why we marked an entity as such.

[NoQ]

clang/include/clang/StaticAnalyzer/Core/BugReporter/BugReporterVisitors.h

92–101 ↗

(On Diff #213258)

We usually rely on our "unhandled switch case" warnings for noticing all the places which we need to expand when we're adding a new case. Your approach requires adding static asserts all over the place instead - not sure what's better. I guess they're not generally mutually exclusive, however NumTrackingKinds makes it impossible to handle all cases in a switch (because NumTrackingKinds itself wouldn't ever be handled). I took some sort of middleground approach in CFGTerminator::Kind in D61814 but i'm very much open to suggestions.

[xazax.hun]

As this thing will now be part of the checker interface it would be great to have some guidelines which interestingness kind to use (or, when to use interestingness at all). I am totally fine with addressing this in a followup patch though.

[Szelethus]

clang/include/clang/StaticAnalyzer/Core/BugReporter/BugReporterVisitors.h

92–101 ↗

(On Diff #213258)

I agree with your reasoning. I decided to remove NumTrackingKinds and use a switch AND llvm_unreachable as well if the warning wasn't scary enough.

cfe/trunk/include/clang/StaticAnalyzer/Core/BugReporter/BugReporter.h

protected:
   const SourceRange ErrorNodeRange;
   NoteList Notes;
 
   /// A (stack of) a set of symbols that are registered with this
   /// report as being "interesting", and thus used to help decide which
   /// diagnostics to include when constructing the final path diagnostic.
   /// The stack is largely used by BugReporter when generating PathDiagnostics
   /// for multiple PathDiagnosticConsumers.
-  llvm::DenseSet<SymbolRef> InterestingSymbols;
+  llvm::DenseMap<SymbolRef, bugreporter::TrackingKind> InterestingSymbols;
 
   /// A (stack of) set of regions that are registered with this report as being
   /// "interesting", and thus used to help decide which diagnostics
   /// to include when constructing the final path diagnostic.
   /// The stack is largely used by BugReporter when generating PathDiagnostics
   /// for multiple PathDiagnosticConsumers.
-  llvm::DenseSet<const MemRegion *> InterestingRegions;
+  llvm::DenseMap<const MemRegion *, bugreporter::TrackingKind>
+      InterestingRegions;
 
   /// A set of location contexts that correspoind to call sites which should be
   /// considered "interesting".
   llvm::SmallSet<const LocationContext *, 2> InterestingLocationContexts;
 
   /// A set of custom visitors which generate "event" diagnostics at
   /// interesting points in the path.
   VisitorList Callbacks;
public:
 
   /// Indicates whether or not any path pruning should take place
   /// when generating a PathDiagnostic from this BugReport.
   bool shouldPrunePath() const { return !DoNotPrunePath; }
 
   /// Disable all path pruning when generating a PathDiagnostic.
   void disablePathPruning() { DoNotPrunePath = true; }
 
-  void markInteresting(SymbolRef sym);
-  void markInteresting(const MemRegion *R);
-  void markInteresting(SVal V);
+  /// Marks a symbol as interesting. Different kinds of interestingness will
+  /// be processed differently by visitors (e.g. if the tracking kind is
+  /// condition, will append "will be used as a condition" to the message).
+  void markInteresting(SymbolRef sym, bugreporter::TrackingKind TKind =
+                                          bugreporter::TrackingKind::Thorough);
+
+  /// Marks a region as interesting. Different kinds of interestingness will
+  /// be processed differently by visitors (e.g. if the tracking kind is
+  /// condition, will append "will be used as a condition" to the message).
+  void markInteresting(
+      const MemRegion *R,
+      bugreporter::TrackingKind TKind = bugreporter::TrackingKind::Thorough);
+
+  /// Marks a symbolic value as interesting. Different kinds of interestingness
+  /// will be processed differently by visitors (e.g. if the tracking kind is
+  /// condition, will append "will be used as a condition" to the message).
+  void markInteresting(SVal V, bugreporter::TrackingKind TKind =
+                                   bugreporter::TrackingKind::Thorough);
   void markInteresting(const LocationContext *LC);
 
   bool isInteresting(SymbolRef sym) const;
   bool isInteresting(const MemRegion *R) const;
   bool isInteresting(SVal V) const;
   bool isInteresting(const LocationContext *LC) const;
 
+  Optional<bugreporter::TrackingKind>
+  getInterestingnessKind(SymbolRef sym) const;
+
+  Optional<bugreporter::TrackingKind>
+  getInterestingnessKind(const MemRegion *R) const;
+
+  Optional<bugreporter::TrackingKind> getInterestingnessKind(SVal V) const;
+
   /// Returns whether or not this report should be considered valid.
   ///
   /// Invalid reports are those that have been classified as likely false
   /// positives after the fact.
   bool isValid() const {
     return Invalidations.empty();
   }
 

cfe/trunk/lib/StaticAnalyzer/Core/BugReporter.cpp

void BugReport::Profile(llvm::FoldingSetNodeID& hash) const {
   for (SourceRange range : Ranges) {
     if (!range.isValid())
       continue;
     hash.AddInteger(range.getBegin().getRawEncoding());
     hash.AddInteger(range.getEnd().getRawEncoding());
   }
 }
 
-void BugReport::markInteresting(SymbolRef sym) {
+template <class T>
+static void insertToInterestingnessMap(
+    llvm::DenseMap<T, bugreporter::TrackingKind> &InterestingnessMap, T Val,
+    bugreporter::TrackingKind TKind) {
+  auto Result = InterestingnessMap.insert({Val, TKind});
+
+  if (Result.second)
+    return;
+
+  // Even if this symbol/region was already marked as interesting as a
+  // condition, if we later mark it as interesting again but with
+  // thorough tracking, overwrite it. Entities marked with thorough
+  // interestiness are the most important (or most interesting, if you will),
+  // and we wouldn't like to downplay their importance.
+
+  switch (TKind) {
+    case bugreporter::TrackingKind::Thorough:
+      Result.first->getSecond() = bugreporter::TrackingKind::Thorough;
+      return;
+    case bugreporter::TrackingKind::Condition:
+      return;
+  }
+
+  llvm_unreachable(
+      "BugReport::markInteresting currently can only handle 2 different "
+      "tracking kinds! Please define what tracking kind should this entitiy"
+      "have, if it was already marked as interesting with a different kind!");
+}
+
+void BugReport::markInteresting(SymbolRef sym,
+                                bugreporter::TrackingKind TKind) {
   if (!sym)
     return;
 
-  InterestingSymbols.insert(sym);
+  insertToInterestingnessMap(InterestingSymbols, sym, TKind);
 
   if (const auto *meta = dyn_cast<SymbolMetadata>(sym))
-    InterestingRegions.insert(meta->getRegion());
+    markInteresting(meta->getRegion(), TKind);
 }
 
-void BugReport::markInteresting(const MemRegion *R) {
+void BugReport::markInteresting(const MemRegion *R,
+                                bugreporter::TrackingKind TKind) {
   if (!R)
     return;
 
   R = R->getBaseRegion();
-  InterestingRegions.insert(R);
+  insertToInterestingnessMap(InterestingRegions, R, TKind);
 
   if (const auto *SR = dyn_cast<SymbolicRegion>(R))
-    InterestingSymbols.insert(SR->getSymbol());
+    markInteresting(SR->getSymbol(), TKind);
 }
 
-void BugReport::markInteresting(SVal V) {
-  markInteresting(V.getAsRegion());
-  markInteresting(V.getAsSymbol());
+void BugReport::markInteresting(SVal V, bugreporter::TrackingKind TKind) {
+  markInteresting(V.getAsRegion(), TKind);
+  markInteresting(V.getAsSymbol(), TKind);
 }
 
 void BugReport::markInteresting(const LocationContext *LC) {
   if (!LC)
     return;
   InterestingLocationContexts.insert(LC);
 }
 
-bool BugReport::isInteresting(SVal V)  const {
-  return isInteresting(V.getAsRegion()) || isInteresting(V.getAsSymbol());
+Optional<bugreporter::TrackingKind>
+BugReport::getInterestingnessKind(SVal V) const {
+  auto RKind = getInterestingnessKind(V.getAsRegion());
+  auto SKind = getInterestingnessKind(V.getAsSymbol());
+  if (!RKind)
+    return SKind;
+  if (!SKind)
+    return RKind;
+
+  // If either is marked with throrough tracking, return that, we wouldn't like
+  // to downplay a note's importance by 'only' mentioning it as a condition.
+  switch(*RKind) {
+    case bugreporter::TrackingKind::Thorough:
+      return RKind;
+    case bugreporter::TrackingKind::Condition:
+      return SKind;
   }
 
-bool BugReport::isInteresting(SymbolRef sym)  const {
+  llvm_unreachable(
+      "BugReport::getInterestingnessKind currently can only handle 2 different "
+      "tracking kinds! Please define what tracking kind should we return here "
+      "when the kind of getAsRegion() and getAsSymbol() is different!");
+  return None;
+}
+
+Optional<bugreporter::TrackingKind>
+BugReport::getInterestingnessKind(SymbolRef sym) const {
   if (!sym)
-    return false;
+    return None;
   // We don't currently consider metadata symbols to be interesting
   // even if we know their region is interesting. Is that correct behavior?
-  return InterestingSymbols.count(sym);
+  auto It = InterestingSymbols.find(sym);
+  if (It == InterestingSymbols.end())
+    return None;
+  return It->getSecond();
 }
 
-bool BugReport::isInteresting(const MemRegion *R)  const {
+Optional<bugreporter::TrackingKind>
+BugReport::getInterestingnessKind(const MemRegion *R) const {
   if (!R)
-    return false;
+    return None;
+
   R = R->getBaseRegion();
-  bool b = InterestingRegions.count(R);
-  if (b)
-    return true;
+  auto It = InterestingRegions.find(R);
+  if (It != InterestingRegions.end())
+    return It->getSecond();
+
   if (const auto *SR = dyn_cast<SymbolicRegion>(R))
-    return InterestingSymbols.count(SR->getSymbol());
-  return false;
+    return getInterestingnessKind(SR->getSymbol());
+  return None;
+}
+
+bool BugReport::isInteresting(SVal V) const {
+  return getInterestingnessKind(V).hasValue();
+}
+
+bool BugReport::isInteresting(SymbolRef sym) const {
+  return getInterestingnessKind(sym).hasValue();
+}
+
+bool BugReport::isInteresting(const MemRegion *R) const {
+  return getInterestingnessKind(R).hasValue();
 }
 
 bool BugReport::isInteresting(const LocationContext *LC)  const {
   if (!LC)
     return false;
   return InterestingLocationContexts.count(LC);
 }
 

cfe/trunk/lib/StaticAnalyzer/Core/BugReporterVisitors.cpp

if (R) {
       // Mark both the variable region and its contents as interesting.
       SVal V = LVState->getRawSVal(loc::MemRegionVal(R));
       report.addVisitor(
           std::make_unique<NoStoreFuncVisitor>(cast<SubRegion>(R), TKind));
 
       MacroNullReturnSuppressionVisitor::addMacroVisitorIfNecessary(
           LVNode, R, EnableNullFPSuppression, report, V);
 
-      report.markInteresting(V);
+      report.markInteresting(V, TKind);
       report.addVisitor(std::make_unique<UndefOrNullArgVisitor>(R));
 
       // If the contents are symbolic, find out when they became null.
       if (V.getAsLocSymbol(/*IncludeBaseRegions*/ true))
         report.addVisitor(std::make_unique<TrackConstraintBRVisitor>(
               V.castAs<DefinedSVal>(), false));
 
       // Add visitor, which will suppress inline defensive checks.
if (auto L = V.getAs<loc::MemRegionVal>()) {
 
     if (CanDereference)
       if (auto KV = RVal.getAs<KnownSVal>())
         report.addVisitor(std::make_unique<FindLastStoreBRVisitor>(
             *KV, L->getRegion(), EnableNullFPSuppression, TKind, SFC));
 
     const MemRegion *RegionRVal = RVal.getAsRegion();
     if (RegionRVal && isa<SymbolicRegion>(RegionRVal)) {
-      report.markInteresting(RegionRVal);
+      report.markInteresting(RegionRVal, TKind);
       report.addVisitor(std::make_unique<TrackConstraintBRVisitor>(
             loc::MemRegionVal(RegionRVal), /*assumption=*/false));
     }
   }
   return true;
 }
 
 //===----------------------------------------------------------------------===//