From 298225638768903f20a9686991ae8fe39f3a0158 Mon Sep 17 00:00:00 2001 From: Johannes Altmanninger Date: Tue, 1 Aug 2017 20:17:40 +0000 Subject: [PATCH] [clang-diff] Move data declarations to the public header git-svn-id: https://llvm.org/svn/llvm-project/cfe/trunk@309737 91177308-0d34-0410-b5e6-96231b3b80d8 --- include/clang/Tooling/ASTDiff/ASTDiff.h | 51 ++++-- .../clang/Tooling/ASTDiff/ASTDiffInternal.h | 148 +----------------- lib/Tooling/ASTDiff/ASTDiff.cpp | 123 ++++++++++++++- 3 files changed, 157 insertions(+), 165 deletions(-) diff --git a/include/clang/Tooling/ASTDiff/ASTDiff.h b/include/clang/Tooling/ASTDiff/ASTDiff.h index c3cba64112..feeefad793 100644 --- a/include/clang/Tooling/ASTDiff/ASTDiff.h +++ b/include/clang/Tooling/ASTDiff/ASTDiff.h @@ -25,7 +25,42 @@ namespace clang { namespace diff { -class SyntaxTree; +/// 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(); } + const StringRef getTypeLabel() const { return getType().asStringRef(); } + bool isLeaf() const { return Children.empty(); } +}; class ASTDiff { public: @@ -58,6 +93,9 @@ public: template SyntaxTree(T *Node, const ASTContext &AST) : TreeImpl(llvm::make_unique(this, Node, AST)) {} + ~SyntaxTree(); + + const Node &getNode(NodeId Id) const; /// Serialize the node attributes to a string representation. This should /// uniquely distinguish nodes of the same kind. Note that this function just @@ -89,17 +127,6 @@ struct ComparisonOptions { bool isMatchingAllowed(const DynTypedNode &N1, const DynTypedNode &N2) const { return N1.getNodeKind().isSame(N2.getNodeKind()); } - - /// Returns zero if the nodes are considered to be equal. Returns a value - /// indicating the editing distance between the nodes otherwise. - /// There is no need to consider nodes that cannot be matched as input for - /// this function (see isMatchingAllowed). - double getNodeDistance(const SyntaxTree &T1, const DynTypedNode &N1, - const SyntaxTree &T2, const DynTypedNode &N2) const { - if (T1.getNodeValue(N1) == T2.getNodeValue(N2)) - return 0; - return 1; - } }; } // end namespace diff diff --git a/include/clang/Tooling/ASTDiff/ASTDiffInternal.h b/include/clang/Tooling/ASTDiff/ASTDiffInternal.h index a0d0fc3471..150c280dc2 100644 --- a/include/clang/Tooling/ASTDiff/ASTDiffInternal.h +++ b/include/clang/Tooling/ASTDiff/ASTDiffInternal.h @@ -20,8 +20,9 @@ namespace diff { using DynTypedNode = ast_type_traits::DynTypedNode; -struct ComparisonOptions; class SyntaxTree; +class SyntaxTreeImpl; +struct ComparisonOptions; /// Within a tree, this identifies a node by its preorder offset. struct NodeId { @@ -42,151 +43,6 @@ public: bool isInvalid() const { return Id == InvalidNodeId; } }; -/// This represents a match between two nodes in the source and destination -/// trees, meaning that they are likely to be related. -struct Match { - NodeId Src, Dst; -}; - -enum ChangeKind { - Delete, // (Src): delete node Src. - Update, // (Src, Dst): update the value of node Src to match Dst. - Insert, // (Src, Dst, Pos): insert Src as child of Dst at offset Pos. - Move // (Src, Dst, Pos): move Src to be a child of Dst at offset Pos. -}; - -struct Change { - ChangeKind Kind; - NodeId Src, Dst; - size_t Position; - - Change(ChangeKind Kind, NodeId Src, NodeId Dst, size_t Position) - : Kind(Kind), Src(Src), Dst(Dst), Position(Position) {} - Change(ChangeKind Kind, NodeId Src) : Kind(Kind), Src(Src) {} - Change(ChangeKind Kind, NodeId Src, NodeId Dst) - : Kind(Kind), Src(Src), Dst(Dst) {} -}; - -/// Represents a Clang AST node, alongside some additional information. -struct Node { - NodeId Parent, LeftMostDescendant, RightMostDescendant; - int Depth, Height; - DynTypedNode ASTNode; - SmallVector Children; - - ast_type_traits::ASTNodeKind getType() const { return ASTNode.getNodeKind(); } - const StringRef getTypeLabel() const { return getType().asStringRef(); } - bool isLeaf() const { return Children.empty(); } -}; - -/// Maps nodes of the left tree to ones on the right, and vice versa. -class Mapping { -public: - Mapping() = default; - Mapping(Mapping &&Other) = default; - Mapping &operator=(Mapping &&Other) = default; - Mapping(int Size1, int Size2) { - // Maximum possible size after patching one tree. - int Size = Size1 + Size2; - SrcToDst = llvm::make_unique[]>(Size); - DstToSrc = llvm::make_unique[]>(Size); - } - - void link(NodeId Src, NodeId Dst) { - SrcToDst[Src].push_back(Dst); - DstToSrc[Dst].push_back(Src); - } - - NodeId getDst(NodeId Src) const { - if (hasSrc(Src)) - return SrcToDst[Src][0]; - return NodeId(); - } - NodeId getSrc(NodeId Dst) const { - if (hasDst(Dst)) - return DstToSrc[Dst][0]; - return NodeId(); - } - const SmallVector &getAllDsts(NodeId Src) const { - return SrcToDst[Src]; - } - const SmallVector &getAllSrcs(NodeId Dst) const { - return DstToSrc[Dst]; - } - bool hasSrc(NodeId Src) const { return !SrcToDst[Src].empty(); } - bool hasDst(NodeId Dst) const { return !DstToSrc[Dst].empty(); } - bool hasSrcDst(NodeId Src, NodeId Dst) const { - for (NodeId DstId : SrcToDst[Src]) - if (DstId == Dst) - return true; - for (NodeId SrcId : DstToSrc[Dst]) - if (SrcId == Src) - return true; - return false; - } - -private: - std::unique_ptr[]> SrcToDst, DstToSrc; -}; - -/// Represents the AST of a TranslationUnit. -class SyntaxTreeImpl { -public: - /// Constructs a tree from the entire translation unit. - SyntaxTreeImpl(SyntaxTree *Parent, const ASTContext &AST); - /// Constructs a tree from an AST node. - SyntaxTreeImpl(SyntaxTree *Parent, Decl *N, const ASTContext &AST); - SyntaxTreeImpl(SyntaxTree *Parent, Stmt *N, const ASTContext &AST); - template - SyntaxTreeImpl( - SyntaxTree *Parent, - typename std::enable_if::value, T>::type *Node, - const ASTContext &AST) - : SyntaxTreeImpl(Parent, dyn_cast(Node), AST) {} - template - SyntaxTreeImpl( - SyntaxTree *Parent, - typename std::enable_if::value, T>::type *Node, - const ASTContext &AST) - : SyntaxTreeImpl(Parent, dyn_cast(Node), AST) {} - - SyntaxTree *Parent; - const ASTContext &AST; - std::vector Leaves; - // Maps preorder indices to postorder ones. - std::vector PostorderIds; - - int getSize() const { return Nodes.size(); } - NodeId root() const { return 0; } - - const Node &getNode(NodeId Id) const { return Nodes[Id]; } - Node &getMutableNode(NodeId Id) { return Nodes[Id]; } - bool isValidNodeId(NodeId Id) const { return Id >= 0 && Id < getSize(); } - void addNode(Node &N) { Nodes.push_back(N); } - int getNumberOfDescendants(NodeId Id) const; - bool isInSubtree(NodeId Id, NodeId SubtreeRoot) const; - - std::string getNodeValueImpl(NodeId Id) const; - std::string getNodeValueImpl(const DynTypedNode &DTN) const; - /// Prints the node as "[: ]( Nodes; - - void initTree(); - void setLeftMostDescendants(); -}; - } // end namespace diff } // end namespace clang #endif diff --git a/lib/Tooling/ASTDiff/ASTDiff.cpp b/lib/Tooling/ASTDiff/ASTDiff.cpp index 1f30711db4..db84a613d7 100644 --- a/lib/Tooling/ASTDiff/ASTDiff.cpp +++ b/lib/Tooling/ASTDiff/ASTDiff.cpp @@ -27,6 +27,56 @@ using namespace clang; namespace clang { namespace diff { +/// Maps nodes of the left tree to ones on the right, and vice versa. +class Mapping { +public: + Mapping() = default; + Mapping(Mapping &&Other) = default; + Mapping &operator=(Mapping &&Other) = default; + Mapping(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].push_back(Dst); + DstToSrc[Dst].push_back(Src); + } + + NodeId getDst(NodeId Src) const { + if (hasSrc(Src)) + return SrcToDst[Src][0]; + return NodeId(); + } + NodeId getSrc(NodeId Dst) const { + if (hasDst(Dst)) + return DstToSrc[Dst][0]; + return NodeId(); + } + const SmallVector &getAllDsts(NodeId Src) const { + return SrcToDst[Src]; + } + const SmallVector &getAllSrcs(NodeId Dst) const { + return DstToSrc[Dst]; + } + bool hasSrc(NodeId Src) const { return !SrcToDst[Src].empty(); } + bool hasDst(NodeId Dst) const { return !DstToSrc[Dst].empty(); } + bool hasSrcDst(NodeId Src, NodeId Dst) const { + for (NodeId DstId : SrcToDst[Src]) + if (DstId == Dst) + return true; + for (NodeId SrcId : DstToSrc[Dst]) + if (SrcId == Src) + return true; + return false; + } + +private: + std::unique_ptr[]> SrcToDst, DstToSrc; +}; + class ASTDiff::Impl { public: SyntaxTreeImpl &T1, &T2; @@ -82,6 +132,64 @@ private: friend class ZhangShashaMatcher; }; +/// Represents the AST of a TranslationUnit. +class SyntaxTreeImpl { +public: + /// Constructs a tree from the entire translation unit. + SyntaxTreeImpl(SyntaxTree *Parent, const ASTContext &AST); + /// Constructs a tree from an AST node. + SyntaxTreeImpl(SyntaxTree *Parent, Decl *N, const ASTContext &AST); + SyntaxTreeImpl(SyntaxTree *Parent, Stmt *N, const ASTContext &AST); + template + SyntaxTreeImpl( + SyntaxTree *Parent, + typename std::enable_if::value, T>::type *Node, + const ASTContext &AST) + : SyntaxTreeImpl(Parent, dyn_cast(Node), AST) {} + template + SyntaxTreeImpl( + SyntaxTree *Parent, + typename std::enable_if::value, T>::type *Node, + const ASTContext &AST) + : SyntaxTreeImpl(Parent, dyn_cast(Node), AST) {} + + SyntaxTree *Parent; + const ASTContext &AST; + std::vector Leaves; + // Maps preorder indices to postorder ones. + std::vector PostorderIds; + + int getSize() const { return Nodes.size(); } + NodeId root() const { return 0; } + + const Node &getNode(NodeId Id) const { return Nodes[Id]; } + Node &getMutableNode(NodeId Id) { return Nodes[Id]; } + bool isValidNodeId(NodeId Id) const { return Id >= 0 && Id < getSize(); } + void addNode(Node &N) { Nodes.push_back(N); } + int getNumberOfDescendants(NodeId Id) const; + bool isInSubtree(NodeId Id, NodeId SubtreeRoot) const; + + std::string getNodeValueImpl(NodeId Id) const; + std::string getNodeValueImpl(const DynTypedNode &DTN) const; + /// Prints the node as "[: ]( Nodes; + + void initTree(); + void setLeftMostDescendants(); +}; + template static bool isNodeExcluded(const SourceManager &SrcMgr, T *N) { if (!N) @@ -402,6 +510,9 @@ public: NodeId getPostorderOffset() const { return Tree.PostorderIds[getIdInRoot(SNodeId(1))]; } + std::string getNodeValue(SNodeId Id) const { + return Tree.getNodeValueImpl(getIdInRoot(Id)); + } private: /// Returns the number of leafs in the subtree. @@ -527,12 +638,9 @@ private: static constexpr double InsertionCost = 1; double getUpdateCost(SNodeId Id1, SNodeId Id2) { - const DynTypedNode &DTN1 = S1.getNode(Id1).ASTNode, - &DTN2 = S2.getNode(Id2).ASTNode; - if (!DiffImpl.Options.isMatchingAllowed(DTN1, DTN2)) + if (!DiffImpl.isMatchingPossible(S1.getIdInRoot(Id1), S2.getIdInRoot(Id2))) return std::numeric_limits::max(); - return DiffImpl.Options.getNodeDistance(*DiffImpl.T1.Parent, DTN1, - *DiffImpl.T2.Parent, DTN2); + return S1.getNodeValue(Id1) != S2.getNodeValue(Id2); } void computeTreeDist() { @@ -624,8 +732,7 @@ bool ASTDiff::Impl::isomorphic(NodeId Id1, NodeId Id2) const { const Node &N2 = T2.getNode(Id2); if (N1.Children.size() != N2.Children.size() || !isMatchingPossible(Id1, Id2) || - Options.getNodeDistance(*T1.Parent, N1.ASTNode, *T2.Parent, N2.ASTNode) != - 0) + T1.getNodeValueImpl(Id1) != T2.getNodeValueImpl(Id2)) return false; for (size_t Id = 0, E = N1.Children.size(); Id < E; ++Id) if (!isomorphic(N1.Children[Id], N2.Children[Id])) @@ -900,6 +1007,8 @@ void ASTDiff::printMatch(raw_ostream &OS, const Match &M) const { DiffImpl->printMatchImpl(OS, M); } +SyntaxTree::~SyntaxTree() = default; + void SyntaxTree::printAsJson(raw_ostream &OS) { TreeImpl->printAsJsonImpl(OS); } std::string SyntaxTree::getNodeValue(const DynTypedNode &DTN) const { -- 2.40.0