make.c revision 146580
1141104Sharti/*- 21590Srgrimes * Copyright (c) 1988, 1989, 1990, 1993 31590Srgrimes * The Regents of the University of California. All rights reserved. 41590Srgrimes * Copyright (c) 1989 by Berkeley Softworks 51590Srgrimes * All rights reserved. 61590Srgrimes * 71590Srgrimes * This code is derived from software contributed to Berkeley by 81590Srgrimes * Adam de Boor. 91590Srgrimes * 101590Srgrimes * Redistribution and use in source and binary forms, with or without 111590Srgrimes * modification, are permitted provided that the following conditions 121590Srgrimes * are met: 131590Srgrimes * 1. Redistributions of source code must retain the above copyright 141590Srgrimes * notice, this list of conditions and the following disclaimer. 151590Srgrimes * 2. Redistributions in binary form must reproduce the above copyright 161590Srgrimes * notice, this list of conditions and the following disclaimer in the 171590Srgrimes * documentation and/or other materials provided with the distribution. 181590Srgrimes * 3. All advertising materials mentioning features or use of this software 191590Srgrimes * must display the following acknowledgement: 201590Srgrimes * This product includes software developed by the University of 211590Srgrimes * California, Berkeley and its contributors. 221590Srgrimes * 4. Neither the name of the University nor the names of its contributors 231590Srgrimes * may be used to endorse or promote products derived from this software 241590Srgrimes * without specific prior written permission. 251590Srgrimes * 261590Srgrimes * THIS SOFTWARE IS PROVIDED BY THE REGENTS AND CONTRIBUTORS ``AS IS'' AND 271590Srgrimes * ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE 281590Srgrimes * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE 291590Srgrimes * ARE DISCLAIMED. IN NO EVENT SHALL THE REGENTS OR CONTRIBUTORS BE LIABLE 301590Srgrimes * FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL 311590Srgrimes * DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS 321590Srgrimes * OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) 331590Srgrimes * HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT 341590Srgrimes * LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY 351590Srgrimes * OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF 361590Srgrimes * SUCH DAMAGE. 3762833Swsanchez * 3862833Swsanchez * @(#)make.c 8.1 (Berkeley) 6/6/93 391590Srgrimes */ 401590Srgrimes 4162833Swsanchez#include <sys/cdefs.h> 4294587Sobrien__FBSDID("$FreeBSD: head/usr.bin/make/make.c 146580 2005-05-24 15:58:35Z harti $"); 431590Srgrimes 44144478Sharti/* 45144478Sharti * make.c 461590Srgrimes * The functions which perform the examination of targets and 471590Srgrimes * their suitability for creation 481590Srgrimes * 491590Srgrimes * Interface: 50144478Sharti * Make_Run Initialize things for the module and recreate 51144478Sharti * whatever needs recreating. Returns TRUE if 52144478Sharti * work was (or would have been) done and FALSE 53144478Sharti * otherwise. 541590Srgrimes * 55144478Sharti * Make_Update Update all parents of a given child. Performs 56144478Sharti * various bookkeeping chores like the updating 57144478Sharti * of the cmtime field of the parent, filling 58144478Sharti * of the IMPSRC context variable, etc. It will 59144478Sharti * place the parent on the toBeMade queue if it should be. 601590Srgrimes * 61144478Sharti * Make_TimeStamp Function to set the parent's cmtime field 62144478Sharti * based on a child's modification time. 631590Srgrimes * 64144478Sharti * Make_DoAllVar Set up the various local variables for a 65144478Sharti * target, including the .ALLSRC variable, making 66144478Sharti * sure that any variable that needs to exist 67144478Sharti * at the very least has the empty value. 681590Srgrimes * 69144478Sharti * Make_OODate Determine if a target is out-of-date. 701590Srgrimes * 71144478Sharti * Make_HandleUse See if a child is a .USE node for a parent 72144478Sharti * and perform the .USE actions if so. 731590Srgrimes */ 741590Srgrimes 75141104Sharti#include <stdlib.h> 761590Srgrimes 77141104Sharti#include "arch.h" 78141104Sharti#include "config.h" 79141104Sharti#include "dir.h" 80141104Sharti#include "globals.h" 81141104Sharti#include "GNode.h" 82141104Sharti#include "job.h" 83141104Sharti#include "make.h" 84146066Sharti#include "parse.h" 85141104Sharti#include "suff.h" 86141104Sharti#include "targ.h" 87141104Sharti#include "util.h" 88141104Sharti#include "var.h" 89141104Sharti 90138916Sharti/* The current fringe of the graph. These are nodes which await examination 91138916Sharti * by MakeOODate. It is added to by Make_Update and subtracted from by 92138916Sharti * MakeStartJobs */ 93138916Shartistatic Lst toBeMade = Lst_Initializer(toBeMade); 94138916Sharti 95144478Sharti/* 96144478Sharti * Number of nodes to be processed. If this is non-zero when Job_Empty() 97144478Sharti * returns TRUE, there's a cycle in the graph. 98144478Sharti */ 99144478Shartistatic int numNodes; 1001590Srgrimes 10192921Simpstatic Boolean MakeStartJobs(void); 102138232Sharti 103144478Sharti/** 104144478Sharti * Make_TimeStamp 1051590Srgrimes * Set the cmtime field of a parent node based on the mtime stamp in its 106143694Sharti * child. Called from MakeOODate via LST_FOREACH. 1071590Srgrimes * 1081590Srgrimes * Results: 1098874Srgrimes * Always returns 0. 1101590Srgrimes * 1111590Srgrimes * Side Effects: 1121590Srgrimes * The cmtime of the parent node will be changed if the mtime 1131590Srgrimes * field of the child is greater than it. 1141590Srgrimes */ 1151590Srgrimesint 116138232ShartiMake_TimeStamp(GNode *pgn, GNode *cgn) 1171590Srgrimes{ 118138232Sharti 119144478Sharti if (cgn->mtime > pgn->cmtime) { 120144478Sharti pgn->cmtime = cgn->mtime; 121144478Sharti } 122144478Sharti return (0); 1231590Srgrimes} 1245814Sjkh 125144478Sharti/** 126144478Sharti * Make_OODate 1271590Srgrimes * See if a given node is out of date with respect to its sources. 1281590Srgrimes * Used by Make_Run when deciding which nodes to place on the 1291590Srgrimes * toBeMade queue initially and by Make_Update to screen out USE and 1301590Srgrimes * EXEC nodes. In the latter case, however, any other sort of node 1311590Srgrimes * must be considered out-of-date since at least one of its children 1321590Srgrimes * will have been recreated. 1331590Srgrimes * 1341590Srgrimes * Results: 1358874Srgrimes * TRUE if the node is out of date. FALSE otherwise. 1361590Srgrimes * 1371590Srgrimes * Side Effects: 1381590Srgrimes * The mtime field of the node and the cmtime field of its parents 1391590Srgrimes * will/may be changed. 1401590Srgrimes */ 1411590SrgrimesBoolean 142138232ShartiMake_OODate(GNode *gn) 1431590Srgrimes{ 144144478Sharti Boolean oodate; 145144478Sharti LstNode *ln; 1461590Srgrimes 1471590Srgrimes /* 148144478Sharti * Certain types of targets needn't even be sought as their datedness 149144478Sharti * doesn't depend on their modification time... 1501590Srgrimes */ 151144478Sharti if ((gn->type & (OP_JOIN | OP_USE | OP_EXEC)) == 0) { 152144478Sharti Dir_MTime(gn); 153144478Sharti if (gn->mtime != 0) { 154144478Sharti DEBUGF(MAKE, ("modified %s...", 155144478Sharti Targ_FmtTime(gn->mtime))); 156144478Sharti } else { 157144478Sharti DEBUGF(MAKE, ("non-existent...")); 158144478Sharti } 159144478Sharti } 1605814Sjkh 1615814Sjkh /* 162144478Sharti * A target is remade in one of the following circumstances: 163144478Sharti * its modification time is smaller than that of its youngest child 164144478Sharti * and it would actually be run (has commands or type OP_NOP) 165144478Sharti * it's the object of a force operator 166144478Sharti * it has no children, was on the lhs of an operator and doesn't 167144478Sharti * exist already. 168144478Sharti * 169144478Sharti * Libraries are only considered out-of-date if the archive module says 170144478Sharti * they are. 171144478Sharti * 172144478Sharti * These weird rules are brought to you by Backward-Compatibility and 173144478Sharti * the strange people who wrote 'Make'. 1745814Sjkh */ 175144478Sharti if (gn->type & OP_USE) { 176144478Sharti /* 177144478Sharti * If the node is a USE node it is *never* out of date 178144478Sharti * no matter *what*. 179144478Sharti */ 180144478Sharti DEBUGF(MAKE, (".USE node...")); 181144478Sharti oodate = FALSE; 1825814Sjkh 183144478Sharti } else if (gn->type & OP_LIB) { 184144478Sharti DEBUGF(MAKE, ("library...")); 185144478Sharti 186144478Sharti /* 187144478Sharti * always out of date if no children and :: target 188144478Sharti */ 189144478Sharti oodate = Arch_LibOODate(gn) || 190144478Sharti ((gn->cmtime == 0) && (gn->type & OP_DOUBLEDEP)); 191144478Sharti 192144478Sharti } else if (gn->type & OP_JOIN) { 193144478Sharti /* 194144478Sharti * A target with the .JOIN attribute is only considered 195144478Sharti * out-of-date if any of its children was out-of-date. 196144478Sharti */ 197144478Sharti DEBUGF(MAKE, (".JOIN node...")); 198144478Sharti oodate = gn->childMade; 199144478Sharti 200144478Sharti } else if (gn->type & (OP_FORCE|OP_EXEC|OP_PHONY)) { 201144478Sharti /* 202144478Sharti * A node which is the object of the force (!) operator or 203144478Sharti * which has the .EXEC attribute is always considered 204144478Sharti * out-of-date. 205144478Sharti */ 206144478Sharti if (gn->type & OP_FORCE) { 207144478Sharti DEBUGF(MAKE, ("! operator...")); 208144478Sharti } else if (gn->type & OP_PHONY) { 209144478Sharti DEBUGF(MAKE, (".PHONY node...")); 210144478Sharti } else { 211144478Sharti DEBUGF(MAKE, (".EXEC node...")); 212144478Sharti } 213144478Sharti oodate = TRUE; 214144478Sharti 215144478Sharti } else if ((gn->mtime < gn->cmtime) || 216144478Sharti ((gn->cmtime == 0) && 217144478Sharti ((gn->mtime==0) || (gn->type & OP_DOUBLEDEP)))) { 218144478Sharti /* 219144478Sharti * A node whose modification time is less than that of its 220144478Sharti * youngest child or that has no children (cmtime == 0) and 221144478Sharti * either doesn't exist (mtime == 0) or was the object of a 222144478Sharti * :: operator is out-of-date. Why? Because that's the way 223144478Sharti * Make does it. 224144478Sharti */ 225144478Sharti if (gn->mtime < gn->cmtime) { 226144478Sharti DEBUGF(MAKE, ("modified before source...")); 227144478Sharti } else if (gn->mtime == 0) { 228144478Sharti DEBUGF(MAKE, ("non-existent and no sources...")); 229144478Sharti } else { 230144478Sharti DEBUGF(MAKE, (":: operator and no sources...")); 231144478Sharti } 232144478Sharti oodate = TRUE; 233144478Sharti } else 234144478Sharti oodate = FALSE; 235144478Sharti 2361590Srgrimes /* 237144478Sharti * If the target isn't out-of-date, the parents need to know its 238144478Sharti * modification time. Note that targets that appear to be out-of-date 239144478Sharti * but aren't, because they have no commands and aren't of type OP_NOP, 240144478Sharti * have their mtime stay below their children's mtime to keep parents 241144478Sharti * from thinking they're out-of-date. 2421590Srgrimes */ 243144478Sharti if (!oodate) { 244144478Sharti LST_FOREACH(ln, &gn->parents) 245144478Sharti if (Make_TimeStamp(Lst_Datum(ln), gn)) 246144478Sharti break; 2471590Srgrimes } 2481590Srgrimes 249144478Sharti return (oodate); 2501590Srgrimes} 251138232Sharti 252144478Sharti/** 253144478Sharti * Make_HandleUse 2541590Srgrimes * Function called by Make_Run and SuffApplyTransform on the downward 2551590Srgrimes * pass to handle .USE and transformation nodes. A callback function 256143694Sharti * for LST_FOREACH, it implements the .USE and transformation 2571590Srgrimes * functionality by copying the node's commands, type flags 2581590Srgrimes * and children to the parent node. Should be called before the 259143694Sharti * children are enqueued to be looked at. 2601590Srgrimes * 2611590Srgrimes * A .USE node is much like an explicit transformation rule, except 2621590Srgrimes * its commands are always added to the target node, even if the 2631590Srgrimes * target already has commands. 2641590Srgrimes * 2651590Srgrimes * Results: 2661590Srgrimes * returns 0. 2671590Srgrimes * 2681590Srgrimes * Side Effects: 2691590Srgrimes * Children and commands may be added to the parent and the parent's 2701590Srgrimes * type may be changed. 2711590Srgrimes * 2721590Srgrimes *----------------------------------------------------------------------- 2731590Srgrimes */ 2741590Srgrimesint 275138232ShartiMake_HandleUse(GNode *cgn, GNode *pgn) 2761590Srgrimes{ 277144478Sharti GNode *gn; /* A child of the .USE node */ 278144478Sharti LstNode *ln; /* An element in the children list */ 2791590Srgrimes 280144478Sharti if (cgn->type & (OP_USE | OP_TRANSFORM)) { 281144478Sharti if ((cgn->type & OP_USE) || Lst_IsEmpty(&pgn->commands)) { 282144478Sharti /* 283144478Sharti * .USE or transformation and target has no commands -- 284144478Sharti * append the child's commands to the parent. 285144478Sharti */ 286144478Sharti Lst_Concat(&pgn->commands, &cgn->commands, LST_CONCNEW); 287144478Sharti } 2888874Srgrimes 289144478Sharti for (ln = Lst_First(&cgn->children); ln != NULL; 290144478Sharti ln = Lst_Succ(ln)) { 291144478Sharti gn = Lst_Datum(ln); 2921590Srgrimes 293144478Sharti if (Lst_Member(&pgn->children, gn) == NULL) { 294144478Sharti Lst_AtEnd(&pgn->children, gn); 295144478Sharti Lst_AtEnd(&gn->parents, pgn); 296144478Sharti pgn->unmade += 1; 297144478Sharti } 298144478Sharti } 2998874Srgrimes 300144478Sharti pgn->type |= cgn->type & ~(OP_OPMASK | OP_USE | OP_TRANSFORM); 3011590Srgrimes 302144478Sharti /* 303144478Sharti * This child node is now "made", so we decrement the count of 304144478Sharti * unmade children in the parent... We also remove the child 305144478Sharti * from the parent's list to accurately reflect the number of 306144478Sharti * decent children the parent has. This is used by Make_Run to 307144478Sharti * decide whether to queue the parent or examine its children... 308144478Sharti */ 309144478Sharti if (cgn->type & OP_USE) { 310144478Sharti pgn->unmade--; 311144478Sharti } 3121590Srgrimes } 313144478Sharti return (0); 3141590Srgrimes} 315138232Sharti 316144478Sharti/** 317144478Sharti * Make_Update 3181590Srgrimes * Perform update on the parents of a node. Used by JobFinish once 3191590Srgrimes * a node has been dealt with and by MakeStartJobs if it finds an 3208874Srgrimes * up-to-date node. 3211590Srgrimes * 3221590Srgrimes * Results: 3231590Srgrimes * Always returns 0 3241590Srgrimes * 3251590Srgrimes * Side Effects: 3261590Srgrimes * The unmade field of pgn is decremented and pgn may be placed on 3271590Srgrimes * the toBeMade queue if this field becomes 0. 3281590Srgrimes * 3291590Srgrimes * If the child was made, the parent's childMade field will be set true 3301590Srgrimes * and its cmtime set to now. 3311590Srgrimes * 3321590Srgrimes * If the child wasn't made, the cmtime field of the parent will be 3331590Srgrimes * altered if the child's mtime is big enough. 3341590Srgrimes * 3351590Srgrimes * Finally, if the child is the implied source for the parent, the 3361590Srgrimes * parent's IMPSRC variable is set appropriately. 3371590Srgrimes */ 3381590Srgrimesvoid 339138232ShartiMake_Update(GNode *cgn) 3401590Srgrimes{ 341144478Sharti GNode *pgn; /* the parent node */ 342144478Sharti char *cname; /* the child's name */ 343144478Sharti LstNode *ln; /* Element in parents and iParents lists */ 344144478Sharti char *cpref; 3451590Srgrimes 346146580Sharti cname = Var_Value(TARGET, cgn); 3471590Srgrimes 3481590Srgrimes /* 349144478Sharti * If the child was actually made, see what its modification time is 350144478Sharti * now -- some rules won't actually update the file. If the file still 351144478Sharti * doesn't exist, make its mtime now. 3521590Srgrimes */ 353144478Sharti if (cgn->made != UPTODATE) { 354144478Sharti#ifndef RECHECK 355144478Sharti /* 356144478Sharti * We can't re-stat the thing, but we can at least take care 357144478Sharti * of rules where a target depends on a source that actually 358144478Sharti * creates the target, but only if it has changed, e.g. 359144478Sharti * 360144478Sharti * parse.h : parse.o 361144478Sharti * 362144478Sharti * parse.o : parse.y 363144478Sharti * yacc -d parse.y 364144478Sharti * cc -c y.tab.c 365144478Sharti * mv y.tab.o parse.o 366144478Sharti * cmp -s y.tab.h parse.h || mv y.tab.h parse.h 367144478Sharti * 368144478Sharti * In this case, if the definitions produced by yacc haven't 369144478Sharti * changed from before, parse.h won't have been updated and 370144478Sharti * cgn->mtime will reflect the current modification time for 371144478Sharti * parse.h. This is something of a kludge, I admit, but it's a 372144478Sharti * useful one.. 373144478Sharti * XXX: People like to use a rule like 374144478Sharti * 375144478Sharti * FRC: 376144478Sharti * 377144478Sharti * To force things that depend on FRC to be made, so we have to 378144478Sharti * check for gn->children being empty as well... 379144478Sharti */ 380144478Sharti if (!Lst_IsEmpty(&cgn->commands) || 381144478Sharti Lst_IsEmpty(&cgn->children)) { 382144478Sharti cgn->mtime = now; 383144478Sharti } 384144478Sharti #else 385144478Sharti /* 386144478Sharti * This is what Make does and it's actually a good thing, as it 387144478Sharti * allows rules like 388144478Sharti * 389144478Sharti * cmp -s y.tab.h parse.h || cp y.tab.h parse.h 390144478Sharti * 391144478Sharti * to function as intended. Unfortunately, thanks to the 392144478Sharti * stateless nature of NFS (by which I mean the loose coupling 393144478Sharti * of two clients using the same file from a common server), 394144478Sharti * there are times when the modification time of a file created 395144478Sharti * on a remote machine will not be modified before the local 396144478Sharti * stat() implied by the Dir_MTime occurs, thus leading us to 397144478Sharti * believe that the file is unchanged, wreaking havoc with 398144478Sharti * files that depend on this one. 399144478Sharti * 400144478Sharti * I have decided it is better to make too much than to make too 401144478Sharti * little, so this stuff is commented out unless you're sure 402144478Sharti * it's ok. 403144478Sharti * -- ardeb 1/12/88 404144478Sharti */ 405144478Sharti /* 406144478Sharti * Christos, 4/9/92: If we are saving commands pretend that 407144478Sharti * the target is made now. Otherwise archives with ... rules 408144478Sharti * don't work! 409144478Sharti */ 410144478Sharti if (noExecute || (cgn->type & OP_SAVE_CMDS) || 411144478Sharti Dir_MTime(cgn) == 0) { 412144478Sharti cgn->mtime = now; 413144478Sharti } 414144478Sharti DEBUGF(MAKE, ("update time: %s\n", Targ_FmtTime(cgn->mtime))); 415144478Sharti#endif 4161590Srgrimes } 4178874Srgrimes 418144478Sharti for (ln = Lst_First(&cgn->parents); ln != NULL; ln = Lst_Succ(ln)) { 419144478Sharti pgn = Lst_Datum(ln); 420144478Sharti if (pgn->make) { 421144478Sharti pgn->unmade -= 1; 4221590Srgrimes 423144478Sharti if (!(cgn->type & (OP_EXEC | OP_USE))) { 424144478Sharti if (cgn->made == MADE) { 425144478Sharti pgn->childMade = TRUE; 426144478Sharti if (pgn->cmtime < cgn->mtime) { 427144478Sharti pgn->cmtime = cgn->mtime; 428144478Sharti } 429144478Sharti } else { 430144478Sharti Make_TimeStamp(pgn, cgn); 431144478Sharti } 432144478Sharti } 433144478Sharti if (pgn->unmade == 0) { 434144478Sharti /* 435144478Sharti * Queue the node up -- any unmade predecessors 436144478Sharti * will be dealt with in MakeStartJobs. 437144478Sharti */ 438144478Sharti Lst_EnQueue(&toBeMade, pgn); 439144478Sharti } else if (pgn->unmade < 0) { 440144478Sharti Error("Graph cycles through %s", pgn->name); 441144478Sharti } 4421590Srgrimes } 4431590Srgrimes } 444138564Sharti 445144478Sharti /* 446144478Sharti * Deal with successor nodes. If any is marked for making and has an 447144478Sharti * unmade count of 0, has not been made and isn't in the examination 448144478Sharti * queue, it means we need to place it in the queue as it restrained 449144478Sharti * itself before. 450144478Sharti */ 451144478Sharti for (ln = Lst_First(&cgn->successors); ln != NULL; ln = Lst_Succ(ln)) { 452144478Sharti GNode *succ = Lst_Datum(ln); 4531590Srgrimes 454144478Sharti if (succ->make && succ->unmade == 0 && succ->made == UNMADE && 455144478Sharti Lst_Member(&toBeMade, succ) == NULL) { 456144478Sharti Lst_EnQueue(&toBeMade, succ); 457144478Sharti } 4581590Srgrimes } 4598874Srgrimes 460144478Sharti /* 461144478Sharti * Set the .PREFIX and .IMPSRC variables for all the implied parents 462144478Sharti * of this node. 463144478Sharti */ 464146580Sharti cpref = Var_Value(PREFIX, cgn); 465144478Sharti for (ln = Lst_First(&cgn->iParents); ln != NULL; ln = Lst_Succ(ln)) { 466144478Sharti pgn = Lst_Datum(ln); 467144478Sharti if (pgn->make) { 468144478Sharti Var_Set(IMPSRC, cname, pgn); 469144478Sharti Var_Set(PREFIX, cpref, pgn); 470144478Sharti } 4711590Srgrimes } 4721590Srgrimes} 473138232Sharti 474144478Sharti/** 475144478Sharti * Make_DoAllVar 4761590Srgrimes * Set up the ALLSRC and OODATE variables. Sad to say, it must be 4771590Srgrimes * done separately, rather than while traversing the graph. This is 4781590Srgrimes * because Make defined OODATE to contain all sources whose modification 4791590Srgrimes * times were later than that of the target, *not* those sources that 4801590Srgrimes * were out-of-date. Since in both compatibility and native modes, 4811590Srgrimes * the modification time of the parent isn't found until the child 4821590Srgrimes * has been dealt with, we have to wait until now to fill in the 4831590Srgrimes * variable. As for ALLSRC, the ordering is important and not 4841590Srgrimes * guaranteed when in native mode, so it must be set here, too. 4851590Srgrimes * 4861590Srgrimes * Side Effects: 4871590Srgrimes * The ALLSRC and OODATE variables of the given node is filled in. 4881590Srgrimes * If the node is a .JOIN node, its TARGET variable will be set to 4891590Srgrimes * match its ALLSRC variable. 4901590Srgrimes */ 4911590Srgrimesvoid 492138232ShartiMake_DoAllVar(GNode *gn) 4931590Srgrimes{ 494143694Sharti LstNode *ln; 495143694Sharti GNode *cgn; 496143694Sharti char *child; 4971590Srgrimes 498143694Sharti LST_FOREACH(ln, &gn->children) { 499143694Sharti /* 500143694Sharti * Add the child's name to the ALLSRC and OODATE variables of 501143694Sharti * the given node. The child is added only if it has not been 502143694Sharti * given the .EXEC, .USE or .INVISIBLE attributes. .EXEC and 503143694Sharti * .USE children are very rarely going to be files, so... 504143694Sharti * 505143694Sharti * A child is added to the OODATE variable if its modification 506143694Sharti * time is later than that of its parent, as defined by Make, 507143694Sharti * except if the parent is a .JOIN node. In that case, it is 508143694Sharti * only added to the OODATE variable if it was actually made 509143694Sharti * (since .JOIN nodes don't have modification times, the 510143694Sharti * comparison is rather unfair...). 511143694Sharti */ 512143694Sharti cgn = Lst_Datum(ln); 513138232Sharti 514143694Sharti if ((cgn->type & (OP_EXEC | OP_USE | OP_INVISIBLE)) == 0) { 515143694Sharti if (OP_NOP(cgn->type)) { 516143694Sharti /* 517143694Sharti * this node is only source; use the specific 518143694Sharti * pathname for it 519143694Sharti */ 520143694Sharti child = cgn->path ? cgn->path : cgn->name; 521143694Sharti } else 522146580Sharti child = Var_Value(TARGET, cgn); 523143694Sharti Var_Append(ALLSRC, child, gn); 524143694Sharti if (gn->type & OP_JOIN) { 525143694Sharti if (cgn->made == MADE) { 526143694Sharti Var_Append(OODATE, child, gn); 527143694Sharti } 528143694Sharti } else if (gn->mtime < cgn->mtime || 529143694Sharti (cgn->mtime >= now && cgn->made == MADE)) { 530143694Sharti /* 531143694Sharti * It goes in the OODATE variable if the parent 532143694Sharti * is younger than the child or if the child has 533143694Sharti * been modified more recently than the start of 534143694Sharti * the make. This is to keep pmake from getting 535143694Sharti * confused if something else updates the parent 536143694Sharti * after the make starts (shouldn't happen, I 537143694Sharti * know, but sometimes it does). In such a case, 538143694Sharti * if we've updated the kid, the parent is 539143694Sharti * likely to have a modification time later than 540143694Sharti * that of the kid and anything that relies on 541143694Sharti * the OODATE variable will be hosed. 542143694Sharti * 543143694Sharti * XXX: This will cause all made children to 544143694Sharti * go in the OODATE variable, even if they're 545143694Sharti * not touched, if RECHECK isn't defined, since 546143694Sharti * cgn->mtime is set to now in Make_Update. 547143694Sharti * According to some people, this is good... 548143694Sharti */ 549143694Sharti Var_Append(OODATE, child, gn); 550143694Sharti } 551143694Sharti } 552143694Sharti } 5531590Srgrimes 554143694Sharti if (!Var_Exists (OODATE, gn)) { 555143694Sharti Var_Set(OODATE, "", gn); 556143694Sharti } 557143694Sharti if (!Var_Exists (ALLSRC, gn)) { 558143694Sharti Var_Set(ALLSRC, "", gn); 559143694Sharti } 560138232Sharti 561143694Sharti if (gn->type & OP_JOIN) { 562146580Sharti Var_Set(TARGET, Var_Value(ALLSRC, gn), gn); 563143694Sharti } 5641590Srgrimes} 565138232Sharti 566144478Sharti/** 567144478Sharti * MakeStartJobs 5681590Srgrimes * Start as many jobs as possible. 5691590Srgrimes * 5701590Srgrimes * Results: 5711590Srgrimes * If the query flag was given to pmake, no job will be started, 5721590Srgrimes * but as soon as an out-of-date target is found, this function 5731590Srgrimes * returns TRUE. At all other times, this function returns FALSE. 5741590Srgrimes * 5751590Srgrimes * Side Effects: 5761590Srgrimes * Nodes are removed from the toBeMade queue and job table slots 5771590Srgrimes * are filled. 5781590Srgrimes */ 5791590Srgrimesstatic Boolean 580138232ShartiMakeStartJobs(void) 5811590Srgrimes{ 582144478Sharti GNode *gn; 5838874Srgrimes 584144478Sharti while (!Lst_IsEmpty(&toBeMade) && !Job_Full()) { 585144478Sharti gn = Lst_DeQueue(&toBeMade); 586144478Sharti DEBUGF(MAKE, ("Examining %s...", gn->name)); 5871590Srgrimes 588144478Sharti /* 589144478Sharti * Make sure any and all predecessors that are going to be made, 590144478Sharti * have been. 591144478Sharti */ 592144478Sharti if (!Lst_IsEmpty(&gn->preds)) { 593144478Sharti LstNode *ln; 5941590Srgrimes 595144478Sharti for (ln = Lst_First(&gn->preds); ln != NULL; 596144478Sharti ln = Lst_Succ(ln)){ 597144478Sharti GNode *pgn = Lst_Datum(ln); 598144478Sharti 599144478Sharti if (pgn->make && pgn->made == UNMADE) { 600144478Sharti DEBUGF(MAKE, ("predecessor %s not made " 601144478Sharti "yet.\n", pgn->name)); 602144478Sharti break; 603144478Sharti } 604144478Sharti } 605144478Sharti /* 606144478Sharti * If ln isn't NULL, there's a predecessor as yet 607144478Sharti * unmade, so we just drop this node on the floor. 608144478Sharti * When the node in question has been made, it will 609144478Sharti * notice this node as being ready to make but as yet 610144478Sharti * unmade and will place the node on the queue. 611144478Sharti */ 612144478Sharti if (ln != NULL) { 613144478Sharti continue; 614144478Sharti } 6151590Srgrimes } 6168874Srgrimes 617144478Sharti numNodes--; 618144478Sharti if (Make_OODate(gn)) { 619144478Sharti DEBUGF(MAKE, ("out-of-date\n")); 620144478Sharti if (queryFlag) { 621144478Sharti return (TRUE); 622144478Sharti } 623144478Sharti Make_DoAllVar(gn); 624144478Sharti Job_Make(gn); 625144478Sharti } else { 626144478Sharti DEBUGF(MAKE, ("up-to-date\n")); 627144478Sharti gn->made = UPTODATE; 628144478Sharti if (gn->type & OP_JOIN) { 629144478Sharti /* 630144478Sharti * Even for an up-to-date .JOIN node, we need 631144478Sharti * it to have its context variables so 632144478Sharti * references to it get the correct value for 633144478Sharti * .TARGET when building up the context 634144478Sharti * variables of its parent(s)... 635144478Sharti */ 636144478Sharti Make_DoAllVar(gn); 637144478Sharti } 6388874Srgrimes 639144478Sharti Make_Update(gn); 640144478Sharti } 6411590Srgrimes } 642144478Sharti return (FALSE); 6431590Srgrimes} 644138232Sharti 645144478Sharti/** 646144478Sharti * MakePrintStatus 6471590Srgrimes * Print the status of a top-level node, viz. it being up-to-date 6481590Srgrimes * already or not created due to an error in a lower level. 649143694Sharti * Callback function for Make_Run via LST_FOREACH. If gn->unmade is 650104696Sjmallett * nonzero and that is meant to imply a cycle in the graph, then 651104696Sjmallett * cycle is TRUE. 6521590Srgrimes * 6531590Srgrimes * Side Effects: 6541590Srgrimes * A message may be printed. 6551590Srgrimes */ 656143694Shartistatic void 657143694ShartiMakePrintStatus(GNode *gn, Boolean cycle) 6581590Srgrimes{ 659144478Sharti LstNode *ln; 660138232Sharti 661144478Sharti if (gn->made == UPTODATE) { 662144478Sharti printf("`%s' is up to date.\n", gn->name); 663144478Sharti 664144478Sharti } else if (gn->unmade != 0) { 665144478Sharti if (cycle) { 666144478Sharti /* 667144478Sharti * If printing cycles and came to one that has unmade 668144478Sharti * children, print out the cycle by recursing on its 669144478Sharti * children. Note a cycle like: 670144478Sharti * a : b 671144478Sharti * b : c 672144478Sharti * c : b 673144478Sharti * will cause this to erroneously complain about a 674144478Sharti * being in the cycle, but this is a good approximation. 675144478Sharti */ 676144478Sharti if (gn->made == CYCLE) { 677144478Sharti Error("Graph cycles through `%s'", gn->name); 678144478Sharti gn->made = ENDCYCLE; 679144478Sharti LST_FOREACH(ln, &gn->children) 680144478Sharti MakePrintStatus(Lst_Datum(ln), TRUE); 681144478Sharti gn->made = UNMADE; 682144478Sharti } else if (gn->made != ENDCYCLE) { 683144478Sharti gn->made = CYCLE; 684144478Sharti LST_FOREACH(ln, &gn->children) 685144478Sharti MakePrintStatus(Lst_Datum(ln), TRUE); 686144478Sharti } 687144478Sharti } else { 688144478Sharti printf("`%s' not remade because of errors.\n", 689144478Sharti gn->name); 690144478Sharti } 6911590Srgrimes } 6921590Srgrimes} 693138232Sharti 694144478Sharti/** 695144478Sharti * Make_Run 6961590Srgrimes * Initialize the nodes to remake and the list of nodes which are 6971590Srgrimes * ready to be made by doing a breadth-first traversal of the graph 6981590Srgrimes * starting from the nodes in the given list. Once this traversal 6991590Srgrimes * is finished, all the 'leaves' of the graph are in the toBeMade 7001590Srgrimes * queue. 7011590Srgrimes * Using this queue and the Job module, work back up the graph, 7021590Srgrimes * calling on MakeStartJobs to keep the job table as full as 7031590Srgrimes * possible. 7041590Srgrimes * 7051590Srgrimes * Results: 7061590Srgrimes * TRUE if work was done. FALSE otherwise. 7071590Srgrimes * 7081590Srgrimes * Side Effects: 7091590Srgrimes * The make field of all nodes involved in the creation of the given 7101590Srgrimes * targets is set to 1. The toBeMade list is set to contain all the 7111590Srgrimes * 'leaves' of these subgraphs. 7121590Srgrimes */ 7131590SrgrimesBoolean 714138512ShartiMake_Run(Lst *targs) 7151590Srgrimes{ 716144478Sharti GNode *gn; /* a temporary pointer */ 717144478Sharti GNode *cgn; 718144478Sharti Lst examine; /* List of targets to examine */ 719144478Sharti int errors; /* Number of errors the Job module reports */ 720144478Sharti LstNode *ln; 7211590Srgrimes 722144478Sharti Lst_Init(&examine); 723144478Sharti Lst_Duplicate(&examine, targs, NOCOPY); 724144478Sharti numNodes = 0; 7258874Srgrimes 726144478Sharti /* 727144478Sharti * Make an initial downward pass over the graph, marking nodes to be 728144478Sharti * made as we go down. We call Suff_FindDeps to find where a node is and 729144478Sharti * to get some children for it if it has none and also has no commands. 730144478Sharti * If the node is a leaf, we stick it on the toBeMade queue to 731144478Sharti * be looked at in a minute, otherwise we add its children to our queue 732144478Sharti * and go on about our business. 733144478Sharti */ 734144478Sharti while (!Lst_IsEmpty(&examine)) { 735144478Sharti gn = Lst_DeQueue(&examine); 7368874Srgrimes 737144478Sharti if (!gn->make) { 738144478Sharti gn->make = TRUE; 739144478Sharti numNodes++; 7408874Srgrimes 741144478Sharti /* 742144478Sharti * Apply any .USE rules before looking for implicit 743144478Sharti * dependencies to make sure everything has commands 744144478Sharti * that should... 745144478Sharti */ 746144478Sharti LST_FOREACH(ln, &gn->children) 747144478Sharti if (Make_HandleUse(Lst_Datum(ln), gn)) 748144478Sharti break; 749143694Sharti 750144478Sharti Suff_FindDeps(gn); 7511590Srgrimes 752144478Sharti if (gn->unmade != 0) { 753144478Sharti LST_FOREACH(ln, &gn->children) { 754144478Sharti cgn = Lst_Datum(ln); 755144478Sharti if (!cgn->make && !(cgn->type & OP_USE)) 756144478Sharti Lst_EnQueue(&examine, cgn); 757144478Sharti } 758144478Sharti } else { 759144478Sharti Lst_EnQueue(&toBeMade, gn); 760144478Sharti } 761143694Sharti } 7621590Srgrimes } 7638874Srgrimes 764144478Sharti if (queryFlag) { 765144478Sharti /* 766144478Sharti * We wouldn't do any work unless we could start some jobs in 767144478Sharti * the next loop... (we won't actually start any, of course, 768144478Sharti * this is just to see if any of the targets was out of date) 769144478Sharti */ 770144478Sharti return (MakeStartJobs()); 771144478Sharti 772144478Sharti } else { 773144478Sharti /* 774144478Sharti * Initialization. At the moment, no jobs are running and 775144478Sharti * until some get started, nothing will happen since the 776144478Sharti * remaining upward traversal of the graph is performed by the 777144478Sharti * routines in job.c upon the finishing of a job. So we fill 778144478Sharti * the Job table as much as we can before going into our loop. 779144478Sharti */ 780144478Sharti MakeStartJobs(); 781144478Sharti } 782144478Sharti 7831590Srgrimes /* 784144478Sharti * Main Loop: The idea here is that the ending of jobs will take 785144478Sharti * care of the maintenance of data structures and the waiting for output 786144478Sharti * will cause us to be idle most of the time while our children run as 787144478Sharti * much as possible. Because the job table is kept as full as possible, 788144478Sharti * the only time when it will be empty is when all the jobs which need 789144478Sharti * running have been run, so that is the end condition of this loop. 790144478Sharti * Note that the Job module will exit if there were any errors unless 791144478Sharti * the keepgoing flag was given. 7921590Srgrimes */ 793144478Sharti while (!Job_Empty()) { 794144478Sharti Job_CatchOutput(!Lst_IsEmpty(&toBeMade)); 795144478Sharti Job_CatchChildren(!usePipes); 796144478Sharti MakeStartJobs(); 797144478Sharti } 798144478Sharti 799144478Sharti errors = Job_Finish(); 800144478Sharti 8011590Srgrimes /* 802144478Sharti * Print the final status of each target. E.g. if it wasn't made 803144478Sharti * because some inferior reported an error. 8041590Srgrimes */ 805144478Sharti errors = ((errors == 0) && (numNodes != 0)); 806144478Sharti LST_FOREACH(ln, targs) 807144478Sharti MakePrintStatus(Lst_Datum(ln), errors); 8081590Srgrimes 809144478Sharti return (TRUE); 8101590Srgrimes} 811