View Javadoc

1   /*
2    * $Id: WildcardHelper.java 421119 2006-07-12 04:49:11Z wsmoak $
3    *
4    * Copyright 2003-2004 The Apache Software Foundation.
5    *
6    * Licensed under the Apache License, Version 2.0 (the "License");
7    * you may not use this file except in compliance with the License.
8    * You may obtain a copy of the License at
9    *
10   *      http://www.apache.org/licenses/LICENSE-2.0
11   *
12   * Unless required by applicable law or agreed to in writing, software
13   * distributed under the License is distributed on an "AS IS" BASIS,
14   * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
15   * See the License for the specific language governing permissions and
16   * limitations under the License.
17   */
18  package org.apache.struts.util;
19  
20  import java.util.Map;
21  
22  /***
23   * This class is an utility class that perform wilcard-patterns matching and
24   * isolation taken from Apache Cocoon.
25   *
26   * @version $Rev: 421119 $ $Date: 2005-05-07 12:11:38 -0400 (Sat, 07 May 2005)
27   *          $
28   * @since Struts 1.2
29   */
30  public class WildcardHelper {
31      /***
32       * The int representing '*' in the pattern <code>int []</code>.
33       */
34      protected static final int MATCH_FILE = -1;
35  
36      /***
37       * The int representing '**' in the pattern <code>int []</code>.
38       */
39      protected static final int MATCH_PATH = -2;
40  
41      /***
42       * The int representing begin in the pattern <code>int []</code>.
43       */
44      protected static final int MATCH_BEGIN = -4;
45  
46      /***
47       * The int representing end in pattern <code>int []</code>.
48       */
49      protected static final int MATCH_THEEND = -5;
50  
51      /***
52       * The int value that terminates the pattern <code>int []</code>.
53       */
54      protected static final int MATCH_END = -3;
55  
56      /***
57       * <p> Translate the given <code>String</code> into a <code>int []</code>
58       * representing the pattern matchable by this class. <br> This function
59       * translates a <code>String</code> into an int array converting the
60       * special '*' and '\' characters. <br> Here is how the conversion
61       * algorithm works:</p>
62       *
63       * <ul>
64       *
65       * <li>The '*' character is converted to MATCH_FILE, meaning that zero or
66       * more characters (excluding the path separator '/') are to be
67       * matched.</li>
68       *
69       * <li>The '**' sequence is converted to MATCH_PATH, meaning that zero or
70       * more characters (including the path separator '/') are to be
71       * matched.</li>
72       *
73       * <li>The '\' character is used as an escape sequence ('\*' is translated
74       * in '*', not in MATCH_FILE). If an exact '\' character is to be matched
75       * the source string must contain a '//'. sequence.</li>
76       *
77       * </ul>
78       *
79       * <p>When more than two '*' characters, not separated by another
80       * character, are found their value is considered as '**' (MATCH_PATH).
81       * <br> The array is always terminated by a special value (MATCH_END).
82       * <br> All MATCH* values are less than zero, while normal characters are
83       * equal or greater.</p>
84       *
85       * @param data The string to translate.
86       * @return The encoded string as an int array, terminated by the MATCH_END
87       *         value (don't consider the array length).
88       * @throws NullPointerException If data is null.
89       */
90      public int[] compilePattern(String data) {
91          // Prepare the arrays
92          int[] expr = new int[data.length() + 2];
93          char[] buff = data.toCharArray();
94  
95          // Prepare variables for the translation loop
96          int y = 0;
97          boolean slash = false;
98  
99          // Must start from beginning
100         expr[y++] = MATCH_BEGIN;
101 
102         if (buff.length > 0) {
103             if (buff[0] == '//') {
104                 slash = true;
105             } else if (buff[0] == '*') {
106                 expr[y++] = MATCH_FILE;
107             } else {
108                 expr[y++] = buff[0];
109             }
110 
111             // Main translation loop
112             for (int x = 1; x < buff.length; x++) {
113                 // If the previous char was '\' simply copy this char.
114                 if (slash) {
115                     expr[y++] = buff[x];
116                     slash = false;
117 
118                     // If the previous char was not '\' we have to do a bunch of
119                     // checks
120                 } else {
121                     // If this char is '\' declare that and continue
122                     if (buff[x] == '//') {
123                         slash = true;
124 
125                         // If this char is '*' check the previous one
126                     } else if (buff[x] == '*') {
127                         // If the previous character als was '*' match a path
128                         if (expr[y - 1] <= MATCH_FILE) {
129                             expr[y - 1] = MATCH_PATH;
130                         } else {
131                             expr[y++] = MATCH_FILE;
132                         }
133                     } else {
134                         expr[y++] = buff[x];
135                     }
136                 }
137             }
138         }
139 
140         // Must match end at the end
141         expr[y] = MATCH_THEEND;
142 
143         return expr;
144     }
145 
146     /***
147      * Match a pattern agains a string and isolates wildcard replacement into
148      * a <code>Stack</code>.
149      *
150      * @param map  The map to store matched values
151      * @param data The string to match
152      * @param expr The compiled wildcard expression
153      * @return True if a match
154      * @throws NullPointerException If any parameters are null
155      */
156     public boolean match(Map map, String data, int[] expr) {
157         if (map == null) {
158             throw new NullPointerException("No map provided");
159         }
160 
161         if (data == null) {
162             throw new NullPointerException("No data provided");
163         }
164 
165         if (expr == null) {
166             throw new NullPointerException("No pattern expression provided");
167         }
168 
169         char[] buff = data.toCharArray();
170 
171         // Allocate the result buffer
172         char[] rslt = new char[expr.length + buff.length];
173 
174         // The previous and current position of the expression character
175         // (MATCH_*)
176         int charpos = 0;
177 
178         // The position in the expression, input, translation and result arrays
179         int exprpos = 0;
180         int buffpos = 0;
181         int rsltpos = 0;
182         int offset = -1;
183 
184         // The matching count
185         int mcount = 0;
186 
187         // We want the complete data be in {0}
188         map.put(Integer.toString(mcount), data);
189 
190         // First check for MATCH_BEGIN
191         boolean matchBegin = false;
192 
193         if (expr[charpos] == MATCH_BEGIN) {
194             matchBegin = true;
195             exprpos = ++charpos;
196         }
197 
198         // Search the fist expression character (except MATCH_BEGIN - already
199         // skipped)
200         while (expr[charpos] >= 0) {
201             charpos++;
202         }
203 
204         // The expression charater (MATCH_*)
205         int exprchr = expr[charpos];
206 
207         while (true) {
208             // Check if the data in the expression array before the current
209             // expression character matches the data in the input buffer
210             if (matchBegin) {
211                 if (!matchArray(expr, exprpos, charpos, buff, buffpos)) {
212                     return (false);
213                 }
214 
215                 matchBegin = false;
216             } else {
217                 offset = indexOfArray(expr, exprpos, charpos, buff, buffpos);
218 
219                 if (offset < 0) {
220                     return (false);
221                 }
222             }
223 
224             // Check for MATCH_BEGIN
225             if (matchBegin) {
226                 if (offset != 0) {
227                     return (false);
228                 }
229 
230                 matchBegin = false;
231             }
232 
233             // Advance buffpos
234             buffpos += (charpos - exprpos);
235 
236             // Check for END's
237             if (exprchr == MATCH_END) {
238                 if (rsltpos > 0) {
239                     map.put(Integer.toString(++mcount),
240                         new String(rslt, 0, rsltpos));
241                 }
242 
243                 // Don't care about rest of input buffer
244                 return (true);
245             } else if (exprchr == MATCH_THEEND) {
246                 if (rsltpos > 0) {
247                     map.put(Integer.toString(++mcount),
248                         new String(rslt, 0, rsltpos));
249                 }
250 
251                 // Check that we reach buffer's end
252                 return (buffpos == buff.length);
253             }
254 
255             // Search the next expression character
256             exprpos = ++charpos;
257 
258             while (expr[charpos] >= 0) {
259                 charpos++;
260             }
261 
262             int prevchr = exprchr;
263 
264             exprchr = expr[charpos];
265 
266             // We have here prevchr == * or **.
267             offset =
268                 (prevchr == MATCH_FILE)
269                 ? indexOfArray(expr, exprpos, charpos, buff, buffpos)
270                 : lastIndexOfArray(expr, exprpos, charpos, buff, buffpos);
271 
272             if (offset < 0) {
273                 return (false);
274             }
275 
276             // Copy the data from the source buffer into the result buffer
277             // to substitute the expression character
278             if (prevchr == MATCH_PATH) {
279                 while (buffpos < offset) {
280                     rslt[rsltpos++] = buff[buffpos++];
281                 }
282             } else {
283                 // Matching file, don't copy '/'
284                 while (buffpos < offset) {
285                     if (buff[buffpos] == '/') {
286                         return (false);
287                     }
288 
289                     rslt[rsltpos++] = buff[buffpos++];
290                 }
291             }
292 
293             map.put(Integer.toString(++mcount), new String(rslt, 0, rsltpos));
294             rsltpos = 0;
295         }
296     }
297 
298     /***
299      * Get the offset of a part of an int array within a char array. <br> This
300      * method return the index in d of the first occurrence after dpos of that
301      * part of array specified by r, starting at rpos and terminating at
302      * rend.
303      *
304      * @param r    The array containing the data that need to be matched in
305      *             d.
306      * @param rpos The index of the first character in r to look for.
307      * @param rend The index of the last character in r to look for plus 1.
308      * @param d    The array of char that should contain a part of r.
309      * @param dpos The starting offset in d for the matching.
310      * @return The offset in d of the part of r matched in d or -1 if that was
311      *         not found.
312      */
313     protected int indexOfArray(int[] r, int rpos, int rend, char[] d,
314         int dpos) {
315         // Check if pos and len are legal
316         if (rend < rpos) {
317             throw new IllegalArgumentException("rend < rpos");
318         }
319 
320         // If we need to match a zero length string return current dpos
321         if (rend == rpos) {
322             return (d.length); //?? dpos?
323         }
324 
325         // If we need to match a 1 char length string do it simply
326         if ((rend - rpos) == 1) {
327             // Search for the specified character
328             for (int x = dpos; x < d.length; x++) {
329                 if (r[rpos] == d[x]) {
330                     return (x);
331                 }
332             }
333         }
334 
335         // Main string matching loop. It gets executed if the characters to
336         // match are less then the characters left in the d buffer
337         while (((dpos + rend) - rpos) <= d.length) {
338             // Set current startpoint in d
339             int y = dpos;
340 
341             // Check every character in d for equity. If the string is matched
342             // return dpos
343             for (int x = rpos; x <= rend; x++) {
344                 if (x == rend) {
345                     return (dpos);
346                 }
347 
348                 if (r[x] != d[y++]) {
349                     break;
350                 }
351             }
352 
353             // Increase dpos to search for the same string at next offset
354             dpos++;
355         }
356 
357         // The remaining chars in d buffer were not enough or the string
358         // wasn't matched
359         return (-1);
360     }
361 
362     /***
363      * Get the offset of a last occurance of an int array within a char array.
364      * <br> This method return the index in d of the last occurrence after
365      * dpos of that part of array specified by r, starting at rpos and
366      * terminating at rend.
367      *
368      * @param r    The array containing the data that need to be matched in
369      *             d.
370      * @param rpos The index of the first character in r to look for.
371      * @param rend The index of the last character in r to look for plus 1.
372      * @param d    The array of char that should contain a part of r.
373      * @param dpos The starting offset in d for the matching.
374      * @return The offset in d of the last part of r matched in d or -1 if
375      *         that was not found.
376      */
377     protected int lastIndexOfArray(int[] r, int rpos, int rend, char[] d,
378         int dpos) {
379         // Check if pos and len are legal
380         if (rend < rpos) {
381             throw new IllegalArgumentException("rend < rpos");
382         }
383 
384         // If we need to match a zero length string return current dpos
385         if (rend == rpos) {
386             return (d.length); //?? dpos?
387         }
388 
389         // If we need to match a 1 char length string do it simply
390         if ((rend - rpos) == 1) {
391             // Search for the specified character
392             for (int x = d.length - 1; x > dpos; x--) {
393                 if (r[rpos] == d[x]) {
394                     return (x);
395                 }
396             }
397         }
398 
399         // Main string matching loop. It gets executed if the characters to
400         // match are less then the characters left in the d buffer
401         int l = d.length - (rend - rpos);
402 
403         while (l >= dpos) {
404             // Set current startpoint in d
405             int y = l;
406 
407             // Check every character in d for equity. If the string is matched
408             // return dpos
409             for (int x = rpos; x <= rend; x++) {
410                 if (x == rend) {
411                     return (l);
412                 }
413 
414                 if (r[x] != d[y++]) {
415                     break;
416                 }
417             }
418 
419             // Decrease l to search for the same string at next offset
420             l--;
421         }
422 
423         // The remaining chars in d buffer were not enough or the string
424         // wasn't matched
425         return (-1);
426     }
427 
428     /***
429      * Matches elements of array r from rpos to rend with array d, starting
430      * from dpos. <br> This method return true if elements of array r from
431      * rpos to rend equals elements of array d starting from dpos to
432      * dpos+(rend-rpos).
433      *
434      * @param r    The array containing the data that need to be matched in
435      *             d.
436      * @param rpos The index of the first character in r to look for.
437      * @param rend The index of the last character in r to look for.
438      * @param d    The array of char that should start from a part of r.
439      * @param dpos The starting offset in d for the matching.
440      * @return true if array d starts from portion of array r.
441      */
442     protected boolean matchArray(int[] r, int rpos, int rend, char[] d,
443         int dpos) {
444         if ((d.length - dpos) < (rend - rpos)) {
445             return (false);
446         }
447 
448         for (int i = rpos; i < rend; i++) {
449             if (r[i] != d[dpos++]) {
450                 return (false);
451             }
452         }
453 
454         return (true);
455     }
456 }