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 59static 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 82static int exit_code; 83static int file_count; 84static char **file_list; 85 86#define TRUE 1 87#define FALSE 0 88typedef bool flag; 89#define SET TRUE 90#define RESET FALSE 91 92static flag do_graphviz = false; 93static flag do_parallel = false; 94 95static Hash_Table provide_hash_s, *provide_hash; 96 97typedef struct provnode provnode; 98typedef struct filenode filenode; 99typedef struct f_provnode f_provnode; 100typedef struct f_reqnode f_reqnode; 101typedef struct strnodelist strnodelist; 102 103struct provnode { 104 flag head; 105 flag in_progress; 106 int sequence; 107 filenode *fnode; 108 provnode *next, *last; 109}; 110 111struct f_provnode { 112 provnode *pnode; 113 Hash_Entry *entry; 114 f_provnode *next; 115}; 116 117struct f_reqnode { 118 Hash_Entry *entry; 119 f_reqnode *next; 120}; 121 122struct strnodelist { 123 filenode *node; 124 strnodelist *next; 125 char s[1]; 126}; 127 128struct 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 139static filenode fn_head_s, *fn_head, **fn_seqlist; 140static int max_sequence = 0; 141 142static strnodelist *bl_list; 143static strnodelist *keep_list; 144static strnodelist *skip_list; 145 146static void do_file(filenode *fnode, strnodelist *); 147static void strnode_add(strnodelist **, char *, filenode *); 148static int skip_ok(filenode *fnode); 149static int keep_ok(filenode *fnode); 150static char *generate_loop_for_req(strnodelist *, provnode *, filenode *); 151static void satisfy_req(f_reqnode *rnode, filenode *fnode, strnodelist *); 152static void crunch_file(char *); 153static void parse_require(filenode *, char *); 154static void parse_provide(filenode *, char *); 155static void parse_before(filenode *, char *); 156static void parse_keywords(filenode *, char *); 157static filenode *filenode_new(char *); 158static void add_require(filenode *, char *); 159static void add_provide(filenode *, char *); 160static void add_before(filenode *, char *); 161static void add_keyword(filenode *, char *); 162static void insert_before(void); 163static Hash_Entry *make_fake_provision(filenode *); 164static void crunch_all_files(void); 165static void initialize(void); 166static void generate_graphviz_header(void); 167static void generate_graphviz_footer(void); 168static void generate_graphviz_file_links(Hash_Entry *, filenode *); 169static void generate_graphviz_providers(void); 170static inline int is_fake_prov(const char *); 171static int sequence_cmp(const void *, const void *); 172static void generate_ordering(void); 173 174int 175main(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 */ 227static void 228initialize(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 */ 238static void 239strnode_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 */ 260static filenode * 261filenode_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 */ 288static void 289add_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 */ 308static void 309add_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 */ 389static void 390add_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 */ 404static void 405add_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 */ 415static void 416parse_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 */ 429static void 430parse_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 */ 443static void 444parse_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 */ 457static void 458parse_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 */ 471static void 472crunch_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 543static Hash_Entry * 544make_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 */ 590static void 591insert_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 */ 633static void 634crunch_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 643static inline int 644is_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 */ 651static void 652generate_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 */ 706static char * 707generate_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 */ 785static void 786satisfy_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 845static int 846skip_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 859static int 860keep_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 */ 884static void 885do_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 990static void 991generate_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 1003static void 1004generate_graphviz_footer(void) 1005{ 1006 1007 if (do_graphviz == true) 1008 printf("}\n"); 1009} 1010 1011static void 1012generate_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 1052static int 1053sequence_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 1069static void 1070generate_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