Proofing: look up unchecked runs by binary search, not a scan per issue

paragraph_issues dropped issues touching a run left unchecked by testing
every run of the paragraph against every issue. A paragraph can have many
runs and many issues within the proofing size limit, so the filter was
quadratic in the paragraph's size. The unchecked ranges are now merged and
sorted once, each issue is looked up by binary search, and paragraphs
without unchecked runs skip the filter.

crates/layout/src/para/lines.rs

@@ -90,8 +90,6 @@ 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,
@@ -113,15 +111,17 @@ fn takes_room(c: &Cluster) -> bool {
     c.kind != ClKind::Marker && !(matches!(c.kind, ClKind::Object(_)) && c.adv == 0.0 && c.obj_h == 0.0)
 }
 
-/// 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 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
 }
 
 /// The objects' exclusions mirrored across a line of `width`, for a right-to-left paragraph.
@@ -276,7 +276,6 @@ impl<'e> Breaker<'e> {
             end: LineEnd::Para,
             j: self.i,
             pending_tab: None,
-            decimal: None,
             space_w: 0.0,
             has_tab: false,
             skip: false,
@@ -840,29 +839,6 @@ 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 };
@@ -871,7 +847,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 - self.width_to_decimal(pl, tj, self.j).unwrap_or(seg_w),
+            TabAlign::Decimal => stop.pos - tx - width_to_decimal(pl, tj, self.j).unwrap_or(seg_w),
             _ => 0.0,
         };
         let shift = shift.max(0.0);

crates/layout/src/para/proof.rs

@@ -46,8 +46,37 @@ pub fn paragraph_issues(
     }
     let text = proof_text(p);
     let spans: Vec<(std::ops::Range<usize>, wordcraft_proof::ProofLang)> = runs.iter().map(|r| (r.range.clone(), r.lang)).collect();
-    let skip = |a: usize, b: usize| runs.iter().any(|r| r.skip && r.range.start < b && a < r.range.end);
-    wordcraft_proof::check_text_with(&text, &spans, spelling, grammar, list_item).into_iter().filter(|i| !skip(i.start, i.end)).collect()
+    let skipped = skipped_ranges(runs);
+    let issues = wordcraft_proof::check_text_with(&text, &spans, spelling, grammar, list_item);
+    if skipped.is_empty() {
+        return issues;
+    }
+    issues.into_iter().filter(|i| !overlaps(&skipped, i.start, i.end)).collect()
+}
+
+/// The byte ranges of the runs left unchecked, in order, those that overlap merged: their
+/// starts and ends both rise, so [`overlaps`] finds an issue's by binary search instead of
+/// looking at every run for every issue.
+fn skipped_ranges(runs: &[ProofRun]) -> Vec<(usize, usize)> {
+    let mut ranges: Vec<(usize, usize)> = runs.iter().filter(|r| r.skip).map(|r| (r.range.start, r.range.end)).collect();
+    ranges.sort_unstable();
+    let mut merged: Vec<(usize, usize)> = Vec::with_capacity(ranges.len());
+    for (s, e) in ranges {
+        crate::work::steps(1);
+        match merged.last_mut() {
+            Some(last) if s < last.1 => last.1 = last.1.max(e),
+            _ => merged.push((s, e)),
+        }
+    }
+    merged
+}
+
+/// Whether bytes `a..b` overlap one of `skipped` ([`skipped_ranges`]): the first range ending
+/// after `a` is the only one that can, as every later one starts no earlier.
+fn overlaps(skipped: &[(usize, usize)], a: usize, b: usize) -> bool {
+    crate::work::steps(1);
+    let k = skipped.partition_point(|&(_, e)| e <= a);
+    skipped.get(k).is_some_and(|&(s, _)| s < b)
 }
 
 /// Whether the paragraph is a list item: its own numbering, or its style's, names a list (not 0).
@@ -101,3 +130,26 @@ pub fn proof_text(p: &wordcraft_doc::Paragraph) -> String {
     }
     out
 }
+
+#[cfg(test)]
+mod tests {
+    use super::*;
+
+    fn run(range: std::ops::Range<usize>, skip: bool) -> ProofRun {
+        ProofRun { range, lang: Default::default(), skip }
+    }
+
+    /// The lookup finds what a look at every run finds, overlapping and empty runs included.
+    #[test]
+    fn skipped_lookup_matches_a_scan_of_every_run() {
+        let runs = [run(0..4, false), run(4..9, true), run(5..6, true), run(9..9, true), run(9..12, false), run(12..20, true), run(14..30, true)];
+        let skipped = skipped_ranges(&runs);
+        for a in 0..32 {
+            for b in a..32 {
+                let scan = runs.iter().any(|r| r.skip && r.range.start < b && a < r.range.end);
+                assert_eq!(overlaps(&skipped, a, b), scan, "{a}..{b}");
+            }
+        }
+        assert!(skipped_ranges(&[run(0..5, false)]).is_empty());
+    }
+}

crates/layout/src/tests/linear.rs

@@ -482,25 +482,3 @@ 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);
-}