[Analyzer] Iterator Checkers: Replace `UnknownVal` in comparison result by a conjured value

[baloghadamsoftware]

Summary

Sometimes the return value of a comparison operator call is UnkownVal. Since no assumptions can be made on UnknownVal, this leeds to keeping impossible execution paths in the exploded graph resulting in poor performance and false positives. To overcome this we replace unknown results of iterator comparisons by conjured symbols.

[baloghadamsoftware]

@NoQ, @Szelethus What about this patch? It is an essential bugfix.

[NoQ]

That's a fair point, these days we always have to account for unknown values.

I'm still curious (for science!) about how exactly it came to be in the tests.

clang/lib/StaticAnalyzer/Checkers/IteratorModeling.cpp

 using namespace iterator;
 
 namespace {
 
 class IteratorModeling
     : public Checker<check::PostCall, check::PostStmt<MaterializeTemporaryExpr>,
                      check::Bind, check::LiveSymbols, check::DeadSymbols> {
 
-  void handleComparison(CheckerContext &C, const Expr *CE, const SVal &RetVal,
+  void handleComparison(CheckerContext &C, const Expr *CE, SVal RetVal,
                         const SVal &LVal, const SVal &RVal,
                         OverloadedOperatorKind Op) const;
   void processComparison(CheckerContext &C, ProgramStateRef State,
                          SymbolRef Sym1, SymbolRef Sym2, const 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,
if (!SR.isLiveRegion(Cont.first)) {
       }
     }
   }
 
   C.addTransition(State);
 }
 
 void IteratorModeling::handleComparison(CheckerContext &C, const Expr *CE,
-                                        const SVal &RetVal, const SVal &LVal,
-                                        const SVal &RVal,
-                                        OverloadedOperatorKind Op) const {
+                                       SVal RetVal, const SVal &LVal,
   // 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;
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);
   }
 
+  // We cannot make assumpotions 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);
 }
 
 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 {
       C.generateSink(State, C.getPredecessor());
     }
     return;
   }
 
   const auto ConditionVal = RetVal.getAs<DefinedSVal>();
   if (!ConditionVal)
     return;
-  
   if (auto StateTrue = relateSymbols(State, Sym1, Sym2, Op == OO_EqualEqual)) {
     StateTrue = StateTrue->assume(*ConditionVal, true);
     C.addTransition(StateTrue);
   }
   
   if (auto StateFalse = relateSymbols(State, Sym1, Sym2, Op != OO_EqualEqual)) {
     StateFalse = StateFalse->assume(*ConditionVal, false);
     C.addTransition(StateFalse);

clang/test/Analysis/invalidated-iterator.cpp

void invalidated_subscript(std::vector<int> &V) {
   i[1]; // expected-warning{{Invalidated iterator accessed}}
 }
 
 void assignment(std::vector<int> &V) {
   auto i = V.cbegin();
   V.erase(i);
   auto j = V.cbegin(); // no-warning
 }
-

clang/test/Analysis/iterator-modelling.cpp

InputIterator nonStdFind(InputIterator first, InputIterator last,
   return last;
 }
 
 void non_std_find(std::vector<int> &V, int e) {
   auto first = nonStdFind(V.begin(), V.end(), e);
   clang_analyzer_eval(clang_analyzer_container_end(V) ==
                       clang_analyzer_iterator_position(first)); // expected-warning@-1{{FALSE}} expected-warning@-1{{TRUE}}
   if (V.end() != first) {
-      clang_analyzer_eval(clang_analyzer_container_end(V) ==
-                        clang_analyzer_iterator_position(first)); // expected-warning@-1{{FALSE}} expected-warning@-1 0-1{{TRUE}} FIXME: should only expect FALSE in every case
+                        clang_analyzer_iterator_position(first)); // expected-warning@-1{{FALSE}}
   }
 }
 
 void clang_analyzer_printState();
 
 void print_state(std::vector<int> &V) {
   const auto i0 = V.cbegin();
   clang_analyzer_printState();