[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

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

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 NoItParamFn *Handler0 = NoIterParamFunctions.lookup(Call);
-      if (Handler0) {
-        (this->**Handler0)(C, InstCall->getCXXThisVal(),
-                           InstCall->getCXXThisExpr());
-        return;
-      }
+  } else if (const auto *InstCall = dyn_cast<CXXInstanceCall>(&Call)) {
+    const auto *OrigExpr = Call.getOriginExpr();
+    if (!OrigExpr)
+      return;
+
+    SVal RetVal = Call.getReturnValue();
+    if (isIteratorType(Call.getResultType()))
+      RetVal = getReturnIterator(Call);
+
+    const ZeroItParamFn *Handler0 = ZeroIterParamFunctions.lookup(Call);
+      (this->**Handler0)(C, OrigExpr, InstCall->getCXXThisExpr(),
+                         InstCall->getCXXThisVal(), RetVal);
 
-      const OneItParamFn *Handler1 = OneIterParamFunctions.lookup(Call);
-      if (Handler1) {
-        (this->**Handler1)(C, InstCall->getCXXThisVal(), Call.getArgSVal(0));
-        return;
-      }
+      SVal Arg0 = getIteratorArg(Call, 0, C.blockCount());
+      (this->**Handler1)(C, OrigExpr, InstCall->getCXXThisExpr(),
+                         InstCall->getCXXThisVal(), Arg0, RetVal);
 
-      const TwoItParamFn *Handler2 = TwoIterParamFunctions.lookup(Call);
-      if (Handler2) {
-        (this->**Handler2)(C, InstCall->getCXXThisVal(), Call.getArgSVal(0),
-                           Call.getArgSVal(1));
-        return;
-      }
-
-      const auto *OrigExpr = Call.getOriginExpr();
-      if (!OrigExpr)
-        return;
-
-      if (isBeginCall(Func)) {
-        handleBegin(C, OrigExpr, Call.getReturnValue(),
-                    InstCall->getCXXThisVal());
-        return;
-      }
-
-      if (isEndCall(Func)) {
-        handleEnd(C, OrigExpr, Call.getReturnValue(),
-                  InstCall->getCXXThisVal());
-        return;
-      }
-    }
+      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);
   }
 }
 
 void ContainerModeling::checkLiveSymbols(ProgramStateRef State,
                                          SymbolReaper &SR) const {
   // Keep symbolic expressions of container begins and ends alive
   auto ContMap = State->get<ContainerMap>();
   for (const auto &Cont : ContMap) {
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/InvalidatedIteratorChecker.cpp

 class InvalidatedIteratorChecker
   : public Checker<check::PreCall, check::PreStmt<UnaryOperator>,
                    check::PreStmt<BinaryOperator>,
                    check::PreStmt<ArraySubscriptExpr>,
                    check::PreStmt<MemberExpr>> {
 
   std::unique_ptr<BugType> InvalidatedBugType;
 
-  void verifyAccess(CheckerContext &C, const SVal &Val) const;
-  void reportBug(const StringRef &Message, const SVal &Val,
-                 CheckerContext &C, ExplodedNode *ErrNode) const;
+  void verifyAccess(CheckerContext &C, SVal Val) const;
+  void reportBug(const StringRef &Message, SVal Val, CheckerContext &C,
+                 ExplodedNode *ErrNode) const;
 public:
   InvalidatedIteratorChecker();
 
   void checkPreCall(const CallEvent &Call, CheckerContext &C) const;
   void checkPreStmt(const UnaryOperator *UO, CheckerContext &C) const;
   void checkPreStmt(const BinaryOperator *BO, CheckerContext &C) const;
   void checkPreStmt(const ArraySubscriptExpr *ASE, CheckerContext &C) const;
   void checkPreStmt(const MemberExpr *ME, CheckerContext &C) const;
if (!Func)
     return;
 
   if (Func->isOverloadedOperator() &&
       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));
+      SVal Arg0 = getIteratorArg(Call, 0, C.blockCount());
+      verifyAccess(C, Arg0);
     }
   }
 }
 
 void InvalidatedIteratorChecker::checkPreStmt(const UnaryOperator *UO,
                                               CheckerContext &C) const {
   if (isa<CXXThisExpr>(UO->getSubExpr()))
     return;
void InvalidatedIteratorChecker::checkPreStmt(const MemberExpr *ME,
   if (!ME->isArrow() || ME->isImplicitAccess())
     return;
 
   ProgramStateRef State = C.getState();
   SVal BaseVal = State->getSVal(ME->getBase(), C.getLocationContext());
   verifyAccess(C, BaseVal);
 }
 
-void InvalidatedIteratorChecker::verifyAccess(CheckerContext &C, const SVal &Val) const {
+void InvalidatedIteratorChecker::verifyAccess(CheckerContext &C,
+                                              SVal Val) const {
   auto State = C.getState();
   const auto *Pos = getIteratorPosition(State, Val);
   if (Pos && !Pos->isValid()) {
     auto *N = C.generateErrorNode(State);
     if (!N) {
       return;
     }
     reportBug("Invalidated iterator accessed.", Val, C, N);
   }
 }
 
 void InvalidatedIteratorChecker::reportBug(const StringRef &Message,
-                                           const SVal &Val, CheckerContext &C,
+                                           SVal Val, CheckerContext &C,
                                            ExplodedNode *ErrNode) const {
   auto R = std::make_unique<PathSensitiveBugReport>(*InvalidatedBugType,
                                                     Message, ErrNode);
   R->markInteresting(Val);
   C.emitReport(std::move(R));
 }
 
 void ento::registerInvalidatedIteratorChecker(CheckerManager &mgr) {
   mgr.registerChecker<InvalidatedIteratorChecker>();
 }
 
 bool ento::shouldRegisterInvalidatedIteratorChecker(const CheckerManager &mgr) {
   return true;
 }

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()).
+SVal getIteratorArg(const CallEvent &Call, unsigned Index, unsigned BlockCount);
+
+// If the call returns an class instance iterator by value then this function
+// retrieves and returns it from the construction context of the call.
+// Otherwise (for non-class types) it simply returns the return value of the
+// call.
+SVal getReturnIterator(const CallEvent &Call);
+
 } // namespace iterator
 } // namespace ento
 } // namespace clang
 
 #endif

clang/lib/StaticAnalyzer/Checkers/Iterator.cpp

 //=== Iterator.cpp - Common functions for iterator checkers. -------*- C++ -*-//
 //
 // Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.
 // See https://llvm.org/LICENSE.txt for license information.
 // SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception
 //
 //===----------------------------------------------------------------------===//
 //
 // Defines common functions to be used by the itertor checkers .
 //
 //===----------------------------------------------------------------------===//
 
+#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;
 
