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