contrib/llvm-project/clang/lib/ASTMatchers/Dynamic/Parser.cpp

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