[clang-diff] Support templates

[johannes]

Summary

TemplateName and TemplateArgument are now treated as nodes.

[arphaman]

lib/Tooling/ASTDiff/ASTDiff.cpp

299

Interesting, I didn't know that this iteration happened out-of-order. My https://reviews.llvm.org/D35012 patch (I'll commit it right now) has a RecursiveASTVisitor subclass that tries to traverse the tree in the source order, I think you should move this code:

DEF_TRAVERSE_TMPL_DECL_(Class)
DEF_TRAVERSE_TMPL_DECL_(Var)
DEF_TRAVERSE_TMPL_DECL_(Function)

to LexicallyOrderedRecursiveASTVisitor subclass instead and change your visitor to derive from LexicallyOrderedRecursiveASTVisitor. You can probably repurpose https://reviews.llvm.org/D36998 and have both the visibility change and the move to LexicallyOrderedRecursiveASTVisitor in that patch.

[johannes]

use LexicallyOrderedRecursiveASTVisitor

[johannes]

update

lib/Tooling/ASTDiff/ASTDiff.cpp

public:
   ASTUnit *
   PrintingPolicy TypePP;
   /// Nodes in preorder.
   std::vector<Node> Nodes;
   std::vector<NodeId> Leaves;
   // Maps preorder indices to postorder ones.
   std::vector<int> PostorderIds;
   std::vector<NodeId> NodesBfs;
+  std::map<NodeId, SourceRange> TemplateArgumentLocations;
 
   int getSize() const { return Nodes.size(); }
   NodeId getRootId() const { return 0; }
   PreorderIterator begin() const { return getRootId(); }
   PreorderIterator end() const { return getSize(); }
 
   const Node &getNode(NodeId Id) const { return Nodes[Id]; }
   Node &getMutableNode(NodeId Id) { return Nodes[Id]; }
private:
   void setLeftMostDescendants();
 };
 
 static bool isSpecializedNodeExcluded(const Decl *D) { return D->isImplicit(); }
 static bool isSpecializedNodeExcluded(const Stmt *S) { return false; }
 static bool isSpecializedNodeExcluded(CXXCtorInitializer *I) {
   return !I->isWritten();
 }
+static bool isSpecializedNodeExcluded(const TemplateArgumentLoc *S) {
+  return false;
+}
+
+static bool isNodeExcluded(ASTUnit &AST, TemplateName *Template) {
+  // TODO what if it is from another file
+  return false;
+}
 
 template <class T> static bool isNodeExcluded(ASTUnit &AST, T *N) {
   const SourceManager &SrcMgr = AST.getSourceManager();
   if (!N)
     return true;
   SourceLocation SLoc = N->getSourceRange().getBegin();
   if (SLoc.isValid()) {
     // Ignore everything from other files.
     if (!SrcMgr.isInMainFile(SLoc))
       return true;
     const Preprocessor &PP = AST.getPreprocessor();
     if (SLoc.isMacroID() && !PP.isAtStartOfMacroExpansion(SLoc))
       return true;
   }
   return isSpecializedNodeExcluded(N);
 }
 
