[clang-diff] Split findPositionInParent

[johannes]

Summary

This makes findPositionInParent() a member of Node. Additionally, the
function that computes the new position that is dependent on
insertions and deletions of siblings, is now a member of
ASTDiff::Impl.

include/clang/Tooling/ASTDiff/ASTDiff.h

public:
 
   int getSize() const;
   NodeRef getRoot() const;
   using PreorderIterator = const Node *;
   PreorderIterator begin() const;
   PreorderIterator end() const;
 
   NodeRef getNode(NodeId Id) const;
-  int findPositionInParent(NodeRef Node) const;
 
   // Returns the starting and ending offset of the node in its source file.
   std::pair<unsigned, unsigned> getSourceRangeOffsets(NodeRef N) 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.
struct Node {
   ast_type_traits::ASTNodeKind getType() const;
   StringRef getTypeLabel() const;
   bool isLeaf() const { return Children.empty(); }
   llvm::Optional<StringRef> getIdentifier() const;
   llvm::Optional<std::string> getQualifiedIdentifier() const;
 
   NodeRefIterator begin() const;
   NodeRefIterator end() const;
+
+  int findPositionInParent() const;
 };
 
 struct NodeRefIterator {
   SyntaxTree::Impl *Tree;
   const NodeId *IdPointer;
   NodeRefIterator(SyntaxTree::Impl *Tree, const NodeId *IdPointer)
       : Tree(Tree), IdPointer(IdPointer) {}
   NodeRef operator*() const;

lib/Tooling/ASTDiff/ASTDiff.cpp

private:
   const Node *findCandidate(NodeRef N1) const;
 
   // Returns a mapping of identical subtrees.
   void matchTopDown();
 
   // Tries to match any yet unmapped nodes, in a bottom-up fashion.
   void matchBottomUp();
 
+  int findNewPosition(NodeRef N) const;
+
   const ComparisonOptions &Options;
 
   friend class ZhangShashaMatcher;
 };
 
 namespace {
 struct NodeList {
   SyntaxTree::Impl &Tree;
public:
   PreorderIterator begin() const { return &getRoot(); }
   PreorderIterator end() const { return begin() + getSize(); }
 
   NodeRef getNode(NodeId Id) const { return Nodes[Id]; }
   Node &getMutableNode(NodeId Id) { return Nodes[Id]; }
   Node &getMutableNode(NodeRef N) { return getMutableNode(N.getId()); }
   int getNumberOfDescendants(NodeRef N) const;
   bool isInSubtree(NodeRef N, NodeRef SubtreeRoot) const;
-  int findPositionInParent(NodeRef Id, bool Shifted = false) const;
 
   std::string getRelativeName(const NamedDecl *ND,
                               const DeclContext *Context) const;
   std::string getRelativeName(const NamedDecl *ND) const;
 
   std::string getNodeValue(NodeRef Node) const;
   std::string getDeclValue(const Decl *D) const;
   std::string getStmtValue(const Stmt *S) const;
int SyntaxTree::Impl::getNumberOfDescendants(NodeRef N) const {
   return N.RightMostDescendant - N.getId() + 1;
 }
 
 bool SyntaxTree::Impl::isInSubtree(NodeRef N, NodeRef SubtreeRoot) const {
   return N.getId() >= SubtreeRoot.getId() &&
          N.getId() <= SubtreeRoot.RightMostDescendant;
 }
 
-int SyntaxTree::Impl::findPositionInParent(NodeRef N, bool Shifted) const {
-  if (!N.getParent())
-    return 0;
-  NodeRef Parent = *N.getParent();
-  const auto &Siblings = Parent.Children;
-  int Position = 0;
-  for (size_t I = 0, E = Siblings.size(); I < E; ++I) {
-    if (Shifted)
-      Position += getNode(Siblings[I]).Shift;
-    if (Siblings[I] == N.getId()) {
-      Position += I;
-      return Position;
-    }
-  }
-  llvm_unreachable("Node not found in parent's children.");
-}
-
 // Returns the qualified name of ND. If it is subordinate to Context,
 // then the prefix of the latter is removed from the returned value.
 std::string
 SyntaxTree::Impl::getRelativeName(const NamedDecl *ND,
                                   const DeclContext *Context) const {
   std::string Val = ND->getQualifiedNameAsString();
   std::string ContextPrefix;
   if (!Context)

 
 NodeRefIterator Node::begin() const {
   return {&Tree, isLeaf() ? nullptr : &Children[0]};
 }
 NodeRefIterator Node::end() const {
   return {&Tree, isLeaf() ? nullptr : &Children[0] + Children.size()};
 }
 
+int Node::findPositionInParent() const {
+  if (!getParent())
+    return 0;
+  const ArrayRef<NodeId> &Siblings = getParent()->Children;
+  return std::find(Siblings.begin(), Siblings.end(), getId()) -
+         Siblings.begin();
+}
+
 namespace {
 // Compares nodes by their depth.
 struct HeightLess {
   SyntaxTree::Impl &Tree;
   HeightLess(SyntaxTree::Impl &Tree) : Tree(Tree) {}
   bool operator()(NodeId Id1, NodeId Id2) const {
     return Tree.getNode(Id1).Height < Tree.getNode(Id2).Height;
   }
if (!getSrc(N2)) {
       T2.getMutableNode(N2).Change = Insert;
       T2.getMutableNode(N2).Shift -= 1;
     }
   }
   for (NodeRef N1 : T1.NodesBfs) {
     if (!getDst(N1))
       continue;
     NodeRef N2 = *getDst(N1);
-    if (!haveSameParents(N1, N2) || T1.findPositionInParent(N1, true) !=
-                                        T2.findPositionInParent(N2, true)) {
+    if (!haveSameParents(N1, N2) ||
+        findNewPosition(N1) != findNewPosition(N2)) {
       T1.getMutableNode(N1).Shift -= 1;
       T2.getMutableNode(N2).Shift -= 1;
     }
   }
   for (NodeRef N2 : T2.NodesBfs) {
     if (!getSrc(N2))
       continue;
     NodeRef N1 = *getSrc(N2);
     Node &MutableN1 = T1.getMutableNode(N1);
     Node &MutableN2 = T2.getMutableNode(N2);
-    if (!haveSameParents(N1, N2) || T1.findPositionInParent(N1, true) !=
-                                        T2.findPositionInParent(N2, true)) {
+    if (!haveSameParents(N1, N2) ||
+        findNewPosition(N1) != findNewPosition(N2)) {
       MutableN1.Change = MutableN2.Change = Move;
     }
     if (T1.getNodeValue(N1) != T2.getNodeValue(N2)) {
       MutableN1.Change = MutableN2.Change =
           (N1.Change == Move ? UpdateMove : Update);
     }
   }
 }
return SrcToDst[N1.getId()].isValid() ? &T2.getNode(SrcToDst[N1.getId()])
                                         : nullptr;
 }
 const Node *ASTDiff::Impl::getSrc(NodeRef N2) const {
   assert(&N2.Tree == &T2 && "Invalid tree.");
   return DstToSrc[N2.getId()].isValid() ? &T1.getNode(DstToSrc[N2.getId()])
                                         : nullptr;
 }
 
+int ASTDiff::Impl::findNewPosition(NodeRef N) const {
+  if (!N.getParent())
+    return 0;
+  int Position = N.findPositionInParent();
+  for (NodeRef Sibling : *N.getParent()) {
+    Position += Sibling.Shift;
+    if (&Sibling == &N)
+      return Position;
+  }
+  llvm_unreachable("Node not found amongst parent's children.");
+}
+
 ASTDiff::ASTDiff(SyntaxTree &T1, SyntaxTree &T2,
                  const ComparisonOptions &Options)
     : DiffImpl(llvm::make_unique<Impl>(*T1.TreeImpl, *T2.TreeImpl, Options)) {}
 
 ASTDiff::~ASTDiff() = default;
 
 const Node *ASTDiff::getMapped(NodeRef N) const {
   return DiffImpl->getMapped(N);

 
 int SyntaxTree::getSize() const { return TreeImpl->getSize(); }
 NodeRef SyntaxTree::getRoot() const { return TreeImpl->getRoot(); }
 SyntaxTree::PreorderIterator SyntaxTree::begin() const {
   return TreeImpl->begin();
 }
 SyntaxTree::PreorderIterator SyntaxTree::end() const { return TreeImpl->end(); }
 
-int SyntaxTree::findPositionInParent(NodeRef N) const {
-  return TreeImpl->findPositionInParent(N);
-}
-
 std::pair<unsigned, unsigned>
 SyntaxTree::getSourceRangeOffsets(NodeRef N) const {
   const SourceManager &SM = TreeImpl->AST.getSourceManager();
   SourceRange Range = N.ASTNode.getSourceRange();
   SourceLocation BeginLoc = Range.getBegin();
   SourceLocation EndLoc = Lexer::getLocForEndOfToken(
       Range.getEnd(), /*Offset=*/0, SM, TreeImpl->AST.getLangOpts());
   if (auto *ThisExpr = N.ASTNode.get<CXXThisExpr>()) {

tools/clang-diff/ClangDiff.cpp

else if (Dst.Change == diff::UpdateMove)
       OS << "Update and Move";
     OS << " ";
     printNode(OS, DstTree, Dst);
     OS << " into ";
     if (!Dst.getParent())
       OS << "None";
     else
       printNode(OS, DstTree, *Dst.getParent());
-    OS << " at " << DstTree.findPositionInParent(Dst) << "\n";
+    OS << " at " << Dst.findPositionInParent() << "\n";
     break;
   }
 }
 
 int main(int argc, const char **argv) {
   std::string ErrorMessage;
   std::unique_ptr<CompilationDatabase> CommonCompilations =
       FixedCompilationDatabase::loadFromCommandLine(argc, argv, ErrorMessage);