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