[analyzer] Improve SVal cast from integer to bool using known RangeSet

[ASDenysPetrov]

Summary

Improve SValBuilder::evalCast function in a part of integer to bool cast. Сonvert known SymbolVal RangeSet to ConcreteInt if possible.

[NoQ]

clang/lib/StaticAnalyzer/Core/SValBuilder.cpp

877–879

What was wrong with State->assume(V)? Why make a new function? Is this for optimization only?

[ASDenysPetrov]

Rebased on main.

[ASDenysPetrov]

@NoQ Thanks for your comment.

clang/lib/StaticAnalyzer/Core/SValBuilder.cpp

877–879

Yes, it's created just for avoiding unnecessary work. You are right. I found an appropriate function ProgramState::isNull. I'll replace by it.

[ASDenysPetrov]

Updated due to discussion.

[NoQ]

Great, thanks!

I still have concerns about these functions - isNull, isNonNull etc. They do indeed provide a quick test for nullness that doesn't involve constructing a new program state. This test, however, will never be as precise as constructing a new state. It used to be when RangeConstraintManager boiled down to simple range operations but now that it grew much larger (eg., the newly added support for symbolic == and != that involves tracking equivalence classes), there's really no way to tell whether a state is going to be feasible without running the whole machine and observing its emergent behavior, which is what assume() does. On the other hand i still don't see any indication that assume() is noticeably expensive. So i'm really worried that this is a premature optimization that sacrifices correctness for nothing. So i'm in favor of phasing out these functions entirely and converting all code to always use assume(). This may occasionally involve untangling unwanted recursions but i hope that all recursive-ish operations can be isolated within the constraint manager itself (and possibly in checker's evalAssume() which we can hopefully guard against with runtime assertions).

[steakhal]

I would suggest not merging this patch.

Circumventing the assume machinery could cause potential crashes.
By tracking equivalence classes and whatnot, our solver is becoming more and more capable.

Doing a bifurcation, then realizing that the current path is infeasible had caused some trouble in the past (D88019), and
it still can cause crashes RangeConstraintManager infeasible execution path due to EquivalenceClasses.
Reproducing and debugging these is a real headache. And I think there are more bugs like these lurking inside.

If we want to have a chance to tackle all of these for once and all, we need a common entrypoint for querying assumptions.
Thus, I would suggest not providing an extra API.

@NoQ @vsavchenko What's your take on this?

You could probably put these changes into the assume handler, but that would need really careful evaluation.
If you think it's worth the effort, consider taking a few measurements on several projects.

[vsavchenko]

@steakhal I personally don't see any fundamental problems with this patch

clang/lib/StaticAnalyzer/Core/SValBuilder.cpp

879

nit: LLVM coding standards call for variable names starting with upper-case letters.

[steakhal]

In D97874#2616660, @vsavchenko wrote:

@steakhal I personally don't see any fundamental problems with this patch

Then, I guess, it should be fine :)

[martong]

@ASDenysPetrov I think the dependent patch https://reviews.llvm.org/D97296 is too much and contains unnecessary things for this change.

If you could you please incorporate the minimum needed changes from that patch to here then this patch could land.
If I am not mistaken then we need only the below changes:

