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 | #include <optional> |
24 | |
25 | namespace clang { |
26 | namespace diff { |
27 | |
28 | enum ChangeKind { |
29 | None, |
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. |
38 | struct Node { |
39 | NodeId Parent, LeftMostDescendant, RightMostDescendant; |
40 | int Depth, Height, Shift = 0; |
41 | DynTypedNode ASTNode; |
42 | SmallVector<NodeId, 4> Children; |
43 | ChangeKind Change = None; |
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. |
54 | class SyntaxTree { |
55 | public: |
56 | /// Constructs a tree from a translation unit. |
57 | SyntaxTree(ASTContext &AST); |
58 | /// Constructs a tree from any AST node. |
59 | template <class T> |
60 | SyntaxTree(T *Node, ASTContext &AST) |
61 | : TreeImpl(std::make_unique<Impl>(this, Node, AST)) {} |
62 | SyntaxTree(SyntaxTree &&Other) = default; |
63 | ~SyntaxTree(); |
64 | |
65 | const ASTContext &getASTContext() const; |
66 | StringRef getFilename() const; |
67 | |
68 | int getSize() const; |
69 | NodeId getRootId() const; |
70 | using PreorderIterator = NodeId; |
71 | PreorderIterator begin() const; |
72 | PreorderIterator end() const; |
73 | |
74 | const Node &getNode(NodeId Id) const; |
75 | int findPositionInParent(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 | |
90 | struct ComparisonOptions { |
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(Other: N2.getType()); |
107 | } |
108 | }; |
109 | |
110 | class ASTDiff { |
111 | public: |
112 | ASTDiff(SyntaxTree &Src, SyntaxTree &Dst, const ComparisonOptions &Options); |
113 | ~ASTDiff(); |
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 | |
120 | private: |
121 | std::unique_ptr<Impl> DiffImpl; |
122 | }; |
123 | |
124 | } // end namespace diff |
125 | } // end namespace clang |
126 | |
127 | #endif |
128 | |