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