/*      $OpenBSD: suff.c,v 1.103 2023/09/04 11:35:11 espie Exp $ */
/*      $NetBSD: suff.c,v 1.13 1996/11/06 17:59:25 christos Exp $       */

/*
 * Copyright (c) 1988, 1989, 1990, 1993
 *      The Regents of the University of California.  All rights reserved.
 * Copyright (c) 1989 by Berkeley Softworks
 * All rights reserved.
 *
 * This code is derived from software contributed to Berkeley by
 * Adam de Boor.
 *
 * Redistribution and use in source and binary forms, with or without
 * modification, are permitted provided that the following conditions
 * are met:
 * 1. Redistributions of source code must retain the above copyright
 *    notice, this list of conditions and the following disclaimer.
 * 2. Redistributions in binary form must reproduce the above copyright
 *    notice, this list of conditions and the following disclaimer in the
 *    documentation and/or other materials provided with the distribution.
 * 3. Neither the name of the University nor the names of its contributors
 *    may be used to endorse or promote products derived from this software
 *    without specific prior written permission.
 *
 * THIS SOFTWARE IS PROVIDED BY THE REGENTS AND CONTRIBUTORS ``AS IS'' AND
 * ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
 * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE
 * ARE DISCLAIMED.  IN NO EVENT SHALL THE REGENTS OR CONTRIBUTORS BE LIABLE
 * FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL
 * DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS
 * OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION)
 * HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT
 * LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY
 * OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF
 * SUCH DAMAGE.
 */

/*-
 * suff.c --
 *      Functions to maintain suffix lists and find implicit dependents
 *      using suffix transformation rules
 */

#include <ctype.h>
#include <stddef.h>
#include <stdint.h>
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <ohash.h>
#include "defines.h"
#include "dir.h"
#include "engine.h"
#include "suff.h"
#include "var.h"
#include "targ.h"
#include "error.h"
#include "str.h"
#include "lst.h"
#include "memory.h"
#include "gnode.h"
#include "stats.h"
#include "dump.h"
#include "expandchildren.h"

/* XXX the suffixes hash is stored using a specific hash function, suitable
 * for looking up suffixes in reverse.
 */
static struct ohash suffixes;

/* We remember the longest suffix, so we don't need to look beyond that.  */
size_t maxLen = 0U;
static LIST srclist;

/* Transforms (.c.o) are stored in another hash, independently from suffixes.
 * When make sees a target, it checks whether it's currently parsable as a
 * transform (according to the active suffixes). If yes, it's stored as a
 * new transform.
 *
 * XXX
 * But transforms DO NOT have a canonical decomposition as a set of suffixes,
 * and will be used as necessary later, when looking up implicit rules for
 * actual targets.
 *
 * For instance, a transform .a.b.c  can be parsed as .a -> .b.c if suffixes
 * .a and .b.c are active, and then LATER, reused as .a.b -> .c if suffixes
 * .a.b and .c are active.
 */
static struct ohash transforms;

/* conflicts between suffixes are solved by suffix declaration order. */
static int order = 0;

/*
 * Structure describing an individual suffix.
 */
struct Suff_ {
        size_t nameLen;         /* optimisation: strlen(name) */
        short flags;
#define SUFF_ACTIVE       0x08  /* We never destroy suffixes and rules, */
                                /* we just deactivate them. */
#define SUFF_PATH         0x10  /* False suffix: actually, the path keyword */
        LIST searchPath;        /* The path along which files of this suffix
                                 * may be found */
        int order;              /* order of declaration for conflict
                                 * resolution. */
        LIST parents;           /* List of Suff we have a transformation to */
        LIST children;          /* List of Suff we have a transformation from */
        char name[1];
};

static struct ohash_info suff_info = {
        offsetof(struct Suff_, name), NULL,
        hash_calloc, hash_free, element_alloc
};

/*
 * Structure used in the search for implied sources.
 */
typedef struct Src_ {
        char *file;             /* The file to look for */
        char *prefix;           /* Prefix from which file was formed */
        Suff *suff;             /* The suffix on the file */
        struct Src_ *parent;    /* The Src for which this is a source */
        GNode *node;            /* The node describing the file */
        int children;           /* Count of existing children (so we don't free
                                 * this thing too early or never nuke it) */
#ifdef DEBUG_SRC
        LIST        cp;         /* Debug; children list */
#endif
} Src;

/*
 * A structure for passing more than one argument to the Lst-library-invoked
 * function...
 */
typedef struct {
        Lst l;
        Src *s;
} LstSrc;

static Suff *emptySuff; /* The empty suffix required for POSIX
                         * single-suffix transformation rules */


#define parse_transform(s, p, q) parse_transformi(s, s + strlen(s), p, q)
static bool parse_transformi(const char *, const char *, Suff **, Suff **);
#define new_suffix(s)   new_suffixi(s, NULL)
static Suff *new_suffixi(const char *, const char *);
static void reverse_hash_add_char(uint32_t *, const char *);
static uint32_t reverse_hashi(const char *, const char **);
static unsigned int reverse_slot(struct ohash *, const char *, const char **);
static void record_possible_suffix(Suff *, GNode *, char *, Lst, Lst);
static void record_possible_suffixes(GNode *, Lst, Lst);
static Suff *find_suffix_as_suffix(Lst, const char *, const char *);
static Suff *add_suffixi(const char *, const char *);

static void SuffInsert(Lst, Suff *);
static void SuffAddSrc(void *, void *);
static bool SuffRemoveSrc(Lst);
static void SuffAddLevel(Lst, Src *);
static Src *SuffFindThem(Lst, Lst);
static Src *SuffFindCmds(Src *, Lst);
static bool SuffApplyTransform(GNode *, GNode *, Suff *, Suff *);
static void SuffFindDeps(GNode *, Lst);
static void SuffFindArchiveDeps(GNode *, Lst);
static void SuffFindNormalDeps(GNode *, Lst);
static void SuffPrintName(void *);
static void SuffPrintSuff(void *);
static void SuffPrintTrans(GNode *);

