001/* 002 * Licensed to the Apache Software Foundation (ASF) under one 003 * or more contributor license agreements. See the NOTICE file 004 * distributed with this work for additional information 005 * regarding copyright ownership. The ASF licenses this file 006 * to you under the Apache License, Version 2.0 (the 007 * "License"); you may not use this file except in compliance 008 * with the License. You may obtain a copy of the License at 009 * 010 * http://www.apache.org/licenses/LICENSE-2.0 011 * 012 * Unless required by applicable law or agreed to in writing, 013 * software distributed under the License is distributed on an 014 * "AS IS" BASIS, WITHOUT WARRANTIES OR CONDITIONS OF ANY 015 * KIND, either express or implied. See the License for the 016 * specific language governing permissions and limitations 017 * under the License. 018 */ 019package org.apache.shiro.util; 020 021/** 022 * <p>PathMatcher implementation for Ant-style path patterns. 023 * Examples are provided below.</p> 024 * 025 * <p>Part of this mapping code has been kindly borrowed from 026 * <a href="http://ant.apache.org">Apache Ant</a>. 027 * 028 * <p>The mapping matches URLs using the following rules:<br> 029 * <ul> 030 * <li>? matches one character</li> 031 * <li>* matches zero or more characters</li> 032 * <li>** matches zero or more 'directories' in a path</li> 033 * </ul> 034 * 035 * <p>Some examples:<br> 036 * <ul> 037 * <li><code>com/t?st.jsp</code> - matches <code>com/test.jsp</code> but also 038 * <code>com/tast.jsp</code> or <code>com/txst.jsp</code></li> 039 * <li><code>com/*.jsp</code> - matches all <code>.jsp</code> files in the 040 * <code>com</code> directory</li> 041 * <li><code>com/**/test.jsp</code> - matches all <code>test.jsp</code> 042 * files underneath the <code>com</code> path</li> 043 * <li><code>org/apache/shiro/**/*.jsp</code> - matches all <code>.jsp</code> 044 * files underneath the <code>org/apache/shiro</code> path</li> 045 * <li><code>org/**/servlet/bla.jsp</code> - matches 046 * <code>org/apache/shiro/servlet/bla.jsp</code> but also 047 * <code>org/apache/shiro/testing/servlet/bla.jsp</code> and 048 * <code>org/servlet/bla.jsp</code></li> 049 * </ul> 050 * 051 * <p><b>N.B.</b>: This class was borrowed (with much appreciation) from the 052 * <a href="http://www.springframework.org">Spring Framework</a> with modifications. We didn't want to reinvent the 053 * wheel of great work they've done, but also didn't want to force every Shiro user to depend on Spring</p> 054 * 055 * <p>As per the Apache 2.0 license, the original copyright notice and all author and copyright information have 056 * remained in tact.</p> 057 * 058 * @since 16.07.2003 059 */ 060public class AntPathMatcher implements PatternMatcher { 061 062 //TODO - complete JavaDoc 063 064 /** 065 * Default path separator: "/" 066 */ 067 public static final String DEFAULT_PATH_SEPARATOR = "/"; 068 069 private String pathSeparator = DEFAULT_PATH_SEPARATOR; 070 071 072 /** 073 * Set the path separator to use for pattern parsing. 074 * Default is "/", as in Ant. 075 */ 076 public void setPathSeparator(String pathSeparator) { 077 this.pathSeparator = (pathSeparator != null ? pathSeparator : DEFAULT_PATH_SEPARATOR); 078 } 079 080 081 public boolean isPattern(String path) { 082 return (path.indexOf('*') != -1 || path.indexOf('?') != -1); 083 } 084 085 public boolean matches(String pattern, String source) { 086 return match(pattern, source); 087 } 088 089 public boolean match(String pattern, String path) { 090 return doMatch(pattern, path, true); 091 } 092 093 public boolean matchStart(String pattern, String path) { 094 return doMatch(pattern, path, false); 095 } 096 097 098 /** 099 * Actually match the given <code>path</code> against the given <code>pattern</code>. 100 * 101 * @param pattern the pattern to match against 102 * @param path the path String to test 103 * @param fullMatch whether a full pattern match is required 104 * (else a pattern match as far as the given base path goes is sufficient) 105 * @return <code>true</code> if the supplied <code>path</code> matched, 106 * <code>false</code> if it didn't 107 */ 108 protected boolean doMatch(String pattern, String path, boolean fullMatch) { 109 if (path.startsWith(this.pathSeparator) != pattern.startsWith(this.pathSeparator)) { 110 return false; 111 } 112 113 String[] pattDirs = StringUtils.tokenizeToStringArray(pattern, this.pathSeparator); 114 String[] pathDirs = StringUtils.tokenizeToStringArray(path, this.pathSeparator); 115 116 int pattIdxStart = 0; 117 int pattIdxEnd = pattDirs.length - 1; 118 int pathIdxStart = 0; 119 int pathIdxEnd = pathDirs.length - 1; 120 121 // Match all elements up to the first ** 122 while (pattIdxStart <= pattIdxEnd && pathIdxStart <= pathIdxEnd) { 123 String patDir = pattDirs[pattIdxStart]; 124 if ("**".equals(patDir)) { 125 break; 126 } 127 if (!matchStrings(patDir, pathDirs[pathIdxStart])) { 128 return false; 129 } 130 pattIdxStart++; 131 pathIdxStart++; 132 } 133 134 if (pathIdxStart > pathIdxEnd) { 135 // Path is exhausted, only match if rest of pattern is * or **'s 136 if (pattIdxStart > pattIdxEnd) { 137 return (pattern.endsWith(this.pathSeparator) ? 138 path.endsWith(this.pathSeparator) : !path.endsWith(this.pathSeparator)); 139 } 140 if (!fullMatch) { 141 return true; 142 } 143 if (pattIdxStart == pattIdxEnd && pattDirs[pattIdxStart].equals("*") && 144 path.endsWith(this.pathSeparator)) { 145 return true; 146 } 147 for (int i = pattIdxStart; i <= pattIdxEnd; i++) { 148 if (!pattDirs[i].equals("**")) { 149 return false; 150 } 151 } 152 return true; 153 } else if (pattIdxStart > pattIdxEnd) { 154 // String not exhausted, but pattern is. Failure. 155 return false; 156 } else if (!fullMatch && "**".equals(pattDirs[pattIdxStart])) { 157 // Path start definitely matches due to "**" part in pattern. 158 return true; 159 } 160 161 // up to last '**' 162 while (pattIdxStart <= pattIdxEnd && pathIdxStart <= pathIdxEnd) { 163 String patDir = pattDirs[pattIdxEnd]; 164 if (patDir.equals("**")) { 165 break; 166 } 167 if (!matchStrings(patDir, pathDirs[pathIdxEnd])) { 168 return false; 169 } 170 pattIdxEnd--; 171 pathIdxEnd--; 172 } 173 if (pathIdxStart > pathIdxEnd) { 174 // String is exhausted 175 for (int i = pattIdxStart; i <= pattIdxEnd; i++) { 176 if (!pattDirs[i].equals("**")) { 177 return false; 178 } 179 } 180 return true; 181 } 182 183 while (pattIdxStart != pattIdxEnd && pathIdxStart <= pathIdxEnd) { 184 int patIdxTmp = -1; 185 for (int i = pattIdxStart + 1; i <= pattIdxEnd; i++) { 186 if (pattDirs[i].equals("**")) { 187 patIdxTmp = i; 188 break; 189 } 190 } 191 if (patIdxTmp == pattIdxStart + 1) { 192 // '**/**' situation, so skip one 193 pattIdxStart++; 194 continue; 195 } 196 // Find the pattern between padIdxStart & padIdxTmp in str between 197 // strIdxStart & strIdxEnd 198 int patLength = (patIdxTmp - pattIdxStart - 1); 199 int strLength = (pathIdxEnd - pathIdxStart + 1); 200 int foundIdx = -1; 201 202 strLoop: 203 for (int i = 0; i <= strLength - patLength; i++) { 204 for (int j = 0; j < patLength; j++) { 205 String subPat = (String) pattDirs[pattIdxStart + j + 1]; 206 String subStr = (String) pathDirs[pathIdxStart + i + j]; 207 if (!matchStrings(subPat, subStr)) { 208 continue strLoop; 209 } 210 } 211 foundIdx = pathIdxStart + i; 212 break; 213 } 214 215 if (foundIdx == -1) { 216 return false; 217 } 218 219 pattIdxStart = patIdxTmp; 220 pathIdxStart = foundIdx + patLength; 221 } 222 223 for (int i = pattIdxStart; i <= pattIdxEnd; i++) { 224 if (!pattDirs[i].equals("**")) { 225 return false; 226 } 227 } 228 229 return true; 230 } 231 232 /** 233 * Tests whether or not a string matches against a pattern. 234 * The pattern may contain two special characters:<br> 235 * '*' means zero or more characters<br> 236 * '?' means one and only one character 237 * 238 * @param pattern pattern to match against. 239 * Must not be <code>null</code>. 240 * @param str string which must be matched against the pattern. 241 * Must not be <code>null</code>. 242 * @return <code>true</code> if the string matches against the 243 * pattern, or <code>false</code> otherwise. 244 */ 245 private boolean matchStrings(String pattern, String str) { 246 char[] patArr = pattern.toCharArray(); 247 char[] strArr = str.toCharArray(); 248 int patIdxStart = 0; 249 int patIdxEnd = patArr.length - 1; 250 int strIdxStart = 0; 251 int strIdxEnd = strArr.length - 1; 252 char ch; 253 254 boolean containsStar = false; 255 for (char aPatArr : patArr) { 256 if (aPatArr == '*') { 257 containsStar = true; 258 break; 259 } 260 } 261 262 if (!containsStar) { 263 // No '*'s, so we make a shortcut 264 if (patIdxEnd != strIdxEnd) { 265 return false; // Pattern and string do not have the same size 266 } 267 for (int i = 0; i <= patIdxEnd; i++) { 268 ch = patArr[i]; 269 if (ch != '?') { 270 if (ch != strArr[i]) { 271 return false;// Character mismatch 272 } 273 } 274 } 275 return true; // String matches against pattern 276 } 277 278 279 if (patIdxEnd == 0) { 280 return true; // Pattern contains only '*', which matches anything 281 } 282 283 // Process characters before first star 284 while ((ch = patArr[patIdxStart]) != '*' && strIdxStart <= strIdxEnd) { 285 if (ch != '?') { 286 if (ch != strArr[strIdxStart]) { 287 return false;// Character mismatch 288 } 289 } 290 patIdxStart++; 291 strIdxStart++; 292 } 293 if (strIdxStart > strIdxEnd) { 294 // All characters in the string are used. Check if only '*'s are 295 // left in the pattern. If so, we succeeded. Otherwise failure. 296 for (int i = patIdxStart; i <= patIdxEnd; i++) { 297 if (patArr[i] != '*') { 298 return false; 299 } 300 } 301 return true; 302 } 303 304 // Process characters after last star 305 while ((ch = patArr[patIdxEnd]) != '*' && strIdxStart <= strIdxEnd) { 306 if (ch != '?') { 307 if (ch != strArr[strIdxEnd]) { 308 return false;// Character mismatch 309 } 310 } 311 patIdxEnd--; 312 strIdxEnd--; 313 } 314 if (strIdxStart > strIdxEnd) { 315 // All characters in the string are used. Check if only '*'s are 316 // left in the pattern. If so, we succeeded. Otherwise failure. 317 for (int i = patIdxStart; i <= patIdxEnd; i++) { 318 if (patArr[i] != '*') { 319 return false; 320 } 321 } 322 return true; 323 } 324 325 // process pattern between stars. padIdxStart and patIdxEnd point 326 // always to a '*'. 327 while (patIdxStart != patIdxEnd && strIdxStart <= strIdxEnd) { 328 int patIdxTmp = -1; 329 for (int i = patIdxStart + 1; i <= patIdxEnd; i++) { 330 if (patArr[i] == '*') { 331 patIdxTmp = i; 332 break; 333 } 334 } 335 if (patIdxTmp == patIdxStart + 1) { 336 // Two stars next to each other, skip the first one. 337 patIdxStart++; 338 continue; 339 } 340 // Find the pattern between padIdxStart & padIdxTmp in str between 341 // strIdxStart & strIdxEnd 342 int patLength = (patIdxTmp - patIdxStart - 1); 343 int strLength = (strIdxEnd - strIdxStart + 1); 344 int foundIdx = -1; 345 strLoop: 346 for (int i = 0; i <= strLength - patLength; i++) { 347 for (int j = 0; j < patLength; j++) { 348 ch = patArr[patIdxStart + j + 1]; 349 if (ch != '?') { 350 if (ch != strArr[strIdxStart + i + j]) { 351 continue strLoop; 352 } 353 } 354 } 355 356 foundIdx = strIdxStart + i; 357 break; 358 } 359 360 if (foundIdx == -1) { 361 return false; 362 } 363 364 patIdxStart = patIdxTmp; 365 strIdxStart = foundIdx + patLength; 366 } 367 368 // All characters in the string are used. Check if only '*'s are left 369 // in the pattern. If so, we succeeded. Otherwise failure. 370 for (int i = patIdxStart; i <= patIdxEnd; i++) { 371 if (patArr[i] != '*') { 372 return false; 373 } 374 } 375 376 return true; 377 } 378 379 /** 380 * Given a pattern and a full path, determine the pattern-mapped part. 381 * <p>For example: 382 * <ul> 383 * <li>'<code>/docs/cvs/commit.html</code>' and '<code>/docs/cvs/commit.html</code> -> ''</li> 384 * <li>'<code>/docs/*</code>' and '<code>/docs/cvs/commit</code> -> '<code>cvs/commit</code>'</li> 385 * <li>'<code>/docs/cvs/*.html</code>' and '<code>/docs/cvs/commit.html</code> -> '<code>commit.html</code>'</li> 386 * <li>'<code>/docs/**</code>' and '<code>/docs/cvs/commit</code> -> '<code>cvs/commit</code>'</li> 387 * <li>'<code>/docs/**\/*.html</code>' and '<code>/docs/cvs/commit.html</code> -> '<code>cvs/commit.html</code>'</li> 388 * <li>'<code>/*.html</code>' and '<code>/docs/cvs/commit.html</code> -> '<code>docs/cvs/commit.html</code>'</li> 389 * <li>'<code>*.html</code>' and '<code>/docs/cvs/commit.html</code> -> '<code>/docs/cvs/commit.html</code>'</li> 390 * <li>'<code>*</code>' and '<code>/docs/cvs/commit.html</code> -> '<code>/docs/cvs/commit.html</code>'</li> 391 * </ul> 392 * <p>Assumes that {@link #match} returns <code>true</code> for '<code>pattern</code>' 393 * and '<code>path</code>', but does <strong>not</strong> enforce this. 394 */ 395 public String extractPathWithinPattern(String pattern, String path) { 396 String[] patternParts = StringUtils.tokenizeToStringArray(pattern, this.pathSeparator); 397 String[] pathParts = StringUtils.tokenizeToStringArray(path, this.pathSeparator); 398 399 StringBuilder buffer = new StringBuilder(); 400 401 // Add any path parts that have a wildcarded pattern part. 402 int puts = 0; 403 for (int i = 0; i < patternParts.length; i++) { 404 String patternPart = patternParts[i]; 405 if ((patternPart.indexOf('*') > -1 || patternPart.indexOf('?') > -1) && pathParts.length >= i + 1) { 406 if (puts > 0 || (i == 0 && !pattern.startsWith(this.pathSeparator))) { 407 buffer.append(this.pathSeparator); 408 } 409 buffer.append(pathParts[i]); 410 puts++; 411 } 412 } 413 414 // Append any trailing path parts. 415 for (int i = patternParts.length; i < pathParts.length; i++) { 416 if (puts > 0 || i > 0) { 417 buffer.append(this.pathSeparator); 418 } 419 buffer.append(pathParts[i]); 420 } 421 422 return buffer.toString(); 423 } 424 425}