[Analyzer] Iterator Checker - Part 2: Increment, decrement operators and ahead-of-begin checks

[takuto.ikuta]

lib/StaticAnalyzer/Checkers/IteratorChecker.cpp

357

We cannot use else after return?
http://llvm.org/docs/CodingStandards.html#don-t-use-else-after-a-return

576

oldOffset -> OldOffset?
same with L577, L580, L595, L596, L599 and so on.

941

else after return?

945

else after return too.

1195

else after return?

[baloghadamsoftware]

Rebased to (committed) Part1 (rL304160) and updated according to comments.

[baloghadamsoftware]

Any progress in the review?

[NoQ]

I'm sorry, i'd try to get back to this and unblock your progress as soon as possible.

One thing i notice is that you manipulate symbolic expressions manually, however many of the things that you need, eg stuff in your compose() method, seem to be already available in SValBuilder::evalBinOp(). I think you could simplify the code significantly if you rely on it.

One of the downsides of SValBuilder::evalBinOp() is that it sometimes simplifies some operations to UnknownVal when it knows that the rest of the analyzer would be unable to handle the results anyway. I'm not sure if your approach is more clever than the rest of the analyzer when it comes to handling such values. However, in any case, we're thinking about lifting these limitations in D28953, so it might be a good idea to wait for that to land as well.

lib/StaticAnalyzer/Checkers/IteratorChecker.cpp

51

Just noticed: Constraint Manager can handle these SVals sometimes, suggesting such SVals.

125

Just noticed: can we mark these as const, because there are no methods to modify them? I guess you intended to keep objects of this class immutable.

[baloghadamsoftware]

I tried SValBuilder::evalBinOp() first but it did not help too much. It could decide only if I compared the same conjured symbols or different ones, but nothing more. It always gave me UnknownVal. Even if comparing ${conj_X} == ${conj_X} + n where n was a concrete integer. So I have to compare the symbol part and the concrete integer part separately. Waiting is not an option for us since we are a bit delayed with this checker. I have to bring them out of alpha until the end of the year. If Z3 constraint solver is accepted and will be the default constraint manager, then I can somewhat simplify my code. That patch is under review for long and I am not sure whether it will be the default ever.

[baloghadamsoftware]

Minor fixes according to the comments.

[NoQ]

In D32642#787913, @baloghadamsoftware wrote:

I tried SValBuilder::evalBinOp() first but it did not help too much. It could decide only if I compared the same conjured symbols or different ones, but nothing more. It always gave me UnknownVal. Even if comparing ${conj_X} == ${conj_X} + n where n was a concrete integer. So I have to compare the symbol part and the concrete integer part separately.

In any case, it's not right to have two SValBuilders. Your code simplifies symbolic expressions of numeric types, SValBuilder does the same thing, there's no need to duplicate. It would be much better to move the functionality you need (and already have implemented) directly to SValBuilder.

I'm sure that simplification (($x + N) + M) ~> ($x + (M + N)) is already working in SValBuilder. I think it's totally worth it to add (($x + M) == ($x + N)) ~> (M == N) and (($x + M) - ($x + N)) ~> M - N into SValBuilder in case it's not already there, because the whole analyzer would immediately benefit from that, not just your checker.

Generally, i totally encourage you to modify the analyzer's core to fit your purposes, even if to reduce code duplication. It's not worth it to teach the core constraint manager how to work with user-defined types such as iterators, but it's definitely worth it to teach SValBuilder how to handle numeric-type symbols better.

In D32642#787913, @baloghadamsoftware wrote:

If Z3 constraint solver is accepted and will be the default constraint manager, then I can somewhat simplify my code. That patch is under review for long and I am not sure whether it will be the default ever.

I don't expect Z3 to be on by default soon, however i'm only pointing to the changes in the mainline SValBuilder in that patch. Z3 doesn't replace SValBuilder, it only replaces the constraint manager. However, SValBuilder needs to provide accurate SVals to Z3, which means that a lot of UnknownVals need to go away. We're discussing if they should go away completely even if Z3 isn't on.

In D32642#787913, @baloghadamsoftware wrote:

Waiting is not an option for us since we are a bit delayed with this checker. I have to bring them out of alpha until the end of the year.

While moving things out of alpha is pretty much the primary goal of any work we do, sacrificing quality defeats that purpose. We can only afford to enable things by default when we know they're ready. This checker is research-heavy and as such hard to plan. We need to understand the decisions and trade-offs that you made.

[baloghadamsoftware]

I'm sure that simplification (($x + N) + M) ~> ($x + (M + N)) is already working in SValBuilder.

No, it is unfortunately not working: I tried to increase ${conj_X} by 1, then again by 1, and I got symbolic expression (${conj_X}+1)+1).

[NoQ]

In D32642#788822, @baloghadamsoftware wrote:

I'm sure that simplification (($x + N) + M) ~> ($x + (M + N)) is already working in SValBuilder.

No, it is unfortunately not working: I tried to increase ${conj_X} by 1, then again by 1, and I got symbolic expression (${conj_X}+1)+1).

Could you post the code you use?

[NoQ]

For example,

$ cat test.c

void clang_analyzer_dump(int);

int bar();

void foo() {
  int x = bar();
  clang_analyzer_dump(x);
  ++x;
  clang_analyzer_dump(x);
  ++x;
  clang_analyzer_dump(x);
}

$ ~/debug/bin/clang -cc1 -analyze -analyzer-checker=debug.ExprInspection test.c

test.c:7:3: warning: conj_$2{int}
  clang_analyzer_dump(x);
  ^~~~~~~~~~~~~~~~~~~~~~
test.c:9:3: warning: (conj_$2{int}) + 1
  clang_analyzer_dump(x);
  ^~~~~~~~~~~~~~~~~~~~~~
