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