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