File: [local] / src / usr.bin / make / suff.c (download)
Revision 1.103, Mon Sep 4 11:35:11 2023 UTC (8 months, 2 weeks ago) by espie
Branch: MAIN
CVS Tags: OPENBSD_7_5_BASE, OPENBSD_7_5, OPENBSD_7_4_BASE, OPENBSD_7_4, HEAD
Changes since 1.102: +1 -2 lines
GC old code that was originally implemented to facilitate adoption by
other BSDs, which never happened, so make things simpler for further
development.
Ditches config.h entirely since it gets reduced to 2 defines.
okay tb@
|
/* $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
![[BACK]](/icons/back.gif){kind=icon}
Return to suff.c CVS log ![[TXT]](/icons/text.gif){kind=icon}
![[DIR]](/icons/dir.gif){kind=icon}
Up to [local] / src / usr.bin / make