rsalz@uunet.uu.net (Rich Salz) (03/23/89)
Submitted-by: Bob McQueer <mtxinu!rtech!weevil!bobm> Posting-number: Volume 18, Issue 53 Archive-name: hat-n-coat/part02 #! /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 export PATH; PATH=/bin:/usr/bin:$PATH echo shar: "extracting 'amain.c'" '(3494 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; rat_init(); 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; case 'n': rat_forget(*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); 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'" '(4245 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(); } static 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. */ static 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); } } } static 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 */ static 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'" '(2278 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': case 'n': sprintf(a,"%s ",*argv); a += strlen(a); break; case 'q': case 'i': case 'p': case 'a': case 'c': case 'f': 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'" '(3164 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 static 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'" '(6721 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 = FORGET; if (htab_find(RatTab,(char *) &key) != NULL) return; 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 = FORGET; if (htab_find(RatTab,(char *) &key) != NULL) return; 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); } /* ** Forget symbol. we really don't need the list of these - only ** the fact that a "forget" has been entered. */ rat_forget(s) char *s; { tab_enter(s,FORGET); } /* ** 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'" '(7343 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 *str1; char *str2; 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) { str1 = to->key.name; str2 = ptr->d.dep.sym; len = strlen(str1) + strlen(str2) + 4; if ((count += len) > CATBUFFER) strcpy(buf," ...."); else sprintf(buf," (%s) %s",str2,str1); 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; str1 = (ptr->d.dep.dfile)->key.name; str2 = ptr->d.dep.sym; len = strlen(str1)+strlen(str2)+4; if ((count += len) < CATBUFFER) sprintf(buf," (%s) %s",str2,str1); p2 = path_find(ptr->d.dep.dfile, to, buf+len, count); if (p2 != NULL) return(p2); count -= len; } return(NULL); } SHAR_EOF fi exit 0 # End of shell archive -- Please send comp.sources.unix-related mail to rsalz@uunet.uu.net.