text: sort a paragraph's tab stops once and find the next by binary search

crates/av1/src/decoder.rs

@@ -425,8 +425,6 @@ impl Decoder {
 
     fn parse_obus(&mut self, data: &[u8], out: &mut Vec<(Output, usize, u32)>) -> Result<()> {
         let mut tu = 0usize;
-        // Repeated-frame outputs in `out`, counted as they are added rather than recounted per OBU.
-        let mut existing = out.iter().filter(|(o, _, _)| matches!(o, Output::Existing { .. })).count();
         let mut pos = 0;
         while pos < data.len() {
             let obu = parse_obu_unit(data, pos)?;
@@ -446,10 +444,9 @@ impl Decoder {
                 }
                 OBU_FRAME_HEADER_T | OBU_REDUNDANT_FRAME_HEADER_T | OBU_FRAME_T => {
                     if let Some(o) = self.frame_obu(&obu)? {
-                        if existing >= 32 {
+                        if out.iter().filter(|(o, _, _)| matches!(o, Output::Existing { .. })).count() >= 32 {
                             return Err(Error::Invalid("too many frame outputs in chunk"));
                         }
-                        existing += usize::from(matches!(o, Output::Existing { .. }));
                         out.push((o, tu, spatial_id));
                     }
                 }

crates/hevc/src/slice.rs

@@ -326,9 +326,7 @@ impl SliceHeader {
 
     /// entry_point_offset list (tiles / wavefront substreams).
     fn parse_entry_points(&mut self, r: &mut BitReader, pps: &Pps, sps: &Sps) -> Result<()> {
-        // A fresh list, not `clear()`: a dependent segment starts as a copy of its independent
-        // segment's header, and clearing would keep that copy's allocation for every segment.
-        self.entry_points = Vec::new();
+        self.entry_points.clear();
         if pps.tiles_enabled || pps.entropy_coding_sync {
             let n = r.read_ue()?;
             ensure!(n <= sps.pic_width_in_ctbs() * sps.pic_height_in_ctbs(), "num_entry_point_offsets out of range");

crates/text/src/breaking.rs

@@ -260,12 +260,15 @@ pub(crate) struct Tab {
     align: TabAlign,
 }
 
+/// The paragraph's tab stops in position order (a stop at no finite position is left out), so
+/// [`tab_advance`] finds the next one by binary search instead of a scan per tab.
 pub(crate) fn tabs_of(props: &ParaProps) -> Vec<Tab> {
-    props
+    let mut tabs: Vec<Tab> = props
         .tabs
         .as_ref()
         .map(|t| {
             t.iter()
+                .filter(|s| s.pos.is_finite())
                 .map(|s| Tab {
                     pos: s.pos,
                     align: match s.align.as_str() {
@@ -277,7 +280,9 @@ pub(crate) fn tabs_of(props: &ParaProps) -> Vec<Tab> {
                 })
                 .collect()
         })
-        .unwrap_or_default()
+        .unwrap_or_default();
+    tabs.sort_by(|a, b| a.pos.total_cmp(&b.pos));
+    tabs
 }
 
 /// Width of the text after the tab at cell `i` up to the next tab or line break, and the width of
@@ -301,16 +306,15 @@ pub(crate) fn tab_segment(cells: &[Cell], i: usize) -> (f64, f64) {
 /// (`seg`: its width, and its width before the decimal point) as the stop aligns it but never
 /// moving back, as PowerPoint does; past the last stop, to the next default stop.
 pub(crate) fn tab_advance(x: f64, stops: &[Tab], default_tab: f64, seg: (f64, f64)) -> f64 {
-    for s in stops {
-        if s.pos > x + 0.5 {
-            let to = s.pos - x;
-            return match s.align {
-                TabAlign::Left => to,
-                TabAlign::Right => (to - seg.0).max(0.0),
-                TabAlign::Center => (to - seg.0 / 2.0).max(0.0),
-                TabAlign::Decimal => (to - seg.1).max(0.0),
-            };
-        }
+    // `stops` is in position order (`tabs_of`): the next stop is the first past x.
+    if let Some(s) = stops.get(stops.partition_point(|s| s.pos <= x + 0.5)) {
+        let to = s.pos - x;
+        return match s.align {
+            TabAlign::Left => to,
+            TabAlign::Right => (to - seg.0).max(0.0),
+            TabAlign::Center => (to - seg.0 / 2.0).max(0.0),
+            TabAlign::Decimal => (to - seg.1).max(0.0),
+        };
     }
     let d = if default_tab > 1.0 { default_tab } else { 72.0 };
     let next = ((x / d).floor() + 1.0) * d;

crates/text/src/tests.rs

@@ -1416,6 +1416,16 @@ fn tab_stops_align_the_text_after_them() {
     assert!((l.lines[0].edges[4].0 - x0(&l) - 72.0).abs() < 0.01);
 }
 
+#[test]
+fn many_tabs_over_many_stops_lay_out_by_position() {
+    // 20,000 stops given out of order, and 2,000 tabs: each tab finds the next stop by position.
+    let mut stops: Vec<(f64, &str)> = (1..=20_000).rev().map(|k| (k as f64 * 0.05 + 30.0, "l")).collect();
+    stops.push((f64::NAN, "l"));
+    let text = "a\t".repeat(2_000);
+    let l = tabbed(&text, &stops, 1.0e6);
+    assert!((l.lines[0].edges[2].0 - l.inner.x0 - 30.05).abs() < 0.01, "{:?}", &l.lines[0].edges[..3]);
+}
+
 #[test]
 fn a_tab_past_the_end_moves_to_the_next_line() {
     // PowerPoint: "abcdefghij\tk\tl\tm…" in a narrow box puts the tab that doesn't fit on the next