[Analyzer] Model `empty()` member function of containers

[baloghadamsoftware]

Summary

Modeling the empty() method of containers both improves iterator range checking and enables the possibility to create new checkers for containers.

[baloghadamsoftware]

Supersedes D62688.

[baloghadamsoftware]

clang/lib/StaticAnalyzer/Checkers/IteratorModeling.cpp

492

Maybe I should move these lines into a separate function in the library to avoid repetition.

511–512

This is way longer than the previously used processComparison() but I am reluctant to pass CheckerContext to a non-member function. (And especially add transitions there. Even worse, to a function in a common library.)

[martong]

clang/lib/StaticAnalyzer/Checkers/ContainerModeling.cpp

34–75

Perhaps it would be easier to read these functions if we had a documentation for their parameters. Maybe we could have some of them documented in one comment since many seem to have similar params.
Or maybe just renaming Cont to Container would help also.

56

I understand that the container SVal is no longer const, but why did the iterator loose its constness?

85–86

Just a nit, if we are at counting below (one, two) then perhaps Zero would be more coherent with the other typedefs?

270–271

Why do we skip the const qualifiers here?

432

Is there really no sense to continue the analysis here? In what state we are here exactly? Is there an inconsistency between the begin , end and the return value?

clang/lib/StaticAnalyzer/Checkers/Iterator.cpp

21

Docs, docs, docs.

312

Perhaps we should guard Op with an assert, I mean it should be either == or !=.

314

Could we spare the if with just keeping the declaration of State and then

return std::make_pair(State, nullptr);

?

315–316

This is hard to read for me. Also, Isn't it enough just to write TruthVal->getValue() ?

328

Why do we assume here again? We already had an assume in relateSymbols, hadn't we?

339

Please explain in the comment what is the problem with the current impl.

351–352

Could we merge the declaration of the new state into the parens of the if?

clang/lib/StaticAnalyzer/Checkers/Iterator.h

182

Documentation would be helpful.

clang/test/Analysis/container-modeling.cpp

19

It seems like we don't use it anywhere.

[martong]

clang/lib/StaticAnalyzer/Checkers/Iterator.cpp

335

Would assumeEqual be a better name?

[baloghadamsoftware]

Rebased, updated.

[baloghadamsoftware]

clang/lib/StaticAnalyzer/Checkers/ContainerModeling.cpp

56

We passed it earlier as a constant reference, but SVal is small, it should be passed by value.

270–271

Do you mean for SVal? See above.

432

Yes, see the comment I added. If data about emptiness based on the difference of begin and and and the return value of empty() contradict each other then we are on an impossible branch.

clang/lib/StaticAnalyzer/Checkers/Iterator.cpp

21

This function is moved here, it is nothing new.

312

Actually, this works for any comparison operator. So it is enough to assume that Op is a comparison operator.

328

In relateSymbols we assumed the comparison of the two symbols. Here we assume the RetVal. The new states are nullptr if we cannot assume the same for both.

335

This method is just moved from another source file.

339

Ditto. The community requested a future refactoring.

351–352

No, because we use it later in the function. (See below.)

clang/test/Analysis/container-modeling.cpp

19

We use this in the definition of the assert() macro. And we use that macro in the new test cases.

[baloghadamsoftware]

Updated according to the comments.

[baloghadamsoftware]

Minor fix.

[baloghadamsoftware]

isIterator() updated because it did not work perfectly with the refactored handleBegin() after rebase. (Why did it work before the rebase?) The problem was that it only looked for the necessary operators in the actual class but not in its bases.

[Szelethus]

I'm in favor of most, if not all of the changes, though I will admit that this patch seems pretty cluttered, you are doing a lot of refactoring under the same hood. You're moving, adding, removing and changing helper functions and their invocations. Would be possible to make this patch a bit leaner?

clang/lib/StaticAnalyzer/Checkers/ContainerModeling.cpp

36

Hmm, this was changed to an optional, unnamed parameter without docs... Might be a bit cryptic :) Also, this seems to be orthogonal to the patch, is it not? Does the modeling of empty() change something that affects this function?

420

assumpotions > assumptions

420–427

You will have to help me out here -- if the analyzer couldn't return a sensible symbol, is it okay to just create one? When does UnknownVal even happen, does it ever happen? Also, if we're doing this anyways, wouldn't using evalCall be more appropriate?

clang/unittests/StaticAnalyzer/TestReturnValueUnderConstruction.cpp

71 ↗

