[Analyzer] Iterator Checker - Part 4: Mismatched iterator checker for function parameters

[baloghadamsoftware]

Summary

New check added to the checker which checks whether iterator parameters of template functions typed by the same template parameter refer to the same container.

[NoQ]

lib/StaticAnalyzer/Checkers/IteratorChecker.cpp

396–414

Could you add more comments on how this machinery works, probably with examples?

[baloghadamsoftware]

Rebased to current Part 3. Comment added.

[a.sidorin]

Hello Adam,
This looks like a nice improvement. I have some remarks inline.

lib/StaticAnalyzer/Checkers/IteratorChecker.cpp

384

The function becomes > 100 lines long. Should we refactor this check into a separate function to improve readability?

390

While this assumption is sane and is true for <algorithm> functions, user code can have other design solutions. There is nothing that prevents users from writing a function looking like:

template <typename IterTy>
void f(IterTy FromBegin, IterTy FromEnd, IterTy ToBegin, IterTy ToEnd);

and there is nothing wrong with it.
One of possible solutions is to restrict checker to check only functions from std namespace. What do you think?

412

size_t I = 0?

914

We always report about first iterator, but the mismatched one can be second. I think this deserves a FIXME, at least.

1012

We usually pass StringRefs and SVals by value because they're very cheap for copying. However, the surrounding code follows the same conventions so it's not strongly required to change.

[baloghadamsoftware]

lib/StaticAnalyzer/Checkers/IteratorChecker.cpp

384

Yes, I think so this would be a good idea. Should I do it now?

390

We can restrict, of course, but first we should measure how it performs on real code. With the restriction, we can get rid of some false positives but we may also loose some true positives.

[baloghadamsoftware]

Updated according to some comments.

[baloghadamsoftware]

Rebased to rL335835.

[baloghadamsoftware]

Previous rebase was wrong, this is the correct one.

[whisperity]

include/clang/StaticAnalyzer/Checkers/Checkers.td

320

Is there any particular order entries of this file should be in? Seems to be broken now, but I guess when this patch comes up to the top of the stack it shall be fixed at a rebase.

lib/StaticAnalyzer/Checkers/IteratorChecker.cpp

427

functions' parameters' ?

914

If this string is the message that gets printed to the user, I think it must be rephrased a bit. If this message came across me, I'd be puzzled at first to understand what it is trying to mean.

[baloghadamsoftware]

lib/StaticAnalyzer/Checkers/IteratorChecker.cpp

390

One more thing:

The main purpose of iterators is to make algorithms independent of the data representation. So you can decide whether your algorithm works on a specific representation and create non-template function that takes reference for the specific container itself or you make it generic so you use template function which takes iterators. If you chose this latter one for an algorithm that works on two different container then there is no point to restrict the function to only work on two containers with exactly the same representation. Either specific or generic, but there is no point for something in between.

[NoQ]

Looks good. I guess we may have to tone down the heuristic about "all template functions" if we see it fail.

@a.sidorin and @whisperity have some valid minor comments.

[baloghadamsoftware]

Since rL338263 fixed a bug in the cleanup phase the tests for mismatched iterator checker did not pass. The reason for this is that the region of some LazyCompoundVals are cleaned up while there are still iterator positions connected to the LazyCompoundVal itself. This happens typically for arguments which are constructed in-place (e.g. begin() or end() of a container is invoked in the argument itself).

We applied a fix here that defers cleanup of such iterator positions. No other solution comes to my mind at the moment.

I wanted to upload this fix in a separate patch but I could not create tests for it.

@NoQ please review this fix before I commit the patch.

[baloghadamsoftware]

Minor changes.

[baloghadamsoftware]

include/clang/StaticAnalyzer/Checkers/Checkers.td

320

Alphabetical order. Now it seems to be OK.

lib/StaticAnalyzer/Checkers/IteratorChecker.cpp

384

I propose to refactor it later in a separate patch.

