Compile-time wildcard pattern matching

Question

I was in need of a function that could check a string against a certain pattern at compile-time. The pattern can contain any of the commonly known wildcards: ?, * and +.

• ? - match any character.
• * - match any sequence of characters, including the empty string.
• + - equal to ?*

I'm not sure how to test my code for errors, is there a set of patterns and strings that will determine (with 100% certainty) nothing is wrong with my code? If not, could any of you spare a moment and check my code for errors?

I've tested this code and it seems to work fine. Also, is this a good way of implementing compile-time functionality?

Compiled with: clang++ -std=c++11

Just as a help to more easily get into this code, I've tried to write the syntax in such a way to represent an if-elseif chain. The indentation shows the level of nesting.

constexpr int MatchPattern_Rec(const char* pattern, const char* text) {
    return *pattern == '\0' || *text == '\0' ? *pattern == *text :
            *pattern == '?' ? MatchPattern_Rec(pattern+1, text+1) :
            *pattern == '*' ? 
                MatchPattern_Rec(pattern+1, text) ? 1 :
                MatchPattern_Rec(pattern, text+1) ? 1 :
                0 :
            *pattern == '+' ?
                MatchPattern_Rec(pattern+1, text+1) ? 1 :
                MatchPattern_Rec(pattern, text+1) ? 1 :
                0 :
            *pattern == *text ? MatchPattern_Rec(pattern+1, text+1) :
            0;
}

constexpr int MatchPattern(const char* pattern, const char* text) {
    return *pattern == '\0' ? 0 :
            *pattern == '*' && *(pattern+1) == '\0' && *text == '\0' ? 1 :
            MatchPattern_Rec(pattern, text);
}

Some side notes:

1. The code will only be run when compiling debug builds. Performance is the least of my worries.
2. The strings and patterns will be limited in size (max. 50 characters) and the patterns will have 5 wildcards at most. The stack should be big enough to handle that level of recursion.

Answer 1

I am not most experienced with C++ (java's my best language) but as far as I know, method names are supposed to be camelCase. MatchPattern_Rec should be matchPatternRec.

Also, why are you returning a 1 or a 0? Shouldn't you be returning a bool? (Again, correct me if I'm wrong)

The chain of ternary operators is very unreadable and messy, which causes easy bugs. You are also using ternary in places you can just use || and &&. Use if and switch statements to simplify:

constexpr bool matchPatternRec(const char* pattern, const char* text) {
    if (*pattern == '\0' || *text == '\0') {
        return *pattern == *text;
    }
    switch (*pattern) {
    case '?':
        return matchPatternRec(pattern + 1, text + 1);
    case '*':
        return matchPatternRec(pattern + 1, text) ||
                matchPatternRec(pattern, text + 1);
    case '+':
        return matchPatternRec(pattern + 1, text + 1) ||
                matchPatternRec(pattern, text + 1);
    default:
        return *pattern == *text && matchPatternRec(pattern + 1, text + 1);
    }
}

constexpr int matchPattern(const char* pattern, const char* text) {
    if (*pattern == '\0') {
        return false;
    }
    return (*pattern == '*' && *(pattern+1) == '\0' && *text == '\0') ||
            matchPatternRec(pattern, text);
}