Skip to main content

codewhale_runtime/
regex_cache.rs

1//! Compiled-regex cache for patterns a user or model supplies (tool search,
2//! purge). Those patterns are untrusted input, so compilation is bounded:
3//! the pattern length is capped, the compiled program and lazy DFA have
4//! explicit size limits, compilation runs outside the cache lock, and a
5//! rejected pattern is remembered so repeating it costs a lookup.
6
7use std::num::NonZeroUsize;
8use std::sync::{Mutex, OnceLock};
9
10use lru::LruCache;
11use regex::{Regex, RegexBuilder};
12
13const DEFAULT_USER_REGEX_CACHE_CAPACITY: usize = 64;
14/// Longest pattern accepted, in bytes. Search and purge patterns are short.
15pub const MAX_USER_REGEX_PATTERN_BYTES: usize = 4 * 1024;
16/// Compiled program limit (the `regex` default is 10 MiB).
17const USER_REGEX_SIZE_LIMIT: usize = 1024 * 1024;
18/// Lazy DFA cache limit per matcher.
19const USER_REGEX_DFA_SIZE_LIMIT: usize = 1024 * 1024;
20
21static USER_REGEX_CACHE: OnceLock<UserRegexCache> = OnceLock::new();
22
23pub fn compile_user_regex(pattern: &str) -> Result<Regex, regex::Error> {
24    user_regex_cache().compile(pattern, false)
25}
26
27pub fn compile_user_regex_case_insensitive(pattern: &str) -> Result<Regex, regex::Error> {
28    user_regex_cache().compile(pattern, true)
29}
30
31fn user_regex_cache() -> &'static UserRegexCache {
32    USER_REGEX_CACHE.get_or_init(UserRegexCache::new)
33}
34
35fn compile_bounded(pattern: &str, case_insensitive: bool) -> Result<Regex, regex::Error> {
36    if pattern.len() > MAX_USER_REGEX_PATTERN_BYTES {
37        return Err(regex::Error::Syntax(format!(
38            "pattern is {} bytes; the limit is {MAX_USER_REGEX_PATTERN_BYTES}",
39            pattern.len()
40        )));
41    }
42    RegexBuilder::new(pattern)
43        .case_insensitive(case_insensitive)
44        .size_limit(USER_REGEX_SIZE_LIMIT)
45        .dfa_size_limit(USER_REGEX_DFA_SIZE_LIMIT)
46        .build()
47}
48
49struct UserRegexCache {
50    /// Compiled patterns and rejected ones alike, so a repeated bad pattern
51    /// is not recompiled.
52    inner: Mutex<LruCache<(String, bool), Result<Regex, regex::Error>>>,
53}
54
55impl UserRegexCache {
56    fn new() -> Self {
57        Self::with_capacity(
58            NonZeroUsize::new(DEFAULT_USER_REGEX_CACHE_CAPACITY).expect("non-zero capacity"),
59        )
60    }
61
62    fn with_capacity(capacity: NonZeroUsize) -> Self {
63        Self {
64            inner: Mutex::new(LruCache::new(capacity)),
65        }
66    }
67
68    fn compile(&self, pattern: &str, case_insensitive: bool) -> Result<Regex, regex::Error> {
69        // An over-long pattern is refused before it is hashed or stored.
70        if pattern.len() > MAX_USER_REGEX_PATTERN_BYTES {
71            return compile_bounded(pattern, case_insensitive);
72        }
73        let key = (pattern.to_string(), case_insensitive);
74        if let Ok(mut cache) = self.inner.lock()
75            && let Some(cached) = cache.get(&key)
76        {
77            return cached.clone();
78        }
79        // Compile without the lock: one slow pattern must not stall every
80        // other caller. Two racing misses both compile; the result is equal.
81        let compiled = compile_bounded(pattern, case_insensitive);
82        if let Ok(mut cache) = self.inner.lock() {
83            cache.put(key, compiled.clone());
84        }
85        compiled
86    }
87
88    #[cfg(test)]
89    fn len(&self) -> usize {
90        self.inner.lock().expect("cache lock").len()
91    }
92
93    #[cfg(test)]
94    fn contains(&self, pattern: &str) -> bool {
95        self.inner
96            .lock()
97            .expect("cache lock")
98            .contains(&(pattern.to_string(), false))
99    }
100}
101
102#[cfg(test)]
103mod tests {
104    use super::*;
105
106    #[test]
107    fn repeated_pattern_uses_one_cache_entry() {
108        let cache = UserRegexCache::with_capacity(NonZeroUsize::new(2).unwrap());
109
110        let first = cache.compile("alpha|beta", false).expect("regex compiles");
111        let second = cache.compile("alpha|beta", false).expect("regex cache hit");
112
113        assert!(first.is_match("alpha"));
114        assert!(second.is_match("beta"));
115        assert_eq!(cache.len(), 1);
116    }
117
118    #[test]
119    fn capacity_evicts_least_recently_used_pattern() {
120        let cache = UserRegexCache::with_capacity(NonZeroUsize::new(2).unwrap());
121
122        cache.compile("one", false).expect("one compiles");
123        cache.compile("two", false).expect("two compiles");
124        cache.compile("one", false).expect("one is refreshed");
125        cache.compile("three", false).expect("three compiles");
126
127        assert!(cache.contains("one"));
128        assert!(!cache.contains("two"));
129        assert!(cache.contains("three"));
130    }
131
132    #[test]
133    fn invalid_pattern_is_remembered_as_invalid() {
134        let cache = UserRegexCache::with_capacity(NonZeroUsize::new(2).unwrap());
135
136        assert!(cache.compile("[", false).is_err());
137        assert!(cache.contains("["));
138        assert!(cache.compile("[", false).is_err());
139
140        assert_eq!(cache.len(), 1);
141    }
142
143    #[test]
144    fn oversized_patterns_are_refused_without_being_cached() {
145        let cache = UserRegexCache::with_capacity(NonZeroUsize::new(2).unwrap());
146
147        let long = "a".repeat(MAX_USER_REGEX_PATTERN_BYTES + 1);
148        assert!(cache.compile(&long, false).is_err());
149        assert_eq!(cache.len(), 0);
150
151        // Within the length cap, a pattern whose compiled form exceeds the
152        // program limit is refused rather than built.
153        let explosive = r"(?:\w{100}){100}";
154        assert!(explosive.len() <= MAX_USER_REGEX_PATTERN_BYTES);
155        assert!(matches!(
156            cache.compile(explosive, false),
157            Err(regex::Error::CompiledTooBig(_))
158        ));
159    }
160}