001: /*
002: * $Id: WildcardHelper.java 471754 2006-11-06 14:55:09Z husted $
003: *
004: * Licensed to the Apache Software Foundation (ASF) under one
005: * or more contributor license agreements. See the NOTICE file
006: * distributed with this work for additional information
007: * regarding copyright ownership. The ASF licenses this file
008: * to you under the Apache License, Version 2.0 (the
009: * "License"); you may not use this file except in compliance
010: * with the License. You may obtain a copy of the License at
011: *
012: * http://www.apache.org/licenses/LICENSE-2.0
013: *
014: * Unless required by applicable law or agreed to in writing,
015: * software distributed under the License is distributed on an
016: * "AS IS" BASIS, WITHOUT WARRANTIES OR CONDITIONS OF ANY
017: * KIND, either express or implied. See the License for the
018: * specific language governing permissions and limitations
019: * under the License.
020: */
021: package org.apache.struts.util;
022:
023: import java.util.Map;
024:
025: /**
026: * This class is an utility class that perform wilcard-patterns matching and
027: * isolation taken from Apache Cocoon.
028: *
029: * @version $Rev: 471754 $ $Date: 2005-05-07 12:11:38 -0400 (Sat, 07 May 2005)
030: * $
031: * @since Struts 1.2
032: */
033: public class WildcardHelper {
034: /**
035: * The int representing '*' in the pattern <code>int []</code>.
036: */
037: protected static final int MATCH_FILE = -1;
038:
039: /**
040: * The int representing '**' in the pattern <code>int []</code>.
041: */
042: protected static final int MATCH_PATH = -2;
043:
044: /**
045: * The int representing begin in the pattern <code>int []</code>.
046: */
047: protected static final int MATCH_BEGIN = -4;
048:
049: /**
050: * The int representing end in pattern <code>int []</code>.
051: */
052: protected static final int MATCH_THEEND = -5;
053:
054: /**
055: * The int value that terminates the pattern <code>int []</code>.
056: */
057: protected static final int MATCH_END = -3;
058:
059: /**
060: * <p> Translate the given <code>String</code> into a <code>int []</code>
061: * representing the pattern matchable by this class. <br> This function
062: * translates a <code>String</code> into an int array converting the
063: * special '*' and '\' characters. <br> Here is how the conversion
064: * algorithm works:</p>
065: *
066: * <ul>
067: *
068: * <li>The '*' character is converted to MATCH_FILE, meaning that zero or
069: * more characters (excluding the path separator '/') are to be
070: * matched.</li>
071: *
072: * <li>The '**' sequence is converted to MATCH_PATH, meaning that zero or
073: * more characters (including the path separator '/') are to be
074: * matched.</li>
075: *
076: * <li>The '\' character is used as an escape sequence ('\*' is translated
077: * in '*', not in MATCH_FILE). If an exact '\' character is to be matched
078: * the source string must contain a '\\'. sequence.</li>
079: *
080: * </ul>
081: *
082: * <p>When more than two '*' characters, not separated by another
083: * character, are found their value is considered as '**' (MATCH_PATH).
084: * <br> The array is always terminated by a special value (MATCH_END).
085: * <br> All MATCH* values are less than zero, while normal characters are
086: * equal or greater.</p>
087: *
088: * @param data The string to translate.
089: * @return The encoded string as an int array, terminated by the MATCH_END
090: * value (don't consider the array length).
091: * @throws NullPointerException If data is null.
092: */
093: public int[] compilePattern(String data) {
094: // Prepare the arrays
095: int[] expr = new int[data.length() + 2];
096: char[] buff = data.toCharArray();
097:
098: // Prepare variables for the translation loop
099: 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 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(
170: "No pattern expression provided");
171: }
172:
173: char[] buff = data.toCharArray();
174:
175: // Allocate the result buffer
176: char[] rslt = new char[expr.length + buff.length];
177:
178: // The previous and current position of the expression character
179: // (MATCH_*)
180: int charpos = 0;
181:
182: // The position in the expression, input, translation and result arrays
183: int exprpos = 0;
184: int buffpos = 0;
185: int rsltpos = 0;
186: int offset = -1;
187:
188: // The matching count
189: int mcount = 0;
190:
191: // We want the complete data be in {0}
192: map.put(Integer.toString(mcount), data);
193:
194: // First check for MATCH_BEGIN
195: boolean matchBegin = false;
196:
197: if (expr[charpos] == MATCH_BEGIN) {
198: matchBegin = true;
199: exprpos = ++charpos;
200: }
201:
202: // Search the fist expression character (except MATCH_BEGIN - already
203: // skipped)
204: while (expr[charpos] >= 0) {
205: charpos++;
206: }
207:
208: // The expression charater (MATCH_*)
209: int exprchr = expr[charpos];
210:
211: while (true) {
212: // Check if the data in the expression array before the current
213: // expression character matches the data in the input buffer
214: if (matchBegin) {
215: if (!matchArray(expr, exprpos, charpos, buff, buffpos)) {
216: return (false);
217: }
218:
219: matchBegin = false;
220: } else {
221: offset = indexOfArray(expr, exprpos, charpos, buff,
222: buffpos);
223:
224: if (offset < 0) {
225: return (false);
226: }
227: }
228:
229: // Check for MATCH_BEGIN
230: if (matchBegin) {
231: if (offset != 0) {
232: return (false);
233: }
234:
235: matchBegin = false;
236: }
237:
238: // Advance buffpos
239: buffpos += (charpos - exprpos);
240:
241: // Check for END's
242: if (exprchr == MATCH_END) {
243: if (rsltpos > 0) {
244: map.put(Integer.toString(++mcount), new String(
245: rslt, 0, rsltpos));
246: }
247:
248: // Don't care about rest of input buffer
249: return (true);
250: } else if (exprchr == MATCH_THEEND) {
251: if (rsltpos > 0) {
252: map.put(Integer.toString(++mcount), new String(
253: rslt, 0, rsltpos));
254: }
255:
256: // Check that we reach buffer's end
257: return (buffpos == buff.length);
258: }
259:
260: // Search the next expression character
261: exprpos = ++charpos;
262:
263: while (expr[charpos] >= 0) {
264: charpos++;
265: }
266:
267: int prevchr = exprchr;
268:
269: exprchr = expr[charpos];
270:
271: // We have here prevchr == * or **.
272: offset = (prevchr == MATCH_FILE) ? indexOfArray(expr,
273: exprpos, charpos, buff, buffpos)
274: : lastIndexOfArray(expr, exprpos, charpos, buff,
275: buffpos);
276:
277: if (offset < 0) {
278: return (false);
279: }
280:
281: // Copy the data from the source buffer into the result buffer
282: // to substitute the expression character
283: if (prevchr == MATCH_PATH) {
284: while (buffpos < offset) {
285: rslt[rsltpos++] = buff[buffpos++];
286: }
287: } else {
288: // Matching file, don't copy '/'
289: while (buffpos < offset) {
290: if (buff[buffpos] == '/') {
291: return (false);
292: }
293:
294: rslt[rsltpos++] = buff[buffpos++];
295: }
296: }
297:
298: map.put(Integer.toString(++mcount), new String(rslt, 0,
299: rsltpos));
300: rsltpos = 0;
301: }
302: }
303:
304: /**
305: * Get the offset of a part of an int array within a char array. <br> This
306: * method return the index in d of the first occurrence after dpos of that
307: * part of array specified by r, starting at rpos and terminating at
308: * rend.
309: *
310: * @param r The array containing the data that need to be matched in
311: * d.
312: * @param rpos The index of the first character in r to look for.
313: * @param rend The index of the last character in r to look for plus 1.
314: * @param d The array of char that should contain a part of r.
315: * @param dpos The starting offset in d for the matching.
316: * @return The offset in d of the part of r matched in d or -1 if that was
317: * not found.
318: */
319: protected int indexOfArray(int[] r, int rpos, int rend, char[] d,
320: int dpos) {
321: // Check if pos and len are legal
322: if (rend < rpos) {
323: throw new IllegalArgumentException("rend < rpos");
324: }
325:
326: // If we need to match a zero length string return current dpos
327: if (rend == rpos) {
328: return (d.length); //?? dpos?
329: }
330:
331: // If we need to match a 1 char length string do it simply
332: if ((rend - rpos) == 1) {
333: // Search for the specified character
334: for (int x = dpos; x < d.length; x++) {
335: if (r[rpos] == d[x]) {
336: return (x);
337: }
338: }
339: }
340:
341: // Main string matching loop. It gets executed if the characters to
342: // match are less then the characters left in the d buffer
343: while (((dpos + rend) - rpos) <= d.length) {
344: // Set current startpoint in d
345: int y = dpos;
346:
347: // Check every character in d for equity. If the string is matched
348: // return dpos
349: for (int x = rpos; x <= rend; x++) {
350: if (x == rend) {
351: return (dpos);
352: }
353:
354: if (r[x] != d[y++]) {
355: break;
356: }
357: }
358:
359: // Increase dpos to search for the same string at next offset
360: dpos++;
361: }
362:
363: // The remaining chars in d buffer were not enough or the string
364: // wasn't matched
365: return (-1);
366: }
367:
368: /**
369: * Get the offset of a last occurance of an int array within a char array.
370: * <br> This method return the index in d of the last occurrence after
371: * dpos of that part of array specified by r, starting at rpos and
372: * terminating at rend.
373: *
374: * @param r The array containing the data that need to be matched in
375: * d.
376: * @param rpos The index of the first character in r to look for.
377: * @param rend The index of the last character in r to look for plus 1.
378: * @param d The array of char that should contain a part of r.
379: * @param dpos The starting offset in d for the matching.
380: * @return The offset in d of the last part of r matched in d or -1 if
381: * that was not found.
382: */
383: protected int lastIndexOfArray(int[] r, int rpos, int rend,
384: char[] d, int dpos) {
385: // Check if pos and len are legal
386: if (rend < rpos) {
387: throw new IllegalArgumentException("rend < rpos");
388: }
389:
390: // If we need to match a zero length string return current dpos
391: if (rend == rpos) {
392: return (d.length); //?? dpos?
393: }
394:
395: // If we need to match a 1 char length string do it simply
396: if ((rend - rpos) == 1) {
397: // Search for the specified character
398: for (int x = d.length - 1; x > dpos; x--) {
399: if (r[rpos] == d[x]) {
400: return (x);
401: }
402: }
403: }
404:
405: // Main string matching loop. It gets executed if the characters to
406: // match are less then the characters left in the d buffer
407: int l = d.length - (rend - rpos);
408:
409: while (l >= dpos) {
410: // Set current startpoint in d
411: int y = l;
412:
413: // Check every character in d for equity. If the string is matched
414: // return dpos
415: for (int x = rpos; x <= rend; x++) {
416: if (x == rend) {
417: return (l);
418: }
419:
420: if (r[x] != d[y++]) {
421: break;
422: }
423: }
424:
425: // Decrease l to search for the same string at next offset
426: l--;
427: }
428:
429: // The remaining chars in d buffer were not enough or the string
430: // wasn't matched
431: return (-1);
432: }
433:
434: /**
435: * Matches elements of array r from rpos to rend with array d, starting
436: * from dpos. <br> This method return true if elements of array r from
437: * rpos to rend equals elements of array d starting from dpos to
438: * dpos+(rend-rpos).
439: *
440: * @param r The array containing the data that need to be matched in
441: * d.
442: * @param rpos The index of the first character in r to look for.
443: * @param rend The index of the last character in r to look for.
444: * @param d The array of char that should start from a part of r.
445: * @param dpos The starting offset in d for the matching.
446: * @return true if array d starts from portion of array r.
447: */
448: protected boolean matchArray(int[] r, int rpos, int rend, char[] d,
449: int dpos) {
450: if ((d.length - dpos) < (rend - rpos)) {
451: return (false);
452: }
453:
454: for (int i = rpos; i < rend; i++) {
455: if (r[i] != d[dpos++]) {
456: return (false);
457: }
458: }
459:
460: return (true);
461: }
462: }
|