1 /* $NetBSD: rcorder.c,v 1.4 2000/05/10 02:04:27 enami 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 "sprite.h" 48 #include "hash.h" 49 50 #ifdef DEBUG 51 int debug = 0; 52 # define DPRINTF(args) if (debug) { fflush(stdout); fprintf args; } 53 #else 54 # define DPRINTF(args) 55 #endif 56 57 #define REQUIRE_STR "# REQUIRE:" 58 #define REQUIRE_LEN (sizeof(REQUIRE_STR) - 1) 59 #define REQUIRES_STR "# REQUIRES:" 60 #define REQUIRES_LEN (sizeof(REQUIRES_STR) - 1) 61 #define PROVIDE_STR "# PROVIDE:" 62 #define PROVIDE_LEN (sizeof(PROVIDE_STR) - 1) 63 #define PROVIDES_STR "# PROVIDES:" 64 #define PROVIDES_LEN (sizeof(PROVIDES_STR) - 1) 65 #define BEFORE_STR "# BEFORE:" 66 #define BEFORE_LEN (sizeof(BEFORE_STR) - 1) 67 68 int exit_code; 69 int file_count; 70 char **file_list; 71 72 typedef int bool; 73 #define TRUE 1 74 #define FALSE 0 75 typedef bool flag; 76 #define SET TRUE 77 #define RESET FALSE 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 beforelist beforelist; 86 87 struct provnode { 88 flag head; 89 flag 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 filenode { 105 char *filename; 106 flag in_progress; 107 filenode *next, *last; 108 f_reqnode *req_list; 109 f_provnode *prov_list; 110 }; 111 112 struct beforelist { 113 filenode *node; 114 char *s; 115 beforelist *next; 116 } *bl_list = NULL; 117 118 filenode fn_head_s, *fn_head; 119 120 void do_file __P((filenode *fnode)); 121 void satisfy_req __P((f_reqnode *rnode, char *filename)); 122 void crunch_file __P((char *)); 123 void parse_require __P((filenode *, char *)); 124 void parse_provide __P((filenode *, char *)); 125 void parse_before __P((filenode *, char *)); 126 filenode *filenode_new __P((char *)); 127 void add_require __P((filenode *, char *)); 128 void add_provide __P((filenode *, char *)); 129 void add_before __P((filenode *, char *)); 130 void insert_before __P((void)); 131 Hash_Entry *make_fake_provision __P((filenode *)); 132 void crunch_all_files __P((void)); 133 void initialize __P((void)); 134 void generate_ordering __P((void)); 135 int main __P((int, char *[])); 136 137 int 138 main(argc, argv) 139 int argc; 140 char *argv[]; 141 { 142 int ch; 143 144 while ((ch = getopt(argc, argv, "d")) != -1) 145 switch (ch) { 146 case 'd': 147 #ifdef DEBUG 148 debug = 1; 149 #else 150 warnx("debugging not compiled in, -d ignored"); 151 #endif 152 break; 153 default: 154 /* XXX should crunch it? */ 155 break; 156 } 157 argc -= optind; 158 argv += optind; 159 160 file_count = argc; 161 file_list = argv; 162 163 DPRINTF((stderr, "parse_args\n")); 164 initialize(); 165 DPRINTF((stderr, "initialize\n")); 166 crunch_all_files(); 167 DPRINTF((stderr, "crunch_all_files\n")); 168 generate_ordering(); 169 DPRINTF((stderr, "generate_ordering\n")); 170 171 exit(exit_code); 172 } 173 174 /* 175 * initialise various variables. 176 */ 177 void 178 initialize() 179 { 180 181 fn_head = &fn_head_s; 182 183 provide_hash = &provide_hash_s; 184 Hash_InitTable(provide_hash, file_count); 185 } 186 187 /* 188 * below are the functions that deal with creating the lists 189 * from the filename's given and the dependancies and provisions 190 * in each of these files. no ordering or checking is done here. 191 */ 192 193 /* 194 * we have a new filename, create a new filenode structure. 195 * fill in the bits, and put it in the filenode linked list 196 */ 197 filenode * 198 filenode_new(filename) 199 char *filename; 200 { 201 filenode *temp; 202 203 temp = emalloc(sizeof(*temp)); 204 memset(temp, 0, sizeof(*temp)); 205 temp->filename = estrdup(filename); 206 temp->req_list = NULL; 207 temp->prov_list = NULL; 208 temp->in_progress = RESET; 209 /* 210 * link the filenode into the list of filenodes. 211 * note that the double linking means we can delete a 212 * filenode without searching for where it belongs. 213 */ 214 temp->next = fn_head->next; 215 if (temp->next != NULL) 216 temp->next->last = temp; 217 temp->last = fn_head; 218 fn_head->next = temp; 219 return (temp); 220 } 221 222 /* 223 * add a requirement a filenode. 224 */ 225 void 226 add_require(fnode, s) 227 filenode *fnode; 228 char *s; 229 { 230 Hash_Entry *entry; 231 f_reqnode *rnode; 232 int new; 233 234 entry = Hash_CreateEntry(provide_hash, s, &new); 235 if (new) 236 Hash_SetValue(entry, NULL); 237 rnode = emalloc(sizeof(*rnode)); 238 rnode->entry = entry; 239 rnode->next = fnode->req_list; 240 fnode->req_list = rnode; 241 } 242 243 /* 244 * add a provision to a filenode. if this provision doesn't 245 * have a head node, create one here. 246 */ 247 void 248 add_provide(fnode, s) 249 filenode *fnode; 250 char *s; 251 { 252 Hash_Entry *entry; 253 f_provnode *f_pnode; 254 provnode *pnode, *head; 255 int new; 256 257 entry = Hash_CreateEntry(provide_hash, s, &new); 258 head = Hash_GetValue(entry); 259 260 /* create a head node if necessary. */ 261 if (head == NULL) { 262 head = emalloc(sizeof(*head)); 263 head->head = SET; 264 head->in_progress = RESET; 265 head->fnode = NULL; 266 head->last = head->next = NULL; 267 Hash_SetValue(entry, head); 268 } 269 #if 0 270 /* 271 * Don't warn about this. We want to be able to support 272 * scripts that do two complex things: 273 * 274 * - Two independent scripts which both provide the 275 * same thing. Both scripts must be executed in 276 * any order to meet the barrier. An example: 277 * 278 * Script 1: 279 * 280 * PROVIDE: mail 281 * REQUIRE: LOGIN 282 * 283 * Script 2: 284 * 285 * PROVIDE: mail 286 * REQUIRE: LOGIN 287 * 288 * - Two interdependent scripts which both provide the 289 * same thing. Both scripts must be executed in 290 * graph order to meet the barrier. An example: 291 * 292 * Script 1: 293 * 294 * PROVIDE: nameservice dnscache 295 * REQUIRE: SERVERS 296 * 297 * Script 2: 298 * 299 * PROVIDE: nameservice nscd 300 * REQUIRE: dnscache 301 */ 302 else if (new == 0) { 303 warnx("file `%s' provides `%s'.", fnode->filename, s); 304 warnx("\tpreviously seen in `%s'.", 305 head->next->fnode->filename); 306 } 307 #endif 308 309 pnode = emalloc(sizeof(*pnode)); 310 pnode->head = RESET; 311 pnode->in_progress = RESET; 312 pnode->fnode = fnode; 313 pnode->next = head->next; 314 pnode->last = head; 315 head->next = pnode; 316 if (pnode->next != NULL) 317 pnode->next->last = pnode; 318 319 f_pnode = emalloc(sizeof(*f_pnode)); 320 f_pnode->pnode = pnode; 321 f_pnode->next = fnode->prov_list; 322 fnode->prov_list = f_pnode; 323 } 324 325 /* 326 * put the BEFORE: lines to a list and handle them later. 327 */ 328 void 329 add_before(fnode, s) 330 filenode *fnode; 331 char *s; 332 { 333 beforelist *bf_ent; 334 335 bf_ent = emalloc(sizeof *bf_ent); 336 bf_ent->node = fnode; 337 bf_ent->s = s; 338 bf_ent->next = bl_list; 339 bl_list = bf_ent; 340 } 341 342 /* 343 * loop over the rest of a REQUIRE line, giving each word to 344 * add_require() to do the real work. 345 */ 346 void 347 parse_require(node, buffer) 348 filenode *node; 349 char *buffer; 350 { 351 char *s; 352 353 while ((s = strsep(&buffer, " \t\n")) != NULL) 354 if (*s != '\0') 355 add_require(node, s); 356 } 357 358 /* 359 * loop over the rest of a PROVIDE line, giving each word to 360 * add_provide() to do the real work. 361 */ 362 void 363 parse_provide(node, buffer) 364 filenode *node; 365 char *buffer; 366 { 367 char *s; 368 369 while ((s = strsep(&buffer, " \t\n")) != NULL) 370 if (*s != '\0') 371 add_provide(node, s); 372 } 373 374 /* 375 * loop over the rest of a BEFORE line, giving each word to 376 * add_before() to do the real work. 377 */ 378 void 379 parse_before(node, buffer) 380 filenode *node; 381 char *buffer; 382 { 383 char *s; 384 385 while ((s = strsep(&buffer, " \t\n")) != NULL) 386 if (*s != '\0') 387 add_before(node, s); 388 } 389 390 /* 391 * given a file name, create a filenode for it, read in lines looking 392 * for provision and requirement lines, building the graphs as needed. 393 */ 394 void 395 crunch_file(filename) 396 char *filename; 397 { 398 FILE *fp; 399 char *buf; 400 int require_flag, provide_flag, before_flag, directive_flag; 401 filenode *node; 402 char delims[3] = { '\\', '\\', '\0' }; 403 struct stat st; 404 405 directive_flag = 0; 406 407 if ((fp = fopen(filename, "r")) == NULL) { 408 warn("could not open %s", filename); 409 return; 410 } 411 412 if (fstat(fileno(fp), &st) == -1) { 413 warn("could not stat %s", filename); 414 fclose(fp); 415 return; 416 } 417 418 if (!S_ISREG(st.st_mode)) { 419 warnx("%s is not a file", filename); 420 fclose(fp); 421 return; 422 } 423 424 node = filenode_new(filename); 425 426 /* 427 * we don't care about length, line number, don't want # for comments, 428 * and have no flags. 429 */ 430 while ((buf = fparseln(fp, NULL, NULL, delims, 0))) { 431 require_flag = provide_flag = before_flag = 0; 432 if (strncmp(REQUIRE_STR, buf, REQUIRE_LEN) == 0) 433 require_flag = REQUIRE_LEN; 434 else if (strncmp(REQUIRES_STR, buf, REQUIRES_LEN) == 0) 435 require_flag = REQUIRES_LEN; 436 else if (strncmp(PROVIDE_STR, buf, PROVIDE_LEN) == 0) 437 provide_flag = PROVIDE_LEN; 438 else if (strncmp(PROVIDES_STR, buf, PROVIDES_LEN) == 0) 439 provide_flag = PROVIDES_LEN; 440 else if (strncmp(BEFORE_STR, buf, BEFORE_LEN) == 0) 441 before_flag = BEFORE_LEN; 442 443 if (require_flag) 444 parse_require(node, buf + require_flag); 445 446 if (provide_flag) 447 parse_provide(node, buf + provide_flag); 448 449 if (before_flag) 450 parse_before(node, buf + before_flag); 451 } 452 fclose(fp); 453 } 454 455 Hash_Entry * 456 make_fake_provision(node) 457 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() 504 { 505 Hash_Entry *entry, *fake_prov_entry; 506 provnode *pnode; 507 f_reqnode *rnode; 508 beforelist *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() 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(rnode, filename) 567 f_reqnode *rnode; 568 char *filename; 569 { 570 Hash_Entry *entry; 571 provnode *head; 572 573 entry = rnode->entry; 574 head = Hash_GetValue(entry); 575 576 if (head == NULL) { 577 warnx("requirement `%s' in file `%s' has no providers.", 578 Hash_GetKey(entry), filename); 579 exit_code = 1; 580 return; 581 } 582 583 /* return if the requirement is already satisfied. */ 584 if (head->next == NULL) 585 return; 586 587 /* 588 * if list is marked as in progress, 589 * print that there is a circular dependency on it and abort 590 */ 591 if (head->in_progress == SET) { 592 warnx("Circular dependency on provision `%s' in file `%s'.", 593 Hash_GetKey(entry), filename); 594 exit_code = 1; 595 return; 596 } 597 598 head->in_progress = SET; 599 600 /* 601 * while provision_list is not empty 602 * do_file(first_member_of(provision_list)); 603 */ 604 while (head->next != NULL) 605 do_file(head->next->fnode); 606 } 607 608 /* 609 * given a filenode, we ensure we are not a cyclic graph. if this 610 * is ok, we loop over the filenodes requirements, calling satisfy_req() 611 * for each of them.. once we have done this, remove this filenode 612 * from each provision table, as we are now done. 613 */ 614 void 615 do_file(fnode) 616 filenode *fnode; 617 { 618 f_reqnode *r, *r_tmp; 619 f_provnode *p, *p_tmp; 620 provnode *pnode; 621 int was_set; 622 623 DPRINTF((stderr, "do_file on %s.\n", fnode->filename)); 624 625 /* 626 * if fnode is marked as in progress, 627 * print that fnode; is circularly depended upon and abort. 628 */ 629 if (fnode->in_progress == SET) { 630 warnx("Circular dependency on file `%s'.", 631 fnode->filename); 632 was_set = exit_code = 1; 633 } else 634 was_set = 0; 635 636 /* mark fnode */ 637 fnode->in_progress = SET; 638 639 /* 640 * for each requirement of fnode -> r 641 * satisfy_req(r, filename) 642 */ 643 r = fnode->req_list; 644 while (r != NULL) { 645 r_tmp = r; 646 satisfy_req(r, fnode->filename); 647 r = r->next; 648 free(r_tmp); 649 } 650 fnode->req_list = NULL; 651 652 /* 653 * for each provision of fnode -> p 654 * remove fnode from provision list for p in hash table 655 */ 656 p = fnode->prov_list; 657 while (p != NULL) { 658 p_tmp = p; 659 pnode = p->pnode; 660 if (pnode->next != NULL) { 661 pnode->next->last = pnode->last; 662 } 663 if (pnode->last != NULL) { 664 pnode->last->next = pnode->next; 665 } 666 free(pnode); 667 p = p->next; 668 free(p_tmp); 669 } 670 fnode->prov_list = NULL; 671 672 /* do_it(fnode) */ 673 DPRINTF((stderr, "next do: ")); 674 675 /* if we were already in progress, don't print again */ 676 if (was_set == 0) 677 printf("%s\n", fnode->filename); 678 679 if (fnode->next != NULL) { 680 fnode->next->last = fnode->last; 681 } 682 if (fnode->last != NULL) { 683 fnode->last->next = fnode->next; 684 } 685 686 DPRINTF((stderr, "nuking %s\n", fnode->filename)); 687 free(fnode->filename); 688 free(fnode); 689 } 690 691 void 692 generate_ordering() 693 { 694 695 /* 696 * while there remain undone files{f}, 697 * pick an arbitrary f, and do_file(f) 698 * Note that the first file in the file list is perfectly 699 * arbitrary, and easy to find, so we use that. 700 */ 701 702 /* 703 * N.B.: the file nodes "self delete" after they execute, so 704 * after each iteration of the loop, the head will be pointing 705 * to something totally different. The loop ends up being 706 * executed only once for every strongly connected set of 707 * nodes. 708 */ 709 while (fn_head->next != NULL) { 710 DPRINTF((stderr, "generate on %s\n", fn_head->next->filename)); 711 do_file(fn_head->next); 712 } 713 } 714