Return to ex_tag.c CVS log

Up to [local] / src / usr.bin / vi / ex

For open/openat, if the flags parameter does not contain O_CREAT, the
3rd (variadic) mode_t parameter is irrelevant.  Many developers in the past
have passed mode_t (0, 044, 0644, or such), which might lead future people
to copy this broken idiom, and perhaps even believe this parameter has some
meaning or implication or application. Delete them all.
This comes out of a conversation where tb@ noticed that a strange (but
intentional) pledge behaviour is to always knock-out high-bits from
mode_t on a number of system calls as a safety factor, and his bewilderment
that this appeared to be happening against valid modes (at least visually),
but no sorry, they are all irrelevant junk.  They could all be 0xdeafbeef.
ok millert

/*	$OpenBSD: ex_tag.c,v 1.26 2021/10/24 21:24:17 deraadt Exp $	*/

/*-
 * Copyright (c) 1992, 1993, 1994
 *	The Regents of the University of California.  All rights reserved.
 * Copyright (c) 1992, 1993, 1994, 1995, 1996
 *	Keith Bostic.  All rights reserved.
 *
 * This code is derived from software contributed to Berkeley by
 * David Hitz of Auspex Systems, Inc.
 *
 * See the LICENSE file for redistribution information.
 */

#include "config.h"

#include <sys/mman.h>
#include <sys/queue.h>
#include <sys/stat.h>
#include <sys/time.h>

#include <bitstring.h>
#include <ctype.h>
#include <errno.h>
#include <fcntl.h>
#include <limits.h>
#include <stddef.h>
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <unistd.h>

#include "../common/common.h"
#include "../vi/vi.h"
#include "tag.h"

static char	*binary_search(char *, char *, char *);
static int	 compare(char *, char *, char *);
static void	 ctag_file(SCR *, TAGF *, char *, char **, size_t *);
static int	 ctag_search(SCR *, char *, size_t, char *);
static int	 ctag_sfile(SCR *, TAGF *, TAGQ *, char *);
static TAGQ	*ctag_slist(SCR *, char *);
static char	*linear_search(char *, char *, char *);
static int	 tag_copy(SCR *, TAG *, TAG **);
static int	 tag_pop(SCR *, TAGQ *, int);
static int	 tagf_copy(SCR *, TAGF *, TAGF **);
static int	 tagf_free(SCR *, TAGF *);
static int	 tagq_copy(SCR *, TAGQ *, TAGQ **);

/*
 * ex_tag_first --
 *	The tag code can be entered from main, e.g., "vi -t tag".
 *
 * PUBLIC: int ex_tag_first(SCR *, char *);
 */
int
ex_tag_first(SCR *sp, char *tagarg)
{
	ARGS *ap[2], a;
	EXCMD cmd;

	/* Build an argument for the ex :tag command. */
	ex_cinit(&cmd, C_TAG, 0, OOBLNO, OOBLNO, 0, ap);
	ex_cadd(&cmd, &a, tagarg, strlen(tagarg));

	/*
	 * XXX
	 * Historic vi went ahead and created a temporary file when it failed
	 * to find the tag.  We match historic practice, but don't distinguish
	 * between real error and failure to find the tag.
	 */
	if (ex_tag_push(sp, &cmd))
		return (0);

	/* Display tags in the center of the screen. */
	F_CLR(sp, SC_SCR_TOP);
	F_SET(sp, SC_SCR_CENTER);

	return (0);
}

/*
 * ex_tag_push -- ^]
 *		  :tag[!] [string]
 *
 * Enter a new TAGQ context based on a ctag string.
 *
 * PUBLIC: int ex_tag_push(SCR *, EXCMD *);
 */
