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