contrib/bmake/suff.c

   1 /*      $NetBSD: suff.c,v 1.69 2011/09/29 23:38:04 sjg 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 #ifndef MAKE_NATIVE
  72 static char rcsid[] = "$NetBSD: suff.c,v 1.69 2011/09/29 23:38:04 sjg Exp $";
  73 #else
  74 #include <sys/cdefs.h>
  75 #ifndef lint
  76 #if 0
  77 static char sccsid[] = "@(#)suff.c      8.4 (Berkeley) 3/21/94";
  78 #else
  79 __RCSID("$NetBSD: suff.c,v 1.69 2011/09/29 23:38:04 sjg Exp $");
  80 #endif
  81 #endif /* not lint */
  82 #endif
  83
  84 /*-
  85  * suff.c --
  86  *      Functions to maintain suffix lists and find implicit dependents
  87  *      using suffix transformation rules
  88  *
  89  * Interface:
  90  *      Suff_Init               Initialize all things to do with suffixes.
  91  *
  92  *      Suff_End                Cleanup the module
  93  *
  94  *      Suff_DoPaths            This function is used to make life easier
  95  *                              when searching for a file according to its
  96  *                              suffix. It takes the global search path,
  97  *                              as defined using the .PATH: target, and appends
  98  *                              its directories to the path of each of the
  99  *                              defined suffixes, as specified using
 100  *                              .PATH<suffix>: targets. In addition, all
 101  *                              directories given for suffixes labeled as
 102  *                              include files or libraries, using the .INCLUDES
 103  *                              or .LIBS targets, are played with using
 104  *                              Dir_MakeFlags to create the .INCLUDES and
 105  *                              .LIBS global variables.
 106  *
 107  *      Suff_ClearSuffixes      Clear out all the suffixes and defined
 108  *                              transformations.
 109  *
 110  *      Suff_IsTransform        Return TRUE if the passed string is the lhs
 111  *                              of a transformation rule.
 112  *
 113  *      Suff_AddSuffix          Add the passed string as another known suffix.
 114  *
 115  *      Suff_GetPath            Return the search path for the given suffix.
 116  *
 117  *      Suff_AddInclude         Mark the given suffix as denoting an include
 118  *                              file.
 119  *
 120  *      Suff_AddLib             Mark the given suffix as denoting a library.
 121  *
 122  *      Suff_AddTransform       Add another transformation to the suffix
 123  *                              graph. Returns  GNode suitable for framing, I
 124  *                              mean, tacking commands, attributes, etc. on.
 125  *
 126  *      Suff_SetNull            Define the suffix to consider the suffix of
 127  *                              any file that doesn't have a known one.
 128  *
 129  *      Suff_FindDeps           Find implicit sources for and the location of
 130  *                              a target based on its suffix. Returns the
 131  *                              bottom-most node added to the graph or NULL
 132  *                              if the target had no implicit sources.
 133  *
 134  *      Suff_FindPath           Return the appropriate path to search in
 135  *                              order to find the node.
 136  */
 137
 138 #include          <stdio.h>
 139 #include          "make.h"
 140 #include          "hash.h"
 141 #include          "dir.h"
 142
 143 static Lst       sufflist;      /* Lst of suffixes */
 144 #ifdef CLEANUP
 145 static Lst       suffClean;     /* Lst of suffixes to be cleaned */
 146 #endif
 147 static Lst       srclist;       /* Lst of sources */
 148 static Lst       transforms;    /* Lst of transformation rules */
 149
 150 static int        sNum = 0;     /* Counter for assigning suffix numbers */
 151
 152 /*
 153  * Structure describing an individual suffix.
 154  */
 155 typedef struct _Suff {
 156     char         *name;         /* The suffix itself */
 157     int          nameLen;       /* Length of the suffix */
 158     short        flags;         /* Type of suffix */
 159 #define SUFF_INCLUDE      0x01      /* One which is #include'd */
 160 #define SUFF_LIBRARY      0x02      /* One which contains a library */
 161 #define SUFF_NULL         0x04      /* The empty suffix */
 162     Lst          searchPath;    /* The path along which files of this suffix
 163                                  * may be found */
 164     int          sNum;          /* The suffix number */
 165     int          refCount;      /* Reference count of list membership */
 166     Lst          parents;       /* Suffixes we have a transformation to */
 167     Lst          children;      /* Suffixes we have a transformation from */
 168     Lst          ref;           /* List of lists this suffix is referenced */
 169 } Suff;
 170
 171 /*
 172  * for SuffSuffIsSuffix
 173  */
 174 typedef struct {
 175     char        *ename;         /* The end of the name */
 176     int          len;           /* Length of the name */
 177 } SuffixCmpData;
 178
 179 /*
 180  * Structure used in the search for implied sources.
 181  */
 182 typedef struct _Src {
 183     char            *file;      /* The file to look for */
 184     char            *pref;      /* Prefix from which file was formed */
 185     Suff            *suff;      /* The suffix on the file */
 186     struct _Src     *parent;    /* The Src for which this is a source */
 187     GNode           *node;      /* The node describing the file */
 188     int             children;   /* Count of existing children (so we don't free
 189                                  * this thing too early or never nuke it) */
 190 #ifdef DEBUG_SRC
 191     Lst             cp;         /* Debug; children list */
 192 #endif
 193 } Src;
 194
 195 /*
 196  * A structure for passing more than one argument to the Lst-library-invoked
 197  * function...
 198  */
 199 typedef struct {
 200     Lst            l;
 201     Src            *s;
 202 } LstSrc;
 203
 204 typedef struct {
 205     GNode         **gn;
 206     Suff           *s;
 207     Boolean         r;
 208 } GNodeSuff;
 209
 210 static Suff         *suffNull;  /* The NULL suffix for this run */
 211 static Suff         *emptySuff; /* The empty suffix required for POSIX
 212                                  * single-suffix transformation rules */
 213
 214
 215 static const char *SuffStrIsPrefix(const char *, const char *);
 216 static char *SuffSuffIsSuffix(const Suff *, const SuffixCmpData *);
 217 static int SuffSuffIsSuffixP(const void *, const void *);
 218 static int SuffSuffHasNameP(const void *, const void *);
 219 static int SuffSuffIsPrefix(const void *, const void *);
 220 static int SuffGNHasNameP(const void *, const void *);
 221 static void SuffUnRef(void *, void *);
 222 static void SuffFree(void *);
 223 static void SuffInsert(Lst, Suff *);
 224 static void SuffRemove(Lst, Suff *);
 225 static Boolean SuffParseTransform(char *, Suff **, Suff **);
 226 static int SuffRebuildGraph(void *, void *);
 227 static int SuffScanTargets(void *, void *);
 228 static int SuffAddSrc(void *, void *);
 229 static int SuffRemoveSrc(Lst);
 230 static void SuffAddLevel(Lst, Src *);
 231 static Src *SuffFindThem(Lst, Lst);
 232 static Src *SuffFindCmds(Src *, Lst);
 233 static void SuffExpandChildren(LstNode, GNode *);
 234 static void SuffExpandWildcards(LstNode, GNode *);
 235 static Boolean SuffApplyTransform(GNode *, GNode *, Suff *, Suff *);
 236 static void SuffFindDeps(GNode *, Lst);
 237 static void SuffFindArchiveDeps(GNode *, Lst);
 238 static void SuffFindNormalDeps(GNode *, Lst);
 239 static int SuffPrintName(void *, void *);
 240 static int SuffPrintSuff(void *, void *);
 241 static int SuffPrintTrans(void *, void *);
 242
 243         /*************** Lst Predicates ****************/
 244 /*-
 245  *-----------------------------------------------------------------------
 246  * SuffStrIsPrefix  --
 247  *      See if pref is a prefix of str.
 248  *
 249  * Input:
 250  *      pref            possible prefix
 251  *      str             string to check
 252  *
 253  * Results:
 254  *      NULL if it ain't, pointer to character in str after prefix if so
 255  *
 256  * Side Effects:
 257  *      None
 258  *-----------------------------------------------------------------------
 259  */
 260 static const char *
 261 SuffStrIsPrefix(const char *pref, const char *str)
 262 {
 263     while (*str && *pref == *str) {
 264         pref++;
 265         str++;
 266     }
 267
 268     return (*pref ? NULL : str);
 269 }
 270
 271 /*-
 272  *-----------------------------------------------------------------------
 273  * SuffSuffIsSuffix  --
 274  *      See if suff is a suffix of str. sd->ename should point to THE END
 275  *      of the string to check. (THE END == the null byte)
 276  *
 277  * Input:
 278  *      s               possible suffix
 279  *      sd              string to examine
 280  *
 281  * Results:
 282  *      NULL if it ain't, pointer to character in str before suffix if
 283  *      it is.
 284  *
 285  * Side Effects:
 286  *      None
 287  *-----------------------------------------------------------------------
 288  */
 289 static char *
 290 SuffSuffIsSuffix(const Suff *s, const SuffixCmpData *sd)
 291 {
 292     char  *p1;          /* Pointer into suffix name */
 293     char  *p2;          /* Pointer into string being examined */
 294
 295     if (sd->len < s->nameLen)
 296         return NULL;            /* this string is shorter than the suffix */
 297
 298     p1 = s->name + s->nameLen;
 299     p2 = sd->ename;
 300
 301     while (p1 >= s->name && *p1 == *p2) {
 302         p1--;
 303         p2--;
 304     }
 305
 306     return (p1 == s->name - 1 ? p2 : NULL);
 307 }
 308
 309 /*-
 310  *-----------------------------------------------------------------------
 311  * SuffSuffIsSuffixP --
 312  *      Predicate form of SuffSuffIsSuffix. Passed as the callback function
 313  *      to Lst_Find.
 314  *
 315  * Results:
 316  *      0 if the suffix is the one desired, non-zero if not.
 317  *
 318  * Side Effects:
 319  *      None.
 320  *
 321  *-----------------------------------------------------------------------
 322  */
 323 static int
 324 SuffSuffIsSuffixP(const void *s, const void *sd)
 325 {
 326     return(!SuffSuffIsSuffix(s, sd));
 327 }
 328
 329 /*-
 330  *-----------------------------------------------------------------------
 331  * SuffSuffHasNameP --
 332  *      Callback procedure for finding a suffix based on its name. Used by
 333  *      Suff_GetPath.
 334  *
 335  * Input:
 336  *      s               Suffix to check
 337  *      sd              Desired name
 338  *
 339  * Results:
 340  *      0 if the suffix is of the given name. non-zero otherwise.
 341  *
 342  * Side Effects:
 343  *      None
 344  *-----------------------------------------------------------------------
 345  */
 346 static int
 347 SuffSuffHasNameP(const void *s, const void *sname)
 348 {
 349     return (strcmp(sname, ((const Suff *)s)->name));
 350 }
 351
 352 /*-
 353  *-----------------------------------------------------------------------
 354  * SuffSuffIsPrefix  --
 355  *      See if the suffix described by s is a prefix of the string. Care
 356  *      must be taken when using this to search for transformations and
 357  *      what-not, since there could well be two suffixes, one of which
 358  *      is a prefix of the other...
 359  *
 360  * Input:
 361  *      s               suffix to compare
 362  *      str             string to examine
 363  *
 364  * Results:
 365  *      0 if s is a prefix of str. non-zero otherwise
 366  *
 367  * Side Effects:
 368  *      None
 369  *-----------------------------------------------------------------------
 370  */
 371 static int
 372 SuffSuffIsPrefix(const void *s, const void *str)
 373 {
 374     return SuffStrIsPrefix(((const Suff *)s)->name, str) == NULL;
 375 }
 376
 377 /*-
 378  *-----------------------------------------------------------------------
 379  * SuffGNHasNameP  --
 380  *      See if the graph node has the desired name
 381  *
 382  * Input:
 383  *      gn              current node we're looking at
 384  *      name            name we're looking for
 385  *
 386  * Results:
 387  *      0 if it does. non-zero if it doesn't
 388  *
 389  * Side Effects:
 390  *      None
 391  *-----------------------------------------------------------------------
 392  */
 393 static int
 394 SuffGNHasNameP(const void *gn, const void *name)
 395 {
 396     return (strcmp(name, ((const GNode *)gn)->name));
 397 }
 398
 399             /*********** Maintenance Functions ************/
 400
 401 static void
 402 SuffUnRef(void *lp, void *sp)
 403 {
 404     Lst l = (Lst) lp;
 405
 406     LstNode ln = Lst_Member(l, sp);
 407     if (ln != NULL) {
 408         Lst_Remove(l, ln);
 409         ((Suff *)sp)->refCount--;
 410     }
 411 }
 412
 413 /*-
 414  *-----------------------------------------------------------------------
 415  * SuffFree  --
 416  *      Free up all memory associated with the given suffix structure.
 417  *
 418  * Results:
 419  *      none
 420  *
 421  * Side Effects:
 422  *      the suffix entry is detroyed
 423  *-----------------------------------------------------------------------
 424  */
 425 static void
 426 SuffFree(void *sp)
 427 {
 428     Suff           *s = (Suff *)sp;
 429
 430     if (s == suffNull)
 431         suffNull = NULL;
 432
 433     if (s == emptySuff)
 434         emptySuff = NULL;
 435
 436 #ifdef notdef
 437     /* We don't delete suffixes in order, so we cannot use this */
 438     if (s->refCount)
 439         Punt("Internal error deleting suffix `%s' with refcount = %d", s->name,
 440             s->refCount);
 441 #endif
 442
 443     Lst_Destroy(s->ref, NULL);
 444     Lst_Destroy(s->children, NULL);
 445     Lst_Destroy(s->parents, NULL);
 446     Lst_Destroy(s->searchPath, Dir_Destroy);
 447
 448     free(s->name);
 449     free(s);
 450 }
 451
 452 /*-
 453  *-----------------------------------------------------------------------
 454  * SuffRemove  --
 455  *      Remove the suffix into the list
 456  *
 457  * Results:
 458  *      None
 459  *
 460  * Side Effects:
 461  *      The reference count for the suffix is decremented and the
 462  *      suffix is possibly freed
 463  *-----------------------------------------------------------------------
 464  */
 465 static void
 466 SuffRemove(Lst l, Suff *s)
 467 {
 468     SuffUnRef(l, s);
 469     if (s->refCount == 0) {
 470         SuffUnRef(sufflist, s);
 471         SuffFree(s);
 472     }
 473 }
 474 \f
 475 /*-
 476  *-----------------------------------------------------------------------
 477  * SuffInsert  --
 478  *      Insert the suffix into the list keeping the list ordered by suffix
 479  *      numbers.
 480  *
 481  * Input:
 482  *      l               the list where in s should be inserted
 483  *      s               the suffix to insert
 484  *
 485  * Results:
 486  *      None
 487  *
 488  * Side Effects:
 489  *      The reference count of the suffix is incremented
 490  *-----------------------------------------------------------------------
 491  */
 492 static void
 493 SuffInsert(Lst l, Suff *s)
 494 {
 495     LstNode       ln;           /* current element in l we're examining */
 496     Suff          *s2 = NULL;   /* the suffix descriptor in this element */
 497
 498     if (Lst_Open(l) == FAILURE) {
 499         return;
 500     }
 501     while ((ln = Lst_Next(l)) != NULL) {
 502         s2 = (Suff *)Lst_Datum(ln);
 503         if (s2->sNum >= s->sNum) {
 504             break;
 505         }
 506     }
 507
 508     Lst_Close(l);
 509     if (DEBUG(SUFF)) {
 510         fprintf(debug_file, "inserting %s(%d)...", s->name, s->sNum);
 511     }
 512     if (ln == NULL) {
 513         if (DEBUG(SUFF)) {
 514             fprintf(debug_file, "at end of list\n");
 515         }
 516         (void)Lst_AtEnd(l, s);
 517         s->refCount++;
 518         (void)Lst_AtEnd(s->ref, l);
 519     } else if (s2->sNum != s->sNum) {
 520         if (DEBUG(SUFF)) {
 521             fprintf(debug_file, "before %s(%d)\n", s2->name, s2->sNum);
 522         }
 523         (void)Lst_InsertBefore(l, ln, s);
 524         s->refCount++;
 525         (void)Lst_AtEnd(s->ref, l);
 526     } else if (DEBUG(SUFF)) {
 527         fprintf(debug_file, "already there\n");
 528     }
 529 }
 530
 531 /*-
 532  *-----------------------------------------------------------------------
 533  * Suff_ClearSuffixes --
 534  *      This is gross. Nuke the list of suffixes but keep all transformation
 535  *      rules around. The transformation graph is destroyed in this process,
 536  *      but we leave the list of rules so when a new graph is formed the rules
 537  *      will remain.
 538  *      This function is called from the parse module when a
 539  *      .SUFFIXES:\n line is encountered.
 540  *
 541  * Results:
 542  *      none
 543  *
 544  * Side Effects:
 545  *      the sufflist and its graph nodes are destroyed
 546  *-----------------------------------------------------------------------
 547  */
 548 void
 549 Suff_ClearSuffixes(void)
 550 {
 551 #ifdef CLEANUP
 552     Lst_Concat(suffClean, sufflist, LST_CONCLINK);
 553 #endif
 554     sufflist = Lst_Init(FALSE);
 555     sNum = 0;
 556     suffNull = emptySuff;
 557 }
 558
 559 /*-
 560  *-----------------------------------------------------------------------
 561  * SuffParseTransform --
 562  *      Parse a transformation string to find its two component suffixes.
 563  *
 564  * Input:
 565  *      str             String being parsed
 566  *      srcPtr          Place to store source of trans.
 567  *      targPtr         Place to store target of trans.
 568  *
 569  * Results:
 570  *      TRUE if the string is a valid transformation and FALSE otherwise.
 571  *
 572  * Side Effects:
 573  *      The passed pointers are overwritten.
 574  *
 575  *-----------------------------------------------------------------------
 576  */
 577 static Boolean
 578 SuffParseTransform(char *str, Suff **srcPtr, Suff **targPtr)
 579 {
 580     LstNode             srcLn;      /* element in suffix list of trans source*/
 581     Suff                *src;       /* Source of transformation */
 582     LstNode             targLn;     /* element in suffix list of trans target*/
 583     char                *str2;      /* Extra pointer (maybe target suffix) */
 584     LstNode             singleLn;   /* element in suffix list of any suffix
 585                                      * that exactly matches str */
 586     Suff                *single = NULL;/* Source of possible transformation to
 587                                      * null suffix */
 588
 589     srcLn = NULL;
 590     singleLn = NULL;
 591
 592     /*
 593      * Loop looking first for a suffix that matches the start of the
 594      * string and then for one that exactly matches the rest of it. If
 595      * we can find two that meet these criteria, we've successfully
 596      * parsed the string.
 597      */
 598     for (;;) {
 599         if (srcLn == NULL) {
 600             srcLn = Lst_Find(sufflist, str, SuffSuffIsPrefix);
 601         } else {
 602             srcLn = Lst_FindFrom(sufflist, Lst_Succ(srcLn), str,
 603                                   SuffSuffIsPrefix);
 604         }
 605         if (srcLn == NULL) {
 606             /*
 607              * Ran out of source suffixes -- no such rule
 608              */
 609             if (singleLn != NULL) {
 610                 /*
 611                  * Not so fast Mr. Smith! There was a suffix that encompassed
 612                  * the entire string, so we assume it was a transformation
 613                  * to the null suffix (thank you POSIX). We still prefer to
 614                  * find a double rule over a singleton, hence we leave this
 615                  * check until the end.
 616                  *
 617                  * XXX: Use emptySuff over suffNull?
 618                  */
 619                 *srcPtr = single;
 620                 *targPtr = suffNull;
 621                 return(TRUE);
 622             }
 623             return (FALSE);
 624         }
 625         src = (Suff *)Lst_Datum(srcLn);
 626         str2 = str + src->nameLen;
 627         if (*str2 == '\0') {
 628             single = src;
 629             singleLn = srcLn;
 630         } else {
 631             targLn = Lst_Find(sufflist, str2, SuffSuffHasNameP);
 632             if (targLn != NULL) {
 633                 *srcPtr = src;
 634                 *targPtr = (Suff *)Lst_Datum(targLn);
 635                 return (TRUE);
 636             }
 637         }
 638     }
 639 }
 640
 641 /*-
 642  *-----------------------------------------------------------------------
 643  * Suff_IsTransform  --
 644  *      Return TRUE if the given string is a transformation rule
 645  *
 646  *
 647  * Input:
 648  *      str             string to check
 649  *
 650  * Results:
 651  *      TRUE if the string is a concatenation of two known suffixes.
 652  *      FALSE otherwise
 653  *
 654  * Side Effects:
 655  *      None
 656  *-----------------------------------------------------------------------
 657  */
 658 Boolean
 659 Suff_IsTransform(char *str)
 660 {
 661     Suff          *src, *targ;
 662
 663     return (SuffParseTransform(str, &src, &targ));
 664 }
 665
 666 /*-
 667  *-----------------------------------------------------------------------
 668  * Suff_AddTransform --
 669  *      Add the transformation rule described by the line to the
 670  *      list of rules and place the transformation itself in the graph
 671  *
 672  * Input:
 673  *      line            name of transformation to add
 674  *
 675  * Results:
 676  *      The node created for the transformation in the transforms list
 677  *
 678  * Side Effects:
 679  *      The node is placed on the end of the transforms Lst and links are
 680  *      made between the two suffixes mentioned in the target name
 681  *-----------------------------------------------------------------------
 682  */
 683 GNode *
 684 Suff_AddTransform(char *line)
 685 {
 686     GNode         *gn;          /* GNode of transformation rule */
 687     Suff          *s,           /* source suffix */
 688                   *t;           /* target suffix */
 689     LstNode       ln;           /* Node for existing transformation */
 690
 691     ln = Lst_Find(transforms, line, SuffGNHasNameP);
 692     if (ln == NULL) {
 693         /*
 694          * Make a new graph node for the transformation. It will be filled in
 695          * by the Parse module.
 696          */
 697         gn = Targ_NewGN(line);
 698         (void)Lst_AtEnd(transforms, gn);
 699     } else {
 700         /*
 701          * New specification for transformation rule. Just nuke the old list
 702          * of commands so they can be filled in again... We don't actually
 703          * free the commands themselves, because a given command can be
 704          * attached to several different transformations.
 705          */
 706         gn = (GNode *)Lst_Datum(ln);
 707         Lst_Destroy(gn->commands, NULL);
 708         Lst_Destroy(gn->children, NULL);
 709         gn->commands = Lst_Init(FALSE);
 710         gn->children = Lst_Init(FALSE);
 711     }
 712
 713     gn->type = OP_TRANSFORM;
 714
 715     (void)SuffParseTransform(line, &s, &t);
 716
 717     /*
 718      * link the two together in the proper relationship and order
 719      */
 720     if (DEBUG(SUFF)) {
 721         fprintf(debug_file, "defining transformation from `%s' to `%s'\n",
 722                 s->name, t->name);
 723     }
 724     SuffInsert(t->children, s);
 725     SuffInsert(s->parents, t);
 726
 727     return (gn);
 728 }
 729
 730 /*-
 731  *-----------------------------------------------------------------------
 732  * Suff_EndTransform --
 733  *      Handle the finish of a transformation definition, removing the
 734  *      transformation from the graph if it has neither commands nor
 735  *      sources. This is a callback procedure for the Parse module via
 736  *      Lst_ForEach
 737  *
 738  * Input:
 739  *      gnp             Node for transformation
 740  *      dummy           Node for transformation
 741  *
 742  * Results:
 743  *      === 0
 744  *
 745  * Side Effects:
 746  *      If the node has no commands or children, the children and parents
 747  *      lists of the affected suffixes are altered.
 748  *
 749  *-----------------------------------------------------------------------
 750  */
 751 int
 752 Suff_EndTransform(void *gnp, void *dummy)
 753 {
 754     GNode *gn = (GNode *)gnp;
 755
 756     if ((gn->type & OP_DOUBLEDEP) && !Lst_IsEmpty (gn->cohorts))
 757         gn = (GNode *)Lst_Datum(Lst_Last(gn->cohorts));
 758     if ((gn->type & OP_TRANSFORM) && Lst_IsEmpty(gn->commands) &&
 759         Lst_IsEmpty(gn->children))
 760     {
 761         Suff    *s, *t;
 762
 763         /*
 764          * SuffParseTransform() may fail for special rules which are not
 765          * actual transformation rules. (e.g. .DEFAULT)
 766          */
 767         if (SuffParseTransform(gn->name, &s, &t)) {
 768             Lst  p;
 769
 770             if (DEBUG(SUFF)) {
 771                 fprintf(debug_file, "deleting transformation from `%s' to `%s'\n",
 772                 s->name, t->name);
 773             }
 774
 775             /*
 776              * Store s->parents because s could be deleted in SuffRemove
 777              */
 778             p = s->parents;
 779
 780             /*
 781              * Remove the source from the target's children list. We check for a
 782              * nil return to handle a beanhead saying something like
 783              *  .c.o .c.o:
 784              *
 785              * We'll be called twice when the next target is seen, but .c and .o
 786              * are only linked once...
 787              */
 788             SuffRemove(t->children, s);
 789
 790             /*
 791              * Remove the target from the source's parents list
 792              */
 793             SuffRemove(p, t);
 794         }
 795     } else if ((gn->type & OP_TRANSFORM) && DEBUG(SUFF)) {
 796         fprintf(debug_file, "transformation %s complete\n", gn->name);
 797     }
 798
 799     return(dummy ? 0 : 0);
 800 }
 801
 802 /*-
 803  *-----------------------------------------------------------------------
 804  * SuffRebuildGraph --
 805  *      Called from Suff_AddSuffix via Lst_ForEach to search through the
 806  *      list of existing transformation rules and rebuild the transformation
 807  *      graph when it has been destroyed by Suff_ClearSuffixes. If the
 808  *      given rule is a transformation involving this suffix and another,
 809  *      existing suffix, the proper relationship is established between
 810  *      the two.
 811  *
 812  * Input:
 813  *      transformp      Transformation to test
 814  *      sp              Suffix to rebuild
 815  *
 816  * Results:
 817  *      Always 0.
 818  *
 819  * Side Effects:
 820  *      The appropriate links will be made between this suffix and
 821  *      others if transformation rules exist for it.
 822  *
 823  *-----------------------------------------------------------------------
 824  */
 825 static int
 826 SuffRebuildGraph(void *transformp, void *sp)
 827 {
 828     GNode       *transform = (GNode *)transformp;
 829     Suff        *s = (Suff *)sp;
 830     char        *cp;
 831     LstNode     ln;
 832     Suff        *s2;
 833     SuffixCmpData sd;
 834
 835     /*
 836      * First see if it is a transformation from this suffix.
 837      */
 838     cp = UNCONST(SuffStrIsPrefix(s->name, transform->name));
 839     if (cp != NULL) {
 840         ln = Lst_Find(sufflist, cp, SuffSuffHasNameP);
 841         if (ln != NULL) {
 842             /*
 843              * Found target. Link in and return, since it can't be anything
 844              * else.
 845              */
 846             s2 = (Suff *)Lst_Datum(ln);
 847             SuffInsert(s2->children, s);
 848             SuffInsert(s->parents, s2);
 849             return(0);
 850         }
 851     }
 852
 853     /*
 854      * Not from, maybe to?
 855      */
 856     sd.len = strlen(transform->name);
 857     sd.ename = transform->name + sd.len;
 858     cp = SuffSuffIsSuffix(s, &sd);
 859     if (cp != NULL) {
 860         /*
 861          * Null-terminate the source suffix in order to find it.
 862          */
 863         cp[1] = '\0';
 864         ln = Lst_Find(sufflist, transform->name, SuffSuffHasNameP);
 865         /*
 866          * Replace the start of the target suffix
 867          */
 868         cp[1] = s->name[0];
 869         if (ln != NULL) {
 870             /*
 871              * Found it -- establish the proper relationship
 872              */
 873             s2 = (Suff *)Lst_Datum(ln);
 874             SuffInsert(s->children, s2);
 875             SuffInsert(s2->parents, s);
 876         }
 877     }
 878     return(0);
 879 }
 880
 881 /*-
 882  *-----------------------------------------------------------------------
 883  * SuffScanTargets --
 884  *      Called from Suff_AddSuffix via Lst_ForEach to search through the
 885  *      list of existing targets and find if any of the existing targets
 886  *      can be turned into a transformation rule.
 887  *
 888  * Results:
 889  *      1 if a new main target has been selected, 0 otherwise.
 890  *
 891  * Side Effects:
 892  *      If such a target is found and the target is the current main
 893  *      target, the main target is set to NULL and the next target
 894  *      examined (if that exists) becomes the main target.
 895  *
 896  *-----------------------------------------------------------------------
 897  */
 898 static int
 899 SuffScanTargets(void *targetp, void *gsp)
 900 {
 901     GNode       *target = (GNode *)targetp;
 902     GNodeSuff   *gs = (GNodeSuff *)gsp;
 903     Suff        *s, *t;
 904     char        *ptr;
 905
 906     if (*gs->gn == NULL && gs->r && (target->type & OP_NOTARGET) == 0) {
 907         *gs->gn = target;
 908         Targ_SetMain(target);
 909         return 1;
 910     }
 911
 912     if ((unsigned int)target->type == OP_TRANSFORM)
 913         return 0;
 914
 915     if ((ptr = strstr(target->name, gs->s->name)) == NULL ||
 916         ptr == target->name)
 917         return 0;
 918
 919     if (SuffParseTransform(target->name, &s, &t)) {
 920         if (*gs->gn == target) {
 921             gs->r = TRUE;
 922             *gs->gn = NULL;
 923             Targ_SetMain(NULL);
 924         }
 925         Lst_Destroy(target->children, NULL);
 926         target->children = Lst_Init(FALSE);
 927         target->type = OP_TRANSFORM;
 928         /*
 929          * link the two together in the proper relationship and order
 930          */
 931         if (DEBUG(SUFF)) {
 932             fprintf(debug_file, "defining transformation from `%s' to `%s'\n",
 933                 s->name, t->name);
 934         }
 935         SuffInsert(t->children, s);
 936         SuffInsert(s->parents, t);
 937     }
 938     return 0;
 939 }
 940
 941 /*-
 942  *-----------------------------------------------------------------------
 943  * Suff_AddSuffix --
 944  *      Add the suffix in string to the end of the list of known suffixes.
 945  *      Should we restructure the suffix graph? Make doesn't...
 946  *
 947  * Input:
 948  *      str             the name of the suffix to add
 949  *
 950  * Results:
 951  *      None
 952  *
 953  * Side Effects:
 954  *      A GNode is created for the suffix and a Suff structure is created and
 955  *      added to the suffixes list unless the suffix was already known.
 956  *      The mainNode passed can be modified if a target mutated into a
 957  *      transform and that target happened to be the main target.
 958  *-----------------------------------------------------------------------
 959  */
 960 void
 961 Suff_AddSuffix(char *str, GNode **gn)
 962 {
 963     Suff          *s;       /* new suffix descriptor */
 964     LstNode       ln;
 965     GNodeSuff     gs;
 966
 967     ln = Lst_Find(sufflist, str, SuffSuffHasNameP);
 968     if (ln == NULL) {
 969         s = bmake_malloc(sizeof(Suff));
 970
 971         s->name =       bmake_strdup(str);
 972         s->nameLen =    strlen(s->name);
 973         s->searchPath = Lst_Init(FALSE);
 974         s->children =   Lst_Init(FALSE);
 975         s->parents =    Lst_Init(FALSE);
 976         s->ref =        Lst_Init(FALSE);
 977         s->sNum =       sNum++;
 978         s->flags =      0;
 979         s->refCount =   1;
 980
 981         (void)Lst_AtEnd(sufflist, s);
 982         /*
 983          * We also look at our existing targets list to see if adding
 984          * this suffix will make one of our current targets mutate into
 985          * a suffix rule. This is ugly, but other makes treat all targets
 986          * that start with a . as suffix rules.
 987          */
 988         gs.gn = gn;
 989         gs.s  = s;
 990         gs.r  = FALSE;
 991         Lst_ForEach(Targ_List(), SuffScanTargets, &gs);
 992         /*
 993          * Look for any existing transformations from or to this suffix.
 994          * XXX: Only do this after a Suff_ClearSuffixes?
 995          */
 996         Lst_ForEach(transforms, SuffRebuildGraph, s);
 997     }
 998 }
 999
