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