[Analyzer] Iterator Checker - Part 6: Mismatched iterator checker for constructors and comparisons

[baloghadamsoftware]

Summary

Extension of the mismatched iterator checker for constructors taking range of first..last (first and last must be iterators of the same container) and also for comparisons of iterators of different containers (one does not compare iterators of different containers, since the set of iterators is partially ordered, there are no relations between iterators of different containers, except that they are always non-equal).

[NoQ]

This looks clear to me.

lib/StaticAnalyzer/Checkers/IteratorChecker.cpp

554–555

C.getSVal(CCE->getArg(0)) etc. Or, even better, use PreCall and CallEvent(?)

[baloghadamsoftware]

Rebased.

[baloghadamsoftware]

Rebased to Part 5.

[baloghadamsoftware]

Checking of constructor parameters moved to PreCall check.

lib/StaticAnalyzer/Checkers/IteratorChecker.cpp

public:
   bool operator!=(const IteratorComparison &X) const {
     return Left != X.Left || Right != X.Right || Equality != X.Equality;
   }
   void Profile(llvm::FoldingSetNodeID &ID) const { ID.AddInteger(Equality); }
 };
 
 class IteratorChecker
     : public Checker<check::PreCall, check::PostCall,
+                     check::PreStmt<CXXConstructExpr>,
                      check::PreStmt<CXXOperatorCallExpr>,
                      check::PostStmt<MaterializeTemporaryExpr>,
                      check::LiveSymbols, check::DeadSymbols,
                      eval::Assume> {
 
   std::unique_ptr<BugType> OutOfRangeBugType;
   std::unique_ptr<BugType> MismatchedBugType;
   std::unique_ptr<BugType> InvalidatedBugType;
class IteratorChecker
   void assignToContainer(CheckerContext &C, const Expr *CE, const SVal &RetVal,
                          const MemRegion *Cont) const;
   void handleAssign(CheckerContext &C, const SVal &Cont,
                     const Expr *CE = nullptr,
                     const SVal &OldCont = UndefinedVal()) const;
   void verifyRandomIncrOrDecr(CheckerContext &C, OverloadedOperatorKind Op,
                               const SVal &RetVal, const SVal &LHS,
                               const SVal &RHS) const;
+  void verifyMatch(CheckerContext &C, const SVal &Iter,
+                   const MemRegion *Cont) const;
   void verifyMatch(CheckerContext &C, const SVal &Iter1,
                    const SVal &Iter2) const;
 
   void reportOutOfRangeBug(const StringRef &Message, const SVal &Val,
                            CheckerContext &C, ExplodedNode *ErrNode) const;
   void reportMismatchedBug(const StringRef &Message, const SVal &Val,
                            CheckerContext &C, ExplodedNode *ErrNode) const;
   void reportInvalidatedBug(const StringRef &Message, const SVal &Val,
enum CheckKind {
     CK_NumCheckKinds
   };
 
   DefaultBool ChecksEnabled[CK_NumCheckKinds];
   CheckName CheckNames[CK_NumCheckKinds];
 
   void checkPreCall(const CallEvent &Call, CheckerContext &C) const;
   void checkPostCall(const CallEvent &Call, CheckerContext &C) const;
+  void checkPreStmt(const CXXConstructExpr *CCE, CheckerContext &C) const;
   void checkPreStmt(const CXXOperatorCallExpr *COCE, CheckerContext &C) const;
+  void checkPostStmt(const CXXConstructExpr *CCE, CheckerContext &C) const;
+  void checkPostStmt(const DeclStmt *DS, CheckerContext &C) const;
   void checkPostStmt(const MaterializeTemporaryExpr *MTE,
                      CheckerContext &C) const;
   void checkLiveSymbols(ProgramStateRef State, SymbolReaper &SR) const;
   void checkDeadSymbols(SymbolReaper &SR, CheckerContext &C) const;
   ProgramStateRef evalAssume(ProgramStateRef State, SVal Cond,
                              bool Assumption) const;
 };
 } // namespace

 
 static llvm::APSInt Zero = llvm::APSInt::get(0);
 static llvm::APSInt One = llvm::APSInt::get(1);
 
 namespace {
 
 bool isIteratorType(const QualType &Type);
 bool isIterator(const CXXRecordDecl *CRD);
+bool isComparisonOperator(OverloadedOperatorKind OK);
 bool isBeginCall(const FunctionDecl *Func);
 bool isEndCall(const FunctionDecl *Func);
 bool isAssignmentOperator(OverloadedOperatorKind OK);
 bool isSimpleComparisonOperator(OverloadedOperatorKind OK);
 bool isAccessOperator(OverloadedOperatorKind OK);
 bool isDereferenceOperator(OverloadedOperatorKind OK);
 bool isIncrementOperator(OverloadedOperatorKind OK);
 bool isDecrementOperator(OverloadedOperatorKind OK);
if (Func->isOverloadedOperator()) {
     } else if (ChecksEnabled[CK_IteratorRangeChecker] &&
                isDereferenceOperator(Func->getOverloadedOperator())) {
       // Check for dereference of out-of-range iterators
       if (const auto *InstCall = dyn_cast<CXXInstanceCall>(&Call)) {
         verifyDereference(C, InstCall->getCXXThisVal());
       } else {
         verifyDereference(C, Call.getArgSVal(0));
       }
+    } else if (ChecksEnabled[CK_MismatchedIteratorChecker] &&
+               isComparisonOperator(Func->getOverloadedOperator())) {
+      // Check for comparisons of iterators of different containers
+      if (const auto *InstCall = dyn_cast<CXXInstanceCall>(&Call)) {
+        if (Call.getNumArgs() < 1)
+          return;
+
+        if (!isIteratorType(InstCall->getCXXThisExpr()->getType()) ||
+            !isIteratorType(Call.getArgExpr(0)->getType()))
+          return;
+
+        verifyMatch(C, InstCall->getCXXThisVal(), Call.getArgSVal(0));
+      } else {
+        if (Call.getNumArgs() < 2)
+          return;
+
+        if (!isIteratorType(Call.getArgExpr(0)->getType()) ||
+            !isIteratorType(Call.getArgExpr(1)->getType()))
+          return;
+
+        verifyMatch(C, Call.getArgSVal(0), Call.getArgSVal(1));
+      }
     }
   } else if (!isa<CXXConstructorCall>(&Call)) {
     // The main purpose of iterators is to abstract away from different
     // containers and provide a (maybe limited) uniform access to them.
     // This implies that any correctly written template function that
     // works on multiple containers using iterators takes different
     // template parameters for different containers. So we can safely
     // assume that passing iterators of different containers as arguments
for (unsigned i = 0; i < Call.getNumArgs(); ++i) {
                             Pos->getContainer());
           return;
         }
       }
     }
   }
 }
 
