fix(render): charge every block entry, index attribute definitions, and walk dashes and outlines in linear time (#2724)

* fix(render): charge every block entry, index attribute definitions, and walk dashes and outlines in linear time

Array copies skipped ATTDEF entries before charging the expansion budget, each attribute searched its block for a definition, each dash scanned every centreline sample, and outline chaining searched a vertex's segment list from its start on every visit. Each is now charged, indexed or cursored.

* address review: drop wall-clock bound from outline test

crates/engine/src/autosave.rs

@@ -405,10 +405,11 @@ mod native {
     pub fn prune_locks(dir: &Path) {
         let Ok(entries) = std::fs::read_dir(dir) else { return };
         let names: Vec<String> = entries.flatten().take(10_000).map(|e| e.file_name().to_string_lossy().to_string()).collect();
+        // The instances that own autosave files, parsed once rather than once per lock file.
+        let with_files: std::collections::HashSet<&str> = names.iter().filter_map(|f| parse_file_name(f)).map(|(_, i, _)| i).collect();
         for n in &names {
             let Some(instance) = parse_lock_name(n) else { continue };
-            let has_files = names.iter().any(|f| parse_file_name(f).is_some_and(|(_, i, _)| i == instance));
-            if !has_files && !owner_alive(dir, instance) {
+            if !with_files.contains(instance) && !owner_alive(dir, instance) {
                 let _ = std::fs::remove_file(dir.join(n));
             }
         }
@@ -435,7 +436,22 @@ mod native {
         }
         // Create a fresh temporary file exclusively and rename it into place, so a planted
         // `<path>.tmp` symlink in a shared autosave directory cannot redirect the write (CWE-59).
-        crate::atomic_write::write_atomic(Path::new(path), &bytes).map_err(|e| e.to_string())
+        // The file holds unsaved work: owner-only from its creation, whatever the umask.
+        crate::atomic_write::write_atomic_with(Path::new(path), private_mode(), |f| f.write_all(&bytes)).map_err(|e| e.to_string())
+    }
+
+    /// Owner read/write only (`None` where file modes don't exist).
+    fn private_mode() -> Option<std::fs::Permissions> {
+        #[cfg(unix)]
+        return Some(std::os::unix::fs::PermissionsExt::from_mode(0o600));
+        #[cfg(not(unix))]
+        None
+    }
+
+    /// Write this app's lock file at `path` without following a link planted there: the file is
+    /// replaced (exclusive temporary file, then rename), never written through (CWE-59).
+    fn write_lock(path: &Path, id: u32) -> std::io::Result<()> {
+        crate::atomic_write::write_atomic_with(path, private_mode(), |f| f.write_all(id.to_string().as_bytes()))
     }
 
     impl Autosaver {
@@ -586,7 +602,7 @@ mod native {
             for (held, file) in &self.locks {
                 let refreshed = match file {
                     Some(file) => file.set_modified(SystemTime::now()),
-                    None => std::fs::write(held, id.to_string()),
+                    None => write_lock(held, id),
                 };
                 if held == path {
                     current = Some(refreshed);
@@ -595,10 +611,22 @@ mod native {
             if let Some(refreshed) = current {
                 return refreshed;
             }
-            let mut file = OpenOptions::new().write(true).create(true).truncate(false).open(path)?;
+            let mut options = OpenOptions::new();
+            options.write(true).create(true).truncate(false);
+            #[cfg(unix)]
+            {
+                use std::os::unix::fs::OpenOptionsExt;
+                // A symlink planted at the lock path must not be opened (and truncated) through,
+                // nor a FIFO wait for a reader.
+                options.custom_flags(libc::O_NOFOLLOW | libc::O_NONBLOCK).mode(0o600);
+            }
+            let mut file = options.open(path)?;
+            if !file.metadata()?.is_file() {
+                return Err(std::io::Error::new(std::io::ErrorKind::InvalidInput, "the lock file is not a plain file"));
+            }
             if file.try_lock().is_err() {
                 self.locks.push((path.to_path_buf(), None));
-                return std::fs::write(path, id.to_string());
+                return write_lock(path, id);
             }
             file.set_len(0)?;
             file.write_all(format!("{id}{LOCK_HELD}").as_bytes())?;
@@ -627,6 +655,30 @@ mod native {
             }
         }
     }
+
+    #[cfg(all(test, unix))]
+    mod tests {
+        use super::*;
+
+        /// A symlink planted at the lock path is neither opened through nor written through.
+        #[test]
+        fn lock_writes_do_not_follow_a_planted_link() {
+            let dir = std::env::temp_dir().join(format!("cadcraft-lock-link-{}", std::process::id()));
+            std::fs::create_dir_all(&dir).unwrap();
+            let victim = dir.join("victim.txt");
+            std::fs::write(&victim, b"precious").unwrap();
+            let link = dir.join("1-a.lock");
+            std::os::unix::fs::symlink(&victim, &link).unwrap();
+            let mut a = Autosaver::new("1-a");
+            assert!(a.refresh_lock(&link).is_err());
+            assert_eq!(std::fs::read(&victim).unwrap(), b"precious");
+            write_lock(&link, 42).unwrap();
+            assert_eq!(std::fs::read(&victim).unwrap(), b"precious");
+            assert!(!std::fs::symlink_metadata(&link).unwrap().file_type().is_symlink());
+            assert_eq!(std::fs::read(&link).unwrap(), b"42");
+            std::fs::remove_dir_all(dir).unwrap();
+        }
+    }
 }
 
 #[cfg(test)]

crates/render/src/blocks.rs

@@ -56,13 +56,15 @@ pub(crate) fn insert(b: &mut Builder, ctx: &Ctx, e: &Entity, ins: &cadcraft_doc:
                 let m = Mat3::translate(off).then_before(ins.transform(blk.base.xy()));
                 let sub = Ctx { block_pstyle: b.named, block_transparency: b.transparency, ..sub_ctx(ctx, e, m) };
                 for be in blk.entities.iter() {
+                    // Every visit is charged, drawn or not, so a block of definitions can't make
+                    // the copies loop free.
+                    if !b.expand() {
+                        break 'copies;
+                    }
                     // Constant/visible attribute definitions inside blocks are not drawn; attribs are.
                     if matches!(be.kind, EntityKind::AttDef(_)) {
                         continue;
                     }
-                    if !b.expand() {
-                        break 'copies;
-                    }
                     entity(b, &sub, be);
                 }
             }
@@ -73,6 +75,17 @@ pub(crate) fn insert(b: &mut Builder, ctx: &Ctx, e: &Entity, ins: &cadcraft_doc:
         let attmode = ctx.d.header.i64("ATTMODE", 1);
         // The reference's transparency; each attribute draws with its own.
         let reference = b.transparency;
+        // The block's first definition per tag (without case), built once for all the attributes.
+        let mut defs: std::collections::HashMap<String, &Entity> = std::collections::HashMap::new();
+        if !ins.attribs.is_empty()
+            && let Some(blk) = ctx.d.block(&ins.block)
+        {
+            for be in blk.entities.iter() {
+                if let EntityKind::AttDef(d) = &be.kind {
+                    defs.entry(d.tag.to_ascii_lowercase()).or_insert(be.as_ref());
+                }
+            }
+        }
         for a in &ins.attribs {
             if attmode == 0 || (a.invisible && attmode != 2) {
                 continue;
@@ -83,7 +96,7 @@ pub(crate) fn insert(b: &mut Builder, ctx: &Ctx, e: &Entity, ins: &cadcraft_doc:
             // Properties of the attribute's definition (as AutoCAD copies them to the attribute
             // on insertion), except those set on the attribute itself: ByBlock = the reference's,
             // layer 0 = the reference's layer.
-            let def = ctx.d.block(&ins.block).and_then(|blk| blk.entities.iter().find(|be| attdef_tag(be, &a.tag)));
+            let def = defs.get(&a.tag.to_ascii_lowercase()).copied();
             let (ink, lw, shown, t) = match (def, a.props.is_empty()) {
                 (None, true) => (rgb, resolve(ctx, e, b.plotting).1, true, reference),
                 (def, _) => {
@@ -117,8 +130,3 @@ fn by_block() -> cadcraft_doc::Common {
         ..cadcraft_doc::Common::default()
     }
 }
-
-/// The attribute definition with tag `tag` (any case).
-fn attdef_tag(e: &Entity, tag: &str) -> bool {
-    matches!(&e.kind, EntityKind::AttDef(d) if d.tag.eq_ignore_ascii_case(tag))
-}

crates/render/src/outline.rs

@@ -106,10 +106,12 @@ fn chain(mut segs: Vec<(Vec2, Vec2)>) -> Vec<Vec<Vec2>> {
         }
     }
     segs.sort_unstable_by(|(a, b), (c, d)| cmp(*a, *c).then_with(|| cmp(*b, *d)));
-    let mut at: HashMap<Key, Vec<usize>> = HashMap::new();
+    // Segments at each vertex with a cursor past the used ones, so many segments meeting at one
+    // vertex are each examined once rather than from the start on every visit.
+    let mut at: HashMap<Key, (Vec<usize>, usize)> = HashMap::new();
     for (i, (a, b)) in segs.iter().enumerate() {
-        at.entry(key(*a)).or_default().push(i);
-        at.entry(key(*b)).or_default().push(i);
+        at.entry(key(*a)).or_default().0.push(i);
+        at.entry(key(*b)).or_default().0.push(i);
     }
     let mut used = vec![false; segs.len()];
     let mut out = Vec::new();
@@ -125,7 +127,15 @@ fn chain(mut segs: Vec<(Vec2, Vec2)>) -> Vec<Vec<Vec2>> {
         let mut end = b;
         // Each step uses one segment, so the walk ends within `segs.len()` steps.
         loop {
-            let next = at.get(&key(end)).and_then(|ids| ids.iter().copied().find(|&i| !used.get(i).copied().unwrap_or(true)));
+            let next = at.get_mut(&key(end)).and_then(|(ids, cursor)| {
+                while let Some(&i) = ids.get(*cursor) {
+                    if !used.get(i).copied().unwrap_or(true) {
+                        return Some(i);
+                    }
+                    *cursor += 1;
+                }
+                None
+            });
             let Some(i) = next else { break };
             let Some(&(p, q)) = segs.get(i) else { break };
             if let Some(u) = used.get_mut(i) {
@@ -147,6 +157,20 @@ mod tests {
         lines.iter().flat_map(|l| l.windows(2).map(|w| w[0].dist(w[1]))).sum()
     }
 
+    /// Thousands of lobes meeting at one vertex chain in one pass over that vertex's segments.
+    #[test]
+    fn many_lobes_at_one_vertex_chain_quickly() {
+        let mut tris = Vec::new();
+        for i in 0..20_000 {
+            let x = f64::from(i + 1);
+            tris.extend_from_slice(&[Vec2::ZERO, Vec2::new(x, 1.0), Vec2::new(x + 0.5, 2.0)]);
+        }
+        // No wall-clock bound (flaky on loaded runners): a quadratic scan would make this test crawl
+        // rather than fail, so check the output is complete instead.
+        let lines = fill_outlines(&tris);
+        assert_eq!(lines.iter().map(|l| l.len() - 1).sum::<usize>(), 60_000, "every triangle edge is emitted once");
+    }
+
     #[test]
     fn a_square_of_two_triangles_is_one_loop() {
         let (a, b, c, d) = (Vec2::new(0.0, 0.0), Vec2::new(2.0, 0.0), Vec2::new(2.0, 1.0), Vec2::new(0.0, 1.0));

crates/render/src/wide.rs

@@ -95,7 +95,9 @@ pub fn dashed(p: &LwPolyline, tol: f64, lt: &Linetype, scale: f64, min_pattern:
                 continue;
             }
             let (Some(first), Some(last)) = (at(run, a), at(run, b)) else { continue };
-            let inner = run.iter().filter(|x| x.s > a && x.s < b).copied();
+            // The samples strictly between a and b: `run` is ordered by `s`, so a slice, not a scan.
+            let (lo, hi) = (run.partition_point(|x| x.s <= a), run.partition_point(|x| x.s < b));
+            let inner = run.get(lo..hi.max(lo)).unwrap_or_default().iter().copied();
             let pts: Vec<Sample> = std::iter::once(first).chain(inner).chain(std::iter::once(last)).collect();
             for w in pts.windows(2) {
                 if let [x, y] = w {