specmock_runtime/http/
router.rs

1//! Radix-tree based path router built at spec load time.
2//!
3//! Replaces the previous linear-scan `match_operation` approach with an
4//! O(depth) lookup over a tree of path segments.
5
6use std::collections::HashMap;
7
8use http::Method;
9
10use super::openapi::OperationSpec;
11
12// ---------------------------------------------------------------------------
13// Public types
14// ---------------------------------------------------------------------------
15
16/// Pre-compiled radix-tree router for HTTP path matching.
17#[derive(Debug, Clone)]
18pub struct PathRouter {
19    root: RadixNode,
20}
21
22/// Result of a successful route match.
23#[derive(Debug)]
24pub struct RouteMatch {
25    /// Index into the originating `Vec<OperationSpec>`.
26    pub operation_index: usize,
27    /// Extracted path parameters.
28    pub path_params: HashMap<String, String>,
29}
30
31/// A single segment matcher used when building the tree.
32#[derive(Debug, Clone, PartialEq, Eq)]
33pub enum SegmentMatcher {
34    /// Exact literal segment (e.g. `pets`).
35    Literal(String),
36    /// Named path parameter (e.g. `{petId}` → `petId`).
37    Param(String),
38}
39
40// ---------------------------------------------------------------------------
41// Private types
42// ---------------------------------------------------------------------------
43
44/// A node in the radix tree.
45#[derive(Debug, Clone, Default)]
46struct RadixNode {
47    /// Outgoing edges to child nodes.
48    children: Vec<RadixEdge>,
49    /// Operations that terminate at this node: `(Method, operation_index)`.
50    operations: Vec<(Method, usize)>,
51}
52
53/// An edge connecting two `RadixNode`s via a `SegmentMatcher`.
54#[derive(Debug, Clone)]
55struct RadixEdge {
56    segment: SegmentMatcher,
57    child: RadixNode,
58}
59
60// ---------------------------------------------------------------------------
61// Construction
62// ---------------------------------------------------------------------------
63
64impl PathRouter {
65    /// Build a `PathRouter` from a slice of `OperationSpec`.
66    ///
67    /// Each operation's `path_template` is split into segments and inserted
68    /// into the tree. Lookup time is O(number of segments in the request
69    /// path).
70    pub fn build(operations: &[OperationSpec]) -> Self {
71        let mut root = RadixNode::default();
72
73        for (index, operation) in operations.iter().enumerate() {
74            let segments = parse_segments(&operation.path_template);
75            insert(&mut root, &segments, operation.method.clone(), index);
76        }
77
78        Self { root }
79    }
80
81    /// Match an HTTP method and path against the tree.
82    ///
83    /// Returns a [`RouteMatch`] on success or `None` when no route matches.
84    pub fn match_route(&self, method: &Method, path: &str) -> Option<RouteMatch> {
85        let segments = split_path(path);
86        let mut params = HashMap::new();
87        let node = walk(&self.root, &segments, &mut params)?;
88
89        node.operations
90            .iter()
91            .find(|(m, _)| m == method)
92            .map(|&(_, operation_index)| RouteMatch { operation_index, path_params: params })
93    }
94}
95
96// ---------------------------------------------------------------------------
97// Helpers — segment parsing
98// ---------------------------------------------------------------------------
99
100/// Parse an OpenAPI path template into a list of `SegmentMatcher`s.
101fn parse_segments(template: &str) -> Vec<SegmentMatcher> {
102    template
103        .trim_matches('/')
104        .split('/')
105        .filter(|s| !s.is_empty())
106        .map(|s| {
107            if s.starts_with('{') && s.ends_with('}') && s.len() > 2 {
108                SegmentMatcher::Param(s[1..s.len() - 1].to_owned())
109            } else {
110                SegmentMatcher::Literal(s.to_owned())
111            }
112        })
113        .collect()
114}
115
116/// Split a concrete request path into segments.
117fn split_path(path: &str) -> Vec<&str> {
118    path.trim_matches('/').split('/').filter(|s| !s.is_empty()).collect()
119}
120
121// ---------------------------------------------------------------------------
122// Helpers — tree insertion
123// ---------------------------------------------------------------------------
124
125fn insert(node: &mut RadixNode, segments: &[SegmentMatcher], method: Method, index: usize) {
126    if segments.is_empty() {
127        node.operations.push((method, index));
128        return;
129    }
130
131    let Some((head, tail)) = segments.split_first() else {
132        return;
133    };
134
135    // Find an existing edge that matches this segment matcher exactly.
136    for edge in &mut node.children {
137        if &edge.segment == head {
138            insert(&mut edge.child, tail, method, index);
139            return;
140        }
141    }
142
143    // No existing edge — create a new one.
144    let mut child = RadixNode::default();
145    insert(&mut child, tail, method, index);
146    node.children.push(RadixEdge { segment: head.clone(), child });
147}
148
149// ---------------------------------------------------------------------------
150// Helpers — tree walk
151// ---------------------------------------------------------------------------
152
153/// Recursively walk the tree and collect path parameters.
154///
155/// Returns the terminal `RadixNode` if the walk succeeds.
156fn walk<'a>(
157    node: &'a RadixNode,
158    segments: &[&str],
159    params: &mut HashMap<String, String>,
160) -> Option<&'a RadixNode> {
161    if segments.is_empty() {
162        return Some(node);
163    }
164
165    let (head, tail) = segments.split_first()?;
166
167    // Prefer literal matches over parameter matches so that `/pets/mine`
168    // beats `/pets/{petId}` when both exist.
169    for edge in &node.children {
170        if let SegmentMatcher::Literal(ref lit) = edge.segment &&
171            lit == head &&
172            let Some(result) = walk(&edge.child, tail, params)
173        {
174            return Some(result);
175        }
176    }
177
178    // Fall back to parameter edges.
179    for edge in &node.children {
180        if let SegmentMatcher::Param(ref name) = edge.segment {
181            let mut candidate_params = params.clone();
182            candidate_params.insert(name.clone(), (*head).to_owned());
183            if let Some(result) = walk(&edge.child, tail, &mut candidate_params) {
184                *params = candidate_params;
185                return Some(result);
186            }
187        }
188    }
189
190    None
191}
192
193// ---------------------------------------------------------------------------
194// Tests
195// ---------------------------------------------------------------------------
196
197#[cfg(test)]
198mod tests {
199    use super::*;
200
201    /// Helper: build a minimal `OperationSpec` with only method + path.
202    fn op(method: Method, path: &str) -> OperationSpec {
203        OperationSpec {
204            method,
205            path_template: path.to_owned(),
206            operation_id: None,
207            parameters: vec![],
208            request_body_schema: None,
209            request_body_required: false,
210            responses: vec![],
211            callbacks: vec![],
212        }
213    }
214
215    #[test]
216    fn literal_match() {
217        let ops = vec![op(Method::GET, "/pets")];
218        let router = PathRouter::build(&ops);
219
220        let m = router.match_route(&Method::GET, "/pets");
221        assert!(m.is_some());
222        let m = m.unwrap_or_else(|| unreachable!());
223        assert_eq!(m.operation_index, 0);
224        assert!(m.path_params.is_empty());
225    }
226
227    #[test]
228    fn param_match() {
229        let ops = vec![op(Method::GET, "/pets/{petId}")];
230        let router = PathRouter::build(&ops);
231
232        let m = router.match_route(&Method::GET, "/pets/42");
233        assert!(m.is_some());
234        let m = m.unwrap_or_else(|| unreachable!());
235        assert_eq!(m.operation_index, 0);
236        assert_eq!(m.path_params.get("petId").map(String::as_str), Some("42"));
237    }
238
239    #[test]
240    fn no_match_wrong_path() {
241        let ops = vec![op(Method::GET, "/pets")];
242        let router = PathRouter::build(&ops);
243        assert!(router.match_route(&Method::GET, "/dogs").is_none());
244    }
245
246    #[test]
247    fn no_match_wrong_method() {
248        let ops = vec![op(Method::GET, "/pets")];
249        let router = PathRouter::build(&ops);
250        assert!(router.match_route(&Method::POST, "/pets").is_none());
251    }
252
253    #[test]
254    fn method_disambiguation() {
255        let ops = vec![
256            op(Method::GET, "/pets"),
257            op(Method::POST, "/pets"),
258            op(Method::DELETE, "/pets/{petId}"),
259        ];
260        let router = PathRouter::build(&ops);
261
262        let get = router.match_route(&Method::GET, "/pets");
263        assert!(get.is_some());
264        assert_eq!(get.unwrap_or_else(|| unreachable!()).operation_index, 0);
265
266        let post = router.match_route(&Method::POST, "/pets");
267        assert!(post.is_some());
268        assert_eq!(post.unwrap_or_else(|| unreachable!()).operation_index, 1);
269
270        let delete = router.match_route(&Method::DELETE, "/pets/7");
271        assert!(delete.is_some());
272        let delete = delete.unwrap_or_else(|| unreachable!());
273        assert_eq!(delete.operation_index, 2);
274        assert_eq!(delete.path_params.get("petId").map(String::as_str), Some("7"));
275    }
276
277    #[test]
278    fn coexisting_paths() {
279        let ops = vec![
280            op(Method::GET, "/pets"),
281            op(Method::GET, "/pets/{petId}"),
282            op(Method::GET, "/pets/{petId}/toys"),
283            op(Method::GET, "/pets/{petId}/toys/{toyId}"),
284        ];
285        let router = PathRouter::build(&ops);
286
287        let m0 = router.match_route(&Method::GET, "/pets");
288        assert_eq!(m0.unwrap_or_else(|| unreachable!()).operation_index, 0);
289
290        let m1 = router.match_route(&Method::GET, "/pets/3");
291        let m1 = m1.unwrap_or_else(|| unreachable!());
292        assert_eq!(m1.operation_index, 1);
293        assert_eq!(m1.path_params.get("petId").map(String::as_str), Some("3"));
294
295        let m2 = router.match_route(&Method::GET, "/pets/3/toys");
296        let m2 = m2.unwrap_or_else(|| unreachable!());
297        assert_eq!(m2.operation_index, 2);
298        assert_eq!(m2.path_params.get("petId").map(String::as_str), Some("3"));
299
300        let m3 = router.match_route(&Method::GET, "/pets/3/toys/99");
301        let m3 = m3.unwrap_or_else(|| unreachable!());
302        assert_eq!(m3.operation_index, 3);
303        assert_eq!(m3.path_params.get("petId").map(String::as_str), Some("3"));
304        assert_eq!(m3.path_params.get("toyId").map(String::as_str), Some("99"));
305    }
306
307    #[test]
308    fn trailing_slash_normalisation() {
309        let ops = vec![op(Method::GET, "/pets")];
310        let router = PathRouter::build(&ops);
311
312        // Trailing slash on request should still match.
313        assert!(router.match_route(&Method::GET, "/pets/").is_some());
314        // Path template with trailing slash should also work.
315        let ops2 = vec![op(Method::GET, "/pets/")];
316        let router2 = PathRouter::build(&ops2);
317        assert!(router2.match_route(&Method::GET, "/pets").is_some());
318    }
319
320    #[test]
321    fn literal_preferred_over_param() {
322        let ops = vec![op(Method::GET, "/pets/{petId}"), op(Method::GET, "/pets/mine")];
323        let router = PathRouter::build(&ops);
324
325        let mine = router.match_route(&Method::GET, "/pets/mine");
326        let mine = mine.unwrap_or_else(|| unreachable!());
327        // Should match the literal `/pets/mine` (index 1), not the param.
328        assert_eq!(mine.operation_index, 1);
329        assert!(mine.path_params.is_empty());
330
331        // Other values should still match the param route.
332        let other = router.match_route(&Method::GET, "/pets/42");
333        let other = other.unwrap_or_else(|| unreachable!());
334        assert_eq!(other.operation_index, 0);
335        assert_eq!(other.path_params.get("petId").map(String::as_str), Some("42"));
336    }
337
338    #[test]
339    fn root_path() {
340        let ops = vec![op(Method::GET, "/")];
341        let router = PathRouter::build(&ops);
342        assert!(router.match_route(&Method::GET, "/").is_some());
343    }
344
345    #[test]
346    fn multi_param_segments() {
347        let ops = vec![op(Method::GET, "/orgs/{orgId}/repos/{repoId}/issues/{issueId}")];
348        let router = PathRouter::build(&ops);
349
350        let m = router.match_route(&Method::GET, "/orgs/acme/repos/widget/issues/123");
351        let m = m.unwrap_or_else(|| unreachable!());
352        assert_eq!(m.path_params.get("orgId").map(String::as_str), Some("acme"));
353        assert_eq!(m.path_params.get("repoId").map(String::as_str), Some("widget"));
354        assert_eq!(m.path_params.get("issueId").map(String::as_str), Some("123"));
355    }
356
357    #[test]
358    fn extra_segments_no_match() {
359        let ops = vec![op(Method::GET, "/pets")];
360        let router = PathRouter::build(&ops);
361        assert!(router.match_route(&Method::GET, "/pets/1/extra").is_none());
362    }
363
364    #[test]
365    fn fewer_segments_no_match() {
366        let ops = vec![op(Method::GET, "/pets/{petId}/toys")];
367        let router = PathRouter::build(&ops);
368        assert!(router.match_route(&Method::GET, "/pets/1").is_none());
369    }
370}
specmock_runtime/http/router.rs

specmock_runtime/http/
router.rs
