Tooling/ASTDiff/ASTDiff.h

0001 //===- ASTDiff.h - AST differencing API -----------------------*- C++ -*- -===//
0002 //
0003 //
0004 // Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.
0005 // See https://llvm.org/LICENSE.txt for license information.
0006 // SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception
0007 //
0008 //===----------------------------------------------------------------------===//
0009 //
0010 // This file specifies an interface that can be used to compare C++ syntax
0011 // trees.
0012 //
0013 // We use the gumtree algorithm which combines a heuristic top-down search that
0014 // is able to match large subtrees that are equivalent, with an optimal
0015 // algorithm to match small subtrees.
0016 //
0017 //===----------------------------------------------------------------------===//
0018
0019 #ifndef LLVM_CLANG_TOOLING_ASTDIFF_ASTDIFF_H
0020 #define LLVM_CLANG_TOOLING_ASTDIFF_ASTDIFF_H
0021
0022 #include "clang/Tooling/ASTDiff/ASTDiffInternal.h"
0023 #include <optional>
0024
0025 namespace clang {
0026 namespace diff {
0027
0028 enum ChangeKind {
0029   None,
0030   Delete,    // (Src): delete node Src.
0031   Update,    // (Src, Dst): update the value of node Src to match Dst.
0032   Insert,    // (Src, Dst, Pos): insert Src as child of Dst at offset Pos.
0033   Move,      // (Src, Dst, Pos): move Src to be a child of Dst at offset Pos.
0034   UpdateMove // Same as Move plus Update.
0035 };
0036
0037 /// Represents a Clang AST node, alongside some additional information.
0038 struct Node {
0039   NodeId Parent, LeftMostDescendant, RightMostDescendant;
0040   int Depth, Height, Shift = 0;
0041   DynTypedNode ASTNode;
0042   SmallVector<NodeId, 4> Children;
0043   ChangeKind Change = None;
0044
0045   ASTNodeKind getType() const;
0046   StringRef getTypeLabel() const;
0047   bool isLeaf() const { return Children.empty(); }
0048   std::optional<StringRef> getIdentifier() const;
0049   std::optional<std::string> getQualifiedIdentifier() const;
0050 };
0051
0052 /// SyntaxTree objects represent subtrees of the AST.
0053 /// They can be constructed from any Decl or Stmt.
0054 class SyntaxTree {
0055 public:
0056   /// Constructs a tree from a translation unit.
0057   SyntaxTree(ASTContext &AST);
0058   /// Constructs a tree from any AST node.
0059   template <class T>
0060   SyntaxTree(T *Node, ASTContext &AST)
0061       : TreeImpl(std::make_unique<Impl>(this, Node, AST)) {}
0062   SyntaxTree(SyntaxTree &&Other) = default;
0063   ~SyntaxTree();
0064
0065   const ASTContext &getASTContext() const;
0066   StringRef getFilename() const;
0067
0068   int getSize() const;
0069   NodeId getRootId() const;
0070   using PreorderIterator = NodeId;
0071   PreorderIterator begin() const;
0072   PreorderIterator end() const;
0073
0074   const Node &getNode(NodeId Id) const;
0075   int findPositionInParent(NodeId Id) const;
0076
0077   // Returns the starting and ending offset of the node in its source file.
0078   std::pair<unsigned, unsigned> getSourceRangeOffsets(const Node &N) const;
0079
0080   /// Serialize the node attributes to a string representation. This should
0081   /// uniquely distinguish nodes of the same kind. Note that this function just
0082   /// returns a representation of the node value, not considering descendants.
0083   std::string getNodeValue(NodeId Id) const;
0084   std::string getNodeValue(const Node &Node) const;
0085
0086   class Impl;
0087   std::unique_ptr<Impl> TreeImpl;
0088 };
0089
0090 struct ComparisonOptions {
0091   /// During top-down matching, only consider nodes of at least this height.
0092   int MinHeight = 2;
0093
0094   /// During bottom-up matching, match only nodes with at least this value as
0095   /// the ratio of their common descendants.
0096   double MinSimilarity = 0.5;
0097
0098   /// Whenever two subtrees are matched in the bottom-up phase, the optimal
0099   /// mapping is computed, unless the size of either subtrees exceeds this.
0100   int MaxSize = 100;
0101
0102   bool StopAfterTopDown = false;
0103
0104   /// Returns false if the nodes should never be matched.
0105   bool isMatchingAllowed(const Node &N1, const Node &N2) const {
0106     return N1.getType().isSame(N2.getType());
0107   }
0108 };
0109
0110 class ASTDiff {
0111 public:
0112   ASTDiff(SyntaxTree &Src, SyntaxTree &Dst, const ComparisonOptions &Options);
0113   ~ASTDiff();
0114
0115   // Returns the ID of the node that is mapped to the given node in SourceTree.
0116   NodeId getMapped(const SyntaxTree &SourceTree, NodeId Id) const;
0117
0118   class Impl;
0119
0120 private:
0121   std::unique_ptr<Impl> DiffImpl;
0122 };
0123
0124 } // end namespace diff
0125 } // end namespace clang
0126
0127 #endif