[Syntax] Build nodes for template declarations.

[ilya-biryukov]

Summary

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.

[ilya-biryukov]

• Cosmetics

[merge_guards_bot]

Unit tests: unknown.

clang-tidy: unknown.

clang-format: unknown.

Build artifacts: diff.json, console-log.txt

[merge_guards_bot]

Unit tests: unknown.

clang-tidy: unknown.

clang-format: unknown.

Build artifacts: diff.json, console-log.txt

[ilya-biryukov]

• Rebase

[merge_guards_bot]

Unit tests: pass. 61849 tests passed, 0 failed and 781 were skipped.

clang-tidy: unknown.

clang-format: fail. Please format your changes with clang-format by running git-clang-format HEAD^ or applying this patch.

Build artifacts: diff.json, clang-format.patch, CMakeCache.txt, console-log.txt, test-results.xml

[gribozavr2]

clang/lib/Tooling/Syntax/BuildTree.cpp

190

Three slashes for docs.

clang/unittests/Tooling/Syntax/TreeTest.cpp

738

Could you also add an out-of-line definition of X::foo? It will have two template parameter lists, which is a special case.

[gribozavr2]

clang/lib/Tooling/Syntax/BuildTree.cpp

930

Why is this range maybe-delayed?

[hlopko]

Let's continue the review at https://reviews.llvm.org/D76346.

clang/lib/Tooling/Syntax/BuildTree.cpp

190

Done.

930

E.g because template <class T> struct cls {}; is doesn't need delaying, but template <class T> int var = 10;` does (SimpleDeclaration is processed before Declarator). I'll try to come up with a more fitting design after I submit this and https://reviews.llvm.org/D72446.

clang/unittests/Tooling/Syntax/TreeTest.cpp

738

Example:

template <class T>
struct X {

template <class U>
U foo();

};

template <class T>
template <class U>
U X<T>::foo() {}

Discussed offline, RAV doesn't visit TemplateParameters and therefore we're not creating a node for the first template parameter (in bold). We could overcome this in the BuildTree.cpp, but more principled solution would be to teach RAV to visit TemplateParameters. In a separate patch.

[gribozavr2]

Superseded by https://reviews.llvm.org/D76346.

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 (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) {
+      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