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

static bool        
is_match(const char *restrict patt, const char *restrict str);

typedef struct Testdata{
    char    *p, *str;
    bool    matched;
} Testdata;

// Search if s is matched to pattern p
int                main(int argc, char *argv[]){
    bool real_mode = argc  != 1;     // true if real mode, false if test mode
    
    if (real_mode && argc < 3){
        fprintf(stderr, "Usage: %s 'string' 'pattern'\n", *argv);
        return 1;
    }
    
    if (real_mode){
        if (is_match(argv[2], argv[1]))
            printf("Lines matched!\n");
        else 
            printf("Line not matched\n");
        return 0;
    } else {
        Testdata dt[] = (Testdata[]) {
            [0].p = "abcde",        [0].str = "abcde",                          [0].matched = true
          , [1].p = "abcd?",        [1].str = "abcde",                          [1].matched = true
          , [2].p = "abcd?d",       [2].str = "abcde",                          [2].matched = false
          , [3].p = "*",            [3].str = "abcde",                          [3].matched = true
          , [4].p = "abc*xy",       [4].str = "abcqwewweqewqeqeeqeeeqxy",       [4].matched = true
          , [5].p = "abc*xy",       [5].str = "abc11111111xf22222xb33333xy",    [5].matched = true
          , [6].p = "abc*xy",       [6].str = "abcxyz",                         [6].matched = false
          , [7].p = "abc*xy*xz",    [7].str = "abcxy1111z11x11x222x22xz",       [7].matched = true
          , [8].p = "abc*xy*xz",    [8].str = "abcxy1111z11x11x222x22x",       [8].matched = false
          , [9].p = "abc*xy*xz*",   [9].str = "abcxy1111z11x11x222x22xzppppp",  [9].matched = true
        };
        int     failed = 0, total = sizeof dt/sizeof(Testdata);
        for (int i = 0; i < total; i++)
            if (is_match(dt[i].p, dt[i].str) != dt[i].matched){
                printf("Failed (%d): [%s] [%s] must be %s\n", i, dt[i].p, dt[i].str, dt[i].matched?"matched": "not matched");
                failed++;
            }
        printf("Total tests %d, failed %d\n", total, failed);
        return failed == 0;
    }
}

// end of substring 
static inline bool 
is_end(char c){
    return c == '\0' || c == '*';
}


// returns pos of not-match sym (or last pos of substring if matched)
// s1 - pattern side
static int         
is_submatch(const char *restrict s1, const char *restrict s2, bool *restrict matched){
    int     i = 0;
    while (!is_end(s1[i]) && 
           s2[i] != '\0'  && 
           (s1[i] == s2[i] || s1[i] == '?')    // only s1 has pattern ability
          )
        i++;
    if (matched){
        if (is_end(s1[i]) 
            // && s2[i] == '\0'
           )
            *matched = true;
        else
            *matched = false;
    }
    return i;
}

// skip str till symbol n of till the end of line
static int          
skip_to(const char *str, char c){
    int     i = 0;
    while (str[i] && str[i] != c)
        i++; 
    return i;
}

               //   abc*az
               //   abcdddddaxtttttaz

// assumption: patt and str has at lease 1 sym
static bool         
is_match(const char *restrict patt, const char *restrict str){
   int     i = is_submatch(patt, str, 0);
   patt += i;  str += i;
   while (*patt == '*') {
        while (*patt == '*')
            patt++;
        char next = *patt;      // even if '\0'
        bool matched = false;
        do {
            i = 0;      // to avoid confustion with prev run
            str += skip_to(str, next);
            if (*str == '\0')
                break;
            i = is_submatch(patt, str, &matched);
            if (!matched)
                str++;  // go to next symbol
        } while (!matched);
        patt += i; str += i;    
    };
    if (*str != '\0' || *patt != '\0')
        return false;
    else
        return true;
}