path_tree/
lib.rs

1//! path-tree is a lightweight high performance HTTP request router for Rust.
2//!
3//! # Example
4//!
5//! ```
6//! use path_tree::PathTree;
7//!
8//! /*
9//! / •0
10//! ├── api/
11//! │   └── + •13
12//! ├── login •1
13//! ├── public/
14//! │   └── ** •7
15//! ├── s
16//! │   ├── ettings •3
17//! │   │   └── /
18//! │   │       └── : •4
19//! │   └── ignup •2
20//! └── : •5
21//!     └── /
22//!         └── : •6
23//!             └── /
24//!                 ├── actions/
25//!                 │   └── :
26//!                 │       └── \:
27//!                 │           └── : •10
28//!                 ├── releases/download/
29//!                 │   └── :
30//!                 │       └── /
31//!                 │           └── :
32//!                 │               └── .
33//!                 │                   └── : •8
34//!                 ├── tags/
35//!                 │   └── :
36//!                 │       └── -
37//!                 │           └── :
38//!                 │               └── -
39//!                 │                   └── : •9
40//!                 ├── : •11
41//!                 └── ** •12
42//! */
43//! let mut tree = PathTree::new();
44//!
45//! tree.insert("/", 0);
46//! tree.insert("/login", 1);
47//! tree.insert("/signup", 2);
48//! tree.insert("/settings", 3);
49//! tree.insert("/settings/:page", 4);
50//! tree.insert("/:user", 5);
51//! tree.insert("/:user/:repo", 6);
52//! tree.insert("/public/:any*", 7);
53//! tree.insert("/:org/:repo/releases/download/:tag/:filename.:ext", 8);
54//! tree.insert("/:org/:repo/tags/:day-:month-:year", 9);
55//! tree.insert("/:org/:repo/actions/:name\\::verb", 10);
56//! tree.insert("/:org/:repo/:page", 11);
57//! tree.insert("/:org/:repo/*", 12);
58//! tree.insert("/api/+", 13);
59//!
60//! let (h, p) = tree.find("/").unwrap();
61//! assert_eq!(h, &0);
62//! assert_eq!(p.params(), vec![]);
63//!
64//! let (h, p) = tree.find("/login").unwrap();
65//! assert_eq!(h, &1);
66//! assert_eq!(p.params(), vec![]);
67//!
68//! let (h, p) = tree.find("/settings/admin").unwrap();
69//! assert_eq!(h, &4);
70//! assert_eq!(p.params(), vec![("page", "admin")]);
71//!
72//! let (h, p) = tree.find("/viz-rs").unwrap();
73//! assert_eq!(h, &5);
74//! assert_eq!(p.params(), vec![("user", "viz-rs")]);
75//!
76//! let (h, p) = tree.find("/viz-rs/path-tree").unwrap();
77//! assert_eq!(h, &6);
78//! assert_eq!(p.params(), vec![("user", "viz-rs"), ("repo", "path-tree")]);
79//!
80//! let (h, p) = tree.find("/rust-lang/rust-analyzer/releases/download/2022-09-12/rust-analyzer-aarch64-apple-darwin.gz").unwrap();
81//! assert_eq!(h, &8);
82//! assert_eq!(
83//!     p.params(),
84//!     vec![
85//!         ("org", "rust-lang"),
86//!         ("repo", "rust-analyzer"),
87//!         ("tag", "2022-09-12"),
88//!         ("filename", "rust-analyzer-aarch64-apple-darwin"),
89//!         ("ext", "gz")
90//!     ]
91//! );
92//!
93//! let (h, p) = tree.find("/rust-lang/rust-analyzer/tags/2022-09-12").unwrap();
94//! assert_eq!(h, &9);
95//! assert_eq!(
96//!     p.params(),
97//!     vec![
98//!         ("org", "rust-lang"),
99//!         ("repo", "rust-analyzer"),
100//!         ("day", "2022"),
101//!         ("month", "09"),
102//!         ("year", "12")
103//!     ]
104//! );
105//!
106//! let (h, p) = tree.find("/rust-lang/rust-analyzer/actions/ci:bench").unwrap();
107//! assert_eq!(h, &10);
108//! assert_eq!(
109//!     p.params(),
110//!     vec![
111//!         ("org", "rust-lang"),
112//!         ("repo", "rust-analyzer"),
113//!         ("name", "ci"),
114//!         ("verb", "bench"),
115//!     ]
116//! );
117//!
118//! let (h, p) = tree.find("/rust-lang/rust-analyzer/stargazers").unwrap();
119//! assert_eq!(h, &11);
120//! assert_eq!(p.params(), vec![("org", "rust-lang"), ("repo", "rust-analyzer"), ("page", "stargazers")]);
121//!
122//! let (h, p) = tree.find("/rust-lang/rust-analyzer/stargazers/404").unwrap();
123//! assert_eq!(h, &12);
124//! assert_eq!(p.params(), vec![("org", "rust-lang"), ("repo", "rust-analyzer"), ("*1", "stargazers/404")]);
125//!
126//! let (h, p) = tree.find("/public/js/main.js").unwrap();
127//! assert_eq!(h, &7);
128//! assert_eq!(p.params(), vec![("any", "js/main.js")]);
129//!
130//! let (h, p) = tree.find("/api/v1").unwrap();
131//! assert_eq!(h, &13);
132//! assert_eq!(p.params(), vec![("+1", "v1")]);
133//! ```
134
135#![no_std]
136#![forbid(unsafe_code)]
137#![warn(rust_2018_idioms, unreachable_pub)]
138
139extern crate alloc;
140
141use alloc::{
142    string::{String, ToString},
143    vec::Vec,
144};
145use core::{slice::Iter, str::from_utf8};
146use smallvec::SmallVec;
147
148mod node;
149pub use node::{Key, Node};
150
151mod parser;
152pub use parser::{Kind, Parser, Piece, Position};
153
154/// A path tree.
155#[derive(Clone, Debug)]
156pub struct PathTree<T> {
157    id: usize,
158    routes: Vec<(T, Vec<Piece>)>,
159    pub node: Node<usize>,
160}
161
162impl<T> Default for PathTree<T> {
163    fn default() -> Self {
164        Self::new()
165    }
166}
167
168impl<T> PathTree<T> {
169    /// Creates a new [`PathTree`].
170    #[must_use]
171    pub fn new() -> Self {
172        Self {
173            id: 0,
174            routes: Vec::new(),
175            node: Node::new(Key::String(Vec::new()), None),
176        }
177    }
178
179    /// Inserts a part path-value to the tree and returns the id.
180    #[must_use]
181    pub fn insert(&mut self, path: &str, value: T) -> usize {
182        let mut node = &mut self.node;
183
184        let (overwritten, pieces) = if path.is_empty() {
185            (false, Vec::new())
186        } else {
187            let pieces = Parser::new(path).collect::<Vec<_>>();
188            node = pieces.iter().fold(node, |node, piece| match piece {
189                Piece::String(s) => node.insert_bytes(&s[..]),
190                Piece::Parameter(_, k) => node.insert_parameter(*k),
191            });
192            (true, pieces)
193        };
194
195        if let Some(id) = node.value {
196            self.routes[id].0 = value;
197            if overwritten {
198                self.routes[id].1 = pieces;
199            }
200            id
201        } else {
202            self.routes.push((value, pieces));
203            let id = self.id;
204            node.value = Some(id);
205            self.id += 1;
206            id
207        }
208    }
209
210    /// Returns the [`Path`] by the given path.
211    #[must_use]
212    pub fn find<'a, 'b>(&'a self, path: &'b str) -> Option<(&'a T, Path<'a, 'b>)> {
213        let bytes = path.as_bytes();
214        self.node.find(bytes).and_then(|(id, ranges)| {
215            self.routes.get(*id).map(|(value, pieces)| {
216                (
217                    value,
218                    Path {
219                        id,
220                        pieces,
221                        // opt!
222                        raws: ranges
223                            .into_iter()
224                            .filter_map(|r| from_utf8(&bytes[r]).ok())
225                            .rev()
226                            .collect(),
227                    },
228                )
229            })
230        })
231    }
232
233    /// Gets the route by id.
234    #[must_use]
235    #[inline]
236    pub fn get_route(&self, index: usize) -> Option<&(T, Vec<Piece>)> {
237        self.routes.get(index)
238    }
239
240    /// Generates URL with the params.
241    #[must_use]
242    pub fn url_for(&self, index: usize, params: &[&str]) -> Option<String> {
243        self.get_route(index).and_then(|(_, pieces)| {
244            let mut bytes = Vec::new();
245            let mut iter = params.iter();
246
247            pieces.iter().for_each(|piece| match piece {
248                Piece::String(s) => {
249                    bytes.extend_from_slice(s);
250                }
251                Piece::Parameter(_, _) => {
252                    if let Some(s) = iter.next() {
253                        bytes.extend_from_slice(s.as_bytes());
254                    }
255                }
256            });
257
258            from_utf8(&bytes).map(ToString::to_string).ok()
259        })
260    }
261
262    pub fn iter(&self) -> Iter<'_, (T, Vec<Piece>)> {
263        self.routes.iter()
264    }
265}
266
267impl<'a, T> IntoIterator for &'a PathTree<T> {
268    type Item = &'a (T, Vec<Piece>);
269    type IntoIter = Iter<'a, (T, Vec<Piece>)>;
270
271    fn into_iter(self) -> Self::IntoIter {
272        self.iter()
273    }
274}
275
276/// Matched route path infomation.
277#[derive(Clone, Debug, PartialEq, Eq)]
278pub struct Path<'a, 'b> {
279    pub id: &'a usize,
280    pub pieces: &'a [Piece],
281    pub raws: SmallVec<[&'b str; 4]>,
282}
283
284impl Path<'_, '_> {
285    /// Gets current path pattern.
286    ///
287    /// # Panics
288    ///
289    /// Will panic if bytes to string conversion fails.
290    pub fn pattern(&self) -> String {
291        let mut bytes = Vec::new();
292
293        self.pieces.iter().for_each(|piece| match piece {
294            Piece::String(s) => {
295                if s == b":" || s == b"+" || s == b"?" {
296                    bytes.push(b'\\');
297                }
298                bytes.extend_from_slice(s);
299            }
300            Piece::Parameter(p, k) => match p {
301                Position::Index(_, _) => {
302                    if *k == Kind::OneOrMore {
303                        bytes.push(b'+');
304                    } else if *k == Kind::ZeroOrMore || *k == Kind::ZeroOrMoreSegment {
305                        bytes.push(b'*');
306                    }
307                }
308                Position::Named(n) => match k {
309                    Kind::Normal | Kind::Optional | Kind::OptionalSegment => {
310                        bytes.push(b':');
311                        bytes.extend_from_slice(n);
312                        if *k == Kind::Optional || *k == Kind::OptionalSegment {
313                            bytes.push(b'?');
314                        }
315                    }
316                    Kind::OneOrMore => {
317                        bytes.push(b'+');
318                        bytes.extend_from_slice(n);
319                    }
320                    Kind::ZeroOrMore | Kind::ZeroOrMoreSegment => {
321                        bytes.push(b'*');
322                        bytes.extend_from_slice(n);
323                    }
324                },
325            },
326        });
327
328        from_utf8(&bytes)
329            .map(ToString::to_string)
330            .expect("pattern generated failure")
331    }
332
333    /// Returns the parameters of the current path.
334    #[must_use]
335    pub fn params(&self) -> Vec<(&str, &str)> {
336        self.params_iter().collect()
337    }
338
339    /// Returns the parameters iterator of the current path.
340    pub fn params_iter(&self) -> impl Iterator<Item = (&str, &str)> {
341        #[inline]
342        fn piece_filter(piece: &Piece) -> Option<&str> {
343            match piece {
344                Piece::String(_) => None,
345                Piece::Parameter(p, _) => from_utf8(match p {
346                    Position::Index(_, n) | Position::Named(n) => n,
347                })
348                .ok(),
349            }
350        }
351
352        self.pieces
353            .iter()
354            .filter_map(piece_filter)
355            .zip(self.raws.iter().copied())
356    }
357}
path_tree/lib.rs

path_tree/
lib.rs
