use alloc::boxed::Box;
use alloc::vec::Vec;
use regex_automata::util::lazy::Lazy;
use regex_syntax::hir::{self, HirKind};
use crate::vm::{char_at, range_contains};
#[derive(Clone, Copy, Debug)]
pub(super) enum Stops {
None,
One(u8),
Two(u8, u8),
Three(u8, u8, u8),
}
#[derive(Clone, Debug)]
pub(super) enum Class {
Chars(Box<CharSet>),
Bytes([u64; 4]),
}
#[derive(Clone, Debug)]
pub(super) struct CharSet {
pub(super) ascii: u128,
pub(super) two: [u64; 30],
pub(super) wide: Box<[(char, char)]>,
}
#[derive(Clone, Copy, Debug)]
pub(super) struct ByteRanges {
pub(super) ranges: [(u8, u8); 2],
pub(super) high: bool,
pub(super) bytes: [u64; 4],
}
impl ByteRanges {
pub(super) fn of(bytes: &[u64; 4]) -> Option<ByteRanges> {
let mut ranges = [(1, 0); 2];
let mut count = 0;
let mut b = 0;
while b < 0x80 {
if !has_byte(bytes, b) {
b += 1;
continue;
}
let lo = b;
while b < 0x80 && has_byte(bytes, b) {
b += 1;
}
*ranges.get_mut(count)? = (lo, b - 1);
count += 1;
}
let high = bytes[2] | bytes[3] != 0;
let mut all = *bytes;
if high {
all[2] = u64::MAX;
all[3] = u64::MAX;
}
(count > 0).then_some(ByteRanges {
ranges,
high,
bytes: all,
})
}
#[inline]
fn mask(&self, word: u64) -> u64 {
const LANES: u64 = 0x0101_0101_0101_0101;
let low = word & (LANES * 0x7F);
let ascii = !word & (LANES * 0x80);
let mut found = if self.high { word & (LANES * 0x80) } else { 0 };
for (lo, hi) in self.ranges {
let below = (LANES * (128 + u64::from(hi))).wrapping_sub(low);
let above = low.wrapping_add(LANES * (128 - u64::from(lo)));
found |= below & above & ascii;
}
found & (LANES * 0x80)
}
#[inline]
pub(super) fn contains(&self, b: u8) -> bool {
has_byte(&self.bytes, b)
}
#[inline]
pub(super) fn find(&self, haystack: &[u8], from: usize, end: usize) -> Option<usize> {
let head = (from + 4).min(end);
if let Some(offset) = haystack[from..head].iter().position(|&b| self.contains(b)) {
return Some(from + offset);
}
let mut at = head;
while let Some(word) = haystack[at..end].first_chunk::<8>() {
let mask = self.mask(u64::from_le_bytes(*word));
if mask != 0 {
return Some(at + (mask.trailing_zeros() / 8) as usize);
}
at += 8;
}
haystack[at..end]
.iter()
.position(|&b| self.contains(b))
.map(|offset| at + offset)
}
}
const UNION_RANGES: usize = 4096;
const ASCII_WORD: u128 =
(0x3FF << b'0') | (0x3FF_FFFF << b'A') | (0x3FF_FFFF << b'a') | (1 << b'_');
pub(super) static WORD_BYTE: [bool; 256] = {
let mut table = [false; 256];
let mut b = 0;
while b < 128 {
table[b] = (ASCII_WORD >> b) & 1 == 1;
b += 1;
}
table
};
pub(super) fn has_byte(set: &[u64; 4], b: u8) -> bool {
set[usize::from(b >> 6)] & (1 << (b & 63)) != 0
}
pub(super) fn insert_byte(set: &mut [u64; 4], b: u8) {
set[usize::from(b >> 6)] |= 1 << (b & 63);
}
pub(super) fn bytes_in(set: [u64; 4]) -> impl Iterator<Item = u8> {
(0u8..).zip(set).flat_map(|(word, mut bits)| {
core::iter::from_fn(move || {
let bit = (bits != 0).then(|| bits.trailing_zeros() as u8)?;
bits &= bits - 1;
Some(word * 64 + bit)
})
})
}
#[inline]
pub(super) fn bit128(bits: u128, b: u8) -> bool {
let half = if b < 64 {
bits as u64
} else {
(bits >> 64) as u64
};
(half >> (b & 63)) & 1 == 1
}
#[inline]
fn decode_wide(bytes: &[u8]) -> Option<(char, usize)> {
let continuation = |b: u8| b & 0xC0 == 0x80;
match *bytes {
[lead @ 0xE0..=0xEF, b1, b2, ..] => {
let second = match lead {
0xE0 => (0xA0..=0xBF).contains(&b1),
0xED => (0x80..=0x9F).contains(&b1),
_ => continuation(b1),
};
if !second || !continuation(b2) {
return None;
}
let value =
(u32::from(lead & 0x0F) << 12) | (u32::from(b1 & 0x3F) << 6) | u32::from(b2 & 0x3F);
char::from_u32(value).map(|c| (c, 3))
}
[lead @ 0xF0..=0xF4, b1, b2, b3, ..] => {
let second = match lead {
0xF0 => (0x90..=0xBF).contains(&b1),
0xF4 => (0x80..=0x8F).contains(&b1),
_ => continuation(b1),
};
if !second || !continuation(b2) || !continuation(b3) {
return None;
}
let value = (u32::from(lead & 0x07) << 18)
| (u32::from(b1 & 0x3F) << 12)
| (u32::from(b2 & 0x3F) << 6)
| u32::from(b3 & 0x3F);
char::from_u32(value).map(|c| (c, 4))
}
_ => None,
}
}
fn fill(words: &mut [u64], lo: usize, hi: usize) {
for (index, word) in words.iter_mut().enumerate().take(hi / 64 + 1).skip(lo / 64) {
let base = index * 64;
let first = lo.max(base) - base;
let last = hi.min(base + 63) - base;
*word |= (u64::MAX >> (63 - last)) & (u64::MAX << first);
}
}
pub(super) fn char_boundary(haystack: &[u8], at: usize) -> bool {
haystack.get(at).is_none_or(|&b| (b as i8) >= -0x40)
}
impl CharSet {
pub(super) fn new(ranges: impl IntoIterator<Item = (char, char)>) -> CharSet {
let mut set = CharSet {
ascii: 0,
two: [0; 30],
wide: Box::new([]),
};
let mut wide = Vec::new();
for (start, end) in ranges {
let (lo, hi) = (u32::from(start) as usize, u32::from(end) as usize);
if lo <= 0x7F {
set.ascii |= (u128::MAX >> (0x7F - hi.min(0x7F))) & (u128::MAX << lo);
}
if lo <= 0x7FF && hi >= 0x80 {
fill(&mut set.two, lo.max(0x80) - 0x80, hi.min(0x7FF) - 0x80);
}
if hi >= 0x800 {
wide.push((start.max('\u{800}'), end));
}
}
set.wide = wide.into_boxed_slice();
set
}
fn has_non_ascii(&self) -> bool {
self.two.iter().any(|&bits| bits != 0) || !self.wide.is_empty()
}
#[inline]
pub(super) fn non_ascii_len(&self, haystack: &[u8], at: usize, end: usize) -> Option<usize> {
let lead = haystack[at];
if lead < 0xE0 {
let next = *haystack[..end].get(at + 1)?;
if lead < 0xC2 || next & 0xC0 != 0x80 {
return None;
}
let index = ((usize::from(lead & 0x1F) << 6) | usize::from(next & 0x3F)) - 0x80;
return ((self.two[index >> 6] >> (index & 63)) & 1 == 1).then_some(2);
}
if self.wide.is_empty() {
return None;
}
let (c, len) = decode_wide(&haystack[at..end])?;
range_contains(&self.wide, c).then_some(len)
}
fn union(&self, other: &CharSet) -> CharSet {
let mut ranges: Vec<(char, char)> = self.wide.iter().chain(&*other.wide).copied().collect();
ranges.sort_unstable();
let mut wide: Vec<(char, char)> = Vec::with_capacity(ranges.len());
for (lo, hi) in ranges {
match wide.last_mut() {
Some((_, end)) if u32::from(lo) <= u32::from(*end) + 1 => *end = (*end).max(hi),
_ => wide.push((lo, hi)),
}
}
let mut two = self.two;
for (bits, other) in two.iter_mut().zip(&other.two) {
*bits |= other;
}
CharSet {
ascii: self.ascii | other.ascii,
two,
wide: wide.into_boxed_slice(),
}
}
fn is_subset(&self, other: &CharSet) -> bool {
self.ascii & !other.ascii == 0
&& self.two.iter().zip(&other.two).all(|(a, b)| a & !b == 0)
&& self.wide.iter().all(|&(lo, hi)| {
let at = other.wide.partition_point(|&(_, end)| end < lo);
other
.wide
.get(at)
.is_some_and(|&(start, end)| start <= lo && hi <= end)
})
}
}
fn sequence_bound(start: char, end: char) -> usize {
let (start, end) = (u32::from(start), u32::from(end));
[
(0, 0x7F, 1),
(0x80, 0x7FF, 3),
(0x800, 0xD7FF, 5),
(0xE000, 0xFFFF, 5),
(0x1_0000, 0x10_FFFF, 7),
]
.iter()
.filter(|&&(lo, hi, _)| start <= hi && lo <= end)
.map(|&(_, _, units)| units)
.sum()
}
pub(super) fn class_units(class: &hir::Class) -> usize {
match class {
hir::Class::Unicode(class) => class
.iter()
.map(|range| sequence_bound(range.start(), range.end()))
.fold(0, usize::saturating_add),
hir::Class::Bytes(class) => class.ranges().len(),
}
}
impl Class {
pub(super) fn from_hir(class: &hir::Class) -> Class {
match class {
hir::Class::Unicode(class) => Class::Chars(Box::new(CharSet::new(
class.iter().map(|range| (range.start(), range.end())),
))),
hir::Class::Bytes(class) => {
let mut set = [0u64; 4];
for range in class.iter() {
fill(&mut set, range.start().into(), range.end().into());
}
Class::Bytes(set)
}
}
}
pub(super) fn from_literal(bytes: &[u8]) -> Option<Class> {
match char_at(bytes, 0) {
Some((c, len)) if len == bytes.len() => {
Some(Class::Chars(Box::new(CharSet::new([(c, c)]))))
}
_ => match *bytes {
[b] => {
let mut set = [0u64; 4];
insert_byte(&mut set, b);
Some(Class::Bytes(set))
}
_ => None,
},
}
}
#[inline]
pub(super) fn match_len(&self, haystack: &[u8], at: usize, end: usize) -> Option<usize> {
if at >= end {
return None;
}
let b = haystack[at];
match self {
Class::Chars(set) if b < 0x80 => bit128(set.ascii, b).then_some(1),
Class::Chars(set) => set.non_ascii_len(haystack, at, end),
Class::Bytes(set) => has_byte(set, b).then_some(1),
}
}
#[inline]
pub(super) fn len_before(&self, haystack: &[u8], at: usize) -> Option<usize> {
match self {
Class::Bytes(set) => {
let b = *haystack.get(at.checked_sub(1)?)?;
has_byte(set, b).then_some(1)
}
Class::Chars(_) => {
let start = (at.saturating_sub(4)..at)
.rev()
.find(|&i| haystack[i] & 0xC0 != 0x80)?;
(self.match_len(haystack, start, at) == Some(at - start)).then_some(at - start)
}
}
}
pub(super) fn single(&self) -> Option<Vec<u8>> {
match self {
Class::Bytes(set) => {
let mut members = bytes_in(*set);
match (members.next(), members.next()) {
(Some(b), None) => Some(Vec::from([b])),
_ => None,
}
}
Class::Chars(set) => {
let count = set.ascii.count_ones()
+ set.two.iter().map(|bits| bits.count_ones()).sum::<u32>();
let c = match (count, &*set.wide) {
(1, []) if set.ascii != 0 => char::from(set.ascii.trailing_zeros() as u8),
(1, []) => {
let (word, bits) = set.two.iter().enumerate().find(|(_, b)| **b != 0)?;
char::from_u32(0x80 + 64 * word as u32 + bits.trailing_zeros())?
}
(0, [(lo, hi)]) if lo == hi => *lo,
_ => return None,
};
Some(Vec::from(c.encode_utf8(&mut [0; 4]).as_bytes()))
}
}
}
pub(super) fn has_ascii(&self, b: u8) -> bool {
match self {
Class::Chars(set) => bit128(set.ascii, b),
Class::Bytes(set) => has_byte(set, b),
}
}
pub(super) fn has_single_byte(&self, b: u8) -> bool {
match self {
Class::Chars(set) => b < 0x80 && bit128(set.ascii, b),
Class::Bytes(set) => has_byte(set, b),
}
}
pub(super) fn max_len(&self) -> usize {
match self {
Class::Chars(set) => match set.wide.last() {
Some(&(_, end)) => end.len_utf8(),
None if set.two.iter().any(|&bits| bits != 0) => 2,
None => 1,
},
Class::Bytes(_) => 1,
}
}
pub(super) fn stops(&self) -> Option<Stops> {
let Class::Chars(set) = self else {
return None;
};
if set.ascii.count_zeros() > 3
|| set.two.iter().any(|&bits| bits != u64::MAX)
|| *set.wide != [('\u{800}', char::MAX)]
{
return None;
}
let excluded = [!set.ascii as u64, (!set.ascii >> 64) as u64, 0, 0];
Stops::of(&mut bytes_in(excluded))
}
pub(super) fn first_bytes(&self) -> [u64; 4] {
match self {
Class::Bytes(set) => *set,
Class::Chars(set) => {
let mut bytes = [set.ascii as u64, (set.ascii >> 64) as u64, 0, 0];
for (lead, &bits) in (0xC2..=0xDFu8).zip(&set.two) {
if bits != 0 {
insert_byte(&mut bytes, lead);
}
}
let lead = |c: char| c.encode_utf8(&mut [0; 4]).as_bytes()[0];
for &(lo, hi) in set.wide.iter() {
for b in lead(lo)..=lead(hi) {
insert_byte(&mut bytes, b);
}
}
bytes
}
}
}
pub(super) fn union(&self, other: &Class) -> Option<Class> {
let ascii_bytes = |set: &[u64; 4]| u128::from(set[0]) | (u128::from(set[1]) << 64);
match (self, other) {
(Class::Chars(a), Class::Chars(b)) => (a.wide.len() + b.wide.len() <= UNION_RANGES)
.then(|| Class::Chars(Box::new(a.union(b)))),
(Class::Bytes(a), Class::Bytes(b)) => Some(Class::Bytes([
a[0] | b[0],
a[1] | b[1],
a[2] | b[2],
a[3] | b[3],
])),
(Class::Chars(chars), Class::Bytes(bytes))
| (Class::Bytes(bytes), Class::Chars(chars)) => {
if bytes[2] | bytes[3] == 0 {
let mut set = (**chars).clone();
set.ascii |= ascii_bytes(bytes);
Some(Class::Chars(Box::new(set)))
} else if !chars.has_non_ascii() {
let mut set = *bytes;
set[0] |= chars.ascii as u64;
set[1] |= (chars.ascii >> 64) as u64;
Some(Class::Bytes(set))
} else {
None
}
}
}
}
pub(super) fn overlaps(&self, other: &Class) -> bool {
match (self, other) {
(Class::Chars(a), Class::Chars(b)) => {
a.ascii & b.ascii != 0
|| a.two.iter().zip(&b.two).any(|(x, y)| x & y != 0)
|| a.wide.iter().any(|&(lo, hi)| {
b.wide.iter().any(|&(start, end)| lo <= end && start <= hi)
})
}
(Class::Bytes(a), Class::Bytes(b)) => a.iter().zip(b).any(|(a, b)| a & b != 0),
(Class::Chars(chars), Class::Bytes(bytes))
| (Class::Bytes(bytes), Class::Chars(chars)) => {
(u128::from(bytes[0]) | (u128::from(bytes[1]) << 64)) & chars.ascii != 0
|| (bytes[2] | bytes[3] != 0 && chars.has_non_ascii())
}
}
}
pub(super) fn is_word(&self, unicode: bool) -> bool {
match self {
Class::Bytes(set) => {
set[2] | set[3] == 0
&& (u128::from(set[0]) | (u128::from(set[1]) << 64)) & !ASCII_WORD == 0
}
Class::Chars(set) => {
set.ascii & !ASCII_WORD == 0
&& (!set.has_non_ascii()
|| unicode
&& Lazy::get(&UNICODE_WORD)
.as_ref()
.is_some_and(|word| set.is_subset(word)))
}
}
}
}
static UNICODE_WORD: Lazy<Option<CharSet>> = Lazy::new(unicode_word);
fn unicode_word() -> Option<CharSet> {
let hir = regex_syntax::ParserBuilder::new()
.build()
.parse(r"\w")
.ok()?;
match hir.kind() {
HirKind::Class(hir::Class::Unicode(class)) => Some(CharSet::new(
class.iter().map(|range| (range.start(), range.end())),
)),
_ => None,
}
}
impl Stops {
pub(super) fn of(bytes: &mut impl Iterator<Item = u8>) -> Option<Stops> {
Some(
match (bytes.next(), bytes.next(), bytes.next(), bytes.next()) {
(None, ..) => Stops::None,
(Some(a), None, ..) => Stops::One(a),
(Some(a), Some(b), None, _) => Stops::Two(a, b),
(Some(a), Some(b), Some(c), None) => Stops::Three(a, b, c),
_ => return None,
},
)
}
#[inline]
pub(super) fn find(self, haystack: &[u8]) -> Option<usize> {
match self {
Stops::None => None,
Stops::One(a) => memchr::memchr(a, haystack),
Stops::Two(a, b) => memchr::memchr2(a, b, haystack),
Stops::Three(a, b, c) => memchr::memchr3(a, b, c, haystack),
}
}
}
#[cfg(test)]
mod tests {
#[test]
fn char_sets_fill_exactly_the_ranges() {
let ranges = [
('\u{0}', '\u{0}'),
('\u{3F}', '\u{40}'),
('\u{7E}', '\u{85}'),
('\u{BF}', '\u{C0}'),
('\u{100}', '\u{13F}'),
('\u{7C0}', '\u{900}'),
('\u{21}', '\u{10FFFF}'),
];
for (index, &range) in ranges.iter().enumerate() {
let set = super::CharSet::new(ranges[index..].iter().copied().chain([range]));
let mut ascii = 0u128;
let mut two = [0u64; 30];
for &(start, end) in &ranges[index..] {
for c in u32::from(start)..=u32::from(end).min(0x7FF) {
match c {
0..=0x7F => ascii |= 1 << c,
_ => two[(c as usize - 0x80) >> 6] |= 1 << ((c - 0x80) & 63),
}
}
}
assert_eq!(set.ascii, ascii, "{range:?}");
assert_eq!(set.two, two, "{range:?}");
}
let mut bytes = [0u64; 4];
super::fill(&mut bytes, 0x3F, 0xC1);
let expected: [u64; 4] = [1 << 63, u64::MAX, u64::MAX, 0b11];
assert_eq!(bytes, expected);
}
#[test]
fn byte_ranges_mask_each_lane_exactly() {
let sets: [&[u8]; 5] = [b"AZ", b"09af", b"az", b"\x00\x10", b"\x7F\x7F"];
for (index, bounds) in sets.iter().enumerate() {
let mut bytes = [0u64; 4];
for pair in bounds.chunks(2) {
for b in pair[0]..=pair[1] {
super::insert_byte(&mut bytes, b);
}
}
if index % 2 == 1 {
super::insert_byte(&mut bytes, 0xC3);
}
let ranges = super::ByteRanges::of(&bytes).unwrap();
for b in 0..=255u8 {
for lane in 0..8 {
for filler in [0u8, 0x7F, 0x80, 0xFF, b'A', b'z'] {
let mut word = [filler; 8];
word[lane] = b;
let mask = ranges.mask(u64::from_le_bytes(word));
let expected = word.iter().enumerate().fold(0u64, |mask, (i, &w)| {
mask | (u64::from(ranges.contains(w)) << (8 * i + 7))
});
assert_eq!(mask, expected, "{bounds:?} {b} {lane} {filler}");
}
}
}
}
}
#[test]
fn decode_wide_matches_from_utf8() {
let seconds = [0x7F, 0x80, 0x8F, 0x90, 0x9F, 0xA0, 0xBF, 0xC0];
for lead in 0xC0..=0xFFu8 {
for &b1 in &seconds {
for &b2 in &[0x7F, 0x80, 0xBF, 0xC0] {
for &b3 in &[0x7F, 0x80, 0xBF, 0xC0] {
let bytes = [lead, b1, b2, b3];
let expected = (3..=4).find_map(|len| {
core::str::from_utf8(&bytes[..len])
.ok()
.and_then(|text| text.chars().next().map(|c| (c, len)))
.filter(|_| lead >= 0xE0)
});
let expected = expected.filter(|&(c, len)| c.len_utf8() == len);
assert_eq!(super::decode_wide(&bytes), expected, "{bytes:02X?}");
assert_eq!(
super::decode_wide(&bytes[..3]),
expected.filter(|&(_, l)| l == 3)
);
}
}
}
}
}
#[test]
fn sequence_bound_covers_utf8_sequences() {
use regex_syntax::hir::{Class, HirKind};
use regex_syntax::utf8::Utf8Sequences;
for pattern in [
r"\w",
r"\p{L}",
r"\d",
"(?s:.)",
r"[^\n]",
r"\s",
"(?i:k)",
r"\p{Han}",
"[€-𝄞]",
r"[\x{7FF}-\x{800}]",
r"[\x{D7FF}-\x{E000}]",
r"[\x{FFFF}-\x{10000}]",
] {
let hir = regex_syntax::parse(pattern).unwrap();
let HirKind::Class(Class::Unicode(class)) = hir.kind() else {
panic!("{pattern} is not a Unicode class");
};
for range in class.iter() {
let actual = Utf8Sequences::new(range.start(), range.end()).count();
let bound = super::sequence_bound(range.start(), range.end());
assert!(actual <= bound, "{pattern} {range:?}: {actual} > {bound}");
}
}
}
}