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