1336815Sdim//== RangedConstraintManager.h ----------------------------------*- C++ -*--==// 2336815Sdim// 3353358Sdim// Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions. 4353358Sdim// See https://llvm.org/LICENSE.txt for license information. 5353358Sdim// SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception 6336815Sdim// 7336815Sdim//===----------------------------------------------------------------------===// 8336815Sdim// 9336815Sdim// Ranged constraint manager, built on SimpleConstraintManager. 10336815Sdim// 11336815Sdim//===----------------------------------------------------------------------===// 12336815Sdim 13336815Sdim#ifndef LLVM_CLANG_LIB_STATICANALYZER_CORE_RANGEDCONSTRAINTMANAGER_H 14336815Sdim#define LLVM_CLANG_LIB_STATICANALYZER_CORE_RANGEDCONSTRAINTMANAGER_H 15336815Sdim 16336815Sdim#include "clang/StaticAnalyzer/Core/PathSensitive/ProgramState.h" 17336815Sdim#include "clang/StaticAnalyzer/Core/PathSensitive/ProgramStateTrait.h" 18336815Sdim#include "clang/StaticAnalyzer/Core/PathSensitive/SimpleConstraintManager.h" 19336815Sdim 20336815Sdimnamespace clang { 21336815Sdim 22336815Sdimnamespace ento { 23336815Sdim 24336815Sdim/// A Range represents the closed range [from, to]. The caller must 25336815Sdim/// guarantee that from <= to. Note that Range is immutable, so as not 26336815Sdim/// to subvert RangeSet's immutability. 27336815Sdimclass Range : public std::pair<const llvm::APSInt *, const llvm::APSInt *> { 28336815Sdimpublic: 29336815Sdim Range(const llvm::APSInt &from, const llvm::APSInt &to) 30336815Sdim : std::pair<const llvm::APSInt *, const llvm::APSInt *>(&from, &to) { 31336815Sdim assert(from <= to); 32336815Sdim } 33336815Sdim bool Includes(const llvm::APSInt &v) const { 34336815Sdim return *first <= v && v <= *second; 35336815Sdim } 36336815Sdim const llvm::APSInt &From() const { return *first; } 37336815Sdim const llvm::APSInt &To() const { return *second; } 38336815Sdim const llvm::APSInt *getConcreteValue() const { 39336815Sdim return &From() == &To() ? &From() : nullptr; 40336815Sdim } 41336815Sdim 42336815Sdim void Profile(llvm::FoldingSetNodeID &ID) const { 43336815Sdim ID.AddPointer(&From()); 44336815Sdim ID.AddPointer(&To()); 45336815Sdim } 46336815Sdim}; 47336815Sdim 48336815Sdimclass RangeTrait : public llvm::ImutContainerInfo<Range> { 49336815Sdimpublic: 50336815Sdim // When comparing if one Range is less than another, we should compare 51336815Sdim // the actual APSInt values instead of their pointers. This keeps the order 52336815Sdim // consistent (instead of comparing by pointer values) and can potentially 53336815Sdim // be used to speed up some of the operations in RangeSet. 54336815Sdim static inline bool isLess(key_type_ref lhs, key_type_ref rhs) { 55336815Sdim return *lhs.first < *rhs.first || 56336815Sdim (!(*rhs.first < *lhs.first) && *lhs.second < *rhs.second); 57336815Sdim } 58336815Sdim}; 59336815Sdim 60336815Sdim/// RangeSet contains a set of ranges. If the set is empty, then 61336815Sdim/// there the value of a symbol is overly constrained and there are no 62336815Sdim/// possible values for that symbol. 63336815Sdimclass RangeSet { 64336815Sdim typedef llvm::ImmutableSet<Range, RangeTrait> PrimRangeSet; 65336815Sdim PrimRangeSet ranges; // no need to make const, since it is an 66336815Sdim // ImmutableSet - this allows default operator= 67336815Sdim // to work. 68336815Sdimpublic: 69336815Sdim typedef PrimRangeSet::Factory Factory; 70336815Sdim typedef PrimRangeSet::iterator iterator; 71336815Sdim 72336815Sdim RangeSet(PrimRangeSet RS) : ranges(RS) {} 73336815Sdim 74336815Sdim /// Create a new set with all ranges of this set and RS. 75336815Sdim /// Possible intersections are not checked here. 76336815Sdim RangeSet addRange(Factory &F, const RangeSet &RS) { 77336815Sdim PrimRangeSet Ranges(RS.ranges); 78336815Sdim for (const auto &range : ranges) 79336815Sdim Ranges = F.add(Ranges, range); 80336815Sdim return RangeSet(Ranges); 81336815Sdim } 82336815Sdim 83336815Sdim iterator begin() const { return ranges.begin(); } 84336815Sdim iterator end() const { return ranges.end(); } 85336815Sdim 86336815Sdim bool isEmpty() const { return ranges.isEmpty(); } 87336815Sdim 88336815Sdim /// Construct a new RangeSet representing '{ [from, to] }'. 89336815Sdim RangeSet(Factory &F, const llvm::APSInt &from, const llvm::APSInt &to) 90336815Sdim : ranges(F.add(F.getEmptySet(), Range(from, to))) {} 91336815Sdim 92336815Sdim /// Profile - Generates a hash profile of this RangeSet for use 93336815Sdim /// by FoldingSet. 94336815Sdim void Profile(llvm::FoldingSetNodeID &ID) const { ranges.Profile(ID); } 95336815Sdim 96336815Sdim /// getConcreteValue - If a symbol is contrained to equal a specific integer 97336815Sdim /// constant then this method returns that value. Otherwise, it returns 98336815Sdim /// NULL. 99336815Sdim const llvm::APSInt *getConcreteValue() const { 100336815Sdim return ranges.isSingleton() ? ranges.begin()->getConcreteValue() : nullptr; 101336815Sdim } 102336815Sdim 103336815Sdimprivate: 104336815Sdim void IntersectInRange(BasicValueFactory &BV, Factory &F, 105336815Sdim const llvm::APSInt &Lower, const llvm::APSInt &Upper, 106336815Sdim PrimRangeSet &newRanges, PrimRangeSet::iterator &i, 107336815Sdim PrimRangeSet::iterator &e) const; 108336815Sdim 109336815Sdim const llvm::APSInt &getMinValue() const; 110336815Sdim 111336815Sdim bool pin(llvm::APSInt &Lower, llvm::APSInt &Upper) const; 112336815Sdim 113336815Sdimpublic: 114336815Sdim RangeSet Intersect(BasicValueFactory &BV, Factory &F, llvm::APSInt Lower, 115336815Sdim llvm::APSInt Upper) const; 116353358Sdim RangeSet Intersect(BasicValueFactory &BV, Factory &F, 117353358Sdim const RangeSet &Other) const; 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