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