[Analyzer] Hotfix for various crashes in iterator checkers

[baloghadamsoftware]

Summary

The patch that introduces handling iterators implemented as pointers may cause crash in some projects because pointer difference is mistakenly handled as pointer decrement. (Similair case for iterators implemented as class instances are already handled correctly.) This patch fixes this issue.

The second case that causes crash is comparison of an iterator implemented as pointer and a null-pointer. This patch contains a fix for this issue as well.

The third case which causes crash is that the checker mistakenly considers all integers as nonloc::ConcreteInt when handling an increment or decrement of an iterator implemented as pointers. This patch adds a fix for this too.

The last case where crashes were detected is when checking for success of an std::advance() operation. Since the modeling of iterators implemented as pointers is still incomplete this may result in an assertion. This patch replaces the assertion with an early exit and adds a FIXME there.

[baloghadamsoftware]

Test added for the third fix in this patch.

[Szelethus]

clang/lib/StaticAnalyzer/Checkers/IteratorModeling.cpp

275–276

This doesn't look symmetrical. How does this patch interact with D83190?

[baloghadamsoftware]

clang/lib/StaticAnalyzer/Checkers/IteratorModeling.cpp

275–276

This is not symmetrical. Since this patch is a hotfix for three bugs, all of them cause crashes it is more urgent to land. The other patch should be rebased on it.

[gamesh411]

clang/lib/StaticAnalyzer/Checkers/IteratorModeling.cpp

275–276

I see that patch D83190 will need not only to be rebased, but modified slightly to take this early checking into account. I will refer to this review over there.

[gamesh411]

@Szelethus thanks for being watchful, appreciated c:

[Szelethus]

LGTM, but if we knowingly a subpar solution, we should make that clear in the surrounding code. I know the followup patch is around the corner, but just to be sure.

clang/lib/StaticAnalyzer/Checkers/IteratorModeling.cpp

275–276

Please add a FIXME before commiting, if we knowingly add a hack.

466–470

Is this always okay? Shouldn't we check what the reason was behind the failure to retrieve the position? Is a TODO: at the very least appropriate?

clang/lib/StaticAnalyzer/Checkers/IteratorRangeChecker.cpp

172–173

FIXME:

[baloghadamsoftware]

Two more crashes detected, fixes for them added.

[baloghadamsoftware]

Protection against Unknown added for pointer increments and decrements. No more crashes on LLVM/Clang.

clang/lib/StaticAnalyzer/Checkers/IteratorModeling.cpp

void IteratorModeling::checkPostStmt(const BinaryOperator *BO,
   SVal RVal = State->getSVal(BO->getRHS(), C.getLocationContext());
 
   if (isSimpleComparisonOperator(BO->getOpcode())) {
     SVal LVal = State->getSVal(BO->getLHS(), C.getLocationContext());
     SVal Result = State->getSVal(BO, C.getLocationContext());
     handleComparison(C, BO, Result, LVal, RVal,
                      BinaryOperator::getOverloadedOperator(OK));
   } else if (isRandomIncrOrDecrOperator(OK)) {
+    if (!BO->getRHS()->getType()->isIntegralOrEnumerationType())
+      return;
     handlePtrIncrOrDecr(C, BO->getLHS(),
                         BinaryOperator::getOverloadedOperator(OK), RVal);
   }
 }
 
 void IteratorModeling::checkPostStmt(const MaterializeTemporaryExpr *MTE,
                                      CheckerContext &C) const {
   /* Transfer iterator state to temporary objects */
State = setIteratorPosition(State, LVal,
                                 IteratorPosition::getPosition(Cont, Sym));
     LPos = getIteratorPosition(State, LVal);
   } else if (!RPos) {
     State = setIteratorPosition(State, RVal,
                                 IteratorPosition::getPosition(Cont, Sym));
     RPos = getIteratorPosition(State, RVal);
   }
 
+  // If the value for which we just tried to set a new iterator position is
+  // an `SVal`for which no iterator position can be set then the setting was
+  // unsuccessful. We cannot handle the comparison in this case.
+  if (!LPos || !RPos)
+    return;
+
   // 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);
