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