clang 18.0.0git
ASTDiff.cpp
Go to the documentation of this file.
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
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[]>(Size);
41 DstToSrc = std::make_unique<NodeId[]>(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
59public:
61 Mapping TheMapping;
62
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(Id);
76 assert(&*Tree == &T2 && "Invalid tree.");
77 return TheMapping.getSrc(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.
114public:
116 /// Constructs a tree from an AST node.
119 template <class T>
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>
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
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]; }
145 bool isValidNodeId(NodeId Id) const { return Id >= 0 && Id < getSize(); }
146 void addNode(Node &N) { Nodes.push_back(N); }
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; }
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(SLoc))
179 return true;
180 // Ignore macros.
181 if (SLoc != SrcMgr.getSpellingLoc(SLoc))
182 return true;
183 }
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(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(Parent);
207 P.Children.push_back(MyId);
208 }
209 Parent = MyId;
210 ++Id;
211 ++Depth;
212 return std::make_tuple(MyId, Tree.getNode(MyId).Parent);
213 }
214 void PostTraverse(std::tuple<NodeId, NodeId> State) {
215 NodeId MyId, PreviousParent;
216 std::tie(MyId, PreviousParent) = State;
217 assert(MyId.isValid() && "Expecting to only traverse valid nodes.");
218 Parent = PreviousParent;
219 --Depth;
220 Node &N = Tree.getMutableNode(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(MyId);
227 N.Height = 1;
228 for (NodeId Child : N.Children)
229 N.Height = std::max(N.Height, 1 + Tree.getNode(Child).Height);
230 }
231 bool TraverseDecl(Decl *D) {
232 if (isNodeExcluded(Tree.AST.getSourceManager(), D))
233 return true;
234 auto SavedState = PreTraverse(D);
236 PostTraverse(SavedState);
237 return true;
238 }
239 bool TraverseStmt(Stmt *S) {
240 if (auto *E = dyn_cast_or_null<Expr>(S))
241 S = E->IgnoreImplicit();
242 if (isNodeExcluded(Tree.AST.getSourceManager(), S))
243 return true;
244 auto SavedState = PreTraverse(S);
246 PostTraverse(SavedState);
247 return true;
248 }
249 bool TraverseType(QualType T) { return true; }
250 bool TraverseConstructorInitializer(CXXCtorInitializer *Init) {
251 if (isNodeExcluded(Tree.AST.getSourceManager(), Init))
252 return true;
253 auto SavedState = PreTraverse(Init);
255 PostTraverse(SavedState);
256 return true;
257 }
258};
259} // end anonymous namespace
260
262 : Parent(Parent), AST(AST), TypePP(AST.getLangOpts()) {
264}
265
267 : Impl(Parent, AST) {
268 PreorderVisitor PreorderWalker(*this);
269 PreorderWalker.TraverseDecl(N);
270 initTree();
271}
272
274 : Impl(Parent, AST) {
275 PreorderVisitor PreorderWalker(*this);
276 PreorderWalker.TraverseStmt(N);
277 initTree();
278}
279
280static std::vector<NodeId> getSubtreePostorder(const SyntaxTree::Impl &Tree,
281 NodeId Root) {
282 std::vector<NodeId> Postorder;
283 std::function<void(NodeId)> Traverse = [&](NodeId Id) {
284 const Node &N = Tree.getNode(Id);
285 for (NodeId Child : N.Children)
286 Traverse(Child);
287 Postorder.push_back(Id);
288 };
289 Traverse(Root);
290 return Postorder;
291}
292
293static std::vector<NodeId> getSubtreeBfs(const SyntaxTree::Impl &Tree,
294 NodeId Root) {
295 std::vector<NodeId> Ids;
296 size_t Expanded = 0;
297 Ids.push_back(Root);
298 while (Expanded < Ids.size())
299 for (NodeId Child : Tree.getNode(Ids[Expanded++]).Children)
300 Ids.push_back(Child);
301 return Ids;
302}
303
304void SyntaxTree::Impl::initTree() {
305 setLeftMostDescendants();
306 int PostorderId = 0;
307 PostorderIds.resize(getSize());
308 std::function<void(NodeId)> PostorderTraverse = [&](NodeId Id) {
309 for (NodeId Child : getNode(Id).Children)
310 PostorderTraverse(Child);
311 PostorderIds[Id] = PostorderId;
312 ++PostorderId;
313 };
314 PostorderTraverse(getRootId());
315 NodesBfs = getSubtreeBfs(*this, getRootId());
316}
317
318void SyntaxTree::Impl::setLeftMostDescendants() {
319 for (NodeId Leaf : Leaves) {
320 getMutableNode(Leaf).LeftMostDescendant = Leaf;
321 NodeId Parent, Cur = Leaf;
322 while ((Parent = getNode(Cur).Parent).isValid() &&
323 getNode(Parent).Children[0] == Cur) {
324 Cur = Parent;
325 getMutableNode(Cur).LeftMostDescendant = Leaf;
326 }
327 }
328}
329
331 return getNode(Id).RightMostDescendant - Id + 1;
332}
333
335 return Id >= SubtreeRoot && Id <= getNode(SubtreeRoot).RightMostDescendant;
336}
337
340 if (Parent.isInvalid())
341 return 0;
342 const auto &Siblings = getNode(Parent).Children;
343 int Position = 0;
344 for (size_t I = 0, E = Siblings.size(); I < E; ++I) {
345 if (Shifted)
346 Position += getNode(Siblings[I]).Shift;
347 if (Siblings[I] == Id) {
348 Position += I;
349 return Position;
350 }
351 }
352 llvm_unreachable("Node not found in parent's children.");
353}
354
355// Returns the qualified name of ND. If it is subordinate to Context,
356// then the prefix of the latter is removed from the returned value.
357std::string
359 const DeclContext *Context) const {
360 std::string Val = ND->getQualifiedNameAsString();
361 std::string ContextPrefix;
362 if (!Context)
363 return Val;
364 if (auto *Namespace = dyn_cast<NamespaceDecl>(Context))
365 ContextPrefix = Namespace->getQualifiedNameAsString();
366 else if (auto *Record = dyn_cast<RecordDecl>(Context))
367 ContextPrefix = Record->getQualifiedNameAsString();
368 else if (AST.getLangOpts().CPlusPlus11)
369 if (auto *Tag = dyn_cast<TagDecl>(Context))
370 ContextPrefix = Tag->getQualifiedNameAsString();
371 // Strip the qualifier, if Val refers to something in the current scope.
372 // But leave one leading ':' in place, so that we know that this is a
373 // relative path.
374 if (!ContextPrefix.empty() && StringRef(Val).startswith(ContextPrefix))
375 Val = Val.substr(ContextPrefix.size() + 1);
376 return Val;
377}
378
379std::string SyntaxTree::Impl::getRelativeName(const NamedDecl *ND) const {
380 return getRelativeName(ND, ND->getDeclContext());
381}
382
384 const Stmt *S) {
385 while (S) {
386 const auto &Parents = AST.getParents(*S);
387 if (Parents.empty())
388 return nullptr;
389 const auto &P = Parents[0];
390 if (const auto *D = P.get<Decl>())
391 return D->getDeclContext();
392 S = P.get<Stmt>();
393 }
394 return nullptr;
395}
396
397static std::string getInitializerValue(const CXXCtorInitializer *Init,
398 const PrintingPolicy &TypePP) {
399 if (Init->isAnyMemberInitializer())
400 return std::string(Init->getAnyMember()->getName());
401 if (Init->isBaseInitializer())
402 return QualType(Init->getBaseClass(), 0).getAsString(TypePP);
403 if (Init->isDelegatingInitializer())
404 return Init->getTypeSourceInfo()->getType().getAsString(TypePP);
405 llvm_unreachable("Unknown initializer type");
406}
407
409 return getNodeValue(getNode(Id));
410}
411
412std::string SyntaxTree::Impl::getNodeValue(const Node &N) const {
413 const DynTypedNode &DTN = N.ASTNode;
414 if (auto *S = DTN.get<Stmt>())
415 return getStmtValue(S);
416 if (auto *D = DTN.get<Decl>())
417 return getDeclValue(D);
418 if (auto *Init = DTN.get<CXXCtorInitializer>())
419 return getInitializerValue(Init, TypePP);
420 llvm_unreachable("Fatal: unhandled AST node.\n");
421}
422
423std::string SyntaxTree::Impl::getDeclValue(const Decl *D) const {
424 std::string Value;
425 if (auto *V = dyn_cast<ValueDecl>(D))
426 return getRelativeName(V) + "(" + V->getType().getAsString(TypePP) + ")";
427 if (auto *N = dyn_cast<NamedDecl>(D))
428 Value += getRelativeName(N) + ";";
429 if (auto *T = dyn_cast<TypedefNameDecl>(D))
430 return Value + T->getUnderlyingType().getAsString(TypePP) + ";";
431 if (auto *T = dyn_cast<TypeDecl>(D))
432 if (T->getTypeForDecl())
433 Value +=
434 T->getTypeForDecl()->getCanonicalTypeInternal().getAsString(TypePP) +
435 ";";
436 if (auto *U = dyn_cast<UsingDirectiveDecl>(D))
437 return std::string(U->getNominatedNamespace()->getName());
438 if (auto *A = dyn_cast<AccessSpecDecl>(D)) {
439 CharSourceRange Range(A->getSourceRange(), false);
440 return std::string(
441 Lexer::getSourceText(Range, AST.getSourceManager(), AST.getLangOpts()));
442 }
443 return Value;
444}
445
446std::string SyntaxTree::Impl::getStmtValue(const Stmt *S) const {
447 if (auto *U = dyn_cast<UnaryOperator>(S))
448 return std::string(UnaryOperator::getOpcodeStr(U->getOpcode()));
449 if (auto *B = dyn_cast<BinaryOperator>(S))
450 return std::string(B->getOpcodeStr());
451 if (auto *M = dyn_cast<MemberExpr>(S))
452 return getRelativeName(M->getMemberDecl());
453 if (auto *I = dyn_cast<IntegerLiteral>(S)) {
455 I->getValue().toString(Str, /*Radix=*/10, /*Signed=*/false);
456 return std::string(Str.str());
457 }
458 if (auto *F = dyn_cast<FloatingLiteral>(S)) {
460 F->getValue().toString(Str);
461 return std::string(Str.str());
462 }
463 if (auto *D = dyn_cast<DeclRefExpr>(S))
464 return getRelativeName(D->getDecl(), getEnclosingDeclContext(AST, S));
465 if (auto *String = dyn_cast<StringLiteral>(S))
466 return std::string(String->getString());
467 if (auto *B = dyn_cast<CXXBoolLiteralExpr>(S))
468 return B->getValue() ? "true" : "false";
469 return "";
470}
471
472/// Identifies a node in a subtree by its postorder offset, starting at 1.
473struct SNodeId {
474 int Id = 0;
475
476 explicit SNodeId(int Id) : Id(Id) {}
477 explicit SNodeId() = default;
478
479 operator int() const { return Id; }
480 SNodeId &operator++() { return ++Id, *this; }
481 SNodeId &operator--() { return --Id, *this; }
482 SNodeId operator+(int Other) const { return SNodeId(Id + Other); }
483};
484
485class Subtree {
486private:
487 /// The parent tree.
488 const SyntaxTree::Impl &Tree;
489 /// Maps SNodeIds to original ids.
490 std::vector<NodeId> RootIds;
491 /// Maps subtree nodes to their leftmost descendants wtihin the subtree.
492 std::vector<SNodeId> LeftMostDescendants;
493
494public:
495 std::vector<SNodeId> KeyRoots;
496
497 Subtree(const SyntaxTree::Impl &Tree, NodeId SubtreeRoot) : Tree(Tree) {
498 RootIds = getSubtreePostorder(Tree, SubtreeRoot);
499 int NumLeaves = setLeftMostDescendants();
500 computeKeyRoots(NumLeaves);
501 }
502 int getSize() const { return RootIds.size(); }
504 assert(Id > 0 && Id <= getSize() && "Invalid subtree node index.");
505 return RootIds[Id - 1];
506 }
507 const Node &getNode(SNodeId Id) const {
508 return Tree.getNode(getIdInRoot(Id));
509 }
511 assert(Id > 0 && Id <= getSize() && "Invalid subtree node index.");
512 return LeftMostDescendants[Id - 1];
513 }
514 /// Returns the postorder index of the leftmost descendant in the subtree.
516 return Tree.PostorderIds[getIdInRoot(SNodeId(1))];
517 }
518 std::string getNodeValue(SNodeId Id) const {
519 return Tree.getNodeValue(getIdInRoot(Id));
520 }
521
522private:
523 /// Returns the number of leafs in the subtree.
524 int setLeftMostDescendants() {
525 int NumLeaves = 0;
526 LeftMostDescendants.resize(getSize());
527 for (int I = 0; I < getSize(); ++I) {
528 SNodeId SI(I + 1);
529 const Node &N = getNode(SI);
530 NumLeaves += N.isLeaf();
531 assert(I == Tree.PostorderIds[getIdInRoot(SI)] - getPostorderOffset() &&
532 "Postorder traversal in subtree should correspond to traversal in "
533 "the root tree by a constant offset.");
534 LeftMostDescendants[I] = SNodeId(Tree.PostorderIds[N.LeftMostDescendant] -
535 getPostorderOffset());
536 }
537 return NumLeaves;
538 }
539 void computeKeyRoots(int Leaves) {
540 KeyRoots.resize(Leaves);
541 std::unordered_set<int> Visited;
542 int K = Leaves - 1;
543 for (SNodeId I(getSize()); I > 0; --I) {
544 SNodeId LeftDesc = getLeftMostDescendant(I);
545 if (Visited.count(LeftDesc))
546 continue;
547 assert(K >= 0 && "K should be non-negative");
548 KeyRoots[K] = I;
549 Visited.insert(LeftDesc);
550 --K;
551 }
552 }
553};
554
555/// Implementation of Zhang and Shasha's Algorithm for tree edit distance.
556/// Computes an optimal mapping between two trees using only insertion,
557/// deletion and update as edit actions (similar to the Levenshtein distance).
559 const ASTDiff::Impl &DiffImpl;
560 Subtree S1;
561 Subtree S2;
562 std::unique_ptr<std::unique_ptr<double[]>[]> TreeDist, ForestDist;
563
564public:
566 const SyntaxTree::Impl &T2, NodeId Id1, NodeId Id2)
567 : DiffImpl(DiffImpl), S1(T1, Id1), S2(T2, Id2) {
568 TreeDist = std::make_unique<std::unique_ptr<double[]>[]>(
569 size_t(S1.getSize()) + 1);
570 ForestDist = std::make_unique<std::unique_ptr<double[]>[]>(
571 size_t(S1.getSize()) + 1);
572 for (int I = 0, E = S1.getSize() + 1; I < E; ++I) {
573 TreeDist[I] = std::make_unique<double[]>(size_t(S2.getSize()) + 1);
574 ForestDist[I] = std::make_unique<double[]>(size_t(S2.getSize()) + 1);
575 }
576 }
577
578 std::vector<std::pair<NodeId, NodeId>> getMatchingNodes() {
579 std::vector<std::pair<NodeId, NodeId>> Matches;
580 std::vector<std::pair<SNodeId, SNodeId>> TreePairs;
581
582 computeTreeDist();
583
584 bool RootNodePair = true;
585
586 TreePairs.emplace_back(SNodeId(S1.getSize()), SNodeId(S2.getSize()));
587
588 while (!TreePairs.empty()) {
589 SNodeId LastRow, LastCol, FirstRow, FirstCol, Row, Col;
590 std::tie(LastRow, LastCol) = TreePairs.back();
591 TreePairs.pop_back();
592
593 if (!RootNodePair) {
594 computeForestDist(LastRow, LastCol);
595 }
596
597 RootNodePair = false;
598
599 FirstRow = S1.getLeftMostDescendant(LastRow);
600 FirstCol = S2.getLeftMostDescendant(LastCol);
601
602 Row = LastRow;
603 Col = LastCol;
604
605 while (Row > FirstRow || Col > FirstCol) {
606 if (Row > FirstRow &&
607 ForestDist[Row - 1][Col] + 1 == ForestDist[Row][Col]) {
608 --Row;
609 } else if (Col > FirstCol &&
610 ForestDist[Row][Col - 1] + 1 == ForestDist[Row][Col]) {
611 --Col;
612 } else {
613 SNodeId LMD1 = S1.getLeftMostDescendant(Row);
614 SNodeId LMD2 = S2.getLeftMostDescendant(Col);
615 if (LMD1 == S1.getLeftMostDescendant(LastRow) &&
616 LMD2 == S2.getLeftMostDescendant(LastCol)) {
617 NodeId Id1 = S1.getIdInRoot(Row);
618 NodeId Id2 = S2.getIdInRoot(Col);
619 assert(DiffImpl.isMatchingPossible(Id1, Id2) &&
620 "These nodes must not be matched.");
621 Matches.emplace_back(Id1, Id2);
622 --Row;
623 --Col;
624 } else {
625 TreePairs.emplace_back(Row, Col);
626 Row = LMD1;
627 Col = LMD2;
628 }
629 }
630 }
631 }
632 return Matches;
633 }
634
635private:
636 /// We use a simple cost model for edit actions, which seems good enough.
637 /// Simple cost model for edit actions. This seems to make the matching
638 /// algorithm perform reasonably well.
639 /// The values range between 0 and 1, or infinity if this edit action should
640 /// always be avoided.
641 static constexpr double DeletionCost = 1;
642 static constexpr double InsertionCost = 1;
643
644 double getUpdateCost(SNodeId Id1, SNodeId Id2) {
645 if (!DiffImpl.isMatchingPossible(S1.getIdInRoot(Id1), S2.getIdInRoot(Id2)))
646 return std::numeric_limits<double>::max();
647 return S1.getNodeValue(Id1) != S2.getNodeValue(Id2);
648 }
649
650 void computeTreeDist() {
651 for (SNodeId Id1 : S1.KeyRoots)
652 for (SNodeId Id2 : S2.KeyRoots)
653 computeForestDist(Id1, Id2);
654 }
655
656 void computeForestDist(SNodeId Id1, SNodeId Id2) {
657 assert(Id1 > 0 && Id2 > 0 && "Expecting offsets greater than 0.");
658 SNodeId LMD1 = S1.getLeftMostDescendant(Id1);
659 SNodeId LMD2 = S2.getLeftMostDescendant(Id2);
660
661 ForestDist[LMD1][LMD2] = 0;
662 for (SNodeId D1 = LMD1 + 1; D1 <= Id1; ++D1) {
663 ForestDist[D1][LMD2] = ForestDist[D1 - 1][LMD2] + DeletionCost;
664 for (SNodeId D2 = LMD2 + 1; D2 <= Id2; ++D2) {
665 ForestDist[LMD1][D2] = ForestDist[LMD1][D2 - 1] + InsertionCost;
666 SNodeId DLMD1 = S1.getLeftMostDescendant(D1);
667 SNodeId DLMD2 = S2.getLeftMostDescendant(D2);
668 if (DLMD1 == LMD1 && DLMD2 == LMD2) {
669 double UpdateCost = getUpdateCost(D1, D2);
670 ForestDist[D1][D2] =
671 std::min({ForestDist[D1 - 1][D2] + DeletionCost,
672 ForestDist[D1][D2 - 1] + InsertionCost,
673 ForestDist[D1 - 1][D2 - 1] + UpdateCost});
674 TreeDist[D1][D2] = ForestDist[D1][D2];
675 } else {
676 ForestDist[D1][D2] =
677 std::min({ForestDist[D1 - 1][D2] + DeletionCost,
678 ForestDist[D1][D2 - 1] + InsertionCost,
679 ForestDist[DLMD1][DLMD2] + TreeDist[D1][D2]});
680 }
681 }
682 }
683 }
684};
685
686ASTNodeKind Node::getType() const { return ASTNode.getNodeKind(); }
687
688StringRef Node::getTypeLabel() const { return getType().asStringRef(); }
689
690std::optional<std::string> Node::getQualifiedIdentifier() const {
691 if (auto *ND = ASTNode.get<NamedDecl>()) {
692 if (ND->getDeclName().isIdentifier())
693 return ND->getQualifiedNameAsString();
694 }
695 return std::nullopt;
696}
697
698std::optional<StringRef> Node::getIdentifier() const {
699 if (auto *ND = ASTNode.get<NamedDecl>()) {
700 if (ND->getDeclName().isIdentifier())
701 return ND->getName();
702 }
703 return std::nullopt;
704}
705
706namespace {
707// Compares nodes by their depth.
708struct HeightLess {
709 const SyntaxTree::Impl &Tree;
710 HeightLess(const SyntaxTree::Impl &Tree) : Tree(Tree) {}
711 bool operator()(NodeId Id1, NodeId Id2) const {
712 return Tree.getNode(Id1).Height < Tree.getNode(Id2).Height;
713 }
714};
715} // end anonymous namespace
716
717namespace {
718// Priority queue for nodes, sorted descendingly by their height.
719class PriorityList {
720 const SyntaxTree::Impl &Tree;
721 HeightLess Cmp;
722 std::vector<NodeId> Container;
723 PriorityQueue<NodeId, std::vector<NodeId>, HeightLess> List;
724
725public:
726 PriorityList(const SyntaxTree::Impl &Tree)
727 : Tree(Tree), Cmp(Tree), List(Cmp, Container) {}
728
729 void push(NodeId id) { List.push(id); }
730
731 std::vector<NodeId> pop() {
732 int Max = peekMax();
733 std::vector<NodeId> Result;
734 if (Max == 0)
735 return Result;
736 while (peekMax() == Max) {
737 Result.push_back(List.top());
738 List.pop();
739 }
740 // TODO this is here to get a stable output, not a good heuristic
741 llvm::sort(Result);
742 return Result;
743 }
744 int peekMax() const {
745 if (List.empty())
746 return 0;
747 return Tree.getNode(List.top()).Height;
748 }
749 void open(NodeId Id) {
750 for (NodeId Child : Tree.getNode(Id).Children)
751 push(Child);
752 }
753};
754} // end anonymous namespace
755
756bool ASTDiff::Impl::identical(NodeId Id1, NodeId Id2) const {
757 const Node &N1 = T1.getNode(Id1);
758 const Node &N2 = T2.getNode(Id2);
759 if (N1.Children.size() != N2.Children.size() ||
760 !isMatchingPossible(Id1, Id2) ||
761 T1.getNodeValue(Id1) != T2.getNodeValue(Id2))
762 return false;
763 for (size_t Id = 0, E = N1.Children.size(); Id < E; ++Id)
764 if (!identical(N1.Children[Id], N2.Children[Id]))
765 return false;
766 return true;
767}
768
769bool ASTDiff::Impl::isMatchingPossible(NodeId Id1, NodeId Id2) const {
770 return Options.isMatchingAllowed(T1.getNode(Id1), T2.getNode(Id2));
771}
772
773bool ASTDiff::Impl::haveSameParents(const Mapping &M, NodeId Id1,
774 NodeId Id2) const {
775 NodeId P1 = T1.getNode(Id1).Parent;
776 NodeId P2 = T2.getNode(Id2).Parent;
777 return (P1.isInvalid() && P2.isInvalid()) ||
778 (P1.isValid() && P2.isValid() && M.getDst(P1) == P2);
779}
780
781void ASTDiff::Impl::addOptimalMapping(Mapping &M, NodeId Id1,
782 NodeId Id2) const {
783 if (std::max(T1.getNumberOfDescendants(Id1), T2.getNumberOfDescendants(Id2)) >
784 Options.MaxSize)
785 return;
786 ZhangShashaMatcher Matcher(*this, T1, T2, Id1, Id2);
787 std::vector<std::pair<NodeId, NodeId>> R = Matcher.getMatchingNodes();
788 for (const auto &Tuple : R) {
789 NodeId Src = Tuple.first;
790 NodeId Dst = Tuple.second;
791 if (!M.hasSrc(Src) && !M.hasDst(Dst))
792 M.link(Src, Dst);
793 }
794}
795
796double ASTDiff::Impl::getJaccardSimilarity(const Mapping &M, NodeId Id1,
797 NodeId Id2) const {
798 int CommonDescendants = 0;
799 const Node &N1 = T1.getNode(Id1);
800 // Count the common descendants, excluding the subtree root.
801 for (NodeId Src = Id1 + 1; Src <= N1.RightMostDescendant; ++Src) {
802 NodeId Dst = M.getDst(Src);
803 CommonDescendants += int(Dst.isValid() && T2.isInSubtree(Dst, Id2));
804 }
805 // We need to subtract 1 to get the number of descendants excluding the root.
806 double Denominator = T1.getNumberOfDescendants(Id1) - 1 +
807 T2.getNumberOfDescendants(Id2) - 1 - CommonDescendants;
808 // CommonDescendants is less than the size of one subtree.
809 assert(Denominator >= 0 && "Expected non-negative denominator.");
810 if (Denominator == 0)
811 return 0;
812 return CommonDescendants / Denominator;
813}
814
815NodeId ASTDiff::Impl::findCandidate(const Mapping &M, NodeId Id1) const {
816 NodeId Candidate;
817 double HighestSimilarity = 0.0;
818 for (NodeId Id2 : T2) {
819 if (!isMatchingPossible(Id1, Id2))
820 continue;
821 if (M.hasDst(Id2))
822 continue;
823 double Similarity = getJaccardSimilarity(M, Id1, Id2);
824 if (Similarity >= Options.MinSimilarity && Similarity > HighestSimilarity) {
825 HighestSimilarity = Similarity;
826 Candidate = Id2;
827 }
828 }
829 return Candidate;
830}
831
832void ASTDiff::Impl::matchBottomUp(Mapping &M) const {
833 std::vector<NodeId> Postorder = getSubtreePostorder(T1, T1.getRootId());
834 for (NodeId Id1 : Postorder) {
835 if (Id1 == T1.getRootId() && !M.hasSrc(T1.getRootId()) &&
836 !M.hasDst(T2.getRootId())) {
837 if (isMatchingPossible(T1.getRootId(), T2.getRootId())) {
838 M.link(T1.getRootId(), T2.getRootId());
839 addOptimalMapping(M, T1.getRootId(), T2.getRootId());
840 }
841 break;
842 }
843 bool Matched = M.hasSrc(Id1);
844 const Node &N1 = T1.getNode(Id1);
845 bool MatchedChildren = llvm::any_of(
846 N1.Children, [&](NodeId Child) { return M.hasSrc(Child); });
847 if (Matched || !MatchedChildren)
848 continue;
849 NodeId Id2 = findCandidate(M, Id1);
850 if (Id2.isValid()) {
851 M.link(Id1, Id2);
852 addOptimalMapping(M, Id1, Id2);
853 }
854 }
855}
856
857Mapping ASTDiff::Impl::matchTopDown() const {
858 PriorityList L1(T1);
859 PriorityList L2(T2);
860
861 Mapping M(T1.getSize() + T2.getSize());
862
863 L1.push(T1.getRootId());
864 L2.push(T2.getRootId());
865
866 int Max1, Max2;
867 while (std::min(Max1 = L1.peekMax(), Max2 = L2.peekMax()) >
868 Options.MinHeight) {
869 if (Max1 > Max2) {
870 for (NodeId Id : L1.pop())
871 L1.open(Id);
872 continue;
873 }
874 if (Max2 > Max1) {
875 for (NodeId Id : L2.pop())
876 L2.open(Id);
877 continue;
878 }
879 std::vector<NodeId> H1, H2;
880 H1 = L1.pop();
881 H2 = L2.pop();
882 for (NodeId Id1 : H1) {
883 for (NodeId Id2 : H2) {
884 if (identical(Id1, Id2) && !M.hasSrc(Id1) && !M.hasDst(Id2)) {
885 for (int I = 0, E = T1.getNumberOfDescendants(Id1); I < E; ++I)
886 M.link(Id1 + I, Id2 + I);
887 }
888 }
889 }
890 for (NodeId Id1 : H1) {
891 if (!M.hasSrc(Id1))
892 L1.open(Id1);
893 }
894 for (NodeId Id2 : H2) {
895 if (!M.hasDst(Id2))
896 L2.open(Id2);
897 }
898 }
899 return M;
900}
901
903 const ComparisonOptions &Options)
904 : T1(T1), T2(T2), Options(Options) {
907}
908
910 TheMapping = matchTopDown();
911 if (Options.StopAfterTopDown)
912 return;
913 matchBottomUp(TheMapping);
914}
915
917 for (NodeId Id1 : T1) {
918 if (!M.hasSrc(Id1)) {
919 T1.getMutableNode(Id1).Change = Delete;
920 T1.getMutableNode(Id1).Shift -= 1;
921 }
922 }
923 for (NodeId Id2 : T2) {
924 if (!M.hasDst(Id2)) {
925 T2.getMutableNode(Id2).Change = Insert;
926 T2.getMutableNode(Id2).Shift -= 1;
927 }
928 }
929 for (NodeId Id1 : T1.NodesBfs) {
930 NodeId Id2 = M.getDst(Id1);
931 if (Id2.isInvalid())
932 continue;
933 if (!haveSameParents(M, Id1, Id2) ||
934 T1.findPositionInParent(Id1, true) !=
935 T2.findPositionInParent(Id2, true)) {
936 T1.getMutableNode(Id1).Shift -= 1;
937 T2.getMutableNode(Id2).Shift -= 1;
938 }
939 }
940 for (NodeId Id2 : T2.NodesBfs) {
941 NodeId Id1 = M.getSrc(Id2);
942 if (Id1.isInvalid())
943 continue;
944 Node &N1 = T1.getMutableNode(Id1);
945 Node &N2 = T2.getMutableNode(Id2);
946 if (Id1.isInvalid())
947 continue;
948 if (!haveSameParents(M, Id1, Id2) ||
949 T1.findPositionInParent(Id1, true) !=
950 T2.findPositionInParent(Id2, true)) {
951 N1.Change = N2.Change = Move;
952 }
953 if (T1.getNodeValue(Id1) != T2.getNodeValue(Id2)) {
954 N1.Change = N2.Change = (N1.Change == Move ? UpdateMove : Update);
955 }
956 }
957}
958
960 const ComparisonOptions &Options)
961 : DiffImpl(std::make_unique<Impl>(*T1.TreeImpl, *T2.TreeImpl, Options)) {}
962
963ASTDiff::~ASTDiff() = default;
964
965NodeId ASTDiff::getMapped(const SyntaxTree &SourceTree, NodeId Id) const {
966 return DiffImpl->getMapped(SourceTree.TreeImpl, Id);
967}
968
970 : TreeImpl(std::make_unique<SyntaxTree::Impl>(
971 this, AST.getTranslationUnitDecl(), AST)) {}
972
973SyntaxTree::~SyntaxTree() = default;
974
975const ASTContext &SyntaxTree::getASTContext() const { return TreeImpl->AST; }
976
978 return TreeImpl->getNode(Id);
979}
980
981int SyntaxTree::getSize() const { return TreeImpl->getSize(); }
982NodeId SyntaxTree::getRootId() const { return TreeImpl->getRootId(); }
984 return TreeImpl->begin();
985}
987
989 return TreeImpl->findPositionInParent(Id);
990}
991
992std::pair<unsigned, unsigned>
994 const SourceManager &SrcMgr = TreeImpl->AST.getSourceManager();
995 SourceRange Range = N.ASTNode.getSourceRange();
996 SourceLocation BeginLoc = Range.getBegin();
998 Range.getEnd(), /*Offset=*/0, SrcMgr, TreeImpl->AST.getLangOpts());
999 if (auto *ThisExpr = N.ASTNode.get<CXXThisExpr>()) {
1000 if (ThisExpr->isImplicit())
1001 EndLoc = BeginLoc;
1002 }
1003 unsigned Begin = SrcMgr.getFileOffset(SrcMgr.getExpansionLoc(BeginLoc));
1004 unsigned End = SrcMgr.getFileOffset(SrcMgr.getExpansionLoc(EndLoc));
1005 return {Begin, End};
1006}
1007
1009 return TreeImpl->getNodeValue(Id);
1010}
1011
1012std::string SyntaxTree::getNodeValue(const Node &N) const {
1013 return TreeImpl->getNodeValue(N);
1014}
1015
1016} // end namespace diff
1017} // end namespace clang
#define V(N, I)
Definition: ASTContext.h:3233
NodeId Parent
Definition: ASTDiff.cpp:191
SyntaxTree::Impl & Tree
Definition: ASTDiff.cpp:192
int Id
Definition: ASTDiff.cpp:190
DynTypedNode Node
StringRef P
llvm::DenseSet< const void * > Visited
Definition: HTMLLogger.cpp:143
static Expected< DynTypedNode > getNode(const ast_matchers::BoundNodes &Nodes, StringRef ID)
Defines the SourceManager interface.
SourceLocation Begin
__device__ int
__SIZE_TYPE__ size_t
Holds long-lived AST nodes (such as types and decls) that can be referred to throughout the semantic ...
Definition: ASTContext.h:182
DynTypedNodeList getParents(const NodeT &Node)
Forwards to get node parents from the ParentMapContext.
Kind identifier.
Definition: ASTTypeTraits.h:51
Represents a C++ base or member initializer.
Definition: DeclCXX.h:2259
bool isWritten() const
Determine whether this initializer is explicitly written in the source code.
Definition: DeclCXX.h:2428
Represents the this expression in C++.
Definition: ExprCXX.h:1148
Represents a character-granular source range.
DeclContext - This is used only as base class of specific decl types that can act as declaration cont...
Definition: DeclBase.h:1409
Decl - This represents one declaration (or definition), e.g.
Definition: DeclBase.h:83
bool isImplicit() const
isImplicit - Indicates whether the declaration was implicitly generated by the implementation.
Definition: DeclBase.h:576
DeclContext * getDeclContext()
Definition: DeclBase.h:441
const T * get() const
Retrieve the stored node as type T.
static DynTypedNode create(const T &Node)
Creates a DynTypedNode from Node.
static StringRef getSourceText(CharSourceRange Range, const SourceManager &SM, const LangOptions &LangOpts, bool *Invalid=nullptr)
Returns a string for the source that the range encompasses.
Definition: Lexer.cpp:976
static SourceLocation getLocForEndOfToken(SourceLocation Loc, unsigned Offset, const SourceManager &SM, const LangOptions &LangOpts)
Computes the source location just past the end of the token at this source location.
Definition: Lexer.cpp:802
This represents a decl that may have a name.
Definition: Decl.h:247
std::string getQualifiedNameAsString() const
Definition: Decl.cpp:1680
A (possibly-)qualified type.
Definition: Type.h:736
static std::string getAsString(SplitQualType split, const PrintingPolicy &Policy)
Definition: Type.h:1120
A class that does preorder or postorder depth-first traversal on the entire Clang AST and visits each...
bool TraverseStmt(Stmt *S, DataRecursionQueue *Queue=nullptr)
Recursively visit a statement or expression, by dispatching to Traverse*() based on the argument's dy...
bool TraverseDecl(Decl *D)
Recursively visit a declaration, by dispatching to Traverse*Decl() based on the argument's dynamic ty...
bool TraverseConstructorInitializer(CXXCtorInitializer *Init)
Recursively visit a constructor initializer.
Encodes a location in the source.
bool isValid() const
Return true if this is a valid SourceLocation object.
This class handles loading and caching of source files into memory.
unsigned getFileOffset(SourceLocation SpellingLoc) const
Returns the offset from the start of the file that the specified SourceLocation represents.
bool isInMainFile(SourceLocation Loc) const
Returns whether the PresumedLoc for a given SourceLocation is in the main file.
SourceLocation getSpellingLoc(SourceLocation Loc) const
Given a SourceLocation object, return the spelling location referenced by the ID.
SourceLocation getExpansionLoc(SourceLocation Loc) const
Given a SourceLocation object Loc, return the expansion location referenced by the ID.
A trivial tuple used to represent a source range.
Stmt - This represents one statement.
Definition: Stmt.h:72
static StringRef getOpcodeStr(Opcode Op)
getOpcodeStr - Turn an Opcode enum value into the punctuation char it corresponds to,...
Definition: Expr.cpp:1420
void computeChangeKinds(Mapping &M)
Definition: ASTDiff.cpp:916
NodeId getMapped(const std::unique_ptr< SyntaxTree::Impl > &Tree, NodeId Id) const
Definition: ASTDiff.cpp:72
SyntaxTree::Impl & T2
Definition: ASTDiff.cpp:60
Impl(SyntaxTree::Impl &T1, SyntaxTree::Impl &T2, const ComparisonOptions &Options)
Definition: ASTDiff.cpp:902
void computeMapping()
Matches nodes one-by-one based on their similarity.
Definition: ASTDiff.cpp:909
SyntaxTree::Impl & T1
Definition: ASTDiff.cpp:60
ASTDiff(SyntaxTree &Src, SyntaxTree &Dst, const ComparisonOptions &Options)
Definition: ASTDiff.cpp:959
NodeId getMapped(const SyntaxTree &SourceTree, NodeId Id) const
Definition: ASTDiff.cpp:965
const Node & getNode(SNodeId Id) const
Definition: ASTDiff.cpp:507
SNodeId getLeftMostDescendant(SNodeId Id) const
Definition: ASTDiff.cpp:510
Subtree(const SyntaxTree::Impl &Tree, NodeId SubtreeRoot)
Definition: ASTDiff.cpp:497
std::vector< SNodeId > KeyRoots
Definition: ASTDiff.cpp:495
NodeId getPostorderOffset() const
Returns the postorder index of the leftmost descendant in the subtree.
Definition: ASTDiff.cpp:515
NodeId getIdInRoot(SNodeId Id) const
Definition: ASTDiff.cpp:503
std::string getNodeValue(SNodeId Id) const
Definition: ASTDiff.cpp:518
int getSize() const
Definition: ASTDiff.cpp:502
Represents the AST of a TranslationUnit.
Definition: ASTDiff.cpp:113
std::string getRelativeName(const NamedDecl *ND, const DeclContext *Context) const
Definition: ASTDiff.cpp:358
int getNumberOfDescendants(NodeId Id) const
Definition: ASTDiff.cpp:330
bool isValidNodeId(NodeId Id) const
Definition: ASTDiff.cpp:145
std::vector< NodeId > Leaves
Definition: ASTDiff.cpp:133
bool isInSubtree(NodeId Id, NodeId SubtreeRoot) const
Definition: ASTDiff.cpp:334
PreorderIterator begin() const
Definition: ASTDiff.cpp:140
std::vector< Node > Nodes
Nodes in preorder.
Definition: ASTDiff.cpp:132
PreorderIterator end() const
Definition: ASTDiff.cpp:141
int findPositionInParent(NodeId Id, bool Shifted=false) const
Definition: ASTDiff.cpp:338
const Node & getNode(NodeId Id) const
Definition: ASTDiff.cpp:143
std::string getStmtValue(const Stmt *S) const
Definition: ASTDiff.cpp:446
std::vector< int > PostorderIds
Definition: ASTDiff.cpp:135
std::string getNodeValue(NodeId Id) const
Definition: ASTDiff.cpp:408
Impl(SyntaxTree *Parent, std::enable_if_t< std::is_base_of_v< Decl, T >, T > *Node, ASTContext &AST)
Definition: ASTDiff.cpp:124
Impl(SyntaxTree *Parent, std::enable_if_t< std::is_base_of_v< Stmt, T >, T > *Node, ASTContext &AST)
Definition: ASTDiff.cpp:120
std::string getDeclValue(const Decl *D) const
Definition: ASTDiff.cpp:423
std::vector< NodeId > NodesBfs
Definition: ASTDiff.cpp:136
Impl(SyntaxTree *Parent, ASTContext &AST)
Definition: ASTDiff.cpp:261
Node & getMutableNode(NodeId Id)
Definition: ASTDiff.cpp:144
SyntaxTree objects represent subtrees of the AST.
Definition: ASTDiff.h:54
const Node & getNode(NodeId Id) const
Definition: ASTDiff.cpp:977
NodeId getRootId() const
Definition: ASTDiff.cpp:982
int findPositionInParent(NodeId Id) const
Definition: ASTDiff.cpp:988
const ASTContext & getASTContext() const
Definition: ASTDiff.cpp:975
PreorderIterator begin() const
Definition: ASTDiff.cpp:983
std::pair< unsigned, unsigned > getSourceRangeOffsets(const Node &N) const
Definition: ASTDiff.cpp:993
SyntaxTree(ASTContext &AST)
Constructs a tree from a translation unit.
Definition: ASTDiff.cpp:969
std::unique_ptr< Impl > TreeImpl
Definition: ASTDiff.h:87
PreorderIterator end() const
Definition: ASTDiff.cpp:986
std::string getNodeValue(NodeId Id) const
Serialize the node attributes to a string representation.
Definition: ASTDiff.cpp:1008
Implementation of Zhang and Shasha's Algorithm for tree edit distance.
Definition: ASTDiff.cpp:558
ZhangShashaMatcher(const ASTDiff::Impl &DiffImpl, const SyntaxTree::Impl &T1, const SyntaxTree::Impl &T2, NodeId Id1, NodeId Id2)
Definition: ASTDiff.cpp:565
std::vector< std::pair< NodeId, NodeId > > getMatchingNodes()
Definition: ASTDiff.cpp:578
static bool isSpecializedNodeExcluded(const Decl *D)
Definition: ASTDiff.cpp:165
@ UpdateMove
Definition: ASTDiff.h:34
static const DeclContext * getEnclosingDeclContext(ASTContext &AST, const Stmt *S)
Definition: ASTDiff.cpp:383
DynTypedNode DynTypedNode
static std::vector< NodeId > getSubtreePostorder(const SyntaxTree::Impl &Tree, NodeId Root)
Definition: ASTDiff.cpp:280
static std::vector< NodeId > getSubtreeBfs(const SyntaxTree::Impl &Tree, NodeId Root)
Definition: ASTDiff.cpp:293
static bool isNodeExcluded(const SourceManager &SrcMgr, T *N)
Definition: ASTDiff.cpp:172
static std::string getInitializerValue(const CXXCtorInitializer *Init, const PrintingPolicy &TypePP)
Definition: ASTDiff.cpp:397
YAML serialization mapping.
Definition: Dominators.h:30
Definition: Format.h:5078
Describes how types, statements, expressions, and declarations should be printed.
Definition: PrettyPrinter.h:57
unsigned AnonymousTagLocations
When printing an anonymous tag name, also print the location of that entity (e.g.,...
Within a tree, this identifies a node by its preorder offset.
bool isInvalid() const
Represents a Clang AST node, alongside some additional information.
Definition: ASTDiff.h:38
NodeId Parent
Definition: ASTDiff.h:39
NodeId RightMostDescendant
Definition: ASTDiff.h:39
bool isLeaf() const
Definition: ASTDiff.h:47
ChangeKind Change
Definition: ASTDiff.h:43
std::optional< std::string > getQualifiedIdentifier() const
Definition: ASTDiff.cpp:690
std::optional< StringRef > getIdentifier() const
Definition: ASTDiff.cpp:698
ASTNodeKind getType() const
Definition: ASTDiff.cpp:686
NodeId LeftMostDescendant
Definition: ASTDiff.h:39
StringRef getTypeLabel() const
Definition: ASTDiff.cpp:688
DynTypedNode ASTNode
Definition: ASTDiff.h:41
SmallVector< NodeId, 4 > Children
Definition: ASTDiff.h:42
Identifies a node in a subtree by its postorder offset, starting at 1.
Definition: ASTDiff.cpp:473
SNodeId operator+(int Other) const
Definition: ASTDiff.cpp:482
SNodeId & operator--()
Definition: ASTDiff.cpp:481
SNodeId & operator++()
Definition: ASTDiff.cpp:480