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     */
019    package 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/&#42;&#42;/test.jsp</code> - matches all <code>test.jsp</code>
042     * files underneath the <code>com</code> path</li>
043     * <li><code>org/apache/shiro/&#42;&#42;/*.jsp</code> - matches all <code>.jsp</code>
044     * files underneath the <code>org/apache/shiro</code> path</li>
045     * <li><code>org/&#42;&#42;/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     */
060    public 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    }