chore: add vendor directory

6 files changed, 1729 insertions, 0 deletions

diff --git a/vendor/matchit/src/error.rs b/vendor/matchit/src/error.rs
new file mode 100644
index 00000000..ab879f30
--- /dev/null
+++ b/vendor/matchit/src/error.rs
@@ -0,0 +1,127 @@
+use crate::escape::{UnescapedRef, UnescapedRoute};
+use crate::tree::{denormalize_params, Node};
+
+use std::fmt;
+
+/// Represents errors that can occur when inserting a new route.
+#[non_exhaustive]
+#[derive(Clone, Debug, Eq, Hash, Ord, PartialEq, PartialOrd)]
+pub enum InsertError {
+    /// Attempted to insert a path that conflicts with an existing route.
+    Conflict {
+        /// The existing route that the insertion is conflicting with.
+        with: String,
+    },
+    /// Only one parameter per route segment is allowed.
+    ///
+    /// Static segments are also allowed before a parameter, but not after it. For example,
+    /// `/foo-{bar}` is a valid route, but `/{bar}-foo` is not.
+    InvalidParamSegment,
+    /// Parameters must be registered with a valid name and matching braces.
+    ///
+    /// Note you can use `{{` or `}}` to escape literal brackets.
+    InvalidParam,
+    /// Catch-all parameters are only allowed at the end of a path.
+    InvalidCatchAll,
+}
+
+impl fmt::Display for InsertError {
+    fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
+        match self {
+            Self::Conflict { with } => {
+                write!(
+                    f,
+                    "Insertion failed due to conflict with previously registered route: {}",
+                    with
+                )
+            }
+            Self::InvalidParamSegment => {
+                write!(f, "Only one parameter is allowed per path segment")
+            }
+            Self::InvalidParam => write!(f, "Parameters must be registered with a valid name"),
+            Self::InvalidCatchAll => write!(
+                f,
+                "Catch-all parameters are only allowed at the end of a route"
+            ),
+        }
+    }
+}
+
+impl std::error::Error for InsertError {}
+
+impl InsertError {
+    /// Returns an error for a route conflict with the given node.
+    ///
+    /// This method attempts to find the full conflicting route.
+    pub(crate) fn conflict<T>(
+        route: &UnescapedRoute,
+        prefix: UnescapedRef<'_>,
+        current: &Node<T>,
+    ) -> Self {
+        let mut route = route.clone();
+
+        // The route is conflicting with the current node.
+        if prefix.unescaped() == current.prefix.unescaped() {
+            denormalize_params(&mut route, &current.remapping);
+            return InsertError::Conflict {
+                with: String::from_utf8(route.into_unescaped()).unwrap(),
+            };
+        }
+
+        // Remove the non-matching suffix from the route.
+        route.truncate(route.len() - prefix.len());
+
+        // Add the conflicting prefix.
+        if !route.ends_with(&current.prefix) {
+            route.append(&current.prefix);
+        }
+
+        // Add the prefixes of any conflicting children.
+        let mut child = current.children.first();
+        while let Some(node) = child {
+            route.append(&node.prefix);
+            child = node.children.first();
+        }
+
+        // Denormalize any route parameters.
+        let mut last = current;
+        while let Some(node) = last.children.first() {
+            last = node;
+        }
+        denormalize_params(&mut route, &last.remapping);
+
+        // Return the conflicting route.
+        InsertError::Conflict {
+            with: String::from_utf8(route.into_unescaped()).unwrap(),
+        }
+    }
+}
+
+/// A failed match attempt.
+///
+/// ```
+/// use matchit::{MatchError, Router};
+/// # fn main() -> Result<(), Box<dyn std::error::Error>> {
+/// let mut router = Router::new();
+/// router.insert("/home", "Welcome!")?;
+/// router.insert("/blog", "Our blog.")?;
+///
+/// // no routes match
+/// if let Err(err) = router.at("/blo") {
+///     assert_eq!(err, MatchError::NotFound);
+/// }
+/// # Ok(())
+/// # }
+#[derive(Debug, PartialEq, Eq, Clone, Copy)]
+pub enum MatchError {
+    /// No matching route was found.
+    NotFound,
+}
+
+impl fmt::Display for MatchError {
+    fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
+        write!(f, "Matching route not found")
+    }
+}
+
+impl std::error::Error for MatchError {}
diff --git a/vendor/matchit/src/escape.rs b/vendor/matchit/src/escape.rs
new file mode 100644
index 00000000..ef8ddbfb
--- /dev/null
+++ b/vendor/matchit/src/escape.rs
@@ -0,0 +1,184 @@
+use std::{fmt, ops::Range};
+
+/// An unescaped route that keeps track of the position of escaped characters ('{{' or '}}').
+///
+/// Note that this type dereferences to `&[u8]`.
+#[derive(Clone, Default)]
+pub struct UnescapedRoute {
+    // The raw unescaped route.
+    inner: Vec<u8>,
+    escaped: Vec<usize>,
+}
+
+impl UnescapedRoute {
+    /// Unescapes escaped brackets ('{{' or '}}') in a route.
+    pub fn new(mut inner: Vec<u8>) -> UnescapedRoute {
+        let mut escaped = Vec::new();
+        let mut i = 0;
+
+        while let Some(&c) = inner.get(i) {
+            if (c == b'{' && inner.get(i + 1) == Some(&b'{'))
+                || (c == b'}' && inner.get(i + 1) == Some(&b'}'))
+            {
+                inner.remove(i);
+                escaped.push(i);
+            }
+
+            i += 1;
+        }
+
+        UnescapedRoute { inner, escaped }
+    }
+
+    /// Returns true if the character at the given index was escaped.
+    pub fn is_escaped(&self, i: usize) -> bool {
+        self.escaped.contains(&i)
+    }
+
+    /// Replaces the characters in the given range.
+    pub fn splice(
+        &mut self,
+        range: Range<usize>,
+        replace: Vec<u8>,
+    ) -> impl Iterator<Item = u8> + '_ {
+        // Ignore any escaped characters in the range being replaced.
+        self.escaped.retain(|x| !range.contains(x));
+
+        // Update the escaped indices.
+        let offset = (replace.len() as isize) - (range.len() as isize);
+        for i in &mut self.escaped {
+            if *i > range.end {
+                *i = i.checked_add_signed(offset).unwrap();
+            }
+        }
+
+        self.inner.splice(range, replace)
+    }
+
+    /// Appends another route to the end of this one.
+    pub fn append(&mut self, other: &UnescapedRoute) {
+        for i in &other.escaped {
+            self.escaped.push(self.inner.len() + i);
+        }
+
+        self.inner.extend_from_slice(&other.inner);
+    }
+
+    /// Truncates the route to the given length.
+    pub fn truncate(&mut self, to: usize) {
+        self.escaped.retain(|&x| x < to);
+        self.inner.truncate(to);
+    }
+
+    /// Returns a reference to this route.
+    pub fn as_ref(&self) -> UnescapedRef<'_> {
+        UnescapedRef {
+            inner: &self.inner,
+            escaped: &self.escaped,
+            offset: 0,
+        }
+    }
+
+    /// Returns a reference to the unescaped slice.
+    pub fn unescaped(&self) -> &[u8] {
+        &self.inner
+    }
+
+    /// Returns the unescaped route.
+    pub fn into_unescaped(self) -> Vec<u8> {
+        self.inner
+    }
+}
+
+impl std::ops::Deref for UnescapedRoute {
+    type Target = [u8];
+
+    fn deref(&self) -> &Self::Target {
+        &self.inner
+    }
+}
+
+impl fmt::Debug for UnescapedRoute {
+    fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
+        fmt::Debug::fmt(std::str::from_utf8(&self.inner).unwrap(), f)
+    }
+}
+
+/// A reference to an `UnescapedRoute`.
+#[derive(Copy, Clone)]
+pub struct UnescapedRef<'a> {
+    pub inner: &'a [u8],
+    escaped: &'a [usize],
+    // An offset applied to each escaped index.
+    offset: isize,
+}
+
+impl<'a> UnescapedRef<'a> {
+    /// Converts this reference into an owned route.
+    pub fn to_owned(self) -> UnescapedRoute {
+        let mut escaped = Vec::new();
+        for &i in self.escaped {
+            let i = i.checked_add_signed(self.offset);
+
+            match i {
+                Some(i) if i < self.inner.len() => escaped.push(i),
+                _ => {}
+            }
+        }
+
+        UnescapedRoute {
+            escaped,
+            inner: self.inner.to_owned(),
+        }
+    }
+
+    /// Returns `true` if the character at the given index was escaped.
+    pub fn is_escaped(&self, i: usize) -> bool {
+        if let Some(i) = i.checked_add_signed(-self.offset) {
+            return self.escaped.contains(&i);
+        }
+
+        false
+    }
+
+    /// Slices the route with `start..`.
+    pub fn slice_off(&self, start: usize) -> UnescapedRef<'a> {
+        UnescapedRef {
+            inner: &self.inner[start..],
+            escaped: self.escaped,
+            offset: self.offset - (start as isize),
+        }
+    }
+
+    /// Slices the route with `..end`.
+    pub fn slice_until(&self, end: usize) -> UnescapedRef<'a> {
+        UnescapedRef {
+            inner: &self.inner[..end],
+            escaped: self.escaped,
+            offset: self.offset,
+        }
+    }
+
+    /// Returns a reference to the unescaped slice.
+    pub fn unescaped(&self) -> &[u8] {
+        self.inner
+    }
+}
+
+impl<'a> std::ops::Deref for UnescapedRef<'a> {
+    type Target = &'a [u8];
+
+    fn deref(&self) -> &Self::Target {
+        &self.inner
+    }
+}
+
+impl<'a> fmt::Debug for UnescapedRef<'a> {
+    fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
+        f.debug_struct("UnescapedRef")
+            .field("inner", &std::str::from_utf8(self.inner))
+            .field("escaped", &self.escaped)
+            .field("offset", &self.offset)
+            .finish()
+    }
+}
diff --git a/vendor/matchit/src/lib.rs b/vendor/matchit/src/lib.rs
new file mode 100644
index 00000000..cf128525
--- /dev/null
+++ b/vendor/matchit/src/lib.rs
@@ -0,0 +1,131 @@
+/*!
+A high performance, zero-copy URL router.
+
+```rust
+use matchit::Router;
+
+fn main() -> Result<(), Box<dyn std::error::Error>> {
+    let mut router = Router::new();
+    router.insert("/home", "Welcome!")?;
+    router.insert("/users/{id}", "A User")?;
+
+    let matched = router.at("/users/978")?;
+    assert_eq!(matched.params.get("id"), Some("978"));
+    assert_eq!(*matched.value, "A User");
+
+    Ok(())
+}
+```
+
+# Parameters
+
+The router supports dynamic route segments. These can either be named or catch-all parameters.
+
+Named parameters like `/{id}` match anything until the next `/` or the end of the path. Note that named parameters must be followed
+by a `/` or the end of the route. Dynamic suffixes are not currently supported.
+
+```rust
+# use matchit::Router;
+# fn main() -> Result<(), Box<dyn std::error::Error>> {
+let mut m = Router::new();
+m.insert("/users/{id}", true)?;
+
+assert_eq!(m.at("/users/1")?.params.get("id"), Some("1"));
+assert_eq!(m.at("/users/23")?.params.get("id"), Some("23"));
+assert!(m.at("/users").is_err());
+# Ok(())
+# }
+```
+
+Catch-all parameters start with `*` and match anything until the end of the path. They must always be at the **end** of the route.
+
+```rust
+# use matchit::Router;
+# fn main() -> Result<(), Box<dyn std::error::Error>> {
+let mut m = Router::new();
+m.insert("/{*p}", true)?;
+
+assert_eq!(m.at("/foo.js")?.params.get("p"), Some("foo.js"));
+assert_eq!(m.at("/c/bar.css")?.params.get("p"), Some("c/bar.css"));
+
+// note that this will not match
+assert!(m.at("/").is_err());
+# Ok(())
+# }
+```
+
+The literal characters `{` and `}` may be included in a static route by escaping them with the same character. For example, the `{` character is escaped with `{{` and the `}` character is escaped with `}}`.
+
+```rust
+# use matchit::Router;
+# fn main() -> Result<(), Box<dyn std::error::Error>> {
+let mut m = Router::new();
+m.insert("/{{hello}}", true)?;
+m.insert("/{hello}", true)?;
+
+// match the static route
+assert!(m.at("/{hello}")?.value);
+
+// match the dynamic route
+assert_eq!(m.at("/hello")?.params.get("hello"), Some("hello"));
+# Ok(())
+# }
+```
+
+# Routing Priority
+
+Static and dynamic route segments are allowed to overlap. If they do, static segments will be given higher priority:
+
+```rust
+# use matchit::Router;
+# fn main() -> Result<(), Box<dyn std::error::Error>> {
+let mut m = Router::new();
+m.insert("/", "Welcome!").unwrap();      // priority: 1
+m.insert("/about", "About Me").unwrap(); // priority: 1
+m.insert("/{*filepath}", "...").unwrap();  // priority: 2
+# Ok(())
+# }
+```
+
+# How does it work?
+
+The router takes advantage of the fact that URL routes generally follow a hierarchical structure. Routes are stored them in a radix trie that makes heavy use of common prefixes.
+
+```text
+Priority   Path             Value
+9          \                1
+3          ├s               None
+2          |├earch\         2
+1          |└upport\        3
+2          ├blog\           4
+1          |    └{post}     None
+1          |          └\    5
+2          ├about-us\       6
+1          |        └team\  7
+1          └contact\        8
+```
+
+This allows us to reduce the route search to a small number of branches. Child nodes on the same level of the tree are also prioritized
+by the number of children with registered values, increasing the chance of choosing the correct branch of the first try.
+
+As it turns out, this method of routing is extremely fast. See the [benchmark results](https://github.com/ibraheemdev/matchit?tab=readme-ov-file#benchmarks) for details.
+*/
+
+#![deny(rust_2018_idioms, clippy::all)]
+
+mod error;
+mod escape;
+mod params;
+mod router;
+mod tree;
+
+pub use error::{InsertError, MatchError};
+pub use params::{Params, ParamsIter};
+pub use router::{Match, Router};
+
+#[cfg(doctest)]
+mod readme {
+    #[allow(dead_code)]
+    #[doc = include_str!("../README.md")]
+    struct Readme;
+}
diff --git a/vendor/matchit/src/params.rs b/vendor/matchit/src/params.rs
new file mode 100644
index 00000000..625b544b
--- /dev/null
+++ b/vendor/matchit/src/params.rs
@@ -0,0 +1,262 @@
+use std::{fmt, iter, mem, slice};
+
+/// A single URL parameter, consisting of a key and a value.
+#[derive(PartialEq, Eq, Ord, PartialOrd, Default, Copy, Clone)]
+struct Param<'k, 'v> {
+    // Keys and values are stored as byte slices internally by the router
+    // to avoid UTF8 checks when slicing, but UTF8 is still respected,
+    // so these slices are valid strings.
+    key: &'k [u8],
+    value: &'v [u8],
+}
+
+impl<'k, 'v> Param<'k, 'v> {
+    const EMPTY: Param<'static, 'static> = Param {
+        key: b"",
+        value: b"",
+    };
+
+    // Returns the parameter key as a string.
+    fn key_str(&self) -> &'k str {
+        std::str::from_utf8(self.key).unwrap()
+    }
+
+    // Returns the parameter value as a string.
+    fn value_str(&self) -> &'v str {
+        std::str::from_utf8(self.value).unwrap()
+    }
+}
+
+/// A list of parameters returned by a route match.
+///
+/// ```rust
+/// # fn main() -> Result<(), Box<dyn std::error::Error>> {
+/// # let mut router = matchit::Router::new();
+/// # router.insert("/users/{id}", true).unwrap();
+/// let matched = router.at("/users/1")?;
+///
+/// // Iterate through the keys and values.
+/// for (key, value) in matched.params.iter() {
+///     println!("key: {}, value: {}", key, value);
+/// }
+///
+/// // Get a specific value by name.
+/// let id = matched.params.get("id");
+/// assert_eq!(id, Some("1"));
+/// # Ok(())
+/// # }
+/// ```
+#[derive(PartialEq, Eq, Ord, PartialOrd, Clone)]
+pub struct Params<'k, 'v> {
+    kind: ParamsKind<'k, 'v>,
+}
+
+// Most routes have a small number of dynamic parameters, so we can avoid
+// heap allocations in the common case.
+const SMALL: usize = 3;
+
+// A list of parameters, optimized to avoid allocations when possible.
+#[derive(PartialEq, Eq, Ord, PartialOrd, Clone)]
+enum ParamsKind<'k, 'v> {
+    Small([Param<'k, 'v>; SMALL], usize),
+    Large(Vec<Param<'k, 'v>>),
+}
+
+impl<'k, 'v> Params<'k, 'v> {
+    pub(crate) fn new() -> Self {
+        Self {
+            kind: ParamsKind::Small([Param::EMPTY; 3], 0),
+        }
+    }
+
+    /// Returns the number of parameters.
+    pub fn len(&self) -> usize {
+        match self.kind {
+            ParamsKind::Small(_, len) => len,
+            ParamsKind::Large(ref vec) => vec.len(),
+        }
+    }
+
+    // Truncates the parameter list to the given length.
+    pub(crate) fn truncate(&mut self, n: usize) {
+        match &mut self.kind {
+            ParamsKind::Small(_, len) => *len = n,
+            ParamsKind::Large(vec) => vec.truncate(n),
+        }
+    }
+
+    /// Returns the value of the first parameter registered under the given key.
+    pub fn get(&self, key: impl AsRef<str>) -> Option<&'v str> {
+        let key = key.as_ref().as_bytes();
+
+        match &self.kind {
+            ParamsKind::Small(arr, len) => arr
+                .iter()
+                .take(*len)
+                .find(|param| param.key == key)
+                .map(Param::value_str),
+            ParamsKind::Large(vec) => vec
+                .iter()
+                .find(|param| param.key == key)
+                .map(Param::value_str),
+        }
+    }
+
+    /// Returns an iterator over the parameters in the list.
+    pub fn iter(&self) -> ParamsIter<'_, 'k, 'v> {
+        ParamsIter::new(self)
+    }
+
+    /// Returns `true` if there are no parameters in the list.
+    pub fn is_empty(&self) -> bool {
+        match self.kind {
+            ParamsKind::Small(_, len) => len == 0,
+            ParamsKind::Large(ref vec) => vec.is_empty(),
+        }
+    }
+
+    /// Inserts a key value parameter pair into the list.
+    pub(crate) fn push(&mut self, key: &'k [u8], value: &'v [u8]) {
+        #[cold]
+        fn drain_to_vec<T: Default>(len: usize, elem: T, arr: &mut [T; SMALL]) -> Vec<T> {
+            let mut vec = Vec::with_capacity(len + 1);
+            vec.extend(arr.iter_mut().map(mem::take));
+            vec.push(elem);
+            vec
+        }
+
+        let param = Param { key, value };
+        match &mut self.kind {
+            ParamsKind::Small(arr, len) => {
+                if *len == SMALL {
+                    self.kind = ParamsKind::Large(drain_to_vec(*len, param, arr));
+                    return;
+                }
+
+                arr[*len] = param;
+                *len += 1;
+            }
+            ParamsKind::Large(vec) => vec.push(param),
+        }
+    }
+
+    // Applies a transformation function to each key.
+    pub(crate) fn for_each_key_mut(&mut self, f: impl Fn((usize, &mut &'k [u8]))) {
+        match &mut self.kind {
+            ParamsKind::Small(arr, len) => arr
+                .iter_mut()
+                .take(*len)
+                .map(|param| &mut param.key)
+                .enumerate()
+                .for_each(f),
+            ParamsKind::Large(vec) => vec
+                .iter_mut()
+                .map(|param| &mut param.key)
+                .enumerate()
+                .for_each(f),
+        }
+    }
+}
+
+impl fmt::Debug for Params<'_, '_> {
+    fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
+        f.debug_list().entries(self.iter()).finish()
+    }
+}
+
+/// An iterator over the keys and values of a route's [parameters](crate::Params).
+pub struct ParamsIter<'ps, 'k, 'v> {
+    kind: ParamsIterKind<'ps, 'k, 'v>,
+}
+
+impl<'ps, 'k, 'v> ParamsIter<'ps, 'k, 'v> {
+    fn new(params: &'ps Params<'k, 'v>) -> Self {
+        let kind = match &params.kind {
+            ParamsKind::Small(arr, len) => ParamsIterKind::Small(arr.iter().take(*len)),
+            ParamsKind::Large(vec) => ParamsIterKind::Large(vec.iter()),
+        };
+        Self { kind }
+    }
+}
+
+enum ParamsIterKind<'ps, 'k, 'v> {
+    Small(iter::Take<slice::Iter<'ps, Param<'k, 'v>>>),
+    Large(slice::Iter<'ps, Param<'k, 'v>>),
+}
+
+impl<'ps, 'k, 'v> Iterator for ParamsIter<'ps, 'k, 'v> {
+    type Item = (&'k str, &'v str);
+
+    fn next(&mut self) -> Option<Self::Item> {
+        match self.kind {
+            ParamsIterKind::Small(ref mut iter) => {
+                iter.next().map(|p| (p.key_str(), p.value_str()))
+            }
+            ParamsIterKind::Large(ref mut iter) => {
+                iter.next().map(|p| (p.key_str(), p.value_str()))
+            }
+        }
+    }
+}
+
+impl ExactSizeIterator for ParamsIter<'_, '_, '_> {
+    fn len(&self) -> usize {
+        match self.kind {
+            ParamsIterKind::Small(ref iter) => iter.len(),
+            ParamsIterKind::Large(ref iter) => iter.len(),
+        }
+    }
+}
+
+#[cfg(test)]
+mod tests {
+    use super::*;
+
+    #[test]
+    fn heap_alloc() {
+        let vec = vec![
+            ("hello", "hello"),
+            ("world", "world"),
+            ("foo", "foo"),
+            ("bar", "bar"),
+            ("baz", "baz"),
+        ];
+
+        let mut params = Params::new();
+        for (key, value) in vec.clone() {
+            params.push(key.as_bytes(), value.as_bytes());
+            assert_eq!(params.get(key), Some(value));
+        }
+
+        match params.kind {
+            ParamsKind::Large(..) => {}
+            _ => panic!(),
+        }
+
+        assert!(params.iter().eq(vec.clone()));
+    }
+
+    #[test]
+    fn stack_alloc() {
+        let vec = vec![("hello", "hello"), ("world", "world"), ("baz", "baz")];
+
+        let mut params = Params::new();
+        for (key, value) in vec.clone() {
+            params.push(key.as_bytes(), value.as_bytes());
+            assert_eq!(params.get(key), Some(value));
+        }
+
+        match params.kind {
+            ParamsKind::Small(..) => {}
+            _ => panic!(),
+        }
+
+        assert!(params.iter().eq(vec.clone()));
+    }
+
+    #[test]
+    fn ignore_array_default() {
+        let params = Params::new();
+        assert!(params.get("").is_none());
+    }
+}
diff --git a/vendor/matchit/src/router.rs b/vendor/matchit/src/router.rs
new file mode 100644
index 00000000..8256c4bc
--- /dev/null
+++ b/vendor/matchit/src/router.rs
@@ -0,0 +1,147 @@
+use crate::tree::Node;
+use crate::{InsertError, MatchError, Params};
+
+/// A zero-copy URL router.
+///
+/// See [the crate documentation](crate) for details.
+#[derive(Clone, Debug)]
+pub struct Router<T> {
+    root: Node<T>,
+}
+
+impl<T> Default for Router<T> {
+    fn default() -> Self {
+        Self {
+            root: Node::default(),
+        }
+    }
+}
+
+impl<T> Router<T> {
+    /// Construct a new router.
+    pub fn new() -> Self {
+        Self::default()
+    }
+
+    /// Insert a route into the router.
+    ///
+    /// # Examples
+    ///
+    /// ```rust
+    /// # use matchit::Router;
+    /// # fn main() -> Result<(), Box<dyn std::error::Error>> {
+    /// let mut router = Router::new();
+    /// router.insert("/home", "Welcome!")?;
+    /// router.insert("/users/{id}", "A User")?;
+    /// # Ok(())
+    /// # }
+    /// ```
+    pub fn insert(&mut self, route: impl Into<String>, value: T) -> Result<(), InsertError> {
+        self.root.insert(route.into(), value)
+    }
+
+    /// Tries to find a value in the router matching the given path.
+    ///
+    /// # Examples
+    ///
+    /// ```rust
+    /// # use matchit::Router;
+    /// # fn main() -> Result<(), Box<dyn std::error::Error>> {
+    /// let mut router = Router::new();
+    /// router.insert("/home", "Welcome!")?;
+    ///
+    /// let matched = router.at("/home").unwrap();
+    /// assert_eq!(*matched.value, "Welcome!");
+    /// # Ok(())
+    /// # }
+    /// ```
+    pub fn at<'path>(&self, path: &'path str) -> Result<Match<'_, 'path, &T>, MatchError> {
+        match self.root.at(path.as_bytes()) {
+            Ok((value, params)) => Ok(Match {
+                // Safety: We only expose `&mut T` through `&mut self`
+                value: unsafe { &*value.get() },
+                params,
+            }),
+            Err(e) => Err(e),
+        }
+    }
+
+    /// Tries to find a value in the router matching the given path,
+    /// returning a mutable reference.
+    ///
+    /// # Examples
+    ///
+    /// ```rust
+    /// # use matchit::Router;
+    /// # fn main() -> Result<(), Box<dyn std::error::Error>> {
+    /// let mut router = Router::new();
+    /// router.insert("/", 1)?;
+    ///
+    /// *router.at_mut("/").unwrap().value += 1;
+    /// assert_eq!(*router.at("/").unwrap().value, 2);
+    /// # Ok(())
+    /// # }
+    /// ```
+    pub fn at_mut<'path>(
+        &mut self,
+        path: &'path str,
+    ) -> Result<Match<'_, 'path, &mut T>, MatchError> {
+        match self.root.at(path.as_bytes()) {
+            Ok((value, params)) => Ok(Match {
+                // Safety: We have `&mut self`
+                value: unsafe { &mut *value.get() },
+                params,
+            }),
+            Err(e) => Err(e),
+        }
+    }
+
+    /// Remove a given route from the router.
+    ///
+    /// Returns the value stored under the route if it was found.
+    /// If the route was not found or invalid, `None` is returned.
+    ///
+    /// # Examples
+    ///
+    /// ```rust
+    /// # use matchit::Router;
+    /// let mut router = Router::new();
+    ///
+    /// router.insert("/home", "Welcome!");
+    /// assert_eq!(router.remove("/home"), Some("Welcome!"));
+    /// assert_eq!(router.remove("/home"), None);
+    ///
+    /// router.insert("/home/{id}/", "Hello!");
+    /// assert_eq!(router.remove("/home/{id}/"), Some("Hello!"));
+    /// assert_eq!(router.remove("/home/{id}/"), None);
+    ///
+    /// router.insert("/home/{id}/", "Hello!");
+    /// // the route does not match
+    /// assert_eq!(router.remove("/home/{user}"), None);
+    /// assert_eq!(router.remove("/home/{id}/"), Some("Hello!"));
+    ///
+    /// router.insert("/home/{id}/", "Hello!");
+    /// // invalid route
+    /// assert_eq!(router.remove("/home/{id"), None);
+    /// assert_eq!(router.remove("/home/{id}/"), Some("Hello!"));
+    /// ```
+    pub fn remove(&mut self, path: impl Into<String>) -> Option<T> {
+        self.root.remove(path.into())
+    }
+
+    #[cfg(feature = "__test_helpers")]
+    pub fn check_priorities(&self) -> Result<u32, (u32, u32)> {
+        self.root.check_priorities()
+    }
+}
+
+/// A successful match consisting of the registered value
+/// and URL parameters, returned by [`Router::at`](Router::at).
+#[derive(Debug)]
+pub struct Match<'k, 'v, V> {
+    /// The value stored under the matched node.
+    pub value: V,
+
+    /// The route parameters. See [parameters](crate#parameters) for more details.
+    pub params: Params<'k, 'v>,
+}
diff --git a/vendor/matchit/src/tree.rs b/vendor/matchit/src/tree.rs
new file mode 100644
index 00000000..69a01495
--- /dev/null
+++ b/vendor/matchit/src/tree.rs
@@ -0,0 +1,878 @@
+use crate::escape::{UnescapedRef, UnescapedRoute};
+use crate::{InsertError, MatchError, Params};
+
+use std::cell::UnsafeCell;
+use std::cmp::min;
+use std::ops::Range;
+use std::{fmt, mem};
+
+/// A radix tree used for URL path matching.
+///
+/// See [the crate documentation](crate) for details.
+pub struct Node<T> {
+    // This node's prefix.
+    pub(crate) prefix: UnescapedRoute,
+    // The priority of this node.
+    //
+    // Nodes with more children are higher priority and searched first.
+    pub(crate) priority: u32,
+    // Whether this node contains a wildcard child.
+    pub(crate) wild_child: bool,
+    // The first character of any static children, for fast linear search.
+    pub(crate) indices: Vec<u8>,
+    // The type of this node.
+    pub(crate) node_type: NodeType,
+    pub(crate) children: Vec<Self>,
+    // The value stored at this node.
+    //
+    // See `Node::at` for why an `UnsafeCell` is necessary.
+    value: Option<UnsafeCell<T>>,
+    // Parameter name remapping, stored at nodes that hold values.
+    pub(crate) remapping: ParamRemapping,
+}
+
+/// The types of nodes a tree can hold.
+#[derive(PartialEq, Eq, PartialOrd, Ord, Debug, Clone)]
+pub(crate) enum NodeType {
+    /// The root path.
+    Root,
+    /// A route parameter, e.g. `/{id}`.
+    Param,
+    /// A catch-all parameter, e.g. `/*file`.
+    CatchAll,
+    /// A static prefix, e.g. `/foo`.
+    Static,
+}
+
+/// Safety: We expose `value` per Rust's usual borrowing rules, so we can just
+/// delegate these traits.
+unsafe impl<T: Send> Send for Node<T> {}
+unsafe impl<T: Sync> Sync for Node<T> {}
+
+impl<T> Node<T> {
+    // Insert a route into the tree.
+    pub fn insert(&mut self, route: String, val: T) -> Result<(), InsertError> {
+        let route = UnescapedRoute::new(route.into_bytes());
+        let (route, remapping) = normalize_params(route)?;
+        let mut remaining = route.as_ref();
+
+        self.priority += 1;
+
+        // If the tree is empty, insert the root node.
+        if self.prefix.is_empty() && self.children.is_empty() {
+            let last = self.insert_route(remaining, val)?;
+            last.remapping = remapping;
+            self.node_type = NodeType::Root;
+            return Ok(());
+        }
+
+        let mut current = self;
+        'walk: loop {
+            // Find the common prefix between the route and the current node.
+            let len = min(remaining.len(), current.prefix.len());
+            let common_prefix = (0..len)
+                .find(|&i| {
+                    remaining[i] != current.prefix[i]
+                    // Make sure not confuse the start of a wildcard with an escaped `{`.
+                        || remaining.is_escaped(i) != current.prefix.is_escaped(i)
+                })
+                .unwrap_or(len);
+
+            // If this node has a longer prefix than we need, we have to fork and extract the
+            // common prefix into a shared parent.
+            if current.prefix.len() > common_prefix {
+                // Move the non-matching suffix into a child node.
+                let suffix = current.prefix.as_ref().slice_off(common_prefix).to_owned();
+                let child = Node {
+                    prefix: suffix,
+                    value: current.value.take(),
+                    indices: current.indices.clone(),
+                    wild_child: current.wild_child,
+                    children: mem::take(&mut current.children),
+                    remapping: mem::take(&mut current.remapping),
+                    priority: current.priority - 1,
+                    node_type: NodeType::Static,
+                };
+
+                // The current node now only holds the common prefix.
+                current.children = vec![child];
+                current.indices = vec![current.prefix[common_prefix]];
+                current.prefix = current
+                    .prefix
+                    .as_ref()
+                    .slice_until(common_prefix)
+                    .to_owned();
+                current.wild_child = false;
+                continue;
+            }
+
+            if remaining.len() == common_prefix {
+                // This node must not already contain a value.
+                if current.value.is_some() {
+                    return Err(InsertError::conflict(&route, remaining, current));
+                }
+
+                // Insert the value.
+                current.value = Some(UnsafeCell::new(val));
+                current.remapping = remapping;
+                return Ok(());
+            }
+
+            // Otherwise, the route has a remaining non-matching suffix.
+            //
+            // We have to search deeper.
+            remaining = remaining.slice_off(common_prefix);
+            let next = remaining[0];
+
+            // After matching against a wildcard the next character is always `/`.
+            //
+            // Continue searching in the child node if it already exists.
+            if current.node_type == NodeType::Param && current.children.len() == 1 {
+                debug_assert_eq!(next, b'/');
+                current = &mut current.children[0];
+                current.priority += 1;
+                continue 'walk;
+            }
+
+            // Find a child node that matches the next character in the route.
+            for mut i in 0..current.indices.len() {
+                if next == current.indices[i] {
+                    // Make sure not confuse the start of a wildcard with an escaped `{` or `}`.
+                    if matches!(next, b'{' | b'}') && !remaining.is_escaped(0) {
+                        continue;
+                    }
+
+                    // Continue searching in the child.
+                    i = current.update_child_priority(i);
+                    current = &mut current.children[i];
+                    continue 'walk;
+                }
+            }
+
+            // We couldn't find a matching child.
+            //
+            // If we're not inserting a wildcard we have to create a child.
+            if (!matches!(next, b'{') || remaining.is_escaped(0))
+                && current.node_type != NodeType::CatchAll
+            {
+                current.indices.push(next);
+                let mut child = current.add_child(Node::default());
+                child = current.update_child_priority(child);
+
+                // Insert into the newly created node.
+                let last = current.children[child].insert_route(remaining, val)?;
+                last.remapping = remapping;
+                return Ok(());
+            }
+
+            // We're trying to insert a wildcard.
+            //
+            // If this node already has a wildcard child, we have to make sure it matches.
+            if current.wild_child {
+                // Wildcards are always the last child.
+                current = current.children.last_mut().unwrap();
+                current.priority += 1;
+
+                // Make sure the route parameter matches.
+                if let Some(wildcard) = remaining.get(..current.prefix.len()) {
+                    if *wildcard != *current.prefix {
+                        return Err(InsertError::conflict(&route, remaining, current));
+                    }
+                }
+
+                // Catch-all routes cannot have children.
+                if current.node_type == NodeType::CatchAll {
+                    return Err(InsertError::conflict(&route, remaining, current));
+                }
+
+                // Continue with the wildcard node.
+                continue 'walk;
+            }
+
+            // Otherwise, create a new node for the wildcard and insert the route.
+            let last = current.insert_route(remaining, val)?;
+            last.remapping = remapping;
+            return Ok(());
+        }
+    }
+
+    /// Removes a route from the tree, returning the value if the route already existed.
+    ///
+    /// The provided path should be the same as the one used to insert the route, including
+    /// wildcards.
+    pub fn remove(&mut self, route: String) -> Option<T> {
+        let route = UnescapedRoute::new(route.into_bytes());
+        let (route, remapping) = normalize_params(route).ok()?;
+        let mut remaining = route.unescaped();
+
+        // Check if we are removing the root node.
+        if remaining == self.prefix.unescaped() {
+            let value = self.value.take().map(UnsafeCell::into_inner);
+
+            // If the root node has no children, we can reset it.
+            if self.children.is_empty() {
+                *self = Node::default();
+            }
+
+            return value;
+        }
+
+        let mut current = self;
+        'walk: loop {
+            // The path is longer than this node's prefix, search deeper.
+            if remaining.len() > current.prefix.len() {
+                let (prefix, rest) = remaining.split_at(current.prefix.len());
+
+                // The prefix matches.
+                if prefix == current.prefix.unescaped() {
+                    let first = rest[0];
+                    remaining = rest;
+
+                    // If there is a single child node, we can continue searching in the child.
+                    if current.children.len() == 1 {
+                        // The route matches, remove the node.
+                        if current.children[0].prefix.unescaped() == remaining {
+                            return current.remove_child(0, &remapping);
+                        }
+
+                        // Otherwise, continue searching.
+                        current = &mut current.children[0];
+                        continue 'walk;
+                    }
+
+                    // Find a child node that matches the next character in the route.
+                    if let Some(i) = current.indices.iter().position(|&c| c == first) {
+                        // The route matches, remove the node.
+                        if current.children[i].prefix.unescaped() == remaining {
+                            return current.remove_child(i, &remapping);
+                        }
+
+                        // Otherwise, continue searching.
+                        current = &mut current.children[i];
+                        continue 'walk;
+                    }
+
+                    // If the node has a matching wildcard child, continue searching in the child.
+                    if current.wild_child
+                        && remaining.first().zip(remaining.get(2)) == Some((&b'{', &b'}'))
+                    {
+                        // The route matches, remove the node.
+                        if current.children.last_mut().unwrap().prefix.unescaped() == remaining {
+                            return current.remove_child(current.children.len() - 1, &remapping);
+                        }
+
+                        current = current.children.last_mut().unwrap();
+                        continue 'walk;
+                    }
+                }
+            }
+
+            // Could not find a match.
+            return None;
+        }
+    }
+
+    /// Remove the child node at the given index, if the route parameters match.
+    fn remove_child(&mut self, i: usize, remapping: &ParamRemapping) -> Option<T> {
+        // Require an exact match to remove a route.
+        //
+        // For example, `/{a}` cannot be used to remove `/{b}`.
+        if self.children[i].remapping != *remapping {
+            return None;
+        }
+
+        // If the node does not have any children, we can remove it completely.
+        let value = if self.children[i].children.is_empty() {
+            // Removing a single child with no indices.
+            if self.children.len() == 1 && self.indices.is_empty() {
+                self.wild_child = false;
+                self.children.remove(0).value.take()
+            } else {
+                // Remove the child node.
+                let child = self.children.remove(i);
+
+                match child.node_type {
+                    // Remove the index if we removed a static prefix.
+                    NodeType::Static => {
+                        self.indices.remove(i);
+                    }
+                    // Otherwise, we removed a wildcard.
+                    _ => self.wild_child = false,
+                }
+
+                child.value
+            }
+        }
+        // Otherwise, remove the value but preserve the node.
+        else {
+            self.children[i].value.take()
+        };
+
+        value.map(UnsafeCell::into_inner)
+    }
+
+    // Adds a child to this node, keeping wildcards at the end.
+    fn add_child(&mut self, child: Node<T>) -> usize {
+        let len = self.children.len();
+
+        if self.wild_child && len > 0 {
+            self.children.insert(len - 1, child);
+            len - 1
+        } else {
+            self.children.push(child);
+            len
+        }
+    }
+
+    // Increments priority of the given child node, reordering the children if necessary.
+    //
+    // Returns the new index of the node.
+    fn update_child_priority(&mut self, i: usize) -> usize {
+        self.children[i].priority += 1;
+        let priority = self.children[i].priority;
+
+        // Move the node to the front as necessary.
+        let mut updated = i;
+        while updated > 0 && self.children[updated - 1].priority < priority {
+            self.children.swap(updated - 1, updated);
+            updated -= 1;
+        }
+
+        // Update the position of the indices to match.
+        if updated != i {
+            self.indices[updated..=i].rotate_right(1);
+        }
+
+        updated
+    }
+
+    // Insert a route at this node.
+    fn insert_route(
+        &mut self,
+        mut prefix: UnescapedRef<'_>,
+        val: T,
+    ) -> Result<&mut Node<T>, InsertError> {
+        let mut current = self;
+
+        loop {
+            // Search for a wildcard segment.
+            let wildcard = match find_wildcard(prefix)? {
+                Some(wildcard) => wildcard,
+                // There is no wildcard, simply insert into the current node.
+                None => {
+                    current.value = Some(UnsafeCell::new(val));
+                    current.prefix = prefix.to_owned();
+                    return Ok(current);
+                }
+            };
+
+            // Insering a catch-all route.
+            if prefix[wildcard.clone()][1] == b'*' {
+                // Ensure there is no suffix after the parameter, e.g. `/foo/{*x}/bar`.
+                if wildcard.end != prefix.len() {
+                    return Err(InsertError::InvalidCatchAll);
+                }
+
+                // Add the prefix before the wildcard into the current node.
+                if wildcard.start > 0 {
+                    current.prefix = prefix.slice_until(wildcard.start).to_owned();
+                    prefix = prefix.slice_off(wildcard.start);
+                }
+
+                // Add the catch-all as a child node.
+                let child = Self {
+                    prefix: prefix.to_owned(),
+                    node_type: NodeType::CatchAll,
+                    value: Some(UnsafeCell::new(val)),
+                    priority: 1,
+                    ..Self::default()
+                };
+
+                let i = current.add_child(child);
+                current.wild_child = true;
+                return Ok(&mut current.children[i]);
+            }
+
+            // Otherwise, we're inserting a regular route parameter.
+            assert_eq!(prefix[wildcard.clone()][0], b'{');
+
+            // Add the prefix before the wildcard into the current node.
+            if wildcard.start > 0 {
+                current.prefix = prefix.slice_until(wildcard.start).to_owned();
+                prefix = prefix.slice_off(wildcard.start);
+            }
+
+            // Add the parameter as a child node.
+            let child = Self {
+                node_type: NodeType::Param,
+                prefix: prefix.slice_until(wildcard.len()).to_owned(),
+                ..Self::default()
+            };
+
+            let child = current.add_child(child);
+            current.wild_child = true;
+            current = &mut current.children[child];
+            current.priority += 1;
+
+            // If the route doesn't end in the wildcard, we have to insert the suffix as a child.
+            if wildcard.len() < prefix.len() {
+                prefix = prefix.slice_off(wildcard.len());
+                let child = Self {
+                    priority: 1,
+                    ..Self::default()
+                };
+
+                let child = current.add_child(child);
+                current = &mut current.children[child];
+                continue;
+            }
+
+            // Finally, insert the value.
+            current.value = Some(UnsafeCell::new(val));
+            return Ok(current);
+        }
+    }
+}
+
+/// A wildcard node that was skipped during a tree search.
+///
+/// Contains the state necessary to backtrack to the given node.
+struct Skipped<'n, 'p, T> {
+    // The node that was skipped.
+    node: &'n Node<T>,
+    /// The path at the time we skipped this node.
+    path: &'p [u8],
+    // The number of parameters that were present.
+    params: usize,
+}
+
+#[rustfmt::skip]
+macro_rules! backtracker {
+    ($skipped_nodes:ident, $path:ident, $current:ident, $params:ident, $backtracking:ident, $walk:lifetime) => {
+        macro_rules! try_backtrack {
+            () => {
+                // Try backtracking to any matching wildcard nodes that we skipped while
+                // traversing the tree.
+                while let Some(skipped) = $skipped_nodes.pop() {
+                    if skipped.path.ends_with($path) {
+                        // Restore the search state.
+                        $path = skipped.path;
+                        $current = &skipped.node;
+                        $params.truncate(skipped.params);
+                        $backtracking = true;
+                        continue $walk;
+                    }
+                }
+            };
+        }
+    };
+}
+
+impl<T> Node<T> {
+    // Returns the node matching the given path.
+    //
+    // Returning an `UnsafeCell` allows us to avoid duplicating the logic between `Node::at` and
+    // `Node::at_mut`, as Rust doesn't have a great way of abstracting over mutability.
+    pub fn at<'node, 'path>(
+        &'node self,
+        full_path: &'path [u8],
+    ) -> Result<(&'node UnsafeCell<T>, Params<'node, 'path>), MatchError> {
+        let mut current = self;
+        let mut path = full_path;
+        let mut backtracking = false;
+        let mut params = Params::new();
+        let mut skipped_nodes: Vec<Skipped<'_, '_, T>> = Vec::new();
+
+        'walk: loop {
+            // Initialize the backtracker.
+            backtracker!(skipped_nodes, path, current, params, backtracking, 'walk);
+
+            // Reached the end of the search.
+            if path.len() <= current.prefix.len() {
+                // Check for an exact match.
+                if *path == *current.prefix {
+                    // Found the matching value.
+                    if let Some(ref value) = current.value {
+                        // Remap the keys of any route parameters we accumulated during the search.
+                        params.for_each_key_mut(|(i, key)| *key = &current.remapping[i]);
+                        return Ok((value, params));
+                    }
+                }
+
+                // Try backtracking in case we skipped a wildcard that may match.
+                try_backtrack!();
+
+                // Otherwise, there are no matching routes in the tree.
+                return Err(MatchError::NotFound);
+            }
+
+            // Otherwise, the path is longer than this node's prefix, search deeper.
+            let (prefix, rest) = path.split_at(current.prefix.len());
+
+            // The prefix does not match.
+            if *prefix != *current.prefix {
+                // Try backtracking in case we skipped a wildcard that may match.
+                try_backtrack!();
+
+                // Otherwise, there are no matching routes in the tree.
+                return Err(MatchError::NotFound);
+            }
+
+            let previous = path;
+            path = rest;
+
+            // If we are currently backtracking, avoid searching static children
+            // that we already searched.
+            if !backtracking {
+                let next = path[0];
+
+                // Find a child node that matches the next character in the path.
+                if let Some(i) = current.indices.iter().position(|&c| c == next) {
+                    // Keep track of wildcard routes that we skip.
+                    //
+                    // We may end up needing to backtrack later in case we do not find a
+                    // match.
+                    if current.wild_child {
+                        skipped_nodes.push(Skipped {
+                            path: previous,
+                            node: current,
+                            params: params.len(),
+                        });
+                    }
+
+                    // Continue searching.
+                    current = &current.children[i];
+                    continue 'walk;
+                }
+            }
+
+            // We didn't find a matching static child.
+            //
+            // If there are no wildcards, then there are no matching routes in the tree.
+            if !current.wild_child {
+                // Try backtracking in case we skipped a wildcard that may match.
+                try_backtrack!();
+                return Err(MatchError::NotFound);
+            }
+
+            // Continue searching in the wildcard child, which is kept at the end of the list.
+            current = current.children.last().unwrap();
+            match current.node_type {
+                // Match against a route parameter.
+                NodeType::Param => {
+                    // Check for more path segments.
+                    let i = match path.iter().position(|&c| c == b'/') {
+                        // Found another segment.
+                        Some(i) => i,
+                        // This is the last path segment.
+                        None => {
+                            let value = match current.value {
+                                // Found the matching value.
+                                Some(ref value) => value,
+                                None => {
+                                    // Try backtracking in case we skipped a wildcard that may match.
+                                    try_backtrack!();
+
+                                    // Otherwise, there are no matching routes in the tree.
+                                    return Err(MatchError::NotFound);
+                                }
+                            };
+
+                            // Store the parameter value.
+                            // Parameters are normalized so the key is irrelevant for now.
+                            params.push(b"", path);
+
+                            // Remap the keys of any route parameters we accumulated during the search.
+                            params.for_each_key_mut(|(i, key)| *key = &current.remapping[i]);
+
+                            return Ok((value, params));
+                        }
+                    };
+
+                    // Found another path segment.
+                    let (param, rest) = path.split_at(i);
+
+                    // If there is a static child, continue the search.
+                    if let [child] = current.children.as_slice() {
+                        // Store the parameter value.
+                        // Parameters are normalized so the key is irrelevant for now.
+                        params.push(b"", param);
+
+                        // Continue searching.
+                        path = rest;
+                        current = child;
+                        backtracking = false;
+                        continue 'walk;
+                    }
+
+                    // Try backtracking in case we skipped a wildcard that may match.
+                    try_backtrack!();
+
+                    // Otherwise, there are no matching routes in the tree.
+                    return Err(MatchError::NotFound);
+                }
+                NodeType::CatchAll => {
+                    // Catch-all segments are only allowed at the end of the route, meaning
+                    // this node must contain the value.
+                    let value = match current.value {
+                        // Found the matching value.
+                        Some(ref value) => value,
+                        // Otherwise, there are no matching routes in the tree.
+                        None => return Err(MatchError::NotFound),
+                    };
+
+                    // Remap the keys of any route parameters we accumulated during the search.
+                    params.for_each_key_mut(|(i, key)| *key = &current.remapping[i]);
+
+                    // Store the final catch-all parameter (`{*...}`).
+                    let key = &current.prefix[2..current.prefix.len() - 1];
+                    params.push(key, path);
+
+                    return Ok((value, params));
+                }
+                _ => unreachable!(),
+            }
+        }
+    }
+
+    /// Test helper that ensures route priorities are consistent.
+    #[cfg(feature = "__test_helpers")]
+    pub fn check_priorities(&self) -> Result<u32, (u32, u32)> {
+        let mut priority: u32 = 0;
+        for child in &self.children {
+            priority += child.check_priorities()?;
+        }
+
+        if self.value.is_some() {
+            priority += 1;
+        }
+
+        if self.priority != priority {
+            return Err((self.priority, priority));
+        }
+
+        Ok(priority)
+    }
+}
+
+/// An ordered list of route parameters keys for a specific route.
+///
+/// To support conflicting routes like `/{a}/foo` and `/{b}/bar`, route parameters
+/// are normalized before being inserted into the tree. Parameter remapping are
+/// stored at nodes containing values, containing the "true" names of all route parameters
+/// for the given route.
+type ParamRemapping = Vec<Vec<u8>>;
+
+/// Returns `path` with normalized route parameters, and a parameter remapping
+/// to store at the node for this route.
+///
+/// Note that the parameter remapping may contain unescaped characters.
+fn normalize_params(
+    mut path: UnescapedRoute,
+) -> Result<(UnescapedRoute, ParamRemapping), InsertError> {
+    let mut start = 0;
+    let mut original = ParamRemapping::new();
+
+    // Parameter names are normalized alphabetically.
+    let mut next = b'a';
+
+    loop {
+        // Find a wildcard to normalize.
+        let mut wildcard = match find_wildcard(path.as_ref().slice_off(start))? {
+            Some(wildcard) => wildcard,
+            // No wildcard, we are done.
+            None => return Ok((path, original)),
+        };
+
+        wildcard.start += start;
+        wildcard.end += start;
+
+        // Ensure the parameter has a valid name.
+        if wildcard.len() < 2 {
+            return Err(InsertError::InvalidParam);
+        }
+
+        // We don't need to normalize catch-all parameters, as they are always
+        // at the end of a route.
+        if path[wildcard.clone()][1] == b'*' {
+            start = wildcard.end;
+            continue;
+        }
+
+        // Normalize the parameter.
+        let removed = path.splice(wildcard.clone(), vec![b'{', next, b'}']);
+
+        // Preserve the original name for remapping.
+        let mut removed = removed.skip(1).collect::<Vec<_>>();
+        removed.pop();
+        original.push(removed);
+
+        next += 1;
+        if next > b'z' {
+            panic!("Too many route parameters.");
+        }
+
+        // Continue the search after the parameter we just normalized.
+        start = wildcard.start + 3;
+    }
+}
+
+/// Restores `route` to it's original, denormalized form.
+pub(crate) fn denormalize_params(route: &mut UnescapedRoute, params: &ParamRemapping) {
+    let mut start = 0;
+    let mut i = 0;
+
+    loop {
+        // Find a wildcard to denormalize.
+        let mut wildcard = match find_wildcard(route.as_ref().slice_off(start)).unwrap() {
+            Some(w) => w,
+            None => return,
+        };
+
+        wildcard.start += start;
+        wildcard.end += start;
+
+        // Get the corresponding parameter remapping.
+        let mut next = match params.get(i) {
+            Some(param) => param.clone(),
+            None => return,
+        };
+
+        // Denormalize this parameter.
+        next.insert(0, b'{');
+        next.push(b'}');
+        let _ = route.splice(wildcard.clone(), next.clone());
+
+        i += 1;
+        start = wildcard.start + next.len();
+    }
+}
+
+// Searches for a wildcard segment and checks the path for invalid characters.
+fn find_wildcard(path: UnescapedRef<'_>) -> Result<Option<Range<usize>>, InsertError> {
+    for (start, &c) in path.iter().enumerate() {
+        // Found an unescaped closing brace without a corresponding opening brace.
+        if c == b'}' && !path.is_escaped(start) {
+            return Err(InsertError::InvalidParam);
+        }
+
+        // Keep going until we find an unescaped opening brace.
+        if c != b'{' || path.is_escaped(start) {
+            continue;
+        }
+
+        // Ensure there is a non-empty parameter name.
+        if path.get(start + 1) == Some(&b'}') {
+            return Err(InsertError::InvalidParam);
+        }
+
+        // Find the corresponding closing brace.
+        for (i, &c) in path.iter().enumerate().skip(start + 2) {
+            match c {
+                b'}' => {
+                    // This closing brace was escaped, keep searching.
+                    if path.is_escaped(i) {
+                        continue;
+                    }
+
+                    // Ensure catch-all parameters have a non-empty name.
+                    if path.get(i - 1) == Some(&b'*') {
+                        return Err(InsertError::InvalidParam);
+                    }
+
+                    if let Some(&c) = path.get(i + 1) {
+                        // Prefixes after route parameters are not supported.
+                        if c != b'/' {
+                            return Err(InsertError::InvalidParamSegment);
+                        }
+                    }
+
+                    return Ok(Some(start..i + 1));
+                }
+                // `*` and `/` are invalid in parameter names.
+                b'*' | b'/' => return Err(InsertError::InvalidParam),
+                _ => {}
+            }
+        }
+
+        // Missing closing brace.
+        return Err(InsertError::InvalidParam);
+    }
+
+    Ok(None)
+}
+
+impl<T> Clone for Node<T>
+where
+    T: Clone,
+{
+    fn clone(&self) -> Self {
+        let value = self.value.as_ref().map(|value| {
+            // Safety: We only expose `&mut T` through `&mut self`.
+            let value = unsafe { &*value.get() };
+            UnsafeCell::new(value.clone())
+        });
+
+        Self {
+            value,
+            prefix: self.prefix.clone(),
+            wild_child: self.wild_child,
+            node_type: self.node_type.clone(),
+            indices: self.indices.clone(),
+            children: self.children.clone(),
+            remapping: self.remapping.clone(),
+            priority: self.priority,
+        }
+    }
+}
+
+impl<T> Default for Node<T> {
+    fn default() -> Self {
+        Self {
+            remapping: ParamRemapping::new(),
+            prefix: UnescapedRoute::default(),
+            wild_child: false,
+            node_type: NodeType::Static,
+            indices: Vec::new(),
+            children: Vec::new(),
+            value: None,
+            priority: 0,
+        }
+    }
+}
+
+impl<T> fmt::Debug for Node<T>
+where
+    T: fmt::Debug,
+{
+    fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
+        // Safety: We only expose `&mut T` through `&mut self`.
+        let value = unsafe { self.value.as_ref().map(|x| &*x.get()) };
+
+        let mut f = f.debug_struct("Node");
+        f.field("value", &value)
+            .field("prefix", &self.prefix)
+            .field("node_type", &self.node_type)
+            .field("children", &self.children);
+
+        // Extra information for debugging purposes.
+        #[cfg(test)]
+        {
+            let indices = self
+                .indices
+                .iter()
+                .map(|&x| char::from_u32(x as _))
+                .collect::<Vec<_>>();
+
+            let params = self
+                .remapping
+                .iter()
+                .map(|x| std::str::from_utf8(x).unwrap())
+                .collect::<Vec<_>>();
+
+            f.field("indices", &indices).field("params", &params);
+        }
+
+        f.finish()
+    }
+}