usr.bin/make/make.c

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