rustf 1.0.0

A simple MVC web framework inspired by Total.js
Documentation
//! High-performance Trie-based router for RustF
//!
//! This module implements a radix trie (compressed trie) for efficient route matching.
//! It provides O(log n) route matching instead of the previous O(n) implementation.

use super::{BeforeFn, RouteHandler, SocketOptions};
use std::collections::HashMap;
use std::fmt::Debug;

/// Route information stored at trie nodes
#[derive(Clone, Debug)]
pub struct RouteInfo {
    pub handler: RouteHandler,
    pub xhr_only: bool,
    /// Optional controller-level pre-handler hook, copied through from
    /// `Route::before`. The dispatcher calls this before invoking
    /// `handler` and skips `handler` if the hook returns `Stop`.
    pub before: Option<BeforeFn>,
    /// `Some` for a `SOCKET` route, copied through from `Route::socket`.
    /// The dispatcher answers a non-handshake request on one with `426`.
    pub socket: Option<SocketOptions>,
}

impl RouteInfo {
    /// A plain route: no XHR constraint, no `before` hook, not a socket.
    pub fn new(handler: RouteHandler) -> Self {
        Self {
            handler,
            xhr_only: false,
            before: None,
            socket: None,
        }
    }

    /// Require the request to be an XHR/AJAX call.
    pub fn xhr_only(mut self) -> Self {
        self.xhr_only = true;
        self
    }

    /// Attach a controller-level `before` hook.
    pub fn with_before(mut self, before: Option<BeforeFn>) -> Self {
        self.before = before;
        self
    }

    /// Mark this as a WebSocket route with the given settings.
    pub fn with_socket(mut self, socket: Option<SocketOptions>) -> Self {
        self.socket = socket;
        self
    }
}

/// A Trie node that can contain route handlers and parameters
#[derive(Debug)]
struct TrieNode {
    /// Exact path segment match
    static_children: HashMap<String, TrieNode>,
    /// Dynamic parameter match (e.g., {id})
    param_child: Option<(String, Box<TrieNode>)>,
    /// Wildcard match (e.g., * or **)
    wildcard_child: Option<Box<TrieNode>>,
    /// Route information for each HTTP method at this node
    handlers: HashMap<String, RouteInfo>,
}

impl TrieNode {
    fn new() -> Self {
        Self {
            static_children: HashMap::new(),
            param_child: None,
            wildcard_child: None,
            handlers: HashMap::new(),
        }
    }
}

/// High-performance Trie-based router
///
/// Provides efficient route matching using a radix trie data structure.
/// Routes are pre-compiled into the trie at startup for O(log n) lookup performance.
pub struct TrieRouter {
    root: TrieNode,
    route_count: usize,
}

impl Default for TrieRouter {
    fn default() -> Self {
        Self::new()
    }
}

impl TrieRouter {
    /// Create a new empty trie router
    pub fn new() -> Self {
        Self {
            root: TrieNode::new(),
            route_count: 0,
        }
    }

    /// Add a route to the trie
    ///
    /// # Arguments
    /// * `method` - HTTP method (GET, POST, etc.)
    /// * `path` - Route path with optional parameters (e.g., "/users/{id}")
    /// * `info` - Handler plus the per-route flags (XHR, `before`, socket)
    pub fn add_route(&mut self, method: &str, path: &str, info: RouteInfo) {
        let segments = self.parse_path(path);
        let mut current = &mut self.root;

        // Navigate/create the trie path
        for segment in segments {
            match segment {
                PathSegment::Static(segment_str) => {
                    current = current
                        .static_children
                        .entry(segment_str)
                        .or_insert_with(TrieNode::new);
                }
                PathSegment::Parameter(param_name) => {
                    if current.param_child.is_none() {
                        current.param_child = Some((param_name, Box::new(TrieNode::new())));
                    } else if current.param_child.as_ref().unwrap().0 != param_name {
                        panic!(
                            "Conflicting route parameter names at the same path segment: '{}' vs '{}'",
                            current.param_child.as_ref().unwrap().0,
                            param_name
                        );
                    }
                    current = &mut current.param_child.as_mut().unwrap().1;
                }
                PathSegment::Wildcard => {
                    if current.wildcard_child.is_none() {
                        current.wildcard_child = Some(Box::new(TrieNode::new()));
                    }
                    current = current.wildcard_child.as_mut().unwrap();
                }
            }
        }

        // Add the handler at the final node
        // For XHR routes, we store with "XHR" as method but match on GET/POST
        if method == "XHR" {
            // XHR routes match both GET and POST
            current.handlers.insert("GET".to_string(), info.clone());
            current.handlers.insert("POST".to_string(), info);
            self.route_count += 2;
        } else {
            current.handlers.insert(method.to_uppercase(), info);
            self.route_count += 1;
        }
    }

    /// Match a route in the trie
    ///
    /// Returns the route info and extracted parameters if a match is found.
    pub fn match_route(
        &self,
        method: &str,
        path: &str,
    ) -> Option<(&RouteInfo, HashMap<String, String>)> {
        // Remove query parameters
        let path_only = if let Some(query_start) = path.find('?') {
            &path[..query_start]
        } else {
            path
        };

        let segments: Vec<&str> = path_only
            .trim_start_matches('/')
            .split('/')
            .filter(|s| !s.is_empty())
            .collect();

        let mut params = HashMap::new();

        if let Some(node) = self.match_segments(&self.root, &segments, 0, &mut params) {
            if let Some(route_info) = node.handlers.get(&method.to_uppercase()) {
                return Some((route_info, params));
            }
        }

        None
    }

    /// Get the number of routes registered
    pub fn route_count(&self) -> usize {
        self.route_count
    }