-static SourceRange getSourceRange(const ASTUnit &AST, const DynTypedNode &DTN) {
+static SourceRange getSourceExtent(const ASTUnit &AST, SourceRange Range) {
   const SourceManager &SrcMgr = AST.getSourceManager();
-  SourceRange Range = DTN.getSourceRange();
   SourceLocation BeginLoc = Range.getBegin();
   SourceLocation EndLoc;
   if (BeginLoc.isMacroID())
     EndLoc = SrcMgr.getExpansionRange(BeginLoc).second;
   else
     EndLoc = Range.getEnd();
   EndLoc = Lexer::getLocForEndOfToken(EndLoc, /*Offset=*/0, SrcMgr,
                                       AST.getLangOpts());
-  if (auto *ThisExpr = DTN.get<CXXThisExpr>()) {
-    if (ThisExpr->isImplicit())
-      EndLoc = BeginLoc;
-  }
   return {SrcMgr.getExpansionLoc(BeginLoc), SrcMgr.getExpansionLoc(EndLoc)};
 }
 
 namespace {
 // Sets Height, Parent and Children for each node.
 struct PreorderVisitor : public RecursiveASTVisitor<PreorderVisitor> {
   int Id = 0, Depth = 0;
   NodeId Parent;
   SyntaxTree::Impl &Tree;
 
   PreorderVisitor(SyntaxTree::Impl &Tree) : Tree(Tree) {}
 
-  template <class T> std::tuple<NodeId, NodeId> PreTraverse(T *ASTNode) {
+  template <class T> std::tuple<NodeId, NodeId> PreTraverse(const T &ASTNode) {
     NodeId MyId = Id;
     Tree.Nodes.emplace_back();
     Node &N = Tree.getMutableNode(MyId);
     N.Parent = Parent;
     N.Depth = Depth;
-    N.ASTNode = DynTypedNode::create(*ASTNode);
+    N.ASTNode = DynTypedNode::create(ASTNode);
     assert(!N.ASTNode.getNodeKind().isNone() &&
            "Expected nodes to have a valid kind.");
     if (Parent.isValid()) {
       Node &P = Tree.getMutableNode(Parent);
       P.Children.push_back(MyId);
     }
     Parent = MyId;
     ++Id;
if (N.isLeaf())
       Tree.Leaves.push_back(MyId);
     N.Height = 1;
     for (NodeId Child : N.Children)
       N.Height = std::max(N.Height, 1 + Tree.getNode(Child).Height);
   }
   bool TraverseDecl(Decl *D) {
     if (isNodeExcluded(Tree.AST, D))
       return true;
-    auto SavedState = PreTraverse(D);
+    auto SavedState = PreTraverse(*D);
     RecursiveASTVisitor<PreorderVisitor>::TraverseDecl(D);
     PostTraverse(SavedState);
     return true;
   }
   bool TraverseStmt(Stmt *S) {
     if (S)
       S = S->IgnoreImplicit();
     if (isNodeExcluded(Tree.AST, S))
       return true;
-    auto SavedState = PreTraverse(S);
+    auto SavedState = PreTraverse(*S);
     RecursiveASTVisitor<PreorderVisitor>::TraverseStmt(S);
     PostTraverse(SavedState);
     return true;
   }
   bool TraverseType(QualType T) { return true; }
   bool TraverseConstructorInitializer(CXXCtorInitializer *Init) {
     if (isNodeExcluded(Tree.AST, Init))
       return true;
-    auto SavedState = PreTraverse(Init);
+    auto SavedState = PreTraverse(*Init);
     RecursiveASTVisitor<PreorderVisitor>::TraverseConstructorInitializer(Init);
     PostTraverse(SavedState);
     return true;
   }
+// We want nodes to be in the same order as in the source code.
+// So we traverse template parameters before the remainder of the declaration.
+#define DEF_TRAVERSE_TMPL_DECL_(TMPLDECLKIND)                                  \
+  bool Traverse##TMPLDECLKIND##TemplateDecl(TMPLDECLKIND##TemplateDecl *TD) {  \
+    /* No need to check return value, always true. */                          \
+    TraverseTemplateParameterListHelper(TD->getTemplateParameters());          \
+    TraverseDecl(TD->getTemplatedDecl());                                      \
+    return true;                                                               \
+  }
+  DEF_TRAVERSE_TMPL_DECL_(Class)
+  DEF_TRAVERSE_TMPL_DECL_(Var)
+  DEF_TRAVERSE_TMPL_DECL_(Function)
+#undef DEF_TRAVERSE_TMPL_DECL_
+  bool TraverseTemplateArgumentLoc(const TemplateArgumentLoc &ArgLoc) {
+    if (isNodeExcluded(Tree.AST, &ArgLoc))
+      return true;
+    Tree.TemplateArgumentLocations.emplace(Id, ArgLoc.getSourceRange());
+    auto SavedState = PreTraverse(ArgLoc.getArgument());
+    RecursiveASTVisitor<PreorderVisitor>::TraverseTemplateArgumentLoc(ArgLoc);
+    PostTraverse(SavedState);
+    return true;
+  }
+  bool TraverseTemplateName(TemplateName Template) {
+    if (isNodeExcluded(Tree.AST, &Template))
+      return true;
+    auto SavedState = PreTraverse(Template);
+    RecursiveASTVisitor<PreorderVisitor>::TraverseTemplateName(Template);
+    PostTraverse(SavedState);
+    return true;
+  }
 };
 } // end anonymous namespace
 
 SyntaxTree::Impl::Impl(SyntaxTree *Parent, ASTUnit &AST)
     : Parent(Parent), AST(AST), TypePP(AST.getLangOpts()) {
   TypePP.AnonymousTagLocations = false;
 }
 
if (Init->isAnyMemberInitializer())
     return Init->getAnyMember()->getName();
   if (Init->isBaseInitializer())
     return QualType(Init->getBaseClass(), 0).getAsString(TypePP);
   if (Init->isDelegatingInitializer())
     return Init->getTypeSourceInfo()->getType().getAsString(TypePP);
   llvm_unreachable("Unknown initializer type");
 }
 
