Re: lib/wildmat.c broken?

/me wrote the following:

> it seems that XPAT doesn't work properly. Mozilla uses XPAT to search
> all subjects in a group for an expression but sn returns always all
> subjects if you search for a single word e.g. nerd. Mozilla generates
> the following: XPAT SUBJECT  1- *[Nn][Ee][Rr][Dd]*

It seems that the *-handling is slightly broken but I couldn't track down
the bug so I looked up for another wildmat.c and found one in the diablo
source.
It works fine here and it's also much faster for cases like:

text    = "235325235foobaz354325fdhhysfdhdsfh\r\n"
pattern = "*[Ff][Oo][Oo][Bb][Aa][Rr]*\r\n"

I benchmarked a little bit (AthlonXP 2600+):

chris@chris: ~/EIS/SN/sn-0.3.8/lib > gcc testwm2.c wildmat2.c wildmat.c -o testwm2
chris@chris: ~/EIS/SN/sn-0.3.8/lib > for i in 1 2 3 4 5 6 7 8 9 10; do ./testwm2; done
diablo-wildmat says 0 in 787133 µsec
sn-wildmat     says 1 in 4413316 µsec
diablo-wildmat says 0 in 773476 µsec
sn-wildmat     says 1 in 4392618 µsec
diablo-wildmat says 0 in 774748 µsec
sn-wildmat     says 1 in 4396111 µsec
diablo-wildmat says 0 in 776780 µsec
sn-wildmat     says 1 in 4392465 µsec
diablo-wildmat says 0 in 775474 µsec
sn-wildmat     says 1 in 4407019 µsec
diablo-wildmat says 0 in 770684 µsec
sn-wildmat     says 1 in 4440008 µsec
diablo-wildmat says 0 in 782249 µsec
sn-wildmat     says 1 in 4503065 µsec
diablo-wildmat says 0 in 780462 µsec
sn-wildmat     says 1 in 4403415 µsec
diablo-wildmat says 0 in 781486 µsec
sn-wildmat     says 1 in 4428745 µsec
diablo-wildmat says 0 in 826685 µsec
sn-wildmat     says 1 in 4410529 µsec
chris@chris: ~/EIS/SN/sn-0.3.8/lib > 

---[testwm2.c]-----------------------------------------------------------
#include <sys/time.h>
#include <time.h>

#include "wildmat.h"
#include "wildmat2.h"

#define MAX_TRY 100000

int main(void) {
   struct timeval start, stop;
   long i, timediff;
   char *s = "235325235foobaz354325fdhhysfdhdsfh\r\n";
   char *p = "*[Ff][Oo][Oo][Bb][Aa][Rr]*\r\n";
   
   gettimeofday(&start, NULL);
   for (i = 0; i < MAX_TRY; i++) wildmat2(s, p);
   gettimeofday(&stop, NULL);
   timediff = (stop.tv_sec - start.tv_sec) * 1000000 + stop.tv_usec - start.tv_usec;
   printf("diablo-wildmat says %d in %ld µsec\n", wildmat2(s, p), timediff);

   gettimeofday(&start, NULL);
   for (i = 0; i < MAX_TRY; i++) wildmat(s, p);
   gettimeofday(&stop, NULL);
   timediff = (stop.tv_sec - start.tv_sec) * 1000000 + stop.tv_usec - start.tv_usec;
   printf("sn-wildmat     says %d in %ld µsec\n", wildmat(s, p), timediff);

   return 0;
}
-------------------------------------------------------------------------

As you can see the diablo wildmat is around 5-6 times faster in this
case.

In the case of

text    = "-adobe-courier-bold-o-normal--12-120-75-75-X-70-iso8859-1\r\n"
pattern = "-*-*-*-*-*-*-12-*-*-*-m-*-*-*\r\n"

the speedup is 500.

I've included the new wildmat.c, maybe you want to use it in 0.4.0.

---[wildmat2.c]-----------------------------------------------------------
/*
 * This file is part of the sn package.
 * Distribution of sn is covered by the GNU GPL. See file COPYING.
 */

/*
 * Globbing function (borrowed from diablo source).
 */

/*
**    Copyright 1991 Rich Salz.
**    All rights reserved.
**    $Revision: 1.3 $
**
**    Redistribution and use in any form are permitted provided that the
**    following restrictions are are met:
**	1.  Source distributions must retain this entire copyright notice
**	    and comment.
**	2.  Binary distributions must include the acknowledgement ``This
**	    product includes software developed by Rich Salz'' in the
**	    documentation or other materials provided with the
**	    distribution.  This must not be represented as an endorsement
**	    or promotion without specific prior written permission.
**	3.  The origin of this software must not be misrepresented, either
**	    by explicit claim or by omission.  Credits must appear in the
**	    source and documentation.
**	4.  Altered versions must be plainly marked as such in the source
**	    and documentation and must not be misrepresented as being the
**	    original software.
**    THIS SOFTWARE IS PROVIDED ``AS IS'' AND WITHOUT ANY EXPRESS OR IMPLIED
**    WARRANTIES, INCLUDING, WITHOUT LIMITATION, THE IMPLIED WARRANTIES OF
**    MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE.
**
*/

