# Compile-time wildcard pattern matching

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.
• @SirPython Thank you! This code runs fine, I've already discovered a bug or two and corrected them. I'm certainly not asking to debug this, I'm only asking for second opinions on my code. – Maarten Bamelis Oct 25 '15 at 21:17

I am not most experienced with C++ ('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);
}

• Yes, my naming is a bit off and I could return booleans but 1's and 0's also work (the code I used as an example also returned 1's and 0's, so yeah I copied that guy). For the ternary operators; keep in mind that this is code that gets executed at compile-time; using if-else and switches cause the following warning use of this statement in a constexpr function is a C++1y extension [-Wc++1y-extensions]; and I'd like to stick to the standard C++11 for now. Again, thanks for your feedback. – Maarten Bamelis Nov 1 '15 at 13:00
• @Deduplicator whoops, I didn't edit the naming in the final code. Will fix. – TheCoffeeCup Nov 8 '15 at 2:09