1 //===- ASTDiff.h - AST differencing API -----------------------*- C++ -*- -===//
2 //
3 //
4 //                     The LLVM Compiler Infrastructure
5 //
6 // This file is distributed under the University of Illinois Open Source
7 // License. See LICENSE.TXT for details.
8 //
9 //===----------------------------------------------------------------------===//
10 //
11 // This file specifies an interface that can be used to compare C++ syntax
12 // trees.
13 //
14 // We use the gumtree algorithm which combines a heuristic top-down search that
15 // is able to match large subtrees that are equivalent, with an optimal
16 // algorithm to match small subtrees.
17 //
18 //===----------------------------------------------------------------------===//
19 
20 #ifndef LLVM_CLANG_TOOLING_ASTDIFF_ASTDIFF_H
21 #define LLVM_CLANG_TOOLING_ASTDIFF_ASTDIFF_H
22 
23 #include "clang/Tooling/ASTDiff/ASTDiffInternal.h"
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   ast_type_traits::DynTypedNode ASTNode;
42   SmallVector<NodeId, 4> Children;
43   ChangeKind Change = None;
44 
45   ast_type_traits::ASTNodeKind getType() const;
46   StringRef getTypeLabel() const;
isLeafNode47   bool isLeaf() const { return Children.empty(); }
48   llvm::Optional<StringRef> getIdentifier() const;
49   llvm::Optional<std::string> getQualifiedIdentifier() const;
50 };
51 
52 class ASTDiff {
53 public:
54   ASTDiff(SyntaxTree &Src, SyntaxTree &Dst, const ComparisonOptions &Options);
55   ~ASTDiff();
56 
57   // Returns the ID of the node that is mapped to the given node in SourceTree.
58   NodeId getMapped(const SyntaxTree &SourceTree, NodeId Id) const;
59 
60   class Impl;
61 
62 private:
63   std::unique_ptr<Impl> DiffImpl;
64 };
65 
66 /// SyntaxTree objects represent subtrees of the AST.
67 /// They can be constructed from any Decl or Stmt.
68 class SyntaxTree {
69 public:
70   /// Constructs a tree from a translation unit.
71   SyntaxTree(ASTContext &AST);
72   /// Constructs a tree from any AST node.
73   template <class T>
SyntaxTree(T * Node,ASTContext & AST)74   SyntaxTree(T *Node, ASTContext &AST)
75       : TreeImpl(llvm::make_unique<Impl>(this, Node, AST)) {}
76   SyntaxTree(SyntaxTree &&Other) = default;
77   ~SyntaxTree();
78 
79   const ASTContext &getASTContext() const;
80   StringRef getFilename() const;
81 
82   int getSize() const;
83   NodeId getRootId() const;
84   using PreorderIterator = NodeId;
85   PreorderIterator begin() const;
86   PreorderIterator end() const;
87 
88   const Node &getNode(NodeId Id) const;
89   int findPositionInParent(NodeId Id) const;
90 
91   // Returns the starting and ending offset of the node in its source file.
92   std::pair<unsigned, unsigned> getSourceRangeOffsets(const Node &N) const;
93 
94   /// Serialize the node attributes to a string representation. This should
95   /// uniquely distinguish nodes of the same kind. Note that this function just
96   /// returns a representation of the node value, not considering descendants.
97   std::string getNodeValue(NodeId Id) const;
98   std::string getNodeValue(const Node &Node) const;
99 
100   class Impl;
101   std::unique_ptr<Impl> TreeImpl;
102 };
103 
104 struct ComparisonOptions {
105   /// During top-down matching, only consider nodes of at least this height.
106   int MinHeight = 2;
107 
108   /// During bottom-up matching, match only nodes with at least this value as
109   /// the ratio of their common descendants.
110   double MinSimilarity = 0.5;
111 
112   /// Whenever two subtrees are matched in the bottom-up phase, the optimal
113   /// mapping is computed, unless the size of either subtrees exceeds this.
114   int MaxSize = 100;
115 
116   bool StopAfterTopDown = false;
117 
118   /// Returns false if the nodes should never be matched.
isMatchingAllowedComparisonOptions119   bool isMatchingAllowed(const Node &N1, const Node &N2) const {
120     return N1.getType().isSame(N2.getType());
121   }
122 };
123 
124 } // end namespace diff
125 } // end namespace clang
126 
127 #endif
128