use std::ops::Range;
use super::files::{unterminated_tail, without_cr};
use super::{
Block, BlockError, Blocks, Job, MAX_BLOCKS, OneCopy, Refusal, Slots, Tracker, tracked,
};
const TEXT_BLOCK_MIN: usize = 64 * 1024;
#[derive(Clone, Debug, PartialEq, Eq)]
pub struct TextMatch {
pub index: u64,
pub line_number: u64,
pub line: String,
}
#[derive(Clone, Debug, PartialEq, Eq)]
pub struct TextMeasure {
pub bytes: u64,
pub lines: u64,
pub words: u64,
pub matches: Option<u64>,
}
#[derive(Clone, Copy, Debug, Default, PartialEq, Eq, Hash)]
pub enum TextTransform {
#[default]
Replace,
ToUpper,
ToLower,
}
impl TextTransform {
pub const ALL: [Self; 3] = [Self::Replace, Self::ToUpper, Self::ToLower];
pub const NAMES: [&'static str; 3] = ["Replace", "ToUpper", "ToLower"];
}
fn hits_in(hay: &[u8], needle: &[u8], span: Range<usize>) -> Vec<usize> {
if needle.is_empty() || needle.len() > hay.len() {
return Vec::new();
}
let stop = (span.end + needle.len() - 1).min(hay.len());
if span.start >= stop || stop - span.start < needle.len() {
return Vec::new();
}
let mut hits = Vec::new();
for (offset, w) in hay[span.start..stop].windows(needle.len()).enumerate() {
if w == needle && span.start + offset < span.end {
hits.push(span.start + offset);
}
}
hits
}
fn newlines_in(hay: &[u8], span: Range<usize>) -> Vec<usize> {
let start = span.start;
hay[span]
.iter()
.enumerate()
.filter(|(_offset, b)| **b == b'\n')
.map(|(offset, _newline)| start + offset)
.collect()
}
fn line_of(newlines: &[usize], at: usize) -> u64 {
newlines.partition_point(|&p| p < at) as u64 + 1
}
fn line_at(hay: &[u8], newlines: &[usize], at: usize) -> String {
let idx = newlines.partition_point(|&p| p < at);
let start = if idx == 0 { 0 } else { newlines[idx - 1] + 1 };
let end = match newlines.get(idx) {
Some(&p) => p,
None => hay.len(),
};
String::from_utf8_lossy(without_cr(&hay[start..end])).into_owned()
}
fn non_overlapping(hits: &[usize], width: usize) -> usize {
let mut kept = 0usize;
let mut next_free = 0usize;
for &at in hits {
if at >= next_free {
kept += 1;
next_free = at + width;
}
}
kept
}
fn text_blocks(n: usize) -> (Blocks, Option<usize>) {
let blocks = Blocks::new(n, TEXT_BLOCK_MIN, MAX_BLOCKS);
let opening = (blocks.count() > 0).then_some(blocks.count());
(blocks, opening)
}
fn concat(parts: Vec<Vec<usize>>) -> Vec<usize> {
parts.into_iter().flatten().collect()
}
pub struct SearchTextJob<'a> {
hay: &'a [u8],
needle: Vec<u8>,
blocks: Blocks,
found: Slots<(Vec<usize>, Vec<usize>)>,
hits: Vec<usize>,
newlines: Vec<usize>,
tracker: Tracker,
}
pub fn search_text<'a>(text: &'a str, pattern: &str) -> Result<SearchTextJob<'a>, Refusal> {
if pattern.is_empty() {
return Err(Refusal::argument("Pattern must not be empty"));
}
let hay = text.as_bytes();
let (blocks, opening) = text_blocks(hay.len());
Ok(SearchTextJob {
hay,
needle: pattern.as_bytes().to_vec(),
found: Slots::new(blocks.count()),
hits: Vec::new(),
newlines: Vec::new(),
tracker: Tracker::new(opening),
blocks,
})
}
impl Block for SearchTextJob<'_> {
fn run_block(&self, _phase: usize, block: usize) {
let span = self.blocks.range(block);
let hits = hits_in(self.hay, &self.needle, span.clone());
let newlines = newlines_in(self.hay, span);
self.found.put(block, (hits, newlines));
}
}
impl Job for SearchTextJob<'_> {
type Answer = Vec<TextMatch>;
tracked!();
fn end_phase(&mut self, phase: usize) -> Result<(), Refusal> {
self.tracker.check_ended(phase)?;
let (hits, newlines): (Vec<Vec<usize>>, Vec<Vec<usize>>) =
self.found.take_all()?.into_iter().unzip();
self.hits = concat(hits);
self.newlines = concat(newlines);
self.tracker.advance(None);
Ok(())
}
fn finish(self) -> Result<Vec<TextMatch>, Refusal> {
self.tracker.check_finished()?;
Ok(self
.hits
.iter()
.map(|&at| TextMatch {
index: at as u64,
line_number: line_of(&self.newlines, at),
line: line_at(self.hay, &self.newlines, at),
})
.collect())
}
}
pub struct TextCountJob<'a> {
hay: &'a [u8],
needle: Option<Vec<u8>>,
blocks: Blocks,
counts: Slots<(u64, u64, Vec<usize>)>,
totals: (u64, u64),
hits: Vec<usize>,
tracker: Tracker,
}
pub fn text_count<'a>(text: &'a str, pattern: Option<&str>) -> Result<TextCountJob<'a>, Refusal> {
let needle = match pattern {
None => None,
Some("") => return Err(Refusal::argument("Pattern must not be empty")),
Some(p) => Some(p.as_bytes().to_vec()),
};
let hay = text.as_bytes();
let (blocks, opening) = text_blocks(hay.len());
Ok(TextCountJob {
hay,
needle,
counts: Slots::new(blocks.count()),
totals: (0, 0),
hits: Vec::new(),
tracker: Tracker::new(opening),
blocks,
})
}
impl Block for TextCountJob<'_> {
#[inline(always)]
fn run_block(&self, _phase: usize, block: usize) {
let span = self.blocks.range(block);
let (lo, hi) = (span.start, span.end);
let mut lines = 0u64;
let mut words = 0u64;
let mut prev_space = lo == 0 || self.hay[lo - 1].is_ascii_whitespace();
for &b in &self.hay[lo..hi] {
if b == b'\n' {
lines += 1;
}
let space = b.is_ascii_whitespace();
if prev_space && !space {
words += 1;
}
prev_space = space;
}
let hits = match &self.needle {
Some(needle) => hits_in(self.hay, needle, span),
None => Vec::new(),
};
self.counts.put(block, (lines, words, hits));
}
}
impl Job for TextCountJob<'_> {
type Answer = TextMeasure;
tracked!();
fn end_phase(&mut self, phase: usize) -> Result<(), Refusal> {
self.tracker.check_ended(phase)?;
let mut lines = 0u64;
let mut words = 0u64;
let mut hits = Vec::new();
for (l, w, h) in self.counts.take_all()? {
lines += l;
words += w;
hits.extend(h);
}
self.totals = (lines, words);
self.hits = hits;
self.tracker.advance(None);
Ok(())
}
fn finish(self) -> Result<TextMeasure, Refusal> {
self.tracker.check_finished()?;
Ok(TextMeasure {
bytes: self.hay.len() as u64,
lines: self.totals.0 + unterminated_tail(self.hay),
words: self.totals.1,
matches: self
.needle
.as_ref()
.map(|needle| non_overlapping(&self.hits, needle.len()) as u64),
})
}
}
struct Find<'a> {
hay: &'a [u8],
needle: Vec<u8>,
blocks: Blocks,
found: Slots<Vec<usize>>,
hits: Vec<usize>,
tracker: Tracker,
}
impl<'a> Find<'a> {
fn new(text: &'a str, needle: &str) -> Self {
let hay = text.as_bytes();
let (blocks, opening) = text_blocks(hay.len());
Self {
hay,
needle: needle.as_bytes().to_vec(),
found: Slots::new(blocks.count()),
hits: Vec::new(),
tracker: Tracker::new(opening),
blocks,
}
}
fn run(&self, phase: usize, block: usize) -> Result<(), BlockError> {
self.tracker.run(phase, block, self)
}
fn end_phase(&mut self, phase: usize) -> Result<(), Refusal> {
self.tracker.check_ended(phase)?;
self.hits = concat(self.found.take_all()?);
self.tracker.advance(None);
Ok(())
}
fn pieces(&self) -> Vec<&'a [u8]> {
let width = self.needle.len();
let mut out = Vec::with_capacity(self.hits.len() + 1);
let mut cursor = 0usize;
for &at in &self.hits {
if at < cursor {
continue;
}
out.push(&self.hay[cursor..at]);
cursor = at + width;
}
out.push(&self.hay[cursor..]);
out
}
}
impl Block for Find<'_> {
fn run_block(&self, _phase: usize, block: usize) {
let hits = hits_in(self.hay, &self.needle, self.blocks.range(block));
self.found.put(block, hits);
}
}
pub struct SplitTextJob<'a> {
find: Find<'a>,
no_empty: bool,
}
pub fn split_text<'a>(
text: &'a str,
separator: &str,
no_empty: bool,
) -> Result<SplitTextJob<'a>, Refusal> {
if separator.is_empty() {
return Err(Refusal::argument("Separator must not be empty"));
}
Ok(SplitTextJob {
find: Find::new(text, separator),
no_empty,
})
}
impl Job for SplitTextJob<'_> {
type Answer = Vec<String>;
fn blocks(&self, phase: usize) -> Option<usize> {
self.find.tracker.blocks(phase)
}
fn state(&self, phase: usize, block: usize) -> Option<super::BlockState> {
self.find.tracker.state(phase, block)
}
fn run(&self, phase: usize, block: usize) -> Result<(), BlockError> {
self.find.run(phase, block)
}
fn end_phase(&mut self, phase: usize) -> Result<(), Refusal> {
self.find.end_phase(phase)
}
fn finish(self) -> Result<Vec<String>, Refusal> {
self.find.tracker.check_finished()?;
let mut out: Vec<String> = self
.find
.pieces()
.into_iter()
.map(|piece| String::from_utf8_lossy(piece).into_owned())
.collect();
if self.no_empty {
out.retain(|s| !s.is_empty());
}
Ok(out)
}
}
fn piece_bounds(text: &str, lower: bool) -> Vec<usize> {
let n = text.len();
let bytes = text.as_bytes();
let blocks = Blocks::new(n, TEXT_BLOCK_MIN, MAX_BLOCKS);
let mut bounds = vec![0usize];
let mut last = 0usize;
for b in 1..blocks.count() {
let nominal = blocks.range(b).start.max(last + 1);
if nominal >= n {
break;
}
let at = if lower {
match bytes[nominal - 1..]
.iter()
.position(|c| c.is_ascii_whitespace())
{
Some(offset) => nominal + offset,
None => break,
}
} else {
let mut at = nominal;
while at < n && !text.is_char_boundary(at) {
at += 1;
}
at
};
if at > last && at < n {
bounds.push(at);
last = at;
}
}
bounds.push(n);
bounds
}
enum Rewrite<'a> {
Replace {
find: Find<'a>,
replacement: String,
},
Case {
text: &'a str,
upper: bool,
bounds: Vec<usize>,
pieces: Slots<String>,
done: Vec<String>,
tracker: Tracker,
},
}
pub struct UpdateTextJob<'a> {
rewrite: Rewrite<'a>,
capacity: usize,
}
pub fn update_text<'a>(
text: &'a str,
op: TextTransform,
pattern: Option<&str>,
replacement: Option<&str>,
) -> Result<UpdateTextJob<'a>, Refusal> {
let rewrite = match op {
TextTransform::Replace => {
let Some(pattern) = pattern else {
return Err(Refusal::argument("Replace needs Pattern"));
};
if pattern.is_empty() {
return Err(Refusal::argument("Pattern must not be empty"));
}
let replacement = match replacement {
Some(r) => r.to_string(),
None => String::new(),
};
Rewrite::Replace {
find: Find::new(text, pattern),
replacement,
}
}
TextTransform::ToUpper | TextTransform::ToLower => {
let upper = op == TextTransform::ToUpper;
let bounds = if text.is_empty() {
Vec::new()
} else {
piece_bounds(text, !upper)
};
let n_pieces = bounds.len().saturating_sub(1);
Rewrite::Case {
text,
upper,
pieces: Slots::new(n_pieces),
done: Vec::new(),
tracker: Tracker::new((n_pieces > 0).then_some(n_pieces)),
bounds,
}
}
};
Ok(UpdateTextJob {
rewrite,
capacity: text.len(),
})
}
impl Job for UpdateTextJob<'_> {
type Answer = String;
fn blocks(&self, phase: usize) -> Option<usize> {
match &self.rewrite {
Rewrite::Replace { find, .. } => find.tracker.blocks(phase),
Rewrite::Case { tracker, .. } => tracker.blocks(phase),
}
}
fn state(&self, phase: usize, block: usize) -> Option<super::BlockState> {
match &self.rewrite {
Rewrite::Replace { find, .. } => find.tracker.state(phase, block),
Rewrite::Case { tracker, .. } => tracker.state(phase, block),
}
}
fn run(&self, phase: usize, block: usize) -> Result<(), BlockError> {
match &self.rewrite {
Rewrite::Replace { find, .. } => find.run(phase, block),
Rewrite::Case {
text,
upper,
bounds,
pieces,
tracker,
..
} => tracker.run(
phase,
block,
&OneCopy(|_phase, block| {
let piece = &text[bounds[block]..bounds[block + 1]];
let mapped = if *upper {
piece.to_uppercase()
} else {
piece.to_lowercase()
};
pieces.put(block, mapped);
}),
),
}
}
fn end_phase(&mut self, phase: usize) -> Result<(), Refusal> {
match &mut self.rewrite {
Rewrite::Replace { find, .. } => find.end_phase(phase),
Rewrite::Case {
pieces,
done,
tracker,
..
} => {
tracker.check_ended(phase)?;
*done = pieces.take_all()?;
tracker.advance(None);
Ok(())
}
}
}
fn finish(self) -> Result<String, Refusal> {
match self.rewrite {
Rewrite::Replace { find, replacement } => {
find.tracker.check_finished()?;
let pieces = find.pieces();
let mut out = String::with_capacity(self.capacity);
let last = pieces.len().saturating_sub(1);
for (i, piece) in pieces.into_iter().enumerate() {
out.push_str(&String::from_utf8_lossy(piece));
if i < last {
out.push_str(&replacement);
}
}
Ok(out)
}
Rewrite::Case { done, tracker, .. } => {
tracker.check_finished()?;
Ok(done.concat())
}
}
}
}
#[cfg(test)]
mod tests {
use super::super::{drive, drive_serial, simd};
use super::*;
fn drive_reversed<J: Job>(job: J) -> Result<J::Answer, Refusal> {
drive(job, |n, body| {
for b in (0..n).rev() {
body(b)?;
}
Ok(())
})
}
fn long_text() -> String {
let mut s = String::new();
let mut i = 0u64;
while s.len() < 700_000 {
s.push_str(&format!("line {i} has ERROR and ERRORERROR\r\n"));
i += 1;
}
s.push_str("tail without newline ERROR");
s
}
#[test]
fn a_search_finds_what_a_serial_scan_finds_with_the_right_lines() {
let text = long_text();
let got =
drive_reversed(search_text(&text, "ERROR").expect("a pattern")).expect("finishes");
let want: Vec<usize> = text.match_indices("ERROR").map(|(at, _found)| at).collect();
assert_eq!(
got.iter().map(|m| m.index as usize).collect::<Vec<_>>(),
want
);
assert_eq!(got[0].line_number, 1);
assert_eq!(got[0].line, "line 0 has ERROR and ERRORERROR");
let last = got.last().expect("matches");
assert_eq!(last.line, "tail without newline ERROR");
assert_eq!(
search_text(&text, "").err().map(|r| r.message).as_deref(),
Some("Pattern must not be empty")
);
}
#[test]
fn counts_agree_with_the_serial_walk() {
let text = long_text();
let got = drive_reversed(text_count(&text, Some("ERRORERROR")).expect("a pattern"))
.expect("finishes");
assert_eq!(got.bytes, text.len() as u64);
assert_eq!(got.lines, text.lines().count() as u64);
assert_eq!(got.words, text.split_ascii_whitespace().count() as u64);
assert_eq!(got.matches, Some(text.matches("ERRORERROR").count() as u64));
let none = drive_serial(text_count("", None).expect("no pattern")).expect("finishes");
assert_eq!(
none,
TextMeasure {
bytes: 0,
lines: 0,
words: 0,
matches: None
}
);
}
#[test]
fn a_split_and_a_replace_agree_with_std() {
let text = long_text();
let parts = drive_reversed(split_text(&text, "ERROR", false).expect("a separator"))
.expect("finishes");
assert_eq!(parts, text.split("ERROR").collect::<Vec<_>>());
let kept =
drive_serial(split_text("a,,b", ",", true).expect("a separator")).expect("finishes");
assert_eq!(kept, vec!["a", "b"]);
assert_eq!(
drive_serial(split_text("", ",", false).expect("a separator")).expect("finishes"),
vec![String::new()]
);
let replaced = drive_reversed(
update_text(&text, TextTransform::Replace, Some("ERROR"), Some("ok"))
.expect("a pattern"),
)
.expect("finishes");
assert_eq!(replaced, text.replace("ERROR", "ok"));
let deleted = drive_serial(
update_text("aXbXc", TextTransform::Replace, Some("X"), None).expect("a pattern"),
)
.expect("finishes");
assert_eq!(deleted, "abc");
assert_eq!(
update_text("a", TextTransform::Replace, None, None)
.err()
.map(|r| r.message)
.as_deref(),
Some("Replace needs Pattern")
);
}
#[test]
fn lowercasing_splits_where_no_final_sigma_can_be_moved() {
let mut text = String::new();
while text.len() < 600_000 {
text.push_str("ΟΔΟΣΣΟΦΙΑΣ ΑΣΑ ΣΑΣ\n");
}
let lowered = drive_reversed(
update_text(&text, TextTransform::ToLower, None, None).expect("no operand"),
)
.expect("finishes");
assert_eq!(lowered, text.to_lowercase());
let raised = drive_reversed(
update_text(&lowered, TextTransform::ToUpper, None, None).expect("no operand"),
)
.expect("finishes");
assert_eq!(raised, lowered.to_uppercase());
for &at in &piece_bounds(&text, true)[1..] {
if at < text.len() {
assert!(
text.as_bytes()[at - 1].is_ascii_whitespace(),
"split at {at}"
);
}
}
}
#[test]
fn text_with_no_whitespace_lowercases_whole() {
let text = "ΣΑ".repeat(200_000);
assert_eq!(piece_bounds(&text, true), vec![0, text.len()]);
let lowered = drive_serial(
update_text(&text, TextTransform::ToLower, None, None).expect("no operand"),
)
.expect("finishes");
assert_eq!(lowered, text.to_lowercase());
}
#[test]
fn the_transform_names_follow_the_declaration_order() {
for (op, name) in TextTransform::ALL.iter().zip(TextTransform::NAMES) {
assert_eq!(format!("{op:?}"), name);
}
}
#[test]
fn every_kernel_answers_the_baseline_s_bits_at_every_level() {
let text = long_text();
simd::assert_every_level_agrees("search", || {
drive_reversed(search_text(&text, "ERROR").expect("a pattern")).expect("finishes")
});
simd::assert_every_level_agrees("count", || {
drive_reversed(text_count(&text, Some("ERRORERROR")).expect("a pattern"))
.expect("finishes")
});
simd::assert_every_level_agrees("split", || {
drive_reversed(split_text(&text, "ERROR", false).expect("a separator"))
.expect("finishes")
});
let mut greek = String::new();
while greek.len() < 300_000 {
greek.push_str("ΟΔΟΣΣΟΦΙΑΣ ΑΣΑ ΣΑΣ ERROR\n");
}
for input in [&text, &greek] {
for op in TextTransform::ALL {
simd::assert_every_level_agrees(&format!("update {op:?}"), || {
drive_reversed(update_text(input, op, Some("ERROR"), Some("ok")).expect("ok"))
.expect("finishes")
});
}
}
}
}