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