[Analyzer] Iterator Checkers - Check and simulate `std::advance`, `std::prev` and `std::next`

[baloghadamsoftware]

Summary

In case of invoking std::advance, std::prev and std::next range errors should be reported in the invoker and not inside the STL implementation code. Another problem is if the analyzer budget runs out just at the point these functions are invoked. This results in strange behavior such as std::prev(v.end()) equals v.end(). To prevent this simulate these functions if they were not inlined.

[baloghadamsoftware]

This patch definitely reduces the number of false positives, but may not be enough. The problem is that std::advance() may call another function that does the actual incremention or decremention, in the gcc implementation it is __advance(). If the std::advance() is inlined but __advance() not then we still get false positive. The obvious way would be to simulate __advance() as well but it is an implementation dependent internal function and may be totally different for other implementations. Another idea is that instead of querying the CheckerContext whether advance() was inlined we go up the exploded graph and find its "precall" state and compare the values of the first parameter related to the second one in the two states. This is a bit more complex and more expensive but this for me this seems to be the correct solution.

[baloghadamsoftware]

Gentle ping.

[Szelethus]

Again, this a place where a debugging functionality would be awesome to precisely observe the change being made. I also noticed that IteratorChecker and related classes don't have any dump methods, maybe that is worth investing into as well?

[baloghadamsoftware]

Replaced by D76379 and D76361.

lib/StaticAnalyzer/Checkers/IteratorChecker.cpp

 bool isPopBackCall(const FunctionDecl *Func);
 bool isPushFrontCall(const FunctionDecl *Func);
 bool isEmplaceFrontCall(const FunctionDecl *Func);
 bool isPopFrontCall(const FunctionDecl *Func);
 bool isInsertCall(const FunctionDecl *Func);
 bool isEraseCall(const FunctionDecl *Func);
 bool isEraseAfterCall(const FunctionDecl *Func);
 bool isEmplaceCall(const FunctionDecl *Func);
+bool isStdAdvanceCall(const FunctionDecl *Func);
+bool isStdPrevCall(const FunctionDecl *Func);
+bool isStdNextCall(const FunctionDecl *Func);
 bool isAssignmentOperator(OverloadedOperatorKind OK);
 bool isSimpleComparisonOperator(OverloadedOperatorKind OK);
 bool isAccessOperator(OverloadedOperatorKind OK);
 bool isDereferenceOperator(OverloadedOperatorKind OK);
 bool isIncrementOperator(OverloadedOperatorKind OK);
 bool isDecrementOperator(OverloadedOperatorKind OK);
 bool isRandomIncrOrDecrOperator(OverloadedOperatorKind OK);
 bool hasSubscriptOperator(ProgramStateRef State, const MemRegion *Reg);
if (isEraseCall(Func) || isEraseAfterCall(Func)) {
           isIteratorType(Call.getArgExpr(1)->getType()) &&
           isIteratorType(Call.getArgExpr(2)->getType())) {
         verifyMatch(C, Call.getArgSVal(1), Call.getArgSVal(2));
       }
     } else if (isEmplaceCall(Func)) {
       verifyMatch(C, Call.getArgSVal(0),
                   InstCall->getCXXThisVal().getAsRegion());
     }
+  } else if (ChecksEnabled[CK_IteratorRangeChecker] &&
+             (isStdAdvanceCall(Func) || isStdNextCall(Func))) {
+    verifyRandomIncrOrDecr(C, OO_Plus, Call.getArgSVal(0), Call.getArgSVal(1));
+  } else if (ChecksEnabled[CK_IteratorRangeChecker] &&
+             isStdPrevCall(Func)) {
+    verifyRandomIncrOrDecr(C, OO_Minus, Call.getArgSVal(0), Call.getArgSVal(1));
   } 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 (const auto *InstCall = dyn_cast<CXXInstanceCall>(&Call)) {
 
         if (Call.getNumArgs() == 2) {
           handleEraseAfter(C, Call.getArgSVal(0), Call.getArgSVal(1));
           return;
         }
       }
     }
 
+    if (!C.wasInlined) {
+      if (isStdAdvanceCall(Func)) {
+        handleRandomIncrOrDecr(C, OO_PlusEqual, UndefinedVal(),
+                               Call.getArgSVal(0), Call.getArgSVal(1));
+        return;
+      }
+      if (isStdPrevCall(Func)) {
+        handleRandomIncrOrDecr(C, OO_Minus, Call.getReturnValue(),
+                               Call.getArgSVal(0), Call.getArgSVal(1));
+        return;
+      }
+      if (isStdNextCall(Func)) {
+        handleRandomIncrOrDecr(C, OO_Plus, Call.getReturnValue(),
+                               Call.getArgSVal(0), Call.getArgSVal(1));
+        return;
+      }
+    }
+
     const auto *OrigExpr = Call.getOriginExpr();
     if (!OrigExpr)
       return;
 
     if (!isIteratorType(Call.getResultType()))
       return;
 
     auto State = C.getState();
