path_table/
lib.rs

1//! Generic types for path-based routing.
2
3use std::collections::HashMap;
4
5/// A generic path-based routing table, terminating with resources `R`.
6//
7// The implementation uses a very simple-minded tree structure. `PathTable` is a node,
8// with branches corresponding to the next path segment. For concrete segments, the
9// `next` table gives the available string matches. For the (at most one) wildcard match,
10// the `wildcard` field contains the branch.
11//
12// If the current path itself is a route, the `accept` field says what resource it contains.
13#[derive(Clone)]
14pub struct PathTable<R> {
15  accept: Option<R>,
16  next: HashMap<String, PathTable<R>>,
17  wildcard: Option<Box<Wildcard<R>>>,
18}
19
20#[derive(Copy, Clone, PartialEq)]
21enum WildcardKind {
22  Segment,
23  CatchAll,
24}
25
26impl std::fmt::Display for WildcardKind {
27  fn fmt(&self, fmt: &mut std::fmt::Formatter) -> std::fmt::Result {
28    match self {
29      WildcardKind::Segment => Ok(()),
30      WildcardKind::CatchAll => write!(fmt, "*"),
31    }
32  }
33}
34
35#[derive(Clone)]
36struct Wildcard<R> {
37  name: String,
38  count_mod: WildcardKind,
39  table: PathTable<R>,
40}
41
42/// For a successful match, this structure says how any wildcard segments were matched.
43#[derive(Debug)]
44pub struct RouteMatch<'a> {
45  /// Wildcard matches in the order they appeared in the path.
46  pub vec: Vec<&'a str>,
47  /// Named wildcard matches, indexed by name.
48  pub map: HashMap<&'a str, &'a str>,
49}
50
51impl<R> std::fmt::Debug for PathTable<R> {
52  fn fmt(&self, fmt: &mut std::fmt::Formatter) -> std::fmt::Result {
53    struct Children<'a, R>(
54      &'a HashMap<String, PathTable<R>>,
55      Option<&'a Wildcard<R>>,
56    );
57    impl<'a, R> std::fmt::Debug for Children<'a, R> {
58      fn fmt(&self, fmt: &mut std::fmt::Formatter) -> std::fmt::Result {
59        let mut dbg = fmt.debug_map();
60        dbg.entries(self.0.iter());
61        if let Some(wildcard) = self.1 {
62          dbg.entry(
63            &format_args!("{{{}}}{}", wildcard.name, wildcard.count_mod),
64            &wildcard.table,
65          );
66        }
67        dbg.finish()
68      }
69    }
70
71    fmt
72      .debug_struct("PathTable")
73      .field(
74        "resource",
75        &format_args!(
76          "{}",
77          if self.accept.is_some() {
78            "Some"
79          } else {
80            "None"
81          }
82        ),
83      )
84      .field(
85        "children",
86        &Children(&self.next, self.wildcard.as_ref().map(|x| &**x)),
87      )
88      .finish()
89  }
90}
91
92impl<R> Default for PathTable<R> {
93  fn default() -> Self {
94    PathTable::new()
95  }
96}
97
98impl<R> PathTable<R> {
99  /// Create an empty routing table.
100  pub fn new() -> PathTable<R> {
101    PathTable {
102      accept: None,
103      next: HashMap::new(),
104      wildcard: None,
105    }
106  }
107
108  /// Get the resource of current path.
109  pub fn resource(&self) -> Option<&R> {
110    self.accept.as_ref()
111  }
112
113  /// Retrieve a mutable reference of the resource.
114  pub fn resource_mut(&mut self) -> &mut Option<R> {
115    &mut self.accept
116  }
117
118  /// Return an iterator of all resources.
119  pub fn iter(&self) -> Resources<R> {
120    Resources { stack: vec![self] }
121  }
122
123  /// Return a mutable iterator of all resources.
124  pub fn iter_mut(&mut self) -> ResourcesMut<R> {
125    ResourcesMut { stack: vec![self] }
126  }
127
128  /// Determine which resource, if any, the concrete `path` should be routed to.
129  pub fn route<'a>(&'a self, path: &'a str) -> Option<(&'a R, RouteMatch<'a>)> {
130    let mut table = self;
131    let mut params = Vec::new();
132    let mut param_map = HashMap::new();
133
134    // Find all segments with their indices.
135    let segment_iter = path
136      .match_indices('/')
137      .chain(std::iter::once((path.len(), "")))
138      .scan(0usize, |prev_idx, (idx, _)| {
139        let starts_at = *prev_idx;
140        let segment = &path[starts_at..idx];
141        *prev_idx = idx + 1;
142        Some((starts_at, segment))
143      });
144
145    for (starts_at, mut segment) in segment_iter {
146      if segment.is_empty() {
147        continue;
148      }
149
150      if let Some(next_table) = table.next.get(segment) {
151        table = next_table;
152      } else if let Some(wildcard) = &table.wildcard {
153        let last = if wildcard.count_mod == WildcardKind::CatchAll {
154          segment = &path[starts_at..];
155          true
156        } else {
157          false
158        };
159
160        params.push(segment);
161
162        if !wildcard.name.is_empty() {
163          param_map.insert(&*wildcard.name, segment);
164        }
165
166        table = &wildcard.table;
167
168        if last {
169          break;
170        }
171      } else {
172        return None;
173      }
174    }
175
176    if table.accept.is_none() {
177      if let Some(wildcard) = &table.wildcard {
178        if wildcard.count_mod == WildcardKind::CatchAll {
179          params.push("");
180
181          if !wildcard.name.is_empty() {
182            param_map.insert(&*wildcard.name, "");
183          }
184
185          table = &wildcard.table;
186        }
187      }
188    }
189
190    table.accept.as_ref().map(|res| {
191      (
192        res,
193        RouteMatch {
194          vec: params,
195          map: param_map,
196        },
197      )
198    })
199  }
200
201  fn wildcard_mut(&mut self) -> Option<&mut Wildcard<R>> {
202    self.wildcard.as_mut().map(|b| &mut **b)
203  }
204
205  /// Return the table of the given routing path (which may contain wildcards).
206  ///
207  /// If it doesn't already exist, this will make a new one.
208  pub fn setup_table(&mut self, path: &str) -> &mut PathTable<R> {
209    let mut table = self;
210    let mut forbid_next = false;
211    for segment in path.split('/') {
212      if segment.is_empty() {
213        continue;
214      }
215
216      if forbid_next {
217        panic!("No segments are allowed after wildcard with `*` modifier");
218      }
219
220      let wildcard_opt = if segment.starts_with('{') {
221        if segment.ends_with('}') {
222          Some((&segment[1..segment.len() - 1], WildcardKind::Segment))
223        } else if segment.ends_with("}*") {
224          Some((&segment[1..segment.len() - 2], WildcardKind::CatchAll))
225        } else {
226          None
227        }
228      } else if segment == "*" {
229        Some(("", WildcardKind::CatchAll))
230      } else {
231        None
232      };
233
234      if let Some((name, count_mod)) = wildcard_opt {
235        if count_mod != WildcardKind::Segment {
236          forbid_next = true;
237        }
238
239        if table.wildcard.is_none() {
240          table.wildcard = Some(Box::new(Wildcard {
241            name: name.to_string(),
242            count_mod,
243            table: PathTable::new(),
244          }));
245        }
246
247        match table.wildcard_mut().unwrap() {
248          Wildcard {
249            name: n,
250            count_mod: c,
251            ..
252          } if name != n || count_mod != *c => {
253            panic!(
254                            "Route {} segment `{{{}}}{}` conflicts with existing wildcard segment `{{{}}}{}`",
255                            path, name, count_mod, n, c
256                        );
257          }
258          Wildcard { table: t, .. } => {
259            table = t;
260          }
261        }
262      } else {
263        table = table
264          .next
265          .entry(segment.to_string())
266          .or_insert_with(PathTable::new);
267      }
268    }
269
270    table
271  }
272}
273
274impl<R: Default> PathTable<R> {
275  /// Add or access a new resource at the given routing path (which may contain wildcards).
276  pub fn setup(&mut self, path: &str) -> &mut R {
277    let table = self.setup_table(path);
278
279    if table.accept.is_none() {
280      table.accept = Some(R::default())
281    }
282
283    table.accept.as_mut().unwrap()
284  }
285}
286
287/// An iterator over the resources of a `PathTable`.
288pub struct Resources<'a, R> {
289  stack: Vec<&'a PathTable<R>>,
290}
291
292impl<'a, R> Iterator for Resources<'a, R> {
293  type Item = &'a R;
294
295  fn next(&mut self) -> Option<&'a R> {
296    while let Some(table) = self.stack.pop() {
297      self.stack.extend(table.next.values());
298      if let Some(wildcard) = table.wildcard.as_ref() {
299        self.stack.push(&wildcard.table);
300      }
301      if let Some(res) = &table.accept {
302        return Some(res);
303      }
304    }
305    None
306  }
307}
308
309/// A mutable iterator over the resources of a `PathTable`.
310pub struct ResourcesMut<'a, R> {
311  stack: Vec<&'a mut PathTable<R>>,
312}
313
314impl<'a, R> Iterator for ResourcesMut<'a, R> {
315  type Item = &'a mut R;
316
317  fn next(&mut self) -> Option<&'a mut R> {
318    while let Some(table) = self.stack.pop() {
319      self.stack.extend(table.next.values_mut());
320      if let Some(wildcard) = table.wildcard.as_mut() {
321        self.stack.push(&mut wildcard.table);
322      }
323      if let Some(res) = &mut table.accept {
324        return Some(res);
325      }
326    }
327    None
328  }
329}
330
331#[cfg(test)]
332mod test {
333  use std::collections::HashSet;
334
335  use super::*;
336
337  #[test]
338  fn empty_route_no_matches() {
339    let table: PathTable<()> = PathTable::new();
340
341    assert!(table.route("").is_none());
342    assert!(table.route("/").is_none());
343    assert!(table.route("//").is_none());
344    assert!(table.route("foo").is_none());
345    assert!(table.route("foo/bar").is_none());
346  }
347
348  #[test]
349  fn root_matches() {
350    let mut table: PathTable<()> = PathTable::new();
351    table.setup("/");
352
353    assert!(table.route("").is_some());
354    assert!(table.route("/").is_some());
355    assert!(table.route("//").is_some());
356
357    assert!(table.route("foo").is_none());
358    assert!(table.route("foo/bar").is_none());
359  }
360
361  #[test]
362  fn one_fixed_segment_matches() {
363    let mut table: PathTable<()> = PathTable::new();
364    table.setup("foo");
365
366    assert!(table.route("").is_none());
367    assert!(table.route("/").is_none());
368    assert!(table.route("//").is_none());
369
370    assert!(table.route("foo").is_some());
371    assert!(table.route("/foo").is_some());
372    assert!(table.route("foo/").is_some());
373    assert!(table.route("/foo/").is_some());
374    assert!(table.route("//foo//").is_some());
375
376    assert!(table.route("foo/bar").is_none());
377    assert!(table.route("fo/o").is_none());
378  }
379
380  #[test]
381  fn multiple_fixed_segment_matches() {
382    let mut table: PathTable<()> = PathTable::new();
383    table.setup("foo");
384    table.setup("bar");
385
386    assert!(table.route("").is_none());
387    assert!(table.route("/").is_none());
388    assert!(table.route("//").is_none());
389
390    assert!(table.route("foo").is_some());
391    assert!(table.route("bar").is_some());
392
393    assert!(table.route("foo/bar").is_none());
394    assert!(table.route("bar/foo").is_none())
395  }
396
397  #[test]
398  fn nested_fixed_segment_matches() {
399    let mut table: PathTable<()> = PathTable::new();
400    table.setup("foo/bar");
401
402    assert!(table.route("").is_none());
403    assert!(table.route("foo").is_none());
404
405    assert!(table.route("foo/bar").is_some());
406  }
407
408  #[test]
409  fn multiple_nested_fixed_segment_matches() {
410    let mut table: PathTable<()> = PathTable::new();
411    table.setup("foo/bar");
412    table.setup("baz");
413    table.setup("quux/twiddle/twibble");
414
415    assert!(table.route("").is_none());
416    assert!(table.route("foo").is_none());
417    assert!(table.route("quux").is_none());
418
419    assert!(table.route("foo/bar").is_some());
420    assert!(table.route("baz").is_some());
421    assert!(table.route("quux/twiddle/twibble").is_some());
422  }
423
424  #[test]
425  fn overlap_nested_fixed_segment_matches() {
426    let mut table: PathTable<i32> = PathTable::new();
427    *table.setup("") = 0;
428    *table.setup("foo") = 1;
429    *table.setup("foo/bar") = 2;
430
431    assert_eq!(*table.route("/").unwrap().0, 0);
432    assert_eq!(*table.route("/foo").unwrap().0, 1);
433    assert_eq!(*table.route("/foo/bar").unwrap().0, 2);
434
435    assert_eq!(*table.route("").unwrap().0, 0);
436    assert_eq!(*table.route("foo").unwrap().0, 1);
437    assert_eq!(*table.route("foo/bar").unwrap().0, 2);
438  }
439
440  #[test]
441  fn wildcard_matches() {
442    let mut table: PathTable<()> = PathTable::new();
443    table.setup("{}");
444
445    assert!(table.route("").is_none());
446    assert!(table.route("foo/bar").is_none());
447
448    assert!(table.route("foo").is_some());
449    assert!(table.route("bar").is_some());
450  }
451
452  #[test]
453  fn nested_wildcard_matches() {
454    let mut table: PathTable<()> = PathTable::new();
455    table.setup("{}/{}");
456
457    assert!(table.route("").is_none());
458    assert!(table.route("foo").is_none());
459
460    assert!(table.route("foo/bar").is_some());
461    assert_eq!(&table.route("foo/bar").unwrap().1.vec, &["foo", "bar"]);
462    assert!(table.route("foo/bar").unwrap().1.map.is_empty());
463  }
464
465  #[test]
466  fn mixed_route() {
467    let mut table: PathTable<()> = PathTable::new();
468    table.setup("foo/{}/bar");
469
470    assert!(table.route("").is_none());
471    assert!(table.route("foo").is_none());
472    assert!(table.route("foo/bar").is_none());
473    assert!(table.route("foo/bar/baz").is_none());
474
475    assert!(table.route("foo/baz/bar").is_some());
476    assert_eq!(&table.route("foo/baz/bar").unwrap().1.vec, &["baz"]);
477  }
478
479  #[test]
480  fn wildcard_fallback() {
481    let mut table: PathTable<i32> = PathTable::new();
482    *table.setup("foo") = 0;
483    *table.setup("foo/bar") = 1;
484    *table.setup("foo/{}/bar") = 2;
485
486    assert!(table.route("").is_none());
487    assert!(table.route("foo/bar/baz").is_none());
488    assert!(table.route("foo/bar/bar").is_none());
489
490    assert_eq!(*table.route("foo").unwrap().0, 0);
491    assert_eq!(*table.route("foo/bar").unwrap().0, 1);
492    assert_eq!(*table.route("foo/baz/bar").unwrap().0, 2);
493  }
494
495  #[test]
496  fn named_wildcard() {
497    let mut table: PathTable<()> = PathTable::new();
498    *table.setup("foo/{foo}");
499    *table.setup("foo/{foo}/{bar}");
500    *table.setup("{}");
501
502    let (_, params) = table.route("foo/a").unwrap();
503    assert_eq!(params.vec, &["a"]);
504    assert_eq!(params.map, [("foo", "a")].iter().cloned().collect());
505
506    let (_, params) = table.route("foo/a/b").unwrap();
507    assert_eq!(params.vec, &["a", "b"]);
508    assert_eq!(
509      params.map,
510      [("foo", "a"), ("bar", "b")].iter().cloned().collect()
511    );
512
513    let (_, params) = table.route("c").unwrap();
514    assert_eq!(params.vec, &["c"]);
515    assert!(params.map.is_empty());
516  }
517
518  #[test]
519  fn wildcard_count_mod() {
520    let mut table: PathTable<usize> = PathTable::new();
521    *table.setup("foo/{foo}*") = 0;
522    *table.setup("bar/{}*") = 1;
523    *table.setup("baz/*") = 2;
524    *table.setup("foo/bar") = 3;
525
526    let (&id, params) = table.route("foo/a/b").unwrap();
527    assert_eq!(id, 0);
528    assert_eq!(params.vec, &["a/b"]);
529    assert_eq!(params.map, [("foo", "a/b")].iter().cloned().collect());
530
531    let (&id, params) = table.route("bar/a/b").unwrap();
532    assert_eq!(id, 1);
533    assert_eq!(params.vec, &["a/b"]);
534    assert!(params.map.is_empty());
535
536    let (&id, params) = table.route("baz/a/b").unwrap();
537    assert_eq!(id, 2);
538    assert_eq!(params.vec, &["a/b"]);
539    assert!(params.map.is_empty());
540
541    let (&id, params) = table.route("foo/bar").unwrap();
542    assert_eq!(id, 3);
543    assert!(params.vec.is_empty());
544    assert!(params.map.is_empty());
545  }
546
547  #[test]
548  #[should_panic]
549  fn conflicting_wildcard_name_fails() {
550    let mut table: PathTable<()> = PathTable::new();
551    *table.setup("foo/{foo}");
552    *table.setup("foo/{bar}");
553  }
554
555  #[test]
556  #[should_panic]
557  fn conflicting_wildcard_modifier_fails() {
558    let mut table: PathTable<()> = PathTable::new();
559    table.setup("foo/{foo}*");
560    table.setup("foo/{foo}");
561  }
562
563  #[test]
564  fn iter() {
565    let mut table: PathTable<usize> = PathTable::new();
566    *table.setup("foo") = 1;
567    *table.setup("foo/bar") = 2;
568    *table.setup("{}") = 3;
569
570    let set: HashSet<_> = table.iter().cloned().collect();
571    assert_eq!(set, [1, 2, 3].iter().cloned().collect());
572  }
573
574  #[test]
575  fn iter_mut() {
576    let mut table: PathTable<usize> = PathTable::new();
577    *table.setup("foo") = 1;
578    *table.setup("foo/bar") = 2;
579    *table.setup("{}") = 3;
580
581    for res in table.iter_mut() {
582      *res -= 1;
583    }
584
585    let set: HashSet<_> = table.iter().cloned().collect();
586    assert_eq!(set, [0, 1, 2].iter().cloned().collect());
587  }
588}
path_table/lib.rs

path_table/
lib.rs