+template <class T> static std::string dumpToString(const T &Object) {
+  std::string Str;
+  llvm::raw_string_ostream OS(Str);
+  Object.dump(OS);
+  return OS.str();
+}
+
 std::string SyntaxTree::Impl::getNodeValue(NodeId Id) const {
   return getNodeValue(getNode(Id));
 }
 
 std::string SyntaxTree::Impl::getNodeValue(const Node &N) const {
   const DynTypedNode &DTN = N.ASTNode;
   if (N.isMacro()) {
-    CharSourceRange Range(getSourceRange(AST, N.ASTNode), false);
+    CharSourceRange Range(getSourceExtent(AST, N.ASTNode.getSourceRange()),
+                          false);
     return Lexer::getSourceText(Range, AST.getSourceManager(),
                                 AST.getLangOpts());
   }
   if (auto *S = DTN.get<Stmt>())
     return getStmtValue(S);
   if (auto *D = DTN.get<Decl>())
     return getDeclValue(D);
   if (auto *Init = DTN.get<CXXCtorInitializer>())
     return getInitializerValue(Init, TypePP);
-  llvm_unreachable("Fatal: unhandled AST node.\n");
+  if (auto *Template = DTN.get<TemplateName>())
+    return dumpToString(*Template);
+  if (auto *Arg = DTN.get<TemplateArgument>())
+    return dumpToString(*Arg);
+  llvm_unreachable("getNodeValue: unhandled AST node.\n");
 }
 
 std::string SyntaxTree::Impl::getDeclValue(const Decl *D) const {
   std::string Value;
   if (auto *V = dyn_cast<ValueDecl>(D))
     return getRelativeName(V) + "(" + V->getType().getAsString(TypePP) + ")";
   if (auto *N = dyn_cast<NamedDecl>(D))
     Value += getRelativeName(N) + ";";
DataCollector(const DynTypedNode &DTN, const SyntaxTree::Impl &Tree,
       : Tree(Tree), Context(Tree.AST.getASTContext()),
         DataConsumer(DataConsumer) {
     if (auto *S = DTN.get<Stmt>())
       ConstStmtVisitor<DataCollector>::Visit(S);
     else if (auto *D = DTN.get<Decl>())
       ConstDeclVisitor<DataCollector>::Visit(D);
     else if (auto *Init = DTN.get<CXXCtorInitializer>())
       addData(getInitializerValue(Init, Tree.TypePP));
+    else if (auto *Template = DTN.get<TemplateName>())
+      addData(dumpToString(*Template));
+    else if (auto *Arg = DTN.get<TemplateArgument>())
+      addData(dumpToString(*Arg));
     else
-      llvm_unreachable("Fatal: unhandled AST node.\n");
+      llvm_unreachable("DataConsumer: unhandled AST node.\n");
   }
 
 #define DEF_ADD_DATA(CLASS, CODE)                                              \
   template <class Dummy = void> Dummy Visit##CLASS(const CLASS *D) {           \
     CODE;                                                                      \
     ConstDeclVisitor<DataCollector>::Visit##CLASS(D);                          \
   }
 

 static HashType hashString(StringRef Str) {
   ArrayRef<uint8_t> Data((const uint8_t *)Str.data(), Str.size());
   return llvm::MD5::hash(Data);
 }
 
 HashType SyntaxTree::Impl::hashNode(const Node &N) const {
   const DynTypedNode &DTN = N.ASTNode;
   if (N.isMacro()) {
-    CharSourceRange Range(getSourceRange(AST, N.ASTNode), false);
+    CharSourceRange Range(getSourceExtent(AST, N.ASTNode.getSourceRange()),
+                          false);
     return hashString(
         Lexer::getSourceText(Range, AST.getSourceManager(), AST.getLangOpts()));
   }
   llvm::MD5 Hash;
   DataCollector(DTN, *this, Hash);
   llvm::MD5::MD5Result HashResult;
   Hash.final(HashResult);
   return HashResult;

 
 int SyntaxTree::findPositionInParent(NodeId Id) const {
   return TreeImpl->findPositionInParent(Id);
 }
 
 std::pair<unsigned, unsigned>
 SyntaxTree::getSourceRangeOffsets(const Node &N) const {
   const SourceManager &SrcMgr = TreeImpl->AST.getSourceManager();
-  SourceRange Range = getSourceRange(TreeImpl->AST, N.ASTNode);
+  SourceRange Range;
+  if (auto *Arg = N.ASTNode.get<TemplateArgument>())
+    Range = TreeImpl->TemplateArgumentLocations.at(&N - &TreeImpl->Nodes[0]);
+  else {
+    Range = N.ASTNode.getSourceRange();
+    if (auto *ThisExpr = N.ASTNode.get<CXXThisExpr>())
+      if (ThisExpr->isImplicit())
+        Range.setEnd(Range.getBegin());
+  }
+  Range = getSourceExtent(TreeImpl->AST, Range);
   unsigned Begin = SrcMgr.getFileOffset(Range.getBegin());
   unsigned End = SrcMgr.getFileOffset(Range.getEnd());
   return {Begin, End};
 }
 
 std::string SyntaxTree::getNodeValue(NodeId Id) const {
   return TreeImpl->getNodeValue(Id);
 }
 
 std::string SyntaxTree::getNodeValue(const Node &N) const {
   return TreeImpl->getNodeValue(N);
 }
 
 } // end namespace diff
 } // end namespace clang

