xref: /llvm-project/clang/lib/ASTMatchers/Dynamic/Parser.cpp (revision f0722333dd167245eb3c2b4263529a1ce3679b5c)
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_NewLine) {
358     Error->addError(Tokenizer->peekNextToken().Range,
359                     Error->ET_ParserNoOpenParen)
360         << "NewLine";
361     return false;
362   }
363 
364   if (Tokenizer->nextTokenKind() != TokenInfo::TK_OpenParen) {
365     // Parse as a named value.
366     if (const VariantValue NamedValue =
367             NamedValues ? NamedValues->lookup(NameToken.Text)
368                         : VariantValue()) {
369 
370       if (Tokenizer->nextTokenKind() != TokenInfo::TK_Period) {
371         *Value = NamedValue;
372         return true;
373       }
374 
375       std::string BindID;
376       if (!parseBindID(BindID))
377         return false;
378 
379       assert(NamedValue.isMatcher());
380       llvm::Optional<DynTypedMatcher> Result =
381           NamedValue.getMatcher().getSingleMatcher();
382       if (Result.hasValue()) {
383         llvm::Optional<DynTypedMatcher> Bound = Result->tryBind(BindID);
384         if (Bound.hasValue()) {
385           *Value = VariantMatcher::SingleMatcher(*Bound);
386           return true;
387         }
388       }
389       return false;
390     }
391     // If the syntax is correct and the name is not a matcher either, report
392     // unknown named value.
393     if ((Tokenizer->nextTokenKind() == TokenInfo::TK_Comma ||
394          Tokenizer->nextTokenKind() == TokenInfo::TK_CloseParen ||
395          Tokenizer->nextTokenKind() == TokenInfo::TK_NewLine ||
396          Tokenizer->nextTokenKind() == TokenInfo::TK_Eof) &&
397         !S->lookupMatcherCtor(NameToken.Text)) {
398       Error->addError(NameToken.Range, Error->ET_RegistryValueNotFound)
399           << NameToken.Text;
400       return false;
401     }
402     // Otherwise, fallback to the matcher parser.
403   }
404 
405   Tokenizer->SkipNewlines();
406 
407   // Parse as a matcher expression.
408   return parseMatcherExpressionImpl(NameToken, Value);
409 }
410 
411 bool Parser::parseBindID(std::string &BindID) {
412   // Parse .bind("foo")
413   assert(Tokenizer->peekNextToken().Kind == TokenInfo::TK_Period);
414   Tokenizer->consumeNextToken(); // consume the period.
415   const TokenInfo BindToken = Tokenizer->consumeNextToken();
416   if (BindToken.Kind == TokenInfo::TK_CodeCompletion) {
417     addCompletion(BindToken, MatcherCompletion("bind(\"", "bind", 1));
418     return false;
419   }
420 
421   const TokenInfo OpenToken = Tokenizer->consumeNextToken();
422   const TokenInfo IDToken = Tokenizer->consumeNextTokenIgnoreNewlines();
423   const TokenInfo CloseToken = Tokenizer->consumeNextTokenIgnoreNewlines();
424 
425   // TODO: We could use different error codes for each/some to be more
426   //       explicit about the syntax error.
427   if (BindToken.Kind != TokenInfo::TK_Ident ||
428       BindToken.Text != TokenInfo::ID_Bind) {
429     Error->addError(BindToken.Range, Error->ET_ParserMalformedBindExpr);
430     return false;
431   }
432   if (OpenToken.Kind != TokenInfo::TK_OpenParen) {
433     Error->addError(OpenToken.Range, Error->ET_ParserMalformedBindExpr);
434     return false;
435   }
436   if (IDToken.Kind != TokenInfo::TK_Literal || !IDToken.Value.isString()) {
437     Error->addError(IDToken.Range, Error->ET_ParserMalformedBindExpr);
438     return false;
439   }
440   if (CloseToken.Kind != TokenInfo::TK_CloseParen) {
441     Error->addError(CloseToken.Range, Error->ET_ParserMalformedBindExpr);
442     return false;
443   }
444   BindID = IDToken.Value.getString();
445   return true;
446 }
447 
448 /// Parse and validate a matcher expression.
449 /// \return \c true on success, in which case \c Value has the matcher parsed.
450 ///   If the input is malformed, or some argument has an error, it
451 ///   returns \c false.
452 bool Parser::parseMatcherExpressionImpl(const TokenInfo &NameToken,
453                                         VariantValue *Value) {
454   assert(NameToken.Kind == TokenInfo::TK_Ident);
455   const TokenInfo OpenToken = Tokenizer->consumeNextToken();
456   if (OpenToken.Kind != TokenInfo::TK_OpenParen) {
457     Error->addError(OpenToken.Range, Error->ET_ParserNoOpenParen)
458         << OpenToken.Text;
459     return false;
460   }
461 
462   llvm::Optional<MatcherCtor> Ctor = S->lookupMatcherCtor(NameToken.Text);
463 
464   if (!Ctor) {
465     Error->addError(NameToken.Range, Error->ET_RegistryMatcherNotFound)
466         << NameToken.Text;
467     // Do not return here. We need to continue to give completion suggestions.
468   }
469 
470   std::vector<ParserValue> Args;
471   TokenInfo EndToken;
472 
473   Tokenizer->SkipNewlines();
474 
475   {
476     ScopedContextEntry SCE(this, Ctor ? *Ctor : nullptr);
477 
478     while (Tokenizer->nextTokenKind() != TokenInfo::TK_Eof) {
479       if (Tokenizer->nextTokenKind() == TokenInfo::TK_CloseParen) {
480         // End of args.
481         EndToken = Tokenizer->consumeNextToken();
482         break;
483       }
484       if (!Args.empty()) {
485         // We must find a , token to continue.
486         const TokenInfo CommaToken = Tokenizer->consumeNextToken();
487         if (CommaToken.Kind != TokenInfo::TK_Comma) {
488           Error->addError(CommaToken.Range, Error->ET_ParserNoComma)
489               << CommaToken.Text;
490           return false;
491         }
492       }
493 
494       Diagnostics::Context Ctx(Diagnostics::Context::MatcherArg, Error,
495                                NameToken.Text, NameToken.Range,
496                                Args.size() + 1);
497       ParserValue ArgValue;
498       Tokenizer->SkipNewlines();
499       ArgValue.Text = Tokenizer->peekNextToken().Text;
500       ArgValue.Range = Tokenizer->peekNextToken().Range;
501       if (!parseExpressionImpl(&ArgValue.Value)) {
502         return false;
503       }
504 
505       Tokenizer->SkipNewlines();
506       Args.push_back(ArgValue);
507       SCE.nextArg();
508     }
509   }
510 
511   if (EndToken.Kind == TokenInfo::TK_Eof) {
512     Error->addError(OpenToken.Range, Error->ET_ParserNoCloseParen);
513     return false;
514   }
515 
516   std::string BindID;
517   if (Tokenizer->peekNextToken().Kind == TokenInfo::TK_Period) {
518     if (!parseBindID(BindID))
519       return false;
520   }
521 
522   if (!Ctor)
523     return false;
524 
525   // Merge the start and end infos.
526   Diagnostics::Context Ctx(Diagnostics::Context::ConstructMatcher, Error,
527                            NameToken.Text, NameToken.Range);
528   SourceRange MatcherRange = NameToken.Range;
529   MatcherRange.End = EndToken.Range.End;
530   VariantMatcher Result = S->actOnMatcherExpression(
531       *Ctor, MatcherRange, BindID, Args, Error);
532   if (Result.isNull()) return false;
533 
534   *Value = Result;
535   return true;
536 }
537 
538 // If the prefix of this completion matches the completion token, add it to
539 // Completions minus the prefix.
540 void Parser::addCompletion(const TokenInfo &CompToken,
541                            const MatcherCompletion& Completion) {
542   if (StringRef(Completion.TypedText).startswith(CompToken.Text) &&
543       Completion.Specificity > 0) {
544     Completions.emplace_back(Completion.TypedText.substr(CompToken.Text.size()),
545                              Completion.MatcherDecl, Completion.Specificity);
546   }
547 }
548 
549 std::vector<MatcherCompletion> Parser::getNamedValueCompletions(
550     ArrayRef<ArgKind> AcceptedTypes) {
551   if (!NamedValues) return std::vector<MatcherCompletion>();
552   std::vector<MatcherCompletion> Result;
553   for (const auto &Entry : *NamedValues) {
554     unsigned Specificity;
555     if (Entry.getValue().isConvertibleTo(AcceptedTypes, &Specificity)) {
556       std::string Decl =
557           (Entry.getValue().getTypeAsString() + " " + Entry.getKey()).str();
558       Result.emplace_back(Entry.getKey(), Decl, Specificity);
559     }
560   }
561   return Result;
562 }
563 
564 void Parser::addExpressionCompletions() {
565   const TokenInfo CompToken = Tokenizer->consumeNextTokenIgnoreNewlines();
566   assert(CompToken.Kind == TokenInfo::TK_CodeCompletion);
567 
568   // We cannot complete code if there is an invalid element on the context
569   // stack.
570   for (ContextStackTy::iterator I = ContextStack.begin(),
571                                 E = ContextStack.end();
572        I != E; ++I) {
573     if (!I->first)
574       return;
575   }
576 
577   auto AcceptedTypes = S->getAcceptedCompletionTypes(ContextStack);
578   for (const auto &Completion : S->getMatcherCompletions(AcceptedTypes)) {
579     addCompletion(CompToken, Completion);
580   }
581 
582   for (const auto &Completion : getNamedValueCompletions(AcceptedTypes)) {
583     addCompletion(CompToken, Completion);
584   }
585 }
586 
587 /// Parse an <Expression>
588 bool Parser::parseExpressionImpl(VariantValue *Value) {
589   switch (Tokenizer->nextTokenKind()) {
590   case TokenInfo::TK_Literal:
591     *Value = Tokenizer->consumeNextToken().Value;
592     return true;
593 
594   case TokenInfo::TK_Ident:
595     return parseIdentifierPrefixImpl(Value);
596 
597   case TokenInfo::TK_CodeCompletion:
598     addExpressionCompletions();
599     return false;
600 
601   case TokenInfo::TK_Eof:
602     Error->addError(Tokenizer->consumeNextToken().Range,
603                     Error->ET_ParserNoCode);
604     return false;
605 
606   case TokenInfo::TK_Error:
607     // This error was already reported by the tokenizer.
608     return false;
609   case TokenInfo::TK_NewLine:
610     llvm_unreachable("Newline should never be found here");
611     return false;
612   case TokenInfo::TK_OpenParen:
613   case TokenInfo::TK_CloseParen:
614   case TokenInfo::TK_Comma:
615   case TokenInfo::TK_Period:
616   case TokenInfo::TK_InvalidChar:
617     const TokenInfo Token = Tokenizer->consumeNextToken();
618     Error->addError(Token.Range, Error->ET_ParserInvalidToken) << 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