RangedConstraintManager.h source code [clang_source_code/include/clang/StaticAnalyzer/Core/PathSensitive/RangedConstraintManager.h]

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