[Analyzer] Add visitor to track iterator invalidation

[baloghadamsoftware]

Summary

To understand the bug report issued by the InvalidatedIterator checker it is essential to see the point where the iterator was invalidated and also to track the assignemnts of the already invalidated iterator up to its errorneous access. Since iterator invalidation is neither "done" by InvalidatedIterator checker nor by IteratorModeling but "happens" upon container modifications (modeled by ContainerModeling) the proper solution here seems to be a BugReporterVisitor instead of NoteTags.

[Szelethus]

You may have explained it in the summary, and I didn't get it, but why isn't putting a NoteTag in invalidateAllIteratorPositions sufficient? We could state something like All iterators associated with 'V' are invalidated. I'm not against a visitor, just playing the dumb to get on track :)

[NoQ]

In D74615#1917289, @Szelethus wrote:

You may have explained it in the summary, and I didn't get it, but why isn't putting a NoteTag in invalidateAllIteratorPositions sufficient? We could state something like All iterators associated with 'V' are invalidated.

+1, that's the intended approach. I suspect we don't even need to simplify the message.

[baloghadamsoftware]

In D74615#1923710, @NoQ wrote:

In D74615#1917289, @Szelethus wrote:

You may have explained it in the summary, and I didn't get it, but why isn't putting a NoteTag in invalidateAllIteratorPositions sufficient? We could state something like All iterators associated with 'V' are invalidated.

+1, that's the intended approach. I suspect we don't even need to simplify the message.

That is planned (a third patch for Container Note Tags), but does not fully solve the problem. There could be multiple operations for the same container which invalidates some iterators. Each operation creates a not tag which explains the kind of iterators invalidated (e.g. all iterators after the iterator passed in the parameter). However that does not explain which operation invalidates the particular iterator which is accessed.

Generally, I do not think the note tags should completely replace custom visitors. Instead we should take the approach which is more convenient in each case. The basic rule I can think of is the following: if the checker does something with a value when adding a new transition then we should assign a note tag to that transition. However, if something happens to the value in a transition which is done by another checker (or the core engine) then we should use a visitor to find that transition.

In this case the container modeling shrinks and extends the container and invalidates groups of iterators. However, from the point of view of an iterator the invalidation happens in another checker (ContainerModeling). Therefore I still think that a visitor is needed to mark the point where that particular iterator was invalidated. This may result in double notes like All iterators of 'V' after 'i1' are invalidated. and then the next is Iterator 'i0' is invalidated. but this is not disturbing. We already have such double notes: Assuming the condition is 'true'. then Taking 'true' branch..

[NoQ]

However, if something happens to the value in a transition which is done by another checker (or the core engine) then

... then that checker (or the engine) adds a tag in order to explain itself, because from its point of view it

does something with a value when adding a new transition

.

---

This may result in double notes like All iterators of 'V' after 'i1' are invalidated. and then the next is Iterator 'i0' is invalidated.

Not if interestingness checks are performed correctly. Before emitting such note, the note tag should ask the bug report whether it's interested in all iterators being invalidated, or in how a particular iterator is invalidated. If PathSensitiveBugReport is not flexible enough to answer such questions, we should improve it.

---

We already have such double notes: Assuming the condition is 'true'. then Taking 'true' branch..

These are not double notes. The former describes the arbitrary state split, thus indicating that there is no concrete knowledge about the branch condition up to this point, while the latter describes the control flow in the program. Also the "Taking..." notes are displayed as arrows rather than as bubbles by GUIs that read plists, so basically everything except scan-build.

