Subversion Repositories QNX 8.QNX8 LLVM/Clang compiler suite

Rev

Blame | Last modification | View Log | Download | RSS feed

  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
  128.