route_recognizer/

lib.rs

//! Recognizes URL patterns with support for dynamic and wildcard segments
//!
//! # Examples
//!
//! ```
//! use route_recognizer::{Router, Params};
//!
//! let mut router = Router::new();
//!
//! router.add("/thomas", "Thomas".to_string());
//! router.add("/tom", "Tom".to_string());
//! router.add("/wycats", "Yehuda".to_string());
//!
//! let m = router.recognize("/thomas").unwrap();
//!
//! assert_eq!(m.handler().as_str(), "Thomas");
//! assert_eq!(m.params(), &Params::new());
//! ```
//!
//! # Routing params
//!
//! The router supports four kinds of route segments:
//! - __segments__: these are of the format `/a/b`.
//! - __params__: these are of the format `/a/:b`.
//! - __named wildcards__: these are of the format `/a/*b`.
//! - __unnamed wildcards__: these are of the format `/a/*`.
//!
//! The difference between a "named wildcard" and a "param" is how the
//! matching rules apply. Given the router `/a/:b`, passing in `/foo/bar/baz`
//! will not match because `/baz` has no counterpart in the router.
//!
//! However if we define the route `/a/*b` and we pass `/foo/bar/baz` we end up
//! with a named param `"b"` that contains the value `"bar/baz"`. Wildcard
//! routing rules are useful when you don't know which routes may follow. The
//! difference between "named" and "unnamed" wildcards is that the former will
//! show up in `Params`, while the latter won't.

#![cfg_attr(feature = "docs", feature(doc_cfg))]
#![deny(unsafe_code)]
#![deny(missing_debug_implementations, nonstandard_style)]
#![warn(missing_docs, unreachable_pub, future_incompatible, rust_2018_idioms)]
#![doc(test(attr(deny(warnings))))]
#![doc(test(attr(allow(unused_extern_crates, unused_variables))))]
#![doc(html_favicon_url = "https://yoshuawuyts.com/assets/http-rs/favicon.ico")]
#![doc(html_logo_url = "https://yoshuawuyts.com/assets/http-rs/logo-rounded.png")]

use std::cmp::Ordering;
use std::collections::{btree_map, BTreeMap};
use std::ops::Index;

use crate::nfa::{CharacterClass, NFA};

#[doc(hidden)]
pub mod nfa;

#[derive(Clone, Eq, Debug)]
struct Metadata {
    statics: u32,
    dynamics: u32,
    wildcards: u32,
    param_names: Vec<String>,
}

impl Metadata {
    pub(crate) fn new() -> Self {
        Self {
            statics: 0,
            dynamics: 0,
            wildcards: 0,
            param_names: Vec::new(),
        }
    }
}

impl Ord for Metadata {
    fn cmp(&self, other: &Self) -> Ordering {
        if self.statics > other.statics {
            Ordering::Greater
        } else if self.statics < other.statics {
            Ordering::Less
        } else if self.dynamics > other.dynamics {
            Ordering::Greater
        } else if self.dynamics < other.dynamics {
            Ordering::Less
        } else if self.wildcards > other.wildcards {
            Ordering::Greater
        } else if self.wildcards < other.wildcards {
            Ordering::Less
        } else {
            Ordering::Equal
        }
    }
}

impl PartialOrd for Metadata {
    fn partial_cmp(&self, other: &Self) -> Option<Ordering> {
        Some(self.cmp(other))
    }
}

impl PartialEq for Metadata {
    fn eq(&self, other: &Self) -> bool {
        self.statics == other.statics
            && self.dynamics == other.dynamics
            && self.wildcards == other.wildcards
    }
}

/// Router parameters.
#[derive(PartialEq, Clone, Debug, Default)]
pub struct Params {
    map: BTreeMap<String, String>,
}

impl Params {
    /// Create a new instance of `Params`.
    pub fn new() -> Self {
        Self {
            map: BTreeMap::new(),
        }
    }

    /// Insert a new param into `Params`.
    pub fn insert(&mut self, key: String, value: String) {
        self.map.insert(key, value);
    }

    /// Find a param by name in `Params`.
    pub fn find(&self, key: &str) -> Option<&str> {
        self.map.get(key).map(|s| &s[..])
    }

    /// Iterate over all named params.
    ///
    /// This will return all named params and named wildcards.
    pub fn iter(&self) -> Iter<'_> {
        Iter(self.map.iter())
    }
}

