[clang-diff] NFC: replace const Node & with a typedef'd NodeRef

include/clang/Tooling/ASTDiff/ASTDiff.h

enum ChangeKind {
   None,
   Delete,    // (Src): delete node Src.
   Update,    // (Src, Dst): update the value of node Src to match Dst.
   Insert,    // (Src, Dst, Pos): insert Src as child of Dst at offset Pos.
   Move,      // (Src, Dst, Pos): move Src to be a child of Dst at offset Pos.
   UpdateMove // Same as Move plus Update.
 };
 
+using NodeRef = const Node &;
 
 class ASTDiff {
 public:
   ASTDiff(SyntaxTree &Src, SyntaxTree &Dst, const ComparisonOptions &Options);
   ~ASTDiff();
 
   // Returns the ID of the node that is mapped to the given node in SourceTree.
-  const Node *getMapped(const SyntaxTree &SourceTree, const Node &N) const;
+  const Node *getMapped(const SyntaxTree &SourceTree, NodeRef N) const;
 
   class Impl;
 
 private:
   std::unique_ptr<Impl> DiffImpl;
 };
 
 /// SyntaxTree objects represent subtrees of the AST.
 /// They can be constructed from any Decl or Stmt.
 class SyntaxTree {
 public:
   /// Constructs a tree from a translation unit.
   SyntaxTree(ASTContext &AST);
   /// Constructs a tree from any AST node.
   template <class T>
   SyntaxTree(T *Node, ASTContext &AST)
       : TreeImpl(llvm::make_unique<Impl>(this, Node, AST)) {}
   SyntaxTree(SyntaxTree &&Other) = default;
   ~SyntaxTree();
 
   const ASTContext &getASTContext() const;
   StringRef getFilename() const;
 
   int getSize() const;
-  const Node &getRoot() const;
+  NodeRef getRoot() const;
   using PreorderIterator = const Node *;
   PreorderIterator begin() const;
   PreorderIterator end() const;
 
-  const Node &getNode(NodeId Id) const;
-  int findPositionInParent(const Node &Node) 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(const Node &N) const;
+  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.
-  std::string getNodeValue(const Node &Node) const;
+  std::string getNodeValue(NodeRef Node) const;
 
   class Impl;
   std::unique_ptr<Impl> TreeImpl;
 };
 
 /// Represents a Clang AST node, alongside some additional information.
 struct Node {
   SyntaxTree::Impl &Tree;
   NodeId Parent, LeftMostDescendant, RightMostDescendant;
   int Depth, Height, Shift = 0;
   ast_type_traits::DynTypedNode ASTNode;
   SmallVector<NodeId, 4> Children;
   ChangeKind Change = None;
   Node(SyntaxTree::Impl &Tree) : Tree(Tree), Children() {}
 
   NodeId getId() const;
   SyntaxTree &getTree() const;
   const Node *getParent() const;
-  const Node &getChild(size_t Index) const;
+  NodeRef getChild(size_t Index) const;
   size_t getNumChildren() const { return Children.size(); }
   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;
 };
 
 struct NodeRefIterator {
   SyntaxTree::Impl *Tree;
   const NodeId *IdPointer;
   NodeRefIterator(SyntaxTree::Impl *Tree, const NodeId *IdPointer)
       : Tree(Tree), IdPointer(IdPointer) {}
-  const Node &operator*() const;
+  NodeRef operator*() const;
   NodeRefIterator &operator++();
   NodeRefIterator &operator+(int Offset);
   bool operator!=(const NodeRefIterator &Other) const;
 };
 
 struct ComparisonOptions {
   /// During top-down matching, only consider nodes of at least this height.
   int MinHeight = 2;
 
   /// During bottom-up matching, match only nodes with at least this value as
   /// the ratio of their common descendants.
   double MinSimilarity = 0.5;
 
   /// 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;
 
   bool StopAfterTopDown = false;
 
   /// Returns false if the nodes should never be matched.
-  bool isMatchingAllowed(const Node &N1, const Node &N2) const {
+  bool isMatchingAllowed(NodeRef N1, NodeRef N2) const {
     return N1.getType().isSame(N2.getType());
   }
 };
 
 } // end namespace diff
 } // end namespace clang
 
 #endif

lib/Tooling/ASTDiff/ASTDiff.cpp

