Home | History | Annotate | Line # | Download | only in make
targ.c revision 1.173
      1 /*	$NetBSD: targ.c,v 1.173 2021/11/28 19:51:06 rillig Exp $	*/
      2 
      3 /*
      4  * Copyright (c) 1988, 1989, 1990, 1993
      5  *	The Regents of the University of California.  All rights reserved.
      6  *
      7  * This code is derived from software contributed to Berkeley by
      8  * Adam de Boor.
      9  *
     10  * Redistribution and use in source and binary forms, with or without
     11  * modification, are permitted provided that the following conditions
     12  * are met:
     13  * 1. Redistributions of source code must retain the above copyright
     14  *    notice, this list of conditions and the following disclaimer.
     15  * 2. Redistributions in binary form must reproduce the above copyright
     16  *    notice, this list of conditions and the following disclaimer in the
     17  *    documentation and/or other materials provided with the distribution.
     18  * 3. Neither the name of the University nor the names of its contributors
     19  *    may be used to endorse or promote products derived from this software
     20  *    without specific prior written permission.
     21  *
     22  * THIS SOFTWARE IS PROVIDED BY THE REGENTS AND CONTRIBUTORS ``AS IS'' AND
     23  * ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
     24  * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE
     25  * ARE DISCLAIMED.  IN NO EVENT SHALL THE REGENTS OR CONTRIBUTORS BE LIABLE
     26  * FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL
     27  * DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS
     28  * OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION)
     29  * HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT
     30  * LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY
     31  * OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF
     32  * SUCH DAMAGE.
     33  */
     34 
     35 /*
     36  * Copyright (c) 1989 by Berkeley Softworks
     37  * All rights reserved.
     38  *
     39  * This code is derived from software contributed to Berkeley by
     40  * Adam de Boor.
     41  *
     42  * Redistribution and use in source and binary forms, with or without
     43  * modification, are permitted provided that the following conditions
     44  * are met:
     45  * 1. Redistributions of source code must retain the above copyright
     46  *    notice, this list of conditions and the following disclaimer.
     47  * 2. Redistributions in binary form must reproduce the above copyright
     48  *    notice, this list of conditions and the following disclaimer in the
     49  *    documentation and/or other materials provided with the distribution.
     50  * 3. All advertising materials mentioning features or use of this software
     51  *    must display the following acknowledgement:
     52  *	This product includes software developed by the University of
     53  *	California, Berkeley and its contributors.
     54  * 4. Neither the name of the University nor the names of its contributors
     55  *    may be used to endorse or promote products derived from this software
     56  *    without specific prior written permission.
     57  *
     58  * THIS SOFTWARE IS PROVIDED BY THE REGENTS AND CONTRIBUTORS ``AS IS'' AND
     59  * ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
     60  * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE
     61  * ARE DISCLAIMED.  IN NO EVENT SHALL THE REGENTS OR CONTRIBUTORS BE LIABLE
     62  * FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL
     63  * DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS
     64  * OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION)
     65  * HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT
     66  * LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY
     67  * OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF
     68  * SUCH DAMAGE.
     69  */
     70 
     71 /*
     72  * Maintaining the targets and sources, which are both implemented as GNode.
     73  *
     74  * Interface:
     75  *	Targ_Init	Initialize the module.
     76  *
     77  *	Targ_End	Clean up the module.
     78  *
     79  *	Targ_List	Return the list of all targets so far.
     80  *
     81  *	GNode_New	Create a new GNode for the passed target
     82  *			(string). The node is *not* placed in the
     83  *			hash table, though all its fields are
     84  *			initialized.
     85  *
     86  *	Targ_FindNode	Find the node, or return NULL.
     87  *
     88  *	Targ_GetNode	Find the node, or create it.
     89  *
     90  *	Targ_NewInternalNode
     91  *			Create an internal node.
     92  *
     93  *	Targ_FindList	Given a list of names, find nodes for all
     94  *			of them, creating them as necessary.
     95  *
     96  *	Targ_Precious	Return true if the target is precious and
     97  *			should not be removed if we are interrupted.
     98  *
     99  *	Targ_Propagate	Propagate information between related nodes.
    100  *			Should be called after the makefiles are parsed
    101  *			but before any action is taken.
    102  *
    103  * Debugging:
    104  *	Targ_PrintGraph
    105  *			Print out the entire graph, all variables and
    106  *			statistics for the directory cache. Should print
    107  *			something for suffixes, too, but...
    108  */
    109 
    110 #include <time.h>
    111 
    112 #include "make.h"
    113 #include "dir.h"
    114 
    115 /*	"@(#)targ.c	8.2 (Berkeley) 3/19/94"	*/
    116 MAKE_RCSID("$NetBSD: targ.c,v 1.173 2021/11/28 19:51:06 rillig Exp $");
    117 
    118 /*
    119  * All target nodes that appeared on the left-hand side of one of the
    120  * dependency operators ':', '::', '!'.
    121  */
    122 static GNodeList allTargets = LST_INIT;
    123 static HashTable allTargetsByName;
    124 
    125 #ifdef CLEANUP
    126 static GNodeList allNodes = LST_INIT;
    127 
    128 static void GNode_Free(void *);
    129 #endif
    130 
    131 void
    132 Targ_Init(void)
    133 {
    134 	HashTable_Init(&allTargetsByName);
    135 }
    136 
    137 void
    138 Targ_End(void)
    139 {
    140 	Targ_Stats();
    141 #ifdef CLEANUP
    142 	Lst_Done(&allTargets);
    143 	HashTable_Done(&allTargetsByName);
    144 	Lst_DoneCall(&allNodes, GNode_Free);
    145 #endif
    146 }
    147 
    148 void
    149 Targ_Stats(void)
    150 {
    151 	HashTable_DebugStats(&allTargetsByName, "targets");
    152 }
    153 
    154 /*
    155  * Return the list of all targets, which are all nodes that appear on the
    156  * left-hand side of a dependency declaration such as "target: source".
    157  * The returned list does not contain pure sources.
    158  */
    159 GNodeList *
    160 Targ_List(void)
    161 {
    162 	return &allTargets;
    163 }
    164 
    165 /*
    166  * Create a new graph node, but don't register it anywhere.
    167  *
    168  * Graph nodes that appear on the left-hand side of a dependency line such
    169  * as "target: source" are called targets.  XXX: In some cases (like the
    170  * .ALLTARGETS variable), all nodes are called targets as well, even if they
    171  * never appear on the left-hand side.  This is a mistake.
    172  *
    173  * Typical names for graph nodes are:
    174  *	"src.c" (an ordinary file)
    175  *	"clean" (a .PHONY target)
    176  *	".END" (a special hook target)
    177  *	"-lm" (a library)
    178  *	"libc.a(isspace.o)" (an archive member)
    179  */
    180 GNode *
    181 GNode_New(const char *name)
    182 {
    183 	GNode *gn;
    184 
    185 	gn = bmake_malloc(sizeof *gn);
    186 	gn->name = bmake_strdup(name);
    187 	gn->uname = NULL;
    188 	gn->path = NULL;
    189 	gn->type = name[0] == '-' && name[1] == 'l' ? OP_LIB : OP_NONE;
    190 	memset(&gn->flags, 0, sizeof(gn->flags));
    191 	gn->made = UNMADE;
    192 	gn->unmade = 0;
    193 	gn->mtime = 0;
    194 	gn->youngestChild = NULL;
    195 	Lst_Init(&gn->implicitParents);
    196 	Lst_Init(&gn->parents);
    197 	Lst_Init(&gn->children);
    198 	Lst_Init(&gn->order_pred);
    199 	Lst_Init(&gn->order_succ);
    200 	Lst_Init(&gn->cohorts);
    201 	gn->cohort_num[0] = '\0';
    202 	gn->unmade_cohorts = 0;
    203 	gn->centurion = NULL;
    204 	gn->checked_seqno = 0;
    205 	HashTable_Init(&gn->vars);
    206 	Lst_Init(&gn->commands);
    207 	gn->suffix = NULL;
    208 	gn->fname = NULL;
    209 	gn->lineno = 0;
    210 
    211 #ifdef CLEANUP
    212 	Lst_Append(&allNodes, gn);
    213 #endif
    214 
    215 	return gn;
    216 }
    217 
    218 #ifdef CLEANUP
    219 static void
    220 GNode_Free(void *gnp)
    221 {
    222 	GNode *gn = gnp;
    223 
    224 	free(gn->name);
    225 	free(gn->uname);
    226 	free(gn->path);
    227 
    228 	/* Don't free gn->youngestChild since it is not owned by this node. */
    229 
    230 	/*
    231 	 * In the following lists, only free the list nodes, but not the
    232 	 * GNodes in them since these are not owned by this node.
    233 	 */
    234 	Lst_Done(&gn->implicitParents);
    235 	Lst_Done(&gn->parents);
    236 	Lst_Done(&gn->children);
    237 	Lst_Done(&gn->order_pred);
    238 	Lst_Done(&gn->order_succ);
    239 	Lst_Done(&gn->cohorts);
    240 
    241 	/*
    242 	 * Do not free the variables themselves, even though they are owned
    243 	 * by this node.
    244 	 *
    245 	 * XXX: For the nodes that represent targets or sources (and not
    246 	 * SCOPE_GLOBAL), it should be safe to free the variables as well,
    247 	 * since each node manages the memory for all its variables itself.
    248 	 *
    249 	 * XXX: The GNodes that are only used as variable scopes (SCOPE_CMD,
    250 	 * SCOPE_GLOBAL, SCOPE_INTERNAL) are not freed at all (see Var_End,
    251 	 * where they are not mentioned).  These might be freed at all, if
    252 	 * their variable values are indeed not used anywhere else (see
    253 	 * Trace_Init for the only suspicious use).
    254 	 */
    255 	HashTable_Done(&gn->vars);
    256 
    257 	/*
    258 	 * Do not free the commands themselves, as they may be shared with
    259 	 * other nodes.
    260 	 */
    261 	Lst_Done(&gn->commands);
    262 
    263 	/*
    264 	 * gn->suffix is not owned by this node.
    265 	 *
    266 	 * XXX: gn->suffix should be unreferenced here.  This requires a
    267 	 * thorough check that the reference counting is done correctly in
    268 	 * all places, otherwise a suffix might be freed too early.
    269 	 */
    270 
    271 	free(gn);
    272 }
    273 #endif
    274 
    275 /* Get the existing global node, or return NULL. */
    276 GNode *
    277 Targ_FindNode(const char *name)
    278 {
    279 	return HashTable_FindValue(&allTargetsByName, name);
    280 }
    281 
    282 /* Get the existing global node, or create it. */
    283 GNode *
    284 Targ_GetNode(const char *name)
    285 {
    286 	bool isNew;
    287 	HashEntry *he = HashTable_CreateEntry(&allTargetsByName, name, &isNew);
    288 	if (!isNew)
    289 		return HashEntry_Get(he);
    290 
    291 	{
    292 		GNode *gn = Targ_NewInternalNode(name);
    293 		HashEntry_Set(he, gn);
    294 		return gn;
    295 	}
    296 }
    297 
    298 /*
    299  * Create a node, register it in .ALLTARGETS but don't store it in the
    300  * table of global nodes.  This means it cannot be found by name.
    301  *
    302  * This is used for internal nodes, such as cohorts or .WAIT nodes.
    303  */
    304 GNode *
    305 Targ_NewInternalNode(const char *name)
    306 {
    307 	GNode *gn = GNode_New(name);
    308 	Global_Append(".ALLTARGETS", name);
    309 	Lst_Append(&allTargets, gn);
    310 	DEBUG1(TARG, "Adding \"%s\" to all targets.\n", gn->name);
    311 	if (doing_depend)
    312 		gn->flags.fromDepend = true;
    313 	return gn;
    314 }
    315 
    316 /*
    317  * Return the .END node, which contains the commands to be run when
    318  * everything else has been made.
    319  */
    320 GNode *
    321 Targ_GetEndNode(void)
    322 {
    323 	/*
    324 	 * Save the node locally to avoid having to search for it all
    325 	 * the time.
    326 	 */
    327 	static GNode *endNode = NULL;
    328 
    329 	if (endNode == NULL) {
    330 		endNode = Targ_GetNode(".END");
    331 		endNode->type = OP_SPECIAL;
    332 	}
    333 	return endNode;
    334 }
    335 
    336 /* Add the named nodes to the list, creating them as necessary. */
    337 void
    338 Targ_FindList(GNodeList *gns, StringList *names)
    339 {
    340 	StringListNode *ln;
    341 
    342 	for (ln = names->first; ln != NULL; ln = ln->next) {
    343 		const char *name = ln->datum;
    344 		GNode *gn = Targ_GetNode(name);
    345 		Lst_Append(gns, gn);
    346 	}
    347 }
    348 
    349 /* See if the given target is precious. */
    350 bool
    351 Targ_Precious(const GNode *gn)
    352 {
    353 	/* XXX: Why are '::' targets precious? */
    354 	return allPrecious || gn->type & (OP_PRECIOUS | OP_DOUBLEDEP);
    355 }
    356 
    357 /*
    358  * The main target to be made; only for debugging output.
    359  * See mainNode in parse.c for the definitive source.
    360  */
    361 static GNode *mainTarg;
    362 
    363 /* Remember the main target to make; only used for debugging. */
    364 void
    365 Targ_SetMain(GNode *gn)
    366 {
    367 	mainTarg = gn;
    368 }
    369 
    370 static void
    371 PrintNodeNames(GNodeList *gnodes)
    372 {
    373 	GNodeListNode *ln;
    374 
    375 	for (ln = gnodes->first; ln != NULL; ln = ln->next) {
    376 		GNode *gn = ln->datum;
    377 		debug_printf(" %s%s", gn->name, gn->cohort_num);
    378 	}
    379 }
    380 
    381 static void
    382 PrintNodeNamesLine(const char *label, GNodeList *gnodes)
    383 {
    384 	if (Lst_IsEmpty(gnodes))
    385 		return;
    386 	debug_printf("# %s:", label);
    387 	PrintNodeNames(gnodes);
    388 	debug_printf("\n");
    389 }
    390 
    391 void
    392 Targ_PrintCmds(GNode *gn)
    393 {
    394 	StringListNode *ln;
    395 
    396 	for (ln = gn->commands.first; ln != NULL; ln = ln->next) {
    397 		const char *cmd = ln->datum;
    398 		debug_printf("\t%s\n", cmd);
    399 	}
    400 }
    401 
    402 /*
    403  * Format a modification time in some reasonable way and return it.
    404  * The formatted time is placed in a static area, so it is overwritten
    405  * with each call.
    406  */
    407 const char *
    408 Targ_FmtTime(time_t tm)
    409 {
    410 	static char buf[128];
    411 
    412 	struct tm *parts = localtime(&tm);
    413 	(void)strftime(buf, sizeof buf, "%H:%M:%S %b %d, %Y", parts);
    414 	return buf;
    415 }
    416 
    417 /* Print out a type field giving only those attributes the user can set. */
    418 void
    419 Targ_PrintType(GNodeType type)
    420 {
    421 	static const struct {
    422 		GNodeType bit;
    423 		bool internal;
    424 		const char name[10];
    425 	} names[] = {
    426 		{ OP_MEMBER,	true,	"MEMBER"	},
    427 		{ OP_LIB,	true,	"LIB"		},
    428 		{ OP_ARCHV,	true,	"ARCHV"		},
    429 		{ OP_PHONY,	true,	"PHONY"		},
    430 		{ OP_NOTMAIN,	false,	"NOTMAIN"	},
    431 		{ OP_INVISIBLE,	false,	"INVISIBLE"	},
    432 		{ OP_MADE,	true,	"MADE"		},
    433 		{ OP_JOIN,	false,	"JOIN"		},
    434 		{ OP_MAKE,	false,	"MAKE"		},
    435 		{ OP_SILENT,	false,	"SILENT"	},
    436 		{ OP_PRECIOUS,	false,	"PRECIOUS"	},
    437 		{ OP_IGNORE,	false,	"IGNORE"	},
    438 		{ OP_EXEC,	false,	"EXEC"		},
    439 		{ OP_USE,	false,	"USE"		},
    440 		{ OP_OPTIONAL,	false,	"OPTIONAL"	},
    441 	};
    442 	size_t i;
    443 
    444 	for (i = 0; i < sizeof(names) / sizeof(names[0]); i++) {
    445 		if (type & names[i].bit) {
    446 			if (names[i].internal)
    447 				DEBUG1(TARG, " .%s", names[i].name);
    448 			else
    449 				debug_printf(" .%s", names[i].name);
    450 		}
    451 	}
    452 }
    453 
    454 const char *
    455 GNodeMade_Name(GNodeMade made)
    456 {
    457 	switch (made) {
    458 	case UNMADE:    return "unmade";
    459 	case DEFERRED:  return "deferred";
    460 	case REQUESTED: return "requested";
    461 	case BEINGMADE: return "being made";
    462 	case MADE:      return "made";
    463 	case UPTODATE:  return "up-to-date";
    464 	case ERROR:     return "error when made";
    465 	case ABORTED:   return "aborted";
    466 	default:        return "unknown enum_made value";
    467 	}
    468 }
    469 
    470 static const char *
    471 GNode_OpName(const GNode *gn)
    472 {
    473 	switch (gn->type & OP_OPMASK) {
    474 	case OP_DEPENDS:
    475 		return ":";
    476 	case OP_FORCE:
    477 		return "!";
    478 	case OP_DOUBLEDEP:
    479 		return "::";
    480 	}
    481 	return "";
    482 }
    483 
    484 static bool
    485 GNodeFlags_IsNone(GNodeFlags flags)
    486 {
    487 	return !flags.remake
    488 	       && !flags.childMade
    489 	       && !flags.force
    490 	       && !flags.doneWait
    491 	       && !flags.doneOrder
    492 	       && !flags.fromDepend
    493 	       && !flags.doneAllsrc
    494 	       && !flags.cycle
    495 	       && !flags.doneCycle;
    496 }
    497 
    498 /* Print the contents of a node. */
    499 void
    500 Targ_PrintNode(GNode *gn, int pass)
    501 {
    502 	debug_printf("# %s%s", gn->name, gn->cohort_num);
    503 	GNode_FprintDetails(opts.debug_file, ", ", gn, "\n");
    504 	if (GNodeFlags_IsNone(gn->flags))
    505 		return;
    506 
    507 	if (!GNode_IsTarget(gn))
    508 		return;
    509 
    510 	debug_printf("#\n");
    511 	if (gn == mainTarg)
    512 		debug_printf("# *** MAIN TARGET ***\n");
    513 
    514 	if (pass >= 2) {
    515 		if (gn->unmade > 0)
    516 			debug_printf("# %d unmade children\n", gn->unmade);
    517 		else
    518 			debug_printf("# No unmade children\n");
    519 		if (!(gn->type & (OP_JOIN | OP_USE | OP_USEBEFORE | OP_EXEC))) {
    520 			if (gn->mtime != 0) {
    521 				debug_printf("# last modified %s: %s\n",
    522 				    Targ_FmtTime(gn->mtime),
    523 				    GNodeMade_Name(gn->made));
    524 			} else if (gn->made != UNMADE) {
    525 				debug_printf("# nonexistent (maybe): %s\n",
    526 				    GNodeMade_Name(gn->made));
    527 			} else
    528 				debug_printf("# unmade\n");
    529 		}
    530 		PrintNodeNamesLine("implicit parents", &gn->implicitParents);
    531 	} else {
    532 		if (gn->unmade != 0)
    533 			debug_printf("# %d unmade children\n", gn->unmade);
    534 	}
    535 
    536 	PrintNodeNamesLine("parents", &gn->parents);
    537 	PrintNodeNamesLine("order_pred", &gn->order_pred);
    538 	PrintNodeNamesLine("order_succ", &gn->order_succ);
    539 
    540 	debug_printf("%-16s%s", gn->name, GNode_OpName(gn));
    541 	Targ_PrintType(gn->type);
    542 	PrintNodeNames(&gn->children);
    543 	debug_printf("\n");
    544 	Targ_PrintCmds(gn);
    545 	debug_printf("\n\n");
    546 	if (gn->type & OP_DOUBLEDEP)
    547 		Targ_PrintNodes(&gn->cohorts, pass);
    548 }
    549 
    550 void
    551 Targ_PrintNodes(GNodeList *gnodes, int pass)
    552 {
    553 	GNodeListNode *ln;
    554 
    555 	for (ln = gnodes->first; ln != NULL; ln = ln->next)
    556 		Targ_PrintNode(ln->datum, pass);
    557 }
    558 
    559 /* Print only those targets that are just a source. */
    560 static void
    561 PrintOnlySources(void)
    562 {
    563 	GNodeListNode *ln;
    564 
    565 	for (ln = allTargets.first; ln != NULL; ln = ln->next) {
    566 		GNode *gn = ln->datum;
    567 		if (GNode_IsTarget(gn))
    568 			continue;
    569 
    570 		debug_printf("#\t%s [%s]", gn->name, GNode_Path(gn));
    571 		Targ_PrintType(gn->type);
    572 		debug_printf("\n");
    573 	}
    574 }
    575 
    576 /*
    577  * Input:
    578  *	pass		1 => before processing
    579  *			2 => after processing
    580  *			3 => after processing, an error occurred
    581  */
    582 void
    583 Targ_PrintGraph(int pass)
    584 {
    585 	debug_printf("#*** Input graph:\n");
    586 	Targ_PrintNodes(&allTargets, pass);
    587 	debug_printf("\n");
    588 	debug_printf("\n");
    589 
    590 	debug_printf("#\n");
    591 	debug_printf("#   Files that are only sources:\n");
    592 	PrintOnlySources();
    593 
    594 	debug_printf("#*** Global Variables:\n");
    595 	Var_Dump(SCOPE_GLOBAL);
    596 
    597 	debug_printf("#*** Command-line Variables:\n");
    598 	Var_Dump(SCOPE_CMDLINE);
    599 
    600 	debug_printf("\n");
    601 	Dir_PrintDirectories();
    602 	debug_printf("\n");
    603 
    604 	Suff_PrintAll();
    605 }
    606 
    607 /*
    608  * Propagate some type information to cohort nodes (those from the '::'
    609  * dependency operator).
    610  *
    611  * Should be called after the makefiles are parsed but before any action is
    612  * taken.
    613  */
    614 void
    615 Targ_Propagate(void)
    616 {
    617 	GNodeListNode *ln, *cln;
    618 
    619 	for (ln = allTargets.first; ln != NULL; ln = ln->next) {
    620 		GNode *gn = ln->datum;
    621 		GNodeType type = gn->type;
    622 
    623 		if (!(type & OP_DOUBLEDEP))
    624 			continue;
    625 
    626 		for (cln = gn->cohorts.first; cln != NULL; cln = cln->next) {
    627 			GNode *cohort = cln->datum;
    628 
    629 			cohort->type |= type & ~OP_OPMASK;
    630 		}
    631 	}
    632 }
    633