[clang-diff] Fix some errors and inconsistencies

[johannes]

Summary

Fix to the computation of the rightmost descendant. Prevents root
nodes from being mapped if they are already mapped. This only makes a
difference when we compare AST Nodes other than entire translation units, a
feature which still has to be tested.

[arphaman]

Is this an NFC patch or does it have an impact on the produced results? If yes, can you come up with a test that ensures that the new results are verified?

include/clang/Tooling/ASTDiff/ASTDiff.h

96

It might be better to add a move constructor which would disable copy constructors.

[johannes]

include/clang/Tooling/ASTDiff/ASTDiff.h

96

ASTDiff::getMapped internally uses the address of the SyntaxTree that is passed as parameter.
So the tree must be exactly the same as the one that is passed to the constructor of ASTDiff.

This is quite bad. I will change ASTDiff::getMapped to accept a boolean or split it into two methods
Should I still add a move constructor?

[arphaman]

include/clang/Tooling/ASTDiff/ASTDiff.h

96

Can't you just use the TreeImpl pointer value? That should be the same even after you've moved SyntaxTree with the move constructor.

[johannes]

move most functional changes to other commits
move constructor for Syntaxtree

[johannes]

include/clang/Tooling/ASTDiff/ASTDiff.h

96

ok perfect

[arphaman]

LGTM. Although I'm not 100% sure it's fully NFC, so if you can't come up with a test please justify why.

[johannes]

In D36176#830341, @arphaman wrote:

LGTM. Although I'm not 100% sure it's fully NFC, so if you can't come up with a test please justify why.

There are changes that affect the output.
Firstly the computation of the rightmost descendant; the added assertion fails every time with the old version.
Secondly, the change around line 811 prevents root nodes from being mapped if they are already mapped. When comparing translation units this happens only if the two trees are identical (in this case the output would not change). Otherwise, it would require some change in the client to demonstrate how the behaviour changed. One needs to compare AST Nodes other than entire translation units. At some point there will be something that uses this feature so we cover it too (or remove the feature). So I'd keep it like this

[arphaman]

Ok, please include this info in the commit message.

[johannes]

update commit message

include/clang/Tooling/ASTDiff/ASTDiff.h

 class SyntaxTree {
 public:
   /// Constructs a tree from a translation unit.
   SyntaxTree(const ASTContext &AST);
   /// Constructs a tree from any AST node.
   template <class T>
   SyntaxTree(T *Node, const ASTContext &AST)
       : TreeImpl(llvm::make_unique<Impl>(this, Node, AST)) {}
+  SyntaxTree(SyntaxTree &&Other) = default;
   ~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
   /// returns a representation of the node value, not considering descendants.
   std::string getNodeValue(const DynTypedNode &DTN) const;

include/clang/Tooling/ASTDiff/ASTDiffInternal.h

 //===- ASTDiffInternal.h --------------------------------------*- C++ -*- -===//
 //
 //
 //                     The LLVM Compiler Infrastructure
 //
 // This file is distributed under the University of Illinois Open Source
 // License. See LICENSE.TXT for details.
 //
 //===----------------------------------------------------------------------===//
 
 #ifndef LLVM_CLANG_TOOLING_ASTDIFF_ASTDIFFINTERNAL_H
 #define LLVM_CLANG_TOOLING_ASTDIFF_ASTDIFFINTERNAL_H
 
-#include <utility>
-
 #include "clang/AST/ASTTypeTraits.h"
 
 namespace clang {
 namespace diff {
 
 using DynTypedNode = ast_type_traits::DynTypedNode;
 
 class SyntaxTree;

lib/Tooling/ASTDiff/ASTDiff.cpp

 #include <unordered_set>
 
 using namespace llvm;
 using namespace clang;
 
 namespace clang {
 namespace diff {
 
+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.
for (NodeId SrcId : DstToSrc[Dst])
       if (SrcId == Src)
         return true;
     return false;
   }
 
 private:
   std::unique_ptr<SmallVector<NodeId, 2>[]> SrcToDst, DstToSrc;
 };
+} // end anonymous namespace
 
 class ASTDiff::Impl {
 public:
   SyntaxTree::Impl &T1, &T2;
   bool IsMappingDone = false;
   Mapping TheMapping;
 
   Impl(SyntaxTree::Impl &T1, SyntaxTree::Impl &T2,
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;
 
-  // Adds all corresponding subtrees of the two nodes to the mapping.
-  // The two nodes must be identical.
-  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;
 
   // Computes the ratio of common descendants between the two nodes.
   // Descendants are only considered to be equal when they are mapped in M.
   double getSimilarity(const Mapping &M, NodeId Id1, NodeId Id2) const;
 
struct PreorderVisitor : public RecursiveASTVisitor<PreorderVisitor> {
   }
   void PostTraverse(std::tuple<NodeId, NodeId> State) {
     NodeId MyId, PreviousParent;
     std::tie(MyId, PreviousParent) = State;
     assert(MyId.isValid() && "Expecting to only traverse valid nodes.");
     Parent = PreviousParent;
     --Depth;
     Node &N = Tree.getMutableNode(MyId);
-    N.RightMostDescendant = Id;
+    N.RightMostDescendant = Id - 1;
+    assert(N.RightMostDescendant >= 0 &&
+           N.RightMostDescendant < Tree.getSize() &&
+           "Rightmost descendant must be a valid tree node.");
     if (N.isLeaf())
       Tree.Leaves.push_back(MyId);
     N.Height = 1;
     for (NodeId Child : N.Children)
       N.Height = std::max(N.Height, 1 + Tree.getNode(Child).Height);
   }
   bool TraverseDecl(Decl *D) {
     if (isNodeExcluded(Tree.AST.getSourceManager(), D))
static std::vector<NodeId> getSubtreeBfs(const SyntaxTree::Impl &Tree,
   return Ids;
 }
 
 int SyntaxTree::Impl::getNumberOfDescendants(NodeId Id) const {
   return getNode(Id).RightMostDescendant - Id + 1;
 }
 
 bool SyntaxTree::Impl::isInSubtree(NodeId Id, NodeId SubtreeRoot) const {
-  NodeId Lower = SubtreeRoot;
-  NodeId Upper = getNode(SubtreeRoot).RightMostDescendant;
-  return Id >= Lower && Id <= Upper;
+  return Id >= SubtreeRoot && Id <= getNode(SubtreeRoot).RightMostDescendant;
 }
 
 std::string SyntaxTree::Impl::getNodeValue(NodeId Id) const {
   return getNodeValue(getNode(Id).ASTNode);
 }
 
 std::string SyntaxTree::Impl::getNodeValue(const DynTypedNode &DTN) const {
   if (auto *X = DTN.get<BinaryOperator>())
while (!TreePairs.empty()) {
           }
         }
       }
     }
     return Matches;
   }
 
 private:
-  /// Simple cost model for edit actions.
+  /// We use a simple cost model for edit actions, which seems good enough.
+  /// Simple cost model for edit actions. This seems to make the matching
+  /// algorithm perform reasonably well.
   /// The values range between 0 and 1, or infinity if this edit action should
   /// always be avoided.
-
-  /// These costs could be modified to better model the estimated cost of /
-  /// inserting / deleting the current node.
   static constexpr double DeletionCost = 1;
   static constexpr double InsertionCost = 1;
 
   double getUpdateCost(SNodeId Id1, SNodeId Id2) {
     if (!DiffImpl.isMatchingPossible(S1.getIdInRoot(Id1), S2.getIdInRoot(Id2)))
       return std::numeric_limits<double>::max();
     return S1.getNodeValue(Id1) != S2.getNodeValue(Id2);
   }
struct HeightLess {
   const SyntaxTree::Impl &Tree;
   HeightLess(const SyntaxTree::Impl &Tree) : Tree(Tree) {}
   bool operator()(NodeId Id1, NodeId Id2) const {
     return Tree.getNode(Id1).Height < Tree.getNode(Id2).Height;
   }
 };
 } // end anonymous namespace
 
+namespace {
 // Priority queue for nodes, sorted descendingly by their height.
 class PriorityList {
   const SyntaxTree::Impl &Tree;
   HeightLess Cmp;
   std::vector<NodeId> Container;
   PriorityQueue<NodeId, std::vector<NodeId>, HeightLess> List;
 
 public:
if (List.empty())
       return 0;
     return Tree.getNode(List.top()).Height;
   }
   void open(NodeId Id) {
     for (NodeId Child : Tree.getNode(Id).Children)
       push(Child);
   }
 };
+} // end anonymous namespace
 
 bool ASTDiff::Impl::identical(NodeId Id1, NodeId Id2) const {
   const Node &N1 = T1.getNode(Id1);
   const Node &N2 = T2.getNode(Id2);
   if (N1.Children.size() != N2.Children.size() ||
       !isMatchingPossible(Id1, Id2) ||
       T1.getNodeValue(Id1) != T2.getNodeValue(Id2))
     return false;
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).ASTNode,
                                    T2.getNode(Id2).ASTNode);
 }
 
