1 /* $NetBSD: suff.c,v 1.374 2023/12/29 18:53:24 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 * Maintain suffix lists and find implicit dependents using suffix 73 * transformation rules such as ".c.o". 74 * 75 * Interface: 76 * Suff_Init Initialize the module. 77 * 78 * Suff_End Clean up the module. 79 * 80 * Suff_ExtendPaths 81 * Extend the search path of each suffix to include the 82 * default search path. 83 * 84 * Suff_ClearSuffixes 85 * Clear out all the suffixes and transformations. 86 * 87 * Suff_IsTransform 88 * See if the passed string is a transformation rule. 89 * 90 * Suff_AddSuffix Add the passed string as another known suffix. 91 * 92 * Suff_GetPath Return the search path for the given suffix. 93 * 94 * Suff_AddInclude 95 * Mark the given suffix as denoting an include file. 96 * 97 * Suff_AddLib Mark the given suffix as denoting a library. 98 * 99 * Suff_AddTransform 100 * Add another transformation to the suffix graph. 101 * 102 * Suff_SetNull Define the suffix to consider the suffix of 103 * any file that doesn't have a known one. 104 * 105 * Suff_FindDeps Find implicit sources for and the location of 106 * a target based on its suffix. Returns the 107 * bottom-most node added to the graph or NULL 108 * if the target had no implicit sources. 109 * 110 * Suff_FindPath Return the appropriate path to search in order to 111 * find the node. 112 */ 113 114 #include "make.h" 115 #include "dir.h" 116 117 /* "@(#)suff.c 8.4 (Berkeley) 3/21/94" */ 118 MAKE_RCSID("$NetBSD: suff.c,v 1.374 2023/12/29 18:53:24 rillig Exp $"); 119 120 typedef List SuffixList; 121 typedef ListNode SuffixListNode; 122 123 typedef List CandidateList; 124 typedef ListNode CandidateListNode; 125 126 /* The defined suffixes, such as '.c', '.o', '.l'. */ 127 static SuffixList sufflist = LST_INIT; 128 #ifdef CLEANUP 129 /* The suffixes to be cleaned up at the end. */ 130 static SuffixList suffClean = LST_INIT; 131 #endif 132 133 /* 134 * The transformation rules, such as '.c.o' to transform '.c' into '.o', 135 * or simply '.c' to transform 'file.c' into 'file'. 136 */ 137 static GNodeList transforms = LST_INIT; 138 139 /* 140 * Counter for assigning suffix numbers. 141 * TODO: What are these suffix numbers used for? 142 */ 143 static int sNum = 0; 144 145 typedef List SuffixListList; 146 147 /* 148 * A suffix such as ".c" or ".o" that may be used in suffix transformation 149 * rules such as ".c.o:". 150 */ 151 typedef struct Suffix { 152 /* The suffix itself, such as ".c" */ 153 char *name; 154 /* Length of the name, to avoid strlen calls */ 155 size_t nameLen; 156 /* 157 * This suffix marks include files. Their search path ends up in the 158 * undocumented special variable '.INCLUDES'. 159 */ 160 bool include:1; 161 /* 162 * This suffix marks library files. Their search path ends up in the 163 * undocumented special variable '.LIBS'. 164 */ 165 bool library:1; 166 /* 167 * The empty suffix. 168 * 169 * XXX: What is the difference between the empty suffix and the null 170 * suffix? 171 * 172 * XXX: Why is SUFF_NULL needed at all? Wouldn't nameLen == 0 mean 173 * the same? 174 */ 175 bool isNull:1; 176 /* The path along which files of this suffix may be found */ 177 SearchPath *searchPath; 178 179 /* The suffix number; TODO: document the purpose of this number */ 180 int sNum; 181 /* Reference count of list membership and several other places */ 182 int refCount; 183 184 /* Suffixes we have a transformation to */ 185 SuffixList parents; 186 /* Suffixes we have a transformation from */ 187 SuffixList children; 188 /* 189 * Lists in which this suffix is referenced. 190 * 191 * XXX: These lists are used nowhere, they are just appended to, for 192 * no apparent reason. They do have the side effect of increasing 193 * refCount though. 194 */ 195 SuffixListList ref; 196 } Suffix; 197 198 /* 199 * A candidate when searching for implied sources. 200 * 201 * For example, when "src.o" is to be made, a typical candidate is "src.c" 202 * via the transformation rule ".c.o". If that doesn't exist, maybe there is 203 * another transformation rule ".pas.c" that would make "src.pas" an indirect 204 * candidate as well. The first such chain that leads to an existing file or 205 * node is finally chosen to be made. 206 */ 207 typedef struct Candidate { 208 /* The file or node to look for. */ 209 char *file; 210 /* 211 * The prefix from which file was formed. Its memory is shared among 212 * all candidates. 213 */ 214 char *prefix; 215 /* The suffix on the file. */ 216 Suffix *suff; 217 218 /* 219 * The candidate that can be made from this, or NULL for the 220 * top-level candidate. 221 */ 222 struct Candidate *parent; 223 /* The node describing the file. */ 224 GNode *node; 225 226 /* 227 * Count of existing children, only used for memory management, so we 228 * don't free this candidate too early or too late. 229 */ 230 int numChildren; 231 #ifdef DEBUG_SRC 232 CandidateList childrenList; 233 #endif 234 } Candidate; 235 236 typedef struct CandidateSearcher { 237 238 CandidateList list; 239 240 /* 241 * TODO: Add HashSet for seen entries, to avoid endless loops such as 242 * in suff-transform-endless.mk. 243 */ 244 245 } CandidateSearcher; 246 247 248 /* TODO: Document the difference between nullSuff and emptySuff. */ 249 /* The NULL suffix is used when a file has no known suffix */ 250 static Suffix *nullSuff; 251 /* The empty suffix required for POSIX single-suffix transformation rules */ 252 static Suffix *emptySuff; 253 254 255 static Suffix * 256 Suffix_Ref(Suffix *suff) 257 { 258 suff->refCount++; 259 return suff; 260 } 261 262 /* Change the value of a Suffix variable, adjusting the reference counts. */ 263 static void 264 Suffix_Reassign(Suffix **var, Suffix *suff) 265 { 266 if (*var != NULL) 267 (*var)->refCount--; 268 *var = suff; 269 suff->refCount++; 270 } 271 272 /* Set a Suffix variable to NULL, adjusting the reference count. */ 273 static void 274 Suffix_Unassign(Suffix **var) 275 { 276 if (*var != NULL) 277 (*var)->refCount--; 278 *var = NULL; 279 } 280 281 /* 282 * See if pref is a prefix of str. 283 * Return NULL if it ain't, pointer to character in str after prefix if so. 284 */ 285 static const char * 286 StrTrimPrefix(const char *pref, const char *str) 287 { 288 while (*str != '\0' && *pref == *str) { 289 pref++; 290 str++; 291 } 292 293 return *pref != '\0' ? NULL : str; 294 } 295 296 /* 297 * See if suff is a suffix of str, and if so, return the pointer to the suffix 298 * in str, which at the same time marks the end of the prefix. 299 */ 300 static const char * 301 StrTrimSuffix(const char *str, size_t strLen, const char *suff, size_t suffLen) 302 { 303 const char *suffInStr; 304 size_t i; 305 306 if (strLen < suffLen) 307 return NULL; 308 309 suffInStr = str + strLen - suffLen; 310 for (i = 0; i < suffLen; i++) 311 if (suff[i] != suffInStr[i]) 312 return NULL; 313 314 return suffInStr; 315 } 316 317 /* 318 * See if suff is a suffix of name, and if so, return the end of the prefix 319 * in name. 320 */ 321 static const char * 322 Suffix_TrimSuffix(const Suffix *suff, size_t nameLen, const char *nameEnd) 323 { 324 return StrTrimSuffix(nameEnd - nameLen, nameLen, 325 suff->name, suff->nameLen); 326 } 327 328 static bool 329 Suffix_IsSuffix(const Suffix *suff, size_t nameLen, const char *nameEnd) 330 { 331 return Suffix_TrimSuffix(suff, nameLen, nameEnd) != NULL; 332 } 333 334 static Suffix * 335 FindSuffixByNameLen(const char *name, size_t nameLen) 336 { 337 SuffixListNode *ln; 338 339 for (ln = sufflist.first; ln != NULL; ln = ln->next) { 340 Suffix *suff = ln->datum; 341 if (suff->nameLen == nameLen && 342 memcmp(suff->name, name, nameLen) == 0) 343 return suff; 344 } 345 return NULL; 346 } 347 348 static Suffix * 349 FindSuffixByName(const char *name) 350 { 351 return FindSuffixByNameLen(name, strlen(name)); 352 } 353 354 static GNode * 355 FindTransformByName(const char *name) 356 { 357 GNodeListNode *ln; 358 359 for (ln = transforms.first; ln != NULL; ln = ln->next) { 360 GNode *gn = ln->datum; 361 if (strcmp(gn->name, name) == 0) 362 return gn; 363 } 364 return NULL; 365 } 366 367 static void 368 SuffixList_Unref(SuffixList *list, Suffix *suff) 369 { 370 SuffixListNode *ln = Lst_FindDatum(list, suff); 371 if (ln != NULL) { 372 Lst_Remove(list, ln); 373 suff->refCount--; 374 } 375 } 376 377 /* Free up all memory associated with the given suffix structure. */ 378 static void 379 Suffix_Free(Suffix *suff) 380 { 381 382 if (suff == nullSuff) 383 nullSuff = NULL; 384 385 if (suff == emptySuff) 386 emptySuff = NULL; 387 388 #if 0 389 /* We don't delete suffixes in order, so we cannot use this */ 390 if (suff->refCount != 0) 391 Punt("Internal error deleting suffix `%s' with refcount = %d", 392 suff->name, suff->refCount); 393 #endif 394 395 Lst_Done(&suff->ref); 396 Lst_Done(&suff->children); 397 Lst_Done(&suff->parents); 398 SearchPath_Free(suff->searchPath); 399 400 free(suff->name); 401 free(suff); 402 } 403 404 static void 405 SuffFree(void *p) 406 { 407 Suffix_Free(p); 408 } 409 410 /* Remove the suffix from the list, and free if it is otherwise unused. */ 411 static void 412 SuffixList_Remove(SuffixList *list, Suffix *suff) 413 { 414 SuffixList_Unref(list, suff); 415 if (suff->refCount == 0) { 416 /* XXX: can lead to suff->refCount == -1 */ 417 SuffixList_Unref(&sufflist, suff); 418 DEBUG1(SUFF, "Removing suffix \"%s\"\n", suff->name); 419 SuffFree(suff); 420 } 421 } 422 423 /* 424 * Insert the suffix into the list, keeping the list ordered by suffix 425 * number. 426 */ 427 static void 428 SuffixList_Insert(SuffixList *list, Suffix *suff) 429 { 430 SuffixListNode *ln; 431 Suffix *listSuff = NULL; 432 433 for (ln = list->first; ln != NULL; ln = ln->next) { 434 listSuff = ln->datum; 435 if (listSuff->sNum >= suff->sNum) 436 break; 437 } 438 439 if (ln == NULL) { 440 DEBUG2(SUFF, "inserting \"%s\" (%d) at end of list\n", 441 suff->name, suff->sNum); 442 Lst_Append(list, Suffix_Ref(suff)); 443 Lst_Append(&suff->ref, list); 444 } else if (listSuff->sNum != suff->sNum) { 445 DEBUG4(SUFF, "inserting \"%s\" (%d) before \"%s\" (%d)\n", 446 suff->name, suff->sNum, listSuff->name, listSuff->sNum); 447 Lst_InsertBefore(list, ln, Suffix_Ref(suff)); 448 Lst_Append(&suff->ref, list); 449 } else { 450 DEBUG2(SUFF, "\"%s\" (%d) is already there\n", 451 suff->name, suff->sNum); 452 } 453 } 454 455 static void 456 Relate(Suffix *srcSuff, Suffix *targSuff) 457 { 458 SuffixList_Insert(&targSuff->children, srcSuff); 459 SuffixList_Insert(&srcSuff->parents, targSuff); 460 } 461 462 static Suffix * 463 Suffix_New(const char *name) 464 { 465 Suffix *suff = bmake_malloc(sizeof *suff); 466 467 suff->name = bmake_strdup(name); 468 suff->nameLen = strlen(suff->name); 469 suff->searchPath = SearchPath_New(); 470 Lst_Init(&suff->children); 471 Lst_Init(&suff->parents); 472 Lst_Init(&suff->ref); 473 suff->sNum = sNum++; 474 suff->include = false; 475 suff->library = false; 476 suff->isNull = false; 477 suff->refCount = 1; /* XXX: why 1? It's not assigned anywhere yet. */ 478 479 return suff; 480 } 481 482 /* 483 * Nuke the list of suffixes but keep all transformation rules around. The 484 * transformation graph is destroyed in this process, but we leave the list 485 * of rules so when a new graph is formed, the rules will remain. This 486 * function is called when a line '.SUFFIXES:' with an empty suffixes list is 487 * encountered in a makefile. 488 */ 489 void 490 Suff_ClearSuffixes(void) 491 { 492 #ifdef CLEANUP 493 Lst_MoveAll(&suffClean, &sufflist); 494 #endif 495 DEBUG0(SUFF, "Clearing all suffixes\n"); 496 Lst_Init(&sufflist); 497 sNum = 0; 498 if (nullSuff != NULL) 499 SuffFree(nullSuff); 500 emptySuff = nullSuff = Suffix_New(""); 501 502 SearchPath_AddAll(nullSuff->searchPath, &dirSearchPath); 503 nullSuff->include = false; 504 nullSuff->library = false; 505 nullSuff->isNull = true; 506 } 507 508 /* 509 * Parse a transformation string such as ".c.o" to find its two component 510 * suffixes (the source ".c" and the target ".o"). If there are no such 511 * suffixes, try a single-suffix transformation as well. 512 * 513 * Return true if the string is a valid transformation. 514 */ 515 static bool 516 ParseTransform(const char *str, Suffix **out_src, Suffix **out_targ) 517 { 518 SuffixListNode *ln; 519 Suffix *single = NULL; 520 521 /* 522 * Loop looking first for a suffix that matches the start of the 523 * string and then for one that exactly matches the rest of it. If 524 * we can find two that meet these criteria, we've successfully 525 * parsed the string. 526 */ 527 for (ln = sufflist.first; ln != NULL; ln = ln->next) { 528 Suffix *src = ln->datum; 529 530 if (StrTrimPrefix(src->name, str) == NULL) 531 continue; 532 533 if (str[src->nameLen] == '\0') { 534 single = src; 535 } else { 536 Suffix *targ = FindSuffixByName(str + src->nameLen); 537 if (targ != NULL) { 538 *out_src = src; 539 *out_targ = targ; 540 return true; 541 } 542 } 543 } 544 545 if (single != NULL) { 546 /* 547 * There was a suffix that encompassed the entire string, so we 548 * assume it was a transformation to the null suffix (thank you 549 * POSIX; search for "single suffix" or "single-suffix"). 550 * 551 * We still prefer to find a double rule over a singleton, 552 * hence we leave this check until the end. 553 * 554 * XXX: Use emptySuff over nullSuff? 555 */ 556 *out_src = single; 557 *out_targ = nullSuff; 558 return true; 559 } 560 return false; 561 } 562 563 /* 564 * Return true if the given string is a transformation rule, that is, a 565 * concatenation of two known suffixes such as ".c.o" or a single suffix 566 * such as ".o". 567 */ 568 bool 569 Suff_IsTransform(const char *str) 570 { 571 Suffix *src, *targ; 572 573 return ParseTransform(str, &src, &targ); 574 } 575 576 /* 577 * Add the transformation rule to the list of rules and place the 578 * transformation itself in the graph. 579 * 580 * The transformation is linked to the two suffixes mentioned in the name. 581 * 582 * Input: 583 * name must have the form ".from.to" or just ".from" 584 * 585 * Results: 586 * The created or existing transformation node in the transforms list 587 */ 588 GNode * 589 Suff_AddTransform(const char *name) 590 { 591 Suffix *srcSuff; 592 Suffix *targSuff; 593 594 GNode *gn = FindTransformByName(name); 595 if (gn == NULL) { 596 /* 597 * Make a new graph node for the transformation. It will be 598 * filled in by the Parse module. 599 */ 600 gn = GNode_New(name); 601 Lst_Append(&transforms, gn); 602 } else { 603 /* 604 * New specification for transformation rule. Just nuke the 605 * old list of commands so they can be filled in again. We 606 * don't actually free the commands themselves, because a 607 * given command can be attached to several different 608 * transformations. 609 */ 610 Lst_Done(&gn->commands); 611 Lst_Init(&gn->commands); 612 Lst_Done(&gn->children); 613 Lst_Init(&gn->children); 614 } 615 616 gn->type = OP_TRANSFORM; 617 618 { 619 /* TODO: Avoid the redundant parsing here. */ 620 bool ok = ParseTransform(name, &srcSuff, &targSuff); 621 assert(ok); 622 /* LINTED 129 *//* expression has null effect */ 623 (void)ok; 624 } 625 626 /* Link the two together in the proper relationship and order. */ 627 DEBUG2(SUFF, "defining transformation from `%s' to `%s'\n", 628 srcSuff->name, targSuff->name); 629 Relate(srcSuff, targSuff); 630 631 return gn; 632 } 633 634 /* 635 * Handle the finish of a transformation definition, removing the 636 * transformation from the graph if it has neither commands nor sources. 637 * 638 * If the node has no commands or children, the children and parents lists 639 * of the affected suffixes are altered. 640 * 641 * Input: 642 * gn Node for transformation 643 */ 644 void 645 Suff_EndTransform(GNode *gn) 646 { 647 Suffix *srcSuff, *targSuff; 648 SuffixList *srcSuffParents; 649 650 if ((gn->type & OP_DOUBLEDEP) && !Lst_IsEmpty(&gn->cohorts)) 651 gn = gn->cohorts.last->datum; 652 653 if (!(gn->type & OP_TRANSFORM)) 654 return; 655 656 if (!Lst_IsEmpty(&gn->commands) || !Lst_IsEmpty(&gn->children)) { 657 DEBUG1(SUFF, "transformation %s complete\n", gn->name); 658 return; 659 } 660 661 /* 662 * SuffParseTransform() may fail for special rules which are not 663 * actual transformation rules. (e.g. .DEFAULT) 664 */ 665 if (!ParseTransform(gn->name, &srcSuff, &targSuff)) 666 return; 667 668 DEBUG2(SUFF, "deleting incomplete transformation from `%s' to `%s'\n", 669 srcSuff->name, targSuff->name); 670 671 /* 672 * Remember the parents since srcSuff could be deleted in 673 * SuffixList_Remove. 674 */ 675 srcSuffParents = &srcSuff->parents; 676 SuffixList_Remove(&targSuff->children, srcSuff); 677 SuffixList_Remove(srcSuffParents, targSuff); 678 } 679 680 /* 681 * Called from Suff_AddSuffix to search through the list of 682 * existing transformation rules and rebuild the transformation graph when 683 * it has been destroyed by Suff_ClearSuffixes. If the given rule is a 684 * transformation involving this suffix and another, existing suffix, the 685 * proper relationship is established between the two. 686 * 687 * The appropriate links will be made between this suffix and others if 688 * transformation rules exist for it. 689 * 690 * Input: 691 * transform Transformation to test 692 * suff Suffix to rebuild 693 */ 694 static void 695 RebuildGraph(GNode *transform, Suffix *suff) 696 { 697 const char *name = transform->name; 698 size_t nameLen = strlen(name); 699 const char *toName; 700 701 /* 702 * See if it is a transformation from this suffix to another suffix. 703 */ 704 toName = StrTrimPrefix(suff->name, name); 705 if (toName != NULL) { 706 Suffix *to = FindSuffixByName(toName); 707 if (to != NULL) { 708 Relate(suff, to); 709 return; 710 } 711 } 712 713 /* 714 * See if it is a transformation from another suffix to this suffix. 715 */ 716 toName = Suffix_TrimSuffix(suff, nameLen, name + nameLen); 717 if (toName != NULL) { 718 Suffix *from = FindSuffixByNameLen(name, 719 (size_t)(toName - name)); 720 if (from != NULL) 721 Relate(from, suff); 722 } 723 } 724 725 /* 726 * During Suff_AddSuffix, search through the list of existing targets and find 727 * if any of the existing targets can be turned into a transformation rule. 728 * 729 * If such a target is found and the target is the current main target, the 730 * main target is set to NULL and the next target examined (if that exists) 731 * becomes the main target. 732 * 733 * Results: 734 * true iff a new main target has been selected. 735 */ 736 static bool 737 UpdateTarget(GNode *target, Suffix *suff, bool *inout_removedMain) 738 { 739 Suffix *srcSuff, *targSuff; 740 char *ptr; 741 742 if (mainNode == NULL && *inout_removedMain && 743 GNode_IsMainCandidate(target)) { 744 DEBUG1(MAKE, "Setting main node to \"%s\"\n", target->name); 745 mainNode = target; 746 /* 747 * XXX: Why could it be a good idea to return true here? 748 * The main task of this function is to turn ordinary nodes 749 * into transformations, no matter whether or not a new .MAIN 750 * node has been found. 751 */ 752 /* 753 * XXX: Even when changing this to false, none of the existing 754 * unit tests fails. 755 */ 756 return true; 757 } 758 759 if (target->type == OP_TRANSFORM) 760 return false; 761 762 /* 763 * XXX: What about a transformation ".cpp.c"? If ".c" is added as 764 * a new suffix, it seems wrong that this transformation would be 765 * skipped just because ".c" happens to be a prefix of ".cpp". 766 */ 767 ptr = strstr(target->name, suff->name); 768 if (ptr == NULL) 769 return false; 770 771 /* 772 * XXX: In suff-rebuild.mk, in the line '.SUFFIXES: .c .b .a', this 773 * condition prevents the rule '.b.c' from being added again during 774 * Suff_AddSuffix(".b"). 775 * 776 * XXX: Removing this paragraph makes suff-add-later.mk use massive 777 * amounts of memory. 778 */ 779 if (ptr == target->name) 780 return false; 781 782 if (ParseTransform(target->name, &srcSuff, &targSuff)) { 783 if (mainNode == target) { 784 DEBUG1(MAKE, 785 "Setting main node from \"%s\" back to null\n", 786 target->name); 787 *inout_removedMain = true; 788 mainNode = NULL; 789 } 790 Lst_Done(&target->children); 791 Lst_Init(&target->children); 792 target->type = OP_TRANSFORM; 793 794 /* 795 * Link the two together in the proper relationship and order. 796 */ 797 DEBUG2(SUFF, "defining transformation from `%s' to `%s'\n", 798 srcSuff->name, targSuff->name); 799 Relate(srcSuff, targSuff); 800 } 801 return false; 802 } 803 804 /* 805 * Look at all existing targets to see if adding this suffix will make one 806 * of the current targets mutate into a suffix rule. 807 * 808 * This is ugly, but other makes treat all targets that start with a '.' as 809 * suffix rules. 810 */ 811 static void 812 UpdateTargets(Suffix *suff) 813 { 814 bool removedMain = false; 815 GNodeListNode *ln; 816 817 for (ln = Targ_List()->first; ln != NULL; ln = ln->next) { 818 GNode *gn = ln->datum; 819 if (UpdateTarget(gn, suff, &removedMain)) 820 break; 821 } 822 } 823 824 /* 825 * Add the suffix to the end of the list of known suffixes. 826 * Should we restructure the suffix graph? Make doesn't. 827 * 828 * A GNode is created for the suffix (XXX: this sounds completely wrong) and 829 * a Suffix structure is created and added to the suffixes list unless the 830 * suffix was already known. 831 * The mainNode passed can be modified if a target mutated into a 832 * transform and that target happened to be the main target. 833 * 834 * Input: 835 * name the name of the suffix to add 836 */ 837 void 838 Suff_AddSuffix(const char *name) 839 { 840 GNodeListNode *ln; 841 842 Suffix *suff = FindSuffixByName(name); 843 if (suff != NULL) 844 return; 845 846 suff = Suffix_New(name); 847 Lst_Append(&sufflist, suff); 848 DEBUG1(SUFF, "Adding suffix \"%s\"\n", suff->name); 849 850 UpdateTargets(suff); 851 852 /* 853 * Look for any existing transformations from or to this suffix. 854 * XXX: Only do this after a Suff_ClearSuffixes? 855 */ 856 for (ln = transforms.first; ln != NULL; ln = ln->next) 857 RebuildGraph(ln->datum, suff); 858 } 859 860 /* Return the search path for the given suffix, or NULL. */ 861 SearchPath * 862 Suff_GetPath(const char *name) 863 { 864 Suffix *suff = FindSuffixByName(name); 865 return suff != NULL ? suff->searchPath : NULL; 866 } 867 868 /* 869 * Extend the search paths for all suffixes to include the default search 870 * path (dirSearchPath). 871 * 872 * The default search path can be defined using the special target '.PATH'. 873 * The search path of each suffix can be defined using the special target 874 * '.PATH<suffix>'. 875 * 876 * If paths were specified for the ".h" suffix, the directories are stuffed 877 * into a global variable called ".INCLUDES" with each directory preceded by 878 * '-I'. The same is done for the ".a" suffix, except the variable is called 879 * ".LIBS" and the flag is '-L'. 880 */ 881 void 882 Suff_ExtendPaths(void) 883 { 884 SuffixListNode *ln; 885 char *flags; 886 SearchPath *includesPath = SearchPath_New(); 887 SearchPath *libsPath = SearchPath_New(); 888 889 for (ln = sufflist.first; ln != NULL; ln = ln->next) { 890 Suffix *suff = ln->datum; 891 if (!Lst_IsEmpty(&suff->searchPath->dirs)) { 892 #ifdef INCLUDES 893 if (suff->include) 894 SearchPath_AddAll(includesPath, 895 suff->searchPath); 896 #endif 897 #ifdef LIBRARIES 898 if (suff->library) 899 SearchPath_AddAll(libsPath, suff->searchPath); 900 #endif 901 SearchPath_AddAll(suff->searchPath, &dirSearchPath); 902 } else { 903 SearchPath_Free(suff->searchPath); 904 suff->searchPath = Dir_CopyDirSearchPath(); 905 } 906 } 907 908 flags = SearchPath_ToFlags(includesPath, "-I"); 909 Global_Set(".INCLUDES", flags); 910 free(flags); 911 912 flags = SearchPath_ToFlags(libsPath, "-L"); 913 Global_Set(".LIBS", flags); 914 free(flags); 915 916 SearchPath_Free(includesPath); 917 SearchPath_Free(libsPath); 918 } 919 920 /* 921 * Add the given suffix as a type of file which gets included. 922 * Called when a '.INCLUDES: .h' line is parsed. 923 * To have an effect, the suffix must already exist. 924 * This affects the magic variable '.INCLUDES'. 925 */ 926 void 927 Suff_AddInclude(const char *suffName) 928 { 929 Suffix *suff = FindSuffixByName(suffName); 930 if (suff != NULL) 931 suff->include = true; 932 } 933 934 /* 935 * Add the given suffix as a type of file which is a library. 936 * Called when a '.LIBS: .a' line is parsed. 937 * To have an effect, the suffix must already exist. 938 * This affects the magic variable '.LIBS'. 939 */ 940 void 941 Suff_AddLib(const char *suffName) 942 { 943 Suffix *suff = FindSuffixByName(suffName); 944 if (suff != NULL) 945 suff->library = true; 946 } 947 948 /********** Implicit Source Search Functions *********/ 949 950 static void 951 CandidateSearcher_Init(CandidateSearcher *cs) 952 { 953 Lst_Init(&cs->list); 954 } 955 956 static void 957 CandidateSearcher_Done(CandidateSearcher *cs) 958 { 959 Lst_Done(&cs->list); 960 } 961 962 static void 963 CandidateSearcher_Add(CandidateSearcher *cs, Candidate *cand) 964 { 965 /* TODO: filter duplicates */ 966 Lst_Append(&cs->list, cand); 967 } 968 969 static void 970 CandidateSearcher_AddIfNew(CandidateSearcher *cs, Candidate *cand) 971 { 972 /* TODO: filter duplicates */ 973 if (Lst_FindDatum(&cs->list, cand) == NULL) 974 Lst_Append(&cs->list, cand); 975 } 976 977 static void 978 CandidateSearcher_MoveAll(CandidateSearcher *cs, CandidateList *list) 979 { 980 /* TODO: filter duplicates */ 981 Lst_MoveAll(&cs->list, list); 982 } 983 984 985 #ifdef DEBUG_SRC 986 static void 987 CandidateList_PrintAddrs(CandidateList *list) 988 { 989 CandidateListNode *ln; 990 991 for (ln = list->first; ln != NULL; ln = ln->next) { 992 Candidate *cand = ln->datum; 993 debug_printf(" %p:%s", cand, cand->file); 994 } 995 debug_printf("\n"); 996 } 997 #endif 998 999 static Candidate * 1000 Candidate_New(char *name, char *prefix, Suffix *suff, Candidate *parent, 1001 GNode *gn) 1002 { 1003 Candidate *cand = bmake_malloc(sizeof *cand); 1004 1005 cand->file = name; 1006 cand->prefix = prefix; 1007 cand->suff = Suffix_Ref(suff); 1008 cand->parent = parent; 1009 cand->node = gn; 1010 cand->numChildren = 0; 1011 #ifdef DEBUG_SRC 1012 Lst_Init(&cand->childrenList); 1013 #endif 1014 1015 return cand; 1016 } 1017 1018 /* Add a new candidate to the list. */ 1019 /*ARGSUSED*/ 1020 static void 1021 CandidateList_Add(CandidateList *list, char *srcName, Candidate *targ, 1022 Suffix *suff, const char *debug_tag MAKE_ATTR_UNUSED) 1023 { 1024 Candidate *cand = Candidate_New(srcName, targ->prefix, suff, targ, 1025 NULL); 1026 targ->numChildren++; 1027 Lst_Append(list, cand); 1028 1029 #ifdef DEBUG_SRC 1030 Lst_Append(&targ->childrenList, cand); 1031 debug_printf("%s add suff %p:%s candidate %p:%s to list %p:", 1032 debug_tag, targ, targ->file, cand, cand->file, list); 1033 CandidateList_PrintAddrs(list); 1034 #endif 1035 } 1036 1037 /* 1038 * Add all candidates to the list that can be formed by applying a suffix to 1039 * the candidate. 1040 */ 1041 static void 1042 CandidateList_AddCandidatesFor(CandidateList *list, Candidate *cand) 1043 { 1044 SuffixListNode *ln; 1045 for (ln = cand->suff->children.first; ln != NULL; ln = ln->next) { 1046 Suffix *suff = ln->datum; 1047 1048 if (suff->isNull && suff->name[0] != '\0') { 1049 /* 1050 * If the suffix has been marked as the NULL suffix, 1051 * also create a candidate for a file with no suffix 1052 * attached. 1053 */ 1054 CandidateList_Add(list, bmake_strdup(cand->prefix), 1055 cand, suff, "1"); 1056 } 1057 1058 CandidateList_Add(list, str_concat2(cand->prefix, suff->name), 1059 cand, suff, "2"); 1060 } 1061 } 1062 1063 /* 1064 * Free the first candidate in the list that is not referenced anymore. 1065 * Return whether a candidate was removed. 1066 */ 1067 static bool 1068 RemoveCandidate(CandidateList *srcs) 1069 { 1070 CandidateListNode *ln; 1071 1072 #ifdef DEBUG_SRC 1073 debug_printf("cleaning list %p:", srcs); 1074 CandidateList_PrintAddrs(srcs); 1075 #endif 1076 1077 for (ln = srcs->first; ln != NULL; ln = ln->next) { 1078 Candidate *src = ln->datum; 1079 1080 if (src->numChildren == 0) { 1081 if (src->parent == NULL) 1082 free(src->prefix); 1083 else { 1084 #ifdef DEBUG_SRC 1085 /* XXX: Lst_RemoveDatum */ 1086 CandidateListNode *ln2; 1087 ln2 = Lst_FindDatum(&src->parent->childrenList, 1088 src); 1089 if (ln2 != NULL) 1090 Lst_Remove(&src->parent->childrenList, 1091 ln2); 1092 #endif 1093 src->parent->numChildren--; 1094 } 1095 #ifdef DEBUG_SRC 1096 debug_printf("free: list %p src %p:%s children %d\n", 1097 srcs, src, src->file, src->numChildren); 1098 Lst_Done(&src->childrenList); 1099 #endif 1100 Lst_Remove(srcs, ln); 1101 free(src->file); 1102 free(src); 1103 return true; 1104 } 1105 #ifdef DEBUG_SRC 1106 else { 1107 debug_printf("keep: list %p src %p:%s children %d:", 1108 srcs, src, src->file, src->numChildren); 1109 CandidateList_PrintAddrs(&src->childrenList); 1110 } 1111 #endif 1112 } 1113 1114 return false; 1115 } 1116 1117 /* Find the first existing file/target in srcs. */ 1118 static Candidate * 1119 FindThem(CandidateList *srcs, CandidateSearcher *cs) 1120 { 1121 HashSet seen; 1122 1123 HashSet_Init(&seen); 1124 1125 while (!Lst_IsEmpty(srcs)) { 1126 Candidate *src = Lst_Dequeue(srcs); 1127 1128 #ifdef DEBUG_SRC 1129 debug_printf("remove from list %p src %p:%s\n", 1130 srcs, src, src->file); 1131 #endif 1132 DEBUG1(SUFF, "\ttrying %s...", src->file); 1133 1134 /* 1135 * A file is considered to exist if either a node exists in the 1136 * graph for it or the file actually exists. 1137 */ 1138 if (Targ_FindNode(src->file) != NULL) { 1139 found: 1140 HashSet_Done(&seen); 1141 DEBUG0(SUFF, "got it\n"); 1142 return src; 1143 } 1144 1145 { 1146 char *file = Dir_FindFile(src->file, 1147 src->suff->searchPath); 1148 if (file != NULL) { 1149 free(file); 1150 goto found; 1151 } 1152 } 1153 1154 DEBUG0(SUFF, "not there\n"); 1155 1156 if (HashSet_Add(&seen, src->file)) 1157 CandidateList_AddCandidatesFor(srcs, src); 1158 else { 1159 DEBUG1(SUFF, "FindThem: skipping duplicate \"%s\"\n", 1160 src->file); 1161 } 1162 1163 CandidateSearcher_Add(cs, src); 1164 } 1165 1166 HashSet_Done(&seen); 1167 return NULL; 1168 } 1169 1170 /* 1171 * See if any of the children of the candidate's GNode is one from which the 1172 * target can be transformed. If there is one, a candidate is put together 1173 * for it and returned. 1174 */ 1175 static Candidate * 1176 FindCmds(Candidate *targ, CandidateSearcher *cs) 1177 { 1178 GNodeListNode *gln; 1179 GNode *tgn; /* Target GNode */ 1180 GNode *sgn; /* Source GNode */ 1181 size_t prefLen; /* The length of the defined prefix */ 1182 Suffix *suff; /* Suffix of the matching candidate */ 1183 Candidate *ret; /* Return value */ 1184 1185 tgn = targ->node; 1186 prefLen = strlen(targ->prefix); 1187 1188 for (gln = tgn->children.first; gln != NULL; gln = gln->next) { 1189 const char *base; 1190 1191 sgn = gln->datum; 1192 1193 if (sgn->type & OP_OPTIONAL && Lst_IsEmpty(&tgn->commands)) { 1194 /* 1195 * We haven't looked to see if .OPTIONAL files exist 1196 * yet, so don't use one as the implicit source. 1197 * This allows us to use .OPTIONAL in .depend files so 1198 * make won't complain "don't know how to make xxx.h" 1199 * when a dependent file has been moved/deleted. 1200 */ 1201 continue; 1202 } 1203 1204 base = str_basename(sgn->name); 1205 if (strncmp(base, targ->prefix, prefLen) != 0) 1206 continue; 1207 /* 1208 * The node matches the prefix, see if it has a known suffix. 1209 */ 1210 suff = FindSuffixByName(base + prefLen); 1211 if (suff == NULL) 1212 continue; 1213 1214 /* 1215 * It even has a known suffix, see if there's a transformation 1216 * defined between the node's suffix and the target's suffix. 1217 * 1218 * XXX: Handle multi-stage transformations here, too. 1219 */ 1220 1221 if (Lst_FindDatum(&suff->parents, targ->suff) != NULL) 1222 break; 1223 } 1224 1225 if (gln == NULL) 1226 return NULL; 1227 1228 ret = Candidate_New(bmake_strdup(sgn->name), targ->prefix, suff, targ, 1229 sgn); 1230 targ->numChildren++; 1231 #ifdef DEBUG_SRC 1232 debug_printf("3 add targ %p:%s ret %p:%s\n", 1233 targ, targ->file, ret, ret->file); 1234 Lst_Append(&targ->childrenList, ret); 1235 #endif 1236 CandidateSearcher_Add(cs, ret); 1237 DEBUG1(SUFF, "\tusing existing source %s\n", sgn->name); 1238 return ret; 1239 } 1240 1241 static void 1242 ExpandWildcards(GNodeListNode *cln, GNode *pgn) 1243 { 1244 GNode *cgn = cln->datum; 1245 StringList expansions; 1246 1247 if (!Dir_HasWildcards(cgn->name)) 1248 return; 1249 1250 /* Expand the word along the chosen path. */ 1251 Lst_Init(&expansions); 1252 SearchPath_Expand(Suff_FindPath(cgn), cgn->name, &expansions); 1253 1254 while (!Lst_IsEmpty(&expansions)) { 1255 GNode *gn; 1256 /* 1257 * Fetch next expansion off the list and find its GNode 1258 */ 1259 char *name = Lst_Dequeue(&expansions); 1260 1261 DEBUG1(SUFF, "%s...", name); 1262 gn = Targ_GetNode(name); 1263 1264 /* Insert gn before the original child. */ 1265 Lst_InsertBefore(&pgn->children, cln, gn); 1266 Lst_Append(&gn->parents, pgn); 1267 pgn->unmade++; 1268 } 1269 1270 Lst_Done(&expansions); 1271 1272 DEBUG0(SUFF, "\n"); 1273 1274 /* 1275 * Now that the source is expanded, remove it from the list of 1276 * children, to keep it from being processed. 1277 */ 1278 pgn->unmade--; 1279 Lst_Remove(&pgn->children, cln); 1280 Lst_Remove(&cgn->parents, Lst_FindDatum(&cgn->parents, pgn)); 1281 } 1282 1283 /* 1284 * Break the result into a vector of strings whose nodes we can find, then 1285 * add those nodes to the members list. 1286 * 1287 * Unfortunately, we can't use Str_Words because it doesn't understand about 1288 * expressions with spaces in them. 1289 */ 1290 static void 1291 ExpandChildrenRegular(char *p, GNode *pgn, GNodeList *members) 1292 { 1293 char *start; 1294 1295 pp_skip_hspace(&p); 1296 start = p; 1297 while (*p != '\0') { 1298 if (*p == ' ' || *p == '\t') { 1299 GNode *gn; 1300 /* 1301 * White-space -- terminate element, find the node, 1302 * add it, skip any further spaces. 1303 */ 1304 *p++ = '\0'; 1305 gn = Targ_GetNode(start); 1306 Lst_Append(members, gn); 1307 pp_skip_hspace(&p); 1308 /* Continue at the next non-space. */ 1309 start = p; 1310 } else if (*p == '$') { 1311 /* Skip over the expression. */ 1312 const char *nested_p = p; 1313 FStr junk = Var_Parse(&nested_p, pgn, VARE_PARSE_ONLY); 1314 /* TODO: handle errors */ 1315 if (junk.str == var_Error) { 1316 Parse_Error(PARSE_FATAL, 1317 "Malformed expression at \"%s\"", 1318 p); 1319 p++; 1320 } else { 1321 p += nested_p - p; 1322 } 1323 1324 FStr_Done(&junk); 1325 } else if (p[0] == '\\' && p[1] != '\0') { 1326 /* Escaped something -- skip over it. */ 1327 /* 1328 * XXX: In other places, escaping at this syntactical 1329 * position is done by a '$', not a '\'. The '\' is 1330 * only used in variable modifiers. 1331 */ 1332 p += 2; 1333 } else { 1334 p++; 1335 } 1336 } 1337 1338 if (p != start) { 1339 /* 1340 * Stuff left over -- add it to the list too 1341 */ 1342 GNode *gn = Targ_GetNode(start); 1343 Lst_Append(members, gn); 1344 } 1345 } 1346 1347 /* 1348 * Expand the names of any children of a given node that contain 1349 * expressions or file wildcards into actual targets. 1350 * 1351 * The expanded node is removed from the parent's list of children, and the 1352 * parent's unmade counter is decremented, but other nodes may be added. 1353 * 1354 * Input: 1355 * cln Child to examine 1356 * pgn Parent node being processed 1357 */ 1358 static void 1359 ExpandChildren(GNodeListNode *cln, GNode *pgn) 1360 { 1361 GNode *cgn = cln->datum; 1362 char *expanded; 1363 1364 if (!Lst_IsEmpty(&cgn->order_pred) || !Lst_IsEmpty(&cgn->order_succ)) 1365 /* It is all too hard to process the result of .ORDER */ 1366 return; 1367 1368 if (cgn->type & OP_WAIT) 1369 /* Ignore these (& OP_PHONY ?) */ 1370 return; 1371 1372 /* 1373 * First do variable expansion -- this takes precedence over wildcard 1374 * expansion. If the result contains wildcards, they'll be gotten to 1375 * later since the resulting words are tacked on to the end of the 1376 * children list. 1377 */ 1378 if (strchr(cgn->name, '$') == NULL) { 1379 ExpandWildcards(cln, pgn); 1380 return; 1381 } 1382 1383 DEBUG1(SUFF, "Expanding \"%s\"...", cgn->name); 1384 expanded = Var_Subst(cgn->name, pgn, VARE_UNDEFERR); 1385 /* TODO: handle errors */ 1386 1387 { 1388 GNodeList members = LST_INIT; 1389 1390 if (cgn->type & OP_ARCHV) { 1391 /* 1392 * Node was an 'archive(member)' target, so 1393 * call on the Arch module to find the nodes for us, 1394 * expanding variables in the parent's scope. 1395 */ 1396 char *ap = expanded; 1397 (void)Arch_ParseArchive(&ap, &members, pgn); 1398 } else { 1399 ExpandChildrenRegular(expanded, pgn, &members); 1400 } 1401 1402 /* Add all members to the parent node. */ 1403 while (!Lst_IsEmpty(&members)) { 1404 GNode *gn = Lst_Dequeue(&members); 1405 1406 DEBUG1(SUFF, "%s...", gn->name); 1407 Lst_InsertBefore(&pgn->children, cln, gn); 1408 Lst_Append(&gn->parents, pgn); 1409 pgn->unmade++; 1410 ExpandWildcards(cln->prev, pgn); 1411 } 1412 Lst_Done(&members); 1413 1414 free(expanded); 1415 } 1416 1417 DEBUG0(SUFF, "\n"); 1418 1419 /* 1420 * The source is expanded now, so remove it from the list of children, 1421 * to keep it from being processed. 1422 */ 1423 pgn->unmade--; 1424 Lst_Remove(&pgn->children, cln); 1425 Lst_Remove(&cgn->parents, Lst_FindDatum(&cgn->parents, pgn)); 1426 } 1427 1428 static void 1429 ExpandAllChildren(GNode *gn) 1430 { 1431 GNodeListNode *ln, *nln; 1432 1433 for (ln = gn->children.first; ln != NULL; ln = nln) { 1434 nln = ln->next; 1435 ExpandChildren(ln, gn); 1436 } 1437 } 1438 1439 /* 1440 * Find a path along which to search or expand the node. 1441 * 1442 * If the node has a known suffix, use that path, 1443 * otherwise use the default system search path. 1444 */ 1445 SearchPath * 1446 Suff_FindPath(GNode *gn) 1447 { 1448 Suffix *suff = gn->suffix; 1449 1450 if (suff == NULL) { 1451 char *name = gn->name; 1452 size_t nameLen = strlen(gn->name); 1453 SuffixListNode *ln; 1454 for (ln = sufflist.first; ln != NULL; ln = ln->next) 1455 if (Suffix_IsSuffix(ln->datum, nameLen, name + nameLen)) 1456 break; 1457 1458 DEBUG1(SUFF, "Wildcard expanding \"%s\"...", gn->name); 1459 if (ln != NULL) 1460 suff = ln->datum; 1461 /* 1462 * XXX: Here we can save the suffix so we don't have to do 1463 * this again. 1464 */ 1465 } 1466 1467 if (suff != NULL) { 1468 DEBUG1(SUFF, "suffix is \"%s\"...\n", suff->name); 1469 return suff->searchPath; 1470 } else { 1471 DEBUG0(SUFF, "\n"); 1472 return &dirSearchPath; /* Use default search path */ 1473 } 1474 } 1475 1476 /* 1477 * Apply a transformation rule, given the source and target nodes and 1478 * suffixes. 1479 * 1480 * The source and target are linked and the commands from the transformation 1481 * are added to the target node's commands list. The target also inherits all 1482 * the sources for the transformation rule. 1483 * 1484 * Results: 1485 * true if successful, false if not. 1486 */ 1487 static bool 1488 ApplyTransform(GNode *tgn, GNode *sgn, Suffix *tsuff, Suffix *ssuff) 1489 { 1490 GNodeListNode *ln; 1491 char *tname; /* Name of transformation rule */ 1492 GNode *gn; /* Node for the transformation rule */ 1493 1494 /* Form the proper links between the target and source. */ 1495 Lst_Append(&tgn->children, sgn); 1496 Lst_Append(&sgn->parents, tgn); 1497 tgn->unmade++; 1498 1499 /* Locate the transformation rule itself. */ 1500 tname = str_concat2(ssuff->name, tsuff->name); 1501 gn = FindTransformByName(tname); 1502 free(tname); 1503 1504 /* This can happen when linking an OP_MEMBER and OP_ARCHV node. */ 1505 if (gn == NULL) 1506 return false; 1507 1508 DEBUG3(SUFF, "\tapplying %s -> %s to \"%s\"\n", 1509 ssuff->name, tsuff->name, tgn->name); 1510 1511 /* Record last child; Make_HandleUse may add child nodes. */ 1512 ln = tgn->children.last; 1513 1514 /* Apply the rule. */ 1515 Make_HandleUse(gn, tgn); 1516 1517 /* Deal with wildcards and expressions in any acquired sources. */ 1518 ln = ln != NULL ? ln->next : NULL; 1519 while (ln != NULL) { 1520 GNodeListNode *nln = ln->next; 1521 ExpandChildren(ln, tgn); 1522 ln = nln; 1523 } 1524 1525 /* 1526 * Keep track of another parent to which this node is transformed so 1527 * the .IMPSRC variable can be set correctly for the parent. 1528 */ 1529 Lst_Append(&sgn->implicitParents, tgn); 1530 1531 return true; 1532 } 1533 1534 /* 1535 * Member has a known suffix, so look for a transformation rule from 1536 * it to a possible suffix of the archive. 1537 * 1538 * Rather than searching through the entire list, we just look at 1539 * suffixes to which the member's suffix may be transformed. 1540 */ 1541 static void 1542 ExpandMember(GNode *gn, const char *eoarch, GNode *mem, Suffix *memSuff) 1543 { 1544 SuffixListNode *ln; 1545 size_t nameLen = (size_t)(eoarch - gn->name); 1546 1547 /* Use first matching suffix... */ 1548 for (ln = memSuff->parents.first; ln != NULL; ln = ln->next) 1549 if (Suffix_IsSuffix(ln->datum, nameLen, eoarch)) 1550 break; 1551 1552 if (ln != NULL) { 1553 Suffix *suff = ln->datum; 1554 if (!ApplyTransform(gn, mem, suff, memSuff)) { 1555 DEBUG2(SUFF, "\tNo transformation from %s -> %s\n", 1556 memSuff->name, suff->name); 1557 } 1558 } 1559 } 1560 1561 static void FindDeps(GNode *, CandidateSearcher *); 1562 1563 /* 1564 * Locate dependencies for an OP_ARCHV node. 1565 * 1566 * Side Effects: 1567 * Same as Suff_FindDeps 1568 */ 1569 static void 1570 FindDepsArchive(GNode *gn, CandidateSearcher *cs) 1571 { 1572 char *eoarch; /* End of archive portion */ 1573 char *eoname; /* End of member portion */ 1574 GNode *mem; /* Node for member */ 1575 Suffix *memSuff; 1576 const char *name; /* Start of member's name */ 1577 1578 /* 1579 * The node is an 'archive(member)' pair, so we must find a 1580 * suffix for both of them. 1581 */ 1582 eoarch = strchr(gn->name, '('); 1583 eoname = strchr(eoarch, ')'); 1584 1585 /* 1586 * Caller guarantees the format `libname(member)', via 1587 * Arch_ParseArchive. 1588 */ 1589 assert(eoarch != NULL); 1590 assert(eoname != NULL); 1591 1592 *eoname = '\0'; /* Nuke parentheses during suffix search */ 1593 *eoarch = '\0'; /* So a suffix can be found */ 1594 1595 name = eoarch + 1; 1596 1597 /* 1598 * To simplify things, call Suff_FindDeps recursively on the member 1599 * now, so we can simply compare the member's .PREFIX and .TARGET 1600 * variables to locate its suffix. This allows us to figure out the 1601 * suffix to use for the archive without having to do a quadratic 1602 * search over the suffix list, backtracking for each one. 1603 */ 1604 mem = Targ_GetNode(name); 1605 FindDeps(mem, cs); 1606 1607 /* Create the link between the two nodes right off. */ 1608 Lst_Append(&gn->children, mem); 1609 Lst_Append(&mem->parents, gn); 1610 gn->unmade++; 1611 1612 /* Copy in the variables from the member node to this one. */ 1613 Var_Set(gn, PREFIX, GNode_VarPrefix(mem)); 1614 Var_Set(gn, TARGET, GNode_VarTarget(mem)); 1615 1616 memSuff = mem->suffix; 1617 if (memSuff == NULL) { /* Didn't know what it was. */ 1618 DEBUG0(SUFF, "using null suffix\n"); 1619 memSuff = nullSuff; 1620 } 1621 1622 1623 /* Set the other two local variables required for this target. */ 1624 Var_Set(gn, MEMBER, name); 1625 Var_Set(gn, ARCHIVE, gn->name); 1626 /* Set $@ for compatibility with other makes. */ 1627 Var_Set(gn, TARGET, gn->name); 1628 1629 /* 1630 * Now we've got the important local variables set, expand any sources 1631 * that still contain variables or wildcards in their names. 1632 */ 1633 ExpandAllChildren(gn); 1634 1635 if (memSuff != NULL) 1636 ExpandMember(gn, eoarch, mem, memSuff); 1637 1638 /* 1639 * Replace the opening and closing parens now we've no need of the 1640 * separate pieces. 1641 */ 1642 *eoarch = '('; 1643 *eoname = ')'; 1644 1645 /* 1646 * Pretend gn appeared to the left of a dependency operator so the 1647 * user needn't provide a transformation from the member to the 1648 * archive. 1649 */ 1650 if (!GNode_IsTarget(gn)) 1651 gn->type |= OP_DEPENDS; 1652 1653 /* 1654 * Flag the member as such so we remember to look in the archive for 1655 * its modification time. The OP_JOIN | OP_MADE is needed because 1656 * this target should never get made. 1657 */ 1658 mem->type |= OP_MEMBER | OP_JOIN | OP_MADE; 1659 } 1660 1661 /* 1662 * If the node is a library, it is the arch module's job to find it 1663 * and set the TARGET variable accordingly. We merely provide the 1664 * search path, assuming all libraries end in ".a" (if the suffix 1665 * hasn't been defined, there's nothing we can do for it, so we just 1666 * set the TARGET variable to the node's name in order to give it a 1667 * value). 1668 */ 1669 static void 1670 FindDepsLib(GNode *gn) 1671 { 1672 Suffix *suff = FindSuffixByName(LIBSUFF); 1673 if (suff != NULL) { 1674 Suffix_Reassign(&gn->suffix, suff); 1675 Arch_FindLib(gn, suff->searchPath); 1676 } else { 1677 Suffix_Unassign(&gn->suffix); 1678 Var_Set(gn, TARGET, gn->name); 1679 } 1680 1681 /* 1682 * Because a library (-lfoo) target doesn't follow the standard 1683 * filesystem conventions, we don't set the regular variables for 1684 * the thing. .PREFIX is simply made empty. 1685 */ 1686 Var_Set(gn, PREFIX, ""); 1687 } 1688 1689 static void 1690 FindDepsRegularKnown(const char *name, size_t nameLen, GNode *gn, 1691 CandidateList *srcs, CandidateList *targs) 1692 { 1693 SuffixListNode *ln; 1694 Candidate *targ; 1695 char *pref; 1696 1697 for (ln = sufflist.first; ln != NULL; ln = ln->next) { 1698 Suffix *suff = ln->datum; 1699 if (!Suffix_IsSuffix(suff, nameLen, name + nameLen)) 1700 continue; 1701 1702 pref = bmake_strldup(name, (size_t)(nameLen - suff->nameLen)); 1703 targ = Candidate_New(bmake_strdup(gn->name), pref, suff, NULL, 1704 gn); 1705 1706 CandidateList_AddCandidatesFor(srcs, targ); 1707 1708 /* Record the target so we can nuke it. */ 1709 Lst_Append(targs, targ); 1710 } 1711 } 1712 1713 static void 1714 FindDepsRegularUnknown(GNode *gn, const char *sopref, 1715 CandidateList *srcs, CandidateList *targs) 1716 { 1717 Candidate *targ; 1718 1719 if (!Lst_IsEmpty(targs) || nullSuff == NULL) 1720 return; 1721 1722 DEBUG1(SUFF, "\tNo known suffix on %s. Using .NULL suffix\n", gn->name); 1723 1724 targ = Candidate_New(bmake_strdup(gn->name), bmake_strdup(sopref), 1725 nullSuff, NULL, gn); 1726 1727 /* 1728 * Only use the default suffix rules if we don't have commands 1729 * defined for this gnode; traditional make programs used to not 1730 * define suffix rules if the gnode had children but we don't do 1731 * this anymore. 1732 */ 1733 if (Lst_IsEmpty(&gn->commands)) 1734 CandidateList_AddCandidatesFor(srcs, targ); 1735 else { 1736 DEBUG0(SUFF, "not "); 1737 } 1738 1739 DEBUG0(SUFF, "adding suffix rules\n"); 1740 1741 Lst_Append(targs, targ); 1742 } 1743 1744 /* 1745 * Deal with finding the thing on the default search path. We always do 1746 * that, not only if the node is only a source (not on the lhs of a 1747 * dependency operator or [XXX] it has neither children or commands) as 1748 * the old pmake did. 1749 */ 1750 static void 1751 FindDepsRegularPath(GNode *gn, Candidate *targ) 1752 { 1753 if (gn->type & (OP_PHONY | OP_NOPATH)) 1754 return; 1755 1756 free(gn->path); 1757 gn->path = Dir_FindFile(gn->name, 1758 targ == NULL ? &dirSearchPath : targ->suff->searchPath); 1759 if (gn->path == NULL) 1760 return; 1761 1762 Var_Set(gn, TARGET, gn->path); 1763 1764 if (targ != NULL) { 1765 /* 1766 * Suffix known for the thing -- trim the suffix off 1767 * the path to form the proper .PREFIX variable. 1768 */ 1769 size_t savep = strlen(gn->path) - targ->suff->nameLen; 1770 char savec; 1771 1772 Suffix_Reassign(&gn->suffix, targ->suff); 1773 1774 savec = gn->path[savep]; 1775 gn->path[savep] = '\0'; 1776 1777 Var_Set(gn, PREFIX, str_basename(gn->path)); 1778 1779 gn->path[savep] = savec; 1780 } else { 1781 /* 1782 * The .PREFIX gets the full path if the target has no 1783 * known suffix. 1784 */ 1785 Suffix_Unassign(&gn->suffix); 1786 Var_Set(gn, PREFIX, str_basename(gn->path)); 1787 } 1788 } 1789 1790 /* 1791 * Locate implicit dependencies for regular targets. 1792 * 1793 * Input: 1794 * gn Node for which to find sources 1795 * 1796 * Side Effects: 1797 * Same as Suff_FindDeps 1798 */ 1799 static void 1800 FindDepsRegular(GNode *gn, CandidateSearcher *cs) 1801 { 1802 /* List of sources at which to look */ 1803 CandidateList srcs = LST_INIT; 1804 /* 1805 * List of targets to which things can be transformed. 1806 * They all have the same file, but different suff and prefix fields. 1807 */ 1808 CandidateList targs = LST_INIT; 1809 Candidate *bottom; /* Start of found transformation path */ 1810 Candidate *src; 1811 Candidate *targ; 1812 1813 const char *name = gn->name; 1814 size_t nameLen = strlen(name); 1815 1816 #ifdef DEBUG_SRC 1817 DEBUG1(SUFF, "FindDepsRegular \"%s\"\n", gn->name); 1818 #endif 1819 1820 /* 1821 * We're caught in a catch-22 here. On the one hand, we want to use 1822 * any transformation implied by the target's sources, but we can't 1823 * examine the sources until we've expanded any variables/wildcards 1824 * they may hold, and we can't do that until we've set up the 1825 * target's local variables and we can't do that until we know what 1826 * the proper suffix for the target is (in case there are two 1827 * suffixes one of which is a suffix of the other) and we can't know 1828 * that until we've found its implied source, which we may not want 1829 * to use if there's an existing source that implies a different 1830 * transformation. 1831 * 1832 * In an attempt to get around this, which may not work all the time, 1833 * but should work most of the time, we look for implied sources 1834 * first, checking transformations to all possible suffixes of the 1835 * target, use what we find to set the target's local variables, 1836 * expand the children, then look for any overriding transformations 1837 * they imply. Should we find one, we discard the one we found before. 1838 */ 1839 bottom = NULL; 1840 targ = NULL; 1841 1842 if (!(gn->type & OP_PHONY)) { 1843 1844 FindDepsRegularKnown(name, nameLen, gn, &srcs, &targs); 1845 1846 /* Handle target of unknown suffix... */ 1847 FindDepsRegularUnknown(gn, name, &srcs, &targs); 1848 1849 /* 1850 * Using the list of possible sources built up from the target 1851 * suffix(es), try and find an existing file/target that 1852 * matches. 1853 */ 1854 bottom = FindThem(&srcs, cs); 1855 1856 if (bottom == NULL) { 1857 /* 1858 * No known transformations -- use the first suffix 1859 * found for setting the local variables. 1860 */ 1861 if (targs.first != NULL) 1862 targ = targs.first->datum; 1863 else 1864 targ = NULL; 1865 } else { 1866 /* 1867 * Work up the transformation path to find the suffix 1868 * of the target to which the transformation was made. 1869 */ 1870 for (targ = bottom; 1871 targ->parent != NULL; targ = targ->parent) 1872 continue; 1873 } 1874 } 1875 1876 Var_Set(gn, TARGET, GNode_Path(gn)); 1877 Var_Set(gn, PREFIX, targ != NULL ? targ->prefix : gn->name); 1878 1879 /* 1880 * Now we've got the important local variables set, expand any sources 1881 * that still contain variables or wildcards in their names. 1882 */ 1883 { 1884 GNodeListNode *ln, *nln; 1885 for (ln = gn->children.first; ln != NULL; ln = nln) { 1886 nln = ln->next; 1887 ExpandChildren(ln, gn); 1888 } 1889 } 1890 1891 if (targ == NULL) { 1892 DEBUG1(SUFF, "\tNo valid suffix on %s\n", gn->name); 1893 1894 sfnd_abort: 1895 FindDepsRegularPath(gn, targ); 1896 goto sfnd_return; 1897 } 1898 1899 /* 1900 * If the suffix indicates that the target is a library, mark that in 1901 * the node's type field. 1902 */ 1903 if (targ->suff->library) 1904 gn->type |= OP_LIB; 1905 1906 /* 1907 * Check for overriding transformation rule implied by sources 1908 */ 1909 if (!Lst_IsEmpty(&gn->children)) { 1910 src = FindCmds(targ, cs); 1911 1912 if (src != NULL) { 1913 /* 1914 * Free up all the candidates in the transformation 1915 * path, up to but not including the parent node. 1916 */ 1917 while (bottom != NULL && bottom->parent != NULL) { 1918 CandidateSearcher_AddIfNew(cs, bottom); 1919 bottom = bottom->parent; 1920 } 1921 bottom = src; 1922 } 1923 } 1924 1925 if (bottom == NULL) { 1926 /* No idea from where it can come -- return now. */ 1927 goto sfnd_abort; 1928 } 1929 1930 /* 1931 * We now have a list of candidates headed by 'bottom' and linked via 1932 * their 'parent' pointers. What we do next is create links between 1933 * source and target nodes (which may or may not have been created) 1934 * and set the necessary local variables in each target. 1935 * 1936 * The commands for each target are set from the commands of the 1937 * transformation rule used to get from the src suffix to the targ 1938 * suffix. Note that this causes the commands list of the original 1939 * node, gn, to be replaced with the commands of the final 1940 * transformation rule. 1941 */ 1942 if (bottom->node == NULL) 1943 bottom->node = Targ_GetNode(bottom->file); 1944 1945 for (src = bottom; src->parent != NULL; src = src->parent) { 1946 targ = src->parent; 1947 1948 Suffix_Reassign(&src->node->suffix, src->suff); 1949 1950 if (targ->node == NULL) 1951 targ->node = Targ_GetNode(targ->file); 1952 1953 ApplyTransform(targ->node, src->node, 1954 targ->suff, src->suff); 1955 1956 if (targ->node != gn) { 1957 /* 1958 * Finish off the dependency-search process for any 1959 * nodes between bottom and gn (no point in questing 1960 * around the filesystem for their implicit source 1961 * when it's already known). Note that the node 1962 * can't have any sources that need expanding, since 1963 * SuffFindThem will stop on an existing node, so all 1964 * we need to do is set the standard variables. 1965 */ 1966 targ->node->type |= OP_DEPS_FOUND; 1967 Var_Set(targ->node, PREFIX, targ->prefix); 1968 Var_Set(targ->node, TARGET, targ->node->name); 1969 } 1970 } 1971 1972 Suffix_Reassign(&gn->suffix, src->suff); 1973 1974 /* 1975 * Nuke the transformation path and the candidates left over in the 1976 * two lists. 1977 */ 1978 sfnd_return: 1979 if (bottom != NULL) 1980 CandidateSearcher_AddIfNew(cs, bottom); 1981 1982 while (RemoveCandidate(&srcs) || RemoveCandidate(&targs)) 1983 continue; 1984 1985 CandidateSearcher_MoveAll(cs, &srcs); 1986 CandidateSearcher_MoveAll(cs, &targs); 1987 } 1988 1989 static void 1990 CandidateSearcher_CleanUp(CandidateSearcher *cs) 1991 { 1992 while (RemoveCandidate(&cs->list)) 1993 continue; 1994 assert(Lst_IsEmpty(&cs->list)); 1995 } 1996 1997 1998 /* 1999 * Find implicit sources for the target. 2000 * 2001 * Nodes are added to the graph as children of the passed-in node. The nodes 2002 * are marked to have their IMPSRC variable filled in. The PREFIX variable 2003 * is set for the given node and all its implied children. 2004 * 2005 * The path found by this target is the shortest path in the transformation 2006 * graph, which may pass through nonexistent targets, to an existing target. 2007 * The search continues on all paths from the root suffix until a file is 2008 * found. I.e. if there's a path .o -> .c -> .l -> .l,v from the root and the 2009 * .l,v file exists but the .c and .l files don't, the search will branch out 2010 * in all directions from .o and again from all the nodes on the next level 2011 * until the .l,v node is encountered. 2012 */ 2013 void 2014 Suff_FindDeps(GNode *gn) 2015 { 2016 CandidateSearcher cs; 2017 2018 CandidateSearcher_Init(&cs); 2019 2020 FindDeps(gn, &cs); 2021 2022 CandidateSearcher_CleanUp(&cs); 2023 CandidateSearcher_Done(&cs); 2024 } 2025 2026 static void 2027 FindDeps(GNode *gn, CandidateSearcher *cs) 2028 { 2029 if (gn->type & OP_DEPS_FOUND) 2030 return; 2031 gn->type |= OP_DEPS_FOUND; 2032 2033 /* Make sure we have these set, may get revised below. */ 2034 Var_Set(gn, TARGET, GNode_Path(gn)); 2035 Var_Set(gn, PREFIX, gn->name); 2036 2037 DEBUG1(SUFF, "SuffFindDeps \"%s\"\n", gn->name); 2038 2039 if (gn->type & OP_ARCHV) 2040 FindDepsArchive(gn, cs); 2041 else if (gn->type & OP_LIB) 2042 FindDepsLib(gn); 2043 else 2044 FindDepsRegular(gn, cs); 2045 } 2046 2047 /* 2048 * Define which suffix is the null suffix. 2049 * 2050 * Need to handle the changing of the null suffix gracefully so the old 2051 * transformation rules don't just go away. 2052 */ 2053 void 2054 Suff_SetNull(const char *name) 2055 { 2056 Suffix *suff = FindSuffixByName(name); 2057 if (suff == NULL) { 2058 Parse_Error(PARSE_WARNING, 2059 "Desired null suffix %s not defined", 2060 name); 2061 return; 2062 } 2063 2064 if (nullSuff != NULL) 2065 nullSuff->isNull = false; 2066 suff->isNull = true; 2067 /* XXX: Here's where the transformation mangling would take place. */ 2068 nullSuff = suff; 2069 } 2070 2071 /* Initialize the suffixes module. */ 2072 void 2073 Suff_Init(void) 2074 { 2075 /* 2076 * Create null suffix for single-suffix rules (POSIX). The thing 2077 * doesn't actually go on the suffix list or everyone will think 2078 * that's its suffix. 2079 */ 2080 Suff_ClearSuffixes(); 2081 } 2082 2083 2084 /* Clean up the suffixes module. */ 2085 void 2086 Suff_End(void) 2087 { 2088 #ifdef CLEANUP 2089 Lst_DoneCall(&sufflist, SuffFree); 2090 Lst_DoneCall(&suffClean, SuffFree); 2091 if (nullSuff != NULL) 2092 SuffFree(nullSuff); 2093 Lst_Done(&transforms); 2094 #endif 2095 } 2096 2097 2098 static void 2099 PrintSuffNames(const char *prefix, const SuffixList *suffs) 2100 { 2101 SuffixListNode *ln; 2102 2103 debug_printf("#\t%s: ", prefix); 2104 for (ln = suffs->first; ln != NULL; ln = ln->next) { 2105 const Suffix *suff = ln->datum; 2106 debug_printf("%s ", suff->name); 2107 } 2108 debug_printf("\n"); 2109 } 2110 2111 static void 2112 Suffix_Print(const Suffix *suff) 2113 { 2114 Buffer buf; 2115 2116 Buf_Init(&buf); 2117 Buf_AddFlag(&buf, suff->include, "SUFF_INCLUDE"); 2118 Buf_AddFlag(&buf, suff->library, "SUFF_LIBRARY"); 2119 Buf_AddFlag(&buf, suff->isNull, "SUFF_NULL"); 2120 2121 debug_printf("# \"%s\" (num %d, ref %d)", 2122 suff->name, suff->sNum, suff->refCount); 2123 if (buf.len > 0) 2124 debug_printf(" (%s)", buf.data); 2125 debug_printf("\n"); 2126 2127 Buf_Done(&buf); 2128 2129 PrintSuffNames("To", &suff->parents); 2130 PrintSuffNames("From", &suff->children); 2131 2132 debug_printf("#\tSearch Path: "); 2133 SearchPath_Print(suff->searchPath); 2134 debug_printf("\n"); 2135 } 2136 2137 static void 2138 PrintTransformation(GNode *t) 2139 { 2140 debug_printf("%-16s:", t->name); 2141 Targ_PrintType(t->type); 2142 debug_printf("\n"); 2143 Targ_PrintCmds(t); 2144 debug_printf("\n"); 2145 } 2146 2147 void 2148 Suff_PrintAll(void) 2149 { 2150 debug_printf("#*** Suffixes:\n"); 2151 { 2152 SuffixListNode *ln; 2153 for (ln = sufflist.first; ln != NULL; ln = ln->next) 2154 Suffix_Print(ln->datum); 2155 } 2156 2157 debug_printf("#*** Transformations:\n"); 2158 { 2159 GNodeListNode *ln; 2160 for (ln = transforms.first; ln != NULL; ln = ln->next) 2161 PrintTransformation(ln->datum); 2162 } 2163 } 2164 2165 char * 2166 Suff_NamesStr(void) 2167 { 2168 Buffer buf; 2169 SuffixListNode *ln; 2170 Suffix *suff; 2171 2172 Buf_Init(&buf); 2173 for (ln = sufflist.first; ln != NULL; ln = ln->next) { 2174 suff = ln->datum; 2175 if (ln != sufflist.first) 2176 Buf_AddByte(&buf, ' '); 2177 Buf_AddStr(&buf, suff->name); 2178 } 2179 return Buf_DoneData(&buf); 2180 } 2181