Skip to main content

alpha2_text/
animated.rs

1//! Per-cluster animation states (motion and color) for text animators.
2//!
3//! [`TextRasterizer::layout`] reports where each cluster lies so a caller can compute states;
4//! [`TextRasterizer::rasterize_animated`] draws with them. Tracking re-aligns a line but never
5//! re-wraps it.
6//!
7//! Outlines are transformed before rasterizing, so scaled or rotated glyphs stay sharp. Each
8//! cluster is drawn into its own tile and tiles combine by maximum coverage, taking color from the
9//! winning cluster; strokes work the same way. Color glyphs are drawn upright and resampled
10//! bilinearly in fixed point. Integer and `libm` arithmetic keep native and wasm output identical.
11
12use super::{
13    Drawing, Faces, HashMap, HostTexture, HostTexturePixels, Layout, PixelBox, PixelLook,
14    Premultiplication, RasterColorSpace, RequestLook, TextFill, TextRasterError, TextRasterRequest,
15    TextRasterResult, TextRasterizer, TextTexture, decoration_extents, dilate, disc_extent,
16    gradient, normalize_mapped, over, point, raster_bytes_per_pixel, raster_pixels, stroke_radius,
17    validate_request,
18};
19use std::ops::Range;
20use std::sync::Arc;
21use unicode_segmentation::UnicodeSegmentation;
22
23/// Cluster and line positions, matching [`TextRasterizer::rasterize`].
24#[derive(Clone, Debug, PartialEq)]
25pub struct TextLayout {
26    /// Clusters (the unit of letter spacing) in logical order.
27    pub clusters: Vec<ClusterInfo>,
28    /// Lines, top to bottom.
29    pub lines: Vec<LineInfo>,
30    /// Font size in pixels.
31    pub font_size: f32,
32}
33
34/// One cluster of a [`TextLayout`].
35#[derive(Clone, Debug, PartialEq)]
36pub struct ClusterInfo {
37    /// Byte range in the request's text.
38    pub bytes: Range<usize>,
39    /// Line index.
40    pub line: u32,
41    /// Index of its UAX #29 word, counting only words with a letter or digit; `None` for spaces
42    /// and punctuation between words.
43    pub word: Option<u32>,
44    /// Whether it holds only white space.
45    pub is_space: bool,
46    /// Start of its advance in pixels from the layout box's left edge.
47    pub x: f32,
48    /// Advance in pixels; zero for a space hanging at a line end.
49    pub advance: f32,
50    /// Line baseline in pixels from the layout box's top.
51    pub baseline: f32,
52    /// Whether it is the ellipsis a [`crate::TextClamp`] ends a cut line with. Its byte range
53    /// is empty, at the cut, and it is in no word.
54    pub ellipsis: bool,
55}
56
57/// One line of a [`TextLayout`].
58#[derive(Clone, Debug, PartialEq)]
59pub struct LineInfo {
60    /// Cluster indices, in logical order.
61    pub clusters: Range<usize>,
62    /// Start in pixels from the layout box's left edge.
63    pub left: f32,
64    /// Advance excluding trailing spaces.
65    pub width: f32,
66    /// Baseline in pixels from the layout box's top.
67    pub baseline: f32,
68}
69
70/// A color change `base * keep + add` in premultiplied linear light. Mixing toward a target by
71/// `w` is `keep = 1 - w`, `add = w * target`; mixes compose.
72#[derive(Copy, Clone, Debug, PartialEq)]
73pub struct ColorMix {
74    /// Factor on the base color, in `[0, 1]`.
75    pub keep: f32,
76    /// Premultiplied linear-light RGBA in `[0, 1]`.
77    pub add: [f32; 4],
78}
79
80/// Largest scale of a [`ClusterState`] on either axis.
81pub const MAX_CLUSTER_SCALE: f32 = 10.0;
82
83/// Animation state of one cluster.
84#[derive(Copy, Clone, Debug, PartialEq)]
85pub struct ClusterState {
86    /// Translation in pixels, +y down.
87    pub offset: [f32; 2],
88    /// Scale about its center, in `[0, MAX_CLUSTER_SCALE]`.
89    pub scale: [f32; 2],
90    /// Clockwise rotation about its center, in radians.
91    pub rotation: f32,
92    /// Multiplies fill and stroke coverage, in `[0, 1]`.
93    pub opacity: f32,
94    /// Fill color change; `None` keeps it.
95    pub fill: Option<ColorMix>,
96    /// Stroke color change; `None` keeps them.
97    pub stroke: Option<ColorMix>,
98    /// Extra space after the cluster in pixels, like letter spacing.
99    pub tracking: f32,
100}
101
102impl ClusterState {
103    /// No change.
104    pub const IDENTITY: Self = Self {
105        offset: [0.0, 0.0],
106        scale: [1.0, 1.0],
107        rotation: 0.0,
108        opacity: 1.0,
109        fill: None,
110        stroke: None,
111        tracking: 0.0,
112    };
113
114    /// Whether the state changes nothing.
115    #[must_use]
116    pub fn is_identity(&self) -> bool {
117        *self == Self::IDENTITY
118    }
119
120    fn is_valid(&self) -> bool {
121        let mix = |mix: &Option<ColorMix>| {
122            mix.is_none_or(|mix| {
123                (0.0..=1.0).contains(&mix.keep)
124                    && mix.add.iter().all(|value| (0.0..=1.0).contains(value))
125            })
126        };
127        self.offset.iter().all(|value| value.is_finite())
128            && self
129                .scale
130                .iter()
131                .all(|value| (0.0..=MAX_CLUSTER_SCALE).contains(value))
132            && self.rotation.is_finite()
133            && (0.0..=1.0).contains(&self.opacity)
134            && self.tracking.is_finite()
135            && mix(&self.fill)
136            && mix(&self.stroke)
137    }
138}
139
140/// An affine map of layout pixels: `[a, b, c, d, e, f]` sends `(x, y)` to
141/// `(a x + c y + e, b x + d y + f)`.
142type Affine = [f32; 6];
143
144fn apply(affine: Affine, [x, y]: [f32; 2]) -> [f32; 2] {
145    [
146        affine[0] * x + affine[2] * y + affine[4],
147        affine[1] * x + affine[3] * y + affine[5],
148    ]
149}
150
151/// Scales and rotates about `pivot`, then translates by `offset`.
152fn cluster_affine(state: &ClusterState, pivot: [f32; 2]) -> Affine {
153    let (sine, cosine) = (libm::sinf(state.rotation), libm::cosf(state.rotation));
154    let [sx, sy] = state.scale;
155    // Rotation clockwise on screen, y down: x' = x cos - y sin, y' = x sin + y cos.
156    let (a, b, c, d) = (cosine * sx, sine * sx, -sine * sy, cosine * sy);
157    let [px, py] = pivot;
158    [
159        a,
160        b,
161        c,
162        d,
163        px - a * px - c * py + state.offset[0],
164        py - b * px - d * py + state.offset[1],
165    ]
166}
167
168fn invert(affine: Affine) -> Option<Affine> {
169    let determinant = affine[0] * affine[3] - affine[1] * affine[2];
170    if determinant.abs() <= f32::MIN_POSITIVE {
171        return None;
172    }
173    let (a, b, c, d) = (
174        affine[3] / determinant,
175        -affine[1] / determinant,
176        -affine[2] / determinant,
177        affine[0] / determinant,
178    );
179    Some([
180        a,
181        b,
182        c,
183        d,
184        -(a * affine[4] + c * affine[5]),
185        -(b * affine[4] + d * affine[5]),
186    ])
187}
188
189/// One cluster's coverage and color glyphs over a pixel rectangle (right and bottom exclusive)
190/// that may extend past the layout box.
191struct Tile {
192    left: i64,
193    top: i64,
194    width: usize,
195    height: usize,
196    coverage: Vec<u8>,
197    /// Premultiplied RGBA8, once a color glyph is drawn into it.
198    colors: Option<Vec<u8>>,
199}
200
201impl Tile {
202    fn empty() -> Self {
203        Self {
204            left: 0,
205            top: 0,
206            width: 0,
207            height: 0,
208            coverage: Vec::new(),
209            colors: None,
210        }
211    }
212
213    fn grow(&mut self, bounds: PixelBox) {
214        if self.width == 0 || self.height == 0 {
215            *self = Self {
216                left: bounds.left,
217                top: bounds.top,
218                width: usize::try_from(bounds.right - bounds.left).unwrap_or(0),
219                height: usize::try_from(bounds.bottom - bounds.top).unwrap_or(0),
220                coverage: Vec::new(),
221                colors: None,
222            };
223            self.coverage = vec![0; self.width * self.height];
224            return;
225        }
226        let right = (self.left + i64::try_from(self.width).unwrap_or(0)).max(bounds.right);
227        let bottom = (self.top + i64::try_from(self.height).unwrap_or(0)).max(bounds.bottom);
228        let (left, top) = (self.left.min(bounds.left), self.top.min(bounds.top));
229        if left == self.left
230            && top == self.top
231            && right == self.left + i64::try_from(self.width).unwrap_or(0)
232            && bottom == self.top + i64::try_from(self.height).unwrap_or(0)
233        {
234            return;
235        }
236        let width = usize::try_from(right - left).unwrap_or(0);
237        let height = usize::try_from(bottom - top).unwrap_or(0);
238        let (dx, dy) = (
239            usize::try_from(self.left - left).unwrap_or(0),
240            usize::try_from(self.top - top).unwrap_or(0),
241        );
242        let mut coverage = vec![0; width * height];
243        let mut colors = self.colors.as_ref().map(|_| vec![0; width * height * 4]);
244        for row in 0..self.height {
245            let to = (row + dy) * width + dx;
246            coverage[to..to + self.width]
247                .copy_from_slice(&self.coverage[row * self.width..(row + 1) * self.width]);
248            if let (Some(colors), Some(held)) = (&mut colors, &self.colors) {
249                colors[to * 4..(to + self.width) * 4]
250                    .copy_from_slice(&held[row * self.width * 4..(row + 1) * self.width * 4]);
251            }
252        }
253        *self = Self {
254            left,
255            top,
256            width,
257            height,
258            coverage,
259            colors,
260        };
261    }
262
263    fn index(&self, x: i64, y: i64) -> Option<usize> {
264        let (x, y) = (
265            usize::try_from(x - self.left).ok()?,
266            usize::try_from(y - self.top).ok()?,
267        );
268        (x < self.width && y < self.height).then_some(y * self.width + x)
269    }
270
271    fn bounds(&self) -> Option<PixelBox> {
272        (self.width > 0 && self.height > 0).then(|| PixelBox {
273            left: self.left,
274            top: self.top,
275            right: self.left + i64::try_from(self.width).unwrap_or(0),
276            bottom: self.top + i64::try_from(self.height).unwrap_or(0),
277        })
278    }
279}
280
281/// Pixel box of a glyph's font-unit `bounds` after placement and `affine`.
282#[allow(clippy::cast_possible_truncation)]
283fn mapped_box(bounds: [f32; 4], origin: [f32; 2], scale: f32, affine: Affine) -> PixelBox {
284    let [x_min, y_min, x_max, y_max] = bounds;
285    let corners = [
286        [x_min, y_min],
287        [x_max, y_min],
288        [x_min, y_max],
289        [x_max, y_max],
290    ]
291    .map(|[x, y]| apply(affine, [origin[0] + x * scale, origin[1] - y * scale]));
292    let (mut left, mut top, mut right, mut bottom) = (f32::MAX, f32::MAX, f32::MIN, f32::MIN);
293    for [x, y] in corners {
294        (left, top, right, bottom) = (left.min(x), top.min(y), right.max(x), bottom.max(y));
295    }
296    PixelBox {
297        left: left.floor() as i64,
298        top: top.floor() as i64,
299        right: right.ceil() as i64,
300        bottom: bottom.ceil() as i64,
301    }
302}
303
304/// Resamples an upright color glyph into `target` through `affine`, bilinear with 8-bit weights.
305#[allow(
306    clippy::cast_possible_truncation,
307    clippy::cast_possible_wrap,
308    clippy::cast_sign_loss,
309    clippy::cast_precision_loss,
310    clippy::many_single_char_names
311)]
312fn resample(rgba8: &[u8], source: PixelBox, target: PixelBox, inverse: Affine) -> Vec<u8> {
313    let source_width = usize::try_from(source.right - source.left).unwrap_or(0);
314    let source_height = usize::try_from(source.bottom - source.top).unwrap_or(0);
315    let width = usize::try_from(target.right - target.left).unwrap_or(0);
316    let height = usize::try_from(target.bottom - target.top).unwrap_or(0);
317    let mut out = vec![0_u8; width * height * 4];
318    let texel = |x: i64, y: i64| -> [u32; 4] {
319        if x < 0 || y < 0 || x >= source_width as i64 || y >= source_height as i64 {
320            return [0; 4];
321        }
322        let at = (y as usize * source_width + x as usize) * 4;
323        std::array::from_fn(|channel| u32::from(rgba8[at + channel]))
324    };
325    for row in 0..height {
326        for column in 0..width {
327            let [x, y] = apply(
328                inverse,
329                [
330                    (target.left + column as i64) as f32 + 0.5,
331                    (target.top + row as i64) as f32 + 0.5,
332                ],
333            );
334            // Texel space, with texel centres at whole numbers.
335            let (u, v) = (x - source.left as f32 - 0.5, y - source.top as f32 - 0.5);
336            let (u0, v0) = (u.floor(), v.floor());
337            let fx = ((u - u0) * 256.0) as u32;
338            let fy = ((v - v0) * 256.0) as u32;
339            let (u0, v0) = (u0 as i64, v0 as i64);
340            let [a, b, c, d] = [
341                texel(u0, v0),
342                texel(u0 + 1, v0),
343                texel(u0, v0 + 1),
344                texel(u0 + 1, v0 + 1),
345            ];
346            let at = (row * width + column) * 4;
347            for channel in 0..4 {
348                let top = a[channel] * (256 - fx) + b[channel] * fx;
349                let bottom = c[channel] * (256 - fx) + d[channel] * fx;
350                let value = (top * (256 - fy) + bottom * fy + 32_768) >> 16;
351                out[at + channel] = value.min(255) as u8;
352            }
353        }
354    }
355    out
356}
357
358fn mixed(color: [u8; 4], mix: &ColorMix) -> [u8; 4] {
359    let base = gradient::premultiplied_linear(color.map(|value| f32::from(value) / 255.0));
360    gradient::stored_rgba8(std::array::from_fn(|channel| {
361        base[channel] * mix.keep + mix.add[channel]
362    }))
363}
364
365/// Per-pixel color ownership: each pixel takes its colors from the cluster that gives it coverage.
366struct ClusterLook<'a> {
367    base: RequestLook<'a>,
368    states: &'a [ClusterState],
369    /// Owning cluster per pixel, `u32::MAX` for none.
370    fill_owner: Vec<u32>,
371    band_owner: Vec<Vec<u32>>,
372    /// The cluster whose color glyph was drawn last at each pixel.
373    color_owner: Vec<u32>,
374    solid: Vec<Option<[u8; 4]>>,
375    strokes: Vec<Vec<[u8; 4]>>,
376}
377
378impl PixelLook for ClusterLook<'_> {
379    fn fill(&self, index: usize, point: [f32; 2]) -> [u8; 4] {
380        let owner = self.fill_owner[index] as usize;
381        let Some(state) = self.states.get(owner) else {
382            return self.base.fill(index, point);
383        };
384        match (&self.base.gradient, state.fill) {
385            (Some(gradient), Some(mix)) => {
386                let base = gradient.linear_at(point);
387                gradient::stored_rgba8(std::array::from_fn(|channel| {
388                    base[channel] * mix.keep + mix.add[channel]
389                }))
390            }
391            (None, Some(_)) => self.solid[owner].unwrap_or(self.base.foreground),
392            (_, None) => self.base.fill(index, point),
393        }
394    }
395
396    fn band(&self, stroke: usize, index: usize) -> [u8; 4] {
397        let owner = self.band_owner[stroke][index] as usize;
398        self.strokes[stroke]
399            .get(owner)
400            .copied()
401            .unwrap_or_else(|| self.base.band(stroke, index))
402    }
403
404    /// Opacity of the owning cluster: fill, else color glyph, else innermost band.
405    #[allow(clippy::cast_possible_truncation, clippy::cast_sign_loss)]
406    fn fade(&self, index: usize) -> Option<u32> {
407        let owner = [self.fill_owner[index], self.color_owner[index]]
408            .into_iter()
409            .chain(self.band_owner.iter().map(|owners| owners[index]))
410            .find(|&owner| owner != u32::MAX)?;
411        let opacity = (self.states.get(owner as usize)?.opacity * 255.0).round() as u32;
412        (opacity < 255).then_some(opacity)
413    }
414}
415
416/// Writes `tile`'s coverage into `plane` where it is larger (ties go to the later cluster) and
417/// records `cluster` as the owner.
418fn place_max(
419    plane: (&mut [u8], &mut [u32], u32),
420    margin: [u32; 2],
421    tile: &Tile,
422    coverage: &[u8],
423    cluster: u32,
424) {
425    let (plane, owners, width) = plane;
426    let height = plane.len() / width.max(1) as usize;
427    for row in 0..tile.height {
428        let y = tile.top + i64::try_from(row).unwrap_or(0) + i64::from(margin[1]);
429        let Ok(y) = usize::try_from(y) else { continue };
430        if y >= height {
431            continue;
432        }
433        for column in 0..tile.width {
434            let value = coverage[row * tile.width + column];
435            if value == 0 {
436                continue;
437            }
438            let x = tile.left + i64::try_from(column).unwrap_or(0) + i64::from(margin[0]);
439            let Ok(x) = usize::try_from(x) else { continue };
440            if x >= width as usize {
441                continue;
442            }
443            let at = y * width as usize + x;
444            if value >= plane[at] {
445                plane[at] = value;
446                owners[at] = cluster;
447            }
448        }
449    }
450}
451
452impl TextRasterizer {
453    /// Lays out `request`'s clusters and lines as [`Self::rasterize`] would.
454    ///
455    /// # Errors
456    /// Returns the same errors as [`Self::rasterize`].
457    pub fn layout(&self, request: &TextRasterRequest) -> Result<TextLayout, TextRasterError> {
458        validate_request(request)?;
459        if self.fonts.is_empty() {
460            return Err(TextRasterError::NoFonts);
461        }
462        let faces = Faces::new(&self.fonts, request.font_weight)?;
463        let layout = self.lay_out(&faces, request)?;
464        Ok(text_layout(&layout, request))
465    }
466
467    /// [`Self::rasterize`] with one state per [`Self::layout`] cluster, in logical order. Identity
468    /// states match [`Self::rasterize`] exactly. Results are cached by content version, so give
469    /// each set of states its own version.
470    ///
471    /// # Errors
472    /// Returns [`TextRasterError::InvalidRequest`] when the state count or a value is out of
473    /// range, otherwise what [`Self::rasterize`] returns.
474    pub fn rasterize_animated(
475        &mut self,
476        request: &TextRasterRequest,
477        states: &[ClusterState],
478    ) -> Result<Arc<TextRasterResult>, TextRasterError> {
479        validate_request(request)?;
480        if self.fonts.is_empty() {
481            return Err(TextRasterError::NoFonts);
482        }
483        if !states.iter().all(ClusterState::is_valid) {
484            return Err(TextRasterError::InvalidRequest);
485        }
486        if states.iter().all(ClusterState::is_identity) {
487            let result = self.rasterize(request)?;
488            let clusters = self.layout(request)?.clusters.len();
489            return if states.len() == clusters {
490                Ok(result)
491            } else {
492                Err(TextRasterError::InvalidRequest)
493            };
494        }
495        if let Some(cached) = self.cache.get(request.content_version) {
496            return Ok(cached);
497        }
498        let mut tiles = std::mem::take(&mut self.tiles);
499        let result = self.rasterize_states(request, states, &mut tiles);
500        self.tiles = tiles;
501        let result = Arc::new(result?);
502        self.cache.insert(request.content_version, &result);
503        Ok(result)
504    }
505
506    #[allow(
507        clippy::cast_possible_truncation,
508        clippy::cast_possible_wrap,
509        clippy::cast_precision_loss,
510        clippy::cast_sign_loss,
511        clippy::too_many_lines
512    )]
513    fn rasterize_states(
514        &self,
515        request: &TextRasterRequest,
516        states: &[ClusterState],
517        cache: &mut TileCache,
518    ) -> Result<TextRasterResult, TextRasterError> {
519        let faces = Faces::new(&self.fonts, request.font_weight)?;
520        let layout = self.lay_out(&faces, request)?;
521        if states.len() != layout.clusters.len() {
522            return Err(TextRasterError::InvalidRequest);
523        }
524        let (box_width, box_height) = (layout.box_width, layout.box_height);
525        let ascent = layout.ascent;
526        let pivot_drop = request.font_size * 0.3;
527        let mut placed = vec![(Vec::<Placed>::new(), [0.0_f32; 6]); states.len()];
528        let mut drawings = HashMap::<(usize, u16), Drawing>::new();
529        let (mut ink_ascent, mut ink_descent) = (layout.ascent, layout.descent);
530        for (index, line) in layout.lines.iter().enumerate() {
531            let baseline = layout.line_top(index) + ascent;
532            // Tracking goes after each cluster except the line's last, in visual order.
533            let mut shifts = Vec::with_capacity(line.glyphs.len());
534            let mut shift = 0.0_f32;
535            let mut previous: Option<usize> = None;
536            for glyph in &line.glyphs {
537                if let Some(before) = previous.filter(|&before| before != glyph.cluster) {
538                    shift += states[before].tracking;
539                }
540                previous = Some(glyph.cluster);
541                shifts.push(shift);
542            }
543            let width = line.width + shift;
544            let offset = line_start(&layout, line.rtl, width, request);
545            // Pivot is the middle of the advance and of the em box.
546            let mut extents = HashMap::<usize, (f32, f32)>::new();
547            for (glyph, shift) in line.glyphs.iter().zip(&shifts) {
548                let left = glyph.x + shift + offset;
549                let extent = extents.entry(glyph.cluster).or_insert((left, left));
550                *extent = (extent.0.min(left), extent.1.max(left + glyph.advance));
551            }
552            for (glyph, shift) in line.glyphs.iter().zip(&shifts) {
553                let (left, right) = extents[&glyph.cluster];
554                let affine = cluster_affine(
555                    &states[glyph.cluster],
556                    [f32::midpoint(left, right), baseline - pivot_drop],
557                );
558                let drawing = drawings
559                    .entry((glyph.font, glyph.glyph_index))
560                    .or_insert_with(|| Drawing::of(&faces, glyph.font, glyph.glyph_index, request));
561                let Some(bounds) = drawing.bounds() else {
562                    continue;
563                };
564                let scale = request.font_size / faces.units_per_em(glyph.font);
565                ink_ascent = ink_ascent.max(bounds[3] * scale + glyph.y_offset);
566                ink_descent = ink_descent.max(-(bounds[1] * scale + glyph.y_offset));
567                let slot = &mut placed[glyph.cluster];
568                slot.1 = affine;
569                slot.0.push(Placed {
570                    key: (glyph.font, glyph.glyph_index),
571                    origin: [
572                        glyph.x + shift + glyph.x_offset + offset,
573                        baseline - glyph.y_offset,
574                    ],
575                    scale,
576                });
577            }
578        }
579        // Tiles depend only on the glyphs, the linear part of the map and the subpixel position,
580        // so they can be cached. Every tile is sized here, before any is drawn.
581        let look_key = look_key(request);
582        let mut planned = Vec::with_capacity(states.len());
583        for (glyphs, affine) in &placed {
584            let Some(first) = glyphs.first() else {
585                planned.push(None);
586                continue;
587            };
588            let [x, y] = apply(*affine, first.origin);
589            let whole = [x.floor(), y.floor()];
590            let local = [
591                affine[0],
592                affine[1],
593                affine[2],
594                affine[3],
595                affine[4] - whole[0],
596                affine[5] - whole[1],
597            ];
598            let (bounds, color) = cluster_box(&drawings, glyphs, local);
599            planned.push(Some(PlannedCluster {
600                key: cluster_key(look_key, glyphs, local),
601                whole: [whole[0] as i64, whole[1] as i64],
602                local,
603                bounds,
604                color,
605            }));
606        }
607        // Same symmetric margin as the static raster, with room for strokes.
608        let (outline, padding) = decoration_extents(request);
609        let (mut overflow_x, mut overflow_y) = (0_i64, 0_i64);
610        for bounds in planned
611            .iter()
612            .flatten()
613            .filter_map(|cluster| cluster.bounds.map(|bounds| bounds.moved(cluster.whole)))
614        {
615            overflow_x = overflow_x
616                .max(bounds.left.saturating_neg())
617                .max(bounds.right.saturating_sub(i64::from(box_width)));
618            overflow_y = overflow_y
619                .max(bounds.top.saturating_neg())
620                .max(bounds.bottom.saturating_sub(i64::from(box_height)));
621        }
622        let margin = |overflow: i64| -> Result<u32, TextRasterError> {
623            u32::try_from(overflow)
624                .map_err(|_| TextRasterError::TooLarge)?
625                .checked_add(outline)
626                .map(|margin| margin.max(outline.max(padding)))
627                .ok_or(TextRasterError::TooLarge)
628        };
629        let (margin_x, margin_y) = (margin(overflow_x)?, margin(overflow_y)?);
630        let width = margin_x
631            .checked_mul(2)
632            .and_then(|margins| box_width.checked_add(margins))
633            .ok_or(TextRasterError::TooLarge)?;
634        let height = margin_y
635            .checked_mul(2)
636            .and_then(|margins| box_height.checked_add(margins))
637            .ok_or(TextRasterError::TooLarge)?;
638        // Two owner planes of `u32`, and an owner plane per stroke band.
639        let colors = planned.iter().flatten().any(|cluster| cluster.color);
640        let owners = 8 + 4 * request.strokes.len() as u64;
641        let pixel_count = raster_pixels(
642            width,
643            height,
644            raster_bytes_per_pixel(request, colors) + owners,
645        )?;
646        if u64::from(width) * u64::from(height) > MAX_ANIMATED_PIXELS {
647            return Err(TextRasterError::TooLarge);
648        }
649        let reach = stroke_radius(&request.strokes).map_or(0, disc_extent);
650        let mut drawing = std::collections::HashSet::new();
651        let mut tile_bytes = 0_u64;
652        for cluster in planned.iter().flatten() {
653            if !cache.contains(cluster.key) && drawing.insert(cluster.key) {
654                tile_bytes =
655                    tile_bytes.saturating_add(cluster.drawing_bytes(request.strokes.len(), reach));
656            }
657        }
658        if tile_bytes > MAX_REQUEST_TILE_BYTES {
659            return Err(TextRasterError::TooLarge);
660        }
661        let mut tiles = Vec::with_capacity(states.len());
662        for cluster in &planned {
663            let Some(cluster) = cluster else {
664                tiles.push(None);
665                continue;
666            };
667            let drawn = if let Some(drawn) = cache.get(cluster.key) {
668                drawn
669            } else {
670                let glyphs = &placed[tiles.len()].0;
671                let drawn = Arc::new(draw_cluster(request, &drawings, glyphs, cluster.local));
672                debug_assert_eq!(
673                    drawn.tile.bounds().map(|bounds| [
674                        bounds.left,
675                        bounds.top,
676                        bounds.right,
677                        bounds.bottom
678                    ]),
679                    cluster.bounds.map(|bounds| [
680                        bounds.left,
681                        bounds.top,
682                        bounds.right,
683                        bounds.bottom
684                    ]),
685                );
686                cache.insert(cluster.key, &drawn);
687                drawn
688            };
689            tiles.push(Some((drawn, cluster.whole)));
690        }
691        let margins = [margin_x, margin_y];
692        let mut coverage = vec![0_u8; pixel_count];
693        let mut fill_owner = vec![u32::MAX; pixel_count];
694        let mut color_owner = vec![u32::MAX; pixel_count];
695        let mut colors: Option<Vec<u8>> = None;
696        let mut bands = vec![vec![0_u8; pixel_count]; request.strokes.len()];
697        let mut band_owner = vec![vec![u32::MAX; pixel_count]; request.strokes.len()];
698        for (cluster, (drawn, at)) in tiles
699            .iter()
700            .enumerate()
701            .filter_map(|(cluster, tile)| tile.as_ref().map(|tile| (cluster, tile)))
702        {
703            let cluster = u32::try_from(cluster).map_err(|_| TextRasterError::TooLarge)?;
704            let tile = drawn.tile.moved(*at);
705            place_max(
706                (&mut coverage, &mut fill_owner, width),
707                margins,
708                &tile,
709                &drawn.tile.coverage,
710                cluster,
711            );
712            if let Some(held) = &drawn.tile.colors {
713                let plane = colors.get_or_insert_with(|| vec![0; pixel_count * 4]);
714                for row in 0..tile.height {
715                    for column in 0..tile.width {
716                        let source = &held[(row * tile.width + column) * 4..][..4];
717                        if source[3] == 0 {
718                            continue;
719                        }
720                        let x = tile.left + column as i64 + i64::from(margin_x);
721                        let y = tile.top + row as i64 + i64::from(margin_y);
722                        if x < 0 || y < 0 || x >= i64::from(width) || y >= i64::from(height) {
723                            continue;
724                        }
725                        let pixel = y as usize * width as usize + x as usize;
726                        color_owner[pixel] = cluster;
727                        let at = pixel * 4;
728                        let slot = &mut plane[at..at + 4];
729                        let blended = over(
730                            std::array::from_fn(|channel| u32::from(source[channel])),
731                            std::array::from_fn(|channel| u32::from(slot[channel])),
732                        );
733                        for (byte, value) in slot.iter_mut().zip(blended) {
734                            *byte = u8::try_from(value.min(255)).unwrap_or(u8::MAX);
735                        }
736                    }
737                }
738            }
739            let padded = drawn.padded.moved(*at);
740            for ((band, owners), dilated) in bands
741                .iter_mut()
742                .zip(band_owner.iter_mut())
743                .zip(&drawn.bands)
744            {
745                place_max((band, owners, width), margins, &padded, dilated, cluster);
746            }
747        }
748        let mut line_boxes = Vec::with_capacity(layout.lines.len());
749        for (index, line) in layout.lines.iter().enumerate() {
750            if line.width > 0.0 {
751                line_boxes.push((
752                    layout.line_offset(line, request.align),
753                    line.width,
754                    layout.line_top(index),
755                ));
756            }
757        }
758        let base = RequestLook::of(request, [layout.width, layout.height]);
759        let solid = match &request.fill {
760            TextFill::Solid(color) => states
761                .iter()
762                .map(|state| state.fill.map(|mix| mixed(*color, &mix)))
763                .collect(),
764            TextFill::Gradient(_) => vec![None; states.len()],
765        };
766        let strokes = request
767            .strokes
768            .iter()
769            .map(|stroke| {
770                states
771                    .iter()
772                    .map(|state| {
773                        state
774                            .stroke
775                            .map_or(stroke.color, |mix| mixed(stroke.color, &mix))
776                    })
777                    .collect()
778            })
779            .collect();
780        let look = ClusterLook {
781            base,
782            states,
783            fill_owner,
784            band_owner,
785            color_owner,
786            solid,
787            strokes,
788        };
789        let (rgba8, background) = super::compose(
790            request,
791            &coverage,
792            colors.as_deref(),
793            width,
794            margins,
795            &line_boxes,
796            &bands,
797            &look,
798        );
799        let texture = HostTexture {
800            content_version: request.content_version,
801            width,
802            height,
803            premultiplication: Premultiplication::Premultiplied,
804            color_space: RasterColorSpace::Srgb,
805        };
806        Ok(TextRasterResult {
807            descriptor: TextTexture {
808                texture: texture.clone(),
809                layout_x: margin_x as f32,
810                layout_y: margin_y as f32,
811                layout_width: layout.width,
812                layout_height: layout.height,
813                first_baseline: layout.half_leading + layout.ascent,
814                ascent: ink_ascent,
815                descent: ink_descent,
816                line_count: layout.line_count,
817            },
818            pixels: HostTexturePixels { texture, rgba8 },
819            background,
820        })
821    }
822}
823
824/// Most pixels an animated raster may have. Its planes and the owner planes take 17 to 37 bytes
825/// per pixel, about twice a static raster.
826const MAX_ANIMATED_PIXELS: u64 = 1 << 25;
827
828/// Most bytes the tiles one request draws (those not cached) may take while drawn.
829const MAX_REQUEST_TILE_BYTES: u64 = 256 << 20;
830
831/// Most bytes the tile cache holds.
832const MAX_TILE_CACHE_BYTES: usize = 64 << 20;
833
834/// A cluster's tile key, placement and box, known before the tile is drawn.
835struct PlannedCluster {
836    key: u64,
837    whole: [i64; 2],
838    local: Affine,
839    /// The box [`draw_cluster`] gives the tile, in the frame offset by `whole`.
840    bounds: Option<PixelBox>,
841    /// Whether a glyph is a color glyph.
842    color: bool,
843}
844
845impl PlannedCluster {
846    /// Bytes drawing the tile takes: coverage and the outline accumulator (4 bytes) per pixel,
847    /// color glyphs and their resampled copy (8 more), and over the box padded by `reach` the
848    /// ink plane and one band per stroke.
849    fn drawing_bytes(&self, strokes: usize, reach: u32) -> u64 {
850        let Some(bounds) = self.bounds else {
851            return 0;
852        };
853        let side = |from: i64, to: i64| u64::try_from(to.saturating_sub(from)).unwrap_or(0);
854        let (width, height) = (
855            side(bounds.left, bounds.right),
856            side(bounds.top, bounds.bottom),
857        );
858        let pixels = width.saturating_mul(height);
859        let padded = width
860            .saturating_add(2 * u64::from(reach))
861            .saturating_mul(height.saturating_add(2 * u64::from(reach)));
862        let per_pixel = 5 + if self.color { 8 } else { 0 };
863        let planes = if strokes == 0 { 0 } else { strokes as u64 + 1 };
864        pixels
865            .saturating_mul(per_pixel)
866            .saturating_add(padded.saturating_mul(planes))
867    }
868}
869
870/// The tile box [`draw_cluster`] draws `glyphs` into through `affine`, and whether any has color.
871fn cluster_box(
872    drawings: &HashMap<(usize, u16), Drawing>,
873    glyphs: &[Placed],
874    affine: Affine,
875) -> (Option<PixelBox>, bool) {
876    let mut union: Option<PixelBox> = None;
877    let mut color = false;
878    for glyph in glyphs {
879        let drawing = &drawings[&glyph.key];
880        let Some(bounds) = drawing.bounds() else {
881            continue;
882        };
883        let target = mapped_box(bounds, glyph.origin, glyph.scale, affine);
884        if target.right <= target.left || target.bottom <= target.top {
885            continue;
886        }
887        color |= !matches!(drawing, Drawing::Outline(_));
888        union = Some(union.map_or(target, |held| PixelBox {
889            left: held.left.min(target.left),
890            top: held.top.min(target.top),
891            right: held.right.max(target.right),
892            bottom: held.bottom.max(target.bottom),
893        }));
894    }
895    (union, color)
896}
897
898/// A glyph with its origin before the cluster's map and its pixels per font unit.
899#[derive(Clone, Debug)]
900struct Placed {
901    key: (usize, u16),
902    origin: [f32; 2],
903    scale: f32,
904}
905
906/// A cluster's tile and stroke bands, in a frame offset by whole pixels when placed.
907struct DrawnCluster {
908    tile: Tile,
909    padded: Tile,
910    bands: Vec<Vec<u8>>,
911}
912
913impl Tile {
914    fn moved(&self, [x, y]: [i64; 2]) -> Self {
915        Self {
916            left: self.left + x,
917            top: self.top + y,
918            width: self.width,
919            height: self.height,
920            coverage: Vec::new(),
921            colors: None,
922        }
923    }
924}
925
926impl PixelBox {
927    fn moved(self, [x, y]: [i64; 2]) -> Self {
928        Self {
929            left: self.left.saturating_add(x),
930            top: self.top.saturating_add(y),
931            right: self.right.saturating_add(x),
932            bottom: self.bottom.saturating_add(y),
933        }
934    }
935}
936
937/// LRU cache of drawn clusters, so held or settled characters are drawn once. Bounded by
938/// [`MAX_TILE_CACHE_BYTES`] and [`MAX_CACHED_CLUSTERS`].
939#[derive(Debug, Default)]
940pub(crate) struct TileCache {
941    entries: HashMap<u64, (Arc<DrawnCluster>, u64)>,
942    bytes: usize,
943    next_use: u64,
944}
945
946impl std::fmt::Debug for DrawnCluster {
947    fn fmt(&self, formatter: &mut std::fmt::Formatter<'_>) -> std::fmt::Result {
948        formatter
949            .debug_struct("DrawnCluster")
950            .field("width", &self.tile.width)
951            .field("height", &self.tile.height)
952            .finish_non_exhaustive()
953    }
954}
955
956impl DrawnCluster {
957    fn bytes(&self) -> usize {
958        self.tile.coverage.len()
959            + self.tile.colors.as_ref().map_or(0, Vec::len)
960            + self.bands.iter().map(Vec::len).sum::<usize>()
961    }
962}
963
964const MAX_CACHED_CLUSTERS: usize = 4_096;
965
966impl TileCache {
967    fn contains(&self, key: u64) -> bool {
968        self.entries.contains_key(&key)
969    }
970
971    fn get(&mut self, key: u64) -> Option<Arc<DrawnCluster>> {
972        self.next_use += 1;
973        let use_now = self.next_use;
974        self.entries.get_mut(&key).map(|(drawn, used)| {
975            *used = use_now;
976            Arc::clone(drawn)
977        })
978    }
979
980    /// Keeps `drawn` unless it is larger than a quarter of the byte budget, evicting the least
981    /// recently used entries to make room.
982    fn insert(&mut self, key: u64, drawn: &Arc<DrawnCluster>) {
983        let bytes = drawn.bytes();
984        if bytes > MAX_TILE_CACHE_BYTES / 4 {
985            return;
986        }
987        if self.entries.len() >= MAX_CACHED_CLUSTERS {
988            // Drop the older half so eviction stays rare.
989            let mut uses = self
990                .entries
991                .values()
992                .map(|(_, used)| *used)
993                .collect::<Vec<_>>();
994            uses.sort_unstable();
995            let cut = uses[uses.len() / 2];
996            self.entries.retain(|_, (_, used)| *used > cut);
997            self.bytes = self.entries.values().map(|(drawn, _)| drawn.bytes()).sum();
998        }
999        if self.bytes + bytes > MAX_TILE_CACHE_BYTES {
1000            let mut by_use = self
1001                .entries
1002                .iter()
1003                .map(|(key, (drawn, used))| (*used, *key, drawn.bytes()))
1004                .collect::<Vec<_>>();
1005            by_use.sort_unstable();
1006            for (_, old, old_bytes) in by_use {
1007                if self.bytes + bytes <= MAX_TILE_CACHE_BYTES {
1008                    break;
1009                }
1010                self.entries.remove(&old);
1011                self.bytes -= old_bytes;
1012            }
1013        }
1014        if let Some((replaced, _)) = self.entries.insert(key, (Arc::clone(drawn), self.next_use)) {
1015            self.bytes -= replaced.bytes();
1016        }
1017        self.bytes += bytes;
1018    }
1019
1020    /// Bytes the cached tiles hold.
1021    #[cfg(test)]
1022    pub(crate) const fn bytes(&self) -> usize {
1023        self.bytes
1024    }
1025
1026    pub(crate) fn clear(&mut self) {
1027        self.entries.clear();
1028        self.bytes = 0;
1029    }
1030}
1031
1032/// FNV-1a over the request fields that affect cluster drawing besides glyphs and maps.
1033fn look_key(request: &TextRasterRequest) -> u64 {
1034    let mut hash = Fnv::default();
1035    hash.feed(&request.font_weight.to_le_bytes());
1036    hash.feed(&[request.emoji_policy as u8]);
1037    hash.feed(&request.fill.foreground());
1038    for stroke in &request.strokes {
1039        hash.feed(&stroke.width.to_bits().to_le_bytes());
1040    }
1041    hash.0
1042}
1043
1044fn cluster_key(look: u64, glyphs: &[Placed], affine: Affine) -> u64 {
1045    let mut hash = Fnv(look);
1046    let first = glyphs.first().map_or([0.0; 2], |glyph| glyph.origin);
1047    for glyph in glyphs {
1048        hash.feed(&glyph.key.0.to_le_bytes());
1049        hash.feed(&glyph.key.1.to_le_bytes());
1050        hash.feed(&glyph.scale.to_bits().to_le_bytes());
1051        for value in [glyph.origin[0] - first[0], glyph.origin[1] - first[1]] {
1052            hash.feed(&value.to_bits().to_le_bytes());
1053        }
1054    }
1055    // Key the map relative to the first glyph, so a moved cluster hits the cache.
1056    let [x, y] = apply(affine, first);
1057    for value in [affine[0], affine[1], affine[2], affine[3], x, y] {
1058        hash.feed(&value.to_bits().to_le_bytes());
1059    }
1060    hash.0
1061}
1062
1063struct Fnv(u64);
1064
1065impl Default for Fnv {
1066    fn default() -> Self {
1067        Self(0xcbf2_9ce4_8422_2325)
1068    }
1069}
1070
1071impl Fnv {
1072    fn feed(&mut self, bytes: &[u8]) {
1073        for byte in bytes {
1074            self.0 = (self.0 ^ u64::from(*byte)).wrapping_mul(0x0000_0100_0000_01b3);
1075        }
1076    }
1077}
1078
1079#[allow(
1080    clippy::cast_possible_truncation,
1081    clippy::cast_possible_wrap,
1082    clippy::cast_precision_loss,
1083    clippy::cast_sign_loss,
1084    clippy::too_many_lines
1085)]
1086fn draw_cluster(
1087    request: &TextRasterRequest,
1088    drawings: &HashMap<(usize, u16), Drawing>,
1089    glyphs: &[Placed],
1090    affine: Affine,
1091) -> DrawnCluster {
1092    let mut tile = Tile::empty();
1093    for glyph in glyphs {
1094        let drawing = &drawings[&glyph.key];
1095        let Some(bounds) = drawing.bounds() else {
1096            continue;
1097        };
1098        let (origin, scale) = (glyph.origin, glyph.scale);
1099        let target = mapped_box(bounds, origin, scale, affine);
1100        if target.right <= target.left || target.bottom <= target.top {
1101            continue;
1102        }
1103        tile.grow(target);
1104        let width = usize::try_from(target.right - target.left).unwrap_or(0);
1105        match drawing {
1106            Drawing::Outline(outline) => {
1107                let height = usize::try_from(target.bottom - target.top).unwrap_or(0);
1108                let (left, top) = (target.left as f32, target.top as f32);
1109                let raster = outline.raster(width, height, |[x, y]| {
1110                    let [x, y] = apply(affine, [origin[0] + x * scale, origin[1] - y * scale]);
1111                    point(x - left, y - top)
1112                });
1113                raster.for_each_pixel(|at, coverage| {
1114                    let value = (coverage.min(1.0) * 255.0).round() as u8;
1115                    let x = target.left + (at % width) as i64;
1116                    let y = target.top + (at / width) as i64;
1117                    if let Some(slot) = tile.index(x, y) {
1118                        tile.coverage[slot] = tile.coverage[slot].max(value);
1119                    }
1120                });
1121            }
1122            drawing => {
1123                let Some(inverse) = invert(affine) else {
1124                    continue;
1125                };
1126                let upright = PixelBox::of(bounds, origin, scale);
1127                let rgba8 = resample(
1128                    &drawing.draw_color(origin, scale, upright),
1129                    upright,
1130                    target,
1131                    inverse,
1132                );
1133                let size = tile.width * tile.height * 4;
1134                let slots = (0..rgba8.len() / 4)
1135                    .map(|at| {
1136                        tile.index(
1137                            target.left + (at % width) as i64,
1138                            target.top + (at / width) as i64,
1139                        )
1140                    })
1141                    .collect::<Vec<_>>();
1142                let colors = tile.colors.get_or_insert_with(|| vec![0; size]);
1143                for (source, slot) in rgba8.as_chunks::<4>().0.iter().zip(slots) {
1144                    let Some(slot) = slot.filter(|_| source[3] > 0) else {
1145                        continue;
1146                    };
1147                    let held = &mut colors[slot * 4..slot * 4 + 4];
1148                    let blended = over(
1149                        source.map(u32::from),
1150                        std::array::from_fn(|channel| u32::from(held[channel])),
1151                    );
1152                    for (byte, value) in held.iter_mut().zip(blended) {
1153                        *byte = u8::try_from(value.min(255)).unwrap_or(u8::MAX);
1154                    }
1155                }
1156            }
1157        }
1158    }
1159    // Dilate the ink, including color glyph alpha, band by band.
1160    let reach = stroke_radius(&request.strokes).map_or(0, disc_extent) as usize;
1161    let padded = Tile {
1162        left: tile.left - reach as i64,
1163        top: tile.top - reach as i64,
1164        width: tile.width + 2 * reach,
1165        height: tile.height + 2 * reach,
1166        coverage: Vec::new(),
1167        colors: None,
1168    };
1169    let mut bands = Vec::with_capacity(request.strokes.len());
1170    if !request.strokes.is_empty() && tile.width > 0 && tile.height > 0 {
1171        let mut ink = vec![0_u8; padded.width * padded.height];
1172        for row in 0..tile.height {
1173            for column in 0..tile.width {
1174                let at = row * tile.width + column;
1175                let alpha = tile.colors.as_ref().map_or(0, |held| held[at * 4 + 3]);
1176                ink[(row + reach) * padded.width + column + reach] = tile.coverage[at].max(alpha);
1177            }
1178        }
1179        let mut radius = 0.0;
1180        for stroke in &request.strokes {
1181            radius += stroke.width;
1182            bands.push(dilate(
1183                &ink,
1184                u32::try_from(padded.width).unwrap_or(u32::MAX),
1185                u32::try_from(padded.height).unwrap_or(u32::MAX),
1186                radius,
1187            ));
1188        }
1189    }
1190    DrawnCluster {
1191        tile,
1192        padded,
1193        bands,
1194    }
1195}
1196
1197/// Line start in the box, as [`Layout::line_offset`] computes it.
1198fn line_start(layout: &Layout, rtl: bool, width: f32, request: &TextRasterRequest) -> f32 {
1199    use alpha2_media::TextAlign;
1200    match (request.align, rtl) {
1201        (TextAlign::Center, _) => (layout.width - width) * 0.5,
1202        (TextAlign::Start, false) | (TextAlign::End, true) => 0.0,
1203        (TextAlign::End, false) | (TextAlign::Start, true) => layout.width - width,
1204    }
1205}
1206
1207fn text_layout(layout: &Layout, request: &TextRasterRequest) -> TextLayout {
1208    let mut map = Vec::new();
1209    normalize_mapped(&request.text, request.emoji_policy, Some(&mut map));
1210    let original = |at: usize| map.get(at).copied().unwrap_or(request.text.len());
1211    let words = request
1212        .text
1213        .split_word_bound_indices()
1214        .filter(|(_, word)| word.chars().any(char::is_alphanumeric))
1215        .map(|(start, word)| start..start + word.len())
1216        .collect::<Vec<_>>();
1217    let mut clusters = layout
1218        .clusters
1219        .iter()
1220        .map(|span| {
1221            let bytes = original(span.bytes.start)..original(span.bytes.end);
1222            let text = &request.text[bytes.clone()];
1223            let word = words
1224                .partition_point(|word| word.end <= bytes.start)
1225                .try_into()
1226                .ok()
1227                .filter(|&index: &u32| {
1228                    !span.ellipsis
1229                        && words
1230                            .get(index as usize)
1231                            .is_some_and(|word| word.contains(&bytes.start))
1232                });
1233            ClusterInfo {
1234                is_space: !text.is_empty() && text.chars().all(char::is_whitespace),
1235                bytes,
1236                line: u32::try_from(span.line).unwrap_or(u32::MAX),
1237                word,
1238                x: 0.0,
1239                advance: 0.0,
1240                baseline: 0.0,
1241                ellipsis: span.ellipsis,
1242            }
1243        })
1244        .collect::<Vec<_>>();
1245    let mut lines = Vec::with_capacity(layout.lines.len());
1246    let mut first_cluster = 0;
1247    for (index, line) in layout.lines.iter().enumerate() {
1248        let left = layout.line_offset(line, request.align);
1249        let baseline = layout.line_top(index) + layout.ascent;
1250        let line_number = u32::try_from(index).unwrap_or(u32::MAX);
1251        let last_cluster = clusters[first_cluster..]
1252            .iter()
1253            .position(|cluster| cluster.line != line_number)
1254            .map_or(clusters.len(), |count| first_cluster + count);
1255        let mut extents = HashMap::<usize, (f32, f32)>::new();
1256        for glyph in &line.glyphs {
1257            let start = glyph.x + left;
1258            let extent = extents.entry(glyph.cluster).or_insert((start, start));
1259            *extent = (extent.0.min(start), extent.1.max(start + glyph.advance));
1260        }
1261        for (cluster, info) in clusters[first_cluster..last_cluster].iter_mut().enumerate() {
1262            let (start, end) = extents
1263                .get(&(first_cluster + cluster))
1264                .copied()
1265                .unwrap_or((left + line.width, left + line.width));
1266            info.x = start;
1267            info.advance = end - start;
1268            info.baseline = baseline;
1269        }
1270        lines.push(LineInfo {
1271            clusters: first_cluster..last_cluster,
1272            left,
1273            width: line.width,
1274            baseline,
1275        });
1276        first_cluster = last_cluster;
1277    }
1278    TextLayout {
1279        clusters,
1280        lines,
1281        font_size: request.font_size,
1282    }
1283}
1284
1285#[cfg(test)]
1286mod tests {
1287    use super::*;
1288
1289    fn drawn(bytes: usize) -> Arc<DrawnCluster> {
1290        Arc::new(DrawnCluster {
1291            tile: Tile {
1292                left: 0,
1293                top: 0,
1294                width: bytes,
1295                height: 1,
1296                coverage: vec![0; bytes],
1297                colors: None,
1298            },
1299            padded: Tile::empty(),
1300            bands: Vec::new(),
1301        })
1302    }
1303
1304    #[test]
1305    fn the_tile_cache_evicts_the_least_recently_used_by_bytes() {
1306        let mut cache = TileCache::default();
1307        let tile = 10 << 20;
1308        for key in 0..6 {
1309            cache.insert(key, &drawn(tile));
1310        }
1311        assert_eq!(cache.bytes(), 6 * tile);
1312        assert!(cache.get(0).is_some());
1313        cache.insert(6, &drawn(tile));
1314        assert!(cache.bytes() <= MAX_TILE_CACHE_BYTES);
1315        assert!(cache.contains(0) && cache.contains(6) && !cache.contains(1));
1316        cache.insert(7, &drawn(MAX_TILE_CACHE_BYTES / 4 + 1));
1317        assert!(!cache.contains(7));
1318        cache.insert(6, &drawn(tile));
1319        assert!(cache.bytes() <= MAX_TILE_CACHE_BYTES);
1320        cache.clear();
1321        assert_eq!(cache.bytes(), 0);
1322    }
1323}