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