+void IteratorChecker::checkPreStmt(const CXXConstructExpr *CCE,
+                                   CheckerContext &C) const {
+  // Check match of first-last iterator pair in a constructor of a container
+  if (CCE->getNumArgs() < 2)
+    return;
+
+  const auto *Ctr = CCE->getConstructor();
+  if (Ctr->getNumParams() < 2)
+    return;
+
+  if (Ctr->getParamDecl(0)->getName() != "first" ||
+      Ctr->getParamDecl(1)->getName() != "last")
+    return;
+
+  if (!isIteratorType(CCE->getArg(0)->getType()) ||
+      !isIteratorType(CCE->getArg(1)->getType()))
+    return;
+
+  auto State = C.getState();
+  const auto *LCtx = C.getPredecessor()->getLocationContext();
+
+  verifyMatch(C, State->getSVal(CCE->getArg(0), LCtx),
+              State->getSVal(CCE->getArg(1), LCtx));
+}
+
 void IteratorChecker::checkPreStmt(const CXXOperatorCallExpr *COCE,
                                    CheckerContext &C) const {
   const auto *ThisExpr = COCE->getArg(0);
 
   auto State = C.getState();
   const auto *LCtx = C.getLocationContext();
 
   const auto CurrentThis = State->getSVal(ThisExpr, LCtx);
void IteratorChecker::verifyRandomIncrOrDecr(CheckerContext &C,
   if (isOutOfRange(State, newPos)) {
     auto *N = C.generateNonFatalErrorNode(State);
     if (!N)
       return;
     reportOutOfRangeBug("Iterator accessed past its end.", LHS, C, N);
   }
 }
 
+void IteratorChecker::verifyMatch(CheckerContext &C, const SVal &Iter,
+                                  const MemRegion *Cont) const {
+  // Verify match between a container and the container of an iterator
+  while (const auto *CBOR = Cont->getAs<CXXBaseObjectRegion>()) {
+    Cont = CBOR->getSuperRegion();
+  }
+
+  auto State = C.getState();
+  const auto *Pos = getIteratorPosition(State, Iter);
+  if (Pos && Pos->getContainer() != Cont) {
+    auto *N = C.generateNonFatalErrorNode(State);
+    if (!N) {
+      return;
+    }
+    reportMismatchedBug("Iterator access mismatched.", Iter, C, N);
+  }
+}
+
 void IteratorChecker::verifyMatch(CheckerContext &C, const SVal &Iter1,
                                   const SVal &Iter2) const {
   // Verify match between the containers of two iterators
   auto State = C.getState();
   const auto *Pos1 = getIteratorPosition(State, Iter1);
   const auto *Pos2 = getIteratorPosition(State, Iter2);
   if (Pos1 && Pos2 && Pos1->getContainer() != Pos2->getContainer()) {
     // If I do not put a tag here, the comparison test will fail
if (OPK == OO_Star) {
       continue;
     }
   }
 
   return HasCopyCtor && HasCopyAssign && HasDtor && HasPreIncrOp &&
          HasPostIncrOp && HasDerefOp;
 }
 
+bool isComparisonOperator(OverloadedOperatorKind OK) {
+  return OK == OO_EqualEqual || OK == OO_ExclaimEqual || OK == OO_Less ||
+         OK == OO_LessEqual || OK == OO_Greater || OK == OO_GreaterEqual;
+}
+
 bool isBeginCall(const FunctionDecl *Func) {
   const auto *IdInfo = Func->getIdentifier();
   if (!IdInfo)
     return false;
   return IdInfo->getName().endswith_lower("begin");
 }
 
 bool isEndCall(const FunctionDecl *Func) {

test/Analysis/mismatched-iterator.cpp

 // RUN: %clang_analyze_cc1 -std=c++11 -analyzer-checker=core,cplusplus,alpha.cplusplus.MismatchedIterator -analyzer-eagerly-assume -analyzer-config c++-container-inlining=false %s -verify
 // RUN: %clang_analyze_cc1 -std=c++11 -analyzer-checker=core,cplusplus,alpha.cplusplus.MismatchedIterator -analyzer-eagerly-assume -analyzer-config c++-container-inlining=true -DINLINE=1 %s -verify
 
 #include "Inputs/system-header-simulator-cxx.h"
 
+void good_ctor(std::vector<int> &v) {
+  std::vector<int> new_v(v.cbegin(), v.cend()); // no-warning
+}
+
 void good_find(std::vector<int> &v, int n) {
   std::find(v.cbegin(), v.cend(), n); // no-warning
 }
 
 void good_find_first_of(std::vector<int> &v1, std::vector<int> &v2) {
   std::find_first_of(v1.cbegin(), v1.cend(), v2.cbegin(), v2.cend()); // no-warning
 }
 
 void good_copy(std::vector<int> &v1, std::vector<int> &v2, int n) {
   std::copy(v1.cbegin(), v1.cend(), v2.begin()); // no-warning
 }
 
 void good_move_find(std::vector<int> &v1, std::vector<int> &v2, int n) {
   auto i0 = v2.cbegin();
   v1 = std::move(v2);
   std::find(i0, v1.cend(), n); // no-warning
 }
 
+void good_comparison(std::vector<int> &v) {
+  if (v.cbegin() == v.cend()) {} // no-warning
+}
+
+void bad_ctor(std::vector<int> &v1, std::vector<int> &v2) {
+  std::vector<int> new_v(v1.cbegin(), v2.cend()); // expected-warning{{Iterator access mismatched}}
+}
+
 void bad_find(std::vector<int> &v1, std::vector<int> &v2, int n) {
   std::find(v1.cbegin(), v2.cend(), n); // expected-warning{{Iterator access mismatched}}
 }
 
 void bad_find_first_of(std::vector<int> &v1, std::vector<int> &v2) {
   std::find_first_of(v1.cbegin(), v2.cend(), v2.cbegin(), v2.cend()); // expected-warning{{Iterator access mismatched}}
   std::find_first_of(v1.cbegin(), v1.cend(), v2.cbegin(), v1.cend()); // expected-warning{{Iterator access mismatched}}
 }
 
 void bad_move_find(std::vector<int> &v1, std::vector<int> &v2, int n) {
   auto i0 = v2.cbegin();
   v1 = std::move(v2);
   std::find(i0, v2.cend(), n); // expected-warning{{Iterator access mismatched}}
 }
+
+void bad_comparison(std::vector<int> &v1, std::vector<int> &v2) {
+  if (v1.cbegin() != v2.cend()) { // expected-warning{{Iterator access mismatched}}
+    *v1.cbegin();
+  }
+}