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