if (AdvancedState) {
     assignToContainer(C, CE, TgtVal, Pos->getContainer());
   }
 }
 
 void IteratorModeling::handlePtrIncrOrDecr(CheckerContext &C,
                                            const Expr *Iterator,
                                            OverloadedOperatorKind OK,
                                            SVal Offset) const {
+  if (!Offset.getAs<DefinedSVal>())
+    return;
+
   QualType PtrType = Iterator->getType();
   if (!PtrType->isPointerType())
     return;
   QualType ElementType = PtrType->getPointeeType();
 
   ProgramStateRef State = C.getState();
   SVal OldVal = State->getSVal(Iterator, C.getLocationContext());
 
   const IteratorPosition *OldPos = getIteratorPosition(State, OldVal);
   if (!OldPos)
     return;
 
   SVal NewVal;
-  if (OK == OO_Plus || OK == OO_PlusEqual)
+  if (OK == OO_Plus || OK == OO_PlusEqual) {
     NewVal = State->getLValue(ElementType, Offset, OldVal);
-  else {
-    const llvm::APSInt &OffsetInt =
-      Offset.castAs<nonloc::ConcreteInt>().getValue();
-    auto &BVF = C.getSymbolManager().getBasicVals();
-    SVal NegatedOffset = nonloc::ConcreteInt(BVF.getValue(-OffsetInt));
+  } else {
+    auto &SVB = C.getSValBuilder();
+    SVal NegatedOffset = SVB.evalMinus(Offset.castAs<NonLoc>());
     NewVal = State->getLValue(ElementType, NegatedOffset, OldVal);
   }
 
   // `AdvancedState` is a state where the position of `Old` is advanced. We
   // only need this state to retrieve the new position, but we do not want
   // ever to change the position of `OldVal`.
   auto AdvancedState = advancePosition(State, OldVal, OK, Offset);
   if (AdvancedState) {
bool IteratorModeling::noChangeInAdvance(CheckerContext &C, SVal Iter,
   if (!PosAfter)
     return false;
 
   const ExplodedNode *N = findCallEnter(C.getPredecessor(), CE);
   assert(N && "Any call should have a `CallEnter` node.");
 
   const auto StateBefore = N->getState();
   const auto *PosBefore = getIteratorPosition(StateBefore, Iter);
-
-  assert(PosBefore && "`std::advance() should not create new iterator "
-         "position but change existing ones");
+  // FIXME: `std::advance()` should not create a new iterator position but
+  //        change existing ones. However, in case of iterators implemented as
+  //        pointers the handling of parameters in `std::advance()`-like
+  //        functions is still incomplete which may result in cases where
+  //        the new position is assigned to the wrong pointer. This causes
+  //        crash if we use an assertion here.
+  if (!PosBefore)
+    return false;
 
   return PosBefore->getOffset() == PosAfter->getOffset();
 }
 
 void IteratorModeling::printState(raw_ostream &Out, ProgramStateRef State,
                                   const char *NL, const char *Sep) const {
   auto SymbolMap = State->get<IteratorSymbolMap>();
   auto RegionMap = State->get<IteratorRegionMap>();

clang/lib/StaticAnalyzer/Checkers/IteratorRangeChecker.cpp

void IteratorRangeChecker::checkPreStmt(const BinaryOperator *BO,
   ProgramStateRef State = C.getState();
   BinaryOperatorKind OK = BO->getOpcode();
   SVal LVal = State->getSVal(BO->getLHS(), C.getLocationContext());
 
   if (isDereferenceOperator(OK)) {
     verifyDereference(C, LVal);
   } else if (isRandomIncrOrDecrOperator(OK)) {
     SVal RVal = State->getSVal(BO->getRHS(), C.getLocationContext());
+    if (!BO->getRHS()->getType()->isIntegralOrEnumerationType())
+      return;
     verifyRandomIncrOrDecr(C, BinaryOperator::getOverloadedOperator(OK), LVal,
                            RVal);
   }
 }
 
 void IteratorRangeChecker::checkPreStmt(const ArraySubscriptExpr *ASE,
                                         CheckerContext &C) const {
   ProgramStateRef State = C.getState();

clang/test/Analysis/iterator-modeling.cpp

void minus_equal_ptr_iterator(const cont_with_ptr_iterator<int> &c) {
 
   clang_analyzer_denote(clang_analyzer_container_end(c), "$c.end()");
 
   i -= 2;
 
   clang_analyzer_express(clang_analyzer_iterator_position(i)); // expected-warning{{$c.end() - 2}}
 }
 
+void minus_equal_ptr_iterator_variable(const cont_with_ptr_iterator<int> &c,
+                                       int n) {
+  auto i = c.end();
+
+  i -= n; // no-crash
+}
+
 void plus_ptr_iterator(const cont_with_ptr_iterator<int> &c) {
   auto i1 = c.begin();
 
   clang_analyzer_denote(clang_analyzer_container_begin(c), "$c.begin()");
 
   auto i2 = i1 + 2;
 
   clang_analyzer_eval(clang_analyzer_iterator_container(i2) == &c); // expected-warning{{TRUE}}
   clang_analyzer_express(clang_analyzer_iterator_position(i1)); // expected-warning{{$c.begin()}}
   clang_analyzer_express(clang_analyzer_iterator_position(i2)); // expected-warning{{$c.begin() + 2}}
 }
 
 void minus_ptr_iterator(const cont_with_ptr_iterator<int> &c) {
   auto i1 = c.end();
 
   clang_analyzer_denote(clang_analyzer_container_end(c), "$c.end()");
 
   auto i2 = i1 - 2;
 
   clang_analyzer_eval(clang_analyzer_iterator_container(i2) == &c); // expected-warning{{TRUE}}
   clang_analyzer_express(clang_analyzer_iterator_position(i1)); // expected-warning{{$c.end()}}
   clang_analyzer_express(clang_analyzer_iterator_position(i2)); // expected-warning{{$c.end() - 2}}
 }
 
+void ptr_iter_diff(cont_with_ptr_iterator<int> &c) {
+  auto i0 = c.begin(), i1 = c.end();
+  ptrdiff_t len = i1 - i0; // no-crash
+}
+
+void ptr_iter_cmp_nullptr(cont_with_ptr_iterator<int> &c) {
+  auto i0 = c.begin();
+  if (i0 != nullptr) // no-crash
+    ++i0;
+}
+
 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/iterator-range.cpp

 
 void postfix_minus_assign_2_begin_ptr_iterator(
     const cont_with_ptr_iterator<S> &c) {
   auto i = c.begin();
   i -= 2; // expected-warning{{Iterator decremented ahead of its valid range}}
           // expected-note@-1{{Iterator decremented ahead of its valid range}}
 }
 
+void ptr_iter_diff(cont_with_ptr_iterator<S> &c) {
+  auto i0 = c.begin(), i1 = c.end();
+  ptrdiff_t len = i1 - i0; // no-crash
+}