Details | Last modification | View Log | RSS feed
| Rev | Author | Line No. | Line |
|---|---|---|---|
| 14 | pmbaty | 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; |
||
| 47 | 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> |
||
| 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. |
||
| 105 | 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 |