org.argeo.osgi.boot/src/org/argeo/osgi/boot/internal/springutil/AntPathMatcher.java

   1 /*
   2  * Copyright 2002-2007 the original author or authors.
   3  *
   4  * Licensed under the Apache License, Version 2.0 (the "License");
   5  * you may not use this file except in compliance with the License.
   6  * You may obtain a copy of the License at
   7  *
   8  *      http://www.apache.org/licenses/LICENSE-2.0
   9  *
  10  * Unless required by applicable law or agreed to in writing, software
  11  * distributed under the License is distributed on an "AS IS" BASIS,
  12  * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
  13  * See the License for the specific language governing permissions and
  14  * limitations under the License.
  15  */
  16
  17 package org.argeo.osgi.boot.internal.springutil;
  18
  19 /**
  20  * PathMatcher implementation for Ant-style path patterns.
  21  * Examples are provided below.
  22  *
  23  * <p>Part of this mapping code has been kindly borrowed from
  24  * <a href="http://ant.apache.org">Apache Ant</a>.
  25  *
  26  * <p>The mapping matches URLs using the following rules:<br>
  27  * <ul>
  28  * <li>? matches one character</li>
  29  * <li>* matches zero or more characters</li>
  30  * <li>** matches zero or more 'directories' in a path</li>
  31  * </ul>
  32  *
  33  * <p>Some examples:<br>
  34  * <ul>
  35  * <li><code>com/t?st.jsp</code> - matches <code>com/test.jsp</code> but also
  36  * <code>com/tast.jsp</code> or <code>com/txst.jsp</code></li>
  37  * <li><code>com/*.jsp</code> - matches all <code>.jsp</code> files in the
  38  * <code>com</code> directory</li>
  39  * <li><code>com/&#42;&#42;/test.jsp</code> - matches all <code>test.jsp</code>
  40  * files underneath the <code>com</code> path</li>
  41  * <li><code>org/springframework/&#42;&#42;/*.jsp</code> - matches all <code>.jsp</code>
  42  * files underneath the <code>org/springframework</code> path</li>
  43  * <li><code>org/&#42;&#42;/servlet/bla.jsp</code> - matches
  44  * <code>org/springframework/servlet/bla.jsp</code> but also
  45  * <code>org/springframework/testing/servlet/bla.jsp</code> and
  46  * <code>org/servlet/bla.jsp</code></li>
  47  * </ul>
  48  *
  49  * @author Alef Arendsen
  50  * @author Juergen Hoeller
  51  * @author Rob Harrop
  52  * @since 16.07.2003
  53  */
  54 public class AntPathMatcher implements PathMatcher {
  55
  56         /** Default path separator: "/" */
  57         public static final String DEFAULT_PATH_SEPARATOR = "/";
  58
  59         private String pathSeparator = DEFAULT_PATH_SEPARATOR;
  60
  61
  62         /**
  63          * Set the path separator to use for pattern parsing.
  64          * Default is "/", as in Ant.
  65          */
  66         public void setPathSeparator(String pathSeparator) {
  67                 this.pathSeparator = (pathSeparator != null ? pathSeparator : DEFAULT_PATH_SEPARATOR);
  68         }
  69
  70
  71         public boolean isPattern(String path) {
  72                 return (path.indexOf('*') != -1 || path.indexOf('?') != -1);
  73         }
  74
  75         public boolean match(String pattern, String path) {
  76                 return doMatch(pattern, path, true);
  77         }
  78
  79         public boolean matchStart(String pattern, String path) {
  80                 return doMatch(pattern, path, false);
  81         }
  82
  83
  84         /**
  85          * Actually match the given <code>path</code> against the given <code>pattern</code>.
  86          * @param pattern the pattern to match against
  87          * @param path the path String to test
  88          * @param fullMatch whether a full pattern match is required
  89          * (else a pattern match as far as the given base path goes is sufficient)
  90          * @return <code>true</code> if the supplied <code>path</code> matched,
  91          * <code>false</code> if it didn't
  92          */
  93         protected boolean doMatch(String pattern, String path, boolean fullMatch) {
  94                 if (path.startsWith(this.pathSeparator) != pattern.startsWith(this.pathSeparator)) {
  95                         return false;
  96                 }
  97
  98                 String[] pattDirs = StringUtils.tokenizeToStringArray(pattern, this.pathSeparator);
  99                 String[] pathDirs = StringUtils.tokenizeToStringArray(path, this.pathSeparator);
 100
 101                 int pattIdxStart = 0;
 102                 int pattIdxEnd = pattDirs.length - 1;
 103                 int pathIdxStart = 0;
 104                 int pathIdxEnd = pathDirs.length - 1;
 105
 106                 // Match all elements up to the first **
 107                 while (pattIdxStart <= pattIdxEnd && pathIdxStart <= pathIdxEnd) {
 108                         String patDir = pattDirs[pattIdxStart];
 109                         if ("**".equals(patDir)) {
 110                                 break;
 111                         }
 112                         if (!matchStrings(patDir, pathDirs[pathIdxStart])) {
 113                                 return false;
 114                         }
 115                         pattIdxStart++;
 116                         pathIdxStart++;
 117                 }
 118
 119                 if (pathIdxStart > pathIdxEnd) {
 120                         // Path is exhausted, only match if rest of pattern is * or **'s
 121                         if (pattIdxStart > pattIdxEnd) {
 122                                 return (pattern.endsWith(this.pathSeparator) ?
 123                                                 path.endsWith(this.pathSeparator) : !path.endsWith(this.pathSeparator));
 124                         }
 125                         if (!fullMatch) {
 126                                 return true;
 127                         }
 128                         if (pattIdxStart == pattIdxEnd && pattDirs[pattIdxStart].equals("*") &&
 129                                         path.endsWith(this.pathSeparator)) {
 130                                 return true;
 131                         }
 132                         for (int i = pattIdxStart; i <= pattIdxEnd; i++) {
 133                                 if (!pattDirs[i].equals("**")) {
 134                                         return false;
 135                                 }
 136                         }
 137                         return true;
 138                 }
 139                 else if (pattIdxStart > pattIdxEnd) {
 140                         // String not exhausted, but pattern is. Failure.
 141                         return false;
 142                 }
 143                 else if (!fullMatch && "**".equals(pattDirs[pattIdxStart])) {
 144                         // Path start definitely matches due to "**" part in pattern.
 145                         return true;
 146                 }
 147
 148                 // up to last '**'
 149                 while (pattIdxStart <= pattIdxEnd && pathIdxStart <= pathIdxEnd) {
 150                         String patDir = pattDirs[pattIdxEnd];
 151                         if (patDir.equals("**")) {
 152                                 break;
 153                         }
 154                         if (!matchStrings(patDir, pathDirs[pathIdxEnd])) {
 155                                 return false;
 156                         }
 157                         pattIdxEnd--;
 158                         pathIdxEnd--;
 159                 }
 160                 if (pathIdxStart > pathIdxEnd) {
 161                         // String is exhausted
 162                         for (int i = pattIdxStart; i <= pattIdxEnd; i++) {
 163                                 if (!pattDirs[i].equals("**")) {
 164                                         return false;
 165                                 }
 166                         }
 167                         return true;
 168                 }
 169
 170                 while (pattIdxStart != pattIdxEnd && pathIdxStart <= pathIdxEnd) {
 171                         int patIdxTmp = -1;
 172                         for (int i = pattIdxStart + 1; i <= pattIdxEnd; i++) {
 173                                 if (pattDirs[i].equals("**")) {
 174                                         patIdxTmp = i;
 175                                         break;
 176                                 }
 177                         }
 178                         if (patIdxTmp == pattIdxStart + 1) {
 179                                 // '**/**' situation, so skip one
 180                                 pattIdxStart++;
 181                                 continue;
 182                         }
 183                         // Find the pattern between padIdxStart & padIdxTmp in str between
 184                         // strIdxStart & strIdxEnd
 185                         int patLength = (patIdxTmp - pattIdxStart - 1);
 186                         int strLength = (pathIdxEnd - pathIdxStart + 1);
 187                         int foundIdx = -1;
 188
 189                         strLoop:
 190                             for (int i = 0; i <= strLength - patLength; i++) {
 191                                     for (int j = 0; j < patLength; j++) {
 192                                             String subPat = (String) pattDirs[pattIdxStart + j + 1];
 193                                             String subStr = (String) pathDirs[pathIdxStart + i + j];
 194                                             if (!matchStrings(subPat, subStr)) {
 195                                                     continue strLoop;
 196                                             }
 197                                     }
 198                                     foundIdx = pathIdxStart + i;
 199                                     break;
 200                             }
 201
 202                         if (foundIdx == -1) {
 203                                 return false;
 204                         }
 205
 206                         pattIdxStart = patIdxTmp;
 207                         pathIdxStart = foundIdx + patLength;
 208                 }
 209
 210                 for (int i = pattIdxStart; i <= pattIdxEnd; i++) {
 211                         if (!pattDirs[i].equals("**")) {
 212                                 return false;
 213                         }
 214                 }
 215
 216                 return true;
 217         }
 218
 219         /**
 220          * Tests whether or not a string matches against a pattern.
 221          * The pattern may contain two special characters:<br>
 222          * '*' means zero or more characters<br>
 223          * '?' means one and only one character
 224          * @param pattern pattern to match against.
 225          * Must not be <code>null</code>.
 226          * @param str string which must be matched against the pattern.
 227          * Must not be <code>null</code>.
 228          * @return <code>true</code> if the string matches against the
 229          * pattern, or <code>false</code> otherwise.
 230          */
 231         private boolean matchStrings(String pattern, String str) {
 232                 char[] patArr = pattern.toCharArray();
 233                 char[] strArr = str.toCharArray();
 234                 int patIdxStart = 0;
 235                 int patIdxEnd = patArr.length - 1;
 236                 int strIdxStart = 0;
 237                 int strIdxEnd = strArr.length - 1;
 238                 char ch;
 239
 240                 boolean containsStar = false;
 241                 for (int i = 0; i < patArr.length; i++) {
 242                         if (patArr[i] == '*') {
 243                                 containsStar = true;
 244                                 break;
 245                         }
 246                 }
 247
 248                 if (!containsStar) {
 249                         // No '*'s, so we make a shortcut
 250                         if (patIdxEnd != strIdxEnd) {
 251                                 return false; // Pattern and string do not have the same size
 252                         }
 253                         for (int i = 0; i <= patIdxEnd; i++) {
 254                                 ch = patArr[i];
 255                                 if (ch != '?') {
 256                                         if (ch != strArr[i]) {
 257                                                 return false;// Character mismatch
 258                                         }
 259                                 }
 260                         }
 261                         return true; // String matches against pattern
 262                 }
 263
 264
 265                 if (patIdxEnd == 0) {
 266                         return true; // Pattern contains only '*', which matches anything
 267                 }
 268
 269                 // Process characters before first star
 270                 while ((ch = patArr[patIdxStart]) != '*' && strIdxStart <= strIdxEnd) {
 271                         if (ch != '?') {
 272                                 if (ch != strArr[strIdxStart]) {
 273                                         return false;// Character mismatch
 274                                 }
 275                         }
 276                         patIdxStart++;
 277                         strIdxStart++;
 278                 }
 279                 if (strIdxStart > strIdxEnd) {
 280                         // All characters in the string are used. Check if only '*'s are
 281                         // left in the pattern. If so, we succeeded. Otherwise failure.
 282                         for (int i = patIdxStart; i <= patIdxEnd; i++) {
 283                                 if (patArr[i] != '*') {
 284                                         return false;
 285                                 }
 286                         }
 287                         return true;
 288                 }
 289
 290                 // Process characters after last star
 291                 while ((ch = patArr[patIdxEnd]) != '*' && strIdxStart <= strIdxEnd) {
 292                         if (ch != '?') {
 293                                 if (ch != strArr[strIdxEnd]) {
 294                                         return false;// Character mismatch
 295                                 }
 296                         }
 297                         patIdxEnd--;
 298                         strIdxEnd--;
 299                 }
 300                 if (strIdxStart > strIdxEnd) {
 301                         // All characters in the string are used. Check if only '*'s are
 302                         // left in the pattern. If so, we succeeded. Otherwise failure.
 303                         for (int i = patIdxStart; i <= patIdxEnd; i++) {
 304                                 if (patArr[i] != '*') {
 305                                         return false;
 306                                 }
 307                         }
 308                         return true;
 309                 }
 310
 311                 // process pattern between stars. padIdxStart and patIdxEnd point
 312                 // always to a '*'.
 313                 while (patIdxStart != patIdxEnd && strIdxStart <= strIdxEnd) {
 314                         int patIdxTmp = -1;
 315                         for (int i = patIdxStart + 1; i <= patIdxEnd; i++) {
 316                                 if (patArr[i] == '*') {
 317                                         patIdxTmp = i;
 318                                         break;
 319                                 }
 320                         }
 321                         if (patIdxTmp == patIdxStart + 1) {
 322                                 // Two stars next to each other, skip the first one.
 323                                 patIdxStart++;
 324                                 continue;
 325                         }
 326                         // Find the pattern between padIdxStart & padIdxTmp in str between
 327                         // strIdxStart & strIdxEnd
 328                         int patLength = (patIdxTmp - patIdxStart - 1);
 329                         int strLength = (strIdxEnd - strIdxStart + 1);
 330                         int foundIdx = -1;
 331                         strLoop:
 332                         for (int i = 0; i <= strLength - patLength; i++) {
 333                                 for (int j = 0; j < patLength; j++) {
 334                                         ch = patArr[patIdxStart + j + 1];
 335                                         if (ch != '?') {
 336                                                 if (ch != strArr[strIdxStart + i + j]) {
 337                                                         continue strLoop;
 338                                                 }
 339                                         }
 340                                 }
 341
 342                                 foundIdx = strIdxStart + i;
 343                                 break;
 344                         }
 345
 346                         if (foundIdx == -1) {
 347                                 return false;
 348                         }
 349
 350                         patIdxStart = patIdxTmp;
 351                         strIdxStart = foundIdx + patLength;
 352                 }
 353
 354                 // All characters in the string are used. Check if only '*'s are left
 355                 // in the pattern. If so, we succeeded. Otherwise failure.
 356                 for (int i = patIdxStart; i <= patIdxEnd; i++) {
 357                         if (patArr[i] != '*') {
 358                                 return false;
 359                         }
 360                 }
 361
 362                 return true;
 363         }
 364
 365         /**
 366          * Given a pattern and a full path, determine the pattern-mapped part.
 367          * <p>For example:
 368          * <ul>
 369          * <li>'<code>/docs/cvs/commit.html</code>' and '<code>/docs/cvs/commit.html</code> to ''</li>
 370          * <li>'<code>/docs/*</code>' and '<code>/docs/cvs/commit</code> to '<code>cvs/commit</code>'</li>
 371          * <li>'<code>/docs/cvs/*.html</code>' and '<code>/docs/cvs/commit.html</code> to '<code>commit.html</code>'</li>
 372          * <li>'<code>/docs/**</code>' and '<code>/docs/cvs/commit</code> to '<code>cvs/commit</code>'</li>
 373          * <li>'<code>/docs/**\/*.html</code>' and '<code>/docs/cvs/commit.html</code> to '<code>cvs/commit.html</code>'</li>
 374          * <li>'<code>/*.html</code>' and '<code>/docs/cvs/commit.html</code> to '<code>docs/cvs/commit.html</code>'</li>
 375          * <li>'<code>*.html</code>' and '<code>/docs/cvs/commit.html</code> to '<code>/docs/cvs/commit.html</code>'</li>
 376          * <li>'<code>*</code>' and '<code>/docs/cvs/commit.html</code> to '<code>/docs/cvs/commit.html</code>'</li>
 377          * </ul>
 378          * <p>Assumes that {@link #match} returns <code>true</code> for '<code>pattern</code>'
 379          * and '<code>path</code>', but does <strong>not</strong> enforce this.
 380          */
 381         public String extractPathWithinPattern(String pattern, String path) {
 382                 String[] patternParts = StringUtils.tokenizeToStringArray(pattern, this.pathSeparator);
 383                 String[] pathParts = StringUtils.tokenizeToStringArray(path, this.pathSeparator);
 384
 385                 StringBuffer buffer = new StringBuffer();
 386
 387                 // Add any path parts that have a wildcarded pattern part.
 388                 int puts = 0;
 389                 for (int i = 0; i < patternParts.length; i++) {
 390                         String patternPart = patternParts[i];
 391                         if ((patternPart.indexOf('*') > -1 || patternPart.indexOf('?') > -1) && pathParts.length >= i + 1) {
 392                                 if (puts > 0 || (i == 0 && !pattern.startsWith(this.pathSeparator))) {
 393                                         buffer.append(this.pathSeparator);
 394                                 }
 395                                 buffer.append(pathParts[i]);
 396                                 puts++;
 397                         }
 398                 }
 399
 400                 // Append any trailing path parts.
 401                 for (int i = patternParts.length; i < pathParts.length; i++) {
 402                         if (puts > 0 || i > 0) {
 403                                 buffer.append(this.pathSeparator);
 404                         }
 405                         buffer.append(pathParts[i]);
 406                 }
 407
 408                 return buffer.toString();
 409         }
 410
 411 }