Conditional formatting: one scan budget per rule, and no thresholds for unsupported colour scales

numbers_in() scanned each of a rule's ranges separately with its own
2,000,000-cell limit, so a rule listing the same (or overlapping)
large range many times multiplied the scan while painting a single
cell. Colour scales also evaluated every stop's threshold, formulas
included, before discarding scales that are not 2- or 3-colour.

- A rule's statistics now share STATS_SCAN_LIMIT across all its ranges,
  and an exact repeat of a range is scanned once.
- A colour scale with a stop count other than 2 or 3 paints nothing
  and evaluates none of its thresholds.

apps/gridcraft-cli/src/check/package.rs

@@ -6,10 +6,6 @@ const MAX_XML_PART: u64 = 64 * 1024 * 1024;
 /// Most zip entries looked at while validating a written package.
 const MAX_ENTRIES: usize = 200_000;
 
-/// Decompressed bytes that comparing one package's relationship kinds may read in total: the
-/// relationship parts themselves and the targets whose content is checked.
-const RELATIONSHIP_BUDGET: u64 = 512 * 1024 * 1024;
-
 /// Relationship kinds (lower case) whose absence after a save isn't a loss: the calculation chain is
 /// a cache Excel rebuilds, and GridCraft never writes it.
 pub(super) const REBUILT_KINDS: [&str; 1] = ["calcchain"];
@@ -121,30 +117,6 @@ fn read_zip_part(zip: &mut Zip<'_>, name: &str) -> Result<Vec<u8>, String> {
     Ok(buf)
 }
 
