spring 中的路径匹配

在 spring 中，不管是注解使用时配置的基础包扫描路径，还是在 spring MVC 中根据路径匹配到具体的 handler，都会使用到路径匹配，今天我们来看下 spring 中的路径匹配到底是如何实现的。

glob pattern 语法

spring 借鉴了一种称之为 glob pattern 的语法，这是一种常用的匹配文件路径的模式语法，通过简单的规则来匹配文件名、路径名等，实现文件的查找、筛选等操作。常用在 Unix/Linux 系统的 shell 编程中。

下面我们来详细看下语法：

在 glob pattern 常用的特殊字符只有三个，'?'、'*'、'{'，含义如下：

• ?  匹配一个字符
• *  匹配零个或多个字符
• {xxx, xxx} 匹配 {} 中任意一组字符 

spring 中的实现

在 spring 中定义了基于字符串的路径匹配的接口，org.springframework.util.PathMatcher，目前只有一个实现类，org.springframework.util.AntPathMatcher，所以接下来我们所描述的路径匹配实现都是基于 AntPathMatcher。 

在 AntPathMatcher 中，匹配规则如下：

• ? 匹配单个任意字符
• *  匹配零个或多个任意字符
• ** 匹配单个或多个路径中的文件夹，即匹配当前包及其子包
• {spring:[a-z]+} 匹配regexp [a-z]+作为名为"spring"的路径变量

在 AntPathMatcher 中定义了是否采用此种匹配规则的方法 AntPathMatcher#isPattern，其实就是判断路径中是否存在规则中出现的三个特殊字符。

@Override
public boolean isPattern(@Nullable String path) {
	if (path == null) {
		return false;
	}
	boolean uriVar = false;
	for (int i = 0; i < path.length(); i++) {
		char c = path.charAt(i);
		if (c == '*' || c == '?') {
			return true;
		}
		if (c == '{') {
			uriVar = true;
			continue;
		}
		if (c == '}' && uriVar) {
			return true;
		}
	}
	return false;
}

在 AntPathMatcher#doMatch 中定义了匹配的算法逻辑，而将真正的字符串匹配委托给了内部类AntPathStringMatcher。

下面来看下 AntPathStringMatcher 的创建

private boolean matchStrings(String pattern, String str,
		@Nullable Map uriTemplateVariables) {
 
	return getStringMatcher(pattern).matchStrings(str, uriTemplateVariables);
}
 
// 获取 pattern 对应的匹配器
protected AntPathStringMatcher getStringMatcher(String pattern) {
	AntPathStringMatcher matcher = null;
	Boolean cachePatterns = this.cachePatterns;
	if (cachePatterns == null || cachePatterns.booleanValue()) {
		matcher = this.stringMatcherCache.get(pattern);
	}
	if (matcher == null) {
		// AntPathMatcher 内部类
		matcher = new AntPathStringMatcher(pattern, this.caseSensitive);
		if (cachePatterns == null && this.stringMatcherCache.size() >= CACHE_TURNOFF_THRESHOLD) {
			// 超过阈值，关闭缓存，上限 65536
			deactivatePatternCache();
			return matcher;
		}
		if (cachePatterns == null || cachePatterns.booleanValue()) {
			// 加入缓存
			this.stringMatcherCache.put(pattern, matcher);
		}
	}
	return matcher;
}

可以看到，在字符串路径匹配时，先去获取字符串路径匹配器，此时将一个个 pattern 片段作为 key，去匹配器缓存获取一遍，获取不到，才进行创建。

在路径匹配时，传入的路径都是绝对路径，所以会存在很多相同的片段，此处应用缓存，也是为了提高匹配器的复用，减少对象的创建。

private static final Pattern GLOB_PATTERN = Pattern.compile("\\?|\\*|\\{((?:\\{[^/]+?\\}|[^/{}]|\\\\[{}])+?)\\}");
 
