mini_serve/

router.rs

use std::collections::HashMap;

use hyper::Method;

use crate::handler::Handler;

/// Extracted path parameters from a matched route.
///
/// Contains a map of parameter names to their decoded string values
/// (e.g., `id` → `"42"` from a route `/items/:id`). Populated by the router
/// and stored in request extensions; extract via `path_params::<T>(req)`.
#[derive(Clone, Debug, Default)]
pub struct PathParams(pub HashMap<String, String>);

/// Parsed query parameters from the request URL.
///
/// Contains a map of query parameter names to their values, with `+` decoded
/// as space and percent-encoded sequences decoded. Populated by the app and
/// stored in request extensions; extract via `req.extensions().get::<QueryParams>()`.
#[derive(Clone, Debug, Default)]
pub struct QueryParams(pub HashMap<String, String>);

/// A trie-based HTTP router for matching requests to handlers.
///
/// Routes are matched by method and path, with support for dynamic path parameters
/// (`:name`) and wildcards (`*`). Each request is matched in a single trie traversal.
#[derive(Default)]
pub struct Router<S> {
	root: Node<S>,
}

struct Node<S> {
	segment:    String,
	param_name: String,
	is_wildcard: bool,
	handlers:   HashMap<Method, Handler<S>>,
	children:   Vec<Node<S>>,
}

impl<S> Default for Node<S> {
	fn default() -> Self {
		Node {
			segment:    String::new(),
			param_name: String::new(),
			is_wildcard: false,
			handlers:   HashMap::new(),
			children:   Vec::new(),
		}
	}
}

