1 # if 0
2 /* $NetBSD: rcorder.c,v 1.7 2000/08/04 07:33:55 enami Exp $ */
3 #endif
4
5 /*-
6 * SPDX-License-Identifier: BSD-2-Clause
7 *
8 * Copyright (c) 1998, 1999 Matthew R. Green
9 * All rights reserved.
10 * Copyright (c) 1998
11 * Perry E. Metzger. All rights reserved.
12 * Copyright (c) 2020
13 * Boris N. Lytochkin. All rights reserved.
14 *
15 * Redistribution and use in source and binary forms, with or without
16 * modification, are permitted provided that the following conditions
17 * are met:
18 * 1. Redistributions of source code must retain the above copyright
19 * notice, this list of conditions and the following disclaimer.
20 * 2. Redistributions in binary form must reproduce the above copyright
21 * notice, this list of conditions and the following disclaimer in the
22 * documentation and/or other materials provided with the distribution.
23 * 3. All advertising materials mentioning features or use of this software
24 * must display the following acknowledgement:
25 * This product includes software developed for the NetBSD Project
26 * by Perry E. Metzger.
27 * 4. The name of the author may not be used to endorse or promote products
28 * derived from this software without specific prior written permission.
29 *
30 * THIS SOFTWARE IS PROVIDED BY THE AUTHOR ``AS IS'' AND ANY EXPRESS OR
31 * IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE IMPLIED WARRANTIES
32 * OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE ARE DISCLAIMED.
33 * IN NO EVENT SHALL THE AUTHOR BE LIABLE FOR ANY DIRECT, INDIRECT,
34 * INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT
35 * NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE,
36 * DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY
37 * THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT
38 * (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF
39 * THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
40 */
41
42 #include <sys/types.h>
43 #include <sys/stat.h>
44
45 #include <err.h>
46 #include <stdio.h>
47 #include <libutil.h>
48 #include <stdlib.h>
49 #include <string.h>
50 #include <unistd.h>
51 #include <libgen.h>
52 #include <stdbool.h>
53
54 #include "ealloc.h"
55 #include "sprite.h"
56 #include "hash.h"
57
58 #ifdef DEBUG
59 static int debug = 0;
60 # define DPRINTF(args) if (debug) { fflush(stdout); fprintf args; }
61 #else
62 # define DPRINTF(args)
63 #endif
64
65 #define REQUIRE_STR "# REQUIRE:"
66 #define REQUIRE_LEN (sizeof(REQUIRE_STR) - 1)
67 #define REQUIRES_STR "# REQUIRES:"
68 #define REQUIRES_LEN (sizeof(REQUIRES_STR) - 1)
69 #define PROVIDE_STR "# PROVIDE:"
70 #define PROVIDE_LEN (sizeof(PROVIDE_STR) - 1)
71 #define PROVIDES_STR "# PROVIDES:"
72 #define PROVIDES_LEN (sizeof(PROVIDES_STR) - 1)
73 #define BEFORE_STR "# BEFORE:"
74 #define BEFORE_LEN (sizeof(BEFORE_STR) - 1)
75 #define KEYWORD_STR "# KEYWORD:"
76 #define KEYWORD_LEN (sizeof(KEYWORD_STR) - 1)
77 #define KEYWORDS_STR "# KEYWORDS:"
78 #define KEYWORDS_LEN (sizeof(KEYWORDS_STR) - 1)
79
80 #define FAKE_PROV_NAME "fake_prov_"
81
82 static int exit_code;
83 static int file_count;
84 static char **file_list;
85
86 #define TRUE 1
87 #define FALSE 0
88 typedef bool flag;
89 #define SET TRUE
90 #define RESET FALSE
91
92 static flag do_graphviz = false;
93 static flag do_parallel = false;
94
95 static Hash_Table provide_hash_s, *provide_hash;
96
97 typedef struct provnode provnode;
98 typedef struct filenode filenode;
99 typedef struct f_provnode f_provnode;
100 typedef struct f_reqnode f_reqnode;
101 typedef struct strnodelist strnodelist;
102
103 struct provnode {
104 flag head;
105 flag in_progress;
106 int sequence;
107 filenode *fnode;
108 provnode *next, *last;
109 };
110
111 struct f_provnode {
112 provnode *pnode;
113 Hash_Entry *entry;
114 f_provnode *next;
115 };
116
117 struct f_reqnode {
118 Hash_Entry *entry;
119 f_reqnode *next;
120 };
121
122 struct strnodelist {
123 filenode *node;
124 strnodelist *next;
125 char s[1];
126 };
127
128 struct filenode {
129 char *filename;
130 flag in_progress;
131 filenode *next, *last;
132 f_reqnode *req_list;
133 f_provnode *prov_list;
134 strnodelist *keyword_list;
135 int issues_count;
136 int sequence;
137 };
138
139 static filenode fn_head_s, *fn_head, **fn_seqlist;
140 static int max_sequence = 0;
141
142 static strnodelist *bl_list;
143 static strnodelist *keep_list;
144 static strnodelist *skip_list;
145
146 static void do_file(filenode *fnode, strnodelist *);
147 static void strnode_add(strnodelist **, char *, filenode *);
148 static int skip_ok(filenode *fnode);
149 static int keep_ok(filenode *fnode);
150 static char *generate_loop_for_req(strnodelist *, provnode *, filenode *);
151 static void satisfy_req(f_reqnode *rnode, filenode *fnode, strnodelist *);
152 static void crunch_file(char *);
153 static void parse_require(filenode *, char *);
154 static void parse_provide(filenode *, char *);
155 static void parse_before(filenode *, char *);
156 static void parse_keywords(filenode *, char *);
157 static filenode *filenode_new(char *);
158 static void add_require(filenode *, char *);
159 static void add_provide(filenode *, char *);
160 static void add_before(filenode *, char *);
161 static void add_keyword(filenode *, char *);
162 static void insert_before(void);
163 static Hash_Entry *make_fake_provision(filenode *);
164 static void crunch_all_files(void);
165 static void initialize(void);
166 static void generate_graphviz_header(void);
167 static void generate_graphviz_footer(void);
168 static void generate_graphviz_file_links(Hash_Entry *, filenode *);
169 static void generate_graphviz_providers(void);
170 static inline int is_fake_prov(const char *);
171 static int sequence_cmp(const void *, const void *);
172 static void generate_ordering(void);
173
174 int
main(int argc,char * argv[])175 main(int argc, char *argv[])
176 {
177 int ch;
178
179 while ((ch = getopt(argc, argv, "dgk:ps:")) != -1)
180 switch (ch) {
181 case 'd':
182 #ifdef DEBUG
183 debug = 1;
184 #else
185 warnx("debugging not compiled in, -d ignored");
186 #endif
187 break;
188 case 'g':
189 do_graphviz = true;
190 break;
191 case 'k':
192 strnode_add(&keep_list, optarg, 0);
193 break;
194 case 'p':
195 do_parallel = true;
196 break;
197 case 's':
198 strnode_add(&skip_list, optarg, 0);
199 break;
200 default:
201 /* XXX should crunch it? */
202 break;
203 }
204 argc -= optind;
205 argv += optind;
206
207 file_count = argc;
208 file_list = argv;
209
210 DPRINTF((stderr, "parse_args\n"));
211 initialize();
212 DPRINTF((stderr, "initialize\n"));
213 generate_graphviz_header();
214 crunch_all_files();
215 DPRINTF((stderr, "crunch_all_files\n"));
216 generate_graphviz_providers();
217 generate_ordering();
218 DPRINTF((stderr, "generate_ordering\n"));
219 generate_graphviz_footer();
220
221 exit(exit_code);
222 }
223
224 /*
225 * initialise various variables.
226 */
227 static void
initialize(void)228 initialize(void)
229 {
230
231 fn_head = &fn_head_s;
232
233 provide_hash = &provide_hash_s;
234 Hash_InitTable(provide_hash, file_count);
235 }
236
237 /* generic function to insert a new strnodelist element */
238 static void
strnode_add(strnodelist ** listp,char * s,filenode * fnode)239 strnode_add(strnodelist **listp, char *s, filenode *fnode)
240 {
241 strnodelist *ent;
242
243 ent = emalloc(sizeof *ent + strlen(s));
244 ent->node = fnode;
245 strcpy(ent->s, s);
246 ent->next = *listp;
247 *listp = ent;
248 }
249
250 /*
251 * below are the functions that deal with creating the lists
252 * from the filename's given dependencies and provisions
253 * in each of these files. no ordering or checking is done here.
254 */
255
256 /*
257 * we have a new filename, create a new filenode structure.
258 * fill in the bits, and put it in the filenode linked list
259 */
260 static filenode *
filenode_new(char * filename)261 filenode_new(char *filename)
262 {
263 filenode *temp;
264
265 temp = emalloc(sizeof(*temp));
266 memset(temp, 0, sizeof(*temp));
267 temp->filename = estrdup(filename);
268 temp->req_list = NULL;
269 temp->prov_list = NULL;
270 temp->keyword_list = NULL;
271 temp->in_progress = RESET;
272 /*
273 * link the filenode into the list of filenodes.
274 * note that the double linking means we can delete a
275 * filenode without searching for where it belongs.
276 */
277 temp->next = fn_head->next;
278 if (temp->next != NULL)
279 temp->next->last = temp;
280 temp->last = fn_head;
281 fn_head->next = temp;
282 return (temp);
283 }
284
285 /*
286 * add a requirement to a filenode.
287 */
288 static void
add_require(filenode * fnode,char * s)289 add_require(filenode *fnode, char *s)
290 {
291 Hash_Entry *entry;
292 f_reqnode *rnode;
293 int new;
294
295 entry = Hash_CreateEntry(provide_hash, s, &new);
296 if (new)
297 Hash_SetValue(entry, NULL);
298 rnode = emalloc(sizeof(*rnode));
299 rnode->entry = entry;
300 rnode->next = fnode->req_list;
301 fnode->req_list = rnode;
302 }
303
304 /*
305 * add a provision to a filenode. if this provision doesn't
306 * have a head node, create one here.
307 */
308 static void
add_provide(filenode * fnode,char * s)309 add_provide(filenode *fnode, char *s)
310 {
311 Hash_Entry *entry;
312 f_provnode *f_pnode;
313 provnode *pnode, *head;
314 int new;
315
316 entry = Hash_CreateEntry(provide_hash, s, &new);
317 head = Hash_GetValue(entry);
318
319 /* create a head node if necessary. */
320 if (head == NULL) {
321 head = emalloc(sizeof(*head));
322 head->head = SET;
323 head->in_progress = RESET;
324 head->fnode = NULL;
325 head->sequence = 0;
326 head->last = head->next = NULL;
327 Hash_SetValue(entry, head);
328 }
329 #if 0
330 /*
331 * Don't warn about this. We want to be able to support
332 * scripts that do two complex things:
333 *
334 * - Two independent scripts which both provide the
335 * same thing. Both scripts must be executed in
336 * any order to meet the barrier. An example:
337 *
338 * Script 1:
339 *
340 * PROVIDE: mail
341 * REQUIRE: LOGIN
342 *
343 * Script 2:
344 *
345 * PROVIDE: mail
346 * REQUIRE: LOGIN
347 *
348 * - Two interdependent scripts which both provide the
349 * same thing. Both scripts must be executed in
350 * graph order to meet the barrier. An example:
351 *
352 * Script 1:
353 *
354 * PROVIDE: nameservice dnscache
355 * REQUIRE: SERVERS
356 *
357 * Script 2:
358 *
359 * PROVIDE: nameservice nscd
360 * REQUIRE: dnscache
361 */
362 else if (new == 0) {
363 warnx("file `%s' provides `%s'.", fnode->filename, s);
364 warnx("\tpreviously seen in `%s'.",
365 head->next->fnode->filename);
366 }
367 #endif
368
369 pnode = emalloc(sizeof(*pnode));
370 pnode->head = RESET;
371 pnode->in_progress = RESET;
372 pnode->fnode = fnode;
373 pnode->next = head->next;
374 pnode->last = head;
375 head->next = pnode;
376 if (pnode->next != NULL)
377 pnode->next->last = pnode;
378
379 f_pnode = emalloc(sizeof(*f_pnode));
380 f_pnode->pnode = pnode;
381 f_pnode->entry = entry;
382 f_pnode->next = fnode->prov_list;
383 fnode->prov_list = f_pnode;
384 }
385
386 /*
387 * put the BEFORE: lines to a list and handle them later.
388 */
389 static void
add_before(filenode * fnode,char * s)390 add_before(filenode *fnode, char *s)
391 {
392 strnodelist *bf_ent;
393
394 bf_ent = emalloc(sizeof *bf_ent + strlen(s));
395 bf_ent->node = fnode;
396 strcpy(bf_ent->s, s);
397 bf_ent->next = bl_list;
398 bl_list = bf_ent;
399 }
400
401 /*
402 * add a key to a filenode.
403 */
404 static void
add_keyword(filenode * fnode,char * s)405 add_keyword(filenode *fnode, char *s)
406 {
407
408 strnode_add(&fnode->keyword_list, s, fnode);
409 }
410
411 /*
412 * loop over the rest of a REQUIRE line, giving each word to
413 * add_require() to do the real work.
414 */
415 static void
parse_require(filenode * node,char * buffer)416 parse_require(filenode *node, char *buffer)
417 {
418 char *s;
419
420 while ((s = strsep(&buffer, " \t\n")) != NULL)
421 if (*s != '\0')
422 add_require(node, s);
423 }
424
425 /*
426 * loop over the rest of a PROVIDE line, giving each word to
427 * add_provide() to do the real work.
428 */
429 static void
parse_provide(filenode * node,char * buffer)430 parse_provide(filenode *node, char *buffer)
431 {
432 char *s;
433
434 while ((s = strsep(&buffer, " \t\n")) != NULL)
435 if (*s != '\0')
436 add_provide(node, s);
437 }
438
439 /*
440 * loop over the rest of a BEFORE line, giving each word to
441 * add_before() to do the real work.
442 */
443 static void
parse_before(filenode * node,char * buffer)444 parse_before(filenode *node, char *buffer)
445 {
446 char *s;
447
448 while ((s = strsep(&buffer, " \t\n")) != NULL)
449 if (*s != '\0')
450 add_before(node, s);
451 }
452
453 /*
454 * loop over the rest of a KEYWORD line, giving each word to
455 * add_keyword() to do the real work.
456 */
457 static void
parse_keywords(filenode * node,char * buffer)458 parse_keywords(filenode *node, char *buffer)
459 {
460 char *s;
461
462 while ((s = strsep(&buffer, " \t\n")) != NULL)
463 if (*s != '\0')
464 add_keyword(node, s);
465 }
466
467 /*
468 * given a file name, create a filenode for it, read in lines looking
469 * for provision and requirement lines, building the graphs as needed.
470 */
471 static void
crunch_file(char * filename)472 crunch_file(char *filename)
473 {
474 FILE *fp;
475 char *buf;
476 int require_flag, provide_flag, before_flag, keywords_flag;
477 enum { BEFORE_PARSING, PARSING, PARSING_DONE } state;
478 filenode *node;
479 char delims[3] = { '\\', '\\', '\0' };
480 struct stat st;
481
482 if ((fp = fopen(filename, "r")) == NULL) {
483 warn("could not open %s", filename);
484 return;
485 }
486
487 if (fstat(fileno(fp), &st) == -1) {
488 warn("could not stat %s", filename);
489 fclose(fp);
490 return;
491 }
492
493 if (!S_ISREG(st.st_mode)) {
494 #if 0
495 warnx("%s is not a file", filename);
496 #endif
497 fclose(fp);
498 return;
499 }
500
501 node = filenode_new(filename);
502
503 /*
504 * we don't care about length, line number, don't want # for comments,
505 * and have no flags.
506 */
507 for (state = BEFORE_PARSING; state != PARSING_DONE &&
508 (buf = fparseln(fp, NULL, NULL, delims, 0)) != NULL; free(buf)) {
509 require_flag = provide_flag = before_flag = keywords_flag = 0;
510 if (strncmp(REQUIRE_STR, buf, REQUIRE_LEN) == 0)
511 require_flag = REQUIRE_LEN;
512 else if (strncmp(REQUIRES_STR, buf, REQUIRES_LEN) == 0)
513 require_flag = REQUIRES_LEN;
514 else if (strncmp(PROVIDE_STR, buf, PROVIDE_LEN) == 0)
515 provide_flag = PROVIDE_LEN;
516 else if (strncmp(PROVIDES_STR, buf, PROVIDES_LEN) == 0)
517 provide_flag = PROVIDES_LEN;
518 else if (strncmp(BEFORE_STR, buf, BEFORE_LEN) == 0)
519 before_flag = BEFORE_LEN;
520 else if (strncmp(KEYWORD_STR, buf, KEYWORD_LEN) == 0)
521 keywords_flag = KEYWORD_LEN;
522 else if (strncmp(KEYWORDS_STR, buf, KEYWORDS_LEN) == 0)
523 keywords_flag = KEYWORDS_LEN;
524 else {
525 if (state == PARSING)
526 state = PARSING_DONE;
527 continue;
528 }
529
530 state = PARSING;
531 if (require_flag)
532 parse_require(node, buf + require_flag);
533 else if (provide_flag)
534 parse_provide(node, buf + provide_flag);
535 else if (before_flag)
536 parse_before(node, buf + before_flag);
537 else if (keywords_flag)
538 parse_keywords(node, buf + keywords_flag);
539 }
540 fclose(fp);
541 }
542
543 static Hash_Entry *
make_fake_provision(filenode * node)544 make_fake_provision(filenode *node)
545 {
546 Hash_Entry *entry;
547 f_provnode *f_pnode;
548 provnode *head, *pnode;
549 static int i = 0;
550 int new;
551 char buffer[30];
552
553 do {
554 snprintf(buffer, sizeof buffer, FAKE_PROV_NAME "%08d", i++);
555 entry = Hash_CreateEntry(provide_hash, buffer, &new);
556 } while (new == 0);
557 head = emalloc(sizeof(*head));
558 head->head = SET;
559 head->in_progress = RESET;
560 head->fnode = NULL;
561 head->last = head->next = NULL;
562 Hash_SetValue(entry, head);
563
564 pnode = emalloc(sizeof(*pnode));
565 pnode->head = RESET;
566 pnode->in_progress = RESET;
567 pnode->fnode = node;
568 pnode->next = head->next;
569 pnode->last = head;
570 head->next = pnode;
571 if (pnode->next != NULL)
572 pnode->next->last = pnode;
573
574 f_pnode = emalloc(sizeof(*f_pnode));
575 f_pnode->entry = entry;
576 f_pnode->pnode = pnode;
577 f_pnode->next = node->prov_list;
578 node->prov_list = f_pnode;
579
580 return (entry);
581 }
582
583 /*
584 * go through the BEFORE list, inserting requirements into the graph(s)
585 * as required. in the before list, for each entry B, we have a file F
586 * and a string S. we create a "fake" provision (P) that F provides.
587 * for each entry in the provision list for S, add a requirement to
588 * that provisions filenode for P.
589 */
590 static void
insert_before(void)591 insert_before(void)
592 {
593 Hash_Entry *entry, *fake_prov_entry;
594 provnode *pnode;
595 f_reqnode *rnode;
596 strnodelist *bl;
597 int new;
598
599 while (bl_list != NULL) {
600 bl = bl_list->next;
601
602 fake_prov_entry = make_fake_provision(bl_list->node);
603
604 entry = Hash_CreateEntry(provide_hash, bl_list->s, &new);
605 if (new == 1)
606 warnx("file `%s' is before unknown provision `%s'", bl_list->node->filename, bl_list->s);
607
608 if (new == 1 && do_graphviz == true)
609 generate_graphviz_file_links(
610 Hash_FindEntry(provide_hash, bl_list->s),
611 bl_list->node);
612
613 for (pnode = Hash_GetValue(entry); pnode; pnode = pnode->next) {
614 if (pnode->head)
615 continue;
616
617 rnode = emalloc(sizeof(*rnode));
618 rnode->entry = fake_prov_entry;
619 rnode->next = pnode->fnode->req_list;
620 pnode->fnode->req_list = rnode;
621 }
622
623 free(bl_list);
624 bl_list = bl;
625 }
626 }
627
628 /*
629 * loop over all the files calling crunch_file() on them to do the
630 * real work. after we have built all the nodes, insert the BEFORE:
631 * lines into graph(s).
632 */
633 static void
crunch_all_files(void)634 crunch_all_files(void)
635 {
636 int i;
637
638 for (i = 0; i < file_count; i++)
639 crunch_file(file_list[i]);
640 insert_before();
641 }
642
643 static inline int
is_fake_prov(const char * name)644 is_fake_prov(const char *name)
645 {
646
647 return (name == strstr(name, FAKE_PROV_NAME));
648 }
649
650 /* loop though provide list of vnode drawing all non-fake dependencies */
651 static void
generate_graphviz_file_links(Hash_Entry * entry,filenode * fnode)652 generate_graphviz_file_links(Hash_Entry *entry, filenode *fnode)
653 {
654 char *dep_name, *fname;
655 provnode *head;
656 f_provnode *fpnode, *rfpnode;
657 int is_before = 0;
658
659 dep_name = Hash_GetKey(entry);
660 if (is_fake_prov(dep_name))
661 is_before = 1;
662 head = Hash_GetValue(entry);
663
664 for (fpnode = fnode->prov_list; fpnode && fpnode->entry;
665 fpnode = fpnode->next) {
666 fname = Hash_GetKey(fpnode->entry);
667 if (is_fake_prov(fname))
668 continue;
669 rfpnode = NULL;
670 do {
671 if (rfpnode)
672 dep_name = Hash_GetKey(rfpnode->entry);
673 else
674 dep_name = Hash_GetKey(entry);
675
676 if (!is_fake_prov(dep_name)) {
677 printf("\"%s\" -> \"%s\" [%s%s];\n",
678 fname, dep_name,
679 /* edge style */
680 (is_before ? "style=dashed" : "style=solid"),
681 /* circular dep? */
682 ((head == NULL ||
683 (head->next && head->in_progress == SET)) ?
684 ", color=red, penwidth=4" : ""));
685 if (rfpnode == NULL)
686 break;
687 }
688 /* dependency is solved already */
689 if (head == NULL || head->next == NULL)
690 break;
691
692 if (rfpnode == NULL)
693 rfpnode = head->next->fnode->prov_list;
694 else
695 rfpnode = rfpnode->next;
696 } while (rfpnode);
697 }
698 }
699
700 /*
701 * Walk the stack, find the looping point and generate traceback.
702 * NULL is returned on failure, otherwize pointer to a buffer holding
703 * text representation is returned, caller must run free(3) for the
704 * pointer.
705 */
706 static char *
generate_loop_for_req(strnodelist * stack_tail,provnode * head,filenode * fnode)707 generate_loop_for_req(strnodelist *stack_tail, provnode *head,
708 filenode *fnode)
709 {
710 provnode *pnode;
711 strnodelist *stack_ptr, *loop_entry;
712 char *buf, **revstack;
713 size_t bufsize;
714 int i, stack_depth;
715
716 loop_entry = NULL;
717 /* fast forward stack to the component that is required now */
718 for (pnode = head->next; pnode; pnode = pnode->next) {
719 if (loop_entry)
720 break;
721 stack_depth = 0;
722 for (stack_ptr = stack_tail; stack_ptr;
723 stack_ptr = stack_ptr->next) {
724 stack_depth++;
725 if (stack_ptr->node == pnode->fnode) {
726 loop_entry = stack_ptr;
727 break;
728 }
729 }
730 }
731
732 if (loop_entry == NULL)
733 return (NULL);
734
735 stack_depth += 2; /* fnode + loop_entry */
736 revstack = emalloc(sizeof(char *) * stack_depth);
737 bzero(revstack, (sizeof(char *) * stack_depth));
738
739 /* reverse stack and estimate buffer size to allocate */
740 bufsize = 1; /* tralining \0 */
741
742 revstack[stack_depth - 1] = loop_entry->node->filename;
743 bufsize += strlen(revstack[stack_depth - 1]);
744
745 revstack[stack_depth - 2] = fnode->filename;
746 bufsize += strlen(revstack[stack_depth - 2]);
747 fnode->issues_count++;
748
749 stack_ptr = stack_tail;
750 for (i = stack_depth - 3; i >= 0; i--) {
751 revstack[i] = stack_ptr->node->filename;
752 stack_ptr->node->issues_count++;
753 stack_ptr = stack_ptr->next;
754 bufsize += strlen(revstack[i]);
755 }
756 bufsize += strlen(" -> ") * (stack_depth - 1);
757
758 buf = emalloc(bufsize);
759 bzero(buf, bufsize);
760
761 for (i = 0; i < stack_depth; i++) {
762 strlcat(buf, revstack[i], bufsize);
763 if (i < stack_depth - 1)
764 strlcat(buf, " -> ", bufsize);
765 }
766
767 free(revstack);
768 return (buf);
769 }
770 /*
771 * below are the functions that traverse the graphs we have built
772 * finding out the desired ordering, printing each file in turn.
773 * if missing requirements, or cyclic graphs are detected, a
774 * warning will be issued, and we will continue on..
775 */
776
777 /*
778 * given a requirement node (in a filename) we attempt to satisfy it.
779 * we do some sanity checking first, to ensure that we have providers,
780 * aren't already satisfied and aren't already being satisfied (ie,
781 * cyclic). if we pass all this, we loop over the provision list
782 * calling do_file() (enter recursion) for each filenode in this
783 * provision.
784 */
785 static void
satisfy_req(f_reqnode * rnode,filenode * fnode,strnodelist * stack_ptr)786 satisfy_req(f_reqnode *rnode, filenode *fnode, strnodelist *stack_ptr)
787 {
788 Hash_Entry *entry;
789 provnode *head;
790 strnodelist stack_item;
791 char *buf;
792
793 entry = rnode->entry;
794 head = Hash_GetValue(entry);
795
796 if (do_graphviz == true)
797 generate_graphviz_file_links(entry, fnode);
798
799 if (head == NULL) {
800 warnx("requirement `%s' in file `%s' has no providers.",
801 Hash_GetKey(entry), fnode->filename);
802 exit_code = 1;
803 return;
804 }
805
806 /* return if the requirement is already satisfied. */
807 if (head->next == NULL)
808 return;
809
810 /*
811 * if list is marked as in progress,
812 * print that there is a circular dependency on it and abort
813 */
814 if (head->in_progress == SET) {
815 exit_code = 1;
816 buf = generate_loop_for_req(stack_ptr, head,
817 fnode);
818
819 if (buf == NULL) {
820 warnx("Circular dependency on provision `%s' in "
821 "file `%s' (tracing has failed).",
822 Hash_GetKey(entry), fnode->filename);
823 return;
824 }
825
826 warnx("Circular dependency on provision `%s': %s.",
827 Hash_GetKey(entry), buf);
828 free(buf);
829 return;
830 }
831
832 head->in_progress = SET;
833
834 stack_item.next = stack_ptr;
835 stack_item.node = fnode;
836
837 /*
838 * while provision_list is not empty
839 * do_file(first_member_of(provision_list));
840 */
841 while (head->next != NULL)
842 do_file(head->next->fnode, &stack_item);
843 }
844
845 static int
skip_ok(filenode * fnode)846 skip_ok(filenode *fnode)
847 {
848 strnodelist *s;
849 strnodelist *k;
850
851 for (s = skip_list; s; s = s->next)
852 for (k = fnode->keyword_list; k; k = k->next)
853 if (strcmp(k->s, s->s) == 0)
854 return (0);
855
856 return (1);
857 }
858
859 static int
keep_ok(filenode * fnode)860 keep_ok(filenode *fnode)
861 {
862 strnodelist *s;
863 strnodelist *k;
864
865 for (s = keep_list; s; s = s->next)
866 for (k = fnode->keyword_list; k; k = k->next)
867 if (strcmp(k->s, s->s) == 0)
868 return (1);
869
870 /* an empty keep_list means every one */
871 return (!keep_list);
872 }
873
874 /*
875 * given a filenode, we ensure we are not a cyclic graph. if this
876 * is ok, we loop over the filenodes requirements, calling satisfy_req()
877 * for each of them.. once we have done this, remove this filenode
878 * from each provision table, as we are now done.
879 *
880 * NOTE: do_file() is called recursively from several places and cannot
881 * safely free() anything related to items that may be recursed on.
882 * Circular dependencies will cause problems if we do.
883 */
884 static void
do_file(filenode * fnode,strnodelist * stack_ptr)885 do_file(filenode *fnode, strnodelist *stack_ptr)
886 {
887 f_reqnode *r;
888 f_provnode *p, *p_tmp;
889 provnode *pnode, *head;
890 int was_set;
891 char *dep_name;
892
893 DPRINTF((stderr, "do_file on %s.\n", fnode->filename));
894
895 /*
896 * if fnode is marked as in progress,
897 * print that fnode; is circularly depended upon and abort.
898 */
899 if (fnode->in_progress == SET) {
900 warnx("Circular dependency on file `%s'.",
901 fnode->filename);
902 was_set = exit_code = 1;
903 } else
904 was_set = 0;
905
906 /* mark fnode */
907 fnode->in_progress = SET;
908
909 /*
910 * for each requirement of fnode -> r
911 * satisfy_req(r, filename)
912 */
913 r = fnode->req_list;
914 fnode->sequence = 0;
915 while (r != NULL) {
916 satisfy_req(r, fnode, stack_ptr);
917 /* find sequence number where all requirements are satisfied */
918 head = Hash_GetValue(r->entry);
919 if (head && head->sequence > fnode->sequence)
920 fnode->sequence = head->sequence;
921 r = r->next;
922 }
923 fnode->req_list = NULL;
924 fnode->sequence++;
925
926 /* if we've seen issues with this file - put it to the tail */
927 if (fnode->issues_count)
928 fnode->sequence = max_sequence + 1;
929
930 if (max_sequence < fnode->sequence)
931 max_sequence = fnode->sequence;
932
933 /*
934 * for each provision of fnode -> p
935 * remove fnode from provision list for p in hash table
936 */
937 p = fnode->prov_list;
938 while (p != NULL) {
939 /* mark all troublemakers on graphviz */
940 if (do_graphviz == true && fnode->issues_count) {
941 dep_name = Hash_GetKey(p->entry);
942 if (!is_fake_prov(dep_name))
943 printf("\"%s\" [ color=red, penwidth=4 ];\n",
944 dep_name);
945 }
946
947 /* update sequence when provided requirements are satisfied */
948 head = Hash_GetValue(p->entry);
949 if (head->sequence < fnode->sequence)
950 head->sequence = fnode->sequence;
951
952 p_tmp = p;
953 pnode = p->pnode;
954 if (pnode->next != NULL) {
955 pnode->next->last = pnode->last;
956 }
957 if (pnode->last != NULL) {
958 pnode->last->next = pnode->next;
959 }
960 free(pnode);
961 p = p->next;
962 free(p_tmp);
963 }
964 fnode->prov_list = NULL;
965
966 /* do_it(fnode) */
967 DPRINTF((stderr, "next do: "));
968
969 /* if we were already in progress, don't print again */
970 if (do_graphviz != true && was_set == 0 && skip_ok(fnode) &&
971 keep_ok(fnode)) {
972 *fn_seqlist = fnode;
973 fn_seqlist++;
974 }
975
976 if (fnode->next != NULL) {
977 fnode->next->last = fnode->last;
978 }
979 if (fnode->last != NULL) {
980 fnode->last->next = fnode->next;
981 }
982
983 if (fnode->issues_count)
984 warnx("`%s' was seen in circular dependencies for %d times.",
985 fnode->filename, fnode->issues_count);
986
987 DPRINTF((stderr, "nuking %s\n", fnode->filename));
988 }
989
990 static void
generate_graphviz_header(void)991 generate_graphviz_header(void)
992 {
993
994 if (do_graphviz != true)
995 return;
996
997 printf("digraph rcorder {\n"
998 "rankdir=\"BT\";\n"
999 "node [style=rounded, shape=record];\n"
1000 "graph [overlap = false];\n");
1001 }
1002
1003 static void
generate_graphviz_footer(void)1004 generate_graphviz_footer(void)
1005 {
1006
1007 if (do_graphviz == true)
1008 printf("}\n");
1009 }
1010
1011 static void
generate_graphviz_providers(void)1012 generate_graphviz_providers(void)
1013 {
1014 Hash_Entry *entry;
1015 Hash_Search psearch;
1016 provnode *head, *pnode;
1017 char *dep_name;
1018
1019 if (do_graphviz != true)
1020 return;
1021
1022 entry = Hash_EnumFirst(provide_hash, &psearch);
1023 if (entry == NULL)
1024 return;
1025
1026 do {
1027 dep_name = Hash_GetKey(entry);
1028 if (is_fake_prov(dep_name))
1029 continue;
1030 head = Hash_GetValue(entry);
1031 /* no providers for this requirement */
1032 if (head == NULL || head->next == NULL) {
1033 printf("\"%s\" [label=\"{ %s | ENOENT }\", "
1034 "style=\"rounded,filled\", color=red];\n",
1035 dep_name, dep_name);
1036 continue;
1037 }
1038 /* one PROVIDE word for one file that matches */
1039 if (head->next->next == NULL &&
1040 strcmp(dep_name,
1041 basename(head->next->fnode->filename)) == 0) {
1042 continue;
1043 }
1044 printf("\"%s\" [label=\"{ %s | ", dep_name, dep_name);
1045 for (pnode = head->next; pnode; pnode = pnode->next)
1046 printf("%s\\n", basename(pnode->fnode->filename));
1047
1048 printf("}\"];\n");
1049 } while (NULL != (entry = Hash_EnumNext(&psearch)));
1050 }
1051
1052 static int
sequence_cmp(const void * a,const void * b)1053 sequence_cmp(const void *a, const void *b)
1054 {
1055 const filenode *fna = *((const filenode * const *)a);
1056 const filenode *fnb = *((const filenode * const *)b);
1057 int left, right;
1058
1059 /* push phantom files to the end */
1060 if (fna == NULL || fnb == NULL)
1061 return ((fna < fnb) - (fna > fnb));
1062
1063 left = fna->sequence;
1064 right = fnb->sequence;
1065
1066 return ((left > right) - (left < right));
1067 }
1068
1069 static void
generate_ordering(void)1070 generate_ordering(void)
1071 {
1072 filenode **seqlist, **psl;
1073 int last_seq = 0;
1074
1075 /* Prepare order buffer, use an additional one as a list terminator */
1076 seqlist = emalloc(sizeof(filenode *) * (file_count + 1));
1077 bzero(seqlist, sizeof(filenode *) * (file_count + 1));
1078 fn_seqlist = seqlist;
1079
1080 /*
1081 * while there remain undone files{f},
1082 * pick an arbitrary f, and do_file(f)
1083 * Note that the first file in the file list is perfectly
1084 * arbitrary, and easy to find, so we use that.
1085 */
1086
1087 /*
1088 * N.B.: the file nodes "self delete" after they execute, so
1089 * after each iteration of the loop, the head will be pointing
1090 * to something totally different. The loop ends up being
1091 * executed only once for every strongly connected set of
1092 * nodes.
1093 */
1094 while (fn_head->next != NULL) {
1095 DPRINTF((stderr, "generate on %s\n", fn_head->next->filename));
1096 do_file(fn_head->next, NULL);
1097 }
1098
1099 /* Sort filenode list based on sequence */
1100 qsort(seqlist, file_count, sizeof(filenode *), sequence_cmp);
1101
1102 for (psl = seqlist; *psl; psl++) {
1103 printf("%s%s",
1104 (last_seq == 0 ? "" :
1105 (do_parallel != true || last_seq != (*psl)->sequence) ?
1106 "\n" : " "),
1107 (*psl)->filename);
1108 last_seq = (*psl)->sequence;
1109 free((*psl)->filename);
1110 free(*psl);
1111 }
1112 if (last_seq)
1113 printf("\n");
1114
1115 free(seqlist);
1116 }
1117