1 /* $OpenBSD: suff.c,v 1.90 2015/01/23 22:35:58 espie Exp $ */ 2 /* $NetBSD: suff.c,v 1.13 1996/11/06 17:59:25 christos Exp $ */ 3 4 /* 5 * Copyright (c) 1988, 1989, 1990, 1993 6 * The Regents of the University of California. All rights reserved. 7 * Copyright (c) 1989 by Berkeley Softworks 8 * All rights reserved. 9 * 10 * This code is derived from software contributed to Berkeley by 11 * Adam de Boor. 12 * 13 * Redistribution and use in source and binary forms, with or without 14 * modification, are permitted provided that the following conditions 15 * are met: 16 * 1. Redistributions of source code must retain the above copyright 17 * notice, this list of conditions and the following disclaimer. 18 * 2. Redistributions in binary form must reproduce the above copyright 19 * notice, this list of conditions and the following disclaimer in the 20 * documentation and/or other materials provided with the distribution. 21 * 3. Neither the name of the University nor the names of its contributors 22 * may be used to endorse or promote products derived from this software 23 * without specific prior written permission. 24 * 25 * THIS SOFTWARE IS PROVIDED BY THE REGENTS AND CONTRIBUTORS ``AS IS'' AND 26 * ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE 27 * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE 28 * ARE DISCLAIMED. IN NO EVENT SHALL THE REGENTS OR CONTRIBUTORS BE LIABLE 29 * FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL 30 * DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS 31 * OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) 32 * HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT 33 * LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY 34 * OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF 35 * SUCH DAMAGE. 36 */ 37 38 /*- 39 * suff.c -- 40 * Functions to maintain suffix lists and find implicit dependents 41 * using suffix transformation rules 42 * 43 * Interface: 44 * Suff_Init Initialize all things to do with suffixes. 45 * 46 * Suff_ClearSuffixes Clear out all the suffixes. 47 * 48 * Suff_AddSuffix Add the passed string as another known suffix. 49 * 50 * Suff_ParseAsTransform Line might be a suffix line, check it. 51 * If it's not, return NULL. Otherwise, add 52 * another transformation to the suffix graph. 53 * Returns GNode suitable for framing, I mean, 54 * tacking commands, attributes, etc. on. 55 * 56 * Suff_FindDeps Find implicit sources for and the location of 57 * a target based on its suffix. Returns the 58 * bottom-most node added to the graph or NULL 59 * if the target had no implicit sources. 60 */ 61 62 #include <ctype.h> 63 #include <signal.h> 64 #include <stddef.h> 65 #include <stdint.h> 66 #include <stdio.h> 67 #include <stdlib.h> 68 #include <string.h> 69 #include <ohash.h> 70 #include "config.h" 71 #include "defines.h" 72 #include "dir.h" 73 #include "direxpand.h" 74 #include "engine.h" 75 #include "arch.h" 76 #include "suff.h" 77 #include "var.h" 78 #include "targ.h" 79 #include "error.h" 80 #include "str.h" 81 #include "lst.h" 82 #include "memory.h" 83 #include "gnode.h" 84 #include "make.h" 85 #include "stats.h" 86 #include "dump.h" 87 88 /* XXX the suffixes hash is stored using a specific hash function, suitable 89 * for looking up suffixes in reverse. 90 */ 91 static struct ohash suffixes; 92 93 /* We remember the longest suffix, so we don't need to look beyond that. */ 94 size_t maxLen; 95 static LIST srclist; 96 97 /* Transforms (.c.o) are stored in another hash, independently from suffixes. 98 * When make sees a target, it checks whether it's currently parsable as a 99 * transform (according to the active suffixes). If yes, it's stored as a 100 * new transform. 101 * 102 * XXX 103 * But transforms DO NOT have a canonical decomposition as a set of suffixes, 104 * and will be used as necessary later, when looking up implicit rules for 105 * actual targets. 106 * 107 * For instance, a transform .a.b.c can be parsed as .a -> .b.c if suffixes 108 * .a and .b.c are active, and then LATER, reused as .a.b -> .c if suffixes 109 * .a.b and .c are active. 110 */ 111 static struct ohash transforms; 112 113 /* conflicts between suffixes are solved by suffix declaration order. */ 114 static int order = 0; 115 116 /* 117 * Structure describing an individual suffix. 118 */ 119 struct Suff_ { 120 size_t nameLen; /* optimisation: strlen(name) */ 121 short flags; 122 #define SUFF_ACTIVE 0x08 /* We never destroy suffixes and rules, */ 123 /* we just deactivate them. */ 124 #define SUFF_PATH 0x10 /* False suffix: actually, the path keyword */ 125 LIST searchPath; /* The path along which files of this suffix 126 * may be found */ 127 int order; /* order of declaration for conflict 128 * resolution. */ 129 LIST parents; /* List of Suff we have a transformation to */ 130 LIST children; /* List of Suff we have a transformation from */ 131 char name[1]; 132 }; 133 134 static struct ohash_info suff_info = { 135 offsetof(struct Suff_, name), NULL, 136 hash_calloc, hash_free, element_alloc 137 }; 138 139 /* 140 * Structure used in the search for implied sources. 141 */ 142 typedef struct Src_ { 143 char *file; /* The file to look for */ 144 char *prefix; /* Prefix from which file was formed */ 145 Suff *suff; /* The suffix on the file */ 146 struct Src_ *parent; /* The Src for which this is a source */ 147 GNode *node; /* The node describing the file */ 148 int children; /* Count of existing children (so we don't free 149 * this thing too early or never nuke it) */ 150 #ifdef DEBUG_SRC 151 LIST cp; /* Debug; children list */ 152 #endif 153 } Src; 154 155 /* 156 * A structure for passing more than one argument to the Lst-library-invoked 157 * function... 158 */ 159 typedef struct { 160 Lst l; 161 Src *s; 162 } LstSrc; 163 164 static Suff *emptySuff; /* The empty suffix required for POSIX 165 * single-suffix transformation rules */ 166 167 168 #define parse_transform(s, p, q) parse_transformi(s, s + strlen(s), p, q) 169 static bool parse_transformi(const char *, const char *, Suff **, Suff **); 170 #define new_suffix(s) new_suffixi(s, NULL) 171 static Suff *new_suffixi(const char *, const char *); 172 static void reverse_hash_add_char(uint32_t *, const char *); 173 static uint32_t reverse_hashi(const char *, const char **); 174 static unsigned int reverse_slot(struct ohash *, const char *, const char **); 175 static void clear_suffixes(void); 176 static void record_possible_suffix(Suff *, GNode *, char *, Lst, Lst); 177 static void record_possible_suffixes(GNode *, Lst, Lst); 178 static Suff *find_suffix_as_suffix(Lst, const char *, const char *); 179 static Suff *add_suffixi(const char *, const char *); 180 181 static void SuffInsert(Lst, Suff *); 182 static void SuffAddSrc(void *, void *); 183 static int SuffRemoveSrc(Lst); 184 static void SuffAddLevel(Lst, Src *); 185 static Src *SuffFindThem(Lst, Lst); 186 static Src *SuffFindCmds(Src *, Lst); 187 static void SuffExpandChildren(LstNode, GNode *); 188 static void SuffExpandVarChildren(LstNode, GNode *, GNode *); 189 static void SuffExpandWildChildren(LstNode, GNode *, GNode *); 190 static bool SuffApplyTransform(GNode *, GNode *, Suff *, Suff *); 191 static void SuffFindDeps(GNode *, Lst); 192 static void SuffFindArchiveDeps(GNode *, Lst); 193 static void SuffFindNormalDeps(GNode *, Lst); 194 static void SuffPrintName(void *); 195 static void SuffPrintSuff(void *); 196 static void SuffPrintTrans(GNode *); 197 198 #define find_suff(name) find_suffi(name, NULL) 199 static Suff *find_suffi(const char *, const char *); 200 static Suff *find_best_suffix(const char *, const char *); 201 static GNode *find_transform(const char *); 202 static GNode *find_or_create_transformi(const char *, const char *); 203 static void setup_paths(void); 204 static void build_suffixes_graph(void); 205 static void special_path_hack(void); 206 207 #ifdef DEBUG_SRC 208 static void PrintAddr(void *); 209 #endif 210 211 /* hash functions for the suffixes hash */ 212 /* add one char to the hash */ 213 static void 214 reverse_hash_add_char(uint32_t *pk, const char *s) 215 { 216 *pk = ((*pk << 2) | (*pk >> 30)) ^ *s; 217 } 218 219 /* build a full hash from end to start */ 220 static uint32_t 221 reverse_hashi(const char *s, const char **e) 222 { 223 const char *p; 224 uint32_t k; 225 226 if (*e == NULL) 227 *e = s + strlen(s); 228 p = *e; 229 if (p == s) 230 k = 0; 231 else 232 k = *--p; 233 while (p != s) { 234 reverse_hash_add_char(&k, --p); 235 } 236 return k; 237 } 238 239 static unsigned int 240 reverse_slot(struct ohash *h, const char *s, const char **e) 241 { 242 uint32_t hv; 243 244 hv = reverse_hashi(s, e); 245 return ohash_lookup_interval(h, s, *e, hv); 246 } 247 248 249 static char * 250 suffix_is_suffix(Suff *s, const char *str, const char *estr) 251 { 252 const char *p1; /* Pointer into suffix name */ 253 const char *p2; /* Pointer into string being examined */ 254 255 if (estr - str < (ptrdiff_t) s->nameLen) 256 return NULL; 257 p1 = s->name + s->nameLen; 258 p2 = estr; 259 260 while (p1 != s->name) { 261 p1--; 262 p2--; 263 if (*p1 != *p2) 264 return NULL; 265 } 266 267 return (char *)p2; 268 } 269 270 static Suff * 271 find_suffi(const char *name, const char *ename) 272 { 273 unsigned int slot; 274 #ifdef STATS_SUFF 275 STAT_SUFF_LOOKUP_NAME++; 276 #endif 277 slot = reverse_slot(&suffixes, name, &ename); 278 return ohash_find(&suffixes, slot); 279 } 280 281 static GNode * 282 find_transform(const char *name) 283 { 284 unsigned int slot; 285 286 #ifdef STATS_SUFF 287 STAT_TRANSFORM_LOOKUP_NAME++; 288 #endif 289 slot = ohash_qlookup(&transforms, name); 290 291 return ohash_find(&transforms, slot); 292 } 293 294 static GNode * 295 find_or_create_transformi(const char *name, const char *end) 296 { 297 GNode *r; 298 unsigned int slot; 299 300 #ifdef STATS_SUFF 301 STAT_TRANSFORM_LOOKUP_NAME++; 302 #endif 303 slot = ohash_qlookupi(&transforms, name, &end); 304 305 r = ohash_find(&transforms, slot); 306 307 if (r == NULL) { 308 r = Targ_NewGNi(name, end); 309 ohash_insert(&transforms, slot, r); 310 } 311 return r; 312 } 313 314 /*- 315 *----------------------------------------------------------------------- 316 * SuffInsert -- 317 * Insert the suffix into the list keeping the list ordered by suffix 318 * numbers. 319 * 320 * Side Effects: 321 * The reference count of the suffix is incremented 322 *----------------------------------------------------------------------- 323 */ 324 static void 325 SuffInsert(Lst l, Suff *s) 326 { 327 LstNode ln; /* current element in l we're examining */ 328 Suff *s2 = NULL; /* the suffix descriptor in this element */ 329 330 for (ln = Lst_First(l); ln != NULL; ln = Lst_Adv(ln)) { 331 s2 = (Suff *)Lst_Datum(ln); 332 if (s2->order >= s->order) 333 break; 334 } 335 336 if (DEBUG(SUFF)) 337 printf("inserting %s(%d)...", s->name, s->order); 338 if (ln == NULL) { 339 if (DEBUG(SUFF)) 340 printf("at end of list\n"); 341 Lst_AtEnd(l, s); 342 } else if (s2->order != s->order) { 343 if (DEBUG(SUFF)) 344 printf("before %s(%d)\n", s2->name, s2->order); 345 Lst_Insert(l, ln, s); 346 } else if (DEBUG(SUFF)) { 347 printf("already there\n"); 348 } 349 } 350 351 /*- 352 *----------------------------------------------------------------------- 353 * Suff_ClearSuffixes -- 354 * Nuke the list of suffixes but keep all transformation 355 * rules around. 356 * 357 * Side Effects: 358 * Current suffixes are reset 359 *----------------------------------------------------------------------- 360 */ 361 static void 362 clear_suffixes(void) 363 { 364 unsigned int i; 365 Suff *s; 366 367 for (s = ohash_first(&suffixes, &i); s != NULL; 368 s = ohash_next(&suffixes, &i)) 369 s->flags &= ~SUFF_ACTIVE; 370 371 order = 0; 372 maxLen = 0; 373 } 374 375 void 376 Suff_ClearSuffixes(void) 377 { 378 clear_suffixes(); 379 } 380 381 382 /* okay = parse_transform(str, &src, &targ); 383 * try parsing a string as a transformation rule, returns true if 384 * successful. Fills &src, &targ with the constituent suffixes. 385 * Special hack: source suffixes must exist OR be the special SUFF_PATH 386 * pseudo suffix (.PATH) 387 */ 388 static bool 389 parse_transformi(const char *str, const char *e, Suff **srcPtr, Suff **targPtr) 390 { 391 Suff *src, *target, *best_src, *best_target; 392 const char *p; 393 394 size_t len; 395 uint32_t hv; 396 unsigned int slot; 397 398 /* empty string -> no suffix */ 399 if (e == str) 400 return false; 401 402 len = e - str; 403 404 if (len > 2 * maxLen) 405 return false; 406 407 p = e; 408 best_src = best_target = NULL; 409 410 hv = *--p; 411 while (p != str) { 412 slot = ohash_lookup_interval(&suffixes, p, e, hv); 413 /* no double suffix in there */ 414 if (p - str <= (ptrdiff_t)maxLen) { 415 target = ohash_find(&suffixes, slot); 416 if (target != NULL && (target->flags & SUFF_ACTIVE)) { 417 src = find_suffi(str, p); 418 if (src != NULL && 419 (src->flags & (SUFF_ACTIVE | SUFF_PATH))) { 420 /* XXX even if we find a set of suffixes, we 421 * have to keep going to find the best one, 422 * namely, the one whose src appears first in 423 * .SUFFIXES 424 */ 425 if (best_src == NULL || 426 src->order < best_src->order) { 427 best_src = src; 428 best_target = target; 429 } 430 } 431 } 432 } 433 /* can't be a suffix anyways */ 434 if (e - p >= (ptrdiff_t)maxLen) 435 break; 436 reverse_hash_add_char(&hv, --p); 437 } 438 439 if (p == str && best_src == NULL) { 440 /* no double suffix transformation, resort to single suffix if 441 * we find one. */ 442 slot = ohash_lookup_interval(&suffixes, p, e, hv); 443 src = ohash_find(&suffixes, slot); 444 if (src != NULL && (src->flags & (SUFF_ACTIVE | SUFF_PATH))) { 445 best_src = src; 446 best_target = emptySuff; 447 } 448 } 449 if (best_src != NULL) { 450 *srcPtr = best_src; 451 *targPtr = best_target; 452 return true; 453 } else { 454 return false; 455 } 456 } 457 458 static void 459 special_path_hack(void) 460 { 461 Suff *path = add_suffixi(".PATH", NULL); 462 path->flags |= SUFF_PATH; 463 } 464 465 static Suff * 466 find_best_suffix(const char *s, const char *e) 467 { 468 const char *p; 469 uint32_t hv; 470 unsigned int slot; 471 Suff *best = NULL; 472 Suff *suff; 473 474 if (e == s) 475 return NULL; 476 p = e; 477 hv = *--p; 478 while (p != s) { 479 slot = ohash_lookup_interval(&suffixes, p, e, hv); 480 suff = ohash_find(&suffixes, slot); 481 if (suff != NULL) 482 if (best == NULL || suff->order < best->order) 483 best = suff; 484 if (e - p >= (ptrdiff_t)maxLen) 485 break; 486 reverse_hash_add_char(&hv, --p); 487 } 488 return best; 489 } 490 491 /*- 492 *----------------------------------------------------------------------- 493 * Suff_ParseAsTransform -- 494 * Try parsing a target line as a transformation rule, depending on 495 * existing suffixes. 496 * 497 * Possibly create a new transform, or reset an existing one. 498 *----------------------------------------------------------------------- 499 */ 500 GNode * 501 Suff_ParseAsTransform(const char *line, const char *end) 502 { 503 GNode *gn; /* GNode of transformation rule */ 504 Suff *s; /* source suffix */ 505 Suff *t; /* target suffix */ 506 507 if (!parse_transformi(line, end, &s, &t)) 508 return NULL; 509 510 gn = find_or_create_transformi(line, end); 511 /* In case the transform already exists, nuke old commands and children. 512 * Note we can't free them, since there might be stuff that references 513 * them elsewhere 514 */ 515 if (!Lst_IsEmpty(&gn->commands)) { 516 Lst_Destroy(&gn->commands, NOFREE); 517 Lst_Init(&gn->commands); 518 } 519 if (!Lst_IsEmpty(&gn->children)) { 520 Lst_Destroy(&gn->children, NOFREE); 521 Lst_Init(&gn->children); 522 } 523 524 gn->type = OP_TRANSFORM; 525 if (s->flags & SUFF_PATH) { 526 gn->special = SPECIAL_PATH | SPECIAL_TARGET; 527 gn->suffix = t; 528 } 529 530 if (DEBUG(SUFF)) 531 printf("defining transformation from `%s' to `%s'\n", 532 s->name, t->name); 533 return gn; 534 } 535 536 static void 537 make_suffix_known(Suff *s) 538 { 539 if ((s->flags & SUFF_ACTIVE) == 0) { 540 s->order = order++; 541 s->flags |= SUFF_ACTIVE; 542 if (s->nameLen > maxLen) 543 maxLen = s->nameLen; 544 } 545 } 546 547 static Suff * 548 new_suffixi(const char *str, const char *eptr) 549 { 550 Suff *s; 551 552 s = ohash_create_entry(&suff_info, str, &eptr); 553 s->nameLen = eptr - str; 554 Lst_Init(&s->searchPath); 555 Lst_Init(&s->children); 556 Lst_Init(&s->parents); 557 s->flags = 0; 558 return s; 559 } 560 561 /*- 562 *----------------------------------------------------------------------- 563 * Suff_AddSuffix -- 564 * Add the suffix in string to the end of the list of known suffixes. 565 * Should we restructure the suffix graph? Make doesn't... 566 * 567 * Side Effects: 568 * A GNode is created for the suffix and a Suff structure is created and 569 * added to the known suffixes, unless it was already known. 570 *----------------------------------------------------------------------- 571 */ 572 void 573 Suff_AddSuffixi(const char *str, const char *end) 574 { 575 (void)add_suffixi(str, end); 576 } 577 578 static Suff * 579 add_suffixi(const char *str, const char *end) 580 { 581 Suff *s; /* new suffix descriptor */ 582 583 unsigned int slot; 584 585 slot = reverse_slot(&suffixes, str, &end); 586 s = ohash_find(&suffixes, slot); 587 if (s == NULL) { 588 s = new_suffixi(str, end); 589 ohash_insert(&suffixes, slot, s); 590 } 591 make_suffix_known(s); 592 return s; 593 } 594 595 Lst 596 find_suffix_path(GNode *gn) 597 { 598 if (gn->suffix != NULL && gn->suffix != emptySuff) 599 return &(gn->suffix->searchPath); 600 else 601 return defaultPath; 602 } 603 604 static void 605 build_suffixes_graph(void) 606 { 607 Suff *s, *s2; 608 GNode *gn; 609 unsigned int i; 610 611 for (gn = ohash_first(&transforms, &i); gn != NULL; 612 gn = ohash_next(&transforms, &i)) { 613 if (Lst_IsEmpty(&gn->commands) && Lst_IsEmpty(&gn->children)) 614 continue; 615 if ((gn->special & SPECIAL_MASK) == SPECIAL_PATH) 616 continue; 617 if (parse_transform(gn->name, &s, &s2)) { 618 SuffInsert(&s2->children, s); 619 SuffInsert(&s->parents, s2); 620 } 621 } 622 } 623 624 /*- 625 *----------------------------------------------------------------------- 626 * setup_paths 627 * Extend the search paths for all suffixes to include the default 628 * search path. 629 * 630 * Side Effects: 631 * The searchPath field of all the suffixes is extended by the 632 * directories in defaultPath. If paths were specified for the 633 * ".h" suffix, the directories are stuffed into a global variable 634 * called ".INCLUDES" with each directory preceded by a -I. The same 635 * is done for the ".a" suffix, except the variable is called 636 * ".LIBS" and the flag is -L. 637 *----------------------------------------------------------------------- 638 */ 639 static void 640 setup_paths(void) 641 { 642 unsigned int i; 643 Suff *s; 644 645 for (s = ohash_first(&suffixes, &i); s != NULL; 646 s = ohash_next(&suffixes, &i)) { 647 if (!Lst_IsEmpty(&s->searchPath)) 648 Dir_Concat(&s->searchPath, defaultPath); 649 else 650 Lst_Clone(&s->searchPath, defaultPath, Dir_CopyDir); 651 } 652 } 653 654 void 655 process_suffixes_after_makefile_is_read(void) 656 { 657 /* once the Makefile is finish reading, we can set up the default PATH 658 * stuff, and build the final suffixes graph 659 */ 660 setup_paths(); 661 /* and we link all transforms to active suffixes at this point. */ 662 build_suffixes_graph(); 663 } 664 /********** Implicit Source Search Functions *********/ 665 666 /*- 667 *----------------------------------------------------------------------- 668 * SuffAddSrc -- 669 * Add a suffix as a Src structure to the given list with its parent 670 * being the given Src structure. If the suffix is the null suffix, 671 * the prefix is used unaltered as the file name in the Src structure. 672 * 673 * Side Effects: 674 * A Src structure is created and tacked onto the end of the list 675 *----------------------------------------------------------------------- 676 */ 677 static void 678 SuffAddSrc( 679 void *sp, /* suffix for which to create a Src structure */ 680 void *lsp) /* list and parent for the new Src */ 681 { 682 Suff *s = sp; 683 LstSrc *ls = lsp; 684 Src *s2; /* new Src structure */ 685 Src *targ; /* Target structure */ 686 687 targ = ls->s; 688 689 s2 = emalloc(sizeof(Src)); 690 s2->file = Str_concat(targ->prefix, s->name, 0); 691 s2->prefix = targ->prefix; 692 s2->parent = targ; 693 s2->node = NULL; 694 s2->suff = s; 695 s2->children = 0; 696 targ->children++; 697 Lst_AtEnd(ls->l, s2); 698 #ifdef DEBUG_SRC 699 Lst_Init(&s2->cp); 700 Lst_AtEnd(&targ->cp, s2); 701 printf("2 add %x %x to %x:", targ, s2, ls->l); 702 Lst_Every(ls->l, PrintAddr); 703 printf("\n"); 704 #endif 705 706 } 707 708 /*- 709 *----------------------------------------------------------------------- 710 * SuffAddLevel -- 711 * Add all the children of targ as Src structures to the given list 712 * 713 * Side Effects: 714 * Lots of structures are created and added to the list 715 *----------------------------------------------------------------------- 716 */ 717 static void 718 SuffAddLevel( 719 Lst l, /* list to which to add the new level */ 720 Src *targ) /* Src structure to use as the parent */ 721 { 722 LstSrc ls; 723 724 ls.s = targ; 725 ls.l = l; 726 727 Lst_ForEach(&targ->suff->children, SuffAddSrc, &ls); 728 } 729 730 /*- 731 *---------------------------------------------------------------------- 732 * SuffRemoveSrc -- 733 * Free all src structures in list that don't have a reference count 734 * 735 * Results: 736 * Ture if an src was removed 737 * 738 * Side Effects: 739 * The memory is free'd. 740 *---------------------------------------------------------------------- 741 */ 742 static int 743 SuffRemoveSrc(Lst l) 744 { 745 LstNode ln; 746 Src *s; 747 int t = 0; 748 749 #ifdef DEBUG_SRC 750 printf("cleaning %lx: ", (unsigned long)l); 751 Lst_Every(l, PrintAddr); 752 printf("\n"); 753 #endif 754 755 756 for (ln = Lst_First(l); ln != NULL; ln = Lst_Adv(ln)) { 757 s = (Src *)Lst_Datum(ln); 758 if (s->children == 0) { 759 free(s->file); 760 if (!s->parent) 761 free(s->prefix); 762 else { 763 #ifdef DEBUG_SRC 764 LstNode ln2 = Lst_Member(&s->parent->cp, s); 765 if (ln2 != NULL) 766 Lst_Remove(&s->parent->cp, ln2); 767 #endif 768 --s->parent->children; 769 } 770 #ifdef DEBUG_SRC 771 printf("free: [l=%x] p=%x %d\n", l, s, s->children); 772 Lst_Destroy(&s->cp, NOFREE); 773 #endif 774 Lst_Remove(l, ln); 775 free(s); 776 t |= 1; 777 return true; 778 } 779 #ifdef DEBUG_SRC 780 else { 781 printf("keep: [l=%x] p=%x %d: ", l, s, s->children); 782 Lst_Every(&s->cp, PrintAddr); 783 printf("\n"); 784 } 785 #endif 786 } 787 788 return t; 789 } 790 791 /*- 792 *----------------------------------------------------------------------- 793 * SuffFindThem -- 794 * Find the first existing file/target in the list srcs 795 * 796 * Results: 797 * The lowest structure in the chain of transformations 798 *----------------------------------------------------------------------- 799 */ 800 static Src * 801 SuffFindThem( 802 Lst srcs, /* list of Src structures to search through */ 803 Lst slst) 804 { 805 Src *s; /* current Src */ 806 Src *rs; /* returned Src */ 807 char *ptr; 808 809 rs = NULL; 810 811 while ((s = (Src *)Lst_DeQueue(srcs)) != NULL) { 812 if (DEBUG(SUFF)) 813 printf("\ttrying %s...", s->file); 814 815 /* 816 * A file is considered to exist if either a node exists in the 817 * graph for it or the file actually exists. 818 */ 819 if (Targ_FindNode(s->file, TARG_NOCREATE) != NULL) { 820 #ifdef DEBUG_SRC 821 printf("remove %x from %x\n", s, srcs); 822 #endif 823 rs = s; 824 break; 825 } 826 827 if ((ptr = Dir_FindFile(s->file, &s->suff->searchPath)) 828 != NULL) { 829 rs = s; 830 #ifdef DEBUG_SRC 831 printf("remove %x from %x\n", s, srcs); 832 #endif 833 free(ptr); 834 break; 835 } 836 837 if (DEBUG(SUFF)) 838 printf("not there\n"); 839 840 SuffAddLevel(srcs, s); 841 Lst_AtEnd(slst, s); 842 } 843 844 if (DEBUG(SUFF) && rs) 845 printf("got it\n"); 846 return rs; 847 } 848 849 /*- 850 *----------------------------------------------------------------------- 851 * SuffFindCmds -- 852 * See if any of the children of the target in the Src structure is 853 * one from which the target can be transformed. If there is one, 854 * a Src structure is put together for it and returned. 855 *----------------------------------------------------------------------- 856 */ 857 static Src * 858 SuffFindCmds(Src *targ, Lst slst) 859 { 860 LstNode ln; /* General-purpose list node */ 861 GNode *t; /* Target GNode */ 862 GNode *s; /* Source GNode */ 863 int prefixLen; /* The length of the defined prefix */ 864 Suff *suff; /* Suffix on matching beastie */ 865 Src *ret; /* Return value */ 866 const char *cp; 867 868 t = targ->node; 869 prefixLen = strlen(targ->prefix); 870 871 for (ln = Lst_First(&t->children); ln != NULL; ln = Lst_Adv(ln)) { 872 s = (GNode *)Lst_Datum(ln); 873 874 cp = strrchr(s->name, '/'); 875 if (cp == NULL) 876 cp = s->name; 877 else 878 cp++; 879 if (strncmp(cp, targ->prefix, prefixLen) != 0) 880 continue; 881 /* The node matches the prefix ok, see if it has a known 882 * suffix. */ 883 suff = find_suff(&cp[prefixLen]); 884 if (suff == NULL) 885 continue; 886 /* 887 * It even has a known suffix, see if there's a transformation 888 * defined between the node's suffix and the target's suffix. 889 * 890 * XXX: Handle multi-stage transformations here, too. 891 */ 892 if (Lst_Member(&suff->parents, targ->suff) == NULL) 893 continue; 894 /* 895 * Create a new Src structure to describe this transformation 896 * (making sure to duplicate the source node's name so 897 * Suff_FindDeps can free it again (ick)), and return the new 898 * structure. 899 */ 900 ret = emalloc(sizeof(Src)); 901 ret->file = estrdup(s->name); 902 ret->prefix = targ->prefix; 903 ret->suff = suff; 904 ret->parent = targ; 905 ret->node = s; 906 ret->children = 0; 907 targ->children++; 908 #ifdef DEBUG_SRC 909 Lst_Init(&ret->cp); 910 printf("3 add %x %x\n", targ, ret); 911 Lst_AtEnd(&targ->cp, ret); 912 #endif 913 Lst_AtEnd(slst, ret); 914 if (DEBUG(SUFF)) 915 printf("\tusing existing source %s\n", s->name); 916 return ret; 917 } 918 return NULL; 919 } 920 921 static void 922 SuffLinkParent(GNode *cgn, GNode *pgn) 923 { 924 Lst_AtEnd(&cgn->parents, pgn); 925 if (!has_been_built(cgn)) 926 pgn->unmade++; 927 else if ( ! (cgn->type & (OP_EXEC|OP_USE))) { 928 if (cgn->built_status == MADE) 929 pgn->childMade = true; 930 (void)Make_TimeStamp(pgn, cgn); 931 } 932 } 933 934 static void 935 SuffExpandVarChildren(LstNode after, GNode *cgn, GNode *pgn) 936 { 937 GNode *gn; /* New source 8) */ 938 char *cp; /* Expanded value */ 939 LIST members; 940 941 942 if (DEBUG(SUFF)) 943 printf("Expanding \"%s\"...", cgn->name); 944 945 cp = Var_Subst(cgn->name, &pgn->context, true); 946 if (cp == NULL) { 947 printf("Problem substituting in %s", cgn->name); 948 printf("\n"); 949 return; 950 } 951 952 Lst_Init(&members); 953 954 if (cgn->type & OP_ARCHV) { 955 /* 956 * Node was an archive(member) target, so we want to call 957 * on the Arch module to find the nodes for us, expanding 958 * variables in the parent's context. 959 */ 960 const char *sacrifice = (const char *)cp; 961 962 (void)Arch_ParseArchive(&sacrifice, &members, &pgn->context); 963 } else { 964 /* Break the result into a vector of strings whose nodes 965 * we can find, then add those nodes to the members list. 966 * Unfortunately, we can't use brk_string because it 967 * doesn't understand about variable specifications with 968 * spaces in them... */ 969 const char *start, *cp2; 970 971 for (start = cp; *start == ' ' || *start == '\t'; start++) 972 continue; 973 for (cp2 = start; *cp2 != '\0';) { 974 if (ISSPACE(*cp2)) { 975 /* White-space -- terminate element, find the 976 * node, add it, skip any further spaces. */ 977 gn = Targ_FindNodei(start, cp2, TARG_CREATE); 978 cp2++; 979 Lst_AtEnd(&members, gn); 980 while (ISSPACE(*cp2)) 981 cp2++; 982 /* Adjust cp2 for increment at start of loop, 983 * but set start to first non-space. */ 984 start = cp2; 985 } else if (*cp2 == '$') 986 /* Start of a variable spec -- contact variable 987 * module to find the end so we can skip over 988 * it. */ 989 Var_ParseSkip(&cp2, &pgn->context); 990 else if (*cp2 == '\\' && cp2[1] != '\0') 991 /* Escaped something -- skip over it. */ 992 cp2+=2; 993 else 994 cp2++; 995 } 996 997 if (cp2 != start) { 998 /* Stuff left over -- add it to the list too. */ 999 gn = Targ_FindNodei(start, cp2, TARG_CREATE); 1000 Lst_AtEnd(&members, gn); 1001 } 1002 } 1003 /* Add all elements of the members list to the parent node. */ 1004 while ((gn = (GNode *)Lst_DeQueue(&members)) != NULL) { 1005 if (DEBUG(SUFF)) 1006 printf("%s...", gn->name); 1007 if (Lst_Member(&pgn->children, gn) == NULL) { 1008 Lst_Append(&pgn->children, after, gn); 1009 after = Lst_Adv(after); 1010 SuffLinkParent(gn, pgn); 1011 } 1012 } 1013 /* Free the result. */ 1014 free(cp); 1015 if (DEBUG(SUFF)) 1016 printf("\n"); 1017 } 1018 1019 static void 1020 SuffExpandWildChildren(LstNode after, GNode *cgn, GNode *pgn) 1021 { 1022 Suff *s; 1023 char *cp; /* Expanded value */ 1024 1025 LIST exp; /* List of expansions */ 1026 Lst path; /* Search path along which to expand */ 1027 1028 if (DEBUG(SUFF)) 1029 printf("Wildcard expanding \"%s\"...", cgn->name); 1030 1031 /* Find a path along which to expand the word. 1032 * 1033 * If the word has a known suffix, use that path. 1034 * If it has no known suffix and we're allowed to use the null 1035 * suffix, use its path. 1036 * Else use the default system search path. */ 1037 s = find_best_suffix(cgn->name, cgn->name + strlen(cgn->name)); 1038 1039 if (s != NULL) { 1040 if (DEBUG(SUFF)) 1041 printf("suffix is \"%s\"...", s->name); 1042 path = &s->searchPath; 1043 } else 1044 /* Use default search path. */ 1045 path = defaultPath; 1046 1047 /* Expand the word along the chosen path. */ 1048 Lst_Init(&exp); 1049 Dir_Expand(cgn->name, path, &exp); 1050 1051 /* Fetch next expansion off the list and find its GNode. */ 1052 while ((cp = (char *)Lst_DeQueue(&exp)) != NULL) { 1053 GNode *gn; /* New source 8) */ 1054 if (DEBUG(SUFF)) 1055 printf("%s...", cp); 1056 gn = Targ_FindNode(cp, TARG_CREATE); 1057 1058 /* If gn isn't already a child of the parent, make it so and 1059 * up the parent's count of unmade children. */ 1060 if (Lst_Member(&pgn->children, gn) == NULL) { 1061 Lst_Append(&pgn->children, after, gn); 1062 after = Lst_Adv(after); 1063 SuffLinkParent(gn, pgn); 1064 } 1065 } 1066 1067 if (DEBUG(SUFF)) 1068 printf("\n"); 1069 } 1070 1071 /*- 1072 *----------------------------------------------------------------------- 1073 * SuffExpandChildren -- 1074 * Expand the names of any children of a given node that contain 1075 * variable invocations or file wildcards into actual targets. 1076 * 1077 * Side Effects: 1078 * The expanded node is removed from the parent's list of children, 1079 * and the parent's unmade counter is decremented, but other nodes 1080 * may be added. 1081 *----------------------------------------------------------------------- 1082 */ 1083 static void 1084 SuffExpandChildren(LstNode ln, /* LstNode of child, so we can replace it */ 1085 GNode *pgn) 1086 { 1087 GNode *cgn = (GNode *)Lst_Datum(ln); 1088 1089 /* First do variable expansion -- this takes precedence over wildcard 1090 * expansion. If the result contains wildcards, they'll be gotten to 1091 * later since the resulting words are tacked on to the end of the 1092 * children list. */ 1093 if (strchr(cgn->name, '$') != NULL) 1094 SuffExpandVarChildren(ln, cgn, pgn); 1095 else if (Dir_HasWildcards(cgn->name)) 1096 SuffExpandWildChildren(ln, cgn, pgn); 1097 else 1098 /* Third case: nothing to expand. */ 1099 return; 1100 1101 /* Since the source was expanded, remove it from the list of children to 1102 * keep it from being processed. */ 1103 pgn->unmade--; 1104 Lst_Remove(&pgn->children, ln); 1105 } 1106 1107 void 1108 expand_children_from(GNode *parent, LstNode from) 1109 { 1110 LstNode np, ln; 1111 1112 for (ln = from; ln != NULL; ln = np) { 1113 np = Lst_Adv(ln); 1114 SuffExpandChildren(ln, parent); 1115 } 1116 } 1117 1118 /*- 1119 *----------------------------------------------------------------------- 1120 * SuffApplyTransform -- 1121 * Apply a transformation rule, given the source and target nodes 1122 * and suffixes. 1123 * 1124 * Results: 1125 * true if successful, false if not. 1126 * 1127 * Side Effects: 1128 * The source and target are linked and the commands from the 1129 * transformation are added to the target node's commands list. 1130 * All attributes but OP_DEPMASK and OP_TRANSFORM are applied 1131 * to the target. The target also inherits all the sources for 1132 * the transformation rule. 1133 *----------------------------------------------------------------------- 1134 */ 1135 static bool 1136 SuffApplyTransform( 1137 GNode *tGn, /* Target node */ 1138 GNode *sGn, /* Source node */ 1139 Suff *t, /* Target suffix */ 1140 Suff *s) /* Source suffix */ 1141 { 1142 LstNode ln; /* General node */ 1143 char *tname; /* Name of transformation rule */ 1144 GNode *gn; /* Node for same */ 1145 1146 if (Lst_AddNew(&tGn->children, sGn)) { 1147 /* Not already linked, so form the proper links between the 1148 * target and source. */ 1149 SuffLinkParent(sGn, tGn); 1150 } 1151 1152 if ((sGn->type & OP_OPMASK) == OP_DOUBLEDEP) { 1153 /* When a :: node is used as the implied source of a node, we 1154 * have to link all its cohorts in as sources as well. There's 1155 * only one implied src, as that will be sufficient to get 1156 * the .IMPSRC variable set for tGn. */ 1157 for (ln=Lst_First(&sGn->cohorts); ln != NULL; ln=Lst_Adv(ln)) { 1158 gn = (GNode *)Lst_Datum(ln); 1159 1160 if (Lst_AddNew(&tGn->children, gn)) { 1161 /* Not already linked, so form the proper links 1162 * between the target and source. */ 1163 SuffLinkParent(gn, tGn); 1164 } 1165 } 1166 } 1167 /* Locate the transformation rule itself. */ 1168 tname = Str_concat(s->name, t->name, 0); 1169 gn = find_transform(tname); 1170 free(tname); 1171 1172 if (gn == NULL) 1173 /* 1174 * Not really such a transformation rule (can happen when we're 1175 * called to link an OP_MEMBER and OP_ARCHV node), so return 1176 * false. 1177 */ 1178 return false; 1179 1180 if (DEBUG(SUFF)) 1181 printf("\tapplying %s -> %s to \"%s\"\n", s->name, t->name, 1182 tGn->name); 1183 1184 /* Record last child for expansion purposes. */ 1185 ln = Lst_Last(&tGn->children); 1186 1187 /* Pass the buck to Make_HandleUse to apply the rule. */ 1188 Make_HandleUse(gn, tGn); 1189 1190 /* Deal with wildcards and variables in any acquired sources. */ 1191 expand_children_from(tGn, Lst_Succ(ln)); 1192 1193 /* Keep track of another parent to which this beast is transformed so 1194 * the .IMPSRC variable can be set correctly for the parent. */ 1195 tGn->impliedsrc = sGn; 1196 1197 return true; 1198 } 1199 1200 static Suff * 1201 find_suffix_as_suffix(Lst l, const char *b, const char *e) 1202 { 1203 LstNode ln; 1204 Suff *s; 1205 1206 for (ln = Lst_First(l); ln != NULL; ln = Lst_Adv(ln)) { 1207 s = (Suff *)Lst_Datum(ln); 1208 if (suffix_is_suffix(s, b, e)) 1209 return s; 1210 } 1211 return NULL; 1212 } 1213 1214 /*- 1215 *----------------------------------------------------------------------- 1216 * SuffFindArchiveDeps -- 1217 * Locate dependencies for an OP_ARCHV node. 1218 * 1219 * Side Effects: 1220 * Same as Suff_FindDeps 1221 *----------------------------------------------------------------------- 1222 */ 1223 static void 1224 SuffFindArchiveDeps( 1225 GNode *gn, /* Node for which to locate dependencies */ 1226 Lst slst) 1227 { 1228 char *eoarch; /* End of archive portion */ 1229 char *eoname; /* End of member portion */ 1230 GNode *mem; /* Node for member */ 1231 Suff *ms; /* Suffix descriptor for member */ 1232 char *name; /* Start of member's name */ 1233 1234 /* The node is an archive(member) pair. so we must find a suffix 1235 * for both of them. */ 1236 eoarch = strchr(gn->name, '('); 1237 if (eoarch == NULL) 1238 return; 1239 1240 name = eoarch + 1; 1241 1242 eoname = strchr(name, ')'); 1243 if (eoname == NULL) 1244 return; 1245 1246 /* To simplify things, call Suff_FindDeps recursively on the member now, 1247 * so we can simply compare the member's .PREFIX and .TARGET variables 1248 * to locate its suffix. This allows us to figure out the suffix to 1249 * use for the archive without having to do a quadratic search over the 1250 * suffix list, backtracking for each one... */ 1251 mem = Targ_FindNodei(name, eoname, TARG_CREATE); 1252 SuffFindDeps(mem, slst); 1253 1254 /* Create the link between the two nodes right off. */ 1255 if (Lst_AddNew(&gn->children, mem)) 1256 SuffLinkParent(mem, gn); 1257 1258 /* Copy variables from member node to this one. */ 1259 Var(TARGET_INDEX, gn) = Var(TARGET_INDEX, mem); 1260 Var(PREFIX_INDEX, gn) = Var(PREFIX_INDEX, mem); 1261 1262 ms = mem->suffix; 1263 if (ms == NULL) { 1264 /* Didn't know what it was -- use .NULL suffix if not in make 1265 * mode. */ 1266 if (DEBUG(SUFF)) 1267 printf("using empty suffix\n"); 1268 ms = emptySuff; 1269 } 1270 1271 1272 /* Set the other two local variables required for this target. */ 1273 Var(MEMBER_INDEX, gn) = mem->name; 1274 Var(ARCHIVE_INDEX, gn) = gn->name; 1275 1276 if (ms != NULL) { 1277 /* 1278 * Member has a known suffix, so look for a transformation rule 1279 * from it to a possible suffix of the archive. Rather than 1280 * searching through the entire list, we just look at suffixes 1281 * to which the member's suffix may be transformed... 1282 */ 1283 1284 Suff *suff; 1285 1286 suff = find_suffix_as_suffix(&ms->parents, gn->name, eoarch); 1287 1288 if (suff != NULL) { 1289 /* Got one -- apply it. */ 1290 if (!SuffApplyTransform(gn, mem, suff, ms) && 1291 DEBUG(SUFF)) 1292 printf("\tNo transformation from %s -> %s\n", 1293 ms->name, suff->name); 1294 } 1295 } 1296 1297 /* Pretend gn appeared to the left of a dependency operator so 1298 * the user needn't provide a transformation from the member to the 1299 * archive. */ 1300 if (OP_NOP(gn->type)) 1301 gn->type |= OP_DEPENDS; 1302 1303 /* Flag the member as such so we remember to look in the archive for 1304 * its modification time. */ 1305 mem->type |= OP_MEMBER; 1306 } 1307 1308 static void 1309 record_possible_suffix(Suff *s, GNode *gn, char *eoname, Lst srcs, Lst targs) 1310 { 1311 int prefixLen; 1312 Src *targ; 1313 1314 targ = emalloc(sizeof(Src)); 1315 targ->file = estrdup(gn->name); 1316 targ->suff = s; 1317 targ->node = gn; 1318 targ->parent = NULL; 1319 targ->children = 0; 1320 #ifdef DEBUG_SRC 1321 Lst_Init(&targ->cp); 1322 #endif 1323 1324 /* Allocate room for the prefix, whose end is found by 1325 * subtracting the length of the suffix from the end of 1326 * the name. */ 1327 prefixLen = (eoname - targ->suff->nameLen) - gn->name; 1328 targ->prefix = emalloc(prefixLen + 1); 1329 memcpy(targ->prefix, gn->name, prefixLen); 1330 targ->prefix[prefixLen] = '\0'; 1331 1332 /* Add nodes from which the target can be made. */ 1333 SuffAddLevel(srcs, targ); 1334 1335 /* Record the target so we can nuke it. */ 1336 Lst_AtEnd(targs, targ); 1337 } 1338 1339 static void 1340 record_possible_suffixes(GNode *gn, Lst srcs, Lst targs) 1341 { 1342 char *s = gn->name; 1343 char *e = s + strlen(s); 1344 const char *p; 1345 uint32_t hv; 1346 unsigned int slot; 1347 Suff *suff; 1348 1349 if (e == s) 1350 return; 1351 1352 p = e; 1353 hv = *--p; 1354 1355 while (p != s) { 1356 slot = ohash_lookup_interval(&suffixes, p, e, hv); 1357 suff = ohash_find(&suffixes, slot); 1358 if (suff != NULL && (suff->flags & SUFF_ACTIVE)) 1359 record_possible_suffix(suff, gn, e, srcs, targs); 1360 if (e - p >= (ptrdiff_t)maxLen) 1361 break; 1362 reverse_hash_add_char(&hv, --p); 1363 } 1364 } 1365 1366 /*- 1367 *----------------------------------------------------------------------- 1368 * SuffFindNormalDeps -- 1369 * Locate implicit dependencies for regular targets. 1370 * 1371 * Side Effects: 1372 * Same as Suff_FindDeps... 1373 *----------------------------------------------------------------------- 1374 */ 1375 static void 1376 SuffFindNormalDeps( 1377 GNode *gn, /* Node for which to find sources */ 1378 Lst slst) 1379 { 1380 LIST srcs; /* List of sources at which to look */ 1381 LIST targs; /* List of targets to which things can be 1382 * transformed. They all have the same file, 1383 * but different suff and prefix fields */ 1384 Src *bottom; /* Start of found transformation path */ 1385 Src *src; /* General Src pointer */ 1386 char *prefix; /* Prefix to use */ 1387 Src *targ; /* General Src target pointer */ 1388 1389 1390 Lst_Init(&srcs); 1391 Lst_Init(&targs); 1392 1393 /* We're caught in a catch-22 here. On the one hand, we want to use any 1394 * transformation implied by the target's sources, but we can't examine 1395 * the sources until we've expanded any variables/wildcards they may 1396 * hold, and we can't do that until we've set up the target's local 1397 * variables and we can't do that until we know what the proper suffix 1398 * for the target is (in case there are two suffixes one of which is a 1399 * suffix of the other) and we can't know that until we've found its 1400 * implied source, which we may not want to use if there's an existing 1401 * source that implies a different transformation. 1402 * 1403 * In an attempt to get around this, which may not work all the time, 1404 * but should work most of the time, we look for implied sources first, 1405 * checking transformations to all possible suffixes of the target, use 1406 * what we find to set the target's local variables, expand the 1407 * children, then look for any overriding transformations they imply. 1408 * Should we find one, we discard the one we found before. */ 1409 1410 1411 record_possible_suffixes(gn, &srcs, &targs); 1412 /* Handle target of unknown suffix... */ 1413 if (Lst_IsEmpty(&srcs)) { 1414 if (DEBUG(SUFF)) 1415 printf("\tNo known suffix on %s. Using empty suffix\n", 1416 gn->name); 1417 1418 targ = emalloc(sizeof(Src)); 1419 targ->file = estrdup(gn->name); 1420 targ->suff = emptySuff; 1421 targ->node = gn; 1422 targ->parent = NULL; 1423 targ->children = 0; 1424 targ->prefix = estrdup(gn->name); 1425 #ifdef DEBUG_SRC 1426 Lst_Init(&targ->cp); 1427 #endif 1428 1429 /* Only use the default suffix rules if we don't have commands 1430 * or dependencies defined for this gnode. */ 1431 if (Lst_IsEmpty(&gn->commands) && Lst_IsEmpty(&gn->children)) 1432 SuffAddLevel(&srcs, targ); 1433 else { 1434 if (DEBUG(SUFF)) 1435 printf("not "); 1436 } 1437 1438 if (DEBUG(SUFF)) 1439 printf("adding suffix rules\n"); 1440 1441 Lst_AtEnd(&targs, targ); 1442 } 1443 1444 /* Using the list of possible sources built up from the target 1445 * suffix(es), try and find an existing file/target that matches. */ 1446 bottom = SuffFindThem(&srcs, slst); 1447 1448 if (bottom == NULL) { 1449 /* No known transformations -- use the first suffix found for 1450 * setting the local variables. */ 1451 if (!Lst_IsEmpty(&targs)) 1452 targ = (Src *)Lst_Datum(Lst_First(&targs)); 1453 else 1454 targ = NULL; 1455 } else { 1456 /* Work up the transformation path to find the suffix of the 1457 * target to which the transformation was made. */ 1458 for (targ = bottom; targ->parent != NULL; targ = targ->parent) 1459 continue; 1460 } 1461 1462 /* The .TARGET variable we always set to be the name at this point, 1463 * since it's only set to the path if the thing is only a source and 1464 * if it's only a source, it doesn't matter what we put here as far 1465 * as expanding sources is concerned, since it has none... */ 1466 Var(TARGET_INDEX, gn) = gn->name; 1467 1468 prefix = targ != NULL ? estrdup(targ->prefix) : gn->name; 1469 Var(PREFIX_INDEX, gn) = prefix; 1470 1471 /* Now we've got the important local variables set, expand any sources 1472 * that still contain variables or wildcards in their names. */ 1473 expand_all_children(gn); 1474 1475 if (targ == NULL) { 1476 if (DEBUG(SUFF)) 1477 printf("\tNo valid suffix on %s\n", gn->name); 1478 1479 sfnd_abort: 1480 /* Deal with finding the thing on the default search path if the 1481 * node is only a source (not on the lhs of a dependency operator 1482 * or [XXX] it has neither children or commands). */ 1483 if (OP_NOP(gn->type) || 1484 (Lst_IsEmpty(&gn->children) && 1485 Lst_IsEmpty(&gn->commands))) { 1486 gn->path = Dir_FindFile(gn->name, 1487 (targ == NULL ? defaultPath : 1488 &targ->suff->searchPath)); 1489 if (gn->path != NULL) { 1490 char *ptr; 1491 Var(TARGET_INDEX, gn) = estrdup(gn->path); 1492 1493 if (targ != NULL) { 1494 /* Suffix known for the thing -- trim 1495 * the suffix off the path to form the 1496 * proper .PREFIX variable. */ 1497 int savep = strlen(gn->path) - 1498 targ->suff->nameLen; 1499 char savec; 1500 1501 gn->suffix = targ->suff; 1502 1503 savec = gn->path[savep]; 1504 gn->path[savep] = '\0'; 1505 1506 if ((ptr = strrchr(gn->path, '/')) != 1507 NULL) 1508 ptr++; 1509 else 1510 ptr = gn->path; 1511 1512 Var(PREFIX_INDEX, gn) = estrdup(ptr); 1513 1514 gn->path[savep] = savec; 1515 } else { 1516 /* The .PREFIX gets the full path if the 1517 * target has no known suffix. */ 1518 gn->suffix = NULL; 1519 1520 if ((ptr = strrchr(gn->path, '/')) != 1521 NULL) 1522 ptr++; 1523 else 1524 ptr = gn->path; 1525 1526 Var(PREFIX_INDEX, gn) = estrdup(ptr); 1527 } 1528 } 1529 } else { 1530 /* Not appropriate to search for the thing -- set the 1531 * path to be the name so Dir_MTime won't go grovelling 1532 * for it. */ 1533 gn->suffix = targ == NULL ? NULL : targ->suff; 1534 efree(gn->path); 1535 gn->path = estrdup(gn->name); 1536 } 1537 1538 goto sfnd_return; 1539 } 1540 1541 /* Check for overriding transformation rule implied by sources. */ 1542 if (!Lst_IsEmpty(&gn->children)) { 1543 src = SuffFindCmds(targ, slst); 1544 1545 if (src != NULL) { 1546 /* Free up all the Src structures in the transformation 1547 * path up to, but not including, the parent node. */ 1548 while (bottom && bottom->parent != NULL) { 1549 (void)Lst_AddNew(slst, bottom); 1550 bottom = bottom->parent; 1551 } 1552 bottom = src; 1553 } 1554 } 1555 1556 if (bottom == NULL) { 1557 /* No idea from where it can come -- return now. */ 1558 goto sfnd_abort; 1559 } 1560 1561 /* We now have a list of Src structures headed by 'bottom' and linked 1562 * via their 'parent' pointers. What we do next is create links between 1563 * source and target nodes (which may or may not have been created) and 1564 * set the necessary local variables in each target. The commands for 1565 * each target are set from the commands of the transformation rule 1566 * used to get from the src suffix to the targ suffix. Note that this 1567 * causes the commands list of the original node, gn, to be replaced by 1568 * the commands of the final transformation rule. Also, the unmade 1569 * field of gn is incremented. Etc. */ 1570 if (bottom->node == NULL) { 1571 bottom->node = Targ_FindNode(bottom->file, TARG_CREATE); 1572 } 1573 1574 for (src = bottom; src->parent != NULL; src = src->parent) { 1575 targ = src->parent; 1576 1577 src->node->suffix = src->suff; 1578 1579 if (targ->node == NULL) { 1580 targ->node = Targ_FindNode(targ->file, TARG_CREATE); 1581 } 1582 1583 SuffApplyTransform(targ->node, src->node, 1584 targ->suff, src->suff); 1585 1586 if (targ->node != gn) { 1587 /* Finish off the dependency-search process for any 1588 * nodes between bottom and gn (no point in questing 1589 * around the filesystem for their implicit source when 1590 * it's already known). Note that the node can't have 1591 * any sources that need expanding, since SuffFindThem 1592 * will stop on an existing node, so all we need to do 1593 * is set the standard and System V variables. */ 1594 targ->node->type |= OP_DEPS_FOUND; 1595 1596 Var(PREFIX_INDEX, targ->node) = estrdup(targ->prefix); 1597 1598 Var(TARGET_INDEX, targ->node) = targ->node->name; 1599 } 1600 } 1601 1602 gn->suffix = src->suff; 1603 1604 /* So Dir_MTime doesn't go questing for it... */ 1605 efree(gn->path); 1606 gn->path = estrdup(gn->name); 1607 1608 /* Nuke the transformation path and the Src structures left over in the 1609 * two lists. */ 1610 sfnd_return: 1611 if (bottom) 1612 (void)Lst_AddNew(slst, bottom); 1613 1614 while (SuffRemoveSrc(&srcs) || SuffRemoveSrc(&targs)) 1615 continue; 1616 1617 Lst_ConcatDestroy(slst, &srcs); 1618 Lst_ConcatDestroy(slst, &targs); 1619 } 1620 1621 1622 /*- 1623 *----------------------------------------------------------------------- 1624 * Suff_FindDeps -- 1625 * Find implicit sources for the target described by the graph node 1626 * gn 1627 * 1628 * Side Effects: 1629 * Nodes are added to the graph below the passed-in node. The nodes 1630 * are marked to have their IMPSRC variable filled in. The 1631 * PREFIX variable is set for the given node and all its 1632 * implied children. 1633 * 1634 * Notes: 1635 * The path found by this target is the shortest path in the 1636 * transformation graph, which may pass through non-existent targets, 1637 * to an existing target. The search continues on all paths from the 1638 * root suffix until a file is found. I.e. if there's a path 1639 * .o -> .c -> .l -> .l,v from the root and the .l,v file exists but 1640 * the .c and .l files don't, the search will branch out in 1641 * all directions from .o and again from all the nodes on the 1642 * next level until the .l,v node is encountered. 1643 *----------------------------------------------------------------------- 1644 */ 1645 1646 void 1647 Suff_FindDeps(GNode *gn) 1648 { 1649 1650 SuffFindDeps(gn, &srclist); 1651 while (SuffRemoveSrc(&srclist)) 1652 continue; 1653 } 1654 1655 1656 static void 1657 SuffFindDeps(GNode *gn, Lst slst) 1658 { 1659 if (gn->type & OP_DEPS_FOUND) { 1660 /* 1661 * If dependencies already found, no need to do it again... 1662 */ 1663 return; 1664 } else { 1665 gn->type |= OP_DEPS_FOUND; 1666 } 1667 1668 if (DEBUG(SUFF)) 1669 printf("SuffFindDeps (%s)\n", gn->name); 1670 1671 current_node = gn; 1672 if (gn->type & OP_ARCHV) 1673 SuffFindArchiveDeps(gn, slst); 1674 else 1675 SuffFindNormalDeps(gn, slst); 1676 current_node = NULL; 1677 } 1678 1679 /*- 1680 *----------------------------------------------------------------------- 1681 * Suff_Init -- 1682 * Initialize suffixes module 1683 * 1684 * Side Effects: 1685 * Many 1686 *----------------------------------------------------------------------- 1687 */ 1688 void 1689 Suff_Init(void) 1690 { 1691 Static_Lst_Init(&srclist); 1692 ohash_init(&transforms, 4, &gnode_info); 1693 1694 /* 1695 * Create null suffix for single-suffix rules (POSIX). The thing doesn't 1696 * actually go on the suffix list or everyone will think that's its 1697 * suffix. 1698 */ 1699 emptySuff = new_suffix(""); 1700 make_suffix_known(emptySuff); 1701 Dir_Concat(&emptySuff->searchPath, defaultPath); 1702 ohash_init(&suffixes, 4, &suff_info); 1703 order = 0; 1704 clear_suffixes(); 1705 special_path_hack(); 1706 1707 } 1708 1709 1710 /********************* DEBUGGING FUNCTIONS **********************/ 1711 1712 static void 1713 SuffPrintName(void *p) 1714 { 1715 const Suff *s = p; 1716 printf("%s ", s == emptySuff ? "<empty>" : s->name); 1717 } 1718 1719 static void 1720 SuffPrintSuff(void *sp) 1721 { 1722 Suff *s = sp; 1723 1724 printf("# %-5s ", s->name); 1725 1726 if (!Lst_IsEmpty(&s->parents)) { 1727 printf(" ->"); 1728 Lst_Every(&s->parents, SuffPrintName); 1729 } 1730 if (!Lst_IsEmpty(&s->children)) { 1731 printf(" <-"); 1732 Lst_Every(&s->children, SuffPrintName); 1733 } 1734 fputc('\n', stdout); 1735 } 1736 1737 static void 1738 SuffPrintTrans(GNode *t) 1739 { 1740 printf("%-16s: ", t->name); 1741 Targ_PrintType(t->type); 1742 fputc('\n', stdout); 1743 Lst_Every(&t->commands, Targ_PrintCmd); 1744 fputc('\n', stdout); 1745 } 1746 1747 static int 1748 compare_order(const void *a, const void *b) 1749 { 1750 const Suff **pa = (const Suff **)a; 1751 const Suff **pb = (const Suff **)b; 1752 return (*pb)->order - (*pa)->order; 1753 } 1754 1755 static void 1756 print_path(Suff *s) 1757 { 1758 /* do we need to print it ? compare against defaultPath */ 1759 LstNode ln1, ln2; 1760 bool first = true; 1761 1762 for (ln1 = Lst_First(&s->searchPath), ln2 = Lst_First(defaultPath); 1763 ln1 != NULL && ln2 != NULL; 1764 ln1 = Lst_Adv(ln1)) { 1765 if (Lst_Datum(ln1) == Lst_Datum(ln2)) { 1766 ln2 = Lst_Adv(ln2); 1767 continue; 1768 } 1769 if (first) { 1770 printf(".PATH%s:", s->name); 1771 first = false; 1772 } 1773 printf(" %s", PathEntry_name(Lst_Datum(ln1))); 1774 } 1775 if (!first) 1776 printf("\n\n"); 1777 } 1778 1779 void 1780 Suff_PrintAll(void) 1781 { 1782 Suff **t; 1783 GNode **u; 1784 unsigned int i; 1785 bool reprint; 1786 1787 1788 printf("# Suffixes graph\n"); 1789 t = sort_ohash_by_name(&suffixes); 1790 for (i = 0; t[i] != NULL; i++) 1791 if (!(t[i]->flags & SUFF_PATH)) 1792 SuffPrintSuff(t[i]); 1793 1794 printf("\n.PATH: "); 1795 Dir_PrintPath(defaultPath); 1796 printf("\n\n"); 1797 for (i = 0; t[i] != NULL; i++) 1798 if (!(t[i]->flags & SUFF_PATH)) 1799 print_path(t[i]); 1800 free(t); 1801 1802 reprint = false; 1803 t = sort_ohash(&suffixes, compare_order); 1804 printf(".SUFFIXES:"); 1805 for (i = 0; t[i] != NULL; i++) { 1806 if (t[i]->flags & SUFF_PATH) 1807 continue; 1808 printf(" %s", t[i]->name); 1809 if (!(t[i]->flags & SUFF_ACTIVE)) 1810 reprint = true; 1811 } 1812 printf("\n\n"); 1813 u = sort_ohash_by_name(&transforms); 1814 for (i = 0; u[i] != NULL; i++) 1815 SuffPrintTrans(u[i]); 1816 free(u); 1817 1818 if (reprint) { 1819 printf(".SUFFIXES:"); 1820 for (i = 0; t[i] != NULL; i++) 1821 if (t[i]->flags & SUFF_ACTIVE) 1822 printf(" %s", t[i]->name); 1823 printf("\n"); 1824 } 1825 free(t); 1826 } 1827 1828 #ifdef DEBUG_SRC 1829 static void 1830 PrintAddr(void *a) 1831 { 1832 printf("%lx ", (unsigned long)a); 1833 } 1834 #endif 1835