Analysis ToolPak: stop building a report once it outgrows the output limit

Report builders filled their whole output map before write_report
checked its size, so Descriptive Statistics grouped by rows over a
tall, nearly empty column allocated about 16 entries for each of up
to a million variables before refusing the report.

Grid now tracks its extent as values are stored and keeps nothing
once the report's rows x columns pass MAX_OUTPUT_CELLS; write_report
refuses such a report. extent() no longer rescans every entry.

crates/engine/src/cmd/analysis.rs

@@ -272,11 +272,25 @@ struct Grid {
     cells: BTreeMap<(u32, u32), Value>,
     /// Cells shown as percentages.
     pct: Vec<(u32, u32)>,
+    /// Rows and columns spanned by `cells`.
+    rows: u32,
+    cols: u32,
+    /// A cell was dropped because the report outgrew [`MAX_OUTPUT_CELLS`]: the report is refused.
+    too_large: bool,
 }
 
 impl Grid {
+    /// Stores a value. Past [`MAX_OUTPUT_CELLS`] (the most a report writes) nothing more is kept,
+    /// so a builder that would produce millions of entries stops allocating them, and
+    /// [`write_report`] refuses the report.
     fn put(&mut self, r: u32, c: u32, v: Value) {
         if !v.is_empty() {
+            let (rows, cols) = (self.rows.max(r.saturating_add(1)), self.cols.max(c.saturating_add(1)));
+            if self.too_large || u64::from(rows) * u64::from(cols) > MAX_OUTPUT_CELLS {
+                self.too_large = true;
+                return;
+            }
+            (self.rows, self.cols) = (rows, cols);
             self.cells.insert((r, c), v);
         }
     }
@@ -296,9 +310,7 @@ impl Grid {
     }
     /// (rows, cols) spanned.
     fn extent(&self) -> (u32, u32) {
-        let rows = self.cells.keys().map(|(r, _)| r + 1).max().unwrap_or(0);
-        let cols = self.cells.keys().map(|(_, c)| c + 1).max().unwrap_or(0);
-        (rows, cols)
+        (self.rows, self.cols)
     }
 }
 