int
ex_tag_push(SCR *sp, EXCMD *cmdp)
{
	EX_PRIVATE *exp;
	FREF *frp;
	TAG *rtp;
	TAGQ *rtqp, *tqp;
	recno_t lno;
	size_t cno;
	long tl;
	int force, istmp;

	exp = EXP(sp);
	switch (cmdp->argc) {
	case 1:
		free(exp->tag_last);

		if ((exp->tag_last = strdup(cmdp->argv[0]->bp)) == NULL) {
			msgq(sp, M_SYSERR, NULL);
			return (1);
		}

		/* Taglength may limit the number of characters. */
		if ((tl =
		    O_VAL(sp, O_TAGLENGTH)) != 0 && strlen(exp->tag_last) > tl)
			exp->tag_last[tl] = '\0';
		break;
	case 0:
		if (exp->tag_last == NULL) {
			msgq(sp, M_ERR, "No previous tag entered");
			return (1);
		}
		break;
	default:
		abort();
	}

	/* Get the tag information. */
	if ((tqp = ctag_slist(sp, exp->tag_last)) == NULL)
		return (1);

	/*
	 * Allocate all necessary memory before swapping screens.  Initialize
	 * flags so we know what to free.
	 */
	rtp = NULL;
	rtqp = NULL;
	if (TAILQ_EMPTY(&exp->tq)) {
		/* Initialize the `local context' tag queue structure. */
		CALLOC_GOTO(sp, rtqp, 1, sizeof(TAGQ));
		TAILQ_INIT(&rtqp->tagq);

		/* Initialize and link in its tag structure. */
		CALLOC_GOTO(sp, rtp, 1, sizeof(TAG));
		TAILQ_INSERT_HEAD(&rtqp->tagq, rtp, q);
		rtqp->current = rtp;
	}

	/*
	 * Stick the current context information in a convenient place, we're
	 * about to lose it.  Note, if we're called on editor startup, there
	 * will be no FREF structure.
	 */
	frp = sp->frp;
	lno = sp->lno;
	cno = sp->cno;
	istmp = frp == NULL ||
	    (F_ISSET(frp, FR_TMPFILE) && !F_ISSET(cmdp, E_NEWSCREEN));

	/* Try to switch to the tag. */
	force = FL_ISSET(cmdp->iflags, E_C_FORCE);
	if (F_ISSET(cmdp, E_NEWSCREEN)) {
		if (ex_tag_Nswitch(sp, TAILQ_FIRST(&tqp->tagq), force))
			goto err;

		/* Everything else gets done in the new screen. */
		sp = sp->nextdisp;
		exp = EXP(sp);
	} else
		if (ex_tag_nswitch(sp, TAILQ_FIRST(&tqp->tagq), force))
			goto err;

	/*
	 * If this is the first tag, put a `current location' queue entry
	 * in place, so we can pop all the way back to the current mark.
	 * Note, it doesn't point to much of anything, it's a placeholder.
	 */
	if (TAILQ_EMPTY(&exp->tq)) {
		TAILQ_INSERT_HEAD(&exp->tq, rtqp, q);
	} else
		rtqp = TAILQ_FIRST(&exp->tq);

	/* Link the new TAGQ structure into place. */
	TAILQ_INSERT_HEAD(&exp->tq, tqp, q);

	(void)ctag_search(sp,
	    tqp->current->search, tqp->current->slen, tqp->tag);

	/*
	 * Move the current context from the temporary save area into the
	 * right structure.
	 *
	 * If we were in a temporary file, we don't have a context to which
	 * we can return, so just make it be the same as what we're moving
	 * to.  It will be a little odd that ^T doesn't change anything, but
	 * I don't think it's a big deal.
	 */
	if (istmp) {
		rtqp->current->frp = sp->frp;
		rtqp->current->lno = sp->lno;
		rtqp->current->cno = sp->cno;
	} else {
		rtqp->current->frp = frp;
		rtqp->current->lno = lno;
		rtqp->current->cno = cno;
	}
	return (0);

err:
alloc_err:
	free(rtqp);
	free(rtp);
	tagq_free(sp, tqp);
	return (1);
}

/* 
 * ex_tag_next --
 *	Switch context to the next TAG.
 *
 * PUBLIC: int ex_tag_next(SCR *, EXCMD *);
 */
int
ex_tag_next(SCR *sp, EXCMD *cmdp)
{
	EX_PRIVATE *exp;
	TAG *tp;
	TAGQ *tqp;

	exp = EXP(sp);
	if ((tqp = TAILQ_FIRST(&exp->tq)) == NULL) {
		tag_msg(sp, TAG_EMPTY, NULL);
		return (1);
	}
	if ((tp = TAILQ_NEXT(tqp->current, q)) == NULL) {
		msgq(sp, M_ERR, "Already at the last tag of this group");
		return (1);
	}
	if (ex_tag_nswitch(sp, tp, FL_ISSET(cmdp->iflags, E_C_FORCE)))
		return (1);
	tqp->current = tp;

	(void)ctag_search(sp, tp->search, tp->slen, tqp->tag);

	return (0);
}

/* 
 * ex_tag_prev --
 *	Switch context to the next TAG.
 *
 * PUBLIC: int ex_tag_prev(SCR *, EXCMD *);
 */
int
ex_tag_prev(SCR *sp, EXCMD *cmdp)
{
	EX_PRIVATE *exp;
	TAG *tp;
	TAGQ *tqp;

	exp = EXP(sp);
	if ((tqp = TAILQ_FIRST(&exp->tq)) == NULL) {
		tag_msg(sp, TAG_EMPTY, NULL);
		return (0);
	}
	if ((tp = TAILQ_PREV(tqp->current, _tagqh, q)) == NULL) {
		msgq(sp, M_ERR, "Already at the first tag of this group");
		return (1);
	}
	if (ex_tag_nswitch(sp, tp, FL_ISSET(cmdp->iflags, E_C_FORCE)))
		return (1);
	tqp->current = tp;

	(void)ctag_search(sp, tp->search, tp->slen, tqp->tag);

	return (0);
}

/*
 * ex_tag_nswitch --
 *	Switch context to the specified TAG.
 *
 * PUBLIC: int ex_tag_nswitch(SCR *, TAG *, int);
 */