#define find_suff(name) find_suffi(name, NULL)
static Suff *find_suffi(const char *, const char *);
static Suff *find_best_suffix(const char *, const char *);
static GNode *find_transform(const char *);
static GNode *find_or_create_transformi(const char *, const char *);
static void setup_paths(void);
static void build_suffixes_graph(void);
static void special_path_hack(void);

#ifdef DEBUG_SRC
static void PrintAddr(void *);
#endif

/* hash functions for the suffixes hash */
/* add one char to the hash */
static void
reverse_hash_add_char(uint32_t *pk, const char *s)
{
        *pk =  ((*pk << 2) | (*pk >> 30)) ^ *s;
}

/* build a full hash from end to start */
static uint32_t
reverse_hashi(const char *s, const char **e)
{
        const char *p;
        uint32_t k;

        if (*e == NULL)
                *e = s + strlen(s);
        p = *e;
        if (p == s)
                k = 0;
        else
                k = *--p;
        while (p != s) {
                reverse_hash_add_char(&k, --p);
        }
        return k;
}

static unsigned int
reverse_slot(struct ohash *h, const char *s, const char **e)
{
        uint32_t hv;

        hv = reverse_hashi(s, e);
        return ohash_lookup_interval(h, s, *e, hv);
}


static char *
suffix_is_suffix(Suff *s, const char *str, const char *estr)
{
        const char *p1;         /* Pointer into suffix name */
        const char *p2;         /* Pointer into string being examined */

        if (estr - str < (ptrdiff_t) s->nameLen)
                return NULL;
        p1 = s->name + s->nameLen;
        p2 = estr;

        while (p1 != s->name) {
                p1--;
                p2--;
                if (*p1 != *p2)
                        return NULL;
        }

        return (char *)p2;
}

static Suff *
find_suffi(const char *name, const char *ename)
{
        unsigned int slot;
#ifdef STATS_SUFF
        STAT_SUFF_LOOKUP_NAME++;
#endif
        slot = reverse_slot(&suffixes, name, &ename);
        return ohash_find(&suffixes, slot);
}

static GNode *
find_transform(const char *name)
{
        unsigned int slot;

#ifdef STATS_SUFF
        STAT_TRANSFORM_LOOKUP_NAME++;
#endif
        slot = ohash_qlookup(&transforms, name);

        return ohash_find(&transforms, slot);
}

static GNode *
find_or_create_transformi(const char *name, const char *end)
{
        GNode *r;
        unsigned int slot;

#ifdef STATS_SUFF
        STAT_TRANSFORM_LOOKUP_NAME++;
#endif
        slot = ohash_qlookupi(&transforms, name, &end);

        r = ohash_find(&transforms, slot);

        if (r == NULL) {
                r = Targ_NewGNi(name, end);
                ohash_insert(&transforms, slot, r);
        }
        return r;
}

/*-
 *-----------------------------------------------------------------------
 * SuffInsert  --
 *      Insert the suffix into the list keeping the list ordered by suffix
 *      numbers.
 *
 * Side Effects:
 *      The reference count of the suffix is incremented
 *-----------------------------------------------------------------------
 */
static void
SuffInsert(Lst l, Suff *s)
{
        LstNode ln;             /* current element in l we're examining */
        Suff *s2 = NULL;        /* the suffix descriptor in this element */

        for (ln = Lst_First(l); ln != NULL; ln = Lst_Adv(ln)) {
                s2 = Lst_Datum(ln);
                if (s2->order >= s->order)
                        break;
        }

        if (DEBUG(SUFF))
                printf("inserting %s(%d)...", s->name, s->order);
        if (ln == NULL) {
                if (DEBUG(SUFF))
                        printf("at end of list\n");
                Lst_AtEnd(l, s);
        } else if (s2->order != s->order) {
                if (DEBUG(SUFF))
                        printf("before %s(%d)\n", s2->name, s2->order);
                Lst_Insert(l, ln, s);
        } else if (DEBUG(SUFF)) {
                printf("already there\n");
        }
}

/* Suff_DisableAllSuffixes
 *      mark all current suffixes as inactive, and reset precedence
 *      computation.  */
void
Suff_DisableAllSuffixes(void)
{
        unsigned int i;
        Suff *s;

        for (s = ohash_first(&suffixes, &i); s != NULL;
            s = ohash_next(&suffixes, &i))
                s->flags &= ~SUFF_ACTIVE;

        order = 0;
        maxLen = 0;
}


/* okay = parse_transform(str, &src, &targ);
 *      try parsing a string as a transformation rule, returns true if
 *      successful. Fills &src, &targ with the constituent suffixes.
 * Special hack: source suffixes must exist OR be the special SUFF_PATH
 * pseudo suffix (.PATH)
 */
static bool
parse_transformi(const char *str, const char *e, Suff **srcPtr, Suff **targPtr)
{
        Suff *src, *target, *best_src, *best_target;
        const char *p;

        size_t len;
        uint32_t hv;
        unsigned int slot;

        /* empty string -> no suffix */
        if (e == str)
                return false;

        len = e - str;

        if (len > 2 * maxLen)
                return false;

        p = e;
        best_src = best_target = NULL;

        hv = *--p;
        while (p != str) {
                slot = ohash_lookup_interval(&suffixes, p, e, hv);
                /* no double suffix in there */
                if (p - str <= (ptrdiff_t)maxLen) {
                        target = ohash_find(&suffixes, slot);
                        if (target != NULL && (target->flags & SUFF_ACTIVE)) {
                                src = find_suffi(str, p);
                                if (src != NULL &&
                                    (src->flags & (SUFF_ACTIVE | SUFF_PATH))) {
                                /* XXX even if we find a set of suffixes, we
                                 * have to keep going to find the best one,
                                 * namely, the one whose src appears first in
                                 * .SUFFIXES
                                 */
                                        if (best_src == NULL ||
                                            src->order < best_src->order) {
                                                best_src = src;
                                                best_target = target;
                                        }
                                }
                        }
                }
                /* can't be a suffix anyways */
                if (e - p >= (ptrdiff_t)maxLen)
                        break;
                reverse_hash_add_char(&hv, --p);
        }

        if (p == str && best_src == NULL) {
                /* no double suffix transformation, resort to single suffix if
                 * we find one.  */
                slot = ohash_lookup_interval(&suffixes, p, e, hv);
                src = ohash_find(&suffixes, slot);
                if (src != NULL && (src->flags & (SUFF_ACTIVE | SUFF_PATH))) {
                        best_src = src;
                        best_target = emptySuff;
                }
        }
        if (best_src != NULL) {
                *srcPtr = best_src;
                *targPtr = best_target;
                return true;
        } else {
                return false;
        }
}

