qbrsh 0.2.0

A fast, keyboard-driven web browser
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
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126

//! A trie for O(k) key-sequence matching.
//!
//! Each path from the root to a node carrying a command represents a complete
//! keybinding. Prefix matching distinguishes partial input from complete
//! bindings; commands are stored as strings parsed by [`Command::parse`].
//!
//! [`Command::parse`]: crate::core::command::Command::parse

use std::collections::HashMap;

use crate::core::key::Key;

/// Result of looking up a key sequence.
#[derive(Debug, Clone, PartialEq, Eq)]
pub enum TrieMatch {
    /// No binding starts with this sequence.
    None,
    /// Some bindings have this as a prefix, but no exact match yet.
    Partial,
    /// Exact match; carries the command string.
    Exact(String),
    /// Exact match that is also a prefix of longer bindings.
    Ambiguous(String),
}

#[derive(Debug, Default)]
struct TrieNode {
    children: HashMap<Key, TrieNode>,
    command: Option<String>,
}

/// A prefix tree mapping key sequences to command strings.
#[derive(Debug, Default)]
pub struct BindingTrie {
    root: TrieNode,
}

impl BindingTrie {
    pub fn new() -> Self {
        Self::default()
    }

    /// Insert a binding mapping `keys` to `command`.
    pub fn insert(&mut self, keys: &[Key], command: String) {
        let mut node = &mut self.root;
        for key in keys {
            node = node.children.entry(key.clone()).or_default();
        }
        node.command = Some(command);
    }

    /// Look up a key sequence.
    pub fn lookup(&self, keys: &[Key]) -> TrieMatch {
        let mut node = &self.root;
        for key in keys {
            match node.children.get(key) {
                Some(child) => node = child,
                None => return TrieMatch::None,
            }
        }
        match (&node.command, node.children.is_empty()) {
            (Some(cmd), true) => TrieMatch::Exact(cmd.clone()),
            (Some(cmd), false) => TrieMatch::Ambiguous(cmd.clone()),
            (None, _) => TrieMatch::Partial,
        }
    }
}

#[cfg(test)]
mod tests {
    use super::*;
    use crate::core::key::Key;

    #[test]
    fn single_key_exact() {
        let mut t = BindingTrie::new();
        t.insert(&[Key::plain("j")], "scroll down".into());
        assert_eq!(
            t.lookup(&[Key::plain("j")]),
            TrieMatch::Exact("scroll down".into())
        );
    }

    #[test]
    fn multi_key_partial_then_exact() {
        let mut t = BindingTrie::new();
        t.insert(&[Key::plain("g"), Key::plain("g")], "scroll-to-perc 0".into());
        assert_eq!(t.lookup(&[Key::plain("g")]), TrieMatch::Partial);
        assert_eq!(
            t.lookup(&[Key::plain("g"), Key::plain("g")]),
            TrieMatch::Exact("scroll-to-perc 0".into())
        );
    }

    #[test]
    fn unknown_is_none() {
        let mut t = BindingTrie::new();
        t.insert(&[Key::plain("j")], "scroll down".into());
        assert_eq!(t.lookup(&[Key::plain("x")]), TrieMatch::None);
    }

    #[test]
    fn modifiers_distinguish_bindings() {
        let mut t = BindingTrie::new();
        t.insert(&[Key::plain("f")], "hint".into());
        t.insert(
            &[Key {
                sym: "f".into(),
                ctrl: true,
                alt: false,
                shift: false,
            }],
            "scroll-page down".into(),
        );
        assert_eq!(t.lookup(&[Key::plain("f")]), TrieMatch::Exact("hint".into()));
        assert_eq!(
            t.lookup(&[Key {
                sym: "f".into(),
                ctrl: true,
                alt: false,
                shift: false
            }]),
            TrieMatch::Exact("scroll-page down".into())
        );
    }
}