int
ex_tag_nswitch(SCR *sp, TAG *tp, int force)
{
	/* Get a file structure. */
	if (tp->frp == NULL && (tp->frp = file_add(sp, tp->fname)) == NULL)
		return (1);

	/* If not changing files, return, we're done. */
	if (tp->frp == sp->frp)
		return (0);

	/* Check for permission to leave. */
	if (file_m1(sp, force, FS_ALL | FS_POSSIBLE))
		return (1);

	/* Initialize the new file. */
	if (file_init(sp, tp->frp, NULL, FS_SETALT))
		return (1);

	/* Display tags in the center of the screen. */
	F_CLR(sp, SC_SCR_TOP);
	F_SET(sp, SC_SCR_CENTER);

	/* Switch. */
	F_SET(sp, SC_FSWITCH);
	return (0);
}

/*
 * ex_tag_Nswitch --
 *	Switch context to the specified TAG in a new screen.
 *
 * PUBLIC: int ex_tag_Nswitch(SCR *, TAG *, int);
 */
int
ex_tag_Nswitch(SCR *sp, TAG *tp, int force)
{
	SCR *new;

	/* Get a file structure. */
	if (tp->frp == NULL && (tp->frp = file_add(sp, tp->fname)) == NULL)
		return (1);

	/* Get a new screen. */
	if (screen_init(sp->gp, sp, &new))
		return (1);
	if (vs_split(sp, new, 0)) {
		(void)file_end(new, new->ep, 1);
		(void)screen_end(new);
		return (1);
	}

	/* Get a backing file. */
	if (tp->frp == sp->frp) {
		/* Copy file state. */
		new->ep = sp->ep;
		++new->ep->refcnt;

		new->frp = tp->frp;
		new->frp->flags = sp->frp->flags;
	} else if (file_init(new, tp->frp, NULL, force)) {
		(void)vs_discard(new, NULL);
		(void)screen_end(new);
		return (1);
	}

	/* Create the argument list. */
	new->cargv = new->argv = ex_buildargv(sp, NULL, tp->frp->name);

	/* Display tags in the center of the screen. */
	F_CLR(new, SC_SCR_TOP);
	F_SET(new, SC_SCR_CENTER);

	/* Switch. */
	sp->nextdisp = new;
	F_SET(sp, SC_SSWITCH);

	return (0);
}

/*
 * ex_tag_pop -- ^T
 *		 :tagp[op][!] [number | file]
 *
 *	Pop to a previous TAGQ context.
 *
 * PUBLIC: int ex_tag_pop(SCR *, EXCMD *);
 */
int
ex_tag_pop(SCR *sp, EXCMD *cmdp)
{
	EX_PRIVATE *exp;
	TAGQ *tqp, *dtqp = NULL;
	size_t arglen;
	long off;
	char *arg, *p, *t;

	/* Check for an empty stack. */
	exp = EXP(sp);
	if (TAILQ_EMPTY(&exp->tq)) {
		tag_msg(sp, TAG_EMPTY, NULL);
		return (1);
	}

	/* Find the last TAG structure that we're going to DISCARD! */
	switch (cmdp->argc) {
	case 0:				/* Pop one tag. */
		dtqp = TAILQ_FIRST(&exp->tq);
		break;
	case 1:				/* Name or number. */
		arg = cmdp->argv[0]->bp;
		off = strtol(arg, &p, 10);
		if (*p != '\0')
			goto filearg;

		/* Number: pop that many queue entries. */
		if (off < 1)
			return (0);
		TAILQ_FOREACH(tqp, &exp->tq, q) {
			if (--off <= 1)
				break;
		}
		if (tqp == NULL) {
			msgq(sp, M_ERR,
	"Less than %s entries on the tags stack; use :display t[ags]",
			    arg);
			return (1);
		}
		dtqp = tqp;
		break;

		/* File argument: pop to that queue entry. */
filearg:	arglen = strlen(arg);
		for (tqp = TAILQ_FIRST(&exp->tq); tqp;
		    dtqp = tqp, tqp = TAILQ_NEXT(tqp, q)) {
			/* Don't pop to the current file. */
			if (tqp == TAILQ_FIRST(&exp->tq))
				continue;
			p = tqp->current->frp->name;
			if ((t = strrchr(p, '/')) == NULL)
				t = p;
			else
				++t;
			if (!strncmp(arg, t, arglen))
				break;
		}
		if (tqp == NULL) {
			msgq_str(sp, M_ERR, arg,
	"No file %s on the tags stack to return to; use :display t[ags]");
			return (1);
		}
		if (tqp == TAILQ_FIRST(&exp->tq))
			return (0);
		break;
	default:
		abort();
		/* NOTREACHED */
	}

	return (tag_pop(sp, dtqp, FL_ISSET(cmdp->iflags, E_C_FORCE)));
}

