Home | History | Annotate | Line # | Download | only in rcorder
rcorder.c revision 1.13
      1  1.13    rumble /*	$NetBSD: rcorder.c,v 1.13 2004/09/21 15:47:32 rumble Exp $	*/
      2   1.1       mrg 
      3   1.1       mrg /*
      4   1.1       mrg  * Copyright (c) 1998, 1999 Matthew R. Green
      5   1.1       mrg  * All rights reserved.
      6  1.12       agc  *
      7  1.12       agc  * Redistribution and use in source and binary forms, with or without
      8  1.12       agc  * modification, are permitted provided that the following conditions
      9  1.12       agc  * are met:
     10  1.12       agc  * 1. Redistributions of source code must retain the above copyright
     11  1.12       agc  *    notice, this list of conditions and the following disclaimer.
     12  1.12       agc  * 2. Redistributions in binary form must reproduce the above copyright
     13  1.12       agc  *    notice, this list of conditions and the following disclaimer in the
     14  1.12       agc  *    documentation and/or other materials provided with the distribution.
     15  1.12       agc  * 3. The name of the author may not be used to endorse or promote products
     16  1.12       agc  *    derived from this software without specific prior written permission.
     17  1.12       agc  *
     18  1.12       agc  * THIS SOFTWARE IS PROVIDED BY THE AUTHOR ``AS IS'' AND ANY EXPRESS OR
     19  1.12       agc  * IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE IMPLIED WARRANTIES
     20  1.12       agc  * OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE ARE DISCLAIMED.
     21  1.12       agc  * IN NO EVENT SHALL THE AUTHOR BE LIABLE FOR ANY DIRECT, INDIRECT,
     22  1.12       agc  * INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT
     23  1.12       agc  * NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE,
     24  1.12       agc  * DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY
     25  1.12       agc  * THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT
     26  1.12       agc  * (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF
     27  1.12       agc  * THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
     28  1.12       agc  */
     29  1.12       agc 
     30  1.12       agc /*
     31   1.1       mrg  * Copyright (c) 1998
     32   1.1       mrg  * 	Perry E. Metzger.  All rights reserved.
     33   1.1       mrg  *
     34   1.1       mrg  * Redistribution and use in source and binary forms, with or without
     35   1.1       mrg  * modification, are permitted provided that the following conditions
     36   1.1       mrg  * are met:
     37   1.1       mrg  * 1. Redistributions of source code must retain the above copyright
     38   1.1       mrg  *    notice, this list of conditions and the following disclaimer.
     39   1.1       mrg  * 2. Redistributions in binary form must reproduce the above copyright
     40   1.1       mrg  *    notice, this list of conditions and the following disclaimer in the
     41   1.1       mrg  *    documentation and/or other materials provided with the distribution.
     42   1.1       mrg  * 3. All advertising materials mentioning features or use of this software
     43   1.1       mrg  *    must display the following acknowledgement:
     44   1.1       mrg  *	This product includes software developed for the NetBSD Project
     45   1.1       mrg  *	by Perry E. Metzger.
     46   1.1       mrg  * 4. The name of the author may not be used to endorse or promote products
     47   1.1       mrg  *    derived from this software without specific prior written permission.
     48   1.1       mrg  *
     49   1.1       mrg  * THIS SOFTWARE IS PROVIDED BY THE AUTHOR ``AS IS'' AND ANY EXPRESS OR
     50   1.1       mrg  * IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE IMPLIED WARRANTIES
     51   1.1       mrg  * OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE ARE DISCLAIMED.
     52   1.1       mrg  * IN NO EVENT SHALL THE AUTHOR BE LIABLE FOR ANY DIRECT, INDIRECT,
     53   1.1       mrg  * INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT
     54   1.1       mrg  * NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE,
     55   1.1       mrg  * DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY
     56   1.1       mrg  * THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT
     57   1.1       mrg  * (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF
     58   1.1       mrg  * THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
     59   1.1       mrg  */
     60   1.1       mrg 
     61   1.1       mrg #include <sys/types.h>
     62   1.3     enami #include <sys/stat.h>
     63   1.1       mrg 
     64   1.1       mrg #include <err.h>
     65   1.1       mrg #include <stdio.h>
     66   1.1       mrg #include <stdlib.h>
     67   1.1       mrg #include <string.h>
     68   1.1       mrg #include <unistd.h>
     69   1.1       mrg 
     70   1.1       mrg #include "ealloc.h"
     71   1.1       mrg #include "hash.h"
     72   1.1       mrg 
     73   1.1       mrg #ifdef DEBUG
     74   1.1       mrg int debug = 0;
     75   1.1       mrg # define	DPRINTF(args) if (debug) { fflush(stdout); fprintf args; }
     76   1.1       mrg #else
     77   1.1       mrg # define	DPRINTF(args)
     78   1.1       mrg #endif
     79   1.1       mrg 
     80   1.1       mrg #define REQUIRE_STR	"# REQUIRE:"
     81   1.1       mrg #define REQUIRE_LEN	(sizeof(REQUIRE_STR) - 1)
     82   1.1       mrg #define REQUIRES_STR	"# REQUIRES:"
     83   1.1       mrg #define REQUIRES_LEN	(sizeof(REQUIRES_STR) - 1)
     84   1.1       mrg #define PROVIDE_STR	"# PROVIDE:"
     85   1.1       mrg #define PROVIDE_LEN	(sizeof(PROVIDE_STR) - 1)
     86   1.1       mrg #define PROVIDES_STR	"# PROVIDES:"
     87   1.1       mrg #define PROVIDES_LEN	(sizeof(PROVIDES_STR) - 1)
     88   1.1       mrg #define BEFORE_STR	"# BEFORE:"
     89   1.1       mrg #define BEFORE_LEN	(sizeof(BEFORE_STR) - 1)
     90   1.5       mrg #define KEYWORD_STR	"# KEYWORD:"
     91   1.5       mrg #define KEYWORD_LEN	(sizeof(KEYWORD_STR) - 1)
     92   1.5       mrg #define KEYWORDS_STR	"# KEYWORDS:"
     93   1.5       mrg #define KEYWORDS_LEN	(sizeof(KEYWORDS_STR) - 1)
     94   1.1       mrg 
     95   1.1       mrg int exit_code;
     96   1.1       mrg int file_count;
     97   1.1       mrg char **file_list;
     98   1.1       mrg 
     99  1.10     lukem enum {
    100  1.10     lukem 	RESET	= 0,
    101  1.10     lukem 	SET	= 1,
    102  1.10     lukem };
    103   1.1       mrg 
    104   1.1       mrg Hash_Table provide_hash_s, *provide_hash;
    105   1.1       mrg 
    106   1.1       mrg typedef struct provnode provnode;
    107   1.1       mrg typedef struct filenode filenode;
    108   1.1       mrg typedef struct f_provnode f_provnode;
    109   1.1       mrg typedef struct f_reqnode f_reqnode;
    110   1.5       mrg typedef struct strnodelist strnodelist;
    111   1.1       mrg 
    112   1.1       mrg struct provnode {
    113  1.10     lukem 	int		head;
    114  1.10     lukem 	int		in_progress;
    115   1.1       mrg 	filenode	*fnode;
    116   1.1       mrg 	provnode	*next, *last;
    117   1.1       mrg };
    118   1.1       mrg 
    119   1.1       mrg struct f_provnode {
    120   1.1       mrg 	provnode	*pnode;
    121   1.1       mrg 	f_provnode	*next;
    122   1.1       mrg };
    123   1.1       mrg 
    124   1.1       mrg struct f_reqnode {
    125   1.1       mrg 	Hash_Entry	*entry;
    126   1.1       mrg 	f_reqnode	*next;
    127   1.1       mrg };
    128   1.1       mrg 
    129   1.5       mrg struct strnodelist {
    130   1.5       mrg 	filenode	*node;
    131   1.5       mrg 	strnodelist	*next;
    132   1.6     enami 	char		s[1];
    133   1.5       mrg };
    134   1.5       mrg 
    135   1.1       mrg struct filenode {
    136   1.1       mrg 	char		*filename;
    137  1.10     lukem 	int		in_progress;
    138   1.1       mrg 	filenode	*next, *last;
    139   1.1       mrg 	f_reqnode	*req_list;
    140   1.1       mrg 	f_provnode	*prov_list;
    141   1.5       mrg 	strnodelist	*keyword_list;
    142   1.1       mrg };
    143   1.1       mrg 
    144   1.5       mrg filenode fn_head_s, *fn_head;
    145   1.1       mrg 
    146   1.5       mrg strnodelist *bl_list;
    147   1.5       mrg strnodelist *keep_list;
    148   1.5       mrg strnodelist *skip_list;
    149   1.1       mrg 
    150  1.10     lukem void do_file(filenode *fnode);
    151  1.10     lukem void strnode_add(strnodelist **, char *, filenode *);
    152  1.10     lukem int skip_ok(filenode *fnode);
    153  1.10     lukem int keep_ok(filenode *fnode);
    154  1.10     lukem void satisfy_req(f_reqnode *rnode, char *);
    155  1.10     lukem void crunch_file(char *);
    156  1.10     lukem void parse_line(filenode *, char *, void (*)(filenode *, char *));
    157  1.10     lukem filenode *filenode_new(char *);
    158  1.10     lukem void add_require(filenode *, char *);
    159  1.10     lukem void add_provide(filenode *, char *);
    160  1.10     lukem void add_before(filenode *, char *);
    161  1.10     lukem void add_keyword(filenode *, char *);
    162  1.10     lukem void insert_before(void);
    163  1.10     lukem Hash_Entry *make_fake_provision(filenode *);
    164  1.10     lukem void crunch_all_files(void);
    165  1.10     lukem void initialize(void);
    166  1.10     lukem void generate_ordering(void);
    167  1.10     lukem int main(int, char *[]);
    168   1.1       mrg 
    169   1.1       mrg int
    170  1.10     lukem main(int argc, char *argv[])
    171   1.1       mrg {
    172   1.1       mrg 	int ch;
    173   1.1       mrg 
    174   1.5       mrg 	while ((ch = getopt(argc, argv, "dk:s:")) != -1)
    175   1.1       mrg 		switch (ch) {
    176   1.1       mrg 		case 'd':
    177   1.1       mrg #ifdef DEBUG
    178   1.1       mrg 			debug = 1;
    179   1.1       mrg #else
    180   1.1       mrg 			warnx("debugging not compiled in, -d ignored");
    181   1.1       mrg #endif
    182   1.1       mrg 			break;
    183   1.5       mrg 		case 'k':
    184   1.5       mrg 			strnode_add(&keep_list, optarg, 0);
    185   1.5       mrg 			break;
    186   1.5       mrg 		case 's':
    187   1.5       mrg 			strnode_add(&skip_list, optarg, 0);
    188   1.5       mrg 			break;
    189   1.1       mrg 		default:
    190   1.1       mrg 			/* XXX should crunch it? */
    191   1.1       mrg 			break;
    192   1.1       mrg 		}
    193   1.1       mrg 	argc -= optind;
    194   1.1       mrg 	argv += optind;
    195   1.1       mrg 
    196   1.1       mrg 	file_count = argc;
    197   1.1       mrg 	file_list = argv;
    198   1.1       mrg 
    199   1.1       mrg 	DPRINTF((stderr, "parse_args\n"));
    200   1.1       mrg 	initialize();
    201   1.1       mrg 	DPRINTF((stderr, "initialize\n"));
    202   1.1       mrg 	crunch_all_files();
    203   1.1       mrg 	DPRINTF((stderr, "crunch_all_files\n"));
    204   1.1       mrg 	generate_ordering();
    205   1.1       mrg 	DPRINTF((stderr, "generate_ordering\n"));
    206   1.1       mrg 
    207   1.1       mrg 	exit(exit_code);
    208   1.1       mrg }
    209   1.1       mrg 
    210   1.1       mrg /*
    211   1.1       mrg  * initialise various variables.
    212   1.1       mrg  */
    213   1.1       mrg void
    214  1.10     lukem initialize(void)
    215   1.1       mrg {
    216   1.1       mrg 
    217   1.1       mrg 	fn_head = &fn_head_s;
    218   1.1       mrg 
    219   1.1       mrg 	provide_hash = &provide_hash_s;
    220   1.1       mrg 	Hash_InitTable(provide_hash, file_count);
    221   1.1       mrg }
    222   1.1       mrg 
    223   1.5       mrg /* generic function to insert a new strnodelist element */
    224   1.5       mrg void
    225  1.10     lukem strnode_add(strnodelist **listp, char *s, filenode *fnode)
    226   1.5       mrg {
    227   1.5       mrg 	strnodelist *ent;
    228   1.5       mrg 
    229   1.6     enami 	ent = emalloc(sizeof *ent + strlen(s));
    230   1.5       mrg 	ent->node = fnode;
    231   1.6     enami 	strcpy(ent->s, s);
    232   1.5       mrg 	ent->next = *listp;
    233   1.5       mrg 	*listp = ent;
    234   1.5       mrg }
    235   1.5       mrg 
    236   1.1       mrg /*
    237   1.1       mrg  * below are the functions that deal with creating the lists
    238   1.1       mrg  * from the filename's given and the dependancies and provisions
    239   1.1       mrg  * in each of these files.  no ordering or checking is done here.
    240   1.1       mrg  */
    241   1.1       mrg 
    242   1.1       mrg /*
    243   1.1       mrg  * we have a new filename, create a new filenode structure.
    244   1.1       mrg  * fill in the bits, and put it in the filenode linked list
    245   1.1       mrg  */
    246   1.1       mrg filenode *
    247  1.10     lukem filenode_new(char *filename)
    248   1.1       mrg {
    249   1.1       mrg 	filenode *temp;
    250   1.1       mrg 
    251   1.1       mrg 	temp = emalloc(sizeof(*temp));
    252   1.1       mrg 	memset(temp, 0, sizeof(*temp));
    253   1.1       mrg 	temp->filename = estrdup(filename);
    254   1.1       mrg 	temp->req_list = NULL;
    255   1.1       mrg 	temp->prov_list = NULL;
    256   1.5       mrg 	temp->keyword_list = NULL;
    257   1.1       mrg 	temp->in_progress = RESET;
    258   1.1       mrg 	/*
    259   1.1       mrg 	 * link the filenode into the list of filenodes.
    260   1.1       mrg 	 * note that the double linking means we can delete a
    261   1.1       mrg 	 * filenode without searching for where it belongs.
    262   1.1       mrg 	 */
    263   1.1       mrg 	temp->next = fn_head->next;
    264   1.1       mrg 	if (temp->next != NULL)
    265   1.1       mrg 		temp->next->last = temp;
    266   1.1       mrg 	temp->last = fn_head;
    267   1.1       mrg 	fn_head->next = temp;
    268   1.1       mrg 	return (temp);
    269   1.1       mrg }
    270   1.1       mrg 
    271   1.1       mrg /*
    272   1.5       mrg  * add a requirement to a filenode.
    273   1.1       mrg  */
    274   1.1       mrg void
    275  1.10     lukem add_require(filenode *fnode, char *s)
    276   1.1       mrg {
    277   1.1       mrg 	Hash_Entry *entry;
    278   1.1       mrg 	f_reqnode *rnode;
    279   1.1       mrg 	int new;
    280   1.1       mrg 
    281   1.1       mrg 	entry = Hash_CreateEntry(provide_hash, s, &new);
    282   1.1       mrg 	if (new)
    283   1.1       mrg 		Hash_SetValue(entry, NULL);
    284   1.1       mrg 	rnode = emalloc(sizeof(*rnode));
    285   1.1       mrg 	rnode->entry = entry;
    286   1.1       mrg 	rnode->next = fnode->req_list;
    287   1.1       mrg 	fnode->req_list = rnode;
    288   1.1       mrg }
    289   1.1       mrg 
    290   1.1       mrg /*
    291   1.1       mrg  * add a provision to a filenode.  if this provision doesn't
    292   1.1       mrg  * have a head node, create one here.
    293   1.1       mrg  */
    294   1.1       mrg void
    295  1.10     lukem add_provide(filenode *fnode, char *s)
    296   1.1       mrg {
    297   1.1       mrg 	Hash_Entry *entry;
    298   1.1       mrg 	f_provnode *f_pnode;
    299   1.1       mrg 	provnode *pnode, *head;
    300   1.1       mrg 	int new;
    301   1.1       mrg 
    302   1.1       mrg 	entry = Hash_CreateEntry(provide_hash, s, &new);
    303   1.1       mrg 	head = Hash_GetValue(entry);
    304   1.1       mrg 
    305   1.1       mrg 	/* create a head node if necessary. */
    306   1.1       mrg 	if (head == NULL) {
    307   1.1       mrg 		head = emalloc(sizeof(*head));
    308   1.1       mrg 		head->head = SET;
    309   1.1       mrg 		head->in_progress = RESET;
    310   1.1       mrg 		head->fnode = NULL;
    311   1.1       mrg 		head->last = head->next = NULL;
    312   1.1       mrg 		Hash_SetValue(entry, head);
    313   1.2   thorpej 	}
    314   1.2   thorpej #if 0
    315   1.2   thorpej 	/*
    316   1.2   thorpej 	 * Don't warn about this.  We want to be able to support
    317   1.2   thorpej 	 * scripts that do two complex things:
    318   1.2   thorpej 	 *
    319   1.2   thorpej 	 *	- Two independent scripts which both provide the
    320   1.2   thorpej 	 *	  same thing.  Both scripts must be executed in
    321   1.2   thorpej 	 *	  any order to meet the barrier.  An example:
    322   1.2   thorpej 	 *
    323   1.2   thorpej 	 *		Script 1:
    324   1.2   thorpej 	 *
    325   1.2   thorpej 	 *			PROVIDE: mail
    326   1.2   thorpej 	 *			REQUIRE: LOGIN
    327   1.2   thorpej 	 *
    328   1.2   thorpej 	 *		Script 2:
    329   1.2   thorpej 	 *
    330   1.2   thorpej 	 *			PROVIDE: mail
    331   1.2   thorpej 	 *			REQUIRE: LOGIN
    332   1.2   thorpej 	 *
    333   1.2   thorpej 	 * 	- Two interdependent scripts which both provide the
    334   1.2   thorpej 	 *	  same thing.  Both scripts must be executed in
    335   1.2   thorpej 	 *	  graph order to meet the barrier.  An example:
    336   1.2   thorpej 	 *
    337   1.2   thorpej 	 *		Script 1:
    338   1.2   thorpej 	 *
    339   1.2   thorpej 	 *			PROVIDE: nameservice dnscache
    340   1.2   thorpej 	 *			REQUIRE: SERVERS
    341   1.2   thorpej 	 *
    342   1.2   thorpej 	 *		Script 2:
    343   1.2   thorpej 	 *
    344   1.2   thorpej 	 *			PROVIDE: nameservice nscd
    345   1.2   thorpej 	 *			REQUIRE: dnscache
    346   1.2   thorpej 	 */
    347   1.2   thorpej 	else if (new == 0) {
    348   1.1       mrg 		warnx("file `%s' provides `%s'.", fnode->filename, s);
    349   1.2   thorpej 		warnx("\tpreviously seen in `%s'.",
    350   1.2   thorpej 		    head->next->fnode->filename);
    351   1.1       mrg 	}
    352   1.2   thorpej #endif
    353   1.1       mrg 
    354   1.1       mrg 	pnode = emalloc(sizeof(*pnode));
    355   1.1       mrg 	pnode->head = RESET;
    356   1.1       mrg 	pnode->in_progress = RESET;
    357   1.1       mrg 	pnode->fnode = fnode;
    358   1.1       mrg 	pnode->next = head->next;
    359   1.1       mrg 	pnode->last = head;
    360   1.1       mrg 	head->next = pnode;
    361   1.1       mrg 	if (pnode->next != NULL)
    362   1.1       mrg 		pnode->next->last = pnode;
    363   1.1       mrg 
    364   1.1       mrg 	f_pnode = emalloc(sizeof(*f_pnode));
    365   1.1       mrg 	f_pnode->pnode = pnode;
    366   1.1       mrg 	f_pnode->next = fnode->prov_list;
    367   1.1       mrg 	fnode->prov_list = f_pnode;
    368   1.1       mrg }
    369   1.1       mrg 
    370   1.1       mrg /*
    371   1.1       mrg  * put the BEFORE: lines to a list and handle them later.
    372   1.1       mrg  */
    373   1.1       mrg void
    374  1.10     lukem add_before(filenode *fnode, char *s)
    375   1.1       mrg {
    376   1.1       mrg 
    377   1.9     lukem 	strnode_add(&bl_list, s, fnode);
    378   1.1       mrg }
    379   1.1       mrg 
    380   1.1       mrg /*
    381   1.5       mrg  * add a key to a filenode.
    382   1.5       mrg  */
    383   1.5       mrg void
    384  1.10     lukem add_keyword(filenode *fnode, char *s)
    385   1.5       mrg {
    386   1.5       mrg 
    387   1.5       mrg 	strnode_add(&fnode->keyword_list, s, fnode);
    388   1.5       mrg }
    389   1.5       mrg 
    390   1.5       mrg /*
    391  1.10     lukem  * loop over the rest of a line, giving each word to
    392  1.10     lukem  * add_func() to do the real work.
    393   1.1       mrg  */
    394   1.1       mrg void
    395  1.10     lukem parse_line(filenode *node, char *buffer, void (*add_func)(filenode *, char *))
    396   1.1       mrg {
    397   1.1       mrg 	char *s;
    398   1.1       mrg 
    399   1.1       mrg 	while ((s = strsep(&buffer, " \t\n")) != NULL)
    400   1.1       mrg 		if (*s != '\0')
    401  1.10     lukem 			(*add_func)(node, s);
    402   1.5       mrg }
    403   1.5       mrg 
    404   1.5       mrg /*
    405   1.1       mrg  * given a file name, create a filenode for it, read in lines looking
    406   1.1       mrg  * for provision and requirement lines, building the graphs as needed.
    407   1.1       mrg  */
    408   1.1       mrg void
    409  1.10     lukem crunch_file(char *filename)
    410   1.1       mrg {
    411   1.1       mrg 	FILE *fp;
    412   1.1       mrg 	char *buf;
    413  1.10     lukem 	int require_flag, provide_flag, before_flag, keyword_flag;
    414   1.7     enami 	enum { BEFORE_PARSING, PARSING, PARSING_DONE } state;
    415   1.1       mrg 	filenode *node;
    416   1.1       mrg 	char delims[3] = { '\\', '\\', '\0' };
    417   1.3     enami 	struct stat st;
    418   1.1       mrg 
    419   1.1       mrg 	if ((fp = fopen(filename, "r")) == NULL) {
    420   1.1       mrg 		warn("could not open %s", filename);
    421   1.3     enami 		return;
    422   1.3     enami 	}
    423   1.3     enami 
    424   1.3     enami 	if (fstat(fileno(fp), &st) == -1) {
    425   1.3     enami 		warn("could not stat %s", filename);
    426   1.4     enami 		fclose(fp);
    427   1.3     enami 		return;
    428   1.3     enami 	}
    429   1.3     enami 
    430   1.3     enami 	if (!S_ISREG(st.st_mode)) {
    431   1.8  christos #if 0
    432   1.3     enami 		warnx("%s is not a file", filename);
    433   1.8  christos #endif
    434   1.4     enami 		fclose(fp);
    435   1.1       mrg 		return;
    436   1.1       mrg 	}
    437   1.1       mrg 
    438   1.1       mrg 	node = filenode_new(filename);
    439   1.1       mrg 
    440   1.1       mrg 	/*
    441   1.1       mrg 	 * we don't care about length, line number, don't want # for comments,
    442   1.1       mrg 	 * and have no flags.
    443   1.1       mrg 	 */
    444   1.7     enami 	for (state = BEFORE_PARSING; state != PARSING_DONE &&
    445   1.7     enami 	    (buf = fparseln(fp, NULL, NULL, delims, 0)) != NULL; free(buf)) {
    446  1.10     lukem 		require_flag = provide_flag = before_flag = keyword_flag = 0;
    447   1.1       mrg 		if (strncmp(REQUIRE_STR, buf, REQUIRE_LEN) == 0)
    448   1.1       mrg 			require_flag = REQUIRE_LEN;
    449   1.1       mrg 		else if (strncmp(REQUIRES_STR, buf, REQUIRES_LEN) == 0)
    450   1.1       mrg 			require_flag = REQUIRES_LEN;
    451   1.1       mrg 		else if (strncmp(PROVIDE_STR, buf, PROVIDE_LEN) == 0)
    452   1.1       mrg 			provide_flag = PROVIDE_LEN;
    453   1.1       mrg 		else if (strncmp(PROVIDES_STR, buf, PROVIDES_LEN) == 0)
    454   1.1       mrg 			provide_flag = PROVIDES_LEN;
    455   1.1       mrg 		else if (strncmp(BEFORE_STR, buf, BEFORE_LEN) == 0)
    456   1.1       mrg 			before_flag = BEFORE_LEN;
    457   1.5       mrg 		else if (strncmp(KEYWORD_STR, buf, KEYWORD_LEN) == 0)
    458  1.10     lukem 			keyword_flag = KEYWORD_LEN;
    459   1.5       mrg 		else if (strncmp(KEYWORDS_STR, buf, KEYWORDS_LEN) == 0)
    460  1.10     lukem 			keyword_flag = KEYWORDS_LEN;
    461   1.7     enami 		else {
    462   1.7     enami 			if (state == PARSING)
    463   1.7     enami 				state = PARSING_DONE;
    464   1.7     enami 			continue;
    465   1.7     enami 		}
    466   1.1       mrg 
    467   1.7     enami 		state = PARSING;
    468   1.1       mrg 		if (require_flag)
    469  1.10     lukem 			parse_line(node, buf + require_flag, add_require);
    470   1.6     enami 		else if (provide_flag)
    471  1.10     lukem 			parse_line(node, buf + provide_flag, add_provide);
    472   1.6     enami 		else if (before_flag)
    473  1.10     lukem 			parse_line(node, buf + before_flag,  add_before);
    474  1.10     lukem 		else if (keyword_flag)
    475  1.10     lukem 			parse_line(node, buf + keyword_flag, add_keyword);
    476   1.1       mrg 	}
    477   1.1       mrg 	fclose(fp);
    478   1.1       mrg }
    479   1.1       mrg 
    480   1.1       mrg Hash_Entry *
    481  1.10     lukem make_fake_provision(filenode *node)
    482   1.1       mrg {
    483   1.1       mrg 	Hash_Entry *entry;
    484   1.1       mrg 	f_provnode *f_pnode;
    485   1.1       mrg 	provnode *head, *pnode;
    486   1.1       mrg 	static	int i = 0;
    487   1.1       mrg 	int	new;
    488   1.1       mrg 	char buffer[30];
    489   1.1       mrg 
    490   1.1       mrg 	do {
    491   1.1       mrg 		snprintf(buffer, sizeof buffer, "fake_prov_%08d", i++);
    492   1.1       mrg 		entry = Hash_CreateEntry(provide_hash, buffer, &new);
    493   1.1       mrg 	} while (new == 0);
    494   1.1       mrg 	head = emalloc(sizeof(*head));
    495   1.1       mrg 	head->head = SET;
    496   1.1       mrg 	head->in_progress = RESET;
    497   1.1       mrg 	head->fnode = NULL;
    498   1.1       mrg 	head->last = head->next = NULL;
    499   1.1       mrg 	Hash_SetValue(entry, head);
    500   1.1       mrg 
    501   1.1       mrg 	pnode = emalloc(sizeof(*pnode));
    502   1.1       mrg 	pnode->head = RESET;
    503   1.1       mrg 	pnode->in_progress = RESET;
    504   1.1       mrg 	pnode->fnode = node;
    505   1.1       mrg 	pnode->next = head->next;
    506   1.1       mrg 	pnode->last = head;
    507   1.1       mrg 	head->next = pnode;
    508   1.1       mrg 	if (pnode->next != NULL)
    509   1.1       mrg 		pnode->next->last = pnode;
    510   1.1       mrg 
    511   1.1       mrg 	f_pnode = emalloc(sizeof(*f_pnode));
    512   1.1       mrg 	f_pnode->pnode = pnode;
    513   1.1       mrg 	f_pnode->next = node->prov_list;
    514   1.1       mrg 	node->prov_list = f_pnode;
    515   1.1       mrg 
    516   1.1       mrg 	return (entry);
    517   1.1       mrg }
    518   1.1       mrg 
    519   1.1       mrg /*
    520   1.1       mrg  * go through the BEFORE list, inserting requirements into the graph(s)
    521   1.1       mrg  * as required.  in the before list, for each entry B, we have a file F
    522   1.1       mrg  * and a string S.  we create a "fake" provision (P) that F provides.
    523   1.1       mrg  * for each entry in the provision list for S, add a requirement to
    524   1.1       mrg  * that provisions filenode for P.
    525   1.1       mrg  */
    526   1.1       mrg void
    527  1.10     lukem insert_before(void)
    528   1.1       mrg {
    529   1.1       mrg 	Hash_Entry *entry, *fake_prov_entry;
    530   1.1       mrg 	provnode *pnode;
    531   1.1       mrg 	f_reqnode *rnode;
    532   1.5       mrg 	strnodelist *bl;
    533   1.1       mrg 	int new;
    534   1.1       mrg 
    535   1.1       mrg 	while (bl_list != NULL) {
    536   1.1       mrg 		bl = bl_list->next;
    537   1.1       mrg 
    538   1.1       mrg 		fake_prov_entry = make_fake_provision(bl_list->node);
    539   1.1       mrg 
    540   1.1       mrg 		entry = Hash_CreateEntry(provide_hash, bl_list->s, &new);
    541   1.1       mrg 		if (new == 1)
    542  1.13    rumble 			warnx("file `%s' is before unknown provision `%s'",
    543  1.13    rumble 			    bl_list->node->filename, bl_list->s);
    544   1.1       mrg 
    545   1.1       mrg 		for (pnode = Hash_GetValue(entry); pnode; pnode = pnode->next) {
    546   1.1       mrg 			if (pnode->head)
    547   1.1       mrg 				continue;
    548   1.1       mrg 
    549   1.1       mrg 			rnode = emalloc(sizeof(*rnode));
    550   1.1       mrg 			rnode->entry = fake_prov_entry;
    551   1.1       mrg 			rnode->next = pnode->fnode->req_list;
    552   1.1       mrg 			pnode->fnode->req_list = rnode;
    553   1.1       mrg 		}
    554   1.1       mrg 
    555   1.1       mrg 		free(bl_list);
    556   1.1       mrg 		bl_list = bl;
    557   1.1       mrg 	}
    558   1.1       mrg }
    559   1.1       mrg 
    560   1.1       mrg /*
    561   1.1       mrg  * loop over all the files calling crunch_file() on them to do the
    562   1.1       mrg  * real work.  after we have built all the nodes, insert the BEFORE:
    563   1.1       mrg  * lines into graph(s).
    564   1.1       mrg  */
    565   1.1       mrg void
    566  1.10     lukem crunch_all_files(void)
    567   1.1       mrg {
    568   1.1       mrg 	int i;
    569   1.1       mrg 
    570   1.1       mrg 	for (i = 0; i < file_count; i++)
    571   1.1       mrg 		crunch_file(file_list[i]);
    572   1.1       mrg 	insert_before();
    573   1.1       mrg }
    574   1.1       mrg 
    575   1.1       mrg /*
    576   1.1       mrg  * below are the functions that traverse the graphs we have built
    577   1.1       mrg  * finding out the desired ordering, printing each file in turn.
    578   1.1       mrg  * if missing requirements, or cyclic graphs are detected, a
    579   1.1       mrg  * warning will be issued, and we will continue on..
    580   1.1       mrg  */
    581   1.1       mrg 
    582   1.1       mrg /*
    583   1.1       mrg  * given a requirement node (in a filename) we attempt to satisfy it.
    584   1.1       mrg  * we do some sanity checking first, to ensure that we have providers,
    585   1.1       mrg  * aren't already satisfied and aren't already being satisfied (ie,
    586   1.1       mrg  * cyclic).  if we pass all this, we loop over the provision list
    587   1.1       mrg  * calling do_file() (enter recursion) for each filenode in this
    588   1.1       mrg  * provision.
    589   1.1       mrg  */
    590   1.1       mrg void
    591  1.10     lukem satisfy_req(f_reqnode *rnode, char *filename)
    592   1.1       mrg {
    593   1.1       mrg 	Hash_Entry *entry;
    594   1.1       mrg 	provnode *head;
    595   1.1       mrg 
    596   1.1       mrg 	entry = rnode->entry;
    597   1.1       mrg 	head = Hash_GetValue(entry);
    598   1.1       mrg 
    599   1.1       mrg 	if (head == NULL) {
    600   1.1       mrg 		warnx("requirement `%s' in file `%s' has no providers.",
    601   1.1       mrg 		    Hash_GetKey(entry), filename);
    602   1.1       mrg 		exit_code = 1;
    603   1.1       mrg 		return;
    604   1.1       mrg 	}
    605   1.1       mrg 
    606   1.1       mrg 	/* return if the requirement is already satisfied. */
    607   1.1       mrg 	if (head->next == NULL)
    608   1.1       mrg 		return;
    609   1.1       mrg 
    610   1.1       mrg 	/*
    611   1.1       mrg 	 * if list is marked as in progress,
    612   1.1       mrg 	 *	print that there is a circular dependency on it and abort
    613   1.1       mrg 	 */
    614   1.1       mrg 	if (head->in_progress == SET) {
    615   1.1       mrg 		warnx("Circular dependency on provision `%s' in file `%s'.",
    616   1.1       mrg 		    Hash_GetKey(entry), filename);
    617   1.1       mrg 		exit_code = 1;
    618   1.1       mrg 		return;
    619   1.1       mrg 	}
    620   1.1       mrg 
    621   1.1       mrg 	head->in_progress = SET;
    622   1.1       mrg 
    623   1.1       mrg 	/*
    624   1.1       mrg 	 * while provision_list is not empty
    625   1.1       mrg 	 *	do_file(first_member_of(provision_list));
    626   1.1       mrg 	 */
    627   1.1       mrg 	while (head->next != NULL)
    628   1.1       mrg 		do_file(head->next->fnode);
    629   1.1       mrg }
    630   1.1       mrg 
    631   1.5       mrg int
    632  1.10     lukem skip_ok(filenode *fnode)
    633   1.5       mrg {
    634   1.5       mrg 	strnodelist *s;
    635   1.5       mrg 	strnodelist *k;
    636   1.5       mrg 
    637   1.5       mrg 	for (s = skip_list; s; s = s->next)
    638   1.5       mrg 		for (k = fnode->keyword_list; k; k = k->next)
    639   1.5       mrg 			if (strcmp(k->s, s->s) == 0)
    640   1.5       mrg 				return (0);
    641   1.5       mrg 
    642   1.5       mrg 	return (1);
    643   1.5       mrg }
    644   1.5       mrg 
    645   1.5       mrg int
    646  1.10     lukem keep_ok(filenode *fnode)
    647   1.5       mrg {
    648   1.5       mrg 	strnodelist *s;
    649   1.5       mrg 	strnodelist *k;
    650   1.5       mrg 
    651   1.5       mrg 	for (s = keep_list; s; s = s->next)
    652   1.5       mrg 		for (k = fnode->keyword_list; k; k = k->next)
    653   1.5       mrg 			if (strcmp(k->s, s->s) == 0)
    654   1.5       mrg 				return (1);
    655   1.5       mrg 
    656   1.5       mrg 	/* an empty keep_list means every one */
    657   1.5       mrg 	return (!keep_list);
    658   1.5       mrg }
    659   1.5       mrg 
    660   1.1       mrg /*
    661   1.1       mrg  * given a filenode, we ensure we are not a cyclic graph.  if this
    662   1.1       mrg  * is ok, we loop over the filenodes requirements, calling satisfy_req()
    663   1.1       mrg  * for each of them.. once we have done this, remove this filenode
    664   1.1       mrg  * from each provision table, as we are now done.
    665   1.1       mrg  */
    666   1.1       mrg void
    667  1.10     lukem do_file(filenode *fnode)
    668   1.1       mrg {
    669   1.1       mrg 	f_reqnode *r, *r_tmp;
    670   1.1       mrg 	f_provnode *p, *p_tmp;
    671   1.1       mrg 	provnode *pnode;
    672   1.1       mrg 	int was_set;
    673   1.1       mrg 
    674   1.1       mrg 	DPRINTF((stderr, "do_file on %s.\n", fnode->filename));
    675   1.1       mrg 
    676   1.1       mrg 	/*
    677   1.1       mrg 	 * if fnode is marked as in progress,
    678   1.1       mrg 	 *	 print that fnode; is circularly depended upon and abort.
    679   1.1       mrg 	 */
    680   1.1       mrg 	if (fnode->in_progress == SET) {
    681   1.1       mrg 		warnx("Circular dependency on file `%s'.",
    682   1.1       mrg 			fnode->filename);
    683   1.1       mrg 		was_set = exit_code = 1;
    684   1.1       mrg 	} else
    685   1.1       mrg 		was_set = 0;
    686   1.1       mrg 
    687   1.1       mrg 	/* mark fnode */
    688   1.1       mrg 	fnode->in_progress = SET;
    689   1.1       mrg 
    690   1.1       mrg 	/*
    691   1.1       mrg 	 * for each requirement of fnode -> r
    692   1.1       mrg 	 *	satisfy_req(r, filename)
    693   1.1       mrg 	 */
    694   1.1       mrg 	r = fnode->req_list;
    695   1.1       mrg 	while (r != NULL) {
    696   1.1       mrg 		r_tmp = r;
    697   1.1       mrg 		satisfy_req(r, fnode->filename);
    698   1.1       mrg 		r = r->next;
    699   1.1       mrg 		free(r_tmp);
    700   1.1       mrg 	}
    701   1.1       mrg 	fnode->req_list = NULL;
    702   1.1       mrg 
    703   1.1       mrg 	/*
    704   1.1       mrg 	 * for each provision of fnode -> p
    705   1.1       mrg 	 *	remove fnode from provision list for p in hash table
    706   1.1       mrg 	 */
    707   1.1       mrg 	p = fnode->prov_list;
    708   1.1       mrg 	while (p != NULL) {
    709   1.1       mrg 		p_tmp = p;
    710   1.1       mrg 		pnode = p->pnode;
    711   1.1       mrg 		if (pnode->next != NULL) {
    712   1.1       mrg 			pnode->next->last = pnode->last;
    713   1.1       mrg 		}
    714   1.1       mrg 		if (pnode->last != NULL) {
    715   1.1       mrg 			pnode->last->next = pnode->next;
    716   1.1       mrg 		}
    717   1.1       mrg 		free(pnode);
    718   1.1       mrg 		p = p->next;
    719   1.1       mrg 		free(p_tmp);
    720   1.1       mrg 	}
    721   1.1       mrg 	fnode->prov_list = NULL;
    722   1.1       mrg 
    723   1.1       mrg 	/* do_it(fnode) */
    724   1.1       mrg 	DPRINTF((stderr, "next do: "));
    725   1.1       mrg 
    726   1.1       mrg 	/* if we were already in progress, don't print again */
    727   1.5       mrg 	if (was_set == 0 && skip_ok(fnode) && keep_ok(fnode))
    728   1.1       mrg 		printf("%s\n", fnode->filename);
    729   1.1       mrg 
    730   1.1       mrg 	if (fnode->next != NULL) {
    731   1.1       mrg 		fnode->next->last = fnode->last;
    732   1.1       mrg 	}
    733   1.1       mrg 	if (fnode->last != NULL) {
    734   1.1       mrg 		fnode->last->next = fnode->next;
    735   1.1       mrg 	}
    736   1.1       mrg 
    737   1.1       mrg 	DPRINTF((stderr, "nuking %s\n", fnode->filename));
    738   1.1       mrg 	free(fnode->filename);
    739   1.1       mrg 	free(fnode);
    740   1.1       mrg }
    741   1.1       mrg 
    742   1.1       mrg void
    743  1.10     lukem generate_ordering(void)
    744   1.1       mrg {
    745   1.1       mrg 
    746   1.1       mrg 	/*
    747   1.1       mrg 	 * while there remain undone files{f},
    748   1.1       mrg 	 *	pick an arbitrary f, and do_file(f)
    749   1.1       mrg 	 * Note that the first file in the file list is perfectly
    750   1.1       mrg 	 * arbitrary, and easy to find, so we use that.
    751   1.1       mrg 	 */
    752   1.1       mrg 
    753   1.1       mrg 	/*
    754   1.1       mrg 	 * N.B.: the file nodes "self delete" after they execute, so
    755   1.1       mrg 	 * after each iteration of the loop, the head will be pointing
    756   1.1       mrg 	 * to something totally different. The loop ends up being
    757   1.1       mrg 	 * executed only once for every strongly connected set of
    758   1.1       mrg 	 * nodes.
    759   1.1       mrg 	 */
    760   1.1       mrg 	while (fn_head->next != NULL) {
    761   1.1       mrg 		DPRINTF((stderr, "generate on %s\n", fn_head->next->filename));
    762   1.1       mrg 		do_file(fn_head->next);
    763   1.1       mrg 	}
    764   1.1       mrg }
    765