[Analyzer] Iterator Checker - Part 7: Support for push and pop operations

[baloghadamsoftware]

Summary

This patch adds support for the following operations in the iterator checkers: push_back, push_front, emplace_back, emplace_front, pop_back and pop_front. This affects iterator range checks (range is extended after push and emplace and reduced after pop operations) and invalidation checks (according to the standard).

[baloghadamsoftware]

Wrong diff.

[NoQ]

This looks clear to me.

lib/StaticAnalyzer/Checkers/IteratorChecker.cpp

1449–1464 ↗

(On Diff #97942)

Would getDynamicTypeInfo() be of any help?

[baloghadamsoftware]

Rebased to Part6. Also fixed a test failing now: it is not enough to mark the symbolic expressions as live, but if it is a SymIntExpr (it can be nothing else, except SymbolConjured), we also have to mark the left side of it (which is always SymbolConjured) as live. Using scanReachableSymbols() here would be too heavyweight.

[NoQ]

lib/StaticAnalyzer/Checkers/IteratorChecker.cpp

1477–1530 ↗

(On Diff #144330)

I guess we should think if we want to use CallDescription for these when D48027 lands.

[baloghadamsoftware]

Updated according to the comments and rebased.

[baloghadamsoftware]

lib/StaticAnalyzer/Checkers/IteratorChecker.cpp

1477–1530 ↗

(On Diff #144330)

Here we do not need the qualified name.

1449–1464 ↗

(On Diff #97942)

I changed the function to use getDynamicTypeInfo(), but now I had to include a ProgramStateRef parameter to the function and to all its callers so it did not become much more simple.

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

 // a constraint which we later retrieve when doing an actual comparison.
 
 #include "ClangSACheckers.h"
 #include "clang/AST/DeclTemplate.h"
 #include "clang/StaticAnalyzer/Core/BugReporter/BugType.h"
 #include "clang/StaticAnalyzer/Core/Checker.h"
 #include "clang/StaticAnalyzer/Core/PathSensitive/CallEvent.h"
 #include "clang/StaticAnalyzer/Core/PathSensitive/CheckerContext.h"
+#include "clang/StaticAnalyzer/Core/PathSensitive/DynamicTypeMap.h"
 
 #include <utility>
 
 using namespace clang;
 using namespace ento;
 
 namespace {
 
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 Expr *CE = nullptr,
                     const SVal &OldCont = UndefinedVal()) const;
+  void handlePushBack(CheckerContext &C, const SVal &Cont) const;
+  void handlePopBack(CheckerContext &C, const SVal &Cont) const;
+  void handlePushFront(CheckerContext &C, const SVal &Cont) const;
+  void handlePopFront(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;

 
 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 isPushBackCall(const FunctionDecl *Func);
+bool isEmplaceBackCall(const FunctionDecl *Func);
+bool isPopBackCall(const FunctionDecl *Func);
+bool isPushFrontCall(const FunctionDecl *Func);
+bool isEmplaceFrontCall(const FunctionDecl *Func);
+bool isPopFrontCall(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);
 bool isRandomIncrOrDecrOperator(OverloadedOperatorKind OK);
+bool hasSubscriptOperator(ProgramStateRef State, const MemRegion *Reg);
+bool frontModifiable(ProgramStateRef State, const MemRegion *Reg);
+bool backModifiable(ProgramStateRef State, const MemRegion *Reg);
 BinaryOperator::Opcode getOpcode(const SymExpr *SE);
 const RegionOrSymbol getRegionOrSymbol(const SVal &Val);
 const ProgramStateRef processComparison(ProgramStateRef State,
                                         RegionOrSymbol LVal,
                                         RegionOrSymbol RVal, bool Equal);
 const ProgramStateRef saveComparison(ProgramStateRef State,
                                      const SymExpr *Condition, const SVal &LVal,
                                      const SVal &RVal, bool Eq);
ProgramStateRef adjustIteratorPosition(ProgramStateRef State,
                                        RegionOrSymbol RegOrSym,
                                        const IteratorPosition &Pos, bool Equal);
 ProgramStateRef relateIteratorPositions(ProgramStateRef State,
                                         const IteratorPosition &Pos1,
                                         const IteratorPosition &Pos2,
                                         bool Equal);
 ProgramStateRef invalidateAllIteratorPositions(ProgramStateRef State,
                                                const MemRegion *Cont);
+ProgramStateRef invalidateIteratorPositions(ProgramStateRef State,
+                                            SymbolRef Offset,
+                                            BinaryOperator::Opcode Opc);
 ProgramStateRef reassignAllIteratorPositions(ProgramStateRef State,
                                              const MemRegion *Cont,
                                              const MemRegion *NewCont);
 ProgramStateRef reassignAllIteratorPositionsUnless(ProgramStateRef State,
                                                    const MemRegion *Cont,
                                                    const MemRegion *NewCont,
                                                    SymbolRef Offset,
                                                    BinaryOperator::Opcode Opc);
if (isAssignmentOperator(Op)) {
         handleDecrement(C, Call.getReturnValue(), InstCall->getCXXThisVal(),
                         Call.getNumArgs());
       } else {
         handleDecrement(C, Call.getReturnValue(), Call.getArgSVal(0),
                         Call.getNumArgs());
       }
     }
   } else {
+    if (const auto *InstCall = dyn_cast<CXXInstanceCall>(&Call)) {
+      if (isPushBackCall(Func) || isEmplaceBackCall(Func)) {
+        handlePushBack(C, InstCall->getCXXThisVal());
+      } else if (isPopBackCall(Func)) {
+        handlePopBack(C, InstCall->getCXXThisVal());
+      } else if (isPushFrontCall(Func) || isEmplaceFrontCall(Func)) {
+        handlePushFront(C, InstCall->getCXXThisVal());
+      } else if (isPopFrontCall(Func)) {
+        handlePopFront(C, InstCall->getCXXThisVal());
+      }
+    }
+
     const auto *OrigExpr = Call.getOriginExpr();
     if (!OrigExpr)
       return;
 
     if (!isIteratorType(Call.getResultType()))
       return;
 
     auto State = C.getState();
for (auto i = Offset->symbol_begin(); i != Offset->symbol_end(); ++i)
         SR.markLive(*i);
   }
 
   auto ContMap = State->get<ContainerMap>();
   for (const auto Cont : ContMap) {
     const auto CData = Cont.second;
     if (CData.getBegin()) {
       SR.markLive(CData.getBegin());
+      if(const auto *SIE = dyn_cast<SymIntExpr>(CData.getBegin()))
+        SR.markLive(SIE->getLHS());
     }
     if (CData.getEnd()) {
       SR.markLive(CData.getEnd());
+      if(const auto *SIE = dyn_cast<SymIntExpr>(CData.getEnd()))
+        SR.markLive(SIE->getLHS());
     }
   }
 }
 
 void IteratorChecker::checkDeadSymbols(SymbolReaper &SR,
                                        CheckerContext &C) const {
   // Cleanup
   auto State = C.getState();
if (OldContReg) {
         // container, so reassign all iterator positions to the new container.
         State = reassignAllIteratorPositions(State, OldContReg, ContReg);
       }
     }
   }
   C.addTransition(State);
 }
 
