ASTDiff.h revision 360784 
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
24namespace clang {
25namespace diff {
26
27enum 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.
37struct Node {
38  NodeId Parent, LeftMostDescendant, RightMostDescendant;
39  int Depth, Height, Shift = 0;
40  ast_type_traits::DynTypedNode ASTNode;
41  SmallVector<NodeId, 4> Children;
42  ChangeKind Change = None;
43
44  ast_type_traits::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
51class ASTDiff {
52public:
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
61private:
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.
67class SyntaxTree {
68public:
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
103struct 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