go-redis/lib/wildcard/wildcard.go

// Package wildcard 实现了通配符模式匹配功能
package wildcard

const (
	normal     = iota // 普通字符
	all               // * 匹配任意数量字符
	anySymbol         // ? 匹配单个字符
	setSymbol         // [] 字符集匹配
	rangSymbol        // [a-b] 范围匹配
	negSymbol         // [^a] 否定匹配
)

// item 表示模式中的一个元素
type item struct {
	character byte          // 字符值
	set       map[byte]bool // 字符集合
	typeCode  int           // 类型码
}

// contains 检查字符是否匹配当前元素
func (i *item) contains(c byte) bool {
	switch i.typeCode {
	case setSymbol:
		_, ok := i.set[c]
		return ok
	case rangSymbol:
		if _, ok := i.set[c]; ok {
			return true
		}
		var (
			_min byte = 255
			_max byte = 0
		)
		for k := range i.set {
			if _min > k {
				_min = k
			}
			if _max < k {
				_max = k
			}
		}
		return c >= _min && c <= _max
	case negSymbol:
		_, ok := i.set[c]
		return !ok
	default:
		return false
	}
}

// Pattern 表示一个通配符模式
type Pattern struct {
	items []*item
}

// CompilePattern 将通配符字符串转换为Pattern对象
//
//	支持的通配符:
//	* - 匹配任意数量的字符(包括空字符)
//	? - 匹配单个字符
//	[] - 匹配括号内任意一个字符，如[abc]
//	[a-b] - 匹配范围内的任意字符
//	[^a] - 匹配除括号内字符外的任意字符
//	\ - 转义字符
func CompilePattern(src string) *Pattern {
	items := make([]*item, 0, len(src)) // 预分配容量
	escape := false
	inSet := false
	var set map[byte]bool

	for _, v := range src {
		c := byte(v)
		if escape {
			// 处理转义字符
			items = append(items, &item{typeCode: normal, character: c})
			escape = false
		} else if c == '*' {
			// 匹配任意数量字符
			items = append(items, &item{typeCode: all})
		} else if c == '?' {
			// 匹配单个字符
			items = append(items, &item{typeCode: anySymbol})
		} else if c == '\\' {
			// 转义下一个字符
			escape = true
		} else if c == '[' {
			// 开始字符集定义
			if !inSet {
				inSet = true
				set = make(map[byte]bool)
			} else {
				set[c] = true
			}
		} else if c == ']' {
			// 结束字符集定义
			if inSet {
				inSet = false
				typeCode := setSymbol
				if _, ok := set['-']; ok {
					typeCode = rangSymbol
					delete(set, '-')
				}
				if _, ok := set['^']; ok {
					typeCode = negSymbol
					delete(set, '^')
				}
				items = append(items, &item{typeCode: typeCode, set: set})
			} else {
				items = append(items, &item{typeCode: normal, character: c})
			}
		} else {
			if inSet {
				set[c] = true
			} else {
				items = append(items, &item{typeCode: normal, character: c})
			}
		}
	}
	return &Pattern{
		items: items,
	}
}

// IsMatch 检查给定字符串是否匹配该模式
// 使用动态规划算法实现
func (p *Pattern) IsMatch(s string) bool {
	if len(p.items) == 0 {
		return len(s) == 0
	}

	m := len(s)
	n := len(p.items)

	// 使用二维布尔数组进行动态规划
	table := make([][]bool, m+1)
	for i := range table {
		table[i] = make([]bool, n+1)
	}

	// 初始化基本情况
	table[0][0] = true

	// 处理空字符串与模式的匹配情况
	for j := 1; j <= n; j++ {
		if p.items[j-1].typeCode == all {
			table[0][j] = table[0][j-1]
		}
	}

	// 填充动态规划表
	for i := 1; i <= m; i++ {
		for j := 1; j <= n; j++ {
			switch p.items[j-1].typeCode {
			case all:
				// * 可以匹配空字符串或多个字符
				table[i][j] = table[i-1][j] || table[i][j-1]
			case anySymbol:
				// ? 匹配任意单个字符
				table[i][j] = table[i-1][j-1]
			case normal:
				// 普通字符精确匹配
				table[i][j] = table[i-1][j-1] && s[i-1] == p.items[j-1].character
			default:
				// 集合类匹配 [abc], [a-z], [^a] 等
				table[i][j] = table[i-1][j-1] && p.items[j-1].contains(s[i-1])
			}
		}
	}

	return table[m][n]
}