xref: /freebsd/contrib/bmake/make.c (revision ec0ea6efa1ad229d75c394c1a9b9cac33af2b1d3)
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 }
1489