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