Clang Project

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