impl Index<&str> for Params {
    type Output = String;
    fn index(&self, index: &str) -> &String {
        match self.map.get(index) {
            None => panic!("params[{}] did not exist", index),
            Some(s) => s,
        }
    }
}

impl<'a> IntoIterator for &'a Params {
    type IntoIter = Iter<'a>;
    type Item = (&'a str, &'a str);

    fn into_iter(self) -> Iter<'a> {
        self.iter()
    }
}

/// An iterator over `Params`.
#[derive(Debug)]
pub struct Iter<'a>(btree_map::Iter<'a, String, String>);

impl<'a> Iterator for Iter<'a> {
    type Item = (&'a str, &'a str);

    #[inline]
    fn next(&mut self) -> Option<(&'a str, &'a str)> {
        self.0.next().map(|(k, v)| (&**k, &**v))
    }

    fn size_hint(&self) -> (usize, Option<usize>) {
        self.0.size_hint()
    }
}

/// The result of a successful match returned by `Router::recognize`.
#[derive(Debug)]
pub struct Match<T> {
    /// Return the endpoint handler.
    handler: T,
    /// Return the params.
    params: Params,
}

impl<T> Match<T> {
    /// Create a new instance of `Match`.
    pub fn new(handler: T, params: Params) -> Self {
        Self { handler, params }
    }

    /// Get a handle to the handler.
    pub fn handler(&self) -> &T {
        &self.handler
    }

    /// Get a mutable handle to the handler.
    pub fn handler_mut(&mut self) -> &mut T {
        &mut self.handler
    }

    /// Get a handle to the params.
    pub fn params(&self) -> &Params {
        &self.params
    }

    /// Get a mutable handle to the params.
    pub fn params_mut(&mut self) -> &mut Params {
        &mut self.params
    }
}

/// Recognizes URL patterns with support for dynamic and wildcard segments.
#[derive(Clone, Debug)]
pub struct Router<T> {
    nfa: NFA<Metadata>,
    handlers: BTreeMap<usize, T>,
}

fn segments(route: &str) -> Vec<(Option<char>, &str)> {
    let predicate = |c| c == '.' || c == '/';

    let mut segments = vec![];
    let mut segment_start = 0;

    while segment_start < route.len() {
        let segment_end = route[segment_start + 1..]
            .find(predicate)
            .map(|i| i + segment_start + 1)
            .unwrap_or_else(|| route.len());
        let potential_sep = route.chars().nth(segment_start);
        let sep_and_segment = match potential_sep {
            Some(sep) if predicate(sep) => (Some(sep), &route[segment_start + 1..segment_end]),
            _ => (None, &route[segment_start..segment_end]),
        };

        segments.push(sep_and_segment);
        segment_start = segment_end;
    }

    segments
}

impl<T> Router<T> {
    /// Create a new instance of `Router`.
    pub fn new() -> Self {
        Self {
            nfa: NFA::new(),
            handlers: BTreeMap::new(),
        }
    }

    /// Add a route to the router.
    pub fn add(&mut self, mut route: &str, dest: T) {
        if !route.is_empty() && route.as_bytes()[0] == b'/' {
            route = &route[1..];
        }

        let nfa = &mut self.nfa;
        let mut state = 0;
        let mut metadata = Metadata::new();

        for (separator, segment) in segments(route) {
            if let Some(separator) = separator {
                state = nfa.put(state, CharacterClass::valid_char(separator));
            }

            if !segment.is_empty() && segment.as_bytes()[0] == b':' {
                state = process_dynamic_segment(nfa, state);
                metadata.dynamics += 1;
                metadata.param_names.push(segment[1..].to_string());
            } else if !segment.is_empty() && segment.as_bytes()[0] == b'*' {
                state = process_star_state(nfa, state);
                metadata.wildcards += 1;
                metadata.param_names.push(segment[1..].to_string());
            } else {
                state = process_static_segment(segment, nfa, state);
                metadata.statics += 1;
            }
        }

        nfa.acceptance(state);
        nfa.metadata(state, metadata);
        self.handlers.insert(state, dest);
    }

