clang 19.0.0git
ASTDiff.h
Go to the documentation of this file.
1//===- ASTDiff.h - AST differencing API -----------------------*- C++ -*- -===//
2//
3//
4// Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.
5// See https://llvm.org/LICENSE.txt for license information.
6// SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception
7//
8//===----------------------------------------------------------------------===//
9//
10// This file specifies an interface that can be used to compare C++ syntax
11// trees.
12//
13// We use the gumtree algorithm which combines a heuristic top-down search that
14// is able to match large subtrees that are equivalent, with an optimal
15// algorithm to match small subtrees.
16//
17//===----------------------------------------------------------------------===//
18
19#ifndef LLVM_CLANG_TOOLING_ASTDIFF_ASTDIFF_H
20#define LLVM_CLANG_TOOLING_ASTDIFF_ASTDIFF_H
21
23#include <optional>
24
25namespace clang {
26namespace diff {
27
30 Delete, // (Src): delete node Src.
31 Update, // (Src, Dst): update the value of node Src to match Dst.
32 Insert, // (Src, Dst, Pos): insert Src as child of Dst at offset Pos.
33 Move, // (Src, Dst, Pos): move Src to be a child of Dst at offset Pos.
34 UpdateMove // Same as Move plus Update.
35};
36
37/// Represents a Clang AST node, alongside some additional information.
38struct Node {
40 int Depth, Height, Shift = 0;
44
45 ASTNodeKind getType() const;
46 StringRef getTypeLabel() const;
47 bool isLeaf() const { return Children.empty(); }
48 std::optional<StringRef> getIdentifier() const;
49 std::optional<std::string> getQualifiedIdentifier() const;
50};
51
52/// SyntaxTree objects represent subtrees of the AST.
53/// They can be constructed from any Decl or Stmt.
55public:
56 /// Constructs a tree from a translation unit.
58 /// Constructs a tree from any AST node.
59 template <class T>
61 : TreeImpl(std::make_unique<Impl>(this, Node, AST)) {}
64
65 const ASTContext &getASTContext() const;
66 StringRef getFilename() const;
67
68 int getSize() const;
69 NodeId getRootId() const;
71 PreorderIterator begin() const;
72 PreorderIterator end() const;
73
74 const Node &getNode(NodeId Id) const;
76
77 // Returns the starting and ending offset of the node in its source file.
78 std::pair<unsigned, unsigned> getSourceRangeOffsets(const Node &N) const;
79
80 /// Serialize the node attributes to a string representation. This should
81 /// uniquely distinguish nodes of the same kind. Note that this function just
82 /// returns a representation of the node value, not considering descendants.
83 std::string getNodeValue(NodeId Id) const;
84 std::string getNodeValue(const Node &Node) const;
85
86 class Impl;
87 std::unique_ptr<Impl> TreeImpl;
88};
89
91 /// During top-down matching, only consider nodes of at least this height.
92 int MinHeight = 2;
93
94 /// During bottom-up matching, match only nodes with at least this value as
95 /// the ratio of their common descendants.
96 double MinSimilarity = 0.5;
97
98 /// Whenever two subtrees are matched in the bottom-up phase, the optimal
99 /// mapping is computed, unless the size of either subtrees exceeds this.
100 int MaxSize = 100;
101
102 bool StopAfterTopDown = false;
103
104 /// Returns false if the nodes should never be matched.
105 bool isMatchingAllowed(const Node &N1, const Node &N2) const {
106 return N1.getType().isSame(N2.getType());
107 }
108};
109
110class ASTDiff {
111public:
112 ASTDiff(SyntaxTree &Src, SyntaxTree &Dst, const ComparisonOptions &Options);
114
115 // Returns the ID of the node that is mapped to the given node in SourceTree.
116 NodeId getMapped(const SyntaxTree &SourceTree, NodeId Id) const;
117
118 class Impl;
119
120private:
121 std::unique_ptr<Impl> DiffImpl;
122};
123
124} // end namespace diff
125} // end namespace clang
126
127#endif
int Id
Definition: ASTDiff.cpp:190
Holds long-lived AST nodes (such as types and decls) that can be referred to throughout the semantic ...
Definition: ASTContext.h:182
Kind identifier.
Definition: ASTTypeTraits.h:51
constexpr bool isSame(ASTNodeKind Other) const
Returns true if this and Other represent the same kind.
Definition: ASTTypeTraits.h:73
NodeId getMapped(const SyntaxTree &SourceTree, NodeId Id) const
Definition: ASTDiff.cpp:965
Represents the AST of a TranslationUnit.
Definition: ASTDiff.cpp:113
SyntaxTree objects represent subtrees of the AST.
Definition: ASTDiff.h:54
const Node & getNode(NodeId Id) const
Definition: ASTDiff.cpp:977
StringRef getFilename() const
NodeId getRootId() const
Definition: ASTDiff.cpp:982
int findPositionInParent(NodeId Id) const
Definition: ASTDiff.cpp:988
SyntaxTree(SyntaxTree &&Other)=default
const ASTContext & getASTContext() const
Definition: ASTDiff.cpp:975
PreorderIterator begin() const
Definition: ASTDiff.cpp:983
std::pair< unsigned, unsigned > getSourceRangeOffsets(const Node &N) const
Definition: ASTDiff.cpp:993
std::unique_ptr< Impl > TreeImpl
Definition: ASTDiff.h:87
SyntaxTree(T *Node, ASTContext &AST)
Constructs a tree from any AST node.
Definition: ASTDiff.h:60
PreorderIterator end() const
Definition: ASTDiff.cpp:986
std::string getNodeValue(NodeId Id) const
Serialize the node attributes to a string representation.
Definition: ASTDiff.cpp:1008
@ UpdateMove
Definition: ASTDiff.h:34
DynTypedNode DynTypedNode
The JSON file list parser is used to communicate input to InstallAPI.
const FunctionProtoType * T
@ Other
Other implicit parameter.
Definition: Format.h:5428
int MinHeight
During top-down matching, only consider nodes of at least this height.
Definition: ASTDiff.h:92
double MinSimilarity
During bottom-up matching, match only nodes with at least this value as the ratio of their common des...
Definition: ASTDiff.h:96
bool isMatchingAllowed(const Node &N1, const Node &N2) const
Returns false if the nodes should never be matched.
Definition: ASTDiff.h:105
int MaxSize
Whenever two subtrees are matched in the bottom-up phase, the optimal mapping is computed,...
Definition: ASTDiff.h:100
Within a tree, this identifies a node by its preorder offset.
Represents a Clang AST node, alongside some additional information.
Definition: ASTDiff.h:38
NodeId Parent
Definition: ASTDiff.h:39
NodeId RightMostDescendant
Definition: ASTDiff.h:39
bool isLeaf() const
Definition: ASTDiff.h:47
ChangeKind Change
Definition: ASTDiff.h:43
std::optional< std::string > getQualifiedIdentifier() const
Definition: ASTDiff.cpp:690
std::optional< StringRef > getIdentifier() const
Definition: ASTDiff.cpp:698
ASTNodeKind getType() const
Definition: ASTDiff.cpp:686
NodeId LeftMostDescendant
Definition: ASTDiff.h:39
StringRef getTypeLabel() const
Definition: ASTDiff.cpp:688
DynTypedNode ASTNode
Definition: ASTDiff.h:41
SmallVector< NodeId, 4 > Children
Definition: ASTDiff.h:42