clang/lib/StaticAnalyzer/Checkers/InvalidatedIteratorChecker.cpp

 
 namespace {
 
 class InvalidatedIteratorChecker
   : public Checker<check::PreCall> {
 
   std::unique_ptr<BugType> InvalidatedBugType;
 
-  void verifyAccess(CheckerContext &C, const SVal &Val) const;
-  void reportBug(const StringRef &Message, const SVal &Val,
-                 CheckerContext &C, ExplodedNode *ErrNode) const;
+  void verifyAccess(CheckerContext &C, const SVal &Val, const Expr *Ex) const;
 public:
   InvalidatedIteratorChecker();
 
   void checkPreCall(const CallEvent &Call, CheckerContext &C) const;
 
 };
 
+class IteratorInvalidationBRVisitor final : public BugReporterVisitor {
+  SVal Iter;
+  const Expr *IterExpr;
+  bool Satisfied = false;
+
+public:
+  IteratorInvalidationBRVisitor(SVal It, const Expr *ItEx) : Iter(It),
+                                                             IterExpr(ItEx) {}
+
+  void Profile(llvm::FoldingSetNodeID &ID) const override {
+    ID.Add(Iter);
+    ID.Add(IterExpr);
+  }
+
+  std::shared_ptr<PathDiagnosticPiece>
+  VisitNode(const ExplodedNode *Succ, BugReporterContext &BRC,
+            PathSensitiveBugReport &BR) override;
+
+private:
+  bool getPredecessor(const ExplodedNode *Node, const Stmt *S, BugReport &BR,
+                      SVal &PredVal, const Expr *&PredExpr) const;
+};
+
 } //namespace
 
 InvalidatedIteratorChecker::InvalidatedIteratorChecker() {
   InvalidatedBugType.reset(
       new BugType(this, "Iterator invalidated", "Misuse of STL APIs"));
 }
 
 void InvalidatedIteratorChecker::checkPreCall(const CallEvent &Call,
                                               CheckerContext &C) const {
   // Check for access of invalidated position
   const auto *Func = dyn_cast_or_null<FunctionDecl>(Call.getDecl());
   if (!Func)
     return;
 
   if (Func->isOverloadedOperator() &&
       isAccessOperator(Func->getOverloadedOperator())) {
     // Check for any kind of access of invalidated iterator positions
     if (const auto *InstCall = dyn_cast<CXXInstanceCall>(&Call)) {
-      verifyAccess(C, InstCall->getCXXThisVal());
+      verifyAccess(C, InstCall->getCXXThisVal(), InstCall->getCXXThisExpr());
     } else {
-      verifyAccess(C, Call.getArgSVal(0));
+      verifyAccess(C, Call.getArgSVal(0), Call.getArgExpr(0));
     }
   }
 }
 
