wayfind 1.0.1

A speedy, flexible router.
Documentation 
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110

use alloc::boxed::Box;
use alloc::collections::BTreeSet;
use alloc::vec::Vec;
use core::cmp::Reverse;

use memchr::memmem::FinderRev;

use crate::node::Node;
use crate::state::StaticState;

/// A single pre-computed suffix pattern.
#[derive(Clone, Debug)]
pub(crate) struct Suffix {
    bytes: Box<[u8]>,
    finder: FinderRev<'static>,
}

impl Suffix {
    fn new(bytes: Vec<u8>) -> Self {
        let finder = FinderRev::new(&bytes).into_owned();
        Self {
            bytes: bytes.into_boxed_slice(),
            finder,
        }
    }

    /// Yields each match position, walking from right to left.
    fn positions<'a>(
        &'a self,
        remaining: &'a [u8],
        cap: usize,
    ) -> impl Iterator<Item = usize> + 'a {
        let initial = (cap + self.bytes.len()).min(remaining.len());
        let first = self.finder.rfind(&remaining[..initial]);
        core::iter::successors(first, move |&end| self.finder.rfind(&remaining[..end]))
    }
}

/// Pre-computed suffix patterns for parameter matching, sorted longest first.
#[derive(Clone, Default, Debug)]
pub(crate) struct Suffixes(Box<[Suffix]>);

impl Suffixes {
    /// The length of the longest suffix.
    ///
    /// Zero when there are no suffixes.
    pub(crate) fn longest(&self) -> usize {
        self.0.first().map_or(0, |suffix| suffix.bytes.len())
    }

    /// Whether the input starts with any suffix.
    pub(crate) fn accepts(&self, after: &[u8]) -> bool {
        self.0.iter().any(|suffix| {
            after.len() >= suffix.bytes.len() && suffix.bytes.iter().zip(after).all(|(a, b)| a == b)
        })
    }

    /// Yields candidate boundary positions, walking from right to left.
    pub(crate) fn positions<'a>(
        &'a self,
        path: &'a str,
        offset: usize,
        cap: usize,
    ) -> impl Iterator<Item = usize> + 'a {
        let remaining = &path.as_bytes()[offset..];
        self.0
            .iter()
            .flat_map(move |suffix| suffix.positions(remaining, cap))
            .filter(|&position| position > 0)
            .filter(move |&position| path.is_char_boundary(offset + position))
    }

    /// Computes the suffix set from a node's static descendants.
    pub(crate) fn compute<S, T>(
        node: &Node<S, T>,
        prefix: &mut Vec<u8>,
        seen: &mut BTreeSet<Vec<u8>>,
    ) -> Self {
        seen.clear();

        for child in &node.static_children {
            Self::walk_static(child, prefix, seen);
        }

        let mut suffixes: Vec<Suffix> = seen.iter().cloned().map(Suffix::new).collect();
        suffixes.sort_by_key(|suffix| Reverse(suffix.bytes.len()));
        Self(suffixes.into_boxed_slice())
    }

    /// Walks a static subtree, recording the accumulated prefix at each node that can terminate a route.
    fn walk_static<T>(
        node: &Node<StaticState, T>,
        prefix: &mut Vec<u8>,
        seen: &mut BTreeSet<Vec<u8>>,
    ) {
        let start = prefix.len();
        prefix.extend_from_slice(&node.state.prefix);

        let is_terminal = node.data.is_some() || node.has_parameters();
        if is_terminal {
            seen.insert(prefix.clone());
        }

        for child in &node.static_children {
            Self::walk_static(child, prefix, seen);
        }

        prefix.truncate(start);
    }
}