1 /* $NetBSD: targ.c,v 1.183 2024/05/25 21:07:48 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.183 2024/05/25 21:07:48 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 Var_DeleteAll(gn); 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 HashTable_Done(&gn->vars); 242 243 /* 244 * Do not free the commands themselves, as they may be shared with 245 * other nodes. 246 */ 247 Lst_Done(&gn->commands); 248 249 /* 250 * gn->suffix is not owned by this node. 251 * 252 * XXX: gn->suffix should be unreferenced here. This requires a 253 * thorough check that the reference counting is done correctly in 254 * all places, otherwise a suffix might be freed too early. 255 */ 256 257 free(gn); 258 } 259 #endif 260 261 /* Get the existing global node, or return NULL. */ 262 GNode * 263 Targ_FindNode(const char *name) 264 { 265 return HashTable_FindValue(&allTargetsByName, name); 266 } 267 268 /* Get the existing global node, or create it. */ 269 GNode * 270 Targ_GetNode(const char *name) 271 { 272 bool isNew; 273 HashEntry *he = HashTable_CreateEntry(&allTargetsByName, name, &isNew); 274 if (!isNew) 275 return HashEntry_Get(he); 276 277 { 278 GNode *gn = Targ_NewInternalNode(name); 279 HashEntry_Set(he, gn); 280 return gn; 281 } 282 } 283 284 /* 285 * Create a node, register it in .ALLTARGETS but don't store it in the 286 * table of global nodes. This means it cannot be found by name. 287 * 288 * This is used for internal nodes, such as cohorts or .WAIT nodes. 289 */ 290 GNode * 291 Targ_NewInternalNode(const char *name) 292 { 293 GNode *gn = GNode_New(name); 294 Global_Append(".ALLTARGETS", name); 295 Lst_Append(&allTargets, gn); 296 DEBUG1(TARG, "Adding \"%s\" to all targets.\n", gn->name); 297 if (doing_depend) 298 gn->flags.fromDepend = true; 299 return gn; 300 } 301 302 /* 303 * Return the .END node, which contains the commands to be run when 304 * everything else has been made. 305 */ 306 GNode * 307 Targ_GetEndNode(void) 308 { 309 /* 310 * Save the node locally to avoid having to search for it all 311 * the time. 312 */ 313 static GNode *endNode = NULL; 314 315 if (endNode == NULL) { 316 endNode = Targ_GetNode(".END"); 317 endNode->type = OP_SPECIAL; 318 } 319 return endNode; 320 } 321 322 /* Add the named nodes to the list, creating them as necessary. */ 323 void 324 Targ_FindList(GNodeList *gns, StringList *names) 325 { 326 StringListNode *ln; 327 328 for (ln = names->first; ln != NULL; ln = ln->next) { 329 const char *name = ln->datum; 330 GNode *gn = Targ_GetNode(name); 331 Lst_Append(gns, gn); 332 } 333 } 334 335 static void 336 PrintNodeNames(GNodeList *gnodes) 337 { 338 GNodeListNode *ln; 339 340 for (ln = gnodes->first; ln != NULL; ln = ln->next) { 341 GNode *gn = ln->datum; 342 debug_printf(" %s%s", gn->name, gn->cohort_num); 343 } 344 } 345 346 static void 347 PrintNodeNamesLine(const char *label, GNodeList *gnodes) 348 { 349 if (Lst_IsEmpty(gnodes)) 350 return; 351 debug_printf("# %s:", label); 352 PrintNodeNames(gnodes); 353 debug_printf("\n"); 354 } 355 356 void 357 Targ_PrintCmds(GNode *gn) 358 { 359 StringListNode *ln; 360 361 for (ln = gn->commands.first; ln != NULL; ln = ln->next) { 362 const char *cmd = ln->datum; 363 debug_printf("\t%s\n", cmd); 364 } 365 } 366 367 /* 368 * Format a modification time in some reasonable way and return it. 369 * The formatted time is placed in a static area, so it is overwritten 370 * with each call. 371 */ 372 const char * 373 Targ_FmtTime(time_t tm) 374 { 375 static char buf[128]; 376 377 struct tm *parts = localtime(&tm); 378 (void)strftime(buf, sizeof buf, "%H:%M:%S %b %d, %Y", parts); 379 return buf; 380 } 381 382 /* Print out a type field giving only those attributes the user can set. */ 383 void 384 Targ_PrintType(GNodeType type) 385 { 386 static const struct { 387 GNodeType bit; 388 bool internal; 389 const char name[10]; 390 } names[] = { 391 { OP_MEMBER, true, "MEMBER" }, 392 { OP_LIB, true, "LIB" }, 393 { OP_ARCHV, true, "ARCHV" }, 394 { OP_PHONY, true, "PHONY" }, 395 { OP_NOTMAIN, false, "NOTMAIN" }, 396 { OP_INVISIBLE, false, "INVISIBLE" }, 397 { OP_MADE, true, "MADE" }, 398 { OP_JOIN, false, "JOIN" }, 399 { OP_MAKE, false, "MAKE" }, 400 { OP_SILENT, false, "SILENT" }, 401 { OP_PRECIOUS, false, "PRECIOUS" }, 402 { OP_IGNORE, false, "IGNORE" }, 403 { OP_EXEC, false, "EXEC" }, 404 { OP_USE, false, "USE" }, 405 { OP_USEBEFORE, false, "USEBEFORE" }, 406 { OP_OPTIONAL, false, "OPTIONAL" }, 407 }; 408 size_t i; 409 410 for (i = 0; i < sizeof(names) / sizeof(names[0]); i++) { 411 if (type & names[i].bit) { 412 if (names[i].internal) 413 DEBUG1(TARG, " .%s", names[i].name); 414 else 415 debug_printf(" .%s", names[i].name); 416 } 417 } 418 } 419 420 const char * 421 GNodeMade_Name(GNodeMade made) 422 { 423 switch (made) { 424 case UNMADE: return "unmade"; 425 case DEFERRED: return "deferred"; 426 case REQUESTED: return "requested"; 427 case BEINGMADE: return "being made"; 428 case MADE: return "made"; 429 case UPTODATE: return "up-to-date"; 430 case ERROR: return "error when made"; 431 case ABORTED: return "aborted"; 432 default: return "unknown enum_made value"; 433 } 434 } 435 436 static const char * 437 GNode_OpName(const GNode *gn) 438 { 439 switch (gn->type & OP_OPMASK) { 440 case OP_DEPENDS: 441 return ":"; 442 case OP_FORCE: 443 return "!"; 444 case OP_DOUBLEDEP: 445 return "::"; 446 } 447 return ""; 448 } 449 450 static bool 451 GNodeFlags_IsNone(GNodeFlags flags) 452 { 453 return !flags.remake 454 && !flags.childMade 455 && !flags.force 456 && !flags.doneWait 457 && !flags.doneOrder 458 && !flags.fromDepend 459 && !flags.doneAllsrc 460 && !flags.cycle 461 && !flags.doneCycle; 462 } 463 464 /* Print the contents of a node. */ 465 void 466 Targ_PrintNode(GNode *gn, int pass) 467 { 468 debug_printf("# %s%s", gn->name, gn->cohort_num); 469 GNode_FprintDetails(opts.debug_file, ", ", gn, "\n"); 470 if (GNodeFlags_IsNone(gn->flags)) 471 return; 472 473 if (!GNode_IsTarget(gn)) 474 return; 475 476 debug_printf("#\n"); 477 if (gn == mainNode) 478 debug_printf("# *** MAIN TARGET ***\n"); 479 480 if (pass >= 2) { 481 if (gn->unmade > 0) 482 debug_printf("# %d unmade children\n", gn->unmade); 483 else 484 debug_printf("# No unmade children\n"); 485 if (!(gn->type & (OP_JOIN | OP_USE | OP_USEBEFORE | OP_EXEC))) { 486 if (gn->mtime != 0) { 487 debug_printf("# last modified %s: %s\n", 488 Targ_FmtTime(gn->mtime), 489 GNodeMade_Name(gn->made)); 490 } else if (gn->made != UNMADE) { 491 debug_printf("# nonexistent (maybe): %s\n", 492 GNodeMade_Name(gn->made)); 493 } else 494 debug_printf("# unmade\n"); 495 } 496 PrintNodeNamesLine("implicit parents", &gn->implicitParents); 497 } else { 498 if (gn->unmade != 0) 499 debug_printf("# %d unmade children\n", gn->unmade); 500 } 501 502 PrintNodeNamesLine("parents", &gn->parents); 503 PrintNodeNamesLine("order_pred", &gn->order_pred); 504 PrintNodeNamesLine("order_succ", &gn->order_succ); 505 506 debug_printf("%-16s%s", gn->name, GNode_OpName(gn)); 507 Targ_PrintType(gn->type); 508 PrintNodeNames(&gn->children); 509 debug_printf("\n"); 510 Targ_PrintCmds(gn); 511 debug_printf("\n\n"); 512 if (gn->type & OP_DOUBLEDEP) 513 Targ_PrintNodes(&gn->cohorts, pass); 514 } 515 516 void 517 Targ_PrintNodes(GNodeList *gnodes, int pass) 518 { 519 GNodeListNode *ln; 520 521 for (ln = gnodes->first; ln != NULL; ln = ln->next) 522 Targ_PrintNode(ln->datum, pass); 523 } 524 525 static void 526 PrintOnlySources(void) 527 { 528 GNodeListNode *ln; 529 530 for (ln = allTargets.first; ln != NULL; ln = ln->next) { 531 GNode *gn = ln->datum; 532 if (GNode_IsTarget(gn)) 533 continue; 534 535 debug_printf("#\t%s [%s]", gn->name, GNode_Path(gn)); 536 Targ_PrintType(gn->type); 537 debug_printf("\n"); 538 } 539 } 540 541 /* 542 * Input: 543 * pass 1 => before processing 544 * 2 => after processing 545 * 3 => after processing, an error occurred 546 */ 547 void 548 Targ_PrintGraph(int pass) 549 { 550 debug_printf("#*** Input graph:\n"); 551 Targ_PrintNodes(&allTargets, pass); 552 debug_printf("\n"); 553 debug_printf("\n"); 554 555 debug_printf("#\n"); 556 debug_printf("# Files that are only sources:\n"); 557 PrintOnlySources(); 558 559 debug_printf("#*** Global Variables:\n"); 560 Var_Dump(SCOPE_GLOBAL); 561 562 debug_printf("#*** Command-line Variables:\n"); 563 Var_Dump(SCOPE_CMDLINE); 564 565 debug_printf("\n"); 566 Dir_PrintDirectories(); 567 debug_printf("\n"); 568 569 Suff_PrintAll(); 570 } 571 572 /* 573 * Propagate some type information to cohort nodes (those from the '::' 574 * dependency operator). 575 * 576 * Should be called after the makefiles are parsed but before any action is 577 * taken. 578 */ 579 void 580 Targ_Propagate(void) 581 { 582 GNodeListNode *ln, *cln; 583 584 for (ln = allTargets.first; ln != NULL; ln = ln->next) { 585 GNode *gn = ln->datum; 586 GNodeType type = gn->type; 587 588 if (!(type & OP_DOUBLEDEP)) 589 continue; 590 591 for (cln = gn->cohorts.first; cln != NULL; cln = cln->next) { 592 GNode *cohort = cln->datum; 593 594 cohort->type |= type & (unsigned)~OP_OPMASK; 595 } 596 } 597 } 598