test.c:11:3: warning: (conj_$2{int}) + 2
  clang_analyzer_dump(x);
  ^~~~~~~~~~~~~~~~~~~~~~
3 warnings generated.

So i'm sure we're already doing this everywhere.

[baloghadamsoftware]

SymbolManager::getSymIntExpr() replaced by SValBuilder::evalBinOp(), function compact() eliminated.

[baloghadamsoftware]

Now I can improve SValBuilder to compare {conj_X}+n to conj_X}+m, but I am not sure if it helps to simplify compare() much. How to handle cases where I have to compare {conj_X}+n to {conj_Y}+m, an we have a range [k..k] for {conj_X}-{conj_Y} in the constraint manager. I still need to decompose the two expressions, retrieve the single length range and adjust one of the sides of the comparison. I think I should not add such complicated code (i.e. retrieving single length range from the constrain manager) to SValBuilder.

[NoQ]

In D32642#789004, @baloghadamsoftware wrote:

Now I can improve SValBuilder to compare {conj_X}+n to conj_X}+m, but I am not sure if it helps to simplify compare() much. How to handle cases where I have to compare {conj_X}+n to {conj_Y}+m, an we have a range [k..k] for {conj_X}-{conj_Y} in the constraint manager. I still need to decompose the two expressions, retrieve the single length range and adjust one of the sides of the comparison. I think I should not add such complicated code (i.e. retrieving single length range from the constrain manager) to SValBuilder.

SValBuilder simplifies the symbolic expressions to a certain "canonical" form - collapses ($x op N) op M to single-op expressions, reorders N op $x to $x op N, unpacks !$x into $x == 0, etc.), and ConstraintManager makes assumptions over such "canonical" symbolic expressions (but unable to handle non-canonical symbolic expressions).

I propose to canonicalize ($x + N) == ($y + M) to ($x - $y) == (M - N) in SValBuilder, and then ConstraintManager should be able to assume over it, as long as it has a range for ($x - $y). ConstraintManager would also need an update to support reversing the range when he only has a range for ($y - $x) but not for ($x - $y).

[baloghadamsoftware]

Simplified for enhanced SValBuilder and ConstraintManager.

[baloghadamsoftware]

It seems that review on D35109 is stuck forever. So maybe we should forget about this simplification and return to the local solution I tried to use here originally. It is Part2, and we need to go through all parts as soon as possible. In the meanwhile I also tested the whole iterator solution on the whole Clang project and got rid of many false positives. So the checker itself is very promissing.

[NoQ]

This patch would be in a good shape once we settle the rearrangement stuff. I had a look at all follow-up patches and identified other, hopefully smaller, places where i have overall design concerns; otherwise, the rest of the patches also look safe and straightforward.

[baloghadamsoftware]

Updated to be based upon D41938 and D35110.

[baloghadamsoftware]

Updated to work with the latest Constrain Manager patch.

[NoQ]

I think this looks good. There's a problem with missing construction contexts, but i guess that's not the checker's fault, so let's add a FIXME and commit.

lib/StaticAnalyzer/Checkers/IteratorChecker.cpp

454–455

This deserves a FIXME because that's definitely unreliable (i.e. if another checker subscribes to the operator call and adds a transition before you, you'll break because you'd have to ascend two nodes above, not one).

The proper fix is to make the CFG provide a ConstructionContext for the CXXOperatorCallExpr, which would turn the corresponding CFGStmt element into a CFGCXXRecordTypedCall element, which will allow ExprEngine to foresee that the begin()/end() call constructs the object directly in the temporary region that CXXOperatorCallExpr takes as its implicit object argument.

The proper fix is not hard, but there are still a lot of simpler and more common cases that we don't handle.

476–502

I guess we'll have this sorted out in another patch.

lib/StaticAnalyzer/Checkers/IteratorChecker.cpp

 // use setter and getters functions which separate the three cases. To store
 // them we use a pointer union of symbol and memory region.
 //
-// The checker works the following way: We record the past-end iterator for
-// all containers whenever their `.end()` is called. Since the Constraint
-// Manager cannot handle SVals we need to take over its role. We post-check
-// equality and non-equality comparisons and propagate the position of the
-// iterator to the other side of the comparison if it is past-end and we are in
-// the 'equal' branch (true-branch for `==` and false-branch for `!=`).
+// The checker works the following way: We record the begin and the
+// past-end iterator for all containers whenever their `.begin()` and `.end()`
+// are called. Since the Constraint Manager cannot handle such SVals we need
+// to take over its role. We post-check equality and non-equality comparisons
+// and record that the two sides are equal if we are in the 'equal' branch
+// (true-branch for `==` and false-branch for `!=`).
 //
 // In case of type-I or type-II iterators we get a concrete integer as a result
 // of the comparison (1 or 0) but in case of type-III we only get a Symbol. In
 // this latter case we record the symbol and reload it in evalAssume() and do
 // the propagation there. We also handle (maybe double) negated comparisons
-// which are represented in the form of (x == 0 or x !=0 ) where x is the
+// which are represented in the form of (x == 0 or x != 0) where x is the
 // comparison itself.
+//
+// Since `SimpleConstraintManager` cannot handle complex symbolic expressions
+// we only use expressions of the format S, S+n or S-n for iterator positions
+// where S is a conjured symbol and n is an unsigned concrete integer. When
+// making an assumption e.g. `S1 + n == S2 + m` we store `S1 - S2 == m - n` as
+// a constraint which we later retrieve when doing an actual comparison.
 
 #include "ClangSACheckers.h"
 #include "clang/StaticAnalyzer/Core/BugReporter/BugType.h"

   const MemRegion *Cont;
 
   // Abstract offset
