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