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_LIB_STATICANALYZER_CORE_RANGEDCONSTRAINTMANAGER_H 14 #define LLVM_CLANG_LIB_STATICANALYZER_CORE_RANGEDCONSTRAINTMANAGER_H 15 16 #include "clang/StaticAnalyzer/Core/PathSensitive/ProgramState.h" 17 #include "clang/StaticAnalyzer/Core/PathSensitive/ProgramStateTrait.h" 18 #include "clang/StaticAnalyzer/Core/PathSensitive/SimpleConstraintManager.h" 19 20 namespace clang { 21 22 namespace ento { 23 24 /// A Range represents the closed range [from, to]. The caller must 25 /// guarantee that from <= to. Note that Range is immutable, so as not 26 /// to subvert RangeSet's immutability. 27 class Range : public std::pair<const llvm::APSInt *, const llvm::APSInt *> { 28 public: 29 Range(const llvm::APSInt &from, const llvm::APSInt &to) 30 : std::pair<const llvm::APSInt *, const llvm::APSInt *>(&from, &to) { 31 assert(from <= to); 32 } 33 34 Range(const llvm::APSInt &point) 35 : std::pair<const llvm::APSInt *, const llvm::APSInt *>(&point, &point) {} 36 37 bool Includes(const llvm::APSInt &v) const { 38 return *first <= v && v <= *second; 39 } 40 const llvm::APSInt &From() const { return *first; } 41 const llvm::APSInt &To() const { return *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 }; 51 52 class RangeTrait : public llvm::ImutContainerInfo<Range> { 53 public: 54 // When comparing if one Range is less than another, we should compare 55 // the actual APSInt values instead of their pointers. This keeps the order 56 // consistent (instead of comparing by pointer values) and can potentially 57 // be used to speed up some of the operations in RangeSet. 58 static inline bool isLess(key_type_ref lhs, key_type_ref rhs) { 59 return *lhs.first < *rhs.first || 60 (!(*rhs.first < *lhs.first) && *lhs.second < *rhs.second); 61 } 62 }; 63 64 /// RangeSet contains a set of ranges. If the set is empty, then 65 /// there the value of a symbol is overly constrained and there are no 66 /// possible values for that symbol. 67 class RangeSet { 68 typedef llvm::ImmutableSet<Range, RangeTrait> PrimRangeSet; 69 PrimRangeSet ranges; // no need to make const, since it is an 70 // ImmutableSet - this allows default operator= 71 // to work. 72 public: 73 typedef PrimRangeSet::Factory Factory; 74 typedef PrimRangeSet::iterator iterator; 75 76 RangeSet(PrimRangeSet RS) : ranges(RS) {} 77 78 /// Create a new set with all ranges of this set and RS. 79 /// Possible intersections are not checked here. 80 RangeSet addRange(Factory &F, const RangeSet &RS) { 81 PrimRangeSet Ranges(RS.ranges); 82 for (const auto &range : ranges) 83 Ranges = F.add(Ranges, range); 84 return RangeSet(Ranges); 85 } 86 87 iterator begin() const { return ranges.begin(); } 88 iterator end() const { return ranges.end(); } 89 90 bool isEmpty() const { return ranges.isEmpty(); } 91 92 /// Construct a new RangeSet representing '{ [from, to] }'. 93 RangeSet(Factory &F, const llvm::APSInt &from, const llvm::APSInt &to) 94 : ranges(F.add(F.getEmptySet(), Range(from, to))) {} 95 96 /// Construct a new RangeSet representing the given point as a range. 97 RangeSet(Factory &F, const llvm::APSInt &point) : RangeSet(F, point, point) {} 98 99 /// Profile - Generates a hash profile of this RangeSet for use 100 /// by FoldingSet. 101 void Profile(llvm::FoldingSetNodeID &ID) const { ranges.Profile(ID); } 102 103 /// getConcreteValue - If a symbol is contrained to equal a specific integer 104 /// constant then this method returns that value. Otherwise, it returns 105 /// NULL. 106 const llvm::APSInt *getConcreteValue() const { 107 return ranges.isSingleton() ? ranges.begin()->getConcreteValue() : nullptr; 108 } 109 110 /// Get a minimal value covered by the ranges in the set 111 const llvm::APSInt &getMinValue() const; 112 /// Get a maximal value covered by the ranges in the set 113 const llvm::APSInt &getMaxValue() const; 114 115 private: 116 void IntersectInRange(BasicValueFactory &BV, Factory &F, 117 const llvm::APSInt &Lower, const llvm::APSInt &Upper, 118 PrimRangeSet &newRanges, PrimRangeSet::iterator &i, 119 PrimRangeSet::iterator &e) const; 120 121 bool pin(llvm::APSInt &Lower, llvm::APSInt &Upper) const; 122 123 public: 124 RangeSet Intersect(BasicValueFactory &BV, Factory &F, llvm::APSInt Lower, 125 llvm::APSInt Upper) const; 126 RangeSet Intersect(BasicValueFactory &BV, Factory &F, 127 const RangeSet &Other) const; 128 RangeSet Negate(BasicValueFactory &BV, Factory &F) const; 129 RangeSet Delete(BasicValueFactory &BV, Factory &F, 130 const llvm::APSInt &Point) const; 131 132 void print(raw_ostream &os) const; 133 134 bool operator==(const RangeSet &other) const { 135 return ranges == other.ranges; 136 } 137 }; 138 139 using ConstraintMap = llvm::ImmutableMap<SymbolRef, RangeSet>; 140 ConstraintMap getConstraintMap(ProgramStateRef State); 141 142 class RangedConstraintManager : public SimpleConstraintManager { 143 public: 144 RangedConstraintManager(ExprEngine *EE, SValBuilder &SB) 145 : SimpleConstraintManager(EE, SB) {} 146 147 ~RangedConstraintManager() override; 148 149 //===------------------------------------------------------------------===// 150 // Implementation for interface from SimpleConstraintManager. 151 //===------------------------------------------------------------------===// 152 153 ProgramStateRef assumeSym(ProgramStateRef State, SymbolRef Sym, 154 bool Assumption) override; 155 156 ProgramStateRef assumeSymInclusiveRange(ProgramStateRef State, SymbolRef Sym, 157 const llvm::APSInt &From, 158 const llvm::APSInt &To, 159 bool InRange) override; 160 161 ProgramStateRef assumeSymUnsupported(ProgramStateRef State, SymbolRef Sym, 162 bool Assumption) override; 163 164 protected: 165 /// Assume a constraint between a symbolic expression and a concrete integer. 166 virtual ProgramStateRef assumeSymRel(ProgramStateRef State, SymbolRef Sym, 167 BinaryOperator::Opcode op, 168 const llvm::APSInt &Int); 169 170 //===------------------------------------------------------------------===// 171 // Interface that subclasses must implement. 172 //===------------------------------------------------------------------===// 173 174 // Each of these is of the form "$Sym+Adj <> V", where "<>" is the comparison 175 // operation for the method being invoked. 176 177 virtual ProgramStateRef assumeSymNE(ProgramStateRef State, SymbolRef Sym, 178 const llvm::APSInt &V, 179 const llvm::APSInt &Adjustment) = 0; 180 181 virtual ProgramStateRef assumeSymEQ(ProgramStateRef State, SymbolRef Sym, 182 const llvm::APSInt &V, 183 const llvm::APSInt &Adjustment) = 0; 184 185 virtual ProgramStateRef assumeSymLT(ProgramStateRef State, SymbolRef Sym, 186 const llvm::APSInt &V, 187 const llvm::APSInt &Adjustment) = 0; 188 189 virtual ProgramStateRef assumeSymGT(ProgramStateRef State, SymbolRef Sym, 190 const llvm::APSInt &V, 191 const llvm::APSInt &Adjustment) = 0; 192 193 virtual ProgramStateRef assumeSymLE(ProgramStateRef State, SymbolRef Sym, 194 const llvm::APSInt &V, 195 const llvm::APSInt &Adjustment) = 0; 196 197 virtual ProgramStateRef assumeSymGE(ProgramStateRef State, SymbolRef Sym, 198 const llvm::APSInt &V, 199 const llvm::APSInt &Adjustment) = 0; 200 201 virtual ProgramStateRef assumeSymWithinInclusiveRange( 202 ProgramStateRef State, SymbolRef Sym, const llvm::APSInt &From, 203 const llvm::APSInt &To, const llvm::APSInt &Adjustment) = 0; 204 205 virtual ProgramStateRef assumeSymOutsideInclusiveRange( 206 ProgramStateRef State, SymbolRef Sym, const llvm::APSInt &From, 207 const llvm::APSInt &To, const llvm::APSInt &Adjustment) = 0; 208 209 //===------------------------------------------------------------------===// 210 // Internal implementation. 211 //===------------------------------------------------------------------===// 212 private: 213 static void computeAdjustment(SymbolRef &Sym, llvm::APSInt &Adjustment); 214 }; 215 216 } // namespace ento 217 } // namespace clang 218 219 REGISTER_FACTORY_WITH_PROGRAMSTATE(ConstraintMap) 220 221 #endif 222