contrib/bmake/suff.c

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