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