Relay-Version: version B 2.10 5/3/83; site utzoo.UUCP
Posting-Version: version B 2.10.1 6/24/83 (MC840302); site enea.UUCP
Path: utzoo!watmath!clyde!burl!ulysses!allegra!mit-eddie!genrad!panda!talcott!harvard!seismo!mcvax!enea!kim
From: kim@enea.UUCP (Kim Walden)
Newsgroups: net.sources
Subject: make depend (part 2 of 3)
Message-ID: <855@enea.UUCP>
Date: Wed, 10-Apr-85 14:00:40 EST
Article-I.D.: enea.855
Posted: Wed Apr 10 14:00:40 1985
Date-Received: Sat, 13-Apr-85 05:16:14 EST
Reply-To: kim@enea.UUCP (Kim Walden)
Distribution: net
Organization: ENEA DATA, Sweden
Lines: 1452

#	This is a shell archive.
#	Remove everything above and including the cut line.
#	Then run the rest of the file through sh.
#----cut here-----cut here-----cut here-----cut here-----
#!/bin/sh
# shar:	Shell Archiver
#	Run the following text with /bin/sh to create:
#	tool
# This archive created: Wed Apr 10 14:06:20 1985
mkdir tool
chdir tool
sed 's/^XX//' << \SHAR_EOF > READ_ME
XX*******************************************************************
XX**                                                               **
XX**  This distribution implements the algorithm described in      **
XX**                                                               **
XX**      K. Walden, "Automatic Generation of Make Dependencies",  **
XX**      Softw. Practice & Exper., vol. 14, no. 6, June 1984      **
XX**                                                               **
XX**  Copyright (c) 1983  Kim Walden                               **
XX**      ENEA DATA, Sweden and                                    **
XX**      SYSLAB, Department of Computer Science,                  **
XX**      University of Stockholm, Sweden.                         **
XX**                                                               **
XX**  The software may be used and copied freely,                  **
XX**      provided that proper credit is given to the originator   **
XX**      by including this text label in each copy.               **
XX**                                                               **
XX*******************************************************************
XX
XX
XX
XXSOURCES			FUNCTION
XX
XXMakefile		Make script to build the programs.
XXmakedep.c		Main program for extracting include statements
XX			and pipe them to makenorm and depend.
XXmakenorm.y		Include statement normalizer.
XXnormscan.l		Scanner for the normalizer.
XXdepend.y		Main dependency generator.
XXdepscan.l		Scanner for the dependency generator.
XXmpath.c			File name path reduction routine.
XXerror.c			Error handling routine.
XX
XXman			Manuals subdirectory
XXtest			Subdirectory structure with test files.
XX
XX
XX
XX
XXThe programs should be built invoking the Makefile, and the tool
XXdirectory added to the command search path, so the programs can be
XXfound when running the test below.
XX
XXWhen make is invoked on the test directory test/proc, the test
XXexample in the above SP & E paper is run, and the output should be
XXthe same as the contents of the file Dep.mk.
XX
XXMakedep and makenorm extract and normalize include statements that
XXare directed to the C preprocessor.
XXThese programs must be modified if include statements of other
XXlanguages are to be handled, unless the include syntax and semantics
XXhappen to be the same, while depend can be used unchanged.
XX
XXA general recommendation for Berkeley UNIX users is to get hold of
XXthe augmented version of make available under AT & T System III/V,
XXwhich has an include facility.
XXAll generated dependencies can then be put in a separate file,
XXwhich is made part of the ordinary make dependency graph.
XX
XXPorting the augmented make to run under Berkeley UNIX is not very
XXdifficult, and mostly has to do with different formats of archive
XXfiles.
SHAR_EOF
if test 2713 -ne "`wc -c READ_ME`"
then
echo shar: error transmitting READ_ME '(should have been 2713 characters)'
fi
sed 's/^XX//' << \SHAR_EOF > Makefile
XXCFLAGS= -O -s
XX
XXOBJ1= mpath.o 
XXOBJ2= error.o
XX
XXall: makedep makenorm depend 
XX
XXmakedep: makedep.o $(OBJ2)
XX	$(CC) $(CFLAGS) $@.o $(OBJ2) -o $@
XX
XXmakenorm: makenorm.o $(OBJ1) $(OBJ2)
XX	$(CC) $(CFLAGS) $@.o $(OBJ1) $(OBJ2) -ll -o $@
XX
XXdepend: depend.o $(OBJ2)
XX	$(CC) $(CFLAGS) $@.o $(OBJ2) -ll -o $@
XX
XXmakenorm.o: normscan.c
XXdepend.o: depscan.c
XX
XXclean:
XX	rm *.o
XX	rm makedep
XX	rm makenorm makenorm.c normscan.c
XX	rm depend depend.c depscan.c
XX	rm man/*.man
XX
XX.y.o:
XX	$(YACC) $(YFLAGS) $<
XX	@mv -f y.tab.c $*.c
XX	$(CC) $(CFLAGS) -c $*.c
XX
XX.y.c:
XX	$(YACC) $(YFLAGS) $<
XX	@mv -f y.tab.c $@
XX
XX.l.o:
XX	$(LEX) $(LFLAGS) $<
XX	@mv -f lex.yy.c $*.c
XX	$(CC) $(CFLAGS) -c $*.c
XX
XX.l.c:
XX	$(LEX) $(LFLAGS) $<
XX	@mv -f lex.yy.c $@
SHAR_EOF
if test 688 -ne "`wc -c Makefile`"
then
echo shar: error transmitting Makefile '(should have been 688 characters)'
fi
sed 's/^XX//' << \SHAR_EOF > depend.y
XX%{
XX/* -- Make include dependency generator
XX *
XX * $File: depend.y  1.13  1985-03-29  14:06:29 $
XX *
XX *  Copyright (c) 1983  Kim Walden
XX *      ENEA DATA, Sweden and    
XX *      SYSLAB, Department of Computer Science,
XX *      University of Stockholm, Sweden.
XX *
XX *	This software may be used and copied freely,
XX *	provided that proper credit is given to the originator
XX *	by including the above text in each copy.
XX *
XX *	Descr:	This program implements part of the algorithm described in
XX *      	K. Walden, "Automatic Generation of Make Dependencies",
XX *      	Softw. Practice & Exper., vol. 14, no. 6, June 1984 
XX *
XX * $Log:	depend.y,v $
XX * 
XX * Revision 1.13  1985-03-29  14:06:29  kim
XX * New source format
XX * 
XX * Revision 1.12  1985-03-08  01:16:37  kim
XX * Added support for parallell transfer rules.
XX * Added -1 option to makedep and depend.
XX * 
XX * Revision 1.11  1985-02-25  19:40:21  kim
XX * Path reduction moved to earlier stage
XX * 
XX * Revision 1.10  1985-02-19  11:19:59  kim
XX * New default include rules
XX * 
XX * Revision 1.9  1985-02-18  14:23:55  kim
XX * New error handling
XX * 
XX * Revision 1.8  1985-02-14  13:59:52  kim
XX * Changed rules options to -r/-R
XX * 
XX * Revision 1.7  1985-02-14  01:53:19  kim
XX * Converted to RCS format
XX * 
XX * Revision 1.4  1983-10-06  19:50:16  kim
XX * Allow empty include line input
XX * 
XX * Revision 1.3  1983-07-20  19:50:00  kim
XX * Closer to algorithm in SYSLAB Report No. 19 (June 1983)
XX * 
XX * Revision 1.2  1983-02-22  19:49:51  kim
XX * First version with include rules
XX * 
XX * Revision 1.1  1982-12-15  19:49:47  kim
XX * Initial revision
XX */
XX%}
XX
XX%token SPACE RULSEP INCSEP PATH SUFF
XX%{
XX# define PREF    struct pref
XX# define SUF     struct suf
XX# define INCFILE struct incfile
XX# define LHSFILE struct lhsfile
XX# define NAME    struct filename
XX# define OUTSIZ  10
XX# define PATHSIZ 100
XX# define DIRSIZ  14
XX# define LINSIZ  256
XX# define PHASHL  503
XX# define LINE	 80
XX# define INCLUDED  1
XX# define CNULL '\0'
XX# define KOL ':'
XX# define EQU '='
XX# define RULES	 ".o: .c .p .f; .c= .y .l .q; .h= .y"
XX
XX# include <stdio.h>
XX# include <strings.h>
XX
XXstatic char usage[]= "Usage: depend [-1] [-rfile] [-Rrules]";
XX
XX/* File name prefixes
XX */
XXPREF
XX{	
XX	PREF	*	nexthash;
XX	char		path[PATHSIZ+1];
XX};
XX
XX/* File name suffixes:
XX *
XX * If the suffix occurs in the rhs of a rule,
XX * the output file suffix and rule type
XX * (KOL or EQU) is recorded.
XX */
XXSUF
XX{
XX	SUF	*	next,
XX		*	out[OUTSIZ];
XX	char		name[DIRSIZ+1];
XX	int		top,
XX			rule;
XX};
XX
XX/* List of files included by a given file.
XX */
XXINCFILE
XX{
XX	INCFILE	*	next;
XX	PREF	*	pf;
XX	SUF	*	sf;
XX};
XX
XX/* A node for each file found in the lhs of some include statement.
XX * The transfer rules are successively applied to the suffix
XX * before the file is inserted.
XX * Reference to list of included files.
XX */
XXLHSFILE
XX{
XX	LHSFILE	*	next;
XX	PREF	*	pf;
XX	SUF	*	sf;
XX	INCFILE	*	ic;
XX	int		state;
XX};
XX
XXNAME
XX{
XX	PREF	*	pf;
XX	SUF	*	sf;
XX};
XX
XXstruct
XX{
XX	SUF	*	sf;
XX	LHSFILE *	lf;
XX} first;
XX
XX
XXextern char	*	calloc();
XXvoid			yyerror();
XX
XXstatic NAME		getname(),
XX			lhs,
XX			rhs;
XXstatic LHSFILE	*	nodelf(),
XX		*	thislf;
XXstatic PREF	*	nodepf(),
XX		*	phash[PHASHL];
XXstatic SUF	*	nodesf(),
XX		*	lsuf,
XX		*	rsuf;
XXstatic char	*	alloc(),
XX		*	rulstring,
XX		*	yystring;
XXstatic char		line[LINSIZ];
XXstatic void		printdep(),
XX			copyinc(),
XX			nodeic();
XXstatic int		hash(),
XX			lineno,
XX			rule,
XX			onedep;
XX
XX# include "depscan.c"
XX
XXmain(argc, argv)
XX	int		argc;
XX	char	*	argv[];
XX{
XX	char		rulbuf[LINSIZ];
XX
XX	setprogname(argv[0]);
XX	rulstring = rulbuf;
XX	strcpy(rulbuf, RULES);
XX
XX	while (argc > 1 && argv[1][0] == '-')
XX	{
XX		switch (argv[1][1])
XX		{
XX		 case 'r':
XX			strcat(rulbuf, "; ");
XX			strcat(rulbuf, argv[1]+2);
XX			break;
XX
XX		 case 'R':
XX			rulstring = argv[1]+2;
XX			break;
XX
XX		 case '1':
XX			onedep++;
XX			break;
XX
XX		 default:
XX			fatal("unknown option %s", argv[1]);
XX		}
XX
XX		argv++;
XX		argc--;
XX	}
XX
XX	if (argc != 1)
XX		fatalmesg(usage);
XX
XX	yystring = rulstring;
XX	BEGIN rules;
XX
XX	first.lf = NULL;
XX	yyparse();
XX	if (first.lf)
XX		printdep();
XX	exit(0);
XX}
XX%}
XX
XX%%
XX
XXaccept	:	rules includes
XX	;
XXrules	:	rule
XX	|	RULSEP rules
XX	|	rules RULSEP
XX	|	rules RULSEP rule
XX	;
XXrule	:	':' SPACE
XX			{   /* Lhs of inclusion rule, empty output suffix */
XX				lsuf = nodesf("");
XX				rule = KOL;
XX			}
XX		rhssuf
XX	|	lhssuf ':' SPACE
XX			{   /* Lhs of inclusion rule */
XX				rule = KOL;
XX			}
XX		rhssuf
XX	|	lhssuf '=' SPACE
XX			{   /* Lhs of transfer rule */
XX				rule = EQU;
XX			}
XX		rhssuf
XX	|	rule SPACE rhssuf
XX	;
XXlhssuf	:	SUFF
XX			{   /* Lhs of any rule */
XX				lsuf = nodesf(yytext);
XX			}
XX	;
XXrhssuf	:	SUFF
XX			{   /* Rhs of any rule */
XX				rsuf = nodesf(yytext);
XX				if (rsuf->rule && (rsuf->rule != EQU || rule != EQU))
XX				        fatal("ambiguous rules %s", rulstring);
XX				rsuf->rule = rule;
XX				if (rsuf->top >= OUTSIZ)
XX					fatal("to many parallel transfers %s", rulstring);
XX				rsuf->out[rsuf->top++] = lsuf;
XX			}
XX	;
XXincludes:
XX	|	includes INCSEP
XX	|	includes INCSEP include
XX	;
XXinclude	:	PATH
XX			{   /* Lhs of include statement:
XX			     *      Insert in lhsfile list.
XX			     */
XX				lhs = getname(yytext);
XX				thislf = nodelf(lhs.pf, lhs.sf);
XX			}
XX		SPACE '<' SPACE
XX		PATH
XX			{   /* Rhs of include statement:
XX			     *      Append to include list of lhsfile.
XX			     */
XX				rhs = getname(yytext);
XX				nodeic(thislf, rhs.pf, rhs.sf);
XX			}
XX	;
XX
XX%%
XX
XXvoid
XXyyerror(s)
XX	char	*	s;
XX{
XX	if (yystring)
XX		fatal("%s rules: %s", s, rulstring);
XX	else
XX		fatal("%s near line %d: %s", s, lineno, line);
XX}
XX
XX/* Go through lhsfile list and print implied Make dependencies.
XX */
XXstatic void
XXprintdep()
XX{
XX	LHSFILE	*	lf,
XX		*	lf2;
XX	SUF	*	sf;
XX	INCFILE	*	ic;
XX	int		i;
XX
XX    /* Apply transfer rules to the LHS suffixes.
XX     * If there are more than one output suffix,
XX     * make a new LHS node with a copy of the include list for each of them.
XX     *
XX     * Since the new nodes are inserted at the end of the LHS list,
XX     * they will be dealt with again, later in the for-loop.
XX     */
XX	for (lf = first.lf; lf; lf = lf->next)
XX		while (lf->sf->rule == EQU)
XX		{
XX			for (i = 1; i < lf->sf->top; i++)
XX				copyinc(lf, nodelf(lf->pf, lf->sf->out[i]));
XX			
XX			lf->sf = lf->sf->out[0];
XX		}
XX
XX    /* Construct Transitive Closure.
XX     */
XX	for (lf = first.lf; lf; lf = lf->next)
XX		for (lf2 = first.lf; lf2; lf2 = lf2->next)
XX			for (ic = lf2->ic; ic; ic = ic->next)
XX				if (ic->pf == lf->pf && ic->sf == lf->sf)
XX				{
XX					lf->state = INCLUDED;
XX					copyinc(lf, lf2);
XX					break;
XX				}
XX
XX    /* For each lhs file, apply inclusion rules
XX     * and generate Make dependencies.
XX     */
XX	for (lf = first.lf; lf; lf = lf->next)
XX	{
XX		char	lhsdep[PATHSIZ+1], rhsdep[PATHSIZ+1];
XX		int	brk = 0;
XX
XX	    /* If the file was included in some other file,
XX	     * no separate output file will be generated for it.
XX	     * The corresponding dependencies have thus already
XX	     * been taken care of.
XX	     */
XX		if (lf->state == INCLUDED)
XX			continue;
XX
XX		sf = lf->sf;
XX
XX	    /* If the file was not included in any other file,
XX	     * and there is no inclusion rule for its suffix,
XX	     * the file is discarded.
XX	     */
XX		if (sf->rule != KOL)
XX			continue;
XX
XX		sprintf(lhsdep, "%s%s", lf->pf->path, sf->out[0]->name); 
XX		sprintf(line, "%s:", lhsdep); 
XX
XX		for (ic = lf->ic; ic; ic = ic->next)
XX		{
XX			sprintf(rhsdep, "%s%s", ic->pf->path, ic->sf->name);
XX
XX			if (strlen(line)+strlen(rhsdep)+1 > LINE || brk)
XX			{
XX				printf("%s\n", line);
XX				sprintf(line, "%s:", lhsdep); 
XX			}
XX			strcat(line, " ");
XX			strcat(line, rhsdep);
XX			brk = onedep;
XX		}
XX		printf("%s\n", line);
XX	}
XX}
XX
XX/* Copy entire include file list.
XX *
XX */
XXstatic void
XXcopyinc(from, to)
XX	LHSFILE *	from,
XX		*	to;
XX{
XX	INCFILE	*	ic;
XX
XX		for (ic = from->ic; ic; ic = ic->next)
XX			nodeic(to, ic->pf, ic->sf);
XX}
XX
XX/* Return file name.  
XX *
XX */
XXstatic NAME
XXgetname(path)
XX	char	*	path;
XX{
XX	NAME		nm;
XX	char	*	p;
XX	int		c;
XX
XX	if (strlen(path) > PATHSIZ)
XX		fatal("path too long: %s", path);
XX
XX	if ((p = rindex(path, '/')) == NULL)
XX		p = path;
XX
XX	if ((p = rindex(p, '.')) == NULL)
XX		p = path + strlen(path);
XX
XX	nm.sf = nodesf(p);
XX	c = *p;
XX	*p = CNULL;
XX	nm.pf = nodepf(path);
XX	*p = c;
XX
XX	return nm;
XX}
XX
XX/* Return suffix node.
XX * If the given suffix was not in the suffix list,
XX * allocate a new node.
XX */
XXstatic SUF *
XXnodesf(name)
XX	char	*	name;
XX{
XX	SUF	*	node,
XX		*	prev;
XX
XX	for (prev = node = first.sf; node; prev = node, node = node->next)
XX		if (strcmp(name, node->name) == 0)
XX			return node;
XX
XX	node = (SUF *) alloc(sizeof(SUF), name);
XX	strcpy(node->name, name);
XX
XX	if (prev)
XX		prev->next = node;
XX	else
XX		first.sf = node;
XX
XX	return node;
XX}
XX
XX/* Return prefix node.
XX * If the given (reduced) path was not in the prefix list,
XX * allocate a new node.
XX */
XXstatic PREF *
XXnodepf(path)
XX	char	*	path;
XX{
XX	PREF	*	node,
XX		*	prevhash;
XX	int		h;
XX
XX	h = hash(path, PHASHL);
XX
XX	for (node = phash[h]; node; node = node->nexthash)
XX		if (strcmp(path, node->path) == 0)
XX			return node;
XX		else
XX			prevhash = node;
XX
XX	node = (PREF *) alloc(sizeof(PREF), path);
XX	strcpy(node->path, path);
XX
XX	if (phash[h])
XX		prevhash->nexthash = node;
XX	else
XX		phash[h] = node;
XX
XX	return node;
XX}
XX
XX/* Return lhsfile node.
XX * If the given lhsfile was not in the lhsfile list,
XX * allocate a new node.
XX */
XXstatic LHSFILE *
XXnodelf(pf, sf)
XX	PREF	*	pf;
XX	SUF	*	sf;
XX{
XX	LHSFILE *	node,
XX		*	prev;
XX
XX	for (prev = node = first.lf; node; prev = node, node = node->next)
XX		if (node->pf == pf && node->sf == sf)
XX			return node;
XX
XX	node = (LHSFILE *) alloc(sizeof(LHSFILE), line);
XX
XX	node->pf = pf;
XX	node->sf = sf;
XX
XX	if (prev)
XX		prev->next = node;
XX	else
XX		first.lf = node;
XX
XX	return node;
XX}
XX
XX/* Add the given rhsfile to the include list
XX * of the given lhsfile,
XX * if it was not there already.
XX */
XXstatic void
XXnodeic(lf, pf, sf)
XX	LHSFILE	*	lf;
XX	PREF	*	pf;
XX	SUF	*	sf;
XX{
XX	INCFILE *	node,
XX		*	prev;
XX
XX	if (sf->rule == EQU)
XX	   /* Must follow the Suffix Convention for Included Files.
XX	    */
XX		fatal("bad include file suffix %s%s < %s%s",
XX		   lf->pf->path, lf->sf->name, pf->path, sf->name);
XX		
XX	for (prev = node = lf->ic; node; prev = node, node = node->next)
XX		if (node->pf == pf && node->sf == sf)
XX			return;
XX
XX	if (pf == lf->pf && sf == lf->sf)
XX	{
XX		error("infinite recursion on %s%s - dependency ignored", pf->path, sf->name);
XX		return;
XX	}
XX
XX	node = (INCFILE *) alloc(sizeof(INCFILE), line);
XX	node->pf = pf;
XX	node->sf = sf;
XX
XX	if (prev)
XX		prev->next = node;
XX	else
XX		lf->ic = node;
XX}
XX
XX/* Allocate a zero initialized node.
XX */
XXstatic char *
XXalloc(size, obj)
XX	char	*	obj;
XX{
XX	char	*	node;
XX
XX	if ((node = calloc(1, size)) == NULL)
XX		fatal("can't alloc: %s", obj);
XX
XX	return node;
XX}
XX
XX/* Hash a character string, and return the hash value
XX * modulo the given hash length.
XX */
XXstatic int
XXhash(p, hashl)
XX	char	*	p;
XX	int		hashl;
XX{
XX	register 	unsigned sum;
XX	register 	c;
XX
XX	sum = 0;
XX	while ((c = *p++) != 0)
XX	{
XX		if (sum & 01)
XX			sum = (sum >> 1) + 0x8000;
XX		else
XX			sum >>= 1;
XX		sum += c;
XX		sum &= 0xFFFF;
XX	}
XX	return sum % hashl;
XX}
SHAR_EOF
if test 10650 -ne "`wc -c depend.y`"
then
echo shar: error transmitting depend.y '(should have been 10650 characters)'
fi
sed 's/^XX//' << \SHAR_EOF > makenorm.y
XX%{
XX/* -- Normalize include references
XX *
XX * $File: makenorm.y  1.8  1985-03-29  14:11:19 $
XX *
XX *  Copyright (c) 1983  Kim Walden
XX *      ENEA DATA, Sweden and    
XX *      SYSLAB, Department of Computer Science,
XX *      University of Stockholm, Sweden.
XX *
XX *	This software may be used and copied freely,
XX *	provided that proper credit is given to the originator
XX *	by including the above text in each copy.
XX *
XX *	Descr:	This program implements part of the algorithm described
XX *      	in K. Walden, "Automatic Generation of Make Dependencies",
XX *      	Softw. Practice & Exper., vol. 14, no. 6, June 1984 
XX *
XX *
XX * $Log:	makenorm.y,v $
XX * 
XX * Revision 1.8  1985-03-29  14:11:19  kim
XX * New source format
XX * 
XX * Revision 1.7  1985-03-21  09:31:11  kim
XX * Use sprintf in a System V compatible way
XX * 
XX * Revision 1.6  1985-03-08  01:18:35  kim
XX * Added support for parallell transfer rules.
XX * Added -1 option to makedep and depend.
XX * 
XX * Revision 1.5  1985-02-25  19:41:56  kim
XX * Added -a option for absolute directories
XX * 
XX * Revision 1.4  1985-02-20  11:53:09  kim
XX * Bug fix
XX * 
XX * Revision 1.3  1985-02-19  11:21:23  kim
XX * New default include rules
XX * 
XX * Revision 1.2  1985-02-18  14:24:15  kim
XX * New error handling
XX * 
XX * Revision 1.1  1985-02-16  18:57:07  kim
XX * Initial revision
XX */
XX%}
XX
XX%token SPACE RULSEP INCSEP PATH SUFF INCL QUOTE LPAR RPAR
XX%{
XX# define DIRLIST  struct dirlist
XX# define PREF     struct pref
XX# define SUF      struct suf
XX# define SOURCE   struct source
XX# define NAME     struct filename
XX# define PATHSIZ  100
XX# define DIRSIZ   14
XX# define LINSIZ   256
XX# define OUTSIZ   10
XX# define PHASHL   503
XX# define LINE	  80
XX# define EXACT    0
XX# define DERIVED  1
XX# define FORCE	  2
XX# define NOREDUCE 0
XX# define REDUCE   1
XX# define FALSE	  0
XX# define TRUE	  1
XX# define CNULL   '\0'
XX# define KOL     ':'
XX# define EQU     '='
XX# define RULES	 ".o: .c; .c= .y .l .q; .h= .y"
XX
XX# include <stdio.h>
XX# include <strings.h>
XX# include <sys/types.h>
XX# include <sys/stat.h>
XX
XXstatic char usage[]=
XX"Usage: makenorm [-rfile] [-Rrules] [-Ilist] [-alist] [-i] makedir sourcefiles";
XX
XX/* Directory lists
XX */
XXDIRLIST
XX{
XX	DIRLIST	*	next;
XX	char		path[PATHSIZ+1];
XX};
XX
XX/* File name prefixes   (including directory part)
XX */
XXPREF
XX{	
XX	PREF	*	nexthash;
XX	char		path[PATHSIZ+1];
XX};
XX
XX/* File name suffixes:
XX *
XX * If the suffix occurs in the rhs of a rule,
XX * the output file suffix and rule type
XX * (KOL or EQU) is recorded.
XX */
XXSUF
XX{
XX	SUF	*	next,
XX		*	out[OUTSIZ];
XX	char		name[DIRSIZ+1];
XX	int		top,
XX			rule;
XX};
XX
XX/* Declared sources:
XX *
XX * The transfer rules are successively applied
XX * to the suffix before a file is inserted.
XX */
XXSOURCE
XX{
XX	SOURCE	*	next;
XX	PREF	*	pf;
XX	SUF	*	sf;
XX};
XX
XX/* File names
XX */
XXNAME
XX{
XX	PREF	*	pf;
XX	SUF	*	sf;
XX};
XX
XX
XXstruct 
XX{
XX	SOURCE	*	so;		/* source list */
XX	SUF	*	sf;		/* suffix list */
XX	DIRLIST	*	idir, 		/* list of include directories */
XX		*	adir;		/* list of absolute directories */
XX} first;
XX
XXextern char	*	calloc(),
XX		*	mpath();
XXvoid			yyerror();
XXstatic PREF 	*	nodepf(),
XX		*	phash[PHASHL];	/* hash table for prefixes */
XXstatic SUF	*	nodesf(),
XX		*	lsuf,
XX		*	rsuf;
XXstatic NAME		getname(),
XX			lhs,
XX			rhs;
XXstatic char	*	alloc(),
XX		*	makedir,
XX		*	rulstring,
XX		*	yystring;
XXstatic char		line[LINSIZ];
XXstatic int		derived(),
XX			hash(),
XX			findso(),
XX			printcond(),
XX			lineno,
XX			rule,
XX			remote,
XX			sysflag;
XXstatic void		getdirlist(),
XX			nodedl(),
XX			printnorm();
XX
XX# include "normscan.c"
XX
XXmain(argc, argv)
XX	int		argc;
XX	char	*	argv[];
XX{
XX	char		rulbuf[LINSIZ];
XX
XX	setprogname(argv[0]);
XX	rulstring = rulbuf;
XX	strcpy(rulbuf, RULES);
XX	nodedl("/usr/include", &first.adir);
XX	sysflag = 0;
XX
XX	while (argc > 1 && argv[1][0] == '-')
XX	{
XX		switch (argv[1][1])
XX		{
XX		 case 'r':
XX			strcat(rulbuf, "; ");
XX			strcat(rulbuf, argv[1]+2);
XX			break;
XX
XX		 case 'R':
XX			rulstring = argv[1]+2;
XX			break;
XX
XX		 case 'i':
XX			sysflag++;
XX			break;
XX
XX		 case 'a':
XX		 case 'I':
XX			getdirlist(argv[1]);
XX			break;
XX
XX		 default:
XX			error("unknown option %s", argv[1]);
XX			fatalmesg(usage);
XX		}
XX
XX		argv++;
XX		argc--;
XX	}
XX
XX	if (argc < 2)
XX		fatalmesg(usage);
XX	makedir = argv[1];
XX	argv ++;
XX	argc --;
XX
XX	if (argc < 2)
XX		fatal("no source files specified");
XX
XX	while (--argc)
XX		findso(getname(argv++[1], REDUCE), FORCE);
XX
XX	yystring = rulstring;
XX	BEGIN rules;
XX
XX	yyparse();
XX	exit(0);
XX}
XX%}
XX
XX%%
XX
XXaccept	:	rules includes
XX	;
XXrules	:	rule
XX	|	RULSEP rules
XX	|	rules RULSEP
XX	|	rules RULSEP rule
XX	;
XXrule	:	':' SPACE
XX			{   /* Lhs of inclusion rule, empty output suffix */
XX				lsuf = nodesf("");
XX				rule = KOL;
XX			}
XX		rhssuf
XX	|	lhssuf ':' SPACE
XX			{   /* Lhs of inclusion rule */
XX				rule = KOL;
XX			}
XX		rhssuf
XX	|	lhssuf '=' SPACE
XX			{   /* Lhs of transfer rule */
XX				rule = EQU;
XX			}
XX		rhssuf
XX	|	rule SPACE rhssuf
XX	;
XXlhssuf	:	SUFF
XX			{   /* Lhs of any rule */
XX				lsuf = nodesf(yytext);
XX			}
XX	;
XXrhssuf	:	SUFF
XX			{   /* Rhs of any rule */
XX				rsuf = nodesf(yytext);
XX				if (rsuf->rule && (rsuf->rule != EQU || rule != EQU))
XX				        fatal("ambiguous rules %s", rulstring);
XX				rsuf->rule = rule;
XX				if (rsuf->top >= OUTSIZ)
XX					fatal("to many parallel transfers %s", rulstring);
XX				rsuf->out[rsuf->top++] = lsuf;
XX			}
XX	;
XXincludes:
XX	|	includes INCSEP
XX	|	includes INCSEP include
XX	;
XXinclude	:	lhs
XX		QUOTE
XX			{	remote = 0;	}
XX		rhs
XX		QUOTE
XX			{	unput('#');
XX				BEGIN comment;
XX			}
XX	|	lhs
XX		LPAR
XX			{	remote = 1;	}
XX		rhs
XX		RPAR
XX			{	unput('#');
XX				BEGIN comment;
XX			}
XX	;
XXlhs	:	PATH
XX			{   /* Lhs of include statement:
XX			     *      Reduce filename, and check that
XX			     *      file name was in the source list.
XX			     */
XX				lhs = getname(yytext, REDUCE);
XX				if (!findso(lhs, EXACT))
XX					error("%s not in source list",
XX					   yytext);
XX			}
XX		':' INCL 
XX	;
XXrhs	:	PATH
XX			{   /* Rhs of include statement:
XX			     *      Resolve file reference and print
XX			     *      normalized include statement.
XX			     */
XX				rhs = getname(yytext, NOREDUCE);
XX				if (rhs.sf->rule == EQU)
XX					fatal("bad include file suffix: %s",
XX					   line);
XX				printnorm();
XX			}
XX	;
XX
XX%%
XX
XXvoid
XXyyerror(s)
XX	char	*	s;
XX{
XX	if (yystring)
XX		fatal("%s rules: %s", s, rulstring);
XX	else
XX		fatal("%s near line %d: %s", s, lineno, line);
XX}
XX
XX/* Resolve current include file reference and print
XX * the corresponding normalized include statement.
XX */
XXstatic void
XXprintnorm()
XX{
XX	DIRLIST *	dl;
XX	char	*	p;
XX	char		dir[PATHSIZ+1];
XX
XX    /* Try directory of left hand side file when
XX     *    format: #include "file".
XX     */
XX	if (!remote)
XX	{
XX		strcpy(dir, lhs.pf->path);
XX
XX		if ((p = rindex(dir, '/')) == NULL)
XX			p = dir;
XX
XX		*p = CNULL;
XX
XX		if (printcond(dir))
XX			return;
XX	}
XX
XX    /* Try user include libraries */
XX
XX	for (dl = first.idir; dl; dl = dl->next)
XX		if (printcond(dl->path))
XX			return;
XX
XX    /* Try system include library */
XX
XX	if (printcond("/usr/include"))
XX		return;
XX	
XX	error("cannot resolve: %s", line);
XX}
XX
XXstatic int
XXprintcond(dir)
XX	char	*	dir;
XX{
XX	struct stat	stbuf;
XX	NAME		nm;
XX	char		buf[PATHSIZ+1];
XX
XX    /* If include reference is not absolute,
XX     * prepend directory.
XX     */
XX
XX	if (strlen(dir) != 0 && rhs.pf->path[0] != '/')
XX		sprintf(buf, "%s/%s%s", dir, rhs.pf->path, rhs.sf->name);
XX	else
XX		sprintf(buf, "%s%s", rhs.pf->path, rhs.sf->name);
XX
XX	nm = getname(buf, REDUCE);
XX
XX	sprintf(buf, "%s%s", nm.pf->path, nm.sf->name);
XX
XX    /* If the resulting file name path can be derived from a source,
XX     * accept include reference and print dependency.
XX     */
XX	if (findso(nm, DERIVED))
XX	{
XX		printf("%s%s < %s\n", lhs.pf->path, lhs.sf->name, buf); 
XX		return TRUE;
XX	}
XX
XX    /* Ignore system include references not specified as sources,
XX     * unless -i option was specified.
XX     */
XX	if (strncmp(buf, "/usr/include/", strlen("/usr/include/")) == 0
XX	       && !sysflag && (stat(buf, &stbuf) == 0))
XX		return TRUE;
XX
XX	return FALSE;
XX}
XX
XX
XX/* Return file name,
XX *    reduced if flag == REDUCE.
XX */
XXstatic NAME
XXgetname(path, flag)
XX	char	*	path;
XX	int		flag;
XX{
XX	NAME		nm;
XX	DIRLIST *	dl;
XX	char	*	mp,
XX		*	p;
XX	char		buf[PATHSIZ+1];
XX	int		c;
XX
XX	mp = path;
XX
XX	if (flag == REDUCE )
XX	{
XX	    int absdir = 0;
XX
XX	    /* Make reference absolute */
XX		if (*path != '/')
XX		{
XX			sprintf(buf, "%s/%s", makedir, path);
XX			path = buf;
XX		}
XX
XX	    /* If the file name refers to one of the absolute directories,
XX	     * it should be in absolute form.
XX	     */
XX		for (dl = first.adir; dl; dl = dl->next)
XX		{
XX			if ((mp = mpath(path, dl->path)) == NULL)
XX				fatal("can't reduce path");
XX
XX			if (strncmp(mp, "../", 3) != 0)
XX			{
XX				if (strlen(mp)+strlen(dl->path)+1 > PATHSIZ)
XX					fatal("path too long: %s/%s",
XX					   dl->path, mp);
XX
XX				absdir++;
XX				sprintf(buf, "%s/%s", dl->path, mp);
XX				mp = buf;
XX				break;
XX			}
XX		}
XX
XX	    /* If the file name does not refer to any of the
XX	     * absolute directories, it should be in relative form.
XX	     */
XX		if (!absdir)
XX		{
XX			if ((mp = mpath(path, makedir)) == NULL)
XX				fatal("can't reduce path");
XX
XX			if (strlen(mp) > PATHSIZ)
XX				fatal("path too long: %s", mp);
XX		}
XX	}
XX
XX
XX	if ((p = rindex(mp, '/')) == NULL)
XX		p = mp;
XX
XX	if ((p = rindex(p, '.')) == NULL)
XX		p = mp + strlen(mp);
XX
XX	nm.sf = nodesf(p);
XX	c = *p;
XX	*p = CNULL;
XX	nm.pf = nodepf(mp);
XX	*p = c;
XX
XX	return nm;
XX}
XX
XXstatic char *
XXgetword(p, buf)
XX	char	*	p,
XX		*	buf;
XX{
XX	while (*p == ' ' || *p == '\t')
XX		p++;
XX
XX	if (*p == CNULL)
XX		return NULL;
XX
XX	while (*p != ' ' && *p != '\t' && *p != CNULL)
XX		*buf++ = *p++;
XX
XX	*buf = CNULL;
XX	return p;
XX}
XX
XXstatic void
XXgetdirlist(arg)
XX	char	*	arg;
XX{
XX	DIRLIST **	head;
XX	char	*	s;
XX	char		buf[PATHSIZ+1];
XX
XX	if (arg[1] == 'a')
XX		head = &first.adir;
XX	else
XX		head = &first.idir;
XX	
XX	s = arg;
XX	s += 2;
XX	while (s = getword(s, buf))
XX	{
XX		if (arg[1] == 'a' && buf[0] != '/')
XX			fatal("directory list must be absolute: %s", arg);
XX
XX		nodedl(buf, head); 
XX	}
XX}
XX
XX/* Return suffix node.
XX * If the given suffix was not in the suffix list,
XX * allocate a new node.
XX */
XXstatic SUF *
XXnodesf(name)
XX	char	*	name;
XX{
XX	SUF	*	node,
XX		*	prev;
XX
XX	for (prev = node = first.sf; node; prev = node, node = node->next)
XX		if (strcmp(name, node->name) == 0)
XX			return node;
XX
XX	node = (SUF *) alloc(sizeof(SUF), name);
XX	strcpy(node->name, name);
XX
XX	if (prev)
XX		prev->next = node;
XX	else
XX		first.sf = node;
XX
XX	return node;
XX}
XX
XX/* Return prefix node.
XX * If the given (reduced) path was not in the prefix list,
XX * allocate a new node.
XX */
XXstatic PREF *
XXnodepf(path)
XX	char	*	path;
XX{
XX	PREF	*	node,
XX		*	prevhash;
XX	int		h;
XX
XX	h = hash(path, PHASHL);
XX
XX	for (node = phash[h]; node; node = node->nexthash)
XX		if (strcmp(path, node->path) == 0)
XX			return node;
XX		else
XX			prevhash = node;
XX
XX	node = (PREF *) alloc(sizeof(PREF), path);
XX	strcpy(node->path, path);
XX
XX	if (phash[h])
XX		prevhash->nexthash = node;
XX	else
XX		phash[h] = node;
XX
XX	return node;
XX}
XX
XX/* Search the source list for the given file name:
XX *
XX *   1. flag = EXACT		Look for exact match.
XX *				Return TRUE if found, else FALSE
XX *
XX *   2. flag = FORCE		Look for exact match.
XX *				If not found, allocate a new node.
XX *				Always return TRUE.
XX *
XX *   3. flag = DERIVED		Return TRUE if a match can be found by applying
XX *				transfer rules to the file name suffixes in the
XX *			 	source list, else FALSE.
XX */
XXstatic int
XXfindso(nm, flag)
XX	NAME		nm;
XX	int		flag;
XX{
XX	SOURCE	*	node,
XX		*	prev;
XX
XX	for (prev = node = first.so; node; prev = node, node = node->next)
XX		if (node->pf == nm.pf
XX		  && (node->sf == nm.sf || DERIVED && derived(nm.sf, node->sf)))
XX			return TRUE;
XX
XX	if (flag == FORCE)
XX	{
XX		node = (SOURCE *) alloc(sizeof(SOURCE), line);
XX
XX		node->pf = nm.pf;
XX		node->sf = nm.sf;
XX
XX		if (prev)
XX			prev->next = node;
XX		else
XX			first.so = node;
XX
XX		return TRUE;
XX	}
XX	else
XX		return FALSE;
XX}
XX
XX/* If dsf is same as sf, or can be derived from it by applying
XX * a number of transfer rules, return TRUE, else FALSE
XX */
XXstatic int
XXderived(dsf, sf)
XX	SUF	*	dsf,
XX		*	sf;
XX{
XX	int		i;
XX
XX	if (dsf == sf)
XX		return TRUE;
XX
XX	if (sf->rule != EQU)
XX		return FALSE;
XX
XX	for (i = 0; i < sf->top; i++)
XX		if (derived(dsf, sf->out[i]))
XX			return TRUE;
XX
XX	return FALSE;
XX}
XX
XX/* Append directory to search list.
XX */
XXstatic void
XXnodedl(path, head)
XX	char	*	path;
XX	DIRLIST **	head;
XX{
XX	DIRLIST *	node,
XX		*	prev;
XX
XX	for (prev = node = *head; node; prev = node, node = node->next)
XX		if (strcmp(path, node->path) == 0)
XX			return;
XX
XX	node = (DIRLIST *) alloc(sizeof(DIRLIST), path);
XX	strcpy(node->path, path);
XX
XX	if (prev)
XX		prev->next = node;
XX	else
XX		*head = node;
XX
XX	return;
XX}
XX
XX
XX/* Allocate a zero initialized node.
XX */
XXstatic char *
XXalloc(size, obj)
XX	char	*	obj;
XX{
XX	char	*	node;
XX
XX	if ((node = calloc(1, size)) == NULL)
XX		fatal("can't alloc %s", obj);
XX
XX	return node;
XX}
XX
XX/* Hash a character string, and return the hash value
XX * modulo the given hash length.
XX */
XXstatic int
XXhash(p, hashl)
XX	char	*	p;
XX	int		hashl;
XX{
XX	register	unsigned sum;
XX	register	c;
XX
XX	sum = 0;
XX	while ((c = *p++) != 0)
XX	{
XX		if (sum & 01)
XX			sum = (sum >> 1) + 0x8000;
XX		else
XX			sum >>= 1;
XX		sum += c;
XX		sum &= 0xFFFF;
XX	}
XX	return sum % hashl;
XX}
SHAR_EOF
if test 12659 -ne "`wc -c makenorm.y`"
then
echo shar: error transmitting makenorm.y '(should have been 12659 characters)'
fi
chdir ..
#	End of shell archive
exit 0
-- 
	Kim Walden
	ENEA DATA Sweden

	UUCP:	{seismo,decvax,philabs}!{mcvax,ukc,unido}!enea!kim
	ARPA:	decvax!mcvax!enea!kim@berkeley.arpa
		mcvax!enea!kim@seismo.arpa