impl<S: Send + Sync + 'static> Router<S> {
	/// Create a new empty router.
	pub fn new() -> Self {
		Router { root: Node::default() }
	}

	/// Register a handler for the given method and path.
	///
	/// Paths may contain static segments, dynamic parameters (`:name`), and a
	/// wildcard (`*`) to match everything. For example: `/users/:id` or `/api/*`.
	pub fn insert(&mut self, method: Method, path: &str, handler: Handler<S>) {
		let segments = split_path(path);
		let mut node = &mut self.root;

		for seg in segments {
			if seg == "*" {
				if let Some(idx) = node.children.iter().position(|c| c.is_wildcard) {
					node = &mut node.children[idx];
				} else {
					node.children.push(Node {
						segment:    "*".to_string(),
						param_name: String::new(),
						is_wildcard: true,
						handlers:   HashMap::new(),
						children:   Vec::new(),
					});
					node = node.children.last_mut().unwrap();
				}
			} else if let Some(param_name) = seg.strip_prefix(':') {
				if let Some(idx) = node.children.iter().position(|c| c.param_name == param_name) {
					node = &mut node.children[idx];
				} else {
					node.children.push(Node {
						segment:    seg.to_string(),
						param_name: param_name.to_string(),
						is_wildcard: false,
						handlers:   HashMap::new(),
						children:   Vec::new(),
					});
					node = node.children.last_mut().unwrap();
				}
			} else {
				if let Some(idx) = node.children.iter().position(|c| c.segment == seg) {
					node = &mut node.children[idx];
				} else {
					node.children.push(Node {
						segment:    seg.to_string(),
						param_name: String::new(),
						is_wildcard: false,
						handlers:   HashMap::new(),
						children:   Vec::new(),
					});
					node = node.children.last_mut().unwrap();
				}
			}
		}

		node.handlers.insert(method, handler);
	}

	/// Find and return the handler for the given method and path, along with extracted parameters.
	///
	/// Returns `None` if no route matches. Path parameters are percent-decoded and
	/// included in the returned `PathParams`.
	pub fn match_route<'a>(
		&'a self,
		method: &Method,
		path: &str,
	) -> Option<(&'a Handler<S>, PathParams)> {
		let segments = split_path(path);
		let mut params = PathParams::default();
		let node = Self::find_node(&self.root, &segments, 0, method, &mut params)?;
		node.handlers.get(method).map(|h| (h, params))
	}

	/// List all HTTP methods that have handlers registered for the given path.
	///
	/// Returns an empty vector if the path has no registered handlers.
	pub fn allowed_methods(&self, path: &str) -> Vec<Method> {
		let segments = split_path(path);
		let mut methods = std::collections::HashSet::new();
		let mut params = PathParams::default();
		Self::collect_allowed_methods(&self.root, &segments, 0, &mut params, &mut methods);
		methods.into_iter().collect()
	}

	/// Check whether any handler is registered for the given path.
	pub fn path_exists(&self, path: &str) -> bool {
		!self.allowed_methods(path).is_empty()
	}

	/// Recursive backtracking search for a trie node that is both
	/// path-complete *and* has a handler for `method`.
	///
	/// Tries children in precedence order: static → param → wildcard.
	/// Backtracks to the next-choice child on either kind of dead end: no
	/// path match, or a path-complete node with no handler for `method` (so
	/// e.g. a registered `POST /users/new` doesn't shadow `GET /users/:id`
	/// for a `GET /users/new` request — the static branch is path-complete
	/// but lacks GET, so the search falls back to the param branch).
	///
	/// Optimization: borrows params through static segments without cloning,
	/// only cloning before modifying for param branches. On backtrack,
	/// truncates params to remove any additions made in failed attempts.
	fn find_node<'a>(
		node: &'a Node<S>,
		segments: &[String],
		idx: usize,
		method: &Method,
		params: &mut PathParams,
	) -> Option<&'a Node<S>> {
		if idx == segments.len() {
			return if node.handlers.contains_key(method) { Some(node) } else { None };
		}

		let seg = &segments[idx];

		for child in &node.children {
			if !child.is_wildcard && child.param_name.is_empty() && child.segment == *seg {
				// Static segment: pass params through without cloning.
				if let Some(found) = Self::find_node(child, segments, idx + 1, method, params) {
					return Some(found);
				}
			}
		}

		for child in &node.children {
			if !child.is_wildcard && !child.param_name.is_empty() {
				// Param segment: clone before modifying for backtrack safety.
				let mut p = params.clone();
				p.0.insert(child.param_name.clone(), seg.clone());
				if let Some(found) = Self::find_node(child, segments, idx + 1, method, &mut p) {
					*params = p;
					return Some(found);
				}
				// Backtrack: remove the param we added in this failed attempt.
				params.0.remove(&child.param_name);
			}
		}

		for child in &node.children {
			if child.is_wildcard && child.handlers.contains_key(method) {
				params.0.insert("*".to_string(), segments[idx..].join("/"));
				return Some(child);
			}
		}

		None
	}

	/// Exhaustive counterpart to [`find_node`] for computing the `Allow`
	/// header: unions handler methods across *every* path-complete node
	/// reachable, not just the first one the static→param→wildcard
	/// precedence would settle on. Necessary because, per the same
	/// ambiguity `find_node` backtracks around, more than one branch can be
	/// path-complete for a given request path.
	fn collect_allowed_methods(
		node: &Node<S>,
		segments: &[String],
		idx: usize,
		params: &mut PathParams,
		methods: &mut std::collections::HashSet<Method>,
	) {
		if idx == segments.len() {
			methods.extend(node.handlers.keys().cloned());
			return;
		}

		let seg = &segments[idx];

		for child in &node.children {
			if !child.is_wildcard && child.param_name.is_empty() && child.segment == *seg {
				let mut p = params.clone();
				Self::collect_allowed_methods(child, segments, idx + 1, &mut p, methods);
			}
		}

		for child in &node.children {
			if !child.is_wildcard && !child.param_name.is_empty() {
				let mut p = params.clone();
				p.0.insert(child.param_name.clone(), seg.clone());
				Self::collect_allowed_methods(child, segments, idx + 1, &mut p, methods);
			}
		}

		for child in &node.children {
			if child.is_wildcard {
				methods.extend(child.handlers.keys().cloned());
			}
		}
	}
}

fn split_path(path: &str) -> Vec<String> {
	path.trim_start_matches('/')
		.split('/')
		.filter(|s| !s.is_empty())
		.map(|s| percent_encoding::percent_decode_str(s).decode_utf8_lossy().into_owned())
		.collect()
}

#[cfg(test)]
mod tests {
	use super::*;
	use crate::error::ServeError;
	use hyper::Response;
	use hyper::body::Bytes;

