- Cleanup white space. style(9)
[dragonfly.git] / usr.bin / make / make.c
1 /*
2  * Copyright (c) 1988, 1989, 1990, 1993
3  *      The Regents of the University of California.  All rights reserved.
4  * Copyright (c) 1989 by Berkeley Softworks
5  * 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. All advertising materials mentioning features or use of this software
19  *    must display the following acknowledgement:
20  *      This product includes software developed by the University of
21  *      California, Berkeley and its contributors.
22  * 4. Neither the name of the University nor the names of its contributors
23  *    may be used to endorse or promote products derived from this software
24  *    without specific prior written permission.
25  *
26  * THIS SOFTWARE IS PROVIDED BY THE REGENTS AND CONTRIBUTORS ``AS IS'' AND
27  * ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
28  * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE
29  * ARE DISCLAIMED.  IN NO EVENT SHALL THE REGENTS OR CONTRIBUTORS BE LIABLE
30  * FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL
31  * DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS
32  * OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION)
33  * HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT
34  * LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY
35  * OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF
36  * SUCH DAMAGE.
37  *
38  * @(#)make.c   8.1 (Berkeley) 6/6/93
39  * $FreeBSD: src/usr.bin/make/make.c,v 1.11 1999/09/11 13:08:01 hoek Exp $
40  * $DragonFly: src/usr.bin/make/make.c,v 1.19 2005/01/09 23:03:28 okumoto Exp $
41  */
42
43 /*-
44  * make.c --
45  *      The functions which perform the examination of targets and
46  *      their suitability for creation
47  *
48  * Interface:
49  *      Make_Run                Initialize things for the module and recreate
50  *                              whatever needs recreating. Returns TRUE if
51  *                              work was (or would have been) done and FALSE
52  *                              otherwise.
53  *
54  *      Make_Update             Update all parents of a given child. Performs
55  *                              various bookkeeping chores like the updating
56  *                              of the cmtime field of the parent, filling
57  *                              of the IMPSRC context variable, etc. It will
58  *                              place the parent on the toBeMade queue if it
59  *                              should be.
60  *
61  *      Make_TimeStamp          Function to set the parent's cmtime field
62  *                              based on a child's modification time.
63  *
64  *      Make_DoAllVar           Set up the various local variables for a
65  *                              target, including the .ALLSRC variable, making
66  *                              sure that any variable that needs to exist
67  *                              at the very least has the empty value.
68  *
69  *      Make_OODate             Determine if a target is out-of-date.
70  *
71  *      Make_HandleUse          See if a child is a .USE node for a parent
72  *                              and perform the .USE actions if so.
73  */
74
75 #include <stdlib.h>
76
77 #include "arch.h"
78 #include "config.h"
79 #include "dir.h"
80 #include "globals.h"
81 #include "GNode.h"
82 #include "job.h"
83 #include "make.h"
84 #include "suff.h"
85 #include "targ.h"
86 #include "util.h"
87 #include "var.h"
88
89 /* The current fringe of the graph. These are nodes which await examination
90  * by MakeOODate. It is added to by Make_Update and subtracted from by
91  * MakeStartJobs */
92 static Lst toBeMade = Lst_Initializer(toBeMade);
93
94 static int      numNodes;       /* Number of nodes to be processed. If this
95                                  * is non-zero when Job_Empty() returns
96                                  * TRUE, there's a cycle in the graph */
97
98 static int MakeAddChild(void *, void *);
99 static int MakeAddAllSrc(void *, void *);
100 static int MakeTimeStamp(void *, void *);
101 static int MakeHandleUse(void *, void *);
102 static Boolean MakeStartJobs(void);
103 static int MakePrintStatus(void *, void *);
104
105 /*-
106  *-----------------------------------------------------------------------
107  * Make_TimeStamp --
108  *      Set the cmtime field of a parent node based on the mtime stamp in its
109  *      child. Called from MakeOODate via Lst_ForEach.
110  *
111  * Results:
112  *      Always returns 0.
113  *
114  * Side Effects:
115  *      The cmtime of the parent node will be changed if the mtime
116  *      field of the child is greater than it.
117  *-----------------------------------------------------------------------
118  */
119 int
120 Make_TimeStamp(GNode *pgn, GNode *cgn)
121 {
122
123     if (cgn->mtime > pgn->cmtime) {
124         pgn->cmtime = cgn->mtime;
125     }
126     return (0);
127 }
128
129 static int
130 MakeTimeStamp(void *pgn, void *cgn)
131 {
132
133     return (Make_TimeStamp(pgn, cgn));
134 }
135
136 /*-
137  *-----------------------------------------------------------------------
138  * Make_OODate --
139  *      See if a given node is out of date with respect to its sources.
140  *      Used by Make_Run when deciding which nodes to place on the
141  *      toBeMade queue initially and by Make_Update to screen out USE and
142  *      EXEC nodes. In the latter case, however, any other sort of node
143  *      must be considered out-of-date since at least one of its children
144  *      will have been recreated.
145  *
146  * Results:
147  *      TRUE if the node is out of date. FALSE otherwise.
148  *
149  * Side Effects:
150  *      The mtime field of the node and the cmtime field of its parents
151  *      will/may be changed.
152  *-----------------------------------------------------------------------
153  */
154 Boolean
155 Make_OODate(GNode *gn)
156 {
157     Boolean         oodate;
158
159     /*
160      * Certain types of targets needn't even be sought as their datedness
161      * doesn't depend on their modification time...
162      */
163     if ((gn->type & (OP_JOIN | OP_USE | OP_EXEC)) == 0) {
164         Dir_MTime(gn);
165         if (gn->mtime != 0) {
166             DEBUGF(MAKE, ("modified %s...", Targ_FmtTime(gn->mtime)));
167         } else {
168             DEBUGF(MAKE, ("non-existent..."));
169         }
170     }
171
172     /*
173      * A target is remade in one of the following circumstances:
174      *  its modification time is smaller than that of its youngest child
175      *      and it would actually be run (has commands or type OP_NOP)
176      *  it's the object of a force operator
177      *  it has no children, was on the lhs of an operator and doesn't exist
178      *      already.
179      *
180      * Libraries are only considered out-of-date if the archive module says
181      * they are.
182      *
183      * These weird rules are brought to you by Backward-Compatability and
184      * the strange people who wrote 'Make'.
185      */
186     if (gn->type & OP_USE) {
187         /*
188          * If the node is a USE node it is *never* out of date
189          * no matter *what*.
190          */
191         DEBUGF(MAKE, (".USE node..."));
192         oodate = FALSE;
193     } else if (gn->type & OP_LIB) {
194         DEBUGF(MAKE, ("library..."));
195
196         /*
197          * always out of date if no children and :: target
198          */
199
200         oodate = Arch_LibOODate(gn) ||
201             ((gn->cmtime == 0) && (gn->type & OP_DOUBLEDEP));
202     } else if (gn->type & OP_JOIN) {
203         /*
204          * A target with the .JOIN attribute is only considered
205          * out-of-date if any of its children was out-of-date.
206          */
207         DEBUGF(MAKE, (".JOIN node..."));
208         oodate = gn->childMade;
209     } else if (gn->type & (OP_FORCE|OP_EXEC|OP_PHONY)) {
210         /*
211          * A node which is the object of the force (!) operator or which has
212          * the .EXEC attribute is always considered out-of-date.
213          */
214         if (gn->type & OP_FORCE) {
215             DEBUGF(MAKE, ("! operator..."));
216         } else if (gn->type & OP_PHONY) {
217             DEBUGF(MAKE, (".PHONY node..."));
218         } else {
219             DEBUGF(MAKE, (".EXEC node..."));
220         }
221         oodate = TRUE;
222     } else if ((gn->mtime < gn->cmtime) ||
223                ((gn->cmtime == 0) &&
224                 ((gn->mtime==0) || (gn->type & OP_DOUBLEDEP))))
225     {
226         /*
227          * A node whose modification time is less than that of its
228          * youngest child or that has no children (cmtime == 0) and
229          * either doesn't exist (mtime == 0) or was the object of a
230          * :: operator is out-of-date. Why? Because that's the way Make does
231          * it.
232          */
233         if (gn->mtime < gn->cmtime) {
234             DEBUGF(MAKE, ("modified before source..."));
235         } else if (gn->mtime == 0) {
236             DEBUGF(MAKE, ("non-existent and no sources..."));
237         } else {
238             DEBUGF(MAKE, (":: operator and no sources..."));
239         }
240         oodate = TRUE;
241     } else
242         oodate = FALSE;
243
244     /*
245      * If the target isn't out-of-date, the parents need to know its
246      * modification time. Note that targets that appear to be out-of-date
247      * but aren't, because they have no commands and aren't of type OP_NOP,
248      * have their mtime stay below their children's mtime to keep parents from
249      * thinking they're out-of-date.
250      */
251     if (!oodate) {
252         Lst_ForEach(&gn->parents, MakeTimeStamp, gn);
253     }
254
255     return (oodate);
256 }
257
258 /*-
259  *-----------------------------------------------------------------------
260  * MakeAddChild  --
261  *      Function used by Make_Run to add a child to the list l.
262  *      It will only add the child if its make field is FALSE.
263  *
264  * Results:
265  *      Always returns 0
266  *
267  * Side Effects:
268  *      The given list is extended
269  *-----------------------------------------------------------------------
270  */
271 static int
272 MakeAddChild(void *gnp, void *lp)
273 {
274     GNode *gn = gnp;
275     Lst *l = lp;
276
277     if (!gn->make && !(gn->type & OP_USE)) {
278         Lst_EnQueue(l, gn);
279     }
280     return (0);
281 }
282
283 /*-
284  *-----------------------------------------------------------------------
285  * Make_HandleUse --
286  *      Function called by Make_Run and SuffApplyTransform on the downward
287  *      pass to handle .USE and transformation nodes. A callback function
288  *      for Lst_ForEach, it implements the .USE and transformation
289  *      functionality by copying the node's commands, type flags
290  *      and children to the parent node. Should be called before the
291  *      children are enqueued to be looked at by MakeAddChild.
292  *
293  *      A .USE node is much like an explicit transformation rule, except
294  *      its commands are always added to the target node, even if the
295  *      target already has commands.
296  *
297  * Results:
298  *      returns 0.
299  *
300  * Side Effects:
301  *      Children and commands may be added to the parent and the parent's
302  *      type may be changed.
303  *
304  *-----------------------------------------------------------------------
305  */
306 int
307 Make_HandleUse(GNode *cgn, GNode *pgn)
308 {
309     GNode       *gn;            /* A child of the .USE node */
310     LstNode     *ln;            /* An element in the children list */
311
312     if (cgn->type & (OP_USE | OP_TRANSFORM)) {
313         if ((cgn->type & OP_USE) || Lst_IsEmpty(&pgn->commands)) {
314             /*
315              * .USE or transformation and target has no commands -- append
316              * the child's commands to the parent.
317              */
318              Lst_Concat(&pgn->commands, &cgn->commands, LST_CONCNEW);
319         }
320
321         for (ln = Lst_First(&cgn->children); ln != NULL; ln = Lst_Succ(ln)) {
322             gn = Lst_Datum(ln);
323
324             if (Lst_Member(&pgn->children, gn) == NULL) {
325                 Lst_AtEnd(&pgn->children, gn);
326                 Lst_AtEnd(&gn->parents, pgn);
327                 pgn->unmade += 1;
328             }
329         }
330
331         pgn->type |= cgn->type & ~(OP_OPMASK | OP_USE | OP_TRANSFORM);
332
333         /*
334          * This child node is now "made", so we decrement the count of
335          * unmade children in the parent... We also remove the child
336          * from the parent's list to accurately reflect the number of decent
337          * children the parent has. This is used by Make_Run to decide
338          * whether to queue the parent or examine its children...
339          */
340         if (cgn->type & OP_USE) {
341             pgn->unmade--;
342         }
343     }
344     return (0);
345 }
346
347 static int
348 MakeHandleUse(void *pgn, void *cgn)
349 {
350
351     return (Make_HandleUse(pgn, cgn));
352 }
353
354 /*-
355  *-----------------------------------------------------------------------
356  * Make_Update  --
357  *      Perform update on the parents of a node. Used by JobFinish once
358  *      a node has been dealt with and by MakeStartJobs if it finds an
359  *      up-to-date node.
360  *
361  * Results:
362  *      Always returns 0
363  *
364  * Side Effects:
365  *      The unmade field of pgn is decremented and pgn may be placed on
366  *      the toBeMade queue if this field becomes 0.
367  *
368  *      If the child was made, the parent's childMade field will be set true
369  *      and its cmtime set to now.
370  *
371  *      If the child wasn't made, the cmtime field of the parent will be
372  *      altered if the child's mtime is big enough.
373  *
374  *      Finally, if the child is the implied source for the parent, the
375  *      parent's IMPSRC variable is set appropriately.
376  *
377  *-----------------------------------------------------------------------
378  */
379 void
380 Make_Update(GNode *cgn)
381 {
382     GNode       *pgn;           /* the parent node */
383     char        *cname;         /* the child's name */
384     LstNode     *ln;            /* Element in parents and iParents lists */
385     char        *p1;
386     char        *ptr;
387     char        *cpref;
388
389     cname = Var_Value(TARGET, cgn, &p1);
390     free(p1);
391
392     /*
393      * If the child was actually made, see what its modification time is
394      * now -- some rules won't actually update the file. If the file still
395      * doesn't exist, make its mtime now.
396      */
397     if (cgn->made != UPTODATE) {
398 #ifndef RECHECK
399         /*
400          * We can't re-stat the thing, but we can at least take care of rules
401          * where a target depends on a source that actually creates the
402          * target, but only if it has changed, e.g.
403          *
404          * parse.h : parse.o
405          *
406          * parse.o : parse.y
407          *      yacc -d parse.y
408          *      cc -c y.tab.c
409          *      mv y.tab.o parse.o
410          *      cmp -s y.tab.h parse.h || mv y.tab.h parse.h
411          *
412          * In this case, if the definitions produced by yacc haven't changed
413          * from before, parse.h won't have been updated and cgn->mtime will
414          * reflect the current modification time for parse.h. This is
415          * something of a kludge, I admit, but it's a useful one..
416          * XXX: People like to use a rule like
417          *
418          * FRC:
419          *
420          * To force things that depend on FRC to be made, so we have to
421          * check for gn->children being empty as well...
422          */
423         if (!Lst_IsEmpty(&cgn->commands) || Lst_IsEmpty(&cgn->children)) {
424             cgn->mtime = now;
425         }
426 #else
427         /*
428          * This is what Make does and it's actually a good thing, as it
429          * allows rules like
430          *
431          *      cmp -s y.tab.h parse.h || cp y.tab.h parse.h
432          *
433          * to function as intended. Unfortunately, thanks to the stateless
434          * nature of NFS (by which I mean the loose coupling of two clients
435          * using the same file from a common server), there are times
436          * when the modification time of a file created on a remote
437          * machine will not be modified before the local stat() implied by
438          * the Dir_MTime occurs, thus leading us to believe that the file
439          * is unchanged, wreaking havoc with files that depend on this one.
440          *
441          * I have decided it is better to make too much than to make too
442          * little, so this stuff is commented out unless you're sure it's ok.
443          * -- ardeb 1/12/88
444          */
445         /*
446          * Christos, 4/9/92: If we are  saving commands pretend that
447          * the target is made now. Otherwise archives with ... rules
448          * don't work!
449          */
450         if (noExecute || (cgn->type & OP_SAVE_CMDS) || Dir_MTime(cgn) == 0) {
451             cgn->mtime = now;
452         }
453         DEBUGF(MAKE, ("update time: %s\n", Targ_FmtTime(cgn->mtime)));
454 #endif
455     }
456
457     for (ln = Lst_First(&cgn->parents); ln != NULL; ln = Lst_Succ(ln)) {
458         pgn = Lst_Datum(ln);
459         if (pgn->make) {
460             pgn->unmade -= 1;
461
462             if (!(cgn->type & (OP_EXEC | OP_USE))) {
463                 if (cgn->made == MADE) {
464                     pgn->childMade = TRUE;
465                     if (pgn->cmtime < cgn->mtime) {
466                         pgn->cmtime = cgn->mtime;
467                     }
468                 } else {
469                     Make_TimeStamp(pgn, cgn);
470                 }
471             }
472             if (pgn->unmade == 0) {
473                 /*
474                  * Queue the node up -- any unmade predecessors will
475                  * be dealt with in MakeStartJobs.
476                  */
477                 Lst_EnQueue(&toBeMade, pgn);
478             } else if (pgn->unmade < 0) {
479                 Error("Graph cycles through %s", pgn->name);
480             }
481         }
482     }
483
484     /*
485      * Deal with successor nodes. If any is marked for making and has an unmade
486      * count of 0, has not been made and isn't in the examination queue,
487      * it means we need to place it in the queue as it restrained itself
488      * before.
489      */
490     for (ln = Lst_First(&cgn->successors); ln != NULL; ln = Lst_Succ(ln)) {
491         GNode   *succ = Lst_Datum(ln);
492
493         if (succ->make && succ->unmade == 0 && succ->made == UNMADE &&
494             Lst_Member(&toBeMade, succ) == NULL)
495         {
496             Lst_EnQueue(&toBeMade, succ);
497         }
498     }
499
500     /*
501      * Set the .PREFIX and .IMPSRC variables for all the implied parents
502      * of this node.
503      */
504     cpref = Var_Value(PREFIX, cgn, &ptr);
505     for (ln = Lst_First(&cgn->iParents); ln != NULL; ln = Lst_Succ(ln)) {
506         pgn = Lst_Datum(ln);
507         if (pgn->make) {
508             Var_Set(IMPSRC, cname, pgn);
509             Var_Set(PREFIX, cpref, pgn);
510         }
511     }
512     free(ptr);
513 }
514
515 /*-
516  *-----------------------------------------------------------------------
517  * MakeAddAllSrc --
518  *      Add a child's name to the ALLSRC and OODATE variables of the given
519  *      node. Called from Make_DoAllVar via Lst_ForEach. A child is added only
520  *      if it has not been given the .EXEC, .USE or .INVISIBLE attributes.
521  *      .EXEC and .USE children are very rarely going to be files, so...
522  *      A child is added to the OODATE variable if its modification time is
523  *      later than that of its parent, as defined by Make, except if the
524  *      parent is a .JOIN node. In that case, it is only added to the OODATE
525  *      variable if it was actually made (since .JOIN nodes don't have
526  *      modification times, the comparison is rather unfair...)..
527  *
528  * Results:
529  *      Always returns 0
530  *
531  * Side Effects:
532  *      The ALLSRC variable for the given node is extended.
533  *-----------------------------------------------------------------------
534  */
535 static int
536 MakeAddAllSrc(void *cgnp, void *pgnp)
537 {
538     GNode       *cgn = (GNode *) cgnp;
539     GNode       *pgn = (GNode *) pgnp;
540
541     if ((cgn->type & (OP_EXEC | OP_USE | OP_INVISIBLE)) == 0) {
542         char *child;
543         char *p1 = NULL;
544
545         if (OP_NOP(cgn->type)) {
546             /*
547              * this node is only source; use the specific pathname for it
548              */
549             child = cgn->path ? cgn->path : cgn->name;
550         }
551         else
552             child = Var_Value(TARGET, cgn, &p1);
553         Var_Append(ALLSRC, child, pgn);
554         if (pgn->type & OP_JOIN) {
555             if (cgn->made == MADE) {
556                 Var_Append(OODATE, child, pgn);
557             }
558         } else if ((pgn->mtime < cgn->mtime) ||
559                    (cgn->mtime >= now && cgn->made == MADE))
560         {
561             /*
562              * It goes in the OODATE variable if the parent is younger than the
563              * child or if the child has been modified more recently than
564              * the start of the make. This is to keep pmake from getting
565              * confused if something else updates the parent after the
566              * make starts (shouldn't happen, I know, but sometimes it
567              * does). In such a case, if we've updated the kid, the parent
568              * is likely to have a modification time later than that of
569              * the kid and anything that relies on the OODATE variable will
570              * be hosed.
571              *
572              * XXX: This will cause all made children to go in the OODATE
573              * variable, even if they're not touched, if RECHECK isn't defined,
574              * since cgn->mtime is set to now in Make_Update. According to
575              * some people, this is good...
576              */
577             Var_Append(OODATE, child, pgn);
578         }
579         free(p1);
580     }
581     return (0);
582 }
583
584 /*-
585  *-----------------------------------------------------------------------
586  * Make_DoAllVar --
587  *      Set up the ALLSRC and OODATE variables. Sad to say, it must be
588  *      done separately, rather than while traversing the graph. This is
589  *      because Make defined OODATE to contain all sources whose modification
590  *      times were later than that of the target, *not* those sources that
591  *      were out-of-date. Since in both compatibility and native modes,
592  *      the modification time of the parent isn't found until the child
593  *      has been dealt with, we have to wait until now to fill in the
594  *      variable. As for ALLSRC, the ordering is important and not
595  *      guaranteed when in native mode, so it must be set here, too.
596  *
597  * Results:
598  *      None
599  *
600  * Side Effects:
601  *      The ALLSRC and OODATE variables of the given node is filled in.
602  *      If the node is a .JOIN node, its TARGET variable will be set to
603  *      match its ALLSRC variable.
604  *-----------------------------------------------------------------------
605  */
606 void
607 Make_DoAllVar(GNode *gn)
608 {
609
610     Lst_ForEach(&gn->children, MakeAddAllSrc, gn);
611
612     if (!Var_Exists (OODATE, gn)) {
613         Var_Set(OODATE, "", gn);
614     }
615     if (!Var_Exists (ALLSRC, gn)) {
616         Var_Set(ALLSRC, "", gn);
617     }
618
619     if (gn->type & OP_JOIN) {
620         char *p1;
621
622         Var_Set(TARGET, Var_Value(ALLSRC, gn, &p1), gn);
623         free(p1);
624     }
625 }
626
627 /*-
628  *-----------------------------------------------------------------------
629  * MakeStartJobs --
630  *      Start as many jobs as possible.
631  *
632  * Results:
633  *      If the query flag was given to pmake, no job will be started,
634  *      but as soon as an out-of-date target is found, this function
635  *      returns TRUE. At all other times, this function returns FALSE.
636  *
637  * Side Effects:
638  *      Nodes are removed from the toBeMade queue and job table slots
639  *      are filled.
640  *
641  *-----------------------------------------------------------------------
642  */
643 static Boolean
644 MakeStartJobs(void)
645 {
646     GNode       *gn;
647
648     while (!Lst_IsEmpty(&toBeMade) && !Job_Full()) {
649         gn = Lst_DeQueue(&toBeMade);
650         DEBUGF(MAKE, ("Examining %s...", gn->name));
651         /*
652          * Make sure any and all predecessors that are going to be made,
653          * have been.
654          */
655         if (!Lst_IsEmpty(&gn->preds)) {
656             LstNode *ln;
657
658             for (ln = Lst_First(&gn->preds); ln != NULL; ln = Lst_Succ(ln)){
659                 GNode   *pgn = Lst_Datum(ln);
660
661                 if (pgn->make && pgn->made == UNMADE) {
662                     DEBUGF(MAKE, ("predecessor %s not made yet.\n", pgn->name));
663                     break;
664                 }
665             }
666             /*
667              * If ln isn't NULL, there's a predecessor as yet unmade, so we
668              * just drop this node on the floor. When the node in question
669              * has been made, it will notice this node as being ready to
670              * make but as yet unmade and will place the node on the queue.
671              */
672             if (ln != NULL) {
673                 continue;
674             }
675         }
676
677         numNodes--;
678         if (Make_OODate(gn)) {
679             DEBUGF(MAKE, ("out-of-date\n"));
680             if (queryFlag) {
681                 return (TRUE);
682             }
683             Make_DoAllVar(gn);
684             Job_Make(gn);
685         } else {
686             DEBUGF(MAKE, ("up-to-date\n"));
687             gn->made = UPTODATE;
688             if (gn->type & OP_JOIN) {
689                 /*
690                  * Even for an up-to-date .JOIN node, we need it to have its
691                  * context variables so references to it get the correct
692                  * value for .TARGET when building up the context variables
693                  * of its parent(s)...
694                  */
695                 Make_DoAllVar(gn);
696             }
697
698             Make_Update(gn);
699         }
700     }
701     return (FALSE);
702 }
703
704 /*-
705  *-----------------------------------------------------------------------
706  * MakePrintStatus --
707  *      Print the status of a top-level node, viz. it being up-to-date
708  *      already or not created due to an error in a lower level.
709  *      Callback function for Make_Run via Lst_ForEach.  If gn->unmade is
710  *      nonzero and that is meant to imply a cycle in the graph, then
711  *      cycle is TRUE.
712  *
713  * Results:
714  *      Always returns 0.
715  *
716  * Side Effects:
717  *      A message may be printed.
718  *
719  *-----------------------------------------------------------------------
720  */
721 static int
722 MakePrintStatus(void *gnp, void *cyclep)
723 {
724     GNode *gn = gnp;
725     Boolean cycle = *(Boolean *)cyclep;
726
727     if (gn->made == UPTODATE) {
728         printf("`%s' is up to date.\n", gn->name);
729     } else if (gn->unmade != 0) {
730         if (cycle) {
731             Boolean t = TRUE;
732             /*
733              * If printing cycles and came to one that has unmade children,
734              * print out the cycle by recursing on its children. Note a
735              * cycle like:
736              *  a : b
737              *  b : c
738              *  c : b
739              * will cause this to erroneously complain about a being in
740              * the cycle, but this is a good approximation.
741              */
742             if (gn->made == CYCLE) {
743                 Error("Graph cycles through `%s'", gn->name);
744                 gn->made = ENDCYCLE;
745                 Lst_ForEach(&gn->children, MakePrintStatus, &t);
746                 gn->made = UNMADE;
747             } else if (gn->made != ENDCYCLE) {
748                 gn->made = CYCLE;
749                 Lst_ForEach(&gn->children, MakePrintStatus, &t);
750             }
751         } else {
752             printf("`%s' not remade because of errors.\n", gn->name);
753         }
754     }
755     return (0);
756 }
757
758 /*-
759  *-----------------------------------------------------------------------
760  * Make_Run --
761  *      Initialize the nodes to remake and the list of nodes which are
762  *      ready to be made by doing a breadth-first traversal of the graph
763  *      starting from the nodes in the given list. Once this traversal
764  *      is finished, all the 'leaves' of the graph are in the toBeMade
765  *      queue.
766  *      Using this queue and the Job module, work back up the graph,
767  *      calling on MakeStartJobs to keep the job table as full as
768  *      possible.
769  *
770  * Results:
771  *      TRUE if work was done. FALSE otherwise.
772  *
773  * Side Effects:
774  *      The make field of all nodes involved in the creation of the given
775  *      targets is set to 1. The toBeMade list is set to contain all the
776  *      'leaves' of these subgraphs.
777  *-----------------------------------------------------------------------
778  */
779 Boolean
780 Make_Run(Lst *targs)
781 {
782     GNode           *gn;        /* a temporary pointer */
783     Lst             examine;    /* List of targets to examine */
784     int             errors;     /* Number of errors the Job module reports */
785
786     Lst_Init(&examine);
787     Lst_Duplicate(&examine, targs, NOCOPY);
788     numNodes = 0;
789
790     /*
791      * Make an initial downward pass over the graph, marking nodes to be made
792      * as we go down. We call Suff_FindDeps to find where a node is and
793      * to get some children for it if it has none and also has no commands.
794      * If the node is a leaf, we stick it on the toBeMade queue to
795      * be looked at in a minute, otherwise we add its children to our queue
796      * and go on about our business.
797      */
798     while (!Lst_IsEmpty(&examine)) {
799         gn = Lst_DeQueue(&examine);
800
801         if (!gn->make) {
802             gn->make = TRUE;
803             numNodes++;
804
805             /*
806              * Apply any .USE rules before looking for implicit dependencies
807              * to make sure everything has commands that should...
808              */
809             Lst_ForEach(&gn->children, MakeHandleUse, gn);
810             Suff_FindDeps(gn);
811
812             if (gn->unmade != 0) {
813                 Lst_ForEach(&gn->children, MakeAddChild, &examine);
814             } else {
815                 Lst_EnQueue(&toBeMade, gn);
816             }
817         }
818     }
819
820     if (queryFlag) {
821         /*
822          * We wouldn't do any work unless we could start some jobs in the
823          * next loop... (we won't actually start any, of course, this is just
824          * to see if any of the targets was out of date)
825          */
826         return (MakeStartJobs());
827     } else {
828         /*
829          * Initialization. At the moment, no jobs are running and until some
830          * get started, nothing will happen since the remaining upward
831          * traversal of the graph is performed by the routines in job.c upon
832          * the finishing of a job. So we fill the Job table as much as we can
833          * before going into our loop.
834          */
835          MakeStartJobs();
836     }
837
838     /*
839      * Main Loop: The idea here is that the ending of jobs will take
840      * care of the maintenance of data structures and the waiting for output
841      * will cause us to be idle most of the time while our children run as
842      * much as possible. Because the job table is kept as full as possible,
843      * the only time when it will be empty is when all the jobs which need
844      * running have been run, so that is the end condition of this loop.
845      * Note that the Job module will exit if there were any errors unless the
846      * keepgoing flag was given.
847      */
848     while (!Job_Empty ()) {
849         Job_CatchOutput(!Lst_IsEmpty(&toBeMade));
850         Job_CatchChildren(!usePipes);
851         MakeStartJobs();
852     }
853
854     errors = Job_Finish();
855
856     /*
857      * Print the final status of each target. E.g. if it wasn't made
858      * because some inferior reported an error.
859      */
860     errors = ((errors == 0) && (numNodes != 0));
861     Lst_ForEach(targs, MakePrintStatus, &errors);
862
863     return (TRUE);
864 }