?  search:
summary | log | graphiclog1 | graphiclog2 | commit | commitdiff | tree | refs | edit | fork
blame | history | raw | HEAD
kunmap: update validation file
[smatch.git] / dissect.c
blobd211bca6fbe43d66ef7423063449630e3fe46356
1 /*
2 * sparse/dissect.c
3 *
4 * Started by Oleg Nesterov <oleg@tv-sign.ru>
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 static struct reporter *reporter;
55 static struct symbol *return_type;
56
57 static void do_sym_list(struct symbol_list *list);
58
59 static struct symbol
60 *base_type(struct symbol *sym),
61 *do_initializer(struct symbol *type, struct expression *expr),
62 *do_expression(usage_t mode, struct expression *expr),
63 *do_statement(usage_t mode, struct statement *stmt);
64
65 static inline int is_ptr(struct symbol *type)
66 {
67 return type->type == SYM_PTR || type->type == SYM_ARRAY;
68 }
69
70 static inline usage_t u_rval(usage_t mode)
71 {
72 return mode & (U_R_VAL | (U_MASK << U_SHIFT))
73 ? U_R_VAL : 0;
74 }
75
76 static inline usage_t u_addr(usage_t mode)
77 {
78 return mode = mode & U_MASK
79 ? U_R_AOF | (mode & U_W_AOF) : 0;
80 }
81
82 static usage_t u_lval(struct symbol *type)
83 {
84 int wptr = is_ptr(type) && !(type->ctype.modifiers & MOD_CONST);
85 return wptr || type == &bad_ctype
86 ? U_W_AOF | U_R_VAL : U_R_VAL;
87 }
88
89 static usage_t fix_mode(struct symbol *type, usage_t mode)
90 {
91 mode &= (U_SELF | (U_SELF << U_SHIFT));
92
93 switch (type->type) {
94 case SYM_BASETYPE:
95 if (!type->ctype.base_type)
96 break;
97 case SYM_ENUM:
98 case SYM_BITFIELD:
99 if (mode & U_MASK)
100 mode &= U_SELF;
101 default:
102
103 break; case SYM_FN:
104 if (mode & U_R_VAL)
105 mode |= U_R_AOF;
106 mode &= ~(U_R_VAL | U_W_AOF);
107
108 break; case SYM_ARRAY:
109 if (mode & (U_MASK << U_SHIFT))
110 mode >>= U_SHIFT;
111 else if (mode != U_W_VAL)
112 mode = u_addr(mode);
113 }
114
115 if (!(mode & U_R_AOF))
116 mode &= ~U_W_AOF;
117
118 return mode;
119 }
120
121 static inline struct symbol *no_member(struct ident *name)
122 {
123 static struct symbol sym = {
124 .type = SYM_BAD,
125 };
126
127 sym.ctype.base_type = &bad_ctype;
128 sym.ident = name;
129
130 return &sym;
131 }
132
133 static struct symbol *report_member(mode_t mode, struct position *pos,
134 struct symbol *type, struct symbol *mem)
135 {
136 struct symbol *ret = mem->ctype.base_type;
137
138 if (reporter->r_member)
139 reporter->r_member(fix_mode(ret, mode), pos, type, mem);
140
141 return ret;
142 }
143
144 static void report_implicit(usage_t mode, struct position *pos, struct symbol *type)
145 {
146 if (type->type != SYM_STRUCT && type->type != SYM_UNION)
147 return;
148
149 if (!reporter->r_member)
150 return;
151
152 if (type->ident != NULL)
153 reporter->r_member(mode, pos, type, NULL);
154
155 DO_LIST(type->symbol_list, mem,
156 report_implicit(mode, pos, base_type(mem)));
157 }
158
159 static inline struct symbol *expr_symbol(struct expression *expr)
160 {
161 struct symbol *sym = expr->symbol;
162
163 if (!sym) {
164 sym = lookup_symbol(expr->symbol_name, NS_SYMBOL);
165
166 if (!sym) {
167 sym = alloc_symbol(expr->pos, SYM_BAD);
168 bind_symbol(sym, expr->symbol_name, NS_SYMBOL);
169 sym->ctype.modifiers = MOD_EXTERN;
170 }
171 }
172
173 if (!sym->ctype.base_type)
174 sym->ctype.base_type = &bad_ctype;
175
176 return sym;
177 }
178
179 static struct symbol *report_symbol(usage_t mode, struct expression *expr)
180 {
181 struct symbol *sym = expr_symbol(expr);
182 struct symbol *ret = base_type(sym);
183
184 if (0 && ret->type == SYM_ENUM)
185 return report_member(mode, &expr->pos, ret, expr->symbol);
186
187 if (reporter->r_symbol)
188 reporter->r_symbol(fix_mode(ret, mode), &expr->pos, sym);
189
190 return ret;
191 }
192
193 static inline struct ident *mk_name(struct ident *root, struct ident *node)
194 {
195 char name[256];
196
197 snprintf(name, sizeof(name), "%.*s:%.*s",
198 root ? root->len : 0, root ? root->name : "",
199 node ? node->len : 0, node ? node->name : "");
200
201 return built_in_ident(name);
202 }
203
204 static void examine_sym_node(struct symbol *node, struct ident *root)
205 {
206 struct symbol *base;
207 struct ident *name;
208
209 if (node->examined)
210 return;
211
212 node->examined = 1;
213 name = node->ident;
214
215 while ((base = node->ctype.base_type) != NULL)
216 switch (base->type) {
217 case SYM_TYPEOF:
218 node->ctype.base_type =
219 do_expression(U_VOID, base->initializer);
220 break;
221
222 case SYM_ARRAY:
223 do_expression(U_R_VAL, base->array_size);
224 case SYM_PTR: case SYM_FN:
225 node = base;
226 break;
227
228 case SYM_STRUCT: case SYM_UNION: //case SYM_ENUM:
229 if (base->evaluated)
230 return;
231 if (!base->symbol_list)
232 return;
233 base->evaluated = 1;
234
235 if (!base->ident && name)
236 base->ident = mk_name(root, name);
237 if (base->ident && reporter->r_symdef)
238 reporter->r_symdef(base);
239 DO_LIST(base->symbol_list, mem,
240 examine_sym_node(mem, base->ident ?: root));
241 default:
242 return;
243 }
244 }
245
246 static struct symbol *base_type(struct symbol *sym)
247 {
248 if (!sym)
249 return &bad_ctype;
250
251 if (sym->type == SYM_NODE)
252 examine_sym_node(sym, NULL);
253
254 return sym->ctype.base_type // builtin_fn_type
255 ?: &bad_ctype;
256 }
257
258 static struct symbol *__lookup_member(struct symbol *type, struct ident *name, int *p_addr)
259 {
260 struct symbol *node;
261 int addr = 0;
262
263 FOR_EACH_PTR(type->symbol_list, node)
264 if (!name) {
265 if (addr == *p_addr)
266 return node;
267 }
268 else if (node->ident == NULL) {
269 node = __lookup_member(node->ctype.base_type, name, NULL);
270 if (node)
271 goto found;
272 }
273 else if (node->ident == name) {
274 found:
275 if (p_addr)
276 *p_addr = addr;
277 return node;
278 }
279 addr++;
280 END_FOR_EACH_PTR(node);
281
282 return NULL;
283 }
284
285 static struct symbol *lookup_member(struct symbol *type, struct ident *name, int *addr)
286 {
287 return __lookup_member(type, name, addr)
288 ?: no_member(name);
289 }
290
291 static struct expression *peek_preop(struct expression *expr, int op)
292 {
293 do {
294 if (expr->type != EXPR_PREOP)
295 break;
296 if (expr->op == op)
297 return expr->unop;
298 if (expr->op == '(')
299 expr = expr->unop;
300 else
301 break;
302 } while (expr);
303
304 return NULL;
305 }
306
307 static struct symbol *do_expression(usage_t mode, struct expression *expr)
308 {
309 struct symbol *ret = &int_ctype;
310
311 again:
312 if (expr) switch (expr->type) {
313 default:
314 warning(expr->pos, "bad expr->type: %d", expr->type);
315
316 case EXPR_TYPE: // [struct T]; Why ???
317 case EXPR_VALUE:
318 case EXPR_FVALUE:
319
320 break; case EXPR_LABEL:
321 ret = &label_ctype;
322
323 break; case EXPR_STRING:
324 ret = &string_ctype;
325
326 break; case EXPR_STATEMENT:
327 ret = do_statement(mode, expr->statement);
328
329 break; case EXPR_SIZEOF: case EXPR_ALIGNOF: case EXPR_PTRSIZEOF:
330 do_expression(U_VOID, expr->cast_expression);
331
332 break; case EXPR_COMMA:
333 do_expression(U_VOID, expr->left);
334 ret = do_expression(mode, expr->right);
335
336 break; case EXPR_CAST: case EXPR_FORCE_CAST: //case EXPR_IMPLIED_CAST:
337 ret = base_type(expr->cast_type);
338 do_initializer(ret, expr->cast_expression);
339
340 break; case EXPR_COMPARE: case EXPR_LOGICAL:
341 mode = u_rval(mode);
342 do_expression(mode, expr->left);
343 do_expression(mode, expr->right);
344
345 break; case EXPR_CONDITIONAL: //case EXPR_SELECT:
346 do_expression(expr->cond_true
347 ? U_R_VAL : U_R_VAL | mode,
348 expr->conditional);
349 ret = do_expression(mode, expr->cond_true);
350 ret = do_expression(mode, expr->cond_false);
351
352 break; case EXPR_CALL:
353 ret = do_expression(U_R_PTR, expr->fn);
354 if (is_ptr(ret))
355 ret = ret->ctype.base_type;
356 DO_2_LIST(ret->arguments, expr->args, arg, val,
357 do_expression(u_lval(base_type(arg)), val));
358 ret = ret->type == SYM_FN ? base_type(ret)
359 : &bad_ctype;
360
361 break; case EXPR_ASSIGNMENT:
362 mode |= U_W_VAL | U_R_VAL;
363 if (expr->op == '=')
364 mode &= ~U_R_VAL;
365 ret = do_expression(mode, expr->left);
366 report_implicit(mode, &expr->pos, ret);
367 mode = expr->op == '='
368 ? u_lval(ret) : U_R_VAL;
369 do_expression(mode, expr->right);
370
371 break; case EXPR_BINOP: {
372 struct symbol *l, *r;
373 mode |= u_rval(mode);
374 l = do_expression(mode, expr->left);
375 r = do_expression(mode, expr->right);
376 if (expr->op != '+' && expr->op != '-')
377 ;
378 else if (!is_ptr_type(r))
379 ret = l;
380 else if (!is_ptr_type(l))
381 ret = r;
382 }
383
384 break; case EXPR_PREOP: case EXPR_POSTOP: {
385 struct expression *unop = expr->unop;
386
387 switch (expr->op) {
388 case SPECIAL_INCREMENT:
389 case SPECIAL_DECREMENT:
390 mode |= U_W_VAL | U_R_VAL;
391 default:
392 mode |= u_rval(mode);
393 case '(':
394 ret = do_expression(mode, unop);
395
396 break; case '&':
397 if ((expr = peek_preop(unop, '*')))
398 goto again;
399 ret = alloc_symbol(unop->pos, SYM_PTR);
400 ret->ctype.base_type =
401 do_expression(u_addr(mode), unop);
402
403 break; case '*':
404 if ((expr = peek_preop(unop, '&')))
405 goto again;
406 if (mode & (U_MASK << U_SHIFT))
407 mode |= U_R_VAL;
408 mode <<= U_SHIFT;
409 if (mode & (U_R_AOF << U_SHIFT))
410 mode |= U_R_VAL;
411 if (mode & (U_W_VAL << U_SHIFT))
412 mode |= U_W_AOF;
413 ret = do_expression(mode, unop);
414 ret = is_ptr(ret) ? base_type(ret)
415 : &bad_ctype;
416 }
417 }
418
419 break; case EXPR_DEREF: {
420 struct symbol *p_type;
421 usage_t p_mode;
422
423 p_mode = mode & U_SELF;
424 if (!(mode & U_MASK) && (mode & (U_MASK << U_SHIFT)))
425 p_mode = U_R_VAL;
426 p_type = do_expression(p_mode, expr->deref);
427
428 ret = report_member(mode, &expr->pos, p_type,
429 lookup_member(p_type, expr->member, NULL));
430 }
431
432 break; case EXPR_SYMBOL:
433 ret = report_symbol(mode, expr);
434 }
435
436 return ret;
437 }
438
439 static void do_asm_xputs(usage_t mode, struct expression_list *xputs)
440 {
441 int nr = 0;
442
443 DO_LIST(xputs, expr,
444 if (++nr % 3 == 0)
445 do_expression(U_W_AOF | mode, expr));
446 }
447
448 static struct symbol *do_statement(usage_t mode, struct statement *stmt)
449 {
450 struct symbol *ret = &void_ctype;
451
452 if (stmt) switch (stmt->type) {
453 default:
454 warning(stmt->pos, "bad stmt->type: %d", stmt->type);
455
456 case STMT_NONE:
457 case STMT_RANGE:
458 case STMT_CONTEXT:
459
460 break; case STMT_DECLARATION:
461 do_sym_list(stmt->declaration);
462
463 break; case STMT_EXPRESSION:
464 ret = do_expression(mode, stmt->expression);
465
466 break; case STMT_RETURN:
467 do_expression(u_lval(return_type), stmt->expression);
468
469 break; case STMT_ASM:
470 do_expression(U_R_VAL, stmt->asm_string);
471 do_asm_xputs(U_W_VAL, stmt->asm_outputs);
472 do_asm_xputs(U_R_VAL, stmt->asm_inputs);
473
474 break; case STMT_COMPOUND: {
475 int count;
476
477 count = statement_list_size(stmt->stmts);
478 DO_LIST(stmt->stmts, st,
479 ret = do_statement(--count ? U_VOID : mode, st));
480 }
481
482 break; case STMT_ITERATOR:
483 do_sym_list(stmt->iterator_syms);
484 do_statement(U_VOID, stmt->iterator_pre_statement);
485 do_expression(U_R_VAL, stmt->iterator_pre_condition);
486 do_statement(U_VOID, stmt->iterator_post_statement);
487 do_statement(U_VOID, stmt->iterator_statement);
488 do_expression(U_R_VAL, stmt->iterator_post_condition);
489
490 break; case STMT_IF:
491 do_expression(U_R_VAL, stmt->if_conditional);
492 do_statement(U_VOID, stmt->if_true);
493 do_statement(U_VOID, stmt->if_false);
494
495 break; case STMT_SWITCH:
496 do_expression(U_R_VAL, stmt->switch_expression);
497 do_statement(U_VOID, stmt->switch_statement);
498
499 break; case STMT_CASE:
500 do_expression(U_R_VAL, stmt->case_expression);
501 do_expression(U_R_VAL, stmt->case_to);
502 do_statement(U_VOID, stmt->case_statement);
503
504 break; case STMT_GOTO:
505 do_expression(U_R_PTR, stmt->goto_expression);
506
507 break; case STMT_LABEL:
508 do_statement(mode, stmt->label_statement);
509
510 }
511
512 return ret;
513 }
514
515 static struct symbol *do_initializer(struct symbol *type, struct expression *expr)
516 {
517 struct symbol *m_type;
518 struct expression *m_expr;
519 int m_addr;
520
521 if (expr) switch (expr->type) {
522 default:
523 do_expression(u_lval(type), expr);
524
525 break; case EXPR_INDEX:
526 do_initializer(base_type(type), expr->idx_expression);
527
528 break; case EXPR_INITIALIZER:
529 m_addr = 0;
530 FOR_EACH_PTR(expr->expr_list, m_expr)
531 if (type->type == SYM_ARRAY) {
532 m_type = base_type(type);
533 if (m_expr->type == EXPR_INDEX)
534 m_expr = m_expr->idx_expression;
535 } else {
536 struct position *pos = &m_expr->pos;
537 struct ident *m_name = NULL;
538
539 if (m_expr->type == EXPR_IDENTIFIER) {
540 m_name = m_expr->expr_ident;
541 m_expr = m_expr->ident_expression;
542 }
543
544 m_type = report_member(U_W_VAL, pos, type,
545 lookup_member(type, m_name, &m_addr));
546 if (m_expr->type != EXPR_INITIALIZER)
547 report_implicit(U_W_VAL, pos, m_type);
548 }
549 do_initializer(m_type, m_expr);
550 m_addr++;
551 END_FOR_EACH_PTR(m_expr);
552 }
553
554 return type;
555 }
556
557 static inline struct symbol *do_symbol(struct symbol *sym)
558 {
559 struct symbol *type;
560
561 type = base_type(sym);
562
563 if (reporter->r_symdef)
564 reporter->r_symdef(sym);
565
566 switch (type->type) {
567 default:
568 if (!sym->initializer)
569 break;
570 if (reporter->r_symbol)
571 reporter->r_symbol(U_W_VAL, &sym->pos, sym);
572 do_initializer(type, sym->initializer);
573
574 break; case SYM_FN:
575 do_sym_list(type->arguments);
576 return_type = base_type(type);
577 do_statement(U_VOID, sym->ctype.modifiers & MOD_INLINE
578 ? type->inline_stmt
579 : type->stmt);
580 }
581
582 return type;
583 }
584
585 static void do_sym_list(struct symbol_list *list)
586 {
587 DO_LIST(list, sym, do_symbol(sym));
588 }
589
590 void dissect(struct symbol_list *list, struct reporter *rep)
591 {
592 reporter = rep;
593 do_sym_list(list);
594 }
Static analysis for C