clang  10.0.0svn
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 
14 
16 #include "clang/Lex/Lexer.h"
17 #include "llvm/ADT/PriorityQueue.h"
18 
19 #include <limits>
20 #include <memory>
21 #include <unordered_set>
22 
23 using namespace llvm;
24 using namespace clang;
25 
26 namespace clang {
27 namespace diff {
28 
29 namespace {
30 /// Maps nodes of the left tree to ones on the right, and vice versa.
31 class Mapping {
32 public:
33  Mapping() = default;
34  Mapping(Mapping &&Other) = default;
35  Mapping &operator=(Mapping &&Other) = default;
36 
37  Mapping(size_t Size) {
38  SrcToDst = std::make_unique<NodeId[]>(Size);
39  DstToSrc = std::make_unique<NodeId[]>(Size);
40  }
41 
42  void link(NodeId Src, NodeId Dst) {
43  SrcToDst[Src] = Dst, DstToSrc[Dst] = Src;
44  }
45 
46  NodeId getDst(NodeId Src) const { return SrcToDst[Src]; }
47  NodeId getSrc(NodeId Dst) const { return DstToSrc[Dst]; }
48  bool hasSrc(NodeId Src) const { return getDst(Src).isValid(); }
49  bool hasDst(NodeId Dst) const { return getSrc(Dst).isValid(); }
50 
51 private:
52  std::unique_ptr<NodeId[]> SrcToDst, DstToSrc;
53 };
54 } // end anonymous namespace
55 
57 public:
59  Mapping TheMapping;
60 
62  const ComparisonOptions &Options);
63 
64  /// Matches nodes one-by-one based on their similarity.
65  void computeMapping();
66 
67  // Compute Change for each node based on similarity.
68  void computeChangeKinds(Mapping &M);
69 
70  NodeId getMapped(const std::unique_ptr<SyntaxTree::Impl> &Tree,
71  NodeId Id) const {
72  if (&*Tree == &T1)
73  return TheMapping.getDst(Id);
74  assert(&*Tree == &T2 && "Invalid tree.");
75  return TheMapping.getSrc(Id);
76  }
77 
78 private:
79  // Returns true if the two subtrees are identical.
80  bool identical(NodeId Id1, NodeId Id2) const;
81 
82  // Returns false if the nodes must not be mached.
83  bool isMatchingPossible(NodeId Id1, NodeId Id2) const;
84 
85  // Returns true if the nodes' parents are matched.
86  bool haveSameParents(const Mapping &M, NodeId Id1, NodeId Id2) const;
87 
88  // Uses an optimal albeit slow algorithm to compute a mapping between two
89  // subtrees, but only if both have fewer nodes than MaxSize.
90  void addOptimalMapping(Mapping &M, NodeId Id1, NodeId Id2) const;
91 
92  // Computes the ratio of common descendants between the two nodes.
93  // Descendants are only considered to be equal when they are mapped in M.
94  double getJaccardSimilarity(const Mapping &M, NodeId Id1, NodeId Id2) const;
95 
96  // Returns the node that has the highest degree of similarity.
97  NodeId findCandidate(const Mapping &M, NodeId Id1) const;
98 
99  // Returns a mapping of identical subtrees.
100  Mapping matchTopDown() const;
101 
102  // Tries to match any yet unmapped nodes, in a bottom-up fashion.
103  void matchBottomUp(Mapping &M) const;
104 
105  const ComparisonOptions &Options;
106 
107  friend class ZhangShashaMatcher;
108 };
109 
110 /// Represents the AST of a TranslationUnit.
112 public:
114  /// Constructs a tree from an AST node.
115  Impl(SyntaxTree *Parent, Decl *N, ASTContext &AST);
116  Impl(SyntaxTree *Parent, Stmt *N, ASTContext &AST);
117  template <class T>
118  Impl(SyntaxTree *Parent,
119  typename std::enable_if<std::is_base_of<Stmt, T>::value, T>::type *Node,
120  ASTContext &AST)
121  : Impl(Parent, dyn_cast<Stmt>(Node), AST) {}
122  template <class T>
123  Impl(SyntaxTree *Parent,
124  typename std::enable_if<std::is_base_of<Decl, T>::value, T>::type *Node,
125  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 
160 private:
161  void initTree();
162  void setLeftMostDescendants();
163 };
164 
165 static bool isSpecializedNodeExcluded(const Decl *D) { return D->isImplicit(); }
166 static bool isSpecializedNodeExcluded(const Stmt *S) { return false; }
168  return !I->isWritten();
169 }
170 
171 template <class T>
172 static 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  }
184  return isSpecializedNodeExcluded(N);
185 }
186 
187 namespace {
188 // Sets Height, Parent and Children for each node.
189 struct 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 
261 SyntaxTree::Impl::Impl(SyntaxTree *Parent, ASTContext &AST)
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 
280 static 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 
293 static 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 
304 void 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 
318 void 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;
326  }
327  }
328 }
329 
331  return getNode(Id).RightMostDescendant - Id + 1;
332 }
333 
334 bool SyntaxTree::Impl::isInSubtree(NodeId Id, NodeId SubtreeRoot) const {
335  return Id >= SubtreeRoot && Id <= getNode(SubtreeRoot).RightMostDescendant;
336 }
337 
339  NodeId Parent = getNode(Id).Parent;
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.
357 std::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 
379 std::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 
397 static std::string getInitializerValue(const CXXCtorInitializer *Init,
398  const PrintingPolicy &TypePP) {
399  if (Init->isAnyMemberInitializer())
400  return 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 
412 std::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 
423 std::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 U->getNominatedNamespace()->getName();
438  if (auto *A = dyn_cast<AccessSpecDecl>(D)) {
439  CharSourceRange Range(A->getSourceRange(), false);
440  return Lexer::getSourceText(Range, AST.getSourceManager(),
441  AST.getLangOpts());
442  }
443  return Value;
444 }
445 
446 std::string SyntaxTree::Impl::getStmtValue(const Stmt *S) const {
447  if (auto *U = dyn_cast<UnaryOperator>(S))
448  return UnaryOperator::getOpcodeStr(U->getOpcode());
449  if (auto *B = dyn_cast<BinaryOperator>(S))
450  return B->getOpcodeStr();
451  if (auto *M = dyn_cast<MemberExpr>(S))
452  return getRelativeName(M->getMemberDecl());
453  if (auto *I = dyn_cast<IntegerLiteral>(S)) {
454  SmallString<256> Str;
455  I->getValue().toString(Str, /*Radix=*/10, /*Signed=*/false);
456  return Str.str();
457  }
458  if (auto *F = dyn_cast<FloatingLiteral>(S)) {
459  SmallString<256> Str;
460  F->getValue().toString(Str);
461  return 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 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.
473 struct 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 
485 class Subtree {
486 private:
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 
494 public:
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 
522 private:
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 
564 public:
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 
635 private:
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)))
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 
687  return ASTNode.getNodeKind();
688 }
689 
690 StringRef Node::getTypeLabel() const { return getType().asStringRef(); }
691 
693  if (auto *ND = ASTNode.get<NamedDecl>()) {
694  if (ND->getDeclName().isIdentifier())
695  return ND->getQualifiedNameAsString();
696  }
697  return llvm::None;
698 }
699 
701  if (auto *ND = ASTNode.get<NamedDecl>()) {
702  if (ND->getDeclName().isIdentifier())
703  return ND->getName();
704  }
705  return llvm::None;
706 }
707 
708 namespace {
709 // Compares nodes by their depth.
710 struct HeightLess {
711  const SyntaxTree::Impl &Tree;
712  HeightLess(const SyntaxTree::Impl &Tree) : Tree(Tree) {}
713  bool operator()(NodeId Id1, NodeId Id2) const {
714  return Tree.getNode(Id1).Height < Tree.getNode(Id2).Height;
715  }
716 };
717 } // end anonymous namespace
718 
719 namespace {
720 // Priority queue for nodes, sorted descendingly by their height.
721 class PriorityList {
722  const SyntaxTree::Impl &Tree;
723  HeightLess Cmp;
724  std::vector<NodeId> Container;
725  PriorityQueue<NodeId, std::vector<NodeId>, HeightLess> List;
726 
727 public:
728  PriorityList(const SyntaxTree::Impl &Tree)
729  : Tree(Tree), Cmp(Tree), List(Cmp, Container) {}
730 
731  void push(NodeId id) { List.push(id); }
732 
733  std::vector<NodeId> pop() {
734  int Max = peekMax();
735  std::vector<NodeId> Result;
736  if (Max == 0)
737  return Result;
738  while (peekMax() == Max) {
739  Result.push_back(List.top());
740  List.pop();
741  }
742  // TODO this is here to get a stable output, not a good heuristic
743  llvm::sort(Result);
744  return Result;
745  }
746  int peekMax() const {
747  if (List.empty())
748  return 0;
749  return Tree.getNode(List.top()).Height;
750  }
751  void open(NodeId Id) {
752  for (NodeId Child : Tree.getNode(Id).Children)
753  push(Child);
754  }
755 };
756 } // end anonymous namespace
757 
758 bool ASTDiff::Impl::identical(NodeId Id1, NodeId Id2) const {
759  const Node &N1 = T1.getNode(Id1);
760  const Node &N2 = T2.getNode(Id2);
761  if (N1.Children.size() != N2.Children.size() ||
762  !isMatchingPossible(Id1, Id2) ||
763  T1.getNodeValue(Id1) != T2.getNodeValue(Id2))
764  return false;
765  for (size_t Id = 0, E = N1.Children.size(); Id < E; ++Id)
766  if (!identical(N1.Children[Id], N2.Children[Id]))
767  return false;
768  return true;
769 }
770 
771 bool ASTDiff::Impl::isMatchingPossible(NodeId Id1, NodeId Id2) const {
772  return Options.isMatchingAllowed(T1.getNode(Id1), T2.getNode(Id2));
773 }
774 
775 bool ASTDiff::Impl::haveSameParents(const Mapping &M, NodeId Id1,
776  NodeId Id2) const {
777  NodeId P1 = T1.getNode(Id1).Parent;
778  NodeId P2 = T2.getNode(Id2).Parent;
779  return (P1.isInvalid() && P2.isInvalid()) ||
780  (P1.isValid() && P2.isValid() && M.getDst(P1) == P2);
781 }
782 
783 void ASTDiff::Impl::addOptimalMapping(Mapping &M, NodeId Id1,
784  NodeId Id2) const {
785  if (std::max(T1.getNumberOfDescendants(Id1), T2.getNumberOfDescendants(Id2)) >
786  Options.MaxSize)
787  return;
788  ZhangShashaMatcher Matcher(*this, T1, T2, Id1, Id2);
789  std::vector<std::pair<NodeId, NodeId>> R = Matcher.getMatchingNodes();
790  for (const auto Tuple : R) {
791  NodeId Src = Tuple.first;
792  NodeId Dst = Tuple.second;
793  if (!M.hasSrc(Src) && !M.hasDst(Dst))
794  M.link(Src, Dst);
795  }
796 }
797 
798 double ASTDiff::Impl::getJaccardSimilarity(const Mapping &M, NodeId Id1,
799  NodeId Id2) const {
800  int CommonDescendants = 0;
801  const Node &N1 = T1.getNode(Id1);
802  // Count the common descendants, excluding the subtree root.
803  for (NodeId Src = Id1 + 1; Src <= N1.RightMostDescendant; ++Src) {
804  NodeId Dst = M.getDst(Src);
805  CommonDescendants += int(Dst.isValid() && T2.isInSubtree(Dst, Id2));
806  }
807  // We need to subtract 1 to get the number of descendants excluding the root.
808  double Denominator = T1.getNumberOfDescendants(Id1) - 1 +
809  T2.getNumberOfDescendants(Id2) - 1 - CommonDescendants;
810  // CommonDescendants is less than the size of one subtree.
811  assert(Denominator >= 0 && "Expected non-negative denominator.");
812  if (Denominator == 0)
813  return 0;
814  return CommonDescendants / Denominator;
815 }
816 
817 NodeId ASTDiff::Impl::findCandidate(const Mapping &M, NodeId Id1) const {
818  NodeId Candidate;
819  double HighestSimilarity = 0.0;
820  for (NodeId Id2 : T2) {
821  if (!isMatchingPossible(Id1, Id2))
822  continue;
823  if (M.hasDst(Id2))
824  continue;
825  double Similarity = getJaccardSimilarity(M, Id1, Id2);
826  if (Similarity >= Options.MinSimilarity && Similarity > HighestSimilarity) {
827  HighestSimilarity = Similarity;
828  Candidate = Id2;
829  }
830  }
831  return Candidate;
832 }
833 
834 void ASTDiff::Impl::matchBottomUp(Mapping &M) const {
835  std::vector<NodeId> Postorder = getSubtreePostorder(T1, T1.getRootId());
836  for (NodeId Id1 : Postorder) {
837  if (Id1 == T1.getRootId() && !M.hasSrc(T1.getRootId()) &&
838  !M.hasDst(T2.getRootId())) {
839  if (isMatchingPossible(T1.getRootId(), T2.getRootId())) {
840  M.link(T1.getRootId(), T2.getRootId());
841  addOptimalMapping(M, T1.getRootId(), T2.getRootId());
842  }
843  break;
844  }
845  bool Matched = M.hasSrc(Id1);
846  const Node &N1 = T1.getNode(Id1);
847  bool MatchedChildren = llvm::any_of(
848  N1.Children, [&](NodeId Child) { return M.hasSrc(Child); });
849  if (Matched || !MatchedChildren)
850  continue;
851  NodeId Id2 = findCandidate(M, Id1);
852  if (Id2.isValid()) {
853  M.link(Id1, Id2);
854  addOptimalMapping(M, Id1, Id2);
855  }
856  }
857 }
858 
859 Mapping ASTDiff::Impl::matchTopDown() const {
860  PriorityList L1(T1);
861  PriorityList L2(T2);
862 
863  Mapping M(T1.getSize() + T2.getSize());
864 
865  L1.push(T1.getRootId());
866  L2.push(T2.getRootId());
867 
868  int Max1, Max2;
869  while (std::min(Max1 = L1.peekMax(), Max2 = L2.peekMax()) >
870  Options.MinHeight) {
871  if (Max1 > Max2) {
872  for (NodeId Id : L1.pop())
873  L1.open(Id);
874  continue;
875  }
876  if (Max2 > Max1) {
877  for (NodeId Id : L2.pop())
878  L2.open(Id);
879  continue;
880  }
881  std::vector<NodeId> H1, H2;
882  H1 = L1.pop();
883  H2 = L2.pop();
884  for (NodeId Id1 : H1) {
885  for (NodeId Id2 : H2) {
886  if (identical(Id1, Id2) && !M.hasSrc(Id1) && !M.hasDst(Id2)) {
887  for (int I = 0, E = T1.getNumberOfDescendants(Id1); I < E; ++I)
888  M.link(Id1 + I, Id2 + I);
889  }
890  }
891  }
892  for (NodeId Id1 : H1) {
893  if (!M.hasSrc(Id1))
894  L1.open(Id1);
895  }
896  for (NodeId Id2 : H2) {
897  if (!M.hasDst(Id2))
898  L2.open(Id2);
899  }
900  }
901  return M;
902 }
903 
905  const ComparisonOptions &Options)
906  : T1(T1), T2(T2), Options(Options) {
907  computeMapping();
909 }
910 
912  TheMapping = matchTopDown();
913  if (Options.StopAfterTopDown)
914  return;
915  matchBottomUp(TheMapping);
916 }
917 
919  for (NodeId Id1 : T1) {
920  if (!M.hasSrc(Id1)) {
921  T1.getMutableNode(Id1).Change = Delete;
922  T1.getMutableNode(Id1).Shift -= 1;
923  }
924  }
925  for (NodeId Id2 : T2) {
926  if (!M.hasDst(Id2)) {
927  T2.getMutableNode(Id2).Change = Insert;
928  T2.getMutableNode(Id2).Shift -= 1;
929  }
930  }
931  for (NodeId Id1 : T1.NodesBfs) {
932  NodeId Id2 = M.getDst(Id1);
933  if (Id2.isInvalid())
934  continue;
935  if (!haveSameParents(M, Id1, Id2) ||
936  T1.findPositionInParent(Id1, true) !=
937  T2.findPositionInParent(Id2, true)) {
938  T1.getMutableNode(Id1).Shift -= 1;
939  T2.getMutableNode(Id2).Shift -= 1;
940  }
941  }
942  for (NodeId Id2 : T2.NodesBfs) {
943  NodeId Id1 = M.getSrc(Id2);
944  if (Id1.isInvalid())
945  continue;
946  Node &N1 = T1.getMutableNode(Id1);
947  Node &N2 = T2.getMutableNode(Id2);
948  if (Id1.isInvalid())
949  continue;
950  if (!haveSameParents(M, Id1, Id2) ||
951  T1.findPositionInParent(Id1, true) !=
952  T2.findPositionInParent(Id2, true)) {
953  N1.Change = N2.Change = Move;
954  }
955  if (T1.getNodeValue(Id1) != T2.getNodeValue(Id2)) {
956  N1.Change = N2.Change = (N1.Change == Move ? UpdateMove : Update);
957  }
958  }
959 }
960 
962  const ComparisonOptions &Options)
963  : DiffImpl(std::make_unique<Impl>(*T1.TreeImpl, *T2.TreeImpl, Options)) {}
964 
965 ASTDiff::~ASTDiff() = default;
966 
967 NodeId ASTDiff::getMapped(const SyntaxTree &SourceTree, NodeId Id) const {
968  return DiffImpl->getMapped(SourceTree.TreeImpl, Id);
969 }
970 
972  : TreeImpl(std::make_unique<SyntaxTree::Impl>(
973  this, AST.getTranslationUnitDecl(), AST)) {}
974 
975 SyntaxTree::~SyntaxTree() = default;
976 
977 const ASTContext &SyntaxTree::getASTContext() const { return TreeImpl->AST; }
978 
980  return TreeImpl->getNode(Id);
981 }
982 
983 int SyntaxTree::getSize() const { return TreeImpl->getSize(); }
984 NodeId SyntaxTree::getRootId() const { return TreeImpl->getRootId(); }
986  return TreeImpl->begin();
987 }
989 
991  return TreeImpl->findPositionInParent(Id);
992 }
993 
994 std::pair<unsigned, unsigned>
996  const SourceManager &SrcMgr = TreeImpl->AST.getSourceManager();
997  SourceRange Range = N.ASTNode.getSourceRange();
998  SourceLocation BeginLoc = Range.getBegin();
1000  Range.getEnd(), /*Offset=*/0, SrcMgr, TreeImpl->AST.getLangOpts());
1001  if (auto *ThisExpr = N.ASTNode.get<CXXThisExpr>()) {
1002  if (ThisExpr->isImplicit())
1003  EndLoc = BeginLoc;
1004  }
1005  unsigned Begin = SrcMgr.getFileOffset(SrcMgr.getExpansionLoc(BeginLoc));
1006  unsigned End = SrcMgr.getFileOffset(SrcMgr.getExpansionLoc(EndLoc));
1007  return {Begin, End};
1008 }
1009 
1010 std::string SyntaxTree::getNodeValue(NodeId Id) const {
1011  return TreeImpl->getNodeValue(Id);
1012 }
1013 
1014 std::string SyntaxTree::getNodeValue(const Node &N) const {
1015  return TreeImpl->getNodeValue(N);
1016 }
1017 
1018 } // end namespace diff
1019 } // end namespace clang
bool isBaseInitializer() const
Determine whether this initializer is initializing a base class.
Definition: DeclCXX.h:2369
llvm::Optional< std::string > getQualifiedIdentifier() const
Definition: ASTDiff.cpp:692
A (possibly-)qualified type.
Definition: Type.h:643
NodeId Parent
Definition: ASTDiff.h:38
const Node & getNode(NodeId Id) const
Definition: ASTDiff.cpp:979
Specialize PointerLikeTypeTraits to allow LazyGenerationalUpdatePtr to be placed into a PointerUnion...
Definition: Dominators.h:30
Stmt - This represents one statement.
Definition: Stmt.h:66
const T * get() const
Retrieve the stored node as type T.
NodeId getMapped(const SyntaxTree &SourceTree, NodeId Id) const
Definition: ASTDiff.cpp:967
Decl - This represents one declaration (or definition), e.g.
Definition: DeclBase.h:88
bool isInSubtree(NodeId Id, NodeId SubtreeRoot) const
Definition: ASTDiff.cpp:334
ZhangShashaMatcher(const ASTDiff::Impl &DiffImpl, const SyntaxTree::Impl &T1, const SyntaxTree::Impl &T2, NodeId Id1, NodeId Id2)
Definition: ASTDiff.cpp:565
bool isWritten() const
Determine whether this initializer is explicitly written in the source code.
Definition: DeclCXX.h:2468
StringRef P
ast_type_traits::ASTNodeKind getType() const
Definition: ASTDiff.cpp:686
static std::vector< NodeId > getSubtreePostorder(const SyntaxTree::Impl &Tree, NodeId Root)
Definition: ASTDiff.cpp:280
void computeChangeKinds(Mapping &M)
Definition: ASTDiff.cpp:918
void computeMapping()
Matches nodes one-by-one based on their similarity.
Definition: ASTDiff.cpp:911
llvm::Optional< StringRef > getIdentifier() const
Definition: ASTDiff.cpp:700
const Node & getNode(SNodeId Id) const
Definition: ASTDiff.cpp:507
std::vector< NodeId > NodesBfs
Definition: ASTDiff.cpp:136
PreorderIterator end() const
Definition: ASTDiff.cpp:141
bool isValid() const
std::vector< NodeId > Leaves
Definition: ASTDiff.cpp:133
Describes how types, statements, expressions, and declarations should be printed. ...
Definition: PrettyPrinter.h:37
NodeId getMapped(const std::unique_ptr< SyntaxTree::Impl > &Tree, NodeId Id) const
Definition: ASTDiff.cpp:70
bool isValidNodeId(NodeId Id) const
Definition: ASTDiff.cpp:145
std::vector< SNodeId > KeyRoots
Definition: ASTDiff.cpp:495
SNodeId operator+(int Other) const
Definition: ASTDiff.cpp:482
Holds long-lived AST nodes (such as types and decls) that can be referred to throughout the semantic ...
Definition: ASTContext.h:160
LineState State
TypeSourceInfo * getTypeSourceInfo() const
Returns the declarator information for a base class or delegating initializer.
Definition: DeclCXX.h:2430
DynTypedNodeList getParents(const NodeT &Node)
Returns the parents of the given node (within the traversal scope).
Definition: ASTContext.h:661
Definition: Format.h:2327
std::string getNodeValue(NodeId Id) const
Definition: ASTDiff.cpp:408
SyntaxTree::Impl & T2
Definition: ASTDiff.cpp:58
std::string getNodeValue(SNodeId Id) const
Definition: ASTDiff.cpp:518
__SIZE_TYPE__ size_t
The unsigned integer type of the result of the sizeof operator.
Definition: opencl-c-base.h:40
__DEVICE__ int max(int __a, int __b)
Implementation of Zhang and Shasha&#39;s Algorithm for tree edit distance.
Definition: ASTDiff.cpp:558
Within a tree, this identifies a node by its preorder offset.
NodeId getPostorderOffset() const
Returns the postorder index of the leftmost descendant in the subtree.
Definition: ASTDiff.cpp:515
ast_type_traits::DynTypedNode ASTNode
Definition: ASTDiff.h:40
SourceLocation getExpansionLoc(SourceLocation Loc) const
Given a SourceLocation object Loc, return the expansion location referenced by the ID...
SNodeId & operator++()
Definition: ASTDiff.cpp:480
std::string getNodeValue(NodeId Id) const
Serialize the node attributes to a string representation.
Definition: ASTDiff.cpp:1010
ChangeKind Change
Definition: ASTDiff.h:42
bool isAnyMemberInitializer() const
Definition: DeclCXX.h:2377
std::unique_ptr< Impl > TreeImpl
Definition: ASTDiff.h:99
SyntaxTree::Impl & T1
Definition: ASTDiff.cpp:58
SourceLocation getSpellingLoc(SourceLocation Loc) const
Given a SourceLocation object, return the spelling location referenced by the ID. ...
FieldDecl * getAnyMember() const
Definition: DeclCXX.h:2442
int findPositionInParent(NodeId Id) const
Definition: ASTDiff.cpp:990
A class that does preorder or postorder depth-first traversal on the entire Clang AST and visits each...
std::string getStmtValue(const Stmt *S) const
Definition: ASTDiff.cpp:446
Represents the this expression in C++.
Definition: ExprCXX.h:1006
int getNumberOfDescendants(NodeId Id) const
Definition: ASTDiff.cpp:330
NodeId Parent
Definition: ASTDiff.cpp:191
Impl(SyntaxTree *Parent, ASTContext &AST)
Definition: ASTDiff.cpp:261
static std::string getInitializerValue(const CXXCtorInitializer *Init, const PrintingPolicy &TypePP)
Definition: ASTDiff.cpp:397
ASTDiff(SyntaxTree &Src, SyntaxTree &Dst, const ComparisonOptions &Options)
Definition: ASTDiff.cpp:961
bool isDelegatingInitializer() const
Determine whether this initializer is creating a delegating constructor.
Definition: DeclCXX.h:2397
Impl(SyntaxTree *Parent, typename std::enable_if< std::is_base_of< Decl, T >::value, T >::type *Node, ASTContext &AST)
Definition: ASTDiff.cpp:123
NodeId RightMostDescendant
Definition: ASTDiff.h:38
PreorderIterator end() const
Definition: ASTDiff.cpp:988
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:939
Identifies a node in a subtree by its postorder offset, starting at 1.
Definition: ASTDiff.cpp:473
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:778
SourceLocation End
Represents a character-granular source range.
llvm::StringRef getAsString(SyncScope S)
Definition: SyncScope.h:50
int Id
Definition: ASTDiff.cpp:190
#define V(N, I)
Definition: ASTContext.h:2913
bool isImplicit() const
isImplicit - Indicates whether the declaration was implicitly generated by the implementation.
Definition: DeclBase.h:558
static std::vector< NodeId > getSubtreeBfs(const SyntaxTree::Impl &Tree, NodeId Root)
Definition: ASTDiff.cpp:293
PreorderIterator begin() const
Definition: ASTDiff.cpp:140
DeclContext * getDeclContext()
Definition: DeclBase.h:438
SourceLocation Begin
const ASTContext & getASTContext() const
Definition: ASTDiff.cpp:977
int Depth
Definition: ASTDiff.cpp:190
SourceRange getSourceRange() const
For nodes which represent textual entities in the source code, return their SourceRange.
SourceLocation getEnd() const
bool isLeaf() const
Definition: ASTDiff.h:46
unsigned AnonymousTagLocations
When printing an anonymous tag name, also print the location of that entity (e.g., "enum <anonymous at t.h:10:5>").
unsigned getFileOffset(SourceLocation SpellingLoc) const
Returns the offset from the start of the file that the specified SourceLocation represents.
Encodes a location in the source.
PreorderIterator begin() const
Definition: ASTDiff.cpp:985
SyntaxTree(ASTContext &AST)
Constructs a tree from a translation unit.
Definition: ASTDiff.cpp:971
std::string getRelativeName(const NamedDecl *ND, const DeclContext *Context) const
Definition: ASTDiff.cpp:358
std::vector< int > PostorderIds
Definition: ASTDiff.cpp:135
StringRef getTypeLabel() const
Definition: ASTDiff.cpp:690
std::vector< Node > Nodes
Nodes in preorder.
Definition: ASTDiff.cpp:132
SyntaxTree objects represent subtrees of the AST.
Definition: ASTDiff.h:67
SmallVector< NodeId, 4 > Children
Definition: ASTDiff.h:41
Subtree(const SyntaxTree::Impl &Tree, NodeId SubtreeRoot)
Definition: ASTDiff.cpp:497
NodeId getIdInRoot(SNodeId Id) const
Definition: ASTDiff.cpp:503
bool isInMainFile(SourceLocation Loc) const
Returns whether the PresumedLoc for a given SourceLocation is in the main file.
int getSize() const
Definition: ASTDiff.cpp:502
ast_type_traits::DynTypedNode Node
NodeId getRootId() const
Definition: ASTDiff.cpp:984
static bool isNodeExcluded(const SourceManager &SrcMgr, T *N)
Definition: ASTDiff.cpp:172
Dataflow Directional Tag Classes.
bool isValid() const
Return true if this is a valid SourceLocation object.
std::pair< unsigned, unsigned > getSourceRangeOffsets(const Node &N) const
Definition: ASTDiff.cpp:995
DeclContext - This is used only as base class of specific decl types that can act as declaration cont...
Definition: DeclBase.h:1271
Node & getMutableNode(NodeId Id)
Definition: ASTDiff.cpp:144
int findPositionInParent(NodeId Id, bool Shifted=false) const
Definition: ASTDiff.cpp:338
std::unique_ptr< DiagnosticConsumer > create(StringRef OutputFile, DiagnosticOptions *Diags, bool MergeChildRecords=false)
Returns a DiagnosticConsumer that serializes diagnostics to a bitcode file.
static std::string getAsString(SplitQualType split, const PrintingPolicy &Policy)
Definition: Type.h:979
const Type * getBaseClass() const
If this is a base class initializer, returns the type of the base class.
Definition: DeclCXX.cpp:2370
Represents the AST of a TranslationUnit.
Definition: ASTDiff.cpp:111
NodeId LeftMostDescendant
Definition: ASTDiff.h:38
Impl(SyntaxTree::Impl &T1, SyntaxTree::Impl &T2, const ComparisonOptions &Options)
Definition: ASTDiff.cpp:904
SyntaxTree::Impl & Tree
Definition: ASTDiff.cpp:192
A dynamically typed AST node container.
SNodeId getLeftMostDescendant(SNodeId Id) const
Definition: ASTDiff.cpp:510
Represents a C++ base or member initializer.
Definition: DeclCXX.h:2300
SourceManager & getSourceManager()
Definition: ASTContext.h:675
std::string getDeclValue(const Decl *D) const
Definition: ASTDiff.cpp:423
static const DeclContext * getEnclosingDeclContext(ASTContext &AST, const Stmt *S)
Definition: ASTDiff.cpp:383
std::vector< std::pair< NodeId, NodeId > > getMatchingNodes()
Definition: ASTDiff.cpp:578
bool isInvalid() const
__DEVICE__ int min(int __a, int __b)
StringRef getName() const
Get the name of identifier for this declaration as a StringRef.
Definition: Decl.h:275
std::string getQualifiedNameAsString() const
Definition: Decl.cpp:1548
const Node & getNode(NodeId Id) const
Definition: ASTDiff.cpp:143
A trivial tuple used to represent a source range.
static StringRef getOpcodeStr(Opcode Op)
getOpcodeStr - Turn an Opcode enum value into the punctuation char it corresponds to...
Definition: Expr.cpp:1285
This represents a decl that may have a name.
Definition: Decl.h:248
Represents a Clang AST node, alongside some additional information.
Definition: ASTDiff.h:37
SourceLocation getBegin() const
const LangOptions & getLangOpts() const
Definition: ASTContext.h:720
SNodeId & operator--()
Definition: ASTDiff.cpp:481
This class handles loading and caching of source files into memory.
Impl(SyntaxTree *Parent, typename std::enable_if< std::is_base_of< Stmt, T >::value, T >::type *Node, ASTContext &AST)
Definition: ASTDiff.cpp:118
QualType getType() const
Return the type wrapped by this type source info.
Definition: Decl.h:97
static bool isSpecializedNodeExcluded(CXXCtorInitializer *I)
Definition: ASTDiff.cpp:167