1/*2 * $Id: WildcardHelper.java 795343 2009-07-18 11:26:09Z apetrelli $3 *4 * Licensed to the Apache Software Foundation (ASF) under one5 * or more contributor license agreements. See the NOTICE file6 * distributed with this work for additional information7 * regarding copyright ownership. The ASF licenses this file8 * to you under the Apache License, Version 2.0 (the9 * "License"); you may not use this file except in compliance10 * with the License. You may obtain a copy of the License at11 *12 * http://www.apache.org/licenses/LICENSE-2.013 *14 * Unless required by applicable law or agreed to in writing,15 * software distributed under the License is distributed on an16 * "AS IS" BASIS, WITHOUT WARRANTIES OR CONDITIONS OF ANY17 * KIND, either express or implied. See the License for the18 * specific language governing permissions and limitations19 * under the License.20 */21package org.apache.tiles.util;
2223import java.util.ArrayList;
24import java.util.Iterator;
25import java.util.List;
26import java.util.Map;
2728/***29 * This class is an utility class that perform wilcard-patterns matching and30 * isolation taken from Apache Struts that is taken, in turn, from Apache31 * Struts.32 *33 * @version $Rev: 795343 $ $Date: 2009-07-18 13:26:09 +0200 (sab, 18 lug 2009) $34 * @since 2.1.035 */36publicclassWildcardHelper {
37/***38 * The int representing '*' in the pattern <code>int []</code>.39 *40 * @since 2.1.041 */42protectedstaticfinalint MATCH_FILE = -1;
4344/***45 * The int representing '**' in the pattern <code>int []</code>.46 *47 * @since 2.1.048 */49protectedstaticfinalint MATCH_PATH = -2;
5051/***52 * The int representing begin in the pattern <code>int []</code>.53 *54 * @since 2.1.055 */56protectedstaticfinalint MATCH_BEGIN = -4;
5758/***59 * The int representing end in pattern <code>int []</code>.60 *61 * @since 2.1.062 */63protectedstaticfinalint MATCH_THEEND = -5;
6465/***66 * The int value that terminates the pattern <code>int []</code>.67 *68 * @since 2.1.069 */70protectedstaticfinalint MATCH_END = -3;
7172/***73 * The length of the placeholder.74 *75 * @since 2.1.076 */77privatestaticfinalint PLACEHOLDER_LENGTH = 3;
7879/***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 array84 * 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 or91 * more characters (excluding the path separator '/') are to be matched.</li>92 *93 * <li>The '**' sequence is converted to MATCH_PATH, meaning that zero or94 * more characters (including the path separator '/') are to be matched.</li>95 *96 * <li>The '\' character is used as an escape sequence ('\*' is translated97 * in '*', not in MATCH_FILE). If an exact '\' character is to be matched98 * 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 equal107 * 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_END112 * value (don't consider the array length).113 * @throws NullPointerException If data is null.114 * @since 2.1.0115 */116publicint[] compilePattern(String data) {
117// Prepare the arrays118int[] expr = newint[data.length() + 2];
119char[] buff = data.toCharArray();
120121// Prepare variables for the translation loop122int y = 0;
123boolean slash = false;
124125// Must start from beginning126 expr[y++] = MATCH_BEGIN;
127128if (buff.length > 0) {
129if (buff[0] == '//') {
130 slash = true;
131 } elseif (buff[0] == '*') {
132 expr[y++] = MATCH_FILE;
133 } else {
134 expr[y++] = buff[0];
135 }
136137// Main translation loop138for (int x = 1; x < buff.length; x++) {
139// If the previous char was '\' simply copy this char.140if (slash) {
141 expr[y++] = buff[x];
142 slash = false;
143144// If the previous char was not '\' we have to do a bunch of145// checks146 } else {
147// If this char is '\' declare that and continue148if (buff[x] == '//') {
149 slash = true;
150151// If this char is '*' check the previous one152 } elseif (buff[x] == '*') {
153// If the previous character als was '*' match a path154if (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 }
165166// Must match end at the end167 expr[y] = MATCH_THEEND;
168169return expr;
170 }
171172/***173 * Match a pattern agains a string and isolates wildcard replacement into a174 * <code>Stack</code>.175 *176 * @param map The map to store matched values177 * @param data The string to match178 * @param expr The compiled wildcard expression179 * @return True if a match180 * @throws NullPointerException If any parameters are null181 * @since 2.1.0182 * @deprecated Use {@link #match(List, String, int[])}.183 */184publicboolean match(Map<Integer, String> map, String data, int[] expr) {
185if (map == null) {
186thrownew NullPointerException("No map provided");
187 }
188 List<String> varsValues = match(data, expr);
189int i = 0;
190for (String value : varsValues) {
191 map.put(i, value);
192 i++;
193 }
194return varsValues != null;
195 }
196197/***198 * Match a pattern agains a string and isolates wildcard replacement into a199 * <code>Stack</code>.200 *201 * @param data The string to match202 * @param expr The compiled wildcard expression203 * @return The list of matched variables, or <code>null</code> if it does not match.204 * @throws NullPointerException If any parameters are null205 * @since 2.2.0206 */207public List<String> match(String data, int[] expr) {
208 List<String> varsValues = null;
209210if (data == null) {
211thrownew NullPointerException("No data provided");
212 }
213214if (expr == null) {
215thrownew NullPointerException("No pattern expression provided");
216 }
217218char[] buff = data.toCharArray();
219220// Allocate the result buffer221char[] rslt = newchar[expr.length + buff.length];
222223// The previous and current position of the expression character224// (MATCH_*)225int charpos = 0;
226227// The position in the expression, input, translation and result arrays228int exprpos = 0;
229int buffpos = 0;
230int rsltpos = 0;
231int offset = -1;
232233// First check for MATCH_BEGIN234boolean matchBegin = false;
235236if (expr[charpos] == MATCH_BEGIN) {
237 matchBegin = true;
238 exprpos = ++charpos;
239 }
240241// Search the fist expression character (except MATCH_BEGIN - already242// skipped)243while (expr[charpos] >= 0) {
244 charpos++;
245 }
246247// The expression charater (MATCH_*)248int exprchr = expr[charpos];
249250while (true) {
251// Check if the data in the expression array before the current252// expression character matches the data in the input buffer253if (matchBegin) {
254if (!matchArray(expr, exprpos, charpos, buff, buffpos)) {
255returnnull;
256 }
257258 matchBegin = false;
259 } else {
260 offset = indexOfArray(expr, exprpos, charpos, buff, buffpos);
261262if (offset < 0) {
263returnnull;
264 }
265 }
266267// Check for MATCH_BEGIN268if (matchBegin) {
269if (offset != 0) {
270returnnull;
271 }
272273 matchBegin = false;
274 }
275276// Advance buffpos277 buffpos += (charpos - exprpos);
278279// Check for END's280if (exprchr == MATCH_END) {
281if (rsltpos > 0) {
282 varsValues = addAndCreateList(varsValues, new String(rslt,
283 0, rsltpos));
284 }
285286// Don't care about rest of input buffer287 varsValues = addElementOnTop(varsValues, data);
288return varsValues;
289 } elseif (exprchr == MATCH_THEEND) {
290if (rsltpos > 0) {
291 varsValues = addAndCreateList(varsValues, new String(rslt,
292 0, rsltpos));
293 }
294295// Check that we reach buffer's end296if (buffpos == buff.length) {
297 addElementOnTop(varsValues, data);
298return varsValues;
299 }
300returnnull;
301 }
302303// Search the next expression character304 exprpos = ++charpos;
305306while (expr[charpos] >= 0) {
307 charpos++;
308 }
309310int prevchr = exprchr;
311312 exprchr = expr[charpos];
313314// We have here prevchr == * or **.315 offset = (prevchr == MATCH_FILE) ? indexOfArray(expr, exprpos,
316 charpos, buff, buffpos) : lastIndexOfArray(expr, exprpos,
317 charpos, buff, buffpos);
318319if (offset < 0) {
320returnnull;
321 }
322323// Copy the data from the source buffer into the result buffer324// to substitute the expression character325if (prevchr == MATCH_PATH) {
326while (buffpos < offset) {
327 rslt[rsltpos++] = buff[buffpos++];
328 }
329 } else {
330// Matching file, don't copy '/'331while (buffpos < offset) {
332if (buff[buffpos] == '/') {
333returnnull;
334 }
335336 rslt[rsltpos++] = buff[buffpos++];
337 }
338 }
339340 varsValues = addAndCreateList(varsValues, new String(rslt, 0,
341 rsltpos));
342 rsltpos = 0;
343 }
344 }
345346/***347 * Get the offset of a part of an int array within a char array. <br>348 * This method return the index in d of the first occurrence after dpos of349 * that part of array specified by r, starting at rpos and terminating at350 * rend.351 *352 * @param r The array containing the data that need to be matched in d.353 * @param rpos The index of the first character in r to look for.354 * @param rend The index of the last character in r to look for plus 1.355 * @param d The array of char that should contain a part of r.356 * @param dpos The starting offset in d for the matching.357 * @return The offset in d of the part of r matched in d or -1 if that was358 * not found.359 * @since 2.1.0360 */361protectedint indexOfArray(int[] r, int rpos, int rend, char[] d, int dpos) {
362// Check if pos and len are legal363if (rend < rpos) {
364thrownew IllegalArgumentException("rend < rpos");
365 }
366367// If we need to match a zero length string return current dpos368if (rend == rpos) {
369return (d.length); // ?? dpos?370 }
371372// If we need to match a 1 char length string do it simply373if ((rend - rpos) == 1) {
374// Search for the specified character375for (int x = dpos; x < d.length; x++) {
376if (r[rpos] == d[x]) {
377return (x);
378 }
379 }
380 }
381382// Main string matching loop. It gets executed if the characters to383// match are less then the characters left in the d buffer384while (((dpos + rend) - rpos) <= d.length) {
385// Set current startpoint in d386int y = dpos;
387388// Check every character in d for equity. If the string is matched389// return dpos390for (int x = rpos; x <= rend; x++) {
391if (x == rend) {
392return (dpos);
393 }
394395if (r[x] != d[y++]) {
396break;
397 }
398 }
399400// Increase dpos to search for the same string at next offset401 dpos++;
402 }
403404// The remaining chars in d buffer were not enough or the string405// wasn't matched406return (-1);
407 }
408409/***410 * Get the offset of a last occurance of an int array within a char array.411 * <br>412 * This method return the index in d of the last occurrence after dpos of413 * that part of array specified by r, starting at rpos and terminating at414 * rend.415 *416 * @param r The array containing the data that need to be matched in d.417 * @param rpos The index of the first character in r to look for.418 * @param rend The index of the last character in r to look for plus 1.419 * @param d The array of char that should contain a part of r.420 * @param dpos The starting offset in d for the matching.421 * @return The offset in d of the last part of r matched in d or -1 if that422 * was not found.423 * @since 2.1.0424 */425protectedint lastIndexOfArray(int[] r, int rpos, int rend, char[] d,
426int dpos) {
427// Check if pos and len are legal428if (rend < rpos) {
429thrownew IllegalArgumentException("rend < rpos");
430 }
431432// If we need to match a zero length string return current dpos433if (rend == rpos) {
434return (d.length); // ?? dpos?435 }
436437// If we need to match a 1 char length string do it simply438if ((rend - rpos) == 1) {
439// Search for the specified character440for (int x = d.length - 1; x > dpos; x--) {
441if (r[rpos] == d[x]) {
442return (x);
443 }
444 }
445 }
446447// Main string matching loop. It gets executed if the characters to448// match are less then the characters left in the d buffer449int l = d.length - (rend - rpos);
450451while (l >= dpos) {
452// Set current startpoint in d453int y = l;
454455// Check every character in d for equity. If the string is matched456// return dpos457for (int x = rpos; x <= rend; x++) {
458if (x == rend) {
459return (l);
460 }
461462if (r[x] != d[y++]) {
463break;
464 }
465 }
466467// Decrease l to search for the same string at next offset468 l--;
469 }
470471// The remaining chars in d buffer were not enough or the string472// wasn't matched473return (-1);
474 }
475476/***477 * Matches elements of array r from rpos to rend with array d, starting from478 * dpos. <br>479 * This method return true if elements of array r from rpos to rend equals480 * elements of array d starting from dpos to dpos+(rend-rpos).481 *482 * @param r The array containing the data that need to be matched in d.483 * @param rpos The index of the first character in r to look for.484 * @param rend The index of the last character in r to look for.485 * @param d The array of char that should start from a part of r.486 * @param dpos The starting offset in d for the matching.487 * @return true if array d starts from portion of array r.488 * @since 2.1.0489 */490protectedboolean matchArray(int[] r, int rpos, int rend, char[] d, int dpos) {
491if ((d.length - dpos) < (rend - rpos)) {
492return (false);
493 }
494495for (int i = rpos; i < rend; i++) {
496if (r[i] != d[dpos++]) {
497return (false);
498 }
499 }
500501return (true);
502 }
503504/***505 * <p>506 * Inserts into a value wildcard-matched strings where specified.507 * </p>508 *509 * @param val The value to convert510 * @param vars A Map of wildcard-matched strings511 * @return The new value512 * @since 2.1.0513 */514publicstatic String convertParam(String val, Map<Integer, String> vars) {
515if (val == null) {
516returnnull;
517 } elseif (val.indexOf("{") == -1) {
518return val;
519 }
520521 Map.Entry<Integer, String> entry;
522 StringBuffer key = new StringBuffer("{0}");
523 StringBuffer ret = new StringBuffer(val);
524 String keyTmp;
525int x;
526527for (Iterator<Map.Entry<Integer, String>> i = vars.entrySet()
528 .iterator(); i.hasNext();) {
529 entry = i.next();
530 key.setCharAt(1, entry.getKey().toString().charAt(0));
531 keyTmp = key.toString();
532533// Replace all instances of the placeholder534while ((x = ret.toString().indexOf(keyTmp)) > -1) {
535 ret.replace(x, x + PLACEHOLDER_LENGTH, entry.getValue());
536 }
537 }
538539return ret.toString();
540 }
541542/***543 * Adds and object to a list. If the list is null, it creates it.544 *545 * @param <T> The type of the element.546 * @param list The list.547 * @param data The data to add.548 * @return The list itself, or a new one if it is <code>null</code>.549 */550private <T> List<T> addAndCreateList(List<T> list, T data) {
551if (list == null) {
552 list = new ArrayList<T>();
553 }
554 list.add(data);
555return list;
556 }
557558/***559 * Adds and object on top of a list. If the list is null, it creates it.560 *561 * @param <T> The type of the element.562 * @param list The list.563 * @param data The data to add.564 * @return The list itself, or a new one if it is <code>null</code>.565 */566private <T> List<T> addElementOnTop(List<T> list, T data) {
567if (list == null) {
568 list = new ArrayList<T>();
569 }
570 list.add(0, data);
571return list;
572 }
573 }