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