From c778ea4b266d5fdcf3ab2d2509b19083bc43a91e Mon Sep 17 00:00:00 2001 From: Johannes Altmanninger Date: Sat, 19 Aug 2017 17:53:01 +0000 Subject: [PATCH] [clang-diff] Simplify mapping Summary: Until we find a decent heuristic on how to choose between multiple identical trees, there is no point in supporting multiple mappings. This also enables matching of nodes with parents of different types, because there are many instances where this is appropriate. For example for and foreach statements; functions in the global or other namespaces. Reviewers: arphaman Subscribers: klimek Differential Revision: https://reviews.llvm.org/D36183 git-svn-id: https://llvm.org/svn/llvm-project/cfe/trunk@311251 91177308-0d34-0410-b5e6-96231b3b80d8 --- include/clang/Tooling/ASTDiff/ASTDiff.h | 4 -- lib/Tooling/ASTDiff/ASTDiff.cpp | 74 ++++---------------- test/Tooling/Inputs/clang-diff-basic-src.cpp | 4 +- test/Tooling/clang-diff-basic.cpp | 8 ++- 4 files changed, 25 insertions(+), 65 deletions(-) diff --git a/include/clang/Tooling/ASTDiff/ASTDiff.h b/include/clang/Tooling/ASTDiff/ASTDiff.h index 815a3ab32e..ac33dc42d8 100644 --- a/include/clang/Tooling/ASTDiff/ASTDiff.h +++ b/include/clang/Tooling/ASTDiff/ASTDiff.h @@ -111,10 +111,6 @@ struct ComparisonOptions { /// mapping is computed, unless the size of either subtrees exceeds this. int MaxSize = 100; - /// If this is set to true, nodes that have parents that must not be matched - /// (see NodeComparison) will be allowed to be matched. - bool EnableMatchingWithUnmatchableParents = false; - /// Returns false if the nodes should never be matched. bool isMatchingAllowed(const Node &N1, const Node &N2) const { return N1.getType().isSame(N2.getType()); diff --git a/lib/Tooling/ASTDiff/ASTDiff.cpp b/lib/Tooling/ASTDiff/ASTDiff.cpp index cada8f0178..43c19a7226 100644 --- a/lib/Tooling/ASTDiff/ASTDiff.cpp +++ b/lib/Tooling/ASTDiff/ASTDiff.cpp @@ -34,48 +34,23 @@ 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); + + Mapping(size_t Size) { + 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; + 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 getDst(Src).isValid(); } + bool hasDst(NodeId Dst) const { return getSrc(Dst).isValid(); } + private: - std::unique_ptr[]> SrcToDst, DstToSrc; + std::unique_ptr SrcToDst, DstToSrc; }; } // end anonymous namespace @@ -105,8 +80,6 @@ private: // Returns true if the two subtrees are identical. bool identical(NodeId Id1, NodeId Id2) const; - bool canBeAddedToMapping(const Mapping &M, NodeId Id1, NodeId Id2) const; - // Returns false if the nodes must not be mached. bool isMatchingPossible(NodeId Id1, NodeId Id2) const; @@ -712,23 +685,6 @@ bool ASTDiff::Impl::identical(NodeId Id1, NodeId Id2) const { return true; } -bool ASTDiff::Impl::canBeAddedToMapping(const Mapping &M, NodeId Id1, - NodeId Id2) const { - assert(isMatchingPossible(Id1, Id2) && - "Matching must be possible in the first place."); - if (M.hasSrcDst(Id1, 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. - return (P1.isInvalid() && P2.isInvalid()) || - (P1.isValid() && P2.isValid() && isMatchingPossible(P1, P2)); -} - bool ASTDiff::Impl::isMatchingPossible(NodeId Id1, NodeId Id2) const { return Options.isMatchingAllowed(T1.getNode(Id1), T2.getNode(Id2)); } @@ -751,7 +707,7 @@ void ASTDiff::Impl::addOptimalMapping(Mapping &M, NodeId Id1, for (const auto Tuple : R) { NodeId Src = Tuple.first; NodeId Dst = Tuple.second; - if (canBeAddedToMapping(M, Src, Dst)) + if (!M.hasSrc(Src) && !M.hasDst(Dst)) M.link(Src, Dst); } } @@ -804,7 +760,7 @@ void ASTDiff::Impl::matchBottomUp(Mapping &M) const { if (Matched || !MatchedChildren) continue; NodeId Id2 = findCandidate(M, Id1); - if (Id2.isValid() && canBeAddedToMapping(M, Id1, Id2)) { + if (Id2.isValid()) { M.link(Id1, Id2); addOptimalMapping(M, Id1, Id2); } @@ -815,7 +771,7 @@ Mapping ASTDiff::Impl::matchTopDown() const { PriorityList L1(T1); PriorityList L2(T2); - Mapping M(T1.getSize(), T2.getSize()); + Mapping M(T1.getSize() + T2.getSize()); L1.push(T1.getRootId()); L2.push(T2.getRootId()); @@ -838,7 +794,7 @@ Mapping ASTDiff::Impl::matchTopDown() const { H2 = L2.pop(); for (NodeId Id1 : H1) { for (NodeId Id2 : H2) { - if (identical(Id1, Id2) && canBeAddedToMapping(M, Id1, Id2)) { + if (identical(Id1, Id2) && !M.hasSrc(Id1) && !M.hasDst(Id2)) { for (int I = 0, E = T1.getNumberOfDescendants(Id1); I < E; ++I) M.link(Id1 + I, Id2 + I); } diff --git a/test/Tooling/Inputs/clang-diff-basic-src.cpp b/test/Tooling/Inputs/clang-diff-basic-src.cpp index 7a7b98675b..8f15232916 100644 --- a/test/Tooling/Inputs/clang-diff-basic-src.cpp +++ b/test/Tooling/Inputs/clang-diff-basic-src.cpp @@ -28,4 +28,6 @@ public: } void m() { int x = 0 + 0 + 0; } -int um = 1 + 2 + 3; +int um = 1 * 2 + 3; + +void f1() {{ (void) __func__;;; }} diff --git a/test/Tooling/clang-diff-basic.cpp b/test/Tooling/clang-diff-basic.cpp index 0e375fb1b0..aa78d5dc52 100644 --- a/test/Tooling/clang-diff-basic.cpp +++ b/test/Tooling/clang-diff-basic.cpp @@ -42,10 +42,16 @@ class X { }; } -// CHECK: Move DeclStmt{{.*}} into CompoundStmt +// CHECK: Move CompoundStmt{{.*}} into CompoundStmt void m() { { int x = 0 + 0 + 0; } } // CHECK: Update and Move IntegerLiteral: 7{{.*}} into BinaryOperator: +({{.*}}) at 1 int um = 1 + 7; +namespace { +// match with parents of different type +// CHECK: Match FunctionDecl: f1{{.*}} to FunctionDecl: f1 +void f1() {{ (void) __func__;;; }} +} + // CHECK: Delete AccessSpecDecl: public // CHECK: Delete CXXMethodDecl -- 2.40.0