contrib/bmake/targ.c

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