ASTDiff.h source code [clang_source_code/include/clang/Tooling/ASTDiff/ASTDiff.h]

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	ast_type_traits::DynTypedNode ASTNode;
41	SmallVector<NodeId, 4> Children;
42	ChangeKind Change = None;
43
44	ast_type_traits::ASTNodeKind getType() const;
45	StringRef getTypeLabel() const;
46	bool isLeaf() const { return Children.empty(); }
47	llvm::Optional<StringRef> getIdentifier() const;
48	llvm::Optional<std::string> getQualifiedIdentifier() const;
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>
73	SyntaxTree(T *Node, ASTContext &AST)
74	: TreeImpl(llvm::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;
83	using PreorderIterator = NodeId;
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.
96	std::string getNodeValue(NodeId Id) const;
97	std::string getNodeValue(const Node &Node) const;
98
99	class Impl;
100	std::unique_ptr<Impl> TreeImpl;
101	};
102
103	struct ComparisonOptions {
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
127