/* match.c */
#include "copyright.h"
#include "config.h"
#include <stdio.h>
#include <ctype.h>
#include "teeny.h"
#include "match.h"
#include "case.h"
/*
* Matching routines for TeenyMUD. Matching against contents lists is
* different* from matching against exit lists, so be careful.
*
* Some matching rouines require dinking with private data elsewhere, so
* match_player() (which hacks through the DB internals) lives with the db
* stuff in db.c, and match_who() (which hacks around with the WHO list
* maintained in misc.c) and match_active_player (likewise) is in misc.c.
*
*/
struct match *matches = NULL;
struct match *free_matches = NULL;
int current_best;
int match_thing_name();
int match_an_exit();
int match_tokens();
struct match *get_match();
#ifdef OLD_RAND
long rand();
#else
long random();
#endif /* OLD_RAND */
int best_match();
int score_match();
int pick2();
int pick3();
/*
* Searches the contents list, matching contents-wise (i.e. inexact matches
* OK, pick the best), and if that comes up empty, then the exits list
* matching exit-wise (i.e. must match an alias exactly). It returns one of
* the best it finds, chosen at random. Note that any match at all in the
* contents list will take precedence.
*
* Now it will return -2 if a tie occurs that should be notified as
* "I can't tell which one you mean."
*
*/
int
match_here(player, thing, str, code)
int player;
int thing;
char *str;
int code;
{
int list, total, the_match;
int loc, flags;
/* Catch "me" if we are, in fact, searching the player's location */
if ((code & MAT_PLAYERS) && strcmp(str, "me") == 0)
{
if (get_int_elt(player, LOC, &loc) == -1)
{
warning("match_here", "could not get LOC on player");
return (-1);
}
if (loc == thing)
{
return (player);
}
}
/* Catch object number references to, verify locations and types */
/* Fall through if anything is wrong, so *names* like #22 are OK */
if (*str == '#' && isdigit(str[1]))
{
the_match = atoi(str + 1);
if (exists_object(the_match))
{
if (get_int_elt(the_match, LOC, &loc) == -1)
{
warning("match_here", "could not get LOC");
return (-1);
}
if (loc == thing)
{
if (get_int_elt(the_match, FLAGS, &flags) == -1)
{
warning("match_here", "bad flags ref");
return (-1);
}
switch (flags & TYPE_MASK)
{
case TYP_THING:
if (code & MAT_THINGS)
return (the_match);
break;
case TYP_PLAYER:
if (code & MAT_PLAYERS)
return (the_match);
break;
case TYP_EXIT:
if (code & MAT_EXITS)
return (the_match);
break;
}
}
}
}
/* Do exits first. Only exact matches count here, so we */
/* avoid troubles with 's' matching a thing called 'Sam' */
/* rather than the exit 's;so;sou;sout;south' */
if (code & MAT_EXITS)
{
if (get_int_elt(thing, EXITS, &list) == -1)
{
warning("match_here", "bad exits list on thing.");
return (-1);
}
matches = match_exits(str, list, &total);
if (matches != NULL)
{
/* OK, we have some exits on this list. Pick one. */
the_match = choose_match(total);
free_match_list(matches);
matches = NULL;
return (the_match);
}
}
/* no dice on exits. Try other stuff */
if (code & (MAT_THINGS | MAT_PLAYERS))
{
/* Go get the list of things on the thing. */
if (get_int_elt(thing, CONTENTS, &list) == -1)
{
warning("match_here", "bad contents list on thing.");
return (-1);
}
current_best = 0;
total = match_contents(str, list, code);
if (total == -2) return (-2);
if (total != 0)
{
the_match = choose_match(total);
free_match_list(matches);
matches = NULL;
return (the_match);
}
}
return (-1);
}
/*
* Match against a contents list. Makes a list of all the stuff in the list
* that matched as well as possible. Returns total number of matches. May be
* called multiple times without spamming the matches list.
*
* Caller MUST zero current_best.
*/
match_contents(str, list, code)
char *str;
int list; /* First object in the contents list */
int code;
{
int count, total_matches, perfect_match;
char *name, *p, ch;
struct match *current_match;
int flags, type;
/* Loop across the entire list */
total_matches = 0;
perfect_match = 0; /* if we have >1 perfect match, return -2 (tie) */
while (list != -1)
{ /* While not end of list */
if (get_str_elt(list, NAME, &name) == -1)
{
warning("match_contents", "nameless object found!");
break;
}
if (get_int_elt(list, FLAGS, &flags) == -1)
{
warning("match_contents", "bad flags reference");
break;
}
type = TYPE_MASK & flags;
/* Check to see if we are looking for this sort of thing */
if ((!(code & MAT_PLAYERS) && type == TYP_PLAYER)
|| (!(code & MAT_THINGS) && type == TYP_THING))
{
if (get_int_elt(list, NEXT, &list) == -1)
{
warning("match_contents", "bad contents list");
break;
}
continue;
}
/* If it's a player, terminate after the name, before pwd */
if (type == TYP_PLAYER)
{
p = name;
while (!isspace(*p) && *p)
p++;
ch = *p;
*p = '\0';
} else
{
ch = '\0';
}
count = match_thing_name(str, name);
if (ch != '\0') /* If required, repair the name */
*p = ch;
if (count != 0)
{
if (current_best == count)
{
/* This match was just as good */
current_match = get_match();
current_match->obj = list;
insert_match(current_match, &matches);
total_matches++;
} else
if ((count > current_best && current_best >= 0)
|| count == -1)
{
/* This latest was a better match */
free_match_list(matches);
matches = NULL;
current_match = get_match();
current_match->obj = list;
insert_match(current_match, &matches);
total_matches = 1;
current_best = count;
}
}
if (get_int_elt(list, NEXT, &list) == -1)
{
warning("match_contents", "bad contents list");
break;
}
}
/*
* if we have a tie and the string isn't specific enough,
* then return -2 and let the player know we can't tell what
* he's referring to. Otherwise it's okay to choose randomly
* from the choices, or if there's only one, well yay.
*/
if(current_best != -1 && total_matches > 1)
return (-2);
else
return (total_matches);
}
/*
* Matches a string against the list of exits. Only exact matches are
* allowed, we handle semi-colon seperated aliases on exits. Matching is not
* case sensitive. Things better not have whitespace leading or following.
*
*/
struct match *
match_exits(str, list, count)
char *str;
int list;
int *count;
{
int total_matches;
struct match *current_match, *exits_matched;
char *name;
while (*str && isspace(*str))
str++;
/* Loop across the list. 'list' should be the first element */
total_matches = 0;
exits_matched = NULL;
while (list != -1)
{
if (get_str_elt(list, NAME, &name) == -1)
{
warning("match_exits", "bad exits list");
break;
}
while (*name && isspace(*name))
name++;
/* See if we have a match on this name */
if (match_an_exit(str, name))
{
/* Get a new match struct and enlist it */
current_match = get_match();
current_match->obj = list;
insert_match(current_match, &exits_matched);
total_matches++;
}
/* Get the next list element */
if (get_int_elt(list, NEXT, &list) == -1)
{
warning("match_exits", "bad exits list");
break;
}
}
*count = total_matches;
if (total_matches == 0)
{
return (NULL);
}
return (exits_matched);
}
/*
* Chooses a match at random from the 'matches' list, using the number passed
* as a count of how many things are on the list.
*
*/
int
choose_match(total)
int total;
{
int the_match;
struct match *current_match;
if (total == 0)
{
return (-1);
}
#ifdef OLD_RAND
the_match = (int) (rand() % (long) total);
#else
the_match = (int) (random() % (long) total);
#endif /* OLD_RAND */
current_match = matches;
while(the_match > 0)
{
current_match = current_match->fwd;
the_match--;
}
/*
* Old way. Made match confused.
* if (total > 1)
* return (-2);
*/
the_match = current_match->obj; /* This is bad. Recycling vbls! */
return (the_match);
}
/*
* Matches a string against an exit name. We require exact (though not case
* sensitive) matches. Cope with semi-colon seperated aliases in the exit
* name.
*
* Return 1 if a match, 0 if not.
*
*/
int
match_an_exit(str, name)
char *str, *name;
{
char *p;
p = str;
while (1)
{
while (DOWNCASE(*p) == DOWNCASE(*name) && *p
&& *name != ';' && *name)
{
p++;
name++;
}
/* Post mortem */
if ((*name == ';' || *name == '\0') && *p == '\0')
{
return (1);
}
while (*name != ';' && *name)
name++;
if (*name == '\0')
{
break;
} else
{
/* Skip the semi-colon and any whitespace after it */
while (*name && ((*name == ';') || isspace(*name)))
name++;
}
p = str;
}
return (0);
}
/*
* Match a thing name. The p is, roughly, what the monkey at the keyboard
* typed, q is the name we're matching against. Returns number of characters
* matched, or -1 to indicate an exact match.
*
* Case insensitive.
*/
int
match_thing_name(p, q)
char *p, *q;
{
int matched = 0;
int old_matched = 0;
int exact;
int initial_token;
while (isspace(*p) && *p)
p++;
if (*p == '\0')
{
return (0);
}
/* We slide along q, trying to match tokens in p against initial */
/* segments of sequential tokens of q. We keep track of stuff. */
initial_token = 1;
while (1)
{ /* Break out when we run out of space in q */
while (isspace(*q) && *q)
q++;
if (*q == '\0')
break;
matched = match_tokens(p, q, &exact);
if (exact && initial_token)
{
return (-1); /* Exact match */
} else
if (matched > old_matched)
{
old_matched = matched;
}
/* Skip q ahead to the end of this token */
while (!isspace(*q) && *q)
q++;
if (*q == '\0')
break;
initial_token = 0;
}
return (old_matched); /* This will be the best count we found */
}
/*
* Match p against q, token by token. p's tokens must be initial segments of
* q's tokens, in sequence, otherwise no match at all. Returns number of
* characters matched. Sets the value of exact to 1 or 0 to indicate whether
* or not all tokens matched exactly.
*
* Not case sensitive. Pretty much assumes no leading or trailing whitespace,
* this should not be a big problem. It's a *game*.
*
*/
int
match_tokens(p, q, exact)
char *p, *q;
int *exact;
{
int count = 0;
*exact = 1;
while (1)
{
/* Loop across characters of this token */
while (DOWNCASE(*p) == DOWNCASE(*q) && !isspace(p[1])
&& !isspace(q[1]) && *p && *q)
{
p++;
q++;
count++;
}
/* Post mortem. */
if (!(*q) && *p)
{ /* q ran out early. */
count = *exact = 0;
break;
}
if (*p == '\0')
{
if (*q)
*exact = 0;
break;
}
/* Neither *p nor *q are \0 */
if (DOWNCASE(*p) != DOWNCASE(*q))
{ /* No Match */
count = *exact = 0;
break;
}
/* OK. one of p[1] or q[1] was a space */
if (isspace(p[1]) || p[1] == '\0')
{
count++; /* Count misses a char. */
p++;
while (isspace(*p) && *p)
p++;
} else
{
count = *exact = 0;
break; /* No match */
}
if (!isspace(q[1]) && q[1])
{
*exact = 0;
}
while (!isspace(*q) && *q)
q++;
while (isspace(*q) && *q)
q++;
}
return (count);
}
/*
* Insert a match struct into a match list.
*/
insert_match(mt, mtlist)
struct match *mt, **mtlist;
{
if (*mtlist == NULL)
{
mt->back = mt->fwd = *mtlist = mt;
return;
}
mt->fwd = (*mtlist)->fwd;
mt->back = (*mtlist);
((*mtlist)->fwd)->back = mt;
(*mtlist)->fwd = mt;
}
/*
* Management code for match structs. We don't wanna malloc() and free all
* over the place, so we do it more efficiently ourselves. I know, this is
* anal retentive and probably no faster. Hah!
*
*/
struct match *
get_match()
{
int i;
struct match *ret;
/* If we have no free match structs around to give away, go get some */
if (free_matches == NULL)
{
free_matches = (struct match *) ty_malloc(
32 * sizeof(struct match),
"get_match");
/* Link them up into a free list */
for (i = 0; i < 31; i++)
{
free_matches[i].fwd = &(free_matches[i + 1]);
free_matches[i + 1].back = &(free_matches[i]);
}
free_matches[0].back = &(free_matches[31]);
free_matches[31].fwd = &(free_matches[0]);
}
/* Grab a match struct off the free list */
if (free_matches->back == free_matches)
{
ret = free_matches;
free_matches = NULL;
} else
{
ret = free_matches->fwd;
(ret->fwd)->back = free_matches;
free_matches->fwd = ret->fwd;
}
return (ret);
}
/*
* Places a list of matches on the free list. Copes with an empty list.
*/
free_match_list(mt)
struct match *mt;
{
if (mt == NULL)
{
return;
}
if (free_matches == NULL)
{
free_matches = mt;
return;
}
(mt->back)->fwd = free_matches->fwd;
(free_matches->fwd)->back = mt->back;
mt->back = free_matches;
free_matches->fwd = mt;
}
/*
* Takes four objects, and returns the best match with a given string.
*/
int best_match(str, match1, match2, match3, match4)
char *str;
int match1, match2, match3, match4;
{
int mscore[4], smatch[4], i, j, tie;
int tieflag = 0;
smatch[0] = match1;
smatch[1] = match2;
smatch[2] = match3;
smatch[3] = match4;
for(i=0,j=0;i<4;i++)
{
if(smatch[i] == -2) {
smatch[i] = -1;
tieflag = 1;
}
if(smatch[i] == -1)
mscore[i] = -2;
else
mscore[i] = score_match(str, smatch[i]);
if(mscore[i] > 1) mscore[i] = 1;
j += mscore[i];
}
if (j == -8)
return (-1 - tieflag); /* No matches (-1) ties exist (-2) */
if (smatch[3] > 0) { /* all exits are perfect */
mscore[3] = -1;
}
/* If there are perfect matches, */
/* pick one randomly. */
#ifdef OLD_RAND
j = rand();
#else
j = random();
#endif /* OLD_RAND */
for (i=0;i<4;i++,j++)
if (mscore[j%4] == -1)
return (smatch[j%4]);
/*
* If tieflag is set and there's no perfect matches, we do have
* ties, so return -2 immediately.
*/
if (tieflag) return (-2);
/*
* Okay, no exact matches. Next, check for ties... (ties return -2)
* Using smart algorithm, at the same, check for best match.
*/
/*
j = 0;
best = mscore[0];
tie = 0;
for (i=1;i<4;i++)
{
if (mscore[i] == best)
tie = 1;
if (mscore[i] > best)
{
best = mscore[i];
tie = 0;
j = i;
}
}
if (tie) return (-2);
return (smatch[j]);
*/
for(tie=i=0;i<4;i++)
{
if (mscore[i] == 1) j = i;
tie += mscore[i];
}
if (tie > 1) return (-2);
return (smatch[j]);
}
int score_match(str, object)
char *str;
int object;
{
int flags, score;
char *name, *p, ch;
if(get_str_elt(object, NAME, &name) == -1
|| get_int_elt(object, FLAGS, &flags) == -1)
{
warning("score_match", "bad object name or flags ref");
/* treat as not a match. */
return (-2);
}
if((flags & TYPE_MASK) == TYP_PLAYER)
{
p = name;
while (!isspace(*p) && *p)
p++;
ch = *p;
*p = '\0';
} else
{
ch = '\0';
}
if((flags & TYPE_MASK) == TYP_EXIT)
score = match_an_exit(str, name) ? -1 : 0;
else
score = match_thing_name(str, name);
if (ch != '\0') /* clean up. */
*p = ch;
return (score);
}