fix(geom): report a spent containment budget instead of partial islands

crates/constraints/src/auto.rs

@@ -232,6 +232,10 @@ pub fn infer_placed(d: &Drawing, placed: &[Handle], others: &[Handle], o: &Infer
     let mut extra = Vec::new();
     let mut on = Vec::new();
     for (rp, p) in g.points.iter().filter(|(r, _)| placed.contains(&r.handle)) {
+        // Nothing is added once the candidates are full, so the points left need no search.
+        if extra.len() + on.len() + out.len() >= MAX_CANDIDATES {
+            break;
+        }
         if out.iter().any(|c| c.kind == ConstraintKind::Coincident && c.refs.contains(rp)) {
             continue;
         }
@@ -267,20 +271,22 @@ pub fn infer_placed(d: &Drawing, placed: &[Handle], others: &[Handle], o: &Infer
     // Perpendicular lines meeting in a T (a perpendicular snap onto the middle of a line).
     let atol = if o.angle_tolerance.is_finite() { o.angle_tolerance.clamp(0.0, 45.0).to_radians() } else { 0.0 };
     let allow_per = o.types.is_empty() || o.types.iter().any(|t| t.eq_ignore_ascii_case(ConstraintKind::Perpendicular.name()));
-    for (r1, a1, b1) in g.lines.iter().filter(|(r, _, _)| placed.contains(&r.handle)) {
+    'per: for (r1, a1, b1) in g.lines.iter().filter(|(r, _, _)| allow_per && placed.contains(&r.handle)) {
         for (r2, a2, b2) in g.lines.iter().filter(|(r, _, _)| r.handle != r1.handle) {
+            // Full: nothing more can be added, so the pairs left need no geometry or duplicate search.
+            if out.len() >= MAX_CANDIDATES {
+                break 'per;
+            }
             let (l1, l2) = (Line::new(*a1, *b1), Line::new(*a2, *b2));
             let touches = |l: &Line, p: Vec2| l.dist(p) <= tol && (0.0..=1.0).contains(&l.param_of(p));
             let tee = [*a1, *b1].iter().any(|p| touches(&l2, *p)) || [*a2, *b2].iter().any(|p| touches(&l1, *p));
             let ang = ang_between(*b1 - *a1, *b2 - *a2);
-            let dup = out.iter().any(|c| c.kind == ConstraintKind::Perpendicular && c.refs.contains(r1) && c.refs.contains(r2));
-            if allow_per
-                && tee
-                && !dup
+            // The duplicate search scans every candidate, so it comes after the cheap tests.
+            if tee
                 && (std::f64::consts::FRAC_PI_2 - ang).abs() <= atol
                 && l1.len() > tol
                 && l2.len() > tol
-                && out.len() < MAX_CANDIDATES
+                && !out.iter().any(|c| c.kind == ConstraintKind::Perpendicular && c.refs.contains(r1) && c.refs.contains(r2))
             {
                 out.push(Constraint { id: 0, kind: ConstraintKind::Perpendicular, refs: vec![*r1, *r2], name: String::new(), expr: String::new() });
             }

crates/engine/src/lisp.rs

@@ -123,12 +123,6 @@ pub struct LispState {
     acad_loaded: bool,
     /// Memory caps (lowered by tests).
     pub(crate) limits: Limits,
-    /// Interpreter steps all synchronous callbacks have run, nested ones included. A callback's
-    /// allowance counts what ran since it started, so the callbacks it calls spend its steps.
-    pub(crate) callback_used: u64,
-    /// The `callback_used` value the callback running now (and so every one it calls) must not
-    /// pass: the lowest of its own and its callers' allowances.
-    pub(crate) callback_ceiling: Option<u64>,
 }
 
 /// What U and REDO inside the running routine take back: the commands it ran, each as the drawing

crates/engine/src/lisp/builtins/strings.rs

@@ -1,5 +1,5 @@
 use super::args::{R, arity, int, list_arg, string};
-use super::{LispError, OsStr, Value, charge_bytes, check_string_len, read, to_text};
+use super::{LispError, OsStr, Value, check_string_len, read, to_text};
 
 // ---------------- strings ----------------
 
@@ -114,13 +114,7 @@ pub(super) fn read_fn(a: &[Value]) -> R {
     arity(a, 0, 1)?;
     match a.first() {
         None | Some(Value::Nil) => Ok(Value::Nil),
-        Some(v) => {
-            // The strings in the list it makes are new, each as long as its text at most: the
-            // text is charged, though a list result isn't inspected by `charge_result`.
-            let text = string(v)?;
-            charge_bytes(text.len())?;
-            read::read_one(&text)
-        }
+        Some(v) => read::read_one(&string(v)?),
     }
 }
 

crates/engine/src/lisp/drawing.rs

@@ -179,12 +179,7 @@ fn to_json_bounded(v: &Value, depth: usize, budget: &mut u64) -> Option<serde_js
         Value::Nil => serde_json::Value::Null,
         Value::Int(i) => serde_json::json!(i),
         Value::Real(r) => serde_json::json!(r),
-        Value::Str(s) => {
-            // A string is copied whole each time it occurs: it spends the allowance by its length
-            // (one unit per 16 bytes, so about 32 MB in all), shared or not.
-            *budget = budget.checked_sub(s.len() as u64 / 16)?;
-            serde_json::json!(&**s)
-        }
+        Value::Str(s) => serde_json::json!(&**s),
         Value::Cons(_) => {
             let mut arr = Vec::new();
             for x in v.iter() {
@@ -301,16 +296,12 @@ fn groups_to_list(tags: &[Tag]) -> Vec<Value> {
     out
 }
 
-/// The most string bytes an entity list may hold (counted per occurrence, shared or not).
-const MAX_GROUP_TEXT: usize = 32 << 20;
-
 /// An association list back to DXF groups (points split into x, y, z groups). The type
 /// (`0`), the entity name (`-1`), the handle (`5`), the owner (`330`) and the layout (`410`) are
 /// left out: they aren't the entity's to set.
 fn list_to_groups(list: &Value) -> Result<(String, Vec<Tag>), LispError> {
     let mut kind = None;
     let mut tags = Vec::new();
-    let mut text_left = MAX_GROUP_TEXT;
     for item in list.iter() {
         let Value::Cons(c) = &item else { return Err(LispError::bad_arg("listp", &item)) };
         let Value::Int(code) = c.car else { return Err(LispError::bad_arg("fixnump", &c.car)) };
@@ -332,11 +323,7 @@ fn list_to_groups(list: &Value) -> Result<(String, Vec<Tag>), LispError> {
             _ => tags.push(match &v {
                 Value::Int(i) => Tag::i(code, i64::from(*i)),
                 Value::Real(r) => Tag::f(code, *r),
-                Value::Str(s) => {
-                    // Each occurrence of a shared string becomes its own copy in the tag.
-                    text_left = text_left.checked_sub(s.len()).ok_or_else(|| LispError::new("out of memory: the entity list holds too much text"))?;
-                    Tag::s(code, &**s)
-                }
+                Value::Str(s) => Tag::s(code, &**s),
                 Value::Ename(h) => Tag::s(code, h.hex()),
                 other => return Err(LispError::bad_arg("DXF group value", other)),
             }),
@@ -1138,27 +1125,3 @@ pub fn load_source(s: &Session, name: &str) -> Option<String> {
         s.lisp_support_dir().map(|d| candidates.iter().map(|c| d.join(c).to_string_lossy().into_owned()).collect::<Vec<_>>()).unwrap_or_default();
     candidates.iter().chain(&support).find_map(super::builtins::read_text_file)
 }
-
-#[cfg(test)]
-mod budget_tests {
-    use super::*;
-
-    /// One 64 KB string occurring many times is charged by its length each time.
-    #[test]
-    fn shared_strings_spend_the_conversion_budgets() {
-        let big = Value::str(&"x".repeat(64 << 10));
-        // 600 x 64 KB is over the 32 MiB an entity list may hold; 100 x 64 KB is not.
-        let list = |n: usize| {
-            let mut items = vec![Value::cons(Value::Int(0), Value::str("TEXT"))];
-            items.extend(std::iter::repeat_n(Value::cons(Value::Int(1), big.clone()), n));
-            Value::list(items)
-        };
-        assert!(list_to_groups(&list(600)).is_err());
-        assert!(list_to_groups(&list(100)).is_ok());
-        // 1,000 x 64 KB is 4,096,000 units of the 2,000,000 SETVAR allows; 100 x 64 KB is not.
-        let mut budget = TO_JSON_BUDGET;
-        assert!(to_json_bounded(&Value::list(vec![big.clone(); 1_000]), 0, &mut budget).is_none());
-        let mut budget = TO_JSON_BUDGET;
-        assert!(to_json_bounded(&Value::list(vec![big; 100]), 0, &mut budget).is_some());
-    }
-}

crates/engine/src/lisp/eval.rs

@@ -175,19 +175,17 @@ pub struct Machine {
     stack: Vec<Frame>,
     state: State,
     need: Option<Need>,
-    /// Steps the last [`Machine::run`] took.
-    last_steps: u64,
 }
 
 impl Machine {
     /// A machine evaluating `forms` in turn.
     pub fn forms(forms: Vec<Value>) -> Machine {
-        Machine { stack: vec![Frame::Forms { rest: forms.into_iter().rev().collect() }], state: State::Ret(Value::Nil), need: None, last_steps: 0 }
+        Machine { stack: vec![Frame::Forms { rest: forms.into_iter().rev().collect() }], state: State::Ret(Value::Nil), need: None }
     }
 
     /// A machine calling `f` with `args`.
     pub fn calling(f: Value, args: Vec<Value>) -> Machine {
-        Machine { stack: Vec::new(), state: State::Call(f, args), need: None, last_steps: 0 }
+        Machine { stack: Vec::new(), state: State::Call(f, args), need: None }
     }
 
     /// Give the value a [`Need`] waited for, and carry on.
@@ -198,15 +196,9 @@ impl Machine {
     /// Run until done, waiting, or `budget` steps.
     pub fn run(&mut self, ctx: &mut Ctx<'_>, budget: u64) -> Outcome {
         let mut n = 0u64;
-        let outcome = self.run_counted(ctx, budget, &mut n);
-        self.last_steps = n.min(budget);
-        outcome
-    }
-
-    fn run_counted(&mut self, ctx: &mut Ctx<'_>, budget: u64, n: &mut u64) -> Outcome {
         loop {
-            *n += 1;
-            if *n > budget {
+            n += 1;
+            if n > budget {
                 return Outcome::Wait(Need::Yield);
             }
             let r = match std::mem::replace(&mut self.state, State::Ret(Value::Nil)) {
@@ -654,41 +646,29 @@ impl Ctx<'_> {
             super::value::charge_result(&v)?;
             return Ok(v);
         }
-        let cap = self.s.lisp.limits.callback_steps;
-        let start = self.s.lisp.callback_used;
-        // This callback may run until `callback_used` reaches `ceiling`: `cap` steps from now, or
-        // sooner where a caller's allowance ends, so callbacks nested in callbacks share one
-        // allowance instead of each taking a fresh one (an exponential tree otherwise).
-        let outer = self.s.lisp.callback_ceiling;
-        let ceiling = start.saturating_add(cap).min(outer.unwrap_or(u64::MAX));
-        self.s.lisp.callback_ceiling = Some(ceiling);
-        let r = self.drive_callback(f, args, ceiling);
-        self.s.lisp.callback_ceiling = outer;
-        r
-    }
-
-    /// Run callback `f` in slices until it finishes or `callback_used` reaches `ceiling`.
-    fn drive_callback(&mut self, f: &Value, args: Vec<Value>, ceiling: u64) -> Result<Value, LispError> {
         let cap = self.s.lisp.limits.callback_steps;
         let mut m = Machine::calling(f.clone(), args);
         let mut sub = Ctx { s: &mut *self.s, env: &mut *self.env, depth: self.depth + 1 };
         // Drive the callback in bounded slices instead of granting it `u64::MAX` fuel. A `Yield`
-        // (the step budget ran out) is retried until the ceiling, so a constant-memory infinite
+        // (the step budget ran out) is retried until a hard cap, so a constant-memory infinite
         // loop inside a comparator or predicate terminates with an error rather than hanging the
-        // thread and bypassing the blocking execution cap (CWE-400). The steps of callbacks this
-        // one calls are counted in `callback_used` too.
+        // thread and bypassing the blocking execution cap (CWE-400).
+        let mut spent: u64 = 0;
         loop {
-            let remaining = ceiling.saturating_sub(sub.s.lisp.callback_used);
+            let remaining = cap.saturating_sub(spent);
             if remaining == 0 {
                 return Err(LispError::new(format!("callback stopped after {cap} steps")));
             }
             let slice = remaining.min(SYNC_SLICE);
-            let outcome = m.run(&mut sub, slice);
-            sub.s.lisp.callback_used = sub.s.lisp.callback_used.saturating_add(m.last_steps);
-            match outcome {
+            match m.run(&mut sub, slice) {
                 Outcome::Done(v) => return Ok(v),
                 Outcome::Error(e) => return Err(e),
-                Outcome::Wait(Need::Yield) => {}
+                Outcome::Wait(Need::Yield) => {
+                    spent = spent.saturating_add(slice);
+                    if spent >= cap {
+                        return Err(LispError::new(format!("callback stopped after {cap} steps")));
+                    }
+                }
                 Outcome::Wait(_) => return Err(LispError::new("this function can't ask for input here")),
             }
         }

crates/engine/src/lisp/tests.rs

@@ -286,20 +286,6 @@ fn reaching_a_callback_slice_boundary_does_not_grant_another_slice() {
     assert!(counts[1] >= counts[0] && counts[1] - counts[0] <= 1, "{counts:?}");
 }
 
-/// Callbacks that call callbacks share one allowance: a branching routine can't multiply it.
-#[test]
-fn nested_callbacks_share_one_step_allowance() {
-    let mut s = session();
-    s.lisp.limits.callback_steps = 1_000_000;
-    // 4^14 leaf calls if every callback took a fresh allowance; the whole tree gets one.
-    let started = std::time::Instant::now();
-    let e = eval(&mut s, "(defun f (n) (if (> n 0) (vl-every '(lambda (x) (f (1- n)) t) '(1 2 3 4)) t)) (f 14)").unwrap_err();
-    assert!(e.contains("callback stopped after 1000000 steps"), "{e}");
-    assert!(started.elapsed() < std::time::Duration::from_secs(60));
-    // The next run starts afresh.
-    assert_eq!(ok(&mut s, "(f 1)"), "T");
-}
-
 /// System-variable conversion rejects a shared list whose owned JSON expansion would exceed its budget.
 #[test]
 fn setvar_rejects_an_oversized_shared_structure() {
@@ -991,9 +977,6 @@ fn strings_are_capped() {
     assert!(e.contains("too much text"), "{e}");
     let e = eval(&mut s, "(repeat 200000 (princ \"0123456789\"))").unwrap_err();
     assert!(e.contains("too much text"), "{e}");
-    // READ makes new strings inside the list it returns: they count, though the result is a list.
-    let e = eval(&mut s, "(setq a \"(\\\"0123456789\\\")\") (repeat 100000 (setq b (read a)))").unwrap_err();
-    assert!(e.contains("too much text"), "{e}");
     // The budget is per run: the next one starts afresh.
     assert_eq!(ok(&mut s, "(strcat \"a\" \"b\")"), "\"ab\"");
 }

crates/engine/src/lisp/value.rs

@@ -346,11 +346,7 @@ pub fn equal(a: &Value, b: &Value, fuzz: f64) -> bool {
     // A shared cons DAG can expand into exponentially many node visits when compared as a tree.
     // Bound the total comparisons so `equal` on adversarial shared structure cannot monopolise the
     // thread (CWE-407); exhausting the budget reports "not equal" rather than looping.
-    equal_within(a, b, fuzz, EQUAL_BUDGET)
-}
-
-/// [`equal`] with its work allowance (node visits plus string bytes / 64) given.
-fn equal_within(a: &Value, b: &Value, fuzz: f64, mut budget: u64) -> bool {
+    let mut budget: u64 = EQUAL_BUDGET;
     equal_depth(a, b, fuzz, 0, &mut budget)
 }
 
@@ -377,19 +373,7 @@ fn equal_depth(a: &Value, b: &Value, fuzz: f64, depth: usize, budget: &mut u64)
                 a = na;
                 b = nb;
             }
-            _ => {
-                // Comparing two strings costs their length, not one visit: a shared list of long
-                // equal strings must spend the allowance by the bytes it compares (one unit per 64).
-                if let (Value::Str(x), Value::Str(y)) = (&a, &b) {
-                    let cost = (x.len().min(y.len()) / 64) as u64;
-                    if cost >= *budget {
-                        *budget = 0;
-                        return false;
-                    }
-                    *budget -= cost;
-                }
-                return atom_equal(&a, &b, fuzz);
-            }
+            _ => return atom_equal(&a, &b, fuzz),
         }
     }
 }
@@ -556,20 +540,6 @@ fn write_value(out: &mut String, v: &Value, escape: bool, depth: usize) {
 mod tests {
     use super::*;
 
-    /// `equal` charges the bytes of the strings it compares: a list of long equal strings fits a
-    /// big allowance but not a small one, though it has few nodes.
-    #[test]
-    fn equal_spends_its_allowance_on_string_bytes() {
-        let long = Value::str(&"x".repeat(6_400));
-        let other = Value::str(&"x".repeat(6_400));
-        let list = |v: &Value| Value::list(vec![v.clone(); 100]);
-        let (a, b) = (list(&long), list(&other));
-        // 100 strings x 100 units each, plus about 100 node visits.
-        assert!(equal_within(&a, &b, 0.0, 20_000));
-        assert!(!equal_within(&a, &b, 0.0, 5_000));
-        assert!(equal(&a, &b, 0.0));
-    }
-
     #[test]
     fn reals_print_with_six_significant_digits() {
         assert_eq!(real_text(1.0), "1.0");

crates/fonts/src/ttf.rs

@@ -89,7 +89,11 @@ impl Face {
         let Some(f) = self.font() else { return Vec::new() };
         [skrifa::string::StringId::FAMILY_NAME, skrifa::string::StringId::TYPOGRAPHIC_FAMILY_NAME, skrifa::string::StringId::FULL_NAME]
             .into_iter()
-            .flat_map(|id| f.localized_strings(id).map(|s| norm(&s.to_string())).collect::<Vec<_>>())
+            // A name table can hold many records that point at one big string: at most
+            // MAX_NAME_RECORDS per name id, each decoded only up to MAX_NAME_CHARS characters.
+            .flat_map(|id| {
+                f.localized_strings(id).take(MAX_NAME_RECORDS).map(|s| norm(&s.chars().take(MAX_NAME_CHARS).collect::<String>())).collect::<Vec<_>>()
+            })
             .collect()
     }
 }
@@ -104,6 +108,10 @@ pub fn faces(bytes: &Arc<Vec<u8>>) -> Vec<Face> {
 }
 
 const MAX_FACES_PER_FILE: u32 = 32;
+/// Name records read per name id of a face, and characters read of each: real fonts have a few
+/// dozen short ones.
+const MAX_NAME_RECORDS: usize = 64;
+const MAX_NAME_CHARS: usize = 256;
 /// Bounds of the missing-glyph search: files loaded, bytes loaded, faces checked per character.
 const MAX_FALLBACK_FILES: usize = 24;
 const MAX_FALLBACK_BYTES: usize = 160 << 20;

crates/geom/src/region.rs

@@ -110,6 +110,10 @@ fn build(polys: &[Vec<Vec2>], tol: f64) -> Option<Graph> {
     };
     let mut grid: HashMap<(usize, usize), Vec<usize>> = HashMap::new();
     let mut long: Vec<usize> = Vec::new();
+    // Every cell a segment is registered in is an index kept: past this many in all (each segment
+    // may take up to 4096 cells), the input is refused as it is for too much pair work.
+    const MAX_REGISTRATIONS: usize = 20_000_000;
+    let mut registered = 0usize;
     for (i, (a, b)) in segs.iter().enumerate() {
         let (x0, y0) = cell(a.min(*b));
         let (x1, y1) = cell(a.max(*b));
@@ -118,6 +122,10 @@ fn build(polys: &[Vec<Vec2>], tol: f64) -> Option<Graph> {
             long.push(i);
             continue;
         }
+        registered = registered.saturating_add((x1 - x0 + 1) * (y1 - y0 + 1));
+        if registered > MAX_REGISTRATIONS {
+            return None;
+        }
         for gx in x0..=x1 {
             for gy in y0..=y1 {
                 grid.entry((gx, gy)).or_default().push(i);
@@ -391,10 +399,10 @@ fn outside(core: &Graph, u: usize, steps: usize) -> Option<Vec<Vec2>> {
 }
 
 /// Outlines of the groups of curves inside the face `outer` (vertex indices into `g`).
-fn islands(g: &Graph, outer: &[usize], p: Vec2) -> Vec<Island> {
+fn islands(g: &Graph, outer: &[usize], p: Vec2) -> Option<Vec<Island>> {
     let comp = components(g);
     let outer_comp: std::collections::HashSet<usize> = outer.iter().filter_map(|&i| comp.get(i).copied()).collect();
-    let Some(outer_pts) = points(g, outer) else { return Vec::new() };
+    let outer_pts = points(g, outer)?;
     let ob = Bounds2::from_points(outer_pts.iter().copied());
     let core = prune(g);
     // Leftmost (then lowest) vertex still on a cycle, per component.
@@ -424,19 +432,32 @@ fn islands(g: &Graph, outer: &[usize], p: Vec2) -> Vec<Island> {
     let mut starts: Vec<(usize, usize)> = start.into_iter().collect();
     starts.sort_unstable();
     let mut out = Vec::new();
+    // Each containment test scans a whole polygon, accepted or not: they share one allowance of
+    // polygon edges, and the search ends when it is spent.
+    let mut edges_left: usize = 100_000_000;
     for (c, u) in starts {
         if out.len() >= MAX_ISLANDS {
             break;
         }
         let Some(&pu) = core.pts.get(u) else { continue };
-        if !ob.contains(pu) || !point_in_polygon(&outer_pts, pu) {
+        if !ob.contains(pu) {
+            continue;
+        }
+        let left = edges_left.checked_sub(outer_pts.len())?;
+        edges_left = left;
+        if !point_in_polygon(&outer_pts, pu) {
             continue;
         }
         let steps = edges.get(&c).copied().unwrap_or(0).saturating_add(4);
         let Some(lp) = outside(&core, u, steps) else { continue };
         let area = shoelace(&lp);
         let ib = Bounds2::from_points(lp.iter().copied());
-        if lp.len() < 3 || !area.is_finite() || area <= 0.0 || !ob.contains_box(&ib) || point_in_polygon(&lp, p) {
+        if lp.len() < 3 || !area.is_finite() || area <= 0.0 || !ob.contains_box(&ib) {
+            continue;
+        }
+        let left = edges_left.checked_sub(lp.len())?;
+        edges_left = left;
+        if point_in_polygon(&lp, p) {
             continue;
         }
         let mut src = sources.remove(&c).unwrap_or_default();
@@ -444,7 +465,7 @@ fn islands(g: &Graph, outer: &[usize], p: Vec2) -> Vec<Island> {
         src.dedup();
         out.push(Island { outline: lp, sources: src });
     }
-    out
+    Some(out)
 }
 
 /// The point of the nearest other curve within `snap` of the end `e` of curve `i`, as (curve,
@@ -457,6 +478,10 @@ fn nearest_curve(polys: &[Vec<Vec2>], i: usize, e: Vec2, snap: f64, tol: f64, bu
         if j == i {
             continue;
         }
+        // A curve with no segment costs a visit too, so many of them can't multiply the searches.
+        if other.len() < 2 {
+            *budget = budget.checked_sub(1).ok_or(())?;
+        }
         for (k, w) in other.windows(2).enumerate() {
             if *budget == 0 {
                 return Err(());
@@ -558,7 +583,7 @@ pub fn boundary_at_gap(polys: &[Vec<Vec2>], p: Vec2, tol: f64, gap: f64) -> Opti
     let g = build_gap(polys, tol, gap)?;
     let ids = outer_face(&g, p)?;
     let outer = points(&g, &ids)?;
-    let islands = islands(&g, &ids, p);
+    let islands = islands(&g, &ids, p)?;
     let mut outer_sources: Vec<usize> =
         ids.iter().zip(ids.iter().cycle().skip(1)).filter_map(|(&u, &v)| g.edge_src.get(&(u.min(v), u.max(v))).copied()).collect();
     outer_sources.sort_unstable();