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   bool Includes(const llvm::APSInt &v) const {
34     return *first <= v && v <= *second;
35   }
36   const llvm::APSInt &From() const { return *first; }
37   const llvm::APSInt &To() const { return *second; }
38   const llvm::APSInt *getConcreteValue() const {
39     return &From() == &To() ? &From() : nullptr;
40   }
41 
42   void Profile(llvm::FoldingSetNodeID &ID) const {
43     ID.AddPointer(&From());
44     ID.AddPointer(&To());
45   }
46 };
47 
48 class RangeTrait : public llvm::ImutContainerInfo<Range> {
49 public:
50   // When comparing if one Range is less than another, we should compare
51   // the actual APSInt values instead of their pointers.  This keeps the order
52   // consistent (instead of comparing by pointer values) and can potentially
53   // be used to speed up some of the operations in RangeSet.
54   static inline bool isLess(key_type_ref lhs, key_type_ref rhs) {
55     return *lhs.first < *rhs.first ||
56            (!(*rhs.first < *lhs.first) && *lhs.second < *rhs.second);
57   }
58 };
59 
60 /// RangeSet contains a set of ranges. If the set is empty, then
61 ///  there the value of a symbol is overly constrained and there are no
62 ///  possible values for that symbol.
63 class RangeSet {
64   typedef llvm::ImmutableSet<Range, RangeTrait> PrimRangeSet;
65   PrimRangeSet ranges; // no need to make const, since it is an
66                        // ImmutableSet - this allows default operator=
67                        // to work.
68 public:
69   typedef PrimRangeSet::Factory Factory;
70   typedef PrimRangeSet::iterator iterator;
71 
72   RangeSet(PrimRangeSet RS) : ranges(RS) {}
73 
74   /// Create a new set with all ranges of this set and RS.
75   /// Possible intersections are not checked here.
76   RangeSet addRange(Factory &F, const RangeSet &RS) {
77     PrimRangeSet Ranges(RS.ranges);
78     for (const auto &range : ranges)
79       Ranges = F.add(Ranges, range);
80     return RangeSet(Ranges);
81   }
82 
83   iterator begin() const { return ranges.begin(); }
84   iterator end() const { return ranges.end(); }
85 
86   bool isEmpty() const { return ranges.isEmpty(); }
87 
88   /// Construct a new RangeSet representing '{ [from, to] }'.
89   RangeSet(Factory &F, const llvm::APSInt &from, const llvm::APSInt &to)
90       : ranges(F.add(F.getEmptySet(), Range(from, to))) {}
91 
92   /// Profile - Generates a hash profile of this RangeSet for use
93   ///  by FoldingSet.
94   void Profile(llvm::FoldingSetNodeID &ID) const { ranges.Profile(ID); }
95 
96   /// getConcreteValue - If a symbol is contrained to equal a specific integer
97   ///  constant then this method returns that value.  Otherwise, it returns
98   ///  NULL.
99   const llvm::APSInt *getConcreteValue() const {
100     return ranges.isSingleton() ? ranges.begin()->getConcreteValue() : nullptr;
101   }
102 
103 private:
104   void IntersectInRange(BasicValueFactory &BV, Factory &F,
105                         const llvm::APSInt &Lower, const llvm::APSInt &Upper,
106                         PrimRangeSet &newRanges, PrimRangeSet::iterator &i,
107                         PrimRangeSet::iterator &e) const;
108 
109   const llvm::APSInt &getMinValue() const;
110 
111   bool pin(llvm::APSInt &Lower, llvm::APSInt &Upper) const;
112 
113 public:
114   RangeSet Intersect(BasicValueFactory &BV, Factory &F, llvm::APSInt Lower,
115                      llvm::APSInt Upper) const;
116   RangeSet Intersect(BasicValueFactory &BV, Factory &F,
117                      const RangeSet &Other) const;
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