    /// Match a route on the router.
    pub fn recognize(&self, mut path: &str) -> Result<Match<&T>, String> {
        if !path.is_empty() && path.as_bytes()[0] == b'/' {
            path = &path[1..];
        }

        let nfa = &self.nfa;
        let result = nfa.process(path, |index| nfa.get(index).metadata.as_ref().unwrap());

        match result {
            Ok(nfa_match) => {
                let mut map = Params::new();
                let state = &nfa.get(nfa_match.state);
                let metadata = state.metadata.as_ref().unwrap();
                let param_names = metadata.param_names.clone();

                for (i, capture) in nfa_match.captures.iter().enumerate() {
                    if !param_names[i].is_empty() {
                        map.insert(param_names[i].to_string(), capture.to_string());
                    }
                }

                let handler = self.handlers.get(&nfa_match.state).unwrap();
                Ok(Match::new(handler, map))
            }
            Err(str) => Err(str),
        }
    }
}

impl<T> Default for Router<T> {
    fn default() -> Self {
        Self::new()
    }
}

fn process_static_segment<T>(segment: &str, nfa: &mut NFA<T>, mut state: usize) -> usize {
    for char in segment.chars() {
        state = nfa.put(state, CharacterClass::valid_char(char));
    }

    state
}

fn process_dynamic_segment<T>(nfa: &mut NFA<T>, mut state: usize) -> usize {
    state = nfa.put(state, CharacterClass::invalid_char('/'));
    nfa.put_state(state, state);
    nfa.start_capture(state);
    nfa.end_capture(state);

    state
}

fn process_star_state<T>(nfa: &mut NFA<T>, mut state: usize) -> usize {
    state = nfa.put(state, CharacterClass::any());
    nfa.put_state(state, state);
    nfa.start_capture(state);
    nfa.end_capture(state);

    state
}

#[cfg(test)]
mod tests {
    use super::{Params, Router};

    #[test]
    fn basic_router() {
        let mut router = Router::new();

        router.add("/thomas", "Thomas".to_string());
        router.add("/tom", "Tom".to_string());
        router.add("/wycats", "Yehuda".to_string());

        let m = router.recognize("/thomas").unwrap();

        assert_eq!(*m.handler, "Thomas".to_string());
        assert_eq!(m.params, Params::new());
    }

    #[test]
    fn root_router() {
        let mut router = Router::new();
        router.add("/", 10);
        assert_eq!(*router.recognize("/").unwrap().handler, 10)
    }

    #[test]
    fn empty_path() {
        let mut router = Router::new();
        router.add("/", 12);
        assert_eq!(*router.recognize("").unwrap().handler, 12)
    }

    #[test]
    fn empty_route() {
        let mut router = Router::new();
        router.add("", 12);
        assert_eq!(*router.recognize("/").unwrap().handler, 12)
    }

    #[test]
    fn ambiguous_router() {
        let mut router = Router::new();

        router.add("/posts/new", "new".to_string());
        router.add("/posts/:id", "id".to_string());

        let id = router.recognize("/posts/1").unwrap();

        assert_eq!(*id.handler, "id".to_string());
        assert_eq!(id.params, params("id", "1"));

        let new = router.recognize("/posts/new").unwrap();
        assert_eq!(*new.handler, "new".to_string());
        assert_eq!(new.params, Params::new());
    }

    #[test]
    fn ambiguous_router_b() {
        let mut router = Router::new();

        router.add("/posts/:id", "id".to_string());
        router.add("/posts/new", "new".to_string());

        let id = router.recognize("/posts/1").unwrap();

        assert_eq!(*id.handler, "id".to_string());
        assert_eq!(id.params, params("id", "1"));

        let new = router.recognize("/posts/new").unwrap();
        assert_eq!(*new.handler, "new".to_string());
        assert_eq!(new.params, Params::new());
    }

    #[test]
    fn multiple_params() {
        let mut router = Router::new();

        router.add("/posts/:post_id/comments/:id", "comment".to_string());
        router.add("/posts/:post_id/comments", "comments".to_string());

        let com = router.recognize("/posts/12/comments/100").unwrap();
        let coms = router.recognize("/posts/12/comments").unwrap();

        assert_eq!(*com.handler, "comment".to_string());
        assert_eq!(com.params, two_params("post_id", "12", "id", "100"));

        assert_eq!(*coms.handler, "comments".to_string());
        assert_eq!(coms.params, params("post_id", "12"));
        assert_eq!(coms.params["post_id"], "12".to_string());
    }

