[Analyzer] Iterator Checker - Forbid decrements past the begin() and increments past the end() of containers

[baloghadamsoftware]

Summary

Previously, the iterator range checker only warned upon dereferencing of iterators outside their valid range as well as increments and decrements of out-of-range iterators where the result remains out-of-range. However, the C++ standard is more strict than this: decrementing begin() or incrementing end() results in undefined behaviour even if the iterator is not dereferenced afterwards. Coming back to the range once out-of-range is also undefined.

This patch corrects the behaviour of the iterator range checker: warnings are given for any operation whose result is ahead of begin() or past the end() (which is the past-end iterator itself, thus now we are speaking of past past-end).

[whisperity]

lib/StaticAnalyzer/Checkers/IteratorChecker.cpp

421–470

This is a bit of an organisational comment (and the compiler of course hopefully optimises this out), but could you, for the sake of code readability, break the if-elseif-elseif-elseif chain's common check out into an outer if, and only check for the inner parts? Thinking of something like this:

if (ChecksEnabled[CK_InvalidatedIteratorChecker])
{
   /* yadda */
}

if (ChecksEnabled[CK_IteratorRangeChecker])
{
  X* OOperator = Func->getOverloadedOperator();
  if (isIncrementOperator(OOperator))
  {
    /* yadda */
  } else if (isDecrementOperator(OOperator)) {
    /* yadda */
  }
}

/* etc. */

1075–1076

is never a, also . at the end

1555

(Minor: I don't like the name of this function, advancePosition (akin to std::advance) sounds cleaner to my ears.)

1562

For the sake of clarity, I think an assert should be introduced her, lest someone ends up shifting the position with <=.

2322–2337

How does the introduction of IncludeEnd change this behaviour? What does the parameter refer to?

[baloghadamsoftware]

This comment was removed by baloghadamsoftware.

[baloghadamsoftware]

Restored corrected patch after uploading an incorrect one.

[baloghadamsoftware]

Updated according to the comments.

[NoQ]

Makes perfect sense to me!

test/Analysis/iterator-range.cpp

210

I guess we'll have to come up with a separate warning text for this case, as there's no access happening through the iterator.

Regardless of how the final message would look, i suggest adding logic for having a different message now, so that we didn't forget about this case later.

[baloghadamsoftware]

Thank you for the review!

You are absolutely right, these error messages were not accurate and even misleading. Now I updated them. To achieve this I also had to separate the function isOutOfRange() into three different functions.

[baloghadamsoftware]

One error message slightly updated.

lib/StaticAnalyzer/Checkers/IteratorChecker.cpp

class IteratorChecker
   void handlePopFront(CheckerContext &C, const SVal &Cont) const;
   void handleInsert(CheckerContext &C, const SVal &Iter) const;
   void handleErase(CheckerContext &C, const SVal &Iter) const;
   void handleErase(CheckerContext &C, const SVal &Iter1,
                    const SVal &Iter2) const;
   void handleEraseAfter(CheckerContext &C, const SVal &Iter) const;
   void handleEraseAfter(CheckerContext &C, const SVal &Iter1,
                         const SVal &Iter2) const;
+  void verifyIncrement(CheckerContext &C, const SVal &Iter) const;
+  void verifyDecrement(CheckerContext &C, const SVal &Iter) const;
   void verifyRandomIncrOrDecr(CheckerContext &C, OverloadedOperatorKind Op,
-                              const SVal &RetVal, const SVal &LHS,
-                              const SVal &RHS) const;
+                              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;
-
+  IteratorPosition advancePosition(CheckerContext &C, OverloadedOperatorKind Op,
+                                   const IteratorPosition &Pos,
+                                   const SVal &Distance) 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;
ProgramStateRef rebaseSymbolInIteratorPositionsIf(
     SymbolRef NewSym, SymbolRef CondSym, BinaryOperator::Opcode Opc);
 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 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"));
   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
   // iterator mismatches
   const auto *Func = dyn_cast_or_null<FunctionDecl>(Call.getDecl());
   if (!Func)
     return;
 
   if (Func->isOverloadedOperator()) {
     if (ChecksEnabled[CK_InvalidatedIteratorChecker] &&
         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());
       } else {
         verifyAccess(C, Call.getArgSVal(0));
       }
     }