1000 /*-
1001  *-----------------------------------------------------------------------
1002  * Suff_GetPath --
1003  *      Return the search path for the given suffix, if it's defined.
1004  *
1005  * Results:
1006  *      The searchPath for the desired suffix or NULL if the suffix isn't
1007  *      defined.
1008  *
1009  * Side Effects:
1010  *      None
1011  *-----------------------------------------------------------------------
1012  */
1013 Lst
1014 Suff_GetPath(char *sname)
1015 {
1016     LstNode       ln;
1017     Suff          *s;
1018
1019     ln = Lst_Find(sufflist, sname, SuffSuffHasNameP);
1020     if (ln == NULL) {
1021         return NULL;
1022     } else {
1023         s = (Suff *)Lst_Datum(ln);
1024         return (s->searchPath);
1025     }
1026 }
1027
1028 /*-
1029  *-----------------------------------------------------------------------
1030  * Suff_DoPaths --
1031  *      Extend the search paths for all suffixes to include the default
1032  *      search path.
1033  *
1034  * Results:
1035  *      None.
1036  *
1037  * Side Effects:
1038  *      The searchPath field of all the suffixes is extended by the
1039  *      directories in dirSearchPath. If paths were specified for the
1040  *      ".h" suffix, the directories are stuffed into a global variable
1041  *      called ".INCLUDES" with each directory preceded by a -I. The same
1042  *      is done for the ".a" suffix, except the variable is called
1043  *      ".LIBS" and the flag is -L.
1044  *-----------------------------------------------------------------------
1045  */
1046 void
1047 Suff_DoPaths(void)
1048 {
1049     Suff                *s;
1050     LstNode             ln;
1051     char                *ptr;
1052     Lst                 inIncludes; /* Cumulative .INCLUDES path */
1053     Lst                 inLibs;     /* Cumulative .LIBS path */
1054
1055     if (Lst_Open(sufflist) == FAILURE) {
1056         return;
1057     }
1058
1059     inIncludes = Lst_Init(FALSE);
1060     inLibs = Lst_Init(FALSE);
1061
1062     while ((ln = Lst_Next(sufflist)) != NULL) {
1063         s = (Suff *)Lst_Datum(ln);
1064         if (!Lst_IsEmpty (s->searchPath)) {
1065 #ifdef INCLUDES
1066             if (s->flags & SUFF_INCLUDE) {
1067                 Dir_Concat(inIncludes, s->searchPath);
1068             }
1069 #endif /* INCLUDES */
1070 #ifdef LIBRARIES
1071             if (s->flags & SUFF_LIBRARY) {
1072                 Dir_Concat(inLibs, s->searchPath);
1073             }
1074 #endif /* LIBRARIES */
1075             Dir_Concat(s->searchPath, dirSearchPath);
1076         } else {
1077             Lst_Destroy(s->searchPath, Dir_Destroy);
1078             s->searchPath = Lst_Duplicate(dirSearchPath, Dir_CopyDir);
1079         }
1080     }
1081
1082     Var_Set(".INCLUDES", ptr = Dir_MakeFlags("-I", inIncludes), VAR_GLOBAL, 0);
1083     free(ptr);
1084     Var_Set(".LIBS", ptr = Dir_MakeFlags("-L", inLibs), VAR_GLOBAL, 0);
1085     free(ptr);
1086
1087     Lst_Destroy(inIncludes, Dir_Destroy);
1088     Lst_Destroy(inLibs, Dir_Destroy);
1089
1090     Lst_Close(sufflist);
1091 }
1092
1093 /*-
1094  *-----------------------------------------------------------------------
1095  * Suff_AddInclude --
1096  *      Add the given suffix as a type of file which gets included.
1097  *      Called from the parse module when a .INCLUDES line is parsed.
1098  *      The suffix must have already been defined.
1099  *
1100  * Input:
1101  *      sname           Name of the suffix to mark
1102  *
1103  * Results:
1104  *      None.
1105  *
1106  * Side Effects:
1107  *      The SUFF_INCLUDE bit is set in the suffix's flags field
1108  *
1109  *-----------------------------------------------------------------------
1110  */
1111 void
1112 Suff_AddInclude(char *sname)
1113 {
1114     LstNode       ln;
1115     Suff          *s;
1116
1117     ln = Lst_Find(sufflist, sname, SuffSuffHasNameP);
1118     if (ln != NULL) {
1119         s = (Suff *)Lst_Datum(ln);
1120         s->flags |= SUFF_INCLUDE;
1121     }
1122 }
1123
1124 /*-
1125  *-----------------------------------------------------------------------
1126  * Suff_AddLib --
1127  *      Add the given suffix as a type of file which is a library.
1128  *      Called from the parse module when parsing a .LIBS line. The
1129  *      suffix must have been defined via .SUFFIXES before this is
1130  *      called.
1131  *
1132  * Input:
1133  *      sname           Name of the suffix to mark
1134  *
1135  * Results:
1136  *      None.
1137  *
1138  * Side Effects:
1139  *      The SUFF_LIBRARY bit is set in the suffix's flags field
1140  *
1141  *-----------------------------------------------------------------------
1142  */
1143 void
1144 Suff_AddLib(char *sname)
1145 {
1146     LstNode       ln;
1147     Suff          *s;
1148
1149     ln = Lst_Find(sufflist, sname, SuffSuffHasNameP);
1150     if (ln != NULL) {
1151         s = (Suff *)Lst_Datum(ln);
1152         s->flags |= SUFF_LIBRARY;
1153     }
1154 }
1155
1156           /********** Implicit Source Search Functions *********/
1157
1158 /*-
1159  *-----------------------------------------------------------------------
1160  * SuffAddSrc  --
1161  *      Add a suffix as a Src structure to the given list with its parent
1162  *      being the given Src structure. If the suffix is the null suffix,
1163  *      the prefix is used unaltered as the file name in the Src structure.
1164  *
1165  * Input:
1166  *      sp              suffix for which to create a Src structure
1167  *      lsp             list and parent for the new Src
1168  *
1169  * Results:
1170  *      always returns 0
1171  *
1172  * Side Effects:
1173  *      A Src structure is created and tacked onto the end of the list
1174  *-----------------------------------------------------------------------
1175  */
1176 static int
1177 SuffAddSrc(void *sp, void *lsp)
1178 {
1179     Suff        *s = (Suff *)sp;
1180     LstSrc      *ls = (LstSrc *)lsp;
1181     Src         *s2;        /* new Src structure */
1182     Src         *targ;      /* Target structure */
1183
1184     targ = ls->s;
1185
1186     if ((s->flags & SUFF_NULL) && (*s->name != '\0')) {
1187         /*
1188          * If the suffix has been marked as the NULL suffix, also create a Src
1189          * structure for a file with no suffix attached. Two birds, and all
1190          * that...
1191          */
1192         s2 = bmake_malloc(sizeof(Src));
1193         s2->file =      bmake_strdup(targ->pref);
1194         s2->pref =      targ->pref;
1195         s2->parent =    targ;
1196         s2->node =      NULL;
1197         s2->suff =      s;
1198         s->refCount++;
1199         s2->children =  0;
1200         targ->children += 1;
1201         (void)Lst_AtEnd(ls->l, s2);
1202 #ifdef DEBUG_SRC
1203         s2->cp = Lst_Init(FALSE);
1204         Lst_AtEnd(targ->cp, s2);
1205         fprintf(debug_file, "1 add %x %x to %x:", targ, s2, ls->l);
1206         Lst_ForEach(ls->l, PrintAddr, NULL);
1207         fprintf(debug_file, "\n");
1208 #endif
1209     }
1210     s2 = bmake_malloc(sizeof(Src));
1211     s2->file =      str_concat(targ->pref, s->name, 0);
1212     s2->pref =      targ->pref;
1213     s2->parent =    targ;
1214     s2->node =      NULL;
1215     s2->suff =      s;
1216     s->refCount++;
1217     s2->children =  0;
1218     targ->children += 1;
1219     (void)Lst_AtEnd(ls->l, s2);
1220 #ifdef DEBUG_SRC
1221     s2->cp = Lst_Init(FALSE);
1222     Lst_AtEnd(targ->cp, s2);
1223     fprintf(debug_file, "2 add %x %x to %x:", targ, s2, ls->l);
1224     Lst_ForEach(ls->l, PrintAddr, NULL);
1225     fprintf(debug_file, "\n");
1226 #endif
1227
1228     return(0);
1229 }
1230
1231 /*-
1232  *-----------------------------------------------------------------------
1233  * SuffAddLevel  --
1234  *      Add all the children of targ as Src structures to the given list
1235  *
1236  * Input:
1237  *      l               list to which to add the new level
1238  *      targ            Src structure to use as the parent
1239  *
1240  * Results:
1241  *      None
1242  *
1243  * Side Effects:
1244  *      Lots of structures are created and added to the list
1245  *-----------------------------------------------------------------------
1246  */
1247 static void
1248 SuffAddLevel(Lst l, Src *targ)
1249 {
1250     LstSrc         ls;
1251
1252     ls.s = targ;
1253     ls.l = l;
1254
1255     Lst_ForEach(targ->suff->children, SuffAddSrc, &ls);
1256 }
1257
1258 /*-
1259  *----------------------------------------------------------------------
1260  * SuffRemoveSrc --
1261  *      Free all src structures in list that don't have a reference count
1262  *
1263  * Results:
1264  *      Ture if an src was removed
1265  *
1266  * Side Effects:
1267  *      The memory is free'd.
1268  *----------------------------------------------------------------------
1269  */
1270 static int
1271 SuffRemoveSrc(Lst l)
1272 {
1273     LstNode ln;
1274     Src *s;
1275     int t = 0;
1276
1277     if (Lst_Open(l) == FAILURE) {
1278         return 0;
1279     }
1280 #ifdef DEBUG_SRC
1281     fprintf(debug_file, "cleaning %lx: ", (unsigned long) l);
1282     Lst_ForEach(l, PrintAddr, NULL);
1283     fprintf(debug_file, "\n");
1284 #endif
1285
1286
1287     while ((ln = Lst_Next(l)) != NULL) {
1288         s = (Src *)Lst_Datum(ln);
1289         if (s->children == 0) {
1290             free(s->file);
1291             if (!s->parent)
1292                 free(s->pref);
1293             else {
1294 #ifdef DEBUG_SRC
1295                 LstNode ln = Lst_Member(s->parent->cp, s);
1296                 if (ln != NULL)
1297                     Lst_Remove(s->parent->cp, ln);
1298 #endif
1299                 --s->parent->children;
1300             }
1301 #ifdef DEBUG_SRC
1302             fprintf(debug_file, "free: [l=%x] p=%x %d\n", l, s, s->children);
1303             Lst_Destroy(s->cp, NULL);
1304 #endif
1305             Lst_Remove(l, ln);
1306             free(s);
1307             t |= 1;
1308             Lst_Close(l);
1309             return TRUE;
1310         }
1311 #ifdef DEBUG_SRC
1312         else {
1313             fprintf(debug_file, "keep: [l=%x] p=%x %d: ", l, s, s->children);
1314             Lst_ForEach(s->cp, PrintAddr, NULL);
1315             fprintf(debug_file, "\n");
1316         }
1317 #endif
1318     }
1319
1320     Lst_Close(l);
1321
1322     return t;
1323 }
1324
1325 /*-
1326  *-----------------------------------------------------------------------
1327  * SuffFindThem --
1328  *      Find the first existing file/target in the list srcs
1329  *
1330  * Input:
1331  *      srcs            list of Src structures to search through
1332  *
1333  * Results:
1334  *      The lowest structure in the chain of transformations
1335  *
1336  * Side Effects:
1337  *      None
1338  *-----------------------------------------------------------------------
1339  */
1340 static Src *
1341 SuffFindThem(Lst srcs, Lst slst)
1342 {
1343     Src            *s;          /* current Src */
1344     Src            *rs;         /* returned Src */
1345     char           *ptr;
1346
1347     rs = NULL;
1348
1349     while (!Lst_IsEmpty (srcs)) {
1350         s = (Src *)Lst_DeQueue(srcs);
1351
1352         if (DEBUG(SUFF)) {
1353             fprintf(debug_file, "\ttrying %s...", s->file);
1354         }
1355
1356         /*
1357          * A file is considered to exist if either a node exists in the
1358          * graph for it or the file actually exists.
1359          */
1360         if (Targ_FindNode(s->file, TARG_NOCREATE) != NULL) {
1361 #ifdef DEBUG_SRC
1362             fprintf(debug_file, "remove %x from %x\n", s, srcs);
1363 #endif
1364             rs = s;
1365             break;
1366         }
1367
1368         if ((ptr = Dir_FindFile(s->file, s->suff->searchPath)) != NULL) {
1369             rs = s;
1370 #ifdef DEBUG_SRC
1371             fprintf(debug_file, "remove %x from %x\n", s, srcs);
1372 #endif
1373             free(ptr);
1374             break;
1375         }
1376
1377         if (DEBUG(SUFF)) {
1378             fprintf(debug_file, "not there\n");
1379         }
1380
1381         SuffAddLevel(srcs, s);
1382         Lst_AtEnd(slst, s);
1383     }
1384
1385     if (DEBUG(SUFF) && rs) {
1386         fprintf(debug_file, "got it\n");
1387     }
1388     return (rs);
1389 }
1390
1391 /*-
1392  *-----------------------------------------------------------------------
1393  * SuffFindCmds --
1394  *      See if any of the children of the target in the Src structure is
1395  *      one from which the target can be transformed. If there is one,
1396  *      a Src structure is put together for it and returned.
1397  *
1398  * Input:
1399  *      targ            Src structure to play with
1400  *
1401  * Results:
1402  *      The Src structure of the "winning" child, or NULL if no such beast.
1403  *
1404  * Side Effects:
1405  *      A Src structure may be allocated.
1406  *
1407  *-----------------------------------------------------------------------
1408  */
1409 static Src *
1410 SuffFindCmds(Src *targ, Lst slst)
1411 {
1412     LstNode             ln;     /* General-purpose list node */
1413     GNode               *t,     /* Target GNode */
1414                         *s;     /* Source GNode */
1415     int                 prefLen;/* The length of the defined prefix */
1416     Suff                *suff;  /* Suffix on matching beastie */
1417     Src                 *ret;   /* Return value */
1418     char                *cp;
1419
1420     t = targ->node;
1421     (void)Lst_Open(t->children);
1422     prefLen = strlen(targ->pref);
1423
1424     for (;;) {
1425         ln = Lst_Next(t->children);
1426         if (ln == NULL) {
1427             Lst_Close(t->children);
1428             return NULL;
1429         }
1430         s = (GNode *)Lst_Datum(ln);
1431
1432         if (s->type & OP_OPTIONAL && Lst_IsEmpty(t->commands)) {
1433             /*
1434              * We haven't looked to see if .OPTIONAL files exist yet, so
1435              * don't use one as the implicit source.
1436              * This allows us to use .OPTIONAL in .depend files so make won't
1437              * complain "don't know how to make xxx.h' when a dependent file
1438              * has been moved/deleted.
1439              */
1440             continue;
1441         }
1442
1443         cp = strrchr(s->name, '/');
1444         if (cp == NULL) {
1445             cp = s->name;
1446         } else {
1447             cp++;
1448         }
1449         if (strncmp(cp, targ->pref, prefLen) != 0)
1450             continue;
1451         /*
1452          * The node matches the prefix ok, see if it has a known
1453          * suffix.
1454          */
1455         ln = Lst_Find(sufflist, &cp[prefLen], SuffSuffHasNameP);
1456         if (ln == NULL)
1457             continue;
1458         /*
1459          * It even has a known suffix, see if there's a transformation
1460          * defined between the node's suffix and the target's suffix.
1461          *
1462          * XXX: Handle multi-stage transformations here, too.
1463          */
1464         suff = (Suff *)Lst_Datum(ln);
1465
1466         if (Lst_Member(suff->parents, targ->suff) != NULL)
1467             break;
1468     }
1469
1470     /*
1471      * Hot Damn! Create a new Src structure to describe
1472      * this transformation (making sure to duplicate the
1473      * source node's name so Suff_FindDeps can free it
1474      * again (ick)), and return the new structure.
1475      */
1476     ret = bmake_malloc(sizeof(Src));
1477     ret->file = bmake_strdup(s->name);
1478     ret->pref = targ->pref;
1479     ret->suff = suff;
1480     suff->refCount++;
1481     ret->parent = targ;
1482     ret->node = s;
1483     ret->children = 0;
1484     targ->children += 1;
1485 #ifdef DEBUG_SRC
1486     ret->cp = Lst_Init(FALSE);
1487     fprintf(debug_file, "3 add %x %x\n", targ, ret);
1488     Lst_AtEnd(targ->cp, ret);
1489 #endif
1490     Lst_AtEnd(slst, ret);
1491     if (DEBUG(SUFF)) {
1492         fprintf(debug_file, "\tusing existing source %s\n", s->name);
1493     }
1494     return (ret);
1495 }
1496
1497 /*-
1498  *-----------------------------------------------------------------------
1499  * SuffExpandChildren --
1500  *      Expand the names of any children of a given node that contain
1501  *      variable invocations or file wildcards into actual targets.
1502  *
1503  * Input:
1504  *      cln             Child to examine
1505  *      pgn             Parent node being processed
1506  *
1507  * Results:
1508  *      === 0 (continue)
1509  *
1510  * Side Effects:
1511  *      The expanded node is removed from the parent's list of children,
1512  *      and the parent's unmade counter is decremented, but other nodes
1513  *      may be added.
1514  *
1515  *-----------------------------------------------------------------------
1516  */
1517 static void
1518 SuffExpandChildren(LstNode cln, GNode *pgn)
1519 {
1520     GNode       *cgn = (GNode *)Lst_Datum(cln);
1521     GNode       *gn;        /* New source 8) */
1522     char        *cp;        /* Expanded value */
1523
1524     if (!Lst_IsEmpty(cgn->order_pred) || !Lst_IsEmpty(cgn->order_succ))
1525         /* It is all too hard to process the result of .ORDER */
1526         return;
1527
1528     if (cgn->type & OP_WAIT)
1529         /* Ignore these (& OP_PHONY ?) */
1530         return;
1531
1532     /*
1533      * First do variable expansion -- this takes precedence over
1534      * wildcard expansion. If the result contains wildcards, they'll be gotten
1535      * to later since the resulting words are tacked on to the end of
1536      * the children list.
1537      */
1538     if (strchr(cgn->name, '$') == NULL) {
1539         SuffExpandWildcards(cln, pgn);
1540         return;
1541     }
1542
1543     if (DEBUG(SUFF)) {
1544         fprintf(debug_file, "Expanding \"%s\"...", cgn->name);
1545     }
1546     cp = Var_Subst(NULL, cgn->name, pgn, TRUE);
1547
1548     if (cp != NULL) {
1549         Lst         members = Lst_Init(FALSE);
1550
1551         if (cgn->type & OP_ARCHV) {
1552             /*
1553              * Node was an archive(member) target, so we want to call
1554              * on the Arch module to find the nodes for us, expanding
1555              * variables in the parent's context.
1556              */
1557             char        *sacrifice = cp;
1558
1559             (void)Arch_ParseArchive(&sacrifice, members, pgn);
1560         } else {
1561             /*
1562              * Break the result into a vector of strings whose nodes
1563              * we can find, then add those nodes to the members list.
1564              * Unfortunately, we can't use brk_string b/c it
1565              * doesn't understand about variable specifications with
1566              * spaces in them...
1567              */
1568             char            *start;
1569             char            *initcp = cp;   /* For freeing... */
1570
1571             for (start = cp; *start == ' ' || *start == '\t'; start++)
1572                 continue;
1573             for (cp = start; *cp != '\0'; cp++) {
1574                 if (*cp == ' ' || *cp == '\t') {
1575                     /*
1576                      * White-space -- terminate element, find the node,
1577                      * add it, skip any further spaces.
1578                      */
1579                     *cp++ = '\0';
1580                     gn = Targ_FindNode(start, TARG_CREATE);
1581                     (void)Lst_AtEnd(members, gn);
1582                     while (*cp == ' ' || *cp == '\t') {
1583                         cp++;
1584                     }
1585                     /*
1586                      * Adjust cp for increment at start of loop, but
1587                      * set start to first non-space.
1588                      */
1589                     start = cp--;
1590                 } else if (*cp == '$') {
1591                     /*
1592                      * Start of a variable spec -- contact variable module
1593                      * to find the end so we can skip over it.
1594                      */
1595                     char        *junk;
1596                     int         len;
1597                     void        *freeIt;
1598
1599                     junk = Var_Parse(cp, pgn, TRUE, &len, &freeIt);
1600                     if (junk != var_Error) {
1601                         cp += len - 1;
1602                     }
1603
1604                     if (freeIt)
1605                         free(freeIt);
1606                 } else if (*cp == '\\' && *cp != '\0') {
1607                     /*
1608                      * Escaped something -- skip over it
1609                      */
1610                     cp++;
1611                 }
1612             }
1613
1614             if (cp != start) {
1615                 /*
1616                  * Stuff left over -- add it to the list too
1617                  */
1618                 gn = Targ_FindNode(start, TARG_CREATE);
1619                 (void)Lst_AtEnd(members, gn);
1620             }
1621             /*
1622              * Point cp back at the beginning again so the variable value
1623              * can be freed.
1624              */
1625             cp = initcp;
1626         }
1627
1628         /*
1629          * Add all elements of the members list to the parent node.
1630          */
1631         while(!Lst_IsEmpty(members)) {
1632             gn = (GNode *)Lst_DeQueue(members);
1633
1634             if (DEBUG(SUFF)) {
1635                 fprintf(debug_file, "%s...", gn->name);
1636             }
1637             /* Add gn to the parents child list before the original child */
1638             (void)Lst_InsertBefore(pgn->children, cln, gn);
1639             (void)Lst_AtEnd(gn->parents, pgn);
1640             pgn->unmade++;
1641             /* Expand wildcards on new node */
1642             SuffExpandWildcards(Lst_Prev(cln), pgn);
1643         }
1644         Lst_Destroy(members, NULL);
1645
1646         /*
1647          * Free the result
1648          */
1649         free(cp);
1650     }
1651     if (DEBUG(SUFF)) {
1652         fprintf(debug_file, "\n");
1653     }
1654
1655     /*
1656      * Now the source is expanded, remove it from the list of children to
1657      * keep it from being processed.
1658      */
1659     pgn->unmade--;
1660     Lst_Remove(pgn->children, cln);
1661     Lst_Remove(cgn->parents, Lst_Member(cgn->parents, pgn));
1662 }
1663
1664 static void
1665 SuffExpandWildcards(LstNode cln, GNode *pgn)
1666 {
1667     GNode       *cgn = (GNode *)Lst_Datum(cln);
1668     GNode       *gn;        /* New source 8) */
1669     char        *cp;        /* Expanded value */
1670     Lst         explist;    /* List of expansions */
1671
1672     if (!Dir_HasWildcards(cgn->name))
1673         return;
1674
1675     /*
1676      * Expand the word along the chosen path
1677      */
1678     explist = Lst_Init(FALSE);
1679     Dir_Expand(cgn->name, Suff_FindPath(cgn), explist);
1680
1681     while (!Lst_IsEmpty(explist)) {
1682         /*
1683          * Fetch next expansion off the list and find its GNode
1684          */
1685         cp = (char *)Lst_DeQueue(explist);
1686
1687         if (DEBUG(SUFF)) {
1688             fprintf(debug_file, "%s...", cp);
1689         }
1690         gn = Targ_FindNode(cp, TARG_CREATE);
1691
1692         /* Add gn to the parents child list before the original child */
1693         (void)Lst_InsertBefore(pgn->children, cln, gn);
1694         (void)Lst_AtEnd(gn->parents, pgn);
1695         pgn->unmade++;
1696     }
1697
1698     /*
1699      * Nuke what's left of the list
1700      */
1701     Lst_Destroy(explist, NULL);
1702
1703     if (DEBUG(SUFF)) {
1704         fprintf(debug_file, "\n");
1705     }
1706
1707     /*
1708      * Now the source is expanded, remove it from the list of children to
1709      * keep it from being processed.
1710      */
1711     pgn->unmade--;
1712     Lst_Remove(pgn->children, cln);
1713     Lst_Remove(cgn->parents, Lst_Member(cgn->parents, pgn));
1714 }
1715
1716 /*-
1717  *-----------------------------------------------------------------------
1718  * Suff_FindPath --
1719  *      Find a path along which to expand the node.
1720  *
1721  *      If the word has a known suffix, use that path.
1722  *      If it has no known suffix, use the default system search path.
1723  *
1724  * Input:
1725  *      gn              Node being examined
1726  *
1727  * Results:
1728  *      The appropriate path to search for the GNode.
1729  *
1730  * Side Effects:
1731  *      XXX: We could set the suffix here so that we don't have to scan
1732  *      again.
1733  *
1734  *-----------------------------------------------------------------------
1735  */
1736 Lst
1737 Suff_FindPath(GNode* gn)
1738 {
1739     Suff *suff = gn->suffix;
1740
1741     if (suff == NULL) {
1742         SuffixCmpData sd;   /* Search string data */
1743         LstNode ln;
1744         sd.len = strlen(gn->name);
1745         sd.ename = gn->name + sd.len;
1746         ln = Lst_Find(sufflist, &sd, SuffSuffIsSuffixP);
1747
1748         if (DEBUG(SUFF)) {
1749             fprintf(debug_file, "Wildcard expanding \"%s\"...", gn->name);
1750         }
1751         if (ln != NULL)
1752             suff = (Suff *)Lst_Datum(ln);
1753         /* XXX: Here we can save the suffix so we don't have to do this again */
1754     }
1755
1756     if (suff != NULL) {
1757         if (DEBUG(SUFF)) {
1758             fprintf(debug_file, "suffix is \"%s\"...", suff->name);
1759         }
1760         return suff->searchPath;
1761     } else {
1762         /*
1763          * Use default search path
1764          */
1765         return dirSearchPath;
1766     }
1767 }
1768
1769 /*-
1770  *-----------------------------------------------------------------------
1771  * SuffApplyTransform --
1772  *      Apply a transformation rule, given the source and target nodes
1773  *      and suffixes.
1774  *
1775  * Input:
1776  *      tGn             Target node
1777  *      sGn             Source node
1778  *      t               Target suffix
1779  *      s               Source suffix
1780  *
1781  * Results:
1782  *      TRUE if successful, FALSE if not.
1783  *
1784  * Side Effects:
1785  *      The source and target are linked and the commands from the
1786  *      transformation are added to the target node's commands list.
1787  *      All attributes but OP_DEPMASK and OP_TRANSFORM are applied
1788  *      to the target. The target also inherits all the sources for
1789  *      the transformation rule.
1790  *
1791  *-----------------------------------------------------------------------
1792  */
1793 static Boolean
1794 SuffApplyTransform(GNode *tGn, GNode *sGn, Suff *t, Suff *s)
1795 {
1796     LstNode     ln, nln;    /* General node */
1797     char        *tname;     /* Name of transformation rule */
1798     GNode       *gn;        /* Node for same */
1799
1800     /*
1801      * Form the proper links between the target and source.
1802      */
1803     (void)Lst_AtEnd(tGn->children, sGn);
1804     (void)Lst_AtEnd(sGn->parents, tGn);
1805     tGn->unmade += 1;
1806
1807     /*
1808      * Locate the transformation rule itself
1809      */
1810     tname = str_concat(s->name, t->name, 0);
1811     ln = Lst_Find(transforms, tname, SuffGNHasNameP);
1812     free(tname);
1813
1814     if (ln == NULL) {
1815         /*
1816          * Not really such a transformation rule (can happen when we're
1817          * called to link an OP_MEMBER and OP_ARCHV node), so return
1818          * FALSE.
1819          */
1820         return(FALSE);
1821     }
1822
1823     gn = (GNode *)Lst_Datum(ln);
1824
1825     if (DEBUG(SUFF)) {
1826         fprintf(debug_file, "\tapplying %s -> %s to \"%s\"\n", s->name, t->name, tGn->name);
1827     }
1828
1829     /*
1830      * Record last child for expansion purposes
1831      */
1832     ln = Lst_Last(tGn->children);
1833
1834     /*
1835      * Pass the buck to Make_HandleUse to apply the rule
1836      */
1837     (void)Make_HandleUse(gn, tGn);
1838
1839     /*
1840      * Deal with wildcards and variables in any acquired sources
1841      */
1842     for (ln = Lst_Succ(ln); ln != NULL; ln = nln) {
1843         nln = Lst_Succ(ln);
1844         SuffExpandChildren(ln, tGn);
1845     }
1846
1847     /*
1848      * Keep track of another parent to which this beast is transformed so
1849      * the .IMPSRC variable can be set correctly for the parent.
1850      */
1851     (void)Lst_AtEnd(sGn->iParents, tGn);
1852
1853     return(TRUE);
1854 }
1855
1856
1857 /*-
1858  *-----------------------------------------------------------------------
1859  * SuffFindArchiveDeps --
1860  *      Locate dependencies for an OP_ARCHV node.
1861  *
1862  * Input:
1863  *      gn              Node for which to locate dependencies
1864  *
1865  * Results:
1866  *      None
1867  *
1868  * Side Effects:
1869  *      Same as Suff_FindDeps
1870  *
1871  *-----------------------------------------------------------------------
1872  */
1873 static void
1874 SuffFindArchiveDeps(GNode *gn, Lst slst)
1875 {
1876     char        *eoarch;    /* End of archive portion */
1877     char        *eoname;    /* End of member portion */
1878     GNode       *mem;       /* Node for member */
1879     static const char   *copy[] = {
1880         /* Variables to be copied from the member node */
1881         TARGET,             /* Must be first */
1882         PREFIX,             /* Must be second */
1883     };
1884     int         i;          /* Index into copy and vals */
1885     Suff        *ms;        /* Suffix descriptor for member */
1886     char        *name;      /* Start of member's name */
1887
1888     /*
1889      * The node is an archive(member) pair. so we must find a
1890      * suffix for both of them.
1891      */
1892     eoarch = strchr(gn->name, '(');
1893     eoname = strchr(eoarch, ')');
1894
1895     *eoname = '\0';       /* Nuke parentheses during suffix search */
1896     *eoarch = '\0';       /* So a suffix can be found */
1897
1898     name = eoarch + 1;
1899
1900     /*
1901      * To simplify things, call Suff_FindDeps recursively on the member now,
1902      * so we can simply compare the member's .PREFIX and .TARGET variables
1903      * to locate its suffix. This allows us to figure out the suffix to
1904      * use for the archive without having to do a quadratic search over the
1905      * suffix list, backtracking for each one...
1906      */
1907     mem = Targ_FindNode(name, TARG_CREATE);
1908     SuffFindDeps(mem, slst);
1909
1910     /*
1911      * Create the link between the two nodes right off
1912      */
1913     (void)Lst_AtEnd(gn->children, mem);
1914     (void)Lst_AtEnd(mem->parents, gn);
1915     gn->unmade += 1;
1916
1917     /*
1918      * Copy in the variables from the member node to this one.
1919      */
1920     for (i = (sizeof(copy)/sizeof(copy[0]))-1; i >= 0; i--) {
1921         char *p1;
1922         Var_Set(copy[i], Var_Value(copy[i], mem, &p1), gn, 0);
1923         if (p1)
1924             free(p1);
1925
1926     }
1927
1928     ms = mem->suffix;
1929     if (ms == NULL) {
1930         /*
1931          * Didn't know what it was -- use .NULL suffix if not in make mode
1932          */
1933         if (DEBUG(SUFF)) {
1934             fprintf(debug_file, "using null suffix\n");
1935         }
1936         ms = suffNull;
1937     }
1938
1939
1940     /*
1941      * Set the other two local variables required for this target.
1942      */
1943     Var_Set(MEMBER, name, gn, 0);
1944     Var_Set(ARCHIVE, gn->name, gn, 0);
1945
1946     if (ms != NULL) {
1947         /*
1948          * Member has a known suffix, so look for a transformation rule from
1949          * it to a possible suffix of the archive. Rather than searching
1950          * through the entire list, we just look at suffixes to which the
1951          * member's suffix may be transformed...
1952          */
1953         LstNode         ln;
1954         SuffixCmpData   sd;             /* Search string data */
1955
1956         /*
1957          * Use first matching suffix...
1958          */
1959         sd.len = eoarch - gn->name;
1960         sd.ename = eoarch;
1961         ln = Lst_Find(ms->parents, &sd, SuffSuffIsSuffixP);
1962
1963         if (ln != NULL) {
1964             /*
1965              * Got one -- apply it
1966              */
1967             if (!SuffApplyTransform(gn, mem, (Suff *)Lst_Datum(ln), ms) &&
1968                 DEBUG(SUFF))
1969             {
1970                 fprintf(debug_file, "\tNo transformation from %s -> %s\n",
1971                        ms->name, ((Suff *)Lst_Datum(ln))->name);
1972             }
1973         }
1974     }
1975
1976     /*
1977      * Replace the opening and closing parens now we've no need of the separate
1978      * pieces.
1979      */
1980     *eoarch = '('; *eoname = ')';
1981
1982     /*
1983      * Pretend gn appeared to the left of a dependency operator so
1984      * the user needn't provide a transformation from the member to the
1985      * archive.
1986      */
1987     if (OP_NOP(gn->type)) {
1988         gn->type |= OP_DEPENDS;
1989     }
1990
1991     /*
1992      * Flag the member as such so we remember to look in the archive for
1993      * its modification time.
1994      */
1995     mem->type |= OP_MEMBER;
1996 }
1997
1998 /*-
1999  *-----------------------------------------------------------------------
2000  * SuffFindNormalDeps --
2001  *      Locate implicit dependencies for regular targets.
2002  *
2003  * Input:
2004  *      gn              Node for which to find sources
2005  *
2006  * Results:
2007  *      None.
2008  *
2009  * Side Effects:
2010  *      Same as Suff_FindDeps...
2011  *
2012  *-----------------------------------------------------------------------
2013  */
2014 static void
2015 SuffFindNormalDeps(GNode *gn, Lst slst)
2016 {
2017     char        *eoname;    /* End of name */
2018     char        *sopref;    /* Start of prefix */
2019     LstNode     ln, nln;    /* Next suffix node to check */
2020     Lst         srcs;       /* List of sources at which to look */
2021     Lst         targs;      /* List of targets to which things can be
2022                              * transformed. They all have the same file,
2023                              * but different suff and pref fields */
2024     Src         *bottom;    /* Start of found transformation path */
2025     Src         *src;       /* General Src pointer */
2026     char        *pref;      /* Prefix to use */
2027     Src         *targ;      /* General Src target pointer */
2028     SuffixCmpData sd;       /* Search string data */
2029
2030
2031     sd.len = strlen(gn->name);
2032     sd.ename = eoname = gn->name + sd.len;
2033
2034     sopref = gn->name;
2035
2036     /*
2037      * Begin at the beginning...
2038      */
2039     ln = Lst_First(sufflist);
2040     srcs = Lst_Init(FALSE);
2041     targs = Lst_Init(FALSE);
2042
2043     /*
2044      * We're caught in a catch-22 here. On the one hand, we want to use any
2045      * transformation implied by the target's sources, but we can't examine
2046      * the sources until we've expanded any variables/wildcards they may hold,
2047      * and we can't do that until we've set up the target's local variables
2048      * and we can't do that until we know what the proper suffix for the
2049      * target is (in case there are two suffixes one of which is a suffix of
2050      * the other) and we can't know that until we've found its implied
2051      * source, which we may not want to use if there's an existing source
2052      * that implies a different transformation.
2053      *
2054      * In an attempt to get around this, which may not work all the time,
2055      * but should work most of the time, we look for implied sources first,
2056      * checking transformations to all possible suffixes of the target,
2057      * use what we find to set the target's local variables, expand the
2058      * children, then look for any overriding transformations they imply.
2059      * Should we find one, we discard the one we found before.
2060      */
2061
2062     while (ln != NULL) {
2063         /*
2064          * Look for next possible suffix...
2065          */
2066         ln = Lst_FindFrom(sufflist, ln, &sd, SuffSuffIsSuffixP);
2067
2068         if (ln != NULL) {
2069             int     prefLen;        /* Length of the prefix */
2070
2071             /*
2072              * Allocate a Src structure to which things can be transformed
2073              */
2074             targ = bmake_malloc(sizeof(Src));
2075             targ->file = bmake_strdup(gn->name);
2076             targ->suff = (Suff *)Lst_Datum(ln);
2077             targ->suff->refCount++;
2078             targ->node = gn;
2079             targ->parent = NULL;
2080             targ->children = 0;
2081 #ifdef DEBUG_SRC
2082             targ->cp = Lst_Init(FALSE);
2083 #endif
2084
2085             /*
2086              * Allocate room for the prefix, whose end is found by subtracting
2087              * the length of the suffix from the end of the name.
2088              */
2089             prefLen = (eoname - targ->suff->nameLen) - sopref;
2090             targ->pref = bmake_malloc(prefLen + 1);
2091             memcpy(targ->pref, sopref, prefLen);
2092             targ->pref[prefLen] = '\0';
2093
2094             /*
2095              * Add nodes from which the target can be made
2096              */
2097             SuffAddLevel(srcs, targ);
2098
2099             /*
2100              * Record the target so we can nuke it
2101              */
2102             (void)Lst_AtEnd(targs, targ);
2103
2104             /*
2105              * Search from this suffix's successor...
2106              */
2107             ln = Lst_Succ(ln);
2108         }
2109     }
2110
2111     /*
2112      * Handle target of unknown suffix...
2113      */
2114     if (Lst_IsEmpty(targs) && suffNull != NULL) {
2115         if (DEBUG(SUFF)) {
2116             fprintf(debug_file, "\tNo known suffix on %s. Using .NULL suffix\n", gn->name);
2117         }
2118
2119         targ = bmake_malloc(sizeof(Src));
2120         targ->file = bmake_strdup(gn->name);
2121         targ->suff = suffNull;
2122         targ->suff->refCount++;
2123         targ->node = gn;
2124         targ->parent = NULL;
2125         targ->children = 0;
2126         targ->pref = bmake_strdup(sopref);
2127 #ifdef DEBUG_SRC
2128         targ->cp = Lst_Init(FALSE);
2129 #endif
2130
2131         /*
2132          * Only use the default suffix rules if we don't have commands
2133          * defined for this gnode; traditional make programs used to
2134          * not define suffix rules if the gnode had children but we
2135          * don't do this anymore.
2136          */
2137         if (Lst_IsEmpty(gn->commands))
2138             SuffAddLevel(srcs, targ);
2139         else {
2140             if (DEBUG(SUFF))
2141                 fprintf(debug_file, "not ");
2142         }
2143
2144         if (DEBUG(SUFF))
2145             fprintf(debug_file, "adding suffix rules\n");
2146
2147         (void)Lst_AtEnd(targs, targ);
2148     }
2149
2150     /*
2151      * Using the list of possible sources built up from the target suffix(es),
2152      * try and find an existing file/target that matches.
2153      */
2154     bottom = SuffFindThem(srcs, slst);
2155
2156     if (bottom == NULL) {
2157         /*
2158          * No known transformations -- use the first suffix found for setting
2159          * the local variables.
2160          */
2161         if (!Lst_IsEmpty(targs)) {
2162             targ = (Src *)Lst_Datum(Lst_First(targs));
2163         } else {
2164             targ = NULL;
2165         }
2166     } else {
2167         /*
2168          * Work up the transformation path to find the suffix of the
2169          * target to which the transformation was made.
2170          */
2171         for (targ = bottom; targ->parent != NULL; targ = targ->parent)
2172             continue;
2173     }
2174
2175     Var_Set(TARGET, gn->path ? gn->path : gn->name, gn, 0);
2176
2177     pref = (targ != NULL) ? targ->pref : gn->name;
2178     Var_Set(PREFIX, pref, gn, 0);
2179
2180     /*
2181      * Now we've got the important local variables set, expand any sources
2182      * that still contain variables or wildcards in their names.
2183      */
2184     for (ln = Lst_First(gn->children); ln != NULL; ln = nln) {
2185         nln = Lst_Succ(ln);
2186         SuffExpandChildren(ln, gn);
2187     }
2188
2189     if (targ == NULL) {
2190         if (DEBUG(SUFF)) {
2191             fprintf(debug_file, "\tNo valid suffix on %s\n", gn->name);
2192         }
2193
2194 sfnd_abort:
2195         /*
2196          * Deal with finding the thing on the default search path. We
2197          * always do that, not only if the node is only a source (not
2198          * on the lhs of a dependency operator or [XXX] it has neither
2199          * children or commands) as the old pmake did.
2200          */
2201         if ((gn->type & (OP_PHONY|OP_NOPATH)) == 0) {
2202             free(gn->path);
2203             gn->path = Dir_FindFile(gn->name,
2204                                     (targ == NULL ? dirSearchPath :
2205                                      targ->suff->searchPath));
2206             if (gn->path != NULL) {
2207                 char *ptr;
2208                 Var_Set(TARGET, gn->path, gn, 0);
2209
2210                 if (targ != NULL) {
2211                     /*
2212                      * Suffix known for the thing -- trim the suffix off
2213                      * the path to form the proper .PREFIX variable.
2214                      */
2215                     int     savep = strlen(gn->path) - targ->suff->nameLen;
2216                     char    savec;
2217
2218                     if (gn->suffix)
2219                         gn->suffix->refCount--;
2220                     gn->suffix = targ->suff;
2221                     gn->suffix->refCount++;
2222
2223                     savec = gn->path[savep];
2224                     gn->path[savep] = '\0';
2225
2226                     if ((ptr = strrchr(gn->path, '/')) != NULL)
2227                         ptr++;
2228                     else
2229                         ptr = gn->path;
2230
2231                     Var_Set(PREFIX, ptr, gn, 0);
2232
2233                     gn->path[savep] = savec;
2234                 } else {
2235                     /*
2236                      * The .PREFIX gets the full path if the target has
2237                      * no known suffix.
2238                      */
2239                     if (gn->suffix)
2240                         gn->suffix->refCount--;
2241                     gn->suffix = NULL;
2242
2243                     if ((ptr = strrchr(gn->path, '/')) != NULL)
2244                         ptr++;
2245                     else
2246                         ptr = gn->path;
2247
2248                     Var_Set(PREFIX, ptr, gn, 0);
2249                 }
2250             }
2251         }
2252
2253         goto sfnd_return;
2254     }
2255
2256     /*
2257      * If the suffix indicates that the target is a library, mark that in
2258      * the node's type field.
2259      */
2260     if (targ->suff->flags & SUFF_LIBRARY) {
2261         gn->type |= OP_LIB;
2262     }
2263
2264     /*
2265      * Check for overriding transformation rule implied by sources
2266      */
2267     if (!Lst_IsEmpty(gn->children)) {
2268         src = SuffFindCmds(targ, slst);
2269
2270         if (src != NULL) {
2271             /*
2272              * Free up all the Src structures in the transformation path
2273              * up to, but not including, the parent node.
2274              */
2275             while (bottom && bottom->parent != NULL) {
2276                 if (Lst_Member(slst, bottom) == NULL) {
2277                     Lst_AtEnd(slst, bottom);
2278                 }
2279                 bottom = bottom->parent;
2280             }
2281             bottom = src;
2282         }
2283     }
2284
2285     if (bottom == NULL) {
2286         /*
2287          * No idea from where it can come -- return now.
2288          */
2289         goto sfnd_abort;
2290     }
2291
2292     /*
2293      * We now have a list of Src structures headed by 'bottom' and linked via
2294      * their 'parent' pointers. What we do next is create links between
2295      * source and target nodes (which may or may not have been created)
2296      * and set the necessary local variables in each target. The
2297      * commands for each target are set from the commands of the
2298      * transformation rule used to get from the src suffix to the targ
2299      * suffix. Note that this causes the commands list of the original
2300      * node, gn, to be replaced by the commands of the final
2301      * transformation rule. Also, the unmade field of gn is incremented.
2302      * Etc.
2303      */
2304     if (bottom->node == NULL) {
2305         bottom->node = Targ_FindNode(bottom->file, TARG_CREATE);
2306     }
2307
2308     for (src = bottom; src->parent != NULL; src = src->parent) {
2309         targ = src->parent;
2310
2311         if (src->node->suffix)
2312             src->node->suffix->refCount--;
2313         src->node->suffix = src->suff;
2314         src->node->suffix->refCount++;
2315
2316         if (targ->node == NULL) {
2317             targ->node = Targ_FindNode(targ->file, TARG_CREATE);
2318         }
2319
2320         SuffApplyTransform(targ->node, src->node,
2321                            targ->suff, src->suff);
2322
2323         if (targ->node != gn) {
2324             /*
2325              * Finish off the dependency-search process for any nodes
2326              * between bottom and gn (no point in questing around the
2327              * filesystem for their implicit source when it's already
2328              * known). Note that the node can't have any sources that
2329              * need expanding, since SuffFindThem will stop on an existing
2330              * node, so all we need to do is set the standard and System V
2331              * variables.
2332              */
2333             targ->node->type |= OP_DEPS_FOUND;
2334
2335             Var_Set(PREFIX, targ->pref, targ->node, 0);
2336
2337             Var_Set(TARGET, targ->node->name, targ->node, 0);
2338         }
2339     }
2340
2341     if (gn->suffix)
2342         gn->suffix->refCount--;
2343     gn->suffix = src->suff;
2344     gn->suffix->refCount++;
2345
2346     /*
2347      * Nuke the transformation path and the Src structures left over in the
2348      * two lists.
2349      */
2350 sfnd_return:
2351     if (bottom)
2352         if (Lst_Member(slst, bottom) == NULL)
2353             Lst_AtEnd(slst, bottom);
2354
2355     while (SuffRemoveSrc(srcs) || SuffRemoveSrc(targs))
2356         continue;
2357
2358     Lst_Concat(slst, srcs, LST_CONCLINK);
2359     Lst_Concat(slst, targs, LST_CONCLINK);
2360 }
2361
2362
2363 /*-
2364  *-----------------------------------------------------------------------
2365  * Suff_FindDeps  --
2366  *      Find implicit sources for the target described by the graph node
2367  *      gn
2368  *
2369  * Results:
2370  *      Nothing.
2371  *
2372  * Side Effects:
2373  *      Nodes are added to the graph below the passed-in node. The nodes
2374  *      are marked to have their IMPSRC variable filled in. The
2375  *      PREFIX variable is set for the given node and all its
2376  *      implied children.
2377  *
2378  * Notes:
2379  *      The path found by this target is the shortest path in the
2380  *      transformation graph, which may pass through non-existent targets,
2381  *      to an existing target. The search continues on all paths from the
2382  *      root suffix until a file is found. I.e. if there's a path
2383  *      .o -> .c -> .l -> .l,v from the root and the .l,v file exists but
2384  *      the .c and .l files don't, the search will branch out in
2385  *      all directions from .o and again from all the nodes on the
2386  *      next level until the .l,v node is encountered.
2387  *
2388  *-----------------------------------------------------------------------
2389  */
2390
2391 void
2392 Suff_FindDeps(GNode *gn)
2393 {
2394
2395     SuffFindDeps(gn, srclist);
2396     while (SuffRemoveSrc(srclist))
2397         continue;
2398 }
2399
2400
2401 /*
2402  * Input:
2403  *      gn              node we're dealing with
2404  *
2405  */
2406 static void
2407 SuffFindDeps(GNode *gn, Lst slst)
2408 {
2409     if (gn->type & OP_DEPS_FOUND) {
2410         /*
2411          * If dependencies already found, no need to do it again...
2412          */
2413         return;
2414     } else {
2415         gn->type |= OP_DEPS_FOUND;
2416     }
2417     /*
2418      * Make sure we have these set, may get revised below.
2419      */
2420     Var_Set(TARGET, gn->path ? gn->path : gn->name, gn, 0);
2421     Var_Set(PREFIX, gn->name, gn, 0);
2422     if (gn->type & OP_PHONY) {
2423         /*
2424          * If this is a .PHONY target, we do not apply suffix rules.
2425          */
2426         return;
2427     }
2428     if (DEBUG(SUFF)) {
2429         fprintf(debug_file, "SuffFindDeps (%s)\n", gn->name);
2430     }
2431
2432     if (gn->type & OP_ARCHV) {
2433         SuffFindArchiveDeps(gn, slst);
2434     } else if (gn->type & OP_LIB) {
2435         /*
2436          * If the node is a library, it is the arch module's job to find it
2437          * and set the TARGET variable accordingly. We merely provide the
2438          * search path, assuming all libraries end in ".a" (if the suffix
2439          * hasn't been defined, there's nothing we can do for it, so we just
2440          * set the TARGET variable to the node's name in order to give it a
2441          * value).
2442          */
2443         LstNode ln;
2444         Suff    *s;
2445
2446         ln = Lst_Find(sufflist, LIBSUFF, SuffSuffHasNameP);
2447         if (gn->suffix)
2448             gn->suffix->refCount--;
2449         if (ln != NULL) {
2450             gn->suffix = s = (Suff *)Lst_Datum(ln);
2451             gn->suffix->refCount++;
2452             Arch_FindLib(gn, s->searchPath);
2453         } else {
2454             gn->suffix = NULL;
2455             Var_Set(TARGET, gn->name, gn, 0);
2456         }
2457         /*
2458          * Because a library (-lfoo) target doesn't follow the standard
2459          * filesystem conventions, we don't set the regular variables for
2460          * the thing. .PREFIX is simply made empty...
2461          */
2462         Var_Set(PREFIX, "", gn, 0);
2463     } else {
2464         SuffFindNormalDeps(gn, slst);
2465     }
2466 }
2467
2468 /*-
2469  *-----------------------------------------------------------------------
2470  * Suff_SetNull --
2471  *      Define which suffix is the null suffix.
2472  *
2473  * Input:
2474  *      name            Name of null suffix
2475  *
2476  * Results:
2477  *      None.
2478  *
2479  * Side Effects:
2480  *      'suffNull' is altered.
2481  *
2482  * Notes:
2483  *      Need to handle the changing of the null suffix gracefully so the
2484  *      old transformation rules don't just go away.
2485  *
2486  *-----------------------------------------------------------------------
2487  */
2488 void
2489 Suff_SetNull(char *name)
2490 {
2491     Suff    *s;
2492     LstNode ln;
2493
2494     ln = Lst_Find(sufflist, name, SuffSuffHasNameP);
2495     if (ln != NULL) {
2496         s = (Suff *)Lst_Datum(ln);
2497         if (suffNull != NULL) {
2498             suffNull->flags &= ~SUFF_NULL;
2499         }
2500         s->flags |= SUFF_NULL;
2501         /*
2502          * XXX: Here's where the transformation mangling would take place
2503          */
2504         suffNull = s;
2505     } else {
2506         Parse_Error(PARSE_WARNING, "Desired null suffix %s not defined.",
2507                      name);
2508     }
2509 }
2510
2511 /*-
2512  *-----------------------------------------------------------------------
2513  * Suff_Init --
2514  *      Initialize suffixes module
2515  *
2516  * Results:
2517  *      None
2518  *
2519  * Side Effects:
2520  *      Many
2521  *-----------------------------------------------------------------------
2522  */
2523 void
2524 Suff_Init(void)
2525 {
2526     sufflist = Lst_Init(FALSE);
2527 #ifdef CLEANUP
2528     suffClean = Lst_Init(FALSE);
2529 #endif
2530     srclist = Lst_Init(FALSE);
2531     transforms = Lst_Init(FALSE);
2532
2533     sNum = 0;
2534     /*
2535      * Create null suffix for single-suffix rules (POSIX). The thing doesn't
2536      * actually go on the suffix list or everyone will think that's its
2537      * suffix.
2538      */
2539     emptySuff = suffNull = bmake_malloc(sizeof(Suff));
2540
2541     suffNull->name =        bmake_strdup("");
2542     suffNull->nameLen =     0;
2543     suffNull->searchPath =  Lst_Init(FALSE);
2544     Dir_Concat(suffNull->searchPath, dirSearchPath);
2545     suffNull->children =    Lst_Init(FALSE);
2546     suffNull->parents =     Lst_Init(FALSE);
2547     suffNull->ref =         Lst_Init(FALSE);
2548     suffNull->sNum =        sNum++;
2549     suffNull->flags =       SUFF_NULL;
2550     suffNull->refCount =    1;
2551
2552 }
2553
2554
2555 /*-
2556  *----------------------------------------------------------------------
2557  * Suff_End --
2558  *      Cleanup the this module
2559  *
2560  * Results:
2561  *      None
2562  *
2563  * Side Effects:
2564  *      The memory is free'd.
2565  *----------------------------------------------------------------------
2566  */
2567
2568 void
2569 Suff_End(void)
2570 {
2571 #ifdef CLEANUP
2572     Lst_Destroy(sufflist, SuffFree);
2573     Lst_Destroy(suffClean, SuffFree);
2574     if (suffNull)
2575         SuffFree(suffNull);
2576     Lst_Destroy(srclist, NULL);
2577     Lst_Destroy(transforms, NULL);
2578 #endif
2579 }
2580
2581
2582 /********************* DEBUGGING FUNCTIONS **********************/
2583
2584 static int SuffPrintName(void *s, void *dummy)
2585 {
2586     fprintf(debug_file, "%s ", ((Suff *)s)->name);
2587     return (dummy ? 0 : 0);
2588 }
2589
2590 static int
2591 SuffPrintSuff(void *sp, void *dummy)
2592 {
2593     Suff    *s = (Suff *)sp;
2594     int     flags;
2595     int     flag;
2596
2597     fprintf(debug_file, "# `%s' [%d] ", s->name, s->refCount);
2598
2599     flags = s->flags;
2600     if (flags) {
2601         fputs(" (", debug_file);
2602         while (flags) {
2603             flag = 1 << (ffs(flags) - 1);
2604             flags &= ~flag;
2605             switch (flag) {
2606                 case SUFF_NULL:
2607                     fprintf(debug_file, "NULL");
2608                     break;
2609                 case SUFF_INCLUDE:
2610                     fprintf(debug_file, "INCLUDE");
2611                     break;
2612                 case SUFF_LIBRARY:
2613                     fprintf(debug_file, "LIBRARY");
2614                     break;
2615             }
2616             fputc(flags ? '|' : ')', debug_file);
2617         }
2618     }
2619     fputc('\n', debug_file);
2620     fprintf(debug_file, "#\tTo: ");
2621     Lst_ForEach(s->parents, SuffPrintName, NULL);
2622     fputc('\n', debug_file);
2623     fprintf(debug_file, "#\tFrom: ");
2624     Lst_ForEach(s->children, SuffPrintName, NULL);
2625     fputc('\n', debug_file);
2626     fprintf(debug_file, "#\tSearch Path: ");
2627     Dir_PrintPath(s->searchPath);
2628     fputc('\n', debug_file);
2629     return (dummy ? 0 : 0);
2630 }
2631
2632 static int
2633 SuffPrintTrans(void *tp, void *dummy)
2634 {
2635     GNode   *t = (GNode *)tp;
2636
2637     fprintf(debug_file, "%-16s: ", t->name);
2638     Targ_PrintType(t->type);
2639     fputc('\n', debug_file);
2640     Lst_ForEach(t->commands, Targ_PrintCmd, NULL);
2641     fputc('\n', debug_file);
2642     return(dummy ? 0 : 0);
2643 }
2644
2645 void
2646 Suff_PrintAll(void)
2647 {
2648     fprintf(debug_file, "#*** Suffixes:\n");
2649     Lst_ForEach(sufflist, SuffPrintSuff, NULL);
2650
2651     fprintf(debug_file, "#*** Transformations:\n");
2652     Lst_ForEach(transforms, SuffPrintTrans, NULL);
2653 }