Index: lib/Tooling/ASTDiff/ASTDiff.cpp
===================================================================
--- lib/Tooling/ASTDiff/ASTDiff.cpp
+++ lib/Tooling/ASTDiff/ASTDiff.cpp
@@ -13,9 +13,13 @@
 
 #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>
@@ -116,9 +120,12 @@
   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);
@@ -135,6 +142,7 @@
 
   SyntaxTree *Parent;
   ASTUnit &AST;
+  PrintingPolicy TypePP;
   /// Nodes in preorder.
   std::vector<Node> Nodes;
   std::vector<NodeId> Leaves;
@@ -164,6 +172,10 @@
   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();
@@ -272,15 +284,20 @@
 };
 } // 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();
@@ -422,9 +439,6 @@
 
 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)) {
@@ -490,6 +504,92 @@
   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;
@@ -536,6 +636,9 @@
   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));
   }
@@ -665,7 +768,7 @@
   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() {
@@ -796,8 +899,7 @@
   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]))
@@ -857,7 +959,7 @@
   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;
@@ -1045,9 +1147,8 @@
             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);
-    }
   }
 }