1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
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
92 int[] expr = new int[data.length() + 2];
93 char[] buff = data.toCharArray();
94
95
96 int y = 0;
97 boolean slash = false;
98
99
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
112 for (int x = 1; x < buff.length; x++) {
113
114 if (slash) {
115 expr[y++] = buff[x];
116 slash = false;
117
118
119
120 } else {
121
122 if (buff[x] == '//') {
123 slash = true;
124
125
126 } else if (buff[x] == '*') {
127
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
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
172 char[] rslt = new char[expr.length + buff.length];
173
174
175
176 int charpos = 0;
177
178
179 int exprpos = 0;
180 int buffpos = 0;
181 int rsltpos = 0;
182 int offset = -1;
183
184
185 int mcount = 0;
186
187
188 map.put(Integer.toString(mcount), data);
189
190
191 boolean matchBegin = false;
192
193 if (expr[charpos] == MATCH_BEGIN) {
194 matchBegin = true;
195 exprpos = ++charpos;
196 }
197
198
199
200 while (expr[charpos] >= 0) {
201 charpos++;
202 }
203
204
205 int exprchr = expr[charpos];
206
207 while (true) {
208
209
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
225 if (matchBegin) {
226 if (offset != 0) {
227 return (false);
228 }
229
230 matchBegin = false;
231 }
232
233
234 buffpos += (charpos - exprpos);
235
236
237 if (exprchr == MATCH_END) {
238 if (rsltpos > 0) {
239 map.put(Integer.toString(++mcount),
240 new String(rslt, 0, rsltpos));
241 }
242
243
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
252 return (buffpos == buff.length);
253 }
254
255
256 exprpos = ++charpos;
257
258 while (expr[charpos] >= 0) {
259 charpos++;
260 }
261
262 int prevchr = exprchr;
263
264 exprchr = expr[charpos];
265
266
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
277
278 if (prevchr == MATCH_PATH) {
279 while (buffpos < offset) {
280 rslt[rsltpos++] = buff[buffpos++];
281 }
282 } else {
283
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
316 if (rend < rpos) {
317 throw new IllegalArgumentException("rend < rpos");
318 }
319
320
321 if (rend == rpos) {
322 return (d.length);
323 }
324
325
326 if ((rend - rpos) == 1) {
327
328 for (int x = dpos; x < d.length; x++) {
329 if (r[rpos] == d[x]) {
330 return (x);
331 }
332 }
333 }
334
335
336
337 while (((dpos + rend) - rpos) <= d.length) {
338
339 int y = dpos;
340
341
342
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
354 dpos++;
355 }
356
357
358
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
380 if (rend < rpos) {
381 throw new IllegalArgumentException("rend < rpos");
382 }
383
384
385 if (rend == rpos) {
386 return (d.length);
387 }
388
389
390 if ((rend - rpos) == 1) {
391
392 for (int x = d.length - 1; x > dpos; x--) {
393 if (r[rpos] == d[x]) {
394 return (x);
395 }
396 }
397 }
398
399
400
401 int l = d.length - (rend - rpos);
402
403 while (l >= dpos) {
404
405 int y = l;
406
407
408
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
420 l--;
421 }
422
423
424
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 }