contrib/bmake/suff.c

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