sys/src/cmd/spin/structs.c

   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 }