1 /*
2 * sparse/dissect.c
3 *
4 * Started by Oleg Nesterov <oleg@redhat.com>
5 *
6 * Permission is hereby granted, free of charge, to any person obtaining a copy
7 * of this software and associated documentation files (the "Software"), to deal
8 * in the Software without restriction, including without limitation the rights
9 * to use, copy, modify, merge, publish, distribute, sublicense, and/or sell
10 * copies of the Software, and to permit persons to whom the Software is
11 * furnished to do so, subject to the following conditions:
12 *
13 * The above copyright notice and this permission notice shall be included in
14 * all copies or substantial portions of the Software.
15 *
16 * THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR
17 * IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY,
18 * FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT. IN NO EVENT SHALL THE
19 * AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER
20 * LIABILITY, WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING FROM,
21 * OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN
22 * THE SOFTWARE.
23 */
24
25 #include "dissect.h"
26
27 #define U_VOID 0x00
28 #define U_SELF ((1 << U_SHIFT) - 1)
29 #define U_MASK (U_R_VAL | U_W_VAL | U_R_AOF)
30
31 #define DO_LIST(l__, p__, expr__) \
32 do { \
33 typeof(l__->list[0]) p__; \
34 FOR_EACH_PTR(l__, p__) \
35 expr__; \
36 END_FOR_EACH_PTR(p__); \
37 } while (0)
38
39 #define DO_2_LIST(l1__,l2__, p1__,p2__, expr__) \
40 do { \
41 typeof(l1__->list[0]) p1__; \
42 typeof(l2__->list[0]) p2__; \
43 PREPARE_PTR_LIST(l1__, p1__); \
44 FOR_EACH_PTR(l2__, p2__) \
45 expr__; \
46 NEXT_PTR_LIST(p1__); \
47 END_FOR_EACH_PTR(p2__); \
48 FINISH_PTR_LIST(p1__); \
49 } while (0)
50
51
52 typedef unsigned usage_t;
53
54 struct symbol *dissect_ctx;
55
56 static struct reporter *reporter;
57
58 static void do_sym_list(struct symbol_list *list);
59
60 static struct symbol
61 *base_type(struct symbol *sym),
62 *do_initializer(struct symbol *type, struct expression *expr),
63 *do_expression(usage_t mode, struct expression *expr),
64 *do_statement(usage_t mode, struct statement *stmt);
65
is_ptr(struct symbol * type)66 static inline int is_ptr(struct symbol *type)
67 {
68 return type->type == SYM_PTR || type->type == SYM_ARRAY;
69 }
70
u_rval(usage_t mode)71 static inline usage_t u_rval(usage_t mode)
72 {
73 return mode & (U_R_VAL | (U_MASK << U_SHIFT))
74 ? U_R_VAL : 0;
75 }
76
u_addr(usage_t mode)77 static inline usage_t u_addr(usage_t mode)
78 {
79 return mode = mode & U_MASK
80 ? U_R_AOF | (mode & U_W_AOF) : 0;
81 }
82
u_lval(struct symbol * type)83 static usage_t u_lval(struct symbol *type)
84 {
85 int wptr = is_ptr(type) && !(type->ctype.modifiers & MOD_CONST);
86 return wptr || type == &bad_ctype
87 ? U_W_AOF | U_R_VAL : U_R_VAL;
88 }
89
fix_mode(struct symbol * type,usage_t mode)90 static usage_t fix_mode(struct symbol *type, usage_t mode)
91 {
92 mode &= (U_SELF | (U_SELF << U_SHIFT));
93
94 switch (type->type) {
95 case SYM_BASETYPE:
96 if (!type->ctype.base_type)
97 break;
98 case SYM_ENUM:
99 case SYM_BITFIELD:
100 if (mode & U_MASK)
101 mode &= U_SELF;
102 default:
103
104 break; case SYM_FN:
105 if (mode & U_R_VAL)
106 mode |= U_R_AOF;
107 mode &= ~(U_R_VAL | U_W_AOF);
108
109 break; case SYM_ARRAY:
110 if (mode & (U_MASK << U_SHIFT))
111 mode >>= U_SHIFT;
112 else if (mode != U_W_VAL)
113 mode = u_addr(mode);
114 }
115
116 if (!(mode & U_R_AOF))
117 mode &= ~U_W_AOF;
118
119 return mode;
120 }
121
report_member(usage_t mode,struct position * pos,struct symbol * type,struct symbol * mem)122 static struct symbol *report_member(usage_t mode, struct position *pos,
123 struct symbol *type, struct symbol *mem)
124 {
125 struct symbol *ret = mem->ctype.base_type;
126
127 if (mem->ident || mem->type == SYM_BAD)
128 reporter->r_member(fix_mode(ret, mode), pos, type, mem);
129
130 return ret;
131 }
132
report_implicit(usage_t mode,struct position * pos,struct symbol * type)133 static void report_implicit(usage_t mode, struct position *pos, struct symbol *type)
134 {
135 if (type->type != SYM_STRUCT && type->type != SYM_UNION)
136 return;
137
138 if (type->ident != NULL)
139 reporter->r_member(mode, pos, type, NULL);
140
141 DO_LIST(type->symbol_list, mem,
142 report_implicit(mode, pos, base_type(mem)));
143 }
144
expr_symbol(struct expression * expr)145 static inline struct symbol *expr_symbol(struct expression *expr)
146 {
147 struct symbol *sym = expr->symbol;
148
149 if (!sym) {
150 sym = lookup_symbol(expr->symbol_name, NS_SYMBOL);
151
152 if (!sym) {
153 sym = alloc_symbol(expr->pos, SYM_BAD);
154 bind_symbol(sym, expr->symbol_name, NS_SYMBOL);
155 sym->kind = expr->op ?: 'v'; /* see EXPR_CALL */
156 }
157 }
158
159 if (!sym->ctype.base_type)
160 sym->ctype.base_type = &bad_ctype;
161
162 return sym;
163 }
164
report_symbol(usage_t mode,struct expression * expr)165 static struct symbol *report_symbol(usage_t mode, struct expression *expr)
166 {
167 struct symbol *sym = expr_symbol(expr);
168 struct symbol *ret = base_type(sym);
169
170 if (0 && ret->type == SYM_ENUM)
171 return report_member(mode, &expr->pos, ret, expr->symbol);
172
173 reporter->r_symbol(fix_mode(ret, mode), &expr->pos, sym);
174
175 return ret;
176 }
177
deanon(struct symbol * base,struct ident * node,struct symbol * parent)178 static bool deanon(struct symbol *base, struct ident *node, struct symbol *parent)
179 {
180 struct ident *pi = parent ? parent->ident : NULL;
181 char name[256];
182
183 if (!node) {
184 base->ident = pi;
185 return false;
186 }
187
188 snprintf(name, sizeof(name), "%.*s:%.*s",
189 pi ? pi->len : 0, pi ? pi->name : NULL, node->len, node->name);
190
191 base->ident = built_in_ident(name);
192 return true;
193 }
194
report_memdef(struct symbol * sym,struct symbol * mem)195 static void report_memdef(struct symbol *sym, struct symbol *mem)
196 {
197 mem->kind = 'm';
198 if (sym && mem->ident)
199 reporter->r_memdef(sym, mem);
200 }
201
examine_sym_node(struct symbol * node,struct symbol * parent)202 static void examine_sym_node(struct symbol *node, struct symbol *parent)
203 {
204 struct ident *name = node->ident;
205 struct symbol *base, *dctx;
206
207 if (node->visited)
208 return;
209 node->visited = 1;
210 node->kind = 'v';
211
212 while ((base = node->ctype.base_type) != NULL)
213 switch (base->type) {
214 case SYM_TYPEOF:
215 node->ctype.base_type =
216 do_expression(U_VOID, base->initializer);
217 break;
218
219 case SYM_ARRAY:
220 do_expression(U_R_VAL, base->array_size);
221 case SYM_PTR:
222 node = base;
223 break;
224
225 case SYM_FN:
226 node->kind = 'f';
227 node = base;
228 break;
229
230 case SYM_STRUCT: case SYM_UNION: //case SYM_ENUM:
231 if (base->inspected)
232 return;
233 base->inspected = 1;
234 base->kind = 's';
235
236 if (!base->symbol_list)
237 return;
238
239 dctx = dissect_ctx;
240 if (toplevel(base->scope))
241 dissect_ctx = NULL;
242
243 if (base->ident || deanon(base, name, parent))
244 reporter->r_symdef(base);
245
246 if (base->ident)
247 parent = base;
248 DO_LIST(base->symbol_list, mem,
249 examine_sym_node(mem, parent);
250 report_memdef(parent, mem));
251 dissect_ctx = dctx;
252 default:
253 return;
254 }
255 }
256
base_type(struct symbol * sym)257 static struct symbol *base_type(struct symbol *sym)
258 {
259 if (!sym)
260 return &bad_ctype;
261
262 if (sym->type == SYM_NODE)
263 examine_sym_node(sym, NULL);
264
265 return sym->ctype.base_type // builtin_fn_type
266 ?: &bad_ctype;
267 }
268
__lookup_member(struct symbol * type,struct ident * name,int * p_addr)269 static struct symbol *__lookup_member(struct symbol *type, struct ident *name, int *p_addr)
270 {
271 struct symbol *node;
272 int addr = 0;
273
274 FOR_EACH_PTR(type->symbol_list, node)
275 if (!name) {
276 if (addr == *p_addr)
277 return node;
278 }
279 else if (node->ident == NULL) {
280 node = __lookup_member(node->ctype.base_type, name, NULL);
281 if (node)
282 goto found;
283 }
284 else if (node->ident == name) {
285 found:
286 if (p_addr)
287 *p_addr = addr;
288 return node;
289 }
290 addr++;
291 END_FOR_EACH_PTR(node);
292
293 return NULL;
294 }
295
lookup_member(struct symbol * type,struct ident * name,int * addr)296 static struct symbol *lookup_member(struct symbol *type, struct ident *name, int *addr)
297 {
298 struct symbol *mem = __lookup_member(type, name, addr);
299
300 if (!mem) {
301 static struct symbol bad_member = {
302 .type = SYM_BAD,
303 .ctype.base_type = &bad_ctype,
304 .kind = 'm',
305 };
306
307 if (!type->symbol_list)
308 type->scope = file_scope;
309
310 mem = &bad_member;
311 mem->ident = name;
312 }
313
314 return mem;
315 }
316
peek_preop(struct expression * expr,int op)317 static struct expression *peek_preop(struct expression *expr, int op)
318 {
319 do {
320 if (expr->type != EXPR_PREOP)
321 break;
322 if (expr->op == op)
323 return expr->unop;
324 if (expr->op == '(')
325 expr = expr->unop;
326 else
327 break;
328 } while (expr);
329
330 return NULL;
331 }
332
do_expression(usage_t mode,struct expression * expr)333 static struct symbol *do_expression(usage_t mode, struct expression *expr)
334 {
335 struct symbol *ret = &int_ctype;
336
337 again:
338 if (expr) switch (expr->type) {
339 default:
340 warning(expr->pos, "bad expr->type: %d", expr->type);
341
342 case EXPR_TYPE: // [struct T]; Why ???
343 case EXPR_VALUE:
344 case EXPR_FVALUE:
345
346 break; case EXPR_LABEL:
347 ret = &label_ctype;
348
349 break; case EXPR_STRING:
350 ret = &string_ctype;
351
352 break; case EXPR_STATEMENT:
353 ret = do_statement(mode, expr->statement);
354
355 break; case EXPR_SIZEOF: case EXPR_ALIGNOF: case EXPR_PTRSIZEOF:
356 do_expression(U_VOID, expr->cast_expression);
357
358 break; case EXPR_COMMA:
359 do_expression(U_VOID, expr->left);
360 ret = do_expression(mode, expr->right);
361
362 break; case EXPR_CAST: case EXPR_FORCE_CAST: //case EXPR_IMPLIED_CAST:
363 ret = base_type(expr->cast_type);
364 do_initializer(ret, expr->cast_expression);
365
366 break; case EXPR_COMPARE: case EXPR_LOGICAL:
367 mode = u_rval(mode);
368 do_expression(mode, expr->left);
369 do_expression(mode, expr->right);
370
371 break; case EXPR_CONDITIONAL: //case EXPR_SELECT:
372 do_expression(expr->cond_true
373 ? U_R_VAL : U_R_VAL | mode,
374 expr->conditional);
375 ret = do_expression(mode, expr->cond_true);
376 ret = do_expression(mode, expr->cond_false);
377
378 break; case EXPR_CALL:
379 if (expr->fn->type == EXPR_SYMBOL)
380 expr->fn->op = 'f'; /* for expr_symbol() */
381 ret = do_expression(U_R_PTR, expr->fn);
382 if (is_ptr(ret))
383 ret = ret->ctype.base_type;
384 DO_2_LIST(ret->arguments, expr->args, arg, val,
385 do_expression(u_lval(base_type(arg)), val));
386 ret = ret->type == SYM_FN ? base_type(ret)
387 : &bad_ctype;
388
389 break; case EXPR_ASSIGNMENT:
390 mode |= U_W_VAL | U_R_VAL;
391 if (expr->op == '=')
392 mode &= ~U_R_VAL;
393 ret = do_expression(mode, expr->left);
394 report_implicit(mode, &expr->pos, ret);
395 mode = expr->op == '='
396 ? u_lval(ret) : U_R_VAL;
397 do_expression(mode, expr->right);
398
399 break; case EXPR_BINOP: {
400 struct symbol *l, *r;
401 mode |= u_rval(mode);
402 l = do_expression(mode, expr->left);
403 r = do_expression(mode, expr->right);
404 if (expr->op != '+' && expr->op != '-')
405 ;
406 else if (!is_ptr_type(r))
407 ret = l;
408 else if (!is_ptr_type(l))
409 ret = r;
410 }
411
412 break; case EXPR_PREOP: case EXPR_POSTOP: {
413 struct expression *unop = expr->unop;
414
415 switch (expr->op) {
416 case SPECIAL_INCREMENT:
417 case SPECIAL_DECREMENT:
418 mode |= U_W_VAL | U_R_VAL;
419 default:
420 mode |= u_rval(mode);
421 case '(':
422 ret = do_expression(mode, unop);
423
424 break; case '&':
425 if ((expr = peek_preop(unop, '*')))
426 goto again;
427 ret = alloc_symbol(unop->pos, SYM_PTR);
428 ret->ctype.base_type =
429 do_expression(u_addr(mode), unop);
430
431 break; case '*':
432 if ((expr = peek_preop(unop, '&')))
433 goto again;
434 if (mode & (U_MASK << U_SHIFT))
435 mode |= U_R_VAL;
436 mode <<= U_SHIFT;
437 if (mode & (U_R_AOF << U_SHIFT))
438 mode |= U_R_VAL;
439 if (mode & (U_W_VAL << U_SHIFT))
440 mode |= U_W_AOF;
441 ret = do_expression(mode, unop);
442 ret = is_ptr(ret) ? base_type(ret)
443 : &bad_ctype;
444 }
445 }
446
447 break; case EXPR_DEREF: {
448 struct symbol *p_type;
449 usage_t p_mode;
450
451 p_mode = mode & U_SELF;
452 if (!(mode & U_MASK) && (mode & (U_MASK << U_SHIFT)))
453 p_mode = U_R_VAL;
454 p_type = do_expression(p_mode, expr->deref);
455
456 ret = report_member(mode, &expr->pos, p_type,
457 lookup_member(p_type, expr->member, NULL));
458 }
459
460 break; case EXPR_OFFSETOF: {
461 struct symbol *in = base_type(expr->in);
462
463 do {
464 if (expr->op == '.') {
465 in = report_member(U_VOID, &expr->pos, in,
466 lookup_member(in, expr->ident, NULL));
467 } else {
468 do_expression(U_R_VAL, expr->index);
469 in = in->ctype.base_type;
470 }
471 } while ((expr = expr->down));
472 }
473
474 break; case EXPR_GENERIC: {
475 struct type_expression *map;
476
477 do_expression(U_VOID, expr->control);
478
479 for (map = expr->map; map; map = map->next)
480 ret = do_expression(mode, map->expr);
481 if (expr->def)
482 ret = do_expression(mode, expr->def);
483 }
484
485 break; case EXPR_SYMBOL:
486 ret = report_symbol(mode, expr);
487 }
488
489 return ret;
490 }
491
do_asm_xputs(usage_t mode,struct asm_operand_list * xputs)492 static void do_asm_xputs(usage_t mode, struct asm_operand_list *xputs)
493 {
494 DO_LIST(xputs, op, do_expression(U_W_AOF | mode, op->expr));
495 }
496
do_statement(usage_t mode,struct statement * stmt)497 static struct symbol *do_statement(usage_t mode, struct statement *stmt)
498 {
499 struct symbol *ret = &void_ctype;
500
501 if (stmt) switch (stmt->type) {
502 default:
503 warning(stmt->pos, "bad stmt->type: %d", stmt->type);
504
505 case STMT_NONE:
506 case STMT_RANGE:
507 case STMT_CONTEXT:
508
509 break; case STMT_DECLARATION:
510 do_sym_list(stmt->declaration);
511
512 break; case STMT_EXPRESSION:
513 ret = do_expression(mode, stmt->expression);
514
515 break; case STMT_RETURN: {
516 struct symbol *type = dissect_ctx->ctype.base_type;
517 do_expression(u_lval(base_type(type)), stmt->expression);
518 }
519
520 break; case STMT_ASM:
521 do_expression(U_R_VAL, stmt->asm_string);
522 do_asm_xputs(U_W_VAL, stmt->asm_outputs);
523 do_asm_xputs(U_R_VAL, stmt->asm_inputs);
524
525 break; case STMT_COMPOUND: {
526 int count;
527
528 count = statement_list_size(stmt->stmts);
529 DO_LIST(stmt->stmts, st,
530 ret = do_statement(--count ? U_VOID : mode, st));
531 }
532
533 break; case STMT_ITERATOR:
534 do_sym_list(stmt->iterator_syms);
535 do_statement(U_VOID, stmt->iterator_pre_statement);
536 do_expression(U_R_VAL, stmt->iterator_pre_condition);
537 do_statement(U_VOID, stmt->iterator_post_statement);
538 do_statement(U_VOID, stmt->iterator_statement);
539 do_expression(U_R_VAL, stmt->iterator_post_condition);
540
541 break; case STMT_IF:
542 do_expression(U_R_VAL, stmt->if_conditional);
543 do_statement(U_VOID, stmt->if_true);
544 do_statement(U_VOID, stmt->if_false);
545
546 break; case STMT_SWITCH:
547 do_expression(U_R_VAL, stmt->switch_expression);
548 do_statement(U_VOID, stmt->switch_statement);
549
550 break; case STMT_CASE:
551 do_expression(U_R_VAL, stmt->case_expression);
552 do_expression(U_R_VAL, stmt->case_to);
553 do_statement(U_VOID, stmt->case_statement);
554
555 break; case STMT_GOTO:
556 do_expression(U_R_PTR, stmt->goto_expression);
557
558 break; case STMT_LABEL:
559 do_statement(mode, stmt->label_statement);
560
561 }
562
563 return ret;
564 }
565
do_initializer(struct symbol * type,struct expression * expr)566 static struct symbol *do_initializer(struct symbol *type, struct expression *expr)
567 {
568 struct symbol *m_type;
569 struct expression *m_expr;
570 int m_addr;
571
572 if (expr) switch (expr->type) {
573 default:
574 do_expression(u_lval(type), expr);
575
576 break; case EXPR_INDEX:
577 do_initializer(base_type(type), expr->idx_expression);
578
579 break; case EXPR_INITIALIZER:
580 m_addr = 0;
581 FOR_EACH_PTR(expr->expr_list, m_expr) {
582 if (type->type == SYM_ARRAY) {
583 m_type = base_type(type);
584 if (m_expr->type == EXPR_INDEX)
585 m_expr = m_expr->idx_expression;
586 } else {
587 int *m_atop = &m_addr;
588
589 m_type = type;
590 while (m_expr->type == EXPR_IDENTIFIER) {
591 m_type = report_member(U_W_VAL, &m_expr->pos, m_type,
592 lookup_member(m_type, m_expr->expr_ident, m_atop));
593 m_expr = m_expr->ident_expression;
594 m_atop = NULL;
595 }
596
597 if (m_atop) {
598 m_type = report_member(U_W_VAL, &m_expr->pos, m_type,
599 lookup_member(m_type, NULL, m_atop));
600 }
601
602 if (m_expr->type != EXPR_INITIALIZER)
603 report_implicit(U_W_VAL, &m_expr->pos, m_type);
604 }
605 do_initializer(m_type, m_expr);
606 m_addr++;
607 } END_FOR_EACH_PTR(m_expr);
608 }
609
610 return type;
611 }
612
do_symbol(struct symbol * sym)613 static inline struct symbol *do_symbol(struct symbol *sym)
614 {
615 struct symbol *type = base_type(sym);
616 struct symbol *dctx = dissect_ctx;
617 struct statement *stmt;
618
619 reporter->r_symdef(sym);
620
621 switch (type->type) {
622 default:
623 if (!sym->initializer)
624 break;
625 reporter->r_symbol(U_W_VAL, &sym->pos, sym);
626 if (!dctx)
627 dissect_ctx = sym;
628 do_initializer(type, sym->initializer);
629 dissect_ctx = dctx;
630
631 break; case SYM_FN:
632 stmt = sym->ctype.modifiers & MOD_INLINE
633 ? type->inline_stmt : type->stmt;
634 if (!stmt)
635 break;
636
637 if (dctx)
638 sparse_error(dctx->pos, "dissect_ctx change %s -> %s",
639 show_ident(dctx->ident), show_ident(sym->ident));
640
641 dissect_ctx = sym;
642 do_sym_list(type->arguments);
643 do_statement(U_VOID, stmt);
644 dissect_ctx = dctx;
645 }
646
647 return type;
648 }
649
do_sym_list(struct symbol_list * list)650 static void do_sym_list(struct symbol_list *list)
651 {
652 DO_LIST(list, sym, do_symbol(sym));
653 }
654
dissect(struct reporter * rep,struct string_list * filelist)655 void dissect(struct reporter *rep, struct string_list *filelist)
656 {
657 reporter = rep;
658
659 DO_LIST(filelist, file, do_sym_list(__sparse(file)));
660 }
661