blob: 747c67ecdcb65a7814a24b114938e4e72adea2b7 [file] [log] [blame]
Alex Lorenza75b2ca2017-07-21 12:49:28 +00001//===- ASTDiff.cpp - AST differencing implementation-----------*- C++ -*- -===//
2//
3// The LLVM Compiler Infrastructure
4//
5// This file is distributed under the University of Illinois Open Source
6// License. See LICENSE.TXT for details.
7//
8//===----------------------------------------------------------------------===//
9//
10// This file contains definitons for the AST differencing interface.
11//
12//===----------------------------------------------------------------------===//
13
14#include "clang/Tooling/ASTDiff/ASTDiff.h"
15
16#include "clang/AST/RecursiveASTVisitor.h"
17#include "clang/Lex/Lexer.h"
18#include "llvm/ADT/PriorityQueue.h"
19
20#include <limits>
21#include <memory>
22#include <unordered_set>
23
24using namespace llvm;
25using namespace clang;
26
27namespace clang {
28namespace diff {
29
Johannes Altmanningerfa524d72017-08-18 16:34:15 +000030namespace {
Johannes Altmanninger8b0e0662017-08-01 20:17:40 +000031/// Maps nodes of the left tree to ones on the right, and vice versa.
32class Mapping {
33public:
34 Mapping() = default;
35 Mapping(Mapping &&Other) = default;
36 Mapping &operator=(Mapping &&Other) = default;
Johannes Altmanninger51321ae2017-08-19 17:53:01 +000037
38 Mapping(size_t Size) {
39 SrcToDst = llvm::make_unique<NodeId[]>(Size);
40 DstToSrc = llvm::make_unique<NodeId[]>(Size);
Johannes Altmanninger8b0e0662017-08-01 20:17:40 +000041 }
42
43 void link(NodeId Src, NodeId Dst) {
Johannes Altmanninger51321ae2017-08-19 17:53:01 +000044 SrcToDst[Src] = Dst, DstToSrc[Dst] = Src;
Johannes Altmanninger8b0e0662017-08-01 20:17:40 +000045 }
46
Johannes Altmanninger51321ae2017-08-19 17:53:01 +000047 NodeId getDst(NodeId Src) const { return SrcToDst[Src]; }
48 NodeId getSrc(NodeId Dst) const { return DstToSrc[Dst]; }
49 bool hasSrc(NodeId Src) const { return getDst(Src).isValid(); }
50 bool hasDst(NodeId Dst) const { return getSrc(Dst).isValid(); }
Johannes Altmanninger8b0e0662017-08-01 20:17:40 +000051
52private:
Johannes Altmanninger51321ae2017-08-19 17:53:01 +000053 std::unique_ptr<NodeId[]> SrcToDst, DstToSrc;
Johannes Altmanninger8b0e0662017-08-01 20:17:40 +000054};
Johannes Altmanningerfa524d72017-08-18 16:34:15 +000055} // end anonymous namespace
Johannes Altmanninger8b0e0662017-08-01 20:17:40 +000056
Alex Lorenza75b2ca2017-07-21 12:49:28 +000057class ASTDiff::Impl {
58public:
Johannes Altmanninger31b52d62017-08-01 20:17:46 +000059 SyntaxTree::Impl &T1, &T2;
Alex Lorenza75b2ca2017-07-21 12:49:28 +000060 Mapping TheMapping;
61
Johannes Altmanninger31b52d62017-08-01 20:17:46 +000062 Impl(SyntaxTree::Impl &T1, SyntaxTree::Impl &T2,
Johannes Altmanningere0fe5cd2017-08-19 02:56:35 +000063 const ComparisonOptions &Options);
Alex Lorenza75b2ca2017-07-21 12:49:28 +000064
65 /// Matches nodes one-by-one based on their similarity.
66 void computeMapping();
67
Johannes Altmanningere0fe5cd2017-08-19 02:56:35 +000068 // Compute Change for each node based on similarity.
69 void computeChangeKinds(Mapping &M);
Alex Lorenza75b2ca2017-07-21 12:49:28 +000070
Johannes Altmanningere0fe5cd2017-08-19 02:56:35 +000071 NodeId getMapped(const std::unique_ptr<SyntaxTree::Impl> &Tree,
72 NodeId Id) const {
73 if (&*Tree == &T1)
74 return TheMapping.getDst(Id);
75 assert(&*Tree == &T2 && "Invalid tree.");
76 return TheMapping.getSrc(Id);
77 }
Alex Lorenza75b2ca2017-07-21 12:49:28 +000078
79private:
80 // Returns true if the two subtrees are identical.
Johannes Altmanninger31b52d62017-08-01 20:17:46 +000081 bool identical(NodeId Id1, NodeId Id2) const;
Alex Lorenza75b2ca2017-07-21 12:49:28 +000082
Alex Lorenza75b2ca2017-07-21 12:49:28 +000083 // Returns false if the nodes must not be mached.
84 bool isMatchingPossible(NodeId Id1, NodeId Id2) const;
85
Johannes Altmanningere0fe5cd2017-08-19 02:56:35 +000086 // Returns true if the nodes' parents are matched.
87 bool haveSameParents(const Mapping &M, NodeId Id1, NodeId Id2) const;
88
Alex Lorenza75b2ca2017-07-21 12:49:28 +000089 // Uses an optimal albeit slow algorithm to compute a mapping between two
90 // subtrees, but only if both have fewer nodes than MaxSize.
91 void addOptimalMapping(Mapping &M, NodeId Id1, NodeId Id2) const;
92
93 // Computes the ratio of common descendants between the two nodes.
94 // Descendants are only considered to be equal when they are mapped in M.
Johannes Altmanningerd1969302017-08-20 12:09:07 +000095 double getJaccardSimilarity(const Mapping &M, NodeId Id1, NodeId Id2) const;
Alex Lorenza75b2ca2017-07-21 12:49:28 +000096
97 // Returns the node that has the highest degree of similarity.
98 NodeId findCandidate(const Mapping &M, NodeId Id1) const;
99
Johannes Altmanningere0fe5cd2017-08-19 02:56:35 +0000100 // Returns a mapping of identical subtrees.
101 Mapping matchTopDown() const;
102
Alex Lorenza75b2ca2017-07-21 12:49:28 +0000103 // Tries to match any yet unmapped nodes, in a bottom-up fashion.
104 void matchBottomUp(Mapping &M) const;
105
106 const ComparisonOptions &Options;
107
108 friend class ZhangShashaMatcher;
109};
110
Johannes Altmanninger8b0e0662017-08-01 20:17:40 +0000111/// Represents the AST of a TranslationUnit.
Johannes Altmanninger31b52d62017-08-01 20:17:46 +0000112class SyntaxTree::Impl {
Johannes Altmanninger8b0e0662017-08-01 20:17:40 +0000113public:
Johannes Altmanninger8b0e0662017-08-01 20:17:40 +0000114 /// Constructs a tree from an AST node.
Johannes Altmanninger2b955ff2017-08-22 08:56:26 +0000115 Impl(SyntaxTree *Parent, Decl *N, ASTContext &AST);
116 Impl(SyntaxTree *Parent, Stmt *N, ASTContext &AST);
Johannes Altmanninger8b0e0662017-08-01 20:17:40 +0000117 template <class T>
Johannes Altmanninger31b52d62017-08-01 20:17:46 +0000118 Impl(SyntaxTree *Parent,
119 typename std::enable_if<std::is_base_of<Stmt, T>::value, T>::type *Node,
Johannes Altmanninger2b955ff2017-08-22 08:56:26 +0000120 ASTContext &AST)
Johannes Altmanninger31b52d62017-08-01 20:17:46 +0000121 : Impl(Parent, dyn_cast<Stmt>(Node), AST) {}
Johannes Altmanninger8b0e0662017-08-01 20:17:40 +0000122 template <class T>
Johannes Altmanninger31b52d62017-08-01 20:17:46 +0000123 Impl(SyntaxTree *Parent,
124 typename std::enable_if<std::is_base_of<Decl, T>::value, T>::type *Node,
Johannes Altmanninger2b955ff2017-08-22 08:56:26 +0000125 ASTContext &AST)
Johannes Altmanninger31b52d62017-08-01 20:17:46 +0000126 : Impl(Parent, dyn_cast<Decl>(Node), AST) {}
Johannes Altmanninger8b0e0662017-08-01 20:17:40 +0000127
128 SyntaxTree *Parent;
Johannes Altmanninger2b955ff2017-08-22 08:56:26 +0000129 ASTContext &AST;
Johannes Altmanninger8b0e0662017-08-01 20:17:40 +0000130 std::vector<NodeId> Leaves;
131 // Maps preorder indices to postorder ones.
132 std::vector<int> PostorderIds;
Johannes Altmanningere0fe5cd2017-08-19 02:56:35 +0000133 std::vector<NodeId> NodesBfs;
Johannes Altmanninger8b0e0662017-08-01 20:17:40 +0000134
135 int getSize() const { return Nodes.size(); }
Johannes Altmanninger31b52d62017-08-01 20:17:46 +0000136 NodeId getRootId() const { return 0; }
Johannes Altmanningere0fe5cd2017-08-19 02:56:35 +0000137 PreorderIterator begin() const { return getRootId(); }
138 PreorderIterator end() const { return getSize(); }
Johannes Altmanninger8b0e0662017-08-01 20:17:40 +0000139
140 const Node &getNode(NodeId Id) const { return Nodes[Id]; }
141 Node &getMutableNode(NodeId Id) { return Nodes[Id]; }
142 bool isValidNodeId(NodeId Id) const { return Id >= 0 && Id < getSize(); }
143 void addNode(Node &N) { Nodes.push_back(N); }
144 int getNumberOfDescendants(NodeId Id) const;
145 bool isInSubtree(NodeId Id, NodeId SubtreeRoot) const;
Johannes Altmanningere0fe5cd2017-08-19 02:56:35 +0000146 int findPositionInParent(NodeId Id, bool Shifted = false) const;
Johannes Altmanninger8b0e0662017-08-01 20:17:40 +0000147
Johannes Altmanninger2b955ff2017-08-22 08:56:26 +0000148 std::string getRelativeName(const NamedDecl *ND,
149 const DeclContext *Context) const;
150 std::string getRelativeName(const NamedDecl *ND) const;
151
Johannes Altmanninger31b52d62017-08-01 20:17:46 +0000152 std::string getNodeValue(NodeId Id) const;
Johannes Altmanningere0fe5cd2017-08-19 02:56:35 +0000153 std::string getNodeValue(const Node &Node) const;
Johannes Altmanninger0dd86dc2017-08-20 16:18:43 +0000154 std::string getDeclValue(const Decl *D) const;
155 std::string getStmtValue(const Stmt *S) const;
Johannes Altmanninger8b0e0662017-08-01 20:17:40 +0000156
Johannes Altmanninger8b0e0662017-08-01 20:17:40 +0000157private:
158 /// Nodes in preorder.
159 std::vector<Node> Nodes;
160
161 void initTree();
162 void setLeftMostDescendants();
163};
164
Johannes Altmanningerd5b56a82017-08-20 10:22:32 +0000165static bool isSpecializedNodeExcluded(const Decl *D) { return D->isImplicit(); }
166static bool isSpecializedNodeExcluded(const Stmt *S) { return false; }
167
Alex Lorenza75b2ca2017-07-21 12:49:28 +0000168template <class T>
169static bool isNodeExcluded(const SourceManager &SrcMgr, T *N) {
170 if (!N)
171 return true;
172 SourceLocation SLoc = N->getLocStart();
Johannes Altmanningerd5b56a82017-08-20 10:22:32 +0000173 if (SLoc.isValid()) {
174 // Ignore everything from other files.
175 if (!SrcMgr.isInMainFile(SLoc))
176 return true;
177 // Ignore macros.
178 if (SLoc != SrcMgr.getSpellingLoc(SLoc))
179 return true;
180 }
181 return isSpecializedNodeExcluded(N);
Alex Lorenza75b2ca2017-07-21 12:49:28 +0000182}
183
184namespace {
185/// Counts the number of nodes that will be compared.
186struct NodeCountVisitor : public RecursiveASTVisitor<NodeCountVisitor> {
187 int Count = 0;
Johannes Altmanninger31b52d62017-08-01 20:17:46 +0000188 const SyntaxTree::Impl &Tree;
189 NodeCountVisitor(const SyntaxTree::Impl &Tree) : Tree(Tree) {}
Alex Lorenza75b2ca2017-07-21 12:49:28 +0000190 bool TraverseDecl(Decl *D) {
Johannes Altmanninger31b52d62017-08-01 20:17:46 +0000191 if (isNodeExcluded(Tree.AST.getSourceManager(), D))
Alex Lorenza75b2ca2017-07-21 12:49:28 +0000192 return true;
193 ++Count;
194 RecursiveASTVisitor<NodeCountVisitor>::TraverseDecl(D);
195 return true;
196 }
197 bool TraverseStmt(Stmt *S) {
Johannes Altmanningerd5b56a82017-08-20 10:22:32 +0000198 if (S)
199 S = S->IgnoreImplicit();
Johannes Altmanninger31b52d62017-08-01 20:17:46 +0000200 if (isNodeExcluded(Tree.AST.getSourceManager(), S))
Alex Lorenza75b2ca2017-07-21 12:49:28 +0000201 return true;
202 ++Count;
203 RecursiveASTVisitor<NodeCountVisitor>::TraverseStmt(S);
204 return true;
205 }
206 bool TraverseType(QualType T) { return true; }
207};
208} // end anonymous namespace
209
210namespace {
211// Sets Height, Parent and Children for each node.
212struct PreorderVisitor : public RecursiveASTVisitor<PreorderVisitor> {
213 int Id = 0, Depth = 0;
214 NodeId Parent;
Johannes Altmanninger31b52d62017-08-01 20:17:46 +0000215 SyntaxTree::Impl &Tree;
Alex Lorenza75b2ca2017-07-21 12:49:28 +0000216
Johannes Altmanninger31b52d62017-08-01 20:17:46 +0000217 PreorderVisitor(SyntaxTree::Impl &Tree) : Tree(Tree) {}
Alex Lorenza75b2ca2017-07-21 12:49:28 +0000218
219 template <class T> std::tuple<NodeId, NodeId> PreTraverse(T *ASTNode) {
220 NodeId MyId = Id;
Johannes Altmanninger31b52d62017-08-01 20:17:46 +0000221 Node &N = Tree.getMutableNode(MyId);
Alex Lorenza75b2ca2017-07-21 12:49:28 +0000222 N.Parent = Parent;
223 N.Depth = Depth;
224 N.ASTNode = DynTypedNode::create(*ASTNode);
225 assert(!N.ASTNode.getNodeKind().isNone() &&
226 "Expected nodes to have a valid kind.");
227 if (Parent.isValid()) {
Johannes Altmanninger31b52d62017-08-01 20:17:46 +0000228 Node &P = Tree.getMutableNode(Parent);
Alex Lorenza75b2ca2017-07-21 12:49:28 +0000229 P.Children.push_back(MyId);
230 }
231 Parent = MyId;
232 ++Id;
233 ++Depth;
Johannes Altmanninger31b52d62017-08-01 20:17:46 +0000234 return std::make_tuple(MyId, Tree.getNode(MyId).Parent);
Alex Lorenza75b2ca2017-07-21 12:49:28 +0000235 }
236 void PostTraverse(std::tuple<NodeId, NodeId> State) {
237 NodeId MyId, PreviousParent;
238 std::tie(MyId, PreviousParent) = State;
239 assert(MyId.isValid() && "Expecting to only traverse valid nodes.");
240 Parent = PreviousParent;
241 --Depth;
Johannes Altmanninger31b52d62017-08-01 20:17:46 +0000242 Node &N = Tree.getMutableNode(MyId);
Johannes Altmanningerfa524d72017-08-18 16:34:15 +0000243 N.RightMostDescendant = Id - 1;
244 assert(N.RightMostDescendant >= 0 &&
245 N.RightMostDescendant < Tree.getSize() &&
246 "Rightmost descendant must be a valid tree node.");
Alex Lorenza75b2ca2017-07-21 12:49:28 +0000247 if (N.isLeaf())
Johannes Altmanninger31b52d62017-08-01 20:17:46 +0000248 Tree.Leaves.push_back(MyId);
Alex Lorenza75b2ca2017-07-21 12:49:28 +0000249 N.Height = 1;
250 for (NodeId Child : N.Children)
Johannes Altmanninger31b52d62017-08-01 20:17:46 +0000251 N.Height = std::max(N.Height, 1 + Tree.getNode(Child).Height);
Alex Lorenza75b2ca2017-07-21 12:49:28 +0000252 }
253 bool TraverseDecl(Decl *D) {
Johannes Altmanninger31b52d62017-08-01 20:17:46 +0000254 if (isNodeExcluded(Tree.AST.getSourceManager(), D))
Alex Lorenza75b2ca2017-07-21 12:49:28 +0000255 return true;
256 auto SavedState = PreTraverse(D);
257 RecursiveASTVisitor<PreorderVisitor>::TraverseDecl(D);
258 PostTraverse(SavedState);
259 return true;
260 }
261 bool TraverseStmt(Stmt *S) {
Johannes Altmanningerd5b56a82017-08-20 10:22:32 +0000262 if (S)
263 S = S->IgnoreImplicit();
Johannes Altmanninger31b52d62017-08-01 20:17:46 +0000264 if (isNodeExcluded(Tree.AST.getSourceManager(), S))
Alex Lorenza75b2ca2017-07-21 12:49:28 +0000265 return true;
266 auto SavedState = PreTraverse(S);
267 RecursiveASTVisitor<PreorderVisitor>::TraverseStmt(S);
268 PostTraverse(SavedState);
269 return true;
270 }
271 bool TraverseType(QualType T) { return true; }
272};
273} // end anonymous namespace
274
Johannes Altmanninger2b955ff2017-08-22 08:56:26 +0000275SyntaxTree::Impl::Impl(SyntaxTree *Parent, Decl *N, ASTContext &AST)
Alex Lorenza75b2ca2017-07-21 12:49:28 +0000276 : Parent(Parent), AST(AST) {
277 NodeCountVisitor NodeCounter(*this);
278 NodeCounter.TraverseDecl(N);
279 Nodes.resize(NodeCounter.Count);
280 PreorderVisitor PreorderWalker(*this);
281 PreorderWalker.TraverseDecl(N);
282 initTree();
283}
284
Johannes Altmanninger2b955ff2017-08-22 08:56:26 +0000285SyntaxTree::Impl::Impl(SyntaxTree *Parent, Stmt *N, ASTContext &AST)
Alex Lorenza75b2ca2017-07-21 12:49:28 +0000286 : Parent(Parent), AST(AST) {
287 NodeCountVisitor NodeCounter(*this);
288 NodeCounter.TraverseStmt(N);
289 Nodes.resize(NodeCounter.Count);
290 PreorderVisitor PreorderWalker(*this);
291 PreorderWalker.TraverseStmt(N);
292 initTree();
293}
294
Johannes Altmanninger31b52d62017-08-01 20:17:46 +0000295static std::vector<NodeId> getSubtreePostorder(const SyntaxTree::Impl &Tree,
Alex Lorenza75b2ca2017-07-21 12:49:28 +0000296 NodeId Root) {
297 std::vector<NodeId> Postorder;
298 std::function<void(NodeId)> Traverse = [&](NodeId Id) {
299 const Node &N = Tree.getNode(Id);
300 for (NodeId Child : N.Children)
301 Traverse(Child);
302 Postorder.push_back(Id);
303 };
304 Traverse(Root);
305 return Postorder;
306}
307
Johannes Altmanninger31b52d62017-08-01 20:17:46 +0000308static std::vector<NodeId> getSubtreeBfs(const SyntaxTree::Impl &Tree,
Alex Lorenza75b2ca2017-07-21 12:49:28 +0000309 NodeId Root) {
310 std::vector<NodeId> Ids;
311 size_t Expanded = 0;
312 Ids.push_back(Root);
313 while (Expanded < Ids.size())
314 for (NodeId Child : Tree.getNode(Ids[Expanded++]).Children)
315 Ids.push_back(Child);
316 return Ids;
317}
318
Johannes Altmanningere0fe5cd2017-08-19 02:56:35 +0000319void SyntaxTree::Impl::initTree() {
320 setLeftMostDescendants();
321 int PostorderId = 0;
322 PostorderIds.resize(getSize());
323 std::function<void(NodeId)> PostorderTraverse = [&](NodeId Id) {
324 for (NodeId Child : getNode(Id).Children)
325 PostorderTraverse(Child);
326 PostorderIds[Id] = PostorderId;
327 ++PostorderId;
328 };
329 PostorderTraverse(getRootId());
330 NodesBfs = getSubtreeBfs(*this, getRootId());
331}
332
333void SyntaxTree::Impl::setLeftMostDescendants() {
334 for (NodeId Leaf : Leaves) {
335 getMutableNode(Leaf).LeftMostDescendant = Leaf;
336 NodeId Parent, Cur = Leaf;
337 while ((Parent = getNode(Cur).Parent).isValid() &&
338 getNode(Parent).Children[0] == Cur) {
339 Cur = Parent;
340 getMutableNode(Cur).LeftMostDescendant = Leaf;
341 }
342 }
343}
344
Johannes Altmanninger31b52d62017-08-01 20:17:46 +0000345int SyntaxTree::Impl::getNumberOfDescendants(NodeId Id) const {
Alex Lorenza75b2ca2017-07-21 12:49:28 +0000346 return getNode(Id).RightMostDescendant - Id + 1;
347}
348
Johannes Altmanninger31b52d62017-08-01 20:17:46 +0000349bool SyntaxTree::Impl::isInSubtree(NodeId Id, NodeId SubtreeRoot) const {
Johannes Altmanningerfa524d72017-08-18 16:34:15 +0000350 return Id >= SubtreeRoot && Id <= getNode(SubtreeRoot).RightMostDescendant;
Alex Lorenza75b2ca2017-07-21 12:49:28 +0000351}
352
Johannes Altmanningere0fe5cd2017-08-19 02:56:35 +0000353int SyntaxTree::Impl::findPositionInParent(NodeId Id, bool Shifted) const {
354 NodeId Parent = getNode(Id).Parent;
355 if (Parent.isInvalid())
356 return 0;
357 const auto &Siblings = getNode(Parent).Children;
358 int Position = 0;
359 for (size_t I = 0, E = Siblings.size(); I < E; ++I) {
360 if (Shifted)
361 Position += getNode(Siblings[I]).Shift;
362 if (Siblings[I] == Id) {
363 Position += I;
364 return Position;
365 }
366 }
367 llvm_unreachable("Node not found in parent's children.");
Johannes Altmanninger69774d62017-08-18 21:26:34 +0000368}
369
Johannes Altmanninger2b955ff2017-08-22 08:56:26 +0000370// Returns the qualified name of ND. If it is subordinate to Context,
371// then the prefix of the latter is removed from the returned value.
372std::string
373SyntaxTree::Impl::getRelativeName(const NamedDecl *ND,
374 const DeclContext *Context) const {
Johannes Altmanningerbc7d8172017-08-22 08:59:13 +0000375 std::string Val = ND->getQualifiedNameAsString();
Johannes Altmanninger2b955ff2017-08-22 08:56:26 +0000376 std::string ContextPrefix;
Johannes Altmanningerbc7d8172017-08-22 08:59:13 +0000377 if (!Context)
378 return Val;
Johannes Altmanninger2b955ff2017-08-22 08:56:26 +0000379 if (auto *Namespace = dyn_cast<NamespaceDecl>(Context))
380 ContextPrefix = Namespace->getQualifiedNameAsString();
381 else if (auto *Record = dyn_cast<RecordDecl>(Context))
382 ContextPrefix = Record->getQualifiedNameAsString();
383 else if (AST.getLangOpts().CPlusPlus11)
384 if (auto *Tag = dyn_cast<TagDecl>(Context))
385 ContextPrefix = Tag->getQualifiedNameAsString();
Johannes Altmanninger2b955ff2017-08-22 08:56:26 +0000386 // Strip the qualifier, if Val refers to somthing in the current scope.
387 // But leave one leading ':' in place, so that we know that this is a
388 // relative path.
389 if (!ContextPrefix.empty() && StringRef(Val).startswith(ContextPrefix))
390 Val = Val.substr(ContextPrefix.size() + 1);
391 return Val;
392}
393
394std::string SyntaxTree::Impl::getRelativeName(const NamedDecl *ND) const {
395 return getRelativeName(ND, ND->getDeclContext());
396}
397
398static const DeclContext *getEnclosingDeclContext(ASTContext &AST,
399 const Stmt *S) {
400 while (S) {
401 const auto &Parents = AST.getParents(*S);
402 if (Parents.empty())
403 return nullptr;
404 const auto &P = Parents[0];
405 if (const auto *D = P.get<Decl>())
406 return D->getDeclContext();
407 S = P.get<Stmt>();
408 }
Johannes Altmanningerbc7d8172017-08-22 08:59:13 +0000409 return nullptr;
Johannes Altmanninger2b955ff2017-08-22 08:56:26 +0000410}
411
Johannes Altmanningere0fe5cd2017-08-19 02:56:35 +0000412std::string SyntaxTree::Impl::getNodeValue(NodeId Id) const {
413 return getNodeValue(getNode(Id));
414}
415
416std::string SyntaxTree::Impl::getNodeValue(const Node &N) const {
417 const DynTypedNode &DTN = N.ASTNode;
Johannes Altmanninger0dd86dc2017-08-20 16:18:43 +0000418 if (auto *S = DTN.get<Stmt>())
419 return getStmtValue(S);
420 if (auto *D = DTN.get<Decl>())
421 return getDeclValue(D);
422 llvm_unreachable("Fatal: unhandled AST node.\n");
423}
424
425std::string SyntaxTree::Impl::getDeclValue(const Decl *D) const {
426 std::string Value;
427 PrintingPolicy TypePP(AST.getLangOpts());
428 TypePP.AnonymousTagLocations = false;
429
430 if (auto *V = dyn_cast<ValueDecl>(D)) {
Johannes Altmanninger2b955ff2017-08-22 08:56:26 +0000431 Value += getRelativeName(V) + "(" + V->getType().getAsString(TypePP) + ")";
Johannes Altmanninger0dd86dc2017-08-20 16:18:43 +0000432 if (auto *C = dyn_cast<CXXConstructorDecl>(D)) {
433 for (auto *Init : C->inits()) {
434 if (!Init->isWritten())
435 continue;
436 if (Init->isBaseInitializer()) {
437 Value += Init->getBaseClass()->getCanonicalTypeInternal().getAsString(
438 TypePP);
439 } else if (Init->isDelegatingInitializer()) {
440 Value += C->getNameAsString();
441 } else {
442 assert(Init->isAnyMemberInitializer());
Johannes Altmanninger2b955ff2017-08-22 08:56:26 +0000443 Value += getRelativeName(Init->getMember());
Johannes Altmanninger0dd86dc2017-08-20 16:18:43 +0000444 }
445 Value += ",";
446 }
447 }
448 return Value;
449 }
450 if (auto *N = dyn_cast<NamedDecl>(D))
Johannes Altmanninger2b955ff2017-08-22 08:56:26 +0000451 Value += getRelativeName(N) + ";";
Johannes Altmanninger0dd86dc2017-08-20 16:18:43 +0000452 if (auto *T = dyn_cast<TypedefNameDecl>(D))
453 return Value + T->getUnderlyingType().getAsString(TypePP) + ";";
454 if (auto *T = dyn_cast<TypeDecl>(D))
455 if (T->getTypeForDecl())
456 Value +=
457 T->getTypeForDecl()->getCanonicalTypeInternal().getAsString(TypePP) +
458 ";";
459 if (auto *U = dyn_cast<UsingDirectiveDecl>(D))
460 return U->getNominatedNamespace()->getName();
461 if (auto *A = dyn_cast<AccessSpecDecl>(D)) {
462 CharSourceRange Range(A->getSourceRange(), false);
Alex Lorenza75b2ca2017-07-21 12:49:28 +0000463 return Lexer::getSourceText(Range, AST.getSourceManager(),
464 AST.getLangOpts());
465 }
Johannes Altmanninger0dd86dc2017-08-20 16:18:43 +0000466 return Value;
467}
468
469std::string SyntaxTree::Impl::getStmtValue(const Stmt *S) const {
470 if (auto *U = dyn_cast<UnaryOperator>(S))
471 return UnaryOperator::getOpcodeStr(U->getOpcode());
472 if (auto *B = dyn_cast<BinaryOperator>(S))
473 return B->getOpcodeStr();
474 if (auto *M = dyn_cast<MemberExpr>(S))
Johannes Altmanninger2b955ff2017-08-22 08:56:26 +0000475 return getRelativeName(M->getMemberDecl());
Johannes Altmanninger0dd86dc2017-08-20 16:18:43 +0000476 if (auto *I = dyn_cast<IntegerLiteral>(S)) {
Alex Lorenza75b2ca2017-07-21 12:49:28 +0000477 SmallString<256> Str;
Johannes Altmanninger0dd86dc2017-08-20 16:18:43 +0000478 I->getValue().toString(Str, /*Radix=*/10, /*Signed=*/false);
Alex Lorenza75b2ca2017-07-21 12:49:28 +0000479 return Str.str();
480 }
Johannes Altmanninger0dd86dc2017-08-20 16:18:43 +0000481 if (auto *F = dyn_cast<FloatingLiteral>(S)) {
482 SmallString<256> Str;
483 F->getValue().toString(Str);
484 return Str.str();
Alex Lorenza75b2ca2017-07-21 12:49:28 +0000485 }
Johannes Altmanninger0dd86dc2017-08-20 16:18:43 +0000486 if (auto *D = dyn_cast<DeclRefExpr>(S))
Johannes Altmanninger2b955ff2017-08-22 08:56:26 +0000487 return getRelativeName(D->getDecl(), getEnclosingDeclContext(AST, S));
Johannes Altmanninger0dd86dc2017-08-20 16:18:43 +0000488 if (auto *String = dyn_cast<StringLiteral>(S))
489 return String->getString();
490 if (auto *B = dyn_cast<CXXBoolLiteralExpr>(S))
491 return B->getValue() ? "true" : "false";
492 return "";
Alex Lorenza75b2ca2017-07-21 12:49:28 +0000493}
494
Alex Lorenza75b2ca2017-07-21 12:49:28 +0000495/// Identifies a node in a subtree by its postorder offset, starting at 1.
496struct SNodeId {
497 int Id = 0;
498
499 explicit SNodeId(int Id) : Id(Id) {}
500 explicit SNodeId() = default;
501
502 operator int() const { return Id; }
503 SNodeId &operator++() { return ++Id, *this; }
504 SNodeId &operator--() { return --Id, *this; }
505 SNodeId operator+(int Other) const { return SNodeId(Id + Other); }
506};
507
508class Subtree {
509private:
510 /// The parent tree.
Johannes Altmanninger31b52d62017-08-01 20:17:46 +0000511 const SyntaxTree::Impl &Tree;
Alex Lorenza75b2ca2017-07-21 12:49:28 +0000512 /// Maps SNodeIds to original ids.
513 std::vector<NodeId> RootIds;
514 /// Maps subtree nodes to their leftmost descendants wtihin the subtree.
515 std::vector<SNodeId> LeftMostDescendants;
516
517public:
518 std::vector<SNodeId> KeyRoots;
519
Johannes Altmanninger31b52d62017-08-01 20:17:46 +0000520 Subtree(const SyntaxTree::Impl &Tree, NodeId SubtreeRoot) : Tree(Tree) {
Alex Lorenza75b2ca2017-07-21 12:49:28 +0000521 RootIds = getSubtreePostorder(Tree, SubtreeRoot);
522 int NumLeaves = setLeftMostDescendants();
523 computeKeyRoots(NumLeaves);
524 }
525 int getSize() const { return RootIds.size(); }
526 NodeId getIdInRoot(SNodeId Id) const {
527 assert(Id > 0 && Id <= getSize() && "Invalid subtree node index.");
528 return RootIds[Id - 1];
529 }
530 const Node &getNode(SNodeId Id) const {
531 return Tree.getNode(getIdInRoot(Id));
532 }
533 SNodeId getLeftMostDescendant(SNodeId Id) const {
534 assert(Id > 0 && Id <= getSize() && "Invalid subtree node index.");
535 return LeftMostDescendants[Id - 1];
536 }
537 /// Returns the postorder index of the leftmost descendant in the subtree.
538 NodeId getPostorderOffset() const {
539 return Tree.PostorderIds[getIdInRoot(SNodeId(1))];
540 }
Johannes Altmanninger8b0e0662017-08-01 20:17:40 +0000541 std::string getNodeValue(SNodeId Id) const {
Johannes Altmanninger31b52d62017-08-01 20:17:46 +0000542 return Tree.getNodeValue(getIdInRoot(Id));
Johannes Altmanninger8b0e0662017-08-01 20:17:40 +0000543 }
Alex Lorenza75b2ca2017-07-21 12:49:28 +0000544
545private:
546 /// Returns the number of leafs in the subtree.
547 int setLeftMostDescendants() {
548 int NumLeaves = 0;
549 LeftMostDescendants.resize(getSize());
550 for (int I = 0; I < getSize(); ++I) {
551 SNodeId SI(I + 1);
552 const Node &N = getNode(SI);
553 NumLeaves += N.isLeaf();
554 assert(I == Tree.PostorderIds[getIdInRoot(SI)] - getPostorderOffset() &&
555 "Postorder traversal in subtree should correspond to traversal in "
556 "the root tree by a constant offset.");
557 LeftMostDescendants[I] = SNodeId(Tree.PostorderIds[N.LeftMostDescendant] -
558 getPostorderOffset());
559 }
560 return NumLeaves;
561 }
562 void computeKeyRoots(int Leaves) {
563 KeyRoots.resize(Leaves);
564 std::unordered_set<int> Visited;
565 int K = Leaves - 1;
566 for (SNodeId I(getSize()); I > 0; --I) {
567 SNodeId LeftDesc = getLeftMostDescendant(I);
568 if (Visited.count(LeftDesc))
569 continue;
570 assert(K >= 0 && "K should be non-negative");
571 KeyRoots[K] = I;
572 Visited.insert(LeftDesc);
573 --K;
574 }
575 }
576};
577
578/// Implementation of Zhang and Shasha's Algorithm for tree edit distance.
579/// Computes an optimal mapping between two trees using only insertion,
580/// deletion and update as edit actions (similar to the Levenshtein distance).
581class ZhangShashaMatcher {
582 const ASTDiff::Impl &DiffImpl;
583 Subtree S1;
584 Subtree S2;
585 std::unique_ptr<std::unique_ptr<double[]>[]> TreeDist, ForestDist;
586
587public:
Johannes Altmanninger31b52d62017-08-01 20:17:46 +0000588 ZhangShashaMatcher(const ASTDiff::Impl &DiffImpl, const SyntaxTree::Impl &T1,
589 const SyntaxTree::Impl &T2, NodeId Id1, NodeId Id2)
Alex Lorenza75b2ca2017-07-21 12:49:28 +0000590 : DiffImpl(DiffImpl), S1(T1, Id1), S2(T2, Id2) {
591 TreeDist = llvm::make_unique<std::unique_ptr<double[]>[]>(
592 size_t(S1.getSize()) + 1);
593 ForestDist = llvm::make_unique<std::unique_ptr<double[]>[]>(
594 size_t(S1.getSize()) + 1);
595 for (int I = 0, E = S1.getSize() + 1; I < E; ++I) {
596 TreeDist[I] = llvm::make_unique<double[]>(size_t(S2.getSize()) + 1);
597 ForestDist[I] = llvm::make_unique<double[]>(size_t(S2.getSize()) + 1);
598 }
599 }
600
601 std::vector<std::pair<NodeId, NodeId>> getMatchingNodes() {
602 std::vector<std::pair<NodeId, NodeId>> Matches;
603 std::vector<std::pair<SNodeId, SNodeId>> TreePairs;
604
605 computeTreeDist();
606
607 bool RootNodePair = true;
608
Alex Lorenz4c0a8662017-07-21 13:04:57 +0000609 TreePairs.emplace_back(SNodeId(S1.getSize()), SNodeId(S2.getSize()));
Alex Lorenza75b2ca2017-07-21 12:49:28 +0000610
611 while (!TreePairs.empty()) {
612 SNodeId LastRow, LastCol, FirstRow, FirstCol, Row, Col;
613 std::tie(LastRow, LastCol) = TreePairs.back();
614 TreePairs.pop_back();
615
616 if (!RootNodePair) {
617 computeForestDist(LastRow, LastCol);
618 }
619
620 RootNodePair = false;
621
622 FirstRow = S1.getLeftMostDescendant(LastRow);
623 FirstCol = S2.getLeftMostDescendant(LastCol);
624
625 Row = LastRow;
626 Col = LastCol;
627
628 while (Row > FirstRow || Col > FirstCol) {
629 if (Row > FirstRow &&
630 ForestDist[Row - 1][Col] + 1 == ForestDist[Row][Col]) {
631 --Row;
632 } else if (Col > FirstCol &&
633 ForestDist[Row][Col - 1] + 1 == ForestDist[Row][Col]) {
634 --Col;
635 } else {
636 SNodeId LMD1 = S1.getLeftMostDescendant(Row);
637 SNodeId LMD2 = S2.getLeftMostDescendant(Col);
638 if (LMD1 == S1.getLeftMostDescendant(LastRow) &&
639 LMD2 == S2.getLeftMostDescendant(LastCol)) {
640 NodeId Id1 = S1.getIdInRoot(Row);
641 NodeId Id2 = S2.getIdInRoot(Col);
642 assert(DiffImpl.isMatchingPossible(Id1, Id2) &&
643 "These nodes must not be matched.");
644 Matches.emplace_back(Id1, Id2);
645 --Row;
646 --Col;
647 } else {
648 TreePairs.emplace_back(Row, Col);
649 Row = LMD1;
650 Col = LMD2;
651 }
652 }
653 }
654 }
655 return Matches;
656 }
657
658private:
Johannes Altmanningerfa524d72017-08-18 16:34:15 +0000659 /// We use a simple cost model for edit actions, which seems good enough.
660 /// Simple cost model for edit actions. This seems to make the matching
661 /// algorithm perform reasonably well.
Alex Lorenza75b2ca2017-07-21 12:49:28 +0000662 /// The values range between 0 and 1, or infinity if this edit action should
663 /// always be avoided.
Alex Lorenza75b2ca2017-07-21 12:49:28 +0000664 static constexpr double DeletionCost = 1;
665 static constexpr double InsertionCost = 1;
666
667 double getUpdateCost(SNodeId Id1, SNodeId Id2) {
Johannes Altmanninger8b0e0662017-08-01 20:17:40 +0000668 if (!DiffImpl.isMatchingPossible(S1.getIdInRoot(Id1), S2.getIdInRoot(Id2)))
Alex Lorenza75b2ca2017-07-21 12:49:28 +0000669 return std::numeric_limits<double>::max();
Johannes Altmanninger8b0e0662017-08-01 20:17:40 +0000670 return S1.getNodeValue(Id1) != S2.getNodeValue(Id2);
Alex Lorenza75b2ca2017-07-21 12:49:28 +0000671 }
672
673 void computeTreeDist() {
674 for (SNodeId Id1 : S1.KeyRoots)
675 for (SNodeId Id2 : S2.KeyRoots)
676 computeForestDist(Id1, Id2);
677 }
678
679 void computeForestDist(SNodeId Id1, SNodeId Id2) {
680 assert(Id1 > 0 && Id2 > 0 && "Expecting offsets greater than 0.");
681 SNodeId LMD1 = S1.getLeftMostDescendant(Id1);
682 SNodeId LMD2 = S2.getLeftMostDescendant(Id2);
683
684 ForestDist[LMD1][LMD2] = 0;
685 for (SNodeId D1 = LMD1 + 1; D1 <= Id1; ++D1) {
686 ForestDist[D1][LMD2] = ForestDist[D1 - 1][LMD2] + DeletionCost;
687 for (SNodeId D2 = LMD2 + 1; D2 <= Id2; ++D2) {
688 ForestDist[LMD1][D2] = ForestDist[LMD1][D2 - 1] + InsertionCost;
689 SNodeId DLMD1 = S1.getLeftMostDescendant(D1);
690 SNodeId DLMD2 = S2.getLeftMostDescendant(D2);
691 if (DLMD1 == LMD1 && DLMD2 == LMD2) {
692 double UpdateCost = getUpdateCost(D1, D2);
693 ForestDist[D1][D2] =
694 std::min({ForestDist[D1 - 1][D2] + DeletionCost,
695 ForestDist[D1][D2 - 1] + InsertionCost,
696 ForestDist[D1 - 1][D2 - 1] + UpdateCost});
697 TreeDist[D1][D2] = ForestDist[D1][D2];
698 } else {
699 ForestDist[D1][D2] =
700 std::min({ForestDist[D1 - 1][D2] + DeletionCost,
701 ForestDist[D1][D2 - 1] + InsertionCost,
702 ForestDist[DLMD1][DLMD2] + TreeDist[D1][D2]});
703 }
704 }
705 }
706 }
707};
708
Johannes Altmanninger0da12c82017-08-19 00:57:38 +0000709ast_type_traits::ASTNodeKind Node::getType() const {
710 return ASTNode.getNodeKind();
711}
712
713StringRef Node::getTypeLabel() const { return getType().asStringRef(); }
714
Johannes Altmanninger0dd86dc2017-08-20 16:18:43 +0000715llvm::Optional<std::string> Node::getQualifiedIdentifier() const {
716 if (auto *ND = ASTNode.get<NamedDecl>()) {
717 if (ND->getDeclName().isIdentifier())
718 return ND->getQualifiedNameAsString();
719 }
720 return llvm::None;
721}
722
723llvm::Optional<StringRef> Node::getIdentifier() const {
724 if (auto *ND = ASTNode.get<NamedDecl>()) {
725 if (ND->getDeclName().isIdentifier())
726 return ND->getName();
727 }
728 return llvm::None;
729}
730
Alex Lorenza75b2ca2017-07-21 12:49:28 +0000731namespace {
732// Compares nodes by their depth.
733struct HeightLess {
Johannes Altmanninger31b52d62017-08-01 20:17:46 +0000734 const SyntaxTree::Impl &Tree;
735 HeightLess(const SyntaxTree::Impl &Tree) : Tree(Tree) {}
Alex Lorenza75b2ca2017-07-21 12:49:28 +0000736 bool operator()(NodeId Id1, NodeId Id2) const {
737 return Tree.getNode(Id1).Height < Tree.getNode(Id2).Height;
738 }
739};
740} // end anonymous namespace
741
Johannes Altmanningerfa524d72017-08-18 16:34:15 +0000742namespace {
Alex Lorenza75b2ca2017-07-21 12:49:28 +0000743// Priority queue for nodes, sorted descendingly by their height.
744class PriorityList {
Johannes Altmanninger31b52d62017-08-01 20:17:46 +0000745 const SyntaxTree::Impl &Tree;
Alex Lorenza75b2ca2017-07-21 12:49:28 +0000746 HeightLess Cmp;
747 std::vector<NodeId> Container;
748 PriorityQueue<NodeId, std::vector<NodeId>, HeightLess> List;
749
750public:
Johannes Altmanninger31b52d62017-08-01 20:17:46 +0000751 PriorityList(const SyntaxTree::Impl &Tree)
Alex Lorenza75b2ca2017-07-21 12:49:28 +0000752 : Tree(Tree), Cmp(Tree), List(Cmp, Container) {}
753
754 void push(NodeId id) { List.push(id); }
755
756 std::vector<NodeId> pop() {
757 int Max = peekMax();
758 std::vector<NodeId> Result;
759 if (Max == 0)
760 return Result;
761 while (peekMax() == Max) {
762 Result.push_back(List.top());
763 List.pop();
764 }
765 // TODO this is here to get a stable output, not a good heuristic
766 std::sort(Result.begin(), Result.end());
767 return Result;
768 }
769 int peekMax() const {
770 if (List.empty())
771 return 0;
772 return Tree.getNode(List.top()).Height;
773 }
774 void open(NodeId Id) {
775 for (NodeId Child : Tree.getNode(Id).Children)
776 push(Child);
777 }
778};
Johannes Altmanningerfa524d72017-08-18 16:34:15 +0000779} // end anonymous namespace
Alex Lorenza75b2ca2017-07-21 12:49:28 +0000780
Johannes Altmanninger31b52d62017-08-01 20:17:46 +0000781bool ASTDiff::Impl::identical(NodeId Id1, NodeId Id2) const {
Alex Lorenza75b2ca2017-07-21 12:49:28 +0000782 const Node &N1 = T1.getNode(Id1);
783 const Node &N2 = T2.getNode(Id2);
784 if (N1.Children.size() != N2.Children.size() ||
785 !isMatchingPossible(Id1, Id2) ||
Johannes Altmanninger31b52d62017-08-01 20:17:46 +0000786 T1.getNodeValue(Id1) != T2.getNodeValue(Id2))
Alex Lorenza75b2ca2017-07-21 12:49:28 +0000787 return false;
788 for (size_t Id = 0, E = N1.Children.size(); Id < E; ++Id)
Johannes Altmanninger31b52d62017-08-01 20:17:46 +0000789 if (!identical(N1.Children[Id], N2.Children[Id]))
Alex Lorenza75b2ca2017-07-21 12:49:28 +0000790 return false;
791 return true;
792}
793
Alex Lorenza75b2ca2017-07-21 12:49:28 +0000794bool ASTDiff::Impl::isMatchingPossible(NodeId Id1, NodeId Id2) const {
Johannes Altmanningere0fe5cd2017-08-19 02:56:35 +0000795 return Options.isMatchingAllowed(T1.getNode(Id1), T2.getNode(Id2));
796}
797
798bool ASTDiff::Impl::haveSameParents(const Mapping &M, NodeId Id1,
799 NodeId Id2) const {
800 NodeId P1 = T1.getNode(Id1).Parent;
801 NodeId P2 = T2.getNode(Id2).Parent;
802 return (P1.isInvalid() && P2.isInvalid()) ||
803 (P1.isValid() && P2.isValid() && M.getDst(P1) == P2);
Alex Lorenza75b2ca2017-07-21 12:49:28 +0000804}
805
Alex Lorenza75b2ca2017-07-21 12:49:28 +0000806void ASTDiff::Impl::addOptimalMapping(Mapping &M, NodeId Id1,
807 NodeId Id2) const {
Johannes Altmanningerd1969302017-08-20 12:09:07 +0000808 if (std::max(T1.getNumberOfDescendants(Id1), T2.getNumberOfDescendants(Id2)) >
809 Options.MaxSize)
Alex Lorenza75b2ca2017-07-21 12:49:28 +0000810 return;
811 ZhangShashaMatcher Matcher(*this, T1, T2, Id1, Id2);
812 std::vector<std::pair<NodeId, NodeId>> R = Matcher.getMatchingNodes();
813 for (const auto Tuple : R) {
814 NodeId Src = Tuple.first;
815 NodeId Dst = Tuple.second;
Johannes Altmanninger51321ae2017-08-19 17:53:01 +0000816 if (!M.hasSrc(Src) && !M.hasDst(Dst))
Alex Lorenza75b2ca2017-07-21 12:49:28 +0000817 M.link(Src, Dst);
818 }
819}
820
Johannes Altmanningerd1969302017-08-20 12:09:07 +0000821double ASTDiff::Impl::getJaccardSimilarity(const Mapping &M, NodeId Id1,
822 NodeId Id2) const {
Alex Lorenza75b2ca2017-07-21 12:49:28 +0000823 int CommonDescendants = 0;
824 const Node &N1 = T1.getNode(Id1);
Johannes Altmanningerd1969302017-08-20 12:09:07 +0000825 // Count the common descendants, excluding the subtree root.
826 for (NodeId Src = Id1 + 1; Src <= N1.RightMostDescendant; ++Src) {
827 NodeId Dst = M.getDst(Src);
828 CommonDescendants += int(Dst.isValid() && T2.isInSubtree(Dst, Id2));
829 }
830 // We need to subtract 1 to get the number of descendants excluding the root.
831 double Denominator = T1.getNumberOfDescendants(Id1) - 1 +
832 T2.getNumberOfDescendants(Id2) - 1 - CommonDescendants;
833 // CommonDescendants is less than the size of one subtree.
834 assert(Denominator >= 0 && "Expected non-negative denominator.");
835 if (Denominator == 0)
836 return 0;
837 return CommonDescendants / Denominator;
Alex Lorenza75b2ca2017-07-21 12:49:28 +0000838}
839
840NodeId ASTDiff::Impl::findCandidate(const Mapping &M, NodeId Id1) const {
841 NodeId Candidate;
Johannes Altmanninger31b52d62017-08-01 20:17:46 +0000842 double HighestSimilarity = 0.0;
Johannes Altmanningere0fe5cd2017-08-19 02:56:35 +0000843 for (NodeId Id2 : T2) {
Alex Lorenza75b2ca2017-07-21 12:49:28 +0000844 if (!isMatchingPossible(Id1, Id2))
845 continue;
846 if (M.hasDst(Id2))
847 continue;
Johannes Altmanningerd1969302017-08-20 12:09:07 +0000848 double Similarity = getJaccardSimilarity(M, Id1, Id2);
Johannes Altmanningerfa524d72017-08-18 16:34:15 +0000849 if (Similarity >= Options.MinSimilarity && Similarity > HighestSimilarity) {
Johannes Altmanninger31b52d62017-08-01 20:17:46 +0000850 HighestSimilarity = Similarity;
Alex Lorenza75b2ca2017-07-21 12:49:28 +0000851 Candidate = Id2;
852 }
853 }
854 return Candidate;
855}
856
857void ASTDiff::Impl::matchBottomUp(Mapping &M) const {
Johannes Altmanninger31b52d62017-08-01 20:17:46 +0000858 std::vector<NodeId> Postorder = getSubtreePostorder(T1, T1.getRootId());
Alex Lorenza75b2ca2017-07-21 12:49:28 +0000859 for (NodeId Id1 : Postorder) {
Johannes Altmanningerfa524d72017-08-18 16:34:15 +0000860 if (Id1 == T1.getRootId() && !M.hasSrc(T1.getRootId()) &&
861 !M.hasDst(T2.getRootId())) {
Johannes Altmanninger31b52d62017-08-01 20:17:46 +0000862 if (isMatchingPossible(T1.getRootId(), T2.getRootId())) {
863 M.link(T1.getRootId(), T2.getRootId());
864 addOptimalMapping(M, T1.getRootId(), T2.getRootId());
Alex Lorenza75b2ca2017-07-21 12:49:28 +0000865 }
866 break;
867 }
Alex Lorenza75b2ca2017-07-21 12:49:28 +0000868 bool Matched = M.hasSrc(Id1);
Johannes Altmanningerd1969302017-08-20 12:09:07 +0000869 const Node &N1 = T1.getNode(Id1);
Alex Lorenza75b2ca2017-07-21 12:49:28 +0000870 bool MatchedChildren =
871 std::any_of(N1.Children.begin(), N1.Children.end(),
872 [&](NodeId Child) { return M.hasSrc(Child); });
873 if (Matched || !MatchedChildren)
874 continue;
875 NodeId Id2 = findCandidate(M, Id1);
Johannes Altmanninger51321ae2017-08-19 17:53:01 +0000876 if (Id2.isValid()) {
Johannes Altmanningerfa524d72017-08-18 16:34:15 +0000877 M.link(Id1, Id2);
878 addOptimalMapping(M, Id1, Id2);
879 }
Alex Lorenza75b2ca2017-07-21 12:49:28 +0000880 }
881}
882
883Mapping ASTDiff::Impl::matchTopDown() const {
884 PriorityList L1(T1);
885 PriorityList L2(T2);
886
Johannes Altmanninger51321ae2017-08-19 17:53:01 +0000887 Mapping M(T1.getSize() + T2.getSize());
Alex Lorenza75b2ca2017-07-21 12:49:28 +0000888
Johannes Altmanninger31b52d62017-08-01 20:17:46 +0000889 L1.push(T1.getRootId());
890 L2.push(T2.getRootId());
Alex Lorenza75b2ca2017-07-21 12:49:28 +0000891
892 int Max1, Max2;
893 while (std::min(Max1 = L1.peekMax(), Max2 = L2.peekMax()) >
894 Options.MinHeight) {
895 if (Max1 > Max2) {
896 for (NodeId Id : L1.pop())
897 L1.open(Id);
898 continue;
899 }
900 if (Max2 > Max1) {
901 for (NodeId Id : L2.pop())
902 L2.open(Id);
903 continue;
904 }
905 std::vector<NodeId> H1, H2;
906 H1 = L1.pop();
907 H2 = L2.pop();
908 for (NodeId Id1 : H1) {
Johannes Altmanningerfa524d72017-08-18 16:34:15 +0000909 for (NodeId Id2 : H2) {
Johannes Altmanninger51321ae2017-08-19 17:53:01 +0000910 if (identical(Id1, Id2) && !M.hasSrc(Id1) && !M.hasDst(Id2)) {
Johannes Altmanningerfa524d72017-08-18 16:34:15 +0000911 for (int I = 0, E = T1.getNumberOfDescendants(Id1); I < E; ++I)
912 M.link(Id1 + I, Id2 + I);
913 }
914 }
Alex Lorenza75b2ca2017-07-21 12:49:28 +0000915 }
916 for (NodeId Id1 : H1) {
917 if (!M.hasSrc(Id1))
918 L1.open(Id1);
919 }
920 for (NodeId Id2 : H2) {
921 if (!M.hasDst(Id2))
922 L2.open(Id2);
923 }
924 }
925 return M;
926}
927
Johannes Altmanningere0fe5cd2017-08-19 02:56:35 +0000928ASTDiff::Impl::Impl(SyntaxTree::Impl &T1, SyntaxTree::Impl &T2,
929 const ComparisonOptions &Options)
930 : T1(T1), T2(T2), Options(Options) {
931 computeMapping();
932 computeChangeKinds(TheMapping);
933}
934
Alex Lorenza75b2ca2017-07-21 12:49:28 +0000935void ASTDiff::Impl::computeMapping() {
Alex Lorenza75b2ca2017-07-21 12:49:28 +0000936 TheMapping = matchTopDown();
Johannes Altmanningerd1969302017-08-20 12:09:07 +0000937 if (Options.StopAfterTopDown)
938 return;
Alex Lorenza75b2ca2017-07-21 12:49:28 +0000939 matchBottomUp(TheMapping);
Alex Lorenza75b2ca2017-07-21 12:49:28 +0000940}
941
Johannes Altmanningere0fe5cd2017-08-19 02:56:35 +0000942void ASTDiff::Impl::computeChangeKinds(Mapping &M) {
943 for (NodeId Id1 : T1) {
944 if (!M.hasSrc(Id1)) {
945 T1.getMutableNode(Id1).Change = Delete;
946 T1.getMutableNode(Id1).Shift -= 1;
Alex Lorenza75b2ca2017-07-21 12:49:28 +0000947 }
Alex Lorenza75b2ca2017-07-21 12:49:28 +0000948 }
Johannes Altmanningere0fe5cd2017-08-19 02:56:35 +0000949 for (NodeId Id2 : T2) {
950 if (!M.hasDst(Id2)) {
951 T2.getMutableNode(Id2).Change = Insert;
952 T2.getMutableNode(Id2).Shift -= 1;
953 }
954 }
955 for (NodeId Id1 : T1.NodesBfs) {
Alex Lorenza75b2ca2017-07-21 12:49:28 +0000956 NodeId Id2 = M.getDst(Id1);
957 if (Id2.isInvalid())
Johannes Altmanningere0fe5cd2017-08-19 02:56:35 +0000958 continue;
959 if (!haveSameParents(M, Id1, Id2) ||
960 T1.findPositionInParent(Id1, true) !=
961 T2.findPositionInParent(Id2, true)) {
962 T1.getMutableNode(Id1).Shift -= 1;
963 T2.getMutableNode(Id2).Shift -= 1;
964 }
Alex Lorenza75b2ca2017-07-21 12:49:28 +0000965 }
Johannes Altmanningere0fe5cd2017-08-19 02:56:35 +0000966 for (NodeId Id2 : T2.NodesBfs) {
967 NodeId Id1 = M.getSrc(Id2);
968 if (Id1.isInvalid())
969 continue;
970 Node &N1 = T1.getMutableNode(Id1);
971 Node &N2 = T2.getMutableNode(Id2);
972 if (Id1.isInvalid())
973 continue;
974 if (!haveSameParents(M, Id1, Id2) ||
975 T1.findPositionInParent(Id1, true) !=
976 T2.findPositionInParent(Id2, true)) {
977 N1.Change = N2.Change = Move;
978 }
979 if (T1.getNodeValue(Id1) != T2.getNodeValue(Id2)) {
980 N1.Change = N2.Change = (N1.Change == Move ? UpdateMove : Update);
981 }
982 }
Alex Lorenza75b2ca2017-07-21 12:49:28 +0000983}
984
985ASTDiff::ASTDiff(SyntaxTree &T1, SyntaxTree &T2,
986 const ComparisonOptions &Options)
987 : DiffImpl(llvm::make_unique<Impl>(*T1.TreeImpl, *T2.TreeImpl, Options)) {}
988
Johannes Altmanninger31b52d62017-08-01 20:17:46 +0000989ASTDiff::~ASTDiff() = default;
Alex Lorenza75b2ca2017-07-21 12:49:28 +0000990
Johannes Altmanningere0fe5cd2017-08-19 02:56:35 +0000991NodeId ASTDiff::getMapped(const SyntaxTree &SourceTree, NodeId Id) const {
992 return DiffImpl->getMapped(SourceTree.TreeImpl, Id);
993}
994
Johannes Altmanninger2b955ff2017-08-22 08:56:26 +0000995SyntaxTree::SyntaxTree(ASTContext &AST)
Johannes Altmanninger31b52d62017-08-01 20:17:46 +0000996 : TreeImpl(llvm::make_unique<SyntaxTree::Impl>(
Alex Lorenza75b2ca2017-07-21 12:49:28 +0000997 this, AST.getTranslationUnitDecl(), AST)) {}
998
Johannes Altmanninger8b0e0662017-08-01 20:17:40 +0000999SyntaxTree::~SyntaxTree() = default;
1000
Johannes Altmanninger0da12c82017-08-19 00:57:38 +00001001const ASTContext &SyntaxTree::getASTContext() const { return TreeImpl->AST; }
1002
1003const Node &SyntaxTree::getNode(NodeId Id) const {
1004 return TreeImpl->getNode(Id);
1005}
1006
Johannes Altmanningere0fe5cd2017-08-19 02:56:35 +00001007int SyntaxTree::getSize() const { return TreeImpl->getSize(); }
Johannes Altmanninger0da12c82017-08-19 00:57:38 +00001008NodeId SyntaxTree::getRootId() const { return TreeImpl->getRootId(); }
Johannes Altmanningere0fe5cd2017-08-19 02:56:35 +00001009SyntaxTree::PreorderIterator SyntaxTree::begin() const {
1010 return TreeImpl->begin();
1011}
1012SyntaxTree::PreorderIterator SyntaxTree::end() const { return TreeImpl->end(); }
Johannes Altmanninger0da12c82017-08-19 00:57:38 +00001013
Johannes Altmanningere0fe5cd2017-08-19 02:56:35 +00001014int SyntaxTree::findPositionInParent(NodeId Id) const {
1015 return TreeImpl->findPositionInParent(Id);
1016}
1017
1018std::pair<unsigned, unsigned>
1019SyntaxTree::getSourceRangeOffsets(const Node &N) const {
Johannes Altmanninger0da12c82017-08-19 00:57:38 +00001020 const SourceManager &SrcMgr = TreeImpl->AST.getSourceManager();
1021 SourceRange Range = N.ASTNode.getSourceRange();
1022 SourceLocation BeginLoc = Range.getBegin();
1023 SourceLocation EndLoc = Lexer::getLocForEndOfToken(
1024 Range.getEnd(), /*Offset=*/0, SrcMgr, TreeImpl->AST.getLangOpts());
1025 if (auto *ThisExpr = N.ASTNode.get<CXXThisExpr>()) {
1026 if (ThisExpr->isImplicit())
1027 EndLoc = BeginLoc;
1028 }
1029 unsigned Begin = SrcMgr.getFileOffset(SrcMgr.getExpansionLoc(BeginLoc));
1030 unsigned End = SrcMgr.getFileOffset(SrcMgr.getExpansionLoc(EndLoc));
1031 return {Begin, End};
1032}
Alex Lorenza75b2ca2017-07-21 12:49:28 +00001033
Johannes Altmanningere0fe5cd2017-08-19 02:56:35 +00001034std::string SyntaxTree::getNodeValue(NodeId Id) const {
1035 return TreeImpl->getNodeValue(Id);
1036}
1037
1038std::string SyntaxTree::getNodeValue(const Node &N) const {
1039 return TreeImpl->getNodeValue(N);
Alex Lorenza75b2ca2017-07-21 12:49:28 +00001040}
1041
1042} // end namespace diff
1043} // end namespace clang