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/geom/src/picture.rs

@@ -207,8 +207,7 @@ fn worst_coefficients(bytes: &[u8]) -> u64 {
 }
 
 /// The compression of a classic TIFF's first image (the one the image crate decodes): 1 when the
-/// tag is missing. None when the header can't be read, or when the tag appears more than once:
-/// the decoder keeps the last copy, so a harmless first one must not hide a JPEG one after it.
+/// tag is missing. None when the header can't be read.
 fn tiff_compression(bytes: &[u8]) -> Option<u16> {
     let le = match bytes.get(..4)? {
         b"II*\0" => true,
@@ -224,22 +223,21 @@ fn tiff_compression(bytes: &[u8]) -> Option<u16> {
         Some(if le { u32::from_le_bytes(b) } else { u32::from_be_bytes(b) })
     };
     let ifd = usize::try_from(u32_at(4)?).ok()?;
-    let mut found = None;
     for i in 0..usize::from(u16_at(ifd)?) {
         let entry = ifd.checked_add(2)?.checked_add(i.checked_mul(12)?)?;
         if u16_at(entry)? != 259 {
             continue;
         }
-        if found.is_some() || u32_at(entry.checked_add(4)?)? != 1 {
+        if u32_at(entry.checked_add(4)?)? != 1 {
             return None;
         }
-        found = Some(match u16_at(entry.checked_add(2)?)? {
-            3 => u16_at(entry.checked_add(8)?)?,
-            4 => u16::try_from(u32_at(entry.checked_add(8)?)?).ok()?,
-            _ => return None,
-        });
+        return match u16_at(entry.checked_add(2)?)? {
+            3 => u16_at(entry.checked_add(8)?),
+            4 => u16::try_from(u32_at(entry.checked_add(8)?)?).ok(),
+            _ => None,
+        };
     }
-    Some(found.unwrap_or(1))
+    Some(1)
 }
 
 /// A DIB with a V4 or V5 header in the layout the decoder reads. A 32-bit one whose alpha mask
@@ -412,19 +410,6 @@ mod tests {
         assert_eq!(tiff_compression(&be), Some(7), "big-endian: the short is left-justified");
         be.truncate(12);
         assert_eq!(tiff_compression(&be), None, "cut short");
-        // A second compression tag (the one the decoder keeps) can't hide behind an allowed first.
-        let mut twice = b"II*\0".to_vec();
-        twice.extend(8u32.to_le_bytes());
-        twice.extend(2u16.to_le_bytes());
-        for compression in [1u32, 7] {
-            twice.extend(259u16.to_le_bytes());
-            twice.extend(3u16.to_le_bytes());
-            twice.extend(1u32.to_le_bytes());
-            twice.extend(compression.to_le_bytes());
-        }
-        twice.extend(0u32.to_le_bytes());
-        assert_eq!(tiff_compression(&twice), None, "duplicate compression tags");
-        assert!(matches!(probe(&twice), Err(Refusal::Unsupported(_))));
         // An uncompressed TIFF reads as before.
         let tiff = encode(image::RgbImage::from_pixel(5, 3, image::Rgb([9, 8, 7])), ImageFormat::Tiff);
         assert_eq!(tiff_compression(&tiff), Some(1));

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());
+    }
+}