[clang-diff] improve mapping accuracy

[arphaman]

Can you provide a test that demonstrates what this change fixed/improved?

include/clang/Tooling/ASTDiff/ASTDiffInternal.h

53

If I understand correctly this comment matches the same method in MultiMapping. Will you ever implement this method in Mapping though? I don't think you need such a comment if you don't intend to have this method in the Mapping class.

[johannes]

In D34748#802037, @arphaman wrote:

Can you provide a test that demonstrates what this change fixed/improved?

My bad, it looks like this does not improve anything yet. In order to do so I will use additional heuristics for similarity, like in the reference implementation.

[arphaman]

Some comments:

• I had to make a couple of post-commit fixes to appease the buildbots when I committed your first patch, so it looks like this one doesn't apply cleanly anymore. Can you please rebase it?
• Let's separate the addition of HTML output and the improvements to the algorithm in two patches. I would recommend that you leave the algorithm improvements in this one and post a follow-up patch that has HTML output (with a HTML output test).
• I won't be able to accept a change like this without tests. Did you monitor the changes in the HTML output while your worked on improvements to the algorithm? Please try and base the tests on those changes and improvements.

lib/Tooling/ASTDiff/ASTDiff.cpp

818

What are these magic constants? Please describe them in comments and factor out to appropriately named const variables if needed.

[arphaman]

In general this patch is too big, and combines a lot of changes that could be separated using multiple patches. I've suggested one pre-commit and a new patch so far, but more changes might be required once I see the updated patch.

include/clang/Tooling/ASTDiff/ASTDiff.h

48

Redundant const in the return type.

49

Redundant const in the return type.

58

Please Move these fields to the end of the class. Can they be private too?

lib/Tooling/ASTDiff/ASTDiff.cpp

170

How will you deal with changes in headers if you limit analysis to main files only?

694

Redundant const in return type.

tools/clang-diff/ClangDiff.cpp

28

The rename of DumpAST to ASTDump should be a separate change. Please pre-commit this rename and remove it from the updated patch.

45

Can you avoid moving the NoCompilationDatabase? This will make the patch clearer.

65

This is a copy ArgumentsAdjustingCompilations from lib/Tooling. You should create a patch that moves existing ArgumentsAdjustingCompilations from the implementation file to some header so that it will be accessible by the tool and make this patch depend on the new patch.

224

You might want to assert here. We should never have Delete in the destination AST, right?

[johannes]

split up in several commits starting from https://reviews.llvm.org/D36176

lib/Tooling/ASTDiff/ASTDiff.cpp

170

I will change this to support headers in another patch

