use std::collections::HashMap;
use std::hash::Hash;
use crate::font::FontId;
use crate::shaping::{ShapedGlyph, ShapedLine, TextMetrics};
pub const DEFAULT_MEMORY_BUDGET: usize = 16 * 1024 * 1024;
#[derive(Copy, Clone, Debug, PartialEq, Eq, Hash)]
pub struct FontSizeBits(pub u32);
impl FontSizeBits {
#[inline(always)]
pub fn from_f32(size: f32) -> Self {
Self(size.to_bits())
}
#[inline(always)]
pub fn to_f32(self) -> f32 {
f32::from_bits(self.0)
}
}
#[derive(Copy, Clone, Debug, PartialEq, Eq, Hash)]
pub struct TextHash(pub u64);
impl TextHash {
pub fn from_bytes(bytes: &[u8]) -> Self {
let mut hash = 0xcbf29ce484222325u64;
for &byte in bytes {
hash = (hash ^ byte as u64).wrapping_mul(0x100000001b3);
}
Self(hash)
}
#[inline]
pub fn from_string(text: &str) -> Self {
Self::from_bytes(text.as_bytes())
}
}
#[derive(Copy, Clone, Debug, PartialEq, Eq, Hash)]
pub struct ShapeCacheKey {
pub font_id: FontId,
pub font_size_bits: FontSizeBits,
pub text_hash: TextHash,
pub max_width_bits: MaxWidthBits,
pub family_hash: TextHash,
pub line_height_bits: LineHeightBits,
}
#[derive(Copy, Clone, Debug, PartialEq, Eq, Hash)]
pub struct MaxWidthBits(pub u32);
impl MaxWidthBits {
#[inline]
pub fn from_opt(width: Option<f32>) -> Self {
match width {
Some(w) if w.is_finite() && w > 0.0 => Self(w.to_bits()),
Some(w) if w.is_finite() && w <= 0.0 => Self(0),
_ => Self(u32::MAX),
}
}
#[inline]
pub fn to_opt(self) -> Option<f32> {
if self.0 == u32::MAX {
None
} else if self.0 == 0 {
Some(0.0)
} else {
Some(f32::from_bits(self.0))
}
}
}
#[derive(Copy, Clone, Debug, PartialEq, Eq, Hash)]
pub struct LineHeightBits(pub u32);
impl LineHeightBits {
#[inline]
pub fn from_f32(line_height: f32) -> Self {
if line_height.is_finite() && line_height > 0.0 {
Self(line_height.to_bits())
} else {
Self(0)
}
}
#[inline]
pub fn to_f32(self) -> f32 {
if self.0 == 0 {
0.0
} else {
f32::from_bits(self.0)
}
}
}
impl ShapeCacheKey {
#[inline]
pub fn new(font_id: FontId, font_size: f32, text: &str) -> Self {
Self::with_max_width_and_family(font_id, font_size, text, None, "", 0.0)
}
#[inline]
pub fn with_max_width(
font_id: FontId,
font_size: f32,
text: &str,
max_width: Option<f32>,
) -> Self {
Self::with_max_width_and_family(font_id, font_size, text, max_width, "", 0.0)
}
#[inline]
pub fn with_max_width_and_family(
font_id: FontId,
font_size: f32,
text: &str,
max_width: Option<f32>,
family: &str,
line_height: f32,
) -> Self {
Self {
font_id,
font_size_bits: FontSizeBits::from_f32(font_size),
text_hash: TextHash::from_string(text),
max_width_bits: MaxWidthBits::from_opt(max_width),
family_hash: TextHash::from_string(family),
line_height_bits: LineHeightBits::from_f32(line_height),
}
}
}
#[derive(Clone, Debug)]
pub struct CachedShape {
pub lines: Vec<ShapedLine>,
pub metrics: TextMetrics,
pub mem_size: usize,
}
impl CachedShape {
pub fn new(lines: Vec<ShapedLine>, metrics: TextMetrics) -> Self {
let mem_size = Self::estimate_mem_size(&lines);
Self {
lines,
metrics,
mem_size,
}
}
fn estimate_mem_size(lines: &[ShapedLine]) -> usize {
let mut total = std::mem::size_of::<TextMetrics>() + std::mem::size_of::<usize>();
for line in lines {
total += std::mem::size_of::<ShapedLine>();
total += line.text.capacity();
total += line.glyphs.len() * std::mem::size_of::<ShapedGlyph>();
}
total
}
}
pub struct TextShapeCache {
entries: HashMap<ShapeCacheKey, (u64, CachedShape)>,
age: u64,
total_mem: usize,
budget: usize,
hits: u64,
misses: u64,
}
impl Default for TextShapeCache {
fn default() -> Self {
Self::new(DEFAULT_MEMORY_BUDGET)
}
}
impl TextShapeCache {
pub fn new(budget: usize) -> Self {
Self {
entries: HashMap::new(),
age: 0,
total_mem: 0,
budget,
hits: 0,
misses: 0,
}
}
#[inline]
pub fn with_default_budget() -> Self {
Self::default()
}
#[inline]
pub fn len(&self) -> usize {
self.entries.len()
}
#[inline]
pub fn is_empty(&self) -> bool {
self.entries.is_empty()
}
#[inline]
pub fn total_memory(&self) -> usize {
self.total_mem
}
#[inline]
pub fn budget(&self) -> usize {
self.budget
}
#[inline]
pub fn hits(&self) -> u64 {
self.hits
}
#[inline]
pub fn misses(&self) -> u64 {
self.misses
}
#[inline]
pub fn hit_rate(&self) -> f64 {
let total = self.hits + self.misses;
if total == 0 {
0.0
} else {
self.hits as f64 / total as f64
}
}
pub fn get(&mut self, key: &ShapeCacheKey) -> Option<&CachedShape> {
if let Some((entry_age, shape)) = self.entries.get_mut(key) {
*entry_age = self.age;
self.age += 1;
self.hits += 1;
Some(shape)
} else {
self.misses += 1;
None
}
}
pub fn insert(&mut self, key: ShapeCacheKey, shape: CachedShape) {
let mem_size = shape.mem_size;
if let Some((_, old)) = self.entries.remove(&key) {
self.total_mem = self.total_mem.saturating_sub(old.mem_size);
}
while self.total_mem + mem_size > self.budget && !self.entries.is_empty() {
self.evict_oldest();
}
self.total_mem += mem_size;
self.entries.insert(key, (self.age, shape));
self.age += 1;
}
fn evict_oldest(&mut self) {
if let Some(&oldest_key) = self
.entries
.iter()
.min_by_key(|(_, (age, _))| *age)
.map(|(k, _)| k)
{
if let Some((_, removed)) = self.entries.remove(&oldest_key) {
self.total_mem = self.total_mem.saturating_sub(removed.mem_size);
}
}
}
pub fn clear(&mut self) {
self.entries.clear();
self.total_mem = 0;
}
pub fn trim(&mut self, keep_age: u64) {
let current_age = self.age;
self.entries.retain(|_, (age, shape)| {
if *age + keep_age >= current_age {
true
} else {
self.total_mem = self.total_mem.saturating_sub(shape.mem_size);
false
}
});
}
pub fn invalidate_font(&mut self, font_id: FontId) {
self.entries.retain(|key, (_, shape)| {
if key.font_id == font_id {
self.total_mem = self.total_mem.saturating_sub(shape.mem_size);
false
} else {
true
}
});
}
pub fn invalidate_font_size(&mut self, font_size: f32) {
let bits = FontSizeBits::from_f32(font_size);
self.entries.retain(|key, (_, shape)| {
if key.font_size_bits == bits {
self.total_mem = self.total_mem.saturating_sub(shape.mem_size);
false
} else {
true
}
});
}
pub fn resize(&mut self, new_budget: usize) {
self.budget = new_budget;
while self.total_mem > self.budget && !self.entries.is_empty() {
self.evict_oldest();
}
}
}
impl std::fmt::Debug for TextShapeCache {
fn fmt(&self, f: &mut std::fmt::Formatter<'_>) -> std::fmt::Result {
f.debug_struct("TextShapeCache")
.field("entries", &self.entries.len())
.field("total_mem", &self.total_mem)
.field("budget", &self.budget)
.field("hits", &self.hits)
.field("misses", &self.misses)
.field("hit_rate", &self.hit_rate())
.finish()
}
}
#[cfg(test)]
mod tests {
use super::*;
use crate::shaping::TextMetrics;
fn make_cached_shape(width: f32, height: f32, line_count: usize) -> CachedShape {
let metrics = TextMetrics {
width,
height,
line_count,
};
CachedShape::new(vec![], metrics)
}
fn make_key(_id: u32, size: f32, text: &str) -> ShapeCacheKey {
ShapeCacheKey::new(FontId(dummy_font_id()), size, text)
}
fn dummy_font_id() -> fontdb::ID {
fontdb::ID::dummy()
}
fn make_key_v2(_id_val: u64, size: f32, text: &str) -> ShapeCacheKey {
ShapeCacheKey::new(FontId(dummy_font_id()), size, text)
}
#[test]
fn make_key_v2_compiles() {
let _ = make_key_v2(1, 16.0, "test");
}
#[test]
fn font_size_bits_roundtrip() {
let bits = FontSizeBits::from_f32(16.0);
assert_eq!(bits.to_f32(), 16.0);
let bits_nan = FontSizeBits::from_f32(f32::NAN);
assert!(bits_nan.to_f32().is_nan());
}
#[test]
fn text_hash_deterministic() {
let h1 = TextHash::from_string("Hello");
let h2 = TextHash::from_string("Hello");
assert_eq!(h1, h2);
let h3 = TextHash::from_string("World");
assert_ne!(h1, h3);
}
#[test]
fn text_hash_empty() {
let h = TextHash::from_string("");
assert_eq!(h.0, 0xcbf29ce484222325);
}
#[test]
fn cache_key_equality() {
let k1 = ShapeCacheKey::new(FontId(dummy_font_id()), 16.0, "Hello");
let k2 = ShapeCacheKey::new(FontId(dummy_font_id()), 16.0, "Hello");
assert_eq!(k1, k2);
}
#[test]
fn cache_key_differs_by_text() {
let k1 = ShapeCacheKey::new(FontId(dummy_font_id()), 16.0, "Hello");
let k2 = ShapeCacheKey::new(FontId(dummy_font_id()), 16.0, "World");
assert_ne!(k1, k2);
}
#[test]
fn cache_key_differs_by_font_size() {
let k1 = ShapeCacheKey::new(FontId(dummy_font_id()), 16.0, "Hello");
let k2 = ShapeCacheKey::new(FontId(dummy_font_id()), 20.0, "Hello");
assert_ne!(k1, k2);
}
#[test]
fn cache_new_is_empty() {
let cache = TextShapeCache::new(1024);
assert!(cache.is_empty());
assert_eq!(cache.len(), 0);
assert_eq!(cache.total_memory(), 0);
}
#[test]
fn cache_insert_and_get() {
let mut cache = TextShapeCache::new(1024 * 1024);
let key = ShapeCacheKey::new(FontId(dummy_font_id()), 16.0, "Hello");
let shape = make_cached_shape(100.0, 20.0, 1);
cache.insert(key, shape);
assert_eq!(cache.len(), 1);
let retrieved = cache.get(&key);
assert!(retrieved.is_some());
assert_eq!(retrieved.unwrap().metrics.width, 100.0);
}
#[test]
fn cache_miss_returns_none() {
let mut cache = TextShapeCache::new(1024 * 1024);
let key = ShapeCacheKey::new(FontId(dummy_font_id()), 16.0, "Hello");
assert!(cache.get(&key).is_none());
assert_eq!(cache.misses(), 1);
}
#[test]
fn cache_hit_rate() {
let mut cache = TextShapeCache::new(1024 * 1024);
let key = ShapeCacheKey::new(FontId(dummy_font_id()), 16.0, "Hello");
cache.insert(key, make_cached_shape(100.0, 20.0, 1));
cache.get(&key);
cache.get(&key);
let missing_key = ShapeCacheKey::new(FontId(dummy_font_id()), 16.0, "World");
cache.get(&missing_key);
assert_eq!(cache.hits(), 2);
assert_eq!(cache.misses(), 1);
assert!((cache.hit_rate() - 2.0 / 3.0).abs() < 0.001);
}
#[test]
fn cache_eviction_on_budget_exceeded() {
let mut cache = TextShapeCache::new(200); let key1 = ShapeCacheKey::new(FontId(dummy_font_id()), 16.0, "A");
let key2 = ShapeCacheKey::new(FontId(dummy_font_id()), 16.0, "B");
let key3 = ShapeCacheKey::new(FontId(dummy_font_id()), 16.0, "C");
cache.insert(key1, make_cached_shape(10.0, 10.0, 1));
cache.insert(key2, make_cached_shape(20.0, 10.0, 1));
cache.insert(key3, make_cached_shape(30.0, 10.0, 1));
assert!(
cache.total_memory() <= 200,
"total mem {} should be <= 200",
cache.total_memory()
);
}
#[test]
fn cache_lru_eviction_order() {
let mut cache = TextShapeCache::new(300);
let key1 = ShapeCacheKey::new(FontId(dummy_font_id()), 16.0, "A");
let key2 = ShapeCacheKey::new(FontId(dummy_font_id()), 16.0, "B");
let key3 = ShapeCacheKey::new(FontId(dummy_font_id()), 16.0, "C");
cache.insert(key1, make_cached_shape(10.0, 10.0, 1));
cache.insert(key2, make_cached_shape(20.0, 10.0, 1));
cache.get(&key1);
cache.insert(key3, make_cached_shape(30.0, 10.0, 1));
assert!(cache.get(&key1).is_some(), "key1 should still be present");
}
#[test]
fn cache_clear() {
let mut cache = TextShapeCache::new(1024 * 1024);
let key = ShapeCacheKey::new(FontId(dummy_font_id()), 16.0, "Hello");
cache.insert(key, make_cached_shape(100.0, 20.0, 1));
assert!(!cache.is_empty());
cache.clear();
assert!(cache.is_empty());
assert_eq!(cache.total_memory(), 0);
}
#[test]
fn cache_update_existing_entry() {
let mut cache = TextShapeCache::new(1024 * 1024);
let key = ShapeCacheKey::new(FontId(dummy_font_id()), 16.0, "Hello");
cache.insert(key, make_cached_shape(100.0, 20.0, 1));
cache.insert(key, make_cached_shape(200.0, 40.0, 2));
assert_eq!(cache.len(), 1, "should still have 1 entry");
let retrieved = cache.get(&key).unwrap();
assert_eq!(retrieved.metrics.width, 200.0);
assert_eq!(retrieved.metrics.line_count, 2);
}
#[test]
fn cache_invalidate_font() {
let mut cache = TextShapeCache::new(1024 * 1024);
let fid = FontId(dummy_font_id());
let key = ShapeCacheKey::new(fid, 16.0, "Hello");
cache.insert(key, make_cached_shape(100.0, 20.0, 1));
assert!(!cache.is_empty());
cache.invalidate_font(fid);
assert!(cache.is_empty());
}
#[test]
fn cache_invalidate_font_size() {
let mut cache = TextShapeCache::new(1024 * 1024);
let key16 = ShapeCacheKey::new(FontId(dummy_font_id()), 16.0, "Hello");
let key20 = ShapeCacheKey::new(FontId(dummy_font_id()), 20.0, "Hello");
cache.insert(key16, make_cached_shape(100.0, 20.0, 1));
cache.insert(key20, make_cached_shape(120.0, 24.0, 1));
assert_eq!(cache.len(), 2);
cache.invalidate_font_size(16.0);
assert_eq!(cache.len(), 1);
assert!(cache.get(&key20).is_some());
}
#[test]
fn cache_resize_evicts() {
let mut cache = TextShapeCache::new(1024 * 1024);
for i in 0..10 {
let key = ShapeCacheKey::new(FontId(dummy_font_id()), 16.0, &format!("text{i}"));
cache.insert(key, make_cached_shape(100.0, 20.0, 1));
}
assert!(cache.total_memory() > 0);
cache.resize(1);
assert!(
cache.total_memory() <= 1 || cache.is_empty(),
"total mem {} should be <= 1 or cache empty",
cache.total_memory()
);
}
#[test]
fn cache_trim_old_entries() {
let mut cache = TextShapeCache::new(1024 * 1024);
let key1 = ShapeCacheKey::new(FontId(dummy_font_id()), 16.0, "A");
let key2 = ShapeCacheKey::new(FontId(dummy_font_id()), 16.0, "B");
cache.insert(key1, make_cached_shape(10.0, 10.0, 1));
cache.insert(key2, make_cached_shape(20.0, 10.0, 1));
cache.get(&key2);
cache.trim(1);
assert!(cache.get(&key2).is_some());
}
#[test]
fn cache_debug_format() {
let cache = TextShapeCache::new(1024);
let debug = format!("{:?}", cache);
assert!(debug.contains("TextShapeCache"));
assert!(debug.contains("hit_rate"));
}
#[test]
fn cached_shape_mem_size_estimation() {
let shape = make_cached_shape(100.0, 20.0, 1);
let _ = shape.mem_size;
}
#[test]
fn cached_shape_with_lines() {
use crate::shaping::ShapedLine;
let line = ShapedLine {
text: "Hello".to_string(),
rtl: false,
line_y: 0.0,
line_top: 0.0,
line_height: 20.0,
line_w: 50.0,
glyphs: vec![],
};
let shape = CachedShape::new(
vec![line],
TextMetrics {
width: 50.0,
height: 20.0,
line_count: 1,
},
);
assert!(shape.mem_size > 0);
}
#[test]
fn make_key_compiles() {
let _ = make_key(1, 16.0, "test");
}
}