Redeclarable.h source code [clang_source_code/include/clang/AST/Redeclarable.h]

1	//===- Redeclarable.h - Base for Decls that can be redeclared --- 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 the Redeclarable interface.
10	//
11	//===----------------------------------------------------------------------===//
12
13	#ifndef LLVM_CLANG_AST_REDECLARABLE_H
14	#define LLVM_CLANG_AST_REDECLARABLE_H
15
16	#include "clang/AST/ExternalASTSource.h"
17	#include "llvm/ADT/DenseMapInfo.h"
18	#include "llvm/ADT/PointerUnion.h"
19	#include "llvm/ADT/iterator_range.h"
20	#include "llvm/Support/Casting.h"
21	#include <cassert>
22	#include <cstddef>
23	#include <iterator>
24
25	namespace clang {
26
27	class ASTContext;
28	class Decl;
29
30	// Some notes on redeclarables:
31	//
32	// - Every redeclarable is on a circular linked list.
33	//
34	// - Every decl has a pointer to the first element of the chain _and_ a
35	// DeclLink that may point to one of 3 possible states:
36	// - the "previous" (temporal) element in the chain
37	// - the "latest" (temporal) element in the chain
38	// - the "uninitialized-latest" value (when newly-constructed)
39	//
40	// - The first element is also often called the canonical element. Every
41	// element has a pointer to it so that "getCanonical" can be fast.
42	//
43	// - Most links in the chain point to previous, except the link out of
44	// the first; it points to latest.
45	//
46	// - Elements are called "first", "previous", "latest" or
47	// "most-recent" when referring to temporal order: order of addition
48	// to the chain.
49	//
50	// - It's easiest to just ignore the implementation of DeclLink when making
51	// sense of the redeclaration chain.
52	//
53	// - There's also a "definition" link for several types of
54	// redeclarable, where only one definition should exist at any given
55	// time (and the defn pointer is stored in the decl's "data" which
56	// is copied to every element on the chain when it's changed).
57	//
58	// Here is some ASCII art:
59	//
60	// "first" "latest"
61	// "canonical" "most recent"
62	// +------------+ first +--------------+
63	// \| \| <--------------------------- \| \|
64	// \| \| \| \|
65	// \| \| \| \|
66	// \| \| +--------------+ \| \|
67	// \| \| first \| \| \| \|
68	// \| \| <---- \| \| \| \|
69	// \| \| \| \| \| \|
70	// \| @class A \| link \| @interface A \| link \| @class A \|
71	// \| seen first \| <---- \| seen second \| <---- \| seen third \|
72	// \| \| \| \| \| \|
73	// +------------+ +--------------+ +--------------+
74	// \| data \| defn \| data \| defn \| data \|
75	// \| \| ----> \| \| <---- \| \|
76	// +------------+ +--------------+ +--------------+
77	// \| \| ^ ^
78	// \| \|defn \| \|
79	// \| link +-----+ \|
80	// +-->-------------------------------------------+
81
82	/// Provides common interface for the Decls that can be redeclared.
83	template<typename decl_type>
84	class Redeclarable {
85	protected:
86	class DeclLink {
87	/// A pointer to a known latest declaration, either statically known or
88	/// generationally updated as decls are added by an external source.
89	using KnownLatest =
90	LazyGenerationalUpdatePtr<const Decl , Decl ,
91	&ExternalASTSource::CompleteRedeclChain>;
92
93	/// We store a pointer to the ASTContext in the UninitializedLatest
94	/// pointer, but to avoid circular type dependencies when we steal the low
95	/// bits of this pointer, we use a raw void* here.
96	using UninitializedLatest = const void *;
97
98	using Previous = Decl *;
99
100	/// A pointer to either an uninitialized latest declaration (where either
101	/// we've not yet set the previous decl or there isn't one), or to a known
102	/// previous declaration.
103	using NotKnownLatest = llvm::PointerUnion<Previous, UninitializedLatest>;
104
105	mutable llvm::PointerUnion<NotKnownLatest, KnownLatest> Link;
106
107	public:
108	enum PreviousTag { PreviousLink };
109	enum LatestTag { LatestLink };
110
111	DeclLink(LatestTag, const ASTContext &Ctx)
112	: Link(NotKnownLatest(reinterpret_cast<UninitializedLatest>(&Ctx))) {}
113	DeclLink(PreviousTag, decl_type *D) : Link(NotKnownLatest(Previous(D))) {}
114
115	bool isFirst() const {
116	return Link.is<KnownLatest>() \|\|
117	// FIXME: 'template' is required on the next line due to an
118	// apparent clang bug.
119	Link.get<NotKnownLatest>().template is<UninitializedLatest>();
120	}
121
122	decl_type getPrevious(const decl_type D) const {
123	if (Link.is<NotKnownLatest>()) {
124	NotKnownLatest NKL = Link.get<NotKnownLatest>();
125	if (NKL.is<Previous>())
126	return static_cast<decl_type*>(NKL.get<Previous>());
127
128	// Allocate the generational 'most recent' cache now, if needed.
129	Link = KnownLatest(reinterpret_cast<const ASTContext >(
130	NKL.get<UninitializedLatest>()),
131	const_cast<decl_type *>(D));
132	}
133
134	return static_cast<decl_type*>(Link.get<KnownLatest>().get(D));
135	}
136
137	void setPrevious(decl_type *D) {
138	(0) . __assert_fail ("!isFirst() && \"decl became non-canonical unexpectedly\"", "/home/seafit/code_projects/clang_source/clang/include/clang/AST/Redeclarable.h", 138, __PRETTY_FUNCTION__))" file_link="../../../../include/assert.h.html#88" macro="true">assert(!isFirst() && "decl became non-canonical unexpectedly");
139	Link = Previous(D);
140	}
141
142	void setLatest(decl_type *D) {
143	(0) . __assert_fail ("isFirst() && \"decl became canonical unexpectedly\"", "/home/seafit/code_projects/clang_source/clang/include/clang/AST/Redeclarable.h", 143, __PRETTY_FUNCTION__))" file_link="../../../../include/assert.h.html#88" macro="true">assert(isFirst() && "decl became canonical unexpectedly");
144	if (Link.is<NotKnownLatest>()) {
145	NotKnownLatest NKL = Link.get<NotKnownLatest>();
146	Link = KnownLatest(reinterpret_cast<const ASTContext >(
147	NKL.get<UninitializedLatest>()),
148	D);
149	} else {
150	auto Latest = Link.get<KnownLatest>();
151	Latest.set(D);
152	Link = Latest;
153	}
154	}
155
156	void markIncomplete() { Link.get<KnownLatest>().markIncomplete(); }
157
158	Decl *getLatestNotUpdated() const {
159	(0) . __assert_fail ("isFirst() && \"expected a canonical decl\"", "/home/seafit/code_projects/clang_source/clang/include/clang/AST/Redeclarable.h", 159, __PRETTY_FUNCTION__))" file_link="../../../../include/assert.h.html#88" macro="true">assert(isFirst() && "expected a canonical decl");
160	if (Link.is<NotKnownLatest>())
161	return nullptr;
162	return Link.get<KnownLatest>().getNotUpdated();
163	}
164	};
165
166	static DeclLink PreviousDeclLink(decl_type *D) {
167	return DeclLink(DeclLink::PreviousLink, D);
168	}
169
170	static DeclLink LatestDeclLink(const ASTContext &Ctx) {
171	return DeclLink(DeclLink::LatestLink, Ctx);
172	}
173
174	/// Points to the next redeclaration in the chain.
175	///
176	/// If isFirst() is false, this is a link to the previous declaration
177	/// of this same Decl. If isFirst() is true, this is the first
178	/// declaration and Link points to the latest declaration. For example:
179	///
180	/// #1 int f(int x, int y = 1); // <pointer to #3, true>
181	/// #2 int f(int x = 0, int y); // <pointer to #1, false>
182	/// #3 int f(int x, int y) { return x + y; } // <pointer to #2, false>
183	///
184	/// If there is only one declaration, it is <pointer to self, true>
185	DeclLink RedeclLink;
186
187	decl_type *First;
188
189	decl_type *getNextRedeclaration() const {
190	return RedeclLink.getPrevious(static_cast<const decl_type *>(this));
191	}
192
193	public:
194	friend class ASTDeclReader;
195	friend class ASTDeclWriter;
196
197	Redeclarable(const ASTContext &Ctx)
198	: RedeclLink(LatestDeclLink(Ctx)),
199	First(static_cast<decl_type *>(this)) {}
200
201	/// Return the previous declaration of this declaration or NULL if this
202	/// is the first declaration.
203	decl_type *getPreviousDecl() {
204	if (!RedeclLink.isFirst())
205	return getNextRedeclaration();
206	return nullptr;
207	}
208	const decl_type *getPreviousDecl() const {
209	return const_cast<decl_type *>(
210	static_cast<const decl_type*>(this))->getPreviousDecl();
211	}
212
213	/// Return the first declaration of this declaration or itself if this
214	/// is the only declaration.
215	decl_type *getFirstDecl() { return First; }
216
217	/// Return the first declaration of this declaration or itself if this
218	/// is the only declaration.
219	const decl_type *getFirstDecl() const { return First; }
220
221	/// True if this is the first declaration in its redeclaration chain.
222	bool isFirstDecl() const { return RedeclLink.isFirst(); }
223
224	/// Returns the most recent (re)declaration of this declaration.
225	decl_type *getMostRecentDecl() {
226	return getFirstDecl()->getNextRedeclaration();
227	}
228
229	/// Returns the most recent (re)declaration of this declaration.
230	const decl_type *getMostRecentDecl() const {
231	return getFirstDecl()->getNextRedeclaration();
232	}
233
234	/// Set the previous declaration. If PrevDecl is NULL, set this as the
235	/// first and only declaration.
236	void setPreviousDecl(decl_type *PrevDecl);
237
238	/// Iterates through all the redeclarations of the same decl.
239	class redecl_iterator {
240	/// Current - The current declaration.
241	decl_type *Current = nullptr;
242	decl_type *Starter;
243	bool PassedFirst = false;
244
245	public:
246	using value_type = decl_type *;
247	using reference = decl_type *;
248	using pointer = decl_type *;
249	using iterator_category = std::forward_iterator_tag;
250	using difference_type = std::ptrdiff_t;
251
252	redecl_iterator() = default;
253	explicit redecl_iterator(decl_type *C) : Current(C), Starter(C) {}
254
255	reference operator*() const { return Current; }
256	pointer operator->() const { return Current; }
257
258	redecl_iterator& operator++() {
259	(0) . __assert_fail ("Current && \"Advancing while iterator has reached end\"", "/home/seafit/code_projects/clang_source/clang/include/clang/AST/Redeclarable.h", 259, __PRETTY_FUNCTION__))" file_link="../../../../include/assert.h.html#88" macro="true">assert(Current && "Advancing while iterator has reached end");
260	// Sanity check to avoid infinite loop on invalid redecl chain.
261	if (Current->isFirstDecl()) {
262	if (PassedFirst) {
263	(0) . __assert_fail ("0 && \"Passed first decl twice, invalid redecl chain!\"", "/home/seafit/code_projects/clang_source/clang/include/clang/AST/Redeclarable.h", 263, __PRETTY_FUNCTION__))" file_link="../../../../include/assert.h.html#88" macro="true">assert(0 && "Passed first decl twice, invalid redecl chain!");
264	Current = nullptr;
265	return *this;
266	}
267	PassedFirst = true;
268	}
269
270	// Get either previous decl or latest decl.
271	decl_type *Next = Current->getNextRedeclaration();
272	Current = (Next != Starter) ? Next : nullptr;
273	return *this;
274	}
275
276	redecl_iterator operator++(int) {
277	redecl_iterator tmp(*this);
278	++(*this);
279	return tmp;
280	}
281
282	friend bool operator==(redecl_iterator x, redecl_iterator y) {
283	return x.Current == y.Current;
284	}
285	friend bool operator!=(redecl_iterator x, redecl_iterator y) {
286	return x.Current != y.Current;
287	}
288	};
289
290	using redecl_range = llvm::iterator_range<redecl_iterator>;
291
292	/// Returns an iterator range for all the redeclarations of the same
293	/// decl. It will iterate at least once (when this decl is the only one).
294	redecl_range redecls() const {
295	return redecl_range(redecl_iterator(const_cast<decl_type *>(
296	static_cast<const decl_type *>(this))),
297	redecl_iterator());
298	}
299
300	redecl_iterator redecls_begin() const { return redecls().begin(); }
301	redecl_iterator redecls_end() const { return redecls().end(); }
302	};
303
304	/// Get the primary declaration for a declaration from an AST file. That
305	/// will be the first-loaded declaration.
306	Decl getPrimaryMergedDecl(Decl D);
307
308	/// Provides common interface for the Decls that cannot be redeclared,
309	/// but can be merged if the same declaration is brought in from multiple
310	/// modules.
311	template<typename decl_type>
312	class Mergeable {
313	public:
314	Mergeable() = default;
315
316	/// Return the first declaration of this declaration or itself if this
317	/// is the only declaration.
318	decl_type *getFirstDecl() {
319	auto D = static_cast<decl_type >(this);
320	if (!D->isFromASTFile())
321	return D;
322	return cast<decl_type>(getPrimaryMergedDecl(const_cast<decl_type*>(D)));
323	}
324
325	/// Return the first declaration of this declaration or itself if this
326	/// is the only declaration.
327	const decl_type *getFirstDecl() const {
328	const auto D = static_cast<const decl_type >(this);
329	if (!D->isFromASTFile())
330	return D;
331	return cast<decl_type>(getPrimaryMergedDecl(const_cast<decl_type*>(D)));
332	}
333
334	/// Returns true if this is the first declaration.
335	bool isFirstDecl() const { return getFirstDecl() == this; }
336	};
337
338	/// A wrapper class around a pointer that always points to its canonical
339	/// declaration.
340	///
341	/// CanonicalDeclPtr<decl_type> behaves just like decl_type*, except we call
342	/// decl_type::getCanonicalDecl() on construction.
343	///
344	/// This is useful for hashtables that you want to be keyed on a declaration's
345	/// canonical decl -- if you use CanonicalDeclPtr as the key, you don't need to
346	/// remember to call getCanonicalDecl() everywhere.
347	template <typename decl_type> class CanonicalDeclPtr {
348	public:
349	CanonicalDeclPtr() = default;
350	CanonicalDeclPtr(decl_type *Ptr)
351	: Ptr(Ptr ? Ptr->getCanonicalDecl() : nullptr) {}
352	CanonicalDeclPtr(const CanonicalDeclPtr &) = default;
353	CanonicalDeclPtr &operator=(const CanonicalDeclPtr &) = default;
354
355	operator decl_type *() { return Ptr; }
356	operator const decl_type *() const { return Ptr; }
357
358	decl_type *operator->() { return Ptr; }
359	const decl_type *operator->() const { return Ptr; }
360
361	decl_type &operator() { return Ptr; }
362	const decl_type &operator() const { return Ptr; }
363
364	private:
365	friend struct llvm::DenseMapInfo<CanonicalDeclPtr<decl_type>>;
366
367	decl_type *Ptr = nullptr;
368	};
369
370	} // namespace clang
371
372	namespace llvm {
373
374	template <typename decl_type>
375	struct DenseMapInfo<clang::CanonicalDeclPtr<decl_type>> {
376	using CanonicalDeclPtr = clang::CanonicalDeclPtr<decl_type>;
377	using BaseInfo = DenseMapInfo<decl_type *>;
378
379	static CanonicalDeclPtr getEmptyKey() {
380	// Construct our CanonicalDeclPtr this way because the regular constructor
381	// would dereference P.Ptr, which is not allowed.
382	CanonicalDeclPtr P;
383	P.Ptr = BaseInfo::getEmptyKey();
384	return P;
385	}
386
387	static CanonicalDeclPtr getTombstoneKey() {
388	CanonicalDeclPtr P;
389	P.Ptr = BaseInfo::getTombstoneKey();
390	return P;
391	}
392
393	static unsigned getHashValue(const CanonicalDeclPtr &P) {
394	return BaseInfo::getHashValue(P);
395	}
396
397	static bool isEqual(const CanonicalDeclPtr &LHS,
398	const CanonicalDeclPtr &RHS) {
399	return BaseInfo::isEqual(LHS, RHS);
400	}
401	};
402
403	} // namespace llvm
404
405	#endif // LLVM_CLANG_AST_REDECLARABLE_H
406