squeeze/
uuid.rs

1use super::{Anchor, ByteSet, Finder, RunClass, RunRule};
2use std::ops::Range;
3
4#[derive(Default)]
5pub struct Uuid {}
6
7impl Uuid {
8    fn is_hex(b: u8) -> bool {
9        b.is_ascii_hexdigit()
10    }
11
12    /// Whether the 36 bytes at `start` are `8-4-4-4-12` hex groups.
13    fn check_pattern(input: &[u8], start: usize) -> bool {
14        let Some(bytes) = input.get(start..start + 36) else {
15            return false;
16        };
17        let bytes: &[u8; 36] = bytes.try_into().expect("36 bytes");
18        #[cfg(target_arch = "aarch64")]
19        {
20            Self::check_pattern_neon(bytes)
21        }
22        #[cfg(not(target_arch = "aarch64"))]
23        {
24            Self::check_pattern_scalar(bytes)
25        }
26    }
27
28    #[cfg(any(test, not(target_arch = "aarch64")))]
29    fn check_pattern_scalar(bytes: &[u8; 36]) -> bool {
30        bytes.iter().enumerate().all(|(i, &b)| match i {
31            8 | 13 | 18 | 23 => b == b'-',
32            _ => Self::is_hex(b),
33        })
34    }
35
36    /// The same test on two 16-byte vectors and a 4-byte tail: every byte
37    /// is a hex digit except the dashes at 8, 13, 18 and 23.
38    #[cfg(target_arch = "aarch64")]
39    fn check_pattern_neon(bytes: &[u8; 36]) -> bool {
40        use core::arch::aarch64::*;
41        // Dash positions within each 16-byte block: 8, 13 | 18, 23.
42        const DASHES_LO: [u8; 16] = [0, 0, 0, 0, 0, 0, 0, 0, 0xFF, 0, 0, 0, 0, 0xFF, 0, 0];
43        const DASHES_HI: [u8; 16] = [0, 0, 0xFF, 0, 0, 0, 0, 0xFF, 0, 0, 0, 0, 0, 0, 0, 0];
44        // SAFETY: NEON is part of the aarch64 baseline; the loads read 16
45        // bytes at offsets 0 and 16 of a 36-byte array.
46        unsafe {
47            let hex_ok = |v: uint8x16_t| -> uint8x16_t {
48                let digit = vcltq_u8(vsubq_u8(v, vdupq_n_u8(b'0')), vdupq_n_u8(10));
49                let lower = vorrq_u8(v, vdupq_n_u8(0x20));
50                let alpha = vcltq_u8(vsubq_u8(lower, vdupq_n_u8(b'a')), vdupq_n_u8(6));
51                vorrq_u8(digit, alpha)
52            };
53            let check = |v: uint8x16_t, dashes: uint8x16_t| -> bool {
54                let is_dash = vceqq_u8(v, vdupq_n_u8(b'-'));
55                // Dash lanes must be dashes, the others hex digits.
56                let ok = vbslq_u8(dashes, is_dash, hex_ok(v));
57                vminvq_u8(ok) == 0xFF
58            };
59            let lo = vld1q_u8(bytes.as_ptr());
60            let hi = vld1q_u8(bytes.as_ptr().add(16));
61            check(lo, vld1q_u8(DASHES_LO.as_ptr()))
62                && check(hi, vld1q_u8(DASHES_HI.as_ptr()))
63                && bytes[32..36].iter().all(|&b| Self::is_hex(b))
64        }
65    }
66}
67
68impl Finder for Uuid {
69    fn line_agnostic(&self) -> bool {
70        // Matches never contain a line terminator and `\n`/`\r` end every
71        // walk exactly like the end of the input does.
72        true
73    }
74
75    fn id(&self) -> &'static str {
76        "uuid"
77    }
78
79    fn dispatchable(&self) -> bool {
80        true
81    }
82
83    fn could_start_at(&self, byte: u8) -> bool {
84        byte.is_ascii_hexdigit()
85    }
86
87    fn could_start_after(&self, prev: u8, _cur: u8) -> bool {
88        !(Self::is_hex(prev) || prev == b'-')
89    }
90
91    fn could_continue_with(&self, _cur: u8, next: u8) -> bool {
92        Self::is_hex(next)
93    }
94
95    fn anchor(&self) -> Option<Anchor> {
96        // The dashes sit at offsets 8, 13, 18 and 23.
97        Some(
98            Anchor::new(
99                ByteSet::from_bytes(b"-"),
100                ByteSet::from_fn(|b| b.is_ascii_hexdigit()),
101            )
102            .confirm_all(b"-", &[5, 10, 15], b"-")
103            .back(8),
104        )
105    }
106
107    fn run_rules(&self) -> Vec<RunRule> {
108        // `xxxxxxxx-xxxx-xxxx-`.
109        vec![
110            RunRule::new(RunClass::Hex, 8, 8)
111                .followed_by(b"-")
112                .then(RunClass::Hex, 4, 4)
113                .followed_by(b"-")
114                .then(RunClass::Hex, 4, 4)
115                .followed_by(b"-"),
116        ]
117    }
118
119    fn try_at(&self, input: &[u8], pos: usize) -> Option<Range<usize>> {
120        if !Self::is_hex(input[pos]) {
121            return None;
122        }
123        if pos > 0 && (Self::is_hex(input[pos - 1]) || input[pos - 1] == b'-') {
124            return None;
125        }
126        if !Self::check_pattern(input, pos) {
127            return None;
128        }
129        let end = pos + 36;
130        if end < input.len() && (Self::is_hex(input[end]) || input[end] == b'-') {
131            return None;
132        }
133        Some(pos..end)
134    }
135
136    fn find(&self, s: &str) -> Option<Range<usize>> {
137        let input = s.as_bytes();
138        let mut idx = 0;
139
140        while idx + 36 <= input.len() {
141            if Self::is_hex(input[idx]) {
142                if idx > 0 && (Self::is_hex(input[idx - 1]) || input[idx - 1] == b'-') {
143                    idx += 1;
144                    continue;
145                }
146
147                if Self::check_pattern(input, idx) {
148                    let end = idx + 36;
149                    if end < input.len() && (Self::is_hex(input[end]) || input[end] == b'-') {
150                        idx += 1;
151                        continue;
152                    }
153                    return Some(idx..end);
154                }
155            }
156            idx += 1;
157        }
158
159        None
160    }
161}
162
163#[cfg(test)]
164mod tests {
165    use super::*;
166
167    #[test]
168    fn id_should_return_uuid() {
169        let finder = Uuid::default();
170        assert_eq!("uuid", finder.id());
171    }
172
173    #[test]
174    fn find_should_extract_uuid() {
175        let finder = Uuid::default();
176        let input = "id: 550e8400-e29b-41d4-a716-446655440000";
177        let range = finder.find(input).unwrap();
178        assert_eq!("550e8400-e29b-41d4-a716-446655440000", &input[range]);
179    }
180
181    #[test]
182    fn find_should_extract_uuid_at_start() {
183        let finder = Uuid::default();
184        let input = "550e8400-e29b-41d4-a716-446655440000 is the id";
185        let range = finder.find(input).unwrap();
186        assert_eq!("550e8400-e29b-41d4-a716-446655440000", &input[range]);
187    }
188
189    #[test]
190    fn find_should_extract_uppercase_uuid() {
191        let finder = Uuid::default();
192        let input = "550E8400-E29B-41D4-A716-446655440000";
193        let range = finder.find(input).unwrap();
194        assert_eq!("550E8400-E29B-41D4-A716-446655440000", &input[range]);
195    }
196
197    #[test]
198    fn find_should_extract_mixed_case_uuid() {
199        let finder = Uuid::default();
200        let input = "550e8400-E29B-41d4-A716-446655440000";
201        let range = finder.find(input).unwrap();
202        assert_eq!("550e8400-E29B-41d4-A716-446655440000", &input[range]);
203    }
204
205    #[test]
206    fn find_should_reject_no_dashes() {
207        let finder = Uuid::default();
208        assert!(finder.find("550e8400e29b41d4a716446655440000").is_none());
209    }
210
211    #[test]
212    fn find_should_reject_wrong_dash_positions() {
213        let finder = Uuid::default();
214        assert!(
215            finder
216                .find("550e840-0e29b-41d4-a716-446655440000")
217                .is_none()
218        );
219    }
220
221    #[test]
222    fn find_should_reject_too_short() {
223        let finder = Uuid::default();
224        assert!(finder.find("550e8400-e29b-41d4-a716").is_none());
225    }
226
227    #[test]
228    fn find_should_reject_non_hex() {
229        let finder = Uuid::default();
230        assert!(
231            finder
232                .find("550e8400-e29b-41d4-a716-44665544000g")
233                .is_none()
234        );
235    }
236
237    #[test]
238    fn find_should_not_match_within_longer_hex() {
239        let finder = Uuid::default();
240        assert!(
241            finder
242                .find("ff550e8400-e29b-41d4-a716-446655440000")
243                .is_none()
244        );
245    }
246
247    #[test]
248    fn find_should_not_match_with_trailing_hex() {
249        let finder = Uuid::default();
250        assert!(
251            finder
252                .find("550e8400-e29b-41d4-a716-446655440000ff")
253                .is_none()
254        );
255    }
256
257    #[test]
258    fn find_should_extract_uuid_in_brackets() {
259        let finder = Uuid::default();
260        let input = "[550e8400-e29b-41d4-a716-446655440000]";
261        let range = finder.find(input).unwrap();
262        assert_eq!("550e8400-e29b-41d4-a716-446655440000", &input[range]);
263    }
264
265    #[test]
266    fn find_should_handle_empty_input() {
267        let finder = Uuid::default();
268        assert!(finder.find("").is_none());
269    }
270
271    #[test]
272    fn find_should_extract_multiple_uuids_iteratively() {
273        let finder = Uuid::default();
274        let input = "550e8400-e29b-41d4-a716-446655440000 and 6ba7b810-9dad-11d1-80b4-00c04fd430c8";
275
276        let mut results = Vec::new();
277        let mut idx = 0;
278        while idx < input.len() {
279            if let Some(range) = finder.find(&input[idx..]) {
280                results.push(&input[idx + range.start..idx + range.end]);
281                idx += range.end;
282            } else {
283                break;
284            }
285        }
286
287        assert_eq!(
288            vec![
289                "550e8400-e29b-41d4-a716-446655440000",
290                "6ba7b810-9dad-11d1-80b4-00c04fd430c8"
291            ],
292            results
293        );
294    }
295
296    #[test]
297    fn find_should_extract_nil_uuid() {
298        let finder = Uuid::default();
299        let input = "00000000-0000-0000-0000-000000000000";
300        let range = finder.find(input).unwrap();
301        assert_eq!("00000000-0000-0000-0000-000000000000", &input[range]);
302    }
303
304    #[test]
305    fn try_at_at_start() {
306        let finder = Uuid::default();
307        let input = b"550e8400-e29b-41d4-a716-446655440000 end";
308        assert_eq!(finder.try_at(input, 0), Some(0..36));
309    }
310
311    #[test]
312    fn try_at_preceded_by_hex() {
313        let finder = Uuid::default();
314        let input = b"ff550e8400-e29b-41d4-a716-446655440000";
315        assert!(finder.try_at(input, 2).is_none());
316    }
317
318    #[test]
319    fn try_at_preceded_by_dash() {
320        let finder = Uuid::default();
321        let input = b"-550e8400-e29b-41d4-a716-446655440000";
322        assert!(finder.try_at(input, 1).is_none());
323    }
324
325    #[test]
326    fn try_at_too_short_input() {
327        let finder = Uuid::default();
328        let input = b"550e8400";
329        assert!(finder.try_at(input, 0).is_none());
330    }
331
332    #[test]
333    fn find_should_reject_extra_dash_at_end() {
334        let finder = Uuid::default();
335        assert!(
336            finder
337                .find("550e8400-e29b-41d4-a716-446655440000-")
338                .is_none()
339        );
340    }
341
342    #[test]
343    fn find_should_handle_uuid_at_exact_end() {
344        let finder = Uuid::default();
345        let input = "x 550e8400-e29b-41d4-a716-446655440000";
346        let range = finder.find(input).unwrap();
347        assert_eq!("550e8400-e29b-41d4-a716-446655440000", &input[range]);
348    }
349
350    #[test]
351    fn find_should_handle_input_shorter_than_uuid() {
352        let finder = Uuid::default();
353        assert!(finder.find("abc").is_none());
354        assert!(finder.find("a").is_none());
355    }
356}
357
358#[cfg(test)]
359mod pattern_tests {
360    use super::Uuid;
361
362    #[test]
363    fn vector_pattern_check_agrees_with_the_scalar_one() {
364        let mut seed = 0x9E37_79B9_7F4A_7C15u64;
365        let mut next = || {
366            seed ^= seed << 13;
367            seed ^= seed >> 7;
368            seed ^= seed << 17;
369            seed
370        };
371        let alphabet = b"0123456789abcdefABCDEF-gG/ :";
372        for round in 0..20_000 {
373            let mut bytes = *b"550e8400-e29b-41d4-a716-446655440000";
374            // Mostly valid UUIDs with a few bytes disturbed.
375            let flips = round % 4;
376            for _ in 0..flips {
377                let at = (next() % 36) as usize;
378                bytes[at] = alphabet[(next() % alphabet.len() as u64) as usize];
379            }
380            let input = bytes.to_vec();
381            assert_eq!(
382                Uuid::check_pattern(&input, 0),
383                Uuid::check_pattern_scalar(&bytes),
384                "{}",
385                String::from_utf8_lossy(&bytes)
386            );
387        }
388    }
389}
squeeze/uuid.rs

squeeze/
uuid.rs
