UriPatternHelper


1   /*
2    * Copyright 1999-2004 The Apache Software Foundation.
3    *
4    * Licensed under the Apache License, Version 2.0 (the "License");
5    * you may not use this file except in compliance with the License.
6    * You may obtain a copy of the License at
7    *
8    *      http://www.apache.org/licenses/LICENSE-2.0
9    *
10   * Unless required by applicable law or agreed to in writing, software
11   * distributed under the License is distributed on an "AS IS" BASIS,
12   * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
13   * See the License for the specific language governing permissions and
14   * limitations under the License.
15   */
16  package org.sapia.regis.loader;
17  
18  import java.util.Map  ;
19  
20  /**
21   * 
22   * NOTE: THE SOURCE FROM THIS CLASS HAS BEEN COPIED FROM APACHE COCOON'S
23   * org.apache.cocoon.matching.helpers.WildcardHelper CLASS. THIS ALLOWS NOT
24   * HAVING DEPENCIES ON COCOON AT COMPILE-TIME/RUNTIME, IF COCOON IS NOT USED.
25   * <p>
26   * This class is an utility class that perform wilcard-patterns matching and
27   * isolation.
28   * 
29   * @author <a HREF="mailto:pier@apache.org">Pierpaolo Fumagalli </a> (Apache
30   *         Software Foundation)
31   * @author <a HREF="mailto:Giacomo.Pati@pwr.ch">Giacomo Pati </a>
32   * @author <a HREF="mailto:stefano@apache.org">Stefano Mazzocchi </a>
33   * @author <a HREF="mailto:bloritsch@apache.org">Berin Loritsch </a>
34   */
35  public class UriPatternHelper {
36  
37    /** The int representing '*' in the pattern <code>int []</code>. */
38    protected static final int MATCH_FILE   = -1;
39    /** The int representing '**' in the pattern <code>int []</code>. */
40    protected static final int MATCH_PATH   = -2;
41    /** The int representing begin in the pattern <code>int []</code>. */
42    protected static final int MATCH_BEGIN  = -4;
43    /** The int representing end in pattern <code>int []</code>. */
44    protected static final int MATCH_THEEND = -5;
45    /** The int value that terminates the pattern <code>int []</code>. */
46    protected static final int MATCH_END    = -3;
47  
48    /**
49     * Translate the given <code>String</code> into a <code>int []</code>
50     * representing the pattern matchable by this class. <br>
51     * This function translates a <code>String</code> into an int array
52     * converting the special '*' and '\' characters. <br>
53     * Here is how the conversion algorithm works:
54     * <ul>
55     * <li>The '*' character is converted to MATCH_FILE, meaning that zero or
56     * more characters (excluding the path separator '/') are to be matched.</li>
57     * <li>The '**' sequence is converted to MATCH_PATH, meaning that zero or
58     * more characters (including the path separator '/') are to be matched.</li>
59     * <li>The '\' character is used as an escape sequence ('\*' is translated in
60     * '*', not in MATCH_FILE). If an exact '\' character is to be matched the
61     * source string must contain a '\\'. sequence.</li>
62     * </ul>
63     * When more than two '*' characters, not separated by another character, are
64     * found their value is considered as '**' (MATCH_PATH). <br>
65     * The array is always terminated by a special value (MATCH_END). <br>
66     * All MATCH* values are less than zero, while normal characters are equal or
67     * greater.
68     * 
69     * @param data
70     *          The string to translate.
71     * @return The encoded string as an int array, terminated by the MATCH_END
72     *         value (don't consider the array length).
73     * @exception NullPointerException
74     *              If data is null.
75     */
76    static int[] compilePattern(String   data) throws NullPointerException   {
77  
78      // Prepare the arrays
79      int expr[] = new int[data.length() + 2];
80      char buff[] = data.toCharArray();
81  
82      // Prepare variables for the translation loop
83      int y = 0;
84      boolean slash = false;
85  
86      // Must start from beginning
87      expr[y++] = MATCH_BEGIN;
88  
89      if(buff.length > 0) {
90        if(buff[0] == '\\') {
91          slash = true;
92        } else if(buff[0] == '*') {
93          expr[y++] = MATCH_FILE;
94        } else {
95          expr[y++] = buff[0];
96        }
97  
98        // Main translation loop
99        for(int x = 1; x < buff.length; x++) {
100         // If the previous char was '\' simply copy this char.
101         if(slash) {
102           expr[y++] = buff[x];
103           slash = false;
104           // If the previous char was not '\' we have to do a bunch of checks
105         } else {
106           // If this char is '\' declare that and continue
107           if(buff[x] == '\\') {
108             slash = true;
109             // If this char is '*' check the previous one
110           } else if(buff[x] == '*') {
111             // If the previous character als was '*' match a path
112             if(expr[y - 1] <= MATCH_FILE) {
113               expr[y - 1] = MATCH_PATH;
114             } else {
115               expr[y++] = MATCH_FILE;
116             }
117           } else {
118             expr[y++] = buff[x];
119           }
120         }
121       }
122     }
123 
124     // Must match end at the end
125     expr[y] = MATCH_THEEND;
126     return expr;
127   }
128 
129   /**
130    * match a pattern agains a string and isolates wildcard replacement into a
131    * <code>Stack</code>.
132    */
133   static boolean match(Map   map, String   data, int[] expr)
134       throws NullPointerException   {
135     if(map == null)
136       throw new NullPointerException  ("No map provided");
137     if(data == null)
138       throw new NullPointerException  ("No data provided");
139     if(expr == null)
140       throw new NullPointerException  ("No pattern expression provided");
141 
142     char buff[] = data.toCharArray();
143     // Allocate the result buffer
144     char rslt[] = new char[expr.length + buff.length];
145 
146     // The previous and current position of the expression character
147     // (MATCH_*)
148     int charpos = 0;
149 
150     // The position in the expression, input, translation and result arrays
151     int exprpos = 0;
152     int buffpos = 0;
153     int rsltpos = 0;
154     int offset = -1;
155 
156     // The matching count
157     int mcount = 0;
158 
159     // We want the complete data be in {0}
160     map.put(Integer.toString(mcount), data);
161 
162     // First check for MATCH_BEGIN
163     boolean matchBegin = false;
164     if(expr[charpos] == MATCH_BEGIN) {
165       matchBegin = true;
166       exprpos = ++charpos;
167     }
168 
169     // Search the fist expression character (except MATCH_BEGIN - already
170     // skipped)
171     while(expr[charpos] >= 0)
172       charpos++;
173 
174     // The expression charater (MATCH_*)
175     int exprchr = expr[charpos];
176 
177     while(true) {
178       // Check if the data in the expression array before the current
179       // expression character matches the data in the input buffer
180       if(matchBegin) {
181         if(!matchArray(expr, exprpos, charpos, buff, buffpos))
182           return (false);
183         matchBegin = false;
184       } else {
185         offset = indexOfArray(expr, exprpos, charpos, buff, buffpos);
186         if(offset < 0)
187           return (false);
188       }
189 
190       // Check for MATCH_BEGIN
191       if(matchBegin) {
192         if(offset != 0)
193           return (false);
194         matchBegin = false;
195       }
196 
197       // Advance buffpos
198       buffpos += (charpos - exprpos);
199 
200       // Check for END's
201       if(exprchr == MATCH_END) {
202         if(rsltpos > 0)
203           map.put(Integer.toString(++mcount), new String  (rslt, 0, rsltpos));
204         // Don't care about rest of input buffer
205         return (true);
206       } else if(exprchr == MATCH_THEEND) {
207         if(rsltpos > 0)
208           map.put(Integer.toString(++mcount), new String  (rslt, 0, rsltpos));
209         // Check that we reach buffer's end
210         return (buffpos == buff.length);
211       }
212 
213       // Search the next expression character
214       exprpos = ++charpos;
215       while(expr[charpos] >= 0)
216         charpos++;
217       int prevchr = exprchr;
218       exprchr = expr[charpos];
219 
220       // We have here prevchr == * or **.
221       offset = (prevchr == MATCH_FILE) ? indexOfArray(expr, exprpos, charpos,
222           buff, buffpos) : lastIndexOfArray(expr, exprpos, charpos, buff,
223           buffpos);
224 
225       if(offset < 0)
226         return (false);
227 
228       // Copy the data from the source buffer into the result buffer
229       // to substitute the expression character
230       if(prevchr == MATCH_PATH) {
231         while(buffpos < offset)
232           rslt[rsltpos++] = buff[buffpos++];
233       } else {
234         // Matching file, don't copy '/'
235         while(buffpos < offset) {
236           if(buff[buffpos] == '/')
237             return (false);
238           rslt[rsltpos++] = buff[buffpos++];
239         }
240       }
241 
242       map.put(Integer.toString(++mcount), new String  (rslt, 0, rsltpos));
243       rsltpos = 0;
244     }
245   }
246 
247   /**
248    * Get the offset of a part of an int array within a char array. <br>
249    * This method return the index in d of the first occurrence after dpos of
250    * that part of array specified by r, starting at rpos and terminating at
251    * rend.
252    * 
253    * @param r
254    *          The array containing the data that need to be matched in d.
255    * @param rpos
256    *          The index of the first character in r to look for.
257    * @param rend
258    *          The index of the last character in r to look for plus 1.
259    * @param d
260    *          The array of char that should contain a part of r.
261    * @param dpos
262    *          The starting offset in d for the matching.
263    * @return The offset in d of the part of r matched in d or -1 if that was not
264    *         found.
265    */
266   protected static int indexOfArray(int r[], int rpos, int rend, char d[],
267       int dpos) {
268     // Check if pos and len are legal
269     if(rend < rpos)
270       throw new IllegalArgumentException  ("rend < rpos");
271     // If we need to match a zero length string return current dpos
272     if(rend == rpos)
273       return (d.length); //?? dpos?
274     // If we need to match a 1 char length string do it simply
275     if((rend - rpos) == 1) {
276       // Search for the specified character
277       for(int x = dpos; x < d.length; x++)
278         if(r[rpos] == d[x])
279           return (x);
280     }
281     // Main string matching loop. It gets executed if the characters to
282     // match are less then the characters left in the d buffer
283     while((dpos + rend - rpos) <= d.length) {
284       // Set current startpoint in d
285       int y = dpos;
286       // Check every character in d for equity. If the string is matched
287       // return dpos
288       for(int x = rpos; x <= rend; x++) {
289         if(x == rend)
290           return (dpos);
291         if(r[x] != d[y++])
292           break;
293       }
294       // Increase dpos to search for the same string at next offset
295       dpos++;
296     }
297     // The remaining chars in d buffer were not enough or the string
298     // wasn't matched
299     return (-1);
300   }
301 
302   /**
303    * Get the offset of a last occurance of an int array within a char array.
304    * <br>
305    * This method return the index in d of the last occurrence after dpos of that
306    * part of array specified by r, starting at rpos and terminating at rend.
307    * 
308    * @param r
309    *          The array containing the data that need to be matched in d.
310    * @param rpos
311    *          The index of the first character in r to look for.
312    * @param rend
313    *          The index of the last character in r to look for plus 1.
314    * @param d
315    *          The array of char that should contain a part of r.
316    * @param dpos
317    *          The starting offset in d for the matching.
318    * @return The offset in d of the last part of r matched in d or -1 if that
319    *         was not found.
320    */
321   protected static int lastIndexOfArray(int r[], int rpos, int rend, char d[],
322       int dpos) {
323     // Check if pos and len are legal
324     if(rend < rpos)
325       throw new IllegalArgumentException  ("rend < rpos");
326     // If we need to match a zero length string return current dpos
327     if(rend == rpos)
328       return (d.length); //?? dpos?
329 
330     // If we need to match a 1 char length string do it simply
331     if((rend - rpos) == 1) {
332       // Search for the specified character
333       for(int x = d.length - 1; x > dpos; x--)
334         if(r[rpos] == d[x])
335           return (x);
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     int l = d.length - (rend - rpos);
341     while(l >= dpos) {
342       // Set current startpoint in d
343       int y = l;
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 (l);
349         if(r[x] != d[y++])
350           break;
351       }
352       // Decrease l to search for the same string at next offset
353       l--;
354     }
355     // The remaining chars in d buffer were not enough or the string
356     // wasn't matched
357     return (-1);
358   }
359 
360   /**
361    * Matches elements of array r from rpos to rend with array d, starting from
362    * dpos. <br>
363    * This method return true if elements of array r from rpos to rend equals
364    * elements of array d starting from dpos to dpos+(rend-rpos).
365    * 
366    * @param r
367    *          The array containing the data that need to be matched in d.
368    * @param rpos
369    *          The index of the first character in r to look for.
370    * @param d
371    *          The array of char that should start from a part of r.
372    * @param dpos
373    *          The starting offset in d for the matching.
374    * @return true if array d starts from portion of array r.
375    */
376   protected static boolean matchArray(int r[], int rpos, int rend, char d[],
377       int dpos) {
378     if(d.length - dpos < rend - rpos)
379       return (false);
380     for(int i = rpos; i < rend; i++)
381       if(r[i] != d[dpos++])
382         return (false);
383     return (true);
384   }
385 
386 }
387
A to Z: JavaDoc & Examples Daily Java News & Articles Open Source Projects Open Source Codes Free Computer Books Remove Frame
Popular Tags