Skip to main content

xrack_runtime/
input_pattern.rs

1use regex_automata::{
2    Anchored, Input, MatchKind,
3    dfa::{Automaton, StartKind, dense, sparse},
4    nfa::thompson,
5    util::primitives::StateID,
6};
7use std::{
8    cell::RefCell,
9    collections::{HashMap, HashSet, VecDeque, hash_map::Entry},
10};
11
12const CACHED_PATTERNS: usize = 16;
13
14thread_local! {
15    static PATTERNS: RefCell<VecDeque<(String, Option<InputPattern>)>> =
16        const { RefCell::new(VecDeque::new()) };
17}
18
19/// The validity of a draft relative to the editor's current submission rules.
20#[derive(Clone, Copy, Debug, Default, PartialEq, Eq)]
21pub enum InputValidity {
22    Acceptable,
23    Intermediate,
24    #[default]
25    Invalid,
26}
27
28struct InputPattern {
29    dfa: sparse::DFA<Vec<u8>>,
30    start: StateID,
31    completable: HashSet<StateID>,
32}
33
34impl InputPattern {
35    fn compile(pattern: &str) -> Option<Self> {
36        let dfa = dense::Builder::new()
37            .thompson(thompson::Config::new().nfa_size_limit(Some(1024 * 1024)))
38            .configure(
39                dense::Config::new()
40                    .start_kind(StartKind::Anchored)
41                    .match_kind(MatchKind::All)
42                    .dfa_size_limit(Some(1024 * 1024))
43                    .determinize_size_limit(Some(4 * 1024 * 1024)),
44            )
45            .build(pattern)
46            .ok()?
47            .to_sparse()
48            .ok()?;
49        let start = dfa
50            .start_state_forward(&Input::new("").anchored(Anchored::Yes))
51            .ok()?;
52        let completable = completable_states(&dfa, start);
53        Some(Self {
54            dfa,
55            start,
56            completable,
57        })
58    }
59
60    fn classify(&self, text: &str) -> InputValidity {
61        let mut state = self.start;
62        for byte in text.bytes() {
63            state = self.dfa.next_state(state, byte);
64            if self.dfa.is_dead_state(state) || self.dfa.is_quit_state(state) {
65                return InputValidity::Invalid;
66            }
67        }
68        // The anchored DFA reports matches one byte late. Checking only its
69        // end-of-input transition requires a full match of the draft.
70        if self.dfa.is_match_state(self.dfa.next_eoi_state(state)) {
71            InputValidity::Acceptable
72        } else if self.completable.contains(&state) {
73            InputValidity::Intermediate
74        } else {
75            InputValidity::Invalid
76        }
77    }
78}
79
80fn completable_states(dfa: &sparse::DFA<Vec<u8>>, start: StateID) -> HashSet<StateID> {
81    let mut seen_classes = [false; 256];
82    let alphabet: Vec<u8> = (u8::MIN..=u8::MAX)
83        .filter(|byte| {
84            let seen = &mut seen_classes[usize::from(dfa.byte_classes().get(*byte))];
85            !std::mem::replace(seen, true)
86        })
87        .collect();
88    let mut predecessors = HashMap::from([(start, Vec::new())]);
89    let mut reachable = VecDeque::from([start]);
90    let mut accepting = VecDeque::new();
91    while let Some(state) = reachable.pop_front() {
92        if dfa.is_match_state(dfa.next_eoi_state(state)) {
93            accepting.push_back(state);
94        }
95        for &byte in &alphabet {
96            let next = dfa.next_state(state, byte);
97            if dfa.is_dead_state(next) || dfa.is_quit_state(next) {
98                continue;
99            }
100            match predecessors.entry(next) {
101                Entry::Occupied(mut entry) => entry.get_mut().push(state),
102                Entry::Vacant(entry) => {
103                    entry.insert(vec![state]);
104                    reachable.push_back(next);
105                }
106            }
107        }
108    }
109    let mut completable = HashSet::new();
110    while let Some(state) = accepting.pop_front() {
111        if completable.insert(state)
112            && let Some(previous) = predecessors.remove(&state)
113        {
114            accepting.extend(previous);
115        }
116    }
117    completable
118}
119
120fn with_pattern<T>(pattern: &str, use_pattern: impl FnOnce(&Option<InputPattern>) -> T) -> T {
121    PATTERNS.with_borrow_mut(|cache| {
122        let cached = cache
123            .iter()
124            .position(|(source, _)| source == pattern)
125            .and_then(|index| cache.remove(index));
126        let entry = cached.unwrap_or_else(|| (pattern.to_owned(), InputPattern::compile(pattern)));
127        let result = use_pattern(&entry.1);
128        cache.push_back(entry);
129        if cache.len() > CACHED_PATTERNS {
130            cache.pop_front();
131        }
132        result
133    })
134}
135
136pub(crate) fn pattern_validity(pattern: &str, text: &str) -> InputValidity {
137    if pattern.is_empty() {
138        InputValidity::Acceptable
139    } else {
140        with_pattern(pattern, |entry| {
141            entry
142                .as_ref()
143                .map_or(InputValidity::Invalid, |pattern| pattern.classify(text))
144        })
145    }
146}
147
148#[doc(hidden)]
149pub fn input_pattern_accepts(pattern: &str, text: &str) -> bool {
150    pattern_validity(pattern, text) == InputValidity::Acceptable
151}
152
153pub(crate) fn input_pattern_allows(pattern: &str, text: &str) -> bool {
154    pattern_validity(pattern, text) != InputValidity::Invalid
155}
156
157#[cfg(test)]
158mod tests {
159    use super::{InputPattern, InputValidity::*, pattern_validity};
160
161    #[test]
162    fn separates_complete_inputs_prefixes_and_invalid_drafts() {
163        for (pattern, text, expected) in [
164            ("[A-Z]{2}-[0-9]{3}", "", Intermediate),
165            ("[A-Z]{2}-[0-9]{3}", "AB-12", Intermediate),
166            ("[A-Z]{2}-[0-9]{3}", "AB-123", Acceptable),
167            ("[A-Z]{2}-[0-9]{3}", "AB-1234", Invalid),
168            ("[A-Z]{2}-[0-9]{3}", "AB-x", Invalid),
169            ("a|abc", "a", Acceptable),
170            ("a|abc", "ab", Intermediate),
171            ("a|abc", "abc", Acceptable),
172            ("a|abc", "ax", Invalid),
173            ("(?m)^A$", "A\n", Invalid),
174            (r"\p{L}{2}[0-9]", "中文", Intermediate),
175            (r"\p{L}{2}[0-9]", "中文1", Acceptable),
176            (r"\p{L}{2}[0-9]", "中1", Invalid),
177            ("(?x) A #comment to end of pattern", "A", Acceptable),
178            (r"a\Ab", "", Invalid),
179            ("", "any text", Acceptable),
180        ] {
181            assert_eq!(
182                pattern_validity(pattern, text),
183                expected,
184                "{pattern:?} with {text:?}"
185            );
186        }
187    }
188
189    #[test]
190    fn invalid_dynamic_patterns_reject_both_edits_and_submission() {
191        assert!(InputPattern::compile("[").is_none());
192        assert_eq!(pattern_validity("[", "a"), Invalid);
193        assert!(InputPattern::compile("a{1000000000}").is_none());
194    }
195
196    #[test]
197    fn validity_combines_draft_checks_and_keeps_submission_rules_lazy() {
198        use crate::{InputType, NumericTextLimits, text_input_validity};
199        use std::cell::Cell;
200
201        let calls = Cell::new(0);
202        let validate = |text: &str, mode, mask: &str, pattern: &str, allowed| {
203            text_input_validity(
204                text,
205                mode,
206                || '.',
207                || Some(6),
208                || 2,
209                |_| NumericTextLimits {
210                    maximum: Some(10.0),
211                    ..NumericTextLimits::default()
212                },
213                || mask.to_owned(),
214                || pattern.to_owned(),
215                || {
216                    calls.set(calls.get() + 1);
217                    allowed
218                },
219            )
220        };
221        assert_eq!(validate("xx", InputType::Number, "", "", true), Invalid);
222        assert_eq!(validate("hello!!", InputType::Text, "", "", true), Invalid);
223        assert_eq!(
224            validate("-", InputType::Decimal, "", "", true),
225            Intermediate
226        );
227        assert_eq!(
228            validate("12", InputType::Number, "", "", true),
229            Intermediate
230        );
231        assert_eq!(
232            validate("12-3", InputType::Text, "99-99", "", true),
233            Intermediate
234        );
235        assert_eq!(
236            validate("12-3", InputType::Text, "99-99", "[A-Z]+", true),
237            Invalid
238        );
239        assert_eq!(calls.get(), 0);
240        assert_eq!(
241            validate("12-34", InputType::Text, "99-99", "", false),
242            Intermediate
243        );
244        assert_eq!(
245            validate("12-34", InputType::Text, "99-99", "", true),
246            Acceptable
247        );
248        assert_eq!(calls.get(), 2);
249    }
250}