include/clang/Tooling/ASTDiff/ASTDiff.h

 #ifndef LLVM_CLANG_TOOLING_ASTDIFF_ASTDIFF_H
 #define LLVM_CLANG_TOOLING_ASTDIFF_ASTDIFF_H
 
 #include "clang/Tooling/ASTDiff/ASTDiffInternal.h"
 
 namespace clang {
 namespace diff {
 
-class SyntaxTree;
+enum ChangeKind {
+  None,
+  Delete,    // (Src): delete node Src.
+  Update,    // (Src, Dst): update the value of node Src to match Dst.
+  Insert,    // (Src, Dst, Pos): insert Src as child of Dst at offset Pos.
+  Move,      // (Src, Dst, Pos): move Src to be a child of Dst at offset Pos.
+  UpdateMove // Same as Move plus Update.
+};
+
+/// Represents a Clang AST node, alongside some additional information.
+struct Node {
+  NodeId Parent, LeftMostDescendant, RightMostDescendant;
+  int Depth, Height, Shift;
+  ast_type_traits::DynTypedNode ASTNode;
+  SmallVector<NodeId, 4> Children;
+  ChangeKind ChangeKind = None;
+
+  ast_type_traits::ASTNodeKind getType() const;
+  const StringRef getTypeLabel() const;
+  bool isLeaf() const { return Children.empty(); }
+  llvm::Optional<const std::string> getQualifiedIdentifier() const;
+  llvm::Optional<const StringRef> getIdentifier() const;
+};
 
 class ASTDiff {
 public:
-  ASTDiff(SyntaxTree &T1, SyntaxTree &T2, const ComparisonOptions &Options);
+  ASTDiff(SyntaxTree &SrcTree, SyntaxTree &DstTree,
+          const ComparisonOptions &Options);
   ~ASTDiff();
 
-  // Returns a list of matches.
-  std::vector<Match> getMatches();
-  /// Returns an edit script.
-  std::vector<Change> getChanges();
-
-  // Prints an edit action.
-  void printChange(raw_ostream &OS, const Change &Chg) const;
-  // Prints a match between two nodes.
-  void printMatch(raw_ostream &OS, const Match &M) const;
+  SyntaxTree &SrcTree, &DstTree;
 
-  class Impl;
+  // Returns the ID of the node that is mapped to the given node in SourceTree.
+  NodeId getMapped(const SyntaxTree &SourceTree, NodeId Id) const;
 
-private:
+  class Impl;
   std::unique_ptr<Impl> DiffImpl;
 };
 
 /// SyntaxTree objects represent subtrees of the AST.
 /// They can be constructed from any Decl or Stmt.
 class SyntaxTree {
 public:
   /// Constructs a tree from a translation unit.
-  SyntaxTree(const ASTContext &AST);
+  SyntaxTree(ASTContext &AST);
   /// Constructs a tree from any AST node.
   template <class T>
-  SyntaxTree(T *Node, const ASTContext &AST)
+  SyntaxTree(T *Node, ASTContext &AST)
       : TreeImpl(llvm::make_unique<SyntaxTreeImpl>(this, Node, AST)) {}
+  SyntaxTree(const SyntaxTree &Tree) = delete;
+  ~SyntaxTree();
+
+  ASTContext &getASTContext() const;
+  const StringRef getFilename() const;
+
+  int getSize() const;
+  NodeId getRootId() const;
+  using PreorderIterator = NodeId;
+  PreorderIterator begin() const;
+  PreorderIterator end() const;
+
+  const Node &getNode(NodeId Id) const;
+  int findPositionInParent(NodeId Id) const;
+
+  std::pair<unsigned, unsigned> getFileOffsets(const Node &N) const;
 
   /// Serialize the node attributes to a string representation. This should
   /// uniquely distinguish nodes of the same kind. Note that this function just
   /// returns a representation of the node value, not considering descendants.
-  std::string getNodeValue(const DynTypedNode &DTN) const;
+  std::string getNodeValue(NodeId Id);
+  std::string getNodeValue(const Node &Node);
 
-  void printAsJson(raw_ostream &OS);
+  const std::vector<NodeId> &getNodesBreadthFirst() const;
 
-  std::unique_ptr<SyntaxTreeImpl> TreeImpl;
+  class Impl;
+  std::unique_ptr<Impl> TreeImpl;
 };
 
 struct ComparisonOptions {
   /// During top-down matching, only consider nodes of at least this height.
   int MinHeight = 2;
 
   /// During bottom-up matching, match only nodes with at least this value as
   /// the ratio of their common descendants.
-  double MinSimilarity = 0.2;
+  double MinSimilarity = 0.5;
 
   /// Whenever two subtrees are matched in the bottom-up phase, the optimal
   /// mapping is computed, unless the size of either subtrees exceeds this.
   int MaxSize = 100;
 
-  /// If this is set to true, nodes that have parents that must not be matched
-  /// (see NodeComparison) will be allowed to be matched.
-  bool EnableMatchingWithUnmatchableParents = false;
-
   /// Returns false if the nodes should never be matched.
-  bool isMatchingAllowed(const DynTypedNode &N1, const DynTypedNode &N2) const {
-    return N1.getNodeKind().isSame(N2.getNodeKind());
-  }
-
-  /// Returns zero if the nodes are considered to be equal.  Returns a value
-  /// indicating the editing distance between the nodes otherwise.
-  /// There is no need to consider nodes that cannot be matched as input for
-  /// this function (see isMatchingAllowed).
-  double getNodeDistance(const SyntaxTree &T1, const DynTypedNode &N1,
-                         const SyntaxTree &T2, const DynTypedNode &N2) const {
-    if (T1.getNodeValue(N1) == T2.getNodeValue(N2))
-      return 0;
-    return 1;
+  bool isMatchingAllowed(const Node &N1, const Node &N2) const {
+    return N1.getType().isSame(N2.getType());
   }
 };
 
 } // end namespace diff
 } // end namespace clang
 
 #endif

include/clang/Tooling/ASTDiff/ASTDiffInternal.h

 //===- ASTDiffInternal.h --------------------------------------*- C++ -*- -===//
 //
 //
 //                     The LLVM Compiler Infrastructure
 //
 // This file is distributed under the University of Illinois Open Source
 // License. See LICENSE.TXT for details.
 //
 //===----------------------------------------------------------------------===//
 
 #ifndef LLVM_CLANG_TOOLING_ASTDIFF_ASTDIFFINTERNAL_H
 #define LLVM_CLANG_TOOLING_ASTDIFF_ASTDIFFINTERNAL_H
 
-#include <utility>
-
 #include "clang/AST/ASTTypeTraits.h"
 
 namespace clang {
 namespace diff {
 
-using DynTypedNode = ast_type_traits::DynTypedNode;
-
-struct ComparisonOptions;
 class SyntaxTree;
+class SyntaxTreeImpl;
+struct ComparisonOptions;
+
+using DynTypedNode = ast_type_traits::DynTypedNode;
 
 /// Within a tree, this identifies a node by its preorder offset.
 struct NodeId {
 private:
   static constexpr int InvalidNodeId = -1;
 
 public:
   int Id;
 
   NodeId() : Id(InvalidNodeId) {}
   NodeId(int Id) : Id(Id) {}
 
   operator int() const { return Id; }
   NodeId &operator++() { return ++Id, *this; }
   NodeId &operator--() { return --Id, *this; }
+  // Support defining iterators on NodeId.
+  NodeId &operator*() { return *this; }
 
   bool isValid() const { return Id != InvalidNodeId; }
   bool isInvalid() const { return Id == InvalidNodeId; }
 };
 
-/// This represents a match between two nodes in the source and destination
-/// trees, meaning that they are likely to be related.
-struct Match {
-  NodeId Src, Dst;
-};
-
-enum ChangeKind {
-  Delete, // (Src): delete node Src.
-  Update, // (Src, Dst): update the value of node Src to match Dst.
-  Insert, // (Src, Dst, Pos): insert Src as child of Dst at offset Pos.
-  Move    // (Src, Dst, Pos): move Src to be a child of Dst at offset Pos.
-};
-
-struct Change {
-  ChangeKind Kind;
-  NodeId Src, Dst;
-  size_t Position;
-
-  Change(ChangeKind Kind, NodeId Src, NodeId Dst, size_t Position)
-      : Kind(Kind), Src(Src), Dst(Dst), Position(Position) {}
-  Change(ChangeKind Kind, NodeId Src) : Kind(Kind), Src(Src) {}
-  Change(ChangeKind Kind, NodeId Src, NodeId Dst)
-      : Kind(Kind), Src(Src), Dst(Dst) {}
-};
-
-/// Represents a Clang AST node, alongside some additional information.
-struct Node {
-  NodeId Parent, LeftMostDescendant, RightMostDescendant;
-  int Depth, Height;
-  DynTypedNode ASTNode;
-  SmallVector<NodeId, 4> Children;
-
-  ast_type_traits::ASTNodeKind getType() const { return ASTNode.getNodeKind(); }
-  const StringRef getTypeLabel() const { return getType().asStringRef(); }
-  bool isLeaf() const { return Children.empty(); }
-};
-
-/// Maps nodes of the left tree to ones on the right, and vice versa.
-class Mapping {
-public:
-  Mapping() = default;
-  Mapping(Mapping &&Other) = default;
-  Mapping &operator=(Mapping &&Other) = default;
-  Mapping(int Size1, int Size2) {
-    // Maximum possible size after patching one tree.
-    int Size = Size1 + Size2;
-    SrcToDst = llvm::make_unique<SmallVector<NodeId, 2>[]>(Size);
-    DstToSrc = llvm::make_unique<SmallVector<NodeId, 2>[]>(Size);
-  }
-
-  void link(NodeId Src, NodeId Dst) {
-    SrcToDst[Src].push_back(Dst);
-    DstToSrc[Dst].push_back(Src);
-  }
-
-  NodeId getDst(NodeId Src) const {
-    if (hasSrc(Src))
-      return SrcToDst[Src][0];
-    return NodeId();
-  }
-  NodeId getSrc(NodeId Dst) const {
-    if (hasDst(Dst))
-      return DstToSrc[Dst][0];
-    return NodeId();
-  }
-  const SmallVector<NodeId, 2> &getAllDsts(NodeId Src) const {
-    return SrcToDst[Src];
-  }
-  const SmallVector<NodeId, 2> &getAllSrcs(NodeId Dst) const {
-    return DstToSrc[Dst];
-  }
-  bool hasSrc(NodeId Src) const { return !SrcToDst[Src].empty(); }
-  bool hasDst(NodeId Dst) const { return !DstToSrc[Dst].empty(); }
-  bool hasSrcDst(NodeId Src, NodeId Dst) const {
-    for (NodeId DstId : SrcToDst[Src])
-      if (DstId == Dst)
-        return true;
-    for (NodeId SrcId : DstToSrc[Dst])
-      if (SrcId == Src)
-        return true;
-    return false;
-  }
-
-private:
-  std::unique_ptr<SmallVector<NodeId, 2>[]> SrcToDst, DstToSrc;
-};
-
-/// Represents the AST of a TranslationUnit.
-class SyntaxTreeImpl {
-public:
-  /// Constructs a tree from the entire translation unit.
-  SyntaxTreeImpl(SyntaxTree *Parent, const ASTContext &AST);
-  /// Constructs a tree from an AST node.
-  SyntaxTreeImpl(SyntaxTree *Parent, Decl *N, const ASTContext &AST);
-  SyntaxTreeImpl(SyntaxTree *Parent, Stmt *N, const ASTContext &AST);
-  template <class T>
-  SyntaxTreeImpl(
-      SyntaxTree *Parent,
-      typename std::enable_if<std::is_base_of<Stmt, T>::value, T>::type *Node,
-      const ASTContext &AST)
-      : SyntaxTreeImpl(Parent, dyn_cast<Stmt>(Node), AST) {}
-  template <class T>
-  SyntaxTreeImpl(
-      SyntaxTree *Parent,
-      typename std::enable_if<std::is_base_of<Decl, T>::value, T>::type *Node,
-      const ASTContext &AST)
-      : SyntaxTreeImpl(Parent, dyn_cast<Decl>(Node), AST) {}
-
-  SyntaxTree *Parent;
-  const ASTContext &AST;
-  std::vector<NodeId> Leaves;
-  // Maps preorder indices to postorder ones.
-  std::vector<int> PostorderIds;
-
-  int getSize() const { return Nodes.size(); }
-  NodeId root() const { return 0; }
-
-  const Node &getNode(NodeId Id) const { return Nodes[Id]; }
-  Node &getMutableNode(NodeId Id) { return Nodes[Id]; }
-  bool isValidNodeId(NodeId Id) const { return Id >= 0 && Id < getSize(); }
-  void addNode(Node &N) { Nodes.push_back(N); }
-  int getNumberOfDescendants(NodeId Id) const;
-  bool isInSubtree(NodeId Id, NodeId SubtreeRoot) const;
-
-  std::string getNodeValueImpl(NodeId Id) const;
-  std::string getNodeValueImpl(const DynTypedNode &DTN) const;
-  /// Prints the node as "<type>[: <value>](<postorder-id)"
-  void printNode(NodeId Id) const { printNode(llvm::outs(), Id); }
-  void printNode(raw_ostream &OS, NodeId Id) const;
-
-  void printTree() const;
-  void printTree(NodeId Root) const;
-  void printTree(raw_ostream &OS, NodeId Root) const;
-
-  void printAsJsonImpl(raw_ostream &OS) const;
-  void printNodeAsJson(raw_ostream &OS, NodeId Id) const;
-
-private:
-  /// Nodes in preorder.
-  std::vector<Node> Nodes;
-
-  void initTree();
-  void setLeftMostDescendants();
-};
-
 } // end namespace diff
 } // end namespace clang
 #endif

lib/Tooling/ASTDiff/ASTDiff.cpp

 #include <unordered_set>
 
 using namespace llvm;
 using namespace clang;
 
 namespace clang {
 namespace diff {
 
+/// Maps nodes of the left tree to ones on the right, and vice versa.
+class Mapping {
+public:
+  Mapping() = default;
+  Mapping(Mapping &&Other) = default;
+  Mapping &operator=(Mapping &&Other) = default;
+  Mapping(size_t Size);
+
+  void link(NodeId Src, NodeId Dst);
+
+  NodeId getDst(NodeId Src) const;
+  NodeId getSrc(NodeId Dst) const;
+  bool hasSrc(NodeId Src) const;
+  bool hasDst(NodeId Dst) const;
+
+private:
+  std::unique_ptr<NodeId[]> SrcToDst, DstToSrc;
+};
+
 class ASTDiff::Impl {
 public:
-  SyntaxTreeImpl &T1, &T2;
-  bool IsMappingDone = false;
+  SyntaxTree::Impl &T1, &T2;
   Mapping TheMapping;
 
-  Impl(SyntaxTreeImpl &T1, SyntaxTreeImpl &T2, const ComparisonOptions &Options)
+  Impl(SyntaxTree::Impl &T1, SyntaxTree::Impl &T2,
+       const ComparisonOptions &Options)
       : T1(T1), T2(T2), Options(Options) {}
 
-  /// Matches nodes one-by-one based on their similarity.
+  // Matches nodes one-by-one based on their similarity.
   void computeMapping();
 
-  std::vector<Match> getMatches(Mapping &M);
+  // Compute ChangeKind for each node based on similarity.
+  void computeChangeKinds(Mapping &M);
 
-  /// Finds an edit script that converts T1 to T2.
-  std::vector<Change> computeChanges(Mapping &M);
-
-  void printChangeImpl(raw_ostream &OS, const Change &Chg) const;
-  void printMatchImpl(raw_ostream &OS, const Match &M) const;
-
-  // Returns a mapping of isomorphic subtrees.
-  Mapping matchTopDown() const;
+  NodeId getMapped(const SyntaxTree::Impl &Tree, NodeId Id) const {
+    if (&Tree == &T1)
+      return TheMapping.getDst(Id);
+    assert(&Tree == &T2 && "Invalid tree.");
+    return TheMapping.getSrc(Id);
+  }
 
 private:
   // Returns true if the two subtrees are identical.
-  bool isomorphic(NodeId Id1, NodeId Id2) const;
+  bool identical(NodeId Id1, NodeId Id2);
 
-  bool canBeAddedToMapping(const Mapping &M, NodeId Id1, NodeId Id2) const;
+  // Returns true if the nodes' parents are matched.
+  bool haveSameParents(const Mapping &M, NodeId Id1, NodeId Id2) const;
 
-  // Returns false if the nodes must not be mached.
+  // Returns false if the nodes must not be matched.
   bool isMatchingPossible(NodeId Id1, NodeId Id2) const;
 
-  // Adds all corresponding subtrees of the two nodes to the mapping.
-  // The two nodes must be isomorphic.
-  void addIsomorphicSubTrees(Mapping &M, NodeId Id1, NodeId Id2) const;
-
   // Uses an optimal albeit slow algorithm to compute a mapping between two
   // subtrees, but only if both have fewer nodes than MaxSize.
   void addOptimalMapping(Mapping &M, NodeId Id1, NodeId Id2) const;
 
-  // Computes the ratio of common descendants between the two nodes.
-  // Descendants are only considered to be equal when they are mapped in M.
-  double getSimilarity(const Mapping &M, NodeId Id1, NodeId Id2) const;
+  double getSimilarity(const Mapping &M, NodeId Id1, NodeId Id2);
+  double getJaccardSimilarity(const Mapping &M, NodeId Id1, NodeId Id2) const;
 
   // Returns the node that has the highest degree of similarity.
-  NodeId findCandidate(const Mapping &M, NodeId Id1) const;
+  NodeId findCandidate(const Mapping &M, NodeId Id1, NodeId Subtree);
 
+  // Returns a mapping of identical subtrees.
+  Mapping matchTopDown();
   // Tries to match any yet unmapped nodes, in a bottom-up fashion.
-  void matchBottomUp(Mapping &M) const;
+  void matchBottomUp(Mapping &M);
+  // Matches nodes, whose parents are matched.
+  void matchChildren(Mapping &M);
 
   const ComparisonOptions &Options;
 
   friend class ZhangShashaMatcher;
 };
 
+class SyntaxTree::Impl {
+public:
+  Impl(SyntaxTree *Parent, ASTContext &AST);
+  Impl(SyntaxTree *Parent, Decl *N, ASTContext &AST);
+  Impl(SyntaxTree *Parent, Stmt *N, ASTContext &AST);
+  template <class T>
+  Impl(SyntaxTree *Parent,
+       typename std::enable_if<std::is_base_of<Stmt, T>::value, T>::type *Node,
+       ASTContext &AST)
+      : SyntaxTree::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,
+       ASTContext &AST)
+      : SyntaxTree::Impl(Parent, dyn_cast<Decl>(Node), AST) {}
+
+  SyntaxTree *Parent;
+  ASTContext &AST;
+  std::vector<NodeId> Leaves;
+  // Maps preorder indices to postorder ones.
+  std::vector<int> PostorderIds;
+  std::vector<NodeId> NodesBfs;
+
+  const StringRef getFilename() const;
+  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]; }
+  // Returns the number of nodes in the subtree, including this one.
+  int getNumberOfDescendants(NodeId Id) const;
+  bool isDescendantOf(NodeId Child, NodeId Parent) const;
+  int findPositionInParent(NodeId Id, bool Shifted = false) const;
+
+  std::string getNodeValue(NodeId Id);
+  std::string getNodeValue(const DynTypedNode &DTN);
+  std::string getDeclValue(const Decl *D) const;
+  std::string getStmtValue(const Stmt *S);
+
+  struct SubtreeIterator {
+    NodeId Root, End;
+    SubtreeIterator(const SyntaxTree::Impl &Tree, NodeId Root)
+        : Root(Root), End(Tree.getNode(Root).RightMostDescendant + 1) {}
+    PreorderIterator begin() const { return Root; }
+    PreorderIterator end() const { return End; }
+  };
+
+  SubtreeIterator iteratePreorder(NodeId Root) const { return {*this, Root}; }
+
+private:
+  /// Nodes in preorder.
+  std::vector<Node> Nodes;
+
+  void initTree();
+  void setLeftMostDescendants();
+};
+
 template <class T>
 static bool isNodeExcluded(const SourceManager &SrcMgr, T *N) {
   if (!N)
     return true;
   SourceLocation SLoc = N->getLocStart();
-  return SLoc.isValid() && SrcMgr.isInSystemHeader(SLoc);
+  if (!SLoc.isValid())
+    return false;
+  // Ignore everything from other files.
+  if (!SrcMgr.isInMainFile(SLoc))
+    return true;
+  // Ignore macros.
+  if (N->getLocStart() != SrcMgr.getSpellingLoc(N->getLocStart()))
+    return true;
+  return false;
 }
 
