[clang-diff] Initial implementation.

[johannes]

Summary

So far, I have implemented the gumtree algorithm https://github.com/GumTreeDiff/gumtree/ to match AST nodes in the source file with their equivalents in the destination files. It combines a heuristic top-down search with an optimal algorithm for small subtrees

The clang-diff tool will mimic the output of the gumtree textual diff, that is, it will print matched nodes (identified by their postorder offset) and an edit script consisting of insertions/deletions.
Note that every node is matched separately (even if large subtrees are equivalent), hence it is rather verbose.

clang-diff src.cpp dst.cpp

The trees that are used to create the matchings and the edit script can be serialized to JSON. I use this to test it by comparing the matchings and the edit script to the ones generated by a prototype implementation.

clang-diff -ast-dump src.cpp

Future features:

• detect code movements (not just inserts / updates / deletes)
• proper visualization (such as http://www.yinwang.org/resources/diff1-diff2.html)
• recursively compare directories
• proper handling of preprocessor macros

[arphaman]

Congratulations of the first GSoC patch! I have some below comments:

• Patches should be submitted using the full context (git diff -U9999). This makes it easier for reviewers to understand the change. This patch mainly adds new code, so this won't make much difference, but please keep this in mind as you update this patch and submit new patches.

include/clang/Tooling/ASTDiff/ASTDiff.h

12

Missing doc comments? You could provide a brief, high-level overview of the algorithm that you're implementing.

62

What do you use from the ASTUnit in the code? Is it possible to use ASTContext instead?

119

Use end namespace diff instead. This applies to any other closing namespace comments as well.

lib/Tooling/ASTDiff/ASTDiff.cpp

32

I don't see the point in these functions. Are you going to add some more logic to them?

I'd suggest removing them and using early return in the traversal functions instead, e.g:

bool TraverseDecl(Decl *D) {
  if (!D)
    return true;
  ++Count;
  return RecursiveASTVisitor<NodeCountVisitor>::TraverseDecl(D);
}

188

You don't need the braces around this if and the ones below (This suggestion probably applies to a few other places as well).

240

Typically dump methods print to stderr, I would suggest renaming these methods to print. You should also pass-in a raw_ostream & to these methods to allow output to different streams. And then you can provide a printAsJson implementation without any parameters that just passes llvm::outs() to the printAsJson that takes in the raw_ostream &.

Similar comments apply to other dump methods.

352

asserts should typically have a message describing the failure, e.g.:

assert(K >= 0 && "Expected a positive non-zero K");

440

You can use std::unique_ptr<std::unique_ptr<double []> []> and avoid the custom destructor. The constructor will then be something like:

TreeDist = llvm::make_unique<std::unique_ptr<double []> []>(S1.getSizeS() + 1);
ForestDist = llvm::make_unique<std::unique_ptr<double []> []>(S1.getSizeS() + 1);
for (int I = 0, E = S1.getSizeS() + 1; I < E; ++I) {
  TreeDist[I] = llvm::make_unique<double []>(S2.getSizeS() + 1);
  ForestDist[I] = llvm::make_unique<double []>(S2.getSizeS() + 1);
}

509

Use // end anonymous namespace instead

815

Please document these parameters and their default values.

tools/clang-diff/ClangDiff.cpp

11

Missing file comment. You should either delete this or add some description.

[arphaman]

lib/Tooling/ASTDiff/ASTDiff.cpp

278

Please use std::unique_ptr<NodeId []> for SrcToDst and DstToSrc as well and remove the destructor.

[arphaman]

Generally we shouldn't have untested code in trunk, so I think that we need to find a way to test this before committing. We can start off by testing the output of the diff tool. Since there will be a lot of changes in the future, you don't have to have everything covered now, so I think that even a couple of tests be enough.

[johannes]

• style fixes
• do not compare nodes from system headers

[johannes]

In D34329#784090, @arphaman wrote:

Generally we shouldn't have untested code in trunk, so I think that we need to find a way to test this before committing. We can start off by testing the output of the diff tool. Since there will be a lot of changes in the future, you don't have to have everything covered now, so I think that even a couple of tests be enough.

Thanks for your feedback! I think I have adressed all issues, except for the tests.

For the tests to run properly, I tried to create a local compile_commands.json, because ClangTool refuses to build an AST when the command for a source not found in the compilation database. However, it seems like relative paths do not work for the "directory" property.
So maybe this can be added? Other options are: 1. patching the compilation database before running the test, so that it has the absolute path or 2. adding an option to my tool to not load a compilation database. WDYT?

Edit: See Tooling.cpp line 401 for a related problem. Maybe it would make sense if ClangTool had an option to silently ignore missing source files.

Edit: I solved it by adding an option to not use compilation databases, so this is not really a problem anymore.

lib/Tooling/ASTDiff/ASTDiff.cpp

32

This is now done in discardNode, which also filters nodes from system headers.

[johannes]

• Add the option to not use compilation databases.
• Add a basic test.

[klimek]

include/clang/Tooling/ASTDiff/ASTDiff.h

124

This is the main exposed interface?

Generally, if all we want to do is printing, I wouldn't put that into a library in Tooling, but just implement a tools/ASTDiffer or somesuch.

If you want to make this a library, it should return the diff in some form that's nice to use (or print).

[johannes]

include/clang/Tooling/ASTDiff/ASTDiff.h

124

I started out by creating a self contained tool, that's why the interface does not really make sense.

I will change it to provide the mappings and the edit script in a nice way, this might be quite useful.

[arphaman]

Looking at the output of the tool, I have the following suggestion:

• We should avoid implicit expressions (We don't need to see things like Insert ImplicitCastExpr(21) into BinaryOperator: *(22) at 0). This can be done in a follow-up patch though.

include/clang/Tooling/ASTDiff/ASTDiff.h

26

There's no need to include the using namespace declarations in the header.

36

InvalidNodeId sounds better IMHO.

124

I agree with Manuel here. We should move runDiff to the tool and and expose the ClandDiff interface in the header.

lib/Tooling/ASTDiff/ASTDiff.cpp

171

Please use Lexer::getSourceText instead of this custom function.

475

Are the DeletionCost and InsertionCost constants or are you planning to modify them in the future?

592

The for loops in LLVM typically store the end value in a separate variable, e.g:

for (size_t Id = 0, E = N1.Children.size(); Id < E; ++Id)

Please update this and similar for loops in this patch.

694

Please wrap these loops in braces.

test/Tooling/clang-diff-basic.cpp

3 ↗

(On Diff #103163)

I'd prefer it if we used something like clang -E and preprocessor to generate the two files.

E.g.:

RUN: %clang_cc1 -E %s > %T/src.cpp
RUN: %clang_cc1 -E %s -D DEST > %T/dst.cpp
#ifndef DEST
namespace src { };
#else
namespace dst { };
#endif

[arphaman]

test/Tooling/clang-diff-basic.cpp

4 ↗

(On Diff #103163)

Why do you need two invocations of clang-diff with the same arguments?

[johannes]

In D34329#785190, @arphaman wrote:

Looking at the output of the tool, I have the following suggestion:

• We should avoid implicit expressions (We don't need to see things like Insert ImplicitCastExpr(21) into BinaryOperator: *(22) at 0). This can be done in a follow-up patch though.

Ok, I will include that and other features in future patches.

lib/Tooling/ASTDiff/ASTDiff.cpp

475

I think they could be modified for minor improvements of the matching, but I am probably not going to do so anytime soon. Maybe it is better to store them at class scope as static const / constexpr?

694

Not sure if I got this right.

test/Tooling/clang-diff-basic.cpp

3 ↗

(On Diff #103163)

Yes, much better!

4 ↗

(On Diff #103163)

That was unintentional, I removed it.

[arphaman]

lib/Tooling/ASTDiff/ASTDiff.cpp

475

Yeah, I suppose for now they should be declared as constants (the static const / constexpr doesn't matter). They should probably be documented as well.

694

It looks better, thanks. Generally we prefer to use braces for if/for/etc. if they have more than one statement.

[arphaman]

lib/Tooling/ASTDiff/ASTDiff.cpp

304

What's the difference between SNodeId and NodeId?

[arphaman]

lib/Tooling/ASTDiff/ASTDiff.cpp

172

I believe that this method that you call label actually represents the value attribute that's described in the paper for the gumtree algorithm. Is that right? If so, then this method name should be updated to reflect that.

[johannes]

lib/Tooling/ASTDiff/ASTDiff.cpp

304

NodeId is the preorder offset inside the root tree, starting at 0.
SNodeId is the postorder offset within a subtree, starting at 1.
Not sure if this irregularity can be improved upon easily, but I guess I can mention it in the comments.

[arphaman]

lib/Tooling/ASTDiff/ASTDiff.cpp

304

Ok. It's fine to have two different types for them, but to avoid confusions I think that the code should be constructed in such a way that prohibits passing in NodeId to a function that expects SNodeId and vice-versa. You can wrap SNodeId in a typedef with an explicit constructor to achieve that goal, e.g.:

struct SNodeId {
  int Id;

  explicit SNodeId(int Id) : Id(Id) { };
};

[johannes]

lib/Tooling/ASTDiff/ASTDiff.cpp

172

Yes, good catch. Strangely, the gumtree implementation uses label. I think we should use type for node kinds and value for their actual value, in order to avoid confusion about what a label is.

[johannes]

• Fix a bug in getSimilarity()
• Change terminology: label -> value
• Define SNodeId: Now it cannot be implicitly constructed from an int, however it can be converted to int. Still feels a bit weird
• Fix some issues with SNodeId
• Rewrite the computation of leftmost descendants in subtrees.

[arphaman]

lib/Tooling/ASTDiff/ASTDiff.cpp

157

Please use a more descriptive name e.g. NumLeaves.

158

you should be able to use auto instead of std::function here I think.

210

Qualifiers (i.e. NestedNameSpecifiers) can contain multiple identifiers (e.g. foo::bar::). You should use the print method from NestedNameSpecifier instead.

227

This Value will always be "", right? You can just return "" here then.

756

Looking at the unpacking here it's probably better to make Change a struct with named fields instead of a tuple. You would still be able to use emplace to create the changes though.

760

You can just get rid of the intermediate S here and print directly to OS in all cases, e.g.:

OS << "Delete " << T1.showNode(Id1) << "\n"

[klimek]

Reviewing this mainly from the API view, and leaving the technical details to others :)

include/clang/Tooling/ASTDiff/ASTDiff.h

125

Generally, can we put the public interface first in the class?
Usually folks read a source file top-down, so if the most relevant pieces of code are at the top, the source file gets easier to read and understand.

Thus:

1. try to keep clutter (like classes and typedefs not used by a user of the API) in a different header, or forward declare them and define them in the .cpp file
2. sort things into public first, then private in classes.

[johannes]

• move some unnecessary things out of the public header

Is this a proper way to declutter the header file? Using inheritance would also be possible.

I have to define a destructor for ASTDiff because TreeComparator is forward-declared

lib/Tooling/ASTDiff/ASTDiff.cpp

158

It does not work because the function is recursive. I'm not sure whether it is good practise to do it like this.

210

Ok nice, this works properly!
This function needs a lot of work. I try to extract relevant information from base classes first.

[arphaman]

The API looks better IMHO. Some more comments:

include/clang/Tooling/ASTDiff/ASTDiff.h

58

I think that it's better to make make NodeId a structure as well and make InvalidNodeId a private member. I suggest the following interface for NodeId:

struct NodeId {
private:
  static const int InvalidNodeId; 
public:
  int Id;

  NodeId() : Id(InvalidNodeId) { }
  NodeId(int Id) : Id(Id) { }
  
  bool isValid() const { return Id != InvalidNodeId; }
  bool isInvalid() const { return Id == InvalidNodeId; }
};

This way you'll get rid of a couple of variable initializations that use InvalidNodeId. You also won't need to call the memset when creating the unique pointer array of NodeIds.

lib/Tooling/ASTDiff/ASTDiff.cpp

34

Mapping should use the C++ move semantics IMHO.

36

This field is used only in TreeComparator, so you might as well move it there and rename to something like IsMappingDone.

319

We don't really need this check. Let's use just one unreachable here.

639

I think this function would would be clearer and faster (you'll be able to avoid redundant work) if you use early exists for the main conditions of the return, e.g.:

if (M.hasSrc(Id1) || M.hasDst(Id2)) return false; // Both nodes must not be mapped.

And so on.

[johannes]

include/clang/Tooling/ASTDiff/ASTDiff.h

58

Ok, I did it like this.

Can I create a header file inside lib/Tooling/ASTDiff and include it from the public interface? This would help reduce the clutter.

Instead of NodeId we could also just use references / pointer types. I don't see any particularly good reason for choosing either one above the other.
I guess indices make it more obvious how to compute the number of descendants and such. On the other hand, when using reference types, there is less boilerplate to write for loops.

[klimek]

include/clang/Tooling/ASTDiff/ASTDiff.h

58

No, but you can create a header ASTDiffInternal or somesuch next to the header in the public dir.

[arphaman]

lib/Tooling/ASTDiff/ASTDiff.cpp

731

Johannes, it seems to me that your implementation of the top-down portion of the GumTree algorithm doesn't use the an empty list A of candidate mappings that's described in the paper (and that you have in the Python prototype). Is that correct or am I missing something?

[johannes]

lib/Tooling/ASTDiff/ASTDiff.cpp

731

Yes, initially I implemented it as it is described in the paper, but then I realized that the list of candidate mappings will always stay empty, because the condition in the top-down algorithm in the paper on line 14 will never be true. Maybe I am mistaken here, but if t1 and t2 are isomorphic, then none of the descendants of t1 will be isomorphic to t2. I mean, the height of isomorphic trees must be equal, and the descendant does not have the same height. So to me this looks like an error in the paper, I probably should have communicated this.
What I did instead is, I had a look at the reference implementation, and what they do instead of using a list of candidate mappings is to just use a data structure for the mapping that allows multiple matches for each node.
After matching collecting all candidates this way, they extract the unambiguous matches and then sort the ambiguous matches by their parents' similarity.
AbstractSubtreeMatcher.java
GreedySubtreeMatcher.java
This seems to be a good solution, I plan to implement that in the future.

[johannes]

lib/Tooling/ASTDiff/ASTDiff.cpp

731

My bad, I misread the algorithm in the paper, of course the entire tree is searched for other isomorphic subtrees.
I will still stick to the way it is implemented in gumtree, it should be more efficient.

[johannes]

refactor

[ruiu]

I'd copy what Hal mentioned in other review thread for other GSoC project. You don't want to tag your patches with "[GSoC]" because it doesn't describe anything about patch contents and many other unrelated patches could have been tagged as single "[GSoC]" tag. Instead, you want to use some other tag that describe your patch. Looks like you are adding a new tool, so I'd guess that "[clang-diff]" could be a good tag.

[arphaman]

Just to clarify: I'm fine with adding the

include/clang/Tooling/ASTDiff/ASTDiff.h

33

Can you pass-in the options by value instead of a pointer?

[arphaman]

Ignore the "Just to clarify: I'm fine with adding the" comment, it was from last week that was saved in my session and that I didn't delete.

[arphaman]

include/clang/Tooling/ASTDiff/ASTDiff.h

58

If you want to use two different names then something like SyntaxTreeImpl is better imho

[johannes]

• pass Options as a const reference instead of a pointer
• rename TreeComparator -> ASTDiff::Impl, rename Comparator -> DiffImpl
• move declaration of ASTDiff::Impl from the header to the source file so that Options does not need to be an opaque pointer
• rename SyntaxTreeI -> SyntaxTreeImpl

[johannes]

• remove unused struct
• rename getNodeValueI -> getNodeValueImpl

[arphaman]

include/clang/Tooling/ASTDiff/ASTDiffInternal.h

184 ↗

(On Diff #104401)

getNodeValueImpl?

lib/Tooling/ASTDiff/ASTDiff.cpp

440

Do you know the reason for the ZsMatcher name? I noticed that they used it in the GumTree java implementation as well. If it's based on some paper you should add a comment that mentions it.

[johannes]

lib/Tooling/ASTDiff/ASTDiff.cpp

440

Ok, i forgot about that, it's Zhang and Shasha's algorithm for the tree edit distance, basically computing the Levenshtein distance for ordered trees.

[arphaman]

I think that it's pretty much ready. I think that the test should be expanded though. At the very least it should check that all of the node types that are supported by SyntaxTreeImpl::getNodeValueImpl get matched.

[teemperor]

I didn't have time to have a close look at this patch, but it seems you're interested in the specific TU-independent data of a Stmt to compare them. So if you are interested in such data and don't want to write your own function to collect it for each Stmt subclass, there is the StmtDataCollector in the CloneDetection.cpp here and a example how to use it is here.

I'm fine with moving this into a header and make it more usable for this use case if you think it makes sense to use it here. The main advantage would be that we don't get yet another of these classes in clang (we already have 3 of them: One in the Stmt profiler code, another one in the ODRHash code for modules and another one in the CloneDetection code).

[johannes]

In D34329#796574, @teemperor wrote:

I didn't have time to have a close look at this patch, but it seems you're interested in the specific TU-independent data of a Stmt to compare them. So if you are interested in such data and don't want to write your own function to collect it for each Stmt subclass, there is the StmtDataCollector in the CloneDetection.cpp here and a example how to use it is here.

I'm fine with moving this into a header and make it more usable for this use case if you think it makes sense to use it here. The main advantage would be that we don't get yet another of these classes in clang (we already have 3 of them: One in the Stmt profiler code, another one in the ODRHash code for modules and another one in the CloneDetection code).

Looking at this again now, it seems to make sense to consolidate this. It collects a lot of data I currently don't.
Does it include the values of literals / identifiers? It seems not (since it is geared towards detecting structural clones only). So we could make that optional, or I could do that myself.

[teemperor]

Yes, it does indeed skip identifiers and literals for this reason :). It was planned to make this template more configurable for use cases like yours, so I'm totally fine with adding configuration parameters. I just opened D34880 where I make this template public as a first step.

[arphaman]

@johannes
Are you planning to work on integration with the StmtDataCollector in this patch or would you prefer to follow-up with additional patches?

[johannes]

In D34329#798377, @arphaman wrote:

@johannes
Are you planning to work on integration with the StmtDataCollector in this patch or would you prefer to follow-up with additional patches?

Later would be better

[arphaman]

lib/Tooling/ASTDiff/ASTDiff.cpp

386

What's the purpose of the S prefix in the name of this method and a couple of other methods below? Can you replace it with something more descriptive or remove it altogether?

[arphaman]

include/clang/Tooling/ASTDiff/ASTDiffInternal.h

38 ↗

(On Diff #105059)

NIT: You don't need this here or in -- as well.

lib/Tooling/ASTDiff/ASTDiff.cpp

360

NIT: This ';' is redundant.

364

NIT: You don't need 'this' here or in the 2 methods below.

810

Missing assertion message.

[johannes]

• style fixes
• correct getSimilarity()

[arphaman]

LGTM. You can request commit access at http://llvm.org/docs/DeveloperPolicy.html#obtaining-commit-access.

[teemperor]

@johannes D34880 has landed, so feel free to propose patches to the StmtDataCollector API that would help you (e.g. to support identifiers). You can see examples how to use it in the CloneDetection.cpp (once for storing data in a FoldingetSetNodeID and once for directly hashing the data with MD5).

[arphaman]

I'll commit this on behalf of Johannes today as he didn't get his access yet

[sylvestre.ledru]

@arphaman @johannes Is that normal that clang-diff isn't installed by cmake? (like clang-format?)

[johannes]

In D34329#1213667, @sylvestre.ledru wrote:

@arphaman @johannes Is that normal that clang-diff isn't installed by cmake? (like clang-format?)

Yes, we did not add that. I don't know if anyone would use it.

[sylvestre.ledru]

@johannes Someone asked for that in Debian: https://bugs.debian.org/cgi-bin/bugreport.cgi?bug=907269

include/clang/Tooling/ASTDiff/ASTDiff.h

+//===- ASTDiff.h - AST differencing API -----------------------*- C++ -*- -===//
+//
+//
+//                     The LLVM Compiler Infrastructure
+//
+// This file is distributed under the University of Illinois Open Source
+// License. See LICENSE.TXT for details.
+//
+//===----------------------------------------------------------------------===//
+//
+// This file specifies an interface that can be used to compare C++ syntax
+// trees.
+//
+// We use the gumtree algorithm which combines a heuristic top-down search that
+// is able to match large subtrees that are equivalent, with an optimal
+// algorithm to match small subtrees.
+//
+//===----------------------------------------------------------------------===//
+
+#ifndef LLVM_CLANG_TOOLING_ASTDIFF_ASTDIFF_H
+#define LLVM_CLANG_TOOLING_ASTDIFF_ASTDIFF_H
+
+#include "clang/AST/ASTTypeTraits.h"
+
+using namespace llvm;
+using namespace clang;
+
+namespace clang {
+namespace diff {
+
+/// Within a tree, this identifies a node by its preorder offset.
+using NodeId = int;
+
+/// Sentinel value for invalid nodes.
+const NodeId NoNodeId = -1;
+
+/// Represents a Clang AST node, alongside some additional information.
+struct Node {
+  NodeId Parent, LeftMostDescendant;
+  int Depth, Height;
+  ast_type_traits::DynTypedNode ASTNode;
+  // Maybe there is a better way to store children than this.
+  SmallVector<NodeId, 4> Children;
+
+  ast_type_traits::ASTNodeKind getType() const { return ASTNode.getNodeKind(); }
+  bool hasSameType(const Node &Other) const {
+    return getType().isSame(Other.getType()) ||
+           (getType().isNone() && Other.getType().isNone());
+  }
+  const StringRef getTypeLabel() const { return getType().asStringRef(); }
+  bool isLeaf() const { return Children.empty(); }
+};
+
+/// Represents the AST of a TranslationUnit.
+class TreeRoot {
+private:
+  /// Nodes in preorder.
+  std::vector<Node> Nodes;
+  void setRightMostDescendant();
+  void setLeftMostDescendant();
+  void setSize(size_t Size) { Nodes.resize(Size); }
+  std::string getSourceString(SourceLocation SourceBegin,
+                              SourceLocation SourceEnd) const;
+
+public:
+  ASTContext &AST;
+  std::vector<NodeId> Leaves;
+  std::vector<int> PostorderIds;
+
+  TreeRoot(ASTContext &AST);
+
+  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); }
+  template <class T> bool discardNode(T *N) const;
+
+  int getSubtreePostorder(std::vector<NodeId> &Ids, NodeId Root) const;
+  std::vector<NodeId> getSubtreeBfs(NodeId Id) const;
+  int getNumberOfDescendants(NodeId Id) const;
+
+  /// Returns the value of the node.
+  std::string label(NodeId Id) const;
+  void printTree(raw_ostream &OS, NodeId Id = NoNodeId) const;
+  /// Return the node as "<kind>[: <label>](<postorder-id)"
+  std::string showNode(NodeId Id) const;
+  void printNodeAsJson(raw_ostream &OS, NodeId Id) const;
+  void printAsJson() const;
+  void printAsJson(raw_ostream &OS) const;
+};
+
+/// Maps nodes of the left tree to ones on the right, and vice versa.
+// Supports fast insertion and lookup.
+// TODO allow multiple mappings
+class Mappings {
+  std::unique_ptr<NodeId[]> SrcToDst, DstToSrc;
+  const TreeRoot &T1, &T2;
+
+public:
+  Mappings(const TreeRoot &T1, const TreeRoot &T2);
+
+  void link(NodeId Src, NodeId Dst);
+
+  NodeId getDst(NodeId Src) const { return SrcToDst[Src]; }
+  NodeId getSrc(NodeId Dst) const { return DstToSrc[Dst]; }
+  bool hasSrc(NodeId Src) const { return SrcToDst[Src] != NoNodeId; }
+  bool hasDst(NodeId Dst) const { return DstToSrc[Dst] != NoNodeId; }
+
+  void printMapping() const;
+  void printMapping(raw_ostream &OS) const;
+};
+
+/// (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.
+/// (Delete, src, _,   _  ): delete node src.
+/// (Move,   src, dst, pos): move src to a child of dst at offset pos.
+enum ChangeKind { Delete, Update, Insert, Move };
+using Change = std::tuple<ChangeKind, NodeId, NodeId, size_t>;
+
+void runDiff(ASTContext &AST1, ASTContext &AST2);
+
+} // end namespace diff
+} // end namespace clang
+
+#endif

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/RecursiveASTVisitor.h"
+#include "llvm/ADT/PriorityQueue.h"
+#include "llvm/Support/FormatVariadic.h"
+
+#include <limits>
+#include <memory>
+#include <unordered_set>
+
+using namespace llvm;
+using namespace clang;
+
+namespace clang {
+namespace diff {
+
+namespace {
+// Count the number of non-null nodes
+struct NodeCountVisitor : public RecursiveASTVisitor<NodeCountVisitor> {
+  int Count = 0;
+  const TreeRoot &Root;
+  NodeCountVisitor(const TreeRoot &Root) : Root(Root) {}
+  bool TraverseDecl(Decl *D) {
+    if (Root.discardNode(D))
+      return true;
+    ++Count;
+    RecursiveASTVisitor<NodeCountVisitor>::TraverseDecl(D);
+    return true;
+  }
+  bool TraverseStmt(Stmt *S) {
+    if (Root.discardNode(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 = NoNodeId;
+  TreeRoot &Root;
+
+  PreorderVisitor(TreeRoot &Root) : Root(Root) {}
+
+  template <class T> std::tuple<NodeId, NodeId> PreTraverse(T *ASTNode) {
+    NodeId MyId = Id;
+    Node &N = Root.getMutableNode(MyId);
+    N.Parent = Parent;
+    N.Depth = Depth;
+    N.ASTNode = ast_type_traits::DynTypedNode::create(*ASTNode);
+    assert(!N.ASTNode.getNodeKind().isNone() &&
+           "Expected nodes to have a valid kind.");
+    if (Parent != NoNodeId) {
+      Node &P = Root.getMutableNode(Parent);
+      P.Children.push_back(MyId);
+    }
+    Parent = MyId;
+    ++Id;
+    ++Depth;
+    return {MyId, Root.getNode(MyId).Parent};
+  }
+  void PostTraverse(std::tuple<NodeId, NodeId> State) {
+    NodeId MyId, PreviousParent;
+    std::tie(MyId, PreviousParent) = State;
+    Parent = PreviousParent;
+    --Depth;
+    if (MyId == NoNodeId)
+      return;
+    Node &N = Root.getMutableNode(MyId);
+    if (N.isLeaf())
+      Root.Leaves.push_back(MyId);
+    N.Height = 1;
+    for (NodeId Child : N.Children)
+      N.Height = std::max(N.Height, 1 + Root.getNode(Child).Height);
+  }
+  bool TraverseDecl(Decl *D) {
+    if (Root.discardNode(D))
+      return true;
+    auto SavedState = PreTraverse(D);
+    RecursiveASTVisitor<PreorderVisitor>::TraverseDecl(D);
+    PostTraverse(SavedState);
+    return true;
+  }
+  bool TraverseStmt(Stmt *S) {
+    if (Root.discardNode(S))
+      return true;
+    auto SavedState = PreTraverse(S);
+    RecursiveASTVisitor<PreorderVisitor>::TraverseStmt(S);
+    PostTraverse(SavedState);
+    return true;
+  }
+  bool TraverseType(QualType T) { return true; }
+};
+} // end anonymous namespace
+
+TreeRoot::TreeRoot(ASTContext &AST) : AST(AST) {
+  auto *TUD = AST.getTranslationUnitDecl();
+  // Run the above visitors to initialize the tree.
+  NodeCountVisitor NodeCounter(*this);
+  NodeCounter.TraverseDecl(TUD);
+  setSize(NodeCounter.Count);
+  PreorderVisitor PreorderWalker(*this);
+  PreorderWalker.TraverseDecl(TUD);
+  setLeftMostDescendant();
+  int PostorderId = 0;
+  PostorderIds.resize(Nodes.size());
+  std::function<void(NodeId)> PostorderTraverse = [&](NodeId Id) {
+    for (NodeId Child : getNode(Id).Children)
+      PostorderTraverse(Child);
+    PostorderIds[Id] = PostorderId;
+    ++PostorderId;
+  };
+  PostorderTraverse(root());
+}
+
+template <class T> bool TreeRoot::discardNode(T *N) const {
+  if (!N)
+    return true;
+  SourceLocation SLoc = N->getLocStart();
+  const SourceManager &SrcMgr = AST.getSourceManager();
+  return SLoc.isValid() && SrcMgr.isInSystemHeader(SLoc);
+}
+
+int TreeRoot::getSubtreePostorder(std::vector<NodeId> &Ids, NodeId Root) const {
+  int Leaves = 0;
+  std::function<void(NodeId)> Traverse = [&](NodeId Id) {
+    const Node &N = getNode(Id);
+    for (NodeId Child : N.Children)
+      Traverse(Child);
+    if (N.isLeaf())
+      ++Leaves;
+    Ids.push_back(Id);
+  };
+  Traverse(Root);
+  return Leaves;
+}
+
+std::vector<NodeId> TreeRoot::getSubtreeBfs(NodeId Id) const {
+  std::vector<NodeId> Ids;
+  size_t Expanded = 0;
+  Ids.push_back(Id);
+  while (Expanded < Ids.size())
+    for (NodeId Child : getNode(Ids[Expanded++]).Children)
+      Ids.push_back(Child);
+  return Ids;
+}
+
+int TreeRoot::getNumberOfDescendants(NodeId Id) const {
+  return PostorderIds[Id] - getNode(Id).LeftMostDescendant;
+}
+
+std::string TreeRoot::getSourceString(SourceLocation SourceBegin,
+                                      SourceLocation SourceEnd) const {
+  const SourceManager &SrcMgr = AST.getSourceManager();
+  const char *Begin = SrcMgr.getCharacterData(SourceBegin);
+  const char *End = SrcMgr.getCharacterData(SourceEnd);
+  return {Begin, static_cast<size_t>(End - Begin)};
+}
+
+std::string TreeRoot::label(NodeId Id) const {
+  const Node &N = getNode(Id);
+  const ast_type_traits::DynTypedNode &DTN = N.ASTNode;
+  if (auto *X = DTN.get<BinaryOperator>())
+    return X->getOpcodeStr();
+  if (auto *X = DTN.get<AccessSpecDecl>())
+    return getSourceString(X->getAccessSpecifierLoc(), X->getColonLoc());
+  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 (auto *X = DTN.get<DeclStmt>())
+    return "";
+  if (auto *X = DTN.get<TranslationUnitDecl>())
+    return "";
+  std::string Label;
+  if (auto *X = DTN.get<DeclRefExpr>()) {
+    if (X->hasQualifier() && X->getQualifier()->getAsIdentifier())
+      Label += std::string(X->getQualifier()->getAsIdentifier()->getName());
+    Label += X->getDecl()->getNameAsString();
+    return Label;
+  }
+  if (auto *X = DTN.get<NamedDecl>())
+    Label += X->getNameAsString() + ";";
+  if (auto *X = DTN.get<TypedefNameDecl>())
+    return Label + X->getUnderlyingType().getAsString() + ";";
+  if (auto *X = DTN.get<NamespaceDecl>())
+    return Label;
+  if (auto *X = DTN.get<TypeDecl>())
+    if (X->getTypeForDecl())
+      Label +=
+          X->getTypeForDecl()->getCanonicalTypeInternal().getAsString() + ";";
+  if (auto *X = DTN.get<Decl>())
+    return Label;
+  if (auto *X = DTN.get<Stmt>())
+    return Label;
+  if (auto *X = DTN.get<QualType>())
+    llvm_unreachable("Types are not included.\n");
+  llvm_unreachable("Fatal: unhandled AST node.\n");
+}
+
+void TreeRoot::printTree(raw_ostream &OS, NodeId Id) const {
+  if (Id == NoNodeId)
+    Id = root();
+  const Node &N = getNode(Id);
+  for (int I = 0; I < N.Depth; ++I)
+    OS << " ";
+  OS << showNode(Id) << "\n";
+  for (NodeId Child : N.Children)
+    printTree(OS, Child);
+}
+
+std::string TreeRoot::showNode(NodeId Id) const {
+  if (Id == NoNodeId)
+    return "None";
+  std::string Label;
+  if (label(Id) != "")
+    Label = formatv(": {0}", label(Id));
+  return formatv("{0}{1}({2})", getNode(Id).getTypeLabel(), Label,
+                 PostorderIds[Id]);
+}
+
+void TreeRoot::printNodeAsJson(raw_ostream &OS, NodeId Id) const {
+  auto N = getNode(Id);
+  std::string Label;
+  if (label(Id) != "")
+    Label = formatv(R"(,"label":"{0}")", label(Id));
+  OS << formatv(R"({"typeLabel":"{0}"{1},"children":[)", N.getTypeLabel(),
+                Label);
+  if (N.Children.size() > 0) {
+    printNodeAsJson(OS, N.Children[0]);
+    for (size_t I = 1; I < N.Children.size(); ++I) {
+      OS << ",";
+      printNodeAsJson(OS, N.Children[I]);
+    }
+  }
+  OS << "]}";
+}
+
+void TreeRoot::printAsJson(raw_ostream &OS) const {
+  OS << R"({"root":)";
+  printNodeAsJson(OS, root());
+  OS << "}\n";
+}
+
+void TreeRoot::printAsJson() const { printAsJson(llvm::outs()); }
+
+void TreeRoot::setLeftMostDescendant() {
+  for (NodeId Id : Leaves) {
+    Node &N = getMutableNode(Id);
+    N.LeftMostDescendant = Id;
+    NodeId Cur = Id;
+    while (N.Parent != NoNodeId && getNode(N.Parent).Children.front() == Cur) {
+      Cur = N.Parent;
+      getMutableNode(Cur).LeftMostDescendant = Id;
+    }
+  }
+}
+
+Mappings::Mappings(const TreeRoot &T1, const TreeRoot &T2) : T1(T1), T2(T2) {
+  // Maximum possible size after patching one tree.
+  int Size = T1.getSize() + T2.getSize();
+  SrcToDst = llvm::make_unique<NodeId[]>(Size);
+  DstToSrc = llvm::make_unique<NodeId[]>(Size);
+  // set everything to NoNodeId == -1
+  memset(SrcToDst.get(), NoNodeId, Size * sizeof(NodeId));
+  memset(DstToSrc.get(), NoNodeId, Size * sizeof(NodeId));
+}
+
+void Mappings::link(NodeId Src, NodeId Dst) {
+  SrcToDst[Src] = Dst;
+  DstToSrc[Dst] = Src;
+}
+
+void Mappings::printMapping(raw_ostream &OS) const {
+  for (NodeId Id1 = 0, Id2; Id1 < T1.getSize(); ++Id1)
+    if ((Id2 = getDst(Id1)) != NoNodeId)
+      OS << formatv("Match {0} to {1}\n", T1.showNode(Id1), T2.showNode(Id2));
+}
+
+void Mappings::printMapping() const { printMapping(llvm::outs()); }
+
+/// Identifies a node in this subtree by its postorder offset.
+using SNodeId = int;
+
+class Subtree {
+private:
+  /// The parent tree.
+  const TreeRoot &Tree;
+  /// Maps SNodeIds to original ids.
+  std::vector<NodeId> RootIds;
+  std::vector<NodeId> LeftMostDescendants;
+
+public:
+  std::vector<NodeId> KeyRoots;
+
+  Subtree(const TreeRoot &Tree, NodeId SubtreeRoot) : Tree(Tree) {
+    int Leaves = Tree.getSubtreePostorder(RootIds, SubtreeRoot);
+    setLeftMostDescendants();
+    computeKeyRoots(Leaves);
+  }
+
+  int getSizeS() const { return RootIds.size(); }
+  NodeId getIdInRoot(SNodeId Id) const {
+    assert(Id > 0 && Id <= getSizeS() && "Invalid subtree node index.");
+    return RootIds[Id - 1];
+  }
+  const Node &getNodeS(SNodeId Id) const {
+    return Tree.getNode(getIdInRoot(Id));
+  }
+  const std::string labelS(SNodeId Id) const {
+    return Tree.label(getIdInRoot(Id));
+  }
+  SNodeId getLeftMostDescendant(SNodeId Id) const {
+    assert(Id > 0 && Id <= getSizeS() && "Invalid subtree node index.");
+    return LeftMostDescendants[Id - 1];
+  }
+
+private:
+  void setLeftMostDescendants() {
+    LeftMostDescendants.resize(getSizeS());
+    for (SNodeId I = 0; I < getSizeS(); ++I) {
+      NodeId Cur = getIdInRoot(I + 1);
+      while (!Tree.getNode(Cur).isLeaf())
+        Cur = Tree.getNode(Cur).Children[0];
+      // TODO why does this work
+      LeftMostDescendants[I] = 1 + (Tree.PostorderIds[Cur] - getIdInRoot(1));
+    }
+    assert(LeftMostDescendants[0] == 0 &&
+           "The leftmost node should have subtree index 0.");
+  }
+  void computeKeyRoots(int Leaves) {
+    KeyRoots.resize(Leaves);
+    std::unordered_set<SNodeId> Visited;
+    int K = Leaves - 1;
+    for (int I = getSizeS(); I > 0; --I) {
+      SNodeId LeftDesc = getLeftMostDescendant(I);
+      if (Visited.count(LeftDesc))
+        continue;
+      assert(K >= 0 && "K should be non-negative");
+      KeyRoots[K] = I;
+      Visited.insert(LeftDesc);
+      --K;
+    }
+  }
+};
+
+// Computes an optimal mapping between two trees
+class ZsMatcher {
+  using Pairs = std::vector<std::pair<NodeId, NodeId>>;
+
+  Subtree S1;
+  Subtree S2;
+  std::unique_ptr<std::unique_ptr<double[]>[]> TreeDist, ForestDist;
+
+public:
+  ZsMatcher(const TreeRoot &T1, const TreeRoot &T2, NodeId Id1, NodeId Id2)
+      : S1(T1, Id1), S2(T2, Id2) {
+    TreeDist =
+        llvm::make_unique<std::unique_ptr<double[]>[]>(S1.getSizeS() + 1);
+    ForestDist =
+        llvm::make_unique<std::unique_ptr<double[]>[]>(S1.getSizeS() + 1);
+    for (int I = 0; I < S1.getSizeS() + 1; ++I) {
+      TreeDist[I] = llvm::make_unique<double[]>(S2.getSizeS() + 1);
+      ForestDist[I] = llvm::make_unique<double[]>(S2.getSizeS() + 1);
+    }
+  }
+
+  Pairs matchZs() {
+    Pairs Matches;
+
+    computeTreeDist();
+
+    bool RootNodePair = true;
+    Pairs TreePairs{{S1.getSizeS(), S2.getSizeS()}};
+
+    NodeId LastRow, LastCol, FirstRow, FirstCol, Row, Col;
+    while (!TreePairs.empty()) {
+      std::tie(LastRow, LastCol) = TreePairs.back();
+      TreePairs.pop_back();
+
+      if (!RootNodePair) {
+        computeForestDist(LastRow, LastCol);
+      }
+
+      RootNodePair = false;
+
+      FirstRow = S1.getLeftMostDescendant(LastRow);
+      FirstCol = S2.getLeftMostDescendant(LastCol);
+
+      Row = LastRow;
+      Col = LastCol;
+
+      while (Row > FirstRow || Col > FirstCol) {
+        if (Row > FirstRow &&
+            ForestDist[Row - 1][Col] + 1 == ForestDist[Row][Col]) {
+          --Row;
+        } else if (Col > FirstCol &&
+                   ForestDist[Row][Col - 1] + 1 == ForestDist[Row][Col]) {
+          --Col;
+        } else {
+          NodeId LMD1 = S1.getLeftMostDescendant(Row);
+          NodeId LMD2 = S2.getLeftMostDescendant(Col);
+          if (LMD1 == S1.getLeftMostDescendant(LastRow) &&
+              LMD2 == S2.getLeftMostDescendant(LastCol)) {
+            assert(S1.getNodeS(Row).hasSameType(S2.getNodeS(Col)) &&
+                   "Must not match nodes of different kind.");
+            Matches.emplace_back(S1.getIdInRoot(Row), S2.getIdInRoot(Col));
+            --Row;
+            --Col;
+          } else {
+            TreePairs.emplace_back(Row, Col);
+            Row = LMD1;
+            Col = LMD2;
+          }
+        }
+      }
+    }
+    return Matches;
+  }
+
+private:
+  // TODO Use string editing distance if applicable.
+  double getUpdateCost(NodeId Id1, NodeId Id2) {
+    if (!S1.getNodeS(Id1).hasSameType(S2.getNodeS(Id2)))
+      return std::numeric_limits<double>::max();
+    if (S1.labelS(Id1) == S2.labelS(Id2))
+      return 0;
+    return 1;
+  }
+  void computeTreeDist() {
+    for (NodeId Id1 : S1.KeyRoots)
+      for (NodeId Id2 : S2.KeyRoots)
+        computeForestDist(Id1, Id2);
+  }
+  void dumpForestDist() const {
+    for (int I = 0; I < S1.getSizeS() + 1; ++I) {
+      llvm::errs() << "[";
+      for (int J = 0; J < S2.getSizeS() + 1; ++J)
+        llvm::errs() << formatv("{0}{1: 2}", (J == 0 ? "" : " "),
+                                ForestDist[I][J]);
+      llvm::errs() << "]\n";
+    }
+  }
+  void computeForestDist(SNodeId Id1, SNodeId Id2) {
+    assert(Id1 > 0 && Id2 > 0 && "Expecting offsets greater than 0.");
+    SNodeId LMD1 = S1.getLeftMostDescendant(Id1);
+    SNodeId LMD2 = S2.getLeftMostDescendant(Id2);
+
+    ForestDist[LMD1][LMD2] = 0;
+    for (SNodeId D1 = LMD1 + 1; D1 <= Id1; ++D1) {
+      double DeletionCost = 1.0;
+      ForestDist[D1][LMD2] = ForestDist[D1 - 1][LMD2] + DeletionCost;
+      for (SNodeId D2 = LMD2 + 1; D2 <= Id2; ++D2) {
+        double InsertionCost = 1;
+        ForestDist[LMD1][D2] = ForestDist[LMD1][D2 - 1] + InsertionCost;
+        SNodeId DLMD1 = S1.getLeftMostDescendant(D1);
+        SNodeId DLMD2 = S2.getLeftMostDescendant(D2);
+        if (DLMD1 == LMD1 && DLMD2 == LMD2) {
+          double UpdateCost = getUpdateCost(D1, D2);
+          ForestDist[D1][D2] =
+              std::min(std::min(ForestDist[D1 - 1][D2] + DeletionCost,
+                                ForestDist[D1][D2 - 1] + InsertionCost),
+                       ForestDist[D1 - 1][D2 - 1] + UpdateCost);
+          TreeDist[D1][D2] = ForestDist[D1][D2];
+        } else {
+          ForestDist[D1][D2] =
+              std::min(std::min(ForestDist[D1 - 1][D2] + DeletionCost,
+                                ForestDist[D1][D2 - 1] + InsertionCost),
+                       ForestDist[DLMD1][DLMD2] + TreeDist[D1][D2]);
+        }
+      }
+    }
+  }
+};
+
+namespace {
+// Compares nodes by their depth.
+struct HeightLess {
+  const TreeRoot &Tree;
+  HeightLess(const TreeRoot &Tree) : Tree(Tree) {}
+  bool operator()(NodeId Id1, NodeId Id2) const {
+    return Tree.getNode(Id1).Height < Tree.getNode(Id2).Height;
+  }
+};
+} // end anonymous namespace
+
+// Priority queue for nodes, sorted descendingly by their height.
+class PriorityList {
+  const TreeRoot &Tree;
+  HeightLess Comparator;
+  std::vector<NodeId> Container;
+  PriorityQueue<NodeId, std::vector<NodeId>, HeightLess> List;
+
+public:
+  PriorityList(const TreeRoot &Tree)
+      : Tree(Tree), Comparator(Tree), List(Comparator, Container) {}
+
+  void push(NodeId id) { List.push(id); }
+
+  std::vector<NodeId> pop() {
+    int Max = peekMax();
+    std::vector<NodeId> Result;
+    if (Max == 0)
+      return Result;
+    while (peekMax() == Max) {
+      Result.push_back(List.top());
+      List.pop();
+    }
+    // TODO this is here to get a stable output, not a good heuristic
+    std::sort(Result.begin(), Result.end());
+    return Result;
+  }
+  int peekMax() const {
+    if (List.empty())
+      return 0;
+    return Tree.getNode(List.top()).Height;
+  }
+  void open(NodeId Id) {
+    for (NodeId Child : Tree.getNode(Id).Children)
+      push(Child);
+  }
+};
+
+/// Computes the differences between two ASTs
+class ClangDiff {
+private:
+  TreeRoot &T1;
+  TreeRoot &T2;
+
+  // Returns true if the two subtrees have the same structure
+  // and equal node kinds (does not compare labels).
+  bool isomorphic(NodeId Id1, NodeId Id2) const {
+    const Node &N1 = T1.getNode(Id1);
+    const Node &N2 = T2.getNode(Id2);
+    if (!N1.hasSameType(N2) || N1.Children.size() != N2.Children.size() ||
+        T1.label(Id1) != T2.label(Id2))
+      return false;
+    for (size_t Id = 0; Id < N1.Children.size(); ++Id)
+      if (!isomorphic(N1.Children[Id], N2.Children[Id]))
+        return false;
+    return true;
+  }
+
+  // TODO This is too restrictive, we want to allow multiple mapping
+  // candidates
+  // for nodes and resolve the ambiguity later.
+  bool isMappingAllowed(const Mappings &M, NodeId Id1, NodeId Id2) const {
+    const Node &N1 = T1.getNode(Id1);
+    const Node &N2 = T2.getNode(Id2);
+    bool AnyMapped = M.hasSrc(Id1) || M.hasDst(Id2);
+    bool SameType = N1.hasSameType(N2);
+    NodeId P1 = N1.Parent;
+    NodeId P2 = N2.Parent;
+    bool ParentsSameType = (P1 == NoNodeId && P2 == NoNodeId) ||
+                           (P1 != NoNodeId && P2 != NoNodeId &&
+                            T1.getNode(P1).hasSameType(T2.getNode(P2)));
+    return !AnyMapped && SameType && ParentsSameType;
+  }
+
+  // Adds all corresponding subtrees of the two nodes to the mappings.
+  // The two nodes must be isomorphic.
+  void addIsomorphicSubTrees(Mappings &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; Id < N1.Children.size(); ++Id)
+      addIsomorphicSubTrees(M, N1.Children[Id], N2.Children[Id]);
+  }
+
+  // Uses an optimal albeit slow algorithm to compute mappings for two
+  // subtrees, but only if both have fewer nodes than MaxSize.
+  void addOptimalMappings(Mappings &M, NodeId Id1, NodeId Id2) const {
+    if (std::max(T1.getNumberOfDescendants(Id1),
+                 T2.getNumberOfDescendants(Id2)) >= MaxSize)
+      return;
+    ZsMatcher Matcher(T1, T2, Id1, Id2);
+    std::vector<std::pair<NodeId, NodeId>> R = Matcher.matchZs();
+    for (const auto Tuple : R) {
+      NodeId Src = Tuple.first;
+      NodeId Dst = Tuple.second;
+      if (isMappingAllowed(M, Src, Dst))
+        M.link(Src, Dst);
+    }
+  }
+
+  // Computes the ratio of common descendants between the two nodes.
+  // Descendants are only considered to be equal when they are mapped in M.
+  double dice(const Mappings &M, NodeId Id1, NodeId Id2) const {
+    if (Id1 == NoNodeId || Id2 == NoNodeId)
+      return 0.0;
+    int CommonDescendants = 0;
+    const Node &N1 = T1.getNode(Id1);
+    for (NodeId Id = N1.LeftMostDescendant; Id < Id1; ++Id)
+      CommonDescendants += int(M.hasSrc(Id));
+    return 2.0 * CommonDescendants /
+           (T1.getNumberOfDescendants(Id1) + T2.getNumberOfDescendants(Id2));
+  }
+
+  // Returns the node that has the highest degree of similarity.
+  NodeId findCandidate(const Mappings &M, NodeId Id1) const {
+    NodeId Candidate = NoNodeId;
+    double BestDiceValue = 0.0;
+    const Node &N1 = T1.getNode(Id1);
+    for (NodeId Id2 = 0; Id2 < T2.getSize(); ++Id2) {
+      const Node &N2 = T2.getNode(Id2);
+      if (!N1.hasSameType(N2))
+        continue;
+      if (M.hasDst(Id2))
+        continue;
+      double DiceValue = dice(M, Id1, Id2);
+      if (DiceValue > BestDiceValue) {
+        BestDiceValue = DiceValue;
+        Candidate = Id2;
+      }
+    }
+    return Candidate;
+  }
+
+  // Tries to match any yet unmapped nodes, in a bottom-up fashion.
+  void matchBottomUp(Mappings &M) const {
+    for (NodeId Id1 = 0; Id1 < T1.getSize(); ++Id1) {
+      if (Id1 == T1.root()) {
+        M.link(T1.root(), T2.root());
+        addOptimalMappings(M, T1.root(), T2.root());
+        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 == NoNodeId || dice(M, Id1, Id2) < MinDice ||
+          !isMappingAllowed(M, Id1, Id2))
+        continue;
+      M.link(Id1, Id2);
+      addOptimalMappings(M, Id1, Id2);
+    }
+  }
+
+  // Returns a set of mappings of isomorphic subtrees.
+  Mappings matchTopDown() const {
+    PriorityList L1(T1);
+    PriorityList L2(T2);
+
+    Mappings M(T1, T2);
+
+    L1.push(T1.root());
+    L2.push(T2.root());
+
+    int Max1, Max2;
+    while (std::min(Max1 = L1.peekMax(), Max2 = L2.peekMax()) > 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) && isMappingAllowed(M, Id1, Id2))
+            addIsomorphicSubTrees(M, Id1, Id2);
+      for (NodeId Id1 : H1)
+        if (!M.hasSrc(Id1))
+          L1.open(Id1);
+      for (NodeId Id2 : H2)
+        if (!M.hasDst(Id2))
+          L2.open(Id2);
+    }
+    return M;
+  }
+
+  // Finds an edit script that converts T1 to T2.
+  std::vector<Change> computeChanges(Mappings &M) {
+    std::vector<Change> Changes;
+    for (NodeId Id2 : T2.getSubtreeBfs(T2.root())) {
+      const Node &N2 = T2.getNode(Id2);
+      NodeId Id1 = M.getSrc(Id2);
+      if (Id1 != NoNodeId) {
+        assert(T1.getNode(Id1).hasSameType(N2) &&
+               "Matched nodes with different kinds.");
+        if (T1.label(Id1) != T2.label(Id2)) {
+          Changes.emplace_back(Update, Id1, Id2, /*UNUSED Position=*/0);
+        }
+        continue;
+      }
+      NodeId P2 = N2.Parent;
+      NodeId P1 = M.getSrc(P2);
+      assert(P1 != NoNodeId);
+      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.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);
+    }
+    for (NodeId Id1 = 0; Id1 < T1.getSize(); ++Id1) {
+      NodeId Id2 = M.getDst(Id1);
+      if (Id2 == NoNodeId)
+        Changes.emplace_back(Delete, Id1, Id2, /*UNUSED Position=*/0);
+    }
+    return Changes;
+  }
+
+  // Prints an edit action.
+  void printChange(const Change &Chg) const { printChange(llvm::outs(), Chg); }
+  void printChange(raw_ostream &OS, const Change &Chg) const {
+    ChangeKind Kind;
+    NodeId Id1, Id2;
+    size_t Position;
+    std::tie(Kind, Id1, Id2, Position) = Chg;
+    std::string S;
+    switch (Kind) {
+    case Delete:
+      S = formatv("Delete {0}", T1.showNode(Id1));
+      break;
+    case Update:
+      S = formatv("Update {0} to {1}", T1.showNode(Id1), T2.label(Id2));
+      break;
+    case Insert:
+      S = formatv("Insert {0} into {1} at {2}", T2.showNode(Id1),
+                  T2.showNode(Id2), Position);
+      break;
+    case Move:
+      llvm_unreachable("TODO");
+      break;
+    };
+    OS << S << "\n";
+  }
+
+  Mappings match() const {
+    Mappings M = matchTopDown();
+    matchBottomUp(M);
+    return M;
+  }
+
+public:
+  // 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 MinDice = 0.2;
+  // 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;
+
+  ClangDiff(TreeRoot &T1, TreeRoot &T2) : T1(T1), T2(T2) {}
+
+  void printDiff() {
+    Mappings M = match();
+    M.printMapping();
+    auto Changes = computeChanges(M);
+    for (const auto &C : Changes)
+      printChange(C);
+  }
+};
+
+void runDiff(ASTContext &AST1, ASTContext &AST2) {
+  TreeRoot T1(AST1);
+  TreeRoot T2(AST2);
+  ClangDiff DiffTool(T1, T2);
+  DiffTool.printDiff();
+}
+
+} // end namespace diff
+} // end namespace clang

lib/Tooling/ASTDiff/CMakeLists.txt

+set(LLVM_LINK_COMPONENTS
+  # Option
+  Support
+  )
+
+add_clang_library(clangToolingASTDiff
+  ASTDiff.cpp
+  LINK_LIBS
+  clangBasic
+  clangAST
+  # clangToolingCore
+  )

lib/Tooling/CMakeLists.txt

 set(LLVM_LINK_COMPONENTS
   Option
   Support
   )
 
 add_subdirectory(Core)
 add_subdirectory(Refactoring)
+add_subdirectory(ASTDiff)
 
 add_clang_library(clangTooling
   ArgumentsAdjusters.cpp
   CommonOptionsParser.cpp
   CompilationDatabase.cpp
   FileMatchTrie.cpp
   FixIt.cpp
   JSONCompilationDatabase.cpp

tools/CMakeLists.txt

 create_subdirectory_options(CLANG TOOL)
 
 add_clang_subdirectory(diagtool)
 add_clang_subdirectory(driver)
+add_clang_subdirectory(clang-diff)
 add_clang_subdirectory(clang-format)
 add_clang_subdirectory(clang-format-vs)
 add_clang_subdirectory(clang-fuzzer)
 add_clang_subdirectory(clang-import-test)
 add_clang_subdirectory(clang-offload-bundler)
 
 add_clang_subdirectory(c-index-test)
 

tools/clang-diff/CMakeLists.txt

+set(LLVM_LINK_COMPONENTS
+  Support
+  )
+
+add_clang_executable(clang-diff
+  ClangDiff.cpp
+  )
+
+target_link_libraries(clang-diff
+  clangAST
+  clangBasic
+  clangFrontend
+  clangLex
+  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/CommonOptionsParser.h"
+#include "clang/Tooling/Tooling.h"
+#include "llvm/Support/CommandLine.h"
+
+using namespace tooling;
+
+static cl::OptionCategory ClangDiffCategory("clang-diff options");
+
+static cl::opt<bool>
+    DumpAST("ast-dump",
+            cl::desc("Print the internal representation of the AST as JSON."),
+            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 std::unique_ptr<ASTUnit> getAST(const StringRef Filename) {
+  std::string ErrorMessage;
+  std::unique_ptr<CompilationDatabase> Compilations =
+      CompilationDatabase::autoDetectFromSource(Filename, ErrorMessage);
+  if (!Compilations) {
+    llvm::errs()
+        << "Error while trying to load a compilation database, running "
+           "without flags.\n"
+        << ErrorMessage;
+    Compilations.reset(
+        new FixedCompilationDatabase(".", std::vector<std::string>()));
+  }
+  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]);
+}
+
+int main(int argc, const char **argv) {
+  cl::HideUnrelatedOptions(ClangDiffCategory);
+  if (!cl::ParseCommandLineOptions(argc, argv)) {
+    cl::PrintOptionValues();
+    return 1;
+  }
+
+  if (DumpAST) {
+    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;
+    clang::diff::TreeRoot Tree(AST->getASTContext());
+    Tree.printAsJson();
+    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;
+
+  clang::diff::runDiff(Src->getASTContext(), Dst->getASTContext());
+
+  return 0;
+}