+void IteratorChecker::handlePushBack(CheckerContext &C,
+                                     const SVal &Cont) const {
+  const auto *ContReg = Cont.getAsRegion();
+  if (!ContReg)
+    return;
+
+  while (const auto *CBOR = ContReg->getAs<CXXBaseObjectRegion>()) {
+    ContReg = CBOR->getSuperRegion();
+  }
+
+  // For deque-like containers invalidate all iterator positions
+  auto State = C.getState();
+  if (hasSubscriptOperator(State, ContReg) && frontModifiable(State, ContReg)) {
+    State = invalidateAllIteratorPositions(State, ContReg);
+    C.addTransition(State);
+    return;
+  }
+
+  const auto CData = getContainerData(State, ContReg);
+  if (!CData)
+    return;
+
+  // For vector-like containers invalidate the past-end iterator positions
+  if (const auto EndSym = CData->getEnd()) {
+    if (hasSubscriptOperator(State, ContReg)) {
+      State = invalidateIteratorPositions(State, EndSym, BO_GE);
+    }
+    auto &SymMgr = C.getSymbolManager();
+    auto &BVF = SymMgr.getBasicVals();
+    auto &SVB = C.getSValBuilder();
+    const auto newEndSym =
+      SVB.evalBinOp(State, BO_Add,
+                    nonloc::SymbolVal(EndSym),
+                    nonloc::ConcreteInt(BVF.getValue(llvm::APSInt::get(1))),
+                    SymMgr.getType(EndSym)).getAsSymbol();
+    State = setContainerData(State, ContReg, CData->newEnd(newEndSym));
+  }
+  C.addTransition(State);
+}
+
+void IteratorChecker::handlePopBack(CheckerContext &C, const SVal &Cont) const {
+  const auto *ContReg = Cont.getAsRegion();
+  if (!ContReg)
+    return;
+
+  while (const auto *CBOR = ContReg->getAs<CXXBaseObjectRegion>()) {
+    ContReg = CBOR->getSuperRegion();
+  }
+
+  auto State = C.getState();
+  const auto CData = getContainerData(State, ContReg);
+  if (!CData)
+    return;
+
+  if (const auto EndSym = CData->getEnd()) {
+    auto &SymMgr = C.getSymbolManager();
+    auto &BVF = SymMgr.getBasicVals();
+    auto &SVB = C.getSValBuilder();
+    const auto BackSym =
+      SVB.evalBinOp(State, BO_Sub,
+                    nonloc::SymbolVal(EndSym),
+                    nonloc::ConcreteInt(BVF.getValue(llvm::APSInt::get(1))),
+                    SymMgr.getType(EndSym)).getAsSymbol();
+    // For vector-like and deque-like containers invalidate the last and the
+    // past-end iterator positions. For list-like containers only invalidate
+    // the last position
+    if (hasSubscriptOperator(State, ContReg) &&
+        backModifiable(State, ContReg)) {
+      State = invalidateIteratorPositions(State, BackSym, BO_GE);
+      State = setContainerData(State, ContReg, CData->newEnd(nullptr));
+    } else {
+      State = invalidateIteratorPositions(State, BackSym, BO_EQ);
+    }
+    auto newEndSym = BackSym;
+    State = setContainerData(State, ContReg, CData->newEnd(newEndSym));
+    C.addTransition(State);
+  }
+}
+
+void IteratorChecker::handlePushFront(CheckerContext &C,
+                                      const SVal &Cont) const {
+  const auto *ContReg = Cont.getAsRegion();
+  if (!ContReg)
+    return;
+
+  while (const auto *CBOR = ContReg->getAs<CXXBaseObjectRegion>()) {
+    ContReg = CBOR->getSuperRegion();
+  }
+
+  // For deque-like containers invalidate all iterator positions
+  auto State = C.getState();
+  if (hasSubscriptOperator(State, ContReg)) {
+    State = invalidateAllIteratorPositions(State, ContReg);
+    C.addTransition(State);
+  } else {
+    const auto CData = getContainerData(State, ContReg);
+    if (!CData)
+      return;
+
+    if (const auto BeginSym = CData->getBegin()) {
+      auto &SymMgr = C.getSymbolManager();
+      auto &BVF = SymMgr.getBasicVals();
+      auto &SVB = C.getSValBuilder();
+      const auto newBeginSym =
+        SVB.evalBinOp(State, BO_Sub,
+                      nonloc::SymbolVal(BeginSym),
+                      nonloc::ConcreteInt(BVF.getValue(llvm::APSInt::get(1))),
+                      SymMgr.getType(BeginSym)).getAsSymbol();
+      State = setContainerData(State, ContReg, CData->newBegin(newBeginSym));
+      C.addTransition(State);
+    }
+  }
+}
+
+void IteratorChecker::handlePopFront(CheckerContext &C,
+                                     const SVal &Cont) const {
+  const auto *ContReg = Cont.getAsRegion();
+  if (!ContReg)
+    return;
+
+  while (const auto *CBOR = ContReg->getAs<CXXBaseObjectRegion>()) {
+    ContReg = CBOR->getSuperRegion();
+  }
+
+  auto State = C.getState();
+  const auto CData = getContainerData(State, ContReg);
+  if (!CData)
+    return;
+
+  // For deque-like containers invalidate all iterator positions. For list-like
+  // iterators only invalidate the first position
+  if (const auto BeginSym = CData->getBegin()) {
+    if (hasSubscriptOperator(State, ContReg)) {
+      State = invalidateIteratorPositions(State, BeginSym, BO_LE);
+    } else {
+      State = invalidateIteratorPositions(State, BeginSym, BO_EQ);
+    }
+    auto &SymMgr = C.getSymbolManager();
+    auto &BVF = SymMgr.getBasicVals();
+    auto &SVB = C.getSValBuilder();
+    const auto newBeginSym =
+      SVB.evalBinOp(State, BO_Add,
+                    nonloc::SymbolVal(BeginSym),
+                    nonloc::ConcreteInt(BVF.getValue(llvm::APSInt::get(1))),
+                    SymMgr.getType(BeginSym)).getAsSymbol();
+    State = setContainerData(State, ContReg, CData->newBegin(newBeginSym));
+    C.addTransition(State);
+  }
+}
+
 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));
 }
 

 namespace {
 
 bool isLess(ProgramStateRef State, SymbolRef Sym1, SymbolRef Sym2);
 bool isGreaterOrEqual(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 isIteratorType(const QualType &Type) {
   if (Type->isPointerType())
     return true;
 
   const auto *CRD = Type->getUnqualifiedDesugaredType()->getAsCXXRecordDecl();

 
 bool isEndCall(const FunctionDecl *Func) {
   const auto *IdInfo = Func->getIdentifier();
   if (!IdInfo)
     return false;
   return IdInfo->getName().endswith_lower("end");
 }
 
+bool isPushBackCall(const FunctionDecl *Func) {
+  const auto *IdInfo = Func->getIdentifier();
+  if (!IdInfo)
+    return false;
+  if (Func->getNumParams() != 1)
+    return false;
+  return IdInfo->getName() == "push_back";
+}
+
+bool isEmplaceBackCall(const FunctionDecl *Func) {
+  const auto *IdInfo = Func->getIdentifier();
+  if (!IdInfo)
+    return false;
+  if (Func->getNumParams() < 1)
+    return false;
+  return IdInfo->getName() == "emplace_back";
+}
+
+bool isPopBackCall(const FunctionDecl *Func) {
+  const auto *IdInfo = Func->getIdentifier();
+  if (!IdInfo)
+    return false;
+  if (Func->getNumParams() > 0)
+    return false;
+  return IdInfo->getName() == "pop_back";
+}
+
+bool isPushFrontCall(const FunctionDecl *Func) {
+  const auto *IdInfo = Func->getIdentifier();
+  if (!IdInfo)
+    return false;
+  if (Func->getNumParams() != 1)
+    return false;
+  return IdInfo->getName() == "push_front";
+}
+
+bool isEmplaceFrontCall(const FunctionDecl *Func) {
+  const auto *IdInfo = Func->getIdentifier();
+  if (!IdInfo)
+    return false;
+  if (Func->getNumParams() < 1)
+    return false;
+  return IdInfo->getName() == "emplace_front";
+}
+
+bool isPopFrontCall(const FunctionDecl *Func) {
+  const auto *IdInfo = Func->getIdentifier();
+  if (!IdInfo)
+    return false;
+  if (Func->getNumParams() > 0)
+    return false;
+  return IdInfo->getName() == "pop_front";
+}
+
 bool isAssignmentOperator(OverloadedOperatorKind OK) { return OK == OO_Equal; }
 
 bool isSimpleComparisonOperator(OverloadedOperatorKind OK) {
   return OK == OO_EqualEqual || OK == OO_ExclaimEqual;
 }
 
 bool isAccessOperator(OverloadedOperatorKind OK) {
   return isDereferenceOperator(OK) || isIncrementOperator(OK) ||
if (const auto *BSE = dyn_cast<BinarySymExpr>(SE)) {
     } else if (COE->getOperator() == OO_ExclaimEqual) {
       return BO_NE;
     }
     return BO_Comma; // Extremal value, neither EQ nor NE
   }
   return BO_Comma; // Extremal value, neither EQ nor NE
 }
 
+bool hasSubscriptOperator(ProgramStateRef State, const MemRegion *Reg) {
+  const auto *CRD = getCXXRecordDecl(State, Reg);
+  if (!CRD)
+    return false;
+
+  for (const auto *Method : CRD->methods()) {
+    if (!Method->isOverloadedOperator())
+      continue;
+    const auto OPK = Method->getOverloadedOperator();
+    if (OPK == OO_Subscript) {
+      return true;
+    }
+  }
+  return false;
+}
+
+bool frontModifiable(ProgramStateRef State, const MemRegion *Reg) {
+  const auto *CRD = getCXXRecordDecl(State, Reg);
+  if (!CRD)
+    return false;
+
+  for (const auto *Method : CRD->methods()) {
+    if (!Method->getDeclName().isIdentifier())
+      continue;
+    if (Method->getName() == "push_front" || Method->getName() == "pop_front") {
+      return true;
+    }
+  }
+  return false;
+}
+
+bool backModifiable(ProgramStateRef State, const MemRegion *Reg) {
+  const auto *CRD = getCXXRecordDecl(State, Reg);
+  if (!CRD)
+    return false;
+
+  for (const auto *Method : CRD->methods()) {
+    if (!Method->getDeclName().isIdentifier())
+      continue;
+    if (Method->getName() == "push_back" || Method->getName() == "pop_back") {
+      return true;
+    }
+  }
+  return false;
+}
+
+const CXXRecordDecl *getCXXRecordDecl(ProgramStateRef State,
+                                      const MemRegion *Reg) {
+  auto TI = getDynamicTypeInfo(State, Reg);
+  if (!TI.isValid())
+    return nullptr;
+
+  auto Type = TI.getType();
+  if (const auto *RefT = Type->getAs<ReferenceType>()) {
+    Type = RefT->getPointeeType();
+  }
+
+  return Type->getUnqualifiedDesugaredType()->getAsCXXRecordDecl();
+}
+
 const RegionOrSymbol getRegionOrSymbol(const SVal &Val) {
   if (const auto Reg = Val.getAsRegion()) {
     return Reg;
   } else if (const auto Sym = Val.getAsSymbol()) {
     return Sym;
   } else if (const auto LCVal = Val.getAs<nonloc::LazyCompoundVal>()) {
     return LCVal->getRegion();
   }
auto MatchCont = [&](const IteratorPosition &Pos) {
     return Pos.getContainer() == Cont;
   };
   auto Invalidate = [&](const IteratorPosition &Pos) {
     return Pos.invalidate();
   };
   return processIteratorPositions(State, MatchCont, Invalidate);
 }
 
+ProgramStateRef invalidateIteratorPositions(ProgramStateRef State,
+                                            SymbolRef Offset,
+                                            BinaryOperator::Opcode Opc) {
+  auto Compare = [&](const IteratorPosition &Pos) {
+    return compare(State, Pos.getOffset(), Offset, Opc);
+  };
+  auto Invalidate = [&](const IteratorPosition &Pos) {
+    return Pos.invalidate();
+  };
+  return processIteratorPositions(State, Compare, Invalidate);
+}
+
 ProgramStateRef reassignAllIteratorPositions(ProgramStateRef State,
                                              const MemRegion *Cont,
                                              const MemRegion *NewCont) {
   auto MatchCont = [&](const IteratorPosition &Pos) {
     return Pos.getContainer() == Cont;
   };
   auto ReAssign = [&](const IteratorPosition &Pos) {
     return Pos.reAssign(NewCont);
bool isGreaterOrEqual(ProgramStateRef State, SymbolRef Sym1, SymbolRef Sym2) {
   return compare(State, Sym1, Sym2, BO_GE);
 }
 
 bool compare(ProgramStateRef State, SymbolRef Sym1, SymbolRef Sym2,
              BinaryOperator::Opcode Opc) {
   return compare(State, nonloc::SymbolVal(Sym1), nonloc::SymbolVal(Sym2), Opc);
 }
 
+
 bool compare(ProgramStateRef State, NonLoc NL1, NonLoc NL2,
              BinaryOperator::Opcode Opc) {
   auto &SVB = State->getStateManager().getSValBuilder();
 
   const auto comparison =
     SVB.evalBinOp(State, Opc, NL1, NL2, SVB.getConditionType());
 
   assert(comparison.getAs<DefinedSVal>() &&

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

public:
     template <typename InputIterator >
     void assign(InputIterator first, InputIterator last);
     void assign(std::initializer_list<T> ilist);
 
     void clear();
 
     void push_back(const T &value);
     void push_back(T &&value);
+    template<class... Args>
+    void emplace_back(Args&&... args);
     void pop_back();
 
     T &operator[](size_t n) {
       return _start[n];
     }
     
     const T &operator[](size_t n) const {
       return _start[n];
public:
     template <typename InputIterator >
     void assign(InputIterator first, InputIterator last);
     void assign(std::initializer_list<T> ilist);
 
     void clear();
 
     void push_back(const T &value);
     void push_back(T &&value);
+    template<class... Args>
+    void emplace_back(Args&&... args);
     void pop_back();
 
     void push_front(const T &value);
     void push_front(T &&value);
+    template<class... Args>
+    void emplace_front(Args&&... args);
     void pop_front();
 
     iterator begin() { return iterator(_start); }
     const_iterator begin() const { return const_iterator(_start); }
     const_iterator cbegin() const { return const_iterator(_start); }
     iterator end() { return iterator(_finish); }
     const_iterator end() const { return const_iterator(_finish); }
     const_iterator cend() const { return const_iterator(_finish); }
public:
     template <typename InputIterator >
     void assign(InputIterator first, InputIterator last);
     void assign(std::initializer_list<T> ilist);
 
     void clear();
 
     void push_back(const T &value);
     void push_back(T &&value);
+    template<class... Args>
+    void emplace_back(Args&&... args);
     void pop_back();
 
     void push_front(const T &value);
     void push_front(T &&value);
+    template<class... Args>
+    void emplace_front(Args&&... args);
     void pop_front();
 
     T &operator[](size_t n) {
       return _start[n];
     }
 
     const T &operator[](size_t n) const {
       return _start[n];
public:
     template <typename InputIterator >
     void assign(InputIterator first, InputIterator last);
     void assign(std::initializer_list<T> ilist);
 
     void clear();
 
     void push_front(const T &value);
     void push_front(T &&value);
+    template<class... Args>
+    void emplace_front(Args&&... args);
     void pop_front();
 
     iterator begin() { return iterator(_start); }
     const_iterator begin() const { return const_iterator(_start); }
     const_iterator cbegin() const { return const_iterator(_start); }
     iterator end() { return iterator(); }
     const_iterator end() const { return const_iterator(); }
     const_iterator cend() const { return const_iterator(); }

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:554 {{Called C++ object pointer is null}}
+  // expected-warning@../Inputs/system-header-simulator-cxx.h:566 {{Called C++ object pointer is null}}
 #endif
 }

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

 }
 
 void bad_copy_assign_operator_forward_list1(std::forward_list<int> &FL1,
                                             const std::forward_list<int> &FL2) {
   auto i0 = FL1.cbegin();
   FL1 = FL2;
   *i0; // expected-warning{{Invalidated iterator accessed}}
 }
+
+void good_push_back_list1(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) {
+  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) {
+  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) {
+  auto i0 = D.cbegin(), i1 = D.cend();
+  D.push_back(n);
+  *i0; // expected-warning{{Invalidated iterator accessed}}
+  --i1; // expected-warning{{Invalidated iterator accessed}}
+}
+
+void good_emplace_back_list1(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) {
+  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) {
+  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) {
+  auto i0 = D.cbegin(), i1 = D.cend();
+  D.emplace_back(n);
+  *i0; // expected-warning{{Invalidated iterator accessed}}
+  --i1; // expected-warning{{Invalidated iterator accessed}}
+}
+
+void good_pop_back_list1(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) {
+  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) {
+  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) {
+  auto i0 = V.cbegin(), i1 = V.cend(), i2 = i1--;
+  V.pop_back();
+  *i1; // expected-warning{{Invalidated iterator accessed}}
+  --i2; // expected-warning{{Invalidated iterator accessed}}
+}
+
+void good_pop_back_deque1(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) {
+  auto i0 = D.cbegin(), i1 = D.cend(), i2 = i1--;
+  D.pop_back();
+  *i1; // expected-warning{{Invalidated iterator accessed}}
+  --i2; // expected-warning{{Invalidated iterator accessed}}
+}
+
+void good_push_front_list1(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) {
+  auto i0 = D.cbegin(), i1 = D.cend();
+  D.push_front(n);
+  *i0; // expected-warning{{Invalidated iterator accessed}}
+  --i1; // expected-warning{{Invalidated iterator accessed}}
+}
+
+void good_push_front_forward_list1(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) {
+  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) {
+  auto i0 = D.cbegin(), i1 = D.cend();
+  D.emplace_front(n);
+  *i0; // expected-warning{{Invalidated iterator accessed}}
+  --i1; // expected-warning{{Invalidated iterator accessed}}
+}
+
+void good_emplace_front_forward_list1(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) {
+  auto i1 = L.cbegin(), i0 = i1++;
+  L.pop_front();
+  *i1; // no-warning
+}
+
+void bad_pop_front_list1(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) {
+  auto i1 = D.cbegin(), i0 = i1++;
+  D.pop_front();
+  *i1; // no-warning
+}
+
+void bad_pop_front_deque1(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) {
+  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) {
+  auto i1 = FL.cbegin(), i0 = i1++;
+  FL.pop_front();
+  *i0; // expected-warning{{Invalidated iterator accessed}}
+}

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

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}}
+}
+
+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}}
+}
+
+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}}
+}
+
+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}}
+}
+
 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}}
 }
+
+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}}
+}