clang  11.0.0git
RangeConstraintManager.cpp
Go to the documentation of this file.
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 
20 #include "llvm/ADT/FoldingSet.h"
21 #include "llvm/ADT/ImmutableSet.h"
22 #include "llvm/Support/raw_ostream.h"
23 
24 using namespace clang;
25 using namespace ento;
26 
27 // This class can be extended with other tables which will help to reason
28 // about ranges more precisely.
30  static_assert(BO_LT < BO_GT && BO_GT < BO_LE && BO_LE < BO_GE &&
31  BO_GE < BO_EQ && BO_EQ < BO_NE,
32  "This class relies on operators order. Rework it otherwise.");
33 
34 public:
35  enum TriStateKind {
36  False = 0,
39  };
40 
41 private:
42  // CmpOpTable holds states which represent the corresponding range for
43  // branching an exploded graph. We can reason about the branch if there is
44  // a previously known fact of the existence of a comparison expression with
45  // operands used in the current expression.
46  // E.g. assuming (x < y) is true that means (x != y) is surely true.
47  // if (x previous_operation y) // < | != | >
48  // if (x operation y) // != | > | <
49  // tristate // True | Unknown | False
50  //
51  // CmpOpTable represents next:
52  // __|< |> |<=|>=|==|!=|UnknownX2|
53  // < |1 |0 |* |0 |0 |* |1 |
54  // > |0 |1 |0 |* |0 |* |1 |
55  // <=|1 |0 |1 |* |1 |* |0 |
56  // >=|0 |1 |* |1 |1 |* |0 |
57  // ==|0 |0 |* |* |1 |0 |1 |
58  // !=|1 |1 |* |* |0 |1 |0 |
59  //
60  // Columns stands for a previous operator.
61  // Rows stands for a current operator.
62  // Each row has exactly two `Unknown` cases.
63  // UnknownX2 means that both `Unknown` previous operators are met in code,
64  // and there is a special column for that, for example:
65  // if (x >= y)
66  // if (x != y)
67  // if (x <= y)
68  // False only
69  static constexpr size_t CmpOpCount = BO_NE - BO_LT + 1;
70  const TriStateKind CmpOpTable[CmpOpCount][CmpOpCount + 1] = {
71  // < > <= >= == != UnknownX2
72  {True, False, Unknown, False, False, Unknown, True}, // <
73  {False, True, False, Unknown, False, Unknown, True}, // >
74  {True, False, True, Unknown, True, Unknown, False}, // <=
75  {False, True, Unknown, True, True, Unknown, False}, // >=
76  {False, False, Unknown, Unknown, True, False, True}, // ==
77  {True, True, Unknown, Unknown, False, True, False}, // !=
78  };
79 
80  static size_t getIndexFromOp(BinaryOperatorKind OP) {
81  return static_cast<size_t>(OP - BO_LT);
82  }
83 
84 public:
85  constexpr size_t getCmpOpCount() const { return CmpOpCount; }
86 
87  static BinaryOperatorKind getOpFromIndex(size_t Index) {
88  return static_cast<BinaryOperatorKind>(Index + BO_LT);
89  }
90 
92  BinaryOperatorKind QueriedOP) const {
93  return CmpOpTable[getIndexFromOp(CurrentOP)][getIndexFromOp(QueriedOP)];
94  }
95 
97  return CmpOpTable[getIndexFromOp(CurrentOP)][CmpOpCount];
98  }
99 };
100 //===----------------------------------------------------------------------===//
101 // RangeSet implementation
102 //===----------------------------------------------------------------------===//
103 
104 void RangeSet::IntersectInRange(BasicValueFactory &BV, Factory &F,
105  const llvm::APSInt &Lower,
106  const llvm::APSInt &Upper,
107  PrimRangeSet &newRanges,
108  PrimRangeSet::iterator &i,
109  PrimRangeSet::iterator &e) const {
110  // There are six cases for each range R in the set:
111  // 1. R is entirely before the intersection range.
112  // 2. R is entirely after the intersection range.
113  // 3. R contains the entire intersection range.
114  // 4. R starts before the intersection range and ends in the middle.
115  // 5. R starts in the middle of the intersection range and ends after it.
116  // 6. R is entirely contained in the intersection range.
117  // These correspond to each of the conditions below.
118  for (/* i = begin(), e = end() */; i != e; ++i) {
119  if (i->To() < Lower) {
120  continue;
121  }
122  if (i->From() > Upper) {
123  break;
124  }
125 
126  if (i->Includes(Lower)) {
127  if (i->Includes(Upper)) {
128  newRanges =
129  F.add(newRanges, Range(BV.getValue(Lower), BV.getValue(Upper)));
130  break;
131  } else
132  newRanges = F.add(newRanges, Range(BV.getValue(Lower), i->To()));
133  } else {
134  if (i->Includes(Upper)) {
135  newRanges = F.add(newRanges, Range(i->From(), BV.getValue(Upper)));
136  break;
137  } else
138  newRanges = F.add(newRanges, *i);
139  }
140  }
141 }
142 
144  assert(!isEmpty());
145  return begin()->From();
146 }
147 
149  assert(!isEmpty());
150  // NOTE: It's a shame that we can't implement 'getMaxValue' without scanning
151  // the whole tree to get to the last element.
152  // llvm::ImmutableSet should support decrement for 'end' iterators
153  // or reverse order iteration.
154  auto It = begin();
155  for (auto End = end(); std::next(It) != End; ++It) {
156  }
157  return It->To();
158 }
159 
160 bool RangeSet::pin(llvm::APSInt &Lower, llvm::APSInt &Upper) const {
161  if (isEmpty()) {
162  // This range is already infeasible.
163  return false;
164  }
165 
166  // This function has nine cases, the cartesian product of range-testing
167  // both the upper and lower bounds against the symbol's type.
168  // Each case requires a different pinning operation.
169  // The function returns false if the described range is entirely outside
170  // the range of values for the associated symbol.
171  APSIntType Type(getMinValue());
172  APSIntType::RangeTestResultKind LowerTest = Type.testInRange(Lower, true);
173  APSIntType::RangeTestResultKind UpperTest = Type.testInRange(Upper, true);
174 
175  switch (LowerTest) {
177  switch (UpperTest) {
179  // The entire range is outside the symbol's set of possible values.
180  // If this is a conventionally-ordered range, the state is infeasible.
181  if (Lower <= Upper)
182  return false;
183 
184  // However, if the range wraps around, it spans all possible values.
185  Lower = Type.getMinValue();
186  Upper = Type.getMaxValue();
187  break;
189  // The range starts below what's possible but ends within it. Pin.
190  Lower = Type.getMinValue();
191  Type.apply(Upper);
192  break;
194  // The range spans all possible values for the symbol. Pin.
195  Lower = Type.getMinValue();
196  Upper = Type.getMaxValue();
197  break;
198  }
199  break;
201  switch (UpperTest) {
203  // The range wraps around, but all lower values are not possible.
204  Type.apply(Lower);
205  Upper = Type.getMaxValue();
206  break;
208  // The range may or may not wrap around, but both limits are valid.
209  Type.apply(Lower);
210  Type.apply(Upper);
211  break;
213  // The range starts within what's possible but ends above it. Pin.
214  Type.apply(Lower);
215  Upper = Type.getMaxValue();
216  break;
217  }
218  break;
220  switch (UpperTest) {
222  // The range wraps but is outside the symbol's set of possible values.
223  return false;
225  // The range starts above what's possible but ends within it (wrap).
226  Lower = Type.getMinValue();
227  Type.apply(Upper);
228  break;
230  // The entire range is outside the symbol's set of possible values.
231  // If this is a conventionally-ordered range, the state is infeasible.
232  if (Lower <= Upper)
233  return false;
234 
235  // However, if the range wraps around, it spans all possible values.
236  Lower = Type.getMinValue();
237  Upper = Type.getMaxValue();
238  break;
239  }
240  break;
241  }
242 
243  return true;
244 }
245 
246 // Returns a set containing the values in the receiving set, intersected with
247 // the closed range [Lower, Upper]. Unlike the Range type, this range uses
248 // modular arithmetic, corresponding to the common treatment of C integer
249 // overflow. Thus, if the Lower bound is greater than the Upper bound, the
250 // range is taken to wrap around. This is equivalent to taking the
251 // intersection with the two ranges [Min, Upper] and [Lower, Max],
252 // or, alternatively, /removing/ all integers between Upper and Lower.
254  llvm::APSInt Lower, llvm::APSInt Upper) const {
255  PrimRangeSet newRanges = F.getEmptySet();
256 
257  if (isEmpty() || !pin(Lower, Upper))
258  return newRanges;
259 
260  PrimRangeSet::iterator i = begin(), e = end();
261  if (Lower <= Upper)
262  IntersectInRange(BV, F, Lower, Upper, newRanges, i, e);
263  else {
264  // The order of the next two statements is important!
265  // IntersectInRange() does not reset the iteration state for i and e.
266  // Therefore, the lower range most be handled first.
267  IntersectInRange(BV, F, BV.getMinValue(Upper), Upper, newRanges, i, e);
268  IntersectInRange(BV, F, Lower, BV.getMaxValue(Lower), newRanges, i, e);
269  }
270 
271  return newRanges;
272 }
273 
274 // Returns a set containing the values in the receiving set, intersected with
275 // the range set passed as parameter.
277  const RangeSet &Other) const {
278  PrimRangeSet newRanges = F.getEmptySet();
279 
280  for (iterator i = Other.begin(), e = Other.end(); i != e; ++i) {
281  RangeSet newPiece = Intersect(BV, F, i->From(), i->To());
282  for (iterator j = newPiece.begin(), ee = newPiece.end(); j != ee; ++j) {
283  newRanges = F.add(newRanges, *j);
284  }
285  }
286 
287  return newRanges;
288 }
289 
290 // Turn all [A, B] ranges to [-B, -A], when "-" is a C-like unary minus
291 // operation under the values of the type.
292 //
293 // We also handle MIN because applying unary minus to MIN does not change it.
294 // Example 1:
295 // char x = -128; // -128 is a MIN value in a range of 'char'
296 // char y = -x; // y: -128
297 // Example 2:
298 // unsigned char x = 0; // 0 is a MIN value in a range of 'unsigned char'
299 // unsigned char y = -x; // y: 0
300 //
301 // And it makes us to separate the range
302 // like [MIN, N] to [MIN, MIN] U [-N,MAX].
303 // For instance, whole range is {-128..127} and subrange is [-128,-126],
304 // thus [-128,-127,-126,.....] negates to [-128,.....,126,127].
305 //
306 // Negate restores disrupted ranges on bounds,
307 // e.g. [MIN, B] => [MIN, MIN] U [-B, MAX] => [MIN, B].
309  PrimRangeSet newRanges = F.getEmptySet();
310 
311  if (isEmpty())
312  return newRanges;
313 
314  const llvm::APSInt sampleValue = getMinValue();
315  const llvm::APSInt &MIN = BV.getMinValue(sampleValue);
316  const llvm::APSInt &MAX = BV.getMaxValue(sampleValue);
317 
318  // Handle a special case for MIN value.
319  iterator i = begin();
320  const llvm::APSInt &from = i->From();
321  const llvm::APSInt &to = i->To();
322  if (from == MIN) {
323  // If [from, to] are [MIN, MAX], then just return the same [MIN, MAX].
324  if (to == MAX) {
325  newRanges = ranges;
326  } else {
327  // Add separate range for the lowest value.
328  newRanges = F.add(newRanges, Range(MIN, MIN));
329  // Skip adding the second range in case when [from, to] are [MIN, MIN].
330  if (to != MIN) {
331  newRanges = F.add(newRanges, Range(BV.getValue(-to), MAX));
332  }
333  }
334  // Skip the first range in the loop.
335  ++i;
336  }
337 
338  // Negate all other ranges.
339  for (iterator e = end(); i != e; ++i) {
340  // Negate int values.
341  const llvm::APSInt &newFrom = BV.getValue(-i->To());
342  const llvm::APSInt &newTo = BV.getValue(-i->From());
343  // Add a negated range.
344  newRanges = F.add(newRanges, Range(newFrom, newTo));
345  }
346 
347  if (newRanges.isSingleton())
348  return newRanges;
349 
350  // Try to find and unite next ranges:
351  // [MIN, MIN] & [MIN + 1, N] => [MIN, N].
352  iterator iter1 = newRanges.begin();
353  iterator iter2 = std::next(iter1);
354 
355  if (iter1->To() == MIN && (iter2->From() - 1) == MIN) {
356  const llvm::APSInt &to = iter2->To();
357  // remove adjacent ranges
358  newRanges = F.remove(newRanges, *iter1);
359  newRanges = F.remove(newRanges, *newRanges.begin());
360  // add united range
361  newRanges = F.add(newRanges, Range(MIN, to));
362  }
363 
364  return newRanges;
365 }
366 
367 void RangeSet::print(raw_ostream &os) const {
368  bool isFirst = true;
369  os << "{ ";
370  for (iterator i = begin(), e = end(); i != e; ++i) {
371  if (isFirst)
372  isFirst = false;
373  else
374  os << ", ";
375 
376  os << '[' << i->From().toString(10) << ", " << i->To().toString(10)
377  << ']';
378  }
379  os << " }";
380 }
381 
382 namespace {
383 
384 /// A little component aggregating all of the reasoning we have about
385 /// the ranges of symbolic expressions.
386 ///
387 /// Even when we don't know the exact values of the operands, we still
388 /// can get a pretty good estimate of the result's range.
389 class SymbolicRangeInferrer
390  : public SymExprVisitor<SymbolicRangeInferrer, RangeSet> {
391 public:
392  static RangeSet inferRange(BasicValueFactory &BV, RangeSet::Factory &F,
394  SymbolicRangeInferrer Inferrer(BV, F, State);
395  return Inferrer.infer(Sym);
396  }
397 
398  RangeSet VisitSymExpr(SymbolRef Sym) {
399  // If we got to this function, the actual type of the symbolic
400  // expression is not supported for advanced inference.
401  // In this case, we simply backoff to the default "let's simply
402  // infer the range from the expression's type".
403  return infer(Sym->getType());
404  }
405 
406  RangeSet VisitSymIntExpr(const SymIntExpr *Sym) {
407  return VisitBinaryOperator(Sym);
408  }
409 
410  RangeSet VisitIntSymExpr(const IntSymExpr *Sym) {
411  return VisitBinaryOperator(Sym);
412  }
413 
414  RangeSet VisitSymSymExpr(const SymSymExpr *Sym) {
415  return VisitBinaryOperator(Sym);
416  }
417 
418 private:
419  SymbolicRangeInferrer(BasicValueFactory &BV, RangeSet::Factory &F,
420  ProgramStateRef S)
421  : ValueFactory(BV), RangeFactory(F), State(S) {}
422 
423  /// Infer range information from the given integer constant.
424  ///
425  /// It's not a real "inference", but is here for operating with
426  /// sub-expressions in a more polymorphic manner.
427  RangeSet inferAs(const llvm::APSInt &Val, QualType) {
428  return {RangeFactory, Val};
429  }
430 
431  /// Infer range information from symbol in the context of the given type.
432  RangeSet inferAs(SymbolRef Sym, QualType DestType) {
433  QualType ActualType = Sym->getType();
434  // Check that we can reason about the symbol at all.
435  if (ActualType->isIntegralOrEnumerationType() ||
436  Loc::isLocType(ActualType)) {
437  return infer(Sym);
438  }
439  // Otherwise, let's simply infer from the destination type.
440  // We couldn't figure out nothing else about that expression.
441  return infer(DestType);
442  }
443 
444  RangeSet infer(SymbolRef Sym) {
445  const RangeSet *AssociatedRange = State->get<ConstraintRange>(Sym);
446 
447  // If Sym is a difference of symbols A - B, then maybe we have range set
448  // stored for B - A.
449  const RangeSet *RangeAssociatedWithNegatedSym =
450  getRangeForMinusSymbol(State, Sym);
451 
452  // If we have range set stored for both A - B and B - A then calculate the
453  // effective range set by intersecting the range set for A - B and the
454  // negated range set of B - A.
455  if (AssociatedRange && RangeAssociatedWithNegatedSym)
456  return AssociatedRange->Intersect(
457  ValueFactory, RangeFactory,
458  RangeAssociatedWithNegatedSym->Negate(ValueFactory, RangeFactory));
459 
460  if (AssociatedRange)
461  return *AssociatedRange;
462 
463  if (RangeAssociatedWithNegatedSym)
464  return RangeAssociatedWithNegatedSym->Negate(ValueFactory, RangeFactory);
465 
466  // If Sym is a comparison expression (except <=>),
467  // find any other comparisons with the same operands.
468  // See function description.
469  const RangeSet CmpRangeSet = getRangeForComparisonSymbol(State, Sym);
470  if (!CmpRangeSet.isEmpty())
471  return CmpRangeSet;
472 
473  return Visit(Sym);
474  }
475 
476  /// Infer range information solely from the type.
477  RangeSet infer(QualType T) {
478  // Lazily generate a new RangeSet representing all possible values for the
479  // given symbol type.
480  RangeSet Result(RangeFactory, ValueFactory.getMinValue(T),
481  ValueFactory.getMaxValue(T));
482 
483  // References are known to be non-zero.
484  if (T->isReferenceType())
485  return assumeNonZero(Result, T);
486 
487  return Result;
488  }
489 
490  template <class BinarySymExprTy>
491  RangeSet VisitBinaryOperator(const BinarySymExprTy *Sym) {
492  // TODO #1: VisitBinaryOperator implementation might not make a good
493  // use of the inferred ranges. In this case, we might be calculating
494  // everything for nothing. This being said, we should introduce some
495  // sort of laziness mechanism here.
496  //
497  // TODO #2: We didn't go into the nested expressions before, so it
498  // might cause us spending much more time doing the inference.
499  // This can be a problem for deeply nested expressions that are
500  // involved in conditions and get tested continuously. We definitely
501  // need to address this issue and introduce some sort of caching
502  // in here.
503  QualType ResultType = Sym->getType();
504  return VisitBinaryOperator(inferAs(Sym->getLHS(), ResultType),
505  Sym->getOpcode(),
506  inferAs(Sym->getRHS(), ResultType), ResultType);
507  }
508 
509  RangeSet VisitBinaryOperator(RangeSet LHS, BinaryOperator::Opcode Op,
510  RangeSet RHS, QualType T) {
511  switch (Op) {
512  case BO_Or:
513  return VisitBinaryOperator<BO_Or>(LHS, RHS, T);
514  case BO_And:
515  return VisitBinaryOperator<BO_And>(LHS, RHS, T);
516  case BO_Rem:
517  return VisitBinaryOperator<BO_Rem>(LHS, RHS, T);
518  default:
519  return infer(T);
520  }
521  }
522 
523  //===----------------------------------------------------------------------===//
524  // Ranges and operators
525  //===----------------------------------------------------------------------===//
526 
527  /// Return a rough approximation of the given range set.
528  ///
529  /// For the range set:
530  /// { [x_0, y_0], [x_1, y_1], ... , [x_N, y_N] }
531  /// it will return the range [x_0, y_N].
532  static Range fillGaps(RangeSet Origin) {
533  assert(!Origin.isEmpty());
534  return {Origin.getMinValue(), Origin.getMaxValue()};
535  }
536 
537  /// Try to convert given range into the given type.
538  ///
539  /// It will return llvm::None only when the trivial conversion is possible.
540  llvm::Optional<Range> convert(const Range &Origin, APSIntType To) {
541  if (To.testInRange(Origin.From(), false) != APSIntType::RTR_Within ||
542  To.testInRange(Origin.To(), false) != APSIntType::RTR_Within) {
543  return llvm::None;
544  }
545  return Range(ValueFactory.Convert(To, Origin.From()),
546  ValueFactory.Convert(To, Origin.To()));
547  }
548 
549  template <BinaryOperator::Opcode Op>
550  RangeSet VisitBinaryOperator(RangeSet LHS, RangeSet RHS, QualType T) {
551  // We should propagate information about unfeasbility of one of the
552  // operands to the resulting range.
553  if (LHS.isEmpty() || RHS.isEmpty()) {
554  return RangeFactory.getEmptySet();
555  }
556 
557  Range CoarseLHS = fillGaps(LHS);
558  Range CoarseRHS = fillGaps(RHS);
559 
560  APSIntType ResultType = ValueFactory.getAPSIntType(T);
561 
562  // We need to convert ranges to the resulting type, so we can compare values
563  // and combine them in a meaningful (in terms of the given operation) way.
564  auto ConvertedCoarseLHS = convert(CoarseLHS, ResultType);
565  auto ConvertedCoarseRHS = convert(CoarseRHS, ResultType);
566 
567  // It is hard to reason about ranges when conversion changes
568  // borders of the ranges.
569  if (!ConvertedCoarseLHS || !ConvertedCoarseRHS) {
570  return infer(T);
571  }
572 
573  return VisitBinaryOperator<Op>(*ConvertedCoarseLHS, *ConvertedCoarseRHS, T);
574  }
575 
576  template <BinaryOperator::Opcode Op>
577  RangeSet VisitBinaryOperator(Range LHS, Range RHS, QualType T) {
578  return infer(T);
579  }
580 
581  /// Return a symmetrical range for the given range and type.
582  ///
583  /// If T is signed, return the smallest range [-x..x] that covers the original
584  /// range, or [-min(T), max(T)] if the aforementioned symmetric range doesn't
585  /// exist due to original range covering min(T)).
586  ///
587  /// If T is unsigned, return the smallest range [0..x] that covers the
588  /// original range.
589  Range getSymmetricalRange(Range Origin, QualType T) {
590  APSIntType RangeType = ValueFactory.getAPSIntType(T);
591 
592  if (RangeType.isUnsigned()) {
593  return Range(ValueFactory.getMinValue(RangeType), Origin.To());
594  }
595 
596  if (Origin.From().isMinSignedValue()) {
597  // If mini is a minimal signed value, absolute value of it is greater
598  // than the maximal signed value. In order to avoid these
599  // complications, we simply return the whole range.
600  return {ValueFactory.getMinValue(RangeType),
601  ValueFactory.getMaxValue(RangeType)};
602  }
603 
604  // At this point, we are sure that the type is signed and we can safely
605  // use unary - operator.
606  //
607  // While calculating absolute maximum, we can use the following formula
608  // because of these reasons:
609  // * If From >= 0 then To >= From and To >= -From.
610  // AbsMax == To == max(To, -From)
611  // * If To <= 0 then -From >= -To and -From >= From.
612  // AbsMax == -From == max(-From, To)
613  // * Otherwise, From <= 0, To >= 0, and
614  // AbsMax == max(abs(From), abs(To))
615  llvm::APSInt AbsMax = std::max(-Origin.From(), Origin.To());
616 
617  // Intersection is guaranteed to be non-empty.
618  return {ValueFactory.getValue(-AbsMax), ValueFactory.getValue(AbsMax)};
619  }
620 
621  /// Return a range set subtracting zero from \p Domain.
622  RangeSet assumeNonZero(RangeSet Domain, QualType T) {
623  APSIntType IntType = ValueFactory.getAPSIntType(T);
624  return Domain.Intersect(ValueFactory, RangeFactory,
625  ++IntType.getZeroValue(), --IntType.getZeroValue());
626  }
627 
628  // FIXME: Once SValBuilder supports unary minus, we should use SValBuilder to
629  // obtain the negated symbolic expression instead of constructing the
630  // symbol manually. This will allow us to support finding ranges of not
631  // only negated SymSymExpr-type expressions, but also of other, simpler
632  // expressions which we currently do not know how to negate.
633  const RangeSet *getRangeForMinusSymbol(ProgramStateRef State, SymbolRef Sym) {
634  if (const SymSymExpr *SSE = dyn_cast<SymSymExpr>(Sym)) {
635  if (SSE->getOpcode() == BO_Sub) {
636  QualType T = Sym->getType();
637  SymbolManager &SymMgr = State->getSymbolManager();
638  SymbolRef negSym =
639  SymMgr.getSymSymExpr(SSE->getRHS(), BO_Sub, SSE->getLHS(), T);
640 
641  if (const RangeSet *negV = State->get<ConstraintRange>(negSym)) {
642  // Unsigned range set cannot be negated, unless it is [0, 0].
645  return negV;
646  }
647  }
648  }
649  return nullptr;
650  }
651 
652  // Returns ranges only for binary comparison operators (except <=>)
653  // when left and right operands are symbolic values.
654  // Finds any other comparisons with the same operands.
655  // Then do logical calculations and refuse impossible branches.
656  // E.g. (x < y) and (x > y) at the same time are impossible.
657  // E.g. (x >= y) and (x != y) at the same time makes (x > y) true only.
658  // E.g. (x == y) and (y == x) are just reversed but the same.
659  // It covers all possible combinations (see CmpOpTable description).
660  // Note that `x` and `y` can also stand for subexpressions,
661  // not only for actual symbols.
662  RangeSet getRangeForComparisonSymbol(ProgramStateRef State, SymbolRef Sym) {
663  const RangeSet EmptyRangeSet = RangeFactory.getEmptySet();
664 
665  auto SSE = dyn_cast<SymSymExpr>(Sym);
666  if (!SSE)
667  return EmptyRangeSet;
668 
669  BinaryOperatorKind CurrentOP = SSE->getOpcode();
670 
671  // We currently do not support <=> (C++20).
672  if (!BinaryOperator::isComparisonOp(CurrentOP) || (CurrentOP == BO_Cmp))
673  return EmptyRangeSet;
674 
675  static const OperatorRelationsTable CmpOpTable{};
676 
677  const SymExpr *LHS = SSE->getLHS();
678  const SymExpr *RHS = SSE->getRHS();
679  QualType T = SSE->getType();
680 
681  SymbolManager &SymMgr = State->getSymbolManager();
682  const llvm::APSInt &Zero = ValueFactory.getValue(0, T);
683  const llvm::APSInt &One = ValueFactory.getValue(1, T);
684  const RangeSet TrueRangeSet(RangeFactory, One, One);
685  const RangeSet FalseRangeSet(RangeFactory, Zero, Zero);
686 
687  int UnknownStates = 0;
688 
689  // Loop goes through all of the columns exept the last one ('UnknownX2').
690  // We treat `UnknownX2` column separately at the end of the loop body.
691  for (size_t i = 0; i < CmpOpTable.getCmpOpCount(); ++i) {
692 
693  // Let's find an expression e.g. (x < y).
695  const SymSymExpr *SymSym = SymMgr.getSymSymExpr(LHS, QueriedOP, RHS, T);
696  const RangeSet *QueriedRangeSet = State->get<ConstraintRange>(SymSym);
697 
698  // If ranges were not previously found,
699  // try to find a reversed expression (y > x).
700  if (!QueriedRangeSet) {
701  const BinaryOperatorKind ROP =
703  SymSym = SymMgr.getSymSymExpr(RHS, ROP, LHS, T);
704  QueriedRangeSet = State->get<ConstraintRange>(SymSym);
705  }
706 
707  if (!QueriedRangeSet || QueriedRangeSet->isEmpty())
708  continue;
709 
710  const llvm::APSInt *ConcreteValue = QueriedRangeSet->getConcreteValue();
711  const bool isInFalseBranch =
712  ConcreteValue ? (*ConcreteValue == 0) : false;
713 
714  // If it is a false branch, we shall be guided by opposite operator,
715  // because the table is made assuming we are in the true branch.
716  // E.g. when (x <= y) is false, then (x > y) is true.
717  if (isInFalseBranch)
718  QueriedOP = BinaryOperator::negateComparisonOp(QueriedOP);
719 
721  CmpOpTable.getCmpOpState(CurrentOP, QueriedOP);
722 
723  if (BranchState == OperatorRelationsTable::Unknown) {
724  if (++UnknownStates == 2)
725  // If we met both Unknown states.
726  // if (x <= y) // assume true
727  // if (x != y) // assume true
728  // if (x < y) // would be also true
729  // Get a state from `UnknownX2` column.
730  BranchState = CmpOpTable.getCmpOpStateForUnknownX2(CurrentOP);
731  else
732  continue;
733  }
734 
735  return (BranchState == OperatorRelationsTable::True) ? TrueRangeSet
736  : FalseRangeSet;
737  }
738 
739  return EmptyRangeSet;
740  }
741 
742  BasicValueFactory &ValueFactory;
743  RangeSet::Factory &RangeFactory;
745 };
746 
747 template <>
748 RangeSet SymbolicRangeInferrer::VisitBinaryOperator<BO_Or>(Range LHS, Range RHS,
749  QualType T) {
750  APSIntType ResultType = ValueFactory.getAPSIntType(T);
751  llvm::APSInt Zero = ResultType.getZeroValue();
752 
753  bool IsLHSPositiveOrZero = LHS.From() >= Zero;
754  bool IsRHSPositiveOrZero = RHS.From() >= Zero;
755 
756  bool IsLHSNegative = LHS.To() < Zero;
757  bool IsRHSNegative = RHS.To() < Zero;
758 
759  // Check if both ranges have the same sign.
760  if ((IsLHSPositiveOrZero && IsRHSPositiveOrZero) ||
761  (IsLHSNegative && IsRHSNegative)) {
762  // The result is definitely greater or equal than any of the operands.
763  const llvm::APSInt &Min = std::max(LHS.From(), RHS.From());
764 
765  // We estimate maximal value for positives as the maximal value for the
766  // given type. For negatives, we estimate it with -1 (e.g. 0x11111111).
767  //
768  // TODO: We basically, limit the resulting range from below, but don't do
769  // anything with the upper bound.
770  //
771  // For positive operands, it can be done as follows: for the upper
772  // bound of LHS and RHS we calculate the most significant bit set.
773  // Let's call it the N-th bit. Then we can estimate the maximal
774  // number to be 2^(N+1)-1, i.e. the number with all the bits up to
775  // the N-th bit set.
776  const llvm::APSInt &Max = IsLHSNegative
777  ? ValueFactory.getValue(--Zero)
778  : ValueFactory.getMaxValue(ResultType);
779 
780  return {RangeFactory, ValueFactory.getValue(Min), Max};
781  }
782 
783  // Otherwise, let's check if at least one of the operands is negative.
784  if (IsLHSNegative || IsRHSNegative) {
785  // This means that the result is definitely negative as well.
786  return {RangeFactory, ValueFactory.getMinValue(ResultType),
787  ValueFactory.getValue(--Zero)};
788  }
789 
790  RangeSet DefaultRange = infer(T);
791 
792  // It is pretty hard to reason about operands with different signs
793  // (and especially with possibly different signs). We simply check if it
794  // can be zero. In order to conclude that the result could not be zero,
795  // at least one of the operands should be definitely not zero itself.
796  if (!LHS.Includes(Zero) || !RHS.Includes(Zero)) {
797  return assumeNonZero(DefaultRange, T);
798  }
799 
800  // Nothing much else to do here.
801  return DefaultRange;
802 }
803 
804 template <>
805 RangeSet SymbolicRangeInferrer::VisitBinaryOperator<BO_And>(Range LHS,
806  Range RHS,
807  QualType T) {
808  APSIntType ResultType = ValueFactory.getAPSIntType(T);
809  llvm::APSInt Zero = ResultType.getZeroValue();
810 
811  bool IsLHSPositiveOrZero = LHS.From() >= Zero;
812  bool IsRHSPositiveOrZero = RHS.From() >= Zero;
813 
814  bool IsLHSNegative = LHS.To() < Zero;
815  bool IsRHSNegative = RHS.To() < Zero;
816 
817  // Check if both ranges have the same sign.
818  if ((IsLHSPositiveOrZero && IsRHSPositiveOrZero) ||
819  (IsLHSNegative && IsRHSNegative)) {
820  // The result is definitely less or equal than any of the operands.
821  const llvm::APSInt &Max = std::min(LHS.To(), RHS.To());
822 
823  // We conservatively estimate lower bound to be the smallest positive
824  // or negative value corresponding to the sign of the operands.
825  const llvm::APSInt &Min = IsLHSNegative
826  ? ValueFactory.getMinValue(ResultType)
827  : ValueFactory.getValue(Zero);
828 
829  return {RangeFactory, Min, Max};
830  }
831 
832  // Otherwise, let's check if at least one of the operands is positive.
833  if (IsLHSPositiveOrZero || IsRHSPositiveOrZero) {
834  // This makes result definitely positive.
835  //
836  // We can also reason about a maximal value by finding the maximal
837  // value of the positive operand.
838  const llvm::APSInt &Max = IsLHSPositiveOrZero ? LHS.To() : RHS.To();
839 
840  // The minimal value on the other hand is much harder to reason about.
841  // The only thing we know for sure is that the result is positive.
842  return {RangeFactory, ValueFactory.getValue(Zero),
843  ValueFactory.getValue(Max)};
844  }
845 
846  // Nothing much else to do here.
847  return infer(T);
848 }
849 
850 template <>
851 RangeSet SymbolicRangeInferrer::VisitBinaryOperator<BO_Rem>(Range LHS,
852  Range RHS,
853  QualType T) {
854  llvm::APSInt Zero = ValueFactory.getAPSIntType(T).getZeroValue();
855 
856  Range ConservativeRange = getSymmetricalRange(RHS, T);
857 
858  llvm::APSInt Max = ConservativeRange.To();
859  llvm::APSInt Min = ConservativeRange.From();
860 
861  if (Max == Zero) {
862  // It's an undefined behaviour to divide by 0 and it seems like we know
863  // for sure that RHS is 0. Let's say that the resulting range is
864  // simply infeasible for that matter.
865  return RangeFactory.getEmptySet();
866  }
867 
868  // At this point, our conservative range is closed. The result, however,
869  // couldn't be greater than the RHS' maximal absolute value. Because of
870  // this reason, we turn the range into open (or half-open in case of
871  // unsigned integers).
872  //
873  // While we operate on integer values, an open interval (a, b) can be easily
874  // represented by the closed interval [a + 1, b - 1]. And this is exactly
875  // what we do next.
876  //
877  // If we are dealing with unsigned case, we shouldn't move the lower bound.
878  if (Min.isSigned()) {
879  ++Min;
880  }
881  --Max;
882 
883  bool IsLHSPositiveOrZero = LHS.From() >= Zero;
884  bool IsRHSPositiveOrZero = RHS.From() >= Zero;
885 
886  // Remainder operator results with negative operands is implementation
887  // defined. Positive cases are much easier to reason about though.
888  if (IsLHSPositiveOrZero && IsRHSPositiveOrZero) {
889  // If maximal value of LHS is less than maximal value of RHS,
890  // the result won't get greater than LHS.To().
891  Max = std::min(LHS.To(), Max);
892  // We want to check if it is a situation similar to the following:
893  //
894  // <------------|---[ LHS ]--------[ RHS ]----->
895  // -INF 0 +INF
896  //
897  // In this situation, we can conclude that (LHS / RHS) == 0 and
898  // (LHS % RHS) == LHS.
899  Min = LHS.To() < RHS.From() ? LHS.From() : Zero;
900  }
901 
902  // Nevertheless, the symmetrical range for RHS is a conservative estimate
903  // for any sign of either LHS, or RHS.
904  return {RangeFactory, ValueFactory.getValue(Min), ValueFactory.getValue(Max)};
905 }
906 
907 class RangeConstraintManager : public RangedConstraintManager {
908 public:
909  RangeConstraintManager(ExprEngine *EE, SValBuilder &SVB)
910  : RangedConstraintManager(EE, SVB) {}
911 
912  //===------------------------------------------------------------------===//
913  // Implementation for interface from ConstraintManager.
914  //===------------------------------------------------------------------===//
915 
916  bool haveEqualConstraints(ProgramStateRef S1,
917  ProgramStateRef S2) const override {
918  return S1->get<ConstraintRange>() == S2->get<ConstraintRange>();
919  }
920 
921  bool canReasonAbout(SVal X) const override;
922 
923  ConditionTruthVal checkNull(ProgramStateRef State, SymbolRef Sym) override;
924 
925  const llvm::APSInt *getSymVal(ProgramStateRef State,
926  SymbolRef Sym) const override;
927 
928  ProgramStateRef removeDeadBindings(ProgramStateRef State,
929  SymbolReaper &SymReaper) override;
930 
931  void printJson(raw_ostream &Out, ProgramStateRef State, const char *NL = "\n",
932  unsigned int Space = 0, bool IsDot = false) const override;
933 
934  //===------------------------------------------------------------------===//
935  // Implementation for interface from RangedConstraintManager.
936  //===------------------------------------------------------------------===//
937 
938  ProgramStateRef assumeSymNE(ProgramStateRef State, SymbolRef Sym,
939  const llvm::APSInt &V,
940  const llvm::APSInt &Adjustment) override;
941 
942  ProgramStateRef assumeSymEQ(ProgramStateRef State, SymbolRef Sym,
943  const llvm::APSInt &V,
944  const llvm::APSInt &Adjustment) override;
945 
946  ProgramStateRef assumeSymLT(ProgramStateRef State, SymbolRef Sym,
947  const llvm::APSInt &V,
948  const llvm::APSInt &Adjustment) override;
949 
950  ProgramStateRef assumeSymGT(ProgramStateRef State, SymbolRef Sym,
951  const llvm::APSInt &V,
952  const llvm::APSInt &Adjustment) override;
953 
954  ProgramStateRef assumeSymLE(ProgramStateRef State, SymbolRef Sym,
955  const llvm::APSInt &V,
956  const llvm::APSInt &Adjustment) override;
957 
958  ProgramStateRef assumeSymGE(ProgramStateRef State, SymbolRef Sym,
959  const llvm::APSInt &V,
960  const llvm::APSInt &Adjustment) override;
961 
962  ProgramStateRef assumeSymWithinInclusiveRange(
963  ProgramStateRef State, SymbolRef Sym, const llvm::APSInt &From,
964  const llvm::APSInt &To, const llvm::APSInt &Adjustment) override;
965 
966  ProgramStateRef assumeSymOutsideInclusiveRange(
967  ProgramStateRef State, SymbolRef Sym, const llvm::APSInt &From,
968  const llvm::APSInt &To, const llvm::APSInt &Adjustment) override;
969 
970 private:
972 
973  RangeSet getRange(ProgramStateRef State, SymbolRef Sym);
974 
975  RangeSet getSymLTRange(ProgramStateRef St, SymbolRef Sym,
976  const llvm::APSInt &Int,
977  const llvm::APSInt &Adjustment);
978  RangeSet getSymGTRange(ProgramStateRef St, SymbolRef Sym,
979  const llvm::APSInt &Int,
980  const llvm::APSInt &Adjustment);
981  RangeSet getSymLERange(ProgramStateRef St, SymbolRef Sym,
982  const llvm::APSInt &Int,
983  const llvm::APSInt &Adjustment);
984  RangeSet getSymLERange(llvm::function_ref<RangeSet()> RS,
985  const llvm::APSInt &Int,
986  const llvm::APSInt &Adjustment);
987  RangeSet getSymGERange(ProgramStateRef St, SymbolRef Sym,
988  const llvm::APSInt &Int,
989  const llvm::APSInt &Adjustment);
990 };
991 
992 } // end anonymous namespace
993 
994 std::unique_ptr<ConstraintManager>
996  ExprEngine *Eng) {
997  return std::make_unique<RangeConstraintManager>(Eng, StMgr.getSValBuilder());
998 }
999 
1000 bool RangeConstraintManager::canReasonAbout(SVal X) const {
1002  if (SymVal && SymVal->isExpression()) {
1003  const SymExpr *SE = SymVal->getSymbol();
1004 
1005  if (const SymIntExpr *SIE = dyn_cast<SymIntExpr>(SE)) {
1006  switch (SIE->getOpcode()) {
1007  // We don't reason yet about bitwise-constraints on symbolic values.
1008  case BO_And:
1009  case BO_Or:
1010  case BO_Xor:
1011  return false;
1012  // We don't reason yet about these arithmetic constraints on
1013  // symbolic values.
1014  case BO_Mul:
1015  case BO_Div:
1016  case BO_Rem:
1017  case BO_Shl:
1018  case BO_Shr:
1019  return false;
1020  // All other cases.
1021  default:
1022  return true;
1023  }
1024  }
1025 
1026  if (const SymSymExpr *SSE = dyn_cast<SymSymExpr>(SE)) {
1027  // FIXME: Handle <=> here.
1028  if (BinaryOperator::isEqualityOp(SSE->getOpcode()) ||
1029  BinaryOperator::isRelationalOp(SSE->getOpcode())) {
1030  // We handle Loc <> Loc comparisons, but not (yet) NonLoc <> NonLoc.
1031  // We've recently started producing Loc <> NonLoc comparisons (that
1032  // result from casts of one of the operands between eg. intptr_t and
1033  // void *), but we can't reason about them yet.
1034  if (Loc::isLocType(SSE->getLHS()->getType())) {
1035  return Loc::isLocType(SSE->getRHS()->getType());
1036  }
1037  }
1038  }
1039 
1040  return false;
1041  }
1042 
1043  return true;
1044 }
1045 
1046 ConditionTruthVal RangeConstraintManager::checkNull(ProgramStateRef State,
1047  SymbolRef Sym) {
1048  const RangeSet *Ranges = State->get<ConstraintRange>(Sym);
1049 
1050  // If we don't have any information about this symbol, it's underconstrained.
1051  if (!Ranges)
1052  return ConditionTruthVal();
1053 
1054  // If we have a concrete value, see if it's zero.
1055  if (const llvm::APSInt *Value = Ranges->getConcreteValue())
1056  return *Value == 0;
1057 
1058  BasicValueFactory &BV = getBasicVals();
1059  APSIntType IntType = BV.getAPSIntType(Sym->getType());
1060  llvm::APSInt Zero = IntType.getZeroValue();
1061 
1062  // Check if zero is in the set of possible values.
1063  if (Ranges->Intersect(BV, F, Zero, Zero).isEmpty())
1064  return false;
1065 
1066  // Zero is a possible value, but it is not the /only/ possible value.
1067  return ConditionTruthVal();
1068 }
1069 
1070 const llvm::APSInt *RangeConstraintManager::getSymVal(ProgramStateRef St,
1071  SymbolRef Sym) const {
1072  const ConstraintRangeTy::data_type *T = St->get<ConstraintRange>(Sym);
1073  return T ? T->getConcreteValue() : nullptr;
1074 }
1075 
1076 /// Scan all symbols referenced by the constraints. If the symbol is not alive
1077 /// as marked in LSymbols, mark it as dead in DSymbols.
1079 RangeConstraintManager::removeDeadBindings(ProgramStateRef State,
1080  SymbolReaper &SymReaper) {
1081  bool Changed = false;
1082  ConstraintRangeTy CR = State->get<ConstraintRange>();
1083  ConstraintRangeTy::Factory &CRFactory = State->get_context<ConstraintRange>();
1084 
1085  for (ConstraintRangeTy::iterator I = CR.begin(), E = CR.end(); I != E; ++I) {
1086  SymbolRef Sym = I.getKey();
1087  if (SymReaper.isDead(Sym)) {
1088  Changed = true;
1089  CR = CRFactory.remove(CR, Sym);
1090  }
1091  }
1092 
1093  return Changed ? State->set<ConstraintRange>(CR) : State;
1094 }
1095 
1096 RangeSet RangeConstraintManager::getRange(ProgramStateRef State,
1097  SymbolRef Sym) {
1098  return SymbolicRangeInferrer::inferRange(getBasicVals(), F, State, Sym);
1099 }
1100 
1101 //===------------------------------------------------------------------------===
1102 // assumeSymX methods: protected interface for RangeConstraintManager.
1103 //===------------------------------------------------------------------------===/
1104 
1105 // The syntax for ranges below is mathematical, using [x, y] for closed ranges
1106 // and (x, y) for open ranges. These ranges are modular, corresponding with
1107 // a common treatment of C integer overflow. This means that these methods
1108 // do not have to worry about overflow; RangeSet::Intersect can handle such a
1109 // "wraparound" range.
1110 // As an example, the range [UINT_MAX-1, 3) contains five values: UINT_MAX-1,
1111 // UINT_MAX, 0, 1, and 2.
1112 
1114 RangeConstraintManager::assumeSymNE(ProgramStateRef St, SymbolRef Sym,
1115  const llvm::APSInt &Int,
1116  const llvm::APSInt &Adjustment) {
1117  // Before we do any real work, see if the value can even show up.
1118  APSIntType AdjustmentType(Adjustment);
1119  if (AdjustmentType.testInRange(Int, true) != APSIntType::RTR_Within)
1120  return St;
1121 
1122  llvm::APSInt Lower = AdjustmentType.convert(Int) - Adjustment;
1123  llvm::APSInt Upper = Lower;
1124  --Lower;
1125  ++Upper;
1126 
1127  // [Int-Adjustment+1, Int-Adjustment-1]
1128  // Notice that the lower bound is greater than the upper bound.
1129  RangeSet New = getRange(St, Sym).Intersect(getBasicVals(), F, Upper, Lower);
1130  return New.isEmpty() ? nullptr : St->set<ConstraintRange>(Sym, New);
1131 }
1132 
1134 RangeConstraintManager::assumeSymEQ(ProgramStateRef St, SymbolRef Sym,
1135  const llvm::APSInt &Int,
1136  const llvm::APSInt &Adjustment) {
1137  // Before we do any real work, see if the value can even show up.
1138  APSIntType AdjustmentType(Adjustment);
1139  if (AdjustmentType.testInRange(Int, true) != APSIntType::RTR_Within)
1140  return nullptr;
1141 
1142  // [Int-Adjustment, Int-Adjustment]
1143  llvm::APSInt AdjInt = AdjustmentType.convert(Int) - Adjustment;
1144  RangeSet New = getRange(St, Sym).Intersect(getBasicVals(), F, AdjInt, AdjInt);
1145  return New.isEmpty() ? nullptr : St->set<ConstraintRange>(Sym, New);
1146 }
1147 
1148 RangeSet RangeConstraintManager::getSymLTRange(ProgramStateRef St,
1149  SymbolRef Sym,
1150  const llvm::APSInt &Int,
1151  const llvm::APSInt &Adjustment) {
1152  // Before we do any real work, see if the value can even show up.
1153  APSIntType AdjustmentType(Adjustment);
1154  switch (AdjustmentType.testInRange(Int, true)) {
1155  case APSIntType::RTR_Below:
1156  return F.getEmptySet();
1158  break;
1159  case APSIntType::RTR_Above:
1160  return getRange(St, Sym);
1161  }
1162 
1163  // Special case for Int == Min. This is always false.
1164  llvm::APSInt ComparisonVal = AdjustmentType.convert(Int);
1165  llvm::APSInt Min = AdjustmentType.getMinValue();
1166  if (ComparisonVal == Min)
1167  return F.getEmptySet();
1168 
1169  llvm::APSInt Lower = Min - Adjustment;
1170  llvm::APSInt Upper = ComparisonVal - Adjustment;
1171  --Upper;
1172 
1173  return getRange(St, Sym).Intersect(getBasicVals(), F, Lower, Upper);
1174 }
1175 
1177 RangeConstraintManager::assumeSymLT(ProgramStateRef St, SymbolRef Sym,
1178  const llvm::APSInt &Int,
1179  const llvm::APSInt &Adjustment) {
1180  RangeSet New = getSymLTRange(St, Sym, Int, Adjustment);
1181  return New.isEmpty() ? nullptr : St->set<ConstraintRange>(Sym, New);
1182 }
1183 
1184 RangeSet RangeConstraintManager::getSymGTRange(ProgramStateRef St,
1185  SymbolRef Sym,
1186  const llvm::APSInt &Int,
1187  const llvm::APSInt &Adjustment) {
1188  // Before we do any real work, see if the value can even show up.
1189  APSIntType AdjustmentType(Adjustment);
1190  switch (AdjustmentType.testInRange(Int, true)) {
1191  case APSIntType::RTR_Below:
1192  return getRange(St, Sym);
1194  break;
1195  case APSIntType::RTR_Above:
1196  return F.getEmptySet();
1197  }
1198 
1199  // Special case for Int == Max. This is always false.
1200  llvm::APSInt ComparisonVal = AdjustmentType.convert(Int);
1201  llvm::APSInt Max = AdjustmentType.getMaxValue();
1202  if (ComparisonVal == Max)
1203  return F.getEmptySet();
1204 
1205  llvm::APSInt Lower = ComparisonVal - Adjustment;
1206  llvm::APSInt Upper = Max - Adjustment;
1207  ++Lower;
1208 
1209  return getRange(St, Sym).Intersect(getBasicVals(), F, Lower, Upper);
1210 }
1211 
1213 RangeConstraintManager::assumeSymGT(ProgramStateRef St, SymbolRef Sym,
1214  const llvm::APSInt &Int,
1215  const llvm::APSInt &Adjustment) {
1216  RangeSet New = getSymGTRange(St, Sym, Int, Adjustment);
1217  return New.isEmpty() ? nullptr : St->set<ConstraintRange>(Sym, New);
1218 }
1219 
1220 RangeSet RangeConstraintManager::getSymGERange(ProgramStateRef St,
1221  SymbolRef Sym,
1222  const llvm::APSInt &Int,
1223  const llvm::APSInt &Adjustment) {
1224  // Before we do any real work, see if the value can even show up.
1225  APSIntType AdjustmentType(Adjustment);
1226  switch (AdjustmentType.testInRange(Int, true)) {
1227  case APSIntType::RTR_Below:
1228  return getRange(St, Sym);
1230  break;
1231  case APSIntType::RTR_Above:
1232  return F.getEmptySet();
1233  }
1234 
1235  // Special case for Int == Min. This is always feasible.
1236  llvm::APSInt ComparisonVal = AdjustmentType.convert(Int);
1237  llvm::APSInt Min = AdjustmentType.getMinValue();
1238  if (ComparisonVal == Min)
1239  return getRange(St, Sym);
1240 
1241  llvm::APSInt Max = AdjustmentType.getMaxValue();
1242  llvm::APSInt Lower = ComparisonVal - Adjustment;
1243  llvm::APSInt Upper = Max - Adjustment;
1244 
1245  return getRange(St, Sym).Intersect(getBasicVals(), F, Lower, Upper);
1246 }
1247 
1249 RangeConstraintManager::assumeSymGE(ProgramStateRef St, SymbolRef Sym,
1250  const llvm::APSInt &Int,
1251  const llvm::APSInt &Adjustment) {
1252  RangeSet New = getSymGERange(St, Sym, Int, Adjustment);
1253  return New.isEmpty() ? nullptr : St->set<ConstraintRange>(Sym, New);
1254 }
1255 
1256 RangeSet RangeConstraintManager::getSymLERange(
1257  llvm::function_ref<RangeSet()> RS,
1258  const llvm::APSInt &Int,
1259  const llvm::APSInt &Adjustment) {
1260  // Before we do any real work, see if the value can even show up.
1261  APSIntType AdjustmentType(Adjustment);
1262  switch (AdjustmentType.testInRange(Int, true)) {
1263  case APSIntType::RTR_Below:
1264  return F.getEmptySet();
1266  break;
1267  case APSIntType::RTR_Above:
1268  return RS();
1269  }
1270 
1271  // Special case for Int == Max. This is always feasible.
1272  llvm::APSInt ComparisonVal = AdjustmentType.convert(Int);
1273  llvm::APSInt Max = AdjustmentType.getMaxValue();
1274  if (ComparisonVal == Max)
1275  return RS();
1276 
1277  llvm::APSInt Min = AdjustmentType.getMinValue();
1278  llvm::APSInt Lower = Min - Adjustment;
1279  llvm::APSInt Upper = ComparisonVal - Adjustment;
1280 
1281  return RS().Intersect(getBasicVals(), F, Lower, Upper);
1282 }
1283 
1284 RangeSet RangeConstraintManager::getSymLERange(ProgramStateRef St,
1285  SymbolRef Sym,
1286  const llvm::APSInt &Int,
1287  const llvm::APSInt &Adjustment) {
1288  return getSymLERange([&] { return getRange(St, Sym); }, Int, Adjustment);
1289 }
1290 
1292 RangeConstraintManager::assumeSymLE(ProgramStateRef St, SymbolRef Sym,
1293  const llvm::APSInt &Int,
1294  const llvm::APSInt &Adjustment) {
1295  RangeSet New = getSymLERange(St, Sym, Int, Adjustment);
1296  return New.isEmpty() ? nullptr : St->set<ConstraintRange>(Sym, New);
1297 }
1298 
1299 ProgramStateRef RangeConstraintManager::assumeSymWithinInclusiveRange(
1300  ProgramStateRef State, SymbolRef Sym, const llvm::APSInt &From,
1301  const llvm::APSInt &To, const llvm::APSInt &Adjustment) {
1302  RangeSet New = getSymGERange(State, Sym, From, Adjustment);
1303  if (New.isEmpty())
1304  return nullptr;
1305  RangeSet Out = getSymLERange([&] { return New; }, To, Adjustment);
1306  return Out.isEmpty() ? nullptr : State->set<ConstraintRange>(Sym, Out);
1307 }
1308 
1309 ProgramStateRef RangeConstraintManager::assumeSymOutsideInclusiveRange(
1310  ProgramStateRef State, SymbolRef Sym, const llvm::APSInt &From,
1311  const llvm::APSInt &To, const llvm::APSInt &Adjustment) {
1312  RangeSet RangeLT = getSymLTRange(State, Sym, From, Adjustment);
1313  RangeSet RangeGT = getSymGTRange(State, Sym, To, Adjustment);
1314  RangeSet New(RangeLT.addRange(F, RangeGT));
1315  return New.isEmpty() ? nullptr : State->set<ConstraintRange>(Sym, New);
1316 }
1317 
1318 //===----------------------------------------------------------------------===//
1319 // Pretty-printing.
1320 //===----------------------------------------------------------------------===//
1321 
1322 void RangeConstraintManager::printJson(raw_ostream &Out, ProgramStateRef State,
1323  const char *NL, unsigned int Space,
1324  bool IsDot) const {
1325  ConstraintRangeTy Constraints = State->get<ConstraintRange>();
1326 
1327  Indent(Out, Space, IsDot) << "\"constraints\": ";
1328  if (Constraints.isEmpty()) {
1329  Out << "null," << NL;
1330  return;
1331  }
1332 
1333  ++Space;
1334  Out << '[' << NL;
1335  for (ConstraintRangeTy::iterator I = Constraints.begin();
1336  I != Constraints.end(); ++I) {
1337  Indent(Out, Space, IsDot)
1338  << "{ \"symbol\": \"" << I.getKey() << "\", \"range\": \"";
1339  I.getData().print(Out);
1340  Out << "\" }";
1341 
1342  if (std::next(I) != Constraints.end())
1343  Out << ',';
1344  Out << NL;
1345  }
1346 
1347  --Space;
1348  Indent(Out, Space, IsDot) << "]," << NL;
1349 }
const llvm::APSInt & From() const
A (possibly-)qualified type.
Definition: Type.h:655
Value is less than the minimum representable value.
Definition: APSIntType.h:77
bool isUnsignedIntegerOrEnumerationType() const
Determines whether this is an integer type that is unsigned or an enumeration types whose underlying ...
Definition: Type.cpp:2074
bool isDead(SymbolRef sym)
Returns whether or not a symbol has been confirmed dead.
The base class of the type hierarchy.
Definition: Type.h:1472
std::unique_ptr< ConstraintManager > CreateRangeConstraintManager(ProgramStateManager &statemgr, ExprEngine *exprengine)
A Range represents the closed range [from, to].
llvm::ImmutableMap< SymbolRef, RangeSet > ConstraintRangeTy
RangeSet contains a set of ranges.
bool isEqualityOp() const
Definition: Expr.h:3729
Symbolic value.
Definition: SymExpr.h:29
static Opcode reverseComparisonOp(Opcode Opc)
Definition: Expr.h:3750
LineState State
RangeSet addRange(Factory &F, const RangeSet &RS)
Create a new set with all ranges of this set and RS.
bool Zero(InterpState &S, CodePtr OpPC)
Definition: Interp.h:812
bool isReferenceType() const
Definition: Type.h:6662
bool isIntegralOrEnumerationType() const
Determine whether this type is an integral or enumeration type.
Definition: Type.h:7032
RangeSet Negate(BasicValueFactory &BV, Factory &F) const
static bool isLocType(QualType T)
Definition: SVals.h:329
BinaryOperatorKind
SymExprVisitor - this class implements a simple visitor for SymExpr subclasses.
Definition: SValVisitor.h:75
PrimRangeSet::Factory Factory
static BinaryOperatorKind getOpFromIndex(size_t Index)
Value is representable using this type.
Definition: APSIntType.h:78
A record of the "type" of an APSInt, used for conversions.
Definition: APSIntType.h:19
bool isRelationalOp() const
Definition: Expr.h:3726
RangeTestResultKind testInRange(const llvm::APSInt &Val, bool AllowMixedSign) const LLVM_READONLY
Tests whether a given value is losslessly representable using this type.
Definition: APSIntType.cpp:15
llvm::APSInt getZeroValue() const LLVM_READONLY
Returns an all-zero value for this type.
Definition: APSIntType.h:55
virtual QualType getType() const =0
static Opcode negateComparisonOp(Opcode Opc)
Definition: Expr.h:3737
void print(raw_ostream &os) const
__DEVICE__ int min(int __a, int __b)
SourceLocation End
llvm::APSInt getMinValue() const LLVM_READONLY
Returns the minimum value for this type.
Definition: APSIntType.h:60
#define V(N, I)
Definition: ASTContext.h:2899
const llvm::APSInt * getConcreteValue() const
getConcreteValue - If a symbol is contrained to equal a specific integer constant then this method re...
TriStateKind getCmpOpStateForUnknownX2(BinaryOperatorKind CurrentOP) const
Template implementation for all binary symbolic expressions.
Optional< T > getAs() const
Convert to the specified SVal type, returning None if this SVal is not of the desired type...
Definition: SVals.h:111
bool isComparisonOp() const
Definition: Expr.h:3732
llvm::APSInt getMaxValue() const LLVM_READONLY
Returns the maximum value for this type.
Definition: APSIntType.h:65
const SymSymExpr * getSymSymExpr(const SymExpr *lhs, BinaryOperator::Opcode op, const SymExpr *rhs, QualType t)
constexpr size_t getCmpOpCount() const
llvm::APSInt APSInt
SVal - This represents a symbolic expression, which can be either an L-value or an R-value...
Definition: SVals.h:75
bool isSignedIntegerOrEnumerationType() const
Determines whether this is an integer type that is signed or an enumeration types whose underlying ty...
Definition: Type.cpp:2027
A class responsible for cleaning up unused symbols.
Value is greater than the maximum representable value.
Definition: APSIntType.h:79
RangeTestResultKind
Used to classify whether a value is representable using this type.
Definition: APSIntType.h:76
llvm::APSInt convert(const llvm::APSInt &Value) const LLVM_READONLY
Convert and return a new APSInt with the given value, but this type&#39;s bit width and signedness...
Definition: APSIntType.h:48
Dataflow Directional Tag Classes.
TriStateKind getCmpOpState(BinaryOperatorKind CurrentOP, BinaryOperatorKind QueriedOP) const
const llvm::APSInt & To() const
Represents symbolic expression that isn&#39;t a location.
Definition: SVals.h:349
const llvm::APSInt & getMaxValue() const
Get a maximal value covered by the ranges in the set.
const llvm::APSInt & getMinValue(const llvm::APSInt &v)
APSIntType getAPSIntType(QualType T) const
Returns the type of the APSInt used to store values of the given QualType.
RangeSet Intersect(BasicValueFactory &BV, Factory &F, llvm::APSInt Lower, llvm::APSInt Upper) const
bool isUnsigned() const
Definition: APSIntType.h:31
__DEVICE__ int max(int __a, int __b)
X
Add a minimal nested name specifier fixit hint to allow lookup of a tag name from an outer enclosing ...
Definition: SemaDecl.cpp:15145
void apply(llvm::APSInt &Value) const
Convert a given APSInt, in place, to match this type.
Definition: APSIntType.h:37
const llvm::APSInt & getMaxValue(const llvm::APSInt &v)
raw_ostream & Indent(raw_ostream &Out, const unsigned int Space, bool IsDot)
Definition: JsonSupport.h:20
const llvm::APSInt & getMinValue() const
Get a minimal value covered by the ranges in the set.