ASTDiff.cpp source code [clang_source_code/lib/Tooling/ASTDiff/ASTDiff.cpp]

1	//===- ASTDiff.cpp - AST differencing implementation------------ C++ -- -===//
2	//
3	// Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.
4	// See https://llvm.org/LICENSE.txt for license information.
5	// SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception
6	//
7	//===----------------------------------------------------------------------===//
8	//
9	// This file contains definitons for the AST differencing interface.
10	//
11	//===----------------------------------------------------------------------===//
12
13	#include "clang/Tooling/ASTDiff/ASTDiff.h"
14
15	#include "clang/AST/RecursiveASTVisitor.h"
16	#include "clang/Lex/Lexer.h"
17	#include "llvm/ADT/PriorityQueue.h"
18
19	#include <limits>
20	#include <memory>
21	#include <unordered_set>
22
23	using namespace llvm;
24	using namespace clang;
25
26	namespace clang {
27	namespace diff {
28
29	namespace {
30	/// Maps nodes of the left tree to ones on the right, and vice versa.
31	class Mapping {
32	public:
33	Mapping() = default;
34	Mapping(Mapping &&Other) = default;
35	Mapping &operator=(Mapping &&Other) = default;
36
37	Mapping(size_t Size) {
38	SrcToDst = llvm::make_unique<NodeId[]>(Size);
39	DstToSrc = llvm::make_unique<NodeId[]>(Size);
40	}
41
42	void link(NodeId Src, NodeId Dst) {
43	SrcToDst[Src] = Dst, DstToSrc[Dst] = Src;
44	}
45
46	NodeId getDst(NodeId Src) const { return SrcToDst[Src]; }
47	NodeId getSrc(NodeId Dst) const { return DstToSrc[Dst]; }
48	bool hasSrc(NodeId Src) const { return getDst(Src).isValid(); }
49	bool hasDst(NodeId Dst) const { return getSrc(Dst).isValid(); }
50
51	private:
52	std::unique_ptr<NodeId[]> SrcToDst, DstToSrc;
53	};
54	} // end anonymous namespace
55
56	class ASTDiff::Impl {
57	public:
58	SyntaxTree::Impl &T1, &T2;
59	Mapping TheMapping;
60
61	Impl(SyntaxTree::Impl &T1, SyntaxTree::Impl &T2,
62	const ComparisonOptions &Options);
63
64	/// Matches nodes one-by-one based on their similarity.
65	void computeMapping();
66
67	// Compute Change for each node based on similarity.
68	void computeChangeKinds(Mapping &M);
69
70	NodeId getMapped(const std::unique_ptr<SyntaxTree::Impl> &Tree,
71	NodeId Id) const {
72	if (&*Tree == &T1)
73	return TheMapping.getDst(Id);
74	(0) . __assert_fail ("&Tree == &T2 && \"Invalid tree.\"", "/home/seafit/code_projects/clang_source/clang/lib/Tooling/ASTDiff/ASTDiff.cpp", 74, __PRETTY_FUNCTION__))" file_link="../../../../include/assert.h.html#88" macro="true">assert(&Tree == &T2 && "Invalid tree.");
75	return TheMapping.getSrc(Id);
76	}
77
78	private:
79	// Returns true if the two subtrees are identical.
80	bool identical(NodeId Id1, NodeId Id2) const;
81
82	// Returns false if the nodes must not be mached.
83	bool isMatchingPossible(NodeId Id1, NodeId Id2) const;
84
85	// Returns true if the nodes' parents are matched.
86	bool haveSameParents(const Mapping &M, NodeId Id1, NodeId Id2) const;
87
88	// Uses an optimal albeit slow algorithm to compute a mapping between two
89	// subtrees, but only if both have fewer nodes than MaxSize.
90	void addOptimalMapping(Mapping &M, NodeId Id1, NodeId Id2) const;
91
92	// Computes the ratio of common descendants between the two nodes.
93	// Descendants are only considered to be equal when they are mapped in M.
94	double getJaccardSimilarity(const Mapping &M, NodeId Id1, NodeId Id2) const;
95
96	// Returns the node that has the highest degree of similarity.
97	NodeId findCandidate(const Mapping &M, NodeId Id1) const;
98
99	// Returns a mapping of identical subtrees.
100	Mapping matchTopDown() const;
101
102	// Tries to match any yet unmapped nodes, in a bottom-up fashion.
103	void matchBottomUp(Mapping &M) const;
104
105	const ComparisonOptions &Options;
106
107	friend class ZhangShashaMatcher;
108	};
109
110	/// Represents the AST of a TranslationUnit.
111	class SyntaxTree::Impl {
112	public:
113	Impl(SyntaxTree *Parent, ASTContext &AST);
114	/// Constructs a tree from an AST node.
115	Impl(SyntaxTree Parent, Decl N, ASTContext &AST);
116	Impl(SyntaxTree Parent, Stmt N, ASTContext &AST);
117	template <class T>
118	Impl(SyntaxTree *Parent,
119	typename std::enable_if<std::is_base_of<Stmt, T>::value, T>::type *Node,
120	ASTContext &AST)
121	: Impl(Parent, dyn_cast<Stmt>(Node), AST) {}
122	template <class T>
123	Impl(SyntaxTree *Parent,
124	typename std::enable_if<std::is_base_of<Decl, T>::value, T>::type *Node,
125	ASTContext &AST)
126	: Impl(Parent, dyn_cast<Decl>(Node), AST) {}
127
128	SyntaxTree *Parent;
129	ASTContext &AST;
130	PrintingPolicy TypePP;
131	/// Nodes in preorder.
132	std::vector<Node> Nodes;
133	std::vector<NodeId> Leaves;
134	// Maps preorder indices to postorder ones.
135	std::vector<int> PostorderIds;
136	std::vector<NodeId> NodesBfs;
137
138	int getSize() const { return Nodes.size(); }
139	NodeId getRootId() const { return 0; }
140	PreorderIterator begin() const { return getRootId(); }
141	PreorderIterator end() const { return getSize(); }
142
143	const Node &getNode(NodeId Id) const { return Nodes[Id]; }
144	Node &getMutableNode(NodeId Id) { return Nodes[Id]; }
145	bool isValidNodeId(NodeId Id) const { return Id >= 0 && Id < getSize(); }
146	void addNode(Node &N) { Nodes.push_back(N); }
147	int getNumberOfDescendants(NodeId Id) const;
148	bool isInSubtree(NodeId Id, NodeId SubtreeRoot) const;
149	int findPositionInParent(NodeId Id, bool Shifted = false) const;
150
151	std::string getRelativeName(const NamedDecl *ND,
152	const DeclContext *Context) const;
153	std::string getRelativeName(const NamedDecl *ND) const;
154
155	std::string getNodeValue(NodeId Id) const;
156	std::string getNodeValue(const Node &Node) const;
157	std::string getDeclValue(const Decl *D) const;
158	std::string getStmtValue(const Stmt *S) const;
159
160	private:
161	void initTree();
162	void setLeftMostDescendants();
163	};
164
165	static bool isSpecializedNodeExcluded(const Decl *D) { return D->isImplicit(); }
166	static bool isSpecializedNodeExcluded(const Stmt *S) { return false; }
167	static bool isSpecializedNodeExcluded(CXXCtorInitializer *I) {
168	return !I->isWritten();
169	}
170
171	template <class T>
172	static bool isNodeExcluded(const SourceManager &SrcMgr, T *N) {
173	if (!N)
174	return true;
175	SourceLocation SLoc = N->getSourceRange().getBegin();
176	if (SLoc.isValid()) {
177	// Ignore everything from other files.
178	if (!SrcMgr.isInMainFile(SLoc))
179	return true;
180	// Ignore macros.
181	if (SLoc != SrcMgr.getSpellingLoc(SLoc))
182	return true;
183	}
184	return isSpecializedNodeExcluded(N);
185	}
186
187	namespace {
188	// Sets Height, Parent and Children for each node.
189	struct PreorderVisitor : public RecursiveASTVisitor<PreorderVisitor> {
190	int Id = 0, Depth = 0;
191	NodeId Parent;
192	SyntaxTree::Impl &Tree;
193
194	PreorderVisitor(SyntaxTree::Impl &Tree) : Tree(Tree) {}
195
196	template <class T> std::tuple<NodeId, NodeId> PreTraverse(T *ASTNode) {
197	NodeId MyId = Id;
198	Tree.Nodes.emplace_back();
199	Node &N = Tree.getMutableNode(MyId);
200	N.Parent = Parent;
201	N.Depth = Depth;
202	N.ASTNode = DynTypedNode::create(*ASTNode);
203	(0) . __assert_fail ("!N.ASTNode.getNodeKind().isNone() && \"Expected nodes to have a valid kind.\"", "/home/seafit/code_projects/clang_source/clang/lib/Tooling/ASTDiff/ASTDiff.cpp", 204, __PRETTY_FUNCTION__))" file_link="../../../../include/assert.h.html#88" macro="true">assert(!N.ASTNode.getNodeKind().isNone() &&
204	(0) . __assert_fail ("!N.ASTNode.getNodeKind().isNone() && \"Expected nodes to have a valid kind.\"", "/home/seafit/code_projects/clang_source/clang/lib/Tooling/ASTDiff/ASTDiff.cpp", 204, __PRETTY_FUNCTION__))" file_link="../../../../include/assert.h.html#88" macro="true"> "Expected nodes to have a valid kind.");
205	if (Parent.isValid()) {
206	Node &P = Tree.getMutableNode(Parent);
207	P.Children.push_back(MyId);
208	}
209	Parent = MyId;
210	++Id;
211	++Depth;
212	return std::make_tuple(MyId, Tree.getNode(MyId).Parent);
213	}
214	void PostTraverse(std::tuple<NodeId, NodeId> State) {
215	NodeId MyId, PreviousParent;
216	std::tie(MyId, PreviousParent) = State;
217	(0) . __assert_fail ("MyId.isValid() && \"Expecting to only traverse valid nodes.\"", "/home/seafit/code_projects/clang_source/clang/lib/Tooling/ASTDiff/ASTDiff.cpp", 217, __PRETTY_FUNCTION__))" file_link="../../../../include/assert.h.html#88" macro="true">assert(MyId.isValid() && "Expecting to only traverse valid nodes.");
218	Parent = PreviousParent;
219	--Depth;
220	Node &N = Tree.getMutableNode(MyId);
221	N.RightMostDescendant = Id - 1;
222	(0) . __assert_fail ("N.RightMostDescendant >= 0 && N.RightMostDescendant < Tree.getSize() && \"Rightmost descendant must be a valid tree node.\"", "/home/seafit/code_projects/clang_source/clang/lib/Tooling/ASTDiff/ASTDiff.cpp", 224, __PRETTY_FUNCTION__))" file_link="../../../../include/assert.h.html#88" macro="true">assert(N.RightMostDescendant >= 0 &&
223	(0) . __assert_fail ("N.RightMostDescendant >= 0 && N.RightMostDescendant < Tree.getSize() && \"Rightmost descendant must be a valid tree node.\"", "/home/seafit/code_projects/clang_source/clang/lib/Tooling/ASTDiff/ASTDiff.cpp", 224, __PRETTY_FUNCTION__))" file_link="../../../../include/assert.h.html#88" macro="true"> N.RightMostDescendant < Tree.getSize() &&
224	(0) . __assert_fail ("N.RightMostDescendant >= 0 && N.RightMostDescendant < Tree.getSize() && \"Rightmost descendant must be a valid tree node.\"", "/home/seafit/code_projects/clang_source/clang/lib/Tooling/ASTDiff/ASTDiff.cpp", 224, __PRETTY_FUNCTION__))" file_link="../../../../include/assert.h.html#88" macro="true"> "Rightmost descendant must be a valid tree node.");
225	if (N.isLeaf())
226	Tree.Leaves.push_back(MyId);
227	N.Height = 1;
228	for (NodeId Child : N.Children)
229	N.Height = std::max(N.Height, 1 + Tree.getNode(Child).Height);
230	}
231	bool TraverseDecl(Decl *D) {
232	if (isNodeExcluded(Tree.AST.getSourceManager(), D))
233	return true;
234	auto SavedState = PreTraverse(D);
235	RecursiveASTVisitor<PreorderVisitor>::TraverseDecl(D);
236	PostTraverse(SavedState);
237	return true;
238	}
239	bool TraverseStmt(Stmt *S) {
240	if (auto *E = dyn_cast_or_null<Expr>(S))
241	S = E->IgnoreImplicit();
242	if (isNodeExcluded(Tree.AST.getSourceManager(), S))
243	return true;
244	auto SavedState = PreTraverse(S);
245	RecursiveASTVisitor<PreorderVisitor>::TraverseStmt(S);
246	PostTraverse(SavedState);
247	return true;
248	}
249	bool TraverseType(QualType T) { return true; }
250	bool TraverseConstructorInitializer(CXXCtorInitializer *Init) {
251	if (isNodeExcluded(Tree.AST.getSourceManager(), Init))
252	return true;
253	auto SavedState = PreTraverse(Init);
254	RecursiveASTVisitor<PreorderVisitor>::TraverseConstructorInitializer(Init);
255	PostTraverse(SavedState);
256	return true;
257	}
258	};
259	} // end anonymous namespace
260
261	SyntaxTree::Impl::Impl(SyntaxTree *Parent, ASTContext &AST)
262	: Parent(Parent), AST(AST), TypePP(AST.getLangOpts()) {
263	TypePP.AnonymousTagLocations = false;
264	}
265
266	SyntaxTree::Impl::Impl(SyntaxTree Parent, Decl N, ASTContext &AST)
267	: Impl(Parent, AST) {
268	PreorderVisitor PreorderWalker(*this);
269	PreorderWalker.TraverseDecl(N);
270	initTree();
271	}
272
273	SyntaxTree::Impl::Impl(SyntaxTree Parent, Stmt N, ASTContext &AST)
274	: Impl(Parent, AST) {
275	PreorderVisitor PreorderWalker(*this);
276	PreorderWalker.TraverseStmt(N);
277	initTree();
278	}
279
280	static std::vector<NodeId> getSubtreePostorder(const SyntaxTree::Impl &Tree,
281	NodeId Root) {
282	std::vector<NodeId> Postorder;
283	std::function<void(NodeId)> Traverse = [&](NodeId Id) {
284	const Node &N = Tree.getNode(Id);
285	for (NodeId Child : N.Children)
286	Traverse(Child);
287	Postorder.push_back(Id);
288	};
289	Traverse(Root);
290	return Postorder;
291	}
292
293	static std::vector<NodeId> getSubtreeBfs(const SyntaxTree::Impl &Tree,
294	NodeId Root) {
295	std::vector<NodeId> Ids;
296	size_t Expanded = 0;
297	Ids.push_back(Root);
298	while (Expanded < Ids.size())
299	for (NodeId Child : Tree.getNode(Ids[Expanded++]).Children)
300	Ids.push_back(Child);
301	return Ids;
302	}
303
304	void SyntaxTree::Impl::initTree() {
305	setLeftMostDescendants();
306	int PostorderId = 0;
307	PostorderIds.resize(getSize());
308	std::function<void(NodeId)> PostorderTraverse = [&](NodeId Id) {
309	for (NodeId Child : getNode(Id).Children)
310	PostorderTraverse(Child);
311	PostorderIds[Id] = PostorderId;
312	++PostorderId;
313	};
314	PostorderTraverse(getRootId());
315	NodesBfs = getSubtreeBfs(*this, getRootId());
316	}
317
318	void SyntaxTree::Impl::setLeftMostDescendants() {
319	for (NodeId Leaf : Leaves) {
320	getMutableNode(Leaf).LeftMostDescendant = Leaf;
321	NodeId Parent, Cur = Leaf;
322	while ((Parent = getNode(Cur).Parent).isValid() &&
323	getNode(Parent).Children[0] == Cur) {
324	Cur = Parent;
325	getMutableNode(Cur).LeftMostDescendant = Leaf;
326	}
327	}
328	}
329
330	int SyntaxTree::Impl::getNumberOfDescendants(NodeId Id) const {
331	return getNode(Id).RightMostDescendant - Id + 1;
332	}
333
334	bool SyntaxTree::Impl::isInSubtree(NodeId Id, NodeId SubtreeRoot) const {
335	return Id >= SubtreeRoot && Id <= getNode(SubtreeRoot).RightMostDescendant;
336	}
337
338	int SyntaxTree::Impl::findPositionInParent(NodeId Id, bool Shifted) const {
339	NodeId Parent = getNode(Id).Parent;
340	if (Parent.isInvalid())
341	return 0;
342	const auto &Siblings = getNode(Parent).Children;
343	int Position = 0;
344	for (size_t I = 0, E = Siblings.size(); I < E; ++I) {
345	if (Shifted)
346	Position += getNode(Siblings[I]).Shift;
347	if (Siblings[I] == Id) {
348	Position += I;
349	return Position;
350	}
351	}
352	llvm_unreachable("Node not found in parent's children.");
353	}
354
355	// Returns the qualified name of ND. If it is subordinate to Context,
356	// then the prefix of the latter is removed from the returned value.
357	std::string
358	SyntaxTree::Impl::getRelativeName(const NamedDecl *ND,
359	const DeclContext *Context) const {
360	std::string Val = ND->getQualifiedNameAsString();
361	std::string ContextPrefix;
362	if (!Context)
363	return Val;
364	if (auto *Namespace = dyn_cast<NamespaceDecl>(Context))
365	ContextPrefix = Namespace->getQualifiedNameAsString();
366	else if (auto *Record = dyn_cast<RecordDecl>(Context))
367	ContextPrefix = Record->getQualifiedNameAsString();
368	else if (AST.getLangOpts().CPlusPlus11)
369	if (auto *Tag = dyn_cast<TagDecl>(Context))
370	ContextPrefix = Tag->getQualifiedNameAsString();
371	// Strip the qualifier, if Val refers to something in the current scope.
372	// But leave one leading ':' in place, so that we know that this is a
373	// relative path.
374	if (!ContextPrefix.empty() && StringRef(Val).startswith(ContextPrefix))
375	Val = Val.substr(ContextPrefix.size() + 1);
376	return Val;
377	}
378
379	std::string SyntaxTree::Impl::getRelativeName(const NamedDecl *ND) const {
380	return getRelativeName(ND, ND->getDeclContext());
381	}
382
383	static const DeclContext *getEnclosingDeclContext(ASTContext &AST,
384	const Stmt *S) {
385	while (S) {
386	const auto &Parents = AST.getParents(*S);
387	if (Parents.empty())
388	return nullptr;
389	const auto &P = Parents[0];
390	if (const auto *D = P.get<Decl>())
391	return D->getDeclContext();
392	S = P.get<Stmt>();
393	}
394	return nullptr;
395	}
396
397	static std::string getInitializerValue(const CXXCtorInitializer *Init,
398	const PrintingPolicy &TypePP) {
399	if (Init->isAnyMemberInitializer())
400	return Init->getAnyMember()->getName();
401	if (Init->isBaseInitializer())
402	return QualType(Init->getBaseClass(), 0).getAsString(TypePP);
403	if (Init->isDelegatingInitializer())
404	return Init->getTypeSourceInfo()->getType().getAsString(TypePP);
405	llvm_unreachable("Unknown initializer type");
406	}
407
408	std::string SyntaxTree::Impl::getNodeValue(NodeId Id) const {
409	return getNodeValue(getNode(Id));
410	}
411
412	std::string SyntaxTree::Impl::getNodeValue(const Node &N) const {
413	const DynTypedNode &DTN = N.ASTNode;
414	if (auto *S = DTN.get<Stmt>())
415	return getStmtValue(S);
416	if (auto *D = DTN.get<Decl>())
417	return getDeclValue(D);
418	if (auto *Init = DTN.get<CXXCtorInitializer>())
419	return getInitializerValue(Init, TypePP);
420	llvm_unreachable("Fatal: unhandled AST node.\n");
421	}
422
423	std::string SyntaxTree::Impl::getDeclValue(const Decl *D) const {
424	std::string Value;
425	if (auto *V = dyn_cast<ValueDecl>(D))
426	return getRelativeName(V) + "(" + V->getType().getAsString(TypePP) + ")";
427	if (auto *N = dyn_cast<NamedDecl>(D))
428	Value += getRelativeName(N) + ";";
429	if (auto *T = dyn_cast<TypedefNameDecl>(D))
430	return Value + T->getUnderlyingType().getAsString(TypePP) + ";";
431	if (auto *T = dyn_cast<TypeDecl>(D))
432	if (T->getTypeForDecl())
433	Value +=
434	T->getTypeForDecl()->getCanonicalTypeInternal().getAsString(TypePP) +
435	";";
436	if (auto *U = dyn_cast<UsingDirectiveDecl>(D))
437	return U->getNominatedNamespace()->getName();
438	if (auto *A = dyn_cast<AccessSpecDecl>(D)) {
439	CharSourceRange Range(A->getSourceRange(), false);
440	return Lexer::getSourceText(Range, AST.getSourceManager(),
441	AST.getLangOpts());
442	}
443	return Value;
444	}
445
446	std::string SyntaxTree::Impl::getStmtValue(const Stmt *S) const {
447	if (auto *U = dyn_cast<UnaryOperator>(S))
448	return UnaryOperator::getOpcodeStr(U->getOpcode());
449	if (auto *B = dyn_cast<BinaryOperator>(S))
450	return B->getOpcodeStr();
451	if (auto *M = dyn_cast<MemberExpr>(S))
452	return getRelativeName(M->getMemberDecl());
453	if (auto *I = dyn_cast<IntegerLiteral>(S)) {
454	SmallString<256> Str;
455	I->getValue().toString(Str, /Radix=/10, /Signed=/false);
456	return Str.str();
457	}
458	if (auto *F = dyn_cast<FloatingLiteral>(S)) {
459	SmallString<256> Str;
460	F->getValue().toString(Str);
461	return Str.str();
462	}
463	if (auto *D = dyn_cast<DeclRefExpr>(S))
464	return getRelativeName(D->getDecl(), getEnclosingDeclContext(AST, S));
465	if (auto *String = dyn_cast<StringLiteral>(S))
466	return String->getString();
467	if (auto *B = dyn_cast<CXXBoolLiteralExpr>(S))
468	return B->getValue() ? "true" : "false";
469	return "";
470	}
471
472	/// Identifies a node in a subtree by its postorder offset, starting at 1.
473	struct SNodeId {
474	int Id = 0;
475
476	explicit SNodeId(int Id) : Id(Id) {}
477	explicit SNodeId() = default;
478
479	operator int() const { return Id; }
480	SNodeId &operator++() { return ++Id, *this; }
481	SNodeId &operator--() { return --Id, *this; }
482	SNodeId operator+(int Other) const { return SNodeId(Id + Other); }
483	};
484
485	class Subtree {
486	private:
487	/// The parent tree.
488	const SyntaxTree::Impl &Tree;
489	/// Maps SNodeIds to original ids.
490	std::vector<NodeId> RootIds;
491	/// Maps subtree nodes to their leftmost descendants wtihin the subtree.
492	std::vector<SNodeId> LeftMostDescendants;
493
494	public:
495	std::vector<SNodeId> KeyRoots;
496
497	Subtree(const SyntaxTree::Impl &Tree, NodeId SubtreeRoot) : Tree(Tree) {
498	RootIds = getSubtreePostorder(Tree, SubtreeRoot);
499	int NumLeaves = setLeftMostDescendants();
500	computeKeyRoots(NumLeaves);
501	}
502	int getSize() const { return RootIds.size(); }
503	NodeId getIdInRoot(SNodeId Id) const {
504	(0) . __assert_fail ("Id > 0 && Id <= getSize() && \"Invalid subtree node index.\"", "/home/seafit/code_projects/clang_source/clang/lib/Tooling/ASTDiff/ASTDiff.cpp", 504, __PRETTY_FUNCTION__))" file_link="../../../../include/assert.h.html#88" macro="true">assert(Id > 0 && Id <= getSize() && "Invalid subtree node index.");
505	return RootIds[Id - 1];
506	}
507	const Node &getNode(SNodeId Id) const {
508	return Tree.getNode(getIdInRoot(Id));
509	}
510	SNodeId getLeftMostDescendant(SNodeId Id) const {
511	(0) . __assert_fail ("Id > 0 && Id <= getSize() && \"Invalid subtree node index.\"", "/home/seafit/code_projects/clang_source/clang/lib/Tooling/ASTDiff/ASTDiff.cpp", 511, __PRETTY_FUNCTION__))" file_link="../../../../include/assert.h.html#88" macro="true">assert(Id > 0 && Id <= getSize() && "Invalid subtree node index.");
512	return LeftMostDescendants[Id - 1];
513	}
514	/// Returns the postorder index of the leftmost descendant in the subtree.
515	NodeId getPostorderOffset() const {
516	return Tree.PostorderIds[getIdInRoot(SNodeId(1))];
517	}
518	std::string getNodeValue(SNodeId Id) const {
519	return Tree.getNodeValue(getIdInRoot(Id));
520	}
521
522	private:
523	/// Returns the number of leafs in the subtree.
524	int setLeftMostDescendants() {
525	int NumLeaves = 0;
526	LeftMostDescendants.resize(getSize());
527	for (int I = 0; I < getSize(); ++I) {
528	SNodeId SI(I + 1);
529	const Node &N = getNode(SI);
530	NumLeaves += N.isLeaf();
531	(0) . __assert_fail ("I == Tree.PostorderIds[getIdInRoot(SI)] - getPostorderOffset() && \"Postorder traversal in subtree should correspond to traversal in \" \"the root tree by a constant offset.\"", "/home/seafit/code_projects/clang_source/clang/lib/Tooling/ASTDiff/ASTDiff.cpp", 533, __PRETTY_FUNCTION__))" file_link="../../../../include/assert.h.html#88" macro="true">assert(I == Tree.PostorderIds[getIdInRoot(SI)] - getPostorderOffset() &&
532	(0) . __assert_fail ("I == Tree.PostorderIds[getIdInRoot(SI)] - getPostorderOffset() && \"Postorder traversal in subtree should correspond to traversal in \" \"the root tree by a constant offset.\"", "/home/seafit/code_projects/clang_source/clang/lib/Tooling/ASTDiff/ASTDiff.cpp", 533, __PRETTY_FUNCTION__))" file_link="../../../../include/assert.h.html#88" macro="true"> "Postorder traversal in subtree should correspond to traversal in "
533	(0) . __assert_fail ("I == Tree.PostorderIds[getIdInRoot(SI)] - getPostorderOffset() && \"Postorder traversal in subtree should correspond to traversal in \" \"the root tree by a constant offset.\"", "/home/seafit/code_projects/clang_source/clang/lib/Tooling/ASTDiff/ASTDiff.cpp", 533, __PRETTY_FUNCTION__))" file_link="../../../../include/assert.h.html#88" macro="true"> "the root tree by a constant offset.");
534	LeftMostDescendants[I] = SNodeId(Tree.PostorderIds[N.LeftMostDescendant] -
535	getPostorderOffset());
536	}
537	return NumLeaves;
538	}
539	void computeKeyRoots(int Leaves) {
540	KeyRoots.resize(Leaves);
541	std::unordered_set<int> Visited;
542	int K = Leaves - 1;
543	for (SNodeId I(getSize()); I > 0; --I) {
544	SNodeId LeftDesc = getLeftMostDescendant(I);
545	if (Visited.count(LeftDesc))
546	continue;
547	(0) . __assert_fail ("K >= 0 && \"K should be non-negative\"", "/home/seafit/code_projects/clang_source/clang/lib/Tooling/ASTDiff/ASTDiff.cpp", 547, __PRETTY_FUNCTION__))" file_link="../../../../include/assert.h.html#88" macro="true">assert(K >= 0 && "K should be non-negative");
548	KeyRoots[K] = I;
549	Visited.insert(LeftDesc);
550	--K;
551	}
552	}
553	};
554
555	/// Implementation of Zhang and Shasha's Algorithm for tree edit distance.
556	/// Computes an optimal mapping between two trees using only insertion,
557	/// deletion and update as edit actions (similar to the Levenshtein distance).
558	class ZhangShashaMatcher {
559	const ASTDiff::Impl &DiffImpl;
560	Subtree S1;
561	Subtree S2;
562	std::unique_ptr<std::unique_ptr<double[]>[]> TreeDist, ForestDist;
563
564	public:
565	ZhangShashaMatcher(const ASTDiff::Impl &DiffImpl, const SyntaxTree::Impl &T1,
566	const SyntaxTree::Impl &T2, NodeId Id1, NodeId Id2)
567	: DiffImpl(DiffImpl), S1(T1, Id1), S2(T2, Id2) {
568	TreeDist = llvm::make_unique<std::unique_ptr<double[]>[]>(
569	size_t(S1.getSize()) + 1);
570	ForestDist = llvm::make_unique<std::unique_ptr<double[]>[]>(
571	size_t(S1.getSize()) + 1);
572	for (int I = 0, E = S1.getSize() + 1; I < E; ++I) {
573	TreeDist[I] = llvm::make_unique<double[]>(size_t(S2.getSize()) + 1);
574	ForestDist[I] = llvm::make_unique<double[]>(size_t(S2.getSize()) + 1);
575	}
576	}
577
578	std::vector<std::pair<NodeId, NodeId>> getMatchingNodes() {
579	std::vector<std::pair<NodeId, NodeId>> Matches;
580	std::vector<std::pair<SNodeId, SNodeId>> TreePairs;
581
582	computeTreeDist();
583
584	bool RootNodePair = true;
585
586	TreePairs.emplace_back(SNodeId(S1.getSize()), SNodeId(S2.getSize()));
587
588	while (!TreePairs.empty()) {
589	SNodeId LastRow, LastCol, FirstRow, FirstCol, Row, Col;
590	std::tie(LastRow, LastCol) = TreePairs.back();
591	TreePairs.pop_back();
592
593	if (!RootNodePair) {
594	computeForestDist(LastRow, LastCol);
595	}
596
597	RootNodePair = false;
598
599	FirstRow = S1.getLeftMostDescendant(LastRow);
600	FirstCol = S2.getLeftMostDescendant(LastCol);
601
602	Row = LastRow;
603	Col = LastCol;
604
605	while (Row > FirstRow \|\| Col > FirstCol) {
606	if (Row > FirstRow &&
607	ForestDist[Row - 1][Col] + 1 == ForestDist[Row][Col]) {
608	--Row;
609	} else if (Col > FirstCol &&
610	ForestDist[Row][Col - 1] + 1 == ForestDist[Row][Col]) {
611	--Col;
612	} else {
613	SNodeId LMD1 = S1.getLeftMostDescendant(Row);
614	SNodeId LMD2 = S2.getLeftMostDescendant(Col);
615	if (LMD1 == S1.getLeftMostDescendant(LastRow) &&
616	LMD2 == S2.getLeftMostDescendant(LastCol)) {
617	NodeId Id1 = S1.getIdInRoot(Row);
618	NodeId Id2 = S2.getIdInRoot(Col);
619	(0) . __assert_fail ("DiffImpl.isMatchingPossible(Id1, Id2) && \"These nodes must not be matched.\"", "/home/seafit/code_projects/clang_source/clang/lib/Tooling/ASTDiff/ASTDiff.cpp", 620, __PRETTY_FUNCTION__))" file_link="../../../../include/assert.h.html#88" macro="true">assert(DiffImpl.isMatchingPossible(Id1, Id2) &&
620	(0) . __assert_fail ("DiffImpl.isMatchingPossible(Id1, Id2) && \"These nodes must not be matched.\"", "/home/seafit/code_projects/clang_source/clang/lib/Tooling/ASTDiff/ASTDiff.cpp", 620, __PRETTY_FUNCTION__))" file_link="../../../../include/assert.h.html#88" macro="true"> "These nodes must not be matched.");
621	Matches.emplace_back(Id1, Id2);
622	--Row;
623	--Col;
624	} else {
625	TreePairs.emplace_back(Row, Col);
626	Row = LMD1;
627	Col = LMD2;
628	}
629	}
630	}
631	}
632	return Matches;
633	}
634
635	private:
636	/// We use a simple cost model for edit actions, which seems good enough.
637	/// Simple cost model for edit actions. This seems to make the matching
638	/// algorithm perform reasonably well.
639	/// The values range between 0 and 1, or infinity if this edit action should
640	/// always be avoided.
641	static constexpr double DeletionCost = 1;
642	static constexpr double InsertionCost = 1;
643
644	double getUpdateCost(SNodeId Id1, SNodeId Id2) {
645	if (!DiffImpl.isMatchingPossible(S1.getIdInRoot(Id1), S2.getIdInRoot(Id2)))
646	return std::numeric_limits<double>::max();
647	return S1.getNodeValue(Id1) != S2.getNodeValue(Id2);
648	}
649
650	void computeTreeDist() {
651	for (SNodeId Id1 : S1.KeyRoots)
652	for (SNodeId Id2 : S2.KeyRoots)
653	computeForestDist(Id1, Id2);
654	}
655
656	void computeForestDist(SNodeId Id1, SNodeId Id2) {
657	(0) . __assert_fail ("Id1 > 0 && Id2 > 0 && \"Expecting offsets greater than 0.\"", "/home/seafit/code_projects/clang_source/clang/lib/Tooling/ASTDiff/ASTDiff.cpp", 657, __PRETTY_FUNCTION__))" file_link="../../../../include/assert.h.html#88" macro="true">assert(Id1 > 0 && Id2 > 0 && "Expecting offsets greater than 0.");
658	SNodeId LMD1 = S1.getLeftMostDescendant(Id1);
659	SNodeId LMD2 = S2.getLeftMostDescendant(Id2);
660
661	ForestDist[LMD1][LMD2] = 0;
662	for (SNodeId D1 = LMD1 + 1; D1 <= Id1; ++D1) {
663	ForestDist[D1][LMD2] = ForestDist[D1 - 1][LMD2] + DeletionCost;
664	for (SNodeId D2 = LMD2 + 1; D2 <= Id2; ++D2) {
665	ForestDist[LMD1][D2] = ForestDist[LMD1][D2 - 1] + InsertionCost;
666	SNodeId DLMD1 = S1.getLeftMostDescendant(D1);
667	SNodeId DLMD2 = S2.getLeftMostDescendant(D2);
668	if (DLMD1 == LMD1 && DLMD2 == LMD2) {
669	double UpdateCost = getUpdateCost(D1, D2);
670	ForestDist[D1][D2] =
671	std::min({ForestDist[D1 - 1][D2] + DeletionCost,
672	ForestDist[D1][D2 - 1] + InsertionCost,
673	ForestDist[D1 - 1][D2 - 1] + UpdateCost});
674	TreeDist[D1][D2] = ForestDist[D1][D2];
675	} else {
676	ForestDist[D1][D2] =
677	std::min({ForestDist[D1 - 1][D2] + DeletionCost,
678	ForestDist[D1][D2 - 1] + InsertionCost,
679	ForestDist[DLMD1][DLMD2] + TreeDist[D1][D2]});
680	}
681	}
682	}
683	}
684	};
685
686	ast_type_traits::ASTNodeKind Node::getType() const {
687	return ASTNode.getNodeKind();
688	}
689
690	StringRef Node::getTypeLabel() const { return getType().asStringRef(); }
691
692	llvm::Optional<std::string> Node::getQualifiedIdentifier() const {
693	if (auto *ND = ASTNode.get<NamedDecl>()) {
694	if (ND->getDeclName().isIdentifier())
695	return ND->getQualifiedNameAsString();
696	}
697	return llvm::None;
698	}
699
700	llvm::Optional<StringRef> Node::getIdentifier() const {
701	if (auto *ND = ASTNode.get<NamedDecl>()) {
702	if (ND->getDeclName().isIdentifier())
703	return ND->getName();
704	}
705	return llvm::None;
706	}
707
708	namespace {
709	// Compares nodes by their depth.
710	struct HeightLess {
711	const SyntaxTree::Impl &Tree;
712	HeightLess(const SyntaxTree::Impl &Tree) : Tree(Tree) {}
713	bool operator()(NodeId Id1, NodeId Id2) const {
714	return Tree.getNode(Id1).Height < Tree.getNode(Id2).Height;
715	}
716	};
717	} // end anonymous namespace
718
719	namespace {
720	// Priority queue for nodes, sorted descendingly by their height.
721	class PriorityList {
722	const SyntaxTree::Impl &Tree;
723	HeightLess Cmp;
724	std::vector<NodeId> Container;
725	PriorityQueue<NodeId, std::vector<NodeId>, HeightLess> List;
726
727	public:
728	PriorityList(const SyntaxTree::Impl &Tree)
729	: Tree(Tree), Cmp(Tree), List(Cmp, Container) {}
730
731	void push(NodeId id) { List.push(id); }
732
733	std::vector<NodeId> pop() {
734	int Max = peekMax();
735	std::vector<NodeId> Result;
736	if (Max == 0)
737	return Result;
738	while (peekMax() == Max) {
739	Result.push_back(List.top());
740	List.pop();
741	}
742	// TODO this is here to get a stable output, not a good heuristic
743	llvm::sort(Result);
744	return Result;
745	}
746	int peekMax() const {
747	if (List.empty())
748	return 0;
749	return Tree.getNode(List.top()).Height;
750	}
751	void open(NodeId Id) {
752	for (NodeId Child : Tree.getNode(Id).Children)
753	push(Child);
754	}
755	};
756	} // end anonymous namespace
757
758	bool ASTDiff::Impl::identical(NodeId Id1, NodeId Id2) const {
759	const Node &N1 = T1.getNode(Id1);
760	const Node &N2 = T2.getNode(Id2);
761	if (N1.Children.size() != N2.Children.size() \|\|
762	!isMatchingPossible(Id1, Id2) \|\|
763	T1.getNodeValue(Id1) != T2.getNodeValue(Id2))
764	return false;
765	for (size_t Id = 0, E = N1.Children.size(); Id < E; ++Id)
766	if (!identical(N1.Children[Id], N2.Children[Id]))
767	return false;
768	return true;
769	}
770
771	bool ASTDiff::Impl::isMatchingPossible(NodeId Id1, NodeId Id2) const {
772	return Options.isMatchingAllowed(T1.getNode(Id1), T2.getNode(Id2));
773	}
774
775	bool ASTDiff::Impl::haveSameParents(const Mapping &M, NodeId Id1,
776	NodeId Id2) const {
777	NodeId P1 = T1.getNode(Id1).Parent;
778	NodeId P2 = T2.getNode(Id2).Parent;
779	return (P1.isInvalid() && P2.isInvalid()) \|\|
780	(P1.isValid() && P2.isValid() && M.getDst(P1) == P2);
781	}
782
783	void ASTDiff::Impl::addOptimalMapping(Mapping &M, NodeId Id1,
784	NodeId Id2) const {
785	if (std::max(T1.getNumberOfDescendants(Id1), T2.getNumberOfDescendants(Id2)) >
786	Options.MaxSize)
787	return;
788	ZhangShashaMatcher Matcher(*this, T1, T2, Id1, Id2);
789	std::vector<std::pair<NodeId, NodeId>> R = Matcher.getMatchingNodes();
790	for (const auto Tuple : R) {
791	NodeId Src = Tuple.first;
792	NodeId Dst = Tuple.second;
793	if (!M.hasSrc(Src) && !M.hasDst(Dst))
794	M.link(Src, Dst);
795	}
796	}
797
798	double ASTDiff::Impl::getJaccardSimilarity(const Mapping &M, NodeId Id1,
799	NodeId Id2) const {
800	int CommonDescendants = 0;
801	const Node &N1 = T1.getNode(Id1);
802	// Count the common descendants, excluding the subtree root.
803	for (NodeId Src = Id1 + 1; Src <= N1.RightMostDescendant; ++Src) {
804	NodeId Dst = M.getDst(Src);
805	CommonDescendants += int(Dst.isValid() && T2.isInSubtree(Dst, Id2));
806	}
807	// We need to subtract 1 to get the number of descendants excluding the root.
808	double Denominator = T1.getNumberOfDescendants(Id1) - 1 +
809	T2.getNumberOfDescendants(Id2) - 1 - CommonDescendants;
810	// CommonDescendants is less than the size of one subtree.
811	(0) . __assert_fail ("Denominator >= 0 && \"Expected non-negative denominator.\"", "/home/seafit/code_projects/clang_source/clang/lib/Tooling/ASTDiff/ASTDiff.cpp", 811, __PRETTY_FUNCTION__))" file_link="../../../../include/assert.h.html#88" macro="true">assert(Denominator >= 0 && "Expected non-negative denominator.");
812	if (Denominator == 0)
813	return 0;
814	return CommonDescendants / Denominator;
815	}
816
817	NodeId ASTDiff::Impl::findCandidate(const Mapping &M, NodeId Id1) const {
818	NodeId Candidate;
819	double HighestSimilarity = 0.0;
820	for (NodeId Id2 : T2) {
821	if (!isMatchingPossible(Id1, Id2))
822	continue;
823	if (M.hasDst(Id2))
824	continue;
825	double Similarity = getJaccardSimilarity(M, Id1, Id2);
826	if (Similarity >= Options.MinSimilarity && Similarity > HighestSimilarity) {
827	HighestSimilarity = Similarity;
828	Candidate = Id2;
829	}
830	}
831	return Candidate;
832	}
833
834	void ASTDiff::Impl::matchBottomUp(Mapping &M) const {
835	std::vector<NodeId> Postorder = getSubtreePostorder(T1, T1.getRootId());
836	for (NodeId Id1 : Postorder) {
837	if (Id1 == T1.getRootId() && !M.hasSrc(T1.getRootId()) &&
838	!M.hasDst(T2.getRootId())) {
839	if (isMatchingPossible(T1.getRootId(), T2.getRootId())) {
840	M.link(T1.getRootId(), T2.getRootId());
841	addOptimalMapping(M, T1.getRootId(), T2.getRootId());
842	}
843	break;
844	}
845	bool Matched = M.hasSrc(Id1);
846	const Node &N1 = T1.getNode(Id1);
847	bool MatchedChildren = llvm::any_of(
848	N1.Children, [&](NodeId Child) { return M.hasSrc(Child); });
849	if (Matched \|\| !MatchedChildren)
850	continue;
851	NodeId Id2 = findCandidate(M, Id1);
852	if (Id2.isValid()) {
853	M.link(Id1, Id2);
854	addOptimalMapping(M, Id1, Id2);
855	}
856	}
857	}
858
859	Mapping ASTDiff::Impl::matchTopDown() const {
860	PriorityList L1(T1);
861	PriorityList L2(T2);
862
863	Mapping M(T1.getSize() + T2.getSize());
864
865	L1.push(T1.getRootId());
866	L2.push(T2.getRootId());
867
868	int Max1, Max2;
869	while (std::min(Max1 = L1.peekMax(), Max2 = L2.peekMax()) >
870	Options.MinHeight) {
871	if (Max1 > Max2) {
872	for (NodeId Id : L1.pop())
873	L1.open(Id);
874	continue;
875	}
876	if (Max2 > Max1) {
877	for (NodeId Id : L2.pop())
878	L2.open(Id);
879	continue;
880	}
881	std::vector<NodeId> H1, H2;
882	H1 = L1.pop();
883	H2 = L2.pop();
884	for (NodeId Id1 : H1) {
885	for (NodeId Id2 : H2) {
886	if (identical(Id1, Id2) && !M.hasSrc(Id1) && !M.hasDst(Id2)) {
887	for (int I = 0, E = T1.getNumberOfDescendants(Id1); I < E; ++I)
888	M.link(Id1 + I, Id2 + I);
889	}
890	}
891	}
892	for (NodeId Id1 : H1) {
893	if (!M.hasSrc(Id1))
894	L1.open(Id1);
895	}
896	for (NodeId Id2 : H2) {
897	if (!M.hasDst(Id2))
898	L2.open(Id2);
899	}
900	}
901	return M;
902	}
903
904	ASTDiff::Impl::Impl(SyntaxTree::Impl &T1, SyntaxTree::Impl &T2,
905	const ComparisonOptions &Options)
906	: T1(T1), T2(T2), Options(Options) {
907	computeMapping();
908	computeChangeKinds(TheMapping);
909	}
910
911	void ASTDiff::Impl::computeMapping() {
912	TheMapping = matchTopDown();
913	if (Options.StopAfterTopDown)
914	return;
915	matchBottomUp(TheMapping);
916	}
917
918	void ASTDiff::Impl::computeChangeKinds(Mapping &M) {
919	for (NodeId Id1 : T1) {
920	if (!M.hasSrc(Id1)) {
921	T1.getMutableNode(Id1).Change = Delete;
922	T1.getMutableNode(Id1).Shift -= 1;
923	}
924	}
925	for (NodeId Id2 : T2) {
926	if (!M.hasDst(Id2)) {
927	T2.getMutableNode(Id2).Change = Insert;
928	T2.getMutableNode(Id2).Shift -= 1;
929	}
930	}
931	for (NodeId Id1 : T1.NodesBfs) {
932	NodeId Id2 = M.getDst(Id1);
933	if (Id2.isInvalid())
934	continue;
935	if (!haveSameParents(M, Id1, Id2) \|\|
936	T1.findPositionInParent(Id1, true) !=
937	T2.findPositionInParent(Id2, true)) {
938	T1.getMutableNode(Id1).Shift -= 1;
939	T2.getMutableNode(Id2).Shift -= 1;
940	}
941	}
942	for (NodeId Id2 : T2.NodesBfs) {
943	NodeId Id1 = M.getSrc(Id2);
944	if (Id1.isInvalid())
945	continue;
946	Node &N1 = T1.getMutableNode(Id1);
947	Node &N2 = T2.getMutableNode(Id2);
948	if (Id1.isInvalid())
949	continue;
950	if (!haveSameParents(M, Id1, Id2) \|\|
951	T1.findPositionInParent(Id1, true) !=
952	T2.findPositionInParent(Id2, true)) {
953	N1.Change = N2.Change = Move;
954	}
955	if (T1.getNodeValue(Id1) != T2.getNodeValue(Id2)) {
956	N1.Change = N2.Change = (N1.Change == Move ? UpdateMove : Update);
957	}
958	}
959	}
960
961	ASTDiff::ASTDiff(SyntaxTree &T1, SyntaxTree &T2,
962	const ComparisonOptions &Options)
963	: DiffImpl(llvm::make_unique<Impl>(T1.TreeImpl, T2.TreeImpl, Options)) {}
964
965	ASTDiff::~ASTDiff() = default;
966
967	NodeId ASTDiff::getMapped(const SyntaxTree &SourceTree, NodeId Id) const {
968	return DiffImpl->getMapped(SourceTree.TreeImpl, Id);
969	}
970
971	SyntaxTree::SyntaxTree(ASTContext &AST)
972	: TreeImpl(llvm::make_unique<SyntaxTree::Impl>(
973	this, AST.getTranslationUnitDecl(), AST)) {}
974
975	SyntaxTree::~SyntaxTree() = default;
976
977	const ASTContext &SyntaxTree::getASTContext() const { return TreeImpl->AST; }
978
979	const Node &SyntaxTree::getNode(NodeId Id) const {
980	return TreeImpl->getNode(Id);
981	}
982
983	int SyntaxTree::getSize() const { return TreeImpl->getSize(); }
984	NodeId SyntaxTree::getRootId() const { return TreeImpl->getRootId(); }
985	SyntaxTree::PreorderIterator SyntaxTree::begin() const {
986	return TreeImpl->begin();
987	}
988	SyntaxTree::PreorderIterator SyntaxTree::end() const { return TreeImpl->end(); }
989
990	int SyntaxTree::findPositionInParent(NodeId Id) const {
991	return TreeImpl->findPositionInParent(Id);
992	}
993
994	std::pair<unsigned, unsigned>
995	SyntaxTree::getSourceRangeOffsets(const Node &N) const {
996	const SourceManager &SrcMgr = TreeImpl->AST.getSourceManager();
997	SourceRange Range = N.ASTNode.getSourceRange();
998	SourceLocation BeginLoc = Range.getBegin();
999	SourceLocation EndLoc = Lexer::getLocForEndOfToken(
1000	Range.getEnd(), /Offset=/0, SrcMgr, TreeImpl->AST.getLangOpts());
1001	if (auto *ThisExpr = N.ASTNode.get<CXXThisExpr>()) {
1002	if (ThisExpr->isImplicit())
1003	EndLoc = BeginLoc;
1004	}
1005	unsigned Begin = SrcMgr.getFileOffset(SrcMgr.getExpansionLoc(BeginLoc));
1006	unsigned End = SrcMgr.getFileOffset(SrcMgr.getExpansionLoc(EndLoc));
1007	return {Begin, End};
1008	}
1009
1010	std::string SyntaxTree::getNodeValue(NodeId Id) const {
1011	return TreeImpl->getNodeValue(Id);
1012	}
1013
1014	std::string SyntaxTree::getNodeValue(const Node &N) const {
1015	return TreeImpl->getNodeValue(N);
1016	}
1017
1018	} // end namespace diff
1019	} // end namespace clang
1020