clang  15.0.0git
RangedConstraintManager.h
Go to the documentation of this file.
1 //== RangedConstraintManager.h ----------------------------------*- 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 // Ranged constraint manager, built on SimpleConstraintManager.
10 //
11 //===----------------------------------------------------------------------===//
12 
13 #ifndef LLVM_CLANG_STATICANALYZER_CORE_PATHSENSITIVE_RANGEDCONSTRAINTMANAGER_H
14 #define LLVM_CLANG_STATICANALYZER_CORE_PATHSENSITIVE_RANGEDCONSTRAINTMANAGER_H
15 
19 #include "llvm/ADT/APSInt.h"
20 #include "llvm/Support/Allocator.h"
21 
22 namespace clang {
23 
24 namespace ento {
25 
26 /// A Range represents the closed range [from, to]. The caller must
27 /// guarantee that from <= to. Note that Range is immutable, so as not
28 /// to subvert RangeSet's immutability.
29 class Range {
30 public:
31  Range(const llvm::APSInt &From, const llvm::APSInt &To) : Impl(&From, &To) {
32  assert(From <= To);
33  }
34 
35  Range(const llvm::APSInt &Point) : Range(Point, Point) {}
36 
37  bool Includes(const llvm::APSInt &Point) const {
38  return From() <= Point && Point <= To();
39  }
40  const llvm::APSInt &From() const { return *Impl.first; }
41  const llvm::APSInt &To() const { return *Impl.second; }
42  const llvm::APSInt *getConcreteValue() const {
43  return &From() == &To() ? &From() : nullptr;
44  }
45 
46  void Profile(llvm::FoldingSetNodeID &ID) const {
47  ID.AddPointer(&From());
48  ID.AddPointer(&To());
49  }
50  void dump(raw_ostream &OS) const;
51  void dump() const;
52 
53  // In order to keep non-overlapping ranges sorted, we can compare only From
54  // points.
55  bool operator<(const Range &RHS) const { return From() < RHS.From(); }
56 
57  bool operator==(const Range &RHS) const { return Impl == RHS.Impl; }
58  bool operator!=(const Range &RHS) const { return !operator==(RHS); }
59 
60 private:
61  std::pair<const llvm::APSInt *, const llvm::APSInt *> Impl;
62 };
63 
64 /// @class RangeSet is a persistent set of non-overlapping ranges.
65 ///
66 /// New RangeSet objects can be ONLY produced by RangeSet::Factory object, which
67 /// also supports the most common operations performed on range sets.
68 ///
69 /// Empty set corresponds to an overly constrained symbol meaning that there
70 /// are no possible values for that symbol.
71 class RangeSet {
72 public:
73  class Factory;
74 
75 private:
76  // We use llvm::SmallVector as the underlying container for the following
77  // reasons:
78  //
79  // * Range sets are usually very simple, 1 or 2 ranges.
80  // That's why llvm::ImmutableSet is not perfect.
81  //
82  // * Ranges in sets are NOT overlapping, so it is natural to keep them
83  // sorted for efficient operations and queries. For this reason,
84  // llvm::SmallSet doesn't fit the requirements, it is not sorted when it
85  // is a vector.
86  //
87  // * Range set operations usually a bit harder than add/remove a range.
88  // Complex operations might do many of those for just one range set.
89  // Formerly it used to be llvm::ImmutableSet, which is inefficient for our
90  // purposes as we want to make these operations BOTH immutable AND
91  // efficient.
92  //
93  // * Iteration over ranges is widespread and a more cache-friendly
94  // structure is preferred.
96 
97  struct ContainerType : public ImplType, public llvm::FoldingSetNode {
98  void Profile(llvm::FoldingSetNodeID &ID) const {
99  for (const Range &It : *this) {
100  It.Profile(ID);
101  }
102  }
103  };
104  // This is a non-owning pointer to an actual container.
105  // The memory is fully managed by the factory and is alive as long as the
106  // factory itself is alive.
107  // It is a pointer as opposed to a reference, so we can easily reassign
108  // RangeSet objects.
109  using UnderlyingType = const ContainerType *;
110  UnderlyingType Impl;
111 
112 public:
113  using const_iterator = ImplType::const_iterator;
114 
115  const_iterator begin() const { return Impl->begin(); }
116  const_iterator end() const { return Impl->end(); }
117  size_t size() const { return Impl->size(); }
118 
119  bool isEmpty() const { return Impl->empty(); }
120 
121  class Factory {
122  public:
123  Factory(BasicValueFactory &BV) : ValueFactory(BV) {}
124 
125  /// Create a new set with all ranges from both LHS and RHS.
126  /// Possible intersections are not checked here.
127  ///
128  /// Complexity: O(N + M)
129  /// where N = size(LHS), M = size(RHS)
130  RangeSet add(RangeSet LHS, RangeSet RHS);
131  /// Create a new set with all ranges from the original set plus the new one.
132  /// Possible intersections are not checked here.
133  ///
134  /// Complexity: O(N)
135  /// where N = size(Original)
136  RangeSet add(RangeSet Original, Range Element);
137  /// Create a new set with all ranges from the original set plus the point.
138  /// Possible intersections are not checked here.
139  ///
140  /// Complexity: O(N)
141  /// where N = size(Original)
142  RangeSet add(RangeSet Original, const llvm::APSInt &Point);
143  /// Create a new set which is a union of two given ranges.
144  /// Possible intersections are not checked here.
145  ///
146  /// Complexity: O(N + M)
147  /// where N = size(LHS), M = size(RHS)
148  RangeSet unite(RangeSet LHS, RangeSet RHS);
149  /// Create a new set by uniting given range set with the given range.
150  /// All intersections and adjacent ranges are handled here.
151  ///
152  /// Complexity: O(N)
153  /// where N = size(Original)
154  RangeSet unite(RangeSet Original, Range Element);
155  /// Create a new set by uniting given range set with the given point.
156  /// All intersections and adjacent ranges are handled here.
157  ///
158  /// Complexity: O(N)
159  /// where N = size(Original)
160  RangeSet unite(RangeSet Original, llvm::APSInt Point);
161  /// Create a new set by uniting given range set with the given range
162  /// between points. All intersections and adjacent ranges are handled here.
163  ///
164  /// Complexity: O(N)
165  /// where N = size(Original)
166  RangeSet unite(RangeSet Original, llvm::APSInt From, llvm::APSInt To);
167 
168  RangeSet getEmptySet() { return &EmptySet; }
169 
170  /// Create a new set with just one range.
171  /// @{
172  RangeSet getRangeSet(Range Origin);
173  RangeSet getRangeSet(const llvm::APSInt &From, const llvm::APSInt &To) {
174  return getRangeSet(Range(From, To));
175  }
177  return getRangeSet(Origin, Origin);
178  }
179  /// @}
180 
181  /// Intersect the given range sets.
182  ///
183  /// Complexity: O(N + M)
184  /// where N = size(LHS), M = size(RHS)
186  /// Intersect the given set with the closed range [Lower, Upper].
187  ///
188  /// Unlike the Range type, this range uses modular arithmetic, corresponding
189  /// to the common treatment of C integer overflow. Thus, if the Lower bound
190  /// is greater than the Upper bound, the range is taken to wrap around. This
191  /// is equivalent to taking the intersection with the two ranges [Min,
192  /// Upper] and [Lower, Max], or, alternatively, /removing/ all integers
193  /// between Upper and Lower.
194  ///
195  /// Complexity: O(N)
196  /// where N = size(What)
198  /// Intersect the given range with the given point.
199  ///
200  /// The result can be either an empty set or a set containing the given
201  /// point depending on whether the point is in the range set.
202  ///
203  /// Complexity: O(logN)
204  /// where N = size(What)
206 
207  /// Delete the given point from the range set.
208  ///
209  /// Complexity: O(N)
210  /// where N = size(From)
211  RangeSet deletePoint(RangeSet From, const llvm::APSInt &Point);
212  /// Negate the given range set.
213  ///
214  /// Turn all [A, B] ranges to [-B, -A], when "-" is a C-like unary minus
215  /// operation under the values of the type.
216  ///
217  /// We also handle MIN because applying unary minus to MIN does not change
218  /// it.
219  /// Example 1:
220  /// char x = -128; // -128 is a MIN value in a range of 'char'
221  /// char y = -x; // y: -128
222  ///
223  /// Example 2:
224  /// unsigned char x = 0; // 0 is a MIN value in a range of 'unsigned char'
225  /// unsigned char y = -x; // y: 0
226  ///
227  /// And it makes us to separate the range
228  /// like [MIN, N] to [MIN, MIN] U [-N, MAX].
229  /// For instance, whole range is {-128..127} and subrange is [-128,-126],
230  /// thus [-128,-127,-126,...] negates to [-128,...,126,127].
231  ///
232  /// Negate restores disrupted ranges on bounds,
233  /// e.g. [MIN, B] => [MIN, MIN] U [-B, MAX] => [MIN, B].
234  ///
235  /// Negate is a self-inverse function, i.e. negate(negate(R)) == R.
236  ///
237  /// Complexity: O(N)
238  /// where N = size(What)
239  RangeSet negate(RangeSet What);
240  /// Performs promotions, truncations and conversions of the given set.
241  ///
242  /// This function is optimized for each of the six cast cases:
243  /// - noop
244  /// - conversion
245  /// - truncation
246  /// - truncation-conversion
247  /// - promotion
248  /// - promotion-conversion
249  ///
250  /// NOTE: This function is NOT self-inverse for truncations, because of
251  /// the higher bits loss:
252  /// - castTo(castTo(OrigRangeOfInt, char), int) != OrigRangeOfInt.
253  /// - castTo(castTo(OrigRangeOfChar, int), char) == OrigRangeOfChar.
254  /// But it is self-inverse for all the rest casts.
255  ///
256  /// Complexity:
257  /// - Noop O(1);
258  /// - Truncation O(N^2);
259  /// - Another case O(N);
260  /// where N = size(What)
262  RangeSet castTo(RangeSet What, QualType T);
263 
264  /// Return associated value factory.
265  BasicValueFactory &getValueFactory() const { return ValueFactory; }
266 
267  private:
268  /// Return a persistent version of the given container.
269  RangeSet makePersistent(ContainerType &&From);
270  /// Construct a new persistent version of the given container.
271  ContainerType *construct(ContainerType &&From);
272 
273  RangeSet intersect(const ContainerType &LHS, const ContainerType &RHS);
274  /// NOTE: This function relies on the fact that all values in the
275  /// containers are persistent (created via BasicValueFactory::getValue).
276  ContainerType unite(const ContainerType &LHS, const ContainerType &RHS);
277 
278  /// This is a helper function for `castTo` method. Implies not to be used
279  /// separately.
280  /// Performs a truncation case of a cast operation.
281  ContainerType truncateTo(RangeSet What, APSIntType Ty);
282 
283  /// This is a helper function for `castTo` method. Implies not to be used
284  /// separately.
285  /// Performs a conversion case and a promotion-conversion case for signeds
286  /// of a cast operation.
287  ContainerType convertTo(RangeSet What, APSIntType Ty);
288 
289  /// This is a helper function for `castTo` method. Implies not to be used
290  /// separately.
291  /// Performs a promotion for unsigneds only.
292  ContainerType promoteTo(RangeSet What, APSIntType Ty);
293 
294  // Many operations include producing new APSInt values and that's why
295  // we need this factory.
296  BasicValueFactory &ValueFactory;
297  // Allocator for all the created containers.
298  // Containers might own their own memory and that's why it is specific
299  // for the type, so it calls container destructors upon deletion.
300  llvm::SpecificBumpPtrAllocator<ContainerType> Arena;
301  // Usually we deal with the same ranges and range sets over and over.
302  // Here we track all created containers and try not to repeat ourselves.
303  llvm::FoldingSet<ContainerType> Cache;
304  static ContainerType EmptySet;
305  };
306 
307  RangeSet(const RangeSet &) = default;
308  RangeSet &operator=(const RangeSet &) = default;
309  RangeSet(RangeSet &&) = default;
310  RangeSet &operator=(RangeSet &&) = default;
311  ~RangeSet() = default;
312 
313  /// Construct a new RangeSet representing '{ [From, To] }'.
314  RangeSet(Factory &F, const llvm::APSInt &From, const llvm::APSInt &To)
315  : RangeSet(F.getRangeSet(From, To)) {}
316 
317  /// Construct a new RangeSet representing the given point as a range.
318  RangeSet(Factory &F, const llvm::APSInt &Point)
319  : RangeSet(F.getRangeSet(Point)) {}
320 
321  static void Profile(llvm::FoldingSetNodeID &ID, const RangeSet &RS) {
322  ID.AddPointer(RS.Impl);
323  }
324 
325  /// Profile - Generates a hash profile of this RangeSet for use
326  /// by FoldingSet.
327  void Profile(llvm::FoldingSetNodeID &ID) const { Profile(ID, *this); }
328 
329  /// getConcreteValue - If a symbol is constrained to equal a specific integer
330  /// constant then this method returns that value. Otherwise, it returns
331  /// NULL.
333  return Impl->size() == 1 ? begin()->getConcreteValue() : nullptr;
334  }
335 
336  /// Get the minimal value covered by the ranges in the set.
337  ///
338  /// Complexity: O(1)
339  const llvm::APSInt &getMinValue() const;
340  /// Get the maximal value covered by the ranges in the set.
341  ///
342  /// Complexity: O(1)
343  const llvm::APSInt &getMaxValue() const;
344 
345  bool isUnsigned() const;
346  uint32_t getBitWidth() const;
347  APSIntType getAPSIntType() const;
348 
349  /// Test whether the given point is contained by any of the ranges.
350  ///
351  /// Complexity: O(logN)
352  /// where N = size(this)
353  bool contains(llvm::APSInt Point) const { return containsImpl(Point); }
354 
355  bool containsZero() const {
356  APSIntType T{getMinValue()};
357  return contains(T.getZeroValue());
358  }
359 
360  /// Test if the range is the [0,0] range.
361  ///
362  /// Complexity: O(1)
363  bool encodesFalseRange() const {
364  const llvm::APSInt *Constant = getConcreteValue();
365  return Constant && Constant->isZero();
366  }
367 
368  /// Test if the range doesn't contain zero.
369  ///
370  /// Complexity: O(logN)
371  /// where N = size(this)
372  bool encodesTrueRange() const { return !containsZero(); }
373 
374  void dump(raw_ostream &OS) const;
375  void dump() const;
376 
377  bool operator==(const RangeSet &Other) const { return *Impl == *Other.Impl; }
378  bool operator!=(const RangeSet &Other) const { return !(*this == Other); }
379 
380 private:
381  /* implicit */ RangeSet(ContainerType *RawContainer) : Impl(RawContainer) {}
382  /* implicit */ RangeSet(UnderlyingType Ptr) : Impl(Ptr) {}
383 
384  /// Pin given points to the type represented by the current range set.
385  ///
386  /// This makes parameter points to be in-out parameters.
387  /// In order to maintain consistent types across all of the ranges in the set
388  /// and to keep all the operations to compare ONLY points of the same type, we
389  /// need to pin every point before any operation.
390  ///
391  /// @Returns true if the given points can be converted to the target type
392  /// without changing the values (i.e. trivially) and false otherwise.
393  /// @{
394  bool pin(llvm::APSInt &Lower, llvm::APSInt &Upper) const;
395  bool pin(llvm::APSInt &Point) const;
396  /// @}
397 
398  // This version of this function modifies its arguments (pins it).
399  bool containsImpl(llvm::APSInt &Point) const;
400 
401  friend class Factory;
402 };
403 
404 using ConstraintMap = llvm::ImmutableMap<SymbolRef, RangeSet>;
406 
408 public:
410  : SimpleConstraintManager(EE, SB) {}
411 
412  ~RangedConstraintManager() override;
413 
414  //===------------------------------------------------------------------===//
415  // Implementation for interface from SimpleConstraintManager.
416  //===------------------------------------------------------------------===//
417 
419  bool Assumption) override;
420 
422  const llvm::APSInt &From,
423  const llvm::APSInt &To,
424  bool InRange) override;
425 
427  bool Assumption) override;
428 
429 protected:
430  /// Assume a constraint between a symbolic expression and a concrete integer.
433  const llvm::APSInt &Int);
434 
435  //===------------------------------------------------------------------===//
436  // Interface that subclasses must implement.
437  //===------------------------------------------------------------------===//
438 
439  // Each of these is of the form "$Sym+Adj <> V", where "<>" is the comparison
440  // operation for the method being invoked.
441 
443  const llvm::APSInt &V,
444  const llvm::APSInt &Adjustment) = 0;
445 
447  const llvm::APSInt &V,
448  const llvm::APSInt &Adjustment) = 0;
449 
451  const llvm::APSInt &V,
452  const llvm::APSInt &Adjustment) = 0;
453 
455  const llvm::APSInt &V,
456  const llvm::APSInt &Adjustment) = 0;
457 
459  const llvm::APSInt &V,
460  const llvm::APSInt &Adjustment) = 0;
461 
463  const llvm::APSInt &V,
464  const llvm::APSInt &Adjustment) = 0;
465 
467  ProgramStateRef State, SymbolRef Sym, const llvm::APSInt &From,
468  const llvm::APSInt &To, const llvm::APSInt &Adjustment) = 0;
469 
471  ProgramStateRef State, SymbolRef Sym, const llvm::APSInt &From,
472  const llvm::APSInt &To, const llvm::APSInt &Adjustment) = 0;
473 
474  //===------------------------------------------------------------------===//
475  // Internal implementation.
476  //===------------------------------------------------------------------===//
477 private:
478  static void computeAdjustment(SymbolRef &Sym, llvm::APSInt &Adjustment);
479 };
480 
481 /// Try to simplify a given symbolic expression based on the constraints in
482 /// State. This is needed because the Environment bindings are not getting
483 /// updated when a new constraint is added to the State. If the symbol is
484 /// simplified to a non-symbol (e.g. to a constant) then the original symbol
485 /// is returned. We use this function in the family of assumeSymNE/EQ/LT/../GE
486 /// functions where we can work only with symbols. Use the other function
487 /// (simplifyToSVal) if you are interested in a simplification that may yield
488 /// a concrete constant value.
490 
491 /// Try to simplify a given symbolic expression's associated `SVal` based on the
492 /// constraints in State. This is very similar to `simplify`, but this function
493 /// always returns the simplified SVal. The simplified SVal might be a single
494 /// constant (i.e. `ConcreteInt`).
496 
497 } // namespace ento
498 } // namespace clang
499 
501 
502 #endif
clang::ento::RangeSet::Factory::unite
RangeSet unite(RangeSet LHS, RangeSet RHS)
Create a new set which is a union of two given ranges.
Definition: RangeConstraintManager.cpp:137
clang::ento::RangeSet::encodesTrueRange
bool encodesTrueRange() const
Test if the range doesn't contain zero.
Definition: RangedConstraintManager.h:372
clang::ento::RangeSet::contains
bool contains(llvm::APSInt Point) const
Test whether the given point is contained by any of the ranges.
Definition: RangedConstraintManager.h:353
clang::ento::BasicValueFactory
Definition: BasicValueFactory.h:113
clang::ento::RangeSet::size
size_t size() const
Definition: RangedConstraintManager.h:117
clang::ento::RangedConstraintManager::assumeSymGE
virtual ProgramStateRef assumeSymGE(ProgramStateRef State, SymbolRef Sym, const llvm::APSInt &V, const llvm::APSInt &Adjustment)=0
clang::ento::RangeSet::Factory::getEmptySet
RangeSet getEmptySet()
Definition: RangedConstraintManager.h:168
llvm::SmallVector
Definition: LLVM.h:38
clang::ento::RangeSet::~RangeSet
~RangeSet()=default
clang::ento::ProgramStateRef
IntrusiveRefCntPtr< const ProgramState > ProgramStateRef
Definition: ProgramState_Fwd.h:37
clang::QualType
A (possibly-)qualified type.
Definition: Type.h:731
clang::ento::Range::Includes
bool Includes(const llvm::APSInt &Point) const
Definition: RangedConstraintManager.h:37
clang::ento::RangeSet::isUnsigned
bool isUnsigned() const
Definition: RangeConstraintManager.cpp:356
clang::ento::SymbolRef
const SymExpr * SymbolRef
Definition: SymExpr.h:111
clang::ento::RangeSet::dump
void dump() const
Definition: RangeConstraintManager.cpp:873
clang::ento::RangeSet::Factory::negate
RangeSet negate(RangeSet What)
Negate the given range set.
Definition: RangeConstraintManager.cpp:610
clang::ento::RangeSet::Factory::getValueFactory
BasicValueFactory & getValueFactory() const
Return associated value factory.
Definition: RangedConstraintManager.h:265
REGISTER_FACTORY_WITH_PROGRAMSTATE
#define REGISTER_FACTORY_WITH_PROGRAMSTATE(Type)
Declares a factory for objects of type Type in the program state manager.
Definition: ProgramStateTrait.h:55
clang::ento::RangeSet::getBitWidth
uint32_t getBitWidth() const
Definition: RangeConstraintManager.cpp:361
APSInt
llvm::APSInt APSInt
Definition: ByteCodeEmitter.cpp:19
V
#define V(N, I)
Definition: ASTContext.h:3176
clang::ento::RangeSet::Factory::intersect
RangeSet intersect(RangeSet LHS, RangeSet RHS)
Intersect the given range sets.
Definition: RangeConstraintManager.cpp:594
clang::ento::Range
A Range represents the closed range [from, to].
Definition: RangedConstraintManager.h:29
clang::ento::ConstraintMap
llvm::ImmutableMap< SymbolRef, RangeSet > ConstraintMap
Definition: RangedConstraintManager.h:404
clang::ento::RangedConstraintManager
Definition: RangedConstraintManager.h:407
clang::ento::RangedConstraintManager::assumeSym
ProgramStateRef assumeSym(ProgramStateRef State, SymbolRef Sym, bool Assumption) override
Given a symbolic expression that can be reasoned about, assume that it is true/false and generate the...
Definition: RangedConstraintManager.cpp:23
clang::ento::RangeSet::getAPSIntType
APSIntType getAPSIntType() const
Definition: RangeConstraintManager.cpp:366
clang::ento::RangeSet::operator=
RangeSet & operator=(const RangeSet &)=default
clang::ento::SymExpr
Symbolic value.
Definition: SymExpr.h:29
clang::ento::Range::Profile
void Profile(llvm::FoldingSetNodeID &ID) const
Definition: RangedConstraintManager.h:46
clang::ento::Range::To
const llvm::APSInt & To() const
Definition: RangedConstraintManager.h:41
clang::ento::RangeSet::Factory::castTo
RangeSet castTo(RangeSet What, APSIntType Ty)
Performs promotions, truncations and conversions of the given set.
Definition: RangeConstraintManager.cpp:675
clang::ento::RangeSet::Profile
void Profile(llvm::FoldingSetNodeID &ID) const
Profile - Generates a hash profile of this RangeSet for use by FoldingSet.
Definition: RangedConstraintManager.h:327
clang::ento::Range::Range
Range(const llvm::APSInt &From, const llvm::APSInt &To)
Definition: RangedConstraintManager.h:31
clang::ento::RangedConstraintManager::assumeSymLT
virtual ProgramStateRef assumeSymLT(ProgramStateRef State, SymbolRef Sym, const llvm::APSInt &V, const llvm::APSInt &Adjustment)=0
clang::ento::RangedConstraintManager::assumeSymLE
virtual ProgramStateRef assumeSymLE(ProgramStateRef State, SymbolRef Sym, const llvm::APSInt &V, const llvm::APSInt &Adjustment)=0
clang::ento::RangedConstraintManager::RangedConstraintManager
RangedConstraintManager(ExprEngine *EE, SValBuilder &SB)
Definition: RangedConstraintManager.h:409
clang::ento::RangeSet::operator!=
bool operator!=(const RangeSet &Other) const
Definition: RangedConstraintManager.h:378
clang::ento::RangeSet::getMinValue
const llvm::APSInt & getMinValue() const
Get the minimal value covered by the ranges in the set.
Definition: RangeConstraintManager.cpp:346
clang::ento::simplifyToSVal
SVal simplifyToSVal(ProgramStateRef State, SymbolRef Sym)
Try to simplify a given symbolic expression's associated SVal based on the constraints in State.
Definition: RangedConstraintManager.cpp:235
clang::ento::RangeSet::const_iterator
ImplType::const_iterator const_iterator
Definition: RangedConstraintManager.h:113
clang::ento::RangeSet::isEmpty
bool isEmpty() const
Definition: RangedConstraintManager.h:119
clang::ento::RangeSet::encodesFalseRange
bool encodesFalseRange() const
Test if the range is the [0,0] range.
Definition: RangedConstraintManager.h:363
clang::ento::RangeSet::containsZero
bool containsZero() const
Definition: RangedConstraintManager.h:355
SimpleConstraintManager.h
clang::ento::APSIntType
A record of the "type" of an APSInt, used for conversions.
Definition: APSIntType.h:19
clang::interp::InRange
bool InRange(InterpState &S, CodePtr OpPC)
Definition: Interp.h:266
clang::ento::SValBuilder
Definition: SValBuilder.h:53
clang::ento::RangeSet::getMaxValue
const llvm::APSInt & getMaxValue() const
Get the maximal value covered by the ranges in the set.
Definition: RangeConstraintManager.cpp:351
clang::ento::RangeSet::Factory::deletePoint
RangeSet deletePoint(RangeSet From, const llvm::APSInt &Point)
Delete the given point from the range set.
Definition: RangeConstraintManager.cpp:848
clang::ento::RangeSet::Profile
static void Profile(llvm::FoldingSetNodeID &ID, const RangeSet &RS)
Definition: RangedConstraintManager.h:321
clang::ento::RangedConstraintManager::assumeSymGT
virtual ProgramStateRef assumeSymGT(ProgramStateRef State, SymbolRef Sym, const llvm::APSInt &V, const llvm::APSInt &Adjustment)=0
clang::ento::RangedConstraintManager::assumeSymRel
virtual ProgramStateRef assumeSymRel(ProgramStateRef State, SymbolRef Sym, BinaryOperator::Opcode op, const llvm::APSInt &Int)
Assume a constraint between a symbolic expression and a concrete integer.
Definition: RangedConstraintManager.cpp:152
clang::ento::RangedConstraintManager::assumeSymOutsideInclusiveRange
virtual ProgramStateRef assumeSymOutsideInclusiveRange(ProgramStateRef State, SymbolRef Sym, const llvm::APSInt &From, const llvm::APSInt &To, const llvm::APSInt &Adjustment)=0
Cache
TypePropertyCache< Private > Cache
Definition: Type.cpp:3885
clang::ento::Range::operator==
bool operator==(const Range &RHS) const
Definition: RangedConstraintManager.h:57
clang::ento::RangeSet::begin
const_iterator begin() const
Definition: RangedConstraintManager.h:115
clang::ento::RangeSet::Factory
Definition: RangedConstraintManager.h:121
clang::ento::Range::From
const llvm::APSInt & From() const
Definition: RangedConstraintManager.h:40
clang::ento::Range::dump
void dump() const
Definition: RangeConstraintManager.cpp:866
State
LineState State
Definition: UnwrappedLineFormatter.cpp:1126
clang::ento::RangedConstraintManager::assumeSymUnsupported
ProgramStateRef assumeSymUnsupported(ProgramStateRef State, SymbolRef Sym, bool Assumption) override
Given a symbolic expression that cannot be reasoned about, assume that it is zero/nonzero and add it ...
Definition: RangedConstraintManager.cpp:133
clang::ento::RangeSet
Definition: RangedConstraintManager.h:71
clang::BinaryOperatorKind
BinaryOperatorKind
Definition: OperationKinds.h:25
clang::ento::RangeSet::RangeSet
RangeSet(Factory &F, const llvm::APSInt &From, const llvm::APSInt &To)
Construct a new RangeSet representing '{ [From, To] }'.
Definition: RangedConstraintManager.h:314
clang::ento::Range::getConcreteValue
const llvm::APSInt * getConcreteValue() const
Definition: RangedConstraintManager.h:42
clang::ento::ExprEngine
Definition: ExprEngine.h:123
ProgramState.h
clang::ento::Range::operator!=
bool operator!=(const Range &RHS) const
Definition: RangedConstraintManager.h:58
clang::ento::RangedConstraintManager::assumeSymWithinInclusiveRange
virtual ProgramStateRef assumeSymWithinInclusiveRange(ProgramStateRef State, SymbolRef Sym, const llvm::APSInt &From, const llvm::APSInt &To, const llvm::APSInt &Adjustment)=0
clang::Builtin::ID
ID
Definition: Builtins.h:52
clang
Definition: CalledOnceCheck.h:17
clang::ento::RangedConstraintManager::~RangedConstraintManager
~RangedConstraintManager() override
Definition: RangedConstraintManager.cpp:21
clang::ento::RangeSet::Factory::Factory
Factory(BasicValueFactory &BV)
Definition: RangedConstraintManager.h:123
clang::ento::RangedConstraintManager::assumeSymInclusiveRange
ProgramStateRef assumeSymInclusiveRange(ProgramStateRef State, SymbolRef Sym, const llvm::APSInt &From, const llvm::APSInt &To, bool InRange) override
Given a symbolic expression within the range [From, To], assume that it is true/false and generate th...
Definition: RangedConstraintManager.cpp:101
clang::ento::Range::operator<
bool operator<(const Range &RHS) const
Definition: RangedConstraintManager.h:55
clang::ento::RangeSet::RangeSet
RangeSet(const RangeSet &)=default
clang::ento::RangedConstraintManager::assumeSymEQ
virtual ProgramStateRef assumeSymEQ(ProgramStateRef State, SymbolRef Sym, const llvm::APSInt &V, const llvm::APSInt &Adjustment)=0
clang::ento::RangeSet::RangeSet
RangeSet(Factory &F, const llvm::APSInt &Point)
Construct a new RangeSet representing the given point as a range.
Definition: RangedConstraintManager.h:318
clang::ento::SimpleConstraintManager
Definition: SimpleConstraintManager.h:23
clang::ento::Range::Range
Range(const llvm::APSInt &Point)
Definition: RangedConstraintManager.h:35
clang::ento::RangeSet::operator==
bool operator==(const RangeSet &Other) const
Definition: RangedConstraintManager.h:377
clang::ento::RangeSet::Factory::getRangeSet
RangeSet getRangeSet(Range Origin)
Create a new set with just one range.
ProgramStateTrait.h
clang::ento::RangeSet::end
const_iterator end() const
Definition: RangedConstraintManager.h:116
clang::ento::RangeSet::Factory::add
RangeSet add(RangeSet LHS, RangeSet RHS)
Create a new set with all ranges from both LHS and RHS.
Definition: RangeConstraintManager.cpp:113
clang::ento::RangeSet::getConcreteValue
const llvm::APSInt * getConcreteValue() const
getConcreteValue - If a symbol is constrained to equal a specific integer constant then this method r...
Definition: RangedConstraintManager.h:332
clang::ento::RangedConstraintManager::assumeSymNE
virtual ProgramStateRef assumeSymNE(ProgramStateRef State, SymbolRef Sym, const llvm::APSInt &V, const llvm::APSInt &Adjustment)=0
clang::ento::RangeSet::Factory::getRangeSet
RangeSet getRangeSet(const llvm::APSInt &Origin)
Definition: RangedConstraintManager.h:176
clang::ento::getConstraintMap
ConstraintMap getConstraintMap(ProgramStateRef State)
Definition: RangeConstraintManager.cpp:2178
llvm::IntrusiveRefCntPtr
Definition: LLVM.h:47
clang::ento::RangeSet::Factory::getRangeSet
RangeSet getRangeSet(const llvm::APSInt &From, const llvm::APSInt &To)
Definition: RangedConstraintManager.h:173
clang::ento::simplify
SymbolRef simplify(ProgramStateRef State, SymbolRef Sym)
Try to simplify a given symbolic expression based on the constraints in State.
Definition: RangedConstraintManager.cpp:240