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