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