Algoritmo para búsquedas con comodines (wildcards)

Recientemente andaba yo enredado en un proyecto personal de poca trascendencia pero que me obligó a hacer una implementación completa de un sistema de archivos FAT a bajo nivel.

La FAT es un sistema de archivos muy simple para los estándares de hoy y la implementación fue muy fácil y rápida.

Sin embargo, en el proyecto además se necesitaba agregar algunas funciones típicas de sistemas operativos de sabor Microsoft, entre ellas la habitual búsqueda por comodines o wildcard. Pues esto, que parece una tontería, me tuvo filosofando para su implementación más tiempo que casi el resto de la implementación.

Se me ocurrieron diferentes acercamientos al problema de interpretar una cadena cualquiera que usase el comodín asterisco (*) para sustituir una subcadena cualquiera y el interrogante (?) para sustituir cualquier carácter coincidente en esa posición. Pensé en aplicar mis oxidados conocimientos de autómatas y lenguajes, o también una simple rutina al estilo amateur a base de recorrer las cadenas con un bucle e ir contando caracteres e intentando cuadrarlo todo usando código spaghetti.

Pero finalmente opté por la implementación más sencilla y elegante, si bien no la más eficiente: convertir los viejos comodines de tipo DOS a expresiones regulares de las que hoy en día se usan para todo. Cualquier lenguaje de programación moderno permite el uso de regex cuyo parseo es transparente para el programador.

Para ello basta con buscar las equivalencias necesarias entre comodines DOS y expresiones regulares o regex:

Función	Wildcard	Regex
Sustituye un carácter en la posición indicada	?	[^\.]
Sustituye una secuencia cualquiera de caracteres	*	.*
Separador de extensión	.	\.
Punto sin extensión final	*.	[^\.]+\.?

Además, si se trata de una regex en un entorno POSIX, es probable que para que la coincidencia de la cadena buscada sea haga desde las posiciones indicadas de cada comodín comenzando por el primer carácter de la cadena (y no en cualquier lugar de la misma), haya que agregar el metacarácter ^ al comienzo de la expresión.

De esta forma, la conversión entre wildcards y regex puede verse ilustrada en los siguientes ejemplos:

Descripción	Wildcards	Regex
Cualquier archivo con cualquier extensión	*.*	^.*\..*
Todos los archivos que comiencen por A	A*.*	^A.*\..*
Todos los archivos con extensión jpg que comiencen por pic y dos caracteres más	pic??.jpg	^pic..\.jpg
Archivos que comiencen por "abc" y NO tengan extensión	abc*.	abc*[^\.]+\.?

El código 

Para transformar los comodines en expresiones regulares hemos visto que basta cualquier tipo de sustitución simple, incluso la que hace un editor de texto con sus macros correspondientes. El lenguaje Perl tiene, como parte de su propia sintaxis, el manejo de expresiones regulares. También existen en Java, Javascript, c#, PHP y casi cualquiera que se precie.

No obstante, en mi ejemplo yo usaré lenguaje C ansi por ser un estándar y porque además era el lenguaje usado en mi proyecto.

#include <string.h>
#include <regex.h>
/*
 *Esta función recorre el patrón basado en comodines y los sustituye por sus equivalencias regex
 */
char * wildcard_to_regex(char * pattern) {
    if (pattern) {
        int len = strlen(pattern);
        char * regstr = malloc(200);
        int r = 0;
        regstr[r++] = '^';
        for (int i = 0; i < len; i++) {
            switch ( * (pattern + i)) {
            case '*': //*  [^\.]+\.?
                if ( * (pattern + i + 1) == '.' && (i == (len - 1))) {
                    regstr[r++] = '[';
                    regstr[r++] = '^';
                    regstr[r++] = '\\';
                    regstr[r++] = '.';
                    regstr[r++] = ']';
                    regstr[r++] = '+';
                    regstr[r++] = '\\';
                    regstr[r++] = '.';
                    regstr[r++] = '?';
                } else {
                    regstr[r++] = '.';
                    regstr[r++] = '*';
                }
                break;
            case '?': //[^\.]
                regstr[r++] = '[';
                regstr[r++] = '^';
                regstr[r++] = '\\';
                regstr[r++] = '.';
                regstr[r++] = ']';
                break;
            case '.': //\.
                regstr[r++] = '\\';
                regstr[r++] = '.';
                break;
            default:
                regstr[r++] = * (pattern + i);
            }
        }
        regstr[r++] = '$';
        regstr[r] = '\0';
        return regstr;
    } else {
        return NULL;
    }
}
/*
 *En esta función se comprueba si el nombre de archivo o cadena coincide con la expresión regex dada
 */
bool pattern_matches(char * filename, char * mask) {
    regex_t regex;
    regcomp( & regex, wildcard_to_regex(mask), REG_ICASE);
    if (!regexec( & regex, filename, 0, NULL, 0)) {
        return true;
    } else {
        return false;
    }
}

Ambas funciones se utilizarían para construir la expresión regular a partir de un patrón de búsqueda por comodines y para comprobar si una cadena dada (por ejemplo, un nombre de archivo) concuerda con dicha expresión regular:

void main (int argc, char *argv[])
{
    if (pattern_matches(argv[1], wilcard_to_regex("test*.*") )
    {
        // el archivo especificado en la línea de comandos
        // concuerda con la máscara "test*.*"
    } else {
        // el archivo no concuerda
    }
}