[Analyzer] Iterator Checkers - Make range errors and invalidated access fatal

[baloghadamsoftware]

Summary

Range errors (dereferencing or incrementing the past-the-end iterator or decrementing the iterator of the first element of the range) and access of invalidated iterators lead to undefined behavior. There is no point to continue the analysis after such an error on the same execution path, but terminate it by a sink node (fatal error). This also improves the performance and helps avoiding double reports (e.g. in case of nested iterators).

[baloghadamsoftware]

I left errors caused by mismatched iterators non-fatal for now. This is debatable because passing a function expecting a range iterators for two different containers or applying a container modifier using a mismatched iterator also leads to undefined behavior. However, comparing two iterators of different containers always returns false thus it is non-fatal. Maybe we should separate these two cases and report the first one as fatal, the second one as non-fatal errors.

[baloghadamsoftware]

Gentle ping.

[Szelethus]

Makes sense! But, does any of the test cases actually test *this* particular change?

[baloghadamsoftware]

In D62893#1608000, @Szelethus wrote:

Makes sense! But, does any of the test cases actually test *this* particular change?

I added some reachability checks before committing.

cfe/trunk/lib/StaticAnalyzer/Checkers/IteratorChecker.cpp

 bool isPastTheEnd(ProgramStateRef State, const IteratorPosition &Pos);
 bool isAheadOfRange(ProgramStateRef State, const IteratorPosition &Pos);
 bool isBehindPastTheEnd(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",
-                  /*SuppressOnSink=*/true));
+      new BugType(this, "Iterator out of range", "Misuse of STL APIs"));
   MismatchedBugType.reset(
       new BugType(this, "Iterator(s) mismatched", "Misuse of STL APIs",
                   /*SuppressOnSink=*/true));
   InvalidatedBugType.reset(
-      new BugType(this, "Iterator invalidated", "Misuse of STL APIs",
-                  /*SuppressOnSink=*/true));
+      new BugType(this, "Iterator invalidated", "Misuse of STL APIs"));
 }
 
 void IteratorChecker::checkPreCall(const CallEvent &Call,
                                    CheckerContext &C) const {
   // Check for out of range access or access of invalidated position and
   // iterator mismatches
   const auto *Func = dyn_cast_or_null<FunctionDecl>(Call.getDecl());
   if (!Func)
void IteratorChecker::processComparison(CheckerContext &C,
   }
 }
 
 void IteratorChecker::verifyDereference(CheckerContext &C,
                                         const SVal &Val) const {
   auto State = C.getState();
   const auto *Pos = getIteratorPosition(State, Val);
   if (Pos && isPastTheEnd(State, *Pos)) {
-    auto *N = C.generateNonFatalErrorNode(State);
+    auto *N = C.generateErrorNode(State);
     if (!N)
       return;
     reportOutOfRangeBug("Past-the-end iterator dereferenced.", Val, C, N);
     return;
   }
 }
 
 void IteratorChecker::verifyAccess(CheckerContext &C, const SVal &Val) const {
   auto State = C.getState();
   const auto *Pos = getIteratorPosition(State, Val);
   if (Pos && !Pos->isValid()) {
-    auto *N = C.generateNonFatalErrorNode(State);
+    auto *N = C.generateErrorNode(State);
     if (!N) {
       return;
     }
     reportInvalidatedBug("Invalidated iterator accessed.", Val, C, N);
   }
 }
 
 void IteratorChecker::handleIncrement(CheckerContext &C, const SVal &RetVal,
void IteratorChecker::verifyRandomIncrOrDecr(CheckerContext &C,
 
   // Incremention or decremention by 0 is never a bug.
   if (isZero(State, Value.castAs<NonLoc>()))
     return;
 
   // The result may be the past-end iterator of the container, but any other
   // out of range position is undefined behaviour
   if (isAheadOfRange(State, advancePosition(C, Op, *Pos, Value))) {
-    auto *N = C.generateNonFatalErrorNode(State);
+    auto *N = C.generateErrorNode(State);
     if (!N)
       return;
     reportOutOfRangeBug("Iterator decremented ahead of its valid range.", LHS,
                         C, N);
   }
   if (isBehindPastTheEnd(State, advancePosition(C, Op, *Pos, Value))) {
-    auto *N = C.generateNonFatalErrorNode(State);
+    auto *N = C.generateErrorNode(State);
     if (!N)
       return;
     reportOutOfRangeBug("Iterator incremented behind the past-the-end "
                         "iterator.", LHS, C, N);
   }
 }
 
 void IteratorChecker::verifyMatch(CheckerContext &C, const SVal &Iter,

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

template <typename T, typename Ptr, typename Ref> struct __list_iterator {
 
   typedef ptrdiff_t difference_type;
   typedef T value_type;
   typedef Ptr pointer;
   typedef Ref reference;
   typedef std::bidirectional_iterator_tag iterator_category;
 
   __list_iterator(T* it = 0) : item(it) {}
-  __list_iterator(const iterator &rhs): item(rhs.base()) {}
+  __list_iterator(const iterator &rhs): item(rhs.item) {}
   __list_iterator<T, Ptr, Ref> operator++() { item = item->next; return *this; }
   __list_iterator<T, Ptr, Ref> operator++(int) {
     auto tmp = *this;
     item = item->next;
     return tmp;
   }
   __list_iterator<T, Ptr, Ref> operator--() { item = item->prev; return *this; }
   __list_iterator<T, Ptr, Ref> operator--(int) {
     auto tmp = *this;
     item = item->prev;
     return tmp;
   }
 
   Ref operator*() const { return item->data; }
   Ptr operator->() const { return item->data; }
 
   bool operator==(const iterator &rhs) const { return item == rhs->item; }
   bool operator==(const const_iterator &rhs) const { return item == rhs->item; }
 
   bool operator!=(const iterator &rhs) const { return item != rhs->item; }
   bool operator!=(const const_iterator &rhs) const { return item != rhs->item; }
 
   const T* &base() const { return item; }
 
+  template <typename UT, typename UPtr, typename URef>
+  friend struct __list_iterator;
+
 private:
   T* item;
 };
 
 template <typename T, typename Ptr, typename Ref> struct __fwdl_iterator {
   typedef __fwdl_iterator<T, __typeof__(T::data) *, __typeof__(T::data) &> iterator;
   typedef __fwdl_iterator<T, const __typeof__(T::data) *, const __typeof__(T::data) &> const_iterator;
 
   typedef ptrdiff_t difference_type;
   typedef T value_type;
   typedef Ptr pointer;
   typedef Ref reference;
   typedef std::forward_iterator_tag iterator_category;
 
   __fwdl_iterator(T* it = 0) : item(it) {}
-  __fwdl_iterator(const iterator &rhs): item(rhs.base()) {}
+  __fwdl_iterator(const iterator &rhs): item(rhs.item) {}
   __fwdl_iterator<T, Ptr, Ref> operator++() { item = item->next; return *this; }
   __fwdl_iterator<T, Ptr, Ref> operator++(int) {
     auto tmp = *this;
     item = item->next;
     return tmp;
   }
   Ref operator*() const { return item->data; }
   Ptr operator->() const { return item->data; }
 
   bool operator==(const iterator &rhs) const { return item == rhs->item; }
   bool operator==(const const_iterator &rhs) const { return item == rhs->item; }
 
   bool operator!=(const iterator &rhs) const { return item != rhs->item; }
   bool operator!=(const const_iterator &rhs) const { return item != rhs->item; }
 
   const T* &base() const { return item; }
 
+  template <typename UT, typename UPtr, typename URef>
+  friend struct __fwdl_iterator;
+
 private:
   T* item;
 };
 
 namespace std {
   template <class T1, class T2>
   struct pair {
     T1 first;

cfe/trunk/test/Analysis/diagnostics/explicit-suppression.cpp

class C {
   // The virtual function is to make C not trivially copy assignable so that we call the
   // variant of std::copy() that does not defer to memmove().
   virtual int f();
 };
 
 void testCopyNull(C *I, C *E) {
   std::copy(I, E, (C *)0);
 #ifndef SUPPRESSED
-  // expected-warning@../Inputs/system-header-simulator-cxx.h:680 {{Called C++ object pointer is null}}
+  // expected-warning@../Inputs/system-header-simulator-cxx.h:686 {{Called C++ object pointer is null}}
 #endif
 }

cfe/trunk/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
 
 #include "Inputs/system-header-simulator-cxx.h"
 
-void bad_copy_assign_operator_list1(std::list<int> &L1,
+void clang_analyzer_warnIfReached();
+
+void bad_copy_assign_operator1_list(std::list<int> &L1,
                                     const std::list<int> &L2) {
   auto i0 = L1.cbegin();
   L1 = L2;
   *i0; // expected-warning{{Invalidated iterator accessed}}
+  clang_analyzer_warnIfReached();
 }
 
-void bad_copy_assign_operator_vector1(std::vector<int> &V1,
+void bad_copy_assign_operator1_vector(std::vector<int> &V1,
                                       const std::vector<int> &V2) {
   auto i0 = V1.cbegin();
   V1 = V2;
   *i0; // expected-warning{{Invalidated iterator accessed}}
 }
 
-void bad_copy_assign_operator_deque1(std::deque<int> &D1,
+void bad_copy_assign_operator1_deque(std::deque<int> &D1,
                                      const std::deque<int> &D2) {
   auto i0 = D1.cbegin();
   D1 = D2;
   *i0; // expected-warning{{Invalidated iterator accessed}}
 }
 
-void bad_copy_assign_operator_forward_list1(std::forward_list<int> &FL1,
+void bad_copy_assign_operator1_forward_list(std::forward_list<int> &FL1,
                                             const std::forward_list<int> &FL2) {
   auto i0 = FL1.cbegin();
   FL1 = FL2;
   *i0; // expected-warning{{Invalidated iterator accessed}}
 }
 
-void bad_assign_list1(std::list<int> &L, int n) {
+void bad_assign1_list(std::list<int> &L, int n) {
   auto i0 = L.cbegin();
   L.assign(10, n);
   *i0; // expected-warning{{Invalidated iterator accessed}}
 }
 
-void bad_assign_vector1(std::vector<int> &V, int n) {
+void bad_assign1_vector(std::vector<int> &V, int n) {
   auto i0 = V.cbegin();
   V.assign(10, n);
   *i0; // expected-warning{{Invalidated iterator accessed}}
 }
 
-void bad_assign_deque1(std::deque<int> &D, int n) {
+void bad_assign1_deque(std::deque<int> &D, int n) {
   auto i0 = D.cbegin();
   D.assign(10, n);
   *i0; // expected-warning{{Invalidated iterator accessed}}
 }
 
-void bad_assign_forward_list1(std::forward_list<int> &FL, int n) {
+void bad_assign1_forward_list(std::forward_list<int> &FL, int n) {
   auto i0 = FL.cbegin();
   FL.assign(10, n);
   *i0; // expected-warning{{Invalidated iterator accessed}}
 }
 
-void good_clear_list1(std::list<int> &L) {
+void good_clear1_list(std::list<int> &L) {
   auto i0 = L.cend();
   L.clear();
   --i0; // no-warning
 }
 
-void bad_clear_list1(std::list<int> &L) {
+void bad_clear1_list(std::list<int> &L) {
   auto i0 = L.cbegin(), i1 = L.cend();
   L.clear();
   *i0; // expected-warning{{Invalidated iterator accessed}}
 }
 
-void bad_clear_vector1(std::vector<int> &V) {
+void bad_clear1_vector(std::vector<int> &V) {
   auto i0 = V.cbegin(), i1 = V.cend();
   V.clear();
   *i0; // expected-warning{{Invalidated iterator accessed}}
+}
+
+void bad_clear1_vector_decr(std::vector<int> &V) {
+  auto i0 = V.cbegin(), i1 = V.cend();
+  V.clear();
   --i1; // expected-warning{{Invalidated iterator accessed}}
 }
 
-void bad_clear_deque1(std::deque<int> &D) {
+void bad_clear1_deque(std::deque<int> &D) {
   auto i0 = D.cbegin(), i1 = D.cend();
   D.clear();
   *i0; // expected-warning{{Invalidated iterator accessed}}
+}
+
+void bad_clear1_deque_decr(std::deque<int> &D) {
+  auto i0 = D.cbegin(), i1 = D.cend();
+  D.clear();
   --i1; // expected-warning{{Invalidated iterator accessed}}
 }
 
-void good_push_back_list1(std::list<int> &L, int n) {
+void good_push_back1_list(std::list<int> &L, int n) {
   auto i0 = L.cbegin(), i1 = L.cend();
   L.push_back(n);
   *i0; // no-warning
   --i1; // no-warning
 }
 
-void good_push_back_vector1(std::vector<int> &V, int n) {
+void good_push_back1_vector(std::vector<int> &V, int n) {
   auto i0 = V.cbegin(), i1 = V.cend();
   V.push_back(n);
   *i0; // no-warning
 }
 
-void bad_push_back_vector1(std::vector<int> &V, int n) {
+void bad_push_back1_vector(std::vector<int> &V, int n) {
   auto i0 = V.cbegin(), i1 = V.cend();
   V.push_back(n);
   --i1; // expected-warning{{Invalidated iterator accessed}}
 }
 
-void bad_push_back_deque1(std::deque<int> &D, int n) {
+void bad_push_back1_deque(std::deque<int> &D, int n) {
   auto i0 = D.cbegin(), i1 = D.cend();
   D.push_back(n);
   *i0; // expected-warning{{Invalidated iterator accessed}}
+}
+
+void bad_push_back1_deque_decr(std::deque<int> &D, int n) {
+  auto i0 = D.cbegin(), i1 = D.cend();
+  D.push_back(n);
   --i1; // expected-warning{{Invalidated iterator accessed}}
 }
 
-void good_emplace_back_list1(std::list<int> &L, int n) {
+void good_emplace_back1_list(std::list<int> &L, int n) {
   auto i0 = L.cbegin(), i1 = L.cend();
   L.emplace_back(n);
   *i0; // no-warning
   --i1; // no-warning
 }
 
-void good_emplace_back_vector1(std::vector<int> &V, int n) {
+void good_emplace_back1_vector(std::vector<int> &V, int n) {
   auto i0 = V.cbegin(), i1 = V.cend();
   V.emplace_back(n);
   *i0; // no-warning
 }
 
-void bad_emplace_back_vector1(std::vector<int> &V, int n) {
+void bad_emplace_back1_vector(std::vector<int> &V, int n) {
   auto i0 = V.cbegin(), i1 = V.cend();
   V.emplace_back(n);
   --i1; // expected-warning{{Invalidated iterator accessed}}
 }
 
-void bad_emplace_back_deque1(std::deque<int> &D, int n) {
+void bad_emplace_back1_deque(std::deque<int> &D, int n) {
   auto i0 = D.cbegin(), i1 = D.cend();
   D.emplace_back(n);
   *i0; // expected-warning{{Invalidated iterator accessed}}
+}
+
+void bad_emplace_back1_deque_decr(std::deque<int> &D, int n) {
+  auto i0 = D.cbegin(), i1 = D.cend();
+  D.emplace_back(n);
   --i1; // expected-warning{{Invalidated iterator accessed}}
 }
 
-void good_pop_back_list1(std::list<int> &L, int n) {
+void good_pop_back1_list(std::list<int> &L, int n) {
   auto i0 = L.cbegin(), i1 = L.cend(), i2 = i1--;
   L.pop_back();
   *i0; // no-warning
   *i2; // no-warning
 }
 
-void bad_pop_back_list1(std::list<int> &L, int n) {
+void bad_pop_back1_list(std::list<int> &L, int n) {
   auto i0 = L.cbegin(), i1 = L.cend(), i2 = i1--;
   L.pop_back();
   *i1; // expected-warning{{Invalidated iterator accessed}}
 }
 
-void good_pop_back_vector1(std::vector<int> &V, int n) {
+void good_pop_back1_vector(std::vector<int> &V, int n) {
   auto i0 = V.cbegin(), i1 = V.cend(), i2 = i1--;
   V.pop_back();
   *i0; // no-warning
 }
 
-void bad_pop_back_vector1(std::vector<int> &V, int n) {
+void bad_pop_back1_vector(std::vector<int> &V, int n) {
   auto i0 = V.cbegin(), i1 = V.cend(), i2 = i1--;
   V.pop_back();
   *i1; // expected-warning{{Invalidated iterator accessed}}
+}
+
+void bad_pop_back1_vector_decr(std::vector<int> &V, int n) {
+  auto i0 = V.cbegin(), i1 = V.cend(), i2 = i1--;
+  V.pop_back();
   --i2; // expected-warning{{Invalidated iterator accessed}}
 }
 
-void good_pop_back_deque1(std::deque<int> &D, int n) {
+void good_pop_back1_deque(std::deque<int> &D, int n) {
   auto i0 = D.cbegin(), i1 = D.cend(), i2 = i1--;
   D.pop_back();
   *i0; // no-warning
 }
 
-void bad_pop_back_deque1(std::deque<int> &D, int n) {
+void bad_pop_back1_deque(std::deque<int> &D, int n) {
   auto i0 = D.cbegin(), i1 = D.cend(), i2 = i1--;
   D.pop_back();
   *i1; // expected-warning{{Invalidated iterator accessed}}
+}
+
+void bad_pop_back1_deque_decr(std::deque<int> &D, int n) {
+  auto i0 = D.cbegin(), i1 = D.cend(), i2 = i1--;
+  D.pop_back();
   --i2; // expected-warning{{Invalidated iterator accessed}}
 }
 
-void good_push_front_list1(std::list<int> &L, int n) {
+void good_push_front1_list(std::list<int> &L, int n) {
   auto i0 = L.cbegin(), i1 = L.cend();
   L.push_front(n);
   *i0; // no-warning
   --i1; // no-warning
 }
 
-void bad_push_front_deque1(std::deque<int> &D, int n) {
+void bad_push_front1_deque(std::deque<int> &D, int n) {
   auto i0 = D.cbegin(), i1 = D.cend();
   D.push_front(n);
   *i0; // expected-warning{{Invalidated iterator accessed}}
+}
+
+void bad_push_front1_deque_decr(std::deque<int> &D, int n) {
+  auto i0 = D.cbegin(), i1 = D.cend();
+  D.push_front(n);
   --i1; // expected-warning{{Invalidated iterator accessed}}
 }
 
-void good_push_front_forward_list1(std::forward_list<int> &FL, int n) {
+void good_push_front1_forward_list(std::forward_list<int> &FL, int n) {
   auto i0 = FL.cbegin(), i1 = FL.cend();
   FL.push_front(n);
   *i0; // no-warning
 }
 
-void good_emplace_front_list1(std::list<int> &L, int n) {
+void good_emplace_front1_list(std::list<int> &L, int n) {
   auto i0 = L.cbegin(), i1 = L.cend();
   L.emplace_front(n);
   *i0; // no-warning
   --i1; // no-warning
 }
 
-void bad_emplace_front_deque1(std::deque<int> &D, int n) {
+void bad_emplace_front1_deque(std::deque<int> &D, int n) {
   auto i0 = D.cbegin(), i1 = D.cend();
   D.emplace_front(n);
   *i0; // expected-warning{{Invalidated iterator accessed}}
+}
+
+void bad_emplace_front1_deque_decr(std::deque<int> &D, int n) {
+  auto i0 = D.cbegin(), i1 = D.cend();
+  D.emplace_front(n);
   --i1; // expected-warning{{Invalidated iterator accessed}}
 }
 
-void good_emplace_front_forward_list1(std::forward_list<int> &FL, int n) {
+void good_emplace_front1_forward_list(std::forward_list<int> &FL, int n) {
   auto i0 = FL.cbegin(), i1 = FL.cend();
   FL.emplace_front(n);
   *i0; // no-warning
 }
 
-void good_pop_front_list1(std::list<int> &L, int n) {
+void good_pop_front1_list(std::list<int> &L, int n) {
   auto i1 = L.cbegin(), i0 = i1++;
   L.pop_front();
   *i1; // no-warning
 }
 
-void bad_pop_front_list1(std::list<int> &L, int n) {
+void bad_pop_front1_list(std::list<int> &L, int n) {
   auto i1 = L.cbegin(), i0 = i1++;
   L.pop_front();
   *i0; // expected-warning{{Invalidated iterator accessed}}
 }
 
-void good_pop_front_deque1(std::deque<int> &D, int n) {
+void good_pop_front1_deque(std::deque<int> &D, int n) {
   auto i1 = D.cbegin(), i0 = i1++;
   D.pop_front();
   *i1; // no-warning
 }
 
-void bad_pop_front_deque1(std::deque<int> &D, int n) {
+void bad_pop_front1_deque(std::deque<int> &D, int n) {
   auto i1 = D.cbegin(), i0 = i1++;
   D.pop_front();
   *i0; // expected-warning{{Invalidated iterator accessed}}
 }
 
-void good_pop_front_forward_list1(std::forward_list<int> &FL, int n) {
+void good_pop_front1_forward_list(std::forward_list<int> &FL, int n) {
   auto i1 = FL.cbegin(), i0 = i1++;
   FL.pop_front();
   *i1; // no-warning
 }
 
-void bad_pop_front_forward_list1(std::forward_list<int> &FL, int n) {
+void bad_pop_front1_forward_list(std::forward_list<int> &FL, int n) {
   auto i1 = FL.cbegin(), i0 = i1++;
   FL.pop_front();
   *i0; // expected-warning{{Invalidated iterator accessed}}
 }
 
-void good_insert_list1(std::list<int> &L, int n) {
+void good_insert1_list1(std::list<int> &L, int n) {
   auto i1 = L.cbegin(), i0 = i1++;
   L.insert(i1, n);
   *i0; // no-warning
   *i1; // no-warning
 }
 
-void good_insert_vector1(std::vector<int> &V, int n) {
+void good_insert1_list2(std::list<int> &L, int n) {
+  auto i1 = L.cbegin(), i0 = i1++;
+  i1 = L.insert(i1, n);
+  *i1; // no-warning
+}
+
+void good_insert1_vector1(std::vector<int> &V, int n) {
   auto i1 = V.cbegin(), i0 = i1++;
   V.insert(i1, n);
   *i0; // no-warning
 }
 
-void bad_insert_vector1(std::vector<int> &V, int n) {
+void good_insert1_vector2(std::vector<int> &V, int n) {
+  auto i1 = V.cbegin(), i0 = i1++;
+  i1 = V.insert(i1, n);
+  *i1; // no-warning
+}
+
+void bad_insert1_vector(std::vector<int> &V, int n) {
   auto i1 = V.cbegin(), i0 = i1++;
   V.insert(i1, n);
   *i1; // expected-warning{{Invalidated iterator accessed}}
 }
 
-void bad_insert_deque1(std::deque<int> &D, int n) {
+void good_insert1_deque(std::deque<int> &D, int n) {
+  auto i1 = D.cbegin(), i0 = i1++;
+  i0 = D.insert(i1, n);
+  *i0; // no-warning
+}
+
+void bad_insert1_deque1(std::deque<int> &D, int n) {
   auto i1 = D.cbegin(), i0 = i1++;
   D.insert(i1, n);
   *i0; // expected-warning{{Invalidated iterator accessed}}
+}
+
+void bad_insert1_deque2(std::deque<int> &D, int n) {
+  auto i1 = D.cbegin(), i0 = i1++;
+  D.insert(i1, n);
   *i1; // expected-warning{{Invalidated iterator accessed}}
 }
 
-void good_emplace_list1(std::list<int> &L, int n) {
+void good_insert2_list1(std::list<int> &L, int n) {
+  auto i1 = L.cbegin(), i0 = i1++;
+  L.insert(i1, std::move(n));
+  *i0; // no-warning
+  *i1; // no-warning
+}
+
+void good_insert2_list2(std::list<int> &L, int n) {
+  auto i1 = L.cbegin(), i0 = i1++;
+  i1 = L.insert(i1, std::move(n));
+  *i1; // no-warning
+}
+
+void good_insert2_vector1(std::vector<int> &V, int n) {
+  auto i1 = V.cbegin(), i0 = i1++;
+  V.insert(i1, std::move(n));
+  *i0; // no-warning
+}
+
+void good_insert2_vector2(std::vector<int> &V, int n) {
+  auto i1 = V.cbegin(), i0 = i1++;
+  i1 = V.insert(i1, std::move(n));
+  *i1; // no-warning
+}
+
+void bad_insert2_vector(std::vector<int> &V, int n) {
+  auto i1 = V.cbegin(), i0 = i1++;
+  V.insert(i1, std::move(n));
+  *i1; // expected-warning{{Invalidated iterator accessed}}
+}
+
+void good_insert2_deque(std::deque<int> &D, int n) {
+  auto i1 = D.cbegin(), i0 = i1++;
+  i1 = D.insert(i1, std::move(n));
+  *i1; // no-warning
+}
+
+void bad_insert2_deque1(std::deque<int> &D, int n) {
+  auto i1 = D.cbegin(), i0 = i1++;
+  D.insert(i1, std::move(n));
+  *i0; // expected-warning{{Invalidated iterator accessed}}
+}
+
+void bad_insert2_deque2(std::deque<int> &D, int n) {
+  auto i1 = D.cbegin(), i0 = i1++;
+  D.insert(i1, std::move(n));
+  *i1; // expected-warning{{Invalidated iterator accessed}}
+}
+
+void good_insert3_list1(std::list<int> &L, int n) {
+  auto i1 = L.cbegin(), i0 = i1++;
+  L.insert(i1, 10, n);
+  *i0; // no-warning
+  *i1; // no-warning
+}
+
+void good_insert3_list2(std::list<int> &L, int n) {
+  auto i1 = L.cbegin(), i0 = i1++;
+  i1 = L.insert(i1, 10, n);
+  *i1; // no-warning
+}
+
+void good_insert3_vector1(std::vector<int> &V, int n) {
+  auto i1 = V.cbegin(), i0 = i1++;
+  V.insert(i1, 10, n);
+  *i0; // no-warning
+}
+
+void good_insert3_vector2(std::vector<int> &V, int n) {
+  auto i1 = V.cbegin(), i0 = i1++;
+  i1 = V.insert(i1, 10, n);
+  *i1; // no-warning
+}
+
+void bad_insert3_vector(std::vector<int> &V, int n) {
+  auto i1 = V.cbegin(), i0 = i1++;
+  V.insert(i1, 10, n);
+  *i1; // expected-warning{{Invalidated iterator accessed}}
+}
+
+void good_insert3_deque(std::deque<int> &D, int n) {
+  auto i1 = D.cbegin(), i0 = i1++;
+  i1 = D.insert(i1, 10, std::move(n));
+  *i1; // no-warning
+}
+
+void bad_insert3_deque1(std::deque<int> &D, int n) {
+  auto i1 = D.cbegin(), i0 = i1++;
+  D.insert(i1, 10, std::move(n));
+  *i0; // expected-warning{{Invalidated iterator accessed}}
+}
+
+void bad_insert3_deque2(std::deque<int> &D, int n) {
+  auto i1 = D.cbegin(), i0 = i1++;
+  D.insert(i1, 10, std::move(n));
+  *i1; // expected-warning{{Invalidated iterator accessed}}
+}
+
+void good_insert4_list1(std::list<int> &L1, std::list<int> &L2, int n) {
+  auto i1 = L1.cbegin(), i0 = i1++;
+  L1.insert(i1, L2.cbegin(), L2.cend());
+  *i0; // no-warning
+  *i1; // no-warning
+}
+
+void good_insert4_list2(std::list<int> &L1, std::list<int> &L2, int n) {
+  auto i1 = L1.cbegin(), i0 = i1++;
+  i1 = L1.insert(i1, L2.cbegin(), L2.cend());
+  *i1; // no-warning
+}
+
+void good_insert4_vector1(std::vector<int> &V1, std::vector<int> &V2, int n) {
+  auto i1 = V1.cbegin(), i0 = i1++;
+  V1.insert(i1, V2.cbegin(), V2.cend());
+  *i0; // no-warning
+}
+
+void good_insert4_vector2(std::vector<int> &V1, std::vector<int> &V2, int n) {
+  auto i1 = V1.cbegin(), i0 = i1++;
+  i1 = V1.insert(i1, V2.cbegin(), V2.cend());
+  *i1; // no-warning
+}
+
+void bad_insert4_vector(std::vector<int> &V1, std::vector<int> &V2, int n) {
+  auto i1 = V1.cbegin(), i0 = i1++;
+  V1.insert(i1, V2.cbegin(), V2.cend());
+  *i1; // expected-warning{{Invalidated iterator accessed}}
+}
+
+void good_insert4_deque(std::deque<int> &D1, std::deque<int> &D2, int n) {
+  auto i1 = D1.cbegin(), i0 = i1++;
+  i1 = D1.insert(i1, D2.cbegin(), D2.cend());
+  *i1; // no-warning
+}
+
+void bad_insert4_deque1(std::deque<int> &D1, std::deque<int> &D2, int n) {
+  auto i1 = D1.cbegin(), i0 = i1++;
+  D1.insert(i1, D2.cbegin(), D2.cend());
+  *i0; // expected-warning{{Invalidated iterator accessed}}
+}
+
+void bad_insert4_deque2(std::deque<int> &D1, std::deque<int> &D2, int n) {
+  auto i1 = D1.cbegin(), i0 = i1++;
+  D1.insert(i1, D2.cbegin(), D2.cend());
+  *i1; // expected-warning{{Invalidated iterator accessed}}
+}
+
+void good_insert5_list1(std::list<int> &L) {
+  auto i1 = L.cbegin(), i0 = i1++;
+  L.insert(i1, {1, 2, 3, 4});
+  *i0; // no-warning
+  *i1; // no-warning
+}
+
+void good_insert5_list2(std::list<int> &L) {
+  auto i1 = L.cbegin(), i0 = i1++;
+  i1 = L.insert(i1, {1, 2, 3, 4});
+  *i1; // no-warning
+}
+
+void good_insert5_vector1(std::vector<int> &V) {
+  auto i1 = V.cbegin(), i0 = i1++;
+  V.insert(i1, {1, 2, 3, 4});
+  *i0; // no-warning
+}
+
+void good_insert5_vector2(std::vector<int> &V) {
+  auto i1 = V.cbegin(), i0 = i1++;
+  i1 = V.insert(i1, {1, 2, 3, 4});
+  *i1; // no-warning
+}
+
+void bad_insert5_vector(std::vector<int> &V) {
+  auto i1 = V.cbegin(), i0 = i1++;
+  V.insert(i1, {1, 2, 3, 4});
+  *i1; // expected-warning{{Invalidated iterator accessed}}
+}
+
+void good_insert5_deque(std::deque<int> &D) {
+  auto i1 = D.cbegin(), i0 = i1++;
+  i1 = D.insert(i1, {1, 2, 3, 4});
+  *i1; // no-warning
+}
+
+void bad_insert5_deque1(std::deque<int> &D) {
+  auto i1 = D.cbegin(), i0 = i1++;
+  D.insert(i1, {1, 2, 3, 4});
+  *i0; // expected-warning{{Invalidated iterator accessed}}
+}
+
+void bad_insert5_deque2(std::deque<int> &D) {
+  auto i1 = D.cbegin(), i0 = i1++;
+  D.insert(i1, {1, 2, 3, 4});
+  *i1; // expected-warning{{Invalidated iterator accessed}}
+}
+
+void good_emplace1_list(std::list<int> &L, int n) {
   auto i1 = L.cbegin(), i0 = i1++;
   L.emplace(i1, n);
   *i0; // no-warning
   *i1; // no-warning
 }
 
-void good_emplace_vector1(std::vector<int> &V, int n) {
+void good_emplace1_vector(std::vector<int> &V, int n) {
   auto i1 = V.cbegin(), i0 = i1++;
   V.emplace(i1, n);
   *i0; // no-warning
 }
 
-void bad_emplace_vector1(std::vector<int> &V, int n) {
+void bad_emplace1_vector(std::vector<int> &V, int n) {
   auto i1 = V.cbegin(), i0 = i1++;
   V.emplace(i1, n);
   *i1; // expected-warning{{Invalidated iterator accessed}}
 }
 
-void bad_emplace_deque1(std::deque<int> &D, int n) {
+void bad_emplace1_deque1(std::deque<int> &D, int n) {
   auto i1 = D.cbegin(), i0 = i1++;
   D.emplace(i1, n);
   *i0; // expected-warning{{Invalidated iterator accessed}}
+}
+
+void bad_emplace1_deque2(std::deque<int> &D, int n) {
+  auto i1 = D.cbegin(), i0 = i1++;
+  D.emplace(i1, n);
   *i1; // expected-warning{{Invalidated iterator accessed}}
 }
 
-void good_erase_list1(std::list<int> &L) {
+void good_erase1_list1(std::list<int> &L) {
   auto i2 = L.cbegin(), i0 = i2++, i1 = i2++;
   L.erase(i1);
   *i0; // no-warning
   *i2; // no-warning
 }
 
-void bad_erase_list1(std::list<int> &L) {
+void good_erase1_list2(std::list<int> &L) {
+  auto i0 = L.cbegin();
+  i0 = L.erase(i0);
+  *i0; // no-warning
+}
+
+void bad_erase1_list(std::list<int> &L) {
   auto i0 = L.cbegin();
   L.erase(i0);
   *i0; // expected-warning{{Invalidated iterator accessed}}
 }
 
-void good_erase_vector1(std::vector<int> &V) {
+void good_erase1_vector1(std::vector<int> &V) {
   auto i2 = V.cbegin(), i0 = i2++, i1 = i2++;
   V.erase(i1);
   *i0; // no-warning
 }
 
-void bad_erase_vector1(std::vector<int> &V) {
+void good_erase1_vector2(std::vector<int> &V) {
+  auto i0 = V.cbegin();
+  i0 = V.erase(i0);
+  *i0; // no-warning
+}
+
+void bad_erase1_vector1(std::vector<int> &V) {
   auto i1 = V.cbegin(), i0 = i1++;
   V.erase(i0);
   *i0; // expected-warning{{Invalidated iterator accessed}}
+}
+
+void bad_erase1_vector2(std::vector<int> &V) {
+  auto i1 = V.cbegin(), i0 = i1++;
+  V.erase(i0);
   *i1; // expected-warning{{Invalidated iterator accessed}}
 }
 
-void bad_erase_deque1(std::deque<int> &D) {
+void good_erase1_deque(std::deque<int> &D) {
+  auto i0 = D.cbegin();
+  i0 = D.erase(i0);
+  *i0; // no-warning
+}
+
+void bad_erase1_deque1(std::deque<int> &D) {
   auto i2 = D.cbegin(), i0 = i2++, i1 = i2++;
   D.erase(i1);
   *i0; // expected-warning{{Invalidated iterator accessed}}
+}
+
+void bad_erase1_deque2(std::deque<int> &D) {
+  auto i2 = D.cbegin(), i0 = i2++, i1 = i2++;
+  D.erase(i1);
   *i1; // expected-warning{{Invalidated iterator accessed}}
+}
+
+void bad_erase1_deque3(std::deque<int> &D) {
+  auto i2 = D.cbegin(), i0 = i2++, i1 = i2++;
+  D.erase(i1);
   *i2; // expected-warning{{Invalidated iterator accessed}}
 }
 
-void good_erase_list2(std::list<int> &L) {
+void good_erase2_list1(std::list<int> &L) {
   auto i3 = L.cbegin(), i0 = i3++, i1 = i3++, i2 = i3++;
   L.erase(i1, i3);
   *i0; // no-warning
   *i3; // no-warning
 }
 
-void bad_erase_list2(std::list<int> &L) {
+void good_erase2_list2(std::list<int> &L) {
+  auto i2 = L.cbegin(), i0 = i2++, i1 = i2++;
+  i0 = L.erase(i0, i2);
+  *i0; // no-warning
+}
+
+void bad_erase2_list1(std::list<int> &L) {
   auto i2 = L.cbegin(), i0 = i2++, i1 = i2++;
   L.erase(i0, i2);
   *i0; // expected-warning{{Invalidated iterator accessed}}
+}
+
+void bad_erase2_list2(std::list<int> &L) {
+  auto i2 = L.cbegin(), i0 = i2++, i1 = i2++;
+  L.erase(i0, i2);
   *i1; // expected-warning{{Invalidated iterator accessed}}
 }
 
-void good_erase_vector2(std::vector<int> &V) {
+void good_erase2_vector1(std::vector<int> &V) {
   auto i3 = V.cbegin(), i0 = i3++, i1 = i3++, i2 = i3++;;
   V.erase(i1, i3);
   *i0; // no-warning
 }
 
-void bad_erase_vector2(std::vector<int> &V) {
+void good_erase2_vector2(std::vector<int> &V) {
+  auto i2 = V.cbegin(), i0 = i2++, i1 = i2++;
+  i0 = V.erase(i0, i2);
+  *i0; // no-warning
+}
+
+void bad_erase2_vector1(std::vector<int> &V) {
   auto i2 = V.cbegin(), i0 = i2++, i1 = i2++;
   V.erase(i0, i2);
   *i0; // expected-warning{{Invalidated iterator accessed}}
+}
+
+void bad_erase2_vector2(std::vector<int> &V) {
+  auto i2 = V.cbegin(), i0 = i2++, i1 = i2++;
+  V.erase(i0, i2);
   *i1; // expected-warning{{Invalidated iterator accessed}}
+}
+
+void bad_erase2_vector3(std::vector<int> &V) {
+  auto i2 = V.cbegin(), i0 = i2++, i1 = i2++;
+  V.erase(i0, i2);
   *i2; // expected-warning{{Invalidated iterator accessed}}
 }
 
-void bad_erase_deque2(std::deque<int> &D) {
+void good_erase2_deque(std::deque<int> &D) {
+  auto i2 = D.cbegin(), i0 = i2++, i1 = i2++;
+  i0 = D.erase(i0, i2);
+  *i0; // no-warning
+}
+
+void bad_erase2_deque1(std::deque<int> &D) {
   auto i3 = D.cbegin(), i0 = i3++, i1 = i3++, i2 = i3++;
   D.erase(i1, i3);
   *i0; // expected-warning{{Invalidated iterator accessed}}
+}
+
+void bad_erase2_deque2(std::deque<int> &D) {
+  auto i3 = D.cbegin(), i0 = i3++, i1 = i3++, i2 = i3++;
+  D.erase(i1, i3);
   *i1; // expected-warning{{Invalidated iterator accessed}}
+}
+
+void bad_erase2_deque3(std::deque<int> &D) {
+  auto i3 = D.cbegin(), i0 = i3++, i1 = i3++, i2 = i3++;
+  D.erase(i1, i3);
   *i2; // expected-warning{{Invalidated iterator accessed}}
+}
+
+void bad_erase2_deque4(std::deque<int> &D) {
+  auto i3 = D.cbegin(), i0 = i3++, i1 = i3++, i2 = i3++;
+  D.erase(i1, i3);
   *i3; // expected-warning{{Invalidated iterator accessed}}
 }
 
-void good_erase_after_forward_list1(std::forward_list<int> &FL) {
+void good_erase_after1_forward_list1(std::forward_list<int> &FL) {
   auto i2 = FL.cbegin(), i0 = i2++, i1 = i2++;
   FL.erase_after(i0);
   *i0; // no-warning
   *i2; // no-warning
 }
 
-void bad_erase_after_forward_list1(std::forward_list<int> &FL) {
+void good_erase_after1_forward_lis2(std::forward_list<int> &FL) {
+  auto i1 = FL.cbegin(), i0 = i1++;
+  i1 = FL.erase_after(i0);
+  *i1; // no-warning
+}
+
+void bad_erase_after1_forward_list(std::forward_list<int> &FL) {
   auto i1 = FL.cbegin(), i0 = i1++;
   FL.erase_after(i0);
   *i1; // expected-warning{{Invalidated iterator accessed}}
 }
 
-void good_erase_after_forward_list2(std::forward_list<int> &FL) {
+void good_erase_after2_forward_list1(std::forward_list<int> &FL) {
   auto i3 = FL.cbegin(), i0 = i3++, i1 = i3++, i2 = i3++;
   FL.erase_after(i0, i3);
   *i0; // no-warning
   *i3; // no-warning
 }
 
-void bad_erase_after_forward_list2(std::forward_list<int> &FL) {
+void good_erase_after2_forward_list2(std::forward_list<int> &FL) {
+  auto i3 = FL.cbegin(), i0 = i3++, i1 = i3++, i2 = i3++;
+  i2 = FL.erase_after(i0, i3);
+  *i2; // no-warning
+}
+
+void bad_erase_after2_forward_list1(std::forward_list<int> &FL) {
   auto i3 = FL.cbegin(), i0 = i3++, i1 = i3++, i2 = i3++;
   FL.erase_after(i0, i3);
   *i1; // expected-warning{{Invalidated iterator accessed}}
+}
+
+void bad_erase_after2_forward_list2(std::forward_list<int> &FL) {
+  auto i3 = FL.cbegin(), i0 = i3++, i1 = i3++, i2 = i3++;
+  FL.erase_after(i0, i3);
   *i2; // expected-warning{{Invalidated iterator accessed}}
 }

cfe/trunk/test/Analysis/iterator-range.cpp

if (!(i == v.end())) {
     clang_analyzer_warnIfReached();
     *i; // no-warning
   }
 }
 
 void simple_bad_end(const std::vector<int> &v) {
   auto i = v.end();
   *i; // expected-warning{{Past-the-end iterator dereferenced}}
+  clang_analyzer_warnIfReached();
 }
 
 void copy(const std::vector<int> &v) {
   auto i1 = v.end();
   auto i2 = i1;
   *i2; // expected-warning{{Past-the-end iterator dereferenced}}
 }