	fn dummy_handler() -> Handler<()> {
		crate::handler::handler(|_, _| async {
			Ok::<_, ServeError>(Response::new(crate::handler::body(Bytes::from("ok"))))
		})
	}

	#[test]
	fn insert_and_match_static() {
		let mut router = Router::new();
		router.insert(Method::GET, "/hello", dummy_handler());
		let (_, _) = router.match_route(&Method::GET, "/hello").unwrap();
	}

	#[test]
	fn match_with_path_param() {
		let mut router = Router::new();
		router.insert(Method::GET, "/users/:id", dummy_handler());
		let (_, params) = router.match_route(&Method::GET, "/users/42").unwrap();
		assert_eq!(params.0.get("id").unwrap(), "42");
	}

	#[test]
	fn match_with_wildcard() {
		let mut router = Router::new();
		router.insert(Method::GET, "/files/*", dummy_handler());
		let (_, params) = router.match_route(&Method::GET, "/files/a/b/c").unwrap();
		assert_eq!(params.0.get("*").unwrap(), "a/b/c");
	}

	#[test]
	fn no_match_for_unregistered_route() {
		let mut router = Router::new();
		router.insert(Method::GET, "/hello", dummy_handler());
		assert!(router.match_route(&Method::GET, "/world").is_none());
	}

	#[test]
	fn method_mismatch_returns_none() {
		let mut router = Router::new();
		router.insert(Method::GET, "/hello", dummy_handler());
		assert!(router.match_route(&Method::POST, "/hello").is_none());
	}

	#[test]
	fn root_path_matches() {
		let mut router = Router::new();
		router.insert(Method::GET, "/", dummy_handler());
		let (_, _) = router.match_route(&Method::GET, "/").unwrap();
	}

	#[test]
	fn method_mismatch_on_static_branch_backtracks_to_param_sibling() {
		let mut router = Router::new();
		router.insert(Method::GET, "/users/:id", dummy_handler());
		router.insert(Method::POST, "/users/new", dummy_handler());

		// The static "new" branch matches the path but has no GET handler;
		// the search must fall back to the ":id" param branch rather than
		// reporting no match.
		let (_, params) = router.match_route(&Method::GET, "/users/new").unwrap();
		assert_eq!(params.0.get("id").unwrap(), "new");
	}

	#[test]
	fn static_branch_with_matching_method_still_wins_over_param_sibling() {
		let mut router = Router::new();
		router.insert(Method::GET, "/users/:id", dummy_handler());
		router.insert(Method::GET, "/users/new", dummy_handler());

		let (_, params) = router.match_route(&Method::GET, "/users/new").unwrap();
		assert!(params.0.is_empty(), "static branch should win, not fall back to :id");
	}

	#[test]
	fn allowed_methods_unions_across_ambiguous_branches() {
		let mut router = Router::new();
		router.insert(Method::GET, "/users/:id", dummy_handler());
		router.insert(Method::POST, "/users/new", dummy_handler());

		let mut allowed = router.allowed_methods("/users/new");
		allowed.sort_by_key(|m| m.to_string());
		assert_eq!(allowed, vec![Method::GET, Method::POST]);
	}

	#[test]
	fn static_path_traversal_borrows_params_without_cloning() {
		let mut router = Router::new();
		// Deep static path: /api/v1/users/profile
		router.insert(Method::GET, "/api/v1/users/profile", dummy_handler());
		let (_, params) = router.match_route(&Method::GET, "/api/v1/users/profile").unwrap();

		// For a pure static path with no params, params map should be empty.
		// More importantly, the optimization ensures we don't clone params
		// while traversing static segments.
		assert!(params.0.is_empty());
	}

	#[test]
	fn param_backtracking_truncates_params_on_failure() {
		let mut router = Router::new();
		// Route with param after static segments
		router.insert(Method::GET, "/users/:id", dummy_handler());
		// Also register a route that forces backtracking
		router.insert(Method::POST, "/users/new", dummy_handler());

		// GET /users/new should match the param route (static branch has no GET)
		let (_, params) = router.match_route(&Method::GET, "/users/new").unwrap();
		assert_eq!(params.0.get("id").unwrap(), "new");

		// Verify no extra params were left behind from the static branch attempt
		assert_eq!(params.0.len(), 1);
	}
}