bobm@rtech.UUCP (Bob Mcqueer) (03/27/88)
------------- #! /bin/sh # This is a shell archive, meaning: # 1. Remove everything above the #! /bin/sh line. # 2. Save the resulting text in a file. # 3. Execute the file with /bin/sh (not csh) to create: # amain.c # analyze.c # anread.c # hat.c # keycheck.c # listsort.c # pmain.c # table.c # topsort.c # config.h # node.h # stdio.h # This archive created: Thu Mar 24 17:21:25 1988 export PATH; PATH=/bin:/usr/bin:$PATH echo shar: "extracting 'amain.c'" '(3448 characters)' if test -f 'amain.c' then echo shar: "will not over-write existing file 'amain.c'" else cat << \SHAR_EOF > 'amain.c' /* ** ** Copyright (c) 1988, Robert L. McQueer ** All Rights Reserved ** ** Permission granted for use, modification and redistribution of this ** software provided that no use is made for commercial gain without the ** written consent of the author, that all copyright notices remain intact, ** and that all changes are clearly documented. No warranty of any kind ** concerning any use which may be made of this software is offered or implied. ** */ #include <stdio.h> #include <sys/param.h> #include <sys/types.h> #include <sys/dir.h> #include "node.h" #include "config.h" extern char *Diag_cmd; char *htab_init(); /* ** there's only a few global variables, so we just declare them in here, ** rather than having a separate source file. */ NODE *RatList[MAXTYPE+1]; /* lists of nodes by type */ char *RatTab; /* hash table pointer */ int Verbosity; int Smask; int Hflag; int Zflag; main(argc,argv) int argc; char **argv; { char *rindex(); char *ptr; if ((Diag_cmd = rindex(*argv,'/')) == NULL) Diag_cmd = *argv; Zflag = Verbosity = 0; Smask = 0x1f; for (++argv; argc > 1; --argc,++argv) { /* ** not intended to handle multiple files. ** "normal" invocation is on the end of a pipe ** Allowing a file at all is simply a debugging aid. */ if (**argv != '-') { fprintf(stderr,"reading from %s\n",*argv); freopen(*argv,"r",stdin); continue; } switch(*(*argv+1)) { case 's': Smask = 0; for (ptr = *argv + 2; *ptr != '\0'; ++ptr) { switch(*ptr) { case 'd': Smask |= 1; break; case 'e': Smask |= 2; break; case 's': Smask |= 4; break; case 'm': Smask |= 8; break; case 'u': Smask |= 0x10; break; default: fatal("bad section - %c",*ptr); } } break; case 'r': Smask = 0x1f; for (ptr = *argv + 2; *ptr != '\0'; ++ptr) { switch(*ptr) { case 'd': Smask &= ~1; break; case 'e': Smask &= ~2; break; case 's': Smask &= ~4; break; case 'm': Smask &= ~8; break; case 'u': Smask &= ~0x10; break; default: fatal("bad section - %c",*ptr); } } break; case 'z': Zflag = 1 - Zflag; break; case 'v': Verbosity = atoi(*argv+2); break; default: fatal("bad argument - %s",*argv); } } if (Smask == 0x10 || Smask == 8 || Smask == 4 || Smask == 2 || Smask == 1) Hflag = 0; else Hflag = 1; if (Verbosity > 0) fprintf(stderr,"%s: ENTRY\n",Diag_cmd); rat_init(); an_read(); if (Verbosity > 0) fprintf(stderr,"%s: ANALYSIS\n",Diag_cmd); rat_analyze(); } /* ** to hash a key, we do a "normal" hash with the string, with the ** type added. This keeps us from generating a lot of collisions ** from having both a REF & a DEF for most symbols. */ static int hash_func(s,size) register char *s; int size; { register long rem; KEY *k; k = (KEY *) s; s = k->name; for (rem = k->type % size; *s != '\0'; ++s) rem = (rem*128 + (unsigned) *s) % size; return(rem); } /* ** key comparison - both name & type equal. */ static int key_compare(s1,s2) char *s1; char *s2; { if (((KEY *) s1)->type != ((KEY *) s2)->type) return (-1); return (strcmp(((KEY *) s1)->name, ((KEY *) s2)->name)); } static rat_init () { int i; i = next_prime(TABLE_SIZE); RatTab = htab_init(i,NULL,key_compare,hash_func); for (i=0; i < MAXTYPE+1; ++i) RatList[i] = NULL; } SHAR_EOF fi echo shar: "extracting 'analyze.c'" '(4217 characters)' if test -f 'analyze.c' then echo shar: "will not over-write existing file 'analyze.c'" else cat << \SHAR_EOF > 'analyze.c' /* ** ** Copyright (c) 1988, Robert L. McQueer ** All Rights Reserved ** ** Permission granted for use, modification and redistribution of this ** software provided that no use is made for commercial gain without the ** written consent of the author, that all copyright notices remain intact, ** and that all changes are clearly documented. No warranty of any kind ** concerning any use which may be made of this software is offered or implied. ** */ #include <stdio.h> #include "node.h" extern NODE *RatList[]; extern char *RatTab; extern char *strtok(); extern char *htab_find(); extern NODE *rat_list_sort(); extern int Verbosity; extern int Smask; extern int Hflag; rat_analyze() { /* fill in dependency & undef lists. */ if (Verbosity > 1) fprintf(stderr,"finding dependencies\n"); rat_dep_scan(); /* topological sort based on dependency */ if (Verbosity > 1) fprintf(stderr,"sorting dependencies\n"); rat_top_sort(); /* sort symbol DEF, UDEF, DDEF lists into alphabetical order */ if (Verbosity > 1) fprintf(stderr,"sorting symbol lists\n"); RatList[DEF] = rat_list_sort(RatList[DEF]); RatList[UDEF] = rat_list_sort(RatList[UDEF]); RatList[DDEF] = rat_list_sort(RatList[DDEF]); /* print results */ if (Smask & 3) fildep_sect(); if (Smask & 4) sym_sect(); if (Smask & 8) dd_sect(); if (Smask & 0x10) ud_sect(); } fildep_sect() { register NODE *ptr; register NODE *dp; if (Smask & 1) { if (Hflag) printf ("\f\n<FILE DEPENDENCIES / INCLUSION ORDER>\n\n"); for (ptr = RatList[FNAME]; ptr != NULL; ptr = ptr->next) { printf("%s:\n",ptr->key.name); for (dp = ptr->d.fname.dep; dp != NULL; dp = dp->d.dep.next) printf("\t%s (%s)\n", (dp->d.dep.dfile)->key.name, dp->d.dep.sym); } } /* ** find expanded dependency list by marking nodes, and using ** DFS. Lot of hacking through the list, but it's the file ** list, which is presumably short compared to lists of ** symbols & so on. */ if (Smask & 2) { if (Hflag) printf ("\f\n<EXPANDED DEPENDENCY LIST>\n\n"); for (ptr = RatList[CYCLE]; ptr != NULL; ptr = ptr->next) printf("CIRCULAR DEPENDENCIES: %s\n\n",ptr->d.cycle); for (ptr = RatList[FNAME]; ptr != NULL; ptr = ptr->next) { printf("%s:\n",ptr->key.name); for (dp = RatList[FNAME]; dp != NULL; dp = dp->next) dp->d.fname.mark = 0; ref_mark(ptr); for (dp = RatList[FNAME]; dp != NULL; dp = dp->next) if (dp->d.fname.mark && dp != ptr) printf("\t%s\n",dp->key.name); } } } /* ** recursive DFS to mark included files */ static ref_mark(n) NODE *n; { NODE *ptr; n->d.fname.mark = 1; for (ptr = n->d.fname.dep; ptr != NULL; ptr = ptr->d.dep.next) if (! ((ptr->d.dep.dfile)->d.fname.mark)) ref_mark(ptr->d.dep.dfile); } /* ** NOTE: sym_sect removes REF nodes from the hash table, in order ** to get at all the multiple entries. */ sym_sect() { register NODE *ptr; register NODE *rptr; KEY key; if (Hflag) printf ("\f\n<DEFINITIONS / REFERENCES BY SYMBOL>\n\n"); key.type = REF; for (ptr = RatList[DEF]; ptr != NULL; ptr = ptr->next) { key.name = ptr->key.name; printf("%s: %s\n",key.name,(ptr->d.file)->key.name); while ((rptr = (NODE *)htab_find(RatTab,(char *) &key)) != NULL) { if (rptr->d.file != ptr->d.file) printf("\t%s\n",(rptr->d.file)->key.name); htab_del(RatTab,(char *) &key); } } } dd_sect() { register NODE *ptr; register NODE *dptr; KEY key; if (Hflag) printf ("\f\n<DOUBLE DEFINITIONS>\n\n"); key.type = DEF; for (ptr = RatList[DDEF]; ptr != NULL; ptr = ptr->next) { key.name = ptr->key.name; dptr = (NODE *) htab_find(RatTab,(char *) &key); printf ("%s: %s %s\n",ptr->key.name, (dptr->d.file)->key.name, (ptr->d.file)->key.name); } } /* ** parses file names from UDEF node strings destructively */ ud_sect() { register NODE *ptr; char *wd; int cnt; if (Hflag) printf ("\f\n<UNDEFINED>\n\n"); for (ptr = RatList[UDEF]; ptr != NULL; ptr = ptr->next) { printf("%s:\n", ptr->key.name); cnt = 0; for (wd = strtok(ptr->d.ud.files," "); wd != NULL; wd = strtok(NULL," ")) { --cnt; printf("\t%s\n",wd); } if ((cnt += ptr->d.ud.count) > 0) printf("\t+%d more\n",cnt); } } SHAR_EOF fi echo shar: "extracting 'anread.c'" '(1377 characters)' if test -f 'anread.c' then echo shar: "will not over-write existing file 'anread.c'" else cat << \SHAR_EOF > 'anread.c' /* ** ** Copyright (c) 1988, Robert L. McQueer ** All Rights Reserved ** ** Permission granted for use, modification and redistribution of this ** software provided that no use is made for commercial gain without the ** written consent of the author, that all copyright notices remain intact, ** and that all changes are clearly documented. No warranty of any kind ** concerning any use which may be made of this software is offered or implied. ** */ #include <stdio.h> #include "config.h" char *strtok(); an_read() { char buf[BUFSIZ+1]; int incflag; char code; int fcount; char *dstr; fcount = incflag = 0; dstr = " \t\"\n"; while (fgets(buf,BUFSIZ,stdin) != NULL) { if (buf[0] != '@') continue; code = buf[1]; if (incflag) { switch(code) { case '<': fatal("nested @<"); case '>': incflag = 0; default: break; } continue; } switch(code) { case '=': ++fcount; rat_file(strtok(buf+2,dstr)); break; case '!': if (fcount <= 0) fatal("definition with no file"); rat_def_enter(strtok(buf+2,dstr)); break; case '?': if (fcount <= 0) fatal("reference with no file"); rat_ref_enter(strtok(buf+2,dstr)); break; case '<': incflag = 1; break; case '>': fatal("unmatched @>"); default: fatal("bad line - @%c",code); } } if (incflag) fatal("unclosed @<"); } SHAR_EOF fi echo shar: "extracting 'hat.c'" '(2265 characters)' if test -f 'hat.c' then echo shar: "will not over-write existing file 'hat.c'" else cat << \SHAR_EOF > 'hat.c' /* ** ** Copyright (c) 1988, Robert L. McQueer ** All Rights Reserved ** ** Permission granted for use, modification and redistribution of this ** software provided that no use is made for commercial gain without the ** written consent of the author, that all copyright notices remain intact, ** and that all changes are clearly documented. No warranty of any kind ** concerning any use which may be made of this software is offered or implied. ** */ #include <stdio.h> #include <sys/param.h> #include "config.h" /* ** localnames.h is generated by the makefile before compiling, and ** moved to lastnames.h afterwards. */ #include "localnames.h" main(argc,argv) int argc; char **argv; { char pipe[3*MAXPATHLEN+MAXCMDLEN+120]; char *cpp,cppopt[MAXCMDLEN]; char *p,popt[MAXCMDLEN]; char *a,aopt[MAXCMDLEN]; int verbosity; int xflag; aopt[0] = cppopt[0] = popt[0] = '\0'; cpp = cppopt; p = popt; a = aopt; xflag = 0; /* ** Note that we preserve the order of the files & parser options ** It is legal in the parser to turn options on and off between ** files. */ verbosity = 0; for (++argv; argc > 1; --argc,++argv) { if (**argv == '-') { switch(*(*argv+1)) { case 's': case 'z': case 'r': sprintf(a,"%s ",*argv); a += strlen(a); break; case 'q': case 'i': case 'f': case 'p': case 'a': case 'c': sprintf(p,"%s ",*argv); p += strlen(p); break; case 'v': if (*(*argv+2) != '\0') verbosity = atoi(*argv+2); else verbosity = 1; if (verbosity < 0) { verbosity *= -1; sprintf(a,"-v%d ",verbosity); a += strlen(a); } else { sprintf(p,"-v%d ",verbosity); p += strlen(p); } break; case 'x': xflag = 1; break; default: sprintf(cpp,"%s ",*argv); cpp += strlen(cpp); break; } } else { sprintf(p,"%s ",*argv); p += strlen(p); } } if (xflag) sprintf(pipe,"%s/%s -x %s|%s/%s %s", HATDIR,PARSER,popt,HATDIR,ANALYZER,aopt); else sprintf(pipe,"%s/%s %s|%s %s|%s/%s %s", HATDIR,PARSER,popt,CPPCMD,cppopt,HATDIR,ANALYZER,aopt); if (verbosity > 0) fprintf(stderr,"exec: %s\n",pipe); execl(SHELLCMD,SHELLCMD,"-c",pipe,NULL); fprintf(stderr,"EXECL RETURNED\n"); } SHAR_EOF fi echo shar: "extracting 'keycheck.c'" '(3157 characters)' if test -f 'keycheck.c' then echo shar: "will not over-write existing file 'keycheck.c'" else cat << \SHAR_EOF > 'keycheck.c' /* ** ** Copyright (c) 1988, Robert L. McQueer ** All Rights Reserved ** ** Permission granted for use, modification and redistribution of this ** software provided that no use is made for commercial gain without the ** written consent of the author, that all copyright notices remain intact, ** and that all changes are clearly documented. No warranty of any kind ** concerning any use which may be made of this software is offered or implied. ** */ #include <stdio.h> #include "config.h" #include "y.tab.h" static char *Ktab = NULL; char *htab_init(); char *htab_find(); typedef struct { char *word; int tok; } KTAB_ENTRY; /* ** this table controls recognition of C language keywords. Except ** for a few, it really divides them into 4 rough classes, which is ** all the parser cares about: ** ** NTYPE - can only appear as the terminating end of a datatype. ** ADJ - can appear either as the terminating end of a datatype, ** or as an adjective modifying a datatype. ** STCLASS - storage classes and anything else which can modify ** a datatype, but not terminate it. ** KEYWORD - any other keyword. ** ** Datatype includes things like "void" only applicable to functions ** so that function pointers are recognized. ** ** Things not recognized by all compilers should be #ifdef'ed with ** USEXXX. Most compilers / OS's generate some symbol to allow ** you to recognize them. Use those directly underneath to define ** the right USEXXX's. You can also assign sets to be used explicitly ** from -D options. */ /* ** CCEXTRAKEYS picks up some supposed reserved words which are often ** ignored by compilers */ #ifdef CCEXTRAKEYS #define USECONST #define USEVOLATILE #define USEENTRY #endif /* ** for void, we require you to set something to turn it OFF */ #ifndef CCNOVOID #define USEVOID #endif #ifdef vms #define USEGLOBAL #endif KTAB_ENTRY Kt[] = { { "typedef", TYPEDEF }, { "extern", EXTERN }, { "struct", STRUCT }, { "union", STRUCT }, /* same as a struct for our purposes */ { "enum", ENUM }, #ifdef USEVOID { "void", NTYPE}, #endif { "int", NTYPE }, { "float", NTYPE }, { "char", NTYPE }, { "double", NTYPE}, { "unsigned", ADJ}, { "signed", ADJ}, { "short", ADJ}, { "long", ADJ}, { "register", STCLASS}, { "auto", STCLASS}, { "static", STCLASS}, #ifdef USEGLOBAL { "GLOBALDEF", STCLASS}, { "globaldef", STCLASS}, { "GLOBALREF", STCLASS}, { "globalref", STCLASS}, #endif #ifdef USECONST { "const", STCLASS}, #endif #ifdef USEVOLATILE { "volatile", STCLASS}, #endif { "goto", KEYWORD }, { "return", KEYWORD }, { "sizeof", KEYWORD }, { "break", KEYWORD }, { "continue", KEYWORD }, { "if", KEYWORD }, { "else", KEYWORD }, { "for", KEYWORD }, { "do", KEYWORD }, { "while", KEYWORD }, { "switch", KEYWORD }, { "case", KEYWORD }, #ifdef USEENTRY { "entry", KEYWORD }, #endif { "default", KEYWORD } }; kt_init() { int i; Ktab = htab_init(SMALL_TABLE,NULL,NULL,NULL); for (i=0; i < sizeof(Kt)/sizeof(Kt[0]); ++i) htab_enter(Ktab, Kt[i].word, (char *) &(Kt[i].tok)); } keycheck(s) char *s; { char *dat; if ((dat = htab_find(Ktab,s)) != NULL) return (*((int *) dat)); return (WORD); } SHAR_EOF fi echo shar: "extracting 'listsort.c'" '(1590 characters)' if test -f 'listsort.c' then echo shar: "will not over-write existing file 'listsort.c'" else cat << \SHAR_EOF > 'listsort.c' /* ** ** Copyright (c) 1988, Robert L. McQueer ** All Rights Reserved ** ** Permission granted for use, modification and redistribution of this ** software provided that no use is made for commercial gain without the ** written consent of the author, that all copyright notices remain intact, ** and that all changes are clearly documented. No warranty of any kind ** concerning any use which may be made of this software is offered or implied. ** */ #include <stdio.h> #include "node.h" extern int Verbosity; NODE * rat_list_sort(list) NODE *list; { register NODE *ptr; register int elt,i; NODE **arr; char *malloc(); int compar(); if (list == NULL) return(NULL); elt = 0; for (ptr = list; ptr != NULL; ptr = ptr->next) ++elt; if (Verbosity > 3) { fprintf(stderr,"Original order:\n"); for (ptr = list; ptr != NULL; ptr = ptr->next) fprintf(stderr," %s\n",ptr->key.name); } if ((arr = (NODE **) malloc(elt * sizeof(NODE *))) == NULL) fatal("Can't alloc array for sorting"); i = 0; for (ptr = list; ptr != NULL; ptr = ptr->next) { arr[i] = ptr; ++i; } qsort((char *) arr,elt,sizeof(NODE *),compar); --elt; for (list=ptr=arr[i=0]; i < elt; ++i) { ptr->next = arr[i+1]; ptr = ptr->next; } ptr->next = NULL; free((char *) arr); if (Verbosity > 3) { fprintf(stderr,"End order:\n"); for (ptr = list; ptr != NULL; ptr = ptr->next) fprintf(stderr," %s\n",ptr->key.name); } return(list); } static compar(s1,s2) register char *s1; register char *s2; { return (strcmp((*((NODE **)s1))->key.name,(*((NODE **)s2))->key.name)); } SHAR_EOF fi echo shar: "extracting 'pmain.c'" '(2944 characters)' if test -f 'pmain.c' then echo shar: "will not over-write existing file 'pmain.c'" else cat << \SHAR_EOF > 'pmain.c' /* ** ** Copyright (c) 1988, Robert L. McQueer ** All Rights Reserved ** ** Permission granted for use, modification and redistribution of this ** software provided that no use is made for commercial gain without the ** written consent of the author, that all copyright notices remain intact, ** and that all changes are clearly documented. No warranty of any kind ** concerning any use which may be made of this software is offered or implied. ** */ #include <stdio.h> #include <sys/param.h> #include <sys/types.h> #include <sys/dir.h> #include "config.h" extern char *Diag_cmd; extern FILE *yyin; char *htab_init(); int Qflag; int Iflag; int Verbosity; int Xflag; int Cflag; int Aflag; char *Ftab; char Fextra[CATBUFFER]; main(argc,argv) int argc; char **argv; { char *fex; Diag_cmd = *argv; kt_init(); Cflag = Aflag = Xflag = Iflag = Qflag = Verbosity = 0; Ftab = NULL; fex = Fextra; for (--argc; argc > 0; --argc) { ++argv; if (**argv == '-') { ++(*argv); switch(**argv) { case 'q': Qflag = 1 - Qflag; break; case 'i': Iflag = 1 - Iflag; break; case 'a': if (Ftab == NULL) Ftab = htab_init(SMALL_TABLE, NULL,NULL,NULL); Aflag = 1 - Aflag; break; case 'x': Xflag = 1; break; case 'p': switch((*argv)[1]) { case '-': *argv += 2; sprintf(fex,"#undef %s\n",*argv); break; case '+': ++(*argv); /* fall through */ default: ++(*argv); sprintf(fex,"#define %s\n",*argv); break; } fex += strlen(fex); break; case 'c': Cflag = 1; if (Ftab == NULL) Ftab = htab_init(SMALL_TABLE, NULL,NULL,NULL); /* ** yes, modifying the command line strings ** Probably shouldn't do that, but ** we aren't changing the length, just ** replacing characters. */ switch((*argv)[1]) { case '-': ++(*argv); **argv = '+'; htab_del(Ftab,*argv); **argv = '-'; htab_enter(Ftab,*argv,*argv); break; case '.': ++(*argv); **argv = '+'; htab_del(Ftab,*argv); **argv = '-'; htab_del(Ftab,*argv); ++(*argv); break; case '+': ++(*argv); /* fall through */ default: **argv = '-'; htab_del(Ftab,*argv); **argv = '+'; htab_enter(Ftab,*argv,*argv); break; } break; case 'f': ++(*argv); if (Ftab == NULL) Ftab = htab_init(SMALL_TABLE, NULL,NULL,NULL); if (htab_del(Ftab,*argv) < 0) htab_enter(Ftab,*argv,*argv); break; case 'v': ++(*argv); Verbosity = atoi(*argv); break; default: fatal("bad option: %s",*argv); exit(1); } } else { if (Verbosity > 0) printf("Scanning file %s .....\n",*argv); if ((yyin = fopen(*argv,"r")) == NULL) { fprintf(stderr,"Cannot open %s\n",*argv); continue; } init_lex(*argv); yyparse(); fclose(yyin); } } } SHAR_EOF fi echo shar: "extracting 'table.c'" '(6398 characters)' if test -f 'table.c' then echo shar: "will not over-write existing file 'table.c'" else cat << \SHAR_EOF > 'table.c' /* ** ** Copyright (c) 1988, Robert L. McQueer ** All Rights Reserved ** ** Permission granted for use, modification and redistribution of this ** software provided that no use is made for commercial gain without the ** written consent of the author, that all copyright notices remain intact, ** and that all changes are clearly documented. No warranty of any kind ** concerning any use which may be made of this software is offered or implied. ** */ #include <stdio.h> #include <sys/param.h> #include "node.h" #include "config.h" extern char *htab_find(); extern char *str_store(); extern NODE *RatList[]; extern char *RatTab; extern int Verbosity; NODE *tab_enter(); static NODE *Curfile; static NODE *Avail = NULL; static int Avnum = 0; /* ** enter a symbol definition into the table. If already there, enter ** it as a DDEF. */ rat_def_enter(s) char *s; { KEY key; if (s == NULL) return; key.name = s; key.type = DEF; if (htab_find(RatTab,(char *) &key) != NULL) key.type = DDEF; if (Verbosity > 1) { if (key.type == DDEF) fprintf(stderr,"enter DOUBLEDEF: %s\n",s); else fprintf(stderr,"enter DEF: %s\n",s); } (tab_enter(s,key.type))->d.file = Curfile; } /* ** enter a symbol reference into the table. ** ** NOTE: this routine depends on the way htab_find handles multiple ** entries - MOST RECENT entry will be returned. This is used ** to prevent multiple entries for one file. */ rat_ref_enter(s) char *s; { NODE *ptr; KEY key; if (s == NULL) return; key.name = s; key.type = REF; ptr = (NODE *) htab_find(RatTab,(char *) &key); if (ptr == NULL || ptr->d.file != Curfile) { if (Verbosity > 1) { if (ptr == NULL) fprintf(stderr,"enter NEWREF: %s\n",s); else fprintf(stderr,"enter OLDREF(%s): %s\n", (ptr->d.file)->key.name,s); } ptr = tab_enter(s,REF); ptr->d.file = Curfile; } else { if (Verbosity > 2) fprintf(stderr,"MULTREF: %s\n",s); } } /* ** new file. Sets Curfile as well as entering new file into table. ** until another call to this routine, all Ref's & Def's will be from ** this file. */ rat_file(s) char *s; { Curfile = tab_enter(s,FNAME); if (Verbosity > 0) fprintf(stderr,"FILE: %s\n",s); } /* ** rat_dep_scan is called after all files are entered, and runs down the list ** of symbol references, finding their definitions. If a definition is found, ** a file dependency is noted. If not, an undef is noted. ** ** Sets up the file dependancy / refcount / circle information ** for later use by topological sort. */ rat_dep_scan() { register NODE *ref,*def,*ptr; KEY key; int i; char *str; char name[CATBUFFER < 2*MAXPATHLEN+3 ? 2*MAXPATHLEN+3 : CATBUFFER]; for (ptr = RatList[FNAME]; ptr != NULL; ptr = ptr->next) { ptr->d.fname.dep = NULL; ptr->d.fname.refcount = 0; } for (ref = RatList[REF]; ref != NULL; ref = ref->next) { key.name = ref->key.name; key.type = DEF; /* ** if DEF node exists, we have a dependency */ if ((def = (NODE *) htab_find(RatTab,(char *) &key)) != NULL) { if (Verbosity > 2) fprintf(stderr,"CHECKREF_DEF: %s(%s,%s)\n", key.name, (ref->d.file)->key.name, (def->d.file)->key.name); /* forget about depending on ourselves */ if (def->d.file == ref->d.file) continue; /* ** make a key from the two names, and continue ** if the dependency already exists. The key ** contains "illegal" characters to avoid problems ** arising from different names concatenating into ** the same string. Since the first part is a ** filename which can contain anything, this can ** still break in theory, but only truly perverse ** filenames would cause problems. */ sprintf(name,")%s$%s",(ref->d.file)->key.name, (def->d.file)->key.name); key.name = name; key.type = DEP; if (htab_find(RatTab,(char *) &key) != NULL) continue; /* ** new dependency. Chain the dep node onto the ** referring files dep list, bump the reffering ** file's reference count. */ if (Verbosity > 1) fprintf(stderr,"DEPEND: %s\n",name); ptr = tab_enter(name,DEP); ptr->d.dep.sym = ref->key.name; ptr->d.dep.dfile = def->d.file; ptr->d.dep.rfile = ref->d.file; ptr->d.dep.next = (ref->d.file)->d.fname.dep; (ref->d.file)->d.fname.dep = ptr; ++((ref->d.file)->d.fname.refcount); continue; } /* ** not defined. If undef node already exists, concatenate ** new file onto descriptor string, otherwise make new node. ** This wastes string storage somewhat, but WHOGAS. */ key.type = UDEF; if ((ptr = (NODE *) htab_find(RatTab,(char *) &key)) != NULL) { if (Verbosity > 2) fprintf(stderr,"OLD_UNDEF: %s(%s)\n", key.name,name); ++(ptr->d.ud.count); str = (ref->d.file)->key.name; i = strlen(ptr->d.ud.files) + strlen(str) + 1; if (i < CATBUFFER) { sprintf(name,"%s %s",ptr->d.ud.files,str); ptr->d.ud.files = str_store(name); } continue; } if (Verbosity > 1) fprintf(stderr,"NEW_UNDEF: %s(%s)\n",key.name, (ref->d.file)->key.name); ptr = tab_enter(key.name,UDEF); ptr->d.ud.files = (ref->d.file)->key.name; ptr->d.ud.count = 1; } } static int Ckey = 0; /* ** enter a cycle into the hash table - we really only need the ** list of the things, but this avoids bothering with a different ** mechanism. We don't use the cycle itself as the key to avoid ** hashing huge strings needlessly. Entry is made by topological ** sort, which detects cycles. */ new_cycle(s) char *s; { char kbuf[12]; sprintf(kbuf,"%x",Ckey++); (tab_enter(kbuf,CYCLE))->d.cycle = str_store(s); } /* ** new entry into hash table, allocating a node and a permanent copy of ** the key string. Also builds the RatList[] array of entries of the various ** types as it goes. Returns node pointer, so caller may fill in type ** specific information. */ static NODE * tab_enter(str,type) char *str; unsigned type; { NODE *ptr; if (type > MAXTYPE) fatal("prog. err - table entry with type = %d",type); if (Avnum <= 0) { Avnum = NODE_BLOCK; if ((Avail = (NODE *) malloc(NODE_BLOCK*sizeof(NODE))) == NULL) fatal("can't allocate memory for table nodes"); } ptr = Avail; ++Avail; --Avnum; ptr->next = RatList[type]; RatList[type] = ptr; ptr->key.name = str_store(str); ptr->key.type = type; htab_enter(RatTab, (char *) &(ptr->key), (char *) ptr); return(ptr); } SHAR_EOF fi echo shar: "extracting 'topsort.c'" '(7201 characters)' if test -f 'topsort.c' then echo shar: "will not over-write existing file 'topsort.c'" else cat << \SHAR_EOF > 'topsort.c' /* ** ** Copyright (c) 1988, Robert L. McQueer ** All Rights Reserved ** ** Permission granted for use, modification and redistribution of this ** software provided that no use is made for commercial gain without the ** written consent of the author, that all copyright notices remain intact, ** and that all changes are clearly documented. No warranty of any kind ** concerning any use which may be made of this software is offered or implied. ** */ #include <stdio.h> #include "node.h" #include "config.h" extern NODE *RatList[]; extern int Verbosity; extern int Zflag; NODE *path_find(); /* ** topological sort. This destroys the refcounts, which are assumed ** at this point to accurately reflect the DEP records. The sense of the ** sort is that files containing a definition come before their ** dependent files, ie. the inclusion order for the files. If you ** want to consider arrows drawn from referring file to defining file, ** this is a "backwards" sort, finding the terminal nodes first - of ** course, if you want to draw the arrows the other direction, you ** are finding the originating nodes first, but then you have "backwards" ** arrows :-). ** ** once you follow out the conventions for the data structures involved ** this is pretty much the textbook standard topological sort - find ** a node with no successors (predecessors, if you want to draw the ** arrows the other way), that's the next node. Decrement successor ** (predecessor) counts on all its predecessors (successors), and iterate. ** Failure to find a node indicates circularity. ** ** Circular references are resolved by finding a cycle, arbitrarily ** choosing one of its nodes, and zapping one of the dependencies ** from consideration for future cycle detection. I THINK the set ** of cycles we wind up with is a fundamental set. */ rat_top_sort() { NODE *flist, *tail, *ptr, *pred, *pp; char bufr[CATBUFFER+40]; /* see path_find() */ /* ** list is reverse of user's original order - re-reverse, ** unless z-option was used (we'll reverse at end in that case) ** Basically, we want the sort to reflect the user's order ** as closely as possible. */ if (!Zflag) { flist = NULL; for (pp = RatList[FNAME]; pp != NULL; pp = ptr) { ptr = pp->next; pp->next = flist; flist = pp; } RatList[FNAME] = flist; } /* clear all the edge marks */ for (pp = RatList[DEP]; pp != NULL; pp = pp->next) pp->d.dep.erase = 0; /* ** we will build up the sorted list on flist, removing them from ** RatList[FNAME] as we go. */ tail = flist = NULL; while (RatList[FNAME] != NULL) { /* ** find an item with no references. As long as there ** are no circular references, there should be one */ pred = NULL; for (ptr = RatList[FNAME]; ptr != NULL; ptr = ptr->next) { if (ptr->d.fname.refcount == 0) break; pred = ptr; } /* ** if no zero refcounts, find a cyclical reference, ie. ** a node with a path back to itself, traversing entirely ** nodes with non-zero refcounts. Then arbitrarily use ** that node. */ if (ptr == NULL) { if (Verbosity > 2) fprintf(stderr, "NO UNREF'ED files - finding a cycle\n"); pred = NULL; for (ptr = RatList[FNAME]; ptr != NULL; ptr = ptr->next) { if ((pp = path_find(ptr,ptr,bufr,0)) != NULL) break; pred = ptr; } if (ptr == NULL) fatal("logic error - topological sort"); /* enter a cycle */ new_cycle(bufr); /* ** this is tricky - we'll arbitrarily use this node, ** but we have to take care with marks. path_find ** passes back the last edge in the cycle - we mark ** the edge to exclude it from future cycle detections. ** The path is constructed in such a way that this ** edge represents a file which depends upon ptr - ** its refcount will be taken care of below. ptr ** will still have a positive refcount, even though ** we are removing it from the list. This will be ** cleared out when we pick up the appropriate ** neighbor in the cycle - note that we have to very ** careful because we may have lots of overlapping ** cycles, and we don't want to pick up the same one ** over again. */ pp->d.dep.erase = 1; if (Verbosity > 2) fprintf(stderr,"cycle edge: ref %s, def %s\n", (pp->d.dep.rfile)->key.name, (pp->d.dep.dfile)->key.name); } /* take off RatList */ if (pred == NULL) { RatList[FNAME] = ptr->next; if (Verbosity > 2) fprintf(stderr,"found list head: %s\n", ptr->key.name); } else { pred->next = ptr->next; if (Verbosity > 2) fprintf(stderr,"found %s after %s\n", ptr->key.name,pred->key.name); } if (flist == NULL) flist = ptr; else tail->next = ptr; ptr->next = NULL; tail = ptr; /* ** run down the list of dependencies (our "edge-list", really) ** and decrement the refcount of all nodes referring to ** this one */ for (pred = RatList[DEP]; pred != NULL; pred = pred->next) { if (pred->d.dep.dfile != ptr) continue; if (Verbosity > 3) fprintf(stderr,"decrement %s ref count\n", (pred->d.dep.rfile)->key.name); --((pred->d.dep.rfile)->d.fname.refcount); } } /* replace list with sorted one */ RatList[FNAME] = flist; /* for -z option, reverse the list */ if (Zflag) { flist = NULL; for (pp = RatList[FNAME]; pp != NULL; pp = ptr) { ptr = pp->next; pp->next = flist; flist = pp; } RatList[FNAME] = flist; } } /* ** path_find routine is a recursive DFS to find a path. Used only to ** find cycles. Returns NULL if no path, fills in bufr with path if there ** is one. Pointer returned is DEP node for final path edge. Top level ** call should have count = 0, flagging top entry. */ static NODE * path_find(from,to,buf,count) NODE *from; NODE *to; char *buf; int count; { NODE *ptr, *p2; char *str; int len; /* on top-level call, initialize marks, put "from" in buffer */ if (count <= 0) { for (ptr = RatList[FNAME]; ptr != NULL; ptr = ptr->next) ptr->d.fname.mark = 0; strcpy(buf,from->key.name); buf += (count = strlen(buf)); } /* for space character, and to assure positive */ ++count; /* mark that we've been here */ from->d.fname.mark = 1; /* ** we WILL look for a direct path first ** - IGNORE mark because original from may = to, and has ** already been marked */ for (ptr = from->d.fname.dep; ptr != NULL; ptr = ptr->d.dep.next) { /* if "erased" edge, ignore */ if (ptr->d.dep.erase) continue; if (ptr->d.dep.dfile == to) { if ((count += strlen(to->key.name)) > CATBUFFER) strcpy(buf," ...."); else sprintf(buf," %s",to->key.name); return (ptr); } } /* USE mark on recursive call */ for (ptr = from->d.fname.dep; ptr != NULL; ptr = ptr->d.dep.next) { /* if "erased" edge, ignore */ if (ptr->d.dep.erase) continue; /* if visited node, ignore */ if ((ptr->d.dep.dfile)->d.fname.mark) continue; str = (ptr->d.dep.dfile)->key.name; len = strlen(str); if ((count += len) < CATBUFFER) sprintf(buf," %s",str); p2 = path_find(ptr->d.dep.dfile, to, buf+len+1, count); if (p2 != NULL) return(p2); count -= len; } return(NULL); } SHAR_EOF fi echo shar: "extracting 'config.h'" '(1276 characters)' if test -f 'config.h' then echo shar: "will not over-write existing file 'config.h'" else cat << \SHAR_EOF > 'config.h' /* ** size of hash tables ** ** TABLE_SIZE refers to analysis program, and will contain entries ** for every symbol reference, definition, file, etc. - It can ** potentially contain a great many entries. ** ** SMALL_TABLE is for three tables used by the parser - language keywords, ** -f/-c options, and the symbols referenced by a single macro respectively. ** None expected to require a huge number of entries. ** ** These sizes DO NOT affect how many entries may be made to the tables - ** they are a linked list arrangement allowed to be >100% density. ** ** actual table sizes will be adjusted upwards to a prime number. */ #define TABLE_SIZE 4000 #define SMALL_TABLE 60 /* ** hash table node allocation block for the analysis program. */ #define NODE_BLOCK 200 /* ** buffer size for strings containing lists of files, and lists ** of #define's and #undef's for -p options */ #define CATBUFFER 4800 /* ** couple things which ought to be defined in stdio.h and sys/params.h. ** In case they aren't */ #ifndef MAXPATHLEN #define MAXPATHLEN 240 #endif #ifndef BUFSIZ #define BUFSIZ 1024 #endif /* ** longest command line possible using your favorite shell(s) ** Used to allocate buffers for strings constructed from command line ** arguments */ #define MAXCMDLEN 4096 SHAR_EOF fi echo shar: "extracting 'node.h'" '(865 characters)' if test -f 'node.h' then echo shar: "will not over-write existing file 'node.h'" else cat << \SHAR_EOF > 'node.h' #define REF 1 #define DEF 2 #define FNAME 3 #define DEP 4 #define DDEF 5 #define UDEF 6 #define CYCLE 7 #define MAXTYPE 7 /* maximum of above node types */ typedef struct { char *name; int type; } KEY; typedef struct _nd_s { struct _nd_s *next; KEY key; union { struct _nd_s *file; /* file for DEF, DDEF, REF, UREF */ char *cycle; struct { struct _nd_s *dep; /* FNAME dependency list */ int refcount; /* refcount for use in sort */ int mark; /* mark for DFS's */ } fname; struct { struct _nd_s *dfile; /* defining file */ struct _nd_s *rfile; /* referring file */ struct _nd_s *next; /* next list element */ char *sym; /* symbol causing dependency */ int erase; /* erase edge (cyclic) */ } dep; struct { char *files; /* up to MAXCATFILE */ int count; /* actual number of files */ } ud; } d; } NODE; SHAR_EOF fi echo shar: "extracting 'stdio.h'" '(397 characters)' if test -f 'stdio.h' then echo shar: "will not over-write existing file 'stdio.h'" else cat << \SHAR_EOF > 'stdio.h' /* ** Little trick to get token codes into lex. lex.yy.c includes "stdio.h". ** in here we define everything needed that can't be indented ahead of the ** lex script %%, and pick up the "real" stdio.h via <stdio.h> */ #include <stdio.h> #include "y.tab.h" #include "config.h" #define MYPUTS(S) if (Outflag) fputs(S,stdout) #define SQRET(X) if (!Squelch) return(Verbosity > 4 ? tok_out(X) : X) SHAR_EOF fi exit 0 # End of shell archive