clang 22.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]; }
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(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; }
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, bool TraverseQualifier = true) { 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()) {
263 TypePP.AnonymousTagLocations = false;
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
333
334bool SyntaxTree::Impl::isInSubtree(NodeId Id, NodeId SubtreeRoot) const {
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).starts_with(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
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>())
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 const ASTContext &Ctx = T->getASTContext();
433 Value +=
435 ";";
436 }
437 if (auto *U = dyn_cast<UsingDirectiveDecl>(D))
438 return std::string(U->getNominatedNamespace()->getName());
439 if (auto *A = dyn_cast<AccessSpecDecl>(D)) {
440 CharSourceRange Range(A->getSourceRange(), false);
441 return std::string(
442 Lexer::getSourceText(Range, AST.getSourceManager(), AST.getLangOpts()));
443 }
444 return Value;
445}
446
447std::string SyntaxTree::Impl::getStmtValue(const Stmt *S) const {
448 if (auto *U = dyn_cast<UnaryOperator>(S))
449 return std::string(UnaryOperator::getOpcodeStr(U->getOpcode()));
450 if (auto *B = dyn_cast<BinaryOperator>(S))
451 return std::string(B->getOpcodeStr());
452 if (auto *M = dyn_cast<MemberExpr>(S))
453 return getRelativeName(M->getMemberDecl());
454 if (auto *I = dyn_cast<IntegerLiteral>(S)) {
456 I->getValue().toString(Str, /*Radix=*/10, /*Signed=*/false);
457 return std::string(Str);
458 }
459 if (auto *F = dyn_cast<FloatingLiteral>(S)) {
461 F->getValue().toString(Str);
462 return std::string(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 std::string(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.
474struct SNodeId {
475 int Id = 0;
476
477 explicit SNodeId(int Id) : Id(Id) {}
478 explicit SNodeId() = default;
479
480 operator int() const { return Id; }
481 SNodeId &operator++() { return ++Id, *this; }
482 SNodeId &operator--() { return --Id, *this; }
483 SNodeId operator+(int Other) const { return SNodeId(Id + Other); }
484};
485
486class Subtree {
487private:
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
495public:
496 std::vector<SNodeId> KeyRoots;
497
498 Subtree(const SyntaxTree::Impl &Tree, NodeId SubtreeRoot) : Tree(Tree) {
499 RootIds = getSubtreePostorder(Tree, SubtreeRoot);
500 int NumLeaves = setLeftMostDescendants();
501 computeKeyRoots(NumLeaves);
502 }
503 int getSize() const { return RootIds.size(); }
505 assert(Id > 0 && Id <= getSize() && "Invalid subtree node index.");
506 return RootIds[Id - 1];
507 }
508 const Node &getNode(SNodeId Id) const {
509 return Tree.getNode(getIdInRoot(Id));
510 }
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.
517 return Tree.PostorderIds[getIdInRoot(SNodeId(1))];
518 }
519 std::string getNodeValue(SNodeId Id) const {
520 return Tree.getNodeValue(getIdInRoot(Id));
521 }
522
523private:
524 /// Returns the number of leafs in the subtree.
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 }
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).
560 const ASTDiff::Impl &DiffImpl;
561 Subtree S1;
562 Subtree S2;
563 std::unique_ptr<std::unique_ptr<double[]>[]> TreeDist, ForestDist;
564
565public:
567 const SyntaxTree::Impl &T2, NodeId Id1, NodeId Id2)
568 : DiffImpl(DiffImpl), S1(T1, Id1), S2(T2, Id2) {
569 TreeDist = std::make_unique<std::unique_ptr<double[]>[]>(
570 size_t(S1.getSize()) + 1);
571 ForestDist = std::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] = std::make_unique<double[]>(size_t(S2.getSize()) + 1);
575 ForestDist[I] = std::make_unique<double[]>(size_t(S2.getSize()) + 1);
576 }
577 }
578
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
636private:
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
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
651 void computeTreeDist() {
652 for (SNodeId Id1 : S1.KeyRoots)
653 for (SNodeId Id2 : S2.KeyRoots)
654 computeForestDist(Id1, Id2);
655 }
656
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
687ASTNodeKind Node::getType() const { return ASTNode.getNodeKind(); }
688
689StringRef Node::getTypeLabel() const { return getType().asStringRef(); }
690
691std::optional<std::string> Node::getQualifiedIdentifier() const {
692 if (auto *ND = ASTNode.get<NamedDecl>()) {
693 if (ND->getDeclName().isIdentifier())
694 return ND->getQualifiedNameAsString();
695 }
696 return std::nullopt;
697}
698
699std::optional<StringRef> Node::getIdentifier() const {
700 if (auto *ND = ASTNode.get<NamedDecl>()) {
701 if (ND->getDeclName().isIdentifier())
702 return ND->getName();
703 }
704 return std::nullopt;
705}
706
707namespace {
708// Compares nodes by their depth.
709struct HeightLess {
710 const SyntaxTree::Impl &Tree;
711 HeightLess(const SyntaxTree::Impl &Tree) : Tree(Tree) {}
712 bool operator()(NodeId Id1, NodeId Id2) const {
713 return Tree.getNode(Id1).Height < Tree.getNode(Id2).Height;
714 }
715};
716} // end anonymous namespace
717
718namespace {
719// Priority queue for nodes, sorted descendingly by their height.
720class PriorityList {
721 const SyntaxTree::Impl &Tree;
722 HeightLess Cmp;
723 std::vector<NodeId> Container;
724 PriorityQueue<NodeId, std::vector<NodeId>, HeightLess> List;
725
726public:
727 PriorityList(const SyntaxTree::Impl &Tree)
728 : Tree(Tree), Cmp(Tree), List(Cmp, Container) {}
729
730 void push(NodeId id) { List.push(id); }
731
732 std::vector<NodeId> pop() {
733 int Max = peekMax();
734 std::vector<NodeId> Result;
735 if (Max == 0)
736 return Result;
737 while (peekMax() == Max) {
738 Result.push_back(List.top());
739 List.pop();
740 }
741 // TODO this is here to get a stable output, not a good heuristic
742 llvm::sort(Result);
743 return Result;
744 }
745 int peekMax() const {
746 if (List.empty())
747 return 0;
748 return Tree.getNode(List.top()).Height;
749 }
750 void open(NodeId Id) {
751 for (NodeId Child : Tree.getNode(Id).Children)
752 push(Child);
753 }
754};
755} // end anonymous namespace
756
757bool ASTDiff::Impl::identical(NodeId Id1, NodeId Id2) const {
758 const Node &N1 = T1.getNode(Id1);
759 const Node &N2 = T2.getNode(Id2);
760 if (N1.Children.size() != N2.Children.size() ||
761 !isMatchingPossible(Id1, Id2) ||
762 T1.getNodeValue(Id1) != T2.getNodeValue(Id2))
763 return false;
764 for (size_t Id = 0, E = N1.Children.size(); Id < E; ++Id)
765 if (!identical(N1.Children[Id], N2.Children[Id]))
766 return false;
767 return true;
768}
769
770bool ASTDiff::Impl::isMatchingPossible(NodeId Id1, NodeId Id2) const {
771 return Options.isMatchingAllowed(T1.getNode(Id1), T2.getNode(Id2));
772}
773
774bool ASTDiff::Impl::haveSameParents(const Mapping &M, NodeId Id1,
775 NodeId Id2) const {
776 NodeId P1 = T1.getNode(Id1).Parent;
777 NodeId P2 = T2.getNode(Id2).Parent;
778 return (P1.isInvalid() && P2.isInvalid()) ||
779 (P1.isValid() && P2.isValid() && M.getDst(P1) == P2);
780}
781
782void ASTDiff::Impl::addOptimalMapping(Mapping &M, NodeId Id1,
783 NodeId Id2) const {
784 if (std::max(T1.getNumberOfDescendants(Id1), T2.getNumberOfDescendants(Id2)) >
785 Options.MaxSize)
786 return;
787 ZhangShashaMatcher Matcher(*this, T1, T2, Id1, Id2);
788 std::vector<std::pair<NodeId, NodeId>> R = Matcher.getMatchingNodes();
789 for (const auto &Tuple : R) {
790 NodeId Src = Tuple.first;
791 NodeId Dst = Tuple.second;
792 if (!M.hasSrc(Src) && !M.hasDst(Dst))
793 M.link(Src, Dst);
794 }
795}
796
797double ASTDiff::Impl::getJaccardSimilarity(const Mapping &M, NodeId Id1,
798 NodeId Id2) const {
799 int CommonDescendants = 0;
800 const Node &N1 = T1.getNode(Id1);
801 // Count the common descendants, excluding the subtree root.
802 for (NodeId Src = Id1 + 1; Src <= N1.RightMostDescendant; ++Src) {
803 NodeId Dst = M.getDst(Src);
804 CommonDescendants += int(Dst.isValid() && T2.isInSubtree(Dst, Id2));
805 }
806 // We need to subtract 1 to get the number of descendants excluding the root.
807 double Denominator = T1.getNumberOfDescendants(Id1) - 1 +
808 T2.getNumberOfDescendants(Id2) - 1 - CommonDescendants;
809 // CommonDescendants is less than the size of one subtree.
810 assert(Denominator >= 0 && "Expected non-negative denominator.");
811 if (Denominator == 0)
812 return 0;
813 return CommonDescendants / Denominator;
814}
815
816NodeId ASTDiff::Impl::findCandidate(const Mapping &M, NodeId Id1) const {
817 NodeId Candidate;
818 double HighestSimilarity = 0.0;
819 for (NodeId Id2 : T2) {
820 if (!isMatchingPossible(Id1, Id2))
821 continue;
822 if (M.hasDst(Id2))
823 continue;
824 double Similarity = getJaccardSimilarity(M, Id1, Id2);
825 if (Similarity >= Options.MinSimilarity && Similarity > HighestSimilarity) {
826 HighestSimilarity = Similarity;
827 Candidate = Id2;
828 }
829 }
830 return Candidate;
831}
832
833void ASTDiff::Impl::matchBottomUp(Mapping &M) const {
834 std::vector<NodeId> Postorder = getSubtreePostorder(T1, T1.getRootId());
835 for (NodeId Id1 : Postorder) {
836 if (Id1 == T1.getRootId() && !M.hasSrc(T1.getRootId()) &&
837 !M.hasDst(T2.getRootId())) {
838 if (isMatchingPossible(T1.getRootId(), T2.getRootId())) {
839 M.link(T1.getRootId(), T2.getRootId());
840 addOptimalMapping(M, T1.getRootId(), T2.getRootId());
841 }
842 break;
843 }
844 bool Matched = M.hasSrc(Id1);
845 const Node &N1 = T1.getNode(Id1);
846 bool MatchedChildren = llvm::any_of(
847 N1.Children, [&](NodeId Child) { return M.hasSrc(Child); });
848 if (Matched || !MatchedChildren)
849 continue;
850 NodeId Id2 = findCandidate(M, Id1);
851 if (Id2.isValid()) {
852 M.link(Id1, Id2);
853 addOptimalMapping(M, Id1, Id2);
854 }
855 }
856}
857
858Mapping ASTDiff::Impl::matchTopDown() const {
859 PriorityList L1(T1);
860 PriorityList L2(T2);
861
862 Mapping M(T1.getSize() + T2.getSize());
863
864 L1.push(T1.getRootId());
865 L2.push(T2.getRootId());
866
867 int Max1, Max2;
868 while (std::min(Max1 = L1.peekMax(), Max2 = L2.peekMax()) >
869 Options.MinHeight) {
870 if (Max1 > Max2) {
871 for (NodeId Id : L1.pop())
872 L1.open(Id);
873 continue;
874 }
875 if (Max2 > Max1) {
876 for (NodeId Id : L2.pop())
877 L2.open(Id);
878 continue;
879 }
880 std::vector<NodeId> H1, H2;
881 H1 = L1.pop();
882 H2 = L2.pop();
883 for (NodeId Id1 : H1) {
884 for (NodeId Id2 : H2) {
885 if (identical(Id1, Id2) && !M.hasSrc(Id1) && !M.hasDst(Id2)) {
886 for (int I = 0, E = T1.getNumberOfDescendants(Id1); I < E; ++I)
887 M.link(Id1 + I, Id2 + I);
888 }
889 }
890 }
891 for (NodeId Id1 : H1) {
892 if (!M.hasSrc(Id1))
893 L1.open(Id1);
894 }
895 for (NodeId Id2 : H2) {
896 if (!M.hasDst(Id2))
897 L2.open(Id2);
898 }
899 }
900 return M;
901}
902
904 const ComparisonOptions &Options)
905 : T1(T1), T2(T2), Options(Options) {
908}
909
911 TheMapping = matchTopDown();
912 if (Options.StopAfterTopDown)
913 return;
914 matchBottomUp(TheMapping);
915}
916
918 for (NodeId Id1 : T1) {
919 if (!M.hasSrc(Id1)) {
920 T1.getMutableNode(Id1).Change = Delete;
921 T1.getMutableNode(Id1).Shift -= 1;
922 }
923 }
924 for (NodeId Id2 : T2) {
925 if (!M.hasDst(Id2)) {
926 T2.getMutableNode(Id2).Change = Insert;
927 T2.getMutableNode(Id2).Shift -= 1;
928 }
929 }
930 for (NodeId Id1 : T1.NodesBfs) {
931 NodeId Id2 = M.getDst(Id1);
932 if (Id2.isInvalid())
933 continue;
934 if (!haveSameParents(M, Id1, Id2) ||
935 T1.findPositionInParent(Id1, true) !=
936 T2.findPositionInParent(Id2, true)) {
937 T1.getMutableNode(Id1).Shift -= 1;
938 T2.getMutableNode(Id2).Shift -= 1;
939 }
940 }
941 for (NodeId Id2 : T2.NodesBfs) {
942 NodeId Id1 = M.getSrc(Id2);
943 if (Id1.isInvalid())
944 continue;
945 Node &N1 = T1.getMutableNode(Id1);
946 Node &N2 = T2.getMutableNode(Id2);
947 if (Id1.isInvalid())
948 continue;
949 if (!haveSameParents(M, Id1, Id2) ||
950 T1.findPositionInParent(Id1, true) !=
951 T2.findPositionInParent(Id2, true)) {
952 N1.Change = N2.Change = Move;
953 }
954 if (T1.getNodeValue(Id1) != T2.getNodeValue(Id2)) {
955 N1.Change = N2.Change = (N1.Change == Move ? UpdateMove : Update);
956 }
957 }
958}
959
961 const ComparisonOptions &Options)
962 : DiffImpl(std::make_unique<Impl>(*T1.TreeImpl, *T2.TreeImpl, Options)) {}
963
964ASTDiff::~ASTDiff() = default;
965
966NodeId ASTDiff::getMapped(const SyntaxTree &SourceTree, NodeId Id) const {
967 return DiffImpl->getMapped(SourceTree.TreeImpl, Id);
968}
969
971 : TreeImpl(std::make_unique<SyntaxTree::Impl>(
972 this, AST.getTranslationUnitDecl(), AST)) {}
973
974SyntaxTree::~SyntaxTree() = default;
975
976const ASTContext &SyntaxTree::getASTContext() const { return TreeImpl->AST; }
977
979 return TreeImpl->getNode(Id);
980}
981
982int SyntaxTree::getSize() const { return TreeImpl->getSize(); }
983NodeId SyntaxTree::getRootId() const { return TreeImpl->getRootId(); }
985 return TreeImpl->begin();
986}
988
990 return TreeImpl->findPositionInParent(Id);
991}
992
993std::pair<unsigned, unsigned>
995 const SourceManager &SrcMgr = TreeImpl->AST.getSourceManager();
996 SourceRange Range = N.ASTNode.getSourceRange();
997 SourceLocation BeginLoc = Range.getBegin();
999 Range.getEnd(), /*Offset=*/0, SrcMgr, TreeImpl->AST.getLangOpts());
1000 if (auto *ThisExpr = N.ASTNode.get<CXXThisExpr>()) {
1001 if (ThisExpr->isImplicit())
1002 EndLoc = BeginLoc;
1003 }
1004 unsigned Begin = SrcMgr.getFileOffset(SrcMgr.getExpansionLoc(BeginLoc));
1005 unsigned End = SrcMgr.getFileOffset(SrcMgr.getExpansionLoc(EndLoc));
1006 return {Begin, End};
1007}
1008
1009std::string SyntaxTree::getNodeValue(NodeId Id) const {
1010 return TreeImpl->getNodeValue(Id);
1011}
1012
1013std::string SyntaxTree::getNodeValue(const Node &N) const {
1014 return TreeImpl->getNodeValue(N);
1015}
1016
1017} // end namespace diff
1018} // end namespace clang
#define V(N, I)
TokenType getType() const
Returns the token's type, e.g.
SmallVector< AnnotatedLine *, 1 > Children
If this token starts a block, this contains all the unwrapped lines in it.
llvm::MachO::Record Record
Definition MachO.h:31
static Expected< DynTypedNode > getNode(const ast_matchers::BoundNodes &Nodes, StringRef ID)
Defines the SourceManager interface.
__SIZE_TYPE__ size_t
The unsigned integer type of the result of the sizeof operator.
Holds long-lived AST nodes (such as types and decls) that can be referred to throughout the semantic ...
Definition ASTContext.h:188
DynTypedNodeList getParents(const NodeT &Node)
Forwards to get node parents from the ParentMapContext.
QualType getTypeDeclType(ElaboratedTypeKeyword Keyword, NestedNameSpecifier Qualifier, const TypeDecl *Decl) const
Kind identifier.
Represents a C++ base or member initializer.
Definition DeclCXX.h:2369
bool isWritten() const
Determine whether this initializer is explicitly written in the source code.
Definition DeclCXX.h:2541
Represents the this expression in C++.
Definition ExprCXX.h:1155
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:1449
Decl - This represents one declaration (or definition), e.g.
Definition DeclBase.h:86
bool isImplicit() const
isImplicit - Indicates whether the declaration was implicitly generated by the implementation.
Definition DeclBase.h:593
DeclContext * getDeclContext()
Definition DeclBase.h:448
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:1020
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:848
This represents a decl that may have a name.
Definition Decl.h:273
std::string getQualifiedNameAsString() const
Definition Decl.cpp:1680
A (possibly-)qualified type.
Definition TypeBase.h:937
static std::string getAsString(SplitQualType split, const PrintingPolicy &Policy)
Definition TypeBase.h:1332
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.
A trivial tuple used to represent a source range.
Stmt - This represents one statement.
Definition Stmt.h:85
QualType getCanonicalTypeInternal() const
Definition TypeBase.h:3119
static StringRef getOpcodeStr(Opcode Op)
getOpcodeStr - Turn an Opcode enum value into the punctuation char it corresponds to,...
Definition Expr.cpp:1402
void computeChangeKinds(Mapping &M)
Definition ASTDiff.cpp:917
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:903
friend class ZhangShashaMatcher
Definition ASTDiff.cpp:109
void computeMapping()
Matches nodes one-by-one based on their similarity.
Definition ASTDiff.cpp:910
SyntaxTree::Impl & T1
Definition ASTDiff.cpp:60
ASTDiff(SyntaxTree &Src, SyntaxTree &Dst, const ComparisonOptions &Options)
Definition ASTDiff.cpp:960
NodeId getMapped(const SyntaxTree &SourceTree, NodeId Id) const
Definition ASTDiff.cpp:966
const Node & getNode(SNodeId Id) const
Definition ASTDiff.cpp:508
SNodeId getLeftMostDescendant(SNodeId Id) const
Definition ASTDiff.cpp:511
Subtree(const SyntaxTree::Impl &Tree, NodeId SubtreeRoot)
Definition ASTDiff.cpp:498
std::vector< SNodeId > KeyRoots
Definition ASTDiff.cpp:496
NodeId getPostorderOffset() const
Returns the postorder index of the leftmost descendant in the subtree.
Definition ASTDiff.cpp:516
NodeId getIdInRoot(SNodeId Id) const
Definition ASTDiff.cpp:504
std::string getNodeValue(SNodeId Id) const
Definition ASTDiff.cpp:519
int getSize() const
Definition ASTDiff.cpp:503
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:447
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:978
NodeId getRootId() const
Definition ASTDiff.cpp:983
int findPositionInParent(NodeId Id) const
Definition ASTDiff.cpp:989
const ASTContext & getASTContext() const
Definition ASTDiff.cpp:976
PreorderIterator begin() const
Definition ASTDiff.cpp:984
std::pair< unsigned, unsigned > getSourceRangeOffsets(const Node &N) const
Definition ASTDiff.cpp:994
SyntaxTree(ASTContext &AST)
Constructs a tree from a translation unit.
Definition ASTDiff.cpp:970
std::unique_ptr< Impl > TreeImpl
Definition ASTDiff.h:87
PreorderIterator end() const
Definition ASTDiff.cpp:987
std::string getNodeValue(NodeId Id) const
Serialize the node attributes to a string representation.
Definition ASTDiff.cpp:1009
ZhangShashaMatcher(const ASTDiff::Impl &DiffImpl, const SyntaxTree::Impl &T1, const SyntaxTree::Impl &T2, NodeId Id1, NodeId Id2)
Definition ASTDiff.cpp:566
std::vector< std::pair< NodeId, NodeId > > getMatchingNodes()
Definition ASTDiff.cpp:579
Public enums and private classes that are part of the SourceManager implementation.
static bool isSpecializedNodeExcluded(const Decl *D)
Definition ASTDiff.cpp:165
static const DeclContext * getEnclosingDeclContext(ASTContext &AST, const Stmt *S)
Definition ASTDiff.cpp:383
static std::vector< NodeId > getSubtreePostorder(const SyntaxTree::Impl &Tree, NodeId Root)
Definition ASTDiff.cpp:280
DynTypedNode DynTypedNode
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
The JSON file list parser is used to communicate input to InstallAPI.
@ Result
The result type of a method or function.
Definition TypeBase.h:905
const FunctionProtoType * T
@ Other
Other implicit parameter.
Definition Decl.h:1745
bool link(llvm::ArrayRef< const char * > args, llvm::raw_ostream &stdoutOS, llvm::raw_ostream &stderrOS, bool exitEarly, bool disableOutput)
Diagnostic wrappers for TextAPI types for error reporting.
Definition Dominators.h:30
int const char * function
Definition c++config.h:31
Describes how types, statements, expressions, and declarations should be printed.
Within a tree, this identifies a node by its preorder offset.
Represents a Clang AST node, alongside some additional information.
Definition ASTDiff.h:38
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:691
std::optional< StringRef > getIdentifier() const
Definition ASTDiff.cpp:699
ASTNodeKind getType() const
Definition ASTDiff.cpp:687
NodeId LeftMostDescendant
Definition ASTDiff.h:39
StringRef getTypeLabel() const
Definition ASTDiff.cpp:689
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:474
SNodeId operator+(int Other) const
Definition ASTDiff.cpp:483
SNodeId & operator--()
Definition ASTDiff.cpp:482
SNodeId & operator++()
Definition ASTDiff.cpp:481