include/clang/StaticAnalyzer/Checkers/Checkers.td

 
 let ParentPackage = CplusplusAlpha in {
 
 def DeleteWithNonVirtualDtorChecker : Checker<"DeleteWithNonVirtualDtor">,
   HelpText<"Reports destructions of polymorphic objects with a non-virtual "
            "destructor in their base class">,
   DescFile<"DeleteWithNonVirtualDtorChecker.cpp">;
 
+def InvalidatedIteratorChecker : Checker<"InvalidatedIterator">,
+  HelpText<"Check for use of invalidated iterators">,
+  DescFile<"IteratorChecker.cpp">;
+
 def IteratorRangeChecker : Checker<"IteratorRange">,
   HelpText<"Check for iterators used outside their valid ranges">,
   DescFile<"IteratorChecker.cpp">;
 
-def InvalidatedIteratorChecker : Checker<"InvalidatedIterator">,
-  HelpText<"Check for use of invalidated iterators">,
+def MismatchedIteratorChecker : Checker<"MismatchedIterator">,
+  HelpText<"Check for use of iterators of different containers where iterators of the same container are expected">,
   DescFile<"IteratorChecker.cpp">;
 
 def MisusedMovedObjectChecker: Checker<"MisusedMovedObject">,
      HelpText<"Method calls on a moved-from object and copying a moved-from "
               "object will be reported">,
      DescFile<"MisusedMovedObjectChecker.cpp">;
 
 def UninitializedObjectChecker: Checker<"UninitializedObject">,

lib/StaticAnalyzer/Checkers/IteratorChecker.cpp

 
 class IteratorChecker
     : public Checker<check::PreCall, check::PostCall,
                      check::PostStmt<MaterializeTemporaryExpr>,
                      check::LiveSymbols, check::DeadSymbols,
                      eval::Assume> {
 
   std::unique_ptr<BugType> OutOfRangeBugType;
+  std::unique_ptr<BugType> MismatchedBugType;
   std::unique_ptr<BugType> InvalidatedBugType;
 
   void handleComparison(CheckerContext &C, const SVal &RetVal, const SVal &LVal,
                         const SVal &RVal, OverloadedOperatorKind Op) const;
   void verifyAccess(CheckerContext &C, const SVal &Val) const;
   void verifyDereference(CheckerContext &C, const SVal &Val) const;
   void handleIncrement(CheckerContext &C, const SVal &RetVal, const SVal &Iter,
                        bool Postfix) const;
   void handleDecrement(CheckerContext &C, const SVal &RetVal, const SVal &Iter,
                        bool Postfix) const;
   void handleRandomIncrOrDecr(CheckerContext &C, OverloadedOperatorKind Op,
                               const SVal &RetVal, const SVal &LHS,
                               const SVal &RHS) const;
   void handleBegin(CheckerContext &C, const Expr *CE, const SVal &RetVal,
                    const SVal &Cont) const;
   void handleEnd(CheckerContext &C, const Expr *CE, const SVal &RetVal,
                  const SVal &Cont) const;
   void assignToContainer(CheckerContext &C, const Expr *CE, const SVal &RetVal,
                          const MemRegion *Cont) const;
   void handleAssign(CheckerContext &C, const SVal &Cont) const;
   void verifyRandomIncrOrDecr(CheckerContext &C, OverloadedOperatorKind Op,
                               const SVal &RetVal, const SVal &LHS,
                               const SVal &RHS) 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 &Val1,
+                           const SVal &Val2, CheckerContext &C,
+                           ExplodedNode *ErrNode) const;
   void reportInvalidatedBug(const StringRef &Message, const SVal &Val,
                             CheckerContext &C, ExplodedNode *ErrNode) const;
 
 public:
   IteratorChecker();
 
   enum CheckKind {
     CK_IteratorRangeChecker,
+    CK_MismatchedIteratorChecker,
     CK_InvalidatedIteratorChecker,
     CK_NumCheckKinds
   };
 
   DefaultBool ChecksEnabled[CK_NumCheckKinds];
   CheckName CheckNames[CK_NumCheckKinds];
 
   void checkPreCall(const CallEvent &Call, CheckerContext &C) const;
ProgramStateRef relateIteratorPositions(ProgramStateRef State,
                                         bool Equal);
 ProgramStateRef invalidateAllIteratorPositions(ProgramStateRef State,
                                                const MemRegion *Cont);
 const ContainerData *getContainerData(ProgramStateRef State,
                                       const MemRegion *Cont);
 ProgramStateRef setContainerData(ProgramStateRef State, const MemRegion *Cont,
                                  const ContainerData &CData);
 bool hasLiveIterators(ProgramStateRef State, const MemRegion *Cont);
+bool isBoundThroughLazyCompoundVal(const Environment &Env,
+                                   const MemRegion *Reg);
 bool isOutOfRange(ProgramStateRef State, const IteratorPosition &Pos);
 bool isZero(ProgramStateRef State, const NonLoc &Val);
 } // namespace
 
 IteratorChecker::IteratorChecker() {
   OutOfRangeBugType.reset(
       new BugType(this, "Iterator out of range", "Misuse of STL APIs"));
   OutOfRangeBugType->setSuppressOnSink(true);
+  MismatchedBugType.reset(
+      new BugType(this, "Iterator(s) mismatched", "Misuse of STL APIs"));
+  MismatchedBugType->setSuppressOnSink(true);
   InvalidatedBugType.reset(
       new BugType(this, "Iterator invalidated", "Misuse of STL APIs"));
   InvalidatedBugType->setSuppressOnSink(true);
 }
 
 void IteratorChecker::checkPreCall(const CallEvent &Call,
                                    CheckerContext &C) const {
   // Check for out of range access or access of invalidated position and
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 (!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
+    // whose type replaces the same template parameter is a bug.
+    //
+    // Example:
+    // template<typename I1, typename I2>
+    // void f(I1 first1, I1 last1, I2 first2, I2 last2);
+    // 
+    // In this case the first two arguments to f() must be iterators must belong
+    // to the same container and the last to also to the same container but
+    // not neccessarily to the same as the first two.
+
+    if (!ChecksEnabled[CK_MismatchedIteratorChecker])
+      return;
+
+    const auto *Templ = Func->getPrimaryTemplate();
+    if (!Templ)
+      return;
+
+    const auto *TParams = Templ->getTemplateParameters();
+    const auto *TArgs = Func->getTemplateSpecializationArgs();
+
+    // Iterate over all the template parameters
+    for (size_t I = 0; I < TParams->size(); ++I) {
+      const auto *TPDecl = dyn_cast<TemplateTypeParmDecl>(TParams->getParam(I));
+      if (!TPDecl)
+        continue;
+
+      if (TPDecl->isParameterPack())
+        continue;
+
+      const auto TAType = TArgs->get(I).getAsType();
+      if (!isIteratorType(TAType))
+        continue;
+
+      SVal LHS = UndefinedVal();
+
+      // For every template parameter which is an iterator type in the
+      // instantiation look for all functions' parameters' type by it and
+      // check whether they belong to the same container
+      for (auto J = 0U; J < Func->getNumParams(); ++J) {
+        const auto *Param = Func->getParamDecl(J);
+        const auto *ParamType =
+            Param->getType()->getAs<SubstTemplateTypeParmType>();
+        if (!ParamType ||
+            ParamType->getReplacedParameter()->getDecl() != TPDecl)
+          continue;
+        if (LHS.isUndef()) {
+          LHS = Call.getArgSVal(J);
+        } else {
+          verifyMatch(C, LHS, Call.getArgSVal(J));
+        }
+      }
+    }
   }
 }
 
 void IteratorChecker::checkPostCall(const CallEvent &Call,
                                     CheckerContext &C) const {
   // Record new iterator positions and iterator position changes
   const auto *Func = dyn_cast_or_null<FunctionDecl>(Call.getDecl());
   if (!Func)

 void IteratorChecker::checkDeadSymbols(SymbolReaper &SR,
                                        CheckerContext &C) const {
   // Cleanup
   auto State = C.getState();
 
   auto RegionMap = State->get<IteratorRegionMap>();
   for (const auto Reg : RegionMap) {
     if (!SR.isLiveRegion(Reg.first)) {
+      // The region behind the `LazyCompoundVal` is often cleaned up before
+      // the `LazyCompoundVal` itself. If there are iterator positions keyed
+      // by these regions their cleanup must be deferred.
+      if (!isBoundThroughLazyCompoundVal(State->getEnvironment(), Reg.first)) {
         State = State->remove<IteratorRegionMap>(Reg.first);
       }
     }
+  }
 
   auto SymbolMap = State->get<IteratorSymbolMap>();
   for (const auto Sym : SymbolMap) {
     if (!SR.isLive(Sym.first)) {
       State = State->remove<IteratorSymbolMap>(Sym.first);
     }
   }
 
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 &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()) {
+    auto *N = C.generateNonFatalErrorNode(State);
+    if (!N)
+      return;
+    reportMismatchedBug("Iterators of different containers used where the "
+                        "same container is expected.", Iter1, Iter2, C, N);
+  }
+}
+
 void IteratorChecker::handleBegin(CheckerContext &C, const Expr *CE,
                                   const SVal &RetVal, const SVal &Cont) const {
   const auto *ContReg = Cont.getAsRegion();
   if (!ContReg)
     return;
 
   while (const auto *CBOR = ContReg->getAs<CXXBaseObjectRegion>()) {
     ContReg = CBOR->getSuperRegion();

 void IteratorChecker::reportOutOfRangeBug(const StringRef &Message,
                                           const SVal &Val, CheckerContext &C,
                                           ExplodedNode *ErrNode) const {
   auto R = llvm::make_unique<BugReport>(*OutOfRangeBugType, Message, ErrNode);
   R->markInteresting(Val);
   C.emitReport(std::move(R));
 }
 
+void IteratorChecker::reportMismatchedBug(const StringRef &Message,
+                                          const SVal &Val1, const SVal &Val2,
+                                          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::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));
 }
 