/*
 * ex_tag_top -- :tagt[op][!]
 *	Clear the tag stack.
 *
 * PUBLIC: int ex_tag_top(SCR *, EXCMD *);
 */
int
ex_tag_top(SCR *sp, EXCMD *cmdp)
{
	EX_PRIVATE *exp;

	exp = EXP(sp);

	/* Check for an empty stack. */
	if (TAILQ_EMPTY(&exp->tq)) {
		tag_msg(sp, TAG_EMPTY, NULL);
		return (1);
	}

	/* Return to the oldest information. */
	return (tag_pop(sp,
	    TAILQ_PREV(TAILQ_LAST(&exp->tq, _tqh), _tqh, q),
	    FL_ISSET(cmdp->iflags, E_C_FORCE)));
}

/*
 * tag_pop --
 *	Pop up to and including the specified TAGQ context.
 */
static int
tag_pop(SCR *sp, TAGQ *dtqp, int force)
{
	EX_PRIVATE *exp;
	TAG *tp;
	TAGQ *tqp;

	exp = EXP(sp);

	/*
	 * Update the cursor from the saved TAG information of the TAG
	 * structure we're moving to.
	 */
	tp = TAILQ_NEXT(dtqp, q)->current;
	if (tp->frp == sp->frp) {
		sp->lno = tp->lno;
		sp->cno = tp->cno;
	} else {
		if (file_m1(sp, force, FS_ALL | FS_POSSIBLE))
			return (1);

		tp->frp->lno = tp->lno;
		tp->frp->cno = tp->cno;
		F_SET(sp->frp, FR_CURSORSET);
		if (file_init(sp, tp->frp, NULL, FS_SETALT))
			return (1);

		F_SET(sp, SC_FSWITCH);
	}

	/* Pop entries off the queue up to and including dtqp. */
	do {
		tqp = TAILQ_FIRST(&exp->tq);
		if (tagq_free(sp, tqp))
			return (0);
	} while (tqp != dtqp);

	/*
	 * If only a single tag left, we've returned to the first tag point,
	 * and the stack is now empty.
	 */
	if (TAILQ_NEXT(TAILQ_FIRST(&exp->tq), q) == NULL)
		tagq_free(sp, TAILQ_FIRST(&exp->tq));

	return (0);
}

/*
 * ex_tag_display --
 *	Display the list of tags.
 *
 * PUBLIC: int ex_tag_display(SCR *);
 */
int
ex_tag_display(SCR *sp)
{
	EX_PRIVATE *exp;
	TAG *tp;
	TAGQ *tqp;
	int cnt;
	size_t len;
	char *p;

	exp = EXP(sp);
	if (TAILQ_EMPTY(&exp->tq)) {
		tag_msg(sp, TAG_EMPTY, NULL);
		return (0);
	}
	tqp = TAILQ_FIRST(&exp->tq);

	/*
	 * We give the file name 20 columns and the search string the rest.
	 * If there's not enough room, we don't do anything special, it's
	 * not worth the effort, it just makes the display more confusing.
	 *
	 * We also assume that characters in file names map 1-1 to printing
	 * characters.  This might not be true, but I don't think it's worth
	 * fixing.  (The obvious fix is to pass the filenames through the
	 * msg_print function.)
	 */
#define	L_NAME	30		/* Name. */
#define	L_SLOP	 4		/* Leading number plus trailing *. */
#define	L_SPACE	 5		/* Spaces after name, before tag. */
#define	L_TAG	20		/* Tag. */
	if (sp->cols <= L_NAME + L_SLOP) {
		msgq(sp, M_ERR, "Display too small.");
		return (0);
	}

	/*
	 * Display the list of tags for each queue entry.  The first entry
	 * is numbered, and the current tag entry has an asterisk appended.
	 */
	cnt = 0;
	TAILQ_FOREACH(tqp, &exp->tq, q) {
		if (INTERRUPTED(sp))
			break;
		++cnt;
		TAILQ_FOREACH(tp, &tqp->tagq, q) {
			if (tp == TAILQ_FIRST(&tqp->tagq))
				(void)ex_printf(sp, "%2d ", cnt);
			else
				(void)ex_printf(sp, "   ");
			p = tp->frp == NULL ? tp->fname : tp->frp->name;
			if ((len = strlen(p)) > L_NAME) {
				len = len - (L_NAME - 4);
				(void)ex_printf(sp, "   ... %*.*s",
				    L_NAME - 4, L_NAME - 4, p + len);
			} else
				(void)ex_printf(sp,
				    "   %*.*s", L_NAME, L_NAME, p);
			if (tqp->current == tp)
				(void)ex_printf(sp, "*");

			if (tp == TAILQ_FIRST(&tqp->tagq) && tqp->tag != NULL &&
			    (sp->cols - L_NAME) >= L_TAG + L_SPACE) {
				len = strlen(tqp->tag);
				if (len > sp->cols - (L_NAME + L_SPACE))
					len = sp->cols - (L_NAME + L_SPACE);
				(void)ex_printf(sp, "%s%.*s",
				    tqp->current == tp ? "    " : "     ",
				    (int)len, tqp->tag);
			}
			(void)ex_printf(sp, "\n");
		}
	}
	return (0);
}

