RangedConstraintManager.h revision 336815
1157114Sscottl//== RangedConstraintManager.h ----------------------------------*- C++ -*--==// 2157114Sscottl// 3157114Sscottl// The LLVM Compiler Infrastructure 4157114Sscottl// 5157114Sscottl// This file is distributed under the University of Illinois Open Source 6157114Sscottl// License. See LICENSE.TXT for details. 7157114Sscottl// 8157114Sscottl//===----------------------------------------------------------------------===// 9157114Sscottl// 10157114Sscottl// Ranged constraint manager, built on SimpleConstraintManager. 11157114Sscottl// 12157114Sscottl//===----------------------------------------------------------------------===// 13157114Sscottl 14157114Sscottl#ifndef LLVM_CLANG_LIB_STATICANALYZER_CORE_RANGEDCONSTRAINTMANAGER_H 15157114Sscottl#define LLVM_CLANG_LIB_STATICANALYZER_CORE_RANGEDCONSTRAINTMANAGER_H 16157114Sscottl 17157114Sscottl#include "clang/StaticAnalyzer/Core/PathSensitive/ProgramState.h" 18157114Sscottl#include "clang/StaticAnalyzer/Core/PathSensitive/ProgramStateTrait.h" 19157114Sscottl#include "clang/StaticAnalyzer/Core/PathSensitive/SimpleConstraintManager.h" 20157114Sscottl 21157114Sscottlnamespace clang { 22157114Sscottl 23157114Sscottlnamespace ento { 24157114Sscottl 25157114Sscottl/// A Range represents the closed range [from, to]. The caller must 26157114Sscottl/// guarantee that from <= to. Note that Range is immutable, so as not 27157114Sscottl/// to subvert RangeSet's immutability. 28157114Sscottlclass Range : public std::pair<const llvm::APSInt *, const llvm::APSInt *> { 29157114Sscottlpublic: 30196200Sscottl Range(const llvm::APSInt &from, const llvm::APSInt &to) 31196200Sscottl : std::pair<const llvm::APSInt *, const llvm::APSInt *>(&from, &to) { 32164281Sambrisko assert(from <= to); 33164281Sambrisko } 34164281Sambrisko bool Includes(const llvm::APSInt &v) const { 35164281Sambrisko return *first <= v && v <= *second; 36164281Sambrisko } 37157114Sscottl const llvm::APSInt &From() const { return *first; } 38157114Sscottl const llvm::APSInt &To() const { return *second; } 39157114Sscottl const llvm::APSInt *getConcreteValue() const { 40157114Sscottl return &From() == &To() ? &From() : nullptr; 41157114Sscottl } 42157114Sscottl 43157114Sscottl void Profile(llvm::FoldingSetNodeID &ID) const { 44157114Sscottl ID.AddPointer(&From()); 45157114Sscottl ID.AddPointer(&To()); 46157114Sscottl } 47157114Sscottl}; 48157114Sscottl 49157114Sscottlclass RangeTrait : public llvm::ImutContainerInfo<Range> { 50157114Sscottlpublic: 51157114Sscottl // When comparing if one Range is less than another, we should compare 52157114Sscottl // the actual APSInt values instead of their pointers. This keeps the order 53184897Sambrisko // consistent (instead of comparing by pointer values) and can potentially 54184897Sambrisko // be used to speed up some of the operations in RangeSet. 55184897Sambrisko static inline bool isLess(key_type_ref lhs, key_type_ref rhs) { 56184897Sambrisko return *lhs.first < *rhs.first || 57184897Sambrisko (!(*rhs.first < *lhs.first) && *lhs.second < *rhs.second); 58184897Sambrisko } 59184897Sambrisko}; 60184897Sambrisko 61184897Sambrisko/// RangeSet contains a set of ranges. If the set is empty, then 62184897Sambrisko/// there the value of a symbol is overly constrained and there are no 63164281Sambrisko/// possible values for that symbol. 64164281Sambriskoclass RangeSet { 65164281Sambrisko typedef llvm::ImmutableSet<Range, RangeTrait> PrimRangeSet; 66165225Sambrisko PrimRangeSet ranges; // no need to make const, since it is an 67165225Sambrisko // ImmutableSet - this allows default operator= 68165225Sambrisko // to work. 69165225Sambriskopublic: 70165225Sambrisko typedef PrimRangeSet::Factory Factory; 71165225Sambrisko typedef PrimRangeSet::iterator iterator; 72164281Sambrisko 73164281Sambrisko RangeSet(PrimRangeSet RS) : ranges(RS) {} 74164281Sambrisko 75165225Sambrisko /// Create a new set with all ranges of this set and RS. 76164281Sambrisko /// Possible intersections are not checked here. 77165225Sambrisko RangeSet addRange(Factory &F, const RangeSet &RS) { 78164281Sambrisko PrimRangeSet Ranges(RS.ranges); 79164281Sambrisko for (const auto &range : ranges) 80233711Sambrisko Ranges = F.add(Ranges, range); 81179392Sambrisko return RangeSet(Ranges); 82179392Sambrisko } 83179392Sambrisko 84179392Sambrisko iterator begin() const { return ranges.begin(); } 85179392Sambrisko iterator end() const { return ranges.end(); } 86179392Sambrisko 87179392Sambrisko bool isEmpty() const { return ranges.isEmpty(); } 88179392Sambrisko 89179392Sambrisko /// Construct a new RangeSet representing '{ [from, to] }'. 90179392Sambrisko RangeSet(Factory &F, const llvm::APSInt &from, const llvm::APSInt &to) 91179392Sambrisko : ranges(F.add(F.getEmptySet(), Range(from, to))) {} 92179392Sambrisko 93179392Sambrisko /// Profile - Generates a hash profile of this RangeSet for use 94179392Sambrisko /// by FoldingSet. 95179392Sambrisko void Profile(llvm::FoldingSetNodeID &ID) const { ranges.Profile(ID); } 96179392Sambrisko 97164281Sambrisko /// getConcreteValue - If a symbol is contrained to equal a specific integer 98164281Sambrisko /// constant then this method returns that value. Otherwise, it returns 99164281Sambrisko /// NULL. 100164281Sambrisko const llvm::APSInt *getConcreteValue() const { 101164281Sambrisko return ranges.isSingleton() ? ranges.begin()->getConcreteValue() : nullptr; 102164281Sambrisko } 103164281Sambrisko 104164281Sambriskoprivate: 105233711Sambrisko void IntersectInRange(BasicValueFactory &BV, Factory &F, 106179392Sambrisko const llvm::APSInt &Lower, const llvm::APSInt &Upper, 107179392Sambrisko PrimRangeSet &newRanges, PrimRangeSet::iterator &i, 108164281Sambrisko PrimRangeSet::iterator &e) const; 109164281Sambrisko 110158737Sambrisko const llvm::APSInt &getMinValue() const; 111158737Sambrisko 112158737Sambrisko bool pin(llvm::APSInt &Lower, llvm::APSInt &Upper) const; 113158737Sambrisko 114158737Sambriskopublic: 115158737Sambrisko RangeSet Intersect(BasicValueFactory &BV, Factory &F, llvm::APSInt Lower, 116158737Sambrisko llvm::APSInt Upper) const; 117158737Sambrisko 118158737Sambrisko RangeSet Negate(BasicValueFactory &BV, Factory &F) const; 119158737Sambrisko 120158737Sambrisko void print(raw_ostream &os) const; 121158737Sambrisko 122158737Sambrisko bool operator==(const RangeSet &other) const { 123158737Sambrisko return ranges == other.ranges; 124164281Sambrisko } 125164281Sambrisko}; 126164281Sambrisko 127158737Sambrisko 128164281Sambriskoclass ConstraintRange {}; 129158737Sambriskousing ConstraintRangeTy = llvm::ImmutableMap<SymbolRef, RangeSet>; 130158737Sambrisko 131178968Sscottltemplate <> 132178968Sscottlstruct ProgramStateTrait<ConstraintRange> 133178968Sscottl : public ProgramStatePartialTrait<ConstraintRangeTy> { 134178968Sscottl static void *GDMIndex() { static int Index; return &Index; } 135178968Sscottl}; 136178968Sscottl 137233711Sambrisko 138178968Sscottlclass RangedConstraintManager : public SimpleConstraintManager { 139178968Sscottlpublic: 140178968Sscottl RangedConstraintManager(SubEngine *SE, SValBuilder &SB) 141178968Sscottl : SimpleConstraintManager(SE, SB) {} 142178968Sscottl 143178968Sscottl ~RangedConstraintManager() override; 144178968Sscottl 145157114Sscottl //===------------------------------------------------------------------===// 146178968Sscottl // Implementation for interface from SimpleConstraintManager. 147233711Sambrisko //===------------------------------------------------------------------===// 148178968Sscottl 149178968Sscottl ProgramStateRef assumeSym(ProgramStateRef State, SymbolRef Sym, 150157114Sscottl bool Assumption) override; 151158737Sambrisko 152158737Sambrisko ProgramStateRef assumeSymInclusiveRange(ProgramStateRef State, SymbolRef Sym, 153158737Sambrisko const llvm::APSInt &From, 154158737Sambrisko const llvm::APSInt &To, 155158737Sambrisko bool InRange) override; 156158737Sambrisko 157164281Sambrisko ProgramStateRef assumeSymUnsupported(ProgramStateRef State, SymbolRef Sym, 158169451Sscottl bool Assumption) override; 159169451Sscottl 160169451Sscottlprotected: 161169451Sscottl /// Assume a constraint between a symbolic expression and a concrete integer. 162169451Sscottl virtual ProgramStateRef assumeSymRel(ProgramStateRef State, SymbolRef Sym, 163169451Sscottl BinaryOperator::Opcode op, 164169451Sscottl const llvm::APSInt &Int); 165169451Sscottl 166169451Sscottl //===------------------------------------------------------------------===// 167169451Sscottl // Interface that subclasses must implement. 168164281Sambrisko //===------------------------------------------------------------------===// 169164281Sambrisko 170164281Sambrisko // Each of these is of the form "$Sym+Adj <> V", where "<>" is the comparison 171164281Sambrisko // operation for the method being invoked. 172164281Sambrisko 173164281Sambrisko virtual ProgramStateRef assumeSymNE(ProgramStateRef State, SymbolRef Sym, 174164281Sambrisko const llvm::APSInt &V, 175164281Sambrisko const llvm::APSInt &Adjustment) = 0; 176 177 virtual ProgramStateRef assumeSymEQ(ProgramStateRef State, SymbolRef Sym, 178 const llvm::APSInt &V, 179 const llvm::APSInt &Adjustment) = 0; 180 181 virtual ProgramStateRef assumeSymLT(ProgramStateRef State, SymbolRef Sym, 182 const llvm::APSInt &V, 183 const llvm::APSInt &Adjustment) = 0; 184 185 virtual ProgramStateRef assumeSymGT(ProgramStateRef State, SymbolRef Sym, 186 const llvm::APSInt &V, 187 const llvm::APSInt &Adjustment) = 0; 188 189 virtual ProgramStateRef assumeSymLE(ProgramStateRef State, SymbolRef Sym, 190 const llvm::APSInt &V, 191 const llvm::APSInt &Adjustment) = 0; 192 193 virtual ProgramStateRef assumeSymGE(ProgramStateRef State, SymbolRef Sym, 194 const llvm::APSInt &V, 195 const llvm::APSInt &Adjustment) = 0; 196 197 virtual ProgramStateRef assumeSymWithinInclusiveRange( 198 ProgramStateRef State, SymbolRef Sym, const llvm::APSInt &From, 199 const llvm::APSInt &To, const llvm::APSInt &Adjustment) = 0; 200 201 virtual ProgramStateRef assumeSymOutsideInclusiveRange( 202 ProgramStateRef State, SymbolRef Sym, const llvm::APSInt &From, 203 const llvm::APSInt &To, const llvm::APSInt &Adjustment) = 0; 204 205 //===------------------------------------------------------------------===// 206 // Internal implementation. 207 //===------------------------------------------------------------------===// 208private: 209 static void computeAdjustment(SymbolRef &Sym, llvm::APSInt &Adjustment); 210}; 211 212} // end GR namespace 213 214} // end clang namespace 215 216#endif 217