Home | History | Annotate | Line # | Download | only in ASTDiff 
      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   DynTypedNode ASTNode;
     41   SmallVector<NodeId, 4> Children;
     42   ChangeKind Change = None;
     43 
     44   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(std::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
    127