xref: /llvm-project/clang/lib/ASTMatchers/Dynamic/Parser.cpp (revision 252444a77718ef8b456338a7a08f3211c6fede93) 
1 //===--- Parser.cpp - 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 /// \brief Recursive parser implementation for the matcher expression grammar.
12 ///
13 //===----------------------------------------------------------------------===//
14 
15 #include "clang/ASTMatchers/Dynamic/Parser.h"
16 #include "clang/ASTMatchers/Dynamic/Registry.h"
17 #include "clang/Basic/CharInfo.h"
18 #include "llvm/ADT/Optional.h"
19 #include "llvm/ADT/Twine.h"
20 #include <string>
21 #include <vector>
22 
23 namespace clang {
24 namespace ast_matchers {
25 namespace dynamic {
26 
27 /// \brief Simple structure to hold information for one token from the parser.
28 struct Parser::TokenInfo {
29   /// \brief Different possible tokens.
30   enum TokenKind {
31     TK_Eof,
32     TK_OpenParen,
33     TK_CloseParen,
34     TK_Comma,
35     TK_Period,
36     TK_Literal,
37     TK_Ident,
38     TK_InvalidChar,
39     TK_Error,
40     TK_CodeCompletion
41   };
42 
43   /// \brief Some known identifiers.
44   static const char* const ID_Bind;
45 
46   TokenInfo() : Text(), Kind(TK_Eof), Range(), Value() {}
47 
48   StringRef Text;
49   TokenKind Kind;
50   SourceRange Range;
51   VariantValue Value;
52 };
53 
54 const char* const Parser::TokenInfo::ID_Bind = "bind";
55 
56 /// \brief Simple tokenizer for the parser.
57 class Parser::CodeTokenizer {
58 public:
59   explicit CodeTokenizer(StringRef MatcherCode, Diagnostics *Error)
60       : Code(MatcherCode), StartOfLine(MatcherCode), Line(1), Error(Error),
61         CodeCompletionLocation(0) {
62     NextToken = getNextToken();
63   }
64 
65   CodeTokenizer(StringRef MatcherCode, Diagnostics *Error,
66                 unsigned CodeCompletionOffset)
67       : Code(MatcherCode), StartOfLine(MatcherCode), Line(1), Error(Error),
68         CodeCompletionLocation(MatcherCode.data() + CodeCompletionOffset) {
69     NextToken = getNextToken();
70   }
71 
72   /// \brief Returns but doesn't consume the next token.
73   const TokenInfo &peekNextToken() const { return NextToken; }
74 
75   /// \brief Consumes and returns the next token.
76   TokenInfo consumeNextToken() {
77     TokenInfo ThisToken = NextToken;
78     NextToken = getNextToken();
79     return ThisToken;
80   }
81 
82   TokenInfo::TokenKind nextTokenKind() const { return NextToken.Kind; }
83 
84 private:
85   TokenInfo getNextToken() {
86     consumeWhitespace();
87     TokenInfo Result;
88     Result.Range.Start = currentLocation();
89 
90     if (CodeCompletionLocation && CodeCompletionLocation <= Code.data()) {
91       Result.Kind = TokenInfo::TK_CodeCompletion;
92       Result.Text = StringRef(CodeCompletionLocation, 0);
93       CodeCompletionLocation = 0;
94       return Result;
95     }
96 
97     if (Code.empty()) {
98       Result.Kind = TokenInfo::TK_Eof;
99       Result.Text = "";
100       return Result;
101     }
102 
103     switch (Code[0]) {
104     case ',':
105       Result.Kind = TokenInfo::TK_Comma;
106       Result.Text = Code.substr(0, 1);
107       Code = Code.drop_front();
108       break;
109     case '.':
110       Result.Kind = TokenInfo::TK_Period;
111       Result.Text = Code.substr(0, 1);
112       Code = Code.drop_front();
113       break;
114     case '(':
115       Result.Kind = TokenInfo::TK_OpenParen;
116       Result.Text = Code.substr(0, 1);
117       Code = Code.drop_front();
118       break;
119     case ')':
120       Result.Kind = TokenInfo::TK_CloseParen;
121       Result.Text = Code.substr(0, 1);
122       Code = Code.drop_front();
123       break;
124 
125     case '"':
126     case '\'':
127       // Parse a string literal.
128       consumeStringLiteral(&Result);
129       break;
130 
131     case '0': case '1': case '2': case '3': case '4':
132     case '5': case '6': case '7': case '8': case '9':
133       // Parse an unsigned literal.
134       consumeUnsignedLiteral(&Result);
135       break;
136 
137     default:
138       if (isAlphanumeric(Code[0])) {
139         // Parse an identifier
140         size_t TokenLength = 1;
141         while (1) {
142           // A code completion location in/immediately after an identifier will
143           // cause the portion of the identifier before the code completion
144           // location to become a code completion token.
145           if (CodeCompletionLocation == Code.data() + TokenLength) {
146             CodeCompletionLocation = 0;
147             Result.Kind = TokenInfo::TK_CodeCompletion;
148             Result.Text = Code.substr(0, TokenLength);
149             Code = Code.drop_front(TokenLength);
150             return Result;
151           }
152           if (TokenLength == Code.size() || !isAlphanumeric(Code[TokenLength]))
153             break;
154           ++TokenLength;
155         }
156         Result.Kind = TokenInfo::TK_Ident;
157         Result.Text = Code.substr(0, TokenLength);
158         Code = Code.drop_front(TokenLength);
159       } else {
160         Result.Kind = TokenInfo::TK_InvalidChar;
161         Result.Text = Code.substr(0, 1);
162         Code = Code.drop_front(1);
163       }
164       break;
165     }
166 
167     Result.Range.End = currentLocation();
168     return Result;
169   }
170 
171   /// \brief Consume an unsigned literal.
172   void consumeUnsignedLiteral(TokenInfo *Result) {
173     unsigned Length = 1;
174     if (Code.size() > 1) {
175       // Consume the 'x' or 'b' radix modifier, if present.
176       switch (toLowercase(Code[1])) {
177       case 'x': case 'b': Length = 2;
178       }
179     }
180     while (Length < Code.size() && isHexDigit(Code[Length]))
181       ++Length;
182 
183     Result->Text = Code.substr(0, Length);
184     Code = Code.drop_front(Length);
185 
186     unsigned Value;
187     if (!Result->Text.getAsInteger(0, Value)) {
188       Result->Kind = TokenInfo::TK_Literal;
189       Result->Value = Value;
190     } else {
191       SourceRange Range;
192       Range.Start = Result->Range.Start;
193       Range.End = currentLocation();
194       Error->addError(Range, Error->ET_ParserUnsignedError) << Result->Text;
195       Result->Kind = TokenInfo::TK_Error;
196     }
197   }
198 
199   /// \brief Consume a string literal.
200   ///
201   /// \c Code must be positioned at the start of the literal (the opening
202   /// quote). Consumed until it finds the same closing quote character.
203   void consumeStringLiteral(TokenInfo *Result) {
204     bool InEscape = false;
205     const char Marker = Code[0];
206     for (size_t Length = 1, Size = Code.size(); Length != Size; ++Length) {
207       if (InEscape) {
208         InEscape = false;
209         continue;
210       }
211       if (Code[Length] == '\\') {
212         InEscape = true;
213         continue;
214       }
215       if (Code[Length] == Marker) {
216         Result->Kind = TokenInfo::TK_Literal;
217         Result->Text = Code.substr(0, Length + 1);
218         Result->Value = Code.substr(1, Length - 1).str();
219         Code = Code.drop_front(Length + 1);
220         return;
221       }
222     }
223 
224     StringRef ErrorText = Code;
225     Code = Code.drop_front(Code.size());
226     SourceRange Range;
227     Range.Start = Result->Range.Start;
228     Range.End = currentLocation();
229     Error->addError(Range, Error->ET_ParserStringError) << ErrorText;
230     Result->Kind = TokenInfo::TK_Error;
231   }
232 
233   /// \brief Consume all leading whitespace from \c Code.
234   void consumeWhitespace() {
235     while (!Code.empty() && isWhitespace(Code[0])) {
236       if (Code[0] == '\n') {
237         ++Line;
238         StartOfLine = Code.drop_front();
239       }
240       Code = Code.drop_front();
241     }
242   }
243 
244   SourceLocation currentLocation() {
245     SourceLocation Location;
246     Location.Line = Line;
247     Location.Column = Code.data() - StartOfLine.data() + 1;
248     return Location;
249   }
250 
251   StringRef Code;
252   StringRef StartOfLine;
253   unsigned Line;
254   Diagnostics *Error;
255   TokenInfo NextToken;
256   const char *CodeCompletionLocation;
257 };
258 
259 Parser::Sema::~Sema() {}
260 
261 struct Parser::ScopedContextEntry {
262   Parser *P;
263 
264   ScopedContextEntry(Parser *P, MatcherCtor C) : P(P) {
265     P->ContextStack.push_back(std::make_pair(C, 0u));
266   }
267 
268   ~ScopedContextEntry() {
269     P->ContextStack.pop_back();
270   }
271 
272   void nextArg() {
273     ++P->ContextStack.back().second;
274   }
275 };
276 
277 /// \brief Parse and validate a matcher expression.
278 /// \return \c true on success, in which case \c Value has the matcher parsed.
279 ///   If the input is malformed, or some argument has an error, it
280 ///   returns \c false.
281 bool Parser::parseMatcherExpressionImpl(VariantValue *Value) {
282   const TokenInfo NameToken = Tokenizer->consumeNextToken();
283   assert(NameToken.Kind == TokenInfo::TK_Ident);
284   const TokenInfo OpenToken = Tokenizer->consumeNextToken();
285   if (OpenToken.Kind != TokenInfo::TK_OpenParen) {
286     Error->addError(OpenToken.Range, Error->ET_ParserNoOpenParen)
287         << OpenToken.Text;
288     return false;
289   }
290 
291   llvm::Optional<MatcherCtor> Ctor =
292       S->lookupMatcherCtor(NameToken.Text, NameToken.Range, Error);
293   std::vector<ParserValue> Args;
294   TokenInfo EndToken;
295 
296   {
297     ScopedContextEntry SCE(this, Ctor ? *Ctor : 0);
298 
299     while (Tokenizer->nextTokenKind() != TokenInfo::TK_Eof) {
300       if (Tokenizer->nextTokenKind() == TokenInfo::TK_CloseParen) {
301         // End of args.
302         EndToken = Tokenizer->consumeNextToken();
303         break;
304       }
305       if (Args.size() > 0) {
306         // We must find a , token to continue.
307         const TokenInfo CommaToken = Tokenizer->consumeNextToken();
308         if (CommaToken.Kind != TokenInfo::TK_Comma) {
309           Error->addError(CommaToken.Range, Error->ET_ParserNoComma)
310               << CommaToken.Text;
311           return false;
312         }
313       }
314 
315       Diagnostics::Context Ctx(Diagnostics::Context::MatcherArg, Error,
316                                NameToken.Text, NameToken.Range,
317                                Args.size() + 1);
318       ParserValue ArgValue;
319       ArgValue.Text = Tokenizer->peekNextToken().Text;
320       ArgValue.Range = Tokenizer->peekNextToken().Range;
321       if (!parseExpressionImpl(&ArgValue.Value)) {
322         return false;
323       }
324 
325       Args.push_back(ArgValue);
326       SCE.nextArg();
327     }
328   }
329 
330   if (EndToken.Kind == TokenInfo::TK_Eof) {
331     Error->addError(OpenToken.Range, Error->ET_ParserNoCloseParen);
332     return false;
333   }
334 
335   std::string BindID;
336   if (Tokenizer->peekNextToken().Kind == TokenInfo::TK_Period) {
337     // Parse .bind("foo")
338     Tokenizer->consumeNextToken();  // consume the period.
339     const TokenInfo BindToken = Tokenizer->consumeNextToken();
340     if (BindToken.Kind == TokenInfo::TK_CodeCompletion) {
341       addCompletion(BindToken, "bind(\"", "bind");
342       return false;
343     }
344 
345     const TokenInfo OpenToken = Tokenizer->consumeNextToken();
346     const TokenInfo IDToken = Tokenizer->consumeNextToken();
347     const TokenInfo CloseToken = Tokenizer->consumeNextToken();
348 
349     // TODO: We could use different error codes for each/some to be more
350     //       explicit about the syntax error.
351     if (BindToken.Kind != TokenInfo::TK_Ident ||
352         BindToken.Text != TokenInfo::ID_Bind) {
353       Error->addError(BindToken.Range, Error->ET_ParserMalformedBindExpr);
354       return false;
355     }
356     if (OpenToken.Kind != TokenInfo::TK_OpenParen) {
357       Error->addError(OpenToken.Range, Error->ET_ParserMalformedBindExpr);
358       return false;
359     }
360     if (IDToken.Kind != TokenInfo::TK_Literal || !IDToken.Value.isString()) {
361       Error->addError(IDToken.Range, Error->ET_ParserMalformedBindExpr);
362       return false;
363     }
364     if (CloseToken.Kind != TokenInfo::TK_CloseParen) {
365       Error->addError(CloseToken.Range, Error->ET_ParserMalformedBindExpr);
366       return false;
367     }
368     BindID = IDToken.Value.getString();
369   }
370 
371   if (!Ctor)
372     return false;
373 
374   // Merge the start and end infos.
375   Diagnostics::Context Ctx(Diagnostics::Context::ConstructMatcher, Error,
376                            NameToken.Text, NameToken.Range);
377   SourceRange MatcherRange = NameToken.Range;
378   MatcherRange.End = EndToken.Range.End;
379   VariantMatcher Result = S->actOnMatcherExpression(
380       *Ctor, MatcherRange, BindID, Args, Error);
381   if (Result.isNull()) return false;
382 
383   *Value = Result;
384   return true;
385 }
386 
387 // If the prefix of this completion matches the completion token, add it to
388 // Completions minus the prefix.
389 void Parser::addCompletion(const TokenInfo &CompToken, StringRef TypedText,
390                            StringRef Decl) {
391   if (TypedText.size() >= CompToken.Text.size() &&
392       TypedText.substr(0, CompToken.Text.size()) == CompToken.Text) {
393     Completions.push_back(
394         MatcherCompletion(TypedText.substr(CompToken.Text.size()), Decl));
395   }
396 }
397 
398 void Parser::addExpressionCompletions() {
399   const TokenInfo CompToken = Tokenizer->consumeNextToken();
400   assert(CompToken.Kind == TokenInfo::TK_CodeCompletion);
401 
402   // We cannot complete code if there is an invalid element on the context
403   // stack.
404   for (ContextStackTy::iterator I = ContextStack.begin(),
405                                 E = ContextStack.end();
406        I != E; ++I) {
407     if (!I->first)
408       return;
409   }
410 
411   std::vector<MatcherCompletion> RegCompletions =
412       Registry::getCompletions(ContextStack);
413   for (std::vector<MatcherCompletion>::iterator I = RegCompletions.begin(),
414                                                 E = RegCompletions.end();
415        I != E; ++I) {
416     addCompletion(CompToken, I->TypedText, I->MatcherDecl);
417   }
418 }
419 
420 /// \brief Parse an <Expresssion>
421 bool Parser::parseExpressionImpl(VariantValue *Value) {
422   switch (Tokenizer->nextTokenKind()) {
423   case TokenInfo::TK_Literal:
424     *Value = Tokenizer->consumeNextToken().Value;
425     return true;
426 
427   case TokenInfo::TK_Ident:
428     return parseMatcherExpressionImpl(Value);
429 
430   case TokenInfo::TK_CodeCompletion:
431     addExpressionCompletions();
432     return false;
433 
434   case TokenInfo::TK_Eof:
435     Error->addError(Tokenizer->consumeNextToken().Range,
436                     Error->ET_ParserNoCode);
437     return false;
438 
439   case TokenInfo::TK_Error:
440     // This error was already reported by the tokenizer.
441     return false;
442 
443   case TokenInfo::TK_OpenParen:
444   case TokenInfo::TK_CloseParen:
445   case TokenInfo::TK_Comma:
446   case TokenInfo::TK_Period:
447   case TokenInfo::TK_InvalidChar:
448     const TokenInfo Token = Tokenizer->consumeNextToken();
449     Error->addError(Token.Range, Error->ET_ParserInvalidToken) << Token.Text;
450     return false;
451   }
452 
453   llvm_unreachable("Unknown token kind.");
454 }
455 
456 Parser::Parser(CodeTokenizer *Tokenizer, Sema *S,
457                Diagnostics *Error)
458     : Tokenizer(Tokenizer), S(S), Error(Error) {}
459 
460 class RegistrySema : public Parser::Sema {
461 public:
462   virtual ~RegistrySema() {}
463   llvm::Optional<MatcherCtor> lookupMatcherCtor(StringRef MatcherName,
464                                                 const SourceRange &NameRange,
465                                                 Diagnostics *Error) {
466     return Registry::lookupMatcherCtor(MatcherName, NameRange, Error);
467   }
468   VariantMatcher actOnMatcherExpression(MatcherCtor Ctor,
469                                         const SourceRange &NameRange,
470                                         StringRef BindID,
471                                         ArrayRef<ParserValue> Args,
472                                         Diagnostics *Error) {
473     if (BindID.empty()) {
474       return Registry::constructMatcher(Ctor, NameRange, Args, Error);
475     } else {
476       return Registry::constructBoundMatcher(Ctor, NameRange, BindID, Args,
477                                              Error);
478     }
479   }
480 };
481 
482 bool Parser::parseExpression(StringRef Code, VariantValue *Value,
483                              Diagnostics *Error) {
484   RegistrySema S;
485   return parseExpression(Code, &S, Value, Error);
486 }
487 
488 bool Parser::parseExpression(StringRef Code, Sema *S,
489                              VariantValue *Value, Diagnostics *Error) {
490   CodeTokenizer Tokenizer(Code, Error);
491   if (!Parser(&Tokenizer, S, Error).parseExpressionImpl(Value)) return false;
492   if (Tokenizer.peekNextToken().Kind != TokenInfo::TK_Eof) {
493     Error->addError(Tokenizer.peekNextToken().Range,
494                     Error->ET_ParserTrailingCode);
495     return false;
496   }
497   return true;
498 }
499 
500 std::vector<MatcherCompletion>
501 Parser::completeExpression(StringRef Code, unsigned CompletionOffset) {
502   Diagnostics Error;
503   CodeTokenizer Tokenizer(Code, &Error, CompletionOffset);
504   RegistrySema S;
505   Parser P(&Tokenizer, &S, &Error);
506   VariantValue Dummy;
507   P.parseExpressionImpl(&Dummy);
508 
509   return P.Completions;
510 }
511 
512 llvm::Optional<DynTypedMatcher>
513 Parser::parseMatcherExpression(StringRef Code, Diagnostics *Error) {
514   RegistrySema S;
515   return parseMatcherExpression(Code, &S, Error);
516 }
517 
518 llvm::Optional<DynTypedMatcher>
519 Parser::parseMatcherExpression(StringRef Code, Parser::Sema *S,
520                                Diagnostics *Error) {
521   VariantValue Value;
522   if (!parseExpression(Code, S, &Value, Error))
523     return llvm::Optional<DynTypedMatcher>();
524   if (!Value.isMatcher()) {
525     Error->addError(SourceRange(), Error->ET_ParserNotAMatcher);
526     return llvm::Optional<DynTypedMatcher>();
527   }
528   llvm::Optional<DynTypedMatcher> Result =
529       Value.getMatcher().getSingleMatcher();
530   if (!Result.hasValue()) {
531     Error->addError(SourceRange(), Error->ET_ParserOverloadedType)
532         << Value.getTypeAsString();
533   }
534   return Result;
535 }
536 
537 }  // namespace dynamic
538 }  // namespace ast_matchers
539 }  // namespace clang
540