1 //===- Parser.cpp - Matcher expression parser -----------------------------===//
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 /// Recursive parser implementation for the matcher expression grammar.
11 ///
12 //===----------------------------------------------------------------------===//
13 
14 #include "clang/ASTMatchers/Dynamic/Parser.h"
15 #include "clang/ASTMatchers/ASTMatchersInternal.h"
16 #include "clang/ASTMatchers/Dynamic/Diagnostics.h"
17 #include "clang/ASTMatchers/Dynamic/Registry.h"
18 #include "clang/Basic/CharInfo.h"
19 #include "llvm/ADT/Optional.h"
20 #include "llvm/ADT/StringRef.h"
21 #include "llvm/Support/ErrorHandling.h"
22 #include "llvm/Support/ManagedStatic.h"
23 #include <algorithm>
24 #include <cassert>
25 #include <cerrno>
26 #include <cstddef>
27 #include <cstdlib>
28 #include <string>
29 #include <utility>
30 #include <vector>
31 
32 namespace clang {
33 namespace ast_matchers {
34 namespace dynamic {
35 
36 /// Simple structure to hold information for one token from the parser.
37 struct Parser::TokenInfo {
38   /// Different possible tokens.
39   enum TokenKind {
40     TK_Eof,
41     TK_NewLine,
42     TK_OpenParen,
43     TK_CloseParen,
44     TK_Comma,
45     TK_Period,
46     TK_Literal,
47     TK_Ident,
48     TK_InvalidChar,
49     TK_Error,
50     TK_CodeCompletion
51   };
52 
53   /// Some known identifiers.
54   static const char* const ID_Bind;
55 
56   TokenInfo() = default;
57 
58   StringRef Text;
59   TokenKind Kind = TK_Eof;
60   SourceRange Range;
61   VariantValue Value;
62 };
63 
64 const char* const Parser::TokenInfo::ID_Bind = "bind";
65 
66 /// Simple tokenizer for the parser.
67 class Parser::CodeTokenizer {
68 public:
69   explicit CodeTokenizer(StringRef &MatcherCode, Diagnostics *Error)
70       : Code(MatcherCode), StartOfLine(MatcherCode), Error(Error) {
71     NextToken = getNextToken();
72   }
73 
74   CodeTokenizer(StringRef &MatcherCode, Diagnostics *Error,
75                 unsigned CodeCompletionOffset)
76       : Code(MatcherCode), StartOfLine(MatcherCode), Error(Error),
77         CodeCompletionLocation(MatcherCode.data() + CodeCompletionOffset) {
78     NextToken = getNextToken();
79   }
80 
81   /// Returns but doesn't consume the next token.
82   const TokenInfo &peekNextToken() const { return NextToken; }
83 
84   /// Consumes and returns the next token.
85   TokenInfo consumeNextToken() {
86     TokenInfo ThisToken = NextToken;
87     NextToken = getNextToken();
88     return ThisToken;
89   }
90 
91   TokenInfo SkipNewlines() {
92     while (NextToken.Kind == TokenInfo::TK_NewLine)
93       NextToken = getNextToken();
94     return NextToken;
95   }
96 
97   TokenInfo consumeNextTokenIgnoreNewlines() {
98     SkipNewlines();
99     if (NextToken.Kind == TokenInfo::TK_Eof)
100       return NextToken;
101     return consumeNextToken();
102   }
103 
104   TokenInfo::TokenKind nextTokenKind() const { return NextToken.Kind; }
105 
106 private:
107   TokenInfo getNextToken() {
108     consumeWhitespace();
109     TokenInfo Result;
110     Result.Range.Start = currentLocation();
111 
112     if (CodeCompletionLocation && CodeCompletionLocation <= Code.data()) {
113       Result.Kind = TokenInfo::TK_CodeCompletion;
114       Result.Text = StringRef(CodeCompletionLocation, 0);
115       CodeCompletionLocation = nullptr;
116       return Result;
117     }
118 
119     if (Code.empty()) {
120       Result.Kind = TokenInfo::TK_Eof;
121       Result.Text = "";
122       return Result;
123     }
124 
125     switch (Code[0]) {
126     case '#':
127       Code = Code.drop_until([](char c) { return c == '\n'; });
128       return getNextToken();
129     case ',':
130       Result.Kind = TokenInfo::TK_Comma;
131       Result.Text = Code.substr(0, 1);
132       Code = Code.drop_front();
133       break;
134     case '.':
135       Result.Kind = TokenInfo::TK_Period;
136       Result.Text = Code.substr(0, 1);
137       Code = Code.drop_front();
138       break;
139     case '\n':
140       ++Line;
141       StartOfLine = Code.drop_front();
142       Result.Kind = TokenInfo::TK_NewLine;
143       Result.Text = Code.substr(0, 1);
144       Code = Code.drop_front();
145       break;
146     case '(':
147       Result.Kind = TokenInfo::TK_OpenParen;
148       Result.Text = Code.substr(0, 1);
149       Code = Code.drop_front();
150       break;
151     case ')':
152       Result.Kind = TokenInfo::TK_CloseParen;
153       Result.Text = Code.substr(0, 1);
154       Code = Code.drop_front();
155       break;
156 
157     case '"':
158     case '\'':
159       // Parse a string literal.
160       consumeStringLiteral(&Result);
161       break;
162 
163     case '0': case '1': case '2': case '3': case '4':
164     case '5': case '6': case '7': case '8': case '9':
165       // Parse an unsigned and float literal.
166       consumeNumberLiteral(&Result);
167       break;
168 
169     default:
170       if (isAlphanumeric(Code[0])) {
171         // Parse an identifier
172         size_t TokenLength = 1;
173         while (true) {
174           // A code completion location in/immediately after an identifier will
175           // cause the portion of the identifier before the code completion
176           // location to become a code completion token.
177           if (CodeCompletionLocation == Code.data() + TokenLength) {
178             CodeCompletionLocation = nullptr;
179             Result.Kind = TokenInfo::TK_CodeCompletion;
180             Result.Text = Code.substr(0, TokenLength);
181             Code = Code.drop_front(TokenLength);
182             return Result;
183           }
184           if (TokenLength == Code.size() || !isAlphanumeric(Code[TokenLength]))
185             break;
186           ++TokenLength;
187         }
188         if (TokenLength == 4 && Code.startswith("true")) {
189           Result.Kind = TokenInfo::TK_Literal;
190           Result.Value = true;
191         } else if (TokenLength == 5 && Code.startswith("false")) {
192           Result.Kind = TokenInfo::TK_Literal;
193           Result.Value = false;
194         } else {
195           Result.Kind = TokenInfo::TK_Ident;
196           Result.Text = Code.substr(0, TokenLength);
197         }
198         Code = Code.drop_front(TokenLength);
199       } else {
200         Result.Kind = TokenInfo::TK_InvalidChar;
201         Result.Text = Code.substr(0, 1);
202         Code = Code.drop_front(1);
203       }
204       break;
205     }
206 
207     Result.Range.End = currentLocation();
208     return Result;
209   }
210 
211   /// Consume an unsigned and float literal.
212   void consumeNumberLiteral(TokenInfo *Result) {
213     bool isFloatingLiteral = false;
214     unsigned Length = 1;
215     if (Code.size() > 1) {
216       // Consume the 'x' or 'b' radix modifier, if present.
217       switch (toLowercase(Code[1])) {
218       case 'x': case 'b': Length = 2;
219       }
220     }
221     while (Length < Code.size() && isHexDigit(Code[Length]))
222       ++Length;
223 
224     // Try to recognize a floating point literal.
225     while (Length < Code.size()) {
226       char c = Code[Length];
227       if (c == '-' || c == '+' || c == '.' || isHexDigit(c)) {
228         isFloatingLiteral = true;
229         Length++;
230       } else {
231         break;
232       }
233     }
234 
235     Result->Text = Code.substr(0, Length);
236     Code = Code.drop_front(Length);
237 
238     if (isFloatingLiteral) {
239       char *end;
240       errno = 0;
241       std::string Text = Result->Text.str();
242       double doubleValue = strtod(Text.c_str(), &end);
243       if (*end == 0 && errno == 0) {
244         Result->Kind = TokenInfo::TK_Literal;
245         Result->Value = doubleValue;
246         return;
247       }
248     } else {
249       unsigned Value;
250       if (!Result->Text.getAsInteger(0, Value)) {
251         Result->Kind = TokenInfo::TK_Literal;
252         Result->Value = Value;
253         return;
254       }
255     }
256 
257     SourceRange Range;
258     Range.Start = Result->Range.Start;
259     Range.End = currentLocation();
260     Error->addError(Range, Error->ET_ParserNumberError) << Result->Text;
261     Result->Kind = TokenInfo::TK_Error;
262   }
263 
264   /// Consume a string literal.
265   ///
266   /// \c Code must be positioned at the start of the literal (the opening
267   /// quote). Consumed until it finds the same closing quote character.
268   void consumeStringLiteral(TokenInfo *Result) {
269     bool InEscape = false;
270     const char Marker = Code[0];
271     for (size_t Length = 1, Size = Code.size(); Length != Size; ++Length) {
272       if (InEscape) {
273         InEscape = false;
274         continue;
275       }
276       if (Code[Length] == '\\') {
277         InEscape = true;
278         continue;
279       }
280       if (Code[Length] == Marker) {
281         Result->Kind = TokenInfo::TK_Literal;
282         Result->Text = Code.substr(0, Length + 1);
283         Result->Value = Code.substr(1, Length - 1);
284         Code = Code.drop_front(Length + 1);
285         return;
286       }
287     }
288 
289     StringRef ErrorText = Code;
290     Code = Code.drop_front(Code.size());
291     SourceRange Range;
292     Range.Start = Result->Range.Start;
293     Range.End = currentLocation();
294     Error->addError(Range, Error->ET_ParserStringError) << ErrorText;
295     Result->Kind = TokenInfo::TK_Error;
296   }
297 
298   /// Consume all leading whitespace from \c Code.
299   void consumeWhitespace() {
300     Code = Code.drop_while([](char c) {
301       // Don't trim newlines.
302       return StringRef(" \t\v\f\r").contains(c);
303     });
304   }
305 
306   SourceLocation currentLocation() {
307     SourceLocation Location;
308     Location.Line = Line;
309     Location.Column = Code.data() - StartOfLine.data() + 1;
310     return Location;
311   }
312 
313   StringRef &Code;
314   StringRef StartOfLine;
315   unsigned Line = 1;
316   Diagnostics *Error;
317   TokenInfo NextToken;
318   const char *CodeCompletionLocation = nullptr;
319 };
320 
321 Parser::Sema::~Sema() = default;
322 
323 std::vector<ArgKind> Parser::Sema::getAcceptedCompletionTypes(
324     llvm::ArrayRef<std::pair<MatcherCtor, unsigned>> Context) {
325   return {};
326 }
327 
328 std::vector<MatcherCompletion>
329 Parser::Sema::getMatcherCompletions(llvm::ArrayRef<ArgKind> AcceptedTypes) {
330   return {};
331 }
332 
333 struct Parser::ScopedContextEntry {
334   Parser *P;
335 
336   ScopedContextEntry(Parser *P, MatcherCtor C) : P(P) {
337     P->ContextStack.push_back(std::make_pair(C, 0u));
338   }
339 
340   ~ScopedContextEntry() {
341     P->ContextStack.pop_back();
342   }
343 
344   void nextArg() {
345     ++P->ContextStack.back().second;
346   }
347 };
348 
349 /// Parse expressions that start with an identifier.
350 ///
351 /// This function can parse named values and matchers.
352 /// In case of failure it will try to determine the user's intent to give
353 /// an appropriate error message.
354 bool Parser::parseIdentifierPrefixImpl(VariantValue *Value) {
355   const TokenInfo NameToken = Tokenizer->consumeNextToken();
356 
357   if (Tokenizer->nextTokenKind() != TokenInfo::TK_OpenParen) {
358     // Parse as a named value.
359     if (const VariantValue NamedValue =
360             NamedValues ? NamedValues->lookup(NameToken.Text)
361                         : VariantValue()) {
362 
363       if (Tokenizer->nextTokenKind() != TokenInfo::TK_Period) {
364         *Value = NamedValue;
365         return true;
366       }
367 
368       std::string BindID;
369       if (!parseBindID(BindID))
370         return false;
371 
372       assert(NamedValue.isMatcher());
373       llvm::Optional<DynTypedMatcher> Result =
374           NamedValue.getMatcher().getSingleMatcher();
375       if (Result.hasValue()) {
376         llvm::Optional<DynTypedMatcher> Bound = Result->tryBind(BindID);
377         if (Bound.hasValue()) {
378           *Value = VariantMatcher::SingleMatcher(*Bound);
379           return true;
380         }
381       }
382       return false;
383     }
384 
385     if (Tokenizer->nextTokenKind() == TokenInfo::TK_NewLine) {
386       Error->addError(Tokenizer->peekNextToken().Range,
387                       Error->ET_ParserNoOpenParen)
388           << "NewLine";
389       return false;
390     }
391 
392     // If the syntax is correct and the name is not a matcher either, report
393     // unknown named value.
394     if ((Tokenizer->nextTokenKind() == TokenInfo::TK_Comma ||
395          Tokenizer->nextTokenKind() == TokenInfo::TK_CloseParen ||
396          Tokenizer->nextTokenKind() == TokenInfo::TK_NewLine ||
397          Tokenizer->nextTokenKind() == TokenInfo::TK_Eof) &&
398         !S->lookupMatcherCtor(NameToken.Text)) {
399       Error->addError(NameToken.Range, Error->ET_RegistryValueNotFound)
400           << NameToken.Text;
401       return false;
402     }
403     // Otherwise, fallback to the matcher parser.
404   }
405 
406   Tokenizer->SkipNewlines();
407 
408   // Parse as a matcher expression.
409   return parseMatcherExpressionImpl(NameToken, Value);
410 }
411 
412 bool Parser::parseBindID(std::string &BindID) {
413   // Parse .bind("foo")
414   assert(Tokenizer->peekNextToken().Kind == TokenInfo::TK_Period);
415   Tokenizer->consumeNextToken(); // consume the period.
416   const TokenInfo BindToken = Tokenizer->consumeNextToken();
417   if (BindToken.Kind == TokenInfo::TK_CodeCompletion) {
418     addCompletion(BindToken, MatcherCompletion("bind(\"", "bind", 1));
419     return false;
420   }
421 
422   const TokenInfo OpenToken = Tokenizer->consumeNextToken();
423   const TokenInfo IDToken = Tokenizer->consumeNextTokenIgnoreNewlines();
424   const TokenInfo CloseToken = Tokenizer->consumeNextTokenIgnoreNewlines();
425 
426   // TODO: We could use different error codes for each/some to be more
427   //       explicit about the syntax error.
428   if (BindToken.Kind != TokenInfo::TK_Ident ||
429       BindToken.Text != TokenInfo::ID_Bind) {
430     Error->addError(BindToken.Range, Error->ET_ParserMalformedBindExpr);
431     return false;
432   }
433   if (OpenToken.Kind != TokenInfo::TK_OpenParen) {
434     Error->addError(OpenToken.Range, Error->ET_ParserMalformedBindExpr);
435     return false;
436   }
437   if (IDToken.Kind != TokenInfo::TK_Literal || !IDToken.Value.isString()) {
438     Error->addError(IDToken.Range, Error->ET_ParserMalformedBindExpr);
439     return false;
440   }
441   if (CloseToken.Kind != TokenInfo::TK_CloseParen) {
442     Error->addError(CloseToken.Range, Error->ET_ParserMalformedBindExpr);
443     return false;
444   }
445   BindID = IDToken.Value.getString();
446   return true;
447 }
448 
449 /// Parse and validate a matcher expression.
450 /// \return \c true on success, in which case \c Value has the matcher parsed.
451 ///   If the input is malformed, or some argument has an error, it
452 ///   returns \c false.
453 bool Parser::parseMatcherExpressionImpl(const TokenInfo &NameToken,
454                                         VariantValue *Value) {
455   assert(NameToken.Kind == TokenInfo::TK_Ident);
456   const TokenInfo OpenToken = Tokenizer->consumeNextToken();
457   if (OpenToken.Kind != TokenInfo::TK_OpenParen) {
458     Error->addError(OpenToken.Range, Error->ET_ParserNoOpenParen)
459         << OpenToken.Text;
460     return false;
461   }
462 
463   llvm::Optional<MatcherCtor> Ctor = S->lookupMatcherCtor(NameToken.Text);
464 
465   if (!Ctor) {
466     Error->addError(NameToken.Range, Error->ET_RegistryMatcherNotFound)
467         << NameToken.Text;
468     // Do not return here. We need to continue to give completion suggestions.
469   }
470 
471   std::vector<ParserValue> Args;
472   TokenInfo EndToken;
473 
474   Tokenizer->SkipNewlines();
475 
476   {
477     ScopedContextEntry SCE(this, Ctor ? *Ctor : nullptr);
478 
479     while (Tokenizer->nextTokenKind() != TokenInfo::TK_Eof) {
480       if (Tokenizer->nextTokenKind() == TokenInfo::TK_CloseParen) {
481         // End of args.
482         EndToken = Tokenizer->consumeNextToken();
483         break;
484       }
485       if (!Args.empty()) {
486         // We must find a , token to continue.
487         const TokenInfo CommaToken = Tokenizer->consumeNextToken();
488         if (CommaToken.Kind != TokenInfo::TK_Comma) {
489           Error->addError(CommaToken.Range, Error->ET_ParserNoComma)
490               << CommaToken.Text;
491           return false;
492         }
493       }
494 
495       Diagnostics::Context Ctx(Diagnostics::Context::MatcherArg, Error,
496                                NameToken.Text, NameToken.Range,
497                                Args.size() + 1);
498       ParserValue ArgValue;
499       Tokenizer->SkipNewlines();
500       ArgValue.Text = Tokenizer->peekNextToken().Text;
501       ArgValue.Range = Tokenizer->peekNextToken().Range;
502       if (!parseExpressionImpl(&ArgValue.Value)) {
503         return false;
504       }
505 
506       Tokenizer->SkipNewlines();
507       Args.push_back(ArgValue);
508       SCE.nextArg();
509     }
510   }
511 
512   if (EndToken.Kind == TokenInfo::TK_Eof) {
513     Error->addError(OpenToken.Range, Error->ET_ParserNoCloseParen);
514     return false;
515   }
516 
517   std::string BindID;
518   if (Tokenizer->peekNextToken().Kind == TokenInfo::TK_Period) {
519     if (!parseBindID(BindID))
520       return false;
521   }
522 
523   if (!Ctor)
524     return false;
525 
526   // Merge the start and end infos.
527   Diagnostics::Context Ctx(Diagnostics::Context::ConstructMatcher, Error,
528                            NameToken.Text, NameToken.Range);
529   SourceRange MatcherRange = NameToken.Range;
530   MatcherRange.End = EndToken.Range.End;
531   VariantMatcher Result = S->actOnMatcherExpression(
532       *Ctor, MatcherRange, BindID, Args, Error);
533   if (Result.isNull()) return false;
534 
535   *Value = Result;
536   return true;
537 }
538 
539 // If the prefix of this completion matches the completion token, add it to
540 // Completions minus the prefix.
541 void Parser::addCompletion(const TokenInfo &CompToken,
542                            const MatcherCompletion& Completion) {
543   if (StringRef(Completion.TypedText).startswith(CompToken.Text) &&
544       Completion.Specificity > 0) {
545     Completions.emplace_back(Completion.TypedText.substr(CompToken.Text.size()),
546                              Completion.MatcherDecl, Completion.Specificity);
547   }
548 }
549 
550 std::vector<MatcherCompletion> Parser::getNamedValueCompletions(
551     ArrayRef<ArgKind> AcceptedTypes) {
552   if (!NamedValues) return std::vector<MatcherCompletion>();
553   std::vector<MatcherCompletion> Result;
554   for (const auto &Entry : *NamedValues) {
555     unsigned Specificity;
556     if (Entry.getValue().isConvertibleTo(AcceptedTypes, &Specificity)) {
557       std::string Decl =
558           (Entry.getValue().getTypeAsString() + " " + Entry.getKey()).str();
559       Result.emplace_back(Entry.getKey(), Decl, Specificity);
560     }
561   }
562   return Result;
563 }
564 
565 void Parser::addExpressionCompletions() {
566   const TokenInfo CompToken = Tokenizer->consumeNextTokenIgnoreNewlines();
567   assert(CompToken.Kind == TokenInfo::TK_CodeCompletion);
568 
569   // We cannot complete code if there is an invalid element on the context
570   // stack.
571   for (ContextStackTy::iterator I = ContextStack.begin(),
572                                 E = ContextStack.end();
573        I != E; ++I) {
574     if (!I->first)
575       return;
576   }
577 
578   auto AcceptedTypes = S->getAcceptedCompletionTypes(ContextStack);
579   for (const auto &Completion : S->getMatcherCompletions(AcceptedTypes)) {
580     addCompletion(CompToken, Completion);
581   }
582 
583   for (const auto &Completion : getNamedValueCompletions(AcceptedTypes)) {
584     addCompletion(CompToken, Completion);
585   }
586 }
587 
588 /// Parse an <Expression>
589 bool Parser::parseExpressionImpl(VariantValue *Value) {
590   switch (Tokenizer->nextTokenKind()) {
591   case TokenInfo::TK_Literal:
592     *Value = Tokenizer->consumeNextToken().Value;
593     return true;
594 
595   case TokenInfo::TK_Ident:
596     return parseIdentifierPrefixImpl(Value);
597 
598   case TokenInfo::TK_CodeCompletion:
599     addExpressionCompletions();
600     return false;
601 
602   case TokenInfo::TK_Eof:
603     Error->addError(Tokenizer->consumeNextToken().Range,
604                     Error->ET_ParserNoCode);
605     return false;
606 
607   case TokenInfo::TK_Error:
608     // This error was already reported by the tokenizer.
609     return false;
610   case TokenInfo::TK_NewLine:
611   case TokenInfo::TK_OpenParen:
612   case TokenInfo::TK_CloseParen:
613   case TokenInfo::TK_Comma:
614   case TokenInfo::TK_Period:
615   case TokenInfo::TK_InvalidChar:
616     const TokenInfo Token = Tokenizer->consumeNextToken();
617     Error->addError(Token.Range, Error->ET_ParserInvalidToken)
618         << (Token.Kind == TokenInfo::TK_NewLine ? "NewLine" : Token.Text);
619     return false;
620   }
621 
622   llvm_unreachable("Unknown token kind.");
623 }
624 
625 static llvm::ManagedStatic<Parser::RegistrySema> DefaultRegistrySema;
626 
627 Parser::Parser(CodeTokenizer *Tokenizer, Sema *S,
628                const NamedValueMap *NamedValues, Diagnostics *Error)
629     : Tokenizer(Tokenizer), S(S ? S : &*DefaultRegistrySema),
630       NamedValues(NamedValues), Error(Error) {}
631 
632 Parser::RegistrySema::~RegistrySema() = default;
633 
634 llvm::Optional<MatcherCtor>
635 Parser::RegistrySema::lookupMatcherCtor(StringRef MatcherName) {
636   return Registry::lookupMatcherCtor(MatcherName);
637 }
638 
639 VariantMatcher Parser::RegistrySema::actOnMatcherExpression(
640     MatcherCtor Ctor, SourceRange NameRange, StringRef BindID,
641     ArrayRef<ParserValue> Args, Diagnostics *Error) {
642   if (BindID.empty()) {
643     return Registry::constructMatcher(Ctor, NameRange, Args, Error);
644   } else {
645     return Registry::constructBoundMatcher(Ctor, NameRange, BindID, Args,
646                                            Error);
647   }
648 }
649 
650 std::vector<ArgKind> Parser::RegistrySema::getAcceptedCompletionTypes(
651     ArrayRef<std::pair<MatcherCtor, unsigned>> Context) {
652   return Registry::getAcceptedCompletionTypes(Context);
653 }
654 
655 std::vector<MatcherCompletion> Parser::RegistrySema::getMatcherCompletions(
656     ArrayRef<ArgKind> AcceptedTypes) {
657   return Registry::getMatcherCompletions(AcceptedTypes);
658 }
659 
660 bool Parser::parseExpression(StringRef &Code, Sema *S,
661                              const NamedValueMap *NamedValues,
662                              VariantValue *Value, Diagnostics *Error) {
663   CodeTokenizer Tokenizer(Code, Error);
664   if (!Parser(&Tokenizer, S, NamedValues, Error).parseExpressionImpl(Value))
665     return false;
666   auto NT = Tokenizer.peekNextToken();
667   if (NT.Kind != TokenInfo::TK_Eof && NT.Kind != TokenInfo::TK_NewLine) {
668     Error->addError(Tokenizer.peekNextToken().Range,
669                     Error->ET_ParserTrailingCode);
670     return false;
671   }
672   return true;
673 }
674 
675 std::vector<MatcherCompletion>
676 Parser::completeExpression(StringRef &Code, unsigned CompletionOffset, Sema *S,
677                            const NamedValueMap *NamedValues) {
678   Diagnostics Error;
679   CodeTokenizer Tokenizer(Code, &Error, CompletionOffset);
680   Parser P(&Tokenizer, S, NamedValues, &Error);
681   VariantValue Dummy;
682   P.parseExpressionImpl(&Dummy);
683 
684   // Sort by specificity, then by name.
685   llvm::sort(P.Completions,
686              [](const MatcherCompletion &A, const MatcherCompletion &B) {
687                if (A.Specificity != B.Specificity)
688                  return A.Specificity > B.Specificity;
689                return A.TypedText < B.TypedText;
690              });
691 
692   return P.Completions;
693 }
694 
695 llvm::Optional<DynTypedMatcher>
696 Parser::parseMatcherExpression(StringRef &Code, Sema *S,
697                                const NamedValueMap *NamedValues,
698                                Diagnostics *Error) {
699   VariantValue Value;
700   if (!parseExpression(Code, S, NamedValues, &Value, Error))
701     return llvm::Optional<DynTypedMatcher>();
702   if (!Value.isMatcher()) {
703     Error->addError(SourceRange(), Error->ET_ParserNotAMatcher);
704     return llvm::Optional<DynTypedMatcher>();
705   }
706   llvm::Optional<DynTypedMatcher> Result =
707       Value.getMatcher().getSingleMatcher();
708   if (!Result.hasValue()) {
709     Error->addError(SourceRange(), Error->ET_ParserOverloadedType)
710         << Value.getTypeAsString();
711   }
712   return Result;
713 }
714 
715 } // namespace dynamic
716 } // namespace ast_matchers
717 } // namespace clang
718