1 /*
2 * $Id: WildcardHelper.java 829574 2009-10-25 14:15:31Z apetrelli $
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.tiles.util;
22
23 import java.util.ArrayList;
24 import java.util.Iterator;
25 import java.util.List;
26 import java.util.Map;
27
28 /**
29 * This class is an utility class that perform wilcard-patterns matching and
30 * isolation taken from Apache Struts that is taken, in turn, from Apache
31 * Struts.
32 *
33 * @version $Rev: 829574 $ $Date: 2009-10-26 01:15:31 +1100 (Mon, 26 Oct 2009) $
34 * @since 2.1.0
35 */
36 public class WildcardHelper {
37 /**
38 * The int representing '*' in the pattern <code>int []</code>.
39 *
40 * @since 2.1.0
41 */
42 protected static final int MATCH_FILE = -1;
43
44 /**
45 * The int representing '**' in the pattern <code>int []</code>.
46 *
47 * @since 2.1.0
48 */
49 protected static final int MATCH_PATH = -2;
50
51 /**
52 * The int representing begin in the pattern <code>int []</code>.
53 *
54 * @since 2.1.0
55 */
56 protected static final int MATCH_BEGIN = -4;
57
58 /**
59 * The int representing end in pattern <code>int []</code>.
60 *
61 * @since 2.1.0
62 */
63 protected static final int MATCH_THEEND = -5;
64
65 /**
66 * The int value that terminates the pattern <code>int []</code>.
67 *
68 * @since 2.1.0
69 */
70 protected static final int MATCH_END = -3;
71
72 /**
73 * The length of the placeholder.
74 *
75 * @since 2.1.0
76 */
77 private static final int PLACEHOLDER_LENGTH = 3;
78
79 /**
80 * <p>
81 * Translate the given <code>String</code> into a <code>int []</code>
82 * representing the pattern matchable by this class. <br>
83 * This function translates a <code>String</code> into an int array
84 * converting the special '*' and '\' characters. <br>
85 * Here is how the conversion algorithm works:
86 * </p>
87 *
88 * <ul>
89 *
90 * <li>The '*' character is converted to MATCH_FILE, meaning that zero or
91 * more characters (excluding the path separator '/') are to be matched.</li>
92 *
93 * <li>The '**' sequence is converted to MATCH_PATH, meaning that zero or
94 * more characters (including the path separator '/') are to be matched.</li>
95 *
96 * <li>The '\' character is used as an escape sequence ('\*' is translated
97 * in '*', not in MATCH_FILE). If an exact '\' character is to be matched
98 * the source string must contain a '\\'. sequence.</li>
99 *
100 * </ul>
101 *
102 * <p>
103 * When more than two '*' characters, not separated by another character,
104 * are found their value is considered as '**' (MATCH_PATH). <br>
105 * The array is always terminated by a special value (MATCH_END). <br>
106 * All MATCH* values are less than zero, while normal characters are equal
107 * or greater.
108 * </p>
109 *
110 * @param data The string to translate.
111 * @return The encoded string as an int array, terminated by the MATCH_END
112 * value (don't consider the array length).
113 * @throws NullPointerException If data is null.
114 * @since 2.1.0
115 */
116 public int[] compilePattern(String data) {
117 // Prepare the arrays
118 int[] expr = new int[data.length() + 2];
119 char[] buff = data.toCharArray();
120
121 // Prepare variables for the translation loop
122 int y = 0;
123 boolean slash = false;
124
125 // Must start from beginning
126 expr[y++] = MATCH_BEGIN;
127
128 if (buff.length > 0) {
129 if (buff[0] == '\\') {
130 slash = true;
131 } else if (buff[0] == '*') {
132 expr[y++] = MATCH_FILE;
133 } else {
134 expr[y++] = buff[0];
135 }
136
137 // Main translation loop
138 for (int x = 1; x < buff.length; x++) {
139 // If the previous char was '\' simply copy this char.
140 if (slash) {
141 expr[y++] = buff[x];
142 slash = false;
143
144 // If the previous char was not '\' we have to do a bunch of
145 // checks
146 } else {
147 // If this char is '\' declare that and continue
148 if (buff[x] == '\\') {
149 slash = true;
150
151 // If this char is '*' check the previous one
152 } else if (buff[x] == '*') {
153 // If the previous character als was '*' match a path
154 if (expr[y - 1] <= MATCH_FILE) {
155 expr[y - 1] = MATCH_PATH;
156 } else {
157 expr[y++] = MATCH_FILE;
158 }
159 } else {
160 expr[y++] = buff[x];
161 }
162 }
163 }
164 }
165
166 // Must match end at the end
167 expr[y] = MATCH_THEEND;
168
169 return expr;
170 }
171
172 /**
173 * Match a pattern agains a string and isolates wildcard replacement into a
174 * <code>Stack</code>.
175 *
176 * @param data The string to match
177 * @param expr The compiled wildcard expression
178 * @return The list of matched variables, or <code>null</code> if it does not match.
179 * @throws NullPointerException If any parameters are null
180 * @since 2.2.0
181 */
182 public List<String> match(String data, int[] expr) {
183 List<String> varsValues = null;
184
185 if (data == null) {
186 throw new NullPointerException("No data provided");
187 }
188
189 if (expr == null) {
190 throw new NullPointerException("No pattern expression provided");
191 }
192
193 char[] buff = data.toCharArray();
194
195 // Allocate the result buffer
196 char[] rslt = new char[expr.length + buff.length];
197
198 // The previous and current position of the expression character
199 // (MATCH_*)
200 int charpos = 0;
201
202 // The position in the expression, input, translation and result arrays
203 int exprpos = 0;
204 int buffpos = 0;
205 int rsltpos = 0;
206 int offset = -1;
207
208 // First check for MATCH_BEGIN
209 boolean matchBegin = false;
210
211 if (expr[charpos] == MATCH_BEGIN) {
212 matchBegin = true;
213 exprpos = ++charpos;
214 }
215
216 // Search the fist expression character (except MATCH_BEGIN - already
217 // skipped)
218 while (expr[charpos] >= 0) {
219 charpos++;
220 }
221
222 // The expression charater (MATCH_*)
223 int exprchr = expr[charpos];
224
225 while (true) {
226 // Check if the data in the expression array before the current
227 // expression character matches the data in the input buffer
228 if (matchBegin) {
229 if (!matchArray(expr, exprpos, charpos, buff, buffpos)) {
230 return null;
231 }
232
233 matchBegin = false;
234 } else {
235 offset = indexOfArray(expr, exprpos, charpos, buff, buffpos);
236
237 if (offset < 0) {
238 return null;
239 }
240 }
241
242 // Check for MATCH_BEGIN
243 if (matchBegin) {
244 if (offset != 0) {
245 return null;
246 }
247
248 matchBegin = false;
249 }
250
251 // Advance buffpos
252 buffpos += (charpos - exprpos);
253
254 // Check for END's
255 if (exprchr == MATCH_END) {
256 if (rsltpos > 0) {
257 varsValues = addAndCreateList(varsValues, new String(rslt,
258 0, rsltpos));
259 }
260
261 // Don't care about rest of input buffer
262 varsValues = addElementOnTop(varsValues, data);
263 return varsValues;
264 } else if (exprchr == MATCH_THEEND) {
265 if (rsltpos > 0) {
266 varsValues = addAndCreateList(varsValues, new String(rslt,
267 0, rsltpos));
268 }
269
270 // Check that we reach buffer's end
271 if (buffpos == buff.length) {
272 addElementOnTop(varsValues, data);
273 return varsValues;
274 }
275 return null;
276 }
277
278 // Search the next expression character
279 exprpos = ++charpos;
280
281 while (expr[charpos] >= 0) {
282 charpos++;
283 }
284
285 int prevchr = exprchr;
286
287 exprchr = expr[charpos];
288
289 // We have here prevchr == * or **.
290 offset = (prevchr == MATCH_FILE) ? indexOfArray(expr, exprpos,
291 charpos, buff, buffpos) : lastIndexOfArray(expr, exprpos,
292 charpos, buff, buffpos);
293
294 if (offset < 0) {
295 return null;
296 }
297
298 // Copy the data from the source buffer into the result buffer
299 // to substitute the expression character
300 if (prevchr == MATCH_PATH) {
301 while (buffpos < offset) {
302 rslt[rsltpos++] = buff[buffpos++];
303 }
304 } else {
305 // Matching file, don't copy '/'
306 while (buffpos < offset) {
307 if (buff[buffpos] == '/') {
308 return null;
309 }
310
311 rslt[rsltpos++] = buff[buffpos++];
312 }
313 }
314
315 varsValues = addAndCreateList(varsValues, new String(rslt, 0,
316 rsltpos));
317 rsltpos = 0;
318 }
319 }
320
321 /**
322 * Get the offset of a part of an int array within a char array. <br>
323 * This method return the index in d of the first occurrence after dpos of
324 * that part of array specified by r, starting at rpos and terminating at
325 * rend.
326 *
327 * @param r The array containing the data that need to be matched in d.
328 * @param rpos The index of the first character in r to look for.
329 * @param rend The index of the last character in r to look for plus 1.
330 * @param d The array of char that should contain a part of r.
331 * @param dpos The starting offset in d for the matching.
332 * @return The offset in d of the part of r matched in d or -1 if that was
333 * not found.
334 * @since 2.1.0
335 */
336 protected int indexOfArray(int[] r, int rpos, int rend, char[] d, int dpos) {
337 // Check if pos and len are legal
338 if (rend < rpos) {
339 throw new IllegalArgumentException("rend < rpos");
340 }
341
342 // If we need to match a zero length string return current dpos
343 if (rend == rpos) {
344 return (d.length); // ?? dpos?
345 }
346
347 // If we need to match a 1 char length string do it simply
348 if ((rend - rpos) == 1) {
349 // Search for the specified character
350 for (int x = dpos; x < d.length; x++) {
351 if (r[rpos] == d[x]) {
352 return (x);
353 }
354 }
355 }
356
357 // Main string matching loop. It gets executed if the characters to
358 // match are less then the characters left in the d buffer
359 while (((dpos + rend) - rpos) <= d.length) {
360 // Set current startpoint in d
361 int y = dpos;
362
363 // Check every character in d for equity. If the string is matched
364 // return dpos
365 for (int x = rpos; x <= rend; x++) {
366 if (x == rend) {
367 return (dpos);
368 }
369
370 if (r[x] != d[y++]) {
371 break;
372 }
373 }
374
375 // Increase dpos to search for the same string at next offset
376 dpos++;
377 }
378
379 // The remaining chars in d buffer were not enough or the string
380 // wasn't matched
381 return (-1);
382 }
383
384 /**
385 * Get the offset of a last occurance of an int array within a char array.
386 * <br>
387 * This method return the index in d of the last occurrence after dpos of
388 * that part of array specified by r, starting at rpos and terminating at
389 * rend.
390 *
391 * @param r The array containing the data that need to be matched in d.
392 * @param rpos The index of the first character in r to look for.
393 * @param rend The index of the last character in r to look for plus 1.
394 * @param d The array of char that should contain a part of r.
395 * @param dpos The starting offset in d for the matching.
396 * @return The offset in d of the last part of r matched in d or -1 if that
397 * was not found.
398 * @since 2.1.0
399 */
400 protected int lastIndexOfArray(int[] r, int rpos, int rend, char[] d,
401 int dpos) {
402 // Check if pos and len are legal
403 if (rend < rpos) {
404 throw new IllegalArgumentException("rend < rpos");
405 }
406
407 // If we need to match a zero length string return current dpos
408 if (rend == rpos) {
409 return (d.length); // ?? dpos?
410 }
411
412 // If we need to match a 1 char length string do it simply
413 if ((rend - rpos) == 1) {
414 // Search for the specified character
415 for (int x = d.length - 1; x > dpos; x--) {
416 if (r[rpos] == d[x]) {
417 return (x);
418 }
419 }
420 }
421
422 // Main string matching loop. It gets executed if the characters to
423 // match are less then the characters left in the d buffer
424 int l = d.length - (rend - rpos);
425
426 while (l >= dpos) {
427 // Set current startpoint in d
428 int y = l;
429
430 // Check every character in d for equity. If the string is matched
431 // return dpos
432 for (int x = rpos; x <= rend; x++) {
433 if (x == rend) {
434 return (l);
435 }
436
437 if (r[x] != d[y++]) {
438 break;
439 }
440 }
441
442 // Decrease l to search for the same string at next offset
443 l--;
444 }
445
446 // The remaining chars in d buffer were not enough or the string
447 // wasn't matched
448 return (-1);
449 }
450
451 /**
452 * Matches elements of array r from rpos to rend with array d, starting from
453 * dpos. <br>
454 * This method return true if elements of array r from rpos to rend equals
455 * elements of array d starting from dpos to dpos+(rend-rpos).
456 *
457 * @param r The array containing the data that need to be matched in d.
458 * @param rpos The index of the first character in r to look for.
459 * @param rend The index of the last character in r to look for.
460 * @param d The array of char that should start from a part of r.
461 * @param dpos The starting offset in d for the matching.
462 * @return true if array d starts from portion of array r.
463 * @since 2.1.0
464 */
465 protected boolean matchArray(int[] r, int rpos, int rend, char[] d, int dpos) {
466 if ((d.length - dpos) < (rend - rpos)) {
467 return (false);
468 }
469
470 for (int i = rpos; i < rend; i++) {
471 if (r[i] != d[dpos++]) {
472 return (false);
473 }
474 }
475
476 return (true);
477 }
478
479 /**
480 * <p>
481 * Inserts into a value wildcard-matched strings where specified.
482 * </p>
483 *
484 * @param val The value to convert
485 * @param vars A Map of wildcard-matched strings
486 * @return The new value
487 * @since 2.1.0
488 */
489 public static String convertParam(String val, Map<Integer, String> vars) {
490 if (val == null) {
491 return null;
492 } else if (val.indexOf("{") == -1) {
493 return val;
494 }
495
496 Map.Entry<Integer, String> entry;
497 StringBuffer key = new StringBuffer("{0}");
498 StringBuffer ret = new StringBuffer(val);
499 String keyTmp;
500 int x;
501
502 for (Iterator<Map.Entry<Integer, String>> i = vars.entrySet()
503 .iterator(); i.hasNext();) {
504 entry = i.next();
505 key.setCharAt(1, entry.getKey().toString().charAt(0));
506 keyTmp = key.toString();
507
508 // Replace all instances of the placeholder
509 while ((x = ret.toString().indexOf(keyTmp)) > -1) {
510 ret.replace(x, x + PLACEHOLDER_LENGTH, entry.getValue());
511 }
512 }
513
514 return ret.toString();
515 }
516
517 /**
518 * Adds and object to a list. If the list is null, it creates it.
519 *
520 * @param <T> The type of the element.
521 * @param list The list.
522 * @param data The data to add.
523 * @return The list itself, or a new one if it is <code>null</code>.
524 */
525 private <T> List<T> addAndCreateList(List<T> list, T data) {
526 if (list == null) {
527 list = new ArrayList<T>();
528 }
529 list.add(data);
530 return list;
531 }
532
533 /**
534 * Adds and object on top of a list. If the list is null, it creates it.
535 *
536 * @param <T> The type of the element.
537 * @param list The list.
538 * @param data The data to add.
539 * @return The list itself, or a new one if it is <code>null</code>.
540 */
541 private <T> List<T> addElementOnTop(List<T> list, T data) {
542 if (list == null) {
543 list = new ArrayList<T>();
544 }
545 list.add(0, data);
546 return list;
547 }
548 }