    #[test]
    fn wildcard() {
        let mut router = Router::new();

        router.add("*foo", "test".to_string());
        router.add("/bar/*foo", "test2".to_string());

        let m = router.recognize("/test").unwrap();
        assert_eq!(*m.handler, "test".to_string());
        assert_eq!(m.params, params("foo", "test"));

        let m = router.recognize("/foo/bar").unwrap();
        assert_eq!(*m.handler, "test".to_string());
        assert_eq!(m.params, params("foo", "foo/bar"));

        let m = router.recognize("/bar/foo").unwrap();
        assert_eq!(*m.handler, "test2".to_string());
        assert_eq!(m.params, params("foo", "foo"));
    }

    #[test]
    fn wildcard_colon() {
        let mut router = Router::new();

        router.add("/a/*b", "ab".to_string());
        router.add("/a/*b/c", "abc".to_string());
        router.add("/a/*b/c/:d", "abcd".to_string());

        let m = router.recognize("/a/foo").unwrap();
        assert_eq!(*m.handler, "ab".to_string());
        assert_eq!(m.params, params("b", "foo"));

        let m = router.recognize("/a/foo/bar").unwrap();
        assert_eq!(*m.handler, "ab".to_string());
        assert_eq!(m.params, params("b", "foo/bar"));

        let m = router.recognize("/a/foo/c").unwrap();
        assert_eq!(*m.handler, "abc".to_string());
        assert_eq!(m.params, params("b", "foo"));

        let m = router.recognize("/a/foo/bar/c").unwrap();
        assert_eq!(*m.handler, "abc".to_string());
        assert_eq!(m.params, params("b", "foo/bar"));

        let m = router.recognize("/a/foo/c/baz").unwrap();
        assert_eq!(*m.handler, "abcd".to_string());
        assert_eq!(m.params, two_params("b", "foo", "d", "baz"));

        let m = router.recognize("/a/foo/bar/c/baz").unwrap();
        assert_eq!(*m.handler, "abcd".to_string());
        assert_eq!(m.params, two_params("b", "foo/bar", "d", "baz"));

        let m = router.recognize("/a/foo/bar/c/baz/bay").unwrap();
        assert_eq!(*m.handler, "ab".to_string());
        assert_eq!(m.params, params("b", "foo/bar/c/baz/bay"));
    }

    #[test]
    fn unnamed_parameters() {
        let mut router = Router::new();

        router.add("/foo/:/bar", "test".to_string());
        router.add("/foo/:bar/*", "test2".to_string());
        let m = router.recognize("/foo/test/bar").unwrap();
        assert_eq!(*m.handler, "test");
        assert_eq!(m.params, Params::new());

        let m = router.recognize("/foo/test/blah").unwrap();
        assert_eq!(*m.handler, "test2");
        assert_eq!(m.params, params("bar", "test"));
    }

    fn params(key: &str, val: &str) -> Params {
        let mut map = Params::new();
        map.insert(key.to_string(), val.to_string());
        map
    }

    fn two_params(k1: &str, v1: &str, k2: &str, v2: &str) -> Params {
        let mut map = Params::new();
        map.insert(k1.to_string(), v1.to_string());
        map.insert(k2.to_string(), v2.to_string());
        map
    }

    #[test]
    fn dot() {
        let mut router = Router::new();
        router.add("/1/baz.:wibble", ());
        router.add("/2/:bar.baz", ());
        router.add("/3/:dynamic.:extension", ());
        router.add("/4/static.static", ());

        let m = router.recognize("/1/baz.jpg").unwrap();
        assert_eq!(m.params, params("wibble", "jpg"));

        let m = router.recognize("/2/test.baz").unwrap();
        assert_eq!(m.params, params("bar", "test"));

        let m = router.recognize("/3/any.thing").unwrap();
        assert_eq!(m.params, two_params("dynamic", "any", "extension", "thing"));

        let m = router.recognize("/3/this.performs.a.greedy.match").unwrap();
        assert_eq!(
            m.params,
            two_params("dynamic", "this.performs.a.greedy", "extension", "match")
        );

        let m = router.recognize("/4/static.static").unwrap();
        assert_eq!(m.params, Params::new());

        let m = router.recognize("/4/static/static");
        assert!(m.is_err());

        let m = router.recognize("/4.static.static");
        assert!(m.is_err());
    }

    #[test]
    fn test_chinese() {
        let mut router = Router::new();
        router.add("/crates/:foo/:bar", "Hello".to_string());

        let m = router.recognize("/crates/实打实打算/d's'd").unwrap();
        assert_eq!(m.handler().as_str(), "Hello");
        assert_eq!(m.params().find("foo"), Some("实打实打算"));
        assert_eq!(m.params().find("bar"), Some("d's'd"));
    }
}