use std::collections::HashSet;
pub const NGRAM: usize = 4;
fn hash_bytes(bytes: &[u8], seed: u64) -> u64 {
let mut z = seed ^ 0x9E37_79B9_7F4A_7C15;
for &b in bytes {
z = (z ^ u64::from(b)).wrapping_mul(0x1000_0000_01B3);
}
z = (z ^ (z >> 30)).wrapping_mul(0xBF58_476D_1CE4_E5B9);
z = (z ^ (z >> 27)).wrapping_mul(0x94D0_49BB_1331_11EB);
z ^ (z >> 31)
}
fn reduce(x: u32, n: usize) -> usize {
((u64::from(x) * n as u64) >> 32) as usize
}
fn ngram_keys(corpus: &[u8]) -> Vec<u64> {
if corpus.len() < NGRAM {
return Vec::new();
}
let mut set: HashSet<u64> = HashSet::new();
for w in corpus.windows(NGRAM) {
set.insert(hash_bytes(w, 0));
}
set.into_iter().collect()
}
fn all_ngrams_present(literal: &[u8], present: impl Fn(u64) -> bool) -> bool {
if literal.len() < NGRAM {
return true;
}
literal.windows(NGRAM).all(|w| present(hash_bytes(w, 0)))
}
pub trait Membership {
fn might_contain(&self, literal: &[u8]) -> bool;
fn name(&self) -> &'static str;
}
pub struct BloomFilter {
bits: Vec<u64>,
nbits: usize,
k: usize,
}
impl BloomFilter {
#[must_use]
pub fn build(corpus: &[u8]) -> Self {
let keys = ngram_keys(corpus);
let n = keys.len().max(1);
let nbits = (n * 10).next_power_of_two().max(64);
let mut f = Self { bits: vec![0u64; nbits / 64], nbits, k: 7 };
for key in keys {
f.insert(key);
}
f
}
fn positions(&self, key: u64) -> impl Iterator<Item = usize> + '_ {
let h1 = key;
let h2 = hash_bytes(&key.to_le_bytes(), 0xD1B5_4A32);
(0..self.k).map(move |i| {
let h = h1.wrapping_add((i as u64).wrapping_mul(h2));
(h as usize) & (self.nbits - 1)
})
}
fn insert(&mut self, key: u64) {
for p in self.positions(key).collect::<Vec<_>>() {
self.bits[p >> 6] |= 1u64 << (p & 63);
}
}
fn has(&self, key: u64) -> bool {
self.positions(key).all(|p| self.bits[p >> 6] & (1u64 << (p & 63)) != 0)
}
}
impl Membership for BloomFilter {
fn might_contain(&self, literal: &[u8]) -> bool {
all_ngrams_present(literal, |k| self.has(k))
}
fn name(&self) -> &'static str {
"bloom"
}
}
pub struct CuckooFilter {
buckets: Vec<[u8; 4]>,
nbuckets: usize,
}
impl CuckooFilter {
#[must_use]
pub fn build(corpus: &[u8]) -> Self {
let keys = ngram_keys(corpus);
let mut nbuckets = ((keys.len() / 4) + 1).next_power_of_two().max(4);
loop {
if let Some(f) = Self::try_build(&keys, nbuckets) {
return f;
}
nbuckets *= 2;
}
}
fn fingerprint(key: u64) -> u8 {
((key & 0xFF) as u8).max(1)
}
fn index1(key: u64, nbuckets: usize) -> usize {
((key >> 32) as usize) & (nbuckets - 1)
}
fn alt_index(i: usize, fp: u8, nbuckets: usize) -> usize {
let h = hash_bytes(&[fp], 0x9E37_79B1);
(i ^ (h as usize)) & (nbuckets - 1)
}
fn try_build(keys: &[u64], nbuckets: usize) -> Option<Self> {
let mut f = Self { buckets: vec![[0u8; 4]; nbuckets], nbuckets };
for &key in keys {
if !f.insert(key) {
return None;
}
}
Some(f)
}
fn place(&mut self, i: usize, fp: u8) -> bool {
for slot in &mut self.buckets[i] {
if *slot == 0 {
*slot = fp;
return true;
}
}
false
}
fn insert(&mut self, key: u64) -> bool {
let fp = Self::fingerprint(key);
let i1 = Self::index1(key, self.nbuckets);
if self.place(i1, fp) {
return true;
}
let i2 = Self::alt_index(i1, fp, self.nbuckets);
if self.place(i2, fp) {
return true;
}
let mut i = i2;
let mut carry = fp;
for kick in 0..500usize {
let victim_slot = kick & 3;
std::mem::swap(&mut carry, &mut self.buckets[i][victim_slot]);
i = Self::alt_index(i, carry, self.nbuckets);
if self.place(i, carry) {
return true;
}
}
false
}
fn has(&self, key: u64) -> bool {
let fp = Self::fingerprint(key);
let i1 = Self::index1(key, self.nbuckets);
if self.buckets[i1].contains(&fp) {
return true;
}
let i2 = Self::alt_index(i1, fp, self.nbuckets);
self.buckets[i2].contains(&fp)
}
}
impl Membership for CuckooFilter {
fn might_contain(&self, literal: &[u8]) -> bool {
all_ngrams_present(literal, |k| self.has(k))
}
fn name(&self) -> &'static str {
"cuckoo"
}
}
pub struct XorFilter {
fingerprints: Vec<u8>,
block: usize,
seed: u64,
}
impl XorFilter {
#[must_use]
pub fn build(corpus: &[u8]) -> Self {
let keys = ngram_keys(corpus);
let mut block = (((1.23 * keys.len() as f64).ceil() as usize + 32) / 3).max(1) + 1;
loop {
for seed in 0..64u64 {
if let Some(f) = Self::try_build(&keys, block, seed) {
return f;
}
}
block += block / 2 + 1;
}
}
fn fp(hash: u64) -> u8 {
(hash ^ (hash >> 32)) as u8
}
fn slots(hash: u64, block: usize) -> [usize; 3] {
let r0 = hash as u32;
let r1 = hash.rotate_left(21) as u32;
let r2 = hash.rotate_left(42) as u32;
[reduce(r0, block), block + reduce(r1, block), 2 * block + reduce(r2, block)]
}
fn try_build(keys: &[u64], block: usize, seed: u64) -> Option<Self> {
let size = block * 3;
let mut h_xor = vec![0u64; size];
let mut h_count = vec![0u32; size];
let hashes: Vec<u64> = keys.iter().map(|&k| hash_bytes(&k.to_le_bytes(), seed | 1)).collect();
for &h in &hashes {
for s in Self::slots(h, block) {
h_xor[s] ^= h;
h_count[s] += 1;
}
}
let mut stack: Vec<(usize, u64)> = Vec::with_capacity(keys.len());
let mut queue: Vec<usize> = (0..size).filter(|&s| h_count[s] == 1).collect();
while let Some(s) = queue.pop() {
if h_count[s] != 1 {
continue;
}
let h = h_xor[s];
stack.push((s, h));
for t in Self::slots(h, block) {
h_xor[t] ^= h;
h_count[t] -= 1;
if h_count[t] == 1 {
queue.push(t);
}
}
}
if stack.len() != keys.len() {
return None;
}
let mut fingerprints = vec![0u8; size];
while let Some((s, h)) = stack.pop() {
let [a, b, c] = Self::slots(h, block);
let other = fingerprints[a] ^ fingerprints[b] ^ fingerprints[c];
fingerprints[s] = Self::fp(h) ^ other;
}
Some(Self { fingerprints, block, seed: seed | 1 })
}
fn has(&self, key: u64) -> bool {
let h = hash_bytes(&key.to_le_bytes(), self.seed);
let [a, b, c] = Self::slots(h, self.block);
Self::fp(h) == (self.fingerprints[a] ^ self.fingerprints[b] ^ self.fingerprints[c])
}
}
impl Membership for XorFilter {
fn might_contain(&self, literal: &[u8]) -> bool {
all_ngrams_present(literal, |k| self.has(k))
}
fn name(&self) -> &'static str {
"xor"
}
}
#[derive(Clone, Debug, PartialEq, Eq)]
pub struct FilterCheck {
pub name: &'static str,
pub present: usize,
pub false_negatives: usize,
pub absent: usize,
pub rejected: usize,
}
#[must_use]
pub fn verify(corpus: &[u8]) -> Vec<FilterCheck> {
let filters: [Box<dyn Membership>; 3] = [
Box::new(BloomFilter::build(corpus)),
Box::new(CuckooFilter::build(corpus)),
Box::new(XorFilter::build(corpus)),
];
let mut present: Vec<&[u8]> = Vec::new();
for len in [4usize, 6, 8, 12, 16] {
if len > corpus.len() {
continue;
}
let step = (corpus.len() / 200).max(1);
let mut p = 0;
while p + len <= corpus.len() {
present.push(&corpus[p..p + len]);
p += step;
}
}
let mut absent: Vec<Vec<u8>> = Vec::new();
let mut state: u64 = 0x1234_5678_9ABC_DEF0;
while absent.len() < 500 {
state = state.wrapping_mul(6_364_136_223_846_793_005).wrapping_add(1_442_695_040_888_963_407);
let len = 6 + (state >> 60) as usize;
let probe: Vec<u8> = (0..len)
.map(|j| {
let r = state.rotate_left(j as u32 * 7);
b'!' + (r % 93) as u8
})
.collect();
if !crate::byte_simd::contains(corpus, &probe) {
absent.push(probe);
}
}
filters
.iter()
.map(|f| FilterCheck {
name: f.name(),
present: present.len(),
false_negatives: present.iter().filter(|l| !f.might_contain(l)).count(),
absent: absent.len(),
rejected: absent.iter().filter(|l| !f.might_contain(l)).count(),
})
.collect()
}
const DIRECT_SEARCH_MAX_LITERALS: usize = 1024;
#[must_use]
pub fn absent_guard_literals(pattern: &crate::ast::Pattern, input: &[u8]) -> HashSet<Vec<u8>> {
let mut lits: Vec<Vec<u8>> = Vec::new();
collect_guard_literals(pattern, &mut lits);
if lits.is_empty() {
return HashSet::new();
}
if lits.len() <= DIRECT_SEARCH_MAX_LITERALS {
return lits.into_iter().filter(|l| !crate::byte_simd::contains(input, l)).collect();
}
let filter = BloomFilter::build(input);
lits.into_iter().filter(|l| !filter.might_contain(l)).collect()
}
#[must_use]
pub fn requires_absent(pattern: &crate::ast::Pattern, input: &[u8]) -> bool {
requires_absent_with(pattern, input, None)
}
#[must_use]
pub fn requires_absent_with(
pattern: &crate::ast::Pattern,
input: &[u8],
filter: Option<&BloomFilter>,
) -> bool {
let mut lits: Vec<Vec<u8>> = Vec::new();
collect_required_literals(pattern, &mut lits);
let literal_absent = lits.iter().any(|l| match filter {
Some(f) if !f.might_contain(l) => true,
Some(_) | None => !crate::byte_simd::contains(input, l),
});
literal_absent || requires_absent_run(pattern, input)
}
#[must_use]
pub fn required_literal_count(pattern: &crate::ast::Pattern) -> usize {
let mut lits: Vec<Vec<u8>> = Vec::new();
collect_required_literals(pattern, &mut lits);
lits.len()
}
#[must_use]
pub fn all_absent_by(filter: &BloomFilter, lits: &[&str]) -> bool {
!lits.is_empty() && lits.iter().all(|l| !filter.might_contain(l.as_bytes()))
}
#[must_use]
pub fn direct_search_max_literals() -> usize {
DIRECT_SEARCH_MAX_LITERALS
}
#[must_use]
pub fn byte_routable_literal(pattern: &crate::ast::Pattern) -> Option<&str> {
use crate::ast::{Atom, Pattern};
use crate::orbit::OrbitGroup;
let Pattern::Atom(Atom::Literal(lit, OrbitGroup::Identity)) = pattern else {
return None;
};
let b = lit.as_bytes();
let opens = b.first().is_some_and(|c| c.is_ascii_alphabetic() || *c == b'_');
let word = b.iter().all(|c| c.is_ascii_alphanumeric() || *c == b'_');
(opens && word).then_some(lit.as_str())
}
pub(crate) fn settles_number(input: &[u8], s: usize, e: usize) -> bool {
if s >= e || !input[s..e].iter().all(u8::is_ascii_digit) {
return false;
}
let joins = |c: u8| {
c.is_ascii_alphanumeric()
|| matches!(c, b'.' | b':' | b'-' | b'_' | b'%' | b'$' | b',' | b'/' | b'+' | b'#')
|| c >= 0x80
};
if s > 0 && joins(input[s - 1]) {
return false;
}
if input.get(e).copied().is_some_and(joins) {
return false;
}
if input.get(e) == Some(&b' ') && crate::quantity::spaced_symbol_len(input, e + 1).is_some() {
return false;
}
if (3..=5).contains(&(e - s)) {
let after = input.get(e) == Some(&b' ')
&& input.get(e + 1).is_some_and(u8::is_ascii_digit);
let before = s >= 2 && input[s - 1] == b' ' && input[s - 2].is_ascii_digit();
if after || before {
return false;
}
}
true
}
#[must_use]
pub fn byte_route_first_number(input: &[u8]) -> Option<Option<crate::engine::Span>> {
byte_route_first_number_from(input, 0)
}
#[must_use]
pub fn byte_route_first_number_from(
input: &[u8],
from: usize,
) -> Option<Option<crate::engine::Span>> {
byte_route_first_number_reading(&ByteReader::new(input), from)
}
#[must_use]
pub(crate) fn byte_route_first_number_reading(
reader: &ByteReader<'_>,
from: usize,
) -> Option<Option<crate::engine::Span>> {
let input = reader.input;
let mut from = from.min(input.len());
while let Some(rel) = crate::byte_simd::digit_find(&input[from..]) {
let s = from + rel;
if reader.string_end(s).is_some() {
from = s + 1;
continue;
}
if reader.unsettled() {
return None;
}
if s > 0 && (input[s - 1].is_ascii_alphanumeric() || input[s - 1] == b'_') {
let mut w = s;
while input.get(w).is_some_and(|c| c.is_ascii_alphanumeric() || *c == b'_') {
w += 1;
}
from = w;
continue;
}
let mut e = s;
while input.get(e).is_some_and(|c| c.is_ascii_digit()) {
e += 1;
}
if !settles_number(input, s, e) {
return None;
}
return Some(Some(crate::engine::Span { start: s as u32, end: e as u32 }));
}
if reader.unsettled() {
return None;
}
Some(None)
}
#[must_use]
pub fn byte_route_first_word(input: &[u8]) -> Option<Option<crate::engine::Span>> {
byte_route_first_word_from(input, 0)
}
#[must_use]
pub fn byte_route_first_word_from(
input: &[u8],
from: usize,
) -> Option<Option<crate::engine::Span>> {
byte_route_first_word_reading(&ByteReader::new(input), from)
}
#[must_use]
pub(crate) fn byte_route_first_word_reading(
reader: &ByteReader<'_>,
from: usize,
) -> Option<Option<crate::engine::Span>> {
let input = reader.input;
let mut from = from.min(input.len());
while let Some(rel) =
input[from..].iter().position(|c| c.is_ascii_alphabetic() || *c == b'_')
{
let s = from + rel;
if reader.string_end(s).is_some() {
from = s + 1;
continue;
}
if reader.unsettled() {
return None;
}
if s > 0 && (input[s - 1].is_ascii_alphanumeric() || input[s - 1] == b'_') {
let mut w = s;
while input.get(w).is_some_and(|c| c.is_ascii_alphanumeric() || *c == b'_') {
w += 1;
}
from = w;
continue;
}
match reader.probe_starting_at(s) {
Probe::Settled(Read::TokenEndingAt(crate::token::TokenKind::Word, e)) => {
return Some(Some(crate::engine::Span { start: s as u32, end: e as u32 }));
}
Probe::Settled(
Read::TokenEndingAt(..) | Read::TokenStartingAt(..) | Read::TokenAt(..),
) => return None,
Probe::Settled(Read::NoToken) => {
from = s + 1;
continue;
}
Probe::Settled(Read::Unsettled) | Probe::Lex => return None,
}
}
if reader.unsettled() {
return None;
}
Some(None)
}
#[must_use]
pub fn byte_route_kind_from(
pattern: &crate::ast::Pattern,
input: &[u8],
at: usize,
) -> Option<Option<crate::engine::Span>> {
byte_route_kind_reading(pattern, input, &mut None, at)
}
#[must_use]
pub(crate) fn byte_route_first_quoted_reading(
reader: &ByteReader<'_>,
from: usize,
) -> Option<Option<crate::engine::Span>> {
let input = reader.input;
let next = |at: usize, q: u8| crate::byte_simd::find(&input[at..], &[q]).map(|r| at + r);
let mut from = from.min(input.len());
loop {
let q = match (next(from, b'"'), next(from, b'\'')) {
(Some(d), Some(s)) => d.min(s),
(Some(one), None) | (None, Some(one)) => one,
(None, None) => break,
};
let span = reader.string_span(q);
if reader.unsettled() {
return None;
}
match span {
Some((a, b)) if a == q => {
return Some(Some(crate::engine::Span {
start: a as u32,
end: (b + 1).min(input.len()) as u32,
}));
}
Some((_, b)) => from = b + 1,
None => {
if !reader.run_of(q, q + 1, false).blob
&& let Some(end) = crate::lexer::char_literal_end(input, q)
{
return Some(Some(crate::engine::Span {
start: q as u32,
end: end as u32,
}));
}
from = q + 1;
}
}
}
Some(None)
}
#[must_use]
pub(crate) fn byte_route_kind_reading<'i>(
pattern: &crate::ast::Pattern,
input: &'i [u8],
reader: &mut Option<ByteReader<'i>>,
at: usize,
) -> Option<Option<crate::engine::Span>> {
use crate::ast::{Atom, Pattern};
use crate::token::TokenKind;
match pattern {
Pattern::Atom(Atom::Kind(TokenKind::Number)) => byte_route_first_number_reading(
reader.get_or_insert_with(|| ByteReader::new(input)),
at,
),
Pattern::Atom(Atom::Kind(TokenKind::Word)) => byte_route_first_word_reading(
reader.get_or_insert_with(|| ByteReader::new(input)),
at,
),
Pattern::Atom(Atom::Kind(TokenKind::Quoted)) => byte_route_first_quoted_reading(
reader.get_or_insert_with(|| ByteReader::new(input)),
at,
),
_ => {
let codes = crate::kind_route::kind_sequence(pattern)?;
let word = TokenKind::Word.code();
if codes.len() < 2 || codes.iter().any(|&c| c != word) {
return None;
}
byte_route_first_word_run_reading(
reader.get_or_insert_with(|| ByteReader::new(input)),
codes.len(),
at,
)
}
}
}
#[must_use]
pub(crate) fn byte_route_first_word_run_reading(
reader: &ByteReader<'_>,
times: usize,
at: usize,
) -> Option<Option<crate::engine::Span>> {
let input = reader.input;
let mut at = at;
loop {
let first = byte_route_first_word_reading(reader, at)?;
let Some(first) = first else {
return Some(None);
};
let mut end = first.end as usize;
let mut held = 1usize;
while held < times {
let Some(rel) = input[end..].iter().position(|c| !c.is_ascii_whitespace()) else {
break;
};
let p = end + rel;
if !(input[p].is_ascii_alphabetic() || input[p] == b'_')
|| reader.string_end(p).is_some()
{
break;
}
match reader.probe_starting_at(p) {
Probe::Settled(Read::TokenEndingAt(crate::token::TokenKind::Word, e)) => {
end = e;
held += 1;
}
Probe::Settled(Read::Unsettled) | Probe::Lex => return None,
Probe::Settled(_) => break,
}
}
if held == times {
return Some(Some(crate::engine::Span { start: first.start, end: end as u32 }));
}
at = first.end as usize;
}
}
#[must_use]
pub fn byte_routable_line_anchored_literal(pattern: &crate::ast::Pattern) -> Option<&str> {
use crate::ast::{AnchorKind, Pattern};
let Pattern::Concat(v) = pattern else {
return None;
};
let [Pattern::Anchor(AnchorKind::LineStart), rest] = v.as_slice() else {
return None;
};
byte_routable_literal(rest)
}
#[must_use]
pub fn byte_route_first_line_anchored_literal(
lit: &str,
input: &[u8],
from: usize,
) -> Option<Option<crate::engine::Span>> {
byte_route_first_line_anchored_literal_reading(lit, &mut ByteReader::new(input), from)
}
#[must_use]
pub(crate) fn byte_route_first_line_anchored_literal_reading(
lit: &str,
reader: &mut ByteReader<'_>,
from: usize,
) -> Option<Option<crate::engine::Span>> {
let input = reader.input;
let mut from = from.min(input.len());
loop {
let Some(found) = byte_route_first_word_literal_reading(&[lit], reader, from)? else {
return Some(None);
};
if leads_its_line(input, found.start()) {
return Some(Some(found));
}
from = found.start() + 1;
}
}
#[must_use]
pub(crate) fn leads_its_line(input: &[u8], at: usize) -> bool {
input[..at].iter().rev().take_while(|&&c| c != b'\n').all(u8::is_ascii_whitespace)
}
#[must_use]
pub fn byte_routable_literals(pattern: &crate::ast::Pattern) -> Option<Vec<&str>> {
use crate::ast::Pattern;
if let Some(lit) = byte_routable_literal(pattern) {
return Some(vec![lit]);
}
let Pattern::Alt(branches, _) = pattern else {
return None;
};
let mut lits: Vec<&str> = Vec::with_capacity(branches.len());
for branch in branches {
let lit = byte_routable_literal(branch)?;
if !lits.contains(&lit) {
lits.push(lit);
}
}
(!lits.is_empty()).then_some(lits)
}
pub const CUT_ROUTE_THRESHOLD: usize = 160 * 1024;
fn cut_across_cores<F>(input: &[u8], route: F) -> Option<Vec<crate::engine::Span>>
where
F: Fn(&[u8]) -> Option<Vec<crate::engine::Span>> + Sync,
{
let cores = std::thread::available_parallelism().map_or(1, std::num::NonZero::get);
let n = input.len();
let mut bounds = crate::parallel_lex::safe_boundaries(input, cores * 4);
bounds.retain(|&b| b == 0 || b == n || input[b - 1] == b'\n');
let leaves = bounds.len() - 1;
crate::trace::rung("byte route across", "leaves", leaves);
let mut found: Vec<Option<Vec<crate::engine::Span>>> = vec![None; leaves];
let plan = flynnel::JobPlan::set_profile(
0,
u32::try_from(leaves).unwrap_or(u32::MAX),
flynnel::DispatchProfile::Streaming,
);
flynnel::sched::par_iter::for_each_chunk_indexed_min_leaf(&plan, &mut found, 1, |base, slots| {
for (k, slot) in slots.iter_mut().enumerate() {
let lo = bounds[base + k];
let hi = bounds[base + k + 1];
let rebase = u32::try_from(lo).expect("an input this route takes fits a u32 span");
*slot = route(&input[lo..hi]).map(|spans| {
spans
.into_iter()
.map(|s| crate::engine::Span { start: s.start + rebase, end: s.end + rebase })
.collect()
});
}
});
let mut out: Vec<crate::engine::Span> = Vec::new();
for leaf in found {
out.extend(leaf?);
}
Some(out)
}
fn cut_across_cores_reading_past<F>(input: &[u8], route: F) -> Option<Vec<crate::engine::Span>>
where
F: Fn(&[u8], usize) -> Option<Vec<crate::engine::Span>> + Sync,
{
let cores = std::thread::available_parallelism().map_or(1, std::num::NonZero::get);
let n = input.len();
let mut bounds = crate::parallel_lex::safe_boundaries(input, cores * 4);
bounds.retain(|&b| b == 0 || b == n || input[b - 1] == b'\n');
let leaves = bounds.len() - 1;
crate::trace::rung("byte route across", "leaves, reading past", leaves);
let mut found: Vec<Option<Vec<crate::engine::Span>>> = vec![None; leaves];
let plan = flynnel::JobPlan::set_profile(
0,
u32::try_from(leaves).unwrap_or(u32::MAX),
flynnel::DispatchProfile::Streaming,
);
flynnel::sched::par_iter::for_each_chunk_indexed_min_leaf(&plan, &mut found, 1, |base, slots| {
for (k, slot) in slots.iter_mut().enumerate() {
let lo = bounds[base + k];
let hi = bounds[base + k + 1];
let rebase = u32::try_from(lo).expect("an input this route takes fits a u32 span");
*slot = route(&input[lo..], hi - lo).map(|spans| {
spans
.into_iter()
.map(|s| crate::engine::Span { start: s.start + rebase, end: s.end + rebase })
.collect()
});
}
});
let mut out: Vec<crate::engine::Span> = Vec::new();
for leaf in found {
out.extend(leaf?);
}
Some(out)
}
#[must_use]
pub fn byte_route_word_literals(lits: &[&str], input: &[u8]) -> Option<Vec<crate::engine::Span>> {
if input.len() >= CUT_ROUTE_THRESHOLD {
crate::trace::rung("byte route", "word literals, cut across the cores", input.len());
return cut_across_cores(input, |chunk| byte_route_word_literals_one_pass(lits, chunk));
}
crate::trace::rung("byte route", "word literals, one pass", input.len());
byte_route_word_literals_one_pass(lits, input)
}
#[must_use]
pub fn byte_route_line_anchored_literal(lit: &str, input: &[u8]) -> Option<Vec<crate::engine::Span>> {
if input.len() >= CUT_ROUTE_THRESHOLD {
crate::trace::rung("byte route", "line-anchored literal, cut across the cores", input.len());
return cut_across_cores(input, |chunk| byte_route_line_anchored_literal_one_pass(lit, chunk));
}
crate::trace::rung("byte route", "line-anchored literal, one pass", input.len());
byte_route_line_anchored_literal_one_pass(lit, input)
}
#[must_use]
pub fn byte_route_line_anchored_literal_one_pass(
lit: &str,
input: &[u8],
) -> Option<Vec<crate::engine::Span>> {
let spans = byte_route_word_literals_one_pass(&[lit], input)?;
Some(spans.into_iter().filter(|s| leads_its_line(input, s.start as usize)).collect())
}
#[must_use]
pub fn byte_route_word_literals_one_pass(
lits: &[&str],
input: &[u8],
) -> Option<Vec<crate::engine::Span>> {
let mut reader = ByteReader::new(input);
if reader.unsettled() {
return None;
}
let mut out: Vec<crate::engine::Span> = Vec::new();
for lit in lits {
out.extend(route_word_literal(&mut reader, lit)?);
}
out.sort_by_key(|s| s.start);
Some(out)
}
#[must_use]
pub fn byte_route_any_word_literal(lits: &[&str], input: &[u8]) -> Option<bool> {
let mut reader = ByteReader::new(input);
if reader.unsettled() {
return None;
}
for lit in lits {
if first_word_literal(&mut reader, lit, 0)?.is_some() {
return Some(true);
}
}
Some(false)
}
#[must_use]
pub fn byte_route_first_word_literal(
lits: &[&str],
input: &[u8],
) -> Option<Option<crate::engine::Span>> {
byte_route_first_word_literal_from(lits, input, 0)
}
#[must_use]
pub fn byte_route_first_word_literal_from(
lits: &[&str],
input: &[u8],
from: usize,
) -> Option<Option<crate::engine::Span>> {
byte_route_first_word_literal_reading(lits, &mut ByteReader::new(input), from)
}
#[must_use]
pub(crate) fn byte_route_first_word_literal_reading(
lits: &[&str],
reader: &mut ByteReader<'_>,
from: usize,
) -> Option<Option<crate::engine::Span>> {
if reader.unsettled() {
return None;
}
let mut best: Option<crate::engine::Span> = None;
for lit in lits {
if let Some(s) = first_word_literal(reader, lit, from)?
&& best.is_none_or(|b| s.start < b.start)
{
best = Some(s);
}
}
Some(best)
}
fn first_word_literal(
reader: &mut ByteReader<'_>,
lit: &str,
start_at: usize,
) -> Option<Option<crate::engine::Span>> {
let pat = lit.as_bytes();
if pat.is_empty() {
return None;
}
let input = reader.input;
let mut from = start_at.min(input.len());
while let Some(rel) = crate::byte_simd::find(&input[from..], pat) {
let s = from + rel;
let e = s + pat.len();
from = s + 1;
if input.get(e).is_some_and(|&c| word_byte(c)) {
continue;
}
if s > 0 && (input[s - 1].is_ascii_alphabetic() || input[s - 1] == b'_') {
continue;
}
let settled = match reader.probe_ending_at(e) {
Probe::Settled(Read::TokenStartingAt(_, start)) => start == s,
Probe::Settled(Read::TokenEndingAt(..) | Read::TokenAt(..) | Read::NoToken) => false,
Probe::Settled(Read::Unsettled) => return None,
Probe::Lex => match reader.lex_ending_at(e) {
Read::TokenStartingAt(_, start) => start == s,
Read::TokenEndingAt(..) | Read::TokenAt(..) | Read::NoToken => false,
Read::Unsettled => return None,
},
};
if settled {
return Some(Some(crate::engine::Span { start: s as u32, end: e as u32 }));
}
}
Some(None)
}
#[derive(Clone, Copy, Debug, PartialEq, Eq)]
enum Read {
TokenStartingAt(crate::token::TokenKind, usize),
TokenEndingAt(crate::token::TokenKind, usize),
TokenAt(crate::token::TokenKind, usize),
NoToken,
Unsettled,
}
#[derive(Clone, Copy, Debug, PartialEq, Eq)]
enum Probe {
Settled(Read),
Lex,
}
struct WordRun {
ws: usize,
run_start: usize,
run_end: usize,
digits_end: usize,
seen: Option<u8>,
}
const fn word_byte(c: u8) -> bool {
c.is_ascii_alphanumeric() || c == b'_'
}
const fn plain_punct(c: u8) -> bool {
matches!(c, b'(' | b')' | b'[' | b']' | b'{' | b'}' | b',' | b';' | b'=' | b'<' | b'>' | b'!')
}
const fn settled_byte(c: u8) -> bool {
word_byte(c) || plain_punct(c) || c == b'.' || c == b'/' || c == b':'
}
const RUN_UNSETTLED: u8 = 1;
const RUN_JOINS: u8 = 2;
static RUN_BYTE: [u8; 256] = {
let mut t = [0u8; 256];
let mut c = 0usize;
while c < 256 {
#[allow(clippy::cast_possible_truncation)]
let b = c as u8;
if !settled_byte(b) {
t[c] |= RUN_UNSETTLED;
}
if b == b'.' || b == b'/' || b == b':' {
t[c] |= RUN_JOINS;
}
c += 1;
}
t
};
fn settled_run(run: &[u8]) -> bool {
run.iter().all(|&c| settled_byte(c)) && !run.windows(2).any(|w| w == b":/")
}
fn b64_byte(c: u8) -> bool {
c.is_ascii_alphanumeric() || c == b'/'
}
pub(crate) struct ByteReader<'a> {
input: &'a [u8],
quotes: std::cell::RefCell<crate::parallel_lex::QuoteScan<'a>>,
quote_cursor: std::cell::Cell<usize>,
run: std::cell::Cell<RunCache>,
word: std::cell::Cell<(usize, usize)>,
scratch: Vec<crate::token::Token>,
lexed: (usize, usize),
unsettled: std::cell::Cell<bool>,
}
#[derive(Clone, Copy, Default)]
struct RunCache {
start: usize,
end: usize,
blob: bool,
seen: u8,
seen_whole: bool,
}
impl RunCache {
fn run_of(&mut self, input: &[u8], s: usize, e: usize, gap_is_clear: bool) -> RunCache {
if !(self.start < self.end && self.start <= s && e <= self.end) {
let mut seen = 0u8;
let mut start = s;
for &c in input[..s].iter().rev() {
if c.is_ascii_whitespace() {
break;
}
seen |= RUN_BYTE[c as usize];
start -= 1;
}
let mut end = e;
for &c in &input[e..] {
if c.is_ascii_whitespace() {
break;
}
seen |= RUN_BYTE[c as usize];
end += 1;
}
let blob = end - start >= crate::spectral::BLOB_MIN_LEN
&& !crate::lexer::blob_runs_in_span(input, start, end).is_empty();
*self = RunCache { start, end, blob, seen, seen_whole: gap_is_clear };
}
*self
}
}
impl<'a> ByteReader<'a> {
pub(crate) fn new(input: &'a [u8]) -> Self {
Self {
input,
quotes: std::cell::RefCell::new(crate::parallel_lex::QuoteScan::new(input)),
quote_cursor: std::cell::Cell::new(0),
run: std::cell::Cell::new(RunCache::default()),
word: std::cell::Cell::new((0, 0)),
scratch: Vec::new(),
lexed: (0, 0),
unsettled: std::cell::Cell::new(false),
}
}
fn quotes_through(&self, p: usize) {
let input = self.input;
self.quotes.borrow_mut().ensure(p, &mut |q: usize| {
let run = self.run_of(q, q + 1, false);
if run.blob {
return Some(false);
}
let in_url = input[q] == b'\'' && input[run.start..q].windows(3).any(|w| w == b"://");
(!in_url).then_some(true)
});
if self.quotes.borrow().unsettled() {
self.unsettled.set(true);
}
}
fn run_of(&self, s: usize, e: usize, gap_is_clear: bool) -> RunCache {
let mut runs = self.run.get();
let run = runs.run_of(self.input, s, e, gap_is_clear);
self.run.set(runs);
run
}
fn word_run_at(&self, p: usize) -> (usize, usize) {
let (ws, we) = self.word.get();
if (ws..we).contains(&p) {
return (ws, we);
}
let input = self.input;
let ws = p - input[..p].iter().rev().take_while(|&&c| word_byte(c)).count();
let we = p + input[p..].iter().take_while(|&&c| word_byte(c)).count();
self.word.set((ws, we));
(ws, we)
}
fn string_end(&self, p: usize) -> Option<usize> {
self.string_span(p).map(|(_, e)| e)
}
fn string_span(&self, p: usize) -> Option<(usize, usize)> {
self.quotes_through(p);
let scan = self.quotes.borrow();
let quotes = scan.spans();
let mut k = self.quote_cursor.get();
while k > 0 && quotes[k - 1].0 > p {
k -= 1;
}
while k < quotes.len() && quotes[k].0 <= p {
k += 1;
}
self.quote_cursor.set(k);
(k > 0 && quotes[k - 1].1 >= p).then(|| quotes[k - 1])
}
fn unsettled(&self) -> bool {
self.unsettled.get()
}
fn settles_word(&self, word: &WordRun, e: usize) -> bool {
let (start, end, ws) = (word.run_start, word.run_end, word.ws);
let input = self.input;
if self.quantity_reaches(word) != Some(false) {
return false;
}
let run = &input[start..end];
let seen = word.seen.unwrap_or_else(|| {
let mut seen = 0u8;
for &c in run {
seen |= RUN_BYTE[c as usize];
}
seen
});
if seen & RUN_UNSETTLED != 0 {
return false;
}
if seen & RUN_JOINS == 0 {
return true;
}
let (mut joins, mut jwt, mut path, mut colon) = (false, false, false, false);
let mut prev = 0u8;
for (i, &c) in run.iter().enumerate() {
if !settled_byte(c) {
return false;
}
match c {
b'/' => {
if prev == b':' {
return false;
}
joins = true;
path |= i == 0 || matches!(prev, b'(' | b'[' | b'{' | b'.');
}
b'.' => joins = true,
b':' => {
joins = true;
colon = true;
}
b'J' => jwt |= i >= 2 && run[i - 2] == b'e' && prev == b'y',
_ => {}
}
prev = c;
}
if !joins {
return true;
}
let number_before_dot = ws >= 2 && input[ws - 1] == b'.' && {
let dot = ws - 1;
let before = dot - input[..dot].iter().rev().take_while(|&&c| word_byte(c)).count();
before < dot && input[before].is_ascii_digit()
};
if jwt
|| path
|| number_before_dot
|| (input.get(e) == Some(&b'.') && input.get(e + 1).is_some_and(u8::is_ascii_digit))
|| (colon && e - ws <= 4 && input[ws..e].iter().all(u8::is_ascii_hexdigit))
{
return false;
}
let body = input[..e].iter().rev().take_while(|&&c| b64_byte(c)).count()
+ input[e..end].iter().take_while(|&&c| b64_byte(c)).count();
body < crate::lexer::TYPED_WORD_RUN
}
fn word_run_ending_at(&self, e: usize) -> Option<WordRun> {
let input = self.input;
let (ws, _) = self.word_run_at(e - 1);
let run = self.run_of(ws, e, true);
if run.blob {
return None;
}
let digits_end = ws + input[ws..e].iter().take_while(|&&c| c.is_ascii_digit()).count();
Some(WordRun {
ws,
run_start: run.start,
run_end: run.end,
digits_end,
seen: run.seen_whole.then_some(run.seen),
})
}
fn lex_run(&mut self, start: usize, end: usize) -> usize {
let from = self.string_end(start).map_or(start, |close| close + 1);
if self.lexed != (from, end) {
crate::lexer::lex_run_into(&self.input[from..end], &mut self.scratch);
self.lexed = (from, end);
}
from
}
fn probe_ending_at(&self, e: usize) -> Probe {
self.probe_ending_at_carrying(e, true)
}
fn probe_ending_at_carrying(&self, e: usize, carry: bool) -> Probe {
let quoted = self.string_end(e - 1).is_some();
if self.unsettled() {
return Probe::Settled(Read::Unsettled);
}
if quoted {
return Probe::Settled(Read::NoToken);
}
let Some(mut run) = self.word_run_ending_at(e) else {
return Probe::Settled(Read::NoToken);
};
if !carry {
run.seen = None;
}
if run.digits_end == run.ws
&& e - run.ws < crate::lexer::TYPED_WORD_RUN
&& self.settles_word(&run, e)
{
return Probe::Settled(Read::TokenStartingAt(crate::token::TokenKind::Word, run.ws));
}
Probe::Lex
}
fn quantity_reaches(&self, run: &WordRun) -> Option<bool> {
let input = self.input;
if run.ws < 2 || !(input[run.ws - 1] == b' ' || input[run.ws - 1] >= 0x80) {
return Some(false);
}
crate::quantity::joins_the_number_before(input, run.ws)
}
fn phone_reaches(&self, run: &WordRun, from: usize) -> bool {
let input = self.input;
run.digits_end > run.ws
&& run.run_start == run.ws
&& run.run_start >= 2
&& input[run.run_start - 1] == b' '
&& input[run.run_start - 2].is_ascii_digit()
&& self.scratch.first().is_some_and(|t| from + t.end() > run.digits_end)
}
fn lex_ending_at(&mut self, e: usize) -> Read {
let Some(run) = self.word_run_ending_at(e) else {
return Read::NoToken;
};
match self.quantity_reaches(&run) {
Some(true) => return Read::NoToken,
None => return Read::Unsettled,
Some(false) => {}
}
let from = self.lex_run(run.run_start, run.run_end);
if self.phone_reaches(&run, from) {
return Read::Unsettled;
}
match self.scratch.iter().find(|t| from + t.end() == e) {
Some(t) => Read::TokenStartingAt(t.kind, from + t.start()),
None => Read::NoToken,
}
}
fn word_run_end(&self, s: usize) -> usize {
self.word_run_at(s).1
}
fn probe_starting_at(&self, s: usize) -> Probe {
let quoted = self.string_end(s).is_some();
if self.unsettled() {
return Probe::Settled(Read::Unsettled);
}
if quoted {
return Probe::Settled(Read::NoToken);
}
let e = self.word_run_end(s);
let Some(run) = self.word_run_ending_at(e) else {
return Probe::Settled(Read::NoToken);
};
if run.ws == s
&& e - s < crate::lexer::TYPED_WORD_RUN
&& self.settles_word(&run, e)
{
return Probe::Settled(Read::TokenEndingAt(crate::token::TokenKind::Word, e));
}
Probe::Lex
}
fn lex_starting_at(&mut self, s: usize) -> Read {
let e = self.word_run_end(s);
let Some(run) = self.word_run_ending_at(e) else {
return Read::NoToken;
};
match self.quantity_reaches(&run) {
Some(true) => return Read::NoToken,
None => return Read::Unsettled,
Some(false) => {}
}
let from = self.lex_run(run.run_start, run.run_end);
if self.phone_reaches(&run, from) {
return Read::Unsettled;
}
match self.scratch.iter().find(|t| from + t.start() == s) {
Some(t) => Read::TokenEndingAt(t.kind, from + t.end()),
None => Read::NoToken,
}
}
fn probe_punct_at(&self, q: usize) -> Probe {
let input = self.input;
let quoted = self.string_end(q).is_some();
if self.unsettled() {
return Probe::Settled(Read::Unsettled);
}
if quoted {
return Probe::Settled(Read::NoToken);
}
let run = self.run_of(q, q + 1, RUN_BYTE[input[q] as usize] == 0);
let (run_start, run_end) = (run.start, run.end);
if run.blob {
return Probe::Settled(Read::NoToken);
}
let settled = (run.seen_whole && run.seen & (RUN_UNSETTLED | RUN_JOINS) == 0)
|| settled_run(&input[run_start..run_end]);
if settled {
let body = input[run_start..q]
.iter()
.rev()
.skip_while(|&&c| c == b'=')
.take_while(|&&c| b64_byte(c))
.count();
if input[q] != b'=' || body < crate::lexer::TYPED_WORD_RUN {
return Probe::Settled(Read::TokenAt(crate::lexer::punct_kind(input[q]), q));
}
}
Probe::Lex
}
fn lex_punct_at(&mut self, q: usize) -> Read {
let RunCache { start: run_start, end: run_end, .. } =
self.run_of(q, q + 1, RUN_BYTE[self.input[q] as usize] == 0);
let from = self.lex_run(run_start, run_end);
match self.scratch.iter().find(|t| from + t.start() == q && from + t.end() == q + 1) {
Some(t) => Read::TokenAt(t.kind, q),
None => Read::NoToken,
}
}
}
fn drop_marked(out: &mut Vec<crate::engine::Span>, dropped: &[bool]) {
let mut i = 0;
out.retain(|_| {
i += 1;
!dropped[i - 1]
});
}
#[must_use]
pub fn byte_route_word_literal(lit: &str, input: &[u8]) -> Option<Vec<crate::engine::Span>> {
let mut reader = ByteReader::new(input);
if reader.unsettled() {
return None;
}
route_word_literal(&mut reader, lit)
}
#[must_use]
pub fn byte_route_word_literal_unsplit(
lit: &str,
input: &[u8],
) -> Option<Vec<crate::engine::Span>> {
let mut reader = ByteReader::new(input);
if reader.unsettled() {
return None;
}
let pat = lit.as_bytes();
if pat.is_empty() {
return None;
}
route_word_literal_over(&mut reader, pat, crate::byte_simd::occurrences_unsplit(input, pat))
}
#[must_use]
pub fn byte_route_word_literal_unprobed(lit: &str, input: &[u8]) -> Option<usize> {
let reader = ByteReader::new(input);
if reader.unsettled() {
return None;
}
let pat = lit.as_bytes();
if pat.is_empty() {
return None;
}
let mut kept = 0usize;
for s in crate::byte_simd::occurrences_unsplit(input, pat) {
let e = s + pat.len();
if input.get(e).is_some_and(|&c| word_byte(c)) {
continue;
}
if s > 0 && (input[s - 1].is_ascii_alphabetic() || input[s - 1] == b'_') {
continue;
}
kept += 1;
}
Some(kept)
}
#[must_use]
pub fn byte_route_word_literal_quote_only(lit: &str, input: &[u8]) -> Option<usize> {
let reader = ByteReader::new(input);
if reader.unsettled() {
return None;
}
let pat = lit.as_bytes();
if pat.is_empty() {
return None;
}
let mut kept = 0usize;
for s in crate::byte_simd::occurrences_unsplit(input, pat) {
let e = s + pat.len();
if input.get(e).is_some_and(|&c| word_byte(c)) {
continue;
}
if s > 0 && (input[s - 1].is_ascii_alphabetic() || input[s - 1] == b'_') {
continue;
}
if reader.string_end(e - 1).is_some() || reader.unsettled() {
continue;
}
kept += 1;
}
Some(kept)
}
#[must_use]
pub fn byte_route_word_literal_run_only(lit: &str, input: &[u8]) -> Option<usize> {
let reader = ByteReader::new(input);
if reader.unsettled() {
return None;
}
let pat = lit.as_bytes();
if pat.is_empty() {
return None;
}
let mut kept = 0usize;
for s in crate::byte_simd::occurrences_unsplit(input, pat) {
let e = s + pat.len();
if input.get(e).is_some_and(|&c| word_byte(c)) {
continue;
}
if s > 0 && (input[s - 1].is_ascii_alphabetic() || input[s - 1] == b'_') {
continue;
}
if reader.string_end(e - 1).is_some() || reader.unsettled() {
continue;
}
if reader.word_run_ending_at(e).is_some() {
kept += 1;
}
}
Some(kept)
}
fn route_word_literal_priced(input: &[u8], pat: &[u8], carry: bool) -> Option<usize> {
let reader = ByteReader::new(input);
if reader.unsettled() {
return None;
}
if pat.is_empty() {
return None;
}
let mut kept = 0usize;
for s in crate::byte_simd::occurrences_unsplit(input, pat) {
let e = s + pat.len();
if input.get(e).is_some_and(|&c| word_byte(c)) {
continue;
}
if s > 0 && (input[s - 1].is_ascii_alphabetic() || input[s - 1] == b'_') {
continue;
}
if let Probe::Settled(Read::TokenStartingAt(_, start)) =
reader.probe_ending_at_carrying(e, carry)
&& start == s
{
kept += 1;
}
}
Some(kept)
}
#[must_use]
pub fn byte_route_word_literal_carried(lit: &str, input: &[u8]) -> Option<usize> {
route_word_literal_priced(input, lit.as_bytes(), true)
}
#[must_use]
pub fn byte_route_word_literal_rescanned(lit: &str, input: &[u8]) -> Option<usize> {
route_word_literal_priced(input, lit.as_bytes(), false)
}
fn route_word_literal(reader: &mut ByteReader<'_>, lit: &str) -> Option<Vec<crate::engine::Span>> {
let pat = lit.as_bytes();
if pat.is_empty() {
return None;
}
let input = reader.input;
route_word_literal_over(reader, pat, crate::byte_simd::occurrences_unsplit(input, pat))
}
fn route_word_literal_over(
reader: &mut ByteReader<'_>,
pat: &[u8],
at: impl Iterator<Item = usize>,
) -> Option<Vec<crate::engine::Span>> {
let input = reader.input;
let mut out: Vec<crate::engine::Span> = Vec::new();
let mut deferred: Vec<usize> = Vec::new();
for s in at {
let e = s + pat.len();
if input.get(e).is_some_and(|&c| word_byte(c)) {
continue;
}
if s > 0 && (input[s - 1].is_ascii_alphabetic() || input[s - 1] == b'_') {
continue;
}
let span = crate::engine::Span { start: s as u32, end: e as u32 };
match reader.probe_ending_at(e) {
Probe::Settled(Read::TokenStartingAt(_, start)) if start == s => out.push(span),
Probe::Settled(
Read::TokenStartingAt(..)
| Read::TokenEndingAt(..)
| Read::TokenAt(..)
| Read::NoToken,
) => {}
Probe::Settled(Read::Unsettled) => return None,
Probe::Lex => {
deferred.push(out.len());
out.push(span);
}
}
}
if !deferred.is_empty() {
let mut dropped = vec![false; out.len()];
for &i in &deferred {
let span = out[i];
dropped[i] = match reader.lex_ending_at(span.end as usize) {
Read::TokenStartingAt(_, start) => start != span.start as usize,
Read::TokenEndingAt(..) | Read::TokenAt(..) | Read::NoToken => true,
Read::Unsettled => return None,
};
}
drop_marked(&mut out, &dropped);
}
Some(out)
}
fn flat_atom_sequence(pattern: &crate::ast::Pattern) -> Option<Vec<&crate::ast::Atom>> {
use crate::ast::Pattern;
fn atom_of(p: &Pattern) -> Option<&crate::ast::Atom> {
match p {
Pattern::Atom(a) => Some(a),
Pattern::Bind(_, false, inner) => atom_of(inner),
_ => None,
}
}
let atoms: Vec<&crate::ast::Atom> = match pattern {
Pattern::Concat(parts) => parts.iter().map(atom_of).collect::<Option<Vec<_>>>()?,
other => vec![atom_of(other)?],
};
atoms.iter().all(|a| decides_from_its_own_token(a)).then_some(atoms)
}
fn decides_from_its_own_token(atom: &crate::ast::Atom) -> bool {
use crate::ast::Atom;
match atom {
Atom::Literal(_, crate::orbit::OrbitGroup::Identity)
| Atom::Kind(_)
| Atom::Any
| Atom::Byte(_)
| Atom::BytePattern(_) => true,
Atom::Class(c) => {
c.any.iter().chain(&c.all).chain(&c.none).all(decides_from_its_own_token)
}
_ => false,
}
}
fn inside_a_run(runs: &[(usize, usize)], at: usize) -> bool {
let i = runs.partition_point(|&(s, _)| s <= at);
i > 0 && runs[i - 1].1 > at
}
#[must_use]
pub fn scan_by_literal_windows(
pattern: &crate::ast::Pattern,
input: &[u8],
) -> Option<Vec<crate::engine::Span>> {
scan_by_literal_windows_at(pattern, input, 0)
}
#[must_use]
pub fn scan_by_literal_windows_at(
pattern: &crate::ast::Pattern,
input: &[u8],
at: usize,
) -> Option<Vec<crate::engine::Span>> {
let finding = crate::trace::phase("the literal route: its anchors");
let (anchors, compiled, atoms) = literal_window_anchors(pattern, input)?;
drop(finding);
let anchors = &anchors[anchors.partition_point(|a| (a.start as usize) < at)..];
if anchors.is_empty() {
return Some(Vec::new());
}
let tabling = crate::trace::phase("the literal route: the blob table");
let blobs = crate::lexer::blob_runs_parallel(input);
drop(tabling);
let reserve = atoms + 1;
let guarding = crate::trace::phase("the literal route: the absent guards");
let absent = absent_guard_literals(pattern, input);
drop(guarding);
let starts: Vec<usize> = anchors.iter().map(|a| a.start as usize).collect();
let scanning = crate::trace::phase("the literal route: the windows");
let found = windows_matching(input, &starts, &blobs, &compiled, &absent, reserve, start_width(reserve));
drop(scanning);
let mut kept: Vec<crate::engine::Span> = Vec::with_capacity(found.len());
let mut from = u32::try_from(at).expect("an offset within the span's width");
for (s, sp) in found.into_iter().flatten() {
let sp = crate::engine::Span {
start: sp.start + s as u32,
end: sp.end + s as u32,
};
if sp.start >= from {
from = sp.end;
kept.push(sp);
}
}
Some(kept)
}
#[must_use]
pub fn settled_prefix_matches(
pattern: &crate::ast::Pattern,
input: &[u8],
upto: usize,
) -> Option<(Vec<crate::engine::Span>, bool)> {
if !settles_from_a_prefix(pattern) {
return None;
}
let upto = upto.min(input.len());
let whole = upto == input.len();
let prefix = &input[..upto];
let toks = crate::lexer::lex(prefix);
let found = crate::nfa::scan_nfa_over_serial(pattern, prefix, &toks)?;
if whole {
return Some((found, true));
}
let reserve = crate::nfa::bounded_max_len(pattern).unwrap_or(1).max(1)
+ pattern.widest_forward_window();
let settled: Vec<crate::engine::Span> =
found.into_iter().filter(|s| end_clear_of_the_cut(&toks, s.end(), reserve)).collect();
Some((settled, false))
}
#[must_use]
pub fn first_by_literal_windows(
pattern: &crate::ast::Pattern,
input: &[u8],
) -> Option<Option<crate::engine::Span>> {
first_by_literal_windows_at(pattern, input, 0)
}
#[must_use]
pub fn first_by_literal_windows_at(
pattern: &crate::ast::Pattern,
input: &[u8],
at: usize,
) -> Option<Option<crate::engine::Span>> {
use crate::ast::Atom;
if !settles_from_a_prefix(pattern) {
crate::trace::rung("first windows", "no: a prefix cannot settle it", input.len());
return None;
}
let Some(atoms) = flat_atom_sequence(pattern) else {
crate::trace::rung("first windows", "no: not a flat sequence of plain atoms", input.len());
return None;
};
let Some(Atom::Literal(lit, crate::orbit::OrbitGroup::Identity)) = atoms.first() else {
crate::trace::rung("first windows", "no: it opens with no plain literal", input.len());
return None;
};
if byte_routable_literal(&crate::ast::Pattern::Atom(Atom::Literal(
(*lit).clone(),
crate::orbit::OrbitGroup::Identity,
)))
.is_none()
{
crate::trace::rung("first windows", "no: the literal is not a word token", input.len());
return None;
}
let Some(compiled) = crate::nfa::compile_pattern(pattern) else {
crate::trace::rung("first windows", "no: the engine declines it", input.len());
return None;
};
let pat = lit.as_bytes();
let absent = absent_guard_literals(pattern, input);
let reserve = atoms.len() + 1;
let mut width = 4 * reserve + 8;
let mut toks: Vec<crate::token::Token> = Vec::new();
let mut seams = crate::lexer::Seams::default();
let mut chunk: Vec<(usize, usize)> = Vec::new();
let mut scratch = crate::nfa::AttemptScratch::for_program(&compiled);
let mut tried = 0usize;
let mut from = at.min(input.len());
let mut quote_free = 0usize;
while let Some(rel) = crate::byte_simd::find(&input[from..], pat) {
let s = from + rel;
from = s + 1;
if quote_free < s {
if input[quote_free..s].iter().any(|&c| c == b'"' || c == b'\'') {
crate::trace::rung("first windows", "no: a quote opens before the match", s);
return None;
}
quote_free = s;
}
if input.get(s + pat.len()).is_some_and(|&c| word_byte(c)) {
continue;
}
if s > 0 && (input[s - 1].is_ascii_alphabetic() || input[s - 1] == b'_') {
continue;
}
let lo = run_start(input, s);
let hi = run_end(input, (s + LOCAL_BLOB_REACH).min(input.len()));
let local = crate::lexer::blob_runs(&input[lo..hi]);
let blobs: Vec<(usize, usize)> = local.iter().map(|&(a, b)| (lo + a, lo + b)).collect();
tried += 1;
let Some((s, e)) =
window_tokens(input, s, &blobs, reserve, &mut width, &mut toks, &mut seams, &mut chunk)
else {
continue;
};
if e > hi {
crate::trace::rung("first windows", "no: a window outgrew its blob region", e - s);
return None;
}
if let Some(sp) =
crate::nfa::match_at_first_token(&compiled, &input[s..e], &toks, &mut scratch, &absent)
{
crate::trace::rung("first windows", "yes: found it", tried);
return Some(Some(crate::engine::Span {
start: sp.start + s as u32,
end: sp.end + s as u32,
}));
}
}
crate::trace::rung("first windows", "yes: no match anywhere", tried);
Some(None)
}
const LOCAL_BLOB_REACH: usize = 4096;
fn run_start(input: &[u8], at: usize) -> usize {
let mut lo = at.min(input.len());
while lo > 0 && !input[lo - 1].is_ascii_whitespace() {
lo -= 1;
}
lo
}
fn run_end(input: &[u8], at: usize) -> usize {
let at = at.min(input.len());
at + input[at..].iter().take_while(|&&c| !c.is_ascii_whitespace()).count()
}
fn literal_window_anchors(
pattern: &crate::ast::Pattern,
input: &[u8],
) -> Option<(Vec<crate::engine::Span>, crate::nfa::Compiled, usize)> {
use crate::ast::Atom;
if !settles_from_a_prefix(pattern) {
crate::trace::rung("windows", "no: a prefix cannot settle this pattern", input.len());
return None;
}
let Some(atoms) = flat_atom_sequence(pattern) else {
crate::trace::rung("windows", "no: not a flat sequence of plain atoms", input.len());
return None;
};
let Some(Atom::Literal(lit, crate::orbit::OrbitGroup::Identity)) = atoms.first() else {
crate::trace::rung("windows", "no: it does not open with a plain literal", input.len());
return None;
};
byte_routable_literal(&crate::ast::Pattern::Atom(Atom::Literal(
(*lit).clone(),
crate::orbit::OrbitGroup::Identity,
)))?;
if atoms.len() == 1 && byte_routable_literals(pattern).is_some() {
crate::trace::rung("windows", "no: the byte literal route answers it whole", input.len());
return None;
}
let compiled = crate::nfa::compile_pattern(pattern)?;
let mut reader = ByteReader::new(input);
if reader.unsettled() {
return None;
}
let anchors = route_word_literal(&mut reader, lit)?;
Some((anchors, compiled, atoms.len()))
}
#[must_use]
pub fn scan_captures_by_literal_windows(
pattern: &crate::ast::Pattern,
input: &[u8],
) -> Option<Vec<crate::engine::Match>> {
let (anchors, compiled, atoms) = literal_window_anchors(pattern, input)?;
let blobs = crate::lexer::blob_runs_parallel(input);
let absent = absent_guard_literals(pattern, input);
let reserve = atoms + 1;
let starts: Vec<usize> = anchors.iter().map(|a| a.start as usize).collect();
let found =
windows_capturing(input, &starts, &blobs, &compiled, &absent, reserve, start_width(reserve));
let mut kept: Vec<crate::engine::Match> = Vec::with_capacity(found.len());
let mut from = 0usize;
for (s, mut m) in found.into_iter().flatten() {
m.start += s;
m.end += s;
if m.start < from {
continue;
}
from = m.end;
for sp in m.captures_mut() {
*sp = crate::engine::Span { start: sp.start + s as u32, end: sp.end + s as u32 };
}
kept.push(m);
}
Some(kept)
}
#[doc(hidden)]
#[must_use]
pub fn anchor_windows_unscanned(pattern: &crate::ast::Pattern, input: &[u8]) -> Option<usize> {
let (anchors, compiled, atoms) = literal_window_anchors(pattern, input)?;
let blobs = crate::lexer::blob_runs_parallel(input);
let absent = absent_guard_literals(pattern, input);
let reserve = atoms + 1;
let starts: Vec<usize> = anchors.iter().map(|a| a.start as usize).collect();
let found = windows_over(
input,
&starts,
&blobs,
&compiled,
&absent,
reserve,
start_width(reserve),
|_, _, toks, _, _| Some(toks.len()),
);
Some(found.iter().flatten().map(|&(_, n)| n).sum())
}
#[must_use]
pub fn scan_flat_by_literal_windows(
pattern: &crate::ast::Pattern,
input: &[u8],
) -> Option<(Vec<crate::nfa::FlatMatch>, std::sync::Arc<[String]>)> {
let (anchors, compiled, atoms) = literal_window_anchors(pattern, input)?;
let shape = crate::nfa::flat_shape(&compiled)?;
let blobs = crate::lexer::blob_runs_parallel(input);
let absent = absent_guard_literals(pattern, input);
let reserve = atoms + 1;
let starts: Vec<usize> = anchors.iter().map(|a| a.start as usize).collect();
let found = windows_over(
input,
&starts,
&blobs,
&compiled,
&absent,
reserve,
start_width(reserve),
|c, i, t, s, _| crate::nfa::flat_regs_at_first_token(c, &shape, i, t, s),
);
let mut kept: Vec<crate::nfa::FlatMatch> = Vec::with_capacity(found.len());
let mut from = 0u32;
for (s, m) in found.into_iter().flatten() {
let m = rebased(m, s as u32);
if m.span.start < from {
continue;
}
from = m.span.end;
kept.push(m);
}
Some((kept, crate::nfa::names_of(&compiled)))
}
#[must_use]
pub fn bytes_walk_the_shape(pattern: &crate::ast::Pattern) -> bool {
crate::nfa::compile_pattern(pattern)
.and_then(|c| crate::nfa::flat_shape(&c))
.is_some_and(|s| s.walks_from_bytes())
}
#[must_use]
pub fn flat_captures_by_byte_bounds(
pattern: &crate::ast::Pattern,
input: &[u8],
spans: &[crate::engine::Span],
) -> Option<(Vec<crate::nfa::FlatMatch>, std::sync::Arc<[String]>)> {
let compiled = crate::nfa::compile_pattern(pattern)?;
let shape = crate::nfa::flat_shape(&compiled)?;
let out: Option<Vec<crate::nfa::FlatMatch>> =
spans.iter().map(|&s| shape.regs_from_bytes(input, s)).collect();
Some((out?, crate::nfa::names_of(&compiled)))
}
#[must_use]
pub fn flat_captures_by_windows(
pattern: &crate::ast::Pattern,
input: &[u8],
spans: &[crate::engine::Span],
) -> Option<(Vec<crate::nfa::FlatMatch>, std::sync::Arc<[String]>)> {
if !settles_from_a_prefix(pattern) {
return None;
}
let atoms = flat_atom_sequence(pattern)?;
let compiled = crate::nfa::compile_pattern(pattern)?;
let shape = crate::nfa::flat_shape(&compiled)?;
let blobs = crate::lexer::blob_runs_parallel(input);
let absent = absent_guard_literals(pattern, input);
let reserve = atoms.len() + 1;
let starts: Vec<usize> = spans.iter().map(|s| s.start()).collect();
let found = windows_over(
input,
&starts,
&blobs,
&compiled,
&absent,
reserve,
start_width(reserve),
|c, i, t, s, _| crate::nfa::flat_regs_at_first_token(c, &shape, i, t, s),
);
let out: Option<Vec<crate::nfa::FlatMatch>> =
found.into_iter().map(|slot| slot.map(|(s, m)| rebased(m, s as u32))).collect();
let out = out?;
(out.len() == spans.len() && out.iter().zip(spans).all(|(m, s)| m.span.start() == s.start()))
.then_some((out, crate::nfa::names_of(&compiled)))
}
fn rebased(mut m: crate::nfa::FlatMatch, at: u32) -> crate::nfa::FlatMatch {
let shift = |s: crate::engine::Span| crate::engine::Span { start: s.start + at, end: s.end + at };
m.span = shift(m.span);
for r in &mut m.regs {
*r = shift(*r);
}
m
}
#[must_use]
pub fn captures_by_windows(
pattern: &crate::ast::Pattern,
input: &[u8],
spans: &[crate::engine::Span],
) -> Option<Vec<crate::engine::Match>> {
if !settles_from_a_prefix(pattern) {
return None;
}
let atoms = flat_atom_sequence(pattern)?;
let compiled = crate::nfa::compile_pattern(pattern)?;
let blobs = crate::lexer::blob_runs_parallel(input);
let absent = absent_guard_literals(pattern, input);
let reserve = atoms.len() + 1;
let starts: Vec<usize> = spans.iter().map(|s| s.start()).collect();
let found =
windows_capturing(input, &starts, &blobs, &compiled, &absent, reserve, start_width(reserve));
let out: Option<Vec<crate::engine::Match>> = found
.into_iter()
.map(|slot| {
slot.map(|(s, mut m)| {
m.start += s;
m.end += s;
for sp in m.captures_mut() {
*sp = crate::engine::Span {
start: sp.start + s as u32,
end: sp.end + s as u32,
};
}
m
})
})
.collect();
let out = out?;
(out.len() == spans.len() && out.iter().zip(spans).all(|(m, s)| m.start == s.start()))
.then_some(out)
}
#[allow(clippy::too_many_arguments)]
fn windows_matching(
input: &[u8],
starts: &[usize],
blobs: &[(usize, usize)],
compiled: &crate::nfa::Compiled,
absent: &std::collections::HashSet<Vec<u8>>,
reserve: usize,
width: usize,
) -> Vec<Option<(usize, crate::engine::Span)>> {
match crate::nfa::flat_shape(compiled) {
Some(shape) => windows_over(input, starts, blobs, compiled, absent, reserve, width, |c, i, t, s, _| {
crate::nfa::flat_match_at_first_token(c, &shape, i, t, s)
}),
None => windows_over(
input,
starts,
blobs,
compiled,
absent,
reserve,
width,
crate::nfa::match_at_first_token,
),
}
}
#[allow(clippy::too_many_arguments)]
fn windows_capturing(
input: &[u8],
starts: &[usize],
blobs: &[(usize, usize)],
compiled: &crate::nfa::Compiled,
absent: &std::collections::HashSet<Vec<u8>>,
reserve: usize,
width: usize,
) -> Vec<Option<(usize, crate::engine::Match)>> {
match crate::nfa::flat_shape(compiled) {
Some(shape) => windows_over(input, starts, blobs, compiled, absent, reserve, width, |c, i, t, s, _| {
crate::nfa::flat_captures_at_first_token(c, &shape, i, t, s)
}),
None => windows_over(
input,
starts,
blobs,
compiled,
absent,
reserve,
width,
crate::nfa::captures_at_first_token,
),
}
}
fn start_width(reserve: usize) -> usize {
4 * reserve + 8
}
fn settled_past_the_match(toks: &[crate::token::Token], reserve: usize, edge: usize) -> bool {
toks.iter()
.filter(|t| t.is_significant())
.nth(reserve)
.is_some_and(|t| t.end() < edge)
}
#[allow(clippy::too_many_arguments)]
fn windows_over<T: Send>(
input: &[u8],
starts: &[usize],
blobs: &[(usize, usize)],
compiled: &crate::nfa::Compiled,
absent: &std::collections::HashSet<Vec<u8>>,
reserve: usize,
start_width: usize,
attempt: impl Fn(
&crate::nfa::Compiled,
&[u8],
&[crate::token::Token],
&mut crate::nfa::AttemptScratch,
&std::collections::HashSet<Vec<u8>>,
) -> Option<T>
+ Sync,
) -> Vec<Option<(usize, T)>> {
let mut found: Vec<Option<(usize, T)>> = Vec::new();
found.resize_with(starts.len(), || None);
let cores = std::thread::available_parallelism().map_or(1, std::num::NonZero::get);
let min_leaf = found.len().div_ceil(cores * 4).max(64);
let plan = flynnel::JobPlan::new(0, found.len() as u32)
.with_leaf_shape(flynnel::LeafShape::Streaming)
.with_estimated_per_item_ns(WINDOW_NS_ESTIMATE);
flynnel::sched::par_iter::for_each_chunk_indexed_min_leaf(
&plan,
&mut found,
min_leaf,
|base, slots| {
let mut width = start_width;
let mut toks: Vec<crate::token::Token> = Vec::new();
let mut seams = crate::lexer::Seams::default();
let mut chunk: Vec<(usize, usize)> = Vec::new();
let mut wide_toks: Vec<crate::token::Token> = Vec::new();
let mut wide_seams = crate::lexer::Seams::default();
let mut wide_chunk: Vec<(usize, usize)> = Vec::new();
let mut scratch = crate::nfa::AttemptScratch::for_program(compiled);
for (i, slot) in slots.iter_mut().enumerate() {
let Some((s, e)) = window_tokens(
input,
starts[base + i],
blobs,
reserve,
&mut width,
&mut toks,
&mut seams,
&mut chunk,
) else {
continue;
};
let Some(answer) = attempt(compiled, &input[s..e], &toks, &mut scratch, absent)
else {
continue;
};
let mut settled = e;
while settled < input.len() {
if settled_past_the_match(&toks, reserve, settled - s) {
break;
}
let wider = (s + (settled - s) * 2).min(input.len());
lex_window_into(
input,
s,
wider,
blobs,
&mut wide_toks,
&mut wide_seams,
&mut wide_chunk,
);
if same_tokens_within(&toks, &wide_toks, settled - s) {
break;
}
std::mem::swap(&mut toks, &mut wide_toks);
settled = wider;
}
if settled == e {
*slot = Some((s, answer));
continue;
}
width = width.max(settled - s);
*slot = attempt(compiled, &input[s..settled], &toks, &mut scratch, absent)
.map(|t| (s, t));
}
},
);
found
}
const WINDOW_NS_ESTIMATE: u32 = 170;
fn lex_window_into(
input: &[u8],
s: usize,
e: usize,
blobs: &[(usize, usize)],
toks: &mut Vec<crate::token::Token>,
seams: &mut crate::lexer::Seams,
chunk: &mut Vec<(usize, usize)>,
) {
toks.clear();
seams.open.clear();
seams.close.clear();
chunk.clear();
let lo = blobs.partition_point(|&(a, _)| a < s);
let hi = blobs.partition_point(|&(a, _)| a < e);
chunk.extend(blobs[lo..hi].iter().filter(|&&(_, b)| b <= e).map(|&(a, b)| (a - s, b - s)));
crate::lexer::lex_chunk_into(&input[s..e], chunk, toks, seams);
}
fn same_tokens_within(
narrow: &[crate::token::Token],
wide: &[crate::token::Token],
upto: usize,
) -> bool {
let within = |t: &&crate::token::Token| t.end() <= upto;
let mut a = narrow.iter().filter(within);
let mut b = wide.iter().filter(within);
loop {
match (a.next(), b.next()) {
(None, None) => return true,
(Some(x), Some(y))
if x.kind == y.kind && x.start() == y.start() && x.end() == y.end() => {}
_ => return false,
}
}
}
#[allow(clippy::too_many_arguments)]
fn window_tokens(
input: &[u8],
s: usize,
blobs: &[(usize, usize)],
reserve: usize,
width: &mut usize,
toks: &mut Vec<crate::token::Token>,
seams: &mut crate::lexer::Seams,
chunk: &mut Vec<(usize, usize)>,
) -> Option<(usize, usize)> {
if inside_a_run(blobs, s) {
return None;
}
loop {
let e = (s + *width).min(input.len());
let whole = e == input.len();
if !whole && inside_a_run(blobs, e) {
*width *= 2;
continue;
}
let slice = &input[s..e];
toks.clear();
seams.open.clear();
seams.close.clear();
chunk.clear();
let lo = blobs.partition_point(|&(a, _)| a < s);
let hi = blobs.partition_point(|&(a, _)| a < e);
chunk.extend(blobs[lo..hi].iter().filter(|&&(_, b)| b <= e).map(|&(a, b)| (a - s, b - s)));
crate::lexer::lex_chunk_into(slice, chunk, toks, seams);
if !whole && toks.iter().filter(|t| t.is_significant()).count() < reserve {
*width *= 2;
continue;
}
return Some((s, e));
}
}
#[cfg(test)]
mod literal_window_tests {
use super::scan_by_literal_windows;
fn spans(v: &[crate::engine::Span]) -> Vec<(usize, usize)> {
v.iter().map(|s| (s.start(), s.end())).collect()
}
fn agrees(src: &str, text: &str) {
let p = crate::parser::parse(src).expect("parses");
let input = text.as_bytes();
let Some(got) = scan_by_literal_windows(&p, input) else {
return;
};
assert_eq!(spans(&got), spans(&crate::engine::scan(&p, input)), "{src}");
}
#[test]
fn a_window_answers_what_the_whole_scan_answers() {
let mut plain = String::new();
for i in 0..400u32 {
plain.push_str(&format!("let value_{i} = {} ; call_{i}(a, b) ;\n", i * 37));
}
let mut blob = String::from("let a = 1 ;\nx ");
for i in 0..900u32 {
blob.push_str(&format!("aZ9+let+kQ2mX7pL4vB8n{}", i % 7));
}
blob.push_str(" ;\nlet b = 2 ;\n");
for (src, text) in [
("\"let\" \\W \"=\"", plain.as_str()),
("\"let\" \\W:v \"=\"", plain.as_str()),
("\"let\"", plain.as_str()),
("\"let\" \\W", plain.as_str()),
("\"let\" \\W \"=\"", blob.as_str()),
("\"let\"", blob.as_str()),
("\"let\" \\W \"=\"", "let a = 1 ; let b = \"never closed ; let c = 3 ;\n"),
("\"let\"", "let a = 1 ; let b = \"never closed ; let c = 3 ;\n"),
("\"let\" \\W \"=\"", "xlet y = 1 ; letx z = 2 ; let w = 3 ;\n"),
("\"let\"", "a b let"),
("\"let\" \\W \"=\"", "a b let"),
("\"let\"", ""),
("\"let\" \\W \"=\"", "let a = 1 ; let a = 2 ; let a = 3 ;\n"),
] {
agrees(src, text);
}
}
#[test]
fn one_literal_atom_is_left_to_the_route_that_answers_it() {
let mut text = String::new();
for i in 0..400u32 {
text.push_str(&format!("let value_{i} = {} ; call_{i}(alpha, beta) ;\n", i * 37));
}
let input = text.as_bytes();
for src in ["\"let\"", "\"alpha\""] {
let p = crate::parser::parse(src).expect("parses");
assert!(scan_by_literal_windows(&p, input).is_none(), "{src} took the windows");
assert!(
super::scan_captures_by_literal_windows(&p, input).is_none(),
"{src} took the capturing windows"
);
let found = crate::engine::scan(&p, input);
let lit = src.trim_matches('"');
assert_eq!(
spans(&found),
spans(&super::byte_route_word_literals(&[lit], input).expect("the bytes settle it")),
"{src}"
);
assert_eq!(found.len(), 400, "{src}");
}
}
#[test]
fn stopping_from_an_offset_gives_the_scans_first_match_there() {
let mut text = String::new();
for i in 0..400u32 {
text.push_str(&format!("let value_{i} = {} ; call_{i}(a, b) ;\n", i * 37));
}
let input = text.as_bytes();
for src in ["\"let\" \\W \"=\"", "\"let\" \\W:v \"=\"", "\"let\""] {
let p = crate::parser::parse(src).expect("parses");
let all = crate::engine::scan(&p, input);
let mut offsets: Vec<usize> = all.iter().flat_map(|s| [s.start(), s.end()]).collect();
offsets.push(0);
offsets.push(input.len());
offsets.push(input.len() + 1);
for at in offsets.into_iter().take(64) {
let Some(got) = super::first_by_literal_windows_at(&p, input, at) else {
continue;
};
let want = all.iter().copied().find(|s| s.start() >= at);
assert_eq!(
got.map(|s| (s.start(), s.end())),
want.map(|s| (s.start(), s.end())),
"{src} from {at}"
);
}
}
}
#[test]
fn stopping_at_the_first_window_gives_the_scans_first_match() {
let mut plain = String::new();
for i in 0..400u32 {
plain.push_str(&format!("let value_{i} = {} ; call_{i}(a, b) ;\n", i * 37));
}
let late = format!("{}\nlet z = 1 ;\n", "x y ; ".repeat(4000));
let bytes_only = "xlet y = 1 ; letx z = 2 ; letter w = 3 ;\n".repeat(200);
let unclosed = "a = 1 ; b = \"never closed ; let c = 3 ;\n".to_string();
for (src, text) in [
("\"let\" \\W \"=\"", &plain),
("\"let\" \\W:v \"=\"", &plain),
("\"let\"", &plain),
("\"let\" \\W \"=\"", &late),
("\"let\" \\W \"=\"", &bytes_only),
("\"let\"", &bytes_only),
("\"let\" \\W \"=\"", &unclosed),
("\"let\" \\W \"=\"", &String::new()),
] {
let p = crate::parser::parse(src).expect("parses");
let input = text.as_bytes();
let Some(got) = super::first_by_literal_windows(&p, input) else {
continue;
};
let want = crate::engine::scan(&p, input).into_iter().next();
assert_eq!(
got.map(|s| (s.start(), s.end())),
want.map(|s| (s.start(), s.end())),
"{src} over {} bytes",
input.len()
);
}
}
#[test]
fn one_pass_over_the_windows_gives_what_two_passes_give() {
let mut text = String::new();
for i in 0..400u32 {
text.push_str(&format!("let value_{i} = {} ; call_{i}(a, b) ;\n", i * 37));
}
let input = text.as_bytes();
for src in ["\"let\" \\W:v \"=\"", "\"let\" \\W \"=\"", "\"let\" \\W:v \"=\" \\N:n"] {
let p = crate::parser::parse(src).expect("parses");
let Some(got) = super::scan_captures_by_literal_windows(&p, input) else {
continue;
};
let spans = crate::engine::scan(&p, input);
let want = crate::engine::captures(&p, input, &spans);
assert_eq!(got.len(), want.len(), "{src}: a different number of matches");
for (g, w) in got.iter().zip(&want) {
assert_eq!((g.start, g.end), (w.start, w.end), "{src}: a different span");
assert_eq!(g.captures(), w.captures(), "{src}: different registers at {}", g.start);
}
}
}
#[test]
fn a_window_at_each_span_binds_what_the_whole_input_binds() {
let mut plain = String::new();
for i in 0..400u32 {
plain.push_str(&format!("let value_{i} = {} ; call_{i}(a, b) ;\n", i * 37));
}
let unclosed = "let a = 1 ; let b = \"never closed ; let c = 3 ;\n".to_string();
for (src, text) in [
("\"let\" \\W:v \"=\"", &plain),
("\"let\" \\W:v \"=\" \\N:n", &plain),
("\\W:name \"=\"", &plain),
("\"let\" \\W:v \"=\"", &unclosed),
("\\W:a \\W:b", &plain),
] {
let p = crate::parser::parse(src).expect("parses");
let input = text.as_bytes();
let all = crate::engine::scan(&p, input);
let Some(got) = super::captures_by_windows(&p, input, &all) else {
continue;
};
let want = crate::nfa::captures_over_parts(&p, input, &all)
.expect("the single-pass engine takes these");
assert_eq!(got.len(), want.len(), "{src}: a different number of matches");
for (g, w) in got.iter().zip(&want) {
assert_eq!((g.start, g.end), (w.start, w.end), "{src}: a different span");
assert_eq!(g.captures(), w.captures(), "{src}: different registers at {}", g.start);
}
}
}
#[test]
fn a_binding_nothing_reads_back_changes_no_span() {
let mut text = String::new();
for i in 0..400u32 {
text.push_str(&format!("let value_{i} = {} ; call_{i}(a, b) ;\n", i * 37));
}
let input = text.as_bytes();
for (bound, bare) in [
("\\W:name \"=\"", "\\W \"=\""),
("\"let\" \\W:v \"=\"", "\"let\" \\W \"=\""),
("\\W:a \\W:b", "\\W \\W"),
("(\\W:x | \\N:y) \"=\"", "(\\W | \\N) \"=\""),
("\\N:n", "\\N"),
] {
let bp = crate::parser::parse(bound).expect("parses");
let rp = crate::parser::parse(bare).expect("parses");
assert_eq!(bp.without_bindings().as_ref(), Some(&rp), "{bound} strips to {bare}");
assert_eq!(
spans(&crate::engine::scan(&bp, input)),
spans(&crate::engine::scan(&rp, input)),
"{bound} and {bare} match the same spans"
);
}
for src in ["\\W:x \"=\" =x", "\\W:x [\\N =x]", "\\W:x ~(=x)"] {
let p = crate::parser::parse(src).expect("parses");
assert!(p.without_bindings().is_none(), "{src} reads a register back");
}
assert!(crate::parser::parse("\\W \"=\"").expect("parses").without_bindings().is_none());
}
#[test]
fn it_refuses_what_a_window_cannot_hold() {
for src in [
"\"let\" \\W*",
"\"let\" ~(\\N)",
"^ \"let\" \\W",
"\"let\" ~\"zzz\"",
"\"let\" \\W:x =x",
"\\B(\"let\")",
"\\W \"=\"",
"\"let\" \\K \\W",
"(?orbit:case \"let\") \\W",
] {
let p = crate::parser::parse(src).expect("parses");
assert!(
scan_by_literal_windows(&p, b"let a = 1 ;").is_none(),
"{src} must be refused"
);
}
}
}
#[must_use]
pub fn byte_routable_byte_pattern(
pattern: &crate::ast::Pattern,
) -> Option<(&crate::bytepat::BytePat, Vec<u8>)> {
use crate::ast::{Atom, Pattern};
let Pattern::Atom(Atom::BytePattern(bp)) = pattern else {
return None;
};
let prefix = bp.literal_prefix();
let opens = prefix.first().is_some_and(|c| c.is_ascii_alphabetic() || *c == b'_');
opens.then_some((bp, prefix))
}
#[must_use]
pub fn byte_route_any_byte_pattern(
bp: &crate::bytepat::BytePat,
prefix: &[u8],
input: &[u8],
) -> Option<bool> {
Some(byte_route_first_byte_pattern(bp, prefix, input)?.is_some())
}
#[must_use]
pub fn byte_route_first_byte_pattern(
bp: &crate::bytepat::BytePat,
prefix: &[u8],
input: &[u8],
) -> Option<Option<crate::engine::Span>> {
byte_route_first_byte_pattern_reading(bp, prefix, &mut ByteReader::new(input), 0)
}
#[must_use]
pub(crate) fn byte_route_first_byte_pattern_reading(
bp: &crate::bytepat::BytePat,
prefix: &[u8],
reader: &mut ByteReader<'_>,
from: usize,
) -> Option<Option<crate::engine::Span>> {
let input = reader.input;
if reader.unsettled() {
return None;
}
let mut from = from.min(input.len());
while let Some(rel) = crate::byte_simd::find(&input[from..], prefix) {
let s = from + rel;
from = s + 1;
if s > 0 && (input[s - 1].is_ascii_alphabetic() || input[s - 1] == b'_') {
continue;
}
let end = match reader.probe_starting_at(s) {
Probe::Settled(Read::TokenEndingAt(_, e)) => e,
Probe::Settled(Read::TokenStartingAt(..) | Read::TokenAt(..) | Read::NoToken) => {
continue;
}
Probe::Settled(Read::Unsettled) => return None,
Probe::Lex => match reader.lex_starting_at(s) {
Read::TokenEndingAt(_, e) => e,
Read::TokenStartingAt(..) | Read::TokenAt(..) | Read::NoToken => continue,
Read::Unsettled => return None,
},
};
if bp.matches_whole(&input[s..end]) {
return Some(Some(crate::engine::Span { start: s as u32, end: end as u32 }));
}
}
Some(None)
}
#[must_use]
pub fn byte_route_byte_pattern(
bp: &crate::bytepat::BytePat,
prefix: &[u8],
input: &[u8],
) -> Option<Vec<crate::engine::Span>> {
if input.len() >= CUT_ROUTE_THRESHOLD {
crate::trace::rung("byte route", "byte pattern, cut across the cores", input.len());
return cut_across_cores(input, |chunk| byte_route_byte_pattern_one_pass(bp, prefix, chunk));
}
crate::trace::rung("byte route", "byte pattern, one pass", input.len());
byte_route_byte_pattern_one_pass(bp, prefix, input)
}
#[must_use]
pub fn byte_route_byte_pattern_one_pass(
bp: &crate::bytepat::BytePat,
prefix: &[u8],
input: &[u8],
) -> Option<Vec<crate::engine::Span>> {
let mut reader = ByteReader::new(input);
if reader.unsettled() {
return None;
}
let machine = bp.automaton();
let whole = |t: &[u8]| machine.as_ref().map_or_else(|| bp.matches_whole(t), |m| m.matches_whole(t));
let mut out: Vec<crate::engine::Span> = Vec::new();
let mut deferred: Vec<usize> = Vec::new();
for s in crate::byte_simd::occurrences_unsplit(input, prefix) {
if s > 0 && (input[s - 1].is_ascii_alphabetic() || input[s - 1] == b'_') {
continue;
}
match reader.probe_starting_at(s) {
Probe::Settled(Read::TokenEndingAt(_, e)) => {
if whole(&input[s..e]) {
out.push(crate::engine::Span { start: s as u32, end: e as u32 });
}
}
Probe::Settled(Read::TokenStartingAt(..) | Read::TokenAt(..) | Read::NoToken) => {}
Probe::Settled(Read::Unsettled) => return None,
Probe::Lex => {
deferred.push(out.len());
out.push(crate::engine::Span { start: s as u32, end: s as u32 });
}
}
}
if !deferred.is_empty() {
let mut dropped = vec![false; out.len()];
for &i in &deferred {
let s = out[i].start as usize;
dropped[i] = match reader.lex_starting_at(s) {
Read::TokenEndingAt(_, e) => {
out[i].end = e as u32;
!whole(&input[s..e])
}
Read::TokenStartingAt(..) | Read::TokenAt(..) | Read::NoToken => true,
Read::Unsettled => return None,
};
}
drop_marked(&mut out, &dropped);
}
Some(out)
}
#[must_use]
pub fn byte_routable_word_then_punct(pattern: &crate::ast::Pattern) -> Option<u8> {
use crate::ast::{Atom, Pattern};
use crate::orbit::OrbitGroup;
let Pattern::Concat(v) = pattern else {
return None;
};
let [Pattern::Atom(Atom::Kind(crate::token::TokenKind::Word)), Pattern::Atom(Atom::Literal(lit, OrbitGroup::Identity))] =
v.as_slice()
else {
return None;
};
let &[c] = lit.as_bytes() else {
return None;
};
plain_punct(c).then_some(c)
}
#[must_use]
pub fn byte_route_any_word_then_punct(punct: u8, input: &[u8]) -> Option<bool> {
Some(byte_route_first_word_then_punct(punct, input)?.is_some())
}
#[must_use]
pub fn byte_route_first_word_then_punct(
punct: u8,
input: &[u8],
) -> Option<Option<crate::engine::Span>> {
byte_route_first_word_then_punct_reading(punct, &mut ByteReader::new(input), 0)
}
#[must_use]
pub(crate) fn byte_route_first_word_then_punct_reading(
punct: u8,
reader: &mut ByteReader<'_>,
from: usize,
) -> Option<Option<crate::engine::Span>> {
use crate::token::TokenKind;
let input = reader.input;
if reader.unsettled() {
return None;
}
let anchor = from.min(input.len());
let mut from = anchor;
while let Some(rel) = crate::byte_simd::find(&input[from..], &[punct]) {
let q = from + rel;
from = q + 1;
let punct_lex = match reader.probe_punct_at(q) {
Probe::Settled(Read::TokenAt(..)) => false,
Probe::Settled(
Read::TokenStartingAt(..) | Read::TokenEndingAt(..) | Read::NoToken,
) => continue,
Probe::Settled(Read::Unsettled) => return None,
Probe::Lex => true,
};
let Some(p) = input[..q].iter().rposition(|c| !c.is_ascii_whitespace()) else {
continue;
};
if input[p] >= 0x80 {
return None;
}
if !word_byte(input[p]) {
continue;
}
let e = p + 1;
let mut word_start = match reader.probe_ending_at(e) {
Probe::Settled(Read::TokenStartingAt(TokenKind::Word, ws)) => Some(ws),
Probe::Settled(
Read::TokenStartingAt(..)
| Read::TokenEndingAt(..)
| Read::TokenAt(..)
| Read::NoToken,
) => continue,
Probe::Settled(Read::Unsettled) => return None,
Probe::Lex => None,
};
if punct_lex {
match reader.lex_punct_at(q) {
Read::TokenAt(..) => {}
Read::TokenStartingAt(..) | Read::TokenEndingAt(..) | Read::NoToken => continue,
Read::Unsettled => return None,
}
}
if word_start.is_none() {
match reader.lex_ending_at(e) {
Read::TokenStartingAt(TokenKind::Word, ws) => word_start = Some(ws),
Read::TokenStartingAt(..)
| Read::TokenEndingAt(..)
| Read::TokenAt(..)
| Read::NoToken => continue,
Read::Unsettled => return None,
}
}
let Some(ws) = word_start else { continue };
if ws < anchor {
continue;
}
return Some(Some(crate::engine::Span { start: ws as u32, end: (q + 1) as u32 }));
}
Some(None)
}
#[must_use]
pub fn byte_route_word_then_punct(punct: u8, input: &[u8]) -> Option<Vec<crate::engine::Span>> {
use crate::token::TokenKind;
struct Deferred {
at: usize,
q: usize,
e: usize,
punct: bool,
word: bool,
}
let mut reader = ByteReader::new(input);
if reader.unsettled() {
return None;
}
let mut out: Vec<crate::engine::Span> = Vec::new();
let mut deferred: Vec<Deferred> = Vec::new();
for q in crate::byte_simd::occurrences_unsplit(input, &[punct]) {
let punct_lex = match reader.probe_punct_at(q) {
Probe::Settled(Read::TokenAt(..)) => false,
Probe::Settled(
Read::TokenStartingAt(..) | Read::TokenEndingAt(..) | Read::NoToken,
) => continue,
Probe::Settled(Read::Unsettled) => return None,
Probe::Lex => true,
};
let Some(p) = input[..q].iter().rposition(|c| !c.is_ascii_whitespace()) else {
continue;
};
if input[p] >= 0x80 {
return None;
}
if !word_byte(input[p]) {
continue;
}
let e = p + 1;
let (start, word_lex) = match reader.probe_ending_at(e) {
Probe::Settled(Read::TokenStartingAt(TokenKind::Word, start)) => (start, false),
Probe::Settled(
Read::TokenStartingAt(..)
| Read::TokenEndingAt(..)
| Read::TokenAt(..)
| Read::NoToken,
) => continue,
Probe::Settled(Read::Unsettled) => return None,
Probe::Lex => (0, true),
};
if punct_lex || word_lex {
deferred.push(Deferred { at: out.len(), q, e, punct: punct_lex, word: word_lex });
}
out.push(crate::engine::Span { start: start as u32, end: (q + 1) as u32 });
}
if !deferred.is_empty() {
let mut dropped = vec![false; out.len()];
for d in &deferred {
if d.punct {
match reader.lex_punct_at(d.q) {
Read::TokenAt(..) => {}
Read::TokenStartingAt(..) | Read::TokenEndingAt(..) | Read::NoToken => {
dropped[d.at] = true;
continue;
}
Read::Unsettled => return None,
}
}
if d.word {
match reader.lex_ending_at(d.e) {
Read::TokenStartingAt(TokenKind::Word, start) => {
out[d.at].start = start as u32;
}
Read::TokenStartingAt(..)
| Read::TokenEndingAt(..)
| Read::TokenAt(..)
| Read::NoToken => dropped[d.at] = true,
Read::Unsettled => return None,
}
}
}
drop_marked(&mut out, &dropped);
}
Some(out)
}
#[must_use]
pub fn byte_routable_literal_word_punct(pattern: &crate::ast::Pattern) -> Option<(&str, u8)> {
use crate::ast::{Atom, Pattern};
use crate::orbit::OrbitGroup;
let Pattern::Concat(v) = pattern else {
return None;
};
let [head, Pattern::Atom(Atom::Kind(crate::token::TokenKind::Word)), Pattern::Atom(Atom::Literal(p, OrbitGroup::Identity))] =
v.as_slice()
else {
return None;
};
let &[c] = p.as_bytes() else {
return None;
};
if !plain_punct(c) {
return None;
}
let lit = byte_routable_literal(head)?;
Some((lit, c))
}
#[must_use]
pub fn byte_route_literal_word_punct(
lit: &str,
punct: u8,
input: &[u8],
) -> Option<Vec<crate::engine::Span>> {
if input.len() >= CUT_ROUTE_THRESHOLD {
crate::trace::rung("byte route", "literal, word, punctuation, cut across the cores", input.len());
return cut_across_cores_reading_past(input, |tail, owns| {
byte_route_literal_word_punct_owning(lit, punct, tail, owns)
});
}
crate::trace::rung("byte route", "literal, word, punctuation, one pass", input.len());
byte_route_literal_word_punct_one_pass(lit, punct, input)
}
#[must_use]
pub fn byte_route_literal_word_punct_one_pass(
lit: &str,
punct: u8,
input: &[u8],
) -> Option<Vec<crate::engine::Span>> {
byte_route_literal_word_punct_owning(lit, punct, input, input.len())
}
#[must_use]
pub fn byte_route_literal_word_punct_owning(
lit: &str,
punct: u8,
input: &[u8],
owns: usize,
) -> Option<Vec<crate::engine::Span>> {
use crate::token::TokenKind;
let mut reader = ByteReader::new(input);
if reader.unsettled() {
return None;
}
let mut out: Vec<crate::engine::Span> = Vec::new();
let mut from = 0usize;
while from < owns {
let Some(anchor) = byte_route_first_word_literal_reading(&[lit], &mut reader, from)? else {
break;
};
let (s, e) = (anchor.start as usize, anchor.end as usize);
if s >= owns {
break;
}
from = e;
let ws = e + input[e..].iter().take_while(|c| c.is_ascii_whitespace()).count();
if ws >= input.len() {
break;
}
if input[ws] >= 0x80 {
return None;
}
if !word_byte(input[ws]) {
continue;
}
let we = match reader.probe_starting_at(ws) {
Probe::Settled(Read::TokenEndingAt(TokenKind::Word, we)) => we,
Probe::Settled(
Read::TokenEndingAt(..) | Read::TokenStartingAt(..) | Read::TokenAt(..) | Read::NoToken,
) => continue,
Probe::Settled(Read::Unsettled) => return None,
Probe::Lex => match reader.lex_starting_at(ws) {
Read::TokenEndingAt(TokenKind::Word, we) => we,
Read::TokenEndingAt(..) | Read::TokenStartingAt(..) | Read::TokenAt(..) | Read::NoToken => {
continue;
}
Read::Unsettled => return None,
},
};
let q = we + input[we..].iter().take_while(|c| c.is_ascii_whitespace()).count();
if q >= input.len() || input[q] != punct {
continue;
}
match reader.probe_punct_at(q) {
Probe::Settled(Read::TokenAt(..)) => {}
Probe::Settled(Read::TokenStartingAt(..) | Read::TokenEndingAt(..) | Read::NoToken) => {
continue;
}
Probe::Settled(Read::Unsettled) => return None,
Probe::Lex => match reader.lex_punct_at(q) {
Read::TokenAt(..) => {}
Read::TokenStartingAt(..) | Read::TokenEndingAt(..) | Read::NoToken => continue,
Read::Unsettled => return None,
},
}
out.push(crate::engine::Span { start: s as u32, end: (q + 1) as u32 });
from = q + 1;
}
Some(out)
}
#[cfg(test)]
mod literal_word_punct_tests {
use super::*;
fn corpus(statements: usize) -> Vec<u8> {
let mut s = String::new();
for i in 0..statements {
match i % 4 {
0 => s.push_str(&format!("let value_{i} = {} ;\n", i * 37)),
1 => s.push_str(&format!("call_{i}(alpha, beta, {i}) ;\n")),
2 => s.push_str(&format!("key_{i}: item_{i}, item_{}, item_{} ;\n", i + 1, i + 2)),
_ => s.push_str(&format!("if (cond_{i}) {{ do_{i}(x) ; }}\n")),
}
}
s.into_bytes()
}
fn holds_on(input: &[u8], src: &str) {
let p = crate::parser::parse(src).expect("parses");
let (lit, punct) = byte_routable_literal_word_punct(&p).expect("the shape is routable");
let one = byte_route_literal_word_punct_one_pass(lit, punct, input);
let cut = cut_across_cores_reading_past(input, |tail, owns| {
byte_route_literal_word_punct_owning(lit, punct, tail, owns)
});
assert_eq!(cut, one, "{src}: the cut form disagrees with one pass");
let chosen = byte_route_literal_word_punct(lit, punct, input);
assert_eq!(chosen, one, "{src}: the shipped route disagrees with one pass");
if let Some(spans) = one {
let windows = scan_by_literal_windows(&p, input).expect("the windows take this shape");
assert_eq!(spans, windows, "{src}: the byte route disagrees with the windows");
let engine = crate::nfa::scan_nfa(&p, input).expect("the single-pass engine takes this shape");
assert_eq!(spans, engine, "{src}: the byte route disagrees with the engine");
}
}
#[test]
fn matches_the_windows_and_the_engine_on_the_comparison_corpus() {
holds_on(&corpus(8000), "\"let\" \\W \"=\"");
holds_on(&corpus(8000), "\"alpha\" \\W \")\"");
holds_on(&corpus(2000), "\"let\" \\W \"=\"");
}
#[test]
fn the_word_may_be_the_literal_and_the_selection_is_leftmost_non_overlapping() {
let input = b"let let = x ;\nlet a = 1 ;\nlet let let = 2 ;\n";
holds_on(input, "\"let\" \\W \"=\"");
let p = crate::parser::parse("\"let\" \\W \"=\"").expect("parses");
let (lit, punct) = byte_routable_literal_word_punct(&p).expect("routable");
let spans = byte_route_literal_word_punct_one_pass(lit, punct, input).expect("the bytes settle it");
let text: Vec<&str> = spans.iter().map(|s| std::str::from_utf8(&input[s.start as usize..s.end as usize]).unwrap()).collect();
assert_eq!(text, ["let let =", "let a =", "let let ="]);
}
#[test]
fn a_quote_the_bytes_cannot_settle_refuses_the_whole_in_both_forms() {
let mut s = String::new();
for i in 0..6000 {
s.push_str(&format!("let v_{i} = {i} ; see http://x/'\"' here\n"));
}
let input = s.into_bytes();
assert!(input.len() >= CUT_ROUTE_THRESHOLD, "the refusing input must reach the cut form");
let p = crate::parser::parse("\"let\" \\W \"=\"").expect("parses");
let (lit, punct) = byte_routable_literal_word_punct(&p).expect("routable");
assert_eq!(byte_route_literal_word_punct_one_pass(lit, punct, &input), None);
assert_eq!(byte_route_literal_word_punct(lit, punct, &input), None);
assert_eq!(byte_route_word_literals(&[lit], &input), None);
assert!(crate::nfa::scan_nfa(&p, &input).is_some());
}
#[test]
fn a_match_spanning_a_line_is_not_split_by_a_cut() {
let mut s = String::new();
for i in 0..3000 {
s.push_str(&format!("let\nvalue_{i} = {i} ;\nlet\n x_{i}\n = 2 ;\ncall_{i}(a) ;\n"));
}
let input = s.into_bytes();
assert!(input.len() >= CUT_ROUTE_THRESHOLD);
holds_on(&input, "\"let\" \\W \"=\"");
let p = crate::parser::parse("\"let\" \\W \"=\"").expect("parses");
let (lit, punct) = byte_routable_literal_word_punct(&p).expect("routable");
let spans = byte_route_literal_word_punct(lit, punct, &input).expect("settled");
assert_eq!(spans.len(), 6000, "two spanning matches a block, none split");
}
#[test]
fn a_line_anchored_literal_cut_at_lines_rejects_a_second_literal_on_the_line() {
let mut s = String::new();
for i in 0..6000 {
s.push_str(&format!("let let = {i} ;\n let a_{i} = 1 ; let b = 2 ;\n"));
}
let input = s.into_bytes();
assert!(input.len() >= CUT_ROUTE_THRESHOLD);
let one = byte_route_line_anchored_literal_one_pass("let", &input).expect("settled");
let cut = byte_route_line_anchored_literal("let", &input).expect("settled");
assert_eq!(cut, one, "the cut line-anchored route disagrees with one pass");
assert_eq!(one.len(), 12000, "one leading `let` a line, two lines a block");
let p = crate::parser::parse("^ \"let\"").expect("parses");
assert_eq!(one, crate::nfa::scan_nfa(&p, &input).expect("the engine takes it"));
}
#[test]
fn strings_across_every_candidate_boundary_do_not_move_a_cut() {
let mut s = String::new();
for i in 0..3000 {
s.push_str(&format!("let a_{i} = \"open {i}\nlet b = 2 ; still in the string\n\" ; let c_{i} = 3 ;\n"));
}
holds_on(&s.into_bytes(), "\"let\" \\W \"=\"");
}
}
const WINDOW_BYTES_PER_TOKEN: usize = 256;
const WINDOW_WIDENINGS: usize = 3;
const WINDOW_LEX_SHARE: usize = 378;
const WINDOW_COVERAGE_LIMIT: usize = WINDOW_LEX_SHARE / WINDOW_MARGIN;
const WINDOW_COST_IN_INPUT_BYTES: usize = 16_000;
const WINDOW_MARGIN: usize = 2;
#[must_use]
pub fn scan_required_windows(
pattern: &crate::ast::Pattern,
input: &[u8],
) -> Option<Vec<crate::engine::Span>> {
required_window_spans(pattern, input, false, true)
}
#[doc(hidden)]
#[derive(Clone, Copy, Debug, PartialEq, Eq)]
pub enum WindowGate {
ByteCount,
CoverageOnly,
PricedWindow,
PredictedDensity,
Open,
}
const WINDOW_TOKEN_SHARE: usize = WINDOW_LEX_SHARE;
const PREFIX_PROBE_BYTES: usize = 64 * 1024;
#[must_use]
pub fn any_in_prefix(pattern: &crate::ast::Pattern, input: &[u8]) -> Option<bool> {
if input.len() <= PREFIX_PROBE_BYTES {
return None;
}
if pattern.starts_with_resume()
|| pattern.mentions_reset_start()
|| pattern.mentions_stream_end_anchor()
{
return None;
}
let compiled = crate::nfa::compile_pattern(pattern)?;
let quotes = crate::parallel_lex::quoted_spans(input);
let cut = boundary_at_or_after(input, "es, PREFIX_PROBE_BYTES);
if cut == 0 || cut >= input.len() {
return None;
}
let toks = lex_window(input, 0, cut);
let spans = crate::nfa::scan_nfa_over_compiled(&compiled, pattern, input, &toks);
let max_len = crate::nfa::bounded_max_len(pattern).unwrap_or(1).max(1)
+ pattern.widest_forward_window();
let edge = toks.iter().filter(|t| t.is_significant()).nth_back(max_len - 1)?.start();
spans.iter().any(|s| s.end() <= edge).then_some(true)
}
const PREFIX_TRIES: usize = 1;
#[must_use]
pub fn find_by_growing_prefix(
pattern: &crate::ast::Pattern,
input: &[u8],
) -> Option<Option<crate::engine::Span>> {
settle_first_from_a_prefix(pattern, input, |s, _| s)
}
#[doc(hidden)]
#[must_use]
pub fn find_by_growing_prefix_at(
pattern: &crate::ast::Pattern,
input: &[u8],
growth: usize,
cap: usize,
) -> Option<Option<crate::engine::Span>> {
find_by_growing_prefix_lexed(pattern, input, growth, cap, false)
}
#[doc(hidden)]
#[must_use]
pub fn find_by_growing_prefix_lexed(
pattern: &crate::ast::Pattern,
input: &[u8],
growth: usize,
cap: usize,
parallel: bool,
) -> Option<Option<crate::engine::Span>> {
if !settles_from_a_prefix(pattern) {
return None;
}
let compiled = crate::nfa::compile_pattern(pattern)?;
let max_len = crate::nfa::bounded_max_len(pattern).unwrap_or(1).max(1)
+ pattern.widest_forward_window();
let mut answer = None;
over_widening_prefixes_lexed(input, growth, cap, parallel, |toks, whole| {
let spans = crate::nfa::scan_nfa_over_compiled(&compiled, pattern, input, toks);
let hit = if whole {
spans.first().copied()
} else {
settled_clear_of_the_cut(toks, &spans, max_len)
};
match hit {
Some(s) => {
answer = Some(Some(s));
false
}
None => {
if whole {
answer = Some(None);
}
true
}
}
});
answer
}
pub fn settle_first_from_a_prefix<T>(
pattern: &crate::ast::Pattern,
input: &[u8],
mut take: impl FnMut(crate::engine::Span, &[crate::token::Token]) -> T,
) -> Option<Option<T>> {
if !settles_from_a_prefix(pattern) {
return None;
}
let compiled = crate::nfa::compile_pattern(pattern)?;
let max_len = crate::nfa::bounded_max_len(pattern).unwrap_or(1).max(1)
+ pattern.widest_forward_window();
let mut answer = None;
over_widening_prefixes(input, |toks, whole| {
let spans = crate::nfa::scan_nfa_over_compiled(&compiled, pattern, input, toks);
let hit = if whole {
spans.first().copied()
} else {
settled_clear_of_the_cut(toks, &spans, max_len)
};
match hit {
Some(s) => {
answer = Some(Some(take(s, toks)));
false
}
None => {
if whole {
answer = Some(None);
}
true
}
}
});
answer
}
#[must_use]
pub fn find_at_by_growing_prefix(
pattern: &crate::ast::Pattern,
input: &[u8],
at: usize,
) -> Option<Option<crate::engine::Span>> {
if !settles_from_a_prefix(pattern) {
return None;
}
let compiled = crate::nfa::compile_pattern(pattern)?;
let max_len = crate::nfa::bounded_max_len(pattern).unwrap_or(1).max(1)
+ pattern.widest_forward_window();
let mut answer = None;
over_widening_prefixes(input, |toks, whole| {
if !whole && toks.last().is_none_or(|t| t.end() <= at) {
return true;
}
let start = toks.partition_point(|t| t.start() < at);
let spans =
crate::nfa::scan_nfa_over_serial_from_compiled(&compiled, pattern, input, toks, start);
let hit = if whole {
spans.first().copied()
} else {
settled_clear_of_the_cut(toks, &spans, max_len)
};
match hit {
Some(s) => {
answer = Some(Some(s));
false
}
None => {
if whole {
answer = Some(None);
}
true
}
}
});
answer
}
#[must_use]
pub fn shortest_end_by_growing_prefix(
pattern: &crate::ast::Pattern,
input: &[u8],
) -> Option<Option<usize>> {
shortest_end_by_growing_prefix_from(pattern, input, 0)
}
#[must_use]
pub fn shortest_end_by_growing_prefix_from(
pattern: &crate::ast::Pattern,
input: &[u8],
at: usize,
) -> Option<Option<usize>> {
if !settles_from_a_prefix(pattern) {
return None;
}
let compiled = crate::nfa::compile_pattern(pattern)?;
let max_len = crate::nfa::bounded_max_len(pattern).unwrap_or(1).max(1)
+ pattern.widest_forward_window();
let mut answer = None;
over_widening_prefixes(input, |toks, whole| {
if !whole && toks.last().is_none_or(|t| t.end() <= at) {
return true;
}
let start = toks.partition_point(|t| t.start() < at);
let end = crate::nfa::shortest_end_over_compiled(&compiled, pattern, input, toks, start);
let hit = match end {
Some(e) if whole || end_clear_of_the_cut(toks, e, max_len) => Some(e),
_ => None,
};
match hit {
Some(e) => {
answer = Some(Some(e));
false
}
None => {
if whole {
answer = Some(None);
}
true
}
}
});
answer
}
#[must_use]
fn end_clear_of_the_cut(toks: &[crate::token::Token], end: usize, reserve: usize) -> bool {
toks.iter()
.filter(|t| t.is_significant())
.nth_back(reserve.max(1) - 1)
.is_some_and(|edge| end <= edge.start())
}
#[must_use]
pub fn settles_from_a_prefix(pattern: &crate::ast::Pattern) -> bool {
!pattern.starts_with_resume()
&& !pattern.mentions_reset_start()
&& !pattern.mentions_stream_end_anchor()
&& !pattern.depends_on_whole_input()
}
#[must_use]
pub fn settled_clear_of_the_cut(
toks: &[crate::token::Token],
spans: &[crate::engine::Span],
reserve: usize,
) -> Option<crate::engine::Span> {
let edge = toks.iter().filter(|t| t.is_significant()).nth_back(reserve.max(1) - 1)?;
spans.iter().find(|s| s.end() <= edge.start()).copied()
}
pub fn over_widening_prefixes(
input: &[u8],
round: impl FnMut(&[crate::token::Token], bool) -> bool,
) {
over_widening_prefixes_lexed(input, 2, PREFIX_TRIES, true, round);
}
#[doc(hidden)]
pub fn over_widening_prefixes_by(
input: &[u8],
growth: usize,
round: impl FnMut(&[crate::token::Token], bool) -> bool,
) {
over_widening_prefixes_capped(input, growth, usize::MAX, round);
}
#[doc(hidden)]
pub fn over_widening_prefixes_capped(
input: &[u8],
growth: usize,
cap: usize,
round: impl FnMut(&[crate::token::Token], bool) -> bool,
) {
over_widening_prefixes_lexed(input, growth, cap, false, round);
}
#[doc(hidden)]
pub fn over_widening_prefixes_lexed(
input: &[u8],
growth: usize,
cap: usize,
parallel: bool,
mut round: impl FnMut(&[crate::token::Token], bool) -> bool,
) {
let quotes = crate::parallel_lex::quoted_spans(input);
let mut toks: Vec<crate::token::Token> = Vec::new();
let mut lo = 0usize;
let mut want = PREFIX_PROBE_BYTES;
let mut done = 0usize;
loop {
let capped = done >= cap;
let cut = if capped || want >= input.len() {
input.len()
} else {
boundary_at_or_after(input, "es, want)
};
let whole = cut >= input.len() || cut <= lo;
let cut = if whole { input.len() } else { cut };
if parallel {
let mut part = crate::parallel_lex::lex_parallel(&input[lo..cut]);
for t in &mut part {
t.start += lo as u32;
t.end += lo as u32;
}
toks.extend(part);
} else {
toks.extend(lex_window(input, lo, cut));
}
lo = cut;
done += 1;
let widen = round(&toks, whole);
if whole || !widen {
return;
}
want = want.saturating_mul(growth.max(2));
}
}
#[doc(hidden)]
#[must_use]
pub fn required_window_reason(pattern: &crate::ast::Pattern, input: &[u8]) -> String {
let Some(max_len) = crate::nfa::bounded_max_len(pattern) else {
return "unbounded".into();
};
if max_len == 0 {
return "empty match".into();
}
if pattern.starts_with_resume() {
return "resume anchor".into();
}
if pattern.mentions_reset_start() {
return "reset start".into();
}
if pattern.mentions_stream_end_anchor() {
return "stream anchor".into();
}
let mut lits: Vec<Vec<u8>> = Vec::new();
collect_contained_literals(pattern, &mut lits);
if lits.iter().all(Vec::is_empty) {
return "no literal".into();
}
if crate::nfa::compile_pattern(pattern).is_none() {
return "set engine".into();
}
let reach = max_len.saturating_mul(WINDOW_BYTES_PER_TOKEN);
let Some(rough) = windows_under_limit(input, &mut lits, reach, WindowGate::ByteCount) else {
return "gate".into();
};
if rough.is_empty() {
return "taken, no hit".into();
}
let budget = settled_budget(input.len(), WindowGate::ByteCount);
if gather_windows(input, None, &rough, budget).is_none() {
return format!("settled past the budget of {budget} bytes before the strings are read");
}
let quotes = crate::parallel_lex::quoted_spans(input);
let Some(gathered) = gather_windows(input, Some("es), &rough, budget) else {
return format!("settled past the budget of {budget} bytes");
};
match settle_gathered(input, "es, &gathered, max_len, budget, |_, _, _| false) {
Ok(_) => "taken".into(),
Err(Unsettled::Widening(report)) => report.to_string(),
Err(Unsettled::Budget(bytes)) => format!("settling lexed {bytes} bytes, past the budget of {budget}"),
}
}
#[derive(Debug, Clone, Copy)]
pub(crate) struct SettleReport {
span: (usize, usize),
lo: usize,
hi: usize,
before: usize,
after: usize,
enough: usize,
widest: usize,
}
impl std::fmt::Display for SettleReport {
fn fmt(&self, f: &mut std::fmt::Formatter<'_>) -> std::fmt::Result {
write!(
f,
"will not settle: {} before and {} after, wanted {}, in {}..{} widened {} around {}..{}",
self.before,
self.after,
self.enough,
self.lo,
self.hi,
self.widest,
self.span.0,
self.span.1
)
}
}
#[doc(hidden)]
#[must_use]
pub fn scan_required_windows_gated(
pattern: &crate::ast::Pattern,
input: &[u8],
gate: WindowGate,
) -> Option<Vec<crate::engine::Span>> {
required_window_spans_gated(pattern, input, false, gate)
}
#[doc(hidden)]
#[must_use]
pub fn scan_required_windows_ungated(
pattern: &crate::ast::Pattern,
input: &[u8],
) -> Option<Vec<crate::engine::Span>> {
required_window_spans_gated(pattern, input, false, WindowGate::Open)
}
fn token_enders_per_mille(input: &[u8], sample: usize) -> usize {
let head = &input[..sample.min(input.len())];
if head.is_empty() {
return 0;
}
let enders = head.iter().filter(|&&c| !word_byte(c)).count();
enders * 1000 / head.len()
}
#[must_use]
pub fn any_required_window(pattern: &crate::ast::Pattern, input: &[u8]) -> Option<bool> {
required_window_spans_gated(pattern, input, true, WindowGate::ByteCount)
.map(|spans| !spans.is_empty())
}
#[must_use]
pub fn first_required_window(
pattern: &crate::ast::Pattern,
input: &[u8],
) -> Option<Option<crate::engine::Span>> {
required_window_spans_gated(pattern, input, true, WindowGate::ByteCount)
.map(|spans| spans.into_iter().next())
}
#[derive(Debug)]
pub enum WindowRefusal {
NoWindowForm,
Uncompiled,
NoLiteral,
TooDense,
Widening,
}
impl std::fmt::Display for WindowRefusal {
fn fmt(&self, f: &mut std::fmt::Formatter<'_>) -> std::fmt::Result {
match self {
WindowRefusal::NoWindowForm => f.write_str("no window form"),
WindowRefusal::Uncompiled => f.write_str("the pattern does not compile"),
WindowRefusal::NoLiteral => f.write_str("no literal anchors a window"),
WindowRefusal::TooDense => f.write_str("the windows cost more than the whole lex"),
WindowRefusal::Widening => f.write_str("a window would not settle even widened"),
}
}
}
impl std::error::Error for WindowRefusal {}
pub fn shortest_end_in_windows(
pattern: &crate::ast::Pattern,
input: &[u8],
) -> Result<Option<usize>, WindowRefusal> {
let Some(max_len) = crate::nfa::bounded_max_len(pattern) else {
return Err(WindowRefusal::NoWindowForm);
};
if max_len == 0
|| pattern.starts_with_resume()
|| pattern.mentions_reset_start()
|| pattern.mentions_stream_end_anchor()
{
return Err(WindowRefusal::NoWindowForm);
}
if crate::nfa::compile_pattern(pattern).is_none() {
return Err(WindowRefusal::Uncompiled);
}
let mut lits: Vec<Vec<u8>> = Vec::new();
collect_contained_literals(pattern, &mut lits);
if lits.iter().all(|l| l.is_empty()) {
return Err(WindowRefusal::NoLiteral);
}
let reach = max_len.saturating_mul(WINDOW_BYTES_PER_TOKEN);
let Some(rough) = windows_under_limit(input, &mut lits, reach, WindowGate::ByteCount) else {
return Err(WindowRefusal::TooDense);
};
if rough.is_empty() {
return Ok(None);
}
let budget = settled_budget(input.len(), WindowGate::ByteCount);
if gather_windows(input, None, &rough, budget).is_none() {
return Err(WindowRefusal::TooDense);
}
let quotes = crate::parallel_lex::quoted_spans(input);
let Some(gathered) = gather_windows(input, Some("es), &rough, budget) else {
return Err(WindowRefusal::TooDense);
};
let mut best: Option<usize> = None;
let settled = settle_gathered(input, "es, &gathered, max_len, budget, |_, _, toks| {
if let Some(end) = crate::nfa::shortest_end(pattern, input, toks, 0)
&& best.is_none_or(|b| end < b)
{
best = Some(end);
}
false
});
match settled {
Ok(_) => Ok(best),
Err(Unsettled::Widening(report)) => {
debug_assert!(report.widest > 0, "a window was refused unwidened: {report}");
Err(WindowRefusal::Widening)
}
Err(Unsettled::Budget(bytes)) => {
if crate::trace::on() {
crate::trace::rung(
"windows",
&format!("declining: settling lexed {bytes} bytes, past the budget of {budget}"),
input.len(),
);
}
Err(WindowRefusal::TooDense)
}
}
}
pub(crate) enum RegionRefusal {
NoRegionForm,
Widening(SettleReport),
}
impl std::fmt::Display for RegionRefusal {
fn fmt(&self, f: &mut std::fmt::Formatter<'_>) -> std::fmt::Result {
match self {
RegionRefusal::NoRegionForm => f.write_str("no region form"),
RegionRefusal::Widening(report) => report.fmt(f),
}
}
}
pub(crate) fn tokens_around(
pattern: &crate::ast::Pattern,
input: &[u8],
span: crate::engine::Span,
) -> Result<Vec<crate::token::Token>, RegionRefusal> {
let Some(max_len) = crate::nfa::bounded_max_len(pattern) else {
return Err(RegionRefusal::NoRegionForm);
};
if max_len == 0
|| pattern.starts_with_resume()
|| pattern.mentions_reset_start()
|| pattern.mentions_stream_end_anchor()
{
return Err(RegionRefusal::NoRegionForm);
}
let mut scan = crate::parallel_lex::QuoteScan::new(input);
match settle_window(
input,
&mut Quoting::AsProbed(&mut scan),
span.start(),
span.end(),
max_len,
) {
Ok((_, _, toks)) => Ok(toks),
Err(report) => Err(RegionRefusal::Widening(report)),
}
}
fn required_window_spans(
pattern: &crate::ast::Pattern,
input: &[u8],
first_only: bool,
gated: bool,
) -> Option<Vec<crate::engine::Span>> {
let gate = if gated { WindowGate::ByteCount } else { WindowGate::Open };
required_window_spans_gated(pattern, input, first_only, gate)
}
fn required_window_spans_gated(
pattern: &crate::ast::Pattern,
input: &[u8],
first_only: bool,
gate: WindowGate,
) -> Option<Vec<crate::engine::Span>> {
let max_len = crate::nfa::bounded_max_len(pattern)?;
if max_len == 0
|| pattern.starts_with_resume()
|| pattern.mentions_reset_start()
|| pattern.mentions_stream_end_anchor()
{
return None;
}
let mut lits: Vec<Vec<u8>> = Vec::new();
collect_contained_literals(pattern, &mut lits);
if lits.iter().all(Vec::is_empty) {
return None;
}
let compiled = crate::nfa::compile_pattern(pattern)?;
let reach = max_len.saturating_mul(WINDOW_BYTES_PER_TOKEN);
let rough = windows_under_limit(input, &mut lits, reach, gate)?;
if rough.is_empty() {
return Some(Vec::new());
}
if crate::trace::on() {
let covered: usize = rough.iter().map(|&(x, y)| y - x).sum();
crate::trace::rung(
"windows",
&format!(
"taking {} window(s) covering {covered} bytes, {} per mille of the input",
rough.len(),
covered.saturating_mul(1000) / input.len().max(1)
),
input.len(),
);
}
let budget = settled_budget(input.len(), gate);
if gate != WindowGate::Open && gather_windows(input, None, &rough, budget).is_none() {
if crate::trace::on() {
crate::trace::rung(
"windows",
&format!("declining: the windows settle past the budget of {budget} bytes before the strings are read"),
input.len(),
);
}
return None;
}
let quotes = crate::parallel_lex::quoted_spans(input);
if gate == WindowGate::PricedWindow {
let &(a, b) = rough.first().expect("the windows are not empty here");
let (lo, hi, toks) =
match settle_window(input, &mut Quoting::Scanned("es), a, b, max_len) {
Ok(settled) => settled,
Err(report) => {
debug_assert!(report.widest > 0, "a window was refused unwidened: {report}");
return None;
}
};
let seen = toks.iter().filter(|t| t.is_significant()).count();
let covered: usize = rough.iter().map(|&(x, y)| y - x).sum();
let tokens_in = |bytes: usize| bytes.saturating_mul(seen).checked_div(hi - lo);
if let (Some(in_windows), Some(in_input)) = (tokens_in(covered), tokens_in(input.len()))
&& (in_input == 0 || in_windows.saturating_mul(1000) / in_input > WINDOW_TOKEN_SHARE)
{
return None;
}
}
let Some(gathered) = gather_windows(input, Some("es), &rough, budget) else {
if crate::trace::on() {
crate::trace::rung(
"windows",
&format!("declining: the windows settle past the budget of {budget} bytes"),
input.len(),
);
}
return None;
};
if crate::trace::on() {
let spans: usize = gathered.iter().map(|g| g.hi - g.lo).sum();
crate::trace::rung(
"windows",
&format!(
"gathered into {} span(s) covering {spans} bytes, {} per mille of the input",
gathered.len(),
spans.saturating_mul(1000) / input.len().max(1)
),
input.len(),
);
}
let mut out: Vec<crate::engine::Span> = Vec::new();
let settled = settle_gathered(input, "es, &gathered, max_len, budget, |lo, hi, toks| {
if crate::trace::on() {
crate::trace::rung(
"windows",
&format!("span {lo}..{hi} lexed to {} tokens", toks.len()),
input.len(),
);
}
let spans = crate::nfa::scan_nfa_over_compiled(&compiled, pattern, input, toks);
if hi == input.len() {
out.extend(spans);
} else {
let edge = match toks.iter().filter(|t| t.is_significant()).nth_back(max_len - 1) {
Some(t) => t.start(),
None => lo,
};
out.extend(spans.into_iter().filter(|s| s.end() <= edge));
}
first_only && !out.is_empty()
});
match settled {
Ok(s) => {
if crate::trace::on() {
crate::trace::rung(
"windows",
&format!(
"settled {} span(s), lexing {} bytes, {} per mille of the input, the widest {}",
s.spans,
s.bytes,
s.bytes.saturating_mul(1000) / input.len().max(1),
s.widest
),
input.len(),
);
}
}
Err(Unsettled::Widening(report)) => {
debug_assert!(report.widest > 0, "a window was refused unwidened: {report}");
return None;
}
Err(Unsettled::Budget(bytes)) => {
if crate::trace::on() {
crate::trace::rung(
"windows",
&format!("declining: settling lexed {bytes} bytes, past the budget of {budget}"),
input.len(),
);
}
return None;
}
}
out.sort_by_key(crate::engine::Span::start);
out.dedup();
Some(out)
}
fn windows_under_limit(
input: &[u8],
lits: &mut [Vec<u8>],
reach: usize,
gate: WindowGate,
) -> Option<Vec<(usize, usize)>> {
lits.sort_by_key(|l| std::cmp::Reverse(l.len()));
lits.iter()
.filter(|l| !l.is_empty())
.find_map(|lit| windows_of_literal(input, lit, reach, gate))
}
fn windows_of_literal(
input: &[u8],
lit: &[u8],
reach: usize,
gate: WindowGate,
) -> Option<Vec<(usize, usize)>> {
let (most, share) = match gate {
WindowGate::ByteCount => (
input.len() / (WINDOW_COST_IN_INPUT_BYTES * WINDOW_MARGIN),
WINDOW_COVERAGE_LIMIT,
),
WindowGate::CoverageOnly | WindowGate::PricedWindow => {
(usize::MAX, WINDOW_COVERAGE_LIMIT)
}
WindowGate::PredictedDensity => {
let enders = token_enders_per_mille(input, 1 << 16).max(1);
(usize::MAX, (WINDOW_COVERAGE_LIMIT * 250 / enders).min(1000))
}
WindowGate::Open => (usize::MAX, usize::MAX),
};
let mut out: Vec<(usize, usize)> = Vec::new();
let mut covered = 0usize;
let mut from = 0usize;
while let Some(rel) = crate::byte_simd::find(&input[from..], lit) {
let p = from + rel;
from = p + 1;
let (a, b) = (p.saturating_sub(reach), (p + reach).min(input.len()));
match out.last_mut() {
Some(last) if a <= last.1 => {
if b > last.1 {
covered += b - last.1;
last.1 = b;
}
}
_ => {
covered += b - a;
out.push((a, b));
}
}
if out.len() > most || covered * 1000 / input.len() > share {
return None;
}
}
Some(out)
}
fn settle_window(
input: &[u8],
quoting: &mut Quoting<'_, '_>,
a: usize,
b: usize,
max_len: usize,
) -> Result<(usize, usize, Vec<crate::token::Token>), SettleReport> {
let enough = 2 * max_len;
let mut out = 0usize;
let mut last = SettleReport {
span: (a, b),
lo: a,
hi: b,
before: 0,
after: 0,
enough,
widest: 0,
};
for _ in 0..WINDOW_WIDENINGS {
let (lo, hi) = match quoting {
Quoting::Scanned(quotes) => (
boundary_at_or_before(input, quotes, a.saturating_sub(out)),
boundary_at_or_after(input, quotes, (b + out).min(input.len())),
),
Quoting::AsProbed(scan) => {
scan.ensure(a, &mut |_| Some(true));
let lo = boundary_at_or_before(input, scan.spans(), a.saturating_sub(out));
let hi = boundary_at_or_after_scanned(input, scan, (b + out).min(input.len()));
(lo, hi)
}
};
let toks = lex_window(input, lo, hi);
let before = toks.iter().filter(|t| t.is_significant() && t.end() <= a).count();
let after = toks.iter().filter(|t| t.is_significant() && t.start() >= b).count();
if (before >= enough || lo == 0) && (after >= enough || hi == input.len()) {
return Ok((lo, hi, toks));
}
last = SettleReport { span: (a, b), lo, hi, before, after, enough, widest: out };
out = if out == 0 { max_len * WINDOW_BYTES_PER_TOKEN } else { out.saturating_mul(2) };
}
Err(last)
}
fn settled_budget(input_len: usize, gate: WindowGate) -> usize {
match gate {
WindowGate::Open => usize::MAX,
WindowGate::ByteCount
| WindowGate::CoverageOnly
| WindowGate::PricedWindow
| WindowGate::PredictedDensity => input_len.saturating_mul(WINDOW_COVERAGE_LIMIT) / 1000,
}
}
#[derive(Clone, Copy, Debug, PartialEq, Eq)]
struct Gathered {
lo: usize,
hi: usize,
a: usize,
b: usize,
}
fn gather_windows(
input: &[u8],
quotes: Option<&[(usize, usize)]>,
rough: &[(usize, usize)],
budget: usize,
) -> Option<Vec<Gathered>> {
let mut out: Vec<Gathered> = Vec::new();
let mut covered = 0usize;
for &(a, b) in rough {
let left = budget - covered;
let floor = match out.last() {
Some(last) => last.hi,
None => 0,
};
let reach = a.saturating_sub(left).max(floor);
if let Some(lo) = cut_back(input, quotes, a, reach) {
let hi = cut_forward(input, quotes, b, lo.saturating_add(left))?;
covered += hi - lo;
out.push(Gathered { lo, hi, a, b });
continue;
}
if reach > floor {
return None;
}
match out.last_mut() {
Some(last) => {
if b > last.hi {
let hi = cut_forward(input, quotes, b, last.hi.saturating_add(left))?;
covered += hi - last.hi;
last.hi = hi;
}
last.b = b;
}
None => {
let hi = cut_forward(input, quotes, b, left)?;
covered += hi;
out.push(Gathered { lo: 0, hi, a, b });
}
}
}
Some(out)
}
#[derive(Clone, Copy, Debug, Default)]
struct SettledSpans {
spans: usize,
bytes: usize,
widest: usize,
lexed: usize,
}
impl SettledSpans {
fn add(&mut self, lo: usize, hi: usize) {
self.spans += 1;
self.bytes += hi - lo;
self.widest = self.widest.max(hi - lo);
}
}
enum Unsettled {
Widening(SettleReport),
Budget(usize),
}
struct OpenSpan {
lo: usize,
hi: usize,
a: usize,
b: usize,
toks: Vec<crate::token::Token>,
}
impl OpenSpan {
fn before(&self) -> usize {
self.toks.iter().filter(|t| t.is_significant() && t.end() <= self.a).count()
}
fn after(&self) -> usize {
self.toks.iter().filter(|t| t.is_significant() && t.start() >= self.b).count()
}
fn report(&self, enough: usize, widest: usize) -> SettleReport {
SettleReport {
span: (self.a, self.b),
lo: self.lo,
hi: self.hi,
before: self.before(),
after: self.after(),
enough,
widest,
}
}
}
struct BudgetLexer<'i> {
input: &'i [u8],
lexed: usize,
budget: usize,
}
impl BudgetLexer<'_> {
fn lex(&mut self, lo: usize, hi: usize) -> Result<Vec<crate::token::Token>, Unsettled> {
self.lexed += hi - lo;
if self.lexed > self.budget {
return Err(Unsettled::Budget(self.lexed));
}
Ok(lex_window(self.input, lo, hi))
}
}
fn widen_forward(
open: &mut OpenSpan,
quotes: &[(usize, usize)],
enough: usize,
max_len: usize,
next: usize,
lexer: &mut BudgetLexer<'_>,
) -> Result<bool, Unsettled> {
let n = lexer.input.len();
let mut out = 0usize;
for _ in 1..WINDOW_WIDENINGS {
if open.hi == n || open.after() >= enough {
return Ok(false);
}
out = if out == 0 { max_len * WINDOW_BYTES_PER_TOKEN } else { out.saturating_mul(2) };
let hi = boundary_at_or_after(lexer.input, quotes, open.b.saturating_add(out).min(n));
if hi >= next {
return Ok(true);
}
if hi > open.hi {
let more = lexer.lex(open.hi, hi)?;
open.toks.extend(more);
open.hi = hi;
}
}
if open.hi == n || open.after() >= enough {
return Ok(false);
}
Err(Unsettled::Widening(open.report(enough, out)))
}
fn widen_back(
open: &mut OpenSpan,
quotes: &[(usize, usize)],
enough: usize,
max_len: usize,
prev: Option<usize>,
lexer: &mut BudgetLexer<'_>,
) -> Result<bool, Unsettled> {
let mut out = 0usize;
for _ in 1..WINDOW_WIDENINGS {
if open.lo == 0 || open.before() >= enough {
return Ok(false);
}
out = if out == 0 { max_len * WINDOW_BYTES_PER_TOKEN } else { out.saturating_mul(2) };
let lo = boundary_at_or_before(lexer.input, quotes, open.a.saturating_sub(out));
if prev.is_some_and(|p| lo <= p) {
return Ok(true);
}
if lo < open.lo {
let mut toks = lexer.lex(lo, open.lo)?;
toks.append(&mut open.toks);
open.toks = toks;
open.lo = lo;
}
}
if open.lo == 0 || open.before() >= enough {
return Ok(false);
}
Err(Unsettled::Widening(open.report(enough, out)))
}
fn settle_gathered(
input: &[u8],
quotes: &[(usize, usize)],
gathered: &[Gathered],
max_len: usize,
budget: usize,
mut each: impl FnMut(usize, usize, &[crate::token::Token]) -> bool,
) -> Result<SettledSpans, Unsettled> {
let enough = 2 * max_len;
let mut lexer = BudgetLexer { input, lexed: 0, budget };
let mut settled = SettledSpans::default();
let mut open: Option<OpenSpan> = None;
for g in gathered {
let mut next = OpenSpan { lo: g.lo, hi: g.hi, a: g.a, b: g.b, toks: lexer.lex(g.lo, g.hi)? };
let join = match open.as_mut() {
Some(cur) => {
widen_forward(cur, quotes, enough, max_len, next.lo, &mut lexer)?
|| widen_back(&mut next, quotes, enough, max_len, Some(cur.hi), &mut lexer)?
}
None => widen_back(&mut next, quotes, enough, max_len, None, &mut lexer)?,
};
if join {
let cur = open.as_mut().expect("only a span with one before it joins");
let gap = lexer.lex(cur.hi, next.lo)?;
cur.toks.extend(gap);
cur.toks.append(&mut next.toks);
cur.hi = next.hi;
cur.b = next.b;
} else if let Some(done) = open.replace(next) {
settled.add(done.lo, done.hi);
if each(done.lo, done.hi, &done.toks) {
settled.lexed = lexer.lexed;
return Ok(settled);
}
}
}
if let Some(mut last) = open {
let joined = widen_forward(&mut last, quotes, enough, max_len, usize::MAX, &mut lexer)?;
debug_assert!(!joined, "no span follows the last for it to join");
settled.add(last.lo, last.hi);
each(last.lo, last.hi, &last.toks);
}
settled.lexed = lexer.lexed;
Ok(settled)
}
enum Quoting<'q, 'i> {
Scanned(&'q [(usize, usize)]),
AsProbed(&'q mut crate::parallel_lex::QuoteScan<'i>),
}
fn quote_holds(quotes: &[(usize, usize)], p: usize) -> bool {
let k = quotes.partition_point(|&(open, _)| open <= p);
k > 0 && quotes[k - 1].1 >= p
}
fn boundary_at_or_before(input: &[u8], quotes: &[(usize, usize)], at: usize) -> usize {
cut_back(input, Some(quotes), at, 0).unwrap_or(0)
}
fn boundary_at_or_after(input: &[u8], quotes: &[(usize, usize)], at: usize) -> usize {
cut_forward(input, Some(quotes), at, input.len()).unwrap_or(input.len())
}
fn cuts_at(input: &[u8], quotes: Option<&[(usize, usize)]>, i: usize) -> bool {
i > 0
&& i < input.len()
&& input[i - 1] == b'\n'
&& !input[i].is_ascii_whitespace()
&& quotes.is_none_or(|q| !quote_holds(q, i - 1) && !quote_holds(q, i))
}
fn cut_back(input: &[u8], quotes: Option<&[(usize, usize)]>, at: usize, floor: usize) -> Option<usize> {
let mut i = at.min(input.len());
while i > floor {
if cuts_at(input, quotes, i) {
return Some(i);
}
i = floor + input[floor..i - 1].iter().rposition(|&c| c == b'\n')? + 1;
}
None
}
fn cut_forward(input: &[u8], quotes: Option<&[(usize, usize)]>, at: usize, limit: usize) -> Option<usize> {
let n = input.len();
let mut i = at.min(n);
while i <= limit {
if i == n || cuts_at(input, quotes, i) {
return Some(i);
}
i = match crate::byte_simd::find(&input[i..], b"\n") {
Some(k) => i + k + 1,
None => n,
};
}
None
}
fn boundary_at_or_after_scanned(
input: &[u8],
scan: &mut crate::parallel_lex::QuoteScan<'_>,
at: usize,
) -> usize {
let n = input.len();
let mut i = at.min(n);
while i < n {
if i > 0 && input[i - 1] == b'\n' && !input[i].is_ascii_whitespace() {
scan.ensure(i, &mut |_| Some(true));
let quotes = scan.spans();
if !quote_holds(quotes, i - 1) && !quote_holds(quotes, i) {
return i;
}
}
i += 1;
}
n
}
#[doc(hidden)]
#[must_use]
pub fn lex_span_as_a_window(input: &[u8], lo: usize, hi: usize) -> Vec<crate::token::Token> {
lex_window(input, lo, hi)
}
fn lex_window(input: &[u8], lo: usize, hi: usize) -> Vec<crate::token::Token> {
let blobs = crate::lexer::blob_runs_within(input, lo, hi);
let local: Vec<(usize, usize)> = blobs.iter().map(|&(a, b)| (a - lo, b - lo)).collect();
let mut toks = crate::lexer::lex_with_blobs(
&input[lo..hi],
&local,
(hi - lo) / crate::lexer::TOKEN_BYTES_ESTIMATE,
);
for t in &mut toks {
t.start += lo as u32;
t.end += lo as u32;
}
toks
}
fn collect_contained_literals(pattern: &crate::ast::Pattern, out: &mut Vec<Vec<u8>>) {
use crate::ast::{Atom, Pattern};
use crate::orbit::OrbitGroup;
match pattern {
Pattern::Atom(Atom::Literal(lit, OrbitGroup::Identity)) if !lit.is_empty() => {
out.push(lit.as_bytes().to_vec());
}
Pattern::Atom(Atom::Kind(kind)) => {
if let Some(lit) = kind_required_literal(*kind) {
out.push(lit.to_vec());
}
}
Pattern::Plus(inner, _)
| Pattern::Bind(_, _, inner)
| Pattern::Balanced(_, inner)
| Pattern::Field(_, inner)
| Pattern::Atomic(inner) => collect_contained_literals(inner, out),
Pattern::Repeat(inner, min, _, _) if *min >= 1 => {
collect_contained_literals(inner, out);
}
Pattern::Concat(v) => {
for p in v {
collect_contained_literals(p, out);
}
}
Pattern::Alt(v, _) => {
let Some((first, rest)) = v.split_first() else { return };
let mut common: Vec<Vec<u8>> = Vec::new();
collect_contained_literals(first, &mut common);
for p in rest {
let mut theirs: Vec<Vec<u8>> = Vec::new();
collect_contained_literals(p, &mut theirs);
common.retain(|l| theirs.contains(l));
}
out.append(&mut common);
}
Pattern::Guard(..)
| Pattern::Assert(..)
| Pattern::Atom(_)
| Pattern::Within(..)
| Pattern::Star(..)
| Pattern::Opt(..)
| Pattern::Repeat(..)
| Pattern::Empty
| Pattern::Anchor(_) => {}
}
}
#[cfg(test)]
mod contained_literal_tests {
use super::collect_contained_literals;
fn contained(src: &str) -> Vec<String> {
let p = crate::parse(src).expect("pattern parses");
let mut out = Vec::new();
collect_contained_literals(&p, &mut out);
out.iter().map(|l| String::from_utf8_lossy(l).into_owned()).collect()
}
#[test]
fn a_repeat_holds_its_body_only_when_it_must_run() {
assert_eq!(contained("\"alpha\"{1,2}"), ["alpha"], "one or two hold one");
assert_eq!(contained("\"alpha\"{2,4}"), ["alpha"], "two or more hold one");
assert_eq!(contained("\"alpha\"{3}"), ["alpha"], "an exact count holds one");
assert!(contained("\"alpha\"{0,2}").is_empty(), "none or two hold none");
assert!(contained("\"alpha\"*").is_empty(), "a star holds none");
assert!(contained("\"alpha\"?").is_empty(), "an option holds none");
assert_eq!(contained("\"alpha\"+"), ["alpha"], "a plus holds one");
}
#[test]
fn a_typed_atom_holds_its_kinds_required_literal() {
assert_eq!(contained("\\E"), ["@"]);
assert_eq!(contained("\\U"), ["://"]);
assert_eq!(contained("\\E \\W"), ["@"], "a sequence holds each atom's");
assert!(contained("(\\E | \\U)").is_empty(), "no literal both branches hold");
assert!(contained("\\E?").is_empty(), "an optional atom holds none");
assert!(contained("\\I").is_empty(), "an address has two forms and requires neither");
}
#[test]
fn every_token_of_a_kind_holds_its_literal_inside_its_span() {
use crate::token::TokenKind;
let samples: [(TokenKind, &str); 10] = [
(TokenKind::Email, "write to ops.team+alerts@example.co.uk today"),
(TokenKind::Url, "see https://example.org/a?b=c#d for more"),
(TokenKind::Jwt, "token eyJhbGciOiJIUzI1NiJ9.eyJzdWIiOiIxIn0.c2lnbmF0dXJl ok"),
(TokenKind::Percent, "load at 97.5% then 12%"),
(TokenKind::HexColor, "color: #fff; border: #a0b1c2;"),
(TokenKind::Version, "upgraded v1.2.3 to 2.0.0-rc.1"),
(TokenKind::Cidr, "allow 10.0.0.0/8 and 192.168.1.0/24"),
(TokenKind::Uuid, "id 123e4567-e89b-12d3-a456-426614174000 done"),
(TokenKind::Money, "paid $1,234.56 and $5"),
(TokenKind::Geo, "at 40.7128, -74.0060 now"),
];
for (kind, text) in samples {
let lit = super::kind_required_literal(kind).expect("each of these kinds names a literal");
let toks: Vec<_> = crate::lexer::lex(text.as_bytes()).into_iter().filter(|t| t.kind == kind).collect();
assert!(!toks.is_empty(), "{kind:?}: the sample {text:?} lexes no token of the kind");
for t in toks {
let span = &text.as_bytes()[t.start as usize..t.end as usize];
assert!(
span.windows(lit.len()).any(|w| w == lit),
"{kind:?} token {:?} does not hold {:?}",
String::from_utf8_lossy(span),
String::from_utf8_lossy(lit)
);
}
}
}
}
fn kind_required_literal(kind: crate::token::TokenKind) -> Option<&'static [u8]> {
use crate::token::TokenKind;
match kind {
TokenKind::Email => Some(b"@"),
TokenKind::Url => Some(b"://"),
TokenKind::Jwt => Some(b"eyJ"),
TokenKind::Percent => Some(b"%"),
TokenKind::HexColor => Some(b"#"),
TokenKind::Version => Some(b"."),
TokenKind::Cidr => Some(b"/"),
TokenKind::Uuid => Some(b"-"),
TokenKind::Money => Some(b"$"),
TokenKind::Geo => Some(b","),
_ => None,
}
}
fn kind_required_run(kind: crate::token::TokenKind) -> Option<(crate::byte_nfa::ByteClass, usize)> {
use crate::byte_nfa::ByteClass;
use crate::token::TokenKind;
let digits = ByteClass::range(b'0', b'9');
match kind {
TokenKind::Base64 => Some((
digits
.union(ByteClass::range(b'a', b'z'))
.union(ByteClass::range(b'A', b'Z'))
.union(ByteClass::just(b'+'))
.union(ByteClass::just(b'/')),
14,
)),
TokenKind::HashDigest => Some((
digits.union(ByteClass::range(b'a', b'f')).union(ByteClass::range(b'A', b'F')),
32,
)),
TokenKind::Mac => Some((
digits
.union(ByteClass::range(b'a', b'f'))
.union(ByteClass::range(b'A', b'F'))
.union(ByteClass::just(b':'))
.union(ByteClass::just(b'-')),
17,
)),
_ => None,
}
}
#[must_use]
pub fn requires_absent_run(pattern: &crate::ast::Pattern, input: &[u8]) -> bool {
use crate::ast::{Atom, Pattern};
let Pattern::Atom(Atom::Kind(kind)) = pattern else {
return false;
};
let Some((class, least)) = kind_required_run(*kind) else {
return false;
};
let Some(tables) = crate::byte_simd::ClassTables::for_class(&class) else {
return false;
};
!tables.has_run_of(input, least)
}
fn collect_required_literals(pattern: &crate::ast::Pattern, out: &mut Vec<Vec<u8>>) {
use crate::ast::{Atom, Pattern};
use crate::orbit::OrbitGroup;
match pattern {
Pattern::Guard(lit, false) => out.push(lit.as_bytes().to_vec()),
Pattern::Atom(Atom::Literal(lit, OrbitGroup::Identity)) if !lit.is_empty() => {
out.push(lit.as_bytes().to_vec());
}
Pattern::Atom(Atom::Kind(kind)) => {
if let Some(lit) = kind_required_literal(*kind) {
out.push(lit.to_vec());
}
}
Pattern::Assert(inner, false, look) => {
if !look.satisfied_by_absence() {
collect_required_literals(inner, out);
}
}
Pattern::Plus(inner, _)
| Pattern::Bind(_, _, inner)
| Pattern::Balanced(_, inner)
| Pattern::Field(_, inner)
| Pattern::Atomic(inner) => collect_required_literals(inner, out),
Pattern::Concat(v) => {
for p in v {
collect_required_literals(p, out);
}
}
Pattern::Alt(v, _) => {
let Some((first, rest)) = v.split_first() else { return };
let mut common: Vec<Vec<u8>> = Vec::new();
collect_required_literals(first, &mut common);
for p in rest {
let mut theirs: Vec<Vec<u8>> = Vec::new();
collect_required_literals(p, &mut theirs);
common.retain(|l| theirs.contains(l));
}
out.append(&mut common);
}
Pattern::Guard(_, true)
| Pattern::Assert(_, true, _)
| Pattern::Atom(_)
| Pattern::Within(..)
| Pattern::Star(..)
| Pattern::Opt(..)
| Pattern::Repeat(..)
| Pattern::Empty
| Pattern::Anchor(_) => {}
}
}
fn collect_guard_literals(pattern: &crate::ast::Pattern, out: &mut Vec<Vec<u8>>) {
use crate::ast::Pattern;
match pattern {
Pattern::Guard(lit, _) => out.push(lit.as_bytes().to_vec()),
Pattern::Assert(p, _, look) => {
if !look.satisfied_by_absence() {
collect_guard_literals(p, out);
}
}
Pattern::Empty | Pattern::Atom(_) | Pattern::Within(..) | Pattern::Anchor(_) => {}
Pattern::Star(p, _) | Pattern::Plus(p, _) | Pattern::Opt(p, _) | Pattern::Bind(_, _, p) => {
collect_guard_literals(p, out);
}
Pattern::Repeat(p, _, _, _)
| Pattern::Balanced(_, p)
| Pattern::Field(_, p)
| Pattern::Atomic(p) => {
collect_guard_literals(p, out);
}
Pattern::Concat(v) | Pattern::Alt(v, _) => {
for p in v {
collect_guard_literals(p, out);
}
}
}
}
#[cfg(test)]
mod tests {
use super::*;
fn engine(p: &crate::ast::Pattern, input: &[u8]) -> Vec<crate::engine::Span> {
crate::nfa::scan_nfa(p, input).expect("the single-pass engine takes these patterns")
}
const CORPUS: &[u8] =
b"the quick brown fox jumps over the lazy dog while 192.168.0.1 logs an ERROR at noon";
#[test]
fn a_run_with_clear_flags_is_a_settled_run() {
for c in 0..=u8::MAX {
if RUN_BYTE[c as usize] & (RUN_UNSETTLED | RUN_JOINS) == 0 {
assert!(settled_byte(c), "{:?} has clear flags and is not settled", c as char);
assert_ne!(c, b':', "a colon must carry RUN_JOINS");
}
}
}
#[test]
fn a_word_byte_carries_no_run_flag() {
for c in 0..=u8::MAX {
if word_byte(c) {
assert_eq!(
RUN_BYTE[c as usize], 0,
"{:?} is a word byte and carries flags {:#04b}",
c as char, RUN_BYTE[c as usize]
);
}
}
}
#[test]
fn a_probed_quote_scan_settles_what_a_whole_scan_settles() {
let mut text = String::new();
for i in 0..40u32 {
match i % 4 {
0 => text.push_str(&format!("let a{i} = \"s{i}\" ;\n")),
1 => text.push_str(&format!("let b{i} = \"open{i}\nstill in it\nclose{i}\" ;\n")),
2 => text.push_str(&format!("let c{i} = {} ;\n", i * 37)),
_ => text.push_str(&format!("let d{i} = don't_{i} ;\n")),
}
}
let input = text.as_bytes();
let n = input.len();
let quotes = crate::parallel_lex::quoted_spans(input);
let read = |r: Result<(usize, usize, Vec<crate::token::Token>), SettleReport>| match r {
Ok((lo, hi, toks)) => Ok((lo, hi, toks.len())),
Err(report) => Err(report.to_string()),
};
for k in 0..=8usize {
for width in [1usize, 9, 40] {
let a = (n * k / 8).min(n.saturating_sub(width));
let b = (a + width).min(n);
for max_len in [1usize, 2, 4] {
let whole =
read(settle_window(input, &mut Quoting::Scanned("es), a, b, max_len));
let mut scan = crate::parallel_lex::QuoteScan::new(input);
let probed = read(settle_window(
input,
&mut Quoting::AsProbed(&mut scan),
a,
b,
max_len,
));
assert_eq!(
whole, probed,
"region {a}..{b} at max_len {max_len} over {n} bytes"
);
}
}
}
}
#[test]
fn a_probed_quote_scan_reads_no_further_than_it_probes() {
let mut text = String::new();
for i in 0..4000u32 {
if i % 3 == 0 {
text.push_str(&format!("let a{i} = \"s{i}\" ;\n"));
} else {
text.push_str(&format!("let c{i} = {} ;\n", i * 37));
}
}
let input = text.as_bytes();
let n = input.len();
assert!(n > 60_000, "the input must be large enough for a bound to show ({n} bytes)");
for (a, b) in [(0usize, 9usize), (200, 240), (1_000, 1_040)] {
for max_len in [1usize, 2, 4] {
let mut scan = crate::parallel_lex::QuoteScan::new(input);
let settled =
settle_window(input, &mut Quoting::AsProbed(&mut scan), a, b, max_len);
assert!(settled.is_ok(), "region {a}..{b} at max_len {max_len} did not settle");
assert!(
scan.searched_to() < b + 4096,
"region {a}..{b} at max_len {max_len} searched to {} of {n}",
scan.searched_to()
);
}
}
}
#[test]
fn the_run_byte_table_is_the_predicates_it_replaces() {
for c in 0..=u8::MAX {
let t = RUN_BYTE[c as usize];
assert_eq!(
t & RUN_UNSETTLED != 0,
!settled_byte(c),
"byte {c:#04x} settles differently"
);
assert_eq!(
t & RUN_JOINS != 0,
c == b'.' || c == b'/' || c == b':',
"byte {c:#04x} joins differently"
);
}
}
#[test]
fn the_registers_read_off_the_bytes_are_the_ones_a_window_resolves() {
let mut text = String::new();
for i in 0..300u32 {
text.push_str(&format!("let value_{i} = {} ; call_{i}(alpha, beta) ;\n", i * 7));
}
let input = text.as_bytes();
for src in ["\\W:name \"=\"", "\"let\" \\W:v \"=\"", "\"let\" \\W \"=\"", "\\W:z \\W:a"] {
let p = crate::parser::parse(src).expect("parses");
let spans = crate::engine::scan(&p, input);
assert!(!spans.is_empty(), "{src} matches the corpus");
let (got, names) = flat_captures_by_byte_bounds(&p, input, &spans)
.unwrap_or_else(|| panic!("the bytes walk {src}"));
let want = captures_by_windows(&p, input, &spans).expect("a window answers these");
assert_eq!(got.len(), want.len(), "{src}");
assert_eq!(names.as_ref(), want[0].names(), "{src} names");
for (g, w) in got.iter().zip(&want) {
assert_eq!((g.span.start(), g.span.end()), (w.start, w.end), "{src} span");
assert_eq!(&g.regs[..names.len()], w.captures(), "{src} registers");
}
}
let bp = crate::parser::parse("`cond_[0-9]+`:c").expect("parses");
let bs = crate::engine::scan(&bp, b"if (cond_12) { }");
assert!(flat_captures_by_byte_bounds(&bp, b"if (cond_12) { }", &bs).is_none());
let accented = "let caf\u{e9}_x = 1 ; let plain = 2 ;\n".as_bytes();
let p = crate::parser::parse("\"let\" \\W:v \"=\"").expect("parses");
let spans = crate::engine::scan(&p, accented);
assert_eq!(spans.len(), 2, "both statements match");
assert!(
flat_captures_by_byte_bounds(&p, accented, &spans).is_none(),
"a word the bytes cannot walk refuses the walk"
);
let want = captures_by_windows(&p, accented, &spans).expect("a window answers it");
assert_eq!(want.len(), 2);
}
#[test]
fn the_word_run_route_reports_the_run_the_tokens_hold() {
use crate::token::TokenKind;
for text in [
"",
"a",
"aa bb",
"aa bb cc dd",
"aa 1 bb cc dd",
"aa, bb cc",
"aa\n\nbb cc\tdd",
"x1 y2 z3 w4",
"let value_0 = 0 ; call_0(alpha, beta) ;",
"aa \"bb cc\" dd ee ff",
"aa bb \"never closed ; cc dd",
"aa bb 192.168.0.1 cc dd",
] {
let input = text.as_bytes();
let toks = crate::lexer::lex(input);
let sig: Vec<&crate::token::Token> =
toks.iter().filter(|t| t.is_significant()).collect();
for times in [2usize, 3] {
for at in 0..=input.len() {
let want = sig
.windows(times)
.find(|w| {
w[0].start() >= at && w.iter().all(|t| t.kind == TokenKind::Word)
})
.map(|w| (w[0].start(), w[times - 1].end()));
let reader = ByteReader::new(input);
let Some(got) = byte_route_first_word_run_reading(&reader, times, at) else {
continue;
};
assert_eq!(
got.map(|s| (s.start(), s.end())),
want,
"{text:?}, a run of {times} at or after {at}"
);
}
}
}
}
fn present_literals() -> Vec<&'static [u8]> {
vec![b"quick", b"brown fox", b"ERROR", b"192.168.0.1", b"lazy dog", b"the"]
}
fn absent_literals() -> Vec<&'static [u8]> {
vec![b"ZZZZ", b"wombat", b"CRITICAL", b"10.0.0.255", b"xylophone", b"qwxz"]
}
#[test]
fn only_a_bare_identity_word_literal_is_byte_routable() {
for src in ["\"alpha\"", "\"_x9\"", "\"Cat\""] {
let p = crate::parse(src).expect("pattern parses");
assert!(byte_routable_literal(&p).is_some(), "{src} is one identifier token");
}
for src in ["\"9lives\"", "\"=\"", "\"a b\"", "\\W", "\"alpha\" \\N", "(\"alpha\" | \"beta\")"]
{
let p = crate::parse(src).expect("pattern parses");
assert!(byte_routable_literal(&p).is_none(), "{src} must not route");
}
}
#[test]
fn an_alternation_of_word_literals_routes_and_a_mixed_one_does_not() {
let routes = crate::parse("(\"alpha\" | \"beta\")").expect("pattern parses");
assert_eq!(byte_routable_literals(&routes), Some(vec!["alpha", "beta"]));
let folded = crate::parse("(\"alpha\" | \"alpha\")").expect("pattern parses");
assert_eq!(byte_routable_literals(&folded), Some(vec!["alpha"]));
for src in ["(\"alpha\" | \\N)", "(\"alpha\" | \"=\")", "(\"alpha\" | \"9x\")"] {
let p = crate::parse(src).expect("pattern parses");
assert_eq!(byte_routable_literals(&p), None, "{src} must not route");
}
}
#[test]
fn a_routed_alternation_answers_what_the_engine_answers() {
let p = crate::parse("(\"alpha\" | \"beta\")").expect("pattern parses");
let inputs: &[&[u8]] = &[
b"alpha beta",
b"beta alpha beta",
b"alphabet beta alpha betas",
b"say \"alpha beta\" then beta",
b"alpha,beta;alpha",
b"nothing here",
];
for input in inputs {
let routed = byte_route_word_literals(&["alpha", "beta"], input);
let engine = engine(&p, input);
assert_eq!(routed, Some(engine), "route and engine differ on {input:?}");
}
}
#[test]
fn the_byte_route_answers_what_the_engine_answers() {
let p = crate::parse("\"alpha\"").expect("pattern parses");
let inputs: &[&[u8]] = &[
b"alpha",
b"say alpha now",
b"alphabet alpha alphas",
b"alpha, alpha; (alpha)",
b"say \"alpha beta\" and alpha",
b"no match here",
b"",
b"ALPHA alpha Alpha",
b"visit http://alpha.com now",
b"mail alpha@example.org today",
b"see alpha.beta.gamma here",
b"alpha:80 and alpha/2",
b"if (alpha==beta) {alpha} else [alpha]; <alpha> !alpha, alpha;",
b"2alpha x2alpha alpha2 _2alpha 42alpha=1 2.5alpha 0xalpha",
b"say \"x y\"alpha and \"z\"alpha too",
b"\"open alpha",
b"say 'alpha beta' and 'x'alpha and alpha",
b"fn f<'alpha>(x: &'alpha str) -> &'alpha str",
b"don'talpha alpha don't",
"\u{e9}alpha alpha\u{e9} alpha".as_bytes(),
b"obj.alpha alpha.len() a.alpha.b x.alpha.y. .alpha alpha. 2.5alpha x.5alpha",
b"eyJhbGciOi.alpha.c v1.2.3 item_1.alpha x1.alpha 1.alpha 1x.alpha 1_.alpha",
b"std::alpha alpha::beta x:alpha alpha:80 ::alpha a:b:alpha 12:30alpha",
b"http://alpha.com/x C:/dir/alpha a::alpha alpha::1",
b"dir/alpha (/usr/alpha) ./alpha a/alpha/b x=/alpha abcdefghij/alpha/ 1.2.3.4/alpha /alpha",
];
for input in inputs {
let routed = byte_route_word_literal("alpha", input);
let engine = engine(&p, input);
assert_eq!(routed, Some(engine), "route and engine differ on {input:?}");
}
}
fn blob_around(mid: &str) -> String {
let mut x: u32 = 0x9e37_79b9;
let mut side = || {
let mut s = String::new();
for _ in 0..80 {
x ^= x << 13;
x ^= x >> 17;
x ^= x << 5;
let c = b'!' + (x >> 25) as u8 % 94;
if !matches!(c, b'"' | b'\'') {
s.push(c as char);
}
}
s
};
format!("{}{mid}{}", side(), side())
}
#[test]
fn a_long_run_is_read_by_its_own_lex_and_a_blob_holds_no_token() {
let p = crate::parse("\"alpha\"").expect("pattern parses");
let pad = ".".repeat(30);
let dotted = format!("data {pad}alpha{pad} end");
assert!(crate::lexer::blob_runs(dotted.as_bytes()).is_empty(), "dots are not a blob");
let blob = format!("data {} end", blob_around(".alpha."));
assert!(!crate::lexer::blob_runs(blob.as_bytes()).is_empty(), "the run must be a blob");
let lettered = format!("{}.alpha.{}", "a".repeat(30), "b".repeat(30));
for input in [dotted, blob, lettered] {
let input = input.as_bytes();
assert_eq!(
byte_route_word_literal("alpha", input),
Some(engine(&p, input)),
"route and engine differ on {input:?}"
);
}
}
#[test]
fn a_quote_inside_a_blob_or_a_char_literal_opens_no_string() {
let p = crate::parse("\"alpha\"").expect("pattern parses");
let blob = format!("x {} alpha", blob_around("\""));
assert!(!crate::lexer::blob_runs(blob.as_bytes()).is_empty(), "the run must be a blob");
let inputs: Vec<Vec<u8>> = vec![
blob.into_bytes(),
b"x = '\"'; alpha".to_vec(),
b"y = '\\\"'; alpha".to_vec(),
b"z = 'a \"b\" c'; alpha".to_vec(),
];
for input in &inputs {
assert_eq!(engine(&p, input).len(), 1, "the engine sees the word on {input:?}");
assert_eq!(byte_route_word_literal("alpha", input), Some(engine(&p, input)), "on {input:?}");
}
assert_eq!(byte_route_word_literal("alpha", b"see http://x/'\"' alpha"), None);
}
#[test]
fn a_digit_before_the_occurrence_is_the_lexers_call() {
let cases: &[(&str, &[u8])] = &[
("ms", b"took 15ms and 3h20m then ms alone" as &[u8]),
("kb", b"2kb of 2 kb"),
("kg", b"5 kg and kg alone and x kg"),
("alpha", b"2alpha 2.5alpha 0xalpha 1_alpha"),
("ms", b"2.5ms 2.ms 2 . ms x.ms x1.ms 1x.ms"),
("v1", b"v1.2.3 v1.x v1 v1.2 a.v1"),
("beef", b"dead::beef x::beef beef::1 beef:cafe::1 (beef) beef:x beef beef:"),
];
for (lit, input) in cases {
let p = crate::parse(&format!("\"{lit}\"")).expect("pattern parses");
assert_eq!(
byte_route_word_literal(lit, input),
Some(engine(&p, input)),
"route and engine differ on {input:?}"
);
}
}
#[test]
fn a_phone_number_reaching_into_the_run_hands_the_input_back() {
let p = crate::parse("\"ms\"").expect("pattern parses");
let input = b"call +1 415 555 2671ms now";
assert_eq!(engine(&p, input).len(), 1, "the engine sees the word after the number");
assert_eq!(byte_route_word_literal("ms", input), None);
let input = b"call x 2671ms now";
assert_eq!(byte_route_word_literal("ms", input), Some(engine(&p, input)));
assert!(engine(&p, input).is_empty(), "a duration is not the word");
}
#[test]
fn a_long_literal_is_a_token_of_whatever_kind_the_lexer_makes() {
let digest = "d41d8cd98f00b204e9800998ecf8427e";
let p = crate::parse(&format!("\"{digest}\"")).expect("pattern parses");
for input in [format!("x {digest} y"), format!("x.{digest}"), format!("{digest}=")] {
let input = input.as_bytes();
assert_eq!(engine(&p, input).len(), 1, "the digest token matches by text on {input:?}");
assert_eq!(byte_route_word_literal(digest, input), Some(engine(&p, input)), "on {input:?}");
}
let p = crate::parse("\"AlphaBetaGamm0\"").expect("pattern parses");
let input = b"AlphaBetaGamm0== and AlphaBetaGamm0 here";
assert_eq!(engine(&p, input).len(), 1, "the padded one is a base64 token");
assert_eq!(byte_route_word_literal("AlphaBetaGamm0", input), Some(engine(&p, input)));
}
#[test]
fn a_word_then_plain_punctuation_is_byte_routable() {
for (src, byte) in [("\\W \"=\"", b'='), ("\\W \"(\"", b'('), ("\\W \";\"", b';')] {
let p = crate::parse(src).expect("pattern parses");
assert_eq!(byte_routable_word_then_punct(&p), Some(byte), "{src}");
}
for src in ["\"=\" \\W", "\\N \"=\"", "\\W \"==\"", "\\W \".\"", "\\W \"=\" \\W", "\\W"] {
let p = crate::parse(src).expect("pattern parses");
assert_eq!(byte_routable_word_then_punct(&p), None, "{src} must not route");
}
}
#[test]
fn the_word_then_punctuation_route_answers_what_the_engine_answers() {
let p = crate::parse("\\W \"=\"").expect("pattern parses");
let inputs: &[&[u8]] = &[
b"a = b == c; x=1; y =2; (z) = 3; \"q\" = 4; 42 = x; 2alpha = 1; 2ms = 5",
b"AlphaBetaGamm0== x = 1",
b"fetch(https://example.com/a?b=1) ; c = 2",
b"x==y ==x x= =y",
b"\"open = 1",
b"= a =\n\tb\t=\r\n",
b"",
b"if (alpha==beta) {alpha} else [alpha]; <alpha> !alpha, alpha;",
];
for input in inputs {
assert_eq!(
byte_route_word_then_punct(b'=', input),
Some(engine(&p, input)),
"route and engine differ on {input:?}"
);
}
}
#[test]
fn the_word_then_punctuation_route_declines_what_the_bytes_cannot_settle() {
let p = crate::parse("\\W \"=\"").expect("pattern parses");
let phone = b"+1 415 555 2671ms = 3";
assert_eq!(engine(&p, phone).len(), 1, "the word after the number then `=`");
assert_eq!(byte_route_word_then_punct(b'=', phone), None);
let accented = "caf\u{e9} = 1".as_bytes();
assert_eq!(engine(&p, accented).len(), 1, "the accented word then `=`");
assert_eq!(byte_route_word_then_punct(b'=', accented), None);
let nbsp = "foo\u{a0}= 1".as_bytes();
assert_eq!(engine(&p, nbsp).len(), 1, "the word, unicode whitespace, then `=`");
assert_eq!(byte_route_word_then_punct(b'=', nbsp), None);
let long = format!("{}=1", "a".repeat(60));
assert_eq!(engine(&p, long.as_bytes()).len(), 1, "the long word then `=`");
assert_eq!(byte_route_word_then_punct(b'=', long.as_bytes()), Some(engine(&p, long.as_bytes())));
}
#[test]
fn a_byte_pattern_with_a_literal_word_prefix_is_byte_routable() {
let p = crate::parse("`cond_[0-9]+`").expect("pattern parses");
let (_, prefix) = byte_routable_byte_pattern(&p).expect("opens with literal bytes");
assert_eq!(prefix, b"cond_");
let p = crate::parse("`x`").expect("pattern parses");
assert!(byte_routable_byte_pattern(&p).is_some());
for src in ["`[0-9]+`", "`=x`", "`cond_[0-9]+` \\N"] {
let p = crate::parse(src).expect("pattern parses");
assert!(byte_routable_byte_pattern(&p).is_none(), "{src} must not route");
}
}
#[test]
fn the_byte_pattern_route_answers_what_the_engine_answers() {
let src = "`cond_[0-9]+`";
let p = crate::parse(src).expect("pattern parses");
let (bp, prefix) = byte_routable_byte_pattern(&p).expect("routable");
let inputs: &[&[u8]] = &[
b"cond_1 cond_22 cond_x xcond_3 2cond_4 cond_5.x cond_6:7 (cond_8) \"cond_9\" cond_",
b"if (cond_10) { do_1(cond_11) ; } cond_cond_12 _cond_13 cond_14_ cond_15",
b"cond_16@example.org http://cond_17.com cond_18/19 cond_20",
b"",
b"cond_",
];
for input in inputs {
let engine = crate::nfa::scan_nfa(&p, input).expect("the single-pass engine takes this pattern");
assert_eq!(byte_route_byte_pattern(bp, &prefix, input), Some(engine), "route and engine differ on {input:?}");
}
}
#[test]
fn the_byte_pattern_route_declines_what_the_bytes_cannot_settle() {
let p = crate::parse("`ms`").expect("pattern parses");
let (bp, prefix) = byte_routable_byte_pattern(&p).expect("routable");
let phone = b"call +1 415 555 2671ms now";
assert_eq!(crate::nfa::scan_nfa(&p, phone).expect("engine").len(), 1);
assert_eq!(byte_route_byte_pattern(bp, &prefix, phone), None);
let long = format!("{}.ms.{}", "a".repeat(30), "b".repeat(30));
let blob = format!("x {} ms", blob_around(".ms."));
for input in [long, blob] {
let input = input.as_bytes();
let engine = crate::nfa::scan_nfa(&p, input).expect("engine");
assert_eq!(byte_route_byte_pattern(bp, &prefix, input), Some(engine), "on {input:?}");
}
}
#[test]
fn the_word_boundary_rule_alone_does_not_decide_a_token() {
let p = crate::parse("\"alpha\"").expect("pattern parses");
assert_eq!(engine(&p, b"say alpha now").len(), 1, "a bare word is its own token");
assert_eq!(
engine(&p, b"say \"alpha beta\" now").len(),
0,
"inside a quoted string there is no word token to match"
);
}
#[test]
fn the_windows_a_required_literal_opens_answer_what_the_whole_scan_answers() {
let mut text = String::new();
text.push_str("alpha = 1 ;\n");
for i in 0..40_000u32 {
text.push_str(&format!("let value_{i} = {} ;\n", i * 7));
if i % 8_000 == 0 {
text.push_str("alpha = 2 ;\nalpha = 3 ;\n");
}
if i % 13_997 == 0 {
text.push_str("key : alpha\n= 4 ;\n");
}
}
text.push_str("alpha = 5 ;\n");
let input = text.as_bytes();
for src in ["\"alpha\" \"=\"", "\"alpha\" \"=\" \\N", "\"alpha\"", "\"alpha\"{1,2}"] {
let p = crate::parse(src).expect("pattern parses");
let want = engine(&p, input);
let got = scan_required_windows(&p, input);
assert_eq!(got.as_ref(), Some(&want), "{src}");
assert_eq!(crate::scan(&p, input), want, "{src} through the scan's own route");
}
let p = crate::parse("\\W \"=\" \\N ~\"alpha\"").expect("pattern parses");
let want = engine(&p, input);
assert_eq!(scan_required_windows(&p, input), None, "a dense guard literal declines");
assert_eq!(crate::scan(&p, input), want, "and the scan answers it anyway");
}
#[test]
fn the_first_window_holding_a_match_holds_the_leftmost_one() {
let mut spread = String::new();
spread.push_str("alpha = 1 ;\n");
for i in 0..40_000u32 {
spread.push_str(&format!("let value_{i} = {} ;\n", i * 7));
if i == 20_000 {
spread.push_str("alpha = 2 ;\n");
}
}
spread.push_str("alpha = 3 ;\n");
let mut never = String::new();
for i in 0..40_000u32 {
never.push_str(&format!("let value_{i} = {} ;\n", i * 7));
if i % 10_000 == 0 {
never.push_str("alpha ;\n");
}
}
let mut blob = String::new();
for i in 0..40_000u32 {
blob.push_str(&format!("let value_{i} = {} ;\n", i * 7));
if i % 2_700 == 0 {
blob.push_str(&format!("{} alpha = {i} ;\n", "n".repeat(700)));
}
}
let mut answered = 0usize;
for (label, text) in [("spread", &spread), ("never", &never), ("blob", &blob)] {
let input = text.as_bytes();
for src in ["\"alpha\" \"=\"", "\"alpha\" \"=\" \\N", "\\W \"alpha\""] {
let p = crate::parse(src).expect("pattern parses");
let Some(got) = first_required_window(&p, input) else {
continue;
};
answered += 1;
let want = engine(&p, input).first().copied();
assert_eq!(got, want, "{label} / {src}: the early exit against the engine");
assert_eq!(
got,
scan_required_windows(&p, input).and_then(|s| s.first().copied()),
"{label} / {src}: the early exit against the full route"
);
}
}
assert!(answered > 0, "no case reached the route, so this test read nothing");
}
fn every_split(input: &[u8], quotes: Option<&[(usize, usize)]>) -> Vec<usize> {
(0..=input.len()).filter(|&i| cuts_at(input, quotes, i)).collect()
}
#[test]
fn the_split_walks_find_the_split_the_byte_walk_finds() {
let mut text = String::new();
for i in 0..400u32 {
match i % 7 {
0 => text.push_str(&format!("let s_{i} = \"open {i} \\\nx = 1 ; still in the string\" ;\n")),
1 => text.push_str(" indented = 1 ;\n"),
2 => text.push_str("\n\n"),
3 => text.push_str(&format!("x_{i} = {i} ; y = 'c' ;\n")),
_ => text.push_str(&format!("let v_{i} = {} ;\n", i * 3)),
}
}
text.push_str("tail with no newline");
let input = text.as_bytes();
let n = input.len();
let quotes = crate::parallel_lex::quoted_spans(input);
for q in [None, Some(quotes.as_slice())] {
let splits = every_split(input, q);
assert!(splits.len() > 100, "the corpus holds {} splits, too few to walk", splits.len());
for at in (0..=n).step_by(7) {
for floor in [0usize, at / 2, at.saturating_sub(40)] {
let want = splits.iter().rev().find(|&&s| s > floor && s <= at).copied();
assert_eq!(cut_back(input, q, at, floor), want, "back from {at} over {floor}");
}
for limit in [n, at + 30, (at + n) / 2] {
let want = (at..=limit.min(n)).find(|&i| i == n || splits.binary_search(&i).is_ok());
assert_eq!(cut_forward(input, q, at, limit), want, "forward from {at} to {limit}");
}
}
}
let bare = every_split(input, None);
let read = every_split(input, Some("es));
assert!(read.iter().all(|s| bare.binary_search(s).is_ok()), "a split read with the strings is one without");
assert!(read.len() < bare.len(), "no string hid a split, so the two readings were not told apart");
}
fn corpus_with_joining_spans() -> Vec<u8> {
let mut text = String::new();
for i in 0..30_000u32 {
text.push_str(&format!("let value_{i} = {} ;\n", i * 7));
if i % 6_000 == 3_000 {
let runs = if i % 12_000 == 3_000 { 4 } else { 5 };
text.push_str("alpha = 1 ;\n");
for k in 0..runs {
text.push_str(&"nmopq"[k..=k].repeat(300));
text.push('\n');
}
text.push_str("alpha = 2 ;\n");
}
}
text.into_bytes()
}
#[test]
fn gathered_spans_are_apart_lexed_once_and_lex_as_the_whole_input_does() {
let input = corpus_with_joining_spans();
let input = input.as_slice();
let p = crate::parse("\"alpha\" \"=\"").expect("pattern parses");
let max_len = crate::nfa::bounded_max_len(&p).expect("two tokens");
let mut lits: Vec<Vec<u8>> = Vec::new();
collect_contained_literals(&p, &mut lits);
let reach = max_len * WINDOW_BYTES_PER_TOKEN;
let rough = windows_under_limit(input, &mut lits, reach, WindowGate::Open).expect("the gate is open");
assert_eq!(rough.len(), 10, "each hit opens a window of its own");
let quotes = crate::parallel_lex::quoted_spans(input);
let gathered = gather_windows(input, Some("es), &rough, usize::MAX).expect("no budget to pass");
for g in &gathered {
assert!(g.lo == 0 || cuts_at(input, Some("es), g.lo), "{g:?} opens off a split");
assert!(g.hi == input.len() || cuts_at(input, Some("es), g.hi), "{g:?} closes off a split");
assert!(g.lo <= g.a && g.b <= g.hi, "{g:?} does not hold its windows");
}
for w in gathered.windows(2) {
assert!(w[0].hi < w[1].lo, "spans touch or overlap: {w:?}");
}
for &(a, b) in &rough {
assert!(gathered.iter().any(|g| g.lo <= a && b <= g.hi), "window {a}..{b} lies in no span");
}
assert_eq!(gathered.len(), 7, "the gather joins the three pairs whose spans meet");
let key = |t: &crate::token::Token| (t.kind, t.start, t.end);
let whole: Vec<_> = crate::parallel_lex::lex_parallel(input).iter().map(key).collect();
let mut handed: Vec<(usize, usize)> = Vec::new();
let settled = settle_gathered(input, "es, &gathered, max_len, usize::MAX, |lo, hi, toks| {
handed.push((lo, hi));
let mine: Vec<_> = toks.iter().map(key).collect();
let theirs: Vec<_> =
whole.iter().filter(|t| t.1 as usize >= lo && t.2 as usize <= hi).copied().collect();
assert_eq!(mine, theirs, "span {lo}..{hi} lexes apart from the whole input");
false
});
let settled = match settled {
Ok(s) => s,
Err(Unsettled::Widening(report)) => panic!("a span would not settle: {report}"),
Err(Unsettled::Budget(bytes)) => panic!("no budget was set and {bytes} bytes passed it"),
};
assert_eq!(handed.len(), 5, "the two pairs a line apart join by widening, the rest stand");
for w in handed.windows(2) {
assert!(w[0].1 < w[1].0, "handed spans touch or overlap: {w:?}");
}
assert_eq!(settled.spans, handed.len());
assert_eq!(settled.bytes, handed.iter().map(|&(lo, hi)| hi - lo).sum::<usize>());
assert_eq!(settled.lexed, settled.bytes, "a byte was lexed twice, or lexed and not handed on");
let want = engine(&p, input);
assert_eq!(want.len(), 10);
assert_eq!(scan_required_windows_ungated(&p, input), Some(want.clone()));
assert_eq!(scan_required_windows(&p, input), Some(want.clone()));
assert_eq!(crate::scan(&p, input), want, "through the scan's own route");
}
#[test]
fn a_gather_reading_no_strings_lies_inside_the_one_that_does() {
let mut text = String::new();
for i in 0..20_000u32 {
text.push_str(&format!("let value_{i} = \"open {i} \\\nx = 1 ; still in the string\" ;\n"));
if i % 3_000 == 1_500 {
text.push_str("alpha = 2 ;\n");
}
}
let input = text.as_bytes();
let p = crate::parse("\"alpha\" \"=\"").expect("pattern parses");
let max_len = crate::nfa::bounded_max_len(&p).expect("two tokens");
let mut lits: Vec<Vec<u8>> = Vec::new();
collect_contained_literals(&p, &mut lits);
let rough = windows_under_limit(input, &mut lits, max_len * WINDOW_BYTES_PER_TOKEN, WindowGate::Open)
.expect("the gate is open");
let quotes = crate::parallel_lex::quoted_spans(input);
let bare = gather_windows(input, None, &rough, usize::MAX).expect("no budget to pass");
let read = gather_windows(input, Some("es), &rough, usize::MAX).expect("no budget to pass");
for g in &bare {
assert!(read.iter().any(|r| r.lo <= g.lo && g.hi <= r.hi), "{g:?} lies in no span read with the strings");
}
let total = |gs: &[Gathered]| gs.iter().map(|g| g.hi - g.lo).sum::<usize>();
assert!(total(&bare) < total(&read), "the strings hid no split, so this read nothing");
for budget in [total(&bare) / 4, total(&bare) - 1, total(&bare), total(&read) - 1, total(&read)] {
if gather_windows(input, None, &rough, budget).is_none() {
assert!(gather_windows(input, Some("es), &rough, budget).is_none(), "budget {budget}");
}
}
assert!(gather_windows(input, None, &rough, total(&bare) - 1).is_none(), "a byte under its total declines");
assert!(gather_windows(input, Some("es), &rough, total(&read)).is_some(), "its total is within budget");
}
fn dense_run(n: usize) -> String {
const ALPHA: &[u8; 64] = b"ABCDEFGHIJKLMNOPQRSTUVWXYZabcdefghijklmnopqrstuvwxyz0123456789+/";
let mut x = 0x2545_f491_4f6c_dd1du64;
(0..n)
.map(|_| {
x = x.wrapping_mul(6_364_136_223_846_793_005).wrapping_add(1_442_695_040_888_963_407);
ALPHA[(x >> 58) as usize] as char
})
.collect()
}
#[test]
fn a_window_holding_a_blob_line_lexes_as_the_whole_input_does() {
let run = dense_run(200);
let mut text = String::new();
for i in 0..40u32 {
text.push_str(&format!("let value_{i} = {} ;\n", i * 7));
}
text.push_str(&format!("let blob = {run} ;\n"));
for i in 0..40u32 {
text.push_str(&format!("see https://example.org/page/{i} for value_{i} ;\n"));
}
let input = text.as_bytes();
let key = |t: &crate::token::Token| (t.kind, t.start, t.end);
let whole: Vec<_> = crate::parallel_lex::lex_parallel(input).iter().map(key).collect();
let window: Vec<_> = lex_window(input, 0, input.len()).iter().map(key).collect();
assert_eq!(window, whole, "the window's lex parts from the whole input's");
assert_eq!(window.iter().filter(|t| t.0 == crate::token::TokenKind::Url).count(), 40);
let at = text.find(&run).expect("the run is in the text");
assert!(
window.iter().any(|t| t.1 as usize == at && t.2 as usize == at + run.len()),
"the blob line's run is one token"
);
let lo = text.find("let value_20").expect("the line is there");
let hi = text.find("see https://example.org/page/20").expect("the line is there");
let inner: Vec<_> = lex_window(input, lo, hi).iter().map(key).collect();
let theirs: Vec<_> = whole.iter().filter(|t| t.1 as usize >= lo && t.2 as usize <= hi).copied().collect();
assert_eq!(inner, theirs, "the inner window's lex parts from the whole input's");
}
#[test]
fn a_typed_atom_scans_as_the_engine_does_where_the_windows_take_it() {
let mut text = String::new();
for i in 0..40_000u32 {
text.push_str(&format!("let value_{i} = {} ;\n", i * 7));
if i % 5_000 == 1_000 {
text.push_str(&format!("mail ops{i}@example.org now\n"));
}
if i % 7_000 == 2_000 {
text.push_str(&format!("see https://example.org/{i} today\n"));
}
if i % 9_000 == 3_000 {
text.push_str(&format!("paid $1,{i:03}.50 here\n"));
}
}
let input = text.as_bytes();
for src in ["\\E", "\\U", "\\$"] {
let p = crate::parse(src).expect("pattern parses");
let want = engine(&p, input);
assert!(!want.is_empty(), "{src} matches nothing, so this reads nothing");
assert!(scan_required_windows(&p, input).is_some(), "{src}: the gate declines, so the ladder change is not exercised");
assert_eq!(crate::scan(&p, input), want, "{src} through the scan's own ladder");
}
}
#[test]
fn the_route_declines_windows_that_settle_past_the_budget() {
let mut text = String::new();
for i in 0..40_000u32 {
text.push_str(&format!(" let value_{i} = {} ;\n", i * 7));
if i % 9_000 == 0 {
text.push_str(" alpha = 2 ;\n");
}
}
let input = text.as_bytes();
let p = crate::parse("\"alpha\" \"=\" \\N").expect("pattern parses");
let want = engine(&p, input);
assert_eq!(want.len(), 5);
assert_eq!(scan_required_windows(&p, input), None, "the settled spans are the input");
let why = required_window_reason(&p, input);
assert!(why.starts_with("settled past the budget"), "the reason is `{why}`");
assert!(matches!(shortest_end_in_windows(&p, input), Err(WindowRefusal::TooDense)));
assert_eq!(crate::scan(&p, input), want, "the scan answers it anyway");
assert_eq!(scan_required_windows_ungated(&p, input), Some(want));
}
#[test]
fn asking_whether_a_kind_matches_agrees_with_the_scan() {
for text in [
"let value_0 = 41 ;\n",
"only_ident_0 and_1 no_number\n",
"1.2.3.4 and 512KB and $5\n",
"\"42 quoted\"\n",
"!@#$%^&*\n",
"",
"7",
"word",
] {
let input = text.as_bytes();
for src in ["\\W", "\\N"] {
let p = crate::parse(src).expect("pattern parses");
let want = !engine(&p, input).is_empty();
assert_eq!(crate::engine::is_match(&p, input), want, "{src} on {text:?}");
}
}
}
#[test]
fn the_kind_routes_answer_an_anchored_ask_as_the_engine_does() {
let text = "let value_0 = 41 ; call_1(alpha, 7) ; x9 y8 = 512KB 3.14% ;\n";
let input = text.as_bytes();
let toks = crate::parallel_lex::lex_parallel(input);
for src in ["\\W", "\\N"] {
let p = crate::parse(src).expect("pattern parses");
let all = crate::nfa::scan_nfa_over_serial(&p, input, &toks)
.expect("the single-pass engine takes a kind atom");
for at in 0..=input.len() {
let want = all.iter().copied().find(|s| s.start() >= at);
assert_eq!(crate::cursor::find_at(&p, input, at), want, "{src} at {at}");
}
}
}
#[test]
fn the_word_route_agrees_with_the_lexer_on_every_typed_near_miss() {
for text in [
"value = 42 ;\n",
"a@b.com sent it\n",
"see http://x.com/p now\n",
"host api.example.com up\n",
"ver v1.2.3 ok\n",
"size 512KB free\n",
"id 550e8400-e29b-41d4-a716-446655440000\n",
"\"quoted word inside\" then tail\n",
"12345 then word\n",
"value_0 = alpha ;\n",
" indented word\n",
"1234567890\n",
"!@#$%^&*()\n",
"word\n",
"3.14% done\n",
] {
let input = text.as_bytes();
let p = crate::parse("\\W").expect("pattern parses");
let want = engine(&p, input).into_iter().next();
assert_eq!(crate::cursor::find(&p, input), want, "{text:?}");
}
}
#[test]
fn the_number_route_agrees_with_the_lexer_on_every_typed_near_miss() {
for text in [
"value = 42 ;\n",
"ip 1.2.3.4 here\n",
"at 12:30:45 today\n",
"ver 1.2.3 ok\n",
"card 4111 1111 1111 1111 done\n",
"size 512KB free\n",
"pct 3.14% done\n",
"cost $5 each\n",
"took 1500ms\n",
"mass 5 kg here\n",
"mass 5kg here\n",
"temp -40\u{b0}C now\n",
"temp 20\u{b0}C now\n",
"clock 3.2 GHz\n",
"share 40 % done\n",
"count 5 items\n",
"range 10-20kg\n",
"three 3 in a row\n",
"uuid 550e8400-e29b-41d4-a716-446655440000\n",
"date 2026-06-16\n",
"mac 01:23:45:67:89:ab\n",
"\"quoted 42 inside\" then 7\n",
"no digits at all here\n",
"7\n",
"a 7\n",
"let value_0 = 41 ;\n",
"let a1b2c3 = 7 ;\n",
"x9 y8 z7 = 5 ;\n",
"only_ident_0 and_1 no_number_here\n",
] {
let input = text.as_bytes();
let p = crate::parse("\\N").expect("pattern parses");
let want = engine(&p, input).into_iter().next();
assert_eq!(crate::cursor::find(&p, input), want, "{text:?}");
}
}
#[test]
fn a_line_anchored_literal_reads_from_the_bytes_as_the_engine_reads_it() {
let mut text = String::new();
text.push_str("let a = 1 ;\n");
for i in 0..2_000u32 {
text.push_str(&format!("let value_{i} = {} ;\n", i * 7));
text.push_str(&format!(" let indented_{i} = {i} ;\n"));
text.push_str(&format!("\tlet tabbed_{i} = {i} ;\n"));
text.push_str(&format!("call_{i}(let_not_a_token, {i}) ;\n"));
text.push_str(&format!("x_{i} = let ;\n"));
}
let input = text.as_bytes();
let p = crate::parse("^ \"let\"").expect("pattern parses");
let want = engine(&p, input);
assert!(!want.is_empty(), "nothing matched, so this test read nothing");
assert_eq!(crate::scan(&p, input), want, "the route against the engine");
assert_eq!(
crate::engine::routed_spans_public(&p, input).as_ref(),
Some(&want),
"the byte route must answer a line-anchored literal"
);
}
#[test]
fn the_windows_soonest_end_is_the_whole_lexs_soonest_end() {
let mut text = String::new();
text.push_str("alpha beta gamma ;\n");
for i in 0..40_000u32 {
text.push_str(&format!("let value_{i} = {} ;\n", i * 7));
if i % 9_000 == 0 {
text.push_str("alpha = 41 ;\nalpha beta ;\n");
}
}
let input = text.as_bytes();
let toks = crate::parallel_lex::lex_parallel(input);
let mut answered = 0usize;
for src in ["\"alpha\" \\W{1,2}", "\"alpha\" \"=\"", "\"alpha\" \"=\" \\N", "\"alpha\" \\W"] {
let p = crate::parse(src).expect("pattern parses");
let want = crate::nfa::shortest_end(&p, input, &toks, 0);
let got = match shortest_end_in_windows(&p, input) {
Ok(end) => end,
Err(why) => {
eprintln!("{src}: the windows declined: {why}");
continue;
}
};
answered += 1;
assert_eq!(got, want, "{src}: the windows against the whole lex");
}
assert!(answered > 0, "no pattern reached the route, so this test read nothing");
}
#[test]
fn one_span_resolves_over_its_region_as_it_does_over_a_whole_lex() {
let mut text = String::new();
for i in 0..40_000u32 {
text.push_str(&format!("let value_{i} = {} ;\n", i * 7));
if i % 9_000 == 0 {
text.push_str("alpha = 41 ;\n");
}
}
let input = text.as_bytes();
for src in ["\\W:name \"=\"", "\"alpha\" \"=\" \\N:num", "\"let\" \\W:v \"=\""] {
let p = crate::parse(src).expect("pattern parses");
let spans = crate::scan(&p, input);
assert!(!spans.is_empty(), "{src} matches nothing, so this reads nothing");
let whole = crate::engine::captures(&p, input, &spans);
assert_eq!(whole.len(), spans.len(), "{src}: one match per span");
for i in [0, spans.len() / 2, spans.len() - 1] {
let one = crate::engine::captures(&p, input, &[spans[i]]);
assert_eq!(one.len(), 1, "{src}: one span must give one match");
assert_eq!(one[0], whole[i], "{src}: span {i} resolved differently alone");
}
}
}
#[test]
fn a_dense_literal_gives_way_to_a_rarer_one_in_the_same_pattern() {
let mut text = String::new();
for i in 0..40_000u32 {
text.push_str(&format!("value = {} ;\n", i * 7));
if i == 20_000 {
text.push_str("value @ 41 ;\n");
}
}
let input = text.as_bytes();
let p = crate::parse("\"value\" \"@\" \\N").expect("pattern parses");
let want = engine(&p, input);
assert_eq!(want.len(), 1, "the corpus holds the match once");
let got = scan_required_windows(&p, input);
assert_eq!(got.as_ref(), Some(&want), "the rarer literal anchors the windows");
assert_eq!(crate::scan(&p, input), want, "and through the scan's own route");
}
#[test]
fn asking_only_whether_a_match_exists_agrees_with_the_scan() {
let mut text = String::new();
text.push_str("alpha = 1 ;\n");
for i in 0..40_000u32 {
text.push_str(&format!("let value_{i} = {} ;\n", i * 7));
if i % 9_000 == 0 {
text.push_str("alpha = 2 ;\n");
}
}
let input = text.as_bytes();
for src in [
"\"alpha\"",
"(\"alpha\" | \"beta\")",
"\"zzzqqq\"",
"\"alpha\" \"=\" \\N",
"\"alpha\"{1,2}",
"\"zzzqqq\" \"=\"",
"\"alpha\" \";\" \\N",
"\"value_1\" \"=\"",
"`value_[0-9]+`",
"`zzz_[0-9]+`",
"\\W \"=\"",
"\\W \";\"",
"\\W \"@\"",
"\\W \"=\" \\N",
"\\N",
"\\W",
"\\N \\N \\N \\N",
"\\W \"~\" \\N",
] {
let p = crate::parse(src).expect("pattern parses");
let want = !crate::scan(&p, input).is_empty();
assert_eq!(crate::engine::is_match(&p, input), want, "{src}");
assert_eq!(crate::nfa::any_nfa(&p, input), Some(want), "{src} through the engine");
}
}
#[test]
fn the_reason_the_route_declines_agrees_with_whether_it_declines() {
let mut text = String::new();
text.push_str("alpha = 1 ;\n");
for i in 0..20_000u32 {
text.push_str(&format!("let value_{i} = {} ;\n", i * 7));
if i % 4_000 == 0 {
text.push_str("alpha = 2 ;\n");
}
}
let input = text.as_bytes();
for src in [
"\"alpha\" \"=\" \\N",
"\"alpha\"",
"\"alpha\"{1,2}",
"\"value_1\" \"=\"",
"\\W \"=\" \\N",
"\\W \"=\" \\N ~\"alpha\"",
"\"alpha\" \\N*",
"\\G \"alpha\"",
"\"alpha\" \\K \"=\"",
"\\A \"alpha\"",
"\"alpha\" \"=\" \\N \";\" \\z",
] {
let p = crate::parse(src).expect("pattern parses");
let why = required_window_reason(&p, input);
let took = scan_required_windows(&p, input).is_some();
assert_eq!(
took,
why.starts_with("taken"),
"{src}: the route {} but the reason is `{why}`",
if took { "answered" } else { "declined" }
);
}
let mut long = String::new();
for i in 0..20_000u32 {
let run: String = (0..200usize)
.map(|j| b"ABCDEFGHIJKLMNOPQRSTUVWXYZabcdefghijklmnopqrstuvwxyz0123456789+/"
[(i as usize * 31 + j * 17) % 64] as char)
.collect();
long.push_str(&format!("blob_{i} = {run} ;\n"));
if i == 10_000 {
long.push_str("rare_value = 4242 ;\n");
}
}
let long = long.as_bytes();
let p = crate::parse("\"rare_value\" \"=\" \\N").expect("pattern parses");
let why = required_window_reason(&p, long);
assert_eq!(
scan_required_windows(&p, long).is_some(),
why.starts_with("taken"),
"long tokens: the reason is `{why}`"
);
}
#[test]
fn a_wider_match_bound_gives_the_route_up_at_the_same_literal_density() {
let mut text = String::new();
for i in 0..40_000u32 {
text.push_str(&format!("let value_{i} = {} ;\n", i * 7));
if i % 7_000 == 0 {
text.push_str("alpha = 2 ;\n");
}
}
let input = text.as_bytes();
let mut answered = Vec::new();
for k in [1usize, 10, 40, 200] {
let p = crate::parse(&format!("\"alpha\" \\W{{{k}}}")).expect("pattern parses");
let got = scan_required_windows(&p, input);
if let Some(spans) = &got {
assert_eq!(spans, &engine(&p, input), "the route answered wrongly at {k}");
}
answered.push(got.is_some());
}
assert_eq!(answered.first(), Some(&true), "the narrowest bound is worth windowing");
assert_eq!(answered.last(), Some(&false), "the widest is not");
assert!(
answered.windows(2).all(|w| w[0] >= w[1]),
"the route took a wider bound after giving up on a narrower one: {answered:?}"
);
}
#[test]
fn the_window_route_declines_what_it_cannot_answer() {
let input = b"alpha = 1 ; beta = 2 ; alpha = 3 ;" as &[u8];
for src in [
"\\W \"=\"",
"\"alpha\" \\N*",
"\\G \"alpha\"",
"\"alpha\" \\K \"=\"",
"\\A \"alpha\"",
"\"alpha\" \"=\" \\N \";\" \\z",
"\\W \\N ~\"alpha\"",
"\\W ~(\"alpha\")",
] {
let p = crate::parse(src).expect("pattern parses");
assert_eq!(scan_required_windows(&p, input), None, "{src} must decline");
}
}
#[test]
fn a_guards_literal_is_required_of_the_input_and_not_of_the_match() {
let guarded = crate::parse("\\W \\N ~\"alpha\"").expect("pattern parses");
let mut required: Vec<Vec<u8>> = Vec::new();
collect_required_literals(&guarded, &mut required);
assert_eq!(required, vec![b"alpha".to_vec()], "the input must hold it");
let mut contained: Vec<Vec<u8>> = Vec::new();
collect_contained_literals(&guarded, &mut contained);
assert!(contained.is_empty(), "no match holds it inside its own span");
let both = crate::parse("\\W \"=\" \\N ~\"alpha\"").expect("pattern parses");
let mut required: Vec<Vec<u8>> = Vec::new();
collect_required_literals(&both, &mut required);
assert_eq!(required, vec![b"=".to_vec(), b"alpha".to_vec()]);
let mut contained: Vec<Vec<u8>> = Vec::new();
collect_contained_literals(&both, &mut contained);
assert_eq!(contained, vec![b"=".to_vec()]);
let plain = crate::parse("\"alpha\" \"=\"").expect("pattern parses");
let mut contained: Vec<Vec<u8>> = Vec::new();
collect_contained_literals(&plain, &mut contained);
assert_eq!(contained, vec![b"alpha".to_vec(), b"=".to_vec()]);
}
#[test]
fn a_window_answers_the_same_at_every_hit_density() {
for (label, text) in [
("one hit", {
let mut s = "x = 1 ;\n".repeat(6000);
s.push_str("alpha = 9 ;\n");
s
}),
("every line", "alpha = 1 ;\n".repeat(3000)),
("every other line", "alpha = 1 ;\nx = 2 ;\n".repeat(1500)),
] {
let input = text.as_bytes();
let p = crate::parse("\"alpha\" \"=\"").expect("pattern parses");
let want = engine(&p, input);
if let Some(got) = scan_required_windows(&p, input) {
assert_eq!(got, want, "{label}");
}
assert_eq!(crate::scan(&p, input), want, "{label} through the scan's own route");
}
}
#[test]
fn a_required_literal_absent_means_no_match_exists() {
let cases: &[(&str, &[u8])] = &[
("\"alpha\"", b"beta gamma delta" as &[u8]),
("\\W ~\"zzz\"", b"one two three"),
("\"alpha\" \\N", b"beta 42"),
];
for (src, input) in cases {
let p = crate::parse(src).expect("pattern parses");
assert!(requires_absent(&p, input), "{src} should read as unmatchable");
assert!(engine(&p, input).is_empty(), "{src} must have no match to lose");
}
}
#[test]
fn a_literal_that_is_not_required_does_not_short_circuit() {
let cases: &[(&str, &[u8])] = &[
("\\W !~\"zzz\"", b"one two three" as &[u8]),
("(\"alpha\" | \"beta\")", b"beta gamma"),
("(\"alpha\" | \\N)", b"beta 42"),
];
for (src, input) in cases {
let p = crate::parse(src).expect("pattern parses");
assert!(!requires_absent(&p, input), "{src} must not short-circuit");
assert!(!engine(&p, input).is_empty(), "{src} has a match the engine must find");
}
}
#[test]
fn a_typed_atom_short_circuits_on_the_marker_its_recognizer_requires() {
let cases: &[(&str, &[u8])] = &[
("\\E", b"no address here, only words and 12 numbers" as &[u8]),
("\\U", b"http and https are named but no scheme separator is"),
("\\E \\W", b"plain words carrying no at sign at all"),
("\\{jwt}", b"a token would open with the base64 of a brace and quote"),
("\\{percent}", b"ninety nine of a hundred, written out"),
("\\{hexcolor}", b"colors named rather than given in hex"),
("\\V", b"deploy build one two three shipped"),
("\\C", b"route 192.168.0.0 added"),
("\\{uuid}", b"id 550e8400e29b41d4a716446655440000 seen"),
("\\$", b"cost 1234.56 today"),
("\\{geo}", b"at 37.7749 and -122.4194"),
];
for (src, input) in cases {
let p = crate::parse(src).expect("pattern parses");
assert!(requires_absent(&p, input), "{src} should read as unmatchable");
assert!(engine(&p, input).is_empty(), "{src} must have no match to lose");
}
}
#[test]
fn a_typed_atom_keeps_an_input_that_holds_its_marker() {
let cases: &[(&str, &[u8])] = &[
("\\E", b"write to bob@example.com today" as &[u8]),
("\\U", b"see http://example.com/p for more"),
("\\{percent}", b"cpu at 97% and climbing"),
("\\{hexcolor}", b"background #ff8800 today"),
("\\V", b"deploy 1.2.3 shipped"),
("\\C", b"route 192.168.0.0/24 added"),
("\\{uuid}", b"id 550e8400-e29b-41d4-a716-446655440000 seen"),
("\\$", b"cost $1,234.56 today"),
("\\{geo}", b"at 37.7749,-122.4194 exactly"),
("(\\E | \"error\")", b"error with no at sign anywhere"),
];
for (src, input) in cases {
let p = crate::parse(src).expect("pattern parses");
assert!(!requires_absent(&p, input), "{src} must not short-circuit");
assert!(!engine(&p, input).is_empty(), "{src} has a match the engine must find");
}
}
#[test]
fn a_kind_with_alternative_forms_contributes_no_required_literal() {
for src in ["\\I", "\\T", "\\A", "\\L", "\\{phone}", "\\W", "\\N"] {
let p = crate::parse(src).expect("pattern parses");
let mut lits: Vec<Vec<u8>> = Vec::new();
collect_required_literals(&p, &mut lits);
assert!(lits.is_empty(), "{src} must contribute no required literal, got {lits:?}");
}
}
#[test]
fn the_run_a_base64_token_needs_is_fourteen_because_its_padding_counts() {
let p = crate::parse("\\{base64}").expect("pattern parses");
let padded: &[u8] = b"blob aB3dEfGhIjKlM1== here";
assert!(
!engine(&p, padded).is_empty(),
"the recognizer takes a fourteen-byte body with its padding"
);
assert!(!requires_absent_run(&p, padded), "so the filter must not refuse it");
let none: &[u8] = b"short words only, and none of them long";
assert!(requires_absent_run(&p, none));
assert!(engine(&p, none).is_empty(), "nothing to lose by refusing it");
}
#[test]
fn the_run_a_hash_digest_needs_is_thirty_two() {
let p = crate::parse("\\D").expect("pattern parses");
let held: &[u8] = b"sum d41d8cd98f00b204e9800998ecf8427e end";
assert!(!engine(&p, held).is_empty(), "an md5 is a digest");
assert!(!requires_absent_run(&p, held));
let short: &[u8] = b"sum d41d8cd98f00b204e9800998ecf842 end";
assert!(requires_absent_run(&p, short));
assert!(engine(&p, short).is_empty());
}
#[test]
fn the_run_a_mac_needs_is_seventeen_because_its_shape_is_fixed() {
let p = crate::parse("\\{mac}").expect("pattern parses");
let colons: &[u8] = b"host 01:23:45:67:89:ab up";
assert!(!engine(&p, colons).is_empty(), "that is a mac");
assert!(!requires_absent_run(&p, colons), "so the filter must not refuse it");
let dashes: &[u8] = b"host 01-23-45-67-89-ab up";
assert!(!engine(&p, dashes).is_empty(), "the hyphen form is a mac too");
assert!(!requires_absent_run(&p, dashes));
let short: &[u8] = b"host 01:23:45:67:89 up";
assert!(requires_absent_run(&p, short));
assert!(engine(&p, short).is_empty(), "nothing to lose by refusing it");
}
#[test]
fn a_kind_or_a_shape_that_names_no_run_is_never_refused_by_one() {
let hay: &[u8] = b"short words only, and none of them long";
for src in ["\\W", "\\N", "\\E", "\\U", "\\{uuid}", "\\I", "\\A"] {
let p = crate::parse(src).expect("pattern parses");
assert!(!requires_absent_run(&p, hay), "{src} names no run");
}
for src in ["\\{base64} \\W", "(\\{base64} | \"x\")", "\\{base64}*"] {
let p = crate::parse(src).expect("pattern parses");
assert!(!requires_absent_run(&p, hay), "{src} is not a bare atom");
}
}
fn assert_no_false_negatives(f: &dyn Membership) {
for lit in present_literals() {
assert!(
f.might_contain(lit),
"{} false-negatived present literal {:?}",
f.name(),
std::str::from_utf8(lit).unwrap()
);
}
}
#[test]
fn bloom_has_no_false_negatives() {
assert_no_false_negatives(&BloomFilter::build(CORPUS));
}
#[test]
fn cuckoo_has_no_false_negatives() {
assert_no_false_negatives(&CuckooFilter::build(CORPUS));
}
#[test]
fn xor_has_no_false_negatives() {
assert_no_false_negatives(&XorFilter::build(CORPUS));
}
#[test]
fn absent_literals_are_mostly_rejected() {
for f in [
Box::new(BloomFilter::build(CORPUS)) as Box<dyn Membership>,
Box::new(CuckooFilter::build(CORPUS)),
Box::new(XorFilter::build(CORPUS)),
] {
let rejected = absent_literals().iter().filter(|l| !f.might_contain(l)).count();
assert!(
rejected >= 5,
"{} rejected only {rejected}/6 absent literals",
f.name()
);
}
}
#[test]
fn short_literal_is_never_rejected() {
let f = BloomFilter::build(CORPUS);
assert!(f.might_contain(b"zz"));
}
#[test]
fn absent_guard_literals_finds_the_missing_one() {
let pattern = crate::parser::parse(". ~\"CRITICAL\"").unwrap();
let absent = absent_guard_literals(&pattern, CORPUS);
assert!(absent.contains(b"CRITICAL".as_slice()));
let pattern2 = crate::parser::parse(". ~\"ERROR\"").unwrap();
let absent2 = absent_guard_literals(&pattern2, CORPUS);
assert!(absent2.is_empty(), "ERROR is present, so nothing is absent");
}
}