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