[Syntax] Build template declaration nodes

[hlopko]

Summary

Copy of https://reviews.llvm.org/D72334, submitting with Ilya's permission.

Handles template declaration of all kinds.

Also builds template declaration nodes for specializations and explicit
instantiations of classes.

Some missing things will be addressed in the follow-up patches:

specializations of functions and variables,
template parameters.

[hlopko]

Clang tidy

[thakis]

Breaks tests on Windows: http://45.33.8.238/win/10716/step_7.txt

Please take a look and revert if it takes a while to fix.

[thakis]

Reverted in 881f5b5a7b2 for now. Usually the fix is to add -fno-delayed-template-parsing somewhere, but in this case it seems like the whole feature might not expect delayed template parsing, so maybe something more holistic is needed in this case.

clang/include/clang/Tooling/Syntax/Nodes.h

enum class NodeKind : uint16_t {
   CompoundStatement,
 
   // Declarations.
   UnknownDeclaration,
   EmptyDeclaration,
   StaticAssertDeclaration,
   LinkageSpecificationDeclaration,
   SimpleDeclaration,
+  TemplateDeclaration,
+  ExplicitTemplateInstantiation,
   NamespaceDefinition,
   NamespaceAliasDefinition,
   UsingNamespaceDirective,
   UsingDeclaration,
   TypeAliasDeclaration,
 
   // Declarators.
   SimpleDeclarator,
enum class NodeRole : uint8_t {
   IfStatement_elseKeyword,
   IfStatement_elseStatement,
   ReturnStatement_value,
   ExpressionStatement_expression,
   CompoundStatement_statement,
   StaticAssertDeclaration_condition,
   StaticAssertDeclaration_message,
   SimpleDeclaration_declarator,
+  TemplateDeclaration_declaration,
+  ExplicitTemplateInstantiation_externKeyword,
+  ExplicitTemplateInstantiation_declaration,
   ArraySubscript_sizeExpression,
   TrailingReturnType_arrow,
   TrailingReturnType_declarator,
   ParametersAndQualifiers_parameter,
   ParametersAndQualifiers_trailingReturn
 };
 /// For debugging purposes.
 llvm::raw_ostream &operator<<(llvm::raw_ostream &OS, NodeRole R);
public:
   SimpleDeclaration() : Declaration(NodeKind::SimpleDeclaration) {}
   static bool classof(const Node *N) {
     return N->kind() == NodeKind::SimpleDeclaration;
   }
   /// FIXME: use custom iterator instead of 'vector'.
   std::vector<syntax::SimpleDeclarator *> declarators();
 };
 
+/// template <template-parameters> <declaration>
+class TemplateDeclaration final : public Declaration {
+public:
+  TemplateDeclaration() : Declaration(NodeKind::TemplateDeclaration) {}
+  static bool classof(const Node *N) {
+    return N->kind() == NodeKind::TemplateDeclaration;
+  }
+  syntax::Leaf *templateKeyword();
+  syntax::Declaration *declaration();
+};
+
+/// template <declaration>
+/// Examples:
+///     template struct X<int>
+///     template void foo<int>()
+///     template int var<double>
+class ExplicitTemplateInstantiation final : public Declaration {
+public:
+  ExplicitTemplateInstantiation()
+      : Declaration(NodeKind::ExplicitTemplateInstantiation) {}
+  static bool classof(const Node *N) {
+    return N->kind() == NodeKind::ExplicitTemplateInstantiation;
+  }
+  syntax::Leaf *templateKeyword();
+  syntax::Leaf *externKeyword();
+  syntax::Declaration *declaration();
+};
+
 /// namespace <name> { <decls> }
 class NamespaceDefinition final : public Declaration {
 public:
   NamespaceDefinition() : Declaration(NodeKind::NamespaceDefinition) {}
   static bool classof(const Node *N) {
     return N->kind() == NodeKind::NamespaceDefinition;
   }
 };

clang/lib/Tooling/Syntax/BuildTree.cpp

 #include "clang/AST/DeclarationName.h"
 #include "clang/AST/RecursiveASTVisitor.h"
 #include "clang/AST/Stmt.h"
 #include "clang/AST/TypeLoc.h"
 #include "clang/AST/TypeLocVisitor.h"
 #include "clang/Basic/LLVM.h"
 #include "clang/Basic/SourceLocation.h"
 #include "clang/Basic/SourceManager.h"
+#include "clang/Basic/Specifiers.h"
 #include "clang/Basic/TokenKinds.h"
 #include "clang/Lex/Lexer.h"
 #include "clang/Tooling/Syntax/Nodes.h"
 #include "clang/Tooling/Syntax/Tokens.h"
 #include "clang/Tooling/Syntax/Tree.h"
 #include "llvm/ADT/ArrayRef.h"
 #include "llvm/ADT/STLExtras.h"
 #include "llvm/ADT/ScopeExit.h"
