1 /* $NetBSD: targ.c,v 1.166 2021/02/22 20:38:55 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.166 2021/02/22 20:38:55 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 Boolean 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 Boolean 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, "%k:%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(int type) 420 { 421 int tbit; 422 423 type &= ~OP_OPMASK; 424 425 while (type != 0) { 426 tbit = 1 << (ffs(type) - 1); 427 type &= ~tbit; 428 429 switch (tbit) { 430 #define PRINTBIT(bit, attr) case bit: debug_printf(" " attr); break 431 #define PRINTDBIT(bit, attr) case bit: DEBUG0(TARG, " " attr); break 432 PRINTBIT(OP_OPTIONAL, ".OPTIONAL"); 433 PRINTBIT(OP_USE, ".USE"); 434 PRINTBIT(OP_EXEC, ".EXEC"); 435 PRINTBIT(OP_IGNORE, ".IGNORE"); 436 PRINTBIT(OP_PRECIOUS, ".PRECIOUS"); 437 PRINTBIT(OP_SILENT, ".SILENT"); 438 PRINTBIT(OP_MAKE, ".MAKE"); 439 PRINTBIT(OP_JOIN, ".JOIN"); 440 PRINTBIT(OP_INVISIBLE, ".INVISIBLE"); 441 PRINTBIT(OP_NOTMAIN, ".NOTMAIN"); 442 PRINTDBIT(OP_LIB, ".LIB"); 443 PRINTDBIT(OP_MEMBER, ".MEMBER"); 444 PRINTDBIT(OP_ARCHV, ".ARCHV"); 445 PRINTDBIT(OP_MADE, ".MADE"); 446 PRINTDBIT(OP_PHONY, ".PHONY"); 447 #undef PRINTBIT 448 #undef PRINTDBIT 449 } 450 } 451 } 452 453 const char * 454 GNodeMade_Name(GNodeMade made) 455 { 456 switch (made) { 457 case UNMADE: return "unmade"; 458 case DEFERRED: return "deferred"; 459 case REQUESTED: return "requested"; 460 case BEINGMADE: return "being made"; 461 case MADE: return "made"; 462 case UPTODATE: return "up-to-date"; 463 case ERROR: return "error when made"; 464 case ABORTED: return "aborted"; 465 default: return "unknown enum_made value"; 466 } 467 } 468 469 static const char * 470 GNode_OpName(const GNode *gn) 471 { 472 switch (gn->type & OP_OPMASK) { 473 case OP_DEPENDS: 474 return ":"; 475 case OP_FORCE: 476 return "!"; 477 case OP_DOUBLEDEP: 478 return "::"; 479 } 480 return ""; 481 } 482 483 /* Print the contents of a node. */ 484 void 485 Targ_PrintNode(GNode *gn, int pass) 486 { 487 debug_printf("# %s%s", gn->name, gn->cohort_num); 488 GNode_FprintDetails(opts.debug_file, ", ", gn, "\n"); 489 if (gn->flags == 0) 490 return; 491 492 if (!GNode_IsTarget(gn)) 493 return; 494 495 debug_printf("#\n"); 496 if (gn == mainTarg) 497 debug_printf("# *** MAIN TARGET ***\n"); 498 499 if (pass >= 2) { 500 if (gn->unmade > 0) 501 debug_printf("# %d unmade children\n", gn->unmade); 502 else 503 debug_printf("# No unmade children\n"); 504 if (!(gn->type & (OP_JOIN | OP_USE | OP_USEBEFORE | OP_EXEC))) { 505 if (gn->mtime != 0) { 506 debug_printf("# last modified %s: %s\n", 507 Targ_FmtTime(gn->mtime), 508 GNodeMade_Name(gn->made)); 509 } else if (gn->made != UNMADE) { 510 debug_printf("# nonexistent (maybe): %s\n", 511 GNodeMade_Name(gn->made)); 512 } else 513 debug_printf("# unmade\n"); 514 } 515 PrintNodeNamesLine("implicit parents", &gn->implicitParents); 516 } else { 517 if (gn->unmade != 0) 518 debug_printf("# %d unmade children\n", gn->unmade); 519 } 520 521 PrintNodeNamesLine("parents", &gn->parents); 522 PrintNodeNamesLine("order_pred", &gn->order_pred); 523 PrintNodeNamesLine("order_succ", &gn->order_succ); 524 525 debug_printf("%-16s%s", gn->name, GNode_OpName(gn)); 526 Targ_PrintType(gn->type); 527 PrintNodeNames(&gn->children); 528 debug_printf("\n"); 529 Targ_PrintCmds(gn); 530 debug_printf("\n\n"); 531 if (gn->type & OP_DOUBLEDEP) 532 Targ_PrintNodes(&gn->cohorts, pass); 533 } 534 535 void 536 Targ_PrintNodes(GNodeList *gnodes, int pass) 537 { 538 GNodeListNode *ln; 539 540 for (ln = gnodes->first; ln != NULL; ln = ln->next) 541 Targ_PrintNode(ln->datum, pass); 542 } 543 544 /* Print only those targets that are just a source. */ 545 static void 546 PrintOnlySources(void) 547 { 548 GNodeListNode *ln; 549 550 for (ln = allTargets.first; ln != NULL; ln = ln->next) { 551 GNode *gn = ln->datum; 552 if (GNode_IsTarget(gn)) 553 continue; 554 555 debug_printf("#\t%s [%s]", gn->name, GNode_Path(gn)); 556 Targ_PrintType(gn->type); 557 debug_printf("\n"); 558 } 559 } 560 561 /* 562 * Input: 563 * pass 1 => before processing 564 * 2 => after processing 565 * 3 => after processing, an error occurred 566 */ 567 void 568 Targ_PrintGraph(int pass) 569 { 570 debug_printf("#*** Input graph:\n"); 571 Targ_PrintNodes(&allTargets, pass); 572 debug_printf("\n"); 573 debug_printf("\n"); 574 575 debug_printf("#\n"); 576 debug_printf("# Files that are only sources:\n"); 577 PrintOnlySources(); 578 579 debug_printf("#*** Global Variables:\n"); 580 Var_Dump(SCOPE_GLOBAL); 581 582 debug_printf("#*** Command-line Variables:\n"); 583 Var_Dump(SCOPE_CMDLINE); 584 585 debug_printf("\n"); 586 Dir_PrintDirectories(); 587 debug_printf("\n"); 588 589 Suff_PrintAll(); 590 } 591 592 /* 593 * Propagate some type information to cohort nodes (those from the '::' 594 * dependency operator). 595 * 596 * Should be called after the makefiles are parsed but before any action is 597 * taken. 598 */ 599 void 600 Targ_Propagate(void) 601 { 602 GNodeListNode *ln, *cln; 603 604 for (ln = allTargets.first; ln != NULL; ln = ln->next) { 605 GNode *gn = ln->datum; 606 GNodeType type = gn->type; 607 608 if (!(type & OP_DOUBLEDEP)) 609 continue; 610 611 for (cln = gn->cohorts.first; cln != NULL; cln = cln->next) { 612 GNode *cohort = cln->datum; 613 614 cohort->type |= type & ~OP_OPMASK; 615 } 616 } 617 } 618