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