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