1	//===- ASTMatchersInternal.h - Structural query framework -------*- 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	// Implements the base layer of the matcher framework.
10	//
11	// Matchers are methods that return a Matcher<T> which provides a method
12	// Matches(...) which is a predicate on an AST node. The Matches method's
13	// parameters define the context of the match, which allows matchers to recurse
14	// or store the current node as bound to a specific string, so that it can be
15	// retrieved later.
16	//
17	// In general, matchers have two parts:
18	// 1. A function Matcher<T> MatcherName(<arguments>) which returns a Matcher<T>
19	// based on the arguments and optionally on template type deduction based
20	// on the arguments. Matcher<T>s form an implicit reverse hierarchy
21	// to clang's AST class hierarchy, meaning that you can use a Matcher<Base>
22	// everywhere a Matcher<Derived> is required.
23	// 2. An implementation of a class derived from MatcherInterface<T>.
24	//
25	// The matcher functions are defined in ASTMatchers.h. To make it possible
26	// to implement both the matcher function and the implementation of the matcher
27	// interface in one place, ASTMatcherMacros.h defines macros that allow
28	// implementing a matcher in a single place.
29	//
30	// This file contains the base classes needed to construct the actual matchers.
31	//
32	//===----------------------------------------------------------------------===//
33
34	#ifndef LLVM_CLANG_ASTMATCHERS_ASTMATCHERSINTERNAL_H
35	#define LLVM_CLANG_ASTMATCHERS_ASTMATCHERSINTERNAL_H
36
37	#include "clang/AST/ASTTypeTraits.h"
38	#include "clang/AST/Decl.h"
39	#include "clang/AST/DeclCXX.h"
40	#include "clang/AST/DeclFriend.h"
41	#include "clang/AST/DeclTemplate.h"
42	#include "clang/AST/Expr.h"
43	#include "clang/AST/ExprCXX.h"
44	#include "clang/AST/ExprObjC.h"
45	#include "clang/AST/NestedNameSpecifier.h"
46	#include "clang/AST/Stmt.h"
47	#include "clang/AST/TemplateName.h"
48	#include "clang/AST/Type.h"
49	#include "clang/AST/TypeLoc.h"
50	#include "clang/Basic/LLVM.h"
51	#include "clang/Basic/OperatorKinds.h"
52	#include "llvm/ADT/APFloat.h"
53	#include "llvm/ADT/ArrayRef.h"
54	#include "llvm/ADT/IntrusiveRefCntPtr.h"
55	#include "llvm/ADT/STLExtras.h"
56	#include "llvm/ADT/SmallVector.h"
57	#include "llvm/ADT/StringRef.h"
58	#include "llvm/ADT/iterator.h"
59	#include "llvm/Support/Casting.h"
60	#include "llvm/Support/ManagedStatic.h"
61	#include "llvm/Support/Regex.h"
62	#include <algorithm>
63	#include <cassert>
64	#include <cstddef>
65	#include <cstdint>
66	#include <map>
67	#include <memory>
68	#include <optional>
69	#include <string>
70	#include <tuple>
71	#include <type_traits>
72	#include <utility>
73	#include <vector>
74
75	namespace clang {
76
77	class ASTContext;
78
79	namespace ast_matchers {
80
81	class BoundNodes;
82
83	namespace internal {
84
85	/// A type-list implementation.
86	///
87	/// A "linked list" of types, accessible by using the ::head and ::tail
88	/// typedefs.
89	template <typename... Ts> struct TypeList {}; // Empty sentinel type list.
90
91	template <typename T1, typename... Ts> struct TypeList<T1, Ts...> {
92	/// The first type on the list.
93	using head = T1;
94
95	/// A sublist with the tail. ie everything but the head.
96	///
97	/// This type is used to do recursion. TypeList<>/EmptyTypeList indicates the
98	/// end of the list.
99	using tail = TypeList<Ts...>;
100	};
101
102	/// The empty type list.
103	using EmptyTypeList = TypeList<>;
104
105	/// Helper meta-function to determine if some type \c T is present or
106	/// a parent type in the list.
107	template <typename AnyTypeList, typename T> struct TypeListContainsSuperOf {
108	static const bool value =
109	std::is_base_of<typename AnyTypeList::head, T>::value ||
110	TypeListContainsSuperOf<typename AnyTypeList::tail, T>::value;
111	};
112	template <typename T> struct TypeListContainsSuperOf<EmptyTypeList, T> {
113	static const bool value = false;
114	};
115
116	/// Variadic function object.
117	///
118	/// Most of the functions below that use VariadicFunction could be implemented
119	/// using plain C++11 variadic functions, but the function object allows us to
120	/// capture it on the dynamic matcher registry.
121	template <typename ResultT, typename ArgT,
122	ResultT (*Func)(ArrayRef<const ArgT *>)>
123	struct VariadicFunction {
124	ResultT operator()() const { return Func(std::nullopt); }
125
126	template <typename... ArgsT>
127	ResultT operator()(const ArgT &Arg1, const ArgsT &... Args) const {
128	return Execute(Arg1, static_cast<const ArgT &>(Args)...);
129	}
130
131	// We also allow calls with an already created array, in case the caller
132	// already had it.
133	ResultT operator()(ArrayRef<ArgT> Args) const {
134	return Func(llvm::to_vector<8>(llvm::make_pointer_range(Args)));
135	}
136
137	private:
138	// Trampoline function to allow for implicit conversions to take place
139	// before we make the array.
140	template <typename... ArgsT> ResultT Execute(const ArgsT &... Args) const {
141	const ArgT *const ArgsArray[] = {&Args...};
142	return Func(ArrayRef<const ArgT *>(ArgsArray, sizeof...(ArgsT)));
143	}
144	};
145
146	/// Unifies obtaining the underlying type of a regular node through
147	/// `getType` and a TypedefNameDecl node through `getUnderlyingType`.
148	inline QualType getUnderlyingType(const Expr &Node) { return Node.getType(); }
149
150	inline QualType getUnderlyingType(const ValueDecl &Node) {
151	return Node.getType();
152	}
153	inline QualType getUnderlyingType(const TypedefNameDecl &Node) {
154	return Node.getUnderlyingType();
155	}
156	inline QualType getUnderlyingType(const FriendDecl &Node) {
157	if (const TypeSourceInfo *TSI = Node.getFriendType())
158	return TSI->getType();
159	return QualType();
160	}
161	inline QualType getUnderlyingType(const CXXBaseSpecifier &Node) {
162	return Node.getType();
163	}
164
165	/// Unifies obtaining a `TypeSourceInfo` from different node types.
166	template <typename T,
167	std::enable_if_t<TypeListContainsSuperOf<
168	TypeList<CXXBaseSpecifier, CXXCtorInitializer,
169	CXXTemporaryObjectExpr, CXXUnresolvedConstructExpr,
170	CompoundLiteralExpr, DeclaratorDecl, ObjCPropertyDecl,
171	TemplateArgumentLoc, TypedefNameDecl>,
172	T>::value> * = nullptr>
173	inline TypeSourceInfo *GetTypeSourceInfo(const T &Node) {
174	return Node.getTypeSourceInfo();
175	}
176	template <typename T,
177	std::enable_if_t<TypeListContainsSuperOf<
178	TypeList<CXXFunctionalCastExpr, ExplicitCastExpr>, T>::value> * =
179	nullptr>
180	inline TypeSourceInfo *GetTypeSourceInfo(const T &Node) {
181	return Node.getTypeInfoAsWritten();
182	}
183	inline TypeSourceInfo *GetTypeSourceInfo(const BlockDecl &Node) {
184	return Node.getSignatureAsWritten();
185	}
186	inline TypeSourceInfo *GetTypeSourceInfo(const CXXNewExpr &Node) {
187	return Node.getAllocatedTypeSourceInfo();
188	}
189	inline TypeSourceInfo *
190	GetTypeSourceInfo(const ClassTemplateSpecializationDecl &Node) {
191	return Node.getTypeAsWritten();
192	}
193
194	/// Unifies obtaining the FunctionProtoType pointer from both
195	/// FunctionProtoType and FunctionDecl nodes..
196	inline const FunctionProtoType *
197	getFunctionProtoType(const FunctionProtoType &Node) {
198	return &Node;
199	}
200
201	inline const FunctionProtoType *getFunctionProtoType(const FunctionDecl &Node) {
202	return Node.getType()->getAs<FunctionProtoType>();
203	}
204
205	/// Unifies obtaining the access specifier from Decl and CXXBaseSpecifier nodes.
206	inline clang::AccessSpecifier getAccessSpecifier(const Decl &Node) {
207	return Node.getAccess();
208	}
209
210	inline clang::AccessSpecifier getAccessSpecifier(const CXXBaseSpecifier &Node) {
211	return Node.getAccessSpecifier();
212	}
213
214	/// Internal version of BoundNodes. Holds all the bound nodes.
215	class BoundNodesMap {
216	public:
217	/// Adds \c Node to the map with key \c ID.
218	///
219	/// The node's base type should be in NodeBaseType or it will be unaccessible.
220	void addNode(StringRef ID, const DynTypedNode &DynNode) {
221	NodeMap[std::string(ID)] = DynNode;
222	}
223
224	/// Returns the AST node bound to \c ID.
225	///
226	/// Returns NULL if there was no node bound to \c ID or if there is a node but
227	/// it cannot be converted to the specified type.
228	template <typename T>
229	const T *getNodeAs(StringRef ID) const {
230	IDToNodeMap::const_iterator It = NodeMap.find(x: ID);
231	if (It == NodeMap.end()) {
232	return nullptr;
233	}
234	return It->second.get<T>();
235	}
236
237	DynTypedNode getNode(StringRef ID) const {
238	IDToNodeMap::const_iterator It = NodeMap.find(x: ID);
239	if (It == NodeMap.end()) {
240	return DynTypedNode();
241	}
242	return It->second;
243	}
244
245	/// Imposes an order on BoundNodesMaps.
246	bool operator<(const BoundNodesMap &Other) const {
247	return NodeMap < Other.NodeMap;
248	}
249
250	/// A map from IDs to the bound nodes.
251	///
252	/// Note that we're using std::map here, as for memoization:
253	/// - we need a comparison operator
254	/// - we need an assignment operator
255	using IDToNodeMap = std::map<std::string, DynTypedNode, std::less<>>;
256
257	const IDToNodeMap &getMap() const {
258	return NodeMap;
259	}
260
261	/// Returns \c true if this \c BoundNodesMap can be compared, i.e. all
262	/// stored nodes have memoization data.
263	bool isComparable() const {
264	for (const auto &IDAndNode : NodeMap) {
265	if (!IDAndNode.second.getMemoizationData())
266	return false;
267	}
268	return true;
269	}
270
271	private:
272	IDToNodeMap NodeMap;
273	};
274
275	/// Creates BoundNodesTree objects.
276	///
277	/// The tree builder is used during the matching process to insert the bound
278	/// nodes from the Id matcher.
279	class BoundNodesTreeBuilder {
280	public:
281	/// A visitor interface to visit all BoundNodes results for a
282	/// BoundNodesTree.
283	class Visitor {
284	public:
285	virtual ~Visitor() = default;
286
287	/// Called multiple times during a single call to VisitMatches(...).
288	///
289	/// 'BoundNodesView' contains the bound nodes for a single match.
290	virtual void visitMatch(const BoundNodes& BoundNodesView) = 0;
291	};
292
293	/// Add a binding from an id to a node.
294	void setBinding(StringRef Id, const DynTypedNode &DynNode) {
295	if (Bindings.empty())
296	Bindings.emplace_back();
297	for (BoundNodesMap &Binding : Bindings)
298	Binding.addNode(ID: Id, DynNode);
299	}
300
301	/// Adds a branch in the tree.
302	void addMatch(const BoundNodesTreeBuilder &Bindings);
303
304	/// Visits all matches that this BoundNodesTree represents.
305	///
306	/// The ownership of 'ResultVisitor' remains at the caller.
307	void visitMatches(Visitor* ResultVisitor);
308
309	template <typename ExcludePredicate>
310	bool removeBindings(const ExcludePredicate &Predicate) {
311	llvm::erase_if(Bindings, Predicate);
312	return !Bindings.empty();
313	}
314
315	/// Imposes an order on BoundNodesTreeBuilders.
316	bool operator<(const BoundNodesTreeBuilder &Other) const {
317	return Bindings < Other.Bindings;
318	}
319
320	/// Returns \c true if this \c BoundNodesTreeBuilder can be compared,
321	/// i.e. all stored node maps have memoization data.
322	bool isComparable() const {
323	for (const BoundNodesMap &NodesMap : Bindings) {
324	if (!NodesMap.isComparable())
325	return false;
326	}
327	return true;
328	}
329
330	private:
331	SmallVector<BoundNodesMap, 1> Bindings;
332	};
333
334	class ASTMatchFinder;
335
336	/// Generic interface for all matchers.
337	///
338	/// Used by the implementation of Matcher<T> and DynTypedMatcher.
339	/// In general, implement MatcherInterface<T> or SingleNodeMatcherInterface<T>
340	/// instead.
341	class DynMatcherInterface
342	: public llvm::ThreadSafeRefCountedBase<DynMatcherInterface> {
343	public:
344	virtual ~DynMatcherInterface() = default;
345
346	/// Returns true if \p DynNode can be matched.
347	///
348	/// May bind \p DynNode to an ID via \p Builder, or recurse into
349	/// the AST via \p Finder.
350	virtual bool dynMatches(const DynTypedNode &DynNode, ASTMatchFinder *Finder,
351	BoundNodesTreeBuilder *Builder) const = 0;
352
353	virtual std::optional<clang::TraversalKind> TraversalKind() const {
354	return std::nullopt;
355	}
356	};
357
358	/// Generic interface for matchers on an AST node of type T.
359	///
360	/// Implement this if your matcher may need to inspect the children or
361	/// descendants of the node or bind matched nodes to names. If you are
362	/// writing a simple matcher that only inspects properties of the
363	/// current node and doesn't care about its children or descendants,
364	/// implement SingleNodeMatcherInterface instead.
365	template <typename T>
366	class MatcherInterface : public DynMatcherInterface {
367	public:
368	/// Returns true if 'Node' can be matched.
369	///
370	/// May bind 'Node' to an ID via 'Builder', or recurse into
371	/// the AST via 'Finder'.
372	virtual bool matches(const T &Node,
373	ASTMatchFinder *Finder,
374	BoundNodesTreeBuilder *Builder) const = 0;
375
376	bool dynMatches(const DynTypedNode &DynNode, ASTMatchFinder *Finder,
377	BoundNodesTreeBuilder *Builder) const override {
378	return matches(Node: DynNode.getUnchecked<T>(), Finder, Builder);
379	}
380	};
381
382	/// Interface for matchers that only evaluate properties on a single
383	/// node.
384	template <typename T>
385	class SingleNodeMatcherInterface : public MatcherInterface<T> {
386	public:
387	/// Returns true if the matcher matches the provided node.
388	///
389	/// A subclass must implement this instead of Matches().
390	virtual bool matchesNode(const T &Node) const = 0;
391
392	private:
393	/// Implements MatcherInterface::Matches.
394	bool matches(const T &Node,
395	ASTMatchFinder * /* Finder */,
396	BoundNodesTreeBuilder * /* Builder */) const override {
397	return matchesNode(Node);
398	}
399	};
400
401	template <typename> class Matcher;
402
403	/// Matcher that works on a \c DynTypedNode.
404	///
405	/// It is constructed from a \c Matcher<T> object and redirects most calls to
406	/// underlying matcher.
407	/// It checks whether the \c DynTypedNode is convertible into the type of the
408	/// underlying matcher and then do the actual match on the actual node, or
409	/// return false if it is not convertible.
410	class DynTypedMatcher {
411	public:
412	/// Takes ownership of the provided implementation pointer.
413	template <typename T>
414	DynTypedMatcher(MatcherInterface<T> *Implementation)
415	: SupportedKind(ASTNodeKind::getFromNodeKind<T>()),
416	RestrictKind(SupportedKind), Implementation(Implementation) {}
417
418	/// Construct from a variadic function.
419	enum VariadicOperator {
420	/// Matches nodes for which all provided matchers match.
421	VO_AllOf,
422
423	/// Matches nodes for which at least one of the provided matchers
424	/// matches.
425	VO_AnyOf,
426
427	/// Matches nodes for which at least one of the provided matchers
428	/// matches, but doesn't stop at the first match.
429	VO_EachOf,
430
431	/// Matches any node but executes all inner matchers to find result
432	/// bindings.
433	VO_Optionally,
434
435	/// Matches nodes that do not match the provided matcher.
436	///
437	/// Uses the variadic matcher interface, but fails if
438	/// InnerMatchers.size() != 1.
439	VO_UnaryNot
440	};
441
442	static DynTypedMatcher
443	constructVariadic(VariadicOperator Op, ASTNodeKind SupportedKind,
444	std::vector<DynTypedMatcher> InnerMatchers);
445
446	static DynTypedMatcher
447	constructRestrictedWrapper(const DynTypedMatcher &InnerMatcher,
448	ASTNodeKind RestrictKind);
449
450	/// Get a "true" matcher for \p NodeKind.
451	///
452	/// It only checks that the node is of the right kind.
453	static DynTypedMatcher trueMatcher(ASTNodeKind NodeKind);
454
455	void setAllowBind(bool AB) { AllowBind = AB; }
456
457	/// Check whether this matcher could ever match a node of kind \p Kind.
458	/// \return \c false if this matcher will never match such a node. Otherwise,
459	/// return \c true.
460	bool canMatchNodesOfKind(ASTNodeKind Kind) const;
461
462	/// Return a matcher that points to the same implementation, but
463	/// restricts the node types for \p Kind.
464	DynTypedMatcher dynCastTo(const ASTNodeKind Kind) const;
465
466	/// Return a matcher that points to the same implementation, but sets the
467	/// traversal kind.
468	///
469	/// If the traversal kind is already set, then \c TK overrides it.
470	DynTypedMatcher withTraversalKind(TraversalKind TK);
471
472	/// Returns true if the matcher matches the given \c DynNode.
473	bool matches(const DynTypedNode &DynNode, ASTMatchFinder *Finder,
474	BoundNodesTreeBuilder *Builder) const;
475
476	/// Same as matches(), but skips the kind check.
477	///
478	/// It is faster, but the caller must ensure the node is valid for the
479	/// kind of this matcher.
480	bool matchesNoKindCheck(const DynTypedNode &DynNode, ASTMatchFinder *Finder,
481	BoundNodesTreeBuilder *Builder) const;
482
483	/// Bind the specified \p ID to the matcher.
484	/// \return A new matcher with the \p ID bound to it if this matcher supports
485	/// binding. Otherwise, returns an empty \c std::optional<>.
486	std::optional<DynTypedMatcher> tryBind(StringRef ID) const;
487
488	/// Returns a unique \p ID for the matcher.
489	///
490	/// Casting a Matcher<T> to Matcher<U> creates a matcher that has the
491	/// same \c Implementation pointer, but different \c RestrictKind. We need to
492	/// include both in the ID to make it unique.
493	///
494	/// \c MatcherIDType supports operator< and provides strict weak ordering.
495	using MatcherIDType = std::pair<ASTNodeKind, uint64_t>;
496	MatcherIDType getID() const {
497	/// FIXME: Document the requirements this imposes on matcher
498	/// implementations (no new() implementation_ during a Matches()).
499	return std::make_pair(x: RestrictKind,
500	y: reinterpret_cast<uint64_t>(Implementation.get()));
501	}
502
503	/// Returns the type this matcher works on.
504	///
505	/// \c matches() will always return false unless the node passed is of this
506	/// or a derived type.
507	ASTNodeKind getSupportedKind() const { return SupportedKind; }
508
509	/// Returns \c true if the passed \c DynTypedMatcher can be converted
510	/// to a \c Matcher<T>.
511	///
512	/// This method verifies that the underlying matcher in \c Other can process
513	/// nodes of types T.
514	template <typename T> bool canConvertTo() const {
515	return canConvertTo(ASTNodeKind::getFromNodeKind<T>());
516	}
517	bool canConvertTo(ASTNodeKind To) const;
518
519	/// Construct a \c Matcher<T> interface around the dynamic matcher.
520	///
521	/// This method asserts that \c canConvertTo() is \c true. Callers
522	/// should call \c canConvertTo() first to make sure that \c this is
523	/// compatible with T.
524	template <typename T> Matcher<T> convertTo() const {
525	assert(canConvertTo<T>());
526	return unconditionalConvertTo<T>();
527	}
528
529	/// Same as \c convertTo(), but does not check that the underlying
530	/// matcher can handle a value of T.
531	///
532	/// If it is not compatible, then this matcher will never match anything.
533	template <typename T> Matcher<T> unconditionalConvertTo() const;
534
535	/// Returns the \c TraversalKind respected by calls to `match()`, if any.
536	///
537	/// Most matchers will not have a traversal kind set, instead relying on the
538	/// surrounding context. For those, \c std::nullopt is returned.
539	std::optional<clang::TraversalKind> getTraversalKind() const {
540	return Implementation->TraversalKind();
541	}
542
543	private:
544	DynTypedMatcher(ASTNodeKind SupportedKind, ASTNodeKind RestrictKind,
545	IntrusiveRefCntPtr<DynMatcherInterface> Implementation)
546	: SupportedKind(SupportedKind), RestrictKind(RestrictKind),
547	Implementation(std::move(Implementation)) {}
548
549	bool AllowBind = false;
550	ASTNodeKind SupportedKind;
551
552	/// A potentially stricter node kind.
553	///
554	/// It allows to perform implicit and dynamic cast of matchers without
555	/// needing to change \c Implementation.
556	ASTNodeKind RestrictKind;
557	IntrusiveRefCntPtr<DynMatcherInterface> Implementation;
558	};
559
560	/// Wrapper of a MatcherInterface<T> *that allows copying.
561	///
562	/// A Matcher<Base> can be used anywhere a Matcher<Derived> is
563	/// required. This establishes an is-a relationship which is reverse
564	/// to the AST hierarchy. In other words, Matcher<T> is contravariant
565	/// with respect to T. The relationship is built via a type conversion
566	/// operator rather than a type hierarchy to be able to templatize the
567	/// type hierarchy instead of spelling it out.
568	template <typename T>
569	class Matcher {
570	public:
571	/// Takes ownership of the provided implementation pointer.
572	explicit Matcher(MatcherInterface<T> *Implementation)
573	: Implementation(Implementation) {}
574
575	/// Implicitly converts \c Other to a Matcher<T>.
576	///
577	/// Requires \c T to be derived from \c From.
578	template <typename From>
579	Matcher(const Matcher<From> &Other,
580	std::enable_if_t<std::is_base_of<From, T>::value &&
581	!std::is_same<From, T>::value> * = nullptr)
582	: Implementation(restrictMatcher(Other: Other.Implementation)) {
583	assert(Implementation.getSupportedKind().isSame(
584	ASTNodeKind::getFromNodeKind<T>()));
585	}
586
587	/// Implicitly converts \c Matcher<Type> to \c Matcher<QualType>.
588	///
589	/// The resulting matcher is not strict, i.e. ignores qualifiers.
590	template <typename TypeT>
591	Matcher(const Matcher<TypeT> &Other,
592	std::enable_if_t<std::is_same<T, QualType>::value &&
593	std::is_same<TypeT, Type>::value> * = nullptr)
594	: Implementation(new TypeToQualType<TypeT>(Other)) {}
595
596	/// Convert \c this into a \c Matcher<T> by applying dyn_cast<> to the
597	/// argument.
598	/// \c To must be a base class of \c T.
599	template <typename To> Matcher<To> dynCastTo() const & {
600	static_assert(std::is_base_of<To, T>::value, "Invalid dynCast call.");
601	return Matcher<To>(Implementation);
602	}
603
604	template <typename To> Matcher<To> dynCastTo() && {
605	static_assert(std::is_base_of<To, T>::value, "Invalid dynCast call.");
606	return Matcher<To>(std::move(Implementation));
607	}
608
609	/// Forwards the call to the underlying MatcherInterface<T> pointer.
610	bool matches(const T &Node,
611	ASTMatchFinder *Finder,
612	BoundNodesTreeBuilder *Builder) const {
613	return Implementation.matches(DynNode: DynTypedNode::create(Node), Finder, Builder);
614	}
615
616	/// Returns an ID that uniquely identifies the matcher.
617	DynTypedMatcher::MatcherIDType getID() const {
618	return Implementation.getID();
619	}
620
621	/// Extract the dynamic matcher.
622	///
623	/// The returned matcher keeps the same restrictions as \c this and remembers
624	/// that it is meant to support nodes of type \c T.
625	operator DynTypedMatcher() const & { return Implementation; }
626
627	operator DynTypedMatcher() && { return std::move(Implementation); }
628
629	/// Allows the conversion of a \c Matcher<Type> to a \c
630	/// Matcher<QualType>.
631	///
632	/// Depending on the constructor argument, the matcher is either strict, i.e.
633	/// does only matches in the absence of qualifiers, or not, i.e. simply
634	/// ignores any qualifiers.
635	template <typename TypeT>
636	class TypeToQualType : public MatcherInterface<QualType> {
637	const DynTypedMatcher InnerMatcher;
638
639	public:
640	TypeToQualType(const Matcher<TypeT> &InnerMatcher)
641	: InnerMatcher(InnerMatcher) {}
642
643	bool matches(const QualType &Node, ASTMatchFinder *Finder,
644	BoundNodesTreeBuilder *Builder) const override {
645	if (Node.isNull())
646	return false;
647	return this->InnerMatcher.matches(DynTypedNode::create(Node: *Node), Finder,
648	Builder);
649	}
650
651	std::optional<clang::TraversalKind> TraversalKind() const override {
652	return this->InnerMatcher.getTraversalKind();
653	}
654	};
655
656	private:
657	// For Matcher<T> <=> Matcher<U> conversions.
658	template <typename U> friend class Matcher;
659
660	// For DynTypedMatcher::unconditionalConvertTo<T>.
661	friend class DynTypedMatcher;
662
663	static DynTypedMatcher restrictMatcher(const DynTypedMatcher &Other) {
664	return Other.dynCastTo(Kind: ASTNodeKind::getFromNodeKind<T>());
665	}
666
667	explicit Matcher(const DynTypedMatcher &Implementation)
668	: Implementation(restrictMatcher(Other: Implementation)) {
669	assert(this->Implementation.getSupportedKind().isSame(
670	ASTNodeKind::getFromNodeKind<T>()));
671	}
672
673	DynTypedMatcher Implementation;
674	}; // class Matcher
675
676	/// A convenient helper for creating a Matcher<T> without specifying
677	/// the template type argument.
678	template <typename T>
679	inline Matcher<T> makeMatcher(MatcherInterface<T> *Implementation) {
680	return Matcher<T>(Implementation);
681	}
682
683	/// Interface that allows matchers to traverse the AST.
684	/// FIXME: Find a better name.
685	///
686	/// This provides three entry methods for each base node type in the AST:
687	/// - \c matchesChildOf:
688	/// Matches a matcher on every child node of the given node. Returns true
689	/// if at least one child node could be matched.
690	/// - \c matchesDescendantOf:
691	/// Matches a matcher on all descendant nodes of the given node. Returns true
692	/// if at least one descendant matched.
693	/// - \c matchesAncestorOf:
694	/// Matches a matcher on all ancestors of the given node. Returns true if
695	/// at least one ancestor matched.
696	///
697	/// FIXME: Currently we only allow Stmt and Decl nodes to start a traversal.
698	/// In the future, we want to implement this for all nodes for which it makes
699	/// sense. In the case of matchesAncestorOf, we'll want to implement it for
700	/// all nodes, as all nodes have ancestors.
701	class ASTMatchFinder {
702	public:
703	/// Defines how bindings are processed on recursive matches.
704	enum BindKind {
705	/// Stop at the first match and only bind the first match.
706	BK_First,
707
708	/// Create results for all combinations of bindings that match.
709	BK_All
710	};
711
712	/// Defines which ancestors are considered for a match.
713	enum AncestorMatchMode {
714	/// All ancestors.
715	AMM_All,
716
717	/// Direct parent only.
718	AMM_ParentOnly
719	};
720
721	virtual ~ASTMatchFinder() = default;
722
723	/// Returns true if the given C++ class is directly or indirectly derived
724	/// from a base type matching \c base.
725	///
726	/// A class is not considered to be derived from itself.
727	virtual bool classIsDerivedFrom(const CXXRecordDecl *Declaration,
728	const Matcher<NamedDecl> &Base,
729	BoundNodesTreeBuilder *Builder,
730	bool Directly) = 0;
731
732	/// Returns true if the given Objective-C class is directly or indirectly
733	/// derived from a base class matching \c base.
734	///
735	/// A class is not considered to be derived from itself.
736	virtual bool objcClassIsDerivedFrom(const ObjCInterfaceDecl *Declaration,
737	const Matcher<NamedDecl> &Base,
738	BoundNodesTreeBuilder *Builder,
739	bool Directly) = 0;
740
741	template <typename T>
742	bool matchesChildOf(const T &Node, const DynTypedMatcher &Matcher,
743	BoundNodesTreeBuilder *Builder, BindKind Bind) {
744	static_assert(std::is_base_of<Decl, T>::value ||
745	std::is_base_of<Stmt, T>::value ||
746	std::is_base_of<NestedNameSpecifier, T>::value ||
747	std::is_base_of<NestedNameSpecifierLoc, T>::value ||
748	std::is_base_of<TypeLoc, T>::value ||
749	std::is_base_of<QualType, T>::value ||
750	std::is_base_of<Attr, T>::value,
751	"unsupported type for recursive matching");
752	return matchesChildOf(DynTypedNode::create(Node), getASTContext(), Matcher,
753	Builder, Bind);
754	}
755
756	template <typename T>
757	bool matchesDescendantOf(const T &Node, const DynTypedMatcher &Matcher,
758	BoundNodesTreeBuilder *Builder, BindKind Bind) {
759	static_assert(std::is_base_of<Decl, T>::value ||
760	std::is_base_of<Stmt, T>::value ||
761	std::is_base_of<NestedNameSpecifier, T>::value ||
762	std::is_base_of<NestedNameSpecifierLoc, T>::value ||
763	std::is_base_of<TypeLoc, T>::value ||
764	std::is_base_of<QualType, T>::value ||
765	std::is_base_of<Attr, T>::value,
766	"unsupported type for recursive matching");
767	return matchesDescendantOf(DynTypedNode::create(Node), getASTContext(),
768	Matcher, Builder, Bind);
769	}
770
771	// FIXME: Implement support for BindKind.
772	template <typename T>
773	bool matchesAncestorOf(const T &Node, const DynTypedMatcher &Matcher,
774	BoundNodesTreeBuilder *Builder,
775	AncestorMatchMode MatchMode) {
776	static_assert(std::is_base_of<Decl, T>::value ||
777	std::is_base_of<NestedNameSpecifierLoc, T>::value ||
778	std::is_base_of<Stmt, T>::value ||
779	std::is_base_of<TypeLoc, T>::value ||
780	std::is_base_of<Attr, T>::value,
781	"type not allowed for recursive matching");
782	return matchesAncestorOf(DynTypedNode::create(Node), getASTContext(),
783	Matcher, Builder, MatchMode);
784	}
785
786	virtual ASTContext &getASTContext() const = 0;
787
788	virtual bool IsMatchingInASTNodeNotSpelledInSource() const = 0;
789
790	virtual bool IsMatchingInASTNodeNotAsIs() const = 0;
791
792	bool isTraversalIgnoringImplicitNodes() const;
793
794	protected:
795	virtual bool matchesChildOf(const DynTypedNode &Node, ASTContext &Ctx,
796	const DynTypedMatcher &Matcher,
797	BoundNodesTreeBuilder *Builder,
798	BindKind Bind) = 0;
799
800	virtual bool matchesDescendantOf(const DynTypedNode &Node, ASTContext &Ctx,
801	const DynTypedMatcher &Matcher,
802	BoundNodesTreeBuilder *Builder,
803	BindKind Bind) = 0;
804
805	virtual bool matchesAncestorOf(const DynTypedNode &Node, ASTContext &Ctx,
806	const DynTypedMatcher &Matcher,
807	BoundNodesTreeBuilder *Builder,
808	AncestorMatchMode MatchMode) = 0;
809	private:
810	friend struct ASTChildrenNotSpelledInSourceScope;
811	virtual bool isMatchingChildrenNotSpelledInSource() const = 0;
812	virtual void setMatchingChildrenNotSpelledInSource(bool Set) = 0;
813	};
814
815	struct ASTChildrenNotSpelledInSourceScope {
816	ASTChildrenNotSpelledInSourceScope(ASTMatchFinder *V, bool B)
817	: MV(V), MB(V->isMatchingChildrenNotSpelledInSource()) {
818	V->setMatchingChildrenNotSpelledInSource(B);
819	}
820	~ASTChildrenNotSpelledInSourceScope() {
821	MV->setMatchingChildrenNotSpelledInSource(MB);
822	}
823
824	private:
825	ASTMatchFinder *MV;
826	bool MB;
827	};
828
829	/// Specialization of the conversion functions for QualType.
830	///
831	/// This specialization provides the Matcher<Type>->Matcher<QualType>
832	/// conversion that the static API does.
833	template <>
834	inline Matcher<QualType> DynTypedMatcher::convertTo<QualType>() const {
835	assert(canConvertTo<QualType>());
836	const ASTNodeKind SourceKind = getSupportedKind();
837	if (SourceKind.isSame(Other: ASTNodeKind::getFromNodeKind<Type>())) {
838	// We support implicit conversion from Matcher<Type> to Matcher<QualType>
839	return unconditionalConvertTo<Type>();
840	}
841	return unconditionalConvertTo<QualType>();
842	}
843
844	/// Finds the first node in a range that matches the given matcher.
845	template <typename MatcherT, typename IteratorT>
846	IteratorT matchesFirstInRange(const MatcherT &Matcher, IteratorT Start,
847	IteratorT End, ASTMatchFinder *Finder,
848	BoundNodesTreeBuilder *Builder) {
849	for (IteratorT I = Start; I != End; ++I) {
850	BoundNodesTreeBuilder Result(*Builder);
851	if (Matcher.matches(*I, Finder, &Result)) {
852	*Builder = std::move(Result);
853	return I;
854	}
855	}
856	return End;
857	}
858
859	/// Finds the first node in a pointer range that matches the given
860	/// matcher.
861	template <typename MatcherT, typename IteratorT>
862	IteratorT matchesFirstInPointerRange(const MatcherT &Matcher, IteratorT Start,
863	IteratorT End, ASTMatchFinder *Finder,
864	BoundNodesTreeBuilder *Builder) {
865	for (IteratorT I = Start; I != End; ++I) {
866	BoundNodesTreeBuilder Result(*Builder);
867	if (Matcher.matches(**I, Finder, &Result)) {
868	*Builder = std::move(Result);
869	return I;
870	}
871	}
872	return End;
873	}
874
875	template <typename T, std::enable_if_t<!std::is_base_of<FunctionDecl, T>::value>
876	* = nullptr>
877	inline bool isDefaultedHelper(const T *) {
878	return false;
879	}
880	inline bool isDefaultedHelper(const FunctionDecl *FD) {
881	return FD->isDefaulted();
882	}
883
884	// Metafunction to determine if type T has a member called getDecl.
885	template <typename Ty>
886	class has_getDecl {
887	using yes = char[1];
888	using no = char[2];
889
890	template <typename Inner>
891	static yes& test(Inner *I, decltype(I->getDecl()) * = nullptr);
892
893	template <typename>
894	static no& test(...);
895
896	public:
897	static const bool value = sizeof(test<Ty>(nullptr)) == sizeof(yes);
898	};
899
900	/// Matches overloaded operators with a specific name.
901	///
902	/// The type argument ArgT is not used by this matcher but is used by
903	/// PolymorphicMatcher and should be StringRef.
904	template <typename T, typename ArgT>
905	class HasOverloadedOperatorNameMatcher : public SingleNodeMatcherInterface<T> {
906	static_assert(std::is_same<T, CXXOperatorCallExpr>::value ||
907	std::is_base_of<FunctionDecl, T>::value,
908	"unsupported class for matcher");
909	static_assert(std::is_same<ArgT, std::vector<std::string>>::value,
910	"argument type must be std::vector<std::string>");
911
912	public:
913	explicit HasOverloadedOperatorNameMatcher(std::vector<std::string> Names)
914	: SingleNodeMatcherInterface<T>(), Names(std::move(Names)) {}
915
916	bool matchesNode(const T &Node) const override {
917	return matchesSpecialized(Node);
918	}
919
920	private:
921
922	/// CXXOperatorCallExpr exist only for calls to overloaded operators
923	/// so this function returns true if the call is to an operator of the given
924	/// name.
925	bool matchesSpecialized(const CXXOperatorCallExpr &Node) const {
926	return llvm::is_contained(Range: Names, Element: getOperatorSpelling(Operator: Node.getOperator()));
927	}
928
929	/// Returns true only if CXXMethodDecl represents an overloaded
930	/// operator and has the given operator name.
931	bool matchesSpecialized(const FunctionDecl &Node) const {
932	return Node.isOverloadedOperator() &&
933	llvm::is_contained(
934	Range: Names, Element: getOperatorSpelling(Operator: Node.getOverloadedOperator()));
935	}
936
937	std::vector<std::string> Names;
938	};
939
940	/// Matches named declarations with a specific name.
941	///
942	/// See \c hasName() and \c hasAnyName() in ASTMatchers.h for details.
943	class HasNameMatcher : public SingleNodeMatcherInterface<NamedDecl> {
944	public:
945	explicit HasNameMatcher(std::vector<std::string> Names);
946
947	bool matchesNode(const NamedDecl &Node) const override;
948
949	private:
950	/// Unqualified match routine.
951	///
952	/// It is much faster than the full match, but it only works for unqualified
953	/// matches.
954	bool matchesNodeUnqualified(const NamedDecl &Node) const;
955
956	/// Full match routine
957	///
958	/// Fast implementation for the simple case of a named declaration at
959	/// namespace or RecordDecl scope.
960	/// It is slower than matchesNodeUnqualified, but faster than
961	/// matchesNodeFullSlow.
962	bool matchesNodeFullFast(const NamedDecl &Node) const;
963
964	/// Full match routine
965	///
966	/// It generates the fully qualified name of the declaration (which is
967	/// expensive) before trying to match.
968	/// It is slower but simple and works on all cases.
969	bool matchesNodeFullSlow(const NamedDecl &Node) const;
970
971	bool UseUnqualifiedMatch;
972	std::vector<std::string> Names;
973	};
974
975	/// Trampoline function to use VariadicFunction<> to construct a
976	/// HasNameMatcher.
977	Matcher<NamedDecl> hasAnyNameFunc(ArrayRef<const StringRef *> NameRefs);
978
979	/// Trampoline function to use VariadicFunction<> to construct a
980	/// hasAnySelector matcher.
981	Matcher<ObjCMessageExpr> hasAnySelectorFunc(
982	ArrayRef<const StringRef *> NameRefs);
983
984	/// Matches declarations for QualType and CallExpr.
985	///
986	/// Type argument DeclMatcherT is required by PolymorphicMatcher but
987	/// not actually used.
988	template <typename T, typename DeclMatcherT>
989	class HasDeclarationMatcher : public MatcherInterface<T> {
990	static_assert(std::is_same<DeclMatcherT, Matcher<Decl>>::value,
991	"instantiated with wrong types");
992
993	DynTypedMatcher InnerMatcher;
994
995	public:
996	explicit HasDeclarationMatcher(const Matcher<Decl> &InnerMatcher)
997	: InnerMatcher(InnerMatcher) {}
998
999	bool matches(const T &Node, ASTMatchFinder *Finder,
1000	BoundNodesTreeBuilder *Builder) const override {
1001	return matchesSpecialized(Node, Finder, Builder);
1002	}
1003
1004	private:
1005	/// Forwards to matching on the underlying type of the QualType.
1006	bool matchesSpecialized(const QualType &Node, ASTMatchFinder *Finder,
1007	BoundNodesTreeBuilder *Builder) const {
1008	if (Node.isNull())
1009	return false;
1010
1011	return matchesSpecialized(*Node, Finder, Builder);
1012	}
1013
1014	/// Finds the best declaration for a type and returns whether the inner
1015	/// matcher matches on it.
1016	bool matchesSpecialized(const Type &Node, ASTMatchFinder *Finder,
1017	BoundNodesTreeBuilder *Builder) const {
1018	// DeducedType does not have declarations of its own, so
1019	// match the deduced type instead.
1020	if (const auto *S = dyn_cast<DeducedType>(Val: &Node)) {
1021	QualType DT = S->getDeducedType();
1022	return !DT.isNull() ? matchesSpecialized(*DT, Finder, Builder) : false;
1023	}
1024
1025	// First, for any types that have a declaration, extract the declaration and
1026	// match on it.
1027	if (const auto *S = dyn_cast<TagType>(Val: &Node)) {
1028	return matchesDecl(Node: S->getDecl(), Finder, Builder);
1029	}
1030	if (const auto *S = dyn_cast<InjectedClassNameType>(Val: &Node)) {
1031	return matchesDecl(Node: S->getDecl(), Finder, Builder);
1032	}
1033	if (const auto *S = dyn_cast<TemplateTypeParmType>(Val: &Node)) {
1034	return matchesDecl(Node: S->getDecl(), Finder, Builder);
1035	}
1036	if (const auto *S = dyn_cast<TypedefType>(Val: &Node)) {
1037	return matchesDecl(Node: S->getDecl(), Finder, Builder);
1038	}
1039	if (const auto *S = dyn_cast<UnresolvedUsingType>(Val: &Node)) {
1040	return matchesDecl(Node: S->getDecl(), Finder, Builder);
1041	}
1042	if (const auto *S = dyn_cast<ObjCObjectType>(Val: &Node)) {
1043	return matchesDecl(Node: S->getInterface(), Finder, Builder);
1044	}
1045
1046	// A SubstTemplateTypeParmType exists solely to mark a type substitution
1047	// on the instantiated template. As users usually want to match the
1048	// template parameter on the uninitialized template, we can always desugar
1049	// one level without loss of expressivness.
1050	// For example, given:
1051	// template<typename T> struct X { T t; } class A {}; X<A> a;
1052	// The following matcher will match, which otherwise would not:
1053	// fieldDecl(hasType(pointerType())).
1054	if (const auto *S = dyn_cast<SubstTemplateTypeParmType>(Val: &Node)) {
1055	return matchesSpecialized(S->getReplacementType(), Finder, Builder);
1056	}
1057
1058	// For template specialization types, we want to match the template
1059	// declaration, as long as the type is still dependent, and otherwise the
1060	// declaration of the instantiated tag type.
1061	if (const auto *S = dyn_cast<TemplateSpecializationType>(Val: &Node)) {
1062	if (!S->isTypeAlias() && S->isSugared()) {
1063	// If the template is non-dependent, we want to match the instantiated
1064	// tag type.
1065	// For example, given:
1066	// template<typename T> struct X {}; X<int> a;
1067	// The following matcher will match, which otherwise would not:
1068	// templateSpecializationType(hasDeclaration(cxxRecordDecl())).
1069	return matchesSpecialized(*S->desugar(), Finder, Builder);
1070	}
1071	// If the template is dependent or an alias, match the template
1072	// declaration.
1073	return matchesDecl(Node: S->getTemplateName().getAsTemplateDecl(), Finder,
1074	Builder);
1075	}
1076
1077	// FIXME: We desugar elaborated types. This makes the assumption that users
1078	// do never want to match on whether a type is elaborated - there are
1079	// arguments for both sides; for now, continue desugaring.
1080	if (const auto *S = dyn_cast<ElaboratedType>(Val: &Node)) {
1081	return matchesSpecialized(S->desugar(), Finder, Builder);
1082	}
1083	// Similarly types found via using declarations.
1084	// These are *usually* meaningless sugar, and this matches the historical
1085	// behavior prior to the introduction of UsingType.
1086	if (const auto *S = dyn_cast<UsingType>(Val: &Node)) {
1087	return matchesSpecialized(S->desugar(), Finder, Builder);
1088	}
1089	return false;
1090	}
1091
1092	/// Extracts the Decl the DeclRefExpr references and returns whether
1093	/// the inner matcher matches on it.
1094	bool matchesSpecialized(const DeclRefExpr &Node, ASTMatchFinder *Finder,
1095	BoundNodesTreeBuilder *Builder) const {
1096	return matchesDecl(Node: Node.getDecl(), Finder, Builder);
1097	}
1098
1099	/// Extracts the Decl of the callee of a CallExpr and returns whether
1100	/// the inner matcher matches on it.
1101	bool matchesSpecialized(const CallExpr &Node, ASTMatchFinder *Finder,
1102	BoundNodesTreeBuilder *Builder) const {
1103	return matchesDecl(Node: Node.getCalleeDecl(), Finder, Builder);
1104	}
1105
1106	/// Extracts the Decl of the constructor call and returns whether the
1107	/// inner matcher matches on it.
1108	bool matchesSpecialized(const CXXConstructExpr &Node,
1109	ASTMatchFinder *Finder,
1110	BoundNodesTreeBuilder *Builder) const {
1111	return matchesDecl(Node: Node.getConstructor(), Finder, Builder);
1112	}
1113
1114	bool matchesSpecialized(const ObjCIvarRefExpr &Node,
1115	ASTMatchFinder *Finder,
1116	BoundNodesTreeBuilder *Builder) const {
1117	return matchesDecl(Node: Node.getDecl(), Finder, Builder);
1118	}
1119
1120	/// Extracts the operator new of the new call and returns whether the
1121	/// inner matcher matches on it.
1122	bool matchesSpecialized(const CXXNewExpr &Node,
1123	ASTMatchFinder *Finder,
1124	BoundNodesTreeBuilder *Builder) const {
1125	return matchesDecl(Node: Node.getOperatorNew(), Finder, Builder);
1126	}
1127
1128	/// Extracts the \c ValueDecl a \c MemberExpr refers to and returns
1129	/// whether the inner matcher matches on it.
1130	bool matchesSpecialized(const MemberExpr &Node,
1131	ASTMatchFinder *Finder,
1132	BoundNodesTreeBuilder *Builder) const {
1133	return matchesDecl(Node: Node.getMemberDecl(), Finder, Builder);
1134	}
1135
1136	/// Extracts the \c LabelDecl a \c AddrLabelExpr refers to and returns
1137	/// whether the inner matcher matches on it.
1138	bool matchesSpecialized(const AddrLabelExpr &Node,
1139	ASTMatchFinder *Finder,
1140	BoundNodesTreeBuilder *Builder) const {
1141	return matchesDecl(Node: Node.getLabel(), Finder, Builder);
1142	}
1143
1144	/// Extracts the declaration of a LabelStmt and returns whether the
1145	/// inner matcher matches on it.
1146	bool matchesSpecialized(const LabelStmt &Node, ASTMatchFinder *Finder,
1147	BoundNodesTreeBuilder *Builder) const {
1148	return matchesDecl(Node: Node.getDecl(), Finder, Builder);
1149	}
1150
1151	/// Returns whether the inner matcher \c Node. Returns false if \c Node
1152	/// is \c NULL.
1153	bool matchesDecl(const Decl *Node, ASTMatchFinder *Finder,
1154	BoundNodesTreeBuilder *Builder) const {
1155	return Node != nullptr &&
1156	!(Finder->isTraversalIgnoringImplicitNodes() &&
1157	Node->isImplicit()) &&
1158	this->InnerMatcher.matches(DynTypedNode::create(Node: *Node), Finder,
1159	Builder);
1160	}
1161	};
1162
1163	/// IsBaseType<T>::value is true if T is a "base" type in the AST
1164	/// node class hierarchies.
1165	template <typename T>
1166	struct IsBaseType {
1167	static const bool value =
1168	std::is_same<T, Decl>::value || std::is_same<T, Stmt>::value ||
1169	std::is_same<T, QualType>::value || std::is_same<T, Type>::value ||
1170	std::is_same<T, TypeLoc>::value ||
1171	std::is_same<T, NestedNameSpecifier>::value ||
1172	std::is_same<T, NestedNameSpecifierLoc>::value ||
1173	std::is_same<T, CXXCtorInitializer>::value ||
1174	std::is_same<T, TemplateArgumentLoc>::value ||
1175	std::is_same<T, Attr>::value;
1176	};
1177	template <typename T>
1178	const bool IsBaseType<T>::value;
1179
1180	/// A "type list" that contains all types.
1181	///
1182	/// Useful for matchers like \c anything and \c unless.
1183	using AllNodeBaseTypes =
1184	TypeList<Decl, Stmt, NestedNameSpecifier, NestedNameSpecifierLoc, QualType,
1185	Type, TypeLoc, CXXCtorInitializer, Attr>;
1186
1187	/// Helper meta-function to extract the argument out of a function of
1188	/// type void(Arg).
1189	///
1190	/// See AST_POLYMORPHIC_SUPPORTED_TYPES for details.
1191	template <class T> struct ExtractFunctionArgMeta;
1192	template <class T> struct ExtractFunctionArgMeta<void(T)> {
1193	using type = T;
1194	};
1195
1196	template <class T, class Tuple, std::size_t... I>
1197	constexpr T *new_from_tuple_impl(Tuple &&t, std::index_sequence<I...>) {
1198	return new T(std::get<I>(std::forward<Tuple>(t))...);
1199	}
1200
1201	template <class T, class Tuple> constexpr T *new_from_tuple(Tuple &&t) {
1202	return new_from_tuple_impl<T>(
1203	std::forward<Tuple>(t),
1204	std::make_index_sequence<
1205	std::tuple_size<std::remove_reference_t<Tuple>>::value>{});
1206	}
1207
1208	/// Default type lists for ArgumentAdaptingMatcher matchers.
1209	using AdaptativeDefaultFromTypes = AllNodeBaseTypes;
1210	using AdaptativeDefaultToTypes =
1211	TypeList<Decl, Stmt, NestedNameSpecifier, NestedNameSpecifierLoc, TypeLoc,
1212	QualType, Attr>;
1213
1214	/// All types that are supported by HasDeclarationMatcher above.
1215	using HasDeclarationSupportedTypes =
1216	TypeList<CallExpr, CXXConstructExpr, CXXNewExpr, DeclRefExpr, EnumType,
1217	ElaboratedType, InjectedClassNameType, LabelStmt, AddrLabelExpr,
1218	MemberExpr, QualType, RecordType, TagType,
1219	TemplateSpecializationType, TemplateTypeParmType, TypedefType,
1220	UnresolvedUsingType, ObjCIvarRefExpr>;
1221
1222	/// A Matcher that allows binding the node it matches to an id.
1223	///
1224	/// BindableMatcher provides a \a bind() method that allows binding the
1225	/// matched node to an id if the match was successful.
1226	template <typename T> class BindableMatcher : public Matcher<T> {
1227	public:
1228	explicit BindableMatcher(const Matcher<T> &M) : Matcher<T>(M) {}
1229	explicit BindableMatcher(MatcherInterface<T> *Implementation)
1230	: Matcher<T>(Implementation) {}
1231
1232	/// Returns a matcher that will bind the matched node on a match.
1233	///
1234	/// The returned matcher is equivalent to this matcher, but will
1235	/// bind the matched node on a match.
1236	Matcher<T> bind(StringRef ID) const {
1237	return DynTypedMatcher(*this)
1238	.tryBind(ID)
1239	->template unconditionalConvertTo<T>();
1240	}
1241
1242	/// Same as Matcher<T>'s conversion operator, but enables binding on
1243	/// the returned matcher.
1244	operator DynTypedMatcher() const {
1245	DynTypedMatcher Result = static_cast<const Matcher<T> &>(*this);
1246	Result.setAllowBind(true);
1247	return Result;
1248	}
1249	};
1250
1251	/// Matches any instance of the given NodeType.
1252	///
1253	/// This is useful when a matcher syntactically requires a child matcher,
1254	/// but the context doesn't care. See for example: anything().
1255	class TrueMatcher {
1256	public:
1257	using ReturnTypes = AllNodeBaseTypes;
1258
1259	template <typename T> operator Matcher<T>() const {
1260	return DynTypedMatcher::trueMatcher(NodeKind: ASTNodeKind::getFromNodeKind<T>())
1261	.template unconditionalConvertTo<T>();
1262	}
1263	};
1264
1265	/// Creates a Matcher<T> that matches if all inner matchers match.
1266	template <typename T>
1267	BindableMatcher<T>
1268	makeAllOfComposite(ArrayRef<const Matcher<T> *> InnerMatchers) {
1269	// For the size() == 0 case, we return a "true" matcher.
1270	if (InnerMatchers.empty()) {
1271	return BindableMatcher<T>(TrueMatcher());
1272	}
1273	// For the size() == 1 case, we simply return that one matcher.
1274	// No need to wrap it in a variadic operation.
1275	if (InnerMatchers.size() == 1) {
1276	return BindableMatcher<T>(*InnerMatchers[0]);
1277	}
1278
1279	using PI = llvm::pointee_iterator<const Matcher<T> *const *>;
1280
1281	std::vector<DynTypedMatcher> DynMatchers(PI(InnerMatchers.begin()),
1282	PI(InnerMatchers.end()));
1283	return BindableMatcher<T>(
1284	DynTypedMatcher::constructVariadic(Op: DynTypedMatcher::VO_AllOf,
1285	SupportedKind: ASTNodeKind::getFromNodeKind<T>(),
1286	InnerMatchers: std::move(DynMatchers))
1287	.template unconditionalConvertTo<T>());
1288	}
1289
1290	/// Creates a Matcher<T> that matches if
1291	/// T is dyn_cast'able into InnerT and all inner matchers match.
1292	///
1293	/// Returns BindableMatcher, as matchers that use dyn_cast have
1294	/// the same object both to match on and to run submatchers on,
1295	/// so there is no ambiguity with what gets bound.
1296	template <typename T, typename InnerT>
1297	BindableMatcher<T>
1298	makeDynCastAllOfComposite(ArrayRef<const Matcher<InnerT> *> InnerMatchers) {
1299	return BindableMatcher<T>(
1300	makeAllOfComposite(InnerMatchers).template dynCastTo<T>());
1301	}
1302
1303	/// A VariadicDynCastAllOfMatcher<SourceT, TargetT> object is a
1304	/// variadic functor that takes a number of Matcher<TargetT> and returns a
1305	/// Matcher<SourceT> that matches TargetT nodes that are matched by all of the
1306	/// given matchers, if SourceT can be dynamically casted into TargetT.
1307	///
1308	/// For example:
1309	/// const VariadicDynCastAllOfMatcher<Decl, CXXRecordDecl> record;
1310	/// Creates a functor record(...) that creates a Matcher<Decl> given
1311	/// a variable number of arguments of type Matcher<CXXRecordDecl>.
1312	/// The returned matcher matches if the given Decl can by dynamically
1313	/// casted to CXXRecordDecl and all given matchers match.
1314	template <typename SourceT, typename TargetT>
1315	class VariadicDynCastAllOfMatcher
1316	: public VariadicFunction<BindableMatcher<SourceT>, Matcher<TargetT>,
1317	makeDynCastAllOfComposite<SourceT, TargetT>> {
1318	public:
1319	VariadicDynCastAllOfMatcher() {}
1320	};
1321
1322	/// A \c VariadicAllOfMatcher<T> object is a variadic functor that takes
1323	/// a number of \c Matcher<T> and returns a \c Matcher<T> that matches \c T
1324	/// nodes that are matched by all of the given matchers.
1325	///
1326	/// For example:
1327	/// const VariadicAllOfMatcher<NestedNameSpecifier> nestedNameSpecifier;
1328	/// Creates a functor nestedNameSpecifier(...) that creates a
1329	/// \c Matcher<NestedNameSpecifier> given a variable number of arguments of type
1330	/// \c Matcher<NestedNameSpecifier>.
1331	/// The returned matcher matches if all given matchers match.
1332	template <typename T>
1333	class VariadicAllOfMatcher
1334	: public VariadicFunction<BindableMatcher<T>, Matcher<T>,
1335	makeAllOfComposite<T>> {
1336	public:
1337	VariadicAllOfMatcher() {}
1338	};
1339
1340	/// VariadicOperatorMatcher related types.
1341	/// @{
1342
1343	/// Polymorphic matcher object that uses a \c
1344	/// DynTypedMatcher::VariadicOperator operator.
1345	///
1346	/// Input matchers can have any type (including other polymorphic matcher
1347	/// types), and the actual Matcher<T> is generated on demand with an implicit
1348	/// conversion operator.
1349	template <typename... Ps> class VariadicOperatorMatcher {
1350	public:
1351	VariadicOperatorMatcher(DynTypedMatcher::VariadicOperator Op, Ps &&... Params)
1352	: Op(Op), Params(std::forward<Ps>(Params)...) {}
1353
1354	template <typename T> operator Matcher<T>() const & {
1355	return DynTypedMatcher::constructVariadic(
1356	Op, SupportedKind: ASTNodeKind::getFromNodeKind<T>(),
1357	InnerMatchers: getMatchers<T>(std::index_sequence_for<Ps...>()))
1358	.template unconditionalConvertTo<T>();
1359	}
1360
1361	template <typename T> operator Matcher<T>() && {
1362	return DynTypedMatcher::constructVariadic(
1363	Op, SupportedKind: ASTNodeKind::getFromNodeKind<T>(),
1364	InnerMatchers: getMatchers<T>(std::index_sequence_for<Ps...>()))
1365	.template unconditionalConvertTo<T>();
1366	}
1367
1368	private:
1369	// Helper method to unpack the tuple into a vector.
1370	template <typename T, std::size_t... Is>
1371	std::vector<DynTypedMatcher> getMatchers(std::index_sequence<Is...>) const & {
1372	return {Matcher<T>(std::get<Is>(Params))...};
1373	}
1374
1375	template <typename T, std::size_t... Is>
1376	std::vector<DynTypedMatcher> getMatchers(std::index_sequence<Is...>) && {
1377	return {Matcher<T>(std::get<Is>(std::move(Params)))...};
1378	}
1379
1380	const DynTypedMatcher::VariadicOperator Op;
1381	std::tuple<Ps...> Params;
1382	};
1383
1384	/// Overloaded function object to generate VariadicOperatorMatcher
1385	/// objects from arbitrary matchers.
1386	template <unsigned MinCount, unsigned MaxCount>
1387	struct VariadicOperatorMatcherFunc {
1388	DynTypedMatcher::VariadicOperator Op;
1389
1390	template <typename... Ms>
1391	VariadicOperatorMatcher<Ms...> operator()(Ms &&... Ps) const {
1392	static_assert(MinCount <= sizeof...(Ms) && sizeof...(Ms) <= MaxCount,
1393	"invalid number of parameters for variadic matcher");
1394	return VariadicOperatorMatcher<Ms...>(Op, std::forward<Ms>(Ps)...);
1395	}
1396	};
1397
1398	template <typename T, bool IsBaseOf, typename Head, typename Tail>
1399	struct GetCladeImpl {
1400	using Type = Head;
1401	};
1402	template <typename T, typename Head, typename Tail>
1403	struct GetCladeImpl<T, false, Head, Tail>
1404	: GetCladeImpl<T, std::is_base_of<typename Tail::head, T>::value,
1405	typename Tail::head, typename Tail::tail> {};
1406
1407	template <typename T, typename... U>
1408	struct GetClade : GetCladeImpl<T, false, T, AllNodeBaseTypes> {};
1409
1410	template <typename CladeType, typename... MatcherTypes>
1411	struct MapAnyOfMatcherImpl {
1412
1413	template <typename... InnerMatchers>
1414	BindableMatcher<CladeType>
1415	operator()(InnerMatchers &&... InnerMatcher) const {
1416	return VariadicAllOfMatcher<CladeType>()(std::apply(
1417	internal::VariadicOperatorMatcherFunc<
1418	0, std::numeric_limits<unsigned>::max()>{
1419	.Op: internal::DynTypedMatcher::VO_AnyOf},
1420	std::apply(
1421	[&](auto... Matcher) {
1422	return std::make_tuple(Matcher(InnerMatcher...)...);
1423	},
1424	std::tuple<
1425	VariadicDynCastAllOfMatcher<CladeType, MatcherTypes>...>())));
1426	}
1427	};
1428
1429	template <typename... MatcherTypes>
1430	using MapAnyOfMatcher =
1431	MapAnyOfMatcherImpl<typename GetClade<MatcherTypes...>::Type,
1432	MatcherTypes...>;
1433
1434	template <typename... MatcherTypes> struct MapAnyOfHelper {
1435	using CladeType = typename GetClade<MatcherTypes...>::Type;
1436
1437	MapAnyOfMatcher<MatcherTypes...> with;
1438
1439	operator BindableMatcher<CladeType>() const { return with(); }
1440
1441	Matcher<CladeType> bind(StringRef ID) const { return with().bind(ID); }
1442	};
1443
1444	template <template <typename ToArg, typename FromArg> class ArgumentAdapterT,
1445	typename T, typename ToTypes>
1446	class ArgumentAdaptingMatcherFuncAdaptor {
1447	public:
1448	explicit ArgumentAdaptingMatcherFuncAdaptor(const Matcher<T> &InnerMatcher)
1449	: InnerMatcher(InnerMatcher) {}
1450
1451	using ReturnTypes = ToTypes;
1452
1453	template <typename To> operator Matcher<To>() const & {
1454	return Matcher<To>(new ArgumentAdapterT<To, T>(InnerMatcher));
1455	}
1456
1457	template <typename To> operator Matcher<To>() && {
1458	return Matcher<To>(new ArgumentAdapterT<To, T>(std::move(InnerMatcher)));
1459	}
1460
1461	private:
1462	Matcher<T> InnerMatcher;
1463	};
1464
1465	/// Converts a \c Matcher<T> to a matcher of desired type \c To by
1466	/// "adapting" a \c To into a \c T.
1467	///
1468	/// The \c ArgumentAdapterT argument specifies how the adaptation is done.
1469	///
1470	/// For example:
1471	/// \c ArgumentAdaptingMatcher<HasMatcher, T>(InnerMatcher);
1472	/// Given that \c InnerMatcher is of type \c Matcher<T>, this returns a matcher
1473	/// that is convertible into any matcher of type \c To by constructing
1474	/// \c HasMatcher<To, T>(InnerMatcher).
1475	///
1476	/// If a matcher does not need knowledge about the inner type, prefer to use
1477	/// PolymorphicMatcher.
1478	template <template <typename ToArg, typename FromArg> class ArgumentAdapterT,
1479	typename FromTypes = AdaptativeDefaultFromTypes,
1480	typename ToTypes = AdaptativeDefaultToTypes>
1481	struct ArgumentAdaptingMatcherFunc {
1482	template <typename T>
1483	static ArgumentAdaptingMatcherFuncAdaptor<ArgumentAdapterT, T, ToTypes>
1484	create(const Matcher<T> &InnerMatcher) {
1485	return ArgumentAdaptingMatcherFuncAdaptor<ArgumentAdapterT, T, ToTypes>(
1486	InnerMatcher);
1487	}
1488
1489	template <typename T>
1490	ArgumentAdaptingMatcherFuncAdaptor<ArgumentAdapterT, T, ToTypes>
1491	operator()(const Matcher<T> &InnerMatcher) const {
1492	return create(InnerMatcher);
1493	}
1494
1495	template <typename... T>
1496	ArgumentAdaptingMatcherFuncAdaptor<ArgumentAdapterT,
1497	typename GetClade<T...>::Type, ToTypes>
1498	operator()(const MapAnyOfHelper<T...> &InnerMatcher) const {
1499	return create(InnerMatcher.with());
1500	}
1501	};
1502
1503	template <typename T> class TraversalMatcher : public MatcherInterface<T> {
1504	DynTypedMatcher InnerMatcher;
1505	clang::TraversalKind Traversal;
1506
1507	public:
1508	explicit TraversalMatcher(clang::TraversalKind TK,
1509	const Matcher<T> &InnerMatcher)
1510	: InnerMatcher(InnerMatcher), Traversal(TK) {}
1511
1512	bool matches(const T &Node, ASTMatchFinder *Finder,
1513	BoundNodesTreeBuilder *Builder) const override {
1514	return this->InnerMatcher.matches(DynTypedNode::create(Node), Finder,
1515	Builder);
1516	}
1517
1518	std::optional<clang::TraversalKind> TraversalKind() const override {
1519	if (auto NestedKind = this->InnerMatcher.getTraversalKind())
1520	return NestedKind;
1521	return Traversal;
1522	}
1523	};
1524
1525	template <typename MatcherType> class TraversalWrapper {
1526	public:
1527	TraversalWrapper(TraversalKind TK, const MatcherType &InnerMatcher)
1528	: TK(TK), InnerMatcher(InnerMatcher) {}
1529
1530	template <typename T> operator Matcher<T>() const & {
1531	return internal::DynTypedMatcher::constructRestrictedWrapper(
1532	InnerMatcher: new internal::TraversalMatcher<T>(TK, InnerMatcher),
1533	RestrictKind: ASTNodeKind::getFromNodeKind<T>())
1534	.template unconditionalConvertTo<T>();
1535	}
1536
1537	template <typename T> operator Matcher<T>() && {
1538	return internal::DynTypedMatcher::constructRestrictedWrapper(
1539	InnerMatcher: new internal::TraversalMatcher<T>(TK, std::move(InnerMatcher)),
1540	RestrictKind: ASTNodeKind::getFromNodeKind<T>())
1541	.template unconditionalConvertTo<T>();
1542	}
1543
1544	private:
1545	TraversalKind TK;
1546	MatcherType InnerMatcher;
1547	};
1548
1549	/// A PolymorphicMatcher<MatcherT, P1, ..., PN> object can be
1550	/// created from N parameters p1, ..., pN (of type P1, ..., PN) and
1551	/// used as a Matcher<T> where a MatcherT<T, P1, ..., PN>(p1, ..., pN)
1552	/// can be constructed.
1553	///
1554	/// For example:
1555	/// - PolymorphicMatcher<IsDefinitionMatcher>()
1556	/// creates an object that can be used as a Matcher<T> for any type T
1557	/// where an IsDefinitionMatcher<T>() can be constructed.
1558	/// - PolymorphicMatcher<ValueEqualsMatcher, int>(42)
1559	/// creates an object that can be used as a Matcher<T> for any type T
1560	/// where a ValueEqualsMatcher<T, int>(42) can be constructed.
1561	template <template <typename T, typename... Params> class MatcherT,
1562	typename ReturnTypesF, typename... ParamTypes>
1563	class PolymorphicMatcher {
1564	public:
1565	PolymorphicMatcher(const ParamTypes &... Params) : Params(Params...) {}
1566
1567	using ReturnTypes = typename ExtractFunctionArgMeta<ReturnTypesF>::type;
1568
1569	template <typename T> operator Matcher<T>() const & {
1570	static_assert(TypeListContainsSuperOf<ReturnTypes, T>::value,
1571	"right polymorphic conversion");
1572	return Matcher<T>(new_from_tuple<MatcherT<T, ParamTypes...>>(Params));
1573	}
1574
1575	template <typename T> operator Matcher<T>() && {
1576	static_assert(TypeListContainsSuperOf<ReturnTypes, T>::value,
1577	"right polymorphic conversion");
1578	return Matcher<T>(
1579	new_from_tuple<MatcherT<T, ParamTypes...>>(std::move(Params)));
1580	}
1581
1582	private:
1583	std::tuple<ParamTypes...> Params;
1584	};
1585
1586	/// Matches nodes of type T that have child nodes of type ChildT for
1587	/// which a specified child matcher matches.
1588	///
1589	/// ChildT must be an AST base type.
1590	template <typename T, typename ChildT>
1591	class HasMatcher : public MatcherInterface<T> {
1592	DynTypedMatcher InnerMatcher;
1593
1594	public:
1595	explicit HasMatcher(const Matcher<ChildT> &InnerMatcher)
1596	: InnerMatcher(InnerMatcher) {}
1597
1598	bool matches(const T &Node, ASTMatchFinder *Finder,
1599	BoundNodesTreeBuilder *Builder) const override {
1600	return Finder->matchesChildOf(Node, this->InnerMatcher, Builder,
1601	ASTMatchFinder::BK_First);
1602	}
1603	};
1604
1605	/// Matches nodes of type T that have child nodes of type ChildT for
1606	/// which a specified child matcher matches. ChildT must be an AST base
1607	/// type.
1608	/// As opposed to the HasMatcher, the ForEachMatcher will produce a match
1609	/// for each child that matches.
1610	template <typename T, typename ChildT>
1611	class ForEachMatcher : public MatcherInterface<T> {
1612	static_assert(IsBaseType<ChildT>::value,
1613	"for each only accepts base type matcher");
1614
1615	DynTypedMatcher InnerMatcher;
1616
1617	public:
1618	explicit ForEachMatcher(const Matcher<ChildT> &InnerMatcher)
1619	: InnerMatcher(InnerMatcher) {}
1620
1621	bool matches(const T &Node, ASTMatchFinder *Finder,
1622	BoundNodesTreeBuilder *Builder) const override {
1623	return Finder->matchesChildOf(
1624	Node, this->InnerMatcher, Builder,
1625	ASTMatchFinder::BK_All);
1626	}
1627	};
1628
1629	/// @}
1630
1631	template <typename T>
1632	inline Matcher<T> DynTypedMatcher::unconditionalConvertTo() const {
1633	return Matcher<T>(*this);
1634	}
1635
1636	/// Matches nodes of type T that have at least one descendant node of
1637	/// type DescendantT for which the given inner matcher matches.
1638	///
1639	/// DescendantT must be an AST base type.
1640	template <typename T, typename DescendantT>
1641	class HasDescendantMatcher : public MatcherInterface<T> {
1642	static_assert(IsBaseType<DescendantT>::value,
1643	"has descendant only accepts base type matcher");
1644
1645	DynTypedMatcher DescendantMatcher;
1646
1647	public:
1648	explicit HasDescendantMatcher(const Matcher<DescendantT> &DescendantMatcher)
1649	: DescendantMatcher(DescendantMatcher) {}
1650
1651	bool matches(const T &Node, ASTMatchFinder *Finder,
1652	BoundNodesTreeBuilder *Builder) const override {
1653	return Finder->matchesDescendantOf(Node, this->DescendantMatcher, Builder,
1654	ASTMatchFinder::BK_First);
1655	}
1656	};
1657
1658	/// Matches nodes of type \c T that have a parent node of type \c ParentT
1659	/// for which the given inner matcher matches.
1660	///
1661	/// \c ParentT must be an AST base type.
1662	template <typename T, typename ParentT>
1663	class HasParentMatcher : public MatcherInterface<T> {
1664	static_assert(IsBaseType<ParentT>::value,
1665	"has parent only accepts base type matcher");
1666
1667	DynTypedMatcher ParentMatcher;
1668
1669	public:
1670	explicit HasParentMatcher(const Matcher<ParentT> &ParentMatcher)
1671	: ParentMatcher(ParentMatcher) {}
1672
1673	bool matches(const T &Node, ASTMatchFinder *Finder,
1674	BoundNodesTreeBuilder *Builder) const override {
1675	return Finder->matchesAncestorOf(Node, this->ParentMatcher, Builder,
1676	ASTMatchFinder::AMM_ParentOnly);
1677	}
1678	};
1679
1680	/// Matches nodes of type \c T that have at least one ancestor node of
1681	/// type \c AncestorT for which the given inner matcher matches.
1682	///
1683	/// \c AncestorT must be an AST base type.
1684	template <typename T, typename AncestorT>
1685	class HasAncestorMatcher : public MatcherInterface<T> {
1686	static_assert(IsBaseType<AncestorT>::value,
1687	"has ancestor only accepts base type matcher");
1688
1689	DynTypedMatcher AncestorMatcher;
1690
1691	public:
1692	explicit HasAncestorMatcher(const Matcher<AncestorT> &AncestorMatcher)
1693	: AncestorMatcher(AncestorMatcher) {}
1694
1695	bool matches(const T &Node, ASTMatchFinder *Finder,
1696	BoundNodesTreeBuilder *Builder) const override {
1697	return Finder->matchesAncestorOf(Node, this->AncestorMatcher, Builder,
1698	ASTMatchFinder::AMM_All);
1699	}
1700	};
1701
1702	/// Matches nodes of type T that have at least one descendant node of
1703	/// type DescendantT for which the given inner matcher matches.
1704	///
1705	/// DescendantT must be an AST base type.
1706	/// As opposed to HasDescendantMatcher, ForEachDescendantMatcher will match
1707	/// for each descendant node that matches instead of only for the first.
1708	template <typename T, typename DescendantT>
1709	class ForEachDescendantMatcher : public MatcherInterface<T> {
1710	static_assert(IsBaseType<DescendantT>::value,
1711	"for each descendant only accepts base type matcher");
1712
1713	DynTypedMatcher DescendantMatcher;
1714
1715	public:
1716	explicit ForEachDescendantMatcher(
1717	const Matcher<DescendantT> &DescendantMatcher)
1718	: DescendantMatcher(DescendantMatcher) {}
1719
1720	bool matches(const T &Node, ASTMatchFinder *Finder,
1721	BoundNodesTreeBuilder *Builder) const override {
1722	return Finder->matchesDescendantOf(Node, this->DescendantMatcher, Builder,
1723	ASTMatchFinder::BK_All);
1724	}
1725	};
1726
1727	/// Matches on nodes that have a getValue() method if getValue() equals
1728	/// the value the ValueEqualsMatcher was constructed with.
1729	template <typename T, typename ValueT>
1730	class ValueEqualsMatcher : public SingleNodeMatcherInterface<T> {
1731	static_assert(std::is_base_of<CharacterLiteral, T>::value ||
1732	std::is_base_of<CXXBoolLiteralExpr, T>::value ||
1733	std::is_base_of<FloatingLiteral, T>::value ||
1734	std::is_base_of<IntegerLiteral, T>::value,
1735	"the node must have a getValue method");
1736
1737	public:
1738	explicit ValueEqualsMatcher(const ValueT &ExpectedValue)
1739	: ExpectedValue(ExpectedValue) {}
1740
1741	bool matchesNode(const T &Node) const override {
1742	return Node.getValue() == ExpectedValue;
1743	}
1744
1745	private:
1746	ValueT ExpectedValue;
1747	};
1748
1749	/// Template specializations to easily write matchers for floating point
1750	/// literals.
1751	template <>
1752	inline bool ValueEqualsMatcher<FloatingLiteral, double>::matchesNode(
1753	const FloatingLiteral &Node) const {
1754	if ((&Node.getSemantics()) == &llvm::APFloat::IEEEsingle())
1755	return Node.getValue().convertToFloat() == ExpectedValue;
1756	if ((&Node.getSemantics()) == &llvm::APFloat::IEEEdouble())
1757	return Node.getValue().convertToDouble() == ExpectedValue;
1758	return false;
1759	}
1760	template <>
1761	inline bool ValueEqualsMatcher<FloatingLiteral, float>::matchesNode(
1762	const FloatingLiteral &Node) const {
1763	if ((&Node.getSemantics()) == &llvm::APFloat::IEEEsingle())
1764	return Node.getValue().convertToFloat() == ExpectedValue;
1765	if ((&Node.getSemantics()) == &llvm::APFloat::IEEEdouble())
1766	return Node.getValue().convertToDouble() == ExpectedValue;
1767	return false;
1768	}
1769	template <>
1770	inline bool ValueEqualsMatcher<FloatingLiteral, llvm::APFloat>::matchesNode(
1771	const FloatingLiteral &Node) const {
1772	return ExpectedValue.compare(RHS: Node.getValue()) == llvm::APFloat::cmpEqual;
1773	}
1774
1775	/// Matches nodes of type \c TLoc for which the inner
1776	/// \c Matcher<T> matches.
1777	template <typename TLoc, typename T>
1778	class LocMatcher : public MatcherInterface<TLoc> {
1779	DynTypedMatcher InnerMatcher;
1780
1781	public:
1782	explicit LocMatcher(const Matcher<T> &InnerMatcher)
1783	: InnerMatcher(InnerMatcher) {}
1784
1785	bool matches(const TLoc &Node, ASTMatchFinder *Finder,
1786	BoundNodesTreeBuilder *Builder) const override {
1787	if (!Node)
1788	return false;
1789	return this->InnerMatcher.matches(extract(Loc: Node), Finder, Builder);
1790	}
1791
1792	private:
1793	static DynTypedNode extract(const NestedNameSpecifierLoc &Loc) {
1794	return DynTypedNode::create(Node: *Loc.getNestedNameSpecifier());
1795	}
1796	};
1797
1798	/// Matches \c TypeLocs based on an inner matcher matching a certain
1799	/// \c QualType.
1800	///
1801	/// Used to implement the \c loc() matcher.
1802	class TypeLocTypeMatcher : public MatcherInterface<TypeLoc> {
1803	DynTypedMatcher InnerMatcher;
1804
1805	public:
1806	explicit TypeLocTypeMatcher(const Matcher<QualType> &InnerMatcher)
1807	: InnerMatcher(InnerMatcher) {}
1808
1809	bool matches(const TypeLoc &Node, ASTMatchFinder *Finder,
1810	BoundNodesTreeBuilder *Builder) const override {
1811	if (!Node)
1812	return false;
1813	return this->InnerMatcher.matches(DynNode: DynTypedNode::create(Node: Node.getType()),
1814	Finder, Builder);
1815	}
1816	};
1817
1818	/// Matches nodes of type \c T for which the inner matcher matches on a
1819	/// another node of type \c T that can be reached using a given traverse
1820	/// function.
1821	template <typename T> class TypeTraverseMatcher : public MatcherInterface<T> {
1822	DynTypedMatcher InnerMatcher;
1823
1824	public:
1825	explicit TypeTraverseMatcher(const Matcher<QualType> &InnerMatcher,
1826	QualType (T::*TraverseFunction)() const)
1827	: InnerMatcher(InnerMatcher), TraverseFunction(TraverseFunction) {}
1828
1829	bool matches(const T &Node, ASTMatchFinder *Finder,
1830	BoundNodesTreeBuilder *Builder) const override {
1831	QualType NextNode = (Node.*TraverseFunction)();
1832	if (NextNode.isNull())
1833	return false;
1834	return this->InnerMatcher.matches(DynTypedNode::create(Node: NextNode), Finder,
1835	Builder);
1836	}
1837
1838	private:
1839	QualType (T::*TraverseFunction)() const;
1840	};
1841
1842	/// Matches nodes of type \c T in a ..Loc hierarchy, for which the inner
1843	/// matcher matches on a another node of type \c T that can be reached using a
1844	/// given traverse function.
1845	template <typename T>
1846	class TypeLocTraverseMatcher : public MatcherInterface<T> {
1847	DynTypedMatcher InnerMatcher;
1848
1849	public:
1850	explicit TypeLocTraverseMatcher(const Matcher<TypeLoc> &InnerMatcher,
1851	TypeLoc (T::*TraverseFunction)() const)
1852	: InnerMatcher(InnerMatcher), TraverseFunction(TraverseFunction) {}
1853
1854	bool matches(const T &Node, ASTMatchFinder *Finder,
1855	BoundNodesTreeBuilder *Builder) const override {
1856	TypeLoc NextNode = (Node.*TraverseFunction)();
1857	if (!NextNode)
1858	return false;
1859	return this->InnerMatcher.matches(DynTypedNode::create(Node: NextNode), Finder,
1860	Builder);
1861	}
1862
1863	private:
1864	TypeLoc (T::*TraverseFunction)() const;
1865	};
1866
1867	/// Converts a \c Matcher<InnerT> to a \c Matcher<OuterT>, where
1868	/// \c OuterT is any type that is supported by \c Getter.
1869	///
1870	/// \code Getter<OuterT>::value() \endcode returns a
1871	/// \code InnerTBase (OuterT::*)() \endcode, which is used to adapt a \c OuterT
1872	/// object into a \c InnerT
1873	template <typename InnerTBase,
1874	template <typename OuterT> class Getter,
1875	template <typename OuterT> class MatcherImpl,
1876	typename ReturnTypesF>
1877	class TypeTraversePolymorphicMatcher {
1878	private:
1879	using Self = TypeTraversePolymorphicMatcher<InnerTBase, Getter, MatcherImpl,
1880	ReturnTypesF>;
1881
1882	static Self create(ArrayRef<const Matcher<InnerTBase> *> InnerMatchers);
1883
1884	public:
1885	using ReturnTypes = typename ExtractFunctionArgMeta<ReturnTypesF>::type;
1886
1887	explicit TypeTraversePolymorphicMatcher(
1888	ArrayRef<const Matcher<InnerTBase> *> InnerMatchers)
1889	: InnerMatcher(makeAllOfComposite(InnerMatchers)) {}
1890
1891	template <typename OuterT> operator Matcher<OuterT>() const {
1892	return Matcher<OuterT>(
1893	new MatcherImpl<OuterT>(InnerMatcher, Getter<OuterT>::value()));
1894	}
1895
1896	struct Func
1897	: public VariadicFunction<Self, Matcher<InnerTBase>, &Self::create> {
1898	Func() {}
1899	};
1900
1901	private:
1902	Matcher<InnerTBase> InnerMatcher;
1903	};
1904
1905	/// A simple memoizer of T(*)() functions.
1906	///
1907	/// It will call the passed 'Func' template parameter at most once.
1908	/// Used to support AST_MATCHER_FUNCTION() macro.
1909	template <typename Matcher, Matcher (*Func)()> class MemoizedMatcher {
1910	struct Wrapper {
1911	Wrapper() : M(Func()) {}
1912
1913	Matcher M;
1914	};
1915
1916	public:
1917	static const Matcher &getInstance() {
1918	static llvm::ManagedStatic<Wrapper> Instance;
1919	return Instance->M;
1920	}
1921	};
1922
1923	// Define the create() method out of line to silence a GCC warning about
1924	// the struct "Func" having greater visibility than its base, which comes from
1925	// using the flag -fvisibility-inlines-hidden.
1926	template <typename InnerTBase, template <typename OuterT> class Getter,
1927	template <typename OuterT> class MatcherImpl, typename ReturnTypesF>
1928	TypeTraversePolymorphicMatcher<InnerTBase, Getter, MatcherImpl, ReturnTypesF>
1929	TypeTraversePolymorphicMatcher<
1930	InnerTBase, Getter, MatcherImpl,
1931	ReturnTypesF>::create(ArrayRef<const Matcher<InnerTBase> *> InnerMatchers) {
1932	return Self(InnerMatchers);
1933	}
1934
1935	// FIXME: unify ClassTemplateSpecializationDecl and TemplateSpecializationType's
1936	// APIs for accessing the template argument list.
1937	inline ArrayRef<TemplateArgument>
1938	getTemplateSpecializationArgs(const ClassTemplateSpecializationDecl &D) {
1939	return D.getTemplateArgs().asArray();
1940	}
1941
1942	inline ArrayRef<TemplateArgument>
1943	getTemplateSpecializationArgs(const TemplateSpecializationType &T) {
1944	return T.template_arguments();
1945	}
1946
1947	inline ArrayRef<TemplateArgument>
1948	getTemplateSpecializationArgs(const FunctionDecl &FD) {
1949	if (const auto* TemplateArgs = FD.getTemplateSpecializationArgs())
1950	return TemplateArgs->asArray();
1951	return ArrayRef<TemplateArgument>();
1952	}
1953
1954	struct NotEqualsBoundNodePredicate {
1955	bool operator()(const internal::BoundNodesMap &Nodes) const {
1956	return Nodes.getNode(ID) != Node;
1957	}
1958
1959	std::string ID;
1960	DynTypedNode Node;
1961	};
1962
1963	template <typename Ty, typename Enable = void> struct GetBodyMatcher {
1964	static const Stmt *get(const Ty &Node) { return Node.getBody(); }
1965	};
1966
1967	template <typename Ty>
1968	struct GetBodyMatcher<
1969	Ty, std::enable_if_t<std::is_base_of<FunctionDecl, Ty>::value>> {
1970	static const Stmt *get(const Ty &Node) {
1971	return Node.doesThisDeclarationHaveABody() ? Node.getBody() : nullptr;
1972	}
1973	};
1974
1975	template <typename NodeType>
1976	inline std::optional<BinaryOperatorKind>
1977	equivalentBinaryOperator(const NodeType &Node) {
1978	return Node.getOpcode();
1979	}
1980
1981	template <>
1982	inline std::optional<BinaryOperatorKind>
1983	equivalentBinaryOperator<CXXOperatorCallExpr>(const CXXOperatorCallExpr &Node) {
1984	if (Node.getNumArgs() != 2)
1985	return std::nullopt;
1986	switch (Node.getOperator()) {
1987	default:
1988	return std::nullopt;
1989	case OO_ArrowStar:
1990	return BO_PtrMemI;
1991	case OO_Star:
1992	return BO_Mul;
1993	case OO_Slash:
1994	return BO_Div;
1995	case OO_Percent:
1996	return BO_Rem;
1997	case OO_Plus:
1998	return BO_Add;
1999	case OO_Minus:
2000	return BO_Sub;
2001	case OO_LessLess:
2002	return BO_Shl;
2003	case OO_GreaterGreater:
2004	return BO_Shr;
2005	case OO_Spaceship:
2006	return BO_Cmp;
2007	case OO_Less:
2008	return BO_LT;
2009	case OO_Greater:
2010	return BO_GT;
2011	case OO_LessEqual:
2012	return BO_LE;
2013	case OO_GreaterEqual:
2014	return BO_GE;
2015	case OO_EqualEqual:
2016	return BO_EQ;
2017	case OO_ExclaimEqual:
2018	return BO_NE;
2019	case OO_Amp:
2020	return BO_And;
2021	case OO_Caret:
2022	return BO_Xor;
2023	case OO_Pipe:
2024	return BO_Or;
2025	case OO_AmpAmp:
2026	return BO_LAnd;
2027	case OO_PipePipe:
2028	return BO_LOr;
2029	case OO_Equal:
2030	return BO_Assign;
2031	case OO_StarEqual:
2032	return BO_MulAssign;
2033	case OO_SlashEqual:
2034	return BO_DivAssign;
2035	case OO_PercentEqual:
2036	return BO_RemAssign;
2037	case OO_PlusEqual:
2038	return BO_AddAssign;
2039	case OO_MinusEqual:
2040	return BO_SubAssign;
2041	case OO_LessLessEqual:
2042	return BO_ShlAssign;
2043	case OO_GreaterGreaterEqual:
2044	return BO_ShrAssign;
2045	case OO_AmpEqual:
2046	return BO_AndAssign;
2047	case OO_CaretEqual:
2048	return BO_XorAssign;
2049	case OO_PipeEqual:
2050	return BO_OrAssign;
2051	case OO_Comma:
2052	return BO_Comma;
2053	}
2054	}
2055
2056	template <typename NodeType>
2057	inline std::optional<UnaryOperatorKind>
2058	equivalentUnaryOperator(const NodeType &Node) {
2059	return Node.getOpcode();
2060	}
2061
2062	template <>
2063	inline std::optional<UnaryOperatorKind>
2064	equivalentUnaryOperator<CXXOperatorCallExpr>(const CXXOperatorCallExpr &Node) {
2065	if (Node.getNumArgs() != 1 && Node.getOperator() != OO_PlusPlus &&
2066	Node.getOperator() != OO_MinusMinus)
2067	return std::nullopt;
2068	switch (Node.getOperator()) {
2069	default:
2070	return std::nullopt;
2071	case OO_Plus:
2072	return UO_Plus;
2073	case OO_Minus:
2074	return UO_Minus;
2075	case OO_Amp:
2076	return UO_AddrOf;
2077	case OO_Star:
2078	return UO_Deref;
2079	case OO_Tilde:
2080	return UO_Not;
2081	case OO_Exclaim:
2082	return UO_LNot;
2083	case OO_PlusPlus: {
2084	const auto *FD = Node.getDirectCallee();
2085	if (!FD)
2086	return std::nullopt;
2087	return FD->getNumParams() > 0 ? UO_PostInc : UO_PreInc;
2088	}
2089	case OO_MinusMinus: {
2090	const auto *FD = Node.getDirectCallee();
2091	if (!FD)
2092	return std::nullopt;
2093	return FD->getNumParams() > 0 ? UO_PostDec : UO_PreDec;
2094	}
2095	case OO_Coawait:
2096	return UO_Coawait;
2097	}
2098	}
2099
2100	template <typename NodeType> inline const Expr *getLHS(const NodeType &Node) {
2101	return Node.getLHS();
2102	}
2103	template <>
2104	inline const Expr *
2105	getLHS<CXXOperatorCallExpr>(const CXXOperatorCallExpr &Node) {
2106	if (!internal::equivalentBinaryOperator(Node))
2107	return nullptr;
2108	return Node.getArg(0);
2109	}
2110	template <typename NodeType> inline const Expr *getRHS(const NodeType &Node) {
2111	return Node.getRHS();
2112	}
2113	template <>
2114	inline const Expr *
2115	getRHS<CXXOperatorCallExpr>(const CXXOperatorCallExpr &Node) {
2116	if (!internal::equivalentBinaryOperator(Node))
2117	return nullptr;
2118	return Node.getArg(1);
2119	}
2120	template <typename NodeType>
2121	inline const Expr *getSubExpr(const NodeType &Node) {
2122	return Node.getSubExpr();
2123	}
2124	template <>
2125	inline const Expr *
2126	getSubExpr<CXXOperatorCallExpr>(const CXXOperatorCallExpr &Node) {
2127	if (!internal::equivalentUnaryOperator(Node))
2128	return nullptr;
2129	return Node.getArg(0);
2130	}
2131
2132	template <typename Ty>
2133	struct HasSizeMatcher {
2134	static bool hasSize(const Ty &Node, unsigned int N) {
2135	return Node.getSize() == N;
2136	}
2137	};
2138
2139	template <>
2140	inline bool HasSizeMatcher<StringLiteral>::hasSize(
2141	const StringLiteral &Node, unsigned int N) {
2142	return Node.getLength() == N;
2143	}
2144
2145	template <typename Ty>
2146	struct GetSourceExpressionMatcher {
2147	static const Expr *get(const Ty &Node) {
2148	return Node.getSubExpr();
2149	}
2150	};
2151
2152	template <>
2153	inline const Expr *GetSourceExpressionMatcher<OpaqueValueExpr>::get(
2154	const OpaqueValueExpr &Node) {
2155	return Node.getSourceExpr();
2156	}
2157
2158	template <typename Ty>
2159	struct CompoundStmtMatcher {
2160	static const CompoundStmt *get(const Ty &Node) {
2161	return &Node;
2162	}
2163	};
2164
2165	template <>
2166	inline const CompoundStmt *
2167	CompoundStmtMatcher<StmtExpr>::get(const StmtExpr &Node) {
2168	return Node.getSubStmt();
2169	}
2170
2171	/// If \p Loc is (transitively) expanded from macro \p MacroName, returns the
2172	/// location (in the chain of expansions) at which \p MacroName was
2173	/// expanded. Since the macro may have been expanded inside a series of
2174	/// expansions, that location may itself be a MacroID.
2175	std::optional<SourceLocation> getExpansionLocOfMacro(StringRef MacroName,
2176	SourceLocation Loc,
2177	const ASTContext &Context);
2178
2179	inline std::optional<StringRef> getOpName(const UnaryOperator &Node) {
2180	return Node.getOpcodeStr(Op: Node.getOpcode());
2181	}
2182	inline std::optional<StringRef> getOpName(const BinaryOperator &Node) {
2183	return Node.getOpcodeStr();
2184	}
2185	inline StringRef getOpName(const CXXRewrittenBinaryOperator &Node) {
2186	return Node.getOpcodeStr();
2187	}
2188	inline std::optional<StringRef> getOpName(const CXXOperatorCallExpr &Node) {
2189	auto optBinaryOpcode = equivalentBinaryOperator(Node);
2190	if (!optBinaryOpcode) {
2191	auto optUnaryOpcode = equivalentUnaryOperator(Node);
2192	if (!optUnaryOpcode)
2193	return std::nullopt;
2194	return UnaryOperator::getOpcodeStr(Op: *optUnaryOpcode);
2195	}
2196	return BinaryOperator::getOpcodeStr(Op: *optBinaryOpcode);
2197	}
2198	inline StringRef getOpName(const CXXFoldExpr &Node) {
2199	return BinaryOperator::getOpcodeStr(Op: Node.getOperator());
2200	}
2201
2202	/// Matches overloaded operators with a specific name.
2203	///
2204	/// The type argument ArgT is not used by this matcher but is used by
2205	/// PolymorphicMatcher and should be std::vector<std::string>>.
2206	template <typename T, typename ArgT = std::vector<std::string>>
2207	class HasAnyOperatorNameMatcher : public SingleNodeMatcherInterface<T> {
2208	static_assert(std::is_same<T, BinaryOperator>::value ||
2209	std::is_same<T, CXXOperatorCallExpr>::value ||
2210	std::is_same<T, CXXRewrittenBinaryOperator>::value ||
2211	std::is_same<T, UnaryOperator>::value,
2212	"Matcher only supports `BinaryOperator`, `UnaryOperator`, "
2213	"`CXXOperatorCallExpr` and `CXXRewrittenBinaryOperator`");
2214	static_assert(std::is_same<ArgT, std::vector<std::string>>::value,
2215	"Matcher ArgT must be std::vector<std::string>");
2216
2217	public:
2218	explicit HasAnyOperatorNameMatcher(std::vector<std::string> Names)
2219	: SingleNodeMatcherInterface<T>(), Names(std::move(Names)) {}
2220
2221	bool matchesNode(const T &Node) const override {
2222	std::optional<StringRef> OptOpName = getOpName(Node);
2223	return OptOpName && llvm::is_contained(Range: Names, Element: *OptOpName);
2224	}
2225
2226	private:
2227	static std::optional<StringRef> getOpName(const UnaryOperator &Node) {
2228	return Node.getOpcodeStr(Op: Node.getOpcode());
2229	}
2230	static std::optional<StringRef> getOpName(const BinaryOperator &Node) {
2231	return Node.getOpcodeStr();
2232	}
2233	static StringRef getOpName(const CXXRewrittenBinaryOperator &Node) {
2234	return Node.getOpcodeStr();
2235	}
2236	static std::optional<StringRef> getOpName(const CXXOperatorCallExpr &Node) {
2237	auto optBinaryOpcode = equivalentBinaryOperator(Node);
2238	if (!optBinaryOpcode) {
2239	auto optUnaryOpcode = equivalentUnaryOperator(Node);
2240	if (!optUnaryOpcode)
2241	return std::nullopt;
2242	return UnaryOperator::getOpcodeStr(Op: *optUnaryOpcode);
2243	}
2244	return BinaryOperator::getOpcodeStr(Op: *optBinaryOpcode);
2245	}
2246
2247	std::vector<std::string> Names;
2248	};
2249
2250	using HasOpNameMatcher =
2251	PolymorphicMatcher<HasAnyOperatorNameMatcher,
2252	void(
2253	TypeList<BinaryOperator, CXXOperatorCallExpr,
2254	CXXRewrittenBinaryOperator, UnaryOperator>),
2255	std::vector<std::string>>;
2256
2257	HasOpNameMatcher hasAnyOperatorNameFunc(ArrayRef<const StringRef *> NameRefs);
2258
2259	using HasOverloadOpNameMatcher =
2260	PolymorphicMatcher<HasOverloadedOperatorNameMatcher,
2261	void(TypeList<CXXOperatorCallExpr, FunctionDecl>),
2262	std::vector<std::string>>;
2263
2264	HasOverloadOpNameMatcher
2265	hasAnyOverloadedOperatorNameFunc(ArrayRef<const StringRef *> NameRefs);
2266
2267	/// Returns true if \p Node has a base specifier matching \p BaseSpec.
2268	///
2269	/// A class is not considered to be derived from itself.
2270	bool matchesAnyBase(const CXXRecordDecl &Node,
2271	const Matcher<CXXBaseSpecifier> &BaseSpecMatcher,
2272	ASTMatchFinder *Finder, BoundNodesTreeBuilder *Builder);
2273
2274	std::shared_ptr<llvm::Regex> createAndVerifyRegex(StringRef Regex,
2275	llvm::Regex::RegexFlags Flags,
2276	StringRef MatcherID);
2277
2278	inline bool
2279	MatchTemplateArgLocAt(const DeclRefExpr &Node, unsigned int Index,
2280	internal::Matcher<TemplateArgumentLoc> InnerMatcher,
2281	internal::ASTMatchFinder *Finder,
2282	internal::BoundNodesTreeBuilder *Builder) {
2283	llvm::ArrayRef<TemplateArgumentLoc> ArgLocs = Node.template_arguments();
2284	return Index < ArgLocs.size() &&
2285	InnerMatcher.matches(Node: ArgLocs[Index], Finder, Builder);
2286	}
2287
2288	inline bool
2289	MatchTemplateArgLocAt(const TemplateSpecializationTypeLoc &Node,
2290	unsigned int Index,
2291	internal::Matcher<TemplateArgumentLoc> InnerMatcher,
2292	internal::ASTMatchFinder *Finder,
2293	internal::BoundNodesTreeBuilder *Builder) {
2294	return !Node.isNull() && Index < Node.getNumArgs() &&
2295	InnerMatcher.matches(Node: Node.getArgLoc(i: Index), Finder, Builder);
2296	}
2297
2298	} // namespace internal
2299
2300	} // namespace ast_matchers
2301
2302	} // namespace clang
2303
2304	#endif // LLVM_CLANG_ASTMATCHERS_ASTMATCHERSINTERNAL_H
2305