[analyzer] Implement assumeInclusiveRange in terms of assumeInclusiveRangeDual

[martong]

Summary

Depends on D124758. This is the very same thing we have done for
assumeDual, but this time we do it for assumeInclusiveRange. This patch
is basically a no-brainer copy of that previous patch.

[steakhal]

Okay, it took me a while to get what's going on.
Do you have anything in mind to express it by slightly less indirection, references, templates and well, virtual functions xD

[martong]

In D125892#3523296, @steakhal wrote:

Okay, it took me a while to get what's going on.
Do you have anything in mind to express it by slightly less indirection, references, templates and well, virtual functions xD

Okay, I see your point. Therefore, I am splitting up this patch into two:

1. The no-brainer copy-paste from assumeDual implementaton.
2. An NFC that tries to eliminate the copy paste coding. Efficiency and performance discussions should go there.

[martong]

• Split into two patches, this first patch will be just the no-brainer copy-paste from assumeDual implementaton.

[steakhal]

Now I see, the summary confused me.

This includes the refactoring of the common assumle*Dual logic into the
function template assumeDualImpl.

I felt like this is a refactoring change, but it was not. It's about fixing the behavior by using the cloneAsPosteriorlyOverconstrained().
Please reword the summary.

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

36–37

Why is this in the public: section, if the name of it suggests its a detail?

[martong]

• Move SimpleConstraintManager's assume*Internal functions to be protected

[martong]

In D125892#3524453, @steakhal wrote:

Now I see, the summary confused me.

This includes the refactoring of the common assumle*Dual logic into the
function template assumeDualImpl.

I felt like this is a refactoring change, but it was not. It's about fixing the behavior by using the cloneAsPosteriorlyOverconstrained().
Please reword the summary.

Ok, done.

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

36–37

Good point. I moved them under protected:.

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

public:
 
   /// Returns a pair of states (StTrue, StFalse) where the given condition is
   /// assumed to be true or false, respectively.
   /// (Note that these two states might be equal if the parent state turns out
   /// to be infeasible. This may happen if the underlying constraint solver is
   /// not perfectly precise and this may happen very rarely.)
   ProgramStatePair assumeDual(ProgramStateRef State, DefinedSVal Cond);
 
-  virtual ProgramStateRef assumeInclusiveRange(ProgramStateRef State,
-                                               NonLoc Value,
-                                               const llvm::APSInt &From,
-                                               const llvm::APSInt &To,
-                                               bool InBound) = 0;
+  ProgramStateRef assumeInclusiveRange(ProgramStateRef State, NonLoc Value,
+                                       const llvm::APSInt &To, bool InBound);
 
-  virtual ProgramStatePair assumeInclusiveRangeDual(ProgramStateRef State,
-                                                    NonLoc Value,
-                                                    const llvm::APSInt &From,
-                                                    const llvm::APSInt &To) {
-    ProgramStateRef StInRange =
-        assumeInclusiveRange(State, Value, From, To, true);
-
-    // If StTrue is infeasible, asserting the falseness of Cond is unnecessary
-    // because the existing constraints already establish this.
-    if (!StInRange)
-      return ProgramStatePair((ProgramStateRef)nullptr, State);
-
-    ProgramStateRef StOutOfRange =
-        assumeInclusiveRange(State, Value, From, To, false);
-    if (!StOutOfRange) {
-      // We are careful to return the original state, /not/ StTrue,
-      // because we want to avoid having callers generate a new node
-      // in the ExplodedGraph.
-      return ProgramStatePair(State, (ProgramStateRef)nullptr);
-    }
-
-    return ProgramStatePair(StInRange, StOutOfRange);
-  }
+  /// Returns a pair of states (StInRange, StOutOfRange) where the given value
+  /// is assumed to be in the range or out of the range, respectively.
+  /// (Note that these two states might be equal if the parent state turns out
+  /// to be infeasible. This may happen if the underlying constraint solver is
+  /// not perfectly precise and this may happen very rarely.)
+  ProgramStatePair assumeInclusiveRangeDual(ProgramStateRef State, NonLoc Value,
+                                            const llvm::APSInt &To);
 
   /// If a symbol is perfectly constrained to a constant, attempt
   /// to return the concrete value.
   ///
   /// 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 {
protected:
   ///
   /// Note that this flag allows the ConstraintManager to be re-entrant,
   /// but not thread-safe.
   bool NotifyAssumeClients = true;
 
   virtual ProgramStateRef assumeInternal(ProgramStateRef state,
                                          DefinedSVal Cond, bool Assumption) = 0;
 
+  virtual ProgramStateRef assumeInclusiveRangeInternal(ProgramStateRef State,
+                                                       NonLoc Value,
+                                                       const llvm::APSInt &From,
+                                                       const llvm::APSInt &To,
+                                                       bool InBound) = 0;
+
   /// canReasonAbout - Not all ConstraintManagers can accurately reason about
   ///  all SVal values.  This method returns true if the ConstraintManager can
   ///  reasonably handle a given SVal value.  This is typically queried by
   ///  ExprEngine to determine if the value should be replaced with a
   ///  conjured symbolic value in order to recover some precision.
   virtual bool canReasonAbout(SVal X) const = 0;
 
   /// Returns whether or not a symbol is known to be null ("true"), known to be

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

public:
   SimpleConstraintManager(ExprEngine *exprengine, SValBuilder &SB)
       : EE(exprengine), SVB(SB) {}
 
   ~SimpleConstraintManager() override;
 
   //===------------------------------------------------------------------===//
   // Implementation for interface from ConstraintManager.
   //===------------------------------------------------------------------===//
 
