contrib/llvm/tools/clang/include/clang/Tooling/ASTDiff/ASTDiff.h

   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
  24 namespace clang {
  25 namespace diff {
  26
  27 enum ChangeKind {
  28   None,
  29   Delete,    // (Src): delete node Src.
  30   Update,    // (Src, Dst): update the value of node Src to match Dst.
  31   Insert,    // (Src, Dst, Pos): insert Src as child of Dst at offset Pos.
  32   Move,      // (Src, Dst, Pos): move Src to be a child of Dst at offset Pos.
  33   UpdateMove // Same as Move plus Update.
  34 };
  35
  36 /// Represents a Clang AST node, alongside some additional information.
  37 struct Node {
  38   NodeId Parent, LeftMostDescendant, RightMostDescendant;
  39   int Depth, Height, Shift = 0;
  40   ast_type_traits::DynTypedNode ASTNode;
  41   SmallVector<NodeId, 4> Children;
  42   ChangeKind Change = None;
  43
  44   ast_type_traits::ASTNodeKind getType() const;
  45   StringRef getTypeLabel() const;
  46   bool isLeaf() const { return Children.empty(); }
  47   llvm::Optional<StringRef> getIdentifier() const;
  48   llvm::Optional<std::string> getQualifiedIdentifier() const;
  49 };
  50
  51 class ASTDiff {
  52 public:
  53   ASTDiff(SyntaxTree &Src, SyntaxTree &Dst, const ComparisonOptions &Options);
  54   ~ASTDiff();
  55
  56   // Returns the ID of the node that is mapped to the given node in SourceTree.
  57   NodeId getMapped(const SyntaxTree &SourceTree, NodeId Id) const;
  58
  59   class Impl;
  60
  61 private:
  62   std::unique_ptr<Impl> DiffImpl;
  63 };
  64
  65 /// SyntaxTree objects represent subtrees of the AST.
  66 /// They can be constructed from any Decl or Stmt.
  67 class SyntaxTree {
  68 public:
  69   /// Constructs a tree from a translation unit.
  70   SyntaxTree(ASTContext &AST);
  71   /// Constructs a tree from any AST node.
  72   template <class T>
  73   SyntaxTree(T *Node, ASTContext &AST)
  74       : TreeImpl(llvm::make_unique<Impl>(this, Node, AST)) {}
  75   SyntaxTree(SyntaxTree &&Other) = default;
  76   ~SyntaxTree();
  77
  78   const ASTContext &getASTContext() const;
  79   StringRef getFilename() const;
  80
  81   int getSize() const;
  82   NodeId getRootId() const;
  83   using PreorderIterator = NodeId;
  84   PreorderIterator begin() const;
  85   PreorderIterator end() const;
  86
  87   const Node &getNode(NodeId Id) const;
  88   int findPositionInParent(NodeId Id) const;
  89
  90   // Returns the starting and ending offset of the node in its source file.
  91   std::pair<unsigned, unsigned> getSourceRangeOffsets(const Node &N) const;
  92
  93   /// Serialize the node attributes to a string representation. This should
  94   /// uniquely distinguish nodes of the same kind. Note that this function just
  95   /// returns a representation of the node value, not considering descendants.
  96   std::string getNodeValue(NodeId Id) const;
  97   std::string getNodeValue(const Node &Node) const;
  98
  99   class Impl;
 100   std::unique_ptr<Impl> TreeImpl;
 101 };
 102
 103 struct ComparisonOptions {
 104   /// During top-down matching, only consider nodes of at least this height.
 105   int MinHeight = 2;
 106
 107   /// During bottom-up matching, match only nodes with at least this value as
 108   /// the ratio of their common descendants.
 109   double MinSimilarity = 0.5;
 110
 111   /// Whenever two subtrees are matched in the bottom-up phase, the optimal
 112   /// mapping is computed, unless the size of either subtrees exceeds this.
 113   int MaxSize = 100;
 114
 115   bool StopAfterTopDown = false;
 116
 117   /// Returns false if the nodes should never be matched.
 118   bool isMatchingAllowed(const Node &N1, const Node &N2) const {
 119     return N1.getType().isSame(N2.getType());
 120   }
 121 };
 122
 123 } // end namespace diff
 124 } // end namespace clang
 125
 126 #endif