[clang-diff] Simplify mapping

[johannes]

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.

[johannes]

parent changed

[johannes]

[johannes]

merge parent changes

[arphaman]

include/clang/Tooling/ASTDiff/ASTDiff.h

114 ↗

(On Diff #109504)

It doesn't look like this field is used in this patch, please remove it or move it to a different patch.

[johannes]

remove unused

[arphaman]

LGTM

cfe/trunk/include/clang/Tooling/ASTDiff/ASTDiff.h

struct ComparisonOptions {
   /// 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;
 
-  /// 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());
   }
 };
 
 } // end namespace diff
 } // end namespace clang
 
 #endif

cfe/trunk/lib/Tooling/ASTDiff/ASTDiff.cpp

 
 namespace {
 /// 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<SmallVector<NodeId, 2>[]>(Size);
-    DstToSrc = llvm::make_unique<SmallVector<NodeId, 2>[]>(Size);
+
+  Mapping(size_t Size) {
+    SrcToDst = llvm::make_unique<NodeId[]>(Size);
+    DstToSrc = llvm::make_unique<NodeId[]>(Size);
   }
 
   void link(NodeId Src, NodeId Dst) {
-    SrcToDst[Src].push_back(Dst);
-    DstToSrc[Dst].push_back(Src);
+    SrcToDst[Src] = Dst, DstToSrc[Dst] = 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<NodeId, 2> &getAllDsts(NodeId Src) const {
-    return SrcToDst[Src];
-  }
-  const SmallVector<NodeId, 2> &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;
-  }
+  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<SmallVector<NodeId, 2>[]> SrcToDst, DstToSrc;
+  std::unique_ptr<NodeId[]> SrcToDst, DstToSrc;
 };
 } // end anonymous namespace
 
 class ASTDiff::Impl {
 public:
   SyntaxTree::Impl &T1, &T2;
   Mapping TheMapping;
 
NodeId getMapped(const std::unique_ptr<SyntaxTree::Impl> &Tree,
     assert(&*Tree == &T2 && "Invalid tree.");
     return TheMapping.getSrc(Id);
   }
 
 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;
 
   // Returns true if the nodes' parents are matched.
   bool haveSameParents(const 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.
if (N1.Children.size() != N2.Children.size() ||
       T1.getNodeValue(Id1) != T2.getNodeValue(Id2))
     return false;
   for (size_t Id = 0, E = N1.Children.size(); Id < E; ++Id)
     if (!identical(N1.Children[Id], N2.Children[Id]))
       return false;
   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));
 }
 
 bool ASTDiff::Impl::haveSameParents(const Mapping &M, NodeId Id1,
                                     NodeId Id2) const {
   NodeId P1 = T1.getNode(Id1).Parent;
   NodeId P2 = T2.getNode(Id2).Parent;
   return (P1.isInvalid() && P2.isInvalid()) ||
          (P1.isValid() && P2.isValid() && M.getDst(P1) == P2);
 }
 
 void ASTDiff::Impl::addOptimalMapping(Mapping &M, NodeId Id1,
                                       NodeId Id2) const {
   if (std::max(T1.getNumberOfDescendants(Id1),
                T2.getNumberOfDescendants(Id2)) >= Options.MaxSize)
     return;
   ZhangShashaMatcher Matcher(*this, T1, T2, Id1, Id2);
   std::vector<std::pair<NodeId, NodeId>> R = Matcher.getMatchingNodes();
   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);
   }
 }
 
 double ASTDiff::Impl::getSimilarity(const Mapping &M, NodeId Id1,
                                     NodeId Id2) const {
   if (Id1.isInvalid() || Id2.isInvalid())
     return 0.0;
for (NodeId Id1 : Postorder) {
     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.isValid() && canBeAddedToMapping(M, Id1, Id2)) {
+    if (Id2.isValid()) {
       M.link(Id1, Id2);
       addOptimalMapping(M, Id1, Id2);
     }
   }
 }
 
 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());
 
   int Max1, Max2;
   while (std::min(Max1 = L1.peekMax(), Max2 = L2.peekMax()) >
          Options.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<NodeId> H1, H2;
     H1 = L1.pop();
     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);
         }
       }
     }
     for (NodeId Id1 : H1) {
       if (!M.hasSrc(Id1))
         L1.open(Id1);

cfe/trunk/test/Tooling/Inputs/clang-diff-basic-src.cpp

 public:
   X(){};
 
   int id(int i) { return i; }
 };
 }
 
 void m() { int x = 0 + 0 + 0; }
-int um = 1 + 2 + 3;
+int um = 1 * 2 + 3;
+
+void f1() {{ (void) __func__;;; }}

cfe/trunk/test/Tooling/clang-diff-basic.cpp

const char *foo(int i) {
     else if (i == -1)
       return "foo";
     return 0;
   }
   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