contrib/bmake/make.c

   1 /*      $NetBSD: make.c,v 1.209 2020/11/16 22:31:42 rillig Exp $        */
   2
   3 /*
   4  * Copyright (c) 1988, 1989, 1990, 1993
   5  *      The Regents of the University of California.  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. Neither the name of the University nor the names of its contributors
  19  *    may be used to endorse or promote products derived from this software
  20  *    without specific prior written permission.
  21  *
  22  * THIS SOFTWARE IS PROVIDED BY THE REGENTS AND CONTRIBUTORS ``AS IS'' AND
  23  * ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
  24  * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE
  25  * ARE DISCLAIMED.  IN NO EVENT SHALL THE REGENTS OR CONTRIBUTORS BE LIABLE
  26  * FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL
  27  * DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS
  28  * OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION)
  29  * HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT
  30  * LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY
  31  * OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF
  32  * SUCH DAMAGE.
  33  */
  34
  35 /*
  36  * Copyright (c) 1989 by Berkeley Softworks
  37  * All rights reserved.
  38  *
  39  * This code is derived from software contributed to Berkeley by
  40  * Adam de Boor.
  41  *
  42  * Redistribution and use in source and binary forms, with or without
  43  * modification, are permitted provided that the following conditions
  44  * are met:
  45  * 1. Redistributions of source code must retain the above copyright
  46  *    notice, this list of conditions and the following disclaimer.
  47  * 2. Redistributions in binary form must reproduce the above copyright
  48  *    notice, this list of conditions and the following disclaimer in the
  49  *    documentation and/or other materials provided with the distribution.
  50  * 3. All advertising materials mentioning features or use of this software
  51  *    must display the following acknowledgement:
  52  *      This product includes software developed by the University of
  53  *      California, Berkeley and its contributors.
  54  * 4. Neither the name of the University nor the names of its contributors
  55  *    may be used to endorse or promote products derived from this software
  56  *    without specific prior written permission.
  57  *
  58  * THIS SOFTWARE IS PROVIDED BY THE REGENTS AND CONTRIBUTORS ``AS IS'' AND
  59  * ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
  60  * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE
  61  * ARE DISCLAIMED.  IN NO EVENT SHALL THE REGENTS OR CONTRIBUTORS BE LIABLE
  62  * FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL
  63  * DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS
  64  * OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION)
  65  * HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT
  66  * LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY
  67  * OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF
  68  * SUCH DAMAGE.
  69  */
  70
  71 /* Examination of targets and their suitability for creation.
  72  *
  73  * Interface:
  74  *      Make_Run        Initialize things for the module. Returns TRUE if
  75  *                      work was (or would have been) done.
  76  *
  77  *      Make_Update     After a target is made, update all its parents.
  78  *                      Perform various bookkeeping chores like the updating
  79  *                      of the youngestChild field of the parent, filling
  80  *                      of the IMPSRC context variable, etc. Place the parent
  81  *                      on the toBeMade queue if it should be.
  82  *
  83  *      GNode_UpdateYoungestChild
  84  *                      Update the node's youngestChild field based on the
  85  *                      child's modification time.
  86  *
  87  *      Make_DoAllVar   Set up the various local variables for a
  88  *                      target, including the .ALLSRC variable, making
  89  *                      sure that any variable that needs to exist
  90  *                      at the very least has the empty value.
  91  *
  92  *      GNode_IsOODate  Determine if a target is out-of-date.
  93  *
  94  *      Make_HandleUse  See if a child is a .USE node for a parent
  95  *                      and perform the .USE actions if so.
  96  *
  97  *      Make_ExpandUse  Expand .USE nodes
  98  */
  99
 100 #include "make.h"
 101 #include "dir.h"
 102 #include "job.h"
 103
 104 /*      "@(#)make.c     8.1 (Berkeley) 6/6/93"  */
 105 MAKE_RCSID("$NetBSD: make.c,v 1.209 2020/11/16 22:31:42 rillig Exp $");
 106
 107 /* Sequence # to detect recursion. */
 108 static unsigned int checked_seqno = 1;
 109
 110 /* The current fringe of the graph.
 111  * These are nodes which await examination by MakeOODate.
 112  * It is added to by Make_Update and subtracted from by MakeStartJobs */
 113 static GNodeList *toBeMade;
 114
 115 static int MakeBuildParent(void *, void *);
 116
 117 void
 118 debug_printf(const char *fmt, ...)
 119 {
 120     va_list args;
 121
 122     va_start(args, fmt);
 123     vfprintf(opts.debug_file, fmt, args);
 124     va_end(args);
 125 }
 126
 127 MAKE_ATTR_DEAD static void
 128 make_abort(GNode *gn, int line)
 129 {
 130     debug_printf("make_abort from line %d\n", line);
 131     Targ_PrintNode(gn, 2);
 132     Targ_PrintNodes(toBeMade, 2);
 133     Targ_PrintGraph(3);
 134     abort();
 135 }
 136
 137 ENUM_VALUE_RTTI_8(GNodeMade,
 138                   UNMADE, DEFERRED, REQUESTED, BEINGMADE,
 139                   MADE, UPTODATE, ERROR, ABORTED);
 140
 141 ENUM_FLAGS_RTTI_31(GNodeType,
 142                    OP_DEPENDS, OP_FORCE, OP_DOUBLEDEP,
 143                    /* OP_OPMASK is omitted since it combines other flags */
 144                    OP_OPTIONAL, OP_USE, OP_EXEC, OP_IGNORE,
 145                    OP_PRECIOUS, OP_SILENT, OP_MAKE, OP_JOIN,
 146                    OP_MADE, OP_SPECIAL, OP_USEBEFORE, OP_INVISIBLE,
 147                    OP_NOTMAIN, OP_PHONY, OP_NOPATH, OP_WAIT,
 148                    OP_NOMETA, OP_META, OP_NOMETA_CMP, OP_SUBMAKE,
 149                    OP_TRANSFORM, OP_MEMBER, OP_LIB, OP_ARCHV,
 150                    OP_HAS_COMMANDS, OP_SAVE_CMDS, OP_DEPS_FOUND, OP_MARK);
 151
 152 ENUM_FLAGS_RTTI_10(GNodeFlags,
 153                    REMAKE, CHILDMADE, FORCE, DONE_WAIT,
 154                    DONE_ORDER, FROM_DEPEND, DONE_ALLSRC, CYCLE,
 155                    DONECYCLE, INTERNAL);
 156
 157 void
 158 GNode_FprintDetails(FILE *f, const char *prefix, const GNode *gn,
 159                     const char *suffix)
 160 {
 161     char type_buf[GNodeType_ToStringSize];
 162     char flags_buf[GNodeFlags_ToStringSize];
 163
 164     fprintf(f, "%smade %s, type %s, flags %s%s",
 165             prefix,
 166             Enum_ValueToString(gn->made, GNodeMade_ToStringSpecs),
 167             Enum_FlagsToString(type_buf, sizeof type_buf,
 168                                gn->type, GNodeType_ToStringSpecs),
 169             Enum_FlagsToString(flags_buf, sizeof flags_buf,
 170                                gn->flags, GNodeFlags_ToStringSpecs),
 171             suffix);
 172 }
 173
 174 Boolean
 175 GNode_ShouldExecute(GNode *gn)
 176 {
 177     return !((gn->type & OP_MAKE) ? opts.noRecursiveExecute : opts.noExecute);
 178 }
 179
 180 /* Update the youngest child of the node, according to the given child. */
 181 void
 182 GNode_UpdateYoungestChild(GNode *gn, GNode *cgn)
 183 {
 184     if (gn->youngestChild == NULL || cgn->mtime > gn->youngestChild->mtime)
 185         gn->youngestChild = cgn;
 186 }
 187
 188 static Boolean
 189 IsOODateRegular(GNode *gn)
 190 {
 191     /* These rules are inherited from the original Make. */
 192
 193     if (gn->youngestChild != NULL) {
 194         if (gn->mtime < gn->youngestChild->mtime) {
 195             DEBUG1(MAKE, "modified before source \"%s\"...",
 196                    GNode_Path(gn->youngestChild));
 197             return TRUE;
 198         }
 199         return FALSE;
 200     }
 201
 202     if (gn->mtime == 0 && !(gn->type & OP_OPTIONAL)) {
 203         DEBUG0(MAKE, "non-existent and no sources...");
 204         return TRUE;
 205     }
 206
 207     if (gn->type & OP_DOUBLEDEP) {
 208         DEBUG0(MAKE, ":: operator and no sources...");
 209         return TRUE;
 210     }
 211
 212     return FALSE;
 213 }
 214
 215 /* See if the node is out of date with respect to its sources.
 216  *
 217  * Used by Make_Run when deciding which nodes to place on the
 218  * toBeMade queue initially and by Make_Update to screen out .USE and
 219  * .EXEC nodes. In the latter case, however, any other sort of node
 220  * must be considered out-of-date since at least one of its children
 221  * will have been recreated.
 222  *
 223  * The mtime field of the node and the youngestChild field of its parents
 224  * may be changed.
 225  */
 226 Boolean
 227 GNode_IsOODate(GNode *gn)
 228 {
 229     Boolean         oodate;
 230
 231     /*
 232      * Certain types of targets needn't even be sought as their datedness
 233      * doesn't depend on their modification time...
 234      */
 235     if (!(gn->type & (OP_JOIN|OP_USE|OP_USEBEFORE|OP_EXEC))) {
 236         Dir_UpdateMTime(gn, TRUE);
 237         if (DEBUG(MAKE)) {
 238             if (gn->mtime != 0)
 239                 debug_printf("modified %s...", Targ_FmtTime(gn->mtime));
 240             else
 241                 debug_printf("non-existent...");
 242         }
 243     }
 244
 245     /*
 246      * A target is remade in one of the following circumstances:
 247      *  its modification time is smaller than that of its youngest child and
 248      *      it would actually be run (has commands or is not GNode_IsTarget)
 249      *  it's the object of a force operator
 250      *  it has no children, was on the lhs of an operator and doesn't exist
 251      *      already.
 252      *
 253      * Libraries are only considered out-of-date if the archive module says
 254      * they are.
 255      *
 256      * These weird rules are brought to you by Backward-Compatibility and
 257      * the strange people who wrote 'Make'.
 258      */
 259     if (gn->type & (OP_USE|OP_USEBEFORE)) {
 260         /*
 261          * If the node is a USE node it is *never* out of date
 262          * no matter *what*.
 263          */
 264         DEBUG0(MAKE, ".USE node...");
 265         oodate = FALSE;
 266     } else if ((gn->type & OP_LIB) && (gn->mtime == 0 || Arch_IsLib(gn))) {
 267         DEBUG0(MAKE, "library...");
 268
 269         /*
 270          * always out of date if no children and :: target
 271          * or non-existent.
 272          */
 273         oodate = (gn->mtime == 0 || Arch_LibOODate(gn) ||
 274                   (gn->youngestChild == NULL && (gn->type & OP_DOUBLEDEP)));
 275     } else if (gn->type & OP_JOIN) {
 276         /*
 277          * A target with the .JOIN attribute is only considered
 278          * out-of-date if any of its children was out-of-date.
 279          */
 280         DEBUG0(MAKE, ".JOIN node...");
 281         DEBUG1(MAKE, "source %smade...", gn->flags & CHILDMADE ? "" : "not ");
 282         oodate = (gn->flags & CHILDMADE) != 0;
 283     } else if (gn->type & (OP_FORCE|OP_EXEC|OP_PHONY)) {
 284         /*
 285          * A node which is the object of the force (!) operator or which has
 286          * the .EXEC attribute is always considered out-of-date.
 287          */
 288         if (DEBUG(MAKE)) {
 289             if (gn->type & OP_FORCE) {
 290                 debug_printf("! operator...");
 291             } else if (gn->type & OP_PHONY) {
 292                 debug_printf(".PHONY node...");
 293             } else {
 294                 debug_printf(".EXEC node...");
 295             }
 296         }
 297         oodate = TRUE;
 298     } else if (IsOODateRegular(gn)) {
 299         oodate = TRUE;
 300     } else {
 301         /*
 302          * When a non-existing child with no sources
 303          * (such as a typically used FORCE source) has been made and
 304          * the target of the child (usually a directory) has the same
 305          * timestamp as the timestamp just given to the non-existing child
 306          * after it was considered made.
 307          */
 308         if (DEBUG(MAKE)) {
 309             if (gn->flags & FORCE)
 310                 debug_printf("non existing child...");
 311         }
 312         oodate = (gn->flags & FORCE) != 0;
 313     }
 314
 315 #ifdef USE_META
 316     if (useMeta) {
 317         oodate = meta_oodate(gn, oodate);
 318     }
 319 #endif
 320
 321     /*
 322      * If the target isn't out-of-date, the parents need to know its
 323      * modification time. Note that targets that appear to be out-of-date
 324      * but aren't, because they have no commands and are GNode_IsTarget,
 325      * have their mtime stay below their children's mtime to keep parents from
 326      * thinking they're out-of-date.
 327      */
 328     if (!oodate) {
 329         GNodeListNode *ln;
 330         for (ln = gn->parents->first; ln != NULL; ln = ln->next)
 331             GNode_UpdateYoungestChild(ln->datum, gn);
 332     }
 333
 334     return oodate;
 335 }
 336
 337 static void
 338 PretendAllChildrenAreMade(GNode *pgn)
 339 {
 340     GNodeListNode *ln;
 341
 342     for (ln = pgn->children->first; ln != NULL; ln = ln->next) {
 343         GNode *cgn = ln->datum;
 344
 345         Dir_UpdateMTime(cgn, FALSE);    /* cgn->path may get updated as well */
 346         GNode_UpdateYoungestChild(pgn, cgn);
 347         pgn->unmade--;
 348     }
 349 }
 350
 351 /* Called by Make_Run and SuffApplyTransform on the downward pass to handle
 352  * .USE and transformation nodes, by copying the child node's commands, type
 353  * flags and children to the parent node.
 354  *
 355  * A .USE node is much like an explicit transformation rule, except its
 356  * commands are always added to the target node, even if the target already
 357  * has commands.
 358  *
 359  * Input:
 360  *      cgn             The source node, which is either a .USE/.USEBEFORE
 361  *                      node or a transformation node (OP_TRANSFORM).
 362  *      pgn             The target node
 363  */
 364 void
 365 Make_HandleUse(GNode *cgn, GNode *pgn)
 366 {
 367     GNodeListNode *ln;  /* An element in the children list */
 368
 369 #ifdef DEBUG_SRC
 370     if (!(cgn->type & (OP_USE|OP_USEBEFORE|OP_TRANSFORM))) {
 371         debug_printf("Make_HandleUse: called for plain node %s\n", cgn->name);
 372         return;         /* XXX: debug mode should not affect control flow */
 373     }
 374 #endif
 375
 376     if ((cgn->type & (OP_USE|OP_USEBEFORE)) || Lst_IsEmpty(pgn->commands)) {
 377             if (cgn->type & OP_USEBEFORE) {
 378                 /* .USEBEFORE */
 379                 Lst_PrependAll(pgn->commands, cgn->commands);
 380             } else {
 381                 /* .USE, or target has no commands */
 382                 Lst_AppendAll(pgn->commands, cgn->commands);
 383             }
 384     }
 385
 386     for (ln = cgn->children->first; ln != NULL; ln = ln->next) {
 387         GNode *gn = ln->datum;
 388
 389         /*
 390          * Expand variables in the .USE node's name
 391          * and save the unexpanded form.
 392          * We don't need to do this for commands.
 393          * They get expanded properly when we execute.
 394          */
 395         if (gn->uname == NULL) {
 396             gn->uname = gn->name;
 397         } else {
 398             free(gn->name);
 399         }
 400         (void)Var_Subst(gn->uname, pgn, VARE_WANTRES, &gn->name);
 401         /* TODO: handle errors */
 402         if (gn->uname && strcmp(gn->name, gn->uname) != 0) {
 403             /* See if we have a target for this node. */
 404             GNode *tgn = Targ_FindNode(gn->name);
 405             if (tgn != NULL)
 406                 gn = tgn;
 407         }
 408
 409         Lst_Append(pgn->children, gn);
 410         Lst_Append(gn->parents, pgn);
 411         pgn->unmade++;
 412     }
 413
 414     pgn->type |= cgn->type & ~(OP_OPMASK|OP_USE|OP_USEBEFORE|OP_TRANSFORM);
 415 }
 416
 417 /* Used by Make_Run on the downward pass to handle .USE nodes. Should be
 418  * called before the children are enqueued to be looked at by MakeAddChild.
 419  *
 420  * For a .USE child, the commands, type flags and children are copied to the
 421  * parent node, and since the relation to the .USE node is then no longer
 422  * needed, that relation is removed.
 423  *
 424  * Input:
 425  *      cgn             the child, which may be a .USE node
 426  *      pgn             the current parent
 427  */
 428 static void
 429 MakeHandleUse(GNode *cgn, GNode *pgn, GNodeListNode *ln)
 430 {
 431     Boolean unmarked;
 432
 433     unmarked = !(cgn->type & OP_MARK);
 434     cgn->type |= OP_MARK;
 435
 436     if (!(cgn->type & (OP_USE|OP_USEBEFORE)))
 437         return;
 438
 439     if (unmarked)
 440         Make_HandleUse(cgn, pgn);
 441
 442     /*
 443      * This child node is now "made", so we decrement the count of
 444      * unmade children in the parent... We also remove the child
 445      * from the parent's list to accurately reflect the number of decent
 446      * children the parent has. This is used by Make_Run to decide
 447      * whether to queue the parent or examine its children...
 448      */
 449     Lst_Remove(pgn->children, ln);
 450     pgn->unmade--;
 451 }
 452
 453 static void
 454 HandleUseNodes(GNode *gn)
 455 {
 456     GNodeListNode *ln, *nln;
 457     for (ln = gn->children->first; ln != NULL; ln = nln) {
 458         nln = ln->next;
 459         MakeHandleUse(ln->datum, gn, ln);
 460     }
 461 }
 462
 463
 464 /* Check the modification time of a gnode, and update it if necessary.
 465  * Return 0 if the gnode does not exist, or its filesystem time if it does. */
 466 time_t
 467 Make_Recheck(GNode *gn)
 468 {
 469     time_t mtime;
 470
 471     Dir_UpdateMTime(gn, TRUE);
 472     mtime = gn->mtime;
 473
 474 #ifndef RECHECK
 475     /*
 476      * We can't re-stat the thing, but we can at least take care of rules
 477      * where a target depends on a source that actually creates the
 478      * target, but only if it has changed, e.g.
 479      *
 480      * parse.h : parse.o
 481      *
 482      * parse.o : parse.y
 483      *          yacc -d parse.y
 484      *          cc -c y.tab.c
 485      *          mv y.tab.o parse.o
 486      *          cmp -s y.tab.h parse.h || mv y.tab.h parse.h
 487      *
 488      * In this case, if the definitions produced by yacc haven't changed
 489      * from before, parse.h won't have been updated and gn->mtime will
 490      * reflect the current modification time for parse.h. This is
 491      * something of a kludge, I admit, but it's a useful one.
 492      *
 493      * XXX: People like to use a rule like "FRC:" to force things that
 494      * depend on FRC to be made, so we have to check for gn->children
 495      * being empty as well.
 496      */
 497     if (!Lst_IsEmpty(gn->commands) || Lst_IsEmpty(gn->children)) {
 498         gn->mtime = now;
 499     }
 500 #else
 501     /*
 502      * This is what Make does and it's actually a good thing, as it
 503      * allows rules like
 504      *
 505      *  cmp -s y.tab.h parse.h || cp y.tab.h parse.h
 506      *
 507      * to function as intended. Unfortunately, thanks to the stateless
 508      * nature of NFS (by which I mean the loose coupling of two clients
 509      * using the same file from a common server), there are times
 510      * when the modification time of a file created on a remote
 511      * machine will not be modified before the local stat() implied by
 512      * the Dir_UpdateMTime occurs, thus leading us to believe that the file
 513      * is unchanged, wreaking havoc with files that depend on this one.
 514      *
 515      * I have decided it is better to make too much than to make too
 516      * little, so this stuff is commented out unless you're sure it's ok.
 517      * -- ardeb 1/12/88
 518      */
 519     /*
 520      * Christos, 4/9/92: If we are saving commands, pretend that
 521      * the target is made now. Otherwise archives with '...' rules
 522      * don't work!
 523      */
 524     if (!GNode_ShouldExecute(gn) || (gn->type & OP_SAVE_CMDS) ||
 525             (mtime == 0 && !(gn->type & OP_WAIT))) {
 526         DEBUG2(MAKE, " recheck(%s): update time from %s to now\n",
 527                gn->name, Targ_FmtTime(gn->mtime));
 528         gn->mtime = now;
 529     } else {
 530         DEBUG2(MAKE, " recheck(%s): current update time: %s\n",
 531                gn->name, Targ_FmtTime(gn->mtime));
 532     }
 533 #endif
 534
 535     /* XXX: The returned mtime may differ from gn->mtime.
 536      * Intentionally? */
 537     return mtime;
 538 }
 539
 540 /*
 541  * Set the .PREFIX and .IMPSRC variables for all the implied parents
 542  * of this node.
 543  */
 544 static void
 545 UpdateImplicitParentsVars(GNode *cgn, const char *cname)
 546 {
 547     GNodeListNode *ln;
 548     const char *cpref = GNode_VarPrefix(cgn);
 549
 550     for (ln = cgn->implicitParents->first; ln != NULL; ln = ln->next) {
 551         GNode *pgn = ln->datum;
 552         if (pgn->flags & REMAKE) {
 553             Var_Set(IMPSRC, cname, pgn);
 554             if (cpref != NULL)
 555                 Var_Set(PREFIX, cpref, pgn);
 556         }
 557     }
 558 }
 559
 560 /* See if a .ORDER rule stops us from building this node. */
 561 static Boolean
 562 IsWaitingForOrder(GNode *gn)
 563 {
 564     GNodeListNode *ln;
 565
 566     for (ln = gn->order_pred->first; ln != NULL; ln = ln->next) {
 567         GNode *ogn = ln->datum;
 568
 569         if (ogn->made >= MADE || !(ogn->flags & REMAKE))
 570             continue;
 571
 572         DEBUG2(MAKE, "IsWaitingForOrder: Waiting for .ORDER node \"%s%s\"\n",
 573                ogn->name, ogn->cohort_num);
 574         return TRUE;
 575     }
 576     return FALSE;
 577 }
 578
 579 /* Perform update on the parents of a node. Used by JobFinish once
 580  * a node has been dealt with and by MakeStartJobs if it finds an
 581  * up-to-date node.
 582  *
 583  * The unmade field of pgn is decremented and pgn may be placed on
 584  * the toBeMade queue if this field becomes 0.
 585  *
 586  * If the child was made, the parent's flag CHILDMADE field will be
 587  * set true.
 588  *
 589  * If the child is not up-to-date and still does not exist,
 590  * set the FORCE flag on the parents.
 591  *
 592  * If the child wasn't made, the youngestChild field of the parent will be
 593  * altered if the child's mtime is big enough.
 594  *
 595  * Finally, if the child is the implied source for the parent, the
 596  * parent's IMPSRC variable is set appropriately.
 597  */
 598 void
 599 Make_Update(GNode *cgn)
 600 {
 601     const char *cname;          /* the child's name */
 602     time_t      mtime = -1;
 603     GNodeList *parents;
 604     GNodeListNode *ln;
 605     GNode       *centurion;
 606
 607     /* It is save to re-examine any nodes again */
 608     checked_seqno++;
 609
 610     cname = GNode_VarTarget(cgn);
 611
 612     DEBUG2(MAKE, "Make_Update: %s%s\n", cgn->name, cgn->cohort_num);
 613
 614     /*
 615      * If the child was actually made, see what its modification time is
 616      * now -- some rules won't actually update the file. If the file still
 617      * doesn't exist, make its mtime now.
 618      */
 619     if (cgn->made != UPTODATE) {
 620         mtime = Make_Recheck(cgn);
 621     }
 622
 623     /*
 624      * If this is a `::' node, we must consult its first instance
 625      * which is where all parents are linked.
 626      */
 627     if ((centurion = cgn->centurion) != NULL) {
 628         if (!Lst_IsEmpty(cgn->parents))
 629                 Punt("%s%s: cohort has parents", cgn->name, cgn->cohort_num);
 630         centurion->unmade_cohorts--;
 631         if (centurion->unmade_cohorts < 0)
 632             Error("Graph cycles through centurion %s", centurion->name);
 633     } else {
 634         centurion = cgn;
 635     }
 636     parents = centurion->parents;
 637
 638     /* If this was a .ORDER node, schedule the RHS */
 639     Lst_ForEachUntil(centurion->order_succ, MakeBuildParent, toBeMade->first);
 640
 641     /* Now mark all the parents as having one less unmade child */
 642     for (ln = parents->first; ln != NULL; ln = ln->next) {
 643         GNode *pgn = ln->datum;
 644
 645         if (DEBUG(MAKE)) {
 646             debug_printf("inspect parent %s%s: ", pgn->name, pgn->cohort_num);
 647             GNode_FprintDetails(opts.debug_file, "", pgn, "");
 648             debug_printf(", unmade %d ", pgn->unmade - 1);
 649         }
 650
 651         if (!(pgn->flags & REMAKE)) {
 652             /* This parent isn't needed */
 653             DEBUG0(MAKE, "- not needed\n");
 654             continue;
 655         }
 656         if (mtime == 0 && !(cgn->type & OP_WAIT))
 657             pgn->flags |= FORCE;
 658
 659         /*
 660          * If the parent has the .MADE attribute, its timestamp got
 661          * updated to that of its newest child, and its unmade
 662          * child count got set to zero in Make_ExpandUse().
 663          * However other things might cause us to build one of its
 664          * children - and so we mustn't do any processing here when
 665          * the child build finishes.
 666          */
 667         if (pgn->type & OP_MADE) {
 668             DEBUG0(MAKE, "- .MADE\n");
 669             continue;
 670         }
 671
 672         if (!(cgn->type & (OP_EXEC | OP_USE | OP_USEBEFORE))) {
 673             if (cgn->made == MADE)
 674                 pgn->flags |= CHILDMADE;
 675             GNode_UpdateYoungestChild(pgn, cgn);
 676         }
 677
 678         /*
 679          * A parent must wait for the completion of all instances
 680          * of a `::' dependency.
 681          */
 682         if (centurion->unmade_cohorts != 0 || centurion->made < MADE) {
 683             DEBUG2(MAKE, "- centurion made %d, %d unmade cohorts\n",
 684                    centurion->made, centurion->unmade_cohorts);
 685             continue;
 686         }
 687
 688         /* One more child of this parent is now made */
 689         pgn->unmade--;
 690         if (pgn->unmade < 0) {
 691             if (DEBUG(MAKE)) {
 692                 debug_printf("Graph cycles through %s%s\n",
 693                              pgn->name, pgn->cohort_num);
 694                 Targ_PrintGraph(2);
 695             }
 696             Error("Graph cycles through %s%s", pgn->name, pgn->cohort_num);
 697         }
 698
 699         /* We must always rescan the parents of .WAIT and .ORDER nodes. */
 700         if (pgn->unmade != 0 && !(centurion->type & OP_WAIT)
 701                 && !(centurion->flags & DONE_ORDER)) {
 702             DEBUG0(MAKE, "- unmade children\n");
 703             continue;
 704         }
 705         if (pgn->made != DEFERRED) {
 706             /*
 707              * Either this parent is on a different branch of the tree,
 708              * or it on the RHS of a .WAIT directive
 709              * or it is already on the toBeMade list.
 710              */
 711             DEBUG0(MAKE, "- not deferred\n");
 712             continue;
 713         }
 714
 715         if (IsWaitingForOrder(pgn))
 716             continue;
 717
 718         if (DEBUG(MAKE)) {
 719             debug_printf("- %s%s made, schedule %s%s (made %d)\n",
 720                          cgn->name, cgn->cohort_num,
 721                          pgn->name, pgn->cohort_num, pgn->made);
 722             Targ_PrintNode(pgn, 2);
 723         }
 724         /* Ok, we can schedule the parent again */
 725         pgn->made = REQUESTED;
 726         Lst_Enqueue(toBeMade, pgn);
 727     }
 728
 729     UpdateImplicitParentsVars(cgn, cname);
 730 }
 731
 732 static void
 733 UnmarkChildren(GNode *gn)
 734 {
 735     GNodeListNode *ln;
 736
 737     for (ln = gn->children->first; ln != NULL; ln = ln->next) {
 738         GNode *child = ln->datum;
 739         child->type &= ~OP_MARK;
 740     }
 741 }
 742
 743 /* Add a child's name to the ALLSRC and OODATE variables of the given
 744  * node, but only if it has not been given the .EXEC, .USE or .INVISIBLE
 745  * attributes. .EXEC and .USE children are very rarely going to be files,
 746  * so...
 747  *
 748  * If the child is a .JOIN node, its ALLSRC is propagated to the parent.
 749  *
 750  * A child is added to the OODATE variable if its modification time is
 751  * later than that of its parent, as defined by Make, except if the
 752  * parent is a .JOIN node. In that case, it is only added to the OODATE
 753  * variable if it was actually made (since .JOIN nodes don't have
 754  * modification times, the comparison is rather unfair...)..
 755  *
 756  * Input:
 757  *      cgn             The child to add
 758  *      pgn             The parent to whose ALLSRC variable it should
 759  *                      be added
 760  */
 761 static void
 762 MakeAddAllSrc(GNode *cgn, GNode *pgn)
 763 {
 764     if (cgn->type & OP_MARK)
 765         return;
 766     cgn->type |= OP_MARK;
 767
 768     if (!(cgn->type & (OP_EXEC|OP_USE|OP_USEBEFORE|OP_INVISIBLE))) {
 769         const char *child, *allsrc;
 770
 771         if (cgn->type & OP_ARCHV)
 772             child = GNode_VarMember(cgn);
 773         else
 774             child = GNode_Path(cgn);
 775         if (cgn->type & OP_JOIN) {
 776             allsrc = GNode_VarAllsrc(cgn);
 777         } else {
 778             allsrc = child;
 779         }
 780         if (allsrc != NULL)
 781                 Var_Append(ALLSRC, allsrc, pgn);
 782         if (pgn->type & OP_JOIN) {
 783             if (cgn->made == MADE) {
 784                 Var_Append(OODATE, child, pgn);
 785             }
 786         } else if ((pgn->mtime < cgn->mtime) ||
 787                    (cgn->mtime >= now && cgn->made == MADE))
 788         {
 789             /*
 790              * It goes in the OODATE variable if the parent is younger than the
 791              * child or if the child has been modified more recently than
 792              * the start of the make. This is to keep pmake from getting
 793              * confused if something else updates the parent after the
 794              * make starts (shouldn't happen, I know, but sometimes it
 795              * does). In such a case, if we've updated the child, the parent
 796              * is likely to have a modification time later than that of
 797              * the child and anything that relies on the OODATE variable will
 798              * be hosed.
 799              *
 800              * XXX: This will cause all made children to go in the OODATE
 801              * variable, even if they're not touched, if RECHECK isn't defined,
 802              * since cgn->mtime is set to now in Make_Update. According to
 803              * some people, this is good...
 804              */
 805             Var_Append(OODATE, child, pgn);
 806         }
 807     }
 808 }
 809
 810 /* Set up the ALLSRC and OODATE variables. Sad to say, it must be
 811  * done separately, rather than while traversing the graph. This is
 812  * because Make defined OODATE to contain all sources whose modification
 813  * times were later than that of the target, *not* those sources that
 814  * were out-of-date. Since in both compatibility and native modes,
 815  * the modification time of the parent isn't found until the child
 816  * has been dealt with, we have to wait until now to fill in the
 817  * variable. As for ALLSRC, the ordering is important and not
 818  * guaranteed when in native mode, so it must be set here, too.
 819  *
 820  * If the node is a .JOIN node, its TARGET variable will be set to
 821  * match its ALLSRC variable.
 822  */
 823 void
 824 Make_DoAllVar(GNode *gn)
 825 {
 826     GNodeListNode *ln;
 827
 828     if (gn->flags & DONE_ALLSRC)
 829         return;
 830
 831     UnmarkChildren(gn);
 832     for (ln = gn->children->first; ln != NULL; ln = ln->next)
 833         MakeAddAllSrc(ln->datum, gn);
 834
 835     if (!Var_Exists(OODATE, gn))
 836         Var_Set(OODATE, "", gn);
 837     if (!Var_Exists(ALLSRC, gn))
 838         Var_Set(ALLSRC, "", gn);
 839
 840     if (gn->type & OP_JOIN)
 841         Var_Set(TARGET, GNode_VarAllsrc(gn), gn);
 842     gn->flags |= DONE_ALLSRC;
 843 }
 844
 845 static int
 846 MakeBuildChild(void *v_cn, void *toBeMade_next)
 847 {
 848     GNode *cn = v_cn;
 849
 850     if (DEBUG(MAKE)) {
 851         debug_printf("MakeBuildChild: inspect %s%s, ",
 852                cn->name, cn->cohort_num);
 853         GNode_FprintDetails(opts.debug_file, "", cn, "\n");
 854     }
 855     if (cn->made > DEFERRED)
 856         return 0;
 857
 858     /* If this node is on the RHS of a .ORDER, check LHSs. */
 859     if (IsWaitingForOrder(cn)) {
 860         /* Can't build this (or anything else in this child list) yet */
 861         cn->made = DEFERRED;
 862         return 0;                       /* but keep looking */
 863     }
 864
 865     DEBUG2(MAKE, "MakeBuildChild: schedule %s%s\n", cn->name, cn->cohort_num);
 866
 867     cn->made = REQUESTED;
 868     if (toBeMade_next == NULL)
 869         Lst_Append(toBeMade, cn);
 870     else
 871         Lst_InsertBefore(toBeMade, toBeMade_next, cn);
 872
 873     if (cn->unmade_cohorts != 0)
 874         Lst_ForEachUntil(cn->cohorts, MakeBuildChild, toBeMade_next);
 875
 876     /*
 877      * If this node is a .WAIT node with unmade children
 878      * then don't add the next sibling.
 879      */
 880     return cn->type & OP_WAIT && cn->unmade > 0;
 881 }
 882
 883 /* When a .ORDER LHS node completes, we do this on each RHS. */
 884 static int
 885 MakeBuildParent(void *v_pn, void *toBeMade_next)
 886 {
 887     GNode *pn = v_pn;
 888
 889     if (pn->made != DEFERRED)
 890         return 0;
 891
 892     if (MakeBuildChild(pn, toBeMade_next) == 0) {
 893         /* Mark so that when this node is built we reschedule its parents */
 894         pn->flags |= DONE_ORDER;
 895     }
 896
 897     return 0;
 898 }
 899
 900 /* Start as many jobs as possible, taking them from the toBeMade queue.
 901  *
 902  * If the -q option was given, no job will be started,
 903  * but as soon as an out-of-date target is found, this function
 904  * returns TRUE. In all other cases, this function returns FALSE.
 905  */
 906 static Boolean
 907 MakeStartJobs(void)
 908 {
 909     GNode *gn;
 910     Boolean have_token = FALSE;
 911
 912     while (!Lst_IsEmpty(toBeMade)) {
 913         /* Get token now to avoid cycling job-list when we only have 1 token */
 914         if (!have_token && !Job_TokenWithdraw())
 915             break;
 916         have_token = TRUE;
 917
 918         gn = Lst_Dequeue(toBeMade);
 919         DEBUG2(MAKE, "Examining %s%s...\n", gn->name, gn->cohort_num);
 920
 921         if (gn->made != REQUESTED) {
 922             DEBUG1(MAKE, "state %d\n", gn->made);
 923
 924             make_abort(gn, __LINE__);
 925         }
 926
 927         if (gn->checked_seqno == checked_seqno) {
 928             /* We've already looked at this node since a job finished... */
 929             DEBUG2(MAKE, "already checked %s%s\n", gn->name, gn->cohort_num);
 930             gn->made = DEFERRED;
 931             continue;
 932         }
 933         gn->checked_seqno = checked_seqno;
 934
 935         if (gn->unmade != 0) {
 936             /*
 937              * We can't build this yet, add all unmade children to toBeMade,
 938              * just before the current first element.
 939              */
 940             gn->made = DEFERRED;
 941             Lst_ForEachUntil(gn->children, MakeBuildChild, toBeMade->first);
 942             /* and drop this node on the floor */
 943             DEBUG2(MAKE, "dropped %s%s\n", gn->name, gn->cohort_num);
 944             continue;
 945         }
 946
 947         gn->made = BEINGMADE;
 948         if (GNode_IsOODate(gn)) {
 949             DEBUG0(MAKE, "out-of-date\n");
 950             if (opts.queryFlag)
 951                 return TRUE;
 952             Make_DoAllVar(gn);
 953             Job_Make(gn);
 954             have_token = FALSE;
 955         } else {
 956             DEBUG0(MAKE, "up-to-date\n");
 957             gn->made = UPTODATE;
 958             if (gn->type & OP_JOIN) {
 959                 /*
 960                  * Even for an up-to-date .JOIN node, we need it to have its
 961                  * context variables so references to it get the correct
 962                  * value for .TARGET when building up the context variables
 963                  * of its parent(s)...
 964                  */
 965                 Make_DoAllVar(gn);
 966             }
 967             Make_Update(gn);
 968         }
 969     }
 970
 971     if (have_token)
 972         Job_TokenReturn();
 973
 974     return FALSE;
 975 }
 976
 977 /* Print the status of a .ORDER node. */
 978 static void
 979 MakePrintStatusOrderNode(GNode *ogn, GNode *gn)
 980 {
 981     if (!(ogn->flags & REMAKE) || ogn->made > REQUESTED)
 982         /* not waiting for this one */
 983         return;
 984
 985     printf("    `%s%s' has .ORDER dependency against %s%s ",
 986            gn->name, gn->cohort_num, ogn->name, ogn->cohort_num);
 987     GNode_FprintDetails(stdout, "(", ogn, ")\n");
 988
 989     if (DEBUG(MAKE) && opts.debug_file != stdout) {
 990         debug_printf("    `%s%s' has .ORDER dependency against %s%s ",
 991                      gn->name, gn->cohort_num, ogn->name, ogn->cohort_num);
 992         GNode_FprintDetails(opts.debug_file, "(", ogn, ")\n");
 993     }
 994 }
 995
 996 static void
 997 MakePrintStatusOrder(GNode *gn)
 998 {
 999     GNodeListNode *ln;
1000     for (ln = gn->order_pred->first; ln != NULL; ln = ln->next)
1001         MakePrintStatusOrderNode(ln->datum, gn);
1002 }
1003
1004 static void MakePrintStatusList(GNodeList *, int *);
1005
1006 /* Print the status of a top-level node, viz. it being up-to-date already
1007  * or not created due to an error in a lower level.
1008  * Callback function for Make_Run via Lst_ForEachUntil.
1009  */
1010 static Boolean
1011 MakePrintStatus(GNode *gn, int *errors)
1012 {
1013     if (gn->flags & DONECYCLE)
1014         /* We've completely processed this node before, don't do it again. */
1015         return FALSE;
1016
1017     if (gn->unmade == 0) {
1018         gn->flags |= DONECYCLE;
1019         switch (gn->made) {
1020         case UPTODATE:
1021             printf("`%s%s' is up to date.\n", gn->name, gn->cohort_num);
1022             break;
1023         case MADE:
1024             break;
1025         case UNMADE:
1026         case DEFERRED:
1027         case REQUESTED:
1028         case BEINGMADE:
1029             (*errors)++;
1030             printf("`%s%s' was not built", gn->name, gn->cohort_num);
1031             GNode_FprintDetails(stdout, " (", gn, ")!\n");
1032             if (DEBUG(MAKE) && opts.debug_file != stdout) {
1033                 debug_printf("`%s%s' was not built", gn->name, gn->cohort_num);
1034                 GNode_FprintDetails(opts.debug_file, " (", gn, ")!\n");
1035             }
1036             /* Most likely problem is actually caused by .ORDER */
1037             MakePrintStatusOrder(gn);
1038             break;
1039         default:
1040             /* Errors - already counted */
1041             printf("`%s%s' not remade because of errors.\n",
1042                     gn->name, gn->cohort_num);
1043             if (DEBUG(MAKE) && opts.debug_file != stdout)
1044                 debug_printf("`%s%s' not remade because of errors.\n",
1045                              gn->name, gn->cohort_num);
1046             break;
1047         }
1048         return FALSE;
1049     }
1050
1051     DEBUG3(MAKE, "MakePrintStatus: %s%s has %d unmade children\n",
1052            gn->name, gn->cohort_num, gn->unmade);
1053     /*
1054      * If printing cycles and came to one that has unmade children,
1055      * print out the cycle by recursing on its children.
1056      */
1057     if (!(gn->flags & CYCLE)) {
1058         /* First time we've seen this node, check all children */
1059         gn->flags |= CYCLE;
1060         MakePrintStatusList(gn->children, errors);
1061         /* Mark that this node needn't be processed again */
1062         gn->flags |= DONECYCLE;
1063         return FALSE;
1064     }
1065
1066     /* Only output the error once per node */
1067     gn->flags |= DONECYCLE;
1068     Error("Graph cycles through `%s%s'", gn->name, gn->cohort_num);
1069     if ((*errors)++ > 100)
1070         /* Abandon the whole error report */
1071         return TRUE;
1072
1073     /* Reporting for our children will give the rest of the loop */
1074     MakePrintStatusList(gn->children, errors);
1075     return FALSE;
1076 }
1077
1078 static void
1079 MakePrintStatusList(GNodeList *gnodes, int *errors)
1080 {
1081     GNodeListNode *ln;
1082     for (ln = gnodes->first; ln != NULL; ln = ln->next)
1083         if (MakePrintStatus(ln->datum, errors))
1084             break;
1085 }
1086
1087 static void
1088 ExamineLater(GNodeList *examine, GNodeList *toBeExamined)
1089 {
1090     ListNode *ln;
1091
1092     for (ln = toBeExamined->first; ln != NULL; ln = ln->next) {
1093         GNode *gn = ln->datum;
1094
1095         if (gn->flags & REMAKE)
1096             continue;
1097         if (gn->type & (OP_USE | OP_USEBEFORE))
1098             continue;
1099
1100         DEBUG2(MAKE, "ExamineLater: need to examine \"%s%s\"\n",
1101                gn->name, gn->cohort_num);
1102         Lst_Enqueue(examine, gn);
1103     }
1104 }
1105
1106 /* Expand .USE nodes and create a new targets list.
1107  *
1108  * Input:
1109  *      targs           the initial list of targets
1110  */
1111 void
1112 Make_ExpandUse(GNodeList *targs)
1113 {
1114     GNodeList *examine = Lst_New();     /* Queue of targets to examine */
1115     Lst_AppendAll(examine, targs);
1116
1117     /*
1118      * Make an initial downward pass over the graph, marking nodes to be made
1119      * as we go down. We call Suff_FindDeps to find where a node is and
1120      * to get some children for it if it has none and also has no commands.
1121      * If the node is a leaf, we stick it on the toBeMade queue to
1122      * be looked at in a minute, otherwise we add its children to our queue
1123      * and go on about our business.
1124      */
1125     while (!Lst_IsEmpty(examine)) {
1126         GNode *gn = Lst_Dequeue(examine);
1127
1128         if (gn->flags & REMAKE)
1129             /* We've looked at this one already */
1130             continue;
1131         gn->flags |= REMAKE;
1132         DEBUG2(MAKE, "Make_ExpandUse: examine %s%s\n",
1133                gn->name, gn->cohort_num);
1134
1135         if (gn->type & OP_DOUBLEDEP)
1136             Lst_PrependAll(examine, gn->cohorts);
1137
1138         /*
1139          * Apply any .USE rules before looking for implicit dependencies
1140          * to make sure everything has commands that should...
1141          * Make sure that the TARGET is set, so that we can make
1142          * expansions.
1143          */
1144         if (gn->type & OP_ARCHV) {
1145             char *eoa = strchr(gn->name, '(');
1146             char *eon = strchr(gn->name, ')');
1147             if (eoa == NULL || eon == NULL)
1148                 continue;
1149             *eoa = '\0';
1150             *eon = '\0';
1151             Var_Set(MEMBER, eoa + 1, gn);
1152             Var_Set(ARCHIVE, gn->name, gn);
1153             *eoa = '(';
1154             *eon = ')';
1155         }
1156
1157         Dir_UpdateMTime(gn, FALSE);
1158         Var_Set(TARGET, GNode_Path(gn), gn);
1159         UnmarkChildren(gn);
1160         HandleUseNodes(gn);
1161
1162         if (!(gn->type & OP_MADE))
1163             Suff_FindDeps(gn);
1164         else {
1165             PretendAllChildrenAreMade(gn);
1166             if (gn->unmade != 0)
1167                 printf("Warning: %s%s still has %d unmade children\n",
1168                        gn->name, gn->cohort_num, gn->unmade);
1169         }
1170
1171         if (gn->unmade != 0)
1172             ExamineLater(examine, gn->children);
1173     }
1174
1175     Lst_Free(examine);
1176 }
1177
1178 /* Make the .WAIT node depend on the previous children */
1179 static void
1180 add_wait_dependency(GNodeListNode *owln, GNode *wn)
1181 {
1182     GNodeListNode *cln;
1183     GNode *cn;
1184
1185     for (cln = owln; (cn = cln->datum) != wn; cln = cln->next) {
1186         DEBUG3(MAKE, ".WAIT: add dependency %s%s -> %s\n",
1187                cn->name, cn->cohort_num, wn->name);
1188
1189         /* XXX: This pattern should be factored out, it repeats often */
1190         Lst_Append(wn->children, cn);
1191         wn->unmade++;
1192         Lst_Append(cn->parents, wn);
1193     }
1194 }
1195
1196 /* Convert .WAIT nodes into dependencies. */
1197 static void
1198 Make_ProcessWait(GNodeList *targs)
1199 {
1200     GNode  *pgn;                /* 'parent' node we are examining */
1201     GNodeListNode *owln;        /* Previous .WAIT node */
1202     GNodeList *examine;         /* List of targets to examine */
1203
1204     /*
1205      * We need all the nodes to have a common parent in order for the
1206      * .WAIT and .ORDER scheduling to work.
1207      * Perhaps this should be done earlier...
1208      */
1209
1210     pgn = GNode_New(".MAIN");
1211     pgn->flags = REMAKE;
1212     pgn->type = OP_PHONY | OP_DEPENDS;
1213     /* Get it displayed in the diag dumps */
1214     Lst_Prepend(Targ_List(), pgn);
1215
1216     {
1217         GNodeListNode *ln;
1218         for (ln = targs->first; ln != NULL; ln = ln->next) {
1219             GNode *cgn = ln->datum;
1220
1221             Lst_Append(pgn->children, cgn);
1222             Lst_Append(cgn->parents, pgn);
1223             pgn->unmade++;
1224         }
1225     }
1226
1227     /* Start building with the 'dummy' .MAIN' node */
1228     MakeBuildChild(pgn, NULL);
1229
1230     examine = Lst_New();
1231     Lst_Append(examine, pgn);
1232
1233     while (!Lst_IsEmpty(examine)) {
1234         GNodeListNode *ln;
1235
1236         pgn = Lst_Dequeue(examine);
1237
1238         /* We only want to process each child-list once */
1239         if (pgn->flags & DONE_WAIT)
1240             continue;
1241         pgn->flags |= DONE_WAIT;
1242         DEBUG1(MAKE, "Make_ProcessWait: examine %s\n", pgn->name);
1243
1244         if (pgn->type & OP_DOUBLEDEP)
1245             Lst_PrependAll(examine, pgn->cohorts);
1246
1247         owln = pgn->children->first;
1248         for (ln = pgn->children->first; ln != NULL; ln = ln->next) {
1249             GNode *cgn = ln->datum;
1250             if (cgn->type & OP_WAIT) {
1251                 add_wait_dependency(owln, cgn);
1252                 owln = ln;
1253             } else {
1254                 Lst_Append(examine, cgn);
1255             }
1256         }
1257     }
1258
1259     Lst_Free(examine);
1260 }
1261
1262 /*-
1263  *-----------------------------------------------------------------------
1264  * Make_Run --
1265  *      Initialize the nodes to remake and the list of nodes which are
1266  *      ready to be made by doing a breadth-first traversal of the graph
1267  *      starting from the nodes in the given list. Once this traversal
1268  *      is finished, all the 'leaves' of the graph are in the toBeMade
1269  *      queue.
1270  *      Using this queue and the Job module, work back up the graph,
1271  *      calling on MakeStartJobs to keep the job table as full as
1272  *      possible.
1273  *
1274  * Input:
1275  *      targs           the initial list of targets
1276  *
1277  * Results:
1278  *      TRUE if work was done. FALSE otherwise.
1279  *
1280  * Side Effects:
1281  *      The make field of all nodes involved in the creation of the given
1282  *      targets is set to 1. The toBeMade list is set to contain all the
1283  *      'leaves' of these subgraphs.
1284  *-----------------------------------------------------------------------
1285  */
1286 Boolean
1287 Make_Run(GNodeList *targs)
1288 {
1289     int errors;                 /* Number of errors the Job module reports */
1290
1291     /* Start trying to make the current targets... */
1292     toBeMade = Lst_New();
1293
1294     Make_ExpandUse(targs);
1295     Make_ProcessWait(targs);
1296
1297     if (DEBUG(MAKE)) {
1298          debug_printf("#***# full graph\n");
1299          Targ_PrintGraph(1);
1300     }
1301
1302     if (opts.queryFlag) {
1303         /*
1304          * We wouldn't do any work unless we could start some jobs in the
1305          * next loop... (we won't actually start any, of course, this is just
1306          * to see if any of the targets was out of date)
1307          */
1308         return MakeStartJobs();
1309     }
1310     /*
1311      * Initialization. At the moment, no jobs are running and until some
1312      * get started, nothing will happen since the remaining upward
1313      * traversal of the graph is performed by the routines in job.c upon
1314      * the finishing of a job. So we fill the Job table as much as we can
1315      * before going into our loop.
1316      */
1317     (void)MakeStartJobs();
1318
1319     /*
1320      * Main Loop: The idea here is that the ending of jobs will take
1321      * care of the maintenance of data structures and the waiting for output
1322      * will cause us to be idle most of the time while our children run as
1323      * much as possible. Because the job table is kept as full as possible,
1324      * the only time when it will be empty is when all the jobs which need
1325      * running have been run, so that is the end condition of this loop.
1326      * Note that the Job module will exit if there were any errors unless the
1327      * keepgoing flag was given.
1328      */
1329     while (!Lst_IsEmpty(toBeMade) || jobTokensRunning > 0) {
1330         Job_CatchOutput();
1331         (void)MakeStartJobs();
1332     }
1333
1334     errors = Job_Finish();
1335
1336     /*
1337      * Print the final status of each target. E.g. if it wasn't made
1338      * because some inferior reported an error.
1339      */
1340     DEBUG1(MAKE, "done: errors %d\n", errors);
1341     if (errors == 0) {
1342         MakePrintStatusList(targs, &errors);
1343         if (DEBUG(MAKE)) {
1344             debug_printf("done: errors %d\n", errors);
1345             if (errors > 0)
1346                 Targ_PrintGraph(4);
1347         }
1348     }
1349     return errors > 0;
1350 }