1 /* $NetBSD: targ.c,v 1.181 2024/04/27 17:33:47 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 with the given name, don't add it 82 * to allNodes. 83 * 84 * Targ_FindNode Find the node, or return NULL. 85 * 86 * Targ_GetNode Find the node, or create it. 87 * 88 * Targ_NewInternalNode 89 * Create an internal node. 90 * 91 * Targ_FindList Given a list of names, find nodes for all 92 * of them, creating them as necessary. 93 * 94 * Targ_Propagate Propagate information between related nodes. 95 * Should be called after the makefiles are parsed 96 * but before any action is taken. 97 * 98 * Debugging: 99 * Targ_PrintGraph 100 * Print out the entire graph, all variables and 101 * statistics for the directory cache. 102 */ 103 104 #include <time.h> 105 106 #include "make.h" 107 #include "dir.h" 108 109 /* "@(#)targ.c 8.2 (Berkeley) 3/19/94" */ 110 MAKE_RCSID("$NetBSD: targ.c,v 1.181 2024/04/27 17:33:47 rillig Exp $"); 111 112 /* 113 * All target nodes that appeared on the left-hand side of one of the 114 * dependency operators ':', '::', '!'. 115 */ 116 static GNodeList allTargets = LST_INIT; 117 static HashTable allTargetsByName; 118 119 #ifdef CLEANUP 120 static GNodeList allNodes = LST_INIT; 121 122 static void GNode_Free(GNode *); 123 #endif 124 125 void 126 Targ_Init(void) 127 { 128 HashTable_Init(&allTargetsByName); 129 } 130 131 void 132 Targ_End(void) 133 { 134 #ifdef CLEANUP 135 GNodeListNode *ln; 136 #endif 137 Targ_Stats(); 138 #ifdef CLEANUP 139 Lst_Done(&allTargets); 140 HashTable_Done(&allTargetsByName); 141 for (ln = allNodes.first; ln != NULL; ln = ln->next) 142 GNode_Free(ln->datum); 143 Lst_Done(&allNodes); 144 #endif 145 } 146 147 void 148 Targ_Stats(void) 149 { 150 HashTable_DebugStats(&allTargetsByName, "targets"); 151 } 152 153 /* 154 * Return the list of all targets, which are all nodes that appear on the 155 * left-hand side of a dependency declaration such as "target: source". 156 * The returned list does not contain pure sources. 157 */ 158 GNodeList * 159 Targ_List(void) 160 { 161 return &allTargets; 162 } 163 164 /* 165 * Create a new graph node, but don't register it anywhere. 166 * 167 * Graph nodes that occur on the left-hand side of a dependency line such 168 * as "target: source" are called targets. XXX: In some cases (like the 169 * .ALLTARGETS variable), other nodes are called targets as well, even if 170 * they never occur on the left-hand side of a dependency line. 171 * 172 * Typical names for graph nodes are: 173 * "src.c" an ordinary file 174 * "clean" a .PHONY target 175 * ".END" a special hook target 176 * "-lm" a library 177 * "libm.a(sin.o)" an archive member 178 */ 179 GNode * 180 GNode_New(const char *name) 181 { 182 GNode *gn; 183 184 gn = bmake_malloc(sizeof *gn); 185 gn->name = bmake_strdup(name); 186 gn->uname = NULL; 187 gn->path = NULL; 188 gn->type = name[0] == '-' && name[1] == 'l' ? OP_LIB : OP_NONE; 189 memset(&gn->flags, 0, sizeof(gn->flags)); 190 gn->made = UNMADE; 191 gn->unmade = 0; 192 gn->mtime = 0; 193 gn->youngestChild = NULL; 194 Lst_Init(&gn->implicitParents); 195 Lst_Init(&gn->parents); 196 Lst_Init(&gn->children); 197 Lst_Init(&gn->order_pred); 198 Lst_Init(&gn->order_succ); 199 Lst_Init(&gn->cohorts); 200 gn->cohort_num[0] = '\0'; 201 gn->unmade_cohorts = 0; 202 gn->centurion = NULL; 203 gn->checked_seqno = 0; 204 HashTable_Init(&gn->vars); 205 Lst_Init(&gn->commands); 206 gn->suffix = NULL; 207 gn->fname = NULL; 208 gn->lineno = 0; 209 gn->exit_status = 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(GNode *gn) 221 { 222 free(gn->name); 223 free(gn->uname); 224 free(gn->path); 225 226 /* Don't free gn->youngestChild since it is not owned by this node. */ 227 228 /* 229 * In the following lists, only free the list nodes, but not the 230 * GNodes in them since these are not owned by this node. 231 */ 232 Lst_Done(&gn->implicitParents); 233 Lst_Done(&gn->parents); 234 Lst_Done(&gn->children); 235 Lst_Done(&gn->order_pred); 236 Lst_Done(&gn->order_succ); 237 Lst_Done(&gn->cohorts); 238 239 /* 240 * Do not free the variables themselves, even though they are owned 241 * by this node. 242 * 243 * XXX: For the nodes that represent targets or sources (and not 244 * SCOPE_GLOBAL), it should be safe to free the variables as well, 245 * since each node manages the memory for all its variables itself. 246 * 247 * XXX: The GNodes that are only used as variable scopes (SCOPE_CMD, 248 * SCOPE_GLOBAL, SCOPE_INTERNAL) are not freed at all (see Var_End, 249 * where they are not mentioned). These may be freed if their 250 * variable values are indeed not used anywhere else (see Trace_Init 251 * for the only suspicious use). 252 */ 253 HashTable_Done(&gn->vars); 254 255 /* 256 * Do not free the commands themselves, as they may be shared with 257 * other nodes. 258 */ 259 Lst_Done(&gn->commands); 260 261 /* 262 * gn->suffix is not owned by this node. 263 * 264 * XXX: gn->suffix should be unreferenced here. This requires a 265 * thorough check that the reference counting is done correctly in 266 * all places, otherwise a suffix might be freed too early. 267 */ 268 269 free(gn); 270 } 271 #endif 272 273 /* Get the existing global node, or return NULL. */ 274 GNode * 275 Targ_FindNode(const char *name) 276 { 277 return HashTable_FindValue(&allTargetsByName, name); 278 } 279 280 /* Get the existing global node, or create it. */ 281 GNode * 282 Targ_GetNode(const char *name) 283 { 284 bool isNew; 285 HashEntry *he = HashTable_CreateEntry(&allTargetsByName, name, &isNew); 286 if (!isNew) 287 return HashEntry_Get(he); 288 289 { 290 GNode *gn = Targ_NewInternalNode(name); 291 HashEntry_Set(he, gn); 292 return gn; 293 } 294 } 295 296 /* 297 * Create a node, register it in .ALLTARGETS but don't store it in the 298 * table of global nodes. This means it cannot be found by name. 299 * 300 * This is used for internal nodes, such as cohorts or .WAIT nodes. 301 */ 302 GNode * 303 Targ_NewInternalNode(const char *name) 304 { 305 GNode *gn = GNode_New(name); 306 Global_Append(".ALLTARGETS", name); 307 Lst_Append(&allTargets, gn); 308 DEBUG1(TARG, "Adding \"%s\" to all targets.\n", gn->name); 309 if (doing_depend) 310 gn->flags.fromDepend = true; 311 return gn; 312 } 313 314 /* 315 * Return the .END node, which contains the commands to be run when 316 * everything else has been made. 317 */ 318 GNode * 319 Targ_GetEndNode(void) 320 { 321 /* 322 * Save the node locally to avoid having to search for it all 323 * the time. 324 */ 325 static GNode *endNode = NULL; 326 327 if (endNode == NULL) { 328 endNode = Targ_GetNode(".END"); 329 endNode->type = OP_SPECIAL; 330 } 331 return endNode; 332 } 333 334 /* Add the named nodes to the list, creating them as necessary. */ 335 void 336 Targ_FindList(GNodeList *gns, StringList *names) 337 { 338 StringListNode *ln; 339 340 for (ln = names->first; ln != NULL; ln = ln->next) { 341 const char *name = ln->datum; 342 GNode *gn = Targ_GetNode(name); 343 Lst_Append(gns, gn); 344 } 345 } 346 347 static void 348 PrintNodeNames(GNodeList *gnodes) 349 { 350 GNodeListNode *ln; 351 352 for (ln = gnodes->first; ln != NULL; ln = ln->next) { 353 GNode *gn = ln->datum; 354 debug_printf(" %s%s", gn->name, gn->cohort_num); 355 } 356 } 357 358 static void 359 PrintNodeNamesLine(const char *label, GNodeList *gnodes) 360 { 361 if (Lst_IsEmpty(gnodes)) 362 return; 363 debug_printf("# %s:", label); 364 PrintNodeNames(gnodes); 365 debug_printf("\n"); 366 } 367 368 void 369 Targ_PrintCmds(GNode *gn) 370 { 371 StringListNode *ln; 372 373 for (ln = gn->commands.first; ln != NULL; ln = ln->next) { 374 const char *cmd = ln->datum; 375 debug_printf("\t%s\n", cmd); 376 } 377 } 378 379 /* 380 * Format a modification time in some reasonable way and return it. 381 * The formatted time is placed in a static area, so it is overwritten 382 * with each call. 383 */ 384 const char * 385 Targ_FmtTime(time_t tm) 386 { 387 static char buf[128]; 388 389 struct tm *parts = localtime(&tm); 390 (void)strftime(buf, sizeof buf, "%H:%M:%S %b %d, %Y", parts); 391 return buf; 392 } 393 394 /* Print out a type field giving only those attributes the user can set. */ 395 void 396 Targ_PrintType(GNodeType type) 397 { 398 static const struct { 399 GNodeType bit; 400 bool internal; 401 const char name[10]; 402 } names[] = { 403 { OP_MEMBER, true, "MEMBER" }, 404 { OP_LIB, true, "LIB" }, 405 { OP_ARCHV, true, "ARCHV" }, 406 { OP_PHONY, true, "PHONY" }, 407 { OP_NOTMAIN, false, "NOTMAIN" }, 408 { OP_INVISIBLE, false, "INVISIBLE" }, 409 { OP_MADE, true, "MADE" }, 410 { OP_JOIN, false, "JOIN" }, 411 { OP_MAKE, false, "MAKE" }, 412 { OP_SILENT, false, "SILENT" }, 413 { OP_PRECIOUS, false, "PRECIOUS" }, 414 { OP_IGNORE, false, "IGNORE" }, 415 { OP_EXEC, false, "EXEC" }, 416 { OP_USE, false, "USE" }, 417 { OP_USEBEFORE, false, "USEBEFORE" }, 418 { OP_OPTIONAL, false, "OPTIONAL" }, 419 }; 420 size_t i; 421 422 for (i = 0; i < sizeof(names) / sizeof(names[0]); i++) { 423 if (type & names[i].bit) { 424 if (names[i].internal) 425 DEBUG1(TARG, " .%s", names[i].name); 426 else 427 debug_printf(" .%s", names[i].name); 428 } 429 } 430 } 431 432 const char * 433 GNodeMade_Name(GNodeMade made) 434 { 435 switch (made) { 436 case UNMADE: return "unmade"; 437 case DEFERRED: return "deferred"; 438 case REQUESTED: return "requested"; 439 case BEINGMADE: return "being made"; 440 case MADE: return "made"; 441 case UPTODATE: return "up-to-date"; 442 case ERROR: return "error when made"; 443 case ABORTED: return "aborted"; 444 default: return "unknown enum_made value"; 445 } 446 } 447 448 static const char * 449 GNode_OpName(const GNode *gn) 450 { 451 switch (gn->type & OP_OPMASK) { 452 case OP_DEPENDS: 453 return ":"; 454 case OP_FORCE: 455 return "!"; 456 case OP_DOUBLEDEP: 457 return "::"; 458 } 459 return ""; 460 } 461 462 static bool 463 GNodeFlags_IsNone(GNodeFlags flags) 464 { 465 return !flags.remake 466 && !flags.childMade 467 && !flags.force 468 && !flags.doneWait 469 && !flags.doneOrder 470 && !flags.fromDepend 471 && !flags.doneAllsrc 472 && !flags.cycle 473 && !flags.doneCycle; 474 } 475 476 /* Print the contents of a node. */ 477 void 478 Targ_PrintNode(GNode *gn, int pass) 479 { 480 debug_printf("# %s%s", gn->name, gn->cohort_num); 481 GNode_FprintDetails(opts.debug_file, ", ", gn, "\n"); 482 if (GNodeFlags_IsNone(gn->flags)) 483 return; 484 485 if (!GNode_IsTarget(gn)) 486 return; 487 488 debug_printf("#\n"); 489 if (gn == mainNode) 490 debug_printf("# *** MAIN TARGET ***\n"); 491 492 if (pass >= 2) { 493 if (gn->unmade > 0) 494 debug_printf("# %d unmade children\n", gn->unmade); 495 else 496 debug_printf("# No unmade children\n"); 497 if (!(gn->type & (OP_JOIN | OP_USE | OP_USEBEFORE | OP_EXEC))) { 498 if (gn->mtime != 0) { 499 debug_printf("# last modified %s: %s\n", 500 Targ_FmtTime(gn->mtime), 501 GNodeMade_Name(gn->made)); 502 } else if (gn->made != UNMADE) { 503 debug_printf("# nonexistent (maybe): %s\n", 504 GNodeMade_Name(gn->made)); 505 } else 506 debug_printf("# unmade\n"); 507 } 508 PrintNodeNamesLine("implicit parents", &gn->implicitParents); 509 } else { 510 if (gn->unmade != 0) 511 debug_printf("# %d unmade children\n", gn->unmade); 512 } 513 514 PrintNodeNamesLine("parents", &gn->parents); 515 PrintNodeNamesLine("order_pred", &gn->order_pred); 516 PrintNodeNamesLine("order_succ", &gn->order_succ); 517 518 debug_printf("%-16s%s", gn->name, GNode_OpName(gn)); 519 Targ_PrintType(gn->type); 520 PrintNodeNames(&gn->children); 521 debug_printf("\n"); 522 Targ_PrintCmds(gn); 523 debug_printf("\n\n"); 524 if (gn->type & OP_DOUBLEDEP) 525 Targ_PrintNodes(&gn->cohorts, pass); 526 } 527 528 void 529 Targ_PrintNodes(GNodeList *gnodes, int pass) 530 { 531 GNodeListNode *ln; 532 533 for (ln = gnodes->first; ln != NULL; ln = ln->next) 534 Targ_PrintNode(ln->datum, pass); 535 } 536 537 static void 538 PrintOnlySources(void) 539 { 540 GNodeListNode *ln; 541 542 for (ln = allTargets.first; ln != NULL; ln = ln->next) { 543 GNode *gn = ln->datum; 544 if (GNode_IsTarget(gn)) 545 continue; 546 547 debug_printf("#\t%s [%s]", gn->name, GNode_Path(gn)); 548 Targ_PrintType(gn->type); 549 debug_printf("\n"); 550 } 551 } 552 553 /* 554 * Input: 555 * pass 1 => before processing 556 * 2 => after processing 557 * 3 => after processing, an error occurred 558 */ 559 void 560 Targ_PrintGraph(int pass) 561 { 562 debug_printf("#*** Input graph:\n"); 563 Targ_PrintNodes(&allTargets, pass); 564 debug_printf("\n"); 565 debug_printf("\n"); 566 567 debug_printf("#\n"); 568 debug_printf("# Files that are only sources:\n"); 569 PrintOnlySources(); 570 571 debug_printf("#*** Global Variables:\n"); 572 Var_Dump(SCOPE_GLOBAL); 573 574 debug_printf("#*** Command-line Variables:\n"); 575 Var_Dump(SCOPE_CMDLINE); 576 577 debug_printf("\n"); 578 Dir_PrintDirectories(); 579 debug_printf("\n"); 580 581 Suff_PrintAll(); 582 } 583 584 /* 585 * Propagate some type information to cohort nodes (those from the '::' 586 * dependency operator). 587 * 588 * Should be called after the makefiles are parsed but before any action is 589 * taken. 590 */ 591 void 592 Targ_Propagate(void) 593 { 594 GNodeListNode *ln, *cln; 595 596 for (ln = allTargets.first; ln != NULL; ln = ln->next) { 597 GNode *gn = ln->datum; 598 GNodeType type = gn->type; 599 600 if (!(type & OP_DOUBLEDEP)) 601 continue; 602 603 for (cln = gn->cohorts.first; cln != NULL; cln = cln->next) { 604 GNode *cohort = cln->datum; 605 606 cohort->type |= type & (unsigned)~OP_OPMASK; 607 } 608 } 609 } 610