contrib/bmake/make.c

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