Created
December 3, 2018 21:10
-
-
Save JackyChiu/69ed728d2292d1076c3c9de047c03bdb to your computer and use it in GitHub Desktop.
Pattern Matcher
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
package main | |
// Match accepts a pattern and a string. It will do a full string match base on | |
// the following rules: | |
// | |
// - A non-special character in a pattern matches only that character. | |
// - The special-character `.` in the pattern matches any single character. | |
// - The special-character `?` in the pattern does not match any character, but | |
// indicates the following character in the pattern can match zero or one times. | |
// - The special-character `*` in the pattern does not match any character, but | |
// indicates the following character in the pattern can match zero or more times. | |
// - The special-character `+` in the pattern does not match anything, but | |
// indicates the following character in the pattern can match one or more times. | |
func Match(pattern, str string) (matched bool) { | |
return match(pattern, str) | |
} | |
func match(pattern, str string) bool { | |
if len(pattern) == 0 && len(str) == 0 { | |
// Both are empty; Finished the match! | |
return true | |
} | |
if len(pattern) == 0 || len(str) == 0 { | |
return false | |
} | |
switch pattern[0] { | |
case '?': | |
return matchOptional(pattern[1:], str) | |
case '*': | |
return matchMultiOptional(pattern[1:], str) | |
case '+': | |
return matchMultiLiteral(pattern[1:], str) | |
default: | |
if !matchLiteral(pattern, str) { | |
return false | |
} | |
return match(pattern[1:], str[1:]) | |
} | |
} | |
func matchLiteral(pattern, str string) bool { | |
switch pattern[0] { | |
case '.': | |
return true | |
default: | |
return pattern[0] == str[0] | |
} | |
} | |
func matchOptional(pattern, str string) bool { | |
// Use the optional | |
if match(pattern, str) { | |
return true | |
} | |
// Don't use the optional | |
return match(pattern[1:], str) | |
} | |
func matchMultiLiteral(pattern, str string) (matched bool) { | |
for nextStr := str; len(nextStr) != 0; nextStr = nextStr[1:] { | |
if !matchLiteral(pattern, nextStr) { | |
return false | |
} | |
} | |
return true | |
} | |
func matchMultiOptional(pattern, str string) (matched bool) { | |
for nextStr := str; len(nextStr) != 0; nextStr = nextStr[1:] { | |
if matchOptional(pattern, nextStr) { | |
return true | |
} | |
} | |
return false | |
} |
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
package main | |
import "testing" | |
func TestMatch_literals(t *testing.T) { | |
t.Run("exact match and simple mismatch", func(t *testing.T) { | |
if !Match("abc", "abc") { | |
t.Error("expected match") | |
} | |
if Match("abd", "abc") { | |
t.Error("expected no match") | |
} | |
}) | |
} | |
func TestMatch_anys(t *testing.T) { | |
t.Run("any-char matches", func(t *testing.T) { | |
if !Match("a.c", "a.c") { | |
t.Error("expected match") | |
} | |
if !Match("a.c", "abc") { | |
t.Error("expected match") | |
} | |
}) | |
t.Run("any-char matches with uneven pattern and string", func(t *testing.T) { | |
if Match(".b", "abc") { | |
t.Error("expected no match") | |
} | |
}) | |
} | |
func TestMatch_optionals(t *testing.T) { | |
t.Run("an optional pattern char matches with and without", func(t *testing.T) { | |
if !Match("a?bc", "abc") { | |
t.Error("expected match") | |
} | |
if !Match("a?bc", "ac") { | |
t.Error("expected match") | |
} | |
if Match("a?bcde", "acd") { | |
t.Error("expected no match") | |
} | |
}) | |
t.Run("an optional char that _can_ match is not forced to.", func(t *testing.T) { | |
if !Match("?aab", "ab") { | |
t.Error("expected match") | |
} | |
if !Match("a?bbc", "abc") { | |
t.Error("expected match") | |
} | |
}) | |
} | |
func TestMatch_multi_optionals(t *testing.T) { | |
t.Run("classic log searching", func(t *testing.T) { | |
if !Match("ERROR: *.", "ERROR: file not found") { | |
t.Error("expected match") | |
} | |
if Match("ERROR: *.", "WARNING: file not found") { | |
t.Error("expected no match") | |
} | |
if Match("a*bcde", "abbcd") { | |
t.Error("expected no match") | |
} | |
}) | |
} | |
func TestMatch_multi_literals(t *testing.T) { | |
t.Run("repeated pattern has to match", func(t *testing.T) { | |
if !Match("+.", "abcde") { | |
t.Error("expected match") | |
} | |
if Match("+a_shouldn't_reach_here", "aaa_shouldn't_reach_here") { | |
t.Error("expected no match") | |
} | |
}) | |
} |
Sign up for free
to join this conversation on GitHub.
Already have an account?
Sign in to comment