-    if (ChecksEnabled[CK_IteratorRangeChecker] &&
-        isRandomIncrOrDecrOperator(Func->getOverloadedOperator())) {
+    if (ChecksEnabled[CK_IteratorRangeChecker]) {
+      if (isIncrementOperator(Func->getOverloadedOperator())) {
+        // Check for out-of-range incrementions
+        if (const auto *InstCall = dyn_cast<CXXInstanceCall>(&Call)) {
+          verifyIncrement(C, InstCall->getCXXThisVal());
+        } else {
+          if (Call.getNumArgs() >= 1) {
+            verifyIncrement(C, Call.getArgSVal(0));
+          }
+        }
+      } else if (isDecrementOperator(Func->getOverloadedOperator())) {
+        // Check for out-of-range decrementions
+        if (const auto *InstCall = dyn_cast<CXXInstanceCall>(&Call)) {
+          verifyDecrement(C, InstCall->getCXXThisVal());
+        } else {
+          if (Call.getNumArgs() >= 1) {
+            verifyDecrement(C, Call.getArgSVal(0));
+          }
+        }
+      } else if (isRandomIncrOrDecrOperator(Func->getOverloadedOperator())) {
         if (const auto *InstCall = dyn_cast<CXXInstanceCall>(&Call)) {
           // Check for out-of-range incrementions and decrementions
           if (Call.getNumArgs() >= 1) {
             verifyRandomIncrOrDecr(C, Func->getOverloadedOperator(),
-                                 Call.getReturnValue(),
-                                 InstCall->getCXXThisVal(), Call.getArgSVal(0));
+                                   InstCall->getCXXThisVal(),
+                                   Call.getArgSVal(0));
           }
         } else {
           if (Call.getNumArgs() >= 2) {
             verifyRandomIncrOrDecr(C, Func->getOverloadedOperator(),
-                                 Call.getReturnValue(), Call.getArgSVal(0),
-                                 Call.getArgSVal(1));
+                                   Call.getArgSVal(0), Call.getArgSVal(1));
           }
         }
-    } else if (ChecksEnabled[CK_IteratorRangeChecker] &&
-               isDereferenceOperator(Func->getOverloadedOperator())) {
+      } else if (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()) ||
if (const auto *Condition = RetVal.getAsSymbolicExpression()) {
     }
   }
 }
 
 void IteratorChecker::verifyDereference(CheckerContext &C,
                                         const SVal &Val) const {
   auto State = C.getState();
   const auto *Pos = getIteratorPosition(State, Val);
-  if (Pos && isOutOfRange(State, *Pos)) {
+  if (Pos && isPastTheEnd(State, *Pos)) {
     auto *N = C.generateNonFatalErrorNode(State);
     if (!N)
       return;
-    reportOutOfRangeBug("Iterator accessed outside of its range.", Val, C, N);
+    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);
     if (!N) {
       return;
     }
     reportInvalidatedBug("Invalidated iterator accessed.", Val, C, N);
   }
 }
 
 void IteratorChecker::handleIncrement(CheckerContext &C, const SVal &RetVal,
                                       const SVal &Iter, bool Postfix) const {
   // Increment the symbolic expressions which represents the position of the
   // iterator
   auto State = C.getState();
   const auto *Pos = getIteratorPosition(State, Iter);
   if (Pos) {
     auto &SymMgr = C.getSymbolManager();
     auto &BVF = SymMgr.getBasicVals();
-    auto &SVB = C.getSValBuilder();
-    const auto OldOffset = Pos->getOffset();
-    auto NewOffset =
-      SVB.evalBinOp(State, BO_Add,
-                    nonloc::SymbolVal(OldOffset),
-                    nonloc::ConcreteInt(BVF.getValue(llvm::APSInt::get(1))),
-                    SymMgr.getType(OldOffset)).getAsSymbol();
-    auto NewPos = Pos->setTo(NewOffset);
+    const auto NewPos =
+      advancePosition(C, OO_Plus, *Pos,
+                    nonloc::ConcreteInt(BVF.getValue(llvm::APSInt::get(1))));
     State = setIteratorPosition(State, Iter, NewPos);
     State = setIteratorPosition(State, RetVal, Postfix ? *Pos : NewPos);
     C.addTransition(State);
   }
 }
 
 void IteratorChecker::handleDecrement(CheckerContext &C, const SVal &RetVal,
                                       const SVal &Iter, bool Postfix) const {
   // Decrement the symbolic expressions which represents the position of the
   // iterator
   auto State = C.getState();
   const auto *Pos = getIteratorPosition(State, Iter);
   if (Pos) {
     auto &SymMgr = C.getSymbolManager();
     auto &BVF = SymMgr.getBasicVals();
-    auto &SVB = C.getSValBuilder();
-    const auto OldOffset = Pos->getOffset();
-    auto NewOffset =
-      SVB.evalBinOp(State, BO_Sub,
-                    nonloc::SymbolVal(OldOffset),
-                    nonloc::ConcreteInt(BVF.getValue(llvm::APSInt::get(1))),
-                    SymMgr.getType(OldOffset)).getAsSymbol();
-    auto NewPos = Pos->setTo(NewOffset);
+    const auto NewPos =
+      advancePosition(C, OO_Minus, *Pos,
+                    nonloc::ConcreteInt(BVF.getValue(llvm::APSInt::get(1))));
     State = setIteratorPosition(State, Iter, NewPos);
     State = setIteratorPosition(State, RetVal, Postfix ? *Pos : NewPos);
     C.addTransition(State);
   }
 }
 
 // This function tells the analyzer's engine that symbols produced by our
 // checker, most notably iterator positions, are relatively small.
