fix 'exclude' module to avoid strcasecmp, but with performance problems

[Paul Eggert]

I installed the following to fix the 'exclude' module to avoid
strcasecmp, and to modernize it to support FNM_EXTMATCH.

However, here I had some performance problems with mbscasemcp.  Given
two multibyte strings A and B, I want to know whether A is an initial
prefix of B, ignoring case during comparison; also, if A is a prefix
of B, I need to know where in B the prefix ends (because I want to
check that the next char is a '/' in the code below).

This should be an O(N) algorithm, but I don't see an easy way to do
this with the current mbs* primitives.  The code below uses an O(N**2)
algorithm and makes a copy of B, with a FIXME.

2007-02-14  Paul Eggert  <address@hidden>

        * lib/exclude.c (FNM_EXTMATCH): Define if system does not.
        Verify that it doesn't overlap with our flags.
        (fnmatch_no_wildcards): Don't use strcasecmp or strncasecmp, which
        do not have the desired effect in multibyte locales; instead, use
        mbscasecmp.
        * modules/exclude (Depends-on): Depend on mbscasecmp, not strcase.
        Add dependency on xalloc.  Depend on fnmatch, not fnmatch-gnu, since
        we don't require GNU fnmatch ourselves (if our users require it, they
        should do so explicitly).

Index: lib/exclude.c
===================================================================
RCS file: /cvsroot/gnulib/gnulib/lib/exclude.c,v
retrieving revision 1.31
diff -u -p -r1.31 exclude.c
--- lib/exclude.c       26 Jan 2007 22:16:55 -0000      1.31
+++ lib/exclude.c       15 Feb 2007 00:29:03 -0000
@@ -44,13 +44,16 @@
 #ifndef FNM_CASEFOLD
 # define FNM_CASEFOLD 0
 #endif
+#ifndef FNM_EXTMATCH
+# define FNM_EXTMATCH 0
+#endif
 #ifndef FNM_LEADING_DIR
 # define FNM_LEADING_DIR 0
 #endif

 verify (((EXCLUDE_ANCHORED | EXCLUDE_INCLUDE | EXCLUDE_WILDCARDS)
         & (FNM_PATHNAME | FNM_NOESCAPE | FNM_PERIOD | FNM_LEADING_DIR
-           | FNM_CASEFOLD))
+           | FNM_CASEFOLD | FNM_EXTMATCH))
        == 0);

 /* An exclude pattern-options pair.  The options are fnmatch options
@@ -96,14 +99,12 @@ fnmatch_no_wildcards (char const *patter
 {
   if (! (options & FNM_LEADING_DIR))
     return ((options & FNM_CASEFOLD)
-           ? strcasecmp (pattern, f)
+           ? mbscasecmp (pattern, f)
            : strcmp (pattern, f));
-  else
+  else if (! (options & FNM_CASEFOLD))
     {
       size_t patlen = strlen (pattern);
-      int r = ((options & FNM_CASEFOLD)
-               ? strncasecmp (pattern, f, patlen)
-               : strncmp (pattern, f, patlen));
+      int r = strncmp (pattern, f, patlen);
       if (! r)
        {
          r = f[patlen];
@@ -112,6 +113,30 @@ fnmatch_no_wildcards (char const *patter
        }
       return r;
     }
+  else
+    {
+      /* Walk through a copy of F, seeing whether P matches any prefix
+        of F.
+
+        FIXME: This is an O(N**2) algorithm; it should be O(N).
+        Also, the copy should not be necessary.  However, fixing this
+        will probably involve a change to the mbs* API.  */
+
+      char *fcopy = xstrdup (f);
+      char *p;
+      int r;
+      for (p = fcopy; ; *p++ = '/')
+       {
+         p = strchr (p, '/');
+         if (p)
+           *p = '\0';
+         r = mbscasecmp (pattern, fcopy);
+         if (!p || r <= 0)
+           break;
+       }
+      free (fcopy);
+      return r;
+    }
 }

 bool
Index: modules/exclude
===================================================================
RCS file: /cvsroot/gnulib/gnulib/modules/exclude,v
retrieving revision 1.10
diff -u -p -r1.10 exclude
--- modules/exclude     13 Oct 2006 12:40:23 -0000      1.10
+++ modules/exclude     15 Feb 2007 00:29:03 -0000
@@ -7,11 +7,11 @@ lib/exclude.c
 m4/exclude.m4

 Depends-on:
-xalloc
-strcase
-fnmatch-gnu
+fnmatch
+mbscasecmp
 stdbool
 verify
+xalloc

 configure.ac:
 gl_EXCLUDE