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