-  return HasCopyCtor && HasCopyAssign && HasDtor && HasPreIncrOp &&
-         HasPostIncrOp && HasDerefOp;
+  // Operator Postfix ++
+  if (!hasOperator(CRD, OO_PlusPlus, 1))
+    return false;
+
+  // 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) {

 
 const IteratorPosition *getIteratorPosition(ProgramStateRef State,
                                             const SVal &Val) {
   if (auto Reg = Val.getAsRegion()) {
     Reg = Reg->getMostDerivedObjectRegion();
     return State->get<IteratorRegionMap>(Reg);
   } else if (const auto Sym = Val.getAsSymbol()) {
     return State->get<IteratorSymbolMap>(Sym);
-  } else if (const auto LCVal = Val.getAs<nonloc::LazyCompoundVal>()) {
-    return State->get<IteratorRegionMap>(LCVal->getRegion());
   }
   return nullptr;
 }
 
 ProgramStateRef setIteratorPosition(ProgramStateRef State, const SVal &Val,
                                     const IteratorPosition &Pos) {
   if (auto Reg = Val.getAsRegion()) {
     Reg = Reg->getMostDerivedObjectRegion();
     return State->set<IteratorRegionMap>(Reg, Pos);
   } else if (const auto Sym = Val.getAsSymbol()) {
     return State->set<IteratorSymbolMap>(Sym, Pos);
-  } else if (const auto LCVal = Val.getAs<nonloc::LazyCompoundVal>()) {
-    return State->set<IteratorRegionMap>(LCVal->getRegion(), Pos);
   }
-  return nullptr;
+  return State;
 }
 
 ProgramStateRef createIteratorPosition(ProgramStateRef State, const SVal &Val,
                                        const MemRegion *Cont, const Stmt* S,
                                        const LocationContext *LCtx,
                                        unsigned blockCount) {
   auto &StateMgr = State->getStateManager();
   auto &SymMgr = StateMgr.getSymbolManager();
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();
 
   const auto comparison =
     SVB.evalBinOp(State, Opc, NL1, NL2, SVB.getConditionType());
 
   assert(comparison.getAs<DefinedSVal>() &&
     "Symbol comparison must be a `DefinedSVal`");
 
   return !State->assume(comparison.castAs<DefinedSVal>(), false);
 }
 
+SVal getIteratorArg(const CallEvent& Call, unsigned Index,
+                    unsigned BlockCount) {
+  SVal Arg = Call.getArgSVal(Index);
+  const Expr *ArgExpr = Call.getArgExpr(Index);
+
+  if (ArgExpr->getValueKind() != VK_RValue)
+    return Arg;
+
+  if (!ArgExpr->getType().getDesugaredType(
+          Call.getState()->getStateManager().getContext())->isRecordType())
+    return Arg;
+
+  return loc::MemRegionVal(Call.getParameterLocation(Index, BlockCount));
+}
+
+SVal getReturnIterator(const CallEvent &Call) {
+  Optional<SVal> RetValUnderConstr = Call.getReturnValueUnderConstruction();
+  if (RetValUnderConstr.hasValue())
+    return *RetValUnderConstr;
+
+  return Call.getReturnValue();
+}
+
 } // namespace iterator
 } // namespace ento
 } // namespace clang

