1 /* $NetBSD: targ.c,v 1.172 2021/09/12 08:32:23 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.172 2021/09/12 08:32:23 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 gn->flags = GNF_NONE; 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 |= FROM_DEPEND; 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 /* Print the contents of a node. */ 485 void 486 Targ_PrintNode(GNode *gn, int pass) 487 { 488 debug_printf("# %s%s", gn->name, gn->cohort_num); 489 GNode_FprintDetails(opts.debug_file, ", ", gn, "\n"); 490 if (gn->flags == 0) 491 return; 492 493 if (!GNode_IsTarget(gn)) 494 return; 495 496 debug_printf("#\n"); 497 if (gn == mainTarg) 498 debug_printf("# *** MAIN TARGET ***\n"); 499 500 if (pass >= 2) { 501 if (gn->unmade > 0) 502 debug_printf("# %d unmade children\n", gn->unmade); 503 else 504 debug_printf("# No unmade children\n"); 505 if (!(gn->type & (OP_JOIN | OP_USE | OP_USEBEFORE | OP_EXEC))) { 506 if (gn->mtime != 0) { 507 debug_printf("# last modified %s: %s\n", 508 Targ_FmtTime(gn->mtime), 509 GNodeMade_Name(gn->made)); 510 } else if (gn->made != UNMADE) { 511 debug_printf("# nonexistent (maybe): %s\n", 512 GNodeMade_Name(gn->made)); 513 } else 514 debug_printf("# unmade\n"); 515 } 516 PrintNodeNamesLine("implicit parents", &gn->implicitParents); 517 } else { 518 if (gn->unmade != 0) 519 debug_printf("# %d unmade children\n", gn->unmade); 520 } 521 522 PrintNodeNamesLine("parents", &gn->parents); 523 PrintNodeNamesLine("order_pred", &gn->order_pred); 524 PrintNodeNamesLine("order_succ", &gn->order_succ); 525 526 debug_printf("%-16s%s", gn->name, GNode_OpName(gn)); 527 Targ_PrintType(gn->type); 528 PrintNodeNames(&gn->children); 529 debug_printf("\n"); 530 Targ_PrintCmds(gn); 531 debug_printf("\n\n"); 532 if (gn->type & OP_DOUBLEDEP) 533 Targ_PrintNodes(&gn->cohorts, pass); 534 } 535 536 void 537 Targ_PrintNodes(GNodeList *gnodes, int pass) 538 { 539 GNodeListNode *ln; 540 541 for (ln = gnodes->first; ln != NULL; ln = ln->next) 542 Targ_PrintNode(ln->datum, pass); 543 } 544 545 /* Print only those targets that are just a source. */ 546 static void 547 PrintOnlySources(void) 548 { 549 GNodeListNode *ln; 550 551 for (ln = allTargets.first; ln != NULL; ln = ln->next) { 552 GNode *gn = ln->datum; 553 if (GNode_IsTarget(gn)) 554 continue; 555 556 debug_printf("#\t%s [%s]", gn->name, GNode_Path(gn)); 557 Targ_PrintType(gn->type); 558 debug_printf("\n"); 559 } 560 } 561 562 /* 563 * Input: 564 * pass 1 => before processing 565 * 2 => after processing 566 * 3 => after processing, an error occurred 567 */ 568 void 569 Targ_PrintGraph(int pass) 570 { 571 debug_printf("#*** Input graph:\n"); 572 Targ_PrintNodes(&allTargets, pass); 573 debug_printf("\n"); 574 debug_printf("\n"); 575 576 debug_printf("#\n"); 577 debug_printf("# Files that are only sources:\n"); 578 PrintOnlySources(); 579 580 debug_printf("#*** Global Variables:\n"); 581 Var_Dump(SCOPE_GLOBAL); 582 583 debug_printf("#*** Command-line Variables:\n"); 584 Var_Dump(SCOPE_CMDLINE); 585 586 debug_printf("\n"); 587 Dir_PrintDirectories(); 588 debug_printf("\n"); 589 590 Suff_PrintAll(); 591 } 592 593 /* 594 * Propagate some type information to cohort nodes (those from the '::' 595 * dependency operator). 596 * 597 * Should be called after the makefiles are parsed but before any action is 598 * taken. 599 */ 600 void 601 Targ_Propagate(void) 602 { 603 GNodeListNode *ln, *cln; 604 605 for (ln = allTargets.first; ln != NULL; ln = ln->next) { 606 GNode *gn = ln->datum; 607 GNodeType type = gn->type; 608 609 if (!(type & OP_DOUBLEDEP)) 610 continue; 611 612 for (cln = gn->cohorts.first; cln != NULL; cln = cln->next) { 613 GNode *cohort = cln->datum; 614 615 cohort->type |= type & ~OP_OPMASK; 616 } 617 } 618 } 619