lib/jetty/org/eclipse/jetty/http/PathMap.java

   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
  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;
  35
  36 /* ------------------------------------------------------------ */
  37 /** URI path map to Object.
  38  * This mapping implements the path specification recommended
  39  * in the 2.2 Servlet API.
  40  *
  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
  47  * </PRE>
  48  * Matching is performed in the following order <NL>
  49  * <LI>Exact match.
  50  * <LI>Longest prefix match.
  51  * <LI>Longest suffix match.
  52  * <LI>default.
  53  * </NL>
  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)
  58  * <P>
  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.
  62  * <P>
  63  * This class is not synchronized.  If concurrent modifications are
  64  * possible then it should be synchronized at a higher level.
  65  *
  66  *
  67  */
  68 public class PathMap<O> extends HashMap<String,O>
  69 {
  70     /* ------------------------------------------------------------ */
  71     private static String __pathSpecSeparators = ":,";
  72
  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.
  78      * @param s separators
  79      */
  80     public static void setPathSpecSeparators(String s)
  81     {
  82         __pathSpecSeparators=s;
  83     }
  84
  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<>();
  89
  90     List<MappedEntry<O>> _defaultSingletonList=null;
  91     MappedEntry<O> _prefixDefault=null;
  92     MappedEntry<O> _default=null;
  93     boolean _nodefault=false;
  94
  95     /* --------------------------------------------------------------- */
  96     public PathMap()
  97     {
  98         this(11);
  99     }
 100
 101     /* --------------------------------------------------------------- */
 102     public PathMap(boolean noDefault)
 103     {
 104         this(11, noDefault);
 105     }
 106
 107     /* --------------------------------------------------------------- */
 108     public PathMap(int capacity)
 109     {
 110         this(capacity, false);
 111     }
 112
 113     /* --------------------------------------------------------------- */
 114     private PathMap(int capacity, boolean noDefault)
 115     {
 116         super(capacity);
 117         _nodefault=noDefault;
 118     }
 119
 120     /* --------------------------------------------------------------- */
 121     /** Construct from dictionary PathMap.
 122      */
 123     public PathMap(Map<String, ? extends O> m)
 124     {
 125         putAll(m);
 126     }
 127
 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
 133      */
 134     @Override
 135     public O put(String pathSpec, O object)
 136     {
 137         if ("".equals(pathSpec.trim()))
 138         {
 139             MappedEntry<O> entry = new MappedEntry<>("",object);
 140             entry.setMapped("");
 141             _exactMap.put("", entry);
 142             return super.put("", object);
 143         }
 144
 145         StringTokenizer tok = new StringTokenizer(pathSpec,__pathSpecSeparators);
 146         O old =null;
 147
 148         while (tok.hasMoreTokens())
 149         {
 150             String spec=tok.nextToken();
 151
 152             if (!spec.startsWith("/") && !spec.startsWith("*."))
 153                 throw new IllegalArgumentException("PathSpec "+spec+". must start with '/' or '*.'");
 154
 155             old = super.put(spec,object);
 156
 157             // Make entry that was just created.
 158             MappedEntry<O> entry = new MappedEntry<>(spec,object);
 159
 160             if (entry.getKey().equals(spec))
 161             {
 162                 if (spec.equals("/*"))
 163                     _prefixDefault=entry;
 164                 else if (spec.endsWith("/*"))
 165                 {
 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);
 170                 }
 171                 else if (spec.startsWith("*."))
 172                 {
 173                     String suffix=spec.substring(2);
 174                     while(!_suffixMap.put(suffix,entry))
 175                         _suffixMap=new ArrayTernaryTrie<>((ArrayTernaryTrie<MappedEntry<O>>)_suffixMap,1.5);
 176                 }
 177                 else if (spec.equals(URIUtil.SLASH))
 178                 {
 179                     if (_nodefault)
 180                         _exactMap.put(spec,entry);
 181                     else
 182                     {
 183                         _default=entry;
 184                         _defaultSingletonList=Collections.singletonList(_default);
 185                     }
 186                 }
 187                 else
 188                 {
 189                     entry.setMapped(spec);
 190                     _exactMap.put(spec,entry);
 191                 }
 192             }
 193         }
 194
 195         return old;
 196     }
 197
 198     /* ------------------------------------------------------------ */
 199     /** Get object matched by the path.
 200      * @param path the path.
 201      * @return Best matched object or null.
 202      */
 203     public O match(String path)
 204     {
 205         MappedEntry<O> entry = getMatch(path);
 206         if (entry!=null)
 207             return entry.getValue();
 208         return null;
 209     }
 210
 211
 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.
 216      */
 217     public MappedEntry<O> getMatch(String path)
 218     {
 219         if (path==null)
 220             return null;
 221
 222         int l=path.length();
 223
 224         MappedEntry<O> entry=null;
 225
 226         //special case
 227         if (l == 1 && path.charAt(0)=='/')
 228         {
 229             entry = _exactMap.get("");
 230             if (entry != null)
 231                 return entry;
 232         }
 233
 234         // try exact match
 235         entry=_exactMap.get(path);
 236         if (entry!=null)
 237             return entry;
 238
 239         // prefix search
 240         int i=l;
 241         final Trie<PathMap.MappedEntry<O>> prefix_map=_prefixMap;
 242         while(i>=0)
 243         {
 244             entry=prefix_map.getBest(path,0,i);
 245             if (entry==null)
 246                 break;
 247             String key = entry.getKey();
 248             if (key.length()-2>=path.length() || path.charAt(key.length()-2)=='/')
 249                 return entry;
 250             i=key.length()-3;
 251         }
 252
 253         // Prefix Default
 254         if (_prefixDefault!=null)
 255             return _prefixDefault;
 256
 257         // Extension search
 258         i=0;
 259         final Trie<PathMap.MappedEntry<O>> suffix_map=_suffixMap;
 260         while ((i=path.indexOf('.',i+1))>0)
 261         {
 262             entry=suffix_map.get(path,i+1,l-i-1);
 263             if (entry!=null)
 264                 return entry;
 265         }
 266
 267         // Default
 268         return _default;
 269     }
 270
 271     /* --------------------------------------------------------------- */
 272     /** Get all entries matched by the path.
 273      * Best match first.
 274      * @param path Path to match
 275      * @return List of Map.Entry instances key=pathSpec
 276      */
 277     public List<? extends Map.Entry<String,O>> getMatches(String path)
 278     {
 279         MappedEntry<O> entry;
 280         List<MappedEntry<O>> entries=new ArrayList<>();
 281
 282         if (path==null)
 283             return entries;
 284         if (path.length()==0)
 285             return _defaultSingletonList;
 286
 287         // try exact match
 288         entry=_exactMap.get(path);
 289         if (entry!=null)
 290             entries.add(entry);
 291
 292         // prefix search
 293         int l=path.length();
 294         int i=l;
 295         final Trie<PathMap.MappedEntry<O>> prefix_map=_prefixMap;
 296         while(i>=0)
 297         {
 298             entry=prefix_map.getBest(path,0,i);
 299             if (entry==null)
 300                 break;
 301             String key = entry.getKey();
 302             if (key.length()-2>=path.length() || path.charAt(key.length()-2)=='/')
 303                 entries.add(entry);
 304
 305             i=key.length()-3;
 306         }
 307
 308         // Prefix Default
 309         if (_prefixDefault!=null)
 310             entries.add(_prefixDefault);
 311
 312         // Extension search
 313         i=0;
 314         final Trie<PathMap.MappedEntry<O>> suffix_map=_suffixMap;
 315         while ((i=path.indexOf('.',i+1))>0)
 316         {
 317             entry=suffix_map.get(path,i+1,l-i-1);
 318             if (entry!=null)
 319                 entries.add(entry);
 320         }
 321
 322         // root match
 323         if ("/".equals(path))
 324         {
 325             entry=_exactMap.get("");
 326             if (entry!=null)
 327                 entries.add(entry);
 328         }
 329
 330         // Default
 331         if (_default!=null)
 332             entries.add(_default);
 333
 334         return entries;
 335     }
 336
 337
 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
 343      */
 344     public boolean containsMatch(String path)
 345     {
 346         MappedEntry<?> match = getMatch(path);
 347         return match!=null && !match.equals(_default);
 348     }
 349
 350     /* --------------------------------------------------------------- */
 351     @Override
 352     public O remove(Object pathSpec)
 353     {
 354         if (pathSpec!=null)
 355         {
 356             String spec=(String) pathSpec;
 357             if (spec.equals("/*"))
 358                 _prefixDefault=null;
 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))
 364             {
 365                 _default=null;
 366                 _defaultSingletonList=null;
 367             }
 368             else
 369                 _exactMap.remove(spec);
 370         }
 371         return super.remove(pathSpec);
 372     }
 373
 374     /* --------------------------------------------------------------- */
 375     @Override
 376     public void clear()
 377     {
 378         _exactMap.clear();
 379         _prefixMap=new ArrayTernaryTrie<>(false);
 380         _suffixMap=new ArrayTernaryTrie<>(false);
 381         _default=null;
 382         _defaultSingletonList=null;
 383         _prefixDefault=null;
 384         super.clear();
 385     }
 386
 387     /* --------------------------------------------------------------- */
 388     /**
 389      * @return true if match.
 390      */
 391     public static boolean match(String pathSpec, String path)
 392         throws IllegalArgumentException
 393     {
 394         return match(pathSpec, path, false);
 395     }
 396
 397     /* --------------------------------------------------------------- */
 398     /**
 399      * @return true if match.
 400      */
 401     public static boolean match(String pathSpec, String path, boolean noDefault)
 402         throws IllegalArgumentException
 403     {
 404         if (pathSpec.length()==0)
 405             return "/".equals(path);
 406
 407         char c = pathSpec.charAt(0);
 408         if (c=='/')
 409         {
 410             if (!noDefault && pathSpec.length()==1 || pathSpec.equals(path))
 411                 return true;
 412
 413             if(isPathWildcardMatch(pathSpec, path))
 414                 return true;
 415         }
 416         else if (c=='*')
 417             return path.regionMatches(path.length()-pathSpec.length()+1,
 418                     pathSpec,1,pathSpec.length()-1);
 419         return false;
 420     }
 421
 422     /* --------------------------------------------------------------- */
 423     private static boolean isPathWildcardMatch(String pathSpec, String path)
 424     {
 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))
 428         {
 429             if (path.length()==cpl || '/'==path.charAt(cpl))
 430                 return true;
 431         }
 432         return false;
 433     }
 434
 435
 436     /* --------------------------------------------------------------- */
 437     /** Return the portion of a path that matches a path spec.
 438      * @return null if no match at all.
 439      */
 440     public static String pathMatch(String pathSpec, String path)
 441     {
 442         char c = pathSpec.charAt(0);
 443
 444         if (c=='/')
 445         {
 446             if (pathSpec.length()==1)
 447                 return path;
 448
 449             if (pathSpec.equals(path))
 450                 return path;
 451
 452             if (isPathWildcardMatch(pathSpec, path))
 453                 return path.substring(0,pathSpec.length()-2);
 454         }
 455         else if (c=='*')
 456         {
 457             if (path.regionMatches(path.length()-(pathSpec.length()-1),
 458                     pathSpec,1,pathSpec.length()-1))
 459                 return path;
 460         }
 461         return null;
 462     }
 463
 464     /* --------------------------------------------------------------- */
 465     /** Return the portion of a path that is after a path spec.
 466      * @return The path info string
 467      */
 468     public static String pathInfo(String pathSpec, String path)
 469     {
 470         if ("".equals(pathSpec))
 471             return path; //servlet 3 spec sec 12.2 will be '/'
 472
 473         char c = pathSpec.charAt(0);
 474
 475         if (c=='/')
 476         {
 477             if (pathSpec.length()==1)
 478                 return null;
 479
 480             boolean wildcard = isPathWildcardMatch(pathSpec, path);
 481
 482             // handle the case where pathSpec uses a wildcard and path info is "/*"
 483             if (pathSpec.equals(path) && !wildcard)
 484                 return null;
 485
 486             if (wildcard)
 487             {
 488                 if (path.length()==pathSpec.length()-2)
 489                     return null;
 490                 return path.substring(pathSpec.length()-2);
 491             }
 492         }
 493         return null;
 494     }
 495
 496
 497     /* ------------------------------------------------------------ */
 498     /** Relative path.
 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
 503      */
 504     public static String relativePath(String base,
 505             String pathSpec,
 506             String path )
 507     {
 508         String info=pathInfo(pathSpec,path);
 509         if (info==null)
 510             info=path;
 511
 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);
 517             else
 518                 path = base + info;
 519         else
 520             if( info.startsWith( URIUtil.SLASH))
 521                 path = base + info;
 522             else
 523                 path = base + URIUtil.SLASH + info;
 524         return path;
 525     }
 526
 527     /* ------------------------------------------------------------ */
 528     /* ------------------------------------------------------------ */
 529     /* ------------------------------------------------------------ */
 530     public static class MappedEntry<O> implements Map.Entry<String,O>
 531     {
 532         private final String key;
 533         private final O value;
 534         private String mapped;
 535
 536         MappedEntry(String key, O value)
 537         {
 538             this.key=key;
 539             this.value=value;
 540         }
 541
 542         @Override
 543         public String getKey()
 544         {
 545             return key;
 546         }
 547
 548         @Override
 549         public O getValue()
 550         {
 551             return value;
 552         }
 553
 554         @Override
 555         public O setValue(O o)
 556         {
 557             throw new UnsupportedOperationException();
 558         }
 559
 560         @Override
 561         public String toString()
 562         {
 563             return key+"="+value;
 564         }
 565
 566         public String getMapped()
 567         {
 568             return mapped;
 569         }
 570
 571         void setMapped(String mapped)
 572         {
 573             this.mapped = mapped;
 574         }
 575     }
 576
 577     public static class PathSet extends AbstractSet<String> implements Predicate<String>
 578     {
 579         private final PathMap<Boolean> _map = new PathMap<>();
 580
 581         @Override
 582         public Iterator<String> iterator()
 583         {
 584             return _map.keySet().iterator();
 585         }
 586
 587         @Override
 588         public int size()
 589         {
 590             return _map.size();
 591         }
 592
 593         @Override
 594         public boolean add(String item)
 595         {
 596             return _map.put(item,Boolean.TRUE)==null;
 597         }
 598
 599         @Override
 600         public boolean remove(Object item)
 601         {
 602             return _map.remove(item)!=null;
 603         }
 604
 605         @Override
 606         public boolean contains(Object o)
 607         {
 608             return _map.containsKey(o);
 609         }
 610
 611         @Override
 612         public boolean test(String s)
 613         {
 614             return _map.containsMatch(s);
 615         }
 616
 617         public boolean containsMatch(String s)
 618         {
 619             return _map.containsMatch(s);
 620         }
 621         public boolean matches(String item)
 622         {
 623             return _map.containsMatch(item);
 624         }
 625     }
 626 }