static void
special_path_hack(void)
{
        Suff *path = add_suffixi(".PATH", NULL);
        path->flags |= SUFF_PATH;
}

static Suff *
find_best_suffix(const char *s, const char *e)
{
        const char *p;
        uint32_t hv;
        unsigned int slot;
        Suff *best = NULL;
        Suff *suff;

        if (e == s)
                return NULL;
        p = e;
        hv = *--p;
        while (p != s) {
                slot = ohash_lookup_interval(&suffixes, p, e, hv);
                suff = ohash_find(&suffixes, slot);
                if (suff != NULL)
                        if (best == NULL || suff->order < best->order)
                                best = suff;
                if (e - p >= (ptrdiff_t)maxLen)
                        break;
                reverse_hash_add_char(&hv, --p);
        }
        return best;
}

Lst
find_best_path(const char *name)
{
        Suff *s = find_best_suffix(name, name + strlen(name));
        if (s != NULL) {
                if (DEBUG(SUFF))
                        printf("suffix is \"%s\"...", s->name);
                return &s->searchPath;
        } else
                return defaultPath;
}

/*-
 *-----------------------------------------------------------------------
 * Suff_ParseAsTransform --
 *      Try parsing a target line as a transformation rule, depending on
 *      existing suffixes.
 *
 *      Possibly create a new transform, or reset an existing one.
 *-----------------------------------------------------------------------
 */
GNode *
Suff_ParseAsTransform(const char *line, const char *end)
{
        GNode *gn;      /* GNode of transformation rule */
        Suff *s;        /* source suffix */
        Suff *t;        /* target suffix */

        if (!parse_transformi(line, end, &s, &t))
                return NULL;

        gn = find_or_create_transformi(line, end);
        /* In case the transform already exists, nuke old commands and children.
         * Note we can't free them, since there might be stuff that references
         * them elsewhere
         */
        if (!Lst_IsEmpty(&gn->commands)) {
                Lst_Destroy(&gn->commands, NOFREE);
                Lst_Init(&gn->commands);
        }
        if (!Lst_IsEmpty(&gn->children)) {
                Lst_Destroy(&gn->children, NOFREE);
                Lst_Init(&gn->children);
        }

        gn->type = OP_TRANSFORM;
        if (s->flags & SUFF_PATH) {
                gn->special = SPECIAL_PATH;
                gn->suffix = t;
        }

        if (DEBUG(SUFF))
                printf("defining transformation from `%s' to `%s'\n",
                    s->name, t->name);
        return gn;
}

static void
make_suffix_known(Suff *s)
{
        if ((s->flags & SUFF_ACTIVE) == 0) {
                s->order = order++;
                s->flags |= SUFF_ACTIVE;
                if (s->nameLen > maxLen)
                        maxLen = s->nameLen;
        }
}

static Suff *
new_suffixi(const char *str, const char *eptr)
{
        Suff *s;

        s = ohash_create_entry(&suff_info, str, &eptr);
        s->nameLen = eptr - str;
        Lst_Init(&s->searchPath);
        Lst_Init(&s->children);
        Lst_Init(&s->parents);
        s->flags = 0;
        return s;
}

/*-
 *-----------------------------------------------------------------------
 * Suff_AddSuffix --
 *      Add the suffix in string to the end of the list of known suffixes.
 *      Should we restructure the suffix graph? Make doesn't...
 *
 * Side Effects:
 *      A GNode is created for the suffix and a Suff structure is created and
 *      added to the known suffixes, unless it was already known.
 *-----------------------------------------------------------------------
 */
void
Suff_AddSuffixi(const char *str, const char *end)
{
        (void)add_suffixi(str, end);
}

static Suff *
add_suffixi(const char *str, const char *end)
{
        Suff *s;            /* new suffix descriptor */

        unsigned int slot;

        slot = reverse_slot(&suffixes, str, &end);
        s = ohash_find(&suffixes, slot);
        if (s == NULL) {
                s = new_suffixi(str, end);
                ohash_insert(&suffixes, slot, s);
        }
        make_suffix_known(s);
        return s;
}

Lst
find_suffix_path(GNode *gn)
{
        if (gn->suffix != NULL && gn->suffix != emptySuff)
                return &(gn->suffix->searchPath);
        else
                return defaultPath;
}

static void
build_suffixes_graph(void)
{
        Suff *s, *s2;
        GNode *gn;
        unsigned int i;

        for (gn = ohash_first(&transforms, &i); gn != NULL;
            gn = ohash_next(&transforms, &i)) {
                if (Lst_IsEmpty(&gn->commands) && Lst_IsEmpty(&gn->children))
                        continue;
                if (gn->special == SPECIAL_PATH)
                        continue;
                if (parse_transform(gn->name, &s, &s2)) {
                        SuffInsert(&s2->children, s);
                        SuffInsert(&s->parents, s2);
                }
        }
}

/*-
 *-----------------------------------------------------------------------
 * setup_paths
 *      Extend the search paths for all suffixes to include the default
 *      search path.
 *
 * Side Effects:
 *      The searchPath field of all the suffixes is extended by the
 *      directories in defaultPath. 
 *-----------------------------------------------------------------------
 */
static void
setup_paths(void)
{
        unsigned int i;
        Suff *s;

        for (s = ohash_first(&suffixes, &i); s != NULL;
            s = ohash_next(&suffixes, &i)) {
                if (!Lst_IsEmpty(&s->searchPath))
                        Dir_Concat(&s->searchPath, defaultPath);
                else
                        Lst_Clone(&s->searchPath, defaultPath, Dir_CopyDir);
        }
}

