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