Merge branch 'main' into fix/sec-xlsx-richdata-index

wrap_lines split an over-long word by re-measuring and copying the
rest of the word for every piece it cut, and only checked its line
limit once the word was done, so one long word in a narrow text box
cost word length x pieces. Each new word also re-measured the whole
line built so far.

Line and piece widths are now running sums of glyph widths (the same
sum text_width makes), so every character is measured once, and the
line limit is checked while a word is being split. The lines produced
are unchanged; a test compares them with the old wrapper.

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

@@ -695,6 +695,79 @@ fn bands_unit() {
     assert!(w.len() > 2);
 }
 
+/// The wrapper `wrap_lines` replaced, re-measuring strings, as the reference for its lines.
+fn wrap_lines_remeasuring(text: &str, font: Font, size: f32, width: f32) -> Vec<String> {
+    let mut out = Vec::new();
+    for para in text.split('\n') {
+        let mut line = String::new();
+        for word in para.split(' ') {
+            let cand = if line.is_empty() { word.to_string() } else { format!("{line} {word}") };
+            if line.is_empty() || gridcraft_pdf::text_width(font, size, &cand) <= width {
+                line = cand;
+            } else {
+                out.push(std::mem::take(&mut line));
+                line = word.to_string();
+            }
+            while gridcraft_pdf::text_width(font, size, &line) > width && line.chars().count() > 1 {
+                let chars: Vec<char> = line.chars().collect();
+                let (mut lo, mut hi) = (1usize, chars.len());
+                while lo < hi {
+                    let mid = lo + (hi - lo).div_ceil(2);
+                    let cut: String = chars[..mid].iter().collect();
+                    if gridcraft_pdf::text_width(font, size, &cut) <= width {
+                        lo = mid;
+                    } else {
+                        hi = mid - 1;
+                    }
+                }
+                if lo == chars.len() {
+                    break;
+                }
+                out.push(chars[..lo].iter().collect());
+                line = chars[lo..].iter().collect();
+            }
+            if out.len() > 2000 {
+                return out;
+            }
+        }
+        out.push(line);
+    }
+    out
+}
+
+#[test]
+fn wrap_lines_matches_the_remeasuring_wrapper() {
+    let texts = [
+        "the quick brown fox jumps",
+        "Supercalifragilistic",
+        "a  b   c\n\nverylongwordthatneedsbreaking short\nend ",
+        "Wide WWWWWWWWWW words, iiiiiiii narrow ones; mixed MMMMiiiiMMMM",
+        "€ ü ß — unicode Ünïcödé text",
+        "",
+        " ",
+    ];
+    for text in texts {
+        for font in [Font::Helvetica, Font::HelveticaBold, Font::Courier] {
+            for (size, width) in [(10.0, 50.0), (10.0, 20.0), (11.0, 1.0), (8.0, 300.0), (12.0, 0.0)] {
+                assert_eq!(wrap_lines(text, font, size, width), wrap_lines_remeasuring(text, font, size, width), "{text:?} {font:?} {size} {width}");
+            }
+        }
+    }
+}
+
+#[test]
+fn wrapping_a_long_word_in_a_narrow_box_stops_at_the_line_limit() {
+    // One character per line: the old wrapper re-measured and copied the rest of the word for
+    // each of the 100,000 lines before checking the limit.
+    let word = "w".repeat(100_000);
+    let lines = wrap_lines(&word, Font::Helvetica, 10.0, 1.0);
+    assert!(lines.len() <= 2002, "{}", lines.len());
+    assert!(lines.iter().all(|l| l == "w"));
+    // A long paragraph in a very wide box is one line.
+    let para = vec!["word"; 50_000].join(" ");
+    assert_eq!(wrap_lines(&para, Font::Helvetica, 10.0, 1.0e9), vec![para.clone()]);
+}
+
 #[test]
 fn center_across_spans_following_empty_center_across_cells() {
     let mut styles = StyleTable::default();

crates/engine/src/cmd/print/text.rs

@@ -3,42 +3,57 @@ use super::{CellRef, Color, Font, HAlign, MAX_COLS, Page, Point, RangeRef, Sheet
 
 const PAD_PX: f32 = 2.0;
 
+/// Most lines [`wrap_lines`] returns (it may return one more, the rest of a paragraph).
+const MAX_WRAP_LINES: usize = 2000;
+
 /// Word-wraps `text` to `width` points.
+///
+/// Widths are kept as running sums of glyph widths (the sum `text_width` makes), so each
+/// character is measured once: re-measuring the line for every word, or the rest of an
+/// over-long word for every piece cut from it, made a long paragraph or word quadratic.
 pub(super) fn wrap_lines(text: &str, font: Font, size: f32, width: f32) -> Vec<String> {
+    let units_of = |s: &str| -> u64 { s.chars().map(|c| u64::from(font.char_width(c))).sum() };
+    let fits = |units: u64| units as f32 * size / 1000.0 <= width;
+    let space = units_of(" ");
     let mut out = Vec::new();
     for para in text.split('\n') {
         let mut line = String::new();
+        let mut line_units: u64 = 0;
         for word in para.split(' ') {
-            let cand = if line.is_empty() { word.to_string() } else { format!("{line} {word}") };
-            if line.is_empty() || gridcraft_pdf::text_width(font, size, &cand) <= width {
-                line = cand;
+            let word_units = units_of(word);
+            if line.is_empty() {
+                line.push_str(word);
+                line_units = word_units;
+            } else if fits(line_units + space + word_units) {
+                line.push(' ');
+                line.push_str(word);
+                line_units += space + word_units;
             } else {
                 out.push(std::mem::take(&mut line));
-                line = word.to_string();
+                line.push_str(word);
+                line_units = word_units;
             }
-            // Break a single over-long word by characters. The cut that fits is found by binary
-            // search (each try measures one candidate prefix), so an over-long word costs
-            // O(n log n) measurements instead of re-measuring the whole cut per character for
-            // every emitted line (`a` × 100k pasted text would be cubic worst case).
-            while gridcraft_pdf::text_width(font, size, &line) > width && line.chars().count() > 1 {
-                let chars: Vec<char> = line.chars().collect();
-                let (mut lo, mut hi) = (1usize, chars.len());
-                while lo < hi {
-                    let mid = lo + (hi - lo).div_ceil(2);
-                    let cut: String = chars[..mid].iter().collect();
-                    if gridcraft_pdf::text_width(font, size, &cut) <= width {
-                        lo = mid;
-                    } else {
-                        hi = mid - 1;
+            // Break a single over-long word by characters: each piece is the longest that fits
+            // (at least one character).
+            if !fits(line_units) && line.chars().nth(1).is_some() {
+                let mut piece = String::new();
+                let mut units: u64 = 0;
+                for c in line.chars() {
+                    let w = u64::from(font.char_width(c));
+                    if !piece.is_empty() && !fits(units + w) {
+                        out.push(std::mem::take(&mut piece));
+                        units = 0;
+                        if out.len() > MAX_WRAP_LINES {
+                            return out;
+                        }
                     }
+                    piece.push(c);
+                    units += w;
                 }
-                if lo == chars.len() {
-                    break;
-                }
-                out.push(chars[..lo].iter().collect());
-                line = chars[lo..].iter().collect();
+                line = piece;
+                line_units = units;
             }
-            if out.len() > 2000 {
+            if out.len() > MAX_WRAP_LINES {
                 return out;
             }
         }

crates/engine/src/io.rs

@@ -907,12 +907,6 @@ const MAX_READ_BYTES: u64 = 2 * 1024 * 1024 * 1024;
 pub fn read_file(path: &str) -> Result<Vec<u8>> {
     use std::io::Read;
     script_sandbox_check(path)?;
-    // Checked before opening: opening a FIFO nobody writes to blocks the calling (GUI) thread.
-    // shortcut: a FIFO swapped in between this check and the open still blocks; close that with
-    // O_NONBLOCK when the crate takes a libc dependency.
-    if !std::fs::metadata(path).map_err(|e| EngineError::Other(format!("{path}: {e}")))?.is_file() {
-        return Err(EngineError::Other(format!("{path}: only regular files can be opened")));
-    }
     let f = std::fs::File::open(path).map_err(|e| EngineError::Other(format!("{path}: {e}")))?;
     // A symlink to an endless device reports length 0 but streams forever, so metadata
     // alone never bounds the read: require a real file and cap the bytes actually taken.
@@ -944,37 +938,18 @@ pub fn write_file(path: &str, bytes: &[u8]) -> Result<()> {
     // link's target; and it inherits the destination's access restrictions, so saving a
     // private workbook doesn't widen who can read it.
     let tmp = format!("{path}.sctmp");
-    let prior_meta = std::fs::metadata(path).ok();
-    let prior = prior_meta.as_ref().map(std::fs::Metadata::permissions);
+    let prior = std::fs::metadata(path).ok().map(|m| m.permissions());
     let mut opts = std::fs::OpenOptions::new();
     opts.write(true).create_new(true);
-    // Over an existing file the replacement starts owner-only, whatever the umask: its group is
-    // still the saving user's primary one until it is changed below, and a member of that group
-    // must not be able to open it (and keep the descriptor) before then.
     #[cfg(unix)]
-    if prior.is_some() {
-        use std::os::unix::fs::OpenOptionsExt;
-        opts.mode(0o600);
+    if let Some(p) = &prior {
+        use std::os::unix::fs::{OpenOptionsExt, PermissionsExt};
+        opts.mode(p.mode());
     }
     let mut f = opts.open(&tmp).map_err(|e| {
         let _ = std::fs::remove_file(&tmp);
         EngineError::Other(format!("{path}: {e}"))
     })?;
-    // The replacement belongs to the saving user's primary group: restore the old file's group and
-    // then its mode. When the group can't be restored its access is dropped rather than handed to a
-    // different group; failing to read that back is a failed save.
-    #[cfg(unix)]
-    if let Some(m) = &prior_meta {
-        use std::os::unix::fs::{MetadataExt, PermissionsExt};
-        let _ = std::os::unix::fs::fchown(&f, None, Some(m.gid()));
-        let group_kept = f.metadata().map(|now| now.gid() == m.gid()).map_err(|e| {
-            let _ = std::fs::remove_file(&tmp);
-            EngineError::Other(format!("{path}: {e}"))
-        })?;
-        // Best effort: a file system that can't change modes keeps the owner-only one. Without the
-        // group, the old owner and other bits are kept and the group, setuid and setgid bits dropped.
-        let _ = f.set_permissions(std::fs::Permissions::from_mode(restored_mode(m.mode(), group_kept)));
-    }
     #[cfg(not(unix))]
     if let Some(p) = &prior {
         let _ = f.set_permissions(p.clone());
@@ -991,13 +966,6 @@ pub fn write_file(path: &str, bytes: &[u8]) -> Result<()> {
     })
 }
 
-/// The mode a saved file gets from the file it replaces (`old`): all of it when its group was
-/// restored; without the group, the owner and other bits only.
-#[cfg(unix)]
-fn restored_mode(old: u32, group_kept: bool) -> u32 {
-    if group_kept { old & 0o7777 } else { old & 0o707 }
-}
-
 #[cfg(target_arch = "wasm32")]
 pub fn write_file(path: &str, _bytes: &[u8]) -> Result<()> {
     script_sandbox_check(path)?;

crates/engine/src/io/tests.rs

@@ -51,14 +51,6 @@ fn save_keeps_the_destination_access_restrictions() {
     write_file(dest.to_str().unwrap(), b"v2").unwrap();
     let mode = std::fs::metadata(&dest).unwrap().permissions().mode() & 0o777;
     assert_eq!(mode, 0o600);
-    // The mode is set outright from the old file's, not through the umask: group and other access
-    // it had stay as they were.
-    for old in [0o640, 0o664] {
-        std::fs::set_permissions(&dest, std::fs::Permissions::from_mode(old)).unwrap();
-        write_file(dest.to_str().unwrap(), b"v3").unwrap();
-        assert_eq!(std::fs::metadata(&dest).unwrap().permissions().mode() & 0o777, old);
-    }
-    assert!(!dir.join("private.xlsx.sctmp").exists());
     // And a brand-new file is created with the restrictive, not permissive, default.
     let fresh = dir.join("new.xlsx");
     write_file(fresh.to_str().unwrap(), b"v").unwrap();
@@ -67,17 +59,6 @@ fn save_keeps_the_destination_access_restrictions() {
     let _ = std::fs::remove_dir_all(&dir);
 }
 
-/// Without the old group, a saved file keeps the old owner and other bits and nothing for a group.
-#[cfg(not(target_arch = "wasm32"))]
-#[cfg(unix)]
-#[test]
-fn restored_mode_drops_the_group_and_special_bits_when_the_group_is_lost() {
-    assert_eq!(super::restored_mode(0o100_664, true), 0o664);
-    assert_eq!(super::restored_mode(0o100_664, false), 0o604);
-    assert_eq!(super::restored_mode(0o102_444, false), 0o404, "an original read-only file stays read-only, setgid is dropped");
-    assert_eq!(super::restored_mode(0o104_755, false), 0o705, "setuid is dropped");
-}
-
 #[cfg(not(target_arch = "wasm32"))]
 #[test]
 fn open_refuses_directories_and_unknowable_lengths() {
@@ -780,20 +761,3 @@ fn sylk_survives_huge_relative_offsets_and_width_floods() {
     let (wb, _) = open_bytes("widths.slk", &flood).unwrap();
     assert_eq!(wb.sheet(0).unwrap().value(CellRef::parse("A1").unwrap()), gridcraft_core::Value::Number(1.0));
 }
-
-/// A FIFO with no writer would block an open forever: it is refused before it is opened.
-#[cfg(unix)]
-#[test]
-fn reading_a_fifo_is_refused_without_blocking() {
-    let dir = std::env::temp_dir().join(format!("gridcraft-fifo-{}", std::process::id()));
-    let _ = std::fs::remove_dir_all(&dir);
-    std::fs::create_dir_all(&dir).unwrap();
-    let fifo = dir.join("pipe.xlsx");
-    if !std::process::Command::new("mkfifo").arg(&fifo).status().is_ok_and(|s| s.success()) {
-        let _ = std::fs::remove_dir_all(&dir);
-        return; // no mkfifo here
-    }
-    let err = read_file(fifo.to_str().unwrap()).unwrap_err().to_string();
-    assert!(err.contains("only regular files"), "{err}");
-    let _ = std::fs::remove_dir_all(&dir);
-}

crates/xlsx/src/richdata.rs

@@ -142,13 +142,22 @@ pub fn read(cx: &mut Ctx<'_>, workbook_rels: &[Rel]) -> Result<Vec<Option<Arc<Ce
     let Some(image_rel_list) = read_xml(cx, &image_rels_path, "richValueRels")? else { return Ok(vec![]) };
     let image_rels = cx.pkg.rels(&image_rels_path)?;
     let structures = entries(cx, &structures, "s")?;
+    // Each structure's key layout, worked out once: every value would otherwise walk its
+    // structure's keys again. Only local-image structures matter here.
+    let layouts: Vec<Option<Layout>> = structures.iter().map(|s| Layout::of(s)).collect();
     let image_rel_list = entries(cx, &image_rel_list, "rel")?;
+    // Relationships by id, a repeated id recorded as invalid (`None`), so a value's lookup is
+    // one probe rather than a scan of the whole table for duplicates.
+    let mut rels_by_id: HashMap<&str, Option<&Rel>> = HashMap::new();
+    for rel in &image_rels {
+        rels_by_id.entry(rel.id.as_str()).and_modify(|r| *r = None).or_insert(Some(rel));
+    }
     let values = entries(cx, &data, "rv")?;
     let mut pictures = Vec::with_capacity(values.len());
     let mut cache = HashMap::new();
     let mut total = 0usize;
     for value in values {
-        let picture = read_value(cx, value, &structures, &image_rel_list, &image_rels, &mut cache, &mut total)?;
+        let picture = read_value(cx, value, &layouts, &image_rel_list, &rels_by_id, &mut cache, &mut total)?;
         if picture.is_none() {
             cx.warn("some rich values are unsupported or malformed; their scalar fallbacks were retained (cell pictures may be missing)");
         }
@@ -188,43 +197,56 @@ pub fn read(cx: &mut Ctx<'_>, workbook_rels: &[Rel]) -> Result<Vec<Option<Arc<Ce
         .collect())
 }
 
+/// Where a `_localImage` structure keeps the values a picture needs.
+struct Layout {
+    keys: usize,
+    /// Index of the one `_rvRel:LocalImageIdentifier` key of type `i`, if exactly one.
+    image: Option<usize>,
+    /// Index of the one `Text` key of type `s`, if exactly one.
+    text: Option<usize>,
+}
+
+impl Layout {
+    fn of(structure: &El) -> Option<Layout> {
+        if structure.attr("t") != Some("_localImage") {
+            return None;
+        }
+        let keys: Vec<&El> = structure.kids("k").collect();
+        let one = |name: &str, ty: &str| {
+            let mut matches = keys.iter().enumerate().filter(|(_, k)| k.attr("n") == Some(name));
+            let (i, key) = matches.next()?;
+            (matches.next().is_none() && key.attr("t") == Some(ty)).then_some(i)
+        };
+        Some(Layout { keys: keys.len(), image: one("_rvRel:LocalImageIdentifier", "i"), text: one("Text", "s") })
+    }
+}
+
 fn read_value(
     cx: &mut Ctx<'_>,
     value: &El,
-    structures: &[&El],
+    layouts: &[Option<Layout>],
     image_rel_list: &[&El],
-    image_rels: &[Rel],
+    rels_by_id: &HashMap<&str, Option<&Rel>>,
     cache: &mut HashMap<(String, String), Arc<CellPicture>>,
     total: &mut usize,
 ) -> Result<Option<Arc<CellPicture>>, IoError> {
-    let Some(structure) = value.attr_u32("s").and_then(|n| structures.get(n as usize)) else { return Ok(None) };
-    if structure.attr("t") != Some("_localImage") {
-        return Ok(None);
-    }
-    let keys: Vec<_> = structure.kids("k").collect();
+    let Some(Some(layout)) = value.attr_u32("s").and_then(|n| layouts.get(n as usize)) else { return Ok(None) };
     let values: Vec<_> = value.kids("v").collect();
-    if keys.len() != values.len() {
+    if layout.keys != values.len() {
         return Ok(None);
     }
-    let lookup = |name: &str, ty: &str| {
-        let mut matches = keys.iter().zip(&values).filter(|(k, _)| k.attr("n") == Some(name));
-        let (key, value) = matches.next()?;
-        (matches.next().is_none() && key.attr("t") == Some(ty)).then_some(value.text.as_str())
-    };
-    let Some(rel_id) = lookup("_rvRel:LocalImageIdentifier", "i")
-        .and_then(|v| v.trim().parse::<usize>().ok())
-        .and_then(|n| image_rel_list.get(n))
-        .and_then(|rel| rel.attr("id"))
+    let lookup = |slot: Option<usize>| slot.and_then(|i| values.get(i)).map(|v| v.text.as_str());
+    let Some(rel_id) =
+        lookup(layout.image).and_then(|v| v.trim().parse::<usize>().ok()).and_then(|n| image_rel_list.get(n)).and_then(|rel| rel.attr("id"))
     else {
         return Ok(None);
     };
-    let mut matches = image_rels.iter().filter(|rel| rel.id == rel_id);
-    let Some(rel) = matches.next() else { return Ok(None) };
-    if matches.next().is_some() || rel.kind != "image" || rel.external {
+    let Some(found) = rels_by_id.get(rel_id) else { return Ok(None) };
+    let Some(rel) = found.filter(|rel| rel.kind == "image" && !rel.external) else {
         cx.warn("a cell picture has an external or invalid image relationship; kept its scalar fallback");
         return Ok(None);
-    }
-    let alt = lookup("Text", "s").unwrap_or("").to_string();
+    };
+    let alt = lookup(layout.text).unwrap_or("").to_string();
     let key = (normalize(&rel.target), alt.clone());
     if let Some(picture) = cache.get(&key) {
         return Ok(Some(picture.clone()));

crates/xlsx/src/tests/richdata_tests.rs

@@ -294,3 +294,27 @@ fn picture_metadata_limits_and_relationship_read_errors_do_not_block_workbooks()
         assert!(report.warnings.iter().any(|w| w.contains("cell-picture data could not be read")), "{:?}", report.warnings);
     }
 }
+
+/// Many values over one wide structure, and a repeated relationship id: the structure's layout
+/// is worked out once and relationships are indexed, so the import is linear in the records;
+/// the repeated id is invalid and keeps the scalar fallback.
+#[test]
+fn wide_structures_and_repeated_relationship_ids_are_resolved_through_indexes() {
+    let mut parts = independent_parts(false);
+    // 200,000 keys in one structure and 50,000 short values that name it: rebuilding the key
+    // list per value would be ten billion steps.
+    let padding = r#"<k n="pad" t="s"/>"#.repeat(200_000);
+    replace(&mut parts, "rich/structures.xml", r#"<k n="CalcOrigin" t="i"/>"#, &format!(r#"<k n="CalcOrigin" t="i"/>{padding}"#));
+    let values = r#"<rv s="1"><v/></rv>"#.repeat(50_000);
+    replace(&mut parts, "rich/values.xml", r#"<rv s="1"><v>green &amp; &lt;image&gt;</v><v>1</v><v>5</v></rv>"#, &values);
+    let (wb, report) = read_xlsx(&zip(&parts)).unwrap();
+    assert!(!wb.sheet(0).unwrap().cell_pictures.contains_key(&at("A1")));
+    assert!(report.warnings.iter().any(|w| w.contains("picture")), "{:?}", report.warnings);
+    // The same id twice makes every reference to it invalid.
+    let mut parts = independent_parts(false);
+    let dup = r#"<Relationship Id="opaqueImageId" Type="http://schemas.openxmlformats.org/officeDocument/2006/relationships/image" Target="../media/original.bin"/>"#;
+    replace(&mut parts, "rich/_rels/images.xml.rels", dup, &dup.repeat(2));
+    let (wb, report) = read_xlsx(&zip(&parts)).unwrap();
+    assert!(!wb.sheet(0).unwrap().cell_pictures.contains_key(&at("A1")));
+    assert!(report.warnings.iter().any(|w| w.contains("invalid image relationship")), "{:?}", report.warnings);
+}