wtx/http/
matcher.rs

1#[cfg(all(feature = "_bench", test))]
2mod bench;
3#[cfg(test)]
4mod tests;
5
6use crate::{
7  collection::{ArrayVectorU8, ShortBoxStrU8, ShortStrU8, Vector},
8  http::{DEFAULT_MAX_CHILDREN, DEFAULT_MAX_DEPTH},
9  misc::{bytes_pos1, from_utf8_basic},
10};
11use core::{
12  hint::{cold_path, unreachable_unchecked},
13  mem,
14  range::Range,
15  str,
16};
17
18/// Matcher Error
19#[derive(Clone, Copy, Debug)]
20pub enum MatcherError {
21  /// Route already exists
22  AddErrDuplicate,
23  /// Provided adding route is empty
24  AddErrEmpty,
25  /// Route must start with a forward slash or a parameter bracket
26  AddErrInvalidStart,
27  /// For example, `/{foo}-{bar}`.
28  AddErrMultipleRouteParameters,
29  /// Static route parts contain non-ASCII characters
30  AddErrNonAsciiLiteral,
31  /// Parameter names contain non-ASCII characters
32  AddErrNonAsciiParam,
33  /// Maximum number of routes or internal indices exceeded
34  AddErrOverflow,
35  /// Parameters must be followed by a slash or the end of the string
36  AddErrParamSuffix,
37  /// Parameter bracket `{` was not closed with `}`
38  AddErrUnclosedParameterBracket,
39  /// The inner contents of the instance is empty because no routes were added or `MD` is too
40  /// short to accommodate the maximum depth length.
41  FindErrEmpty,
42  /// Route does not exist
43  FindErrMismatch,
44  /// Input string or parameter length exceeds internal limits
45  FindErrOverflow,
46}
47
48/// Decomposes a series of prefixed routes into common nodes to allow fast comparisons with
49/// other dynamic routes.
50///
51/// * `/hey_{anything}/lyrics`: `/hey_/lyrics`, `/hey_you/lyrics`, `/hey_you_what_is_this_now/lyrics`
52#[derive(Clone, Debug)]
53pub struct Matcher<T, const MC: usize = DEFAULT_MAX_CHILDREN, const MD: usize = DEFAULT_MAX_DEPTH> {
54  rows: Vector<Row<T, MC>>,
55}
56
57impl<T, const MC: usize, const MD: usize> Matcher<T, MC, MD> {
58  /// Empty instance
59  #[inline]
60  pub const fn new() -> Self {
61    Self { rows: Vector::new() }
62  }
63}
64
65impl<T, const MC: usize, const MD: usize> Matcher<T, MC, MD> {
66  /// See [`MatcherBuilder`].
67  #[inline]
68  pub fn builder(&mut self) -> MatcherBuilder<'_, T, MC, MD> {
69    self.rows.clear();
70    MatcherBuilder { rows: &mut self.rows }
71  }
72
73  /// Tries to find registered path that corresponds to `route`.
74  #[inline]
75  pub fn find<'this, 'data, 'rslt>(
76    &'this self,
77    route_str: &'data str,
78  ) -> crate::Result<MatcherPath<'rslt, T, MC, MD>>
79  where
80    'data: 'rslt,
81    'this: 'rslt,
82  {
83    let Self { rows } = self;
84    let route_short_str = ShortStrU8::new(route_str)?;
85    let route = route_short_str.into_str().as_bytes();
86    let route_len = route_short_str.len();
87    let curr_route = &mut route_short_str.into_str().as_bytes();
88    let mut edges;
89    let mut path_rows = ArrayVectorU8::new();
90
91    let Some(first_row) = rows.first() else {
92      cold_path();
93      return Err(MatcherError::FindErrEmpty.into());
94    };
95    match Self::check_row(curr_route, &mut path_rows, route_len, first_row, 0) {
96      CheckSearchRowRslt::CompleteMatch(value) => {
97        return Ok(MatcherPath { path_rows, route, rows, value });
98      }
99      CheckSearchRowRslt::IncompleteMatch(local_edges) => edges = local_edges,
100      CheckSearchRowRslt::Mismatch => return Err(MatcherError::FindErrMismatch.into()),
101    }
102
103    loop {
104      let [statics @ .., last] = edges.as_slice() else {
105        return Err(MatcherError::FindErrMismatch.into());
106      };
107      let curr_ident_first = curr_route.first().copied();
108      let last_edge_has_param = last.first_byte.is_none();
109      if last_edge_has_param {
110        if let Some(edge) = statics.iter().find(|el| el.first_byte == curr_ident_first) {
111          match Self::check_edge(*edge, &mut edges, curr_route, &mut path_rows, route_len, rows) {
112            CheckSearchRowRslt::CompleteMatch(value) => {
113              return Ok(MatcherPath { path_rows, route, rows, value });
114            }
115            CheckSearchRowRslt::IncompleteMatch(_) => continue,
116            CheckSearchRowRslt::Mismatch => {}
117          }
118        }
119        match Self::check_edge(*last, &mut edges, curr_route, &mut path_rows, route_len, rows) {
120          CheckSearchRowRslt::CompleteMatch(value) => {
121            return Ok(MatcherPath { path_rows, route, rows, value });
122          }
123          CheckSearchRowRslt::IncompleteMatch(_) => {}
124          CheckSearchRowRslt::Mismatch => cold_path(),
125        }
126      } else {
127        let Some(edge) = edges.iter().find(|el| el.first_byte == curr_ident_first) else {
128          return Err(MatcherError::FindErrMismatch.into());
129        };
130        match Self::check_edge(*edge, &mut edges, curr_route, &mut path_rows, route_len, rows) {
131          CheckSearchRowRslt::CompleteMatch(value) => {
132            return Ok(MatcherPath { path_rows, route, rows, value });
133          }
134          CheckSearchRowRslt::IncompleteMatch(_) => {}
135          CheckSearchRowRslt::Mismatch => return Err(MatcherError::FindErrMismatch.into()),
136        }
137      }
138    }
139  }
140
141  #[inline(always)]
142  fn check_edge<'this>(
143    edge: Edge,
144    edges: &mut &'this ArrayVectorU8<Edge, MC>,
145    curr_route: &mut &'this [u8],
146    path_rows: &mut ArrayVectorU8<PathRow, MD>,
147    route_len: u8,
148    rows: &'this [Row<T, MC>],
149  ) -> CheckSearchRowRslt<'this, T, MC> {
150    let row_idx = edge.row_target_idx;
151    // SAFETY: constructed edges always point to valid row indices
152    let row = unsafe { rows.get(usize::from(row_idx)).unwrap_unchecked() };
153    match Self::check_row(curr_route, path_rows, route_len, row, row_idx) {
154      CheckSearchRowRslt::CompleteMatch(value) => CheckSearchRowRslt::CompleteMatch(value),
155      CheckSearchRowRslt::IncompleteMatch(local_edges) => {
156        *edges = local_edges;
157        CheckSearchRowRslt::IncompleteMatch(local_edges)
158      }
159      CheckSearchRowRslt::Mismatch => CheckSearchRowRslt::Mismatch,
160    }
161  }
162
163  #[inline(always)]
164  fn check_row<'this>(
165    curr_route: &mut &'this [u8],
166    path_rows: &mut ArrayVectorU8<PathRow, MD>,
167    route_len: u8,
168    row: &'this Row<T, MC>,
169    row_idx: u8,
170  ) -> CheckSearchRowRslt<'this, T, MC> {
171    match row.ty {
172      RowTy::Literal => {
173        if let Some(rest) = curr_route.strip_prefix(row.route.as_bytes()) {
174          *curr_route = rest;
175        } else {
176          return CheckSearchRowRslt::Mismatch;
177        }
178      }
179      #[expect(
180        clippy::as_conversions,
181        clippy::cast_possible_truncation,
182        reason = "full routes are limited by 255, subroutes are smaller"
183      )]
184      RowTy::Param => {
185        // For some reason `memchr` degrades the performance if `target-cpu=native`.
186        let (param, rest) = if let Some(param_end_idx) = bytes_pos1(*curr_route, b'/') {
187          // SAFETY: the index has just been checked
188          unsafe { curr_route.split_at_checked(param_end_idx).unwrap_unchecked() }
189        } else {
190          (*curr_route, &[][..])
191        };
192        let begin_idx = route_len.wrapping_sub(curr_route.len() as u8);
193        let end_idx = begin_idx.wrapping_add(param.len() as u8);
194        // SAFETY: The Drop implementation of `MatcherBuilder` guarantees that `MD` will never
195        //         be lesser than the maximum depth of this instance.
196        unsafe {
197          path_rows.push(PathRow::new((begin_idx..end_idx).into(), row_idx)).unwrap_unchecked();
198        }
199        *curr_route = rest;
200      }
201    }
202    if let ([], Some(value)) = (curr_route, &row.value) {
203      return CheckSearchRowRslt::CompleteMatch(value);
204    }
205    CheckSearchRowRslt::IncompleteMatch(&row.edges)
206  }
207}
208
209impl<T> Default for Matcher<T> {
210  #[inline]
211  fn default() -> Self {
212    Self::new()
213  }
214}
215
216/// Constructs routes
217#[derive(Debug)]
218pub struct MatcherBuilder<
219  'instance,
220  T,
221  const MC: usize = DEFAULT_MAX_CHILDREN,
222  const MD: usize = DEFAULT_MAX_DEPTH,
223> {
224  rows: &'instance mut Vector<Row<T, MC>>,
225}
226
227impl<T, const MC: usize, const MD: usize> MatcherBuilder<'_, T, MC, MD> {
228  /// Adds a new route and its associated value.
229  #[inline]
230  pub fn add(&mut self, route: &ShortBoxStrU8, value: T) -> crate::Result<&mut Self> {
231    let mut curr_bytes_idx = 0;
232    loop {
233      let (mut local_route, local_ty) = Self::manage_row_ty(route.as_bytes(), &mut curr_bytes_idx)?;
234      let final_row_idx = Self::add_local_route(&mut local_route, local_ty, self.rows)?;
235      let should_stop = curr_bytes_idx >= usize::from(route.len());
236      if should_stop {
237        if let Some(row) = self.rows.get_mut(usize::from(final_row_idx)) {
238          if row.value.is_some() {
239            return Err(MatcherError::AddErrDuplicate.into());
240          }
241          row.value = Some(value);
242        }
243        return Ok(self);
244      }
245    }
246  }
247
248  #[inline]
249  fn add_local_route(
250    local_route: &mut &[u8],
251    local_ty: RowTy,
252    rows: &mut Vector<Row<T, MC>>,
253  ) -> crate::Result<u8> {
254    let mut row_idx = 0;
255
256    let mut edges = if let Some(row) = rows.first() {
257      let crr = Self::compare_row(local_route, row)?;
258      match crr {
259        CompareRowRslt::Finished => {
260          return Ok(row_idx);
261        }
262        CompareRowRslt::RowFull(edges) => edges,
263        CompareRowRslt::RowPartial { common_prefix_len, is_single } => {
264          Self::add_row((local_route, local_ty), common_prefix_len, is_single, &mut row_idx, rows)?;
265          return Ok(row_idx);
266        }
267        // Unreachable because all routes must start with '/'
268        CompareRowRslt::Unmatched => return Ok(row_idx),
269      }
270    } else {
271      let row_route = from_utf8_basic(local_route)?.try_into()?;
272      rows.push(Row::new(ArrayVectorU8::new(), row_route, local_ty, None))?;
273      return Ok(row_idx);
274    };
275
276    'outer: loop {
277      'inner: for edge in edges {
278        let Some(row) = rows.get_mut(usize::from(edge.row_target_idx)) else {
279          break 'inner;
280        };
281        let crr = Self::compare_row(local_route, row)?;
282        match crr {
283          CompareRowRslt::Finished => {
284            return Ok(edge.row_target_idx);
285          }
286          CompareRowRslt::RowFull(local_edges) => {
287            row_idx = edge.row_target_idx;
288            edges = local_edges;
289            continue 'outer;
290          }
291          CompareRowRslt::RowPartial { common_prefix_len, is_single } => {
292            row_idx = edge.row_target_idx;
293            Self::add_row(
294              (local_route, local_ty),
295              common_prefix_len,
296              is_single,
297              &mut row_idx,
298              rows,
299            )?;
300            return Ok(row_idx);
301          }
302          CompareRowRslt::Unmatched => {}
303        }
304      }
305      Self::add_row((local_route, local_ty), 0, true, &mut row_idx, rows)?;
306      return Ok(row_idx);
307    }
308  }
309
310  #[inline]
311  fn add_row(
312    (route, ty): (&[u8], RowTy),
313    common_prefix_len: usize,
314    is_single: bool,
315    row_idx: &mut u8,
316    rows: &mut Vector<Row<T, MC>>,
317  ) -> crate::Result<()> {
318    let route_str: ShortBoxStrU8 = route.try_into()?;
319    let parent_idx = usize::from(*row_idx);
320    if is_single {
321      let child_idx = u8::try_from(rows.len()).map_err(|_err| MatcherError::AddErrOverflow)?;
322      if route_str.is_empty() {
323        let Some(parent) = rows.get_mut(parent_idx) else {
324          return Ok(());
325        };
326        let child_edges = mem::take(&mut parent.edges);
327        let child_route = unique_route(common_prefix_len, &parent.route)?;
328        let child_value = parent.value.take();
329        parent.edges.push(Edge::new(None, child_idx))?;
330        parent.route = common_route(common_prefix_len, &parent.route)?;
331        parent.ty = ty;
332        rows.push(Row::new(child_edges, child_route, ty, child_value))?;
333      } else {
334        let Some(parent) = rows.get_mut(parent_idx) else {
335          return Ok(());
336        };
337        parent.edges.push(Edge::new(None, child_idx))?;
338        rows.push(Row::new(ArrayVectorU8::new(), route_str, ty, None))?;
339        *row_idx = child_idx;
340      }
341    } else {
342      let child0_idx = u8::try_from(rows.len()).map_err(|_err| MatcherError::AddErrOverflow)?;
343      let child1_idx = child0_idx.checked_add(1).ok_or(MatcherError::AddErrOverflow)?;
344      let Some(parent) = rows.get_mut(parent_idx) else {
345        return Ok(());
346      };
347      let child0_edges = mem::take(&mut parent.edges);
348      let child0_route = unique_route(common_prefix_len, &parent.route)?;
349      let child0_value = parent.value.take();
350      parent.edges.push(Edge::new(None, child0_idx))?;
351      parent.edges.push(Edge::new(None, child1_idx))?;
352      parent.route = common_route(common_prefix_len, &parent.route)?;
353      rows.push(Row::new(child0_edges, child0_route, RowTy::Literal, child0_value))?;
354      rows.push(Row::new(ArrayVectorU8::new(), route_str, ty, None))?;
355      *row_idx = child1_idx;
356    }
357
358    Ok(())
359  }
360
361  #[inline]
362  fn common_prefix_len(lhs: &[u8], rhs: &[u8]) -> usize {
363    lhs.iter().zip(rhs).take_while(|(b0, b1)| b0 == b1).count()
364  }
365
366  #[inline]
367  fn compare_row(route: &mut &[u8], row: &Row<T, MC>) -> crate::Result<CompareRowRslt<MC>> {
368    if row.ty == RowTy::Param {
369      if route.first() == Some(&b'{')
370        && let Some(idx) = bytes_pos1(*route, b'}')
371        && let Some((lhs, rhs)) = route.split_at_checked(idx.wrapping_add(1))
372      {
373        if lhs == row.route.as_bytes() {
374          *route = rhs;
375          if rhs.is_empty() {
376            return Ok(CompareRowRslt::Finished);
377          }
378          return Ok(CompareRowRslt::RowFull(row.edges.clone()));
379        }
380        return Err(MatcherError::AddErrMultipleRouteParameters.into());
381      }
382      return Ok(CompareRowRslt::Unmatched);
383    }
384
385    let row_route = row.route.as_bytes();
386    let common_prefix_len = Self::common_prefix_len(route, row_route);
387    let (_lhs, rhs) = route.split_at_checked(common_prefix_len).unwrap_or_default();
388    let is_row_fulfilled = common_prefix_len == row_route.len();
389    if common_prefix_len == 0 {
390      Ok(CompareRowRslt::Unmatched)
391    } else if is_row_fulfilled {
392      *route = rhs;
393      if rhs.is_empty() {
394        return Ok(CompareRowRslt::Finished);
395      }
396      Ok(CompareRowRslt::RowFull(row.edges.clone()))
397    } else {
398      *route = rhs;
399      Ok(CompareRowRslt::RowPartial { common_prefix_len, is_single: rhs.is_empty() })
400    }
401  }
402
403  /// Breaks `/a/{}/b/c-{}` into `/a/`, `{}`, `/b` and `/c-{}`.
404  #[inline]
405  fn manage_row_ty<'bytes>(
406    bytes: &'bytes [u8],
407    curr_bytes_idx: &mut usize,
408  ) -> crate::Result<(&'bytes [u8], RowTy)> {
409    let curr_bytes = bytes.get(*curr_bytes_idx..).unwrap_or_default();
410    let Some(([first], rest)) = curr_bytes.split_at_checked(1) else {
411      return Err(MatcherError::AddErrEmpty.into());
412    };
413    let mut iter = rest.iter();
414    let mut route_end_idx: u8 = 1;
415    match first {
416      b'{' => {
417        for byte in iter.by_ref() {
418          match byte {
419            b'{' => return Err(MatcherError::AddErrMultipleRouteParameters.into()),
420            b'}' => {
421              let next = iter.next().copied();
422              if next.is_some() && next != Some(b'/') {
423                return Err(MatcherError::AddErrParamSuffix.into());
424              }
425              route_end_idx = route_end_idx.checked_add(1).ok_or(MatcherError::AddErrOverflow)?;
426              *curr_bytes_idx = curr_bytes_idx.wrapping_add(route_end_idx.into());
427              let route = bytes.get(..*curr_bytes_idx).unwrap_or_default();
428              return Ok((route, RowTy::Param));
429            }
430            other => {
431              if !other.is_ascii_graphic() {
432                return Err(MatcherError::AddErrNonAsciiParam.into());
433              }
434            }
435          }
436          route_end_idx = route_end_idx.checked_add(1).ok_or(MatcherError::AddErrOverflow)?;
437        }
438        Err(MatcherError::AddErrUnclosedParameterBracket.into())
439      }
440      b'/' => {
441        for byte in iter {
442          match byte {
443            b'{' => break,
444            other => {
445              if !other.is_ascii_graphic() {
446                return Err(MatcherError::AddErrNonAsciiLiteral.into());
447              }
448            }
449          }
450          route_end_idx = route_end_idx.checked_add(1).ok_or(MatcherError::AddErrOverflow)?;
451        }
452        *curr_bytes_idx = curr_bytes_idx.wrapping_add(route_end_idx.into());
453        let route = bytes.get(..*curr_bytes_idx).unwrap_or_default();
454        Ok((route, RowTy::Literal))
455      }
456      _ => Err(MatcherError::AddErrInvalidStart.into()),
457    }
458  }
459}
460
461impl<T, const MC: usize, const MD: usize> Drop for MatcherBuilder<'_, T, MC, MD> {
462  #[inline]
463  fn drop(&mut self) {
464    #[inline]
465    fn evaluate_max_depth<T, const MC: usize, const MD: usize>(rows: &mut Vector<Row<T, MC>>) {
466      let mut depths = alloc::vec![0u8; rows.len()];
467      let mut max_depth = 0;
468      for (idx, row) in rows.iter().enumerate() {
469        let next_depth = {
470          let Some(curr_depth) = depths.get(idx) else {
471            continue;
472          };
473          if row.ty == RowTy::Param { curr_depth.saturating_add(1) } else { *curr_depth }
474        };
475        if next_depth > max_depth {
476          max_depth = next_depth;
477        }
478        for edge in &row.edges {
479          let target = usize::from(edge.row_target_idx);
480          if target >= depths.len() {
481            continue;
482          }
483          let Some(depth) = depths.get_mut(target) else {
484            continue;
485          };
486          *depth = next_depth;
487        }
488      }
489      if usize::from(max_depth) > MD {
490        rows.clear();
491      }
492    }
493
494    #[inline]
495    fn fill_first_bytes<T, const MC: usize>(rows: &mut Vector<Row<T, MC>>) {
496      let mut row_idx: usize = 0;
497      while row_idx < rows.len() {
498        let mut first_bytes = ArrayVectorU8::<_, MC>::new();
499        if let Some(row) = rows.get(row_idx) {
500          for edge in &row.edges {
501            let Some(target_row) = rows.get(usize::from(edge.row_target_idx)) else {
502              continue;
503            };
504            let first = match target_row.ty {
505              RowTy::Literal => target_row.route.as_bytes().first().copied(),
506              RowTy::Param => None,
507            };
508            let _rslt = first_bytes.push(first);
509          }
510        }
511        if let Some(row) = rows.get_mut(row_idx) {
512          for (edge, first_byte) in row.edges.iter_mut().zip(first_bytes) {
513            edge.first_byte = first_byte;
514          }
515        }
516        row_idx = row_idx.wrapping_add(1);
517      }
518      for row in rows {
519        let Some(param_idx) = row.edges.iter().position(|el| el.first_byte.is_none()) else {
520          continue;
521        };
522        let last_idx = row.edges.len().wrapping_sub(1).into();
523        row.edges.swap(param_idx, last_idx);
524      }
525    }
526
527    #[inline]
528    fn sort_by_the_number_of_children<T, const MC: usize>(rows: &mut Vector<Row<T, MC>>) {
529      let mut weights = alloc::vec![0u32; rows.len()];
530      for idx in (0..rows.len()).rev() {
531        let Some(row) = rows.get(idx) else {
532          continue;
533        };
534        let mut weight = u32::from(row.value.is_some());
535        for edge in &row.edges {
536          let weight_node = weights.get(usize::from(edge.row_target_idx)).copied();
537          weight = weight.wrapping_add(weight_node.unwrap_or_default());
538        }
539        if let Some(elem) = weights.get_mut(idx) {
540          *elem = weight;
541        }
542      }
543      for row in rows {
544        row.edges.sort_unstable_by(|lhs, rhs| {
545          let weight_a = weights.get(usize::from(lhs.row_target_idx)).copied().unwrap_or_default();
546          let weight_b = weights.get(usize::from(rhs.row_target_idx)).copied().unwrap_or_default();
547          weight_b.cmp(&weight_a)
548        });
549      }
550    }
551
552    sort_by_the_number_of_children(self.rows);
553    fill_first_bytes(self.rows);
554    evaluate_max_depth::<_, _, MD>(self.rows);
555  }
556}
557
558/// Path constructed from a root route
559#[derive(Debug, PartialEq)]
560pub struct MatcherPath<
561  'any,
562  T,
563  const MC: usize = DEFAULT_MAX_CHILDREN,
564  const MD: usize = DEFAULT_MAX_DEPTH,
565> {
566  path_rows: ArrayVectorU8<PathRow, MD>,
567  route: &'any [u8],
568  rows: &'any Vector<Row<T, MC>>,
569  value: &'any T,
570}
571
572impl<T, const MC: usize, const MD: usize> MatcherPath<'_, T, MC, MD> {
573  /// User data originated from a route
574  #[inline]
575  pub fn data(&self) -> &T {
576    self.value
577  }
578
579  /// Gets a parameter according to its index that is related to the entire URI.
580  #[inline]
581  pub fn param_by_idx(&self, idx: usize) -> Option<MatcherPathParam<'_>> {
582    self.params().nth(idx)
583  }
584
585  /// Gets a parameter according to its declared name.
586  #[inline]
587  pub fn param_by_name(&self, name: &[u8]) -> Option<MatcherPathParam<'_>> {
588    self.params().find(|el| el.name.as_bytes() == name)
589  }
590
591  /// Iterator over all parameters
592  #[inline]
593  pub fn params(&self) -> impl Iterator<Item = MatcherPathParam<'_>> {
594    let Self { path_rows, route, rows, .. } = self;
595    path_rows.iter().filter_map(|PathRow { ident_param_range, row_idx }| {
596      let row = rows.get(usize::from(*row_idx))?;
597      let name = match row.ty {
598        RowTy::Literal => return None,
599        RowTy::Param => {
600          if let [_, name @ .., _] = row.route.as_bytes() {
601            // SAFETY: all routes are graphic ASCII
602            unsafe { str::from_utf8_unchecked(name) }
603          } else {
604            // SAFETY: all parameters are captured with their braces included
605            unsafe { unreachable_unchecked() }
606          }
607        }
608      };
609      // SAFETY: every route is originated from a string
610      let value = unsafe {
611        let range = ident_param_range.start.into()..ident_param_range.end.into();
612        str::from_utf8_unchecked(route.get(range)?)
613      };
614      Some(MatcherPathParam::new(name, value))
615    })
616  }
617}
618
619/// Route match parameter
620#[derive(Clone, Copy, Debug, PartialEq)]
621pub struct MatcherPathParam<'any> {
622  /// Identifies the parameter and is defined when building the route.
623  pub name: &'any str,
624  /// Dynamic value associated with the name.
625  pub value: &'any str,
626}
627
628impl<'any> MatcherPathParam<'any> {
629  /// Shortcut
630  #[inline]
631  pub const fn new(name: &'any str, value: &'any str) -> Self {
632    Self { name, value }
633  }
634}
635
636#[derive(Clone, Copy, Debug, PartialEq)]
637enum CheckSearchRowRslt<'any, T, const MC: usize = DEFAULT_MAX_CHILDREN> {
638  CompleteMatch(&'any T),
639  IncompleteMatch(&'any ArrayVectorU8<Edge, MC>),
640  Mismatch,
641}
642
643#[derive(Clone, Debug, PartialEq)]
644enum CompareRowRslt<const MC: usize = DEFAULT_MAX_CHILDREN> {
645  Finished,
646  RowFull(ArrayVectorU8<Edge, MC>),
647  RowPartial { common_prefix_len: usize, is_single: bool },
648  Unmatched,
649}
650
651#[derive(Clone, Copy, Debug, PartialEq)]
652enum RowTy {
653  Literal,
654  Param,
655}
656
657/// An edge is also a piece of data in CSR terms.
658#[derive(Clone, Copy, Debug, PartialEq)]
659struct Edge {
660  // If the target node is a parameter, then the first byte will always be 'None'.
661  first_byte: Option<u8>,
662  row_target_idx: u8,
663}
664
665impl Edge {
666  #[inline]
667  const fn new(first_byte: Option<u8>, row_target_idx: u8) -> Self {
668    Self { first_byte, row_target_idx }
669  }
670}
671
672#[derive(Clone, Copy, Debug, PartialEq)]
673struct PathRow {
674  ident_param_range: Range<u8>,
675  row_idx: u8,
676}
677
678impl PathRow {
679  #[inline]
680  const fn new(ident_param_range: Range<u8>, row_idx: u8) -> Self {
681    Self { ident_param_range, row_idx }
682  }
683}
684
685/// A row can have at-most one parameter and a row is also a node in CSR terms.
686///
687/// Intermediate rows refer common prefixes shared by other routes while final rows are unique.
688///
689/// Leaf rows are always guarantee to have non-null values. Intermediate rows may or may not
690/// have values.
691#[derive(Clone, Debug, PartialEq)]
692struct Row<T, const MC: usize = DEFAULT_MAX_CHILDREN> {
693  edges: ArrayVectorU8<Edge, MC>,
694  route: ShortBoxStrU8,
695  ty: RowTy,
696  value: Option<T>,
697}
698
699impl<T, const MC: usize> Row<T, MC> {
700  #[inline]
701  const fn new(
702    edges: ArrayVectorU8<Edge, MC>,
703    route: ShortBoxStrU8,
704    ty: RowTy,
705    value: Option<T>,
706  ) -> Self {
707    Self { edges, route, ty, value }
708  }
709}
710
711#[inline]
712fn common_route(
713  common_prefix_len: usize,
714  common_route: &ShortBoxStrU8,
715) -> crate::Result<ShortBoxStrU8> {
716  common_route.get(..common_prefix_len).unwrap_or_default().try_into()
717}
718
719#[inline]
720fn unique_route(
721  common_prefix_len: usize,
722  common_route: &ShortBoxStrU8,
723) -> crate::Result<ShortBoxStrU8> {
724  common_route.get(common_prefix_len..).unwrap_or_default().try_into()
725}
wtx/http/matcher.rs

wtx/http/
matcher.rs