/*
 * ex_tag_copy --
 *	Copy a screen's tag structures.
 *
 * PUBLIC: int ex_tag_copy(SCR *, SCR *);
 */
int
ex_tag_copy(SCR *orig, SCR *sp)
{
	EX_PRIVATE *oexp, *nexp;
	TAGQ *aqp, *tqp;
	TAG *ap, *tp;
	TAGF *atfp, *tfp;

	oexp = EXP(orig);
	nexp = EXP(sp);

	/* Copy tag queue and tags stack. */
	TAILQ_FOREACH(aqp, &oexp->tq, q) {
		if (tagq_copy(sp, aqp, &tqp))
			return (1);
		TAILQ_FOREACH(ap, &aqp->tagq, q) {
			if (tag_copy(sp, ap, &tp))
				return (1);
			/* Set the current pointer. */
			if (aqp->current == ap)
				tqp->current = tp;
			TAILQ_INSERT_TAIL(&tqp->tagq, tp, q);
		}
		TAILQ_INSERT_TAIL(&nexp->tq, tqp, q);
	}

	/* Copy list of tag files. */
	TAILQ_FOREACH(atfp, &oexp->tagfq, q) {
		if (tagf_copy(sp, atfp, &tfp))
			return (1);
		TAILQ_INSERT_TAIL(&nexp->tagfq, tfp, q);
	}

	/* Copy the last tag. */
	if (oexp->tag_last != NULL &&
	    (nexp->tag_last = strdup(oexp->tag_last)) == NULL) {
		msgq(sp, M_SYSERR, NULL);
		return (1);
	}
	return (0);
}

/*
 * tagf_copy --
 *	Copy a TAGF structure and return it in new memory.
 */
static int
tagf_copy(SCR *sp, TAGF *otfp, TAGF **tfpp)
{
	TAGF *tfp;

	MALLOC_RET(sp, tfp, sizeof(TAGF));
	*tfp = *otfp;

	/* XXX: Allocate as part of the TAGF structure!!! */
	if ((tfp->name = strdup(otfp->name)) == NULL) {
		free(tfp);
		return (1);
	}

	*tfpp = tfp;
	return (0);
}

/*
 * tagq_copy --
 *	Copy a TAGQ structure and return it in new memory.
 */
static int
tagq_copy(SCR *sp, TAGQ *otqp, TAGQ **tqpp)
{
	TAGQ *tqp;
	size_t len;

	len = sizeof(TAGQ);
	if (otqp->tag != NULL)
		len += otqp->tlen + 1;
	MALLOC_RET(sp, tqp, len);
	memcpy(tqp, otqp, len);

	TAILQ_INIT(&tqp->tagq);
	tqp->current = NULL;
	if (otqp->tag != NULL)
		tqp->tag = tqp->buf;

	*tqpp = tqp;
	return (0);
}

/*
 * tag_copy --
 *	Copy a TAG structure and return it in new memory.
 */
static int
tag_copy(SCR *sp, TAG *otp, TAG **tpp)
{
	TAG *tp;
	size_t len;

	len = sizeof(TAG);
	if (otp->fname != NULL)
		len += otp->fnlen + 1;
	if (otp->search != NULL)
		len += otp->slen + 1;
	MALLOC_RET(sp, tp, len);
	memcpy(tp, otp, len);

	if (otp->fname != NULL)
		tp->fname = tp->buf;
	if (otp->search != NULL)
		tp->search = tp->fname + otp->fnlen + 1;

	*tpp = tp;
	return (0);
}

/*
 * tagf_free --
 *	Free a TAGF structure.
 */
static int
tagf_free(SCR *sp, TAGF *tfp)
{
	EX_PRIVATE *exp;

	exp = EXP(sp);
	TAILQ_REMOVE(&exp->tagfq, tfp, q);
	free(tfp->name);
	free(tfp);
	return (0);
}

/*
 * tagq_free --
 *	Free a TAGQ structure (and associated TAG structures).
 *
 * PUBLIC: int tagq_free(SCR *, TAGQ *);
 */
int
tagq_free(SCR *sp, TAGQ *tqp)
{
	EX_PRIVATE *exp;
	TAGQ *ttqp;
	TAG *tp;

	exp = EXP(sp);
	while ((tp = TAILQ_FIRST(&tqp->tagq))) {
		TAILQ_REMOVE(&tqp->tagq, tp, q);
		free(tp);
	}
	/*
	 * !!!
	 * If allocated and then the user failed to switch files, the TAGQ
	 * structure was never attached to any list.
	 */
	TAILQ_FOREACH(ttqp, &exp->tq, q) {
		if (ttqp == tqp) {
			TAILQ_REMOVE(&exp->tq, tqp, q);
			break;
		}
	}
	free(tqp);
	return (0);
}

