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
25namespace clang {
26namespace diff {
27
28enum 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.
38struct 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;
47  bool isLeaf() const { return Children.empty(); }
48  llvm::Optional<StringRef> getIdentifier() const;
49  llvm::Optional<std::string> getQualifiedIdentifier() const;
50};
51
52class ASTDiff {
53public:
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
62private:
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.
68class SyntaxTree {
69public:
70  /// Constructs a tree from a translation unit.
71  SyntaxTree(ASTContext &AST);
72  /// Constructs a tree from any AST node.
73  template <class T>
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
104struct 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.
119  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