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