contrib/bmake/targ.c

   1 /*      $NetBSD: targ.c,v 1.165 2021/02/04 21:42:46 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.165 2021/02/04 21:42:46 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 (VAR_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 }