bool isEraseAfterCall(const FunctionDecl *Func) {
   if (!isIteratorType(Func->getParamDecl(0)->getType()))
     return false;
   if (Func->getNumParams() == 2 &&
       !isIteratorType(Func->getParamDecl(1)->getType()))
     return false;
   return IdInfo->getName() == "erase_after";
 }
 
+bool isStdAdvanceCall(const FunctionDecl *Func) {
+  if (!Func->isInStdNamespace())
+    return false;
+  const auto *IdInfo = Func->getIdentifier();
+  if (!IdInfo)
+    return false;
+  return (Func->getNumParams() == 2 && IdInfo->getName() == "advance") ||
+         (Func->getNumParams() == 3 && IdInfo->getName() == "__advance");
+}
+
+bool isStdPrevCall(const FunctionDecl *Func) {
+  if (!Func->isInStdNamespace())
+    return false;
+  const auto *IdInfo = Func->getIdentifier();
+  if (!IdInfo)
+    return false;
+  if (Func->getNumParams() != 2)
+    return false;
+  return IdInfo->getName() == "prev";
+}
+
+bool isStdNextCall(const FunctionDecl *Func) {
+  if (!Func->isInStdNamespace())
+    return false;
+  const auto *IdInfo = Func->getIdentifier();
+  if (!IdInfo)
+    return false;
+  if (Func->getNumParams() != 2)
+    return false;
+  return IdInfo->getName() == "next";
+}
+
 bool isAssignmentOperator(OverloadedOperatorKind OK) { return OK == OO_Equal; }
 
 bool isSimpleComparisonOperator(OverloadedOperatorKind OK) {
   return OK == OO_EqualEqual || OK == OO_ExclaimEqual;
 }
 
 bool isAccessOperator(OverloadedOperatorKind OK) {
   return isDereferenceOperator(OK) || isIncrementOperator(OK) ||

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

namespace std {
   BidirectionalIterator
   prev (BidirectionalIterator it,
         typename iterator_traits<BidirectionalIterator>::difference_type n =
         1) {
     advance(it, -n);
     return it;
   }
 
+  template <class ForwardIterator>
+  ForwardIterator
+  next (ForwardIterator it,
+        typename iterator_traits<ForwardIterator>::difference_type n =
+        1) {
+    advance(it, n);
+    return it;
+  }
+
   template <class InputIterator, class T>
   InputIterator find(InputIterator first, InputIterator last, const T &val);
 
   template <class ForwardIterator1, class ForwardIterator2>
   ForwardIterator1 find_first_of(ForwardIterator1 first1,
                                  ForwardIterator1 last1,
                                  ForwardIterator2 first2,
                                  ForwardIterator2 last2);

test/Analysis/iterator-range.cpp

while (true) {
     auto item = std::find(start, V.end(), e);
     if (item == V.end())
       break;
     *item;          // no-warning
     start = ++item; // no-warning
   }
 }
 
+void good_advance(std::vector<int> &vec) {
+  auto i = vec.end();
+  std::advance(i, -1);
+  *i; // no-warning
+}
+
+void good_prev(std::vector<int> &vec) {
+  auto i = vec.end();
+  *std::prev(i); // no-warning
+}
+
 void good_push_back(std::list<int> &L, int n) {
   auto i0 = --L.cend();
   L.push_back(n);
   *++i0; // no-warning
 }
 
 void bad_push_back(std::list<int> &L, int n) {
   auto i0 = --L.cend();
void bad_decr_begin(const std::list<int> &L) {
   --i0;  // expected-warning{{Iterator decremented ahead of its valid range}}
 }
 
 void good_decr_end(const std::list<int> &L) {
   auto i0 = L.end();
   --i0; // no-warning
 }
 
+void good_decr_end_advance(const std::list<int> &L) {
+  auto i0 = L.end();
+  std::advance(i0, -1); // no-warning
+}
+
+void good_decr_end_prev(const std::list<int> &L) {
+  auto i0 = L.end();
+  auto i1 = std::prev(i0); // no-warning
+}
+
 void bad_incr_end(const std::list<int> &L) {
   auto i0 = L.end();
   ++i0;  // expected-warning{{Iterator incremented behind the past-the-end iterator}}
 }
 
+void bad_decr_end_advance(const std::list<int> &L) {
+  auto i0 = L.end();
+  std::advance(i0, 1);  // expected-warning{{Iterator incremented behind the past-the-end }}
+}
+
+void bad_decr_end_next(const std::list<int> &L) {
+  auto i0 = L.end();
+  auto i1 = std::next(i0);  // expected-warning{{Iterator incremented behind the past-the-end }}
+}
+
 struct simple_iterator_base {
   simple_iterator_base();
   simple_iterator_base(const simple_iterator_base& rhs);
   simple_iterator_base &operator=(const simple_iterator_base& rhs);
   virtual ~simple_iterator_base();
   bool friend operator==(const simple_iterator_base &lhs,
                          const simple_iterator_base &rhs);
   bool friend operator!=(const simple_iterator_base &lhs,