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