1//===- Parser.h - Matcher expression parser ---------------------*- 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/// \file
10/// Simple matcher expression parser.
11///
12/// The parser understands matcher expressions of the form:
13/// MatcherName(Arg0, Arg1, ..., ArgN)
14/// as well as simple types like strings.
15/// The parser does not know how to process the matchers. It delegates this task
16/// to a Sema object received as an argument.
17///
18/// \code
19/// Grammar for the expressions supported:
20/// <Expression> := <Literal> | <NamedValue> | <MatcherExpression>
21/// <Literal> := <StringLiteral> | <Boolean> | <Double> | <Unsigned>
22/// <StringLiteral> := "quoted string"
23/// <Boolean> := true | false
24/// <Double> := [0-9]+.[0-9]* | [0-9]+.[0-9]*[eE][-+]?[0-9]+
25/// <Unsigned> := [0-9]+
26/// <NamedValue> := <Identifier>
27/// <MatcherExpression> := <Identifier>(<ArgumentList>) |
28/// <Identifier>(<ArgumentList>).bind(<StringLiteral>)
29/// <Identifier> := [a-zA-Z]+
30/// <ArgumentList> := <Expression> | <Expression>,<ArgumentList>
31/// \endcode
32//
33//===----------------------------------------------------------------------===//
34
35#ifndef LLVM_CLANG_ASTMATCHERS_DYNAMIC_PARSER_H
36#define LLVM_CLANG_ASTMATCHERS_DYNAMIC_PARSER_H
37
38#include "clang/ASTMatchers/ASTMatchersInternal.h"
39#include "clang/ASTMatchers/Dynamic/Registry.h"
40#include "clang/ASTMatchers/Dynamic/VariantValue.h"
41#include "llvm/ADT/ArrayRef.h"
42#include "llvm/ADT/StringMap.h"
43#include "llvm/ADT/StringRef.h"
44#include <optional>
45#include <utility>
46#include <vector>
47
48namespace clang {
49namespace ast_matchers {
50namespace dynamic {
51
52class Diagnostics;
53
54/// Matcher expression parser.
55class Parser {
56public:
57 /// Interface to connect the parser with the registry and more.
58 ///
59 /// The parser uses the Sema instance passed into
60 /// parseMatcherExpression() to handle all matcher tokens. The simplest
61 /// processor implementation would simply call into the registry to create
62 /// the matchers.
63 /// However, a more complex processor might decide to intercept the matcher
64 /// creation and do some extra work. For example, it could apply some
65 /// transformation to the matcher by adding some id() nodes, or could detect
66 /// specific matcher nodes for more efficient lookup.
67 class Sema {
68 public:
69 virtual ~Sema();
70
71 /// Process a matcher expression.
72 ///
73 /// All the arguments passed here have already been processed.
74 ///
75 /// \param Ctor A matcher constructor looked up by lookupMatcherCtor.
76 ///
77 /// \param NameRange The location of the name in the matcher source.
78 /// Useful for error reporting.
79 ///
80 /// \param BindID The ID to use to bind the matcher, or a null \c StringRef
81 /// if no ID is specified.
82 ///
83 /// \param Args The argument list for the matcher.
84 ///
85 /// \return The matcher objects constructed by the processor, or a null
86 /// matcher if an error occurred. In that case, \c Error will contain a
87 /// description of the error.
88 virtual VariantMatcher actOnMatcherExpression(MatcherCtor Ctor,
89 SourceRange NameRange,
90 StringRef BindID,
91 ArrayRef<ParserValue> Args,
92 Diagnostics *Error) = 0;
93
94 /// Look up a matcher by name.
95 ///
96 /// \param MatcherName The matcher name found by the parser.
97 ///
98 /// \return The matcher constructor, or std::optional<MatcherCtor>() if not
99 /// found.
100 virtual std::optional<MatcherCtor>
101 lookupMatcherCtor(StringRef MatcherName) = 0;
102
103 virtual bool isBuilderMatcher(MatcherCtor) const = 0;
104
105 virtual ASTNodeKind nodeMatcherType(MatcherCtor) const = 0;
106
107 virtual internal::MatcherDescriptorPtr
108 buildMatcherCtor(MatcherCtor, SourceRange NameRange,
109 ArrayRef<ParserValue> Args, Diagnostics *Error) const = 0;
110
111 /// Compute the list of completion types for \p Context.
112 ///
113 /// Each element of \p Context represents a matcher invocation, going from
114 /// outermost to innermost. Elements are pairs consisting of a reference to
115 /// the matcher constructor and the index of the next element in the
116 /// argument list of that matcher (or for the last element, the index of
117 /// the completion point in the argument list). An empty list requests
118 /// completion for the root matcher.
119 virtual std::vector<ArgKind> getAcceptedCompletionTypes(
120 llvm::ArrayRef<std::pair<MatcherCtor, unsigned>> Context);
121
122 /// Compute the list of completions that match any of
123 /// \p AcceptedTypes.
124 ///
125 /// \param AcceptedTypes All types accepted for this completion.
126 ///
127 /// \return All completions for the specified types.
128 /// Completions should be valid when used in \c lookupMatcherCtor().
129 /// The matcher constructed from the return of \c lookupMatcherCtor()
130 /// should be convertible to some type in \p AcceptedTypes.
131 virtual std::vector<MatcherCompletion>
132 getMatcherCompletions(llvm::ArrayRef<ArgKind> AcceptedTypes);
133 };
134
135 /// Sema implementation that uses the matcher registry to process the
136 /// tokens.
137 class RegistrySema : public Parser::Sema {
138 public:
139 ~RegistrySema() override;
140
141 std::optional<MatcherCtor>
142 lookupMatcherCtor(StringRef MatcherName) override;
143
144 VariantMatcher actOnMatcherExpression(MatcherCtor Ctor,
145 SourceRange NameRange,
146 StringRef BindID,
147 ArrayRef<ParserValue> Args,
148 Diagnostics *Error) override;
149
150 std::vector<ArgKind> getAcceptedCompletionTypes(
151 llvm::ArrayRef<std::pair<MatcherCtor, unsigned>> Context) override;
152
153 bool isBuilderMatcher(MatcherCtor Ctor) const override;
154
155 ASTNodeKind nodeMatcherType(MatcherCtor) const override;
156
157 internal::MatcherDescriptorPtr
158 buildMatcherCtor(MatcherCtor, SourceRange NameRange,
159 ArrayRef<ParserValue> Args,
160 Diagnostics *Error) const override;
161
162 std::vector<MatcherCompletion>
163 getMatcherCompletions(llvm::ArrayRef<ArgKind> AcceptedTypes) override;
164 };
165
166 using NamedValueMap = llvm::StringMap<VariantValue>;
167
168 /// Parse a matcher expression.
169 ///
170 /// \param MatcherCode The matcher expression to parse.
171 ///
172 /// \param S The Sema instance that will help the parser
173 /// construct the matchers. If null, it uses the default registry.
174 ///
175 /// \param NamedValues A map of precomputed named values. This provides
176 /// the dictionary for the <NamedValue> rule of the grammar.
177 /// If null, it is ignored.
178 ///
179 /// \return The matcher object constructed by the processor, or an empty
180 /// Optional if an error occurred. In that case, \c Error will contain a
181 /// description of the error.
182 /// The caller takes ownership of the DynTypedMatcher object returned.
183 static std::optional<DynTypedMatcher>
184 parseMatcherExpression(StringRef &MatcherCode, Sema *S,
185 const NamedValueMap *NamedValues, Diagnostics *Error);
186 static std::optional<DynTypedMatcher>
187 parseMatcherExpression(StringRef &MatcherCode, Sema *S, Diagnostics *Error) {
188 return parseMatcherExpression(MatcherCode, S, NamedValues: nullptr, Error);
189 }
190 static std::optional<DynTypedMatcher>
191 parseMatcherExpression(StringRef &MatcherCode, Diagnostics *Error) {
192 return parseMatcherExpression(MatcherCode, S: nullptr, Error);
193 }
194
195 /// Parse an expression.
196 ///
197 /// Parses any expression supported by this parser. In general, the
198 /// \c parseMatcherExpression function is a better approach to get a matcher
199 /// object.
200 ///
201 /// \param S The Sema instance that will help the parser
202 /// construct the matchers. If null, it uses the default registry.
203 ///
204 /// \param NamedValues A map of precomputed named values. This provides
205 /// the dictionary for the <NamedValue> rule of the grammar.
206 /// If null, it is ignored.
207 static bool parseExpression(StringRef &Code, Sema *S,
208 const NamedValueMap *NamedValues,
209 VariantValue *Value, Diagnostics *Error);
210 static bool parseExpression(StringRef &Code, Sema *S, VariantValue *Value,
211 Diagnostics *Error) {
212 return parseExpression(Code, S, NamedValues: nullptr, Value, Error);
213 }
214 static bool parseExpression(StringRef &Code, VariantValue *Value,
215 Diagnostics *Error) {
216 return parseExpression(Code, S: nullptr, Value, Error);
217 }
218
219 /// Complete an expression at the given offset.
220 ///
221 /// \param S The Sema instance that will help the parser
222 /// construct the matchers. If null, it uses the default registry.
223 ///
224 /// \param NamedValues A map of precomputed named values. This provides
225 /// the dictionary for the <NamedValue> rule of the grammar.
226 /// If null, it is ignored.
227 ///
228 /// \return The list of completions, which may be empty if there are no
229 /// available completions or if an error occurred.
230 static std::vector<MatcherCompletion>
231 completeExpression(StringRef &Code, unsigned CompletionOffset, Sema *S,
232 const NamedValueMap *NamedValues);
233 static std::vector<MatcherCompletion>
234 completeExpression(StringRef &Code, unsigned CompletionOffset, Sema *S) {
235 return completeExpression(Code, CompletionOffset, S, NamedValues: nullptr);
236 }
237 static std::vector<MatcherCompletion>
238 completeExpression(StringRef &Code, unsigned CompletionOffset) {
239 return completeExpression(Code, CompletionOffset, S: nullptr);
240 }
241
242private:
243 class CodeTokenizer;
244 struct ScopedContextEntry;
245 struct TokenInfo;
246
247 Parser(CodeTokenizer *Tokenizer, Sema *S,
248 const NamedValueMap *NamedValues,
249 Diagnostics *Error);
250
251 bool parseBindID(std::string &BindID);
252 bool parseExpressionImpl(VariantValue *Value);
253 bool parseMatcherBuilder(MatcherCtor Ctor, const TokenInfo &NameToken,
254 const TokenInfo &OpenToken, VariantValue *Value);
255 bool parseMatcherExpressionImpl(const TokenInfo &NameToken,
256 const TokenInfo &OpenToken,
257 std::optional<MatcherCtor> Ctor,
258 VariantValue *Value);
259 bool parseIdentifierPrefixImpl(VariantValue *Value);
260
261 void addCompletion(const TokenInfo &CompToken,
262 const MatcherCompletion &Completion);
263 void addExpressionCompletions();
264
265 std::vector<MatcherCompletion>
266 getNamedValueCompletions(ArrayRef<ArgKind> AcceptedTypes);
267
268 CodeTokenizer *const Tokenizer;
269 Sema *const S;
270 const NamedValueMap *const NamedValues;
271 Diagnostics *const Error;
272
273 using ContextStackTy = std::vector<std::pair<MatcherCtor, unsigned>>;
274
275 ContextStackTy ContextStack;
276 std::vector<MatcherCompletion> Completions;
277};
278
279} // namespace dynamic
280} // namespace ast_matchers
281} // namespace clang
282
283#endif // LLVM_CLANG_ASTMATCHERS_DYNAMIC_PARSER_H
284