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 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 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 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 * 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 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 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 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 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 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 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 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 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 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 * 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 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 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 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 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 * 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 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 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 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 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 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 1004 generate_graphviz_footer(void) 1005 { 1006 1007 if (do_graphviz == true) 1008 printf("}\n"); 1009 } 1010 1011 static 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 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 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