contrib/bmake/make.c

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