public:
 
   /// Matches nodes one-by-one based on their similarity.
   void computeMapping();
 
   // Compute Change for each node based on similarity.
   void computeChangeKinds(Mapping &M);
 
   const Node *getMapped(const std::unique_ptr<SyntaxTree::Impl> &Tree,
-                        const Node &N) const;
+                        NodeRef N) const;
 
 private:
   // Returns true if the two subtrees are identical.
-  bool identical(const Node &N1, const Node &N2) const;
+  bool identical(NodeRef N1, NodeRef N2) const;
 
   // Returns false if the nodes must not be mached.
-  bool isMatchingPossible(const Node &N1, const Node &N2) const;
+  bool isMatchingPossible(NodeRef N1, NodeRef N2) const;
 
   // Returns true if the nodes' parents are matched.
-  bool haveSameParents(const Mapping &M, const Node &N1, const Node &N2) const;
+  bool haveSameParents(const Mapping &M, NodeRef N1, NodeRef N2) 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, const Node &N1, const Node &N2) const;
+  void addOptimalMapping(Mapping &M, NodeRef N1, NodeRef N2) const;
 
   // Computes the ratio of common descendants between the two nodes.
   // Descendants are only considered to be equal when they are mapped.
-  double getJaccardSimilarity(const Mapping &M, const Node &N1,
-                              const Node &N2) const;
+  double getJaccardSimilarity(const Mapping &M, NodeRef N1, NodeRef N2) const;
 
   // Returns the node that has the highest degree of similarity.
-  const Node *findCandidate(const Mapping &M, const Node &N1) const;
+  const Node *findCandidate(const Mapping &M, NodeRef N1) const;
 
   // Returns a mapping of identical subtrees.
   Mapping matchTopDown();
 
   // Tries to match any yet unmapped nodes, in a bottom-up fashion.
   void matchBottomUp(Mapping &M) const;
 
   const ComparisonOptions &Options;
 
   friend class ZhangShashaMatcher;
 };
 
 namespace {
 struct NodeList {
   SyntaxTree::Impl &Tree;
   std::vector<NodeId> Ids;
   NodeList(SyntaxTree::Impl &Tree) : Tree(Tree) {}
   void push_back(NodeId Id) { Ids.push_back(Id); }
   NodeRefIterator begin() const { return {&Tree, &*Ids.begin()}; }
   NodeRefIterator end() const { return {&Tree, &*Ids.end()}; }
-  const Node &operator[](size_t Index) { return *(begin() + Index); }
+  NodeRef operator[](size_t Index) { return *(begin() + Index); }
   size_t size() { return Ids.size(); }
   void sort() { std::sort(Ids.begin(), Ids.end()); }
 };
 } // end anonymous namespace
 
 /// Represents the AST of a TranslationUnit.
 class SyntaxTree::Impl {
 public:
public:
   /// Nodes in preorder.
   std::vector<Node> Nodes;
   NodeList Leaves;
   // Maps preorder indices to postorder ones.
   std::vector<int> PostorderIds;
   NodeList NodesBfs;
 
   int getSize() const { return Nodes.size(); }
-  const Node &getRoot() const { return getNode(getRootId()); }
+  NodeRef getRoot() const { return getNode(getRootId()); }
   NodeId getRootId() const { return 0; }
   PreorderIterator begin() const { return &getRoot(); }
   PreorderIterator end() const { return begin() + getSize(); }
 
-  const Node &getNode(NodeId Id) const { return Nodes[Id]; }
+  NodeRef getNode(NodeId Id) const { return Nodes[Id]; }
   Node &getMutableNode(NodeId Id) { return Nodes[Id]; }
-  Node &getMutableNode(const Node &N) { return getMutableNode(N.getId()); }
-  int getNumberOfDescendants(const Node &N) const;
-  bool isInSubtree(const Node &N, const Node &SubtreeRoot) const;
-  int findPositionInParent(const Node &Id, bool Shifted = false) const;
+  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(const Node &Node) const;
+  std::string getNodeValue(NodeRef Node) const;
   std::string getDeclValue(const Decl *D) const;
   std::string getStmtValue(const Stmt *S) const;
 
 private:
   void initTree();
   void setLeftMostDescendants();
 };
 
