Simple recursion-based wildcard matching

wildcard.c

/*
 * Wildcard matching program in recursive algorithm.
 *
 * Copyright 2018 Keisuke Fukuda
 *
 * Permission is hereby granted, free of charge, to any person
 * obtaining a copy of this software and associated documentation
 * files (the "Software"), to deal in the Software without
 * restriction, including without limitation the rights to use, copy,
 * modify, merge, publish, distribute, sublicense, and/or sell copies
 * of the Software, and to permit persons to whom the Software is
 * furnished to do so, subject to the following conditions:
 *
 * The above copyright notice and this permission notice shall be
 * included in all copies or substantial portions of the Software.
 *
 * THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND,
 * EXPRESS OR IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF
 * MERCHANTABILITY, FITNESS FOR A PARTICULAR PURPOSE AND
 * NONINFRINGEMENT. IN NO EVENT SHALL THE AUTHORS OR COPYRIGHT HOLDERS
 * BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER LIABILITY, WHETHER IN AN
 * ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING FROM, OUT OF OR IN
 * CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN THE
 * SOFTWARE.
 */

#include <stdlib.h>
#include <stdio.h>
#include <string.h>
#include <assert.h>

#if __STDC_VERSION__ >= 199901L
#include <stdbool.h>
#else
typedef unsigned short _Bool;
#define true 1
#define false 0
#endif

#define SINGLE_MATCH '?'
#define MULTI_MATCH '*'


_Bool match(const char *pat_beg, const char *pat_end, const char *target) {
    size_t pat_len = pat_end - pat_beg;
    size_t trg_len = strlen(target);

    if (pat_len == 0) {
        /* If the pattern is empty */
        if (trg_len == 0) {
            return true;
        } else {
            return false;
        }
    }

    switch(*pat_beg) {
        case MULTI_MATCH:
            if (pat_len == 1) {
                return true;
            } else if (trg_len == 0) {
                /* pat_len > 1 and target == "" */
                return match(pat_beg + 1, pat_end, target);
            } else {
                /* pat_len > 1 && trg_len > 0 */
                return match(pat_beg + 1, pat_end, target) || match(pat_beg, pat_end, target + 1);
            }
            break;
        case SINGLE_MATCH:
            if (trg_len == 0) {
                return false;
            } else {
                return match(pat_beg + 1, pat_end, target + 1);
            }
            break;
        case '\0':
            return trg_len == 0 ? true : false;
            break;
        default:
            assert(pat_len > 0);
            if (trg_len == 0) {
                return 0;
            } else if (*pat_beg == *target) {
                return match(pat_beg + 1, pat_end, target + 1);
            } else {
                return false;
            }
    }
}


static int count_ok = 0;
static int count_ng = 0;

void assert_true(const char *pat, const char *target) {
    size_t pat_len = strlen(pat);
    const char *pat_end = pat + pat_len;
    if (match(pat, pat_end, target)) {
        count_ok++;
    } else {
        count_ng++;
        printf("*** failed: '%s' should match '%s'\n", pat, target);
    }
}

void assert_false(const char *pat, const char *target) {
    size_t pat_len = strlen(pat);
    const char *pat_end = pat + pat_len;
    if (!match(pat, pat_end, target)) {
        count_ok++;
    } else {
        count_ng++;
        printf("*** failed: '%s' should NOT match '%s'\n", pat, target);
    }
}

int main() {
    assert_true("", "");
    assert_false("", "a");
    assert_false("", "aa");

    assert_true("*", "");
    assert_true("*", "a");
    assert_true("*", "1");
    assert_true("*", "aaa");
    assert_true("*", " ");

    assert_true("*a", "a");
    assert_true("*a", "ba");
    assert_true("*a", "baa");
    assert_true("*a", "bba");

    assert_false("*a", "");
    assert_false("*a", "b");
    assert_false("*a", "ab");

    assert_true("*a*", "a");
    assert_true("*a*", "ab");
    assert_true("*a*", "bab");
    assert_true("*a*", "aba");
    assert_true("*a*", "bbbabbb");
    assert_true("*a*", "bbaaabb");

    assert_true("**a*", "a");
    assert_true("**a*", "ab");
    assert_true("**a*", "bab");
    assert_true("**a*", "aba");
    assert_true("**a*", "bbbabbb");
    assert_true("**a*", "bbaaabb");

    assert_true("**a**", "a");
    assert_true("**a**", "ab");
    assert_true("**a**", "bab");
    assert_true("**a**", "aba");
    assert_true("**a**", "bbbabbb");
    assert_true("**a**", "bbaaabb");

    assert_false("*a*", "");
    assert_false("*a*", "b");
    assert_false("*a*", "bb");

    assert_true("a*a", "aa");
    assert_true("a*a", "aaa");
    assert_true("a*a", "aba");

    assert_false("a*a", "");
    assert_false("a*a", "ab");
    assert_false("a*a", "ba");
    assert_false("a*a", "aab");
    assert_false("a*a", "baa");

    assert_true("*a*b", "ab");
    assert_true("*a*b", "acb");
    assert_true("*a*b", "dacb");

    assert_false("*a*b", "abc");
    assert_false("*a*b", "cabc");
    assert_false("*a*b", "cba");

    assert_true("**", "");
    assert_true("**", "a");
    assert_true("**", "aa");
    assert_true("**", "aaa");
    assert_true("**", "aaabbb");
    assert_true("**", "aaabbbaaa");

    assert_true("***", "");
    assert_true("***", "a");
    assert_true("***", "aa");
    assert_true("***", "aaa");
    assert_true("***", "aaabbb");
    assert_true("***", "aaabbbaaa");

    assert_true("?", "a");
    assert_false("?", "");
    assert_false("?", "aa");
    assert_false("?", "aaa");

    assert_true("??", "ab");
    assert_true("??", "aa");
    assert_false("??", "");
    assert_false("??", "aaa");

    assert_true("a?", "aa");
    assert_true("a?", "ab");

    printf("OK %d\n", count_ok);
    printf("NG %d\n", count_ng);
}