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