    /// Parse a path into segments
    fn parse_path(&self, path: &str) -> Vec<PathSegment> {
        let path_clean = path.trim_start_matches('/');
        if path_clean.is_empty() {
            return vec![];
        }

        path_clean
            .split('/')
            .filter(|s| !s.is_empty())
            .map(|segment| {
                if segment == "*" {
                    PathSegment::Wildcard
                } else if segment.starts_with('{') && segment.ends_with('}') {
                    let param_name = segment[1..segment.len() - 1].to_string();
                    PathSegment::Parameter(param_name)
                } else {
                    PathSegment::Static(segment.to_string())
                }
            })
            .collect()
    }

    /// Recursively match segments in the trie
    fn match_segments<'a>(
        &'a self,
        node: &'a TrieNode,
        segments: &[&str],
        index: usize,
        params: &mut HashMap<String, String>,
    ) -> Option<&'a TrieNode> {
        // If we've consumed all segments, return current node
        if index >= segments.len() {
            return Some(node);
        }

        let current_segment = segments[index];

        // Try static match first (most specific)
        if let Some(child) = node.static_children.get(current_segment) {
            if let Some(result) = self.match_segments(child, segments, index + 1, params) {
                return Some(result);
            }
        }

        // Try parameter match
        if let Some((param_name, child)) = &node.param_child {
            params.insert(param_name.clone(), current_segment.to_string());
            if let Some(result) = self.match_segments(child, segments, index + 1, params) {
                return Some(result);
            }
            // Remove parameter if match failed
            params.remove(param_name);
        }

        // Try wildcard match (least specific)
        if let Some(child) = &node.wildcard_child {
            // Wildcard matches remaining segments
            return Some(child);
        }

        None
    }
}

/// Path segment types for trie construction
#[derive(Debug, Clone)]
enum PathSegment {
    /// Static segment (exact match)
    Static(String),
    /// Parameter segment (e.g., {id})
    Parameter(String),
    /// Wildcard segment (*)
    Wildcard,
}

#[cfg(test)]
mod tests {
    use super::*;
    use crate::context::Context;
    use crate::error::Result;
    use std::future::Future;
    use std::pin::Pin;

    // Mock handler for testing
    fn mock_handler(_ctx: &mut Context) -> Pin<Box<dyn Future<Output = Result<()>> + Send + '_>> {
        Box::pin(async { Ok(()) })
    }

    #[test]
    fn test_static_routes() {
        let mut router = TrieRouter::new();
        router.add_route("GET", "/", RouteInfo::new(mock_handler as RouteHandler));
        router.add_route("GET", "/users", RouteInfo::new(mock_handler as RouteHandler));
        router.add_route("GET", "/users/profile", RouteInfo::new(mock_handler as RouteHandler));

        assert!(router.match_route("GET", "/").is_some());
        assert!(router.match_route("GET", "/users").is_some());
        assert!(router.match_route("GET", "/users/profile").is_some());
        assert!(router.match_route("GET", "/nonexistent").is_none());
        assert!(router.match_route("POST", "/users").is_none());
    }

    #[test]
    fn test_parameter_routes() {
        let mut router = TrieRouter::new();
        router.add_route("GET", "/users/{id}", RouteInfo::new(mock_handler as RouteHandler));
        router.add_route("GET", "/users/{id}/posts/{post_id}", RouteInfo::new(mock_handler as RouteHandler));

        let (_, params) = router.match_route("GET", "/users/123").unwrap();
        assert_eq!(params.get("id"), Some(&"123".to_string()));

        let (_, params) = router.match_route("GET", "/users/456/posts/789").unwrap();
        assert_eq!(params.get("id"), Some(&"456".to_string()));
        assert_eq!(params.get("post_id"), Some(&"789".to_string()));
    }

    #[test]
    fn test_route_priority() {
        let mut router = TrieRouter::new();
        router.add_route("GET", "/users/special", RouteInfo::new(mock_handler as RouteHandler));
        router.add_route("GET", "/users/{id}", RouteInfo::new(mock_handler as RouteHandler));

        // Static route should take priority over parameter route
        let (_, params) = router.match_route("GET", "/users/special").unwrap();
        assert!(params.is_empty()); // Should match static route, not parameter

        let (_, params) = router.match_route("GET", "/users/123").unwrap();
        assert_eq!(params.get("id"), Some(&"123".to_string()));
    }

    #[test]
    fn test_query_parameters_ignored() {
        let mut router = TrieRouter::new();
        router.add_route("GET", "/search", RouteInfo::new(mock_handler as RouteHandler));

        assert!(router
            .match_route("GET", "/search?q=test&limit=10")
            .is_some());
        assert!(router.match_route("GET", "/search?").is_some());
    }

    #[test]
    fn test_route_count() {
        let mut router = TrieRouter::new();
        assert_eq!(router.route_count(), 0);

        router.add_route("GET", "/", RouteInfo::new(mock_handler));
        assert_eq!(router.route_count(), 1);

        router.add_route("POST", "/", RouteInfo::new(mock_handler as RouteHandler));
        assert_eq!(router.route_count(), 2);

        router.add_route("GET", "/users", RouteInfo::new(mock_handler as RouteHandler));
        assert_eq!(router.route_count(), 3);
    }

    #[test]
    #[should_panic(expected = "Conflicting route parameter names")]
    fn test_conflicting_parameter_names_panic() {
        let mut router = TrieRouter::new();
        router.add_route("GET", "/users/{id}", RouteInfo::new(mock_handler as RouteHandler));
        router.add_route("GET", "/users/{slug}", RouteInfo::new(mock_handler as RouteHandler));
    }
}