View Javadoc

1   //
2   //  ========================================================================
3   //  Copyright (c) 1995-2016 Mort Bay Consulting Pty. Ltd.
4   //  ------------------------------------------------------------------------
5   //  All rights reserved. This program and the accompanying materials
6   //  are made available under the terms of the Eclipse Public License v1.0
7   //  and Apache License v2.0 which accompanies this distribution.
8   //
9   //      The Eclipse Public License is available at
10  //      http://www.eclipse.org/legal/epl-v10.html
11  //
12  //      The Apache License v2.0 is available at
13  //      http://www.opensource.org/licenses/apache2.0.php
14  //
15  //  You may elect to redistribute this code under either of these licenses.
16  //  ========================================================================
17  //
18  
19  package org.eclipse.jetty.http;
20  
21  import java.util.AbstractSet;
22  import java.util.ArrayList;
23  import java.util.Collections;
24  import java.util.HashMap;
25  import java.util.Iterator;
26  import java.util.List;
27  import java.util.Map;
28  import java.util.StringTokenizer;
29  import java.util.function.Predicate;
30  
31  import org.eclipse.jetty.util.ArrayTernaryTrie;
32  import org.eclipse.jetty.util.Trie;
33  import org.eclipse.jetty.util.URIUtil;
34  
35  /** 
36   * URI path map to Object.
37   * <p>
38   * This mapping implements the path specification recommended
39   * in the 2.2 Servlet API.
40   * </p>
41   *
42   * <p>
43   * Path specifications can be of the following forms:
44   * </p>
45   * <pre>
46   * /foo/bar           - an exact path specification.
47   * /foo/*             - a prefix path specification (must end '/*').
48   * *.ext              - a suffix path specification.
49   * /                  - the default path specification.
50   * ""                 - the / path specification
51   * </pre>
52   * 
53   * Matching is performed in the following order 
54   * <ol>
55   * <li>Exact match.</li>
56   * <li>Longest prefix match.</li>
57   * <li>Longest suffix match.</li>
58   * <li>default.</li>
59   * </ol>
60   * 
61   * <p>
62   * Multiple path specifications can be mapped by providing a list of
63   * specifications. By default this class uses characters ":," as path
64   * separators, unless configured differently by calling the static
65   * method @see PathMap#setPathSpecSeparators(String)
66   * <p>
67   * Special characters within paths such as '?� and ';' are not treated specially
68   * as it is assumed they would have been either encoded in the original URL or
69   * stripped from the path.
70   * <p>
71   * This class is not synchronized.  If concurrent modifications are
72   * possible then it should be synchronized at a higher level.
73   * 
74   * @param <O> the Map.Entry value type
75   * @deprecated replaced with {@link org.eclipse.jetty.http.pathmap.PathMappings} (this class will be removed in Jetty 10) 
76   */
77  @Deprecated
78  public class PathMap<O> extends HashMap<String,O>
79  {
80      /* ------------------------------------------------------------ */
81      private static String __pathSpecSeparators = ":,";
82  
83      /* ------------------------------------------------------------ */
84      /** Set the path spec separator.
85       * Multiple path specification may be included in a single string
86       * if they are separated by the characters set in this string.
87       * By default this class uses ":," characters as path separators.
88       * @param s separators
89       */
90      public static void setPathSpecSeparators(String s)
91      {
92          __pathSpecSeparators=s;
93      }
94  
95      /* --------------------------------------------------------------- */
96      Trie<MappedEntry<O>> _prefixMap=new ArrayTernaryTrie<>(false);
97      Trie<MappedEntry<O>> _suffixMap=new ArrayTernaryTrie<>(false);
98      final Map<String,MappedEntry<O>> _exactMap=new HashMap<>();
99  
100     List<MappedEntry<O>> _defaultSingletonList=null;
101     MappedEntry<O> _prefixDefault=null;
102     MappedEntry<O> _default=null;
103     boolean _nodefault=false;
104 
105     /* --------------------------------------------------------------- */
106     public PathMap()
107     {
108         this(11);
109     }
110 
111     /* --------------------------------------------------------------- */
112     public PathMap(boolean noDefault)
113     {
114         this(11, noDefault);
115     }
116 
117     /* --------------------------------------------------------------- */
118     public PathMap(int capacity)
119     {
120         this(capacity, false);
121     }
122 
123     /* --------------------------------------------------------------- */
124     private PathMap(int capacity, boolean noDefault)
125     {
126         super(capacity);
127         _nodefault=noDefault;
128     }
129 
130     /* --------------------------------------------------------------- */
131     /** 
132      * Construct from dictionary PathMap.
133      * @param dictMap the map representing the dictionary to build this PathMap from
134      */
135     public PathMap(Map<String, ? extends O> dictMap)
136     {
137         putAll(dictMap);
138     }
139 
140     /* --------------------------------------------------------------- */
141     /** Add a single path match to the PathMap.
142      * @param pathSpec The path specification, or comma separated list of
143      * path specifications.
144      * @param object The object the path maps to
145      */
146     @Override
147     public O put(String pathSpec, O object)
148     {
149         if ("".equals(pathSpec.trim()))
150         {
151             MappedEntry<O> entry = new MappedEntry<>("",object);
152             entry.setMapped("");
153             _exactMap.put("", entry);
154             return super.put("", object);
155         }
156 
157         StringTokenizer tok = new StringTokenizer(pathSpec,__pathSpecSeparators);
158         O old =null;
159 
160         while (tok.hasMoreTokens())
161         {
162             String spec=tok.nextToken();
163 
164             if (!spec.startsWith("/") && !spec.startsWith("*."))
165                 throw new IllegalArgumentException("PathSpec "+spec+". must start with '/' or '*.'");
166 
167             old = super.put(spec,object);
168 
169             // Make entry that was just created.
170             MappedEntry<O> entry = new MappedEntry<>(spec,object);
171 
172             if (entry.getKey().equals(spec))
173             {
174                 if (spec.equals("/*"))
175                     _prefixDefault=entry;
176                 else if (spec.endsWith("/*"))
177                 {
178                     String mapped=spec.substring(0,spec.length()-2);
179                     entry.setMapped(mapped);
180                     while (!_prefixMap.put(mapped,entry))
181                         _prefixMap=new ArrayTernaryTrie<>((ArrayTernaryTrie<MappedEntry<O>>)_prefixMap,1.5);
182                 }
183                 else if (spec.startsWith("*."))
184                 {
185                     String suffix=spec.substring(2);
186                     while(!_suffixMap.put(suffix,entry))
187                         _suffixMap=new ArrayTernaryTrie<>((ArrayTernaryTrie<MappedEntry<O>>)_suffixMap,1.5);
188                 }
189                 else if (spec.equals(URIUtil.SLASH))
190                 {
191                     if (_nodefault)
192                         _exactMap.put(spec,entry);
193                     else
194                     {
195                         _default=entry;
196                         _defaultSingletonList=Collections.singletonList(_default);
197                     }
198                 }
199                 else
200                 {
201                     entry.setMapped(spec);
202                     _exactMap.put(spec,entry);
203                 }
204             }
205         }
206 
207         return old;
208     }
209 
210     /* ------------------------------------------------------------ */
211     /** Get object matched by the path.
212      * @param path the path.
213      * @return Best matched object or null.
214      */
215     public O match(String path)
216     {
217         MappedEntry<O> entry = getMatch(path);
218         if (entry!=null)
219             return entry.getValue();
220         return null;
221     }
222 
223 
224     /* --------------------------------------------------------------- */
225     /** Get the entry mapped by the best specification.
226      * @param path the path.
227      * @return Map.Entry of the best matched  or null.
228      */
229     public MappedEntry<O> getMatch(String path)
230     {
231         if (path==null)
232             return null;
233 
234         int l=path.length();
235 
236         MappedEntry<O> entry=null;
237 
238         //special case
239         if (l == 1 && path.charAt(0)=='/')
240         {
241             entry = _exactMap.get("");
242             if (entry != null)
243                 return entry;
244         }
245 
246         // try exact match
247         entry=_exactMap.get(path);
248         if (entry!=null)
249             return entry;
250 
251         // prefix search
252         int i=l;
253         final Trie<PathMap.MappedEntry<O>> prefix_map=_prefixMap;
254         while(i>=0)
255         {
256             entry=prefix_map.getBest(path,0,i);
257             if (entry==null)
258                 break;
259             String key = entry.getKey();
260             if (key.length()-2>=path.length() || path.charAt(key.length()-2)=='/')
261                 return entry;
262             i=key.length()-3;
263         }
264 
265         // Prefix Default
266         if (_prefixDefault!=null)
267             return _prefixDefault;
268 
269         // Extension search
270         i=0;
271         final Trie<PathMap.MappedEntry<O>> suffix_map=_suffixMap;
272         while ((i=path.indexOf('.',i+1))>0)
273         {
274             entry=suffix_map.get(path,i+1,l-i-1);
275             if (entry!=null)
276                 return entry;
277         }
278 
279         // Default
280         return _default;
281     }
282 
283     /* --------------------------------------------------------------- */
284     /** Get all entries matched by the path.
285      * Best match first.
286      * @param path Path to match
287      * @return List of Map.Entry instances key=pathSpec
288      */
289     public List<? extends Map.Entry<String,O>> getMatches(String path)
290     {
291         MappedEntry<O> entry;
292         List<MappedEntry<O>> entries=new ArrayList<>();
293 
294         if (path==null)
295             return entries;
296         if (path.length()==0)
297             return _defaultSingletonList;
298 
299         // try exact match
300         entry=_exactMap.get(path);
301         if (entry!=null)
302             entries.add(entry);
303 
304         // prefix search
305         int l=path.length();
306         int i=l;
307         final Trie<PathMap.MappedEntry<O>> prefix_map=_prefixMap;
308         while(i>=0)
309         {
310             entry=prefix_map.getBest(path,0,i);
311             if (entry==null)
312                 break;
313             String key = entry.getKey();
314             if (key.length()-2>=path.length() || path.charAt(key.length()-2)=='/')
315                 entries.add(entry);
316 
317             i=key.length()-3;
318         }
319 
320         // Prefix Default
321         if (_prefixDefault!=null)
322             entries.add(_prefixDefault);
323 
324         // Extension search
325         i=0;
326         final Trie<PathMap.MappedEntry<O>> suffix_map=_suffixMap;
327         while ((i=path.indexOf('.',i+1))>0)
328         {
329             entry=suffix_map.get(path,i+1,l-i-1);
330             if (entry!=null)
331                 entries.add(entry);
332         }
333 
334         // root match
335         if ("/".equals(path))
336         {
337             entry=_exactMap.get("");
338             if (entry!=null)
339                 entries.add(entry);
340         }
341             
342         // Default
343         if (_default!=null)
344             entries.add(_default);
345 
346         return entries;
347     }
348 
349 
350     /* --------------------------------------------------------------- */
351     /** Return whether the path matches any entries in the PathMap,
352      * excluding the default entry
353      * @param path Path to match
354      * @return Whether the PathMap contains any entries that match this
355      */
356     public boolean containsMatch(String path)
357     {
358         MappedEntry<?> match = getMatch(path);
359         return match!=null && !match.equals(_default);
360     }
361 
362     /* --------------------------------------------------------------- */
363     @Override
364     public O remove(Object pathSpec)
365     {
366         if (pathSpec!=null)
367         {
368             String spec=(String) pathSpec;
369             if (spec.equals("/*"))
370                 _prefixDefault=null;
371             else if (spec.endsWith("/*"))
372                 _prefixMap.remove(spec.substring(0,spec.length()-2));
373             else if (spec.startsWith("*."))
374                 _suffixMap.remove(spec.substring(2));
375             else if (spec.equals(URIUtil.SLASH))
376             {
377                 _default=null;
378                 _defaultSingletonList=null;
379             }
380             else
381                 _exactMap.remove(spec);
382         }
383         return super.remove(pathSpec);
384     }
385 
386     /* --------------------------------------------------------------- */
387     @Override
388     public void clear()
389     {
390         _exactMap.clear();
391         _prefixMap=new ArrayTernaryTrie<>(false);
392         _suffixMap=new ArrayTernaryTrie<>(false);
393         _default=null;
394         _defaultSingletonList=null;
395         _prefixDefault=null;
396         super.clear();
397     }
398 
399     /* --------------------------------------------------------------- */
400     /**
401      * @param pathSpec the path spec
402      * @param path the path
403      * @return true if match.
404      */
405     public static boolean match(String pathSpec, String path)
406     {
407         return match(pathSpec, path, false);
408     }
409 
410     /* --------------------------------------------------------------- */
411     /**
412      * @param pathSpec the path spec
413      * @param path the path
414      * @param noDefault true to not handle the default path "/" special, false to allow matcher rules to run  
415      * @return true if match.
416      */
417     public static boolean match(String pathSpec, String path, boolean noDefault)
418     {
419         if (pathSpec.length()==0)
420             return "/".equals(path);
421             
422         char c = pathSpec.charAt(0);
423         if (c=='/')
424         {
425             if (!noDefault && pathSpec.length()==1 || pathSpec.equals(path))
426                 return true;
427 
428             if(isPathWildcardMatch(pathSpec, path))
429                 return true;
430         }
431         else if (c=='*')
432             return path.regionMatches(path.length()-pathSpec.length()+1,
433                     pathSpec,1,pathSpec.length()-1);
434         return false;
435     }
436 
437     /* --------------------------------------------------------------- */
438     private static boolean isPathWildcardMatch(String pathSpec, String path)
439     {
440         // For a spec of "/foo/*" match "/foo" , "/foo/..." but not "/foobar"
441         int cpl=pathSpec.length()-2;
442         if (pathSpec.endsWith("/*") && path.regionMatches(0,pathSpec,0,cpl))
443         {
444             if (path.length()==cpl || '/'==path.charAt(cpl))
445                 return true;
446         }
447         return false;
448     }
449 
450 
451     /* --------------------------------------------------------------- */
452     /** Return the portion of a path that matches a path spec.
453      * @param pathSpec the path spec
454      * @param path the path
455      * @return null if no match at all.
456      */
457     public static String pathMatch(String pathSpec, String path)
458     {
459         char c = pathSpec.charAt(0);
460 
461         if (c=='/')
462         {
463             if (pathSpec.length()==1)
464                 return path;
465 
466             if (pathSpec.equals(path))
467                 return path;
468 
469             if (isPathWildcardMatch(pathSpec, path))
470                 return path.substring(0,pathSpec.length()-2);
471         }
472         else if (c=='*')
473         {
474             if (path.regionMatches(path.length()-(pathSpec.length()-1),
475                     pathSpec,1,pathSpec.length()-1))
476                 return path;
477         }
478         return null;
479     }
480 
481     /* --------------------------------------------------------------- */
482     /** Return the portion of a path that is after a path spec.
483      * @param pathSpec the path spec
484      * @param path the path
485      * @return The path info string
486      */
487     public static String pathInfo(String pathSpec, String path)
488     {
489         if ("".equals(pathSpec))
490             return path; //servlet 3 spec sec 12.2 will be '/'
491 
492         char c = pathSpec.charAt(0);
493 
494         if (c=='/')
495         {
496             if (pathSpec.length()==1)
497                 return null;
498 
499             boolean wildcard = isPathWildcardMatch(pathSpec, path);
500 
501             // handle the case where pathSpec uses a wildcard and path info is "/*"
502             if (pathSpec.equals(path) && !wildcard)
503                 return null;
504 
505             if (wildcard)
506             {
507                 if (path.length()==pathSpec.length()-2)
508                     return null;
509                 return path.substring(pathSpec.length()-2);
510             }
511         }
512         return null;
513     }
514 
515 
516     /* ------------------------------------------------------------ */
517     /** Relative path.
518      * @param base The base the path is relative to.
519      * @param pathSpec The spec of the path segment to ignore.
520      * @param path the additional path
521      * @return base plus path with pathspec removed
522      */
523     public static String relativePath(String base,
524             String pathSpec,
525             String path )
526     {
527         String info=pathInfo(pathSpec,path);
528         if (info==null)
529             info=path;
530 
531         if( info.startsWith( "./"))
532             info = info.substring( 2);
533         if( base.endsWith( URIUtil.SLASH))
534             if( info.startsWith( URIUtil.SLASH))
535                 path = base + info.substring(1);
536             else
537                 path = base + info;
538         else
539             if( info.startsWith( URIUtil.SLASH))
540                 path = base + info;
541             else
542                 path = base + URIUtil.SLASH + info;
543         return path;
544     }
545 
546     /* ------------------------------------------------------------ */
547     /* ------------------------------------------------------------ */
548     /* ------------------------------------------------------------ */
549     public static class MappedEntry<O> implements Map.Entry<String,O>
550     {
551         private final String key;
552         private final O value;
553         private String mapped;
554 
555         MappedEntry(String key, O value)
556         {
557             this.key=key;
558             this.value=value;
559         }
560 
561         @Override
562         public String getKey()
563         {
564             return key;
565         }
566 
567         @Override
568         public O getValue()
569         {
570             return value;
571         }
572 
573         @Override
574         public O setValue(O o)
575         {
576             throw new UnsupportedOperationException();
577         }
578 
579         @Override
580         public String toString()
581         {
582             return key+"="+value;
583         }
584 
585         public String getMapped()
586         {
587             return mapped;
588         }
589 
590         void setMapped(String mapped)
591         {
592             this.mapped = mapped;
593         }
594     }
595     
596     public static class PathSet extends AbstractSet<String> implements Predicate<String>
597     {
598         private final PathMap<Boolean> _map = new PathMap<>();
599         
600         @Override
601         public Iterator<String> iterator()
602         {
603             return _map.keySet().iterator();
604         }
605 
606         @Override
607         public int size()
608         {
609             return _map.size();
610         }
611         
612         @Override
613         public boolean add(String item)
614         {
615             return _map.put(item,Boolean.TRUE)==null;
616         }
617         
618         @Override
619         public boolean remove(Object item)
620         {
621             return _map.remove(item)!=null;
622         }
623 
624         @Override
625         public boolean contains(Object o) 
626         { 
627             return _map.containsKey(o); 
628         }
629         
630         @Override
631         public boolean test(String s)
632         {
633             return _map.containsMatch(s);
634         }
635         
636         public boolean containsMatch(String s) 
637         { 
638             return _map.containsMatch(s); 
639         }
640     }
641 }