Pattern Matcher

matcher.go

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
}

matcher_test.go

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")
		}
	})
}