/*
 * tag_msg
 *	A few common messages.
 *
 * PUBLIC: void tag_msg(SCR *, tagmsg_t, char *);
 */
void
tag_msg(SCR *sp, tagmsg_t msg, char *tag)
{
	switch (msg) {
	case TAG_BADLNO:
		msgq_str(sp, M_ERR, tag,
	    "%s: the tag's line number is past the end of the file");
		break;
	case TAG_EMPTY:
		msgq(sp, M_INFO, "The tags stack is empty");
		break;
	case TAG_SEARCH:
		msgq_str(sp, M_ERR, tag, "%s: search pattern not found");
		break;
	default:
		abort();
	}
}

/*
 * ex_tagf_alloc --
 *	Create a new list of ctag files.
 *
 * PUBLIC: int ex_tagf_alloc(SCR *, char *);
 */
int
ex_tagf_alloc(SCR *sp, char *str)
{
	EX_PRIVATE *exp;
	TAGF *tfp;
	size_t len;
	char *p, *t;

	/* Free current queue. */
	exp = EXP(sp);
	while ((tfp = TAILQ_FIRST(&exp->tagfq)) != NULL)
		tagf_free(sp, tfp);

	/* Create new queue. */
	for (p = t = str;; ++p) {
		if (*p == '\0' || isblank(*p)) {
			if ((len = p - t) > 1) {
				MALLOC_RET(sp, tfp, sizeof(TAGF));
				MALLOC(sp, tfp->name, len + 1);
				if (tfp->name == NULL) {
					free(tfp);
					return (1);
				}
				memcpy(tfp->name, t, len);
				tfp->name[len] = '\0';
				tfp->flags = 0;
				TAILQ_INSERT_TAIL(&exp->tagfq, tfp, q);
			}
			t = p + 1;
		}
		if (*p == '\0')
			 break;
	}
	return (0);
}
						/* Free previous queue. */
/*
 * ex_tag_free --
 *	Free the ex tag information.
 *
 * PUBLIC: int ex_tag_free(SCR *);
 */
int
ex_tag_free(SCR *sp)
{
	EX_PRIVATE *exp;
	TAGF *tfp;
	TAGQ *tqp;

	/* Free up tag information. */
	exp = EXP(sp);
	while ((tqp = TAILQ_FIRST(&exp->tq)))
		tagq_free(sp, tqp);	/* tagq_free removes tqp from queue. */
	while ((tfp = TAILQ_FIRST(&exp->tagfq)) != NULL)
		tagf_free(sp, tfp);
	free(exp->tag_last);
	return (0);
}

/*
 * ctag_search --
 *	Search a file for a tag.
 */
static int
ctag_search(SCR *sp, char *search, size_t slen, char *tag)
{
	MARK m;
	char *p;

	/*
	 * !!!
	 * The historic tags file format (from a long, long time ago...)
	 * used a line number, not a search string.  I got complaints, so
	 * people are still using the format.  POSIX 1003.2 permits it.
	 */
	if (isdigit(search[0])) {
		m.lno = atoi(search);
		if (!db_exist(sp, m.lno)) {
			tag_msg(sp, TAG_BADLNO, tag);
			return (1);
		}
	} else {
		/*
		 * Search for the tag; cheap fallback for C functions
		 * if the name is the same but the arguments have changed.
		 */
		m.lno = 1;
		m.cno = 0;
		if (f_search(sp, &m, &m,
		    search, slen, NULL, SEARCH_FILE | SEARCH_TAG)) {
			if ((p = strrchr(search, '(')) != NULL) {
				slen = p - search;
				if (f_search(sp, &m, &m, search, slen,
				    NULL, SEARCH_FILE | SEARCH_TAG))
					goto notfound;
			} else {
notfound:			tag_msg(sp, TAG_SEARCH, tag);
				return (1);
			}
		}
		/*
		 * !!!
		 * Historically, tags set the search direction if it wasn't
		 * already set.
		 */
		if (sp->searchdir == NOTSET)
			sp->searchdir = FORWARD;
	}

	/*
	 * !!!
	 * Tags move to the first non-blank, NOT the search pattern start.
	 */
	sp->lno = m.lno;
	sp->cno = 0;
	(void)nonblank(sp, sp->lno, &sp->cno);
	return (0);
}

/*
 * ctag_slist --
 *	Search the list of tags files for a tag, and return tag queue.
 */
