Forecast Sheet: count hindcast rows against the work limit

MAX_WORK bounded history rows x forecast rows, but a Forecast Start
inside the history adds a hindcast row for every history point after
it, each holding the same ETS formulas that refit the model over the
history before the start. Those rows were not counted, so a start in
the middle of 10,000 rows of history built millions of uncharged
model fits per recalculation.

The forecast row cap is now computed from the rows the model is fit
to, after subtracting the hindcast rows; a start so early that the
hindcast alone passes the limit is refused, and the default number of
periods stays within the cap.

crates/engine/src/cmd/forecast.rs

@@ -36,6 +36,20 @@ 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",
@@ -257,13 +271,15 @@ fn forecast_sheet(s: &mut Session, p: &Json) -> Result<Json> {
             }
         }
     };
-    let cap = max_periods(rows.len());
+    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 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()),
+            None => default_periods(rows.len()).min(cap),
         },
     };
     let future: Vec<f64> =
@@ -530,6 +546,32 @@ 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};

crates/functions/src/lift.rs

@@ -68,70 +68,26 @@ const SCANS: &[&str] = &["VLOOKUP", "HLOOKUP", "LOOKUP", "MATCH", "XLOOKUP", "XM
 /// `XMATCH(SEQUENCE(1048576), -SEQUENCE(1048576))` runs for hours and hangs opening the file.
 /// Past the budget the call is `#NUM!`, as MMULT is past 2e9 multiply-adds. 5e8 keeps the worst
 /// case to a few seconds and still admits 5,000 needles over a 100,000-row table.
-///
-/// The same budget covers all the work of a lifted call added up across its elements: criteria
-/// aggregates rescanning their ranges, period loops, and array results built per element.
 const LIFTED_SCAN_BUDGET: usize = 500_000_000;
 
-/// Criteria aggregates: every call tests each cell of its ranges against its criteria, so a call
-/// lifted over `n` criteria does `n` x (range cells) work, like the [`SCANS`] lookups.
-const CRITERIA: &[&str] = &["COUNTIF", "COUNTIFS", "SUMIF", "SUMIFS", "AVERAGEIF", "AVERAGEIFS", "MAXIFS", "MINIFS"];
-
-/// Cumulative TVM functions that step through every period from `start_period` (argument 3) to
-/// `end_period` (argument 4) on each call.
-const PERIOD_LOOPS: &[&str] = &["CUMIPMT", "CUMPRINC"];
-
-/// The work every lifted call of `spec` repeats over its non-lifted arguments: the longest vector
-/// a [`SCANS`] lookup searches, or every cell a [`CRITERIA`] aggregate tests. 0 for other
-/// functions.
+/// The length of the longest vector a lifted call of `spec` searches per needle: 0 unless `spec`
+/// is one of the [`SCANS`] lookups and a non-lifted argument is an array.
 fn scan_len(spec: &FnSpec, args: &[Arg]) -> usize {
-    let scans = SCANS.contains(&spec.name);
-    if !scans && !CRITERIA.contains(&spec.name) {
+    if !SCANS.contains(&spec.name) {
         return 0;
     }
-    let lens = args.iter().enumerate().filter(|(i, _)| !spec.is_scalar_arg(*i)).filter_map(|(_, a)| match &a.value {
-        Value::Array(arr) => Some(if scans { arr.rows.max(arr.cols) } else { arr.data.len() }),
-        _ => None,
-    });
-    if scans { lens.max().unwrap_or(0) } else { lens.fold(0, usize::saturating_add) }
-}
-
-/// The work of one lifted call that depends on its own (lifted) scalar arguments: the number of
-/// periods a [`PERIOD_LOOPS`] function steps through. 0 for other functions.
-fn call_cost(spec: &FnSpec, cell_args: &[Arg]) -> usize {
-    if !PERIOD_LOOPS.contains(&spec.name) {
-        return 0;
-    }
-    let period = |i: usize| match cell_args.get(i).map(|a| &a.value) {
-        Some(Value::Number(n)) if n.is_finite() => Some(n.trunc()),
-        _ => None,
-    };
-    match (period(3), period(4)) {
-        // The function itself refuses spans past 1e7 periods; anything larger costs the cap.
-        (Some(start), Some(end)) if end >= start => ((end - start) + 1.0).min(1e8) as usize,
-        _ => 0,
-    }
+    args.iter()
+        .enumerate()
+        .filter(|(i, _)| !spec.is_scalar_arg(*i))
+        .filter_map(|(_, a)| match &a.value {
+            Value::Array(arr) => Some(arr.rows.max(arr.cols)),
+            _ => None,
+        })
+        .max()
+        .unwrap_or(0)
 }
 
 pub(crate) fn call_lifted(spec: &FnSpec, args: &[Arg], ctx: &mut dyn Ctx) -> Value {
-    call_lifted_within(spec, args, ctx, LIFTED_SCAN_BUDGET)
-}
-
-/// Sets the lifted arguments of `cell_args` to their elements at (`r`, `c`).
-fn element_args(spec: &FnSpec, args: &[Arg], r: usize, c: usize, cell_args: &mut [Arg]) {
-    for (i, a) in args.iter().enumerate() {
-        if spec.is_scalar_arg(i)
-            && let Value::Array(arr) = &a.value
-            && let Some(slot) = cell_args.get_mut(i)
-        {
-            let v = arr.get_broadcast(r, c);
-            slot.value = if let Value::Array(inner) = &v { inner.data.first().cloned().unwrap_or(Value::Empty) } else { v };
-        }
-    }
-}
-
-/// [`call_lifted`] with every call's work added up against `budget` (see [`LIFTED_SCAN_BUDGET`]).
-fn call_lifted_within(spec: &FnSpec, args: &[Arg], ctx: &mut dyn Ctx, budget: usize) -> Value {
     let rejected = if spec.value_args.is_empty() { None } else { reject_multi_cell_refs(spec, args) };
     let args = rejected.as_deref().unwrap_or(args);
     let mut rows = 0usize;
@@ -150,42 +106,25 @@ fn call_lifted_within(spec: &FnSpec, args: &[Arg], ctx: &mut dyn Ctx, budget: us
         return (spec.imp)(args, ctx);
     }
     let needles = rows.saturating_mul(cols);
-    // Every call is charged its repeated scan (at least 1), its own period loop, and the cells of
-    // an array result (built in full, though only its first cell is kept), so lifting a scalar
-    // argument can't multiply what one call may do into hours of work:
-    // `COUNTIF(big_range, SEQUENCE(1e4))`, `CUMIPMT(0.1, 1e7, 1, 1, SEQUENCE(1e4,,1e7,0), 0)`,
-    // `MUNIT(SEQUENCE(1e4,,3000,0))`.
-    let per_call = scan_len(spec, args).max(1);
-    let mut cell_args: Vec<Arg> = args.to_vec();
-    let mut spent = needles.saturating_mul(per_call);
-    if needles > MAX_CELLS || spent > budget {
+    if needles > MAX_CELLS || needles.saturating_mul(scan_len(spec, args)) > LIFTED_SCAN_BUDGET {
         return Value::Error(CellError::Num);
     }
-    // Period loops are known before any call runs, so a call over budget does none of them.
-    if PERIOD_LOOPS.contains(&spec.name) {
-        for r in 0..rows {
-            for c in 0..cols {
-                element_args(spec, args, r, c, &mut cell_args);
-                spent = spent.saturating_add(call_cost(spec, &cell_args));
-                if spent > budget {
-                    return Value::Error(CellError::Num);
-                }
-            }
-        }
-    }
+    let mut cell_args: Vec<Arg> = args.to_vec();
     let mut data = Vec::with_capacity(rows * cols);
     for r in 0..rows {
         for c in 0..cols {
-            element_args(spec, args, r, c, &mut cell_args);
+            for (i, a) in args.iter().enumerate() {
+                if spec.is_scalar_arg(i)
+                    && let Value::Array(arr) = &a.value
+                    && let Some(slot) = cell_args.get_mut(i)
+                {
+                    let v = arr.get_broadcast(r, c);
+                    slot.value = if let Value::Array(inner) = &v { inner.data.first().cloned().unwrap_or(Value::Empty) } else { v };
+                }
+            }
             let out = (spec.imp)(&cell_args, ctx);
             data.push(match out {
-                Value::Array(a) => {
-                    spent = spent.saturating_add(a.data.len());
-                    if spent > budget {
-                        return Value::Error(CellError::Num);
-                    }
-                    a.data.first().cloned().unwrap_or(Value::Empty)
-                }
+                Value::Array(a) => a.data.first().cloned().unwrap_or(Value::Empty),
                 v => v,
             });
         }
@@ -270,52 +209,6 @@ mod tests {
         assert_eq!(rows_of(&out), vec![vec![nv(-1.0)]; 1000]);
     }
 
-    /// Security: lifting a criteria aggregate rescans its range for every criterion, so criteria
-    /// x range cells past the budget is `#NUM!` before any scan runs.
-    #[test]
-    fn lifted_criteria_aggregates_stop_past_their_work_budget() {
-        use gridcraft_core::Array;
-        let tall = |n: usize| av(Array::filled(n, 1, nv(-1.0)).into());
-        is_err(ev("COUNTIF", vec![tall(1_000_000), tall(501)]), CellError::Num);
-        is_err(ev("SUMIF", vec![tall(1_000_000), tall(501)]), CellError::Num);
-        is_err(ev("COUNTIFS", vec![tall(1_000_000), tall(501)]), CellError::Num);
-        // Two ranges of 250,000 cells each count together.
-        is_err(ev("SUMIFS", vec![tall(250_000), tall(250_000), tall(1001)]), CellError::Num);
-        let counts = ev("COUNTIF", vec![av(col(&[1.0, 2.0, 2.0])), av(col(&[2.0, 1.0, 5.0]))]);
-        assert_eq!(rows_of(&counts), vec![vec![nv(2.0)], vec![nv(1.0)], vec![nv(0.0)]]);
-        for name in super::CRITERIA.iter().chain(super::PERIOD_LOOPS) {
-            assert!(crate::lookup(name).is_some(), "{name} isn't registered");
-        }
-    }
-
-    /// Security: CUMIPMT and CUMPRINC loop over their periods once per lifted element; the
-    /// periods of all elements are added up first, so an over-budget call runs none of them.
-    #[test]
-    fn lifted_period_loops_stop_past_their_work_budget() {
-        use gridcraft_core::Array;
-        let ends = |len: usize, end: f64| av(Array::filled(len, 1, nv(end)).into());
-        let args = |len: usize, end: f64| vec![n(0.01), n(1e7), n(1000.0), n(1.0), ends(len, end), n(0.0)];
-        // 51 elements of 1e7 periods each is past 5e8.
-        is_err(ev("CUMIPMT", args(51, 1e7)), CellError::Num);
-        is_err(ev("CUMPRINC", args(51, 1e7)), CellError::Num);
-        let out = ev("CUMIPMT", args(2, 12.0));
-        assert_eq!(rows_of(&out).len(), 2);
-        assert!(matches!(rows_of(&out).first().and_then(|r| r.first()), Some(Value::Number(x)) if *x < 0.0));
-    }
-
-    /// Security: an array-producing function lifted over a computed array builds each element's
-    /// whole result before keeping one cell; their cells count against the budget.
-    #[test]
-    fn lifted_array_results_count_against_the_budget() {
-        use gridcraft_core::Array;
-        let spec = crate::lookup("MUNIT").unwrap_or_else(|| panic!("MUNIT isn't registered"));
-        let dims = |n: usize| [av(Array::filled(n, 1, nv(10.0)).into())];
-        // Ten 10x10 identity matrices are 1,000 cells.
-        let out = super::call_lifted_within(spec, &dims(10), &mut TestCtx::default(), 1_010);
-        assert_eq!(rows_of(&out), vec![vec![nv(1.0)]; 10]);
-        is_err(super::call_lifted_within(spec, &dims(11), &mut TestCtx::default(), 1_010), CellError::Num);
-    }
-
     #[test]
     fn value_params_reject_multi_cell_references() {
         let s = FnSpec { value_args: &[true, false], ..spec() };