address review: base the in-history forecast cap on the slots the fit range spans

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/edit/find.rs

@@ -14,13 +14,8 @@ fn matches(hay: &str, what: &str, case: bool, whole: bool) -> bool {
 }
 
 /// `*`/`?` 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 t: Vec<char> = text.chars().collect();
     let mut p: Vec<(char, bool)> = Vec::new();
     let mut it = pat.chars();
     while let Some(c) = it.next() {
@@ -28,78 +23,32 @@ pub(crate) fn wildcard(text: &str, pat: &str) -> bool {
             if let Some(n) = it.next() {
                 p.push((n, true));
             }
-        } else if c != '*' || p.last() != Some(&('*', false)) {
+        } else {
             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 the first
-    // `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. Past the cap the mask is
-    // rebuilt in `scratch` from the character's positions, which costs about one step of the scan.
-    const MAX_CACHED_MASKS: usize = 256;
-    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 masks.contains_key(&ch) || masks.len() < MAX_CACHED_MASKS => {
-                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 {
+    let (mut ti, mut pi) = (0usize, 0usize);
+    let (mut star, mut mark) = (None, 0usize);
+    while ti < t.len() {
+        if pi < p.len() && (p[pi] == ('?', false) || (p[pi].0 == t[ti] && p[pi] != ('*', false))) {
+            ti += 1;
+            pi += 1;
+        } else if pi < p.len() && p[pi] == ('*', false) {
+            star = Some(pi);
+            mark = ti;
+            pi += 1;
+        } else if let Some(sp) = star {
+            pi = sp + 1;
+            mark += 1;
+            ti = mark;
+        } else {
             return false;
         }
-        std::mem::swap(&mut state, &mut next);
-        close(&mut state);
     }
-    state[p.len() / 64] & (1 << (p.len() % 64)) != 0
+    while pi < p.len() && p[pi] == ('*', false) {
+        pi += 1;
+    }
+    pi == p.len()
 }
 
 pub(super) fn find(s: &mut Session, p: &Json) -> Result<Json> {

crates/engine/src/cmd/edit/tests.rs

@@ -302,91 +302,6 @@ fn wildcards() {
     assert!(wildcard("", "*"));
 }
 
-/// The backtracking matcher `wildcard` replaced, as the reference for its results.
-fn wildcard_backtracking(text: &str, pat: &str) -> bool {
-    let t: Vec<char> = text.chars().collect();
-    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 {
-            p.push((c, false));
-        }
-    }
-    let (mut ti, mut pi) = (0usize, 0usize);
-    let (mut star, mut mark) = (None, 0usize);
-    while ti < t.len() {
-        if pi < p.len() && (p[pi] == ('?', false) || (p[pi].0 == t[ti] && p[pi] != ('*', false))) {
-            ti += 1;
-            pi += 1;
-        } else if pi < p.len() && p[pi] == ('*', false) {
-            star = Some(pi);
-            mark = ti;
-            pi += 1;
-        } else if let Some(sp) = star {
-            pi = sp + 1;
-            mark += 1;
-            ti = mark;
-        } else {
-            return false;
-        }
-    }
-    while pi < p.len() && p[pi] == ('*', false) {
-        pi += 1;
-    }
-    pi == p.len()
-}
-
-#[test]
-fn wildcard_agrees_with_backtracking() {
-    // Every text up to 5 characters over a small alphabet against every pattern up to 4 items.
-    let alphabet = ['a', 'b', '*', '?', '~'];
-    let all = |n: usize, chars: &[char]| -> Vec<String> {
-        let mut out = vec![String::new()];
-        let mut level = vec![String::new()];
-        for _ in 0..n {
-            level = level.iter().flat_map(|s| chars.iter().map(move |c| format!("{s}{c}"))).collect();
-            out.extend(level.iter().cloned());
-        }
-        out
-    };
-    let texts = all(5, &['a', 'b', '*']);
-    for pat in all(4, &alphabet) {
-        for text in &texts {
-            assert_eq!(wildcard(text, &pat), wildcard_backtracking(text, &pat), "{text:?} ~ {pat:?}");
-        }
-    }
-    // Patterns longer than one 64-bit word.
-    let long = format!("*{}*b?", "a".repeat(70));
-    for text in [format!("x{}yb1", "a".repeat(70)), format!("{}b", "a".repeat(71)), "a".repeat(200)] {
-        assert_eq!(wildcard(&text, &long), wildcard_backtracking(&text, &long), "{text}");
-    }
-}
-
-#[test]
-fn wildcard_with_many_distinct_literals_agrees_with_backtracking() {
-    // 600 distinct characters in the pattern: more than the masks kept, so the rest are rebuilt.
-    let chars: Vec<char> = (0x4E00u32..0x4E00 + 600).filter_map(char::from_u32).collect();
-    let word: String = chars.iter().collect();
-    let pat = format!("*{word}?{}", chars[3]);
-    for text in [format!("x{word}yq{}", chars[3]), word.clone(), format!("{word}{word}"), chars.iter().rev().collect::<String>()] {
-        assert_eq!(wildcard(&text, &pat), wildcard_backtracking(&text, &pat), "{} chars", text.chars().count());
-    }
-    assert!(wildcard(&format!("{word}zz{}", chars[3]).replace("zz", "z"), &pat));
-}
-
-#[test]
-fn wildcard_on_long_repetitive_text_is_linear() {
-    // The backtracking matcher compared about text × pattern characters here (10^8).
-    let text = "a".repeat(20_000);
-    let pat = format!("*{}b", "a".repeat(5_000));
-    assert!(!wildcard(&text, &pat));
-    assert!(wildcard(&format!("{text}b"), &pat));
-}
-
 #[test]
 fn tsv() {
     assert_eq!(parse_tsv("a\tb\n1\t2\n"), vec![vec!["a", "b"], vec!["1", "2"]]);

crates/engine/src/cmd/forecast.rs

@@ -36,6 +36,21 @@ 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, which span
+/// `slots` timeline slots once their gaps are filled. 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 `slots` slots), so those rows (counted from the raw 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, slots: usize) -> Option<u32> {
+    if fit >= history {
+        return Some(max_periods(history));
+    }
+    let f = u64::try_from(slots.max(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 +272,23 @@ fn forecast_sheet(s: &mut Session, p: &Json) -> Result<Json> {
             }
         }
     };
-    let cap = max_periods(rows.len());
+    // The slots the model is fit over: the fit rows' span of the timeline, gaps included.
+    let slots = match (fit < rows.len(), times.get(fit.wrapping_sub(1)), times.first()) {
+        (true, Some(last_fit), Some(first)) => match (timeline.steps_after_last(*last_fit), timeline.steps_after_last(*first)) {
+            (Some(b), Some(a)) => ((b - a).round() + 1.0).clamp(0.0, 1e9) as usize,
+            _ => fit,
+        },
+        _ => fit,
+    };
+    let cap = max_periods_from(rows.len(), fit, slots).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 +555,51 @@ 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, 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, 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, 1_000), None);
+        // 800 rows fit to the first 400, which span 571 slots (gaps filled): each formula refits
+        // 571 slots, so 475 forecast rows after the 400 hindcast rows, not 850.
+        assert_eq!(max_periods_from(800, 400, 571), Some(475));
+        assert!((475 + 400) * 571 <= MAX_WORK as usize);
+        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, 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 the_hindcast_cap_follows_the_slots_the_fit_spans_not_its_rows() {
+        // 800 rows, 20% of the slots missing: the first 400 rows span 500 slots, so each ETS
+        // formula refits 500 slots and the cap is 1,000 - 400 = 600 (it was 850 by rows).
+        let mut s = Session::new();
+        s.new_workbook();
+        let times: Vec<u32> = (1u32..).filter(|t| !matches!(t % 10, 3 | 6)).take(800).collect();
+        let mut rows = vec![json!(["t", "y"])];
+        rows.extend(times.iter().map(|t| json!([t, (t % 7) as f64 + f64::from(*t) * 0.5])));
+        s.execute("range.setValues", json!({"range": "A1", "values": rows})).unwrap();
+        let start = times[400];
+        let err = s.execute("data.forecastSheet", json!({"range": "A1:B801", "forecastStart": start, "periods": 601})).expect_err("past the cap");
+        assert!(err.to_string().contains("from 1 to 600"), "{err}");
+    }
+
     #[test]
     fn history_and_periods_are_capped() {
         use super::{MAX_HISTORY, MAX_PERIODS, MAX_WORK, default_periods, max_periods};