-void InvalidatedIteratorChecker::verifyAccess(CheckerContext &C, const SVal &Val) const {
+void InvalidatedIteratorChecker::verifyAccess(CheckerContext &C,
+                                              const SVal &Val,
+                                              const Expr *Ex) const {
   auto State = C.getState();
   const auto *Pos = getIteratorPosition(State, Val);
   if (Pos && !Pos->isValid()) {
     auto *N = C.generateErrorNode(State);
     if (!N) {
       return;
     }
-    reportBug("Invalidated iterator accessed.", Val, C, N);
+    auto R =
+      std::make_unique<PathSensitiveBugReport>(*InvalidatedBugType,
+                                               "Invalidated iterator accessed.",
+                                               N);
+    R->markInteresting(Val);
+    R->addVisitor(std::make_unique<IteratorInvalidationBRVisitor>(Val, Ex));
+    C.emitReport(std::move(R));
   }
 }
 
-void InvalidatedIteratorChecker::reportBug(const StringRef &Message,
-                                           const SVal &Val, CheckerContext &C,
-                                           ExplodedNode *ErrNode) const {
-  auto R = std::make_unique<PathSensitiveBugReport>(*InvalidatedBugType,
-                                                    Message, ErrNode);
-  R->markInteresting(Val);
-  C.emitReport(std::move(R));
+std::shared_ptr<PathDiagnosticPiece>
+IteratorInvalidationBRVisitor::VisitNode(const ExplodedNode *Succ,
+                                         BugReporterContext &BRC,
+                                         PathSensitiveBugReport &BR) {
+  if (Satisfied)
+    return nullptr;
+
+  const ExplodedNode *Pred = Succ->getFirstPred();
+  const Stmt *S = nullptr;
+  const auto SP = Succ->getLocation().getAs<StmtPoint>();
+  if (SP.hasValue()) {
+    S = SP->getStmt();
+  } else {
+    const auto E = Succ->getLocation().getAs<BlockEdge>();
+    if (E.hasValue()) {
+      S = E->getSrc()->getTerminator().getStmt();
+    }
+  }
+
+  if (!S)
+    return nullptr;
+
+  const auto &StateBefore = Pred->getState();
+  const auto &StateAfter = Succ->getState();
+  const auto *PosBefore = getIteratorPosition(StateBefore, Iter);
+  const auto *PosAfter = getIteratorPosition(StateAfter, Iter);
+
+  if (!PosAfter)
+    return nullptr;
+
+  SmallString<256> Buf;
+  llvm::raw_svector_ostream Out(Buf);
+
+  StringRef Name;
+  if (const auto *DRE = dyn_cast<DeclRefExpr>(IterExpr->IgnoreParenCasts())) {
+    Name = DRE->getDecl()->getName();
+  }
+
+  if ((PosBefore && PosBefore->isValid()) &&
+      (!PosAfter->isValid())) {
+
+    Out << "Iterator " << (!Name.empty() ? ("'" + Name.str() + "' ") : "" )
+        << "invalidated.";
+    Satisfied = true;
+  }
+
+  SVal PredIter;
+  const Expr *PredIterExpr;
+  if (getPredecessor(Succ, S, BR, PredIter, PredIterExpr)) {
+    StringRef PredName;
+    if (const auto *DRE =
+        dyn_cast<DeclRefExpr>(PredIterExpr->IgnoreParenCasts())) {
+      PredName = DRE->getDecl()->getName();
+    }
+
+    if (Name != PredName) {
+      Out << "Iterator "
+          << (!PredName.empty() ? ("'" + PredName.str() + "' ") : "" )
+          << "assigned"
+          << (!Name.empty() ? (" to '" + Name.str() + "'.") : "." );
+    }
+
+    BR.addVisitor(std::make_unique<IteratorInvalidationBRVisitor>(PredIter,
+                                                                 PredIterExpr));
+    Satisfied = true;
+  }
+
+  if (!Buf.empty()) {
+    auto L = PathDiagnosticLocation::createBegin(S, BRC.getSourceManager(),
+                                                 Succ->getLocationContext());
+
+    if (!L.isValid() || !L.asLocation().isValid())
+      return nullptr;
+
+    auto Piece = std::make_shared<PathDiagnosticEventPiece>(L, Out.str());
+    Piece->addRange(S->getSourceRange());
+
+    return std::move(Piece);
+  }
+
+  return nullptr;
+}
+
+bool
+IteratorInvalidationBRVisitor::getPredecessor(const ExplodedNode *Node,
+                                              const Stmt *S,
+                                              BugReport &BR,
+                                              SVal &PredVal,
+                                              const Expr *&PredExpr) const {
+  auto State = Node->getState();
+  const auto *LCtx = Node->getLocationContext();
+
+  const auto IterSym = Iter.getAsSymbol();
+  const auto *IterReg = Iter.getAsRegion();
+  if (const auto IterLC = Iter.getAs<nonloc::LazyCompoundVal>()) {
+    IterReg = IterLC->getRegion();
+  }
+  const auto *IterPos = getIteratorPosition(State, Iter);
+  assert(IterPos &&
+         "This function is only for iterators with existing positions.");
+
+  const auto *E = dyn_cast<Expr>(S);
+  if (!E)
+    return false;
+
+  const auto &RetVal = State->getSVal(E, LCtx);
+  const auto RetSym = RetVal.getAsSymbol();
+  const auto *RetReg = RetVal.getAsRegion();
+  if (const auto RetLC = RetVal.getAs<nonloc::LazyCompoundVal>()) {
+    RetReg = RetLC->getRegion();
+  }
+
+  // If the current iterator is the return value of an operator and it is a an
+  // assignment operator then its parameter is the predecessor.
+  if (const auto *OpCall = dyn_cast<CXXOperatorCallExpr>(E)) {
+    if (OpCall->getOperator() == OO_Equal) {
+      if (IterSym == RetSym || IterReg == RetReg) {
+        PredExpr = OpCall->getArg(0);
+        PredVal = State->getSVal(PredExpr, LCtx);
+        return true;
+      }
+    }
+  // If the current iterator is the result of a C++ construct expression
+  // and the constructor is a copy or move constructor then its parameter is
+  // the predecessor.
+  } else if (const auto *ConstrExpr = dyn_cast<CXXConstructExpr>(E)) {
+    if (ConstrExpr->getConstructor()->isCopyOrMoveConstructor()) {
+      if (IterSym == RetSym || IterReg == RetReg) {
+        PredExpr = ConstrExpr->getArg(0);
+        PredVal = State->getSVal(PredExpr, LCtx);
+        return true;
+      }
+    }
+  }
+  return false;
 }
 
 void ento::registerInvalidatedIteratorChecker(CheckerManager &mgr) {
   mgr.registerChecker<InvalidatedIteratorChecker>();
 }
 
 bool ento::shouldRegisterInvalidatedIteratorChecker(const LangOptions &LO) {
   return true;
 }

clang/test/Analysis/invalidated-iterator.cpp

-// RUN: %clang_analyze_cc1 -std=c++11 -analyzer-checker=core,cplusplus,alpha.cplusplus.InvalidatedIterator -analyzer-config aggressive-binary-operation-simplification=true -analyzer-config c++-container-inlining=false %s -verify
-// RUN: %clang_analyze_cc1 -std=c++11 -analyzer-checker=core,cplusplus,alpha.cplusplus.InvalidatedIterator -analyzer-config aggressive-binary-operation-simplification=true -analyzer-config c++-container-inlining=true -DINLINE=1 %s -verify
+// RUN: %clang_analyze_cc1 -std=c++11 -analyzer-checker=core,cplusplus,alpha.cplusplus.InvalidatedIterator -analyzer-config aggressive-binary-operation-simplification=true -analyzer-config c++-container-inlining=false -analyzer-output=text %s -verify
+// RUN: %clang_analyze_cc1 -std=c++11 -analyzer-checker=core,cplusplus,alpha.cplusplus.InvalidatedIterator -analyzer-config aggressive-binary-operation-simplification=true -analyzer-config c++-container-inlining=true -DINLINE=1 -analyzer-output=text %s -verify
 
 #include "Inputs/system-header-simulator-cxx.h"
 
 void clang_analyzer_warnIfReached();
 
 void normal_dereference(std::vector<int> &V) {
   auto i = V.cbegin();
   *i; // no-warning
 }
 
 void invalidated_dereference(std::vector<int> &V) {
   auto i = V.cbegin();
-  V.erase(i);
+  V.erase(i); // expected-note{{Iterator 'i' invalidated}}
   *i; // expected-warning{{Invalidated iterator accessed}}
+      // expected-note@-1{{Invalidated iterator accessed}}
 }
 
 void normal_prefix_increment(std::vector<int> &V) {
   auto i = V.cbegin();
   ++i; // no-warning
 }
 
 void invalidated_prefix_increment(std::vector<int> &V) {
   auto i = V.cbegin();
-  V.erase(i);
+  V.erase(i); // expected-note{{Iterator 'i' invalidated}}
   ++i; // expected-warning{{Invalidated iterator accessed}}
+       // expected-note@-1{{Invalidated iterator accessed}}
 }
 
 void normal_prefix_decrement(std::vector<int> &V) {
   auto i = ++V.cbegin();
   --i; // no-warning
 }
 
 void invalidated_prefix_decrement(std::vector<int> &V) {
   auto i = ++V.cbegin();
-  V.erase(i);
+  V.erase(i); // expected-note{{Iterator 'i' invalidated}}
   --i; // expected-warning{{Invalidated iterator accessed}}
+       // expected-note@-1{{Invalidated iterator accessed}}
 }
 
 void normal_postfix_increment(std::vector<int> &V) {
   auto i = V.cbegin();
   i++; // no-warning
 }
 
 void invalidated_postfix_increment(std::vector<int> &V) {
   auto i = V.cbegin();
-  V.erase(i);
+  V.erase(i); // expected-note{{Iterator 'i' invalidated}}
   i++; // expected-warning{{Invalidated iterator accessed}}
+       // expected-note@-1{{Invalidated iterator accessed}}
 }
 
 void normal_postfix_decrement(std::vector<int> &V) {
   auto i = ++V.cbegin();
   i--; // no-warning
 }
 
 void invalidated_postfix_decrement(std::vector<int> &V) {
   auto i = ++V.cbegin();
-  V.erase(i);
+  V.erase(i); // expected-note{{Iterator 'i' invalidated}}
   i--; // expected-warning{{Invalidated iterator accessed}}
+       // expected-note@-1{{Invalidated iterator accessed}}
 }
 
 void normal_increment_by_2(std::vector<int> &V) {
   auto i = V.cbegin();
   i += 2; // no-warning
 }
 
 void invalidated_increment_by_2(std::vector<int> &V) {
   auto i = V.cbegin();
-  V.erase(i);
+  V.erase(i); // expected-note{{Iterator 'i' invalidated}}
   i += 2; // expected-warning{{Invalidated iterator accessed}}
+          // expected-note@-1{{Invalidated iterator accessed}}
 }
 
 void normal_increment_by_2_copy(std::vector<int> &V) {
   auto i = V.cbegin();
   auto j = i + 2; // no-warning
 }
 
 void invalidated_increment_by_2_copy(std::vector<int> &V) {
   auto i = V.cbegin();
-  V.erase(i);
+  V.erase(i); // expected-note{{Iterator 'i' invalidated}}
   auto j = i + 2; // expected-warning{{Invalidated iterator accessed}}
+                  // expected-note@-1{{Invalidated iterator accessed}}
 }
 
 void normal_decrement_by_2(std::vector<int> &V) {
   auto i = V.cbegin();
   i -= 2; // no-warning
 }
 
 void invalidated_decrement_by_2(std::vector<int> &V) {
   auto i = V.cbegin();
-  V.erase(i);
+  V.erase(i); // expected-note{{Iterator 'i' invalidated}}
   i -= 2; // expected-warning{{Invalidated iterator accessed}}
+          // expected-note@-1{{Invalidated iterator accessed}}
 }
 
 void normal_decrement_by_2_copy(std::vector<int> &V) {
   auto i = V.cbegin();
   auto j = i - 2; // no-warning
 }
 
 void invalidated_decrement_by_2_copy(std::vector<int> &V) {
   auto i = V.cbegin();
-  V.erase(i);
+  V.erase(i); // expected-note{{Iterator 'i' invalidated}}
   auto j = i - 2; // expected-warning{{Invalidated iterator accessed}}
+                  // expected-note@-1{{Invalidated iterator accessed}}
 }
 
 void normal_subscript(std::vector<int> &V) {
   auto i = V.cbegin();
   i[1]; // no-warning
 }
 
 void invalidated_subscript(std::vector<int> &V) {
   auto i = V.cbegin();
-  V.erase(i);
+  V.erase(i); // expected-note{{Iterator 'i' invalidated}}
   i[1]; // expected-warning{{Invalidated iterator accessed}}
+        // expected-note@-1{{Invalidated iterator accessed}}
 }
 
 void assignment(std::vector<int> &V) {
   auto i = V.cbegin();
   V.erase(i);
   auto j = V.cbegin(); // no-warning
 }
+
+void indirect(std::vector<int> &V) {
+  auto i = V.cbegin();
+  V.erase(i); // expected-note{{Iterator 'i' invalidated}}
+  auto j = i; // expected-note{{Iterator 'i' assigned to 'j'}}
+  *j; // expected-warning{{Invalidated iterator accessed}}
+      // expected-note@-1{{Invalidated iterator accessed}}
+}