public:
   /// Mark the \p Child node with a corresponding \p Role. All marked children
   /// should be consumed by foldNode.
   /// When called on expressions (clang::Expr is derived from clang::Stmt),
   /// wraps expressions into expression statement.
   void markStmtChild(Stmt *Child, NodeRole Role);
   /// Should be called for expressions in non-statement position to avoid
   /// wrapping into expression statement.
   void markExprChild(Expr *Child, NodeRole Role);
-
   /// Set role for a token starting at \p Loc.
   void markChildToken(SourceLocation Loc, NodeRole R);
   /// Set role for \p T.
   void markChildToken(const syntax::Token *T, NodeRole R);
 
   /// Set role for the node that spans exactly \p Range.
   void markChild(llvm::ArrayRef<syntax::Token> Range, NodeRole R);
   /// Set role for the delayed node that spans exactly \p Range.
   void markDelayedChild(llvm::ArrayRef<syntax::Token> Range, NodeRole R);
+  /// Set role for the node that may or may not be delayed. Node must span
+  /// exactly \p Range.
+  void markMaybeDelayedChild(llvm::ArrayRef<syntax::Token> Range, NodeRole R);
 
   /// Finish building the tree and consume the root node.
   syntax::TranslationUnit *finalize() && {
     auto Tokens = Arena.tokenBuffer().expandedTokens();
     assert(!Tokens.empty());
     assert(Tokens.back().kind() == tok::eof);
 
     // Build the root of the tree, consuming all the children.
     Pending.foldChildren(Arena, Tokens.drop_back(),
                          new (Arena.allocator()) syntax::TranslationUnit);
 
     auto *TU = cast<syntax::TranslationUnit>(std::move(Pending).finalize());
     TU->assertInvariantsRecursive();
     return TU;
   }
 
+  /// Finds a token starting at \p L. The token must exist if \p L is valid.
+  const syntax::Token *findToken(SourceLocation L) const;
+
   /// getRange() finds the syntax tokens corresponding to the passed source
   /// locations.
   /// \p First is the start position of the first token and \p Last is the start
   /// position of the last token.
   llvm::ArrayRef<syntax::Token> getRange(SourceLocation First,
                                          SourceLocation Last) const {
     assert(First.isValid());
     assert(Last.isValid());
     assert(First == Last ||
            Arena.sourceManager().isBeforeInTranslationUnit(First, Last));
     return llvm::makeArrayRef(findToken(First), std::next(findToken(Last)));
   }
