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 `query_params(&req)`, which reads a
/// request with no query string as one with no parameters.
#[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,
	/// Methods registered at this node, in registration order.
	///
	/// A `HashMap` here paid SipHash — a hasher chosen to make *insertion* of
	/// attacker-chosen colliding keys expensive — on a map whose keys are the handful
	/// of `Method` constants the router itself registered. An attacker controls only
	/// the lookup key, never a key in the map, so there is no HashDoS primitive to
	/// defend against, and a scan bounded by the number of methods on one route beats
	/// hashing outright at this size. If handler registration ever becomes reachable
	/// from request data, this trade has to be revisited.
	handlers:   Vec<(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:   Vec::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:   Vec::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:   Vec::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:   Vec::new(),
						children:   Vec::new(),
					});
					node = node.children.last_mut().unwrap();
				}
			}
		}

		// Replace rather than push on re-registration, matching what `HashMap::insert`
		// did: registering the same method twice on one path must leave one handler,
		// not shadow the first with an unreachable second.
		if let Some(slot) = node.handlers.iter_mut().find(|(m, _)| *m == method) {
			slot.1 = handler;
		} else {
			node.handlers.push((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.iter().find(|(m, _)| m == 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.iter().any(|(m, _)| m == 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.iter().any(|(m, _)| m == 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.iter().map(|(m, _)| m.clone()));
			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.iter().map(|(m, _)| m.clone()));
			}
		}
	}
}

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)]
#[path = "../tests/unit/router.rs"]
mod tests;

#[cfg(test)]
#[path = "../tests/unit/router_properties.rs"]
mod property_tests;