Render: evict the least recently used animation instead of clearing the GIF cache

crates/engine/src/cmd/review.rs

@@ -421,30 +421,23 @@ fn add_to_dictionary(_s: &mut Session, p: &Value) -> Result<Value> {
 /// Replace whole-word `from` with `to` in `text`; how many were replaced.
 fn replace_word(text: &mut String, from: &str, to: &str, all: bool) -> usize {
     let is_word = |c: char| c.is_alphanumeric() || c == '\'' || c == '’';
-    // The result is built in one pass; the text is not edited in place for every match.
-    let mut out = String::new();
-    let (mut n, mut at, mut copied) = (0, 0, 0);
+    let mut n = 0;
+    let mut at = 0;
     while let Some(i) = text.get(at..).and_then(|t| t.find(from)).map(|i| i + at) {
         let end = i + from.len();
-        // The character before the match as the edited text would have it.
-        let before = text.get(copied..i).and_then(|t| t.chars().next_back()).or_else(|| out.chars().next_back()).is_some_and(is_word);
+        let before = text.get(..i).and_then(|t| t.chars().next_back()).is_some_and(is_word);
         let after = text.get(end..).and_then(|t| t.chars().next()).is_some_and(is_word);
         if before || after {
             at = end;
             continue;
         }
-        out.push_str(text.get(copied..i).unwrap_or_default());
-        out.push_str(to);
+        text.replace_range(i..end, to);
         n += 1;
-        (at, copied) = (end, end);
+        at = i + to.len();
         if !all {
             break;
         }
     }
-    if n > 0 {
-        out.push_str(text.get(copied..).unwrap_or_default());
-        *text = out;
-    }
     n
 }
 
@@ -771,49 +764,6 @@ fn end_compare(s: &mut Session, _: &Value) -> Result<Value> {
 
 #[cfg(test)]
 mod tests {
-    /// The replacement as it ran before: edited in place for every match.
-    fn replace_word_in_place(text: &mut String, from: &str, to: &str, all: bool) -> usize {
-        let is_word = |c: char| c.is_alphanumeric() || c == '\'' || c == '’';
-        let mut n = 0;
-        let mut at = 0;
-        while let Some(i) = text.get(at..).and_then(|t| t.find(from)).map(|i| i + at) {
-            let end = i + from.len();
-            let before = text.get(..i).and_then(|t| t.chars().next_back()).is_some_and(is_word);
-            let after = text.get(end..).and_then(|t| t.chars().next()).is_some_and(is_word);
-            if before || after {
-                at = end;
-                continue;
-            }
-            text.replace_range(i..end, to);
-            n += 1;
-            at = i + to.len();
-            if !all {
-                break;
-            }
-        }
-        n
-    }
-
-    #[test]
-    fn replace_word_matches_the_in_place_version() {
-        let cases = [
-            ("a a b a", "a", "x", true),
-            ("aa a. a", "a", "bb", true),
-            ("a-a -a-", "-", "ab", true),
-            ("foo. foo.", "foo.", "", true),
-            ("it's it", "it", "so", true),
-            ("x.x. x.", "x.", "y", true),
-            ("a a a", "a", "b", false),
-            ("none", "z", "q", true),
-            ("é é", "é", "e", true),
-        ];
-        for (text, from, to, all) in cases {
-            let (mut a, mut b) = (text.to_string(), text.to_string());
-            let (na, nb) = (replace_word(&mut a, from, to, all), replace_word_in_place(&mut b, from, to, all));
-            assert_eq!((na, a), (nb, b), "{text:?} {from:?} -> {to:?}");
-        }
-    }
-
     use super::*;
     use serde_json::json;
 

crates/render/src/images.rs

@@ -37,7 +37,8 @@ struct Cache {
     bad_order: VecDeque<usize>,
     bad_bytes: usize,
     /// GIFs by bytes address and adjustments (`None`: not animated); the bytes stay alive with them.
-    anims: HashMap<(usize, u64), (Arc<Vec<u8>>, Option<Arc<Anim>>)>,
+    /// Decoded animations by (bytes, adjustments), each with the clock of its last use.
+    anims: HashMap<(usize, u64), (Arc<Vec<u8>>, Option<Arc<Anim>>, u64)>,
 }
 
 /// Longest side, total decoded size and frame count kept for one animated GIF; the largest canvas
@@ -432,16 +433,33 @@ fn anim(bytes: &Arc<Vec<u8>>, adj: &PictureAdjust) -> Option<Arc<Anim>> {
         return None;
     }
     let key = (Arc::as_ptr(bytes) as usize, adjust_key(adj));
-    if let Some(a) = with(|c| c.anims.get(&key).map(|e| e.1.clone())) {
+    let hit = with(|c| {
+        c.clock += 1;
+        let clock = c.clock;
+        c.anims.get_mut(&key).map(|e| {
+            e.2 = clock;
+            e.1.clone()
+        })
+    });
+    if let Some(a) = hit {
         return a;
     }
     let a = decode_anim(bytes, adj).map(Arc::new);
     with(|c| {
-        let held: usize = c.anims.values().filter_map(|e| e.1.as_ref()).map(|a| a.bytes()).sum();
-        if held + a.as_ref().map_or(0, |a| a.bytes()) > GIF_CACHE_BUDGET || c.anims.len() >= 64 {
-            c.anims.clear();
+        // Make room by dropping the least recently used animations, not every one of them, so a
+        // slide whose animations overflow the cache does not decode all of them again each frame.
+        let new = a.as_ref().map_or(0, |a| a.bytes());
+        loop {
+            let held: usize = c.anims.values().filter_map(|e| e.1.as_ref()).map(|a| a.bytes()).sum();
+            if held + new <= GIF_CACHE_BUDGET && c.anims.len() < 64 {
+                break;
+            }
+            let Some(oldest) = c.anims.iter().min_by_key(|(_, e)| e.2).map(|(k, _)| *k) else { break };
+            c.anims.remove(&oldest);
         }
-        c.anims.insert(key, (bytes.clone(), a.clone()));
+        c.clock += 1;
+        let clock = c.clock;
+        c.anims.insert(key, (bytes.clone(), a.clone(), clock));
     });
     a
 }
@@ -535,6 +553,26 @@ mod tests {
         out.into_inner()
     }
 
+    /// A two-frame GIF whose first pixel is `n`, so each one has its own bytes.
+    fn gif(n: u8) -> Arc<Vec<u8>> {
+        use image::codecs::gif::GifEncoder;
+        let frame = |c: u8| image::Frame::new(image::RgbaImage::from_pixel(2, 2, image::Rgba([n, c, 0, 255])));
+        let mut out = Vec::new();
+        GifEncoder::new(&mut out).encode_frames([frame(0), frame(255)]).expect("encode");
+        Arc::new(out)
+    }
+
+    #[test]
+    fn a_full_animation_cache_drops_the_oldest_entry_not_all_of_them() {
+        let adj = PictureAdjust::default();
+        let gifs: Vec<_> = (0..70).map(gif).collect();
+        for g in &gifs {
+            assert!(anim(g, &adj).is_some());
+        }
+        let (len, newest) = with(|c| (c.anims.len(), c.anims.contains_key(&(Arc::as_ptr(&gifs[69]) as usize, adjust_key(&adj)))));
+        assert!(newest && len >= 32, "{len} cached");
+    }
+
     #[test]
     fn rgba_conversion_is_refused_past_the_cap() {
         let png = grey_png(100, 50);