Annotation of src/usr.bin/make/make.c, Revision 1.39
1.25 espie 1: /* $OpenPackages$ */
1.39 ! espie 2: /* $OpenBSD: make.c,v 1.38 2007/09/16 12:09:36 espie Exp $ */
1.6 millert 3: /* $NetBSD: make.c,v 1.10 1996/11/06 17:59:15 christos Exp $ */
1.1 deraadt 4:
5: /*
1.4 millert 6: * Copyright (c) 1988, 1989, 1990, 1993
7: * The Regents of the University of California. All rights reserved.
1.1 deraadt 8: * Copyright (c) 1989 by Berkeley Softworks
9: * All rights reserved.
10: *
11: * This code is derived from software contributed to Berkeley by
12: * Adam de Boor.
13: *
14: * Redistribution and use in source and binary forms, with or without
15: * modification, are permitted provided that the following conditions
16: * are met:
17: * 1. Redistributions of source code must retain the above copyright
18: * notice, this list of conditions and the following disclaimer.
19: * 2. Redistributions in binary form must reproduce the above copyright
20: * notice, this list of conditions and the following disclaimer in the
21: * documentation and/or other materials provided with the distribution.
1.33 millert 22: * 3. Neither the name of the University nor the names of its contributors
1.1 deraadt 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:
39: /*-
40: * make.c --
41: * The functions which perform the examination of targets and
42: * their suitability for creation
43: *
44: * Interface:
1.25 espie 45: * Make_Run Initialize things for the module and recreate
1.26 espie 46: * whatever needs recreating. Returns true if
47: * work was (or would have been) done and
48: * false
1.25 espie 49: * otherwise.
50: *
51: * Make_Update Update all parents of a given child. Performs
52: * various bookkeeping chores like the updating
53: * of the cmtime field of the parent, filling
54: * of the IMPSRC context variable, etc. It will
55: * place the parent on the toBeMade queue if it
56: * should be.
57: *
58: * Make_TimeStamp Function to set the parent's cmtime field
59: * based on a child's modification time.
60: *
61: * Make_DoAllVar Set up the various local variables for a
62: * target, including the .ALLSRC variable, making
63: * sure that any variable that needs to exist
64: * at the very least has the empty value.
1.1 deraadt 65: *
1.25 espie 66: * Make_OODate Determine if a target is out-of-date.
1.1 deraadt 67: *
1.5 millert 68: * Make_HandleUse See if a child is a .USE node for a parent
1.1 deraadt 69: * and perform the .USE actions if so.
70: */
71:
1.27 espie 72: #include <limits.h>
1.26 espie 73: #include <stdio.h>
74: #include "config.h"
75: #include "defines.h"
76: #include "dir.h"
77: #include "job.h"
78: #include "suff.h"
79: #include "var.h"
80: #include "error.h"
81: #include "make.h"
82: #include "gnode.h"
83: #include "extern.h"
84: #include "timestamp.h"
1.37 espie 85: #include "engine.h"
1.26 espie 86: #include "lst.h"
1.25 espie 87:
88: static LIST toBeMade; /* The current fringe of the graph. These
1.1 deraadt 89: * are nodes which await examination by
90: * MakeOODate. It is added to by
91: * Make_Update and subtracted from by
92: * MakeStartJobs */
1.25 espie 93: static int numNodes; /* Number of nodes to be processed. If this
1.1 deraadt 94: * is non-zero when Job_Empty() returns
1.26 espie 95: * true, there's a cycle in the graph */
1.1 deraadt 96:
1.25 espie 97: static void MakeAddChild(void *, void *);
98: static void MakeHandleUse(void *, void *);
1.26 espie 99: static bool MakeStartJobs(void);
1.25 espie 100: static void MakePrintStatus(void *, void *);
1.1 deraadt 101: /*-
102: *-----------------------------------------------------------------------
103: * MakeAddChild --
104: * Function used by Make_Run to add a child to the list l.
1.26 espie 105: * It will only add the child if its make field is false.
1.1 deraadt 106: *
107: * Side Effects:
108: * The given list is extended
109: *-----------------------------------------------------------------------
110: */
1.15 espie 111: static void
1.35 espie 112: MakeAddChild(
113: void *gnp, /* the node to add */
114: void *lp) /* the list to which to add it */
1.1 deraadt 115: {
1.25 espie 116: GNode *gn = (GNode *)gnp;
117: Lst l = (Lst)lp;
1.5 millert 118:
1.15 espie 119: if (!gn->make && !(gn->type & OP_USE))
1.14 espie 120: Lst_EnQueue(l, gn);
1.1 deraadt 121: }
1.25 espie 122:
1.15 espie 123: static void
1.35 espie 124: MakeHandleUse(
125: void *pgn, /* the current parent */
126: void *cgn) /* the child we've just examined */
1.1 deraadt 127: {
1.15 espie 128: Make_HandleUse((GNode *)pgn, (GNode *)cgn);
1.1 deraadt 129: }
1.25 espie 130:
1.1 deraadt 131: /*-
132: *-----------------------------------------------------------------------
1.25 espie 133: * Make_Update --
1.1 deraadt 134: * Perform update on the parents of a node. Used by JobFinish once
135: * a node has been dealt with and by MakeStartJobs if it finds an
1.4 millert 136: * up-to-date node.
1.1 deraadt 137: *
138: * Results:
139: * Always returns 0
140: *
141: * Side Effects:
142: * The unmade field of pgn is decremented and pgn may be placed on
143: * the toBeMade queue if this field becomes 0.
144: *
1.25 espie 145: * If the child was made, the parent's childMade field will be set true
1.1 deraadt 146: * and its cmtime set to now.
147: *
148: * If the child wasn't made, the cmtime field of the parent will be
149: * altered if the child's mtime is big enough.
150: *
151: * Finally, if the child is the implied source for the parent, the
152: * parent's IMPSRC variable is set appropriately.
153: *
154: *-----------------------------------------------------------------------
155: */
156: void
1.35 espie 157: Make_Update(GNode *cgn) /* the child node */
1.1 deraadt 158: {
1.25 espie 159: GNode *pgn; /* the parent node */
160: char *cname; /* the child's name */
161: LstNode ln; /* Element in parents and iParents lists */
1.1 deraadt 162:
1.20 espie 163: cname = Varq_Value(TARGET_INDEX, cgn);
1.1 deraadt 164:
165: /*
166: * If the child was actually made, see what its modification time is
167: * now -- some rules won't actually update the file. If the file still
168: * doesn't exist, make its mtime now.
169: */
170: if (cgn->made != UPTODATE) {
171: /*
172: * This is what Make does and it's actually a good thing, as it
173: * allows rules like
174: *
175: * cmp -s y.tab.h parse.h || cp y.tab.h parse.h
176: *
177: * to function as intended. Unfortunately, thanks to the stateless
178: * nature of NFS (by which I mean the loose coupling of two clients
179: * using the same file from a common server), there are times
180: * when the modification time of a file created on a remote
181: * machine will not be modified before the local stat() implied by
182: * the Dir_MTime occurs, thus leading us to believe that the file
183: * is unchanged, wreaking havoc with files that depend on this one.
184: *
185: * I have decided it is better to make too much than to make too
186: * little, so this stuff is commented out unless you're sure it's ok.
187: * -- ardeb 1/12/88
188: */
189: /*
1.25 espie 190: * Christos, 4/9/92: If we are saving commands pretend that
1.1 deraadt 191: * the target is made now. Otherwise archives with ... rules
192: * don't work!
193: */
1.25 espie 194: if (noExecute || (cgn->type & OP_SAVE_CMDS) ||
1.23 espie 195: is_out_of_date(Dir_MTime(cgn))) {
1.1 deraadt 196: cgn->mtime = now;
197: }
198: if (DEBUG(MAKE)) {
1.38 espie 199: printf("update time: %s\n", time_to_string(cgn->mtime));
1.1 deraadt 200: }
201: }
1.4 millert 202:
1.25 espie 203: for (ln = Lst_First(&cgn->parents); ln != NULL; ln = Lst_Adv(ln)) {
1.19 espie 204: pgn = (GNode *)Lst_Datum(ln);
205: if (pgn->make) {
1.39 ! espie 206: pgn->unmade--;
1.19 espie 207:
208: if ( ! (cgn->type & (OP_EXEC|OP_USE))) {
209: if (cgn->made == MADE) {
1.26 espie 210: pgn->childMade = true;
211: if (is_strictly_before(pgn->cmtime, cgn->mtime))
1.19 espie 212: pgn->cmtime = cgn->mtime;
213: } else {
1.24 espie 214: (void)Make_TimeStamp(pgn, cgn);
1.1 deraadt 215: }
1.19 espie 216: }
217: if (pgn->unmade == 0) {
218: /*
219: * Queue the node up -- any unmade predecessors will
220: * be dealt with in MakeStartJobs.
221: */
222: Lst_EnQueue(&toBeMade, pgn);
223: } else if (pgn->unmade < 0) {
1.25 espie 224: Error("Graph cycles through %s", pgn->name);
1.1 deraadt 225: }
226: }
227: }
1.25 espie 228: /* Deal with successor nodes. If any is marked for making and has an unmade
1.1 deraadt 229: * count of 0, has not been made and isn't in the examination queue,
230: * it means we need to place it in the queue as it restrained itself
1.25 espie 231: * before. */
1.19 espie 232: for (ln = Lst_First(&cgn->successors); ln != NULL; ln = Lst_Adv(ln)) {
1.1 deraadt 233: GNode *succ = (GNode *)Lst_Datum(ln);
234:
1.25 espie 235: if (succ->make && succ->unmade == 0 && succ->made == UNMADE)
236: (void)Lst_QueueNew(&toBeMade, succ);
1.1 deraadt 237: }
1.4 millert 238:
1.25 espie 239: /* Set the .PREFIX and .IMPSRC variables for all the implied parents
240: * of this node. */
1.19 espie 241: {
1.20 espie 242: char *cpref = Varq_Value(PREFIX_INDEX, cgn);
1.1 deraadt 243:
1.25 espie 244: for (ln = Lst_First(&cgn->iParents); ln != NULL; ln = Lst_Adv(ln)) {
245: pgn = (GNode *)Lst_Datum(ln);
246: if (pgn->make) {
1.32 deraadt 247: Varq_Set(IMPSRC_INDEX, cname, pgn);
1.25 espie 248: Varq_Set(PREFIX_INDEX, cpref, pgn);
1.1 deraadt 249: }
1.25 espie 250: }
1.1 deraadt 251: }
252: }
1.25 espie 253:
1.1 deraadt 254: /*-
255: *-----------------------------------------------------------------------
256: * MakeStartJobs --
257: * Start as many jobs as possible.
258: *
259: * Results:
260: * If the query flag was given to pmake, no job will be started,
261: * but as soon as an out-of-date target is found, this function
1.26 espie 262: * returns true. At all other times, this function returns false.
1.1 deraadt 263: *
264: * Side Effects:
265: * Nodes are removed from the toBeMade queue and job table slots
266: * are filled.
267: *-----------------------------------------------------------------------
268: */
1.26 espie 269: static bool
1.35 espie 270: MakeStartJobs(void)
1.1 deraadt 271: {
1.25 espie 272: GNode *gn;
1.4 millert 273:
1.17 espie 274: while (!Job_Full() && (gn = (GNode *)Lst_DeQueue(&toBeMade)) != NULL) {
1.1 deraadt 275: if (DEBUG(MAKE)) {
1.25 espie 276: printf("Examining %s...", gn->name);
1.1 deraadt 277: }
278: /*
279: * Make sure any and all predecessors that are going to be made,
280: * have been.
281: */
1.17 espie 282: if (!Lst_IsEmpty(&gn->preds)) {
1.1 deraadt 283: LstNode ln;
284:
1.19 espie 285: for (ln = Lst_First(&gn->preds); ln != NULL; ln = Lst_Adv(ln)){
1.1 deraadt 286: GNode *pgn = (GNode *)Lst_Datum(ln);
287:
288: if (pgn->make && pgn->made == UNMADE) {
289: if (DEBUG(MAKE)) {
290: printf("predecessor %s not made yet.\n", pgn->name);
291: }
292: break;
293: }
294: }
295: /*
1.25 espie 296: * If ln isn't NULL, there's a predecessor as yet unmade, so we
1.1 deraadt 297: * just drop this node on the floor. When the node in question
298: * has been made, it will notice this node as being ready to
299: * make but as yet unmade and will place the node on the queue.
300: */
1.10 espie 301: if (ln != NULL) {
1.1 deraadt 302: continue;
303: }
304: }
1.4 millert 305:
1.1 deraadt 306: numNodes--;
1.25 espie 307: if (Make_OODate(gn)) {
1.1 deraadt 308: if (DEBUG(MAKE)) {
1.25 espie 309: printf("out-of-date\n");
1.1 deraadt 310: }
311: if (queryFlag) {
1.26 espie 312: return true;
1.1 deraadt 313: }
1.25 espie 314: Make_DoAllVar(gn);
315: Job_Make(gn);
1.1 deraadt 316: } else {
317: if (DEBUG(MAKE)) {
1.25 espie 318: printf("up-to-date\n");
1.1 deraadt 319: }
320: gn->made = UPTODATE;
321: if (gn->type & OP_JOIN) {
322: /*
323: * Even for an up-to-date .JOIN node, we need it to have its
324: * context variables so references to it get the correct
325: * value for .TARGET when building up the context variables
326: * of its parent(s)...
327: */
1.25 espie 328: Make_DoAllVar(gn);
1.1 deraadt 329: }
1.4 millert 330:
1.25 espie 331: Make_Update(gn);
1.1 deraadt 332: }
333: }
1.26 espie 334: return false;
1.1 deraadt 335: }
1.25 espie 336:
1.1 deraadt 337: /*-
338: *-----------------------------------------------------------------------
339: * MakePrintStatus --
340: * Print the status of a top-level node, viz. it being up-to-date
341: * already or not created due to an error in a lower level.
342: * Callback function for Make_Run via Lst_ForEach.
1.25 espie 343: *
344: * Side Effects:
345: * A message may be printed.
1.1 deraadt 346: *-----------------------------------------------------------------------
347: */
1.15 espie 348: static void
1.35 espie 349: MakePrintStatus(
350: void *gnp, /* Node to examine */
351: void *cyclep) /* True if gn->unmade being non-zero implies
1.1 deraadt 352: * a cycle in the graph, not an error in an
353: * inferior */
354: {
1.25 espie 355: GNode *gn = (GNode *)gnp;
1.26 espie 356: bool cycle = *(bool *)cyclep;
1.1 deraadt 357: if (gn->made == UPTODATE) {
1.25 espie 358: printf("`%s' is up to date.\n", gn->name);
1.1 deraadt 359: } else if (gn->unmade != 0) {
360: if (cycle) {
1.26 espie 361: bool t = true;
1.1 deraadt 362: /*
363: * If printing cycles and came to one that has unmade children,
364: * print out the cycle by recursing on its children. Note a
365: * cycle like:
366: * a : b
367: * b : c
368: * c : b
369: * will cause this to erroneously complain about a being in
370: * the cycle, but this is a good approximation.
371: */
372: if (gn->made == CYCLE) {
373: Error("Graph cycles through `%s'", gn->name);
374: gn->made = ENDCYCLE;
1.17 espie 375: Lst_ForEach(&gn->children, MakePrintStatus, &t);
1.1 deraadt 376: gn->made = UNMADE;
377: } else if (gn->made != ENDCYCLE) {
378: gn->made = CYCLE;
1.17 espie 379: Lst_ForEach(&gn->children, MakePrintStatus, &t);
1.1 deraadt 380: }
381: } else {
1.25 espie 382: printf("`%s' not remade because of errors.\n", gn->name);
1.1 deraadt 383: }
384: }
385: }
1.25 espie 386:
1.5 millert 387:
1.1 deraadt 388: /*-
389: *-----------------------------------------------------------------------
1.6 millert 390: * Make_Run --
391: * Initialize the nodes to remake and the list of nodes which are
392: * ready to be made by doing a breadth-first traversal of the graph
393: * starting from the nodes in the given list. Once this traversal
394: * is finished, all the 'leaves' of the graph are in the toBeMade
395: * queue.
396: * Using this queue and the Job module, work back up the graph,
397: * calling on MakeStartJobs to keep the job table as full as
398: * possible.
399: *
1.1 deraadt 400: * Results:
1.26 espie 401: * true if work was done. false otherwise.
1.1 deraadt 402: *
403: * Side Effects:
1.6 millert 404: * The make field of all nodes involved in the creation of the given
405: * targets is set to 1. The toBeMade list is set to contain all the
406: * 'leaves' of these subgraphs.
1.1 deraadt 407: *-----------------------------------------------------------------------
408: */
1.26 espie 409: bool
1.35 espie 410: Make_Run(Lst targs) /* the initial list of targets */
1.1 deraadt 411: {
1.25 espie 412: GNode *gn; /* a temporary pointer */
413: LIST examine; /* List of targets to examine */
414: int errors; /* Number of errors the Job module reports */
1.1 deraadt 415:
1.30 espie 416: Static_Lst_Init(&toBeMade);
1.1 deraadt 417:
1.18 espie 418: Lst_Clone(&examine, targs, NOCOPY);
1.1 deraadt 419: numNodes = 0;
1.4 millert 420:
1.1 deraadt 421: /*
422: * Make an initial downward pass over the graph, marking nodes to be made
423: * as we go down. We call Suff_FindDeps to find where a node is and
424: * to get some children for it if it has none and also has no commands.
425: * If the node is a leaf, we stick it on the toBeMade queue to
426: * be looked at in a minute, otherwise we add its children to our queue
1.4 millert 427: * and go on about our business.
1.1 deraadt 428: */
1.18 espie 429: while ((gn = (GNode *)Lst_DeQueue(&examine)) != NULL) {
1.1 deraadt 430: if (!gn->make) {
1.26 espie 431: gn->make = true;
1.1 deraadt 432: numNodes++;
1.4 millert 433:
1.1 deraadt 434: /*
435: * Apply any .USE rules before looking for implicit dependencies
436: * to make sure everything has commands that should...
437: */
1.17 espie 438: Lst_ForEach(&gn->children, MakeHandleUse, gn);
1.25 espie 439: Suff_FindDeps(gn);
1.1 deraadt 440:
1.6 millert 441: if (gn->unmade != 0) {
1.18 espie 442: Lst_ForEach(&gn->children, MakeAddChild, &examine);
1.1 deraadt 443: } else {
1.17 espie 444: Lst_EnQueue(&toBeMade, gn);
1.1 deraadt 445: }
446: }
447: }
1.4 millert 448:
1.1 deraadt 449: if (queryFlag) {
450: /*
451: * We wouldn't do any work unless we could start some jobs in the
452: * next loop... (we won't actually start any, of course, this is just
453: * to see if any of the targets was out of date)
454: */
1.25 espie 455: return MakeStartJobs();
1.1 deraadt 456: } else {
457: /*
458: * Initialization. At the moment, no jobs are running and until some
459: * get started, nothing will happen since the remaining upward
460: * traversal of the graph is performed by the routines in job.c upon
461: * the finishing of a job. So we fill the Job table as much as we can
1.4 millert 462: * before going into our loop.
1.1 deraadt 463: */
1.25 espie 464: (void)MakeStartJobs();
1.1 deraadt 465: }
466:
467: /*
468: * Main Loop: The idea here is that the ending of jobs will take
469: * care of the maintenance of data structures and the waiting for output
470: * will cause us to be idle most of the time while our children run as
471: * much as possible. Because the job table is kept as full as possible,
472: * the only time when it will be empty is when all the jobs which need
473: * running have been run, so that is the end condition of this loop.
474: * Note that the Job module will exit if there were any errors unless the
475: * keepgoing flag was given.
476: */
1.25 espie 477: while (!Job_Empty()) {
478: Job_CatchOutput();
479: Job_CatchChildren(!usePipes);
1.1 deraadt 480: (void)MakeStartJobs();
481: }
482:
1.7 espie 483: errors = Job_Finish();
1.1 deraadt 484:
485: /*
486: * Print the final status of each target. E.g. if it wasn't made
487: * because some inferior reported an error.
488: */
1.25 espie 489: errors = errors == 0 && numNodes != 0;
1.14 espie 490: Lst_ForEach(targs, MakePrintStatus, &errors);
1.4 millert 491:
1.26 espie 492: return true;
1.1 deraadt 493: }