Fix a corner case of superset matching

The algorithm we're using gets stuck if it has a ? and can only see a *
to feed to it, even if it could skip over that * and consume a character
following it. Remedy this by rearranging the input so * always precedes
? in runs of wildcards, so when we're matching ? we know we can skip
things.

diff --git a/ircd/match.c b/ircd/match.c
index a8165ffb22c0b2c08f42202f94be192ca413c942..417e2ccd3405ee6c12c646a706ae0d36363335fb 100644 (file)
--- a/ircd/match.c
+++ b/ircd/match.c
@@ -104,6 +104,30 @@ int match(const char *mask, const char *name)
        }
 }
 
+void
+match_arrange_stars(char *mask)
+{
+       char *swap = NULL;
+
+       for (char *p = mask; *p != '\0'; p++)
+       {
+               switch (*p)
+               {
+               case '*':
+                       if (swap == NULL) break;
+                       *swap++ = '*';
+                       *p = '?';
+                       break;
+               case '?':
+                       if (swap == NULL) swap = p;
+                       break;
+               default:
+                       swap = NULL;
+                       break;
+               }
+       }
+}
+
 /** Check a mask against a mask.
  * This test checks using traditional IRC wildcards only: '*' means
  * match zero or more characters of any type; '?' means match exactly
@@ -115,15 +139,19 @@ int match(const char *mask, const char *name)
  * @param[in] name New wildcard-containing mask.
  * @return 1 if \a name is equal to or more specific than \a mask, 0 otherwise.
  */
-int mask_match(const char *mask, const char *name)
+int mask_match(const char *mask_, const char *name)
 {
+       static char mask[BUFSIZE];
        const char *m = mask, *n = name;
        const char *m_tmp = mask, *n_tmp = name;
        int star_p;
 
-       s_assert(mask != NULL);
+       s_assert(mask_ != NULL);
        s_assert(name != NULL);
 
+       rb_strlcpy(mask, mask_, sizeof mask);
+       match_arrange_stars(mask);
+
        for (;;)
        {
                switch (*m)
@@ -146,6 +174,7 @@ int mask_match(const char *mask, const char *name)
                                  else if (*m == '?')
                                  {
                                          /* changed for mask_match() */
+                                         while (star_p && *n == '*') n++;
                                          if (*n == '*' || !*n)
                                                  goto backtrack;
                                          n++;

diff --git a/tests/match1.c b/tests/match1.c
index 9d118ed63193a9ba211532e4a940ee90a2268cd0..913f71d7b1666e6b8941b7a5022f7d7623d80bfc 100644 (file)
--- a/tests/match1.c
+++ b/tests/match1.c
@@ -30,6 +30,8 @@
 
 struct Client me;
 
+void match_arrange_stars(char *);
+
 static void test_match(void)
 {
        is_int(0, match("*foo*", "bar"), MSG);
@@ -40,6 +42,7 @@ static void test_match(void)
 
 static void test_mask_match(void)
 {
+
        is_int(0, mask_match("*foo*", "bar"), MSG);
        is_int(1, mask_match("*foo*", "foo"), MSG);
 
@@ -63,12 +66,32 @@ static void test_mask_match(void)
        is_int(0, mask_match("??", "aaa"), MSG);
 }
 
+static void test_arrange_stars(void)
+{
+       {
+               char rearrange[] = "quick brown fox";
+               match_arrange_stars(rearrange);
+               is_string("quick brown fox", rearrange, MSG);
+       }
+       {
+               char rearrange[] = "?*?*?*";
+               match_arrange_stars(rearrange);
+               is_string("***???", rearrange, MSG);
+       }
+       {
+               char rearrange[] = "?*? *?*";
+               match_arrange_stars(rearrange);
+               is_string("*?? **?", rearrange, MSG);
+       }
+}
+
 int main(int argc, char *argv[])
 {
        plan_lazy();
 
        test_match();
        test_mask_match();
+       test_arrange_stars();
 
        return 0;
 }