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

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