| // |
| // ======================================================================== |
| // Copyright (c) 1995-2017 Mort Bay Consulting Pty. Ltd. |
| // ------------------------------------------------------------------------ |
| // All rights reserved. This program and the accompanying materials |
| // are made available under the terms of the Eclipse Public License v1.0 |
| // and Apache License v2.0 which accompanies this distribution. |
| // |
| // The Eclipse Public License is available at |
| // http://www.eclipse.org/legal/epl-v10.html |
| // |
| // The Apache License v2.0 is available at |
| // http://www.opensource.org/licenses/apache2.0.php |
| // |
| // You may elect to redistribute this code under either of these licenses. |
| // ======================================================================== |
| // |
| |
| package org.eclipse.jetty.http; |
| |
| import java.util.AbstractSet; |
| import java.util.ArrayList; |
| import java.util.Collections; |
| import java.util.HashMap; |
| import java.util.Iterator; |
| import java.util.List; |
| import java.util.Map; |
| import java.util.StringTokenizer; |
| |
| import org.eclipse.jetty.util.ArrayTernaryTrie; |
| import org.eclipse.jetty.util.IncludeExclude; |
| import org.eclipse.jetty.util.Predicate; |
| import org.eclipse.jetty.util.Trie; |
| import org.eclipse.jetty.util.URIUtil; |
| |
| /* ------------------------------------------------------------ */ |
| /** URI path map to Object. |
| * This mapping implements the path specification recommended |
| * in the 2.2 Servlet API. |
| * |
| * Path specifications can be of the following forms:<PRE> |
| * /foo/bar - an exact path specification. |
| * /foo/* - a prefix path specification (must end '/*'). |
| * *.ext - a suffix path specification. |
| * / - the default path specification. |
| * "" - the / path specification |
| * </PRE> |
| * Matching is performed in the following order <NL> |
| * <LI>Exact match. |
| * <LI>Longest prefix match. |
| * <LI>Longest suffix match. |
| * <LI>default. |
| * </NL> |
| * Multiple path specifications can be mapped by providing a list of |
| * specifications. By default this class uses characters ":," as path |
| * separators, unless configured differently by calling the static |
| * method @see PathMap#setPathSpecSeparators(String) |
| * <P> |
| * Special characters within paths such as '?� and ';' are not treated specially |
| * as it is assumed they would have been either encoded in the original URL or |
| * stripped from the path. |
| * <P> |
| * This class is not synchronized. If concurrent modifications are |
| * possible then it should be synchronized at a higher level. |
| * |
| * |
| */ |
| public class PathMap<O> extends HashMap<String,O> |
| { |
| /* ------------------------------------------------------------ */ |
| private static String __pathSpecSeparators = ":,"; |
| |
| /* ------------------------------------------------------------ */ |
| /** Set the path spec separator. |
| * Multiple path specification may be included in a single string |
| * if they are separated by the characters set in this string. |
| * By default this class uses ":," characters as path separators. |
| * @param s separators |
| */ |
| public static void setPathSpecSeparators(String s) |
| { |
| __pathSpecSeparators=s; |
| } |
| |
| /* --------------------------------------------------------------- */ |
| Trie<MappedEntry<O>> _prefixMap=new ArrayTernaryTrie<>(false); |
| Trie<MappedEntry<O>> _suffixMap=new ArrayTernaryTrie<>(false); |
| final Map<String,MappedEntry<O>> _exactMap=new HashMap<>(); |
| |
| List<MappedEntry<O>> _defaultSingletonList=null; |
| MappedEntry<O> _prefixDefault=null; |
| MappedEntry<O> _default=null; |
| boolean _nodefault=false; |
| |
| /* --------------------------------------------------------------- */ |
| public PathMap() |
| { |
| this(11); |
| } |
| |
| /* --------------------------------------------------------------- */ |
| public PathMap(boolean noDefault) |
| { |
| this(11, noDefault); |
| } |
| |
| /* --------------------------------------------------------------- */ |
| public PathMap(int capacity) |
| { |
| this(capacity, false); |
| } |
| |
| /* --------------------------------------------------------------- */ |
| private PathMap(int capacity, boolean noDefault) |
| { |
| super(capacity); |
| _nodefault=noDefault; |
| } |
| |
| /* --------------------------------------------------------------- */ |
| /** Construct from dictionary PathMap. |
| */ |
| public PathMap(Map<String, ? extends O> m) |
| { |
| putAll(m); |
| } |
| |
| /* --------------------------------------------------------------- */ |
| /** Add a single path match to the PathMap. |
| * @param pathSpec The path specification, or comma separated list of |
| * path specifications. |
| * @param object The object the path maps to |
| */ |
| @Override |
| public O put(String pathSpec, O object) |
| { |
| if ("".equals(pathSpec.trim())) |
| { |
| MappedEntry<O> entry = new MappedEntry<>("",object); |
| entry.setMapped(""); |
| _exactMap.put("", entry); |
| return super.put("", object); |
| } |
| |
| StringTokenizer tok = new StringTokenizer(pathSpec,__pathSpecSeparators); |
| O old =null; |
| |
| while (tok.hasMoreTokens()) |
| { |
| String spec=tok.nextToken(); |
| |
| if (!spec.startsWith("/") && !spec.startsWith("*.")) |
| throw new IllegalArgumentException("PathSpec "+spec+". must start with '/' or '*.'"); |
| |
| old = super.put(spec,object); |
| |
| // Make entry that was just created. |
| MappedEntry<O> entry = new MappedEntry<>(spec,object); |
| |
| if (entry.getKey().equals(spec)) |
| { |
| if (spec.equals("/*")) |
| _prefixDefault=entry; |
| else if (spec.endsWith("/*")) |
| { |
| String mapped=spec.substring(0,spec.length()-2); |
| entry.setMapped(mapped); |
| while (!_prefixMap.put(mapped,entry)) |
| _prefixMap=new ArrayTernaryTrie<>((ArrayTernaryTrie<MappedEntry<O>>)_prefixMap,1.5); |
| } |
| else if (spec.startsWith("*.")) |
| { |
| String suffix=spec.substring(2); |
| while(!_suffixMap.put(suffix,entry)) |
| _suffixMap=new ArrayTernaryTrie<>((ArrayTernaryTrie<MappedEntry<O>>)_suffixMap,1.5); |
| } |
| else if (spec.equals(URIUtil.SLASH)) |
| { |
| if (_nodefault) |
| _exactMap.put(spec,entry); |
| else |
| { |
| _default=entry; |
| _defaultSingletonList=Collections.singletonList(_default); |
| } |
| } |
| else |
| { |
| entry.setMapped(spec); |
| _exactMap.put(spec,entry); |
| } |
| } |
| } |
| |
| return old; |
| } |
| |
| /* ------------------------------------------------------------ */ |
| /** Get object matched by the path. |
| * @param path the path. |
| * @return Best matched object or null. |
| */ |
| public O match(String path) |
| { |
| MappedEntry<O> entry = getMatch(path); |
| if (entry!=null) |
| return entry.getValue(); |
| return null; |
| } |
| |
| |
| /* --------------------------------------------------------------- */ |
| /** Get the entry mapped by the best specification. |
| * @param path the path. |
| * @return Map.Entry of the best matched or null. |
| */ |
| public MappedEntry<O> getMatch(String path) |
| { |
| if (path==null) |
| return null; |
| |
| int l=path.length(); |
| |
| MappedEntry<O> entry=null; |
| |
| //special case |
| if (l == 1 && path.charAt(0)=='/') |
| { |
| entry = _exactMap.get(""); |
| if (entry != null) |
| return entry; |
| } |
| |
| // try exact match |
| entry=_exactMap.get(path); |
| if (entry!=null) |
| return entry; |
| |
| // prefix search |
| int i=l; |
| final Trie<PathMap.MappedEntry<O>> prefix_map=_prefixMap; |
| while(i>=0) |
| { |
| entry=prefix_map.getBest(path,0,i); |
| if (entry==null) |
| break; |
| String key = entry.getKey(); |
| if (key.length()-2>=path.length() || path.charAt(key.length()-2)=='/') |
| return entry; |
| i=key.length()-3; |
| } |
| |
| // Prefix Default |
| if (_prefixDefault!=null) |
| return _prefixDefault; |
| |
| // Extension search |
| i=0; |
| final Trie<PathMap.MappedEntry<O>> suffix_map=_suffixMap; |
| while ((i=path.indexOf('.',i+1))>0) |
| { |
| entry=suffix_map.get(path,i+1,l-i-1); |
| if (entry!=null) |
| return entry; |
| } |
| |
| // Default |
| return _default; |
| } |
| |
| /* --------------------------------------------------------------- */ |
| /** Get all entries matched by the path. |
| * Best match first. |
| * @param path Path to match |
| * @return List of Map.Entry instances key=pathSpec |
| */ |
| public List<? extends Map.Entry<String,O>> getMatches(String path) |
| { |
| MappedEntry<O> entry; |
| List<MappedEntry<O>> entries=new ArrayList<>(); |
| |
| if (path==null) |
| return entries; |
| if (path.length()==0) |
| return _defaultSingletonList; |
| |
| // try exact match |
| entry=_exactMap.get(path); |
| if (entry!=null) |
| entries.add(entry); |
| |
| // prefix search |
| int l=path.length(); |
| int i=l; |
| final Trie<PathMap.MappedEntry<O>> prefix_map=_prefixMap; |
| while(i>=0) |
| { |
| entry=prefix_map.getBest(path,0,i); |
| if (entry==null) |
| break; |
| String key = entry.getKey(); |
| if (key.length()-2>=path.length() || path.charAt(key.length()-2)=='/') |
| entries.add(entry); |
| |
| i=key.length()-3; |
| } |
| |
| // Prefix Default |
| if (_prefixDefault!=null) |
| entries.add(_prefixDefault); |
| |
| // Extension search |
| i=0; |
| final Trie<PathMap.MappedEntry<O>> suffix_map=_suffixMap; |
| while ((i=path.indexOf('.',i+1))>0) |
| { |
| entry=suffix_map.get(path,i+1,l-i-1); |
| if (entry!=null) |
| entries.add(entry); |
| } |
| |
| // root match |
| if ("/".equals(path)) |
| { |
| entry=_exactMap.get(""); |
| if (entry!=null) |
| entries.add(entry); |
| } |
| |
| // Default |
| if (_default!=null) |
| entries.add(_default); |
| |
| return entries; |
| } |
| |
| |
| /* --------------------------------------------------------------- */ |
| /** Return whether the path matches any entries in the PathMap, |
| * excluding the default entry |
| * @param path Path to match |
| * @return Whether the PathMap contains any entries that match this |
| */ |
| public boolean containsMatch(String path) |
| { |
| MappedEntry<?> match = getMatch(path); |
| return match!=null && !match.equals(_default); |
| } |
| |
| /* --------------------------------------------------------------- */ |
| @Override |
| public O remove(Object pathSpec) |
| { |
| if (pathSpec!=null) |
| { |
| String spec=(String) pathSpec; |
| if (spec.equals("/*")) |
| _prefixDefault=null; |
| else if (spec.endsWith("/*")) |
| _prefixMap.remove(spec.substring(0,spec.length()-2)); |
| else if (spec.startsWith("*.")) |
| _suffixMap.remove(spec.substring(2)); |
| else if (spec.equals(URIUtil.SLASH)) |
| { |
| _default=null; |
| _defaultSingletonList=null; |
| } |
| else |
| _exactMap.remove(spec); |
| } |
| return super.remove(pathSpec); |
| } |
| |
| /* --------------------------------------------------------------- */ |
| @Override |
| public void clear() |
| { |
| _exactMap.clear(); |
| _prefixMap=new ArrayTernaryTrie<>(false); |
| _suffixMap=new ArrayTernaryTrie<>(false); |
| _default=null; |
| _defaultSingletonList=null; |
| _prefixDefault=null; |
| super.clear(); |
| } |
| |
| /* --------------------------------------------------------------- */ |
| /** |
| * @return true if match. |
| */ |
| public static boolean match(String pathSpec, String path) |
| throws IllegalArgumentException |
| { |
| return match(pathSpec, path, false); |
| } |
| |
| /* --------------------------------------------------------------- */ |
| /** |
| * @return true if match. |
| */ |
| public static boolean match(String pathSpec, String path, boolean noDefault) |
| throws IllegalArgumentException |
| { |
| if (pathSpec.length()==0) |
| return "/".equals(path); |
| |
| char c = pathSpec.charAt(0); |
| if (c=='/') |
| { |
| if (!noDefault && pathSpec.length()==1 || pathSpec.equals(path)) |
| return true; |
| |
| if(isPathWildcardMatch(pathSpec, path)) |
| return true; |
| } |
| else if (c=='*') |
| return path.regionMatches(path.length()-pathSpec.length()+1, |
| pathSpec,1,pathSpec.length()-1); |
| return false; |
| } |
| |
| /* --------------------------------------------------------------- */ |
| private static boolean isPathWildcardMatch(String pathSpec, String path) |
| { |
| // For a spec of "/foo/*" match "/foo" , "/foo/..." but not "/foobar" |
| int cpl=pathSpec.length()-2; |
| if (pathSpec.endsWith("/*") && path.regionMatches(0,pathSpec,0,cpl)) |
| { |
| if (path.length()==cpl || '/'==path.charAt(cpl)) |
| return true; |
| } |
| return false; |
| } |
| |
| |
| /* --------------------------------------------------------------- */ |
| /** Return the portion of a path that matches a path spec. |
| * @return null if no match at all. |
| */ |
| public static String pathMatch(String pathSpec, String path) |
| { |
| char c = pathSpec.charAt(0); |
| |
| if (c=='/') |
| { |
| if (pathSpec.length()==1) |
| return path; |
| |
| if (pathSpec.equals(path)) |
| return path; |
| |
| if (isPathWildcardMatch(pathSpec, path)) |
| return path.substring(0,pathSpec.length()-2); |
| } |
| else if (c=='*') |
| { |
| if (path.regionMatches(path.length()-(pathSpec.length()-1), |
| pathSpec,1,pathSpec.length()-1)) |
| return path; |
| } |
| return null; |
| } |
| |
| /* --------------------------------------------------------------- */ |
| /** Return the portion of a path that is after a path spec. |
| * @return The path info string |
| */ |
| public static String pathInfo(String pathSpec, String path) |
| { |
| if ("".equals(pathSpec)) |
| return path; //servlet 3 spec sec 12.2 will be '/' |
| |
| char c = pathSpec.charAt(0); |
| |
| if (c=='/') |
| { |
| if (pathSpec.length()==1) |
| return null; |
| |
| boolean wildcard = isPathWildcardMatch(pathSpec, path); |
| |
| // handle the case where pathSpec uses a wildcard and path info is "/*" |
| if (pathSpec.equals(path) && !wildcard) |
| return null; |
| |
| if (wildcard) |
| { |
| if (path.length()==pathSpec.length()-2) |
| return null; |
| return path.substring(pathSpec.length()-2); |
| } |
| } |
| return null; |
| } |
| |
| |
| /* ------------------------------------------------------------ */ |
| /** Relative path. |
| * @param base The base the path is relative to. |
| * @param pathSpec The spec of the path segment to ignore. |
| * @param path the additional path |
| * @return base plus path with pathspec removed |
| */ |
| public static String relativePath(String base, |
| String pathSpec, |
| String path ) |
| { |
| String info=pathInfo(pathSpec,path); |
| if (info==null) |
| info=path; |
| |
| if( info.startsWith( "./")) |
| info = info.substring( 2); |
| if( base.endsWith( URIUtil.SLASH)) |
| if( info.startsWith( URIUtil.SLASH)) |
| path = base + info.substring(1); |
| else |
| path = base + info; |
| else |
| if( info.startsWith( URIUtil.SLASH)) |
| path = base + info; |
| else |
| path = base + URIUtil.SLASH + info; |
| return path; |
| } |
| |
| /* ------------------------------------------------------------ */ |
| /* ------------------------------------------------------------ */ |
| /* ------------------------------------------------------------ */ |
| public static class MappedEntry<O> implements Map.Entry<String,O> |
| { |
| private final String key; |
| private final O value; |
| private String mapped; |
| |
| MappedEntry(String key, O value) |
| { |
| this.key=key; |
| this.value=value; |
| } |
| |
| @Override |
| public String getKey() |
| { |
| return key; |
| } |
| |
| @Override |
| public O getValue() |
| { |
| return value; |
| } |
| |
| @Override |
| public O setValue(O o) |
| { |
| throw new UnsupportedOperationException(); |
| } |
| |
| @Override |
| public String toString() |
| { |
| return key+"="+value; |
| } |
| |
| public String getMapped() |
| { |
| return mapped; |
| } |
| |
| void setMapped(String mapped) |
| { |
| this.mapped = mapped; |
| } |
| } |
| |
| public static class PathSet extends AbstractSet<String> implements Predicate<String> |
| { |
| private final PathMap<Boolean> _map = new PathMap<>(); |
| |
| @Override |
| public Iterator<String> iterator() |
| { |
| return _map.keySet().iterator(); |
| } |
| |
| @Override |
| public int size() |
| { |
| return _map.size(); |
| } |
| |
| @Override |
| public boolean add(String item) |
| { |
| return _map.put(item,Boolean.TRUE)==null; |
| } |
| |
| @Override |
| public boolean remove(Object item) |
| { |
| return _map.remove(item)!=null; |
| } |
| |
| @Override |
| public boolean contains(Object o) |
| { |
| return _map.containsKey(o); |
| } |
| |
| @Override |
| public boolean test(String s) |
| { |
| return _map.containsMatch(s); |
| } |
| |
| public boolean containsMatch(String s) |
| { |
| return _map.containsMatch(s); |
| } |
| public boolean matches(String item) |
| { |
| return _map.containsMatch(item); |
| } |
| } |
| } |