lib.c

   1 /*
   2  * 'sparse' library helper routines.
   3  *
   4  * Copyright (C) 2003 Transmeta Corp.
   5  *               2003-2004 Linus Torvalds
   6  *
   7  *  Licensed under the Open Software License version 1.1
   8  */
   9 #include <ctype.h>
  10 #include <fcntl.h>
  11 #include <stdarg.h>
  12 #include <stddef.h>
  13 #include <stdio.h>
  14 #include <stdlib.h>
  15 #include <string.h>
  16 #include <unistd.h>
  17 #include <assert.h>
  18
  19 #include <sys/types.h>
  20 #include <sys/stat.h>
  21
  22 #include "lib.h"
  23 #include "allocate.h"
  24 #include "token.h"
  25 #include "parse.h"
  26 #include "symbol.h"
  27 #include "expression.h"
  28 #include "scope.h"
  29 #include "linearize.h"
  30 #include "target.h"
  31
  32 int verbose, optimize, preprocessing;
  33
  34 struct token *skip_to(struct token *token, int op)
  35 {
  36         while (!match_op(token, op) && !eof_token(token))
  37                 token = token->next;
  38         return token;
  39 }
  40
  41 struct token *expect(struct token *token, int op, const char *where)
  42 {
  43         if (!match_op(token, op)) {
  44                 static struct token bad_token;
  45                 if (token != &bad_token) {
  46                         bad_token.next = token;
  47                         warning(token->pos, "Expected %s %s", show_special(op), where);
  48                         warning(token->pos, "got %s", show_token(token));
  49                 }
  50                 if (op == ';')
  51                         return skip_to(token, op);
  52                 return &bad_token;
  53         }
  54         return token->next;
  55 }
  56
  57 unsigned int hexval(unsigned int c)
  58 {
  59         int retval = 256;
  60         switch (c) {
  61         case '0'...'9':
  62                 retval = c - '0';
  63                 break;
  64         case 'a'...'f':
  65                 retval = c - 'a' + 10;
  66                 break;
  67         case 'A'...'F':
  68                 retval = c - 'A' + 10;
  69                 break;
  70         }
  71         return retval;
  72 }
  73
  74 int ptr_list_size(struct ptr_list *head)
  75 {
  76         int nr = 0;
  77
  78         if (head) {
  79                 struct ptr_list *list = head;
  80                 do {
  81                         nr += list->nr;
  82                 } while ((list = list->next) != head);
  83         }
  84         return nr;
  85 }
  86
  87 /*
  88  * Linearize the entries of a list up to a total of 'max',
  89  * and return the nr of entries linearized.
  90  *
  91  * The array to linearize into (second argument) should really
  92  * be "void *x[]", but we want to let people fill in any kind
  93  * of pointer array, so let's just call it "void *".
  94  */
  95 int linearize_ptr_list(struct ptr_list *head, void **arr, int max)
  96 {
  97         int nr = 0;
  98         if (head && max > 0) {
  99                 struct ptr_list *list = head;
 100
 101                 do {
 102                         int i = list->nr;
 103                         if (i > max)
 104                                 i = max;
 105                         memcpy(arr, list->list, i*sizeof(void *));
 106                         arr += i;
 107                         nr += i;
 108                         max -= i;
 109                         if (!max)
 110                                 break;
 111                 } while ((list = list->next) != head);
 112         }
 113         return nr;
 114 }
 115
 116 /*
 117  * When we've walked the list and deleted entries,
 118  * we may need to re-pack it so that we don't have
 119  * any empty blocks left (empty blocks upset the
 120  * walking code
 121  */
 122 void pack_ptr_list(struct ptr_list **listp)
 123 {
 124         struct ptr_list *head = *listp;
 125
 126         if (head) {
 127                 struct ptr_list *entry = head;
 128                 do {
 129                         struct ptr_list *next;
 130 restart:
 131                         next = entry->next;
 132                         if (!entry->nr) {
 133                                 struct ptr_list *prev;
 134                                 if (next == entry) {
 135                                         *listp = NULL;
 136                                         return;
 137                                 }
 138                                 prev = entry->prev;
 139                                 prev->next = next;
 140                                 next->prev = prev;
 141                                 free(entry);
 142                                 if (entry == head) {
 143                                         *listp = next;
 144                                         head = next;
 145                                         goto restart;
 146                                 }
 147                         }
 148                         entry = next;
 149                 } while (entry != head);
 150         }
 151 }
 152
 153 void split_ptr_list_head(struct ptr_list *head)
 154 {
 155         int nr = head->nr / 2;
 156         struct ptr_list *newlist = malloc(sizeof(*newlist));
 157
 158         head->nr -= nr;
 159         newlist->next = head->next;
 160         newlist->prev = head;
 161         head->next = newlist;
 162         newlist->nr = nr;
 163         memcpy(newlist->list, head->list + head->nr, nr * sizeof(void *));
 164         memset(head->list + head->nr, 0xf0, nr * sizeof(void *));
 165 }
 166
 167 void **__add_ptr_list(struct ptr_list **listp, void *ptr)
 168 {
 169         struct ptr_list *list = *listp;
 170         struct ptr_list *last = NULL; /* gcc complains needlessly */
 171         void **ret;
 172         int nr;
 173
 174         if (!list || (nr = (last = list->prev)->nr) >= LIST_NODE_NR) {
 175                 struct ptr_list *newlist = malloc(sizeof(*newlist));
 176                 if (!newlist)
 177                         die("out of memory for symbol/statement lists");
 178                 memset(newlist, 0, sizeof(*newlist));
 179                 if (!list) {
 180                         newlist->next = newlist;
 181                         newlist->prev = newlist;
 182                         *listp = newlist;
 183                 } else {
 184                         newlist->prev = last;
 185                         newlist->next = list;
 186                         list->prev = newlist;
 187                         last->next = newlist;
 188                 }
 189                 last = newlist;
 190                 nr = 0;
 191         }
 192         ret = last->list + nr;
 193         *ret = ptr;
 194         nr++;
 195         last->nr = nr;
 196         return ret;
 197 }
 198
 199 void delete_ptr_list_entry(struct ptr_list **list, void *entry, int count)
 200 {
 201         void *ptr;
 202
 203         FOR_EACH_PTR(*list, ptr) {
 204                 if (ptr == entry) {
 205                         DELETE_CURRENT_PTR(ptr);
 206                         if (!--count)
 207                                 goto out;
 208                 }
 209         } END_FOR_EACH_PTR(ptr);
 210         assert(count <= 0);
 211 out:
 212         pack_ptr_list(list);
 213 }
 214
 215 void replace_ptr_list_entry(struct ptr_list **list, void *old_ptr, void *new_ptr, int count)
 216 {
 217         void *ptr;
 218
 219         FOR_EACH_PTR(*list, ptr) {
 220                 if (ptr==old_ptr) {
 221                         REPLACE_CURRENT_PTR(ptr, new_ptr);
 222                         if (!--count)
 223                                 return;
 224                 }
 225         }END_FOR_EACH_PTR(ptr);
 226         assert(count <= 0);
 227 }
 228
 229 void * delete_ptr_list_last(struct ptr_list **head)
 230 {
 231         void *ptr = NULL;
 232         struct ptr_list *last, *first = *head;
 233
 234         if (!first)
 235                 return NULL;
 236         last = first->prev;
 237         if (last->nr)
 238                 ptr = last->list[--last->nr];
 239         if (last->nr <=0) {
 240                 first->prev = last->prev;
 241                 last->prev->next = first;
 242                 if (last == first)
 243                         *head = NULL;
 244                 free(last);
 245         }
 246         return ptr;
 247 }
 248
 249 void concat_ptr_list(struct ptr_list *a, struct ptr_list **b)
 250 {
 251         void *entry;
 252         FOR_EACH_PTR(a, entry) {
 253                 add_ptr_list(b, entry);
 254         } END_FOR_EACH_PTR(entry);
 255 }
 256
 257 void __free_ptr_list(struct ptr_list **listp)
 258 {
 259         struct ptr_list *tmp, *list = *listp;
 260
 261         if (!list)
 262                 return;
 263
 264         list->prev->next = NULL;
 265         while (list) {
 266                 tmp = list;
 267                 list = list->next;
 268                 free(tmp);
 269         }
 270
 271         *listp = NULL;
 272 }
 273
 274 static void do_warn(const char *type, struct position pos, const char * fmt, va_list args)
 275 {
 276         static char buffer[512];
 277         const char *name;
 278
 279         vsprintf(buffer, fmt, args);
 280         name = input_streams[pos.stream].name;
 281
 282         fprintf(stderr, "%s:%d:%d: %s%s\n",
 283                 name, pos.line, pos.pos, type, buffer);
 284 }
 285
 286 void info(struct position pos, const char * fmt, ...)
 287 {
 288         va_list args;
 289         va_start(args, fmt);
 290         do_warn("", pos, fmt, args);
 291         va_end(args);
 292 }
 293
 294 void warning(struct position pos, const char * fmt, ...)
 295 {
 296         static int warnings = 0;
 297         va_list args;
 298
 299         if (warnings > 100) {
 300                 static int once = 0;
 301                 if (once)
 302                         return;
 303                 fmt = "too many warnings";
 304                 once = 1;
 305         }
 306
 307         va_start(args, fmt);
 308         do_warn("warning: ", pos, fmt, args);
 309         va_end(args);
 310         warnings++;
 311 }
 312
 313 void error(struct position pos, const char * fmt, ...)
 314 {
 315         static int errors = 0;
 316         va_list args;
 317
 318         if (errors > 100) {
 319                 static int once = 0;
 320                 if (once)
 321                         return;
 322                 fmt = "too many errors";
 323                 once = 1;
 324         }
 325
 326         va_start(args, fmt);
 327         do_warn("error: ", pos, fmt, args);
 328         va_end(args);
 329         errors++;
 330 }
 331
 332 void error_die(struct position pos, const char * fmt, ...)
 333 {
 334         va_list args;
 335         va_start(args, fmt);
 336         do_warn("error: ", pos, fmt, args);
 337         va_end(args);
 338         exit(1);
 339 }
 340
 341 void die(const char *fmt, ...)
 342 {
 343         va_list args;
 344         static char buffer[512];
 345
 346         va_start(args, fmt);
 347         vsnprintf(buffer, sizeof(buffer), fmt, args);
 348         va_end(args);
 349
 350         fprintf(stderr, "%s\n", buffer);
 351         exit(1);
 352 }
 353
 354 unsigned int pre_buffer_size;
 355 unsigned char pre_buffer[8192];
 356
 357 int Wdefault_bitfield_sign = 0;
 358 int Wbitwise = 0;
 359 int Wtypesign = 0;
 360 int Wcontext = 0;
 361 int Wundefined_preprocessor = 0;
 362 int preprocess_only;
 363 char *include;
 364 int include_fd = -1;
 365
 366 void add_pre_buffer(const char *fmt, ...)
 367 {
 368         va_list args;
 369         unsigned int size;
 370
 371         va_start(args, fmt);
 372         size = pre_buffer_size;
 373         size += vsnprintf(pre_buffer + size,
 374                 sizeof(pre_buffer) - size,
 375                 fmt, args);
 376         pre_buffer_size = size;
 377         va_end(args);
 378 }
 379
 380 char **handle_switch_D(char *arg, char **next)
 381 {
 382         const char *name = arg + 1;
 383         const char *value = "1";
 384         for (;;) {
 385                 char c;
 386                 c = *++arg;
 387                 if (!c)
 388                         break;
 389                 if (isspace((unsigned char)c) || c == '=') {
 390                         *arg = '\0';
 391                         value = arg + 1;
 392                         break;
 393                 }
 394         }
 395         add_pre_buffer("#define %s %s\n", name, value);
 396         return next;
 397 }
 398
 399 char **handle_switch_E(char *arg, char **next)
 400 {
 401         preprocess_only = 1;
 402         return next;
 403 }
 404
 405 char **handle_switch_v(char *arg, char **next)
 406 {
 407         verbose++;
 408         return next;
 409 }
 410
 411 char **handle_switch_I(char *arg, char **next)
 412 {
 413         char *path = arg+1;
 414
 415         switch (arg[1]) {
 416         case '-':
 417                 /* Explaining '-I-' with a google search:
 418                  *
 419                  *      "Specifying -I after -I- searches for #include directories.
 420                  *       If -I- is specified before, it searches for #include "file"
 421                  *       and not #include ."
 422                  *
 423                  * Which didn't explain it at all to me. Maybe somebody else can
 424                  * explain it properly. We ignore it for now.
 425                  */
 426                 return next;
 427
 428         case '\0':      /* Plain "-I" */
 429                 path = *++next;
 430                 if (!path)
 431                         die("missing argument for -I option");
 432                 /* Fallthrough */
 433         default:
 434                 add_pre_buffer("#add_include \"%s/\"\n", path);
 435         }
 436         return next;
 437 }
 438
 439 char **handle_switch_i(char *arg, char **next)
 440 {
 441         if (*next && !strcmp(arg, "include")) {
 442                 char *name = *++next;
 443                 int fd = open(name, O_RDONLY);
 444
 445                 include_fd = fd;
 446                 include = name;
 447                 if (fd < 0)
 448                         perror(name);
 449         }
 450         return next;
 451 }
 452
 453 char **handle_switch_M(char *arg, char **next)
 454 {
 455         if (!strcmp(arg, "MF") || !strcmp(arg,"MQ") || !strcmp(arg,"MT")) {
 456                 if (!*next)
 457                         die("missing argument for -%s option", arg);
 458                 return next + 1;
 459         }
 460         return next;
 461 }
 462
 463 char **handle_switch_m(char *arg, char **next)
 464 {
 465         if (!strcmp(arg, "m64")) {
 466                 bits_in_long = 64;
 467                 max_int_alignment = 8;
 468                 bits_in_pointer = 64;
 469                 pointer_alignment = 8;
 470         }
 471         return next;
 472 }
 473
 474 char **handle_switch_o(char *arg, char **next)
 475 {
 476         if (!strcmp (arg, "o") && *next)
 477                 return next + 1; // "-o foo"
 478         else
 479                 return next;     // "-ofoo" or (bogus) terminal "-o"
 480 }
 481
 482 const struct warning {
 483         const char *name;
 484         int *flag;
 485 } warnings[] = {
 486         { "default-bitfield-sign", &Wdefault_bitfield_sign },
 487         { "undef", &Wundefined_preprocessor },
 488         { "bitwise", &Wbitwise },
 489         { "typesign", &Wtypesign },
 490         { "context", &Wcontext },
 491 };
 492
 493
 494 char **handle_switch_W(char *arg, char **next)
 495 {
 496         int no = 0;
 497         char *p = arg + 1;
 498         unsigned i;
 499
 500         // Prefixes "no" and "no-" mean to turn warning off.
 501         if (p[0] == 'n' && p[1] == 'o') {
 502                 p += 2;
 503                 if (p[0] == '-')
 504                         p++;
 505                 no = 1;
 506         }
 507
 508         for (i = 0; i < sizeof(warnings) / sizeof(warnings[0]); i++) {
 509                 if (!strcmp(p,warnings[i].name)) {
 510                         *warnings[i].flag = !no;
 511                         return next;
 512                 }
 513         }
 514
 515         // Unknown.
 516         return next;
 517 }
 518
 519 char **handle_switch_U(char *arg, char **next)
 520 {
 521         const char *name = arg + 1;
 522         add_pre_buffer ("#undef %s\n", name);
 523         return next;
 524 }
 525
 526 char **handle_switch_O(char *arg, char **next)
 527 {
 528         int level = 1;
 529         if (arg[1] >= '0' && arg[1] <= '9')
 530                 level = arg[1] - '0';
 531         optimize = level;
 532         return next;
 533 }
 534
 535 char **handle_nostdinc(char *arg, char **next)
 536 {
 537         add_pre_buffer("#nostdinc\n");
 538         return next;
 539 }
 540
 541 struct switches {
 542         const char *name;
 543         char **(*fn)(char *, char**);
 544 };
 545
 546 char **handle_switch(char *arg, char **next)
 547 {
 548         char **rc = next;
 549         static struct switches cmd[] = {
 550                 { "nostdinc", handle_nostdinc },
 551                 { NULL, NULL }
 552         };
 553         struct switches *s;
 554
 555         switch (*arg) {
 556         case 'D': rc = handle_switch_D(arg, next); break;
 557         case 'E': rc = handle_switch_E(arg, next); break;
 558         case 'I': rc = handle_switch_I(arg, next); break;
 559         case 'i': rc = handle_switch_i(arg, next); break;
 560         case 'M': rc = handle_switch_M(arg, next); break;
 561         case 'm': rc = handle_switch_m(arg, next); break;
 562         case 'o': rc = handle_switch_o(arg, next); break;
 563         case 'U': rc = handle_switch_U(arg, next); break;
 564         case 'v': rc = handle_switch_v(arg, next); break;
 565         case 'W': rc = handle_switch_W(arg, next); break;
 566         case 'O': rc = handle_switch_O(arg, next); break;
 567         default:
 568                 break;
 569         }
 570
 571         s = cmd;
 572         while (s->name) {
 573                 if (!strcmp(s->name, arg))
 574                         return s->fn(arg, next);
 575                 s++;
 576         }
 577
 578         /*
 579          * Ignore unknown command line options:
 580          * they're probably gcc switches
 581          */
 582         return rc;
 583 }
 584
 585 void declare_builtin_functions(void)
 586 {
 587         add_pre_buffer("extern void *__builtin_memcpy(void *, const void *, __SIZE_TYPE__);\n");
 588         add_pre_buffer("extern void *__builtin_return_address(unsigned int);\n");
 589         add_pre_buffer("extern void *__builtin_frame_address(unsigned int);\n");
 590         add_pre_buffer("extern void *__builtin_memset(void *, int, __SIZE_TYPE__);\n");
 591         add_pre_buffer("extern void __builtin_trap(void);\n");
 592         add_pre_buffer("extern int __builtin_ffs(int);\n");
 593         add_pre_buffer("extern void *__builtin_alloca(__SIZE_TYPE__);\n");
 594 }
 595
 596 void create_builtin_stream(void)
 597 {
 598         add_pre_buffer("#define __GNUC__ 2\n");
 599         add_pre_buffer("#define __GNUC_MINOR__ 95\n");
 600         add_pre_buffer("#define __extension__\n");
 601         add_pre_buffer("#define __pragma__\n");
 602
 603         // gcc defines __SIZE_TYPE__ to be size_t.  For linux/i86 and
 604         // solaris/sparc that is really "unsigned int" and for linux/x86_64
 605         // it is "long unsigned int".  In either case we can probably
 606         // get away with this.  We need the #ifndef as cgcc will define
 607         // the right __SIZE_TYPE__.
 608         add_pre_buffer("#weak_define __SIZE_TYPE__ long unsigned int\n");
 609         add_pre_buffer("#weak_define __STDC__ 1\n");
 610
 611         add_pre_buffer("#define __builtin_stdarg_start(a,b) ((a) = (__builtin_va_list)(&(b)))\n");
 612         add_pre_buffer("#define __builtin_va_start(a,b) ((a) = (__builtin_va_list)(&(b)))\n");
 613         add_pre_buffer("#define __builtin_va_arg(arg,type)  ({ type __va_arg_ret = *(type *)(arg); arg += sizeof(type); __va_arg_ret; })\n");
 614         add_pre_buffer("#define __builtin_va_alist (*(void *)0)\n");
 615         add_pre_buffer("#define __builtin_va_arg_incr(x) ((x) + 1)\n");
 616         add_pre_buffer("#define __builtin_va_end(arg)\n");
 617 }
 618
 619 static void do_predefined(char *filename)
 620 {
 621         add_pre_buffer("#define __BASE_FILE__ \"%s\"\n", filename);
 622         add_pre_buffer("#define __DATE__ \"??? ?? ????\"\n");
 623         add_pre_buffer("#define __TIME__ \"??:??:??\"\n");
 624 }
 625
 626 struct symbol_list *sparse(int argc, char **argv)
 627 {
 628         int fd;
 629         char *filename = NULL, **args;
 630         struct token *token;
 631
 632         // Initialize symbol stream first, so that we can add defines etc
 633         init_symbols();
 634
 635         args = argv;
 636         for (;;) {
 637                 char *arg = *++args;
 638                 if (!arg)
 639                         break;
 640                 if (arg[0] == '-' && arg[1]) {
 641                         args = handle_switch(arg+1, args);
 642                         continue;
 643                 }
 644                 filename = arg;
 645         }
 646
 647         if (!filename)
 648                 die("no input files given");
 649
 650         // Initialize type system
 651         init_ctype();
 652
 653         create_builtin_stream();
 654         add_pre_buffer("#define __CHECKER__ 1\n");
 655         if (!preprocess_only)
 656                 declare_builtin_functions();
 657
 658         do_predefined(filename);
 659
 660         if (strcmp (filename, "-") == 0) {
 661                 fd = 0;
 662         } else {
 663                 fd = open(filename, O_RDONLY);
 664                 if (fd < 0)
 665                         die("No such file: %s", filename);
 666         }
 667
 668         // Tokenize the input stream
 669         token = tokenize(filename, fd, NULL, includepath);
 670         close(fd);
 671
 672         // Prepend any "include" file to the stream.
 673         if (include_fd >= 0)
 674                 token = tokenize(include, include_fd, token, includepath);
 675
 676         // Prepend the initial built-in stream
 677         token = tokenize_buffer(pre_buffer, pre_buffer_size, token);
 678
 679         // Pre-process the stream
 680         token = preprocess(token);
 681
 682         if (preprocess_only) {
 683                 while (!eof_token(token)) {
 684                         int prec = 1;
 685                         struct token *next = token->next;
 686                         const char *separator = "";
 687                         if (next->pos.whitespace)
 688                                 separator = " ";
 689                         if (next->pos.newline) {
 690                                 separator = "\n\t\t\t\t\t";
 691                                 prec = next->pos.pos;
 692                                 if (prec > 4)
 693                                         prec = 4;
 694                         }
 695                         printf("%s%.*s", show_token(token), prec, separator);
 696                         token = next;
 697                 }
 698                 putchar('\n');
 699
 700                 return NULL;
 701         }
 702
 703         // Parse the resulting C code
 704         return translation_unit(token);
 705 }