[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

640–641

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

class IteratorChecker
   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 &Val1,
                            const SVal &Val2, CheckerContext &C,
                            ExplodedNode *ErrNode) const;
+  void reportMismatchedBug(const StringRef &Message, const SVal &Val,
+                           const MemRegion *Reg, CheckerContext &C,
+                           ExplodedNode *ErrNode) const;
   void reportInvalidatedBug(const StringRef &Message, const SVal &Val,
                             CheckerContext &C, ExplodedNode *ErrNode) const;
 
 public:
   IteratorChecker();
 
   enum CheckKind {
     CK_IteratorRangeChecker,

 
 REGISTER_MAP_WITH_PROGRAMSTATE(IteratorComparisonMap, const SymExpr *,
                                IteratorComparison)
 
 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)) {
+  } else if (isa<CXXConstructorCall>(&Call)) {
+    // Check match of first-last iterator pair in a constructor of a container
+    if (Call.getNumArgs() < 2)
+      return;
+
+    const auto *Ctr = cast<CXXConstructorDecl>(Call.getDecl());
+    if (Ctr->getNumParams() < 2)
+      return;
+
+    if (Ctr->getParamDecl(0)->getName() != "first" ||
+        Ctr->getParamDecl(1)->getName() != "last")
+      return;
+
+    if (!isIteratorType(Call.getArgExpr(0)->getType()) ||
+        !isIteratorType(Call.getArgExpr(1)->getType()))
+      return;
+
+    verifyMatch(C, Call.getArgSVal(0), Call.getArgSVal(1));
+  } else {
     // 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
     // whose type replaces the same template parameter is a bug.
     //
void IteratorChecker::checkLiveSymbols(ProgramStateRef State,
                                        SymbolReaper &SR) const {
   // Keep symbolic expressions of iterator positions, container begins and ends
   // alive
   auto RegionMap = State->get<IteratorRegionMap>();
   for (const auto Reg : RegionMap) {
     const auto Offset = Reg.second.getOffset();
     for (auto i = Offset->symbol_begin(); i != Offset->symbol_end(); ++i)
       if (isa<SymbolData>(*i))
         SR.markLive(*i);
   }
 
   auto SymbolMap = State->get<IteratorSymbolMap>();
   for (const auto Sym : SymbolMap) {
     const auto Offset = Sym.second.getOffset();
     for (auto i = Offset->symbol_begin(); i != Offset->symbol_end(); ++i)
       if (isa<SymbolData>(*i))
         SR.markLive(*i);
   }
void IteratorChecker::reportMismatchedBug(const StringRef &Message,
                                           CheckerContext &C,
                                           ExplodedNode *ErrNode) const {
   auto R = llvm::make_unique<BugReport>(*MismatchedBugType, Message, ErrNode);
   R->markInteresting(Val1);
   R->markInteresting(Val2);
   C.emitReport(std::move(R));
 }
 
+void IteratorChecker::reportMismatchedBug(const StringRef &Message,
+                                          const SVal &Val, const MemRegion *Reg,
+                                          CheckerContext &C,
+                                          ExplodedNode *ErrNode) const {
+  auto R = llvm::make_unique<BugReport>(*MismatchedBugType, Message, ErrNode);
+  R->markInteresting(Val);
+  R->markInteresting(Reg);
+  C.emitReport(std::move(R));
+}
+
 void IteratorChecker::reportInvalidatedBug(const StringRef &Message,
                                            const SVal &Val, CheckerContext &C,
                                            ExplodedNode *ErrNode) const {
   auto R = llvm::make_unique<BugReport>(*InvalidatedBugType, Message, ErrNode);
   R->markInteresting(Val);
   C.emitReport(std::move(R));
 }
 
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) {