001/* 002 * Copyright 2002-2020 the original author or authors. 003 * 004 * Licensed under the Apache License, Version 2.0 (the "License"); 005 * you may not use this file except in compliance with the License. 006 * You may obtain a copy of the License at 007 * 008 * https://www.apache.org/licenses/LICENSE-2.0 009 * 010 * Unless required by applicable law or agreed to in writing, software 011 * distributed under the License is distributed on an "AS IS" BASIS, 012 * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. 013 * See the License for the specific language governing permissions and 014 * limitations under the License. 015 */ 016 017package org.springframework.util; 018 019import java.util.Comparator; 020import java.util.LinkedHashMap; 021import java.util.LinkedList; 022import java.util.List; 023import java.util.Map; 024import java.util.concurrent.ConcurrentHashMap; 025import java.util.regex.Matcher; 026import java.util.regex.Pattern; 027 028import org.springframework.lang.Nullable; 029 030/** 031 * {@link PathMatcher} implementation for Ant-style path patterns. 032 * 033 * <p>Part of this mapping code has been kindly borrowed from <a href="https://ant.apache.org">Apache Ant</a>. 034 * 035 * <p>The mapping matches URLs using the following rules:<br> 036 * <ul> 037 * <li>{@code ?} matches one character</li> 038 * <li>{@code *} matches zero or more characters</li> 039 * <li>{@code **} matches zero or more <em>directories</em> in a path</li> 040 * <li>{@code {spring:[a-z]+}} matches the regexp {@code [a-z]+} as a path variable named "spring"</li> 041 * </ul> 042 * 043 * <h3>Examples</h3> 044 * <ul> 045 * <li>{@code com/t?st.jsp} — matches {@code com/test.jsp} but also 046 * {@code com/tast.jsp} or {@code com/txst.jsp}</li> 047 * <li>{@code com/*.jsp} — matches all {@code .jsp} files in the 048 * {@code com} directory</li> 049 * <li><code>com/**/test.jsp</code> — matches all {@code test.jsp} 050 * files underneath the {@code com} path</li> 051 * <li><code>org/springframework/**/*.jsp</code> — matches all 052 * {@code .jsp} files underneath the {@code org/springframework} path</li> 053 * <li><code>org/**/servlet/bla.jsp</code> — matches 054 * {@code org/springframework/servlet/bla.jsp} but also 055 * {@code org/springframework/testing/servlet/bla.jsp} and {@code org/servlet/bla.jsp}</li> 056 * <li>{@code com/{filename:\\w+}.jsp} will match {@code com/test.jsp} and assign the value {@code test} 057 * to the {@code filename} variable</li> 058 * </ul> 059 * 060 * <p><strong>Note:</strong> a pattern and a path must both be absolute or must 061 * both be relative in order for the two to match. Therefore it is recommended 062 * that users of this implementation to sanitize patterns in order to prefix 063 * them with "/" as it makes sense in the context in which they're used. 064 * 065 * @author Alef Arendsen 066 * @author Juergen Hoeller 067 * @author Rob Harrop 068 * @author Arjen Poutsma 069 * @author Rossen Stoyanchev 070 * @author Sam Brannen 071 * @since 16.07.2003 072 */ 073public class AntPathMatcher implements PathMatcher { 074 075 /** Default path separator: "/". */ 076 public static final String DEFAULT_PATH_SEPARATOR = "/"; 077 078 private static final int CACHE_TURNOFF_THRESHOLD = 65536; 079 080 private static final Pattern VARIABLE_PATTERN = Pattern.compile("\\{[^/]+?}"); 081 082 private static final char[] WILDCARD_CHARS = { '*', '?', '{' }; 083 084 085 private String pathSeparator; 086 087 private PathSeparatorPatternCache pathSeparatorPatternCache; 088 089 private boolean caseSensitive = true; 090 091 private boolean trimTokens = false; 092 093 @Nullable 094 private volatile Boolean cachePatterns; 095 096 private final Map<String, String[]> tokenizedPatternCache = new ConcurrentHashMap<>(256); 097 098 final Map<String, AntPathStringMatcher> stringMatcherCache = new ConcurrentHashMap<>(256); 099 100 101 /** 102 * Create a new instance with the {@link #DEFAULT_PATH_SEPARATOR}. 103 */ 104 public AntPathMatcher() { 105 this.pathSeparator = DEFAULT_PATH_SEPARATOR; 106 this.pathSeparatorPatternCache = new PathSeparatorPatternCache(DEFAULT_PATH_SEPARATOR); 107 } 108 109 /** 110 * A convenient, alternative constructor to use with a custom path separator. 111 * @param pathSeparator the path separator to use, must not be {@code null}. 112 * @since 4.1 113 */ 114 public AntPathMatcher(String pathSeparator) { 115 Assert.notNull(pathSeparator, "'pathSeparator' is required"); 116 this.pathSeparator = pathSeparator; 117 this.pathSeparatorPatternCache = new PathSeparatorPatternCache(pathSeparator); 118 } 119 120 121 /** 122 * Set the path separator to use for pattern parsing. 123 * <p>Default is "/", as in Ant. 124 */ 125 public void setPathSeparator(@Nullable String pathSeparator) { 126 this.pathSeparator = (pathSeparator != null ? pathSeparator : DEFAULT_PATH_SEPARATOR); 127 this.pathSeparatorPatternCache = new PathSeparatorPatternCache(this.pathSeparator); 128 } 129 130 /** 131 * Specify whether to perform pattern matching in a case-sensitive fashion. 132 * <p>Default is {@code true}. Switch this to {@code false} for case-insensitive matching. 133 * @since 4.2 134 */ 135 public void setCaseSensitive(boolean caseSensitive) { 136 this.caseSensitive = caseSensitive; 137 } 138 139 /** 140 * Specify whether to trim tokenized paths and patterns. 141 * <p>Default is {@code false}. 142 */ 143 public void setTrimTokens(boolean trimTokens) { 144 this.trimTokens = trimTokens; 145 } 146 147 /** 148 * Specify whether to cache parsed pattern metadata for patterns passed 149 * into this matcher's {@link #match} method. A value of {@code true} 150 * activates an unlimited pattern cache; a value of {@code false} turns 151 * the pattern cache off completely. 152 * <p>Default is for the cache to be on, but with the variant to automatically 153 * turn it off when encountering too many patterns to cache at runtime 154 * (the threshold is 65536), assuming that arbitrary permutations of patterns 155 * are coming in, with little chance for encountering a recurring pattern. 156 * @since 4.0.1 157 * @see #getStringMatcher(String) 158 */ 159 public void setCachePatterns(boolean cachePatterns) { 160 this.cachePatterns = cachePatterns; 161 } 162 163 private void deactivatePatternCache() { 164 this.cachePatterns = false; 165 this.tokenizedPatternCache.clear(); 166 this.stringMatcherCache.clear(); 167 } 168 169 170 @Override 171 public boolean isPattern(@Nullable String path) { 172 if (path == null) { 173 return false; 174 } 175 boolean uriVar = false; 176 for (int i = 0; i < path.length(); i++) { 177 char c = path.charAt(i); 178 if (c == '*' || c == '?') { 179 return true; 180 } 181 if (c == '{') { 182 uriVar = true; 183 continue; 184 } 185 if (c == '}' && uriVar) { 186 return true; 187 } 188 } 189 return false; 190 } 191 192 @Override 193 public boolean match(String pattern, String path) { 194 return doMatch(pattern, path, true, null); 195 } 196 197 @Override 198 public boolean matchStart(String pattern, String path) { 199 return doMatch(pattern, path, false, null); 200 } 201 202 /** 203 * Actually match the given {@code path} against the given {@code pattern}. 204 * @param pattern the pattern to match against 205 * @param path the path to test 206 * @param fullMatch whether a full pattern match is required (else a pattern match 207 * as far as the given base path goes is sufficient) 208 * @return {@code true} if the supplied {@code path} matched, {@code false} if it didn't 209 */ 210 protected boolean doMatch(String pattern, @Nullable String path, boolean fullMatch, 211 @Nullable Map<String, String> uriTemplateVariables) { 212 213 if (path == null || path.startsWith(this.pathSeparator) != pattern.startsWith(this.pathSeparator)) { 214 return false; 215 } 216 217 String[] pattDirs = tokenizePattern(pattern); 218 if (fullMatch && this.caseSensitive && !isPotentialMatch(path, pattDirs)) { 219 return false; 220 } 221 222 String[] pathDirs = tokenizePath(path); 223 int pattIdxStart = 0; 224 int pattIdxEnd = pattDirs.length - 1; 225 int pathIdxStart = 0; 226 int pathIdxEnd = pathDirs.length - 1; 227 228 // Match all elements up to the first ** 229 while (pattIdxStart <= pattIdxEnd && pathIdxStart <= pathIdxEnd) { 230 String pattDir = pattDirs[pattIdxStart]; 231 if ("**".equals(pattDir)) { 232 break; 233 } 234 if (!matchStrings(pattDir, pathDirs[pathIdxStart], uriTemplateVariables)) { 235 return false; 236 } 237 pattIdxStart++; 238 pathIdxStart++; 239 } 240 241 if (pathIdxStart > pathIdxEnd) { 242 // Path is exhausted, only match if rest of pattern is * or **'s 243 if (pattIdxStart > pattIdxEnd) { 244 return (pattern.endsWith(this.pathSeparator) == path.endsWith(this.pathSeparator)); 245 } 246 if (!fullMatch) { 247 return true; 248 } 249 if (pattIdxStart == pattIdxEnd && pattDirs[pattIdxStart].equals("*") && path.endsWith(this.pathSeparator)) { 250 return true; 251 } 252 for (int i = pattIdxStart; i <= pattIdxEnd; i++) { 253 if (!pattDirs[i].equals("**")) { 254 return false; 255 } 256 } 257 return true; 258 } 259 else if (pattIdxStart > pattIdxEnd) { 260 // String not exhausted, but pattern is. Failure. 261 return false; 262 } 263 else if (!fullMatch && "**".equals(pattDirs[pattIdxStart])) { 264 // Path start definitely matches due to "**" part in pattern. 265 return true; 266 } 267 268 // up to last '**' 269 while (pattIdxStart <= pattIdxEnd && pathIdxStart <= pathIdxEnd) { 270 String pattDir = pattDirs[pattIdxEnd]; 271 if (pattDir.equals("**")) { 272 break; 273 } 274 if (!matchStrings(pattDir, pathDirs[pathIdxEnd], uriTemplateVariables)) { 275 return false; 276 } 277 pattIdxEnd--; 278 pathIdxEnd--; 279 } 280 if (pathIdxStart > pathIdxEnd) { 281 // String is exhausted 282 for (int i = pattIdxStart; i <= pattIdxEnd; i++) { 283 if (!pattDirs[i].equals("**")) { 284 return false; 285 } 286 } 287 return true; 288 } 289 290 while (pattIdxStart != pattIdxEnd && pathIdxStart <= pathIdxEnd) { 291 int patIdxTmp = -1; 292 for (int i = pattIdxStart + 1; i <= pattIdxEnd; i++) { 293 if (pattDirs[i].equals("**")) { 294 patIdxTmp = i; 295 break; 296 } 297 } 298 if (patIdxTmp == pattIdxStart + 1) { 299 // '**/**' situation, so skip one 300 pattIdxStart++; 301 continue; 302 } 303 // Find the pattern between padIdxStart & padIdxTmp in str between 304 // strIdxStart & strIdxEnd 305 int patLength = (patIdxTmp - pattIdxStart - 1); 306 int strLength = (pathIdxEnd - pathIdxStart + 1); 307 int foundIdx = -1; 308 309 strLoop: 310 for (int i = 0; i <= strLength - patLength; i++) { 311 for (int j = 0; j < patLength; j++) { 312 String subPat = pattDirs[pattIdxStart + j + 1]; 313 String subStr = pathDirs[pathIdxStart + i + j]; 314 if (!matchStrings(subPat, subStr, uriTemplateVariables)) { 315 continue strLoop; 316 } 317 } 318 foundIdx = pathIdxStart + i; 319 break; 320 } 321 322 if (foundIdx == -1) { 323 return false; 324 } 325 326 pattIdxStart = patIdxTmp; 327 pathIdxStart = foundIdx + patLength; 328 } 329 330 for (int i = pattIdxStart; i <= pattIdxEnd; i++) { 331 if (!pattDirs[i].equals("**")) { 332 return false; 333 } 334 } 335 336 return true; 337 } 338 339 private boolean isPotentialMatch(String path, String[] pattDirs) { 340 if (!this.trimTokens) { 341 int pos = 0; 342 for (String pattDir : pattDirs) { 343 int skipped = skipSeparator(path, pos, this.pathSeparator); 344 pos += skipped; 345 skipped = skipSegment(path, pos, pattDir); 346 if (skipped < pattDir.length()) { 347 return (skipped > 0 || (pattDir.length() > 0 && isWildcardChar(pattDir.charAt(0)))); 348 } 349 pos += skipped; 350 } 351 } 352 return true; 353 } 354 355 private int skipSegment(String path, int pos, String prefix) { 356 int skipped = 0; 357 for (int i = 0; i < prefix.length(); i++) { 358 char c = prefix.charAt(i); 359 if (isWildcardChar(c)) { 360 return skipped; 361 } 362 int currPos = pos + skipped; 363 if (currPos >= path.length()) { 364 return 0; 365 } 366 if (c == path.charAt(currPos)) { 367 skipped++; 368 } 369 } 370 return skipped; 371 } 372 373 private int skipSeparator(String path, int pos, String separator) { 374 int skipped = 0; 375 while (path.startsWith(separator, pos + skipped)) { 376 skipped += separator.length(); 377 } 378 return skipped; 379 } 380 381 private boolean isWildcardChar(char c) { 382 for (char candidate : WILDCARD_CHARS) { 383 if (c == candidate) { 384 return true; 385 } 386 } 387 return false; 388 } 389 390 /** 391 * Tokenize the given path pattern into parts, based on this matcher's settings. 392 * <p>Performs caching based on {@link #setCachePatterns}, delegating to 393 * {@link #tokenizePath(String)} for the actual tokenization algorithm. 394 * @param pattern the pattern to tokenize 395 * @return the tokenized pattern parts 396 */ 397 protected String[] tokenizePattern(String pattern) { 398 String[] tokenized = null; 399 Boolean cachePatterns = this.cachePatterns; 400 if (cachePatterns == null || cachePatterns.booleanValue()) { 401 tokenized = this.tokenizedPatternCache.get(pattern); 402 } 403 if (tokenized == null) { 404 tokenized = tokenizePath(pattern); 405 if (cachePatterns == null && this.tokenizedPatternCache.size() >= CACHE_TURNOFF_THRESHOLD) { 406 // Try to adapt to the runtime situation that we're encountering: 407 // There are obviously too many different patterns coming in here... 408 // So let's turn off the cache since the patterns are unlikely to be reoccurring. 409 deactivatePatternCache(); 410 return tokenized; 411 } 412 if (cachePatterns == null || cachePatterns.booleanValue()) { 413 this.tokenizedPatternCache.put(pattern, tokenized); 414 } 415 } 416 return tokenized; 417 } 418 419 /** 420 * Tokenize the given path into parts, based on this matcher's settings. 421 * @param path the path to tokenize 422 * @return the tokenized path parts 423 */ 424 protected String[] tokenizePath(String path) { 425 return StringUtils.tokenizeToStringArray(path, this.pathSeparator, this.trimTokens, true); 426 } 427 428 /** 429 * Test whether or not a string matches against a pattern. 430 * @param pattern the pattern to match against (never {@code null}) 431 * @param str the String which must be matched against the pattern (never {@code null}) 432 * @return {@code true} if the string matches against the pattern, or {@code false} otherwise 433 */ 434 private boolean matchStrings(String pattern, String str, 435 @Nullable Map<String, String> uriTemplateVariables) { 436 437 return getStringMatcher(pattern).matchStrings(str, uriTemplateVariables); 438 } 439 440 /** 441 * Build or retrieve an {@link AntPathStringMatcher} for the given pattern. 442 * <p>The default implementation checks this AntPathMatcher's internal cache 443 * (see {@link #setCachePatterns}), creating a new AntPathStringMatcher instance 444 * if no cached copy is found. 445 * <p>When encountering too many patterns to cache at runtime (the threshold is 65536), 446 * it turns the default cache off, assuming that arbitrary permutations of patterns 447 * are coming in, with little chance for encountering a recurring pattern. 448 * <p>This method may be overridden to implement a custom cache strategy. 449 * @param pattern the pattern to match against (never {@code null}) 450 * @return a corresponding AntPathStringMatcher (never {@code null}) 451 * @see #setCachePatterns 452 */ 453 protected AntPathStringMatcher getStringMatcher(String pattern) { 454 AntPathStringMatcher matcher = null; 455 Boolean cachePatterns = this.cachePatterns; 456 if (cachePatterns == null || cachePatterns.booleanValue()) { 457 matcher = this.stringMatcherCache.get(pattern); 458 } 459 if (matcher == null) { 460 matcher = new AntPathStringMatcher(pattern, this.caseSensitive); 461 if (cachePatterns == null && this.stringMatcherCache.size() >= CACHE_TURNOFF_THRESHOLD) { 462 // Try to adapt to the runtime situation that we're encountering: 463 // There are obviously too many different patterns coming in here... 464 // So let's turn off the cache since the patterns are unlikely to be reoccurring. 465 deactivatePatternCache(); 466 return matcher; 467 } 468 if (cachePatterns == null || cachePatterns.booleanValue()) { 469 this.stringMatcherCache.put(pattern, matcher); 470 } 471 } 472 return matcher; 473 } 474 475 /** 476 * Given a pattern and a full path, determine the pattern-mapped part. <p>For example: <ul> 477 * <li>'{@code /docs/cvs/commit.html}' and '{@code /docs/cvs/commit.html} -> ''</li> 478 * <li>'{@code /docs/*}' and '{@code /docs/cvs/commit} -> '{@code cvs/commit}'</li> 479 * <li>'{@code /docs/cvs/*.html}' and '{@code /docs/cvs/commit.html} -> '{@code commit.html}'</li> 480 * <li>'{@code /docs/**}' and '{@code /docs/cvs/commit} -> '{@code cvs/commit}'</li> 481 * <li>'{@code /docs/**\/*.html}' and '{@code /docs/cvs/commit.html} -> '{@code cvs/commit.html}'</li> 482 * <li>'{@code /*.html}' and '{@code /docs/cvs/commit.html} -> '{@code docs/cvs/commit.html}'</li> 483 * <li>'{@code *.html}' and '{@code /docs/cvs/commit.html} -> '{@code /docs/cvs/commit.html}'</li> 484 * <li>'{@code *}' and '{@code /docs/cvs/commit.html} -> '{@code /docs/cvs/commit.html}'</li> </ul> 485 * <p>Assumes that {@link #match} returns {@code true} for '{@code pattern}' and '{@code path}', but 486 * does <strong>not</strong> enforce this. 487 */ 488 @Override 489 public String extractPathWithinPattern(String pattern, String path) { 490 String[] patternParts = StringUtils.tokenizeToStringArray(pattern, this.pathSeparator, this.trimTokens, true); 491 String[] pathParts = StringUtils.tokenizeToStringArray(path, this.pathSeparator, this.trimTokens, true); 492 StringBuilder builder = new StringBuilder(); 493 boolean pathStarted = false; 494 495 for (int segment = 0; segment < patternParts.length; segment++) { 496 String patternPart = patternParts[segment]; 497 if (patternPart.indexOf('*') > -1 || patternPart.indexOf('?') > -1) { 498 for (; segment < pathParts.length; segment++) { 499 if (pathStarted || (segment == 0 && !pattern.startsWith(this.pathSeparator))) { 500 builder.append(this.pathSeparator); 501 } 502 builder.append(pathParts[segment]); 503 pathStarted = true; 504 } 505 } 506 } 507 508 return builder.toString(); 509 } 510 511 @Override 512 public Map<String, String> extractUriTemplateVariables(String pattern, String path) { 513 Map<String, String> variables = new LinkedHashMap<>(); 514 boolean result = doMatch(pattern, path, true, variables); 515 if (!result) { 516 throw new IllegalStateException("Pattern \"" + pattern + "\" is not a match for \"" + path + "\""); 517 } 518 return variables; 519 } 520 521 /** 522 * Combine two patterns into a new pattern. 523 * <p>This implementation simply concatenates the two patterns, unless 524 * the first pattern contains a file extension match (e.g., {@code *.html}). 525 * In that case, the second pattern will be merged into the first. Otherwise, 526 * an {@code IllegalArgumentException} will be thrown. 527 * <h3>Examples</h3> 528 * <table border="1"> 529 * <tr><th>Pattern 1</th><th>Pattern 2</th><th>Result</th></tr> 530 * <tr><td>{@code null}</td><td>{@code null}</td><td> </td></tr> 531 * <tr><td>/hotels</td><td>{@code null}</td><td>/hotels</td></tr> 532 * <tr><td>{@code null}</td><td>/hotels</td><td>/hotels</td></tr> 533 * <tr><td>/hotels</td><td>/bookings</td><td>/hotels/bookings</td></tr> 534 * <tr><td>/hotels</td><td>bookings</td><td>/hotels/bookings</td></tr> 535 * <tr><td>/hotels/*</td><td>/bookings</td><td>/hotels/bookings</td></tr> 536 * <tr><td>/hotels/**</td><td>/bookings</td><td>/hotels/**/bookings</td></tr> 537 * <tr><td>/hotels</td><td>{hotel}</td><td>/hotels/{hotel}</td></tr> 538 * <tr><td>/hotels/*</td><td>{hotel}</td><td>/hotels/{hotel}</td></tr> 539 * <tr><td>/hotels/**</td><td>{hotel}</td><td>/hotels/**/{hotel}</td></tr> 540 * <tr><td>/*.html</td><td>/hotels.html</td><td>/hotels.html</td></tr> 541 * <tr><td>/*.html</td><td>/hotels</td><td>/hotels.html</td></tr> 542 * <tr><td>/*.html</td><td>/*.txt</td><td>{@code IllegalArgumentException}</td></tr> 543 * </table> 544 * @param pattern1 the first pattern 545 * @param pattern2 the second pattern 546 * @return the combination of the two patterns 547 * @throws IllegalArgumentException if the two patterns cannot be combined 548 */ 549 @Override 550 public String combine(String pattern1, String pattern2) { 551 if (!StringUtils.hasText(pattern1) && !StringUtils.hasText(pattern2)) { 552 return ""; 553 } 554 if (!StringUtils.hasText(pattern1)) { 555 return pattern2; 556 } 557 if (!StringUtils.hasText(pattern2)) { 558 return pattern1; 559 } 560 561 boolean pattern1ContainsUriVar = (pattern1.indexOf('{') != -1); 562 if (!pattern1.equals(pattern2) && !pattern1ContainsUriVar && match(pattern1, pattern2)) { 563 // /* + /hotel -> /hotel ; "/*.*" + "/*.html" -> /*.html 564 // However /user + /user -> /usr/user ; /{foo} + /bar -> /{foo}/bar 565 return pattern2; 566 } 567 568 // /hotels/* + /booking -> /hotels/booking 569 // /hotels/* + booking -> /hotels/booking 570 if (pattern1.endsWith(this.pathSeparatorPatternCache.getEndsOnWildCard())) { 571 return concat(pattern1.substring(0, pattern1.length() - 2), pattern2); 572 } 573 574 // /hotels/** + /booking -> /hotels/**/booking 575 // /hotels/** + booking -> /hotels/**/booking 576 if (pattern1.endsWith(this.pathSeparatorPatternCache.getEndsOnDoubleWildCard())) { 577 return concat(pattern1, pattern2); 578 } 579 580 int starDotPos1 = pattern1.indexOf("*."); 581 if (pattern1ContainsUriVar || starDotPos1 == -1 || this.pathSeparator.equals(".")) { 582 // simply concatenate the two patterns 583 return concat(pattern1, pattern2); 584 } 585 586 String ext1 = pattern1.substring(starDotPos1 + 1); 587 int dotPos2 = pattern2.indexOf('.'); 588 String file2 = (dotPos2 == -1 ? pattern2 : pattern2.substring(0, dotPos2)); 589 String ext2 = (dotPos2 == -1 ? "" : pattern2.substring(dotPos2)); 590 boolean ext1All = (ext1.equals(".*") || ext1.isEmpty()); 591 boolean ext2All = (ext2.equals(".*") || ext2.isEmpty()); 592 if (!ext1All && !ext2All) { 593 throw new IllegalArgumentException("Cannot combine patterns: " + pattern1 + " vs " + pattern2); 594 } 595 String ext = (ext1All ? ext2 : ext1); 596 return file2 + ext; 597 } 598 599 private String concat(String path1, String path2) { 600 boolean path1EndsWithSeparator = path1.endsWith(this.pathSeparator); 601 boolean path2StartsWithSeparator = path2.startsWith(this.pathSeparator); 602 603 if (path1EndsWithSeparator && path2StartsWithSeparator) { 604 return path1 + path2.substring(1); 605 } 606 else if (path1EndsWithSeparator || path2StartsWithSeparator) { 607 return path1 + path2; 608 } 609 else { 610 return path1 + this.pathSeparator + path2; 611 } 612 } 613 614 /** 615 * Given a full path, returns a {@link Comparator} suitable for sorting patterns in order of 616 * explicitness. 617 * <p>This {@code Comparator} will {@linkplain java.util.List#sort(Comparator) sort} 618 * a list so that more specific patterns (without URI templates or wild cards) come before 619 * generic patterns. So given a list with the following patterns, the returned comparator 620 * will sort this list so that the order will be as indicated. 621 * <ol> 622 * <li>{@code /hotels/new}</li> 623 * <li>{@code /hotels/{hotel}}</li> 624 * <li>{@code /hotels/*}</li> 625 * </ol> 626 * <p>The full path given as parameter is used to test for exact matches. So when the given path 627 * is {@code /hotels/2}, the pattern {@code /hotels/2} will be sorted before {@code /hotels/1}. 628 * @param path the full path to use for comparison 629 * @return a comparator capable of sorting patterns in order of explicitness 630 */ 631 @Override 632 public Comparator<String> getPatternComparator(String path) { 633 return new AntPatternComparator(path); 634 } 635 636 637 /** 638 * Tests whether or not a string matches against a pattern via a {@link Pattern}. 639 * <p>The pattern may contain special characters: '*' means zero or more characters; '?' means one and 640 * only one character; '{' and '}' indicate a URI template pattern. For example <tt>/users/{user}</tt>. 641 */ 642 protected static class AntPathStringMatcher { 643 644 private static final Pattern GLOB_PATTERN = Pattern.compile("\\?|\\*|\\{((?:\\{[^/]+?}|[^/{}]|\\\\[{}])+?)}"); 645 646 private static final String DEFAULT_VARIABLE_PATTERN = "(.*)"; 647 648 private final Pattern pattern; 649 650 private final List<String> variableNames = new LinkedList<>(); 651 652 public AntPathStringMatcher(String pattern) { 653 this(pattern, true); 654 } 655 656 public AntPathStringMatcher(String pattern, boolean caseSensitive) { 657 StringBuilder patternBuilder = new StringBuilder(); 658 Matcher matcher = GLOB_PATTERN.matcher(pattern); 659 int end = 0; 660 while (matcher.find()) { 661 patternBuilder.append(quote(pattern, end, matcher.start())); 662 String match = matcher.group(); 663 if ("?".equals(match)) { 664 patternBuilder.append('.'); 665 } 666 else if ("*".equals(match)) { 667 patternBuilder.append(".*"); 668 } 669 else if (match.startsWith("{") && match.endsWith("}")) { 670 int colonIdx = match.indexOf(':'); 671 if (colonIdx == -1) { 672 patternBuilder.append(DEFAULT_VARIABLE_PATTERN); 673 this.variableNames.add(matcher.group(1)); 674 } 675 else { 676 String variablePattern = match.substring(colonIdx + 1, match.length() - 1); 677 patternBuilder.append('('); 678 patternBuilder.append(variablePattern); 679 patternBuilder.append(')'); 680 String variableName = match.substring(1, colonIdx); 681 this.variableNames.add(variableName); 682 } 683 } 684 end = matcher.end(); 685 } 686 patternBuilder.append(quote(pattern, end, pattern.length())); 687 this.pattern = (caseSensitive ? Pattern.compile(patternBuilder.toString()) : 688 Pattern.compile(patternBuilder.toString(), Pattern.CASE_INSENSITIVE)); 689 } 690 691 private String quote(String s, int start, int end) { 692 if (start == end) { 693 return ""; 694 } 695 return Pattern.quote(s.substring(start, end)); 696 } 697 698 /** 699 * Main entry point. 700 * @return {@code true} if the string matches against the pattern, or {@code false} otherwise. 701 */ 702 public boolean matchStrings(String str, @Nullable Map<String, String> uriTemplateVariables) { 703 Matcher matcher = this.pattern.matcher(str); 704 if (matcher.matches()) { 705 if (uriTemplateVariables != null) { 706 // SPR-8455 707 if (this.variableNames.size() != matcher.groupCount()) { 708 throw new IllegalArgumentException("The number of capturing groups in the pattern segment " + 709 this.pattern + " does not match the number of URI template variables it defines, " + 710 "which can occur if capturing groups are used in a URI template regex. " + 711 "Use non-capturing groups instead."); 712 } 713 for (int i = 1; i <= matcher.groupCount(); i++) { 714 String name = this.variableNames.get(i - 1); 715 String value = matcher.group(i); 716 uriTemplateVariables.put(name, value); 717 } 718 } 719 return true; 720 } 721 else { 722 return false; 723 } 724 } 725 } 726 727 728 /** 729 * The default {@link Comparator} implementation returned by 730 * {@link #getPatternComparator(String)}. 731 * <p>In order, the most "generic" pattern is determined by the following: 732 * <ul> 733 * <li>if it's null or a capture all pattern (i.e. it is equal to "/**")</li> 734 * <li>if the other pattern is an actual match</li> 735 * <li>if it's a catch-all pattern (i.e. it ends with "**"</li> 736 * <li>if it's got more "*" than the other pattern</li> 737 * <li>if it's got more "{foo}" than the other pattern</li> 738 * <li>if it's shorter than the other pattern</li> 739 * </ul> 740 */ 741 protected static class AntPatternComparator implements Comparator<String> { 742 743 private final String path; 744 745 public AntPatternComparator(String path) { 746 this.path = path; 747 } 748 749 /** 750 * Compare two patterns to determine which should match first, i.e. which 751 * is the most specific regarding the current path. 752 * @return a negative integer, zero, or a positive integer as pattern1 is 753 * more specific, equally specific, or less specific than pattern2. 754 */ 755 @Override 756 public int compare(String pattern1, String pattern2) { 757 PatternInfo info1 = new PatternInfo(pattern1); 758 PatternInfo info2 = new PatternInfo(pattern2); 759 760 if (info1.isLeastSpecific() && info2.isLeastSpecific()) { 761 return 0; 762 } 763 else if (info1.isLeastSpecific()) { 764 return 1; 765 } 766 else if (info2.isLeastSpecific()) { 767 return -1; 768 } 769 770 boolean pattern1EqualsPath = pattern1.equals(this.path); 771 boolean pattern2EqualsPath = pattern2.equals(this.path); 772 if (pattern1EqualsPath && pattern2EqualsPath) { 773 return 0; 774 } 775 else if (pattern1EqualsPath) { 776 return -1; 777 } 778 else if (pattern2EqualsPath) { 779 return 1; 780 } 781 782 if (info1.isPrefixPattern() && info2.isPrefixPattern()) { 783 return info2.getLength() - info1.getLength(); 784 } 785 else if (info1.isPrefixPattern() && info2.getDoubleWildcards() == 0) { 786 return 1; 787 } 788 else if (info2.isPrefixPattern() && info1.getDoubleWildcards() == 0) { 789 return -1; 790 } 791 792 if (info1.getTotalCount() != info2.getTotalCount()) { 793 return info1.getTotalCount() - info2.getTotalCount(); 794 } 795 796 if (info1.getLength() != info2.getLength()) { 797 return info2.getLength() - info1.getLength(); 798 } 799 800 if (info1.getSingleWildcards() < info2.getSingleWildcards()) { 801 return -1; 802 } 803 else if (info2.getSingleWildcards() < info1.getSingleWildcards()) { 804 return 1; 805 } 806 807 if (info1.getUriVars() < info2.getUriVars()) { 808 return -1; 809 } 810 else if (info2.getUriVars() < info1.getUriVars()) { 811 return 1; 812 } 813 814 return 0; 815 } 816 817 818 /** 819 * Value class that holds information about the pattern, e.g. number of 820 * occurrences of "*", "**", and "{" pattern elements. 821 */ 822 private static class PatternInfo { 823 824 @Nullable 825 private final String pattern; 826 827 private int uriVars; 828 829 private int singleWildcards; 830 831 private int doubleWildcards; 832 833 private boolean catchAllPattern; 834 835 private boolean prefixPattern; 836 837 @Nullable 838 private Integer length; 839 840 public PatternInfo(@Nullable String pattern) { 841 this.pattern = pattern; 842 if (this.pattern != null) { 843 initCounters(); 844 this.catchAllPattern = this.pattern.equals("/**"); 845 this.prefixPattern = !this.catchAllPattern && this.pattern.endsWith("/**"); 846 } 847 if (this.uriVars == 0) { 848 this.length = (this.pattern != null ? this.pattern.length() : 0); 849 } 850 } 851 852 protected void initCounters() { 853 int pos = 0; 854 if (this.pattern != null) { 855 while (pos < this.pattern.length()) { 856 if (this.pattern.charAt(pos) == '{') { 857 this.uriVars++; 858 pos++; 859 } 860 else if (this.pattern.charAt(pos) == '*') { 861 if (pos + 1 < this.pattern.length() && this.pattern.charAt(pos + 1) == '*') { 862 this.doubleWildcards++; 863 pos += 2; 864 } 865 else if (pos > 0 && !this.pattern.substring(pos - 1).equals(".*")) { 866 this.singleWildcards++; 867 pos++; 868 } 869 else { 870 pos++; 871 } 872 } 873 else { 874 pos++; 875 } 876 } 877 } 878 } 879 880 public int getUriVars() { 881 return this.uriVars; 882 } 883 884 public int getSingleWildcards() { 885 return this.singleWildcards; 886 } 887 888 public int getDoubleWildcards() { 889 return this.doubleWildcards; 890 } 891 892 public boolean isLeastSpecific() { 893 return (this.pattern == null || this.catchAllPattern); 894 } 895 896 public boolean isPrefixPattern() { 897 return this.prefixPattern; 898 } 899 900 public int getTotalCount() { 901 return this.uriVars + this.singleWildcards + (2 * this.doubleWildcards); 902 } 903 904 /** 905 * Returns the length of the given pattern, where template variables are considered to be 1 long. 906 */ 907 public int getLength() { 908 if (this.length == null) { 909 this.length = (this.pattern != null ? 910 VARIABLE_PATTERN.matcher(this.pattern).replaceAll("#").length() : 0); 911 } 912 return this.length; 913 } 914 } 915 } 916 917 918 /** 919 * A simple cache for patterns that depend on the configured path separator. 920 */ 921 private static class PathSeparatorPatternCache { 922 923 private final String endsOnWildCard; 924 925 private final String endsOnDoubleWildCard; 926 927 public PathSeparatorPatternCache(String pathSeparator) { 928 this.endsOnWildCard = pathSeparator + "*"; 929 this.endsOnDoubleWildCard = pathSeparator + "**"; 930 } 931 932 public String getEndsOnWildCard() { 933 return this.endsOnWildCard; 934 } 935 936 public String getEndsOnDoubleWildCard() { 937 return this.endsOnDoubleWildCard; 938 } 939 } 940 941}