• Home
  • Line#
  • Scopes#
  • Navigate#
  • Raw
  • Download
1 //== RangeConstraintManager.cpp - Manage range constraints.------*- C++ -*--==//
2 //
3 //                     The LLVM Compiler Infrastructure
4 //
5 // This file is distributed under the University of Illinois Open Source
6 // License. See LICENSE.TXT for details.
7 //
8 //===----------------------------------------------------------------------===//
9 //
10 //  This file defines RangeConstraintManager, a class that tracks simple
11 //  equality and inequality constraints on symbolic values of ProgramState.
12 //
13 //===----------------------------------------------------------------------===//
14 
15 #include "SimpleConstraintManager.h"
16 #include "clang/StaticAnalyzer/Core/PathSensitive/APSIntType.h"
17 #include "clang/StaticAnalyzer/Core/PathSensitive/ProgramState.h"
18 #include "clang/StaticAnalyzer/Core/PathSensitive/ProgramStateTrait.h"
19 #include "llvm/ADT/FoldingSet.h"
20 #include "llvm/ADT/ImmutableSet.h"
21 #include "llvm/Support/Debug.h"
22 #include "llvm/Support/raw_ostream.h"
23 
24 using namespace clang;
25 using namespace ento;
26 
27 /// A Range represents the closed range [from, to].  The caller must
28 /// guarantee that from <= to.  Note that Range is immutable, so as not
29 /// to subvert RangeSet's immutability.
30 namespace {
31 class Range : public std::pair<const llvm::APSInt*,
32                                                 const llvm::APSInt*> {
33 public:
Range(const llvm::APSInt & from,const llvm::APSInt & to)34   Range(const llvm::APSInt &from, const llvm::APSInt &to)
35     : std::pair<const llvm::APSInt*, const llvm::APSInt*>(&from, &to) {
36     assert(from <= to);
37   }
Includes(const llvm::APSInt & v) const38   bool Includes(const llvm::APSInt &v) const {
39     return *first <= v && v <= *second;
40   }
From() const41   const llvm::APSInt &From() const {
42     return *first;
43   }
To() const44   const llvm::APSInt &To() const {
45     return *second;
46   }
getConcreteValue() const47   const llvm::APSInt *getConcreteValue() const {
48     return &From() == &To() ? &From() : nullptr;
49   }
50 
Profile(llvm::FoldingSetNodeID & ID) const51   void Profile(llvm::FoldingSetNodeID &ID) const {
52     ID.AddPointer(&From());
53     ID.AddPointer(&To());
54   }
55 };
56 
57 
58 class RangeTrait : public llvm::ImutContainerInfo<Range> {
59 public:
60   // When comparing if one Range is less than another, we should compare
61   // the actual APSInt values instead of their pointers.  This keeps the order
62   // consistent (instead of comparing by pointer values) and can potentially
63   // be used to speed up some of the operations in RangeSet.
isLess(key_type_ref lhs,key_type_ref rhs)64   static inline bool isLess(key_type_ref lhs, key_type_ref rhs) {
65     return *lhs.first < *rhs.first || (!(*rhs.first < *lhs.first) &&
66                                        *lhs.second < *rhs.second);
67   }
68 };
69 
70 /// RangeSet contains a set of ranges. If the set is empty, then
71 ///  there the value of a symbol is overly constrained and there are no
72 ///  possible values for that symbol.
73 class RangeSet {
74   typedef llvm::ImmutableSet<Range, RangeTrait> PrimRangeSet;
75   PrimRangeSet ranges; // no need to make const, since it is an
76                        // ImmutableSet - this allows default operator=
77                        // to work.
78 public:
79   typedef PrimRangeSet::Factory Factory;
80   typedef PrimRangeSet::iterator iterator;
81 
RangeSet(PrimRangeSet RS)82   RangeSet(PrimRangeSet RS) : ranges(RS) {}
83 
84   /// Create a new set with all ranges of this set and RS.
85   /// Possible intersections are not checked here.
addRange(Factory & F,const RangeSet & RS)86   RangeSet addRange(Factory &F, const RangeSet &RS) {
87     PrimRangeSet Ranges(RS.ranges);
88     for (const auto &range : ranges)
89       Ranges = F.add(Ranges, range);
90     return RangeSet(Ranges);
91   }
92 
begin() const93   iterator begin() const { return ranges.begin(); }
end() const94   iterator end() const { return ranges.end(); }
95 
isEmpty() const96   bool isEmpty() const { return ranges.isEmpty(); }
97 
98   /// Construct a new RangeSet representing '{ [from, to] }'.
RangeSet(Factory & F,const llvm::APSInt & from,const llvm::APSInt & to)99   RangeSet(Factory &F, const llvm::APSInt &from, const llvm::APSInt &to)
100     : ranges(F.add(F.getEmptySet(), Range(from, to))) {}
101 
102   /// Profile - Generates a hash profile of this RangeSet for use
103   ///  by FoldingSet.
Profile(llvm::FoldingSetNodeID & ID) const104   void Profile(llvm::FoldingSetNodeID &ID) const { ranges.Profile(ID); }
105 
106   /// getConcreteValue - If a symbol is contrained to equal a specific integer
107   ///  constant then this method returns that value.  Otherwise, it returns
108   ///  NULL.
getConcreteValue() const109   const llvm::APSInt* getConcreteValue() const {
110     return ranges.isSingleton() ? ranges.begin()->getConcreteValue() : nullptr;
111   }
112 
113 private:
IntersectInRange(BasicValueFactory & BV,Factory & F,const llvm::APSInt & Lower,const llvm::APSInt & Upper,PrimRangeSet & newRanges,PrimRangeSet::iterator & i,PrimRangeSet::iterator & e) const114   void IntersectInRange(BasicValueFactory &BV, Factory &F,
115                         const llvm::APSInt &Lower,
116                         const llvm::APSInt &Upper,
117                         PrimRangeSet &newRanges,
118                         PrimRangeSet::iterator &i,
119                         PrimRangeSet::iterator &e) const {
120     // There are six cases for each range R in the set:
121     //   1. R is entirely before the intersection range.
122     //   2. R is entirely after the intersection range.
123     //   3. R contains the entire intersection range.
124     //   4. R starts before the intersection range and ends in the middle.
125     //   5. R starts in the middle of the intersection range and ends after it.
126     //   6. R is entirely contained in the intersection range.
127     // These correspond to each of the conditions below.
128     for (/* i = begin(), e = end() */; i != e; ++i) {
129       if (i->To() < Lower) {
130         continue;
131       }
132       if (i->From() > Upper) {
133         break;
134       }
135 
136       if (i->Includes(Lower)) {
137         if (i->Includes(Upper)) {
138           newRanges = F.add(newRanges, Range(BV.getValue(Lower),
139                                              BV.getValue(Upper)));
140           break;
141         } else
142           newRanges = F.add(newRanges, Range(BV.getValue(Lower), i->To()));
143       } else {
144         if (i->Includes(Upper)) {
145           newRanges = F.add(newRanges, Range(i->From(), BV.getValue(Upper)));
146           break;
147         } else
148           newRanges = F.add(newRanges, *i);
149       }
150     }
151   }
152 
getMinValue() const153   const llvm::APSInt &getMinValue() const {
154     assert(!isEmpty());
155     return ranges.begin()->From();
156   }
157 
pin(llvm::APSInt & Lower,llvm::APSInt & Upper) const158   bool pin(llvm::APSInt &Lower, llvm::APSInt &Upper) const {
159     // This function has nine cases, the cartesian product of range-testing
160     // both the upper and lower bounds against the symbol's type.
161     // Each case requires a different pinning operation.
162     // The function returns false if the described range is entirely outside
163     // the range of values for the associated symbol.
164     APSIntType Type(getMinValue());
165     APSIntType::RangeTestResultKind LowerTest = Type.testInRange(Lower, true);
166     APSIntType::RangeTestResultKind UpperTest = Type.testInRange(Upper, true);
167 
168     switch (LowerTest) {
169     case APSIntType::RTR_Below:
170       switch (UpperTest) {
171       case APSIntType::RTR_Below:
172         // The entire range is outside the symbol's set of possible values.
173         // If this is a conventionally-ordered range, the state is infeasible.
174         if (Lower <= Upper)
175           return false;
176 
177         // However, if the range wraps around, it spans all possible values.
178         Lower = Type.getMinValue();
179         Upper = Type.getMaxValue();
180         break;
181       case APSIntType::RTR_Within:
182         // The range starts below what's possible but ends within it. Pin.
183         Lower = Type.getMinValue();
184         Type.apply(Upper);
185         break;
186       case APSIntType::RTR_Above:
187         // The range spans all possible values for the symbol. Pin.
188         Lower = Type.getMinValue();
189         Upper = Type.getMaxValue();
190         break;
191       }
192       break;
193     case APSIntType::RTR_Within:
194       switch (UpperTest) {
195       case APSIntType::RTR_Below:
196         // The range wraps around, but all lower values are not possible.
197         Type.apply(Lower);
198         Upper = Type.getMaxValue();
199         break;
200       case APSIntType::RTR_Within:
201         // The range may or may not wrap around, but both limits are valid.
202         Type.apply(Lower);
203         Type.apply(Upper);
204         break;
205       case APSIntType::RTR_Above:
206         // The range starts within what's possible but ends above it. Pin.
207         Type.apply(Lower);
208         Upper = Type.getMaxValue();
209         break;
210       }
211       break;
212     case APSIntType::RTR_Above:
213       switch (UpperTest) {
214       case APSIntType::RTR_Below:
215         // The range wraps but is outside the symbol's set of possible values.
216         return false;
217       case APSIntType::RTR_Within:
218         // The range starts above what's possible but ends within it (wrap).
219         Lower = Type.getMinValue();
220         Type.apply(Upper);
221         break;
222       case APSIntType::RTR_Above:
223         // The entire range is outside the symbol's set of possible values.
224         // If this is a conventionally-ordered range, the state is infeasible.
225         if (Lower <= Upper)
226           return false;
227 
228         // However, if the range wraps around, it spans all possible values.
229         Lower = Type.getMinValue();
230         Upper = Type.getMaxValue();
231         break;
232       }
233       break;
234     }
235 
236     return true;
237   }
238 
239 public:
240   // Returns a set containing the values in the receiving set, intersected with
241   // the closed range [Lower, Upper]. Unlike the Range type, this range uses
242   // modular arithmetic, corresponding to the common treatment of C integer
243   // overflow. Thus, if the Lower bound is greater than the Upper bound, the
244   // range is taken to wrap around. This is equivalent to taking the
245   // intersection with the two ranges [Min, Upper] and [Lower, Max],
246   // or, alternatively, /removing/ all integers between Upper and Lower.
Intersect(BasicValueFactory & BV,Factory & F,llvm::APSInt Lower,llvm::APSInt Upper) const247   RangeSet Intersect(BasicValueFactory &BV, Factory &F,
248                      llvm::APSInt Lower, llvm::APSInt Upper) const {
249     if (!pin(Lower, Upper))
250       return F.getEmptySet();
251 
252     PrimRangeSet newRanges = F.getEmptySet();
253 
254     PrimRangeSet::iterator i = begin(), e = end();
255     if (Lower <= Upper)
256       IntersectInRange(BV, F, Lower, Upper, newRanges, i, e);
257     else {
258       // The order of the next two statements is important!
259       // IntersectInRange() does not reset the iteration state for i and e.
260       // Therefore, the lower range most be handled first.
261       IntersectInRange(BV, F, BV.getMinValue(Upper), Upper, newRanges, i, e);
262       IntersectInRange(BV, F, Lower, BV.getMaxValue(Lower), newRanges, i, e);
263     }
264 
265     return newRanges;
266   }
267 
print(raw_ostream & os) const268   void print(raw_ostream &os) const {
269     bool isFirst = true;
270     os << "{ ";
271     for (iterator i = begin(), e = end(); i != e; ++i) {
272       if (isFirst)
273         isFirst = false;
274       else
275         os << ", ";
276 
277       os << '[' << i->From().toString(10) << ", " << i->To().toString(10)
278          << ']';
279     }
280     os << " }";
281   }
282 
operator ==(const RangeSet & other) const283   bool operator==(const RangeSet &other) const {
284     return ranges == other.ranges;
285   }
286 };
287 } // end anonymous namespace
288 
289 REGISTER_TRAIT_WITH_PROGRAMSTATE(ConstraintRange,
290                                  CLANG_ENTO_PROGRAMSTATE_MAP(SymbolRef,
291                                                              RangeSet))
292 
293 namespace {
294 class RangeConstraintManager : public SimpleConstraintManager{
295   RangeSet GetRange(ProgramStateRef state, SymbolRef sym);
296 public:
RangeConstraintManager(SubEngine * subengine,SValBuilder & SVB)297   RangeConstraintManager(SubEngine *subengine, SValBuilder &SVB)
298     : SimpleConstraintManager(subengine, SVB) {}
299 
300   ProgramStateRef assumeSymNE(ProgramStateRef state, SymbolRef sym,
301                              const llvm::APSInt& Int,
302                              const llvm::APSInt& Adjustment) override;
303 
304   ProgramStateRef assumeSymEQ(ProgramStateRef state, SymbolRef sym,
305                              const llvm::APSInt& Int,
306                              const llvm::APSInt& Adjustment) override;
307 
308   ProgramStateRef assumeSymLT(ProgramStateRef state, SymbolRef sym,
309                              const llvm::APSInt& Int,
310                              const llvm::APSInt& Adjustment) override;
311 
312   ProgramStateRef assumeSymGT(ProgramStateRef state, SymbolRef sym,
313                              const llvm::APSInt& Int,
314                              const llvm::APSInt& Adjustment) override;
315 
316   ProgramStateRef assumeSymGE(ProgramStateRef state, SymbolRef sym,
317                              const llvm::APSInt& Int,
318                              const llvm::APSInt& Adjustment) override;
319 
320   ProgramStateRef assumeSymLE(ProgramStateRef state, SymbolRef sym,
321                              const llvm::APSInt& Int,
322                              const llvm::APSInt& Adjustment) override;
323 
324   ProgramStateRef assumeSymbolWithinInclusiveRange(
325         ProgramStateRef State, SymbolRef Sym, const llvm::APSInt &From,
326         const llvm::APSInt &To, const llvm::APSInt &Adjustment) override;
327 
328   ProgramStateRef assumeSymbolOutOfInclusiveRange(
329         ProgramStateRef State, SymbolRef Sym, const llvm::APSInt &From,
330         const llvm::APSInt &To, const llvm::APSInt &Adjustment) override;
331 
332   const llvm::APSInt* getSymVal(ProgramStateRef St,
333                                 SymbolRef sym) const override;
334   ConditionTruthVal checkNull(ProgramStateRef State, SymbolRef Sym) override;
335 
336   ProgramStateRef removeDeadBindings(ProgramStateRef St,
337                                      SymbolReaper& SymReaper) override;
338 
339   void print(ProgramStateRef St, raw_ostream &Out,
340              const char* nl, const char *sep) override;
341 
342 private:
343   RangeSet::Factory F;
344   RangeSet getSymLTRange(ProgramStateRef St, SymbolRef Sym,
345                          const llvm::APSInt &Int,
346                          const llvm::APSInt &Adjustment);
347   RangeSet getSymGTRange(ProgramStateRef St, SymbolRef Sym,
348                          const llvm::APSInt &Int,
349                          const llvm::APSInt &Adjustment);
350   RangeSet getSymLERange(ProgramStateRef St, SymbolRef Sym,
351                          const llvm::APSInt &Int,
352                          const llvm::APSInt &Adjustment);
353   RangeSet getSymLERange(const RangeSet &RS, const llvm::APSInt &Int,
354                          const llvm::APSInt &Adjustment);
355   RangeSet getSymGERange(ProgramStateRef St, SymbolRef Sym,
356                          const llvm::APSInt &Int,
357                          const llvm::APSInt &Adjustment);
358 };
359 
360 } // end anonymous namespace
361 
362 std::unique_ptr<ConstraintManager>
CreateRangeConstraintManager(ProgramStateManager & StMgr,SubEngine * Eng)363 ento::CreateRangeConstraintManager(ProgramStateManager &StMgr, SubEngine *Eng) {
364   return llvm::make_unique<RangeConstraintManager>(Eng, StMgr.getSValBuilder());
365 }
366 
getSymVal(ProgramStateRef St,SymbolRef sym) const367 const llvm::APSInt* RangeConstraintManager::getSymVal(ProgramStateRef St,
368                                                       SymbolRef sym) const {
369   const ConstraintRangeTy::data_type *T = St->get<ConstraintRange>(sym);
370   return T ? T->getConcreteValue() : nullptr;
371 }
372 
checkNull(ProgramStateRef State,SymbolRef Sym)373 ConditionTruthVal RangeConstraintManager::checkNull(ProgramStateRef State,
374                                                     SymbolRef Sym) {
375   const RangeSet *Ranges = State->get<ConstraintRange>(Sym);
376 
377   // If we don't have any information about this symbol, it's underconstrained.
378   if (!Ranges)
379     return ConditionTruthVal();
380 
381   // If we have a concrete value, see if it's zero.
382   if (const llvm::APSInt *Value = Ranges->getConcreteValue())
383     return *Value == 0;
384 
385   BasicValueFactory &BV = getBasicVals();
386   APSIntType IntType = BV.getAPSIntType(Sym->getType());
387   llvm::APSInt Zero = IntType.getZeroValue();
388 
389   // Check if zero is in the set of possible values.
390   if (Ranges->Intersect(BV, F, Zero, Zero).isEmpty())
391     return false;
392 
393   // Zero is a possible value, but it is not the /only/ possible value.
394   return ConditionTruthVal();
395 }
396 
397 /// Scan all symbols referenced by the constraints. If the symbol is not alive
398 /// as marked in LSymbols, mark it as dead in DSymbols.
399 ProgramStateRef
removeDeadBindings(ProgramStateRef state,SymbolReaper & SymReaper)400 RangeConstraintManager::removeDeadBindings(ProgramStateRef state,
401                                            SymbolReaper& SymReaper) {
402 
403   ConstraintRangeTy CR = state->get<ConstraintRange>();
404   ConstraintRangeTy::Factory& CRFactory = state->get_context<ConstraintRange>();
405 
406   for (ConstraintRangeTy::iterator I = CR.begin(), E = CR.end(); I != E; ++I) {
407     SymbolRef sym = I.getKey();
408     if (SymReaper.maybeDead(sym))
409       CR = CRFactory.remove(CR, sym);
410   }
411 
412   return state->set<ConstraintRange>(CR);
413 }
414 
415 RangeSet
GetRange(ProgramStateRef state,SymbolRef sym)416 RangeConstraintManager::GetRange(ProgramStateRef state, SymbolRef sym) {
417   if (ConstraintRangeTy::data_type* V = state->get<ConstraintRange>(sym))
418     return *V;
419 
420   // Lazily generate a new RangeSet representing all possible values for the
421   // given symbol type.
422   BasicValueFactory &BV = getBasicVals();
423   QualType T = sym->getType();
424 
425   RangeSet Result(F, BV.getMinValue(T), BV.getMaxValue(T));
426 
427   // Special case: references are known to be non-zero.
428   if (T->isReferenceType()) {
429     APSIntType IntType = BV.getAPSIntType(T);
430     Result = Result.Intersect(BV, F, ++IntType.getZeroValue(),
431                                      --IntType.getZeroValue());
432   }
433 
434   return Result;
435 }
436 
437 //===------------------------------------------------------------------------===
438 // assumeSymX methods: public interface for RangeConstraintManager.
439 //===------------------------------------------------------------------------===/
440 
441 // The syntax for ranges below is mathematical, using [x, y] for closed ranges
442 // and (x, y) for open ranges. These ranges are modular, corresponding with
443 // a common treatment of C integer overflow. This means that these methods
444 // do not have to worry about overflow; RangeSet::Intersect can handle such a
445 // "wraparound" range.
446 // As an example, the range [UINT_MAX-1, 3) contains five values: UINT_MAX-1,
447 // UINT_MAX, 0, 1, and 2.
448 
449 ProgramStateRef
assumeSymNE(ProgramStateRef St,SymbolRef Sym,const llvm::APSInt & Int,const llvm::APSInt & Adjustment)450 RangeConstraintManager::assumeSymNE(ProgramStateRef St, SymbolRef Sym,
451                                     const llvm::APSInt &Int,
452                                     const llvm::APSInt &Adjustment) {
453   // Before we do any real work, see if the value can even show up.
454   APSIntType AdjustmentType(Adjustment);
455   if (AdjustmentType.testInRange(Int, true) != APSIntType::RTR_Within)
456     return St;
457 
458   llvm::APSInt Lower = AdjustmentType.convert(Int) - Adjustment;
459   llvm::APSInt Upper = Lower;
460   --Lower;
461   ++Upper;
462 
463   // [Int-Adjustment+1, Int-Adjustment-1]
464   // Notice that the lower bound is greater than the upper bound.
465   RangeSet New = GetRange(St, Sym).Intersect(getBasicVals(), F, Upper, Lower);
466   return New.isEmpty() ? nullptr : St->set<ConstraintRange>(Sym, New);
467 }
468 
469 ProgramStateRef
assumeSymEQ(ProgramStateRef St,SymbolRef Sym,const llvm::APSInt & Int,const llvm::APSInt & Adjustment)470 RangeConstraintManager::assumeSymEQ(ProgramStateRef St, SymbolRef Sym,
471                                     const llvm::APSInt &Int,
472                                     const llvm::APSInt &Adjustment) {
473   // Before we do any real work, see if the value can even show up.
474   APSIntType AdjustmentType(Adjustment);
475   if (AdjustmentType.testInRange(Int, true) != APSIntType::RTR_Within)
476     return nullptr;
477 
478   // [Int-Adjustment, Int-Adjustment]
479   llvm::APSInt AdjInt = AdjustmentType.convert(Int) - Adjustment;
480   RangeSet New = GetRange(St, Sym).Intersect(getBasicVals(), F, AdjInt, AdjInt);
481   return New.isEmpty() ? nullptr : St->set<ConstraintRange>(Sym, New);
482 }
483 
getSymLTRange(ProgramStateRef St,SymbolRef Sym,const llvm::APSInt & Int,const llvm::APSInt & Adjustment)484 RangeSet RangeConstraintManager::getSymLTRange(ProgramStateRef St,
485                                                SymbolRef Sym,
486                                                const llvm::APSInt &Int,
487                                                const llvm::APSInt &Adjustment) {
488   // Before we do any real work, see if the value can even show up.
489   APSIntType AdjustmentType(Adjustment);
490   switch (AdjustmentType.testInRange(Int, true)) {
491   case APSIntType::RTR_Below:
492     return F.getEmptySet();
493   case APSIntType::RTR_Within:
494     break;
495   case APSIntType::RTR_Above:
496     return GetRange(St, Sym);
497   }
498 
499   // Special case for Int == Min. This is always false.
500   llvm::APSInt ComparisonVal = AdjustmentType.convert(Int);
501   llvm::APSInt Min = AdjustmentType.getMinValue();
502   if (ComparisonVal == Min)
503     return F.getEmptySet();
504 
505   llvm::APSInt Lower = Min - Adjustment;
506   llvm::APSInt Upper = ComparisonVal - Adjustment;
507   --Upper;
508 
509   return GetRange(St, Sym).Intersect(getBasicVals(), F, Lower, Upper);
510 }
511 
512 ProgramStateRef
assumeSymLT(ProgramStateRef St,SymbolRef Sym,const llvm::APSInt & Int,const llvm::APSInt & Adjustment)513 RangeConstraintManager::assumeSymLT(ProgramStateRef St, SymbolRef Sym,
514                                     const llvm::APSInt &Int,
515                                     const llvm::APSInt &Adjustment) {
516   RangeSet New = getSymLTRange(St, Sym, Int, Adjustment);
517   return New.isEmpty() ? nullptr : St->set<ConstraintRange>(Sym, New);
518 }
519 
520 RangeSet
getSymGTRange(ProgramStateRef St,SymbolRef Sym,const llvm::APSInt & Int,const llvm::APSInt & Adjustment)521 RangeConstraintManager::getSymGTRange(ProgramStateRef St, SymbolRef Sym,
522                                       const llvm::APSInt &Int,
523                                       const llvm::APSInt &Adjustment) {
524   // Before we do any real work, see if the value can even show up.
525   APSIntType AdjustmentType(Adjustment);
526   switch (AdjustmentType.testInRange(Int, true)) {
527   case APSIntType::RTR_Below:
528     return GetRange(St, Sym);
529   case APSIntType::RTR_Within:
530     break;
531   case APSIntType::RTR_Above:
532     return F.getEmptySet();
533   }
534 
535   // Special case for Int == Max. This is always false.
536   llvm::APSInt ComparisonVal = AdjustmentType.convert(Int);
537   llvm::APSInt Max = AdjustmentType.getMaxValue();
538   if (ComparisonVal == Max)
539     return F.getEmptySet();
540 
541   llvm::APSInt Lower = ComparisonVal - Adjustment;
542   llvm::APSInt Upper = Max - Adjustment;
543   ++Lower;
544 
545   return GetRange(St, Sym).Intersect(getBasicVals(), F, Lower, Upper);
546 }
547 
548 ProgramStateRef
assumeSymGT(ProgramStateRef St,SymbolRef Sym,const llvm::APSInt & Int,const llvm::APSInt & Adjustment)549 RangeConstraintManager::assumeSymGT(ProgramStateRef St, SymbolRef Sym,
550                                     const llvm::APSInt &Int,
551                                     const llvm::APSInt &Adjustment) {
552   RangeSet New = getSymGTRange(St, Sym, Int, Adjustment);
553   return New.isEmpty() ? nullptr : St->set<ConstraintRange>(Sym, New);
554 }
555 
556 RangeSet
getSymGERange(ProgramStateRef St,SymbolRef Sym,const llvm::APSInt & Int,const llvm::APSInt & Adjustment)557 RangeConstraintManager::getSymGERange(ProgramStateRef St, SymbolRef Sym,
558                                       const llvm::APSInt &Int,
559                                       const llvm::APSInt &Adjustment) {
560   // Before we do any real work, see if the value can even show up.
561   APSIntType AdjustmentType(Adjustment);
562   switch (AdjustmentType.testInRange(Int, true)) {
563   case APSIntType::RTR_Below:
564     return GetRange(St, Sym);
565   case APSIntType::RTR_Within:
566     break;
567   case APSIntType::RTR_Above:
568     return F.getEmptySet();
569   }
570 
571   // Special case for Int == Min. This is always feasible.
572   llvm::APSInt ComparisonVal = AdjustmentType.convert(Int);
573   llvm::APSInt Min = AdjustmentType.getMinValue();
574   if (ComparisonVal == Min)
575     return GetRange(St, Sym);
576 
577   llvm::APSInt Max = AdjustmentType.getMaxValue();
578   llvm::APSInt Lower = ComparisonVal - Adjustment;
579   llvm::APSInt Upper = Max - Adjustment;
580 
581   return GetRange(St, Sym).Intersect(getBasicVals(), F, Lower, Upper);
582 }
583 
584 ProgramStateRef
assumeSymGE(ProgramStateRef St,SymbolRef Sym,const llvm::APSInt & Int,const llvm::APSInt & Adjustment)585 RangeConstraintManager::assumeSymGE(ProgramStateRef St, SymbolRef Sym,
586                                     const llvm::APSInt &Int,
587                                     const llvm::APSInt &Adjustment) {
588   RangeSet New = getSymGERange(St, Sym, Int, Adjustment);
589   return New.isEmpty() ? nullptr : St->set<ConstraintRange>(Sym, New);
590 }
591 
592 RangeSet
getSymLERange(const RangeSet & RS,const llvm::APSInt & Int,const llvm::APSInt & Adjustment)593 RangeConstraintManager::getSymLERange(const RangeSet &RS,
594                                       const llvm::APSInt &Int,
595                                       const llvm::APSInt &Adjustment) {
596   // Before we do any real work, see if the value can even show up.
597   APSIntType AdjustmentType(Adjustment);
598   switch (AdjustmentType.testInRange(Int, true)) {
599   case APSIntType::RTR_Below:
600     return F.getEmptySet();
601   case APSIntType::RTR_Within:
602     break;
603   case APSIntType::RTR_Above:
604     return RS;
605   }
606 
607   // Special case for Int == Max. This is always feasible.
608   llvm::APSInt ComparisonVal = AdjustmentType.convert(Int);
609   llvm::APSInt Max = AdjustmentType.getMaxValue();
610   if (ComparisonVal == Max)
611     return RS;
612 
613   llvm::APSInt Min = AdjustmentType.getMinValue();
614   llvm::APSInt Lower = Min - Adjustment;
615   llvm::APSInt Upper = ComparisonVal - Adjustment;
616 
617   return RS.Intersect(getBasicVals(), F, Lower, Upper);
618 }
619 
620 RangeSet
getSymLERange(ProgramStateRef St,SymbolRef Sym,const llvm::APSInt & Int,const llvm::APSInt & Adjustment)621 RangeConstraintManager::getSymLERange(ProgramStateRef St, SymbolRef Sym,
622                                       const llvm::APSInt &Int,
623                                       const llvm::APSInt &Adjustment) {
624   // Before we do any real work, see if the value can even show up.
625   APSIntType AdjustmentType(Adjustment);
626   switch (AdjustmentType.testInRange(Int, true)) {
627   case APSIntType::RTR_Below:
628     return F.getEmptySet();
629   case APSIntType::RTR_Within:
630     break;
631   case APSIntType::RTR_Above:
632     return GetRange(St, Sym);
633   }
634 
635   // Special case for Int == Max. This is always feasible.
636   llvm::APSInt ComparisonVal = AdjustmentType.convert(Int);
637   llvm::APSInt Max = AdjustmentType.getMaxValue();
638   if (ComparisonVal == Max)
639     return GetRange(St, Sym);
640 
641   llvm::APSInt Min = AdjustmentType.getMinValue();
642   llvm::APSInt Lower = Min - Adjustment;
643   llvm::APSInt Upper = ComparisonVal - Adjustment;
644 
645   return GetRange(St, Sym).Intersect(getBasicVals(), F, Lower, Upper);
646 }
647 
648 ProgramStateRef
assumeSymLE(ProgramStateRef St,SymbolRef Sym,const llvm::APSInt & Int,const llvm::APSInt & Adjustment)649 RangeConstraintManager::assumeSymLE(ProgramStateRef St, SymbolRef Sym,
650                                     const llvm::APSInt &Int,
651                                     const llvm::APSInt &Adjustment) {
652   RangeSet New = getSymLERange(St, Sym, Int, Adjustment);
653   return New.isEmpty() ? nullptr : St->set<ConstraintRange>(Sym, New);
654 }
655 
656 ProgramStateRef
assumeSymbolWithinInclusiveRange(ProgramStateRef State,SymbolRef Sym,const llvm::APSInt & From,const llvm::APSInt & To,const llvm::APSInt & Adjustment)657 RangeConstraintManager::assumeSymbolWithinInclusiveRange(
658     ProgramStateRef State, SymbolRef Sym, const llvm::APSInt &From,
659     const llvm::APSInt &To, const llvm::APSInt &Adjustment) {
660   RangeSet New = getSymGERange(State, Sym, From, Adjustment);
661   if (New.isEmpty())
662     return nullptr;
663   New = getSymLERange(New, To, Adjustment);
664   return New.isEmpty() ? nullptr : State->set<ConstraintRange>(Sym, New);
665 }
666 
667 ProgramStateRef
assumeSymbolOutOfInclusiveRange(ProgramStateRef State,SymbolRef Sym,const llvm::APSInt & From,const llvm::APSInt & To,const llvm::APSInt & Adjustment)668 RangeConstraintManager::assumeSymbolOutOfInclusiveRange(
669     ProgramStateRef State, SymbolRef Sym, const llvm::APSInt &From,
670     const llvm::APSInt &To, const llvm::APSInt &Adjustment) {
671   RangeSet RangeLT = getSymLTRange(State, Sym, From, Adjustment);
672   RangeSet RangeGT = getSymGTRange(State, Sym, To, Adjustment);
673   RangeSet New(RangeLT.addRange(F, RangeGT));
674   return New.isEmpty() ? nullptr : State->set<ConstraintRange>(Sym, New);
675 }
676 
677 //===------------------------------------------------------------------------===
678 // Pretty-printing.
679 //===------------------------------------------------------------------------===/
680 
print(ProgramStateRef St,raw_ostream & Out,const char * nl,const char * sep)681 void RangeConstraintManager::print(ProgramStateRef St, raw_ostream &Out,
682                                    const char* nl, const char *sep) {
683 
684   ConstraintRangeTy Ranges = St->get<ConstraintRange>();
685 
686   if (Ranges.isEmpty()) {
687     Out << nl << sep << "Ranges are empty." << nl;
688     return;
689   }
690 
691   Out << nl << sep << "Ranges of symbol values:";
692   for (ConstraintRangeTy::iterator I=Ranges.begin(), E=Ranges.end(); I!=E; ++I){
693     Out << nl << ' ' << I.getKey() << " : ";
694     I.getData().print(Out);
695   }
696   Out << nl;
697 }
698