1 //===- ASTDiff.h - AST differencing API -----------------------*- C++ -*- -===// 2 // 3 // 4 // Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions. 5 // See https://llvm.org/LICENSE.txt for license information. 6 // SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception 7 // 8 //===----------------------------------------------------------------------===// 9 // 10 // This file specifies an interface that can be used to compare C++ syntax 11 // trees. 12 // 13 // We use the gumtree algorithm which combines a heuristic top-down search that 14 // is able to match large subtrees that are equivalent, with an optimal 15 // algorithm to match small subtrees. 16 // 17 //===----------------------------------------------------------------------===// 18 19 #ifndef LLVM_CLANG_TOOLING_ASTDIFF_ASTDIFF_H 20 #define LLVM_CLANG_TOOLING_ASTDIFF_ASTDIFF_H 21 22 #include "clang/Tooling/ASTDiff/ASTDiffInternal.h" 23 #include <optional> 24 25 namespace clang { 26 namespace diff { 27 28 enum ChangeKind { 29 None, 30 Delete, // (Src): delete node Src. 31 Update, // (Src, Dst): update the value of node Src to match Dst. 32 Insert, // (Src, Dst, Pos): insert Src as child of Dst at offset Pos. 33 Move, // (Src, Dst, Pos): move Src to be a child of Dst at offset Pos. 34 UpdateMove // Same as Move plus Update. 35 }; 36 37 /// Represents a Clang AST node, alongside some additional information. 38 struct Node { 39 NodeId Parent, LeftMostDescendant, RightMostDescendant; 40 int Depth, Height, Shift = 0; 41 DynTypedNode ASTNode; 42 SmallVector<NodeId, 4> Children; 43 ChangeKind Change = None; 44 45 ASTNodeKind getType() const; 46 StringRef getTypeLabel() const; isLeafNode47 bool isLeaf() const { return Children.empty(); } 48 std::optional<StringRef> getIdentifier() const; 49 std::optional<std::string> getQualifiedIdentifier() const; 50 }; 51 52 /// SyntaxTree objects represent subtrees of the AST. 53 /// They can be constructed from any Decl or Stmt. 54 class SyntaxTree { 55 public: 56 /// Constructs a tree from a translation unit. 57 SyntaxTree(ASTContext &AST); 58 /// Constructs a tree from any AST node. 59 template <class T> SyntaxTree(T * Node,ASTContext & AST)60 SyntaxTree(T *Node, ASTContext &AST) 61 : TreeImpl(std::make_unique<Impl>(this, Node, AST)) {} 62 SyntaxTree(SyntaxTree &&Other) = default; 63 ~SyntaxTree(); 64 65 const ASTContext &getASTContext() const; 66 StringRef getFilename() const; 67 68 int getSize() const; 69 NodeId getRootId() const; 70 using PreorderIterator = NodeId; 71 PreorderIterator begin() const; 72 PreorderIterator end() const; 73 74 const Node &getNode(NodeId Id) const; 75 int findPositionInParent(NodeId Id) const; 76 77 // Returns the starting and ending offset of the node in its source file. 78 std::pair<unsigned, unsigned> getSourceRangeOffsets(const Node &N) const; 79 80 /// Serialize the node attributes to a string representation. This should 81 /// uniquely distinguish nodes of the same kind. Note that this function just 82 /// returns a representation of the node value, not considering descendants. 83 std::string getNodeValue(NodeId Id) const; 84 std::string getNodeValue(const Node &Node) const; 85 86 class Impl; 87 std::unique_ptr<Impl> TreeImpl; 88 }; 89 90 struct ComparisonOptions { 91 /// During top-down matching, only consider nodes of at least this height. 92 int MinHeight = 2; 93 94 /// During bottom-up matching, match only nodes with at least this value as 95 /// the ratio of their common descendants. 96 double MinSimilarity = 0.5; 97 98 /// Whenever two subtrees are matched in the bottom-up phase, the optimal 99 /// mapping is computed, unless the size of either subtrees exceeds this. 100 int MaxSize = 100; 101 102 bool StopAfterTopDown = false; 103 104 /// Returns false if the nodes should never be matched. isMatchingAllowedComparisonOptions105 bool isMatchingAllowed(const Node &N1, const Node &N2) const { 106 return N1.getType().isSame(N2.getType()); 107 } 108 }; 109 110 class ASTDiff { 111 public: 112 ASTDiff(SyntaxTree &Src, SyntaxTree &Dst, const ComparisonOptions &Options); 113 ~ASTDiff(); 114 115 // Returns the ID of the node that is mapped to the given node in SourceTree. 116 NodeId getMapped(const SyntaxTree &SourceTree, NodeId Id) const; 117 118 class Impl; 119 120 private: 121 std::unique_ptr<Impl> DiffImpl; 122 }; 123 124 } // end namespace diff 125 } // end namespace clang 126 127 #endif 128