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