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/StringRef.h"
  20 #include "llvm/Support/ErrorHandling.h"
  21 #include "llvm/Support/ManagedStatic.h"
  22 #include <algorithm>
  23 #include <cassert>
  24 #include <cerrno>
  25 #include <cstddef>
  26 #include <cstdlib>
  27 #include <optional>
  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   static const char *const ID_With;
  56
  57   TokenInfo() = default;
  58
  59   StringRef Text;
  60   TokenKind Kind = TK_Eof;
  61   SourceRange Range;
  62   VariantValue Value;
  63 };
  64
  65 const char* const Parser::TokenInfo::ID_Bind = "bind";
  66 const char *const Parser::TokenInfo::ID_With = "with";
  67
  68 /// Simple tokenizer for the parser.
  69 class Parser::CodeTokenizer {
  70 public:
  71   explicit CodeTokenizer(StringRef &MatcherCode, Diagnostics *Error)
  72       : Code(MatcherCode), StartOfLine(MatcherCode), Error(Error) {
  73     NextToken = getNextToken();
  74   }
  75
  76   CodeTokenizer(StringRef &MatcherCode, Diagnostics *Error,
  77                 unsigned CodeCompletionOffset)
  78       : Code(MatcherCode), StartOfLine(MatcherCode), Error(Error),
  79         CodeCompletionLocation(MatcherCode.data() + CodeCompletionOffset) {
  80     NextToken = getNextToken();
  81   }
  82
  83   /// Returns but doesn't consume the next token.
  84   const TokenInfo &peekNextToken() const { return NextToken; }
  85
  86   /// Consumes and returns the next token.
  87   TokenInfo consumeNextToken() {
  88     TokenInfo ThisToken = NextToken;
  89     NextToken = getNextToken();
  90     return ThisToken;
  91   }
  92
  93   TokenInfo SkipNewlines() {
  94     while (NextToken.Kind == TokenInfo::TK_NewLine)
  95       NextToken = getNextToken();
  96     return NextToken;
  97   }
  98
  99   TokenInfo consumeNextTokenIgnoreNewlines() {
 100     SkipNewlines();
 101     if (NextToken.Kind == TokenInfo::TK_Eof)
 102       return NextToken;
 103     return consumeNextToken();
 104   }
 105
 106   TokenInfo::TokenKind nextTokenKind() const { return NextToken.Kind; }
 107
 108 private:
 109   TokenInfo getNextToken() {
 110     consumeWhitespace();
 111     TokenInfo Result;
 112     Result.Range.Start = currentLocation();
 113
 114     if (CodeCompletionLocation && CodeCompletionLocation <= Code.data()) {
 115       Result.Kind = TokenInfo::TK_CodeCompletion;
 116       Result.Text = StringRef(CodeCompletionLocation, 0);
 117       CodeCompletionLocation = nullptr;
 118       return Result;
 119     }
 120
 121     if (Code.empty()) {
 122       Result.Kind = TokenInfo::TK_Eof;
 123       Result.Text = "";
 124       return Result;
 125     }
 126
 127     switch (Code[0]) {
 128     case '#':
 129       Code = Code.drop_until([](char c) { return c == '\n'; });
 130       return getNextToken();
 131     case ',':
 132       Result.Kind = TokenInfo::TK_Comma;
 133       Result.Text = Code.substr(0, 1);
 134       Code = Code.drop_front();
 135       break;
 136     case '.':
 137       Result.Kind = TokenInfo::TK_Period;
 138       Result.Text = Code.substr(0, 1);
 139       Code = Code.drop_front();
 140       break;
 141     case '\n':
 142       ++Line;
 143       StartOfLine = Code.drop_front();
 144       Result.Kind = TokenInfo::TK_NewLine;
 145       Result.Text = Code.substr(0, 1);
 146       Code = Code.drop_front();
 147       break;
 148     case '(':
 149       Result.Kind = TokenInfo::TK_OpenParen;
 150       Result.Text = Code.substr(0, 1);
 151       Code = Code.drop_front();
 152       break;
 153     case ')':
 154       Result.Kind = TokenInfo::TK_CloseParen;
 155       Result.Text = Code.substr(0, 1);
 156       Code = Code.drop_front();
 157       break;
 158
 159     case '"':
 160     case '\'':
 161       // Parse a string literal.
 162       consumeStringLiteral(&Result);
 163       break;
 164
 165     case '0': case '1': case '2': case '3': case '4':
 166     case '5': case '6': case '7': case '8': case '9':
 167       // Parse an unsigned and float literal.
 168       consumeNumberLiteral(&Result);
 169       break;
 170
 171     default:
 172       if (isAlphanumeric(Code[0])) {
 173         // Parse an identifier
 174         size_t TokenLength = 1;
 175         while (true) {
 176           // A code completion location in/immediately after an identifier will
 177           // cause the portion of the identifier before the code completion
 178           // location to become a code completion token.
 179           if (CodeCompletionLocation == Code.data() + TokenLength) {
 180             CodeCompletionLocation = nullptr;
 181             Result.Kind = TokenInfo::TK_CodeCompletion;
 182             Result.Text = Code.substr(0, TokenLength);
 183             Code = Code.drop_front(TokenLength);
 184             return Result;
 185           }
 186           if (TokenLength == Code.size() || !isAlphanumeric(Code[TokenLength]))
 187             break;
 188           ++TokenLength;
 189         }
 190         if (TokenLength == 4 && Code.startswith("true")) {
 191           Result.Kind = TokenInfo::TK_Literal;
 192           Result.Value = true;
 193         } else if (TokenLength == 5 && Code.startswith("false")) {
 194           Result.Kind = TokenInfo::TK_Literal;
 195           Result.Value = false;
 196         } else {
 197           Result.Kind = TokenInfo::TK_Ident;
 198           Result.Text = Code.substr(0, TokenLength);
 199         }
 200         Code = Code.drop_front(TokenLength);
 201       } else {
 202         Result.Kind = TokenInfo::TK_InvalidChar;
 203         Result.Text = Code.substr(0, 1);
 204         Code = Code.drop_front(1);
 205       }
 206       break;
 207     }
 208
 209     Result.Range.End = currentLocation();
 210     return Result;
 211   }
 212
 213   /// Consume an unsigned and float literal.
 214   void consumeNumberLiteral(TokenInfo *Result) {
 215     bool isFloatingLiteral = false;
 216     unsigned Length = 1;
 217     if (Code.size() > 1) {
 218       // Consume the 'x' or 'b' radix modifier, if present.
 219       switch (toLowercase(Code[1])) {
 220       case 'x': case 'b': Length = 2;
 221       }
 222     }
 223     while (Length < Code.size() && isHexDigit(Code[Length]))
 224       ++Length;
 225
 226     // Try to recognize a floating point literal.
 227     while (Length < Code.size()) {
 228       char c = Code[Length];
 229       if (c == '-' || c == '+' || c == '.' || isHexDigit(c)) {
 230         isFloatingLiteral = true;
 231         Length++;
 232       } else {
 233         break;
 234       }
 235     }
 236
 237     Result->Text = Code.substr(0, Length);
 238     Code = Code.drop_front(Length);
 239
 240     if (isFloatingLiteral) {
 241       char *end;
 242       errno = 0;
 243       std::string Text = Result->Text.str();
 244       double doubleValue = strtod(Text.c_str(), &end);
 245       if (*end == 0 && errno == 0) {
 246         Result->Kind = TokenInfo::TK_Literal;
 247         Result->Value = doubleValue;
 248         return;
 249       }
 250     } else {
 251       unsigned Value;
 252       if (!Result->Text.getAsInteger(0, Value)) {
 253         Result->Kind = TokenInfo::TK_Literal;
 254         Result->Value = Value;
 255         return;
 256       }
 257     }
 258
 259     SourceRange Range;
 260     Range.Start = Result->Range.Start;
 261     Range.End = currentLocation();
 262     Error->addError(Range, Error->ET_ParserNumberError) << Result->Text;
 263     Result->Kind = TokenInfo::TK_Error;
 264   }
 265
 266   /// Consume a string literal.
 267   ///
 268   /// \c Code must be positioned at the start of the literal (the opening
 269   /// quote). Consumed until it finds the same closing quote character.
 270   void consumeStringLiteral(TokenInfo *Result) {
 271     bool InEscape = false;
 272     const char Marker = Code[0];
 273     for (size_t Length = 1, Size = Code.size(); Length != Size; ++Length) {
 274       if (InEscape) {
 275         InEscape = false;
 276         continue;
 277       }
 278       if (Code[Length] == '\\') {
 279         InEscape = true;
 280         continue;
 281       }
 282       if (Code[Length] == Marker) {
 283         Result->Kind = TokenInfo::TK_Literal;
 284         Result->Text = Code.substr(0, Length + 1);
 285         Result->Value = Code.substr(1, Length - 1);
 286         Code = Code.drop_front(Length + 1);
 287         return;
 288       }
 289     }
 290
 291     StringRef ErrorText = Code;
 292     Code = Code.drop_front(Code.size());
 293     SourceRange Range;
 294     Range.Start = Result->Range.Start;
 295     Range.End = currentLocation();
 296     Error->addError(Range, Error->ET_ParserStringError) << ErrorText;
 297     Result->Kind = TokenInfo::TK_Error;
 298   }
 299
 300   /// Consume all leading whitespace from \c Code.
 301   void consumeWhitespace() {
 302     Code = Code.drop_while([](char c) {
 303       // Don't trim newlines.
 304       return StringRef(" \t\v\f\r").contains(c);
 305     });
 306   }
 307
 308   SourceLocation currentLocation() {
 309     SourceLocation Location;
 310     Location.Line = Line;
 311     Location.Column = Code.data() - StartOfLine.data() + 1;
 312     return Location;
 313   }
 314
 315   StringRef &Code;
 316   StringRef StartOfLine;
 317   unsigned Line = 1;
 318   Diagnostics *Error;
 319   TokenInfo NextToken;
 320   const char *CodeCompletionLocation = nullptr;
 321 };
 322
 323 Parser::Sema::~Sema() = default;
 324
 325 std::vector<ArgKind> Parser::Sema::getAcceptedCompletionTypes(
 326     llvm::ArrayRef<std::pair<MatcherCtor, unsigned>> Context) {
 327   return {};
 328 }
 329
 330 std::vector<MatcherCompletion>
 331 Parser::Sema::getMatcherCompletions(llvm::ArrayRef<ArgKind> AcceptedTypes) {
 332   return {};
 333 }
 334
 335 struct Parser::ScopedContextEntry {
 336   Parser *P;
 337
 338   ScopedContextEntry(Parser *P, MatcherCtor C) : P(P) {
 339     P->ContextStack.push_back(std::make_pair(C, 0u));
 340   }
 341
 342   ~ScopedContextEntry() {
 343     P->ContextStack.pop_back();
 344   }
 345
 346   void nextArg() {
 347     ++P->ContextStack.back().second;
 348   }
 349 };
 350
 351 /// Parse expressions that start with an identifier.
 352 ///
 353 /// This function can parse named values and matchers.
 354 /// In case of failure it will try to determine the user's intent to give
 355 /// an appropriate error message.
 356 bool Parser::parseIdentifierPrefixImpl(VariantValue *Value) {
 357   const TokenInfo NameToken = Tokenizer->consumeNextToken();
 358
 359   if (Tokenizer->nextTokenKind() != TokenInfo::TK_OpenParen) {
 360     // Parse as a named value.
 361     if (const VariantValue NamedValue =
 362             NamedValues ? NamedValues->lookup(NameToken.Text)
 363                         : VariantValue()) {
 364
 365       if (Tokenizer->nextTokenKind() != TokenInfo::TK_Period) {
 366         *Value = NamedValue;
 367         return true;
 368       }
 369
 370       std::string BindID;
 371       Tokenizer->consumeNextToken();
 372       TokenInfo ChainCallToken = Tokenizer->consumeNextToken();
 373       if (ChainCallToken.Kind == TokenInfo::TK_CodeCompletion) {
 374         addCompletion(ChainCallToken, MatcherCompletion("bind(\"", "bind", 1));
 375         return false;
 376       }
 377
 378       if (ChainCallToken.Kind != TokenInfo::TK_Ident ||
 379           (ChainCallToken.Text != TokenInfo::ID_Bind &&
 380            ChainCallToken.Text != TokenInfo::ID_With)) {
 381         Error->addError(ChainCallToken.Range,
 382                         Error->ET_ParserMalformedChainedExpr);
 383         return false;
 384       }
 385       if (ChainCallToken.Text == TokenInfo::ID_With) {
 386
 387         Diagnostics::Context Ctx(Diagnostics::Context::ConstructMatcher, Error,
 388                                  NameToken.Text, NameToken.Range);
 389
 390         Error->addError(ChainCallToken.Range,
 391                         Error->ET_RegistryMatcherNoWithSupport);
 392         return false;
 393       }
 394       if (!parseBindID(BindID))
 395         return false;
 396
 397       assert(NamedValue.isMatcher());
 398       std::optional<DynTypedMatcher> Result =
 399           NamedValue.getMatcher().getSingleMatcher();
 400       if (Result) {
 401         std::optional<DynTypedMatcher> Bound = Result->tryBind(BindID);
 402         if (Bound) {
 403           *Value = VariantMatcher::SingleMatcher(*Bound);
 404           return true;
 405         }
 406       }
 407       return false;
 408     }
 409
 410     if (Tokenizer->nextTokenKind() == TokenInfo::TK_NewLine) {
 411       Error->addError(Tokenizer->peekNextToken().Range,
 412                       Error->ET_ParserNoOpenParen)
 413           << "NewLine";
 414       return false;
 415     }
 416
 417     // If the syntax is correct and the name is not a matcher either, report
 418     // unknown named value.
 419     if ((Tokenizer->nextTokenKind() == TokenInfo::TK_Comma ||
 420          Tokenizer->nextTokenKind() == TokenInfo::TK_CloseParen ||
 421          Tokenizer->nextTokenKind() == TokenInfo::TK_NewLine ||
 422          Tokenizer->nextTokenKind() == TokenInfo::TK_Eof) &&
 423         !S->lookupMatcherCtor(NameToken.Text)) {
 424       Error->addError(NameToken.Range, Error->ET_RegistryValueNotFound)
 425           << NameToken.Text;
 426       return false;
 427     }
 428     // Otherwise, fallback to the matcher parser.
 429   }
 430
 431   Tokenizer->SkipNewlines();
 432
 433   assert(NameToken.Kind == TokenInfo::TK_Ident);
 434   TokenInfo OpenToken = Tokenizer->consumeNextToken();
 435   if (OpenToken.Kind != TokenInfo::TK_OpenParen) {
 436     Error->addError(OpenToken.Range, Error->ET_ParserNoOpenParen)
 437         << OpenToken.Text;
 438     return false;
 439   }
 440
 441   std::optional<MatcherCtor> Ctor = S->lookupMatcherCtor(NameToken.Text);
 442
 443   // Parse as a matcher expression.
 444   return parseMatcherExpressionImpl(NameToken, OpenToken, Ctor, Value);
 445 }
 446
 447 bool Parser::parseBindID(std::string &BindID) {
 448   // Parse the parenthesized argument to .bind("foo")
 449   const TokenInfo OpenToken = Tokenizer->consumeNextToken();
 450   const TokenInfo IDToken = Tokenizer->consumeNextTokenIgnoreNewlines();
 451   const TokenInfo CloseToken = Tokenizer->consumeNextTokenIgnoreNewlines();
 452
 453   // TODO: We could use different error codes for each/some to be more
 454   //       explicit about the syntax error.
 455   if (OpenToken.Kind != TokenInfo::TK_OpenParen) {
 456     Error->addError(OpenToken.Range, Error->ET_ParserMalformedBindExpr);
 457     return false;
 458   }
 459   if (IDToken.Kind != TokenInfo::TK_Literal || !IDToken.Value.isString()) {
 460     Error->addError(IDToken.Range, Error->ET_ParserMalformedBindExpr);
 461     return false;
 462   }
 463   if (CloseToken.Kind != TokenInfo::TK_CloseParen) {
 464     Error->addError(CloseToken.Range, Error->ET_ParserMalformedBindExpr);
 465     return false;
 466   }
 467   BindID = IDToken.Value.getString();
 468   return true;
 469 }
 470
 471 bool Parser::parseMatcherBuilder(MatcherCtor Ctor, const TokenInfo &NameToken,
 472                                  const TokenInfo &OpenToken,
 473                                  VariantValue *Value) {
 474   std::vector<ParserValue> Args;
 475   TokenInfo EndToken;
 476
 477   Tokenizer->SkipNewlines();
 478
 479   {
 480     ScopedContextEntry SCE(this, Ctor);
 481
 482     while (Tokenizer->nextTokenKind() != TokenInfo::TK_Eof) {
 483       if (Tokenizer->nextTokenKind() == TokenInfo::TK_CloseParen) {
 484         // End of args.
 485         EndToken = Tokenizer->consumeNextToken();
 486         break;
 487       }
 488       if (!Args.empty()) {
 489         // We must find a , token to continue.
 490         TokenInfo CommaToken = Tokenizer->consumeNextToken();
 491         if (CommaToken.Kind != TokenInfo::TK_Comma) {
 492           Error->addError(CommaToken.Range, Error->ET_ParserNoComma)
 493               << CommaToken.Text;
 494           return false;
 495         }
 496       }
 497
 498       Diagnostics::Context Ctx(Diagnostics::Context::MatcherArg, Error,
 499                                NameToken.Text, NameToken.Range,
 500                                Args.size() + 1);
 501       ParserValue ArgValue;
 502       Tokenizer->SkipNewlines();
 503
 504       if (Tokenizer->peekNextToken().Kind == TokenInfo::TK_CodeCompletion) {
 505         addExpressionCompletions();
 506         return false;
 507       }
 508
 509       TokenInfo NodeMatcherToken = Tokenizer->consumeNextToken();
 510
 511       if (NodeMatcherToken.Kind != TokenInfo::TK_Ident) {
 512         Error->addError(NameToken.Range, Error->ET_ParserFailedToBuildMatcher)
 513             << NameToken.Text;
 514         return false;
 515       }
 516
 517       ArgValue.Text = NodeMatcherToken.Text;
 518       ArgValue.Range = NodeMatcherToken.Range;
 519
 520       std::optional<MatcherCtor> MappedMatcher =
 521           S->lookupMatcherCtor(ArgValue.Text);
 522
 523       if (!MappedMatcher) {
 524         Error->addError(NodeMatcherToken.Range,
 525                         Error->ET_RegistryMatcherNotFound)
 526             << NodeMatcherToken.Text;
 527         return false;
 528       }
 529
 530       ASTNodeKind NK = S->nodeMatcherType(*MappedMatcher);
 531
 532       if (NK.isNone()) {
 533         Error->addError(NodeMatcherToken.Range,
 534                         Error->ET_RegistryNonNodeMatcher)
 535             << NodeMatcherToken.Text;
 536         return false;
 537       }
 538
 539       ArgValue.Value = NK;
 540
 541       Tokenizer->SkipNewlines();
 542       Args.push_back(ArgValue);
 543
 544       SCE.nextArg();
 545     }
 546   }
 547
 548   if (EndToken.Kind == TokenInfo::TK_Eof) {
 549     Error->addError(OpenToken.Range, Error->ET_ParserNoCloseParen);
 550     return false;
 551   }
 552
 553   internal::MatcherDescriptorPtr BuiltCtor =
 554       S->buildMatcherCtor(Ctor, NameToken.Range, Args, Error);
 555
 556   if (!BuiltCtor.get()) {
 557     Error->addError(NameToken.Range, Error->ET_ParserFailedToBuildMatcher)
 558         << NameToken.Text;
 559     return false;
 560   }
 561
 562   std::string BindID;
 563   if (Tokenizer->peekNextToken().Kind == TokenInfo::TK_Period) {
 564     Tokenizer->consumeNextToken();
 565     TokenInfo ChainCallToken = Tokenizer->consumeNextToken();
 566     if (ChainCallToken.Kind == TokenInfo::TK_CodeCompletion) {
 567       addCompletion(ChainCallToken, MatcherCompletion("bind(\"", "bind", 1));
 568       addCompletion(ChainCallToken, MatcherCompletion("with(", "with", 1));
 569       return false;
 570     }
 571     if (ChainCallToken.Kind != TokenInfo::TK_Ident ||
 572         (ChainCallToken.Text != TokenInfo::ID_Bind &&
 573          ChainCallToken.Text != TokenInfo::ID_With)) {
 574       Error->addError(ChainCallToken.Range,
 575                       Error->ET_ParserMalformedChainedExpr);
 576       return false;
 577     }
 578     if (ChainCallToken.Text == TokenInfo::ID_Bind) {
 579       if (!parseBindID(BindID))
 580         return false;
 581       Diagnostics::Context Ctx(Diagnostics::Context::ConstructMatcher, Error,
 582                                NameToken.Text, NameToken.Range);
 583       SourceRange MatcherRange = NameToken.Range;
 584       MatcherRange.End = ChainCallToken.Range.End;
 585       VariantMatcher Result = S->actOnMatcherExpression(
 586           BuiltCtor.get(), MatcherRange, BindID, {}, Error);
 587       if (Result.isNull())
 588         return false;
 589
 590       *Value = Result;
 591       return true;
 592     } else if (ChainCallToken.Text == TokenInfo::ID_With) {
 593       Tokenizer->SkipNewlines();
 594
 595       if (Tokenizer->nextTokenKind() != TokenInfo::TK_OpenParen) {
 596         StringRef ErrTxt = Tokenizer->nextTokenKind() == TokenInfo::TK_Eof
 597                                ? StringRef("EOF")
 598                                : Tokenizer->peekNextToken().Text;
 599         Error->addError(Tokenizer->peekNextToken().Range,
 600                         Error->ET_ParserNoOpenParen)
 601             << ErrTxt;
 602         return false;
 603       }
 604
 605       TokenInfo WithOpenToken = Tokenizer->consumeNextToken();
 606
 607       return parseMatcherExpressionImpl(NameToken, WithOpenToken,
 608                                         BuiltCtor.get(), Value);
 609     }
 610   }
 611
 612   Diagnostics::Context Ctx(Diagnostics::Context::ConstructMatcher, Error,
 613                            NameToken.Text, NameToken.Range);
 614   SourceRange MatcherRange = NameToken.Range;
 615   MatcherRange.End = EndToken.Range.End;
 616   VariantMatcher Result = S->actOnMatcherExpression(
 617       BuiltCtor.get(), MatcherRange, BindID, {}, Error);
 618   if (Result.isNull())
 619     return false;
 620
 621   *Value = Result;
 622   return true;
 623 }
 624
 625 /// Parse and validate a matcher expression.
 626 /// \return \c true on success, in which case \c Value has the matcher parsed.
 627 ///   If the input is malformed, or some argument has an error, it
 628 ///   returns \c false.
 629 bool Parser::parseMatcherExpressionImpl(const TokenInfo &NameToken,
 630                                         const TokenInfo &OpenToken,
 631                                         std::optional<MatcherCtor> Ctor,
 632                                         VariantValue *Value) {
 633   if (!Ctor) {
 634     Error->addError(NameToken.Range, Error->ET_RegistryMatcherNotFound)
 635         << NameToken.Text;
 636     // Do not return here. We need to continue to give completion suggestions.
 637   }
 638
 639   if (Ctor && *Ctor && S->isBuilderMatcher(*Ctor))
 640     return parseMatcherBuilder(*Ctor, NameToken, OpenToken, Value);
 641
 642   std::vector<ParserValue> Args;
 643   TokenInfo EndToken;
 644
 645   Tokenizer->SkipNewlines();
 646
 647   {
 648     ScopedContextEntry SCE(this, Ctor.value_or(nullptr));
 649
 650     while (Tokenizer->nextTokenKind() != TokenInfo::TK_Eof) {
 651       if (Tokenizer->nextTokenKind() == TokenInfo::TK_CloseParen) {
 652         // End of args.
 653         EndToken = Tokenizer->consumeNextToken();
 654         break;
 655       }
 656       if (!Args.empty()) {
 657         // We must find a , token to continue.
 658         const TokenInfo CommaToken = Tokenizer->consumeNextToken();
 659         if (CommaToken.Kind != TokenInfo::TK_Comma) {
 660           Error->addError(CommaToken.Range, Error->ET_ParserNoComma)
 661               << CommaToken.Text;
 662           return false;
 663         }
 664       }
 665
 666       Diagnostics::Context Ctx(Diagnostics::Context::MatcherArg, Error,
 667                                NameToken.Text, NameToken.Range,
 668                                Args.size() + 1);
 669       ParserValue ArgValue;
 670       Tokenizer->SkipNewlines();
 671       ArgValue.Text = Tokenizer->peekNextToken().Text;
 672       ArgValue.Range = Tokenizer->peekNextToken().Range;
 673       if (!parseExpressionImpl(&ArgValue.Value)) {
 674         return false;
 675       }
 676
 677       Tokenizer->SkipNewlines();
 678       Args.push_back(ArgValue);
 679       SCE.nextArg();
 680     }
 681   }
 682
 683   if (EndToken.Kind == TokenInfo::TK_Eof) {
 684     Error->addError(OpenToken.Range, Error->ET_ParserNoCloseParen);
 685     return false;
 686   }
 687
 688   std::string BindID;
 689   if (Tokenizer->peekNextToken().Kind == TokenInfo::TK_Period) {
 690     Tokenizer->consumeNextToken();
 691     TokenInfo ChainCallToken = Tokenizer->consumeNextToken();
 692     if (ChainCallToken.Kind == TokenInfo::TK_CodeCompletion) {
 693       addCompletion(ChainCallToken, MatcherCompletion("bind(\"", "bind", 1));
 694       return false;
 695     }
 696
 697     if (ChainCallToken.Kind != TokenInfo::TK_Ident) {
 698       Error->addError(ChainCallToken.Range,
 699                       Error->ET_ParserMalformedChainedExpr);
 700       return false;
 701     }
 702     if (ChainCallToken.Text == TokenInfo::ID_With) {
 703
 704       Diagnostics::Context Ctx(Diagnostics::Context::ConstructMatcher, Error,
 705                                NameToken.Text, NameToken.Range);
 706
 707       Error->addError(ChainCallToken.Range,
 708                       Error->ET_RegistryMatcherNoWithSupport);
 709       return false;
 710     }
 711     if (ChainCallToken.Text != TokenInfo::ID_Bind) {
 712       Error->addError(ChainCallToken.Range,
 713                       Error->ET_ParserMalformedChainedExpr);
 714       return false;
 715     }
 716     if (!parseBindID(BindID))
 717       return false;
 718   }
 719
 720   if (!Ctor)
 721     return false;
 722
 723   // Merge the start and end infos.
 724   Diagnostics::Context Ctx(Diagnostics::Context::ConstructMatcher, Error,
 725                            NameToken.Text, NameToken.Range);
 726   SourceRange MatcherRange = NameToken.Range;
 727   MatcherRange.End = EndToken.Range.End;
 728   VariantMatcher Result = S->actOnMatcherExpression(
 729       *Ctor, MatcherRange, BindID, Args, Error);
 730   if (Result.isNull()) return false;
 731
 732   *Value = Result;
 733   return true;
 734 }
 735
 736 // If the prefix of this completion matches the completion token, add it to
 737 // Completions minus the prefix.
 738 void Parser::addCompletion(const TokenInfo &CompToken,
 739                            const MatcherCompletion& Completion) {
 740   if (StringRef(Completion.TypedText).startswith(CompToken.Text) &&
 741       Completion.Specificity > 0) {
 742     Completions.emplace_back(Completion.TypedText.substr(CompToken.Text.size()),
 743                              Completion.MatcherDecl, Completion.Specificity);
 744   }
 745 }
 746
 747 std::vector<MatcherCompletion> Parser::getNamedValueCompletions(
 748     ArrayRef<ArgKind> AcceptedTypes) {
 749   if (!NamedValues) return std::vector<MatcherCompletion>();
 750   std::vector<MatcherCompletion> Result;
 751   for (const auto &Entry : *NamedValues) {
 752     unsigned Specificity;
 753     if (Entry.getValue().isConvertibleTo(AcceptedTypes, &Specificity)) {
 754       std::string Decl =
 755           (Entry.getValue().getTypeAsString() + " " + Entry.getKey()).str();
 756       Result.emplace_back(Entry.getKey(), Decl, Specificity);
 757     }
 758   }
 759   return Result;
 760 }
 761
 762 void Parser::addExpressionCompletions() {
 763   const TokenInfo CompToken = Tokenizer->consumeNextTokenIgnoreNewlines();
 764   assert(CompToken.Kind == TokenInfo::TK_CodeCompletion);
 765
 766   // We cannot complete code if there is an invalid element on the context
 767   // stack.
 768   for (ContextStackTy::iterator I = ContextStack.begin(),
 769                                 E = ContextStack.end();
 770        I != E; ++I) {
 771     if (!I->first)
 772       return;
 773   }
 774
 775   auto AcceptedTypes = S->getAcceptedCompletionTypes(ContextStack);
 776   for (const auto &Completion : S->getMatcherCompletions(AcceptedTypes)) {
 777     addCompletion(CompToken, Completion);
 778   }
 779
 780   for (const auto &Completion : getNamedValueCompletions(AcceptedTypes)) {
 781     addCompletion(CompToken, Completion);
 782   }
 783 }
 784
 785 /// Parse an <Expression>
 786 bool Parser::parseExpressionImpl(VariantValue *Value) {
 787   switch (Tokenizer->nextTokenKind()) {
 788   case TokenInfo::TK_Literal:
 789     *Value = Tokenizer->consumeNextToken().Value;
 790     return true;
 791
 792   case TokenInfo::TK_Ident:
 793     return parseIdentifierPrefixImpl(Value);
 794
 795   case TokenInfo::TK_CodeCompletion:
 796     addExpressionCompletions();
 797     return false;
 798
 799   case TokenInfo::TK_Eof:
 800     Error->addError(Tokenizer->consumeNextToken().Range,
 801                     Error->ET_ParserNoCode);
 802     return false;
 803
 804   case TokenInfo::TK_Error:
 805     // This error was already reported by the tokenizer.
 806     return false;
 807   case TokenInfo::TK_NewLine:
 808   case TokenInfo::TK_OpenParen:
 809   case TokenInfo::TK_CloseParen:
 810   case TokenInfo::TK_Comma:
 811   case TokenInfo::TK_Period:
 812   case TokenInfo::TK_InvalidChar:
 813     const TokenInfo Token = Tokenizer->consumeNextToken();
 814     Error->addError(Token.Range, Error->ET_ParserInvalidToken)
 815         << (Token.Kind == TokenInfo::TK_NewLine ? "NewLine" : Token.Text);
 816     return false;
 817   }
 818
 819   llvm_unreachable("Unknown token kind.");
 820 }
 821
 822 static llvm::ManagedStatic<Parser::RegistrySema> DefaultRegistrySema;
 823
 824 Parser::Parser(CodeTokenizer *Tokenizer, Sema *S,
 825                const NamedValueMap *NamedValues, Diagnostics *Error)
 826     : Tokenizer(Tokenizer), S(S ? S : &*DefaultRegistrySema),
 827       NamedValues(NamedValues), Error(Error) {}
 828
 829 Parser::RegistrySema::~RegistrySema() = default;
 830
 831 std::optional<MatcherCtor>
 832 Parser::RegistrySema::lookupMatcherCtor(StringRef MatcherName) {
 833   return Registry::lookupMatcherCtor(MatcherName);
 834 }
 835
 836 VariantMatcher Parser::RegistrySema::actOnMatcherExpression(
 837     MatcherCtor Ctor, SourceRange NameRange, StringRef BindID,
 838     ArrayRef<ParserValue> Args, Diagnostics *Error) {
 839   if (BindID.empty()) {
 840     return Registry::constructMatcher(Ctor, NameRange, Args, Error);
 841   } else {
 842     return Registry::constructBoundMatcher(Ctor, NameRange, BindID, Args,
 843                                            Error);
 844   }
 845 }
 846
 847 std::vector<ArgKind> Parser::RegistrySema::getAcceptedCompletionTypes(
 848     ArrayRef<std::pair<MatcherCtor, unsigned>> Context) {
 849   return Registry::getAcceptedCompletionTypes(Context);
 850 }
 851
 852 std::vector<MatcherCompletion> Parser::RegistrySema::getMatcherCompletions(
 853     ArrayRef<ArgKind> AcceptedTypes) {
 854   return Registry::getMatcherCompletions(AcceptedTypes);
 855 }
 856
 857 bool Parser::RegistrySema::isBuilderMatcher(MatcherCtor Ctor) const {
 858   return Registry::isBuilderMatcher(Ctor);
 859 }
 860
 861 ASTNodeKind Parser::RegistrySema::nodeMatcherType(MatcherCtor Ctor) const {
 862   return Registry::nodeMatcherType(Ctor);
 863 }
 864
 865 internal::MatcherDescriptorPtr
 866 Parser::RegistrySema::buildMatcherCtor(MatcherCtor Ctor, SourceRange NameRange,
 867                                        ArrayRef<ParserValue> Args,
 868                                        Diagnostics *Error) const {
 869   return Registry::buildMatcherCtor(Ctor, NameRange, Args, Error);
 870 }
 871
 872 bool Parser::parseExpression(StringRef &Code, Sema *S,
 873                              const NamedValueMap *NamedValues,
 874                              VariantValue *Value, Diagnostics *Error) {
 875   CodeTokenizer Tokenizer(Code, Error);
 876   if (!Parser(&Tokenizer, S, NamedValues, Error).parseExpressionImpl(Value))
 877     return false;
 878   auto NT = Tokenizer.peekNextToken();
 879   if (NT.Kind != TokenInfo::TK_Eof && NT.Kind != TokenInfo::TK_NewLine) {
 880     Error->addError(Tokenizer.peekNextToken().Range,
 881                     Error->ET_ParserTrailingCode);
 882     return false;
 883   }
 884   return true;
 885 }
 886
 887 std::vector<MatcherCompletion>
 888 Parser::completeExpression(StringRef &Code, unsigned CompletionOffset, Sema *S,
 889                            const NamedValueMap *NamedValues) {
 890   Diagnostics Error;
 891   CodeTokenizer Tokenizer(Code, &Error, CompletionOffset);
 892   Parser P(&Tokenizer, S, NamedValues, &Error);
 893   VariantValue Dummy;
 894   P.parseExpressionImpl(&Dummy);
 895
 896   // Sort by specificity, then by name.
 897   llvm::sort(P.Completions,
 898              [](const MatcherCompletion &A, const MatcherCompletion &B) {
 899                if (A.Specificity != B.Specificity)
 900                  return A.Specificity > B.Specificity;
 901                return A.TypedText < B.TypedText;
 902              });
 903
 904   return P.Completions;
 905 }
 906
 907 std::optional<DynTypedMatcher>
 908 Parser::parseMatcherExpression(StringRef &Code, Sema *S,
 909                                const NamedValueMap *NamedValues,
 910                                Diagnostics *Error) {
 911   VariantValue Value;
 912   if (!parseExpression(Code, S, NamedValues, &Value, Error))
 913     return std::nullopt;
 914   if (!Value.isMatcher()) {
 915     Error->addError(SourceRange(), Error->ET_ParserNotAMatcher);
 916     return std::nullopt;
 917   }
 918   std::optional<DynTypedMatcher> Result = Value.getMatcher().getSingleMatcher();
 919   if (!Result) {
 920     Error->addError(SourceRange(), Error->ET_ParserOverloadedType)
 921         << Value.getTypeAsString();
 922   }
 923   return Result;
 924 }
 925
 926 } // namespace dynamic
 927 } // namespace ast_matchers
 928 } // namespace clang