sys/src/cmd/spin/flow.c

   1 /***** spin: flow.c *****/
   2
   3 /*
   4  * This file is part of the public release of Spin. It is subject to the
   5  * terms in the LICENSE file that is included in this source directory.
   6  * Tool documentation is available at http://spinroot.com
   7  */
   8
   9 #include "spin.h"
  10 #include "y.tab.h"
  11
  12 extern Symbol   *Fname;
  13 extern int      nr_errs, lineno, verbose, in_for, old_scope_rules, s_trail;
  14 extern short    has_unless, has_badelse, has_xu;
  15 extern char CurScope[MAXSCOPESZ];
  16
  17 Element *Al_El = ZE;
  18 Label   *labtab = (Label *) 0;
  19 int     Unique = 0, Elcnt = 0, DstepStart = -1;
  20 int     initialization_ok = 1;
  21 short   has_accept;
  22
  23 static Lbreak   *breakstack = (Lbreak *) 0;
  24 static Lextok   *innermost;
  25 static SeqList  *cur_s = (SeqList *) 0;
  26 static int      break_id=0;
  27
  28 static Element  *if_seq(Lextok *);
  29 static Element  *new_el(Lextok *);
  30 static Element  *unless_seq(Lextok *);
  31 static void     add_el(Element *, Sequence *);
  32 static void     attach_escape(Sequence *, Sequence *);
  33 static void     mov_lab(Symbol *, Element *, Element *);
  34 static void     walk_atomic(Element *, Element *, int);
  35
  36 void
  37 open_seq(int top)
  38 {       SeqList *t;
  39         Sequence *s = (Sequence *) emalloc(sizeof(Sequence));
  40         s->minel = -1;
  41
  42         t = seqlist(s, cur_s);
  43         cur_s = t;
  44         if (top)
  45         {       Elcnt = 1;
  46                 initialization_ok = 1;
  47         } else
  48         {       initialization_ok = 0;
  49         }
  50 }
  51
  52 void
  53 rem_Seq(void)
  54 {
  55         DstepStart = Unique;
  56 }
  57
  58 void
  59 unrem_Seq(void)
  60 {
  61         DstepStart = -1;
  62 }
  63
  64 static int
  65 Rjumpslocal(Element *q, Element *stop)
  66 {       Element *lb, *f;
  67         SeqList *h;
  68
  69         /* allow no jumps out of a d_step sequence */
  70         for (f = q; f && f != stop; f = f->nxt)
  71         {       if (f && f->n && f->n->ntyp == GOTO)
  72                 {       lb = get_lab(f->n, 0);
  73                         if (!lb || lb->Seqno < DstepStart)
  74                         {       lineno = f->n->ln;
  75                                 Fname = f->n->fn;
  76                                 return 0;
  77                 }       }
  78                 for (h = f->sub; h; h = h->nxt)
  79                 {       if (!Rjumpslocal(h->this->frst, h->this->last))
  80                                 return 0;
  81
  82         }       }
  83         return 1;
  84 }
  85
  86 void
  87 cross_dsteps(Lextok *a, Lextok *b)
  88 {
  89         if (a && b
  90         &&  a->indstep != b->indstep)
  91         {       lineno = a->ln;
  92                 Fname  = a->fn;
  93                 if (!s_trail)
  94                 fatal("jump into d_step sequence", (char *) 0);
  95         }
  96 }
  97
  98 int
  99 is_skip(Lextok *n)
 100 {
 101         return (n->ntyp == PRINT
 102         ||      n->ntyp == PRINTM
 103         ||      (n->ntyp == 'c'
 104                 && n->lft
 105                 && n->lft->ntyp == CONST
 106                 && n->lft->val  == 1));
 107 }
 108
 109 void
 110 check_sequence(Sequence *s)
 111 {       Element *e, *le = ZE;
 112         Lextok *n;
 113         int cnt = 0;
 114
 115         for (e = s->frst; e; le = e, e = e->nxt)
 116         {       n = e->n;
 117                 if (is_skip(n) && !has_lab(e, 0))
 118                 {       cnt++;
 119                         if (cnt > 1
 120                         &&  n->ntyp != PRINT
 121                         &&  n->ntyp != PRINTM)
 122                         {       if (verbose&32)
 123                                         printf("spin: %s:%d, redundant skip\n",
 124                                                 n->fn->name, n->ln);
 125                                 if (e != s->frst
 126                                 &&  e != s->last
 127                                 &&  e != s->extent)
 128                                 {       e->status |= DONE;      /* not unreachable */
 129                                         le->nxt = e->nxt;       /* remove it */
 130                                         e = le;
 131                                 }
 132                         }
 133                 } else
 134                         cnt = 0;
 135         }
 136 }
 137
 138 void
 139 prune_opts(Lextok *n)
 140 {       SeqList *l;
 141         extern Symbol *context;
 142         extern char *claimproc;
 143
 144         if (!n
 145         || (context && claimproc && strcmp(context->name, claimproc) == 0))
 146                 return;
 147
 148         for (l = n->sl; l; l = l->nxt)  /* find sequences of unlabeled skips */
 149                 check_sequence(l->this);
 150 }
 151
 152 Sequence *
 153 close_seq(int nottop)
 154 {       Sequence *s = cur_s->this;
 155         Symbol *z;
 156
 157         if (nottop == 0)        /* end of proctype body */
 158         {       initialization_ok = 1;
 159         }
 160
 161         if (nottop > 0 && s->frst && (z = has_lab(s->frst, 0)))
 162         {       printf("error: (%s:%d) label %s placed incorrectly\n",
 163                         (s->frst->n)?s->frst->n->fn->name:"-",
 164                         (s->frst->n)?s->frst->n->ln:0,
 165                         z->name);
 166                 switch (nottop) {
 167                 case 1:
 168                         printf("=====> stmnt unless Label: stmnt\n");
 169                         printf("sorry, cannot jump to the guard of an\n");
 170                         printf("escape (it is not a unique state)\n");
 171                         break;
 172                 case 2:
 173                         printf("=====> instead of  ");
 174                         printf("\"Label: stmnt unless stmnt\"\n");
 175                         printf("=====> always use  ");
 176                         printf("\"Label: { stmnt unless stmnt }\"\n");
 177                         break;
 178                 case 3:
 179                         printf("=====> instead of  ");
 180                         printf("\"atomic { Label: statement ... }\"\n");
 181                         printf("=====> always use  ");
 182                         printf("\"Label: atomic { statement ... }\"\n");
 183                         break;
 184                 case 4:
 185                         printf("=====> instead of  ");
 186                         printf("\"d_step { Label: statement ... }\"\n");
 187                         printf("=====> always use  ");
 188                         printf("\"Label: d_step { statement ... }\"\n");
 189                         break;
 190                 case 5:
 191                         printf("=====> instead of  ");
 192                         printf("\"{ Label: statement ... }\"\n");
 193                         printf("=====> always use  ");
 194                         printf("\"Label: { statement ... }\"\n");
 195                         break;
 196                 case 6:
 197                         printf("=====> instead of\n");
 198                         printf("        do (or if)\n");
 199                         printf("        :: ...\n");
 200                         printf("        :: Label: statement\n");
 201                         printf("        od (of fi)\n");
 202                         printf("=====> use\n");
 203                         printf("Label:  do (or if)\n");
 204                         printf("        :: ...\n");
 205                         printf("        :: statement\n");
 206                         printf("        od (or fi)\n");
 207                         break;
 208                 case 7:
 209                         printf("cannot happen - labels\n");
 210                         break;
 211                 }
 212                 if (nottop != 6)
 213                 {       alldone(1);
 214         }       }
 215
 216         if (nottop == 4
 217         && !Rjumpslocal(s->frst, s->last))
 218                 fatal("non_local jump in d_step sequence", (char *) 0);
 219
 220         cur_s = cur_s->nxt;
 221         s->maxel = Elcnt;
 222         s->extent = s->last;
 223         if (!s->last)
 224                 fatal("sequence must have at least one statement", (char *) 0);
 225         return s;
 226 }
 227
 228 Lextok *
 229 do_unless(Lextok *No, Lextok *Es)
 230 {       SeqList *Sl;
 231         Lextok *Re = nn(ZN, UNLESS, ZN, ZN);
 232
 233         Re->ln = No->ln;
 234         Re->fn = No->fn;
 235         has_unless++;
 236
 237         if (Es->ntyp == NON_ATOMIC)
 238         {       Sl = Es->sl;
 239         } else
 240         {       open_seq(0); add_seq(Es);
 241                 Sl = seqlist(close_seq(1), 0);
 242         }
 243
 244         if (No->ntyp == NON_ATOMIC)
 245         {       No->sl->nxt = Sl;
 246                 Sl = No->sl;
 247         } else  if (No->ntyp == ':'
 248                 && (No->lft->ntyp == NON_ATOMIC
 249                 ||  No->lft->ntyp == ATOMIC
 250                 ||  No->lft->ntyp == D_STEP))
 251         {
 252                 int tok = No->lft->ntyp;
 253
 254                 No->lft->sl->nxt = Sl;
 255                 Re->sl = No->lft->sl;
 256
 257                 open_seq(0); add_seq(Re);
 258                 Re = nn(ZN, tok, ZN, ZN);
 259                 Re->sl = seqlist(close_seq(7), 0);
 260                 Re->ln = No->ln;
 261                 Re->fn = No->fn;
 262
 263                 Re = nn(No, ':', Re, ZN);       /* lift label */
 264                 Re->ln = No->ln;
 265                 Re->fn = No->fn;
 266                 return Re;
 267         } else
 268         {       open_seq(0); add_seq(No);
 269                 Sl = seqlist(close_seq(2), Sl);
 270         }
 271
 272         Re->sl = Sl;
 273         return Re;
 274 }
 275
 276 SeqList *
 277 seqlist(Sequence *s, SeqList *r)
 278 {       SeqList *t = (SeqList *) emalloc(sizeof(SeqList));
 279
 280         t->this = s;
 281         t->nxt = r;
 282         return t;
 283 }
 284
 285 static Element *
 286 new_el(Lextok *n)
 287 {       Element *m;
 288
 289         if (n)
 290         {       if (n->ntyp == IF || n->ntyp == DO)
 291                         return if_seq(n);
 292                 if (n->ntyp == UNLESS)
 293                         return unless_seq(n);
 294         }
 295         m = (Element *) emalloc(sizeof(Element));
 296         m->n = n;
 297         m->seqno = Elcnt++;
 298         m->Seqno = Unique++;
 299         m->Nxt = Al_El; Al_El = m;
 300         return m;
 301 }
 302
 303 static int
 304 has_chanref(Lextok *n)
 305 {
 306         if (!n) return 0;
 307
 308         switch (n->ntyp) {
 309         case 's':       case 'r':
 310 #if 0
 311         case 'R':       case LEN:
 312 #endif
 313         case FULL:      case NFULL:
 314         case EMPTY:     case NEMPTY:
 315                 return 1;
 316         default:
 317                 break;
 318         }
 319         if (has_chanref(n->lft))
 320                 return 1;
 321
 322         return has_chanref(n->rgt);
 323 }
 324
 325 void
 326 loose_ends(void)        /* properly tie-up ends of sub-sequences */
 327 {       Element *e, *f;
 328
 329         for (e = Al_El; e; e = e->Nxt)
 330         {       if (!e->n
 331                 ||  !e->nxt)
 332                         continue;
 333                 switch (e->n->ntyp) {
 334                 case ATOMIC:
 335                 case NON_ATOMIC:
 336                 case D_STEP:
 337                         f = e->nxt;
 338                         while (f && f->n->ntyp == '.')
 339                                 f = f->nxt;
 340                         if (0) printf("link %d, {%d .. %d} -> %d (ntyp=%d) was %d\n",
 341                                 e->seqno,
 342                                 e->n->sl->this->frst->seqno,
 343                                 e->n->sl->this->last->seqno,
 344                                 f?f->seqno:-1, f?f->n->ntyp:-1,
 345                                 e->n->sl->this->last->nxt?e->n->sl->this->last->nxt->seqno:-1);
 346                         if (!e->n->sl->this->last->nxt)
 347                                 e->n->sl->this->last->nxt = f;
 348                         else
 349                         {       if (e->n->sl->this->last->nxt->n->ntyp != GOTO)
 350                                 {       if (!f || e->n->sl->this->last->nxt->seqno != f->seqno)
 351                                         non_fatal("unexpected: loose ends", (char *)0);
 352                                 } else
 353                                         e->n->sl->this->last = e->n->sl->this->last->nxt;
 354                                 /*
 355                                  * fix_dest can push a goto into the nxt position
 356                                  * in that case the goto wins and f is not needed
 357                                  * but the last fields needs adjusting
 358                                  */
 359                         }
 360                         break;
 361         }       }
 362 }
 363
 364 void
 365 popbreak(void)
 366 {
 367         if (!breakstack)
 368                 fatal("cannot happen, breakstack", (char *) 0);
 369
 370         breakstack = breakstack->nxt;   /* pop stack */
 371 }
 372
 373 static Lbreak *ob = (Lbreak *) 0;
 374
 375 void
 376 safe_break(void)
 377 {
 378         ob = breakstack;
 379         popbreak();
 380 }
 381
 382 void
 383 restore_break(void)
 384 {
 385         breakstack = ob;
 386         ob = (Lbreak *) 0;
 387 }
 388
 389 static Element *
 390 if_seq(Lextok *n)
 391 {       int     tok = n->ntyp;
 392         SeqList *s  = n->sl;
 393         Element *e  = new_el(ZN);
 394         Element *t  = new_el(nn(ZN,'.',ZN,ZN)); /* target */
 395         SeqList *z, *prev_z = (SeqList *) 0;
 396         SeqList *move_else  = (SeqList *) 0;    /* to end of optionlist */
 397         int     ref_chans = 0;
 398
 399         for (z = s; z; z = z->nxt)
 400         {       if (!z->this->frst)
 401                         continue;
 402                 if (z->this->frst->n->ntyp == ELSE)
 403                 {       if (move_else)
 404                                 fatal("duplicate `else'", (char *) 0);
 405                         if (z->nxt)     /* is not already at the end */
 406                         {       move_else = z;
 407                                 if (prev_z)
 408                                         prev_z->nxt = z->nxt;
 409                                 else
 410                                         s = n->sl = z->nxt;
 411                                 continue;
 412                         }
 413                 } else
 414                         ref_chans |= has_chanref(z->this->frst->n);
 415                 prev_z = z;
 416         }
 417         if (move_else)
 418         {       move_else->nxt = (SeqList *) 0;
 419                 /* if there is no prev, then else was at the end */
 420                 if (!prev_z) fatal("cannot happen - if_seq", (char *) 0);
 421                 prev_z->nxt = move_else;
 422                 prev_z = move_else;
 423         }
 424         if (prev_z
 425         &&  ref_chans
 426         &&  prev_z->this->frst->n->ntyp == ELSE)
 427         {       prev_z->this->frst->n->val = 1;
 428                 has_badelse++;
 429                 if (has_xu)
 430                 {       fatal("invalid use of 'else' combined with i/o and xr/xs assertions,",
 431                                 (char *)0);
 432                 } else
 433                 {       non_fatal("dubious use of 'else' combined with i/o,",
 434                                 (char *)0);
 435                 }
 436                 nr_errs--;
 437         }
 438
 439         e->n = nn(n, tok, ZN, ZN);
 440         e->n->sl = s;                   /* preserve as info only */
 441         e->sub = s;
 442         for (z = s; z; z = z->nxt)
 443                 add_el(t, z->this);     /* append target */
 444         if (tok == DO)
 445         {       add_el(t, cur_s->this); /* target upfront */
 446                 t = new_el(nn(n, BREAK, ZN, ZN)); /* break target */
 447                 set_lab(break_dest(), t);       /* new exit  */
 448                 popbreak();
 449         }
 450         add_el(e, cur_s->this);
 451         add_el(t, cur_s->this);
 452         return e;                       /* destination node for label */
 453 }
 454
 455 static void
 456 escape_el(Element *f, Sequence *e)
 457 {       SeqList *z;
 458
 459         for (z = f->esc; z; z = z->nxt)
 460                 if (z->this == e)
 461                         return; /* already there */
 462
 463         /* cover the lower-level escapes of this state */
 464         for (z = f->esc; z; z = z->nxt)
 465                 attach_escape(z->this, e);
 466
 467         /* now attach escape to the state itself */
 468
 469         f->esc = seqlist(e, f->esc);    /* in lifo order... */
 470 #ifdef DEBUG
 471         printf("attach %d (", e->frst->Seqno);
 472         comment(stdout, e->frst->n, 0);
 473         printf(")       to %d (", f->Seqno);
 474         comment(stdout, f->n, 0);
 475         printf(")\n");
 476 #endif
 477         switch (f->n->ntyp) {
 478         case UNLESS:
 479                 attach_escape(f->sub->this, e);
 480                 break;
 481         case IF:
 482         case DO:
 483                 for (z = f->sub; z; z = z->nxt)
 484                         attach_escape(z->this, e);
 485                 break;
 486         case D_STEP:
 487                 /* attach only to the guard stmnt */
 488                 escape_el(f->n->sl->this->frst, e);
 489                 break;
 490         case ATOMIC:
 491         case NON_ATOMIC:
 492                 /* attach to all stmnts */
 493                 attach_escape(f->n->sl->this, e);
 494                 break;
 495         }
 496 }
 497
 498 static void
 499 attach_escape(Sequence *n, Sequence *e)
 500 {       Element *f;
 501
 502         for (f = n->frst; f; f = f->nxt)
 503         {       escape_el(f, e);
 504                 if (f == n->extent)
 505                         break;
 506         }
 507 }
 508
 509 static Element *
 510 unless_seq(Lextok *n)
 511 {       SeqList *s  = n->sl;
 512         Element *e  = new_el(ZN);
 513         Element *t  = new_el(nn(ZN,'.',ZN,ZN)); /* target */
 514         SeqList *z;
 515
 516         e->n = nn(n, UNLESS, ZN, ZN);
 517         e->n->sl = s;                   /* info only */
 518         e->sub = s;
 519
 520         /* need 2 sequences: normal execution and escape */
 521         if (!s || !s->nxt || s->nxt->nxt)
 522                 fatal("unexpected unless structure", (char *)0);
 523
 524         /* append the target state to both */
 525         for (z = s; z; z = z->nxt)
 526                 add_el(t, z->this);
 527
 528         /* attach escapes to all states in normal sequence */
 529         attach_escape(s->this, s->nxt->this);
 530
 531         add_el(e, cur_s->this);
 532         add_el(t, cur_s->this);
 533 #ifdef DEBUG
 534         printf("unless element (%d,%d):\n", e->Seqno, t->Seqno);
 535         for (z = s; z; z = z->nxt)
 536         {       Element *x; printf("\t%d,%d,%d :: ",
 537                 z->this->frst->Seqno,
 538                 z->this->extent->Seqno,
 539                 z->this->last->Seqno);
 540                 for (x = z->this->frst; x; x = x->nxt)
 541                         printf("(%d)", x->Seqno);
 542                 printf("\n");
 543         }
 544 #endif
 545         return e;
 546 }
 547
 548 Element *
 549 mk_skip(void)
 550 {       Lextok  *t = nn(ZN, CONST, ZN, ZN);
 551         t->val = 1;
 552         return new_el(nn(ZN, 'c', t, ZN));
 553 }
 554
 555 static void
 556 add_el(Element *e, Sequence *s)
 557 {
 558         if (e->n->ntyp == GOTO)
 559         {       Symbol *z = has_lab(e, (1|2|4));
 560                 if (z)
 561                 {       Element *y; /* insert a skip */
 562                         y = mk_skip();
 563                         mov_lab(z, e, y); /* inherit label */
 564                         add_el(y, s);
 565         }       }
 566 #ifdef DEBUG
 567         printf("add_el %d after %d -- ",
 568         e->Seqno, (s->last)?s->last->Seqno:-1);
 569         comment(stdout, e->n, 0);
 570         printf("\n");
 571 #endif
 572         if (!s->frst)
 573                 s->frst = e;
 574         else
 575                 s->last->nxt = e;
 576         s->last = e;
 577 }
 578
 579 static Element *
 580 colons(Lextok *n)
 581 {
 582         if (!n)
 583                 return ZE;
 584         if (n->ntyp == ':')
 585         {       Element *e = colons(n->lft);
 586                 set_lab(n->sym, e);
 587                 return e;
 588         }
 589         innermost = n;
 590         return new_el(n);
 591 }
 592
 593 void
 594 add_seq(Lextok *n)
 595 {       Element *e;
 596
 597         if (!n) return;
 598         innermost = n;
 599         e = colons(n);
 600         if (innermost->ntyp != IF
 601         &&  innermost->ntyp != DO
 602         &&  innermost->ntyp != UNLESS)
 603                 add_el(e, cur_s->this);
 604 }
 605
 606 void
 607 set_lab(Symbol *s, Element *e)
 608 {       Label *l; extern Symbol *context;
 609         int cur_uiid = is_inline();
 610
 611         if (!s) return;
 612
 613         for (l = labtab; l; l = l->nxt)
 614         {       if (strcmp(l->s->name, s->name) == 0
 615                 &&  l->c == context
 616                 &&  (old_scope_rules || strcmp((const char *) s->bscp, (const char *) l->s->bscp) == 0)
 617                 &&  l->uiid == cur_uiid)
 618                 {       non_fatal("label %s redeclared", s->name);
 619                         break;
 620         }       }
 621
 622         if (strncmp(s->name, "accept", 6) == 0
 623         &&  strncmp(s->name, "accept_all", 10) != 0)
 624         {       has_accept = 1;
 625         }
 626
 627         l = (Label *) emalloc(sizeof(Label));
 628         l->s = s;
 629         l->c = context;
 630         l->e = e;
 631         l->uiid = cur_uiid;
 632         l->nxt = labtab;
 633         labtab = l;
 634 }
 635
 636 static Label *
 637 get_labspec(Lextok *n)
 638 {       Symbol *s = n->sym;
 639         Label  *l, *anymatch = (Label *) 0;
 640         int ln;
 641         /*
 642          * try to find a label with the same inline id (uiid)
 643          * but if it doesn't exist, return any other match
 644          * within the same scope
 645          */
 646         for (l = labtab; l; l = l->nxt)
 647         {       if (strcmp(l->s->name, s->name) == 0    /* labelname matches */
 648                 &&  s->context == l->s->context)        /* same scope */
 649                 {
 650 #if 0
 651                         if (anymatch && n->uiid == anymatch->uiid)
 652                         {       if (0) non_fatal("label %s re-declared", s->name);
 653                         }
 654                         if (0)
 655                         {       printf("Label %s uiid now::then %d :: %d bcsp %s :: %s\n",
 656                                         s->name, n->uiid, l->uiid, s->bscp, l->s->bscp);
 657                                 printf("get_labspec match on %s %s (bscp goto %s - label %s)\n",
 658                                         s->name, s->context->name,  s->bscp, l->s->bscp);
 659                         }
 660 #endif
 661                         /* same block scope */
 662                         if (strcmp((const char *) s->bscp, (const char *) l->s->bscp) == 0)
 663                         {       return l;       /* definite match */
 664                         }
 665                         /* higher block scope */
 666                         ln = strlen((const char *) l->s->bscp);
 667                         if (strncmp((const char *) s->bscp, (const char *) l->s->bscp, ln) == 0)
 668                         {       anymatch = l;   /* possible match */
 669                         } else if (!anymatch)
 670                         {       anymatch = l;   /* somewhere else in same context */
 671         }       }       }
 672
 673         return anymatch; /* return best match */
 674 }
 675
 676 Element *
 677 get_lab(Lextok *n, int md)
 678 {       Label *l = get_labspec(n);
 679
 680         if (l != (Label *) 0)
 681         {       return (l->e);
 682         }
 683
 684         if (md)
 685         {       lineno = n->ln;
 686                 Fname  = n->fn;
 687                 fatal("undefined label %s", n->sym->name);
 688         }
 689         return ZE;
 690 }
 691
 692 Symbol *
 693 has_lab(Element *e, int special)
 694 {       Label *l;
 695
 696         for (l = labtab; l; l = l->nxt)
 697         {       if (e != l->e)
 698                         continue;
 699                 if (special == 0
 700                 ||  ((special&1) && !strncmp(l->s->name, "accept", 6))
 701                 ||  ((special&2) && !strncmp(l->s->name, "end", 3))
 702                 ||  ((special&4) && !strncmp(l->s->name, "progress", 8)))
 703                         return (l->s);
 704         }
 705         return ZS;
 706 }
 707
 708 static void
 709 mov_lab(Symbol *z, Element *e, Element *y)
 710 {       Label *l;
 711
 712         for (l = labtab; l; l = l->nxt)
 713                 if (e == l->e)
 714                 {       l->e = y;
 715                         return;
 716                 }
 717         if (e->n)
 718         {       lineno = e->n->ln;
 719                 Fname  = e->n->fn;
 720         }
 721         fatal("cannot happen - mov_lab %s", z->name);
 722 }
 723
 724 void
 725 fix_dest(Symbol *c, Symbol *a)          /* c:label name, a:proctype name */
 726 {       Label *l; extern Symbol *context;
 727
 728 #if 0
 729         printf("ref to label '%s' in proctype '%s', search:\n",
 730                 c->name, a->name);
 731         for (l = labtab; l; l = l->nxt)
 732                 printf("        %s in   %s\n", l->s->name, l->c->name);
 733 #endif
 734
 735         for (l = labtab; l; l = l->nxt)
 736         {       if (strcmp(c->name, l->s->name) == 0
 737                 &&  strcmp(a->name, l->c->name) == 0)   /* ? */
 738                         break;
 739         }
 740         if (!l)
 741         {       printf("spin: label '%s' (proctype %s)\n", c->name, a->name);
 742                 non_fatal("unknown label '%s'", c->name);
 743                 if (context == a)
 744                 printf("spin: cannot remote ref a label inside the same proctype\n");
 745                 return;
 746         }
 747         if (!l->e || !l->e->n)
 748                 fatal("fix_dest error (%s)", c->name);
 749         if (l->e->n->ntyp == GOTO)
 750         {       Element *y = (Element *) emalloc(sizeof(Element));
 751                 int     keep_ln = l->e->n->ln;
 752                 Symbol  *keep_fn = l->e->n->fn;
 753
 754                 /* insert skip - or target is optimized away */
 755                 y->n = l->e->n;           /* copy of the goto   */
 756                 y->seqno = find_maxel(a); /* unique seqno within proc */
 757                 y->nxt = l->e->nxt;
 758                 y->Seqno = Unique++; y->Nxt = Al_El; Al_El = y;
 759
 760                 /* turn the original element+seqno into a skip */
 761                 l->e->n = nn(ZN, 'c', nn(ZN, CONST, ZN, ZN), ZN);
 762                 l->e->n->ln = l->e->n->lft->ln = keep_ln;
 763                 l->e->n->fn = l->e->n->lft->fn = keep_fn;
 764                 l->e->n->lft->val = 1;
 765                 l->e->nxt = y;          /* append the goto  */
 766         }
 767         l->e->status |= CHECK2; /* treat as if global */
 768         if (l->e->status & (ATOM | L_ATOM | D_ATOM))
 769         {       printf("spin: %s:%d, warning, reference to label ",
 770                         Fname->name, lineno);
 771                 printf("from inside atomic or d_step (%s)\n", c->name);
 772         }
 773 }
 774
 775 int
 776 find_lab(Symbol *s, Symbol *c, int markit)
 777 {       Label *l, *pm = (Label *) 0, *apm = (Label *) 0;
 778         int ln;
 779
 780         /* generally called for remote references in never claims */
 781         for (l = labtab; l; l = l->nxt)
 782         {
 783                 if (strcmp(s->name, l->s->name) == 0
 784                 &&  strcmp(c->name, l->c->name) == 0)
 785                 {       ln = strlen((const char *) l->s->bscp);
 786                         if (0)
 787                         {       printf("want '%s' in context '%s', scope ref '%s' - label '%s'\n",
 788                                         s->name, c->name, s->bscp, l->s->bscp);
 789                         }
 790                         /* same or higher block scope */
 791                         if (strcmp((const char *)  s->bscp, (const char *) l->s->bscp) == 0)
 792                         {       pm = l; /* definite match */
 793                                 break;
 794                         }
 795                         if (strncmp((const char *) s->bscp, (const char *) l->s->bscp, ln) == 0)
 796                         {       pm = l; /* possible match */
 797                         } else
 798                         {       apm = l;        /* remote */
 799         }       }       }
 800
 801         if (pm)
 802         {       pm->visible |= markit;
 803                 return pm->e->seqno;
 804         }
 805         if (apm)
 806         {       apm->visible |= markit;
 807                 return apm->e->seqno;
 808         } /* else printf("Not Found\n"); */
 809         return 0;
 810 }
 811
 812 void
 813 pushbreak(void)
 814 {       Lbreak *r = (Lbreak *) emalloc(sizeof(Lbreak));
 815         Symbol *l;
 816         char buf[64];
 817
 818         sprintf(buf, ":b%d", break_id++);
 819         l = lookup(buf);
 820         r->l = l;
 821         r->nxt = breakstack;
 822         breakstack = r;
 823 }
 824
 825 Symbol *
 826 break_dest(void)
 827 {
 828         if (!breakstack)
 829                 fatal("misplaced break statement", (char *)0);
 830         return breakstack->l;
 831 }
 832
 833 void
 834 make_atomic(Sequence *s, int added)
 835 {       Element *f;
 836
 837         walk_atomic(s->frst, s->last, added);
 838
 839         f = s->last;
 840         switch (f->n->ntyp) {   /* is last step basic stmnt or sequence ? */
 841         case NON_ATOMIC:
 842         case ATOMIC:
 843                 /* redo and search for the last step of that sequence */
 844                 make_atomic(f->n->sl->this, added);
 845                 break;
 846
 847         case UNLESS:
 848                 /* escapes are folded into main sequence */
 849                 make_atomic(f->sub->this, added);
 850                 break;
 851
 852         default:
 853                 f->status &= ~ATOM;
 854                 f->status |= L_ATOM;
 855                 break;
 856         }
 857 }
 858
 859 #if 0
 860 static int depth = 0;
 861 void dump_sym(Symbol *, char *);
 862
 863 void
 864 dump_lex(Lextok *t, char *s)
 865 {       int i;
 866
 867         depth++;
 868         printf(s);
 869         for (i = 0; i < depth; i++)
 870                 printf("\t");
 871         explain(t->ntyp);
 872         if (t->ntyp == NAME) printf(" %s ", t->sym->name);
 873         if (t->ntyp == CONST) printf(" %d ", t->val);
 874         if (t->ntyp == STRUCT)
 875         {       dump_sym(t->sym, "\n:Z:");
 876         }
 877         if (t->lft)
 878         {       dump_lex(t->lft, "\nL");
 879         }
 880         if (t->rgt)
 881         {       dump_lex(t->rgt, "\nR");
 882         }
 883         depth--;
 884 }
 885 void
 886 dump_sym(Symbol *z, char *s)
 887 {       int i;
 888         char txt[64];
 889         depth++;
 890         printf(s);
 891         for (i = 0; i < depth; i++)
 892                 printf("\t");
 893
 894         if (z->type == CHAN)
 895         {       if (z->ini && z->ini->rgt && z->ini->rgt->sym)
 896                 {       /* dump_sym(z->ini->rgt->sym, "\n:I:"); -- could also be longer list */
 897                         if (z->ini->rgt->rgt
 898                         || !z->ini->rgt->sym)
 899                         fatal("chan %s in for should have only one field (a typedef)", z->name);
 900                         printf(" -- %s %p -- ", z->ini->rgt->sym->name, z->ini->rgt->sym);
 901                 }
 902         } else if (z->type == STRUCT)
 903         {       if (z->Snm)
 904                         printf(" == %s %p == ", z->Snm->name, z->Snm);
 905                 else
 906                 {       if (z->Slst)
 907                                 dump_lex(z->Slst, "\n:X:");
 908                         if (z->ini)
 909                                 dump_lex(z->ini, "\n:I:");
 910                 }
 911         }
 912         depth--;
 913
 914 }
 915 #endif
 916
 917 int
 918 match_struct(Symbol *s, Symbol *t)
 919 {
 920         if (!t
 921         ||  !t->ini
 922         ||  !t->ini->rgt
 923         ||  !t->ini->rgt->sym
 924         ||   t->ini->rgt->rgt)
 925         {       fatal("chan %s in for should have only one field (a typedef)", t?t->name:"--");
 926         }
 927         /* we already know that s is a STRUCT */
 928         if (0)
 929         {       printf("index type %s %p ==\n", s->Snm->name, s->Snm);
 930                 printf("chan type  %s %p --\n\n", t->ini->rgt->sym->name, t->ini->rgt->sym);
 931         }
 932
 933         return (s->Snm == t->ini->rgt->sym);
 934 }
 935
 936 void
 937 valid_name(Lextok *a3, Lextok *a5, Lextok *a8, char *tp)
 938 {
 939         if (a3->ntyp != NAME)
 940         {       fatal("%s ( .name : from .. to ) { ... }", tp);
 941         }
 942         if (a3->sym->type == CHAN
 943         ||  a3->sym->type == STRUCT
 944         ||  a3->sym->isarray != 0)
 945         {       fatal("bad index in for-construct %s", a3->sym->name);
 946         }
 947         if (a5->ntyp == CONST && a8->ntyp == CONST && a5->val > a8->val)
 948         {       non_fatal("start value for %s exceeds end-value", a3->sym->name);
 949         }
 950 }
 951
 952 void
 953 for_setup(Lextok *a3, Lextok *a5, Lextok *a8)
 954 {       /* for ( a3 : a5 .. a8 ) */
 955
 956         valid_name(a3, a5, a8, "for");
 957         /* a5->ntyp = a8->ntyp = CONST; */
 958         add_seq(nn(a3, ASGN, a3, a5));  /* start value */
 959         open_seq(0);
 960         add_seq(nn(ZN, 'c', nn(a3, LE, a3, a8), ZN));   /* condition */
 961 }
 962
 963 Lextok *
 964 for_index(Lextok *a3, Lextok *a5)
 965 {       Lextok *z0, *z1, *z2, *z3;
 966         Symbol *tmp_cnt;
 967         char tmp_nm[MAXSCOPESZ+16];
 968         /* for ( a3 in a5 ) { ... } */
 969
 970         if (a3->ntyp != NAME)
 971         {       fatal("for ( .name in name ) { ... }", (char *) 0);
 972         }
 973
 974         if (a5->ntyp != NAME)
 975         {       fatal("for ( %s in .name ) { ... }", a3->sym->name);
 976         }
 977
 978         if (a3->sym->type == STRUCT)
 979         {       if (a5->sym->type != CHAN)
 980                 {       fatal("for ( %s in .channel_name ) { ... }",
 981                                 a3->sym->name);
 982                 }
 983                 z0 = a5->sym->ini;
 984                 if (!z0
 985                 || z0->val <= 0
 986                 || z0->rgt->ntyp != STRUCT
 987                 || z0->rgt->rgt != NULL)
 988                 {       fatal("bad channel type %s in for", a5->sym->name);
 989                 }
 990
 991                 if (!match_struct(a3->sym, a5->sym))
 992                 {       fatal("type of %s does not match chan", a3->sym->name);
 993                 }
 994
 995                 z1 = nn(ZN, CONST, ZN, ZN); z1->val = 0;
 996                 z2 = nn(a5, LEN, a5, ZN);
 997
 998                 sprintf(tmp_nm, "_f0r_t3mp%s", CurScope); /* make sure it's unique */
 999                 tmp_cnt = lookup(tmp_nm);
1000                 if (z0->val > 255)                      /* check nr of slots, i.e. max length */
1001                 {       tmp_cnt->type = SHORT;  /* should be rare */
1002                 } else
1003                 {       tmp_cnt->type = BYTE;
1004                 }
1005                 z3 = nn(ZN, NAME, ZN, ZN);
1006                 z3->sym = tmp_cnt;
1007
1008                 add_seq(nn(z3, ASGN, z3, z1));  /* start value 0 */
1009
1010                 open_seq(0);
1011
1012                 add_seq(nn(ZN, 'c', nn(z3, LT, z3, z2), ZN));   /* condition */
1013
1014                 /* retrieve  message from the right slot -- for now: rotate contents */
1015                 in_for = 0;
1016                 add_seq(nn(a5, 'r', a5, expand(a3, 1)));        /* receive */
1017                 add_seq(nn(a5, 's', a5, expand(a3, 1)));        /* put back in to rotate */
1018                 in_for = 1;
1019                 return z3;
1020         } else
1021         {       if (a5->sym->isarray == 0
1022                 ||  a5->sym->nel <= 0)
1023                 {       fatal("bad arrayname %s", a5->sym->name);
1024                 }
1025                 z1 = nn(ZN, CONST, ZN, ZN); z1->val = 0;
1026                 z2 = nn(ZN, CONST, ZN, ZN); z2->val = a5->sym->nel - 1;
1027                 for_setup(a3, z1, z2);
1028                 return a3;
1029         }
1030 }
1031
1032 Lextok *
1033 for_body(Lextok *a3, int with_else)
1034 {       Lextok *t1, *t2, *t0, *rv;
1035
1036         rv = nn(ZN, CONST, ZN, ZN); rv->val = 1;
1037         rv = nn(ZN,  '+', a3, rv);
1038         rv = nn(a3, ASGN, a3, rv);
1039         add_seq(rv);    /* initial increment */
1040
1041         /* completed loop body, main sequence */
1042         t1 = nn(ZN, 0, ZN, ZN);
1043         t1->sq = close_seq(8);
1044
1045         open_seq(0);            /* add else -> break sequence */
1046         if (with_else)
1047         {       add_seq(nn(ZN, ELSE, ZN, ZN));
1048         }
1049         t2 = nn(ZN, GOTO, ZN, ZN);
1050         t2->sym = break_dest();
1051         add_seq(t2);
1052         t2 = nn(ZN, 0, ZN, ZN);
1053         t2->sq = close_seq(9);
1054
1055         t0 = nn(ZN, 0, ZN, ZN);
1056         t0->sl = seqlist(t2->sq, seqlist(t1->sq, 0));
1057
1058         rv = nn(ZN, DO, ZN, ZN);
1059         rv->sl = t0->sl;
1060
1061         return rv;
1062 }
1063
1064 Lextok *
1065 sel_index(Lextok *a3, Lextok *a5, Lextok *a7)
1066 {       /* select ( a3 : a5 .. a7 ) */
1067
1068         valid_name(a3, a5, a7, "select");
1069         /* a5->ntyp = a7->ntyp = CONST; */
1070
1071         add_seq(nn(a3, ASGN, a3, a5));  /* start value */
1072         open_seq(0);
1073         add_seq(nn(ZN, 'c', nn(a3, LT, a3, a7), ZN));   /* condition */
1074
1075         pushbreak(); /* new 6.2.1 */
1076         return for_body(a3, 0); /* no else, just a non-deterministic break */
1077 }
1078
1079 static void
1080 walk_atomic(Element *a, Element *b, int added)
1081 {       Element *f; Symbol *ofn; int oln;
1082         SeqList *h;
1083
1084         ofn = Fname;
1085         oln = lineno;
1086         for (f = a; ; f = f->nxt)
1087         {       f->status |= (ATOM|added);
1088                 switch (f->n->ntyp) {
1089                 case ATOMIC:
1090                         if (verbose&32)
1091                           printf("spin: %s:%d, warning, atomic inside %s (ignored)\n",
1092                           f->n->fn->name, f->n->ln, (added)?"d_step":"atomic");
1093                         goto mknonat;
1094                 case D_STEP:
1095                         if (!(verbose&32))
1096                         {       if (added) goto mknonat;
1097                                 break;
1098                         }
1099                         printf("spin: %s:%d, warning, d_step inside ",
1100                          f->n->fn->name, f->n->ln);
1101                         if (added)
1102                         {       printf("d_step (ignored)\n");
1103                                 goto mknonat;
1104                         }
1105                         printf("atomic\n");
1106                         break;
1107                 case NON_ATOMIC:
1108 mknonat:                f->n->ntyp = NON_ATOMIC; /* can jump here */
1109                         h = f->n->sl;
1110                         walk_atomic(h->this->frst, h->this->last, added);
1111                         break;
1112                 case UNLESS:
1113                         if (added)
1114                         { printf("spin: error, %s:%d, unless in d_step (ignored)\n",
1115                                  f->n->fn->name, f->n->ln);
1116                         }
1117                 }
1118                 for (h = f->sub; h; h = h->nxt)
1119                         walk_atomic(h->this->frst, h->this->last, added);
1120                 if (f == b)
1121                         break;
1122         }
1123         Fname = ofn;
1124         lineno = oln;
1125 }
1126
1127 void
1128 dumplabels(void)
1129 {       Label *l;
1130
1131         for (l = labtab; l; l = l->nxt)
1132                 if (l->c != 0 && l->s->name[0] != ':')
1133                 {       printf("label   %s      %d      ",
1134                                 l->s->name, l->e->seqno);
1135                         if (l->uiid == 0)
1136                                 printf("<%s>", l->c->name);
1137                         else
1138                                 printf("<%s i%d>", l->c->name, l->uiid);
1139                         if (!old_scope_rules)
1140                         {       printf("\t{scope %s}", l->s->bscp);
1141                         }
1142                         printf("\n");
1143                 }
1144 }