hat/coat dependency analysis tools, 2 of 2
Bob Mcqueer
bobm at rtech.UUCP
Sun Mar 27 04:36:21 AEST 1988
-------------
#! /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
More information about the Alt.sources
mailing list