smatch_states.c

   1 /*
   2  * sparse/smatch_states.c
   3  *
   4  * Copyright (C) 2006 Dan Carpenter.
   5  *
   6  *  Licensed under the Open Software License version 1.1
   7  *
   8  */
   9
  10 #include <stdlib.h>
  11 #include <stdio.h>
  12 #include "smatch.h"
  13
  14 ALLOCATOR(smatch_state, "smatch state");
  15 DECLARE_PTR_LIST(state_list, struct smatch_state);
  16 DECLARE_PTR_LIST(state_list_stack, struct state_list);
  17
  18 static struct state_list *cur_slist;
  19 static struct state_list_stack *false_stack;
  20 static struct state_list_stack *true_stack;
  21 static struct state_list_stack *break_stack;
  22 static struct state_list_stack *switch_stack;
  23 static struct state_list_stack *default_stack;
  24 static struct state_list_stack *continue_stack;
  25 static struct state_list_stack *mini_false_stack;
  26 static struct state_list *and_clumps[2];
  27
  28 struct slist_head {
  29         char *name;
  30         struct state_list *slist;
  31 };
  32 ALLOCATOR(slist_head, "goto stack");
  33 DECLARE_PTR_LIST(slist_stack, struct slist_head);
  34 static struct slist_stack *goto_stack;
  35
  36 int debug_states;
  37
  38 void __print_cur_slist()
  39 {
  40         struct smatch_state *state;
  41
  42         printf("dumping slist at %d\n", get_lineno());
  43         FOR_EACH_PTR(cur_slist, state) {
  44                 printf("%s=%d\n", state->name, state->state);
  45         } END_FOR_EACH_PTR(state);
  46         printf("---\n");
  47 }
  48
  49 static void add_history(struct smatch_state *state)
  50 {
  51         struct state_history *tmp;
  52
  53         if (!state)
  54                 return;
  55         tmp = malloc(sizeof(*tmp));
  56         tmp->loc = get_lineno();
  57         add_ptr_list(&state->line_history, tmp);
  58         tmp = malloc(sizeof(*tmp));
  59         tmp->loc = get_path_id();
  60         add_ptr_list(&state->line_history, tmp);
  61 }
  62
  63 struct smatch_state *alloc_state(const char *name, int owner,
  64                                         struct symbol *sym, int state)
  65 {
  66         struct smatch_state *sm_state = __alloc_smatch_state(0);
  67
  68         sm_state->name = (char *)name;
  69         sm_state->owner = owner;
  70         sm_state->sym = sym;
  71         sm_state->state = state;
  72         sm_state->line_history = NULL;
  73         sm_state->path_history = NULL;
  74         add_history(sm_state);
  75         return sm_state;
  76 }
  77
  78 static struct smatch_state *clone_state(struct smatch_state *s)
  79 {
  80         return alloc_state(s->name, s->owner, s->sym, s->state);
  81 }
  82
  83 static void push_slist(struct state_list_stack **list_stack,
  84                                    struct state_list *slist)
  85 {
  86         add_ptr_list(list_stack, slist);
  87 }
  88
  89 static struct state_list *pop_slist(struct state_list_stack **list_stack)
  90 {
  91         struct state_list *slist;
  92
  93         slist = last_ptr_list((struct ptr_list *)*list_stack);
  94         delete_ptr_list_entry((struct ptr_list **)list_stack, slist, 1);
  95         return slist;
  96 }
  97
  98 static struct state_list *clone_slist(struct state_list *from_slist)
  99 {
 100         struct smatch_state *state;
 101         struct smatch_state *tmp;
 102         struct state_list *to_slist = NULL;
 103
 104         FOR_EACH_PTR(from_slist, state) {
 105                 tmp = clone_state(state);
 106                 add_ptr_list(&to_slist, tmp);
 107         } END_FOR_EACH_PTR(state);
 108         return to_slist;
 109 }
 110
 111 static void del_slist(struct state_list **slist)
 112 {
 113         __free_ptr_list((struct ptr_list **)slist);
 114 }
 115
 116 static void del_slist_stack(struct state_list_stack **slist_stack)
 117 {
 118         struct state_list *slist;
 119
 120         FOR_EACH_PTR(*slist_stack, slist) {
 121                 __free_ptr_list((struct ptr_list **)&slist);
 122         } END_FOR_EACH_PTR(slist);
 123         __free_ptr_list((struct ptr_list **)slist_stack);
 124 }
 125
 126 static void add_state_slist(struct state_list **slist,
 127                             struct smatch_state *state)
 128 {
 129         add_ptr_list(slist, state);
 130 }
 131
 132 static void set_state_slist(struct state_list **slist, const char *name,
 133                             int owner, struct symbol *sym, int state)
 134 {
 135         struct smatch_state *tmp;
 136
 137         FOR_EACH_PTR(*slist, tmp) {
 138                 if (tmp->owner == owner && tmp->sym == sym
 139                     && !strcmp(tmp->name, name)){
 140                         tmp->state = state;
 141                         return;
 142                 }
 143         } END_FOR_EACH_PTR(tmp);
 144         tmp = alloc_state(name, owner, sym, state);
 145         add_state_slist(slist, tmp);
 146 }
 147
 148 static inline void set_state_stack(struct state_list_stack **stack,
 149                                     const char *name, int owner,
 150                                    struct symbol *sym, int state)
 151 {
 152         struct state_list *slist;
 153
 154         slist = pop_slist(stack);
 155         set_state_slist(&slist, name, owner, sym, state);
 156         push_slist(stack, slist);
 157 }
 158
 159 static int merge_states(const char *name, int owner, struct symbol *sym,
 160                         int state1, int state2)
 161 {
 162         if (state1 == state2)
 163                 return state1;
 164         if (__has_merge_function(owner))
 165                 return __client_merge_function(owner, name, sym, (state1 < state2?state1:state2), (state1 > state2?state1:state2));
 166         return UNDEFINED;
 167 }
 168
 169 static void merge_state_slist(struct state_list **slist, const char *name,
 170                               int owner, struct symbol *sym, int state)
 171 {
 172         struct smatch_state *tmp;
 173         int s;
 174
 175         FOR_EACH_PTR(*slist, tmp) {
 176                 if (tmp->owner == owner && tmp->sym == sym
 177                     && !strcmp(tmp->name, name)){
 178                         s = merge_states(name, owner, sym, tmp->state, state);
 179                         if (tmp->state != s) {
 180                                 add_history(tmp);
 181                                 SM_DEBUG("%d merge name='%s' owner=%d: %d + %d => %d\n",
 182                                          get_lineno(), name, owner, tmp->state, state, s);
 183                         }
 184                         tmp->state = s;
 185                         return;
 186                 }
 187         } END_FOR_EACH_PTR(tmp);
 188         tmp = alloc_state(name, owner, sym, state);
 189         add_state_slist(slist, tmp);
 190 }
 191
 192 static void merge_state_stack(struct state_list_stack ** stack,
 193                               const char *name, int owner, struct symbol *sym,
 194                               int state)
 195 {
 196         struct state_list *slist;
 197
 198         slist = pop_slist(stack);
 199         merge_state_slist(&slist, name, owner, sym, state);
 200         push_slist(stack, slist);
 201 }
 202
 203 static void delete_state_slist(struct state_list **slist, const char *name,
 204                                int owner, struct symbol *sym)
 205 {
 206         struct smatch_state *state;
 207
 208         FOR_EACH_PTR(*slist, state) {
 209                 if (state->owner == owner && state->sym == sym
 210                     && !strcmp(state->name, name)){
 211                         delete_ptr_list_entry((struct ptr_list **)slist,
 212                                               state, 1);
 213                         __free_smatch_state(state);
 214                         return;
 215                 }
 216         } END_FOR_EACH_PTR(state);
 217 }
 218
 219 static void merge_slist(struct state_list *slist)
 220 {
 221         struct smatch_state *state;
 222         FOR_EACH_PTR(slist, state) {
 223                 merge_state_slist(&cur_slist, state->name, state->owner,
 224                                   state->sym, state->state);
 225         } END_FOR_EACH_PTR(state);
 226 }
 227
 228 void set_state(const char *name, int owner, struct symbol *sym, int state)
 229 {
 230         struct smatch_state *tmp;
 231
 232         if (!name)
 233                 return;
 234
 235         FOR_EACH_PTR(cur_slist, tmp) {
 236                 if (tmp->owner == owner && tmp->sym == sym
 237                     && !strcmp(tmp->name, name)){
 238                         SM_DEBUG("%d state change name='%s' owner=%d: %d => %d\n"
 239                                  , get_lineno(), name, owner, tmp->state, state);
 240                         add_history(tmp);
 241                         tmp->state = state;
 242                         return;
 243                 }
 244         } END_FOR_EACH_PTR(tmp);
 245         SM_DEBUG("%d new state. name='%s' owner=%d: %d\n", get_lineno(), name,
 246                  owner, state);
 247         tmp = alloc_state(name, owner, sym, state);
 248         add_state_slist(&cur_slist, tmp);
 249
 250 }
 251
 252 static int get_state_slist(struct state_list *slist, const char *name,
 253                            int owner, struct symbol *sym)
 254 {
 255         struct smatch_state *state;
 256
 257         if (!name)
 258                 return NOTFOUND;
 259
 260         FOR_EACH_PTR(cur_slist, state) {
 261                 if (state->owner == owner && state->sym == sym
 262                     && !strcmp(state->name, name))
 263                         return state->state;
 264         } END_FOR_EACH_PTR(state);
 265         return NOTFOUND;
 266 }
 267
 268 int get_state(const char *name, int owner, struct symbol *sym)
 269 {
 270         return get_state_slist(cur_slist, name, owner, sym);
 271 }
 272
 273 struct state_list *get_current_states(int owner)
 274 {
 275         struct state_list *slist;
 276         struct smatch_state *tmp;
 277
 278         FOR_EACH_PTR(cur_slist, tmp) {
 279                 if (tmp->owner == owner) {
 280                         add_ptr_list(&slist, tmp);
 281                 }
 282         } END_FOR_EACH_PTR(tmp);
 283
 284         return slist;
 285 }
 286
 287 void set_true_false_states(const char *name, int owner, struct symbol *sym,
 288                            int true_state, int false_state)
 289 {
 290         int merged = merge_states(name, owner, sym, true_state, false_state);
 291
 292         /* fixme.  history plus don't call get_state() when not needed*/
 293         //SM_DEBUG("%d set_true_false %s.  Was %d.  Now T:%d F:%d\n",
 294         //       get_lineno(), name, get_state(name, owner, sym), true_state,
 295         //       false_state);
 296
 297         if (!false_stack || !true_stack || !mini_false_stack) {
 298                 printf("Error:  missing true/false stacks\n");
 299                 return;
 300         }
 301         if (__negate) {
 302                 int tmp = true_state;
 303
 304                 true_state = false_state;
 305                 false_state = tmp;
 306         }
 307         set_state(name, owner, sym, true_state);
 308         set_state_stack(&mini_false_stack, name, owner, sym, false_state);
 309         set_state_slist(&and_clumps[1], name, owner, sym, true_state);
 310         set_state_stack(&true_stack, name, owner, sym,
 311                         (__ors?merged:true_state));
 312         set_state_stack(&false_stack, name, owner, sym,
 313                         (__ands?merged:false_state));
 314 }
 315
 316 void delete_state(const char *name, int owner, struct symbol *sym)
 317 {
 318         delete_state_slist(&cur_slist, name, owner, sym);
 319 }
 320
 321 void nullify_path()
 322 {
 323         del_slist(&cur_slist);
 324 }
 325
 326 void clear_all_states()
 327 {
 328         struct slist_head *slist_head;
 329
 330         nullify_path();
 331         del_slist_stack(&false_stack);
 332         del_slist_stack(&true_stack);
 333         del_slist_stack(&break_stack);
 334         del_slist_stack(&switch_stack);
 335         del_slist_stack(&continue_stack);
 336         del_slist_stack(&mini_false_stack);
 337         del_slist(&and_clumps[0]);
 338         del_slist(&and_clumps[1]);
 339
 340         FOR_EACH_PTR(goto_stack, slist_head) {
 341                 del_slist(&slist_head->slist);
 342         } END_FOR_EACH_PTR(slist_head);
 343         __free_ptr_list((struct ptr_list **)&goto_stack);
 344 }
 345
 346 void __first_and_clump()
 347 {
 348         and_clumps[0] = and_clumps[1];
 349         and_clumps[1] = NULL;
 350 }
 351
 352 void __merge_and_clump()
 353 {
 354         struct smatch_state *tmp;
 355
 356         FOR_EACH_PTR(and_clumps[0], tmp) {
 357                 if (tmp->state !=  get_state_slist(and_clumps[1], tmp->name,
 358                                                    tmp->owner, tmp->sym))
 359                         DELETE_CURRENT_PTR(tmp);
 360         } END_FOR_EACH_PTR(tmp);
 361         del_slist(&and_clumps[1]);
 362 }
 363
 364 void __use_and_clumps()
 365 {
 366         struct smatch_state *tmp;
 367
 368         return;
 369         FOR_EACH_PTR(and_clumps[0], tmp) {
 370                 if (tmp)
 371                         set_state_stack(&true_stack, tmp->name, tmp->owner,
 372                                         tmp->sym, tmp->state);
 373         } END_FOR_EACH_PTR(tmp);
 374         del_slist(&and_clumps[0]);
 375 }
 376
 377 void __split_false_states_mini()
 378 {
 379         push_slist(&mini_false_stack, clone_slist(cur_slist));
 380 }
 381
 382 void __use_false_states_mini()
 383 {
 384         struct state_list *slist;
 385
 386         nullify_path();
 387         slist = pop_slist(&mini_false_stack);
 388         merge_slist(slist);
 389         del_slist(&slist);
 390 }
 391
 392 void __pop_false_states_mini()
 393 {
 394         struct state_list *slist;
 395
 396         slist = pop_slist(&mini_false_stack);
 397         del_slist(&slist);
 398 }
 399
 400 void __split_true_false_paths()
 401 {
 402         push_slist(&false_stack, clone_slist(cur_slist));
 403         push_slist(&true_stack, clone_slist(cur_slist));
 404         __split_false_states_mini();
 405 }
 406
 407 void __use_true_states()
 408 {
 409         struct state_list *slist;
 410
 411         __pop_false_states_mini();
 412         nullify_path();
 413         slist = pop_slist(&true_stack);
 414         merge_slist(slist);
 415         del_slist(&slist);
 416 }
 417
 418 void __use_false_states()
 419 {
 420         struct state_list *slist;
 421
 422         push_slist(&true_stack, clone_slist(cur_slist));
 423         nullify_path();
 424         slist = pop_slist(&false_stack);
 425         merge_slist(slist);
 426         del_slist(&slist);
 427 }
 428
 429 void __pop_false_states()
 430 {
 431         struct state_list *slist;
 432
 433         slist = pop_slist(&false_stack);
 434         del_slist(&slist);
 435 }
 436
 437 void __merge_false_states()
 438 {
 439         struct state_list *slist;
 440
 441         slist = pop_slist(&false_stack);
 442         merge_slist(slist);
 443         del_slist(&slist);
 444 }
 445
 446 void __merge_true_states()
 447 {
 448         struct state_list *slist;
 449
 450         slist = pop_slist(&true_stack);
 451         merge_slist(slist);
 452         del_slist(&slist);
 453 }
 454
 455 void __pop_true_states()
 456 {
 457         struct state_list *slist;
 458
 459         slist = pop_slist(&true_stack);
 460         del_slist(&slist);
 461 }
 462
 463 void __push_continues()
 464 {
 465         push_slist(&continue_stack, NULL);
 466 }
 467
 468 void __pop_continues()
 469 {
 470         struct state_list *slist;
 471
 472         slist = pop_slist(&continue_stack);
 473         del_slist(&slist);
 474 }
 475
 476 void __process_continues()
 477 {
 478         struct smatch_state *state;
 479
 480         FOR_EACH_PTR(cur_slist, state) {
 481                 merge_state_stack(&continue_stack, state->name, state->owner,
 482                                   state->sym, state->state);
 483         } END_FOR_EACH_PTR(state);
 484 }
 485
 486 void __merge_continues()
 487 {
 488         struct state_list *slist;
 489
 490         slist = pop_slist(&continue_stack);
 491         merge_slist(slist);
 492         del_slist(&slist);
 493 }
 494
 495 void __push_breaks()
 496 {
 497         push_slist(&break_stack, NULL);
 498 }
 499
 500 void __process_breaks()
 501 {
 502         struct smatch_state *state;
 503
 504         FOR_EACH_PTR(cur_slist, state) {
 505                 merge_state_stack(&break_stack, state->name, state->owner,
 506                                   state->sym, state->state);
 507         } END_FOR_EACH_PTR(state);
 508 }
 509
 510 void __merge_breaks()
 511 {
 512         struct state_list *slist;
 513
 514         slist = pop_slist(&break_stack);
 515         merge_slist(slist);
 516         del_slist(&slist);
 517 }
 518
 519 void __pop_breaks()
 520 {
 521         struct state_list *slist;
 522
 523         slist = pop_slist(&break_stack);
 524         del_slist(&slist);
 525 }
 526
 527 void __save_switch_states()
 528 {
 529         push_slist(&switch_stack, clone_slist(cur_slist));
 530 }
 531
 532 void __merge_switches()
 533 {
 534         struct state_list *slist;
 535
 536         slist = pop_slist(&switch_stack);
 537         merge_slist(slist);
 538         push_slist(&switch_stack, slist);
 539 }
 540
 541 void __pop_switches()
 542 {
 543         struct state_list *slist;
 544
 545         slist = pop_slist(&switch_stack);
 546         del_slist(&slist);
 547 }
 548
 549 void __push_default()
 550 {
 551         push_slist(&default_stack, NULL);
 552         set_state_stack(&default_stack, "has_default", 0, NULL, 0);
 553 }
 554
 555 void __set_default()
 556 {
 557         set_state_stack(&default_stack, "has_default", 0, NULL, 1);
 558 }
 559
 560 int __pop_default()
 561 {
 562         struct state_list *slist;
 563         struct smatch_state *state;
 564
 565         int ret = -1;
 566         slist = pop_slist(&default_stack);
 567         FOR_EACH_PTR(slist, state) {
 568                 if (!strcmp(state->name, "has_default"))
 569                         ret = state->state;
 570         } END_FOR_EACH_PTR(state);
 571         del_slist(&slist);
 572         return ret;
 573 }
 574
 575 static struct slist_head *alloc_slist_head(const char *name,
 576                                          struct state_list *slist)
 577 {
 578         struct slist_head *slist_head = __alloc_slist_head(0);
 579
 580         slist_head->name = (char *)name;
 581         slist_head->slist = slist;
 582         return slist_head;
 583 }
 584
 585 static struct state_list *get_slist_from_slist_stack(const char *name)
 586 {
 587         struct slist_head *tmp;
 588
 589         FOR_EACH_PTR(goto_stack, tmp) {
 590                 if (!strcmp(tmp->name, name))
 591                         return tmp->slist;
 592         } END_FOR_EACH_PTR(tmp);
 593         return NULL;
 594 }
 595
 596 void __save_gotos(const char *name)
 597 {
 598         struct state_list *slist;
 599
 600         slist = get_slist_from_slist_stack(name);
 601         if (slist) {
 602                 struct smatch_state *state;
 603                 FOR_EACH_PTR(cur_slist, state) {
 604                         merge_state_slist(&slist, state->name, state->owner,
 605                                           state->sym, state->state);
 606                 } END_FOR_EACH_PTR(state);
 607                 return;
 608         } else {
 609                 struct state_list *slist;
 610                 struct slist_head *slist_head;
 611                 slist = clone_slist(cur_slist);
 612                 slist_head = alloc_slist_head(name, slist);
 613                 add_ptr_list(&goto_stack, slist_head);
 614         }
 615 }
 616
 617 void __merge_gotos(const char *name)
 618 {
 619         struct state_list *slist;
 620
 621         slist = get_slist_from_slist_stack(name);
 622         merge_slist(slist);
 623 }