void
process_suffixes_after_makefile_is_read(void)
{
        /* once the Makefile is finish reading, we can set up the default PATH
         * stuff, and build the final suffixes graph
         */
        setup_paths();
        /* and we link all transforms to active suffixes at this point. */
        build_suffixes_graph();
}
          /********** Implicit Source Search Functions *********/

/*-
 *-----------------------------------------------------------------------
 * SuffAddSrc  --
 *      Add a suffix as a Src structure to the given list with its parent
 *      being the given Src structure. If the suffix is the null suffix,
 *      the prefix is used unaltered as the file name in the Src structure.
 *
 * Side Effects:
 *      A Src structure is created and tacked onto the end of the list
 *-----------------------------------------------------------------------
 */
static void
SuffAddSrc(
    void *sp,           /* suffix for which to create a Src structure */
    void *lsp)          /* list and parent for the new Src */
{
        Suff *s = sp;
        LstSrc *ls = lsp;
        Src *s2;        /* new Src structure */
        Src *targ;      /* Target structure */

        targ = ls->s;

        s2 = emalloc(sizeof(Src));
        s2->file = Str_concat(targ->prefix, s->name, 0);
        s2->prefix = targ->prefix;
        s2->parent = targ;
        s2->node = NULL;
        s2->suff = s;
        s2->children = 0;
        targ->children++;
        Lst_AtEnd(ls->l, s2);
#ifdef DEBUG_SRC
        Lst_Init(&s2->cp);
        Lst_AtEnd(&targ->cp, s2);
        printf("2 add %x %x to %x:", targ, s2, ls->l);
        Lst_Every(ls->l, PrintAddr);
        printf("\n");
#endif

}

/*-
 *-----------------------------------------------------------------------
 * SuffAddLevel  --
 *      Add all the children of targ as Src structures to the given list
 *
 * Side Effects:
 *      Lots of structures are created and added to the list
 *-----------------------------------------------------------------------
 */
static void
SuffAddLevel(
    Lst l,      /* list to which to add the new level */
    Src *targ)  /* Src structure to use as the parent */
{
        LstSrc     ls;

        ls.s = targ;
        ls.l = l;

        Lst_ForEach(&targ->suff->children, SuffAddSrc, &ls);
}

/*-
 *----------------------------------------------------------------------
 * SuffRemoveSrc --
 *      Free Src structure with a zero reference count in a list
 *
 *      returns true if a src was removed
 *----------------------------------------------------------------------
 */
static bool
SuffRemoveSrc(Lst l)
{
        LstNode ln;
        Src *s;

#ifdef DEBUG_SRC
        printf("cleaning %lx: ", (unsigned long)l);
        Lst_Every(l, PrintAddr);
        printf("\n");
#endif


        for (ln = Lst_First(l); ln != NULL; ln = Lst_Adv(ln)) {
                s = Lst_Datum(ln);
                if (s->children == 0) {
                        free(s->file);
                        if (!s->parent)
                                free(s->prefix);
                        else {
#ifdef DEBUG_SRC
                                LstNode ln2 = Lst_Member(&s->parent->cp, s);
                                if (ln2 != NULL)
                                    Lst_Remove(&s->parent->cp, ln2);
#endif
                                --s->parent->children;
                        }
#ifdef DEBUG_SRC
                        printf("free: [l=%x] p=%x %d\n", l, s, s->children);
                        Lst_Destroy(&s->cp, NOFREE);
#endif
                        Lst_Remove(l, ln);
                        free(s);
                        return true;
                }
#ifdef DEBUG_SRC
                else {
                        printf("keep: [l=%x] p=%x %d: ", l, s, s->children);
                        Lst_Every(&s->cp, PrintAddr);
                        printf("\n");
                }
#endif
        }

        return false;
}

/*-
 *-----------------------------------------------------------------------
 * SuffFindThem --
 *      Find the first existing file/target in the list srcs
 *
 * Results:
 *      The lowest structure in the chain of transformations
 *-----------------------------------------------------------------------
 */
static Src *
SuffFindThem(
    Lst srcs,   /* list of Src structures to search through */
    Lst slst)
{
        Src *s;         /* current Src */
        Src *rs;        /* returned Src */
        char *ptr;

        rs = NULL;

        while ((s = Lst_DeQueue(srcs)) != NULL) {
                if (DEBUG(SUFF))
                        printf("\ttrying %s...", s->file);

                /*
                 * A file is considered to exist if either a node exists in the
                 * graph for it or the file actually exists.
                 */
                if (Targ_FindNode(s->file, TARG_NOCREATE) != NULL) {
#ifdef DEBUG_SRC
                        printf("remove %x from %x\n", s, srcs);
#endif
                        rs = s;
                        break;
                }

                if ((ptr = Dir_FindFile(s->file, &s->suff->searchPath))
                    != NULL) {
                        rs = s;
#ifdef DEBUG_SRC
                        printf("remove %x from %x\n", s, srcs);
#endif
                        free(ptr);
                        break;
                }

                if (DEBUG(SUFF))
                    printf("not there\n");

                SuffAddLevel(srcs, s);
                Lst_AtEnd(slst, s);
        }

        if (DEBUG(SUFF) && rs)
            printf("got it\n");
        return rs;
}

/*-
 *-----------------------------------------------------------------------
 * SuffFindCmds --
 *      See if any of the children of the target in the Src structure is
 *      one from which the target can be transformed. If there is one,
 *      a Src structure is put together for it and returned.
 *-----------------------------------------------------------------------
 */
