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 getMatches(); + /// Returns an edit script. + std::vector 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 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 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 Leaves; + // Maps preorder indices to postorder ones. + std::vector 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 "[: ]( Nodes; + + void setLeftMostDescendants(); +}; + +} // end namespace diff +} // end namespace clang + +#endif 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 +#include +#include + +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(Size); + DstToSrc = llvm::make_unique(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 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 getMatches(Mapping &M); + + /// Finds an edit script that converts T1 to T2. + std::vector 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 +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 { + 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::TraverseDecl(D); + return true; + } + bool TraverseStmt(Stmt *S) { + if (isNodeExcluded(Root.AST.getSourceManager(), S)) + return true; + ++Count; + RecursiveASTVisitor::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 { + int Id = 0, Depth = 0; + NodeId Parent; + TreeRoot &Root; + + PreorderVisitor(TreeRoot &Root) : Root(Root) {} + + template std::tuple 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 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::TraverseDecl(D); + PostTraverse(SavedState); + return true; + } + bool TraverseStmt(Stmt *S) { + if (isNodeExcluded(Root.AST.getSourceManager(), S)) + return true; + auto SavedState = PreTraverse(S); + RecursiveASTVisitor::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 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 getSubtreePostorder(const TreeRoot &Tree, + NodeId Root) { + std::vector Postorder; + std::function 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 getSubtreeBfs(const TreeRoot &Tree, NodeId Root) { + std::vector 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()) + return X->getOpcodeStr(); + if (auto *X = DTN.get()) { + CharSourceRange Range(X->getSourceRange(), false); + return Lexer::getSourceText(Range, AST.getSourceManager(), + AST.getLangOpts()); + } + if (auto *X = DTN.get()) { + SmallString<256> Str; + X->getValue().toString(Str, /*Radix=*/10, /*Signed=*/false); + return Str.str(); + } + if (auto *X = DTN.get()) + return X->getString(); + if (auto *X = DTN.get()) + return X->getNameAsString() + "(" + X->getType().getAsString() + ")"; + if (auto *X = DTN.get()) + return ""; + if (auto *X = DTN.get()) + return ""; + std::string Value; + if (auto *X = DTN.get()) { + 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()) + Value += X->getNameAsString() + ";"; + if (auto *X = DTN.get()) + return Value + X->getUnderlyingType().getAsString() + ";"; + if (auto *X = DTN.get()) + return Value; + if (auto *X = DTN.get()) + if (X->getTypeForDecl()) + Value += + X->getTypeForDecl()->getCanonicalTypeInternal().getAsString() + ";"; + if (auto *X = DTN.get()) + return Value; + if (auto *X = DTN.get()) + 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 RootIds; + /// Maps subtree nodes to their leftmost descendants wtihin the subtree. + std::vector LeftMostDescendants; + +public: + std::vector 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 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[]> TreeDist, ForestDist; + +public: + ZsMatcher(const TreeRoot &T1, const TreeRoot &T2, NodeId Id1, NodeId Id2) + : S1(T1, Id1), S2(T2, Id2) { + TreeDist = + llvm::make_unique[]>(S1.getSizeS() + 1); + ForestDist = + llvm::make_unique[]>(S1.getSizeS() + 1); + for (int I = 0, E = S1.getSizeS() + 1; I < E; ++I) { + TreeDist[I] = llvm::make_unique(S2.getSizeS() + 1); + ForestDist[I] = llvm::make_unique(S2.getSizeS() + 1); + } + } + + std::vector> getMatchingNodes() { + std::vector> Matches; + std::vector> 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::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 Container; + PriorityQueue, HeightLess> List; + +public: + PriorityList(const TreeRoot &Tree) + : Tree(Tree), Cmp(Tree), List(Cmp, Container) {} + + void push(NodeId id) { List.push(id); } + + std::vector pop() { + int Max = peekMax(); + std::vector 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> 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 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 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 TreeComparator::getMatches(Mapping &M) { + std::vector 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 TreeComparator::computeChanges(Mapping &M) { + std::vector 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(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 ASTDiff::getMatches() { + Comparator->computeMapping(); + return Comparator->getMatches(Comparator->TheMapping); +} + +std::vector 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: 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/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: 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: 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: 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/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 + DumpAST("ast-dump", + cl::desc("Print the internal representation of the AST as JSON."), + cl::init(false), cl::cat(ClangDiffCategory)); + +static cl::opt 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 SourcePath(cl::Positional, cl::desc(""), + cl::Required, + cl::cat(ClangDiffCategory)); + +static cl::opt DestinationPath(cl::Positional, + cl::desc(""), + cl::Optional, + cl::cat(ClangDiffCategory)); + +static std::unique_ptr getAST(const StringRef Filename) { + std::string ErrorMessage; + std::unique_ptr 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::array Files = {{Filename}}; + ClangTool Tool(*Compilations, Files); + std::vector> 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 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 Src = getAST(SourcePath); + std::unique_ptr 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; +}