-const Node &NodeRefIterator::operator*() const {
-  return Tree->getNode(*IdPointer);
-}
+NodeRef NodeRefIterator::operator*() const { return Tree->getNode(*IdPointer); }
 
 NodeRefIterator &NodeRefIterator::operator++() { return ++IdPointer, *this; }
 NodeRefIterator &NodeRefIterator::operator+(int Offset) {
   return IdPointer += Offset, *this;
 }
 
 bool NodeRefIterator::operator!=(const NodeRefIterator &Other) const {
   assert(Tree == Other.Tree &&
SyntaxTree::Impl::Impl(SyntaxTree *Parent, Stmt *N, ASTContext &AST)
   PreorderWalker.TraverseStmt(N);
   initTree();
 }
 
 static std::vector<NodeId> getSubtreePostorder(SyntaxTree::Impl &Tree,
                                                NodeId Root) {
   std::vector<NodeId> Postorder;
   std::function<void(NodeId)> Traverse = [&](NodeId Id) {
-    const Node &N = Tree.getNode(Id);
+    NodeRef N = Tree.getNode(Id);
     for (NodeId Child : N.Children)
       Traverse(Child);
     Postorder.push_back(Id);
   };
   Traverse(Root);
   return Postorder;
 }
 
-static void getSubtreeBfs(NodeList &Ids, const Node &Root) {
+static void getSubtreeBfs(NodeList &Ids, NodeRef Root) {
   size_t Expanded = 0;
   Ids.push_back(Root.getId());
   while (Expanded < Ids.size())
-    for (const Node &Child : Ids[Expanded++])
+    for (NodeRef Child : Ids[Expanded++])
       Ids.push_back(Child.getId());
 }
 
 void SyntaxTree::Impl::initTree() {
   setLeftMostDescendants();
   int PostorderId = 0;
   PostorderIds.resize(getSize());
-  std::function<void(const Node &)> PostorderTraverse = [&](const Node &N) {
-    for (const Node &Child : N)
+  std::function<void(NodeRef)> PostorderTraverse = [&](NodeRef N) {
+    for (NodeRef Child : N)
       PostorderTraverse(Child);
     PostorderIds[N.getId()] = PostorderId;
     ++PostorderId;
   };
   PostorderTraverse(getRoot());
   getSubtreeBfs(NodesBfs, getRoot());
 }
 
 void SyntaxTree::Impl::setLeftMostDescendants() {
-  for (const Node &Leaf : Leaves) {
+  for (NodeRef Leaf : Leaves) {
     getMutableNode(Leaf).LeftMostDescendant = Leaf.getId();
     const Node *Parent, *Cur = &Leaf;
     while ((Parent = Cur->getParent()) && &Parent->getChild(0) == Cur) {
       Cur = Parent;
       getMutableNode(*Cur).LeftMostDescendant = Leaf.getId();
     }
   }
 }
 
-int SyntaxTree::Impl::getNumberOfDescendants(const Node &N) const {
+int SyntaxTree::Impl::getNumberOfDescendants(NodeRef N) const {
   return N.RightMostDescendant - N.getId() + 1;
 }
 
-bool SyntaxTree::Impl::isInSubtree(const Node &N,
-                                   const Node &SubtreeRoot) const {
+bool SyntaxTree::Impl::isInSubtree(NodeRef N, NodeRef SubtreeRoot) const {
   return N.getId() >= SubtreeRoot.getId() &&
          N.getId() <= SubtreeRoot.RightMostDescendant;
 }
 
-int SyntaxTree::Impl::findPositionInParent(const Node &N, bool Shifted) const {
+int SyntaxTree::Impl::findPositionInParent(NodeRef N, bool Shifted) const {
   if (!N.getParent())
     return 0;
-  const Node &Parent = *N.getParent();
+  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;
if (Init->isAnyMemberInitializer())
     return Init->getAnyMember()->getName();
   if (Init->isBaseInitializer())
     return QualType(Init->getBaseClass(), 0).getAsString(TypePP);
   if (Init->isDelegatingInitializer())
     return Init->getTypeSourceInfo()->getType().getAsString(TypePP);
   llvm_unreachable("Unknown initializer type");
 }
 
-std::string SyntaxTree::Impl::getNodeValue(const Node &N) const {
+std::string SyntaxTree::Impl::getNodeValue(NodeRef N) const {
   assert(&N.Tree == this);
   const DynTypedNode &DTN = N.ASTNode;
   if (auto *S = DTN.get<Stmt>())
     return getStmtValue(S);
   if (auto *D = DTN.get<Decl>())
     return getDeclValue(D);
   if (auto *Init = DTN.get<CXXCtorInitializer>())
     return getInitializerValue(Init, TypePP);
Subtree(SyntaxTree::Impl &Tree, NodeId SubtreeRoot) : Tree(Tree) {
     int NumLeaves = setLeftMostDescendants();
     computeKeyRoots(NumLeaves);
   }
   int getSize() const { return RootIds.size(); }
   NodeId getIdInRoot(SNodeId Id) const {
     assert(Id > 0 && Id <= getSize() && "Invalid subtree node index.");
     return RootIds[Id - 1];
   }
-  const Node &getNode(SNodeId Id) const {
-    return Tree.getNode(getIdInRoot(Id));
-  }
+  NodeRef getNode(SNodeId Id) const { return Tree.getNode(getIdInRoot(Id)); }
   SNodeId getLeftMostDescendant(SNodeId Id) const {
     assert(Id > 0 && Id <= getSize() && "Invalid subtree node index.");
     return LeftMostDescendants[Id - 1];
   }
   /// Returns the postorder index of the leftmost descendant in the subtree.
   NodeId getPostorderOffset() const {
     return Tree.PostorderIds[getIdInRoot(SNodeId(1))];
   }
   std::string getNodeValue(SNodeId Id) const {
     return Tree.getNodeValue(getNode(Id));
   }
 
 private:
   /// Returns the number of leafs in the subtree.
   int setLeftMostDescendants() {
     int NumLeaves = 0;
     LeftMostDescendants.resize(getSize());
     for (int I = 0; I < getSize(); ++I) {
       SNodeId SI(I + 1);
-      const Node &N = getNode(SI);
+      NodeRef N = getNode(SI);
       NumLeaves += N.isLeaf();
       assert(I == Tree.PostorderIds[getIdInRoot(SI)] - getPostorderOffset() &&
              "Postorder traversal in subtree should correspond to traversal in "
              "the root tree by a constant offset.");
       LeftMostDescendants[I] = SNodeId(Tree.PostorderIds[N.LeftMostDescendant] -
                                        getPostorderOffset());
     }
     return NumLeaves;
while (!TreePairs.empty()) {
         } else if (Col > FirstCol &&
                    ForestDist[Row][Col - 1] + 1 == ForestDist[Row][Col]) {
           --Col;
         } else {
           SNodeId LMD1 = S1.getLeftMostDescendant(Row);
           SNodeId LMD2 = S2.getLeftMostDescendant(Col);
           if (LMD1 == S1.getLeftMostDescendant(LastRow) &&
               LMD2 == S2.getLeftMostDescendant(LastCol)) {
-            const Node &N1 = S1.getNode(Row);
-            const Node &N2 = S2.getNode(Col);
+            NodeRef N1 = S1.getNode(Row);
+            NodeRef N2 = S2.getNode(Col);
             assert(DiffImpl.isMatchingPossible(N1, N2) &&
                    "These nodes must not be matched.");
             Matches.emplace_back(N1.getId(), N2.getId());
             --Row;
             --Col;
           } else {
             TreePairs.emplace_back(Row, Col);
             Row = LMD1;
private:
   /// 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.
   static constexpr double DeletionCost = 1;
   static constexpr double InsertionCost = 1;
 
   double getUpdateCost(SNodeId Id1, SNodeId Id2) {
-    const Node &N1 = S1.getNode(Id1), N2 = S2.getNode(Id2);
+    NodeRef N1 = S1.getNode(Id1), N2 = S2.getNode(Id2);
     if (!DiffImpl.isMatchingPossible(N1, N2))
       return std::numeric_limits<double>::max();
     return S1.getNodeValue(Id1) != S2.getNodeValue(Id2);
   }
 
   void computeTreeDist() {
     for (SNodeId Id1 : S1.KeyRoots)
       for (SNodeId Id2 : S2.KeyRoots)

 NodeId Node::getId() const { return this - &Tree.getRoot(); }
 SyntaxTree &Node::getTree() const { return *Tree.Parent; }
 const Node *Node::getParent() const {
   if (Parent.isInvalid())
     return nullptr;
   return &Tree.getNode(Parent);
 }
 
-const Node &Node::getChild(size_t Index) const {
+NodeRef Node::getChild(size_t Index) const {
   return Tree.getNode(Children[Index]);
 }
 
 ast_type_traits::ASTNodeKind Node::getType() const {
   return ASTNode.getNodeKind();
 }
 
 StringRef Node::getTypeLabel() const { return getType().asStringRef(); }
NodeList pop() {
     Result.sort();
     return Result;
   }
   int peekMax() const {
     if (List.empty())
       return 0;
     return Tree.getNode(List.top()).Height;
   }
-  void open(const Node &N) {
-    for (const Node &Child : N)
+  void open(NodeRef N) {
+    for (NodeRef Child : N)
       push(Child.getId());
   }
 };
 } // end anonymous namespace
 
-bool ASTDiff::Impl::identical(const Node &N1, const Node &N2) const {
+bool ASTDiff::Impl::identical(NodeRef N1, NodeRef N2) const {
   if (N1.getNumChildren() != N2.getNumChildren() ||
       !isMatchingPossible(N1, N2) || T1.getNodeValue(N1) != T2.getNodeValue(N2))
     return false;
   for (size_t Id = 0, E = N1.getNumChildren(); Id < E; ++Id)
     if (!identical(N1.getChild(Id), N2.getChild(Id)))
       return false;
   return true;
 }
 
-bool ASTDiff::Impl::isMatchingPossible(const Node &N1, const Node &N2) const {
+bool ASTDiff::Impl::isMatchingPossible(NodeRef N1, NodeRef N2) const {
   return Options.isMatchingAllowed(N1, N2);
 }
 
-bool ASTDiff::Impl::haveSameParents(const Mapping &M, const Node &N1,
-                                    const Node &N2) const {
+bool ASTDiff::Impl::haveSameParents(const Mapping &M, NodeRef N1,
+                                    NodeRef N2) const {
   const Node *P1 = N1.getParent();
   const Node *P2 = N2.getParent();
   return (!P1 && !P2) || (P1 && P2 && M.getDst(P1->getId()) == P2->getId());
 }
 
-void ASTDiff::Impl::addOptimalMapping(Mapping &M, const Node &N1,
-                                      const Node &N2) const {
+void ASTDiff::Impl::addOptimalMapping(Mapping &M, NodeRef N1,
+                                      NodeRef N2) const {
   if (std::max(T1.getNumberOfDescendants(N1), T2.getNumberOfDescendants(N2)) >
       Options.MaxSize)
     return;
   ZhangShashaMatcher Matcher(*this, T1, T2, N1.getId(), N2.getId());
   std::vector<std::pair<NodeId, NodeId>> R = Matcher.getMatchingNodes();
   for (const auto Tuple : R) {
-    const Node &N1 = T1.getNode(Tuple.first);
-    const Node &N2 = T2.getNode(Tuple.second);
+    NodeRef N1 = T1.getNode(Tuple.first);
+    NodeRef N2 = T2.getNode(Tuple.second);
     if (!M.hasSrc(N1.getId()) && !M.hasDst(N2.getId()))
       M.link(N1.getId(), N2.getId());
   }
 }
 
-double ASTDiff::Impl::getJaccardSimilarity(const Mapping &M, const Node &N1,
-                                           const Node &N2) const {
+double ASTDiff::Impl::getJaccardSimilarity(const Mapping &M, NodeRef N1,
+                                           NodeRef N2) const {
   int CommonDescendants = 0;
   // Count the common descendants, excluding the subtree root.
   for (NodeId Src = N1.getId() + 1; Src <= N1.RightMostDescendant; ++Src) {
     const Node *Dst = getMapped(T1.Parent->TreeImpl, T1.getNode(Src));
     if (Dst)
       CommonDescendants += T2.isInSubtree(*Dst, N2);
   }
   // We need to subtract 1 to get the number of descendants excluding the
   // root.
   double Denominator = T1.getNumberOfDescendants(N1) - 1 +
                        T2.getNumberOfDescendants(N2) - 1 - CommonDescendants;
   // CommonDescendants is less than the size of one subtree.
   assert(Denominator >= 0 && "Expected non-negative denominator.");
   if (Denominator == 0)
     return 0;
   return CommonDescendants / Denominator;
 }
 
-const Node *ASTDiff::Impl::findCandidate(const Mapping &M,
-                                         const Node &N1) const {
+const Node *ASTDiff::Impl::findCandidate(const Mapping &M, NodeRef N1) const {
   const Node *Candidate = nullptr;
   double HighestSimilarity = 0.0;
-  for (const Node &N2 : T2) {
+  for (NodeRef N2 : T2) {
     if (!isMatchingPossible(N1, N2))
       continue;
     if (M.hasDst(N2.getId()))
       continue;
     double Similarity = getJaccardSimilarity(M, N1, N2);
     if (Similarity >= Options.MinSimilarity && Similarity > HighestSimilarity) {
       HighestSimilarity = Similarity;
       Candidate = &N2;
if (Id1 == T1.getRootId() && !M.hasSrc(T1.getRootId()) &&
         !M.hasDst(T2.getRootId())) {
       if (isMatchingPossible(T1.getRoot(), T2.getRoot())) {
         M.link(T1.getRootId(), T2.getRootId());
         addOptimalMapping(M, T1.getRoot(), T2.getRoot());
       }
       break;
     }
     bool Matched = M.hasSrc(Id1);
-    const Node &N1 = T1.getNode(Id1);
+    NodeRef N1 = T1.getNode(Id1);
     bool MatchedChildren =
         std::any_of(N1.Children.begin(), N1.Children.end(),
                     [&](NodeId Child) { return M.hasSrc(Child); });
     if (Matched || !MatchedChildren)
       continue;
     const Node *N2 = findCandidate(M, N1);
     if (N2) {
       M.link(N1.getId(), N2->getId());
Mapping ASTDiff::Impl::matchTopDown() {
 
   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 (const Node &N1 : L1.pop())
+      for (NodeRef N1 : L1.pop())
         L1.open(N1);
       continue;
     }
     if (Max2 > Max1) {
-      for (const Node &N2 : L2.pop())
+      for (NodeRef N2 : L2.pop())
         L2.open(N2);
       continue;
     }
     NodeList H1 = L1.pop(), H2 = L2.pop();
-    for (const Node &N1 : H1) {
-      for (const Node &N2 : H2) {
+    for (NodeRef N1 : H1) {
+      for (NodeRef N2 : H2) {
         if (identical(N1, N2) && !M.hasSrc(N1.getId()) &&
             !M.hasDst(N2.getId())) {
           for (int I = 0, E = T1.getNumberOfDescendants(N1); I < E; ++I)
             M.link(N1.getId() + I, N2.getId() + I);
         }
       }
     }
-    for (const Node &N1 : H1) {
+    for (NodeRef N1 : H1) {
       if (!M.hasSrc(N1.getId()))
         L1.open(N1);
     }
-    for (const Node &N2 : H2) {
+    for (NodeRef N2 : H2) {
       if (!M.hasDst(N2.getId()))
         L2.open(N2);
     }
   }
   return M;
 }
 
 ASTDiff::Impl::Impl(SyntaxTree::Impl &T1, SyntaxTree::Impl &T2,
                     const ComparisonOptions &Options)
     : T1(T1), T2(T2), Options(Options) {
   computeMapping();
   computeChangeKinds(TheMapping);
 }
 
 void ASTDiff::Impl::computeMapping() {
   TheMapping = matchTopDown();
   if (Options.StopAfterTopDown)
     return;
   matchBottomUp(TheMapping);
 }
 
 void ASTDiff::Impl::computeChangeKinds(Mapping &M) {
-  for (const Node &N1 : T1) {
+  for (NodeRef N1 : T1) {
     if (!M.hasSrc(N1.getId())) {
       T1.getMutableNode(N1.getId()).Change = Delete;
       T1.getMutableNode(N1.getId()).Shift -= 1;
     }
   }
-  for (const Node &N2 : T2) {
+  for (NodeRef N2 : T2) {
     if (!M.hasDst(N2.getId())) {
       T2.getMutableNode(N2.getId()).Change = Insert;
       T2.getMutableNode(N2.getId()).Shift -= 1;
     }
   }
-  for (const Node &N1 : T1.NodesBfs) {
+  for (NodeRef N1 : T1.NodesBfs) {
     NodeId Id2 = M.getDst(N1.getId());
     if (Id2.isInvalid())
       continue;
-    const Node &N2 = T2.getNode(Id2);
+    NodeRef N2 = T2.getNode(Id2);
     if (!haveSameParents(M, N1, N2) || T1.findPositionInParent(N1, true) !=
                                            T2.findPositionInParent(N2, true)) {
       T1.getMutableNode(N1).Shift -= 1;
       T2.getMutableNode(N2).Shift -= 1;
     }
   }
-  for (const Node &N2TODO : T2.NodesBfs) {
+  for (NodeRef N2TODO : T2.NodesBfs) {
     NodeId Id1 = M.getSrc(N2TODO.getId());
     if (Id1.isInvalid())
       continue;
     Node &N1 = T1.getMutableNode(Id1);
     Node &N2 = T2.getMutableNode(N2TODO.getId());
     if (Id1.isInvalid())
       continue;
     if (!haveSameParents(M, N1, N2) || T1.findPositionInParent(N1, true) !=
                                            T2.findPositionInParent(N2, true)) {
       N1.Change = N2.Change = Move;
     }
     if (T1.getNodeValue(N1) != T2.getNodeValue(N2)) {
       N1.Change = N2.Change = (N1.Change == Move ? UpdateMove : Update);
     }
   }
 }
 
 const Node *
 ASTDiff::Impl::getMapped(const std::unique_ptr<SyntaxTree::Impl> &Tree,
-                         const Node &N) const {
+                         NodeRef N) const {
   if (&*Tree == &T1) {
     NodeId Id = TheMapping.getDst(N.getId());
     return Id.isValid() ? &T2.getNode(Id) : nullptr;
   }
   assert(&*Tree == &T2 && "Invalid tree.");
   NodeId Id = TheMapping.getSrc(N.getId());
   return Id.isValid() ? &T1.getNode(Id) : nullptr;
 }
 
 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(const SyntaxTree &SourceTree,
-                               const Node &N) const {
+const Node *ASTDiff::getMapped(const SyntaxTree &SourceTree, NodeRef N) const {
   return DiffImpl->getMapped(SourceTree.TreeImpl, N);
 }
 
 SyntaxTree::SyntaxTree(ASTContext &AST)
     : TreeImpl(llvm::make_unique<SyntaxTree::Impl>(
           this, AST.getTranslationUnitDecl(), AST)) {}
 
 SyntaxTree::~SyntaxTree() = default;
 
 const ASTContext &SyntaxTree::getASTContext() const { return TreeImpl->AST; }
 
-const Node &SyntaxTree::getNode(NodeId Id) const {
-  return TreeImpl->getNode(Id);
-}
+NodeRef SyntaxTree::getNode(NodeId Id) const { return TreeImpl->getNode(Id); }
 
 int SyntaxTree::getSize() const { return TreeImpl->getSize(); }
-const Node &SyntaxTree::getRoot() const { return TreeImpl->getRoot(); }
+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(const Node &N) const {
+int SyntaxTree::findPositionInParent(NodeRef N) const {
   return TreeImpl->findPositionInParent(N);
 }
 
 std::pair<unsigned, unsigned>
-SyntaxTree::getSourceRangeOffsets(const Node &N) const {
+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>()) {
     if (ThisExpr->isImplicit())
       EndLoc = BeginLoc;
   }
   unsigned Begin = SM.getFileOffset(SM.getExpansionLoc(BeginLoc));
   unsigned End = SM.getFileOffset(SM.getExpansionLoc(EndLoc));
   return {Begin, End};
 }
 
-std::string SyntaxTree::getNodeValue(const Node &N) const {
+std::string SyntaxTree::getNodeValue(NodeRef N) const {
   return TreeImpl->getNodeValue(N);
 }
 
 } // end namespace diff
 } // end namespace clang

tools/clang-diff/ClangDiff.cpp

case diff::Move:
     return "m";
   case diff::UpdateMove:
     return "u m";
   }
   llvm_unreachable("Invalid enumeration value.");
 }
 
 static unsigned printHtmlForNode(raw_ostream &OS, const diff::ASTDiff &Diff,
-                                 bool IsLeft, const diff::Node &Node,
+                                 bool IsLeft,  diff::NodeRef Node,
                                  unsigned Offset) {
   char MyTag, OtherTag;
   diff::NodeId LeftId, RightId;
   diff::SyntaxTree &Tree = Node.getTree();
   const diff::Node *Target = Diff.getMapped(Tree, Node);
   diff::NodeId TargetId = Target ? Target->getId() : diff::NodeId();
   if (IsLeft) {
     MyTag = 'L';
if (!Value.empty()) {
     OS << "\n";
     printHtml(OS, Value);
   }
   OS << "'";
   if (Node.Change != diff::None)
     OS << " class='" << getChangeKindAbbr(Node.Change) << "'";
   OS << ">";
 
-  for (const diff::Node &Child : Node)
+  for (diff::NodeRef Child : Node)
     Offset = printHtmlForNode(OS, Diff, IsLeft, Child, Offset);
 
   for (; Offset < End; ++Offset)
     printHtml(OS, Code[Offset]);
   if (&Node == &Tree.getRoot()) {
     End = Code.size();
     for (; Offset < End; ++Offset)
       printHtml(OS, Code[Offset]);
default:
       } else {
         OS << C;
       }
     }
   }
 }
 
 static void printNodeAttributes(raw_ostream &OS, diff::SyntaxTree &Tree,
-                                const diff::Node &Node) {
+                                diff::NodeRef Node) {
   OS << R"("id":)" << int(Node.getId());
   OS << R"(,"type":")" << Node.getTypeLabel() << '"';
   auto Offsets = Tree.getSourceRangeOffsets(Node);
   OS << R"(,"begin":)" << Offsets.first;
   OS << R"(,"end":)" << Offsets.second;
   std::string Value = Tree.getNodeValue(Node);
   if (!Value.empty()) {
     OS << R"(,"value":")";
     printJsonString(OS, Value);
     OS << '"';
   }
 }
 
 static void printNodeAsJson(raw_ostream &OS, diff::SyntaxTree &Tree,
-                            const diff::Node &Node) {
+                            diff::NodeRef Node) {
   OS << "{";
   printNodeAttributes(OS, Tree, Node);
   auto Identifier = Node.getIdentifier();
   auto QualifiedIdentifier = Node.getQualifiedIdentifier();
   if (Identifier) {
     OS << R"(,"identifier":")";
     printJsonString(OS, *Identifier);
     OS << R"(")";
for (++ChildBegin; ChildBegin != ChildEnd; ++ChildBegin) {
       OS << ",";
       printNodeAsJson(OS, Tree, *ChildBegin);
     }
   }
   OS << "]}";
 }
 
 static void printNode(raw_ostream &OS, diff::SyntaxTree &Tree,
-                      const diff::Node &Node) {
+                      diff::NodeRef Node) {
   OS << Node.getTypeLabel();
   std::string Value = Tree.getNodeValue(Node);
   if (!Value.empty())
     OS << ": " << Value;
   OS << "(" << Node.getId() << ")";
 }
 
 static void printTree(raw_ostream &OS, diff::SyntaxTree &Tree) {
-  for (const diff::Node &Node : Tree) {
+  for (diff::NodeRef Node : Tree) {
     for (int I = 0; I < Node.Depth; ++I)
       OS << " ";
     printNode(OS, Tree, Node);
     OS << "\n";
   }
 }
 
 static void printDstChange(raw_ostream &OS, diff::ASTDiff &Diff,
                            diff::SyntaxTree &SrcTree, diff::SyntaxTree &DstTree,
-                           const diff::Node &Dst) {
+                           diff::NodeRef Dst) {
   const diff::Node *Src = Diff.getMapped(DstTree, Dst);
   switch (Dst.Change) {
   case diff::None:
     break;
   case diff::Delete:
     llvm_unreachable("The destination tree can't have deletions.");
   case diff::Update:
     OS << "Update ";
if (HtmlDiff) {
     llvm::outs() << "</div>";
     llvm::outs() << "<div id='R' class='code'>";
     printHtmlForNode(llvm::outs(), Diff, false, DstTree.getRoot(), 0);
     llvm::outs() << "</div>";
     llvm::outs() << "</pre></div></body></html>\n";
     return 0;
   }
 
-  for (const diff::Node &Dst : DstTree) {
+  for (diff::NodeRef Dst : DstTree) {
     const diff::Node *Src = Diff.getMapped(DstTree, Dst);
     if (PrintMatches && Src) {
       llvm::outs() << "Match ";
       printNode(llvm::outs(), SrcTree, *Src);
       llvm::outs() << " to ";
       printNode(llvm::outs(), DstTree, Dst);
       llvm::outs() << "\n";
     }
     printDstChange(llvm::outs(), Diff, SrcTree, DstTree, Dst);
   }
-  for (const diff::Node &Src : SrcTree) {
+  for (diff::NodeRef Src : SrcTree) {
     if (!Diff.getMapped(SrcTree, Src)) {
       llvm::outs() << "Delete ";
       printNode(llvm::outs(), SrcTree, Src);
       llvm::outs() << "\n";
     }
   }
 
   return 0;
 }