/Users/buildslave/jenkins/workspace/coverage/llvm-project/clang/include/clang/Tooling/ASTDiff/ASTDiff.h
Line | Count | Source |
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 | | |
22 | | #include "clang/Tooling/ASTDiff/ASTDiffInternal.h" |
23 | | |
24 | | namespace clang { |
25 | | namespace diff { |
26 | | |
27 | | enum ChangeKind { |
28 | | None, |
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 { |
38 | | NodeId Parent, LeftMostDescendant, RightMostDescendant; |
39 | | int Depth, Height, Shift = 0; |
40 | | DynTypedNode ASTNode; |
41 | | SmallVector<NodeId, 4> Children; |
42 | | ChangeKind Change = None; |
43 | | |
44 | | ASTNodeKind getType() const; |
45 | | StringRef getTypeLabel() const; |
46 | 1.03k | bool isLeaf() const { return Children.empty(); } |
47 | | llvm::Optional<StringRef> getIdentifier() const; |
48 | | llvm::Optional<std::string> getQualifiedIdentifier() const; |
49 | | }; |
50 | | |
51 | | /// SyntaxTree objects represent subtrees of the AST. |
52 | | /// They can be constructed from any Decl or Stmt. |
53 | | class SyntaxTree { |
54 | | public: |
55 | | /// Constructs a tree from a translation unit. |
56 | | SyntaxTree(ASTContext &AST); |
57 | | /// Constructs a tree from any AST node. |
58 | | template <class T> |
59 | | SyntaxTree(T *Node, ASTContext &AST) |
60 | | : TreeImpl(std::make_unique<Impl>(this, Node, AST)) {} |
61 | | SyntaxTree(SyntaxTree &&Other) = default; |
62 | | ~SyntaxTree(); |
63 | | |
64 | | const ASTContext &getASTContext() const; |
65 | | StringRef getFilename() const; |
66 | | |
67 | | int getSize() const; |
68 | | NodeId getRootId() const; |
69 | | using PreorderIterator = NodeId; |
70 | | PreorderIterator begin() const; |
71 | | PreorderIterator end() const; |
72 | | |
73 | | const Node &getNode(NodeId Id) const; |
74 | | int findPositionInParent(NodeId Id) const; |
75 | | |
76 | | // Returns the starting and ending offset of the node in its source file. |
77 | | std::pair<unsigned, unsigned> getSourceRangeOffsets(const Node &N) const; |
78 | | |
79 | | /// Serialize the node attributes to a string representation. This should |
80 | | /// uniquely distinguish nodes of the same kind. Note that this function just |
81 | | /// returns a representation of the node value, not considering descendants. |
82 | | std::string getNodeValue(NodeId Id) const; |
83 | | std::string getNodeValue(const Node &Node) const; |
84 | | |
85 | | class Impl; |
86 | | std::unique_ptr<Impl> TreeImpl; |
87 | | }; |
88 | | |
89 | | struct ComparisonOptions { |
90 | | /// During top-down matching, only consider nodes of at least this height. |
91 | | int MinHeight = 2; |
92 | | |
93 | | /// During bottom-up matching, match only nodes with at least this value as |
94 | | /// the ratio of their common descendants. |
95 | | double MinSimilarity = 0.5; |
96 | | |
97 | | /// Whenever two subtrees are matched in the bottom-up phase, the optimal |
98 | | /// mapping is computed, unless the size of either subtrees exceeds this. |
99 | | int MaxSize = 100; |
100 | | |
101 | | bool StopAfterTopDown = false; |
102 | | |
103 | | /// Returns false if the nodes should never be matched. |
104 | 11.6k | bool isMatchingAllowed(const Node &N1, const Node &N2) const { |
105 | 11.6k | return N1.getType().isSame(N2.getType()); |
106 | 11.6k | } |
107 | | }; |
108 | | |
109 | | class ASTDiff { |
110 | | public: |
111 | | ASTDiff(SyntaxTree &Src, SyntaxTree &Dst, const ComparisonOptions &Options); |
112 | | ~ASTDiff(); |
113 | | |
114 | | // Returns the ID of the node that is mapped to the given node in SourceTree. |
115 | | NodeId getMapped(const SyntaxTree &SourceTree, NodeId Id) const; |
116 | | |
117 | | class Impl; |
118 | | |
119 | | private: |
120 | | std::unique_ptr<Impl> DiffImpl; |
121 | | }; |
122 | | |
123 | | } // end namespace diff |
124 | | } // end namespace clang |
125 | | |
126 | | #endif |