dissect.c

   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 }