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 /// SyntaxTree objects represent subtrees of the AST.
52 /// They can be constructed from any Decl or Stmt.
53 class SyntaxTree {
54 public:
55   /// Constructs a tree from a translation unit.
56   SyntaxTree(ASTContext &AST);
57   /// Constructs a tree from any AST node.
58   template <class T>
59   SyntaxTree(T *Node, ASTContext &AST)
60       : TreeImpl(std::make_unique<Impl>(this, Node, AST)) {}
61   SyntaxTree(SyntaxTree &&Other) = default;
62   ~SyntaxTree();
63 
64   const ASTContext &getASTContext() const;
65   StringRef getFilename() const;
66 
67   int getSize() const;
68   NodeId getRootId() const;
69   using PreorderIterator = NodeId;
70   PreorderIterator begin() const;
71   PreorderIterator end() const;
72 
73   const Node &getNode(NodeId Id) const;
74   int findPositionInParent(NodeId Id) const;
75 
76   // Returns the starting and ending offset of the node in its source file.
77   std::pair<unsigned, unsigned> getSourceRangeOffsets(const Node &N) const;
78 
79   /// Serialize the node attributes to a string representation. This should
80   /// uniquely distinguish nodes of the same kind. Note that this function just
81   /// returns a representation of the node value, not considering descendants.
82   std::string getNodeValue(NodeId Id) const;
83   std::string getNodeValue(const Node &Node) const;
84 
85   class Impl;
86   std::unique_ptr<Impl> TreeImpl;
87 };
88 
89 struct ComparisonOptions {
90   /// During top-down matching, only consider nodes of at least this height.
91   int MinHeight = 2;
92 
93   /// During bottom-up matching, match only nodes with at least this value as
94   /// the ratio of their common descendants.
95   double MinSimilarity = 0.5;
96 
97   /// Whenever two subtrees are matched in the bottom-up phase, the optimal
98   /// mapping is computed, unless the size of either subtrees exceeds this.
99   int MaxSize = 100;
100 
101   bool StopAfterTopDown = false;
102 
103   /// Returns false if the nodes should never be matched.
104   bool isMatchingAllowed(const Node &N1, const Node &N2) const {
105     return N1.getType().isSame(N2.getType());
106   }
107 };
108 
109 class ASTDiff {
110 public:
111   ASTDiff(SyntaxTree &Src, SyntaxTree &Dst, const ComparisonOptions &Options);
112   ~ASTDiff();
113 
114   // Returns the ID of the node that is mapped to the given node in SourceTree.
115   NodeId getMapped(const SyntaxTree &SourceTree, NodeId Id) const;
116 
117   class Impl;
118 
119 private:
120   std::unique_ptr<Impl> DiffImpl;
121 };
122 
123 } // end namespace diff
124 } // end namespace clang
125 
126 #endif
127