View Javadoc

1   package com.atlassian.seraph.util;
2   
3   import edu.emory.mathcs.backport.java.util.concurrent.locks.ReadWriteLock;
4   import edu.emory.mathcs.backport.java.util.concurrent.locks.ReentrantReadWriteLock;
5   
6   import java.io.Serializable;
7   import java.util.ArrayList;
8   import java.util.Collection;
9   import java.util.Collections;
10  import java.util.HashMap;
11  import java.util.Iterator;
12  import java.util.List;
13  import java.util.Map;
14  
15  /**
16   * @author <a href="mailto:joe@truemesh.com">Joe Walnes</a>
17   * @author <a href="mailto:mike@atlassian.com">Mike Cannon-Brookes</a>
18   * @author <a href="mailto:hani@formicary.net">Hani Suleiman</a>
19   */
20  public class PathMapper implements Serializable, IPathMapper
21  {
22      private static final String[] DEFAULT_KEYS = { "/", "*", "/*" };
23  
24      private final Map mappings = new HashMap();
25      private final List complexPaths = new ArrayList();
26  
27      private final KeyMatcher matcher = new KeyMatcher();
28  
29      // common use of this class is reentrant read-mostly (quite expensive calls too)
30      // we don't want these reads to block each other so use a RWLock
31      private final ReadWriteLock lock = new ReentrantReadWriteLock();
32  
33      public void put(final String key, final String pattern)
34      {
35          lock.writeLock().lock();
36          try
37          {
38              if (pattern == null)
39              {
40                  removeMappingsForKey(key);
41                  return;
42              }
43              mappings.put(pattern, key);
44              if ((pattern.indexOf('?') > -1) || ((pattern.indexOf("*") > -1) && (pattern.length() > 1)))
45              {
46                  complexPaths.add(pattern);
47              }
48          }
49          finally
50          {
51              lock.writeLock().unlock();
52          }
53      }
54  
55      // must be called under lock
56      private void removeMappingsForKey(final String key)
57      {
58          for (final Iterator it = mappings.entrySet().iterator(); it.hasNext();)
59          {
60              final Map.Entry entry = (Map.Entry) it.next();
61              if (entry.getValue().equals(key))
62              {
63                  complexPaths.remove(entry.getKey());
64                  it.remove();
65              }
66          }
67      }
68  
69      public String get(String path)
70      {
71          lock.readLock().lock();
72          try
73          {
74              if (path == null)
75              {
76                  path = "/";
77              }
78              final String mapped = matcher.findKey(path, mappings, complexPaths);
79              if (mapped == null)
80              {
81                  return null;
82              }
83              return (String) mappings.get(mapped);
84          }
85          finally
86          {
87              lock.readLock().unlock();
88          }
89      }
90  
91      /*
92       * @see com.atlassian.seraph.util.IPathMapper#getAll(java.lang.String)
93       */
94      public Collection getAll(String path)
95      {
96          lock.readLock().lock();
97          try
98          {
99              if (path == null)
100             {
101                 path = "/";
102             }
103             final List matches = new ArrayList();
104             // find exact keys
105             final String exactKey = matcher.findExactKey(path, mappings);
106             if (exactKey != null)
107             {
108                 matches.add(mappings.get(exactKey));
109             }
110             // find complex keys
111             for (final Iterator iterator = matcher.findComplexKeys(path, complexPaths).iterator(); iterator.hasNext();)
112             {
113                 final String mapped = (String) iterator.next();
114                 matches.add(mappings.get(mapped));
115             }
116             // find default keys
117             for (final Iterator iterator = matcher.findDefaultKeys(mappings).iterator(); iterator.hasNext();)
118             {
119                 final String mapped = (String) iterator.next();
120                 matches.add(mappings.get(mapped));
121             }
122             return Collections.unmodifiableCollection(matches);
123         }
124         finally
125         {
126             lock.readLock().unlock();
127         }
128     }
129 
130     public String toString()
131     {
132         final StringBuffer sb = new StringBuffer(30 * (mappings.size() + complexPaths.size()));
133         sb.append("Mappings:\n");
134         for (final Iterator iterator = mappings.keySet().iterator(); iterator.hasNext();)
135         {
136             final String key = (String) iterator.next();
137             sb.append(key).append("=").append(mappings.get(key)).append("\n");
138         }
139         sb.append("Complex Paths:\n");
140         for (final Iterator iterator = complexPaths.iterator(); iterator.hasNext();)
141         {
142             final String path = (String) iterator.next();
143             sb.append(path).append("\n");
144         }
145 
146         return sb.toString();
147     }
148 
149     private final class KeyMatcher
150     {
151         /** Find exact key in mappings. */
152         String findKey(final String path, final Map mappings, final List keys)
153         {
154             String result = findExactKey(path, mappings);
155             if (result == null)
156             {
157                 result = findComplexKey(path, keys);
158             }
159             if (result == null)
160             {
161                 result = findDefaultKey(mappings);
162             }
163             return result;
164         }
165 
166         /** Check if path matches exact pattern ( /blah/blah.jsp ). */
167         String findExactKey(final String path, final Map mappings)
168         {
169             if (mappings.containsKey(path))
170             {
171                 return path;
172             }
173             return null;
174         }
175 
176         /** Find single matching complex key */
177         String findComplexKey(final String path, final List complexPaths)
178         {
179             final int size = complexPaths.size();
180             for (int i = 0; i < size; i++)
181             {
182                 final String key = (String) complexPaths.get(i);
183                 if (match(key, path, false))
184                 {
185                     return key;
186                 }
187             }
188             return null;
189         }
190 
191         /** Find all matching complex keys */
192         Collection findComplexKeys(final String path, final List complexPaths)
193         {
194             final int size = complexPaths.size();
195             final List matches = new ArrayList();
196             for (int i = 0; i < size; i++)
197             {
198                 final String key = (String) complexPaths.get(i);
199                 if (match(key, path, false))
200                 {
201                     matches.add(key);
202                 }
203             }
204             return matches;
205         }
206 
207         /** Look for root pattern ( / ). */
208         String findDefaultKey(final Map mappings)
209         {
210             for (int i = 0; i < PathMapper.DEFAULT_KEYS.length; i++)
211             {
212                 if (mappings.containsKey(PathMapper.DEFAULT_KEYS[i]))
213                 {
214                     return PathMapper.DEFAULT_KEYS[i];
215                 }
216             }
217             return null;
218         }
219 
220         /** Look for root patterns ( / ). */
221         Collection findDefaultKeys(final Map mappings)
222         {
223             final List matches = new ArrayList();
224 
225             for (int i = 0; i < PathMapper.DEFAULT_KEYS.length; i++)
226             {
227                 if (mappings.containsKey(PathMapper.DEFAULT_KEYS[i]))
228                 {
229                     matches.add(PathMapper.DEFAULT_KEYS[i]);
230                 }
231             }
232 
233             return matches;
234         }
235 
236         boolean match(final String pattern, final String str, final boolean isCaseSensitive)
237         {
238             final char[] patArr = pattern.toCharArray();
239             final char[] strArr = str.toCharArray();
240             int patIdxStart = 0;
241             int patIdxEnd = patArr.length - 1;
242             int strIdxStart = 0;
243             int strIdxEnd = strArr.length - 1;
244             char ch;
245 
246             boolean containsStar = false;
247             for (int i = 0; i < patArr.length; i++)
248             {
249                 if (patArr[i] == '*')
250                 {
251                     containsStar = true;
252                     break;
253                 }
254             }
255 
256             if (!containsStar)
257             {
258                 // No '*'s, so we make a shortcut
259                 if (patIdxEnd != strIdxEnd)
260                 {
261                     return false; // Pattern and string do not have the same size
262                 }
263                 for (int i = 0; i <= patIdxEnd; i++)
264                 {
265                     ch = patArr[i];
266                     if (ch != '?')
267                     {
268                         if (isCaseSensitive && (ch != strArr[i]))
269                         {
270                             return false;// Character mismatch
271                         }
272                         if (!isCaseSensitive && (Character.toUpperCase(ch) != Character.toUpperCase(strArr[i])))
273                         {
274                             return false; // Character mismatch
275                         }
276                     }
277                 }
278                 return true; // String matches against pattern
279             }
280 
281             if (patIdxEnd == 0)
282             {
283                 return true; // Pattern contains only '*', which matches anything
284             }
285 
286             // Process characters before first star
287             while (((ch = patArr[patIdxStart]) != '*') && (strIdxStart <= strIdxEnd))
288             {
289                 if (ch != '?')
290                 {
291                     if (isCaseSensitive && (ch != strArr[strIdxStart]))
292                     {
293                         return false;// Character mismatch
294                     }
295                     if (!isCaseSensitive && (Character.toUpperCase(ch) != Character.toUpperCase(strArr[strIdxStart])))
296                     {
297                         return false;// Character mismatch
298                     }
299                 }
300                 patIdxStart++;
301                 strIdxStart++;
302             }
303             if (strIdxStart > strIdxEnd)
304             {
305                 // All characters in the string are used. Check if only '*'s are
306                 // left in the pattern. If so, we succeeded. Otherwise failure.
307                 for (int i = patIdxStart; i <= patIdxEnd; i++)
308                 {
309                     if (patArr[i] != '*')
310                     {
311                         return false;
312                     }
313                 }
314                 return true;
315             }
316 
317             // Process characters after last star
318             while (((ch = patArr[patIdxEnd]) != '*') && (strIdxStart <= strIdxEnd))
319             {
320                 if (ch != '?')
321                 {
322                     if (isCaseSensitive && (ch != strArr[strIdxEnd]))
323                     {
324                         return false;// Character mismatch
325                     }
326                     if (!isCaseSensitive && (Character.toUpperCase(ch) != Character.toUpperCase(strArr[strIdxEnd])))
327                     {
328                         return false;// Character mismatch
329                     }
330                 }
331                 patIdxEnd--;
332                 strIdxEnd--;
333             }
334             if (strIdxStart > strIdxEnd)
335             {
336                 // All characters in the string are used. Check if only '*'s are
337                 // left in the pattern. If so, we succeeded. Otherwise failure.
338                 for (int i = patIdxStart; i <= patIdxEnd; i++)
339                 {
340                     if (patArr[i] != '*')
341                     {
342                         return false;
343                     }
344                 }
345                 return true;
346             }
347 
348             // process pattern between stars. padIdxStart and patIdxEnd point
349             // always to a '*'.
350             while ((patIdxStart != patIdxEnd) && (strIdxStart <= strIdxEnd))
351             {
352                 int patIdxTmp = -1;
353                 for (int i = patIdxStart + 1; i <= patIdxEnd; i++)
354                 {
355                     if (patArr[i] == '*')
356                     {
357                         patIdxTmp = i;
358                         break;
359                     }
360                 }
361                 if (patIdxTmp == patIdxStart + 1)
362                 {
363                     // Two stars next to each other, skip the first one.
364                     patIdxStart++;
365                     continue;
366                 }
367                 // Find the pattern between padIdxStart & padIdxTmp in str between
368                 // strIdxStart & strIdxEnd
369                 final int patLength = (patIdxTmp - patIdxStart - 1);
370                 final int strLength = (strIdxEnd - strIdxStart + 1);
371                 int foundIdx = -1;
372                 strLoop : for (int i = 0; i <= strLength - patLength; i++)
373                 {
374                     for (int j = 0; j < patLength; j++)
375                     {
376                         ch = patArr[patIdxStart + j + 1];
377                         if (ch != '?')
378                         {
379                             if (isCaseSensitive && (ch != strArr[strIdxStart + i + j]))
380                             {
381                                 continue strLoop;
382                             }
383                             if (!isCaseSensitive && (Character.toUpperCase(ch) != Character.toUpperCase(strArr[strIdxStart + i + j])))
384                             {
385                                 continue strLoop;
386                             }
387                         }
388                     }
389 
390                     foundIdx = strIdxStart + i;
391                     break;
392                 }
393 
394                 if (foundIdx == -1)
395                 {
396                     return false;
397                 }
398 
399                 patIdxStart = patIdxTmp;
400                 strIdxStart = foundIdx + patLength;
401             }
402 
403             // All characters in the string are used. Check if only '*'s are left
404             // in the pattern. If so, we succeeded. Otherwise failure.
405             for (int i = patIdxStart; i <= patIdxEnd; i++)
406             {
407                 if (patArr[i] != '*')
408                 {
409                     return false;
410                 }
411             }
412             return true;
413         }
414     }
415 }