[clang-diff] Use data collectors for node comparison

[arphaman]

Can you remove getNodeValue now or do you still need it?

[johannes]

In D37001#852442, @arphaman wrote:

Can you remove getNodeValue now or do you still need it?

It is only used in the client, I think it makes sense to move it there, or to remove it altogether.
I think I'd keep it in the client for now, to disambiguate things with different names in the tests.

[arphaman]

lib/Tooling/ASTDiff/ASTDiff.cpp

537

I didn't realize that you're including files from within lib. That's not ideal. You should add a pre-commit that moves the *.inc files over to include/AST (and marks them as textual in Clang's module.modulemap). Then you should include them using the clang/AST path.

[johannes]

lib/Tooling/ASTDiff/ASTDiff.cpp

537

I tried moving StmtDataCollectors.inc to and adding
+ textual header "AST/StmtDataCollectors.inc"
in the modulemap, then I get some CMake errors, not sure why.

It might make sense to tablegen it like the other .inc files.

[johannes]

use raw source code of owned tokens instead

lib/Tooling/ASTDiff/ASTDiff.cpp

 //===- ASTDiff.cpp - AST differencing implementation-----------*- C++ -*- -===//
 //
 //                     The LLVM Compiler Infrastructure
 //
 // This file is distributed under the University of Illinois Open Source
 // License. See LICENSE.TXT for details.
 //
 //===----------------------------------------------------------------------===//
 //
 // This file contains definitons for the AST differencing interface.
 //
 //===----------------------------------------------------------------------===//
 
 #include "clang/Tooling/ASTDiff/ASTDiff.h"
 
+#include "clang/AST/DataCollection.h"
+#include "clang/AST/DeclVisitor.h"
 #include "clang/AST/RecursiveASTVisitor.h"
+#include "clang/AST/StmtVisitor.h"
 #include "clang/Lex/Lexer.h"
 #include "llvm/ADT/PriorityQueue.h"
+#include "llvm/Support/MD5.h"
 
 #include <limits>
 #include <memory>
 #include <unordered_set>
 
 using namespace llvm;
 using namespace clang;
 
private:
   // Matches nodes, whose parents are matched.
   void matchChildren(Mapping &M);
 
   const ComparisonOptions &Options;
 
   friend class ZhangShashaMatcher;
 };
 
+using HashType = std::array<uint8_t, 16>;
+
 /// Represents the AST of a TranslationUnit.
 class SyntaxTree::Impl {
 public:
+  Impl(SyntaxTree *Parent, ASTUnit &AST);
   /// Constructs a tree from an AST node.
   Impl(SyntaxTree *Parent, Decl *N, ASTUnit &AST);
   Impl(SyntaxTree *Parent, Stmt *N, ASTUnit &AST);
   template <class T>
   Impl(SyntaxTree *Parent,
        typename std::enable_if<std::is_base_of<Stmt, T>::value, T>::type *Node,
        ASTUnit &AST)
       : Impl(Parent, dyn_cast<Stmt>(Node), AST) {}
   template <class T>
   Impl(SyntaxTree *Parent,
        typename std::enable_if<std::is_base_of<Decl, T>::value, T>::type *Node,
        ASTUnit &AST)
       : Impl(Parent, dyn_cast<Decl>(Node), AST) {}
 
   SyntaxTree *Parent;
   ASTUnit &AST;
+  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;
 
   int getSize() const { return Nodes.size(); }
std::string getRelativeName(const NamedDecl *ND,
                               const DeclContext *Context) const;
   std::string getRelativeName(const NamedDecl *ND) const;
 
   std::string getNodeValue(NodeId Id) const;
   std::string getNodeValue(const Node &Node) const;
   std::string getDeclValue(const Decl *D) const;
   std::string getStmtValue(const Stmt *S) const;
 
+  HashType hashNode(const Node &N) const;
+  HashType hashStmt(const Stmt *S) const;
+  HashType hashDecl(const Decl *D) const;
+
 private:
   void initTree();
   void setLeftMostDescendants();
 };
 
 static bool isSpecializedNodeExcluded(const Decl *D) { return D->isImplicit(); }
 static bool isSpecializedNodeExcluded(const Stmt *S) { return false; }
 
bool TraverseStmt(Stmt *S) {
     RecursiveASTVisitor<PreorderVisitor>::TraverseStmt(S);
     PostTraverse(SavedState);
     return true;
   }
   bool TraverseType(QualType T) { return true; }
 };
 } // end anonymous namespace
 
