| //===- ASTDiff.h - AST differencing API -----------------------*- C++ -*- -===// |
| // |
| // |
| // Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions. |
| // See https://llvm.org/LICENSE.txt for license information. |
| // SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception |
| // |
| //===----------------------------------------------------------------------===// |
| // |
| // This file specifies an interface that can be used to compare C++ syntax |
| // trees. |
| // |
| // We use the gumtree algorithm which combines a heuristic top-down search that |
| // is able to match large subtrees that are equivalent, with an optimal |
| // algorithm to match small subtrees. |
| // |
| //===----------------------------------------------------------------------===// |
| |
| #ifndef LLVM_CLANG_TOOLING_ASTDIFF_ASTDIFF_H |
| #define LLVM_CLANG_TOOLING_ASTDIFF_ASTDIFF_H |
| |
| #include "clang/Tooling/ASTDiff/ASTDiffInternal.h" |
| |
| namespace clang { |
| namespace diff { |
| |
| enum ChangeKind { |
| None, |
| Delete, // (Src): delete node Src. |
| Update, // (Src, Dst): update the value of node Src to match Dst. |
| Insert, // (Src, Dst, Pos): insert Src as child of Dst at offset Pos. |
| Move, // (Src, Dst, Pos): move Src to be a child of Dst at offset Pos. |
| UpdateMove // Same as Move plus Update. |
| }; |
| |
| /// Represents a Clang AST node, alongside some additional information. |
| struct Node { |
| NodeId Parent, LeftMostDescendant, RightMostDescendant; |
| int Depth, Height, Shift = 0; |
| ast_type_traits::DynTypedNode ASTNode; |
| SmallVector<NodeId, 4> Children; |
| ChangeKind Change = None; |
| |
| ast_type_traits::ASTNodeKind getType() const; |
| StringRef getTypeLabel() const; |
| bool isLeaf() const { return Children.empty(); } |
| llvm::Optional<StringRef> getIdentifier() const; |
| llvm::Optional<std::string> getQualifiedIdentifier() const; |
| }; |
| |
| class ASTDiff { |
| public: |
| ASTDiff(SyntaxTree &Src, SyntaxTree &Dst, const ComparisonOptions &Options); |
| ~ASTDiff(); |
| |
| // Returns the ID of the node that is mapped to the given node in SourceTree. |
| NodeId getMapped(const SyntaxTree &SourceTree, NodeId Id) const; |
| |
| class Impl; |
| |
| private: |
| std::unique_ptr<Impl> DiffImpl; |
| }; |
| |
| /// SyntaxTree objects represent subtrees of the AST. |
| /// They can be constructed from any Decl or Stmt. |
| class SyntaxTree { |
| public: |
| /// Constructs a tree from a translation unit. |
| SyntaxTree(ASTContext &AST); |
| /// Constructs a tree from any AST node. |
| template <class T> |
| SyntaxTree(T *Node, ASTContext &AST) |
| : TreeImpl(llvm::make_unique<Impl>(this, Node, AST)) {} |
| SyntaxTree(SyntaxTree &&Other) = default; |
| ~SyntaxTree(); |
| |
| const ASTContext &getASTContext() const; |
| StringRef getFilename() const; |
| |
| int getSize() const; |
| NodeId getRootId() const; |
| using PreorderIterator = NodeId; |
| PreorderIterator begin() const; |
| PreorderIterator end() const; |
| |
| const Node &getNode(NodeId Id) const; |
| int findPositionInParent(NodeId Id) const; |
| |
| // Returns the starting and ending offset of the node in its source file. |
| std::pair<unsigned, unsigned> getSourceRangeOffsets(const Node &N) const; |
| |
| /// Serialize the node attributes to a string representation. This should |
| /// uniquely distinguish nodes of the same kind. Note that this function just |
| /// returns a representation of the node value, not considering descendants. |
| std::string getNodeValue(NodeId Id) const; |
| std::string getNodeValue(const Node &Node) const; |
| |
| class Impl; |
| std::unique_ptr<Impl> TreeImpl; |
| }; |
| |
| struct ComparisonOptions { |
| /// During top-down matching, only consider nodes of at least this height. |
| int MinHeight = 2; |
| |
| /// During bottom-up matching, match only nodes with at least this value as |
| /// the ratio of their common descendants. |
| double MinSimilarity = 0.5; |
| |
| /// Whenever two subtrees are matched in the bottom-up phase, the optimal |
| /// mapping is computed, unless the size of either subtrees exceeds this. |
| int MaxSize = 100; |
| |
| bool StopAfterTopDown = false; |
| |
| /// Returns false if the nodes should never be matched. |
| bool isMatchingAllowed(const Node &N1, const Node &N2) const { |
| return N1.getType().isSame(N2.getType()); |
| } |
| }; |
| |
| } // end namespace diff |
| } // end namespace clang |
| |
| #endif |