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