-void ASTDiff::Impl::addIsomorphicSubTrees(Mapping &M, NodeId Id1,
-                                          NodeId Id2) const {
-  assert(identical(Id1, Id2) && "Can only be called on identical 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),
                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 ASTDiff::Impl::findCandidate(const Mapping &M, NodeId Id1) const {
   NodeId Candidate;
   double HighestSimilarity = 0.0;
   for (NodeId Id2 = 0, E = T2.getSize(); Id2 < E; ++Id2) {
     if (!isMatchingPossible(Id1, Id2))
       continue;
     if (M.hasDst(Id2))
       continue;
     double Similarity = getSimilarity(M, Id1, Id2);
-    if (Similarity > HighestSimilarity) {
+    if (Similarity >= Options.MinSimilarity && Similarity > HighestSimilarity) {
       HighestSimilarity = Similarity;
       Candidate = Id2;
     }
   }
   return Candidate;
 }
 
 void ASTDiff::Impl::matchBottomUp(Mapping &M) const {
   std::vector<NodeId> Postorder = getSubtreePostorder(T1, T1.getRootId());
   for (NodeId Id1 : Postorder) {
-    if (Id1 == T1.getRootId()) {
+    if (Id1 == T1.getRootId() && !M.hasSrc(T1.getRootId()) &&
+        !M.hasDst(T2.getRootId())) {
       if (isMatchingPossible(T1.getRootId(), T2.getRootId())) {
         M.link(T1.getRootId(), T2.getRootId());
         addOptimalMapping(M, T1.getRootId(), T2.getRootId());
       }
       break;
     }
     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.isInvalid() || !canBeAddedToMapping(M, Id1, Id2) ||
-        getSimilarity(M, Id1, Id2) < Options.MinSimilarity)
-      continue;
+    if (Id2.isValid() && canBeAddedToMapping(M, Id1, Id2)) {
       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());
 
   L1.push(T1.getRootId());
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))
-          addIsomorphicSubTrees(M, Id1, Id2);
+      for (NodeId Id2 : H2) {
+        if (identical(Id1, Id2) && canBeAddedToMapping(M, Id1, 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);
     }
     for (NodeId Id2 : H2) {
       if (!M.hasDst(Id2))
         L2.open(Id2);