123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384858687888990919293949596979899100101102103104105106107108109110111112113114115116117118119120121122123124125126127128129130131132133134135136137138139140141142143144145146147148149150151152153154155156157158159160161162163164165166167168169170171172173174175176177178179180181182183184185186187188189190191192193194195196197198199200201202203204205206207208209210211212213214215216217218219220221222223224225226227228229230231232233234235236237238239240241242243244245246247248249250251252253254255256257258259260261262263264265266267268269270271272273274275276277278279280281282283284285286287288289290291292293294295296297298299300301302303304305306307308309310311312313314315316317318319320321322323324325326327328329330331332333334335336337338339340341342343344345346347348349350351352353354355356357358359360361362363364365366367368369370371372373374375376377378379380381382383384385386387388389390391392393394395396397398399400401402403404405406407408409410411412413414415416417418419420421422423424425426427428429430431432433434435436437438439440441442443444445446447448449450451452453454455456457458459460461462463464465466467468469470471472473474475476477478479480481482483484485486487488489490491492493494495496497498499500501502503504505506507508509510511512513514515516517518519520521522523524525526527528529530531532533534535536537538539540541542543544545546547548549550551552553554555556557558559560561562563564565566567568569570571572573574575576577578579580581582583584585586587588589590591592593594595596597598599600601602603604605606607608609610611612613614615616617618619620621622623624625626627628629630631632633634635636637638639640641642643644645646647648649650651652653654655656657658659660661662663664665666 |
- /***** tl_spin: tl_buchi.c *****/
- /* Copyright (c) 1995-2003 by Lucent Technologies, Bell Laboratories. */
- /* All Rights Reserved. This software is for educational purposes only. */
- /* No guarantee whatsoever is expressed or implied by the distribution of */
- /* this code. Permission is given to distribute this code provided that */
- /* this introductory message is not removed and no monies are exchanged. */
- /* Software written by Gerard J. Holzmann. For tool documentation see: */
- /* http://spinroot.com/ */
- /* Send all bug-reports and/or questions to: bugs@spinroot.com */
- /* Based on the translation algorithm by Gerth, Peled, Vardi, and Wolper, */
- /* presented at the PSTV Conference, held in 1995, Warsaw, Poland 1995. */
- #include "tl.h"
- extern int tl_verbose, tl_clutter, Total, Max_Red;
- FILE *tl_out; /* if standalone: = stdout; */
- typedef struct Transition {
- Symbol *name;
- Node *cond;
- int redundant, merged, marked;
- struct Transition *nxt;
- } Transition;
- typedef struct State {
- Symbol *name;
- Transition *trans;
- Graph *colors;
- unsigned char redundant;
- unsigned char accepting;
- unsigned char reachable;
- struct State *nxt;
- } State;
- static State *never = (State *) 0;
- static int hitsall;
- static int
- sametrans(Transition *s, Transition *t)
- {
- if (strcmp(s->name->name, t->name->name) != 0)
- return 0;
- return isequal(s->cond, t->cond);
- }
- static Node *
- Prune(Node *p)
- {
- if (p)
- switch (p->ntyp) {
- case PREDICATE:
- case NOT:
- case FALSE:
- case TRUE:
- #ifdef NXT
- case NEXT:
- #endif
- return p;
- case OR:
- p->lft = Prune(p->lft);
- if (!p->lft)
- { releasenode(1, p->rgt);
- return ZN;
- }
- p->rgt = Prune(p->rgt);
- if (!p->rgt)
- { releasenode(1, p->lft);
- return ZN;
- }
- return p;
- case AND:
- p->lft = Prune(p->lft);
- if (!p->lft)
- return Prune(p->rgt);
- p->rgt = Prune(p->rgt);
- if (!p->rgt)
- return p->lft;
- return p;
- }
- releasenode(1, p);
- return ZN;
- }
- static State *
- findstate(char *nm)
- { State *b;
- for (b = never; b; b = b->nxt)
- if (!strcmp(b->name->name, nm))
- return b;
- if (strcmp(nm, "accept_all"))
- { if (strncmp(nm, "accept", 6))
- { int i; char altnm[64];
- for (i = 0; i < 64; i++)
- if (nm[i] == '_')
- break;
- if (i >= 64)
- Fatal("name too long %s", nm);
- sprintf(altnm, "accept%s", &nm[i]);
- return findstate(altnm);
- }
- /* Fatal("buchi: no state %s", nm); */
- }
- return (State *) 0;
- }
- static void
- Dfs(State *b)
- { Transition *t;
- if (!b || b->reachable) return;
- b->reachable = 1;
- if (b->redundant)
- printf("/* redundant state %s */\n",
- b->name->name);
- for (t = b->trans; t; t = t->nxt)
- { if (!t->redundant)
- { Dfs(findstate(t->name->name));
- if (!hitsall
- && strcmp(t->name->name, "accept_all") == 0)
- hitsall = 1;
- }
- }
- }
- void
- retarget(char *from, char *to)
- { State *b;
- Transition *t;
- Symbol *To = tl_lookup(to);
- if (tl_verbose) printf("replace %s with %s\n", from, to);
- for (b = never; b; b = b->nxt)
- { if (!strcmp(b->name->name, from))
- b->redundant = 1;
- else
- for (t = b->trans; t; t = t->nxt)
- { if (!strcmp(t->name->name, from))
- t->name = To;
- } }
- }
- #ifdef NXT
- static Node *
- nonxt(Node *n)
- {
- switch (n->ntyp) {
- case U_OPER:
- case V_OPER:
- case NEXT:
- return ZN;
- case OR:
- n->lft = nonxt(n->lft);
- n->rgt = nonxt(n->rgt);
- if (!n->lft || !n->rgt)
- return True;
- return n;
- case AND:
- n->lft = nonxt(n->lft);
- n->rgt = nonxt(n->rgt);
- if (!n->lft)
- { if (!n->rgt)
- n = ZN;
- else
- n = n->rgt;
- } else if (!n->rgt)
- n = n->lft;
- return n;
- }
- return n;
- }
- #endif
- static Node *
- combination(Node *s, Node *t)
- { Node *nc;
- #ifdef NXT
- Node *a = nonxt(s);
- Node *b = nonxt(t);
- if (tl_verbose)
- { printf("\tnonxtA: "); dump(a);
- printf("\n\tnonxtB: "); dump(b);
- printf("\n");
- }
- /* if there's only a X(f), its equivalent to true */
- if (!a || !b)
- nc = True;
- else
- nc = tl_nn(OR, a, b);
- #else
- nc = tl_nn(OR, s, t);
- #endif
- if (tl_verbose)
- { printf("\tcombo: "); dump(nc);
- printf("\n");
- }
- return nc;
- }
- Node *
- unclutter(Node *n, char *snm)
- { Node *t, *s, *v, *u;
- Symbol *w;
- /* check only simple cases like !q && q */
- for (t = n; t; t = t->rgt)
- { if (t->rgt)
- { if (t->ntyp != AND || !t->lft)
- return n;
- if (t->lft->ntyp != PREDICATE
- #ifdef NXT
- && t->lft->ntyp != NEXT
- #endif
- && t->lft->ntyp != NOT)
- return n;
- } else
- { if (t->ntyp != PREDICATE
- #ifdef NXT
- && t->ntyp != NEXT
- #endif
- && t->ntyp != NOT)
- return n;
- }
- }
- for (t = n; t; t = t->rgt)
- { if (t->rgt)
- v = t->lft;
- else
- v = t;
- if (v->ntyp == NOT
- && v->lft->ntyp == PREDICATE)
- { w = v->lft->sym;
- for (s = n; s; s = s->rgt)
- { if (s == t) continue;
- if (s->rgt)
- u = s->lft;
- else
- u = s;
- if (u->ntyp == PREDICATE
- && strcmp(u->sym->name, w->name) == 0)
- { if (tl_verbose)
- { printf("BINGO %s:\t", snm);
- dump(n);
- printf("\n");
- }
- return False;
- }
- }
- } }
- return n;
- }
- static void
- clutter(void)
- { State *p;
- Transition *s;
- for (p = never; p; p = p->nxt)
- for (s = p->trans; s; s = s->nxt)
- { s->cond = unclutter(s->cond, p->name->name);
- if (s->cond
- && s->cond->ntyp == FALSE)
- { if (s != p->trans
- || s->nxt)
- s->redundant = 1;
- }
- }
- }
- static void
- showtrans(State *a)
- { Transition *s;
- for (s = a->trans; s; s = s->nxt)
- { printf("%s ", s->name?s->name->name:"-");
- dump(s->cond);
- printf(" %d %d %d\n", s->redundant, s->merged, s->marked);
- }
- }
- static int
- mergetrans(void)
- { State *b;
- Transition *s, *t;
- Node *nc; int cnt = 0;
- for (b = never; b; b = b->nxt)
- { if (!b->reachable) continue;
- for (s = b->trans; s; s = s->nxt)
- { if (s->redundant) continue;
- for (t = s->nxt; t; t = t->nxt)
- if (!t->redundant
- && !strcmp(s->name->name, t->name->name))
- { if (tl_verbose)
- { printf("===\nstate %s, trans to %s redundant\n",
- b->name->name, s->name->name);
- showtrans(b);
- printf(" conditions ");
- dump(s->cond); printf(" <-> ");
- dump(t->cond); printf("\n");
- }
- if (!s->cond) /* same as T */
- { releasenode(1, t->cond); /* T or t */
- nc = True;
- } else if (!t->cond)
- { releasenode(1, s->cond);
- nc = True;
- } else
- { nc = combination(s->cond, t->cond);
- }
- t->cond = rewrite(nc);
- t->merged = 1;
- s->redundant = 1;
- cnt++;
- break;
- } } }
- return cnt;
- }
- static int
- all_trans_match(State *a, State *b)
- { Transition *s, *t;
- int found, result = 0;
- if (a->accepting != b->accepting)
- goto done;
- for (s = a->trans; s; s = s->nxt)
- { if (s->redundant) continue;
- found = 0;
- for (t = b->trans; t; t = t->nxt)
- { if (t->redundant) continue;
- if (sametrans(s, t))
- { found = 1;
- t->marked = 1;
- break;
- } }
- if (!found)
- goto done;
- }
- for (s = b->trans; s; s = s->nxt)
- { if (s->redundant || s->marked) continue;
- found = 0;
- for (t = a->trans; t; t = t->nxt)
- { if (t->redundant) continue;
- if (sametrans(s, t))
- { found = 1;
- break;
- } }
- if (!found)
- goto done;
- }
- result = 1;
- done:
- for (s = b->trans; s; s = s->nxt)
- s->marked = 0;
- return result;
- }
- #ifndef NO_OPT
- #define BUCKY
- #endif
- #ifdef BUCKY
- static int
- all_bucky(State *a, State *b)
- { Transition *s, *t;
- int found, result = 0;
- for (s = a->trans; s; s = s->nxt)
- { if (s->redundant) continue;
- found = 0;
- for (t = b->trans; t; t = t->nxt)
- { if (t->redundant) continue;
- if (isequal(s->cond, t->cond))
- { if (strcmp(s->name->name, b->name->name) == 0
- && strcmp(t->name->name, a->name->name) == 0)
- { found = 1; /* they point to each other */
- t->marked = 1;
- break;
- }
- if (strcmp(s->name->name, t->name->name) == 0
- && strcmp(s->name->name, "accept_all") == 0)
- { found = 1;
- t->marked = 1;
- break;
- /* same exit from which there is no return */
- }
- }
- }
- if (!found)
- goto done;
- }
- for (s = b->trans; s; s = s->nxt)
- { if (s->redundant || s->marked) continue;
- found = 0;
- for (t = a->trans; t; t = t->nxt)
- { if (t->redundant) continue;
- if (isequal(s->cond, t->cond))
- { if (strcmp(s->name->name, a->name->name) == 0
- && strcmp(t->name->name, b->name->name) == 0)
- { found = 1;
- t->marked = 1;
- break;
- }
- if (strcmp(s->name->name, t->name->name) == 0
- && strcmp(s->name->name, "accept_all") == 0)
- { found = 1;
- t->marked = 1;
- break;
- }
- }
- }
- if (!found)
- goto done;
- }
- result = 1;
- done:
- for (s = b->trans; s; s = s->nxt)
- s->marked = 0;
- return result;
- }
- static int
- buckyballs(void)
- { State *a, *b, *c, *d;
- int m, cnt=0;
- do {
- m = 0; cnt++;
- for (a = never; a; a = a->nxt)
- { if (!a->reachable) continue;
- if (a->redundant) continue;
- for (b = a->nxt; b; b = b->nxt)
- { if (!b->reachable) continue;
- if (b->redundant) continue;
- if (all_bucky(a, b))
- { m++;
- if (tl_verbose)
- { printf("%s bucky match %s\n",
- a->name->name, b->name->name);
- }
- if (a->accepting && !b->accepting)
- { if (strcmp(b->name->name, "T0_init") == 0)
- { c = a; d = b;
- b->accepting = 1;
- } else
- { c = b; d = a;
- }
- } else
- { c = a; d = b;
- }
- retarget(c->name->name, d->name->name);
- if (!strncmp(c->name->name, "accept", 6)
- && Max_Red == 0)
- { char buf[64];
- sprintf(buf, "T0%s", &(c->name->name[6]));
- retarget(buf, d->name->name);
- }
- break;
- }
- } }
- } while (m && cnt < 10);
- return cnt-1;
- }
- #endif
- static int
- mergestates(int v)
- { State *a, *b;
- int m, cnt=0;
- if (tl_verbose)
- return 0;
- do {
- m = 0; cnt++;
- for (a = never; a; a = a->nxt)
- { if (v && !a->reachable) continue;
- if (a->redundant) continue; /* 3.3.10 */
- for (b = a->nxt; b; b = b->nxt)
- { if (v && !b->reachable) continue;
- if (b->redundant) continue; /* 3.3.10 */
- if (all_trans_match(a, b))
- { m++;
- if (tl_verbose)
- { printf("%d: state %s equals state %s\n",
- cnt, a->name->name, b->name->name);
- showtrans(a);
- printf("==\n");
- showtrans(b);
- }
- retarget(a->name->name, b->name->name);
- if (!strncmp(a->name->name, "accept", 6)
- && Max_Red == 0)
- { char buf[64];
- sprintf(buf, "T0%s", &(a->name->name[6]));
- retarget(buf, b->name->name);
- }
- break;
- }
- #if 0
- else if (tl_verbose)
- { printf("\n%d: state %s differs from state %s [%d,%d]\n",
- cnt, a->name->name, b->name->name,
- a->accepting, b->accepting);
- showtrans(a);
- printf("==\n");
- showtrans(b);
- printf("\n");
- }
- #endif
- } }
- } while (m && cnt < 10);
- return cnt-1;
- }
- static int tcnt;
- static void
- rev_trans(Transition *t) /* print transitions in reverse order... */
- {
- if (!t) return;
- rev_trans(t->nxt);
- if (t->redundant && !tl_verbose) return;
- fprintf(tl_out, "\t:: (");
- if (dump_cond(t->cond, t->cond, 1))
- fprintf(tl_out, "1");
- fprintf(tl_out, ") -> goto %s\n", t->name->name);
- tcnt++;
- }
- static void
- printstate(State *b)
- {
- if (!b || (!tl_verbose && !b->reachable)) return;
- b->reachable = 0; /* print only once */
- fprintf(tl_out, "%s:\n", b->name->name);
- if (tl_verbose)
- { fprintf(tl_out, " /* ");
- dump(b->colors->Other);
- fprintf(tl_out, " */\n");
- }
- if (strncmp(b->name->name, "accept", 6) == 0
- && Max_Red == 0)
- fprintf(tl_out, "T0%s:\n", &(b->name->name[6]));
- fprintf(tl_out, "\tif\n");
- tcnt = 0;
- rev_trans(b->trans);
- if (!tcnt) fprintf(tl_out, "\t:: false\n");
- fprintf(tl_out, "\tfi;\n");
- Total++;
- }
- void
- addtrans(Graph *col, char *from, Node *op, char *to)
- { State *b;
- Transition *t;
- t = (Transition *) tl_emalloc(sizeof(Transition));
- t->name = tl_lookup(to);
- t->cond = Prune(dupnode(op));
- if (tl_verbose)
- { printf("\n%s <<\t", from); dump(op);
- printf("\n\t"); dump(t->cond);
- printf(">> %s\n", t->name->name);
- }
- if (t->cond) t->cond = rewrite(t->cond);
- for (b = never; b; b = b->nxt)
- if (!strcmp(b->name->name, from))
- { t->nxt = b->trans;
- b->trans = t;
- return;
- }
- b = (State *) tl_emalloc(sizeof(State));
- b->name = tl_lookup(from);
- b->colors = col;
- b->trans = t;
- if (!strncmp(from, "accept", 6))
- b->accepting = 1;
- b->nxt = never;
- never = b;
- }
- static void
- clr_reach(void)
- { State *p;
- for (p = never; p; p = p->nxt)
- p->reachable = 0;
- hitsall = 0;
- }
- void
- fsm_print(void)
- { State *b; int cnt1, cnt2=0;
- extern void put_uform(void);
- if (tl_clutter) clutter();
- b = findstate("T0_init");
- if (Max_Red == 0)
- b->accepting = 1;
- mergestates(0);
- b = findstate("T0_init");
- fprintf(tl_out, "never { /* ");
- put_uform();
- fprintf(tl_out, " */\n");
- do {
- clr_reach();
- Dfs(b);
- cnt1 = mergetrans();
- cnt2 = mergestates(1);
- if (tl_verbose)
- printf("/* >>%d,%d<< */\n", cnt1, cnt2);
- } while (cnt2 > 0);
- #ifdef BUCKY
- buckyballs();
- clr_reach();
- Dfs(b);
- #endif
- if (b && b->accepting)
- fprintf(tl_out, "accept_init:\n");
- if (!b && !never)
- { fprintf(tl_out, " 0 /* false */;\n");
- } else
- { printstate(b); /* init state must be first */
- for (b = never; b; b = b->nxt)
- printstate(b);
- }
- if (hitsall)
- fprintf(tl_out, "accept_all:\n skip\n");
- fprintf(tl_out, "}\n");
- }
|