Read Aloud: look citations up by binary search, not a scan per character

Building the queue checked every character of the document against every
citation field, so a document with many citations made Read Aloud do
characters x citations comparisons before playback started.

The citation spans are now sorted and merged once, and each position is
looked up by binary search.

crates/engine/src/speech.rs

@@ -80,12 +80,12 @@ impl Utterance {
 pub fn sentences(doc: &Document, from: &Pos, to: Option<&Pos>, skip_citations: bool) -> Vec<Utterance> {
     let story = from.story;
     // Spans to leave out: whole range fields, both markers included.
-    let skipped: Vec<(Pos, Pos)> = if skip_citations {
+    let skipped = Spans::new(if skip_citations {
         doc.field_ranges(story).into_iter().filter(|r| is_citation_code(&r.instr)).map(|r| (r.start, r.end)).collect()
     } else {
         Vec::new()
-    };
-    let in_skipped = |p: &Pos| skipped.iter().any(|(a, b)| a <= p && p <= b);
+    });
+    let in_skipped = |p: &Pos| skipped.contains(p);
     let mut out = Vec::new();
     for path in doc.para_paths(story) {
         if path < from.path {
@@ -156,6 +156,36 @@ pub fn sentences(doc: &Document, from: &Pos, to: Option<&Pos>, skip_citations: b
     out
 }
 
+/// Spans of the document (both ends included), sorted and merged so a position is looked up by
+/// binary search: checking every character against every citation was quadratic in a document
+/// with many of them.
+struct Spans(Vec<(Pos, Pos)>);
+
+impl Spans {
+    fn new(mut spans: Vec<(Pos, Pos)>) -> Self {
+        spans.retain(|(a, b)| a <= b);
+        spans.sort();
+        let mut merged: Vec<(Pos, Pos)> = Vec::with_capacity(spans.len());
+        for (a, b) in spans {
+            match merged.last_mut() {
+                Some(last) if a <= last.1 => {
+                    if b > last.1 {
+                        last.1 = b;
+                    }
+                }
+                _ => merged.push((a, b)),
+            }
+        }
+        Spans(merged)
+    }
+
+    /// Is `p` inside one of the spans?
+    fn contains(&self, p: &Pos) -> bool {
+        let after = self.0.partition_point(|(a, _)| a <= p);
+        after.checked_sub(1).and_then(|i| self.0.get(i)).is_some_and(|(_, b)| p <= b)
+    }
+}
+
 /// The language of `text` from its script, as a BCP 47 primary tag: Cyrillic is Russian (Ukrainian
 /// with one of its letters `іїєґ`), Greek, Arabic, Hebrew, Thai and Hangul map to `el`, `ar`, `he`, `th`
 /// and `ko`, kana to Japanese, Han letters alone to Chinese. `None` for Latin text (the script

crates/engine/src/speech/tests.rs

@@ -364,3 +364,35 @@ fn macos_voice_matches_the_language() {
     assert_eq!(mac_voice("ru", "", "en"), None);
     assert_eq!(mac_voice("ru", "garbage line\n\n  \n", "en"), None);
 }
+
+#[test]
+fn skipped_spans_match_a_scan_of_every_span() {
+    // Overlapping, nested, touching, empty-range and reversed spans.
+    let raw = vec![
+        (Pos::body(0, 5), Pos::body(0, 9)),
+        (Pos::body(0, 7), Pos::body(0, 12)),
+        (Pos::body(0, 20), Pos::body(0, 20)),
+        (Pos::body(0, 30), Pos::body(2, 3)),
+        (Pos::body(1, 4), Pos::body(1, 8)),
+        (Pos::body(3, 9), Pos::body(3, 2)),
+        (Pos::body(4, 0), Pos::body(4, 1)),
+        (Pos::body(4, 2), Pos::body(4, 3)),
+    ];
+    let spans = Spans::new(raw.clone());
+    for block in 0..6 {
+        for off in 0..40 {
+            let p = Pos::body(block, off);
+            let scan = raw.iter().any(|(a, b)| *a <= p && p <= *b);
+            assert_eq!(spans.contains(&p), scan, "{p:?}");
+        }
+    }
+}
+
+#[test]
+fn many_citations_are_looked_up_quickly() {
+    // 50,000 disjoint spans and 200,000 lookups: a scan of every span per position would take
+    // ten billion comparisons.
+    let spans = Spans::new((0..50_000).map(|i| (Pos::body(0, i * 4), Pos::body(0, i * 4 + 1))).collect());
+    let hits = (0..200_000).filter(|&off| spans.contains(&Pos::body(0, off))).count();
+    assert_eq!(hits, 100_000);
+}