Avoid recursion in wildcard comparsion code.

5 files changed, 121 insertions, 73 deletions

diff --git a/src/cmd.c b/src/cmd.c
index 2293e95..236f2b9 100644
--- a/src/cmd.c
+++ b/src/cmd.c
@@ -553,7 +553,7 @@ void Cmd_ExecTrigger( const char *string ) {
     // execute matching triggers
     FOR_EACH_TRIGGER( trigger ) {
         match = Cmd_MacroExpandString( trigger->match, qfalse );
-        if( match && Com_WildCmp( match, string, qfalse ) ) {
+        if( match && Com_WildCmp( match, string ) ) {
             Cbuf_AddText( &cmd_buffer, trigger->command );
             Cbuf_AddText( &cmd_buffer, "\n" );
         }
@@ -1678,7 +1678,7 @@ static void Cmd_List_f( void ) {
     i = total = 0;
     FOR_EACH_CMD( cmd ) {
         total++;
-        if( filter && !Com_WildCmp( filter, cmd->name, qfalse ) ) {
+        if( filter && !Com_WildCmp( filter, cmd->name ) ) {
             continue;
         }
         Com_Printf( "%s\n", cmd->name );
@@ -1704,7 +1704,7 @@ static void Cmd_MacroList_f( void ) {
 
     i = 0;
     for( macro = cmd_macros, total = 0; macro; macro = macro->next, total++ ) {
-        if( filter && !Com_WildCmp( filter, macro->name, qfalse ) ) {
+        if( filter && !Com_WildCmp( filter, macro->name ) ) {
             continue;
         }
         macro->function( buffer, sizeof( buffer ) );
diff --git a/src/com_local.h b/src/com_local.h
index 6e1483b..e04347e 100644
--- a/src/com_local.h
+++ b/src/com_local.h
@@ -515,7 +515,9 @@ void        Com_Color_g( genctx_t *ctx );
 #endif
 void        Com_PlayerToEntityState( const player_state_t *ps, entity_state_t *es );
 
-int         Com_WildCmp( const char *filter, const char *string, qboolean ignoreCase );
+qboolean    Com_WildCmpEx( const char *filter, const char *string, int term, qboolean ignorecase );
+#define Com_WildCmp( filter, string )  Com_WildCmpEx( filter, string, 0, qfalse )
+
 unsigned    Com_HashString( const char *s, unsigned size );
 
 qboolean    Prompt_AddMatch( genctx_t *ctx, const char *s );
diff --git a/src/common.c b/src/common.c
index 5bd1914..e6c803a 100644
--- a/src/common.c
+++ b/src/common.c
@@ -1140,6 +1140,119 @@ int BoxOnPlaneSide( vec3_t emins, vec3_t emaxs, cplane_t *p ) {
 }
 #endif // USE_ASM
 
+/*
+==============================================================================
+
+                        WILDCARD COMPARE
+
+==============================================================================
+*/
+
+static qboolean match_char( int c1, int c2, qboolean ignorecase ) {
+    if( c1 == '?' ) {
+        return !!c2; // match any char except NUL
+    }
+
+    if( c1 != c2 ) {
+        if( !ignorecase ) {
+            return qfalse;
+        }
+#ifdef _WIN32
+        // ugly hack for file listing
+        c1 = c1 == '\\' ? '/' : Q_tolower( c1 );
+        c2 = c2 == '\\' ? '/' : Q_tolower( c2 );
+#else
+        c1 = Q_tolower( c1 );
+        c2 = Q_tolower( c2 );
+#endif
+        if( c1 != c2 ) {
+            return qfalse;
+        }
+    }
+
+    return qtrue;
+}
+
+static qboolean match_part( const char *filter, const char *string, size_t len, qboolean ignorecase ) {
+    do {
+        int c1 = *filter++;
+        int c2 = *string++;
+
+        if( !match_char( c1, c2, ignorecase ) ) {
+            return qfalse;
+        }
+    } while( --len );
+
+    return qtrue;
+}
+
+// match the longest possible part
+static const char *match_filter( const char *filter, const char *string, size_t len, qboolean ignorecase ) {
+    const char *ret = NULL;
+    size_t remaining = strlen( string );
+
+    while( remaining >= len ) {
+        if( match_part( filter, string, len, ignorecase ) ) {
+            string += len;
+            remaining -= len;
+            ret = string;
+            continue;
+        }
+        string++;
+        remaining--;
+    }
+
+    return ret;
+}
+
+/*
+=================
+Com_WildCmpEx
+
+Wildcard compare.
+Returns non-zero if matches, zero otherwise.
+=================
+*/
+qboolean Com_WildCmpEx( const char *filter, const char *string, int term, qboolean ignorecase ) {
+    const char *sub;
+    size_t len;
+
+    while( *filter && *filter != term ) {
+        if( *filter == '*' ) {
+            // skip consecutive wildcards
+            do {
+                filter++;
+            } while( *filter == '*' );
+
+            // wildcard at the end matches everything
+            if( !*filter || *filter == term ) {
+                return qtrue;
+            }
+
+            // scan out filter part to match
+            sub = filter; len = 0;
+            do {
+                filter++; len++;
+            } while( *filter && *filter != term && *filter != '*' );
+
+            string = match_filter( sub, string, len, ignorecase );
+            if( !string ) {
+                return qfalse;
+            }
+        } else {
+            int c1 = *filter++;
+            int c2 = *string++;
+
+            // match single character
+            if( !match_char( c1, c2, ignorecase ) ) {
+                return qfalse;
+            }
+        }
+    }
+
+    // match NUL at the end
+    return !*string;
+}
 
 /*
 ==============================================================================
@@ -1201,30 +1314,6 @@ void Com_PlayerToEntityState( const player_state_t *ps, entity_state_t *es ) {
 }
 
 /*
-=================
-Com_WildCmp
-
-Wildcard compare.
-Returns non-zero if matches, zero otherwise.
-=================
-*/
-int Com_WildCmp( const char *filter, const char *string, qboolean ignoreCase ) {
-    switch( *filter ) {
-    case '\0':
-        return !*string;
-
-    case '*':
-        return Com_WildCmp( filter + 1, string, ignoreCase ) || (*string && Com_WildCmp( filter, string + 1, ignoreCase ));
-
-    case '?':
-        return *string && Com_WildCmp( filter + 1, string + 1, ignoreCase );
-
-    default:
-        return ((*filter == *string) || (ignoreCase && (Q_toupper( *filter ) == Q_toupper( *string )))) && Com_WildCmp( filter + 1, string + 1, ignoreCase );
-    }
-}
-
-/*
 ================
 Com_HashString
 ================
diff --git a/src/cvar.c b/src/cvar.c
index 7c1e425..0448219 100644
--- a/src/cvar.c
+++ b/src/cvar.c
@@ -843,7 +843,7 @@ static void Cvar_List_f( void ) {
         if( mask && !( var->flags & mask ) ) {
             continue;
         }
-        if( wildcard && !Com_WildCmp( wildcard, var->name, qtrue ) ) {
+        if( wildcard && !Com_WildCmp( wildcard, var->name ) ) {
             continue;
         }
         if( modified && ( !strcmp( var->latched_string ? var->latched_string :
diff --git a/src/files.c b/src/files.c
index ab1852b..336ee7e 100644
--- a/src/files.c
+++ b/src/files.c
@@ -2118,52 +2118,9 @@ void **FS_CopyList( void **list, int count ) {
     return out;
 }
 
-#if 0
-// foo*bar
-// foobar
-// fooblahbar
-static qboolean FS_WildCmp_r( const char *filter, const char *string ) {
-    while( *filter && *filter != ';' ) {
-        if( *filter == '*' ) {
-            return FS_WildCmp_r( filter + 1, string ) ||
-                ( *string && FS_WildCmp_r( filter, string + 1 ) );
-        }
-        if( *filter == '[' ) {
-            filter++;
-            
-            continue;
-        }
-        if( *filter != '?' && Q_toupper( *filter ) != Q_toupper( *string ) ) {
-            return qfalse;
-        }
-            filter++;
-            string++;
-    }
-
-    return !*string;
-}
-#endif
-
-static int FS_WildCmp_r( const char *filter, const char *string ) {
-    switch( *filter ) {
-    case '\0':
-    case ';':
-        return !*string;
-
-    case '*':
-        return FS_WildCmp_r( filter + 1, string ) || (*string && FS_WildCmp_r( filter, string + 1 ));
-
-    case '?':
-        return *string && FS_WildCmp_r( filter + 1, string + 1 );
-
-    default:
-        return ((*filter == *string) || (Q_toupper( *filter ) == Q_toupper( *string ))) && FS_WildCmp_r( filter + 1, string + 1 );
-    }
-}
-
 qboolean FS_WildCmp( const char *filter, const char *string ) {
     do {
-        if( FS_WildCmp_r( filter, string ) ) {
+        if( Com_WildCmpEx( filter, string, ';', qtrue ) ) {
             return qtrue;
         }
         filter = strchr( filter, ';' );