clang  15.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/ADT/STLExtras.h"
23 #include "llvm/ADT/StringExtras.h"
24 #include "llvm/ADT/SmallSet.h"
25 #include "llvm/Support/Compiler.h"
26 #include "llvm/Support/raw_ostream.h"
27 #include <algorithm>
28 #include <iterator>
29 
30 using namespace clang;
31 using namespace ento;
32 
33 // This class can be extended with other tables which will help to reason
34 // about ranges more precisely.
36  static_assert(BO_LT < BO_GT && BO_GT < BO_LE && BO_LE < BO_GE &&
37  BO_GE < BO_EQ && BO_EQ < BO_NE,
38  "This class relies on operators order. Rework it otherwise.");
39 
40 public:
41  enum TriStateKind {
42  False = 0,
45  };
46 
47 private:
48  // CmpOpTable holds states which represent the corresponding range for
49  // branching an exploded graph. We can reason about the branch if there is
50  // a previously known fact of the existence of a comparison expression with
51  // operands used in the current expression.
52  // E.g. assuming (x < y) is true that means (x != y) is surely true.
53  // if (x previous_operation y) // < | != | >
54  // if (x operation y) // != | > | <
55  // tristate // True | Unknown | False
56  //
57  // CmpOpTable represents next:
58  // __|< |> |<=|>=|==|!=|UnknownX2|
59  // < |1 |0 |* |0 |0 |* |1 |
60  // > |0 |1 |0 |* |0 |* |1 |
61  // <=|1 |0 |1 |* |1 |* |0 |
62  // >=|0 |1 |* |1 |1 |* |0 |
63  // ==|0 |0 |* |* |1 |0 |1 |
64  // !=|1 |1 |* |* |0 |1 |0 |
65  //
66  // Columns stands for a previous operator.
67  // Rows stands for a current operator.
68  // Each row has exactly two `Unknown` cases.
69  // UnknownX2 means that both `Unknown` previous operators are met in code,
70  // and there is a special column for that, for example:
71  // if (x >= y)
72  // if (x != y)
73  // if (x <= y)
74  // False only
75  static constexpr size_t CmpOpCount = BO_NE - BO_LT + 1;
76  const TriStateKind CmpOpTable[CmpOpCount][CmpOpCount + 1] = {
77  // < > <= >= == != UnknownX2
78  {True, False, Unknown, False, False, Unknown, True}, // <
79  {False, True, False, Unknown, False, Unknown, True}, // >
80  {True, False, True, Unknown, True, Unknown, False}, // <=
81  {False, True, Unknown, True, True, Unknown, False}, // >=
82  {False, False, Unknown, Unknown, True, False, True}, // ==
83  {True, True, Unknown, Unknown, False, True, False}, // !=
84  };
85 
86  static size_t getIndexFromOp(BinaryOperatorKind OP) {
87  return static_cast<size_t>(OP - BO_LT);
88  }
89 
90 public:
91  constexpr size_t getCmpOpCount() const { return CmpOpCount; }
92 
93  static BinaryOperatorKind getOpFromIndex(size_t Index) {
94  return static_cast<BinaryOperatorKind>(Index + BO_LT);
95  }
96 
98  BinaryOperatorKind QueriedOP) const {
99  return CmpOpTable[getIndexFromOp(CurrentOP)][getIndexFromOp(QueriedOP)];
100  }
101 
103  return CmpOpTable[getIndexFromOp(CurrentOP)][CmpOpCount];
104  }
105 };
106 
107 //===----------------------------------------------------------------------===//
108 // RangeSet implementation
109 //===----------------------------------------------------------------------===//
110 
111 RangeSet::ContainerType RangeSet::Factory::EmptySet{};
112 
114  ContainerType Result;
115  Result.reserve(LHS.size() + RHS.size());
116  std::merge(LHS.begin(), LHS.end(), RHS.begin(), RHS.end(),
117  std::back_inserter(Result));
118  return makePersistent(std::move(Result));
119 }
120 
122  ContainerType Result;
123  Result.reserve(Original.size() + 1);
124 
125  const_iterator Lower = llvm::lower_bound(Original, Element);
126  Result.insert(Result.end(), Original.begin(), Lower);
127  Result.push_back(Element);
128  Result.insert(Result.end(), Lower, Original.end());
129 
130  return makePersistent(std::move(Result));
131 }
132 
134  return add(Original, Range(Point));
135 }
136 
138  ContainerType Result = unite(*LHS.Impl, *RHS.Impl);
139  return makePersistent(std::move(Result));
140 }
141 
143  ContainerType Result;
144  Result.push_back(R);
145  Result = unite(*Original.Impl, Result);
146  return makePersistent(std::move(Result));
147 }
148 
150  return unite(Original, Range(ValueFactory.getValue(Point)));
151 }
152 
154  llvm::APSInt To) {
155  return unite(Original,
156  Range(ValueFactory.getValue(From), ValueFactory.getValue(To)));
157 }
158 
159 template <typename T>
160 void swapIterators(T &First, T &FirstEnd, T &Second, T &SecondEnd) {
161  std::swap(First, Second);
162  std::swap(FirstEnd, SecondEnd);
163 }
164 
165 RangeSet::ContainerType RangeSet::Factory::unite(const ContainerType &LHS,
166  const ContainerType &RHS) {
167  if (LHS.empty())
168  return RHS;
169  if (RHS.empty())
170  return LHS;
171 
172  using llvm::APSInt;
173  using iterator = ContainerType::const_iterator;
174 
175  iterator First = LHS.begin();
176  iterator FirstEnd = LHS.end();
177  iterator Second = RHS.begin();
178  iterator SecondEnd = RHS.end();
179  APSIntType Ty = APSIntType(First->From());
180  const APSInt Min = Ty.getMinValue();
181 
182  // Handle a corner case first when both range sets start from MIN.
183  // This helps to avoid complicated conditions below. Specifically, this
184  // particular check for `MIN` is not needed in the loop below every time
185  // when we do `Second->From() - One` operation.
186  if (Min == First->From() && Min == Second->From()) {
187  if (First->To() > Second->To()) {
188  // [ First ]--->
189  // [ Second ]----->
190  // MIN^
191  // The Second range is entirely inside the First one.
192 
193  // Check if Second is the last in its RangeSet.
194  if (++Second == SecondEnd)
195  // [ First ]--[ First + 1 ]--->
196  // [ Second ]--------------------->
197  // MIN^
198  // The Union is equal to First's RangeSet.
199  return LHS;
200  } else {
201  // case 1: [ First ]----->
202  // case 2: [ First ]--->
203  // [ Second ]--->
204  // MIN^
205  // The First range is entirely inside or equal to the Second one.
206 
207  // Check if First is the last in its RangeSet.
208  if (++First == FirstEnd)
209  // [ First ]----------------------->
210  // [ Second ]--[ Second + 1 ]---->
211  // MIN^
212  // The Union is equal to Second's RangeSet.
213  return RHS;
214  }
215  }
216 
217  const APSInt One = Ty.getValue(1);
218  ContainerType Result;
219 
220  // This is called when there are no ranges left in one of the ranges.
221  // Append the rest of the ranges from another range set to the Result
222  // and return with that.
223  const auto AppendTheRest = [&Result](iterator I, iterator E) {
224  Result.append(I, E);
225  return Result;
226  };
227 
228  while (true) {
229  // We want to keep the following invariant at all times:
230  // ---[ First ------>
231  // -----[ Second --->
232  if (First->From() > Second->From())
233  swapIterators(First, FirstEnd, Second, SecondEnd);
234 
235  // The Union definitely starts with First->From().
236  // ----------[ First ------>
237  // ------------[ Second --->
238  // ----------[ Union ------>
239  // UnionStart^
240  const llvm::APSInt &UnionStart = First->From();
241 
242  // Loop where the invariant holds.
243  while (true) {
244  // Skip all enclosed ranges.
245  // ---[ First ]--->
246  // -----[ Second ]--[ Second + 1 ]--[ Second + N ]----->
247  while (First->To() >= Second->To()) {
248  // Check if Second is the last in its RangeSet.
249  if (++Second == SecondEnd) {
250  // Append the Union.
251  // ---[ Union ]--->
252  // -----[ Second ]----->
253  // --------[ First ]--->
254  // UnionEnd^
255  Result.emplace_back(UnionStart, First->To());
256  // ---[ Union ]----------------->
257  // --------------[ First + 1]--->
258  // Append all remaining ranges from the First's RangeSet.
259  return AppendTheRest(++First, FirstEnd);
260  }
261  }
262 
263  // Check if First and Second are disjoint. It means that we find
264  // the end of the Union. Exit the loop and append the Union.
265  // ---[ First ]=------------->
266  // ------------=[ Second ]--->
267  // ----MinusOne^
268  if (First->To() < Second->From() - One)
269  break;
270 
271  // First is entirely inside the Union. Go next.
272  // ---[ Union ----------->
273  // ---- [ First ]-------->
274  // -------[ Second ]----->
275  // Check if First is the last in its RangeSet.
276  if (++First == FirstEnd) {
277  // Append the Union.
278  // ---[ Union ]--->
279  // -----[ First ]------->
280  // --------[ Second ]--->
281  // UnionEnd^
282  Result.emplace_back(UnionStart, Second->To());
283  // ---[ Union ]------------------>
284  // --------------[ Second + 1]--->
285  // Append all remaining ranges from the Second's RangeSet.
286  return AppendTheRest(++Second, SecondEnd);
287  }
288 
289  // We know that we are at one of the two cases:
290  // case 1: --[ First ]--------->
291  // case 2: ----[ First ]------->
292  // --------[ Second ]---------->
293  // In both cases First starts after Second->From().
294  // Make sure that the loop invariant holds.
295  swapIterators(First, FirstEnd, Second, SecondEnd);
296  }
297 
298  // Here First and Second are disjoint.
299  // Append the Union.
300  // ---[ Union ]--------------->
301  // -----------------[ Second ]--->
302  // ------[ First ]--------------->
303  // UnionEnd^
304  Result.emplace_back(UnionStart, First->To());
305 
306  // Check if First is the last in its RangeSet.
307  if (++First == FirstEnd)
308  // ---[ Union ]--------------->
309  // --------------[ Second ]--->
310  // Append all remaining ranges from the Second's RangeSet.
311  return AppendTheRest(Second, SecondEnd);
312  }
313 
314  llvm_unreachable("Normally, we should not reach here");
315 }
316 
318  ContainerType Result;
319  Result.push_back(From);
320  return makePersistent(std::move(Result));
321 }
322 
323 RangeSet RangeSet::Factory::makePersistent(ContainerType &&From) {
324  llvm::FoldingSetNodeID ID;
325  void *InsertPos;
326 
327  From.Profile(ID);
328  ContainerType *Result = Cache.FindNodeOrInsertPos(ID, InsertPos);
329 
330  if (!Result) {
331  // It is cheaper to fully construct the resulting range on stack
332  // and move it to the freshly allocated buffer if we don't have
333  // a set like this already.
334  Result = construct(std::move(From));
335  Cache.InsertNode(Result, InsertPos);
336  }
337 
338  return Result;
339 }
340 
341 RangeSet::ContainerType *RangeSet::Factory::construct(ContainerType &&From) {
342  void *Buffer = Arena.Allocate();
343  return new (Buffer) ContainerType(std::move(From));
344 }
345 
347  assert(!isEmpty());
348  return begin()->From();
349 }
350 
352  assert(!isEmpty());
353  return std::prev(end())->To();
354 }
355 
357  assert(!isEmpty());
358  return begin()->From().isUnsigned();
359 }
360 
362  assert(!isEmpty());
363  return begin()->From().getBitWidth();
364 }
365 
367  assert(!isEmpty());
368  return APSIntType(begin()->From());
369 }
370 
371 bool RangeSet::containsImpl(llvm::APSInt &Point) const {
372  if (isEmpty() || !pin(Point))
373  return false;
374 
375  Range Dummy(Point);
376  const_iterator It = llvm::upper_bound(*this, Dummy);
377  if (It == begin())
378  return false;
379 
380  return std::prev(It)->Includes(Point);
381 }
382 
383 bool RangeSet::pin(llvm::APSInt &Point) const {
384  APSIntType Type(getMinValue());
385  if (Type.testInRange(Point, true) != APSIntType::RTR_Within)
386  return false;
387 
388  Type.apply(Point);
389  return true;
390 }
391 
392 bool RangeSet::pin(llvm::APSInt &Lower, llvm::APSInt &Upper) const {
393  // This function has nine cases, the cartesian product of range-testing
394  // both the upper and lower bounds against the symbol's type.
395  // Each case requires a different pinning operation.
396  // The function returns false if the described range is entirely outside
397  // the range of values for the associated symbol.
398  APSIntType Type(getMinValue());
399  APSIntType::RangeTestResultKind LowerTest = Type.testInRange(Lower, true);
400  APSIntType::RangeTestResultKind UpperTest = Type.testInRange(Upper, true);
401 
402  switch (LowerTest) {
404  switch (UpperTest) {
406  // The entire range is outside the symbol's set of possible values.
407  // If this is a conventionally-ordered range, the state is infeasible.
408  if (Lower <= Upper)
409  return false;
410 
411  // However, if the range wraps around, it spans all possible values.
412  Lower = Type.getMinValue();
413  Upper = Type.getMaxValue();
414  break;
416  // The range starts below what's possible but ends within it. Pin.
417  Lower = Type.getMinValue();
418  Type.apply(Upper);
419  break;
421  // The range spans all possible values for the symbol. Pin.
422  Lower = Type.getMinValue();
423  Upper = Type.getMaxValue();
424  break;
425  }
426  break;
428  switch (UpperTest) {
430  // The range wraps around, but all lower values are not possible.
431  Type.apply(Lower);
432  Upper = Type.getMaxValue();
433  break;
435  // The range may or may not wrap around, but both limits are valid.
436  Type.apply(Lower);
437  Type.apply(Upper);
438  break;
440  // The range starts within what's possible but ends above it. Pin.
441  Type.apply(Lower);
442  Upper = Type.getMaxValue();
443  break;
444  }
445  break;
447  switch (UpperTest) {
449  // The range wraps but is outside the symbol's set of possible values.
450  return false;
452  // The range starts above what's possible but ends within it (wrap).
453  Lower = Type.getMinValue();
454  Type.apply(Upper);
455  break;
457  // The entire range is outside the symbol's set of possible values.
458  // If this is a conventionally-ordered range, the state is infeasible.
459  if (Lower <= Upper)
460  return false;
461 
462  // However, if the range wraps around, it spans all possible values.
463  Lower = Type.getMinValue();
464  Upper = Type.getMaxValue();
465  break;
466  }
467  break;
468  }
469 
470  return true;
471 }
472 
474  llvm::APSInt Upper) {
475  if (What.isEmpty() || !What.pin(Lower, Upper))
476  return getEmptySet();
477 
478  ContainerType DummyContainer;
479 
480  if (Lower <= Upper) {
481  // [Lower, Upper] is a regular range.
482  //
483  // Shortcut: check that there is even a possibility of the intersection
484  // by checking the two following situations:
485  //
486  // <---[ What ]---[------]------>
487  // Lower Upper
488  // -or-
489  // <----[------]----[ What ]---->
490  // Lower Upper
491  if (What.getMaxValue() < Lower || Upper < What.getMinValue())
492  return getEmptySet();
493 
494  DummyContainer.push_back(
495  Range(ValueFactory.getValue(Lower), ValueFactory.getValue(Upper)));
496  } else {
497  // [Lower, Upper] is an inverted range, i.e. [MIN, Upper] U [Lower, MAX]
498  //
499  // Shortcut: check that there is even a possibility of the intersection
500  // by checking the following situation:
501  //
502  // <------]---[ What ]---[------>
503  // Upper Lower
504  if (What.getMaxValue() < Lower && Upper < What.getMinValue())
505  return getEmptySet();
506 
507  DummyContainer.push_back(
508  Range(ValueFactory.getMinValue(Upper), ValueFactory.getValue(Upper)));
509  DummyContainer.push_back(
510  Range(ValueFactory.getValue(Lower), ValueFactory.getMaxValue(Lower)));
511  }
512 
513  return intersect(*What.Impl, DummyContainer);
514 }
515 
516 RangeSet RangeSet::Factory::intersect(const RangeSet::ContainerType &LHS,
517  const RangeSet::ContainerType &RHS) {
518  ContainerType Result;
519  Result.reserve(std::max(LHS.size(), RHS.size()));
520 
521  const_iterator First = LHS.begin(), Second = RHS.begin(),
522  FirstEnd = LHS.end(), SecondEnd = RHS.end();
523 
524  // If we ran out of ranges in one set, but not in the other,
525  // it means that those elements are definitely not in the
526  // intersection.
527  while (First != FirstEnd && Second != SecondEnd) {
528  // We want to keep the following invariant at all times:
529  //
530  // ----[ First ---------------------->
531  // --------[ Second ----------------->
532  if (Second->From() < First->From())
533  swapIterators(First, FirstEnd, Second, SecondEnd);
534 
535  // Loop where the invariant holds:
536  do {
537  // Check for the following situation:
538  //
539  // ----[ First ]--------------------->
540  // ---------------[ Second ]--------->
541  //
542  // which means that...
543  if (Second->From() > First->To()) {
544  // ...First is not in the intersection.
545  //
546  // We should move on to the next range after First and break out of the
547  // loop because the invariant might not be true.
548  ++First;
549  break;
550  }
551 
552  // We have a guaranteed intersection at this point!
553  // And this is the current situation:
554  //
555  // ----[ First ]----------------->
556  // -------[ Second ------------------>
557  //
558  // Additionally, it definitely starts with Second->From().
559  const llvm::APSInt &IntersectionStart = Second->From();
560 
561  // It is important to know which of the two ranges' ends
562  // is greater. That "longer" range might have some other
563  // intersections, while the "shorter" range might not.
564  if (Second->To() > First->To()) {
565  // Here we make a decision to keep First as the "longer"
566  // range.
567  swapIterators(First, FirstEnd, Second, SecondEnd);
568  }
569 
570  // At this point, we have the following situation:
571  //
572  // ---- First ]-------------------->
573  // ---- Second ]--[ Second+1 ---------->
574  //
575  // We don't know the relationship between First->From and
576  // Second->From and we don't know whether Second+1 intersects
577  // with First.
578  //
579  // However, we know that [IntersectionStart, Second->To] is
580  // a part of the intersection...
581  Result.push_back(Range(IntersectionStart, Second->To()));
582  ++Second;
583  // ...and that the invariant will hold for a valid Second+1
584  // because First->From <= Second->To < (Second+1)->From.
585  } while (Second != SecondEnd);
586  }
587 
588  if (Result.empty())
589  return getEmptySet();
590 
591  return makePersistent(std::move(Result));
592 }
593 
595  // Shortcut: let's see if the intersection is even possible.
596  if (LHS.isEmpty() || RHS.isEmpty() || LHS.getMaxValue() < RHS.getMinValue() ||
597  RHS.getMaxValue() < LHS.getMinValue())
598  return getEmptySet();
599 
600  return intersect(*LHS.Impl, *RHS.Impl);
601 }
602 
604  if (LHS.containsImpl(Point))
605  return getRangeSet(ValueFactory.getValue(Point));
606 
607  return getEmptySet();
608 }
609 
611  if (What.isEmpty())
612  return getEmptySet();
613 
614  const llvm::APSInt SampleValue = What.getMinValue();
615  const llvm::APSInt &MIN = ValueFactory.getMinValue(SampleValue);
616  const llvm::APSInt &MAX = ValueFactory.getMaxValue(SampleValue);
617 
618  ContainerType Result;
619  Result.reserve(What.size() + (SampleValue == MIN));
620 
621  // Handle a special case for MIN value.
622  const_iterator It = What.begin();
623  const_iterator End = What.end();
624 
625  const llvm::APSInt &From = It->From();
626  const llvm::APSInt &To = It->To();
627 
628  if (From == MIN) {
629  // If the range [From, To] is [MIN, MAX], then result is also [MIN, MAX].
630  if (To == MAX) {
631  return What;
632  }
633 
634  const_iterator Last = std::prev(End);
635 
636  // Try to find and unite the following ranges:
637  // [MIN, MIN] & [MIN + 1, N] => [MIN, N].
638  if (Last->To() == MAX) {
639  // It means that in the original range we have ranges
640  // [MIN, A], ... , [B, MAX]
641  // And the result should be [MIN, -B], ..., [-A, MAX]
642  Result.emplace_back(MIN, ValueFactory.getValue(-Last->From()));
643  // We already negated Last, so we can skip it.
644  End = Last;
645  } else {
646  // Add a separate range for the lowest value.
647  Result.emplace_back(MIN, MIN);
648  }
649 
650  // Skip adding the second range in case when [From, To] are [MIN, MIN].
651  if (To != MIN) {
652  Result.emplace_back(ValueFactory.getValue(-To), MAX);
653  }
654 
655  // Skip the first range in the loop.
656  ++It;
657  }
658 
659  // Negate all other ranges.
660  for (; It != End; ++It) {
661  // Negate int values.
662  const llvm::APSInt &NewFrom = ValueFactory.getValue(-It->To());
663  const llvm::APSInt &NewTo = ValueFactory.getValue(-It->From());
664 
665  // Add a negated range.
666  Result.emplace_back(NewFrom, NewTo);
667  }
668 
669  llvm::sort(Result);
670  return makePersistent(std::move(Result));
671 }
672 
673 // Convert range set to the given integral type using truncation and promotion.
674 // This works similar to APSIntType::apply function but for the range set.
676  // Set is empty or NOOP (aka cast to the same type).
677  if (What.isEmpty() || What.getAPSIntType() == Ty)
678  return What;
679 
680  const bool IsConversion = What.isUnsigned() != Ty.isUnsigned();
681  const bool IsTruncation = What.getBitWidth() > Ty.getBitWidth();
682  const bool IsPromotion = What.getBitWidth() < Ty.getBitWidth();
683 
684  if (IsTruncation)
685  return makePersistent(truncateTo(What, Ty));
686 
687  // Here we handle 2 cases:
688  // - IsConversion && !IsPromotion.
689  // In this case we handle changing a sign with same bitwidth: char -> uchar,
690  // uint -> int. Here we convert negatives to positives and positives which
691  // is out of range to negatives. We use convertTo function for that.
692  // - IsConversion && IsPromotion && !What.isUnsigned().
693  // In this case we handle changing a sign from signeds to unsigneds with
694  // higher bitwidth: char -> uint, int-> uint64. The point is that we also
695  // need convert negatives to positives and use convertTo function as well.
696  // For example, we don't need such a convertion when converting unsigned to
697  // signed with higher bitwidth, because all the values of unsigned is valid
698  // for the such signed.
699  if (IsConversion && (!IsPromotion || !What.isUnsigned()))
700  return makePersistent(convertTo(What, Ty));
701 
702  assert(IsPromotion && "Only promotion operation from unsigneds left.");
703  return makePersistent(promoteTo(What, Ty));
704 }
705 
707  assert(T->isIntegralOrEnumerationType() && "T shall be an integral type.");
708  return castTo(What, ValueFactory.getAPSIntType(T));
709 }
710 
711 RangeSet::ContainerType RangeSet::Factory::truncateTo(RangeSet What,
712  APSIntType Ty) {
713  using llvm::APInt;
714  using llvm::APSInt;
715  ContainerType Result;
716  ContainerType Dummy;
717  // CastRangeSize is an amount of all possible values of cast type.
718  // Example: `char` has 256 values; `short` has 65536 values.
719  // But in fact we use `amount of values` - 1, because
720  // we can't keep `amount of values of UINT64` inside uint64_t.
721  // E.g. 256 is an amount of all possible values of `char` and we can't keep
722  // it inside `char`.
723  // And it's OK, it's enough to do correct calculations.
724  uint64_t CastRangeSize = APInt::getMaxValue(Ty.getBitWidth()).getZExtValue();
725  for (const Range &R : What) {
726  // Get bounds of the given range.
727  APSInt FromInt = R.From();
728  APSInt ToInt = R.To();
729  // CurrentRangeSize is an amount of all possible values of the current
730  // range minus one.
731  uint64_t CurrentRangeSize = (ToInt - FromInt).getZExtValue();
732  // This is an optimization for a specific case when this Range covers
733  // the whole range of the target type.
734  Dummy.clear();
735  if (CurrentRangeSize >= CastRangeSize) {
736  Dummy.emplace_back(ValueFactory.getMinValue(Ty),
737  ValueFactory.getMaxValue(Ty));
738  Result = std::move(Dummy);
739  break;
740  }
741  // Cast the bounds.
742  Ty.apply(FromInt);
743  Ty.apply(ToInt);
744  const APSInt &PersistentFrom = ValueFactory.getValue(FromInt);
745  const APSInt &PersistentTo = ValueFactory.getValue(ToInt);
746  if (FromInt > ToInt) {
747  Dummy.emplace_back(ValueFactory.getMinValue(Ty), PersistentTo);
748  Dummy.emplace_back(PersistentFrom, ValueFactory.getMaxValue(Ty));
749  } else
750  Dummy.emplace_back(PersistentFrom, PersistentTo);
751  // Every range retrieved after truncation potentialy has garbage values.
752  // So, we have to unite every next range with the previouses.
753  Result = unite(Result, Dummy);
754  }
755 
756  return Result;
757 }
758 
759 // Divide the convertion into two phases (presented as loops here).
760 // First phase(loop) works when casted values go in ascending order.
761 // E.g. char{1,3,5,127} -> uint{1,3,5,127}
762 // Interrupt the first phase and go to second one when casted values start
763 // go in descending order. That means that we crossed over the middle of
764 // the type value set (aka 0 for signeds and MAX/2+1 for unsigneds).
765 // For instance:
766 // 1: uchar{1,3,5,128,255} -> char{1,3,5,-128,-1}
767 // Here we put {1,3,5} to one array and {-128, -1} to another
768 // 2: char{-128,-127,-1,0,1,2} -> uchar{128,129,255,0,1,3}
769 // Here we put {128,129,255} to one array and {0,1,3} to another.
770 // After that we unite both arrays.
771 // NOTE: We don't just concatenate the arrays, because they may have
772 // adjacent ranges, e.g.:
773 // 1: char(-128, 127) -> uchar -> arr1(128, 255), arr2(0, 127) ->
774 // unite -> uchar(0, 255)
775 // 2: uchar(0, 1)U(254, 255) -> char -> arr1(0, 1), arr2(-2, -1) ->
776 // unite -> uchar(-2, 1)
777 RangeSet::ContainerType RangeSet::Factory::convertTo(RangeSet What,
778  APSIntType Ty) {
779  using llvm::APInt;
780  using llvm::APSInt;
781  using Bounds = std::pair<const APSInt &, const APSInt &>;
782  ContainerType AscendArray;
783  ContainerType DescendArray;
784  auto CastRange = [Ty, &VF = ValueFactory](const Range &R) -> Bounds {
785  // Get bounds of the given range.
786  APSInt FromInt = R.From();
787  APSInt ToInt = R.To();
788  // Cast the bounds.
789  Ty.apply(FromInt);
790  Ty.apply(ToInt);
791  return {VF.getValue(FromInt), VF.getValue(ToInt)};
792  };
793  // Phase 1. Fill the first array.
794  APSInt LastConvertedInt = Ty.getMinValue();
795  const auto *It = What.begin();
796  const auto *E = What.end();
797  while (It != E) {
798  Bounds NewBounds = CastRange(*(It++));
799  // If values stop going acsending order, go to the second phase(loop).
800  if (NewBounds.first < LastConvertedInt) {
801  DescendArray.emplace_back(NewBounds.first, NewBounds.second);
802  break;
803  }
804  // If the range contains a midpoint, then split the range.
805  // E.g. char(-5, 5) -> uchar(251, 5)
806  // Here we shall add a range (251, 255) to the first array and (0, 5) to the
807  // second one.
808  if (NewBounds.first > NewBounds.second) {
809  DescendArray.emplace_back(ValueFactory.getMinValue(Ty), NewBounds.second);
810  AscendArray.emplace_back(NewBounds.first, ValueFactory.getMaxValue(Ty));
811  } else
812  // Values are going acsending order.
813  AscendArray.emplace_back(NewBounds.first, NewBounds.second);
814  LastConvertedInt = NewBounds.first;
815  }
816  // Phase 2. Fill the second array.
817  while (It != E) {
818  Bounds NewBounds = CastRange(*(It++));
819  DescendArray.emplace_back(NewBounds.first, NewBounds.second);
820  }
821  // Unite both arrays.
822  return unite(AscendArray, DescendArray);
823 }
824 
825 /// Promotion from unsigneds to signeds/unsigneds left.
826 RangeSet::ContainerType RangeSet::Factory::promoteTo(RangeSet What,
827  APSIntType Ty) {
828  ContainerType Result;
829  // We definitely know the size of the result set.
830  Result.reserve(What.size());
831 
832  // Each unsigned value fits every larger type without any changes,
833  // whether the larger type is signed or unsigned. So just promote and push
834  // back each range one by one.
835  for (const Range &R : What) {
836  // Get bounds of the given range.
837  llvm::APSInt FromInt = R.From();
838  llvm::APSInt ToInt = R.To();
839  // Cast the bounds.
840  Ty.apply(FromInt);
841  Ty.apply(ToInt);
842  Result.emplace_back(ValueFactory.getValue(FromInt),
843  ValueFactory.getValue(ToInt));
844  }
845  return Result;
846 }
847 
849  const llvm::APSInt &Point) {
850  if (!From.contains(Point))
851  return From;
852 
853  llvm::APSInt Upper = Point;
854  llvm::APSInt Lower = Point;
855 
856  ++Upper;
857  --Lower;
858 
859  // Notice that the lower bound is greater than the upper bound.
860  return intersect(From, Upper, Lower);
861 }
862 
863 LLVM_DUMP_METHOD void Range::dump(raw_ostream &OS) const {
864  OS << '[' << toString(From(), 10) << ", " << toString(To(), 10) << ']';
865 }
866 LLVM_DUMP_METHOD void Range::dump() const { dump(llvm::errs()); }
867 
868 LLVM_DUMP_METHOD void RangeSet::dump(raw_ostream &OS) const {
869  OS << "{ ";
870  llvm::interleaveComma(*this, OS, [&OS](const Range &R) { R.dump(OS); });
871  OS << " }";
872 }
873 LLVM_DUMP_METHOD void RangeSet::dump() const { dump(llvm::errs()); }
874 
876 
877 namespace {
878 class EquivalenceClass;
879 } // end anonymous namespace
880 
881 REGISTER_MAP_WITH_PROGRAMSTATE(ClassMap, SymbolRef, EquivalenceClass)
882 REGISTER_MAP_WITH_PROGRAMSTATE(ClassMembers, EquivalenceClass, SymbolSet)
883 REGISTER_MAP_WITH_PROGRAMSTATE(ConstraintRange, EquivalenceClass, RangeSet)
884 
885 REGISTER_SET_FACTORY_WITH_PROGRAMSTATE(ClassSet, EquivalenceClass)
886 REGISTER_MAP_WITH_PROGRAMSTATE(DisequalityMap, EquivalenceClass, ClassSet)
887 
888 namespace {
889 /// This class encapsulates a set of symbols equal to each other.
890 ///
891 /// The main idea of the approach requiring such classes is in narrowing
892 /// and sharing constraints between symbols within the class. Also we can
893 /// conclude that there is no practical need in storing constraints for
894 /// every member of the class separately.
895 ///
896 /// Main terminology:
897 ///
898 /// * "Equivalence class" is an object of this class, which can be efficiently
899 /// compared to other classes. It represents the whole class without
900 /// storing the actual in it. The members of the class however can be
901 /// retrieved from the state.
902 ///
903 /// * "Class members" are the symbols corresponding to the class. This means
904 /// that A == B for every member symbols A and B from the class. Members of
905 /// each class are stored in the state.
906 ///
907 /// * "Trivial class" is a class that has and ever had only one same symbol.
908 ///
909 /// * "Merge operation" merges two classes into one. It is the main operation
910 /// to produce non-trivial classes.
911 /// If, at some point, we can assume that two symbols from two distinct
912 /// classes are equal, we can merge these classes.
913 class EquivalenceClass : public llvm::FoldingSetNode {
914 public:
915  /// Find equivalence class for the given symbol in the given state.
916  LLVM_NODISCARD static inline EquivalenceClass find(ProgramStateRef State,
917  SymbolRef Sym);
918 
919  /// Merge classes for the given symbols and return a new state.
920  LLVM_NODISCARD static inline ProgramStateRef merge(RangeSet::Factory &F,
922  SymbolRef First,
923  SymbolRef Second);
924  // Merge this class with the given class and return a new state.
925  LLVM_NODISCARD inline ProgramStateRef
926  merge(RangeSet::Factory &F, ProgramStateRef State, EquivalenceClass Other);
927 
928  /// Return a set of class members for the given state.
929  LLVM_NODISCARD inline SymbolSet getClassMembers(ProgramStateRef State) const;
930 
931  /// Return true if the current class is trivial in the given state.
932  /// A class is trivial if and only if there is not any member relations stored
933  /// to it in State/ClassMembers.
934  /// An equivalence class with one member might seem as it does not hold any
935  /// meaningful information, i.e. that is a tautology. However, during the
936  /// removal of dead symbols we do not remove classes with one member for
937  /// resource and performance reasons. Consequently, a class with one member is
938  /// not necessarily trivial. It could happen that we have a class with two
939  /// members and then during the removal of dead symbols we remove one of its
940  /// members. In this case, the class is still non-trivial (it still has the
941  /// mappings in ClassMembers), even though it has only one member.
942  LLVM_NODISCARD inline bool isTrivial(ProgramStateRef State) const;
943 
944  /// Return true if the current class is trivial and its only member is dead.
945  LLVM_NODISCARD inline bool isTriviallyDead(ProgramStateRef State,
946  SymbolReaper &Reaper) const;
947 
948  LLVM_NODISCARD static inline ProgramStateRef
949  markDisequal(RangeSet::Factory &F, ProgramStateRef State, SymbolRef First,
950  SymbolRef Second);
951  LLVM_NODISCARD static inline ProgramStateRef
952  markDisequal(RangeSet::Factory &F, ProgramStateRef State,
953  EquivalenceClass First, EquivalenceClass Second);
954  LLVM_NODISCARD inline ProgramStateRef
955  markDisequal(RangeSet::Factory &F, ProgramStateRef State,
956  EquivalenceClass Other) const;
957  LLVM_NODISCARD static inline ClassSet
958  getDisequalClasses(ProgramStateRef State, SymbolRef Sym);
959  LLVM_NODISCARD inline ClassSet
960  getDisequalClasses(ProgramStateRef State) const;
961  LLVM_NODISCARD inline ClassSet
962  getDisequalClasses(DisequalityMapTy Map, ClassSet::Factory &Factory) const;
963 
964  LLVM_NODISCARD static inline Optional<bool> areEqual(ProgramStateRef State,
965  EquivalenceClass First,
966  EquivalenceClass Second);
967  LLVM_NODISCARD static inline Optional<bool>
968  areEqual(ProgramStateRef State, SymbolRef First, SymbolRef Second);
969 
970  /// Remove one member from the class.
971  LLVM_NODISCARD ProgramStateRef removeMember(ProgramStateRef State,
972  const SymbolRef Old);
973 
974  /// Iterate over all symbols and try to simplify them.
975  LLVM_NODISCARD static inline ProgramStateRef simplify(SValBuilder &SVB,
978  EquivalenceClass Class);
979 
980  void dumpToStream(ProgramStateRef State, raw_ostream &os) const;
981  LLVM_DUMP_METHOD void dump(ProgramStateRef State) const {
982  dumpToStream(State, llvm::errs());
983  }
984 
985  /// Check equivalence data for consistency.
986  LLVM_NODISCARD LLVM_ATTRIBUTE_UNUSED static bool
987  isClassDataConsistent(ProgramStateRef State);
988 
989  LLVM_NODISCARD QualType getType() const {
990  return getRepresentativeSymbol()->getType();
991  }
992 
993  EquivalenceClass() = delete;
994  EquivalenceClass(const EquivalenceClass &) = default;
995  EquivalenceClass &operator=(const EquivalenceClass &) = delete;
996  EquivalenceClass(EquivalenceClass &&) = default;
997  EquivalenceClass &operator=(EquivalenceClass &&) = delete;
998 
999  bool operator==(const EquivalenceClass &Other) const {
1000  return ID == Other.ID;
1001  }
1002  bool operator<(const EquivalenceClass &Other) const { return ID < Other.ID; }
1003  bool operator!=(const EquivalenceClass &Other) const {
1004  return !operator==(Other);
1005  }
1006 
1007  static void Profile(llvm::FoldingSetNodeID &ID, uintptr_t CID) {
1008  ID.AddInteger(CID);
1009  }
1010 
1011  void Profile(llvm::FoldingSetNodeID &ID) const { Profile(ID, this->ID); }
1012 
1013 private:
1014  /* implicit */ EquivalenceClass(SymbolRef Sym)
1015  : ID(reinterpret_cast<uintptr_t>(Sym)) {}
1016 
1017  /// This function is intended to be used ONLY within the class.
1018  /// The fact that ID is a pointer to a symbol is an implementation detail
1019  /// and should stay that way.
1020  /// In the current implementation, we use it to retrieve the only member
1021  /// of the trivial class.
1022  SymbolRef getRepresentativeSymbol() const {
1023  return reinterpret_cast<SymbolRef>(ID);
1024  }
1025  static inline SymbolSet::Factory &getMembersFactory(ProgramStateRef State);
1026 
1028  SymbolSet Members, EquivalenceClass Other,
1029  SymbolSet OtherMembers);
1030 
1031  static inline bool
1032  addToDisequalityInfo(DisequalityMapTy &Info, ConstraintRangeTy &Constraints,
1034  EquivalenceClass First, EquivalenceClass Second);
1035 
1036  /// This is a unique identifier of the class.
1037  uintptr_t ID;
1038 };
1039 
1040 //===----------------------------------------------------------------------===//
1041 // Constraint functions
1042 //===----------------------------------------------------------------------===//
1043 
1044 LLVM_NODISCARD LLVM_ATTRIBUTE_UNUSED bool
1045 areFeasible(ConstraintRangeTy Constraints) {
1046  return llvm::none_of(
1047  Constraints,
1048  [](const std::pair<EquivalenceClass, RangeSet> &ClassConstraint) {
1049  return ClassConstraint.second.isEmpty();
1050  });
1051 }
1052 
1053 LLVM_NODISCARD inline const RangeSet *getConstraint(ProgramStateRef State,
1054  EquivalenceClass Class) {
1055  return State->get<ConstraintRange>(Class);
1056 }
1057 
1058 LLVM_NODISCARD inline const RangeSet *getConstraint(ProgramStateRef State,
1059  SymbolRef Sym) {
1060  return getConstraint(State, EquivalenceClass::find(State, Sym));
1061 }
1062 
1063 LLVM_NODISCARD ProgramStateRef setConstraint(ProgramStateRef State,
1064  EquivalenceClass Class,
1065  RangeSet Constraint) {
1066  return State->set<ConstraintRange>(Class, Constraint);
1067 }
1068 
1069 LLVM_NODISCARD ProgramStateRef setConstraints(ProgramStateRef State,
1070  ConstraintRangeTy Constraints) {
1071  return State->set<ConstraintRange>(Constraints);
1072 }
1073 
1074 //===----------------------------------------------------------------------===//
1075 // Equality/diseqiality abstraction
1076 //===----------------------------------------------------------------------===//
1077 
1078 /// A small helper function for detecting symbolic (dis)equality.
1079 ///
1080 /// Equality check can have different forms (like a == b or a - b) and this
1081 /// class encapsulates those away if the only thing the user wants to check -
1082 /// whether it's equality/diseqiality or not.
1083 ///
1084 /// \returns true if assuming this Sym to be true means equality of operands
1085 /// false if it means disequality of operands
1086 /// None otherwise
1087 Optional<bool> meansEquality(const SymSymExpr *Sym) {
1088  switch (Sym->getOpcode()) {
1089  case BO_Sub:
1090  // This case is: A - B != 0 -> disequality check.
1091  return false;
1092  case BO_EQ:
1093  // This case is: A == B != 0 -> equality check.
1094  return true;
1095  case BO_NE:
1096  // This case is: A != B != 0 -> diseqiality check.
1097  return false;
1098  default:
1099  return llvm::None;
1100  }
1101 }
1102 
1103 //===----------------------------------------------------------------------===//
1104 // Intersection functions
1105 //===----------------------------------------------------------------------===//
1106 
1107 template <class SecondTy, class... RestTy>
1108 LLVM_NODISCARD inline RangeSet intersect(RangeSet::Factory &F, RangeSet Head,
1109  SecondTy Second, RestTy... Tail);
1110 
1111 template <class... RangeTy> struct IntersectionTraits;
1112 
1113 template <class... TailTy> struct IntersectionTraits<RangeSet, TailTy...> {
1114  // Found RangeSet, no need to check any further
1115  using Type = RangeSet;
1116 };
1117 
1118 template <> struct IntersectionTraits<> {
1119  // We ran out of types, and we didn't find any RangeSet, so the result should
1120  // be optional.
1121  using Type = Optional<RangeSet>;
1122 };
1123 
1124 template <class OptionalOrPointer, class... TailTy>
1125 struct IntersectionTraits<OptionalOrPointer, TailTy...> {
1126  // If current type is Optional or a raw pointer, we should keep looking.
1127  using Type = typename IntersectionTraits<TailTy...>::Type;
1128 };
1129 
1130 template <class EndTy>
1131 LLVM_NODISCARD inline EndTy intersect(RangeSet::Factory &F, EndTy End) {
1132  // If the list contains only RangeSet or Optional<RangeSet>, simply return
1133  // that range set.
1134  return End;
1135 }
1136 
1137 LLVM_NODISCARD LLVM_ATTRIBUTE_UNUSED inline Optional<RangeSet>
1138 intersect(RangeSet::Factory &F, const RangeSet *End) {
1139  // This is an extraneous conversion from a raw pointer into Optional<RangeSet>
1140  if (End) {
1141  return *End;
1142  }
1143  return llvm::None;
1144 }
1145 
1146 template <class... RestTy>
1147 LLVM_NODISCARD inline RangeSet intersect(RangeSet::Factory &F, RangeSet Head,
1148  RangeSet Second, RestTy... Tail) {
1149  // Here we call either the <RangeSet,RangeSet,...> or <RangeSet,...> version
1150  // of the function and can be sure that the result is RangeSet.
1151  return intersect(F, F.intersect(Head, Second), Tail...);
1152 }
1153 
1154 template <class SecondTy, class... RestTy>
1155 LLVM_NODISCARD inline RangeSet intersect(RangeSet::Factory &F, RangeSet Head,
1156  SecondTy Second, RestTy... Tail) {
1157  if (Second) {
1158  // Here we call the <RangeSet,RangeSet,...> version of the function...
1159  return intersect(F, Head, *Second, Tail...);
1160  }
1161  // ...and here it is either <RangeSet,RangeSet,...> or <RangeSet,...>, which
1162  // means that the result is definitely RangeSet.
1163  return intersect(F, Head, Tail...);
1164 }
1165 
1166 /// Main generic intersect function.
1167 /// It intersects all of the given range sets. If some of the given arguments
1168 /// don't hold a range set (nullptr or llvm::None), the function will skip them.
1169 ///
1170 /// Available representations for the arguments are:
1171 /// * RangeSet
1172 /// * Optional<RangeSet>
1173 /// * RangeSet *
1174 /// Pointer to a RangeSet is automatically assumed to be nullable and will get
1175 /// checked as well as the optional version. If this behaviour is undesired,
1176 /// please dereference the pointer in the call.
1177 ///
1178 /// Return type depends on the arguments' types. If we can be sure in compile
1179 /// time that there will be a range set as a result, the returning type is
1180 /// simply RangeSet, in other cases we have to back off to Optional<RangeSet>.
1181 ///
1182 /// Please, prefer optional range sets to raw pointers. If the last argument is
1183 /// a raw pointer and all previous arguments are None, it will cost one
1184 /// additional check to convert RangeSet * into Optional<RangeSet>.
1185 template <class HeadTy, class SecondTy, class... RestTy>
1186 LLVM_NODISCARD inline
1187  typename IntersectionTraits<HeadTy, SecondTy, RestTy...>::Type
1188  intersect(RangeSet::Factory &F, HeadTy Head, SecondTy Second,
1189  RestTy... Tail) {
1190  if (Head) {
1191  return intersect(F, *Head, Second, Tail...);
1192  }
1193  return intersect(F, Second, Tail...);
1194 }
1195 
1196 //===----------------------------------------------------------------------===//
1197 // Symbolic reasoning logic
1198 //===----------------------------------------------------------------------===//
1199 
1200 /// A little component aggregating all of the reasoning we have about
1201 /// the ranges of symbolic expressions.
1202 ///
1203 /// Even when we don't know the exact values of the operands, we still
1204 /// can get a pretty good estimate of the result's range.
1205 class SymbolicRangeInferrer
1206  : public SymExprVisitor<SymbolicRangeInferrer, RangeSet> {
1207 public:
1208  template <class SourceType>
1209  static RangeSet inferRange(RangeSet::Factory &F, ProgramStateRef State,
1210  SourceType Origin) {
1211  SymbolicRangeInferrer Inferrer(F, State);
1212  return Inferrer.infer(Origin);
1213  }
1214 
1215  RangeSet VisitSymExpr(SymbolRef Sym) {
1216  // If we got to this function, the actual type of the symbolic
1217  // expression is not supported for advanced inference.
1218  // In this case, we simply backoff to the default "let's simply
1219  // infer the range from the expression's type".
1220  return infer(Sym->getType());
1221  }
1222 
1223  RangeSet VisitSymIntExpr(const SymIntExpr *Sym) {
1224  return VisitBinaryOperator(Sym);
1225  }
1226 
1227  RangeSet VisitIntSymExpr(const IntSymExpr *Sym) {
1228  return VisitBinaryOperator(Sym);
1229  }
1230 
1231  RangeSet VisitSymSymExpr(const SymSymExpr *Sym) {
1232  return intersect(
1233  RangeFactory,
1234  // If Sym is (dis)equality, we might have some information
1235  // on that in our equality classes data structure.
1236  getRangeForEqualities(Sym),
1237  // And we should always check what we can get from the operands.
1238  VisitBinaryOperator(Sym));
1239  }
1240 
1241 private:
1242  SymbolicRangeInferrer(RangeSet::Factory &F, ProgramStateRef S)
1243  : ValueFactory(F.getValueFactory()), RangeFactory(F), State(S) {}
1244 
1245  /// Infer range information from the given integer constant.
1246  ///
1247  /// It's not a real "inference", but is here for operating with
1248  /// sub-expressions in a more polymorphic manner.
1249  RangeSet inferAs(const llvm::APSInt &Val, QualType) {
1250  return {RangeFactory, Val};
1251  }
1252 
1253  /// Infer range information from symbol in the context of the given type.
1254  RangeSet inferAs(SymbolRef Sym, QualType DestType) {
1255  QualType ActualType = Sym->getType();
1256  // Check that we can reason about the symbol at all.
1257  if (ActualType->isIntegralOrEnumerationType() ||
1258  Loc::isLocType(ActualType)) {
1259  return infer(Sym);
1260  }
1261  // Otherwise, let's simply infer from the destination type.
1262  // We couldn't figure out nothing else about that expression.
1263  return infer(DestType);
1264  }
1265 
1266  RangeSet infer(SymbolRef Sym) {
1267  return intersect(
1268  RangeFactory,
1269  // Of course, we should take the constraint directly associated with
1270  // this symbol into consideration.
1271  getConstraint(State, Sym),
1272  // If Sym is a difference of symbols A - B, then maybe we have range
1273  // set stored for B - A.
1274  //
1275  // If we have range set stored for both A - B and B - A then
1276  // calculate the effective range set by intersecting the range set
1277  // for A - B and the negated range set of B - A.
1278  getRangeForNegatedSub(Sym),
1279  // If Sym is a comparison expression (except <=>),
1280  // find any other comparisons with the same operands.
1281  // See function description.
1282  getRangeForComparisonSymbol(Sym),
1283  // Apart from the Sym itself, we can infer quite a lot if we look
1284  // into subexpressions of Sym.
1285  Visit(Sym));
1286  }
1287 
1288  RangeSet infer(EquivalenceClass Class) {
1289  if (const RangeSet *AssociatedConstraint = getConstraint(State, Class))
1290  return *AssociatedConstraint;
1291 
1292  return infer(Class.getType());
1293  }
1294 
1295  /// Infer range information solely from the type.
1296  RangeSet infer(QualType T) {
1297  // Lazily generate a new RangeSet representing all possible values for the
1298  // given symbol type.
1299  RangeSet Result(RangeFactory, ValueFactory.getMinValue(T),
1300  ValueFactory.getMaxValue(T));
1301 
1302  // References are known to be non-zero.
1303  if (T->isReferenceType())
1304  return assumeNonZero(Result, T);
1305 
1306  return Result;
1307  }
1308 
1309  template <class BinarySymExprTy>
1310  RangeSet VisitBinaryOperator(const BinarySymExprTy *Sym) {
1311  // TODO #1: VisitBinaryOperator implementation might not make a good
1312  // use of the inferred ranges. In this case, we might be calculating
1313  // everything for nothing. This being said, we should introduce some
1314  // sort of laziness mechanism here.
1315  //
1316  // TODO #2: We didn't go into the nested expressions before, so it
1317  // might cause us spending much more time doing the inference.
1318  // This can be a problem for deeply nested expressions that are
1319  // involved in conditions and get tested continuously. We definitely
1320  // need to address this issue and introduce some sort of caching
1321  // in here.
1322  QualType ResultType = Sym->getType();
1323  return VisitBinaryOperator(inferAs(Sym->getLHS(), ResultType),
1324  Sym->getOpcode(),
1325  inferAs(Sym->getRHS(), ResultType), ResultType);
1326  }
1327 
1328  RangeSet VisitBinaryOperator(RangeSet LHS, BinaryOperator::Opcode Op,
1329  RangeSet RHS, QualType T) {
1330  switch (Op) {
1331  case BO_Or:
1332  return VisitBinaryOperator<BO_Or>(LHS, RHS, T);
1333  case BO_And:
1334  return VisitBinaryOperator<BO_And>(LHS, RHS, T);
1335  case BO_Rem:
1336  return VisitBinaryOperator<BO_Rem>(LHS, RHS, T);
1337  default:
1338  return infer(T);
1339  }
1340  }
1341 
1342  //===----------------------------------------------------------------------===//
1343  // Ranges and operators
1344  //===----------------------------------------------------------------------===//
1345 
1346  /// Return a rough approximation of the given range set.
1347  ///
1348  /// For the range set:
1349  /// { [x_0, y_0], [x_1, y_1], ... , [x_N, y_N] }
1350  /// it will return the range [x_0, y_N].
1351  static Range fillGaps(RangeSet Origin) {
1352  assert(!Origin.isEmpty());
1353  return {Origin.getMinValue(), Origin.getMaxValue()};
1354  }
1355 
1356  /// Try to convert given range into the given type.
1357  ///
1358  /// It will return llvm::None only when the trivial conversion is possible.
1359  llvm::Optional<Range> convert(const Range &Origin, APSIntType To) {
1360  if (To.testInRange(Origin.From(), false) != APSIntType::RTR_Within ||
1361  To.testInRange(Origin.To(), false) != APSIntType::RTR_Within) {
1362  return llvm::None;
1363  }
1364  return Range(ValueFactory.Convert(To, Origin.From()),
1365  ValueFactory.Convert(To, Origin.To()));
1366  }
1367 
1368  template <BinaryOperator::Opcode Op>
1369  RangeSet VisitBinaryOperator(RangeSet LHS, RangeSet RHS, QualType T) {
1370  // We should propagate information about unfeasbility of one of the
1371  // operands to the resulting range.
1372  if (LHS.isEmpty() || RHS.isEmpty()) {
1373  return RangeFactory.getEmptySet();
1374  }
1375 
1376  Range CoarseLHS = fillGaps(LHS);
1377  Range CoarseRHS = fillGaps(RHS);
1378 
1379  APSIntType ResultType = ValueFactory.getAPSIntType(T);
1380 
1381  // We need to convert ranges to the resulting type, so we can compare values
1382  // and combine them in a meaningful (in terms of the given operation) way.
1383  auto ConvertedCoarseLHS = convert(CoarseLHS, ResultType);
1384  auto ConvertedCoarseRHS = convert(CoarseRHS, ResultType);
1385 
1386  // It is hard to reason about ranges when conversion changes
1387  // borders of the ranges.
1388  if (!ConvertedCoarseLHS || !ConvertedCoarseRHS) {
1389  return infer(T);
1390  }
1391 
1392  return VisitBinaryOperator<Op>(*ConvertedCoarseLHS, *ConvertedCoarseRHS, T);
1393  }
1394 
1395  template <BinaryOperator::Opcode Op>
1396  RangeSet VisitBinaryOperator(Range LHS, Range RHS, QualType T) {
1397  return infer(T);
1398  }
1399 
1400  /// Return a symmetrical range for the given range and type.
1401  ///
1402  /// If T is signed, return the smallest range [-x..x] that covers the original
1403  /// range, or [-min(T), max(T)] if the aforementioned symmetric range doesn't
1404  /// exist due to original range covering min(T)).
1405  ///
1406  /// If T is unsigned, return the smallest range [0..x] that covers the
1407  /// original range.
1408  Range getSymmetricalRange(Range Origin, QualType T) {
1409  APSIntType RangeType = ValueFactory.getAPSIntType(T);
1410 
1411  if (RangeType.isUnsigned()) {
1412  return Range(ValueFactory.getMinValue(RangeType), Origin.To());
1413  }
1414 
1415  if (Origin.From().isMinSignedValue()) {
1416  // If mini is a minimal signed value, absolute value of it is greater
1417  // than the maximal signed value. In order to avoid these
1418  // complications, we simply return the whole range.
1419  return {ValueFactory.getMinValue(RangeType),
1420  ValueFactory.getMaxValue(RangeType)};
1421  }
1422 
1423  // At this point, we are sure that the type is signed and we can safely
1424  // use unary - operator.
1425  //
1426  // While calculating absolute maximum, we can use the following formula
1427  // because of these reasons:
1428  // * If From >= 0 then To >= From and To >= -From.
1429  // AbsMax == To == max(To, -From)
1430  // * If To <= 0 then -From >= -To and -From >= From.
1431  // AbsMax == -From == max(-From, To)
1432  // * Otherwise, From <= 0, To >= 0, and
1433  // AbsMax == max(abs(From), abs(To))
1434  llvm::APSInt AbsMax = std::max(-Origin.From(), Origin.To());
1435 
1436  // Intersection is guaranteed to be non-empty.
1437  return {ValueFactory.getValue(-AbsMax), ValueFactory.getValue(AbsMax)};
1438  }
1439 
1440  /// Return a range set subtracting zero from \p Domain.
1441  RangeSet assumeNonZero(RangeSet Domain, QualType T) {
1442  APSIntType IntType = ValueFactory.getAPSIntType(T);
1443  return RangeFactory.deletePoint(Domain, IntType.getZeroValue());
1444  }
1445 
1446  // FIXME: Once SValBuilder supports unary minus, we should use SValBuilder to
1447  // obtain the negated symbolic expression instead of constructing the
1448  // symbol manually. This will allow us to support finding ranges of not
1449  // only negated SymSymExpr-type expressions, but also of other, simpler
1450  // expressions which we currently do not know how to negate.
1451  Optional<RangeSet> getRangeForNegatedSub(SymbolRef Sym) {
1452  if (const SymSymExpr *SSE = dyn_cast<SymSymExpr>(Sym)) {
1453  if (SSE->getOpcode() == BO_Sub) {
1454  QualType T = Sym->getType();
1455 
1456  // Do not negate unsigned ranges
1459  return llvm::None;
1460 
1461  SymbolManager &SymMgr = State->getSymbolManager();
1462  SymbolRef NegatedSym =
1463  SymMgr.getSymSymExpr(SSE->getRHS(), BO_Sub, SSE->getLHS(), T);
1464 
1465  if (const RangeSet *NegatedRange = getConstraint(State, NegatedSym)) {
1466  return RangeFactory.negate(*NegatedRange);
1467  }
1468  }
1469  }
1470  return llvm::None;
1471  }
1472 
1473  // Returns ranges only for binary comparison operators (except <=>)
1474  // when left and right operands are symbolic values.
1475  // Finds any other comparisons with the same operands.
1476  // Then do logical calculations and refuse impossible branches.
1477  // E.g. (x < y) and (x > y) at the same time are impossible.
1478  // E.g. (x >= y) and (x != y) at the same time makes (x > y) true only.
1479  // E.g. (x == y) and (y == x) are just reversed but the same.
1480  // It covers all possible combinations (see CmpOpTable description).
1481  // Note that `x` and `y` can also stand for subexpressions,
1482  // not only for actual symbols.
1483  Optional<RangeSet> getRangeForComparisonSymbol(SymbolRef Sym) {
1484  const auto *SSE = dyn_cast<SymSymExpr>(Sym);
1485  if (!SSE)
1486  return llvm::None;
1487 
1488  const BinaryOperatorKind CurrentOP = SSE->getOpcode();
1489 
1490  // We currently do not support <=> (C++20).
1491  if (!BinaryOperator::isComparisonOp(CurrentOP) || (CurrentOP == BO_Cmp))
1492  return llvm::None;
1493 
1494  static const OperatorRelationsTable CmpOpTable{};
1495 
1496  const SymExpr *LHS = SSE->getLHS();
1497  const SymExpr *RHS = SSE->getRHS();
1498  QualType T = SSE->getType();
1499 
1500  SymbolManager &SymMgr = State->getSymbolManager();
1501 
1502  // We use this variable to store the last queried operator (`QueriedOP`)
1503  // for which the `getCmpOpState` returned with `Unknown`. If there are two
1504  // different OPs that returned `Unknown` then we have to query the special
1505  // `UnknownX2` column. We assume that `getCmpOpState(CurrentOP, CurrentOP)`
1506  // never returns `Unknown`, so `CurrentOP` is a good initial value.
1507  BinaryOperatorKind LastQueriedOpToUnknown = CurrentOP;
1508 
1509  // Loop goes through all of the columns exept the last one ('UnknownX2').
1510  // We treat `UnknownX2` column separately at the end of the loop body.
1511  for (size_t i = 0; i < CmpOpTable.getCmpOpCount(); ++i) {
1512 
1513  // Let's find an expression e.g. (x < y).
1515  const SymSymExpr *SymSym = SymMgr.getSymSymExpr(LHS, QueriedOP, RHS, T);
1516  const RangeSet *QueriedRangeSet = getConstraint(State, SymSym);
1517 
1518  // If ranges were not previously found,
1519  // try to find a reversed expression (y > x).
1520  if (!QueriedRangeSet) {
1521  const BinaryOperatorKind ROP =
1523  SymSym = SymMgr.getSymSymExpr(RHS, ROP, LHS, T);
1524  QueriedRangeSet = getConstraint(State, SymSym);
1525  }
1526 
1527  if (!QueriedRangeSet || QueriedRangeSet->isEmpty())
1528  continue;
1529 
1530  const llvm::APSInt *ConcreteValue = QueriedRangeSet->getConcreteValue();
1531  const bool isInFalseBranch =
1532  ConcreteValue ? (*ConcreteValue == 0) : false;
1533 
1534  // If it is a false branch, we shall be guided by opposite operator,
1535  // because the table is made assuming we are in the true branch.
1536  // E.g. when (x <= y) is false, then (x > y) is true.
1537  if (isInFalseBranch)
1538  QueriedOP = BinaryOperator::negateComparisonOp(QueriedOP);
1539 
1541  CmpOpTable.getCmpOpState(CurrentOP, QueriedOP);
1542 
1543  if (BranchState == OperatorRelationsTable::Unknown) {
1544  if (LastQueriedOpToUnknown != CurrentOP &&
1545  LastQueriedOpToUnknown != QueriedOP) {
1546  // If we got the Unknown state for both different operators.
1547  // if (x <= y) // assume true
1548  // if (x != y) // assume true
1549  // if (x < y) // would be also true
1550  // Get a state from `UnknownX2` column.
1551  BranchState = CmpOpTable.getCmpOpStateForUnknownX2(CurrentOP);
1552  } else {
1553  LastQueriedOpToUnknown = QueriedOP;
1554  continue;
1555  }
1556  }
1557 
1558  return (BranchState == OperatorRelationsTable::True) ? getTrueRange(T)
1559  : getFalseRange(T);
1560  }
1561 
1562  return llvm::None;
1563  }
1564 
1565  Optional<RangeSet> getRangeForEqualities(const SymSymExpr *Sym) {
1566  Optional<bool> Equality = meansEquality(Sym);
1567 
1568  if (!Equality)
1569  return llvm::None;
1570 
1571  if (Optional<bool> AreEqual =
1572  EquivalenceClass::areEqual(State, Sym->getLHS(), Sym->getRHS())) {
1573  // Here we cover two cases at once:
1574  // * if Sym is equality and its operands are known to be equal -> true
1575  // * if Sym is disequality and its operands are disequal -> true
1576  if (*AreEqual == *Equality) {
1577  return getTrueRange(Sym->getType());
1578  }
1579  // Opposite combinations result in false.
1580  return getFalseRange(Sym->getType());
1581  }
1582 
1583  return llvm::None;
1584  }
1585 
1586  RangeSet getTrueRange(QualType T) {
1587  RangeSet TypeRange = infer(T);
1588  return assumeNonZero(TypeRange, T);
1589  }
1590 
1591  RangeSet getFalseRange(QualType T) {
1592  const llvm::APSInt &Zero = ValueFactory.getValue(0, T);
1593  return RangeSet(RangeFactory, Zero);
1594  }
1595 
1596  BasicValueFactory &ValueFactory;
1597  RangeSet::Factory &RangeFactory;
1599 };
1600 
1601 //===----------------------------------------------------------------------===//
1602 // Range-based reasoning about symbolic operations
1603 //===----------------------------------------------------------------------===//
1604 
1605 template <>
1606 RangeSet SymbolicRangeInferrer::VisitBinaryOperator<BO_Or>(Range LHS, Range RHS,
1607  QualType T) {
1608  APSIntType ResultType = ValueFactory.getAPSIntType(T);
1609  llvm::APSInt Zero = ResultType.getZeroValue();
1610 
1611  bool IsLHSPositiveOrZero = LHS.From() >= Zero;
1612  bool IsRHSPositiveOrZero = RHS.From() >= Zero;
1613 
1614  bool IsLHSNegative = LHS.To() < Zero;
1615  bool IsRHSNegative = RHS.To() < Zero;
1616 
1617  // Check if both ranges have the same sign.
1618  if ((IsLHSPositiveOrZero && IsRHSPositiveOrZero) ||
1619  (IsLHSNegative && IsRHSNegative)) {
1620  // The result is definitely greater or equal than any of the operands.
1621  const llvm::APSInt &Min = std::max(LHS.From(), RHS.From());
1622 
1623  // We estimate maximal value for positives as the maximal value for the
1624  // given type. For negatives, we estimate it with -1 (e.g. 0x11111111).
1625  //
1626  // TODO: We basically, limit the resulting range from below, but don't do
1627  // anything with the upper bound.
1628  //
1629  // For positive operands, it can be done as follows: for the upper
1630  // bound of LHS and RHS we calculate the most significant bit set.
1631  // Let's call it the N-th bit. Then we can estimate the maximal
1632  // number to be 2^(N+1)-1, i.e. the number with all the bits up to
1633  // the N-th bit set.
1634  const llvm::APSInt &Max = IsLHSNegative
1635  ? ValueFactory.getValue(--Zero)
1636  : ValueFactory.getMaxValue(ResultType);
1637 
1638  return {RangeFactory, ValueFactory.getValue(Min), Max};
1639  }
1640 
1641  // Otherwise, let's check if at least one of the operands is negative.
1642  if (IsLHSNegative || IsRHSNegative) {
1643  // This means that the result is definitely negative as well.
1644  return {RangeFactory, ValueFactory.getMinValue(ResultType),
1645  ValueFactory.getValue(--Zero)};
1646  }
1647 
1648  RangeSet DefaultRange = infer(T);
1649 
1650  // It is pretty hard to reason about operands with different signs
1651  // (and especially with possibly different signs). We simply check if it
1652  // can be zero. In order to conclude that the result could not be zero,
1653  // at least one of the operands should be definitely not zero itself.
1654  if (!LHS.Includes(Zero) || !RHS.Includes(Zero)) {
1655  return assumeNonZero(DefaultRange, T);
1656  }
1657 
1658  // Nothing much else to do here.
1659  return DefaultRange;
1660 }
1661 
1662 template <>
1663 RangeSet SymbolicRangeInferrer::VisitBinaryOperator<BO_And>(Range LHS,
1664  Range RHS,
1665  QualType T) {
1666  APSIntType ResultType = ValueFactory.getAPSIntType(T);
1667  llvm::APSInt Zero = ResultType.getZeroValue();
1668 
1669  bool IsLHSPositiveOrZero = LHS.From() >= Zero;
1670  bool IsRHSPositiveOrZero = RHS.From() >= Zero;
1671 
1672  bool IsLHSNegative = LHS.To() < Zero;
1673  bool IsRHSNegative = RHS.To() < Zero;
1674 
1675  // Check if both ranges have the same sign.
1676  if ((IsLHSPositiveOrZero && IsRHSPositiveOrZero) ||
1677  (IsLHSNegative && IsRHSNegative)) {
1678  // The result is definitely less or equal than any of the operands.
1679  const llvm::APSInt &Max = std::min(LHS.To(), RHS.To());
1680 
1681  // We conservatively estimate lower bound to be the smallest positive
1682  // or negative value corresponding to the sign of the operands.
1683  const llvm::APSInt &Min = IsLHSNegative
1684  ? ValueFactory.getMinValue(ResultType)
1685  : ValueFactory.getValue(Zero);
1686 
1687  return {RangeFactory, Min, Max};
1688  }
1689 
1690  // Otherwise, let's check if at least one of the operands is positive.
1691  if (IsLHSPositiveOrZero || IsRHSPositiveOrZero) {
1692  // This makes result definitely positive.
1693  //
1694  // We can also reason about a maximal value by finding the maximal
1695  // value of the positive operand.
1696  const llvm::APSInt &Max = IsLHSPositiveOrZero ? LHS.To() : RHS.To();
1697 
1698  // The minimal value on the other hand is much harder to reason about.
1699  // The only thing we know for sure is that the result is positive.
1700  return {RangeFactory, ValueFactory.getValue(Zero),
1701  ValueFactory.getValue(Max)};
1702  }
1703 
1704  // Nothing much else to do here.
1705  return infer(T);
1706 }
1707 
1708 template <>
1709 RangeSet SymbolicRangeInferrer::VisitBinaryOperator<BO_Rem>(Range LHS,
1710  Range RHS,
1711  QualType T) {
1712  llvm::APSInt Zero = ValueFactory.getAPSIntType(T).getZeroValue();
1713 
1714  Range ConservativeRange = getSymmetricalRange(RHS, T);
1715 
1716  llvm::APSInt Max = ConservativeRange.To();
1717  llvm::APSInt Min = ConservativeRange.From();
1718 
1719  if (Max == Zero) {
1720  // It's an undefined behaviour to divide by 0 and it seems like we know
1721  // for sure that RHS is 0. Let's say that the resulting range is
1722  // simply infeasible for that matter.
1723  return RangeFactory.getEmptySet();
1724  }
1725 
1726  // At this point, our conservative range is closed. The result, however,
1727  // couldn't be greater than the RHS' maximal absolute value. Because of
1728  // this reason, we turn the range into open (or half-open in case of
1729  // unsigned integers).
1730  //
1731  // While we operate on integer values, an open interval (a, b) can be easily
1732  // represented by the closed interval [a + 1, b - 1]. And this is exactly
1733  // what we do next.
1734  //
1735  // If we are dealing with unsigned case, we shouldn't move the lower bound.
1736  if (Min.isSigned()) {
1737  ++Min;
1738  }
1739  --Max;
1740 
1741  bool IsLHSPositiveOrZero = LHS.From() >= Zero;
1742  bool IsRHSPositiveOrZero = RHS.From() >= Zero;
1743 
1744  // Remainder operator results with negative operands is implementation
1745  // defined. Positive cases are much easier to reason about though.
1746  if (IsLHSPositiveOrZero && IsRHSPositiveOrZero) {
1747  // If maximal value of LHS is less than maximal value of RHS,
1748  // the result won't get greater than LHS.To().
1749  Max = std::min(LHS.To(), Max);
1750  // We want to check if it is a situation similar to the following:
1751  //
1752  // <------------|---[ LHS ]--------[ RHS ]----->
1753  // -INF 0 +INF
1754  //
1755  // In this situation, we can conclude that (LHS / RHS) == 0 and
1756  // (LHS % RHS) == LHS.
1757  Min = LHS.To() < RHS.From() ? LHS.From() : Zero;
1758  }
1759 
1760  // Nevertheless, the symmetrical range for RHS is a conservative estimate
1761  // for any sign of either LHS, or RHS.
1762  return {RangeFactory, ValueFactory.getValue(Min), ValueFactory.getValue(Max)};
1763 }
1764 
1765 //===----------------------------------------------------------------------===//
1766 // Constraint manager implementation details
1767 //===----------------------------------------------------------------------===//
1768 
1769 class RangeConstraintManager : public RangedConstraintManager {
1770 public:
1771  RangeConstraintManager(ExprEngine *EE, SValBuilder &SVB)
1772  : RangedConstraintManager(EE, SVB), F(getBasicVals()) {}
1773 
1774  //===------------------------------------------------------------------===//
1775  // Implementation for interface from ConstraintManager.
1776  //===------------------------------------------------------------------===//
1777 
1778  bool haveEqualConstraints(ProgramStateRef S1,
1779  ProgramStateRef S2) const override {
1780  // NOTE: ClassMembers are as simple as back pointers for ClassMap,
1781  // so comparing constraint ranges and class maps should be
1782  // sufficient.
1783  return S1->get<ConstraintRange>() == S2->get<ConstraintRange>() &&
1784  S1->get<ClassMap>() == S2->get<ClassMap>();
1785  }
1786 
1787  bool canReasonAbout(SVal X) const override;
1788 
1789  ConditionTruthVal checkNull(ProgramStateRef State, SymbolRef Sym) override;
1790 
1791  const llvm::APSInt *getSymVal(ProgramStateRef State,
1792  SymbolRef Sym) const override;
1793 
1794  ProgramStateRef removeDeadBindings(ProgramStateRef State,
1795  SymbolReaper &SymReaper) override;
1796 
1797  void printJson(raw_ostream &Out, ProgramStateRef State, const char *NL = "\n",
1798  unsigned int Space = 0, bool IsDot = false) const override;
1799  void printConstraints(raw_ostream &Out, ProgramStateRef State,
1800  const char *NL = "\n", unsigned int Space = 0,
1801  bool IsDot = false) const;
1802  void printEquivalenceClasses(raw_ostream &Out, ProgramStateRef State,
1803  const char *NL = "\n", unsigned int Space = 0,
1804  bool IsDot = false) const;
1805  void printDisequalities(raw_ostream &Out, ProgramStateRef State,
1806  const char *NL = "\n", unsigned int Space = 0,
1807  bool IsDot = false) const;
1808 
1809  //===------------------------------------------------------------------===//
1810  // Implementation for interface from RangedConstraintManager.
1811  //===------------------------------------------------------------------===//
1812 
1814  const llvm::APSInt &V,
1815  const llvm::APSInt &Adjustment) override;
1816 
1818  const llvm::APSInt &V,
1819  const llvm::APSInt &Adjustment) override;
1820 
1822  const llvm::APSInt &V,
1823  const llvm::APSInt &Adjustment) override;
1824 
1826  const llvm::APSInt &V,
1827  const llvm::APSInt &Adjustment) override;
1828 
1830  const llvm::APSInt &V,
1831  const llvm::APSInt &Adjustment) override;
1832 
1834  const llvm::APSInt &V,
1835  const llvm::APSInt &Adjustment) override;
1836 
1837  ProgramStateRef assumeSymWithinInclusiveRange(
1838  ProgramStateRef State, SymbolRef Sym, const llvm::APSInt &From,
1839  const llvm::APSInt &To, const llvm::APSInt &Adjustment) override;
1840 
1841  ProgramStateRef assumeSymOutsideInclusiveRange(
1842  ProgramStateRef State, SymbolRef Sym, const llvm::APSInt &From,
1843  const llvm::APSInt &To, const llvm::APSInt &Adjustment) override;
1844 
1845 private:
1847 
1848  RangeSet getRange(ProgramStateRef State, SymbolRef Sym);
1849  RangeSet getRange(ProgramStateRef State, EquivalenceClass Class);
1851  RangeSet Range);
1852  ProgramStateRef setRange(ProgramStateRef State, EquivalenceClass Class,
1853  RangeSet Range);
1854 
1855  RangeSet getSymLTRange(ProgramStateRef St, SymbolRef Sym,
1856  const llvm::APSInt &Int,
1857  const llvm::APSInt &Adjustment);
1858  RangeSet getSymGTRange(ProgramStateRef St, SymbolRef Sym,
1859  const llvm::APSInt &Int,
1860  const llvm::APSInt &Adjustment);
1861  RangeSet getSymLERange(ProgramStateRef St, SymbolRef Sym,
1862  const llvm::APSInt &Int,
1863  const llvm::APSInt &Adjustment);
1864  RangeSet getSymLERange(llvm::function_ref<RangeSet()> RS,
1865  const llvm::APSInt &Int,
1866  const llvm::APSInt &Adjustment);
1867  RangeSet getSymGERange(ProgramStateRef St, SymbolRef Sym,
1868  const llvm::APSInt &Int,
1869  const llvm::APSInt &Adjustment);
1870 };
1871 
1872 //===----------------------------------------------------------------------===//
1873 // Constraint assignment logic
1874 //===----------------------------------------------------------------------===//
1875 
1876 /// ConstraintAssignorBase is a small utility class that unifies visitor
1877 /// for ranges with a visitor for constraints (rangeset/range/constant).
1878 ///
1879 /// It is designed to have one derived class, but generally it can have more.
1880 /// Derived class can control which types we handle by defining methods of the
1881 /// following form:
1882 ///
1883 /// bool handle${SYMBOL}To${CONSTRAINT}(const SYMBOL *Sym,
1884 /// CONSTRAINT Constraint);
1885 ///
1886 /// where SYMBOL is the type of the symbol (e.g. SymSymExpr, SymbolCast, etc.)
1887 /// CONSTRAINT is the type of constraint (RangeSet/Range/Const)
1888 /// return value signifies whether we should try other handle methods
1889 /// (i.e. false would mean to stop right after calling this method)
1890 template <class Derived> class ConstraintAssignorBase {
1891 public:
1892  using Const = const llvm::APSInt &;
1893 
1894 #define DISPATCH(CLASS) return assign##CLASS##Impl(cast<CLASS>(Sym), Constraint)
1895 
1896 #define ASSIGN(CLASS, TO, SYM, CONSTRAINT) \
1897  if (!static_cast<Derived *>(this)->assign##CLASS##To##TO(SYM, CONSTRAINT)) \
1898  return false
1899 
1900  void assign(SymbolRef Sym, RangeSet Constraint) {
1901  assignImpl(Sym, Constraint);
1902  }
1903 
1904  bool assignImpl(SymbolRef Sym, RangeSet Constraint) {
1905  switch (Sym->getKind()) {
1906 #define SYMBOL(Id, Parent) \
1907  case SymExpr::Id##Kind: \
1908  DISPATCH(Id);
1909 #include "clang/StaticAnalyzer/Core/PathSensitive/Symbols.def"
1910  }
1911  llvm_unreachable("Unknown SymExpr kind!");
1912  }
1913 
1914 #define DEFAULT_ASSIGN(Id) \
1915  bool assign##Id##To##RangeSet(const Id *Sym, RangeSet Constraint) { \
1916  return true; \
1917  } \
1918  bool assign##Id##To##Range(const Id *Sym, Range Constraint) { return true; } \
1919  bool assign##Id##To##Const(const Id *Sym, Const Constraint) { return true; }
1920 
1921  // When we dispatch for constraint types, we first try to check
1922  // if the new constraint is the constant and try the corresponding
1923  // assignor methods. If it didn't interrupt, we can proceed to the
1924  // range, and finally to the range set.
1925 #define CONSTRAINT_DISPATCH(Id) \
1926  if (const llvm::APSInt *Const = Constraint.getConcreteValue()) { \
1927  ASSIGN(Id, Const, Sym, *Const); \
1928  } \
1929  if (Constraint.size() == 1) { \
1930  ASSIGN(Id, Range, Sym, *Constraint.begin()); \
1931  } \
1932  ASSIGN(Id, RangeSet, Sym, Constraint)
1933 
1934  // Our internal assign method first tries to call assignor methods for all
1935  // constraint types that apply. And if not interrupted, continues with its
1936  // parent class.
1937 #define SYMBOL(Id, Parent) \
1938  bool assign##Id##Impl(const Id *Sym, RangeSet Constraint) { \
1939  CONSTRAINT_DISPATCH(Id); \
1940  DISPATCH(Parent); \
1941  } \
1942  DEFAULT_ASSIGN(Id)
1943 #define ABSTRACT_SYMBOL(Id, Parent) SYMBOL(Id, Parent)
1944 #include "clang/StaticAnalyzer/Core/PathSensitive/Symbols.def"
1945 
1946  // Default implementations for the top class that doesn't have parents.
1947  bool assignSymExprImpl(const SymExpr *Sym, RangeSet Constraint) {
1948  CONSTRAINT_DISPATCH(SymExpr);
1949  return true;
1950  }
1951  DEFAULT_ASSIGN(SymExpr);
1952 
1953 #undef DISPATCH
1954 #undef CONSTRAINT_DISPATCH
1955 #undef DEFAULT_ASSIGN
1956 #undef ASSIGN
1957 };
1958 
1959 /// A little component aggregating all of the reasoning we have about
1960 /// assigning new constraints to symbols.
1961 ///
1962 /// The main purpose of this class is to associate constraints to symbols,
1963 /// and impose additional constraints on other symbols, when we can imply
1964 /// them.
1965 ///
1966 /// It has a nice symmetry with SymbolicRangeInferrer. When the latter
1967 /// can provide more precise ranges by looking into the operands of the
1968 /// expression in question, ConstraintAssignor looks into the operands
1969 /// to see if we can imply more from the new constraint.
1970 class ConstraintAssignor : public ConstraintAssignorBase<ConstraintAssignor> {
1971 public:
1972  template <class ClassOrSymbol>
1973  LLVM_NODISCARD static ProgramStateRef
1974  assign(ProgramStateRef State, SValBuilder &Builder, RangeSet::Factory &F,
1975  ClassOrSymbol CoS, RangeSet NewConstraint) {
1976  if (!State || NewConstraint.isEmpty())
1977  return nullptr;
1978 
1979  ConstraintAssignor Assignor{State, Builder, F};
1980  return Assignor.assign(CoS, NewConstraint);
1981  }
1982 
1983  /// Handle expressions like: a % b != 0.
1984  template <typename SymT>
1985  bool handleRemainderOp(const SymT *Sym, RangeSet Constraint) {
1986  if (Sym->getOpcode() != BO_Rem)
1987  return true;
1988  // a % b != 0 implies that a != 0.
1989  if (!Constraint.containsZero()) {
1990  SVal SymSVal = Builder.makeSymbolVal(Sym->getLHS());
1991  if (auto NonLocSymSVal = SymSVal.getAs<nonloc::SymbolVal>()) {
1992  State = State->assume(*NonLocSymSVal, true);
1993  if (!State)
1994  return false;
1995  }
1996  }
1997  return true;
1998  }
1999 
2000  inline bool assignSymExprToConst(const SymExpr *Sym, Const Constraint);
2001  inline bool assignSymIntExprToRangeSet(const SymIntExpr *Sym,
2002  RangeSet Constraint) {
2003  return handleRemainderOp(Sym, Constraint);
2004  }
2005  inline bool assignSymSymExprToRangeSet(const SymSymExpr *Sym,
2006  RangeSet Constraint);
2007 
2008 private:
2009  ConstraintAssignor(ProgramStateRef State, SValBuilder &Builder,
2010  RangeSet::Factory &F)
2011  : State(State), Builder(Builder), RangeFactory(F) {}
2012  using Base = ConstraintAssignorBase<ConstraintAssignor>;
2013 
2014  /// Base method for handling new constraints for symbols.
2015  LLVM_NODISCARD ProgramStateRef assign(SymbolRef Sym, RangeSet NewConstraint) {
2016  // All constraints are actually associated with equivalence classes, and
2017  // that's what we are going to do first.
2018  State = assign(EquivalenceClass::find(State, Sym), NewConstraint);
2019  if (!State)
2020  return nullptr;
2021 
2022  // And after that we can check what other things we can get from this
2023  // constraint.
2024  Base::assign(Sym, NewConstraint);
2025  return State;
2026  }
2027 
2028  /// Base method for handling new constraints for classes.
2029  LLVM_NODISCARD ProgramStateRef assign(EquivalenceClass Class,
2030  RangeSet NewConstraint) {
2031  // There is a chance that we might need to update constraints for the
2032  // classes that are known to be disequal to Class.
2033  //
2034  // In order for this to be even possible, the new constraint should
2035  // be simply a constant because we can't reason about range disequalities.
2036  if (const llvm::APSInt *Point = NewConstraint.getConcreteValue()) {
2037 
2038  ConstraintRangeTy Constraints = State->get<ConstraintRange>();
2039  ConstraintRangeTy::Factory &CF = State->get_context<ConstraintRange>();
2040 
2041  // Add new constraint.
2042  Constraints = CF.add(Constraints, Class, NewConstraint);
2043 
2044  for (EquivalenceClass DisequalClass : Class.getDisequalClasses(State)) {
2045  RangeSet UpdatedConstraint = SymbolicRangeInferrer::inferRange(
2046  RangeFactory, State, DisequalClass);
2047 
2048  UpdatedConstraint = RangeFactory.deletePoint(UpdatedConstraint, *Point);
2049 
2050  // If we end up with at least one of the disequal classes to be
2051  // constrained with an empty range-set, the state is infeasible.
2052  if (UpdatedConstraint.isEmpty())
2053  return nullptr;
2054 
2055  Constraints = CF.add(Constraints, DisequalClass, UpdatedConstraint);
2056  }
2057  assert(areFeasible(Constraints) && "Constraint manager shouldn't produce "
2058  "a state with infeasible constraints");
2059 
2060  return setConstraints(State, Constraints);
2061  }
2062 
2063  return setConstraint(State, Class, NewConstraint);
2064  }
2065 
2066  ProgramStateRef trackDisequality(ProgramStateRef State, SymbolRef LHS,
2067  SymbolRef RHS) {
2068  return EquivalenceClass::markDisequal(RangeFactory, State, LHS, RHS);
2069  }
2070 
2071  ProgramStateRef trackEquality(ProgramStateRef State, SymbolRef LHS,
2072  SymbolRef RHS) {
2073  return EquivalenceClass::merge(RangeFactory, State, LHS, RHS);
2074  }
2075 
2076  LLVM_NODISCARD Optional<bool> interpreteAsBool(RangeSet Constraint) {
2077  assert(!Constraint.isEmpty() && "Empty ranges shouldn't get here");
2078 
2079  if (Constraint.getConcreteValue())
2080  return !Constraint.getConcreteValue()->isZero();
2081 
2082  if (!Constraint.containsZero())
2083  return true;
2084 
2085  return llvm::None;
2086  }
2087 
2089  SValBuilder &Builder;
2090  RangeSet::Factory &RangeFactory;
2091 };
2092 
2093 
2094 bool ConstraintAssignor::assignSymExprToConst(const SymExpr *Sym,
2095  const llvm::APSInt &Constraint) {
2096  llvm::SmallSet<EquivalenceClass, 4> SimplifiedClasses;
2097  // Iterate over all equivalence classes and try to simplify them.
2098  ClassMembersTy Members = State->get<ClassMembers>();
2099  for (std::pair<EquivalenceClass, SymbolSet> ClassToSymbolSet : Members) {
2100  EquivalenceClass Class = ClassToSymbolSet.first;
2101  State = EquivalenceClass::simplify(Builder, RangeFactory, State, Class);
2102  if (!State)
2103  return false;
2104  SimplifiedClasses.insert(Class);
2105  }
2106 
2107  // Trivial equivalence classes (those that have only one symbol member) are
2108  // not stored in the State. Thus, we must skim through the constraints as
2109  // well. And we try to simplify symbols in the constraints.
2110  ConstraintRangeTy Constraints = State->get<ConstraintRange>();
2111  for (std::pair<EquivalenceClass, RangeSet> ClassConstraint : Constraints) {
2112  EquivalenceClass Class = ClassConstraint.first;
2113  if (SimplifiedClasses.count(Class)) // Already simplified.
2114  continue;
2115  State = EquivalenceClass::simplify(Builder, RangeFactory, State, Class);
2116  if (!State)
2117  return false;
2118  }
2119 
2120  // We may have trivial equivalence classes in the disequality info as
2121  // well, and we need to simplify them.
2122  DisequalityMapTy DisequalityInfo = State->get<DisequalityMap>();
2123  for (std::pair<EquivalenceClass, ClassSet> DisequalityEntry :
2124  DisequalityInfo) {
2125  EquivalenceClass Class = DisequalityEntry.first;
2126  ClassSet DisequalClasses = DisequalityEntry.second;
2127  State = EquivalenceClass::simplify(Builder, RangeFactory, State, Class);
2128  if (!State)
2129  return false;
2130  }
2131 
2132  return true;
2133 }
2134 
2135 bool ConstraintAssignor::assignSymSymExprToRangeSet(const SymSymExpr *Sym,
2136  RangeSet Constraint) {
2137  if (!handleRemainderOp(Sym, Constraint))
2138  return false;
2139 
2140  Optional<bool> ConstraintAsBool = interpreteAsBool(Constraint);
2141 
2142  if (!ConstraintAsBool)
2143  return true;
2144 
2145  if (Optional<bool> Equality = meansEquality(Sym)) {
2146  // Here we cover two cases:
2147  // * if Sym is equality and the new constraint is true -> Sym's operands
2148  // should be marked as equal
2149  // * if Sym is disequality and the new constraint is false -> Sym's
2150  // operands should be also marked as equal
2151  if (*Equality == *ConstraintAsBool) {
2152  State = trackEquality(State, Sym->getLHS(), Sym->getRHS());
2153  } else {
2154  // Other combinations leave as with disequal operands.
2155  State = trackDisequality(State, Sym->getLHS(), Sym->getRHS());
2156  }
2157 
2158  if (!State)
2159  return false;
2160  }
2161 
2162  return true;
2163 }
2164 
2165 } // end anonymous namespace
2166 
2167 std::unique_ptr<ConstraintManager>
2169  ExprEngine *Eng) {
2170  return std::make_unique<RangeConstraintManager>(Eng, StMgr.getSValBuilder());
2171 }
2172 
2174  ConstraintMap::Factory &F = State->get_context<ConstraintMap>();
2175  ConstraintMap Result = F.getEmptyMap();
2176 
2177  ConstraintRangeTy Constraints = State->get<ConstraintRange>();
2178  for (std::pair<EquivalenceClass, RangeSet> ClassConstraint : Constraints) {
2179  EquivalenceClass Class = ClassConstraint.first;
2180  SymbolSet ClassMembers = Class.getClassMembers(State);
2181  assert(!ClassMembers.isEmpty() &&
2182  "Class must always have at least one member!");
2183 
2184  SymbolRef Representative = *ClassMembers.begin();
2185  Result = F.add(Result, Representative, ClassConstraint.second);
2186  }
2187 
2188  return Result;
2189 }
2190 
2191 //===----------------------------------------------------------------------===//
2192 // EqualityClass implementation details
2193 //===----------------------------------------------------------------------===//
2194 
2195 LLVM_DUMP_METHOD void EquivalenceClass::dumpToStream(ProgramStateRef State,
2196  raw_ostream &os) const {
2197  SymbolSet ClassMembers = getClassMembers(State);
2198  for (const SymbolRef &MemberSym : ClassMembers) {
2199  MemberSym->dump();
2200  os << "\n";
2201  }
2202 }
2203 
2204 inline EquivalenceClass EquivalenceClass::find(ProgramStateRef State,
2205  SymbolRef Sym) {
2206  assert(State && "State should not be null");
2207  assert(Sym && "Symbol should not be null");
2208  // We store far from all Symbol -> Class mappings
2209  if (const EquivalenceClass *NontrivialClass = State->get<ClassMap>(Sym))
2210  return *NontrivialClass;
2211 
2212  // This is a trivial class of Sym.
2213  return Sym;
2214 }
2215 
2216 inline ProgramStateRef EquivalenceClass::merge(RangeSet::Factory &F,
2218  SymbolRef First,
2219  SymbolRef Second) {
2220  EquivalenceClass FirstClass = find(State, First);
2221  EquivalenceClass SecondClass = find(State, Second);
2222 
2223  return FirstClass.merge(F, State, SecondClass);
2224 }
2225 
2226 inline ProgramStateRef EquivalenceClass::merge(RangeSet::Factory &F,
2228  EquivalenceClass Other) {
2229  // It is already the same class.
2230  if (*this == Other)
2231  return State;
2232 
2233  // FIXME: As of now, we support only equivalence classes of the same type.
2234  // This limitation is connected to the lack of explicit casts in
2235  // our symbolic expression model.
2236  //
2237  // That means that for `int x` and `char y` we don't distinguish
2238  // between these two very different cases:
2239  // * `x == y`
2240  // * `(char)x == y`
2241  //
2242  // The moment we introduce symbolic casts, this restriction can be
2243  // lifted.
2244  if (getType() != Other.getType())
2245  return State;
2246 
2247  SymbolSet Members = getClassMembers(State);
2248  SymbolSet OtherMembers = Other.getClassMembers(State);
2249 
2250  // We estimate the size of the class by the height of tree containing
2251  // its members. Merging is not a trivial operation, so it's easier to
2252  // merge the smaller class into the bigger one.
2253  if (Members.getHeight() >= OtherMembers.getHeight()) {
2254  return mergeImpl(F, State, Members, Other, OtherMembers);
2255  } else {
2256  return Other.mergeImpl(F, State, OtherMembers, *this, Members);
2257  }
2258 }
2259 
2260 inline ProgramStateRef
2261 EquivalenceClass::mergeImpl(RangeSet::Factory &RangeFactory,
2262  ProgramStateRef State, SymbolSet MyMembers,
2263  EquivalenceClass Other, SymbolSet OtherMembers) {
2264  // Essentially what we try to recreate here is some kind of union-find
2265  // data structure. It does have certain limitations due to persistence
2266  // and the need to remove elements from classes.
2267  //
2268  // In this setting, EquialityClass object is the representative of the class
2269  // or the parent element. ClassMap is a mapping of class members to their
2270  // parent. Unlike the union-find structure, they all point directly to the
2271  // class representative because we don't have an opportunity to actually do
2272  // path compression when dealing with immutability. This means that we
2273  // compress paths every time we do merges. It also means that we lose
2274  // the main amortized complexity benefit from the original data structure.
2275  ConstraintRangeTy Constraints = State->get<ConstraintRange>();
2276  ConstraintRangeTy::Factory &CRF = State->get_context<ConstraintRange>();
2277 
2278  // 1. If the merged classes have any constraints associated with them, we
2279  // need to transfer them to the class we have left.
2280  //
2281  // Intersection here makes perfect sense because both of these constraints
2282  // must hold for the whole new class.
2283  if (Optional<RangeSet> NewClassConstraint =
2284  intersect(RangeFactory, getConstraint(State, *this),
2285  getConstraint(State, Other))) {
2286  // NOTE: Essentially, NewClassConstraint should NEVER be infeasible because
2287  // range inferrer shouldn't generate ranges incompatible with
2288  // equivalence classes. However, at the moment, due to imperfections
2289  // in the solver, it is possible and the merge function can also
2290  // return infeasible states aka null states.
2291  if (NewClassConstraint->isEmpty())
2292  // Infeasible state
2293  return nullptr;
2294 
2295  // No need in tracking constraints of a now-dissolved class.
2296  Constraints = CRF.remove(Constraints, Other);
2297  // Assign new constraints for this class.
2298  Constraints = CRF.add(Constraints, *this, *NewClassConstraint);
2299 
2300  assert(areFeasible(Constraints) && "Constraint manager shouldn't produce "
2301  "a state with infeasible constraints");
2302 
2303  State = State->set<ConstraintRange>(Constraints);
2304  }
2305 
2306  // 2. Get ALL equivalence-related maps
2307  ClassMapTy Classes = State->get<ClassMap>();
2308  ClassMapTy::Factory &CMF = State->get_context<ClassMap>();
2309 
2310  ClassMembersTy Members = State->get<ClassMembers>();
2311  ClassMembersTy::Factory &MF = State->get_context<ClassMembers>();
2312 
2313  DisequalityMapTy DisequalityInfo = State->get<DisequalityMap>();
2314  DisequalityMapTy::Factory &DF = State->get_context<DisequalityMap>();
2315 
2316  ClassSet::Factory &CF = State->get_context<ClassSet>();
2317  SymbolSet::Factory &F = getMembersFactory(State);
2318 
2319  // 2. Merge members of the Other class into the current class.
2320  SymbolSet NewClassMembers = MyMembers;
2321  for (SymbolRef Sym : OtherMembers) {
2322  NewClassMembers = F.add(NewClassMembers, Sym);
2323  // *this is now the class for all these new symbols.
2324  Classes = CMF.add(Classes, Sym, *this);
2325  }
2326 
2327  // 3. Adjust member mapping.
2328  //
2329  // No need in tracking members of a now-dissolved class.
2330  Members = MF.remove(Members, Other);
2331  // Now only the current class is mapped to all the symbols.
2332  Members = MF.add(Members, *this, NewClassMembers);
2333 
2334  // 4. Update disequality relations
2335  ClassSet DisequalToOther = Other.getDisequalClasses(DisequalityInfo, CF);
2336  // We are about to merge two classes but they are already known to be
2337  // non-equal. This is a contradiction.
2338  if (DisequalToOther.contains(*this))
2339  return nullptr;
2340 
2341  if (!DisequalToOther.isEmpty()) {
2342  ClassSet DisequalToThis = getDisequalClasses(DisequalityInfo, CF);
2343  DisequalityInfo = DF.remove(DisequalityInfo, Other);
2344 
2345  for (EquivalenceClass DisequalClass : DisequalToOther) {
2346  DisequalToThis = CF.add(DisequalToThis, DisequalClass);
2347 
2348  // Disequality is a symmetric relation meaning that if
2349  // DisequalToOther not null then the set for DisequalClass is not
2350  // empty and has at least Other.
2351  ClassSet OriginalSetLinkedToOther =
2352  *DisequalityInfo.lookup(DisequalClass);
2353 
2354  // Other will be eliminated and we should replace it with the bigger
2355  // united class.
2356  ClassSet NewSet = CF.remove(OriginalSetLinkedToOther, Other);
2357  NewSet = CF.add(NewSet, *this);
2358 
2359  DisequalityInfo = DF.add(DisequalityInfo, DisequalClass, NewSet);
2360  }
2361 
2362  DisequalityInfo = DF.add(DisequalityInfo, *this, DisequalToThis);
2363  State = State->set<DisequalityMap>(DisequalityInfo);
2364  }
2365 
2366  // 5. Update the state
2367  State = State->set<ClassMap>(Classes);
2368  State = State->set<ClassMembers>(Members);
2369 
2370  return State;
2371 }
2372 
2373 inline SymbolSet::Factory &
2374 EquivalenceClass::getMembersFactory(ProgramStateRef State) {
2375  return State->get_context<SymbolSet>();
2376 }
2377 
2378 SymbolSet EquivalenceClass::getClassMembers(ProgramStateRef State) const {
2379  if (const SymbolSet *Members = State->get<ClassMembers>(*this))
2380  return *Members;
2381 
2382  // This class is trivial, so we need to construct a set
2383  // with just that one symbol from the class.
2384  SymbolSet::Factory &F = getMembersFactory(State);
2385  return F.add(F.getEmptySet(), getRepresentativeSymbol());
2386 }
2387 
2389  return State->get<ClassMembers>(*this) == nullptr;
2390 }
2391 
2392 bool EquivalenceClass::isTriviallyDead(ProgramStateRef State,
2393  SymbolReaper &Reaper) const {
2394  return isTrivial(State) && Reaper.isDead(getRepresentativeSymbol());
2395 }
2396 
2397 inline ProgramStateRef EquivalenceClass::markDisequal(RangeSet::Factory &RF,
2399  SymbolRef First,
2400  SymbolRef Second) {
2401  return markDisequal(RF, State, find(State, First), find(State, Second));
2402 }
2403 
2404 inline ProgramStateRef EquivalenceClass::markDisequal(RangeSet::Factory &RF,
2406  EquivalenceClass First,
2407  EquivalenceClass Second) {
2408  return First.markDisequal(RF, State, Second);
2409 }
2410 
2411 inline ProgramStateRef
2412 EquivalenceClass::markDisequal(RangeSet::Factory &RF, ProgramStateRef State,
2413  EquivalenceClass Other) const {
2414  // If we know that two classes are equal, we can only produce an infeasible
2415  // state.
2416  if (*this == Other) {
2417  return nullptr;
2418  }
2419 
2420  DisequalityMapTy DisequalityInfo = State->get<DisequalityMap>();
2421  ConstraintRangeTy Constraints = State->get<ConstraintRange>();
2422 
2423  // Disequality is a symmetric relation, so if we mark A as disequal to B,
2424  // we should also mark B as disequalt to A.
2425  if (!addToDisequalityInfo(DisequalityInfo, Constraints, RF, State, *this,
2426  Other) ||
2427  !addToDisequalityInfo(DisequalityInfo, Constraints, RF, State, Other,
2428  *this))
2429  return nullptr;
2430 
2431  assert(areFeasible(Constraints) && "Constraint manager shouldn't produce "
2432  "a state with infeasible constraints");
2433 
2434  State = State->set<DisequalityMap>(DisequalityInfo);
2435  State = State->set<ConstraintRange>(Constraints);
2436 
2437  return State;
2438 }
2439 
2440 inline bool EquivalenceClass::addToDisequalityInfo(
2441  DisequalityMapTy &Info, ConstraintRangeTy &Constraints,
2442  RangeSet::Factory &RF, ProgramStateRef State, EquivalenceClass First,
2443  EquivalenceClass Second) {
2444 
2445  // 1. Get all of the required factories.
2446  DisequalityMapTy::Factory &F = State->get_context<DisequalityMap>();
2447  ClassSet::Factory &CF = State->get_context<ClassSet>();
2448  ConstraintRangeTy::Factory &CRF = State->get_context<ConstraintRange>();
2449 
2450  // 2. Add Second to the set of classes disequal to First.
2451  const ClassSet *CurrentSet = Info.lookup(First);
2452  ClassSet NewSet = CurrentSet ? *CurrentSet : CF.getEmptySet();
2453  NewSet = CF.add(NewSet, Second);
2454 
2455  Info = F.add(Info, First, NewSet);
2456 
2457  // 3. If Second is known to be a constant, we can delete this point
2458  // from the constraint asociated with First.
2459  //
2460  // So, if Second == 10, it means that First != 10.
2461  // At the same time, the same logic does not apply to ranges.
2462  if (const RangeSet *SecondConstraint = Constraints.lookup(Second))
2463  if (const llvm::APSInt *Point = SecondConstraint->getConcreteValue()) {
2464 
2465  RangeSet FirstConstraint = SymbolicRangeInferrer::inferRange(
2466  RF, State, First.getRepresentativeSymbol());
2467 
2468  FirstConstraint = RF.deletePoint(FirstConstraint, *Point);
2469 
2470  // If the First class is about to be constrained with an empty
2471  // range-set, the state is infeasible.
2472  if (FirstConstraint.isEmpty())
2473  return false;
2474 
2475  Constraints = CRF.add(Constraints, First, FirstConstraint);
2476  }
2477 
2478  return true;
2479 }
2480 
2481 inline Optional<bool> EquivalenceClass::areEqual(ProgramStateRef State,
2482  SymbolRef FirstSym,
2483  SymbolRef SecondSym) {
2484  return EquivalenceClass::areEqual(State, find(State, FirstSym),
2485  find(State, SecondSym));
2486 }
2487 
2488 inline Optional<bool> EquivalenceClass::areEqual(ProgramStateRef State,
2489  EquivalenceClass First,
2490  EquivalenceClass Second) {
2491  // The same equivalence class => symbols are equal.
2492  if (First == Second)
2493  return true;
2494 
2495  // Let's check if we know anything about these two classes being not equal to
2496  // each other.
2497  ClassSet DisequalToFirst = First.getDisequalClasses(State);
2498  if (DisequalToFirst.contains(Second))
2499  return false;
2500 
2501  // It is not clear.
2502  return llvm::None;
2503 }
2504 
2505 LLVM_NODISCARD ProgramStateRef
2506 EquivalenceClass::removeMember(ProgramStateRef State, const SymbolRef Old) {
2507 
2508  SymbolSet ClsMembers = getClassMembers(State);
2509  assert(ClsMembers.contains(Old));
2510 
2511  // We don't remove `Old`'s Sym->Class relation for two reasons:
2512  // 1) This way constraints for the old symbol can still be found via it's
2513  // equivalence class that it used to be the member of.
2514  // 2) Performance and resource reasons. We can spare one removal and thus one
2515  // additional tree in the forest of `ClassMap`.
2516 
2517  // Remove `Old`'s Class->Sym relation.
2518  SymbolSet::Factory &F = getMembersFactory(State);
2519  ClassMembersTy::Factory &EMFactory = State->get_context<ClassMembers>();
2520  ClsMembers = F.remove(ClsMembers, Old);
2521  // Ensure another precondition of the removeMember function (we can check
2522  // this only with isEmpty, thus we have to do the remove first).
2523  assert(!ClsMembers.isEmpty() &&
2524  "Class should have had at least two members before member removal");
2525  // Overwrite the existing members assigned to this class.
2526  ClassMembersTy ClassMembersMap = State->get<ClassMembers>();
2527  ClassMembersMap = EMFactory.add(ClassMembersMap, *this, ClsMembers);
2528  State = State->set<ClassMembers>(ClassMembersMap);
2529 
2530  return State;
2531 }
2532 
2533 // Re-evaluate an SVal with top-level `State->assume` logic.
2535  const RangeSet *Constraint,
2536  SVal TheValue) {
2537  if (!Constraint)
2538  return State;
2539 
2540  const auto DefinedVal = TheValue.castAs<DefinedSVal>();
2541 
2542  // If the SVal is 0, we can simply interpret that as `false`.
2543  if (Constraint->encodesFalseRange())
2544  return State->assume(DefinedVal, false);
2545 
2546  // If the constraint does not encode 0 then we can interpret that as `true`
2547  // AND as a Range(Set).
2548  if (Constraint->encodesTrueRange()) {
2549  State = State->assume(DefinedVal, true);
2550  if (!State)
2551  return nullptr;
2552  // Fall through, re-assume based on the range values as well.
2553  }
2554  // Overestimate the individual Ranges with the RangeSet' lowest and
2555  // highest values.
2556  return State->assumeInclusiveRange(DefinedVal, Constraint->getMinValue(),
2557  Constraint->getMaxValue(), true);
2558 }
2559 
2560 // Iterate over all symbols and try to simplify them. Once a symbol is
2561 // simplified then we check if we can merge the simplified symbol's equivalence
2562 // class to this class. This way, we simplify not just the symbols but the
2563 // classes as well: we strive to keep the number of the classes to be the
2564 // absolute minimum.
2565 LLVM_NODISCARD ProgramStateRef
2566 EquivalenceClass::simplify(SValBuilder &SVB, RangeSet::Factory &F,
2567  ProgramStateRef State, EquivalenceClass Class) {
2568  SymbolSet ClassMembers = Class.getClassMembers(State);
2569  for (const SymbolRef &MemberSym : ClassMembers) {
2570 
2571  const SVal SimplifiedMemberVal = simplifyToSVal(State, MemberSym);
2572  const SymbolRef SimplifiedMemberSym = SimplifiedMemberVal.getAsSymbol();
2573 
2574  // The symbol is collapsed to a constant, check if the current State is
2575  // still feasible.
2576  if (const auto CI = SimplifiedMemberVal.getAs<nonloc::ConcreteInt>()) {
2577  const llvm::APSInt &SV = CI->getValue();
2578  const RangeSet *ClassConstraint = getConstraint(State, Class);
2579  // We have found a contradiction.
2580  if (ClassConstraint && !ClassConstraint->contains(SV))
2581  return nullptr;
2582  }
2583 
2584  if (SimplifiedMemberSym && MemberSym != SimplifiedMemberSym) {
2585  // The simplified symbol should be the member of the original Class,
2586  // however, it might be in another existing class at the moment. We
2587  // have to merge these classes.
2588  ProgramStateRef OldState = State;
2589  State = merge(F, State, MemberSym, SimplifiedMemberSym);
2590  if (!State)
2591  return nullptr;
2592  // No state change, no merge happened actually.
2593  if (OldState == State)
2594  continue;
2595 
2596  assert(find(State, MemberSym) == find(State, SimplifiedMemberSym));
2597  // Remove the old and more complex symbol.
2598  State = find(State, MemberSym).removeMember(State, MemberSym);
2599 
2600  // Query the class constraint again b/c that may have changed during the
2601  // merge above.
2602  const RangeSet *ClassConstraint = getConstraint(State, Class);
2603 
2604  // Re-evaluate an SVal with top-level `State->assume`, this ignites
2605  // a RECURSIVE algorithm that will reach a FIXPOINT.
2606  //
2607  // About performance and complexity: Let us assume that in a State we
2608  // have N non-trivial equivalence classes and that all constraints and
2609  // disequality info is related to non-trivial classes. In the worst case,
2610  // we can simplify only one symbol of one class in each iteration. The
2611  // number of symbols in one class cannot grow b/c we replace the old
2612  // symbol with the simplified one. Also, the number of the equivalence
2613  // classes can decrease only, b/c the algorithm does a merge operation
2614  // optionally. We need N iterations in this case to reach the fixpoint.
2615  // Thus, the steps needed to be done in the worst case is proportional to
2616  // N*N.
2617  //
2618  // This worst case scenario can be extended to that case when we have
2619  // trivial classes in the constraints and in the disequality map. This
2620  // case can be reduced to the case with a State where there are only
2621  // non-trivial classes. This is because a merge operation on two trivial
2622  // classes results in one non-trivial class.
2623  State = reAssume(State, ClassConstraint, SimplifiedMemberVal);
2624  if (!State)
2625  return nullptr;
2626  }
2627  }
2628  return State;
2629 }
2630 
2631 inline ClassSet EquivalenceClass::getDisequalClasses(ProgramStateRef State,
2632  SymbolRef Sym) {
2633  return find(State, Sym).getDisequalClasses(State);
2634 }
2635 
2636 inline ClassSet
2637 EquivalenceClass::getDisequalClasses(ProgramStateRef State) const {
2638  return getDisequalClasses(State->get<DisequalityMap>(),
2639  State->get_context<ClassSet>());
2640 }
2641 
2642 inline ClassSet
2643 EquivalenceClass::getDisequalClasses(DisequalityMapTy Map,
2644  ClassSet::Factory &Factory) const {
2645  if (const ClassSet *DisequalClasses = Map.lookup(*this))
2646  return *DisequalClasses;
2647 
2648  return Factory.getEmptySet();
2649 }
2650 
2651 bool EquivalenceClass::isClassDataConsistent(ProgramStateRef State) {
2652  ClassMembersTy Members = State->get<ClassMembers>();
2653 
2654  for (std::pair<EquivalenceClass, SymbolSet> ClassMembersPair : Members) {
2655  for (SymbolRef Member : ClassMembersPair.second) {
2656  // Every member of the class should have a mapping back to the class.
2657  if (find(State, Member) == ClassMembersPair.first) {
2658  continue;
2659  }
2660 
2661  return false;
2662  }
2663  }
2664 
2665  DisequalityMapTy Disequalities = State->get<DisequalityMap>();
2666  for (std::pair<EquivalenceClass, ClassSet> DisequalityInfo : Disequalities) {
2667  EquivalenceClass Class = DisequalityInfo.first;
2668  ClassSet DisequalClasses = DisequalityInfo.second;
2669 
2670  // There is no use in keeping empty sets in the map.
2671  if (DisequalClasses.isEmpty())
2672  return false;
2673 
2674  // Disequality is symmetrical, i.e. for every Class A and B that A != B,
2675  // B != A should also be true.
2676  for (EquivalenceClass DisequalClass : DisequalClasses) {
2677  const ClassSet *DisequalToDisequalClasses =
2678  Disequalities.lookup(DisequalClass);
2679 
2680  // It should be a set of at least one element: Class
2681  if (!DisequalToDisequalClasses ||
2682  !DisequalToDisequalClasses->contains(Class))
2683  return false;
2684  }
2685  }
2686 
2687  return true;
2688 }
2689 
2690 //===----------------------------------------------------------------------===//
2691 // RangeConstraintManager implementation
2692 //===----------------------------------------------------------------------===//
2693 
2694 bool RangeConstraintManager::canReasonAbout(SVal X) const {
2695  Optional<nonloc::SymbolVal> SymVal = X.getAs<nonloc::SymbolVal>();
2696  if (SymVal && SymVal->isExpression()) {
2697  const SymExpr *SE = SymVal->getSymbol();
2698 
2699  if (const SymIntExpr *SIE = dyn_cast<SymIntExpr>(SE)) {
2700  switch (SIE->getOpcode()) {
2701  // We don't reason yet about bitwise-constraints on symbolic values.
2702  case BO_And:
2703  case BO_Or:
2704  case BO_Xor:
2705  return false;
2706  // We don't reason yet about these arithmetic constraints on
2707  // symbolic values.
2708  case BO_Mul:
2709  case BO_Div:
2710  case BO_Rem:
2711  case BO_Shl:
2712  case BO_Shr:
2713  return false;
2714  // All other cases.
2715  default:
2716  return true;
2717  }
2718  }
2719 
2720  if (const SymSymExpr *SSE = dyn_cast<SymSymExpr>(SE)) {
2721  // FIXME: Handle <=> here.
2722  if (BinaryOperator::isEqualityOp(SSE->getOpcode()) ||
2723  BinaryOperator::isRelationalOp(SSE->getOpcode())) {
2724  // We handle Loc <> Loc comparisons, but not (yet) NonLoc <> NonLoc.
2725  // We've recently started producing Loc <> NonLoc comparisons (that
2726  // result from casts of one of the operands between eg. intptr_t and
2727  // void *), but we can't reason about them yet.
2728  if (Loc::isLocType(SSE->getLHS()->getType())) {
2729  return Loc::isLocType(SSE->getRHS()->getType());
2730  }
2731  }
2732  }
2733 
2734  return false;
2735  }
2736 
2737  return true;
2738 }
2739 
2740 ConditionTruthVal RangeConstraintManager::checkNull(ProgramStateRef State,
2741  SymbolRef Sym) {
2742  const RangeSet *Ranges = getConstraint(State, Sym);
2743 
2744  // If we don't have any information about this symbol, it's underconstrained.
2745  if (!Ranges)
2746  return ConditionTruthVal();
2747 
2748  // If we have a concrete value, see if it's zero.
2749  if (const llvm::APSInt *Value = Ranges->getConcreteValue())
2750  return *Value == 0;
2751 
2752  BasicValueFactory &BV = getBasicVals();
2753  APSIntType IntType = BV.getAPSIntType(Sym->getType());
2754  llvm::APSInt Zero = IntType.getZeroValue();
2755 
2756  // Check if zero is in the set of possible values.
2757  if (!Ranges->contains(Zero))
2758  return false;
2759 
2760  // Zero is a possible value, but it is not the /only/ possible value.
2761  return ConditionTruthVal();
2762 }
2763 
2764 const llvm::APSInt *RangeConstraintManager::getSymVal(ProgramStateRef St,
2765  SymbolRef Sym) const {
2766  const RangeSet *T = getConstraint(St, Sym);
2767  return T ? T->getConcreteValue() : nullptr;
2768 }
2769 
2770 //===----------------------------------------------------------------------===//
2771 // Remove dead symbols from existing constraints
2772 //===----------------------------------------------------------------------===//
2773 
2774 /// Scan all symbols referenced by the constraints. If the symbol is not alive
2775 /// as marked in LSymbols, mark it as dead in DSymbols.
2777 RangeConstraintManager::removeDeadBindings(ProgramStateRef State,
2778  SymbolReaper &SymReaper) {
2779  ClassMembersTy ClassMembersMap = State->get<ClassMembers>();
2780  ClassMembersTy NewClassMembersMap = ClassMembersMap;
2781  ClassMembersTy::Factory &EMFactory = State->get_context<ClassMembers>();
2782  SymbolSet::Factory &SetFactory = State->get_context<SymbolSet>();
2783 
2784  ConstraintRangeTy Constraints = State->get<ConstraintRange>();
2785  ConstraintRangeTy NewConstraints = Constraints;
2786  ConstraintRangeTy::Factory &ConstraintFactory =
2787  State->get_context<ConstraintRange>();
2788 
2789  ClassMapTy Map = State->get<ClassMap>();
2790  ClassMapTy NewMap = Map;
2791  ClassMapTy::Factory &ClassFactory = State->get_context<ClassMap>();
2792 
2793  DisequalityMapTy Disequalities = State->get<DisequalityMap>();
2794  DisequalityMapTy::Factory &DisequalityFactory =
2795  State->get_context<DisequalityMap>();
2796  ClassSet::Factory &ClassSetFactory = State->get_context<ClassSet>();
2797 
2798  bool ClassMapChanged = false;
2799  bool MembersMapChanged = false;
2800  bool ConstraintMapChanged = false;
2801  bool DisequalitiesChanged = false;
2802 
2803  auto removeDeadClass = [&](EquivalenceClass Class) {
2804  // Remove associated constraint ranges.
2805  Constraints = ConstraintFactory.remove(Constraints, Class);
2806  ConstraintMapChanged = true;
2807 
2808  // Update disequality information to not hold any information on the
2809  // removed class.
2810  ClassSet DisequalClasses =
2811  Class.getDisequalClasses(Disequalities, ClassSetFactory);
2812  if (!DisequalClasses.isEmpty()) {
2813  for (EquivalenceClass DisequalClass : DisequalClasses) {
2814  ClassSet DisequalToDisequalSet =
2815  DisequalClass.getDisequalClasses(Disequalities, ClassSetFactory);
2816  // DisequalToDisequalSet is guaranteed to be non-empty for consistent
2817  // disequality info.
2818  assert(!DisequalToDisequalSet.isEmpty());
2819  ClassSet NewSet = ClassSetFactory.remove(DisequalToDisequalSet, Class);
2820 
2821  // No need in keeping an empty set.
2822  if (NewSet.isEmpty()) {
2823  Disequalities =
2824  DisequalityFactory.remove(Disequalities, DisequalClass);
2825  } else {
2826  Disequalities =
2827  DisequalityFactory.add(Disequalities, DisequalClass, NewSet);
2828  }
2829  }
2830  // Remove the data for the class
2831  Disequalities = DisequalityFactory.remove(Disequalities, Class);
2832  DisequalitiesChanged = true;
2833  }
2834  };
2835 
2836  // 1. Let's see if dead symbols are trivial and have associated constraints.
2837  for (std::pair<EquivalenceClass, RangeSet> ClassConstraintPair :
2838  Constraints) {
2839  EquivalenceClass Class = ClassConstraintPair.first;
2840  if (Class.isTriviallyDead(State, SymReaper)) {
2841  // If this class is trivial, we can remove its constraints right away.
2842  removeDeadClass(Class);
2843  }
2844  }
2845 
2846  // 2. We don't need to track classes for dead symbols.
2847  for (std::pair<SymbolRef, EquivalenceClass> SymbolClassPair : Map) {
2848  SymbolRef Sym = SymbolClassPair.first;
2849 
2850  if (SymReaper.isDead(Sym)) {
2851  ClassMapChanged = true;
2852  NewMap = ClassFactory.remove(NewMap, Sym);
2853  }
2854  }
2855 
2856  // 3. Remove dead members from classes and remove dead non-trivial classes
2857  // and their constraints.
2858  for (std::pair<EquivalenceClass, SymbolSet> ClassMembersPair :
2859  ClassMembersMap) {
2860  EquivalenceClass Class = ClassMembersPair.first;
2861  SymbolSet LiveMembers = ClassMembersPair.second;
2862  bool MembersChanged = false;
2863 
2864  for (SymbolRef Member : ClassMembersPair.second) {
2865  if (SymReaper.isDead(Member)) {
2866  MembersChanged = true;
2867  LiveMembers = SetFactory.remove(LiveMembers, Member);
2868  }
2869  }
2870 
2871  // Check if the class changed.
2872  if (!MembersChanged)
2873  continue;
2874 
2875  MembersMapChanged = true;
2876 
2877  if (LiveMembers.isEmpty()) {
2878  // The class is dead now, we need to wipe it out of the members map...
2879  NewClassMembersMap = EMFactory.remove(NewClassMembersMap, Class);
2880 
2881  // ...and remove all of its constraints.
2882  removeDeadClass(Class);
2883  } else {
2884  // We need to change the members associated with the class.
2885  NewClassMembersMap =
2886  EMFactory.add(NewClassMembersMap, Class, LiveMembers);
2887  }
2888  }
2889 
2890  // 4. Update the state with new maps.
2891  //
2892  // Here we try to be humble and update a map only if it really changed.
2893  if (ClassMapChanged)
2894  State = State->set<ClassMap>(NewMap);
2895 
2896  if (MembersMapChanged)
2897  State = State->set<ClassMembers>(NewClassMembersMap);
2898 
2899  if (ConstraintMapChanged)
2900  State = State->set<ConstraintRange>(Constraints);
2901 
2902  if (DisequalitiesChanged)
2903  State = State->set<DisequalityMap>(Disequalities);
2904 
2905  assert(EquivalenceClass::isClassDataConsistent(State));
2906 
2907  return State;
2908 }
2909 
2910 RangeSet RangeConstraintManager::getRange(ProgramStateRef State,
2911  SymbolRef Sym) {
2912  return SymbolicRangeInferrer::inferRange(F, State, Sym);
2913 }
2914 
2915 ProgramStateRef RangeConstraintManager::setRange(ProgramStateRef State,
2916  SymbolRef Sym,
2917  RangeSet Range) {
2918  return ConstraintAssignor::assign(State, getSValBuilder(), F, Sym, Range);
2919 }
2920 
2921 //===------------------------------------------------------------------------===
2922 // assumeSymX methods: protected interface for RangeConstraintManager.
2923 //===------------------------------------------------------------------------===/
2924 
2925 // The syntax for ranges below is mathematical, using [x, y] for closed ranges
2926 // and (x, y) for open ranges. These ranges are modular, corresponding with
2927 // a common treatment of C integer overflow. This means that these methods
2928 // do not have to worry about overflow; RangeSet::Intersect can handle such a
2929 // "wraparound" range.
2930 // As an example, the range [UINT_MAX-1, 3) contains five values: UINT_MAX-1,
2931 // UINT_MAX, 0, 1, and 2.
2932 
2934 RangeConstraintManager::assumeSymNE(ProgramStateRef St, SymbolRef Sym,
2935  const llvm::APSInt &Int,
2936  const llvm::APSInt &Adjustment) {
2937  // Before we do any real work, see if the value can even show up.
2938  APSIntType AdjustmentType(Adjustment);
2939  if (AdjustmentType.testInRange(Int, true) != APSIntType::RTR_Within)
2940  return St;
2941 
2942  llvm::APSInt Point = AdjustmentType.convert(Int) - Adjustment;
2943  RangeSet New = getRange(St, Sym);
2944  New = F.deletePoint(New, Point);
2945 
2946  return setRange(St, Sym, New);
2947 }
2948 
2950 RangeConstraintManager::assumeSymEQ(ProgramStateRef St, SymbolRef Sym,
2951  const llvm::APSInt &Int,
2952  const llvm::APSInt &Adjustment) {
2953  // Before we do any real work, see if the value can even show up.
2954  APSIntType AdjustmentType(Adjustment);
2955  if (AdjustmentType.testInRange(Int, true) != APSIntType::RTR_Within)
2956  return nullptr;
2957 
2958  // [Int-Adjustment, Int-Adjustment]
2959  llvm::APSInt AdjInt = AdjustmentType.convert(Int) - Adjustment;
2960  RangeSet New = getRange(St, Sym);
2961  New = F.intersect(New, AdjInt);
2962 
2963  return setRange(St, Sym, New);
2964 }
2965 
2966 RangeSet RangeConstraintManager::getSymLTRange(ProgramStateRef St,
2967  SymbolRef Sym,
2968  const llvm::APSInt &Int,
2969  const llvm::APSInt &Adjustment) {
2970  // Before we do any real work, see if the value can even show up.
2971  APSIntType AdjustmentType(Adjustment);
2972  switch (AdjustmentType.testInRange(Int, true)) {
2973  case APSIntType::RTR_Below:
2974  return F.getEmptySet();
2976  break;
2977  case APSIntType::RTR_Above:
2978  return getRange(St, Sym);
2979  }
2980 
2981  // Special case for Int == Min. This is always false.
2982  llvm::APSInt ComparisonVal = AdjustmentType.convert(Int);
2983  llvm::APSInt Min = AdjustmentType.getMinValue();
2984  if (ComparisonVal == Min)
2985  return F.getEmptySet();
2986 
2987  llvm::APSInt Lower = Min - Adjustment;
2988  llvm::APSInt Upper = ComparisonVal - Adjustment;
2989  --Upper;
2990 
2991  RangeSet Result = getRange(St, Sym);
2992  return F.intersect(Result, Lower, Upper);
2993 }
2994 
2996 RangeConstraintManager::assumeSymLT(ProgramStateRef St, SymbolRef Sym,
2997  const llvm::APSInt &Int,
2998  const llvm::APSInt &Adjustment) {
2999  RangeSet New = getSymLTRange(St, Sym, Int, Adjustment);
3000  return setRange(St, Sym, New);
3001 }
3002 
3003 RangeSet RangeConstraintManager::getSymGTRange(ProgramStateRef St,
3004  SymbolRef Sym,
3005  const llvm::APSInt &Int,
3006  const llvm::APSInt &Adjustment) {
3007  // Before we do any real work, see if the value can even show up.
3008  APSIntType AdjustmentType(Adjustment);
3009  switch (AdjustmentType.testInRange(Int, true)) {
3010  case APSIntType::RTR_Below:
3011  return getRange(St, Sym);
3013  break;
3014  case APSIntType::RTR_Above:
3015  return F.getEmptySet();
3016  }
3017 
3018  // Special case for Int == Max. This is always false.
3019  llvm::APSInt ComparisonVal = AdjustmentType.convert(Int);
3020  llvm::APSInt Max = AdjustmentType.getMaxValue();
3021  if (ComparisonVal == Max)
3022  return F.getEmptySet();
3023 
3024  llvm::APSInt Lower = ComparisonVal - Adjustment;
3025  llvm::APSInt Upper = Max - Adjustment;
3026  ++Lower;
3027 
3028  RangeSet SymRange = getRange(St, Sym);
3029  return F.intersect(SymRange, Lower, Upper);
3030 }
3031 
3033 RangeConstraintManager::assumeSymGT(ProgramStateRef St, SymbolRef Sym,
3034  const llvm::APSInt &Int,
3035  const llvm::APSInt &Adjustment) {
3036  RangeSet New = getSymGTRange(St, Sym, Int, Adjustment);
3037  return setRange(St, Sym, New);
3038 }
3039 
3040 RangeSet RangeConstraintManager::getSymGERange(ProgramStateRef St,
3041  SymbolRef Sym,
3042  const llvm::APSInt &Int,
3043  const llvm::APSInt &Adjustment) {
3044  // Before we do any real work, see if the value can even show up.
3045  APSIntType AdjustmentType(Adjustment);
3046  switch (AdjustmentType.testInRange(Int, true)) {
3047  case APSIntType::RTR_Below:
3048  return getRange(St, Sym);
3050  break;
3051  case APSIntType::RTR_Above:
3052  return F.getEmptySet();
3053  }
3054 
3055  // Special case for Int == Min. This is always feasible.
3056  llvm::APSInt ComparisonVal = AdjustmentType.convert(Int);
3057  llvm::APSInt Min = AdjustmentType.getMinValue();
3058  if (ComparisonVal == Min)
3059  return getRange(St, Sym);
3060 
3061  llvm::APSInt Max = AdjustmentType.getMaxValue();
3062  llvm::APSInt Lower = ComparisonVal - Adjustment;
3063  llvm::APSInt Upper = Max - Adjustment;
3064 
3065  RangeSet SymRange = getRange(St, Sym);
3066  return F.intersect(SymRange, Lower, Upper);
3067 }
3068 
3070 RangeConstraintManager::assumeSymGE(ProgramStateRef St, SymbolRef Sym,
3071  const llvm::APSInt &Int,
3072  const llvm::APSInt &Adjustment) {
3073  RangeSet New = getSymGERange(St, Sym, Int, Adjustment);
3074  return setRange(St, Sym, New);
3075 }
3076 
3077 RangeSet
3078 RangeConstraintManager::getSymLERange(llvm::function_ref<RangeSet()> RS,
3079  const llvm::APSInt &Int,
3080  const llvm::APSInt &Adjustment) {
3081  // Before we do any real work, see if the value can even show up.
3082  APSIntType AdjustmentType(Adjustment);
3083  switch (AdjustmentType.testInRange(Int, true)) {
3084  case APSIntType::RTR_Below:
3085  return F.getEmptySet();
3087  break;
3088  case APSIntType::RTR_Above:
3089  return RS();
3090  }
3091 
3092  // Special case for Int == Max. This is always feasible.
3093  llvm::APSInt ComparisonVal = AdjustmentType.convert(Int);
3094  llvm::APSInt Max = AdjustmentType.getMaxValue();
3095  if (ComparisonVal == Max)
3096  return RS();
3097 
3098  llvm::APSInt Min = AdjustmentType.getMinValue();
3099  llvm::APSInt Lower = Min - Adjustment;
3100  llvm::APSInt Upper = ComparisonVal - Adjustment;
3101 
3102  RangeSet Default = RS();
3103  return F.intersect(Default, Lower, Upper);
3104 }
3105 
3106 RangeSet RangeConstraintManager::getSymLERange(ProgramStateRef St,
3107  SymbolRef Sym,
3108  const llvm::APSInt &Int,
3109  const llvm::APSInt &Adjustment) {
3110  return getSymLERange([&] { return getRange(St, Sym); }, Int, Adjustment);
3111 }
3112 
3114 RangeConstraintManager::assumeSymLE(ProgramStateRef St, SymbolRef Sym,
3115  const llvm::APSInt &Int,
3116  const llvm::APSInt &Adjustment) {
3117  RangeSet New = getSymLERange(St, Sym, Int, Adjustment);
3118  return setRange(St, Sym, New);
3119 }
3120 
3121 ProgramStateRef RangeConstraintManager::assumeSymWithinInclusiveRange(
3122  ProgramStateRef State, SymbolRef Sym, const llvm::APSInt &From,
3123  const llvm::APSInt &To, const llvm::APSInt &Adjustment) {
3124  RangeSet New = getSymGERange(State, Sym, From, Adjustment);
3125  if (New.isEmpty())
3126  return nullptr;
3127  RangeSet Out = getSymLERange([&] { return New; }, To, Adjustment);
3128  return setRange(State, Sym, Out);
3129 }
3130 
3131 ProgramStateRef RangeConstraintManager::assumeSymOutsideInclusiveRange(
3132  ProgramStateRef State, SymbolRef Sym, const llvm::APSInt &From,
3133  const llvm::APSInt &To, const llvm::APSInt &Adjustment) {
3134  RangeSet RangeLT = getSymLTRange(State, Sym, From, Adjustment);
3135  RangeSet RangeGT = getSymGTRange(State, Sym, To, Adjustment);
3136  RangeSet New(F.add(RangeLT, RangeGT));
3137  return setRange(State, Sym, New);
3138 }
3139 
3140 //===----------------------------------------------------------------------===//
3141 // Pretty-printing.
3142 //===----------------------------------------------------------------------===//
3143 
3144 void RangeConstraintManager::printJson(raw_ostream &Out, ProgramStateRef State,
3145  const char *NL, unsigned int Space,
3146  bool IsDot) const {
3147  printConstraints(Out, State, NL, Space, IsDot);
3148  printEquivalenceClasses(Out, State, NL, Space, IsDot);
3149  printDisequalities(Out, State, NL, Space, IsDot);
3150 }
3151 
3152 static std::string toString(const SymbolRef &Sym) {
3153  std::string S;
3154  llvm::raw_string_ostream O(S);
3155  Sym->dumpToStream(O);
3156  return O.str();
3157 }
3158 
3159 void RangeConstraintManager::printConstraints(raw_ostream &Out,
3161  const char *NL,
3162  unsigned int Space,
3163  bool IsDot) const {
3164  ConstraintRangeTy Constraints = State->get<ConstraintRange>();
3165 
3166  Indent(Out, Space, IsDot) << "\"constraints\": ";
3167  if (Constraints.isEmpty()) {
3168  Out << "null," << NL;
3169  return;
3170  }
3171 
3172  std::map<std::string, RangeSet> OrderedConstraints;
3173  for (std::pair<EquivalenceClass, RangeSet> P : Constraints) {
3174  SymbolSet ClassMembers = P.first.getClassMembers(State);
3175  for (const SymbolRef &ClassMember : ClassMembers) {
3176  bool insertion_took_place;
3177  std::tie(std::ignore, insertion_took_place) =
3178  OrderedConstraints.insert({toString(ClassMember), P.second});
3179  assert(insertion_took_place &&
3180  "two symbols should not have the same dump");
3181  }
3182  }
3183 
3184  ++Space;
3185  Out << '[' << NL;
3186  bool First = true;
3187  for (std::pair<std::string, RangeSet> P : OrderedConstraints) {
3188  if (First) {
3189  First = false;
3190  } else {
3191  Out << ',';
3192  Out << NL;
3193  }
3194  Indent(Out, Space, IsDot)
3195  << "{ \"symbol\": \"" << P.first << "\", \"range\": \"";
3196  P.second.dump(Out);
3197  Out << "\" }";
3198  }
3199  Out << NL;
3200 
3201  --Space;
3202  Indent(Out, Space, IsDot) << "]," << NL;
3203 }
3204 
3205 static std::string toString(ProgramStateRef State, EquivalenceClass Class) {
3206  SymbolSet ClassMembers = Class.getClassMembers(State);
3207  llvm::SmallVector<SymbolRef, 8> ClassMembersSorted(ClassMembers.begin(),
3208  ClassMembers.end());
3209  llvm::sort(ClassMembersSorted,
3210  [](const SymbolRef &LHS, const SymbolRef &RHS) {
3211  return toString(LHS) < toString(RHS);
3212  });
3213 
3214  bool FirstMember = true;
3215 
3216  std::string Str;
3217  llvm::raw_string_ostream Out(Str);
3218  Out << "[ ";
3219  for (SymbolRef ClassMember : ClassMembersSorted) {
3220  if (FirstMember)
3221  FirstMember = false;
3222  else
3223  Out << ", ";
3224  Out << "\"" << ClassMember << "\"";
3225  }
3226  Out << " ]";
3227  return Out.str();
3228 }
3229 
3230 void RangeConstraintManager::printEquivalenceClasses(raw_ostream &Out,
3232  const char *NL,
3233  unsigned int Space,
3234  bool IsDot) const {
3235  ClassMembersTy Members = State->get<ClassMembers>();
3236 
3237  Indent(Out, Space, IsDot) << "\"equivalence_classes\": ";
3238  if (Members.isEmpty()) {
3239  Out << "null," << NL;
3240  return;
3241  }
3242 
3243  std::set<std::string> MembersStr;
3244  for (std::pair<EquivalenceClass, SymbolSet> ClassToSymbolSet : Members)
3245  MembersStr.insert(toString(State, ClassToSymbolSet.first));
3246 
3247  ++Space;
3248  Out << '[' << NL;
3249  bool FirstClass = true;
3250  for (const std::string &Str : MembersStr) {
3251  if (FirstClass) {
3252  FirstClass = false;
3253  } else {
3254  Out << ',';
3255  Out << NL;
3256  }
3257  Indent(Out, Space, IsDot);
3258  Out << Str;
3259  }
3260  Out << NL;
3261 
3262  --Space;
3263  Indent(Out, Space, IsDot) << "]," << NL;
3264 }
3265 
3266 void RangeConstraintManager::printDisequalities(raw_ostream &Out,
3268  const char *NL,
3269  unsigned int Space,
3270  bool IsDot) const {
3271  DisequalityMapTy Disequalities = State->get<DisequalityMap>();
3272 
3273  Indent(Out, Space, IsDot) << "\"disequality_info\": ";
3274  if (Disequalities.isEmpty()) {
3275  Out << "null," << NL;
3276  return;
3277  }
3278 
3279  // Transform the disequality info to an ordered map of
3280  // [string -> (ordered set of strings)]
3281  using EqClassesStrTy = std::set<std::string>;
3282  using DisequalityInfoStrTy = std::map<std::string, EqClassesStrTy>;
3283  DisequalityInfoStrTy DisequalityInfoStr;
3284  for (std::pair<EquivalenceClass, ClassSet> ClassToDisEqSet : Disequalities) {
3285  EquivalenceClass Class = ClassToDisEqSet.first;
3286  ClassSet DisequalClasses = ClassToDisEqSet.second;
3287  EqClassesStrTy MembersStr;
3288  for (EquivalenceClass DisEqClass : DisequalClasses)
3289  MembersStr.insert(toString(State, DisEqClass));
3290  DisequalityInfoStr.insert({toString(State, Class), MembersStr});
3291  }
3292 
3293  ++Space;
3294  Out << '[' << NL;
3295  bool FirstClass = true;
3296  for (std::pair<std::string, EqClassesStrTy> ClassToDisEqSet :
3297  DisequalityInfoStr) {
3298  const std::string &Class = ClassToDisEqSet.first;
3299  if (FirstClass) {
3300  FirstClass = false;
3301  } else {
3302  Out << ',';
3303  Out << NL;
3304  }
3305  Indent(Out, Space, IsDot) << "{" << NL;
3306  unsigned int DisEqSpace = Space + 1;
3307  Indent(Out, DisEqSpace, IsDot) << "\"class\": ";
3308  Out << Class;
3309  const EqClassesStrTy &DisequalClasses = ClassToDisEqSet.second;
3310  if (!DisequalClasses.empty()) {
3311  Out << "," << NL;
3312  Indent(Out, DisEqSpace, IsDot) << "\"disequal_to\": [" << NL;
3313  unsigned int DisEqClassSpace = DisEqSpace + 1;
3314  Indent(Out, DisEqClassSpace, IsDot);
3315  bool FirstDisEqClass = true;
3316  for (const std::string &DisEqClass : DisequalClasses) {
3317  if (FirstDisEqClass) {
3318  FirstDisEqClass = false;
3319  } else {
3320  Out << ',' << NL;
3321  Indent(Out, DisEqClassSpace, IsDot);
3322  }
3323  Out << DisEqClass;
3324  }
3325  Out << "]" << NL;
3326  }
3327  Indent(Out, Space, IsDot) << "}";
3328  }
3329  Out << NL;
3330 
3331  --Space;
3332  Indent(Out, Space, IsDot) << "]," << NL;
3333 }
clang::ento::Loc::isLocType
static bool isLocType(QualType T)
Definition: SVals.h:335
toString
static std::string toString(const SymbolRef &Sym)
Definition: RangeConstraintManager.cpp:3152
clang::ento::RangeSet::Factory::unite
RangeSet unite(RangeSet LHS, RangeSet RHS)
Create a new set which is a union of two given ranges.
Definition: RangeConstraintManager.cpp:137
max
__DEVICE__ int max(int __a, int __b)
Definition: __clang_cuda_math.h:196
clang::ento::RangeSet::contains
bool contains(llvm::APSInt Point) const
Test whether the given point is contained by any of the ranges.
Definition: RangedConstraintManager.h:353
clang::ento::ObjKind::CF
@ CF
Indicates that the tracked object is a CF object.
clang::interp::APInt
llvm::APInt APInt
Definition: Integral.h:27
clang::index::SymbolKind::Class
@ Class
REGISTER_SET_FACTORY_WITH_PROGRAMSTATE
#define REGISTER_SET_FACTORY_WITH_PROGRAMSTATE(Name, Elem)
Declares an immutable set type Name and registers the factory for such sets in the program state,...
Definition: ProgramStateTrait.h:116
clang::ento::RangeSet::size
size_t size() const
Definition: RangedConstraintManager.h:117
string
string(SUBSTRING ${CMAKE_CURRENT_BINARY_DIR} 0 ${PATH_LIB_START} PATH_HEAD) string(SUBSTRING $
Definition: CMakeLists.txt:22
llvm::SmallVector
Definition: LLVM.h:38
clang::ento::ProgramStateManager::getSValBuilder
SValBuilder & getSValBuilder()
Definition: ProgramState.h:548
clang::ento::ProgramStateRef
IntrusiveRefCntPtr< const ProgramState > ProgramStateRef
Definition: ProgramState_Fwd.h:37
clang::QualType
A (possibly-)qualified type.
Definition: Type.h:675
clang::Decl::add
static void add(Kind k)
Definition: DeclBase.cpp:193
OperatorRelationsTable::getCmpOpCount
constexpr size_t getCmpOpCount() const
Definition: RangeConstraintManager.cpp:91
OperatorRelationsTable::getCmpOpStateForUnknownX2
TriStateKind getCmpOpStateForUnknownX2(BinaryOperatorKind CurrentOP) const
Definition: RangeConstraintManager.cpp:102
clang::ento::CreateRangeConstraintManager
std::unique_ptr< ConstraintManager > CreateRangeConstraintManager(ProgramStateManager &statemgr, ExprEngine *exprengine)
Definition: RangeConstraintManager.cpp:2168
clang::BinaryOperator::reverseComparisonOp
static Opcode reverseComparisonOp(Opcode Opc)
Definition: Expr.h:3925
clang::ento::RangeSet::isUnsigned
bool isUnsigned() const
Definition: RangeConstraintManager.cpp:356
OperatorRelationsTable::getCmpOpState
TriStateKind getCmpOpState(BinaryOperatorKind CurrentOP, BinaryOperatorKind QueriedOP) const
Definition: RangeConstraintManager.cpp:97
clang::ento::Range::dump
void dump(raw_ostream &OS) const
Definition: RangeConstraintManager.cpp:863
clang::ento::SymbolRef
const SymExpr * SymbolRef
Definition: SymExpr.h:110
llvm::Optional< bool >
clang::ComparisonCategoryType::First
@ First
clang::TypePropertyCache
The type-property cache.
Definition: Type.cpp:3833
clang::tooling::X
static ToolExecutorPluginRegistry::Add< AllTUsToolExecutorPlugin > X("all-TUs", "Runs FrontendActions on all TUs in the compilation database. " "Tool results are stored in memory.")
clang::ento::RangeSet::dump
void dump() const
Definition: RangeConstraintManager.cpp:873
clang::ento::RangeSet::Factory::negate
RangeSet negate(RangeSet What)
Negate the given range set.
Definition: RangeConstraintManager.cpp:610
clang::BinaryOperator::isRelationalOp
bool isRelationalOp() const
Definition: Expr.h:3901
clang::ento::APSIntType::isUnsigned
bool isUnsigned() const
Definition: APSIntType.h:31
OperatorRelationsTable
Definition: RangeConstraintManager.cpp:35
End
SourceLocation End
Definition: USRLocFinder.cpp:167
OperatorRelationsTable::Unknown
@ Unknown
Definition: RangeConstraintManager.cpp:44
clang::Type
The base class of the type hierarchy.
Definition: Type.h:1500
clang::ento::SymSymExpr
BinarySymExprImpl< const SymExpr *, const SymExpr *, SymExpr::Kind::SymSymExprKind > SymSymExpr
Represents a symbolic expression like 'x' + 'y'.
Definition: SymbolManager.h:415
clang::ento::RangeSet::getBitWidth
uint32_t getBitWidth() const
Definition: RangeConstraintManager.cpp:361
REGISTER_MAP_WITH_PROGRAMSTATE
#define REGISTER_MAP_WITH_PROGRAMSTATE(Name, Key, Value)
Declares an immutable map of type NameTy, suitable for placement into the ProgramState.
Definition: ProgramStateTrait.h:84
clang::StructuralEquivalenceKind::Default
@ Default
APSInt
llvm::APSInt APSInt
Definition: ByteCodeEmitter.cpp:19
JsonSupport.h
clang::Type::isReferenceType
bool isReferenceType() const
Definition: Type.h:6760
V
#define V(N, I)
Definition: ASTContext.h:3176
clang::prec::Unknown
@ Unknown
Definition: OperatorPrecedence.h:27
min
__DEVICE__ int min(int __a, int __b)
Definition: __clang_cuda_math.h:197
clang::BinaryOperator::isEqualityOp
bool isEqualityOp() const
Definition: Expr.h:3904
clang::Type::isSignedIntegerOrEnumerationType
bool isSignedIntegerOrEnumerationType() const
Determines whether this is an integer type that is signed or an enumeration types whose underlying ty...
Definition: Type.cpp:2039
clang::ento::RangeSet::Factory::intersect
RangeSet intersect(RangeSet LHS, RangeSet RHS)
Intersect the given range sets.
Definition: RangeConstraintManager.cpp:594
clang::ento::Range
A Range represents the closed range [from, to].
Definition: RangedConstraintManager.h:29
clang::ento::ConstraintMap
llvm::ImmutableMap< SymbolRef, RangeSet > ConstraintMap
Definition: RangedConstraintManager.h:404
clang::ento::RangeSet::getAPSIntType
APSIntType getAPSIntType() const
Definition: RangeConstraintManager.cpp:366
OperatorRelationsTable::TriStateKind
TriStateKind
Definition: RangeConstraintManager.cpp:41
clang::ento::RangeSet::operator=
RangeSet & operator=(const RangeSet &)=default
clang::ento::RangeSet::Factory
friend class Factory
Definition: RangedConstraintManager.h:401
clang::ento::SymExpr
Symbolic value.
Definition: SymExpr.h:29
clang::ento::Range::To
const llvm::APSInt & To() const
Definition: RangedConstraintManager.h:41
clang::ento::RangeSet::Factory::castTo
RangeSet castTo(RangeSet What, APSIntType Ty)
Performs promotions, truncations and conversions of the given set.
Definition: RangeConstraintManager.cpp:675
uintptr_t
__UINTPTR_TYPE__ uintptr_t
An unsigned integer type with the property that any valid pointer to void can be converted to this ty...
Definition: opencl-c-base.h:139
clang::interp::Zero
bool Zero(InterpState &S, CodePtr OpPC)
Definition: Interp.h:814
clang::ento::APSIntType::getBitWidth
uint32_t getBitWidth() const
Definition: APSIntType.h:30
clang::ento::RangeSet::operator!=
bool operator!=(const RangeSet &Other) const
Definition: RangedConstraintManager.h:378
clang::ento::RangeSet::getMinValue
const llvm::APSInt & getMinValue() const
Get the minimal value covered by the ranges in the set.
Definition: RangeConstraintManager.cpp:346
Base
clang::Type::isUnsignedIntegerOrEnumerationType
bool isUnsignedIntegerOrEnumerationType() const
Determines whether this is an integer type that is unsigned or an enumeration types whose underlying ...
Definition: Type.cpp:2089
clang::interp::Const
bool Const(InterpState &S, CodePtr OpPC, const T &Arg)
Definition: Interp.h:296
clang::ento::simplifyToSVal
SVal simplifyToSVal(ProgramStateRef State, SymbolRef Sym)
Try to simplify a given symbolic expression's associated SVal based on the constraints in State.
Definition: RangedConstraintManager.cpp:235
clang::ento::RangeSet::const_iterator
ImplType::const_iterator const_iterator
Definition: RangedConstraintManager.h:113
clang::BinaryOperator::negateComparisonOp
static Opcode negateComparisonOp(Opcode Opc)
Definition: Expr.h:3912
clang::ento::RangeSet::isEmpty
bool isEmpty() const
Definition: RangedConstraintManager.h:119
clang::ento::APSIntType
A record of the "type" of an APSInt, used for conversions.
Definition: APSIntType.h:19
clang::transformer::EditKind::Range
@ Range
clang::ento::RangeSet::Factory::deletePoint
RangeSet deletePoint(RangeSet From, const llvm::APSInt &Point)
Delete the given point from the range set.
Definition: RangeConstraintManager.cpp:848
clang::ento::RangeSet::getMaxValue
const llvm::APSInt & getMaxValue() const
Get the maximal value covered by the ranges in the set.
Definition: RangeConstraintManager.cpp:351
clang::ento::RangeSet::Profile
static void Profile(llvm::FoldingSetNodeID &ID, const RangeSet &RS)
Definition: RangedConstraintManager.h:321
clang::Indent
raw_ostream & Indent(raw_ostream &Out, const unsigned int Space, bool IsDot)
Definition: JsonSupport.h:21
clang::ento::IntSymExpr
BinarySymExprImpl< const llvm::APSInt &, const SymExpr *, SymExpr::Kind::IntSymExprKind > IntSymExpr
Represents a symbolic expression like 3 - 'x'.
Definition: SymbolManager.h:411
P
StringRef P
Definition: ASTMatchersInternal.cpp:563
swapIterators
void swapIterators(T &First, T &FirstEnd, T &Second, T &SecondEnd)
Definition: RangeConstraintManager.cpp:160
clang::ento::ProgramStateManager
Definition: ProgramState.h:498
clang::ento::SymIntExpr
BinarySymExprImpl< const SymExpr *, const llvm::APSInt &, SymExpr::Kind::SymIntExprKind > SymIntExpr
Represents a symbolic expression like 'x' + 3.
Definition: SymbolManager.h:407
clang::ento::RangeSet::begin
const_iterator begin() const
Definition: RangedConstraintManager.h:115
clang::ento::Range::From
const llvm::APSInt & From() const
Definition: RangedConstraintManager.h:40
clang::ento::APSIntType::apply
void apply(llvm::APSInt &Value) const
Convert a given APSInt, in place, to match this type.
Definition: APSIntType.h:37
Value
Value
Definition: UninitializedValues.cpp:102
clang::BinaryOperator::isComparisonOp
bool isComparisonOp() const
Definition: Expr.h:3907
clang::ento::APSIntType::RTR_Within
@ RTR_Within
Value is representable using this type.
Definition: APSIntType.h:78
clang::ento::Range::dump
void dump() const
Definition: RangeConstraintManager.cpp:866
State
LineState State
Definition: UnwrappedLineFormatter.cpp:1090
APSIntType.h
clang::ento::RangeSet
Definition: RangedConstraintManager.h:71
CONSTRAINT_DISPATCH
#define CONSTRAINT_DISPATCH(Id)
Definition: RangeConstraintManager.cpp:1925
clang::BinaryOperatorKind
BinaryOperatorKind
Definition: OperationKinds.h:25
clang::ento::ExprEngine
Definition: ExprEngine.h:123
ProgramState.h
reAssume
LLVM_NODISCARD ProgramStateRef reAssume(ProgramStateRef State, const RangeSet *Constraint, SVal TheValue)
Definition: RangeConstraintManager.cpp:2534
OperatorRelationsTable::getOpFromIndex
static BinaryOperatorKind getOpFromIndex(size_t Index)
Definition: RangeConstraintManager.cpp:93
clang::ento::APSIntType::RTR_Below
@ RTR_Below
Value is less than the minimum representable value.
Definition: APSIntType.h:77
clang::Builtin::ID
ID
Definition: Builtins.h:51
clang
Definition: CalledOnceCheck.h:17
clang::ComparisonCategoryType::Last
@ Last
clang::operator<
bool operator<(DeclarationName LHS, DeclarationName RHS)
Ordering on two declaration names.
Definition: DeclarationName.h:549
clang::prec::Equality
@ Equality
Definition: OperatorPrecedence.h:36
OperatorRelationsTable::True
@ True
Definition: RangeConstraintManager.cpp:43
clang::ento::RangeSet::RangeSet
RangeSet(const RangeSet &)=default
isTrivial
static bool isTrivial(ASTContext &Ctx, const Expr *E)
Checks if the expression is constant or does not have non-trivial function calls.
Definition: CGOpenMPRuntime.cpp:6493
DEFAULT_ASSIGN
#define DEFAULT_ASSIGN(Id)
Definition: RangeConstraintManager.cpp:1914
clang::ento::RangeSet::operator==
bool operator==(const RangeSet &Other) const
Definition: RangedConstraintManager.h:377
clang::ento::RangeSet::Factory::getRangeSet
RangeSet getRangeSet(Range Origin)
Create a new set with just one range.
ProgramStateTrait.h
RangedConstraintManager.h
clang::ento::APSIntType::RangeTestResultKind
RangeTestResultKind
Used to classify whether a value is representable using this type.
Definition: APSIntType.h:76
clang::ento::RangeSet::end
const_iterator end() const
Definition: RangedConstraintManager.h:116
clang::ento::RangeSet::Factory::add
RangeSet add(RangeSet LHS, RangeSet RHS)
Create a new set with all ranges from both LHS and RHS.
Definition: RangeConstraintManager.cpp:113
SValVisitor.h
clang::ento::APSIntType::RTR_Above
@ RTR_Above
Value is greater than the maximum representable value.
Definition: APSIntType.h:79
clang::ento::getConstraintMap
ConstraintMap getConstraintMap(ProgramStateRef State)
Definition: RangeConstraintManager.cpp:2173
llvm::IntrusiveRefCntPtr< const ProgramState >
clang::Type::isIntegralOrEnumerationType
bool isIntegralOrEnumerationType() const
Determine whether this type is an integral or enumeration type.
Definition: Type.h:7140
clang::ento::ObjKind::OS
@ OS
Indicates that the tracking object is a descendant of a referenced-counted OSObject,...
clang::ento::simplify
SymbolRef simplify(ProgramStateRef State, SymbolRef Sym)
Try to simplify a given symbolic expression based on the constraints in State.
Definition: RangedConstraintManager.cpp:240