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