1687a9c05b0c
find.rs
use super::cell::input_to_cell;
use super::{Cell, CellRef, EngineError, Json, Result, Session, Value, bad, bool_param, edit, json, str_param};
// ---------------------------------------------------------------- find & replace
fn matches(hay: &str, what: &str, case: bool, whole: bool) -> bool {
let (h, w) = if case { (hay.to_string(), what.to_string()) } else { (hay.to_lowercase(), what.to_lowercase()) };
let has_wild = w.contains(['*', '?']);
if has_wild {
let pat = if whole { w } else { format!("*{w}*") };
return wildcard(&h, &pat);
}
if whole { h == w } else { h.contains(&w) }
}
/// `*`/`?` wildcard match with `~` escapes.
///
/// The pattern runs as a bit-parallel automaton over the text: one pass, each character costing
/// one step per 64 pattern positions. Backtracking to the last `*` after a mismatch rescans the
/// text and costs text ร pattern comparisons on a long, repetitive cell, for every cell a
/// filter or Find visits.
pub(crate) fn wildcard(text: &str, pat: &str) -> bool {
// The pattern as (character, escaped) items, runs of `*` folded into one.
let mut p: Vec<(char, bool)> = Vec::new();
let mut it = pat.chars();
while let Some(c) = it.next() {
if c == '~' {
if let Some(n) = it.next() {
p.push((n, true));
}
} else if c != '*' || p.last() != Some(&('*', false)) {
p.push((c, false));
}
}
let words = (p.len() + 1).div_ceil(64);
let bit = |set: &mut [u64], i: usize| set[i / 64] |= 1 << (i % 64);
// Positions holding a `*` and a `?`, and where each literal character sits in the pattern.
let mut stars = vec![0u64; words];
let mut any = vec![0u64; words];
let mut at: std::collections::HashMap<char, Vec<usize>> = std::collections::HashMap::new();
for (i, item) in p.iter().enumerate() {
match item {
('*', false) => bit(&mut stars, i),
('?', false) => bit(&mut any, i),
(c, _) => at.entry(*c).or_default().push(i),
}
}
// A literal's bit mask is built when the text first reads it, and kept for at most
// `MAX_CACHED_MASKS` literals: a long pattern of mostly distinct characters would otherwise
// allocate a mask of the pattern's width for each one up front. When there are more literals
// than that, the ones kept are those at the most pattern positions (the dearest to rebuild);
// each of the rest has at most pattern length / `MAX_CACHED_MASKS` positions, so rebuilding
// its mask in `scratch` costs less than one step of the scan.
const MAX_CACHED_MASKS: usize = 256;
let cacheable: Option<std::collections::HashSet<char>> = (at.len() > MAX_CACHED_MASKS).then(|| {
let mut by_count: Vec<(&char, usize)> = at.iter().map(|(c, v)| (c, v.len())).collect();
by_count.sort_unstable_by_key(|&(_, n)| std::cmp::Reverse(n));
by_count.into_iter().take(MAX_CACHED_MASKS).map(|(c, _)| *c).collect()
});
let mut masks: std::collections::HashMap<char, Vec<u64>> = std::collections::HashMap::new();
let mut scratch = vec![0u64; words];
// A set bit i: the text read so far matches the first i pattern items. A `*` matches nothing
// as well, so a state at a `*` is also at the item after it.
let close = |set: &mut Vec<u64>| {
let mut carry = 0u64;
for w in 0..words {
let s = set[w] & stars[w];
let next = (s << 1) | carry;
carry = s >> 63;
set[w] |= next;
}
};
let mut state = vec![0u64; words];
bit(&mut state, 0);
close(&mut state);
let mut next = vec![0u64; words];
for ch in text.chars() {
let lit: Option<&[u64]> = match at.get(&ch) {
None => None,
Some(positions) if cacheable.as_ref().is_none_or(|k| k.contains(&ch)) => {
let mask = masks.entry(ch).or_insert_with(|| {
let mut m = vec![0u64; words];
positions.iter().for_each(|&i| bit(&mut m, i));
m
});
Some(mask)
}
Some(positions) => {
scratch.fill(0);
positions.iter().for_each(|&i| bit(&mut scratch, i));
Some(&scratch)
}
};
let mut carry = 0u64;
let mut alive = 0u64;
for w in 0..words {
// Items that read `ch` advance; a `*` reads it and stays.
let m = state[w] & (any[w] | lit.map_or(0, |l| l[w]));
next[w] = (m << 1) | carry | (state[w] & stars[w]);
carry = m >> 63;
alive |= next[w];
}
if alive == 0 {
return false;
}
std::mem::swap(&mut state, &mut next);
close(&mut state);
}
state[p.len() / 64] & (1 << (p.len() % 64)) != 0
}
pub(super) fn find(s: &mut Session, p: &Json) -> Result<Json> {
let what = str_param(p, "what").unwrap_or("").to_string();
if what.is_empty() {
return Err(bad("edit.find", "missing `what`"));
}
let case = bool_param(p, "matchCase").unwrap_or(false);
let whole = bool_param(p, "wholeCell").unwrap_or(false);
let values = str_param(p, "lookIn") == Some("values");
let by_cols = bool_param(p, "byColumns").unwrap_or(false);
let all = bool_param(p, "all").unwrap_or(false);
let workbook = str_param(p, "within") == Some("workbook");
// `selection`: only the selected cells of the active sheet, as Excel searches a selected range.
let in_selection = str_param(p, "within") == Some("selection");
s.last_find = Some(p.clone());
let d = s.doc()?;
let sheets: Vec<usize> = if workbook { (0..d.wb.sheets.len()).collect() } else { vec![d.wb.active_sheet()] };
let mut hits: Vec<(usize, CellRef, String)> = Vec::new();
for si in sheets {
let Some(sh) = d.wb.sheet(si) else { continue };
let mut cells: Vec<(CellRef, String)> = sh
.cells
.iter()
.filter(|(c, _)| !in_selection || d.selection.contains(*c))
.filter_map(|(c, cell)| {
let text = if values || cell.formula.is_none() || crate::display::formula_hidden(&d.wb, sh, c) {
crate::display::cell_text(&d.wb, sh, c)
} else {
cell.input_text()
};
matches(&text, &what, case, whole).then_some((c, text))
})
.collect();
if by_cols {
cells.sort_by_key(|(c, _)| (c.col, c.row));
}
hits.extend(cells.into_iter().map(|(c, t)| (si, c, t)));
}
if hits.is_empty() {
return Err(EngineError::Other(format!("We couldn't find what you were looking for: {what}")));
}
if all {
let list: Vec<Json> =
hits.iter().map(|(si, c, t)| json!({"sheet": d.wb.sheet(*si).map(|s| s.name.clone()), "cell": c.a1(), "value": t})).collect();
return Ok(json!({"count": list.len(), "results": list}));
}
// Next hit after the active cell.
let cur = (d.wb.active_sheet(), d.selection.active);
let key = |si: usize, c: CellRef| if by_cols { (si, c.col, c.row) } else { (si, c.row, c.col) };
let next = hits.iter().find(|(si, c, _)| key(*si, *c) > key(cur.0, cur.1)).or_else(|| hits.first()).cloned();
let Some((si, c, t)) = next else { return Err(EngineError::Other("not found".into())) };
let dd = s.doc_mut()?;
dd.wb_switch_sheet(si);
if in_selection {
// The range stays selected and the active cell moves through it, as in Excel.
dd.selection.active = c;
} else {
dd.selection = crate::Selection::at(c);
}
Ok(json!({"cell": c.a1(), "sheet": si, "value": t, "count": hits.len()}))
}
/// Most characters a cell holds (Excel's limit).
const REPLACE_CELL_MAX_CHARS: usize = 32_767;
/// Longest text one replacement may give a cell, in bytes: the character limit, each up to four
/// bytes. Every occurrence copies the replacement text, so a short cell full of matches and a
/// long replacement would otherwise expand to gigabytes. The character limit is checked on what
/// fits in this.
const REPLACE_CELL_MAX_BYTES: usize = REPLACE_CELL_MAX_CHARS * 4;
/// Most bytes of replaced text one Replace All builds across all its cells.
const REPLACE_TOTAL_MAX_BYTES: usize = 256 * 1024 * 1024;
pub(super) fn replace(s: &mut Session, p: &Json) -> Result<Json> {
let what = str_param(p, "what").unwrap_or("").to_string();
let with = str_param(p, "with").unwrap_or("");
if what.is_empty() {
return Err(bad("edit.replace", "missing `what`"));
}
let case = bool_param(p, "matchCase").unwrap_or(false);
let whole = bool_param(p, "wholeCell").unwrap_or(false);
let all = bool_param(p, "all").unwrap_or(true);
let workbook = str_param(p, "within") == Some("workbook");
let selection = (str_param(p, "within") == Some("selection")).then(|| s.doc().map(|d| d.selection.clone())).transpose()?;
let active = s.doc()?.selection.active;
let mut skipped = 0usize;
let n = edit(s, |cx| {
let sheets: Vec<usize> = if workbook { (0..cx.wb.sheets.len()).collect() } else { vec![cx.wb.active_sheet()] };
let mut n = 0;
let mut total = 0usize;
for si in sheets {
let cells: Vec<(CellRef, String)> =
// A hidden formula's source is not searched: a count or error would reveal its text.
cx.wb
.sheet(si)
.map(|sh| sh.cells.iter().filter(|(c, cell)| cell.formula.is_none() && cell.py.is_none() || !crate::display::formula_hidden(&cx.wb, sh, *c)).map(|(c, _)| (c, sh.input_text(c))).collect())
.unwrap_or_default();
for (c, text) in cells {
if (!all && c != active) || selection.as_ref().is_some_and(|sel| !sel.contains(c)) {
continue;
}
if !matches(&text, &what, case, whole) {
continue;
}
let new = if whole {
(with.len() <= REPLACE_CELL_MAX_BYTES).then(|| with.to_string())
} else if case {
replace_cs_within(&text, &what, with, REPLACE_CELL_MAX_BYTES)
} else {
replace_ci_within(&text, &what, with, REPLACE_CELL_MAX_BYTES)
};
let new = new.filter(|n| n.chars().count() <= REPLACE_CELL_MAX_CHARS);
let Some(new) = new else {
return Err(EngineError::Other(format!("The replacement makes the text of {} too long.", c.a1())));
};
total = total.saturating_add(new.len());
if total > REPLACE_TOTAL_MAX_BYTES {
return Err(EngineError::Other("The replacements make too much text. Replace in a smaller range.".into()));
}
// A Python cell's text is its code: the replacement edits the code and the cell
// stays a Python cell. Code that would no longer fit in a PY formula is left as it was.
let old_py = cx.wb.sheet(si).and_then(|sh| sh.cell(c)).and_then(|x| x.py.clone());
if let Some(old) = old_py {
let py = gridcraft_model::PyCode { object: old.object, ..gridcraft_model::PyCode::new(&new) };
if py.code == old.code {
continue;
}
if !py.fits() {
skipped += 1;
continue;
}
// Its old spill is left to the recalculation, which removes it and
// recalculates what read it.
let sh = cx.sheet_mut(si)?;
let style = sh.style_id(c);
sh.set_cell(
c,
Cell { value: Value::Error(gridcraft_core::CellError::Blocked), formula: None, style, py: Some(std::sync::Arc::new(py)) },
);
cx.touch(si, c);
n += 1;
continue;
}
let cell = input_to_cell(&new, si, c, &mut cx.wb).unwrap_or_else(|_| Some(Cell::value(Value::text(new.as_str()))));
let sh = cx.sheet_mut(si)?;
match cell {
Some(cell) => sh.set_cell(c, cell),
None => {
sh.remove_cell(c);
}
}
cx.touch(si, c);
n += 1;
}
}
Ok(n)
})?;
if skipped > 0 {
return Ok(json!({"replaced": n, "skipped": skipped}));
}
Ok(json!({"replaced": n}))
}
/// Whether case-folding `s` maps every char to exactly one char of the same UTF-8 length, so
/// byte positions in the folded text still line up with the original's character boundaries.
fn folds_in_place(s: &str) -> bool {
s.chars().all(|c| {
let mut folded = c.to_lowercase();
let first = folded.next();
folded.next().is_none() && first.is_some_and(|l| l.len_utf8() == c.len_utf8())
})
}
#[cfg(test)]
pub(super) fn replace_ci(text: &str, what: &str, with: &str) -> String {
replace_ci_within(text, what, with, usize::MAX).unwrap_or_default()
}
/// `text` with every `what` replaced by `with`, or `None` once the result passes `limit` bytes
/// (checked before each copy, so nothing larger is allocated).
pub(super) fn replace_cs_within(text: &str, what: &str, with: &str, limit: usize) -> Option<String> {
if what.is_empty() {
return (text.len() <= limit).then(|| text.to_string());
}
let mut out = String::new();
let mut i = 0;
for (pos, m) in text.match_indices(what) {
if out.len() + (pos - i) + with.len() > limit {
return None;
}
out.push_str(text.get(i..pos).unwrap_or(""));
out.push_str(with);
i = pos + m.len();
}
let rest = text.get(i..).unwrap_or("");
if out.len() + rest.len() > limit {
return None;
}
out.push_str(rest);
Some(out)
}
/// Case-insensitive [`replace_cs_within`].
pub(super) fn replace_ci_within(text: &str, what: &str, with: &str, limit: usize) -> Option<String> {
let lower = text.to_lowercase();
let w = what.to_lowercase();
// Slicing `text` at positions found in `lower` is only sound when folding kept every byte
// boundary: a length check alone misses foldings that keep the total length while shifting
// boundaries (U+212A KELVIN SIGN shrinks 3โ1 bytes, U+0130 grows 2โ3), where the tail used
// to be dropped. Those fall back to the case-sensitive replace, as length changes already do.
if lower.len() != text.len() || w.is_empty() || !folds_in_place(text) || !folds_in_place(what) {
return replace_cs_within(text, what, with, limit);
}
let mut out = String::new();
let mut i = 0;
while let Some(pos) = lower.get(i..).and_then(|s| s.find(&w)) {
if out.len() + pos + with.len() > limit {
return None;
}
out.push_str(text.get(i..i + pos).unwrap_or(""));
out.push_str(with);
i += pos + w.len();
}
let rest = text.get(i..).unwrap_or("");
if out.len() + rest.len() > limit {
return None;
}
out.push_str(rest);
Some(out)
}
No file is open. Choose one in the tree, or press Ctrl+O (โO on a Mac) to find one by name.
Syntax highlighting could not load. The unmodified read-only text remains available above.