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