param_limit: update a comment
[smatch.git] / dissect.c
blob300d5ca99c97541aac92348c450ad968d188057f
1 /*
2 * sparse/dissect.c
4 * Started by Oleg Nesterov <oleg@redhat.com>
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:
13 * The above copyright notice and this permission notice shall be included in
14 * all copies or substantial portions of the Software.
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.
25 #include "dissect.h"
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)
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)
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)
52 typedef unsigned usage_t;
54 struct symbol *dissect_ctx;
56 static struct reporter *reporter;
58 static void do_sym_list(struct symbol_list *list);
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);
66 static inline int is_ptr(struct symbol *type)
68 return type->type == SYM_PTR || type->type == SYM_ARRAY;
71 static inline usage_t u_rval(usage_t mode)
73 return mode & (U_R_VAL | (U_MASK << U_SHIFT))
74 ? U_R_VAL : 0;
77 static inline usage_t u_addr(usage_t mode)
79 return mode = mode & U_MASK
80 ? U_R_AOF | (mode & U_W_AOF) : 0;
83 static usage_t u_lval(struct symbol *type)
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;
90 static usage_t fix_mode(struct symbol *type, usage_t mode)
92 mode &= (U_SELF | (U_SELF << U_SHIFT));
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:
104 break; case SYM_FN:
105 if (mode & U_R_VAL)
106 mode |= U_R_AOF;
107 mode &= ~(U_R_VAL | U_W_AOF);
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);
116 if (!(mode & U_R_AOF))
117 mode &= ~U_W_AOF;
119 return mode;
122 static struct symbol *report_member(usage_t mode, struct position *pos,
123 struct symbol *type, struct symbol *mem)
125 struct symbol *ret = mem->ctype.base_type;
127 if (mem->ident || mem->type == SYM_BAD)
128 reporter->r_member(fix_mode(ret, mode), pos, type, mem);
130 return ret;
133 static void report_implicit(usage_t mode, struct position *pos, struct symbol *type)
135 if (type->type != SYM_STRUCT && type->type != SYM_UNION)
136 return;
138 if (type->ident != NULL)
139 reporter->r_member(mode, pos, type, NULL);
141 DO_LIST(type->symbol_list, mem,
142 report_implicit(mode, pos, base_type(mem)));
145 static inline struct symbol *expr_symbol(struct expression *expr)
147 struct symbol *sym = expr->symbol;
149 if (!sym) {
150 sym = lookup_symbol(expr->symbol_name, NS_SYMBOL);
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 */
159 if (!sym->ctype.base_type)
160 sym->ctype.base_type = &bad_ctype;
162 return sym;
165 static struct symbol *report_symbol(usage_t mode, struct expression *expr)
167 struct symbol *sym = expr_symbol(expr);
168 struct symbol *ret = base_type(sym);
170 if (0 && ret->type == SYM_ENUM)
171 return report_member(mode, &expr->pos, ret, expr->symbol);
173 reporter->r_symbol(fix_mode(ret, mode), &expr->pos, sym);
175 return ret;
178 static bool deanon(struct symbol *base, struct ident *node, struct symbol *parent)
180 struct ident *pi = parent ? parent->ident : NULL;
181 char name[256];
183 if (!node) {
184 base->ident = pi;
185 return false;
188 snprintf(name, sizeof(name), "%.*s:%.*s",
189 pi ? pi->len : 0, pi ? pi->name : NULL, node->len, node->name);
191 base->ident = built_in_ident(name);
192 return true;
195 static void report_memdef(struct symbol *sym, struct symbol *mem)
197 mem->kind = 'm';
198 if (sym && mem->ident)
199 reporter->r_memdef(sym, mem);
202 static void examine_sym_node(struct symbol *node, struct symbol *parent)
204 struct ident *name = node->ident;
205 struct symbol *base, *dctx;
207 if (node->visited)
208 return;
209 node->visited = 1;
210 node->kind = 'v';
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;
219 case SYM_ARRAY:
220 do_expression(U_R_VAL, base->array_size);
221 case SYM_PTR:
222 node = base;
223 break;
225 case SYM_FN:
226 node->kind = 'f';
227 node = base;
228 break;
230 case SYM_STRUCT: case SYM_UNION: //case SYM_ENUM:
231 if (base->inspected)
232 return;
233 base->inspected = 1;
234 base->kind = 's';
236 if (!base->symbol_list)
237 return;
239 dctx = dissect_ctx;
240 if (toplevel(base->scope))
241 dissect_ctx = NULL;
243 if (base->ident || deanon(base, name, parent))
244 reporter->r_symdef(base);
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;
257 static struct symbol *base_type(struct symbol *sym)
259 if (!sym)
260 return &bad_ctype;
262 if (sym->type == SYM_NODE)
263 examine_sym_node(sym, NULL);
265 return sym->ctype.base_type // builtin_fn_type
266 ?: &bad_ctype;
269 static struct symbol *__lookup_member(struct symbol *type, struct ident *name, int *p_addr)
271 struct symbol *node;
272 int addr = 0;
274 FOR_EACH_PTR(type->symbol_list, node)
275 if (!name) {
276 if (addr == *p_addr)
277 return node;
279 else if (node->ident == NULL) {
280 node = __lookup_member(node->ctype.base_type, name, NULL);
281 if (node)
282 goto found;
284 else if (node->ident == name) {
285 found:
286 if (p_addr)
287 *p_addr = addr;
288 return node;
290 addr++;
291 END_FOR_EACH_PTR(node);
293 return NULL;
296 static struct symbol *lookup_member(struct symbol *type, struct ident *name, int *addr)
298 struct symbol *mem = __lookup_member(type, name, addr);
300 if (!mem) {
301 static struct symbol bad_member = {
302 .type = SYM_BAD,
303 .ctype.base_type = &bad_ctype,
304 .kind = 'm',
307 if (!type->symbol_list)
308 type->scope = file_scope;
310 mem = &bad_member;
311 mem->ident = name;
314 return mem;
317 static struct expression *peek_preop(struct expression *expr, int op)
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);
330 return NULL;
333 static struct symbol *do_expression(usage_t mode, struct expression *expr)
335 struct symbol *ret = &int_ctype;
337 again:
338 if (expr) switch (expr->type) {
339 default:
340 warning(expr->pos, "bad expr->type: %d", expr->type);
342 case EXPR_TYPE: // [struct T]; Why ???
343 case EXPR_VALUE:
344 case EXPR_FVALUE:
346 break; case EXPR_LABEL:
347 ret = &label_ctype;
349 break; case EXPR_STRING:
350 ret = &string_ctype;
352 break; case EXPR_STATEMENT:
353 ret = do_statement(mode, expr->statement);
355 break; case EXPR_SIZEOF: case EXPR_ALIGNOF: case EXPR_PTRSIZEOF:
356 do_expression(U_VOID, expr->cast_expression);
358 break; case EXPR_COMMA:
359 do_expression(U_VOID, expr->left);
360 ret = do_expression(mode, expr->right);
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);
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);
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);
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;
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);
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 != '-')
406 else if (!is_ptr_type(r))
407 ret = l;
408 else if (!is_ptr_type(l))
409 ret = r;
412 break; case EXPR_PREOP: case EXPR_POSTOP: {
413 struct expression *unop = expr->unop;
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);
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);
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;
447 break; case EXPR_DEREF: {
448 struct symbol *p_type;
449 usage_t p_mode;
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);
456 ret = report_member(mode, &expr->pos, p_type,
457 lookup_member(p_type, expr->member, NULL));
460 break; case EXPR_OFFSETOF: {
461 struct symbol *in = base_type(expr->in);
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;
471 } while ((expr = expr->down));
474 break; case EXPR_GENERIC: {
475 struct type_expression *map;
477 do_expression(U_VOID, expr->control);
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);
485 break; case EXPR_SYMBOL:
486 ret = report_symbol(mode, expr);
489 return ret;
492 static void do_asm_xputs(usage_t mode, struct asm_operand_list *xputs)
494 DO_LIST(xputs, op, do_expression(U_W_AOF | mode, op->expr));
497 static struct symbol *do_statement(usage_t mode, struct statement *stmt)
499 struct symbol *ret = &void_ctype;
501 if (stmt) switch (stmt->type) {
502 default:
503 warning(stmt->pos, "bad stmt->type: %d", stmt->type);
505 case STMT_NONE:
506 case STMT_RANGE:
507 case STMT_CONTEXT:
509 break; case STMT_DECLARATION:
510 do_sym_list(stmt->declaration);
512 break; case STMT_EXPRESSION:
513 ret = do_expression(mode, stmt->expression);
515 break; case STMT_RETURN: {
516 struct symbol *type = dissect_ctx->ctype.base_type;
517 do_expression(u_lval(base_type(type)), stmt->expression);
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);
525 break; case STMT_COMPOUND: {
526 int count;
528 count = statement_list_size(stmt->stmts);
529 DO_LIST(stmt->stmts, st,
530 ret = do_statement(--count ? U_VOID : mode, st));
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);
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);
546 break; case STMT_SWITCH:
547 do_expression(U_R_VAL, stmt->switch_expression);
548 do_statement(U_VOID, stmt->switch_statement);
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);
555 break; case STMT_GOTO:
556 do_expression(U_R_PTR, stmt->goto_expression);
558 break; case STMT_LABEL:
559 do_statement(mode, stmt->label_statement);
563 return ret;
566 static struct symbol *do_initializer(struct symbol *type, struct expression *expr)
568 struct symbol *m_type;
569 struct expression *m_expr;
570 int m_addr;
572 if (expr) switch (expr->type) {
573 default:
574 do_expression(u_lval(type), expr);
576 break; case EXPR_INDEX:
577 do_initializer(base_type(type), expr->idx_expression);
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;
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;
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));
602 if (m_expr->type != EXPR_INITIALIZER)
603 report_implicit(U_W_VAL, &m_expr->pos, m_type);
605 do_initializer(m_type, m_expr);
606 m_addr++;
607 } END_FOR_EACH_PTR(m_expr);
610 return type;
613 static inline bool is_macro(struct symbol *sym)
615 return (sym->namespace == NS_MACRO || sym->namespace == NS_UNDEF);
618 static inline bool is_typedef(struct symbol *sym)
620 return (sym->namespace == NS_TYPEDEF);
623 static inline struct symbol *do_symbol(struct symbol *sym)
625 struct symbol *type = base_type(sym);
626 struct symbol *dctx = dissect_ctx;
627 struct statement *stmt;
629 reporter->r_symdef(sym);
631 switch (type->type) {
632 default:
633 if (!sym->initializer)
634 break;
635 reporter->r_symbol(U_W_VAL, &sym->pos, sym);
636 if (!dctx)
637 dissect_ctx = sym;
638 do_initializer(type, sym->initializer);
639 dissect_ctx = dctx;
641 break; case SYM_FN:
642 stmt = sym->ctype.modifiers & MOD_INLINE
643 ? type->inline_stmt : type->stmt;
644 if (!stmt)
645 break;
647 if (dctx)
648 sparse_error(dctx->pos, "dissect_ctx change %s -> %s",
649 show_ident(dctx->ident), show_ident(sym->ident));
651 dissect_ctx = sym;
652 do_sym_list(type->arguments);
653 do_statement(U_VOID, stmt);
654 dissect_ctx = dctx;
657 return type;
660 static void do_sym_list(struct symbol_list *list)
662 DO_LIST(list, sym, do_symbol(sym));
665 static inline bool valid_namespace(enum namespace ns)
667 return (ns == NS_TYPEDEF || ns == NS_MACRO || ns == NS_UNDEF || ns == NS_STRUCT || ns == NS_SYMBOL);
670 static void do_file(char *file)
672 struct symbol_list *res = sparse_keep_tokens(file);
674 if (!dissect_show_all_symbols) {
675 do_sym_list(res);
676 goto end;
679 DO_LIST(file_scope->symbols, sym,
680 if (input_streams[sym->pos.stream].fd != -1 && valid_namespace(sym->namespace)) {
681 if (is_typedef(sym)) {
682 sym->kind = 't';
683 reporter->r_symdef(sym);
684 continue;
687 if (is_macro(sym)) {
688 sym->kind = 'd';
689 reporter->r_symdef(sym);
690 continue;
693 if (sym->type == SYM_STRUCT || sym->type == SYM_UNION) {
694 sym->ctype.base_type = sym;
695 examine_sym_node(sym, NULL);
696 continue;
699 do_symbol(sym);
703 DO_LIST(global_scope->symbols, sym,
704 if (input_streams[sym->pos.stream].fd != -1 && valid_namespace(sym->namespace)) {
705 do_symbol(sym);
709 end:
710 /* Drop the tokens for this file after parsing */
711 clear_token_alloc();
714 void dissect(struct reporter *rep, struct string_list *filelist)
716 reporter = rep;
718 DO_LIST(filelist, file, do_file(file));