Debian Codegraph @

libcextract/LLVMMisc.cpp

raw
1 //===- LLVMMisc.cpp - Implement misc functions that depends on LLVM *- 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 /// MISC functions that is used through the program and use any LLVM
11 /// datastructure.
12 //
13 //===----------------------------------------------------------------------===//
14
15 /* Author: Giuliano Belinassi */
16
17 #include "LLVMMisc.hh"
18 #include "NonLLVMMisc.hh"
19
20 /** Check if Decl is a builtin. */
21 bool Is_Builtin_Decl(const Decl *decl)
22 {
23 const NamedDecl *ndecl = dyn_cast<const NamedDecl>(decl);
24 if (ndecl) {
25 /* Avoid triggering an assert in clang. */
26 if (ndecl->getDeclName().isIdentifier()) {
27 StringRef name = ndecl->getName();
28 if (name.starts_with("__builtin_")) {
29 return true;
30 }
31
32 if (name.starts_with("__compiletime_assert_")) {
33 return true;
34 }
35 }
36 }
37
38 return false;
39 }
40
41 /** Build CallGraph from AST.
42 *
43 * The CallGraph is a datastructure in which nodes are functions and edges
44 * represents function call points. For example:
45 *
46 * void f();
47 * void g() { f(); f(); }
48 *
49 * Resuluts in the following CallGraph:
50 *
51 * (f) -> (g)
52 * -> (g)
53 *
54 * There are two edges to `g` because there are two callpoints to it.
55 * Hence, the resulting graph is not `simple` in Graph Theory nomenclature. But
56 * for the analysis we are doing it is suffice to be, so perhaps some extra
57 * performance can be archived if we could remove duplicated edges.
58 *
59 */
60 CallGraph *Build_CallGraph_From_AST(ASTUnit *ast)
61 {
62 CallGraph *cg = new CallGraph();
63 cg->TraverseAST(ast->getASTContext());
64
65 return cg;
66 }
67
68
69 FunctionDecl *Get_Bodyless_Decl(FunctionDecl *decl)
70 {
71 while (decl) {
72 if (decl->hasBody()) {
73 decl = decl->getPreviousDecl();
74 } else {
75 return decl;
76 }
77 }
78
79 return nullptr;
80 }
81
82 FunctionDecl *Get_Bodyless_Or_Itself(FunctionDecl *decl)
83 {
84 FunctionDecl *bodyless = Get_Bodyless_Decl(decl);
85 return bodyless ? bodyless : decl;
86 }
87
88 TagDecl *Get_Bodyless_Decl(TagDecl *decl)
89 {
90 while (decl) {
91 if (decl->isCompleteDefinition()) {
92 decl = decl->getPreviousDecl();
93 } else {
94 return decl;
95 }
96 }
97
98 return nullptr;
99 }
100
101 TagDecl *Get_Bodyless_Or_Itself(TagDecl *decl)
102 {
103 TagDecl *bodyless = Get_Bodyless_Decl(decl);
104 return bodyless ? bodyless : decl;
105 }
106
107 Decl *Get_Bodyless_Decl(Decl *decl)
108 {
109 if (TagDecl *tag = dyn_cast<TagDecl>(decl)) {
110 return Get_Bodyless_Decl(tag);
111 } else if (FunctionDecl *func = dyn_cast<FunctionDecl>(decl)) {
112 return Get_Bodyless_Decl(func);
113 }
114
115 return nullptr;
116 }
117
118 Decl *Get_Bodyless_Or_Itself(Decl *decl)
119 {
120 Decl *bodyless = Get_Bodyless_Decl(decl);
121 return bodyless ? bodyless : decl;
122 }
123
124 DeclaratorDecl *Get_With_Body(DeclaratorDecl *decl)
125 {
126 if (FunctionDecl *fdecl = dyn_cast<FunctionDecl>(decl)) {
127 return fdecl->getDefinition();
128 }
129
130 if (VarDecl *vdecl = dyn_cast<VarDecl>(decl)) {
131 return vdecl->getDefinition();
132 }
133
134 return nullptr;
135 }
136
137 DeclaratorDecl *Get_With_Body_Or_Itself(DeclaratorDecl *decl)
138 {
139 DeclaratorDecl *with_body = Get_With_Body(decl);
140 return with_body ? with_body : decl;
141 }
142
143 /* Get the TopLevel Decl that contains the location loc. */
144 Decl *Get_Toplevel_Decl_At_Location(ASTUnit *ast, const SourceLocation &loc)
145 {
146 SourceManager &SM = ast->getSourceManager();
147 /* We don't have a way of accessing the TopLevel vector directly, hence we
148 do this. */
149 char *p = (char *) &(*ast->top_level_begin());
150 char *q = (char *) &(*ast->top_level_end());
151
152 int n = (((ptrdiff_t)(q - p))/sizeof(Decl *));
153
154 Decl **array = (Decl **)p;
155
156 /* Do binary search. */
157 int low = 0;
158 int high = n-1;
159 while (low <= high) {
160 int mid = low + (high - low)/2;
161
162 Decl *decl = array[mid];
163 /* Get rid of some weird macro locations. We want the location where
164 it was expanded. */
165 SourceRange decl_range(SM.getExpansionLoc(decl->getBeginLoc()),
166 SM.getExpansionLoc(decl->getEndLoc()));
167
168 if (decl_range.fullyContains(loc)) {
169 return decl;
170 }
171
172 if (SM.isBeforeInTranslationUnit(decl_range.getBegin(), loc)) {
173 low = mid + 1;
174 } else {
175 high = mid - 1;
176 }
177 }
178
179 return nullptr;
180 }
181
182 ArrayRef<Decl *> Get_Toplev_Decls_With_Same_Beginloc(ASTUnit *ast, const SourceLocation &loc)
183 {
184 SourceManager &SM = ast->getSourceManager();
185 /* We don't have a way of accessing the TopLevel vector directly, hence we
186 do this. */
187 char *p = (char *) &(*ast->top_level_begin());
188 char *q = (char *) &(*ast->top_level_end());
189
190 int n = (((ptrdiff_t)(q - p))/sizeof(Decl *));
191
192 Decl **array = (Decl **)p;
193
194 /* Do binary search. */
195 int low = 0;
196 int high = n-1;
197 while (low <= high) {
198 int mid = low + (high - low)/2;
199
200 Decl *decl = array[mid];
201 /* Get rid of some weird macro locations. We want the location where
202 it was expanded. */
203 SourceLocation begin = SM.getExpansionLoc(decl->getBeginLoc());
204
205 if (begin == loc) {
206 /* Go back to the first declaration. */
207 int last_l = mid;
208 for (int l = mid; l >= 0; --l) {
209 if (SM.getExpansionLoc(array[l]->getBeginLoc()) == loc) {
210 last_l = l;
211 } else {
212 break;
213 }
214 }
215
216 /* Go forward to the last declaration. */
217 int last_h = mid;
218 for (int h = mid; h < n; ++h) {
219 if (SM.getExpansionLoc(array[h]->getBeginLoc()) == loc) {
220 last_h = h;
221 } else {
222 break;
223 }
224 }
225
226 return ArrayRef(&array[last_l], &array[last_h+1]);
227 }
228
229 if (SM.isBeforeInTranslationUnit(begin, loc)) {
230 low = mid + 1;
231 } else {
232 high = mid - 1;
233 }
234 }
235
236 return ArrayRef<Decl *>(nullptr, size_t(0));
237 }
238
239 std::string Build_CE_Location_Comment(SourceManager &sm, const SourceLocation &loc)
240 {
241 PresumedLoc presumed = sm.getPresumedLoc(loc);
242 unsigned line = presumed.getLine();
243 unsigned col = presumed.getColumn();
244 const char *filename = presumed.getFilename();
245
246 std::string comment = "/** clang-extract: from " + std::string(filename) + ":" +
247 std::to_string(line) + ":" + std::to_string(col) + " */\n";
248 return comment;
249 }
250
251 /** Get decl clang-extract location comment, or build one if it doesn't exist. */
252 std::string Get_Or_Build_CE_Location_Comment(ASTContext &ctx, Decl *decl)
253 {
254 SourceManager &sm = ctx.getSourceManager();
255 RawComment *comment = ctx.getRawCommentForDeclNoCache(decl);
256 if (Have_Location_Comment(sm, comment)) {
257 return comment->getRawText(sm).str();;
258 } else {
259 return Build_CE_Location_Comment(sm, decl->getBeginLoc());
260 }
261 }
262
263 /** Get the begin location of the Decl before its comment if it have one. */
264 SourceLocation Get_Begin_Loc_Of_Decl_Or_Comment(ASTContext &ctx, Decl *decl)
265 {
266 if (RawComment *comment = ctx.getRawCommentForDeclNoCache(decl)) {
267 return comment->getBeginLoc();
268 } else {
269 return decl->getBeginLoc();
270 }
271 }
272
273 /** Check if Decl have a Location comment. */
274 bool Have_Location_Comment(const SourceManager &sm, RawComment *comment)
275 {
276 if (comment) {
277 StringRef text = comment->getRawText(sm);
278 if (prefix("/** clang-extract: from ", text.data())) {
279 return true;
280 }
281 }
282 return false;
283 }
284
285 /** Lookup in the symbol table for a declaration with given name passed by info. */
286 DeclContextLookupResult Get_Decl_From_Symtab(ASTUnit *ast, const IdentifierInfo *info)
287 {
288 TranslationUnitDecl *tu = ast->getASTContext().getTranslationUnitDecl();
289 return tu->lookup(DeclarationName(info));
290 }
291
292 /** Lookup in the symbol table for a declaration with given name passed by name. */
293 DeclContextLookupResult Get_Decl_From_Symtab(ASTUnit *ast, const StringRef &name)
294 {
295 IdentifierTable &symtab = ast->getPreprocessor().getIdentifierTable();
296 auto info = symtab.find(name);
297 /* Return an empty DeclContextLookupResult if the identifier is not found */
298 if (info == symtab.end())
299 return DeclContextLookupResult();
300
301 return Get_Decl_From_Symtab(ast, info->getValue());
302 }
303
304 /** Check if two Decls are equivalent. */
305 bool Is_Decl_Equivalent_To(Decl *a, Decl *b)
306 {
307 std::string a_str;
308 std::string b_str;
309
310 llvm::raw_string_ostream a_stream(a_str);
311 llvm::raw_string_ostream b_stream(b_str);
312
313 a->print(a_stream);
314 b->print(b_stream);
315
316 return a_str == b_str;
317 }
318
319 #define TOKEN_VECTOR " ().,;+-*/^|&{}[]<>^&|!\r\n\t"
320
321 /** Check if string has unmatched #if, #ifdef, #ifndef. */
322 bool Has_Balanced_Ifdef(const StringRef &string)
323 {
324 /* Create a temporary buffer for strtok and copy the string. */
325 size_t len = string.size();
326 char buf[len + 1];
327 memcpy(buf, string.data(), len);
328 buf[len] = '\0';
329
330 /* Count the number of parenthesis problem. ifdef, ifndef, if increases,
331 endif decreases. */
332 int balance = 0;
333
334 /* Tokenize. */
335 char *tok = strtok(buf, TOKEN_VECTOR);
336 while (tok != nullptr) {
337 /* There is the silly case in which #ifdef is written as `# ifdef`. */
338 if (*tok == '#') {
339 /* Now check if it got into the same token or if we need to pull another
340 token. */
341 if (tok[1] == '\0') {
342 tok = strtok(nullptr, TOKEN_VECTOR);
343 } else {
344 tok++;
345 }
346
347 assert(tok != nullptr && "tok is null! why?");
348
349 /* Case 1: #ifdef, #ifndef, and #if has "if" as prefix. */
350 if (prefix("if", tok)) {
351 balance++;
352 }
353
354 /* Case 2: #endif. Decrease the balance counter. */
355 else if (strcmp("endif", tok) == 0) {
356 balance--;
357 if (balance < 0) {
358 /* Impossible. This means there is an #endif for no matching #if. */
359 return false;
360 }
361 }
362 }
363
364 tok = strtok(nullptr, TOKEN_VECTOR);
365 }
366
367 return balance == 0;
368 }