clang/lib/StaticAnalyzer/Checkers/IteratorModeling.cpp

 using namespace clang;
 using namespace ento;
 using namespace iterator;
 
 namespace {
 
 class IteratorModeling
     : public Checker<check::PostCall, check::PostStmt<UnaryOperator>,
-                     check::PostStmt<BinaryOperator>,
-                     check::PostStmt<MaterializeTemporaryExpr>,
-                     check::Bind, check::LiveSymbols, check::DeadSymbols> {
+                     check::PostStmt<BinaryOperator>, check::Bind,
+                     check::LiveSymbols, check::DeadSymbols> {
 
   using AdvanceFn = void (IteratorModeling::*)(CheckerContext &, const Expr *,
                                                SVal, SVal, SVal) const;
 
   void handleOverloadedOperator(CheckerContext &C, const CallEvent &Call,
                                 OverloadedOperatorKind Op) const;
   void handleAdvanceLikeFunction(CheckerContext &C, const CallEvent &Call,
                                  const Expr *OrigExpr,
                                  const AdvanceFn *Handler) const;
 
   void handleComparison(CheckerContext &C, const Expr *CE, SVal RetVal,
-                        const SVal &LVal, const SVal &RVal,
-                        OverloadedOperatorKind Op) const;
+                        SVal LVal, SVal RVal, OverloadedOperatorKind Op) const;
   void processComparison(CheckerContext &C, ProgramStateRef State,
-                         SymbolRef Sym1, SymbolRef Sym2, const SVal &RetVal,
+                         SymbolRef Sym1, SymbolRef Sym2, SVal RetVal,
                          OverloadedOperatorKind Op) const;
-  void handleIncrement(CheckerContext &C, const SVal &RetVal, const SVal &Iter,
-                       bool Postfix) const;
-  void handleDecrement(CheckerContext &C, const SVal &RetVal, const SVal &Iter,
-                       bool Postfix) const;
+  void handleIncrement(CheckerContext &C, SVal RetVal,
+                       SVal Iter, bool Postfix) const;
+  void handleDecrement(CheckerContext &C, SVal RetVal,
+                       SVal Iter, bool Postfix) const;
   void handleRandomIncrOrDecr(CheckerContext &C, const Expr *CE,
-                              OverloadedOperatorKind Op, const SVal &RetVal,
-                              const SVal &Iterator, const SVal &Amount) const;
+                              OverloadedOperatorKind Op, SVal RetVal,
+                              SVal Iterator, SVal Amount) const;
   void handlePtrIncrOrDecr(CheckerContext &C, const Expr *Iterator,
                            OverloadedOperatorKind OK, SVal Offset) const;
-  void handleAdvance(CheckerContext &C, const Expr *CE, SVal RetVal, SVal Iter,
-                     SVal Amount) const;
-  void handlePrev(CheckerContext &C, const Expr *CE, SVal RetVal, SVal Iter,
-                  SVal Amount) const;
-  void handleNext(CheckerContext &C, const Expr *CE, SVal RetVal, SVal Iter,
-                  SVal Amount) const;
-  void assignToContainer(CheckerContext &C, const Expr *CE, const SVal &RetVal,
+  void handleAdvance(CheckerContext &C, const Expr *CE, SVal RetVal,
+                     SVal Iter, SVal Amount) const;
+  void handlePrev(CheckerContext &C, const Expr *CE, SVal RetVal,
+                  SVal Iter, SVal Amount) const;
+  void handleNext(CheckerContext &C, const Expr *CE, SVal RetVal,
+                  SVal Iter, SVal Amount) const;
+  void assignToContainer(CheckerContext &C, const Expr *CE, SVal RetVal,
                          const MemRegion *Cont) const;
   bool noChangeInAdvance(CheckerContext &C, SVal Iter, const Expr *CE) const;
   void printState(raw_ostream &Out, ProgramStateRef State, const char *NL,
                   const char *Sep) const override;
 
   // std::advance, std::prev & std::next
   CallDescriptionMap<AdvanceFn> AdvanceLikeFunctions = {
       // template<class InputIt, class Distance>
public:
   IteratorModeling() = default;
 
   void checkPostCall(const CallEvent &Call, CheckerContext &C) const;
   void checkBind(SVal Loc, SVal Val, const Stmt *S, CheckerContext &C) const;
   void checkPostStmt(const UnaryOperator *UO, CheckerContext &C) const;
   void checkPostStmt(const BinaryOperator *BO, CheckerContext &C) const;
   void checkPostStmt(const CXXConstructExpr *CCE, CheckerContext &C) const;
   void checkPostStmt(const DeclStmt *DS, CheckerContext &C) const;
-  void checkPostStmt(const MaterializeTemporaryExpr *MTE,
-                     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, const SVal &Val);
-ProgramStateRef relateSymbols(ProgramStateRef State, SymbolRef Sym1,
-                              SymbolRef Sym2, bool Equal);
-bool isBoundThroughLazyCompoundVal(const Environment &Env,
-                                   const MemRegion *Reg);
+ProgramStateRef removeIteratorPosition(ProgramStateRef State, SVal Val);
 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::checkPostCall(const CallEvent &Call,
   }
 
   if (!isIteratorType(Call.getResultType()))
     return;
 
   auto State = C.getState();
 
   // Already bound to container?
-  if (getIteratorPosition(State, Call.getReturnValue()))
+  SVal RetVal = getReturnIterator(Call);
+  if (getIteratorPosition(State, RetVal))
     return;
 
   // Copy-like and move constructors
   if (isa<CXXConstructorCall>(&Call) && Call.getNumArgs() == 1) {
-    if (const auto *Pos = getIteratorPosition(State, Call.getArgSVal(0))) {
-      State = setIteratorPosition(State, Call.getReturnValue(), *Pos);
+    SVal Arg = getIteratorArg(Call, 0, C.blockCount());
+    if (const auto *Pos = getIteratorPosition(State, Arg)) {
+      State = setIteratorPosition(State, RetVal, *Pos);
       if (cast<CXXConstructorDecl>(Func)->isMoveConstructor()) {
-        State = removeIteratorPosition(State, Call.getArgSVal(0));
+        State = removeIteratorPosition(State, Arg);
       }
       C.addTransition(State);
       return;
     }
   }
 
   // Assumption: if return value is an iterator which is not yet bound to a
   //             container, then look for the first iterator argument of the
   //             same type as the return value and bind the return value to
   //             the same container. This approach works for STL algorithms.
   // FIXME: Add a more conservative mode
   for (unsigned i = 0; i < Call.getNumArgs(); ++i) {
     if (isIteratorType(Call.getArgExpr(i)->getType()) &&
         Call.getArgExpr(i)->getType().getNonReferenceType().getDesugaredType(
             C.getASTContext()).getTypePtr() ==
         Call.getResultType().getDesugaredType(C.getASTContext()).getTypePtr()) {
       if (const auto *Pos = getIteratorPosition(State, Call.getArgSVal(i))) {
-        assignToContainer(C, OrigExpr, Call.getReturnValue(),
-                          Pos->getContainer());
+        assignToContainer(C, OrigExpr, RetVal, Pos->getContainer());
         return;
       }
     }
   }
 }
 
 void IteratorModeling::checkBind(SVal Loc, SVal Val, const Stmt *S,
                                  CheckerContext &C) const {
   auto State = C.getState();
+  if (Val.getAs<nonloc::LazyCompoundVal>())
+    return;
+
   const auto *Pos = getIteratorPosition(State, Val);
   if (Pos) {
     State = setIteratorPosition(State, Loc, *Pos);
     C.addTransition(State);
   } else {
     const auto *OldPos = getIteratorPosition(State, Loc);
     if (OldPos) {
       State = removeIteratorPosition(State, Loc);
if (isSimpleComparisonOperator(BO->getOpcode())) {
     if (!AmountExpr->getType()->isIntegralOrEnumerationType())
       return;
     const SVal &AmountVal = IsIterOnLHS ? RVal : LVal;
     handlePtrIncrOrDecr(C, IterExpr, BinaryOperator::getOverloadedOperator(OK),
                         AmountVal);
   }
 }
 
-void IteratorModeling::checkPostStmt(const MaterializeTemporaryExpr *MTE,
-                                     CheckerContext &C) const {
-  /* Transfer iterator state to temporary objects */
-  auto State = C.getState();
-  const auto *Pos = getIteratorPosition(State, C.getSVal(MTE->getSubExpr()));
-  if (!Pos)
-    return;
-  State = setIteratorPosition(State, C.getSVal(MTE), *Pos);
-  C.addTransition(State);
-}
-
 void IteratorModeling::checkLiveSymbols(ProgramStateRef State,
                                         SymbolReaper &SR) const {
   // Keep symbolic expressions of iterator positions alive
   auto RegionMap = State->get<IteratorRegionMap>();
   for (const auto &Reg : RegionMap) {
     const auto Offset = Reg.second.getOffset();
     for (auto i = Offset->symbol_begin(); i != Offset->symbol_end(); ++i)
-      if (isa<SymbolData>(*i))
+      if (isa<SymbolData>(*i)) {
         SR.markLive(*i);
       }
+  }
 
   auto SymbolMap = State->get<IteratorSymbolMap>();
   for (const auto &Sym : SymbolMap) {
     const auto Offset = Sym.second.getOffset();
     for (auto i = Offset->symbol_begin(); i != Offset->symbol_end(); ++i)
       if (isa<SymbolData>(*i))
         SR.markLive(*i);
   }
 
 }
 
 void IteratorModeling::checkDeadSymbols(SymbolReaper &SR,
                                         CheckerContext &C) const {
   // Cleanup
   auto State = C.getState();
 
   auto RegionMap = State->get<IteratorRegionMap>();
   for (const auto &Reg : RegionMap) {
     if (!SR.isLiveRegion(Reg.first)) {
-      // The region behind the `LazyCompoundVal` is often cleaned up before
-      // the `LazyCompoundVal` itself. If there are iterator positions keyed
-      // by these regions their cleanup must be deferred.
-      if (!isBoundThroughLazyCompoundVal(State->getEnvironment(), Reg.first)) {
-        State = State->remove<IteratorRegionMap>(Reg.first);
-      }
-    }
-  }
 
   auto SymbolMap = State->get<IteratorSymbolMap>();
   for (const auto &Sym : SymbolMap) {
     if (!SR.isLive(Sym.first)) {
       State = State->remove<IteratorSymbolMap>(Sym.first);
     }
   }
 
   C.addTransition(State);
 }
 
 void
 IteratorModeling::handleOverloadedOperator(CheckerContext &C,
                                            const CallEvent &Call,
                                            OverloadedOperatorKind Op) const {
-    if (isSimpleComparisonOperator(Op)) {
-      const auto *OrigExpr = Call.getOriginExpr();
-      if (!OrigExpr)
-        return;
+  const auto *OrigExpr = Call.getOriginExpr();
+  if (!OrigExpr)
+    return;
+
 
-      if (const auto *InstCall = dyn_cast<CXXInstanceCall>(&Call)) {
-        handleComparison(C, OrigExpr, Call.getReturnValue(),
-                         InstCall->getCXXThisVal(), Call.getArgSVal(0), Op);
-        return;
-      }
+    SVal Arg0 = getIteratorArg(Call, 0, C.blockCount());
+                       InstCall->getCXXThisVal(), Arg0, Op);
 
-      handleComparison(C, OrigExpr, Call.getReturnValue(), Call.getArgSVal(0),
-                         Call.getArgSVal(1), Op);
-      return;
-    } else if (isRandomIncrOrDecrOperator(Op)) {
-      const auto *OrigExpr = Call.getOriginExpr();
-      if (!OrigExpr)
-        return;
-
-      if (const auto *InstCall = dyn_cast<CXXInstanceCall>(&Call)) {
-        if (Call.getNumArgs() >= 1 &&
-              Call.getArgExpr(0)->getType()->isIntegralOrEnumerationType()) {
-          handleRandomIncrOrDecr(C, OrigExpr, Op, Call.getReturnValue(),
-                                 InstCall->getCXXThisVal(), Call.getArgSVal(0));
-          return;
-        }
-      } else if (Call.getNumArgs() >= 2) {
-        const Expr *FirstArg = Call.getArgExpr(0);
-        const Expr *SecondArg = Call.getArgExpr(1);
-        const QualType FirstType = FirstArg->getType();
-        const QualType SecondType = SecondArg->getType();
+    SVal Arg1 = getIteratorArg(Call, 1, C.blockCount());
+    handleComparison(C, OrigExpr, Call.getReturnValue(), Arg0, Arg1, Op);
+        handleRandomIncrOrDecr(C, OrigExpr, Op, getReturnIterator(Call),
 
-        if (FirstType->isIntegralOrEnumerationType() ||
-            SecondType->isIntegralOrEnumerationType()) {
-          // In case of operator+ the iterator can be either on the LHS (eg.:
-          // it + 1), or on the RHS (eg.: 1 + it). Both cases are modeled.
-          const bool IsIterFirst = FirstType->isStructureOrClassType();
-          const SVal FirstArg = Call.getArgSVal(0);
-          const SVal SecondArg = Call.getArgSVal(1);
-          const SVal &Iterator = IsIterFirst ? FirstArg : SecondArg;
-          const SVal &Amount = IsIterFirst ? SecondArg : FirstArg;
+        const SVal Iterator = getIteratorArg(Call, IsIterFirst ? 0 : 1,
+                                             C.blockCount());
+        const SVal Amount = Call.getArgSVal(IsIterFirst ? 1 : 0);
         
-          handleRandomIncrOrDecr(C, OrigExpr, Op, Call.getReturnValue(),
-                                 Iterator, Amount);
-          return;
-        }
-      }
-    } else if (isIncrementOperator(Op)) {
-      if (const auto *InstCall = dyn_cast<CXXInstanceCall>(&Call)) {
-        handleIncrement(C, Call.getReturnValue(), InstCall->getCXXThisVal(),
-                        Call.getNumArgs());
-        return;
-      }
+        handleRandomIncrOrDecr(C, OrigExpr, Op, getReturnIterator(Call),
+    } else {
+      if (Call.getNumArgs() >= 2 &&
+          Call.getArgExpr(1)->getType()->isIntegralOrEnumerationType()) {
+        SVal Arg0 = getIteratorArg(Call, 0, C.blockCount());
+        handleRandomIncrOrDecr(C, OrigExpr, Op, getReturnIterator(Call), Arg0,
+                               Call.getArgSVal(1));
+        return;
+      }
+      handleIncrement(C, getReturnIterator(Call), InstCall->getCXXThisVal(),
 
-      handleIncrement(C, Call.getReturnValue(), Call.getArgSVal(0),
-                      Call.getNumArgs());
-      return;
-    } else if (isDecrementOperator(Op)) {
-      if (const auto *InstCall = dyn_cast<CXXInstanceCall>(&Call)) {
-        handleDecrement(C, Call.getReturnValue(), InstCall->getCXXThisVal(),
-                        Call.getNumArgs());
-        return;
-      }
+    SVal Arg0 = getIteratorArg(Call, 0, C.blockCount());
+    handleIncrement(C, getReturnIterator(Call), Arg0, Call.getNumArgs());
+      handleDecrement(C, getReturnIterator(Call), InstCall->getCXXThisVal(),
 
-      handleDecrement(C, Call.getReturnValue(), Call.getArgSVal(0),
-                        Call.getNumArgs());
-      return;
-    }
+    SVal Arg0 = getIteratorArg(Call, 0, C.blockCount());
+    handleDecrement(C, getReturnIterator(Call), Arg0, Call.getNumArgs());
 }
 
 void
 IteratorModeling::handleAdvanceLikeFunction(CheckerContext &C,
                                             const CallEvent &Call,
                                             const Expr *OrigExpr,
                                             const AdvanceFn *Handler) const {
+  SVal Arg0 = getIteratorArg(Call, 0, C.blockCount());
    if (!C.wasInlined) {
-    (this->**Handler)(C, OrigExpr, Call.getReturnValue(),
-                      Call.getArgSVal(0), Call.getArgSVal(1));
+     (this->**Handler)(C, OrigExpr, getReturnIterator(Call), Arg0,
+                       Call.getArgSVal(1));
     return;
   }
 
   // If std::advance() was inlined, but a non-standard function it calls inside
   // was not, then we have to model it explicitly
   const auto *IdInfo = cast<FunctionDecl>(Call.getDecl())->getIdentifier();
   if (IdInfo) {
     if (IdInfo->getName() == "advance") {
-      if (noChangeInAdvance(C, Call.getArgSVal(0), OrigExpr)) {
-        (this->**Handler)(C, OrigExpr, Call.getReturnValue(),
-                          Call.getArgSVal(0), Call.getArgSVal(1));
+      if (noChangeInAdvance(C, Arg0, OrigExpr)) {
+        (this->**Handler)(C, OrigExpr, getReturnIterator(Call), Arg0,
+                          Call.getArgSVal(1));
       }
     }
   }
 }
 
 void IteratorModeling::handleComparison(CheckerContext &C, const Expr *CE,
-                                       SVal RetVal, const SVal &LVal,
-                                       const SVal &RVal,
+                                        SVal RetVal, SVal LVal, SVal RVal,
                                         OverloadedOperatorKind Op) const {
   // Record the operands and the operator of the comparison for the next
   // evalAssume, if the result is a symbolic expression. If it is a concrete
   // value (only one branch is possible), then transfer the state between
   // the operands according to the operator and the result
-   auto State = C.getState();
   const auto *LPos = getIteratorPosition(State, LVal);
   const auto *RPos = getIteratorPosition(State, RVal);
   const MemRegion *Cont = nullptr;
   if (LPos) {
     Cont = LPos->getContainer();
   } else if (RPos) {
     Cont = RPos->getContainer();
   }
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, const 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, const SVal &RetVal,
-                                       const SVal &Iter, bool Postfix) const {
+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();
 
   const auto *Pos = getIteratorPosition(State, Iter);
   if (!Pos)
     return;
 
   auto NewState =
     advancePosition(State, Iter, OO_Plus,
                     nonloc::ConcreteInt(BVF.getValue(llvm::APSInt::get(1))));
   assert(NewState &&
          "Advancing position by concrete int should always be successful");
 
   const auto *NewPos = getIteratorPosition(NewState, Iter);
   assert(NewPos &&
          "Iterator should have position after successful advancement");
 
   State = setIteratorPosition(State, Iter, *NewPos);
   State = setIteratorPosition(State, RetVal, Postfix ? *Pos : *NewPos);
   C.addTransition(State);
 }
 
-void IteratorModeling::handleDecrement(CheckerContext &C, const SVal &RetVal,
-                                       const SVal &Iter, bool Postfix) const {
+void IteratorModeling::handleDecrement(CheckerContext &C, SVal RetVal,
+                                       SVal Iter, bool Postfix) const {
   // Decrement the symbolic expressions which represents the position of the
   // iterator
   auto State = C.getState();
   auto &BVF = C.getSymbolManager().getBasicVals();
 
   const auto *Pos = getIteratorPosition(State, Iter);
   if (!Pos)
     return;
void IteratorModeling::handleDecrement(CheckerContext &C, SVal RetVal,
 
   State = setIteratorPosition(State, Iter, *NewPos);
   State = setIteratorPosition(State, RetVal, Postfix ? *Pos : *NewPos);
   C.addTransition(State);
 }
 
 void IteratorModeling::handleRandomIncrOrDecr(CheckerContext &C, const Expr *CE,
                                               OverloadedOperatorKind Op,
-                                              const SVal &RetVal,
-                                              const SVal &Iterator,
-                                              const SVal &Amount) const {
+                                              SVal RetVal, SVal Iterator,
+                                              SVal Amount) const {
   // Increment or decrement the symbolic expressions which represents the
   // position of the iterator
   auto State = C.getState();
 
   const auto *Pos = getIteratorPosition(State, Iterator);
   if (!Pos)
     return;
 
   const auto *Value = &Amount;
   SVal Val;
   if (auto LocAmount = Amount.getAs<Loc>()) {
     Val = State->getRawSVal(*LocAmount);
     Value = &Val;
   }
 
   const auto &TgtVal =
       (Op == OO_PlusEqual || Op == OO_MinusEqual) ? Iterator : RetVal;
 
   // `AdvancedState` is a state where the position of `LHS` is advanced. We
   // only need this state to retrieve the new position, but we do not want
   // to change the position of `LHS` (in every case).
   auto AdvancedState = advancePosition(State, Iterator, Op, *Value);
   if (AdvancedState) {
     const auto *NewPos = getIteratorPosition(AdvancedState, Iterator);
-    assert(NewPos &&
            "Iterator should have position after successful advancement");
 
     State = setIteratorPosition(State, TgtVal, *NewPos);
     C.addTransition(State);
   } else {
     assignToContainer(C, CE, TgtVal, Pos->getContainer());
   }
 }

 
 void IteratorModeling::handleAdvance(CheckerContext &C, const Expr *CE,
                                      SVal RetVal, SVal Iter,
                                      SVal Amount) const {
   handleRandomIncrOrDecr(C, CE, OO_PlusEqual, RetVal, Iter, Amount);
 }
 
 void IteratorModeling::handlePrev(CheckerContext &C, const Expr *CE,
-                                  SVal RetVal, SVal Iter, SVal Amount) const {
+                                  SVal RetVal, SVal Iter,
+                                  SVal Amount) const {
   handleRandomIncrOrDecr(C, CE, OO_Minus, RetVal, Iter, Amount);
 }
 
 void IteratorModeling::handleNext(CheckerContext &C, const Expr *CE,
-                                  SVal RetVal, SVal Iter, SVal Amount) const {
+                                  SVal RetVal, SVal Iter,
+                                  SVal Amount) const {
   handleRandomIncrOrDecr(C, CE, OO_Plus, RetVal, Iter, Amount);
 }
 
 void IteratorModeling::assignToContainer(CheckerContext &C, const Expr *CE,
-                                         const SVal &RetVal,
+                                         SVal RetVal,
                                          const MemRegion *Cont) const {
   Cont = Cont->getMostDerivedObjectRegion();
 
   auto State = C.getState();
   const auto *LCtx = C.getLocationContext();
   State = createIteratorPosition(State, RetVal, Cont, CE, LCtx, C.blockCount());
 
   C.addTransition(State);

 bool isSimpleComparisonOperator(OverloadedOperatorKind OK) {
   return OK == OO_EqualEqual || OK == OO_ExclaimEqual;
 }
 
 bool isSimpleComparisonOperator(BinaryOperatorKind OK) {
   return OK == BO_EQ || OK == BO_NE;
 }
 
-ProgramStateRef removeIteratorPosition(ProgramStateRef State, const SVal &Val) {
+ProgramStateRef removeIteratorPosition(ProgramStateRef State, SVal Val) {
   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);
-  } else if (const auto LCVal = Val.getAs<nonloc::LazyCompoundVal>()) {
-    return State->remove<IteratorRegionMap>(LCVal->getRegion());
-  }
-  return nullptr;
-}
-
-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 isBoundThroughLazyCompoundVal(const Environment &Env,
-                                   const MemRegion *Reg) {
-  for (const auto &Binding : Env) {
-    if (const auto LCVal = Binding.second.getAs<nonloc::LazyCompoundVal>()) {
-      if (LCVal->getRegion() == Reg)
-        return true;
-    }
-  }
-
-  return false;
+  return State;
 }
 
 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/lib/StaticAnalyzer/Checkers/IteratorRangeChecker.cpp

if (!Func)
     return;
 
   if (Func->isOverloadedOperator()) {
     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));
-        }
+        verifyIncrement(C, getIteratorArg(Call, 0, C.blockCount()));
       }
     } 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));
-        }
+        verifyDecrement(C, getIteratorArg(Call, 0, C.blockCount()));
       }
     } 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 &&
             Call.getArgExpr(0)->getType()->isIntegralOrEnumerationType()) {
           verifyRandomIncrOrDecr(C, Func->getOverloadedOperator(),
                                  InstCall->getCXXThisVal(),
                                  Call.getArgSVal(0));
         }
       } else {
         if (Call.getNumArgs() >= 2 &&
             Call.getArgExpr(1)->getType()->isIntegralOrEnumerationType()) {
           verifyRandomIncrOrDecr(C, Func->getOverloadedOperator(),
-                                 Call.getArgSVal(0), Call.getArgSVal(1));
+                                 getIteratorArg(Call, 0, C.blockCount()),
+                                 Call.getArgSVal(1));
         }
       }
     } 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));