-  llvm::ArrayRef<syntax::Token> getRange(const Decl *D) const {
-    auto Tokens = getRange(D->getBeginLoc(), D->getEndLoc());
-    if (llvm::isa<NamespaceDecl>(D))
-      return Tokens;
-    if (DeclsWithoutSemicolons.count(D))
-      return Tokens;
-    // FIXME: do not consume trailing semicolon on function definitions.
-    // Most declarations own a semicolon in syntax trees, but not in clang AST.
-    return withTrailingSemicolon(Tokens);
+
+  llvm::ArrayRef<syntax::Token>
+  getTemplateRange(const ClassTemplateSpecializationDecl *D) const {
+    auto R = D->getSourceRange();
+    auto Tokens = getRange(R.getBegin(), R.getEnd());
+    return maybeAppendSemicolon(Tokens, D);
+  }
+
+  llvm::ArrayRef<syntax::Token> getDeclRange(const Decl *D) const {
+    llvm::ArrayRef<clang::syntax::Token> Tokens;
+    // We want to drop the template parameters for specializations.
+    if (const auto *S = llvm::dyn_cast<TagDecl>(D))
+      Tokens = getRange(S->TypeDecl::getBeginLoc(), S->getEndLoc());
+    else
+      Tokens = getRange(D->getBeginLoc(), D->getEndLoc());
+    return maybeAppendSemicolon(Tokens, D);
   }
   llvm::ArrayRef<syntax::Token> getExprRange(const Expr *E) const {
     return getRange(E->getBeginLoc(), E->getEndLoc());
   }
   /// Find the adjusted range for the statement, consuming the trailing
   /// semicolon when needed.
   llvm::ArrayRef<syntax::Token> getStmtRange(const Stmt *S) const {
     auto Tokens = getRange(S->getBeginLoc(), S->getEndLoc());
     if (isa<CompoundStmt>(S))
       return Tokens;
 
     // Some statements miss a trailing semicolon, e.g. 'return', 'continue' and
     // all statements that end with those. Consume this semicolon here.
     if (Tokens.back().kind() == tok::semi)
       return Tokens;
     return withTrailingSemicolon(Tokens);
   }
 
 private:
   llvm::ArrayRef<syntax::Token>
+  maybeAppendSemicolon(llvm::ArrayRef<syntax::Token> Tokens,
+                       const Decl *D) const {
+    if (llvm::isa<NamespaceDecl>(D))
+      return Tokens;
+    if (DeclsWithoutSemicolons.count(D))
+      return Tokens;
+    // FIXME: do not consume trailing semicolon on function definitions.
+    // Most declarations own a semicolon in syntax trees, but not in clang AST.
+    return withTrailingSemicolon(Tokens);
+  }
+
+  llvm::ArrayRef<syntax::Token>
   withTrailingSemicolon(llvm::ArrayRef<syntax::Token> Tokens) const {
     assert(!Tokens.empty());
     assert(Tokens.back().kind() != tok::eof);
     // We never consume 'eof', so looking at the next token is ok.
     if (Tokens.back().kind() != tok::semi && Tokens.end()->kind() == tok::semi)
       return llvm::makeArrayRef(Tokens.begin(), Tokens.end() + 1);
     return Tokens;
   }
 
-  /// Finds a token starting at \p L. The token must exist.
-  const syntax::Token *findToken(SourceLocation L) const;
-
   /// A collection of trees covering the input tokens.
   /// When created, each tree corresponds to a single token in the file.
   /// Clients call 'foldChildren' to attach one or more subtrees to a parent
   /// node and update the list of trees accordingly.
   ///
   /// Ensures that added nodes properly nest and cover the whole token stream.
   struct Forest {
     Forest(syntax::Arena &A) {
struct Forest {
     void assignRoleDelayed(llvm::ArrayRef<syntax::Token> Range,
                            syntax::NodeRole Role) {
       auto It = DelayedFolds.find(Range.begin());
       assert(It != DelayedFolds.end());
       assert(It->second.End == Range.end());
       It->second.Role = Role;
     }
 
+    void assignRoleMaybeDelayed(llvm::ArrayRef<syntax::Token> Range,
+                                syntax::NodeRole Role) {
+      auto It = DelayedFolds.find(Range.begin());
+      if (It == DelayedFolds.end())
+        return assignRole(Range, Role);
+      assert(It->second.End == Range.end());
+      It->second.Role = Role;
+    }
+
     void assignRole(llvm::ArrayRef<syntax::Token> Range,
                     syntax::NodeRole Role) {
       assert(!Range.empty());
       auto It = Trees.lower_bound(Range.begin());
       assert(It != Trees.end() && "no node found");
       assert(It->first == Range.begin() && "no child with the specified range");
       assert((std::next(It) == Trees.end() ||
               std::next(It)->first == Range.end()) &&

 public:
   explicit BuildTreeVisitor(ASTContext &Ctx, syntax::TreeBuilder &Builder)
       : Builder(Builder), LangOpts(Ctx.getLangOpts()) {}
 
   bool shouldTraversePostOrder() const { return true; }
 
   bool WalkUpFromDeclaratorDecl(DeclaratorDecl *DD) {
     // Ensure declarators are covered by SimpleDeclaration.
-    Builder.noticeDeclRange(Builder.getRange(DD));
+    Builder.noticeDeclRange(Builder.getDeclRange(DD));
 
     // Build the declarator node.
     SourceRange Initializer;
     if (auto *V = llvm::dyn_cast<VarDecl>(DD)) {
       auto *I = V->getInit();
       // Initializers in range-based-for are not part of the declarator
       if (I && !V->isCXXForRangeDecl())
         Initializer = I->getSourceRange();
     }
     auto Declarator = getDeclaratorRange(
         Builder.sourceManager(), DD->getTypeSourceInfo()->getTypeLoc(),
         getQualifiedNameStart(DD), Initializer);
     if (Declarator.isValid()) {
       auto Tokens =
           Builder.getRange(Declarator.getBegin(), Declarator.getEnd());
       Builder.foldNode(Tokens, new (allocator()) syntax::SimpleDeclarator);
       Builder.markChild(Tokens, syntax::NodeRole::SimpleDeclaration_declarator);
     }
 
     return true;
   }
 
   bool WalkUpFromTypedefNameDecl(TypedefNameDecl *D) {
     // Ensure declarators are covered by SimpleDeclaration.
-    Builder.noticeDeclRange(Builder.getRange(D));
+    Builder.noticeDeclRange(Builder.getDeclRange(D));
 
     auto R = getDeclaratorRange(
         Builder.sourceManager(), D->getTypeSourceInfo()->getTypeLoc(),
         /*Name=*/D->getLocation(), /*Initializer=*/SourceRange());
     if (R.isValid()) {
       auto Tokens = Builder.getRange(R.getBegin(), R.getEnd());
       Builder.foldNode(Tokens, new (allocator()) syntax::SimpleDeclarator);
       Builder.markChild(Tokens, syntax::NodeRole::SimpleDeclaration_declarator);
     }
     return true;
   }
 
   bool VisitDecl(Decl *D) {
     assert(!D->isImplicit());
-    Builder.foldNode(Builder.getRange(D),
+    Builder.foldNode(Builder.getDeclRange(D),
                      new (allocator()) syntax::UnknownDeclaration());
     return true;
   }
 
+  // RAV does not call WalkUpFrom* on explicit instantiations, so we have to
+  // override Traverse.
+  // FIXME: make RAV call WalkUpFrom* instead.
+  bool
+  TraverseClassTemplateSpecializationDecl(ClassTemplateSpecializationDecl *C) {
+    if (!RecursiveASTVisitor::TraverseClassTemplateSpecializationDecl(C))
+      return false;
+    if (C->isExplicitSpecialization())
+      return true; // we are only interested in explicit instantiations.
+    if (!WalkUpFromClassTemplateSpecializationDecl(C))
+      return false;
+    foldExplicitTemplateInstantiation(
+        Builder.getTemplateRange(C), Builder.findToken(C->getExternLoc()),
+        Builder.findToken(C->getTemplateKeywordLoc()), Builder.getDeclRange(C));
+    return true;
+  }
+
+  bool WalkUpFromTemplateDecl(TemplateDecl *S) {
+    foldTemplateDeclaration(
+        Builder.getDeclRange(S),
+        Builder.findToken(S->getTemplateParameters()->getTemplateLoc()),
+        Builder.getDeclRange(S->getTemplatedDecl()));
+    return true;
+  }
+
   bool WalkUpFromTagDecl(TagDecl *C) {
     // FIXME: build the ClassSpecifier node.
-    if (C->isFreeStanding()) {
-      // Class is a declaration specifier and needs a spanning declaration node.
-      Builder.foldNode(Builder.getRange(C),
-                       new (allocator()) syntax::SimpleDeclaration);
+    if (!C->isFreeStanding()) {
+      assert(C->getNumTemplateParameterLists() == 0);
       return true;
     }
+    // Class is a declaration specifier and needs a spanning declaration node.
+    auto DeclarationRange = Builder.getDeclRange(C);
+    Builder.foldNode(DeclarationRange,
+                     new (allocator()) syntax::SimpleDeclaration);
+
+    // Build TemplateDeclaration nodes if we had template parameters.
+    auto ConsumeTemplateParameters = [&](const TemplateParameterList &L) {
+      const auto *TemplateKW = Builder.findToken(L.getTemplateLoc());
+      auto R = llvm::makeArrayRef(TemplateKW, DeclarationRange.end());
+      foldTemplateDeclaration(R, TemplateKW, DeclarationRange);
+
+      DeclarationRange = R;
+    };
+    if (auto *S = llvm::dyn_cast<ClassTemplatePartialSpecializationDecl>(C))
+      ConsumeTemplateParameters(*S->getTemplateParameters());
+    for (unsigned I = C->getNumTemplateParameterLists(); 0 < I; --I)
+      ConsumeTemplateParameters(*C->getTemplateParameterList(I - 1));
     return true;
   }
 
   bool WalkUpFromTranslationUnitDecl(TranslationUnitDecl *TU) {
     // We do not want to call VisitDecl(), the declaration for translation
     // unit is built by finalize().
     return true;
   }
public:
   bool WalkUpFromExpr(Expr *E) {
     assert(!isImplicitExpr(E) && "should be handled by TraverseStmt");
     Builder.foldNode(Builder.getExprRange(E),
                      new (allocator()) syntax::UnknownExpression);
     return true;
   }
 
   bool WalkUpFromNamespaceDecl(NamespaceDecl *S) {
-    auto Tokens = Builder.getRange(S);
+    auto Tokens = Builder.getDeclRange(S);
     if (Tokens.front().kind() == tok::coloncolon) {
       // Handle nested namespace definitions. Those start at '::' token, e.g.
       // namespace a^::b {}
       // FIXME: build corresponding nodes for the name of this namespace.
       return true;
     }
     Builder.foldNode(Tokens, new (allocator()) syntax::NamespaceDefinition);
     return true;
Builder.foldNode(Builder.getRange(L.getLBracketLoc(), L.getRBracketLoc()),
                      new (allocator()) syntax::ArraySubscript);
     return true;
   }
 
   bool WalkUpFromFunctionTypeLoc(FunctionTypeLoc L) {
     Builder.markChildToken(L.getLParenLoc(), syntax::NodeRole::OpenParen);
     for (auto *P : L.getParams())
       Builder.markDelayedChild(
-          Builder.getRange(P),
+          Builder.getDeclRange(P),
           syntax::NodeRole::ParametersAndQualifiers_parameter);
     Builder.markChildToken(L.getRParenLoc(), syntax::NodeRole::CloseParen);
     Builder.foldNode(Builder.getRange(L.getLParenLoc(), L.getEndLoc()),
                      new (allocator()) syntax::ParametersAndQualifiers);
     return true;
   }
 
   bool WalkUpFromFunctionProtoTypeLoc(FunctionProtoTypeLoc L) {
bool WalkUpFromCXXForRangeStmt(CXXForRangeStmt *S) {
     Builder.markChildToken(S->getForLoc(), syntax::NodeRole::IntroducerKeyword);
     Builder.markStmtChild(S->getBody(), syntax::NodeRole::BodyStatement);
     Builder.foldNode(Builder.getStmtRange(S),
                      new (allocator()) syntax::RangeBasedForStatement);
     return true;
   }
 
   bool WalkUpFromEmptyDecl(EmptyDecl *S) {
-    Builder.foldNode(Builder.getRange(S),
+    Builder.foldNode(Builder.getDeclRange(S),
                      new (allocator()) syntax::EmptyDeclaration);
     return true;
   }
 
   bool WalkUpFromStaticAssertDecl(StaticAssertDecl *S) {
     Builder.markExprChild(S->getAssertExpr(),
                           syntax::NodeRole::StaticAssertDeclaration_condition);
     Builder.markExprChild(S->getMessage(),
                           syntax::NodeRole::StaticAssertDeclaration_message);
-    Builder.foldNode(Builder.getRange(S),
+    Builder.foldNode(Builder.getDeclRange(S),
                      new (allocator()) syntax::StaticAssertDeclaration);
     return true;
   }
 
   bool WalkUpFromLinkageSpecDecl(LinkageSpecDecl *S) {
-    Builder.foldNode(Builder.getRange(S),
+    Builder.foldNode(Builder.getDeclRange(S),
                      new (allocator()) syntax::LinkageSpecificationDeclaration);
     return true;
   }
 
   bool WalkUpFromNamespaceAliasDecl(NamespaceAliasDecl *S) {
-    Builder.foldNode(Builder.getRange(S),
+    Builder.foldNode(Builder.getDeclRange(S),
                      new (allocator()) syntax::NamespaceAliasDefinition);
     return true;
   }
 
   bool WalkUpFromUsingDirectiveDecl(UsingDirectiveDecl *S) {
-    Builder.foldNode(Builder.getRange(S),
+    Builder.foldNode(Builder.getDeclRange(S),
                      new (allocator()) syntax::UsingNamespaceDirective);
     return true;
   }
 
   bool WalkUpFromUsingDecl(UsingDecl *S) {
-    Builder.foldNode(Builder.getRange(S),
+    Builder.foldNode(Builder.getDeclRange(S),
                      new (allocator()) syntax::UsingDeclaration);
     return true;
   }
 
   bool WalkUpFromUnresolvedUsingValueDecl(UnresolvedUsingValueDecl *S) {
-    Builder.foldNode(Builder.getRange(S),
+    Builder.foldNode(Builder.getDeclRange(S),
                      new (allocator()) syntax::UsingDeclaration);
     return true;
   }
 
   bool WalkUpFromUnresolvedUsingTypenameDecl(UnresolvedUsingTypenameDecl *S) {
-    Builder.foldNode(Builder.getRange(S),
+    Builder.foldNode(Builder.getDeclRange(S),
                      new (allocator()) syntax::UsingDeclaration);
     return true;
   }
 
   bool WalkUpFromTypeAliasDecl(TypeAliasDecl *S) {
-    Builder.foldNode(Builder.getRange(S),
+    Builder.foldNode(Builder.getDeclRange(S),
                      new (allocator()) syntax::TypeAliasDeclaration);
     return true;
   }
 
 private:
   /// Returns the range of the built node.
   llvm::ArrayRef<syntax::Token> BuildTrailingReturn(FunctionProtoTypeLoc L) {
     assert(L.getTypePtr()->hasTrailingReturn());
llvm::ArrayRef<syntax::Token> BuildTrailingReturn(FunctionProtoTypeLoc L) {
     auto Tokens = llvm::makeArrayRef(Arrow, Return.end());
     Builder.markChildToken(Arrow, syntax::NodeRole::TrailingReturnType_arrow);
     if (!ReturnDeclaratorTokens.empty())
       Builder.markChild(ReturnDeclaratorTokens,
                         syntax::NodeRole::TrailingReturnType_declarator);
     Builder.foldNode(Tokens, new (allocator()) syntax::TrailingReturnType);
     return Tokens;
   }
+
+  void
+  foldExplicitTemplateInstantiation(ArrayRef<syntax::Token> Range,
+                                    const syntax::Token *ExternKW,
+                                    const syntax::Token *TemplateKW,
+                                    ArrayRef<syntax::Token> InnerDeclaration) {
+    assert(!ExternKW || ExternKW->kind() == tok::kw_extern);
+    assert(TemplateKW && TemplateKW->kind() == tok::kw_template);
+    Builder.markChildToken(
+        ExternKW,
+        syntax::NodeRole::ExplicitTemplateInstantiation_externKeyword);
+    Builder.markChildToken(TemplateKW, syntax::NodeRole::IntroducerKeyword);
+    Builder.markChild(
+        InnerDeclaration,
+        syntax::NodeRole::ExplicitTemplateInstantiation_declaration);
+    Builder.foldNode(Range,
+                     new (allocator()) syntax::ExplicitTemplateInstantiation);
+  }
+
+  void foldTemplateDeclaration(ArrayRef<syntax::Token> Range,
+                               const syntax::Token *TemplateKW,
+                               ArrayRef<syntax::Token> TemplatedDeclaration) {
+    assert(TemplateKW && TemplateKW->kind() == tok::kw_template);
+    Builder.markChildToken(TemplateKW, syntax::NodeRole::IntroducerKeyword);
+    Builder.markMaybeDelayedChild(
+        TemplatedDeclaration,
+        syntax::NodeRole::TemplateDeclaration_declaration);
+    Builder.foldNode(Range, new (allocator()) syntax::TemplateDeclaration);
+  }
+
   /// A small helper to save some typing.
   llvm::BumpPtrAllocator &allocator() { return Builder.allocator(); }
 
   syntax::TreeBuilder &Builder;
   const LangOptions &LangOpts;
 };
 } // namespace
 
void syntax::TreeBuilder::markChild(llvm::ArrayRef<syntax::Token> Range,
   Pending.assignRole(Range, R);
 }
 
 void syntax::TreeBuilder::markDelayedChild(llvm::ArrayRef<syntax::Token> Range,
                                            NodeRole R) {
   Pending.assignRoleDelayed(Range, R);
 }
 
+void syntax::TreeBuilder::markMaybeDelayedChild(
+    llvm::ArrayRef<syntax::Token> Range, NodeRole R) {
+  Pending.assignRoleMaybeDelayed(Range, R);
+}
+
 void syntax::TreeBuilder::markStmtChild(Stmt *Child, NodeRole Role) {
   if (!Child)
     return;
 
   auto Range = getStmtRange(Child);
   // This is an expression in a statement position, consume the trailing
   // semicolon and form an 'ExpressionStatement' node.
   if (auto *E = dyn_cast<Expr>(Child)) {

 void syntax::TreeBuilder::markExprChild(Expr *Child, NodeRole Role) {
   if (!Child)
     return;
 
   Pending.assignRole(getExprRange(Child), Role);
 }
 
 const syntax::Token *syntax::TreeBuilder::findToken(SourceLocation L) const {
+  if (L.isInvalid())
+    return nullptr;
   auto It = LocationToToken.find(L.getRawEncoding());
   assert(It != LocationToToken.end());
   return It->second;
 }
 
 syntax::TranslationUnit *
 syntax::buildSyntaxTree(Arena &A, const TranslationUnitDecl &TU) {
   TreeBuilder Builder(A);
   BuildTreeVisitor(TU.getASTContext(), Builder).TraverseAST(TU.getASTContext());
   return std::move(Builder).finalize();
 }

clang/lib/Tooling/Syntax/Nodes.cpp

llvm::raw_ostream &syntax::operator<<(llvm::raw_ostream &OS, NodeKind K) {
   case NodeKind::EmptyDeclaration:
     return OS << "EmptyDeclaration";
   case NodeKind::StaticAssertDeclaration:
     return OS << "StaticAssertDeclaration";
   case NodeKind::LinkageSpecificationDeclaration:
     return OS << "LinkageSpecificationDeclaration";
   case NodeKind::SimpleDeclaration:
     return OS << "SimpleDeclaration";
+  case NodeKind::TemplateDeclaration:
+    return OS << "TemplateDeclaration";
+  case NodeKind::ExplicitTemplateInstantiation:
+    return OS << "ExplicitTemplateInstantiation";
   case NodeKind::NamespaceDefinition:
     return OS << "NamespaceDefinition";
   case NodeKind::NamespaceAliasDefinition:
     return OS << "NamespaceAliasDefinition";
   case NodeKind::UsingNamespaceDirective:
     return OS << "UsingNamespaceDirective";
   case NodeKind::UsingDeclaration:
     return OS << "UsingDeclaration";
llvm::raw_ostream &syntax::operator<<(llvm::raw_ostream &OS, NodeRole R) {
   case syntax::NodeRole::CompoundStatement_statement:
     return OS << "CompoundStatement_statement";
   case syntax::NodeRole::StaticAssertDeclaration_condition:
     return OS << "StaticAssertDeclaration_condition";
   case syntax::NodeRole::StaticAssertDeclaration_message:
     return OS << "StaticAssertDeclaration_message";
   case syntax::NodeRole::SimpleDeclaration_declarator:
     return OS << "SimpleDeclaration_declarator";
+  case syntax::NodeRole::TemplateDeclaration_declaration:
+    return OS << "TemplateDeclaration_declaration";
+  case syntax::NodeRole::ExplicitTemplateInstantiation_externKeyword:
+    return OS << "ExplicitTemplateInstantiation_externKeyword";
+  case syntax::NodeRole::ExplicitTemplateInstantiation_declaration:
+    return OS << "ExplicitTemplateInstantiation_declaration";
   case syntax::NodeRole::ArraySubscript_sizeExpression:
     return OS << "ArraySubscript_sizeExpression";
   case syntax::NodeRole::TrailingReturnType_arrow:
     return OS << "TrailingReturnType_arrow";
   case syntax::NodeRole::TrailingReturnType_declarator:
     return OS << "TrailingReturnType_declarator";
   case syntax::NodeRole::ParametersAndQualifiers_parameter:
     return OS << "ParametersAndQualifiers_parameter";
syntax::SimpleDeclaration::declarators() {
   std::vector<syntax::SimpleDeclarator *> Children;
   for (auto *C = firstChild(); C; C = C->nextSibling()) {
     if (C->role() == syntax::NodeRole::SimpleDeclaration_declarator)
       Children.push_back(llvm::cast<syntax::SimpleDeclarator>(C));
   }
   return Children;
 }
 
+syntax::Leaf *syntax::TemplateDeclaration::templateKeyword() {
+  return llvm::cast_or_null<syntax::Leaf>(
+      findChild(syntax::NodeRole::IntroducerKeyword));
+}
+
+syntax::Declaration *syntax::TemplateDeclaration::declaration() {
+  return llvm::cast_or_null<syntax::Declaration>(
+      findChild(syntax::NodeRole::TemplateDeclaration_declaration));
+}
+
+syntax::Leaf *syntax::ExplicitTemplateInstantiation::templateKeyword() {
+  return llvm::cast_or_null<syntax::Leaf>(
+      findChild(syntax::NodeRole::IntroducerKeyword));
+}
+
+syntax::Leaf *syntax::ExplicitTemplateInstantiation::externKeyword() {
+  return llvm::cast_or_null<syntax::Leaf>(
+      findChild(syntax::NodeRole::ExplicitTemplateInstantiation_externKeyword));
+}
+
+syntax::Declaration *syntax::ExplicitTemplateInstantiation::declaration() {
+  return llvm::cast_or_null<syntax::Declaration>(
+      findChild(syntax::NodeRole::ExplicitTemplateInstantiation_declaration));
+}
+
 syntax::Leaf *syntax::ParenDeclarator::lparen() {
   return llvm::cast_or_null<syntax::Leaf>(
       findChild(syntax::NodeRole::OpenParen));
 }
 
 syntax::Leaf *syntax::ParenDeclarator::rparen() {
   return llvm::cast_or_null<syntax::Leaf>(
       findChild(syntax::NodeRole::CloseParen));

clang/unittests/Tooling/Syntax/TreeTest.cpp

`-SimpleDeclaration
   |-{
   |-}
   |-SimpleDeclarator
   | |-*
   | `-a1
   `-;
 )txt"},
       {R"cpp(
+template <class T> struct cls {};
+template <class T> int var = 10;
+template <class T> int fun() {}
+    )cpp",
+       R"txt(
+*: TranslationUnit
+|-TemplateDeclaration
+| |-template
+| |-<
+| |-UnknownDeclaration
+| | |-class
+| | `-T
+| |->
+| `-SimpleDeclaration
+|   |-struct
+|   |-cls
+|   |-{
+|   |-}
+|   `-;
+|-TemplateDeclaration
+| |-template
+| |-<
+| |-UnknownDeclaration
+| | |-class
+| | `-T
+| |->
+| `-SimpleDeclaration
+|   |-int
+|   |-SimpleDeclarator
+|   | |-var
+|   | |-=
+|   | `-UnknownExpression
+|   |   `-10
+|   `-;
+`-TemplateDeclaration
+  |-template
+  |-<
+  |-UnknownDeclaration
+  | |-class
+  | `-T
+  |->
+  `-SimpleDeclaration
+    |-int
+    |-SimpleDeclarator
+    | |-fun
+    | `-ParametersAndQualifiers
+    |   |-(
+    |   `-)
+    `-CompoundStatement
+      |-{
+      `-}
+)txt"},
+      {R"cpp(
+template <class T>
+struct X {
+  template <class U>
+  U foo();
+};
+    )cpp",
+       R"txt(
+*: TranslationUnit
+`-TemplateDeclaration
+  |-template
+  |-<
+  |-UnknownDeclaration
+  | |-class
+  | `-T
+  |->
+  `-SimpleDeclaration
+    |-struct
+    |-X
+    |-{
+    |-TemplateDeclaration
+    | |-template
+    | |-<
+    | |-UnknownDeclaration
+    | | |-class
+    | | `-U
+    | |->
+    | `-SimpleDeclaration
+    |   |-U
+    |   |-SimpleDeclarator
+    |   | |-foo
+    |   | `-ParametersAndQualifiers
+    |   |   |-(
+    |   |   `-)
+    |   `-;
+    |-}
+    `-;
+)txt"},
+      {R"cpp(
+template <class T> struct X {};
+template <class T> struct X<T*> {};
+template <> struct X<int> {};
+
+template struct X<double>;
+extern template struct X<float>;
+)cpp",
+       R"txt(
+*: TranslationUnit
+|-TemplateDeclaration
+| |-template
+| |-<
+| |-UnknownDeclaration
+| | |-class
+| | `-T
+| |->
+| `-SimpleDeclaration
+|   |-struct
+|   |-X
+|   |-{
+|   |-}
+|   `-;
+|-TemplateDeclaration
+| |-template
+| |-<
+| |-UnknownDeclaration
+| | |-class
+| | `-T
+| |->
+| `-SimpleDeclaration
+|   |-struct
+|   |-X
+|   |-<
+|   |-T
+|   |-*
+|   |->
+|   |-{
+|   |-}
+|   `-;
+|-TemplateDeclaration
+| |-template
+| |-<
+| |->
+| `-SimpleDeclaration
+|   |-struct
+|   |-X
+|   |-<
+|   |-int
+|   |->
+|   |-{
+|   |-}
+|   `-;
+|-ExplicitTemplateInstantiation
+| |-template
+| `-SimpleDeclaration
+|   |-struct
+|   |-X
+|   |-<
+|   |-double
+|   |->
+|   `-;
+`-ExplicitTemplateInstantiation
+  |-extern
+  |-template
+  `-SimpleDeclaration
+    |-struct
+    |-X
+    |-<
+    |-float
+    |->
+    `-;
+)txt"},
+      {R"cpp(
+template <class T> struct X { struct Y; };
+template <class T> struct X<T>::Y {};
+    )cpp",
+       R"txt(
+*: TranslationUnit
+|-TemplateDeclaration
+| |-template
+| |-<
+| |-UnknownDeclaration
+| | |-class
+| | `-T
+| |->
+| `-SimpleDeclaration
+|   |-struct
+|   |-X
+|   |-{
+|   |-SimpleDeclaration
+|   | |-struct
+|   | |-Y
+|   | `-;
+|   |-}
+|   `-;
+`-TemplateDeclaration
+  |-template
+  |-<
+  |-UnknownDeclaration
+  | |-class
+  | `-T
+  |->
+  `-SimpleDeclaration
+    |-struct
+    |-X
+    |-<
+    |-T
+    |->
+    |-::
+    |-Y
+    |-{
+    |-}
+    `-;
+       )txt"},
+      {R"cpp(
 namespace ns {}
 using namespace ::ns;
     )cpp",
        R"txt(
 *: TranslationUnit
 |-NamespaceDefinition
 | |-namespace
 | |-ns
`-;
       {R"cpp(
 template <class T> struct X {
   using T::foo;
   using typename T::bar;
 };
     )cpp",
        R"txt(
 *: TranslationUnit
-`-UnknownDeclaration
+`-TemplateDeclaration
   |-template
   |-<
   |-UnknownDeclaration
   | |-class
   | `-T
   |->
   `-SimpleDeclaration
     |-struct