if (!Pos)
     return;
 
   const auto *value = &RHS;
   if (auto loc = RHS.getAs<Loc>()) {
     const auto val = State->getRawSVal(*loc);
     value = &val;
   }
 
-  auto &SymMgr = C.getSymbolManager();
-  auto &SVB = C.getSValBuilder();
-  auto BinOp = (Op == OO_Plus || Op == OO_PlusEqual) ? BO_Add : BO_Sub;
-  const auto OldOffset = Pos->getOffset();
-  SymbolRef NewOffset;
-  if (const auto intValue = value->getAs<nonloc::ConcreteInt>()) {
-    // For concrete integers we can calculate the new position
-    NewOffset = SVB.evalBinOp(State, BinOp, nonloc::SymbolVal(OldOffset),
-                              *intValue,
-                              SymMgr.getType(OldOffset)).getAsSymbol();
-  } else {
-    // For other symbols create a new symbol to keep expressions simple
-    const auto &LCtx = C.getLocationContext();
-    NewOffset = SymMgr.conjureSymbol(nullptr, LCtx, SymMgr.getType(OldOffset),
-                                     C.blockCount());
-    State = assumeNoOverflow(State, NewOffset, 4);
-  }
-  auto NewPos = Pos->setTo(NewOffset);
   auto &TgtVal = (Op == OO_PlusEqual || Op == OO_MinusEqual) ? LHS : RetVal;
-  State = setIteratorPosition(State, TgtVal, NewPos);
+  State =
+      setIteratorPosition(State, TgtVal, advancePosition(C, Op, *Pos, *value));
   C.addTransition(State);
 }
 
