/* wild.c - wildcard routines */
/* $Id: wild.c,v 1.19 2002/08/28 15:24:09 rmg Exp $ */

/*
 * Written by T. Alexander Popiel, 24 June 1993
 * Last modified by T. Alexander Popiel, 19 August 1993
 *
 * Thanks go to Andrew Molitor for debugging
 * Thanks also go to Rich $alz for code to benchmark against
 *
 * Copyright (c) 1993 by T. Alexander Popiel
 * This code is hereby placed under GNU copyleft,
 * see copyright.h for details.
 */

#include "copyright.h"
#include "autoconf.h"
#include "config.h"

#include "alloc.h"	/* required by mudconf */
#include "flags.h"	/* required by mudconf */
#include "htab.h"	/* required by mudconf */
#include "mudconf.h"	/* required by code */

#include "db.h"		/* required by externs */
#include "externs.h"	/* required by code */

extern int FDECL(set_register, (const char *, char *, char *)); /* funvars.c */

#define FIXCASE(a) (tolower(a))
#define EQUAL(a,b) ((a == b) || (FIXCASE(a) == FIXCASE(b)))
#define NOTEQUAL(a,b) ((a != b) && (FIXCASE(a) != FIXCASE(b)))

static char **arglist;		/* argument return space */
static int numargs;		/* argument return size */

/* ---------------------------------------------------------------------------
 * check_literals: All literals in a wildcard pattern must appear in the
 *                 data string, or no match is possible.
 */

static int check_literals(tstr, dstr)
    char *tstr, *dstr;
{
    char pattern[LBUF_SIZE], data[LBUF_SIZE], *p, *dp, *ep, *xp;
    int len;

    /* Fast match the beginning of the string. */

    while ((*tstr != '*') && (*tstr != '?')) {
	if (*tstr == '\\')
	    tstr++;
	if (NOTEQUAL(*dstr, *tstr))
	    return 0;
	if (!*dstr)
	    return 1;
	tstr++;
	dstr++;
    }

    /* Make a lower-case copy of the data. */

    ep = data;
    while (*dstr) {
	*ep = FIXCASE(*dstr);
	ep++;
	dstr++;
    }
    *ep = '\0';

    /* Fast match the end of the string.
     * When we're done with this, we'll also have established a better
     * end point for the remainder of the literals match.
     * ep will point to the null terminator at the end of the data string
     * we need to worry about (i.e., that which has not already been
     * taken care of by our backwards match).
     * xp will point to the last character of the pattern string we need
     * to worry about.
     */

    ep--;
    xp = tstr + strlen(tstr) - 1;
    while ((ep >= dstr) && (xp >= tstr) && (*xp != '*') && (*xp != '?')) {
	if ((*xp != '\\') && NOTEQUAL(*ep, *xp))
	    return 0;
	ep--;
	xp--;
    }
    ep++;
    *ep = '\0';

    /* Walk the pattern string. Use the wildcard characters as delimiters,
     * to extract the literal strings that we need to match sequentially.
     */

    dp = data;
    while (*tstr && (tstr <= xp)) {
	while ((*tstr == '*') || (*tstr == '?'))
	    tstr++;
	if (!*tstr || (tstr > xp))
	    return 1;
	p = pattern;
	len = 0;
	while (*tstr && (*tstr != '*') && (*tstr != '?') && (tstr <= xp)) {
	    if (*tstr == '\\')
		tstr++;
	    *p = FIXCASE(*tstr);
	    p++;
	    tstr++;
	    len++;
	}
	*p = '\0';
	if (len) {
	    if ((dp = strstr(dp, pattern)) == NULL)
		return 0;
	    dp += len;
	}
	if (dp >= ep)
	    return 1;
    }

    return 1;
}

/* ---------------------------------------------------------------------------
 * quick_wild: do a wildcard match, without remembering the wild data.
 *
 * This routine will cause crashes if fed NULLs instead of strings.
 */

