hyperbuild/
pattern.rs

1// Can't use pub const fn constructor due to Copy trait, so allow directly creating struct publicly for now.
2pub struct TrieNode<V: 'static + Copy> {
3    // Using a children array of size 256 would probably be fastest, but waste too much memory and cause slow compiles
4    // and large binaries. Instead, we only store the children between the first and last defined (see `gen/trie.ts`).
5    // When getting a child, use `index - offset`.
6    pub offset: usize,
7    pub value: Option<V>,
8    pub children: &'static [Option<&'static TrieNode<V>>],
9}
10
11pub enum TrieNodeMatch<V: 'static + Copy> {
12    Found { len: usize, value: V },
13    NotFound { reached: usize },
14}
15
16impl<V: 'static + Copy> TrieNode<V> {
17    // Find the node that matches the shortest prefix of {@param text} that:
18    // - has a value (except the start node if it has a value);
19    // - fails to match any further characters (the node itself matches); or,
20    // - the entire text (essentially same as previous point).
21    //
22    // For example, given a trie with only two paths "&amp" and "&amp;":
23    // - "&amp" will return node `p`.
24    // - "&ampere" will return node `p`.
25    // - "&amp;" will return node `p`.
26    // - "&amp;ere" will return node `p`.
27    // - "&am" will return node `m`.
28    //   - Further matching "p;" will return node `p`.
29    //   - Further matching "xyz" will return node `m` (itself).
30    // - "&amx" will return node `m`.
31    // - "&ax" will return node `a`.
32    // - "+ax" will return itself.
33    // - "" will return the itself.
34    #[inline(always)]
35    pub fn shortest_matching_prefix(&self, text: &[u8], from: usize) -> (&TrieNode<V>, usize) {
36        let mut node: &TrieNode<V> = self;
37        let mut pos = from;
38        while let Some(&c) = text.get(pos) {
39            match node.children.get((c as usize).wrapping_sub(node.offset)) {
40                Some(Some(child)) => node = child,
41                None | Some(None) => break,
42            };
43            pos += 1;
44            if node.value.is_some() {
45                break;
46            };
47        };
48        (node, pos)
49    }
50
51    #[inline(always)]
52    pub fn longest_matching_prefix(&self, text: &[u8]) -> TrieNodeMatch<V> {
53        let mut node: &TrieNode<V> = self;
54        let mut value: Option<TrieNodeMatch<V>> = None;
55        let mut pos = 0;
56        while let Some(&c) = text.get(pos) {
57            match node.children.get((c as usize).wrapping_sub(node.offset)) {
58                Some(Some(child)) => node = child,
59                None | Some(None) => break,
60            };
61            pos += 1;
62            match node.value {
63                Some(v) => value = Some(TrieNodeMatch::Found { len: pos, value: v }),
64                None => {}
65            };
66        };
67        value.unwrap_or(TrieNodeMatch::NotFound { reached: pos })
68    }
69}
hyperbuild/pattern.rs

hyperbuild/
pattern.rs
