address review: stop collecting JSON keys at the column limit and reject oversized row counts before building rows

data.getData and data.fromTextCsv built every row densely before
writing it: JSON records were padded to the union of all keys (found
with a quadratic Vec::contains scan), and CSV cells were expanded over
the whole used rectangle. A few sparse records or one far-away CSV
cell therefore allocated billions of slots.

The importer now collects JSON keys with a HashSet, refuses more keys
than a sheet has columns, and checks the projected rows x columns
against MAX_IMPORT_CELLS (10,000,000) before building any row.

crates/engine/src/cmd/extra/data.rs

@@ -42,6 +42,15 @@ pub(super) fn table_resize(s: &mut Session, p: &Json) -> Result<Json> {
     })
 }
 
+/// Most cells (rows × columns, blanks included) Get Data imports. The rows are built densely
+/// before they are written, so a few sparse records or one far-away CSV cell must not expand
+/// into a rectangle of billions of slots.
+const MAX_IMPORT_CELLS: u64 = 10_000_000;
+
+fn too_many_cells() -> EngineError {
+    EngineError::Other(format!("The data is too large to import ({MAX_IMPORT_CELLS} cells at most)."))
+}
+
 pub(super) fn from_csv(s: &mut Session, p: &Json) -> Result<Json> {
     let bytes = if let Some(t) = str_param(p, "text") {
         t.as_bytes().to_vec()
@@ -57,15 +66,27 @@ pub(super) fn from_csv(s: &mut Session, p: &Json) -> Result<Json> {
         if text.trim_start().starts_with('[') {
             let arr: Vec<Json> = serde_json::from_str(&text).map_err(|e| bad("data.getData", e.to_string()))?;
             let mut keys: Vec<String> = Vec::new();
+            let mut seen: std::collections::HashSet<&str> = std::collections::HashSet::new();
             for o in &arr {
                 if let Some(m) = o.as_object() {
                     for k in m.keys() {
-                        if !keys.contains(k) {
+                        if !seen.contains(k.as_str()) {
+                            // Stop collecting at the column limit.
+                            if keys.len() >= gridcraft_core::MAX_COLS as usize {
+                                return Err(EngineError::Other("The data has more fields than a sheet has columns.".into()));
+                            }
+                            seen.insert(k.as_str());
                             keys.push(k.clone());
                         }
                     }
                 }
             }
+            if arr.len() as u64 + 1 > u64::from(gridcraft_core::MAX_ROWS) {
+                return Err(EngineError::Other("The data has more rows than a sheet has.".into()));
+            }
+            if (arr.len() as u64 + 1).saturating_mul(keys.len().max(1) as u64) > MAX_IMPORT_CELLS {
+                return Err(too_many_cells());
+            }
             let mut out = vec![keys.iter().map(|k| json!(k)).collect::<Vec<_>>()];
             for o in &arr {
                 out.push(keys.iter().map(|k| o.get(k).cloned().unwrap_or(Json::Null)).collect());
@@ -79,6 +100,9 @@ pub(super) fn from_csv(s: &mut Session, p: &Json) -> Result<Json> {
             let wb = gridcraft_xlsx::read_csv(&bytes, &opts).map_err(|e| EngineError::Other(e.to_string()))?;
             let sh = wb.sheet(0).ok_or(EngineError::NoDocument)?;
             let Some(u) = sh.used_range() else { return Err(EngineError::Other("The file is empty.".into())) };
+            if u.count() > MAX_IMPORT_CELLS {
+                return Err(too_many_cells());
+            }
             (u.start.row..=u.end.row)
                 .map(|r| {
                     (u.start.col..=u.end.col)
@@ -129,3 +153,35 @@ pub(super) fn queries(s: &mut Session, _: &Json) -> Result<Json> {
             .collect(),
     ))
 }
+
+#[cfg(test)]
+mod tests {
+    use serde_json::json;
+
+    use crate::Session;
+
+    fn s() -> Session {
+        let mut s = Session::new();
+        s.new_workbook();
+        s
+    }
+
+    #[test]
+    fn sparse_imports_are_refused_before_their_rows_are_built() {
+        let mut s = s();
+        let sheets = s.doc().unwrap().wb.sheets.len();
+        // 5,000 records with one field each: 5,001 × 5,000 slots once every record gets every field.
+        let records: Vec<_> = (0..5_000).map(|i| json!({ format!("k{i}"): i })).collect();
+        let text = serde_json::to_string(&records).unwrap();
+        let err = s.execute("data.getData", json!({"text": text})).expect_err("too many cells");
+        assert!(err.to_string().contains("too large"), "{err}");
+        // A CSV whose last line reaches 16,001 columns, 1,000 lines down.
+        let text = format!("1{}{}x", "\n".repeat(999), ",".repeat(16_000));
+        let err = s.execute("data.fromTextCsv", json!({"text": text})).expect_err("too many cells");
+        assert!(err.to_string().contains("too large"), "{err}");
+        assert_eq!(s.doc().unwrap().wb.sheets.len(), sheets);
+        // Small imports still work.
+        let out = s.execute("data.getData", json!({"text": r#"[{"a": 1}, {"b": 2}]"#})).unwrap();
+        assert_eq!((out["rows"].as_u64(), out["cols"].as_u64()), (Some(3), Some(2)), "{out}");
+    }
+}

crates/engine/src/tests.rs

@@ -1312,6 +1312,18 @@ fn scripts_leave_file_access_working_after_they_run() {
     let _ = std::fs::remove_dir_all(&dir);
 }
 
+#[test]
+fn get_data_refuses_json_with_too_many_fields_or_rows_before_building_rows() {
+    let mut s = s();
+    let wide = format!("[{}]", (0..=gridcraft_core::MAX_COLS).map(|i| format!("{{\"k{i}\":1}}")).collect::<Vec<_>>().join(","));
+    let err = s.execute("data.fromTextCsv", json!({"text": wide})).unwrap_err().to_string();
+    assert!(err.contains("more fields"), "{err}");
+    // MAX_ROWS objects plus the header row are one too many.
+    let tall = format!("[{}]", vec!["{}"; gridcraft_core::MAX_ROWS as usize].join(","));
+    let err = s.execute("data.fromTextCsv", json!({"text": tall})).unwrap_err().to_string();
+    assert!(err.contains("more rows"), "{err}");
+}
+
 #[test]
 fn scripts_cannot_reach_outside_the_workbook_even_when_trusted() {
     let dir = std::env::temp_dir().join(format!("gridcraft-script-deny-{}", std::process::id()));

crates/functions/src/lift.rs

@@ -3,7 +3,7 @@
 
 use gridcraft_core::{Array, CellError, Value};
 
-use crate::util::{MAX_CELLS, num};
+use crate::util::MAX_CELLS;
 use crate::{Arg, Ctx, FnSpec};
 
 /// Value-parameter masks (see [`FnSpec::value_args`]), observed in Excel 365: a reference to more
@@ -68,68 +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;
-    }
-    // The function's own coercion (text like "10000000" counts), so no loop goes uncharged.
-    let period = |i: usize| num(cell_args, i).ok().filter(|n| n.is_finite()).map(f64::trunc);
-    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;
@@ -148,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,
             });
         }
@@ -268,55 +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);
-        // Numeric text is coerced by the function, so its periods are charged the same.
-        let text_ends = av(Array::filled(51, 1, Value::text("10000000")).into());
-        is_err(ev("CUMIPMT", vec![n(0.01), n(1e7), n(1000.0), n(1.0), text_ends, n(0.0)]), 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() };