contrib/bmake/suff.c

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