-  SymbolRef Offset;
+  const SymbolRef Offset;
 
   IteratorPosition(const MemRegion *C, SymbolRef Of)
       : Cont(C), Offset(Of) {}

 
 typedef llvm::PointerUnion<const MemRegion *, SymbolRef> RegionOrSymbol;
 
-// Structure to record the symbolic end position of a container
+// Structure to record the symbolic begin and end position of a container
 struct ContainerData {
 private:
-  SymbolRef End;
+  const SymbolRef Begin, End;
 
-  ContainerData(SymbolRef E) : End(E) {}
+  ContainerData(SymbolRef B, SymbolRef E) : Begin(B), End(E) {}
 
 public:
+  static ContainerData fromBegin(SymbolRef B) {
+    return ContainerData(B, nullptr);
+  }
+
   static ContainerData fromEnd(SymbolRef E) {
-    return ContainerData(E);
+    return ContainerData(nullptr, E);
   }
 
+  SymbolRef getBegin() const { return Begin; }
   SymbolRef getEnd() const { return End; }
 
-  ContainerData newEnd(SymbolRef E) const { return ContainerData(E); }
+  ContainerData newBegin(SymbolRef B) const { return ContainerData(B, End); }
+
+  ContainerData newEnd(SymbolRef E) const { return ContainerData(Begin, E); }
 
   bool operator==(const ContainerData &X) const {
-    return End == X.End;
+    return Begin == X.Begin && End == X.End;
   }
 
   bool operator!=(const ContainerData &X) const {
-    return End != X.End;
+    return Begin != X.Begin || End != X.End;
   }
 
   void Profile(llvm::FoldingSetNodeID &ID) const {
+    ID.Add(Begin);
     ID.Add(End);
   }
 };

 
 class IteratorChecker
     : public Checker<check::PreCall, check::PostCall,
+                     check::PreStmt<CXXOperatorCallExpr>,
                      check::PostStmt<MaterializeTemporaryExpr>,
