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