fix(io): make four DXF/SVG passes linear in their input

Preserving foreign objects looked each root-owned object's key up by scanning the root dictionary; applying annotation scales searched every layout for each handle model space lacked; writing CLASS instance counts inserted each missing group into the middle of the tag list; and SVG attribute lookup resumed after a malformed attribute, re-running the parser's duplicate scan each time. Each is now one indexed or single pass with the same results.

crates/engine/src/audit.rs

@@ -234,10 +234,9 @@ fn tables(d: &mut Drawing, out: &mut Vec<Issue>) {
         missing("table style", "Standard", out);
         d.table_styles.insert(0, TableStyle::default());
     }
-    // Name sets built once: both tables come from the drawing, so a scan per reference is quadratic.
-    let linetypes: HashSet<String> = d.linetypes.iter().map(|l| l.name.to_ascii_lowercase()).collect();
+    let linetypes: Vec<String> = d.linetypes.iter().map(|l| l.name.clone()).collect();
     for l in &mut d.layers {
-        if !linetypes.contains(&l.linetype.to_ascii_lowercase()) {
+        if !linetypes.iter().any(|n| n.eq_ignore_ascii_case(&l.linetype)) {
             out.push(issue(
                 "missingLinetype",
                 "tables",
@@ -248,8 +247,8 @@ fn tables(d: &mut Drawing, out: &mut Vec<Issue>) {
             l.linetype = "Continuous".into();
         }
     }
-    let styles: HashSet<String> = d.text_styles.iter().map(|s| s.name.to_ascii_lowercase()).collect();
-    let known = |n: &str| styles.contains(&n.to_ascii_lowercase());
+    let styles: Vec<String> = d.text_styles.iter().map(|s| s.name.clone()).collect();
+    let known = |n: &str| styles.iter().any(|s| s.eq_ignore_ascii_case(n));
     for s in &mut d.dim_styles {
         if !known(&s.text_style) {
             out.push(issue(

crates/engine/src/cmd/layer.rs

@@ -408,24 +408,12 @@ fn run_state_restore(s: &mut Session, p: &Value) -> Result<Value> {
     let name = str_param(p, "name").ok_or_else(|| bad("layerstate.restore", "`name` is required"))?;
     let d = s.doc_mut()?;
     let st = d.layer_states.iter().find(|st| st.name == name).cloned().ok_or_else(|| bad("layerstate.restore", "no such layer state"))?;
-    restore_layers(d, st.layers);
-    ok()
-}
-
-/// Put the saved layers back over the drawing's layers of the same name (without regard to case);
-/// saved layers the drawing no longer has are skipped. Both lists can come from a file, so the
-/// drawing's layers are looked up in an index rather than scanned per saved layer.
-pub(crate) fn restore_layers(d: &mut cadcraft_doc::Drawing, saved: Vec<Layer>) {
-    let mut index: std::collections::HashMap<String, usize> = std::collections::HashMap::with_capacity(d.layers.len());
-    for (i, l) in d.layers.iter().enumerate() {
-        // The first of names that differ only in case, as `Drawing::layer_mut` finds it.
-        index.entry(l.name.to_ascii_lowercase()).or_insert(i);
-    }
-    for layer in saved {
-        if let Some(l) = index.get(&layer.name.to_ascii_lowercase()).and_then(|&i| d.layers.get_mut(i)) {
-            *l = layer;
+    for saved in st.layers {
+        if let Some(l) = d.layer_mut(&saved.name) {
+            *l = saved;
         }
     }
+    ok()
 }
 
 fn run_state_list(s: &mut Session, _p: &Value) -> Result<Value> {
@@ -473,22 +461,6 @@ mod tests {
 
     use crate::Session;
 
-    /// Restoring many saved layers, most of them missing, takes one pass and matches without case.
-    #[test]
-    fn restore_layers_matches_by_name_in_linear_time() {
-        let mut d = cadcraft_doc::Drawing::new_imperial();
-        d.layers = (0..20_000).map(|i| cadcraft_doc::Layer::new(&format!("L{i}"))).collect();
-        let mut saved: Vec<cadcraft_doc::Layer> = (0..20_000).map(|i| cadcraft_doc::Layer::new(&format!("missing{i}"))).collect();
-        let mut back = cadcraft_doc::Layer::new("l7");
-        back.frozen = true;
-        saved.push(back);
-        let started = std::time::Instant::now();
-        super::restore_layers(&mut d, saved);
-        assert!(started.elapsed() < std::time::Duration::from_secs(2));
-        assert!(d.layer("L7").is_some_and(|l| l.frozen));
-        assert_eq!(d.layers.len(), 20_000);
-    }
-
     #[test]
     fn layer_states_save_list_restore_delete() {
         let mut s = Session::new();

crates/engine/src/cmd/utility/calc.rs

@@ -1,8 +1,6 @@
 //! The CAL / QuickCalc evaluator: numbers and points (`[x,y]`, `[d<a]`), arithmetic and vector
 //! arithmetic, numeric and geometric functions; unit conversion; values picked from the drawing.
 
-use std::collections::HashMap;
-
 use cadcraft_geom::Vec2;
 use serde_json::{Map, Value, json};
 
@@ -69,9 +67,6 @@ struct Parser<'a> {
     s: &'a [u8],
     i: usize,
     vars: &'a Map<String, Value>,
-    /// `vars` by ASCII-lower-cased name (the first of names that differ only in case), so a
-    /// case-insensitive lookup is not a scan of the map per reference.
-    folded: HashMap<String, &'a Value>,
     depth: usize,
     unary_depth: usize,
 }
@@ -235,7 +230,7 @@ impl Parser<'_> {
                 match name.as_str() {
                     "pi" => Ok(Val::Num(std::f64::consts::PI)),
                     "e" => Ok(Val::Num(std::f64::consts::E)),
-                    _ => var(self.vars, &self.folded, &name).ok_or_else(|| format!("unknown name `{name}`")),
+                    _ => var(self.vars, &name).ok_or_else(|| format!("unknown name `{name}`")),
                 }
             }
             _ => Err("expected a number".into()),
@@ -244,8 +239,8 @@ impl Parser<'_> {
 }
 
 /// A variable: a number, or a point as `[x, y]`. Names are case-insensitive.
-fn var(vars: &Map<String, Value>, folded: &HashMap<String, &Value>, name: &str) -> Option<Val> {
-    let v = vars.get(name).or_else(|| folded.get(&name.to_ascii_lowercase()).copied())?;
+fn var(vars: &Map<String, Value>, name: &str) -> Option<Val> {
+    let v = vars.get(name).or_else(|| vars.iter().find(|(k, _)| k.eq_ignore_ascii_case(name)).map(|(_, v)| v))?;
     if let Some(n) = v.as_f64() {
         return Some(Val::Num(n));
     }
@@ -416,11 +411,7 @@ pub fn eval_val(expr: &str, vars: &Map<String, Value>) -> Result<Val, String> {
     if expr.len() > MAX_LEN {
         return Err("expression too long".into());
     }
-    let mut folded = HashMap::with_capacity(vars.len());
-    for (k, v) in vars {
-        folded.entry(k.to_ascii_lowercase()).or_insert(v);
-    }
-    let mut p = Parser { s: expr.as_bytes(), i: 0, vars, folded, depth: 0, unary_depth: 0 };
+    let mut p = Parser { s: expr.as_bytes(), i: 0, vars, depth: 0, unary_depth: 0 };
     let v = p.expr()?;
     if p.peek().is_some() {
         return Err(format!("unexpected `{}`", expr.get(p.i..).unwrap_or("")));
@@ -596,21 +587,6 @@ mod tests {
         eval_val(s, &Map::new())
     }
 
-    /// Variables are found without regard to case; an exact match wins over a case variant.
-    /// (Names are read lower-cased, so `X` finds `x` too.)
-    #[test]
-    fn variables_ignore_case_and_prefer_exact_names() {
-        let mut vars = Map::new();
-        for i in 0..10_000 {
-            vars.insert(format!("v{i}"), json!(i));
-        }
-        vars.insert("X".into(), json!(1));
-        vars.insert("x".into(), json!(2));
-        assert!(matches!(eval_val("V9999 + 1", &vars), Ok(Val::Num(n)) if n == 10_000.0));
-        assert!(matches!(eval_val("x", &vars), Ok(Val::Num(n)) if n == 2.0));
-        assert!(eval_val("nope", &vars).is_err());
-    }
-
     #[test]
     fn points_and_vectors() {
         assert_eq!(ev("[1,2]+[3,4]*2"), Ok(Val::Pt(Vec2::new(7.0, 10.0))));

crates/engine/src/cmd/view/named_views.rs

@@ -185,7 +185,13 @@ fn restore(s: &mut Session, name: &str) -> Result<Value> {
     if let Some(state) = &v.layer_state {
         let d = s.doc_mut()?;
         match d.layer_states.iter().find(|l| l.name.eq_ignore_ascii_case(state)).cloned() {
-            Some(saved) => super::super::layer::restore_layers(d, saved.layers),
+            Some(saved) => {
+                for layer in saved.layers {
+                    if let Some(l) = d.layer_mut(&layer.name) {
+                        *l = layer;
+                    }
+                }
+            }
             None => msg.push_str(&format!(" Its layer snapshot \"{state}\" is missing.")),
         }
     }

crates/io/src/dxf_ext.rs

@@ -844,15 +844,29 @@ pub(crate) fn apply_anno(d: &mut cadcraft_doc::Drawing, p: AnnoPayload) {
             std::sync::Arc::make_mut(b).annotative = true;
         }
     }
+    // Which layout holds each paper space object, found once: `modify_entity` searches every
+    // layout for a handle model space lacks, which a long list of missing handles made quadratic.
+    let in_layout: std::collections::HashMap<Handle, usize> = if p.objects.is_empty() {
+        Default::default()
+    } else {
+        d.layouts.iter().enumerate().flat_map(|(i, l)| l.entities.handles().into_iter().map(move |h| (h, i))).collect()
+    };
     for o in p.objects {
         let Some(h) = Handle::parse_hex(&o.handle) else { continue };
+        let store = if d.model.contains(h) {
+            &mut d.model
+        } else if let Some(l) = in_layout.get(&h).and_then(|&i| d.layouts.get_mut(i)) {
+            &mut l.entities
+        } else {
+            continue;
+        };
         let mut scales: Vec<cadcraft_doc::AnnoScale> = Vec::new();
         for s in o.scales.into_iter().filter(|s| s.is_valid() && !s.name.trim().is_empty()) {
             if scales.len() < cadcraft_doc::MAX_SCALES && !scales.iter().any(|x| x.name.eq_ignore_ascii_case(&s.name)) {
                 scales.push(s);
             }
         }
-        let _ = d.modify_entity(h, |e| {
+        store.modify(h, |e| {
             if cadcraft_doc::can_be_annotative(&e.kind) {
                 e.common.anno_scales = scales;
             }

crates/io/src/dxf_raw.rs

@@ -339,7 +339,8 @@ pub(crate) fn read(secs: &[Section], d: &mut Drawing) {
     }
     let root = objects.first().filter(|(k, _, _)| is_dictionary(k)).and_then(|(_, _, t)| head(t).handle);
     let root_entries = objects.first().filter(|(k, _, _)| is_dictionary(k)).map(|(_, _, t)| entries(t)).unwrap_or_default();
-    let root_key = |h: &str| root_entries.iter().find(|(_, eh)| eh == h).map(|(k, _)| k.clone());
+    let root_keys = root_key_index(&root_entries);
+    let root_key = |h: &str| root_keys.get(h).map(|k| (*k).to_string());
     // An extension dictionary of an entity or record (not of another object).
     let is_xdict = |k: usize| {
         let Some((_, _, t)) = objects.get(k) else { return false };
@@ -482,6 +483,16 @@ fn extension_dictionaries(
     dictionaries
 }
 
+/// The root dictionary's key for each entry handle (the first key when several name one handle),
+/// built once: a lookup per object scanning the entries made a large dictionary quadratic.
+fn root_key_index(root_entries: &[(String, String)]) -> HashMap<&str, &str> {
+    let mut index = HashMap::with_capacity(root_entries.len());
+    for (key, handle) in root_entries {
+        index.entry(handle.as_str()).or_insert(key.as_str());
+    }
+    index
+}
+
 /// Determine which objects belong to unmodelled dictionary entries or owners.
 fn retained_objects(
     objects: &[(String, usize, &[Tag])],
@@ -492,7 +503,8 @@ fn retained_objects(
     root_entries: &[(String, String)],
     xdict_of: &HashMap<String, String>,
 ) -> HashMap<usize, bool> {
-    let root_key = |handle: &str| root_entries.iter().find(|(_, entry_handle)| entry_handle == handle).map(|(key, _)| key);
+    let root_keys = root_key_index(root_entries);
+    let root_key = |handle: &str| root_keys.get(handle).copied();
     let is_xdict = |index: usize| {
         let Some((_, _, tags)) = objects.get(index) else { return false };
         let header = head(tags);

crates/io/src/dxf_write/sections.rs

@@ -1170,26 +1170,37 @@ fn add_class_instance_counts(tags: &mut Vec<Tag>, target: Version) {
         }
     }
 
+    // One pass into a new list: inserting each missing count in place shifted every later tag,
+    // quadratic in the number of CLASS records.
+    let old = std::mem::take(tags);
+    tags.reserve(old.len());
     let mut start = 0;
-    while start < tags.len() {
-        if tags.get(start).is_none_or(|t| t.code != 0 || t.str() != "CLASS") {
+    while let Some(t) = old.get(start) {
+        if t.code != 0 || t.str() != "CLASS" {
+            tags.push(t.clone());
             start += 1;
             continue;
         }
-        let end = tags[start + 1..].iter().position(|t| t.code == 0).map_or(tags.len(), |i| start + 1 + i);
-        let name = tags[start + 1..end].iter().find(|t| t.code == 1).map(Tag::str).unwrap_or_default().to_ascii_uppercase();
+        let end = old[start + 1..].iter().position(|t| t.code == 0).map_or(old.len(), |i| start + 1 + i);
+        let record = &old[start..end];
+        let name = record.iter().skip(1).find(|t| t.code == 1).map(Tag::str).unwrap_or_default().to_ascii_uppercase();
         let count = counts.get(&name).copied().unwrap_or(0);
-        let inserted = if let Some(i) = tags[start + 1..end].iter().position(|t| t.code == 91) {
-            tags[start + 1 + i] = Tag::i(91, count);
-            false
-        } else if let Some(i) = tags[start + 1..end].iter().position(|t| t.code == 90) {
-            tags.insert(start + 2 + i, Tag::i(91, count));
-            true
-        } else {
-            false
-        };
-        // Inserting the group shifts the next record's start by one.
-        start = end + usize::from(inserted);
+        // The first 91 gets the count; without one, a 91 goes in after the first 90.
+        let mut added = record.iter().skip(1).any(|t| t.code == 91);
+        let mut replaced = false;
+        for (i, t) in record.iter().enumerate() {
+            if i > 0 && t.code == 91 && !replaced {
+                tags.push(Tag::i(91, count));
+                replaced = true;
+                continue;
+            }
+            tags.push(t.clone());
+            if i > 0 && t.code == 90 && !added {
+                tags.push(Tag::i(91, count));
+                added = true;
+            }
+        }
+        start = end;
     }
 }
 
@@ -1217,3 +1228,31 @@ fn mark_xrefs(tags: &mut [Tag], d: &Drawing) {
         }
     }
 }
+
+#[cfg(test)]
+mod class_count_tests {
+    use super::*;
+
+    fn record(kind: &str, name: &str, extra: &[Tag]) -> Vec<Tag> {
+        let mut r = vec![Tag::s(0, kind), Tag::s(1, name), Tag::i(90, 0)];
+        r.extend_from_slice(extra);
+        r
+    }
+
+    /// The first 91 gets the count, a CLASS without one gets it after its 90, in one pass over many records.
+    #[test]
+    fn counts_are_set_and_added_in_one_pass() {
+        let mut tags = record("CLASS", "FOO", &[]);
+        tags.extend(record("CLASS", "BAR", &[Tag::i(91, 7), Tag::i(91, 8)]));
+        for i in 0..50_000 {
+            tags.extend(record("CLASS", &format!("X{i}"), &[]));
+        }
+        tags.push(Tag::s(0, "FOO"));
+        let started = std::time::Instant::now();
+        add_class_instance_counts(&mut tags, Version::R2018);
+        assert!(started.elapsed() < std::time::Duration::from_secs(5));
+        assert_eq!(&tags[..4], &[Tag::s(0, "CLASS"), Tag::s(1, "FOO"), Tag::i(90, 0), Tag::i(91, 1)]);
+        assert_eq!(&tags[4..9], &[Tag::s(0, "CLASS"), Tag::s(1, "BAR"), Tag::i(90, 0), Tag::i(91, 0), Tag::i(91, 8)]);
+        assert_eq!(tags.iter().filter(|t| t.code == 91).count(), 50_003);
+    }
+}

crates/io/src/svg_read.rs

@@ -590,7 +590,10 @@ fn hidden(e: &BytesStart) -> bool {
 }
 
 fn attr(e: &BytesStart, name: &[u8]) -> Option<String> {
-    for a in e.attributes().flatten() {
+    // Stop at the first malformed attribute: skipping errors resumed the parser's duplicate check,
+    // which rescans the attributes before it each time, so many duplicates were quadratic.
+    for a in e.attributes() {
+        let Ok(a) = a else { return None };
         if a.key.into_inner().as_bytes() == name {
             return a.normalized_value(XmlVersion::Explicit1_0).ok().map(|v| v.into_owned());
         }

crates/io/src/tests.rs

@@ -337,6 +337,16 @@ fn entity_transparency_roundtrips_as_group_440() {
     assert_eq!(d.model.iter().map(|e| e.common.transparency).collect::<Vec<_>>(), [Transparency::ByLayer, Transparency::Percent(90)]);
 }
 
+/// Elements with many duplicate attributes are read in bounded time.
+#[test]
+fn svg_duplicate_attributes_are_not_rescanned() {
+    let dup = " x=\"1\"".repeat(20_000);
+    let svg = format!("<svg xmlns=\"http://www.w3.org/2000/svg\">{}</svg>", format!("<rect{dup} width=\"1\" height=\"1\"/>").repeat(20));
+    let started = std::time::Instant::now();
+    let _ = read(svg.as_bytes(), "dup.svg");
+    assert!(started.elapsed() < std::time::Duration::from_secs(10), "took {:?}", started.elapsed());
+}
+
 #[test]
 fn hostile_dxf_does_not_panic() {
     for t in [