-                     check::DeadSymbols,
+                     check::LiveSymbols, check::DeadSymbols,
                      eval::Assume> {
 
   std::unique_ptr<BugType> OutOfRangeBugType;

   void handleComparison(CheckerContext &C, const SVal &RetVal, const SVal &LVal,
                         const SVal &RVal, OverloadedOperatorKind Op) const;
   void verifyDereference(CheckerContext &C, const SVal &Val) 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 handleRandomIncrOrDecr(CheckerContext &C, OverloadedOperatorKind Op,
+                              const SVal &RetVal, const SVal &LHS,
+                              const SVal &RHS) const;
+  void handleBegin(CheckerContext &C, const Expr *CE, const SVal &RetVal,
+                   const SVal &Cont) const;
   void handleEnd(CheckerContext &C, const Expr *CE, const SVal &RetVal,
                  const SVal &Cont) const;
   void assignToContainer(CheckerContext &C, const Expr *CE, const SVal &RetVal,
                          const MemRegion *Cont) const;
+  void verifyRandomIncrOrDecr(CheckerContext &C, OverloadedOperatorKind Op,
+                              const SVal &RetVal, const SVal &LHS,
+                              const SVal &RHS) const;
   void reportOutOfRangeBug(const StringRef &Message, const SVal &Val,
                            CheckerContext &C, ExplodedNode *ErrNode) const;
 

 
   void checkPreCall(const CallEvent &Call, CheckerContext &C) const;
   void checkPostCall(const CallEvent &Call, CheckerContext &C) const;
+  void checkPreStmt(const CXXOperatorCallExpr *COCE, 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;
   ProgramStateRef evalAssume(ProgramStateRef State, SVal Cond,
                              bool Assumption) const;

 
 bool isIteratorType(const QualType &Type);
 bool isIterator(const CXXRecordDecl *CRD);
+bool isBeginCall(const FunctionDecl *Func);
 bool isEndCall(const FunctionDecl *Func);
 bool isSimpleComparisonOperator(OverloadedOperatorKind OK);
 bool isDereferenceOperator(OverloadedOperatorKind OK);
+bool isIncrementOperator(OverloadedOperatorKind OK);
+bool isDecrementOperator(OverloadedOperatorKind OK);
+bool isRandomIncrOrDecrOperator(OverloadedOperatorKind OK);
 BinaryOperator::Opcode getOpcode(const SymExpr *SE);
 const RegionOrSymbol getRegionOrSymbol(const SVal &Val);
 const ProgramStateRef processComparison(ProgramStateRef State,

                                      const SVal &RVal, bool Eq);
 const IteratorComparison *loadComparison(ProgramStateRef State,
                                          const SymExpr *Condition);
+SymbolRef getContainerBegin(ProgramStateRef State, const MemRegion *Cont);
 SymbolRef getContainerEnd(ProgramStateRef State, const MemRegion *Cont);
+ProgramStateRef createContainerBegin(ProgramStateRef State,
+                                     const MemRegion *Cont,
+                                     const SymbolRef Sym);
 ProgramStateRef createContainerEnd(ProgramStateRef State, const MemRegion *Cont,
                                    const SymbolRef Sym);
 const IteratorPosition *getIteratorPosition(ProgramStateRef State,

 ProgramStateRef setContainerData(ProgramStateRef State, const MemRegion *Cont,
                                  const ContainerData &CData);
 bool isOutOfRange(ProgramStateRef State, const IteratorPosition &Pos);
+bool isZero(ProgramStateRef State, const NonLoc &Val);
 } // namespace
 
 IteratorChecker::IteratorChecker() {

 
   if (Func->isOverloadedOperator()) {
     if (ChecksEnabled[CK_IteratorRangeChecker] &&
+        isRandomIncrOrDecrOperator(Func->getOverloadedOperator())) {
+      if (const auto *InstCall = dyn_cast<CXXInstanceCall>(&Call)) {
+        // Check for out-of-range incrementions and decrementions
+        if (Call.getNumArgs() >= 1) {
+          verifyRandomIncrOrDecr(C, Func->getOverloadedOperator(),
+                                 Call.getReturnValue(),
+                                 InstCall->getCXXThisVal(), Call.getArgSVal(0));
+        }
+      } else {
+        if (Call.getNumArgs() >= 2) {
+          verifyRandomIncrOrDecr(C, Func->getOverloadedOperator(),
+                                 Call.getReturnValue(), Call.getArgSVal(0),
+                                 Call.getArgSVal(1));
+        }
+      }
+    } else if (ChecksEnabled[CK_IteratorRangeChecker] &&
                isDereferenceOperator(Func->getOverloadedOperator())) {
       // Check for dereference of out-of-range iterators
       if (const auto *InstCall = dyn_cast<CXXInstanceCall>(&Call)) {

         handleComparison(C, Call.getReturnValue(), Call.getArgSVal(0),
                          Call.getArgSVal(1), Op);
       }
+    } else if (isRandomIncrOrDecrOperator(Func->getOverloadedOperator())) {
+      if (const auto *InstCall = dyn_cast<CXXInstanceCall>(&Call)) {
+        if (Call.getNumArgs() >= 1) {
+          handleRandomIncrOrDecr(C, Func->getOverloadedOperator(),
+                                 Call.getReturnValue(),
+                                 InstCall->getCXXThisVal(), Call.getArgSVal(0));
+        }
+      } else {
+        if (Call.getNumArgs() >= 2) {
+          handleRandomIncrOrDecr(C, Func->getOverloadedOperator(),
+                                 Call.getReturnValue(), Call.getArgSVal(0),
+                                 Call.getArgSVal(1));
+        }
+      }
+    } else if (isIncrementOperator(Func->getOverloadedOperator())) {
+      if (const auto *InstCall = dyn_cast<CXXInstanceCall>(&Call)) {
+        handleIncrement(C, Call.getReturnValue(), InstCall->getCXXThisVal(),
+                        Call.getNumArgs());
+      } else {
+        handleIncrement(C, Call.getReturnValue(), Call.getArgSVal(0),
+                        Call.getNumArgs());
+      }
+    } else if (isDecrementOperator(Func->getOverloadedOperator())) {
+      if (const auto *InstCall = dyn_cast<CXXInstanceCall>(&Call)) {
+        handleDecrement(C, Call.getReturnValue(), InstCall->getCXXThisVal(),
+                        Call.getNumArgs());
+      } else {
+        handleDecrement(C, Call.getReturnValue(), Call.getArgSVal(0),
+                        Call.getNumArgs());
+      }
     }
   } else {
     const auto *OrigExpr = Call.getOriginExpr();

       return;
 
     if (const auto *InstCall = dyn_cast<CXXInstanceCall>(&Call)) {
+      if (isBeginCall(Func)) {
+        handleBegin(C, OrigExpr, Call.getReturnValue(),
+                    InstCall->getCXXThisVal());
+        return;
+      }
       if (isEndCall(Func)) {
         handleEnd(C, OrigExpr, Call.getReturnValue(),
                   InstCall->getCXXThisVal());

   }
 }
 
+void IteratorChecker::checkPreStmt(const CXXOperatorCallExpr *COCE,
+                                   CheckerContext &C) const {
+  const auto *ThisExpr = COCE->getArg(0);
+
+  auto State = C.getState();
+  const auto *LCtx = C.getLocationContext();
+
+  const auto CurrentThis = State->getSVal(ThisExpr, LCtx);
+  if (const auto *Reg = CurrentThis.getAsRegion()) {
+    if (!Reg->getAs<CXXTempObjectRegion>())
+      return;
+    const auto OldState = C.getPredecessor()->getFirstPred()->getState();
+    const auto OldThis = OldState->getSVal(ThisExpr, LCtx);
+    const auto *Pos = getIteratorPosition(OldState, OldThis);
+    if (!Pos)
+      return;
+    State = setIteratorPosition(State, CurrentThis, *Pos);
+    C.addTransition(State);
+  }
+}
+
 void IteratorChecker::checkPostStmt(const MaterializeTemporaryExpr *MTE,
                                     CheckerContext &C) const {
   /* Transfer iterator state to temporary objects */

   C.addTransition(State);
 }
 
+void IteratorChecker::checkLiveSymbols(ProgramStateRef State,
+                                       SymbolReaper &SR) const {
+  // Keep symbolic expressions of iterator positions, container begins and ends
+  // alive
+  auto RegionMap = State->get<IteratorRegionMap>();
+  for (const auto Reg : RegionMap) {
+    const auto Pos = Reg.second;
+    SR.markLive(Pos.getOffset());
+  }
+
+  auto SymbolMap = State->get<IteratorSymbolMap>();
+  for (const auto Sym : SymbolMap) {
+    const auto Pos = Sym.second;
+    SR.markLive(Pos.getOffset());
+  }
+
+  auto ContMap = State->get<ContainerMap>();
+  for (const auto Cont : ContMap) {
+    const auto CData = Cont.second;
+    if (CData.getBegin()) {
+      SR.markLive(CData.getBegin());
+    }
+    if (CData.getEnd()) {
+      SR.markLive(CData.getEnd());
+    }
+  }
+}
+
 void IteratorChecker::checkDeadSymbols(SymbolReaper &SR,
                                        CheckerContext &C) const {
   // Cleanup

     static CheckerProgramPointTag Tag("IteratorRangeChecker",
                                       "IteratorOutOfRange");
     auto *N = C.generateNonFatalErrorNode(State, &Tag);
-    if (!N) {
+    if (!N)
       return;
-    }
     reportOutOfRangeBug("Iterator accessed outside of its range.", Val, C, N);
   }
 }
 
+void IteratorChecker::handleIncrement(CheckerContext &C, const SVal &RetVal,
+                                      const SVal &Iter, bool Postfix) const {
+  // Increment the symbolic expressions which represents the position of the
+  // iterator
+  auto State = C.getState();
+  const auto *Pos = getIteratorPosition(State, Iter);
+  if (Pos) {
+    auto &SymMgr = C.getSymbolManager();
+    auto &BVF = SymMgr.getBasicVals();
+    auto &SVB = C.getSValBuilder();
+    const auto OldOffset = Pos->getOffset();
+    auto NewOffset =
+      SVB.evalBinOp(State, BO_Add,
+                    nonloc::SymbolVal(OldOffset),
+                    nonloc::ConcreteInt(BVF.getValue(llvm::APSInt::get(1))),
+                    SymMgr.getType(OldOffset)).getAsSymbol();
+    auto NewPos = Pos->setTo(NewOffset);
+    State = setIteratorPosition(State, Iter, NewPos);
+    State = setIteratorPosition(State, RetVal, Postfix ? *Pos : NewPos);
+    C.addTransition(State);
+  }
+}
+
+void IteratorChecker::handleDecrement(CheckerContext &C, const SVal &RetVal,
+                                      const SVal &Iter, bool Postfix) const {
+  // Decrement the symbolic expressions which represents the position of the
+  // iterator
+  auto State = C.getState();
+  const auto *Pos = getIteratorPosition(State, Iter);
+  if (Pos) {
+    auto &SymMgr = C.getSymbolManager();
+    auto &BVF = SymMgr.getBasicVals();
+    auto &SVB = C.getSValBuilder();
+    const auto OldOffset = Pos->getOffset();
+    auto NewOffset =
+      SVB.evalBinOp(State, BO_Sub,
+                    nonloc::SymbolVal(OldOffset),
+                    nonloc::ConcreteInt(BVF.getValue(llvm::APSInt::get(1))),
+                    SymMgr.getType(OldOffset)).getAsSymbol();
+    auto NewPos = Pos->setTo(NewOffset);
+    State = setIteratorPosition(State, Iter, NewPos);
+    State = setIteratorPosition(State, RetVal, Postfix ? *Pos : NewPos);
+    C.addTransition(State);
+  }
+}
+
+// This function tells the analyzer's engine that symbols produced by our
+// checker, most notably iterator positions, are relatively small.
+// A distance between items in the container should not be very large.
+// By assuming that it is within around 1/8 of the address space,
+// we can help the analyzer perform operations on these symbols
+// without being afraid of integer overflows.
+// FIXME: Should we provide it as an API, so that all checkers could use it?
+static ProgramStateRef assumeNoOverflow(ProgramStateRef State, SymbolRef Sym,
+                                        long Scale) {
+  SValBuilder &SVB = State->getStateManager().getSValBuilder();
+  BasicValueFactory &BV = SVB.getBasicValueFactory();
+
+  QualType T = Sym->getType();
+  assert(T->isSignedIntegerOrEnumerationType());
+  APSIntType AT = BV.getAPSIntType(T);
+
+  ProgramStateRef NewState = State;
+
+  llvm::APSInt Max = AT.getMaxValue() / AT.getValue(Scale);
+  SVal IsCappedFromAbove =
+      SVB.evalBinOpNN(State, BO_LE, nonloc::SymbolVal(Sym),
+                      nonloc::ConcreteInt(Max), SVB.getConditionType());
+  if (auto DV = IsCappedFromAbove.getAs<DefinedSVal>()) {
+    NewState = NewState->assume(*DV, true);
+    if (!NewState)
+      return State;
+  }
+
+  llvm::APSInt Min = -Max;
+  SVal IsCappedFromBelow =
+      SVB.evalBinOpNN(State, BO_GE, nonloc::SymbolVal(Sym),
+                      nonloc::ConcreteInt(Min), SVB.getConditionType());
+  if (auto DV = IsCappedFromBelow.getAs<DefinedSVal>()) {
+    NewState = NewState->assume(*DV, true);
+    if (!NewState)
+      return State;
+  }
+
+  return NewState;
+}
+
+void IteratorChecker::handleRandomIncrOrDecr(CheckerContext &C,
+                                             OverloadedOperatorKind Op,
+                                             const SVal &RetVal,
+                                             const SVal &LHS,
+                                             const SVal &RHS) const {
+  // Increment or decrement the symbolic expressions which represents the
+  // position of the iterator
+  auto State = C.getState();
+  const auto *Pos = getIteratorPosition(State, LHS);
+  if (!Pos)
+    return;
+
+  const auto *value = &RHS;
+  if (auto loc = RHS.getAs<Loc>()) {
+    const auto val = State->getRawSVal(*loc);
+    value = &val;
+  }
+
+  auto &SymMgr = C.getSymbolManager();
+  auto &SVB = C.getSValBuilder();
+  auto BinOp = (Op == OO_Plus || Op == OO_PlusEqual) ? BO_Add : BO_Sub;
+  const auto OldOffset = Pos->getOffset();
+  SymbolRef NewOffset;
+  if (const auto intValue = value->getAs<nonloc::ConcreteInt>()) {
+    // For concrete integers we can calculate the new position
+    NewOffset = SVB.evalBinOp(State, BinOp, nonloc::SymbolVal(OldOffset),
+                              *intValue,
+                              SymMgr.getType(OldOffset)).getAsSymbol();
+  } else {
+    // For other symbols create a new symbol to keep expressions simple
+    const auto &LCtx = C.getLocationContext();
+    NewOffset = SymMgr.conjureSymbol(nullptr, LCtx, SymMgr.getType(OldOffset),
+                                     C.blockCount());
+    State = assumeNoOverflow(State, NewOffset, 4);
+  }
+  auto NewPos = Pos->setTo(NewOffset);
+  auto &TgtVal = (Op == OO_PlusEqual || Op == OO_MinusEqual) ? LHS : RetVal;
+  State = setIteratorPosition(State, TgtVal, NewPos);
+  C.addTransition(State);
+}
+
+void IteratorChecker::verifyRandomIncrOrDecr(CheckerContext &C,
+                                             OverloadedOperatorKind Op,
+                                             const SVal &RetVal,
+                                             const SVal &LHS,
+                                             const SVal &RHS) const {
+  auto State = C.getState();
+
+  // If the iterator is initially inside its range, then the operation is valid
+  const auto *Pos = getIteratorPosition(State, LHS);
+  if (!Pos || !isOutOfRange(State, *Pos))
+    return;
+
+  auto value = RHS;
+  if (auto loc = RHS.getAs<Loc>()) {
+    value = State->getRawSVal(*loc);
+  }
+
+  // Incremention or decremention by 0 is never bug
+  if (isZero(State, value.castAs<NonLoc>()))
+    return;
+
+  auto &SymMgr = C.getSymbolManager();
+  auto &SVB = C.getSValBuilder();
+  auto BinOp = (Op == OO_Plus || Op == OO_PlusEqual) ? BO_Add : BO_Sub;
+  const auto OldOffset = Pos->getOffset();
+  const auto intValue = value.getAs<nonloc::ConcreteInt>();
+  if (!intValue)
+    return;
+
+  auto NewOffset = SVB.evalBinOp(State, BinOp, nonloc::SymbolVal(OldOffset),
+                                 *intValue,
+                                 SymMgr.getType(OldOffset)).getAsSymbol();
+  auto NewPos = Pos->setTo(NewOffset);
+
+  // If out of range, the only valid operation is to step into the range
+  if (isOutOfRange(State, NewPos)) {
+    auto *N = C.generateNonFatalErrorNode(State);
+    if (!N)
+      return;
+    reportOutOfRangeBug("Iterator accessed past its end.", LHS, C, N);
+  }
+}
+
+void IteratorChecker::handleBegin(CheckerContext &C, const Expr *CE,
+                                  const SVal &RetVal, const SVal &Cont) const {
+  const auto *ContReg = Cont.getAsRegion();
+  if (!ContReg)
+    return;
+
+  while (const auto *CBOR = ContReg->getAs<CXXBaseObjectRegion>()) {
+    ContReg = CBOR->getSuperRegion();
+  }
+
+  // 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) {
+    auto &SymMgr = C.getSymbolManager();
+    BeginSym = SymMgr.conjureSymbol(CE, C.getLocationContext(),
+                                    C.getASTContext().LongTy, C.blockCount());
+    State = assumeNoOverflow(State, BeginSym, 4);
+    State = createContainerBegin(State, ContReg, BeginSym);
+  }
+  State = setIteratorPosition(State, RetVal,
+                              IteratorPosition::getPosition(ContReg, BeginSym));
+  C.addTransition(State);
+}
+
 void IteratorChecker::handleEnd(CheckerContext &C, const Expr *CE,
                                 const SVal &RetVal, const SVal &Cont) const {
   const auto *ContReg = Cont.getAsRegion();

     auto &SymMgr = C.getSymbolManager();
     EndSym = SymMgr.conjureSymbol(CE, C.getLocationContext(),
                                   C.getASTContext().LongTy, C.blockCount());
+    State = assumeNoOverflow(State, EndSym, 4);
     State = createContainerEnd(State, ContReg, EndSym);
   }
   State = setIteratorPosition(State, RetVal,

   auto &SymMgr = C.getSymbolManager();
   auto Sym = SymMgr.conjureSymbol(CE, C.getLocationContext(),
                                   C.getASTContext().LongTy, C.blockCount());
+  State = assumeNoOverflow(State, Sym, 4);
   State = setIteratorPosition(State, RetVal,
                               IteratorPosition::getPosition(Cont, Sym));
   C.addTransition(State);

 
 namespace {
 
+bool isLess(ProgramStateRef State, SymbolRef Sym1, SymbolRef Sym2);
 bool isGreaterOrEqual(ProgramStateRef State, SymbolRef Sym1, SymbolRef Sym2);
 bool compare(ProgramStateRef State, SymbolRef Sym1, SymbolRef Sym2,
              BinaryOperator::Opcode Opc);
+bool compare(ProgramStateRef State, NonLoc NL1, NonLoc NL2,
+             BinaryOperator::Opcode Opc);
 
 bool isIteratorType(const QualType &Type) {
   if (Type->isPointerType())

          HasPostIncrOp && HasDerefOp;
 }
 
+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)

          OK == OO_Subscript;
 }
 
+bool isIncrementOperator(OverloadedOperatorKind OK) {
+  return OK == OO_PlusPlus;
+}
+
+bool isDecrementOperator(OverloadedOperatorKind OK) {
+  return OK == OO_MinusMinus;
+}
+
+bool isRandomIncrOrDecrOperator(OverloadedOperatorKind OK) {
+  return OK == OO_Plus || OK == OO_PlusEqual || OK == OO_Minus ||
+         OK == OO_MinusEqual;
+}
+
 BinaryOperator::Opcode getOpcode(const SymExpr *SE) {
   if (const auto *BSE = dyn_cast<BinarySymExpr>(SE)) {
     return BSE->getOpcode();

   return State->get<IteratorComparisonMap>(Condition);
 }
 
+SymbolRef getContainerBegin(ProgramStateRef State, const MemRegion *Cont) {
+  const auto *CDataPtr = getContainerData(State, Cont);
+  if (!CDataPtr)
+    return nullptr;
+
+  return CDataPtr->getBegin();
+}
+
 SymbolRef getContainerEnd(ProgramStateRef State, const MemRegion *Cont) {
   const auto *CDataPtr = getContainerData(State, Cont);
   if (!CDataPtr)

   return CDataPtr->getEnd();
 }
 
+ProgramStateRef createContainerBegin(ProgramStateRef State,
+                                     const MemRegion *Cont,
+                                     const SymbolRef Sym) {
+  // Only create if it does not exist
+  const auto *CDataPtr = getContainerData(State, Cont);
+  if (CDataPtr) {
+    if (CDataPtr->getBegin()) {
+      return State;
+    }
+    const auto CData = CDataPtr->newBegin(Sym);
+    return setContainerData(State, Cont, CData);
+  }
+  const auto CData = ContainerData::fromBegin(Sym);
+  return setContainerData(State, Cont, CData);
+}
+
 ProgramStateRef createContainerEnd(ProgramStateRef State, const MemRegion *Cont,
                                    const SymbolRef Sym) {
   // Only create if it does not exist

   if (CDataPtr) {
     if (CDataPtr->getEnd()) {
       return State;
-    } else {
-      const auto CData = CDataPtr->newEnd(Sym);
-      return setContainerData(State, Cont, CData);
     }
-  } else {
-    const auto CData = ContainerData::fromEnd(Sym);
+    const auto CData = CDataPtr->newEnd(Sym);
     return setContainerData(State, Cont, CData);
   }
+  const auto CData = ContainerData::fromEnd(Sym);
+  return setContainerData(State, Cont, CData);
 }
 
 const ContainerData *getContainerData(ProgramStateRef State,

                                         const IteratorPosition &Pos1,
                                         const IteratorPosition &Pos2,
                                         bool Equal) {
-  // Try to compare them and get a defined value
   auto &SVB = State->getStateManager().getSValBuilder();
   const auto comparison =
       SVB.evalBinOp(State, BO_EQ, nonloc::SymbolVal(Pos1.getOffset()),
                     nonloc::SymbolVal(Pos2.getOffset()), SVB.getConditionType())
           .getAs<DefinedSVal>();
+
   if (comparison) {
-    return State->assume(*comparison, Equal);
+    auto NewState = State->assume(*comparison, Equal);
+    if (const auto CompSym = comparison->getAsSymbol()) {
+      return assumeNoOverflow(NewState, cast<SymIntExpr>(CompSym)->getLHS(), 2);
+    }
+
+    return NewState;
   }
 
   return State;
 }
 
+bool isZero(ProgramStateRef State, const NonLoc &Val) {
+  auto &BVF = State->getBasicVals();
+  return compare(State, Val,
+                 nonloc::ConcreteInt(BVF.getValue(llvm::APSInt::get(0))),
+                 BO_EQ);
+}
+
 bool isOutOfRange(ProgramStateRef State, const IteratorPosition &Pos) {
   const auto *Cont = Pos.getContainer();
   const auto *CData = getContainerData(State, Cont);

   // Out of range means less than the begin symbol or greater or equal to the
   // end symbol.
 
+  const auto Beg = CData->getBegin();
+  if (Beg) {
+    if (isLess(State, Pos.getOffset(), Beg)) {
+      return true;
+    }
+  }
+
   const auto End = CData->getEnd();
   if (End) {
     if (isGreaterOrEqual(State, Pos.getOffset(), End)) {

   return false;
 }
 
+bool isLess(ProgramStateRef State, SymbolRef Sym1, SymbolRef Sym2) {
+  return compare(State, Sym1, Sym2, BO_LT);
+}
+
 bool isGreaterOrEqual(ProgramStateRef State, SymbolRef Sym1, SymbolRef Sym2) {
   return compare(State, Sym1, Sym2, BO_GE);
 }
 
 bool compare(ProgramStateRef State, SymbolRef Sym1, SymbolRef Sym2,
              BinaryOperator::Opcode Opc) {
-  auto &SMgr = State->getStateManager();
-  auto &SVB = SMgr.getSValBuilder();
+  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, nonloc::SymbolVal(Sym1),
-                    nonloc::SymbolVal(Sym2), SVB.getConditionType())
+      SVB.evalBinOp(State, Opc, NL1, NL2, SVB.getConditionType())
           .getAs<DefinedSVal>();
 
-  if(comparison) {
-    return !!State->assume(*comparison, true);
+  if (comparison) {
+    return !State->assume(*comparison, false);
   }
 
   return false;

   }
 
 REGISTER_CHECKER(IteratorRangeChecker)
+

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

       return size_t(_finish - _start);
     }
 
+    void clear();
+
+    void push_back(const T &value);
+    void push_back(T &&value);
+    void pop_back();
+
     T &operator[](size_t n) {
       return _start[n];
     }

     list& operator=(list &&other);
     list& operator=(std::initializer_list<T> ilist);
 
+    void clear();
+
     iterator begin() { return iterator(_start); }
     const_iterator begin() const { return const_iterator(_start); }
     const_iterator cbegin() const { return const_iterator(_start); }

       return size_t(_finish - _start);
     }
     
+    void clear();
+
+    void push_back(const T &value);
+    void push_back(T &&value);
+    void pop_back();
+
+    void push_front(const T &value);
+    void push_front(T &&value);
+    void pop_front();
+
     T &operator[](size_t n) {
       return _start[n];
     }

     forward_list(forward_list &&other);
     ~forward_list();
     
+    void clear();
+
+    void push_front(const T &value);
+    void push_front(T &&value);
+    void pop_front();
+
     iterator begin() { return iterator(_start); }
     const_iterator begin() const { return const_iterator(_start); }
     const_iterator cbegin() const { return const_iterator(_start); }

test/Analysis/constraint_manager_negate_difference.c

-// RUN: %clang_analyze_cc1 -analyzer-checker=debug.ExprInspection,core.builtin -verify %s
+// RUN: %clang_analyze_cc1 -analyzer-checker=debug.ExprInspection,core.builtin -analyzer-config aggressive-relational-comparison-simplification=true -verify %s
 
 void clang_analyzer_eval(int);
 
 void exit(int);
 
 #define UINT_MAX (~0U)
 #define INT_MAX (UINT_MAX & (UINT_MAX >> 1))
 

test/Analysis/diagnostics/explicit-suppression.cpp

 void testCopyNull(C *I, C *E) {
   std::copy(I, E, (C *)0);
 #ifndef SUPPRESSED
-  // expected-warning@../Inputs/system-header-simulator-cxx.h:490 {{Called C++ object pointer is null}}
+  // expected-warning@../Inputs/system-header-simulator-cxx.h:514 {{Called C++ object pointer is null}}
 #endif
 }

test/Analysis/iterator-range.cpp

-// RUN: %clang_analyze_cc1 -std=c++11 -analyzer-checker=core,cplusplus,alpha.cplusplus.IteratorRange -analyzer-eagerly-assume -analyzer-config c++-container-inlining=false %s -verify
-// RUN: %clang_analyze_cc1 -std=c++11 -analyzer-checker=core,cplusplus,alpha.cplusplus.IteratorRange -analyzer-eagerly-assume -analyzer-config c++-container-inlining=true -DINLINE=1 %s -verify
+// RUN: %clang_analyze_cc1 -std=c++11 -analyzer-checker=core,cplusplus,alpha.cplusplus.IteratorRange -analyzer-eagerly-assume -analyzer-config aggressive-relational-comparison-simplification=true -analyzer-config c++-container-inlining=false %s -verify
+// RUN: %clang_analyze_cc1 -std=c++11 -analyzer-checker=core,cplusplus,alpha.cplusplus.IteratorRange -analyzer-eagerly-assume -analyzer-config aggressive-relational-comparison-simplification=true -analyzer-config c++-container-inlining=true -DINLINE=1 %s -verify
 
 #include "Inputs/system-header-simulator-cxx.h"
 

   }
 }
 
+void simple_good_end_negated(const std::vector<int> &v) {
+  auto i = v.end();
+  if (!(i == v.end())) {
+    clang_analyzer_warnIfReached();
+    *i; // no-warning
+  }
+}
+
 void simple_bad_end(const std::vector<int> &v) {
   auto i = v.end();
   *i; // expected-warning{{Iterator accessed outside of its range}}
 }
+
+void simple_good_begin(const std::vector<int> &v) {
+  auto i = v.begin();
+  if (i != v.begin()) {
+    clang_analyzer_warnIfReached();
+    *--i; // no-warning
+  }
+}
+
+void simple_good_begin_negated(const std::vector<int> &v) {
+  auto i = v.begin();
+  if (!(i == v.begin())) {
+    clang_analyzer_warnIfReached();
+    *--i; // no-warning
+  }
+}
+
+void simple_bad_begin(const std::vector<int> &v) {
+  auto i = v.begin();
+  *--i; // expected-warning{{Iterator accessed outside of its range}}
+}
+
+void copy(const std::vector<int> &v) {
+  auto i1 = v.end();
+  auto i2 = i1;
+  *i2; // expected-warning{{Iterator accessed outside of its range}}
+}
+
+void decrease(const std::vector<int> &v) {
+  auto i = v.end();
+  --i;
+  *i; // no-warning
+}
+
+void copy_and_decrease1(const std::vector<int> &v) {
+  auto i1 = v.end();
+  auto i2 = i1;
+  --i1;
+  *i1; // no-warning
+}
+
+void copy_and_decrease2(const std::vector<int> &v) {
+  auto i1 = v.end();
+  auto i2 = i1;
+  --i1;
+  *i2; // expected-warning{{Iterator accessed outside of its range}}
+}
+
+void copy_and_increase1(const std::vector<int> &v) {
+  auto i1 = v.begin();
+  auto i2 = i1;
+  ++i1;
+  if (i1 == v.end())
+    *i2; // no-warning
+}
+
+void copy_and_increase2(const std::vector<int> &v) {
+  auto i1 = v.begin();
+  auto i2 = i1;
+  ++i1;
+  if (i2 == v.end())
+    *i2; // expected-warning{{Iterator accessed outside of its range}}
+}
+
+void copy_and_increase3(const std::vector<int> &v) {
+  auto i1 = v.begin();
+  auto i2 = i1;
+  ++i1;
+  if (v.end() == i2)
+    *i2; // expected-warning{{Iterator accessed outside of its range}}
+}
+
+void tricky(std::vector<int> &V, int e) {
+  const auto first = V.begin();
+  const auto comp1 = (first != V.end()), comp2 = (first == V.end());
+  if (comp1)
+    *first;
+}
+
+void loop(std::vector<int> &V, int e) {
+  auto start = V.begin();
+  while (true) {
+    auto item = std::find(start, V.end(), e);
+    if (item == V.end())
+      break;
+    *item;          // no-warning
+    start = ++item; // no-warning
+  }
+}
+
+void bad_move(std::list<int> &L1, std::list<int> &L2) {
+  auto i0 = --L2.cend();
+  L1 = std::move(L2);
+  *++i0; // expected-warning{{Iterator accessed outside of its range}}
+}