SVal evalCastKind(ProgramStateRef State, UndefinedVal V, QualType CastTy,
SVal evalCastSubKind(ProgramStateRef State, nonloc::SymbolVal V,

[ASDenysPetrov]

In D97874#3014922, @martong wrote:

@ASDenysPetrov I think the dependent patch https://reviews.llvm.org/D97296 is too much and contains unnecessary things for this change.

If you could you please incorporate the minimum needed changes from that patch to here then this patch could land.
If I am not mistaken then we need only the below changes:

SVal evalCastKind(ProgramStateRef State, UndefinedVal V, QualType CastTy,
SVal evalCastSubKind(ProgramStateRef State, nonloc::SymbolVal V,

This patch is an old one. I believe it is already irrelevant and has to be reviewed once again by me as an author, since it were a lot of improvements made for ConstraintManager. Indeed it has a big parent revision, which also need a revision. There was my idea about adding a ProgramState inside evalCast to make symbolic values more transparent for casts. Let me mark it as Abandoned for now. I'll return back to it ASAP. Thank you for attention to this.

clang/include/clang/StaticAnalyzer/Core/PathSensitive/ConstraintManager.h

#endif
   ///
   /// Note that a ConstraintManager is not obligated to return a concretized
   /// value for a symbol, even if it is perfectly constrained.
   virtual const llvm::APSInt* getSymVal(ProgramStateRef state,
                                         SymbolRef sym) const {
     return nullptr;
   }
 
+  /// Return pair of booleans for Within and Outside statuses.
+  /// First bool is `true` when SymbolRef range is within the range.
+  /// Second bool is `true` when SymbolRef range is outside the range.
+  /// Return 'false, false' otherwise.
+  ///
+  /// This function acts as `assumeDual` function
+  /// but it does not create any new states.
+  virtual std::pair<bool, bool>
+  isSymValWithinOrOutsideRange(ProgramStateRef state, SymbolRef sym,
+                               llvm::APSInt lower, llvm::APSInt upper) {
+    return {false, false};
+  }
+
   /// Scan all symbols referenced by the constraints. If the symbol is not
   /// alive, remove it.
   virtual ProgramStateRef removeDeadBindings(ProgramStateRef state,
                                                  SymbolReaper& SymReaper) = 0;
 
   virtual void printJson(raw_ostream &Out, ProgramStateRef State,
                          const char *NL, unsigned int Space,
                          bool IsDot) const = 0;

clang/lib/StaticAnalyzer/Core/RangeConstraintManager.cpp

public:
   }
 
   bool canReasonAbout(SVal X) const override;
 
   ConditionTruthVal checkNull(ProgramStateRef State, SymbolRef Sym) override;
 
   const llvm::APSInt *getSymVal(ProgramStateRef State,
                                 SymbolRef Sym) const override;
+  std::pair<bool, bool>
+  isSymValWithinOrOutsideRange(ProgramStateRef State, SymbolRef Sym,
+                               llvm::APSInt lower, llvm::APSInt upper) override;
 
   ProgramStateRef removeDeadBindings(ProgramStateRef State,
                                      SymbolReaper &SymReaper) override;
 
   void printJson(raw_ostream &Out, ProgramStateRef State, const char *NL = "\n",
                  unsigned int Space = 0, bool IsDot = false) const override;
 
   //===------------------------------------------------------------------===//

 }
 
 const llvm::APSInt *RangeConstraintManager::getSymVal(ProgramStateRef St,
                                                       SymbolRef Sym) const {
   const RangeSet *T = getConstraint(St, Sym);
   return T ? T->getConcreteValue() : nullptr;
 }
 
+std::pair<bool, bool> RangeConstraintManager::isSymValWithinOrOutsideRange(
+    ProgramStateRef St, SymbolRef Sym, llvm::APSInt lower, llvm::APSInt upper) {
+  if (const RangeSet *T = getConstraint(St, Sym)) {
+    RangeSet RS = T->Intersect(getBasicVals(), F, lower, upper);
+    return {RS == *T, RS.isEmpty()};
+  }
+  return {false, false};
+}
+
 //===----------------------------------------------------------------------===//
 //                Remove dead symbols from existing constraints
 //===----------------------------------------------------------------------===//
 
 /// Scan all symbols referenced by the constraints. If the symbol is not alive
 /// as marked in LSymbols, mark it as dead in DSymbols.
 ProgramStateRef
 RangeConstraintManager::removeDeadBindings(ProgramStateRef State,

clang/lib/StaticAnalyzer/Core/SValBuilder.cpp

 
 SVal SValBuilder::evalCastSubKind(ProgramStateRef State, nonloc::SymbolVal V,
                                   QualType CastTy, QualType OriginalTy) {
   SymbolRef SE = V.getSymbol();
 
   // Symbol to bool.
   if (!OriginalTy.isNull() && CastTy->isBooleanType()) {
     // Non-float to bool.
-    if (Loc::isLocType(OriginalTy) ||
-        OriginalTy->isIntegralOrEnumerationType() ||
-        OriginalTy->isMemberPointerType()) {
+    if (OriginalTy->isIntegralOrEnumerationType()) {
       BasicValueFactory &BVF = getBasicValueFactory();
-      return makeNonLoc(SE, BO_NE, BVF.getValue(0, SE->getType()), CastTy);
+      const llvm::APSInt &Zero = BVF.getValue(0, OriginalTy);
+      bool IsZero, IsNotZero;
+      std::tie(IsZero, IsNotZero) =
+          getStateManager().getConstraintManager().isSymValWithinOrOutsideRange(
+              State, SE, Zero, Zero);
+      // Symbolic pointer, integer to bool.
+      if (IsZero || IsNotZero)
+        return makeTruthVal(IsNotZero, CastTy);
+      // Symbolic integer to bool.
+      return V;
     }
   } else {
     // Symbol to integer.
     if (!OriginalTy.isNull() && CastTy->isIntegralOrEnumerationType()) {
       // Symbolic integer to integer.
       if (OriginalTy->isIntegralOrEnumerationType()) {
         // Truncation.
         if (getContext().getTypeSize(CastTy) <

clang/test/Analysis/cast_symbolic_ints_to_bool.cpp

+// RUN: %clang_analyze_cc1 -analyzer-checker=core,debug.ExprInspection -verify %s
+
+template <typename T>
+void clang_analyzer_dump(T);
+
+void test_int_to_bool(bool b, int x) {
+  clang_analyzer_dump(b); // expected-warning{{reg_$0<_Bool b>}}
+  b = x;
+  clang_analyzer_dump(b); // expected-warning{{reg_$1<int x>}}
+  if (x < 0) {
+    b = x;
+    clang_analyzer_dump(b); // expected-warning{{1 U1b}}
+  } else if (x > 0) {
+    b = x;
+    clang_analyzer_dump(b); // expected-warning{{1 U1b}}
+  } else {
+    b = x;
+    clang_analyzer_dump(b); // expected-warning{{0 U1b}}
+  }
+}
+
+void test_char_to_bool(char x) {
+  bool b = x;
+  clang_analyzer_dump(b); // expected-warning{{reg_$0<char x>}}
+  if (x < 0) {
+    bool b = x;
+    clang_analyzer_dump(b); // expected-warning{{1 U1b}}
+  } else if (x > 0) {
+    bool b = x;
+    clang_analyzer_dump(b); // expected-warning{{1 U1b}}
+  } else {
+    bool b = x;
+    clang_analyzer_dump(b); // expected-warning{{0 U1b}}
+  }
+}
+
+void test_unsigned_to_bool(bool b, unsigned x) {
+  clang_analyzer_dump(b); // expected-warning{{reg_$0<_Bool b>}}
+  b = x;
+  clang_analyzer_dump(b); // expected-warning{{reg_$1<unsigned int x>}}
+  if (x) {
+    b = x;
+    clang_analyzer_dump(b); // expected-warning{{1 U1b}}
+  } else {
+    b = x;
+    clang_analyzer_dump(b); // expected-warning{{0 U1b}}
+  }
+}
+
+void test_unsigned_to_bool(unsigned char x) {
+  bool b = x;
+  clang_analyzer_dump(b); // expected-warning{{reg_$0<unsigned char x>}}
+  if (x < 42) {
+    b = x;
+    clang_analyzer_dump(b); // expected-warning{{reg_$0<unsigned char x>}}
+    if (x) {
+      b = x;
+      clang_analyzer_dump(b); // expected-warning{{1 U1b}}
+    } else {
+      b = x;
+      clang_analyzer_dump(b); // expected-warning{{0 U1b}}
+    }
+  } else {
+    b = x;
+    clang_analyzer_dump(b); // expected-warning{{1 U1b}}
+  }
+}