wdvi

filefind.c (45081B)

---

 /*========================================================================*\
 
 Copyright (c) 1996-2013  Paul Vojta
 
 Permission is hereby granted, free of charge, to any person obtaining a copy
 of this software and associated documentation files (the "Software"), to
 deal in the Software without restriction, including without limitation the
 rights to use, copy, modify, merge, publish, distribute, sublicense, and/or
 sell copies of the Software, and to permit persons to whom the Software is
 furnished to do so, subject to the following conditions:
 
 The above copyright notice and this permission notice shall be included in
 all copies or substantial portions of the Software.
 
 THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR
 IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY,
 FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT.  IN NO EVENT SHALL
 PAUL VOJTA BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER LIABILITY, WHETHER
 IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING FROM, OUT OF OR IN
 CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN THE SOFTWARE.
 
 \*========================================================================*/
 
 /*
  *	filefind.c - Routines to perform file searches.
  */
 
 /*
  *	We assume that "filf-app.h" includes the following, if appropriate:
  *
  *		<stdlib.h>
  *		<unistd.h>
  *		<string.h>
  *		<memory.h>
  *		<sys/types.h>
  *		<sys/stat.h>
  *		<setjmp.h>
  *		<pwd.h>
  */
 
 #include <sys/types.h>	/* opendir() */
 
 #include <dirent.h>	/* opendir() */
 #include <err.h>
 #include <setjmp.h>	/* jmp_buf, longjmp(), setjmp() */
 #include <stdlib.h>	/* getenv() */
 
 #include "filf-app.h"		/* application-related declarations & defs */
 #include "filefind.h"
 #include "util.h"	/* xfopen(), expandline(), ff_getpw() */
 
 
 /* default list of texmf trees */
 #define	DEFAULT_TEXMF_PATH		\
 "/usr/local/share/texmf-local:"		\
 "/usr/local/share/texmf-dist:"		\
 "/usr/local/share/texmf:"		\
 "/usr/local/texlive/texmf-local:"	\
 "/usr/local/texlive/texmf-dist:"	\
 "/usr/local/texlive/texmf:"		\
 "/usr/share/texmf-local:"		\
 "/usr/share/texmf-dist:"		\
 "/usr/share/texmf:"			\
 "/usr/share/texlive/texmf-local:"	\
 "/usr/share/texlive/texmf-dist:"	\
 "/usr/share/texlive/texmf"
 
 
 #if !defined(S_ISREG) && defined(S_IFREG)
 #define	S_ISREG(m)	(((m) & S_IFMT) == S_IFREG)
 #endif
 
 #if !defined(S_ISDIR) && defined(S_IFDIR)
 #define	S_ISDIR(m)	(((m) & S_IFMT) == S_IFDIR)
 #endif
 
 #if !defined(S_ISLNK) && defined(S_IFLNK)
 #define	S_ISLNK(m)	(((m) & S_IFMT) == S_IFLNK)
 #endif
 
 #ifndef	ST_NLINK_TRICK
 #define	ST_NLINK_TRICK	1
 #endif	/* !defined(ST_NLINK_TRICK) */
 
 	/* These are defined so that the editor can match braces properly.  */
 #define	LBRACE	'{'
 #define	RBRACE	'}'
 
 	/* In configuration files, semicolons are also valid separators.  */
 #define	IS_SEP(c)	((c) == ':')
 
 /*	Local copy of findrec record. */
 
 static	struct findrec	lrec;
 
 /*
  *	Additional data structures.
  */
 
 struct	statrec {		/* status vis-a-vis laying down the file name */
 	unsigned	pos;		/* position in ffline */
 	int		flags;
 	char		quickchar;	/* '\0' or 'q' or 'Q' */
 	unsigned	quickpos;	/* value of pos (above) if 'q' or 'Q' */
 };
 
 struct	texmfrec {		/* list of texmf components */
 	struct texmfrec	*next;
 	const	char	*home;
 	const	char	*str;
 	int		len;
 	int		flags;
 };
 
 static	const char	default_texmf_path[]	= DEFAULT_TEXMF_PATH;
 
 /*	These are global variables. */
 
 const	char			*fF_values[MAX_N_OPTS];	/* not static */
 
 static	FILE			*file_found;
 static	jmp_buf			got_it;
 static	struct steprec		**bracepp;
 static	struct steprec		**steppp;
 static	struct findrec		*frecp;		/* used to distinguish ls-Rs */
 static	int			seqno;
 static	struct texmfrec		*texmfhead	= NULL;
 static	struct rootrec		**rootpp;
 static	const	struct atomrec	*treeatom;
 
 	/* dummy records for handling %s after // or wild cards */
 static	struct atomrec	pct_s_dummy = {NULL, NULL, NULL, F_PCT_S};
 static	struct atomrec	pct_s_dummy_slash
 			= {NULL, NULL, NULL, F_PCT_S | F_SLASH_SLASH};
 
 	/* flag value for directories not read yet */
 static	struct treerec	not_read_yet = {NULL, NULL, NULL};
 
 /*
  *	The following expands in 128-byte increments to be as long as is
  *	necessary.  We don't often use pointers to refer to elements of this
  *	array, since it may move when it is enlarged.
  */
 
 #if !EXTERN_FFLINE
 static	char	*ffline		= NULL;
 static	int	ffline_len	= 0;	/* current length of the array */
 #endif
 
 
 /*
  *	ls-R database hash table
  */
 
 struct	lsr {
 	struct lsr	*next;		/* next in hash chain */
 	struct findrec	*frecp;		/* which search type? */
 	short		seqno;		/* which ls-R invocation we are using */
 	short		keylen;		/* length of key */
 	const	char	*key;
 	const	char	*value;
 };
 
 static	struct lsr	*lsrtab[1024];	/* hash table */
 
 
 /*
  *	Forward references.
  */
 
 static	void		dobrace(const char *, unsigned, int, Boolean);
 static	struct steprec	*scan_pct_s(void);
 static	void		atomize_pct_s(void);
 
 
 #if !EXTERN_FFLINE
 
 /*
  *	Expand ffline[] to at least the given size.
  */
 
 static	void
 expandline(n)
 	int	n;
 {
 	int	newlen	= n + 128;
 
 	ffline = (ffline == NULL) ? xmalloc(newlen) : xrealloc(ffline, newlen);
 	ffline_len = newlen;
 }
 
 #endif	/* !EXTERN_FFLINE */
 
 
 /*
  *	prehash() - hash function (before modding).
  */
 
 static	unsigned int
 prehash(str, len)
 	const	char	*str;
 	size_t		len;
 {
 	const	char	*p;
 	unsigned int	hash;
 
 	hash = 0;
 	for (p = str + len; p > str; )
 	    hash = hash * 5 + *--p;
 	return hash;
 }
 
 
 #if !EXTERN_GETPW
 
 /*
  *	Look up the home directory.
  */
 
 static	const	struct passwd *
 ff_getpw(pp, p_end)
 	const	char	**pp;
 	const	char	*p_end;
 {
 	const	char		*p	= *pp;
 	const	char		*p1;
 	int			len;
 	const	struct passwd	*pw;
 
 	++p;	/* skip the tilde */
 	p1 = p;
 	while (p1 < p_end && *p1 != '/') ++p1;
 	len = p1 - p;
 	if (len == 0)	/* if no user name */
 	    pw = getpwuid(getuid());
 	else {
 	    if (len >= ffline_len)
 		expandline(len);
 	    bcopy(p, ffline, len);
 	    ffline[len] = '\0';
 	    pw = getpwnam(ffline);
 	}
 	if (pw != NULL)
 	    *pp = p1;
 	return pw;
 }
 
 #endif	/* !EXTERN_GETPW */
 
 
 static	void
 gethome(pp, p_end, homepp)
 	const	char	**pp;
 	const	char	*p_end;
 	const	char	**homepp;
 {
 	const	struct passwd	*pw;
 
 	pw = ff_getpw(pp, p_end);
 	if (pw != NULL)
 	    *homepp = xstrdup(pw->pw_dir);
 }
 
 /*
  *	Scan the path part from // or wild cards, to the end.
  *	This assumes that {} have already been taken care of.
  */
 
 static	void
 atomize(p0, sp)
 	const	char	*p0;
 	struct steprec	*sp;
 {
 	struct atomrec	*head;
 	struct atomrec	**linkpp;
 	int		flags;		/* F_SLASH_SLASH and F_WILD */
 	Boolean		percent_s;
 	const	char	*p	= p0;
 	const	char	*p1;
 	const	char	*p2;
 
 	/*
 	 * First check the string for braces.
 	 */
 
 	for (p1 = p; ;++p1) {
 	    if (*p1 == '\0' || IS_SEP(*p1))
 		break;
 	    if (*p1 == LBRACE) {
 		/* Take care of braces first.  This code should only be reached
 		 * if atomize() is called from ff_prescan(). */
 		unsigned n;
 
 		bracepp = &sp->nextstep;
 		n = p1 - p0;
 		if (n >= ffline_len)
 		    expandline(n);
 		bcopy(p0, ffline, n);
 		dobrace(p1, n, 1, False);
 		return;
 	    }
 	    if (*p1 == '%' && p1[1] != '\0')
 		++p1;
 	}
 
 	/*
 	 * No braces.  Split it up into atoms (delimited by / or //).
 	 */
 
 	linkpp = &head;
 	flags = 0;
 	percent_s = False;
 	for (;;) {
 	    if (*p == '/') {
 		++p;
 		flags |= F_SLASH_SLASH;
 		/* a %[qQ] may occur following the first //. */
 		if (*p == '%')
 		    if (p[1] == 'q' || p[1] == 'Q') {
 			if (p[1] == 'Q') flags |= F_QUICKONLY;
 			flags |= F_QUICKFIND;
 			p += 2;
 		    }
 	    }
 	    p1 = p;
 	    for (;; ++p) {
 		if (*p == '\0' || IS_SEP(*p)) {
 		    p2 = NULL;
 		    if (!(sp->flags & F_FILE_USED))
 			p2 = lrec.no_f_str + 1;
 		    break;
 		}
 		if (*p == '/') {
 		    p2 = p + 1;
 		    break;
 		}
 		if (*p == '%' && p[1] != '\0' && p[1] != '/') {
 		    ++p;
 		    if (*p == 'f') sp->flags |= F_FILE_USED;
 		    else if (*p == 's' && (p[1] == '\0' || IS_SEP(p[1]))) {
 			--p;
 			percent_s = True;
 			if (lrec.v.pct_s_atom == NULL)
 			    atomize_pct_s();
 			break;
 		    }
 		}
 		else if (*p == '*' || *p == '?' || *p == '[')
 		    flags |= F_WILD;
 	    }
 	    if (p != p1) {	/* add on an atomrec */
 		struct atomrec	*atomp;
 
 		atomp = xmalloc(sizeof(struct atomrec));
 		*linkpp = atomp;
 		linkpp = &atomp->next;
 		atomp->flags = flags;
 		flags = 0;
 		atomp->p = p1;
 		atomp->p_end = p;
 	    }
 	    if (percent_s) {
 		*linkpp = (flags & F_SLASH_SLASH) ? &pct_s_dummy_slash
 		    : &pct_s_dummy;
 		sp->flags |= F_PCT_S;
 		break;
 	    }
 	    p = p2;
 	    if (p == NULL) {
 		*linkpp = NULL;
 		break;
 	    }
 	}
 	sp->atom = head;
 }
 
 /*
  *	prescan2() sets up the steprec information for a brace alternative.
  *	It also does much of the work in ff_prescan().
  */
 
 static	const	char *
 prescan2(sp, p, skip)
 	struct steprec	*sp;
 	const	char	*p;
 	Boolean		skip;		/* true if initial / does not mean // */
 {
 	int		flags;
 
 	/*
 	 * Scan the string, looking for // or wild cards or braces.
 	 * It takes the input / by / so that we can back up to the previous
 	 * slash if there is a wild card (which may be hidden in braces).
 	 */
 
 	flags = sp->flags;
 	for (;;) {	/* loop over slash-separated substrings */
 	    sp->strend = p;
 	    sp->flags = flags;
 	    while (*p == '/') {	/* check for // */
 		if (skip) {
 		    ++p;
 		    skip = False;
 		}
 		else {
 		    atomize(p, sp);
 		    return p;
 		}
 	    }
 	    for (;;) {	/* loop over characters in this subpart */
 		if (*p == '\0' || IS_SEP(*p)) {
 		    sp->strend = p;
 		    sp->flags = flags;
 		    return p;
 		}
 		if (*p == '/')
 		    break;
 		if (*p == LBRACE) {
 		    unsigned n;
 
 		    bracepp = &sp->nextstep;
 		    n = p - sp->strend;
 		    if (n >= ffline_len)
 			expandline(n);
 		    bcopy(sp->strend, ffline, n);
 		    dobrace(p, n, 1, skip);
 		    return p;
 		}
 		skip = False;
 		if (*p == '%' && p[1] != '\0') {
 		    ++p;
 		    if (*p == 's' && (p[1] == '\0' || IS_SEP(p[1]))) {
 			sp->strend = p - 1;
 			sp->flags = flags;
 			sp->nextstep = scan_pct_s();
 			return p;
 		    }
 		    else if (*p == 'f')
 			flags |= F_FILE_USED | F_VARIABLE;
 		    else if (*p == 'F' || *p == lrec.x_var_char)
 			flags |= F_VARIABLE;
 		    /* %c and %C are sorted out later. */
 		}
 		else if (*p == '*' || *p == '?' || *p == '[') {
 		    atomize(sp->strend, sp);
 		    return p;
 		}
 		++p;
 	    }
 	    ++p;
 	}
 }
 
 /*
  *	dobrace() is the recursive routine for handling {} alternatives.
  *	bracepp (global) = address of where to put next brace item on the
  *		linked list.  It has to be global because dobrace() is called
  *		recursively and leaves its droppings at varying levels.
  *	p = input string pointer; it should point to the opening brace.
  *	pos = position within ffline[] for output string.
  *	level = nesting depth.
  *
  *	skip:	true if initial / does not mean //
  */
 
 static	void
 dobrace(const char *p, unsigned pos0, int level, Boolean skip)
 {
 	int		lev;
 	int		level1;
 	const	char	*p1;
 	unsigned	pos;
 
 	for (;;) {	/* loop over the alternatives */
 	    lev = 0;
 	    ++p;	/* skip left brace or comma */
 	    pos = pos0;
 	    for (;;) {	/* loop over characters */
 		if (*p == '\0' || IS_SEP(*p)) {
 			/* keep the braces matched:  { */
 		    warnx("Missing } in '%s' path.", lrec.type);
 		    return;
 		}
 		else if (*p == '%') {
 		    if (p[1] != '\0') {
 			if (pos >= ffline_len)
 			    expandline(pos);
 			ffline[pos++] = *p++;
 		    }
 		}
 		else if (*p == LBRACE) {
 		    dobrace(p, pos, level + 1, skip && pos == pos0);
 		    /* skip to the next matching comma or right brace */
 		    for (;;) {
 			if (*p == '\0' || IS_SEP(*p))
 			    return;	/* this has already been reported */
 			else if (*p == '%') {
 			    if (p[1] != '\0') ++p;
 			}
 			else if (*p == LBRACE)
 			    ++lev;
 			else if (*p == ',') {
 			    if (lev == 0)
 				break;
 			}
 			else if (*p == RBRACE) {
 			    if (lev == 0)
 				break;
 			    --lev;
 			}
 			++p;
 		    }
 		    goto out2;
 		}
 		else if (*p == ',' || *p == RBRACE)
 		    break;
 		if (pos >= ffline_len)
 		    expandline(pos);
 		ffline[pos++] = *p++;
 	    }
 	    p1 = p;
 	    level1 = level;
 	    for (;;) {
 		/* skip until matching right brace */
 		for (;;) {
 		    if (*p1 == '\0' || IS_SEP(*p1))
 			goto out2;	/* this has already been reported */
 		    if (*p1 == '%') {
 			if (p1[1] != '\0') ++p1;
 		    }
 		    else if (*p1 == LBRACE)
 			++lev;
 		    else if (*p1 == RBRACE) {
 			if (lev == 0) {
 			    ++p1;
 			    break;
 			}
 			--lev;
 		    }
 		    ++p1;
 		}
 		--level1;
 		/* now copy until a qualifying comma */
 		for (;;) {
 		    if (*p1 == '\0' || IS_SEP(*p1)) {
 			if (level1 == 0) {
 			    struct steprec *bp;
 
 			    if (pos >= ffline_len)
 				expandline(pos);
 			    ffline[pos++] = '\0';
 			    *bracepp = bp = xmalloc(sizeof(struct steprec));
 			    bp->next = NULL;
 			    bp->atom = NULL;
 			    bp->nextstep = NULL;
 			    bracepp = &bp->next;
 			    bp->str = xmemdup(ffline, pos);
 			    bp->flags = 0;
 			    (void) prescan2(bp, bp->str, skip);
 			}
 			/* else:  this has already been reported */
 			goto out2;
 		    }
 		    if (*p1 == '%') {
 			if (p1[1] != '\0') {
 			    if (pos >= ffline_len)
 				expandline(pos);
 			    ffline[pos++] = '%';
 			    ++p1;
 			}
 		    }
 		    else if (*p1 == LBRACE) {
 			dobrace(p1, pos, level1 + 1, False);
 			goto out2;
 		    }
 		    else if (*p1 == ',' && level1 > 0)
 			break;
 		    else if (*p1 == RBRACE && level1 > 0) {
 			--level1;
 			++p1;
 			continue;
 		    }
 		    if (pos >= ffline_len)
 			expandline(pos);
 		    ffline[pos++] = *p1++;
 		}
 	    }
 	    out2:
 	    if (*p != ',') break;
 	}
 }
 
 
 /*
  *	Prescan the '%s' string.  This is done only once.
  */
 
 static	struct steprec *
 scan_pct_s()
 {
 	struct steprec	**headpp;
 	const	char	*p;
 	struct steprec	*sp;
 
 	if (lrec.v.pct_s_head != NULL)	/* if we've already done this */
 	    return lrec.v.pct_s_head;
 
 	headpp = &lrec.v.pct_s_head;
 	p = lrec.pct_s_str;
 	for (p = lrec.pct_s_str; ; ++p) {
 	    ++lrec.v.pct_s_count;
 	    *headpp = sp = xmalloc(sizeof(struct steprec));
 	    sp->atom = NULL;
 	    sp->nextstep = NULL;
 	    sp->flags = 0;
 	    sp->str = p;
 	    headpp = &sp->next;
 	    (void) prescan2(sp, p, False);
 	    for (; *p != '\0' && !IS_SEP(*p); ++p)
 		if (*p == '%' && p[1] != '\0') ++p;
 	    if (*p == '\0') break;
 	}
 	*headpp = NULL;
 	return lrec.v.pct_s_head;
 }
 
 /*
  *	Pre-atomize the '%s' strings.  Again, done only once.
  */
 
 static	void
 atomize_pct_s()
 {
 	const	struct atomrec	**app;
 	struct steprec		*sp;
 
 	(void) scan_pct_s();	/* make sure the count is valid */
 
 	app = lrec.v.pct_s_atom =
 		xmalloc((unsigned) lrec.v.pct_s_count * sizeof(*app));
 
 	for (sp = lrec.v.pct_s_head; sp != NULL; sp = sp->next, ++app) {
 	    static struct steprec dummy;
 
 	    dummy.flags = 0;
 	    atomize(sp->str, &dummy);
 	    *app = dummy.atom;
 	}
 }
 
 
 /*
  *	Init_texmf - Initialize the linked list of options for %t.
  */
 
 static	void		/* here's a small subroutine */
 add_to_texmf_list(pp)
 	const	char	**pp;
 {
 	static	struct texmfrec	**tpp	= &texmfhead;
 	struct texmfrec		*tp;
 	const	char		*p;
 	const	char		*p_end;
 	const	char		*home	= NULL;
 	int			flags	= 0;
 
 	p = *pp;
 	p_end = index(p, ':');
 	if (p_end == NULL) p_end = p + strlen(p);
 	*pp = p_end;
 
 	if (*p == '!' && p[1] == '!') {
 	    p += 2;
 	    flags = F_QUICKONLY;
 	}
 
 	if (*p == '~')
 	    gethome(&p, p_end, &home);
 
 	tp = *tpp = xmalloc(sizeof(struct texmfrec));
 	tp->home = home;
 	tp->str = p;
 	tp->len = p_end - p;
 	tp->flags = flags;
 	tp->next = NULL;
 	tpp = &tp->next;
 }
 
 static	void
 init_texmf()
 {
 	const	char		*texmf;
 	const	char		*texmf2;
 	const	struct texmfrec	*tp;
 	unsigned		n;
 
 	if (texmfhead != NULL)
 	    return;
 
 	texmf = getenv("TEXMF");
 	texmf2 = default_texmf_path;
 	if (texmf == NULL) {
 	    texmf = default_texmf_path;
 	    texmf2 = NULL;
 	}
 
 	for (;;) {
 	    if (*texmf == '\0' || *texmf == ':') {
 		if (texmf2 != NULL)
 		    for (;;) {
 			while (*texmf2 == ':') ++texmf2;
 			if (*texmf2 == '\0') break;
 			add_to_texmf_list(&texmf2);
 		    }
 	    }
 	    else
 		add_to_texmf_list(&texmf);
 	    if (*texmf == '\0')
 		break;
 	    ++texmf;
 	}
 
 	/* Make sure ffline[] is long enough for these. */
 
 	n = 0;
 	for (tp = texmfhead; tp != NULL; tp = tp->next)
 	    if (tp->len > n)
 		n = tp->len;
 
 	if (n > ffline_len)
 	    expandline(n);
 }
 
 
 /*
  *	Scan this path part.  This is done at most once.
  *	We look for // or wild cards or {}.
  */
 
 static	const	char *
 ff_prescan(p)
 	const	char	*p;
 {
 	struct steprec	*sp;
 
 	*steppp = sp = xmalloc(sizeof(struct steprec));
 	sp->next = NULL;
 	sp->flags = 0;
 	sp->atom = NULL;
 	sp->nextstep = NULL;
 
 	/*
 	 * Scan the string, looking for // or wild cards or braces.
 	 */
 
 	sp->str = p;
 	return prescan2(sp, p, True);
 }
 
 /*
  *	This routine handles the translation of the '%' modifiers.
  *	It returns the new number string length (pos).
  *	It makes sure that at least one free byte remains in ffline[].
  */
 
 static	unsigned
 xlat(stat_in, stat_ret, pos0, p, lastp)
 	const	struct statrec	*stat_in;
 	struct statrec		*stat_ret;
 	unsigned		pos0;
 	const	char		*p;
 	const	char		*lastp;
 {
 	struct statrec		status;
 	const	char		*q;
 	int			l;
 
 	status.pos = pos0;
 	if (stat_ret != NULL)
 	    status = *stat_in;
 
 	while (p < lastp) {
 	    q = memchr(p, '%', lastp - p);
 	    l = (q != NULL ? q : lastp) - p;
 	    if (status.pos + l >= ffline_len)
 		expandline(status.pos + l);
 	    bcopy(p, ffline + status.pos, l);
 	    status.pos += l;
 	    p = q;
 	    if (p == NULL) break;
 	    do {
 		++p;
 		if (p >= lastp) break;
 		q = index(lrec.fF_etc, *p);
 		if (q != NULL) {
 		    const char *str = fF_values[q - lrec.fF_etc];
 
 		    if (str != NULL) {
 			l = strlen(str);
 			if (status.pos + l >= ffline_len)
 			    expandline(status.pos + l);
 			bcopy(str, ffline + status.pos, l);
 			status.pos += l;
 		    }
 		    else {	/* eliminate a possible double slash */
 			if (p[1] == '/' && (status.pos == 0
 				|| ffline[status.pos - 1] == '/'))
 			    --status.pos;
 		    }
 		}
 		else if (*p == 'q' || *p == 'Q') {
 		    status.quickchar = *p;
 		    status.quickpos = status.pos;
 		}
 		else {
 		    if (status.pos + 1 >= ffline_len)
 			expandline(ffline_len);
 		    ffline[status.pos++] = *p;
 		}
 		++p;
 	    }
 	    while (p < lastp && *p == '%');
 	}
 
 	if (stat_ret != NULL)
 	    *stat_ret = status;
 	return status.pos;
 }
 
 
 /*
  *	Try to open the file.  Exit via longjmp() if success.
  */
 static	void
 try_to_open(unsigned pos, int flags)
 {
 	ffline[pos] = '\0';
 
 	if (FFDEBUG)
 	    printf("Trying %s file %s\n", lrec.type, ffline);
 
 	file_found = xfopen(ffline, "r");
 	if (file_found != NULL)
 	    longjmp(got_it, 1);
 }
 
 
 /*
  *	lsrgetline - Read a line from the (ls-R) file and return:
  *		minus its length if it ends in a colon (including the colon);
  *		its length	 otherwise;
  *		zero		 for end of file.
  *	Blank lines are skipped.
  */
 
 static	int
 lsrgetline(f, pos0)
 	FILE		*f;	/* ls-R file */
 	unsigned	pos0;	/* relative position in line to start reading */
 {
 	unsigned	pos	= pos0;
 
 	for (;;) {
 	    if (pos + 4 >= ffline_len)
 		expandline(pos);
 	    if (fgets(ffline + pos, ffline_len - pos, f) == NULL)
 		break;
 	    pos += strlen(ffline + pos);
 	    if (pos > pos0 && ffline[pos - 1] == '\n') {
 		--pos;		/* trim newline */
 		if (pos > pos0) break;	/* if ffline still nonempty */
 	    }
 	}
 	if (pos > pos0 && ffline[pos - 1] == ':') {
 	    ffline[pos - 1] = '/';	/* change trailing colon to slash */
 	    return pos0 - pos;
 	}
 	else
 	    return pos - pos0;
 }
 
 
 /*
  *	lsrput - Put a key/value pair into the ls-R database.
  */
 
 static	void
 lsrput(key, keylen, value)
 	const	char	*key;
 	unsigned	keylen;
 	const	char	*value;
 {
 	struct lsr	**lpp;
 	struct lsr	*lp;
 
 #if 0
 	fputs("lsrput:  key = `", stdout);
 	fwrite(key, 1, keylen, stdout);
 	printf("'; value = `%s'.\n", value);
 #endif
 
 	    /* make the new record */
 	lp = xmalloc(sizeof(*lp));
 	lp->next = NULL;
 	lp->frecp = frecp;
 	lp->seqno = seqno;
 	lp->keylen = keylen;
 	lp->key = xmemdup(key, keylen);
 	lp->value = value;
 
 	    /* insert it */
 	lpp = lsrtab + prehash(key, keylen) % XtNumber(lsrtab);
 	while (*lpp != NULL)	/* skip to end of chain (performance reasons) */
 	    lpp = &(*lpp)->next;
 	*lpp = lp;
 }
 
 
 /*
  *	init_quick_find - Read ls-R database for this particular search.
  */
 
 static	void
 init_quick_find(root, pos, atom, pos1)
 	struct rootrec		*root;	/* pointer to the governing rootrec */
 	unsigned		pos;	/* position of %[qQ] in ffline[] */
 	const	struct atomrec	*atom;	/* the beginning of the atomlist */
 	unsigned		pos1;	/* next free byte in ffline[] */
 {
 #define	LS_R_LEN	5		/* length of the string "ls-R\0" */
 	char		tmpsav[LS_R_LEN];
 	int		keypos;		/* position of start of key pattern */
 	int		keyend;		/* last + 1 character of the key */
 	int		keypos_a;	/* position + 1 of last slash */
 	unsigned	pos2;		/* end + 1 of the decoded thing */
 	int		nslashes;	/* how many slashes in bbbcccddd */
 	FILE		*f;		/* ls-R file */
 	const	char	*fullpat;	/* fields in *root */
 	const	char	*keypat;	/* " */
 	const	char	*keypat_end;	/* " */
 	const	char	*fullpat_end;	/* " */
 	const	char	*keypat_a;	/* position of end+1 of restricted
 					 * initial fixed part */
 	int		retval;		/* return value of lsrgetline */
 
 	/*
 	 *	Reencode the string of atoms into a character string
 	 *	When we're done, ffline[] contains:
 	 *	/aa/aa/a...a/ bbb/bb...bb/bbb %f/cc/c...c/%d ddd/ddd/.../ddd
 	 *
 	 *	where the aaa part is what's already in ffline[], and
 	 *	the rest is the decoded atom chain.  The ccc part of this
 	 *	string contains all the variable specifiers (not replaced by
 	 *	anything), and the bbb and ddd parts are character strings that
 	 *	should occur verbatim in the file name.
 	 */
 
 	root->flags &= ~F_QUICKFIND;	/* clear it for now; set it later */
 
 	if (atom->flags & F_PCT_S)
 	    atom = treeatom;
 
 	if (atom->flags & F_WILD) return;	/* not allowed */
 
 	pos2 = pos1;
 	keypos = -1;
 	nslashes = 0;
 
 	for (;;) {
 	    const char *p;
 
 	    keypos_a = pos2;
 		/* translate the atom, leaving %f and maybe %d alone */
 	    for (p = atom->p; p < atom->p_end; ++p) {
 		if (p >= atom->p_end) break;
 		if (*p == '%') {
 		    const char *q;
 
 		    ++p;
 		    if (p >= atom->p_end) break;
 		    q = index(lrec.fF_etc, *p);
 		    if (q != NULL) {
 			if (q - lrec.fF_etc < lrec.n_var_opts) {
 			    /* it's a variable specifier (%f or ...) */
 			    --p;	/* copy it over */
 			    if (keypos < 0) keypos = pos2;
 			    keyend = pos2 + 2;
 			}
 			else {
 			    const char *str	= fF_values[q - lrec.fF_etc];
 
 			    if (str != NULL) {
 				int	l	= strlen(str);
 
 				if (pos2 + l >= ffline_len)
 				    expandline(pos2 + l);
 				bcopy(str, ffline + pos2, l);
 				pos2 += l;
 			    }
 			    continue;
 			}
 		    }
 		}
 		if (pos2 + 1 >= ffline_len)
 		    expandline(pos2);
 		ffline[pos2++] = *p;
 	    }
 
 	    atom = atom->next;
 	    if (atom == NULL) break;
 
 	    if (atom->flags & F_PCT_S) atom = treeatom;
 	    if (atom->flags & (F_SLASH_SLASH | F_WILD))
 		return;		/* not supported */
 
 	    if (pos2 == keypos_a) continue;	/* if /%m/ with no mode */
 	    ffline[pos2++] = '/';
 	    ++nslashes;
 	}
 
 	if (keypos_a > keypos) keypos_a = keypos;
 
 	root->flags |= F_QUICKFIND;	/* it's eligible */
 
 	if (FFDEBUG) {
 #define	DDD(a,b,c)	\
 		fputs(a, stdout); \
 		fwrite(ffline + (b), 1, (c) - (b), stdout); \
 		puts("'");
 
 	    DDD("\nReading ls-R.\nOriginal string = `", 0, pos1);
 	    DDD("Restricted initial fixed part = `", pos1, keypos_a);
 	    DDD("Initial fixed part = `", pos1, keypos);
 	    DDD("Key pattern = `", keypos, keyend);
 	    DDD("Final fixed part = `", keyend, pos2);
 #undef	DDD
 	}
 
 	/*
 	 * Open ls-R and start reading it.
 	 */
 
 	bcopy(ffline + pos, tmpsav, sizeof(tmpsav));
 	bcopy("ls-R", ffline + pos, sizeof(tmpsav));
 	if (FFDEBUG) printf("Opening ls-R file %s\n", ffline);
 	f = xfopen(ffline, "r");
 	bcopy(tmpsav, ffline + pos, sizeof(tmpsav));
 	if (f == NULL) {
 	    if (FFDEBUG) printf("xfopen: %s\n", strerror(errno));
 	    return;
 	}
 
 	fullpat = xmemdup(ffline + pos1, pos2 - pos1);
 	keypat = fullpat + (keypos - pos1);
 	keypat_a = fullpat + (keypos_a - pos1);
 	keypat_end = fullpat + (keyend - pos1);
 	fullpat_end = fullpat + (pos2 - pos1);
 
 	do {			/* skip initial comment lines */
 	    retval = lsrgetline(f, pos1);
 	    if (retval == 0) {
 		fclose(f);
 		return;		/* premature end of file */
 	    }
 	} while (ffline[pos1] == '%');
 
 	/* First take care of file names without a directory: these are
 	 * those in the same directory as the ls-R file */
 
 	while (retval > 0) {
 	    if (nslashes == 0	/* if there are no slashes in the pattern */
 				/* and if ls-R is in the same directory
 				 * as the //: */
 		    && pos1 == pos
 				/* and if the initial fixed part matches: */
 		    && memcmp(ffline + pos1, fullpat, keypat - fullpat) == 0
 				/* and if the final fixed part matches: */
 		    && memcmp(ffline + pos1 + retval
 				- (fullpat_end - keypat_end),
 				keypat_end, fullpat_end - keypat_end) == 0)
 				/* then create a directory entry */
 		lsrput(ffline + pos1 + (keypat - fullpat),
 		  retval - (keypat - fullpat) - (fullpat_end - keypat_end), "");
 	    retval = lsrgetline(f, pos1);	/* read next line */
 	}
 
 	/*
 	 * Now do whole directories.
 	 */
 
 	for (;;) {
 	    int		i;
 	    const char *p;
 	    const char *p_begin;
 	    const char *p_end;
 	    unsigned	pos3;
 	    unsigned	pos4;
 	    unsigned	pos5;
 	    unsigned	retpos;
 	    char	*value;
 
 	    while (retval > 0)		/* skip to next directory */
 		retval = lsrgetline(f, pos1);
 	    if (retval == 0) break;	/* if end of file */
 	    retval = -retval;		/* length of the string */
 	    /* also, retval is now > 0, so a continue statement won't lead to
 	     * an infinite loop. */
 	    retpos = pos1 + retval;
 	    if (ffline[pos1] == '/') {	/* if absolute path */
 			/* these should be referring to the same directory */
 		if (retval < pos1 || memcmp(ffline + pos1, ffline, pos1) != 0)
 		    continue;
 		pos2 = pos1 + pos1;
 	    }
 	    else {		/* relative path */
 		pos2 = pos1;
 		if (retval >= 2 && ffline[pos1] == '.'
 		  && ffline[pos1 + 1] == '/')
 		    pos2 += 2;	/* eliminate "./" */
 			/* these should be referring to the same directory */
 		if (retpos - pos2 < pos1 - pos
 			|| memcmp(ffline + pos2, ffline + pos, pos1 - pos) != 0)
 		    continue;
 		pos2 += pos1 - pos;
 	    }
 	    /* now pos2 points to what should follow the // */
 	    /* count backwards from the end of the string to just after the
 	       (nslashes + 1)-st slash */
 	    p_begin = ffline + pos2;
 	    p_end = ffline + retpos;
 	    i = nslashes;
 	    for (p = p_end; p > p_begin; )
 		if (*--p == '/') {
 		    if (i == 0) {
 			++p;
 			break;
 		    }
 		    else --i;
 		}
 	    if (i > 0) continue;	/* if too few slashes */
 	    pos3 = p - ffline;
 	    /* the next part of the directory name should match the initial
 	       fixed part of the pattern */
 	    if (p_end - p < keypat_a - fullpat
 	      || memcmp(p, fullpat, keypat_a - fullpat) != 0)
 		continue;
 	    pos4 = pos3 + (keypat - fullpat);	/* start of key */
 	    value = NULL;
 	    for (;;) {		/* read the files in this directory */
 		retval = lsrgetline(f, retpos);
 		if (retval <= 0) {	/* if done with list*/
 		    bcopy(ffline + retpos, ffline + pos1, -retval);
 		    break;
 		}
 		    /* check the remaining part of the initial fixed part */
 		    /* (the first test is only for performance) */
 		if (keypat_a != keypat
 		  && memcmp(ffline + retpos, keypat_a, keypat - keypat_a) != 0)
 		    continue;
 		    /* end of key */
 		pos5 = retpos + retval - (fullpat_end - keypat_end);
 		    /* check the final fixed part */
 		if (pos5 < pos4 || (fullpat_end != keypat_end
 			&& memcmp(ffline + pos5, keypat_end,
 			fullpat_end - keypat_end) != 0))
 		    continue;
 		if (value == NULL) {
 		    value = xmemdup(ffline + pos2, pos3 - pos2 + 1);
 		    value[pos3 - pos2] = '\0';
 		}
 		lsrput(ffline + pos4, pos5 - pos4, value);
 	    }
 	}
 
 	fclose(f);	/* close the file */
 
 	    /* Fill in the requisite entries in *root:  we have ls-R. */
 	root->fullpat = fullpat;
 	root->fullpat_end = fullpat_end;
 	root->keypat = keypat;
 	root->keypat_end = keypat_end;
 }
 
 /*
  *	wildmatch - Tell whether the string matches the pattern.
  *
  *		pat		pointer to first character of pattern
  *		pat_end		pointer to last + 1 character of pattern
  *		candidate	the string
  *		allowvar	how many characters of fF_etc should be treated
  *				as *
  */
 
 static	Boolean
 wildmatch(pat, pat_end, candidate, allowvar)
 	const	char	*pat;
 	const	char	*pat_end;
 	const	char	*candidate;
 	int		allowvar;	/* How many of %f, %F, %d, ... to */
 					/* treat as '*' */
 {
 	const	char	*p;
 	const	char	*q	= candidate;
 
 	for (p = pat; p < pat_end; ++p)
 	    switch (*p) {
 
 		case '%': {
 		    const char *q1;
 
 		    if (p + 1 >= pat_end) continue;
 		    ++p;
 		    q1 = index(lrec.fF_etc, *p);
 		    if (q1 == NULL) {		/* %[ or something */
 			if (*q != *p)
 			    return False;
 			++q;
 			break;
 		    }
 
 		    if (q1 - lrec.fF_etc < allowvar) {	/* treat it as '*' */
 			for (q1 = q + strlen(q); q1 >= q; --q1)
 			    if (wildmatch(p + 1, pat_end, q1, allowvar))
 				return True;
 			return False;
 		    }
 		    else {
 			const char	*str	= fF_values[q1 - lrec.fF_etc];
 			int		l;
 
 			if (str == NULL) str = "";
 			l = strlen(str);
 			if (bcmp(q, str, l) != 0)
 			    return False;
 			q += l;
 		    }
 		    break;
 		}
 
 		case '*': {
 		    const char *q1;
 
 		    for (q1 = q + strlen(q); q1 >= q; --q1)
 			if (wildmatch(p + 1, pat_end, q1, allowvar))
 			    return True;
 		    return False;
 		}
 
 		case '?':
 		    if (*q == '\0')
 			return False;
 		    ++q;
 		    break;
 
 		case '[': {
 		    char c;
 		    Boolean reverse = False;
 
 		    c = *q++;
 		    if (c == '\0')
 			return False;
 
 		    ++p;
 		    if (*p == '^') {
 			reverse = True;
 			++p;
 		    }
 
 		    for (;;) {
 			char	c1;
 			char	c2;
 
 			if (p >= pat_end)
 			    return False;	/* syntax error */
 			c1 = *p;
 			if (c1 == ']') {
 			    if (reverse)
 				break;		/* success */
 			    else
 				return False;
 			}
 			c2 = c1;
 			++p;
 			if (*p == '-' && p[1] != ']') {
 			    ++p;
 			    c2 = *p++;
 			    if (c2 == '%') c2 = *p++;
 			}
 			if (p >= pat_end)
 			    return False;	/* syntax error */
 			if (c >= c1 && c <= c2) {
 			    if (reverse)
 				return False;
 			    else {		/* success */
 				while (*p != ']') {
 				    if (*p == '%') ++p;
 				    ++p;
 				    if (p >= pat_end)
 					return False;	/* syntax error */
 				}
 				break;
 			    }
 			}
 		    }
 		    break;
 		}
 
 		default:
 		    if (*q != *p)
 			return False;
 		    ++q;
 	    }
 
 	if (*q != '\0')
 	    return False;
 	return True;
 }
 
 
 /*
  *	Read in the given directory.
  */
 
 static	void
 filltree(pos, treepp, atom, slashslash)
 	unsigned	pos;
 	struct treerec	**treepp;
 	const struct atomrec	*atom;
 	Boolean		slashslash;
 {
 	DIR		*f;
 	struct dirent	*dp;
 
 	if (pos == 0) {
 	    if (ffline_len == 0)
 		expandline(2);
 	    ffline[0] = '.';
 	    ffline[1] = '\0';
 	}
 	else
 	    ffline[pos - 1] = '\0';
 
 	if (FFDEBUG)
 	    printf("Opening directory %s\n", ffline);
 
 	f = opendir(ffline);
 	if (f == NULL) {
 	    if (FFDEBUG) printf("%s: %s\n", ffline, strerror(errno));
 	    *treepp = NULL;
 	    return;
 	}
 
 	if (pos != 0) ffline[pos - 1] = '/';
 	for (;;) {
 	    char		*line1;
 	    struct stat		statbuf;
 	    struct treerec	*leaf;
 	    Boolean		isdir;
 	    unsigned		len;
 #if	ST_NLINK_TRICK
 	    struct treerec	*child;
 #endif
 
 	    dp = readdir(f);
 	    if (dp == NULL) break;	/* done */
 
 	    len = strlen((dp)->d_name);
 	    if (pos + len >= ffline_len)
 		expandline(pos + (int) len);
 	    line1 = ffline + pos;
 	    bcopy(dp->d_name, line1, len);
 	    line1[len] = '\0';
 	    if (*line1 == '.' && (line1[1] == '\0'
 		    || (line1[1] == '.' && line1[2] == '\0')))
 		continue;	/* skip . and .. */
 
 	    if (lstat(ffline, &statbuf) != 0) {
 		warn("lstat: filltree ffline");
 		continue;
 	    }
 	    isdir = False;
 #if	ST_NLINK_TRICK
 	    child = &not_read_yet;
 #endif
 	    if (S_ISDIR(statbuf.st_mode)) {
 		isdir = True;
 		if (!slashslash
 			&& (atom->next == NULL
 			|| !wildmatch(atom->p, atom->p_end, line1,
 				lrec.n_var_opts)))
 		    continue;
 #if	ST_NLINK_TRICK
 		if (statbuf.st_nlink <= 2)
 		    child = NULL;
 #endif
 	    }
 	    else if (S_ISREG(statbuf.st_mode)) {
 		if (atom->next != NULL
 			|| (slashslash && !(atom->flags & F_WILD))
 			|| !wildmatch(atom->p, atom->p_end, line1,
 				lrec.n_var_opts))
 		    continue;
 	    }
 	    else continue;	/* something else */
 
 	    leaf = xmalloc(sizeof(struct treerec));
 	    {
 		char	*str;
 
 		str = xmemdup(dp->d_name, (unsigned) len + 1);
 		str[len] = '\0';
 		leaf->dirname = str;
 	    }
 #if	ST_NLINK_TRICK
 	    leaf->child = child;
 #else
 	    leaf->child = &not_read_yet;
 #endif
 	    leaf->isdir = isdir;
 	    *treepp = leaf;
 	    treepp = &leaf->next;
 	}
 	closedir(f);
 
 	*treepp = NULL;
 }
 
 
 /*
  *	do_tree_search() - recursive routine for // and wild card searches.
  */
 
 static	void
 do_tree_search(treepp, atom, goback, pos, flags)
 	struct treerec		**treepp;
 	const	struct atomrec	*atom;
 	const	struct atomrec	*goback;
 	unsigned		pos;
 	int			flags;
 {
 	int		aflags;
 	struct treerec	*tp;
 
 	/*
 	 * If we're at the end of the chain of atoms, try to open the file.
 	 */
 
 	if (atom == NULL) {
 	    try_to_open(pos - 1, flags);
 	    return;
 	}
 
 	/*
 	 * Otherwise, we're still forming the path.
 	 */
 
 	aflags = atom->flags;
 	if (aflags & F_PCT_S) {		/* if it's a dummy record */
 	    atom = treeatom;
 	    aflags |= atom->flags;
 	}
 
 	if (aflags & F_SLASH_SLASH)
 	    goback = atom;
 
 	if (goback == NULL) {		/* wild card search, no // yet */
 	    /*
 	     * If the next atom is neither wild nor variable, then we don't
 	     * need to do a readdir() on the directory.  Just add the
 	     * appropriate characters to the path and recurse.
 	     */
 	    if (!(atom->flags & (F_WILD | F_VARIABLE))) {
 		pos = xlat(NULL, NULL, pos, atom->p, atom->p_end);
 		ffline[pos++] = '/';
 		do_tree_search(treepp, atom->next, goback, pos,
 		    flags | atom->flags);
 		return;
 	    }
 	    /*
 	     * Otherwise, go down one level in the tree.
 	     */
 	    if (*treepp == &not_read_yet)	/* if readdir() not done yet */
 		filltree(pos, treepp, atom, False);	/* do it */
 
 	    for (tp = *treepp; tp != NULL; tp = tp->next)
 		if (wildmatch(atom->p, atom->p_end, tp->dirname, 0)) {
 		    int len = strlen(tp->dirname);
 		    bcopy(tp->dirname, ffline + pos, len);
 		    ffline[pos + len++] = '/';
 		    do_tree_search(&tp->child, atom->next, goback, pos + len,
 			flags | atom->flags);
 		}
 
 	    return;
 	}
 
 	/*
 	 * If we got here, then we're past a //
 	 */
 
 	if (atom->next == NULL && !(atom->flags & F_WILD))
 		/* if we can try a file */
 	    try_to_open(xlat(NULL, NULL, pos, atom->p, atom->p_end),
 		flags | atom->flags);
 
 	if (*treepp == &not_read_yet)		/* if readdir() not done yet */
 	    filltree(pos, treepp, atom, True);	/* do it */
 
 	for (tp = *treepp; tp != NULL; tp = tp->next) {
 	    tp->tried_already = False;
 	    if ((atom->next != NULL || (atom->flags & F_WILD))
 		    && wildmatch(atom->p, atom->p_end, tp->dirname, 0)) {
 		int len = strlen(tp->dirname);
 		bcopy(tp->dirname, ffline + pos, len);
 		ffline[pos + len++] = '/';
 		do_tree_search(&tp->child, atom->next, goback, pos + len,
 		    flags | atom->flags);
 		tp->tried_already = True;
 	    }
 	}
 
 	for (tp = *treepp; tp != NULL; tp = tp->next)
 	    if (!tp->tried_already && tp->isdir) {
 		int len = strlen(tp->dirname);
 		bcopy(tp->dirname, ffline + pos, len);
 		ffline[pos + len++] = '/';
 		do_tree_search(&tp->child, goback, goback, pos + len, flags);
 	    }
 }
 
 
 /*
  *	begin_tree_search() - start a wild card or // search.
  */
 
 static	void
 begin_tree_search(status, oneatom, twoatom)
 	const	struct statrec	*status;
 	const	struct atomrec	*oneatom;	/* initial atom */
 	const	struct atomrec	*twoatom;	/* if F_PCT_S set */
 {
 	struct treerec		**tpp;
 
 #if 0
 	{
 	    const struct atomrec	*atom;
 
 	    puts("begin_tree_search():");
 	    fwrite(ffline, 1, status->pos, stdout);
 	    putchar('\n');
 	    atom = oneatom;
 	    for (;;) {
 		fputs("+ ", stdout);
 		if (atom->flags & F_SLASH_SLASH) fputs("(//) ", stdout);
 		if (atom->flags & F_PCT_S) atom = twoatom;
 		fwrite(atom->p, 1, atom->p_end - atom->p, stdout);
 		if (atom->flags & F_WILD) fputs(" (wild)", stdout);
 		putchar('\n');
 		atom = atom->next;
 		if (atom == NULL) break;
 	    }
 	    putchar('\n');
 	}
 #endif
 
 	++seqno;
 	treeatom = twoatom;		/* save this globally */
 
 	/*
 	 * Find the record controlling this mess.  Create one, if necessary.
 	 */
 
 	if (status->flags & F_VARIABLE) {
 	    struct vrootrec {
 		struct rootrec	*next;	/* link to next in hash chain */
 		struct treerec	*tree;	/* the tree */
 		const char	*path;
 		int		seqno;
 	    };
 	    struct rtab {
 		struct rtab	*next;
 		int		seqno;
 		int		len;
 		const char	*tag;
 		struct vrootrec	*r;
 	    };
 	    static struct rtab	*varroot[32];
 	    struct rtab		**tpp2;
 	    struct rtab		*t;
 	    struct vrootrec	*r;
 
 	    tpp2 = varroot + prehash(ffline, status->pos) % XtNumber(varroot);
 	    for (;;) {
 		t = *tpp2;
 		if (t == NULL) {
 		    t = xmalloc(sizeof(*t));
 		    t->seqno = seqno;
 		    t->len = status->pos;
 		    t->tag = xmemdup(ffline, status->pos);
 		    r = xmalloc(sizeof(*r));
 		    r->next = NULL;
 		    r->tree = &not_read_yet;	/* readdir() not done yet */
 		    t->r = r;
 		    t->next = NULL;
 		    *tpp2 = t;
 		    break;
 		}
 		if (t->seqno == seqno && t->len == status->pos
 			&& memcmp(t->tag, ffline, t->len) == 0) {
 		    r = t->r;
 		    break;
 		}
 		tpp2 = &t->next;
 	    }
 	    tpp = &r->tree;
 	}
 	else {
 	    struct rootrec *r;
 
 	    r = *rootpp;
 	    if (r == NULL) {
 		r = xmalloc(sizeof(*r));
 		r->next = NULL;
 		r->tree = &not_read_yet;	/* readdir() not done yet */
 		r->fullpat = NULL;		/* no ls-R yet */
 		*rootpp = r;
 		r->flags = status->flags |
 		    ((oneatom->flags & F_PCT_S) ? twoatom : oneatom) ->flags;
 		if (r->flags & F_QUICKFIND)
 		    init_quick_find(r, status->pos, oneatom, status->pos);
 		else if (status->quickchar != '\0') {
 		    r->flags |= (status->quickchar == 'Q' ? F_QUICKONLY : 0);
 		    /* (init_quick_find() will set F_QUICKFIND in r->flags) */
 		    init_quick_find(r, status->quickpos, oneatom, status->pos);
 		}
 	    }
 	    rootpp = &r->next;
 	    tpp = &r->tree;
 		/* do ls-R search, if appropriate */
 	    if ((r->flags & F_QUICKFIND) && r->fullpat != NULL) {
 		unsigned	pos;
 		struct lsr	*lp;
 
 		pos = xlat(NULL, NULL, status->pos, r->keypat, r->keypat_end);
 		lp = lsrtab[prehash(ffline + status->pos, pos - status->pos)
 		    % XtNumber(lsrtab)];
 		for (;;) {
 		    if (lp == NULL) break;	/* no match */
 		    if (lp->frecp == frecp && lp->seqno == seqno
 		      && lp->keylen == pos - status->pos
 		      && memcmp(lp->key, ffline + status->pos, lp->keylen) == 0)
 		      {		/* if match */
 			struct statrec	stat1;
 			int		len = strlen(lp->value);
 
 			stat1 = *status;
 			if (stat1.pos + len > ffline_len)
 			    expandline(stat1.pos + len);
 			bcopy(lp->value, ffline + stat1.pos, len);
 			stat1.pos += len;
 			(void) xlat(&stat1, &stat1, 0,
 			  r->fullpat, r->fullpat_end);
 			try_to_open(stat1.pos, stat1.flags);
 			return;
 		    }
 		    lp = lp->next;
 		}
 		    /* if there's an ls-R database, and our file is not there,
 		     * then we don't look recursively this time. */
 		return;
 	    }
 	    if ((r->flags & (F_QUICKFIND | F_QUICKONLY))
 		    == (F_QUICKFIND | F_QUICKONLY)) {
 		return;
 	    }
 	}
 
 	do_tree_search(tpp, oneatom, NULL, status->pos, status->flags);
 }
 
 
 /*
  *	dostep() - Process a steprec record.
  */
 
 static	void
 dostep(sp, stat0)
 	const	struct steprec	*sp;
 	const	struct statrec	*stat0;
 {
 	struct statrec		status;
 
 	(void) xlat(stat0, &status, 0, sp->str, sp->strend);
 
 	status.flags |= sp->flags;
 
 	if (sp->atom != NULL) {		/* if wild cards or // */
 	    if (sp->flags & F_PCT_S) {
 		int	i;
 
 		for (i = 0; i < lrec.v.pct_s_count; ++i)
 		    begin_tree_search(&status, sp->atom, lrec.v.pct_s_atom[i]);
 	    }
 	    else
 		begin_tree_search(&status, sp->atom, NULL);
 	}
 	else if (sp->nextstep != NULL) {	/* if {} list */
 	    struct steprec *sp1;
 
 	    for (sp1 = sp->nextstep; sp1 != NULL; sp1 = sp1->next)
 		dostep(sp1, &status);
 	}
 	else {	/* end of string */
 	    if (!(status.flags & F_FILE_USED)) {
 		(void) xlat(&status, &status, 0,
 		  lrec.no_f_str, lrec.no_f_str_end);
 	    }
 	    try_to_open(status.pos, status.flags);
 	}
 }
 
 
 /*
  *	fixbegin() - Handle !!, %t, %S, and ~ at the beginning of a specifier.
  */
 
 static	void
 fixbegin(sp)
 	struct steprec	*sp;
 {
 	const	char	*p	= sp->str;
 
 	/*
 	 * Initial !!.
 	 */
 
 	if (*p == '!' && p[1] == '!' && sp->strend >= p + 2) {
 	    sp->flags |= F_QUICKONLY;
 	    p += 2;
 	}
 
 	/*
 	 * Take care of %S, %t, and ~.
 	 */
 
 	sp->home = NULL;
 
 	if (*p == '%') {
 	    if (p[1] == 'S' && sp->strend == p + 2 && sp->atom == NULL
 	      && sp->nextstep == NULL) {	/* %S */
 		init_texmf();
 		sp->flags |= F_PCT_T;
 		p = "/";
 		sp->strend = p + 1;
 		sp->nextstep = scan_pct_s();
 	    }
 	    if (p[1] == 't' && sp->strend >= p + 2) {	/* %t */
 		init_texmf();
 		sp->flags |= F_PCT_T;
 		p += 2;
 	    }
 	}
 	else if (*p == '~')
 	    gethome(&p, sp->strend, &sp->home);
 
 	sp->str = p;
 }
 
 
 /*
  *	pathpart() - Handle one (colon-separated) part of the search path.
  */
 
 static	const	char *
 pathpart(p)
 	const	char	*p;
 {
 	struct steprec			*sp;
 	static	const	struct statrec	stat_ini	= {0, 0, '\0', 0};
 	struct statrec			status;
 
 	sp = *steppp;
 	if (sp == NULL) {	/* do prescanning (lazy evaluation) */
 	    const char *p_end;
 	    p_end = ff_prescan(p);
 		/* skip to next colon or end of string */
 	    for (; *p_end != '\0' && *p_end != ':'; ++p_end)
 		if (*p_end == '%' && p_end[1] != '\0')
 		    ++p_end;
 
 	    sp = *steppp;
 	    if (sp->str == sp->strend && sp->nextstep != NULL) {
 		/* If it's braces right off the bat, then pretend these are */
 		/* all different specifiers (so %t, %S, !!, and ~ can work). */
 		/* There's a memory leak here, but it's bounded. */
 		struct steprec	*sp1	= sp->nextstep;
 
 		for (;;) {
 		    fixbegin(sp1);
 		    if (sp1->next == NULL) {
 			sp1->nextpart = p_end;
 			break;
 		    }
 		    sp1->nextpart = p;
 		    sp1 = sp1->next;
 		}
 		*steppp = sp = sp->nextstep;	/* relink the chain */
 	    }
 	    else {
 		fixbegin(sp);
 		sp->nextpart = p_end;
 	    }
 	}
 	steppp = &sp->next;
 
 	if (sp->flags & F_PCT_T) {
 	    struct texmfrec	*tp;
 
 	    for (tp = texmfhead; tp != NULL; tp = tp->next) {
 		status = stat_ini;
 		status.flags = tp->flags;
 		if (tp->home != NULL) {
 		    status.pos = strlen(tp->home);
 		    if (status.pos + tp->len >= ffline_len)
 			expandline(status.pos + tp->len);
 		    bcopy(tp->home, ffline, status.pos);
 		}
 		bcopy(tp->str, ffline + status.pos, tp->len);
 		status.pos += tp->len;
 		dostep(sp, &status);
 	    }
 	}
 	else {
 	    status = stat_ini;
 	    if (sp->home != NULL) {
 		unsigned len = strlen(sp->home);
 
 		if (len >= ffline_len)
 		    expandline(len);
 		bcopy(sp->home, ffline, len);
 		status.pos = len;
 	    }
 	    dostep(sp, &status);
 	}
 
 	return sp->nextpart;
 }
 
 #if FFDUMP
 
 /*
  *	Debugging routine.  Dump those crazy step records.
  */
 
 static	void
 dumpsteps(sp, indent)
 	const struct steprec	*sp;
 	int			indent;
 {
 	const struct steprec	*sp1;
 	int			i;
 
 	while (sp != NULL) {
 	    for (i = 0; i < indent; ++i) putchar(' ');
 	    printf("%04o `", sp->flags);
 	    fwrite(sp->str, 1, sp->strend - sp->str, stdout);
 	    puts("'");
 
 	    if (sp->home != NULL) {
 		for (i = 0; i < indent; ++i) putchar(' ');
 		printf("      Home = %s\n", sp->home);
 	    }
 
 	    /* there's an atomrec dumper in begin_tree_search() */
 
 	    dumpsteps(sp->nextstep, indent + 2);
 
 	    sp = sp->next;
 	}
 }
 
 #endif
 
 
 /*
  *	This is the main search routine.  It calls pathpath() for each
  *	component of the path.  Substitution for the default path is done here.
  */
 
 FILE *
 filefind(name, srchtype, path_ret)
 	const	char	*name;		/* name of the font or file */
 	struct findrec	*srchtype;	/* what type of search to perform */
 	const	char	**path_ret;	/* put the name of the file here */
 {
 	lrec = *srchtype;
 	fF_values[0] = fF_values[1] = name;
 
 	if (setjmp(got_it) == 0) {
 	    if (*name == '/' || *name == '~') {		/* if absolute path */
 		unsigned		pos;
 		unsigned		pos0	= 0;
 		const struct passwd	*pw	= NULL;
 
 		if (*name == '~')
 		    pw = ff_getpw(&name, name + strlen(name));
 		if (pw != NULL) {
 		    pos0 = strlen(pw->pw_dir);
 		    if (pos0 >= ffline_len)
 			expandline(pos0);
 		    bcopy(pw->pw_dir, ffline, pos0);
 		    fF_values[0] = fF_values[1] = name;
 		}
 		pos = xlat(NULL, NULL, pos0, lrec.abs_str,
 			lrec.abs_str + strlen(lrec.abs_str));
 		try_to_open(pos, 0);
 	    }
 	    else {
 		const char	*p;
 
 		steppp = &lrec.v.stephead;
 		frecp = srchtype;
 		seqno = 0;
 		rootpp = &lrec.v.rootp;
 
 		for (p = lrec.path1;;) {
 		    if (*p == '\0' || *p == ':') {
 			    /* bring in the default path */
 			if (lrec.path2 != NULL) {
 			    const char	*p1	= lrec.path2;
 
 			    for (;;) {
 				if (*p1 == '\0') break;
 				if (*p1 == ':') continue;
 				p1 = pathpart(p1);
 				if (*p1 == '\0') break;
 				++p1;	/* skip the colon */
 			    }
 			}
 		    }
 		    else
 			p = pathpart(p);
 		    if (*p == '\0') break;
 		    ++p;	/* skip the colon */
 		}
 
 		file_found = NULL;
 	    }
 	}
 	else {
 	    /* it longjmp()s here when it finds the file */
 	    if (FFDEBUG) puts("--Success--\n");
 	    if (path_ret != NULL)
 		*path_ret = xstrdup(ffline);
 	}
 
 	srchtype->v = lrec.v;	/* restore volatile parameters of *srchtype */
 
 #if FFDUMP
 	dumpsteps(srchtype->v.stephead, 0);
 	putchar('\n');
 #endif
 
 	return file_found;
 }