RangedConstraintManager.h revision 344779
1336815Sdim//== RangedConstraintManager.h ----------------------------------*- C++ -*--==// 2336815Sdim// 3336815Sdim// The LLVM Compiler Infrastructure 4336815Sdim// 5336815Sdim// This file is distributed under the University of Illinois Open Source 6336815Sdim// License. See LICENSE.TXT for details. 7336815Sdim// 8336815Sdim//===----------------------------------------------------------------------===// 9336815Sdim// 10336815Sdim// Ranged constraint manager, built on SimpleConstraintManager. 11336815Sdim// 12336815Sdim//===----------------------------------------------------------------------===// 13336815Sdim 14336815Sdim#ifndef LLVM_CLANG_LIB_STATICANALYZER_CORE_RANGEDCONSTRAINTMANAGER_H 15336815Sdim#define LLVM_CLANG_LIB_STATICANALYZER_CORE_RANGEDCONSTRAINTMANAGER_H 16336815Sdim 17336815Sdim#include "clang/StaticAnalyzer/Core/PathSensitive/ProgramState.h" 18336815Sdim#include "clang/StaticAnalyzer/Core/PathSensitive/ProgramStateTrait.h" 19336815Sdim#include "clang/StaticAnalyzer/Core/PathSensitive/SimpleConstraintManager.h" 20336815Sdim 21336815Sdimnamespace clang { 22336815Sdim 23336815Sdimnamespace ento { 24336815Sdim 25336815Sdim/// A Range represents the closed range [from, to]. The caller must 26336815Sdim/// guarantee that from <= to. Note that Range is immutable, so as not 27336815Sdim/// to subvert RangeSet's immutability. 28336815Sdimclass Range : public std::pair<const llvm::APSInt *, const llvm::APSInt *> { 29336815Sdimpublic: 30336815Sdim Range(const llvm::APSInt &from, const llvm::APSInt &to) 31336815Sdim : std::pair<const llvm::APSInt *, const llvm::APSInt *>(&from, &to) { 32336815Sdim assert(from <= to); 33336815Sdim } 34336815Sdim bool Includes(const llvm::APSInt &v) const { 35336815Sdim return *first <= v && v <= *second; 36336815Sdim } 37336815Sdim const llvm::APSInt &From() const { return *first; } 38336815Sdim const llvm::APSInt &To() const { return *second; } 39336815Sdim const llvm::APSInt *getConcreteValue() const { 40336815Sdim return &From() == &To() ? &From() : nullptr; 41336815Sdim } 42336815Sdim 43336815Sdim void Profile(llvm::FoldingSetNodeID &ID) const { 44336815Sdim ID.AddPointer(&From()); 45336815Sdim ID.AddPointer(&To()); 46336815Sdim } 47336815Sdim}; 48336815Sdim 49336815Sdimclass RangeTrait : public llvm::ImutContainerInfo<Range> { 50336815Sdimpublic: 51336815Sdim // When comparing if one Range is less than another, we should compare 52336815Sdim // the actual APSInt values instead of their pointers. This keeps the order 53336815Sdim // consistent (instead of comparing by pointer values) and can potentially 54336815Sdim // be used to speed up some of the operations in RangeSet. 55336815Sdim static inline bool isLess(key_type_ref lhs, key_type_ref rhs) { 56336815Sdim return *lhs.first < *rhs.first || 57336815Sdim (!(*rhs.first < *lhs.first) && *lhs.second < *rhs.second); 58336815Sdim } 59336815Sdim}; 60336815Sdim 61336815Sdim/// RangeSet contains a set of ranges. If the set is empty, then 62336815Sdim/// there the value of a symbol is overly constrained and there are no 63336815Sdim/// possible values for that symbol. 64336815Sdimclass RangeSet { 65336815Sdim typedef llvm::ImmutableSet<Range, RangeTrait> PrimRangeSet; 66336815Sdim PrimRangeSet ranges; // no need to make const, since it is an 67336815Sdim // ImmutableSet - this allows default operator= 68336815Sdim // to work. 69336815Sdimpublic: 70336815Sdim typedef PrimRangeSet::Factory Factory; 71336815Sdim typedef PrimRangeSet::iterator iterator; 72336815Sdim 73336815Sdim RangeSet(PrimRangeSet RS) : ranges(RS) {} 74336815Sdim 75336815Sdim /// Create a new set with all ranges of this set and RS. 76336815Sdim /// Possible intersections are not checked here. 77336815Sdim RangeSet addRange(Factory &F, const RangeSet &RS) { 78336815Sdim PrimRangeSet Ranges(RS.ranges); 79336815Sdim for (const auto &range : ranges) 80336815Sdim Ranges = F.add(Ranges, range); 81336815Sdim return RangeSet(Ranges); 82336815Sdim } 83336815Sdim 84336815Sdim iterator begin() const { return ranges.begin(); } 85336815Sdim iterator end() const { return ranges.end(); } 86336815Sdim 87336815Sdim bool isEmpty() const { return ranges.isEmpty(); } 88336815Sdim 89336815Sdim /// Construct a new RangeSet representing '{ [from, to] }'. 90336815Sdim RangeSet(Factory &F, const llvm::APSInt &from, const llvm::APSInt &to) 91336815Sdim : ranges(F.add(F.getEmptySet(), Range(from, to))) {} 92336815Sdim 93336815Sdim /// Profile - Generates a hash profile of this RangeSet for use 94336815Sdim /// by FoldingSet. 95336815Sdim void Profile(llvm::FoldingSetNodeID &ID) const { ranges.Profile(ID); } 96336815Sdim 97336815Sdim /// getConcreteValue - If a symbol is contrained to equal a specific integer 98336815Sdim /// constant then this method returns that value. Otherwise, it returns 99336815Sdim /// NULL. 100336815Sdim const llvm::APSInt *getConcreteValue() const { 101336815Sdim return ranges.isSingleton() ? ranges.begin()->getConcreteValue() : nullptr; 102336815Sdim } 103336815Sdim 104336815Sdimprivate: 105336815Sdim void IntersectInRange(BasicValueFactory &BV, Factory &F, 106336815Sdim const llvm::APSInt &Lower, const llvm::APSInt &Upper, 107336815Sdim PrimRangeSet &newRanges, PrimRangeSet::iterator &i, 108336815Sdim PrimRangeSet::iterator &e) const; 109336815Sdim 110336815Sdim const llvm::APSInt &getMinValue() const; 111336815Sdim 112336815Sdim bool pin(llvm::APSInt &Lower, llvm::APSInt &Upper) const; 113336815Sdim 114336815Sdimpublic: 115336815Sdim RangeSet Intersect(BasicValueFactory &BV, Factory &F, llvm::APSInt Lower, 116336815Sdim llvm::APSInt Upper) const; 117336815Sdim 118336815Sdim RangeSet Negate(BasicValueFactory &BV, Factory &F) const; 119336815Sdim 120336815Sdim void print(raw_ostream &os) const; 121336815Sdim 122336815Sdim bool operator==(const RangeSet &other) const { 123336815Sdim return ranges == other.ranges; 124336815Sdim } 125336815Sdim}; 126336815Sdim 127336815Sdim 128336815Sdimclass ConstraintRange {}; 129336815Sdimusing ConstraintRangeTy = llvm::ImmutableMap<SymbolRef, RangeSet>; 130336815Sdim 131336815Sdimtemplate <> 132336815Sdimstruct ProgramStateTrait<ConstraintRange> 133336815Sdim : public ProgramStatePartialTrait<ConstraintRangeTy> { 134344779Sdim static void *GDMIndex(); 135336815Sdim}; 136336815Sdim 137336815Sdim 138336815Sdimclass RangedConstraintManager : public SimpleConstraintManager { 139336815Sdimpublic: 140336815Sdim RangedConstraintManager(SubEngine *SE, SValBuilder &SB) 141336815Sdim : SimpleConstraintManager(SE, SB) {} 142336815Sdim 143336815Sdim ~RangedConstraintManager() override; 144336815Sdim 145336815Sdim //===------------------------------------------------------------------===// 146336815Sdim // Implementation for interface from SimpleConstraintManager. 147336815Sdim //===------------------------------------------------------------------===// 148336815Sdim 149336815Sdim ProgramStateRef assumeSym(ProgramStateRef State, SymbolRef Sym, 150336815Sdim bool Assumption) override; 151336815Sdim 152336815Sdim ProgramStateRef assumeSymInclusiveRange(ProgramStateRef State, SymbolRef Sym, 153336815Sdim const llvm::APSInt &From, 154336815Sdim const llvm::APSInt &To, 155336815Sdim bool InRange) override; 156336815Sdim 157336815Sdim ProgramStateRef assumeSymUnsupported(ProgramStateRef State, SymbolRef Sym, 158336815Sdim bool Assumption) override; 159336815Sdim 160336815Sdimprotected: 161336815Sdim /// Assume a constraint between a symbolic expression and a concrete integer. 162336815Sdim virtual ProgramStateRef assumeSymRel(ProgramStateRef State, SymbolRef Sym, 163336815Sdim BinaryOperator::Opcode op, 164336815Sdim const llvm::APSInt &Int); 165336815Sdim 166336815Sdim //===------------------------------------------------------------------===// 167336815Sdim // Interface that subclasses must implement. 168336815Sdim //===------------------------------------------------------------------===// 169336815Sdim 170336815Sdim // Each of these is of the form "$Sym+Adj <> V", where "<>" is the comparison 171336815Sdim // operation for the method being invoked. 172336815Sdim 173336815Sdim virtual ProgramStateRef assumeSymNE(ProgramStateRef State, SymbolRef Sym, 174336815Sdim const llvm::APSInt &V, 175336815Sdim const llvm::APSInt &Adjustment) = 0; 176336815Sdim 177336815Sdim virtual ProgramStateRef assumeSymEQ(ProgramStateRef State, SymbolRef Sym, 178336815Sdim const llvm::APSInt &V, 179336815Sdim const llvm::APSInt &Adjustment) = 0; 180336815Sdim 181336815Sdim virtual ProgramStateRef assumeSymLT(ProgramStateRef State, SymbolRef Sym, 182336815Sdim const llvm::APSInt &V, 183336815Sdim const llvm::APSInt &Adjustment) = 0; 184336815Sdim 185336815Sdim virtual ProgramStateRef assumeSymGT(ProgramStateRef State, SymbolRef Sym, 186336815Sdim const llvm::APSInt &V, 187336815Sdim const llvm::APSInt &Adjustment) = 0; 188336815Sdim 189336815Sdim virtual ProgramStateRef assumeSymLE(ProgramStateRef State, SymbolRef Sym, 190336815Sdim const llvm::APSInt &V, 191336815Sdim const llvm::APSInt &Adjustment) = 0; 192336815Sdim 193336815Sdim virtual ProgramStateRef assumeSymGE(ProgramStateRef State, SymbolRef Sym, 194336815Sdim const llvm::APSInt &V, 195336815Sdim const llvm::APSInt &Adjustment) = 0; 196336815Sdim 197336815Sdim virtual ProgramStateRef assumeSymWithinInclusiveRange( 198336815Sdim ProgramStateRef State, SymbolRef Sym, const llvm::APSInt &From, 199336815Sdim const llvm::APSInt &To, const llvm::APSInt &Adjustment) = 0; 200336815Sdim 201336815Sdim virtual ProgramStateRef assumeSymOutsideInclusiveRange( 202336815Sdim ProgramStateRef State, SymbolRef Sym, const llvm::APSInt &From, 203336815Sdim const llvm::APSInt &To, const llvm::APSInt &Adjustment) = 0; 204336815Sdim 205336815Sdim //===------------------------------------------------------------------===// 206336815Sdim // Internal implementation. 207336815Sdim //===------------------------------------------------------------------===// 208336815Sdimprivate: 209336815Sdim static void computeAdjustment(SymbolRef &Sym, llvm::APSInt &Adjustment); 210336815Sdim}; 211336815Sdim 212336815Sdim} // end GR namespace 213336815Sdim 214336815Sdim} // end clang namespace 215336815Sdim 216336815Sdim#endif 217