static Src *
SuffFindCmds(Src *targ, Lst slst)
{
        LstNode ln;     /* General-purpose list node */
        GNode *t;       /* Target GNode */
        GNode *s;       /* Source GNode */
        int prefixLen;  /* The length of the defined prefix */
        Suff *suff;     /* Suffix on matching beastie */
        Src *ret;       /* Return value */
        const char *cp;

        t = targ->node;
        prefixLen = strlen(targ->prefix);

        for (ln = Lst_First(&t->children); ln != NULL; ln = Lst_Adv(ln)) {
                s = Lst_Datum(ln);

                cp = strrchr(s->name, '/');
                if (cp == NULL)
                        cp = s->name;
                else
                        cp++;
                if (strncmp(cp, targ->prefix, prefixLen) != 0)
                        continue;
                /* The node matches the prefix ok, see if it has a known
                 * suffix.      */
                suff = find_suff(&cp[prefixLen]);
                if (suff == NULL)
                        continue;
                /*
                 * It even has a known suffix, see if there's a transformation
                 * defined between the node's suffix and the target's suffix.
                 *
                 * XXX: Handle multi-stage transformations here, too.
                 */
                if (Lst_Member(&suff->parents, targ->suff) == NULL)
                        continue;
                /*
                 * Create a new Src structure to describe this transformation
                 * (making sure to duplicate the source node's name so
                 * Suff_FindDeps can free it again (ick)), and return the new
                 * structure.
                 */
                ret = emalloc(sizeof(Src));
                ret->file = estrdup(s->name);
                ret->prefix = targ->prefix;
                ret->suff = suff;
                ret->parent = targ;
                ret->node = s;
                ret->children = 0;
                targ->children++;
#ifdef DEBUG_SRC
                Lst_Init(&ret->cp);
                printf("3 add %x %x\n", targ, ret);
                Lst_AtEnd(&targ->cp, ret);
#endif
                Lst_AtEnd(slst, ret);
                if (DEBUG(SUFF))
                        printf("\tusing existing source %s\n", s->name);
                return ret;
        }
        return NULL;
}

/*-
 *-----------------------------------------------------------------------
 * SuffApplyTransform --
 *      Apply a transformation rule, given the source and target nodes
 *      and suffixes.
 *
 * Results:
 *      true if successful, false if not.
 *
 * Side Effects:
 *      The source and target are linked and the commands from the
 *      transformation are added to the target node's commands list.
 *      All attributes but OP_DEPMASK and OP_TRANSFORM are applied
 *      to the target. The target also inherits all the sources for
 *      the transformation rule.
 *-----------------------------------------------------------------------
 */
static bool
SuffApplyTransform(
    GNode       *tGn,   /* Target node */
    GNode       *sGn,   /* Source node */
    Suff        *t,     /* Target suffix */
    Suff        *s)     /* Source suffix */
{
        LstNode ln;     /* General node */
        char    *tname; /* Name of transformation rule */
        GNode   *gn;    /* Node for same */

        if (Lst_AddNew(&tGn->children, sGn)) {
                /* Not already linked, so form the proper links between the
                 * target and source.  */
                LinkParent(sGn, tGn);
        }

        if ((sGn->type & OP_OPMASK) == OP_DOUBLEDEP) {
                /* When a :: node is used as the implied source of a node, we
                 * have to link all its cohorts in as sources as well. There's
                 * only one implied src, as that will be sufficient to get
                 * the .IMPSRC variable set for tGn.    */
                for (ln=Lst_First(&sGn->cohorts); ln != NULL; ln=Lst_Adv(ln)) {
                        gn = Lst_Datum(ln);

                        if (Lst_AddNew(&tGn->children, gn)) {
                                /* Not already linked, so form the proper links
                                 * between the target and source.  */
                                LinkParent(gn, tGn);
                        }
                }
        }
        /* Locate the transformation rule itself.  */
        tname = Str_concat(s->name, t->name, 0);
        gn = find_transform(tname);
        free(tname);

        if (gn == NULL)
                /*
                 * Not really such a transformation rule (can happen when we're
                 * called to link an OP_MEMBER and OP_ARCHV node), so return
                 * false.
                 */
                return false;

        if (DEBUG(SUFF))
                printf("\tapplying %s -> %s to \"%s\"\n", s->name, t->name,
                    tGn->name);

        /* Record last child for expansion purposes.  */
        ln = Lst_Last(&tGn->children);

        /* Pass the buck to Make_HandleUse to apply the rule.  */
        Make_HandleUse(gn, tGn);

        /* Deal with wildcards and variables in any acquired sources.  */
        expand_children_from(tGn, Lst_Succ(ln));

        /* Keep track of another parent to which this beast is transformed so
         * the .IMPSRC variable can be set correctly for the parent.  */
        tGn->impliedsrc = sGn;

        return true;
}

static Suff *
find_suffix_as_suffix(Lst l, const char *b, const char *e)
{
        LstNode ln;
        Suff *s;

        for (ln = Lst_First(l); ln != NULL; ln = Lst_Adv(ln)) {
                s = Lst_Datum(ln);
                if (suffix_is_suffix(s, b, e))
                        return s;
        }
        return NULL;
}

/*-
 *-----------------------------------------------------------------------
 * SuffFindArchiveDeps --
 *      Locate dependencies for an OP_ARCHV node.
 *
 * Side Effects:
 *      Same as Suff_FindDeps
 *-----------------------------------------------------------------------
 */