/*  $Revision: 1.3 $
**
**  Do shell-style pattern matching for ?, \, [], and * characters.
**  Might not be robust in face of malformed patterns; e.g., "foo[a-"
**  could cause a segmentation violation.  It is 8bit clean.
**
**  Written by Rich $alz, mirror!rs, Wed Nov 26 19:03:17 EST 1986.
**  Rich $alz is now <[email protected]>.
**  April, 1991:  Replaced mutually-recursive calls with in-line code
**  for the star character.
**
**  Special thanks to Lars Mathiesen <[email protected]> for the ABORT code.
**  This can greatly speed up failing wildcard patterns.  For example:
**	pattern: -*-*-*-*-*-*-12-*-*-*-m-*-*-*
**	text 1:	 -adobe-courier-bold-o-normal--12-120-75-75-m-70-iso8859-1
**	text 2:	 -adobe-courier-bold-o-normal--12-120-75-75-X-70-iso8859-1
**  Text 1 matches with 51 calls, while text 2 fails with 54 calls.  Without
**  the ABORT code, it takes 22310 calls to fail.  Ugh.  The following
**  explanation is from Lars:
**  The precondition that must be fulfilled is that DoMatch will consume
**  at least one character in text.  This is true if *p is neither '*' nor
**  '\0'.)  The last return has ABORT instead of FALSE to avoid quadratic
**  behaviour in cases like pattern "*a*b*c*d" with text "abcxxxxx".  With
**  FALSE, each star-loop has to run to the end of the text; with ABORT
**  only the last one does.
**
**  Once the control of one instance of DoMatch enters the star-loop, that
**  instance will return either TRUE or ABORT, and any calling instance
**  will therefore return immediately after (without calling recursively
**  again).  In effect, only one star-loop is ever active.  It would be
**  possible to modify the code to maintain this context explicitly,
**  eliminating all recursive calls at the cost of some complication and
**  loss of clarity (and the ABORT stuff seems to be unclear enough by
**  itself).  I think it would be unwise to try to get this into a
**  released version unless you have a good test data base to try it out
**  on.
*/
#include <ctype.h>

static const char ver_ctrl_id[] = "$Id$";

#if 1
#define TOLOWER(x) tolower(x) /* case insensitive */
#else
#define TOLOWER(x) x /* case sensitive */
#endif

#define TRUE 1
#define FALSE 0
#define ABORT -1
#define NEGATE_CLASS '^'

/*
**  Match text and p, return TRUE, FALSE, or ABORT.
*/
static int match(char *text, char *p)
{
    int	last;
    int	matched;
    int	reverse;

    for ( ; *p; text++, p++) {
	if (*text == '\0' && *p != '*')
	    return ABORT;
	switch (*p) {
	case '\\':
	    /* Literal match with following character. */
	    p++;
	    /* FALLTHROUGH */
	default:
	    if (TOLOWER(*text) != TOLOWER(*p))
		return FALSE;
	    continue;
	case '?':
	    /* Match anything. */
	    continue;
	case '*':
	    while (*++p == '*')
		/* Consecutive stars act just like one. */
		continue;
	    if (*p == '\0')
		/* Trailing star matches everything. */
		return TRUE;
	    while (*text)
		if ((matched = match(text++, p)) != FALSE)
		    return matched;
	    return ABORT;
	case '[':
	    reverse = p[1] == NEGATE_CLASS ? TRUE : FALSE;
	    if (reverse)
		/* Inverted character class. */
		p++;
	    matched = FALSE;
	    if (p[1] == ']' || p[1] == '-')
		if (TOLOWER(*++p) == TOLOWER(*text))
		    matched = TRUE;
	    for (last = TOLOWER(*p); *++p && *p != ']'; last = TOLOWER(*p))
		/* This next line requires a good C compiler. */
		if (*p == '-' && p[1] != ']'
		    ? TOLOWER(*text) <= TOLOWER(*++p) && TOLOWER(*text) >= last : TOLOWER(*text) == TOLOWER(*p))
		    matched = TRUE;
	    if (matched == reverse)
		return FALSE;
	    continue;
	}
    }

    return *text == '\0';
}

int wildmat(char *candidate, char *pattern) {
   return match(candidate, pattern) == TRUE;
}

#undef TOLOWER
-------------------------------------------------------------------------

so long Chris
-- 
Wenn man vom Gegner gelobt wird, hat man etwas falsch gemacht.