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
7 * This code is derived from software contributed to Berkeley by
10 * Redistribution and use in source and binary forms, with or without
11 * modification, are permitted provided that the following conditions
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.
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
40 static char sccsid[] = "@(#)make.c 8.1 (Berkeley) 6/6/93";
45 * The functions which perform the examination of targets and
46 * their suitability for creation
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
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
61 * Make_TimeStamp Function to set the parent's cmtime field
62 * based on a child's modification time.
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.
69 * Make_OODate Determine if a target is out-of-date.
71 * Make_HandleUse See if a child is a .USE node for a parent
72 * and perform the .USE actions if so.
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
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 */
89 static int MakeAddChild __P((GNode *, Lst));
90 static int MakeAddAllSrc __P((GNode *, GNode *));
91 static Boolean MakeStartJobs __P((void));
92 static int MakePrintStatus __P((GNode *, Boolean));
94 *-----------------------------------------------------------------------
96 * Set the cmtime field of a parent node based on the mtime stamp in its
97 * child. Called from MakeOODate via Lst_ForEach.
103 * The cmtime of the parent node will be changed if the mtime
104 * field of the child is greater than it.
105 *-----------------------------------------------------------------------
108 Make_TimeStamp (pgn, cgn)
109 register GNode *pgn; /* the current parent */
110 register GNode *cgn; /* the child we've just examined */
112 if (cgn->mtime > pgn->cmtime) {
113 pgn->cmtime = cgn->mtime;
119 *-----------------------------------------------------------------------
121 * See if a given node is out of date with respect to its sources.
122 * Used by Make_Run when deciding which nodes to place on the
123 * toBeMade queue initially and by Make_Update to screen out USE and
124 * EXEC nodes. In the latter case, however, any other sort of node
125 * must be considered out-of-date since at least one of its children
126 * will have been recreated.
129 * TRUE if the node is out of date. FALSE otherwise.
132 * The mtime field of the node and the cmtime field of its parents
133 * will/may be changed.
134 *-----------------------------------------------------------------------
138 register GNode *gn; /* the node to check */
143 * Certain types of targets needn't even be sought as their datedness
144 * doesn't depend on their modification time...
146 if ((gn->type & (OP_JOIN|OP_USE|OP_EXEC)) == 0) {
147 (void) Dir_MTime (gn);
149 if (gn->mtime != 0) {
150 printf ("modified %s...", Targ_FmtTime(gn->mtime));
152 printf ("non-existent...");
158 * A target is remade in one of the following circumstances:
159 * its modification time is smaller than that of its youngest child
160 * and it would actually be run (has commands or type OP_NOP)
161 * it's the object of a force operator
162 * it has no children, was on the lhs of an operator and doesn't exist
165 * Libraries are only considered out-of-date if the archive module says
168 * These weird rules are brought to you by Backward-Compatability and
169 * the strange people who wrote 'Make'.
171 if (gn->type & OP_USE) {
173 * If the node is a USE node it is *never* out of date
177 printf(".USE node...");
180 } else if (gn->type & OP_LIB) {
182 printf("library...");
184 oodate = Arch_LibOODate (gn);
185 } else if (gn->type & OP_JOIN) {
187 * A target with the .JOIN attribute is only considered
188 * out-of-date if any of its children was out-of-date.
191 printf(".JOIN node...");
193 oodate = gn->childMade;
194 } else if (gn->type & (OP_FORCE|OP_EXEC)) {
196 * A node which is the object of the force (!) operator or which has
197 * the .EXEC attribute is always considered out-of-date.
200 if (gn->type & OP_FORCE) {
201 printf("! operator...");
203 printf(".EXEC node...");
207 } else if ((gn->mtime < gn->cmtime) ||
208 ((gn->cmtime == 0) &&
209 ((gn->mtime==0) || (gn->type & OP_DOUBLEDEP))))
212 * A node whose modification time is less than that of its
213 * youngest child or that has no children (cmtime == 0) and
214 * either doesn't exist (mtime == 0) or was the object of a
215 * :: operator is out-of-date. Why? Because that's the way Make does
219 if (gn->mtime < gn->cmtime) {
220 printf("modified before source...");
221 } else if (gn->mtime == 0) {
222 printf("non-existent and no sources...");
224 printf(":: operator and no sources...");
232 printf("source %smade...", gn->childMade ? "" : "not ");
234 oodate = gn->childMade;
241 * If the target isn't out-of-date, the parents need to know its
242 * modification time. Note that targets that appear to be out-of-date
243 * but aren't, because they have no commands and aren't of type OP_NOP,
244 * have their mtime stay below their children's mtime to keep parents from
245 * thinking they're out-of-date.
248 Lst_ForEach (gn->parents, Make_TimeStamp, (ClientData)gn);
255 *-----------------------------------------------------------------------
257 * Function used by Make_Run to add a child to the list l.
258 * It will only add the child if its make field is FALSE.
264 * The given list is extended
265 *-----------------------------------------------------------------------
269 GNode *gn; /* the node to add */
270 Lst l; /* the list to which to add it */
272 if (!gn->make && !(gn->type & OP_USE)) {
273 (void)Lst_EnQueue (l, (ClientData)gn);
279 *-----------------------------------------------------------------------
281 * Function called by Make_Run and SuffApplyTransform on the downward
282 * pass to handle .USE and transformation nodes. A callback function
283 * for Lst_ForEach, it implements the .USE and transformation
284 * functionality by copying the node's commands, type flags
285 * and children to the parent node. Should be called before the
286 * children are enqueued to be looked at by MakeAddChild.
288 * A .USE node is much like an explicit transformation rule, except
289 * its commands are always added to the target node, even if the
290 * target already has commands.
296 * Children and commands may be added to the parent and the parent's
297 * type may be changed.
299 *-----------------------------------------------------------------------
302 Make_HandleUse (cgn, pgn)
303 register GNode *cgn; /* The .USE node */
304 register GNode *pgn; /* The target of the .USE node */
306 register GNode *gn; /* A child of the .USE node */
307 register LstNode ln; /* An element in the children list */
309 if (cgn->type & (OP_USE|OP_TRANSFORM)) {
310 if ((cgn->type & OP_USE) || Lst_IsEmpty(pgn->commands)) {
312 * .USE or transformation and target has no commands -- append
313 * the child's commands to the parent.
315 (void) Lst_Concat (pgn->commands, cgn->commands, LST_CONCNEW);
318 if (Lst_Open (cgn->children) == SUCCESS) {
319 while ((ln = Lst_Next (cgn->children)) != NILLNODE) {
320 gn = (GNode *)Lst_Datum (ln);
322 if (Lst_Member (pgn->children, gn) == NILLNODE) {
323 (void) Lst_AtEnd (pgn->children, gn);
324 (void) Lst_AtEnd (gn->parents, pgn);
328 Lst_Close (cgn->children);
331 pgn->type |= cgn->type & ~(OP_OPMASK|OP_USE|OP_TRANSFORM);
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...
340 if (cgn->type & OP_USE) {
348 *-----------------------------------------------------------------------
350 * Perform update on the parents of a node. Used by JobFinish once
351 * a node has been dealt with and by MakeStartJobs if it finds an
358 * The unmade field of pgn is decremented and pgn may be placed on
359 * the toBeMade queue if this field becomes 0.
361 * If the child was made, the parent's childMade field will be set true
362 * and its cmtime set to now.
364 * If the child wasn't made, the cmtime field of the parent will be
365 * altered if the child's mtime is big enough.
367 * Finally, if the child is the implied source for the parent, the
368 * parent's IMPSRC variable is set appropriately.
370 *-----------------------------------------------------------------------
374 register GNode *cgn; /* the child node */
376 register GNode *pgn; /* the parent node */
377 register char *cname; /* the child's name */
378 register LstNode ln; /* Element in parents and iParents lists */
380 cname = Var_Value (TARGET, cgn);
383 * If the child was actually made, see what its modification time is
384 * now -- some rules won't actually update the file. If the file still
385 * doesn't exist, make its mtime now.
387 if (cgn->made != UPTODATE) {
390 * We can't re-stat the thing, but we can at least take care of rules
391 * where a target depends on a source that actually creates the
392 * target, but only if it has changed, e.g.
400 * cmp -s y.tab.h parse.h || mv y.tab.h parse.h
402 * In this case, if the definitions produced by yacc haven't changed
403 * from before, parse.h won't have been updated and cgn->mtime will
404 * reflect the current modification time for parse.h. This is
405 * something of a kludge, I admit, but it's a useful one..
406 * XXX: People like to use a rule like
410 * To force things that depend on FRC to be made, so we have to
411 * check for gn->children being empty as well...
413 if (!Lst_IsEmpty(cgn->commands) || Lst_IsEmpty(cgn->children)) {
418 * This is what Make does and it's actually a good thing, as it
421 * cmp -s y.tab.h parse.h || cp y.tab.h parse.h
423 * to function as intended. Unfortunately, thanks to the stateless
424 * nature of NFS (by which I mean the loose coupling of two clients
425 * using the same file from a common server), there are times
426 * when the modification time of a file created on a remote
427 * machine will not be modified before the local stat() implied by
428 * the Dir_MTime occurs, thus leading us to believe that the file
429 * is unchanged, wreaking havoc with files that depend on this one.
431 * I have decided it is better to make too much than to make too
432 * little, so this stuff is commented out unless you're sure it's ok.
436 * Christos, 4/9/92: If we are saving commands pretend that
437 * the target is made now. Otherwise archives with ... rules
440 if (noExecute || (cgn->type & OP_SAVE_CMDS) || Dir_MTime(cgn) == 0) {
444 printf("update time: %s\n", Targ_FmtTime(cgn->mtime));
449 if (Lst_Open (cgn->parents) == SUCCESS) {
450 while ((ln = Lst_Next (cgn->parents)) != NILLNODE) {
451 pgn = (GNode *)Lst_Datum (ln);
455 if ( ! (cgn->type & (OP_EXEC|OP_USE))) {
456 if (cgn->made == MADE) {
457 pgn->childMade = TRUE;
458 if (pgn->cmtime < cgn->mtime) {
459 pgn->cmtime = cgn->mtime;
462 (void)Make_TimeStamp (pgn, cgn);
465 if (pgn->unmade == 0) {
467 * Queue the node up -- any unmade predecessors will
468 * be dealt with in MakeStartJobs.
470 (void)Lst_EnQueue (toBeMade, (ClientData)pgn);
471 } else if (pgn->unmade < 0) {
472 Error ("Graph cycles through %s", pgn->name);
476 Lst_Close (cgn->parents);
479 * Deal with successor nodes. If any is marked for making and has an unmade
480 * count of 0, has not been made and isn't in the examination queue,
481 * it means we need to place it in the queue as it restrained itself
484 for (ln = Lst_First(cgn->successors); ln != NILLNODE; ln = Lst_Succ(ln)) {
485 GNode *succ = (GNode *)Lst_Datum(ln);
487 if (succ->make && succ->unmade == 0 && succ->made == UNMADE &&
488 Lst_Member(toBeMade, (ClientData)succ) == NILLNODE)
490 (void)Lst_EnQueue(toBeMade, (ClientData)succ);
495 * Set the .PREFIX and .IMPSRC variables for all the implied parents
498 if (Lst_Open (cgn->iParents) == SUCCESS) {
499 char *cpref = Var_Value(PREFIX, cgn);
501 while ((ln = Lst_Next (cgn->iParents)) != NILLNODE) {
502 pgn = (GNode *)Lst_Datum (ln);
504 Var_Set (IMPSRC, cname, pgn);
505 Var_Set (PREFIX, cpref, pgn);
508 Lst_Close (cgn->iParents);
513 *-----------------------------------------------------------------------
515 * Add a child's name to the ALLSRC and OODATE variables of the given
516 * node. Called from Make_DoAllVar via Lst_ForEach. A child is added only
517 * if it has not been given the .EXEC, .USE or .INVISIBLE attributes.
518 * .EXEC and .USE children are very rarely going to be files, so...
519 * A child is added to the OODATE variable if its modification time is
520 * later than that of its parent, as defined by Make, except if the
521 * parent is a .JOIN node. In that case, it is only added to the OODATE
522 * variable if it was actually made (since .JOIN nodes don't have
523 * modification times, the comparison is rather unfair...)..
529 * The ALLSRC variable for the given node is extended.
530 *-----------------------------------------------------------------------
533 MakeAddAllSrc (cgn, pgn)
534 GNode *cgn; /* The child to add */
535 GNode *pgn; /* The parent to whose ALLSRC variable it should be */
538 if ((cgn->type & (OP_EXEC|OP_USE|OP_INVISIBLE)) == 0) {
539 register char *child;
541 child = Var_Value(TARGET, cgn);
542 Var_Append (ALLSRC, child, pgn);
543 if (pgn->type & OP_JOIN) {
544 if (cgn->made == MADE) {
545 Var_Append(OODATE, child, pgn);
547 } else if ((pgn->mtime < cgn->mtime) ||
548 (cgn->mtime >= now && cgn->made == MADE))
551 * It goes in the OODATE variable if the parent is younger than the
552 * child or if the child has been modified more recently than
553 * the start of the make. This is to keep pmake from getting
554 * confused if something else updates the parent after the
555 * make starts (shouldn't happen, I know, but sometimes it
556 * does). In such a case, if we've updated the kid, the parent
557 * is likely to have a modification time later than that of
558 * the kid and anything that relies on the OODATE variable will
561 * XXX: This will cause all made children to go in the OODATE
562 * variable, even if they're not touched, if RECHECK isn't defined,
563 * since cgn->mtime is set to now in Make_Update. According to
564 * some people, this is good...
566 Var_Append(OODATE, child, pgn);
573 *-----------------------------------------------------------------------
575 * Set up the ALLSRC and OODATE variables. Sad to say, it must be
576 * done separately, rather than while traversing the graph. This is
577 * because Make defined OODATE to contain all sources whose modification
578 * times were later than that of the target, *not* those sources that
579 * were out-of-date. Since in both compatibility and native modes,
580 * the modification time of the parent isn't found until the child
581 * has been dealt with, we have to wait until now to fill in the
582 * variable. As for ALLSRC, the ordering is important and not
583 * guaranteed when in native mode, so it must be set here, too.
589 * The ALLSRC and OODATE variables of the given node is filled in.
590 * If the node is a .JOIN node, its TARGET variable will be set to
591 * match its ALLSRC variable.
592 *-----------------------------------------------------------------------
598 Lst_ForEach (gn->children, MakeAddAllSrc, gn);
600 if (!Var_Exists (OODATE, gn)) {
601 Var_Set (OODATE, "", gn);
603 if (!Var_Exists (ALLSRC, gn)) {
604 Var_Set (ALLSRC, "", gn);
607 if (gn->type & OP_JOIN) {
608 Var_Set (TARGET, Var_Value (ALLSRC, gn), gn);
613 *-----------------------------------------------------------------------
615 * Start as many jobs as possible.
618 * If the query flag was given to pmake, no job will be started,
619 * but as soon as an out-of-date target is found, this function
620 * returns TRUE. At all other times, this function returns FALSE.
623 * Nodes are removed from the toBeMade queue and job table slots
626 *-----------------------------------------------------------------------
633 while (!Job_Full() && !Lst_IsEmpty (toBeMade)) {
634 gn = (GNode *) Lst_DeQueue (toBeMade);
636 printf ("Examining %s...", gn->name);
639 * Make sure any and all predecessors that are going to be made,
642 if (!Lst_IsEmpty(gn->preds)) {
645 for (ln = Lst_First(gn->preds); ln != NILLNODE; ln = Lst_Succ(ln)){
646 GNode *pgn = (GNode *)Lst_Datum(ln);
648 if (pgn->make && pgn->made == UNMADE) {
650 printf("predecessor %s not made yet.\n", pgn->name);
656 * If ln isn't nil, there's a predecessor as yet unmade, so we
657 * just drop this node on the floor. When the node in question
658 * has been made, it will notice this node as being ready to
659 * make but as yet unmade and will place the node on the queue.
661 if (ln != NILLNODE) {
667 if (Make_OODate (gn)) {
669 printf ("out-of-date\n");
678 printf ("up-to-date\n");
681 if (gn->type & OP_JOIN) {
683 * Even for an up-to-date .JOIN node, we need it to have its
684 * context variables so references to it get the correct
685 * value for .TARGET when building up the context variables
686 * of its parent(s)...
698 *-----------------------------------------------------------------------
700 * Print the status of a top-level node, viz. it being up-to-date
701 * already or not created due to an error in a lower level.
702 * Callback function for Make_Run via Lst_ForEach.
708 * A message may be printed.
710 *-----------------------------------------------------------------------
713 MakePrintStatus(gn, cycle)
714 GNode *gn; /* Node to examine */
715 Boolean cycle; /* True if gn->unmade being non-zero implies
716 * a cycle in the graph, not an error in an
719 if (gn->made == UPTODATE) {
720 printf ("`%s' is up to date.\n", gn->name);
721 } else if (gn->unmade != 0) {
724 * If printing cycles and came to one that has unmade children,
725 * print out the cycle by recursing on its children. Note a
730 * will cause this to erroneously complain about a being in
731 * the cycle, but this is a good approximation.
733 if (gn->made == CYCLE) {
734 Error("Graph cycles through `%s'", gn->name);
736 Lst_ForEach(gn->children, MakePrintStatus, (ClientData)TRUE);
738 } else if (gn->made != ENDCYCLE) {
740 Lst_ForEach(gn->children, MakePrintStatus, (ClientData)TRUE);
743 printf ("`%s' not remade because of errors.\n", gn->name);
750 *-----------------------------------------------------------------------
752 * Initialize the nodes to remake and the list of nodes which are
753 * ready to be made by doing a breadth-first traversal of the graph
754 * starting from the nodes in the given list. Once this traversal
755 * is finished, all the 'leaves' of the graph are in the toBeMade
757 * Using this queue and the Job module, work back up the graph,
758 * calling on MakeStartJobs to keep the job table as full as
762 * TRUE if work was done. FALSE otherwise.
765 * The make field of all nodes involved in the creation of the given
766 * targets is set to 1. The toBeMade list is set to contain all the
767 * 'leaves' of these subgraphs.
768 *-----------------------------------------------------------------------
772 Lst targs; /* the initial list of targets */
774 register GNode *gn; /* a temporary pointer */
775 register Lst examine; /* List of targets to examine */
776 int errors; /* Number of errors the Job module reports */
778 toBeMade = Lst_Init (FALSE);
780 examine = Lst_Duplicate(targs, NOCOPY);
784 * Make an initial downward pass over the graph, marking nodes to be made
785 * as we go down. We call Suff_FindDeps to find where a node is and
786 * to get some children for it if it has none and also has no commands.
787 * If the node is a leaf, we stick it on the toBeMade queue to
788 * be looked at in a minute, otherwise we add its children to our queue
789 * and go on about our business.
791 while (!Lst_IsEmpty (examine)) {
792 gn = (GNode *) Lst_DeQueue (examine);
799 * Apply any .USE rules before looking for implicit dependencies
800 * to make sure everything has commands that should...
802 Lst_ForEach (gn->children, Make_HandleUse, (ClientData)gn);
805 if (gn->unmade != 0) {
806 Lst_ForEach (gn->children, MakeAddChild, (ClientData)examine);
808 (void)Lst_EnQueue (toBeMade, (ClientData)gn);
813 Lst_Destroy (examine, NOFREE);
817 * We wouldn't do any work unless we could start some jobs in the
818 * next loop... (we won't actually start any, of course, this is just
819 * to see if any of the targets was out of date)
821 return (MakeStartJobs());
824 * Initialization. At the moment, no jobs are running and until some
825 * get started, nothing will happen since the remaining upward
826 * traversal of the graph is performed by the routines in job.c upon
827 * the finishing of a job. So we fill the Job table as much as we can
828 * before going into our loop.
830 (void) MakeStartJobs();
834 * Main Loop: The idea here is that the ending of jobs will take
835 * care of the maintenance of data structures and the waiting for output
836 * will cause us to be idle most of the time while our children run as
837 * much as possible. Because the job table is kept as full as possible,
838 * the only time when it will be empty is when all the jobs which need
839 * running have been run, so that is the end condition of this loop.
840 * Note that the Job module will exit if there were any errors unless the
841 * keepgoing flag was given.
843 while (!Job_Empty ()) {
845 Job_CatchChildren (!usePipes);
846 (void)MakeStartJobs();
852 * Print the final status of each target. E.g. if it wasn't made
853 * because some inferior reported an error.
855 Lst_ForEach(targs, MakePrintStatus,
856 (ClientData)((errors == 0) && (numNodes != 0)));