+static bool isDeclExcluded(const Decl *D) { return D->isImplicit(); }
+static bool isStmtExcluded(const Stmt *S) { return false; }
+
 namespace {
 /// Counts the number of nodes that will be compared.
 struct NodeCountVisitor : public RecursiveASTVisitor<NodeCountVisitor> {
   int Count = 0;
-  const SyntaxTreeImpl &Root;
-  NodeCountVisitor(const SyntaxTreeImpl &Root) : Root(Root) {}
+  const SyntaxTree::Impl &Tree;
+  NodeCountVisitor(const SyntaxTree::Impl &Tree) : Tree(Tree) {}
   bool TraverseDecl(Decl *D) {
-    if (isNodeExcluded(Root.AST.getSourceManager(), D))
+    if (isNodeExcluded(Tree.AST.getSourceManager(), D) || isDeclExcluded(D))
       return true;
     ++Count;
     RecursiveASTVisitor<NodeCountVisitor>::TraverseDecl(D);
     return true;
   }
   bool TraverseStmt(Stmt *S) {
-    if (isNodeExcluded(Root.AST.getSourceManager(), S))
+    if (S)
+      S = S->IgnoreImplicit();
+    if (isNodeExcluded(Tree.AST.getSourceManager(), S) || isStmtExcluded(S))
       return true;
     ++Count;
     RecursiveASTVisitor<NodeCountVisitor>::TraverseStmt(S);
     return true;
   }
   bool TraverseType(QualType T) { return true; }
 };
 } // end anonymous namespace
 
 namespace {
 // Sets Height, Parent and Children for each node.
 struct PreorderVisitor : public RecursiveASTVisitor<PreorderVisitor> {
   int Id = 0, Depth = 0;
   NodeId Parent;
-  SyntaxTreeImpl &Root;
+  SyntaxTree::Impl &Tree;
 
-  PreorderVisitor(SyntaxTreeImpl &Root) : Root(Root) {}
+  PreorderVisitor(SyntaxTree::Impl &Tree) : Tree(Tree) {}
 
   template <class T> std::tuple<NodeId, NodeId> PreTraverse(T *ASTNode) {
     NodeId MyId = Id;
-    Node &N = Root.getMutableNode(MyId);
+    Node &N = Tree.getMutableNode(MyId);
     N.Parent = Parent;
     N.Depth = Depth;
     N.ASTNode = DynTypedNode::create(*ASTNode);
     assert(!N.ASTNode.getNodeKind().isNone() &&
            "Expected nodes to have a valid kind.");
     if (Parent.isValid()) {
-      Node &P = Root.getMutableNode(Parent);
+      Node &P = Tree.getMutableNode(Parent);
       P.Children.push_back(MyId);
     }
     Parent = MyId;
     ++Id;
     ++Depth;
-    return std::make_tuple(MyId, Root.getNode(MyId).Parent);
+    return std::make_tuple(MyId, Tree.getNode(MyId).Parent);
   }
   void PostTraverse(std::tuple<NodeId, NodeId> State) {
     NodeId MyId, PreviousParent;
     std::tie(MyId, PreviousParent) = State;
     assert(MyId.isValid() && "Expecting to only traverse valid nodes.");
     Parent = PreviousParent;
     --Depth;
-    Node &N = Root.getMutableNode(MyId);
-    N.RightMostDescendant = Id;
+    Node &N = Tree.getMutableNode(MyId);
+    N.RightMostDescendant = Id - 1;
     if (N.isLeaf())
-      Root.Leaves.push_back(MyId);
+      Tree.Leaves.push_back(MyId);
     N.Height = 1;
     for (NodeId Child : N.Children)
-      N.Height = std::max(N.Height, 1 + Root.getNode(Child).Height);
+      N.Height = std::max(N.Height, 1 + Tree.getNode(Child).Height);
   }
   bool TraverseDecl(Decl *D) {
-    if (isNodeExcluded(Root.AST.getSourceManager(), D))
+    if (isNodeExcluded(Tree.AST.getSourceManager(), D) || isDeclExcluded(D))
       return true;
     auto SavedState = PreTraverse(D);
     RecursiveASTVisitor<PreorderVisitor>::TraverseDecl(D);
     PostTraverse(SavedState);
     return true;
   }
   bool TraverseStmt(Stmt *S) {
-    if (isNodeExcluded(Root.AST.getSourceManager(), S))
+    if (S)
+      S = S->IgnoreImplicit();
+    if (isNodeExcluded(Tree.AST.getSourceManager(), S) || isStmtExcluded(S))
       return true;
     auto SavedState = PreTraverse(S);
     RecursiveASTVisitor<PreorderVisitor>::TraverseStmt(S);
     PostTraverse(SavedState);
     return true;
   }
   bool TraverseType(QualType T) { return true; }
 };
 } // end anonymous namespace
 
-SyntaxTreeImpl::SyntaxTreeImpl(SyntaxTree *Parent, const ASTContext &AST)
-    : SyntaxTreeImpl(Parent, AST.getTranslationUnitDecl(), AST) {}
+SyntaxTree::Impl::Impl(SyntaxTree *Parent, ASTContext &AST)
+    : Impl(Parent, AST.getTranslationUnitDecl(), AST) {}
 
-SyntaxTreeImpl::SyntaxTreeImpl(SyntaxTree *Parent, Decl *N,
-                               const ASTContext &AST)
+SyntaxTree::Impl::Impl(SyntaxTree *Parent, Decl *N, ASTContext &AST)
     : Parent(Parent), AST(AST) {
   NodeCountVisitor NodeCounter(*this);
   NodeCounter.TraverseDecl(N);
   Nodes.resize(NodeCounter.Count);
   PreorderVisitor PreorderWalker(*this);
   PreorderWalker.TraverseDecl(N);
   initTree();
 }
 
-SyntaxTreeImpl::SyntaxTreeImpl(SyntaxTree *Parent, Stmt *N,
-                               const ASTContext &AST)
+SyntaxTree::Impl::Impl(SyntaxTree *Parent, Stmt *N, ASTContext &AST)
     : Parent(Parent), AST(AST) {
   NodeCountVisitor NodeCounter(*this);
   NodeCounter.TraverseStmt(N);
   Nodes.resize(NodeCounter.Count);
   PreorderVisitor PreorderWalker(*this);
   PreorderWalker.TraverseStmt(N);
   initTree();
 }
 