// *  0个或多个
// ?  1个
// {}  url路径 /user/{user}
public AntPathStringMatcher(String pattern, boolean caseSensitive) {
	this.rawPattern = pattern;
	this.caseSensitive = caseSensitive;
	StringBuilder patternBuilder = new StringBuilder();
	// 采用 glob pattern 语法
	Matcher matcher = GLOB_PATTERN.matcher(pattern);
	int end = 0;
	// 将 glob pattern 语法转化为 java 正则语法
	while (matcher.find()) {
		patternBuilder.append(quote(pattern, end, matcher.start()));
		String match = matcher.group();
		if ("?".equals(match)) {
			patternBuilder.append('.');
		}
		else if ("*".equals(match)) {
			patternBuilder.append(".*");
		}
		// {}
		else if (match.startsWith("{") && match.endsWith("}")) {
			int colonIdx = match.indexOf(':');
			if (colonIdx == -1) {
				patternBuilder.append(DEFAULT_VARIABLE_PATTERN);
				this.variableNames.add(matcher.group(1));
			}
			else {
				// ':' 之前的作为 variableName， 之后的部分作为 variablePattern
				String variablePattern = match.substring(colonIdx + 1, match.length() - 1);
				patternBuilder.append('(');
				patternBuilder.append(variablePattern);
				patternBuilder.append(')');
				String variableName = match.substring(1, colonIdx);
				this.variableNames.add(variableName);
			}
		}
		end = matcher.end();
	}
	// 没有 glob pattern 语法，完整字符串匹配
	if (end == 0) {
		this.exactMatch = true;
		this.pattern = null;
	}
	else {
		this.exactMatch = false;
		patternBuilder.append(quote(pattern, end, pattern.length()));
		this.pattern = Pattern.compile(patternBuilder.toString(),
				Pattern.DOTALL | (this.caseSensitive ? 0 : Pattern.CASE_INSENSITIVE));
	}
}

由于 glob pattern 匹配语法与 java 正则语法有区别，此处将 glob pattern 语法做了转化，转化为 java 的正则语法，再进行了编译，赋值给 AntPathStringMatcher.pattern 属性。

此处的 quote 方法是采用了 java Pattern#quote 中的处理，对不需要匹配的字符串引用起来，不看做正则表达式，比如：".class" 引用完之后，变成 "\Q.class\E"，这样字符串中的字符 '.' 就不会看作正则中的特殊字符。

循环时，采用 Matcher#find 方法，此方法会找出参数 pattern 中的下一个子序列与 GLOB_PATTERN，进行匹配，比如："*.class"，执行 Matcher#find 方法后，再执行 Matcher#group 会捕获到 "*"，此时经过转化变成 ".*"，最后拼接，重新编译去匹配的正则表达式就是：".*\Q.class\E"。

// org.springframework.util.AntPathMatcher$AntPathStringMatcher
public boolean matchStrings(String str, @Nullable Map uriTemplateVariables) {
	// 精确匹配
	if (this.exactMatch) {
		return this.caseSensitive ? this.rawPattern.equals(str) : this.rawPattern.equalsIgnoreCase(str);
	}
	// 正则匹配
	else if (this.pattern != null) {
		Matcher matcher = this.pattern.matcher(str);
		if (matcher.matches()) {
			if (uriTemplateVariables != null) {
				if (this.variableNames.size() != matcher.groupCount()) {
					throw ...
				}
				for (int i = 1; i <= matcher.groupCount(); i++) {
					String name = this.variableNames.get(i - 1);
					if (name.startsWith("*")) {
						throw ...
					}
					String value = matcher.group(i);
					uriTemplateVariables.put(name, value);
				}
			}
			return true;
		}
	}
	return false;
}

执行完准备工作，待到字符串具体匹配时，就很简单了，是精确匹配，默认大小写敏感，此时调用 equals 方法判断两个字符串是否相等，非精确匹配，此时已经将 glob pattern 转化为 java 的正则匹配，直接调用 Matcher#matches 方法即可。

下面来看下 AntPathMatcher#doMatch 的匹配逻辑：

