/Users/buildslave/jenkins/workspace/coverage/llvm-project/clang/include/clang/StaticAnalyzer/Core/PathSensitive/RangedConstraintManager.h
Line | Count | Source (jump to first uncovered line) |
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 | 505k | : std::pair<const llvm::APSInt *, const llvm::APSInt *>(&from, &to) { |
31 | 505k | assert(from <= to); |
32 | 505k | } |
33 | | |
34 | | Range(const llvm::APSInt &point) |
35 | 0 | : std::pair<const llvm::APSInt *, const llvm::APSInt *>(&point, &point) {} |
36 | | |
37 | 343k | bool Includes(const llvm::APSInt &v) const { |
38 | 343k | return *first <= v && v <= *second337k ; |
39 | 343k | } |
40 | 1.42M | const llvm::APSInt &From() const { return *first; } |
41 | 1.20M | const llvm::APSInt &To() const { return *second; } |
42 | 200k | const llvm::APSInt *getConcreteValue() const { |
43 | 143k | return &From() == &To() ? &From()57.9k : nullptr; |
44 | 200k | } |
45 | | |
46 | 380k | void Profile(llvm::FoldingSetNodeID &ID) const { |
47 | 380k | ID.AddPointer(&From()); |
48 | 380k | ID.AddPointer(&To()); |
49 | 380k | } |
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 | 14.9k | static inline bool isLess(key_type_ref lhs, key_type_ref rhs) { |
59 | 14.9k | return *lhs.first < *rhs.first || |
60 | 13.5k | (!(*rhs.first < *lhs.first) && *lhs.second < *rhs.second0 ); |
61 | 14.9k | } |
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 | 232k | 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 | 1.96k | RangeSet addRange(Factory &F, const RangeSet &RS) { |
81 | 1.96k | PrimRangeSet Ranges(RS.ranges); |
82 | 1.96k | for (const auto &range : ranges) |
83 | 1.33k | Ranges = F.add(Ranges, range); |
84 | 1.96k | return RangeSet(Ranges); |
85 | 1.96k | } |
86 | | |
87 | 606k | iterator begin() const { return ranges.begin(); } |
88 | 305k | iterator end() const { return ranges.end(); } |
89 | | |
90 | 1.18M | 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 | 188k | : ranges(F.add(F.getEmptySet(), Range(from, to))) {} |
95 | | |
96 | | /// Construct a new RangeSet representing the given point as a range. |
97 | 39.2k | RangeSet(Factory &F, const llvm::APSInt &point) : RangeSet(F, point, point) {} Unexecuted instantiation: clang::ento::RangeSet::RangeSet(llvm::ImmutableSet<clang::ento::Range, clang::ento::RangeTrait>::Factory&, llvm::APSInt const&) clang::ento::RangeSet::RangeSet(llvm::ImmutableSet<clang::ento::Range, clang::ento::RangeTrait>::Factory&, llvm::APSInt const&) Line | Count | Source | 97 | 39.2k | 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 | 607k | 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 | 216k | const llvm::APSInt *getConcreteValue() const { |
107 | 200k | return ranges.isSingleton() ? ranges.begin()->getConcreteValue() : nullptr15.3k ; |
108 | 216k | } |
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 | 654k | bool operator==(const RangeSet &other) const { |
135 | 654k | return ranges == other.ranges; |
136 | 654k | } |
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 | 13.7k | : 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 |