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