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; Index: lib/Tooling/ASTDiff/ASTDiff.cpp =================================================================== --- lib/Tooling/ASTDiff/ASTDiff.cpp +++ lib/Tooling/ASTDiff/ASTDiff.cpp @@ -61,7 +61,7 @@ // 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; + void addIsomorphicSubTrees(MultiMapping &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. @@ -77,6 +77,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; @@ -568,6 +570,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 +670,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,7 +686,7 @@ T2.getNode(Id2).ASTNode); } -void ASTDiff::Impl::addIsomorphicSubTrees(Mapping &M, NodeId Id1, +void ASTDiff::Impl::addIsomorphicSubTrees(MultiMapping &M, NodeId Id1, NodeId Id2) const { assert(isomorphic(Id1, Id2) && "Can only be called on isomorphic subtrees."); M.link(Id1, Id2); @@ -735,7 +770,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 +792,10 @@ H1 = L1.pop(); H2 = L2.pop(); for (NodeId Id1 : H1) { - for (NodeId Id2 : H2) - if (isomorphic(Id1, Id2) && canBeAddedToMapping(M, Id1, Id2)) + for (NodeId Id2 : H2) { + if (isomorphic(Id1, Id2)) addIsomorphicSubTrees(M, Id1, Id2); + } } for (NodeId Id1 : H1) { if (!M.hasSrc(Id1)) @@ -770,7 +806,35 @@ 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; + } + UniqueMapping.link(Src, Destination); + } + return UniqueMapping; } void ASTDiff::Impl::computeMapping() { @@ -871,7 +935,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(