[Analyzer] Fix for iterator modeling and checkers: handle negative numbers correctly

[baloghadamsoftware]

Summary

Currently, using negative numbers in iterator operations (additions and subractions) results in advancements with huge positive numbers due to an error. This patch fixes it.

[Szelethus]

This patch is a good testament to how well those debug functions turned out. LGTM.

clang/lib/StaticAnalyzer/Checkers/Iterator.cpp

203

Don't use auto here.

clang/lib/StaticAnalyzer/Checkers/Iterator.cpp

ProgramStateRef advancePosition(ProgramStateRef State, const SVal &Iter,
                                 OverloadedOperatorKind Op,
                                 const SVal &Distance) {
   const auto *Pos = getIteratorPosition(State, Iter);
   if (!Pos)
     return nullptr;
 
   auto &SymMgr = State->getStateManager().getSymbolManager();
   auto &SVB = State->getStateManager().getSValBuilder();
+  auto &BVF = State->getStateManager().getBasicVals();
 
   assert ((Op == OO_Plus || Op == OO_PlusEqual ||
            Op == OO_Minus || Op == OO_MinusEqual) &&
           "Advance operator must be one of +, -, += and -=.");
   auto BinOp = (Op == OO_Plus || Op == OO_PlusEqual) ? BO_Add : BO_Sub;
-  if (const auto IntDist = Distance.getAs<nonloc::ConcreteInt>()) {
-    // For concrete integers we can calculate the new position
-    const auto NewPos =
-      Pos->setTo(SVB.evalBinOp(State, BinOp,
-                               nonloc::SymbolVal(Pos->getOffset()),
-                               *IntDist, SymMgr.getType(Pos->getOffset()))
-                 .getAsSymbol());
-    return setIteratorPosition(State, Iter, NewPos);
-  }
+  const auto IntDistOp = Distance.getAs<nonloc::ConcreteInt>();
+  if (!IntDistOp)
+    return nullptr;
+
+  nonloc::ConcreteInt IntDist = *IntDistOp;
+
+  if (IntDist.getValue().isNegative()) {
+    IntDist = nonloc::ConcreteInt(BVF.getValue(-IntDist.getValue()));
+    BinOp = (BinOp == BO_Add) ? BO_Sub : BO_Add;
+  }
+                             IntDist, SymMgr.getType(Pos->getOffset()))
 
-  return nullptr;
-}
-
 // 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?
 ProgramStateRef assumeNoOverflow(ProgramStateRef State, SymbolRef Sym,

clang/test/Analysis/iterator-modelling.cpp

void plus_equal(const std::vector<int> &v) {
 
   clang_analyzer_denote(clang_analyzer_container_begin(v), "$v.begin()");
 
   i += 2;
 
   clang_analyzer_express(clang_analyzer_iterator_position(i)); //expected-warning{{$v.begin() + 2}}
 }
 
+void plus_equal_negative(const std::vector<int> &v) {
+  auto i = v.end();
+
+  clang_analyzer_denote(clang_analyzer_container_end(v), "$v.end()");
+
+  i += -2;
+
+  clang_analyzer_express(clang_analyzer_iterator_position(i)); //expected-warning{{$v.end() - 2}}
+}
+
 void minus_equal(const std::vector<int> &v) {
   auto i = v.end();
 
   clang_analyzer_denote(clang_analyzer_container_end(v), "$v.end()");
 
   i -= 2;
 
   clang_analyzer_express(clang_analyzer_iterator_position(i)); //expected-warning{{$v.end() - 2}}
 }
 
+void minus_equal_negative(const std::vector<int> &v) {
+  auto i = v.begin();
+
+  clang_analyzer_denote(clang_analyzer_container_begin(v), "$v.begin()");
+
+  i -= -2;
+
+  clang_analyzer_express(clang_analyzer_iterator_position(i)); //expected-warning{{$v.begin() + 2}}
+}
+
 void copy(const std::vector<int> &v) {
   auto i1 = v.end();
 
   clang_analyzer_denote(clang_analyzer_container_end(v), "$v.end()");
 
   auto i2 = i1;
 
   clang_analyzer_eval(clang_analyzer_iterator_container(i2) == &v); // expected-warning{{TRUE}}
   clang_analyzer_express(clang_analyzer_iterator_position(i2)); //expected-warning{{$v.end()}}
 }
 
 void plus(const std::vector<int> &v) {
   auto i1 = v.begin();
 
   clang_analyzer_denote(clang_analyzer_container_begin(v), "$v.begin()");
 
   auto i2 = i1 + 2;
 
   clang_analyzer_eval(clang_analyzer_iterator_container(i2) == &v); // expected-warning{{TRUE}}
   clang_analyzer_express(clang_analyzer_iterator_position(i2)); //expected-warning{{$v.begin() + 2}}
 }
 
+void plus_negative(const std::vector<int> &v) {
+  auto i1 = v.end();
+
+  clang_analyzer_denote(clang_analyzer_container_end(v), "$v.end()");
+
+  auto i2 = i1 + (-2);
+
+  clang_analyzer_eval(clang_analyzer_iterator_container(i2) == &v); // expected-warning{{TRUE}}
+  clang_analyzer_express(clang_analyzer_iterator_position(i2)); //expected-warning{{$v.end() - 2}}
+}
+
 void minus(const std::vector<int> &v) {
   auto i1 = v.end();
 
   clang_analyzer_denote(clang_analyzer_container_end(v), "$v.end()");
 
   auto i2 = i1 - 2;
 
   clang_analyzer_eval(clang_analyzer_iterator_container(i2) == &v); // expected-warning{{TRUE}}
   clang_analyzer_express(clang_analyzer_iterator_position(i2)); //expected-warning{{$v.end() - 2}}
 }
 
+void minus_negative(const std::vector<int> &v) {
+  auto i1 = v.begin();
+
+  clang_analyzer_denote(clang_analyzer_container_begin(v), "$v.begin()");
+
+  auto i2 = i1 - (-2);
+
+  clang_analyzer_eval(clang_analyzer_iterator_container(i2) == &v); // expected-warning{{TRUE}}
+  clang_analyzer_express(clang_analyzer_iterator_position(i2)); //expected-warning{{$v.begin() + 2}}
+}
+
 void copy_and_increment1(const std::vector<int> &v) {
   auto i1 = v.begin();
 
   clang_analyzer_denote(clang_analyzer_container_begin(v), "$v.begin()");
 
   auto i2 = i1;
   ++i1;