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