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