test/Tooling/Inputs/clang-diff-basic-src.cpp

 #define M2 return 1 + 2
 #define F(a, b) return a + b;
 
 int f2() {
   M1;
   M1;
   F(1, 1);
 }
+
+template <class T, class U = void>
+U visit(T &t) {
+  int x = t;
+  return U();
+}
+
+void tmp() {
+  int x;
+  visit<int>(x);
+}
+
+int x = 1;

test/Tooling/clang-diff-ast.cpp

 // CHECK-NEXT: NamespaceDecl
 namespace world {
 // nodes from other files are excluded, there should be no output here
 #include "clang-diff-ast.cpp"
 }
 // CHECK-NEXT: FunctionDecl: sentinel
 void sentinel();
 #endif
+
+// CHECK-NEXT: ClassTemplateDecl: C
+// CHECK-NEXT: TemplateTypeParmDecl
+// CHECK-NEXT: CXXRecordDecl
+template <class T> class C {
+  // CHECK-NEXT: FieldDecl
+  T t;
+};
+
+// CHECK-NEXT: CXXRecordDecl
+// CHECK-NEXT: TemplateName
+// CHECK-NEXT: TemplateArgument
+class I : C<int> {};

test/Tooling/clang-diff-basic.cpp

-// RUN: clang-diff -dump-matches %S/Inputs/clang-diff-basic-src.cpp %s -- | FileCheck %s
+// RUN: clang-diff -dump-matches %S/Inputs/clang-diff-basic-src.cpp %s -- -std=c++11 | FileCheck %s
 
 // CHECK: Match TranslationUnitDecl{{.*}} to TranslationUnitDecl
 // CHECK: Match NamespaceDecl: src{{.*}} to NamespaceDecl: dst
 namespace dst {
 // CHECK-NOT: Match NamespaceDecl: src{{.*}} to NamespaceDecl: inner
 namespace inner {
 void foo() {
   // CHECK: Match IntegerLiteral: 321{{.*}} to IntegerLiteral: 322
int f2() {
   // CHECK: Match Macro: M1{{.*}} to Macro: M1
   M1;
   // CHECK: Update Macro: M1{{.*}} to M2
   M2;
   // CHECK: Update Macro: F(1, 1){{.*}} to F(1, /*b=*/1)
   F(1, /*b=*/1);
 }
 
+// CHECK: Update TemplateTypeParmDecl: T{{.*}} to Type
+template <class Type, class U = int>
+U visit(Type &t) {
+  int x = t;
+  return U();
+}
+
+void tmp() {
+  long x;
+  // CHECK: Update TemplateArgument: int{{.*}} to long
+  visit<long>(x);
+}
+
 // CHECK: Delete AccessSpecDecl: public
 // CHECK: Delete CXXMethodDecl

test/Tooling/clang-diff-html.test

-// RUN: clang-diff -html %S/Inputs/clang-diff-basic-src.cpp %S/clang-diff-basic.cpp -- | FileCheck %s
+// RUN: clang-diff -html %S/Inputs/clang-diff-basic-src.cpp %S/clang-diff-basic.cpp -- -std=c++11 | FileCheck %s
 
 // CHECK: <pre><div id='L' class='code'><span id='L0' tid='R0' title='TranslationUnitDecl
 // CHECK-NEXT: 0 -> 0'>
 
 // match, update
 // CHECK: <span id='L[[L:[0-9]+]]' tid='R[[R:[0-9]+]]' title='NamespaceDecl
 // CHECK-NEXT: [[L]] -> [[R]]
 // CHECK-NEXT: src;' class='u'>namespace src {