static TAGQ *
ctag_slist(SCR *sp, char *tag)
{
	EX_PRIVATE *exp;
	TAGF *tfp;
	TAGQ *tqp;
	size_t len;
	int echk;

	exp = EXP(sp);

	/* Allocate and initialize the tag queue structure. */
	len = strlen(tag);
	CALLOC_GOTO(sp, tqp, 1, sizeof(TAGQ) + len + 1);
	TAILQ_INIT(&tqp->tagq);
	tqp->tag = tqp->buf;
	memcpy(tqp->tag, tag, (tqp->tlen = len) + 1);

	/*
	 * Find the tag, only display missing file messages once, and
	 * then only if we didn't find the tag.
	 */
	echk = 0;
	TAILQ_FOREACH(tfp, &exp->tagfq, q)
		if (ctag_sfile(sp, tfp, tqp, tag)) {
			echk = 1;
			F_SET(tfp, TAGF_ERR);
		} else
			F_CLR(tfp, TAGF_ERR | TAGF_ERR_WARN);

	/* Check to see if we found anything. */
	if (TAILQ_EMPTY(&tqp->tagq)) {
		msgq_str(sp, M_ERR, tag, "%s: tag not found");
		if (echk)
			TAILQ_FOREACH(tfp, &exp->tagfq, q)
				if (F_ISSET(tfp, TAGF_ERR) &&
				    !F_ISSET(tfp, TAGF_ERR_WARN)) {
					errno = tfp->errnum;
					msgq_str(sp, M_SYSERR, tfp->name, "%s");
					F_SET(tfp, TAGF_ERR_WARN);
				}
		free(tqp);
		return (NULL);
	}

	tqp->current = TAILQ_FIRST(&tqp->tagq);
	return (tqp);

alloc_err:
	return (NULL);
}

/*
 * ctag_sfile --
 *	Search a tags file for a tag, adding any found to the tag queue.
 */
static int
ctag_sfile(SCR *sp, TAGF *tfp, TAGQ *tqp, char *tname)
{
	struct stat sb;
	TAG *tp;
	size_t dlen, nlen, slen;
	int fd, i, nf1, nf2;
	char *back, *cname, *dname, *front, *map, *name, *p, *search, *t;

	if ((fd = open(tfp->name, O_RDONLY)) < 0) {
		tfp->errnum = errno;
		return (1);
	}

	/*
	 * XXX
	 * We'd like to test if the file is too big to mmap.  Since we don't
	 * know what size or type off_t's or size_t's are, what the largest
	 * unsigned integral type is, or what random insanity the local C
	 * compiler will perpetrate, doing the comparison in a portable way
	 * is flatly impossible.  Hope mmap fails if the file is too large.
	 */
	if (fstat(fd, &sb) != 0 ||
	    (map = mmap(NULL, (size_t)sb.st_size, PROT_READ | PROT_WRITE,
	    MAP_PRIVATE, fd, (off_t)0)) == MAP_FAILED) {
		tfp->errnum = errno;
		(void)close(fd);
		return (1);
	}

	front = map;
	back = front + sb.st_size;
	front = binary_search(tname, front, back);
	front = linear_search(tname, front, back);
	if (front == NULL)
		goto done;

	/*
	 * Initialize and link in the tag structure(s).  The historic ctags
	 * file format only permitted a single tag location per tag.  The
	 * obvious extension to permit multiple tags locations per tag is to
	 * output multiple records in the standard format.  Unfortunately,
	 * this won't work correctly with historic ex/vi implementations,
	 * because their binary search assumes that there's only one record
	 * per tag, and so will use a random tag entry if there si more than
	 * one.  This code handles either format.
	 *
	 * The tags file is in the following format:
	 *
	 *	<tag> <filename> <line number> | <pattern>
	 *
	 * Figure out how long everything is so we can allocate in one swell
	 * foop, but discard anything that looks wrong.
	 */
	for (;;) {
		/* Nul-terminate the end of the line. */
		for (p = front; p < back && *p != '\n'; ++p);
		if (p == back || *p != '\n')
			break;
		*p = '\0';

		/* Update the pointers for the next time. */
		t = p + 1;
		p = front;
		front = t;

		/* Break the line into tokens. */
		for (i = 0; i < 2 && (t = strsep(&p, "\t ")) != NULL; ++i)
			switch (i) {
			case 0:			/* Tag. */
				cname = t;
				break;
			case 1:			/* Filename. */
				name = t;
				nlen = strlen(name);
				break;
			}

		/* Check for corruption. */
		if (i != 2 || p == NULL || t == NULL)
			goto corrupt;

		/* The rest of the string is the search pattern. */
		search = p;
		if ((slen = strlen(p)) == 0) {
corrupt:		p = msg_print(sp, tname, &nf1);
			t = msg_print(sp, tfp->name, &nf2);
			msgq(sp, M_ERR, "%s: corrupted tag in %s", p, t);
			if (nf1)
				FREE_SPACE(sp, p, 0);
			if (nf2)
				FREE_SPACE(sp, t, 0);
			continue;
		}

		/* Check for passing the last entry. */
		if (strcmp(tname, cname))
			break;

		/* Resolve the file name. */
		ctag_file(sp, tfp, name, &dname, &dlen);

		CALLOC_GOTO(sp, tp,
		    1, sizeof(TAG) + dlen + 2 + nlen + 1 + slen + 1);
		tp->fname = tp->buf;
		if (dlen != 0) {
			memcpy(tp->fname, dname, dlen);
			tp->fname[dlen] = '/';
			++dlen;
		}
		memcpy(tp->fname + dlen, name, nlen + 1);
		tp->fnlen = dlen + nlen;
		tp->search = tp->fname + tp->fnlen + 1;
		memcpy(tp->search, search, (tp->slen = slen) + 1);
		TAILQ_INSERT_TAIL(&tqp->tagq, tp, q);
	}

alloc_err:
done:	if (munmap(map, (size_t)sb.st_size))
		msgq(sp, M_SYSERR, "munmap");
	if (close(fd))
		msgq(sp, M_SYSERR, "close");
	return (0);
}

