address review: layout progress doc for decimal-tab scan

Text after a decimal tab is shifted after each of its clusters, and each
shift walked the text again from the tab to find its first '.'. A long run
without a '.' (soft hyphens take no room, so it stays on one line) made a
single paragraph's line breaking quadratic. The scan now carries on from the
cluster it reached.

crates/fonts/src/fontdb/user.rs

@@ -154,7 +154,6 @@ pub fn decode_font_file(bytes: &[u8]) -> Result<Vec<u8>, UserFontError> {
             unwrap_web_font(|| wuff::decompress_woff1(bytes))?
         }
         FontFormat::Woff2 => {
-            check_woff2_collection(bytes)?;
             let mut too_many_points = false;
             let unwrapped = unwrap_web_font(|| {
                 wuff::decompress_woff2_with_custom_brotli(bytes, &mut |data, size| {
@@ -222,29 +221,8 @@ fn woff2_points_fit(file: &[u8], stream: &[u8]) -> bool {
 /// The transformed `glyf` tables in `stream`, found from the WOFF2 table directory in `file`
 /// (tables follow each other in directory order).
 fn woff2_transformed_glyf<'a>(file: &[u8], stream: &'a [u8]) -> Option<Vec<&'a [u8]>> {
-    let (tables, _) = woff2_directory(file)?;
-    let (mut offset, mut glyf) = (0usize, Vec::new());
-    for t in tables {
-        let end = offset.checked_add(t.len)?;
-        if t.transformed_glyf {
-            glyf.push(stream.get(offset..end)?);
-        }
-        offset = end;
-    }
-    Some(glyf)
-}
-
-/// A WOFF2 table directory entry: whether it is a transformed `glyf` table, and its length in
-/// the decompressed stream.
-struct Woff2Table {
-    transformed_glyf: bool,
-    len: usize,
-}
-
-/// The WOFF2 table directory in `file`, and where it ends (the collection directory follows).
-fn woff2_directory(file: &[u8]) -> Option<(Vec<Woff2Table>, usize)> {
     let tables = u16::from_be_bytes(file.get(12..14)?.try_into().ok()?);
-    let (mut at, mut out) = (48usize, Vec::with_capacity(usize::from(tables)));
+    let (mut at, mut offset, mut glyf) = (48usize, 0usize, Vec::new());
     for _ in 0..tables {
         let flags = *file.get(at)?;
         at += 1;
@@ -260,81 +238,13 @@ fn woff2_directory(file: &[u8]) -> Option<(Vec<Woff2Table>, usize)> {
         // glyf and loca are transformed at version 0, other tables at any other version.
         let transformed = if is_glyf || is_loca { flags >> 6 == 0 } else { flags >> 6 != 0 };
         let len = if transformed { base128(file, &mut at)? } else { orig };
-        out.push(Woff2Table { transformed_glyf: is_glyf && transformed, len });
-    }
-    Some((out, at))
-}
-
-/// Largest table directories a WOFF2 collection may rebuild, in bytes. Each font's directory is
-/// 16 bytes per table it lists, while the file spends as little as one byte per listed table, so
-/// a collection listing the same tables over and over rebuilt hundreds of megabytes of
-/// directories (twice: built, then copied into the font) before the decoder's output cap was
-/// checked. Real collections need kilobytes.
-const MAX_WOFF2_COLLECTION_HEADER: usize = 16 << 20;
-
-/// Why a WOFF2 collection whose directories are too large, or list a table twice, is refused.
-const BAD_COLLECTION: &str = "the collection's font directories are too large or list a table twice";
-
-/// WOFF2 collections: the table directories the decoder rebuilds for its fonts must fit
-/// [`MAX_WOFF2_COLLECTION_HEADER`], and no font may list a table twice (OpenType allows one
-/// table per tag in a font). Checked before decoding, since the decoder builds them before it
-/// checks its output size. A directory that doesn't parse is left to the decoder to report.
-fn check_woff2_collection(file: &[u8]) -> Result<(), UserFontError> {
-    if file.get(4..8) != Some(b"ttcf".as_slice()) {
-        return Ok(());
-    }
-    match woff2_collection_fits(file) {
-        Some(false) => Err(UserFontError::BadWebFont(BAD_COLLECTION.into())),
-        _ => Ok(()),
-    }
-}
-
-/// Do the collection's rebuilt table directories fit, with no table listed twice in one font?
-/// None when the directories don't parse.
-fn woff2_collection_fits(file: &[u8]) -> Option<bool> {
-    let (tables, mut at) = woff2_directory(file)?;
-    let version = u32::from_be_bytes(file.get(at..at.checked_add(4)?)?.try_into().ok()?);
-    at += 4;
-    let fonts = read_255_u16(file, &mut at)?;
-    // TTC header (with the DSIG fields of version 2) and one offset per font.
-    let dsig = if version == 0x0002_0000 { 12 } else { 0 };
-    let mut size = 12 + dsig + 4 * fonts;
-    let mut indices: Vec<usize> = Vec::new();
-    for _ in 0..fonts {
-        let n = read_255_u16(file, &mut at)?;
-        size = size.saturating_add(12 + 16 * n);
-        if size > MAX_WOFF2_COLLECTION_HEADER {
-            return Some(false);
-        }
-        at = at.checked_add(4)?; // flavor
-        indices.clear();
-        for _ in 0..n {
-            let i = read_255_u16(file, &mut at)?;
-            if i >= tables.len() {
-                return None;
-            }
-            indices.push(i);
-        }
-        indices.sort_unstable();
-        if indices.windows(2).any(|w| w[0] == w[1]) {
-            return Some(false);
+        let end = offset.checked_add(len)?;
+        if is_glyf && transformed {
+            glyf.push(stream.get(offset..end)?);
         }
+        offset = end;
     }
-    Some(true)
-}
-
-/// WOFF2's 255UInt16.
-fn read_255_u16(b: &[u8], at: &mut usize) -> Option<usize> {
-    let mut byte = || {
-        *at += 1;
-        b.get(*at - 1).copied().map(usize::from)
-    };
-    Some(match byte()? {
-        253 => byte()? << 8 | byte()?,
-        254 => byte()? + 253 * 2,
-        255 => byte()? + 253,
-        v => v,
-    })
+    Some(glyf)
 }
 
 /// WOFF2's UIntBase128.
@@ -368,7 +278,19 @@ fn glyf_points_fit(t: &[u8]) -> Option<bool> {
         let n = u16::from_be_bytes(contours.get(2 * g..2 * g + 2)?.try_into().ok()?);
         let mut total = 0usize;
         for _ in 0..if n == 0xFFFF { 0 } else { n } {
-            total += read_255_u16(points, &mut at)?;
+            // 255UInt16
+            let code = *points.get(at)?;
+            at += 1;
+            let mut byte = || {
+                at += 1;
+                points.get(at - 1).copied().map(usize::from)
+            };
+            total += match code {
+                253 => byte()? << 8 | byte()?,
+                254 => byte()? + 253 * 2,
+                255 => byte()? + 253,
+                v => usize::from(v),
+            };
             if total > 1 << 16 {
                 return Some(false);
             }

crates/fonts/src/fontdb/user/tests.rs

@@ -455,50 +455,3 @@ fn fonts_stored_at_once_under_one_name_each_get_their_own_file() {
     }
     let _ = std::fs::remove_dir_all(&dir);
 }
-
-/// A WOFF2 collection of `tables` untransformed tables whose fonts list the tables in `fonts`.
-fn woff2_collection(tables: usize, fonts: &[Vec<u16>]) -> Vec<u8> {
-    fn u255(v: u16, out: &mut Vec<u8>) {
-        match v {
-            0..=252 => out.push(v as u8),
-            _ => {
-                out.push(253);
-                out.extend_from_slice(&v.to_be_bytes());
-            }
-        }
-    }
-    let mut dir = Vec::new();
-    for i in 0..tables {
-        dir.push(63);
-        dir.extend_from_slice(&(i as u32).to_be_bytes()); // a made-up tag per table
-        base128(4, &mut dir);
-    }
-    dir.extend_from_slice(&0x0001_0000u32.to_be_bytes());
-    u255(fonts.len() as u16, &mut dir);
-    for font in fonts {
-        u255(font.len() as u16, &mut dir);
-        dir.extend_from_slice(&[0, 1, 0, 0]);
-        for &i in font {
-            u255(i, &mut dir);
-        }
-    }
-    woff2_file(b"ttcf", tables, &dir, &vec![0; 4 * tables], 4 * tables + 1024)
-}
-
-#[test]
-fn a_woff2_collection_rebuilding_huge_directories_is_refused_before_decoding() {
-    // Each font's rebuilt directory takes 16 bytes per table it lists, the file about two: 600
-    // fonts listing 2,000 tables each come to 19 MB of directories from a 2.4 MB file.
-    let all: Vec<u16> = (0..2_000).collect();
-    let file = woff2_collection(2_000, &vec![all; 600]);
-    assert_eq!(decode_font_file(&file), Err(UserFontError::BadWebFont(BAD_COLLECTION.into())));
-}
-
-#[test]
-fn a_woff2_collection_font_listing_a_table_twice_is_refused() {
-    let file = woff2_collection(3, &[vec![0, 1, 2], vec![0, 1, 1]]);
-    assert_eq!(decode_font_file(&file), Err(UserFontError::BadWebFont(BAD_COLLECTION.into())));
-    // Fonts sharing tables are what collections are for: passed on to the decoder.
-    let file = woff2_collection(3, &[vec![0, 1, 2], vec![0, 1, 2]]);
-    assert_ne!(decode_font_file(&file), Err(UserFontError::BadWebFont(BAD_COLLECTION.into())));
-}

crates/layout/src/para/lines.rs

@@ -90,6 +90,8 @@ struct Scan {
     j: usize,
     /// Tab cluster, stop, and x where the tab started.
     pending_tab: Option<(usize, TabStop, f32)>,
+    /// The text after a pending decimal tab looked at so far for its '.'.
+    decimal: Option<DecimalScan>,
     /// The width of the spaces so far on this line.
     space_w: f32,
     has_tab: bool,
@@ -111,17 +113,15 @@ fn takes_room(c: &Cluster) -> bool {
     c.kind != ClKind::Marker && !(matches!(c.kind, ClKind::Object(_)) && c.adv == 0.0 && c.obj_h == 0.0)
 }
 
-/// The width up to the first '.' of the text after the tab at `tj`, up to cluster `j`.
-fn width_to_decimal(pl: &ParaLayout, tj: usize, j: usize) -> Option<f32> {
-    let mut w = 0.0;
-    for k in tj + 1..=j {
-        let cc = pl.clusters.get(k)?;
-        if pl_text_at(cc) {
-            return Some(w);
-        }
-        w += cc.adv;
-    }
-    None
+/// How far the text after a decimal tab has been looked at for its first '.' (see
+/// [`Scan::width_to_decimal`]): the tab, the next cluster to look at, the width before it, and
+/// whether that cluster is the '.'.
+#[derive(Clone, Copy, Default)]
+struct DecimalScan {
+    tab: usize,
+    next: usize,
+    width: f32,
+    found: bool,
 }
 
 /// The objects' exclusions mirrored across a line of `width`, for a right-to-left paragraph.
@@ -276,6 +276,7 @@ impl<'e> Breaker<'e> {
             end: LineEnd::Para,
             j: self.i,
             pending_tab: None,
+            decimal: None,
             space_w: 0.0,
             has_tab: false,
             skip: false,
@@ -839,6 +840,29 @@ impl Scan {
         false
     }
 
+    /// The width up to the first '.' of the text after the tab at `tj`, up to cluster `j`. The
+    /// text is shifted after each of its clusters, so the clusters already looked at are not
+    /// walked again: a long run without a '.' after a decimal tab is looked at once, not once
+    /// per cluster.
+    fn width_to_decimal(&mut self, pl: &ParaLayout, tj: usize, j: usize) -> Option<f32> {
+        let start = DecimalScan { tab: tj, next: tj + 1, width: 0.0, found: false };
+        let d = self.decimal.get_or_insert(start);
+        if d.tab != tj || d.next > j.saturating_add(1) {
+            *d = start;
+        }
+        while !d.found && d.next <= j {
+            crate::work::steps(1);
+            let cc = pl.clusters.get(d.next)?;
+            if pl_text_at(cc) {
+                d.found = true;
+            } else {
+                d.width += cc.adv;
+                d.next += 1;
+            }
+        }
+        d.found.then_some(d.width)
+    }
+
     /// Text after a decimal/centre/right tab shifts as it grows.
     fn shift_pending_tab(&mut self, pl: &mut ParaLayout) {
         let Some((tj, stop, tx)) = self.pending_tab else { return };
@@ -847,7 +871,7 @@ impl Scan {
             TabAlign::Right => stop.pos - tx - seg_w,
             TabAlign::Center => stop.pos - tx - seg_w / 2.0,
             // Width up to the first '.' in the segment.
-            TabAlign::Decimal => stop.pos - tx - width_to_decimal(pl, tj, self.j).unwrap_or(seg_w),
+            TabAlign::Decimal => stop.pos - tx - self.width_to_decimal(pl, tj, self.j).unwrap_or(seg_w),
             _ => 0.0,
         };
         let shift = shift.max(0.0);

crates/layout/src/tests/linear.rs

@@ -482,3 +482,25 @@ fn selecting_a_header_on_the_hinted_page_does_not_walk_every_page() {
     eprintln!("hinted header: {small} steps for 20 pages, {big} for 160");
     assert!(small > 0 && big <= small + 8, "the pages aren't walked: {small} → {big}");
 }
+
+/// A paragraph of a decimal tab at 200 pt followed by `text`.
+fn after_decimal_tab(text: &str) -> Document {
+    use wordcraft_doc::props::{TabAlign, TabStop};
+    let mut d = Document::from_text(&format!("\t{text}"));
+    let at = Pos::body(0, 0);
+    d.format_paragraphs(&at, &at, &|p| p.tabs = Some(vec![TabStop { pos: 200.0, align: TabAlign::Decimal, leader: Default::default() }])).unwrap();
+    d
+}
+
+/// The text after a decimal tab was looked at again from the tab for its '.' after each of its
+/// clusters, so a long run of clusters without a '.' (soft hyphens take no room, so they stay on
+/// one line) took quadratic time.
+#[test]
+fn text_after_a_decimal_tab_is_looked_at_once() {
+    let opts = LayoutOptions::default();
+    // The text after the tab still ends at the stop, where it ended before.
+    let l = lay(&after_decimal_tab("12.5"), &opts);
+    let (Some(end), Some(start)) = (l.caret(&Pos::body(0, 5)), l.caret(&Pos::body(0, 0))) else { panic!("no carets") };
+    assert!((end.x - start.x - 200.0).abs() < 1.0, "the text ends at the stop: {} from {}", end.x, start.x);
+    assert_layout_linear("decimal tab", 2000, |n| after_decimal_tab(&format!("1{}", "\u{AD}".repeat(n))), &opts);
+}