ThreadSafetyUtil.h source code [clang_source_code/include/clang/Analysis/Analyses/ThreadSafetyUtil.h]

1	//===- ThreadSafetyUtil.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	// This file defines some basic utility classes for use by ThreadSafetyTIL.h
10	//
11	//===----------------------------------------------------------------------===//
12
13	#ifndef LLVM_CLANG_ANALYSIS_ANALYSES_THREADSAFETYUTIL_H
14	#define LLVM_CLANG_ANALYSIS_ANALYSES_THREADSAFETYUTIL_H
15
16	#include "clang/AST/Decl.h"
17	#include "clang/Basic/LLVM.h"
18	#include "llvm/ADT/StringRef.h"
19	#include "llvm/ADT/iterator_range.h"
20	#include "llvm/Support/Allocator.h"
21	#include <cassert>
22	#include <cstddef>
23	#include <cstring>
24	#include <iterator>
25	#include <ostream>
26	#include <string>
27	#include <vector>
28
29	namespace clang {
30
31	class Expr;
32
33	namespace threadSafety {
34	namespace til {
35
36	// Simple wrapper class to abstract away from the details of memory management.
37	// SExprs are allocated in pools, and deallocated all at once.
38	class MemRegionRef {
39	private:
40	union AlignmentType {
41	double d;
42	void *p;
43	long double dd;
44	long long ii;
45	};
46
47	public:
48	MemRegionRef() = default;
49	MemRegionRef(llvm::BumpPtrAllocator *A) : Allocator(A) {}
50
51	void *allocate(size_t Sz) {
52	return Allocator->Allocate(Sz, alignof(AlignmentType));
53	}
54
55	template <typename T> T *allocateT() { return Allocator->Allocate<T>(); }
56
57	template <typename T> T *allocateT(size_t NumElems) {
58	return Allocator->Allocate<T>(NumElems);
59	}
60
61	private:
62	llvm::BumpPtrAllocator *Allocator = nullptr;
63	};
64
65	} // namespace til
66	} // namespace threadSafety
67
68	} // namespace clang
69
70	inline void *operator new(size_t Sz,
71	clang::threadSafety::til::MemRegionRef &R) {
72	return R.allocate(Sz);
73	}
74
75	namespace clang {
76	namespace threadSafety {
77
78	std::string getSourceLiteralString(const Expr *CE);
79
80	namespace til {
81
82	// A simple fixed size array class that does not manage its own memory,
83	// suitable for use with bump pointer allocation.
84	template <class T> class SimpleArray {
85	public:
86	SimpleArray() = default;
87	SimpleArray(T *Dat, size_t Cp, size_t Sz = 0)
88	: Data(Dat), Size(Sz), Capacity(Cp) {}
89	SimpleArray(MemRegionRef A, size_t Cp)
90	: Data(Cp == 0 ? nullptr : A.allocateT<T>(Cp)), Capacity(Cp) {}
91	SimpleArray(const SimpleArray<T> &A) = delete;
92
93	SimpleArray(SimpleArray<T> &&A)
94	: Data(A.Data), Size(A.Size), Capacity(A.Capacity) {
95	A.Data = nullptr;
96	A.Size = 0;
97	A.Capacity = 0;
98	}
99
100	SimpleArray &operator=(SimpleArray &&RHS) {
101	if (this != &RHS) {
102	Data = RHS.Data;
103	Size = RHS.Size;
104	Capacity = RHS.Capacity;
105
106	RHS.Data = nullptr;
107	RHS.Size = RHS.Capacity = 0;
108	}
109	return *this;
110	}
111
112	// Reserve space for at least Ncp items, reallocating if necessary.
113	void reserve(size_t Ncp, MemRegionRef A) {
114	if (Ncp <= Capacity)
115	return;
116	T *Odata = Data;
117	Data = A.allocateT<T>(Ncp);
118	Capacity = Ncp;
119	memcpy(Data, Odata, sizeof(T) * Size);
120	}
121
122	// Reserve space for at least N more items.
123	void reserveCheck(size_t N, MemRegionRef A) {
124	if (Capacity == 0)
125	reserve(u_max(InitialCapacity, N), A);
126	else if (Size + N < Capacity)
127	reserve(u_max(Size + N, Capacity * 2), A);
128	}
129
130	using iterator = T *;
131	using const_iterator = const T *;
132	using reverse_iterator = std::reverse_iterator<iterator>;
133	using const_reverse_iterator = std::reverse_iterator<const_iterator>;
134
135	size_t size() const { return Size; }
136	size_t capacity() const { return Capacity; }
137
138	T &operator[](unsigned i) {
139	(0) . __assert_fail ("i < Size && \"Array index out of bounds.\"", "/home/seafit/code_projects/clang_source/clang/include/clang/Analysis/Analyses/ThreadSafetyUtil.h", 139, __PRETTY_FUNCTION__))" file_link="../../../../../include/assert.h.html#88" macro="true">assert(i < Size && "Array index out of bounds.");
140	return Data[i];
141	}
142
143	const T &operator[](unsigned i) const {
144	(0) . __assert_fail ("i < Size && \"Array index out of bounds.\"", "/home/seafit/code_projects/clang_source/clang/include/clang/Analysis/Analyses/ThreadSafetyUtil.h", 144, __PRETTY_FUNCTION__))" file_link="../../../../../include/assert.h.html#88" macro="true">assert(i < Size && "Array index out of bounds.");
145	return Data[i];
146	}
147
148	T &back() {
149	(0) . __assert_fail ("Size && \"No elements in the array.\"", "/home/seafit/code_projects/clang_source/clang/include/clang/Analysis/Analyses/ThreadSafetyUtil.h", 149, __PRETTY_FUNCTION__))" file_link="../../../../../include/assert.h.html#88" macro="true">assert(Size && "No elements in the array.");
150	return Data[Size - 1];
151	}
152
153	const T &back() const {
154	(0) . __assert_fail ("Size && \"No elements in the array.\"", "/home/seafit/code_projects/clang_source/clang/include/clang/Analysis/Analyses/ThreadSafetyUtil.h", 154, __PRETTY_FUNCTION__))" file_link="../../../../../include/assert.h.html#88" macro="true">assert(Size && "No elements in the array.");
155	return Data[Size - 1];
156	}
157
158	iterator begin() { return Data; }
159	iterator end() { return Data + Size; }
160
161	const_iterator begin() const { return Data; }
162	const_iterator end() const { return Data + Size; }
163
164	const_iterator cbegin() const { return Data; }
165	const_iterator cend() const { return Data + Size; }
166
167	reverse_iterator rbegin() { return reverse_iterator(end()); }
168	reverse_iterator rend() { return reverse_iterator(begin()); }
169
170	const_reverse_iterator rbegin() const {
171	return const_reverse_iterator(end());
172	}
173
174	const_reverse_iterator rend() const {
175	return const_reverse_iterator(begin());
176	}
177
178	void push_back(const T &Elem) {
179	assert(Size < Capacity);
180	Data[Size++] = Elem;
181	}
182
183	// drop last n elements from array
184	void drop(unsigned n = 0) {
185	n", "/home/seafit/code_projects/clang_source/clang/include/clang/Analysis/Analyses/ThreadSafetyUtil.h", 185, __PRETTY_FUNCTION__))" file_link="../../../../../include/assert.h.html#88" macro="true">assert(Size > n);
186	Size -= n;
187	}
188
189	void setValues(unsigned Sz, const T& C) {
190	assert(Sz <= Capacity);
191	Size = Sz;
192	for (unsigned i = 0; i < Sz; ++i) {
193	Data[i] = C;
194	}
195	}
196
197	template <class Iter> unsigned append(Iter I, Iter E) {
198	size_t Osz = Size;
199	size_t J = Osz;
200	for (; J < Capacity && I != E; ++J, ++I)
201	Data[J] = *I;
202	Size = J;
203	return J - Osz;
204	}
205
206	llvm::iterator_range<reverse_iterator> reverse() {
207	return llvm::make_range(rbegin(), rend());
208	}
209
210	llvm::iterator_range<const_reverse_iterator> reverse() const {
211	return llvm::make_range(rbegin(), rend());
212	}
213
214	private:
215	// std::max is annoying here, because it requires a reference,
216	// thus forcing InitialCapacity to be initialized outside the .h file.
217	size_t u_max(size_t i, size_t j) { return (i < j) ? j : i; }
218
219	static const size_t InitialCapacity = 4;
220
221	T *Data = nullptr;
222	size_t Size = 0;
223	size_t Capacity = 0;
224	};
225
226	} // namespace til
227
228	// A copy on write vector.
229	// The vector can be in one of three states:
230	// * invalid -- no operations are permitted.
231	// * read-only -- read operations are permitted.
232	// * writable -- read and write operations are permitted.
233	// The init(), destroy(), and makeWritable() methods will change state.
234	template<typename T>
235	class CopyOnWriteVector {
236	class VectorData {
237	public:
238	unsigned NumRefs = 1;
239	std::vector<T> Vect;
240
241	VectorData() = default;
242	VectorData(const VectorData &VD) : Vect(VD.Vect) {}
243	};
244
245	public:
246	CopyOnWriteVector() = default;
247	CopyOnWriteVector(CopyOnWriteVector &&V) : Data(V.Data) { V.Data = nullptr; }
248
249	CopyOnWriteVector &operator=(CopyOnWriteVector &&V) {
250	destroy();
251	Data = V.Data;
252	V.Data = nullptr;
253	return *this;
254	}
255
256	// No copy constructor or copy assignment. Use clone() with move assignment.
257	CopyOnWriteVector(const CopyOnWriteVector &) = delete;
258	CopyOnWriteVector &operator=(const CopyOnWriteVector &) = delete;
259
260	~CopyOnWriteVector() { destroy(); }
261
262	// Returns true if this holds a valid vector.
263	bool valid() const { return Data; }
264
265	// Returns true if this vector is writable.
266	bool writable() const { return Data && Data->NumRefs == 1; }
267
268	// If this vector is not valid, initialize it to a valid vector.
269	void init() {
270	if (!Data) {
271	Data = new VectorData();
272	}
273	}
274
275	// Destroy this vector; thus making it invalid.
276	void destroy() {
277	if (!Data)
278	return;
279	if (Data->NumRefs <= 1)
280	delete Data;
281	else
282	--Data->NumRefs;
283	Data = nullptr;
284	}
285
286	// Make this vector writable, creating a copy if needed.
287	void makeWritable() {
288	if (!Data) {
289	Data = new VectorData();
290	return;
291	}
292	if (Data->NumRefs == 1)
293	return; // already writeable.
294	--Data->NumRefs;
295	Data = new VectorData(*Data);
296	}
297
298	// Create a lazy copy of this vector.
299	CopyOnWriteVector clone() { return CopyOnWriteVector(Data); }
300
301	using const_iterator = typename std::vector<T>::const_iterator;
302
303	const std::vector<T> &elements() const { return Data->Vect; }
304
305	const_iterator begin() const { return elements().cbegin(); }
306	const_iterator end() const { return elements().cend(); }
307
308	const T& operator[](unsigned i) const { return elements()[i]; }
309
310	unsigned size() const { return Data ? elements().size() : 0; }
311
312	// Return true if V and this vector refer to the same data.
313	bool sameAs(const CopyOnWriteVector &V) const { return Data == V.Data; }
314
315	// Clear vector. The vector must be writable.
316	void clear() {
317	(0) . __assert_fail ("writable() && \"Vector is not writable!\"", "/home/seafit/code_projects/clang_source/clang/include/clang/Analysis/Analyses/ThreadSafetyUtil.h", 317, __PRETTY_FUNCTION__))" file_link="../../../../../include/assert.h.html#88" macro="true">assert(writable() && "Vector is not writable!");
318	Data->Vect.clear();
319	}
320
321	// Push a new element onto the end. The vector must be writable.
322	void push_back(const T &Elem) {
323	(0) . __assert_fail ("writable() && \"Vector is not writable!\"", "/home/seafit/code_projects/clang_source/clang/include/clang/Analysis/Analyses/ThreadSafetyUtil.h", 323, __PRETTY_FUNCTION__))" file_link="../../../../../include/assert.h.html#88" macro="true">assert(writable() && "Vector is not writable!");
324	Data->Vect.push_back(Elem);
325	}
326
327	// Gets a mutable reference to the element at index(i).
328	// The vector must be writable.
329	T& elem(unsigned i) {
330	(0) . __assert_fail ("writable() && \"Vector is not writable!\"", "/home/seafit/code_projects/clang_source/clang/include/clang/Analysis/Analyses/ThreadSafetyUtil.h", 330, __PRETTY_FUNCTION__))" file_link="../../../../../include/assert.h.html#88" macro="true">assert(writable() && "Vector is not writable!");
331	return Data->Vect[i];
332	}
333
334	// Drops elements from the back until the vector has size i.
335	void downsize(unsigned i) {
336	(0) . __assert_fail ("writable() && \"Vector is not writable!\"", "/home/seafit/code_projects/clang_source/clang/include/clang/Analysis/Analyses/ThreadSafetyUtil.h", 336, __PRETTY_FUNCTION__))" file_link="../../../../../include/assert.h.html#88" macro="true">assert(writable() && "Vector is not writable!");
337	Data->Vect.erase(Data->Vect.begin() + i, Data->Vect.end());
338	}
339
340	private:
341	CopyOnWriteVector(VectorData *D) : Data(D) {
342	if (!Data)
343	return;
344	++Data->NumRefs;
345	}
346
347	VectorData *Data = nullptr;
348	};
349
350	inline std::ostream& operator<<(std::ostream& ss, const StringRef str) {
351	return ss.write(str.data(), str.size());
352	}
353
354	} // namespace threadSafety
355	} // namespace clang
356
357	#endif // LLVM_CLANG_THREAD_SAFETY_UTIL_H
358