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:
Range(const llvm::APSInt & from,const llvm::APSInt & to)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   }
Includes(const llvm::APSInt & v)34   bool Includes(const llvm::APSInt &v) const {
35     return *first <= v && v <= *second;
36   }
From()37   const llvm::APSInt &From() const { return *first; }
To()38   const llvm::APSInt &To() const { return *second; }
getConcreteValue()39   const llvm::APSInt *getConcreteValue() const {
40     return &From() == &To() ? &From() : nullptr;
41   }
42 
Profile(llvm::FoldingSetNodeID & ID)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.
isLess(key_type_ref lhs,key_type_ref rhs)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 
RangeSet(PrimRangeSet RS)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.
addRange(Factory & F,const RangeSet & RS)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 
begin()84   iterator begin() const { return ranges.begin(); }
end()85   iterator end() const { return ranges.end(); }
86 
isEmpty()87   bool isEmpty() const { return ranges.isEmpty(); }
88 
89   /// Construct a new RangeSet representing '{ [from, to] }'.
RangeSet(Factory & F,const llvm::APSInt & from,const llvm::APSInt & 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.
Profile(llvm::FoldingSetNodeID & ID)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.
getConcreteValue()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();
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
217