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 #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: Range(const llvm::APSInt & From,const llvm::APSInt & To)31 Range(const llvm::APSInt &From, const llvm::APSInt &To) : Impl(&From, &To) { 32 assert(From <= To); 33 } 34 Range(const llvm::APSInt & Point)35 Range(const llvm::APSInt &Point) : Range(Point, Point) {} 36 Includes(const llvm::APSInt & Point)37 bool Includes(const llvm::APSInt &Point) const { 38 return From() <= Point && Point <= To(); 39 } From()40 const llvm::APSInt &From() const { return *Impl.first; } To()41 const llvm::APSInt &To() const { return *Impl.second; } getConcreteValue()42 const llvm::APSInt *getConcreteValue() const { 43 return &From() == &To() ? &From() : nullptr; 44 } 45 Profile(llvm::FoldingSetNodeID & ID)46 void Profile(llvm::FoldingSetNodeID &ID) const { 47 ID.AddPointer(&From()); 48 ID.AddPointer(&To()); 49 } 50 void dump(raw_ostream &OS) const; 51 52 // In order to keep non-overlapping ranges sorted, we can compare only From 53 // points. 54 bool operator<(const Range &RHS) const { return From() < RHS.From(); } 55 56 bool operator==(const Range &RHS) const { return Impl == RHS.Impl; } 57 bool operator!=(const Range &RHS) const { return !operator==(RHS); } 58 59 private: 60 std::pair<const llvm::APSInt *, const llvm::APSInt *> Impl; 61 }; 62 63 /// @class RangeSet is a persistent set of non-overlapping ranges. 64 /// 65 /// New RangeSet objects can be ONLY produced by RangeSet::Factory object, which 66 /// also supports the most common operations performed on range sets. 67 /// 68 /// Empty set corresponds to an overly constrained symbol meaning that there 69 /// are no possible values for that symbol. 70 class RangeSet { 71 public: 72 class Factory; 73 74 private: 75 // We use llvm::SmallVector as the underlying container for the following 76 // reasons: 77 // 78 // * Range sets are usually very simple, 1 or 2 ranges. 79 // That's why llvm::ImmutableSet is not perfect. 80 // 81 // * Ranges in sets are NOT overlapping, so it is natural to keep them 82 // sorted for efficient operations and queries. For this reason, 83 // llvm::SmallSet doesn't fit the requirements, it is not sorted when it 84 // is a vector. 85 // 86 // * Range set operations usually a bit harder than add/remove a range. 87 // Complex operations might do many of those for just one range set. 88 // Formerly it used to be llvm::ImmutableSet, which is inefficient for our 89 // purposes as we want to make these operations BOTH immutable AND 90 // efficient. 91 // 92 // * Iteration over ranges is widespread and a more cache-friendly 93 // structure is preferred. 94 using ImplType = llvm::SmallVector<Range, 4>; 95 96 struct ContainerType : public ImplType, public llvm::FoldingSetNode { ProfileContainerType97 void Profile(llvm::FoldingSetNodeID &ID) const { 98 for (const Range &It : *this) { 99 It.Profile(ID); 100 } 101 } 102 }; 103 // This is a non-owning pointer to an actual container. 104 // The memory is fully managed by the factory and is alive as long as the 105 // factory itself is alive. 106 // It is a pointer as opposed to a reference, so we can easily reassign 107 // RangeSet objects. 108 using UnderlyingType = const ContainerType *; 109 UnderlyingType Impl; 110 111 public: 112 using const_iterator = ImplType::const_iterator; 113 begin()114 const_iterator begin() const { return Impl->begin(); } end()115 const_iterator end() const { return Impl->end(); } size()116 size_t size() const { return Impl->size(); } 117 isEmpty()118 bool isEmpty() const { return Impl->empty(); } 119 120 class Factory { 121 public: Factory(BasicValueFactory & BV)122 Factory(BasicValueFactory &BV) : ValueFactory(BV) {} 123 124 /// Create a new set with all ranges from both LHS and RHS. 125 /// Possible intersections are not checked here. 126 /// 127 /// Complexity: O(N + M) 128 /// where N = size(LHS), M = size(RHS) 129 RangeSet add(RangeSet LHS, RangeSet RHS); 130 /// Create a new set with all ranges from the original set plus the new one. 131 /// Possible intersections are not checked here. 132 /// 133 /// Complexity: O(N) 134 /// where N = size(Original) 135 RangeSet add(RangeSet Original, Range Element); 136 /// Create a new set with all ranges from the original set plus the point. 137 /// Possible intersections are not checked here. 138 /// 139 /// Complexity: O(N) 140 /// where N = size(Original) 141 RangeSet add(RangeSet Original, const llvm::APSInt &Point); 142 getEmptySet()143 RangeSet getEmptySet() { return &EmptySet; } 144 145 /// Create a new set with just one range. 146 /// @{ 147 RangeSet getRangeSet(Range Origin); getRangeSet(const llvm::APSInt & From,const llvm::APSInt & To)148 RangeSet getRangeSet(const llvm::APSInt &From, const llvm::APSInt &To) { 149 return getRangeSet(Range(From, To)); 150 } getRangeSet(const llvm::APSInt & Origin)151 RangeSet getRangeSet(const llvm::APSInt &Origin) { 152 return getRangeSet(Origin, Origin); 153 } 154 /// @} 155 156 /// Intersect the given range sets. 157 /// 158 /// Complexity: O(N + M) 159 /// where N = size(LHS), M = size(RHS) 160 RangeSet intersect(RangeSet LHS, RangeSet RHS); 161 /// Intersect the given set with the closed range [Lower, Upper]. 162 /// 163 /// Unlike the Range type, this range uses modular arithmetic, corresponding 164 /// to the common treatment of C integer overflow. Thus, if the Lower bound 165 /// is greater than the Upper bound, the range is taken to wrap around. This 166 /// is equivalent to taking the intersection with the two ranges [Min, 167 /// Upper] and [Lower, Max], or, alternatively, /removing/ all integers 168 /// between Upper and Lower. 169 /// 170 /// Complexity: O(N) 171 /// where N = size(What) 172 RangeSet intersect(RangeSet What, llvm::APSInt Lower, llvm::APSInt Upper); 173 /// Intersect the given range with the given point. 174 /// 175 /// The result can be either an empty set or a set containing the given 176 /// point depending on whether the point is in the range set. 177 /// 178 /// Complexity: O(logN) 179 /// where N = size(What) 180 RangeSet intersect(RangeSet What, llvm::APSInt Point); 181 182 /// Delete the given point from the range set. 183 /// 184 /// Complexity: O(N) 185 /// where N = size(From) 186 RangeSet deletePoint(RangeSet From, const llvm::APSInt &Point); 187 /// Negate the given range set. 188 /// 189 /// Turn all [A, B] ranges to [-B, -A], when "-" is a C-like unary minus 190 /// operation under the values of the type. 191 /// 192 /// We also handle MIN because applying unary minus to MIN does not change 193 /// it. 194 /// Example 1: 195 /// char x = -128; // -128 is a MIN value in a range of 'char' 196 /// char y = -x; // y: -128 197 /// 198 /// Example 2: 199 /// unsigned char x = 0; // 0 is a MIN value in a range of 'unsigned char' 200 /// unsigned char y = -x; // y: 0 201 /// 202 /// And it makes us to separate the range 203 /// like [MIN, N] to [MIN, MIN] U [-N, MAX]. 204 /// For instance, whole range is {-128..127} and subrange is [-128,-126], 205 /// thus [-128,-127,-126,...] negates to [-128,...,126,127]. 206 /// 207 /// Negate restores disrupted ranges on bounds, 208 /// e.g. [MIN, B] => [MIN, MIN] U [-B, MAX] => [MIN, B]. 209 /// 210 /// Negate is a self-inverse function, i.e. negate(negate(R)) == R. 211 /// 212 /// Complexity: O(N) 213 /// where N = size(What) 214 RangeSet negate(RangeSet What); 215 216 /// Return associated value factory. getValueFactory()217 BasicValueFactory &getValueFactory() const { return ValueFactory; } 218 219 private: 220 /// Return a persistent version of the given container. 221 RangeSet makePersistent(ContainerType &&From); 222 /// Construct a new persistent version of the given container. 223 ContainerType *construct(ContainerType &&From); 224 225 RangeSet intersect(const ContainerType &LHS, const ContainerType &RHS); 226 227 // Many operations include producing new APSInt values and that's why 228 // we need this factory. 229 BasicValueFactory &ValueFactory; 230 // Allocator for all the created containers. 231 // Containers might own their own memory and that's why it is specific 232 // for the type, so it calls container destructors upon deletion. 233 llvm::SpecificBumpPtrAllocator<ContainerType> Arena; 234 // Usually we deal with the same ranges and range sets over and over. 235 // Here we track all created containers and try not to repeat ourselves. 236 llvm::FoldingSet<ContainerType> Cache; 237 static ContainerType EmptySet; 238 }; 239 240 RangeSet(const RangeSet &) = default; 241 RangeSet &operator=(const RangeSet &) = default; 242 RangeSet(RangeSet &&) = default; 243 RangeSet &operator=(RangeSet &&) = default; 244 ~RangeSet() = default; 245 246 /// Construct a new RangeSet representing '{ [From, To] }'. RangeSet(Factory & F,const llvm::APSInt & From,const llvm::APSInt & To)247 RangeSet(Factory &F, const llvm::APSInt &From, const llvm::APSInt &To) 248 : RangeSet(F.getRangeSet(From, To)) {} 249 250 /// Construct a new RangeSet representing the given point as a range. RangeSet(Factory & F,const llvm::APSInt & Point)251 RangeSet(Factory &F, const llvm::APSInt &Point) 252 : RangeSet(F.getRangeSet(Point)) {} 253 Profile(llvm::FoldingSetNodeID & ID,const RangeSet & RS)254 static void Profile(llvm::FoldingSetNodeID &ID, const RangeSet &RS) { 255 ID.AddPointer(RS.Impl); 256 } 257 258 /// Profile - Generates a hash profile of this RangeSet for use 259 /// by FoldingSet. Profile(llvm::FoldingSetNodeID & ID)260 void Profile(llvm::FoldingSetNodeID &ID) const { Profile(ID, *this); } 261 262 /// getConcreteValue - If a symbol is constrained to equal a specific integer 263 /// constant then this method returns that value. Otherwise, it returns 264 /// NULL. getConcreteValue()265 const llvm::APSInt *getConcreteValue() const { 266 return Impl->size() == 1 ? begin()->getConcreteValue() : nullptr; 267 } 268 269 /// Get the minimal value covered by the ranges in the set. 270 /// 271 /// Complexity: O(1) 272 const llvm::APSInt &getMinValue() const; 273 /// Get the maximal value covered by the ranges in the set. 274 /// 275 /// Complexity: O(1) 276 const llvm::APSInt &getMaxValue() const; 277 278 /// Test whether the given point is contained by any of the ranges. 279 /// 280 /// Complexity: O(logN) 281 /// where N = size(this) contains(llvm::APSInt Point)282 bool contains(llvm::APSInt Point) const { return containsImpl(Point); } 283 284 void dump(raw_ostream &OS) const; 285 286 bool operator==(const RangeSet &Other) const { return *Impl == *Other.Impl; } 287 bool operator!=(const RangeSet &Other) const { return !(*this == Other); } 288 289 private: RangeSet(ContainerType * RawContainer)290 /* implicit */ RangeSet(ContainerType *RawContainer) : Impl(RawContainer) {} RangeSet(UnderlyingType Ptr)291 /* implicit */ RangeSet(UnderlyingType Ptr) : Impl(Ptr) {} 292 293 /// Pin given points to the type represented by the current range set. 294 /// 295 /// This makes parameter points to be in-out parameters. 296 /// In order to maintain consistent types across all of the ranges in the set 297 /// and to keep all the operations to compare ONLY points of the same type, we 298 /// need to pin every point before any operation. 299 /// 300 /// @Returns true if the given points can be converted to the target type 301 /// without changing the values (i.e. trivially) and false otherwise. 302 /// @{ 303 bool pin(llvm::APSInt &Lower, llvm::APSInt &Upper) const; 304 bool pin(llvm::APSInt &Point) const; 305 /// @} 306 307 // This version of this function modifies its arguments (pins it). 308 bool containsImpl(llvm::APSInt &Point) const; 309 310 friend class Factory; 311 }; 312 313 using ConstraintMap = llvm::ImmutableMap<SymbolRef, RangeSet>; 314 ConstraintMap getConstraintMap(ProgramStateRef State); 315 316 class RangedConstraintManager : public SimpleConstraintManager { 317 public: RangedConstraintManager(ExprEngine * EE,SValBuilder & SB)318 RangedConstraintManager(ExprEngine *EE, SValBuilder &SB) 319 : SimpleConstraintManager(EE, SB) {} 320 321 ~RangedConstraintManager() override; 322 323 //===------------------------------------------------------------------===// 324 // Implementation for interface from SimpleConstraintManager. 325 //===------------------------------------------------------------------===// 326 327 ProgramStateRef assumeSym(ProgramStateRef State, SymbolRef Sym, 328 bool Assumption) override; 329 330 ProgramStateRef assumeSymInclusiveRange(ProgramStateRef State, SymbolRef Sym, 331 const llvm::APSInt &From, 332 const llvm::APSInt &To, 333 bool InRange) override; 334 335 ProgramStateRef assumeSymUnsupported(ProgramStateRef State, SymbolRef Sym, 336 bool Assumption) override; 337 338 protected: 339 /// Assume a constraint between a symbolic expression and a concrete integer. 340 virtual ProgramStateRef assumeSymRel(ProgramStateRef State, SymbolRef Sym, 341 BinaryOperator::Opcode op, 342 const llvm::APSInt &Int); 343 344 //===------------------------------------------------------------------===// 345 // Interface that subclasses must implement. 346 //===------------------------------------------------------------------===// 347 348 // Each of these is of the form "$Sym+Adj <> V", where "<>" is the comparison 349 // operation for the method being invoked. 350 351 virtual ProgramStateRef assumeSymNE(ProgramStateRef State, SymbolRef Sym, 352 const llvm::APSInt &V, 353 const llvm::APSInt &Adjustment) = 0; 354 355 virtual ProgramStateRef assumeSymEQ(ProgramStateRef State, SymbolRef Sym, 356 const llvm::APSInt &V, 357 const llvm::APSInt &Adjustment) = 0; 358 359 virtual ProgramStateRef assumeSymLT(ProgramStateRef State, SymbolRef Sym, 360 const llvm::APSInt &V, 361 const llvm::APSInt &Adjustment) = 0; 362 363 virtual ProgramStateRef assumeSymGT(ProgramStateRef State, SymbolRef Sym, 364 const llvm::APSInt &V, 365 const llvm::APSInt &Adjustment) = 0; 366 367 virtual ProgramStateRef assumeSymLE(ProgramStateRef State, SymbolRef Sym, 368 const llvm::APSInt &V, 369 const llvm::APSInt &Adjustment) = 0; 370 371 virtual ProgramStateRef assumeSymGE(ProgramStateRef State, SymbolRef Sym, 372 const llvm::APSInt &V, 373 const llvm::APSInt &Adjustment) = 0; 374 375 virtual ProgramStateRef assumeSymWithinInclusiveRange( 376 ProgramStateRef State, SymbolRef Sym, const llvm::APSInt &From, 377 const llvm::APSInt &To, const llvm::APSInt &Adjustment) = 0; 378 379 virtual ProgramStateRef assumeSymOutsideInclusiveRange( 380 ProgramStateRef State, SymbolRef Sym, const llvm::APSInt &From, 381 const llvm::APSInt &To, const llvm::APSInt &Adjustment) = 0; 382 383 //===------------------------------------------------------------------===// 384 // Internal implementation. 385 //===------------------------------------------------------------------===// 386 private: 387 static void computeAdjustment(SymbolRef &Sym, llvm::APSInt &Adjustment); 388 }; 389 390 /// Try to simplify a given symbolic expression's associated value based on the 391 /// constraints in State. This is needed because the Environment bindings are 392 /// not getting updated when a new constraint is added to the State. 393 SymbolRef simplify(ProgramStateRef State, SymbolRef Sym); 394 395 } // namespace ento 396 } // namespace clang 397 398 REGISTER_FACTORY_WITH_PROGRAMSTATE(ConstraintMap) 399 400 #endif 401