johannes updated this revision to Diff 103432.
https://reviews.llvm.org/D34329
Files:
include/clang/Tooling/ASTDiff/ASTDiff.h
lib/Tooling/ASTDiff/ASTDiff.cpp
lib/Tooling/ASTDiff/CMakeLists.txt
lib/Tooling/CMakeLists.txt
test/Tooling/clang-diff-basic.cpp
tools/CMakeLists.txt
tools/clang-diff/CMakeLists.txt
tools/clang-diff/ClangDiff.cpp
Index: tools/clang-diff/ClangDiff.cpp
===================================================================
--- /dev/null
+++ tools/clang-diff/ClangDiff.cpp
@@ -0,0 +1,107 @@
+//===- 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 llvm;
+using namespace clang;
+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<bool> NoCompilationDatabase(
+ "no-compilation-database",
+ cl::desc(
+ "Do not attempt to load build settigns from a compilation database"),
+ 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;
+ if (!NoCompilationDatabase)
+ Compilations =
+ CompilationDatabase::autoDetectFromSource(Filename, ErrorMessage);
+ if (!Compilations) {
+ if (!NoCompilationDatabase)
+ 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;
+
+ diff::ASTDiff DiffTool(Src->getASTContext(), Dst->getASTContext());
+ for (const auto &Match : DiffTool.getMatches())
+ DiffTool.printMatch(Match);
+ for (const auto &Change : DiffTool.getChanges())
+ DiffTool.printChange(Change);
+
+ return 0;
+}
Index: tools/clang-diff/CMakeLists.txt
===================================================================
--- /dev/null
+++ tools/clang-diff/CMakeLists.txt
@@ -0,0 +1,13 @@
+set(LLVM_LINK_COMPONENTS
+ Support
+ )
+
+add_clang_executable(clang-diff
+ ClangDiff.cpp
+ )
+
+target_link_libraries(clang-diff
+ clangFrontend
+ clangTooling
+ clangToolingASTDiff
+ )
Index: tools/CMakeLists.txt
===================================================================
--- tools/CMakeLists.txt
+++ tools/CMakeLists.txt
@@ -2,6 +2,7 @@
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)
Index: test/Tooling/clang-diff-basic.cpp
===================================================================
--- /dev/null
+++ test/Tooling/clang-diff-basic.cpp
@@ -0,0 +1,61 @@
+// 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
+
+#ifndef DEST
+namespace src {
+ const char str[] = "the string";
+ ;
+ ;
+ ;
+ ;
+}
+
+int on = 1 * 2 * 3 * 4;
+int b = on * 2;
+
+class X {
+ const char *foo(int i) {
+ if (i == 0)
+ return "Foo!";
+ return 0;
+ }
+
+public:
+ X(){};
+
+ int id(int i) { return i; }
+};
+#else
+// CHECK: Match NamespaceDecl: src{{.*}} to NamespaceDecl: src
+namespace src {
+ ;
+ ;
+ ;
+ ;
+}
+// CHECK-NOT: Match NamespaceDecl: src{{.*}} to NamespaceDecl: dst
+namespace dst {
+}
+
+// CHECK: Match VarDecl: on(int){{.*}} to VarDecl: one(double)
+// CHECK: Update VarDecl: on(int){{.*}} to one(double)
+double one = 1 * 2 * 55;
+// CHECK: Update DeclRefExpr
+int b = one * 2;
+
+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
+};
+#endif
Index: lib/Tooling/CMakeLists.txt
===================================================================
--- lib/Tooling/CMakeLists.txt
+++ lib/Tooling/CMakeLists.txt
@@ -5,6 +5,7 @@
add_subdirectory(Core)
add_subdirectory(Refactoring)
+add_subdirectory(ASTDiff)
add_clang_library(clangTooling
ArgumentsAdjusters.cpp
Index: lib/Tooling/ASTDiff/CMakeLists.txt
===================================================================
--- /dev/null
+++ lib/Tooling/ASTDiff/CMakeLists.txt
@@ -0,0 +1,11 @@
+set(LLVM_LINK_COMPONENTS
+ Support
+ )
+
+add_clang_library(clangToolingASTDiff
+ ASTDiff.cpp
+ LINK_LIBS
+ clangBasic
+ clangAST
+ clangLex
+ )
Index: lib/Tooling/ASTDiff/ASTDiff.cpp
===================================================================
--- /dev/null
+++ lib/Tooling/ASTDiff/ASTDiff.cpp
@@ -0,0 +1,883 @@
+//===- 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 "clang/Lex/Lexer.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 {
+
+/// Maps nodes of the left tree to ones on the right, and vice versa.
+/// Supports fast insertion and lookup.
+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<NodeId[]>(Size);
+ DstToSrc = llvm::make_unique<NodeId[]>(Size);
+ }
+
+ void link(NodeId Src, NodeId Dst) {
+ SrcToDst[Src] = Dst;
+ DstToSrc[Dst] = Src;
+ }
+
+ NodeId getDst(NodeId Src) const { return SrcToDst[Src]; }
+ NodeId getSrc(NodeId Dst) const { return DstToSrc[Dst]; }
+ bool hasSrc(NodeId Src) const { return SrcToDst[Src].isValid(); }
+ bool hasDst(NodeId Dst) const { return DstToSrc[Dst].isValid(); }
+
+private:
+ std::unique_ptr<NodeId[]> SrcToDst, DstToSrc;
+};
+
+class TreeComparator {
+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 MinSimilarity = 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;
+
+ TreeRoot T1, T2;
+ bool IsMappingDone = false;
+ Mapping TheMapping;
+
+ TreeComparator(ASTContext &AST1, ASTContext &AST2) : T1(AST1), T2(AST2) {}
+
+ /// Matches nodes one-by-one based on their similarity.
+ void computeMapping();
+
+ std::vector<Match> getMatches(Mapping &M);
+
+ /// Finds an edit script that converts T1 to T2.
+ std::vector<Change> computeChanges(Mapping &M);
+
+ void printChange(raw_ostream &OS, const Change &Chg) const;
+ void printMatch(raw_ostream &OS, const Match &M) const;
+
+private:
+ // Returns true if the two subtrees are identical.
+ bool isomorphic(NodeId Id1, NodeId Id2) const;
+
+ // TODO This is too restrictive, we want to allow multiple mapping candidates
+ // for nodes and resolve the ambiguity later.
+ bool isMappingAllowed(const Mapping &M, 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;
+
+ // Returns the node that has the highest degree of similarity.
+ NodeId findCandidate(const Mapping &M, NodeId Id1) const;
+
+ // Tries to match any yet unmapped nodes, in a bottom-up fashion.
+ void matchBottomUp(Mapping &M) const;
+
+ // Returns a mapping of isomorphic subtrees.
+ Mapping matchTopDown() const;
+};
+
+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);
+}
+
+namespace {
+/// Counts the number of nodes that will be compared.
+struct NodeCountVisitor : public RecursiveASTVisitor<NodeCountVisitor> {
+ int Count = 0;
+ const TreeRoot &Root;
+ NodeCountVisitor(const TreeRoot &Root) : Root(Root) {}
+ bool TraverseDecl(Decl *D) {
+ if (isNodeExcluded(Root.AST.getSourceManager(), D))
+ return true;
+ ++Count;
+ RecursiveASTVisitor<NodeCountVisitor>::TraverseDecl(D);
+ return true;
+ }
+ bool TraverseStmt(Stmt *S) {
+ if (isNodeExcluded(Root.AST.getSourceManager(), 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;
+ 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.isValid()) {
+ 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;
+ assert(MyId.isValid() && "Expecting to only traverse valid nodes.");
+ Parent = PreviousParent;
+ --Depth;
+ Node &N = Root.getMutableNode(MyId);
+ N.RightMostDescendant = Id;
+ 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 (isNodeExcluded(Root.AST.getSourceManager(), 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))
+ 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);
+ Nodes.resize(NodeCounter.Count);
+ PreorderVisitor PreorderWalker(*this);
+ PreorderWalker.TraverseDecl(TUD);
+ 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());
+}
+
+void TreeRoot::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 TreeRoot &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 TreeRoot &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 TreeRoot::getNumberOfDescendants(NodeId Id) const {
+ return getNode(Id).RightMostDescendant - Id + 1;
+}
+
+std::string TreeRoot::getValue(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>()) {
+ 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 (auto *X = DTN.get<DeclStmt>())
+ return "";
+ if (auto *X = DTN.get<TranslationUnitDecl>())
+ return "";
+ 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);
+ }
+ 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 (auto *X = DTN.get<NamespaceDecl>())
+ return Value;
+ if (auto *X = DTN.get<TypeDecl>())
+ if (X->getTypeForDecl())
+ Value +=
+ X->getTypeForDecl()->getCanonicalTypeInternal().getAsString() + ";";
+ if (auto *X = DTN.get<Decl>())
+ return Value;
+ if (auto *X = DTN.get<Stmt>())
+ return "";
+ llvm_unreachable("Fatal: unhandled AST node.\n");
+}
+
+void TreeRoot::printTree(raw_ostream &OS, NodeId Root) const {
+ const Node &N = getNode(Root);
+ for (int I = 0; I < N.Depth; ++I)
+ OS << " ";
+ OS << showNode(Root) << "\n";
+ for (NodeId Child : N.Children)
+ printTree(OS, Child);
+}
+
+std::string TreeRoot::showNode(NodeId Id) const {
+ if (Id.isInvalid())
+ return "None";
+ std::string ValueString;
+ if (getValue(Id) != "")
+ ValueString = formatv(": {0}", getValue(Id));
+ return formatv("{0}{1}({2})", getNode(Id).getTypeLabel(), ValueString,
+ PostorderIds[Id]);
+}
+
+void TreeRoot::printNodeAsJson(raw_ostream &OS, NodeId Id) const {
+ auto N = getNode(Id);
+ std::string ValueProperty;
+ if (getValue(Id) != "")
+ ValueProperty = formatv(R"(,"value":"{0}")", getValue(Id));
+ OS << formatv(R"({"type":"{0}"{1},"children":[)", N.getTypeLabel(),
+ ValueProperty);
+ 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 TreeRoot::printAsJson(raw_ostream &OS) const {
+ OS << R"({"root":)";
+ printNodeAsJson(OS, root());
+ OS << "}\n";
+}
+
+/// Identifies a node in a subtree by its postorder offset, starting at 1.
+struct SNodeId {
+ int Id;
+
+ explicit SNodeId(int Id) : Id(Id){};
+ explicit SNodeId() : Id(0){};
+
+ operator int() const { return Id; }
+ SNodeId &operator++() { return ++this->Id, *this; }
+ SNodeId &operator--() { return --this->Id, *this; }
+ SNodeId operator+(int Other) const { return SNodeId(this->Id + Other); }
+};
+
+class Subtree {
+private:
+ /// The parent tree.
+ const TreeRoot &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 TreeRoot &Tree, NodeId SubtreeRoot) : Tree(Tree) {
+ RootIds = getSubtreePostorder(Tree, SubtreeRoot);
+ int NumLeaves = setLeftMostDescendantsS();
+ computeKeyRoots(NumLeaves);
+ }
+ 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 getValueS(SNodeId Id) const {
+ return Tree.getValue(getIdInRoot(Id));
+ }
+ SNodeId getLeftMostDescendant(SNodeId Id) const {
+ assert(Id > 0 && Id <= getSizeS() && "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))];
+ }
+
+private:
+ /// Returns the number of leafs in the subtree.
+ int setLeftMostDescendantsS() {
+ int NumLeaves = 0;
+ LeftMostDescendants.resize(getSizeS());
+ for (int I = 0; I < getSizeS(); ++I) {
+ SNodeId SI(I + 1);
+ const Node &N = getNodeS(SI);
+ NumLeaves += N.isLeaf();
+ assert(I == Tree.PostorderIds[getIdInRoot(SI)] - getPostorderOffset() &&
+ "Postorder traversal in subtree should correspond to traversal in "
+ "the root tree by a constant offset.");
+ LeftMostDescendants[I] = SNodeId(Tree.PostorderIds[N.LeftMostDescendant] -
+ getPostorderOffset());
+ }
+ return NumLeaves;
+ }
+ void computeKeyRoots(int Leaves) {
+ KeyRoots.resize(Leaves);
+ std::unordered_set<int> Visited;
+ int K = Leaves - 1;
+ for (SNodeId 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 {
+ 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, 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);
+ }
+ }
+
+ std::vector<std::pair<NodeId, NodeId>> getMatchingNodes() {
+ std::vector<std::pair<NodeId, NodeId>> Matches;
+ std::vector<std::pair<SNodeId, SNodeId>> TreePairs;
+
+ computeTreeDist();
+
+ bool RootNodePair = true;
+
+ TreePairs.emplace_back(S1.getSizeS(), S2.getSizeS());
+
+ while (!TreePairs.empty()) {
+ SNodeId LastRow, LastCol, FirstRow, FirstCol, Row, Col;
+ 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 {
+ SNodeId LMD1 = S1.getLeftMostDescendant(Row);
+ SNodeId 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:
+ /// Simple cost model for edit actions.
+ /// 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) {
+ if (!S1.getNodeS(Id1).hasSameType(S2.getNodeS(Id2)))
+ return std::numeric_limits<double>::max();
+ // TODO Use string editing distance instead
+ if (S1.getValueS(Id1) == S2.getValueS(Id2))
+ return 0;
+ return 1;
+ }
+
+ void computeTreeDist() {
+ for (SNodeId Id1 : S1.KeyRoots)
+ for (SNodeId Id2 : S2.KeyRoots)
+ computeForestDist(Id1, Id2);
+ }
+
+ 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) {
+ ForestDist[D1][LMD2] = ForestDist[D1 - 1][LMD2] + DeletionCost;
+ for (SNodeId D2 = LMD2 + 1; D2 <= Id2; ++D2) {
+ 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 Cmp;
+ std::vector<NodeId> Container;
+ PriorityQueue<NodeId, std::vector<NodeId>, HeightLess> List;
+
+public:
+ PriorityList(const TreeRoot &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)
+ 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);
+ }
+};
+
+bool TreeComparator::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.getValue(Id1) != T2.getValue(Id2))
+ return false;
+ for (size_t Id = 0, E = N1.Children.size(); Id < E; ++Id)
+ if (!isomorphic(N1.Children[Id], N2.Children[Id]))
+ return false;
+ return true;
+}
+
+bool TreeComparator::isMappingAllowed(const Mapping &M, NodeId Id1,
+ NodeId Id2) const {
+ const Node &N1 = T1.getNode(Id1);
+ const Node &N2 = T2.getNode(Id2);
+ if (!N1.hasSameType(N2))
+ return false; // Will only match nodes of the same type.
+ if (M.hasSrc(Id1) || M.hasDst(Id2))
+ return false; // Both sources must not be mapped.
+ NodeId P1 = N1.Parent;
+ NodeId P2 = N2.Parent;
+ bool ParentsSameType = (P1.isInvalid() && P2.isInvalid()) ||
+ (P1.isValid() && P2.isValid() &&
+ T1.getNode(P1).hasSameType(T2.getNode(P2)));
+ return ParentsSameType;
+}
+
+void TreeComparator::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]);
+}
+
+void TreeComparator::addOptimalMapping(Mapping &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.getMatchingNodes();
+ for (const auto Tuple : R) {
+ NodeId Src = Tuple.first;
+ NodeId Dst = Tuple.second;
+ if (isMappingAllowed(M, Src, Dst))
+ M.link(Src, Dst);
+ }
+}
+
+double TreeComparator::getSimilarity(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(M.hasSrc(Id));
+ return 2.0 * CommonDescendants /
+ (T1.getNumberOfDescendants(Id1) + T2.getNumberOfDescendants(Id2));
+}
+
+NodeId TreeComparator::findCandidate(const Mapping &M, NodeId Id1) const {
+ NodeId Candidate;
+ double MaxSimilarity = 0.0;
+ const Node &N1 = T1.getNode(Id1);
+ for (NodeId Id2 = 0, E = T2.getSize(); Id2 < E; ++Id2) {
+ const Node &N2 = T2.getNode(Id2);
+ if (!N1.hasSameType(N2))
+ continue;
+ if (M.hasDst(Id2))
+ continue;
+ double Similarity = getSimilarity(M, Id1, Id2);
+ if (Similarity > MaxSimilarity) {
+ MaxSimilarity = Similarity;
+ Candidate = Id2;
+ }
+ }
+ return Candidate;
+}
+
+void TreeComparator::matchBottomUp(Mapping &M) const {
+ std::vector<NodeId> Postorder = getSubtreePostorder(T1, T1.root());
+ for (NodeId Id1 : Postorder) {
+ if (Id1 == T1.root()) {
+ M.link(T1.root(), T2.root());
+ addOptimalMapping(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.isInvalid() || !isMappingAllowed(M, Id1, Id2) ||
+ getSimilarity(M, Id1, Id2) < MinSimilarity)
+ continue;
+ M.link(Id1, Id2);
+ addOptimalMapping(M, Id1, Id2);
+ }
+}
+
+Mapping TreeComparator::matchTopDown() const {
+ PriorityList L1(T1);
+ PriorityList L2(T2);
+
+ Mapping M(T1.getSize(), T2.getSize());
+
+ 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;
+}
+
+void TreeComparator::computeMapping() {
+ if (IsMappingDone)
+ return;
+ TheMapping = matchTopDown();
+ matchBottomUp(TheMapping);
+ IsMappingDone = true;
+}
+
+std::vector<Match> TreeComparator::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;
+}
+
+std::vector<Change> TreeComparator::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(T1.getNode(Id1).hasSameType(N2) &&
+ "Matched nodes with different kinds.");
+ if (T1.getValue(Id1) != T2.getValue(Id2)) {
+ Changes.emplace_back(Update, Id1, Id2);
+ }
+ continue;
+ }
+ NodeId P2 = N2.Parent;
+ NodeId P1 = M.getSrc(P2);
+ assert(P1.isValid());
+ 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);
+ }
+ for (NodeId Id1 = 0; Id1 < T1.getSize(); ++Id1) {
+ NodeId Id2 = M.getDst(Id1);
+ if (Id2.isInvalid())
+ Changes.emplace_back(Delete, Id1, Id2);
+ }
+ return Changes;
+}
+
+ASTDiff::ASTDiff(ASTContext &Src, ASTContext &Dst)
+ : Comparator(llvm::make_unique<TreeComparator>(Src, Dst)) {}
+
+ASTDiff::~ASTDiff() {}
+
+const TreeRoot &ASTDiff::getSourceTree() { return Comparator->T1; }
+const TreeRoot &ASTDiff::getDestinationTree() { return Comparator->T2; }
+
+void TreeComparator::printChange(raw_ostream &OS, const Change &Chg) const {
+ switch (Chg.Kind) {
+ case Delete:
+ OS << "Delete " << T1.showNode(Chg.Src) << "\n";
+ break;
+ case Update:
+ OS << "Update " << T1.showNode(Chg.Src) << " to " << T2.getValue(Chg.Dst)
+ << "\n";
+ break;
+ case Insert:
+ OS << "Insert " << T2.showNode(Chg.Src) << " into " << T2.showNode(Chg.Dst)
+ << " at " << Chg.Position << "\n";
+ break;
+ case Move:
+ llvm_unreachable("TODO");
+ break;
+ };
+}
+
+void TreeComparator::printMatch(raw_ostream &OS, const Match &M) const {
+ OS << formatv("Match {0} to {1}\n", T1.showNode(M.Src), T2.showNode(M.Dst));
+}
+
+std::vector<Match> ASTDiff::getMatches() {
+ Comparator->computeMapping();
+ return Comparator->getMatches(Comparator->TheMapping);
+}
+
+std::vector<Change> ASTDiff::getChanges() {
+ Comparator->computeMapping();
+ return Comparator->computeChanges(Comparator->TheMapping);
+}
+
+void ASTDiff::printChange(raw_ostream &OS, const Change &Chg) const {
+ Comparator->printChange(OS, Chg);
+}
+
+void ASTDiff::printMatch(raw_ostream &OS, const Match &M) const {
+ Comparator->printMatch(OS, M);
+}
+
+} // end namespace diff
+} // end namespace clang
Index: include/clang/Tooling/ASTDiff/ASTDiff.h
===================================================================
--- /dev/null
+++ include/clang/Tooling/ASTDiff/ASTDiff.h
@@ -0,0 +1,157 @@
+//===- 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"
+
+namespace clang {
+namespace diff {
+
+class TreeComparator;
+class TreeRoot;
+struct Change;
+struct Match;
+
+class ASTDiff {
+public:
+ ASTDiff(ASTContext &Src, ASTContext &Dst);
+ ~ASTDiff();
+
+ const TreeRoot &getSourceTree();
+ const TreeRoot &getDestinationTree();
+
+ // Returns a list of matches.
+ std::vector<Match> getMatches();
+ /// Returns an edit script.
+ std::vector<Change> getChanges();
+
+ // Prints an edit action.
+ void printChange(const Change &Chg) const { printChange(llvm::outs(), Chg); }
+ void printChange(raw_ostream &OS, const Change &Chg) const;
+ void printMatch(const Match &M) const { printMatch(llvm::outs(), M); }
+ void printMatch(raw_ostream &OS, const Match &M) const;
+
+private:
+ std::unique_ptr<TreeComparator> Comparator;
+};
+
+/// Within a tree, this identifies a node by its preorder offset.
+struct NodeId {
+private:
+ static const int InvalidNodeId = -1;
+
+public:
+ int Id;
+
+ NodeId() : Id(InvalidNodeId) {}
+ NodeId(int Id) : Id(Id) {}
+
+ operator int() const { return Id; }
+ NodeId &operator++() { return ++this->Id, *this; }
+ NodeId &operator--() { return --this->Id, *this; }
+
+ bool isValid() const { return Id != InvalidNodeId; }
+ bool isInvalid() const { return !isValid(); }
+};
+
+/// 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;
+ ast_type_traits::DynTypedNode ASTNode;
+ SmallVector<NodeId, 4> Children;
+
+ ast_type_traits::ASTNodeKind getType() const { return ASTNode.getNodeKind(); }
+ bool hasSameType(const Node &Other) const {
+ return getType().isSame(Other.getType());
+ }
+ const StringRef getTypeLabel() const { return getType().asStringRef(); }
+ bool isLeaf() const { return Children.empty(); }
+};
+
+/// Represents the AST of a TranslationUnit.
+class TreeRoot {
+public:
+ ASTContext &AST;
+ std::vector<NodeId> Leaves;
+ // Maps preorder indices to postorder ones.
+ 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); }
+ int getNumberOfDescendants(NodeId Id) const;
+
+ /// Returns the string representation of the node.
+ std::string getValue(NodeId Id) const;
+ /// Return the node as "<type>[: <value>](<postorder-id)"
+ std::string showNode(NodeId Id) const;
+
+ void printTree(NodeId Root = 0) const { printTree(llvm::outs(), Root); }
+ void printTree(raw_ostream &OS, NodeId Root) const;
+
+ void printAsJson() const { printAsJson(llvm::outs()); };
+ void printAsJson(raw_ostream &OS) const;
+
+ void printNodeAsJson(raw_ostream &OS, NodeId Root) const;
+
+private:
+ /// Nodes in preorder.
+ std::vector<Node> Nodes;
+
+ void setLeftMostDescendants();
+};
+
+} // end namespace diff
+} // end namespace clang
+
+#endif
_______________________________________________
cfe-commits mailing list
cfe-commits@lists.llvm.org
http://lists.llvm.org/cgi-bin/mailman/listinfo/cfe-commits