/*
 * ctag_file --
 *	Search for the right path to this file.
 */
static void
ctag_file(SCR *sp, TAGF *tfp, char *name, char **dirp, size_t *dlenp)
{
	struct stat sb;
	char *p, buf[PATH_MAX];

	/*
	 * !!!
	 * If the tag file path is a relative path, see if it exists.  If it
	 * doesn't, look relative to the tags file path.  It's okay for a tag
	 * file to not exist, and historically, vi simply displayed a "new"
	 * file.  However, if the path exists relative to the tag file, it's
	 * pretty clear what's happening, so we may as well get it right.
	 */
	*dlenp = 0;
	if (name[0] != '/' &&
	    stat(name, &sb) && (p = strrchr(tfp->name, '/')) != NULL) {
		*p = '\0';
		(void)snprintf(buf, sizeof(buf), "%s/%s", tfp->name, name);
		if (stat(buf, &sb) == 0) {
			*dirp = tfp->name;
			*dlenp = strlen(*dirp);
		}
		*p = '/';
	}
}

/*
 * Binary search for "string" in memory between "front" and "back".
 *
 * This routine is expected to return a pointer to the start of a line at
 * *or before* the first word matching "string".  Relaxing the constraint
 * this way simplifies the algorithm.
 *
 * Invariants:
 * 	front points to the beginning of a line at or before the first
 *	matching string.
 *
 * 	back points to the beginning of a line at or after the first
 *	matching line.
 *
 * Base of the Invariants.
 * 	front = NULL;
 *	back = EOF;
 *
 * Advancing the Invariants:
 *
 * 	p = first newline after halfway point from front to back.
 *
 * 	If the string at "p" is not greater than the string to match,
 *	p is the new front.  Otherwise it is the new back.
 *
 * Termination:
 *
 * 	The definition of the routine allows it return at any point,
 *	since front is always at or before the line to print.
 *
 * 	In fact, it returns when the chosen "p" equals "back".  This
 *	implies that there exists a string is least half as long as
 *	(back - front), which in turn implies that a linear search will
 *	be no more expensive than the cost of simply printing a string or two.
 *
 * 	Trying to continue with binary search at this point would be
 *	more trouble than it's worth.
 */
#define	EQUAL		0
#define	GREATER		1
#define	LESS		(-1)

#define	SKIP_PAST_NEWLINE(p, back)	while ((p) < (back) && *(p)++ != '\n');

static char *
binary_search(char *string, char *front, char *back)
{
	char *p;

	p = front + (back - front) / 2;
	SKIP_PAST_NEWLINE(p, back);

	while (p != back) {
		if (compare(string, p, back) == GREATER)
			front = p;
		else
			back = p;
		p = front + (back - front) / 2;
		SKIP_PAST_NEWLINE(p, back);
	}
	return (front);
}

/*
 * Find the first line that starts with string, linearly searching from front
 * to back.
 *
 * Return NULL for no such line.
 *
 * This routine assumes:
 *
 * 	o front points at the first character in a line.
 *	o front is before or at the first line to be printed.
 */
static char *
linear_search(char *string, char *front, char *back)
{
	while (front < back) {
		switch (compare(string, front, back)) {
		case EQUAL:		/* Found it. */
			return (front);
		case LESS:		/* No such string. */
			return (NULL);
		case GREATER:		/* Keep going. */
			break;
		}
		SKIP_PAST_NEWLINE(front, back);
	}
	return (NULL);
}

/*
 * Return LESS, GREATER, or EQUAL depending on how the string1 compares
 * with string2 (s1 ??? s2).
 *
 * 	o Matches up to len(s1) are EQUAL.
 *	o Matches up to len(s2) are GREATER.
 *
 * The string "s1" is null terminated.  The string s2 is '\t', space, (or
 * "back") terminated.
 *
 * !!!
 * Reasonably modern ctags programs use tabs as separators, not spaces.
 * However, historic programs did use spaces, and, I got complaints.
 */
static int
compare(char *s1, char *s2, char *back)
{
	for (; *s1 && s2 < back && (*s2 != '\t' && *s2 != ' '); ++s1, ++s2)
		if (*s1 != *s2)
			return (*s1 < *s2 ? LESS : GREATER);
	return (*s1 ? GREATER : s2 < back &&
	    (*s2 != '\t' && *s2 != ' ') ? LESS : EQUAL);
}