1 /***** spin: structs.c *****/ 2 3 /* Copyright (c) 1989-2003 by Lucent Technologies, Bell Laboratories. */ 4 /* All Rights Reserved. This software is for educational purposes only. */ 5 /* No guarantee whatsoever is expressed or implied by the distribution of */ 6 /* this code. Permission is given to distribute this code provided that */ 7 /* this introductory message is not removed and no monies are exchanged. */ 8 /* Software written by Gerard J. Holzmann. For tool documentation see: */ 9 /* http://spinroot.com/ */ 10 /* Send all bug-reports and/or questions to: bugs@spinroot.com */ 11 12 #include "spin.h" 13 #include "y.tab.h" 14 15 typedef struct UType { 16 Symbol *nm; /* name of the type */ 17 Lextok *cn; /* contents */ 18 struct UType *nxt; /* linked list */ 19 } UType; 20 21 extern Symbol *Fname; 22 extern int lineno, depth, Expand_Ok, has_hidden, in_for; 23 24 Symbol *owner; 25 26 static UType *Unames = 0; 27 static UType *Pnames = 0; 28 29 static Lextok *cpnn(Lextok *, int, int, int); 30 extern void sr_mesg(FILE *, int, int); 31 32 void 33 setuname(Lextok *n) 34 { UType *tmp; 35 36 if (!owner) 37 fatal("illegal reference inside typedef", (char *) 0); 38 39 for (tmp = Unames; tmp; tmp = tmp->nxt) 40 if (!strcmp(owner->name, tmp->nm->name)) 41 { non_fatal("typename %s was defined before", 42 tmp->nm->name); 43 return; 44 } 45 46 tmp = (UType *) emalloc(sizeof(UType)); 47 tmp->nm = owner; 48 tmp->cn = n; 49 tmp->nxt = Unames; 50 Unames = tmp; 51 } 52 53 static void 54 putUname(FILE *fd, UType *tmp) 55 { Lextok *fp, *tl; 56 57 if (!tmp) return; 58 putUname(fd, tmp->nxt); /* postorder */ 59 fprintf(fd, "struct %s { /* user defined type */\n", 60 tmp->nm->name); 61 for (fp = tmp->cn; fp; fp = fp->rgt) 62 for (tl = fp->lft; tl; tl = tl->rgt) 63 typ2c(tl->sym); 64 fprintf(fd, "};\n"); 65 } 66 67 void 68 putunames(FILE *fd) 69 { 70 putUname(fd, Unames); 71 } 72 73 int 74 isutype(char *t) 75 { UType *tmp; 76 77 for (tmp = Unames; tmp; tmp = tmp->nxt) 78 { if (!strcmp(t, tmp->nm->name)) 79 return 1; 80 } 81 return 0; 82 } 83 84 Lextok * 85 getuname(Symbol *t) 86 { UType *tmp; 87 88 for (tmp = Unames; tmp; tmp = tmp->nxt) 89 { if (!strcmp(t->name, tmp->nm->name)) 90 return tmp->cn; 91 } 92 fatal("%s is not a typename", t->name); 93 return (Lextok *)0; 94 } 95 96 void 97 setutype(Lextok *p, Symbol *t, Lextok *vis) /* user-defined types */ 98 { int oln = lineno; 99 Symbol *ofn = Fname; 100 Lextok *m, *n; 101 102 m = getuname(t); 103 for (n = p; n; n = n->rgt) 104 { lineno = n->ln; 105 Fname = n->fn; 106 if (n->sym->type) 107 fatal("redeclaration of '%s'", n->sym->name); 108 109 if (n->sym->nbits > 0) 110 non_fatal("(%s) only an unsigned can have width-field", 111 n->sym->name); 112 113 if (Expand_Ok) 114 n->sym->hidden |= (4|8|16); /* formal par */ 115 116 if (vis) 117 { if (strncmp(vis->sym->name, ":hide:", (size_t) 6) == 0) 118 { n->sym->hidden |= 1; 119 has_hidden++; 120 } else if (strncmp(vis->sym->name, ":show:", (size_t) 6) == 0) 121 n->sym->hidden |= 2; 122 else if (strncmp(vis->sym->name, ":local:", (size_t) 7) == 0) 123 n->sym->hidden |= 64; 124 } 125 n->sym->type = STRUCT; /* classification */ 126 n->sym->Slst = m; /* structure itself */ 127 n->sym->Snm = t; /* name of typedef */ 128 n->sym->Nid = 0; /* this is no chan */ 129 n->sym->hidden |= 4; 130 if (n->sym->nel <= 0) 131 non_fatal("bad array size for '%s'", n->sym->name); 132 } 133 lineno = oln; 134 Fname = ofn; 135 } 136 137 static Symbol * 138 do_same(Lextok *n, Symbol *v, int xinit) 139 { Lextok *tmp, *fp, *tl; 140 int ix = eval(n->lft); 141 int oln = lineno; 142 Symbol *ofn = Fname; 143 144 lineno = n->ln; 145 Fname = n->fn; 146 147 /* n->sym->type == STRUCT 148 * index: n->lft 149 * subfields: n->rgt 150 * structure template: n->sym->Slst 151 * runtime values: n->sym->Sval 152 */ 153 if (xinit) ini_struct(v); /* once, at top level */ 154 155 if (ix >= v->nel || ix < 0) 156 { printf("spin: indexing %s[%d] - size is %d\n", 157 v->name, ix, v->nel); 158 fatal("indexing error \'%s\'", v->name); 159 } 160 if (!n->rgt || !n->rgt->lft) 161 { non_fatal("no subfields %s", v->name); /* i.e., wants all */ 162 lineno = oln; Fname = ofn; 163 return ZS; 164 } 165 166 if (n->rgt->ntyp != '.') 167 { printf("bad subfield type %d\n", n->rgt->ntyp); 168 alldone(1); 169 } 170 171 tmp = n->rgt->lft; 172 if (tmp->ntyp != NAME && tmp->ntyp != TYPE) 173 { printf("bad subfield entry %d\n", tmp->ntyp); 174 alldone(1); 175 } 176 for (fp = v->Sval[ix]; fp; fp = fp->rgt) 177 for (tl = fp->lft; tl; tl = tl->rgt) 178 if (!strcmp(tl->sym->name, tmp->sym->name)) 179 { lineno = oln; Fname = ofn; 180 return tl->sym; 181 } 182 fatal("cannot locate subfield %s", tmp->sym->name); 183 return ZS; 184 } 185 186 int 187 Rval_struct(Lextok *n, Symbol *v, int xinit) /* n varref, v valref */ 188 { Symbol *tl; 189 Lextok *tmp; 190 int ix; 191 192 if (!n || !(tl = do_same(n, v, xinit))) 193 return 0; 194 195 tmp = n->rgt->lft; 196 if (tmp->sym->type == STRUCT) 197 { return Rval_struct(tmp, tl, 0); 198 } else if (tmp->rgt) 199 fatal("non-zero 'rgt' on non-structure", 0); 200 201 ix = eval(tmp->lft); 202 /* printf("%d: ix: %d (%d) %d\n", depth, ix, tl->nel, tl->val[ix]); */ 203 if (ix >= tl->nel || ix < 0) 204 fatal("indexing error \'%s\'", tl->name); 205 206 return cast_val(tl->type, tl->val[ix], tl->nbits); 207 } 208 209 int 210 Lval_struct(Lextok *n, Symbol *v, int xinit, int a) /* a = assigned value */ 211 { Symbol *tl; 212 Lextok *tmp; 213 int ix; 214 215 if (!(tl = do_same(n, v, xinit))) 216 return 1; 217 218 tmp = n->rgt->lft; 219 if (tmp->sym->type == STRUCT) 220 return Lval_struct(tmp, tl, 0, a); 221 else if (tmp->rgt) 222 fatal("non-zero 'rgt' on non-structure", 0); 223 224 ix = eval(tmp->lft); 225 if (ix >= tl->nel || ix < 0) 226 fatal("indexing error \'%s\'", tl->name); 227 228 if (tl->nbits > 0) 229 a = (a & ((1<<tl->nbits)-1)); 230 231 if (a != tl->val[ix]) 232 { tl->val[ix] = a; 233 tl->setat = depth; 234 } 235 return 1; 236 } 237 238 int 239 Cnt_flds(Lextok *m) 240 { Lextok *fp, *tl, *n; 241 int cnt = 0; 242 243 if (m->ntyp == ',') 244 { n = m; 245 goto is_lst; 246 } 247 if (!m->sym || m->ntyp != STRUCT) 248 return 1; 249 250 n = getuname(m->sym); 251 is_lst: 252 for (fp = n; fp; fp = fp->rgt) 253 for (tl = fp->lft; tl; tl = tl->rgt) 254 { if (tl->sym->type == STRUCT) 255 { if (tl->sym->nel > 1 || tl->sym->isarray) 256 fatal("array of structures in param list, %s", 257 tl->sym->name); 258 cnt += Cnt_flds(tl->sym->Slst); 259 } else 260 cnt += tl->sym->nel; 261 } 262 return cnt; 263 } 264 265 int 266 Sym_typ(Lextok *t) 267 { Symbol *s = t->sym; 268 269 if (!s) return 0; 270 271 if (s->type != STRUCT) 272 return s->type; 273 274 if (!t->rgt 275 || t->rgt->ntyp != '.' /* gh: had ! in wrong place */ 276 || !t->rgt->lft) 277 return STRUCT; /* not a field reference */ 278 279 return Sym_typ(t->rgt->lft); 280 } 281 282 int 283 Width_set(int *wdth, int i, Lextok *n) 284 { Lextok *fp, *tl; 285 int j = i, k; 286 287 for (fp = n; fp; fp = fp->rgt) 288 for (tl = fp->lft; tl; tl = tl->rgt) 289 { if (tl->sym->type == STRUCT) 290 j = Width_set(wdth, j, tl->sym->Slst); 291 else 292 { for (k = 0; k < tl->sym->nel; k++, j++) 293 wdth[j] = tl->sym->type; 294 } } 295 return j; 296 } 297 298 void 299 ini_struct(Symbol *s) 300 { int i; Lextok *fp, *tl; 301 302 if (s->type != STRUCT) /* last step */ 303 { (void) checkvar(s, 0); 304 return; 305 } 306 if (s->Sval == (Lextok **) 0) 307 { s->Sval = (Lextok **) emalloc(s->nel * sizeof(Lextok *)); 308 for (i = 0; i < s->nel; i++) 309 { s->Sval[i] = cpnn(s->Slst, 1, 1, 1); 310 311 for (fp = s->Sval[i]; fp; fp = fp->rgt) 312 for (tl = fp->lft; tl; tl = tl->rgt) 313 ini_struct(tl->sym); 314 } } 315 } 316 317 static Lextok * 318 cpnn(Lextok *s, int L, int R, int S) 319 { Lextok *d; extern int Nid; 320 321 if (!s) return ZN; 322 323 d = (Lextok *) emalloc(sizeof(Lextok)); 324 d->uiid = s->uiid; 325 d->ntyp = s->ntyp; 326 d->val = s->val; 327 d->ln = s->ln; 328 d->fn = s->fn; 329 d->sym = s->sym; 330 if (L) d->lft = cpnn(s->lft, 1, 1, S); 331 if (R) d->rgt = cpnn(s->rgt, 1, 1, S); 332 333 if (S && s->sym) 334 { d->sym = (Symbol *) emalloc(sizeof(Symbol)); 335 memcpy(d->sym, s->sym, sizeof(Symbol)); 336 if (d->sym->type == CHAN) 337 d->sym->Nid = ++Nid; 338 } 339 if (s->sq || s->sl) 340 fatal("cannot happen cpnn", (char *) 0); 341 342 return d; 343 } 344 345 int 346 full_name(FILE *fd, Lextok *n, Symbol *v, int xinit) 347 { Symbol *tl; 348 Lextok *tmp; 349 int hiddenarrays = 0; 350 351 fprintf(fd, "%s", v->name); 352 353 if (!n || !(tl = do_same(n, v, xinit))) 354 return 0; 355 tmp = n->rgt->lft; 356 357 if (tmp->sym->type == STRUCT) 358 { fprintf(fd, "."); 359 hiddenarrays = full_name(fd, tmp, tl, 0); 360 goto out; 361 } 362 fprintf(fd, ".%s", tl->name); 363 out: if (tmp->sym->nel > 1 || tmp->sym->isarray == 1) 364 { fprintf(fd, "[%d]", eval(tmp->lft)); 365 hiddenarrays = 1; 366 } 367 return hiddenarrays; 368 } 369 370 void 371 validref(Lextok *p, Lextok *c) 372 { Lextok *fp, *tl; 373 char lbuf[512]; 374 375 for (fp = p->sym->Slst; fp; fp = fp->rgt) 376 for (tl = fp->lft; tl; tl = tl->rgt) 377 if (strcmp(tl->sym->name, c->sym->name) == 0) 378 return; 379 380 sprintf(lbuf, "no field '%s' defined in structure '%s'\n", 381 c->sym->name, p->sym->name); 382 non_fatal(lbuf, (char *) 0); 383 } 384 385 void 386 struct_name(Lextok *n, Symbol *v, int xinit, char *buf) 387 { Symbol *tl; 388 Lextok *tmp; 389 char lbuf[512]; 390 391 if (!n || !(tl = do_same(n, v, xinit))) 392 return; 393 tmp = n->rgt->lft; 394 if (tmp->sym->type == STRUCT) 395 { strcat(buf, "."); 396 struct_name(tmp, tl, 0, buf); 397 return; 398 } 399 sprintf(lbuf, ".%s", tl->name); 400 strcat(buf, lbuf); 401 if (tmp->sym->nel > 1 || tmp->sym->isarray == 1) 402 { sprintf(lbuf, "[%d]", eval(tmp->lft)); 403 strcat(buf, lbuf); 404 } 405 } 406 407 void 408 walk2_struct(char *s, Symbol *z) 409 { Lextok *fp, *tl; 410 char eprefix[128]; 411 int ix; 412 extern void Done_case(char *, Symbol *); 413 414 ini_struct(z); 415 if (z->nel == 1 && z->isarray == 0) 416 sprintf(eprefix, "%s%s.", s, z->name); 417 for (ix = 0; ix < z->nel; ix++) 418 { if (z->nel > 1 || z->isarray == 1) 419 sprintf(eprefix, "%s%s[%d].", s, z->name, ix); 420 for (fp = z->Sval[ix]; fp; fp = fp->rgt) 421 for (tl = fp->lft; tl; tl = tl->rgt) 422 { if (tl->sym->type == STRUCT) 423 walk2_struct(eprefix, tl->sym); 424 else if (tl->sym->type == CHAN) 425 Done_case(eprefix, tl->sym); 426 } } 427 } 428 429 void 430 walk_struct(FILE *ofd, int dowhat, char *s, Symbol *z, char *a, char *b, char *c) 431 { Lextok *fp, *tl; 432 char eprefix[128]; 433 int ix; 434 435 ini_struct(z); 436 if (z->nel == 1 && z->isarray == 0) 437 sprintf(eprefix, "%s%s.", s, z->name); 438 for (ix = 0; ix < z->nel; ix++) 439 { if (z->nel > 1 || z->isarray == 1) 440 sprintf(eprefix, "%s%s[%d].", s, z->name, ix); 441 for (fp = z->Sval[ix]; fp; fp = fp->rgt) 442 for (tl = fp->lft; tl; tl = tl->rgt) 443 { if (tl->sym->type == STRUCT) 444 walk_struct(ofd, dowhat, eprefix, tl->sym, a,b,c); 445 else 446 do_var(ofd, dowhat, eprefix, tl->sym, a,b,c); 447 } } 448 } 449 450 void 451 c_struct(FILE *fd, char *ipref, Symbol *z) 452 { Lextok *fp, *tl; 453 char pref[256], eprefix[300]; 454 int ix; 455 456 ini_struct(z); 457 458 for (ix = 0; ix < z->nel; ix++) 459 for (fp = z->Sval[ix]; fp; fp = fp->rgt) 460 for (tl = fp->lft; tl; tl = tl->rgt) 461 { strcpy(eprefix, ipref); 462 if (z->nel > 1 || z->isarray == 1) 463 { /* insert index before last '.' */ 464 eprefix[strlen(eprefix)-1] = '\0'; 465 sprintf(pref, "[ %d ].", ix); 466 strcat(eprefix, pref); 467 } 468 if (tl->sym->type == STRUCT) 469 { strcat(eprefix, tl->sym->name); 470 strcat(eprefix, "."); 471 c_struct(fd, eprefix, tl->sym); 472 } else 473 c_var(fd, eprefix, tl->sym); 474 } 475 } 476 477 void 478 dump_struct(Symbol *z, char *prefix, RunList *r) 479 { Lextok *fp, *tl; 480 char eprefix[256]; 481 int ix, jx; 482 483 ini_struct(z); 484 485 for (ix = 0; ix < z->nel; ix++) 486 { if (z->nel > 1 || z->isarray == 1) 487 sprintf(eprefix, "%s[%d]", prefix, ix); 488 else 489 strcpy(eprefix, prefix); 490 491 for (fp = z->Sval[ix]; fp; fp = fp->rgt) 492 for (tl = fp->lft; tl; tl = tl->rgt) 493 { if (tl->sym->type == STRUCT) 494 { char pref[300]; 495 strcpy(pref, eprefix); 496 strcat(pref, "."); 497 strcat(pref, tl->sym->name); 498 dump_struct(tl->sym, pref, r); 499 } else 500 for (jx = 0; jx < tl->sym->nel; jx++) 501 { if (tl->sym->type == CHAN) 502 doq(tl->sym, jx, r); 503 else 504 { printf("\t\t"); 505 if (r) 506 printf("%s(%d):", r->n->name, r->pid); 507 printf("%s.%s", eprefix, tl->sym->name); 508 if (tl->sym->nel > 1 || tl->sym->isarray == 1) 509 printf("[%d]", jx); 510 printf(" = "); 511 sr_mesg(stdout, tl->sym->val[jx], 512 tl->sym->type == MTYPE); 513 printf("\n"); 514 } } } 515 } 516 } 517 518 static int 519 retrieve(Lextok **targ, int i, int want, Lextok *n, int Ntyp) 520 { Lextok *fp, *tl; 521 int j = i, k; 522 523 for (fp = n; fp; fp = fp->rgt) 524 for (tl = fp->lft; tl; tl = tl->rgt) 525 { if (tl->sym->type == STRUCT) 526 { j = retrieve(targ, j, want, tl->sym->Slst, Ntyp); 527 if (j < 0) 528 { Lextok *x = cpnn(tl, 1, 0, 0); 529 x->rgt = nn(ZN, '.', (*targ), ZN); 530 (*targ) = x; 531 return -1; 532 } 533 } else 534 { for (k = 0; k < tl->sym->nel; k++, j++) 535 { if (j == want) 536 { *targ = cpnn(tl, 1, 0, 0); 537 (*targ)->lft = nn(ZN, CONST, ZN, ZN); 538 (*targ)->lft->val = k; 539 if (Ntyp) 540 (*targ)->ntyp = (short) Ntyp; 541 return -1; 542 } 543 } } } 544 return j; 545 } 546 547 static int 548 is_explicit(Lextok *n) 549 { 550 if (!n) return 0; 551 if (!n->sym) fatal("unexpected - no symbol", 0); 552 if (n->sym->type != STRUCT) return 1; 553 if (!n->rgt) return 0; 554 if (n->rgt->ntyp != '.') 555 { lineno = n->ln; 556 Fname = n->fn; 557 printf("ntyp %d\n", n->rgt->ntyp); 558 fatal("unexpected %s, no '.'", n->sym->name); 559 } 560 return is_explicit(n->rgt->lft); 561 } 562 563 Lextok * 564 expand(Lextok *n, int Ok) 565 /* turn rgt-lnked list of struct nms, into ',' list of flds */ 566 { Lextok *x = ZN, *y; 567 568 if (!Ok) return n; 569 570 while (n) 571 { y = mk_explicit(n, 1, 0); 572 if (x) 573 (void) tail_add(x, y); 574 else 575 x = y; 576 577 n = n->rgt; 578 } 579 return x; 580 } 581 582 Lextok * 583 mk_explicit(Lextok *n, int Ok, int Ntyp) 584 /* produce a single ',' list of fields */ 585 { Lextok *bld = ZN, *x; 586 int i, cnt; extern int IArgs; 587 588 if (n->sym->type != STRUCT 589 || in_for 590 || is_explicit(n)) 591 return n; 592 593 594 if (n->rgt 595 && n->rgt->ntyp == '.' 596 && n->rgt->lft 597 && n->rgt->lft->sym 598 && n->rgt->lft->sym->type == STRUCT) 599 { Lextok *y; 600 bld = mk_explicit(n->rgt->lft, Ok, Ntyp); 601 for (x = bld; x; x = x->rgt) 602 { y = cpnn(n, 1, 0, 0); 603 y->rgt = nn(ZN, '.', x->lft, ZN); 604 x->lft = y; 605 } 606 607 return bld; 608 } 609 610 if (!Ok || !n->sym->Slst) 611 { if (IArgs) return n; 612 printf("spin: saw '"); 613 comment(stdout, n, 0); 614 printf("'\n"); 615 fatal("incomplete structure ref '%s'", n->sym->name); 616 } 617 618 cnt = Cnt_flds(n->sym->Slst); 619 for (i = cnt-1; i >= 0; i--) 620 { bld = nn(ZN, ',', ZN, bld); 621 if (retrieve(&(bld->lft), 0, i, n->sym->Slst, Ntyp) >= 0) 622 { printf("cannot retrieve field %d\n", i); 623 fatal("bad structure %s", n->sym->name); 624 } 625 x = cpnn(n, 1, 0, 0); 626 x->rgt = nn(ZN, '.', bld->lft, ZN); 627 bld->lft = x; 628 } 629 return bld; 630 } 631 632 Lextok * 633 tail_add(Lextok *a, Lextok *b) 634 { Lextok *t; 635 636 for (t = a; t->rgt; t = t->rgt) 637 if (t->ntyp != ',') 638 fatal("unexpected type - tail_add", 0); 639 t->rgt = b; 640 return a; 641 } 642 643 void 644 setpname(Lextok *n) 645 { UType *tmp; 646 647 for (tmp = Pnames; tmp; tmp = tmp->nxt) 648 if (!strcmp(n->sym->name, tmp->nm->name)) 649 { non_fatal("proctype %s redefined", 650 n->sym->name); 651 return; 652 } 653 tmp = (UType *) emalloc(sizeof(UType)); 654 tmp->nm = n->sym; 655 tmp->nxt = Pnames; 656 Pnames = tmp; 657 } 658 659 int 660 isproctype(char *t) 661 { UType *tmp; 662 663 for (tmp = Pnames; tmp; tmp = tmp->nxt) 664 { if (!strcmp(t, tmp->nm->name)) 665 return 1; 666 } 667 return 0; 668 } 669