Alex Lorenz | a75b2ca | 2017-07-21 12:49:28 +0000 | [diff] [blame] | 1 | //===- 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 | |
| 24 | using namespace llvm; |
| 25 | using namespace clang; |
| 26 | |
| 27 | namespace clang { |
| 28 | namespace diff { |
| 29 | |
Johannes Altmanninger | fa524d7 | 2017-08-18 16:34:15 +0000 | [diff] [blame] | 30 | namespace { |
Johannes Altmanninger | 8b0e066 | 2017-08-01 20:17:40 +0000 | [diff] [blame] | 31 | /// Maps nodes of the left tree to ones on the right, and vice versa. |
| 32 | class Mapping { |
| 33 | public: |
| 34 | Mapping() = default; |
| 35 | Mapping(Mapping &&Other) = default; |
| 36 | Mapping &operator=(Mapping &&Other) = default; |
Johannes Altmanninger | 51321ae | 2017-08-19 17:53:01 +0000 | [diff] [blame] | 37 | |
| 38 | Mapping(size_t Size) { |
| 39 | SrcToDst = llvm::make_unique<NodeId[]>(Size); |
| 40 | DstToSrc = llvm::make_unique<NodeId[]>(Size); |
Johannes Altmanninger | 8b0e066 | 2017-08-01 20:17:40 +0000 | [diff] [blame] | 41 | } |
| 42 | |
| 43 | void link(NodeId Src, NodeId Dst) { |
Johannes Altmanninger | 51321ae | 2017-08-19 17:53:01 +0000 | [diff] [blame] | 44 | SrcToDst[Src] = Dst, DstToSrc[Dst] = Src; |
Johannes Altmanninger | 8b0e066 | 2017-08-01 20:17:40 +0000 | [diff] [blame] | 45 | } |
| 46 | |
Johannes Altmanninger | 51321ae | 2017-08-19 17:53:01 +0000 | [diff] [blame] | 47 | 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 Altmanninger | 8b0e066 | 2017-08-01 20:17:40 +0000 | [diff] [blame] | 51 | |
| 52 | private: |
Johannes Altmanninger | 51321ae | 2017-08-19 17:53:01 +0000 | [diff] [blame] | 53 | std::unique_ptr<NodeId[]> SrcToDst, DstToSrc; |
Johannes Altmanninger | 8b0e066 | 2017-08-01 20:17:40 +0000 | [diff] [blame] | 54 | }; |
Johannes Altmanninger | fa524d7 | 2017-08-18 16:34:15 +0000 | [diff] [blame] | 55 | } // end anonymous namespace |
Johannes Altmanninger | 8b0e066 | 2017-08-01 20:17:40 +0000 | [diff] [blame] | 56 | |
Alex Lorenz | a75b2ca | 2017-07-21 12:49:28 +0000 | [diff] [blame] | 57 | class ASTDiff::Impl { |
| 58 | public: |
Johannes Altmanninger | 31b52d6 | 2017-08-01 20:17:46 +0000 | [diff] [blame] | 59 | SyntaxTree::Impl &T1, &T2; |
Alex Lorenz | a75b2ca | 2017-07-21 12:49:28 +0000 | [diff] [blame] | 60 | Mapping TheMapping; |
| 61 | |
Johannes Altmanninger | 31b52d6 | 2017-08-01 20:17:46 +0000 | [diff] [blame] | 62 | Impl(SyntaxTree::Impl &T1, SyntaxTree::Impl &T2, |
Johannes Altmanninger | e0fe5cd | 2017-08-19 02:56:35 +0000 | [diff] [blame] | 63 | const ComparisonOptions &Options); |
Alex Lorenz | a75b2ca | 2017-07-21 12:49:28 +0000 | [diff] [blame] | 64 | |
| 65 | /// Matches nodes one-by-one based on their similarity. |
| 66 | void computeMapping(); |
| 67 | |
Johannes Altmanninger | e0fe5cd | 2017-08-19 02:56:35 +0000 | [diff] [blame] | 68 | // Compute Change for each node based on similarity. |
| 69 | void computeChangeKinds(Mapping &M); |
Alex Lorenz | a75b2ca | 2017-07-21 12:49:28 +0000 | [diff] [blame] | 70 | |
Johannes Altmanninger | e0fe5cd | 2017-08-19 02:56:35 +0000 | [diff] [blame] | 71 | 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 Lorenz | a75b2ca | 2017-07-21 12:49:28 +0000 | [diff] [blame] | 78 | |
| 79 | private: |
| 80 | // Returns true if the two subtrees are identical. |
Johannes Altmanninger | 31b52d6 | 2017-08-01 20:17:46 +0000 | [diff] [blame] | 81 | bool identical(NodeId Id1, NodeId Id2) const; |
Alex Lorenz | a75b2ca | 2017-07-21 12:49:28 +0000 | [diff] [blame] | 82 | |
Alex Lorenz | a75b2ca | 2017-07-21 12:49:28 +0000 | [diff] [blame] | 83 | // Returns false if the nodes must not be mached. |
| 84 | bool isMatchingPossible(NodeId Id1, NodeId Id2) const; |
| 85 | |
Johannes Altmanninger | e0fe5cd | 2017-08-19 02:56:35 +0000 | [diff] [blame] | 86 | // Returns true if the nodes' parents are matched. |
| 87 | bool haveSameParents(const Mapping &M, NodeId Id1, NodeId Id2) const; |
| 88 | |
Alex Lorenz | a75b2ca | 2017-07-21 12:49:28 +0000 | [diff] [blame] | 89 | // 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 Altmanninger | d196930 | 2017-08-20 12:09:07 +0000 | [diff] [blame] | 95 | double getJaccardSimilarity(const Mapping &M, NodeId Id1, NodeId Id2) const; |
Alex Lorenz | a75b2ca | 2017-07-21 12:49:28 +0000 | [diff] [blame] | 96 | |
| 97 | // Returns the node that has the highest degree of similarity. |
| 98 | NodeId findCandidate(const Mapping &M, NodeId Id1) const; |
| 99 | |
Johannes Altmanninger | e0fe5cd | 2017-08-19 02:56:35 +0000 | [diff] [blame] | 100 | // Returns a mapping of identical subtrees. |
| 101 | Mapping matchTopDown() const; |
| 102 | |
Alex Lorenz | a75b2ca | 2017-07-21 12:49:28 +0000 | [diff] [blame] | 103 | // 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 Altmanninger | 8b0e066 | 2017-08-01 20:17:40 +0000 | [diff] [blame] | 111 | /// Represents the AST of a TranslationUnit. |
Johannes Altmanninger | 31b52d6 | 2017-08-01 20:17:46 +0000 | [diff] [blame] | 112 | class SyntaxTree::Impl { |
Johannes Altmanninger | 8b0e066 | 2017-08-01 20:17:40 +0000 | [diff] [blame] | 113 | public: |
Johannes Altmanninger | 8b0e066 | 2017-08-01 20:17:40 +0000 | [diff] [blame] | 114 | /// Constructs a tree from an AST node. |
Johannes Altmanninger | 2b955ff | 2017-08-22 08:56:26 +0000 | [diff] [blame] | 115 | Impl(SyntaxTree *Parent, Decl *N, ASTContext &AST); |
| 116 | Impl(SyntaxTree *Parent, Stmt *N, ASTContext &AST); |
Johannes Altmanninger | 8b0e066 | 2017-08-01 20:17:40 +0000 | [diff] [blame] | 117 | template <class T> |
Johannes Altmanninger | 31b52d6 | 2017-08-01 20:17:46 +0000 | [diff] [blame] | 118 | Impl(SyntaxTree *Parent, |
| 119 | typename std::enable_if<std::is_base_of<Stmt, T>::value, T>::type *Node, |
Johannes Altmanninger | 2b955ff | 2017-08-22 08:56:26 +0000 | [diff] [blame] | 120 | ASTContext &AST) |
Johannes Altmanninger | 31b52d6 | 2017-08-01 20:17:46 +0000 | [diff] [blame] | 121 | : Impl(Parent, dyn_cast<Stmt>(Node), AST) {} |
Johannes Altmanninger | 8b0e066 | 2017-08-01 20:17:40 +0000 | [diff] [blame] | 122 | template <class T> |
Johannes Altmanninger | 31b52d6 | 2017-08-01 20:17:46 +0000 | [diff] [blame] | 123 | Impl(SyntaxTree *Parent, |
| 124 | typename std::enable_if<std::is_base_of<Decl, T>::value, T>::type *Node, |
Johannes Altmanninger | 2b955ff | 2017-08-22 08:56:26 +0000 | [diff] [blame] | 125 | ASTContext &AST) |
Johannes Altmanninger | 31b52d6 | 2017-08-01 20:17:46 +0000 | [diff] [blame] | 126 | : Impl(Parent, dyn_cast<Decl>(Node), AST) {} |
Johannes Altmanninger | 8b0e066 | 2017-08-01 20:17:40 +0000 | [diff] [blame] | 127 | |
| 128 | SyntaxTree *Parent; |
Johannes Altmanninger | 2b955ff | 2017-08-22 08:56:26 +0000 | [diff] [blame] | 129 | ASTContext &AST; |
Johannes Altmanninger | 8b0e066 | 2017-08-01 20:17:40 +0000 | [diff] [blame] | 130 | std::vector<NodeId> Leaves; |
| 131 | // Maps preorder indices to postorder ones. |
| 132 | std::vector<int> PostorderIds; |
Johannes Altmanninger | e0fe5cd | 2017-08-19 02:56:35 +0000 | [diff] [blame] | 133 | std::vector<NodeId> NodesBfs; |
Johannes Altmanninger | 8b0e066 | 2017-08-01 20:17:40 +0000 | [diff] [blame] | 134 | |
| 135 | int getSize() const { return Nodes.size(); } |
Johannes Altmanninger | 31b52d6 | 2017-08-01 20:17:46 +0000 | [diff] [blame] | 136 | NodeId getRootId() const { return 0; } |
Johannes Altmanninger | e0fe5cd | 2017-08-19 02:56:35 +0000 | [diff] [blame] | 137 | PreorderIterator begin() const { return getRootId(); } |
| 138 | PreorderIterator end() const { return getSize(); } |
Johannes Altmanninger | 8b0e066 | 2017-08-01 20:17:40 +0000 | [diff] [blame] | 139 | |
| 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 Altmanninger | e0fe5cd | 2017-08-19 02:56:35 +0000 | [diff] [blame] | 146 | int findPositionInParent(NodeId Id, bool Shifted = false) const; |
Johannes Altmanninger | 8b0e066 | 2017-08-01 20:17:40 +0000 | [diff] [blame] | 147 | |
Johannes Altmanninger | 2b955ff | 2017-08-22 08:56:26 +0000 | [diff] [blame] | 148 | std::string getRelativeName(const NamedDecl *ND, |
| 149 | const DeclContext *Context) const; |
| 150 | std::string getRelativeName(const NamedDecl *ND) const; |
| 151 | |
Johannes Altmanninger | 31b52d6 | 2017-08-01 20:17:46 +0000 | [diff] [blame] | 152 | std::string getNodeValue(NodeId Id) const; |
Johannes Altmanninger | e0fe5cd | 2017-08-19 02:56:35 +0000 | [diff] [blame] | 153 | std::string getNodeValue(const Node &Node) const; |
Johannes Altmanninger | 0dd86dc | 2017-08-20 16:18:43 +0000 | [diff] [blame] | 154 | std::string getDeclValue(const Decl *D) const; |
| 155 | std::string getStmtValue(const Stmt *S) const; |
Johannes Altmanninger | 8b0e066 | 2017-08-01 20:17:40 +0000 | [diff] [blame] | 156 | |
Johannes Altmanninger | 8b0e066 | 2017-08-01 20:17:40 +0000 | [diff] [blame] | 157 | private: |
| 158 | /// Nodes in preorder. |
| 159 | std::vector<Node> Nodes; |
| 160 | |
| 161 | void initTree(); |
| 162 | void setLeftMostDescendants(); |
| 163 | }; |
| 164 | |
Johannes Altmanninger | d5b56a8 | 2017-08-20 10:22:32 +0000 | [diff] [blame] | 165 | static bool isSpecializedNodeExcluded(const Decl *D) { return D->isImplicit(); } |
| 166 | static bool isSpecializedNodeExcluded(const Stmt *S) { return false; } |
| 167 | |
Alex Lorenz | a75b2ca | 2017-07-21 12:49:28 +0000 | [diff] [blame] | 168 | template <class T> |
| 169 | static bool isNodeExcluded(const SourceManager &SrcMgr, T *N) { |
| 170 | if (!N) |
| 171 | return true; |
| 172 | SourceLocation SLoc = N->getLocStart(); |
Johannes Altmanninger | d5b56a8 | 2017-08-20 10:22:32 +0000 | [diff] [blame] | 173 | 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 Lorenz | a75b2ca | 2017-07-21 12:49:28 +0000 | [diff] [blame] | 182 | } |
| 183 | |
| 184 | namespace { |
| 185 | /// Counts the number of nodes that will be compared. |
| 186 | struct NodeCountVisitor : public RecursiveASTVisitor<NodeCountVisitor> { |
| 187 | int Count = 0; |
Johannes Altmanninger | 31b52d6 | 2017-08-01 20:17:46 +0000 | [diff] [blame] | 188 | const SyntaxTree::Impl &Tree; |
| 189 | NodeCountVisitor(const SyntaxTree::Impl &Tree) : Tree(Tree) {} |
Alex Lorenz | a75b2ca | 2017-07-21 12:49:28 +0000 | [diff] [blame] | 190 | bool TraverseDecl(Decl *D) { |
Johannes Altmanninger | 31b52d6 | 2017-08-01 20:17:46 +0000 | [diff] [blame] | 191 | if (isNodeExcluded(Tree.AST.getSourceManager(), D)) |
Alex Lorenz | a75b2ca | 2017-07-21 12:49:28 +0000 | [diff] [blame] | 192 | return true; |
| 193 | ++Count; |
| 194 | RecursiveASTVisitor<NodeCountVisitor>::TraverseDecl(D); |
| 195 | return true; |
| 196 | } |
| 197 | bool TraverseStmt(Stmt *S) { |
Johannes Altmanninger | d5b56a8 | 2017-08-20 10:22:32 +0000 | [diff] [blame] | 198 | if (S) |
| 199 | S = S->IgnoreImplicit(); |
Johannes Altmanninger | 31b52d6 | 2017-08-01 20:17:46 +0000 | [diff] [blame] | 200 | if (isNodeExcluded(Tree.AST.getSourceManager(), S)) |
Alex Lorenz | a75b2ca | 2017-07-21 12:49:28 +0000 | [diff] [blame] | 201 | 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 | |
| 210 | namespace { |
| 211 | // Sets Height, Parent and Children for each node. |
| 212 | struct PreorderVisitor : public RecursiveASTVisitor<PreorderVisitor> { |
| 213 | int Id = 0, Depth = 0; |
| 214 | NodeId Parent; |
Johannes Altmanninger | 31b52d6 | 2017-08-01 20:17:46 +0000 | [diff] [blame] | 215 | SyntaxTree::Impl &Tree; |
Alex Lorenz | a75b2ca | 2017-07-21 12:49:28 +0000 | [diff] [blame] | 216 | |
Johannes Altmanninger | 31b52d6 | 2017-08-01 20:17:46 +0000 | [diff] [blame] | 217 | PreorderVisitor(SyntaxTree::Impl &Tree) : Tree(Tree) {} |
Alex Lorenz | a75b2ca | 2017-07-21 12:49:28 +0000 | [diff] [blame] | 218 | |
| 219 | template <class T> std::tuple<NodeId, NodeId> PreTraverse(T *ASTNode) { |
| 220 | NodeId MyId = Id; |
Johannes Altmanninger | 31b52d6 | 2017-08-01 20:17:46 +0000 | [diff] [blame] | 221 | Node &N = Tree.getMutableNode(MyId); |
Alex Lorenz | a75b2ca | 2017-07-21 12:49:28 +0000 | [diff] [blame] | 222 | 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 Altmanninger | 31b52d6 | 2017-08-01 20:17:46 +0000 | [diff] [blame] | 228 | Node &P = Tree.getMutableNode(Parent); |
Alex Lorenz | a75b2ca | 2017-07-21 12:49:28 +0000 | [diff] [blame] | 229 | P.Children.push_back(MyId); |
| 230 | } |
| 231 | Parent = MyId; |
| 232 | ++Id; |
| 233 | ++Depth; |
Johannes Altmanninger | 31b52d6 | 2017-08-01 20:17:46 +0000 | [diff] [blame] | 234 | return std::make_tuple(MyId, Tree.getNode(MyId).Parent); |
Alex Lorenz | a75b2ca | 2017-07-21 12:49:28 +0000 | [diff] [blame] | 235 | } |
| 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 Altmanninger | 31b52d6 | 2017-08-01 20:17:46 +0000 | [diff] [blame] | 242 | Node &N = Tree.getMutableNode(MyId); |
Johannes Altmanninger | fa524d7 | 2017-08-18 16:34:15 +0000 | [diff] [blame] | 243 | N.RightMostDescendant = Id - 1; |
| 244 | assert(N.RightMostDescendant >= 0 && |
| 245 | N.RightMostDescendant < Tree.getSize() && |
| 246 | "Rightmost descendant must be a valid tree node."); |
Alex Lorenz | a75b2ca | 2017-07-21 12:49:28 +0000 | [diff] [blame] | 247 | if (N.isLeaf()) |
Johannes Altmanninger | 31b52d6 | 2017-08-01 20:17:46 +0000 | [diff] [blame] | 248 | Tree.Leaves.push_back(MyId); |
Alex Lorenz | a75b2ca | 2017-07-21 12:49:28 +0000 | [diff] [blame] | 249 | N.Height = 1; |
| 250 | for (NodeId Child : N.Children) |
Johannes Altmanninger | 31b52d6 | 2017-08-01 20:17:46 +0000 | [diff] [blame] | 251 | N.Height = std::max(N.Height, 1 + Tree.getNode(Child).Height); |
Alex Lorenz | a75b2ca | 2017-07-21 12:49:28 +0000 | [diff] [blame] | 252 | } |
| 253 | bool TraverseDecl(Decl *D) { |
Johannes Altmanninger | 31b52d6 | 2017-08-01 20:17:46 +0000 | [diff] [blame] | 254 | if (isNodeExcluded(Tree.AST.getSourceManager(), D)) |
Alex Lorenz | a75b2ca | 2017-07-21 12:49:28 +0000 | [diff] [blame] | 255 | 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 Altmanninger | d5b56a8 | 2017-08-20 10:22:32 +0000 | [diff] [blame] | 262 | if (S) |
| 263 | S = S->IgnoreImplicit(); |
Johannes Altmanninger | 31b52d6 | 2017-08-01 20:17:46 +0000 | [diff] [blame] | 264 | if (isNodeExcluded(Tree.AST.getSourceManager(), S)) |
Alex Lorenz | a75b2ca | 2017-07-21 12:49:28 +0000 | [diff] [blame] | 265 | 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 Altmanninger | 2b955ff | 2017-08-22 08:56:26 +0000 | [diff] [blame] | 275 | SyntaxTree::Impl::Impl(SyntaxTree *Parent, Decl *N, ASTContext &AST) |
Alex Lorenz | a75b2ca | 2017-07-21 12:49:28 +0000 | [diff] [blame] | 276 | : 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 Altmanninger | 2b955ff | 2017-08-22 08:56:26 +0000 | [diff] [blame] | 285 | SyntaxTree::Impl::Impl(SyntaxTree *Parent, Stmt *N, ASTContext &AST) |
Alex Lorenz | a75b2ca | 2017-07-21 12:49:28 +0000 | [diff] [blame] | 286 | : 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 Altmanninger | 31b52d6 | 2017-08-01 20:17:46 +0000 | [diff] [blame] | 295 | static std::vector<NodeId> getSubtreePostorder(const SyntaxTree::Impl &Tree, |
Alex Lorenz | a75b2ca | 2017-07-21 12:49:28 +0000 | [diff] [blame] | 296 | 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 Altmanninger | 31b52d6 | 2017-08-01 20:17:46 +0000 | [diff] [blame] | 308 | static std::vector<NodeId> getSubtreeBfs(const SyntaxTree::Impl &Tree, |
Alex Lorenz | a75b2ca | 2017-07-21 12:49:28 +0000 | [diff] [blame] | 309 | 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 Altmanninger | e0fe5cd | 2017-08-19 02:56:35 +0000 | [diff] [blame] | 319 | void 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 | |
| 333 | void 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 Altmanninger | 31b52d6 | 2017-08-01 20:17:46 +0000 | [diff] [blame] | 345 | int SyntaxTree::Impl::getNumberOfDescendants(NodeId Id) const { |
Alex Lorenz | a75b2ca | 2017-07-21 12:49:28 +0000 | [diff] [blame] | 346 | return getNode(Id).RightMostDescendant - Id + 1; |
| 347 | } |
| 348 | |
Johannes Altmanninger | 31b52d6 | 2017-08-01 20:17:46 +0000 | [diff] [blame] | 349 | bool SyntaxTree::Impl::isInSubtree(NodeId Id, NodeId SubtreeRoot) const { |
Johannes Altmanninger | fa524d7 | 2017-08-18 16:34:15 +0000 | [diff] [blame] | 350 | return Id >= SubtreeRoot && Id <= getNode(SubtreeRoot).RightMostDescendant; |
Alex Lorenz | a75b2ca | 2017-07-21 12:49:28 +0000 | [diff] [blame] | 351 | } |
| 352 | |
Johannes Altmanninger | e0fe5cd | 2017-08-19 02:56:35 +0000 | [diff] [blame] | 353 | int 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 Altmanninger | 69774d6 | 2017-08-18 21:26:34 +0000 | [diff] [blame] | 368 | } |
| 369 | |
Johannes Altmanninger | 2b955ff | 2017-08-22 08:56:26 +0000 | [diff] [blame] | 370 | // 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. |
| 372 | std::string |
| 373 | SyntaxTree::Impl::getRelativeName(const NamedDecl *ND, |
| 374 | const DeclContext *Context) const { |
Johannes Altmanninger | bc7d817 | 2017-08-22 08:59:13 +0000 | [diff] [blame^] | 375 | std::string Val = ND->getQualifiedNameAsString(); |
Johannes Altmanninger | 2b955ff | 2017-08-22 08:56:26 +0000 | [diff] [blame] | 376 | std::string ContextPrefix; |
Johannes Altmanninger | bc7d817 | 2017-08-22 08:59:13 +0000 | [diff] [blame^] | 377 | if (!Context) |
| 378 | return Val; |
Johannes Altmanninger | 2b955ff | 2017-08-22 08:56:26 +0000 | [diff] [blame] | 379 | 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 Altmanninger | 2b955ff | 2017-08-22 08:56:26 +0000 | [diff] [blame] | 386 | // 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 | |
| 394 | std::string SyntaxTree::Impl::getRelativeName(const NamedDecl *ND) const { |
| 395 | return getRelativeName(ND, ND->getDeclContext()); |
| 396 | } |
| 397 | |
| 398 | static 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 Altmanninger | bc7d817 | 2017-08-22 08:59:13 +0000 | [diff] [blame^] | 409 | return nullptr; |
Johannes Altmanninger | 2b955ff | 2017-08-22 08:56:26 +0000 | [diff] [blame] | 410 | } |
| 411 | |
Johannes Altmanninger | e0fe5cd | 2017-08-19 02:56:35 +0000 | [diff] [blame] | 412 | std::string SyntaxTree::Impl::getNodeValue(NodeId Id) const { |
| 413 | return getNodeValue(getNode(Id)); |
| 414 | } |
| 415 | |
| 416 | std::string SyntaxTree::Impl::getNodeValue(const Node &N) const { |
| 417 | const DynTypedNode &DTN = N.ASTNode; |
Johannes Altmanninger | 0dd86dc | 2017-08-20 16:18:43 +0000 | [diff] [blame] | 418 | 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 | |
| 425 | std::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 Altmanninger | 2b955ff | 2017-08-22 08:56:26 +0000 | [diff] [blame] | 431 | Value += getRelativeName(V) + "(" + V->getType().getAsString(TypePP) + ")"; |
Johannes Altmanninger | 0dd86dc | 2017-08-20 16:18:43 +0000 | [diff] [blame] | 432 | 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 Altmanninger | 2b955ff | 2017-08-22 08:56:26 +0000 | [diff] [blame] | 443 | Value += getRelativeName(Init->getMember()); |
Johannes Altmanninger | 0dd86dc | 2017-08-20 16:18:43 +0000 | [diff] [blame] | 444 | } |
| 445 | Value += ","; |
| 446 | } |
| 447 | } |
| 448 | return Value; |
| 449 | } |
| 450 | if (auto *N = dyn_cast<NamedDecl>(D)) |
Johannes Altmanninger | 2b955ff | 2017-08-22 08:56:26 +0000 | [diff] [blame] | 451 | Value += getRelativeName(N) + ";"; |
Johannes Altmanninger | 0dd86dc | 2017-08-20 16:18:43 +0000 | [diff] [blame] | 452 | 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 Lorenz | a75b2ca | 2017-07-21 12:49:28 +0000 | [diff] [blame] | 463 | return Lexer::getSourceText(Range, AST.getSourceManager(), |
| 464 | AST.getLangOpts()); |
| 465 | } |
Johannes Altmanninger | 0dd86dc | 2017-08-20 16:18:43 +0000 | [diff] [blame] | 466 | return Value; |
| 467 | } |
| 468 | |
| 469 | std::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 Altmanninger | 2b955ff | 2017-08-22 08:56:26 +0000 | [diff] [blame] | 475 | return getRelativeName(M->getMemberDecl()); |
Johannes Altmanninger | 0dd86dc | 2017-08-20 16:18:43 +0000 | [diff] [blame] | 476 | if (auto *I = dyn_cast<IntegerLiteral>(S)) { |
Alex Lorenz | a75b2ca | 2017-07-21 12:49:28 +0000 | [diff] [blame] | 477 | SmallString<256> Str; |
Johannes Altmanninger | 0dd86dc | 2017-08-20 16:18:43 +0000 | [diff] [blame] | 478 | I->getValue().toString(Str, /*Radix=*/10, /*Signed=*/false); |
Alex Lorenz | a75b2ca | 2017-07-21 12:49:28 +0000 | [diff] [blame] | 479 | return Str.str(); |
| 480 | } |
Johannes Altmanninger | 0dd86dc | 2017-08-20 16:18:43 +0000 | [diff] [blame] | 481 | if (auto *F = dyn_cast<FloatingLiteral>(S)) { |
| 482 | SmallString<256> Str; |
| 483 | F->getValue().toString(Str); |
| 484 | return Str.str(); |
Alex Lorenz | a75b2ca | 2017-07-21 12:49:28 +0000 | [diff] [blame] | 485 | } |
Johannes Altmanninger | 0dd86dc | 2017-08-20 16:18:43 +0000 | [diff] [blame] | 486 | if (auto *D = dyn_cast<DeclRefExpr>(S)) |
Johannes Altmanninger | 2b955ff | 2017-08-22 08:56:26 +0000 | [diff] [blame] | 487 | return getRelativeName(D->getDecl(), getEnclosingDeclContext(AST, S)); |
Johannes Altmanninger | 0dd86dc | 2017-08-20 16:18:43 +0000 | [diff] [blame] | 488 | 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 Lorenz | a75b2ca | 2017-07-21 12:49:28 +0000 | [diff] [blame] | 493 | } |
| 494 | |
Alex Lorenz | a75b2ca | 2017-07-21 12:49:28 +0000 | [diff] [blame] | 495 | /// Identifies a node in a subtree by its postorder offset, starting at 1. |
| 496 | struct 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 | |
| 508 | class Subtree { |
| 509 | private: |
| 510 | /// The parent tree. |
Johannes Altmanninger | 31b52d6 | 2017-08-01 20:17:46 +0000 | [diff] [blame] | 511 | const SyntaxTree::Impl &Tree; |
Alex Lorenz | a75b2ca | 2017-07-21 12:49:28 +0000 | [diff] [blame] | 512 | /// 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 | |
| 517 | public: |
| 518 | std::vector<SNodeId> KeyRoots; |
| 519 | |
Johannes Altmanninger | 31b52d6 | 2017-08-01 20:17:46 +0000 | [diff] [blame] | 520 | Subtree(const SyntaxTree::Impl &Tree, NodeId SubtreeRoot) : Tree(Tree) { |
Alex Lorenz | a75b2ca | 2017-07-21 12:49:28 +0000 | [diff] [blame] | 521 | 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 Altmanninger | 8b0e066 | 2017-08-01 20:17:40 +0000 | [diff] [blame] | 541 | std::string getNodeValue(SNodeId Id) const { |
Johannes Altmanninger | 31b52d6 | 2017-08-01 20:17:46 +0000 | [diff] [blame] | 542 | return Tree.getNodeValue(getIdInRoot(Id)); |
Johannes Altmanninger | 8b0e066 | 2017-08-01 20:17:40 +0000 | [diff] [blame] | 543 | } |
Alex Lorenz | a75b2ca | 2017-07-21 12:49:28 +0000 | [diff] [blame] | 544 | |
| 545 | private: |
| 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). |
| 581 | class ZhangShashaMatcher { |
| 582 | const ASTDiff::Impl &DiffImpl; |
| 583 | Subtree S1; |
| 584 | Subtree S2; |
| 585 | std::unique_ptr<std::unique_ptr<double[]>[]> TreeDist, ForestDist; |
| 586 | |
| 587 | public: |
Johannes Altmanninger | 31b52d6 | 2017-08-01 20:17:46 +0000 | [diff] [blame] | 588 | ZhangShashaMatcher(const ASTDiff::Impl &DiffImpl, const SyntaxTree::Impl &T1, |
| 589 | const SyntaxTree::Impl &T2, NodeId Id1, NodeId Id2) |
Alex Lorenz | a75b2ca | 2017-07-21 12:49:28 +0000 | [diff] [blame] | 590 | : 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 Lorenz | 4c0a866 | 2017-07-21 13:04:57 +0000 | [diff] [blame] | 609 | TreePairs.emplace_back(SNodeId(S1.getSize()), SNodeId(S2.getSize())); |
Alex Lorenz | a75b2ca | 2017-07-21 12:49:28 +0000 | [diff] [blame] | 610 | |
| 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 | |
| 658 | private: |
Johannes Altmanninger | fa524d7 | 2017-08-18 16:34:15 +0000 | [diff] [blame] | 659 | /// 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 Lorenz | a75b2ca | 2017-07-21 12:49:28 +0000 | [diff] [blame] | 662 | /// The values range between 0 and 1, or infinity if this edit action should |
| 663 | /// always be avoided. |
Alex Lorenz | a75b2ca | 2017-07-21 12:49:28 +0000 | [diff] [blame] | 664 | static constexpr double DeletionCost = 1; |
| 665 | static constexpr double InsertionCost = 1; |
| 666 | |
| 667 | double getUpdateCost(SNodeId Id1, SNodeId Id2) { |
Johannes Altmanninger | 8b0e066 | 2017-08-01 20:17:40 +0000 | [diff] [blame] | 668 | if (!DiffImpl.isMatchingPossible(S1.getIdInRoot(Id1), S2.getIdInRoot(Id2))) |
Alex Lorenz | a75b2ca | 2017-07-21 12:49:28 +0000 | [diff] [blame] | 669 | return std::numeric_limits<double>::max(); |
Johannes Altmanninger | 8b0e066 | 2017-08-01 20:17:40 +0000 | [diff] [blame] | 670 | return S1.getNodeValue(Id1) != S2.getNodeValue(Id2); |
Alex Lorenz | a75b2ca | 2017-07-21 12:49:28 +0000 | [diff] [blame] | 671 | } |
| 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 Altmanninger | 0da12c8 | 2017-08-19 00:57:38 +0000 | [diff] [blame] | 709 | ast_type_traits::ASTNodeKind Node::getType() const { |
| 710 | return ASTNode.getNodeKind(); |
| 711 | } |
| 712 | |
| 713 | StringRef Node::getTypeLabel() const { return getType().asStringRef(); } |
| 714 | |
Johannes Altmanninger | 0dd86dc | 2017-08-20 16:18:43 +0000 | [diff] [blame] | 715 | llvm::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 | |
| 723 | llvm::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 Lorenz | a75b2ca | 2017-07-21 12:49:28 +0000 | [diff] [blame] | 731 | namespace { |
| 732 | // Compares nodes by their depth. |
| 733 | struct HeightLess { |
Johannes Altmanninger | 31b52d6 | 2017-08-01 20:17:46 +0000 | [diff] [blame] | 734 | const SyntaxTree::Impl &Tree; |
| 735 | HeightLess(const SyntaxTree::Impl &Tree) : Tree(Tree) {} |
Alex Lorenz | a75b2ca | 2017-07-21 12:49:28 +0000 | [diff] [blame] | 736 | 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 Altmanninger | fa524d7 | 2017-08-18 16:34:15 +0000 | [diff] [blame] | 742 | namespace { |
Alex Lorenz | a75b2ca | 2017-07-21 12:49:28 +0000 | [diff] [blame] | 743 | // Priority queue for nodes, sorted descendingly by their height. |
| 744 | class PriorityList { |
Johannes Altmanninger | 31b52d6 | 2017-08-01 20:17:46 +0000 | [diff] [blame] | 745 | const SyntaxTree::Impl &Tree; |
Alex Lorenz | a75b2ca | 2017-07-21 12:49:28 +0000 | [diff] [blame] | 746 | HeightLess Cmp; |
| 747 | std::vector<NodeId> Container; |
| 748 | PriorityQueue<NodeId, std::vector<NodeId>, HeightLess> List; |
| 749 | |
| 750 | public: |
Johannes Altmanninger | 31b52d6 | 2017-08-01 20:17:46 +0000 | [diff] [blame] | 751 | PriorityList(const SyntaxTree::Impl &Tree) |
Alex Lorenz | a75b2ca | 2017-07-21 12:49:28 +0000 | [diff] [blame] | 752 | : 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 Altmanninger | fa524d7 | 2017-08-18 16:34:15 +0000 | [diff] [blame] | 779 | } // end anonymous namespace |
Alex Lorenz | a75b2ca | 2017-07-21 12:49:28 +0000 | [diff] [blame] | 780 | |
Johannes Altmanninger | 31b52d6 | 2017-08-01 20:17:46 +0000 | [diff] [blame] | 781 | bool ASTDiff::Impl::identical(NodeId Id1, NodeId Id2) const { |
Alex Lorenz | a75b2ca | 2017-07-21 12:49:28 +0000 | [diff] [blame] | 782 | 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 Altmanninger | 31b52d6 | 2017-08-01 20:17:46 +0000 | [diff] [blame] | 786 | T1.getNodeValue(Id1) != T2.getNodeValue(Id2)) |
Alex Lorenz | a75b2ca | 2017-07-21 12:49:28 +0000 | [diff] [blame] | 787 | return false; |
| 788 | for (size_t Id = 0, E = N1.Children.size(); Id < E; ++Id) |
Johannes Altmanninger | 31b52d6 | 2017-08-01 20:17:46 +0000 | [diff] [blame] | 789 | if (!identical(N1.Children[Id], N2.Children[Id])) |
Alex Lorenz | a75b2ca | 2017-07-21 12:49:28 +0000 | [diff] [blame] | 790 | return false; |
| 791 | return true; |
| 792 | } |
| 793 | |
Alex Lorenz | a75b2ca | 2017-07-21 12:49:28 +0000 | [diff] [blame] | 794 | bool ASTDiff::Impl::isMatchingPossible(NodeId Id1, NodeId Id2) const { |
Johannes Altmanninger | e0fe5cd | 2017-08-19 02:56:35 +0000 | [diff] [blame] | 795 | return Options.isMatchingAllowed(T1.getNode(Id1), T2.getNode(Id2)); |
| 796 | } |
| 797 | |
| 798 | bool 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 Lorenz | a75b2ca | 2017-07-21 12:49:28 +0000 | [diff] [blame] | 804 | } |
| 805 | |
Alex Lorenz | a75b2ca | 2017-07-21 12:49:28 +0000 | [diff] [blame] | 806 | void ASTDiff::Impl::addOptimalMapping(Mapping &M, NodeId Id1, |
| 807 | NodeId Id2) const { |
Johannes Altmanninger | d196930 | 2017-08-20 12:09:07 +0000 | [diff] [blame] | 808 | if (std::max(T1.getNumberOfDescendants(Id1), T2.getNumberOfDescendants(Id2)) > |
| 809 | Options.MaxSize) |
Alex Lorenz | a75b2ca | 2017-07-21 12:49:28 +0000 | [diff] [blame] | 810 | 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 Altmanninger | 51321ae | 2017-08-19 17:53:01 +0000 | [diff] [blame] | 816 | if (!M.hasSrc(Src) && !M.hasDst(Dst)) |
Alex Lorenz | a75b2ca | 2017-07-21 12:49:28 +0000 | [diff] [blame] | 817 | M.link(Src, Dst); |
| 818 | } |
| 819 | } |
| 820 | |
Johannes Altmanninger | d196930 | 2017-08-20 12:09:07 +0000 | [diff] [blame] | 821 | double ASTDiff::Impl::getJaccardSimilarity(const Mapping &M, NodeId Id1, |
| 822 | NodeId Id2) const { |
Alex Lorenz | a75b2ca | 2017-07-21 12:49:28 +0000 | [diff] [blame] | 823 | int CommonDescendants = 0; |
| 824 | const Node &N1 = T1.getNode(Id1); |
Johannes Altmanninger | d196930 | 2017-08-20 12:09:07 +0000 | [diff] [blame] | 825 | // 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 Lorenz | a75b2ca | 2017-07-21 12:49:28 +0000 | [diff] [blame] | 838 | } |
| 839 | |
| 840 | NodeId ASTDiff::Impl::findCandidate(const Mapping &M, NodeId Id1) const { |
| 841 | NodeId Candidate; |
Johannes Altmanninger | 31b52d6 | 2017-08-01 20:17:46 +0000 | [diff] [blame] | 842 | double HighestSimilarity = 0.0; |
Johannes Altmanninger | e0fe5cd | 2017-08-19 02:56:35 +0000 | [diff] [blame] | 843 | for (NodeId Id2 : T2) { |
Alex Lorenz | a75b2ca | 2017-07-21 12:49:28 +0000 | [diff] [blame] | 844 | if (!isMatchingPossible(Id1, Id2)) |
| 845 | continue; |
| 846 | if (M.hasDst(Id2)) |
| 847 | continue; |
Johannes Altmanninger | d196930 | 2017-08-20 12:09:07 +0000 | [diff] [blame] | 848 | double Similarity = getJaccardSimilarity(M, Id1, Id2); |
Johannes Altmanninger | fa524d7 | 2017-08-18 16:34:15 +0000 | [diff] [blame] | 849 | if (Similarity >= Options.MinSimilarity && Similarity > HighestSimilarity) { |
Johannes Altmanninger | 31b52d6 | 2017-08-01 20:17:46 +0000 | [diff] [blame] | 850 | HighestSimilarity = Similarity; |
Alex Lorenz | a75b2ca | 2017-07-21 12:49:28 +0000 | [diff] [blame] | 851 | Candidate = Id2; |
| 852 | } |
| 853 | } |
| 854 | return Candidate; |
| 855 | } |
| 856 | |
| 857 | void ASTDiff::Impl::matchBottomUp(Mapping &M) const { |
Johannes Altmanninger | 31b52d6 | 2017-08-01 20:17:46 +0000 | [diff] [blame] | 858 | std::vector<NodeId> Postorder = getSubtreePostorder(T1, T1.getRootId()); |
Alex Lorenz | a75b2ca | 2017-07-21 12:49:28 +0000 | [diff] [blame] | 859 | for (NodeId Id1 : Postorder) { |
Johannes Altmanninger | fa524d7 | 2017-08-18 16:34:15 +0000 | [diff] [blame] | 860 | if (Id1 == T1.getRootId() && !M.hasSrc(T1.getRootId()) && |
| 861 | !M.hasDst(T2.getRootId())) { |
Johannes Altmanninger | 31b52d6 | 2017-08-01 20:17:46 +0000 | [diff] [blame] | 862 | if (isMatchingPossible(T1.getRootId(), T2.getRootId())) { |
| 863 | M.link(T1.getRootId(), T2.getRootId()); |
| 864 | addOptimalMapping(M, T1.getRootId(), T2.getRootId()); |
Alex Lorenz | a75b2ca | 2017-07-21 12:49:28 +0000 | [diff] [blame] | 865 | } |
| 866 | break; |
| 867 | } |
Alex Lorenz | a75b2ca | 2017-07-21 12:49:28 +0000 | [diff] [blame] | 868 | bool Matched = M.hasSrc(Id1); |
Johannes Altmanninger | d196930 | 2017-08-20 12:09:07 +0000 | [diff] [blame] | 869 | const Node &N1 = T1.getNode(Id1); |
Alex Lorenz | a75b2ca | 2017-07-21 12:49:28 +0000 | [diff] [blame] | 870 | 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 Altmanninger | 51321ae | 2017-08-19 17:53:01 +0000 | [diff] [blame] | 876 | if (Id2.isValid()) { |
Johannes Altmanninger | fa524d7 | 2017-08-18 16:34:15 +0000 | [diff] [blame] | 877 | M.link(Id1, Id2); |
| 878 | addOptimalMapping(M, Id1, Id2); |
| 879 | } |
Alex Lorenz | a75b2ca | 2017-07-21 12:49:28 +0000 | [diff] [blame] | 880 | } |
| 881 | } |
| 882 | |
| 883 | Mapping ASTDiff::Impl::matchTopDown() const { |
| 884 | PriorityList L1(T1); |
| 885 | PriorityList L2(T2); |
| 886 | |
Johannes Altmanninger | 51321ae | 2017-08-19 17:53:01 +0000 | [diff] [blame] | 887 | Mapping M(T1.getSize() + T2.getSize()); |
Alex Lorenz | a75b2ca | 2017-07-21 12:49:28 +0000 | [diff] [blame] | 888 | |
Johannes Altmanninger | 31b52d6 | 2017-08-01 20:17:46 +0000 | [diff] [blame] | 889 | L1.push(T1.getRootId()); |
| 890 | L2.push(T2.getRootId()); |
Alex Lorenz | a75b2ca | 2017-07-21 12:49:28 +0000 | [diff] [blame] | 891 | |
| 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 Altmanninger | fa524d7 | 2017-08-18 16:34:15 +0000 | [diff] [blame] | 909 | for (NodeId Id2 : H2) { |
Johannes Altmanninger | 51321ae | 2017-08-19 17:53:01 +0000 | [diff] [blame] | 910 | if (identical(Id1, Id2) && !M.hasSrc(Id1) && !M.hasDst(Id2)) { |
Johannes Altmanninger | fa524d7 | 2017-08-18 16:34:15 +0000 | [diff] [blame] | 911 | for (int I = 0, E = T1.getNumberOfDescendants(Id1); I < E; ++I) |
| 912 | M.link(Id1 + I, Id2 + I); |
| 913 | } |
| 914 | } |
Alex Lorenz | a75b2ca | 2017-07-21 12:49:28 +0000 | [diff] [blame] | 915 | } |
| 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 Altmanninger | e0fe5cd | 2017-08-19 02:56:35 +0000 | [diff] [blame] | 928 | ASTDiff::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 Lorenz | a75b2ca | 2017-07-21 12:49:28 +0000 | [diff] [blame] | 935 | void ASTDiff::Impl::computeMapping() { |
Alex Lorenz | a75b2ca | 2017-07-21 12:49:28 +0000 | [diff] [blame] | 936 | TheMapping = matchTopDown(); |
Johannes Altmanninger | d196930 | 2017-08-20 12:09:07 +0000 | [diff] [blame] | 937 | if (Options.StopAfterTopDown) |
| 938 | return; |
Alex Lorenz | a75b2ca | 2017-07-21 12:49:28 +0000 | [diff] [blame] | 939 | matchBottomUp(TheMapping); |
Alex Lorenz | a75b2ca | 2017-07-21 12:49:28 +0000 | [diff] [blame] | 940 | } |
| 941 | |
Johannes Altmanninger | e0fe5cd | 2017-08-19 02:56:35 +0000 | [diff] [blame] | 942 | void 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 Lorenz | a75b2ca | 2017-07-21 12:49:28 +0000 | [diff] [blame] | 947 | } |
Alex Lorenz | a75b2ca | 2017-07-21 12:49:28 +0000 | [diff] [blame] | 948 | } |
Johannes Altmanninger | e0fe5cd | 2017-08-19 02:56:35 +0000 | [diff] [blame] | 949 | 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 Lorenz | a75b2ca | 2017-07-21 12:49:28 +0000 | [diff] [blame] | 956 | NodeId Id2 = M.getDst(Id1); |
| 957 | if (Id2.isInvalid()) |
Johannes Altmanninger | e0fe5cd | 2017-08-19 02:56:35 +0000 | [diff] [blame] | 958 | 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 Lorenz | a75b2ca | 2017-07-21 12:49:28 +0000 | [diff] [blame] | 965 | } |
Johannes Altmanninger | e0fe5cd | 2017-08-19 02:56:35 +0000 | [diff] [blame] | 966 | 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 Lorenz | a75b2ca | 2017-07-21 12:49:28 +0000 | [diff] [blame] | 983 | } |
| 984 | |
| 985 | ASTDiff::ASTDiff(SyntaxTree &T1, SyntaxTree &T2, |
| 986 | const ComparisonOptions &Options) |
| 987 | : DiffImpl(llvm::make_unique<Impl>(*T1.TreeImpl, *T2.TreeImpl, Options)) {} |
| 988 | |
Johannes Altmanninger | 31b52d6 | 2017-08-01 20:17:46 +0000 | [diff] [blame] | 989 | ASTDiff::~ASTDiff() = default; |
Alex Lorenz | a75b2ca | 2017-07-21 12:49:28 +0000 | [diff] [blame] | 990 | |
Johannes Altmanninger | e0fe5cd | 2017-08-19 02:56:35 +0000 | [diff] [blame] | 991 | NodeId ASTDiff::getMapped(const SyntaxTree &SourceTree, NodeId Id) const { |
| 992 | return DiffImpl->getMapped(SourceTree.TreeImpl, Id); |
| 993 | } |
| 994 | |
Johannes Altmanninger | 2b955ff | 2017-08-22 08:56:26 +0000 | [diff] [blame] | 995 | SyntaxTree::SyntaxTree(ASTContext &AST) |
Johannes Altmanninger | 31b52d6 | 2017-08-01 20:17:46 +0000 | [diff] [blame] | 996 | : TreeImpl(llvm::make_unique<SyntaxTree::Impl>( |
Alex Lorenz | a75b2ca | 2017-07-21 12:49:28 +0000 | [diff] [blame] | 997 | this, AST.getTranslationUnitDecl(), AST)) {} |
| 998 | |
Johannes Altmanninger | 8b0e066 | 2017-08-01 20:17:40 +0000 | [diff] [blame] | 999 | SyntaxTree::~SyntaxTree() = default; |
| 1000 | |
Johannes Altmanninger | 0da12c8 | 2017-08-19 00:57:38 +0000 | [diff] [blame] | 1001 | const ASTContext &SyntaxTree::getASTContext() const { return TreeImpl->AST; } |
| 1002 | |
| 1003 | const Node &SyntaxTree::getNode(NodeId Id) const { |
| 1004 | return TreeImpl->getNode(Id); |
| 1005 | } |
| 1006 | |
Johannes Altmanninger | e0fe5cd | 2017-08-19 02:56:35 +0000 | [diff] [blame] | 1007 | int SyntaxTree::getSize() const { return TreeImpl->getSize(); } |
Johannes Altmanninger | 0da12c8 | 2017-08-19 00:57:38 +0000 | [diff] [blame] | 1008 | NodeId SyntaxTree::getRootId() const { return TreeImpl->getRootId(); } |
Johannes Altmanninger | e0fe5cd | 2017-08-19 02:56:35 +0000 | [diff] [blame] | 1009 | SyntaxTree::PreorderIterator SyntaxTree::begin() const { |
| 1010 | return TreeImpl->begin(); |
| 1011 | } |
| 1012 | SyntaxTree::PreorderIterator SyntaxTree::end() const { return TreeImpl->end(); } |
Johannes Altmanninger | 0da12c8 | 2017-08-19 00:57:38 +0000 | [diff] [blame] | 1013 | |
Johannes Altmanninger | e0fe5cd | 2017-08-19 02:56:35 +0000 | [diff] [blame] | 1014 | int SyntaxTree::findPositionInParent(NodeId Id) const { |
| 1015 | return TreeImpl->findPositionInParent(Id); |
| 1016 | } |
| 1017 | |
| 1018 | std::pair<unsigned, unsigned> |
| 1019 | SyntaxTree::getSourceRangeOffsets(const Node &N) const { |
Johannes Altmanninger | 0da12c8 | 2017-08-19 00:57:38 +0000 | [diff] [blame] | 1020 | 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 Lorenz | a75b2ca | 2017-07-21 12:49:28 +0000 | [diff] [blame] | 1033 | |
Johannes Altmanninger | e0fe5cd | 2017-08-19 02:56:35 +0000 | [diff] [blame] | 1034 | std::string SyntaxTree::getNodeValue(NodeId Id) const { |
| 1035 | return TreeImpl->getNodeValue(Id); |
| 1036 | } |
| 1037 | |
| 1038 | std::string SyntaxTree::getNodeValue(const Node &N) const { |
| 1039 | return TreeImpl->getNodeValue(N); |
Alex Lorenz | a75b2ca | 2017-07-21 12:49:28 +0000 | [diff] [blame] | 1040 | } |
| 1041 | |
| 1042 | } // end namespace diff |
| 1043 | } // end namespace clang |