static int real_quick_wild(tstr, dstr)
char *tstr, *dstr;
{
	int st;

	if (mudstate.wild_times_lev > mudconf.wild_times_lim)
		return -1;
	mudstate.wild_times_lev++;

	while (*tstr != '*') {
		switch (*tstr) {
		case '?':
			/* Single character match.  Return false if at end
			 * of data. 
			 */
			if (!*dstr)
				return 0;
			break;
		case '\\':
			/* Escape character.  Move up, and force literal
			 * match of next character. 
			 */
			tstr++;
			/*
			 * FALL THROUGH 
			 */
		default:
			/* Literal character.  Check for a match. If
			 * matching end of data, return true. 
			 */
			if (NOTEQUAL(*dstr, *tstr))
				return 0;
			if (!*dstr)
				return 1;
		}
		tstr++;
		dstr++;
	}

	/* Skip over '*'. */

	tstr++;

	/* Return true on trailing '*'. */

	if (!*tstr)
		return 1;

	/* Skip over wildcards. */

	while ((*tstr == '?') || (*tstr == '*')) {
		if (*tstr == '?') {
			if (!*dstr)
				return 0;
			dstr++;
		}
		tstr++;
	}

	/* Skip over a backslash in the pattern string if it is there. */

	if (*tstr == '\\')
		tstr++;

	/* Return true on trailing '*'. */

	if (!*tstr)
		return 1;

	/* Scan for possible matches. */

	while (*dstr) {
	    if (EQUAL(*dstr, *tstr)) {
		if ((st = real_quick_wild(tstr + 1, dstr + 1)) != 0)
		    return st;
	    }
	    dstr++;
	}
	return 0;
}

int quick_wild(tstr, dstr)
    char *tstr, *dstr;
{
    int st;

    if (!check_literals(tstr, dstr))
	return 0;

    mudstate.wild_times_lev = 0;

    st = real_quick_wild(tstr, dstr);
    if ((st < 0) && (mudstate.wild_times_lev > mudconf.wild_times_lim))
	return 0;
    return st;
}

/* ---------------------------------------------------------------------------
 * wild1: INTERNAL: do a wildcard match, remembering the wild data.
 *
 * DO NOT CALL THIS FUNCTION DIRECTLY - DOING SO MAY RESULT IN
 * SERVER CRASHES AND IMPROPER ARGUMENT RETURN.
 *
 * Side Effect: this routine modifies the 'arglist' static global
 * variable.
 */

