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