Index: include/clang/Tooling/ASTDiff/ASTDiffInternal.h =================================================================== --- include/clang/Tooling/ASTDiff/ASTDiffInternal.h +++ include/clang/Tooling/ASTDiff/ASTDiffInternal.h @@ -100,45 +100,34 @@ 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; - } + Mapping(size_t Size); + + void link(NodeId Src, NodeId Dst); + + NodeId getDst(NodeId Src) const; + NodeId getSrc(NodeId Dst) const; + bool hasSrc(NodeId Src) const; + bool hasDst(NodeId Dst) const; + /* bool hasSrcDst(NodeId Src, NodeId Dst) const; */ + +private: + std::unique_ptr SrcToDst, DstToSrc; +}; + +/// Maps nodes to multiple possible mapping candidates. +class MultiMapping { +public: + size_t Size; + + MultiMapping(int Size1, int Size2); + + void link(NodeId Src, NodeId Dst); + + const SmallVector &getDsts(NodeId Src) const; + const SmallVector &getSrcs(NodeId Dst) const; + bool hasSrc(NodeId Src) const; + bool hasDst(NodeId Dst) const; + bool hasSrcDst(NodeId Src, NodeId Dst) const; private: std::unique_ptr[]> SrcToDst, DstToSrc; @@ -179,6 +168,7 @@ 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); } + // Returns the number of nodes in the subtree, including this one. int getNumberOfDescendants(NodeId Id) const; std::string getNodeValueI(NodeId Id) const; Index: lib/Tooling/ASTDiff/ASTDiff.cpp =================================================================== --- lib/Tooling/ASTDiff/ASTDiff.cpp +++ lib/Tooling/ASTDiff/ASTDiff.cpp @@ -59,10 +59,6 @@ // Returns false if the nodes must not be mached. bool isMatchingPossible(NodeId Id1, NodeId Id2) const; - // Adds all corresponding subtrees of the two nodes to the mapping. - // The two nodes must be isomorphic. - void addIsomorphicSubTrees(Mapping &M, NodeId Id1, NodeId Id2) const; - // Uses an optimal albeit slow algorithm to compute a mapping between two // subtrees, but only if both have fewer nodes than MaxSize. void addOptimalMapping(Mapping &M, NodeId Id1, NodeId Id2) const; @@ -77,6 +73,8 @@ // Tries to match any yet unmapped nodes, in a bottom-up fashion. void matchBottomUp(Mapping &M) const; + Mapping resolveMultiMapping(const MultiMapping &M) const; + const ComparisonOptions &Options; friend class ZsMatcher; @@ -147,7 +145,7 @@ Parent = PreviousParent; --Depth; Node &N = Root.getMutableNode(MyId); - N.RightMostDescendant = Id; + N.RightMostDescendant = Id - 1; if (N.isLeaf()) Root.Leaves.push_back(MyId); N.Height = 1; @@ -568,6 +566,41 @@ } }; +Mapping::Mapping(size_t Size) { + SrcToDst = llvm::make_unique(Size); + DstToSrc = llvm::make_unique(Size); +} + +void Mapping::link(NodeId Src, NodeId Dst) { + SrcToDst[Src] = Dst; + DstToSrc[Dst] = Src; +} + +NodeId Mapping::getDst(NodeId Src) const { return SrcToDst[Src]; } +NodeId Mapping::getSrc(NodeId Dst) const { return DstToSrc[Dst]; } +bool Mapping::hasSrc(NodeId Src) const { return getDst(Src).isValid(); } +bool Mapping::hasDst(NodeId Dst) const { return getSrc(Dst).isValid(); } + +MultiMapping::MultiMapping(int Size1, int Size2) : Size(Size1 + Size2) { + SrcToDst = llvm::make_unique[]>(Size); + DstToSrc = llvm::make_unique[]>(Size); +} + +void MultiMapping::link(NodeId Src, NodeId Dst) { + SrcToDst[Src].push_back(Dst); + DstToSrc[Dst].push_back(Src); +} + +bool MultiMapping::hasSrc(NodeId Src) const { return !getDsts(Src).empty(); } +bool MultiMapping::hasDst(NodeId Dst) const { return !getSrcs(Dst).empty(); } + +const SmallVector &MultiMapping::getDsts(NodeId Src) const { + return SrcToDst[Src]; +} +const SmallVector &MultiMapping::getSrcs(NodeId Dst) const { + return DstToSrc[Dst]; +} + namespace { // Compares nodes by their depth. struct HeightLess { @@ -633,15 +666,13 @@ NodeId Id2) const { assert(isMatchingPossible(Id1, Id2) && "Matching must be possible in the first place."); - if (M.hasSrcDst(Id1, Id2)) + if (M.hasSrc(Id1) || M.hasDst(Id2)) return false; if (Options.EnableMatchingWithUnmatchableParents) return true; - const Node &N1 = T1.getNode(Id1); - const Node &N2 = T2.getNode(Id2); - NodeId P1 = N1.Parent; - NodeId P2 = N2.Parent; // Only allow matching if parents can be matched. + NodeId P1 = T1.getNode(Id1).Parent; + NodeId P2 = T2.getNode(Id2).Parent; return (P1.isInvalid() && P2.isInvalid()) || (P1.isValid() && P2.isValid() && isMatchingPossible(P1, P2)); } @@ -651,16 +682,6 @@ T2.getNode(Id2).ASTNode); } -void ASTDiff::Impl::addIsomorphicSubTrees(Mapping &M, NodeId Id1, - NodeId Id2) const { - assert(isomorphic(Id1, Id2) && "Can only be called on isomorphic subtrees."); - M.link(Id1, Id2); - const Node &N1 = T1.getNode(Id1); - const Node &N2 = T2.getNode(Id2); - for (size_t Id = 0, E = N1.Children.size(); Id < E; ++Id) - addIsomorphicSubTrees(M, N1.Children[Id], N2.Children[Id]); -} - void ASTDiff::Impl::addOptimalMapping(Mapping &M, NodeId Id1, NodeId Id2) const { if (std::max(T1.getNumberOfDescendants(Id1), @@ -735,7 +756,7 @@ PriorityList L1(T1); PriorityList L2(T2); - Mapping M(T1.getSize(), T2.getSize()); + MultiMapping M(T1.getSize(), T2.getSize()); L1.push(T1.root()); L2.push(T2.root()); @@ -757,9 +778,14 @@ H1 = L1.pop(); H2 = L2.pop(); for (NodeId Id1 : H1) { - for (NodeId Id2 : H2) - if (isomorphic(Id1, Id2) && canBeAddedToMapping(M, Id1, Id2)) - addIsomorphicSubTrees(M, Id1, Id2); + for (NodeId Id2 : H2) { + if (!isomorphic(Id1, Id2)) + continue; + for (int I = 0, E = T1.getNumberOfDescendants(Id1); I < E; ++I) { + assert(isMatchingPossible(Id1 + I, Id2 + I)); + M.link(Id1 + I, Id2 + I); + } + } } for (NodeId Id1 : H1) { if (!M.hasSrc(Id1)) @@ -770,7 +796,39 @@ L2.open(Id2); } } - return M; + return resolveMultiMapping(M); +} + +Mapping ASTDiff::Impl::resolveMultiMapping(const MultiMapping &M) const { + Mapping UniqueMapping(M.Size); + // Add all unambiguous matches (the similarity computation uses these). + for (NodeId Src = 0, E = T1.getSize(); Src < E; ++Src) { + if (M.getDsts(Src).size() != 1) + continue; + for (NodeId Dst : M.getDsts(Src)) + UniqueMapping.link(Src, Dst); + } + // For others, choose the destination with the highest similarity to the + // source. + for (NodeId Src = 0, E = T1.getSize(); Src < E; ++Src) { + if (M.getDsts(Src).size() < 2) + continue; + double MaxSimilarity = 0.0; + NodeId Destination; + for (NodeId Dst : M.getDsts(Src)) { + double Similarity = getSimilarity(UniqueMapping, Src, Dst); + if (Similarity < MaxSimilarity) + continue; + MaxSimilarity = Similarity; + Destination = Dst; + } + // Recursively connect all isomorphic subtrees. + for (int I = 0, E = T1.getNumberOfDescendants(Src); I < E; ++I) { + assert(isMatchingPossible(Src + I, Destination + I)); + UniqueMapping.link(Src + I, Destination + I); + } + } + return UniqueMapping; } void ASTDiff::Impl::computeMapping() { @@ -871,7 +929,7 @@ const ComparisonOptions &Options) : DiffImpl(llvm::make_unique(*T1.TreeImpl, *T2.TreeImpl, Options)) {} -ASTDiff::~ASTDiff() {} +ASTDiff::~ASTDiff() = default; SyntaxTree::SyntaxTree(const ASTContext &AST) : TreeImpl(llvm::make_unique(