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.
9 // The Eclipse Public License is available at
10 // http://www.eclipse.org/legal/epl-v10.html
12 // The Apache License v2.0 is available at
13 // http://www.opensource.org/licenses/apache2.0.php
15 // You may elect to redistribute this code under either of these licenses.
16 // ========================================================================
19 package org.eclipse.jetty.http;
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;
28 import java.util.StringTokenizer;
30 import org.eclipse.jetty.util.ArrayTernaryTrie;
31 import org.eclipse.jetty.util.IncludeExclude;
32 import org.eclipse.jetty.util.Predicate;
33 import org.eclipse.jetty.util.Trie;
34 import org.eclipse.jetty.util.URIUtil;
36 /* ------------------------------------------------------------ */
37 /** URI path map to Object.
38 * This mapping implements the path specification recommended
39 * in the 2.2 Servlet API.
41 * Path specifications can be of the following forms:<PRE>
42 * /foo/bar - an exact path specification.
43 * /foo/* - a prefix path specification (must end '/*').
44 * *.ext - a suffix path specification.
45 * / - the default path specification.
46 * "" - the / path specification
48 * Matching is performed in the following order <NL>
50 * <LI>Longest prefix match.
51 * <LI>Longest suffix match.
54 * Multiple path specifications can be mapped by providing a list of
55 * specifications. By default this class uses characters ":," as path
56 * separators, unless configured differently by calling the static
57 * method @see PathMap#setPathSpecSeparators(String)
59 * Special characters within paths such as '?� and ';' are not treated specially
60 * as it is assumed they would have been either encoded in the original URL or
61 * stripped from the path.
63 * This class is not synchronized. If concurrent modifications are
64 * possible then it should be synchronized at a higher level.
68 public class PathMap<O> extends HashMap<String,O>
70 /* ------------------------------------------------------------ */
71 private static String __pathSpecSeparators = ":,";
73 /* ------------------------------------------------------------ */
74 /** Set the path spec separator.
75 * Multiple path specification may be included in a single string
76 * if they are separated by the characters set in this string.
77 * By default this class uses ":," characters as path separators.
80 public static void setPathSpecSeparators(String s)
82 __pathSpecSeparators=s;
85 /* --------------------------------------------------------------- */
86 Trie<MappedEntry<O>> _prefixMap=new ArrayTernaryTrie<>(false);
87 Trie<MappedEntry<O>> _suffixMap=new ArrayTernaryTrie<>(false);
88 final Map<String,MappedEntry<O>> _exactMap=new HashMap<>();
90 List<MappedEntry<O>> _defaultSingletonList=null;
91 MappedEntry<O> _prefixDefault=null;
92 MappedEntry<O> _default=null;
93 boolean _nodefault=false;
95 /* --------------------------------------------------------------- */
101 /* --------------------------------------------------------------- */
102 public PathMap(boolean noDefault)
107 /* --------------------------------------------------------------- */
108 public PathMap(int capacity)
110 this(capacity, false);
113 /* --------------------------------------------------------------- */
114 private PathMap(int capacity, boolean noDefault)
117 _nodefault=noDefault;
120 /* --------------------------------------------------------------- */
121 /** Construct from dictionary PathMap.
123 public PathMap(Map<String, ? extends O> m)
128 /* --------------------------------------------------------------- */
129 /** Add a single path match to the PathMap.
130 * @param pathSpec The path specification, or comma separated list of
131 * path specifications.
132 * @param object The object the path maps to
135 public O put(String pathSpec, O object)
137 if ("".equals(pathSpec.trim()))
139 MappedEntry<O> entry = new MappedEntry<>("",object);
141 _exactMap.put("", entry);
142 return super.put("", object);
145 StringTokenizer tok = new StringTokenizer(pathSpec,__pathSpecSeparators);
148 while (tok.hasMoreTokens())
150 String spec=tok.nextToken();
152 if (!spec.startsWith("/") && !spec.startsWith("*."))
153 throw new IllegalArgumentException("PathSpec "+spec+". must start with '/' or '*.'");
155 old = super.put(spec,object);
157 // Make entry that was just created.
158 MappedEntry<O> entry = new MappedEntry<>(spec,object);
160 if (entry.getKey().equals(spec))
162 if (spec.equals("/*"))
163 _prefixDefault=entry;
164 else if (spec.endsWith("/*"))
166 String mapped=spec.substring(0,spec.length()-2);
167 entry.setMapped(mapped);
168 while (!_prefixMap.put(mapped,entry))
169 _prefixMap=new ArrayTernaryTrie<>((ArrayTernaryTrie<MappedEntry<O>>)_prefixMap,1.5);
171 else if (spec.startsWith("*."))
173 String suffix=spec.substring(2);
174 while(!_suffixMap.put(suffix,entry))
175 _suffixMap=new ArrayTernaryTrie<>((ArrayTernaryTrie<MappedEntry<O>>)_suffixMap,1.5);
177 else if (spec.equals(URIUtil.SLASH))
180 _exactMap.put(spec,entry);
184 _defaultSingletonList=Collections.singletonList(_default);
189 entry.setMapped(spec);
190 _exactMap.put(spec,entry);
198 /* ------------------------------------------------------------ */
199 /** Get object matched by the path.
200 * @param path the path.
201 * @return Best matched object or null.
203 public O match(String path)
205 MappedEntry<O> entry = getMatch(path);
207 return entry.getValue();
212 /* --------------------------------------------------------------- */
213 /** Get the entry mapped by the best specification.
214 * @param path the path.
215 * @return Map.Entry of the best matched or null.
217 public MappedEntry<O> getMatch(String path)
224 MappedEntry<O> entry=null;
227 if (l == 1 && path.charAt(0)=='/')
229 entry = _exactMap.get("");
235 entry=_exactMap.get(path);
241 final Trie<PathMap.MappedEntry<O>> prefix_map=_prefixMap;
244 entry=prefix_map.getBest(path,0,i);
247 String key = entry.getKey();
248 if (key.length()-2>=path.length() || path.charAt(key.length()-2)=='/')
254 if (_prefixDefault!=null)
255 return _prefixDefault;
259 final Trie<PathMap.MappedEntry<O>> suffix_map=_suffixMap;
260 while ((i=path.indexOf('.',i+1))>0)
262 entry=suffix_map.get(path,i+1,l-i-1);
271 /* --------------------------------------------------------------- */
272 /** Get all entries matched by the path.
274 * @param path Path to match
275 * @return List of Map.Entry instances key=pathSpec
277 public List<? extends Map.Entry<String,O>> getMatches(String path)
279 MappedEntry<O> entry;
280 List<MappedEntry<O>> entries=new ArrayList<>();
284 if (path.length()==0)
285 return _defaultSingletonList;
288 entry=_exactMap.get(path);
295 final Trie<PathMap.MappedEntry<O>> prefix_map=_prefixMap;
298 entry=prefix_map.getBest(path,0,i);
301 String key = entry.getKey();
302 if (key.length()-2>=path.length() || path.charAt(key.length()-2)=='/')
309 if (_prefixDefault!=null)
310 entries.add(_prefixDefault);
314 final Trie<PathMap.MappedEntry<O>> suffix_map=_suffixMap;
315 while ((i=path.indexOf('.',i+1))>0)
317 entry=suffix_map.get(path,i+1,l-i-1);
323 if ("/".equals(path))
325 entry=_exactMap.get("");
332 entries.add(_default);
338 /* --------------------------------------------------------------- */
339 /** Return whether the path matches any entries in the PathMap,
340 * excluding the default entry
341 * @param path Path to match
342 * @return Whether the PathMap contains any entries that match this
344 public boolean containsMatch(String path)
346 MappedEntry<?> match = getMatch(path);
347 return match!=null && !match.equals(_default);
350 /* --------------------------------------------------------------- */
352 public O remove(Object pathSpec)
356 String spec=(String) pathSpec;
357 if (spec.equals("/*"))
359 else if (spec.endsWith("/*"))
360 _prefixMap.remove(spec.substring(0,spec.length()-2));
361 else if (spec.startsWith("*."))
362 _suffixMap.remove(spec.substring(2));
363 else if (spec.equals(URIUtil.SLASH))
366 _defaultSingletonList=null;
369 _exactMap.remove(spec);
371 return super.remove(pathSpec);
374 /* --------------------------------------------------------------- */
379 _prefixMap=new ArrayTernaryTrie<>(false);
380 _suffixMap=new ArrayTernaryTrie<>(false);
382 _defaultSingletonList=null;
387 /* --------------------------------------------------------------- */
389 * @return true if match.
391 public static boolean match(String pathSpec, String path)
392 throws IllegalArgumentException
394 return match(pathSpec, path, false);
397 /* --------------------------------------------------------------- */
399 * @return true if match.
401 public static boolean match(String pathSpec, String path, boolean noDefault)
402 throws IllegalArgumentException
404 if (pathSpec.length()==0)
405 return "/".equals(path);
407 char c = pathSpec.charAt(0);
410 if (!noDefault && pathSpec.length()==1 || pathSpec.equals(path))
413 if(isPathWildcardMatch(pathSpec, path))
417 return path.regionMatches(path.length()-pathSpec.length()+1,
418 pathSpec,1,pathSpec.length()-1);
422 /* --------------------------------------------------------------- */
423 private static boolean isPathWildcardMatch(String pathSpec, String path)
425 // For a spec of "/foo/*" match "/foo" , "/foo/..." but not "/foobar"
426 int cpl=pathSpec.length()-2;
427 if (pathSpec.endsWith("/*") && path.regionMatches(0,pathSpec,0,cpl))
429 if (path.length()==cpl || '/'==path.charAt(cpl))
436 /* --------------------------------------------------------------- */
437 /** Return the portion of a path that matches a path spec.
438 * @return null if no match at all.
440 public static String pathMatch(String pathSpec, String path)
442 char c = pathSpec.charAt(0);
446 if (pathSpec.length()==1)
449 if (pathSpec.equals(path))
452 if (isPathWildcardMatch(pathSpec, path))
453 return path.substring(0,pathSpec.length()-2);
457 if (path.regionMatches(path.length()-(pathSpec.length()-1),
458 pathSpec,1,pathSpec.length()-1))
464 /* --------------------------------------------------------------- */
465 /** Return the portion of a path that is after a path spec.
466 * @return The path info string
468 public static String pathInfo(String pathSpec, String path)
470 if ("".equals(pathSpec))
471 return path; //servlet 3 spec sec 12.2 will be '/'
473 char c = pathSpec.charAt(0);
477 if (pathSpec.length()==1)
480 boolean wildcard = isPathWildcardMatch(pathSpec, path);
482 // handle the case where pathSpec uses a wildcard and path info is "/*"
483 if (pathSpec.equals(path) && !wildcard)
488 if (path.length()==pathSpec.length()-2)
490 return path.substring(pathSpec.length()-2);
497 /* ------------------------------------------------------------ */
499 * @param base The base the path is relative to.
500 * @param pathSpec The spec of the path segment to ignore.
501 * @param path the additional path
502 * @return base plus path with pathspec removed
504 public static String relativePath(String base,
508 String info=pathInfo(pathSpec,path);
512 if( info.startsWith( "./"))
513 info = info.substring( 2);
514 if( base.endsWith( URIUtil.SLASH))
515 if( info.startsWith( URIUtil.SLASH))
516 path = base + info.substring(1);
520 if( info.startsWith( URIUtil.SLASH))
523 path = base + URIUtil.SLASH + info;
527 /* ------------------------------------------------------------ */
528 /* ------------------------------------------------------------ */
529 /* ------------------------------------------------------------ */
530 public static class MappedEntry<O> implements Map.Entry<String,O>
532 private final String key;
533 private final O value;
534 private String mapped;
536 MappedEntry(String key, O value)
543 public String getKey()
555 public O setValue(O o)
557 throw new UnsupportedOperationException();
561 public String toString()
563 return key+"="+value;
566 public String getMapped()
571 void setMapped(String mapped)
573 this.mapped = mapped;
577 public static class PathSet extends AbstractSet<String> implements Predicate<String>
579 private final PathMap<Boolean> _map = new PathMap<>();
582 public Iterator<String> iterator()
584 return _map.keySet().iterator();
594 public boolean add(String item)
596 return _map.put(item,Boolean.TRUE)==null;
600 public boolean remove(Object item)
602 return _map.remove(item)!=null;
606 public boolean contains(Object o)
608 return _map.containsKey(o);
612 public boolean test(String s)
614 return _map.containsMatch(s);
617 public boolean containsMatch(String s)
619 return _map.containsMatch(s);
621 public boolean matches(String item)
623 return _map.containsMatch(item);