clang  14.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 
24 namespace clang {
25 namespace diff {
26 
27 enum ChangeKind {
29  Delete, // (Src): delete node Src.
30  Update, // (Src, Dst): update the value of node Src to match Dst.
31  Insert, // (Src, Dst, Pos): insert Src as child of Dst at offset Pos.
32  Move, // (Src, Dst, Pos): move Src to be a child of Dst at offset Pos.
33  UpdateMove // Same as Move plus Update.
34 };
35 
36 /// Represents a Clang AST node, alongside some additional information.
37 struct Node {
39  int Depth, Height, Shift = 0;
43 
44  ASTNodeKind getType() const;
45  StringRef getTypeLabel() const;
46  bool isLeaf() const { return Children.empty(); }
49 };
50 
51 class ASTDiff {
52 public:
53  ASTDiff(SyntaxTree &Src, SyntaxTree &Dst, const ComparisonOptions &Options);
54  ~ASTDiff();
55 
56  // Returns the ID of the node that is mapped to the given node in SourceTree.
57  NodeId getMapped(const SyntaxTree &SourceTree, NodeId Id) const;
58 
59  class Impl;
60 
61 private:
62  std::unique_ptr<Impl> DiffImpl;
63 };
64 
65 /// SyntaxTree objects represent subtrees of the AST.
66 /// They can be constructed from any Decl or Stmt.
67 class SyntaxTree {
68 public:
69  /// Constructs a tree from a translation unit.
70  SyntaxTree(ASTContext &AST);
71  /// Constructs a tree from any AST node.
72  template <class T>
74  : TreeImpl(std::make_unique<Impl>(this, Node, AST)) {}
75  SyntaxTree(SyntaxTree &&Other) = default;
76  ~SyntaxTree();
77 
78  const ASTContext &getASTContext() const;
79  StringRef getFilename() const;
80 
81  int getSize() const;
82  NodeId getRootId() const;
84  PreorderIterator begin() const;
85  PreorderIterator end() const;
86 
87  const Node &getNode(NodeId Id) const;
88  int findPositionInParent(NodeId Id) const;
89 
90  // Returns the starting and ending offset of the node in its source file.
91  std::pair<unsigned, unsigned> getSourceRangeOffsets(const Node &N) const;
92 
93  /// Serialize the node attributes to a string representation. This should
94  /// uniquely distinguish nodes of the same kind. Note that this function just
95  /// returns a representation of the node value, not considering descendants.
97  std::string getNodeValue(const Node &Node) const;
98 
99  class Impl;
100  std::unique_ptr<Impl> TreeImpl;
101 };
102 
104  /// During top-down matching, only consider nodes of at least this height.
105  int MinHeight = 2;
106 
107  /// During bottom-up matching, match only nodes with at least this value as
108  /// the ratio of their common descendants.
109  double MinSimilarity = 0.5;
110 
111  /// Whenever two subtrees are matched in the bottom-up phase, the optimal
112  /// mapping is computed, unless the size of either subtrees exceeds this.
113  int MaxSize = 100;
114 
115  bool StopAfterTopDown = false;
116 
117  /// Returns false if the nodes should never be matched.
118  bool isMatchingAllowed(const Node &N1, const Node &N2) const {
119  return N1.getType().isSame(N2.getType());
120  }
121 };
122 
123 } // end namespace diff
124 } // end namespace clang
125 
126 #endif
clang::diff::SyntaxTree::Impl
Represents the AST of a TranslationUnit.
Definition: ASTDiff.cpp:112
clang::diff::SyntaxTree::~SyntaxTree
~SyntaxTree()
clang::diff::ASTDiff::Impl
Definition: ASTDiff.cpp:57
clang::diff::ASTDiff::getMapped
NodeId getMapped(const SyntaxTree &SourceTree, NodeId Id) const
Definition: ASTDiff.cpp:966
clang::diff::Node::getTypeLabel
StringRef getTypeLabel() const
Definition: ASTDiff.cpp:689
string
string(SUBSTRING ${CMAKE_CURRENT_BINARY_DIR} 0 ${PATH_LIB_START} PATH_HEAD) string(SUBSTRING $
Definition: CMakeLists.txt:22
clang::diff::SyntaxTree::TreeImpl
std::unique_ptr< Impl > TreeImpl
Definition: ASTDiff.h:99
clang::diff::SyntaxTree::end
PreorderIterator end() const
Definition: ASTDiff.cpp:987
clang::diff::ComparisonOptions
Definition: ASTDiff.h:103
clang::diff::Node::getType
ASTNodeKind getType() const
Definition: ASTDiff.cpp:687
llvm::SmallVector
Definition: LLVM.h:38
clang::diff::ChangeKind
ChangeKind
Definition: ASTDiff.h:27
clang::diff::NodeId
Within a tree, this identifies a node by its preorder offset.
Definition: ASTDiffInternal.h:25
clang::diff::SyntaxTree::getASTContext
const ASTContext & getASTContext() const
Definition: ASTDiff.cpp:976
clang::diff::ComparisonOptions::MinSimilarity
double MinSimilarity
During bottom-up matching, match only nodes with at least this value as the ratio of their common des...
Definition: ASTDiff.h:109
clang::diff::ASTDiff::~ASTDiff
~ASTDiff()
clang::diff::Node::Children
SmallVector< NodeId, 4 > Children
Definition: ASTDiff.h:41
llvm::Optional
Definition: LLVM.h:40
clang::diff::ComparisonOptions::StopAfterTopDown
bool StopAfterTopDown
Definition: ASTDiff.h:115
clang::diff::ASTDiff::ASTDiff
ASTDiff(SyntaxTree &Src, SyntaxTree &Dst, const ComparisonOptions &Options)
Definition: ASTDiff.cpp:960
clang::diff::SyntaxTree::SyntaxTree
SyntaxTree(T *Node, ASTContext &AST)
Constructs a tree from any AST node.
Definition: ASTDiff.h:73
clang::diff::Node::Height
int Height
Definition: ASTDiff.h:39
clang::diff::SyntaxTree::getRootId
NodeId getRootId() const
Definition: ASTDiff.cpp:983
clang::diff::Node::LeftMostDescendant
NodeId LeftMostDescendant
Definition: ASTDiff.h:38
clang::diff::Move
@ Move
Definition: ASTDiff.h:32
Id
int Id
Definition: ASTDiff.cpp:191
clang::diff::ASTDiff
Definition: ASTDiff.h:51
clang::ASTContext
Holds long-lived AST nodes (such as types and decls) that can be referred to throughout the semantic ...
Definition: ASTContext.h:211
clang::diff::SyntaxTree::findPositionInParent
int findPositionInParent(NodeId Id) const
Definition: ASTDiff.cpp:989
clang::diff::DynTypedNode
DynTypedNode DynTypedNode
Definition: ASTDiffInternal.h:18
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:1009
clang::diff::UpdateMove
@ UpdateMove
Definition: ASTDiff.h:33
clang::diff::SyntaxTree
SyntaxTree objects represent subtrees of the AST.
Definition: ASTDiff.h:67
clang::diff::Node::ASTNode
DynTypedNode ASTNode
Definition: ASTDiff.h:40
ASTDiffInternal.h
clang::diff::Node::Depth
int Depth
Definition: ASTDiff.h:39
clang::diff::Delete
@ Delete
Definition: ASTDiff.h:29
clang::diff::Node::getQualifiedIdentifier
llvm::Optional< std::string > getQualifiedIdentifier() const
Definition: ASTDiff.cpp:691
clang::diff::Node::Parent
NodeId Parent
Definition: ASTDiff.h:38
clang::diff::SyntaxTree::getSourceRangeOffsets
std::pair< unsigned, unsigned > getSourceRangeOffsets(const Node &N) const
Definition: ASTDiff.cpp:994
clang::diff::Node::getIdentifier
llvm::Optional< StringRef > getIdentifier() const
Definition: ASTDiff.cpp:699
clang::diff::ComparisonOptions::isMatchingAllowed
bool isMatchingAllowed(const Node &N1, const Node &N2) const
Returns false if the nodes should never be matched.
Definition: ASTDiff.h:118
clang::diff::SyntaxTree::getSize
int getSize() const
Definition: ASTDiff.cpp:982
std
Definition: Format.h:3899
clang::ASTNodeKind
Kind identifier.
Definition: ASTTypeTraits.h:50
clang
Definition: CalledOnceCheck.h:17
clang::diff::ComparisonOptions::MaxSize
int MaxSize
Whenever two subtrees are matched in the bottom-up phase, the optimal mapping is computed,...
Definition: ASTDiff.h:113
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::getFilename
StringRef getFilename() const
clang::diff::SyntaxTree::begin
PreorderIterator begin() const
Definition: ASTDiff.cpp:984
clang::diff::SyntaxTree::getNode
const Node & getNode(NodeId Id) const
Definition: ASTDiff.cpp:978
clang::ASTNodeKind::isSame
bool isSame(ASTNodeKind Other) const
Returns true if this and Other represent the same kind.
Definition: ASTTypeTraits.h:71
clang::diff::None
@ None
Definition: ASTDiff.h:28
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:970
clang::diff::ComparisonOptions::MinHeight
int MinHeight
During top-down matching, only consider nodes of at least this height.
Definition: ASTDiff.h:105
clang::diff::Node::RightMostDescendant
NodeId RightMostDescendant
Definition: ASTDiff.h:38
clang::diff::Node::isLeaf
bool isLeaf() const
Definition: ASTDiff.h:46