KickJava   Java API By Example, From Geeks To Geeks.

Java > Open Source Codes > org > apache > struts > util > WildcardHelper


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