在 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<String, String> 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<String, String> 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<String, String> 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;
}
代码比较长,归纳总结其实现逻辑如下:
- pattern 和 path 从前匹配,匹配上了,更新 pattIdxStart 和 pathIdxStart,直到 pattern 遇见 **,退出循环
- 此时判断 pattern 和 path 是否耗尽,做出相应处理
- 都未耗尽,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
- 此时,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,接着进行下一次循环
- 首尾,中间部分都匹配完了,一旦执行到了此处,存在的 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<String> 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 主要用于选择类路径、文件系统和其他位置上的资源。