static void
SuffFindArchiveDeps(
    GNode       *gn,    /* Node for which to locate dependencies */
    Lst         slst)
{
        char *eoarch;   /* End of archive portion */
        char *eoname;   /* End of member portion */
        GNode *mem;     /* Node for member */
        Suff *ms;       /* Suffix descriptor for member */
        char *name;     /* Start of member's name */

        /* The node is an archive(member) pair. so we must find a suffix
         * for both of them.  */
        eoarch = strchr(gn->name, '(');
        if (eoarch == NULL)
                return;

        name = eoarch + 1;

        eoname = strchr(name, ')');
        if (eoname == NULL)
                return;

        /* To simplify things, call Suff_FindDeps recursively on the member now,
         * so we can simply compare the member's .PREFIX and .TARGET variables
         * to locate its suffix. This allows us to figure out the suffix to
         * use for the archive without having to do a quadratic search over the
         * suffix list, backtracking for each one...  */
        mem = Targ_FindNodei(name, eoname, TARG_CREATE);
        SuffFindDeps(mem, slst);

        /* Create the link between the two nodes right off. */
        if (Lst_AddNew(&gn->children, mem))
                LinkParent(mem, gn);

        /* Copy variables from member node to this one.  */
        Var(TARGET_INDEX, gn) = Var(TARGET_INDEX, mem);
        Var(PREFIX_INDEX, gn) = Var(PREFIX_INDEX, mem);

        ms = mem->suffix;
        if (ms == NULL) {
                /* Didn't know what it was -- use .NULL suffix if not in make
                 * mode.  */
                if (DEBUG(SUFF))
                        printf("using empty suffix\n");
                ms = emptySuff;
        }


        /* Set the other two local variables required for this target.  */
        Var(MEMBER_INDEX, gn) = mem->name;
        Var(ARCHIVE_INDEX, gn) = gn->name;

        if (ms != NULL) {
                /*
                 * Member has a known suffix, so look for a transformation rule
                 * from it to a possible suffix of the archive. Rather than
                 * searching through the entire list, we just look at suffixes
                 * to which the member's suffix may be transformed...
                 */

                Suff *suff;

                suff = find_suffix_as_suffix(&ms->parents, gn->name, eoarch);

                if (suff != NULL) {
                        /* Got one -- apply it.  */
                        if (!SuffApplyTransform(gn, mem, suff, ms) &&
                            DEBUG(SUFF))
                                printf("\tNo transformation from %s -> %s\n",
                                   ms->name, suff->name);
                }
        }

        /* Pretend gn appeared to the left of a dependency operator so
         * the user needn't provide a transformation from the member to the
         * archive.  */
        if (OP_NOP(gn->type))
                gn->type |= OP_DEPENDS;

        /* Flag the member as such so we remember to look in the archive for
         * its modification time.  */
        mem->type |= OP_MEMBER;
}

static void
record_possible_suffix(Suff *s, GNode *gn, char *eoname, Lst srcs, Lst targs)
{
        int prefixLen;
        Src *targ;

        targ = emalloc(sizeof(Src));
        targ->file = estrdup(gn->name);
        targ->suff = s;
        targ->node = gn;
        targ->parent = NULL;
        targ->children = 0;
#ifdef DEBUG_SRC
        Lst_Init(&targ->cp);
#endif

        /* Allocate room for the prefix, whose end is found by
         * subtracting the length of the suffix from the end of
         * the name.  */
        prefixLen = (eoname - targ->suff->nameLen) - gn->name;
        targ->prefix = emalloc(prefixLen + 1);
        memcpy(targ->prefix, gn->name, prefixLen);
        targ->prefix[prefixLen] = '\0';

        /* Add nodes from which the target can be made.  */
        SuffAddLevel(srcs, targ);

        /* Record the target so we can nuke it.  */
        Lst_AtEnd(targs, targ);
}

static void
record_possible_suffixes(GNode *gn, Lst srcs, Lst targs)
{
        char *s = gn->name;
        char *e =  s + strlen(s);
        const char *p;
        uint32_t hv;
        unsigned int slot;
        Suff *suff;

        if (e == s)
                return;

        p = e;
        hv = *--p;

        while (p != s) {
                slot = ohash_lookup_interval(&suffixes, p, e, hv);
                suff = ohash_find(&suffixes, slot);
                if (suff != NULL && (suff->flags & SUFF_ACTIVE))
                        record_possible_suffix(suff, gn, e, srcs, targs);
                if (e - p >= (ptrdiff_t)maxLen)
                        break;
                reverse_hash_add_char(&hv, --p);
        }
}

/*-
 *-----------------------------------------------------------------------
 * SuffFindNormalDeps --
 *      Locate implicit dependencies for regular targets.
 *
 * Side Effects:
 *      Same as Suff_FindDeps...
 *-----------------------------------------------------------------------
 */
