contrib/llvm/tools/clang/include/clang/StaticAnalyzer/Core/PathSensitive/RangedConstraintManager.h

   1 //== RangedConstraintManager.h ----------------------------------*- C++ -*--==//
   2 //
   3 //                     The LLVM Compiler Infrastructure
   4 //
   5 // This file is distributed under the University of Illinois Open Source
   6 // License. See LICENSE.TXT for details.
   7 //
   8 //===----------------------------------------------------------------------===//
   9 //
  10 //  Ranged constraint manager, built on SimpleConstraintManager.
  11 //
  12 //===----------------------------------------------------------------------===//
  13
  14 #ifndef LLVM_CLANG_LIB_STATICANALYZER_CORE_RANGEDCONSTRAINTMANAGER_H
  15 #define LLVM_CLANG_LIB_STATICANALYZER_CORE_RANGEDCONSTRAINTMANAGER_H
  16
  17 #include "clang/StaticAnalyzer/Core/PathSensitive/ProgramState.h"
  18 #include "clang/StaticAnalyzer/Core/PathSensitive/ProgramStateTrait.h"
  19 #include "clang/StaticAnalyzer/Core/PathSensitive/SimpleConstraintManager.h"
  20
  21 namespace clang {
  22
  23 namespace ento {
  24
  25 /// A Range represents the closed range [from, to].  The caller must
  26 /// guarantee that from <= to.  Note that Range is immutable, so as not
  27 /// to subvert RangeSet's immutability.
  28 class Range : public std::pair<const llvm::APSInt *, const llvm::APSInt *> {
  29 public:
  30   Range(const llvm::APSInt &from, const llvm::APSInt &to)
  31       : std::pair<const llvm::APSInt *, const llvm::APSInt *>(&from, &to) {
  32     assert(from <= to);
  33   }
  34   bool Includes(const llvm::APSInt &v) const {
  35     return *first <= v && v <= *second;
  36   }
  37   const llvm::APSInt &From() const { return *first; }
  38   const llvm::APSInt &To() const { return *second; }
  39   const llvm::APSInt *getConcreteValue() const {
  40     return &From() == &To() ? &From() : nullptr;
  41   }
  42
  43   void Profile(llvm::FoldingSetNodeID &ID) const {
  44     ID.AddPointer(&From());
  45     ID.AddPointer(&To());
  46   }
  47 };
  48
  49 class RangeTrait : public llvm::ImutContainerInfo<Range> {
  50 public:
  51   // When comparing if one Range is less than another, we should compare
  52   // the actual APSInt values instead of their pointers.  This keeps the order
  53   // consistent (instead of comparing by pointer values) and can potentially
  54   // be used to speed up some of the operations in RangeSet.
  55   static inline bool isLess(key_type_ref lhs, key_type_ref rhs) {
  56     return *lhs.first < *rhs.first ||
  57            (!(*rhs.first < *lhs.first) && *lhs.second < *rhs.second);
  58   }
  59 };
  60
  61 /// RangeSet contains a set of ranges. If the set is empty, then
  62 ///  there the value of a symbol is overly constrained and there are no
  63 ///  possible values for that symbol.
  64 class RangeSet {
  65   typedef llvm::ImmutableSet<Range, RangeTrait> PrimRangeSet;
  66   PrimRangeSet ranges; // no need to make const, since it is an
  67                        // ImmutableSet - this allows default operator=
  68                        // to work.
  69 public:
  70   typedef PrimRangeSet::Factory Factory;
  71   typedef PrimRangeSet::iterator iterator;
  72
  73   RangeSet(PrimRangeSet RS) : ranges(RS) {}
  74
  75   /// Create a new set with all ranges of this set and RS.
  76   /// Possible intersections are not checked here.
  77   RangeSet addRange(Factory &F, const RangeSet &RS) {
  78     PrimRangeSet Ranges(RS.ranges);
  79     for (const auto &range : ranges)
  80       Ranges = F.add(Ranges, range);
  81     return RangeSet(Ranges);
  82   }
  83
  84   iterator begin() const { return ranges.begin(); }
  85   iterator end() const { return ranges.end(); }
  86
  87   bool isEmpty() const { return ranges.isEmpty(); }
  88
  89   /// Construct a new RangeSet representing '{ [from, to] }'.
  90   RangeSet(Factory &F, const llvm::APSInt &from, const llvm::APSInt &to)
  91       : ranges(F.add(F.getEmptySet(), Range(from, to))) {}
  92
  93   /// Profile - Generates a hash profile of this RangeSet for use
  94   ///  by FoldingSet.
  95   void Profile(llvm::FoldingSetNodeID &ID) const { ranges.Profile(ID); }
  96
  97   /// getConcreteValue - If a symbol is contrained to equal a specific integer
  98   ///  constant then this method returns that value.  Otherwise, it returns
  99   ///  NULL.
 100   const llvm::APSInt *getConcreteValue() const {
 101     return ranges.isSingleton() ? ranges.begin()->getConcreteValue() : nullptr;
 102   }
 103
 104 private:
 105   void IntersectInRange(BasicValueFactory &BV, Factory &F,
 106                         const llvm::APSInt &Lower, const llvm::APSInt &Upper,
 107                         PrimRangeSet &newRanges, PrimRangeSet::iterator &i,
 108                         PrimRangeSet::iterator &e) const;
 109
 110   const llvm::APSInt &getMinValue() const;
 111
 112   bool pin(llvm::APSInt &Lower, llvm::APSInt &Upper) const;
 113
 114 public:
 115   RangeSet Intersect(BasicValueFactory &BV, Factory &F, llvm::APSInt Lower,
 116                      llvm::APSInt Upper) const;
 117
 118   RangeSet Negate(BasicValueFactory &BV, Factory &F) const;
 119
 120   void print(raw_ostream &os) const;
 121
 122   bool operator==(const RangeSet &other) const {
 123     return ranges == other.ranges;
 124   }
 125 };
 126
 127
 128 class ConstraintRange {};
 129 using ConstraintRangeTy = llvm::ImmutableMap<SymbolRef, RangeSet>;
 130
 131 template <>
 132 struct ProgramStateTrait<ConstraintRange>
 133   : public ProgramStatePartialTrait<ConstraintRangeTy> {
 134   static void *GDMIndex() { static int Index; return &Index; }
 135 };
 136
 137
 138 class RangedConstraintManager : public SimpleConstraintManager {
 139 public:
 140   RangedConstraintManager(SubEngine *SE, SValBuilder &SB)
 141       : SimpleConstraintManager(SE, SB) {}
 142
 143   ~RangedConstraintManager() override;
 144
 145   //===------------------------------------------------------------------===//
 146   // Implementation for interface from SimpleConstraintManager.
 147   //===------------------------------------------------------------------===//
 148
 149   ProgramStateRef assumeSym(ProgramStateRef State, SymbolRef Sym,
 150                             bool Assumption) override;
 151
 152   ProgramStateRef assumeSymInclusiveRange(ProgramStateRef State, SymbolRef Sym,
 153                                           const llvm::APSInt &From,
 154                                           const llvm::APSInt &To,
 155                                           bool InRange) override;
 156
 157   ProgramStateRef assumeSymUnsupported(ProgramStateRef State, SymbolRef Sym,
 158                                        bool Assumption) override;
 159
 160 protected:
 161   /// Assume a constraint between a symbolic expression and a concrete integer.
 162   virtual ProgramStateRef assumeSymRel(ProgramStateRef State, SymbolRef Sym,
 163                                BinaryOperator::Opcode op,
 164                                const llvm::APSInt &Int);
 165
 166   //===------------------------------------------------------------------===//
 167   // Interface that subclasses must implement.
 168   //===------------------------------------------------------------------===//
 169
 170   // Each of these is of the form "$Sym+Adj <> V", where "<>" is the comparison
 171   // operation for the method being invoked.
 172
 173   virtual ProgramStateRef assumeSymNE(ProgramStateRef State, SymbolRef Sym,
 174                                       const llvm::APSInt &V,
 175                                       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   //===------------------------------------------------------------------===//
 208 private:
 209   static void computeAdjustment(SymbolRef &Sym, llvm::APSInt &Adjustment);
 210 };
 211
 212 } // end GR namespace
 213
 214 } // end clang namespace
 215
 216 #endif