+SyntaxTree::Impl::Impl(SyntaxTree *Parent, ASTUnit &AST)
+    : Parent(Parent), AST(AST), TypePP(AST.getLangOpts()) {
+  TypePP.AnonymousTagLocations = false;
+}
+
 SyntaxTree::Impl::Impl(SyntaxTree *Parent, Decl *N, ASTUnit &AST)
-    : Parent(Parent), AST(AST) {
+    : Impl(Parent, AST) {
   PreorderVisitor PreorderWalker(*this);
   PreorderWalker.TraverseDecl(N);
   initTree();
 }
 
 SyntaxTree::Impl::Impl(SyntaxTree *Parent, Stmt *N, ASTUnit &AST)
-    : Parent(Parent), AST(AST) {
+    : Impl(Parent, AST) {
   PreorderVisitor PreorderWalker(*this);
   PreorderWalker.TraverseStmt(N);
   initTree();
 }
 
 static std::vector<NodeId> getSubtreePostorder(const SyntaxTree::Impl &Tree,
                                                NodeId Root) {
   std::vector<NodeId> Postorder;
if (auto *S = DTN.get<Stmt>())
     return getStmtValue(S);
   if (auto *D = DTN.get<Decl>())
     return getDeclValue(D);
   llvm_unreachable("Fatal: unhandled AST node.\n");
 }
 
 std::string SyntaxTree::Impl::getDeclValue(const Decl *D) const {
   std::string Value;
-  PrintingPolicy TypePP(AST.getLangOpts());
-  TypePP.AnonymousTagLocations = false;
-
   if (auto *V = dyn_cast<ValueDecl>(D)) {
     Value += getRelativeName(V) + "(" + V->getType().getAsString(TypePP) + ")";
     if (auto *C = dyn_cast<CXXConstructorDecl>(D)) {
       for (auto *Init : C->inits()) {
         if (!Init->isWritten())
           continue;
         if (Init->isBaseInitializer()) {
           Value += Init->getBaseClass()->getCanonicalTypeInternal().getAsString(
if (auto *D = dyn_cast<DeclRefExpr>(S))
     return getRelativeName(D->getDecl(), getEnclosingDeclContext(AST, S));
   if (auto *String = dyn_cast<StringLiteral>(S))
     return String->getString();
   if (auto *B = dyn_cast<CXXBoolLiteralExpr>(S))
     return B->getValue() ? "true" : "false";
   return "";
 }
 
+class DataCollector : public ConstDeclVisitor<DataCollector>,
+                      public ConstStmtVisitor<DataCollector> {
+  const SyntaxTree::Impl &Tree;
+  ASTContext &Context;
+  llvm::MD5 &DataConsumer;
+
+  void addData(const QualType &QT) { addData(QT.getAsString(Tree.TypePP)); }
+  template <class T> void addData(T Data) {
+    data_collection::addDataToConsumer(DataConsumer, Data);
+  }
+
+public:
+  DataCollector(const DynTypedNode &DTN, const SyntaxTree::Impl &Tree,
+                llvm::MD5 &DataConsumer)
+      : 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
+      llvm_unreachable("Fatal: 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);                          \
+  }
+
+#include "../../AST/DeclDataCollectors.inc"
+
+#define DEF_ADD_DATA(CLASS, CODE)                                              \
+  void Visit##CLASS(const CLASS *D) {                                          \
+    CODE;                                                                      \
+    ConstDeclVisitor<DataCollector>::Visit##CLASS(D);                          \
+  }
+
+  DEF_ADD_DATA(NamedDecl, { addData(Tree.getRelativeName(D)); })
+#undef DEF_ADD_DATA
+
+#define DEF_ADD_DATA(CLASS, CODE)                                              \
+  template <class Dummy = void> Dummy Visit##CLASS(const CLASS *S) {           \
+    CODE;                                                                      \
+    ConstStmtVisitor<DataCollector>::Visit##CLASS(S);                          \
+  }
+
+#include "../../AST/StmtDataCollectors.inc"
+
+#define DEF_ADD_DATA(CLASS, CODE)                                              \
+  void Visit##CLASS(const CLASS *S) {                                          \
+    CODE;                                                                      \
+    ConstStmtVisitor<DataCollector>::Visit##CLASS(S);                          \
+  }
+
+  // ignore differences of type, because they are not local
+  DEF_ADD_DATA(Expr, {})
+  DEF_ADD_DATA(DeclRefExpr, {
+    addData(Tree.getRelativeName(S->getDecl(),
+                                 getEnclosingDeclContext(Tree.AST, S)));
+  })
+  // For CallExpr nodes, all information is included in its children
+  DEF_ADD_DATA(CallExpr, {})
+
+#undef DEF_ADD_DATA
+};
+
+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);
+    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;
+}
+
 /// Identifies a node in a subtree by its postorder offset, starting at 1.
 struct SNodeId {
   int Id = 0;
 
   explicit SNodeId(int Id) : Id(Id) {}
   explicit SNodeId() = default;
 
   operator int() const { return Id; }
public:
   SNodeId getLeftMostDescendant(SNodeId Id) const {
     assert(Id > 0 && Id <= getSize() && "Invalid subtree node index.");
     return LeftMostDescendants[Id - 1];
   }
   /// Returns the postorder index of the leftmost descendant in the subtree.
   NodeId getPostorderOffset() const {
     return Tree.PostorderIds[getIdInRoot(SNodeId(1))];
   }
+  HashType hashNode(SNodeId Id) const {
+    return Tree.hashNode(Tree.getNode(getIdInRoot(Id)));
+  }
   std::string getNodeValue(SNodeId Id) const {
     return Tree.getNodeValue(getIdInRoot(Id));
   }
 
 private:
   /// Returns the number of leafs in the subtree.
   int setLeftMostDescendants() {
     int NumLeaves = 0;
private:
   /// The values range between 0 and 1, or infinity if this edit action should
   /// always be avoided.
   static constexpr double DeletionCost = 1;
   static constexpr double InsertionCost = 1;
 
   double getUpdateCost(SNodeId Id1, SNodeId Id2) {
     if (!DiffImpl.isMatchingPossible(S1.getIdInRoot(Id1), S2.getIdInRoot(Id2)))
       return std::numeric_limits<double>::max();
-    return S1.getNodeValue(Id1) != S2.getNodeValue(Id2);
+    return S1.hashNode(Id1) != S2.hashNode(Id2);
   }
 
   void computeTreeDist() {
     for (SNodeId Id1 : S1.KeyRoots)
       for (SNodeId Id2 : S2.KeyRoots)
         computeForestDist(Id1, Id2);
   }
 
public:
   }
 };
 } // end anonymous namespace
 
 bool ASTDiff::Impl::identical(NodeId Id1, NodeId Id2) const {
   const Node &N1 = T1.getNode(Id1);
   const Node &N2 = T2.getNode(Id2);
   if (N1.Children.size() != N2.Children.size() ||
-      !isMatchingPossible(Id1, Id2) ||
-      T1.getNodeValue(Id1) != T2.getNodeValue(Id2))
+      !isMatchingPossible(Id1, Id2) || T1.hashNode(N1) != T2.hashNode(N2))
     return false;
   for (size_t Id = 0, E = N1.Children.size(); Id < E; ++Id)
     if (!identical(N1.Children[Id], N2.Children[Id]))
       return false;
   return true;
 }
 
 bool ASTDiff::Impl::isMatchingPossible(NodeId Id1, NodeId Id2) const {

 }
 
 double ASTDiff::Impl::getNodeSimilarity(const Mapping &M, NodeId Id1,
                                         NodeId Id2) const {
   const Node &N1 = T1.getNode(Id1);
   const Node &N2 = T2.getNode(Id2);
   auto Ident1 = N1.getIdentifier(), Ident2 = N2.getIdentifier();
 
-  bool SameValue = T1.getNodeValue(Id1) == T2.getNodeValue(Id2);
+  bool SameValue = T1.hashNode(N1) == T2.hashNode(N2);
   auto SameIdent = Ident1 && Ident2 && *Ident1 == *Ident2;
 
   double NodeSimilarity = 0;
   NodeSimilarity += SameValue;
   NodeSimilarity += SameIdent;
 
   assert(haveSameParents(M, Id1, Id2));
   return NodeSimilarity * Options.MinSimilarity;
for (NodeId Id2 : T2.NodesBfs) {
     Node &N2 = T2.getMutableNode(Id2);
     if (Id1.isInvalid())
       continue;
     if (!haveSameParents(M, Id1, Id2) ||
         T1.findPositionInParent(Id1, true) !=
             T2.findPositionInParent(Id2, true)) {
       N1.Change = N2.Change = Move;
     }
-    if (T1.getNodeValue(Id1) != T2.getNodeValue(Id2)) {
+    if (T1.hashNode(N1) != T2.hashNode(N2))
       N1.Change = N2.Change = (N1.Change == Move ? UpdateMove : Update);
-    }
-  }
-}
 
 ASTDiff::ASTDiff(SyntaxTree &T1, SyntaxTree &T2,
                  const ComparisonOptions &Options)
     : DiffImpl(llvm::make_unique<Impl>(*T1.TreeImpl, *T2.TreeImpl, Options)) {}
 
 ASTDiff::~ASTDiff() = default;
 
 NodeId ASTDiff::getMapped(const SyntaxTree &SourceTree, NodeId Id) const {