Skip to main content

alpha2_text/
lib.rs

1//! Text shaping and rasterization for alpha2 hosts.
2//!
3//! Produces the engine's [`TextTexture`] in pure Rust from caller-supplied fonts. Paragraphs are
4//! split by direction (UAX #9), script and font, shaped with rustybuzz, broken per UAX #14 and
5//! rasterized with `ab_glyph_rasterizer` (color glyphs in `color`). The same request and fonts
6//! give the same pixels natively and in wasm, so browser preview and native export match.
7
8use std::cell::OnceCell;
9use std::cmp::Ordering;
10use std::collections::{BTreeMap, BTreeSet, HashMap};
11use std::fmt;
12use std::ops::Range;
13use std::sync::Arc;
14
15use ab_glyph_rasterizer::{Point, Rasterizer, point};
16use alpha2_media::{
17    EmojiPolicy, HostTexture, HostTexturePixels, Premultiplication, RasterColorSpace, TextAlign,
18    TextTexture,
19};
20use rustybuzz::ttf_parser::{self, GlyphId, OutlineBuilder};
21use rustybuzz::{Direction, UnicodeBuffer};
22use unicode_bidi::ParagraphBidiInfo;
23use unicode_linebreak::BreakOpportunity;
24use unicode_script::{Script, UnicodeScript};
25use unicode_segmentation::UnicodeSegmentation;
26
27mod animated;
28mod color;
29mod font_check;
30mod gradient;
31mod unicode_tables;
32
33pub use animated::{ClusterInfo, ClusterState, ColorMix, LineInfo, MAX_CLUSTER_SCALE, TextLayout};
34pub use gradient::{TextGradient, TextGradientKind, TextGradientStop, TextSpread};
35
36const MAX_TEXT_BYTES: usize = 64 * 1024;
37const MAX_FONT_SIZE: f32 = 2_048.0;
38const MAX_LINE_HEIGHT: f32 = 10.0;
39/// Combined stroke width limit, in pixels.
40const MAX_STROKE_EXTENT: f32 = 64.0;
41const MAX_STROKES: usize = 4;
42const MAX_BACKGROUND_PADDING: f32 = 256.0;
43/// The widest wrapping width and the largest raster side in pixels.
44pub const MAX_TEXT_BOX: u32 = 16_384;
45#[allow(clippy::cast_precision_loss)]
46const MAX_TEXT_BOX_PIXELS: f32 = MAX_TEXT_BOX as f32;
47/// In font sizes.
48const LETTER_SPACING_RANGE: std::ops::RangeInclusive<f32> = -0.5..=1.0;
49/// Bytes the planes of one raster may take together.
50const MAX_RASTER_BYTES: u64 = 1 << 30;
51
52/// The pixel count of a `width` x `height` raster whose planes hold `bytes_per_pixel` bytes per
53/// pixel together, or [`TextRasterError::TooLarge`] past the largest frame
54/// ([`alpha2_media::MAX_FRAME_PIXELS`]) or [`MAX_RASTER_BYTES`]. Checked before any plane exists.
55fn raster_pixels(width: u32, height: u32, bytes_per_pixel: u64) -> Result<usize, TextRasterError> {
56    let pixels = u64::from(width) * u64::from(height);
57    if width > MAX_TEXT_BOX
58        || height > MAX_TEXT_BOX
59        || pixels > alpha2_media::MAX_FRAME_PIXELS
60        || pixels.saturating_mul(bytes_per_pixel) > MAX_RASTER_BYTES
61    {
62        return Err(TextRasterError::TooLarge);
63    }
64    usize::try_from(pixels).map_err(|_| TextRasterError::TooLarge)
65}
66
67/// Bytes per pixel of a raster's planes: coverage (1), RGBA8 result (4), split background (4),
68/// color glyph RGBA (4) with its stroke ink plane (1), and one band per stroke (1 each).
69fn raster_bytes_per_pixel(request: &TextRasterRequest, colors: bool) -> u64 {
70    let split = request.split_background && request.background.is_some();
71    let strokes = request.strokes.len() as u64;
72    1 + 4
73        + if split { 4 } else { 0 }
74        + if colors {
75            4 + u64::from(strokes > 0)
76        } else {
77            0
78        }
79        + strokes
80}
81
82/// One caller-owned font registered in fallback order.
83#[derive(Clone, Debug)]
84pub struct TextFont {
85    /// Stable family name used in cache keys and diagnostics.
86    pub family: String,
87    /// OpenType font bytes.
88    pub bytes: Arc<[u8]>,
89    /// Face index for font collections.
90    pub face_index: u32,
91}
92
93/// One text layout request.
94#[derive(Clone, Debug, PartialEq)]
95pub struct TextRasterRequest {
96    /// UTF-8 text shaped by the selected font fallback stack.
97    pub text: String,
98    /// Logical font size in pixels.
99    pub font_size: f32,
100    /// Maximum layout width. Non-positive values disable wrapping.
101    pub max_width: f32,
102    /// Baseline-to-baseline distance in font sizes. The em box (0.8 above the baseline, 0.2
103    /// below) is centered in lines taller than an em.
104    pub line_height: f32,
105    /// Per-line horizontal alignment.
106    pub align: TextAlign,
107    /// Glyph paint. Color glyphs keep their own colors except for text-color parts, which use
108    /// [`TextFill::foreground`], whose alpha is also their opacity.
109    pub fill: TextFill,
110    /// Whether color glyphs are drawn in color, and which fonts emoji take.
111    pub emoji_policy: EmojiPolicy,
112    /// Caller-managed version. Change it whenever content/style/font inputs change.
113    pub content_version: u64,
114    /// Outlines, innermost first, each drawn behind the previous. At most 4, reaching at most 64
115    /// pixels together.
116    pub strokes: Vec<TextStroke>,
117    /// A box behind each line, drawn behind the strokes.
118    pub background: Option<TextBackground>,
119    /// Draws the background into [`TextRasterResult::background`] instead of under the glyphs,
120    /// so a caller can draw something (a shadow) between them.
121    pub split_background: bool,
122    /// Preferred family, matched against any [`font_family_names`] entry after NFC and
123    /// lowercasing; the fallback stack fills missing glyphs. An unknown family keeps the fallback
124    /// order and is listed by [`TextRasterizer::unmatched_families`].
125    pub font_family: Option<String>,
126    /// Space after each grapheme cluster, like CSS `letter-spacing`, in `[-0.5, 1]` font sizes.
127    /// Not applied after a line's last cluster or within cursive scripts. Non-zero values disable
128    /// optional ligatures.
129    pub letter_spacing: f32,
130    /// Weight in `[1, 1000]`, matched per CSS Fonts 4 and applied to a variable face's `wght`
131    /// axis. Faces are never synthetically emboldened.
132    pub font_weight: u16,
133    /// Where lines are cut, as CSS `line-clamp` cuts them; `None` keeps every line.
134    pub clamp: Option<TextClamp>,
135}
136
137/// Most bytes in a [`TextClamp::ellipsis`].
138pub const MAX_ELLIPSIS_BYTES: usize = 256;
139
140/// Lines past the clamp point ([`line_limit`]) are discarded, as CSS `line-clamp` discards them.
141/// A cut text's last line ends with the ellipsis, one more cluster ([`ClusterInfo::ellipsis`]).
142#[derive(Clone, Debug, PartialEq)]
143pub struct TextClamp {
144    /// Most lines, at least 1, as CSS `max-lines`; `None` sets no count.
145    pub max_lines: Option<u32>,
146    /// Height in pixels the kept lines' box fits in, as the automatic clamp point of CSS
147    /// `max-lines: auto`; non-positive sets no height.
148    pub max_height: f32,
149    /// What ends a cut line, as CSS `block-ellipsis`, at most [`MAX_ELLIPSIS_BYTES`] bytes with
150    /// no `\n`; `None` cuts without a mark.
151    pub ellipsis: Option<String>,
152}
153
154/// The most lines a clamp keeps of text `font_size` pixels tall with lines `line_height` font
155/// sizes apart: at most `max_lines`, and as many as fit in `max_height` pixels (non-positive
156/// for no height), but at least one. `None` when neither limits.
157#[must_use]
158#[allow(
159    clippy::cast_possible_truncation,
160    clippy::cast_precision_loss,
161    clippy::cast_sign_loss
162)]
163pub fn line_limit(
164    font_size: f32,
165    line_height: f32,
166    max_lines: Option<u32>,
167    max_height: f32,
168) -> Option<u32> {
169    let advance = font_size * line_height;
170    let by_height = (max_height > 0.0).then(|| {
171        // An estimate, then the exact comparison the box height makes.
172        let first = advance.max(font_size);
173        let estimate = ((max_height - first) / advance).floor() + 1.0;
174        let mut lines = if estimate.is_finite() {
175            estimate.clamp(1.0, 1.0e9) as u32
176        } else {
177            1
178        };
179        while lines > 1 && box_height(lines, advance, font_size) > max_height {
180            lines -= 1;
181        }
182        while lines < 1_000_000_000 && box_height(lines + 1, advance, font_size) <= max_height {
183            lines += 1;
184        }
185        lines
186    });
187    match (max_lines.map(|lines| lines.max(1)), by_height) {
188        (Some(count), Some(height)) => Some(count.min(height)),
189        (count, height) => count.or(height),
190    }
191}
192
193/// What paints a text's glyphs.
194#[derive(Clone, Debug, PartialEq)]
195pub enum TextFill {
196    /// Straight (not premultiplied) sRGB RGBA.
197    Solid([u8; 4]),
198    /// A gradient over the layout box.
199    Gradient(TextGradient),
200}
201
202impl TextFill {
203    /// Color used for a color glyph's text-color parts: the solid color or the first stop.
204    #[must_use]
205    #[allow(clippy::cast_possible_truncation, clippy::cast_sign_loss)]
206    pub fn foreground(&self) -> [u8; 4] {
207        match self {
208            Self::Solid(color) => *color,
209            Self::Gradient(gradient) => gradient.stops.first().map_or([0; 4], |stop| {
210                stop.color
211                    .map(|value| (value.clamp(0.0, 1.0) * 255.0).round() as u8)
212            }),
213        }
214    }
215
216    fn is_valid(&self) -> bool {
217        match self {
218            Self::Solid(_) => true,
219            Self::Gradient(gradient) => gradient.is_valid(),
220        }
221    }
222}
223
224/// An outline band drawn behind the glyphs and earlier strokes.
225///
226/// Stroke `k` dilates glyph coverage by a disc whose radius is the sum of widths up to `k`, with
227/// the disc's last pixel weighted down for antialiasing.
228#[derive(Copy, Clone, Debug, PartialEq)]
229pub struct TextStroke {
230    /// Straight sRGB RGBA.
231    pub color: [u8; 4],
232    /// Positive width in pixels.
233    pub width: f32,
234}
235
236/// A box behind each non-empty line (advance by one em, grown by `padding`). Touching boxes
237/// merge.
238#[derive(Copy, Clone, Debug, PartialEq)]
239pub struct TextBackground {
240    /// Straight sRGB RGBA.
241    pub color: [u8; 4],
242    /// Space between the text and the box edge, in `[0, 256]` pixels.
243    pub padding: f32,
244}
245
246/// Rasterized pixels and their text-specific layout descriptor.
247#[derive(Clone, Debug, PartialEq)]
248pub struct TextRasterResult {
249    /// Layout facts sharing the generic compositor texture contract.
250    pub descriptor: TextTexture,
251    /// Tightly packed premultiplied RGBA8 pixels.
252    pub pixels: HostTexturePixels,
253    /// Background alone, same size as `pixels`, when
254    /// [`TextRasterRequest::split_background`] is set.
255    pub background: Option<Vec<u8>>,
256}
257
258/// Text geometry from [`TextRasterizer::measure`]. Rectangles are `[left, top, right, bottom]`
259/// in pixels from the layout box's top-left, which sits at ([`TextTexture::layout_x`],
260/// [`TextTexture::layout_y`]) in the rasterized texture.
261#[derive(Clone, Debug, PartialEq)]
262pub struct TextMeasure {
263    /// The wrap width, else the widest line, rounded up.
264    pub box_width: u32,
265    /// All lines' em boxes, rounded up.
266    pub box_height: u32,
267    /// [`TextRasterRequest::decoration_margin`].
268    pub decoration_margin: u32,
269    /// Horizontal extent of the line advances by the box height, grown by the decoration
270    /// margin. Unlike `ink`, it does not depend on glyph shapes.
271    pub content: [f32; 4],
272    /// Bounds of everything drawn (glyphs, strokes, background), at most a pixel loose (more for
273    /// COLR clip boxes). `None` when nothing is drawn.
274    pub ink: Option<[f32; 4]>,
275    /// Number of laid-out lines.
276    pub line_count: u32,
277    /// First alphabetic baseline, in pixels from the layout box's top.
278    pub first_baseline: f32,
279    /// Last alphabetic baseline, in pixels from the layout box's top.
280    pub last_baseline: f32,
281    /// Whether [`TextRasterRequest::clamp`] discarded text.
282    pub truncated: bool,
283}
284
285/// Text shaped once ([`TextRasterizer::shape`]) so lines can be broken at any width without
286/// reshaping.
287#[derive(Clone, Debug)]
288pub struct ShapedText {
289    paragraphs: Vec<Vec<Cluster>>,
290    font_size: f32,
291    line_height: f32,
292    line_advance: f32,
293}
294
295/// Lines of a shaped text at one wrapping width ([`ShapedText::lines_at`]).
296#[derive(Copy, Clone, Debug, PartialEq)]
297pub struct LineMetrics {
298    /// Number of lines.
299    pub line_count: u32,
300    /// Widest line advance, excluding trailing spaces.
301    pub widest: f32,
302    /// Unrounded box height.
303    pub height: f32,
304    /// First alphabetic baseline, in pixels from the box's top.
305    pub first_baseline: f32,
306    /// Last alphabetic baseline, in pixels from the box's top.
307    pub last_baseline: f32,
308}
309
310impl ShapedText {
311    /// CSS min-content width: the widest unbreakable run.
312    #[must_use]
313    pub fn min_content_width(&self) -> f32 {
314        let mut widest = 0.0_f32;
315        for clusters in &self.paragraphs {
316            let mut start = 0;
317            for index in 1..=clusters.len() {
318                if index == clusters.len() || clusters[index].break_before {
319                    widest = widest.max(advance(&clusters[start..index]));
320                    start = index;
321                }
322            }
323        }
324        widest
325    }
326
327    /// CSS max-content width: the widest unwrapped paragraph.
328    #[must_use]
329    pub fn max_content_width(&self) -> f32 {
330        self.paragraphs
331            .iter()
332            .map(|clusters| advance(clusters))
333            .fold(0.0, f32::max)
334    }
335
336    /// Lines at `max_width`; a non-positive width does not wrap.
337    #[must_use]
338    pub fn lines_at(&self, max_width: f32) -> LineMetrics {
339        self.lines_within(max_width, None).lines
340    }
341
342    /// [`line_limit`] for this text's font size and line height.
343    #[must_use]
344    pub fn line_limit(&self, max_lines: Option<u32>, max_height: f32) -> Option<u32> {
345        line_limit(self.font_size, self.line_height, max_lines, max_height)
346    }
347
348    /// Lines at `max_width` (non-positive does not wrap), cut after `limit` lines as a
349    /// [`TextClamp`] cuts them. The ellipsis takes no part in the widths.
350    #[must_use]
351    pub fn lines_within(&self, max_width: f32, limit: Option<u32>) -> ClampedLines {
352        let limit = limit.map_or(u32::MAX, |limit| limit.max(1));
353        let (mut count, mut kept, mut widest) = (0_u32, 1_u32, 0.0_f32);
354        let (mut truncated, mut emergency) = (false, false);
355        'paragraphs: for (index, clusters) in self.paragraphs.iter().enumerate() {
356            let ranges = break_lines(clusters, max_width);
357            for (at, range) in ranges.iter().enumerate() {
358                count = count.saturating_add(1);
359                if !range.is_empty() {
360                    kept = count;
361                }
362                widest = widest.max(advance(&clusters[range.clone()]));
363                emergency |= !range.is_empty()
364                    && range.end < clusters.len()
365                    && !clusters[range.end].break_before;
366                if count == limit {
367                    truncated = ranges[at + 1..].iter().any(|range| !range.is_empty())
368                        || self.paragraphs[index + 1..]
369                            .iter()
370                            .any(|clusters| !clusters.is_empty());
371                    break 'paragraphs;
372                }
373            }
374        }
375        let [first_baseline, last_baseline] =
376            baselines(kept, self.font_size, self.line_height, self.line_advance);
377        ClampedLines {
378            lines: LineMetrics {
379                line_count: kept,
380                widest,
381                height: box_height(kept, self.line_advance, self.font_size),
382                first_baseline,
383                last_baseline,
384            },
385            truncated,
386            splits_word: if truncated {
387                emergency
388            } else {
389                max_width > 0.0 && self.min_content_width() > max_width
390            },
391        }
392    }
393}
394
395/// The lines a clamp keeps ([`ShapedText::lines_within`]).
396#[derive(Copy, Clone, Debug, PartialEq)]
397pub struct ClampedLines {
398    /// The kept lines.
399    pub lines: LineMetrics,
400    /// Whether lines with content were cut off.
401    pub truncated: bool,
402    /// Whether a kept line breaks inside a word. Uncut text breaks one when its min-content
403    /// width exceeds the wrapping width.
404    pub splits_word: bool,
405}
406
407/// Line advance as [`break_lines`] sums it, excluding hanging clusters and the last cluster's
408/// letter spacing.
409fn advance(clusters: &[Cluster]) -> f32 {
410    let Some(last) = clusters.iter().rposition(|cluster| !cluster.hangs) else {
411        return 0.0;
412    };
413    clusters[..=last]
414        .iter()
415        .fold(0.0, |width, cluster| width + cluster.width)
416        - clusters[last].spacing
417}
418
419/// CSS half-leading above the em box, or zero when lines are closer than an em.
420#[must_use]
421pub fn half_leading(font_size: f32, line_height: f32) -> f32 {
422    (font_size * line_height - font_size).max(0.0) * 0.5
423}
424
425/// First and last baselines from the box's top, using a nominal ascent of 0.8 font sizes.
426#[allow(clippy::cast_precision_loss)]
427fn baselines(line_count: u32, font_size: f32, line_height: f32, line_advance: f32) -> [f32; 2] {
428    let (leading, ascent) = (half_leading(font_size, line_height), font_size * 0.8);
429    let last = line_count.saturating_sub(1) as f32;
430    [leading + ascent, last * line_advance + leading + ascent]
431}
432
433/// Box height covering every line's em box, including the last when lines overlap.
434#[allow(clippy::cast_precision_loss)]
435fn box_height(line_count: u32, line_advance: f32, font_size: f32) -> f32 {
436    line_count.saturating_sub(1) as f32 * line_advance + line_advance.max(font_size)
437}
438
439/// Typed text-host failure.
440#[derive(Clone, Debug, Eq, PartialEq)]
441#[non_exhaustive]
442pub enum TextRasterError {
443    /// No usable fonts were registered.
444    NoFonts,
445    /// OpenType parsing failed.
446    InvalidFont(String),
447    /// Request values are non-finite or outside the supported range.
448    InvalidRequest,
449    /// Computed dimensions cannot be represented safely.
450    TooLarge,
451}
452
453impl fmt::Display for TextRasterError {
454    fn fmt(&self, formatter: &mut fmt::Formatter<'_>) -> fmt::Result {
455        match self {
456            Self::NoFonts => formatter.write_str("text rasterizer requires at least one font"),
457            Self::InvalidFont(error) => write!(formatter, "invalid text font: {error}"),
458            Self::InvalidRequest => formatter.write_str("invalid text raster request"),
459            Self::TooLarge => formatter.write_str("text raster result is too large"),
460        }
461    }
462}
463
464impl std::error::Error for TextRasterError {}
465
466#[derive(Clone, Debug)]
467struct LoadedFont {
468    source: TextFont,
469    /// Folded [`font_family`], used to group faces.
470    family: Option<String>,
471    /// Folded names in every language, matched against requested families.
472    aliases: Vec<String>,
473    /// OS/2 usWeightClass in [1, 1000]; 400 without the table.
474    weight: u16,
475    /// The fvar `wght` axis (min, default, max), for a variable face.
476    wght: Option<(f32, f32, f32)>,
477}
478
479const WGHT: ttf_parser::Tag = ttf_parser::Tag::from_bytes(b"wght");
480
481impl LoadedFont {
482    /// Validates the face and reads its family and weight; outlines are read lazily.
483    fn parse(source: TextFont) -> Result<Self, TextRasterError> {
484        let face = parse_checked(&source.bytes, source.face_index)?;
485        let weight = face.weight().to_number().clamp(1, 1000);
486        let wght = face
487            .variation_axes()
488            .into_iter()
489            .find(|axis| axis.tag == WGHT)
490            .map(|axis| (axis.min_value, axis.def_value, axis.max_value));
491        let family = font_family(&source.bytes, source.face_index).map(|name| fold_family(&name));
492        let mut aliases = font_family_names(&source.bytes, source.face_index)
493            .iter()
494            .map(|name| fold_family(name))
495            .collect::<Vec<_>>();
496        aliases.extend(family.clone());
497        aliases.sort();
498        aliases.dedup();
499        Ok(Self {
500            source,
501            family,
502            aliases,
503            weight,
504            wght,
505        })
506    }
507
508    /// Weight range: the `wght` axis rounded inward, or the static weight twice.
509    #[allow(clippy::cast_possible_truncation, clippy::cast_sign_loss)]
510    fn weights(&self) -> (u16, u16) {
511        self.wght
512            .map_or((self.weight, self.weight), |(min, _, max)| {
513                let whole = |value: f32| value.clamp(1.0, 1000.0) as u16;
514                (whole(min.ceil()), whole(max.floor()).max(whole(min.ceil())))
515            })
516    }
517}
518
519/// Face indices in CSS Fonts 4 (section 5.2) weight matching order for `desired`, ties in input
520/// order. A range containing `desired` matches exactly; otherwise its nearest end counts.
521fn weight_order(weights: &[(u16, u16)], desired: u16) -> Vec<usize> {
522    let key = |&(min, max): &(u16, u16)| -> (u8, u16) {
523        if (min..=max).contains(&desired) {
524            return (0, 0);
525        }
526        let weight = if desired < min { min } else { max };
527        let (above, distance) = (weight > desired, weight.abs_diff(desired));
528        if (400..=500).contains(&desired) {
529            match (above, weight <= 500) {
530                (true, true) => (1, distance),
531                (false, _) => (2, distance),
532                (true, false) => (3, distance),
533            }
534        } else if (desired < 400) != above {
535            (1, distance)
536        } else {
537            (2, distance)
538        }
539    };
540    let mut order = (0..weights.len()).collect::<Vec<_>>();
541    order.sort_by_key(|&index| key(&weights[index]));
542    order
543}
544
545/// Checks that `bytes` hold an OpenType face at `face_index`, as [`TextRasterizer::add_font`]
546/// would, so a host can reject a file at import.
547///
548/// Fonts are untrusted input: a collection may hold 256 faces, a glyph may expand to 1,024
549/// simple glyphs through its components, and a color glyph's painting may visit 16,384 paints.
550///
551/// # Errors
552/// Returns [`TextRasterError::InvalidFont`] with the parser's or the budget's reason.
553pub fn check_font(bytes: &[u8], face_index: u32) -> Result<(), TextRasterError> {
554    parse_checked(bytes, face_index).map(drop)
555}
556
557fn parse_checked(bytes: &[u8], face_index: u32) -> Result<ttf_parser::Face<'_>, TextRasterError> {
558    if ttf_parser::fonts_in_collection(bytes)
559        .is_some_and(|faces| faces > font_check::MAX_COLLECTION_FACES)
560    {
561        return Err(TextRasterError::InvalidFont(format!(
562            "the font collection holds more than {} faces",
563            font_check::MAX_COLLECTION_FACES
564        )));
565    }
566    let face = ttf_parser::Face::parse(bytes, face_index)
567        .map_err(|error| TextRasterError::InvalidFont(error.to_string()))?;
568    font_check::check_face(&face).map_err(TextRasterError::InvalidFont)?;
569    Ok(face)
570}
571
572/// Number of faces in a font collection (`.ttc`, `.otc`), else 1.
573#[must_use]
574pub fn face_count(bytes: &[u8]) -> u32 {
575    ttf_parser::fonts_in_collection(bytes).unwrap_or(1)
576}
577
578/// The face's typographic family (name ID 16), else family (name ID 1), preferring US English.
579/// `None` for unparsable bytes or no family name.
580#[must_use]
581pub fn font_family(bytes: &[u8], face_index: u32) -> Option<String> {
582    use rustybuzz::ttf_parser::{Language, name_id};
583    let face = rustybuzz::ttf_parser::Face::parse(bytes, face_index).ok()?;
584    let names = face.names();
585    [name_id::TYPOGRAPHIC_FAMILY, name_id::FAMILY]
586        .into_iter()
587        .find_map(|id| {
588            let decoded = || {
589                names
590                    .into_iter()
591                    .filter(move |name| name.name_id == id)
592                    .filter_map(|name| {
593                        let text = name.to_string()?;
594                        (!text.trim().is_empty()).then_some((name.language(), text))
595                    })
596            };
597            decoded()
598                .find(|(language, _)| *language == Language::English_UnitedStates)
599                .or_else(|| decoded().next())
600                .map(|(_, text)| text)
601        })
602}
603
604/// Every distinct name ID 16 and 1 family name in every language, in table order. A project may
605/// name a family by any of them. Empty for unparsable bytes.
606#[must_use]
607pub fn font_family_names(bytes: &[u8], face_index: u32) -> Vec<String> {
608    use rustybuzz::ttf_parser::name_id;
609    let Ok(face) = rustybuzz::ttf_parser::Face::parse(bytes, face_index) else {
610        return Vec::new();
611    };
612    let mut names = Vec::new();
613    for name in face.names() {
614        if name.name_id != name_id::TYPOGRAPHIC_FAMILY && name.name_id != name_id::FAMILY {
615            continue;
616        }
617        if let Some(text) = name.to_string().map(|text| text.trim().to_owned())
618            && !text.is_empty()
619            && !names.contains(&text)
620        {
621            names.push(text);
622        }
623    }
624    names
625}
626
627/// Normalizes a family name for comparison: NFC, then Unicode lowercase.
628#[must_use]
629pub fn fold_family(name: &str) -> String {
630    use unicode_normalization::UnicodeNormalization;
631    name.trim().nfc().collect::<String>().to_lowercase()
632}
633
634/// Default result cache budget in bytes: a few full-frame 4K titles.
635pub const DEFAULT_TEXT_CACHE_BYTES: usize = 64 << 20;
636
637/// Per-entry cost so that empty results still bound the entry count.
638const CACHE_ENTRY_OVERHEAD: usize = 256;
639
640/// Deterministic text host with version-key result caching.
641///
642/// Results are LRU-cached by content version within a byte budget
643/// ([`DEFAULT_TEXT_CACHE_BYTES`] by default) and shared as the same [`Arc`].
644#[derive(Debug)]
645pub struct TextRasterizer {
646    fonts: Vec<LoadedFont>,
647    cache: ResultCache,
648    tiles: animated::TileCache,
649    unmatched: std::sync::Mutex<BTreeSet<String>>,
650}
651
652#[derive(Debug)]
653struct ResultCache {
654    entries: HashMap<u64, CacheEntry>,
655    /// Content versions by last use, oldest first.
656    by_use: BTreeMap<u64, u64>,
657    next_use: u64,
658    bytes: usize,
659    budget: usize,
660}
661
662#[derive(Debug)]
663struct CacheEntry {
664    result: Arc<TextRasterResult>,
665    last_use: u64,
666    bytes: usize,
667}
668
669impl ResultCache {
670    fn new(budget: usize) -> Self {
671        Self {
672            entries: HashMap::new(),
673            by_use: BTreeMap::new(),
674            next_use: 0,
675            bytes: 0,
676            budget,
677        }
678    }
679
680    fn get(&mut self, version: u64) -> Option<Arc<TextRasterResult>> {
681        let entry = self.entries.get_mut(&version)?;
682        self.by_use.remove(&entry.last_use);
683        entry.last_use = self.next_use;
684        self.by_use.insert(self.next_use, version);
685        self.next_use += 1;
686        Some(Arc::clone(&entry.result))
687    }
688
689    fn insert(&mut self, version: u64, result: &Arc<TextRasterResult>) {
690        self.remove(version);
691        let bytes = result
692            .pixels
693            .rgba8
694            .len()
695            .saturating_add(CACHE_ENTRY_OVERHEAD);
696        if bytes > self.budget {
697            return;
698        }
699        self.bytes += bytes;
700        self.entries.insert(
701            version,
702            CacheEntry {
703                result: Arc::clone(result),
704                last_use: self.next_use,
705                bytes,
706            },
707        );
708        self.by_use.insert(self.next_use, version);
709        self.next_use += 1;
710        self.evict();
711    }
712
713    fn remove(&mut self, version: u64) {
714        if let Some(entry) = self.entries.remove(&version) {
715            self.by_use.remove(&entry.last_use);
716            self.bytes -= entry.bytes;
717        }
718    }
719
720    fn clear(&mut self) {
721        self.entries.clear();
722        self.by_use.clear();
723        self.bytes = 0;
724    }
725
726    fn set_budget(&mut self, budget: usize) {
727        self.budget = budget;
728        self.evict();
729    }
730
731    fn evict(&mut self) {
732        while self.bytes > self.budget {
733            let Some((_, version)) = self.by_use.pop_first() else {
734                break;
735            };
736            if let Some(entry) = self.entries.remove(&version) {
737                self.bytes -= entry.bytes;
738            }
739        }
740    }
741}
742
743impl TextRasterizer {
744    /// A rasterizer with no fonts yet; add them with [`Self::add_font`].
745    #[must_use]
746    pub fn empty() -> Self {
747        Self {
748            fonts: Vec::new(),
749            cache: ResultCache::new(DEFAULT_TEXT_CACHE_BYTES),
750            tiles: animated::TileCache::default(),
751            unmatched: std::sync::Mutex::default(),
752        }
753    }
754
755    /// Takes a fallback-ordered OpenType stack.
756    ///
757    /// # Errors
758    /// Returns [`TextRasterError::NoFonts`] or the first malformed font.
759    pub fn new(fonts: Vec<TextFont>) -> Result<Self, TextRasterError> {
760        if fonts.is_empty() {
761            return Err(TextRasterError::NoFonts);
762        }
763        let loaded = fonts
764            .into_iter()
765            .map(LoadedFont::parse)
766            .collect::<Result<Vec<_>, _>>()?;
767        Ok(Self {
768            fonts: loaded,
769            cache: ResultCache::new(DEFAULT_TEXT_CACHE_BYTES),
770            tiles: animated::TileCache::default(),
771            unmatched: std::sync::Mutex::default(),
772        })
773    }
774
775    /// Appends a font to the end of the fallback stack.
776    ///
777    /// Clears the result cache.
778    ///
779    /// # Errors
780    /// Returns [`TextRasterError::InvalidFont`] for malformed font bytes.
781    pub fn add_font(&mut self, source: TextFont) -> Result<(), TextRasterError> {
782        self.fonts.push(LoadedFont::parse(source)?);
783        self.cache.clear();
784        self.tiles.clear();
785        Ok(())
786    }
787
788    /// Number of fonts in the fallback stack.
789    #[must_use]
790    pub fn font_count(&self) -> usize {
791        self.fonts.len()
792    }
793
794    /// Requested families no registered font had, sorted, as spelled. Adding fonts later does not
795    /// clear the list.
796    #[must_use]
797    pub fn unmatched_families(&self) -> Vec<String> {
798        self.unmatched
799            .lock()
800            .unwrap_or_else(std::sync::PoisonError::into_inner)
801            .iter()
802            .cloned()
803            .collect()
804    }
805
806    /// Shapes, lays out and rasterizes one request, or returns the cached result for its version.
807    ///
808    /// # Errors
809    /// Returns a typed validation, font, or size error.
810    pub fn rasterize(
811        &mut self,
812        request: &TextRasterRequest,
813    ) -> Result<Arc<TextRasterResult>, TextRasterError> {
814        validate_request(request)?;
815        if self.fonts.is_empty() {
816            return Err(TextRasterError::NoFonts);
817        }
818        if let Some(cached) = self.cache.get(request.content_version) {
819            return Ok(cached);
820        }
821        let result = Arc::new(self.rasterize_uncached(request)?);
822        self.cache.insert(request.content_version, &result);
823        Ok(result)
824    }
825
826    /// Drops a single host version after content or font invalidation.
827    pub fn invalidate(&mut self, content_version: u64) {
828        self.cache.remove(content_version);
829    }
830
831    /// Sets the result cache budget in bytes, evicting down to it. Results larger than the
832    /// budget are returned but not kept.
833    pub fn set_cache_budget(&mut self, bytes: usize) {
834        self.cache.set_budget(bytes);
835    }
836
837    /// Bytes the cached results count against the budget.
838    #[must_use]
839    pub fn cache_bytes(&self) -> usize {
840        self.cache.bytes
841    }
842
843    /// Drops every rasterized result while retaining parsed fonts.
844    pub fn clear(&mut self) {
845        self.cache.clear();
846        self.tiles.clear();
847    }
848
849    /// Number of versioned raster results currently retained.
850    #[must_use]
851    pub fn cache_len(&self) -> usize {
852        self.cache.entries.len()
853    }
854
855    /// Measures `request` as [`Self::rasterize`] would lay it out, without drawing or caching.
856    ///
857    /// # Errors
858    /// Returns the same errors as [`Self::rasterize`].
859    #[allow(clippy::cast_precision_loss)]
860    pub fn measure(&self, request: &TextRasterRequest) -> Result<TextMeasure, TextRasterError> {
861        validate_request(request)?;
862        if self.fonts.is_empty() {
863            return Err(TextRasterError::NoFonts);
864        }
865        let faces = Faces::new(&self.fonts, request.font_weight)?;
866        let layout = self.lay_out(&faces, request)?;
867        let mut ink = None;
868        layout.each_glyph(
869            &faces,
870            request,
871            &mut HashMap::new(),
872            |drawing, origin, scale, _| {
873                if let Some([x_min, y_min, x_max, y_max]) = drawing.ink_bounds() {
874                    include(
875                        &mut ink,
876                        [
877                            origin[0] + x_min * scale,
878                            origin[1] - y_max * scale,
879                            origin[0] + x_max * scale,
880                            origin[1] - y_min * scale,
881                        ],
882                    );
883                }
884            },
885        );
886        // The outermost band reaches the disc radius plus one rim pixel past the ink.
887        let band = stroke_radius(&request.strokes).map_or(0.0, |radius| radius + 1.0);
888        ink = ink.map(|bounds| grown(bounds, band));
889        let padding = request.background.map(|background| background.padding);
890        let mut content = None;
891        for (index, line) in layout.lines.iter().enumerate() {
892            let left = layout.line_offset(line, request.align);
893            let top = layout.line_top(index);
894            include(&mut content, [left, 0.0, left + line.width, layout.height]);
895            if let (Some(padding), true) = (padding, line.width > 0.0) {
896                include(
897                    &mut ink,
898                    grown(
899                        [left, top, left + line.width, top + request.font_size],
900                        padding,
901                    ),
902                );
903            }
904        }
905        let content = content.unwrap_or([0.0, 0.0, 0.0, layout.height]);
906        let last = layout.lines.len().saturating_sub(1);
907        Ok(TextMeasure {
908            first_baseline: layout.line_top(0) + layout.ascent,
909            last_baseline: layout.line_top(last) + layout.ascent,
910            box_width: layout.box_width,
911            box_height: layout.box_height,
912            decoration_margin: request.decoration_margin(),
913            content: grown(content, request.decoration_margin() as f32),
914            ink,
915            line_count: layout.line_count,
916            truncated: layout.truncated,
917        })
918    }
919
920    /// Shapes `request` as [`Self::rasterize`] would, so lines can be broken at any width later.
921    /// `max_width`, fill, strokes, background and content version are ignored.
922    ///
923    /// # Errors
924    /// Returns [`TextRasterError::NoFonts`] without fonts, and
925    /// [`TextRasterError::InvalidRequest`] for values [`Self::rasterize`] rejects.
926    pub fn shape(&self, request: &TextRasterRequest) -> Result<ShapedText, TextRasterError> {
927        validate_request(&TextRasterRequest {
928            text: String::new(),
929            max_width: 0.0,
930            content_version: 1,
931            fill: TextFill::Solid([0; 4]),
932            strokes: Vec::new(),
933            background: None,
934            ..request.clone()
935        })?;
936        if request.text.len() > MAX_TEXT_BYTES {
937            return Err(TextRasterError::InvalidRequest);
938        }
939        if self.fonts.is_empty() {
940            return Err(TextRasterError::NoFonts);
941        }
942        let faces = Faces::new(&self.fonts, request.font_weight)?;
943        let order = self.font_order(request.font_family.as_deref(), request.font_weight);
944        let paragraphs = normalize(&request.text, request.emoji_policy)
945            .split('\n')
946            .map(|paragraph| {
947                let bidi = ParagraphBidiInfo::new(paragraph, None);
948                let glyphs = shape_paragraph(
949                    &faces,
950                    paragraph,
951                    &bidi,
952                    request.font_size,
953                    &order,
954                    request.emoji_policy,
955                    request.letter_spacing,
956                );
957                clusters(&glyphs, paragraph, request.letter_spacing)
958            })
959            .collect();
960        Ok(ShapedText {
961            paragraphs,
962            font_size: request.font_size,
963            line_height: request.line_height,
964            line_advance: request.font_size * request.line_height,
965        })
966    }
967
968    #[allow(clippy::cast_precision_loss)]
969    fn lay_out(
970        &self,
971        faces: &Faces<'_>,
972        request: &TextRasterRequest,
973    ) -> Result<Layout, TextRasterError> {
974        let line_advance = request.font_size * request.line_height;
975        let order = self.font_order(request.font_family.as_deref(), request.font_weight);
976        let clamp = request.clamp.as_ref();
977        let limit = clamp
978            .and_then(|clamp| {
979                line_limit(
980                    request.font_size,
981                    request.line_height,
982                    clamp.max_lines,
983                    clamp.max_height,
984                )
985            })
986            .map_or(usize::MAX, |limit| limit as usize);
987        let mut lines = Vec::new();
988        // Trailing blank lines take no room.
989        let mut kept = 1;
990        let mut clusters = Vec::new();
991        let mut paragraph_start = 0;
992        let mut truncated = false;
993        let normalized = normalize(&request.text, request.emoji_policy);
994        let paragraphs = normalized.split('\n').collect::<Vec<_>>();
995        for (index, paragraph) in paragraphs.iter().enumerate() {
996            let first = clusters.len();
997            let shaped = ShapedParagraph::new(faces, paragraph, None, request, &order);
998            let ranges = break_lines(&shaped.clusters, request.max_width);
999            let mut clamped = false;
1000            for (at, range) in ranges.iter().enumerate() {
1001                let at_line = (first, lines.len());
1002                clamped = lines.len() + 1 >= limit;
1003                let cut = clamped
1004                    && (ranges[at + 1..].iter().any(|range| !range.is_empty())
1005                        || paragraphs[index + 1..]
1006                            .iter()
1007                            .any(|paragraph| !paragraph.is_empty()));
1008                truncated |= cut;
1009                let ellipsis = clamp
1010                    .and_then(|clamp| clamp.ellipsis.as_deref())
1011                    .filter(|_| cut);
1012                let line = match ellipsis {
1013                    Some(ellipsis) => {
1014                        let level = shaped.bidi.paragraph_level;
1015                        let mark =
1016                            ShapedParagraph::new(faces, ellipsis, Some(level), request, &order);
1017                        shaped.place_cut(
1018                            range.clone(),
1019                            &mark,
1020                            request.max_width,
1021                            at_line,
1022                            &mut clusters,
1023                        )
1024                    }
1025                    None => shaped.place(range.clone(), at_line, &mut clusters),
1026                };
1027                if line.has_glyphs {
1028                    kept = lines.len() + 1;
1029                }
1030                lines.push(line);
1031                if clamped {
1032                    break;
1033                }
1034            }
1035            for span in &mut clusters[first..] {
1036                span.bytes = span.bytes.start + paragraph_start..span.bytes.end + paragraph_start;
1037            }
1038            paragraph_start += paragraph.len() + 1;
1039            if clamped {
1040                break;
1041            }
1042        }
1043        lines.truncate(kept);
1044        let line_count = u32::try_from(lines.len()).map_err(|_| TextRasterError::TooLarge)?;
1045        let width = if request.max_width > 0.0 {
1046            request.max_width
1047        } else {
1048            lines.iter().map(|line| line.width).fold(0.0, f32::max)
1049        }
1050        .max(1.0);
1051        let height = box_height(line_count, line_advance, request.font_size).max(1.0);
1052        Ok(Layout {
1053            box_width: checked_dimension(width)?,
1054            box_height: checked_dimension(height)?,
1055            lines,
1056            clusters,
1057            line_count,
1058            line_advance,
1059            half_leading: half_leading(request.font_size, request.line_height),
1060            ascent: request.font_size * 0.8,
1061            descent: request.font_size * 0.2,
1062            width,
1063            height,
1064            truncated,
1065        })
1066    }
1067
1068    #[allow(
1069        clippy::cast_possible_truncation,
1070        clippy::cast_precision_loss,
1071        clippy::too_many_lines
1072    )]
1073    fn rasterize_uncached(
1074        &self,
1075        request: &TextRasterRequest,
1076    ) -> Result<TextRasterResult, TextRasterError> {
1077        let faces = Faces::new(&self.fonts, request.font_weight)?;
1078        let layout = self.lay_out(&faces, request)?;
1079        let (box_width, box_height) = (layout.box_width, layout.box_height);
1080        let mut drawings = HashMap::<(usize, u16), Drawing>::new();
1081        let mut placed = Vec::new();
1082        let (mut overflow_x, mut overflow_y) = (0_i64, 0_i64);
1083        let (mut ink_ascent, mut ink_descent) = (layout.ascent, layout.descent);
1084        layout.each_glyph(
1085            &faces,
1086            request,
1087            &mut drawings,
1088            |drawing, origin, scale, glyph| {
1089                let Some(bounds) = drawing.bounds() else {
1090                    return;
1091                };
1092                let pixels = PixelBox::of(bounds, origin, scale);
1093                overflow_x = overflow_x
1094                    .max(pixels.left.saturating_neg())
1095                    .max(pixels.right.saturating_sub(i64::from(box_width)));
1096                overflow_y = overflow_y
1097                    .max(pixels.top.saturating_neg())
1098                    .max(pixels.bottom.saturating_sub(i64::from(box_height)));
1099                ink_ascent = ink_ascent.max(bounds[3] * scale + glyph.y_offset);
1100                ink_descent = ink_descent.max(-(bounds[1] * scale + glyph.y_offset));
1101                placed.push(((glyph.font, glyph.glyph_index), origin, scale, pixels));
1102            },
1103        );
1104        // A symmetric margin keeps the box centered and leaves room for decorations and overflow.
1105        let (outline, padding) = decoration_extents(request);
1106        let margin = |overflow: i64| -> Result<u32, TextRasterError> {
1107            u32::try_from(overflow)
1108                .map_err(|_| TextRasterError::TooLarge)?
1109                .checked_add(outline)
1110                .map(|margin| margin.max(outline.max(padding)))
1111                .ok_or(TextRasterError::TooLarge)
1112        };
1113        let (margin_x, margin_y) = (margin(overflow_x)?, margin(overflow_y)?);
1114        let width = margin_x
1115            .checked_mul(2)
1116            .and_then(|margins| box_width.checked_add(margins))
1117            .ok_or(TextRasterError::TooLarge)?;
1118        let height = margin_y
1119            .checked_mul(2)
1120            .and_then(|margins| box_height.checked_add(margins))
1121            .ok_or(TextRasterError::TooLarge)?;
1122        let colors = placed
1123            .iter()
1124            .any(|(key, ..)| !matches!(drawings[key], Drawing::Outline(_)));
1125        let pixel_count = raster_pixels(width, height, raster_bytes_per_pixel(request, colors))?;
1126        let mut coverage = vec![0_u8; pixel_count];
1127        // Allocated only once a color glyph is placed.
1128        let mut colors: Option<Vec<u8>> = None;
1129        let mut line_boxes = Vec::with_capacity(layout.lines.len());
1130        for (index, line) in layout.lines.iter().enumerate() {
1131            if line.width > 0.0 {
1132                line_boxes.push((
1133                    layout.line_offset(line, request.align),
1134                    line.width,
1135                    layout.line_top(index),
1136                ));
1137            }
1138        }
1139        for (key, origin, scale, pixels) in placed {
1140            let (origin_x, origin_y) = (
1141                pixels.left + i64::from(margin_x),
1142                pixels.top + i64::from(margin_y),
1143            );
1144            let glyph_width = usize::try_from(pixels.right - pixels.left).unwrap_or(0);
1145            match &drawings[&key] {
1146                Drawing::Outline(outline) => place_glyph(
1147                    &mut coverage,
1148                    width,
1149                    height,
1150                    origin_x,
1151                    origin_y,
1152                    glyph_width,
1153                    &outline.draw(origin, scale, pixels),
1154                ),
1155                drawing => place_color_glyph(
1156                    colors.get_or_insert_with(|| vec![0; pixel_count * 4]),
1157                    width,
1158                    height,
1159                    origin_x,
1160                    origin_y,
1161                    glyph_width,
1162                    &drawing.draw_color(origin, scale, pixels),
1163                ),
1164            }
1165        }
1166        let bands = stroke_bands(request, &coverage, colors.as_deref(), width);
1167        let (rgba8, background) = compose(
1168            request,
1169            &coverage,
1170            colors.as_deref(),
1171            width,
1172            [margin_x, margin_y],
1173            &line_boxes,
1174            &bands,
1175            &RequestLook::of(request, [layout.width, layout.height]),
1176        );
1177        let texture = HostTexture {
1178            content_version: request.content_version,
1179            width,
1180            height,
1181            premultiplication: Premultiplication::Premultiplied,
1182            color_space: RasterColorSpace::Srgb,
1183        };
1184        Ok(TextRasterResult {
1185            descriptor: TextTexture {
1186                texture: texture.clone(),
1187                layout_x: margin_x as f32,
1188                layout_y: margin_y as f32,
1189                layout_width: layout.width,
1190                layout_height: layout.height,
1191                first_baseline: layout.half_leading + layout.ascent,
1192                ascent: ink_ascent,
1193                descent: ink_descent,
1194                line_count: layout.line_count,
1195            },
1196            pixels: HostTexturePixels { texture, rgba8 },
1197            background,
1198        })
1199    }
1200
1201    /// Font try order: `family` first, then families in registration order; within a family,
1202    /// faces by [`weight_order`].
1203    fn font_order(&self, family: Option<&str>, weight: u16) -> Vec<usize> {
1204        // A face without a family is its own group.
1205        let mut groups: Vec<(Option<&str>, Vec<usize>)> = Vec::new();
1206        for (index, font) in self.fonts.iter().enumerate() {
1207            let name = font.family.as_deref();
1208            match groups
1209                .iter_mut()
1210                .find(|(held, _)| name.is_some() && *held == name)
1211            {
1212                Some((_, faces)) => faces.push(index),
1213                None => groups.push((name, vec![index])),
1214            }
1215        }
1216        if let Some(requested) = family {
1217            let wanted = fold_family(requested);
1218            match groups.iter().position(|(_, faces)| {
1219                faces
1220                    .iter()
1221                    .any(|&index| self.fonts[index].aliases.contains(&wanted))
1222            }) {
1223                Some(at) => {
1224                    let preferred = groups.remove(at);
1225                    groups.insert(0, preferred);
1226                }
1227                None if !self.fonts.is_empty() => {
1228                    self.unmatched
1229                        .lock()
1230                        .unwrap_or_else(std::sync::PoisonError::into_inner)
1231                        .insert(requested.to_owned());
1232                }
1233                None => {}
1234            }
1235        }
1236        groups
1237            .into_iter()
1238            .flat_map(|(_, faces)| {
1239                let weights = faces
1240                    .iter()
1241                    .map(|&index| self.fonts[index].weights())
1242                    .collect::<Vec<_>>();
1243                weight_order(&weights, weight)
1244                    .into_iter()
1245                    .map(move |at| faces[at])
1246            })
1247            .collect()
1248    }
1249}
1250
1251/// Faces parsed once per request; shaping tables load lazily.
1252struct Faces<'a> {
1253    parsed: Vec<ttf_parser::Face<'a>>,
1254    shapers: Vec<OnceCell<rustybuzz::Face<'a>>>,
1255    /// Has a COLR, CBDT or sbix table.
1256    color: Vec<bool>,
1257}
1258
1259impl<'a> Faces<'a> {
1260    /// Variable faces are set to `weight`, clamped to their axis.
1261    fn new(fonts: &'a [LoadedFont], weight: u16) -> Result<Self, TextRasterError> {
1262        let parsed = fonts
1263            .iter()
1264            .map(|font| {
1265                let mut face = ttf_parser::Face::parse(&font.source.bytes, font.source.face_index)
1266                    .ok()
1267                    .filter(|face| face.units_per_em() > 0)
1268                    .ok_or_else(|| TextRasterError::InvalidFont(font.source.family.clone()))?;
1269                if let Some((min, _, max)) = font.wght {
1270                    face.set_variation(WGHT, f32::from(weight).clamp(min, max));
1271                }
1272                Ok(face)
1273            })
1274            .collect::<Result<Vec<_>, _>>()?;
1275        Ok(Self {
1276            shapers: parsed.iter().map(|_| OnceCell::new()).collect(),
1277            color: parsed
1278                .iter()
1279                .map(|face| {
1280                    let tables = face.tables();
1281                    tables.colr.is_some() || tables.cbdt.is_some() || tables.sbix.is_some()
1282                })
1283                .collect(),
1284            parsed,
1285        })
1286    }
1287
1288    fn shaper(&self, font: usize) -> &rustybuzz::Face<'a> {
1289        self.shapers[font].get_or_init(|| rustybuzz::Face::from_face(self.parsed[font].clone()))
1290    }
1291
1292    #[allow(clippy::cast_precision_loss)]
1293    fn units_per_em(&self, font: usize) -> f32 {
1294        f32::from(self.parsed[font].units_per_em())
1295    }
1296
1297    fn has(&self, font: usize, character: char) -> bool {
1298        self.parsed[font]
1299            .glyph_index(character)
1300            .is_some_and(|glyph| glyph.0 != 0)
1301    }
1302
1303    /// Whether the font has every visible character of `grapheme`.
1304    fn covers(&self, font: usize, grapheme: &str) -> bool {
1305        grapheme
1306            .chars()
1307            .filter(|&character| !is_default_ignorable(character))
1308            .all(|character| self.has(font, character))
1309    }
1310}
1311
1312/// Replaces emoji with a replacement character under [`EmojiPolicy::Replace`], every line or
1313/// paragraph separator (U+2028 included) with `\n`, and tabs with spaces.
1314fn normalize(text: &str, policy: EmojiPolicy) -> String {
1315    normalize_mapped(text, policy, None)
1316}
1317
1318/// [`normalize`], optionally filling `map` with the source byte of each output byte (grapheme
1319/// start for replaced ones) plus a final entry for `text`'s length.
1320fn normalize_mapped(text: &str, policy: EmojiPolicy, mut map: Option<&mut Vec<usize>>) -> String {
1321    let mut normalized = String::with_capacity(text.len());
1322    for (start, grapheme) in text.grapheme_indices(true) {
1323        let before = normalized.len();
1324        if policy == EmojiPolicy::Replace && is_emoji(grapheme) {
1325            normalized.push('\u{fffd}');
1326        } else if grapheme == "\r\n" {
1327            normalized.push('\n');
1328        } else {
1329            normalized.extend(grapheme.chars().map(|character| match character {
1330                '\r'
1331                | '\u{b}'
1332                | '\u{c}'
1333                | '\u{1c}'..='\u{1e}'
1334                | '\u{85}'
1335                | '\u{2028}'
1336                | '\u{2029}' => '\n',
1337                '\t' => ' ',
1338                other => other,
1339            }));
1340        }
1341        if let Some(map) = map.as_deref_mut() {
1342            // A grapheme that changed length maps to its start.
1343            let written = normalized.len() - before;
1344            if written == grapheme.len() {
1345                map.extend(start..start + written);
1346            } else {
1347                map.extend(std::iter::repeat_n(start, written));
1348            }
1349        }
1350    }
1351    if let Some(map) = map {
1352        map.push(text.len());
1353    }
1354    normalized
1355}
1356
1357/// Emoji presentation per UTS #51, matching `OffscreenTextRasterizer`: an `Emoji_Presentation`
1358/// character, or U+FE0F with a pictograph or keycap, unless U+FE0E asks for text.
1359fn is_emoji(grapheme: &str) -> bool {
1360    if grapheme.contains('\u{fe0e}') {
1361        return false;
1362    }
1363    let selected = grapheme.contains('\u{fe0f}');
1364    grapheme.chars().any(|character| {
1365        in_table(unicode_tables::EMOJI_PRESENTATION, character)
1366            || (selected
1367                && (character == '\u{20e3}'
1368                    || in_table(unicode_tables::EXTENDED_PICTOGRAPHIC, character)))
1369    })
1370}
1371
1372/// Whether `text`'s first non-common script is cursive per CSS Text 3 (no letter spacing).
1373fn is_cursive(text: &str) -> bool {
1374    text.chars()
1375        .map(|character| character.script())
1376        .find(|script| !matches!(script, Script::Common | Script::Inherited | Script::Unknown))
1377        .is_some_and(|script| {
1378            matches!(
1379                script,
1380                Script::Adlam
1381                    | Script::Arabic
1382                    | Script::Hanifi_Rohingya
1383                    | Script::Mandaic
1384                    | Script::Mongolian
1385                    | Script::Nko
1386                    | Script::Phags_Pa
1387                    | Script::Syriac
1388            )
1389        })
1390}
1391
1392fn is_default_ignorable(character: char) -> bool {
1393    in_table(unicode_tables::DEFAULT_IGNORABLE, character)
1394}
1395
1396fn in_table(table: &[(u32, u32)], character: char) -> bool {
1397    let code = u32::from(character);
1398    table
1399        .binary_search_by(|&(first, last)| {
1400            if last < code {
1401                Ordering::Less
1402            } else if first > code {
1403                Ordering::Greater
1404            } else {
1405                Ordering::Equal
1406            }
1407        })
1408        .is_ok()
1409}
1410
1411/// A space that hangs at a line end. Excludes no-break spaces and the visible Ogham space mark.
1412fn hangs(character: char) -> bool {
1413    character.is_whitespace()
1414        && !matches!(character, '\u{a0}' | '\u{2007}' | '\u{202f}' | '\u{1680}')
1415}
1416
1417fn is_hangul(character: char) -> bool {
1418    matches!(
1419        character,
1420        '\u{1100}'..='\u{11ff}'
1421            | '\u{3130}'..='\u{318f}'
1422            | '\u{a960}'..='\u{a97f}'
1423            | '\u{ac00}'..='\u{d7a3}'
1424            | '\u{d7b0}'..='\u{d7ff}'
1425    )
1426}
1427
1428/// Broken and placed lines, in pixels from the layout box's top-left, y down.
1429struct Layout {
1430    lines: Vec<LaidLine>,
1431    /// Logical order, bytes in the normalized text.
1432    clusters: Vec<ClusterSpan>,
1433    line_count: u32,
1434    line_advance: f32,
1435    /// See [`half_leading`].
1436    half_leading: f32,
1437    ascent: f32,
1438    descent: f32,
1439    /// The wrap width, else the widest line.
1440    width: f32,
1441    height: f32,
1442    box_width: u32,
1443    box_height: u32,
1444    /// Whether the request's clamp discarded lines.
1445    truncated: bool,
1446}
1447
1448impl Layout {
1449    /// Start and End follow the paragraph's direction.
1450    fn line_offset(&self, line: &LaidLine, align: TextAlign) -> f32 {
1451        match (align, line.rtl) {
1452            (TextAlign::Center, _) => (self.width - line.width) * 0.5,
1453            (TextAlign::Start, false) | (TextAlign::End, true) => 0.0,
1454            (TextAlign::End, false) | (TextAlign::Start, true) => self.width - line.width,
1455        }
1456    }
1457
1458    #[allow(clippy::cast_precision_loss)]
1459    fn line_top(&self, index: usize) -> f32 {
1460        index as f32 * self.line_advance + self.half_leading
1461    }
1462
1463    /// Calls `place` with each glyph's drawing (cached in `drawings`), origin and pixels per
1464    /// font unit.
1465    #[allow(clippy::cast_precision_loss)]
1466    fn each_glyph(
1467        &self,
1468        faces: &Faces<'_>,
1469        request: &TextRasterRequest,
1470        drawings: &mut HashMap<(usize, u16), Drawing>,
1471        mut place: impl FnMut(&Drawing, [f32; 2], f32, &PositionedGlyph),
1472    ) {
1473        for (index, line) in self.lines.iter().enumerate() {
1474            let offset = self.line_offset(line, request.align);
1475            let baseline = self.line_top(index) + self.ascent;
1476            for glyph in &line.glyphs {
1477                let drawing = drawings
1478                    .entry((glyph.font, glyph.glyph_index))
1479                    .or_insert_with(|| Drawing::of(faces, glyph.font, glyph.glyph_index, request));
1480                let scale = request.font_size / faces.units_per_em(glyph.font);
1481                let origin = [glyph.x + glyph.x_offset + offset, baseline - glyph.y_offset];
1482                place(drawing, origin, scale, glyph);
1483            }
1484        }
1485    }
1486}
1487
1488fn include(bounds: &mut Option<[f32; 4]>, [left, top, right, bottom]: [f32; 4]) {
1489    let held = bounds.get_or_insert([left, top, right, bottom]);
1490    *held = [
1491        held[0].min(left),
1492        held[1].min(top),
1493        held[2].max(right),
1494        held[3].max(bottom),
1495    ];
1496}
1497
1498fn grown([left, top, right, bottom]: [f32; 4], by: f32) -> [f32; 4] {
1499    [left - by, top - by, right + by, bottom + by]
1500}
1501
1502/// Byte range (paragraph-relative during layout, then text-relative) and line of a cluster.
1503#[derive(Clone, Debug)]
1504struct ClusterSpan {
1505    bytes: Range<usize>,
1506    line: usize,
1507    /// The ellipsis of a cut line, with an empty range where the text was cut.
1508    ellipsis: bool,
1509}
1510
1511struct LaidLine {
1512    /// Glyphs left to right, pens from the line's start.
1513    glyphs: Vec<PositionedGlyph>,
1514    /// Excludes hanging trailing spaces.
1515    width: f32,
1516    rtl: bool,
1517    /// Has glyphs, even if none with ink.
1518    has_glyphs: bool,
1519}
1520
1521/// A paragraph shaped and grouped into clusters, its lines not yet placed.
1522struct ShapedParagraph<'a> {
1523    text: &'a str,
1524    bidi: ParagraphBidiInfo<'a>,
1525    glyphs: Vec<ShapedGlyph>,
1526    clusters: Vec<Cluster>,
1527}
1528
1529impl<'a> ShapedParagraph<'a> {
1530    /// Shapes `text` at `level`, else at the level its first strong character gives.
1531    fn new(
1532        faces: &Faces<'_>,
1533        text: &'a str,
1534        level: Option<unicode_bidi::Level>,
1535        request: &TextRasterRequest,
1536        order: &[usize],
1537    ) -> Self {
1538        let bidi = ParagraphBidiInfo::new(text, level);
1539        let glyphs = shape_paragraph(
1540            faces,
1541            text,
1542            &bidi,
1543            request.font_size,
1544            order,
1545            request.emoji_policy,
1546            request.letter_spacing,
1547        );
1548        let clusters = clusters(&glyphs, text, request.letter_spacing);
1549        Self {
1550            text,
1551            bidi,
1552            glyphs,
1553            clusters,
1554        }
1555    }
1556
1557    /// Places the clusters of `range` as line `line` in visual order. Their spans go to `spans`,
1558    /// where this paragraph's clusters are numbered from `cluster_base`.
1559    fn place(
1560        &self,
1561        range: Range<usize>,
1562        (cluster_base, line): (usize, usize),
1563        spans: &mut Vec<ClusterSpan>,
1564    ) -> LaidLine {
1565        self.push_spans(range.clone(), cluster_base, line, spans);
1566        self.position(range, cluster_base)
1567    }
1568
1569    /// [`Self::place`] for the last line a clamp keeps, shortened so `mark` fits after it within
1570    /// `max_width` (non-positive for any width) and ending with `mark` as one more cluster.
1571    fn place_cut(
1572        &self,
1573        range: Range<usize>,
1574        mark: &ShapedParagraph<'_>,
1575        max_width: f32,
1576        (cluster_base, line): (usize, usize),
1577        spans: &mut Vec<ClusterSpan>,
1578    ) -> LaidLine {
1579        let mark_width = advance(&mark.clusters);
1580        let mut end = self.cut_end(range.clone(), mark_width, max_width);
1581        // Spaces before the cut go with the text after it.
1582        while end > range.start && self.clusters[end - 1].hangs {
1583            end -= 1;
1584        }
1585        self.push_spans(range.start..end, cluster_base, line, spans);
1586        let at = self
1587            .clusters
1588            .get(end)
1589            .map_or(self.text.len(), |next| next.start);
1590        spans.push(ClusterSpan {
1591            bytes: at..at,
1592            line,
1593            ellipsis: true,
1594        });
1595        let mut laid = self.position(range.start..end, cluster_base);
1596        // The letter spacing of the last kept cluster, which no longer ends the line.
1597        let gap = self.clusters[range.start..end]
1598            .last()
1599            .map_or(0.0, |cluster| cluster.spacing);
1600        let mut glyphs = mark.position(0..mark.clusters.len(), 0).glyphs;
1601        let shift = if laid.rtl { 0.0 } else { laid.width + gap };
1602        for glyph in &mut glyphs {
1603            glyph.cluster = cluster_base + end;
1604            glyph.x += shift;
1605        }
1606        if laid.rtl {
1607            for glyph in &mut laid.glyphs {
1608                glyph.x += mark_width + gap;
1609            }
1610            glyphs.append(&mut laid.glyphs);
1611            laid.glyphs = glyphs;
1612        } else {
1613            laid.glyphs.append(&mut glyphs);
1614        }
1615        laid.width += mark_width + gap;
1616        laid.has_glyphs = true;
1617        laid
1618    }
1619
1620    /// Where a line holding `range` is cut so `mark_width` more fits in `max_width`: the last
1621    /// soft wrap opportunity (or the paragraph's end) at which it fits, else the last cluster
1622    /// boundary, else the line's start.
1623    fn cut_end(&self, range: Range<usize>, mark_width: f32, max_width: f32) -> usize {
1624        if max_width <= 0.0 {
1625            return range.end;
1626        }
1627        let fits = |end: usize| {
1628            let kept = &self.clusters[range.start..end];
1629            let width = kept
1630                .iter()
1631                .rposition(|cluster| !cluster.hangs)
1632                .map_or(0.0, |last| {
1633                    kept[..=last]
1634                        .iter()
1635                        .fold(0.0, |width, cluster| width + cluster.width)
1636                });
1637            width + mark_width <= max_width
1638        };
1639        let soft = |end: usize| end == self.clusters.len() || self.clusters[end].break_before;
1640        let ends = || (range.start + 1..=range.end).rev();
1641        ends()
1642            .find(|&end| soft(end) && fits(end))
1643            .or_else(|| ends().find(|&end| fits(end)))
1644            .unwrap_or(range.start)
1645    }
1646
1647    fn push_spans(
1648        &self,
1649        range: Range<usize>,
1650        cluster_base: usize,
1651        line: usize,
1652        spans: &mut Vec<ClusterSpan>,
1653    ) {
1654        debug_assert_eq!(spans.len(), cluster_base + range.start);
1655        for index in range {
1656            let end = self
1657                .clusters
1658                .get(index + 1)
1659                .map_or(self.text.len(), |next| next.start);
1660            spans.push(ClusterSpan {
1661                bytes: self.clusters[index].start..end.max(self.clusters[index].start),
1662                line,
1663                ellipsis: false,
1664            });
1665        }
1666    }
1667
1668    /// The clusters of `range` in visual order, pens from the line's start. Trailing spaces
1669    /// hang: no width, nothing drawn.
1670    fn position(&self, range: Range<usize>, cluster_base: usize) -> LaidLine {
1671        let clusters = &self.clusters;
1672        let glyphs = &self.glyphs;
1673        let has_glyphs = !range.is_empty();
1674        let mut end = range.end;
1675        while end > range.start && clusters[end - 1].hangs {
1676            end -= 1;
1677        }
1678        let mut line = LaidLine {
1679            glyphs: Vec::new(),
1680            width: 0.0,
1681            rtl: self.bidi.paragraph_level.is_rtl(),
1682            has_glyphs,
1683        };
1684        if end == range.start {
1685            return line;
1686        }
1687        let bytes = clusters[range.start].start
1688            ..clusters
1689                .get(range.end)
1690                .map_or(self.text.len(), |next| next.start);
1691        let levels = self.bidi.reordered_levels(bytes);
1692        // Letter spacing goes between visual neighbours, never after the line's last cluster.
1693        let mut cluster_of = vec![0; clusters[end - 1].glyphs.end];
1694        for (index, cluster) in clusters[range.start..end].iter().enumerate() {
1695            cluster_of[cluster.glyphs.clone()].fill(range.start + index);
1696        }
1697        let mut x = 0.0_f32;
1698        let mut previous: Option<usize> = None;
1699        for index in visual_order(
1700            clusters[range.start].glyphs.start..clusters[end - 1].glyphs.end,
1701            |index| levels[glyphs[index].cluster].number(),
1702        ) {
1703            let glyph = &glyphs[index];
1704            let cluster = cluster_of[index];
1705            if let Some(before) = previous.filter(|&before| before != cluster) {
1706                x += clusters[before].spacing;
1707            }
1708            previous = Some(cluster);
1709            line.glyphs.push(PositionedGlyph {
1710                font: glyph.font,
1711                glyph_index: glyph.glyph_index,
1712                cluster: cluster_base + cluster,
1713                advance: glyph.advance,
1714                x,
1715                x_offset: glyph.x_offset,
1716                y_offset: glyph.y_offset,
1717            });
1718            x += glyph.advance;
1719        }
1720        line.width = x;
1721        line
1722    }
1723}
1724
1725/// Reorders logical-order glyphs visually per UAX #9 rule L2.
1726fn visual_order(range: Range<usize>, level: impl Fn(usize) -> u8) -> Vec<usize> {
1727    let mut order = range.collect::<Vec<_>>();
1728    let levels = order.iter().map(|&index| level(index)).collect::<Vec<_>>();
1729    let highest = levels.iter().copied().max().unwrap_or(0);
1730    let Some(lowest_odd) = levels.iter().copied().filter(|level| level % 2 == 1).min() else {
1731        return order;
1732    };
1733    let mut current = levels;
1734    for at_least in (lowest_odd..=highest).rev() {
1735        let mut start = 0;
1736        while start < order.len() {
1737            if current[start] < at_least {
1738                start += 1;
1739                continue;
1740            }
1741            let end = (start..order.len())
1742                .find(|&index| current[index] < at_least)
1743                .unwrap_or(order.len());
1744            order[start..end].reverse();
1745            current[start..end].reverse();
1746            start = end;
1747        }
1748    }
1749    order
1750}
1751
1752/// A run with one direction, script and font.
1753#[derive(Clone, Debug, PartialEq)]
1754struct Run {
1755    range: Range<usize>,
1756    font: usize,
1757    script: Option<Script>,
1758    rtl: bool,
1759}
1760
1761/// Splits a paragraph into runs.
1762///
1763/// Each grapheme takes the first font in `order` that covers it. Common-only graphemes (spaces,
1764/// digits, punctuation) stay in the previous font when it covers them and take the neighbouring
1765/// script. Uncovered graphemes take their base character's font, else the previous font. Emoji
1766/// prefer color fonts under [`EmojiPolicy::Color`] and text fonts otherwise (as does U+FE0E).
1767fn itemize(
1768    faces: &Faces<'_>,
1769    paragraph: &str,
1770    bidi: &ParagraphBidiInfo<'_>,
1771    order: &[usize],
1772    policy: EmojiPolicy,
1773) -> Vec<Run> {
1774    let first = order.first().copied().unwrap_or(0);
1775    let (color, text): (Vec<usize>, Vec<usize>) =
1776        order.iter().partition(|&&font| faces.color[font]);
1777    let color_first = color.iter().chain(&text).copied().collect::<Vec<_>>();
1778    let text_first = text.iter().chain(&color).copied().collect::<Vec<_>>();
1779    let fits = |font: usize, color_wanted: bool| {
1780        faces.color[font] == color_wanted
1781            || if color_wanted {
1782                color.is_empty()
1783            } else {
1784                text.is_empty()
1785            }
1786    };
1787    let mut graphemes = Vec::<(usize, usize, Option<Script>, bool)>::new();
1788    let mut current = None;
1789    for (start, grapheme) in paragraph.grapheme_indices(true) {
1790        let script = grapheme
1791            .chars()
1792            .map(|character| character.script())
1793            .find(|script| !matches!(script, Script::Common | Script::Inherited | Script::Unknown));
1794        let wants_color = if grapheme.contains('\u{fe0e}') {
1795            Some(false)
1796        } else if is_emoji(grapheme) {
1797            Some(policy == EmojiPolicy::Color)
1798        } else {
1799            None
1800        };
1801        let order = match wants_color {
1802            Some(true) => color_first.as_slice(),
1803            Some(false) => text_first.as_slice(),
1804            None => order,
1805        };
1806        let stays = current.filter(|&font| {
1807            script.is_none()
1808                && wants_color.is_none_or(|wanted| fits(font, wanted))
1809                && faces.covers(font, grapheme)
1810        });
1811        let font = stays
1812            .or_else(|| {
1813                order
1814                    .iter()
1815                    .copied()
1816                    .find(|&font| faces.covers(font, grapheme))
1817            })
1818            .or_else(|| {
1819                let base = grapheme
1820                    .chars()
1821                    .find(|&character| !is_default_ignorable(character))?;
1822                order.iter().copied().find(|&font| faces.has(font, base))
1823            })
1824            .or(current)
1825            .unwrap_or(first);
1826        current = Some(font);
1827        graphemes.push((start, font, script, bidi.levels[start].is_rtl()));
1828    }
1829    let leading = graphemes.iter().find_map(|grapheme| grapheme.2);
1830    let mut before = leading;
1831    for grapheme in &mut graphemes {
1832        match grapheme.2 {
1833            Some(script) => before = Some(script),
1834            None => grapheme.2 = before,
1835        }
1836    }
1837    let mut runs = Vec::<Run>::new();
1838    for (index, &(start, font, script, rtl)) in graphemes.iter().enumerate() {
1839        let end = graphemes
1840            .get(index + 1)
1841            .map_or(paragraph.len(), |next| next.0);
1842        match runs.last_mut() {
1843            Some(run) if run.font == font && run.script == script && run.rtl == rtl => {
1844                run.range.end = end;
1845            }
1846            _ => runs.push(Run {
1847                range: start..end,
1848                font,
1849                script,
1850                rtl,
1851            }),
1852        }
1853    }
1854    runs
1855}
1856
1857fn shaping_script(script: Script) -> Option<rustybuzz::Script> {
1858    let code: [u8; 4] = script.short_name().as_bytes().try_into().ok()?;
1859    rustybuzz::Script::from_iso15924_tag(ttf_parser::Tag::from_bytes(&code))
1860}
1861
1862/// Shapes each run with surrounding text as context, returning glyphs in logical order.
1863fn shape_paragraph(
1864    faces: &Faces<'_>,
1865    paragraph: &str,
1866    bidi: &ParagraphBidiInfo<'_>,
1867    font_size: f32,
1868    order: &[usize],
1869    policy: EmojiPolicy,
1870    letter_spacing: f32,
1871) -> Vec<ShapedGlyph> {
1872    // CSS Text 3: letter spacing disables optional ligatures only.
1873    let features = if letter_spacing == 0.0 {
1874        Vec::new()
1875    } else {
1876        [b"liga", b"clig", b"dlig", b"hlig"]
1877            .map(|tag| rustybuzz::Feature::new(ttf_parser::Tag::from_bytes(tag), 0, ..))
1878            .to_vec()
1879    };
1880    let mut glyphs = Vec::new();
1881    for run in itemize(faces, paragraph, bidi, order, policy) {
1882        let face = faces.shaper(run.font);
1883        let units = faces.units_per_em(run.font);
1884        let mut buffer = UnicodeBuffer::new();
1885        buffer.push_str(&paragraph[run.range.clone()]);
1886        buffer.set_pre_context(&paragraph[..run.range.start]);
1887        buffer.set_post_context(&paragraph[run.range.end..]);
1888        buffer.set_direction(if run.rtl {
1889            Direction::RightToLeft
1890        } else {
1891            Direction::LeftToRight
1892        });
1893        match run.script.and_then(shaping_script) {
1894            Some(script) => buffer.set_script(script),
1895            None => buffer.guess_segment_properties(),
1896        }
1897        let shaped = rustybuzz::shape(face, &features, buffer);
1898        let first = glyphs.len();
1899        for (info, position) in shaped.glyph_infos().iter().zip(shaped.glyph_positions()) {
1900            #[allow(clippy::cast_precision_loss)]
1901            glyphs.push(ShapedGlyph {
1902                font: run.font,
1903                // AAT `morx` substitutions may name a missing glyph; draw it as `.notdef`.
1904                glyph_index: u16::try_from(info.glyph_id)
1905                    .ok()
1906                    .filter(|&glyph| glyph < face.number_of_glyphs())
1907                    .unwrap_or(0),
1908                cluster: run.range.start + usize::try_from(info.cluster).unwrap_or(0),
1909                advance: position.x_advance as f32 * font_size / units,
1910                x_offset: position.x_offset as f32 * font_size / units,
1911                y_offset: position.y_offset as f32 * font_size / units,
1912            });
1913        }
1914        // RTL runs come back in visual order; line breaking needs logical order.
1915        if run.rtl {
1916            glyphs[first..].reverse();
1917        }
1918    }
1919    glyphs
1920}
1921
1922#[derive(Copy, Clone, Debug)]
1923struct ShapedGlyph {
1924    font: usize,
1925    glyph_index: u16,
1926    /// Byte offset in the paragraph.
1927    cluster: usize,
1928    advance: f32,
1929    /// Shaper offset from the pen position in pixels, y up.
1930    x_offset: f32,
1931    y_offset: f32,
1932}
1933
1934/// Glyphs a line never splits.
1935#[derive(Clone, Debug, PartialEq)]
1936struct Cluster {
1937    glyphs: Range<usize>,
1938    /// Byte offset in the paragraph.
1939    start: usize,
1940    /// Advance including letter spacing.
1941    width: f32,
1942    /// Letter spacing included in `width`.
1943    spacing: f32,
1944    /// Only hanging spaces.
1945    hangs: bool,
1946    /// UAX #14 allows a break before it.
1947    break_before: bool,
1948}
1949
1950/// Groups glyphs into clusters with UAX #14 break opportunities, tailored so Korean breaks
1951/// between words rather than between Hangul characters. Cursive clusters get no letter spacing.
1952fn clusters(glyphs: &[ShapedGlyph], paragraph: &str, letter_spacing: f32) -> Vec<Cluster> {
1953    let mut opportunities = unicode_linebreak::linebreaks(paragraph)
1954        .filter(|&(at, kind)| {
1955            kind == BreakOpportunity::Allowed
1956                && !(paragraph[..at].chars().next_back().is_some_and(is_hangul)
1957                    && paragraph[at..].chars().next().is_some_and(is_hangul))
1958        })
1959        .map(|(at, _)| at)
1960        .peekable();
1961    let mut clusters = Vec::<Cluster>::new();
1962    for (index, glyph) in glyphs.iter().enumerate() {
1963        match clusters.last_mut() {
1964            Some(cluster) if cluster.start == glyph.cluster => {
1965                cluster.glyphs.end = index + 1;
1966                cluster.width += glyph.advance;
1967            }
1968            _ => clusters.push(Cluster {
1969                glyphs: index..index + 1,
1970                start: glyph.cluster,
1971                width: glyph.advance,
1972                spacing: 0.0,
1973                hangs: false,
1974                break_before: false,
1975            }),
1976        }
1977    }
1978    for index in 0..clusters.len() {
1979        let start = clusters[index].start;
1980        let end = clusters
1981            .get(index + 1)
1982            .map(|next| next.start)
1983            .filter(|&end| end > start)
1984            .unwrap_or_else(|| {
1985                paragraph[start..]
1986                    .chars()
1987                    .next()
1988                    .map_or(start, |character| start + character.len_utf8())
1989            });
1990        clusters[index].hangs = paragraph[start..end].chars().all(hangs);
1991        if letter_spacing != 0.0 && !is_cursive(&paragraph[start..end]) {
1992            clusters[index].spacing = letter_spacing;
1993            clusters[index].width += letter_spacing;
1994        }
1995        let mut found = false;
1996        while let Some(&at) = opportunities.peek() {
1997            if at > start {
1998                break;
1999            }
2000            opportunities.next();
2001            found = true;
2002        }
2003        clusters[index].break_before = index > 0 && found;
2004    }
2005    clusters
2006}
2007
2008/// Breaks clusters into lines no wider than `max_width` (non-positive does not wrap) at the
2009/// last fitting opportunity, else between clusters. Hanging spaces never overflow a line.
2010fn break_lines(clusters: &[Cluster], max_width: f32) -> Vec<Range<usize>> {
2011    let mut lines = Vec::new();
2012    let mut start = 0;
2013    let mut x = 0.0_f32;
2014    // Latest break opportunity and the pen position there.
2015    let mut opportunity: Option<(usize, f32)> = None;
2016    for (index, cluster) in clusters.iter().enumerate() {
2017        if cluster.break_before && index > start {
2018            opportunity = Some((index, x));
2019        }
2020        let fits = |x: f32| x + cluster.width - cluster.spacing <= max_width;
2021        if max_width > 0.0 && !cluster.hangs && index > start && !fits(x) {
2022            let (end, width) = opportunity.unwrap_or((index, x));
2023            lines.push(start..end);
2024            start = end;
2025            x -= width;
2026            opportunity = None;
2027            // The carried-over text is still too wide, so break again before this cluster.
2028            if index > start && !fits(x) {
2029                lines.push(start..index);
2030                start = index;
2031                x = 0.0;
2032            }
2033        }
2034        x += cluster.width;
2035    }
2036    lines.push(start..clusters.len());
2037    lines
2038}
2039
2040#[derive(Copy, Clone, Debug)]
2041struct PositionedGlyph {
2042    font: usize,
2043    glyph_index: u16,
2044    /// Cluster index in logical order.
2045    cluster: usize,
2046    /// Excludes letter spacing.
2047    advance: f32,
2048    /// Pen position from the line's start.
2049    x: f32,
2050    /// Shaper offset from the pen position in pixels, y up.
2051    x_offset: f32,
2052    y_offset: f32,
2053}
2054
2055/// An outline filled with the text paint, or under [`EmojiPolicy::Color`] a color form.
2056enum Drawing {
2057    Outline(Outline),
2058    Painting(color::Painting),
2059    Bitmap(color::Bitmap),
2060}
2061
2062impl Drawing {
2063    /// COLR painting, else bitmap, else outline. The painting uses the text color opaque; its
2064    /// alpha applies to the whole glyph at composition.
2065    fn of(faces: &Faces<'_>, font: usize, glyph: u16, request: &TextRasterRequest) -> Self {
2066        let face = &faces.parsed[font];
2067        if request.emoji_policy == EmojiPolicy::Color && faces.color[font] {
2068            let [red, green, blue, _] = request.fill.foreground();
2069            if let Some(painting) = color::Painting::of(face, glyph, [red, green, blue, 255]) {
2070                return Self::Painting(painting);
2071            }
2072            if let Some(bitmap) = color::Bitmap::of(face, glyph, request.font_size) {
2073                return Self::Bitmap(bitmap);
2074            }
2075        }
2076        Self::Outline(Outline::of(face, glyph))
2077    }
2078
2079    /// Conservative `[x_min, y_min, x_max, y_max]` in font units.
2080    fn bounds(&self) -> Option<[f32; 4]> {
2081        match self {
2082            Self::Outline(outline) => outline.bounds,
2083            Self::Painting(painting) => painting.bounds(),
2084            Self::Bitmap(bitmap) => Some(bitmap.bounds()),
2085        }
2086    }
2087
2088    /// Tight `[x_min, y_min, x_max, y_max]` in font units of what is actually drawn.
2089    fn ink_bounds(&self) -> Option<[f32; 4]> {
2090        match self {
2091            Self::Outline(outline) => outline.curve_bounds(),
2092            Self::Painting(painting) => painting.bounds(),
2093            Self::Bitmap(bitmap) => bitmap.ink_bounds(),
2094        }
2095    }
2096
2097    /// Premultiplied RGBA8; empty for an outline.
2098    fn draw_color(&self, origin: [f32; 2], scale: f32, pixels: PixelBox) -> Vec<u8> {
2099        match self {
2100            Self::Outline(_) => Vec::new(),
2101            Self::Painting(painting) => painting.draw(origin, scale, pixels),
2102            Self::Bitmap(bitmap) => bitmap.draw(origin, scale, pixels),
2103        }
2104    }
2105}
2106
2107/// A glyph outline in font units, y up.
2108#[derive(Default)]
2109struct Outline {
2110    segments: Vec<Segment>,
2111    /// Bounds of all points, control points included.
2112    bounds: Option<[f32; 4]>,
2113}
2114
2115enum Segment {
2116    Line([f32; 2], [f32; 2]),
2117    Quad([f32; 2], [f32; 2], [f32; 2]),
2118    Cubic([f32; 2], [f32; 2], [f32; 2], [f32; 2]),
2119}
2120
2121/// Pixel box in the layout box, right and bottom exclusive.
2122#[derive(Copy, Clone, Debug)]
2123struct PixelBox {
2124    left: i64,
2125    top: i64,
2126    right: i64,
2127    bottom: i64,
2128}
2129
2130impl PixelBox {
2131    #[allow(clippy::cast_possible_truncation)]
2132    fn of(bounds: [f32; 4], origin: [f32; 2], scale: f32) -> Self {
2133        let [x_min, y_min, x_max, y_max] = bounds;
2134        // Same expression as `Outline::draw`, so every point lands inside.
2135        Self {
2136            left: (origin[0] + x_min * scale).floor() as i64,
2137            top: (origin[1] - y_max * scale).floor() as i64,
2138            right: (origin[0] + x_max * scale).ceil() as i64,
2139            bottom: (origin[1] - y_min * scale).ceil() as i64,
2140        }
2141    }
2142}
2143
2144#[cfg(test)]
2145thread_local! {
2146    // Already `const`; clippy misreads the emulated-TLS expansion used on Android.
2147    #[allow(clippy::missing_const_for_thread_local)]
2148    static OUTLINES_READ: std::cell::Cell<usize> = const { std::cell::Cell::new(0) };
2149}
2150
2151impl Outline {
2152    fn of(face: &ttf_parser::Face<'_>, glyph: u16) -> Self {
2153        #[cfg(test)]
2154        OUTLINES_READ.with(|read| read.set(read.get() + 1));
2155        let mut sink = OutlineSink::default();
2156        face.outline_glyph(GlyphId(glyph), &mut sink);
2157        sink.close();
2158        if sink.overflow {
2159            return Self::default();
2160        }
2161        sink.outline
2162    }
2163
2164    #[allow(
2165        clippy::cast_possible_truncation,
2166        clippy::cast_sign_loss,
2167        clippy::cast_precision_loss
2168    )]
2169    fn draw(&self, origin: [f32; 2], scale: f32, pixels: PixelBox) -> Vec<u8> {
2170        let width = usize::try_from(pixels.right - pixels.left).unwrap_or(0);
2171        let height = usize::try_from(pixels.bottom - pixels.top).unwrap_or(0);
2172        let (left, top) = (pixels.left as f32, pixels.top as f32);
2173        let raster = self.raster(width, height, |[x, y]| {
2174            point(origin[0] + x * scale - left, (origin[1] - y * scale) - top)
2175        });
2176        let mut alpha = vec![0_u8; width * height];
2177        raster.for_each_pixel(|index, coverage| {
2178            alpha[index] = (coverage.min(1.0) * 255.0).round() as u8;
2179        });
2180        alpha
2181    }
2182}
2183
2184impl Outline {
2185    /// Bounds of the curves themselves (endpoints and extrema), tighter than `bounds`.
2186    fn curve_bounds(&self) -> Option<[f32; 4]> {
2187        let mut bounds = None;
2188        let mut hold = |[x, y]: [f32; 2]| include(&mut bounds, [x, y, x, y]);
2189        for segment in &self.segments {
2190            match *segment {
2191                Segment::Line(from, to) => {
2192                    hold(from);
2193                    hold(to);
2194                }
2195                Segment::Quad(from, control, to) => {
2196                    hold(from);
2197                    hold(to);
2198                    for axis in 0..2 {
2199                        let curvature = from[axis] - 2.0 * control[axis] + to[axis];
2200                        let t = (from[axis] - control[axis]) / curvature;
2201                        if t > 0.0 && t < 1.0 {
2202                            hold(std::array::from_fn(|axis| {
2203                                let u = 1.0 - t;
2204                                u * u * from[axis] + 2.0 * u * t * control[axis] + t * t * to[axis]
2205                            }));
2206                        }
2207                    }
2208                }
2209                Segment::Cubic(from, first, second, to) => {
2210                    hold(from);
2211                    hold(to);
2212                    for axis in 0..2 {
2213                        let [p0, p1, p2, p3] = [from[axis], first[axis], second[axis], to[axis]];
2214                        for t in quadratic_roots(
2215                            -p0 + 3.0 * (p1 - p2) + p3,
2216                            2.0 * (p0 - 2.0 * p1 + p2),
2217                            p1 - p0,
2218                        )
2219                        .into_iter()
2220                        .flatten()
2221                        .filter(|t| *t > 0.0 && *t < 1.0)
2222                        {
2223                            hold(std::array::from_fn(|axis| {
2224                                let u = 1.0 - t;
2225                                u * u * u * from[axis]
2226                                    + 3.0 * u * u * t * first[axis]
2227                                    + 3.0 * u * t * t * second[axis]
2228                                    + t * t * t * to[axis]
2229                            }));
2230                        }
2231                    }
2232                }
2233            }
2234        }
2235        bounds
2236    }
2237
2238    fn raster(&self, width: usize, height: usize, at: impl Fn([f32; 2]) -> Point) -> Rasterizer {
2239        let mut raster = Rasterizer::new(width, height);
2240        for segment in &self.segments {
2241            match *segment {
2242                Segment::Line(from, to) => raster.draw_line(at(from), at(to)),
2243                Segment::Quad(from, control, to) => raster.draw_quad(at(from), at(control), at(to)),
2244                Segment::Cubic(from, first, second, to) => {
2245                    raster.draw_cubic(at(from), at(first), at(second), at(to));
2246                }
2247            }
2248        }
2249        raster
2250    }
2251}
2252
2253/// Real roots of `a t^2 + b t + c`; non-finite results count as none.
2254fn quadratic_roots(a: f32, b: f32, c: f32) -> [Option<f32>; 2] {
2255    let finite = |t: f32| t.is_finite().then_some(t);
2256    if a.abs() <= f32::EPSILON * (b.abs() + c.abs()) {
2257        return [finite(-c / b), None];
2258    }
2259    let discriminant = b * b - 4.0 * a * c;
2260    if discriminant < 0.0 {
2261        return [None, None];
2262    }
2263    let root = discriminant.sqrt();
2264    [
2265        finite((-b + root) / (2.0 * a)),
2266        finite((-b - root) / (2.0 * a)),
2267    ]
2268}
2269
2270/// Most segments one glyph outline may hold; a glyph past it draws nothing.
2271const MAX_GLYPH_SEGMENTS: usize = 65_536;
2272
2273#[derive(Default)]
2274struct OutlineSink {
2275    outline: Outline,
2276    start: [f32; 2],
2277    pen: [f32; 2],
2278    overflow: bool,
2279}
2280
2281impl OutlineSink {
2282    /// Whether another segment fits; the font parser cannot be stopped, so past the limit the
2283    /// sink only stops recording.
2284    fn room(&mut self) -> bool {
2285        self.overflow |= self.outline.segments.len() >= MAX_GLYPH_SEGMENTS;
2286        !self.overflow
2287    }
2288
2289    fn include(&mut self, points: &[[f32; 2]]) {
2290        for &[x, y] in points {
2291            let bounds = self.outline.bounds.get_or_insert([x, y, x, y]);
2292            *bounds = [
2293                bounds[0].min(x),
2294                bounds[1].min(y),
2295                bounds[2].max(x),
2296                bounds[3].max(y),
2297            ];
2298        }
2299    }
2300}
2301
2302impl OutlineBuilder for OutlineSink {
2303    fn move_to(&mut self, x: f32, y: f32) {
2304        self.close();
2305        self.start = [x, y];
2306        self.pen = [x, y];
2307    }
2308
2309    fn line_to(&mut self, x: f32, y: f32) {
2310        if !self.room() {
2311            return;
2312        }
2313        let to = [x, y];
2314        self.include(&[self.pen, to]);
2315        self.outline.segments.push(Segment::Line(self.pen, to));
2316        self.pen = to;
2317    }
2318
2319    fn quad_to(&mut self, x1: f32, y1: f32, x: f32, y: f32) {
2320        if !self.room() {
2321            return;
2322        }
2323        let (control, to) = ([x1, y1], [x, y]);
2324        self.include(&[self.pen, control, to]);
2325        self.outline
2326            .segments
2327            .push(Segment::Quad(self.pen, control, to));
2328        self.pen = to;
2329    }
2330
2331    fn curve_to(&mut self, x1: f32, y1: f32, x2: f32, y2: f32, x: f32, y: f32) {
2332        if !self.room() {
2333            return;
2334        }
2335        let (first, second, to) = ([x1, y1], [x2, y2], [x, y]);
2336        self.include(&[self.pen, first, second, to]);
2337        self.outline
2338            .segments
2339            .push(Segment::Cubic(self.pen, first, second, to));
2340        self.pen = to;
2341    }
2342
2343    fn close(&mut self) {
2344        // A contour already back at its start needs no closing line.
2345        if self.pen.map(f32::to_bits) != self.start.map(f32::to_bits) {
2346            self.line_to(self.start[0], self.start[1]);
2347        }
2348    }
2349}
2350
2351fn validate_request(request: &TextRasterRequest) -> Result<(), TextRasterError> {
2352    if request.font_size.is_finite()
2353        && request.font_size > 0.0
2354        && request.font_size <= MAX_FONT_SIZE
2355        && request.text.len() <= MAX_TEXT_BYTES
2356        && request.max_width.is_finite()
2357        && request.max_width <= MAX_TEXT_BOX_PIXELS
2358        && request.line_height.is_finite()
2359        && request.line_height > 0.0
2360        && request.line_height <= MAX_LINE_HEIGHT
2361        && request.letter_spacing.is_finite()
2362        && request.letter_spacing >= LETTER_SPACING_RANGE.start() * request.font_size
2363        && request.letter_spacing <= LETTER_SPACING_RANGE.end() * request.font_size
2364        && (1..=1000).contains(&request.font_weight)
2365        && request.content_version > 0
2366        && request.fill.is_valid()
2367        && request.strokes.len() <= MAX_STROKES
2368        && request
2369            .strokes
2370            .iter()
2371            .all(|stroke| stroke.width.is_finite() && stroke.width > 0.0)
2372        && stroke_radius(&request.strokes).is_none_or(|radius| radius <= MAX_STROKE_EXTENT)
2373        && request.background.is_none_or(|background| {
2374            background.padding.is_finite()
2375                && background.padding >= 0.0
2376                && background.padding <= MAX_BACKGROUND_PADDING
2377        })
2378        && request.clamp.as_ref().is_none_or(|clamp| {
2379            clamp.max_lines != Some(0)
2380                && clamp.max_height.is_finite()
2381                && clamp.ellipsis.as_ref().is_none_or(|ellipsis| {
2382                    ellipsis.len() <= MAX_ELLIPSIS_BYTES && !ellipsis.contains('\n')
2383                })
2384        })
2385    {
2386        Ok(())
2387    } else {
2388        Err(TextRasterError::InvalidRequest)
2389    }
2390}
2391
2392fn checked_dimension(value: f32) -> Result<u32, TextRasterError> {
2393    if value.is_finite() && value > 0.0 && value.ceil() <= MAX_TEXT_BOX_PIXELS {
2394        #[allow(clippy::cast_possible_truncation, clippy::cast_sign_loss)]
2395        Ok(value.ceil() as u32)
2396    } else {
2397        Err(TextRasterError::TooLarge)
2398    }
2399}
2400
2401/// Max-combines a glyph's coverage into the mask so overlapping glyphs never erase each other.
2402fn place_glyph(
2403    mask: &mut [u8],
2404    width: u32,
2405    height: u32,
2406    origin_x: i64,
2407    origin_y: i64,
2408    glyph_width: usize,
2409    alpha: &[u8],
2410) {
2411    for (index, coverage) in alpha.iter().copied().enumerate() {
2412        let x = origin_x + i64::try_from(index % glyph_width.max(1)).unwrap_or(0);
2413        let y = origin_y + i64::try_from(index / glyph_width.max(1)).unwrap_or(0);
2414        if x < 0 || y < 0 || x >= i64::from(width) || y >= i64::from(height) {
2415            continue;
2416        }
2417        let pixel =
2418            u64::try_from(y).unwrap_or(0) * u64::from(width) + u64::try_from(x).unwrap_or(0);
2419        let slot = &mut mask[usize::try_from(pixel).unwrap_or(0)];
2420        *slot = (*slot).max(coverage);
2421    }
2422}
2423
2424/// Composites a color glyph over the color layer; later glyphs go on top.
2425fn place_color_glyph(
2426    colors: &mut [u8],
2427    width: u32,
2428    height: u32,
2429    origin_x: i64,
2430    origin_y: i64,
2431    glyph_width: usize,
2432    rgba8: &[u8],
2433) {
2434    for (index, source) in rgba8.as_chunks::<4>().0.iter().enumerate() {
2435        let x = origin_x + i64::try_from(index % glyph_width.max(1)).unwrap_or(0);
2436        let y = origin_y + i64::try_from(index / glyph_width.max(1)).unwrap_or(0);
2437        if x < 0 || y < 0 || x >= i64::from(width) || y >= i64::from(height) || source[3] == 0 {
2438            continue;
2439        }
2440        let pixel =
2441            u64::try_from(y).unwrap_or(0) * u64::from(width) + u64::try_from(x).unwrap_or(0);
2442        let slot = &mut colors[usize::try_from(pixel).unwrap_or(0) * 4..][..4];
2443        let blended = over(
2444            std::array::from_fn(|channel| u32::from(source[channel])),
2445            std::array::from_fn(|channel| u32::from(slot[channel])),
2446        );
2447        for (byte, value) in slot.iter_mut().zip(blended) {
2448            *byte = u8::try_from(value.min(255)).unwrap_or(u8::MAX);
2449        }
2450    }
2451}
2452
2453impl TextRasterRequest {
2454    /// Whole pixels the strokes or background reach past the layout box. The texture margin
2455    /// ([`TextTexture::layout_x`]) adds room for ink overflow to this.
2456    #[must_use]
2457    pub fn decoration_margin(&self) -> u32 {
2458        let (outline, padding) = decoration_extents(self);
2459        outline.max(padding)
2460    }
2461}
2462
2463/// Whole-pixel reach of the outermost stroke past the ink and the background past the box.
2464fn decoration_extents(request: &TextRasterRequest) -> (u32, u32) {
2465    let outline = stroke_radius(&request.strokes).map_or(0, disc_extent);
2466    #[allow(clippy::cast_possible_truncation, clippy::cast_sign_loss)]
2467    let padding = request
2468        .background
2469        .map_or(0, |background| background.padding.ceil() as u32);
2470    (outline, padding)
2471}
2472
2473/// Sum of stroke widths, in order; `None` without strokes.
2474fn stroke_radius(strokes: &[TextStroke]) -> Option<f32> {
2475    let mut radius = None;
2476    for stroke in strokes {
2477        radius = Some(radius.unwrap_or(0.0) + stroke.width);
2478    }
2479    radius
2480}
2481
2482/// Integer radius of the disc a band of radius `width` dilates by.
2483#[allow(clippy::cast_possible_truncation, clippy::cast_sign_loss)]
2484fn disc_extent(width: f32) -> u32 {
2485    (width + 0.5).ceil() as u32
2486}
2487
2488/// Premultiplies `color` by `coverage`, truncating each product to a byte. Pinned rasters
2489/// depend on this truncation.
2490fn premultiplied(color: [u8; 4], coverage: u8) -> [u32; 4] {
2491    let alpha = u32::from(coverage) * u32::from(color[3]) / 255;
2492    [
2493        u32::from(color[0]) * alpha / 255,
2494        u32::from(color[1]) * alpha / 255,
2495        u32::from(color[2]) * alpha / 255,
2496        alpha,
2497    ]
2498}
2499
2500fn over(source: [u32; 4], destination: [u32; 4]) -> [u32; 4] {
2501    let keep = 255 - source[3];
2502    std::array::from_fn(|channel| source[channel] + (destination[channel] * keep + 127) / 255)
2503}
2504
2505trait PixelLook {
2506    /// Straight sRGB fill at `index`; `point` is the pixel center in the layout box.
2507    fn fill(&self, index: usize, point: [f32; 2]) -> [u8; 4];
2508    fn band(&self, stroke: usize, index: usize) -> [u8; 4];
2509    /// 8-bit opacity applied to the glyph layers together; `None` for opaque.
2510    fn fade(&self, _index: usize) -> Option<u32> {
2511        None
2512    }
2513}
2514
2515struct RequestLook<'a> {
2516    foreground: [u8; 4],
2517    gradient: Option<gradient::PreparedGradient<'a>>,
2518    strokes: &'a [TextStroke],
2519}
2520
2521impl<'a> RequestLook<'a> {
2522    fn of(request: &'a TextRasterRequest, layout_size: [f32; 2]) -> Self {
2523        Self {
2524            foreground: request.fill.foreground(),
2525            gradient: match &request.fill {
2526                TextFill::Solid(_) => None,
2527                TextFill::Gradient(gradient) => Some(gradient.prepared(layout_size)),
2528            },
2529            strokes: &request.strokes,
2530        }
2531    }
2532}
2533
2534impl PixelLook for RequestLook<'_> {
2535    #[inline]
2536    fn fill(&self, _: usize, point: [f32; 2]) -> [u8; 4] {
2537        self.gradient
2538            .as_ref()
2539            .map_or(self.foreground, |gradient| gradient.rgba8_at(point))
2540    }
2541
2542    #[inline]
2543    fn band(&self, stroke: usize, _: usize) -> [u8; 4] {
2544        self.strokes[stroke].color
2545    }
2546}
2547
2548/// Dilates coverage (including color glyph alpha) once per stroke, by the cumulative width.
2549fn stroke_bands(
2550    request: &TextRasterRequest,
2551    coverage: &[u8],
2552    colors: Option<&[u8]>,
2553    width: u32,
2554) -> Vec<Vec<u8>> {
2555    if request.strokes.is_empty() {
2556        return Vec::new();
2557    }
2558    let height = u32::try_from(coverage.len() / width.max(1) as usize).unwrap_or(0);
2559    let ink = colors.map(|colors| {
2560        coverage
2561            .iter()
2562            .zip(colors.as_chunks::<4>().0)
2563            .map(|(&text, color)| text.max(color[3]))
2564            .collect::<Vec<_>>()
2565    });
2566    let ink = ink.as_deref().unwrap_or(coverage);
2567    let mut radius = 0.0;
2568    request
2569        .strokes
2570        .iter()
2571        .map(|stroke| {
2572            radius += stroke.width;
2573            dilate(ink, width, height, radius)
2574        })
2575        .collect()
2576}
2577
2578/// Composes text over strokes over line boxes into premultiplied RGBA8, in integers except for
2579/// gradient colors so every target matches. `bands` are innermost first and drawn outermost
2580/// first. With a split background the boxes are returned as their own plane.
2581#[allow(
2582    clippy::cast_possible_truncation,
2583    clippy::cast_sign_loss,
2584    clippy::cast_precision_loss,
2585    clippy::too_many_arguments
2586)]
2587fn compose(
2588    request: &TextRasterRequest,
2589    coverage: &[u8],
2590    colors: Option<&[u8]>,
2591    width: u32,
2592    margin: [u32; 2],
2593    line_boxes: &[(f32, f32, f32)],
2594    bands: &[Vec<u8>],
2595    look: &impl PixelLook,
2596) -> (Vec<u8>, Option<Vec<u8>>) {
2597    let background = request.background.map(|background| {
2598        let [margin_x, margin_y] = margin.map(|margin| margin as f32);
2599        let padding = background.padding;
2600        let boxes = line_boxes
2601            .iter()
2602            .map(|&(left, line_width, top)| {
2603                (
2604                    margin_x + left - padding,
2605                    margin_x + left + line_width + padding,
2606                    margin_y + top - padding,
2607                    margin_y + top + request.font_size + padding,
2608                )
2609            })
2610            .collect::<Vec<_>>();
2611        (background.color, boxes)
2612    });
2613    let split = request.split_background && background.is_some();
2614    let mut split_plane = split.then(|| vec![0_u8; coverage.len() * 4]);
2615    let foreground = request.fill.foreground();
2616    let [margin_x, margin_y] = margin.map(|margin| margin as f32);
2617    let mut rgba8 = vec![0_u8; coverage.len() * 4];
2618    // Boxes are in line order, so the window `first..last` only moves down.
2619    let (mut first, mut last) = (0, 0);
2620    for (index, text) in coverage.iter().copied().enumerate() {
2621        let mut pixel = [0_u32; 4];
2622        let x = (index % width as usize) as f32;
2623        let y = (index / width as usize) as f32;
2624        if let Some((color, boxes)) = &background {
2625            if index % width as usize == 0 {
2626                while first < boxes.len() && boxes[first].3 <= y {
2627                    first += 1;
2628                }
2629                last = last.max(first);
2630                while last < boxes.len() && boxes[last].2 < y + 1.0 {
2631                    last += 1;
2632                }
2633            }
2634            let covered = boxes[first..last]
2635                .iter()
2636                .map(|&(left, right, top, bottom)| {
2637                    let across = (right.min(x + 1.0) - left.max(x)).clamp(0.0, 1.0);
2638                    let down = (bottom.min(y + 1.0) - top.max(y)).clamp(0.0, 1.0);
2639                    across * down
2640                })
2641                .fold(0.0_f32, f32::max);
2642            let boxed = premultiplied(*color, (covered * 255.0).round() as u8);
2643            match &mut split_plane {
2644                Some(plane) => {
2645                    for (channel, value) in boxed.iter().enumerate() {
2646                        plane[index * 4 + channel] = (*value).min(255) as u8;
2647                    }
2648                }
2649                None => pixel = boxed,
2650            }
2651        }
2652        // Fade a character's layers together so its strokes never show through its fill.
2653        let fade = look.fade(index);
2654        let boxes = pixel;
2655        if fade.is_some() {
2656            pixel = [0; 4];
2657        }
2658        for (stroke, band) in bands.iter().enumerate().rev() {
2659            if band[index] > 0 {
2660                pixel = over(premultiplied(look.band(stroke, index), band[index]), pixel);
2661            }
2662        }
2663        if text > 0 {
2664            let fill = look.fill(index, [x + 0.5 - margin_x, y + 0.5 - margin_y]);
2665            pixel = over(premultiplied(fill, text), pixel);
2666        }
2667        if let Some(colors) = colors {
2668            let color = &colors[index * 4..][..4];
2669            if color[3] > 0 {
2670                let opacity = u32::from(foreground[3]);
2671                pixel = over(
2672                    std::array::from_fn(|channel| u32::from(color[channel]) * opacity / 255),
2673                    pixel,
2674                );
2675            }
2676        }
2677        if let Some(fade) = fade {
2678            pixel = over(pixel.map(|value| (value * fade + 127) / 255), boxes);
2679        }
2680        for (channel, value) in pixel.iter().enumerate() {
2681            rgba8[index * 4 + channel] = (*value).min(255) as u8;
2682        }
2683    }
2684    (rgba8, split_plane)
2685}
2686
2687/// Dilates coverage by a disc of radius `width` (max over the disc, rim pixels weighted).
2688///
2689/// Only the ink bounds grown by the disc are visited. Each disc row's fully weighted taps form one
2690/// run, computed as a van Herk/Gil-Werman sliding maximum; only the rim is visited tap by tap. The
2691/// result is byte-identical to a tap-by-tap pass.
2692#[allow(
2693    clippy::cast_possible_truncation,
2694    clippy::cast_sign_loss,
2695    clippy::cast_precision_loss,
2696    clippy::cast_possible_wrap
2697)]
2698fn dilate(coverage: &[u8], width: u32, height: u32, radius: f32) -> Vec<u8> {
2699    let (width, height) = (width as usize, height as usize);
2700    let mut band = vec![0_u8; coverage.len()];
2701    let Some(ink) = ink_bounds(coverage, width, height) else {
2702        return band;
2703    };
2704    let disc = Disc::new(radius);
2705    let extent = disc.extent;
2706    let reach = Bounds {
2707        left: ink.left.saturating_sub(extent),
2708        top: ink.top.saturating_sub(extent),
2709        right: (ink.right + extent).min(width),
2710        bottom: (ink.bottom + extent).min(height),
2711    };
2712    // Compute each run half-width once per source row and apply it to every output row using it.
2713    let span = reach.right - reach.left;
2714    let mut window = WindowMax::default();
2715    let mut maxima = vec![0_u8; span];
2716    for (half, offsets) in &disc.runs {
2717        for source_y in ink.top..ink.bottom {
2718            let row = &coverage[source_y * width..(source_y + 1) * width];
2719            window.of(row, reach.left, span, *half, &mut maxima);
2720            for &offset in offsets {
2721                let Some(y) = source_y.checked_add_signed(-offset) else {
2722                    continue;
2723                };
2724                if y < reach.top || y >= reach.bottom {
2725                    continue;
2726                }
2727                let out = &mut band[y * width + reach.left..y * width + reach.right];
2728                for (pixel, highest) in out.iter_mut().zip(&maxima) {
2729                    *pixel = (*pixel).max(*highest);
2730                }
2731            }
2732        }
2733    }
2734    for &(dx, dy, weight) in &disc.rim {
2735        for source_y in ink.top..ink.bottom {
2736            let Some(y) = source_y.checked_add_signed(-dy) else {
2737                continue;
2738            };
2739            if y >= height {
2740                continue;
2741            }
2742            // Column x reads x + dx; keep both in the texture and the source in the ink.
2743            let first = ink.left.max(usize::try_from(dx).unwrap_or(0));
2744            let last = ink
2745                .right
2746                .min(usize::try_from(width as isize + dx.min(0)).unwrap_or(0));
2747            if first >= last {
2748                continue;
2749            }
2750            let source = &coverage[source_y * width + first..source_y * width + last];
2751            let start = y * width + (first as isize - dx) as usize;
2752            let out = &mut band[start..start + source.len()];
2753            for (pixel, value) in out.iter_mut().zip(source) {
2754                *pixel = (*pixel).max((u32::from(*value) * weight / 255) as u8);
2755            }
2756        }
2757    }
2758    band
2759}
2760
2761/// A rectangle of pixels, right and bottom exclusive.
2762#[derive(Copy, Clone, Debug, Eq, PartialEq)]
2763struct Bounds {
2764    left: usize,
2765    top: usize,
2766    right: usize,
2767    bottom: usize,
2768}
2769
2770fn ink_bounds(coverage: &[u8], width: usize, height: usize) -> Option<Bounds> {
2771    let mut bounds: Option<Bounds> = None;
2772    for y in 0..height {
2773        let row = &coverage[y * width..(y + 1) * width];
2774        let Some(left) = row.iter().position(|&value| value > 0) else {
2775            continue;
2776        };
2777        let right = row.iter().rposition(|&value| value > 0).unwrap_or(left) + 1;
2778        bounds = Some(bounds.map_or(
2779            Bounds {
2780                left,
2781                top: y,
2782                right,
2783                bottom: y + 1,
2784            },
2785            |bounds| Bounds {
2786                left: bounds.left.min(left),
2787                top: bounds.top,
2788                right: bounds.right.max(right),
2789                bottom: y + 1,
2790            },
2791        ));
2792    }
2793    bounds
2794}
2795
2796/// Disc taps split into full-weight row runs and partially weighted rim taps.
2797struct Disc {
2798    extent: usize,
2799    /// Run half-width and the row offsets whose full taps are exactly `-half..=half`.
2800    runs: Vec<(usize, Vec<isize>)>,
2801    /// `(dx, dy, weight)` for taps weighted strictly between 0 and 255.
2802    rim: Vec<(isize, isize, u32)>,
2803}
2804
2805impl Disc {
2806    /// A tap's weight is its area within `radius + 0.5` of the center, in 255ths.
2807    #[allow(
2808        clippy::cast_possible_truncation,
2809        clippy::cast_sign_loss,
2810        clippy::cast_precision_loss,
2811        clippy::cast_possible_wrap
2812    )]
2813    fn new(radius: f32) -> Self {
2814        let extent = disc_extent(radius) as isize;
2815        let mut runs: Vec<(usize, Vec<isize>)> = Vec::new();
2816        let mut rim = Vec::new();
2817        for dy in -extent..=extent {
2818            let mut half = None;
2819            for dx in -extent..=extent {
2820                let distance = ((dx * dx + dy * dy) as f32).sqrt();
2821                let weight = ((radius + 0.5 - distance).clamp(0.0, 1.0) * 255.0).round() as u32;
2822                match weight {
2823                    0 => {}
2824                    // Weight falls with distance, so a row's full taps form one centered run.
2825                    255 => half = Some(dx.unsigned_abs()),
2826                    _ => rim.push((dx, dy, weight)),
2827                }
2828            }
2829            if let Some(half) = half {
2830                match runs.iter_mut().find(|(run, _)| *run == half) {
2831                    Some((_, offsets)) => offsets.push(dy),
2832                    None => runs.push((half, vec![dy])),
2833                }
2834            }
2835        }
2836        Self {
2837            extent: extent as usize,
2838            runs,
2839            rim,
2840        }
2841    }
2842}
2843
2844/// Scratch for van Herk/Gil-Werman sliding-window maxima.
2845#[derive(Default)]
2846struct WindowMax {
2847    padded: Vec<u8>,
2848    from_start: Vec<u8>,
2849    to_end: Vec<u8>,
2850}
2851
2852impl WindowMax {
2853    /// `out[i]` = max of `row` over `left + i - half ..= left + i + half`, 0 outside the row.
2854    fn of(&mut self, row: &[u8], left: usize, count: usize, half: usize, out: &mut [u8]) {
2855        let window = 2 * half + 1;
2856        let length = count + 2 * half;
2857        self.padded.clear();
2858        self.padded.resize(length, 0);
2859        // Padded index i is column left - half + i.
2860        let first_column = left.saturating_sub(half);
2861        let last_column = (left + count + half).min(row.len());
2862        if first_column < last_column {
2863            let at = first_column + half - left;
2864            self.padded[at..at + last_column - first_column]
2865                .copy_from_slice(&row[first_column..last_column]);
2866        }
2867        self.from_start.clear();
2868        self.from_start.resize(length, 0);
2869        self.to_end.clear();
2870        self.to_end.resize(length, 0);
2871        for block in (0..length).step_by(window) {
2872            let end = (block + window).min(length);
2873            let mut highest = 0;
2874            for index in block..end {
2875                highest = highest.max(self.padded[index]);
2876                self.from_start[index] = highest;
2877            }
2878            highest = 0;
2879            for index in (block..end).rev() {
2880                highest = highest.max(self.padded[index]);
2881                self.to_end[index] = highest;
2882            }
2883        }
2884        for (index, value) in out[..count].iter_mut().enumerate() {
2885            *value = self.to_end[index].max(self.from_start[index + window - 1]);
2886        }
2887    }
2888}
2889
2890#[cfg(test)]
2891mod tests;
2892
2893#[cfg(test)]
2894#[path = "clamp_tests.rs"]
2895mod clamp_tests;