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