1 /* 2 * Copyright (c) 1988, 1989, 1990, 1993 3 * The Regents of the University of California. All rights reserved. 4 * Copyright (c) 1989 by Berkeley Softworks 5 * All rights reserved. 6 * 7 * This code is derived from software contributed to Berkeley by 8 * Adam de Boor. 9 * 10 * %sccs.include.redist.c% 11 */ 12 13 #ifndef lint 14 static char sccsid[] = "@(#)make.c 8.1 (Berkeley) 06/06/93"; 15 #endif /* not lint */ 16 17 /*- 18 * make.c -- 19 * The functions which perform the examination of targets and 20 * their suitability for creation 21 * 22 * Interface: 23 * Make_Run Initialize things for the module and recreate 24 * whatever needs recreating. Returns TRUE if 25 * work was (or would have been) done and FALSE 26 * otherwise. 27 * 28 * Make_Update Update all parents of a given child. Performs 29 * various bookkeeping chores like the updating 30 * of the cmtime field of the parent, filling 31 * of the IMPSRC context variable, etc. It will 32 * place the parent on the toBeMade queue if it 33 * should be. 34 * 35 * Make_TimeStamp Function to set the parent's cmtime field 36 * based on a child's modification time. 37 * 38 * Make_DoAllVar Set up the various local variables for a 39 * target, including the .ALLSRC variable, making 40 * sure that any variable that needs to exist 41 * at the very least has the empty value. 42 * 43 * Make_OODate Determine if a target is out-of-date. 44 * 45 * Make_HandleUse See if a child is a .USE node for a parent 46 * and perform the .USE actions if so. 47 */ 48 49 #include "make.h" 50 #include "hash.h" 51 #include "dir.h" 52 #include "job.h" 53 54 static Lst toBeMade; /* The current fringe of the graph. These 55 * are nodes which await examination by 56 * MakeOODate. It is added to by 57 * Make_Update and subtracted from by 58 * MakeStartJobs */ 59 static int numNodes; /* Number of nodes to be processed. If this 60 * is non-zero when Job_Empty() returns 61 * TRUE, there's a cycle in the graph */ 62 63 static int MakeAddChild __P((GNode *, Lst)); 64 static int MakeAddAllSrc __P((GNode *, GNode *)); 65 static Boolean MakeStartJobs __P((void)); 66 static int MakePrintStatus __P((GNode *, Boolean)); 67 /*- 68 *----------------------------------------------------------------------- 69 * Make_TimeStamp -- 70 * Set the cmtime field of a parent node based on the mtime stamp in its 71 * child. Called from MakeOODate via Lst_ForEach. 72 * 73 * Results: 74 * Always returns 0. 75 * 76 * Side Effects: 77 * The cmtime of the parent node will be changed if the mtime 78 * field of the child is greater than it. 79 *----------------------------------------------------------------------- 80 */ 81 int 82 Make_TimeStamp (pgn, cgn) 83 register GNode *pgn; /* the current parent */ 84 register GNode *cgn; /* the child we've just examined */ 85 { 86 if (cgn->mtime > pgn->cmtime) { 87 pgn->cmtime = cgn->mtime; 88 } 89 return (0); 90 } 91 92 /*- 93 *----------------------------------------------------------------------- 94 * Make_OODate -- 95 * See if a given node is out of date with respect to its sources. 96 * Used by Make_Run when deciding which nodes to place on the 97 * toBeMade queue initially and by Make_Update to screen out USE and 98 * EXEC nodes. In the latter case, however, any other sort of node 99 * must be considered out-of-date since at least one of its children 100 * will have been recreated. 101 * 102 * Results: 103 * TRUE if the node is out of date. FALSE otherwise. 104 * 105 * Side Effects: 106 * The mtime field of the node and the cmtime field of its parents 107 * will/may be changed. 108 *----------------------------------------------------------------------- 109 */ 110 Boolean 111 Make_OODate (gn) 112 register GNode *gn; /* the node to check */ 113 { 114 Boolean oodate; 115 116 /* 117 * Certain types of targets needn't even be sought as their datedness 118 * doesn't depend on their modification time... 119 */ 120 if ((gn->type & (OP_JOIN|OP_USE|OP_EXEC)) == 0) { 121 (void) Dir_MTime (gn); 122 if (DEBUG(MAKE)) { 123 if (gn->mtime != 0) { 124 printf ("modified %s...", Targ_FmtTime(gn->mtime)); 125 } else { 126 printf ("non-existent..."); 127 } 128 } 129 } 130 131 /* 132 * A target is remade in one of the following circumstances: 133 * its modification time is smaller than that of its youngest child 134 * and it would actually be run (has commands or type OP_NOP) 135 * it's the object of a force operator 136 * it has no children, was on the lhs of an operator and doesn't exist 137 * already. 138 * 139 * Libraries are only considered out-of-date if the archive module says 140 * they are. 141 * 142 * These weird rules are brought to you by Backward-Compatability and 143 * the strange people who wrote 'Make'. 144 */ 145 if (gn->type & OP_USE) { 146 /* 147 * If the node is a USE node it is *never* out of date 148 * no matter *what*. 149 */ 150 if (DEBUG(MAKE)) { 151 printf(".USE node..."); 152 } 153 oodate = FALSE; 154 } else if (gn->type & OP_LIB) { 155 if (DEBUG(MAKE)) { 156 printf("library..."); 157 } 158 oodate = Arch_LibOODate (gn); 159 } else if (gn->type & OP_JOIN) { 160 /* 161 * A target with the .JOIN attribute is only considered 162 * out-of-date if any of its children was out-of-date. 163 */ 164 if (DEBUG(MAKE)) { 165 printf(".JOIN node..."); 166 } 167 oodate = gn->childMade; 168 } else if (gn->type & (OP_FORCE|OP_EXEC)) { 169 /* 170 * A node which is the object of the force (!) operator or which has 171 * the .EXEC attribute is always considered out-of-date. 172 */ 173 if (DEBUG(MAKE)) { 174 if (gn->type & OP_FORCE) { 175 printf("! operator..."); 176 } else { 177 printf(".EXEC node..."); 178 } 179 } 180 oodate = TRUE; 181 } else if ((gn->mtime < gn->cmtime) || 182 ((gn->cmtime == 0) && 183 ((gn->mtime==0) || (gn->type & OP_DOUBLEDEP)))) 184 { 185 /* 186 * A node whose modification time is less than that of its 187 * youngest child or that has no children (cmtime == 0) and 188 * either doesn't exist (mtime == 0) or was the object of a 189 * :: operator is out-of-date. Why? Because that's the way Make does 190 * it. 191 */ 192 if (DEBUG(MAKE)) { 193 if (gn->mtime < gn->cmtime) { 194 printf("modified before source..."); 195 } else if (gn->mtime == 0) { 196 printf("non-existent and no sources..."); 197 } else { 198 printf(":: operator and no sources..."); 199 } 200 } 201 oodate = TRUE; 202 } else { 203 #if 0 204 /* WHY? */ 205 if (DEBUG(MAKE)) { 206 printf("source %smade...", gn->childMade ? "" : "not "); 207 } 208 oodate = gn->childMade; 209 #else 210 oodate = FALSE; 211 #endif /* 0 */ 212 } 213 214 /* 215 * If the target isn't out-of-date, the parents need to know its 216 * modification time. Note that targets that appear to be out-of-date 217 * but aren't, because they have no commands and aren't of type OP_NOP, 218 * have their mtime stay below their children's mtime to keep parents from 219 * thinking they're out-of-date. 220 */ 221 if (!oodate) { 222 Lst_ForEach (gn->parents, Make_TimeStamp, (ClientData)gn); 223 } 224 225 return (oodate); 226 } 227 228 /*- 229 *----------------------------------------------------------------------- 230 * MakeAddChild -- 231 * Function used by Make_Run to add a child to the list l. 232 * It will only add the child if its make field is FALSE. 233 * 234 * Results: 235 * Always returns 0 236 * 237 * Side Effects: 238 * The given list is extended 239 *----------------------------------------------------------------------- 240 */ 241 static int 242 MakeAddChild (gn, l) 243 GNode *gn; /* the node to add */ 244 Lst l; /* the list to which to add it */ 245 { 246 if (!gn->make && !(gn->type & OP_USE)) { 247 (void)Lst_EnQueue (l, (ClientData)gn); 248 } 249 return (0); 250 } 251 252 /*- 253 *----------------------------------------------------------------------- 254 * Make_HandleUse -- 255 * Function called by Make_Run and SuffApplyTransform on the downward 256 * pass to handle .USE and transformation nodes. A callback function 257 * for Lst_ForEach, it implements the .USE and transformation 258 * functionality by copying the node's commands, type flags 259 * and children to the parent node. Should be called before the 260 * children are enqueued to be looked at by MakeAddChild. 261 * 262 * A .USE node is much like an explicit transformation rule, except 263 * its commands are always added to the target node, even if the 264 * target already has commands. 265 * 266 * Results: 267 * returns 0. 268 * 269 * Side Effects: 270 * Children and commands may be added to the parent and the parent's 271 * type may be changed. 272 * 273 *----------------------------------------------------------------------- 274 */ 275 int 276 Make_HandleUse (cgn, pgn) 277 register GNode *cgn; /* The .USE node */ 278 register GNode *pgn; /* The target of the .USE node */ 279 { 280 register GNode *gn; /* A child of the .USE node */ 281 register LstNode ln; /* An element in the children list */ 282 283 if (cgn->type & (OP_USE|OP_TRANSFORM)) { 284 if ((cgn->type & OP_USE) || Lst_IsEmpty(pgn->commands)) { 285 /* 286 * .USE or transformation and target has no commands -- append 287 * the child's commands to the parent. 288 */ 289 (void) Lst_Concat (pgn->commands, cgn->commands, LST_CONCNEW); 290 } 291 292 if (Lst_Open (cgn->children) == SUCCESS) { 293 while ((ln = Lst_Next (cgn->children)) != NILLNODE) { 294 gn = (GNode *)Lst_Datum (ln); 295 296 if (Lst_Member (pgn->children, gn) == NILLNODE) { 297 (void) Lst_AtEnd (pgn->children, gn); 298 (void) Lst_AtEnd (gn->parents, pgn); 299 pgn->unmade += 1; 300 } 301 } 302 Lst_Close (cgn->children); 303 } 304 305 pgn->type |= cgn->type & ~(OP_OPMASK|OP_USE|OP_TRANSFORM); 306 307 /* 308 * This child node is now "made", so we decrement the count of 309 * unmade children in the parent... We also remove the child 310 * from the parent's list to accurately reflect the number of decent 311 * children the parent has. This is used by Make_Run to decide 312 * whether to queue the parent or examine its children... 313 */ 314 if (cgn->type & OP_USE) { 315 pgn->unmade -= 1; 316 } 317 } 318 return (0); 319 } 320 321 /*- 322 *----------------------------------------------------------------------- 323 * Make_Update -- 324 * Perform update on the parents of a node. Used by JobFinish once 325 * a node has been dealt with and by MakeStartJobs if it finds an 326 * up-to-date node. 327 * 328 * Results: 329 * Always returns 0 330 * 331 * Side Effects: 332 * The unmade field of pgn is decremented and pgn may be placed on 333 * the toBeMade queue if this field becomes 0. 334 * 335 * If the child was made, the parent's childMade field will be set true 336 * and its cmtime set to now. 337 * 338 * If the child wasn't made, the cmtime field of the parent will be 339 * altered if the child's mtime is big enough. 340 * 341 * Finally, if the child is the implied source for the parent, the 342 * parent's IMPSRC variable is set appropriately. 343 * 344 *----------------------------------------------------------------------- 345 */ 346 void 347 Make_Update (cgn) 348 register GNode *cgn; /* the child node */ 349 { 350 register GNode *pgn; /* the parent node */ 351 register char *cname; /* the child's name */ 352 register LstNode ln; /* Element in parents and iParents lists */ 353 354 cname = Var_Value (TARGET, cgn); 355 356 /* 357 * If the child was actually made, see what its modification time is 358 * now -- some rules won't actually update the file. If the file still 359 * doesn't exist, make its mtime now. 360 */ 361 if (cgn->made != UPTODATE) { 362 #ifndef RECHECK 363 /* 364 * We can't re-stat the thing, but we can at least take care of rules 365 * where a target depends on a source that actually creates the 366 * target, but only if it has changed, e.g. 367 * 368 * parse.h : parse.o 369 * 370 * parse.o : parse.y 371 * yacc -d parse.y 372 * cc -c y.tab.c 373 * mv y.tab.o parse.o 374 * cmp -s y.tab.h parse.h || mv y.tab.h parse.h 375 * 376 * In this case, if the definitions produced by yacc haven't changed 377 * from before, parse.h won't have been updated and cgn->mtime will 378 * reflect the current modification time for parse.h. This is 379 * something of a kludge, I admit, but it's a useful one.. 380 * XXX: People like to use a rule like 381 * 382 * FRC: 383 * 384 * To force things that depend on FRC to be made, so we have to 385 * check for gn->children being empty as well... 386 */ 387 if (!Lst_IsEmpty(cgn->commands) || Lst_IsEmpty(cgn->children)) { 388 cgn->mtime = now; 389 } 390 #else 391 /* 392 * This is what Make does and it's actually a good thing, as it 393 * allows rules like 394 * 395 * cmp -s y.tab.h parse.h || cp y.tab.h parse.h 396 * 397 * to function as intended. Unfortunately, thanks to the stateless 398 * nature of NFS (by which I mean the loose coupling of two clients 399 * using the same file from a common server), there are times 400 * when the modification time of a file created on a remote 401 * machine will not be modified before the local stat() implied by 402 * the Dir_MTime occurs, thus leading us to believe that the file 403 * is unchanged, wreaking havoc with files that depend on this one. 404 * 405 * I have decided it is better to make too much than to make too 406 * little, so this stuff is commented out unless you're sure it's ok. 407 * -- ardeb 1/12/88 408 */ 409 /* 410 * Christos, 4/9/92: If we are saving commands pretend that 411 * the target is made now. Otherwise archives with ... rules 412 * don't work! 413 */ 414 if (noExecute || (cgn->type & OP_SAVE_CMDS) || Dir_MTime(cgn) == 0) { 415 cgn->mtime = now; 416 } 417 if (DEBUG(MAKE)) { 418 printf("update time: %s\n", Targ_FmtTime(cgn->mtime)); 419 } 420 #endif 421 } 422 423 if (Lst_Open (cgn->parents) == SUCCESS) { 424 while ((ln = Lst_Next (cgn->parents)) != NILLNODE) { 425 pgn = (GNode *)Lst_Datum (ln); 426 if (pgn->make) { 427 pgn->unmade -= 1; 428 429 if ( ! (cgn->type & (OP_EXEC|OP_USE))) { 430 if (cgn->made == MADE) { 431 pgn->childMade = TRUE; 432 if (pgn->cmtime < cgn->mtime) { 433 pgn->cmtime = cgn->mtime; 434 } 435 } else { 436 (void)Make_TimeStamp (pgn, cgn); 437 } 438 } 439 if (pgn->unmade == 0) { 440 /* 441 * Queue the node up -- any unmade predecessors will 442 * be dealt with in MakeStartJobs. 443 */ 444 (void)Lst_EnQueue (toBeMade, (ClientData)pgn); 445 } else if (pgn->unmade < 0) { 446 Error ("Graph cycles through %s", pgn->name); 447 } 448 } 449 } 450 Lst_Close (cgn->parents); 451 } 452 /* 453 * Deal with successor nodes. If any is marked for making and has an unmade 454 * count of 0, has not been made and isn't in the examination queue, 455 * it means we need to place it in the queue as it restrained itself 456 * before. 457 */ 458 for (ln = Lst_First(cgn->successors); ln != NILLNODE; ln = Lst_Succ(ln)) { 459 GNode *succ = (GNode *)Lst_Datum(ln); 460 461 if (succ->make && succ->unmade == 0 && succ->made == UNMADE && 462 Lst_Member(toBeMade, (ClientData)succ) == NILLNODE) 463 { 464 (void)Lst_EnQueue(toBeMade, (ClientData)succ); 465 } 466 } 467 468 /* 469 * Set the .PREFIX and .IMPSRC variables for all the implied parents 470 * of this node. 471 */ 472 if (Lst_Open (cgn->iParents) == SUCCESS) { 473 char *cpref = Var_Value(PREFIX, cgn); 474 475 while ((ln = Lst_Next (cgn->iParents)) != NILLNODE) { 476 pgn = (GNode *)Lst_Datum (ln); 477 if (pgn->make) { 478 Var_Set (IMPSRC, cname, pgn); 479 Var_Set (PREFIX, cpref, pgn); 480 } 481 } 482 Lst_Close (cgn->iParents); 483 } 484 } 485 486 /*- 487 *----------------------------------------------------------------------- 488 * MakeAddAllSrc -- 489 * Add a child's name to the ALLSRC and OODATE variables of the given 490 * node. Called from Make_DoAllVar via Lst_ForEach. A child is added only 491 * if it has not been given the .EXEC, .USE or .INVISIBLE attributes. 492 * .EXEC and .USE children are very rarely going to be files, so... 493 * A child is added to the OODATE variable if its modification time is 494 * later than that of its parent, as defined by Make, except if the 495 * parent is a .JOIN node. In that case, it is only added to the OODATE 496 * variable if it was actually made (since .JOIN nodes don't have 497 * modification times, the comparison is rather unfair...).. 498 * 499 * Results: 500 * Always returns 0 501 * 502 * Side Effects: 503 * The ALLSRC variable for the given node is extended. 504 *----------------------------------------------------------------------- 505 */ 506 static int 507 MakeAddAllSrc (cgn, pgn) 508 GNode *cgn; /* The child to add */ 509 GNode *pgn; /* The parent to whose ALLSRC variable it should be */ 510 /* added */ 511 { 512 if ((cgn->type & (OP_EXEC|OP_USE|OP_INVISIBLE)) == 0) { 513 register char *child; 514 515 child = Var_Value(TARGET, cgn); 516 Var_Append (ALLSRC, child, pgn); 517 if (pgn->type & OP_JOIN) { 518 if (cgn->made == MADE) { 519 Var_Append(OODATE, child, pgn); 520 } 521 } else if ((pgn->mtime < cgn->mtime) || 522 (cgn->mtime >= now && cgn->made == MADE)) 523 { 524 /* 525 * It goes in the OODATE variable if the parent is younger than the 526 * child or if the child has been modified more recently than 527 * the start of the make. This is to keep pmake from getting 528 * confused if something else updates the parent after the 529 * make starts (shouldn't happen, I know, but sometimes it 530 * does). In such a case, if we've updated the kid, the parent 531 * is likely to have a modification time later than that of 532 * the kid and anything that relies on the OODATE variable will 533 * be hosed. 534 * 535 * XXX: This will cause all made children to go in the OODATE 536 * variable, even if they're not touched, if RECHECK isn't defined, 537 * since cgn->mtime is set to now in Make_Update. According to 538 * some people, this is good... 539 */ 540 Var_Append(OODATE, child, pgn); 541 } 542 } 543 return (0); 544 } 545 546 /*- 547 *----------------------------------------------------------------------- 548 * Make_DoAllVar -- 549 * Set up the ALLSRC and OODATE variables. Sad to say, it must be 550 * done separately, rather than while traversing the graph. This is 551 * because Make defined OODATE to contain all sources whose modification 552 * times were later than that of the target, *not* those sources that 553 * were out-of-date. Since in both compatibility and native modes, 554 * the modification time of the parent isn't found until the child 555 * has been dealt with, we have to wait until now to fill in the 556 * variable. As for ALLSRC, the ordering is important and not 557 * guaranteed when in native mode, so it must be set here, too. 558 * 559 * Results: 560 * None 561 * 562 * Side Effects: 563 * The ALLSRC and OODATE variables of the given node is filled in. 564 * If the node is a .JOIN node, its TARGET variable will be set to 565 * match its ALLSRC variable. 566 *----------------------------------------------------------------------- 567 */ 568 void 569 Make_DoAllVar (gn) 570 GNode *gn; 571 { 572 Lst_ForEach (gn->children, MakeAddAllSrc, gn); 573 574 if (!Var_Exists (OODATE, gn)) { 575 Var_Set (OODATE, "", gn); 576 } 577 if (!Var_Exists (ALLSRC, gn)) { 578 Var_Set (ALLSRC, "", gn); 579 } 580 581 if (gn->type & OP_JOIN) { 582 Var_Set (TARGET, Var_Value (ALLSRC, gn), gn); 583 } 584 } 585 586 /*- 587 *----------------------------------------------------------------------- 588 * MakeStartJobs -- 589 * Start as many jobs as possible. 590 * 591 * Results: 592 * If the query flag was given to pmake, no job will be started, 593 * but as soon as an out-of-date target is found, this function 594 * returns TRUE. At all other times, this function returns FALSE. 595 * 596 * Side Effects: 597 * Nodes are removed from the toBeMade queue and job table slots 598 * are filled. 599 * 600 *----------------------------------------------------------------------- 601 */ 602 static Boolean 603 MakeStartJobs () 604 { 605 register GNode *gn; 606 607 while (!Job_Full() && !Lst_IsEmpty (toBeMade)) { 608 gn = (GNode *) Lst_DeQueue (toBeMade); 609 if (DEBUG(MAKE)) { 610 printf ("Examining %s...", gn->name); 611 } 612 /* 613 * Make sure any and all predecessors that are going to be made, 614 * have been. 615 */ 616 if (!Lst_IsEmpty(gn->preds)) { 617 LstNode ln; 618 619 for (ln = Lst_First(gn->preds); ln != NILLNODE; ln = Lst_Succ(ln)){ 620 GNode *pgn = (GNode *)Lst_Datum(ln); 621 622 if (pgn->make && pgn->made == UNMADE) { 623 if (DEBUG(MAKE)) { 624 printf("predecessor %s not made yet.\n", pgn->name); 625 } 626 break; 627 } 628 } 629 /* 630 * If ln isn't nil, there's a predecessor as yet unmade, so we 631 * just drop this node on the floor. When the node in question 632 * has been made, it will notice this node as being ready to 633 * make but as yet unmade and will place the node on the queue. 634 */ 635 if (ln != NILLNODE) { 636 continue; 637 } 638 } 639 640 numNodes--; 641 if (Make_OODate (gn)) { 642 if (DEBUG(MAKE)) { 643 printf ("out-of-date\n"); 644 } 645 if (queryFlag) { 646 return (TRUE); 647 } 648 Make_DoAllVar (gn); 649 Job_Make (gn); 650 } else { 651 if (DEBUG(MAKE)) { 652 printf ("up-to-date\n"); 653 } 654 gn->made = UPTODATE; 655 if (gn->type & OP_JOIN) { 656 /* 657 * Even for an up-to-date .JOIN node, we need it to have its 658 * context variables so references to it get the correct 659 * value for .TARGET when building up the context variables 660 * of its parent(s)... 661 */ 662 Make_DoAllVar (gn); 663 } 664 665 Make_Update (gn); 666 } 667 } 668 return (FALSE); 669 } 670 671 /*- 672 *----------------------------------------------------------------------- 673 * MakePrintStatus -- 674 * Print the status of a top-level node, viz. it being up-to-date 675 * already or not created due to an error in a lower level. 676 * Callback function for Make_Run via Lst_ForEach. 677 * 678 * Results: 679 * Always returns 0. 680 * 681 * Side Effects: 682 * A message may be printed. 683 * 684 *----------------------------------------------------------------------- 685 */ 686 static int 687 MakePrintStatus(gn, cycle) 688 GNode *gn; /* Node to examine */ 689 Boolean cycle; /* True if gn->unmade being non-zero implies 690 * a cycle in the graph, not an error in an 691 * inferior */ 692 { 693 if (gn->made == UPTODATE) { 694 printf ("`%s' is up to date.\n", gn->name); 695 } else if (gn->unmade != 0) { 696 if (cycle) { 697 /* 698 * If printing cycles and came to one that has unmade children, 699 * print out the cycle by recursing on its children. Note a 700 * cycle like: 701 * a : b 702 * b : c 703 * c : b 704 * will cause this to erroneously complain about a being in 705 * the cycle, but this is a good approximation. 706 */ 707 if (gn->made == CYCLE) { 708 Error("Graph cycles through `%s'", gn->name); 709 gn->made = ENDCYCLE; 710 Lst_ForEach(gn->children, MakePrintStatus, (ClientData)TRUE); 711 gn->made = UNMADE; 712 } else if (gn->made != ENDCYCLE) { 713 gn->made = CYCLE; 714 Lst_ForEach(gn->children, MakePrintStatus, (ClientData)TRUE); 715 } 716 } else { 717 printf ("`%s' not remade because of errors.\n", gn->name); 718 } 719 } 720 return (0); 721 } 722 723 /*- 724 *----------------------------------------------------------------------- 725 * Make_Run -- 726 * Initialize the nodes to remake and the list of nodes which are 727 * ready to be made by doing a breadth-first traversal of the graph 728 * starting from the nodes in the given list. Once this traversal 729 * is finished, all the 'leaves' of the graph are in the toBeMade 730 * queue. 731 * Using this queue and the Job module, work back up the graph, 732 * calling on MakeStartJobs to keep the job table as full as 733 * possible. 734 * 735 * Results: 736 * TRUE if work was done. FALSE otherwise. 737 * 738 * Side Effects: 739 * The make field of all nodes involved in the creation of the given 740 * targets is set to 1. The toBeMade list is set to contain all the 741 * 'leaves' of these subgraphs. 742 *----------------------------------------------------------------------- 743 */ 744 Boolean 745 Make_Run (targs) 746 Lst targs; /* the initial list of targets */ 747 { 748 register GNode *gn; /* a temporary pointer */ 749 register Lst examine; /* List of targets to examine */ 750 int errors; /* Number of errors the Job module reports */ 751 752 toBeMade = Lst_Init (FALSE); 753 754 examine = Lst_Duplicate(targs, NOCOPY); 755 numNodes = 0; 756 757 /* 758 * Make an initial downward pass over the graph, marking nodes to be made 759 * as we go down. We call Suff_FindDeps to find where a node is and 760 * to get some children for it if it has none and also has no commands. 761 * If the node is a leaf, we stick it on the toBeMade queue to 762 * be looked at in a minute, otherwise we add its children to our queue 763 * and go on about our business. 764 */ 765 while (!Lst_IsEmpty (examine)) { 766 gn = (GNode *) Lst_DeQueue (examine); 767 768 if (!gn->make) { 769 gn->make = TRUE; 770 numNodes++; 771 772 /* 773 * Apply any .USE rules before looking for implicit dependencies 774 * to make sure everything has commands that should... 775 */ 776 Lst_ForEach (gn->children, Make_HandleUse, (ClientData)gn); 777 Suff_FindDeps (gn); 778 779 if (gn->unmade != 0) { 780 Lst_ForEach (gn->children, MakeAddChild, (ClientData)examine); 781 } else { 782 (void)Lst_EnQueue (toBeMade, (ClientData)gn); 783 } 784 } 785 } 786 787 Lst_Destroy (examine, NOFREE); 788 789 if (queryFlag) { 790 /* 791 * We wouldn't do any work unless we could start some jobs in the 792 * next loop... (we won't actually start any, of course, this is just 793 * to see if any of the targets was out of date) 794 */ 795 return (MakeStartJobs()); 796 } else { 797 /* 798 * Initialization. At the moment, no jobs are running and until some 799 * get started, nothing will happen since the remaining upward 800 * traversal of the graph is performed by the routines in job.c upon 801 * the finishing of a job. So we fill the Job table as much as we can 802 * before going into our loop. 803 */ 804 (void) MakeStartJobs(); 805 } 806 807 /* 808 * Main Loop: The idea here is that the ending of jobs will take 809 * care of the maintenance of data structures and the waiting for output 810 * will cause us to be idle most of the time while our children run as 811 * much as possible. Because the job table is kept as full as possible, 812 * the only time when it will be empty is when all the jobs which need 813 * running have been run, so that is the end condition of this loop. 814 * Note that the Job module will exit if there were any errors unless the 815 * keepgoing flag was given. 816 */ 817 while (!Job_Empty ()) { 818 Job_CatchOutput (); 819 Job_CatchChildren (!usePipes); 820 (void)MakeStartJobs(); 821 } 822 823 errors = Job_End(); 824 825 /* 826 * Print the final status of each target. E.g. if it wasn't made 827 * because some inferior reported an error. 828 */ 829 Lst_ForEach(targs, MakePrintStatus, 830 (ClientData)((errors == 0) && (numNodes != 0))); 831 832 return (TRUE); 833 } 834