beamterm_core/gl/
glyph_cache.rs

1//! Glyph cache with partitioned regions for normal and double-width glyphs.
2//!
3//! - Two LRU caches: one for normal glyphs, one for double-width (emoji/CJK)
4//! - O(1) lookup, insert, and eviction
5//! - No bitmap needed - each region allocates sequentially then evicts LRU
6
7use beamterm_data::{FontStyle, Glyph};
8use compact_str::CompactString;
9use lru::LruCache;
10use unicode_width::UnicodeWidthStr;
11
12use crate::{
13    gl::atlas::{GlyphSlot, SlotId},
14    is_emoji,
15};
16
17/// Pre-allocated slots for normal-styled ASCII glyphs (0x20..0x7E)
18pub const ASCII_SLOTS: u16 = 0x7E - 0x20 + 1; // 95 slots for ASCII (0x20..0x7E)
19
20/// Normal glyphs: slots 0..2048
21const NORMAL_CAPACITY: usize = 2048;
22/// Double-width glyphs: slots 2048..4096 (1024 glyphs x 2 slots each)
23const WIDE_CAPACITY: usize = 1024;
24const WIDE_BASE: SlotId = NORMAL_CAPACITY as SlotId;
25
26pub(crate) type CacheKey = (CompactString, FontStyle);
27
28/// Glyph cache with separate regions for normal and double-width glyphs.
29///
30/// - Normal region: slots 0-2047 (2048 single-width glyphs)
31/// - Wide region: slots 2048-4095 (1024 double-width glyphs, 2 slots each)
32pub struct GlyphCache {
33    /// LRU for normal (single-width) glyphs
34    normal: LruCache<CacheKey, GlyphSlot>,
35    /// LRU for double-width glyphs
36    wide: LruCache<CacheKey, GlyphSlot>,
37    /// Next slot in normal region (0-2047)
38    normal_next: SlotId,
39    /// Next index in wide region (starts at 2048)
40    wide_next: SlotId,
41}
42
43impl GlyphCache {
44    pub fn new() -> Self {
45        Self {
46            normal: LruCache::unbounded(),
47            wide: LruCache::unbounded(),
48            normal_next: ASCII_SLOTS,
49            wide_next: WIDE_BASE,
50        }
51    }
52
53    /// Gets the slot for a glyph, marking it as recently used.
54    pub fn get(&mut self, key: &str, style: FontStyle) -> Option<GlyphSlot> {
55        let cache_key = (CompactString::new(key), style);
56
57        match () {
58            // ascii glyphs with normal font styles are always allocated (outside cache)
59            _ if key.len() == 1 && style == FontStyle::Normal => Some(GlyphSlot::Normal(
60                (key.chars().next().unwrap() as SlotId).saturating_sub(0x20),
61            )),
62
63            // ascii glyphs are always single-width
64            _ if key.len() == 1 => self.normal.get(&cache_key).copied(),
65
66            // emoji glyphs disregard style
67            _ if is_emoji(key) => self
68                .wide
69                .get(&(CompactString::new(key), FontStyle::Normal))
70                .copied(),
71
72            // double-width glyphs
73            _ if key.width() == 2 => self.wide.get(&cache_key).copied(),
74
75            // normal glyphs
76            _ => self.normal.get(&cache_key).copied(),
77        }
78    }
79
80    /// Inserts a glyph, returning its slot. Evicts LRU if region is full.
81    pub fn insert(&mut self, key: &str, style: FontStyle) -> (GlyphSlot, Option<CacheKey>) {
82        // avoid inserting ASCII normal glyphs into cache
83        if key.len() == 1 && style == FontStyle::Normal {
84            let slot =
85                GlyphSlot::Normal((key.chars().next().unwrap() as SlotId).saturating_sub(0x20));
86            return (slot, None);
87        }
88
89        let cache_key = (CompactString::new(key), style);
90        let is_emoji = is_emoji(key);
91
92        if is_emoji || key.width() == 2 {
93            // Check if already present
94            if let Some(&slot) = self.wide.get(&cache_key) {
95                return (slot, None);
96            }
97
98            // Allocate or evict
99            let (idx, evicted) =
100                if (self.wide_next as usize) < (NORMAL_CAPACITY + WIDE_CAPACITY * 2) {
101                    let idx = self.wide_next;
102                    self.wide_next += 2;
103                    (idx, None)
104                } else {
105                    let (evicted_key, evicted_slot) = self
106                        .wide
107                        .pop_lru()
108                        .expect("wide cache should not be empty when full");
109                    (evicted_slot.slot_id(), Some(evicted_key))
110                };
111
112            let slot = if is_emoji {
113                GlyphSlot::Emoji(idx | Glyph::EMOJI_FLAG)
114            } else {
115                GlyphSlot::Wide(idx)
116            };
117
118            self.wide.put(cache_key, slot);
119
120            (slot, evicted)
121        } else {
122            // Check if already present
123            if let Some(&slot) = self.normal.get(&cache_key) {
124                return (slot, None);
125            }
126
127            // Allocate or evict
128            let (slot, evicted) = if (self.normal_next as usize) < NORMAL_CAPACITY {
129                let slot = self.normal_next;
130                self.normal_next += 1;
131                (GlyphSlot::Normal(slot), None)
132            } else {
133                let (evicted_key, evicted_slot) = self
134                    .normal
135                    .pop_lru()
136                    .expect("normal cache should not be empty when full");
137                (evicted_slot, Some(evicted_key))
138            };
139
140            self.normal.put(cache_key, slot);
141            (slot, evicted)
142        }
143    }
144
145    /// Returns total number of cached glyphs.
146    pub fn len(&self) -> usize {
147        self.normal.len() + self.wide.len()
148    }
149
150    pub fn is_empty(&self) -> bool {
151        self.normal.is_empty() && self.wide.is_empty()
152    }
153
154    /// Clears all cached glyphs.
155    pub fn clear(&mut self) {
156        self.normal.clear();
157        self.wide.clear();
158
159        self.normal_next = ASCII_SLOTS;
160        self.wide_next = WIDE_BASE;
161    }
162}
163
164impl Default for GlyphCache {
165    fn default() -> Self {
166        Self::new()
167    }
168}
169
170impl std::fmt::Debug for GlyphCache {
171    fn fmt(&self, f: &mut std::fmt::Formatter<'_>) -> std::fmt::Result {
172        f.debug_struct("GlyphCache")
173            .field("normal", &self.normal.len())
174            .field("wide", &self.wide.len())
175            .finish()
176    }
177}
178
179#[cfg(test)]
180mod tests {
181    use super::*;
182
183    const S: FontStyle = FontStyle::Normal;
184
185    // First normal slot after reserved ASCII slots (0-94)
186    const FIRST_NORMAL_SLOT: SlotId = ASCII_SLOTS; // 95
187
188    // Emoji slots include EMOJI_FLAG (0x1000)
189    const EMOJI_SLOT_BASE: SlotId = WIDE_BASE | Glyph::EMOJI_FLAG; // 2048 | 4096 = 6144
190
191    #[test]
192    fn test_ascii_fast_path() {
193        // ASCII characters with Normal style use the fast path in get()
194        // They return slot = char - 0x20, without using the cache
195        let mut cache = GlyphCache::new();
196
197        // 'A' = 0x41, so slot = 0x41 - 0x20 = 33
198        assert_eq!(cache.get("A", S), Some(GlyphSlot::Normal(33)));
199        // ' ' = 0x20, so slot = 0
200        assert_eq!(cache.get(" ", S), Some(GlyphSlot::Normal(0)));
201        // '~' = 0x7E, so slot = 0x7E - 0x20 = 94
202        assert_eq!(cache.get("~", S), Some(GlyphSlot::Normal(94)));
203    }
204
205    #[test]
206    fn test_normal_insert_get() {
207        let mut cache = GlyphCache::new();
208
209        // Non-ASCII single-width character (uses cache, not fast path)
210        let (slot, evicted) = cache.insert("\u{2192}", S);
211        assert_eq!(slot, GlyphSlot::Normal(FIRST_NORMAL_SLOT));
212        assert!(evicted.is_none());
213
214        assert_eq!(
215            cache.get("\u{2192}", S),
216            Some(GlyphSlot::Normal(FIRST_NORMAL_SLOT))
217        );
218        assert!(cache.get("\u{2190}", S).is_none());
219    }
220
221    #[test]
222    fn test_wide_insert_get() {
223        let mut cache = GlyphCache::new();
224
225        let (slot1, _) = cache.insert("\u{1F680}", S);
226        let (slot2, _) = cache.insert("\u{1F3AE}", S);
227
228        // Emoji slots start at WIDE_BASE with EMOJI_FLAG, each takes 2 slots
229        assert_eq!(slot1, GlyphSlot::Emoji(EMOJI_SLOT_BASE));
230        assert_eq!(slot2, GlyphSlot::Emoji(EMOJI_SLOT_BASE + 2));
231
232        assert_eq!(
233            cache.get("\u{1F680}", S),
234            Some(GlyphSlot::Emoji(EMOJI_SLOT_BASE))
235        );
236        assert_eq!(
237            cache.get("\u{1F3AE}", S),
238            Some(GlyphSlot::Emoji(EMOJI_SLOT_BASE + 2))
239        );
240    }
241
242    #[test]
243    fn test_wide_cjk() {
244        let mut cache = GlyphCache::new();
245
246        let (slot1, _) = cache.insert("\u{4E2D}", S);
247        let (slot2, _) = cache.insert("\u{6587}", S);
248
249        // CJK wide slots start at WIDE_BASE (no emoji flag), each takes 2 slots
250        assert_eq!(slot1, GlyphSlot::Wide(WIDE_BASE));
251        assert_eq!(slot2, GlyphSlot::Wide(WIDE_BASE + 2));
252
253        assert_eq!(cache.get("\u{4E2D}", S), Some(GlyphSlot::Wide(WIDE_BASE)));
254        assert_eq!(
255            cache.get("\u{6587}", S),
256            Some(GlyphSlot::Wide(WIDE_BASE + 2))
257        );
258    }
259
260    #[test]
261    fn test_mixed_insert() {
262        let mut cache = GlyphCache::new();
263
264        // Use non-ASCII chars to test cache behavior (ASCII uses fast path)
265        let (s1, _) = cache.insert("\u{2192}", S);
266        let (s2, _) = cache.insert("\u{1F680}", S);
267        let (s3, _) = cache.insert("\u{2190}", S);
268
269        assert_eq!(s1, GlyphSlot::Normal(FIRST_NORMAL_SLOT));
270        assert_eq!(s2, GlyphSlot::Emoji(EMOJI_SLOT_BASE));
271        assert_eq!(s3, GlyphSlot::Normal(FIRST_NORMAL_SLOT + 1));
272
273        assert_eq!(
274            cache.get("\u{2192}", S),
275            Some(GlyphSlot::Normal(FIRST_NORMAL_SLOT))
276        );
277        assert_eq!(
278            cache.get("\u{1F680}", S),
279            Some(GlyphSlot::Emoji(EMOJI_SLOT_BASE))
280        );
281        assert_eq!(
282            cache.get("\u{2190}", S),
283            Some(GlyphSlot::Normal(FIRST_NORMAL_SLOT + 1))
284        );
285    }
286
287    #[test]
288    fn test_style_differentiation() {
289        let mut cache = GlyphCache::new();
290
291        // ASCII with Normal style uses fast path (not cache)
292        let (slot1, _) = cache.insert("A", FontStyle::Normal);
293        // ASCII with Bold style uses cache (not fast path which is Normal-only)
294        let (slot2, _) = cache.insert("A", FontStyle::Bold);
295
296        // Normal uses fast path: 'A' = 0x41 - 0x20 = 33
297        assert_eq!(slot1, GlyphSlot::Normal(33));
298        // Bold goes through cache
299        assert_eq!(slot2, GlyphSlot::Normal(FIRST_NORMAL_SLOT));
300
301        // get() for Normal style uses fast path: 'A' = 0x41 - 0x20 = 33
302        assert_eq!(
303            cache.get("A", FontStyle::Normal),
304            Some(GlyphSlot::Normal(33))
305        );
306        // get() for Bold uses cache
307        assert_eq!(
308            cache.get("A", FontStyle::Bold),
309            Some(GlyphSlot::Normal(FIRST_NORMAL_SLOT))
310        );
311    }
312
313    #[test]
314    fn test_reinsert_existing() {
315        let mut cache = GlyphCache::new();
316
317        // Use non-ASCII to test cache reinsert behavior
318        let (slot1, _) = cache.insert("\u{2192}", S);
319        let (slot2, evicted) = cache.insert("\u{2192}", S);
320
321        assert_eq!(slot1, slot2);
322        assert!(evicted.is_none());
323        assert_eq!(cache.len(), 1);
324        assert_eq!(
325            cache.get("\u{2192}", S),
326            Some(GlyphSlot::Normal(FIRST_NORMAL_SLOT))
327        );
328    }
329}
beamterm_core/gl/glyph_cache.rs

beamterm_core/gl/
glyph_cache.rs