static void
SuffFindNormalDeps(
    GNode       *gn,        /* Node for which to find sources */
    Lst         slst)
{
        LIST srcs;      /* List of sources at which to look */
        LIST targs;     /* List of targets to which things can be
                         * transformed. They all have the same file,
                         * but different suff and prefix fields */
        Src *bottom;    /* Start of found transformation path */
        Src *src;       /* General Src pointer */
        char *prefix;   /* Prefix to use */
        Src *targ;      /* General Src target pointer */


        Lst_Init(&srcs);
        Lst_Init(&targs);

        /* We're caught in a catch-22 here. On the one hand, we want to use any
         * transformation implied by the target's sources, but we can't examine
         * the sources until we've expanded any variables/wildcards they may
         * hold, and we can't do that until we've set up the target's local
         * variables and we can't do that until we know what the proper suffix
         * for the target is (in case there are two suffixes one of which is a
         * suffix of the other) and we can't know that until we've found its
         * implied source, which we may not want to use if there's an existing
         * source that implies a different transformation.
         *
         * In an attempt to get around this, which may not work all the time,
         * but should work most of the time, we look for implied sources first,
         * checking transformations to all possible suffixes of the target, use
         * what we find to set the target's local variables, expand the
         * children, then look for any overriding transformations they imply.
         * Should we find one, we discard the one we found before.      */


        record_possible_suffixes(gn, &srcs, &targs);
        /* Handle target of unknown suffix...  */
        if (Lst_IsEmpty(&srcs)) {
                if (DEBUG(SUFF))
                        printf("\tNo known suffix on %s. Using empty suffix\n",
                            gn->name);

                targ = emalloc(sizeof(Src));
                targ->file = estrdup(gn->name);
                targ->suff = emptySuff;
                targ->node = gn;
                targ->parent = NULL;
                targ->children = 0;
                targ->prefix = estrdup(gn->name);
#ifdef DEBUG_SRC
                Lst_Init(&targ->cp);
#endif

                /* Only use the default suffix rules if we don't have commands
                 * or dependencies defined for this gnode.  */
                if (Lst_IsEmpty(&gn->commands) && Lst_IsEmpty(&gn->children))
                        SuffAddLevel(&srcs, targ);
                else {
                        if (DEBUG(SUFF))
                                printf("not ");
                }

                if (DEBUG(SUFF))
                        printf("adding suffix rules\n");

                Lst_AtEnd(&targs, targ);
        }

        /* Using the list of possible sources built up from the target
         * suffix(es), try and find an existing file/target that matches.  */
        bottom = SuffFindThem(&srcs, slst);

        if (bottom == NULL) {
                /* No known transformations -- use the first suffix found for
                 * setting the local variables.  */
                if (!Lst_IsEmpty(&targs))
                        targ = Lst_Datum(Lst_First(&targs));
                else
                        targ = NULL;
        } else {
                /* Work up the transformation path to find the suffix of the
                 * target to which the transformation was made.  */
                for (targ = bottom; targ->parent != NULL; targ = targ->parent)
                        continue;
        }

        /* The .TARGET variable we always set to be the name at this point,
         * since it's only set to the path if the thing is only a source and
         * if it's only a source, it doesn't matter what we put here as far
         * as expanding sources is concerned, since it has none...      */
        Var(TARGET_INDEX, gn) = gn->name;

        prefix = targ != NULL ? estrdup(targ->prefix) : gn->name;
        Var(PREFIX_INDEX, gn) = prefix;

        /* Now we've got the important local variables set, expand any sources
         * that still contain variables or wildcards in their names.  */
        expand_all_children(gn);

        if (targ == NULL) {
                if (DEBUG(SUFF))
                        printf("\tNo valid suffix on %s\n", gn->name);

sfnd_abort:
                /* Deal with finding the thing on the default search path if the
                 * node is only a source (not on the lhs of a dependency operator
                 * or [XXX] it has neither children or commands).  */
                if (OP_NOP(gn->type) ||
                    (Lst_IsEmpty(&gn->children) &&
                    Lst_IsEmpty(&gn->commands))) {
                        gn->path = Dir_FindFile(gn->name,
                            (targ == NULL ? defaultPath :
                            &targ->suff->searchPath));
                        if (gn->path != NULL) {
                                char *ptr;
                                Var(TARGET_INDEX, gn) = estrdup(gn->path);

                                if (targ != NULL) {
                                        /* Suffix known for the thing -- trim
                                         * the suffix off the path to form the
                                         * proper .PREFIX variable.  */
                                        int savep = strlen(gn->path) -
                                            targ->suff->nameLen;
                                        char savec;

                                        gn->suffix = targ->suff;

                                        savec = gn->path[savep];
                                        gn->path[savep] = '\0';

                                        if ((ptr = strrchr(gn->path, '/')) !=
                                            NULL)
                                                ptr++;
                                        else
                                                ptr = gn->path;

                                        Var(PREFIX_INDEX, gn) = estrdup(ptr);

                                        gn->path[savep] = savec;
                                } else {
                                        /* The .PREFIX gets the full path if the
                                         * target has no known suffix.  */
                                        gn->suffix = NULL;

                                        if ((ptr = strrchr(gn->path, '/')) !=
                                            NULL)
                                                ptr++;
                                        else
                                                ptr = gn->path;

                                        Var(PREFIX_INDEX, gn) = estrdup(ptr);
                                }
                        }
                } else {
                        /* Not appropriate to search for the thing -- set the
                         * path to be the name so Dir_MTime won't go grovelling
                         * for it.  */
                        gn->suffix = targ == NULL ? NULL : targ->suff;
                        free(gn->path);
                        gn->path = estrdup(gn->name);
                }

                goto sfnd_return;
        }

        /* Check for overriding transformation rule implied by sources.  */
        if (!Lst_IsEmpty(&gn->children)) {
                src = SuffFindCmds(targ, slst);

                if (src != NULL) {
                        /* Free up all the Src structures in the transformation
                         * path up to, but not including, the parent node.  */
                        while (bottom && bottom->parent != NULL) {
                                (void)Lst_AddNew(slst, bottom);
                                bottom = bottom->parent;
                        }
                        bottom = src;
                }
        }

        if (bottom == NULL) {
                /* No idea from where it can come -- return now.  */
                goto sfnd_abort;
        }

        /* We now have a list of Src structures headed by 'bottom' and linked
         * via their 'parent' pointers. What we do next is create links between
         * source and target nodes (which may or may not have been created) and
         * set the necessary local variables in each target. The commands for
         * each target are set from the commands of the transformation rule
         * used to get from the src suffix to the targ suffix. Note that this
         * causes the commands list of the original node, gn, to be replaced by
         * the commands of the final transformation rule. Also, the children
         * to build field of gn is incremented.  Etc.  */
        if (bottom->node == NULL) {
                bottom->node = Targ_FindNode(bottom->file, TARG_CREATE);
        }

        for (src = bottom; src->parent != NULL; src = src->parent) {
                targ = src->parent;

                src->node->suffix = src->suff;

                if (targ->node == NULL) {
                        targ->node = Targ_FindNode(targ->file, TARG_CREATE);
                }

                SuffApplyTransform(targ->node, src->node,
                                   targ->suff, src->suff);

                if (targ->node != gn) {
                        /* Finish off the dependency-search process for any
                         * nodes between bottom and gn (no point in questing
                         * around the filesystem for their implicit source when
                         * it's already known). Note that the node can't have
                         * any sources that need expanding, since SuffFindThem
                         * will stop on an existing node, so all we need to do
                         * is set the standard and System V variables.  */
                        targ->node->type |= OP_DEPS_FOUND;

                        Var(PREFIX_INDEX, targ->node) = estrdup(targ->prefix);

                        Var(TARGET_INDEX, targ->node) = targ->node->name;
                }
        }

        gn->suffix = src->suff;

        /* So Dir_MTime doesn't go questing for it...  */
        free(gn->path);
        gn->path = estrdup(gn->name);

        /* Nuke the transformation path and the Src structures left over in the
         * two lists.  */
sfnd_return:
        if (bottom)
                (void)Lst_AddNew(slst, bottom);

        while (SuffRemoveSrc(&srcs) || SuffRemoveSrc(&targs))
                continue;

        Lst_ConcatDestroy(slst, &srcs);
        Lst_ConcatDestroy(slst, &targs);
}


