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