-  /// Ensures that the DefinedSVal conditional is expressed as a NonLoc by
-  /// creating boolean casts to handle Loc's.
-  ProgramStateRef assumeInternal(ProgramStateRef State, DefinedSVal Cond,
-                                 bool Assumption) override;
-
-  ProgramStateRef assumeInclusiveRange(ProgramStateRef State, NonLoc Value,
-                                       const llvm::APSInt &From,
-                                       const llvm::APSInt &To,
-                                       bool InRange) override;
-
 protected:
   //===------------------------------------------------------------------===//
   // Interface that subclasses must implement.
   //===------------------------------------------------------------------===//
 
   /// Given a symbolic expression that can be reasoned about, assume that it is
   /// true/false and generate the new program state.
   virtual ProgramStateRef assumeSym(ProgramStateRef State, SymbolRef Sym,
                                     bool Assumption) = 0;
protected:
   virtual ProgramStateRef assumeSymUnsupported(ProgramStateRef State,
                                                SymbolRef Sym,
                                                bool Assumption) = 0;
 
   //===------------------------------------------------------------------===//
   // Internal implementation.
   //===------------------------------------------------------------------===//
 
+  /// Ensures that the DefinedSVal conditional is expressed as a NonLoc by
+  /// creating boolean casts to handle Loc's.
+  ProgramStateRef assumeInternal(ProgramStateRef State, DefinedSVal Cond,
+                                 bool Assumption) override;
+
+  ProgramStateRef assumeInclusiveRangeInternal(ProgramStateRef State,
+                                               NonLoc Value,
+                                               const llvm::APSInt &From,
+                                               const llvm::APSInt &To,
+                                               bool InRange) override;
+
   SValBuilder &getSValBuilder() const { return SVB; }
   BasicValueFactory &getBasicVals() const { return SVB.getBasicValueFactory(); }
   SymbolManager &getSymbolManager() const { return SVB.getSymbolManager(); }
 
 private:
   ProgramStateRef assume(ProgramStateRef State, NonLoc Cond, bool Assumption);
 
   ProgramStateRef assumeAux(ProgramStateRef State, NonLoc Cond,
                             bool Assumption);
 };
 
 } // end namespace ento
 
 } // end namespace clang
 
 #endif

clang/lib/StaticAnalyzer/Core/ConstraintManager.cpp

ConstraintManager::assumeDual(ProgramStateRef State, DefinedSVal Cond) {
   ProgramStateRef StFalse = assumeInternal(State, Cond, false);
   if (!StFalse) {
     return ProgramStatePair(StTrue, nullptr);
   }
 
   return ProgramStatePair(StTrue, StFalse);
 }
 
+ConstraintManager::ProgramStatePair
+ConstraintManager::assumeInclusiveRangeDual(ProgramStateRef State, NonLoc Value,
+                                            const llvm::APSInt &From,
+                                            const llvm::APSInt &To) {
+  ProgramStateRef StInRange =
+      assumeInclusiveRangeInternal(State, Value, From, To, true);
+  if (!StInRange) {
+    ProgramStateRef StOutOfRange =
+        assumeInclusiveRangeInternal(State, Value, From, To, false);
+    if (LLVM_UNLIKELY(!StOutOfRange)) { // both infeasible
+      ProgramStateRef StInfeasible = State->cloneAsPosteriorlyOverconstrained();
+      assert(StInfeasible->isPosteriorlyOverconstrained());
+      // Checkers might rely on the API contract that both returned states
+      // cannot be null. Thus, we return StInfeasible for both branches because
+      // it might happen that a Checker uncoditionally uses one of them if the
+      // other is a nullptr. This may also happen with the non-dual and
+      // adjacent `assume(true)` and `assume(false)` calls. By implementing
+      // assume in therms of assumeDual, we can keep our API contract there as
+      // well.
+      return ProgramStatePair(StInfeasible, StInfeasible);
+    }
+  }
+
+  ProgramStateRef StOutOfRange =
+      assumeInclusiveRangeInternal(State, Value, From, To, false);
+  if (!StOutOfRange) {
+    return ProgramStatePair(StInRange, nullptr);
+  }
+
+  return ProgramStatePair(StInRange, StOutOfRange);
+}
+
 ProgramStateRef ConstraintManager::assume(ProgramStateRef State,
                                           DefinedSVal Cond, bool Assumption) {
   ConstraintManager::ProgramStatePair R = assumeDual(State, Cond);
   return Assumption ? R.first : R.second;
 }
+
+ProgramStateRef
+ConstraintManager::assumeInclusiveRange(ProgramStateRef State, NonLoc Value,
+                                        const llvm::APSInt &From,
+                                        const llvm::APSInt &To, bool InBound) {
+  ConstraintManager::ProgramStatePair R =
+      assumeInclusiveRangeDual(State, Value, From, To);
+  return InBound ? R.first : R.second;
+}

clang/lib/StaticAnalyzer/Core/SimpleConstraintManager.cpp

ProgramStateRef SimpleConstraintManager::assumeAux(ProgramStateRef State,
   }
 
   case nonloc::LocAsIntegerKind:
     return assumeInternal(State, Cond.castAs<nonloc::LocAsInteger>().getLoc(),
                           Assumption);
   } // end switch
 }
 
-ProgramStateRef SimpleConstraintManager::assumeInclusiveRange(
+ProgramStateRef SimpleConstraintManager::assumeInclusiveRangeInternal(
     ProgramStateRef State, NonLoc Value, const llvm::APSInt &From,
     const llvm::APSInt &To, bool InRange) {
 
   assert(From.isUnsigned() == To.isUnsigned() &&
          From.getBitWidth() == To.getBitWidth() &&
          "Values should have same types!");
 
   if (!canReasonAbout(Value)) {