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