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

use alloc::boxed::Box;
use alloc::collections::{BTreeMap, BTreeSet};
use alloc::vec::Vec;

use crate::bounds::Bounds;
use crate::builder::BuilderNode;
use crate::node::{DynamicSearch, Node, WildcardSearch};
use crate::reachable::Reachable;
use crate::router::Router;
use crate::state::{DynamicState, RootState, StaticState, WildcardState};
use crate::suffixes::Suffixes;

/// Compiles a builder tree into an optimized tree.
pub(crate) struct Compiler {
    needles: BTreeMap<Box<[u8]>, usize>,
}

impl Compiler {
    pub(crate) fn run<T>(builder: BuilderNode<RootState, T>) -> Router<T> {
        let mut compiler = Self {
            needles: BTreeMap::new(),
        };

        let root = compiler.compile(builder);
        Router::new(root)
    }

    fn compile<S, T>(&mut self, builder: BuilderNode<S, T>) -> Node<S, T> {
        let mut static_children: Vec<Node<StaticState, T>> = builder
            .static_children
            .into_iter()
            .map(|child| self.compile(child))
            .collect();

        let mut seen = BTreeSet::new();
        let mut prefix = Vec::new();

        let mut dynamic_children: Vec<Node<DynamicState, T>> = builder
            .dynamic_children
            .into_iter()
            .map(|child| self.compile(child))
            .collect();

        for child in &mut dynamic_children {
            child.suffixes = Suffixes::compute(child, &mut prefix, &mut seen);
        }

        let mut wildcard_children: Vec<Node<WildcardState, T>> = builder
            .wildcard_children
            .into_iter()
            .map(|child| self.compile(child))
            .collect();

        for child in &mut wildcard_children {
            child.suffixes = Suffixes::compute(child, &mut prefix, &mut seen);
        }

        static_children.sort_by(|a, b| a.state.prefix.cmp(&b.state.prefix));

        dynamic_children.sort_by(|a, b| {
            b.suffixes
                .longest()
                .cmp(&a.suffixes.longest())
                .then_with(|| a.state.name.cmp(&b.state.name))
        });

        wildcard_children.sort_by(|a, b| {
            b.suffixes
                .longest()
                .cmp(&a.suffixes.longest())
                .then_with(|| a.state.name.cmp(&b.state.name))
        });

        let dynamic_search = if dynamic_children.iter().all(Node::is_segment_only) {
            DynamicSearch::Segment
        } else {
            DynamicSearch::Inline
        };

        let wildcard_search = if wildcard_children.iter().all(Node::is_segment_only) {
            WildcardSearch::Segment
        } else {
            WildcardSearch::Inline
        };

        let mut node = Node {
            state: builder.state,
            data: builder.data,

            static_children: static_children.into_boxed_slice(),
            dynamic_children: dynamic_children.into_boxed_slice(),
            wildcard_children: wildcard_children.into_boxed_slice(),
            end_wildcard: builder.end_wildcard,

            bounds: Bounds::default(),
            reachable: Reachable::default(),
            suffixes: Suffixes::default(),

            dynamic_search,
            wildcard_search,
        };

        node.bounds = Bounds::compute(&node);
        node.reachable = Reachable::compute(&node, &mut self.needles);

        node
    }
}