// AntPathMatcher
@Override
public boolean match(String pattern, String path) {
	return doMatch(pattern, path, true, null);
}
// 匹配
protected boolean doMatch(String pattern, @Nullable String path, boolean fullMatch,
		@Nullable Map uriTemplateVariables) {
	
	// path 路径不存在或者和 pattern 的开头不一致，直接返回 false
	if (path == null || path.startsWith(this.pathSeparator) != pattern.startsWith(this.pathSeparator)) {
		return false;
	}
 
	// 分割 pattern
	String[] pattDirs = tokenizePattern(pattern);
	// caseSensitive true 默认大小写敏感
	// isPotentialMatch 匹配到 pattDirs 中通配符就返回了
	if (fullMatch && this.caseSensitive && !isPotentialMatch(path, pattDirs)) {
		return false;
	}
	
	// 分割 path
	String[] pathDirs = tokenizePath(path);
	int pattIdxStart = 0;
	int pattIdxEnd = pattDirs.length - 1;
	int pathIdxStart = 0;
	int pathIdxEnd = pathDirs.length - 1;
 
	// Match all elements up to the first **
	while (pattIdxStart <= pattIdxEnd && pathIdxStart <= pathIdxEnd) {
		String pattDir = pattDirs[pattIdxStart];
		// pattDir 是 "**" 时跳出循环
		if ("**".equals(pattDir)) {
			break;
		}
		// 字符串匹配，不匹配直接返回 false
		if (!matchStrings(pattDir, pathDirs[pathIdxStart], uriTemplateVariables)) {
			return false;
		}
		// 对于匹配过的，都执行自增
		pattIdxStart++;
		pathIdxStart++;
	}
 
	// path 已经耗尽
	if (pathIdxStart > pathIdxEnd) {
		// Path is exhausted, only match if rest of pattern is * or **'s
		// pattern 也耗尽，判断 pattern 和 path 结尾是否都以 pathSeparator 结尾
		if (pattIdxStart > pattIdxEnd) {
			return (pattern.endsWith(this.pathSeparator) == path.endsWith(this.pathSeparator));
		}
		// pattern 未耗尽，fullMatch 为 false 直接返回
		// fullMatch 传参为 true，此处并不会返回
		if (!fullMatch) {
			return true;
		}
		// path 耗尽，pattern 也走到了结尾，判断 pattern 末端是否为 "*"，并且此时 path 以 pathSeparator 结尾
		if (pattIdxStart == pattIdxEnd && pattDirs[pattIdxStart].equals("*") && path.endsWith(this.pathSeparator)) {
			return true;
		}
		// path 耗尽，pattern 还存在，只能是 "**"，不为 "**" 直接返回 false，不匹配
		for (int i = pattIdxStart; i <= pattIdxEnd; i++) {
			if (!pattDirs[i].equals("**")) {
				return false;
			}
		}
		return true;
	}
	// pattern 耗尽，直接返回 false，因为 path 耗尽的情况上面已经分析了，此处即 path 还存在
	else if (pattIdxStart > pattIdxEnd) {
		// String not exhausted, but pattern is. Failure.
		return false;
	}
	// fullMatch 为 false，最前面 pattern 遇到 "**" 跳出循环，path 和 pattern 都未耗尽，此时 pattern 为 "**"，返回true
	// 执行时传参 fullMatch 为 true，所以此处判断直接跳过
	else if (!fullMatch && "**".equals(pattDirs[pattIdxStart])) {
		// Path start definitely matches due to "**" part in pattern.
		return true;
	}
	
	// path 和 pattern 都未耗尽，pattern 遇到了 "**"，跳出了前面的 while 循环
	// up to last '**'
	while (pattIdxStart <= pattIdxEnd && pathIdxStart <= pathIdxEnd) {
		// 取最后一个 pattern
		String pattDir = pattDirs[pattIdxEnd];
		// 为 "**" 跳出循环
		if (pattDir.equals("**")) {
			break;
		}
		// 末尾字符串匹配，不匹配直接返回 false
		if (!matchStrings(pattDir, pathDirs[pathIdxEnd], uriTemplateVariables)) {
			return false;
		}
		// 对于匹配过的，都执行自减
		pattIdxEnd--;
		pathIdxEnd--;
	}
	// pattern 末尾和 path 一直能匹配上，但 path 的 idxEnd 已经小于 idxStart，说明 path 已耗尽
	//示例：pattern: "a/b/c/**/e/f/g"，只有 e 和 f 都变为 **，才匹配
	//      path:    "a/b/c/g"	
	if (pathIdxStart > pathIdxEnd) {
		// String is exhausted
		// 剩下的 pattern 只有全为 "**" 才能满足匹配，否则返回 false，不匹配
		for (int i = pattIdxStart; i <= pattIdxEnd; i++) {
			if (!pattDirs[i].equals("**")) {
				return false;
			}
		}
		return true;
	}
	// pattern 短，path 长，只能是走到了 pattern 的最后一个 "**" 退出了循环，所以不存在 pattern 耗尽
	// 举例：
	// pattern: a/b/c/**/e/f/g/**/h/j     pattIdxStart 3  pattIdxEnd 7
	// path:    a/b/c/e/f/g/h/j           pathIdxStart 3  pathIdxEnd 5
	// pattIdxStart != pattIdxEnd 才有中间部分需要匹配
	while (pattIdxStart != pattIdxEnd && pathIdxStart <= pathIdxEnd) {
		int patIdxTmp = -1;
		// pattIdxStart 为 "**"，所以 i 从 pattidxStart + 1 开始，找下一个 "**"
		// pattern: a/b/c/**/e/f/g/**/**/h/j    patIdxTmp 为 7
		for (int i = pattIdxStart + 1; i <= pattIdxEnd; i++) {
			if (pattDirs[i].equals("**")) {
				patIdxTmp = i;
				break;
			}
		}
		// "**/**" 这种情况，跳过一个，即 pattIdxStart 自增，接着执行下一次循环
		if (patIdxTmp == pattIdxStart + 1) {
			// '**/**' situation, so skip one
			pattIdxStart++;
			continue;
		}
		// Find the pattern between padIdxStart & padIdxTmp in str between
		// strIdxStart & strIdxEnd
		// 剩余 pattern 长度，即第一个和第二个，两个 "**" 之间 pattern 的个数
		int patLength = (patIdxTmp - pattIdxStart - 1);
		// 剩余 path 未匹配的个数
		int strLength = (pathIdxEnd - pathIdxStart + 1);
		int foundIdx = -1;
 
		// path 剩余长度 大于 pattern 长度，直接返回false
		// 只有 strLength >=  pattern 长度，才会进入循环
		// strLength - patLength 即最大循环多少次，因为 "**" 可以匹配 path 中的子路径，即 path 子路径比 pattern 多出的部分
		// 举例：
		// pattern: a/b/c/**/e/f/g/**/h/j         pattIdxStart 3   pattIdxEnd 7   patIdxTmp 7   patLength = 3
		// path:    a/b/c/m/n/e/f/g/h/j		      pathIdxStart 3   pathIdxEnd 7				    strLength = 5
 
		// pattern: a/b/c/**/e/f/g/**/**/h/j      pattIdxStart 3   pattIdxEnd 8   patIdxTmp 7   patLength = 3
		// path:    a/b/c/m/n/e/f/g/h/j		      pathIdxStart 3   pathIdxEnd 7				    strLength = 5
 
		// pattern: a/b/c/**/e/f/**/g/**/**/h/j   pattIdxStart 3   pattIdxEnd 9   patIdxTmp 6   patLength = 2   
		// path:	a/b/c/m/n/e/f/g/h/j           pathIdxStart 3   pathIdxEnd 7                 strLength = 5    foundIdx = 3 + 2 = 5
		// 匹配完更新 pattIdxStart 6   pathIdxStart = 5 + 2 = 7，接着再次进入循环，此时 patIdxTmp 8，计算出 patLength = 8-6-1=1，strLength = 7-7+1=1，即就剩一个未匹配了
		// 匹配完更新 foundIdx = 7+0=7，pattIdxStart = 8 pathIdxStart = 7 + 1 = 8，再次进入循环，发现 pathIdxStart > pathIdxEnd，path已耗尽，退出循环
		strLoop:
		for (int i = 0; i <= strLength - patLength; i++) {
			for (int j = 0; j < patLength; j++) {
				// pattIdxStart 此时为 "**"， +1 即从下一个开始
				String subPat = pattDirs[pattIdxStart + j + 1];
				String subStr = pathDirs[pathIdxStart + i + j];
				// 不匹配，进行下一次循环
				// 因为 patternIdxStart 为 "**"，可以匹配 path 中的子路径，所以即使字符串匹配返回 false，也不能认为不匹配，只需进行下一次循环即可
				if (!matchStrings(subPat, subStr, uriTemplateVariables)) {
					continue strLoop;
				}
			}
			// 执行到此处，表明字符串匹配都成功了，退出循环
			// foundIdx = pathIdxStart + 子路径多出部分长度，即从这里开始与 pattern 匹配上了
			foundIdx = pathIdxStart + i;
			break;
		}
		
		// 循环完都匹配不上，直接返回 false
		if (foundIdx == -1) {
			return false;
		}
 
		// 更新 pattIdxStart 和 pathIdxStart
		// pattern 更新到最后一个 "**"
		pattIdxStart = patIdxTmp;
		// pathIdxStart 相当于等于 原pathIdxStart + 子路径部分长度 + pattern 部分长度
		pathIdxStart = foundIdx + patLength;
	}
 
	// 首尾部分都匹配完了，此时如果还剩下 pattern，只能为 "**"，否则不匹配，返回 false
	// pattern: a/b/c/**/d/e/**/**/**/k/f/g
	// path:    a/b/c/m/n/d/e/k/f/g
	// 执行到此处还有一种可能，就是 pattIdxStart == pattIdxEnd，并且为 "**"，此时返回 true
	// pattern: a/b/c/**
	// path:    a/b/c/e/f/g    此时也匹配
	for (int i = pattIdxStart; i <= pattIdxEnd; i++) {
		if (!pattDirs[i].equals("**")) {
			return false;
		}
	}
 
	return true;
}