bool hasLiveIterators(ProgramStateRef State, const MemRegion *Cont) {
   for (const auto Sym : SymbolMap) {
     if (Sym.second.getContainer() == Cont)
       return true;
   }
 
   return false;
 }
 
+bool isBoundThroughLazyCompoundVal(const Environment &Env,
+                                   const MemRegion *Reg) {
+  for (const auto Binding: Env) {
+    if (const auto LCVal = Binding.second.getAs<nonloc::LazyCompoundVal>()) {
+      if (LCVal->getRegion() == Reg)
+        return true;
+    }
+  }
+
+  return false;
+}
+
 template <typename Condition, typename Process>
 ProgramStateRef processIteratorPositions(ProgramStateRef State, Condition Cond,
                                          Process Proc) {
   auto &RegionMapFactory = State->get_context<IteratorRegionMap>();
   auto RegionMap = State->get<IteratorRegionMap>();
   bool Changed = false;
   for (const auto Reg : RegionMap) {
     if (Cond(Reg.second)) {
#define REGISTER_CHECKER(name)                                                 \
   void ento::register##name(CheckerManager &Mgr) {                             \
     auto *checker = Mgr.registerChecker<IteratorChecker>();                    \
     checker->ChecksEnabled[IteratorChecker::CK_##name] = true;                 \
     checker->CheckNames[IteratorChecker::CK_##name] =                          \
         Mgr.getCurrentCheckName();                                             \
   }
 
 REGISTER_CHECKER(IteratorRangeChecker)
+REGISTER_CHECKER(MismatchedIteratorChecker)
 REGISTER_CHECKER(InvalidatedIteratorChecker)

test/Analysis/Inputs/system-header-simulator-cxx.h

prev (BidirectionalIterator it,
         1) {
     advance(it, -n);
     return it;
   }
 
   template <class InputIterator, class T>
   InputIterator find(InputIterator first, InputIterator last, const T &val);
 
+  template <class ForwardIterator1, class ForwardIterator2>
+  ForwardIterator1 find_first_of(ForwardIterator1 first1,
+                                 ForwardIterator1 last1,
+                                 ForwardIterator2 first2,
+                                 ForwardIterator2 last2);
+
   template <class InputIterator, class OutputIterator>
   OutputIterator copy(InputIterator first, InputIterator last,
                       OutputIterator result);
 
 }
 
 #ifdef TEST_INLINABLE_ALLOCATORS
 namespace std {

test/Analysis/invalidated-iterator.cpp

-// RUN: %clang_analyze_cc1 -std=c++11 -analyzer-checker=core,cplusplus,alpha.cplusplus.InvalidatedIterator -analyzer-config aggressive-relational-comparison-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-relational-comparison-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 %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
 
 #include "Inputs/system-header-simulator-cxx.h"
 
 void bad_copy_assign_operator_list1(std::list<int> &L1,
                                     const std::list<int> &L2) {
   auto i0 = L1.cbegin();
   L1 = L2;
   *i0; // expected-warning{{Invalidated iterator accessed}}

test/Analysis/mismatched-iterator.cpp

+// RUN: %clang_analyze_cc1 -std=c++11 -analyzer-checker=core,cplusplus,alpha.cplusplus.MismatchedIterator -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.MismatchedIterator -analyzer-config aggressive-binary-operation-simplification=true -analyzer-config c++-container-inlining=true -DINLINE=1 %s -verify
+
+#include "Inputs/system-header-simulator-cxx.h"
+
+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 bad_find(std::vector<int> &v1, std::vector<int> &v2, int n) {
+  std::find(v1.cbegin(), v2.cend(), n); // expected-warning{{Iterators of different containers used where the same container is expected}}
+}
+
+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{{Iterators of different containers used where the same container is expected}}
+  std::find_first_of(v1.cbegin(), v1.cend(), v2.cbegin(), v1.cend()); // expected-warning{{Iterators of different containers used where the same container is expected}}
+}