@@ -1749,7 +1761,7 @@ fn sampling(s: &Session, p: &Json, seed: Option<u64>) -> Result<Grid> {
 fn write_report(s: &mut Session, p: &Json, tool: &str, g: Grid) -> Result<Json> {
     let (rows, cols) = g.extent();
     let (rows, cols) = (rows.max(1), cols.max(1));
-    if u64::from(rows) * u64::from(cols) > MAX_OUTPUT_CELLS {
+    if g.too_large || u64::from(rows) * u64::from(cols) > MAX_OUTPUT_CELLS {
         return Err(bad(CMD, "the report is too large"));
     }
     let d = s.doc()?;
@@ -1914,6 +1926,28 @@ mod tests {
         x
     }
 
+    #[test]
+    fn a_report_stops_growing_past_the_output_limit() {
+        // Entries past the limit are not kept, and the report is refused.
+        let mut g = super::Grid::default();
+        g.num(1999, 1999, 1.0);
+        assert!(!g.too_large);
+        g.num(0, 2000, 1.0);
+        assert!(g.too_large);
+        assert_eq!(g.cells.len(), 1);
+        assert_eq!(g.extent(), (2000, 2000));
+        // Row-grouped statistics of a tall, almost empty column: one variable per row would make
+        // millions of report entries; the report is refused instead of built.
+        let mut s = s();
+        s.execute("range.setValues", json!({"range": "A1", "values": [[1]]})).unwrap();
+        s.execute("range.setValues", json!({"range": "A1000000", "values": [[2]]})).unwrap();
+        let err = s
+            .execute("data.analysisToolPak", json!({"tool": "descriptive", "range": "A1:A1000000", "groupedBy": "rows", "output": "C1"}))
+            .expect_err("report too large");
+        assert!(err.to_string().contains("too large"), "{err}");
+        assert_eq!(v(&s, "C1"), Value::Empty);
+    }
+
     #[test]
     fn forecast_standard_errors_match_the_full_window_rescan() {
         // #1043: the running sum must give what re-adding every window gave, gaps included.

crates/engine/src/cmd/forecast.rs

@@ -36,20 +36,6 @@ fn max_periods(history: usize) -> u32 {
     u32::try_from(MAX_WORK / h).unwrap_or(u32::MAX).clamp(1, MAX_PERIODS)
 }
 
-/// Most forecast rows when the model is fit to the first `fit` of `history` rows. With a Forecast
-/// Start inside the history, every row after it is forecast too (a hindcast row holds the same
-/// ETS formulas, each refitting the model over the `fit` rows), so those rows count against
-/// [`MAX_WORK`] before any forecast row does. `None` when the hindcast alone exceeds it.
-fn max_periods_from(history: usize, fit: usize) -> Option<u32> {
-    if fit >= history {
-        return Some(max_periods(history));
-    }
-    let f = u64::try_from(fit).unwrap_or(u64::MAX).max(1);
-    let hindcast = u64::try_from(history - fit).unwrap_or(u64::MAX);
-    let rest = (MAX_WORK / f).checked_sub(hindcast).filter(|r| *r >= 1)?;
-    Some(u32::try_from(rest).unwrap_or(u32::MAX).min(MAX_PERIODS))
-}
-
 pub fn specs() -> Vec<CommandSpec> {
     vec![cmd!(
         "data.forecastSheet",
@@ -271,15 +257,13 @@ fn forecast_sheet(s: &mut Session, p: &Json) -> Result<Json> {
             }
         }
     };
-    let cap = max_periods_from(rows.len(), fit).ok_or_else(|| {
-        EngineError::Other("The forecast start is too early for this much history: choose a later forecast start or less history.".into())
-    })?;
+    let cap = max_periods(rows.len());
     let periods = match end {
         Some(end) => steps_to(&timeline, end, cap)?,
         None => match number(p, "periods")? {
             Some(n) if n >= 1.0 && n.ceil() <= f64::from(cap) => n.ceil() as u32,
             Some(_) => return Err(bad(CMD, format!("`periods` is from 1 to {cap} for {} rows of history", rows.len()))),
-            None => default_periods(rows.len()).min(cap),
+            None => default_periods(rows.len()),
         },
     };
     let future: Vec<f64> =
@@ -546,32 +530,6 @@ mod tests {
         assert_eq!(s.doc().unwrap().wb.sheets.len(), sheets - 1);
     }
 
-    #[test]
-    fn hindcast_rows_count_against_the_work_limit() {
-        use super::{MAX_WORK, max_periods, max_periods_from};
-        assert_eq!(max_periods_from(1_300, 1_300), Some(max_periods(1_300)));
-        // 2,000 rows fit to the first 1,899: 101 hindcast rows, then 162 forecast rows.
-        assert_eq!(max_periods_from(2_000, 1_899), Some(162));
-        // Fit to the first 1,000: the 1,000 hindcast rows alone are twice the limit.
-        assert_eq!(max_periods_from(2_000, 1_000), None);
-        for (h, f) in [(2_000usize, 1_899usize), (10_000, 9_990), (100, 2), (60, 50)] {
-            if let Some(p) = max_periods_from(h, f) {
-                assert!((u64::from(p) + (h - f) as u64) * f as u64 <= MAX_WORK, "{h} {f}");
-            }
-        }
-        let mut s = Session::new();
-        s.new_workbook();
-        let mut rows = vec![json!(["t", "y"])];
-        rows.extend((1..=2_000).map(|t| json!([t, (t % 7) as f64 + t as f64 * 0.5])));
-        s.execute("range.setValues", json!({"range": "A1", "values": rows})).unwrap();
-        let sheets = s.doc().unwrap().wb.sheets.len();
-        let err = s.execute("data.forecastSheet", json!({"range": "A1:B2001", "forecastStart": 1_001})).expect_err("hindcast too long");
-        assert!(err.to_string().contains("forecast start is too early"), "{err}");
-        let err = s.execute("data.forecastSheet", json!({"range": "A1:B2001", "forecastStart": 1_900, "periods": 163})).expect_err("past the cap");
-        assert!(err.to_string().contains("from 1 to 162"), "{err}");
-        assert_eq!(s.doc().unwrap().wb.sheets.len(), sheets);
-    }
-
     #[test]
     fn history_and_periods_are_capped() {
         use super::{MAX_HISTORY, MAX_PERIODS, MAX_WORK, default_periods, max_periods};