(On Diff #289981)

Did you mean to upload changed to this file from D85351 to this patch as well?

[baloghadamsoftware]

Wrong diff uploaded previously. (Accidentally compared to master instead of the prerequisite.)

[baloghadamsoftware]

clang/lib/StaticAnalyzer/Checkers/ContainerModeling.cpp

36

We discussed with @NoQ a few patches earlier that UnknownVal is not a nullptr-like value for SVals. That time I changed this bad practice in my code everywhere, only forgot this particular place. I do not think that this deserves its own patch, it is really a tiny thing.

420–427

Actually, both UnknownVal and SymbolVal containing a SymbolConjured without constraints are unknown. The main difference (for us) is that we cannot assign constraints to UnknownVal but we can for SymbolConjured. This is the reason for replacing it. However, this is not new. We do it in comparison too. The best would be to change the infrastructure to never return UnknownVal but conjure a new symbol instead if we known nothing about the return value. Maybe I will put a FIXME there. evalCall() is not an option, because we do not want to lose the possibility that the implementation of empty() is inlined by the engine.

clang/unittests/StaticAnalyzer/TestReturnValueUnderConstruction.cpp

71 ↗

(On Diff #289981)

No, I just uploaded the wrong diff here.

clang/lib/StaticAnalyzer/Checkers/ContainerModeling.cpp

 using namespace clang;
 using namespace ento;
 using namespace iterator;
 
 namespace {
 
 class ContainerModeling
   : public Checker<check::PostCall, check::LiveSymbols, check::DeadSymbols> {
 
-  void handleBegin(CheckerContext &C, const Expr *CE, SVal RetVal,
-                   SVal Cont) const;
-  void handleEnd(CheckerContext &C, const Expr *CE, SVal RetVal,
-                 SVal Cont) const;
-  void handleAssignment(CheckerContext &C, SVal Cont, const Expr *CE = nullptr,
-                        SVal OldCont = UndefinedVal()) const;
-  void handleAssign(CheckerContext &C, SVal Cont, const Expr *ContE) const;
-  void handleClear(CheckerContext &C, SVal Cont, const Expr *ContE) const;
-  void handlePushBack(CheckerContext &C, SVal Cont, const Expr *ContE) const;
-  void handlePopBack(CheckerContext &C, SVal Cont, const Expr *ContE) const;
-  void handlePushFront(CheckerContext &C, SVal Cont, const Expr *ContE) const;
-  void handlePopFront(CheckerContext &C, SVal Cont, const Expr *ContE) const;
-  void handleInsert(CheckerContext &C, SVal Cont, SVal Iter) const;
-  void handleErase(CheckerContext &C, SVal Cont, SVal Iter) const;
-  void handleErase(CheckerContext &C, SVal Cont, SVal Iter1, SVal Iter2) const;
-  void handleEraseAfter(CheckerContext &C, SVal Cont, SVal Iter) const;
-  void handleEraseAfter(CheckerContext &C, SVal Cont, SVal Iter1,
-                        SVal Iter2) const;
+  void handleAssignment(CheckerContext &C, const Expr *CE, SVal Cont,
+                        Optional<SVal> = None) const;
+
+  // Handler functions for different container operations.
+  // SVal Parameters:
+  // - Cont:                      The affected container (*this)
+  // - RetVal:                    Return value of the operation
+  // - Iter (or Iter1 and Iter2): Iterator parameters
+
+  void handleBegin(CheckerContext &C, const Expr *CE, const Expr *ContE,
+                   SVal Cont, SVal RetVal) const;
+  void handleEnd(CheckerContext &C, const Expr *CE, const Expr *ContE,
+                 SVal Cont, SVal RetVal) const;
+  void handleEmpty(CheckerContext &C, const Expr *CE, const Expr *ContE,
+                   SVal Cont, SVal RetVal) const;
+  void handleAssign(CheckerContext &C, const Expr *CE, const Expr *ContE,
+                    SVal Cont, SVal RetVal) const;
+  void handleClear(CheckerContext &C, const Expr *CE, const Expr *ContE,
+                   SVal Cont, SVal RetVal) const;
+  void handlePushBack(CheckerContext &C, const Expr *CE, const Expr *ContE,
+                      SVal Cont, SVal RetVal) const;
+  void handlePopBack(CheckerContext &C, const Expr *CE, const Expr *ContE,
+                     SVal Cont, SVal RetVal) const;
+  void handlePushFront(CheckerContext &C, const Expr *CE, const Expr *ContE,
+                       SVal Cont, SVal RetVal) const;
+  void handlePopFront(CheckerContext &C, const Expr *CE, const Expr *ContE,
+                      SVal Cont, SVal RetVal) const;
+  void handleInsert(CheckerContext &C, const Expr *CE, const Expr *ContE,
+                    SVal Cont, SVal Iter, SVal RetVal) const;
+  void handleErase(CheckerContext &C, const Expr *CE, const Expr *ContE,
+                   SVal Cont, SVal Iter, SVal RetVal) const;
+  void handleErase(CheckerContext &C, const Expr *CE, const Expr *ContE,
+                   SVal Cont, SVal Iter1, SVal Iter2, SVal RetVal) const;
+  void handleEraseAfter(CheckerContext &C, const Expr *CE, const Expr *ContE,
+                        SVal Cont, SVal Iter, SVal RetVal) const;
+  void handleEraseAfter(CheckerContext &C, const Expr *CE, const Expr *ContE,
+                        SVal Cont, SVal Iter1, SVal Iter2, SVal RetVal) const;
+
   const NoteTag *getChangeTag(CheckerContext &C, StringRef Text,
                               const MemRegion *ContReg,
                               const Expr *ContE) const;
   void printState(raw_ostream &Out, ProgramStateRef State, const char *NL,
                   const char *Sep) const override;
 
 public:
   ContainerModeling() = default;
 
   void checkPostCall(const CallEvent &Call, CheckerContext &C) const;
   void checkLiveSymbols(ProgramStateRef State, SymbolReaper &SR) const;
   void checkDeadSymbols(SymbolReaper &SR, CheckerContext &C) const;
 
-  using NoItParamFn = void (ContainerModeling::*)(CheckerContext &, SVal,
-                                                  const Expr *) const;
-  using OneItParamFn = void (ContainerModeling::*)(CheckerContext &, SVal,
-                                                   SVal) const;
-  using TwoItParamFn = void (ContainerModeling::*)(CheckerContext &, SVal, SVal,
-                                                   SVal) const;
-
-  CallDescriptionMap<NoItParamFn> NoIterParamFunctions = {
-    {{0, "clear", 0},
-     &ContainerModeling::handleClear},
-    {{0, "assign", 2},
-     &ContainerModeling::handleAssign},
-    {{0, "push_back", 1},
-     &ContainerModeling::handlePushBack},
-    {{0, "emplace_back", 1},
-     &ContainerModeling::handlePushBack},
-    {{0, "pop_back", 0},
-     &ContainerModeling::handlePopBack},
-    {{0, "push_front", 1},
-     &ContainerModeling::handlePushFront},
-    {{0, "emplace_front", 1},
-     &ContainerModeling::handlePushFront},
-    {{0, "pop_front", 0},
-     &ContainerModeling::handlePopFront},
+  using ZeroItParamFn =
+    void (ContainerModeling::*)(CheckerContext &, const Expr *, const Expr *,
+                                SVal, SVal) const;
+  using OneItParamFn =
+    void (ContainerModeling::*)(CheckerContext &, const Expr *, const Expr *,
+                                SVal, SVal, SVal) const;
+  using TwoItParamFn =
+    void (ContainerModeling::*)(CheckerContext &, const Expr *, const Expr *,
+                                SVal, SVal, SVal, SVal) const;
+
+  CallDescriptionMap<ZeroItParamFn> ZeroIterParamFunctions = {
+    // Iterators
+    {{0, "cbegin", 0}, &ContainerModeling::handleBegin},
+    {{0, "cend", 0}, &ContainerModeling::handleEnd},
+    {{0, "begin", 0}, &ContainerModeling::handleBegin},
+    {{0, "end", 0}, &ContainerModeling::handleEnd},
+
+    // Capacity
+    {{0, "empty", 0}, &ContainerModeling::handleEmpty},
+
+    // Modifiers
+    {{0, "clear", 0}, &ContainerModeling::handleClear},
+    {{0, "assign", 2}, &ContainerModeling::handleAssign},
+    {{0, "push_back", 1}, &ContainerModeling::handlePushBack},
+    {{0, "emplace_back", 1}, &ContainerModeling::handlePushBack},
+    {{0, "pop_back", 0}, &ContainerModeling::handlePopBack},
+    {{0, "push_front", 1}, &ContainerModeling::handlePushFront},
+    {{0, "emplace_front", 1}, &ContainerModeling::handlePushFront},
+    {{0, "pop_front", 0}, &ContainerModeling::handlePopFront},
   };
                                                           
   CallDescriptionMap<OneItParamFn> OneIterParamFunctions = {
-    {{0, "insert", 2},
-     &ContainerModeling::handleInsert},
-    {{0, "emplace", 2},
-     &ContainerModeling::handleInsert},
-    {{0, "erase", 1},
-     &ContainerModeling::handleErase},
-    {{0, "erase_after", 1},
-     &ContainerModeling::handleEraseAfter},
+    {{0, "insert", 2}, &ContainerModeling::handleInsert},
+    {{0, "emplace", 2}, &ContainerModeling::handleInsert},
+    {{0, "erase", 1}, &ContainerModeling::handleErase},
+    {{0, "erase_after", 1}, &ContainerModeling::handleEraseAfter},
   };
                                                           
   CallDescriptionMap<TwoItParamFn> TwoIterParamFunctions = {
-    {{0, "erase", 2},
-     &ContainerModeling::handleErase},
-    {{0, "erase_after", 2},
-     &ContainerModeling::handleEraseAfter},
+    {{0, "erase", 2}, &ContainerModeling::handleErase},
+    {{0, "erase_after", 2}, &ContainerModeling::handleEraseAfter},
   };
-                                                          
 };
 
-bool isBeginCall(const FunctionDecl *Func);
-bool isEndCall(const FunctionDecl *Func);
 bool hasSubscriptOperator(ProgramStateRef State, const MemRegion *Reg);
 bool frontModifiable(ProgramStateRef State, const MemRegion *Reg);
 bool backModifiable(ProgramStateRef State, const MemRegion *Reg);
 SymbolRef getContainerBegin(ProgramStateRef State, const MemRegion *Cont);
 SymbolRef getContainerEnd(ProgramStateRef State, const MemRegion *Cont);
 ProgramStateRef createContainerBegin(ProgramStateRef State,
                                      const MemRegion *Cont, const Expr *E,
                                      QualType T, const LocationContext *LCtx,
if (!Func)
     return;
 
   if (Func->isOverloadedOperator()) {
     const auto Op = Func->getOverloadedOperator();
     if (Op == OO_Equal) {
       // Overloaded 'operator=' must be a non-static member function.
       const auto *InstCall = cast<CXXInstanceCall>(&Call);
       if (cast<CXXMethodDecl>(Func)->isMoveAssignmentOperator()) {
-        handleAssignment(C, InstCall->getCXXThisVal(), Call.getOriginExpr(),
+        handleAssignment(C, Call.getOriginExpr(), InstCall->getCXXThisVal(),
                          Call.getArgSVal(0));
         return;
       }
 
-      handleAssignment(C, InstCall->getCXXThisVal());
+      handleAssignment(C, Call.getOriginExpr(), InstCall->getCXXThisVal());
       return;
     }
   } else if (const auto *InstCall = dyn_cast<CXXInstanceCall>(&Call)) {
     const auto *OrigExpr = Call.getOriginExpr();
     if (!OrigExpr)
       return;
 
-    if (isBeginCall(Func)) {
-      handleBegin(C, OrigExpr, getReturnIterator(Call),
-                  InstCall->getCXXThisVal());
-      return;
-    }
-
-    if (isEndCall(Func)) {
-      handleEnd(C, OrigExpr, getReturnIterator(Call),
-                InstCall->getCXXThisVal());
-      return;
-    }
+    SVal RetVal = Call.getReturnValue();
+    if (isIteratorType(Call.getResultType()))
+      RetVal = getReturnIterator(Call);
 
-    const NoItParamFn *Handler0 = NoIterParamFunctions.lookup(Call);
+    const ZeroItParamFn *Handler0 = ZeroIterParamFunctions.lookup(Call);
     if (Handler0) {
-      (this->**Handler0)(C, InstCall->getCXXThisVal(),
-                         InstCall->getCXXThisExpr());
+      (this->**Handler0)(C, OrigExpr, InstCall->getCXXThisExpr(),
+                         InstCall->getCXXThisVal(), RetVal);
       return;
     }
 
-    if (Call.getNumArgs() < 1)
-      return;
-
-    SVal Arg0 = getIteratorArg(Call, 0, C.blockCount());
     const OneItParamFn *Handler1 = OneIterParamFunctions.lookup(Call);
     if (Handler1) {
-      (this->**Handler1)(C, InstCall->getCXXThisVal(), Arg0);
+      SVal Arg0 = getIteratorArg(Call, 0, C.blockCount());
+      (this->**Handler1)(C, OrigExpr, InstCall->getCXXThisExpr(),
+                         InstCall->getCXXThisVal(), Arg0, RetVal);
       return;
     }
 
-    if (Call.getNumArgs() < 2)
-      return;
-
-    SVal Arg1 = getIteratorArg(Call, 1, C.blockCount());
     const TwoItParamFn *Handler2 = TwoIterParamFunctions.lookup(Call);
     if (Handler2) {
-      (this->**Handler2)(C, InstCall->getCXXThisVal(), Arg0, Arg1);
+      SVal Arg0 = getIteratorArg(Call, 0, C.blockCount());
+      SVal Arg1 = getIteratorArg(Call, 1, C.blockCount());
+      (this->**Handler2)(C, OrigExpr, InstCall->getCXXThisExpr(),
+                         InstCall->getCXXThisVal(), Arg0, Arg1, RetVal);
       return;
     }
   }
 }
 
 void ContainerModeling::checkLiveSymbols(ProgramStateRef State,
                                          SymbolReaper &SR) const {
   // Keep symbolic expressions of container begins and ends alive
if (!SR.isLiveRegion(Cont.first)) {
       }
     }
   }
 
   C.addTransition(State);
 }
 
 void ContainerModeling::handleBegin(CheckerContext &C, const Expr *CE,
-                                    SVal RetVal, SVal Cont) const {
+                                    const Expr *, SVal Cont,
+                                    SVal RetVal) const {
   const auto *ContReg = Cont.getAsRegion();
   if (!ContReg)
     return;
 
   ContReg = ContReg->getMostDerivedObjectRegion();
 
   // If the container already has a begin symbol then use it. Otherwise first
   // create a new one.
   auto State = C.getState();
   auto BeginSym = getContainerBegin(State, ContReg);
   if (!BeginSym) {
     State = createContainerBegin(State, ContReg, CE, C.getASTContext().LongTy,
                                  C.getLocationContext(), C.blockCount());
     BeginSym = getContainerBegin(State, ContReg);
   }
 
   State = setIteratorPosition(State, RetVal,
                               IteratorPosition::getPosition(ContReg, BeginSym));
   C.addTransition(State);
 }
 
 void ContainerModeling::handleEnd(CheckerContext &C, const Expr *CE,
-                                  SVal RetVal, SVal Cont) const {
+                                  const Expr *, SVal Cont, SVal RetVal) const {
   const auto *ContReg = Cont.getAsRegion();
   if (!ContReg)
     return;
 
   ContReg = ContReg->getMostDerivedObjectRegion();
 
   // If the container already has an end symbol then use it. Otherwise first
   // create a new one.
   auto State = C.getState();
   auto EndSym = getContainerEnd(State, ContReg);
   if (!EndSym) {
     State = createContainerEnd(State, ContReg, CE, C.getASTContext().LongTy,
                                C.getLocationContext(), C.blockCount());
     EndSym = getContainerEnd(State, ContReg);
   }
 
   State = setIteratorPosition(State, RetVal,
                               IteratorPosition::getPosition(ContReg, EndSym));
   C.addTransition(State);
 }
 
-void ContainerModeling::handleAssignment(CheckerContext &C, SVal Cont,
-                                         const Expr *CE, SVal OldCont) const {
+void ContainerModeling::handleAssignment(CheckerContext &C, const Expr *CE,
+                                         SVal Cont,
+                                         Optional<SVal> OldCont) const {
   const auto *ContReg = Cont.getAsRegion();
   if (!ContReg)
     return;
 
   ContReg = ContReg->getMostDerivedObjectRegion();
 
   // Assignment of a new value to a container always invalidates all its
   // iterators
   auto State = C.getState();
   const auto CData = getContainerData(State, ContReg);
   if (CData) {
     State = invalidateAllIteratorPositions(State, ContReg);
   }
 
   // In case of move, iterators of the old container (except the past-end
   // iterators) remain valid but refer to the new container
-  if (!OldCont.isUndef()) {
-    const auto *OldContReg = OldCont.getAsRegion();
+  if (OldCont.hasValue()) {
+    const auto *OldContReg = OldCont->getAsRegion();
     if (OldContReg) {
       OldContReg = OldContReg->getMostDerivedObjectRegion();
       const auto OldCData = getContainerData(State, OldContReg);
       if (OldCData) {
         if (const auto OldEndSym = OldCData->getEnd()) {
           // If we already assigned an "end" symbol to the old container, then
           // first reassign all iterator positions to the new container which
           // are not past the container (thus not greater or equal to the
if (OldContReg) {
         // container, so reassign all iterator positions to the new container.
         State = reassignAllIteratorPositions(State, OldContReg, ContReg);
       }
     }
   }
   C.addTransition(State);
 }
 
-void ContainerModeling::handleAssign(CheckerContext &C, SVal Cont,
-                                     const Expr *ContE) const {
+void ContainerModeling::handleEmpty(CheckerContext &C, const Expr *CE,
+                                    const Expr *, SVal Cont,
+                                    SVal RetVal) const {
+  const auto *ContReg = Cont.getAsRegion();
+  if (!ContReg)
+    return;
+
+  ContReg = ContReg->getMostDerivedObjectRegion();
+
+  // If the container already has a begin symbol then use it. Otherwise first
+  // create a new one.
+  auto State = C.getState();
+  auto *LCtx = C.getLocationContext();
+
+  auto BeginSym = getContainerBegin(State, ContReg);
+  if (!BeginSym) {
+    State = createContainerBegin(State, ContReg, CE, C.getASTContext().LongTy,
+                                 LCtx, C.blockCount());
+    BeginSym = getContainerBegin(State, ContReg);
+  }
+  auto EndSym = getContainerEnd(State, ContReg);
+  if (!EndSym) {
+    State = createContainerEnd(State, ContReg, CE, C.getASTContext().LongTy,
+                               LCtx, C.blockCount());
+    EndSym = getContainerEnd(State, ContReg);
+  }
+
+  // We cannot make assumpotions on `UnknownVal`. Let us conjure a symbol
+  // instead.
+  if (RetVal.isUnknown()) {
+    auto &SymMgr = C.getSymbolManager();
+    RetVal = nonloc::SymbolVal(SymMgr.conjureSymbol(
+        CE, LCtx, C.getASTContext().BoolTy, C.blockCount()));
+    State = State->BindExpr(CE, LCtx, RetVal);
+  }
+
+  if (const auto DefRetVal = RetVal.getAs<DefinedSVal>()) {
+    ProgramStateRef StateEmpty, StateNonEmpty;
+    std::tie(StateEmpty, StateNonEmpty) =
+      assumeComparison(State, BeginSym, EndSym, *DefRetVal, OO_EqualEqual);
+
+    if (!StateEmpty && !StateNonEmpty) {
+      // The return value of the `empty()` call contradicts the emptyness of
+      // the container.
+      C.generateSink(State, C.getPredecessor());
+      return;
+    }
+
+    if (StateEmpty)
+      C.addTransition(StateEmpty);
+
+    if (StateNonEmpty)
+      C.addTransition(StateNonEmpty);
+  }
+}
+
+void ContainerModeling::handleAssign(CheckerContext &C, const Expr *CE,
+                                     const Expr *, SVal Cont,
+                                     SVal RetVal) const {
   const auto *ContReg = Cont.getAsRegion();
   if (!ContReg)
     return;
 
   ContReg = ContReg->getMostDerivedObjectRegion();
 
   // The assign() operation invalidates all the iterators
   auto State = C.getState();
   State = invalidateAllIteratorPositions(State, ContReg);
   C.addTransition(State);
 }
 
-void ContainerModeling::handleClear(CheckerContext &C, SVal Cont,
-                                    const Expr *ContE) const {
+void ContainerModeling::handleClear(CheckerContext &C, const Expr *CE,
+                                    const Expr *ContE, SVal Cont,
+                                    SVal RetVal) const {
   const auto *ContReg = Cont.getAsRegion();
   if (!ContReg)
     return;
 
   ContReg = ContReg->getMostDerivedObjectRegion();
 
   // The clear() operation invalidates all the iterators, except the past-end
   // iterators of list-like containers
if (!hasSubscriptOperator(State, ContReg) ||
     }
   }
   const NoteTag *ChangeTag =
     getChangeTag(C, "became empty", ContReg, ContE);
   State = invalidateAllIteratorPositions(State, ContReg);
   C.addTransition(State, ChangeTag);
 }
 
-void ContainerModeling::handlePushBack(CheckerContext &C, SVal Cont,
-                                       const Expr *ContE) const {
+void ContainerModeling::handlePushBack(CheckerContext &C, const Expr *CE,
+                                       const Expr *ContE, SVal Cont,
+                                       SVal RetVal) const {
   const auto *ContReg = Cont.getAsRegion();
   if (!ContReg)
     return;
 
   ContReg = ContReg->getMostDerivedObjectRegion();
 
   // For deque-like containers invalidate all iterator positions
   auto State = C.getState();
const auto newEndSym =
                     SymMgr.getType(EndSym)).getAsSymbol();
     const NoteTag *ChangeTag =
       getChangeTag(C, "extended to the back by 1 position", ContReg, ContE);
     State = setContainerData(State, ContReg, CData->newEnd(newEndSym));
     C.addTransition(State, ChangeTag);
   }
 }
 
-void ContainerModeling::handlePopBack(CheckerContext &C, SVal Cont,
-                                      const Expr *ContE) const {
+void ContainerModeling::handlePopBack(CheckerContext &C, const Expr *CE,
+                                      const Expr *ContE, SVal Cont,
+                                      SVal RetVal) const {
   const auto *ContReg = Cont.getAsRegion();
   if (!ContReg)
     return;
 
   ContReg = ContReg->getMostDerivedObjectRegion();
 
   auto State = C.getState();
   const auto CData = getContainerData(State, ContReg);
if (hasSubscriptOperator(State, ContReg) &&
       State = invalidateIteratorPositions(State, BackSym, BO_EQ);
     }
     auto newEndSym = BackSym;
     State = setContainerData(State, ContReg, CData->newEnd(newEndSym));
     C.addTransition(State, ChangeTag);
   }
 }
 
-void ContainerModeling::handlePushFront(CheckerContext &C, SVal Cont,
-                                        const Expr *ContE) const {
+void ContainerModeling::handlePushFront(CheckerContext &C, const Expr *CE,
+                                        const Expr *ContE, SVal Cont,
+                                        SVal RetVal) const {
   const auto *ContReg = Cont.getAsRegion();
   if (!ContReg)
     return;
 
   ContReg = ContReg->getMostDerivedObjectRegion();
 
   // For deque-like containers invalidate all iterator positions
   auto State = C.getState();
if (const auto BeginSym = CData->getBegin()) {
       const NoteTag *ChangeTag =
         getChangeTag(C, "extended to the front by 1 position", ContReg, ContE);
       State = setContainerData(State, ContReg, CData->newBegin(newBeginSym));
       C.addTransition(State, ChangeTag);
     }
   }
 }
 
-void ContainerModeling::handlePopFront(CheckerContext &C, SVal Cont,
-                                       const Expr *ContE) const {
+void ContainerModeling::handlePopFront(CheckerContext &C, const Expr *CE,
+                                       const Expr *ContE, SVal Cont,
+                                       SVal RetVal) const {
   const auto *ContReg = Cont.getAsRegion();
   if (!ContReg)
     return;
 
   ContReg = ContReg->getMostDerivedObjectRegion();
 
   auto State = C.getState();
   const auto CData = getContainerData(State, ContReg);
const auto newBeginSym =
                     SymMgr.getType(BeginSym)).getAsSymbol();
     const NoteTag *ChangeTag =
       getChangeTag(C, "shrank from the front by 1 position", ContReg, ContE);
     State = setContainerData(State, ContReg, CData->newBegin(newBeginSym));
     C.addTransition(State, ChangeTag);
   }
 }
 
-void ContainerModeling::handleInsert(CheckerContext &C, SVal Cont,
-                                     SVal Iter) const {
+void ContainerModeling::handleInsert(CheckerContext &C, const Expr *CE,
+                                     const Expr *, SVal Cont, SVal Iter,
+                                     SVal RetVal) const {
   const auto *ContReg = Cont.getAsRegion();
   if (!ContReg)
     return;
 
   ContReg = ContReg->getMostDerivedObjectRegion();
 
   auto State = C.getState();
   const auto *Pos = getIteratorPosition(State, Iter);
if (const auto *CData = getContainerData(State, ContReg)) {
         State = invalidateIteratorPositions(State, EndSym, BO_GE);
         State = setContainerData(State, ContReg, CData->newEnd(nullptr));
       }
     }
     C.addTransition(State);
   }
 }
 
-void ContainerModeling::handleErase(CheckerContext &C, SVal Cont,
-                                    SVal Iter) const {
+void ContainerModeling::handleErase(CheckerContext &C, const Expr *CE,
+                                    const Expr *, SVal Cont, SVal Iter,
+                                    SVal RetVal) const {
   const auto *ContReg = Cont.getAsRegion();
   if (!ContReg)
     return;
 
   ContReg = ContReg->getMostDerivedObjectRegion();
 
   auto State = C.getState();
   const auto *Pos = getIteratorPosition(State, Iter);
if (const auto *CData = getContainerData(State, ContReg)) {
       }
     }
   } else {
     State = invalidateIteratorPositions(State, Pos->getOffset(), BO_EQ);
   }
   C.addTransition(State);
 }
 
-void ContainerModeling::handleErase(CheckerContext &C, SVal Cont, SVal Iter1,
-                                    SVal Iter2) const {
+void ContainerModeling::handleErase(CheckerContext &C, const Expr *CE,
+                                    const Expr *, SVal Cont, SVal Iter1,
+                                    SVal Iter2, SVal RetVal) const {
   const auto *ContReg = Cont.getAsRegion();
   if (!ContReg)
     return;
 
   ContReg = ContReg->getMostDerivedObjectRegion();
   auto State = C.getState();
   const auto *Pos1 = getIteratorPosition(State, Iter1);
   const auto *Pos2 = getIteratorPosition(State, Iter2);
if (hasSubscriptOperator(State, ContReg) && backModifiable(State, ContReg)) {
     }
   } else {
     State = invalidateIteratorPositions(State, Pos1->getOffset(), BO_GE,
                                         Pos2->getOffset(), BO_LT);
   }
   C.addTransition(State);
 }
 
-void ContainerModeling::handleEraseAfter(CheckerContext &C, SVal Cont,
-                                        SVal Iter) const {
+void ContainerModeling::handleEraseAfter(CheckerContext &C, const Expr *CE,
+                                         const Expr *, SVal Cont, SVal Iter,
+                                         SVal RetVal) const {
   auto State = C.getState();
   const auto *Pos = getIteratorPosition(State, Iter);
   if (!Pos)
     return;
 
   // Invalidate the deleted iterator position, which is the position of the
   // parameter plus one.
   auto &SymMgr = C.getSymbolManager();
   auto &BVF = SymMgr.getBasicVals();
   auto &SVB = C.getSValBuilder();
   const auto NextSym =
     SVB.evalBinOp(State, BO_Add,
                   nonloc::SymbolVal(Pos->getOffset()),
                   nonloc::ConcreteInt(BVF.getValue(llvm::APSInt::get(1))),
                   SymMgr.getType(Pos->getOffset())).getAsSymbol();
   State = invalidateIteratorPositions(State, NextSym, BO_EQ);
   C.addTransition(State);
 }
 
-void ContainerModeling::handleEraseAfter(CheckerContext &C, SVal Cont,
-                                         SVal Iter1, SVal Iter2) const {
+void ContainerModeling::handleEraseAfter(CheckerContext &C, const Expr *CE,
+                                         const Expr *, SVal Cont, SVal Iter1,
+                                         SVal Iter2, SVal RetVal) const {
   auto State = C.getState();
   const auto *Pos1 = getIteratorPosition(State, Iter1);
   const auto *Pos2 = getIteratorPosition(State, Iter2);
   if (!Pos1 || !Pos2)
     return;
 
   // Invalidate the deleted iterator position range (first..last)
   State = invalidateIteratorPositions(State, Pos1->getOffset(), BO_GT,
for (const auto &Cont : ContMap) {
         Out << "<Unknown>";
       Out << " ]";
     }
   }
 }
 
 namespace {
 
-bool isBeginCall(const FunctionDecl *Func) {
-  const auto *IdInfo = Func->getIdentifier();
-  if (!IdInfo)
-    return false;
-  return IdInfo->getName().endswith_lower("begin");
-}
-
-bool isEndCall(const FunctionDecl *Func) {
-  const auto *IdInfo = Func->getIdentifier();
-  if (!IdInfo)
-    return false;
-  return IdInfo->getName().endswith_lower("end");
-}
-
 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>()) {

clang/lib/StaticAnalyzer/Checkers/Iterator.h

ProgramStateRef createIteratorPosition(ProgramStateRef State, const SVal &Val,
                                        const LocationContext *LCtx,
                                        unsigned blockCount);
 ProgramStateRef advancePosition(ProgramStateRef State,
                                 const SVal &Iter,
                                 OverloadedOperatorKind Op,
                                 const SVal &Distance);
 ProgramStateRef assumeNoOverflow(ProgramStateRef State, SymbolRef Sym,
                                  long Scale);
+
+// Returns states with comparison results assumed to `true` and `false`. If
+// only one of them is possible then the second value of the pair is `nullptr`.
+// If none is possible then both values are `nullptr`.
+std::pair<ProgramStateRef, ProgramStateRef>
+assumeComparison(ProgramStateRef State, SymbolRef Sym1, SymbolRef Sym2,
+                 DefinedSVal RetVal, OverloadedOperatorKind Op);
+
 bool compare(ProgramStateRef State, SymbolRef Sym1, SymbolRef Sym2,
              BinaryOperator::Opcode Opc);
 bool compare(ProgramStateRef State, NonLoc NL1, NonLoc NL2,
              BinaryOperator::Opcode Opc);
 
 // Returns the value of the iterator argument if it non-class value (a pointer
 // or a reference). Otherwise it returns the iterator parameter location (see
 // CallEvent::getParameterLocation()).

clang/lib/StaticAnalyzer/Checkers/Iterator.cpp

 #include "clang/StaticAnalyzer/Core/PathSensitive/CallEvent.h"
 
 #include "Iterator.h"
 
 namespace clang {
 namespace ento {
 namespace iterator {
 
+ProgramStateRef relateSymbols(ProgramStateRef State, SymbolRef Sym1,
+                              SymbolRef Sym2, bool Equal);
+
 bool isIteratorType(const QualType &Type) {
   if (Type->isPointerType())
     return true;
 
   const auto *CRD = Type->getUnqualifiedDesugaredType()->getAsCXXRecordDecl();
   return isIterator(CRD);
 }
 
+static bool hasOperator(const CXXRecordDecl *CRD, OverloadedOperatorKind Op,
+                        unsigned NumParams) {
+  for (const auto *Method : CRD->methods()) {
+    if (!Method->isOverloadedOperator())
+      continue;
+
+    if (Method->getOverloadedOperator() == Op &&
+        Method->getNumParams() == NumParams)
+      return true;
+  }
+
+  for (auto Base : CRD->bases()) {
+    const auto *BaseCRD =
+      Base.getType()->getUnqualifiedDesugaredType()->getAsCXXRecordDecl();
+
+    if (BaseCRD && hasOperator(BaseCRD, Op, NumParams))
+      return true;
+  }
+
+  return false;
+}
+
 bool isIterator(const CXXRecordDecl *CRD) {
   if (!CRD)
     return false;
 
   const auto Name = CRD->getName();
   if (!(Name.endswith_lower("iterator") || Name.endswith_lower("iter") ||
         Name.endswith_lower("it")))
     return false;
 
-  bool HasCopyCtor = false, HasCopyAssign = true, HasDtor = false,
-       HasPreIncrOp = false, HasPostIncrOp = false, HasDerefOp = false;
-  for (const auto *Method : CRD->methods()) {
-    if (const auto *Ctor = dyn_cast<CXXConstructorDecl>(Method)) {
-      if (Ctor->isCopyConstructor()) {
-        HasCopyCtor = !Ctor->isDeleted() && Ctor->getAccess() == AS_public;
-      }
-      continue;
-    }
-    if (const auto *Dtor = dyn_cast<CXXDestructorDecl>(Method)) {
-      HasDtor = !Dtor->isDeleted() && Dtor->getAccess() == AS_public;
-      continue;
-    }
-    if (Method->isCopyAssignmentOperator()) {
-      HasCopyAssign = !Method->isDeleted() && Method->getAccess() == AS_public;
-      continue;
-    }
-    if (!Method->isOverloadedOperator())
-      continue;
-    const auto OPK = Method->getOverloadedOperator();
-    if (OPK == OO_PlusPlus) {
-      HasPreIncrOp = HasPreIncrOp || (Method->getNumParams() == 0);
-      HasPostIncrOp = HasPostIncrOp || (Method->getNumParams() == 1);
-      continue;
-    }
-    if (OPK == OO_Star) {
-      HasDerefOp = (Method->getNumParams() == 0);
-      continue;
-    }
-  }
+  if ((!CRD->hasSimpleCopyConstructor() &&
+       !CRD->hasUserDeclaredCopyConstructor()) || 
+      (!CRD->hasSimpleCopyAssignment() &&
+       !CRD->hasUserDeclaredCopyAssignment()) ||
+      (!CRD->hasSimpleDestructor() &&
+       !CRD->hasUserDeclaredDestructor()))
+    return false;
+
+  // Operator Prefix ++
+  if (!hasOperator(CRD, OO_PlusPlus, 0))
+    return false;
+
+  // Operator Postfix ++
+  if (!hasOperator(CRD, OO_PlusPlus, 1))
+    return false;
 
-  return HasCopyCtor && HasCopyAssign && HasDtor && HasPreIncrOp &&
-         HasPostIncrOp && HasDerefOp;
+  // Operator *
+  if (!hasOperator(CRD, OO_Star, 0))
+    return false;
+
+  return true;
 }
 
 bool isComparisonOperator(OverloadedOperatorKind OK) {
   return OK == OO_EqualEqual || OK == OO_ExclaimEqual || OK == OO_Less ||
          OK == OO_LessEqual || OK == OO_Greater || OK == OO_GreaterEqual;
 }
 
 bool isInsertCall(const FunctionDecl *Func) {
if (auto DV = IsCappedFromBelow.getAs<DefinedSVal>()) {
     NewState = NewState->assume(*DV, true);
     if (!NewState)
       return State;
   }
 
   return NewState;
 }
 
+std::pair<ProgramStateRef, ProgramStateRef>
+assumeComparison(ProgramStateRef State, SymbolRef Sym1, SymbolRef Sym2,
+                 DefinedSVal RetVal, OverloadedOperatorKind Op) {
+  assert(CXXOperatorCallExpr::isComparisonOp(Op) &&
+         "`Op` must be a comparison operator");
+  if (const auto TruthVal = RetVal.getAs<nonloc::ConcreteInt>()) {
+    State = relateSymbols(State, Sym1, Sym2,
+                          (Op == OO_EqualEqual) == TruthVal->getValue());
+    return std::make_pair(State, nullptr);
+  }
+
+  ProgramStateRef StateTrue =
+    relateSymbols(State, Sym1, Sym2, Op == OO_EqualEqual);
+  ProgramStateRef StateFalse =
+    relateSymbols(State, Sym1, Sym2, Op != OO_EqualEqual);
+
+  if (StateTrue)
+    StateTrue = StateTrue->assume(RetVal, true);
+  if (StateFalse)
+    StateFalse = StateFalse->assume(RetVal, false);
+
+  return std::make_pair(StateTrue, StateFalse);
+}
+
+ProgramStateRef relateSymbols(ProgramStateRef State, SymbolRef Sym1,
+                              SymbolRef Sym2, bool Equal) {
+  auto &SVB = State->getStateManager().getSValBuilder();
+
+  // FIXME: This code should be reworked as follows:
+  // 1. Subtract the operands using evalBinOp().
+  // 2. Assume that the result doesn't overflow.
+  // 3. Compare the result to 0.
+  // 4. Assume the result of the comparison.
+  const auto comparison =
+    SVB.evalBinOp(State, BO_EQ, nonloc::SymbolVal(Sym1),
+                  nonloc::SymbolVal(Sym2), SVB.getConditionType());
+
+  assert(comparison.getAs<DefinedSVal>() &&
+    "Symbol comparison must be a `DefinedSVal`");
+
+  auto NewState = State->assume(comparison.castAs<DefinedSVal>(), Equal);
+  if (!NewState)
+    return nullptr;
+
+  if (const auto CompSym = comparison.getAsSymbol()) {
+    assert(isa<SymIntExpr>(CompSym) &&
+           "Symbol comparison must be a `SymIntExpr`");
+    assert(BinaryOperator::isComparisonOp(
+               cast<SymIntExpr>(CompSym)->getOpcode()) &&
+           "Symbol comparison must be a comparison");
+    return assumeNoOverflow(NewState, cast<SymIntExpr>(CompSym)->getLHS(), 2);
+  }
+
+  return NewState;
+}
+
 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();

clang/lib/StaticAnalyzer/Checkers/IteratorModeling.cpp

public:
   void checkPostStmt(const DeclStmt *DS, CheckerContext &C) const;
   void checkLiveSymbols(ProgramStateRef State, SymbolReaper &SR) const;
   void checkDeadSymbols(SymbolReaper &SR, CheckerContext &C) const;
 };
 
 bool isSimpleComparisonOperator(OverloadedOperatorKind OK);
 bool isSimpleComparisonOperator(BinaryOperatorKind OK);
 ProgramStateRef removeIteratorPosition(ProgramStateRef State, SVal Val);
-ProgramStateRef relateSymbols(ProgramStateRef State, SymbolRef Sym1,
-                              SymbolRef Sym2, bool Equal);
 const ExplodedNode *findCallEnter(const ExplodedNode *Node, const Expr *Call);
 
 } // namespace
 
 void IteratorModeling::checkPostCall(const CallEvent &Call,
                                      CheckerContext &C) const {
   // Record new iterator positions and iterator position changes
   const auto *Func = dyn_cast_or_null<FunctionDecl>(Call.getDecl());
void IteratorModeling::handleComparison(CheckerContext &C, const Expr *CE,
   // We cannot make assumptions on `UnknownVal`. Let us conjure a symbol
   // instead.
   if (RetVal.isUnknown()) {
     auto &SymMgr = C.getSymbolManager();
     auto *LCtx = C.getLocationContext();
     RetVal = nonloc::SymbolVal(SymMgr.conjureSymbol(
         CE, LCtx, C.getASTContext().BoolTy, C.blockCount()));
     State = State->BindExpr(CE, LCtx, RetVal);
   }
 
-  processComparison(C, State, LPos->getOffset(), RPos->getOffset(), RetVal, Op);
-}
+  if (const auto DefRetVal = RetVal.getAs<DefinedSVal>()) {
+    ProgramStateRef StateEqual, StateNonEqual;
+    std::tie(StateEqual, StateNonEqual) =
+      assumeComparison(State, LPos->getOffset(), RPos->getOffset(), *DefRetVal,
+                       Op);
 
-void IteratorModeling::processComparison(CheckerContext &C,
-                                         ProgramStateRef State, SymbolRef Sym1,
-                                         SymbolRef Sym2, SVal RetVal,
-                                         OverloadedOperatorKind Op) const {
-  if (const auto TruthVal = RetVal.getAs<nonloc::ConcreteInt>()) {
-    if ((State = relateSymbols(State, Sym1, Sym2,
-                              (Op == OO_EqualEqual) ==
-                               (TruthVal->getValue() != 0)))) {
-      C.addTransition(State);
-    } else {
+    if (!StateEqual && !StateNonEqual) {
       C.generateSink(State, C.getPredecessor());
-    }
       return;
     }
 
-  const auto ConditionVal = RetVal.getAs<DefinedSVal>();
-  if (!ConditionVal)
-    return;
+    if (StateEqual)
+      C.addTransition(StateEqual);
 
-  if (auto StateTrue = relateSymbols(State, Sym1, Sym2, Op == OO_EqualEqual)) {
-    StateTrue = StateTrue->assume(*ConditionVal, true);
-    C.addTransition(StateTrue);
+    if (StateNonEqual)
+      C.addTransition(StateNonEqual);
   }
 
-  if (auto StateFalse = relateSymbols(State, Sym1, Sym2, Op != OO_EqualEqual)) {
-    StateFalse = StateFalse->assume(*ConditionVal, false);
-    C.addTransition(StateFalse);
-  }
 }
 
 void IteratorModeling::handleIncrement(CheckerContext &C, SVal RetVal,
                                        SVal Iter, bool Postfix) const {
   // Increment the symbolic expressions which represents the position of the
   // iterator
   auto State = C.getState();
   auto &BVF = C.getSymbolManager().getBasicVals();
 
if (auto Reg = Val.getAsRegion()) {
     Reg = Reg->getMostDerivedObjectRegion();
     return State->remove<IteratorRegionMap>(Reg);
   } else if (const auto Sym = Val.getAsSymbol()) {
     return State->remove<IteratorSymbolMap>(Sym);
   }
   return State;
 }
 
-ProgramStateRef relateSymbols(ProgramStateRef State, SymbolRef Sym1,
-                              SymbolRef Sym2, bool Equal) {
-  auto &SVB = State->getStateManager().getSValBuilder();
-
-  // FIXME: This code should be reworked as follows:
-  // 1. Subtract the operands using evalBinOp().
-  // 2. Assume that the result doesn't overflow.
-  // 3. Compare the result to 0.
-  // 4. Assume the result of the comparison.
-  const auto comparison =
-    SVB.evalBinOp(State, BO_EQ, nonloc::SymbolVal(Sym1),
-                  nonloc::SymbolVal(Sym2), SVB.getConditionType());
-
-  assert(comparison.getAs<DefinedSVal>() &&
-    "Symbol comparison must be a `DefinedSVal`");
-
-  auto NewState = State->assume(comparison.castAs<DefinedSVal>(), Equal);
-  if (!NewState)
-    return nullptr;
-
-  if (const auto CompSym = comparison.getAsSymbol()) {
-    assert(isa<SymIntExpr>(CompSym) &&
-           "Symbol comparison must be a `SymIntExpr`");
-    assert(BinaryOperator::isComparisonOp(
-               cast<SymIntExpr>(CompSym)->getOpcode()) &&
-           "Symbol comparison must be a comparison");
-    return assumeNoOverflow(NewState, cast<SymIntExpr>(CompSym)->getLHS(), 2);
-  }
-
-  return NewState;
-}
-
 const ExplodedNode *findCallEnter(const ExplodedNode *Node, const Expr *Call) {
   while (Node) {
     ProgramPoint PP = Node->getLocation();
     if (auto Enter = PP.getAs<CallEnter>()) {
       if (Enter->getCallExpr() == Call)
         break;
     }
 

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

public:
     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); }
     T& front() { return *begin(); }
     const T& front() const { return *begin(); }
     T& back() { return *(end() - 1); }
     const T& back() const { return *(end() - 1); }
+
+    bool empty() const;
   };
   
   template<typename T>
   class list {
     struct __item {
       T data;
       __item *prev, *next;
     } *_start, *_finish;
public:
     iterator end() { return iterator(_finish); }
     const_iterator end() const { return const_iterator(_finish); }
     const_iterator cend() const { return const_iterator(_finish); }
 
     T& front() { return *begin(); }
     const T& front() const { return *begin(); }
     T& back() { return *--end(); }
     const T& back() const { return *--end(); }
+
+    bool empty() const;
   };
 
   template<typename T>
   class deque {
     T *_start;
     T *_finish;
     T *_end_of_storage;
 
public:
     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); }
     T& front() { return *begin(); }
     const T& front() const { return *begin(); }
     T& back() { return *(end() - 1); }
     const T& back() const { return *(end() - 1); }
+
+    bool empty() const;
   };
 
   template<typename T>
   class forward_list {
     struct __item {
       T data;
       __item *next;
     } *_start;
public:
     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(); }
 
     T& front() { return *begin(); }
     const T& front() const { return *begin(); }
+
+    bool empty() const;
   };
 
   template <typename CharT>
   class basic_string {
   public:
     basic_string();
     basic_string(const CharT *s);
 

clang/test/Analysis/container-modeling.cpp

 template <typename Container>
 long clang_analyzer_container_end(const Container&);
 
 void clang_analyzer_denote(long, const char*);
 void clang_analyzer_express(long);
 void clang_analyzer_eval(bool);
 void clang_analyzer_warnIfReached();
 
+extern void __assert_fail (__const char *__assertion, __const char *__file,
+    unsigned int __line, __const char *__function)
+     __attribute__ ((__noreturn__));
+#define assert(expr) \
+  ((expr)  ? (void)(0)  : __assert_fail (#expr, __FILE__, __LINE__, __func__))
+
 void begin(const std::vector<int> &V) {
   V.begin();
 
   clang_analyzer_denote(clang_analyzer_container_begin(V), "$V.begin()");
   clang_analyzer_express(clang_analyzer_container_begin(V)); // expected-warning{{$V.begin()}}
                                                              // expected-note@-1{{$V.begin()}}
 }
 
void move_assignment(std::vector<int> &V1, std::vector<int> &V2) {
   clang_analyzer_eval(clang_analyzer_container_begin(V1) == B2); // expected-warning{{TRUE}}
                                                                  // expected-note@-1{{TRUE}}
   clang_analyzer_eval(clang_analyzer_container_end(V2) == E2); // expected-warning{{TRUE}}
                                                                // expected-note@-1{{TRUE}}
 }
 
 ////////////////////////////////////////////////////////////////////////////////
 ///
+/// C O N T A I N E R   C A P A C I T Y
+///
+////////////////////////////////////////////////////////////////////////////////
+
+/// empty()
+
+void empty(const std::vector<int> &V) {
+  for (auto n: V) {}
+  clang_analyzer_eval(clang_analyzer_container_begin(V) ==
+                      clang_analyzer_container_end(V));
+  // expected-warning@-2{{TRUE}} expected-warning@-2{{FALSE}}
+  // expected-note@-3   {{TRUE}} expected-note@-3   {{FALSE}}
+}
+
+void non_empty1(const std::vector<int> &V) {
+  assert(!V.empty()); // expected-note{{'?' condition is true}}
+  for (auto n: V) {}
+  clang_analyzer_eval(clang_analyzer_container_begin(V) ==
+                      clang_analyzer_container_end(V));
+  // expected-warning@-2{{FALSE}}
+  // expected-note@-3   {{FALSE}}
+}
+
+void non_empty2(const std::vector<int> &V) {
+  for (auto n: V) {}
+  assert(!V.empty()); // expected-note{{'?' condition is true}}
+  clang_analyzer_eval(clang_analyzer_container_begin(V) ==
+                      clang_analyzer_container_end(V));
+  // expected-warning@-2{{FALSE}}
+  // expected-note@-3   {{FALSE}}
+}
+
+////////////////////////////////////////////////////////////////////////////////
+///
 /// C O N T A I N E R   M O D I F I E R S
 ///
 ////////////////////////////////////////////////////////////////////////////////
 
 /// push_back()
 ///
 /// Design decision: extends containers to the ->BACK-> (i.e. the
 /// past-the-end position of the container is incremented).

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

clang/test/Analysis/smart-ptr-text-output.cpp

void derefOnSwappedNullPtr() {
   (*P).foo(); // expected-warning {{Dereference of null smart pointer 'P' [alpha.cplusplus.SmartPtr]}}
   // expected-note@-1{{Dereference of null smart pointer 'P'}}
 }
 
 // FIXME: Fix this test when "std::swap" is modeled seperately.
 void derefOnStdSwappedNullPtr() {
   std::unique_ptr<A> P; // expected-note {{Default constructed smart pointer 'P' is null}}
   std::unique_ptr<A> PNull; // expected-note {{Default constructed smart pointer 'PNull' is null}}
-  std::swap(P, PNull); // expected-note@Inputs/system-header-simulator-cxx.h:979 {{Swapped null smart pointer 'PNull' with smart pointer 'P'}}
+  std::swap(P, PNull); // expected-note@Inputs/system-header-simulator-cxx.h:987 {{Swapped null smart pointer 'PNull' with smart pointer 'P'}}
   // expected-note@-1 {{Calling 'swap<A>'}}
   // expected-note@-2 {{Returning from 'swap<A>'}}
   P->foo(); // expected-warning {{Dereference of null smart pointer 'P' [alpha.cplusplus.SmartPtr]}}
   // expected-note@-1{{Dereference of null smart pointer 'P'}}
 }
 
 struct StructWithSmartPtr { // expected-note {{Default constructed smart pointer 'S.P' is null}}
   std::unique_ptr<A> P;