Debian Codegraph @

libcextract/Closure.hh

raw
1 //===- Closure.hh - Compute dependencies of a given symbol *- C++ -*-===//
2 //
3 // This project is licensed under the Apache License v2.0 with LLVM Exceptions.
4 // See https://llvm.org/LICENSE.txt for license information.
5 // SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception
6 //
7 //===----------------------------------------------------------------------===//
8 //
9 /// \file
10 /// Compute a set of Decls that is necessary to compile a given symbol.
11 //
12 //===----------------------------------------------------------------------===//
13
14 /* Author: Giuliano Belinassi */
15
16 #pragma once
17
18 #include <clang/Tooling/Tooling.h>
19 #include <clang/Frontend/ASTUnit.h>
20 #include <clang/Sema/IdentifierResolver.h>
21 #include <clang/AST/RecursiveASTVisitor.h>
22 #include <unordered_set>
23
24 #include "LLVMMisc.hh"
25 #include "PrettyPrint.hh"
26
27 using namespace clang;
28
29 class ClosureSet
30 {
31 public:
32 /** Check if a given declaration was already marked as dependency. */
33 inline bool Is_Decl_Marked(Decl *decl)
34 { return Dependencies.find(decl) != Dependencies.end(); }
35
36 /** Mark decl as dependencies and all its previous decls versions. */
37 bool Add_Decl_And_Prevs(Decl *decl);
38
39 /** Add a single decl to the set. */
40 bool Add_Single_Decl(Decl *decl)
41 {
42 /* Do not insert builtin decls. */
43 if (Is_Builtin_Decl(decl)) {
44 return false;
45 }
46
47 Dependencies.insert(decl);
48 return true;
49 }
50
51 inline std::unordered_set<Decl *> &Get_Set(void)
52 {
53 return Dependencies;
54 }
55
56 inline void Remove_Decl(Decl *decl)
57 {
58 Dependencies.erase(decl);
59 }
60
61 private:
62 /** Datastructure holding all Decls required for the functions. This is
63 then used to mark which Decls we need to output.
64
65 We use a unordered_set because we need quick lookup, so a hash table
66 may be (?) the ideal datastructure for this. */
67 std::unordered_set<Decl*> Dependencies;
68 };
69
70
71 /// AST visitor for computing the closure of given symbol. From clang:
72 ///
73 /// A class that does preorder or postorder
74 /// depth-first traversal on the entire Clang AST and visits each node.
75 ///
76 /// This class performs three distinct tasks:
77 /// 1. traverse the AST (i.e. go to each node);
78 /// 2. at a given node, walk up the class hierarchy, starting from
79 /// the node's dynamic type, until the top-most class (e.g. Stmt,
80 /// Decl, or Type) is reached.
81 /// 3. given a (node, class) combination, where 'class' is some base
82 /// class of the dynamic type of 'node', call a user-overridable
83 /// function to actually visit the node.
84 ///
85 /// These tasks are done by three groups of methods, respectively:
86 /// 1. TraverseDecl(Decl *x) does task #1. It is the entry point
87 /// for traversing an AST rooted at x. This method simply
88 /// dispatches (i.e. forwards) to TraverseFoo(Foo *x) where Foo
89 /// is the dynamic type of *x, which calls WalkUpFromFoo(x) and
90 /// then recursively visits the child nodes of x.
91 /// TraverseStmt(Stmt *x) and TraverseType(QualType x) work
92 /// similarly.
93 /// 2. WalkUpFromFoo(Foo *x) does task #2. It does not try to visit
94 /// any child node of x. Instead, it first calls WalkUpFromBar(x)
95 /// where Bar is the direct parent class of Foo (unless Foo has
96 /// no parent), and then calls VisitFoo(x) (see the next list item).
97 /// 3. VisitFoo(Foo *x) does task #3.
98 ///
99 /// These three method groups are tiered (Traverse* > WalkUpFrom* >
100 /// Visit*). A method (e.g. Traverse*) may call methods from the same
101 /// tier (e.g. other Traverse*) or one tier lower (e.g. WalkUpFrom*).
102 /// It may not call methods from a higher tier.
103 ///
104 /// Note that since WalkUpFromFoo() calls WalkUpFromBar() (where Bar
105 /// is Foo's super class) before calling VisitFoo(), the result is
106 /// that the Visit*() methods for a given node are called in the
107 /// top-down order (e.g. for a node of type NamespaceDecl, the order will
108 /// be VisitDecl(), VisitNamedDecl(), and then VisitNamespaceDecl()).
109 ///
110 /// This scheme guarantees that all Visit*() calls for the same AST
111 /// node are grouped together. In other words, Visit*() methods for
112 /// different nodes are never interleaved.
113 ///
114 /// Clients of this visitor should subclass the visitor (providing
115 /// themselves as the template argument, using the curiously recurring
116 /// template pattern) and override any of the Traverse*, WalkUpFrom*,
117 /// and Visit* methods for declarations, types, statements,
118 /// expressions, or other AST nodes where the visitor should customize
119 /// behavior. Most users only need to override Visit*. Advanced
120 /// users may override Traverse* and WalkUpFrom* to implement custom
121 /// traversal strategies. Returning false from one of these overridden
122 /// functions will abort the entire traversal.
123 ///
124 /// By default, this visitor tries to visit every part of the explicit
125 /// source code exactly once. The default policy towards templates
126 /// is to descend into the 'pattern' class or function body, not any
127 /// explicit or implicit instantiations. Explicit specializations
128 /// are still visited, and the patterns of partial specializations
129 /// are visited separately. This behavior can be changed by
130 /// overriding shouldVisitTemplateInstantiations() in the derived class
131 /// to return true, in which case all known implicit and explicit
132 /// instantiations will be visited at the same time as the pattern
133 /// from which they were produced.
134 ///
135 /// By default, this visitor preorder traverses the AST. If postorder traversal
136 /// is needed, the \c shouldTraversePostOrder method needs to be overridden
137 /// to return \c true.
138 class DeclClosureVisitor : public RecursiveASTVisitor<DeclClosureVisitor>
139 {
140 public:
141 DeclClosureVisitor(ASTUnit *ast)
142 : RecursiveASTVisitor(),
143 AST(ast),
144 Closure(),
145 AnalyzedDecls(),
146 Stack()
147 {
148 }
149
150 /* ---------------- Administrative stuff --------------- */
151
152 /** Tell the RecursiveASTVisitor that we want to visit template instantiations. */
153 bool shouldVisitTemplateInstantiations(void) const //override
154 {
155 return true;
156 }
157
158 /** Check if the Decl was already analyized. */
159 inline bool Already_Analyzed(Decl *decl)
160 {
161 return AnalyzedDecls.find(decl) != AnalyzedDecls.end();
162 }
163
164 inline void Mark_As_Analyzed(Decl *decl)
165 {
166 AnalyzedDecls.insert(decl);
167 }
168
169 enum {
170 VISITOR_CONTINUE = true, // Return this for the AST transversal to continue;
171 VISITOR_STOP = false, // Return this for the AST tranversal to stop completely;
172 };
173
174
175 /* Special Traversal functions which marks if a Decl was already analyzed.
176 Override of TraverseDecl that marks that the given Decl was analyzed. So
177 far it seems we only need this function for now. */
178 bool TraverseDecl(Decl *decl);
179
180 /* -------- C Declarations ----------------- */
181
182 bool VisitFunctionDecl(FunctionDecl *decl);
183
184 bool VisitDeclaratorDecl(DeclaratorDecl *decl);
185
186 bool VisitValueDecl(ValueDecl *decl);
187
188 bool VisitRecordDecl(RecordDecl *decl);
189
190 bool VisitEnumDecl(EnumDecl *decl);
191
192 bool VisitTagDecl(TagDecl *decl);
193
194 bool VisitEnumConstantDecl(EnumConstantDecl *decl);
195
196 /* Not called automatically by Transverse. */
197 bool VisitTypedefNameDecl(TypedefNameDecl *decl);
198
199 bool VisitVarDecl(VarDecl *decl);
200
201 /* --------- C++ Declarations ---------- */
202
203 bool VisitFunctionTemplateDecl(FunctionTemplateDecl *decl);
204
205 bool VisitTemplateDecl(TemplateDecl *decl);
206
207 bool VisitNamespaceDecl(NamespaceDecl *decl);
208
209 bool VisitCXXRecordDecl(CXXRecordDecl *decl);
210
211 bool VisitClassTemplateDecl(ClassTemplateDecl *decl);
212
213 bool VisitClassTemplateSpecializationDecl(ClassTemplateSpecializationDecl *decl);
214
215 /* ----------- Statements -------------- */
216
217 bool VisitDeclRefExpr(DeclRefExpr *expr);
218
219 bool VisitOffsetOfExpr(OffsetOfExpr *expr);
220
221 bool VisitConvertVectorExpr(const ConvertVectorExpr *expr);
222
223 bool VisitUnaryOperator(const UnaryOperator *expr);
224
225 /* --------- Attributes ----------- */
226 bool VisitCleanupAttr(const CleanupAttr *attr);
227
228 /* -------- Types ----------------- */
229 bool VisitTagType(const TagType *type);
230
231 bool VisitTypedefType(const TypedefType *type);
232
233 /* -------- C++ Types ------------- */
234 bool VisitTemplateSpecializationType(const TemplateSpecializationType *type);
235
236 bool VisitDeducedTemplateSpecializationType(
237 const DeducedTemplateSpecializationType *type);
238
239 /* ----------- Other C++ stuff ----------- */
240 bool TraverseNestedNameSpecifier(NestedNameSpecifier *nns);
241
242 bool TraverseCXXBaseSpecifier(const CXXBaseSpecifier base);
243
244 /* ------ Helper Functions ------ */
245
246 bool ParentRecordDeclHelper(TagDecl *decl);
247
248 bool AnalyzeDeclsWithSameBeginlocHelper(Decl *decl);
249
250 bool AnalyzePreviousDecls(Decl *decl);
251
252 ClosureSet &Get_Closure(void)
253 {
254 return Closure;
255 }
256
257 const ClosureSet &Get_Closure(void) const
258 {
259 return Closure;
260 }
261
262 void Compute_Closure_Of_Symbols(const std::vector<std::string> &names,
263 std::unordered_set<std::string> *matched_names = nullptr);
264
265 private:
266
267 /** The ASTUnit object. */
268 ASTUnit *AST;
269
270 /** Datastructure holding all Decls required for the functions. This is
271 then used to mark which Decls we need to output.
272
273 We use a unordered_set because we need quick lookup, so a hash table
274 may be (?) the ideal datastructure for this. */
275 ClosureSet Closure;
276
277 /** The set of all analyzed Decls. */
278 std::unordered_set<Decl *> AnalyzedDecls;
279
280 /** Stack of Decls. Implement using a vector because we may need to access
281 the second element on the top, and we also need its continuity. */
282 llvm::SmallVector<Decl *, 128> Stack;
283
284 /** Return what is on top of our stack. */
285 inline Decl *Stack_Top(void)
286 {
287 return Stack[Stack.size() - 1];
288 }
289 };