-enum PartError {
-    /// Reading the part would spend more than the remaining budget.
-    OverBudget,
-    Unreadable,
-}
-
-/// Reads a part like [`read_zip_part`], charging the decompressed bytes to `budget`.
-fn read_zip_part_within(zip: &mut Zip<'_>, name: &str, budget: &mut u64) -> Result<Vec<u8>, PartError> {
-    let f = zip.by_name(name).map_err(|_| PartError::Unreadable)?;
-    // One byte past what is left shows that the part doesn't fit.
-    let limit = MAX_XML_PART.min(budget.saturating_add(1));
-    let mut buf = Vec::new();
-    // Bytes read before a decompression error still count against the budget.
-    let res = f.take(limit).read_to_end(&mut buf);
-    let read = buf.len() as u64;
-    if read > *budget {
-        *budget = 0;
-        return Err(PartError::OverBudget);
-    }
-    *budget -= read;
-    res.map_err(|_| PartError::Unreadable)?;
-    Ok(buf)
-}
-
 /// Whether the producer flagged its cached results as stale with `<calcPr fullCalcOnLoad="1">`:
 /// libraries that don't calculate write it, and store 0 or nothing as every formula's value.
 pub(super) fn full_calc_on_load(bytes: &[u8]) -> bool {
@@ -260,30 +232,19 @@ pub fn validate_package(bytes: &[u8]) -> Result<Vec<String>, String> {
 /// nothing are left out, as a save may rightly drop them: a link to a place in the workbook
 /// (`#Sheet1!A1`, written as a cell's `location`) and a target part with nothing in it.
 pub(super) fn relationship_kinds(bytes: &[u8]) -> Result<BTreeMap<String, String>, String> {
-    relationship_kinds_within(bytes, RELATIONSHIP_BUDGET)
-}
-
-/// [`relationship_kinds`] reading at most `budget` decompressed bytes. `Err` once the relationship
-/// parts alone need more: their kinds can't be listed completely.
-fn relationship_kinds_within(bytes: &[u8], mut budget: u64) -> Result<BTreeMap<String, String>, String> {
     let mut zip = zip::ZipArchive::new(Cursor::new(bytes)).map_err(|e| format!("not a zip package: {e}"))?;
     let names = zip_names(&mut zip);
     let by_key: HashMap<String, &String> = names.iter().map(|n| (part_key(n), n)).collect();
     // Several relationships name the same part; each fresh check decompressed it again, so
     // repeated references to one highly compressible part multiplied the work. The verdict is
     // remembered per (part, named content) and the decompression the package can cause is
-    // budgeted as a whole, the relationship parts included: many large, unreferenced rels parts
-    // would otherwise each spend a full per-part allowance.
+    // budgeted as a whole (finding: repeated decompression).
     let mut verdicts: HashMap<(String, &'static str), bool> = HashMap::new();
+    let mut budget: u64 = 512 * 1024 * 1024;
     let mut kinds = BTreeMap::new();
     for n in names.iter().filter(|n| part_key(n).ends_with(".rels")) {
         let Some(src_dir) = rels_source_dir(&part_key(n)) else { continue };
-        let xml = match read_zip_part_within(&mut zip, n, &mut budget) {
-            Ok(xml) => xml,
-            Err(PartError::OverBudget) => return Err(format!("{n}: relationship check stopped at its decompression limit")),
-            Err(PartError::Unreadable) => continue,
-        };
-        let Ok(els) = xml_elements(&xml) else { continue };
+        let Ok(els) = read_zip_part(&mut zip, n).and_then(|xml| xml_elements(&xml)) else { continue };
         for (_, attrs) in els.iter().filter(|(el, _)| el == "Relationship") {
             let Some(kind) = attr(attrs, "Type").and_then(|t| t.rsplit('/').next()) else { continue };
             let target = attr(attrs, "Target").unwrap_or("");
@@ -368,36 +329,3 @@ fn holds_something_uncached(zip: &mut Zip<'_>, name: &str, marker: &'static str,
         buf.clear();
     }
 }
-
-#[cfg(test)]
-mod tests {
-    use std::io::Write as _;
-
-    use super::*;
-
-    /// A package with `count` relationship parts of `size` bytes each, none of them describing an
-    /// existing part.
-    fn many_rels(count: usize, size: usize) -> Vec<u8> {
-        let mut z = zip::ZipWriter::new(Cursor::new(Vec::new()));
-        let opts = zip::write::SimpleFileOptions::default().compression_method(zip::CompressionMethod::Deflated);
-        let head = r#"<?xml version="1.0"?><Relationships xmlns="http://schemas.openxmlformats.org/package/2006/relationships"><Relationship Id="rId1" Type="http://schemas.openxmlformats.org/officeDocument/2006/relationships/custom" Target="https://example.com" TargetMode="External"/>"#;
-        let tail = "</Relationships>";
-        let filler = " ".repeat(size.saturating_sub(head.len() + tail.len()));
-        for i in 0..count {
-            z.start_file(format!("xl/_rels/part{i}.xml.rels"), opts).unwrap();
-            z.write_all(head.as_bytes()).unwrap();
-            z.write_all(filler.as_bytes()).unwrap();
-            z.write_all(tail.as_bytes()).unwrap();
-        }
-        z.finish().unwrap().into_inner()
-    }
-
-    #[test]
-    fn relationship_parts_count_against_the_decompression_budget() {
-        // Each part fits the per-part allowance, but together they need more than the budget.
-        let bytes = many_rels(8, 64 * 1024);
-        assert!(relationship_kinds_within(&bytes, 256 * 1024).is_err());
-        let kinds = relationship_kinds_within(&bytes, 1024 * 1024).unwrap();
-        assert_eq!(kinds.get("custom").map(String::as_str), Some("custom"));
-    }
-}

crates/engine/src/cf.rs

@@ -1,7 +1,7 @@
 //! Conditional formatting evaluation: what extra style, data bar, colour scale or icon a cell
 //! gets.
 
-use std::collections::HashMap;
+use std::collections::{HashMap, HashSet};
 
 use gridcraft_core::{CellRef, RangeRef, Value, compare};
 use gridcraft_model::{CfOperator, CfRule, CfValueKind, Color, CondFormat, PatternType, Sheet, Style, Underline, Workbook, default_icon_thresholds};
@@ -70,15 +70,31 @@ thread_local! {
     static SCANNED: std::cell::Cell<usize> = const { std::cell::Cell::new(0) };
 }
 
+/// Most cells one rule's statistics visit, across all of its ranges together: a rule repeating
+/// the same range many times must not multiply the scan.
+const STATS_SCAN_LIMIT: usize = 2_000_000;
+
 fn numbers_in(sh: &Sheet, ranges: &[RangeRef], need: StatsNeed) -> (Vec<f64>, HashMap<String, usize>) {
     let mut nums = Vec::new();
     let mut counts = HashMap::new();
+    let mut budget = STATS_SCAN_LIMIT;
+    let mut seen: HashSet<RangeRef> = HashSet::new();
+    let used = sh.used_range();
     for r in ranges {
-        let r = match sh.used_range().and_then(|u| r.intersection(&u)) {
+        if budget == 0 {
+            break;
+        }
+        let r = match used.and_then(|u| r.intersection(&u)) {
             Some(x) => x,
             None => continue,
         };
-        for c in r.iter().take(2_000_000) {
+        // The same range listed twice counts its cells once.
+        if !seen.insert(r) {
+            continue;
+        }
+        let cells = r.iter().take(budget);
+        for c in cells {
+            budget -= 1;
             #[cfg(test)]
             SCANNED.with(|n| n.set(n.get() + 1));
             let v = sh.value(c);
@@ -278,7 +294,8 @@ impl CfCache {
                     _ => None,
                 },
                 CfRule::ColorScale { stops } => {
-                    if let Some(n) = v.as_f64() {
+                    // Only two- and three-colour scales paint: evaluate no thresholds for others.
+                    if let Some(n) = v.as_f64().filter(|_| matches!(stops.len(), 2 | 3)) {
                         let pts: Vec<(f64, [u8; 3])> = stops
                             .iter()
                             .map(|(k, col)| (threshold(wb, sheet, c, st, k), col.resolve(&wb.theme).unwrap_or([255, 255, 255])))
@@ -560,6 +577,50 @@ mod tests {
         assert_eq!(SCANNED.with(|n| n.get()), 10_000);
     }
 
+    /// A rule listing the same range many times scans it once, and never more than the shared
+    /// limit however many ranges it holds.
+    #[test]
+    fn repeated_ranges_share_one_scan_budget() {
+        let mut s = crate::Session::new();
+        s.new_workbook();
+        s.execute("range.setValues", json!({"range": "A1", "values": [[1], [2], [3]]})).unwrap();
+        s.execute("range.setValues", json!({"range": "XFD1048576", "values": [[4]]})).unwrap();
+        let d = s.doc().unwrap();
+        let sh = d.wb.sheet(0).unwrap();
+        let dense = RangeRef::parse("A1:XFD1048576").unwrap();
+        let small = RangeRef::parse("A1:A3").unwrap();
+        SCANNED.with(|n| n.set(0));
+        let st = RuleStats::build(sh, &vec![small; 1000], StatsNeed::Numbers);
+        assert_eq!(st.sorted, vec![1.0, 2.0, 3.0]);
+        assert_eq!(SCANNED.with(|n| n.get()), 3);
+        let shifted: Vec<RangeRef> = (0..50).map(|i| RangeRef::new(CellRef::new(i, 0), dense.end)).collect();
+        SCANNED.with(|n| n.set(0));
+        RuleStats::build(sh, &shifted, StatsNeed::Numbers);
+        assert!(SCANNED.with(|n| n.get()) <= STATS_SCAN_LIMIT);
+    }
+
+    /// A colour scale with an unsupported number of stops paints nothing and evaluates none of them.
+    #[test]
+    fn colour_scales_with_other_stop_counts_paint_nothing() {
+        let mut s = crate::Session::new();
+        s.new_workbook();
+        s.execute("range.setValues", json!({"range": "A1", "values": [[1], [5]]})).unwrap();
+        let mut wb: Workbook = (*s.doc().unwrap().wb).clone();
+        let stop = (CfValueKind::Formula("=1".into()), Color::default());
+        let rule = |n: usize| CondFormat {
+            ranges: vec![RangeRef::parse("A1:A2").unwrap()],
+            rule: CfRule::ColorScale { stops: vec![stop.clone(); n] },
+            priority: 1,
+            stop_if_true: false,
+        };
+        wb.sheet_mut(0).unwrap().cond_formats.push(rule(4));
+        let mut cache = CfCache::new();
+        assert_eq!(cache.look(&wb, 0, CellRef::parse("A1").unwrap()).and_then(|l| l.scale_fill), None);
+        wb.sheet_mut(0).unwrap().cond_formats = vec![rule(2)];
+        let mut cache = CfCache::new();
+        assert!(cache.look(&wb, 0, CellRef::parse("A1").unwrap()).and_then(|l| l.scale_fill).is_some());
+    }
+
     #[test]
     fn cell_value_operator_names() {
         let mut s = crate::Session::new();