+        verifyDereference(C, getIteratorArg(Call, 0, C.blockCount()));
       }
     }
   } else {
     const AdvanceFn *Verifier = AdvanceFunctions.lookup(Call);
     if (Verifier) {
+      SVal Arg0 = getIteratorArg(Call, 0, C.blockCount());
+
       if (Call.getNumArgs() > 1) {
-        (this->**Verifier)(C, Call.getArgSVal(0), Call.getArgSVal(1));
+        (this->**Verifier)(C, Arg0, Call.getArgSVal(1));
       } else {
         auto &BVF = C.getSValBuilder().getBasicValueFactory();
         (this->**Verifier)(
-            C, Call.getArgSVal(0),
+            C, Arg0,
             nonloc::ConcreteInt(BVF.getValue(llvm::APSInt::get(1))));
       }
     }
   }
 }
 
 void IteratorRangeChecker::checkPreStmt(const UnaryOperator *UO,
                                         CheckerContext &C) const {

clang/lib/StaticAnalyzer/Checkers/MismatchedIteratorChecker.cpp

 
 namespace {
 
 class MismatchedIteratorChecker
   : public Checker<check::PreCall, check::PreStmt<BinaryOperator>> {
 
   std::unique_ptr<BugType> MismatchedBugType;
 
-  void verifyMatch(CheckerContext &C, const SVal &Iter,
-                   const MemRegion *Cont) const;
-  void verifyMatch(CheckerContext &C, const SVal &Iter1,
-                   const SVal &Iter2) const;
-  void reportBug(const StringRef &Message, const SVal &Val1,
-                 const SVal &Val2, CheckerContext &C,
-                 ExplodedNode *ErrNode) const;
-  void reportBug(const StringRef &Message, const SVal &Val,
-                 const MemRegion *Reg, CheckerContext &C,
-                 ExplodedNode *ErrNode) const;
+  void verifyMatch(CheckerContext &C, SVal Iter, const MemRegion *Cont) const;
+  void verifyMatch(CheckerContext &C, SVal Iter1, SVal Iter2) const;
+  void reportBug(const StringRef &Message, SVal Val1, SVal Val2,
+                 CheckerContext &C, ExplodedNode *ErrNode) const;
+  void reportBug(const StringRef &Message, SVal Val, const MemRegion *Reg,
+                 CheckerContext &C, ExplodedNode *ErrNode) const;
 
 public:
   MismatchedIteratorChecker();
 
   void checkPreCall(const CallEvent &Call, CheckerContext &C) const;
   void checkPreStmt(const BinaryOperator *BO, CheckerContext &C) const;
 
 };
 
 } // namespace
 
 MismatchedIteratorChecker::MismatchedIteratorChecker() {
   MismatchedBugType.reset(
       new BugType(this, "Iterator(s) mismatched", "Misuse of STL APIs",
                   /*SuppressOnSink=*/true));
 }
 
 void MismatchedIteratorChecker::checkPreCall(const CallEvent &Call,
                                              CheckerContext &C) const {
   // Check for iterator mismatches
   const auto *Func = dyn_cast_or_null<FunctionDecl>(Call.getDecl());
   if (!Func)
     return;
 
+  // If the call has no arguments, there is nothing to check here
+  if (Call.getNumArgs() < 1)
+    return;
+
   if (Func->isOverloadedOperator() &&
       isComparisonOperator(Func->getOverloadedOperator())) {
     // Check for comparisons of iterators of different containers
+    SVal Arg0 = getIteratorArg(Call, 0, C.blockCount());
     if (const auto *InstCall = dyn_cast<CXXInstanceCall>(&Call)) {
-      if (Call.getNumArgs() < 1)
-        return;
-
       if (!isIteratorType(InstCall->getCXXThisExpr()->getType()) ||
           !isIteratorType(Call.getArgExpr(0)->getType()))
         return;
 
-      verifyMatch(C, InstCall->getCXXThisVal(), Call.getArgSVal(0));
+      verifyMatch(C, InstCall->getCXXThisVal(), Arg0);
     } else {
       if (Call.getNumArgs() < 2)
         return;
 
+      SVal Arg1 = getIteratorArg(Call, 1, C.blockCount());
       if (!isIteratorType(Call.getArgExpr(0)->getType()) ||
           !isIteratorType(Call.getArgExpr(1)->getType()))
         return;
 
-      verifyMatch(C, Call.getArgSVal(0), Call.getArgSVal(1));
+      verifyMatch(C, Arg0, Arg1);
     }
   } else if (const auto *InstCall = dyn_cast<CXXInstanceCall>(&Call)) {
     const auto *ContReg = InstCall->getCXXThisVal().getAsRegion();
     if (!ContReg)
       return;
+
+    SVal Arg0 = getIteratorArg(Call, 0, C.blockCount());
     // Check for erase, insert and emplace using iterator of another container
     if (isEraseCall(Func) || isEraseAfterCall(Func)) {
-      verifyMatch(C, Call.getArgSVal(0),
-                  InstCall->getCXXThisVal().getAsRegion());
+      verifyMatch(C, Arg0, InstCall->getCXXThisVal().getAsRegion());
       if (Call.getNumArgs() == 2) {
-        verifyMatch(C, Call.getArgSVal(1),
-                    InstCall->getCXXThisVal().getAsRegion());
+        SVal Arg1 = getIteratorArg(Call, 1, C.blockCount());
+        verifyMatch(C, Arg1, InstCall->getCXXThisVal().getAsRegion());
       }
     } else if (isInsertCall(Func)) {
-      verifyMatch(C, Call.getArgSVal(0),
-                  InstCall->getCXXThisVal().getAsRegion());
+      verifyMatch(C, Arg0, InstCall->getCXXThisVal().getAsRegion());
       if (Call.getNumArgs() == 3 &&
           isIteratorType(Call.getArgExpr(1)->getType()) &&
           isIteratorType(Call.getArgExpr(2)->getType())) {
-        verifyMatch(C, Call.getArgSVal(1), Call.getArgSVal(2));
+        SVal Arg1 = getIteratorArg(Call, 1, C.blockCount());
+        SVal Arg2 = getIteratorArg(Call, 2, C.blockCount());
+        verifyMatch(C, Arg1, Arg2);
       }
     } else if (isEmplaceCall(Func)) {
-      verifyMatch(C, Call.getArgSVal(0),
-                  InstCall->getCXXThisVal().getAsRegion());
+      verifyMatch(C, Arg0, InstCall->getCXXThisVal().getAsRegion());
     }
   } else if (isa<CXXConstructorCall>(&Call)) {
     // Check match of first-last iterator pair in a constructor of a container
     if (Call.getNumArgs() < 2)
       return;
 
     const auto *Ctr = cast<CXXConstructorDecl>(Call.getDecl());
     if (Ctr->getNumParams() < 2)
       return;
 
     if (Ctr->getParamDecl(0)->getName() != "first" ||
         Ctr->getParamDecl(1)->getName() != "last")
       return;
 
     if (!isIteratorType(Call.getArgExpr(0)->getType()) ||
         !isIteratorType(Call.getArgExpr(1)->getType()))
       return;
 
-    verifyMatch(C, Call.getArgSVal(0), Call.getArgSVal(1));
+    SVal Arg0 = getIteratorArg(Call, 0, C.blockCount());
+    SVal Arg1 = getIteratorArg(Call, 1, C.blockCount());
+    verifyMatch(C, Arg0, Arg1);
   } else {
     // The main purpose of iterators is to abstract away from different
     // containers and provide a (maybe limited) uniform access to them.
     // This implies that any correctly written template function that
     // works on multiple containers using iterators takes different
     // template parameters for different containers. So we can safely
     // assume that passing iterators of different containers as arguments
     // whose type replaces the same template parameter is a bug.
for (size_t I = 0; I < TParams->size(); ++I) {
 
       if (TPDecl->isParameterPack())
         continue;
 
       const auto TAType = TArgs->get(I).getAsType();
       if (!isIteratorType(TAType))
         continue;
 
-      SVal LHS = UndefinedVal();
+      Optional<SVal> LHS = None;
 
       // For every template parameter which is an iterator type in the
       // instantiation look for all functions' parameters' type by it and
       // check whether they belong to the same container
       for (auto J = 0U; J < Func->getNumParams(); ++J) {
         const auto *Param = Func->getParamDecl(J);
         const auto *ParamType =
             Param->getType()->getAs<SubstTemplateTypeParmType>();
         if (!ParamType ||
             ParamType->getReplacedParameter()->getDecl() != TPDecl)
           continue;
-        if (LHS.isUndef()) {
-          LHS = Call.getArgSVal(J);
+
+        SVal ArgJ = getIteratorArg(Call, J, C.blockCount());
+
+        if (!LHS.hasValue()) {
+          LHS = ArgJ;
         } else {
-          verifyMatch(C, LHS, Call.getArgSVal(J));
+          verifyMatch(C, *LHS, ArgJ);
         }
       }
     }
   }
 }
 
 void MismatchedIteratorChecker::checkPreStmt(const BinaryOperator *BO,
                                              CheckerContext &C) const {
   if (!BO->isComparisonOp())
     return;
 
   ProgramStateRef State = C.getState();
   SVal LVal = State->getSVal(BO->getLHS(), C.getLocationContext());
   SVal RVal = State->getSVal(BO->getRHS(), C.getLocationContext());
   verifyMatch(C, LVal, RVal);
 }
 
-void MismatchedIteratorChecker::verifyMatch(CheckerContext &C, const SVal &Iter,
+void MismatchedIteratorChecker::verifyMatch(CheckerContext &C, SVal Iter,
                                             const MemRegion *Cont) const {
   // Verify match between a container and the container of an iterator
   Cont = Cont->getMostDerivedObjectRegion();
 
   if (const auto *ContSym = Cont->getSymbolicBase()) {
     if (isa<SymbolConjured>(ContSym->getSymbol()))
       return;
   }
if (isa<SymbolConjured>(ContSym->getSymbol()))
       return;
   }
 
   if (IterCont != Cont) {
     auto *N = C.generateNonFatalErrorNode(State);
     if (!N) {
       return;
     }
-    reportBug("Container accessed using foreign iterator argument.",
-                        Iter, Cont, C, N);
+    reportBug("Container accessed using foreign iterator argument.", Iter, Cont,
+              C, N);
   }
 }
 
-void MismatchedIteratorChecker::verifyMatch(CheckerContext &C,
-                                            const SVal &Iter1,
-                                            const SVal &Iter2) const {
+void MismatchedIteratorChecker::verifyMatch(CheckerContext &C, SVal Iter1,
+                                            SVal Iter2) const {
   // Verify match between the containers of two iterators
   auto State = C.getState();
   const auto *Pos1 = getIteratorPosition(State, Iter1);
   if (!Pos1)
     return;
 
   const auto *IterCont1 = Pos1->getContainer();
 
if (IterCont1 != IterCont2) {
     auto *N = C.generateNonFatalErrorNode(State);
     if (!N)
       return;
     reportBug("Iterators of different containers used where the "
                         "same container is expected.", Iter1, Iter2, C, N);
   }
 }
 
-void MismatchedIteratorChecker::reportBug(const StringRef &Message,
-                                          const SVal &Val1,
-                                          const SVal &Val2,
-                                          CheckerContext &C,
+void MismatchedIteratorChecker::reportBug(const StringRef &Message, SVal Val1,
+                                          SVal Val2, CheckerContext &C,
                                           ExplodedNode *ErrNode) const {
   auto R = std::make_unique<PathSensitiveBugReport>(*MismatchedBugType, Message,
                                                     ErrNode);
   R->markInteresting(Val1);
   R->markInteresting(Val2);
   C.emitReport(std::move(R));
 }
 
-void MismatchedIteratorChecker::reportBug(const StringRef &Message,
-                                          const SVal &Val, const MemRegion *Reg,
+void MismatchedIteratorChecker::reportBug(const StringRef &Message, SVal Val,
+                                          const MemRegion *Reg,
                                           CheckerContext &C,
                                           ExplodedNode *ErrNode) const {
   auto R = std::make_unique<PathSensitiveBugReport>(*MismatchedBugType, Message,
                                                     ErrNode);
   R->markInteresting(Val);
   R->markInteresting(Reg);
   C.emitReport(std::move(R));
 }
 
 void ento::registerMismatchedIteratorChecker(CheckerManager &mgr) {
   mgr.registerChecker<MismatchedIteratorChecker>();
 }
 
 bool ento::shouldRegisterMismatchedIteratorChecker(const CheckerManager &mgr) {
   return true;
 }

clang/lib/StaticAnalyzer/Checkers/STLAlgorithmModeling.cpp

 
 using namespace clang;
 using namespace ento;
 using namespace iterator;
 
 namespace {
 
 class STLAlgorithmModeling : public Checker<eval::Call> {
-  bool evalFind(CheckerContext &C, const CallExpr *CE) const;
+  void evalFind(CheckerContext &C, const CallExpr *CE, SVal Begin,
+                SVal End) const;
 
-  void Find(CheckerContext &C, const CallExpr *CE, unsigned paramNum) const;
-
-  using FnCheck = bool (STLAlgorithmModeling::*)(CheckerContext &,
-                                                const CallExpr *) const;
+  using FnCheck = void (STLAlgorithmModeling::*)(CheckerContext &,
+                                                 const CallExpr *, SVal Begin,
+                                                 SVal End) const;
 
   const CallDescriptionMap<FnCheck> Callbacks = {
     {{{"std", "find"}, 3}, &STLAlgorithmModeling::evalFind},
     {{{"std", "find"}, 4}, &STLAlgorithmModeling::evalFind},
     {{{"std", "find_if"}, 3}, &STLAlgorithmModeling::evalFind},
     {{{"std", "find_if"}, 4}, &STLAlgorithmModeling::evalFind},
     {{{"std", "find_if_not"}, 3}, &STLAlgorithmModeling::evalFind},
     {{{"std", "find_if_not"}, 4}, &STLAlgorithmModeling::evalFind},
public:
 
   bool AggressiveStdFindModeling;
 
   bool evalCall(const CallEvent &Call, CheckerContext &C) const;
 }; //
 
 bool STLAlgorithmModeling::evalCall(const CallEvent &Call,
                                     CheckerContext &C) const {
-  const auto *CE = dyn_cast_or_null<CallExpr>(Call.getOriginExpr());
-  if (!CE)
-    return false;
-
-  const FnCheck *Handler = Callbacks.lookup(Call);
-  if (!Handler)
-    return false;
-
-  return (this->**Handler)(C, CE);
-}
-
-bool STLAlgorithmModeling::evalFind(CheckerContext &C,
-                                    const CallExpr *CE) const {
   // std::find()-like functions either take their primary range in the first
   // two parameters, or if the first parameter is "execution policy" then in
   // the second and third. This means that the second parameter must always be
   // an iterator.
-  if (!isIteratorType(CE->getArg(1)->getType()))
+  if (Call.getNumArgs() < 2 || !isIteratorType(Call.getArgExpr(1)->getType()))
     return false;
 
   // If no "execution policy" parameter is used then the first argument is the
-  // beginning of the range.
-  if (isIteratorType(CE->getArg(0)->getType())) {
-    Find(C, CE, 0);
-    return true;
+  // beginning of the range. If "execution policy" parmeter is used then the
+  // third argument is the end of the range.
+  unsigned ArgNum = 0;
+  if (!isIteratorType(Call.getArgExpr(0)->getType())) {
+    if (Call.getNumArgs() < 3 || !isIteratorType(Call.getArgExpr(2)->getType()))
+      return false;
+    ArgNum = 1;
   }
 
-  // If "execution policy" parameter is used then the second argument is the
-  // beginning of the range.
-  if (isIteratorType(CE->getArg(2)->getType())) {
-    Find(C, CE, 1);
-    return true;
-  }
+  SVal ArgB = getIteratorArg(Call, ArgNum, C.blockCount());
+  SVal ArgE = getIteratorArg(Call, ArgNum + 1, C.blockCount());
+
+  const auto *CE = dyn_cast_or_null<CallExpr>(Call.getOriginExpr());
+  if (!CE)
+    return false;
 
+  const FnCheck *Handler = Callbacks.lookup(Call);
+  if (!Handler)
     return false;
+
+  (this->**Handler)(C, CE, ArgB, ArgE);
+  return true;
 }
 
-void STLAlgorithmModeling::Find(CheckerContext &C, const CallExpr *CE,
-                                unsigned paramNum) const {
+void STLAlgorithmModeling::evalFind(CheckerContext &C, const CallExpr *CE,
+                                    SVal Begin, SVal End) const {
   auto State = C.getState();
   auto &SVB = C.getSValBuilder();
   const auto *LCtx = C.getLocationContext();
 
   SVal RetVal = SVB.conjureSymbolVal(nullptr, CE, LCtx, C.blockCount());
-  SVal Param = State->getSVal(CE->getArg(paramNum), LCtx);
 
   auto StateFound = State->BindExpr(CE, LCtx, RetVal);
 
   // If we have an iterator position for the range-begin argument then we can
   // assume that in case of successful search the position of the found element
   // is not ahead of it.
   // FIXME: Reverse iterators
-  const auto *Pos = getIteratorPosition(State, Param);
+  const auto *Pos = getIteratorPosition(State, Begin);
   if (Pos) {
     StateFound = createIteratorPosition(StateFound, RetVal, Pos->getContainer(),
                                         CE, LCtx, C.blockCount());
     const auto *NewPos = getIteratorPosition(StateFound, RetVal);
     assert(NewPos && "Failed to create new iterator position.");
 
     SVal GreaterOrEqual = SVB.evalBinOp(StateFound, BO_GE,
                                         nonloc::SymbolVal(NewPos->getOffset()),
                                         nonloc::SymbolVal(Pos->getOffset()),
                                         SVB.getConditionType());
     assert(GreaterOrEqual.getAs<DefinedSVal>() &&
            "Symbol comparison must be a `DefinedSVal`");
     StateFound = StateFound->assume(GreaterOrEqual.castAs<DefinedSVal>(), true);
   }
 
-  Param = State->getSVal(CE->getArg(paramNum + 1), LCtx);
-
   // If we have an iterator position for the range-end argument then we can
   // assume that in case of successful search the position of the found element
   // is ahead of it.
   // FIXME: Reverse iterators
-  Pos = getIteratorPosition(State, Param);
+  Pos = getIteratorPosition(State, End);
   if (Pos) {
     StateFound = createIteratorPosition(StateFound, RetVal, Pos->getContainer(),
                                         CE, LCtx, C.blockCount());
     const auto *NewPos = getIteratorPosition(StateFound, RetVal);
     assert(NewPos && "Failed to create new iterator position.");
 
     SVal Less = SVB.evalBinOp(StateFound, BO_LT,
                               nonloc::SymbolVal(NewPos->getOffset()),
                               nonloc::SymbolVal(Pos->getOffset()),
                               SVB.getConditionType());
     assert(Less.getAs<DefinedSVal>() &&
            "Symbol comparison must be a `DefinedSVal`");
     StateFound = StateFound->assume(Less.castAs<DefinedSVal>(), true);
   }
 
   C.addTransition(StateFound);
 
   if (AggressiveStdFindModeling) {
-    auto StateNotFound = State->BindExpr(CE, LCtx, Param);
+    auto StateNotFound = State->BindExpr(CE, LCtx, End);
     C.addTransition(StateNotFound);
   }
 }
 
 } // namespace
 
 void ento::registerSTLAlgorithmModeling(CheckerManager &Mgr) {
   auto *Checker = Mgr.registerChecker<STLAlgorithmModeling>();

clang/lib/StaticAnalyzer/Core/ExprEngineCXX.cpp

case ConstructionContext::SimpleVariableKind: {
       QualType Ty = Var->getType();
       return makeZeroElementRegion(State, State->getLValue(Var, LCtx), Ty,
                                    CallOpts.IsArrayCtorOrDtor);
     }
     case ConstructionContext::CXX17ElidedCopyConstructorInitializerKind:
     case ConstructionContext::SimpleConstructorInitializerKind: {
       const auto *ICC = cast<ConstructorInitializerConstructionContext>(CC);
       const auto *Init = ICC->getCXXCtorInitializer();
-      assert(Init->isAnyMemberInitializer());
       const CXXMethodDecl *CurCtor = cast<CXXMethodDecl>(LCtx->getDecl());
       Loc ThisPtr = SVB.getCXXThis(CurCtor, LCtx->getStackFrame());
       SVal ThisVal = State->getSVal(ThisPtr);
+      if (Init->isBaseInitializer() || Init->isDelegatingInitializer())
+        return ThisVal;
 
       const ValueDecl *Field;
       SVal FieldVal;
       if (Init->isIndirectMemberInitializer()) {
         Field = Init->getIndirectMember();
         FieldVal = State->getLValue(Init->getIndirectMember(), ThisVal);
       } else {
         Field = Init->getMember();
ProgramStateRef ExprEngine::updateObjectsUnderConstruction(
   case ConstructionContext::CXX17ElidedCopyVariableKind:
   case ConstructionContext::SimpleVariableKind: {
     const auto *DSCC = cast<VariableConstructionContext>(CC);
     return addObjectUnderConstruction(State, DSCC->getDeclStmt(), LCtx, V);
     }
     case ConstructionContext::CXX17ElidedCopyConstructorInitializerKind:
     case ConstructionContext::SimpleConstructorInitializerKind: {
       const auto *ICC = cast<ConstructorInitializerConstructionContext>(CC);
+      const auto *Init = ICC->getCXXCtorInitializer();
+      assert(Init->isAnyMemberInitializer());
       return addObjectUnderConstruction(State, ICC->getCXXCtorInitializer(),
                                         LCtx, V);
     }
     case ConstructionContext::NewAllocatedObjectKind: {
       return State;
     }
     case ConstructionContext::SimpleReturnedValueKind:
     case ConstructionContext::CXX17ElidedCopyReturnedValueKind: {

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/iterator-modeling.cpp

 }
 
 void ptr_iter_cmp_nullptr(cont_with_ptr_iterator<int> &c) {
   auto i0 = c.begin();
   if (i0 != nullptr) // no-crash
     ++i0;
 }
 
+template <typename T>
+struct delegated_ctor_iterator {
+  delegated_ctor_iterator(const T&, int);
+  delegated_ctor_iterator(const T& t) : delegated_ctor_iterator(t, 0) {}
+  delegated_ctor_iterator operator++();
+  delegated_ctor_iterator operator++(int);
+  T& operator*();
+};
+
+template <typename T>
+struct container_with_delegated_ctor_iterator {
+  typedef delegated_ctor_iterator<T> iterator;
+  iterator begin() const { return delegated_ctor_iterator<T>(T()); }
+};
+
+void
+test_delegated_ctor_iterator(
+    const container_with_delegated_ctor_iterator<int> &c) {
+  auto i = c.begin(); // no-crash
+  clang_analyzer_denote(clang_analyzer_container_begin(c), "$c.begin()");
+  clang_analyzer_express(clang_analyzer_iterator_position(i)); // expected-warning{{$c.begin()}}
+}
+
+template <typename T>
+struct base_ctor_iterator {
+  base_ctor_iterator(const T&);
+  base_ctor_iterator operator++();
+  base_ctor_iterator operator++(int);
+  T& operator*();
+};
+
+template <typename T>
+struct derived_ctor_iterator: public base_ctor_iterator<T> {
+  derived_ctor_iterator(const T& t) : base_ctor_iterator<T>(t) {}
+};
+
+template <typename T>
+struct container_with_derived_ctor_iterator {
+  typedef derived_ctor_iterator<T> iterator;
+  iterator begin() const { return derived_ctor_iterator<T>(T()); }
+};
+
+void
+test_derived_ctor_iterator(const container_with_derived_ctor_iterator<int> &c) {
+  auto i = c.begin();
+  clang_analyzer_denote(clang_analyzer_container_begin(c), "$c.begin()");
+  clang_analyzer_express(clang_analyzer_iterator_position(i)); // expected-warning{{$c.begin()}}
+}
+
 void clang_analyzer_printState();
 
 void print_state(std::vector<int> &V) {
   const auto i0 = V.cbegin();
   clang_analyzer_printState();
 
   // CHECK:      "checker_messages": [
   // CHECK:   { "checker": "alpha.cplusplus.IteratorModeling", "messages": [

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;

clang/unittests/StaticAnalyzer/TestReturnValueUnderConstruction.cpp

AnalysisConsumer.AddCheckerRegistrationFn([](CheckerRegistry &Registry) {
       Registry.addChecker<TestReturnValueUnderConstructionChecker>(
           "test.TestReturnValueUnderConstruction", "", "");
     });
 }
 
 TEST(TestReturnValueUnderConstructionChecker,
      ReturnValueUnderConstructionChecker) {
   EXPECT_TRUE(runCheckerOnCode<addTestReturnValueUnderConstructionChecker>(
-                  R"(class C {
-                     public:
-                       C(int nn): n(nn) {}
-                       virtual ~C() {}
-                     private:
-                       int n;
-                     };
 
-                     C returnC(int m) {
-                       C c(m);
-                       return c;
-                     }
 
-                     void foo() {
-                       C c = returnC(1); 
-                     })"));
+           C c = returnC(1);
+
+  EXPECT_TRUE(runCheckerOnCode<addTestReturnValueUnderConstructionChecker>(
+      R"(class C {
+         public:
+           C(int nn): n(nn) {}
+           explicit C(): C(0) {}
+           virtual ~C() {}
+         private:
+           int n;
+         };
+
+         C returnC() {
+           C c;
+           return c;
+         }
+
+         void foo() {
+           C c = returnC();
+         })"));
+
+  EXPECT_TRUE(runCheckerOnCode<addTestReturnValueUnderConstructionChecker>(
+      R"(class C {
+         public:
+           C(int nn): n(nn) {}
+           virtual ~C() {}
+         private:
+           int n;
+         };
+
+         class D: public C {
+         public:
+           D(int nn): C(nn) {}
+           virtual ~D() {}
+         };
+
+         D returnD(int m) {
+           D d(m);
+           return d;
+         }
+
+         void foo() {
+           D d = returnD(1); 
+         })"));
 }
 
 } // namespace
 } // namespace ento
 } // namespace clang