/// A few elementary UTF-8 encoding and decoding functions used by the matching /// engines. /// /// In an ideal world, the matching engines operate on `&str` and we can just /// lean on the standard library for all our UTF-8 needs. However, to support /// byte based regexes (that can match on arbitrary bytes which may contain /// UTF-8), we need to be capable of searching and decoding UTF-8 on a `&[u8]`. /// The standard library doesn't really recognize this use case, so we have /// to build it out ourselves. /// /// Should this be factored out into a separate crate? It seems independently /// useful. There are other crates that already exist (e.g., `utf-8`) that have /// overlapping use cases. Not sure what to do. use std::char; const TAG_CONT: u8 = 0b1000_0000; const TAG_TWO: u8 = 0b1100_0000; const TAG_THREE: u8 = 0b1110_0000; const TAG_FOUR: u8 = 0b1111_0000; /// Returns the smallest possible index of the next valid UTF-8 sequence /// starting after `i`. pub fn next_utf8(text: &[u8], i: usize) -> usize { let b = match text.get(i) { None => return i + 1, Some(&b) => b, }; let inc = if b <= 0x7F { 1 } else if b <= 0b110_11111 { 2 } else if b <= 0b1110_1111 { 3 } else { 4 }; i + inc } /// Decode a single UTF-8 sequence into a single Unicode codepoint from `src`. /// /// If no valid UTF-8 sequence could be found, then `None` is returned. /// Otherwise, the decoded codepoint and the number of bytes read is returned. /// The number of bytes read (for a valid UTF-8 sequence) is guaranteed to be /// 1, 2, 3 or 4. /// /// Note that a UTF-8 sequence is invalid if it is incorrect UTF-8, encodes a /// codepoint that is out of range (surrogate codepoints are out of range) or /// is not the shortest possible UTF-8 sequence for that codepoint. #[inline] pub fn decode_utf8(src: &[u8]) -> Option<(char, usize)> { let b0 = match src.get(0) { None => return None, Some(&b) if b <= 0x7F => return Some((b as char, 1)), Some(&b) => b, }; match b0 { 0b110_00000..=0b110_11111 => { if src.len() < 2 { return None; } let b1 = src[1]; if 0b11_000000 & b1 != TAG_CONT { return None; } let cp = ((b0 & !TAG_TWO) as u32) << 6 | ((b1 & !TAG_CONT) as u32); match cp { 0x80..=0x7FF => char::from_u32(cp).map(|cp| (cp, 2)), _ => None, } } 0b1110_0000..=0b1110_1111 => { if src.len() < 3 { return None; } let (b1, b2) = (src[1], src[2]); if 0b11_000000 & b1 != TAG_CONT { return None; } if 0b11_000000 & b2 != TAG_CONT { return None; } let cp = ((b0 & !TAG_THREE) as u32) << 12 | ((b1 & !TAG_CONT) as u32) << 6 | ((b2 & !TAG_CONT) as u32); match cp { // char::from_u32 will disallow surrogate codepoints. 0x800..=0xFFFF => char::from_u32(cp).map(|cp| (cp, 3)), _ => None, } } 0b11110_000..=0b11110_111 => { if src.len() < 4 { return None; } let (b1, b2, b3) = (src[1], src[2], src[3]); if 0b11_000000 & b1 != TAG_CONT { return None; } if 0b11_000000 & b2 != TAG_CONT { return None; } if 0b11_000000 & b3 != TAG_CONT { return None; } let cp = ((b0 & !TAG_FOUR) as u32) << 18 | ((b1 & !TAG_CONT) as u32) << 12 | ((b2 & !TAG_CONT) as u32) << 6 | ((b3 & !TAG_CONT) as u32); match cp { 0x10000..=0x10FFFF => char::from_u32(cp).map(|cp| (cp, 4)), _ => None, } } _ => None, } } /// Like `decode_utf8`, but decodes the last UTF-8 sequence in `src` instead /// of the first. pub fn decode_last_utf8(src: &[u8]) -> Option<(char, usize)> { if src.is_empty() { return None; } let mut start = src.len() - 1; if src[start] <= 0x7F { return Some((src[start] as char, 1)); } while start > src.len().saturating_sub(4) { start -= 1; if is_start_byte(src[start]) { break; } } match decode_utf8(&src[start..]) { None => None, Some((_, n)) if n < src.len() - start => None, Some((cp, n)) => Some((cp, n)), } } fn is_start_byte(b: u8) -> bool { b & 0b11_000000 != 0b1_0000000 } #[cfg(test)] mod tests { use std::str; use quickcheck::quickcheck; use super::{ decode_last_utf8, decode_utf8, TAG_CONT, TAG_FOUR, TAG_THREE, TAG_TWO, }; #[test] fn prop_roundtrip() { fn p(given_cp: char) -> bool { let mut tmp = [0; 4]; let encoded_len = given_cp.encode_utf8(&mut tmp).len(); let (got_cp, got_len) = decode_utf8(&tmp[..encoded_len]).unwrap(); encoded_len == got_len && given_cp == got_cp } quickcheck(p as fn(char) -> bool) } #[test] fn prop_roundtrip_last() { fn p(given_cp: char) -> bool { let mut tmp = [0; 4]; let encoded_len = given_cp.encode_utf8(&mut tmp).len(); let (got_cp, got_len) = decode_last_utf8(&tmp[..encoded_len]).unwrap(); encoded_len == got_len && given_cp == got_cp } quickcheck(p as fn(char) -> bool) } #[test] fn prop_encode_matches_std() { fn p(cp: char) -> bool { let mut got = [0; 4]; let n = cp.encode_utf8(&mut got).len(); let expected = cp.to_string(); &got[..n] == expected.as_bytes() } quickcheck(p as fn(char) -> bool) } #[test] fn prop_decode_matches_std() { fn p(given_cp: char) -> bool { let mut tmp = [0; 4]; let n = given_cp.encode_utf8(&mut tmp).len(); let (got_cp, _) = decode_utf8(&tmp[..n]).unwrap(); let expected_cp = str::from_utf8(&tmp[..n]).unwrap().chars().next().unwrap(); got_cp == expected_cp } quickcheck(p as fn(char) -> bool) } #[test] fn prop_decode_last_matches_std() { fn p(given_cp: char) -> bool { let mut tmp = [0; 4]; let n = given_cp.encode_utf8(&mut tmp).len(); let (got_cp, _) = decode_last_utf8(&tmp[..n]).unwrap(); let expected_cp = str::from_utf8(&tmp[..n]) .unwrap() .chars() .rev() .next() .unwrap(); got_cp == expected_cp } quickcheck(p as fn(char) -> bool) } #[test] fn reject_invalid() { // Invalid start byte assert_eq!(decode_utf8(&[0xFF]), None); // Surrogate pair assert_eq!(decode_utf8(&[0xED, 0xA0, 0x81]), None); // Invalid continuation byte. assert_eq!(decode_utf8(&[0xD4, 0xC2]), None); // Bad lengths assert_eq!(decode_utf8(&[0xC3]), None); // 2 bytes assert_eq!(decode_utf8(&[0xEF, 0xBF]), None); // 3 bytes assert_eq!(decode_utf8(&[0xF4, 0x8F, 0xBF]), None); // 4 bytes // Not a minimal UTF-8 sequence assert_eq!(decode_utf8(&[TAG_TWO, TAG_CONT | b'a']), None); assert_eq!(decode_utf8(&[TAG_THREE, TAG_CONT, TAG_CONT | b'a']), None); assert_eq!( decode_utf8(&[TAG_FOUR, TAG_CONT, TAG_CONT, TAG_CONT | b'a',]), None ); } #[test] fn reject_invalid_last() { // Invalid start byte assert_eq!(decode_last_utf8(&[0xFF]), None); // Surrogate pair assert_eq!(decode_last_utf8(&[0xED, 0xA0, 0x81]), None); // Bad lengths assert_eq!(decode_last_utf8(&[0xC3]), None); // 2 bytes assert_eq!(decode_last_utf8(&[0xEF, 0xBF]), None); // 3 bytes assert_eq!(decode_last_utf8(&[0xF4, 0x8F, 0xBF]), None); // 4 bytes // Not a minimal UTF-8 sequence assert_eq!(decode_last_utf8(&[TAG_TWO, TAG_CONT | b'a']), None); assert_eq!( decode_last_utf8(&[TAG_THREE, TAG_CONT, TAG_CONT | b'a',]), None ); assert_eq!( decode_last_utf8( &[TAG_FOUR, TAG_CONT, TAG_CONT, TAG_CONT | b'a',] ), None ); } }