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#[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 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}