1744 lines · cpp
1//===- BuildTree.cpp ------------------------------------------*- C++ -*-=====//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-exception6//7//===----------------------------------------------------------------------===//8#include "clang/Tooling/Syntax/BuildTree.h"9#include "clang/AST/ASTFwd.h"10#include "clang/AST/Decl.h"11#include "clang/AST/DeclBase.h"12#include "clang/AST/DeclCXX.h"13#include "clang/AST/DeclarationName.h"14#include "clang/AST/Expr.h"15#include "clang/AST/ExprCXX.h"16#include "clang/AST/IgnoreExpr.h"17#include "clang/AST/OperationKinds.h"18#include "clang/AST/RecursiveASTVisitor.h"19#include "clang/AST/Stmt.h"20#include "clang/AST/TypeLoc.h"21#include "clang/AST/TypeLocVisitor.h"22#include "clang/Basic/LLVM.h"23#include "clang/Basic/SourceLocation.h"24#include "clang/Basic/SourceManager.h"25#include "clang/Basic/TokenKinds.h"26#include "clang/Lex/Lexer.h"27#include "clang/Lex/LiteralSupport.h"28#include "clang/Tooling/Syntax/Nodes.h"29#include "clang/Tooling/Syntax/TokenBufferTokenManager.h"30#include "clang/Tooling/Syntax/Tokens.h"31#include "clang/Tooling/Syntax/Tree.h"32#include "llvm/ADT/ArrayRef.h"33#include "llvm/ADT/DenseMap.h"34#include "llvm/ADT/PointerUnion.h"35#include "llvm/ADT/STLExtras.h"36#include "llvm/ADT/SmallVector.h"37#include "llvm/Support/Allocator.h"38#include "llvm/Support/Compiler.h"39#include "llvm/Support/FormatVariadic.h"40#include <map>41 42using namespace clang;43 44// Ignores the implicit `CXXConstructExpr` for copy/move constructor calls45// generated by the compiler, as well as in implicit conversions like the one46// wrapping `1` in `X x = 1;`.47static Expr *IgnoreImplicitConstructorSingleStep(Expr *E) {48 if (auto *C = dyn_cast<CXXConstructExpr>(E)) {49 auto NumArgs = C->getNumArgs();50 if (NumArgs == 1 || (NumArgs > 1 && isa<CXXDefaultArgExpr>(C->getArg(1)))) {51 Expr *A = C->getArg(0);52 if (C->getParenOrBraceRange().isInvalid())53 return A;54 }55 }56 return E;57}58 59// In:60// struct X {61// X(int)62// };63// X x = X(1);64// Ignores the implicit `CXXFunctionalCastExpr` that wraps65// `CXXConstructExpr X(1)`.66static Expr *IgnoreCXXFunctionalCastExprWrappingConstructor(Expr *E) {67 if (auto *F = dyn_cast<CXXFunctionalCastExpr>(E)) {68 if (F->getCastKind() == CK_ConstructorConversion)69 return F->getSubExpr();70 }71 return E;72}73 74static Expr *IgnoreImplicit(Expr *E) {75 return IgnoreExprNodes(E, IgnoreImplicitSingleStep,76 IgnoreImplicitConstructorSingleStep,77 IgnoreCXXFunctionalCastExprWrappingConstructor);78}79 80[[maybe_unused]]81static bool isImplicitExpr(Expr *E) {82 return IgnoreImplicit(E) != E;83}84 85namespace {86/// Get start location of the Declarator from the TypeLoc.87/// E.g.:88/// loc of `(` in `int (a)`89/// loc of `*` in `int *(a)`90/// loc of the first `(` in `int (*a)(int)`91/// loc of the `*` in `int *(a)(int)`92/// loc of the first `*` in `const int *const *volatile a;`93///94/// It is non-trivial to get the start location because TypeLocs are stored95/// inside out. In the example above `*volatile` is the TypeLoc returned96/// by `Decl.getTypeSourceInfo()`, and `*const` is what `.getPointeeLoc()`97/// returns.98struct GetStartLoc : TypeLocVisitor<GetStartLoc, SourceLocation> {99 SourceLocation VisitParenTypeLoc(ParenTypeLoc T) {100 auto L = Visit(T.getInnerLoc());101 if (L.isValid())102 return L;103 return T.getLParenLoc();104 }105 106 // Types spelled in the prefix part of the declarator.107 SourceLocation VisitPointerTypeLoc(PointerTypeLoc T) {108 return HandlePointer(T);109 }110 111 SourceLocation VisitMemberPointerTypeLoc(MemberPointerTypeLoc T) {112 return HandlePointer(T);113 }114 115 SourceLocation VisitBlockPointerTypeLoc(BlockPointerTypeLoc T) {116 return HandlePointer(T);117 }118 119 SourceLocation VisitReferenceTypeLoc(ReferenceTypeLoc T) {120 return HandlePointer(T);121 }122 123 SourceLocation VisitObjCObjectPointerTypeLoc(ObjCObjectPointerTypeLoc T) {124 return HandlePointer(T);125 }126 127 // All other cases are not important, as they are either part of declaration128 // specifiers (e.g. inheritors of TypeSpecTypeLoc) or introduce modifiers on129 // existing declarators (e.g. QualifiedTypeLoc). They cannot start the130 // declarator themselves, but their underlying type can.131 SourceLocation VisitTypeLoc(TypeLoc T) {132 auto N = T.getNextTypeLoc();133 if (!N)134 return SourceLocation();135 return Visit(N);136 }137 138 SourceLocation VisitFunctionProtoTypeLoc(FunctionProtoTypeLoc T) {139 if (T.getTypePtr()->hasTrailingReturn())140 return SourceLocation(); // avoid recursing into the suffix of declarator.141 return VisitTypeLoc(T);142 }143 144private:145 template <class PtrLoc> SourceLocation HandlePointer(PtrLoc T) {146 auto L = Visit(T.getPointeeLoc());147 if (L.isValid())148 return L;149 return T.getLocalSourceRange().getBegin();150 }151};152} // namespace153 154static CallExpr::arg_range dropDefaultArgs(CallExpr::arg_range Args) {155 auto FirstDefaultArg =156 llvm::find_if(Args, [](auto It) { return isa<CXXDefaultArgExpr>(It); });157 return llvm::make_range(Args.begin(), FirstDefaultArg);158}159 160static syntax::NodeKind getOperatorNodeKind(const CXXOperatorCallExpr &E) {161 switch (E.getOperator()) {162 // Comparison163 case OO_EqualEqual:164 case OO_ExclaimEqual:165 case OO_Greater:166 case OO_GreaterEqual:167 case OO_Less:168 case OO_LessEqual:169 case OO_Spaceship:170 // Assignment171 case OO_Equal:172 case OO_SlashEqual:173 case OO_PercentEqual:174 case OO_CaretEqual:175 case OO_PipeEqual:176 case OO_LessLessEqual:177 case OO_GreaterGreaterEqual:178 case OO_PlusEqual:179 case OO_MinusEqual:180 case OO_StarEqual:181 case OO_AmpEqual:182 // Binary computation183 case OO_Slash:184 case OO_Percent:185 case OO_Caret:186 case OO_Pipe:187 case OO_LessLess:188 case OO_GreaterGreater:189 case OO_AmpAmp:190 case OO_PipePipe:191 case OO_ArrowStar:192 case OO_Comma:193 return syntax::NodeKind::BinaryOperatorExpression;194 case OO_Tilde:195 case OO_Exclaim:196 return syntax::NodeKind::PrefixUnaryOperatorExpression;197 // Prefix/Postfix increment/decrement198 case OO_PlusPlus:199 case OO_MinusMinus:200 switch (E.getNumArgs()) {201 case 1:202 return syntax::NodeKind::PrefixUnaryOperatorExpression;203 case 2:204 return syntax::NodeKind::PostfixUnaryOperatorExpression;205 default:206 llvm_unreachable("Invalid number of arguments for operator");207 }208 // Operators that can be unary or binary209 case OO_Plus:210 case OO_Minus:211 case OO_Star:212 case OO_Amp:213 switch (E.getNumArgs()) {214 case 1:215 return syntax::NodeKind::PrefixUnaryOperatorExpression;216 case 2:217 return syntax::NodeKind::BinaryOperatorExpression;218 default:219 llvm_unreachable("Invalid number of arguments for operator");220 }221 return syntax::NodeKind::BinaryOperatorExpression;222 // Not yet supported by SyntaxTree223 case OO_New:224 case OO_Delete:225 case OO_Array_New:226 case OO_Array_Delete:227 case OO_Coawait:228 case OO_Subscript:229 case OO_Arrow:230 return syntax::NodeKind::UnknownExpression;231 case OO_Call:232 return syntax::NodeKind::CallExpression;233 case OO_Conditional: // not overloadable234 case NUM_OVERLOADED_OPERATORS:235 case OO_None:236 llvm_unreachable("Not an overloadable operator");237 }238 llvm_unreachable("Unknown OverloadedOperatorKind enum");239}240 241/// Get the start of the qualified name. In the examples below it gives the242/// location of the `^`:243/// `int ^a;`244/// `int *^a;`245/// `int ^a::S::f(){}`246static SourceLocation getQualifiedNameStart(NamedDecl *D) {247 assert((isa<DeclaratorDecl, TypedefNameDecl>(D)) &&248 "only DeclaratorDecl and TypedefNameDecl are supported.");249 250 auto DN = D->getDeclName();251 bool IsAnonymous = DN.isIdentifier() && !DN.getAsIdentifierInfo();252 if (IsAnonymous)253 return SourceLocation();254 255 if (const auto *DD = dyn_cast<DeclaratorDecl>(D)) {256 if (DD->getQualifierLoc()) {257 return DD->getQualifierLoc().getBeginLoc();258 }259 }260 261 return D->getLocation();262}263 264/// Gets the range of the initializer inside an init-declarator C++ [dcl.decl].265/// `int a;` -> range of ``,266/// `int *a = nullptr` -> range of `= nullptr`.267/// `int a{}` -> range of `{}`.268/// `int a()` -> range of `()`.269static SourceRange getInitializerRange(Decl *D) {270 if (auto *V = dyn_cast<VarDecl>(D)) {271 auto *I = V->getInit();272 // Initializers in range-based-for are not part of the declarator273 if (I && !V->isCXXForRangeDecl())274 return I->getSourceRange();275 }276 277 return SourceRange();278}279 280/// Gets the range of declarator as defined by the C++ grammar. E.g.281/// `int a;` -> range of `a`,282/// `int *a;` -> range of `*a`,283/// `int a[10];` -> range of `a[10]`,284/// `int a[1][2][3];` -> range of `a[1][2][3]`,285/// `int *a = nullptr` -> range of `*a = nullptr`.286/// `int S::f(){}` -> range of `S::f()`.287/// FIXME: \p Name must be a source range.288static SourceRange getDeclaratorRange(const SourceManager &SM, TypeLoc T,289 SourceLocation Name,290 SourceRange Initializer) {291 SourceLocation Start = GetStartLoc().Visit(T);292 SourceLocation End = T.getEndLoc();293 if (Name.isValid()) {294 if (Start.isInvalid())295 Start = Name;296 // End of TypeLoc could be invalid if the type is invalid, fallback to the297 // NameLoc.298 if (End.isInvalid() || SM.isBeforeInTranslationUnit(End, Name))299 End = Name;300 }301 if (Initializer.isValid()) {302 auto InitializerEnd = Initializer.getEnd();303 assert(SM.isBeforeInTranslationUnit(End, InitializerEnd) ||304 End == InitializerEnd);305 End = InitializerEnd;306 }307 return SourceRange(Start, End);308}309 310namespace {311/// All AST hierarchy roots that can be represented as pointers.312using ASTPtr = llvm::PointerUnion<Stmt *, Decl *>;313/// Maintains a mapping from AST to syntax tree nodes. This class will get more314/// complicated as we support more kinds of AST nodes, e.g. TypeLocs.315/// FIXME: expose this as public API.316class ASTToSyntaxMapping {317public:318 void add(ASTPtr From, syntax::Tree *To) {319 assert(To != nullptr);320 assert(!From.isNull());321 322 bool Added = Nodes.insert({From, To}).second;323 (void)Added;324 assert(Added && "mapping added twice");325 }326 327 void add(NestedNameSpecifierLoc From, syntax::Tree *To) {328 assert(To != nullptr);329 assert(From.hasQualifier());330 331 bool Added = NNSNodes.insert({From, To}).second;332 (void)Added;333 assert(Added && "mapping added twice");334 }335 336 syntax::Tree *find(ASTPtr P) const { return Nodes.lookup(P); }337 338 syntax::Tree *find(NestedNameSpecifierLoc P) const {339 return NNSNodes.lookup(P);340 }341 342private:343 llvm::DenseMap<ASTPtr, syntax::Tree *> Nodes;344 llvm::DenseMap<NestedNameSpecifierLoc, syntax::Tree *> NNSNodes;345};346} // namespace347 348/// A helper class for constructing the syntax tree while traversing a clang349/// AST.350///351/// At each point of the traversal we maintain a list of pending nodes.352/// Initially all tokens are added as pending nodes. When processing a clang AST353/// node, the clients need to:354/// - create a corresponding syntax node,355/// - assign roles to all pending child nodes with 'markChild' and356/// 'markChildToken',357/// - replace the child nodes with the new syntax node in the pending list358/// with 'foldNode'.359///360/// Note that all children are expected to be processed when building a node.361///362/// Call finalize() to finish building the tree and consume the root node.363class syntax::TreeBuilder {364public:365 TreeBuilder(syntax::Arena &Arena, TokenBufferTokenManager& TBTM)366 : Arena(Arena),367 TBTM(TBTM),368 Pending(Arena, TBTM.tokenBuffer()) {369 for (const auto &T : TBTM.tokenBuffer().expandedTokens())370 LocationToToken.insert({T.location(), &T});371 }372 373 llvm::BumpPtrAllocator &allocator() { return Arena.getAllocator(); }374 const SourceManager &sourceManager() const {375 return TBTM.sourceManager();376 }377 378 /// Populate children for \p New node, assuming it covers tokens from \p379 /// Range.380 void foldNode(ArrayRef<syntax::Token> Range, syntax::Tree *New, ASTPtr From) {381 assert(New);382 Pending.foldChildren(TBTM.tokenBuffer(), Range, New);383 if (From)384 Mapping.add(From, New);385 }386 387 void foldNode(ArrayRef<syntax::Token> Range, syntax::Tree *New, TypeLoc L) {388 // FIXME: add mapping for TypeLocs389 foldNode(Range, New, nullptr);390 }391 392 void foldNode(llvm::ArrayRef<syntax::Token> Range, syntax::Tree *New,393 NestedNameSpecifierLoc From) {394 assert(New);395 Pending.foldChildren(TBTM.tokenBuffer(), Range, New);396 if (From)397 Mapping.add(From, New);398 }399 400 /// Populate children for \p New list, assuming it covers tokens from a401 /// subrange of \p SuperRange.402 void foldList(ArrayRef<syntax::Token> SuperRange, syntax::List *New,403 ASTPtr From) {404 assert(New);405 auto ListRange = Pending.shrinkToFitList(SuperRange);406 Pending.foldChildren(TBTM.tokenBuffer(), ListRange, New);407 if (From)408 Mapping.add(From, New);409 }410 411 /// Notifies that we should not consume trailing semicolon when computing412 /// token range of \p D.413 void noticeDeclWithoutSemicolon(Decl *D);414 415 /// Mark the \p Child node with a corresponding \p Role. All marked children416 /// should be consumed by foldNode.417 /// When called on expressions (clang::Expr is derived from clang::Stmt),418 /// wraps expressions into expression statement.419 void markStmtChild(Stmt *Child, NodeRole Role);420 /// Should be called for expressions in non-statement position to avoid421 /// wrapping into expression statement.422 void markExprChild(Expr *Child, NodeRole Role);423 /// Set role for a token starting at \p Loc.424 void markChildToken(SourceLocation Loc, NodeRole R);425 /// Set role for \p T.426 void markChildToken(const syntax::Token *T, NodeRole R);427 428 /// Set role for \p N.429 void markChild(syntax::Node *N, NodeRole R);430 /// Set role for the syntax node matching \p N.431 void markChild(ASTPtr N, NodeRole R);432 /// Set role for the syntax node matching \p N.433 void markChild(NestedNameSpecifierLoc N, NodeRole R);434 435 /// Finish building the tree and consume the root node.436 syntax::TranslationUnit *finalize() && {437 auto Tokens = TBTM.tokenBuffer().expandedTokens();438 assert(!Tokens.empty());439 assert(Tokens.back().kind() == tok::eof);440 441 // Build the root of the tree, consuming all the children.442 Pending.foldChildren(TBTM.tokenBuffer(), Tokens.drop_back(),443 new (Arena.getAllocator()) syntax::TranslationUnit);444 445 auto *TU = cast<syntax::TranslationUnit>(std::move(Pending).finalize());446 TU->assertInvariantsRecursive();447 return TU;448 }449 450 /// Finds a token starting at \p L. The token must exist if \p L is valid.451 const syntax::Token *findToken(SourceLocation L) const;452 453 /// Finds the syntax tokens corresponding to the \p SourceRange.454 ArrayRef<syntax::Token> getRange(SourceRange Range) const {455 assert(Range.isValid());456 return getRange(Range.getBegin(), Range.getEnd());457 }458 459 /// Finds the syntax tokens corresponding to the passed source locations.460 /// \p First is the start position of the first token and \p Last is the start461 /// position of the last token.462 ArrayRef<syntax::Token> getRange(SourceLocation First,463 SourceLocation Last) const {464 assert(First.isValid());465 assert(Last.isValid());466 assert(First == Last ||467 TBTM.sourceManager().isBeforeInTranslationUnit(First, Last));468 return llvm::ArrayRef(findToken(First), std::next(findToken(Last)));469 }470 471 ArrayRef<syntax::Token>472 getTemplateRange(const ClassTemplateSpecializationDecl *D) const {473 auto Tokens = getRange(D->getSourceRange());474 return maybeAppendSemicolon(Tokens, D);475 }476 477 /// Returns true if \p D is the last declarator in a chain and is thus478 /// reponsible for creating SimpleDeclaration for the whole chain.479 bool isResponsibleForCreatingDeclaration(const Decl *D) const {480 assert((isa<DeclaratorDecl, TypedefNameDecl>(D)) &&481 "only DeclaratorDecl and TypedefNameDecl are supported.");482 483 const Decl *Next = D->getNextDeclInContext();484 485 // There's no next sibling, this one is responsible.486 if (Next == nullptr) {487 return true;488 }489 490 // Next sibling is not the same type, this one is responsible.491 if (D->getKind() != Next->getKind()) {492 return true;493 }494 // Next sibling doesn't begin at the same loc, it must be a different495 // declaration, so this declarator is responsible.496 if (Next->getBeginLoc() != D->getBeginLoc()) {497 return true;498 }499 500 // NextT is a member of the same declaration, and we need the last member to501 // create declaration. This one is not responsible.502 return false;503 }504 505 ArrayRef<syntax::Token> getDeclarationRange(Decl *D) {506 ArrayRef<syntax::Token> Tokens;507 // We want to drop the template parameters for specializations.508 if (const auto *S = dyn_cast<TagDecl>(D))509 Tokens = getRange(S->TypeDecl::getBeginLoc(), S->getEndLoc());510 else511 Tokens = getRange(D->getSourceRange());512 return maybeAppendSemicolon(Tokens, D);513 }514 515 ArrayRef<syntax::Token> getExprRange(const Expr *E) const {516 return getRange(E->getSourceRange());517 }518 519 /// Find the adjusted range for the statement, consuming the trailing520 /// semicolon when needed.521 ArrayRef<syntax::Token> getStmtRange(const Stmt *S) const {522 auto Tokens = getRange(S->getSourceRange());523 if (isa<CompoundStmt>(S))524 return Tokens;525 526 // Some statements miss a trailing semicolon, e.g. 'return', 'continue' and527 // all statements that end with those. Consume this semicolon here.528 if (Tokens.back().kind() == tok::semi)529 return Tokens;530 return withTrailingSemicolon(Tokens);531 }532 533private:534 ArrayRef<syntax::Token> maybeAppendSemicolon(ArrayRef<syntax::Token> Tokens,535 const Decl *D) const {536 if (isa<NamespaceDecl>(D))537 return Tokens;538 if (DeclsWithoutSemicolons.count(D))539 return Tokens;540 // FIXME: do not consume trailing semicolon on function definitions.541 // Most declarations own a semicolon in syntax trees, but not in clang AST.542 return withTrailingSemicolon(Tokens);543 }544 545 ArrayRef<syntax::Token>546 withTrailingSemicolon(ArrayRef<syntax::Token> Tokens) const {547 assert(!Tokens.empty());548 assert(Tokens.back().kind() != tok::eof);549 // We never consume 'eof', so looking at the next token is ok.550 if (Tokens.back().kind() != tok::semi && Tokens.end()->kind() == tok::semi)551 return llvm::ArrayRef(Tokens.begin(), Tokens.end() + 1);552 return Tokens;553 }554 555 void setRole(syntax::Node *N, NodeRole R) {556 assert(N->getRole() == NodeRole::Detached);557 N->setRole(R);558 }559 560 /// A collection of trees covering the input tokens.561 /// When created, each tree corresponds to a single token in the file.562 /// Clients call 'foldChildren' to attach one or more subtrees to a parent563 /// node and update the list of trees accordingly.564 ///565 /// Ensures that added nodes properly nest and cover the whole token stream.566 struct Forest {567 Forest(syntax::Arena &A, const syntax::TokenBuffer &TB) {568 assert(!TB.expandedTokens().empty());569 assert(TB.expandedTokens().back().kind() == tok::eof);570 // Create all leaf nodes.571 // Note that we do not have 'eof' in the tree.572 for (const auto &T : TB.expandedTokens().drop_back()) {573 auto *L = new (A.getAllocator())574 syntax::Leaf(reinterpret_cast<TokenManager::Key>(&T));575 L->Original = true;576 L->CanModify = TB.spelledForExpanded(T).has_value();577 Trees.insert(Trees.end(), {&T, L});578 }579 }580 581 void assignRole(ArrayRef<syntax::Token> Range, syntax::NodeRole Role) {582 assert(!Range.empty());583 auto It = Trees.lower_bound(Range.begin());584 assert(It != Trees.end() && "no node found");585 assert(It->first == Range.begin() && "no child with the specified range");586 assert((std::next(It) == Trees.end() ||587 std::next(It)->first == Range.end()) &&588 "no child with the specified range");589 assert(It->second->getRole() == NodeRole::Detached &&590 "re-assigning role for a child");591 It->second->setRole(Role);592 }593 594 /// Shrink \p Range to a subrange that only contains tokens of a list.595 /// List elements and delimiters should already have correct roles.596 ArrayRef<syntax::Token> shrinkToFitList(ArrayRef<syntax::Token> Range) {597 auto BeginChildren = Trees.lower_bound(Range.begin());598 assert((BeginChildren == Trees.end() ||599 BeginChildren->first == Range.begin()) &&600 "Range crosses boundaries of existing subtrees");601 602 auto EndChildren = Trees.lower_bound(Range.end());603 assert(604 (EndChildren == Trees.end() || EndChildren->first == Range.end()) &&605 "Range crosses boundaries of existing subtrees");606 607 auto BelongsToList = [](decltype(Trees)::value_type KV) {608 auto Role = KV.second->getRole();609 return Role == syntax::NodeRole::ListElement ||610 Role == syntax::NodeRole::ListDelimiter;611 };612 613 auto BeginListChildren =614 std::find_if(BeginChildren, EndChildren, BelongsToList);615 616 auto EndListChildren =617 std::find_if_not(BeginListChildren, EndChildren, BelongsToList);618 619 return ArrayRef<syntax::Token>(BeginListChildren->first,620 EndListChildren->first);621 }622 623 /// Add \p Node to the forest and attach child nodes based on \p Tokens.624 void foldChildren(const syntax::TokenBuffer &TB,625 ArrayRef<syntax::Token> Tokens, syntax::Tree *Node) {626 // Attach children to `Node`.627 assert(Node->getFirstChild() == nullptr && "node already has children");628 629 auto *FirstToken = Tokens.begin();630 auto BeginChildren = Trees.lower_bound(FirstToken);631 632 assert((BeginChildren == Trees.end() ||633 BeginChildren->first == FirstToken) &&634 "fold crosses boundaries of existing subtrees");635 auto EndChildren = Trees.lower_bound(Tokens.end());636 assert(637 (EndChildren == Trees.end() || EndChildren->first == Tokens.end()) &&638 "fold crosses boundaries of existing subtrees");639 640 for (auto It = BeginChildren; It != EndChildren; ++It) {641 auto *C = It->second;642 if (C->getRole() == NodeRole::Detached)643 C->setRole(NodeRole::Unknown);644 Node->appendChildLowLevel(C);645 }646 647 // Mark that this node came from the AST and is backed by the source code.648 Node->Original = true;649 Node->CanModify =650 TB.spelledForExpanded(Tokens).has_value();651 652 Trees.erase(BeginChildren, EndChildren);653 Trees.insert({FirstToken, Node});654 }655 656 // EXPECTS: all tokens were consumed and are owned by a single root node.657 syntax::Node *finalize() && {658 assert(Trees.size() == 1);659 auto *Root = Trees.begin()->second;660 Trees = {};661 return Root;662 }663 664 std::string str(const syntax::TokenBufferTokenManager &STM) const {665 std::string R;666 for (auto It = Trees.begin(); It != Trees.end(); ++It) {667 unsigned CoveredTokens =668 It != Trees.end()669 ? (std::next(It)->first - It->first)670 : STM.tokenBuffer().expandedTokens().end() - It->first;671 672 R += std::string(673 formatv("- '{0}' covers '{1}'+{2} tokens\n", It->second->getKind(),674 It->first->text(STM.sourceManager()), CoveredTokens));675 R += It->second->dump(STM);676 }677 return R;678 }679 680 private:681 /// Maps from the start token to a subtree starting at that token.682 /// Keys in the map are pointers into the array of expanded tokens, so683 /// pointer order corresponds to the order of preprocessor tokens.684 std::map<const syntax::Token *, syntax::Node *> Trees;685 };686 687 /// For debugging purposes.688 std::string str() { return Pending.str(TBTM); }689 690 syntax::Arena &Arena;691 TokenBufferTokenManager& TBTM;692 /// To quickly find tokens by their start location.693 llvm::DenseMap<SourceLocation, const syntax::Token *> LocationToToken;694 Forest Pending;695 llvm::DenseSet<Decl *> DeclsWithoutSemicolons;696 ASTToSyntaxMapping Mapping;697};698 699namespace {700class BuildTreeVisitor : public RecursiveASTVisitor<BuildTreeVisitor> {701public:702 explicit BuildTreeVisitor(ASTContext &Context, syntax::TreeBuilder &Builder)703 : Builder(Builder), Context(Context) {}704 705 bool shouldTraversePostOrder() const { return true; }706 707 bool WalkUpFromDeclaratorDecl(DeclaratorDecl *DD) {708 return processDeclaratorAndDeclaration(DD);709 }710 711 bool WalkUpFromTypedefNameDecl(TypedefNameDecl *TD) {712 return processDeclaratorAndDeclaration(TD);713 }714 715 bool VisitDecl(Decl *D) {716 assert(!D->isImplicit());717 Builder.foldNode(Builder.getDeclarationRange(D),718 new (allocator()) syntax::UnknownDeclaration(), D);719 return true;720 }721 722 // RAV does not call WalkUpFrom* on explicit instantiations, so we have to723 // override Traverse.724 // FIXME: make RAV call WalkUpFrom* instead.725 bool726 TraverseClassTemplateSpecializationDecl(ClassTemplateSpecializationDecl *C) {727 if (!RecursiveASTVisitor::TraverseClassTemplateSpecializationDecl(C))728 return false;729 if (C->isExplicitSpecialization())730 return true; // we are only interested in explicit instantiations.731 auto *Declaration =732 cast<syntax::SimpleDeclaration>(handleFreeStandingTagDecl(C));733 foldExplicitTemplateInstantiation(734 Builder.getTemplateRange(C),735 Builder.findToken(C->getExternKeywordLoc()),736 Builder.findToken(C->getTemplateKeywordLoc()), Declaration, C);737 return true;738 }739 740 bool WalkUpFromTemplateDecl(TemplateDecl *S) {741 foldTemplateDeclaration(742 Builder.getDeclarationRange(S),743 Builder.findToken(S->getTemplateParameters()->getTemplateLoc()),744 Builder.getDeclarationRange(S->getTemplatedDecl()), S);745 return true;746 }747 748 bool WalkUpFromTagDecl(TagDecl *C) {749 // FIXME: build the ClassSpecifier node.750 if (!C->isFreeStanding()) {751 assert(C->getNumTemplateParameterLists() == 0);752 return true;753 }754 handleFreeStandingTagDecl(C);755 return true;756 }757 758 syntax::Declaration *handleFreeStandingTagDecl(TagDecl *C) {759 assert(C->isFreeStanding());760 // Class is a declaration specifier and needs a spanning declaration node.761 auto DeclarationRange = Builder.getDeclarationRange(C);762 syntax::Declaration *Result = new (allocator()) syntax::SimpleDeclaration;763 Builder.foldNode(DeclarationRange, Result, nullptr);764 765 // Build TemplateDeclaration nodes if we had template parameters.766 auto ConsumeTemplateParameters = [&](const TemplateParameterList &L) {767 const auto *TemplateKW = Builder.findToken(L.getTemplateLoc());768 auto R = llvm::ArrayRef(TemplateKW, DeclarationRange.end());769 Result =770 foldTemplateDeclaration(R, TemplateKW, DeclarationRange, nullptr);771 DeclarationRange = R;772 };773 if (auto *S = dyn_cast<ClassTemplatePartialSpecializationDecl>(C))774 ConsumeTemplateParameters(*S->getTemplateParameters());775 for (unsigned I = C->getNumTemplateParameterLists(); 0 < I; --I)776 ConsumeTemplateParameters(*C->getTemplateParameterList(I - 1));777 return Result;778 }779 780 bool WalkUpFromTranslationUnitDecl(TranslationUnitDecl *TU) {781 // We do not want to call VisitDecl(), the declaration for translation782 // unit is built by finalize().783 return true;784 }785 786 bool WalkUpFromCompoundStmt(CompoundStmt *S) {787 using NodeRole = syntax::NodeRole;788 789 Builder.markChildToken(S->getLBracLoc(), NodeRole::OpenParen);790 for (auto *Child : S->body())791 Builder.markStmtChild(Child, NodeRole::Statement);792 Builder.markChildToken(S->getRBracLoc(), NodeRole::CloseParen);793 794 Builder.foldNode(Builder.getStmtRange(S),795 new (allocator()) syntax::CompoundStatement, S);796 return true;797 }798 799 // Some statements are not yet handled by syntax trees.800 bool WalkUpFromStmt(Stmt *S) {801 Builder.foldNode(Builder.getStmtRange(S),802 new (allocator()) syntax::UnknownStatement, S);803 return true;804 }805 806 bool TraverseIfStmt(IfStmt *S) {807 bool Result = [&, this]() {808 if (S->getInit() && !TraverseStmt(S->getInit())) {809 return false;810 }811 // In cases where the condition is an initialized declaration in a812 // statement, we want to preserve the declaration and ignore the813 // implicit condition expression in the syntax tree.814 if (S->hasVarStorage()) {815 if (!TraverseStmt(S->getConditionVariableDeclStmt()))816 return false;817 } else if (S->getCond() && !TraverseStmt(S->getCond()))818 return false;819 820 if (S->getThen() && !TraverseStmt(S->getThen()))821 return false;822 if (S->getElse() && !TraverseStmt(S->getElse()))823 return false;824 return true;825 }();826 WalkUpFromIfStmt(S);827 return Result;828 }829 830 bool TraverseCXXForRangeStmt(CXXForRangeStmt *S) {831 // We override to traverse range initializer as VarDecl.832 // RAV traverses it as a statement, we produce invalid node kinds in that833 // case.834 // FIXME: should do this in RAV instead?835 bool Result = [&, this]() {836 if (S->getInit() && !TraverseStmt(S->getInit()))837 return false;838 if (S->getLoopVariable() && !TraverseDecl(S->getLoopVariable()))839 return false;840 if (S->getRangeInit() && !TraverseStmt(S->getRangeInit()))841 return false;842 if (S->getBody() && !TraverseStmt(S->getBody()))843 return false;844 return true;845 }();846 WalkUpFromCXXForRangeStmt(S);847 return Result;848 }849 850 bool TraverseStmt(Stmt *S) {851 if (auto *DS = dyn_cast_or_null<DeclStmt>(S)) {852 // We want to consume the semicolon, make sure SimpleDeclaration does not.853 for (auto *D : DS->decls())854 Builder.noticeDeclWithoutSemicolon(D);855 } else if (auto *E = dyn_cast_or_null<Expr>(S)) {856 return RecursiveASTVisitor::TraverseStmt(IgnoreImplicit(E));857 }858 return RecursiveASTVisitor::TraverseStmt(S);859 }860 861 bool TraverseOpaqueValueExpr(OpaqueValueExpr *VE) {862 // OpaqueValue doesn't correspond to concrete syntax, ignore it.863 return true;864 }865 866 // Some expressions are not yet handled by syntax trees.867 bool WalkUpFromExpr(Expr *E) {868 assert(!isImplicitExpr(E) && "should be handled by TraverseStmt");869 Builder.foldNode(Builder.getExprRange(E),870 new (allocator()) syntax::UnknownExpression, E);871 return true;872 }873 874 bool TraverseUserDefinedLiteral(UserDefinedLiteral *S) {875 // The semantic AST node `UserDefinedLiteral` (UDL) may have one child node876 // referencing the location of the UDL suffix (`_w` in `1.2_w`). The877 // UDL suffix location does not point to the beginning of a token, so we878 // can't represent the UDL suffix as a separate syntax tree node.879 880 return WalkUpFromUserDefinedLiteral(S);881 }882 883 syntax::UserDefinedLiteralExpression *884 buildUserDefinedLiteral(UserDefinedLiteral *S) {885 switch (S->getLiteralOperatorKind()) {886 case UserDefinedLiteral::LOK_Integer:887 return new (allocator()) syntax::IntegerUserDefinedLiteralExpression;888 case UserDefinedLiteral::LOK_Floating:889 return new (allocator()) syntax::FloatUserDefinedLiteralExpression;890 case UserDefinedLiteral::LOK_Character:891 return new (allocator()) syntax::CharUserDefinedLiteralExpression;892 case UserDefinedLiteral::LOK_String:893 return new (allocator()) syntax::StringUserDefinedLiteralExpression;894 case UserDefinedLiteral::LOK_Raw:895 case UserDefinedLiteral::LOK_Template:896 // For raw literal operator and numeric literal operator template we897 // cannot get the type of the operand in the semantic AST. We get this898 // information from the token. As integer and floating point have the same899 // token kind, we run `NumericLiteralParser` again to distinguish them.900 auto TokLoc = S->getBeginLoc();901 auto TokSpelling =902 Builder.findToken(TokLoc)->text(Context.getSourceManager());903 auto Literal =904 NumericLiteralParser(TokSpelling, TokLoc, Context.getSourceManager(),905 Context.getLangOpts(), Context.getTargetInfo(),906 Context.getDiagnostics());907 if (Literal.isIntegerLiteral())908 return new (allocator()) syntax::IntegerUserDefinedLiteralExpression;909 else {910 assert(Literal.isFloatingLiteral());911 return new (allocator()) syntax::FloatUserDefinedLiteralExpression;912 }913 }914 llvm_unreachable("Unknown literal operator kind.");915 }916 917 bool WalkUpFromUserDefinedLiteral(UserDefinedLiteral *S) {918 Builder.markChildToken(S->getBeginLoc(), syntax::NodeRole::LiteralToken);919 Builder.foldNode(Builder.getExprRange(S), buildUserDefinedLiteral(S), S);920 return true;921 }922 923 syntax::NameSpecifier *buildIdentifier(SourceRange SR,924 bool DropBack = false) {925 auto NameSpecifierTokens = Builder.getRange(SR).drop_back(DropBack);926 assert(NameSpecifierTokens.size() == 1);927 Builder.markChildToken(NameSpecifierTokens.begin(),928 syntax::NodeRole::Unknown);929 auto *NS = new (allocator()) syntax::IdentifierNameSpecifier;930 Builder.foldNode(NameSpecifierTokens, NS, nullptr);931 return NS;932 }933 934 syntax::NameSpecifier *buildSimpleTemplateName(SourceRange SR) {935 auto NameSpecifierTokens = Builder.getRange(SR);936 // TODO: Build `SimpleTemplateNameSpecifier` children and implement937 // accessors to them.938 // Be aware, we cannot do that simply by calling `TraverseTypeLoc`,939 // some `TypeLoc`s have inside them the previous name specifier and940 // we want to treat them independently.941 auto *NS = new (allocator()) syntax::SimpleTemplateNameSpecifier;942 Builder.foldNode(NameSpecifierTokens, NS, nullptr);943 return NS;944 }945 946 syntax::NameSpecifier *947 buildNameSpecifier(const NestedNameSpecifierLoc &NNSLoc) {948 assert(NNSLoc.hasQualifier());949 switch (NNSLoc.getNestedNameSpecifier().getKind()) {950 case NestedNameSpecifier::Kind::Global:951 return new (allocator()) syntax::GlobalNameSpecifier;952 953 case NestedNameSpecifier::Kind::Namespace:954 return buildIdentifier(NNSLoc.getLocalSourceRange(), /*DropBack=*/true);955 956 case NestedNameSpecifier::Kind::Type: {957 TypeLoc TL = NNSLoc.castAsTypeLoc();958 switch (TL.getTypeLocClass()) {959 case TypeLoc::Record:960 case TypeLoc::InjectedClassName:961 case TypeLoc::Enum:962 return buildIdentifier(TL.castAs<TagTypeLoc>().getNameLoc());963 case TypeLoc::Typedef:964 return buildIdentifier(TL.castAs<TypedefTypeLoc>().getNameLoc());965 case TypeLoc::UnresolvedUsing:966 return buildIdentifier(967 TL.castAs<UnresolvedUsingTypeLoc>().getNameLoc());968 case TypeLoc::Using:969 return buildIdentifier(TL.castAs<UsingTypeLoc>().getNameLoc());970 case TypeLoc::DependentName:971 return buildIdentifier(TL.castAs<DependentNameTypeLoc>().getNameLoc());972 case TypeLoc::TemplateSpecialization: {973 auto TST = TL.castAs<TemplateSpecializationTypeLoc>();974 SourceLocation BeginLoc = TST.getTemplateKeywordLoc();975 if (BeginLoc.isInvalid())976 BeginLoc = TST.getTemplateNameLoc();977 return buildSimpleTemplateName({BeginLoc, TST.getEndLoc()});978 }979 case TypeLoc::Decltype: {980 const auto DTL = TL.castAs<DecltypeTypeLoc>();981 if (!RecursiveASTVisitor::TraverseDecltypeTypeLoc(982 DTL, /*TraverseQualifier=*/true))983 return nullptr;984 auto *NS = new (allocator()) syntax::DecltypeNameSpecifier;985 // TODO: Implement accessor to `DecltypeNameSpecifier` inner986 // `DecltypeTypeLoc`.987 // For that add mapping from `TypeLoc` to `syntax::Node*` then:988 // Builder.markChild(TypeLoc, syntax::NodeRole);989 Builder.foldNode(Builder.getRange(DTL.getLocalSourceRange()), NS,990 nullptr);991 return NS;992 }993 default:994 return buildIdentifier(TL.getLocalSourceRange());995 }996 }997 default:998 // FIXME: Support Microsoft's __super999 llvm::report_fatal_error("We don't yet support the __super specifier",1000 true);1001 }1002 }1003 1004 // To build syntax tree nodes for NestedNameSpecifierLoc we override1005 // Traverse instead of WalkUpFrom because we want to traverse the children1006 // ourselves and build a list instead of a nested tree of name specifier1007 // prefixes.1008 bool TraverseNestedNameSpecifierLoc(NestedNameSpecifierLoc QualifierLoc) {1009 if (!QualifierLoc)1010 return true;1011 for (auto It = QualifierLoc; It; /**/) {1012 auto *NS = buildNameSpecifier(It);1013 if (!NS)1014 return false;1015 Builder.markChild(NS, syntax::NodeRole::ListElement);1016 Builder.markChildToken(It.getEndLoc(), syntax::NodeRole::ListDelimiter);1017 if (TypeLoc TL = It.getAsTypeLoc())1018 It = TL.getPrefix();1019 else1020 It = It.getAsNamespaceAndPrefix().Prefix;1021 }1022 Builder.foldNode(Builder.getRange(QualifierLoc.getSourceRange()),1023 new (allocator()) syntax::NestedNameSpecifier,1024 QualifierLoc);1025 return true;1026 }1027 1028 syntax::IdExpression *buildIdExpression(NestedNameSpecifierLoc QualifierLoc,1029 SourceLocation TemplateKeywordLoc,1030 SourceRange UnqualifiedIdLoc,1031 ASTPtr From) {1032 if (QualifierLoc) {1033 Builder.markChild(QualifierLoc, syntax::NodeRole::Qualifier);1034 if (TemplateKeywordLoc.isValid())1035 Builder.markChildToken(TemplateKeywordLoc,1036 syntax::NodeRole::TemplateKeyword);1037 }1038 1039 auto *TheUnqualifiedId = new (allocator()) syntax::UnqualifiedId;1040 Builder.foldNode(Builder.getRange(UnqualifiedIdLoc), TheUnqualifiedId,1041 nullptr);1042 Builder.markChild(TheUnqualifiedId, syntax::NodeRole::UnqualifiedId);1043 1044 auto IdExpressionBeginLoc =1045 QualifierLoc ? QualifierLoc.getBeginLoc() : UnqualifiedIdLoc.getBegin();1046 1047 auto *TheIdExpression = new (allocator()) syntax::IdExpression;1048 Builder.foldNode(1049 Builder.getRange(IdExpressionBeginLoc, UnqualifiedIdLoc.getEnd()),1050 TheIdExpression, From);1051 1052 return TheIdExpression;1053 }1054 1055 bool WalkUpFromMemberExpr(MemberExpr *S) {1056 // For `MemberExpr` with implicit `this->` we generate a simple1057 // `id-expression` syntax node, beacuse an implicit `member-expression` is1058 // syntactically undistinguishable from an `id-expression`1059 if (S->isImplicitAccess()) {1060 buildIdExpression(S->getQualifierLoc(), S->getTemplateKeywordLoc(),1061 SourceRange(S->getMemberLoc(), S->getEndLoc()), S);1062 return true;1063 }1064 1065 auto *TheIdExpression = buildIdExpression(1066 S->getQualifierLoc(), S->getTemplateKeywordLoc(),1067 SourceRange(S->getMemberLoc(), S->getEndLoc()), nullptr);1068 1069 Builder.markChild(TheIdExpression, syntax::NodeRole::Member);1070 1071 Builder.markExprChild(S->getBase(), syntax::NodeRole::Object);1072 Builder.markChildToken(S->getOperatorLoc(), syntax::NodeRole::AccessToken);1073 1074 Builder.foldNode(Builder.getExprRange(S),1075 new (allocator()) syntax::MemberExpression, S);1076 return true;1077 }1078 1079 bool WalkUpFromDeclRefExpr(DeclRefExpr *S) {1080 buildIdExpression(S->getQualifierLoc(), S->getTemplateKeywordLoc(),1081 SourceRange(S->getLocation(), S->getEndLoc()), S);1082 1083 return true;1084 }1085 1086 // Same logic as DeclRefExpr.1087 bool WalkUpFromDependentScopeDeclRefExpr(DependentScopeDeclRefExpr *S) {1088 buildIdExpression(S->getQualifierLoc(), S->getTemplateKeywordLoc(),1089 SourceRange(S->getLocation(), S->getEndLoc()), S);1090 1091 return true;1092 }1093 1094 bool WalkUpFromCXXThisExpr(CXXThisExpr *S) {1095 if (!S->isImplicit()) {1096 Builder.markChildToken(S->getLocation(),1097 syntax::NodeRole::IntroducerKeyword);1098 Builder.foldNode(Builder.getExprRange(S),1099 new (allocator()) syntax::ThisExpression, S);1100 }1101 return true;1102 }1103 1104 bool WalkUpFromParenExpr(ParenExpr *S) {1105 Builder.markChildToken(S->getLParen(), syntax::NodeRole::OpenParen);1106 Builder.markExprChild(S->getSubExpr(), syntax::NodeRole::SubExpression);1107 Builder.markChildToken(S->getRParen(), syntax::NodeRole::CloseParen);1108 Builder.foldNode(Builder.getExprRange(S),1109 new (allocator()) syntax::ParenExpression, S);1110 return true;1111 }1112 1113 bool WalkUpFromIntegerLiteral(IntegerLiteral *S) {1114 Builder.markChildToken(S->getLocation(), syntax::NodeRole::LiteralToken);1115 Builder.foldNode(Builder.getExprRange(S),1116 new (allocator()) syntax::IntegerLiteralExpression, S);1117 return true;1118 }1119 1120 bool WalkUpFromCharacterLiteral(CharacterLiteral *S) {1121 Builder.markChildToken(S->getLocation(), syntax::NodeRole::LiteralToken);1122 Builder.foldNode(Builder.getExprRange(S),1123 new (allocator()) syntax::CharacterLiteralExpression, S);1124 return true;1125 }1126 1127 bool WalkUpFromFloatingLiteral(FloatingLiteral *S) {1128 Builder.markChildToken(S->getLocation(), syntax::NodeRole::LiteralToken);1129 Builder.foldNode(Builder.getExprRange(S),1130 new (allocator()) syntax::FloatingLiteralExpression, S);1131 return true;1132 }1133 1134 bool WalkUpFromStringLiteral(StringLiteral *S) {1135 Builder.markChildToken(S->getBeginLoc(), syntax::NodeRole::LiteralToken);1136 Builder.foldNode(Builder.getExprRange(S),1137 new (allocator()) syntax::StringLiteralExpression, S);1138 return true;1139 }1140 1141 bool WalkUpFromCXXBoolLiteralExpr(CXXBoolLiteralExpr *S) {1142 Builder.markChildToken(S->getLocation(), syntax::NodeRole::LiteralToken);1143 Builder.foldNode(Builder.getExprRange(S),1144 new (allocator()) syntax::BoolLiteralExpression, S);1145 return true;1146 }1147 1148 bool WalkUpFromCXXNullPtrLiteralExpr(CXXNullPtrLiteralExpr *S) {1149 Builder.markChildToken(S->getLocation(), syntax::NodeRole::LiteralToken);1150 Builder.foldNode(Builder.getExprRange(S),1151 new (allocator()) syntax::CxxNullPtrExpression, S);1152 return true;1153 }1154 1155 bool WalkUpFromUnaryOperator(UnaryOperator *S) {1156 Builder.markChildToken(S->getOperatorLoc(),1157 syntax::NodeRole::OperatorToken);1158 Builder.markExprChild(S->getSubExpr(), syntax::NodeRole::Operand);1159 1160 if (S->isPostfix())1161 Builder.foldNode(Builder.getExprRange(S),1162 new (allocator()) syntax::PostfixUnaryOperatorExpression,1163 S);1164 else1165 Builder.foldNode(Builder.getExprRange(S),1166 new (allocator()) syntax::PrefixUnaryOperatorExpression,1167 S);1168 1169 return true;1170 }1171 1172 bool WalkUpFromBinaryOperator(BinaryOperator *S) {1173 Builder.markExprChild(S->getLHS(), syntax::NodeRole::LeftHandSide);1174 Builder.markChildToken(S->getOperatorLoc(),1175 syntax::NodeRole::OperatorToken);1176 Builder.markExprChild(S->getRHS(), syntax::NodeRole::RightHandSide);1177 Builder.foldNode(Builder.getExprRange(S),1178 new (allocator()) syntax::BinaryOperatorExpression, S);1179 return true;1180 }1181 1182 /// Builds `CallArguments` syntax node from arguments that appear in source1183 /// code, i.e. not default arguments.1184 syntax::CallArguments *1185 buildCallArguments(CallExpr::arg_range ArgsAndDefaultArgs) {1186 auto Args = dropDefaultArgs(ArgsAndDefaultArgs);1187 for (auto *Arg : Args) {1188 Builder.markExprChild(Arg, syntax::NodeRole::ListElement);1189 const auto *DelimiterToken =1190 std::next(Builder.findToken(Arg->getEndLoc()));1191 if (DelimiterToken->kind() == clang::tok::TokenKind::comma)1192 Builder.markChildToken(DelimiterToken, syntax::NodeRole::ListDelimiter);1193 }1194 1195 auto *Arguments = new (allocator()) syntax::CallArguments;1196 if (!Args.empty())1197 Builder.foldNode(Builder.getRange((*Args.begin())->getBeginLoc(),1198 (*(Args.end() - 1))->getEndLoc()),1199 Arguments, nullptr);1200 1201 return Arguments;1202 }1203 1204 bool WalkUpFromCallExpr(CallExpr *S) {1205 Builder.markExprChild(S->getCallee(), syntax::NodeRole::Callee);1206 1207 const auto *LParenToken =1208 std::next(Builder.findToken(S->getCallee()->getEndLoc()));1209 // FIXME: Assert that `LParenToken` is indeed a `l_paren` once we have fixed1210 // the test on decltype desctructors.1211 if (LParenToken->kind() == clang::tok::l_paren)1212 Builder.markChildToken(LParenToken, syntax::NodeRole::OpenParen);1213 1214 Builder.markChild(buildCallArguments(S->arguments()),1215 syntax::NodeRole::Arguments);1216 1217 Builder.markChildToken(S->getRParenLoc(), syntax::NodeRole::CloseParen);1218 1219 Builder.foldNode(Builder.getRange(S->getSourceRange()),1220 new (allocator()) syntax::CallExpression, S);1221 return true;1222 }1223 1224 bool WalkUpFromCXXConstructExpr(CXXConstructExpr *S) {1225 // Ignore the implicit calls to default constructors.1226 if ((S->getNumArgs() == 0 || isa<CXXDefaultArgExpr>(S->getArg(0))) &&1227 S->getParenOrBraceRange().isInvalid())1228 return true;1229 return RecursiveASTVisitor::WalkUpFromCXXConstructExpr(S);1230 }1231 1232 bool TraverseCXXOperatorCallExpr(CXXOperatorCallExpr *S) {1233 // To construct a syntax tree of the same shape for calls to built-in and1234 // user-defined operators, ignore the `DeclRefExpr` that refers to the1235 // operator and treat it as a simple token. Do that by traversing1236 // arguments instead of children.1237 for (auto *child : S->arguments()) {1238 // A postfix unary operator is declared as taking two operands. The1239 // second operand is used to distinguish from its prefix counterpart. In1240 // the semantic AST this "phantom" operand is represented as a1241 // `IntegerLiteral` with invalid `SourceLocation`. We skip visiting this1242 // operand because it does not correspond to anything written in source1243 // code.1244 if (child->getSourceRange().isInvalid()) {1245 assert(getOperatorNodeKind(*S) ==1246 syntax::NodeKind::PostfixUnaryOperatorExpression);1247 continue;1248 }1249 if (!TraverseStmt(child))1250 return false;1251 }1252 return WalkUpFromCXXOperatorCallExpr(S);1253 }1254 1255 bool WalkUpFromCXXOperatorCallExpr(CXXOperatorCallExpr *S) {1256 switch (getOperatorNodeKind(*S)) {1257 case syntax::NodeKind::BinaryOperatorExpression:1258 Builder.markExprChild(S->getArg(0), syntax::NodeRole::LeftHandSide);1259 Builder.markChildToken(S->getOperatorLoc(),1260 syntax::NodeRole::OperatorToken);1261 Builder.markExprChild(S->getArg(1), syntax::NodeRole::RightHandSide);1262 Builder.foldNode(Builder.getExprRange(S),1263 new (allocator()) syntax::BinaryOperatorExpression, S);1264 return true;1265 case syntax::NodeKind::PrefixUnaryOperatorExpression:1266 Builder.markChildToken(S->getOperatorLoc(),1267 syntax::NodeRole::OperatorToken);1268 Builder.markExprChild(S->getArg(0), syntax::NodeRole::Operand);1269 Builder.foldNode(Builder.getExprRange(S),1270 new (allocator()) syntax::PrefixUnaryOperatorExpression,1271 S);1272 return true;1273 case syntax::NodeKind::PostfixUnaryOperatorExpression:1274 Builder.markChildToken(S->getOperatorLoc(),1275 syntax::NodeRole::OperatorToken);1276 Builder.markExprChild(S->getArg(0), syntax::NodeRole::Operand);1277 Builder.foldNode(Builder.getExprRange(S),1278 new (allocator()) syntax::PostfixUnaryOperatorExpression,1279 S);1280 return true;1281 case syntax::NodeKind::CallExpression: {1282 Builder.markExprChild(S->getArg(0), syntax::NodeRole::Callee);1283 1284 const auto *LParenToken =1285 std::next(Builder.findToken(S->getArg(0)->getEndLoc()));1286 // FIXME: Assert that `LParenToken` is indeed a `l_paren` once we have1287 // fixed the test on decltype desctructors.1288 if (LParenToken->kind() == clang::tok::l_paren)1289 Builder.markChildToken(LParenToken, syntax::NodeRole::OpenParen);1290 1291 Builder.markChild(buildCallArguments(CallExpr::arg_range(1292 S->arg_begin() + 1, S->arg_end())),1293 syntax::NodeRole::Arguments);1294 1295 Builder.markChildToken(S->getRParenLoc(), syntax::NodeRole::CloseParen);1296 1297 Builder.foldNode(Builder.getRange(S->getSourceRange()),1298 new (allocator()) syntax::CallExpression, S);1299 return true;1300 }1301 case syntax::NodeKind::UnknownExpression:1302 return WalkUpFromExpr(S);1303 default:1304 llvm_unreachable("getOperatorNodeKind() does not return this value");1305 }1306 }1307 1308 bool WalkUpFromCXXDefaultArgExpr(CXXDefaultArgExpr *S) { return true; }1309 1310 bool WalkUpFromNamespaceDecl(NamespaceDecl *S) {1311 auto Tokens = Builder.getDeclarationRange(S);1312 if (Tokens.front().kind() == tok::coloncolon) {1313 // Handle nested namespace definitions. Those start at '::' token, e.g.1314 // namespace a^::b {}1315 // FIXME: build corresponding nodes for the name of this namespace.1316 return true;1317 }1318 Builder.foldNode(Tokens, new (allocator()) syntax::NamespaceDefinition, S);1319 return true;1320 }1321 1322 // FIXME: Deleting the `TraverseParenTypeLoc` override doesn't change test1323 // results. Find test coverage or remove it.1324 bool TraverseParenTypeLoc(ParenTypeLoc L, bool TraverseQualifier) {1325 // We reverse order of traversal to get the proper syntax structure.1326 if (!WalkUpFromParenTypeLoc(L))1327 return false;1328 return TraverseTypeLoc(L.getInnerLoc());1329 }1330 1331 bool WalkUpFromParenTypeLoc(ParenTypeLoc L) {1332 Builder.markChildToken(L.getLParenLoc(), syntax::NodeRole::OpenParen);1333 Builder.markChildToken(L.getRParenLoc(), syntax::NodeRole::CloseParen);1334 Builder.foldNode(Builder.getRange(L.getLParenLoc(), L.getRParenLoc()),1335 new (allocator()) syntax::ParenDeclarator, L);1336 return true;1337 }1338 1339 // Declarator chunks, they are produced by type locs and some clang::Decls.1340 bool WalkUpFromArrayTypeLoc(ArrayTypeLoc L) {1341 Builder.markChildToken(L.getLBracketLoc(), syntax::NodeRole::OpenParen);1342 Builder.markExprChild(L.getSizeExpr(), syntax::NodeRole::Size);1343 Builder.markChildToken(L.getRBracketLoc(), syntax::NodeRole::CloseParen);1344 Builder.foldNode(Builder.getRange(L.getLBracketLoc(), L.getRBracketLoc()),1345 new (allocator()) syntax::ArraySubscript, L);1346 return true;1347 }1348 1349 syntax::ParameterDeclarationList *1350 buildParameterDeclarationList(ArrayRef<ParmVarDecl *> Params) {1351 for (auto *P : Params) {1352 Builder.markChild(P, syntax::NodeRole::ListElement);1353 const auto *DelimiterToken = std::next(Builder.findToken(P->getEndLoc()));1354 if (DelimiterToken->kind() == clang::tok::TokenKind::comma)1355 Builder.markChildToken(DelimiterToken, syntax::NodeRole::ListDelimiter);1356 }1357 auto *Parameters = new (allocator()) syntax::ParameterDeclarationList;1358 if (!Params.empty())1359 Builder.foldNode(Builder.getRange(Params.front()->getBeginLoc(),1360 Params.back()->getEndLoc()),1361 Parameters, nullptr);1362 return Parameters;1363 }1364 1365 bool WalkUpFromFunctionTypeLoc(FunctionTypeLoc L) {1366 Builder.markChildToken(L.getLParenLoc(), syntax::NodeRole::OpenParen);1367 1368 Builder.markChild(buildParameterDeclarationList(L.getParams()),1369 syntax::NodeRole::Parameters);1370 1371 Builder.markChildToken(L.getRParenLoc(), syntax::NodeRole::CloseParen);1372 Builder.foldNode(Builder.getRange(L.getLParenLoc(), L.getEndLoc()),1373 new (allocator()) syntax::ParametersAndQualifiers, L);1374 return true;1375 }1376 1377 bool WalkUpFromFunctionProtoTypeLoc(FunctionProtoTypeLoc L) {1378 if (!L.getTypePtr()->hasTrailingReturn())1379 return WalkUpFromFunctionTypeLoc(L);1380 1381 auto *TrailingReturnTokens = buildTrailingReturn(L);1382 // Finish building the node for parameters.1383 Builder.markChild(TrailingReturnTokens, syntax::NodeRole::TrailingReturn);1384 return WalkUpFromFunctionTypeLoc(L);1385 }1386 1387 bool TraverseMemberPointerTypeLoc(MemberPointerTypeLoc L,1388 bool TraverseQualifier) {1389 // In the source code "void (Y::*mp)()" `MemberPointerTypeLoc` corresponds1390 // to "Y::*" but it points to a `ParenTypeLoc` that corresponds to1391 // "(Y::*mp)" We thus reverse the order of traversal to get the proper1392 // syntax structure.1393 if (!WalkUpFromMemberPointerTypeLoc(L))1394 return false;1395 return TraverseTypeLoc(L.getPointeeLoc());1396 }1397 1398 bool WalkUpFromMemberPointerTypeLoc(MemberPointerTypeLoc L) {1399 auto SR = L.getLocalSourceRange();1400 Builder.foldNode(Builder.getRange(SR),1401 new (allocator()) syntax::MemberPointer, L);1402 return true;1403 }1404 1405 // The code below is very regular, it could even be generated with some1406 // preprocessor magic. We merely assign roles to the corresponding children1407 // and fold resulting nodes.1408 bool WalkUpFromDeclStmt(DeclStmt *S) {1409 Builder.foldNode(Builder.getStmtRange(S),1410 new (allocator()) syntax::DeclarationStatement, S);1411 return true;1412 }1413 1414 bool WalkUpFromNullStmt(NullStmt *S) {1415 Builder.foldNode(Builder.getStmtRange(S),1416 new (allocator()) syntax::EmptyStatement, S);1417 return true;1418 }1419 1420 bool WalkUpFromSwitchStmt(SwitchStmt *S) {1421 Builder.markChildToken(S->getSwitchLoc(),1422 syntax::NodeRole::IntroducerKeyword);1423 Builder.markStmtChild(S->getBody(), syntax::NodeRole::BodyStatement);1424 Builder.foldNode(Builder.getStmtRange(S),1425 new (allocator()) syntax::SwitchStatement, S);1426 return true;1427 }1428 1429 bool WalkUpFromCaseStmt(CaseStmt *S) {1430 Builder.markChildToken(S->getKeywordLoc(),1431 syntax::NodeRole::IntroducerKeyword);1432 Builder.markExprChild(S->getLHS(), syntax::NodeRole::CaseValue);1433 Builder.markStmtChild(S->getSubStmt(), syntax::NodeRole::BodyStatement);1434 Builder.foldNode(Builder.getStmtRange(S),1435 new (allocator()) syntax::CaseStatement, S);1436 return true;1437 }1438 1439 bool WalkUpFromDefaultStmt(DefaultStmt *S) {1440 Builder.markChildToken(S->getKeywordLoc(),1441 syntax::NodeRole::IntroducerKeyword);1442 Builder.markStmtChild(S->getSubStmt(), syntax::NodeRole::BodyStatement);1443 Builder.foldNode(Builder.getStmtRange(S),1444 new (allocator()) syntax::DefaultStatement, S);1445 return true;1446 }1447 1448 bool WalkUpFromIfStmt(IfStmt *S) {1449 Builder.markChildToken(S->getIfLoc(), syntax::NodeRole::IntroducerKeyword);1450 Stmt *ConditionStatement = S->getCond();1451 if (S->hasVarStorage())1452 ConditionStatement = S->getConditionVariableDeclStmt();1453 Builder.markStmtChild(ConditionStatement, syntax::NodeRole::Condition);1454 Builder.markStmtChild(S->getThen(), syntax::NodeRole::ThenStatement);1455 Builder.markChildToken(S->getElseLoc(), syntax::NodeRole::ElseKeyword);1456 Builder.markStmtChild(S->getElse(), syntax::NodeRole::ElseStatement);1457 Builder.foldNode(Builder.getStmtRange(S),1458 new (allocator()) syntax::IfStatement, S);1459 return true;1460 }1461 1462 bool WalkUpFromForStmt(ForStmt *S) {1463 Builder.markChildToken(S->getForLoc(), syntax::NodeRole::IntroducerKeyword);1464 Builder.markStmtChild(S->getBody(), syntax::NodeRole::BodyStatement);1465 Builder.foldNode(Builder.getStmtRange(S),1466 new (allocator()) syntax::ForStatement, S);1467 return true;1468 }1469 1470 bool WalkUpFromWhileStmt(WhileStmt *S) {1471 Builder.markChildToken(S->getWhileLoc(),1472 syntax::NodeRole::IntroducerKeyword);1473 Builder.markStmtChild(S->getBody(), syntax::NodeRole::BodyStatement);1474 Builder.foldNode(Builder.getStmtRange(S),1475 new (allocator()) syntax::WhileStatement, S);1476 return true;1477 }1478 1479 bool WalkUpFromContinueStmt(ContinueStmt *S) {1480 Builder.markChildToken(S->getKwLoc(), syntax::NodeRole::IntroducerKeyword);1481 Builder.foldNode(Builder.getStmtRange(S),1482 new (allocator()) syntax::ContinueStatement, S);1483 return true;1484 }1485 1486 bool WalkUpFromBreakStmt(BreakStmt *S) {1487 Builder.markChildToken(S->getKwLoc(), syntax::NodeRole::IntroducerKeyword);1488 Builder.foldNode(Builder.getStmtRange(S),1489 new (allocator()) syntax::BreakStatement, S);1490 return true;1491 }1492 1493 bool WalkUpFromReturnStmt(ReturnStmt *S) {1494 Builder.markChildToken(S->getReturnLoc(),1495 syntax::NodeRole::IntroducerKeyword);1496 Builder.markExprChild(S->getRetValue(), syntax::NodeRole::ReturnValue);1497 Builder.foldNode(Builder.getStmtRange(S),1498 new (allocator()) syntax::ReturnStatement, S);1499 return true;1500 }1501 1502 bool WalkUpFromCXXForRangeStmt(CXXForRangeStmt *S) {1503 Builder.markChildToken(S->getForLoc(), syntax::NodeRole::IntroducerKeyword);1504 Builder.markStmtChild(S->getBody(), syntax::NodeRole::BodyStatement);1505 Builder.foldNode(Builder.getStmtRange(S),1506 new (allocator()) syntax::RangeBasedForStatement, S);1507 return true;1508 }1509 1510 bool WalkUpFromEmptyDecl(EmptyDecl *S) {1511 Builder.foldNode(Builder.getDeclarationRange(S),1512 new (allocator()) syntax::EmptyDeclaration, S);1513 return true;1514 }1515 1516 bool WalkUpFromStaticAssertDecl(StaticAssertDecl *S) {1517 Builder.markExprChild(S->getAssertExpr(), syntax::NodeRole::Condition);1518 Builder.markExprChild(S->getMessage(), syntax::NodeRole::Message);1519 Builder.foldNode(Builder.getDeclarationRange(S),1520 new (allocator()) syntax::StaticAssertDeclaration, S);1521 return true;1522 }1523 1524 bool WalkUpFromLinkageSpecDecl(LinkageSpecDecl *S) {1525 Builder.foldNode(Builder.getDeclarationRange(S),1526 new (allocator()) syntax::LinkageSpecificationDeclaration,1527 S);1528 return true;1529 }1530 1531 bool WalkUpFromNamespaceAliasDecl(NamespaceAliasDecl *S) {1532 Builder.foldNode(Builder.getDeclarationRange(S),1533 new (allocator()) syntax::NamespaceAliasDefinition, S);1534 return true;1535 }1536 1537 bool WalkUpFromUsingDirectiveDecl(UsingDirectiveDecl *S) {1538 Builder.foldNode(Builder.getDeclarationRange(S),1539 new (allocator()) syntax::UsingNamespaceDirective, S);1540 return true;1541 }1542 1543 bool WalkUpFromUsingDecl(UsingDecl *S) {1544 Builder.foldNode(Builder.getDeclarationRange(S),1545 new (allocator()) syntax::UsingDeclaration, S);1546 return true;1547 }1548 1549 bool WalkUpFromUnresolvedUsingValueDecl(UnresolvedUsingValueDecl *S) {1550 Builder.foldNode(Builder.getDeclarationRange(S),1551 new (allocator()) syntax::UsingDeclaration, S);1552 return true;1553 }1554 1555 bool WalkUpFromUnresolvedUsingTypenameDecl(UnresolvedUsingTypenameDecl *S) {1556 Builder.foldNode(Builder.getDeclarationRange(S),1557 new (allocator()) syntax::UsingDeclaration, S);1558 return true;1559 }1560 1561 bool WalkUpFromTypeAliasDecl(TypeAliasDecl *S) {1562 Builder.foldNode(Builder.getDeclarationRange(S),1563 new (allocator()) syntax::TypeAliasDeclaration, S);1564 return true;1565 }1566 1567private:1568 /// Folds SimpleDeclarator node (if present) and in case this is the last1569 /// declarator in the chain it also folds SimpleDeclaration node.1570 template <class T> bool processDeclaratorAndDeclaration(T *D) {1571 auto Range = getDeclaratorRange(1572 Builder.sourceManager(), D->getTypeSourceInfo()->getTypeLoc(),1573 getQualifiedNameStart(D), getInitializerRange(D));1574 1575 // There doesn't have to be a declarator (e.g. `void foo(int)` only has1576 // declaration, but no declarator).1577 if (!Range.getBegin().isValid()) {1578 Builder.markChild(new (allocator()) syntax::DeclaratorList,1579 syntax::NodeRole::Declarators);1580 Builder.foldNode(Builder.getDeclarationRange(D),1581 new (allocator()) syntax::SimpleDeclaration, D);1582 return true;1583 }1584 1585 auto *N = new (allocator()) syntax::SimpleDeclarator;1586 Builder.foldNode(Builder.getRange(Range), N, nullptr);1587 Builder.markChild(N, syntax::NodeRole::ListElement);1588 1589 if (!Builder.isResponsibleForCreatingDeclaration(D)) {1590 // If this is not the last declarator in the declaration we expect a1591 // delimiter after it.1592 const auto *DelimiterToken = std::next(Builder.findToken(Range.getEnd()));1593 if (DelimiterToken->kind() == clang::tok::TokenKind::comma)1594 Builder.markChildToken(DelimiterToken, syntax::NodeRole::ListDelimiter);1595 } else {1596 auto *DL = new (allocator()) syntax::DeclaratorList;1597 auto DeclarationRange = Builder.getDeclarationRange(D);1598 Builder.foldList(DeclarationRange, DL, nullptr);1599 1600 Builder.markChild(DL, syntax::NodeRole::Declarators);1601 Builder.foldNode(DeclarationRange,1602 new (allocator()) syntax::SimpleDeclaration, D);1603 }1604 return true;1605 }1606 1607 /// Returns the range of the built node.1608 syntax::TrailingReturnType *buildTrailingReturn(FunctionProtoTypeLoc L) {1609 assert(L.getTypePtr()->hasTrailingReturn());1610 1611 auto ReturnedType = L.getReturnLoc();1612 // Build node for the declarator, if any.1613 auto ReturnDeclaratorRange = SourceRange(GetStartLoc().Visit(ReturnedType),1614 ReturnedType.getEndLoc());1615 syntax::SimpleDeclarator *ReturnDeclarator = nullptr;1616 if (ReturnDeclaratorRange.isValid()) {1617 ReturnDeclarator = new (allocator()) syntax::SimpleDeclarator;1618 Builder.foldNode(Builder.getRange(ReturnDeclaratorRange),1619 ReturnDeclarator, nullptr);1620 }1621 1622 // Build node for trailing return type.1623 auto Return = Builder.getRange(ReturnedType.getSourceRange());1624 const auto *Arrow = Return.begin() - 1;1625 assert(Arrow->kind() == tok::arrow);1626 auto Tokens = llvm::ArrayRef(Arrow, Return.end());1627 Builder.markChildToken(Arrow, syntax::NodeRole::ArrowToken);1628 if (ReturnDeclarator)1629 Builder.markChild(ReturnDeclarator, syntax::NodeRole::Declarator);1630 auto *R = new (allocator()) syntax::TrailingReturnType;1631 Builder.foldNode(Tokens, R, L);1632 return R;1633 }1634 1635 void foldExplicitTemplateInstantiation(1636 ArrayRef<syntax::Token> Range, const syntax::Token *ExternKW,1637 const syntax::Token *TemplateKW,1638 syntax::SimpleDeclaration *InnerDeclaration, Decl *From) {1639 assert(!ExternKW || ExternKW->kind() == tok::kw_extern);1640 assert(TemplateKW && TemplateKW->kind() == tok::kw_template);1641 Builder.markChildToken(ExternKW, syntax::NodeRole::ExternKeyword);1642 Builder.markChildToken(TemplateKW, syntax::NodeRole::IntroducerKeyword);1643 Builder.markChild(InnerDeclaration, syntax::NodeRole::Declaration);1644 Builder.foldNode(1645 Range, new (allocator()) syntax::ExplicitTemplateInstantiation, From);1646 }1647 1648 syntax::TemplateDeclaration *foldTemplateDeclaration(1649 ArrayRef<syntax::Token> Range, const syntax::Token *TemplateKW,1650 ArrayRef<syntax::Token> TemplatedDeclaration, Decl *From) {1651 assert(TemplateKW && TemplateKW->kind() == tok::kw_template);1652 Builder.markChildToken(TemplateKW, syntax::NodeRole::IntroducerKeyword);1653 1654 auto *N = new (allocator()) syntax::TemplateDeclaration;1655 Builder.foldNode(Range, N, From);1656 Builder.markChild(N, syntax::NodeRole::Declaration);1657 return N;1658 }1659 1660 /// A small helper to save some typing.1661 llvm::BumpPtrAllocator &allocator() { return Builder.allocator(); }1662 1663 syntax::TreeBuilder &Builder;1664 const ASTContext &Context;1665};1666} // namespace1667 1668void syntax::TreeBuilder::noticeDeclWithoutSemicolon(Decl *D) {1669 DeclsWithoutSemicolons.insert(D);1670}1671 1672void syntax::TreeBuilder::markChildToken(SourceLocation Loc, NodeRole Role) {1673 if (Loc.isInvalid())1674 return;1675 Pending.assignRole(*findToken(Loc), Role);1676}1677 1678void syntax::TreeBuilder::markChildToken(const syntax::Token *T, NodeRole R) {1679 if (!T)1680 return;1681 Pending.assignRole(*T, R);1682}1683 1684void syntax::TreeBuilder::markChild(syntax::Node *N, NodeRole R) {1685 assert(N);1686 setRole(N, R);1687}1688 1689void syntax::TreeBuilder::markChild(ASTPtr N, NodeRole R) {1690 auto *SN = Mapping.find(N);1691 assert(SN != nullptr);1692 setRole(SN, R);1693}1694void syntax::TreeBuilder::markChild(NestedNameSpecifierLoc NNSLoc, NodeRole R) {1695 auto *SN = Mapping.find(NNSLoc);1696 assert(SN != nullptr);1697 setRole(SN, R);1698}1699 1700void syntax::TreeBuilder::markStmtChild(Stmt *Child, NodeRole Role) {1701 if (!Child)1702 return;1703 1704 syntax::Tree *ChildNode;1705 if (Expr *ChildExpr = dyn_cast<Expr>(Child)) {1706 // This is an expression in a statement position, consume the trailing1707 // semicolon and form an 'ExpressionStatement' node.1708 markExprChild(ChildExpr, NodeRole::Expression);1709 ChildNode = new (allocator()) syntax::ExpressionStatement;1710 // (!) 'getStmtRange()' ensures this covers a trailing semicolon.1711 Pending.foldChildren(TBTM.tokenBuffer(), getStmtRange(Child), ChildNode);1712 } else {1713 ChildNode = Mapping.find(Child);1714 }1715 assert(ChildNode != nullptr);1716 setRole(ChildNode, Role);1717}1718 1719void syntax::TreeBuilder::markExprChild(Expr *Child, NodeRole Role) {1720 if (!Child)1721 return;1722 Child = IgnoreImplicit(Child);1723 1724 syntax::Tree *ChildNode = Mapping.find(Child);1725 assert(ChildNode != nullptr);1726 setRole(ChildNode, Role);1727}1728 1729const syntax::Token *syntax::TreeBuilder::findToken(SourceLocation L) const {1730 if (L.isInvalid())1731 return nullptr;1732 auto It = LocationToToken.find(L);1733 assert(It != LocationToToken.end());1734 return It->second;1735}1736 1737syntax::TranslationUnit *syntax::buildSyntaxTree(Arena &A,1738 TokenBufferTokenManager& TBTM,1739 ASTContext &Context) {1740 TreeBuilder Builder(A, TBTM);1741 BuildTreeVisitor(Context, Builder).TraverseAST(Context);1742 return std::move(Builder).finalize();1743}1744