-void SyntaxTreeImpl::initTree() {
+static std::vector<NodeId> getSubtreePostorder(const SyntaxTree::Impl &Tree,
+                                               NodeId Root) {
+  std::vector<NodeId> Postorder;
+  std::function<void(NodeId)> Traverse = [&](NodeId Id) {
+    const Node &N = Tree.getNode(Id);
+    for (NodeId Child : N.Children)
+      Traverse(Child);
+    Postorder.push_back(Id);
+  };
+  Traverse(Root);
+  return Postorder;
+}
+
+static std::vector<NodeId> getSubtreeBfs(const SyntaxTree::Impl &Tree,
+                                         NodeId Root) {
+  std::vector<NodeId> Ids;
+  unsigned Expanded = 0;
+  Ids.push_back(Root);
+  while (Expanded < Ids.size())
+    for (NodeId Child : Tree.getNode(Ids[Expanded++]).Children)
+      Ids.push_back(Child);
+  return Ids;
+}
+
+void SyntaxTree::Impl::initTree() {
   setLeftMostDescendants();
   int PostorderId = 0;
   PostorderIds.resize(getSize());
   std::function<void(NodeId)> PostorderTraverse = [&](NodeId Id) {
     for (NodeId Child : getNode(Id).Children)
       PostorderTraverse(Child);
     PostorderIds[Id] = PostorderId;
     ++PostorderId;
   };
-  PostorderTraverse(root());
+  PostorderTraverse(getRootId());
+  NodesBfs = getSubtreeBfs(*this, getRootId());
 }
 
-void SyntaxTreeImpl::setLeftMostDescendants() {
+void SyntaxTree::Impl::setLeftMostDescendants() {
   for (NodeId Leaf : Leaves) {
     getMutableNode(Leaf).LeftMostDescendant = Leaf;
     NodeId Parent, Cur = Leaf;
     while ((Parent = getNode(Cur).Parent).isValid() &&
            getNode(Parent).Children[0] == Cur) {
       Cur = Parent;
       getMutableNode(Cur).LeftMostDescendant = Leaf;
     }
   }
 }
 
-static std::vector<NodeId> getSubtreePostorder(const SyntaxTreeImpl &Tree,
-                                               NodeId Root) {
-  std::vector<NodeId> Postorder;
-  std::function<void(NodeId)> Traverse = [&](NodeId Id) {
-    const Node &N = Tree.getNode(Id);
-    for (NodeId Child : N.Children)
-      Traverse(Child);
-    Postorder.push_back(Id);
-  };
-  Traverse(Root);
-  return Postorder;
+const StringRef SyntaxTree::Impl::getFilename() const {
+  SourceLocation RootLoc = getNode(getNode(getRootId()).LeftMostDescendant)
+                               .ASTNode.getSourceRange()
+                               .getBegin();
+  return AST.getSourceManager().getFilename(RootLoc);
 }
 
-static std::vector<NodeId> getSubtreeBfs(const SyntaxTreeImpl &Tree,
-                                         NodeId Root) {
-  std::vector<NodeId> Ids;
-  size_t Expanded = 0;
-  Ids.push_back(Root);
-  while (Expanded < Ids.size())
-    for (NodeId Child : Tree.getNode(Ids[Expanded++]).Children)
-      Ids.push_back(Child);
-  return Ids;
+int SyntaxTree::Impl::getNumberOfDescendants(NodeId Id) const {
+  return getNode(Id).RightMostDescendant - Id + 1;
 }
 
-int SyntaxTreeImpl::getNumberOfDescendants(NodeId Id) const {
-  return getNode(Id).RightMostDescendant - Id + 1;
+bool SyntaxTree::Impl::isDescendantOf(NodeId Child, NodeId Parent) const {
+  return Child >= Parent && Child <= getNode(Parent).RightMostDescendant;
 }
 
-bool SyntaxTreeImpl::isInSubtree(NodeId Id, NodeId SubtreeRoot) const {
-  NodeId Lower = SubtreeRoot;
-  NodeId Upper = getNode(SubtreeRoot).RightMostDescendant;
-  return Id >= Lower && Id <= Upper;
+std::string SyntaxTree::Impl::getNodeValue(NodeId Id) {
+  return getNodeValue(getNode(Id).ASTNode);
 }
 
-std::string SyntaxTreeImpl::getNodeValueImpl(NodeId Id) const {
-  return getNodeValueImpl(getNode(Id).ASTNode);
+std::string SyntaxTree::Impl::getNodeValue(const DynTypedNode &DTN) {
+  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 SyntaxTreeImpl::getNodeValueImpl(const DynTypedNode &DTN) const {
-  if (auto *X = DTN.get<BinaryOperator>())
-    return X->getOpcodeStr();
-  if (auto *X = DTN.get<AccessSpecDecl>()) {
-    CharSourceRange Range(X->getSourceRange(), false);
-    return Lexer::getSourceText(Range, AST.getSourceManager(),
-                                AST.getLangOpts());
-  }
-  if (auto *X = DTN.get<IntegerLiteral>()) {
-    SmallString<256> Str;
-    X->getValue().toString(Str, /*Radix=*/10, /*Signed=*/false);
-    return Str.str();
-  }
-  if (auto *X = DTN.get<StringLiteral>())
-    return X->getString();
-  if (auto *X = DTN.get<ValueDecl>())
-    return X->getNameAsString() + "(" + X->getType().getAsString() + ")";
-  if (DTN.get<DeclStmt>() || DTN.get<TranslationUnitDecl>())
-    return "";
+static const DeclContext *getEnclosingDeclContext(ASTContext &AST,
+                                                  const Stmt *S) {
+  while (S) {
+    const auto &Parents = AST.getParents(*S);
+    if (Parents.empty())
+      return nullptr;
+    const auto &P = Parents[0];
+    if (const auto *D = P.get<Decl>())
+      return D->getDeclContext();
+    S = P.get<Stmt>();
+  }
+  llvm_unreachable("Could not find Decl ancestor.");
+}
+
+// Returns the qualified name of ND. If the is declared in Context then
+// the name is made relative with respect to the qualified name of Context.
+static std::string getRelativeName(const NamedDecl *ND,
+                                   const DeclContext *Context) {
+  std::string ContextPrefix;
+  if (auto *Namespace = dyn_cast<NamespaceDecl>(Context)) {
+    ContextPrefix = Namespace->getQualifiedNameAsString();
+  } else if (auto *Tag = dyn_cast<TagDecl>(Context)) {
+    ContextPrefix = Tag->getQualifiedNameAsString();
+  }
+  std::string Val = ND->getQualifiedNameAsString();
+  // Strip the qualifier, including the final :: if Val refers to
+  // somthing in the current scope.
+  if (!ContextPrefix.empty() &&
+      Val.substr(0, ContextPrefix.size()) == ContextPrefix)
+    Val = Val.substr(ContextPrefix.size() + 2);
+  else
+    // Otherwise, prepend a double colon to the qualified name
+    // to avoid collision with a relative name.
+    // e.g.
+    // namespace n { int x; int local = x, global = ::x; }
+    // local will have the value "x" because the prefix is stripped as above
+    // global has the qualified name "x", therefore we prepend "::" to make it
+    // unambiguous.
+    Val = "::" + Val;
+  return Val;
+
+static std::string getRelativeName(const NamedDecl *ND) {
+  return getRelativeName(ND, ND->getDeclContext());
+
+std::string SyntaxTree::Impl::getDeclValue(const Decl *D) const {
   std::string Value;
-  if (auto *X = DTN.get<DeclRefExpr>()) {
-    if (X->hasQualifier()) {
-      llvm::raw_string_ostream OS(Value);
-      PrintingPolicy PP(AST.getLangOpts());
-      X->getQualifier()->print(OS, PP);
+  PrintingPolicy TypePP(AST.getLangOpts());
+  TypePP.AnonymousTagLocations = false;
+
+  if (auto *X = dyn_cast<ValueDecl>(D)) {
+    Value += getRelativeName(X) + "(" + X->getType().getAsString(TypePP) + ")";
+    if (auto *X = dyn_cast<CXXConstructorDecl>(D)) {
+      for (auto *Init : X->inits()) {
+        if (!Init->isWritten())
+          continue;
+        if (Init->isBaseInitializer()) {
+          Value += Init->getBaseClass()->getCanonicalTypeInternal().getAsString(
+                       TypePP) +
+                   ",";
+        } else {
+          assert(Init->isAnyMemberInitializer());
+          Value += getRelativeName(Init->getMember()) + ",";
+        }
       }
-    Value += X->getDecl()->getNameAsString();
-    return Value;
     }
-  if (auto *X = DTN.get<NamedDecl>())
-    Value += X->getNameAsString() + ";";
-  if (auto *X = DTN.get<TypedefNameDecl>())
-    return Value + X->getUnderlyingType().getAsString() + ";";
-  if (DTN.get<NamespaceDecl>())
     return Value;
-  if (auto *X = DTN.get<TypeDecl>())
+  }
+  if (auto *X = dyn_cast<NamedDecl>(D))
+    Value += getRelativeName(X) + ";";
+  if (auto *X = dyn_cast<TypedefNameDecl>(D))
+    return Value + X->getUnderlyingType().getAsString(TypePP) + ";";
+  if (auto *X = dyn_cast<TypeDecl>(D))
     if (X->getTypeForDecl())
       Value +=
-          X->getTypeForDecl()->getCanonicalTypeInternal().getAsString() + ";";
-  if (DTN.get<Decl>())
-    return Value;
-  if (DTN.get<Stmt>())
-    return "";
-  llvm_unreachable("Fatal: unhandled AST node.\n");
-}
-
-void SyntaxTreeImpl::printTree() const { printTree(root()); }
-void SyntaxTreeImpl::printTree(NodeId Root) const {
-  printTree(llvm::outs(), Root);
+          X->getTypeForDecl()->getCanonicalTypeInternal().getAsString(TypePP) +
+          ";";
+  if (auto *X = dyn_cast<UsingDirectiveDecl>(D))
+    return X->getNominatedNamespace()->getName();
+  if (auto *X = dyn_cast<AccessSpecDecl>(D)) {
+    CharSourceRange Range(X->getSourceRange(), false);
+    return Lexer::getSourceText(Range, AST.getSourceManager(),
+                                AST.getLangOpts());
   }
-
-void SyntaxTreeImpl::printTree(raw_ostream &OS, NodeId Root) const {
-  const Node &N = getNode(Root);
-  for (int I = 0; I < N.Depth; ++I)
-    OS << " ";
-  printNode(OS, Root);
-  OS << "\n";
-  for (NodeId Child : N.Children)
-    printTree(OS, Child);
+  return Value;
 }
 
-void SyntaxTreeImpl::printNode(raw_ostream &OS, NodeId Id) const {
-  if (Id.isInvalid()) {
-    OS << "None";
-    return;
+std::string SyntaxTree::Impl::getStmtValue(const Stmt *S) {
+  if (auto *X = dyn_cast<UnaryOperator>(S))
+    return UnaryOperator::getOpcodeStr(X->getOpcode());
+  if (auto *X = dyn_cast<BinaryOperator>(S))
+    return X->getOpcodeStr();
+  if (auto *X = dyn_cast<MemberExpr>(S))
+    return getRelativeName(X->getMemberDecl());
+  if (auto *X = dyn_cast<IntegerLiteral>(S)) {
+    SmallString<256> Str;
+    X->getValue().toString(Str, /*Radix=*/10, /*Signed=*/false);
+    return Str.str();
   }
-  OS << getNode(Id).getTypeLabel();
-  if (getNodeValueImpl(Id) != "")
-    OS << ": " << getNodeValueImpl(Id);
-  OS << "(" << PostorderIds[Id] << ")";
-}
-
-void SyntaxTreeImpl::printNodeAsJson(raw_ostream &OS, NodeId Id) const {
-  auto N = getNode(Id);
-  OS << R"({"type":")" << N.getTypeLabel() << R"(")";
-  if (getNodeValueImpl(Id) != "")
-    OS << R"(,"value":")" << getNodeValueImpl(Id) << R"(")";
-  OS << R"(,"children":[)";
-  if (N.Children.size() > 0) {
-    printNodeAsJson(OS, N.Children[0]);
-    for (size_t I = 1, E = N.Children.size(); I < E; ++I) {
-      OS << ",";
-      printNodeAsJson(OS, N.Children[I]);
-    }
-  }
-  OS << "]}";
-}
-
-void SyntaxTreeImpl::printAsJsonImpl(raw_ostream &OS) const {
-  OS << R"({"root":)";
-  printNodeAsJson(OS, root());
-  OS << "}\n";
+  if (auto *X = dyn_cast<DeclRefExpr>(S))
+    return getRelativeName(X->getDecl(), getEnclosingDeclContext(AST, S));
+  if (auto *X = dyn_cast<StringLiteral>(S))
+    return X->getString();
+  if (auto *X = dyn_cast<CXXBoolLiteralExpr>(S))
+    return X->getValue() ? "true" : "false";
+  return "";
 }
 
 /// 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; }
   SNodeId &operator++() { return ++Id, *this; }
   SNodeId &operator--() { return --Id, *this; }
   SNodeId operator+(int Other) const { return SNodeId(Id + Other); }
 };
 
 class Subtree {
 private:
   /// The parent tree.
-  const SyntaxTreeImpl &Tree;
+  SyntaxTree::Impl &Tree;
   /// Maps SNodeIds to original ids.
   std::vector<NodeId> RootIds;
   /// Maps subtree nodes to their leftmost descendants wtihin the subtree.
   std::vector<SNodeId> LeftMostDescendants;
 
 public:
   std::vector<SNodeId> KeyRoots;
 
-  Subtree(const SyntaxTreeImpl &Tree, NodeId SubtreeRoot) : Tree(Tree) {
+  Subtree(SyntaxTree::Impl &Tree, NodeId SubtreeRoot) : Tree(Tree) {
     RootIds = getSubtreePostorder(Tree, SubtreeRoot);
     int NumLeaves = setLeftMostDescendants();
     computeKeyRoots(NumLeaves);
   }
   int getSize() const { return RootIds.size(); }
   NodeId getIdInRoot(SNodeId Id) const {
     assert(Id > 0 && Id <= getSize() && "Invalid subtree node index.");
     return RootIds[Id - 1];
   }
   const Node &getNode(SNodeId Id) const {
     return Tree.getNode(getIdInRoot(Id));
   }
+  std::string getNodeValue(SNodeId Id) {
+    return Tree.getNodeValue(getIdInRoot(Id));
+  }
   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))];
   }

 /// deletion and update as edit actions (similar to the Levenshtein distance).
 class ZhangShashaMatcher {
   const ASTDiff::Impl &DiffImpl;
   Subtree S1;
   Subtree S2;
   std::unique_ptr<std::unique_ptr<double[]>[]> TreeDist, ForestDist;
 
 public:
-  ZhangShashaMatcher(const ASTDiff::Impl &DiffImpl, const SyntaxTreeImpl &T1,
-                     const SyntaxTreeImpl &T2, NodeId Id1, NodeId Id2)
+  ZhangShashaMatcher(const ASTDiff::Impl &DiffImpl, SyntaxTree::Impl &T1,
+                     SyntaxTree::Impl &T2, NodeId Id1, NodeId Id2)
       : DiffImpl(DiffImpl), S1(T1, Id1), S2(T2, Id2) {
     TreeDist = llvm::make_unique<std::unique_ptr<double[]>[]>(
         size_t(S1.getSize()) + 1);
     ForestDist = llvm::make_unique<std::unique_ptr<double[]>[]>(
         size_t(S1.getSize()) + 1);
     for (int I = 0, E = S1.getSize() + 1; I < E; ++I) {
       TreeDist[I] = llvm::make_unique<double[]>(size_t(S2.getSize()) + 1);
       ForestDist[I] = llvm::make_unique<double[]>(size_t(S2.getSize()) + 1);
while (!TreePairs.empty()) {
           }
         }
       }
     }
     return Matches;
   }
 
 private:
-  /// Simple cost model for edit actions.
+  /// We use a simple cost model for edit actions, which seems good enough.
   /// The values range between 0 and 1, or infinity if this edit action should
   /// always be avoided.
-
-  /// These costs could be modified to better model the estimated cost of /
-  /// inserting / deleting the current node.
   static constexpr double DeletionCost = 1;
   static constexpr double InsertionCost = 1;
 
   double getUpdateCost(SNodeId Id1, SNodeId Id2) {
-    const DynTypedNode &DTN1 = S1.getNode(Id1).ASTNode,
-                       &DTN2 = S2.getNode(Id2).ASTNode;
-    if (!DiffImpl.Options.isMatchingAllowed(DTN1, DTN2))
+    if (!DiffImpl.isMatchingPossible(S1.getIdInRoot(Id1), S2.getIdInRoot(Id2)))
       return std::numeric_limits<double>::max();
-    return DiffImpl.Options.getNodeDistance(*DiffImpl.T1.Parent, DTN1,
-                                            *DiffImpl.T2.Parent, DTN2);
+    return S1.getNodeValue(Id1) != S2.getNodeValue(Id2);
   }
 
   void computeTreeDist() {
     for (SNodeId Id1 : S1.KeyRoots)
       for (SNodeId Id2 : S2.KeyRoots)
         computeForestDist(Id1, Id2);
   }
 
for (SNodeId D1 = LMD1 + 1; D1 <= Id1; ++D1) {
                         ForestDist[D1][D2 - 1] + InsertionCost,
                         ForestDist[DLMD1][DLMD2] + TreeDist[D1][D2]});
         }
       }
     }
   }
 };
 
+ast_type_traits::ASTNodeKind Node::getType() const {
+  return ASTNode.getNodeKind();
+}
+
+const StringRef Node::getTypeLabel() const { return getType().asStringRef(); }
+
+llvm::Optional<const std::string> Node::getQualifiedIdentifier() const {
+  if (auto *ND = ASTNode.get<NamedDecl>())
+    return ND->getQualifiedNameAsString();
+  return llvm::None;
+}
+
+llvm::Optional<const StringRef> Node::getIdentifier() const {
+  if (auto *ND = ASTNode.get<NamedDecl>())
+    return ND->getName();
+  return llvm::None;
+}
+
+Mapping::Mapping(size_t Size) {
+  SrcToDst = llvm::make_unique<NodeId[]>(Size);
+  DstToSrc = llvm::make_unique<NodeId[]>(Size);
+}
+
+void Mapping::link(NodeId Src, NodeId Dst) {
+  SrcToDst[Src] = Dst;
+  DstToSrc[Dst] = Src;
+}
+
+NodeId Mapping::getDst(NodeId Src) const { return SrcToDst[Src]; }
+NodeId Mapping::getSrc(NodeId Dst) const { return DstToSrc[Dst]; }
+bool Mapping::hasSrc(NodeId Src) const { return getDst(Src).isValid(); }
+bool Mapping::hasDst(NodeId Dst) const { return getSrc(Dst).isValid(); }
+
 namespace {
 // Compares nodes by their depth.
 struct HeightLess {
-  const SyntaxTreeImpl &Tree;
-  HeightLess(const SyntaxTreeImpl &Tree) : Tree(Tree) {}
+  const SyntaxTree::Impl &Tree;
+  HeightLess(const SyntaxTree::Impl &Tree) : Tree(Tree) {}
   bool operator()(NodeId Id1, NodeId Id2) const {
     return Tree.getNode(Id1).Height < Tree.getNode(Id2).Height;
   }
 };
 } // end anonymous namespace
 
+namespace {
 // Priority queue for nodes, sorted descendingly by their height.
 class PriorityList {
-  const SyntaxTreeImpl &Tree;
+  const SyntaxTree::Impl &Tree;
   HeightLess Cmp;
   std::vector<NodeId> Container;
   PriorityQueue<NodeId, std::vector<NodeId>, HeightLess> List;
 
 public:
-  PriorityList(const SyntaxTreeImpl &Tree)
+  PriorityList(const SyntaxTree::Impl &Tree)
       : Tree(Tree), Cmp(Tree), List(Cmp, Container) {}
 
   void push(NodeId id) { List.push(id); }
 
   std::vector<NodeId> pop() {
     int Max = peekMax();
     std::vector<NodeId> Result;
     if (Max == 0)
if (List.empty())
       return 0;
     return Tree.getNode(List.top()).Height;
   }
   void open(NodeId Id) {
     for (NodeId Child : Tree.getNode(Id).Children)
       push(Child);
   }
 };
+} // end anonymous namespace
 
-bool ASTDiff::Impl::isomorphic(NodeId Id1, NodeId Id2) const {
+bool ASTDiff::Impl::identical(NodeId Id1, NodeId Id2) {
   const Node &N1 = T1.getNode(Id1);
   const Node &N2 = T2.getNode(Id2);
   if (N1.Children.size() != N2.Children.size() ||
       !isMatchingPossible(Id1, Id2) ||
-      Options.getNodeDistance(*T1.Parent, N1.ASTNode, *T2.Parent, N2.ASTNode) !=
-          0)
+      T1.getNodeValue(Id1) != T2.getNodeValue(Id2))
     return false;
   for (size_t Id = 0, E = N1.Children.size(); Id < E; ++Id)
-    if (!isomorphic(N1.Children[Id], N2.Children[Id]))
+    if (!identical(N1.Children[Id], N2.Children[Id]))
       return false;
   return true;
 }
 
-bool ASTDiff::Impl::canBeAddedToMapping(const Mapping &M, NodeId Id1,
-                                        NodeId Id2) const {
-  assert(isMatchingPossible(Id1, Id2) &&
-         "Matching must be possible in the first place.");
-  if (M.hasSrcDst(Id1, Id2))
-    return false;
-  if (Options.EnableMatchingWithUnmatchableParents)
-    return true;
-  const Node &N1 = T1.getNode(Id1);
-  const Node &N2 = T2.getNode(Id2);
-  NodeId P1 = N1.Parent;
-  NodeId P2 = N2.Parent;
-  // Only allow matching if parents can be matched.
+bool ASTDiff::Impl::haveSameParents(const Mapping &M, NodeId Id1,
+  NodeId P1 = T1.getNode(Id1).Parent;
+  NodeId P2 = T2.getNode(Id2).Parent;
   return (P1.isInvalid() && P2.isInvalid()) ||
-         (P1.isValid() && P2.isValid() && isMatchingPossible(P1, P2));
+         (P1.isValid() && P2.isValid() && M.getDst(P1) == P2);
 }
 
 bool ASTDiff::Impl::isMatchingPossible(NodeId Id1, NodeId Id2) const {
-  return Options.isMatchingAllowed(T1.getNode(Id1).ASTNode,
-                                   T2.getNode(Id2).ASTNode);
-}
-
-void ASTDiff::Impl::addIsomorphicSubTrees(Mapping &M, NodeId Id1,
-                                          NodeId Id2) const {
-  assert(isomorphic(Id1, Id2) && "Can only be called on isomorphic subtrees.");
-  M.link(Id1, Id2);
-  const Node &N1 = T1.getNode(Id1);
-  const Node &N2 = T2.getNode(Id2);
-  for (size_t Id = 0, E = N1.Children.size(); Id < E; ++Id)
-    addIsomorphicSubTrees(M, N1.Children[Id], N2.Children[Id]);
+  return Options.isMatchingAllowed(T1.getNode(Id1), T2.getNode(Id2));
 }
 
 void ASTDiff::Impl::addOptimalMapping(Mapping &M, NodeId Id1,
                                       NodeId Id2) const {
-  if (std::max(T1.getNumberOfDescendants(Id1),
-               T2.getNumberOfDescendants(Id2)) >= Options.MaxSize)
+  if (std::max(T1.getNumberOfDescendants(Id1), T2.getNumberOfDescendants(Id2)) >
+      Options.MaxSize)
     return;
   ZhangShashaMatcher Matcher(*this, T1, T2, Id1, Id2);
   std::vector<std::pair<NodeId, NodeId>> R = Matcher.getMatchingNodes();
   for (const auto Tuple : R) {
     NodeId Src = Tuple.first;
     NodeId Dst = Tuple.second;
-    if (canBeAddedToMapping(M, Src, Dst))
+    if (!M.hasSrc(Src) && !M.hasDst(Dst))
       M.link(Src, Dst);
   }
 }
 
-double ASTDiff::Impl::getSimilarity(const Mapping &M, NodeId Id1,
+static double haveSameIdentifier(const Node &N1, const Node &N2) {
+  auto QualIdent1 = N1.getQualifiedIdentifier(),
+       QualIdent2 = N2.getQualifiedIdentifier();
+  auto Ident1 = N1.getIdentifier(), Ident2 = N2.getIdentifier();
+  if (Ident1 && Ident2 && *Ident1 == *Ident2) {
+    // If if there is some qualification (qualified identifier is different than
+    // normal identifier), it is highly likely that two names refer to the same
+    // thing, then return 1.
+    if (QualIdent1 && QualIdent2 && *Ident1 != *QualIdent1 &&
+        *QualIdent1 == *QualIdent2)
+      return 1;
+    return 0.5;
+  }
+  return 0;
+}
+
+double ASTDiff::Impl::getSimilarity(const Mapping &M, NodeId Id1, NodeId Id2) {
+  const Node &N1 = T1.getNode(Id1);
+  const Node &N2 = T2.getNode(Id2);
+  bool SameValue = T1.getNodeValue(Id1) == T2.getNodeValue(Id2);
+
+  // In addition to considering common descendants (Jaccard similarity of
+  // matched descendants), we return a similarity of at least
+  // Options.MinSimilarity for nodes that for example:
+  //  - have the same parents and the same value
+  //  - are functions and have the same qualified name.
+  //  - are functions with same parent node and same unqualified name.
+  // This way, those nodes can be matched during the bottom-up phase.
+  double NodeSimilarity = 0.5 * haveSameParents(M, Id1, Id2) + 0.5 * SameValue +
+                          1.0 * haveSameIdentifier(N1, N2);
+  return Options.MinSimilarity * NodeSimilarity +
+         getJaccardSimilarity(M, Id1, Id2);
+}
+
+double ASTDiff::Impl::getJaccardSimilarity(const Mapping &M, NodeId Id1,
                                            NodeId Id2) const {
-  if (Id1.isInvalid() || Id2.isInvalid())
-    return 0.0;
   int CommonDescendants = 0;
   const Node &N1 = T1.getNode(Id1);
-  for (NodeId Id = Id1 + 1; Id <= N1.RightMostDescendant; ++Id)
-    CommonDescendants += int(T2.isInSubtree(M.getDst(Id), Id2));
-  return 2.0 * CommonDescendants /
-         (T1.getNumberOfDescendants(Id1) + T2.getNumberOfDescendants(Id2));
+  for (NodeId Src = Id1 + 1; Src <= N1.RightMostDescendant; ++Src) {
+    NodeId Dst = M.getDst(Src);
+    CommonDescendants += int(Dst.isValid() && T2.isDescendantOf(Dst, Id2));
+  }
+  double Denominator = T1.getNumberOfDescendants(Id1) +
+                       T2.getNumberOfDescendants(Id2) - CommonDescendants;
+  return CommonDescendants / Denominator;
 }
 
-NodeId ASTDiff::Impl::findCandidate(const Mapping &M, NodeId Id1) const {
+NodeId ASTDiff::Impl::findCandidate(const Mapping &M, NodeId Id1,
+                                    NodeId Subtree) {
   NodeId Candidate;
-  double MaxSimilarity = 0.0;
-  for (NodeId Id2 = 0, E = T2.getSize(); Id2 < E; ++Id2) {
+  double HighestSimilarity = 0.0;
+  for (NodeId Id2 : T2.iteratePreorder(Subtree)) {
     if (!isMatchingPossible(Id1, Id2))
       continue;
     if (M.hasDst(Id2))
       continue;
     double Similarity = getSimilarity(M, Id1, Id2);
-    if (Similarity > MaxSimilarity) {
-      MaxSimilarity = Similarity;
+    if (Similarity >= Options.MinSimilarity && Similarity > HighestSimilarity) {
+      HighestSimilarity = Similarity;
       Candidate = Id2;
     }
   }
   return Candidate;
 }
 
-void ASTDiff::Impl::matchBottomUp(Mapping &M) const {
-  std::vector<NodeId> Postorder = getSubtreePostorder(T1, T1.root());
+void ASTDiff::Impl::matchBottomUp(Mapping &M) {
+  std::vector<NodeId> Postorder = getSubtreePostorder(T1, T1.getRootId());
   for (NodeId Id1 : Postorder) {
-    if (Id1 == T1.root()) {
-      if (isMatchingPossible(T1.root(), T2.root())) {
-        M.link(T1.root(), T2.root());
-        addOptimalMapping(M, T1.root(), T2.root());
+    if (Id1 == T1.getRootId() && M.hasSrc(Id1) && M.hasDst(T2.getRootId())) {
+      if (isMatchingPossible(T1.getRootId(), T2.getRootId())) {
+        M.link(T1.getRootId(), T2.getRootId());
+        addOptimalMapping(M, T1.getRootId(), T2.getRootId());
       }
       break;
     }
     const Node &N1 = T1.getNode(Id1);
     bool Matched = M.hasSrc(Id1);
     bool MatchedChildren =
         std::any_of(N1.Children.begin(), N1.Children.end(),
                     [&](NodeId Child) { return M.hasSrc(Child); });
     if (Matched || !MatchedChildren)
       continue;
-    NodeId Id2 = findCandidate(M, Id1);
-    if (Id2.isInvalid() || !canBeAddedToMapping(M, Id1, Id2) ||
-        getSimilarity(M, Id1, Id2) < Options.MinSimilarity)
+    NodeId Id2 = findCandidate(M, Id1, T2.getRootId());
+    if (Id2.isValid()) {
+      M.link(Id1, Id2);
+      addOptimalMapping(M, Id1, Id2);
+    }
+  }
+}
+
+void ASTDiff::Impl::matchChildren(Mapping &M) {
+  for (NodeId Id1 : T1) {
+    NodeId P1 = T1.getNode(Id1).Parent;
+    if (P1.isInvalid() || !M.hasSrc(P1))
       continue;
+    if (M.hasSrc(Id1))
+      continue;
+    NodeId P2 = M.getDst(P1);
+    NodeId Id2 = findCandidate(M, Id1, P2);
+    if (Id2.isValid()) {
       M.link(Id1, Id2);
       addOptimalMapping(M, Id1, Id2);
     }
   }
+}
 
-Mapping ASTDiff::Impl::matchTopDown() const {
+Mapping ASTDiff::Impl::matchTopDown() {
   PriorityList L1(T1);
   PriorityList L2(T2);
 
-  Mapping M(T1.getSize(), T2.getSize());
+  Mapping M(T1.getSize() + T2.getSize());
 
-  L1.push(T1.root());
-  L2.push(T2.root());
+  L1.push(T1.getRootId());
+  L2.push(T2.getRootId());
 
   int Max1, Max2;
   while (std::min(Max1 = L1.peekMax(), Max2 = L2.peekMax()) >
          Options.MinHeight) {
     if (Max1 > Max2) {
       for (NodeId Id : L1.pop())
         L1.open(Id);
       continue;
     }
     if (Max2 > Max1) {
       for (NodeId Id : L2.pop())
         L2.open(Id);
       continue;
     }
     std::vector<NodeId> H1, H2;
     H1 = L1.pop();
     H2 = L2.pop();
     for (NodeId Id1 : H1) {
-      for (NodeId Id2 : H2)
-        if (isomorphic(Id1, Id2) && canBeAddedToMapping(M, Id1, Id2))
-          addIsomorphicSubTrees(M, Id1, Id2);
+      for (NodeId Id2 : H2) {
+        if (identical(Id1, Id2) && !M.hasSrc(Id1) && !M.hasDst(Id2)) {
+          for (int I = 0, E = T1.getNumberOfDescendants(Id1); I < E; ++I) {
+            assert(isMatchingPossible(Id1 + I, Id2 + I));
+            M.link(Id1 + I, Id2 + I);
+          }
+        }
+      }
     }
     for (NodeId Id1 : H1) {
       if (!M.hasSrc(Id1))
         L1.open(Id1);
     }
     for (NodeId Id2 : H2) {
       if (!M.hasDst(Id2))
         L2.open(Id2);
     }
   }
   return M;
 }
 
 void ASTDiff::Impl::computeMapping() {
-  if (IsMappingDone)
-    return;
   TheMapping = matchTopDown();
   matchBottomUp(TheMapping);
-  IsMappingDone = true;
+  matchChildren(TheMapping);
 }
 
-std::vector<Match> ASTDiff::Impl::getMatches(Mapping &M) {
-  std::vector<Match> Matches;
-  for (NodeId Id1 = 0, Id2, E = T1.getSize(); Id1 < E; ++Id1)
-    if ((Id2 = M.getDst(Id1)).isValid())
-      Matches.push_back({Id1, Id2});
-  return Matches;
+int SyntaxTree::Impl::findPositionInParent(NodeId Id, bool Shifted) const {
+  NodeId Parent = getNode(Id).Parent;
+  if (Parent.isInvalid())
+    return 0;
+  const auto &Siblings = getNode(Parent).Children;
+  int Position = 0;
+  for (size_t I = 0, E = Siblings.size(); I < E; ++I) {
+    if (Shifted)
+      Position += getNode(Siblings[I]).Shift;
+    if (Siblings[I] == Id) {
+      Position += I;
+      return Position;
+    }
+  }
+  llvm_unreachable("Node not found in parent's children.");
 }
 
-std::vector<Change> ASTDiff::Impl::computeChanges(Mapping &M) {
-  std::vector<Change> Changes;
-  for (NodeId Id2 : getSubtreeBfs(T2, T2.root())) {
-    const Node &N2 = T2.getNode(Id2);
-    NodeId Id1 = M.getSrc(Id2);
-    if (Id1.isValid()) {
-      assert(isMatchingPossible(Id1, Id2) && "Invalid matching.");
-      if (T1.getNodeValueImpl(Id1) != T2.getNodeValueImpl(Id2)) {
-        Changes.emplace_back(Update, Id1, Id2);
-      }
-      continue;
-    }
-    NodeId P2 = N2.Parent;
-    NodeId P1 = M.getSrc(P2);
-    assert(P1.isValid() &&
-           "Parents must be matched for determining the change type.");
-    Node &Parent1 = T1.getMutableNode(P1);
-    const Node &Parent2 = T2.getNode(P2);
-    auto &Siblings1 = Parent1.Children;
-    const auto &Siblings2 = Parent2.Children;
-    size_t Position;
-    for (Position = 0; Position < Siblings2.size(); ++Position)
-      if (Siblings2[Position] == Id2 || Position >= Siblings1.size())
-        break;
-    Changes.emplace_back(Insert, Id2, P2, Position);
-    Node PatchNode;
-    PatchNode.Parent = P1;
-    PatchNode.LeftMostDescendant = N2.LeftMostDescendant;
-    PatchNode.RightMostDescendant = N2.RightMostDescendant;
-    PatchNode.Depth = N2.Depth;
-    PatchNode.ASTNode = N2.ASTNode;
-    // TODO update Depth if needed
-    NodeId PatchNodeId = T1.getSize();
-    // TODO maybe choose a different data structure for Children.
-    Siblings1.insert(Siblings1.begin() + Position, PatchNodeId);
-    T1.addNode(PatchNode);
-    M.link(PatchNodeId, Id2);
+void ASTDiff::Impl::computeChangeKinds(Mapping &M) {
+  for (NodeId Id1 : T1) {
+    if (!M.hasSrc(Id1)) {
+      T1.getMutableNode(Id1).ChangeKind = Delete;
+      T1.getMutableNode(Id1).Shift -= 1;
+  for (NodeId Id2 : T2) {
+    if (!M.hasDst(Id2)) {
+      T2.getMutableNode(Id2).ChangeKind = Insert;
+      T2.getMutableNode(Id2).Shift -= 1;
     }
-  for (NodeId Id1 = 0; Id1 < T1.getSize(); ++Id1) {
+  }
+  for (NodeId Id1 : T1.NodesBfs) {
     NodeId Id2 = M.getDst(Id1);
     if (Id2.isInvalid())
-      Changes.emplace_back(Delete, Id1, Id2);
+      continue;
+    if (!haveSameParents(M, Id1, Id2) ||
+        T1.findPositionInParent(Id1, true) !=
+            T2.findPositionInParent(Id2, true)) {
+      T1.getMutableNode(Id1).Shift -= 1;
+      T2.getMutableNode(Id2).Shift -= 1;
     }
-  return Changes;
   }
-
-void ASTDiff::Impl::printChangeImpl(raw_ostream &OS, const Change &Chg) const {
-  switch (Chg.Kind) {
-  case Delete:
-    OS << "Delete ";
-    T1.printNode(OS, Chg.Src);
-    OS << "\n";
-    break;
-  case Update:
-    OS << "Update ";
-    T1.printNode(OS, Chg.Src);
-    OS << " to " << T2.getNodeValueImpl(Chg.Dst) << "\n";
-    break;
-  case Insert:
-    OS << "Insert ";
-    T2.printNode(OS, Chg.Src);
-    OS << " into ";
-    T2.printNode(OS, Chg.Dst);
-    OS << " at " << Chg.Position << "\n";
-    break;
-  case Move:
-    llvm_unreachable("TODO");
-    break;
-  };
+  for (NodeId Id2 : T2.NodesBfs) {
+    NodeId Id1 = M.getSrc(Id2);
+    if (Id1.isInvalid())
+      continue;
+    Node &N1 = T1.getMutableNode(Id1);
+    Node &N2 = T2.getMutableNode(Id2);
+    if (Id1.isInvalid())
+      continue;
+    if (!haveSameParents(M, Id1, Id2) ||
+        T1.findPositionInParent(Id1, true) !=
+            T2.findPositionInParent(Id2, true)) {
+      N1.ChangeKind = N2.ChangeKind = Move;
+    }
+    if (T1.getNodeValue(Id1) != T2.getNodeValue(Id2)) {
+      N1.ChangeKind = N2.ChangeKind =
+          (N1.ChangeKind == Move ? UpdateMove : Update);
+    }
   }
-
-void ASTDiff::Impl::printMatchImpl(raw_ostream &OS, const Match &M) const {
-  OS << "Match ";
-  T1.printNode(OS, M.Src);
-  OS << " to ";
-  T2.printNode(OS, M.Dst);
-  OS << "\n";
 }
 
-ASTDiff::ASTDiff(SyntaxTree &T1, SyntaxTree &T2,
+ASTDiff::ASTDiff(SyntaxTree &SrcTree, SyntaxTree &DstTree,
                  const ComparisonOptions &Options)
-    : DiffImpl(llvm::make_unique<Impl>(*T1.TreeImpl, *T2.TreeImpl, Options)) {}
+    : SrcTree(SrcTree), DstTree(DstTree),
+      DiffImpl(llvm::make_unique<Impl>(*SrcTree.TreeImpl, *DstTree.TreeImpl,
+                                       Options)) {
+  DiffImpl->computeMapping();
+  DiffImpl->computeChangeKinds(DiffImpl->TheMapping);
+}
 
-ASTDiff::~ASTDiff() {}
+ASTDiff::~ASTDiff() = default;
 
-SyntaxTree::SyntaxTree(const ASTContext &AST)
-    : TreeImpl(llvm::make_unique<SyntaxTreeImpl>(
+NodeId ASTDiff::getMapped(const SyntaxTree &SourceTree, NodeId Id) const {
+  return DiffImpl->getMapped(*SourceTree.TreeImpl, Id);
+}
+
+SyntaxTree::SyntaxTree(ASTContext &AST)
+    : TreeImpl(llvm::make_unique<SyntaxTree::Impl>(
           this, AST.getTranslationUnitDecl(), AST)) {}
 
-std::vector<Match> ASTDiff::getMatches() {
-  DiffImpl->computeMapping();
-  return DiffImpl->getMatches(DiffImpl->TheMapping);
+SyntaxTree::~SyntaxTree() = default;
+
+ASTContext &SyntaxTree::getASTContext() const { return TreeImpl->AST; }
+
+const StringRef SyntaxTree::getFilename() const {
+  return TreeImpl->getFilename();
 }
 
-std::vector<Change> ASTDiff::getChanges() {
-  DiffImpl->computeMapping();
-  return DiffImpl->computeChanges(DiffImpl->TheMapping);
+int SyntaxTree::getSize() const { return TreeImpl->getSize(); }
+NodeId SyntaxTree::getRootId() const { return TreeImpl->getRootId(); }
+SyntaxTree::PreorderIterator SyntaxTree::begin() const {
+  return TreeImpl->begin();
 }
+SyntaxTree::PreorderIterator SyntaxTree::end() const { return TreeImpl->end(); }
 
-void ASTDiff::printChange(raw_ostream &OS, const Change &Chg) const {
-  DiffImpl->printChangeImpl(OS, Chg);
+const Node &SyntaxTree::getNode(NodeId Id) const {
+  return TreeImpl->getNode(Id);
 }
 
-void ASTDiff::printMatch(raw_ostream &OS, const Match &M) const {
-  DiffImpl->printMatchImpl(OS, M);
+int SyntaxTree::findPositionInParent(NodeId Id) const {
+  return TreeImpl->findPositionInParent(Id);
 }
 
-void SyntaxTree::printAsJson(raw_ostream &OS) { TreeImpl->printAsJsonImpl(OS); }
+std::pair<unsigned, unsigned> SyntaxTree::getFileOffsets(const Node &N) const {
+  const SourceManager &SrcMgr = TreeImpl->AST.getSourceManager();
+  SourceRange Range = N.ASTNode.getSourceRange();
+  SourceLocation BeginLoc = Range.getBegin();
+  SourceLocation EndLoc = Lexer::getLocForEndOfToken(
+      Range.getEnd(), /*Offset=*/0, SrcMgr, TreeImpl->AST.getLangOpts());
+  if (auto *ThisExpr = N.ASTNode.get<CXXThisExpr>()) {
+    if (ThisExpr->isImplicit())
+      EndLoc = BeginLoc;
+  }
+  unsigned Begin = SrcMgr.getFileOffset(SrcMgr.getExpansionLoc(BeginLoc));
+  unsigned End = SrcMgr.getFileOffset(SrcMgr.getExpansionLoc(EndLoc));
+  return {Begin, End};
+}
+
+std::string SyntaxTree::getNodeValue(NodeId Id) {
+  return TreeImpl->getNodeValue(Id);
+}
+
+std::string SyntaxTree::getNodeValue(const Node &Node) {
+  return TreeImpl->getNodeValue(Node.ASTNode);
+}
 
-std::string SyntaxTree::getNodeValue(const DynTypedNode &DTN) const {
-  return TreeImpl->getNodeValueImpl(DTN);
+const std::vector<NodeId> &SyntaxTree::getNodesBreadthFirst() const {
+  return TreeImpl->NodesBfs;
 }
 
 } // end namespace diff
 } // end namespace clang

test/Tooling/clang-diff-basic.cpp

 // RUN: %clang_cc1 -E %s > %T/src.cpp
 // RUN: %clang_cc1 -E %s > %T/dst.cpp -DDEST
-// RUN: clang-diff -no-compilation-database %T/src.cpp %T/dst.cpp | FileCheck %s
+// RUN: clang-diff -no-compilation-database -m %T/src.cpp %T/dst.cpp | FileCheck %s
 
 #ifndef DEST
 namespace src {
 
-void foo() {
-  int x = 321;
-}
+void foo() { int x = 321; }
 
-void main() { foo(); };
+void main() {
+  foo();
+  {{;;;;;;;;;;;;;;;}}
+};
+
+int f() { return 1 * 2 * 3 * 4; }
 
 const char *a = "foo";
 
 typedef unsigned int nat;
 
+void fun() { f(); }
+
+namespace inner {
+void qfun() { f(); }
+}
+
+bool match = true;
+
 int p = 1 * 2 * 3 * 4;
 int squared = p * p;
+} // end namespace src
+
+class Base {};
+
+class X : Base {
+  int a;
+  X(int a) {}
+
+  void testMemberRef() {
+    (void) a;
+    (void) a;
+    (void) a;
+  }
 
-class X {
   const char *foo(int i) {
     if (i == 0)
       return "foo";
     return 0;
   }
 
 public:
-  X(){};
+  X() {}
 
   int id(int i) { return i; }
 };
-}
+
+int x() { return 2; }
+namespace other { int x(); }
+
+namespace refs1 {
+  int x() { return 1;;;; }
+
+  int X1 = x();
+  int X2 = x();
+  int X3 = x();
+} // end namespace refs1
+
+
 #else
+
 // CHECK: Match TranslationUnitDecl{{.*}} to TranslationUnitDecl
-// CHECK: Match NamespaceDecl: src{{.*}} to NamespaceDecl: dst
+// CHECK: Match NamespaceDecl: ::src{{.*}} to NamespaceDecl: ::dst
 namespace dst {
-// CHECK-NOT: Match NamespaceDecl: src{{.*}} to NamespaceDecl: inner
+// CHECK-NOT: Match NamespaceDecl: ::src{{.*}} to NamespaceDecl: inner
 namespace inner {
 void foo() {
   // CHECK: Match IntegerLiteral: 321{{.*}} to IntegerLiteral: 322
   int x = 322;
 }
-}
+void qfun();
+} // end namespace inner
 
 // CHECK: Match DeclRefExpr: foo{{.*}} to DeclRefExpr: inner::foo
-void main() { inner::foo(); }
+void main() {
+  inner::foo();
+  // Create some common descendants, so that the namespaces are matched.
+  {{;;;;;;;;;;;;;;;}}
+}
+
+// CHECK-NOT: Match FunctionDecl: f{{.*}} to FunctionDecl: f(
+int f() { return 3 * 4; }
+// CHECK: Match FunctionDecl: f{{.*}} to FunctionDecl: f1(
+// CHECK: Match ReturnStmt
+int f1() { return 1 * 2 * 3 * 4; }
+int f2() { return 1 * 2 * 3 * 4; }
 
 // CHECK: Match StringLiteral: foo{{.*}} to StringLiteral: foo
 const char *b = "f" "o" "o";
 
 // unsigned is canonicalized to unsigned int
 // CHECK: Match TypedefDecl: nat;unsigned int;{{.*}} to TypedefDecl: nat;unsigned int;
 typedef unsigned nat;
 
+// match functions with the same name + same parent, even if there is no other
+// similarity
+// CHECK: Match FunctionDecl: fun{{.*}} to FunctionDecl: fun
+void fun() { b = ""; }
+
+// also without the same parent if their qualified names are identical
+void inner::qfun() { b = ""; }
+
+// CHECK: Match CXXBoolLiteralExpr: true{{.*}} to CXXBoolLiteralExpr: false
+bool match = false;
+
 // CHECK: Match VarDecl: p(int){{.*}} to VarDecl: prod(double)
-// CHECK: Match BinaryOperator: *{{.*}} to BinaryOperator: *
 // CHECK: Update VarDecl: p(int){{.*}} to prod(double)
+// CHECK-NOT: Match ImplicitCastExpr
+// CHECK: Match BinaryOperator: *{{.*}} to BinaryOperator: *
 double prod = 1 * 2 * 10;
 // CHECK: Update DeclRefExpr
 int squared = prod * prod;
+} // end namespace dst
+
+class Base {};
+
+class X : Base {
+  // CHECK: Update CXXConstructorDecl: X(void (int)){{.*}} to X(void (int))Base,a,s,
+  // Insert DeclRefExpr: a{{.*}} into CXXConstructorDecl: X(void (int))a,s,{{.*}} at 1
+  // Insert IntegerLiteral: 4{{.*}} into CXXConstructorDecl: X(void (int))a,s,{{.*}} at 2
+  X(int a) : Base(), a(a), s(4) {}
+  int a, s;
+
+  void testMemberRef() {
+    // Superfluous qualification does not make a difference.
+    // CHECK: Match MemberExpr: a{{.*}} to MemberExpr: a
+    // CHECK-NOT: Update MemberExpr: a{{.*}}
+    (void) this->a;
+    // CHECK: Match MemberExpr: a{{.*}} to MemberExpr: a
+    // CHECK-NOT: Update MemberExpr: a{{.*}}
+    (void) X::a;
+  }
 
-class X {
   const char *foo(int i) {
     if (i == 0)
       return "Bar";
     // CHECK: Insert IfStmt{{.*}} into IfStmt
     // CHECK: Insert BinaryOperator: =={{.*}} into IfStmt
     else if (i == -1)
       return "foo";
     return 0;
   }
-  // CHECK: Delete AccessSpecDecl: public
-  X(){};
-  // CHECK: Delete CXXMethodDecl
-};
-}
+  X() {}
+};
+
+int x() { return 2; }
+namespace other { int x(); }
+
+namespace refs2 {
+  int x() { return 1;;;; }
+
+  // CHECK: Match DeclRefExpr: x{{.*}} to DeclRefExpr: x
+  // No update even though the qualified name changed, because the relative
+  // name (x) is still the same.
+  // CHECK-NOT: Update DeclRefExpr: x
+  int X1 = x();
+  // CHECK: Match DeclRefExpr: x{{.*}} to DeclRefExpr: ::x
+  int X2 = ::x();
+  // CHECK: Match DeclRefExpr: x{{.*}} to DeclRefExpr: ::other::x
+  int X3 = other::x();
+} // end namespace refs2
+
+
 #endif

tools/clang-diff/CMakeLists.txt

 set(LLVM_LINK_COMPONENTS
   Support
   )
 
 add_clang_executable(clang-diff
   ClangDiff.cpp
   )
 
 target_link_libraries(clang-diff
+  clangBasic
   clangFrontend
   clangTooling
   clangToolingASTDiff
   )

tools/clang-diff/ClangDiff.cpp

 //===- ClangDiff.cpp - compare source files by AST nodes ------*- C++ -*- -===//
 //
 //                     The LLVM Compiler Infrastructure
 //
 // This file is distributed under the University of Illinois Open Source
 // License. See LICENSE.TXT for details.
 //
 //===----------------------------------------------------------------------===//
 //
 // This file implements a tool for syntax tree based comparison using
 // Tooling/ASTDiff.
 //
 //===----------------------------------------------------------------------===//
 
 #include "clang/Tooling/ASTDiff/ASTDiff.h"
+#include "clang/Tooling/ArgumentsAdjusters.h"
 #include "clang/Tooling/CommonOptionsParser.h"
 #include "clang/Tooling/Tooling.h"
 #include "llvm/Support/CommandLine.h"
 
 using namespace llvm;
 using namespace clang;
 using namespace clang::tooling;
 
 static cl::OptionCategory ClangDiffCategory("clang-diff options");
 
 static cl::opt<bool>
-    DumpAST("ast-dump",
+    ASTDump("ast-dump",
             cl::desc("Print the internal representation of the AST as JSON."),
             cl::init(false), cl::cat(ClangDiffCategory));
 
-static cl::opt<bool> NoCompilationDatabase(
-    "no-compilation-database",
-    cl::desc(
-        "Do not attempt to load build settings from a compilation database"),
+static cl::opt<bool>
+    PrintMatches("m", cl::desc("Print the matched nodes (verbose)."),
                  cl::init(false), cl::cat(ClangDiffCategory));
 
 static cl::opt<std::string> SourcePath(cl::Positional, cl::desc("<source>"),
                                        cl::Required,
                                        cl::cat(ClangDiffCategory));
 
 static cl::opt<std::string> DestinationPath(cl::Positional,
                                             cl::desc("<destination>"),
                                             cl::Optional,
                                             cl::cat(ClangDiffCategory));
 
+static cl::opt<bool> NoCompilationDatabase(
+    "no-compilation-database",
+    cl::desc(
+        "Do not attempt to load build settings from a compilation database"),
+    cl::init(false), cl::cat(ClangDiffCategory));
+
+static cl::opt<std::string> BuildPath("p", cl::desc("Build path"), cl::Optional,
+                                      cl::cat(ClangDiffCategory));
+
+static cl::list<std::string> ArgsAfter(
+    "extra-arg",
+    cl::desc("Additional argument to append to the compiler command line"),
+    cl::cat(ClangDiffCategory));
+
+static cl::list<std::string> ArgsBefore(
+    "extra-arg-before",
+    cl::desc("Additional argument to prepend to the compiler command line"),
+    cl::cat(ClangDiffCategory));
+
+namespace {
+class ArgumentsAdjustingCompilations : public CompilationDatabase {
+public:
+  ArgumentsAdjustingCompilations(
+      std::unique_ptr<CompilationDatabase> Compilations)
+      : Compilations(std::move(Compilations)) {}
+
+  void appendArgumentsAdjuster(ArgumentsAdjuster Adjuster) {
+    Adjusters.push_back(std::move(Adjuster));
+  }
+
+  std::vector<CompileCommand>
+  getCompileCommands(StringRef FilePath) const override {
+    return adjustCommands(Compilations->getCompileCommands(FilePath));
+  }
+
+  std::vector<std::string> getAllFiles() const override {
+    return Compilations->getAllFiles();
+  }
+
+  std::vector<CompileCommand> getAllCompileCommands() const override {
+    return adjustCommands(Compilations->getAllCompileCommands());
+  }
+
+private:
+  std::unique_ptr<CompilationDatabase> Compilations;
+  std::vector<ArgumentsAdjuster> Adjusters;
+
+  std::vector<CompileCommand>
+  adjustCommands(std::vector<CompileCommand> Commands) const {
+    for (CompileCommand &Command : Commands)
+      for (const auto &Adjuster : Adjusters)
+        Command.CommandLine = Adjuster(Command.CommandLine, Command.Filename);
+    return Commands;
+  }
+};
+} // end anonymous namespace
+
 static std::unique_ptr<ASTUnit> getAST(const StringRef Filename) {
   std::string ErrorMessage;
   std::unique_ptr<CompilationDatabase> Compilations;
   if (!NoCompilationDatabase)
-    Compilations =
-        CompilationDatabase::autoDetectFromSource(Filename, ErrorMessage);
+    Compilations = CompilationDatabase::autoDetectFromSource(
+        BuildPath.empty() ? Filename : BuildPath, ErrorMessage);
   if (!Compilations) {
     if (!NoCompilationDatabase)
       llvm::errs()
           << "Error while trying to load a compilation database, running "
              "without flags.\n"
           << ErrorMessage;
     Compilations = llvm::make_unique<clang::tooling::FixedCompilationDatabase>(
         ".", std::vector<std::string>());
   }
+  auto AdjustingCompilations =
+      llvm::make_unique<ArgumentsAdjustingCompilations>(
+          std::move(Compilations));
+  AdjustingCompilations->appendArgumentsAdjuster(
+      getInsertArgumentAdjuster(ArgsBefore, ArgumentInsertPosition::BEGIN));
+  AdjustingCompilations->appendArgumentsAdjuster(
+      getInsertArgumentAdjuster(ArgsAfter, ArgumentInsertPosition::END));
+  Compilations = std::move(AdjustingCompilations);
   std::array<std::string, 1> Files = {{Filename}};
   ClangTool Tool(*Compilations, Files);
   std::vector<std::unique_ptr<ASTUnit>> ASTs;
   Tool.buildASTs(ASTs);
   if (ASTs.size() != Files.size())
     return nullptr;
   return std::move(ASTs[0]);
 }
 
+static char hexdigit(int N) { return N &= 0xf, N + (N < 10 ? '0' : 'a' - 10); }
+
+static void printJsonString(raw_ostream &OS, const StringRef Str) {
+  for (char C : Str) {
+    switch (C) {
+    case '"':
+      OS << R"(\")";
+      break;
+    case '\\':
+      OS << R"(\\)";
+      break;
+    case '\n':
+      OS << R"(\n)";
+      break;
+    case '\t':
+      OS << R"(\t)";
+      break;
+    default:
+      if ('\x00' <= C && C <= '\x1f') {
+        OS << R"(\u00)" << hexdigit(C >> 4) << hexdigit(C);
+      } else {
+        OS << C;
+      }
+    }
+  }
+}
+
+static void printNodeAttributes(raw_ostream &OS, diff::SyntaxTree &Tree,
+                                diff::NodeId Id) {
+  const diff::Node &N = Tree.getNode(Id);
+  OS << R"("id":)" << int(Id);
+  OS << R"(,"type":")" << N.getTypeLabel() << '"';
+  auto Offsets = Tree.getFileOffsets(N);
+  OS << R"(,"begin":)" << Offsets.first;
+  OS << R"(,"end":)" << Offsets.second;
+  std::string Value = Tree.getNodeValue(N);
+  if (!Value.empty()) {
+    OS << R"(,"value":")";
+    printJsonString(OS, Value);
+    OS << '"';
+  }
+}
+
+static void printNodeAsJson(raw_ostream &OS, diff::SyntaxTree &Tree,
+                            diff::NodeId Id) {
+  const diff::Node &N = Tree.getNode(Id);
+  OS << "{";
+  printNodeAttributes(OS, Tree, Id);
+  auto Identifier = N.getIdentifier();
+  auto QualifiedIdentifier = N.getQualifiedIdentifier();
+  if (Identifier) {
+    OS << R"(,"identifier":")";
+    printJsonString(OS, *Identifier);
+    OS << R"(")";
+    if (QualifiedIdentifier && *Identifier != *QualifiedIdentifier) {
+      OS << R"(,"qualified_identifier":")";
+      printJsonString(OS, *QualifiedIdentifier);
+      OS << R"(")";
+    }
+  }
+  OS << R"(,"children":[)";
+  if (N.Children.size() > 0) {
+    printNodeAsJson(OS, Tree, N.Children[0]);
+    for (size_t I = 1, E = N.Children.size(); I < E; ++I) {
+      OS << ",";
+      printNodeAsJson(OS, Tree, N.Children[I]);
+    }
+  }
+  OS << "]}";
+}
+
+static void printNode(raw_ostream &OS, diff::SyntaxTree &Tree,
+                      diff::NodeId Id) {
+  if (Id.isInvalid()) {
+    OS << "None";
+    return;
+  }
+  OS << Tree.getNode(Id).getTypeLabel();
+  std::string Value = Tree.getNodeValue(Id);
+  if (!Value.empty())
+    OS << ": " << Value;
+  OS << "(" << Id << ")";
+}
+
+static void printDstChange(raw_ostream &OS, diff::ASTDiff &Diff,
+                           diff::NodeId Dst) {
+  const diff::Node &DstNode = Diff.DstTree.getNode(Dst);
+  diff::NodeId Src = Diff.getMapped(Diff.DstTree, Dst);
+  switch (DstNode.ChangeKind) {
+  case diff::None:
+  case diff::Delete:
+    break;
+  case diff::Update:
+    OS << "Update ";
+    printNode(OS, Diff.SrcTree, Src);
+    OS << " to " << Diff.DstTree.getNodeValue(Dst) << "\n";
+    break;
+  case diff::Insert:
+  case diff::Move:
+  case diff::UpdateMove:
+    if (DstNode.ChangeKind == diff::Insert)
+      OS << "Insert";
+    else if (DstNode.ChangeKind == diff::Move)
+      OS << "Move";
+    else if (DstNode.ChangeKind == diff::UpdateMove)
+      OS << "Update and Move";
+    OS << " ";
+    printNode(OS, Diff.DstTree, Dst);
+    OS << " into ";
+    printNode(OS, Diff.DstTree, DstNode.Parent);
+    OS << " at " << Diff.DstTree.findPositionInParent(Dst) << "\n";
+    break;
+  }
+}
+
 int main(int argc, const char **argv) {
   cl::HideUnrelatedOptions(ClangDiffCategory);
   if (!cl::ParseCommandLineOptions(argc, argv)) {
     cl::PrintOptionValues();
     return 1;
   }
 
-  if (DumpAST) {
+  if (ASTDump) {
     if (!DestinationPath.empty()) {
       llvm::errs() << "Error: Please specify exactly one filename.\n";
       return 1;
     }
     std::unique_ptr<ASTUnit> AST = getAST(SourcePath);
     if (!AST)
       return 1;
     diff::SyntaxTree Tree(AST->getASTContext());
-    Tree.printAsJson(llvm::outs());
+    llvm::outs() << R"({"filename":")";
+    printJsonString(llvm::outs(), Tree.getFilename());
+    llvm::outs() << R"(","root":)";
+    printNodeAsJson(llvm::outs(), Tree, Tree.getRootId());
+    llvm::outs() << "}\n";
+
     return 0;
   }
 
   if (DestinationPath.empty()) {
     llvm::errs() << "Error: Exactly two paths are required.\n";
     return 1;
   }
 
   std::unique_ptr<ASTUnit> Src = getAST(SourcePath);
   std::unique_ptr<ASTUnit> Dst = getAST(DestinationPath);
   if (!Src || !Dst)
     return 1;
 
   diff::ComparisonOptions Options;
   diff::SyntaxTree SrcTree(Src->getASTContext());
   diff::SyntaxTree DstTree(Dst->getASTContext());
-  diff::ASTDiff DiffTool(SrcTree, DstTree, Options);
-  for (const auto &Match : DiffTool.getMatches())
-    DiffTool.printMatch(llvm::outs(), Match);
-  for (const auto &Change : DiffTool.getChanges())
-    DiffTool.printChange(llvm::outs(), Change);
+  diff::ASTDiff Diff(SrcTree, DstTree, Options);
 
+  for (diff::NodeId Dst : DstTree) {
+    diff::NodeId Src = Diff.getMapped(DstTree, Dst);
+    if (PrintMatches && Src.isValid()) {
+      llvm::outs() << "Match ";
+      printNode(llvm::outs(), SrcTree, Src);
+      llvm::outs() << " to ";
+      printNode(llvm::outs(), DstTree, Dst);
+      llvm::outs() << "\n";
+    }
+    printDstChange(llvm::outs(), Diff, Dst);
+  }
+  for (diff::NodeId Src : SrcTree) {
+    if (Diff.getMapped(SrcTree, Src).isInvalid()) {
+      llvm::outs() << "Delete ";
+      printNode(llvm::outs(), SrcTree, Src);
+      llvm::outs() << "\n";
+    }
+  }
   return 0;
 }