static int real_wild1(tstr, dstr, arg)
char *tstr, *dstr;
int arg;
{
	char *datapos;
	int argpos, numextra, st;

	if (mudstate.wild_times_lev > mudconf.wild_times_lim)
	    return -1;
	mudstate.wild_times_lev++;

	while (*tstr != '*') {
		switch (*tstr) {
		case '?':
			/* Single character match.  Return false if at end
			 * of data. 
			 */
			if (!*dstr)
				return 0;
			arglist[arg][0] = *dstr;
			arglist[arg][1] = '\0';
			arg++;

			/* Jump to the fast routine if we can. */

			if (arg >= numargs)
				return real_quick_wild(tstr + 1, dstr + 1);
			break;
		case '\\':
			/* Escape character.  Move up, and force literal
			 * match of next character. 
			 */
			tstr++;
			/*
			 * FALL THROUGH 
			 */
		default:
			/* Literal character.  Check for a match. If
			 * matching end of data, return true. 
			 */
			if (NOTEQUAL(*dstr, *tstr))
				return 0;
			if (!*dstr)
				return 1;
		}
		tstr++;
		dstr++;
	}

	/* If at end of pattern, slurp the rest, and leave. */

	if (!tstr[1]) {
		StringCopyTrunc(arglist[arg], dstr, LBUF_SIZE - 1);
		arglist[arg][LBUF_SIZE - 1] = '\0';
		return 1;
	}
	/* Remember current position for filling in the '*' return. */

	datapos = dstr;
	argpos = arg;

	/* Scan forward until we find a non-wildcard. */

	do {
		if (argpos < arg) {
			/* Fill in arguments if someone put another '*'
			 * before a fixed string. 
			 */
			arglist[argpos][0] = '\0';
			argpos++;

			/* Jump to the fast routine if we can. */

			if (argpos >= numargs)
				return real_quick_wild(tstr, dstr);

			/* Fill in any intervening '?'s */

			while (argpos < arg) {
				arglist[argpos][0] = *datapos;
				arglist[argpos][1] = '\0';
				datapos++;
				argpos++;

				/* Jump to the fast routine if we can. */

				if (argpos >= numargs)
					return real_quick_wild(tstr, dstr);
			}
		}
		/* Skip over the '*' for now... */

		tstr++;
		arg++;

		/* Skip over '?'s for now... */

		numextra = 0;
		while (*tstr == '?') {
			if (!*dstr)
				return 0;
			tstr++;
			dstr++;
			arg++;
			numextra++;
		}
	} while (*tstr == '*');

	/* Skip over a backslash in the pattern string if it is there. */

	if (*tstr == '\\')
		tstr++;

	/* Check for possible matches.  This loop terminates either at end
	 * of data (resulting in failure), or at a successful match. 
	 */
	while (1) {

		/* Scan forward until first character matches. */

		if (*tstr)
			while (NOTEQUAL(*dstr, *tstr)) {
				if (!*dstr)
					return 0;
				dstr++;
		} else
			while (*dstr)
				dstr++;

		/* The first character matches, now.  Check if the rest 
		 * does, using the fastest method, as usual. 
		 */

		if (*dstr) {
		    st = (arg < numargs) ?
			real_wild1(tstr + 1, dstr + 1, arg) :
			real_quick_wild(tstr + 1, dstr + 1);
		    if (st < 0)
			return st;
		} else {
		    st = 0;
		}
		if (!*dstr || st) {

			/* Found a match!  Fill in all remaining arguments.
			 * First do the '*'... 
			 */
			StringCopyTrunc(arglist[argpos], datapos,
					(dstr - datapos) - numextra);
			arglist[argpos][(dstr - datapos) - numextra] = '\0';
			datapos = dstr - numextra;
			argpos++;

			/* Fill in any trailing '?'s that are left. */

			while (numextra) {
				if (argpos >= numargs)
					return 1;
				arglist[argpos][0] = *datapos;
				arglist[argpos][1] = '\0';
				datapos++;
				argpos++;
				numextra--;
			}

			/* It's done! */

			return 1;
		} else {
			dstr++;
		}
	}
}

int wild1(tstr, dstr, arg)
    char *tstr, *dstr;
    int arg;
{
    int st;

    if (!check_literals(tstr, dstr))
	return 0;

    mudstate.wild_times_lev = 0;

    st = real_wild1(tstr, dstr, arg);
    if ((st < 0) && (mudstate.wild_times_lev > mudconf.wild_times_lim))
	return 0;
    return st;
} 

/* ---------------------------------------------------------------------------
 * wild: do a wildcard match, remembering the wild data.
 *
 * This routine will cause crashes if fed NULLs instead of strings.
 *
 * This function may crash if alloc_lbuf() fails.
 *
 * Side Effect: this routine modifies the 'arglist' and 'numargs'
 * static global variables.
 */
