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