+void IteratorChecker::verifyIncrement(CheckerContext &C,
+                                      const SVal &Iter) const {
+  auto &BVF = C.getSValBuilder().getBasicValueFactory();
+  verifyRandomIncrOrDecr(C, OO_Plus, Iter,
+                     nonloc::ConcreteInt(BVF.getValue(llvm::APSInt::get(1))));
+}
+
+void IteratorChecker::verifyDecrement(CheckerContext &C,
+                                      const SVal &Iter) const {
+  auto &BVF = C.getSValBuilder().getBasicValueFactory();
+  verifyRandomIncrOrDecr(C, OO_Minus, Iter,
+                     nonloc::ConcreteInt(BVF.getValue(llvm::APSInt::get(1))));
+}
+
 void IteratorChecker::verifyRandomIncrOrDecr(CheckerContext &C,
                                              OverloadedOperatorKind Op,
-                                             const SVal &RetVal,
                                              const SVal &LHS,
                                              const SVal &RHS) const {
   auto State = C.getState();
 
   // If the iterator is initially inside its range, then the operation is valid
   const auto *Pos = getIteratorPosition(State, LHS);
-  if (!Pos || !isOutOfRange(State, *Pos))
+  if (!Pos)
     return;
 
-  auto value = RHS;
-  if (auto loc = RHS.getAs<Loc>()) {
-    value = State->getRawSVal(*loc);
+  auto Value = RHS;
+  if (auto ValAsLoc = RHS.getAs<Loc>()) {
+    Value = State->getRawSVal(*ValAsLoc);
   }
 
-  // Incremention or decremention by 0 is never bug
-  if (isZero(State, value.castAs<NonLoc>()))
+  if (Value.isUnknown())
     return;
 
-  auto &SymMgr = C.getSymbolManager();
-  auto &SVB = C.getSValBuilder();
-  auto BinOp = (Op == OO_Plus || Op == OO_PlusEqual) ? BO_Add : BO_Sub;
-  const auto OldOffset = Pos->getOffset();
-  const auto intValue = value.getAs<nonloc::ConcreteInt>();
-  if (!intValue)
+  // Incremention or decremention by 0 is never a bug.
+  if (isZero(State, Value.castAs<NonLoc>()))
     return;
 
-  auto NewOffset = SVB.evalBinOp(State, BinOp, nonloc::SymbolVal(OldOffset),
-                                 *intValue,
-                                 SymMgr.getType(OldOffset)).getAsSymbol();
-  auto NewPos = Pos->setTo(NewOffset);
-
-  // If out of range, the only valid operation is to step into the range
-  if (isOutOfRange(State, NewPos)) {
+  // 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);
+    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);
     if (!N)
       return;
-    reportOutOfRangeBug("Iterator accessed past its end.", LHS, C, N);
+    reportOutOfRangeBug("Iterator incremented behind the past-the-end "
+                        "iterator.", 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
   Cont = Cont->getMostDerivedObjectRegion();
 
if (!Pos1 || !Pos2)
     return;
 
   // Invalidate the deleted iterator position range (first..last)
   State = invalidateIteratorPositions(State, Pos1->getOffset(), BO_GT,
                                       Pos2->getOffset(), BO_LT);
   C.addTransition(State);
 }
 
+IteratorPosition IteratorChecker::advancePosition(CheckerContext &C,
+                                                  OverloadedOperatorKind Op,
+                                                  const IteratorPosition &Pos,
+                                                  const SVal &Distance) const {
+  auto State = C.getState();
+  auto &SymMgr = C.getSymbolManager();
+  auto &SVB = C.getSValBuilder();
+
+  assert ((Op == OO_Plus || Op == OO_PlusEqual ||
+           Op == OO_Minus || Op == OO_MinusEqual) &&
+          "Advance operator must be one of +, -, += and -=.");
+  auto BinOp = (Op == OO_Plus || Op == OO_PlusEqual) ? BO_Add : BO_Sub;
+  if (const auto IntDist = Distance.getAs<nonloc::ConcreteInt>()) {
+    // For concrete integers we can calculate the new position
+    return Pos.setTo(SVB.evalBinOp(State, BinOp,
+                                   nonloc::SymbolVal(Pos.getOffset()), *IntDist,
+                                   SymMgr.getType(Pos.getOffset()))
+                         .getAsSymbol());
+  } else {
+    // For other symbols create a new symbol to keep expressions simple
+    const auto &LCtx = C.getLocationContext();
+    const auto NewPosSym = SymMgr.conjureSymbol(nullptr, LCtx,
+                                             SymMgr.getType(Pos.getOffset()),
+                                             C.blockCount());
+    State = assumeNoOverflow(State, NewPosSym, 4);
+    return Pos.setTo(NewPosSym);
+  }
+}
+
 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::reportInvalidatedBug(const StringRef &Message,
   auto R = llvm::make_unique<BugReport>(*InvalidatedBugType, Message, ErrNode);
   R->markInteresting(Val);
   C.emitReport(std::move(R));
 }
 
 namespace {
 
 bool isLess(ProgramStateRef State, SymbolRef Sym1, SymbolRef Sym2);
-bool isGreaterOrEqual(ProgramStateRef State, SymbolRef Sym1, SymbolRef Sym2);
+bool isGreater(ProgramStateRef State, SymbolRef Sym1, SymbolRef Sym2);
+bool isEqual(ProgramStateRef State, SymbolRef Sym1, SymbolRef Sym2);
 bool compare(ProgramStateRef State, SymbolRef Sym1, SymbolRef Sym2,
              BinaryOperator::Opcode Opc);
 bool compare(ProgramStateRef State, NonLoc NL1, NonLoc NL2,
              BinaryOperator::Opcode Opc);
 const CXXRecordDecl *getCXXRecordDecl(ProgramStateRef State,
                                       const MemRegion *Reg);
 SymbolRef rebaseSymbol(ProgramStateRef State, SValBuilder &SVB, SymbolRef Expr,
                         SymbolRef OldSym, SymbolRef NewSym);

 
 bool isZero(ProgramStateRef State, const NonLoc &Val) {
   auto &BVF = State->getBasicVals();
   return compare(State, Val,
                  nonloc::ConcreteInt(BVF.getValue(llvm::APSInt::get(0))),
                  BO_EQ);
 }
 
-bool isOutOfRange(ProgramStateRef State, const IteratorPosition &Pos) {
+bool isPastTheEnd(ProgramStateRef State, const IteratorPosition &Pos) {
   const auto *Cont = Pos.getContainer();
   const auto *CData = getContainerData(State, Cont);
   if (!CData)
     return false;
 
-  // Out of range means less than the begin symbol or greater or equal to the
-  // end symbol.
+  const auto End = CData->getEnd();
+  if (End) {
+    if (isEqual(State, Pos.getOffset(), End)) {
+      return true;
+    }
+  }
+
+  return false;
+}
+
+bool isAheadOfRange(ProgramStateRef State, const IteratorPosition &Pos) {
+  const auto *Cont = Pos.getContainer();
+  const auto *CData = getContainerData(State, Cont);
+  if (!CData)
+    return false;
 
   const auto Beg = CData->getBegin();
   if (Beg) {
     if (isLess(State, Pos.getOffset(), Beg)) {
       return true;
     }
   }
 
+  return false;
+}
+
+bool isBehindPastTheEnd(ProgramStateRef State, const IteratorPosition &Pos) {
+  const auto *Cont = Pos.getContainer();
+  const auto *CData = getContainerData(State, Cont);
+  if (!CData)
+    return false;
+
   const auto End = CData->getEnd();
   if (End) {
-    if (isGreaterOrEqual(State, Pos.getOffset(), End)) {
+    if (isGreater(State, Pos.getOffset(), End)) {
       return true;
     }
   }
 
   return false;
 }
 
 bool isLess(ProgramStateRef State, SymbolRef Sym1, SymbolRef Sym2) {
   return compare(State, Sym1, Sym2, BO_LT);
 }
 
-bool isGreaterOrEqual(ProgramStateRef State, SymbolRef Sym1, SymbolRef Sym2) {
-  return compare(State, Sym1, Sym2, BO_GE);
+bool isGreater(ProgramStateRef State, SymbolRef Sym1, SymbolRef Sym2) {
+  return compare(State, Sym1, Sym2, BO_GT);
+}
+
+bool isEqual(ProgramStateRef State, SymbolRef Sym1, SymbolRef Sym2) {
+  return compare(State, Sym1, Sym2, BO_EQ);
 }
 
 bool compare(ProgramStateRef State, SymbolRef Sym1, SymbolRef Sym2,
              BinaryOperator::Opcode Opc) {
   return compare(State, nonloc::SymbolVal(Sym1), nonloc::SymbolVal(Sym2), Opc);
 }
 
 

test/Analysis/iterator-range.cpp

void simple_good_end_negated(const std::vector<int> &v) {
   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{{Iterator accessed outside of its range}}
-}
-
-void simple_good_begin(const std::vector<int> &v) {
-  auto i = v.begin();
-  if (i != v.begin()) {
-    clang_analyzer_warnIfReached();
-    *--i; // no-warning
-  }
-}
-
-void simple_good_begin_negated(const std::vector<int> &v) {
-  auto i = v.begin();
-  if (!(i == v.begin())) {
-    clang_analyzer_warnIfReached();
-    *--i; // no-warning
-  }
-}
-
-void simple_bad_begin(const std::vector<int> &v) {
-  auto i = v.begin();
-  *--i; // expected-warning{{Iterator accessed outside of its range}}
+  *i; // expected-warning{{Past-the-end iterator dereferenced}}
 }
 
 void copy(const std::vector<int> &v) {
   auto i1 = v.end();
   auto i2 = i1;
-  *i2; // expected-warning{{Iterator accessed outside of its range}}
+  *i2; // expected-warning{{Past-the-end iterator dereferenced}}
 }
 
 void decrease(const std::vector<int> &v) {
   auto i = v.end();
   --i;
   *i; // no-warning
 }
 
 void copy_and_decrease1(const std::vector<int> &v) {
   auto i1 = v.end();
   auto i2 = i1;
   --i1;
   *i1; // no-warning
 }
 
 void copy_and_decrease2(const std::vector<int> &v) {
   auto i1 = v.end();
   auto i2 = i1;
   --i1;
-  *i2; // expected-warning{{Iterator accessed outside of its range}}
+  *i2; // expected-warning{{Past-the-end iterator dereferenced}}
 }
 
 void copy_and_increase1(const std::vector<int> &v) {
   auto i1 = v.begin();
   auto i2 = i1;
   ++i1;
   if (i1 == v.end())
     *i2; // no-warning
 }
 
 void copy_and_increase2(const std::vector<int> &v) {
   auto i1 = v.begin();
   auto i2 = i1;
   ++i1;
   if (i2 == v.end())
-    *i2; // expected-warning{{Iterator accessed outside of its range}}
+    *i2; // expected-warning{{Past-the-end iterator dereferenced}}
 }
 
 void copy_and_increase3(const std::vector<int> &v) {
   auto i1 = v.begin();
   auto i2 = i1;
   ++i1;
   if (v.end() == i2)
-    *i2; // expected-warning{{Iterator accessed outside of its range}}
+    *i2; // expected-warning{{Past-the-end iterator dereferenced}}
 }
 
 template <class InputIterator, class T>
 InputIterator nonStdFind(InputIterator first, InputIterator last,
                          const T &val) {
   for (auto i = first; i != last; ++i) {
     if (*i == val) {
       return i;
     }
   }
   return last;
 }
 
 void good_non_std_find(std::vector<int> &V, int e) {
   auto first = nonStdFind(V.begin(), V.end(), e);
   if (V.end() != first)
     *first; // no-warning
 }
 
 void bad_non_std_find(std::vector<int> &V, int e) {
   auto first = nonStdFind(V.begin(), V.end(), e);
-  *first; // expected-warning{{Iterator accessed outside of its range}}
+  *first; // expected-warning{{Past-the-end iterator dereferenced}}
 }
 
 void tricky(std::vector<int> &V, int e) {
   const auto first = V.begin();
   const auto comp1 = (first != V.end()), comp2 = (first == V.end());
   if (comp1)
-    *first;
+    *first; // no-warning
 }
 
 void loop(std::vector<int> &V, int e) {
   auto start = V.begin();
   while (true) {
     auto item = std::find(start, V.end(), e);
     if (item == V.end())
       break;
     *item;          // no-warning
     start = ++item; // no-warning
   }
 }
 
 void good_push_back(std::list<int> &L, int n) {
   auto i0 = --L.cend();
   L.push_back(n);
   *++i0; // no-warning
 }
 
 void bad_push_back(std::list<int> &L, int n) {
   auto i0 = --L.cend();
   L.push_back(n);
   ++i0;
-  *++i0; // expected-warning{{Iterator accessed outside of its range}}
+  *++i0; // expected-warning{{Past-the-end iterator dereferenced}}
 }
 
 void good_pop_back(std::list<int> &L, int n) {
   auto i0 = --L.cend(); --i0;
   L.pop_back();
   *i0; // no-warning
 }
 
 void bad_pop_back(std::list<int> &L, int n) {
   auto i0 = --L.cend(); --i0;
   L.pop_back();
-  *++i0; // expected-warning{{Iterator accessed outside of its range}}
+  *++i0; // expected-warning{{Past-the-end iterator dereferenced}}
 }
 
 void good_push_front(std::list<int> &L, int n) {
   auto i0 = L.cbegin();
   L.push_front(n);
   *--i0; // no-warning
 }
 
 void bad_push_front(std::list<int> &L, int n) {
   auto i0 = L.cbegin();
   L.push_front(n);
   --i0;
-  *--i0; // expected-warning{{Iterator accessed outside of its range}}
+  --i0; // expected-warning{{Iterator decremented ahead of its valid range}}
 }
 
 void good_pop_front(std::list<int> &L, int n) {
   auto i0 = ++L.cbegin();
   L.pop_front();
   *i0; // no-warning
 }
 
 void bad_pop_front(std::list<int> &L, int n) {
   auto i0 = ++L.cbegin();
   L.pop_front();
-  *--i0; // expected-warning{{Iterator accessed outside of its range}}
+  --i0; // expected-warning{{Iterator decremented ahead of its valid range}}
 }
 
 void bad_move(std::list<int> &L1, std::list<int> &L2) {
   auto i0 = --L2.cend();
   L1 = std::move(L2);
-  *++i0; // expected-warning{{Iterator accessed outside of its range}}
+  *++i0; // expected-warning{{Past-the-end iterator dereferenced}}
 }
 
 void bad_move_push_back(std::list<int> &L1, std::list<int> &L2, int n) {
   auto i0 = --L2.cend();
   L2.push_back(n);
   L1 = std::move(L2);
   ++i0;
-  *++i0; // expected-warning{{Iterator accessed outside of its range}}
+  *++i0; // expected-warning{{Past-the-end iterator dereferenced}}
+}
+
+void good_incr_begin(const std::list<int> &L) {
+  auto i0 = L.begin();
+  ++i0; // no-warning
+}
+
+void bad_decr_begin(const std::list<int> &L) {
+  auto i0 = L.begin();
+  --i0;  // expected-warning{{Iterator decremented ahead of its valid range}}
+}
+
+void good_decr_end(const std::list<int> &L) {
+  auto i0 = L.end();
+  --i0; // no-warning
+}
+
+void bad_incr_end(const std::list<int> &L) {
+  auto i0 = L.end();
+  ++i0;  // expected-warning{{Iterator incremented behind the past-the-end iterator}}
 }
 
 struct simple_iterator_base {
   simple_iterator_base();
   simple_iterator_base(const simple_iterator_base& rhs);
   simple_iterator_base &operator=(const simple_iterator_base& rhs);
   virtual ~simple_iterator_base();
   bool friend operator==(const simple_iterator_base &lhs,
                          const simple_iterator_base &rhs);
   bool friend operator!=(const simple_iterator_base &lhs,
                          const simple_iterator_base &rhs);
 private:
   int *ptr;
 };
 
 struct simple_derived_iterator: public simple_iterator_base {
   int& operator*();
   int* operator->();