contrib/llvm-project/clang/lib/StaticAnalyzer/Core/RangeConstraintManager.cpp

   1 //== RangeConstraintManager.cpp - Manage range constraints.------*- C++ -*--==//
   2 //
   3 // Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.
   4 // See https://llvm.org/LICENSE.txt for license information.
   5 // SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception
   6 //
   7 //===----------------------------------------------------------------------===//
   8 //
   9 //  This file defines RangeConstraintManager, a class that tracks simple
  10 //  equality and inequality constraints on symbolic values of ProgramState.
  11 //
  12 //===----------------------------------------------------------------------===//
  13
  14 #include "clang/Basic/JsonSupport.h"
  15 #include "clang/StaticAnalyzer/Core/PathSensitive/APSIntType.h"
  16 #include "clang/StaticAnalyzer/Core/PathSensitive/ProgramState.h"
  17 #include "clang/StaticAnalyzer/Core/PathSensitive/ProgramStateTrait.h"
  18 #include "clang/StaticAnalyzer/Core/PathSensitive/RangedConstraintManager.h"
  19 #include "llvm/ADT/FoldingSet.h"
  20 #include "llvm/ADT/ImmutableSet.h"
  21 #include "llvm/Support/raw_ostream.h"
  22
  23 using namespace clang;
  24 using namespace ento;
  25
  26 void RangeSet::IntersectInRange(BasicValueFactory &BV, Factory &F,
  27                       const llvm::APSInt &Lower, const llvm::APSInt &Upper,
  28                       PrimRangeSet &newRanges, PrimRangeSet::iterator &i,
  29                       PrimRangeSet::iterator &e) const {
  30   // There are six cases for each range R in the set:
  31   //   1. R is entirely before the intersection range.
  32   //   2. R is entirely after the intersection range.
  33   //   3. R contains the entire intersection range.
  34   //   4. R starts before the intersection range and ends in the middle.
  35   //   5. R starts in the middle of the intersection range and ends after it.
  36   //   6. R is entirely contained in the intersection range.
  37   // These correspond to each of the conditions below.
  38   for (/* i = begin(), e = end() */; i != e; ++i) {
  39     if (i->To() < Lower) {
  40       continue;
  41     }
  42     if (i->From() > Upper) {
  43       break;
  44     }
  45
  46     if (i->Includes(Lower)) {
  47       if (i->Includes(Upper)) {
  48         newRanges =
  49             F.add(newRanges, Range(BV.getValue(Lower), BV.getValue(Upper)));
  50         break;
  51       } else
  52         newRanges = F.add(newRanges, Range(BV.getValue(Lower), i->To()));
  53     } else {
  54       if (i->Includes(Upper)) {
  55         newRanges = F.add(newRanges, Range(i->From(), BV.getValue(Upper)));
  56         break;
  57       } else
  58         newRanges = F.add(newRanges, *i);
  59     }
  60   }
  61 }
  62
  63 const llvm::APSInt &RangeSet::getMinValue() const {
  64   assert(!isEmpty());
  65   return ranges.begin()->From();
  66 }
  67
  68 bool RangeSet::pin(llvm::APSInt &Lower, llvm::APSInt &Upper) const {
  69   // This function has nine cases, the cartesian product of range-testing
  70   // both the upper and lower bounds against the symbol's type.
  71   // Each case requires a different pinning operation.
  72   // The function returns false if the described range is entirely outside
  73   // the range of values for the associated symbol.
  74   APSIntType Type(getMinValue());
  75   APSIntType::RangeTestResultKind LowerTest = Type.testInRange(Lower, true);
  76   APSIntType::RangeTestResultKind UpperTest = Type.testInRange(Upper, true);
  77
  78   switch (LowerTest) {
  79   case APSIntType::RTR_Below:
  80     switch (UpperTest) {
  81     case APSIntType::RTR_Below:
  82       // The entire range is outside the symbol's set of possible values.
  83       // If this is a conventionally-ordered range, the state is infeasible.
  84       if (Lower <= Upper)
  85         return false;
  86
  87       // However, if the range wraps around, it spans all possible values.
  88       Lower = Type.getMinValue();
  89       Upper = Type.getMaxValue();
  90       break;
  91     case APSIntType::RTR_Within:
  92       // The range starts below what's possible but ends within it. Pin.
  93       Lower = Type.getMinValue();
  94       Type.apply(Upper);
  95       break;
  96     case APSIntType::RTR_Above:
  97       // The range spans all possible values for the symbol. Pin.
  98       Lower = Type.getMinValue();
  99       Upper = Type.getMaxValue();
 100       break;
 101     }
 102     break;
 103   case APSIntType::RTR_Within:
 104     switch (UpperTest) {
 105     case APSIntType::RTR_Below:
 106       // The range wraps around, but all lower values are not possible.
 107       Type.apply(Lower);
 108       Upper = Type.getMaxValue();
 109       break;
 110     case APSIntType::RTR_Within:
 111       // The range may or may not wrap around, but both limits are valid.
 112       Type.apply(Lower);
 113       Type.apply(Upper);
 114       break;
 115     case APSIntType::RTR_Above:
 116       // The range starts within what's possible but ends above it. Pin.
 117       Type.apply(Lower);
 118       Upper = Type.getMaxValue();
 119       break;
 120     }
 121     break;
 122   case APSIntType::RTR_Above:
 123     switch (UpperTest) {
 124     case APSIntType::RTR_Below:
 125       // The range wraps but is outside the symbol's set of possible values.
 126       return false;
 127     case APSIntType::RTR_Within:
 128       // The range starts above what's possible but ends within it (wrap).
 129       Lower = Type.getMinValue();
 130       Type.apply(Upper);
 131       break;
 132     case APSIntType::RTR_Above:
 133       // The entire range is outside the symbol's set of possible values.
 134       // If this is a conventionally-ordered range, the state is infeasible.
 135       if (Lower <= Upper)
 136         return false;
 137
 138       // However, if the range wraps around, it spans all possible values.
 139       Lower = Type.getMinValue();
 140       Upper = Type.getMaxValue();
 141       break;
 142     }
 143     break;
 144   }
 145
 146   return true;
 147 }
 148
 149 // Returns a set containing the values in the receiving set, intersected with
 150 // the closed range [Lower, Upper]. Unlike the Range type, this range uses
 151 // modular arithmetic, corresponding to the common treatment of C integer
 152 // overflow. Thus, if the Lower bound is greater than the Upper bound, the
 153 // range is taken to wrap around. This is equivalent to taking the
 154 // intersection with the two ranges [Min, Upper] and [Lower, Max],
 155 // or, alternatively, /removing/ all integers between Upper and Lower.
 156 RangeSet RangeSet::Intersect(BasicValueFactory &BV, Factory &F,
 157                              llvm::APSInt Lower, llvm::APSInt Upper) const {
 158   if (!pin(Lower, Upper))
 159     return F.getEmptySet();
 160
 161   PrimRangeSet newRanges = F.getEmptySet();
 162
 163   PrimRangeSet::iterator i = begin(), e = end();
 164   if (Lower <= Upper)
 165     IntersectInRange(BV, F, Lower, Upper, newRanges, i, e);
 166   else {
 167     // The order of the next two statements is important!
 168     // IntersectInRange() does not reset the iteration state for i and e.
 169     // Therefore, the lower range most be handled first.
 170     IntersectInRange(BV, F, BV.getMinValue(Upper), Upper, newRanges, i, e);
 171     IntersectInRange(BV, F, Lower, BV.getMaxValue(Lower), newRanges, i, e);
 172   }
 173
 174   return newRanges;
 175 }
 176
 177 // Returns a set containing the values in the receiving set, intersected with
 178 // the range set passed as parameter.
 179 RangeSet RangeSet::Intersect(BasicValueFactory &BV, Factory &F,
 180                              const RangeSet &Other) const {
 181   PrimRangeSet newRanges = F.getEmptySet();
 182
 183   for (iterator i = Other.begin(), e = Other.end(); i != e; ++i) {
 184     RangeSet newPiece = Intersect(BV, F, i->From(), i->To());
 185     for (iterator j = newPiece.begin(), ee = newPiece.end(); j != ee; ++j) {
 186       newRanges = F.add(newRanges, *j);
 187     }
 188   }
 189
 190   return newRanges;
 191 }
 192
 193 // Turn all [A, B] ranges to [-B, -A]. Ranges [MIN, B] are turned to range set
 194 // [MIN, MIN] U [-B, MAX], when MIN and MAX are the minimal and the maximal
 195 // signed values of the type.
 196 RangeSet RangeSet::Negate(BasicValueFactory &BV, Factory &F) const {
 197   PrimRangeSet newRanges = F.getEmptySet();
 198
 199   for (iterator i = begin(), e = end(); i != e; ++i) {
 200     const llvm::APSInt &from = i->From(), &to = i->To();
 201     const llvm::APSInt &newTo = (from.isMinSignedValue() ?
 202                                  BV.getMaxValue(from) :
 203                                  BV.getValue(- from));
 204     if (to.isMaxSignedValue() && !newRanges.isEmpty() &&
 205         newRanges.begin()->From().isMinSignedValue()) {
 206       assert(newRanges.begin()->To().isMinSignedValue() &&
 207              "Ranges should not overlap");
 208       assert(!from.isMinSignedValue() && "Ranges should not overlap");
 209       const llvm::APSInt &newFrom = newRanges.begin()->From();
 210       newRanges =
 211         F.add(F.remove(newRanges, *newRanges.begin()), Range(newFrom, newTo));
 212     } else if (!to.isMinSignedValue()) {
 213       const llvm::APSInt &newFrom = BV.getValue(- to);
 214       newRanges = F.add(newRanges, Range(newFrom, newTo));
 215     }
 216     if (from.isMinSignedValue()) {
 217       newRanges = F.add(newRanges, Range(BV.getMinValue(from),
 218                                          BV.getMinValue(from)));
 219     }
 220   }
 221
 222   return newRanges;
 223 }
 224
 225 void RangeSet::print(raw_ostream &os) const {
 226   bool isFirst = true;
 227   os << "{ ";
 228   for (iterator i = begin(), e = end(); i != e; ++i) {
 229     if (isFirst)
 230       isFirst = false;
 231     else
 232       os << ", ";
 233
 234     os << '[' << i->From().toString(10) << ", " << i->To().toString(10)
 235        << ']';
 236   }
 237   os << " }";
 238 }
 239
 240 namespace {
 241 class RangeConstraintManager : public RangedConstraintManager {
 242 public:
 243   RangeConstraintManager(SubEngine *SE, SValBuilder &SVB)
 244       : RangedConstraintManager(SE, SVB) {}
 245
 246   //===------------------------------------------------------------------===//
 247   // Implementation for interface from ConstraintManager.
 248   //===------------------------------------------------------------------===//
 249
 250   bool haveEqualConstraints(ProgramStateRef S1,
 251                             ProgramStateRef S2) const override {
 252     return S1->get<ConstraintRange>() == S2->get<ConstraintRange>();
 253   }
 254
 255   bool canReasonAbout(SVal X) const override;
 256
 257   ConditionTruthVal checkNull(ProgramStateRef State, SymbolRef Sym) override;
 258
 259   const llvm::APSInt *getSymVal(ProgramStateRef State,
 260                                 SymbolRef Sym) const override;
 261
 262   ProgramStateRef removeDeadBindings(ProgramStateRef State,
 263                                      SymbolReaper &SymReaper) override;
 264
 265   void printJson(raw_ostream &Out, ProgramStateRef State, const char *NL = "\n",
 266                  unsigned int Space = 0, bool IsDot = false) const override;
 267
 268   //===------------------------------------------------------------------===//
 269   // Implementation for interface from RangedConstraintManager.
 270   //===------------------------------------------------------------------===//
 271
 272   ProgramStateRef assumeSymNE(ProgramStateRef State, SymbolRef Sym,
 273                               const llvm::APSInt &V,
 274                               const llvm::APSInt &Adjustment) override;
 275
 276   ProgramStateRef assumeSymEQ(ProgramStateRef State, SymbolRef Sym,
 277                               const llvm::APSInt &V,
 278                               const llvm::APSInt &Adjustment) override;
 279
 280   ProgramStateRef assumeSymLT(ProgramStateRef State, SymbolRef Sym,
 281                               const llvm::APSInt &V,
 282                               const llvm::APSInt &Adjustment) override;
 283
 284   ProgramStateRef assumeSymGT(ProgramStateRef State, SymbolRef Sym,
 285                               const llvm::APSInt &V,
 286                               const llvm::APSInt &Adjustment) override;
 287
 288   ProgramStateRef assumeSymLE(ProgramStateRef State, SymbolRef Sym,
 289                               const llvm::APSInt &V,
 290                               const llvm::APSInt &Adjustment) override;
 291
 292   ProgramStateRef assumeSymGE(ProgramStateRef State, SymbolRef Sym,
 293                               const llvm::APSInt &V,
 294                               const llvm::APSInt &Adjustment) override;
 295
 296   ProgramStateRef assumeSymWithinInclusiveRange(
 297       ProgramStateRef State, SymbolRef Sym, const llvm::APSInt &From,
 298       const llvm::APSInt &To, const llvm::APSInt &Adjustment) override;
 299
 300   ProgramStateRef assumeSymOutsideInclusiveRange(
 301       ProgramStateRef State, SymbolRef Sym, const llvm::APSInt &From,
 302       const llvm::APSInt &To, const llvm::APSInt &Adjustment) override;
 303
 304 private:
 305   RangeSet::Factory F;
 306
 307   RangeSet getRange(ProgramStateRef State, SymbolRef Sym);
 308   const RangeSet* getRangeForMinusSymbol(ProgramStateRef State,
 309                                          SymbolRef Sym);
 310
 311   RangeSet getSymLTRange(ProgramStateRef St, SymbolRef Sym,
 312                          const llvm::APSInt &Int,
 313                          const llvm::APSInt &Adjustment);
 314   RangeSet getSymGTRange(ProgramStateRef St, SymbolRef Sym,
 315                          const llvm::APSInt &Int,
 316                          const llvm::APSInt &Adjustment);
 317   RangeSet getSymLERange(ProgramStateRef St, SymbolRef Sym,
 318                          const llvm::APSInt &Int,
 319                          const llvm::APSInt &Adjustment);
 320   RangeSet getSymLERange(llvm::function_ref<RangeSet()> RS,
 321                          const llvm::APSInt &Int,
 322                          const llvm::APSInt &Adjustment);
 323   RangeSet getSymGERange(ProgramStateRef St, SymbolRef Sym,
 324                          const llvm::APSInt &Int,
 325                          const llvm::APSInt &Adjustment);
 326
 327 };
 328
 329 } // end anonymous namespace
 330
 331 std::unique_ptr<ConstraintManager>
 332 ento::CreateRangeConstraintManager(ProgramStateManager &StMgr, SubEngine *Eng) {
 333   return std::make_unique<RangeConstraintManager>(Eng, StMgr.getSValBuilder());
 334 }
 335
 336 bool RangeConstraintManager::canReasonAbout(SVal X) const {
 337   Optional<nonloc::SymbolVal> SymVal = X.getAs<nonloc::SymbolVal>();
 338   if (SymVal && SymVal->isExpression()) {
 339     const SymExpr *SE = SymVal->getSymbol();
 340
 341     if (const SymIntExpr *SIE = dyn_cast<SymIntExpr>(SE)) {
 342       switch (SIE->getOpcode()) {
 343       // We don't reason yet about bitwise-constraints on symbolic values.
 344       case BO_And:
 345       case BO_Or:
 346       case BO_Xor:
 347         return false;
 348       // We don't reason yet about these arithmetic constraints on
 349       // symbolic values.
 350       case BO_Mul:
 351       case BO_Div:
 352       case BO_Rem:
 353       case BO_Shl:
 354       case BO_Shr:
 355         return false;
 356       // All other cases.
 357       default:
 358         return true;
 359       }
 360     }
 361
 362     if (const SymSymExpr *SSE = dyn_cast<SymSymExpr>(SE)) {
 363       // FIXME: Handle <=> here.
 364       if (BinaryOperator::isEqualityOp(SSE->getOpcode()) ||
 365           BinaryOperator::isRelationalOp(SSE->getOpcode())) {
 366         // We handle Loc <> Loc comparisons, but not (yet) NonLoc <> NonLoc.
 367         // We've recently started producing Loc <> NonLoc comparisons (that
 368         // result from casts of one of the operands between eg. intptr_t and
 369         // void *), but we can't reason about them yet.
 370         if (Loc::isLocType(SSE->getLHS()->getType())) {
 371           return Loc::isLocType(SSE->getRHS()->getType());
 372         }
 373       }
 374     }
 375
 376     return false;
 377   }
 378
 379   return true;
 380 }
 381
 382 ConditionTruthVal RangeConstraintManager::checkNull(ProgramStateRef State,
 383                                                     SymbolRef Sym) {
 384   const RangeSet *Ranges = State->get<ConstraintRange>(Sym);
 385
 386   // If we don't have any information about this symbol, it's underconstrained.
 387   if (!Ranges)
 388     return ConditionTruthVal();
 389
 390   // If we have a concrete value, see if it's zero.
 391   if (const llvm::APSInt *Value = Ranges->getConcreteValue())
 392     return *Value == 0;
 393
 394   BasicValueFactory &BV = getBasicVals();
 395   APSIntType IntType = BV.getAPSIntType(Sym->getType());
 396   llvm::APSInt Zero = IntType.getZeroValue();
 397
 398   // Check if zero is in the set of possible values.
 399   if (Ranges->Intersect(BV, F, Zero, Zero).isEmpty())
 400     return false;
 401
 402   // Zero is a possible value, but it is not the /only/ possible value.
 403   return ConditionTruthVal();
 404 }
 405
 406 const llvm::APSInt *RangeConstraintManager::getSymVal(ProgramStateRef St,
 407                                                       SymbolRef Sym) const {
 408   const ConstraintRangeTy::data_type *T = St->get<ConstraintRange>(Sym);
 409   return T ? T->getConcreteValue() : nullptr;
 410 }
 411
 412 /// Scan all symbols referenced by the constraints. If the symbol is not alive
 413 /// as marked in LSymbols, mark it as dead in DSymbols.
 414 ProgramStateRef
 415 RangeConstraintManager::removeDeadBindings(ProgramStateRef State,
 416                                            SymbolReaper &SymReaper) {
 417   bool Changed = false;
 418   ConstraintRangeTy CR = State->get<ConstraintRange>();
 419   ConstraintRangeTy::Factory &CRFactory = State->get_context<ConstraintRange>();
 420
 421   for (ConstraintRangeTy::iterator I = CR.begin(), E = CR.end(); I != E; ++I) {
 422     SymbolRef Sym = I.getKey();
 423     if (SymReaper.isDead(Sym)) {
 424       Changed = true;
 425       CR = CRFactory.remove(CR, Sym);
 426     }
 427   }
 428
 429   return Changed ? State->set<ConstraintRange>(CR) : State;
 430 }
 431
 432 /// Return a range set subtracting zero from \p Domain.
 433 static RangeSet assumeNonZero(
 434     BasicValueFactory &BV,
 435     RangeSet::Factory &F,
 436     SymbolRef Sym,
 437     RangeSet Domain) {
 438   APSIntType IntType = BV.getAPSIntType(Sym->getType());
 439   return Domain.Intersect(BV, F, ++IntType.getZeroValue(),
 440       --IntType.getZeroValue());
 441 }
 442
 443 /// Apply implicit constraints for bitwise OR- and AND-.
 444 /// For unsigned types, bitwise OR with a constant always returns
 445 /// a value greater-or-equal than the constant, and bitwise AND
 446 /// returns a value less-or-equal then the constant.
 447 ///
 448 /// Pattern matches the expression \p Sym against those rule,
 449 /// and applies the required constraints.
 450 /// \p Input Previously established expression range set
 451 static RangeSet applyBitwiseConstraints(
 452     BasicValueFactory &BV,
 453     RangeSet::Factory &F,
 454     RangeSet Input,
 455     const SymIntExpr* SIE) {
 456   QualType T = SIE->getType();
 457   bool IsUnsigned = T->isUnsignedIntegerType();
 458   const llvm::APSInt &RHS = SIE->getRHS();
 459   const llvm::APSInt &Zero = BV.getAPSIntType(T).getZeroValue();
 460   BinaryOperator::Opcode Operator = SIE->getOpcode();
 461
 462   // For unsigned types, the output of bitwise-or is bigger-or-equal than RHS.
 463   if (Operator == BO_Or && IsUnsigned)
 464     return Input.Intersect(BV, F, RHS, BV.getMaxValue(T));
 465
 466   // Bitwise-or with a non-zero constant is always non-zero.
 467   if (Operator == BO_Or && RHS != Zero)
 468     return assumeNonZero(BV, F, SIE, Input);
 469
 470   // For unsigned types, or positive RHS,
 471   // bitwise-and output is always smaller-or-equal than RHS (assuming two's
 472   // complement representation of signed types).
 473   if (Operator == BO_And && (IsUnsigned || RHS >= Zero))
 474     return Input.Intersect(BV, F, BV.getMinValue(T), RHS);
 475
 476   return Input;
 477 }
 478
 479 RangeSet RangeConstraintManager::getRange(ProgramStateRef State,
 480                                           SymbolRef Sym) {
 481   ConstraintRangeTy::data_type *V = State->get<ConstraintRange>(Sym);
 482
 483   // If Sym is a difference of symbols A - B, then maybe we have range set
 484   // stored for B - A.
 485   BasicValueFactory &BV = getBasicVals();
 486   const RangeSet *R = getRangeForMinusSymbol(State, Sym);
 487
 488   // If we have range set stored for both A - B and B - A then calculate the
 489   // effective range set by intersecting the range set for A - B and the
 490   // negated range set of B - A.
 491   if (V && R)
 492     return V->Intersect(BV, F, R->Negate(BV, F));
 493   if (V)
 494     return *V;
 495   if (R)
 496     return R->Negate(BV, F);
 497
 498   // Lazily generate a new RangeSet representing all possible values for the
 499   // given symbol type.
 500   QualType T = Sym->getType();
 501
 502   RangeSet Result(F, BV.getMinValue(T), BV.getMaxValue(T));
 503
 504   // References are known to be non-zero.
 505   if (T->isReferenceType())
 506     return assumeNonZero(BV, F, Sym, Result);
 507
 508   // Known constraints on ranges of bitwise expressions.
 509   if (const SymIntExpr* SIE = dyn_cast<SymIntExpr>(Sym))
 510     return applyBitwiseConstraints(BV, F, Result, SIE);
 511
 512   return Result;
 513 }
 514
 515 // FIXME: Once SValBuilder supports unary minus, we should use SValBuilder to
 516 //        obtain the negated symbolic expression instead of constructing the
 517 //        symbol manually. This will allow us to support finding ranges of not
 518 //        only negated SymSymExpr-type expressions, but also of other, simpler
 519 //        expressions which we currently do not know how to negate.
 520 const RangeSet*
 521 RangeConstraintManager::getRangeForMinusSymbol(ProgramStateRef State,
 522                                                SymbolRef Sym) {
 523   if (const SymSymExpr *SSE = dyn_cast<SymSymExpr>(Sym)) {
 524     if (SSE->getOpcode() == BO_Sub) {
 525       QualType T = Sym->getType();
 526       SymbolManager &SymMgr = State->getSymbolManager();
 527       SymbolRef negSym = SymMgr.getSymSymExpr(SSE->getRHS(), BO_Sub,
 528                                               SSE->getLHS(), T);
 529       if (const RangeSet *negV = State->get<ConstraintRange>(negSym)) {
 530         // Unsigned range set cannot be negated, unless it is [0, 0].
 531         if ((negV->getConcreteValue() &&
 532              (*negV->getConcreteValue() == 0)) ||
 533             T->isSignedIntegerOrEnumerationType())
 534           return negV;
 535       }
 536     }
 537   }
 538   return nullptr;
 539 }
 540
 541 //===------------------------------------------------------------------------===
 542 // assumeSymX methods: protected interface for RangeConstraintManager.
 543 //===------------------------------------------------------------------------===/
 544
 545 // The syntax for ranges below is mathematical, using [x, y] for closed ranges
 546 // and (x, y) for open ranges. These ranges are modular, corresponding with
 547 // a common treatment of C integer overflow. This means that these methods
 548 // do not have to worry about overflow; RangeSet::Intersect can handle such a
 549 // "wraparound" range.
 550 // As an example, the range [UINT_MAX-1, 3) contains five values: UINT_MAX-1,
 551 // UINT_MAX, 0, 1, and 2.
 552
 553 ProgramStateRef
 554 RangeConstraintManager::assumeSymNE(ProgramStateRef St, SymbolRef Sym,
 555                                     const llvm::APSInt &Int,
 556                                     const llvm::APSInt &Adjustment) {
 557   // Before we do any real work, see if the value can even show up.
 558   APSIntType AdjustmentType(Adjustment);
 559   if (AdjustmentType.testInRange(Int, true) != APSIntType::RTR_Within)
 560     return St;
 561
 562   llvm::APSInt Lower = AdjustmentType.convert(Int) - Adjustment;
 563   llvm::APSInt Upper = Lower;
 564   --Lower;
 565   ++Upper;
 566
 567   // [Int-Adjustment+1, Int-Adjustment-1]
 568   // Notice that the lower bound is greater than the upper bound.
 569   RangeSet New = getRange(St, Sym).Intersect(getBasicVals(), F, Upper, Lower);
 570   return New.isEmpty() ? nullptr : St->set<ConstraintRange>(Sym, New);
 571 }
 572
 573 ProgramStateRef
 574 RangeConstraintManager::assumeSymEQ(ProgramStateRef St, SymbolRef Sym,
 575                                     const llvm::APSInt &Int,
 576                                     const llvm::APSInt &Adjustment) {
 577   // Before we do any real work, see if the value can even show up.
 578   APSIntType AdjustmentType(Adjustment);
 579   if (AdjustmentType.testInRange(Int, true) != APSIntType::RTR_Within)
 580     return nullptr;
 581
 582   // [Int-Adjustment, Int-Adjustment]
 583   llvm::APSInt AdjInt = AdjustmentType.convert(Int) - Adjustment;
 584   RangeSet New = getRange(St, Sym).Intersect(getBasicVals(), F, AdjInt, AdjInt);
 585   return New.isEmpty() ? nullptr : St->set<ConstraintRange>(Sym, New);
 586 }
 587
 588 RangeSet RangeConstraintManager::getSymLTRange(ProgramStateRef St,
 589                                                SymbolRef Sym,
 590                                                const llvm::APSInt &Int,
 591                                                const llvm::APSInt &Adjustment) {
 592   // Before we do any real work, see if the value can even show up.
 593   APSIntType AdjustmentType(Adjustment);
 594   switch (AdjustmentType.testInRange(Int, true)) {
 595   case APSIntType::RTR_Below:
 596     return F.getEmptySet();
 597   case APSIntType::RTR_Within:
 598     break;
 599   case APSIntType::RTR_Above:
 600     return getRange(St, Sym);
 601   }
 602
 603   // Special case for Int == Min. This is always false.
 604   llvm::APSInt ComparisonVal = AdjustmentType.convert(Int);
 605   llvm::APSInt Min = AdjustmentType.getMinValue();
 606   if (ComparisonVal == Min)
 607     return F.getEmptySet();
 608
 609   llvm::APSInt Lower = Min - Adjustment;
 610   llvm::APSInt Upper = ComparisonVal - Adjustment;
 611   --Upper;
 612
 613   return getRange(St, Sym).Intersect(getBasicVals(), F, Lower, Upper);
 614 }
 615
 616 ProgramStateRef
 617 RangeConstraintManager::assumeSymLT(ProgramStateRef St, SymbolRef Sym,
 618                                     const llvm::APSInt &Int,
 619                                     const llvm::APSInt &Adjustment) {
 620   RangeSet New = getSymLTRange(St, Sym, Int, Adjustment);
 621   return New.isEmpty() ? nullptr : St->set<ConstraintRange>(Sym, New);
 622 }
 623
 624 RangeSet RangeConstraintManager::getSymGTRange(ProgramStateRef St,
 625                                                SymbolRef Sym,
 626                                                const llvm::APSInt &Int,
 627                                                const llvm::APSInt &Adjustment) {
 628   // Before we do any real work, see if the value can even show up.
 629   APSIntType AdjustmentType(Adjustment);
 630   switch (AdjustmentType.testInRange(Int, true)) {
 631   case APSIntType::RTR_Below:
 632     return getRange(St, Sym);
 633   case APSIntType::RTR_Within:
 634     break;
 635   case APSIntType::RTR_Above:
 636     return F.getEmptySet();
 637   }
 638
 639   // Special case for Int == Max. This is always false.
 640   llvm::APSInt ComparisonVal = AdjustmentType.convert(Int);
 641   llvm::APSInt Max = AdjustmentType.getMaxValue();
 642   if (ComparisonVal == Max)
 643     return F.getEmptySet();
 644
 645   llvm::APSInt Lower = ComparisonVal - Adjustment;
 646   llvm::APSInt Upper = Max - Adjustment;
 647   ++Lower;
 648
 649   return getRange(St, Sym).Intersect(getBasicVals(), F, Lower, Upper);
 650 }
 651
 652 ProgramStateRef
 653 RangeConstraintManager::assumeSymGT(ProgramStateRef St, SymbolRef Sym,
 654                                     const llvm::APSInt &Int,
 655                                     const llvm::APSInt &Adjustment) {
 656   RangeSet New = getSymGTRange(St, Sym, Int, Adjustment);
 657   return New.isEmpty() ? nullptr : St->set<ConstraintRange>(Sym, New);
 658 }
 659
 660 RangeSet RangeConstraintManager::getSymGERange(ProgramStateRef St,
 661                                                SymbolRef Sym,
 662                                                const llvm::APSInt &Int,
 663                                                const llvm::APSInt &Adjustment) {
 664   // Before we do any real work, see if the value can even show up.
 665   APSIntType AdjustmentType(Adjustment);
 666   switch (AdjustmentType.testInRange(Int, true)) {
 667   case APSIntType::RTR_Below:
 668     return getRange(St, Sym);
 669   case APSIntType::RTR_Within:
 670     break;
 671   case APSIntType::RTR_Above:
 672     return F.getEmptySet();
 673   }
 674
 675   // Special case for Int == Min. This is always feasible.
 676   llvm::APSInt ComparisonVal = AdjustmentType.convert(Int);
 677   llvm::APSInt Min = AdjustmentType.getMinValue();
 678   if (ComparisonVal == Min)
 679     return getRange(St, Sym);
 680
 681   llvm::APSInt Max = AdjustmentType.getMaxValue();
 682   llvm::APSInt Lower = ComparisonVal - Adjustment;
 683   llvm::APSInt Upper = Max - Adjustment;
 684
 685   return getRange(St, Sym).Intersect(getBasicVals(), F, Lower, Upper);
 686 }
 687
 688 ProgramStateRef
 689 RangeConstraintManager::assumeSymGE(ProgramStateRef St, SymbolRef Sym,
 690                                     const llvm::APSInt &Int,
 691                                     const llvm::APSInt &Adjustment) {
 692   RangeSet New = getSymGERange(St, Sym, Int, Adjustment);
 693   return New.isEmpty() ? nullptr : St->set<ConstraintRange>(Sym, New);
 694 }
 695
 696 RangeSet RangeConstraintManager::getSymLERange(
 697       llvm::function_ref<RangeSet()> RS,
 698       const llvm::APSInt &Int,
 699       const llvm::APSInt &Adjustment) {
 700   // Before we do any real work, see if the value can even show up.
 701   APSIntType AdjustmentType(Adjustment);
 702   switch (AdjustmentType.testInRange(Int, true)) {
 703   case APSIntType::RTR_Below:
 704     return F.getEmptySet();
 705   case APSIntType::RTR_Within:
 706     break;
 707   case APSIntType::RTR_Above:
 708     return RS();
 709   }
 710
 711   // Special case for Int == Max. This is always feasible.
 712   llvm::APSInt ComparisonVal = AdjustmentType.convert(Int);
 713   llvm::APSInt Max = AdjustmentType.getMaxValue();
 714   if (ComparisonVal == Max)
 715     return RS();
 716
 717   llvm::APSInt Min = AdjustmentType.getMinValue();
 718   llvm::APSInt Lower = Min - Adjustment;
 719   llvm::APSInt Upper = ComparisonVal - Adjustment;
 720
 721   return RS().Intersect(getBasicVals(), F, Lower, Upper);
 722 }
 723
 724 RangeSet RangeConstraintManager::getSymLERange(ProgramStateRef St,
 725                                                SymbolRef Sym,
 726                                                const llvm::APSInt &Int,
 727                                                const llvm::APSInt &Adjustment) {
 728   return getSymLERange([&] { return getRange(St, Sym); }, Int, Adjustment);
 729 }
 730
 731 ProgramStateRef
 732 RangeConstraintManager::assumeSymLE(ProgramStateRef St, SymbolRef Sym,
 733                                     const llvm::APSInt &Int,
 734                                     const llvm::APSInt &Adjustment) {
 735   RangeSet New = getSymLERange(St, Sym, Int, Adjustment);
 736   return New.isEmpty() ? nullptr : St->set<ConstraintRange>(Sym, New);
 737 }
 738
 739 ProgramStateRef RangeConstraintManager::assumeSymWithinInclusiveRange(
 740     ProgramStateRef State, SymbolRef Sym, const llvm::APSInt &From,
 741     const llvm::APSInt &To, const llvm::APSInt &Adjustment) {
 742   RangeSet New = getSymGERange(State, Sym, From, Adjustment);
 743   if (New.isEmpty())
 744     return nullptr;
 745   RangeSet Out = getSymLERange([&] { return New; }, To, Adjustment);
 746   return Out.isEmpty() ? nullptr : State->set<ConstraintRange>(Sym, Out);
 747 }
 748
 749 ProgramStateRef RangeConstraintManager::assumeSymOutsideInclusiveRange(
 750     ProgramStateRef State, SymbolRef Sym, const llvm::APSInt &From,
 751     const llvm::APSInt &To, const llvm::APSInt &Adjustment) {
 752   RangeSet RangeLT = getSymLTRange(State, Sym, From, Adjustment);
 753   RangeSet RangeGT = getSymGTRange(State, Sym, To, Adjustment);
 754   RangeSet New(RangeLT.addRange(F, RangeGT));
 755   return New.isEmpty() ? nullptr : State->set<ConstraintRange>(Sym, New);
 756 }
 757
 758 //===----------------------------------------------------------------------===//
 759 // Pretty-printing.
 760 //===----------------------------------------------------------------------===//
 761
 762 void RangeConstraintManager::printJson(raw_ostream &Out, ProgramStateRef State,
 763                                        const char *NL, unsigned int Space,
 764                                        bool IsDot) const {
 765   ConstraintRangeTy Constraints = State->get<ConstraintRange>();
 766
 767   Indent(Out, Space, IsDot) << "\"constraints\": ";
 768   if (Constraints.isEmpty()) {
 769     Out << "null," << NL;
 770     return;
 771   }
 772
 773   ++Space;
 774   Out << '[' << NL;
 775   for (ConstraintRangeTy::iterator I = Constraints.begin();
 776        I != Constraints.end(); ++I) {
 777     Indent(Out, Space, IsDot)
 778         << "{ \"symbol\": \"" << I.getKey() << "\", \"range\": \"";
 779     I.getData().print(Out);
 780     Out << "\" }";
 781
 782     if (std::next(I) != Constraints.end())
 783       Out << ',';
 784     Out << NL;
 785   }
 786
 787   --Space;
 788   Indent(Out, Space, IsDot) << "]," << NL;
 789 }