18#include "llvm/ADT/PriorityQueue.h"
23#include <unordered_set>
36 Mapping(Mapping &&
Other) =
default;
37 Mapping &operator=(Mapping &&
Other) =
default;
39 Mapping(
size_t Size) {
40 SrcToDst = std::make_unique<NodeId[]>(Size);
41 DstToSrc = std::make_unique<NodeId[]>(Size);
44 void link(NodeId Src, NodeId Dst) {
45 SrcToDst[Src] = Dst, DstToSrc[Dst] = Src;
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(); }
54 std::unique_ptr<NodeId[]> SrcToDst, DstToSrc;
76 assert(&*Tree == &
T2 &&
"Invalid tree.");
88 bool haveSameParents(
const Mapping &M,
NodeId Id1,
NodeId Id2)
const;
92 void addOptimalMapping(Mapping &M,
NodeId Id1,
NodeId Id2)
const;
96 double getJaccardSimilarity(
const Mapping &M,
NodeId Id1,
NodeId Id2)
const;
99 NodeId findCandidate(
const Mapping &M,
NodeId Id1)
const;
102 Mapping matchTopDown()
const;
105 void matchBottomUp(Mapping &M)
const;
162 void setLeftMostDescendants();
178 if (!
SrcMgr.isInMainFile(SLoc))
181 if (SLoc !=
SrcMgr.getSpellingLoc(SLoc))
190 int Id = 0, Depth = 0;
192 SyntaxTree::Impl &Tree;
194 PreorderVisitor(SyntaxTree::Impl &Tree) : Tree(Tree) {}
196 template <
class T> std::tuple<NodeId, NodeId> PreTraverse(
T *ASTNode) {
198 Tree.Nodes.emplace_back();
199 Node &N = Tree.getMutableNode(MyId);
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);
212 return std::make_tuple(MyId, Tree.getNode(MyId).Parent);
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;
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.");
226 Tree.Leaves.push_back(MyId);
228 for (NodeId Child : N.Children)
229 N.Height = std::max(N.Height, 1 + Tree.getNode(Child).Height);
231 bool TraverseDecl(Decl *D) {
234 auto SavedState = PreTraverse(D);
236 PostTraverse(SavedState);
239 bool TraverseStmt(Stmt *S) {
240 if (
auto *E = dyn_cast_or_null<Expr>(S))
241 S = E->IgnoreImplicit();
244 auto SavedState = PreTraverse(S);
246 PostTraverse(SavedState);
249 bool TraverseType(QualType
T,
bool TraverseQualifier =
true) {
return true; }
250 bool TraverseConstructorInitializer(CXXCtorInitializer *
Init) {
253 auto SavedState = PreTraverse(
Init);
255 PostTraverse(SavedState);
263 TypePP.AnonymousTagLocations =
false;
268 PreorderVisitor PreorderWalker(*
this);
269 PreorderWalker.TraverseDecl(N);
275 PreorderVisitor PreorderWalker(*
this);
276 PreorderWalker.TraverseStmt(N);
282 std::vector<NodeId> Postorder;
287 Postorder.push_back(Id);
295 std::vector<NodeId> Ids;
298 while (Expanded < Ids.size())
300 Ids.push_back(Child);
304void SyntaxTree::Impl::initTree() {
305 setLeftMostDescendants();
307 PostorderIds.resize(
getSize());
308 std::function<void(NodeId)> PostorderTraverse = [&](NodeId Id) {
310 PostorderTraverse(Child);
311 PostorderIds[Id] = PostorderId;
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() &&
325 getMutableNode(Cur).LeftMostDescendant = Leaf;
344 for (
size_t I = 0, E = Siblings.size(); I < E; ++I) {
347 if (Siblings[I] == Id) {
352 llvm_unreachable(
"Node not found in parent's children.");
361 std::string ContextPrefix;
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();
374 if (!ContextPrefix.empty() && StringRef(Val).starts_with(ContextPrefix))
375 Val = Val.substr(ContextPrefix.size() + 1);
389 const auto &P = Parents[0];
390 if (
const auto *D = P.get<
Decl>())
399 if (
Init->isAnyMemberInitializer())
400 return std::string(
Init->getAnyMember()->getName());
401 if (
Init->isBaseInitializer())
403 if (
Init->isDelegatingInitializer())
404 return Init->getTypeSourceInfo()->getType().getAsString(TypePP);
405 llvm_unreachable(
"Unknown initializer type");
420 llvm_unreachable(
"Fatal: unhandled AST node.\n");
425 if (
auto *
V = dyn_cast<ValueDecl>(D))
427 if (
auto *N = dyn_cast<NamedDecl>(D))
429 if (
auto *
T = dyn_cast<TypedefNameDecl>(D))
430 return Value +
T->getUnderlyingType().getAsString(
TypePP) +
";";
431 if (
auto *
T = dyn_cast<TypeDecl>(D)) {
437 if (
auto *
U = dyn_cast<UsingDirectiveDecl>(D))
438 return std::string(
U->getNominatedNamespace()->getName());
439 if (
auto *A = dyn_cast<AccessSpecDecl>(D)) {
448 if (
auto *
U = dyn_cast<UnaryOperator>(S))
450 if (
auto *B = dyn_cast<BinaryOperator>(S))
451 return std::string(B->getOpcodeStr());
452 if (
auto *M = dyn_cast<MemberExpr>(S))
454 if (
auto *I = dyn_cast<IntegerLiteral>(S)) {
456 I->getValue().toString(Str, 10,
false);
457 return std::string(Str);
459 if (
auto *F = dyn_cast<FloatingLiteral>(S)) {
461 F->getValue().toString(Str);
462 return std::string(Str);
464 if (
auto *D = dyn_cast<DeclRefExpr>(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";
491 std::vector<NodeId> RootIds;
493 std::vector<SNodeId> LeftMostDescendants;
500 int NumLeaves = setLeftMostDescendants();
501 computeKeyRoots(NumLeaves);
503 int getSize()
const {
return RootIds.size(); }
505 assert(Id > 0 && Id <=
getSize() &&
"Invalid subtree node index.");
506 return RootIds[Id - 1];
512 assert(Id > 0 && Id <=
getSize() &&
"Invalid subtree node index.");
513 return LeftMostDescendants[Id - 1];
525 int setLeftMostDescendants() {
527 LeftMostDescendants.resize(getSize());
528 for (
int I = 0; I < getSize(); ++I) {
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.");
536 getPostorderOffset());
540 void computeKeyRoots(
int Leaves) {
541 KeyRoots.resize(Leaves);
542 std::unordered_set<int> Visited;
544 for (SNodeId I(getSize()); I > 0; --I) {
545 SNodeId LeftDesc = getLeftMostDescendant(I);
546 if (Visited.count(LeftDesc))
548 assert(K >= 0 &&
"K should be non-negative");
550 Visited.insert(LeftDesc);
563 std::unique_ptr<std::unique_ptr<double[]>[]> TreeDist, ForestDist;
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);
580 std::vector<std::pair<NodeId, NodeId>> Matches;
581 std::vector<std::pair<SNodeId, SNodeId>> TreePairs;
585 bool RootNodePair =
true;
587 TreePairs.emplace_back(
SNodeId(S1.getSize()),
SNodeId(S2.getSize()));
589 while (!TreePairs.empty()) {
590 SNodeId LastRow, LastCol, FirstRow, FirstCol, Row, Col;
591 std::tie(LastRow, LastCol) = TreePairs.back();
592 TreePairs.pop_back();
595 computeForestDist(LastRow, LastCol);
598 RootNodePair =
false;
600 FirstRow = S1.getLeftMostDescendant(LastRow);
601 FirstCol = S2.getLeftMostDescendant(LastCol);
606 while (Row > FirstRow || Col > FirstCol) {
607 if (Row > FirstRow &&
608 ForestDist[Row - 1][Col] + 1 == ForestDist[Row][Col]) {
610 }
else if (Col > FirstCol &&
611 ForestDist[Row][Col - 1] + 1 == ForestDist[Row][Col]) {
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);
626 TreePairs.emplace_back(Row, Col);
642 static constexpr double DeletionCost = 1;
643 static constexpr double InsertionCost = 1;
647 return std::numeric_limits<double>::max();
651 void computeTreeDist() {
654 computeForestDist(Id1, Id2);
657 void computeForestDist(SNodeId Id1, SNodeId Id2) {
658 assert(Id1 > 0 && Id2 > 0 &&
"Expecting offsets greater than 0.");
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;
669 if (DLMD1 == LMD1 && DLMD2 == LMD2) {
670 double UpdateCost = getUpdateCost(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];
678 std::min({ForestDist[D1 - 1][D2] + DeletionCost,
679 ForestDist[D1][D2 - 1] + InsertionCost,
680 ForestDist[DLMD1][DLMD2] + TreeDist[D1][D2]});
693 if (ND->getDeclName().isIdentifier())
694 return ND->getQualifiedNameAsString();
701 if (ND->getDeclName().isIdentifier())
702 return ND->getName();
712 bool operator()(NodeId Id1, NodeId Id2)
const {
721 const SyntaxTree::Impl &Tree;
723 std::vector<NodeId> Container;
724 PriorityQueue<NodeId, std::vector<NodeId>, HeightLess> List;
727 PriorityList(
const SyntaxTree::Impl &Tree)
728 : Tree(Tree), Cmp(Tree), List(Cmp, Container) {}
730 void push(NodeId
id) { List.push(
id); }
732 std::vector<NodeId> pop() {
734 std::vector<NodeId>
Result;
737 while (peekMax() ==
Max) {
738 Result.push_back(List.top());
745 int peekMax()
const {
748 return Tree.getNode(List.top()).Height;
750 void open(NodeId Id) {
751 for (NodeId Child : Tree.getNode(Id).Children)
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))
764 for (
size_t Id = 0, E = N1.Children.size(); Id < E; ++Id)
765 if (!identical(N1.Children[Id], N2.Children[Id]))
770bool ASTDiff::Impl::isMatchingPossible(NodeId Id1, NodeId Id2)
const {
771 return Options.isMatchingAllowed(T1.getNode(Id1), T2.getNode(Id2));
774bool ASTDiff::Impl::haveSameParents(
const Mapping &M, NodeId Id1,
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);
782void ASTDiff::Impl::addOptimalMapping(Mapping &M, NodeId Id1,
784 if (std::max(T1.getNumberOfDescendants(Id1), T2.getNumberOfDescendants(Id2)) >
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))
797double ASTDiff::Impl::getJaccardSimilarity(
const Mapping &M, NodeId Id1,
799 int CommonDescendants = 0;
800 const Node &N1 = T1.getNode(Id1);
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));
807 double Denominator = T1.getNumberOfDescendants(Id1) - 1 +
808 T2.getNumberOfDescendants(Id2) - 1 - CommonDescendants;
810 assert(Denominator >= 0 &&
"Expected non-negative denominator.");
811 if (Denominator == 0)
813 return CommonDescendants / Denominator;
816NodeId ASTDiff::Impl::findCandidate(
const Mapping &M, NodeId Id1)
const {
818 double HighestSimilarity = 0.0;
819 for (NodeId Id2 : T2) {
820 if (!isMatchingPossible(Id1, Id2))
824 double Similarity = getJaccardSimilarity(M, Id1, Id2);
825 if (Similarity >= Options.MinSimilarity && Similarity > HighestSimilarity) {
826 HighestSimilarity = Similarity;
833void ASTDiff::Impl::matchBottomUp(Mapping &M)
const {
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());
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)
850 NodeId Id2 = findCandidate(M, Id1);
853 addOptimalMapping(M, Id1, Id2);
858Mapping ASTDiff::Impl::matchTopDown()
const {
862 Mapping M(T1.getSize() + T2.getSize());
864 L1.push(T1.getRootId());
865 L2.push(T2.getRootId());
868 while (std::min(Max1 = L1.peekMax(), Max2 = L2.peekMax()) >
871 for (NodeId Id : L1.pop())
876 for (NodeId Id : L2.pop())
880 std::vector<NodeId> H1, H2;
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);
891 for (NodeId Id1 : H1) {
895 for (NodeId Id2 : H2) {
905 :
T1(
T1),
T2(
T2), Options(Options) {
912 if (Options.StopAfterTopDown)
919 if (!M.hasSrc(Id1)) {
920 T1.getMutableNode(Id1).Change =
Delete;
921 T1.getMutableNode(Id1).Shift -= 1;
925 if (!M.hasDst(Id2)) {
926 T2.getMutableNode(Id2).Change =
Insert;
927 T2.getMutableNode(Id2).Shift -= 1;
931 NodeId Id2 = M.getDst(Id1);
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;
942 NodeId Id1 = M.getSrc(Id2);
945 Node &N1 =
T1.getMutableNode(Id1);
946 Node &N2 =
T2.getMutableNode(Id2);
949 if (!haveSameParents(M, Id1, Id2) ||
950 T1.findPositionInParent(Id1,
true) !=
951 T2.findPositionInParent(Id2,
true)) {
954 if (
T1.getNodeValue(Id1) !=
T2.getNodeValue(Id2)) {
962 : DiffImpl(
std::make_unique<
Impl>(*T1.TreeImpl, *T2.TreeImpl, Options)) {}
967 return DiffImpl->getMapped(SourceTree.
TreeImpl, Id);
972 this, AST.getTranslationUnitDecl(), AST)) {}
990 return TreeImpl->findPositionInParent(Id);
993std::pair<unsigned, unsigned>
1001 if (ThisExpr->isImplicit())
1004 unsigned Begin =
SrcMgr.getFileOffset(
SrcMgr.getExpansionLoc(BeginLoc));
1005 unsigned End =
SrcMgr.getFileOffset(
SrcMgr.getExpansionLoc(EndLoc));
1006 return {Begin, End};
llvm::MachO::Record Record
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 ...
DynTypedNodeList getParents(const NodeT &Node)
Forwards to get node parents from the ParentMapContext.
QualType getTypeDeclType(ElaboratedTypeKeyword Keyword, NestedNameSpecifier Qualifier, const TypeDecl *Decl) const
Represents a C++ base or member initializer.
bool isWritten() const
Determine whether this initializer is explicitly written in the source code.
Represents the this expression in C++.
Represents a character-granular source range.
DeclContext - This is used only as base class of specific decl types that can act as declaration cont...
Decl - This represents one declaration (or definition), e.g.
bool isImplicit() const
isImplicit - Indicates whether the declaration was implicitly generated by the implementation.
DeclContext * getDeclContext()
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.
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.
This represents a decl that may have a name.
std::string getQualifiedNameAsString() const
A (possibly-)qualified type.
static std::string getAsString(SplitQualType split, const PrintingPolicy &Policy)
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.
QualType getCanonicalTypeInternal() const
static StringRef getOpcodeStr(Opcode Op)
getOpcodeStr - Turn an Opcode enum value into the punctuation char it corresponds to,...
void computeChangeKinds(Mapping &M)
NodeId getMapped(const std::unique_ptr< SyntaxTree::Impl > &Tree, NodeId Id) const
Impl(SyntaxTree::Impl &T1, SyntaxTree::Impl &T2, const ComparisonOptions &Options)
friend class ZhangShashaMatcher
void computeMapping()
Matches nodes one-by-one based on their similarity.
ASTDiff(SyntaxTree &Src, SyntaxTree &Dst, const ComparisonOptions &Options)
NodeId getMapped(const SyntaxTree &SourceTree, NodeId Id) const
const Node & getNode(SNodeId Id) const
SNodeId getLeftMostDescendant(SNodeId Id) const
Subtree(const SyntaxTree::Impl &Tree, NodeId SubtreeRoot)
std::vector< SNodeId > KeyRoots
NodeId getPostorderOffset() const
Returns the postorder index of the leftmost descendant in the subtree.
NodeId getIdInRoot(SNodeId Id) const
std::string getNodeValue(SNodeId Id) const
Represents the AST of a TranslationUnit.
std::string getRelativeName(const NamedDecl *ND, const DeclContext *Context) const
int getNumberOfDescendants(NodeId Id) const
bool isValidNodeId(NodeId Id) const
std::vector< NodeId > Leaves
bool isInSubtree(NodeId Id, NodeId SubtreeRoot) const
PreorderIterator begin() const
std::vector< Node > Nodes
Nodes in preorder.
PreorderIterator end() const
int findPositionInParent(NodeId Id, bool Shifted=false) const
const Node & getNode(NodeId Id) const
std::string getStmtValue(const Stmt *S) const
std::vector< int > PostorderIds
std::string getNodeValue(NodeId Id) const
Impl(SyntaxTree *Parent, std::enable_if_t< std::is_base_of_v< Decl, T >, T > *Node, ASTContext &AST)
Impl(SyntaxTree *Parent, std::enable_if_t< std::is_base_of_v< Stmt, T >, T > *Node, ASTContext &AST)
std::string getDeclValue(const Decl *D) const
std::vector< NodeId > NodesBfs
Impl(SyntaxTree *Parent, ASTContext &AST)
Node & getMutableNode(NodeId Id)
SyntaxTree objects represent subtrees of the AST.
const Node & getNode(NodeId Id) const
int findPositionInParent(NodeId Id) const
const ASTContext & getASTContext() const
PreorderIterator begin() const
std::pair< unsigned, unsigned > getSourceRangeOffsets(const Node &N) const
SyntaxTree(ASTContext &AST)
Constructs a tree from a translation unit.
std::unique_ptr< Impl > TreeImpl
PreorderIterator end() const
std::string getNodeValue(NodeId Id) const
Serialize the node attributes to a string representation.
ZhangShashaMatcher(const ASTDiff::Impl &DiffImpl, const SyntaxTree::Impl &T1, const SyntaxTree::Impl &T2, NodeId Id1, NodeId Id2)
std::vector< std::pair< NodeId, NodeId > > getMatchingNodes()
Public enums and private classes that are part of the SourceManager implementation.
static bool isSpecializedNodeExcluded(const Decl *D)
static const DeclContext * getEnclosingDeclContext(ASTContext &AST, const Stmt *S)
static std::vector< NodeId > getSubtreePostorder(const SyntaxTree::Impl &Tree, NodeId Root)
DynTypedNode DynTypedNode
static std::vector< NodeId > getSubtreeBfs(const SyntaxTree::Impl &Tree, NodeId Root)
static bool isNodeExcluded(const SourceManager &SrcMgr, T *N)
static std::string getInitializerValue(const CXXCtorInitializer *Init, const PrintingPolicy &TypePP)
The JSON file list parser is used to communicate input to InstallAPI.
@ Result
The result type of a method or function.
const FunctionProtoType * T
@ Other
Other implicit parameter.
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.
int const char * function
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.
NodeId RightMostDescendant
std::optional< std::string > getQualifiedIdentifier() const
std::optional< StringRef > getIdentifier() const
ASTNodeKind getType() const
NodeId LeftMostDescendant
StringRef getTypeLabel() const
SmallVector< NodeId, 4 > Children
Identifies a node in a subtree by its postorder offset, starting at 1.
SNodeId operator+(int Other) const