/***** spin: pangen2.h *****/ /* Copyright (c) 1989-2007 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 */ /* (c) 2007: small additions for V5.0 to support multi-core verifications */ static char *Pre0[] = { "#ifdef SC", "#define _FILE_OFFSET_BITS 64", /* to allow file sizes greater than 2Gb */ "#endif", "#include ", "#include ", "#include ", "#include ", "#include ", "#include ", "#include ", "#if defined(WIN32) || defined(WIN64)", "#include ", "#else", "#include ", "#include ", "#endif", "#include ", /* defines off_t */ "#include ", "#include ", "#define Offsetof(X, Y) ((unsigned long)(&(((X *)0)->Y)))", "#ifndef max", "#define max(a,b) (((a)<(b)) ? (b) : (a))", "#endif", "#ifndef PRINTF", "int Printf(const char *fmt, ...); /* prototype only */", "#endif", 0, }; static char *Preamble[] = { "#ifdef RANDOMIZE", " #define T_RAND RANDOMIZE", "#endif", "#ifdef CNTRSTACK", " #define onstack_now() (LL[trpt->j6] && LL[trpt->j7])", " #define onstack_put() LL[trpt->j6]++; LL[trpt->j7]++", " #define onstack_zap() LL[trpt->j6]--; LL[trpt->j7]--", "#endif", "#if !defined(SAFETY) && !defined(NOCOMP)", /* * V_A identifies states in the current statespace * A_V identifies states in the 'other' statespace * S_A remembers how many leading bytes in the sv * are used for these markers + fairness bits */ " #define V_A (((now._a_t&1)?2:1) << (now._a_t&2))", " #define A_V (((now._a_t&1)?1:2) << (now._a_t&2))", " int S_A = 0;", "#else", " #define V_A 0", " #define A_V 0", " #define S_A 0", "#endif", "#ifdef MA", "#undef onstack_now", "#undef onstack_put", "#undef onstack_zap", "#define onstack_put() ;", "#define onstack_zap() gstore((char *) &now, vsize, 4)", "#else", "#if defined(FULLSTACK) && !defined(BITSTATE)", "#define onstack_put() trpt->ostate = Lstate", "#define onstack_zap() { \\", " if (trpt->ostate) \\", " trpt->ostate->tagged = \\", " (S_A)? (trpt->ostate->tagged&~V_A) : 0; \\", " }", "#endif", "#endif", "#ifndef NO_V_PROVISO", "#define V_PROVISO", "#endif", "#if !defined(NO_RESIZE) && !defined(AUTO_RESIZE) && !defined(BITSTATE) && !defined(SPACE) && NCORE==1", " #define AUTO_RESIZE", "#endif", "", "struct H_el {", " struct H_el *nxt;", "#ifdef FULLSTACK", " unsigned int tagged;", " #if defined(BITSTATE) && !defined(NOREDUCE) && !defined(SAFETY)", " unsigned int proviso;", /* uses just 1 bit 0/1 */ " #endif", "#endif", "#if defined(CHECK) || (defined(COLLAPSE) && !defined(FULLSTACK))", " unsigned long st_id;", "#endif", "#if !defined(SAFETY) || defined(REACH)", " unsigned int D;", "#endif", "#ifdef BCS", " #ifndef CONSERVATIVE", " #define CONSERVATIVE 1 /* good for up to 8 processes */", " #endif", " #ifdef CONSERVATIVE", " #if CONSERVATIVE <= 0 || CONSERVATIVE>32", " #error sensible values for CONSERVATIVE are 1..32 (256/8 = 32)", " #endif", " uchar ctx_pid[CONSERVATIVE];", /* pids setting lowest value */ " #endif", " uchar ctx_low;", /* lowest nr of context switches seen so far */ "#endif", "#if NCORE>1", " /* could cost 1 extra word: 4 bytes if 32-bit and 8 bytes if 64-bit */", " #ifdef V_PROVISO", " uchar cpu_id; /* id of cpu that created the state */", " #endif", "#endif", "#ifdef COLLAPSE", " #if VECTORSZ<65536", " unsigned short ln;", /* length of vector */ " #else", " unsigned long ln;", /* length of vector */ " #endif", "#endif", "#if defined(AUTO_RESIZE) && !defined(BITSTATE)", " unsigned long m_K1;", "#endif", " unsigned long state;", "} **H_tab, **S_Tab;\n", "typedef struct Trail {", " int st; /* current state */", " int o_tt;", " uchar pr; /* process id */", " uchar tau; /* 8 bit-flags */", " uchar o_pm; /* 8 more bit-flags */", "#if 0", " Meaning of bit-flags:", " tau&1 -> timeout enabled", " tau&2 -> request to enable timeout 1 level up (in claim)", " tau&4 -> current transition is a claim move", " tau&8 -> current transition is an atomic move", " tau&16 -> last move was truncated on stack", " tau&32 -> current transition is a preselected move", " tau&64 -> at least one next state is not on the stack", " tau&128 -> current transition is a stutter move", " o_pm&1 -> the current pid moved -- implements else", " o_pm&2 -> this is an acceptance state", " o_pm&4 -> this is a progress state", " o_pm&8 -> fairness alg rule 1 undo mark", " o_pm&16 -> fairness alg rule 3 undo mark", " o_pm&32 -> fairness alg rule 2 undo mark", " o_pm&64 -> the current proc applied rule2", " o_pm&128 -> a fairness, dummy move - all procs blocked", "#endif", "#ifdef NSUCC", " uchar n_succ; /* nr of successor states */", "#endif", "#if defined(FULLSTACK) && defined(MA) && !defined(BFS)", " uchar proviso;", "#endif", "#ifndef BFS", " uchar o_n, o_ot; /* to save locals */", "#endif", " uchar o_m;", "#ifdef EVENT_TRACE", " #if nstates_event<256", " uchar o_event;", " #else", " unsigned short o_event;", " #endif", "#endif", "#ifndef BFS", " short o_To;", " #ifdef T_RAND", " short oo_i;", " #endif", "#endif", "#if defined(HAS_UNLESS) && !defined(BFS)", " int e_state; /* if escape trans - state of origin */", "#endif", "#if (defined(FULLSTACK) && !defined(MA)) || defined(BFS) || (NCORE>1)", " struct H_el *ostate; /* pointer to stored state */", "#endif", /* CNTRSTACK when !NOREDUCE && BITSTATE && SAFETY, uses LL[] */ "#if defined(CNTRSTACK) && !defined(BFS)", " long j6, j7;", "#endif", " Trans *o_t;", /* transition fct, next state */ "#if !defined(BFS) && !defined(TRIX_ORIG)", " char *p_bup;", " char *q_bup;", "#endif", "#ifdef BCS", " unsigned short sched_limit;", " unsigned char bcs; /* phase 1 or 2, or forced 4 */", " unsigned char b_pno; /* preferred pid */", "#endif", "#ifdef P_RAND", /* process scheduling randomization */ " unsigned char p_left; /* nr of procs left to explore */", " short p_skip; /* to find starting point in list */", "#endif", "#ifdef HAS_SORTED", " short ipt;", /* insertion slot in q */ "#endif", " union {", " int oval;", /* single backup value of variable */ " int *ovals;", /* ptr to multiple values */ " } bup;", "} Trail;", "Trail *trail, *trpt;", "FILE *efd;", "uchar *this;", "long maxdepth=10000;", "long omaxdepth=10000;", "#ifdef BCS", " /* bitflags in trpt->bcs */", " #define B_PHASE1 1", " #define B_PHASE2 2", " #define B_FORCED 4", "int sched_max = 0;", "#endif", "#ifdef PERMUTED", " uchar permuted = 1;", "#else", " uchar permuted = 0;", "#endif", "double quota; /* time limit */", "#if NCORE>1", "long z_handoff = -1;", "#endif", "#ifdef SC", /* stack cycling */ "char *stackfile;", "#endif", "uchar *SS, *LL;", "uchar HASH_NR = 0;", "", "double memcnt = (double) 0;", "double memlim = (double) (1<<30); /* 1 GB */", "#if NCORE>1", "double mem_reserved = (double) 0;", "#endif", "", "/* for emalloc: */", "static char *have;", "static long left = 0L;", "static double fragment = (double) 0;", "static unsigned long grow;", "", #if 1 "unsigned int HASH_CONST[] = {", " /* asuming 4 bytes per int */", " 0x100d4e63, 0x0fc22f87,", " 0x3ff0c3ff, 0x38e84cd7,", " 0x02b148e9, 0x98b2e49d,", " 0xb616d379, 0xa5247fd9,", " 0xbae92a15, 0xb91c8bc5,", " 0x8e5880f3, 0xacd7c069,", " 0xb4c44bb3, 0x2ead1fb7,", " 0x8e428171, 0xdbebd459,", " 0x00400007, 0x04c11db7,", " 0x828ae611, 0x6cb25933,", " 0x86cdd651, 0x9e8f5f21,", " 0xd5f8d8e7, 0x9c4e956f,", " 0xb5cf2c71, 0x2e805a6d,", " 0x33fc3a55, 0xaf203ed1,", " 0xe31f5909, 0x5276db35,", " 0x0c565ef7, 0x273d1aa5,", " 0x8923b1dd, 0xa9acaac5,", " 0xd1f69207, 0xedfd944b,", " 0x9a68e46b, 0x5355e13f,", " 0x7eeb44f9, 0x932beea9,", " 0x330c4cd3, 0x87f34e5f,", " 0x1b5851b7, 0xb9ca6447,", " 0x58f96a8f, 0x1b3b5307,", " 0x31c387b3, 0xf35f0f35,", " 0xa0acc4df, 0xf3140303,", " 0x2446245d, 0xe4b8f4ef,", " 0x5c007383, 0x68e648af,", " 0x1814fba7, 0xcdf731b5,", " 0xd09ccb4b, 0xb92d0eff,", " 0xcc3c6b67, 0xd3af6a57,", " 0xf44fc3f5, 0x5bb67623,", " 0xaeb9c953, 0x5e0ac739,", " 0x3a7fda09, 0x5edf39eb,", " 0x661eefd9, 0x6423f0d1,", " 0x910fe413, 0x9ec92297,", " 0x4bd8159d, 0xa7b16ee1,", " 0x89d484e9, 0x7f305cb3,", " 0xc5f303e7, 0x415deeef,", " 0x09986f89, 0x7e9c4117,", " 0x0b7cbedb, 0xf9ed7561,", " 0x7a20ac99, 0xf05adef3,", " 0x5893d75b, 0x44d73327,", " 0xb583c873, 0x324d2145,", " 0x7fa3829b, 0xe4b47a23,", " 0xe256d94f, 0xb1fd8959,", " 0xe561a321, 0x1435ac09,", " 0xdd62408b, 0x02ec0bcb,", " 0x5469b785, 0x2f4f50bb,", " 0x20f19395, 0xf96ba085,", " 0x2381f937, 0x768e2a11,", " 0", "};", #else "unsigned int HASH_CONST[] = {", " /* asuming 4 bytes per int */", " 0x88888EEF, 0x00400007,", " 0x04c11db7, 0x100d4e63,", " 0x0fc22f87, 0x3ff0c3ff,", " 0x38e84cd7, 0x02b148e9,", " 0x98b2e49d, 0xb616d379,", " 0xa5247fd9, 0xbae92a15,", " 0xb91c8bc5, 0x8e5880f3,", " 0xacd7c069, 0xb4c44bb3,", " 0x2ead1fb7, 0x8e428171,", " 0xdbebd459, 0x828ae611,", " 0x6cb25933, 0x86cdd651,", " 0x9e8f5f21, 0xd5f8d8e7,", " 0x9c4e956f, 0xb5cf2c71,", " 0x2e805a6d, 0x33fc3a55,", " 0xaf203ed1, 0xe31f5909,", " 0x5276db35, 0x0c565ef7,", " 0x273d1aa5, 0x8923b1dd,", " 0", "};", #endif "#if NCORE>1", "extern int core_id;", "#endif", "long mreached=0;", "int done=0, errors=0, Nrun=1;", "int c_init_done=0;", "char *c_stack_start = (char *) 0;", "double nstates=0, nlinks=0, truncs=0, truncs2=0;", "double nlost=0, nShadow=0, hcmp=0, ngrabs=0;", "#ifdef PUTPID", "char *progname;", "#endif", "#if defined(ZAPH) && defined(BITSTATE)", "double zstates = 0;", "#endif", "int c_init_run;", "#ifdef BFS", "double midrv=0, failedrv=0, revrv=0;", "#endif", "unsigned long nr_states=0; /* nodes in DFA */", "long Fa=0, Fh=0, Zh=0, Zn=0;", "long PUT=0, PROBE=0, ZAPS=0;", "long Ccheck=0, Cholds=0;", "int a_cycles=0, upto=1, strict=0, verbose = 0, signoff = 0;", "#ifdef HAS_CODE", "int gui = 0, coltrace = 0, readtrail = 0;", "int whichtrail = 0, whichclaim = -1, onlyproc = -1, silent = 0;", "char *claimname;", "#endif", "int state_tables=0, fairness=0, no_rck=0, Nr_Trails=0, dodot=0;", "char simvals[128];", "#ifndef INLINE", "int TstOnly=0;", "#endif", "unsigned long mask, nmask;", "#ifdef BITSTATE", "int ssize=23; /* 1 Mb */", "#else", "int ssize=19; /* 512K slots */", "#endif", "int hmax=0, svmax=0, smax=0;", "int Maxbody=0, XX;", "uchar *noptr, *noqptr; /* used by Pptr(x) and Qptr(x) */", "#ifdef VAR_RANGES", "void logval(char *, int);", "void dumpranges(void);", "#endif", "#ifdef MA", "#define INLINE_REV", "extern void dfa_init(unsigned short);", "extern int dfa_member(unsigned long);", "extern int dfa_store(uchar *);", "unsigned int maxgs = 0;", "#endif", "", "#ifdef ALIGNED", " State comp_now __attribute__ ((aligned (8)));", " /* gcc 64-bit aligned for Itanium2 systems */", " /* MAJOR runtime penalty if not used on those systems */", "#else", " State comp_now; /* compressed state vector */", "#endif", "", "State comp_msk;", "uchar *Mask = (uchar *) &comp_msk;", "#ifdef COLLAPSE", "State comp_tmp;", "static char *scratch = (char *) &comp_tmp;", "#endif", "_Stack *stack; /* for queues, processes */", "Svtack *svtack; /* for old state vectors */", "#ifdef BITSTATE", "static unsigned int hfns = 3; /* new default */", "#endif", "static unsigned long j1_spin; /* 5.2.1: avoid nameclash with math.h */", "static unsigned long K1, K2;", "static unsigned long j2, j3, j4;", "#ifdef BITSTATE", "static long udmem;", "#endif", "static long A_depth = 0;", "long depth = 0;", /* depth: not static to support -S2, but possible clash with embedded code */ "#if NCORE>1", "long nr_handoffs = 0;", "#endif", "static uchar warned = 0, iterative = 0, exclusive = 0, like_java = 0, every_error = 0;", "static uchar noasserts = 0, noends = 0, bounded = 0;", "#if defined(T_RAND) || defined(P_RAND) || defined(RANDSTOR)", "unsigned int s_rand = 123; /* default seed */", "#endif", "#if SYNC>0 && ASYNC==0", "void set_recvs(void);", "int no_recvs(int);", "#endif", "#if SYNC", "#define IfNotBlocked if (boq != -1) continue;", "#define UnBlock boq = -1", "#else", "#define IfNotBlocked /* cannot block */", "#define UnBlock /* don't bother */", "#endif\n", "#ifdef BITSTATE", "int (*bstore)(char *, int);", "int bstore_reg(char *, int);", "int bstore_mod(char *, int);", "#endif", "void active_procs(void);", "void cleanup(void);", "void do_the_search(void);", "void find_shorter(int);", "void iniglobals(int);", "void stopped(int);", "void wrapup(void);", "int *grab_ints(int);", "void ungrab_ints(int *, int);", 0, }; static char *Tail[] = { "Trans *", "settr( int t_id, int a, int b, int c, int d,", " char *t, int g, int tpe0, int tpe1)", "{ Trans *tmp = (Trans *) emalloc(sizeof(Trans));\n", " tmp->atom = a&(6|32); /* only (2|8|32) have meaning */", " if (!g) tmp->atom |= 8; /* no global references */", " tmp->st = b;", " tmp->tpe[0] = tpe0;", " tmp->tpe[1] = tpe1;", " tmp->tp = t;", " tmp->t_id = t_id;", " tmp->forw = c;", " tmp->back = d;", " return tmp;", "}\n", "Trans *", "cpytr(Trans *a)", "{ Trans *tmp = (Trans *) emalloc(sizeof(Trans));\n", " int i;", " tmp->atom = a->atom;", " tmp->st = a->st;", "#ifdef HAS_UNLESS", " tmp->e_trans = a->e_trans;", " for (i = 0; i < HAS_UNLESS; i++)", " tmp->escp[i] = a->escp[i];", "#endif", " tmp->tpe[0] = a->tpe[0];", " tmp->tpe[1] = a->tpe[1];", " for (i = 0; i < 6; i++)", " { tmp->qu[i] = a->qu[i];", " tmp->ty[i] = a->ty[i];", " }", " tmp->tp = (char *) emalloc(strlen(a->tp)+1);", " strcpy(tmp->tp, a->tp);", " tmp->t_id = a->t_id;", " tmp->forw = a->forw;", " tmp->back = a->back;", " return tmp;", "}\n", "#ifndef NOREDUCE", "int", "srinc_set(int n)", "{ if (n <= 2) return LOCAL;", " if (n <= 2+ DELTA) return Q_FULL_F; /* 's' or nfull */", " if (n <= 2+2*DELTA) return Q_EMPT_F; /* 'r' or nempty */", " if (n <= 2+3*DELTA) return Q_EMPT_T; /* empty */", " if (n <= 2+4*DELTA) return Q_FULL_T; /* full */", " if (n == 5*DELTA) return GLOBAL;", " if (n == 6*DELTA) return TIMEOUT_F;", " if (n == 7*DELTA) return ALPHA_F;", " Uerror(\"cannot happen srinc_class\");", " return BAD;", "}", "int", "srunc(int n, int m)", "{ switch(m) {", " case Q_FULL_F: return n-2;", " case Q_EMPT_F: return n-2-DELTA;", " case Q_EMPT_T: return n-2-2*DELTA;", " case Q_FULL_T: return n-2-3*DELTA;", " case ALPHA_F:", " case TIMEOUT_F: return 257; /* non-zero, and > MAXQ */", " }", " Uerror(\"cannot happen srunc\");", " return 0;", "}", "#endif", "int cnt;", "#ifdef HAS_UNLESS", "int", "isthere(Trans *a, int b)", /* is b already in a's list? */ "{ Trans *t;", " for (t = a; t; t = t->nxt)", " if (t->t_id == b)", " return 1;", " return 0;", "}", "#endif", "#ifndef NOREDUCE", "int", "mark_safety(Trans *t) /* for conditional safety */", "{ int g = 0, i, j, k;", "", " if (!t) return 0;", " if (t->qu[0])", " return (t->qu[1])?2:1; /* marked */", "", " for (i = 0; i < 2; i++)", " { j = srinc_set(t->tpe[i]);", " if (j >= GLOBAL && j != ALPHA_F)", " return -1;", " if (j != LOCAL)", " { k = srunc(t->tpe[i], j);", " if (g == 0", " || t->qu[0] != k", " || t->ty[0] != j)", " { t->qu[g] = k;", " t->ty[g] = j;", " g++;", " } } }", " return g;", "}", "#endif", "void", "retrans(int n, int m, int is, short srcln[], uchar reach[], uchar lstate[])", " /* process n, with m states, is=initial state */", "{ Trans *T0, *T1, *T2, *T3, *T4, *T5;", " int i, k;", "#ifndef NOREDUCE", " int g, h, j, aa;", "#endif", "#ifdef HAS_UNLESS", " int p;", "#endif", " if (state_tables >= 4)", " { printf(\"STEP 1 %%s\\n\", ", " procname[n]);", " for (i = 1; i < m; i++)", " for (T0 = trans[n][i]; T0; T0 = T0->nxt)", " crack(n, i, T0, srcln);", " return;", " }", " do {", " for (i = 1, cnt = 0; i < m; i++)", " { T2 = trans[n][i];", " T1 = T2?T2->nxt:(Trans *)0;", "/* prescan: */ for (T0 = T1; T0; T0 = T0->nxt)", "/* choice in choice */ { if (T0->st && trans[n][T0->st]", " && trans[n][T0->st]->nxt)", " break;", " }", "#if 0", " if (T0)", " printf(\"\\tstate %%d / %%d: choice in choice\\n\",", " i, T0->st);", "#endif", " if (T0)", " for (T0 = T1; T0; T0 = T0->nxt)", " { T3 = trans[n][T0->st];", " if (!T3->nxt)", " { T2->nxt = cpytr(T0);", " T2 = T2->nxt;", " imed(T2, T0->st, n, i);", " continue;", " }", " do { T3 = T3->nxt;", " T2->nxt = cpytr(T3);", " T2 = T2->nxt;", " imed(T2, T0->st, n, i);", " } while (T3->nxt);", " cnt++;", " }", " }", " } while (cnt);", " if (state_tables >= 3)", " { printf(\"STEP 2 %%s\\n\", ", " procname[n]);", " for (i = 1; i < m; i++)", " for (T0 = trans[n][i]; T0; T0 = T0->nxt)", " crack(n, i, T0, srcln);", " return;", " }", " for (i = 1; i < m; i++)", " { if (trans[n][i] && trans[n][i]->nxt) /* optimize */", " { T1 = trans[n][i]->nxt;", "#if 0", " printf(\"\\t\\tpull %%d (%%d) to %%d\\n\",", " T1->st, T1->forw, i);", "#endif", /* pull linenumber ref as well: */ " srcln[i] = srcln[T1->st]; /* Oyvind Teig, 5.2.0 */", "", " if (!trans[n][T1->st]) continue;", " T0 = cpytr(trans[n][T1->st]);", " trans[n][i] = T0;", " reach[T1->st] = 1;", " imed(T0, T1->st, n, i);", " for (T1 = T1->nxt; T1; T1 = T1->nxt)", " {", "#if 0", " printf(\"\\t\\tpull %%d (%%d) to %%d\\n\",", " T1->st, T1->forw, i);", "#endif", " /* srcln[i] = srcln[T1->st]; gh: not useful */", " if (!trans[n][T1->st]) continue;", " T0->nxt = cpytr(trans[n][T1->st]);", " T0 = T0->nxt;", " reach[T1->st] = 1;", " imed(T0, T1->st, n, i);", " } } }", " if (state_tables >= 2)", " { printf(\"STEP 3 %%s\\n\", ", " procname[n]);", " for (i = 1; i < m; i++)", " for (T0 = trans[n][i]; T0; T0 = T0->nxt)", " crack(n, i, T0, srcln);", " return;", " }", "#ifdef HAS_UNLESS", " for (i = 1; i < m; i++)", " { if (!trans[n][i]) continue;", " /* check for each state i if an", " * escape to some state p is defined", " * if so, copy and mark p's transitions", " * and prepend them to the transition-", " * list of state i", " */", " if (!like_java) /* the default */", " { for (T0 = trans[n][i]; T0; T0 = T0->nxt)", " for (k = HAS_UNLESS-1; k >= 0; k--)", " { if (p = T0->escp[k])", " for (T1 = trans[n][p]; T1; T1 = T1->nxt)", " { if (isthere(trans[n][i], T1->t_id))", " continue;", " T2 = cpytr(T1);", " T2->e_trans = p;", " T2->nxt = trans[n][i];", " trans[n][i] = T2;", " } }", " } else /* outermost unless checked first */", " { T4 = T3 = (Trans *) 0;", " for (T0 = trans[n][i]; T0; T0 = T0->nxt)", " for (k = HAS_UNLESS-1; k >= 0; k--)", " { if (p = T0->escp[k])", " for (T1 = trans[n][p]; T1; T1 = T1->nxt)", " { if (isthere(trans[n][i], T1->t_id))", " continue;", " T2 = cpytr(T1);", " T2->nxt = (Trans *) 0;", " T2->e_trans = p;", " if (T3) T3->nxt = T2;", " else T4 = T2;", " T3 = T2;", " } }", " if (T4)", " { T3->nxt = trans[n][i];", " trans[n][i] = T4;", " }", " }", " }", "#endif", "#ifndef NOREDUCE", " for (i = 1; i < m; i++)", " { if (a_cycles)", " { /* moves through these states are visible */", " #if PROG_LAB>0 && defined(HAS_NP)", " if (progstate[n][i])", " goto degrade;", " for (T1 = trans[n][i]; T1; T1 = T1->nxt)", " if (progstate[n][T1->st])", " goto degrade;", " #endif", " if (accpstate[n][i] || visstate[n][i])", " goto degrade;", " for (T1 = trans[n][i]; T1; T1 = T1->nxt)", " if (accpstate[n][T1->st])", " goto degrade;", " }", " T1 = trans[n][i];", " if (!T1) continue;", " g = mark_safety(T1); /* V3.3.1 */", " if (g < 0) goto degrade; /* global */", " /* check if mixing of guards preserves reduction */", " if (T1->nxt)", " { k = 0;", " for (T0 = T1; T0; T0 = T0->nxt)", " { if (!(T0->atom&8))", " goto degrade;", " for (aa = 0; aa < 2; aa++)", " { j = srinc_set(T0->tpe[aa]);", " if (j >= GLOBAL && j != ALPHA_F)", " goto degrade;", " if (T0->tpe[aa]", " && T0->tpe[aa]", " != T1->tpe[0])", " k = 1;", " } }", " /* g = 0; V3.3.1 */", " if (k) /* non-uniform selection */", " for (T0 = T1; T0; T0 = T0->nxt)", " for (aa = 0; aa < 2; aa++)", " { j = srinc_set(T0->tpe[aa]);", " if (j != LOCAL)", " { k = srunc(T0->tpe[aa], j);", " for (h = 0; h < 6; h++)", " if (T1->qu[h] == k", " && T1->ty[h] == j)", " break;", " if (h >= 6)", " { T1->qu[g%%6] = k;", " T1->ty[g%%6] = j;", " g++;", " } } }", " if (g > 6)", " { T1->qu[0] = 0; /* turn it off */", " printf(\"pan: warning, line %%d, \",", " srcln[i]);", " printf(\"too many stmnt types (%%d)\",", " g);", " printf(\" in selection\\n\");", " goto degrade;", " }", " }", " /* mark all options global if >=1 is global */", " for (T1 = trans[n][i]; T1; T1 = T1->nxt)", " if (!(T1->atom&8)) break;", " if (T1)", "degrade: for (T1 = trans[n][i]; T1; T1 = T1->nxt)", " T1->atom &= ~8; /* mark as unsafe */", " /* can only mix 'r's or 's's if on same chan */", " /* and not mixed with other local operations */", " T1 = trans[n][i];", " if (!T1 || T1->qu[0]) continue;", " j = T1->tpe[0];", " if (T1->nxt && T1->atom&8)", " { if (j == 5*DELTA)", " { printf(\"warning: line %%d \", srcln[i]);", " printf(\"mixed condition \");", " printf(\"(defeats reduction)\\n\");", " goto degrade;", " }", " for (T0 = T1; T0; T0 = T0->nxt)", " for (aa = 0; aa < 2; aa++)", " if (T0->tpe[aa] && T0->tpe[aa] != j)", " { printf(\"warning: line %%d \", srcln[i]);", " printf(\"[%%d-%%d] mixed %%stion \",", " T0->tpe[aa], j, ", " (j==5*DELTA)?\"condi\":\"selec\");", " printf(\"(defeats reduction)\\n\");", " printf(\" '%%s' <-> '%%s'\\n\",", " T1->tp, T0->tp);", " goto degrade;", " } }", " }", "#endif", " for (i = 1; i < m; i++)", /* R */ " { T2 = trans[n][i];", " if (!T2", " || T2->nxt", " || strncmp(T2->tp, \".(goto)\", 7)", " || !stopstate[n][i])", " continue;", " stopstate[n][T2->st] = 1;", " }", " if (state_tables && !verbose)", " { if (dodot)", " { char buf[256], *q = buf, *p = procname[n];", " while (*p != '\\0')", " { if (*p != ':')", " { *q++ = *p;", " }", " p++;", " }", " *q = '\\0';", " printf(\"digraph \");", " switch (Btypes[n]) {", " case I_PROC: printf(\"init {\\n\"); break;", " case N_CLAIM: printf(\"claim_%%s {\\n\", buf); break;", " case E_TRACE: printf(\"notrace {\\n\"); break;", " case N_TRACE: printf(\"trace {\\n\"); break;", " default: printf(\"p_%%s {\\n\", buf); break;", " }", " printf(\"size=\\\"8,10\\\";\\n\");", " printf(\" GT [shape=box,style=dotted,label=\\\"%%s\\\"];\\n\", buf);", " } else", " { switch (Btypes[n]) {", " case I_PROC: printf(\"init\\n\"); break;", " case N_CLAIM: printf(\"claim %%s\\n\", procname[n]); break;", " case E_TRACE: printf(\"notrace assertion\\n\"); break;", " case N_TRACE: printf(\"trace assertion\\n\"); break;", " default: printf(\"proctype %%s\\n\", procname[n]); break;", " } }", " for (i = 1; i < m; i++)", " { reach[i] = 1;", " }", " tagtable(n, m, is, srcln, reach);", " if (dodot) printf(\"}\\n\");", " } else", " for (i = 1; i < m; i++)", " { int nrelse;", " if (Btypes[n] != N_CLAIM)", " { for (T0 = trans[n][i]; T0; T0 = T0->nxt)", " { if (T0->st == i", " && strcmp(T0->tp, \"(1)\") == 0)", " { printf(\"error: proctype '%%s' \",", " procname[n]);", " printf(\"line %%d, state %%d: has un\",", " srcln[i], i);", " printf(\"conditional self-loop\\n\");", " pan_exit(1);", " } } }", " nrelse = 0;", " for (T0 = trans[n][i]; T0; T0 = T0->nxt)", " { if (strcmp(T0->tp, \"else\") == 0)", " nrelse++;", " }", " if (nrelse > 1)", " { printf(\"error: proctype '%%s' state\",", " procname[n]);", " printf(\" %%d, inherits %%d\", i, nrelse);", " printf(\" 'else' stmnts\\n\");", " pan_exit(1);", " } }", "#ifndef LOOPSTATE", " if (state_tables)", "#endif", " do_dfs(n, m, is, srcln, reach, lstate);", "#ifdef T_REVERSE", " /* process n, with m states, is=initial state -- reverse list */", " if (!state_tables && Btypes[n] != N_CLAIM)", " { for (i = 1; i < m; i++)", /* for each state */ " { Trans *Tx = (Trans *) 0; /* list of escapes */", " Trans *Ty = (Trans *) 0; /* its tail element */", " T1 = (Trans *) 0; /* reversed list */", " T2 = (Trans *) 0; /* its tail */", " T3 = (Trans *) 0; /* remembers possible 'else' */", "", " /* find unless-escapes, they should go first */", " T4 = T5 = T0 = trans[n][i];", "#ifdef HAS_UNLESS", " while (T4 && T4->e_trans) /* escapes are first in orig list */", " { T5 = T4; /* remember predecessor */", " T4 = T4->nxt;", " }", "#endif", " /* T4 points to first non-escape, T5 to its parent, T0 to original list */", " if (T4 != T0) /* there was at least one escape */", " { T3 = T5->nxt; /* start of non-escapes */", " T5->nxt = (Trans *) 0; /* separate */", " Tx = T0; /* start of the escapes */", " Ty = T5; /* its tail */", " T0 = T3; /* the rest, to be reversed */", " }", " /* T0 points to first non-escape, Tx to the list of escapes, Ty to its tail */", "", " /* first tail-add non-escape transitions, reversed */", " T3 = (Trans *) 0;", /* remember a possible 'else' */ " for (T5 = T0; T5; T5 = T4)", " { T4 = T5->nxt;", "#ifdef HAS_UNLESS", " if (T5->e_trans)", " { printf(\"error: cannot happen!\\n\");", " continue;", " }", "#endif", " if (strcmp(T5->tp, \"else\") == 0)", " { T3 = T5;", " T5->nxt = (Trans *) 0;", " } else", " { T5->nxt = T1;", " if (!T1) { T2 = T5; }", " T1 = T5;", " } }", " /* T3 points to a possible else, which is removed from the list */", " /* T1 points to the reversed list so far (without escapes) */", " /* T2 points to the tail element -- where the else should go */", " if (T2 && T3) { T2->nxt = T3; } /* add else */", "", " /* add in the escapes, to that they appear at the front */", " if (Tx && Ty) { Ty->nxt = T1; T1 = Tx; }", "", " trans[n][i] = T1;", " /* reversed, with escapes first and else last */", " } }", " if (state_tables && verbose)", " { printf(\"FINAL proctype %%s\\n\", ", " procname[n]);", " for (i = 1; i < m; i++)", " for (T0 = trans[n][i]; T0; T0 = T0->nxt)", " crack(n, i, T0, srcln);", " }", "#endif", "}", "void", "imed(Trans *T, int v, int n, int j) /* set intermediate state */", "{ progstate[n][T->st] |= progstate[n][v];", " accpstate[n][T->st] |= accpstate[n][v];", " stopstate[n][T->st] |= stopstate[n][v];", " mapstate[n][j] = T->st;", "}", "void", "tagtable(int n, int m, int is, short srcln[], uchar reach[])", "{ Trans *z;\n", " if (is >= m || !trans[n][is]", " || is <= 0 || reach[is] == 0)", " return;", " reach[is] = 0;", " if (state_tables)", " for (z = trans[n][is]; z; z = z->nxt)", " { if (dodot)", " dot_crack(n, is, z);", " else", " crack(n, is, z, srcln);", " }", "", " for (z = trans[n][is]; z; z = z->nxt)", " {", "#ifdef HAS_UNLESS", " int i, j;", "#endif", " tagtable(n, m, z->st, srcln, reach);", "#ifdef HAS_UNLESS", " for (i = 0; i < HAS_UNLESS; i++)", " { j = trans[n][is]->escp[i];", " if (!j) break;", " tagtable(n, m, j, srcln, reach);", " }", "#endif", " }", "}", "void", "dfs_table(int n, int m, int is, short srcln[], uchar reach[], uchar lstate[])", "{ Trans *z;\n", " if (is >= m || is <= 0 || !trans[n][is])", " return;", " if ((reach[is] & (4|8|16)) != 0)", " { if ((reach[is] & (8|16)) == 16) /* on stack, not yet recorded */", " { lstate[is] = 1;", " reach[is] |= 8; /* recorded */", " if (state_tables && verbose)", " { printf(\"state %%d line %%d is a loopstate\\n\", is, srcln[is]);", " } }", " return;", " }", " reach[is] |= (4|16); /* visited | onstack */", " for (z = trans[n][is]; z; z = z->nxt)", " {", "#ifdef HAS_UNLESS", " int i, j;", "#endif", " dfs_table(n, m, z->st, srcln, reach, lstate);", "#ifdef HAS_UNLESS", " for (i = 0; i < HAS_UNLESS; i++)", " { j = trans[n][is]->escp[i];", " if (!j) break;", " dfs_table(n, m, j, srcln, reach, lstate);", " }", "#endif", " }", " reach[is] &= ~16; /* no longer on stack */", "}", "void", "do_dfs(int n, int m, int is, short srcln[], uchar reach[], uchar lstate[])", "{ int i;", " dfs_table(n, m, is, srcln, reach, lstate);", " for (i = 0; i < m; i++)", " reach[i] &= ~(4|8|16);", "}", "void", "crack(int n, int j, Trans *z, short srcln[])", "{ int i;\n", " if (!z) return;", " printf(\"\tstate %%3d -(tr %%3d)-> state %%3d \",", " j, z->forw, z->st);", " printf(\"[id %%3d tp %%3d\", z->t_id, z->tpe[0]);", " if (z->tpe[1]) printf(\",%%d\", z->tpe[1]);", "#ifdef HAS_UNLESS", " if (z->e_trans)", " printf(\" org %%3d\", z->e_trans);", " else if (state_tables >= 2)", " for (i = 0; i < HAS_UNLESS; i++)", " { if (!z->escp[i]) break;", " printf(\" esc %%d\", z->escp[i]);", " }", "#endif", " printf(\"]\");", " printf(\" [%%s%%s%%s%%s%%s] %%s:%%d => \",", " z->atom&6?\"A\":z->atom&32?\"D\":\"-\",", " accpstate[n][j]?\"a\" :\"-\",", " stopstate[n][j]?\"e\" : \"-\",", " progstate[n][j]?\"p\" : \"-\",", " z->atom & 8 ?\"L\":\"G\",", " PanSource, srcln[j]);", " for (i = 0; z->tp[i]; i++)", " if (z->tp[i] == \'\\n\')", " printf(\"\\\\n\");", " else", " putchar(z->tp[i]);", " if (verbose && z->qu[0])", " { printf(\"\\t[\");", " for (i = 0; i < 6; i++)", " if (z->qu[i])", " printf(\"(%%d,%%d)\",", " z->qu[i], z->ty[i]);", " printf(\"]\");", " }", " printf(\"\\n\");", " fflush(stdout);", "}", "/* spin -a m.pml; cc -o pan pan.c; ./pan -D | dot -Tps > foo.ps; ps2pdf foo.ps */", "void", "dot_crack(int n, int j, Trans *z)", "{ int i;\n", " if (!z) return;", " printf(\"\tS%%d -> S%%d [color=black\", j, z->st);", "", " if (z->atom&6) printf(\",style=dashed\");", /* A */ " else if (z->atom&32) printf(\",style=dotted\");", /* D */ " else if (z->atom&8) printf(\",style=solid\");", /* L */ " else printf(\",style=bold\");", /* G */ /* other styles: filled dotted */ "", " printf(\",label=\\\"\");", " for (i = 0; z->tp[i]; i++)", " { if (z->tp[i] == \'\\\\\'", " && z->tp[i+1] == \'n\')", " { i++; printf(\" \");", " } else", " { putchar(z->tp[i]);", " } }", " printf(\"\\\"];\\n\");", " if (accpstate[n][j]) printf(\" S%%d [color=red,style=bold];\\n\", j);", " else if (progstate[n][j]) printf(\" S%%d [color=green,style=bold];\\n\", j);", " if (stopstate[n][j]) printf(\" S%%d [color=blue,style=bold,shape=box];\\n\", j);", "}", "", "#ifdef VAR_RANGES", "#define BYTESIZE 32 /* 2^8 : 2^3 = 256:8 = 32 */", "", "typedef struct Vr_Ptr {", " char *nm;", " uchar vals[BYTESIZE];", " struct Vr_Ptr *nxt;", "} Vr_Ptr;", "Vr_Ptr *ranges = (Vr_Ptr *) 0;", "", "void", "logval(char *s, int v)", "{ Vr_Ptr *tmp;", "", " if (v<0 || v > 255) return;", " for (tmp = ranges; tmp; tmp = tmp->nxt)", " if (!strcmp(tmp->nm, s))", " goto found;", " tmp = (Vr_Ptr *) emalloc(sizeof(Vr_Ptr));", " tmp->nxt = ranges;", " ranges = tmp;", " tmp->nm = s;", "found:", " tmp->vals[(v)/8] |= 1<<((v)%%8);", "}", "", "void", "dumpval(uchar X[], int range)", "{ int w, x, i, j = -1;", "", " for (w = i = 0; w < range; w++)", " for (x = 0; x < 8; x++, i++)", " {", "from: if ((X[w] & (1<= 0 && j != 255)", " printf(\"-255\");", "}", "", "void", "dumpranges(void)", "{ Vr_Ptr *tmp;", " printf(\"\\nValues assigned within \");", " printf(\"interval [0..255]:\\n\");", " for (tmp = ranges; tmp; tmp = tmp->nxt)", " { printf(\"\\t%%s\\t: \", tmp->nm);", " dumpval(tmp->vals, BYTESIZE);", " printf(\"\\n\");", " }", "}", "#endif", 0, };