xref: /llvm-project/clang/lib/ASTMatchers/Dynamic/Parser.cpp (revision 2019cea863edd12df1a95ba1cddefcdc91b3c576) 
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     // Identifier could be a name known by Sema as a named value.
429     const VariantValue NamedValue =
430         S->getNamedValue(Tokenizer->peekNextToken().Text);
431     if (!NamedValue.isNothing()) {
432       Tokenizer->consumeNextToken();  // Actually consume it.
433       *Value = NamedValue;
434       return true;
435     }
436     // Fallback to full matcher parsing.
437     return parseMatcherExpressionImpl(Value);
438   }
439 
440   case TokenInfo::TK_CodeCompletion:
441     addExpressionCompletions();
442     return false;
443 
444   case TokenInfo::TK_Eof:
445     Error->addError(Tokenizer->consumeNextToken().Range,
446                     Error->ET_ParserNoCode);
447     return false;
448 
449   case TokenInfo::TK_Error:
450     // This error was already reported by the tokenizer.
451     return false;
452 
453   case TokenInfo::TK_OpenParen:
454   case TokenInfo::TK_CloseParen:
455   case TokenInfo::TK_Comma:
456   case TokenInfo::TK_Period:
457   case TokenInfo::TK_InvalidChar:
458     const TokenInfo Token = Tokenizer->consumeNextToken();
459     Error->addError(Token.Range, Error->ET_ParserInvalidToken) << Token.Text;
460     return false;
461   }
462 
463   llvm_unreachable("Unknown token kind.");
464 }
465 
466 Parser::Parser(CodeTokenizer *Tokenizer, Sema *S,
467                Diagnostics *Error)
468     : Tokenizer(Tokenizer), S(S), Error(Error) {}
469 
470 Parser::RegistrySema::~RegistrySema() {}
471 
472 llvm::Optional<MatcherCtor> Parser::RegistrySema::lookupMatcherCtor(
473     StringRef MatcherName, const SourceRange &NameRange, Diagnostics *Error) {
474   return Registry::lookupMatcherCtor(MatcherName, NameRange, Error);
475 }
476 
477 VariantMatcher Parser::RegistrySema::actOnMatcherExpression(
478     MatcherCtor Ctor, const SourceRange &NameRange, StringRef BindID,
479     ArrayRef<ParserValue> Args, Diagnostics *Error) {
480   if (BindID.empty()) {
481     return Registry::constructMatcher(Ctor, NameRange, Args, Error);
482   } else {
483     return Registry::constructBoundMatcher(Ctor, NameRange, BindID, Args,
484                                            Error);
485   }
486 }
487 
488 bool Parser::parseExpression(StringRef Code, VariantValue *Value,
489                              Diagnostics *Error) {
490   RegistrySema S;
491   return parseExpression(Code, &S, Value, Error);
492 }
493 
494 bool Parser::parseExpression(StringRef Code, Sema *S,
495                              VariantValue *Value, Diagnostics *Error) {
496   CodeTokenizer Tokenizer(Code, Error);
497   if (!Parser(&Tokenizer, S, Error).parseExpressionImpl(Value)) return false;
498   if (Tokenizer.peekNextToken().Kind != TokenInfo::TK_Eof) {
499     Error->addError(Tokenizer.peekNextToken().Range,
500                     Error->ET_ParserTrailingCode);
501     return false;
502   }
503   return true;
504 }
505 
506 std::vector<MatcherCompletion>
507 Parser::completeExpression(StringRef Code, unsigned CompletionOffset) {
508   Diagnostics Error;
509   CodeTokenizer Tokenizer(Code, &Error, CompletionOffset);
510   RegistrySema S;
511   Parser P(&Tokenizer, &S, &Error);
512   VariantValue Dummy;
513   P.parseExpressionImpl(&Dummy);
514 
515   return P.Completions;
516 }
517 
518 llvm::Optional<DynTypedMatcher>
519 Parser::parseMatcherExpression(StringRef Code, Diagnostics *Error) {
520   RegistrySema S;
521   return parseMatcherExpression(Code, &S, Error);
522 }
523 
524 llvm::Optional<DynTypedMatcher>
525 Parser::parseMatcherExpression(StringRef Code, Parser::Sema *S,
526                                Diagnostics *Error) {
527   VariantValue Value;
528   if (!parseExpression(Code, S, &Value, Error))
529     return llvm::Optional<DynTypedMatcher>();
530   if (!Value.isMatcher()) {
531     Error->addError(SourceRange(), Error->ET_ParserNotAMatcher);
532     return llvm::Optional<DynTypedMatcher>();
533   }
534   llvm::Optional<DynTypedMatcher> Result =
535       Value.getMatcher().getSingleMatcher();
536   if (!Result.hasValue()) {
537     Error->addError(SourceRange(), Error->ET_ParserOverloadedType)
538         << Value.getTypeAsString();
539   }
540   return Result;
541 }
542 
543 }  // namespace dynamic
544 }  // namespace ast_matchers
545 }  // namespace clang
546