int wild(tstr, dstr, args, nargs)
char *tstr, *dstr, *args[];
int nargs;
{
	int i, value;
	char *scan;

	/* Initialize the return array. */

	for (i = 0; i < nargs; i++)
		args[i] = NULL;

	/* Do fast match. */

	while ((*tstr != '*') && (*tstr != '?')) {
		if (*tstr == '\\')
			tstr++;
		if (NOTEQUAL(*dstr, *tstr))
			return 0;
		if (!*dstr)
			return 1;
		tstr++;
		dstr++;
	}

	/* Allocate space for the return args. */

	i = 0;
	scan = tstr;
	while (*scan && (i < nargs)) {
		switch (*scan) {
		case '?':
			args[i] = alloc_lbuf("wild.?");
			i++;
			break;
		case '*':
			args[i] = alloc_lbuf("wild.*");
			i++;
		}
		scan++;
	}

	/* Put stuff in globals for quick recursion. */

	arglist = args;
	numargs = nargs;

	/* Do the match. */

	value = nargs ? wild1(tstr, dstr, 0) : quick_wild(tstr, dstr);

	/* Clean out any fake match data left by wild1. */

	for (i = 0; i < nargs; i++)
		if ((args[i] != NULL) && (!*args[i] || !value)) {
			free_lbuf(args[i]);
			args[i] = NULL;
		}
	return value;
}

/* ---------------------------------------------------------------------------
 * wild_match: do either an order comparison or a wildcard match,
 * remembering the wild data, if wildcard match is done.
 *
 * This routine will cause crashes if fed NULLs instead of strings.
 */
int wild_match(tstr, dstr)
char *tstr, *dstr;
{
	switch (*tstr) {
	case '>':
		tstr++;
		if (isdigit(*tstr) || (*tstr == '-'))
			return (atoi(tstr) < atoi(dstr));
		else
			return (strcmp(tstr, dstr) < 0);
	case '<':
		tstr++;
		if (isdigit(*tstr) || (*tstr == '-'))
			return (atoi(tstr) > atoi(dstr));
		else
			return (strcmp(tstr, dstr) > 0);
	}

	return quick_wild(tstr, dstr);
}

/* ----------------------------------------------------------------------
 * register_match: Do a wildcard match, setting the wild data into the
 * global registers.
 */

int register_match(tstr, dstr, args, nargs)
    char *tstr, *dstr, *args[];
    int nargs;
{
    int i, value;
    char *buff, *scan, *p, *end, *q_names[NUM_ENV_VARS];

    /* Initialize return array. */

    for (i = 0; i < nargs; i++)
	args[i] = q_names[i] = NULL;

    /* Do fast match. */

    while ((*tstr != '*') && (*tstr != '?')) {
	if (*tstr == '\\')
	    tstr++;
	if (NOTEQUAL(*dstr, *tstr))
	    return 0;
	if (!*dstr)
	    return 1;
	tstr++;
	dstr++;
    }

    /* Convert string, allocate space for the return args. */

    i = 0;
    scan = tstr;
    buff = alloc_lbuf("rmatch.buff");
    p = buff;
    while (*scan) {
	*p++ = *scan;
	switch (*scan) {
	    case '?':
		/* FALLTHRU */
	    case '*':
		args[i] = alloc_lbuf("xvars_match.wild");
		scan++;
		if (*scan == '{') {
		    if ((end = strchr(scan + 1, '}')) != NULL) {
			*end = '\0';
			if (*(scan + 1)) {
			    q_names[i] = XSTRDUP(scan + 1,
						    "rmatch.name");
			}
			scan = end + 1;
		    }
		}
		i++;
		break;
	    default:
		scan++;
	}
    }
    *p = '\0';

    /* Go do it. */

    arglist = args;
    numargs = nargs;
    value = nargs ? wild1(buff, dstr, 0) : quick_wild(buff, dstr);

    /* Copy things into registers. Clean fake match data from wild1(). */

    for (i = 0; i < nargs; i++) {
	if ((args[i] != NULL) && (!*args[i] || !value)) {
	    free_lbuf(args[i]);
	    args[i] = NULL;
	}
	if (args[i] && q_names[i])
	    set_register("rmatch", q_names[i], args[i]);
	if (q_names[i]) {
	    XFREE(q_names[i], "rmatch.name");
	}
    }
    free_lbuf(buff);

    return value;
}