View Javadoc

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 }