clang/lib/Tooling/ASTDiff/ASTDiff.cpp

   1 //===- ASTDiff.cpp - AST differencing implementation-----------*- C++ -*- -===//
   2 //
   3 // Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.
   4 // See https://llvm.org/LICENSE.txt for license information.
   5 // SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception
   6 //
   7 //===----------------------------------------------------------------------===//
   8 //
   9 // This file contains definitons for the AST differencing interface.
  10 //
  11 //===----------------------------------------------------------------------===//
  12
  13 #include "clang/Tooling/ASTDiff/ASTDiff.h"
  14 #include "clang/AST/ParentMapContext.h"
  15 #include "clang/AST/RecursiveASTVisitor.h"
  16 #include "clang/Basic/SourceManager.h"
  17 #include "clang/Lex/Lexer.h"
  18 #include "llvm/ADT/PriorityQueue.h"
  19
  20 #include <limits>
  21 #include <memory>
  22 #include <optional>
  23 #include <unordered_set>
  24
  25 using namespace llvm;
  26 using namespace clang;
  27
  28 namespace clang {
  29 namespace diff {
  30
  31 namespace {
  32 /// Maps nodes of the left tree to ones on the right, and vice versa.
  33 class Mapping {
  34 public:
  35   Mapping() = default;
  36   Mapping(Mapping &&Other) = default;
  37   Mapping &operator=(Mapping &&Other) = default;
  38
  39   Mapping(size_t Size) {
  40     SrcToDst = std::make_unique<NodeId[]>(Size);
  41     DstToSrc = std::make_unique<NodeId[]>(Size);
  42   }
  43
  44   void link(NodeId Src, NodeId Dst) {
  45     SrcToDst[Src] = Dst, DstToSrc[Dst] = Src;
  46   }
  47
  48   NodeId getDst(NodeId Src) const { return SrcToDst[Src]; }
  49   NodeId getSrc(NodeId Dst) const { return DstToSrc[Dst]; }
  50   bool hasSrc(NodeId Src) const { return getDst(Src).isValid(); }
  51   bool hasDst(NodeId Dst) const { return getSrc(Dst).isValid(); }
  52
  53 private:
  54   std::unique_ptr<NodeId[]> SrcToDst, DstToSrc;
  55 };
  56 } // end anonymous namespace
  57
  58 class ASTDiff::Impl {
  59 public:
  60   SyntaxTree::Impl &T1, &T2;
  61   Mapping TheMapping;
  62
  63   Impl(SyntaxTree::Impl &T1, SyntaxTree::Impl &T2,
  64        const ComparisonOptions &Options);
  65
  66   /// Matches nodes one-by-one based on their similarity.
  67   void computeMapping();
  68
  69   // Compute Change for each node based on similarity.
  70   void computeChangeKinds(Mapping &M);
  71
  72   NodeId getMapped(const std::unique_ptr<SyntaxTree::Impl> &Tree,
  73                    NodeId Id) const {
  74     if (&*Tree == &T1)
  75       return TheMapping.getDst(Id);
  76     assert(&*Tree == &T2 && "Invalid tree.");
  77     return TheMapping.getSrc(Id);
  78   }
  79
  80 private:
  81   // Returns true if the two subtrees are identical.
  82   bool identical(NodeId Id1, NodeId Id2) const;
  83
  84   // Returns false if the nodes must not be mached.
  85   bool isMatchingPossible(NodeId Id1, NodeId Id2) const;
  86
  87   // Returns true if the nodes' parents are matched.
  88   bool haveSameParents(const Mapping &M, NodeId Id1, NodeId Id2) const;
  89
  90   // Uses an optimal albeit slow algorithm to compute a mapping between two
  91   // subtrees, but only if both have fewer nodes than MaxSize.
  92   void addOptimalMapping(Mapping &M, NodeId Id1, NodeId Id2) const;
  93
  94   // Computes the ratio of common descendants between the two nodes.
  95   // Descendants are only considered to be equal when they are mapped in M.
  96   double getJaccardSimilarity(const Mapping &M, NodeId Id1, NodeId Id2) const;
  97
  98   // Returns the node that has the highest degree of similarity.
  99   NodeId findCandidate(const Mapping &M, NodeId Id1) const;
 100
 101   // Returns a mapping of identical subtrees.
 102   Mapping matchTopDown() const;
 103
 104   // Tries to match any yet unmapped nodes, in a bottom-up fashion.
 105   void matchBottomUp(Mapping &M) const;
 106
 107   const ComparisonOptions &Options;
 108
 109   friend class ZhangShashaMatcher;
 110 };
 111
 112 /// Represents the AST of a TranslationUnit.
 113 class SyntaxTree::Impl {
 114 public:
 115   Impl(SyntaxTree *Parent, ASTContext &AST);
 116   /// Constructs a tree from an AST node.
 117   Impl(SyntaxTree *Parent, Decl *N, ASTContext &AST);
 118   Impl(SyntaxTree *Parent, Stmt *N, ASTContext &AST);
 119   template <class T>
 120   Impl(SyntaxTree *Parent,
 121        std::enable_if_t<std::is_base_of_v<Stmt, T>, T> *Node, ASTContext &AST)
 122       : Impl(Parent, dyn_cast<Stmt>(Node), AST) {}
 123   template <class T>
 124   Impl(SyntaxTree *Parent,
 125        std::enable_if_t<std::is_base_of_v<Decl, T>, T> *Node, ASTContext &AST)
 126       : Impl(Parent, dyn_cast<Decl>(Node), AST) {}
 127
 128   SyntaxTree *Parent;
 129   ASTContext &AST;
 130   PrintingPolicy TypePP;
 131   /// Nodes in preorder.
 132   std::vector<Node> Nodes;
 133   std::vector<NodeId> Leaves;
 134   // Maps preorder indices to postorder ones.
 135   std::vector<int> PostorderIds;
 136   std::vector<NodeId> NodesBfs;
 137
 138   int getSize() const { return Nodes.size(); }
 139   NodeId getRootId() const { return 0; }
 140   PreorderIterator begin() const { return getRootId(); }
 141   PreorderIterator end() const { return getSize(); }
 142
 143   const Node &getNode(NodeId Id) const { return Nodes[Id]; }
 144   Node &getMutableNode(NodeId Id) { return Nodes[Id]; }
 145   bool isValidNodeId(NodeId Id) const { return Id >= 0 && Id < getSize(); }
 146   void addNode(Node &N) { Nodes.push_back(N); }
 147   int getNumberOfDescendants(NodeId Id) const;
 148   bool isInSubtree(NodeId Id, NodeId SubtreeRoot) const;
 149   int findPositionInParent(NodeId Id, bool Shifted = false) const;
 150
 151   std::string getRelativeName(const NamedDecl *ND,
 152                               const DeclContext *Context) const;
 153   std::string getRelativeName(const NamedDecl *ND) const;
 154
 155   std::string getNodeValue(NodeId Id) const;
 156   std::string getNodeValue(const Node &Node) const;
 157   std::string getDeclValue(const Decl *D) const;
 158   std::string getStmtValue(const Stmt *S) const;
 159
 160 private:
 161   void initTree();
 162   void setLeftMostDescendants();
 163 };
 164
 165 static bool isSpecializedNodeExcluded(const Decl *D) { return D->isImplicit(); }
 166 static bool isSpecializedNodeExcluded(const Stmt *S) { return false; }
 167 static bool isSpecializedNodeExcluded(CXXCtorInitializer *I) {
 168   return !I->isWritten();
 169 }
 170
 171 template <class T>
 172 static bool isNodeExcluded(const SourceManager &SrcMgr, T *N) {
 173   if (!N)
 174     return true;
 175   SourceLocation SLoc = N->getSourceRange().getBegin();
 176   if (SLoc.isValid()) {
 177     // Ignore everything from other files.
 178     if (!SrcMgr.isInMainFile(SLoc))
 179       return true;
 180     // Ignore macros.
 181     if (SLoc != SrcMgr.getSpellingLoc(SLoc))
 182       return true;
 183   }
 184   return isSpecializedNodeExcluded(N);
 185 }
 186
 187 namespace {
 188 // Sets Height, Parent and Children for each node.
 189 struct PreorderVisitor : public RecursiveASTVisitor<PreorderVisitor> {
 190   int Id = 0, Depth = 0;
 191   NodeId Parent;
 192   SyntaxTree::Impl &Tree;
 193
 194   PreorderVisitor(SyntaxTree::Impl &Tree) : Tree(Tree) {}
 195
 196   template <class T> std::tuple<NodeId, NodeId> PreTraverse(T *ASTNode) {
 197     NodeId MyId = Id;
 198     Tree.Nodes.emplace_back();
 199     Node &N = Tree.getMutableNode(MyId);
 200     N.Parent = Parent;
 201     N.Depth = Depth;
 202     N.ASTNode = DynTypedNode::create(*ASTNode);
 203     assert(!N.ASTNode.getNodeKind().isNone() &&
 204            "Expected nodes to have a valid kind.");
 205     if (Parent.isValid()) {
 206       Node &P = Tree.getMutableNode(Parent);
 207       P.Children.push_back(MyId);
 208     }
 209     Parent = MyId;
 210     ++Id;
 211     ++Depth;
 212     return std::make_tuple(MyId, Tree.getNode(MyId).Parent);
 213   }
 214   void PostTraverse(std::tuple<NodeId, NodeId> State) {
 215     NodeId MyId, PreviousParent;
 216     std::tie(MyId, PreviousParent) = State;
 217     assert(MyId.isValid() && "Expecting to only traverse valid nodes.");
 218     Parent = PreviousParent;
 219     --Depth;
 220     Node &N = Tree.getMutableNode(MyId);
 221     N.RightMostDescendant = Id - 1;
 222     assert(N.RightMostDescendant >= 0 &&
 223            N.RightMostDescendant < Tree.getSize() &&
 224            "Rightmost descendant must be a valid tree node.");
 225     if (N.isLeaf())
 226       Tree.Leaves.push_back(MyId);
 227     N.Height = 1;
 228     for (NodeId Child : N.Children)
 229       N.Height = std::max(N.Height, 1 + Tree.getNode(Child).Height);
 230   }
 231   bool TraverseDecl(Decl *D) {
 232     if (isNodeExcluded(Tree.AST.getSourceManager(), D))
 233       return true;
 234     auto SavedState = PreTraverse(D);
 235     RecursiveASTVisitor<PreorderVisitor>::TraverseDecl(D);
 236     PostTraverse(SavedState);
 237     return true;
 238   }
 239   bool TraverseStmt(Stmt *S) {
 240     if (auto *E = dyn_cast_or_null<Expr>(S))
 241       S = E->IgnoreImplicit();
 242     if (isNodeExcluded(Tree.AST.getSourceManager(), S))
 243       return true;
 244     auto SavedState = PreTraverse(S);
 245     RecursiveASTVisitor<PreorderVisitor>::TraverseStmt(S);
 246     PostTraverse(SavedState);
 247     return true;
 248   }
 249   bool TraverseType(QualType T) { return true; }
 250   bool TraverseConstructorInitializer(CXXCtorInitializer *Init) {
 251     if (isNodeExcluded(Tree.AST.getSourceManager(), Init))
 252       return true;
 253     auto SavedState = PreTraverse(Init);
 254     RecursiveASTVisitor<PreorderVisitor>::TraverseConstructorInitializer(Init);
 255     PostTraverse(SavedState);
 256     return true;
 257   }
 258 };
 259 } // end anonymous namespace
 260
 261 SyntaxTree::Impl::Impl(SyntaxTree *Parent, ASTContext &AST)
 262     : Parent(Parent), AST(AST), TypePP(AST.getLangOpts()) {
 263   TypePP.AnonymousTagLocations = false;
 264 }
 265
 266 SyntaxTree::Impl::Impl(SyntaxTree *Parent, Decl *N, ASTContext &AST)
 267     : Impl(Parent, AST) {
 268   PreorderVisitor PreorderWalker(*this);
 269   PreorderWalker.TraverseDecl(N);
 270   initTree();
 271 }
 272
 273 SyntaxTree::Impl::Impl(SyntaxTree *Parent, Stmt *N, ASTContext &AST)
 274     : Impl(Parent, AST) {
 275   PreorderVisitor PreorderWalker(*this);
 276   PreorderWalker.TraverseStmt(N);
 277   initTree();
 278 }
 279
 280 static std::vector<NodeId> getSubtreePostorder(const SyntaxTree::Impl &Tree,
 281                                                NodeId Root) {
 282   std::vector<NodeId> Postorder;
 283   std::function<void(NodeId)> Traverse = [&](NodeId Id) {
 284     const Node &N = Tree.getNode(Id);
 285     for (NodeId Child : N.Children)
 286       Traverse(Child);
 287     Postorder.push_back(Id);
 288   };
 289   Traverse(Root);
 290   return Postorder;
 291 }
 292
 293 static std::vector<NodeId> getSubtreeBfs(const SyntaxTree::Impl &Tree,
 294                                          NodeId Root) {
 295   std::vector<NodeId> Ids;
 296   size_t Expanded = 0;
 297   Ids.push_back(Root);
 298   while (Expanded < Ids.size())
 299     for (NodeId Child : Tree.getNode(Ids[Expanded++]).Children)
 300       Ids.push_back(Child);
 301   return Ids;
 302 }
 303
 304 void SyntaxTree::Impl::initTree() {
 305   setLeftMostDescendants();
 306   int PostorderId = 0;
 307   PostorderIds.resize(getSize());
 308   std::function<void(NodeId)> PostorderTraverse = [&](NodeId Id) {
 309     for (NodeId Child : getNode(Id).Children)
 310       PostorderTraverse(Child);
 311     PostorderIds[Id] = PostorderId;
 312     ++PostorderId;
 313   };
 314   PostorderTraverse(getRootId());
 315   NodesBfs = getSubtreeBfs(*this, getRootId());
 316 }
 317
 318 void SyntaxTree::Impl::setLeftMostDescendants() {
 319   for (NodeId Leaf : Leaves) {
 320     getMutableNode(Leaf).LeftMostDescendant = Leaf;
 321     NodeId Parent, Cur = Leaf;
 322     while ((Parent = getNode(Cur).Parent).isValid() &&
 323            getNode(Parent).Children[0] == Cur) {
 324       Cur = Parent;
 325       getMutableNode(Cur).LeftMostDescendant = Leaf;
 326     }
 327   }
 328 }
 329
 330 int SyntaxTree::Impl::getNumberOfDescendants(NodeId Id) const {
 331   return getNode(Id).RightMostDescendant - Id + 1;
 332 }
 333
 334 bool SyntaxTree::Impl::isInSubtree(NodeId Id, NodeId SubtreeRoot) const {
 335   return Id >= SubtreeRoot && Id <= getNode(SubtreeRoot).RightMostDescendant;
 336 }
 337
 338 int SyntaxTree::Impl::findPositionInParent(NodeId Id, bool Shifted) const {
 339   NodeId Parent = getNode(Id).Parent;
 340   if (Parent.isInvalid())
 341     return 0;
 342   const auto &Siblings = getNode(Parent).Children;
 343   int Position = 0;
 344   for (size_t I = 0, E = Siblings.size(); I < E; ++I) {
 345     if (Shifted)
 346       Position += getNode(Siblings[I]).Shift;
 347     if (Siblings[I] == Id) {
 348       Position += I;
 349       return Position;
 350     }
 351   }
 352   llvm_unreachable("Node not found in parent's children.");
 353 }
 354
 355 // Returns the qualified name of ND. If it is subordinate to Context,
 356 // then the prefix of the latter is removed from the returned value.
 357 std::string
 358 SyntaxTree::Impl::getRelativeName(const NamedDecl *ND,
 359                                   const DeclContext *Context) const {
 360   std::string Val = ND->getQualifiedNameAsString();
 361   std::string ContextPrefix;
 362   if (!Context)
 363     return Val;
 364   if (auto *Namespace = dyn_cast<NamespaceDecl>(Context))
 365     ContextPrefix = Namespace->getQualifiedNameAsString();
 366   else if (auto *Record = dyn_cast<RecordDecl>(Context))
 367     ContextPrefix = Record->getQualifiedNameAsString();
 368   else if (AST.getLangOpts().CPlusPlus11)
 369     if (auto *Tag = dyn_cast<TagDecl>(Context))
 370       ContextPrefix = Tag->getQualifiedNameAsString();
 371   // Strip the qualifier, if Val refers to something in the current scope.
 372   // But leave one leading ':' in place, so that we know that this is a
 373   // relative path.
 374   if (!ContextPrefix.empty() && StringRef(Val).starts_with(ContextPrefix))
 375     Val = Val.substr(ContextPrefix.size() + 1);
 376   return Val;
 377 }
 378
 379 std::string SyntaxTree::Impl::getRelativeName(const NamedDecl *ND) const {
 380   return getRelativeName(ND, ND->getDeclContext());
 381 }
 382
 383 static const DeclContext *getEnclosingDeclContext(ASTContext &AST,
 384                                                   const Stmt *S) {
 385   while (S) {
 386     const auto &Parents = AST.getParents(*S);
 387     if (Parents.empty())
 388       return nullptr;
 389     const auto &P = Parents[0];
 390     if (const auto *D = P.get<Decl>())
 391       return D->getDeclContext();
 392     S = P.get<Stmt>();
 393   }
 394   return nullptr;
 395 }
 396
 397 static std::string getInitializerValue(const CXXCtorInitializer *Init,
 398                                        const PrintingPolicy &TypePP) {
 399   if (Init->isAnyMemberInitializer())
 400     return std::string(Init->getAnyMember()->getName());
 401   if (Init->isBaseInitializer())
 402     return QualType(Init->getBaseClass(), 0).getAsString(TypePP);
 403   if (Init->isDelegatingInitializer())
 404     return Init->getTypeSourceInfo()->getType().getAsString(TypePP);
 405   llvm_unreachable("Unknown initializer type");
 406 }
 407
 408 std::string SyntaxTree::Impl::getNodeValue(NodeId Id) const {
 409   return getNodeValue(getNode(Id));
 410 }
 411
 412 std::string SyntaxTree::Impl::getNodeValue(const Node &N) const {
 413   const DynTypedNode &DTN = N.ASTNode;
 414   if (auto *S = DTN.get<Stmt>())
 415     return getStmtValue(S);
 416   if (auto *D = DTN.get<Decl>())
 417     return getDeclValue(D);
 418   if (auto *Init = DTN.get<CXXCtorInitializer>())
 419     return getInitializerValue(Init, TypePP);
 420   llvm_unreachable("Fatal: unhandled AST node.\n");
 421 }
 422
 423 std::string SyntaxTree::Impl::getDeclValue(const Decl *D) const {
 424   std::string Value;
 425   if (auto *V = dyn_cast<ValueDecl>(D))
 426     return getRelativeName(V) + "(" + V->getType().getAsString(TypePP) + ")";
 427   if (auto *N = dyn_cast<NamedDecl>(D))
 428     Value += getRelativeName(N) + ";";
 429   if (auto *T = dyn_cast<TypedefNameDecl>(D))
 430     return Value + T->getUnderlyingType().getAsString(TypePP) + ";";
 431   if (auto *T = dyn_cast<TypeDecl>(D))
 432     if (T->getTypeForDecl())
 433       Value +=
 434           T->getTypeForDecl()->getCanonicalTypeInternal().getAsString(TypePP) +
 435           ";";
 436   if (auto *U = dyn_cast<UsingDirectiveDecl>(D))
 437     return std::string(U->getNominatedNamespace()->getName());
 438   if (auto *A = dyn_cast<AccessSpecDecl>(D)) {
 439     CharSourceRange Range(A->getSourceRange(), false);
 440     return std::string(
 441         Lexer::getSourceText(Range, AST.getSourceManager(), AST.getLangOpts()));
 442   }
 443   return Value;
 444 }
 445
 446 std::string SyntaxTree::Impl::getStmtValue(const Stmt *S) const {
 447   if (auto *U = dyn_cast<UnaryOperator>(S))
 448     return std::string(UnaryOperator::getOpcodeStr(U->getOpcode()));
 449   if (auto *B = dyn_cast<BinaryOperator>(S))
 450     return std::string(B->getOpcodeStr());
 451   if (auto *M = dyn_cast<MemberExpr>(S))
 452     return getRelativeName(M->getMemberDecl());
 453   if (auto *I = dyn_cast<IntegerLiteral>(S)) {
 454     SmallString<256> Str;
 455     I->getValue().toString(Str, /*Radix=*/10, /*Signed=*/false);
 456     return std::string(Str.str());
 457   }
 458   if (auto *F = dyn_cast<FloatingLiteral>(S)) {
 459     SmallString<256> Str;
 460     F->getValue().toString(Str);
 461     return std::string(Str.str());
 462   }
 463   if (auto *D = dyn_cast<DeclRefExpr>(S))
 464     return getRelativeName(D->getDecl(), getEnclosingDeclContext(AST, S));
 465   if (auto *String = dyn_cast<StringLiteral>(S))
 466     return std::string(String->getString());
 467   if (auto *B = dyn_cast<CXXBoolLiteralExpr>(S))
 468     return B->getValue() ? "true" : "false";
 469   return "";
 470 }
 471
 472 /// Identifies a node in a subtree by its postorder offset, starting at 1.
 473 struct SNodeId {
 474   int Id = 0;
 475
 476   explicit SNodeId(int Id) : Id(Id) {}
 477   explicit SNodeId() = default;
 478
 479   operator int() const { return Id; }
 480   SNodeId &operator++() { return ++Id, *this; }
 481   SNodeId &operator--() { return --Id, *this; }
 482   SNodeId operator+(int Other) const { return SNodeId(Id + Other); }
 483 };
 484
 485 class Subtree {
 486 private:
 487   /// The parent tree.
 488   const SyntaxTree::Impl &Tree;
 489   /// Maps SNodeIds to original ids.
 490   std::vector<NodeId> RootIds;
 491   /// Maps subtree nodes to their leftmost descendants wtihin the subtree.
 492   std::vector<SNodeId> LeftMostDescendants;
 493
 494 public:
 495   std::vector<SNodeId> KeyRoots;
 496
 497   Subtree(const SyntaxTree::Impl &Tree, NodeId SubtreeRoot) : Tree(Tree) {
 498     RootIds = getSubtreePostorder(Tree, SubtreeRoot);
 499     int NumLeaves = setLeftMostDescendants();
 500     computeKeyRoots(NumLeaves);
 501   }
 502   int getSize() const { return RootIds.size(); }
 503   NodeId getIdInRoot(SNodeId Id) const {
 504     assert(Id > 0 && Id <= getSize() && "Invalid subtree node index.");
 505     return RootIds[Id - 1];
 506   }
 507   const Node &getNode(SNodeId Id) const {
 508     return Tree.getNode(getIdInRoot(Id));
 509   }
 510   SNodeId getLeftMostDescendant(SNodeId Id) const {
 511     assert(Id > 0 && Id <= getSize() && "Invalid subtree node index.");
 512     return LeftMostDescendants[Id - 1];
 513   }
 514   /// Returns the postorder index of the leftmost descendant in the subtree.
 515   NodeId getPostorderOffset() const {
 516     return Tree.PostorderIds[getIdInRoot(SNodeId(1))];
 517   }
 518   std::string getNodeValue(SNodeId Id) const {
 519     return Tree.getNodeValue(getIdInRoot(Id));
 520   }
 521
 522 private:
 523   /// Returns the number of leafs in the subtree.
 524   int setLeftMostDescendants() {
 525     int NumLeaves = 0;
 526     LeftMostDescendants.resize(getSize());
 527     for (int I = 0; I < getSize(); ++I) {
 528       SNodeId SI(I + 1);
 529       const Node &N = getNode(SI);
 530       NumLeaves += N.isLeaf();
 531       assert(I == Tree.PostorderIds[getIdInRoot(SI)] - getPostorderOffset() &&
 532              "Postorder traversal in subtree should correspond to traversal in "
 533              "the root tree by a constant offset.");
 534       LeftMostDescendants[I] = SNodeId(Tree.PostorderIds[N.LeftMostDescendant] -
 535                                        getPostorderOffset());
 536     }
 537     return NumLeaves;
 538   }
 539   void computeKeyRoots(int Leaves) {
 540     KeyRoots.resize(Leaves);
 541     std::unordered_set<int> Visited;
 542     int K = Leaves - 1;
 543     for (SNodeId I(getSize()); I > 0; --I) {
 544       SNodeId LeftDesc = getLeftMostDescendant(I);
 545       if (Visited.count(LeftDesc))
 546         continue;
 547       assert(K >= 0 && "K should be non-negative");
 548       KeyRoots[K] = I;
 549       Visited.insert(LeftDesc);
 550       --K;
 551     }
 552   }
 553 };
 554
 555 /// Implementation of Zhang and Shasha's Algorithm for tree edit distance.
 556 /// Computes an optimal mapping between two trees using only insertion,
 557 /// deletion and update as edit actions (similar to the Levenshtein distance).
 558 class ZhangShashaMatcher {
 559   const ASTDiff::Impl &DiffImpl;
 560   Subtree S1;
 561   Subtree S2;
 562   std::unique_ptr<std::unique_ptr<double[]>[]> TreeDist, ForestDist;
 563
 564 public:
 565   ZhangShashaMatcher(const ASTDiff::Impl &DiffImpl, const SyntaxTree::Impl &T1,
 566                      const SyntaxTree::Impl &T2, NodeId Id1, NodeId Id2)
 567       : DiffImpl(DiffImpl), S1(T1, Id1), S2(T2, Id2) {
 568     TreeDist = std::make_unique<std::unique_ptr<double[]>[]>(
 569         size_t(S1.getSize()) + 1);
 570     ForestDist = std::make_unique<std::unique_ptr<double[]>[]>(
 571         size_t(S1.getSize()) + 1);
 572     for (int I = 0, E = S1.getSize() + 1; I < E; ++I) {
 573       TreeDist[I] = std::make_unique<double[]>(size_t(S2.getSize()) + 1);
 574       ForestDist[I] = std::make_unique<double[]>(size_t(S2.getSize()) + 1);
 575     }
 576   }
 577
 578   std::vector<std::pair<NodeId, NodeId>> getMatchingNodes() {
 579     std::vector<std::pair<NodeId, NodeId>> Matches;
 580     std::vector<std::pair<SNodeId, SNodeId>> TreePairs;
 581
 582     computeTreeDist();
 583
 584     bool RootNodePair = true;
 585
 586     TreePairs.emplace_back(SNodeId(S1.getSize()), SNodeId(S2.getSize()));
 587
 588     while (!TreePairs.empty()) {
 589       SNodeId LastRow, LastCol, FirstRow, FirstCol, Row, Col;
 590       std::tie(LastRow, LastCol) = TreePairs.back();
 591       TreePairs.pop_back();
 592
 593       if (!RootNodePair) {
 594         computeForestDist(LastRow, LastCol);
 595       }
 596
 597       RootNodePair = false;
 598
 599       FirstRow = S1.getLeftMostDescendant(LastRow);
 600       FirstCol = S2.getLeftMostDescendant(LastCol);
 601
 602       Row = LastRow;
 603       Col = LastCol;
 604
 605       while (Row > FirstRow || Col > FirstCol) {
 606         if (Row > FirstRow &&
 607             ForestDist[Row - 1][Col] + 1 == ForestDist[Row][Col]) {
 608           --Row;
 609         } else if (Col > FirstCol &&
 610                    ForestDist[Row][Col - 1] + 1 == ForestDist[Row][Col]) {
 611           --Col;
 612         } else {
 613           SNodeId LMD1 = S1.getLeftMostDescendant(Row);
 614           SNodeId LMD2 = S2.getLeftMostDescendant(Col);
 615           if (LMD1 == S1.getLeftMostDescendant(LastRow) &&
 616               LMD2 == S2.getLeftMostDescendant(LastCol)) {
 617             NodeId Id1 = S1.getIdInRoot(Row);
 618             NodeId Id2 = S2.getIdInRoot(Col);
 619             assert(DiffImpl.isMatchingPossible(Id1, Id2) &&
 620                    "These nodes must not be matched.");
 621             Matches.emplace_back(Id1, Id2);
 622             --Row;
 623             --Col;
 624           } else {
 625             TreePairs.emplace_back(Row, Col);
 626             Row = LMD1;
 627             Col = LMD2;
 628           }
 629         }
 630       }
 631     }
 632     return Matches;
 633   }
 634
 635 private:
 636   /// We use a simple cost model for edit actions, which seems good enough.
 637   /// Simple cost model for edit actions. This seems to make the matching
 638   /// algorithm perform reasonably well.
 639   /// The values range between 0 and 1, or infinity if this edit action should
 640   /// always be avoided.
 641   static constexpr double DeletionCost = 1;
 642   static constexpr double InsertionCost = 1;
 643
 644   double getUpdateCost(SNodeId Id1, SNodeId Id2) {
 645     if (!DiffImpl.isMatchingPossible(S1.getIdInRoot(Id1), S2.getIdInRoot(Id2)))
 646       return std::numeric_limits<double>::max();
 647     return S1.getNodeValue(Id1) != S2.getNodeValue(Id2);
 648   }
 649
 650   void computeTreeDist() {
 651     for (SNodeId Id1 : S1.KeyRoots)
 652       for (SNodeId Id2 : S2.KeyRoots)
 653         computeForestDist(Id1, Id2);
 654   }
 655
 656   void computeForestDist(SNodeId Id1, SNodeId Id2) {
 657     assert(Id1 > 0 && Id2 > 0 && "Expecting offsets greater than 0.");
 658     SNodeId LMD1 = S1.getLeftMostDescendant(Id1);
 659     SNodeId LMD2 = S2.getLeftMostDescendant(Id2);
 660
 661     ForestDist[LMD1][LMD2] = 0;
 662     for (SNodeId D1 = LMD1 + 1; D1 <= Id1; ++D1) {
 663       ForestDist[D1][LMD2] = ForestDist[D1 - 1][LMD2] + DeletionCost;
 664       for (SNodeId D2 = LMD2 + 1; D2 <= Id2; ++D2) {
 665         ForestDist[LMD1][D2] = ForestDist[LMD1][D2 - 1] + InsertionCost;
 666         SNodeId DLMD1 = S1.getLeftMostDescendant(D1);
 667         SNodeId DLMD2 = S2.getLeftMostDescendant(D2);
 668         if (DLMD1 == LMD1 && DLMD2 == LMD2) {
 669           double UpdateCost = getUpdateCost(D1, D2);
 670           ForestDist[D1][D2] =
 671               std::min({ForestDist[D1 - 1][D2] + DeletionCost,
 672                         ForestDist[D1][D2 - 1] + InsertionCost,
 673                         ForestDist[D1 - 1][D2 - 1] + UpdateCost});
 674           TreeDist[D1][D2] = ForestDist[D1][D2];
 675         } else {
 676           ForestDist[D1][D2] =
 677               std::min({ForestDist[D1 - 1][D2] + DeletionCost,
 678                         ForestDist[D1][D2 - 1] + InsertionCost,
 679                         ForestDist[DLMD1][DLMD2] + TreeDist[D1][D2]});
 680         }
 681       }
 682     }
 683   }
 684 };
 685
 686 ASTNodeKind Node::getType() const { return ASTNode.getNodeKind(); }
 687
 688 StringRef Node::getTypeLabel() const { return getType().asStringRef(); }
 689
 690 std::optional<std::string> Node::getQualifiedIdentifier() const {
 691   if (auto *ND = ASTNode.get<NamedDecl>()) {
 692     if (ND->getDeclName().isIdentifier())
 693       return ND->getQualifiedNameAsString();
 694   }
 695   return std::nullopt;
 696 }
 697
 698 std::optional<StringRef> Node::getIdentifier() const {
 699   if (auto *ND = ASTNode.get<NamedDecl>()) {
 700     if (ND->getDeclName().isIdentifier())
 701       return ND->getName();
 702   }
 703   return std::nullopt;
 704 }
 705
 706 namespace {
 707 // Compares nodes by their depth.
 708 struct HeightLess {
 709   const SyntaxTree::Impl &Tree;
 710   HeightLess(const SyntaxTree::Impl &Tree) : Tree(Tree) {}
 711   bool operator()(NodeId Id1, NodeId Id2) const {
 712     return Tree.getNode(Id1).Height < Tree.getNode(Id2).Height;
 713   }
 714 };
 715 } // end anonymous namespace
 716
 717 namespace {
 718 // Priority queue for nodes, sorted descendingly by their height.
 719 class PriorityList {
 720   const SyntaxTree::Impl &Tree;
 721   HeightLess Cmp;
 722   std::vector<NodeId> Container;
 723   PriorityQueue<NodeId, std::vector<NodeId>, HeightLess> List;
 724
 725 public:
 726   PriorityList(const SyntaxTree::Impl &Tree)
 727       : Tree(Tree), Cmp(Tree), List(Cmp, Container) {}
 728
 729   void push(NodeId id) { List.push(id); }
 730
 731   std::vector<NodeId> pop() {
 732     int Max = peekMax();
 733     std::vector<NodeId> Result;
 734     if (Max == 0)
 735       return Result;
 736     while (peekMax() == Max) {
 737       Result.push_back(List.top());
 738       List.pop();
 739     }
 740     // TODO this is here to get a stable output, not a good heuristic
 741     llvm::sort(Result);
 742     return Result;
 743   }
 744   int peekMax() const {
 745     if (List.empty())
 746       return 0;
 747     return Tree.getNode(List.top()).Height;
 748   }
 749   void open(NodeId Id) {
 750     for (NodeId Child : Tree.getNode(Id).Children)
 751       push(Child);
 752   }
 753 };
 754 } // end anonymous namespace
 755
 756 bool ASTDiff::Impl::identical(NodeId Id1, NodeId Id2) const {
 757   const Node &N1 = T1.getNode(Id1);
 758   const Node &N2 = T2.getNode(Id2);
 759   if (N1.Children.size() != N2.Children.size() ||
 760       !isMatchingPossible(Id1, Id2) ||
 761       T1.getNodeValue(Id1) != T2.getNodeValue(Id2))
 762     return false;
 763   for (size_t Id = 0, E = N1.Children.size(); Id < E; ++Id)
 764     if (!identical(N1.Children[Id], N2.Children[Id]))
 765       return false;
 766   return true;
 767 }
 768
 769 bool ASTDiff::Impl::isMatchingPossible(NodeId Id1, NodeId Id2) const {
 770   return Options.isMatchingAllowed(T1.getNode(Id1), T2.getNode(Id2));
 771 }
 772
 773 bool ASTDiff::Impl::haveSameParents(const Mapping &M, NodeId Id1,
 774                                     NodeId Id2) const {
 775   NodeId P1 = T1.getNode(Id1).Parent;
 776   NodeId P2 = T2.getNode(Id2).Parent;
 777   return (P1.isInvalid() && P2.isInvalid()) ||
 778          (P1.isValid() && P2.isValid() && M.getDst(P1) == P2);
 779 }
 780
 781 void ASTDiff::Impl::addOptimalMapping(Mapping &M, NodeId Id1,
 782                                       NodeId Id2) const {
 783   if (std::max(T1.getNumberOfDescendants(Id1), T2.getNumberOfDescendants(Id2)) >
 784       Options.MaxSize)
 785     return;
 786   ZhangShashaMatcher Matcher(*this, T1, T2, Id1, Id2);
 787   std::vector<std::pair<NodeId, NodeId>> R = Matcher.getMatchingNodes();
 788   for (const auto &Tuple : R) {
 789     NodeId Src = Tuple.first;
 790     NodeId Dst = Tuple.second;
 791     if (!M.hasSrc(Src) && !M.hasDst(Dst))
 792       M.link(Src, Dst);
 793   }
 794 }
 795
 796 double ASTDiff::Impl::getJaccardSimilarity(const Mapping &M, NodeId Id1,
 797                                            NodeId Id2) const {
 798   int CommonDescendants = 0;
 799   const Node &N1 = T1.getNode(Id1);
 800   // Count the common descendants, excluding the subtree root.
 801   for (NodeId Src = Id1 + 1; Src <= N1.RightMostDescendant; ++Src) {
 802     NodeId Dst = M.getDst(Src);
 803     CommonDescendants += int(Dst.isValid() && T2.isInSubtree(Dst, Id2));
 804   }
 805   // We need to subtract 1 to get the number of descendants excluding the root.
 806   double Denominator = T1.getNumberOfDescendants(Id1) - 1 +
 807                        T2.getNumberOfDescendants(Id2) - 1 - CommonDescendants;
 808   // CommonDescendants is less than the size of one subtree.
 809   assert(Denominator >= 0 && "Expected non-negative denominator.");
 810   if (Denominator == 0)
 811     return 0;
 812   return CommonDescendants / Denominator;
 813 }
 814
 815 NodeId ASTDiff::Impl::findCandidate(const Mapping &M, NodeId Id1) const {
 816   NodeId Candidate;
 817   double HighestSimilarity = 0.0;
 818   for (NodeId Id2 : T2) {
 819     if (!isMatchingPossible(Id1, Id2))
 820       continue;
 821     if (M.hasDst(Id2))
 822       continue;
 823     double Similarity = getJaccardSimilarity(M, Id1, Id2);
 824     if (Similarity >= Options.MinSimilarity && Similarity > HighestSimilarity) {
 825       HighestSimilarity = Similarity;
 826       Candidate = Id2;
 827     }
 828   }
 829   return Candidate;
 830 }
 831
 832 void ASTDiff::Impl::matchBottomUp(Mapping &M) const {
 833   std::vector<NodeId> Postorder = getSubtreePostorder(T1, T1.getRootId());
 834   for (NodeId Id1 : Postorder) {
 835     if (Id1 == T1.getRootId() && !M.hasSrc(T1.getRootId()) &&
 836         !M.hasDst(T2.getRootId())) {
 837       if (isMatchingPossible(T1.getRootId(), T2.getRootId())) {
 838         M.link(T1.getRootId(), T2.getRootId());
 839         addOptimalMapping(M, T1.getRootId(), T2.getRootId());
 840       }
 841       break;
 842     }
 843     bool Matched = M.hasSrc(Id1);
 844     const Node &N1 = T1.getNode(Id1);
 845     bool MatchedChildren = llvm::any_of(
 846         N1.Children, [&](NodeId Child) { return M.hasSrc(Child); });
 847     if (Matched || !MatchedChildren)
 848       continue;
 849     NodeId Id2 = findCandidate(M, Id1);
 850     if (Id2.isValid()) {
 851       M.link(Id1, Id2);
 852       addOptimalMapping(M, Id1, Id2);
 853     }
 854   }
 855 }
 856
 857 Mapping ASTDiff::Impl::matchTopDown() const {
 858   PriorityList L1(T1);
 859   PriorityList L2(T2);
 860
 861   Mapping M(T1.getSize() + T2.getSize());
 862
 863   L1.push(T1.getRootId());
 864   L2.push(T2.getRootId());
 865
 866   int Max1, Max2;
 867   while (std::min(Max1 = L1.peekMax(), Max2 = L2.peekMax()) >
 868          Options.MinHeight) {
 869     if (Max1 > Max2) {
 870       for (NodeId Id : L1.pop())
 871         L1.open(Id);
 872       continue;
 873     }
 874     if (Max2 > Max1) {
 875       for (NodeId Id : L2.pop())
 876         L2.open(Id);
 877       continue;
 878     }
 879     std::vector<NodeId> H1, H2;
 880     H1 = L1.pop();
 881     H2 = L2.pop();
 882     for (NodeId Id1 : H1) {
 883       for (NodeId Id2 : H2) {
 884         if (identical(Id1, Id2) && !M.hasSrc(Id1) && !M.hasDst(Id2)) {
 885           for (int I = 0, E = T1.getNumberOfDescendants(Id1); I < E; ++I)
 886             M.link(Id1 + I, Id2 + I);
 887         }
 888       }
 889     }
 890     for (NodeId Id1 : H1) {
 891       if (!M.hasSrc(Id1))
 892         L1.open(Id1);
 893     }
 894     for (NodeId Id2 : H2) {
 895       if (!M.hasDst(Id2))
 896         L2.open(Id2);
 897     }
 898   }
 899   return M;
 900 }
 901
 902 ASTDiff::Impl::Impl(SyntaxTree::Impl &T1, SyntaxTree::Impl &T2,
 903                     const ComparisonOptions &Options)
 904     : T1(T1), T2(T2), Options(Options) {
 905   computeMapping();
 906   computeChangeKinds(TheMapping);
 907 }
 908
 909 void ASTDiff::Impl::computeMapping() {
 910   TheMapping = matchTopDown();
 911   if (Options.StopAfterTopDown)
 912     return;
 913   matchBottomUp(TheMapping);
 914 }
 915
 916 void ASTDiff::Impl::computeChangeKinds(Mapping &M) {
 917   for (NodeId Id1 : T1) {
 918     if (!M.hasSrc(Id1)) {
 919       T1.getMutableNode(Id1).Change = Delete;
 920       T1.getMutableNode(Id1).Shift -= 1;
 921     }
 922   }
 923   for (NodeId Id2 : T2) {
 924     if (!M.hasDst(Id2)) {
 925       T2.getMutableNode(Id2).Change = Insert;
 926       T2.getMutableNode(Id2).Shift -= 1;
 927     }
 928   }
 929   for (NodeId Id1 : T1.NodesBfs) {
 930     NodeId Id2 = M.getDst(Id1);
 931     if (Id2.isInvalid())
 932       continue;
 933     if (!haveSameParents(M, Id1, Id2) ||
 934         T1.findPositionInParent(Id1, true) !=
 935             T2.findPositionInParent(Id2, true)) {
 936       T1.getMutableNode(Id1).Shift -= 1;
 937       T2.getMutableNode(Id2).Shift -= 1;
 938     }
 939   }
 940   for (NodeId Id2 : T2.NodesBfs) {
 941     NodeId Id1 = M.getSrc(Id2);
 942     if (Id1.isInvalid())
 943       continue;
 944     Node &N1 = T1.getMutableNode(Id1);
 945     Node &N2 = T2.getMutableNode(Id2);
 946     if (Id1.isInvalid())
 947       continue;
 948     if (!haveSameParents(M, Id1, Id2) ||
 949         T1.findPositionInParent(Id1, true) !=
 950             T2.findPositionInParent(Id2, true)) {
 951       N1.Change = N2.Change = Move;
 952     }
 953     if (T1.getNodeValue(Id1) != T2.getNodeValue(Id2)) {
 954       N1.Change = N2.Change = (N1.Change == Move ? UpdateMove : Update);
 955     }
 956   }
 957 }
 958
 959 ASTDiff::ASTDiff(SyntaxTree &T1, SyntaxTree &T2,
 960                  const ComparisonOptions &Options)
 961     : DiffImpl(std::make_unique<Impl>(*T1.TreeImpl, *T2.TreeImpl, Options)) {}
 962
 963 ASTDiff::~ASTDiff() = default;
 964
 965 NodeId ASTDiff::getMapped(const SyntaxTree &SourceTree, NodeId Id) const {
 966   return DiffImpl->getMapped(SourceTree.TreeImpl, Id);
 967 }
 968
 969 SyntaxTree::SyntaxTree(ASTContext &AST)
 970     : TreeImpl(std::make_unique<SyntaxTree::Impl>(
 971           this, AST.getTranslationUnitDecl(), AST)) {}
 972
 973 SyntaxTree::~SyntaxTree() = default;
 974
 975 const ASTContext &SyntaxTree::getASTContext() const { return TreeImpl->AST; }
 976
 977 const Node &SyntaxTree::getNode(NodeId Id) const {
 978   return TreeImpl->getNode(Id);
 979 }
 980
 981 int SyntaxTree::getSize() const { return TreeImpl->getSize(); }
 982 NodeId SyntaxTree::getRootId() const { return TreeImpl->getRootId(); }
 983 SyntaxTree::PreorderIterator SyntaxTree::begin() const {
 984   return TreeImpl->begin();
 985 }
 986 SyntaxTree::PreorderIterator SyntaxTree::end() const { return TreeImpl->end(); }
 987
 988 int SyntaxTree::findPositionInParent(NodeId Id) const {
 989   return TreeImpl->findPositionInParent(Id);
 990 }
 991
 992 std::pair<unsigned, unsigned>
 993 SyntaxTree::getSourceRangeOffsets(const Node &N) const {
 994   const SourceManager &SrcMgr = TreeImpl->AST.getSourceManager();
 995   SourceRange Range = N.ASTNode.getSourceRange();
 996   SourceLocation BeginLoc = Range.getBegin();
 997   SourceLocation EndLoc = Lexer::getLocForEndOfToken(
 998       Range.getEnd(), /*Offset=*/0, SrcMgr, TreeImpl->AST.getLangOpts());
 999   if (auto *ThisExpr = N.ASTNode.get<CXXThisExpr>()) {
1000     if (ThisExpr->isImplicit())
1001       EndLoc = BeginLoc;
1002   }
1003   unsigned Begin = SrcMgr.getFileOffset(SrcMgr.getExpansionLoc(BeginLoc));
1004   unsigned End = SrcMgr.getFileOffset(SrcMgr.getExpansionLoc(EndLoc));
1005   return {Begin, End};
1006 }
1007
1008 std::string SyntaxTree::getNodeValue(NodeId Id) const {
1009   return TreeImpl->getNodeValue(Id);
1010 }
1011
1012 std::string SyntaxTree::getNodeValue(const Node &N) const {
1013   return TreeImpl->getNodeValue(N);
1014 }
1015
1016 } // end namespace diff
1017 } // end namespace clang