contrib/llvm/tools/clang/lib/Tooling/ASTDiff/ASTDiff.cpp

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