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