/*-
 *-----------------------------------------------------------------------
 * Suff_FindDeps  --
 *      Find implicit sources for the target described by the graph node
 *      gn
 *
 * Side Effects:
 *      Nodes are added to the graph below the passed-in node. The nodes
 *      are marked to have their IMPSRC variable filled in. The
 *      PREFIX variable is set for the given node and all its
 *      implied children.
 *
 * Notes:
 *      The path found by this target is the shortest path in the
 *      transformation graph, which may pass through non-existent targets,
 *      to an existing target. The search continues on all paths from the
 *      root suffix until a file is found. I.e. if there's a path
 *      .o -> .c -> .l -> .l,v from the root and the .l,v file exists but
 *      the .c and .l files don't, the search will branch out in
 *      all directions from .o and again from all the nodes on the
 *      next level until the .l,v node is encountered.
 *-----------------------------------------------------------------------
 */

void
Suff_FindDeps(GNode *gn)
{

        SuffFindDeps(gn, &srclist);
        while (SuffRemoveSrc(&srclist))
                continue;
}


static void
SuffFindDeps(GNode *gn, Lst slst)
{
        if (gn->type & OP_DEPS_FOUND) {
                /*
                 * If dependencies already found, no need to do it again...
                 */
                return;
        } else {
                gn->type |= OP_DEPS_FOUND;
        }

        if (DEBUG(SUFF))
                printf("SuffFindDeps (%s)\n", gn->name);

        current_node = gn;
        if (gn->type & OP_ARCHV)
                SuffFindArchiveDeps(gn, slst);
        else
                SuffFindNormalDeps(gn, slst);
        current_node = NULL;
}

/*-
 *-----------------------------------------------------------------------
 * Suff_Init --
 *      Initialize suffixes module
 *
 * Side Effects:
 *      Many
 *-----------------------------------------------------------------------
 */
void
Suff_Init(void)
{
        Static_Lst_Init(&srclist);
        ohash_init(&transforms, 4, &gnode_info);

        /* Create null suffix for single-suffix rules (POSIX). The thing doesn't
         * actually go on the suffix list as it matches everything.  */
        emptySuff = new_suffix("");
        emptySuff->flags = SUFF_ACTIVE;
        emptySuff->order = 0;
        Dir_Concat(&emptySuff->searchPath, defaultPath);
        ohash_init(&suffixes, 4, &suff_info);
        special_path_hack();
}


/********************* DEBUGGING FUNCTIONS **********************/

static void
SuffPrintName(void *p)
{
        const Suff *s = p;
        printf("%s ", s == emptySuff ? "<empty>" : s->name);
}

static void
SuffPrintSuff(void *sp)
{
        Suff    *s = sp;

        printf("# %-5s ", s->name);

        if (!Lst_IsEmpty(&s->parents)) {
                printf(" ->");
                Lst_Every(&s->parents, SuffPrintName);
        }
        if (!Lst_IsEmpty(&s->children)) {
                printf(" <-");
                Lst_Every(&s->children, SuffPrintName);
        }
        fputc('\n', stdout);
}

static void
SuffPrintTrans(GNode *t)
{
        printf("%-16s: ", t->name);
        Targ_PrintType(t->type);
        fputc('\n', stdout);
        Lst_Every(&t->commands, Targ_PrintCmd);
        fputc('\n', stdout);
}

static int 
compare_order(const void *a, const void *b)
{
        const Suff **pa = (const Suff **)a;
        const Suff **pb = (const Suff **)b;
        return (*pb)->order - (*pa)->order;
}

static void
print_path(Suff *s)
{
        /* do we need to print it ? compare against defaultPath */
        LstNode ln1, ln2;
        bool first = true;

        for (ln1 = Lst_First(&s->searchPath), ln2 = Lst_First(defaultPath);
            ln1 != NULL && ln2 != NULL; 
            ln1 = Lst_Adv(ln1)) {
                if (Lst_Datum(ln1) == Lst_Datum(ln2)) {
                        ln2 = Lst_Adv(ln2);
                        continue;
                }
                if (first) {
                        printf(".PATH%s:", s->name);
                        first = false;
                }
                printf(" %s", PathEntry_name(Lst_Datum(ln1)));
        }
        if (!first)
                printf("\n\n");
}

void
Suff_PrintAll(void)
{
        Suff **t;
        GNode **u;
        unsigned int i;
        bool reprint;


        printf("# Suffixes graph\n");
        t = sort_ohash_by_name(&suffixes);
        for (i = 0; t[i] != NULL; i++)
                if (!(t[i]->flags & SUFF_PATH))
                        SuffPrintSuff(t[i]);

        printf("\n.PATH: ");
        Dir_PrintPath(defaultPath);
        printf("\n\n");
        for (i = 0; t[i] != NULL; i++)
                if (!(t[i]->flags & SUFF_PATH))
                        print_path(t[i]);
        free(t);

        reprint = false;
        t = sort_ohash(&suffixes, compare_order);
        printf(".SUFFIXES:");
        for (i = 0; t[i] != NULL; i++) {
                if (t[i]->flags & SUFF_PATH)
                        continue;
                printf(" %s", t[i]->name);
                if (!(t[i]->flags & SUFF_ACTIVE))
                        reprint = true;
        }
        printf("\n\n");
        u = sort_ohash_by_name(&transforms);
        for (i = 0; u[i] != NULL; i++)
                SuffPrintTrans(u[i]);
        free(u);

        if (reprint) {
                printf(".SUFFIXES:");
                for (i = 0; t[i] != NULL; i++)
                        if (t[i]->flags & SUFF_ACTIVE)
                                printf(" %s", t[i]->name);
                printf("\n");
        }
        free(t);
}

#ifdef DEBUG_SRC
static void
PrintAddr(void *a)
{
        printf("%lx ", (unsigned long)a);
}
#endif