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.18 2005/01/06 10:53:00 okumoto 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 <stdlib.h>
  76
  77 #include "arch.h"
  78 #include "config.h"
  79 #include "dir.h"
  80 #include "globals.h"
  81 #include "GNode.h"
  82 #include "job.h"
  83 #include "make.h"
  84 #include "suff.h"
  85 #include "targ.h"
  86 #include "util.h"
  87 #include "var.h"
  88
  89 /* The current fringe of the graph. These are nodes which await examination
  90  * by MakeOODate. It is added to by Make_Update and subtracted from by
  91  * MakeStartJobs */
  92 static Lst toBeMade = Lst_Initializer(toBeMade);
  93
  94 static int      numNodes;       /* Number of nodes to be processed. If this
  95                                  * is non-zero when Job_Empty() returns
  96                                  * TRUE, there's a cycle in the graph */
  97
  98 static int MakeAddChild(void *, void *);
  99 static int MakeAddAllSrc(void *, void *);
 100 static int MakeTimeStamp(void *, void *);
 101 static int MakeHandleUse(void *, void *);
 102 static Boolean MakeStartJobs(void);
 103 static int MakePrintStatus(void *, void *);
 104
 105 /*-
 106  *-----------------------------------------------------------------------
 107  * Make_TimeStamp --
 108  *      Set the cmtime field of a parent node based on the mtime stamp in its
 109  *      child. Called from MakeOODate via Lst_ForEach.
 110  *
 111  * Results:
 112  *      Always returns 0.
 113  *
 114  * Side Effects:
 115  *      The cmtime of the parent node will be changed if the mtime
 116  *      field of the child is greater than it.
 117  *-----------------------------------------------------------------------
 118  */
 119 int
 120 Make_TimeStamp(GNode *pgn, GNode *cgn)
 121 {
 122
 123     if (cgn->mtime > pgn->cmtime) {
 124         pgn->cmtime = cgn->mtime;
 125     }
 126     return (0);
 127 }
 128
 129 static int
 130 MakeTimeStamp(void *pgn, void *cgn)
 131 {
 132
 133     return (Make_TimeStamp(pgn, cgn));
 134 }
 135
 136 /*-
 137  *-----------------------------------------------------------------------
 138  * Make_OODate --
 139  *      See if a given node is out of date with respect to its sources.
 140  *      Used by Make_Run when deciding which nodes to place on the
 141  *      toBeMade queue initially and by Make_Update to screen out USE and
 142  *      EXEC nodes. In the latter case, however, any other sort of node
 143  *      must be considered out-of-date since at least one of its children
 144  *      will have been recreated.
 145  *
 146  * Results:
 147  *      TRUE if the node is out of date. FALSE otherwise.
 148  *
 149  * Side Effects:
 150  *      The mtime field of the node and the cmtime field of its parents
 151  *      will/may be changed.
 152  *-----------------------------------------------------------------------
 153  */
 154 Boolean
 155 Make_OODate(GNode *gn)
 156 {
 157     Boolean         oodate;
 158
 159     /*
 160      * Certain types of targets needn't even be sought as their datedness
 161      * doesn't depend on their modification time...
 162      */
 163     if ((gn->type & (OP_JOIN | OP_USE | OP_EXEC)) == 0) {
 164         Dir_MTime(gn);
 165         if (gn->mtime != 0) {
 166             DEBUGF(MAKE, ("modified %s...", Targ_FmtTime(gn->mtime)));
 167         } else {
 168             DEBUGF(MAKE, ("non-existent..."));
 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         DEBUGF(MAKE, (".USE node..."));
 192         oodate = FALSE;
 193     } else if (gn->type & OP_LIB) {
 194         DEBUGF(MAKE, ("library..."));
 195
 196         /*
 197          * always out of date if no children and :: target
 198          */
 199
 200         oodate = Arch_LibOODate(gn) ||
 201             ((gn->cmtime == 0) && (gn->type & OP_DOUBLEDEP));
 202     } else if (gn->type & OP_JOIN) {
 203         /*
 204          * A target with the .JOIN attribute is only considered
 205          * out-of-date if any of its children was out-of-date.
 206          */
 207         DEBUGF(MAKE, (".JOIN node..."));
 208         oodate = gn->childMade;
 209     } else if (gn->type & (OP_FORCE|OP_EXEC|OP_PHONY)) {
 210         /*
 211          * A node which is the object of the force (!) operator or which has
 212          * the .EXEC attribute is always considered out-of-date.
 213          */
 214         if (gn->type & OP_FORCE) {
 215             DEBUGF(MAKE, ("! operator..."));
 216         } else if (gn->type & OP_PHONY) {
 217             DEBUGF(MAKE, (".PHONY node..."));
 218         } else {
 219             DEBUGF(MAKE, (".EXEC node..."));
 220         }
 221         oodate = TRUE;
 222     } else if ((gn->mtime < gn->cmtime) ||
 223                ((gn->cmtime == 0) &&
 224                 ((gn->mtime==0) || (gn->type & OP_DOUBLEDEP))))
 225     {
 226         /*
 227          * A node whose modification time is less than that of its
 228          * youngest child or that has no children (cmtime == 0) and
 229          * either doesn't exist (mtime == 0) or was the object of a
 230          * :: operator is out-of-date. Why? Because that's the way Make does
 231          * it.
 232          */
 233         if (gn->mtime < gn->cmtime) {
 234             DEBUGF(MAKE, ("modified before source..."));
 235         } else if (gn->mtime == 0) {
 236             DEBUGF(MAKE, ("non-existent and no sources..."));
 237         } else {
 238             DEBUGF(MAKE, (":: operator and no sources..."));
 239         }
 240         oodate = TRUE;
 241     } else
 242         oodate = FALSE;
 243
 244     /*
 245      * If the target isn't out-of-date, the parents need to know its
 246      * modification time. Note that targets that appear to be out-of-date
 247      * but aren't, because they have no commands and aren't of type OP_NOP,
 248      * have their mtime stay below their children's mtime to keep parents from
 249      * thinking they're out-of-date.
 250      */
 251     if (!oodate) {
 252         Lst_ForEach(&gn->parents, MakeTimeStamp, gn);
 253     }
 254
 255     return (oodate);
 256 }
 257
 258 /*-
 259  *-----------------------------------------------------------------------
 260  * MakeAddChild  --
 261  *      Function used by Make_Run to add a child to the list l.
 262  *      It will only add the child if its make field is FALSE.
 263  *
 264  * Results:
 265  *      Always returns 0
 266  *
 267  * Side Effects:
 268  *      The given list is extended
 269  *-----------------------------------------------------------------------
 270  */
 271 static int
 272 MakeAddChild(void *gnp, void *lp)
 273 {
 274     GNode *gn = gnp;
 275     Lst *l = lp;
 276
 277     if (!gn->make && !(gn->type & OP_USE)) {
 278         Lst_EnQueue(l, gn);
 279     }
 280     return (0);
 281 }
 282
 283 /*-
 284  *-----------------------------------------------------------------------
 285  * Make_HandleUse --
 286  *      Function called by Make_Run and SuffApplyTransform on the downward
 287  *      pass to handle .USE and transformation nodes. A callback function
 288  *      for Lst_ForEach, it implements the .USE and transformation
 289  *      functionality by copying the node's commands, type flags
 290  *      and children to the parent node. Should be called before the
 291  *      children are enqueued to be looked at by MakeAddChild.
 292  *
 293  *      A .USE node is much like an explicit transformation rule, except
 294  *      its commands are always added to the target node, even if the
 295  *      target already has commands.
 296  *
 297  * Results:
 298  *      returns 0.
 299  *
 300  * Side Effects:
 301  *      Children and commands may be added to the parent and the parent's
 302  *      type may be changed.
 303  *
 304  *-----------------------------------------------------------------------
 305  */
 306 int
 307 Make_HandleUse(GNode *cgn, GNode *pgn)
 308 {
 309     GNode       *gn;            /* A child of the .USE node */
 310     LstNode     *ln;            /* An element in the children list */
 311
 312     if (cgn->type & (OP_USE | OP_TRANSFORM)) {
 313         if ((cgn->type & OP_USE) || Lst_IsEmpty(&pgn->commands)) {
 314             /*
 315              * .USE or transformation and target has no commands -- append
 316              * the child's commands to the parent.
 317              */
 318              Lst_Concat(&pgn->commands, &cgn->commands, LST_CONCNEW);
 319         }
 320
 321         for (ln = Lst_First(&cgn->children); ln != NULL; ln = Lst_Succ(ln)) {
 322             gn = Lst_Datum(ln);
 323
 324             if (Lst_Member(&pgn->children, gn) == NULL) {
 325                 Lst_AtEnd(&pgn->children, gn);
 326                 Lst_AtEnd(&gn->parents, pgn);
 327                 pgn->unmade += 1;
 328             }
 329         }
 330
 331         pgn->type |= cgn->type & ~(OP_OPMASK | OP_USE | OP_TRANSFORM);
 332
 333         /*
 334          * This child node is now "made", so we decrement the count of
 335          * unmade children in the parent... We also remove the child
 336          * from the parent's list to accurately reflect the number of decent
 337          * children the parent has. This is used by Make_Run to decide
 338          * whether to queue the parent or examine its children...
 339          */
 340         if (cgn->type & OP_USE) {
 341             pgn->unmade--;
 342         }
 343     }
 344     return (0);
 345 }
 346
 347 static int
 348 MakeHandleUse(void *pgn, void *cgn)
 349 {
 350
 351     return (Make_HandleUse(pgn, cgn));
 352 }
 353
 354 /*-
 355  *-----------------------------------------------------------------------
 356  * Make_Update  --
 357  *      Perform update on the parents of a node. Used by JobFinish once
 358  *      a node has been dealt with and by MakeStartJobs if it finds an
 359  *      up-to-date node.
 360  *
 361  * Results:
 362  *      Always returns 0
 363  *
 364  * Side Effects:
 365  *      The unmade field of pgn is decremented and pgn may be placed on
 366  *      the toBeMade queue if this field becomes 0.
 367  *
 368  *      If the child was made, the parent's childMade field will be set true
 369  *      and its cmtime set to now.
 370  *
 371  *      If the child wasn't made, the cmtime field of the parent will be
 372  *      altered if the child's mtime is big enough.
 373  *
 374  *      Finally, if the child is the implied source for the parent, the
 375  *      parent's IMPSRC variable is set appropriately.
 376  *
 377  *-----------------------------------------------------------------------
 378  */
 379 void
 380 Make_Update(GNode *cgn)
 381 {
 382     GNode       *pgn;           /* the parent node */
 383     char        *cname;         /* the child's name */
 384     LstNode     *ln;            /* Element in parents and iParents lists */
 385     char        *p1;
 386     char        *ptr;
 387     char        *cpref;
 388
 389     cname = Var_Value(TARGET, cgn, &p1);
 390     free(p1);
 391
 392     /*
 393      * If the child was actually made, see what its modification time is
 394      * now -- some rules won't actually update the file. If the file still
 395      * doesn't exist, make its mtime now.
 396      */
 397     if (cgn->made != UPTODATE) {
 398 #ifndef RECHECK
 399         /*
 400          * We can't re-stat the thing, but we can at least take care of rules
 401          * where a target depends on a source that actually creates the
 402          * target, but only if it has changed, e.g.
 403          *
 404          * parse.h : parse.o
 405          *
 406          * parse.o : parse.y
 407          *      yacc -d parse.y
 408          *      cc -c y.tab.c
 409          *      mv y.tab.o parse.o
 410          *      cmp -s y.tab.h parse.h || mv y.tab.h parse.h
 411          *
 412          * In this case, if the definitions produced by yacc haven't changed
 413          * from before, parse.h won't have been updated and cgn->mtime will
 414          * reflect the current modification time for parse.h. This is
 415          * something of a kludge, I admit, but it's a useful one..
 416          * XXX: People like to use a rule like
 417          *
 418          * FRC:
 419          *
 420          * To force things that depend on FRC to be made, so we have to
 421          * check for gn->children being empty as well...
 422          */
 423         if (!Lst_IsEmpty(&cgn->commands) || Lst_IsEmpty(&cgn->children)) {
 424             cgn->mtime = now;
 425         }
 426 #else
 427         /*
 428          * This is what Make does and it's actually a good thing, as it
 429          * allows rules like
 430          *
 431          *      cmp -s y.tab.h parse.h || cp y.tab.h parse.h
 432          *
 433          * to function as intended. Unfortunately, thanks to the stateless
 434          * nature of NFS (by which I mean the loose coupling of two clients
 435          * using the same file from a common server), there are times
 436          * when the modification time of a file created on a remote
 437          * machine will not be modified before the local stat() implied by
 438          * the Dir_MTime occurs, thus leading us to believe that the file
 439          * is unchanged, wreaking havoc with files that depend on this one.
 440          *
 441          * I have decided it is better to make too much than to make too
 442          * little, so this stuff is commented out unless you're sure it's ok.
 443          * -- ardeb 1/12/88
 444          */
 445         /*
 446          * Christos, 4/9/92: If we are  saving commands pretend that
 447          * the target is made now. Otherwise archives with ... rules
 448          * don't work!
 449          */
 450         if (noExecute || (cgn->type & OP_SAVE_CMDS) || Dir_MTime(cgn) == 0) {
 451             cgn->mtime = now;
 452         }
 453         DEBUGF(MAKE, ("update time: %s\n", Targ_FmtTime(cgn->mtime)));
 454 #endif
 455     }
 456
 457     for (ln = Lst_First(&cgn->parents); ln != NULL; ln = Lst_Succ(ln)) {
 458         pgn = Lst_Datum(ln);
 459         if (pgn->make) {
 460             pgn->unmade -= 1;
 461
 462             if (!(cgn->type & (OP_EXEC | OP_USE))) {
 463                 if (cgn->made == MADE) {
 464                     pgn->childMade = TRUE;
 465                     if (pgn->cmtime < cgn->mtime) {
 466                         pgn->cmtime = cgn->mtime;
 467                     }
 468                 } else {
 469                     Make_TimeStamp(pgn, cgn);
 470                 }
 471             }
 472             if (pgn->unmade == 0) {
 473                 /*
 474                  * Queue the node up -- any unmade predecessors will
 475                  * be dealt with in MakeStartJobs.
 476                  */
 477                 Lst_EnQueue(&toBeMade, pgn);
 478             } else if (pgn->unmade < 0) {
 479                 Error("Graph cycles through %s", pgn->name);
 480             }
 481         }
 482     }
 483
 484     /*
 485      * Deal with successor nodes. If any is marked for making and has an unmade
 486      * count of 0, has not been made and isn't in the examination queue,
 487      * it means we need to place it in the queue as it restrained itself
 488      * before.
 489      */
 490     for (ln = Lst_First(&cgn->successors); ln != NULL; ln = Lst_Succ(ln)) {
 491         GNode   *succ = Lst_Datum(ln);
 492
 493         if (succ->make && succ->unmade == 0 && succ->made == UNMADE &&
 494             Lst_Member(&toBeMade, succ) == NULL)
 495         {
 496             Lst_EnQueue(&toBeMade, succ);
 497         }
 498     }
 499
 500     /*
 501      * Set the .PREFIX and .IMPSRC variables for all the implied parents
 502      * of this node.
 503      */
 504     cpref = Var_Value(PREFIX, cgn, &ptr);
 505     for (ln = Lst_First(&cgn->iParents); ln != NULL; ln = Lst_Succ(ln)) {
 506         pgn = Lst_Datum (ln);
 507         if (pgn->make) {
 508             Var_Set(IMPSRC, cname, pgn);
 509             Var_Set(PREFIX, cpref, pgn);
 510         }
 511     }
 512     free(ptr);
 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     Lst_Init(&examine);
 787     Lst_Duplicate(&examine, targs, NOCOPY);
 788     numNodes = 0;
 789
 790     /*
 791      * Make an initial downward pass over the graph, marking nodes to be made
 792      * as we go down. We call Suff_FindDeps to find where a node is and
 793      * to get some children for it if it has none and also has no commands.
 794      * If the node is a leaf, we stick it on the toBeMade queue to
 795      * be looked at in a minute, otherwise we add its children to our queue
 796      * and go on about our business.
 797      */
 798     while (!Lst_IsEmpty(&examine)) {
 799         gn = Lst_DeQueue(&examine);
 800
 801         if (!gn->make) {
 802             gn->make = TRUE;
 803             numNodes++;
 804
 805             /*
 806              * Apply any .USE rules before looking for implicit dependencies
 807              * to make sure everything has commands that should...
 808              */
 809             Lst_ForEach(&gn->children, MakeHandleUse, gn);
 810             Suff_FindDeps(gn);
 811
 812             if (gn->unmade != 0) {
 813                 Lst_ForEach(&gn->children, MakeAddChild, &examine);
 814             } else {
 815                 Lst_EnQueue(&toBeMade, gn);
 816             }
 817         }
 818     }
 819
 820     if (queryFlag) {
 821         /*
 822          * We wouldn't do any work unless we could start some jobs in the
 823          * next loop... (we won't actually start any, of course, this is just
 824          * to see if any of the targets was out of date)
 825          */
 826         return (MakeStartJobs());
 827     } else {
 828         /*
 829          * Initialization. At the moment, no jobs are running and until some
 830          * get started, nothing will happen since the remaining upward
 831          * traversal of the graph is performed by the routines in job.c upon
 832          * the finishing of a job. So we fill the Job table as much as we can
 833          * before going into our loop.
 834          */
 835          MakeStartJobs();
 836     }
 837
 838     /*
 839      * Main Loop: The idea here is that the ending of jobs will take
 840      * care of the maintenance of data structures and the waiting for output
 841      * will cause us to be idle most of the time while our children run as
 842      * much as possible. Because the job table is kept as full as possible,
 843      * the only time when it will be empty is when all the jobs which need
 844      * running have been run, so that is the end condition of this loop.
 845      * Note that the Job module will exit if there were any errors unless the
 846      * keepgoing flag was given.
 847      */
 848     while (!Job_Empty ()) {
 849         Job_CatchOutput(!Lst_IsEmpty(&toBeMade));
 850         Job_CatchChildren(!usePipes);
 851         MakeStartJobs();
 852     }
 853
 854     errors = Job_Finish();
 855
 856     /*
 857      * Print the final status of each target. E.g. if it wasn't made
 858      * because some inferior reported an error.
 859      */
 860     errors = ((errors == 0) && (numNodes != 0));
 861     Lst_ForEach(targs, MakePrintStatus, &errors);
 862
 863     return (TRUE);
 864 }