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