代码比较长，归纳总结其实现逻辑如下：

1. pattern 和 path 从前匹配，匹配上了，更新 pattIdxStart 和 pathIdxStart，直到 pattern 遇见 **，退出循环
2. 此时判断 pattern 和 path 是否耗尽，做出相应处理
3. 都未耗尽，pattern 是遇到了第一个 ** 跳出了循环，此时从后向前匹配，匹配上了，更新 pattIdxEnd 和 pathIdxEnd，直到遇见 **，退出循环，此时还存在一种退出循环的可能，就是 path 耗尽了，pathIdxStart > pathIdxEnd。为什么不存在 pattern 耗尽的情况呢？pattern 耗尽，即 pattern 较短，path 较长，此时从上面已经得到了一个 **，只能是 pattern 遇见了 ** 退出循环，否则肯定是匹配不上的。举个例子，pattern:a/b/c/**/e/f，path:a/b/c/m/n/e/f
4. 此时，pattIdxStart != pattIdxEnd，表示在首尾两个 ** 之间存在中间部分，继续循环，此时从 pattIdxStart + 1 开始，查找下一个 **，记录其索引 patIdxTmp，因为在首尾两个 ** 之间还可能存在 **，对于 **/** 这种情况，使 pattIdxStart 自增，进行下一次循环，直到pattIdxStart 和 patIdxTmp 之间存在其它部分，此时计算出 pattIdxStart 和 patIdxTmp 之间剩余多少需要匹配，由于 pattIdxStart 和 patIdxTmp 都对应 **，所以 patIdxTmp - pattIdxStart 之后还需要再减 1，即剔除 pattIdxStart。而对于 path，剩余未匹配的部分则为 pathIdxEnd - pathIdxStart，再加 1，包含 pathIdxStart。strLength - patLength，即最大可以存在几个子路径片段，因为 pattIdxStart 对应的 ** 可以匹配子路径，匹配完，计算一个 foundIdx，即 pathIdxStart + i，此处 i 表示从 pathIdxStart 开始，第几个索引对应的 path 片段开始与 pattern 片段匹配，i 从 0 开始。从这里开始与 pattern 片段匹配，之后更新 pattIdxStart = patIdxTmp，pathIdxStart = foundIdx + patLength，接着进行下一次循环
5. 首尾，中间部分都匹配完了，一旦执行到了此处，存在的 pattern 剩余部分只能是 **

至此，就完成了路径匹配的核心逻辑。

下面的一些代码，在 AntPathMatcher#doMatch 中虽然也调用到了，权当了解。

protected String[] tokenizePattern(String pattern) {
	String[] tokenized = null;
	Boolean cachePatterns = this.cachePatterns;
	if (cachePatterns == null || cachePatterns.booleanValue()) {
		// tokenizedPatternCache 缓存获取
		tokenized = this.tokenizedPatternCache.get(pattern);
	}
	if (tokenized == null) {
		tokenized = tokenizePath(pattern);
		if (cachePatterns == null && this.tokenizedPatternCache.size() >= CACHE_TURNOFF_THRESHOLD) {
			// 超过阈值，关闭缓存
			deactivatePatternCache();
			return tokenized;
		}
		if (cachePatterns == null || cachePatterns.booleanValue()) {
			this.tokenizedPatternCache.put(pattern, tokenized);
		}
	}
	return tokenized;
}
 
protected String[] tokenizePath(String path) {
	// 使用 java.util.StringTokenizer
	return StringUtils.tokenizeToStringArray(path, this.pathSeparator, this.trimTokens, true);
}
 
// StringUtils
public static String[] tokenizeToStringArray(
		@Nullable String str, String delimiters, boolean trimTokens, boolean ignoreEmptyTokens) {
 
	if (str == null) {
		return EMPTY_STRING_ARRAY;
	}
 
	StringTokenizer st = new StringTokenizer(str, delimiters);
	List tokens = new ArrayList<>();
	while (st.hasMoreTokens()) {
		String token = st.nextToken();
		if (trimTokens) {
			token = token.trim();
		}
		// 是否忽略空 token
		if (!ignoreEmptyTokens || token.length() > 0) {
			tokens.add(token);
		}
	}
	return toStringArray(tokens);
}
 
// 可以认为基本上都是潜在的匹配
private boolean isPotentialMatch(String path, String[] pattDirs) {
	if (!this.trimTokens) {
		// path 中当前字符索引，从 0 开始
		int pos = 0;
		for (String pattDir : pattDirs) {
			// 跳过路径分隔符
			int skipped = skipSeparator(path, pos, this.pathSeparator);
			pos += skipped;
			skipped = skipSegment(path, pos, pattDir);
			// skipped < pattDir.length() 表明 pattDir 中存在通配符，否则 skipped 长度应与 pattDir.length() 长度相等
			if (skipped < pattDir.length()) {
				return (skipped > 0 || (pattDir.length() > 0 && isWildcardChar(pattDir.charAt(0))));
			}
			pos += skipped;
		}
	}
	return true;
}
 
// 跳过分隔符
private int skipSeparator(String path, int pos, String separator) {
	int skipped = 0;
	// 以分隔符开头，跳过分隔符
	while (path.startsWith(separator, pos + skipped)) {
		skipped += separator.length();
	}
	return skipped;
}
 
// abc*
// 跳过片段
private int skipSegment(String path, int pos, String prefix) {
	int skipped = 0;
	for (int i = 0; i < prefix.length(); i++) {
		char c = prefix.charAt(i);
		// 通配符字符，三个 '*'、'?'、'{'
		if (isWildcardChar(c)) {
			return skipped;
		}
		// path 中当前字符索引
		int currPos = pos + skipped;
		if (currPos >= path.length()) {
			return 0;
		}
		// 逐个字符比较，字符一致，skipped 自增
		if (c == path.charAt(currPos)) {
			skipped++;
		}
	}
	return skipped;
}

自 spring 5.0 开始，在 spring web 应用中还提供了另一个路径匹配处理类，PathPattern，语法与AntPathMatcher 类似。该解决方案专为 web 使用而设计，可以有效地处理编码和路径参数，并有效地匹配。

PathPattern是web应用的推荐解决方案，也是Spring WebFlux的唯一选择。它从5.3版开始在Spring MVC中启用，从6.0版开始默认启用。而 AntPathMatcher 主要用于选择类路径、文件系统和其他位置上的资源。