type.c (13406B)
1 #include <u.h> 2 #include <libc.h> 3 #include <bio.h> 4 #include <mach.h> 5 #include <ctype.h> 6 #include "dat.h" 7 8 char *prefix = ""; 9 10 static TypeList *thash[1021]; 11 static TypeList *namehash[1021]; 12 static TypeList *alltypes; 13 14 static uint 15 hash(uint num, uint num1) 16 { 17 return (num*1009 + num1*1013) % nelem(thash); 18 } 19 20 static uint 21 shash(char *s) 22 { 23 uint h; 24 25 h = 0; 26 for(; *s; s++) 27 h = 37*h + *s; 28 return h%nelem(namehash); 29 } 30 31 void 32 addnamehash(Type *t) 33 { 34 uint h; 35 36 if(t->name){ 37 h = shash(t->name); 38 namehash[h] = mktl(t, namehash[h]); 39 } 40 } 41 42 static void 43 addhash(Type *t) 44 { 45 uint h; 46 47 if(t->n1 || t->n2){ 48 h = hash(t->n1, t->n2); 49 thash[h] = mktl(t, thash[h]); 50 } 51 if(t->name) 52 addnamehash(t); 53 } 54 55 Type* 56 typebysue(char sue, char *name) 57 { 58 Type *t; 59 TypeList *tl; 60 61 for(tl=namehash[shash(name)]; tl; tl=tl->tl){ 62 t = tl->hd; 63 if(t->sue==sue && t->suename && strcmp(name, t->suename)==0) 64 return t; 65 } 66 t = newtype(); 67 if(sue=='e') 68 t->ty = Enum; 69 else 70 t->ty = Aggr; 71 if(sue=='u') 72 t->isunion = 1; 73 t->sue = sue; 74 t->suename = name; 75 addnamehash(t); 76 return t; 77 } 78 79 Type* 80 typebynum(uint n1, uint n2) 81 { 82 Type *t; 83 TypeList *tl; 84 85 if(n1 || n2){ 86 for(tl=thash[hash(n1, n2)]; tl; tl=tl->tl){ 87 t = tl->hd; 88 if(t->n1==n1 && t->n2==n2) 89 return t; 90 } 91 } 92 93 t = newtype(); 94 t->n1 = n1; 95 t->n2 = n2; 96 addhash(t); 97 return t; 98 } 99 100 Type* 101 newtype(void) 102 { 103 Type *t; 104 static int gen; 105 106 t = emalloc(sizeof *t); 107 t->gen = ++gen; 108 alltypes = mktl(t, alltypes); 109 return t; 110 } 111 112 struct { 113 char *old; 114 char *new; 115 } fixes[] = { /* Font Tab 4 */ 116 "append", "$append", 117 "builtin", "$builtin", 118 "complex", "$complex", 119 "delete", "$delete", 120 "do", "$do", 121 "else", "$else", 122 "eval", "$eval", 123 "fmt", "$fmt", 124 "fn", "$fn", 125 "head", "$head", 126 "if", "$if", 127 "local", "$local", 128 "loop", "$loop", 129 "ret", "$ret", 130 "tail", "$tail", 131 "then", "$then", 132 "var", "$var", 133 "whatis", "$whatis", 134 "while", "$while", 135 136 /* register names! */ 137 /* generic */ 138 "PC", "$PC", 139 "SP", "$SP", 140 "LR", "$LR", 141 "R0", "$R0", 142 "R1", "$R1", 143 "R2", "$R2", 144 "R3", "$R3", 145 "R4", "$R4", 146 "R5", "$R5", 147 "R6", "$R6", 148 "R7", "$R7", 149 "R8", "$R8", 150 "R9", "$R9", 151 "R10", "$R10", 152 "R11", "$R11", 153 "R12", "$R12", 154 "R13", "$R13", 155 "R14", "$R14", 156 "R15", "$R15", 157 "R16", "$R16", 158 "R17", "$R17", 159 "R18", "$R18", 160 "R19", "$R19", 161 "R20", "$R20", 162 "R21", "$R21", 163 "R22", "$R22", 164 "R23", "$R23", 165 "R24", "$R24", 166 "R25", "$R25", 167 "R26", "$R26", 168 "R27", "$R27", 169 "R28", "$R28", 170 "R29", "$R29", 171 "R30", "$R30", 172 "R31", "$R31", 173 "E0", "$E0", 174 "E1", "$E1", 175 "E2", "$E2", 176 "E3", "$E3", 177 "E4", "$E4", 178 "E5", "$E5", 179 "E6", "$E6", 180 "F0", "$F0", 181 "F1", "$F1", 182 "F2", "$F2", 183 "F3", "$F3", 184 "F4", "$F4", 185 "F5", "$F5", 186 "F6", "$F6", 187 "F7", "$F7", 188 "F8", "$F8", 189 "F9", "$F9", 190 "F10", "$F10", 191 "F11", "$F11", 192 "F12", "$F12", 193 "F13", "$F13", 194 "F14", "$F14", 195 "F15", "$F15", 196 "F16", "$F16", 197 "F17", "$F17", 198 "F18", "$F18", 199 "F19", "$F19", 200 "F20", "$F20", 201 "F21", "$F21", 202 "F22", "$F22", 203 "F23", "$F23", 204 "F24", "$F24", 205 "F25", "$F25", 206 "F26", "$F26", 207 "F27", "$F27", 208 "F28", "$F28", 209 "F29", "$F29", 210 "F30", "$F30", 211 "F31", "$F31", 212 213 /* 386 */ 214 "DI", "$DI", 215 "SI", "$SI", 216 "BP", "$BP", 217 "BX", "$BX", 218 "DX", "$DX", 219 "CX", "$CX", 220 "AX", "$AX", 221 "GS", "$GS", 222 "FS", "$FS", 223 "ES", "$ES", 224 "DS", "$DS", 225 "TRAP", "$TRAP", 226 "ECODE", "$ECODE", 227 "CS", "$CS", 228 "EFLAGS", "$EFLAGS", 229 "SS", "$SS", 230 231 /* power */ 232 "CAUSE", "$CAUSE", 233 "SRR1", "$SRR1", 234 "CR", "$CR", 235 "XER", "$XER", 236 "CTR", "$CTR", 237 "VRSAVE", "$VRSAVE", 238 "FPSCR", "$FPSCR" 239 }; 240 241 char* 242 nonempty(char *name) 243 { 244 if(name[0] == '\0') 245 return "__empty__name__"; 246 return name; 247 } 248 249 char* 250 cleanstl(char *name) 251 { 252 char *b, *p; 253 static char buf[65536]; /* These can be huge. */ 254 255 if(strchr(name, '<') == nil) 256 return nonempty(name); 257 258 b = buf; 259 for(p = name; *p != 0; p++){ 260 switch(*p){ 261 case '<': 262 strcpy(b, "_L_"); 263 b += 3; 264 break; 265 case '>': 266 strcpy(b, "_R_"); 267 b += 3; 268 break; 269 case '*': 270 strcpy(b, "_A_"); 271 b += 3; 272 break; 273 case ',': 274 strcpy(b, "_C_"); 275 b += 3; 276 break; 277 case '.': 278 strcpy(b, "_D_"); 279 b += 3; 280 break; 281 default: 282 *b++ = *p; 283 break; 284 } 285 } 286 *b = 0; 287 return buf; 288 } 289 290 char* 291 fixname(char *name) 292 { 293 int i; 294 char *s; 295 static int nbuf; 296 static char buf[8][65536]; 297 298 if(name == nil) 299 return nil; 300 s = demangle(name, buf[nbuf], 1); 301 if(s != name){ 302 if(++nbuf == nelem(buf)) 303 nbuf = 0; 304 name = s; 305 } 306 for(i=0; i<nelem(fixes); i++) 307 if(name[0]==fixes[i].old[0] && strcmp(name, fixes[i].old)==0) 308 return nonempty(fixes[i].new); 309 return nonempty(name); 310 } 311 312 void 313 denumber(void) 314 { 315 memset(thash, 0, sizeof thash); 316 memset(namehash, 0, sizeof namehash); 317 } 318 319 void 320 renumber(TypeList *tl, uint n1) 321 { 322 int n; 323 Type *t, *tt; 324 325 for(; tl; tl=tl->tl){ 326 t = tl->hd; 327 tt = typebynum(n1, t->n2); 328 *tt = *t; 329 tt->n1 = n1; 330 if(tt->n){ 331 n = (tt->n+31)&~31; 332 if(tt->tname){ 333 tt->tname = emalloc(n*sizeof tt->tname[0]); 334 memmove(tt->tname, t->tname, n*sizeof tt->tname[0]); 335 } 336 if(tt->val){ 337 tt->val = emalloc(n*sizeof tt->val[0]); 338 memmove(tt->val, t->val, n*sizeof tt->val[0]); 339 } 340 if(tt->t){ 341 tt->t = emalloc(n*sizeof tt->t[0]); 342 memmove(tt->t, t->t, n*sizeof tt->t[0]); 343 } 344 } 345 addhash(tt); 346 } 347 } 348 349 Type* 350 defer(Type *t) 351 { 352 Type *u, *oldt; 353 int n; 354 355 if(t == nil) 356 return nil; 357 358 /* XXX rob has return t; here */ 359 u = t; 360 n = 0; 361 oldt = t; 362 while(t && (t->ty == Defer || t->ty == Typedef)){ 363 if(n++%2) 364 u = u->sub; 365 t = t->sub; 366 if(t == u) /* cycle */ 367 goto cycle; 368 } 369 if(oldt != t) 370 oldt->sub = t; 371 return t; 372 373 cycle: 374 fprint(2, "cycle\n"); 375 t = oldt; 376 n = 0; 377 while(t && (t->ty==Defer || t->ty==Typedef)){ 378 fprint(2, "t %p/%d %s\n", t, t->ty, t->name); 379 if(t == u && n++ == 2) 380 break; 381 t = t->sub; 382 } 383 return u; 384 } 385 386 static void 387 dotypedef(Type *t) 388 { 389 if(t->ty != Typedef && t->ty != Defer) 390 return; 391 392 if(t->didtypedef) 393 return; 394 395 t->didtypedef = 1; 396 if(t->sub == nil) 397 return; 398 399 /* push names downward to remove anonymity */ 400 if(t->name && t->sub->name == nil) 401 t->sub->name = t->name; 402 403 dotypedef(t->sub); 404 } 405 406 static int 407 countbytes(uvlong x) 408 { 409 int n; 410 411 for(n=0; x; n++) 412 x>>=8; 413 return n; 414 } 415 416 static void 417 dorange(Type *t) 418 { 419 Type *tt; 420 421 if(t->ty != Range) 422 return; 423 if(t->didrange) 424 return; 425 t->didrange = 1; 426 tt = defer(t->sub); 427 if(tt == nil) 428 return; 429 dorange(tt); 430 if(t != tt && tt->ty != Base) 431 return; 432 t->ty = Base; 433 t->xsizeof = tt->xsizeof; 434 if(t->lo == 0) 435 t->printfmt = 'x'; 436 else 437 t->printfmt = 'd'; 438 if(t->xsizeof == 0) 439 t->xsizeof = countbytes(t->hi); 440 } 441 442 char* 443 mkname(char *prefix, char *name) 444 { 445 static char buf[65536]; 446 447 snprint(buf, sizeof buf, "%s%s", prefix, name); 448 return buf; 449 } 450 451 char* 452 nameof(Type *t, int doanon) 453 { 454 static char buf[65536]; 455 char *p; 456 457 if(t->name) 458 strcpy(buf, fixname(t->name)); 459 else if(t->suename) 460 snprint(buf, sizeof buf, "%s_%s", t->isunion ? "union" : "struct", t->suename); 461 else if(doanon) 462 snprint(buf, sizeof buf, "%s_%lud_", prefix, t->gen); 463 else 464 return ""; 465 for(p=buf; *p; p++) 466 if(isspace((uchar)*p)) 467 *p = '_'; 468 return buf; 469 } 470 471 static char 472 basecharof(Type *t) /*XXX */ 473 { 474 switch(t->xsizeof){ 475 default: 476 return 'X'; 477 case 1: 478 return 'b'; 479 case 2: 480 if(t->printfmt=='d') 481 return 'd'; 482 else 483 return 'x'; 484 case 4: 485 if(t->printfmt=='d') 486 return 'D'; 487 else if(t->printfmt=='f') 488 return 'f'; 489 else 490 return 'X'; 491 case 8: 492 if(t->printfmt=='d') 493 return 'V'; 494 else if(t->printfmt=='f') 495 return 'F'; 496 else 497 return 'Y'; 498 } 499 } 500 501 static int 502 nilstrcmp(char *a, char *b) 503 { 504 if(a == b) 505 return 0; 506 if(a == nil) 507 return -1; 508 if(b == nil) 509 return 1; 510 return strcmp(a, b); 511 } 512 513 int careaboutaggrcount; 514 515 static int 516 typecmp(Type *t, Type *u) 517 { 518 int i; 519 520 if(t == u) 521 return 0; 522 if(t == nil) 523 return -1; 524 if(u == nil) 525 return 1; 526 527 if(t->ty < u->ty) 528 return -1; 529 if(t->ty > u->ty) 530 return 1; 531 532 if(t->isunion != u->isunion) 533 return t->isunion - u->isunion; 534 535 i = nilstrcmp(t->name, u->name); 536 if(i) 537 return i; 538 539 i = nilstrcmp(t->suename, u->suename); 540 if(i) 541 return i; 542 543 if(careaboutaggrcount && t->ty == Aggr){ 544 if(t->n > u->n) 545 return -1; 546 if(t->n < u->n) 547 return 1; 548 } 549 550 if(t->name || t->suename) 551 return 0; 552 553 if(t->ty==Enum){ 554 if(t->n < u->n) 555 return -1; 556 if(t->n > u->n) 557 return 1; 558 if(t->n == 0) 559 return 0; 560 i = strcmp(t->tname[0], u->tname[0]); 561 return i; 562 } 563 if(t < u) 564 return -1; 565 if(t > u) 566 return 1; 567 return 0; 568 } 569 570 static int 571 qtypecmp(const void *va, const void *vb) 572 { 573 Type *t, *u; 574 575 t = *(Type**)va; 576 u = *(Type**)vb; 577 return typecmp(t, u); 578 } 579 580 void 581 printtype(Biobuf *b, Type *t) 582 { 583 char *name; 584 int j, nprint; 585 Type *tt, *ttt; 586 587 if(t->printed) 588 return; 589 t->printed = 1; 590 switch(t->ty){ 591 case Aggr: 592 name = nameof(t, 1); 593 Bprint(b, "%B = %lud;\n", mkname("sizeof", name), t->xsizeof); 594 Bprint(b, "aggr %B {\n", name); 595 nprint = 0; 596 for(j=0; j<t->n; j++){ 597 tt = defer(t->t[j]); 598 if(tt && tt->equiv) 599 tt = tt->equiv; 600 if(tt == nil){ 601 Bprint(b, "// oops: nil type\n"); 602 continue; 603 } 604 switch(tt->ty){ 605 default: 606 Bprint(b, "// oops: unknown type %d for %p/%s (%d,%d; %c,%s; %p)\n", 607 tt->ty, tt, fixname(t->tname[j]), 608 tt->n1, tt->n2, tt->sue ? tt->sue : '.', tt->suename, tt->sub); 609 if(0){ 610 Bprint(b, "// t->t[j] = %p\n", ttt=t->t[j]); 611 while(ttt){ 612 Bprint(b, "// %s %d (%d,%d) sub %p\n", ttt->name, ttt->ty, ttt->n1, ttt->n2, ttt->sub); 613 ttt=ttt->sub; 614 } 615 } 616 case Base: 617 case Pointer: 618 case Enum: 619 case Array: 620 case Function: 621 nprint++; 622 Bprint(b, "\t'%c' %lud %B;\n", basecharof(tt), t->val[j], fixname(t->tname[j])); 623 break; 624 case Aggr: 625 nprint++; 626 Bprint(b, "\t%B %lud %B;\n", nameof(tt, 1), t->val[j], fixname(t->tname[j])); 627 break; 628 } 629 } 630 if(nprint == 0) 631 Bprint(b, "\t'X' 0 __dummy;\n"); 632 Bprint(b, "};\n\n"); 633 634 name = nameof(t, 1); /* might have smashed it */ 635 Bprint(b, "defn %B(addr) { %B(addr, \"\"); }\n", name, mkname("indent_", name)); 636 Bprint(b, "defn %B(addr, indent) {\n", mkname("indent_", name)); 637 Bprint(b, "\tcomplex %B addr;\n", name); 638 for(j=0; j<t->n; j++){ 639 name = fixname(t->tname[j]); 640 tt = defer(t->t[j]); 641 if(tt == nil){ 642 Bprint(b, "// oops nil %s\n", name); 643 continue; 644 } 645 switch(tt->ty){ 646 case Base: 647 base: 648 Bprint(b, "\tprint(indent, \"%s\t\", addr.%B, \"\\n\");\n", 649 name, name); 650 break; 651 case Pointer: 652 ttt = defer(tt->sub); 653 if(ttt && ttt->ty == Aggr) 654 Bprint(b, "\tprint(indent, \"%s\t(%s)\", addr.%B, \"\\n\");\n", 655 name, nameof(ttt, 1), name); 656 else 657 goto base; 658 break; 659 case Array: 660 Bprint(b, "\tprint(indent, \"%s\t\", addr.%B\\X, \"\\n\");\n", 661 name, name); 662 break; 663 case Enum: 664 Bprint(b, "\tprint(indent, \"%s\t\", addr.%B, \" \", %B(addr.%B), \"\\n\");\n", 665 name, name, nameof(tt, 1), name); 666 break; 667 case Aggr: 668 Bprint(b, "\tprint(indent, \"%s\t%s{\\n\");\n", 669 name, nameof(tt, 0)); 670 Bprint(b, "\t%B(addr+%lud, indent+\" \");\n", 671 mkname("indent_", nameof(tt, 1)), t->val[j]); 672 Bprint(b, "\tprint(indent, \"}\\n\");\n"); 673 break; 674 } 675 } 676 Bprint(b, "};\n\n"); 677 break; 678 679 case Enum: 680 name = nameof(t, 1); 681 Bprint(b, "// enum %s\n", name); 682 for(j=0; j<t->n; j++) 683 Bprint(b, "%B = %ld;\n", fixname(t->tname[j]), t->val[j]); 684 685 Bprint(b, "%B = {\n", mkname("vals_", name)); 686 for(j=0; j<t->n; j++) 687 Bprint(b, "\t%lud,\n", t->val[j]); 688 Bprint(b, "};\n"); 689 Bprint(b, "%B = {\n", mkname("names_", name)); 690 for(j=0; j<t->n; j++) 691 Bprint(b, "\t\"%s\",\n", fixname(t->tname[j])); 692 Bprint(b, "};\n"); 693 Bprint(b, "defn %B(val) {\n", name); 694 Bprint(b, "\tlocal i;\n"); 695 Bprint(b, "\ti = match(val, %B);\n", mkname("vals_", name)); 696 Bprint(b, "\tif i >= 0 then return %B[i];\n", mkname("names_", name)); 697 Bprint(b, "\treturn \"???\";\n"); 698 Bprint(b, "};\n"); 699 break; 700 } 701 } 702 703 void 704 printtypes(Biobuf *b) 705 { 706 int i, n, nn; 707 Type *t, *tt, **all; 708 TypeList *tl; 709 710 /* check that pointer resolved */ 711 for(tl=alltypes; tl; tl=tl->tl){ 712 t = tl->hd; 713 if(t->ty==None){ 714 if(t->n1 || t->n2) 715 warn("type %d,%d referenced but not defined - %p", t->n1, t->n2, t); 716 else if(t->sue && t->suename) 717 warn("%s %s referenced but not defined", 718 t->sue=='s' ? "struct" : 719 t->sue=='u' ? "union" : 720 t->sue=='e' ? "enum" : "???", t->suename); 721 } 722 } 723 724 /* push typedefs down, base types up */ 725 n = 0; 726 for(tl=alltypes; tl; tl=tl->tl){ 727 n++; 728 t = tl->hd; 729 if(t->ty == Typedef || t->ty == Defer) 730 dotypedef(t); 731 } 732 733 /* push ranges around */ 734 for(tl=alltypes; tl; tl=tl->tl) 735 dorange(tl->hd); 736 737 /* 738 * only take one type of a given name; acid is going to do this anyway, 739 * and this will reduce the amount of code we output considerably. 740 * we could run a DFA equivalence relaxation sort of algorithm 741 * to find the actual equivalence classes, and then rename types 742 * appropriately, but this will do for now. 743 */ 744 all = emalloc(n*sizeof(all[0])); 745 n = 0; 746 for(tl=alltypes; tl; tl=tl->tl) 747 all[n++] = tl->hd; 748 749 careaboutaggrcount = 1; 750 qsort(all, n, sizeof(all[0]), qtypecmp); 751 careaboutaggrcount = 0; 752 753 nn = 0; 754 for(i=0; i<n; i++){ 755 if(i==0 || typecmp(all[i-1], all[i]) != 0) 756 all[nn++] = all[i]; 757 else 758 all[i]->equiv = all[nn-1]; 759 } 760 761 for(tl=alltypes; tl; tl=tl->tl){ 762 t = tl->hd; 763 tt = defer(t); 764 if(tt && tt->equiv) 765 t->equiv = tt->equiv; 766 } 767 768 for(i=0; i<nn; i++) 769 printtype(b, all[i]); 770 771 free(all); 772 } 773 774 void 775 freetypes(void) 776 { 777 memset(thash, 0, sizeof(thash)); 778 memset(namehash, 0, sizeof namehash); 779 }