Skip to main content

sim_engine/renderer/
glyph.rs

1use super::{
2    Arc, Color, Error, Image2d, ImageBatch2d, ImageBatchBudget, ImageBatchUploadReport,
3    ImageBudget, ImageError, ImageSprite2d, ImageTexelRect, LogicalScreenPosition, LogicalViewport,
4    LogicalViewportRegion, WgpuRenderer, fmt, image,
5};
6
7#[cfg(test)]
8use super::Vec2;
9
10/// Opaque host-provided glyph identity within one [`GlyphAtlas2d`].
11///
12/// The value may be a font glyph index, a Unicode scalar value, or a host
13/// registry key. Sim;Engine only compares it for exact equality and does not
14/// perform shaping or assign text semantics to it.
15#[derive(Debug, Clone, Copy, PartialEq, Eq, PartialOrd, Ord, Hash)]
16pub struct GlyphId(u32);
17
18impl GlyphId {
19    /// Wraps one host-selected glyph identity.
20    pub const fn new(value: u32) -> Self {
21        Self(value)
22    }
23
24    /// Returns the original host-selected identity.
25    pub const fn value(self) -> u32 {
26        self.0
27    }
28}
29
30/// Maps one glyph identity to a non-empty rectangle in an atlas image.
31#[derive(Debug, Clone, Copy, PartialEq, Eq)]
32pub struct GlyphAtlasEntry {
33    glyph: GlyphId,
34    source: ImageTexelRect,
35}
36
37impl GlyphAtlasEntry {
38    /// Associates a glyph with one physical-texel atlas rectangle.
39    pub const fn new(glyph: GlyphId, source: ImageTexelRect) -> Self {
40        Self { glyph, source }
41    }
42
43    /// Returns the opaque glyph identity.
44    pub const fn glyph(self) -> GlyphId {
45        self.glyph
46    }
47
48    /// Returns the physical atlas source rectangle.
49    pub const fn source(self) -> ImageTexelRect {
50        self.source
51    }
52}
53
54/// Image and metadata limits retained with a [`GlyphAtlas2d`].
55#[derive(Debug, Clone, Copy, PartialEq, Eq)]
56pub struct GlyphAtlasBudget {
57    image: ImageBudget,
58    max_entries: usize,
59    max_metadata_bytes: usize,
60}
61
62impl GlyphAtlasBudget {
63    /// Creates non-zero image, entry-count, and metadata-byte limits.
64    pub fn new(
65        image: ImageBudget,
66        max_entries: usize,
67        max_metadata_bytes: usize,
68    ) -> Result<Self, GlyphError> {
69        if max_entries == 0 || max_metadata_bytes < std::mem::size_of::<GlyphAtlasEntry>() {
70            return Err(GlyphError::InvalidBudget);
71        }
72        Ok(Self {
73            image,
74            max_entries,
75            max_metadata_bytes,
76        })
77    }
78
79    /// Returns the atlas image limits.
80    pub const fn image(self) -> ImageBudget {
81        self.image
82    }
83
84    /// Returns the maximum registered glyph count.
85    pub const fn max_entries(self) -> usize {
86        self.max_entries
87    }
88
89    /// Returns the maximum retained glyph-metadata bytes.
90    pub const fn max_metadata_bytes(self) -> usize {
91        self.max_metadata_bytes
92    }
93}
94
95impl Default for GlyphAtlasBudget {
96    fn default() -> Self {
97        Self {
98            image: ImageBudget::default(),
99            max_entries: 65_536,
100            max_metadata_bytes: 4 * 1024 * 1024,
101        }
102    }
103}
104
105/// Retained glyph-run count and byte limits.
106#[derive(Debug, Clone, Copy, PartialEq, Eq)]
107pub struct GlyphRunBudget {
108    max_glyphs: usize,
109    max_retained_bytes: usize,
110}
111
112impl GlyphRunBudget {
113    /// CPU bytes per glyph capacity slot, including sprite and GPU conversion
114    /// staging. Atlas storage and allocator metadata are excluded.
115    pub const RETAINED_BYTES_PER_GLYPH: usize =
116        std::mem::size_of::<PositionedGlyph2d>() + ImageBatchBudget::RETAINED_BYTES_PER_SPRITE;
117
118    /// Creates non-zero limits for positioned glyphs and recovery metadata.
119    pub fn new(max_glyphs: usize, max_retained_bytes: usize) -> Result<Self, GlyphError> {
120        if max_glyphs == 0 || max_retained_bytes < glyph_retained_bytes(1).unwrap_or(usize::MAX) {
121            return Err(GlyphError::InvalidBudget);
122        }
123        Ok(Self {
124            max_glyphs,
125            max_retained_bytes,
126        })
127    }
128
129    /// Returns the maximum number of submitted positioned glyphs.
130    pub const fn max_glyphs(self) -> usize {
131        self.max_glyphs
132    }
133
134    /// Returns the maximum retained glyph, sprite and conversion-staging bytes.
135    pub const fn max_retained_bytes(self) -> usize {
136        self.max_retained_bytes
137    }
138}
139
140impl Default for GlyphRunBudget {
141    fn default() -> Self {
142        Self {
143            max_glyphs: 100_000,
144            max_retained_bytes: 32 * 1024 * 1024,
145        }
146    }
147}
148
149/// Failure while constructing, updating, or restoring glyph resources.
150#[derive(Debug, Clone, Copy, PartialEq, Eq)]
151pub enum GlyphError {
152    /// Image creation, update, ownership, or capacity validation failed.
153    Image(ImageError),
154    /// A glyph budget must fit at least one entry or positioned glyph.
155    InvalidBudget,
156    /// Atlas or run metadata exceeded its configured entry limit.
157    EntryBudgetExceeded {
158        /// Configured count ceiling.
159        limit: usize,
160        /// Requested entry count.
161        actual: usize,
162    },
163    /// Atlas or run recovery metadata exceeded its configured byte limit.
164    MetadataBudgetExceeded {
165        /// Configured byte ceiling.
166        limit: usize,
167        /// Required retained bytes.
168        actual: usize,
169    },
170    /// Two atlas entries use the same glyph identity.
171    DuplicateGlyph {
172        /// Repeated identity.
173        glyph: GlyphId,
174    },
175    /// Two distinct glyph identities claim overlapping atlas texels.
176    OverlappingGlyph {
177        /// Identity whose rectangle was rejected.
178        glyph: GlyphId,
179        /// Existing identity whose rectangle overlaps it.
180        conflicting_glyph: GlyphId,
181    },
182    /// A positioned run references a glyph absent from its atlas.
183    MissingGlyph {
184        /// Missing identity.
185        glyph: GlyphId,
186        /// Zero-based positioned-glyph index in the submitted run.
187        index: usize,
188    },
189    /// A glyph destination, tint, or atlas rectangle is invalid.
190    InvalidGlyph,
191    /// CPU storage for retained metadata or temporary validation/conversion
192    /// scratch could not be reserved.
193    AllocationFailed {
194        /// Minimum bytes requested by the failed reservation.
195        requested_bytes: usize,
196    },
197}
198
199impl fmt::Display for GlyphError {
200    fn fmt(&self, formatter: &mut fmt::Formatter<'_>) -> fmt::Result {
201        match self {
202            Self::Image(error) => write!(formatter, "glyph image error: {error}"),
203            Self::InvalidBudget => write!(formatter, "glyph budget must fit one entry"),
204            Self::EntryBudgetExceeded { limit, actual } => {
205                write!(formatter, "glyph count {actual} exceeds limit {limit}")
206            }
207            Self::MetadataBudgetExceeded { limit, actual } => write!(
208                formatter,
209                "glyph recovery metadata requires {actual} bytes, over limit {limit}"
210            ),
211            Self::DuplicateGlyph { glyph } => {
212                write!(formatter, "glyph identity {} is duplicated", glyph.value())
213            }
214            Self::OverlappingGlyph {
215                glyph,
216                conflicting_glyph,
217            } => write!(
218                formatter,
219                "glyph identity {} overlaps atlas texels owned by glyph {}",
220                glyph.value(),
221                conflicting_glyph.value()
222            ),
223            Self::MissingGlyph { glyph, index } => write!(
224                formatter,
225                "glyph identity {} at run index {index} is absent from the atlas",
226                glyph.value()
227            ),
228            Self::InvalidGlyph => write!(formatter, "glyph placement or atlas region is invalid"),
229            Self::AllocationFailed { requested_bytes } => write!(
230                formatter,
231                "could not reserve {requested_bytes} bytes for glyph metadata or scratch storage"
232            ),
233        }
234    }
235}
236
237impl Error for GlyphError {}
238
239impl From<ImageError> for GlyphError {
240    fn from(error: ImageError) -> Self {
241        Self::Image(error)
242    }
243}
244
245/// Result of uploading one glyph image into an existing atlas.
246#[derive(Debug, Clone, Copy, PartialEq, Eq)]
247pub struct GlyphUploadReport {
248    uploaded_bytes: usize,
249    inserted_entry: bool,
250}
251
252impl GlyphUploadReport {
253    /// Returns the exact number of RGBA bytes submitted to the GPU queue.
254    pub const fn uploaded_bytes(self) -> usize {
255        self.uploaded_bytes
256    }
257
258    /// Returns whether a new glyph identity was registered.
259    pub const fn inserted_entry(self) -> bool {
260        self.inserted_entry
261    }
262}
263
264/// Renderer-owned sRGB RGBA glyph atlas with exact pixels and sorted metadata.
265///
266/// Sim;Engine does not evict entries implicitly. Hosts can therefore treat a
267/// successful upload as stable until they explicitly replace or restore the
268/// atlas. Straight-alpha pixels follow the same color contract as [`Image2d`].
269pub struct GlyphAtlas2d {
270    pub(super) image: Image2d,
271    entries: Vec<GlyphAtlasEntry>,
272    budget: GlyphAtlasBudget,
273}
274
275impl GlyphAtlas2d {
276    /// Returns atlas dimensions in physical source texels.
277    pub const fn size(&self) -> (u32, u32) {
278        self.image.size()
279    }
280
281    /// Returns registered entries sorted by glyph identity.
282    pub fn entries(&self) -> &[GlyphAtlasEntry] {
283        &self.entries
284    }
285
286    /// Returns one atlas rectangle, or `None` for an unregistered identity.
287    pub fn source_for(&self, glyph: GlyphId) -> Option<ImageTexelRect> {
288        find_entry(&self.entries, glyph).map(GlyphAtlasEntry::source)
289    }
290
291    /// Returns the retained atlas limits.
292    pub const fn budget(&self) -> GlyphAtlasBudget {
293        self.budget
294    }
295
296    /// Returns exact CPU bytes retained for image and glyph recovery.
297    pub fn recovery_memory_bytes(&self) -> usize {
298        self.image.recovery_memory_bytes().saturating_add(
299            self.entries
300                .capacity()
301                .saturating_mul(std::mem::size_of::<GlyphAtlasEntry>()),
302        )
303    }
304
305    /// Returns nominal single-level RGBA8 texel-storage bytes, excluding
306    /// opaque backend alignment, tiling, allocation pages, and metadata.
307    pub fn gpu_allocation_bytes(&self) -> usize {
308        self.image.gpu_allocation_bytes()
309    }
310}
311
312/// One host-shaped glyph quad in local logical-screen coordinates.
313#[derive(Debug, Clone, Copy, PartialEq)]
314pub struct PositionedGlyph2d {
315    glyph: GlyphId,
316    destination: LogicalViewportRegion,
317    tint: Color,
318}
319
320impl PositionedGlyph2d {
321    /// Creates a finite logical-pixel quad with normalized straight-linear tint.
322    pub fn new(
323        glyph: GlyphId,
324        destination: LogicalViewportRegion,
325        tint: Color,
326    ) -> Result<Self, GlyphError> {
327        if !tint.is_normalized() || !logical_region_arithmetic_is_finite(destination) {
328            return Err(GlyphError::InvalidGlyph);
329        }
330        Ok(Self {
331            glyph,
332            destination,
333            tint,
334        })
335    }
336
337    /// Returns the atlas-local glyph identity.
338    pub const fn glyph(self) -> GlyphId {
339        self.glyph
340    }
341
342    /// Returns the exact logical-pixel destination supplied by the host shaper.
343    pub const fn destination(self) -> LogicalViewportRegion {
344        self.destination
345    }
346
347    /// Returns normalized straight-linear tint and opacity.
348    pub const fn tint(self) -> Color {
349        self.tint
350    }
351}
352
353/// Deterministic logical-pixel bounds of a submitted positioned glyph run.
354#[derive(Debug, Clone, Copy, PartialEq)]
355pub struct GlyphRunBounds {
356    region: Option<LogicalViewportRegion>,
357}
358
359impl GlyphRunBounds {
360    /// Returns `None` for an empty run or the exact union of its glyph quads.
361    pub const fn region(self) -> Option<LogicalViewportRegion> {
362        self.region
363    }
364
365    /// Returns whether the submitted run contains no glyph quads.
366    pub const fn is_empty(self) -> bool {
367        self.region.is_none()
368    }
369}
370
371/// Bounded retained glyph-run statistics independent of frame timing.
372#[derive(Debug, Clone, Copy, PartialEq, Eq)]
373pub struct GlyphRunStatistics {
374    submitted_glyphs: usize,
375    rendered_quads: usize,
376    atlas_misses: usize,
377    retained_bytes: usize,
378}
379
380impl GlyphRunStatistics {
381    /// Returns positioned glyphs accepted from the host.
382    pub const fn submitted_glyphs(self) -> usize {
383        self.submitted_glyphs
384    }
385
386    /// Returns retained drawable quads. Successful runs have one per glyph.
387    pub const fn rendered_quads(self) -> usize {
388        self.rendered_quads
389    }
390
391    /// Returns atlas misses. Successful retained runs always report zero.
392    pub const fn atlas_misses(self) -> usize {
393        self.atlas_misses
394    }
395
396    /// Returns retained glyph, sprite and conversion-staging capacity bytes.
397    pub const fn retained_bytes(self) -> usize {
398        self.retained_bytes
399    }
400}
401
402/// Renderer-owned positioned glyph run drawn as at most one instanced atlas batch.
403///
404/// A run references exactly one atlas. Mixed fallback fonts remain explicit:
405/// build one run per atlas and submit them at the same frame order. The host is
406/// responsible for shaping, baseline selection, fallback, and line breaking.
407/// An empty run is valid and emits no draw call.
408pub struct GlyphRun2d {
409    pub(super) batch: ImageBatch2d,
410    glyphs: Vec<PositionedGlyph2d>,
411    bounds: GlyphRunBounds,
412    budget: GlyphRunBudget,
413}
414
415/// Outcome of an atomic capacity-aware glyph-run update.
416#[derive(Debug, Clone, Copy, PartialEq, Eq)]
417pub struct GlyphRunUploadReport {
418    batch: ImageBatchUploadReport,
419    capacity: usize,
420    retained_bytes: usize,
421    peak_retained_bytes: usize,
422}
423
424impl GlyphRunUploadReport {
425    /// Returns the accepted positioned-glyph count.
426    pub const fn glyph_count(self) -> usize {
427        self.batch.sprite_count()
428    }
429    /// Returns glyph/layout capacity reusable without growing CPU arrays.
430    pub const fn capacity(self) -> usize {
431        self.capacity
432    }
433    /// Returns the instance upload and GPU capacity/growth outcome.
434    pub const fn instances(self) -> ImageBatchUploadReport {
435        self.batch
436    }
437    /// Returns all retained CPU glyph, sprite and conversion-staging bytes.
438    pub const fn retained_bytes(self) -> usize {
439        self.retained_bytes
440    }
441    /// Returns the conservative old/new CPU peak, excluding caller and backend storage.
442    pub const fn peak_retained_bytes(self) -> usize {
443        self.peak_retained_bytes
444    }
445}
446
447impl GlyphRun2d {
448    /// Returns the exact host-positioned glyph descriptions.
449    pub fn glyphs(&self) -> &[PositionedGlyph2d] {
450        &self.glyphs
451    }
452
453    /// Returns the retained glyph count.
454    pub fn glyph_count(&self) -> usize {
455        self.glyphs.len()
456    }
457
458    /// Returns CPU capacity reusable without growing glyph or sprite arrays.
459    pub fn capacity(&self) -> usize {
460        self.glyphs.capacity().min(self.batch.capacity())
461    }
462
463    /// Returns deterministic logical-pixel bounds without font interpretation.
464    pub const fn bounds(&self) -> GlyphRunBounds {
465        self.bounds
466    }
467
468    /// Returns creation and restoration limits.
469    pub const fn budget(&self) -> GlyphRunBudget {
470        self.budget
471    }
472
473    /// Returns retained work counters for this run.
474    pub fn statistics(&self) -> GlyphRunStatistics {
475        GlyphRunStatistics {
476            submitted_glyphs: self.glyphs.len(),
477            rendered_quads: self.glyphs.len(),
478            atlas_misses: 0,
479            retained_bytes: self.recovery_memory_bytes(),
480        }
481    }
482
483    /// Returns CPU glyph, sprite and conversion-staging capacity bytes.
484    pub fn recovery_memory_bytes(&self) -> usize {
485        self.glyphs
486            .capacity()
487            .saturating_mul(std::mem::size_of::<PositionedGlyph2d>())
488            .saturating_add(self.batch.recovery_memory_bytes())
489    }
490
491    /// Returns GPU instance-buffer bytes actively addressable by the run.
492    pub fn gpu_allocation_bytes(&self) -> usize {
493        self.batch.gpu_allocation_bytes()
494    }
495}
496
497impl WgpuRenderer {
498    /// Creates a bounded glyph atlas from exact RGBA pixels and initial entries.
499    pub fn create_glyph_atlas(
500        &self,
501        width: u32,
502        height: u32,
503        pixels: Vec<u8>,
504        entries: Vec<GlyphAtlasEntry>,
505        budget: GlyphAtlasBudget,
506    ) -> Result<GlyphAtlas2d, GlyphError> {
507        create_glyph_atlas_resources(
508            &self.device,
509            &self.queue,
510            Arc::clone(&self.renderer_identity),
511            width,
512            height,
513            pixels,
514            entries,
515            budget,
516        )
517    }
518
519    /// Uploads or replaces one glyph rectangle after complete metadata preflight.
520    ///
521    /// Reusing an identity requires the same rectangle. Changing atlas packing
522    /// is an explicit new-atlas operation so existing retained runs cannot
523    /// silently sample unrelated texels.
524    pub fn upload_glyph(
525        &self,
526        atlas: &mut GlyphAtlas2d,
527        entry: GlyphAtlasEntry,
528        pixels: &[u8],
529    ) -> Result<GlyphUploadReport, GlyphError> {
530        self.validate_image(&atlas.image)?;
531        if !entry.source.fits(atlas.image.width(), atlas.image.height()) {
532            return Err(GlyphError::InvalidGlyph);
533        }
534        image::validate_image_region_upload(&atlas.image, entry.source, pixels.len())?;
535        let insertion = validate_glyph_insertion(&atlas.entries, entry)?;
536        if insertion.is_some() {
537            validate_metadata_capacity(atlas.entries.len().saturating_add(1), atlas.budget)?;
538        }
539        let replacement_entries = if let Some(index) = insertion {
540            let new_len = atlas.entries.len() + 1;
541            let requested_bytes = new_len
542                .checked_mul(std::mem::size_of::<GlyphAtlasEntry>())
543                .ok_or(GlyphError::InvalidGlyph)?;
544            let mut replacement = Vec::new();
545            replacement
546                .try_reserve_exact(new_len)
547                .map_err(|_| GlyphError::AllocationFailed { requested_bytes })?;
548            replacement.extend_from_slice(&atlas.entries[..index]);
549            replacement.push(entry);
550            replacement.extend_from_slice(&atlas.entries[index..]);
551            let actual = replacement
552                .capacity()
553                .saturating_mul(std::mem::size_of::<GlyphAtlasEntry>());
554            if actual > atlas.budget.max_metadata_bytes {
555                return Err(GlyphError::MetadataBudgetExceeded {
556                    limit: atlas.budget.max_metadata_bytes,
557                    actual,
558                });
559            }
560            Some(replacement)
561        } else {
562            None
563        };
564        let report = self.update_image_region(&mut atlas.image, entry.source, pixels)?;
565        if let Some(replacement) = replacement_entries {
566            atlas.entries = replacement;
567        }
568        Ok(GlyphUploadReport {
569            uploaded_bytes: report.uploaded_bytes(),
570            inserted_entry: insertion.is_some(),
571        })
572    }
573
574    /// Creates one retained instanced run from host-positioned glyph quads.
575    pub fn create_glyph_run(
576        &self,
577        atlas: &GlyphAtlas2d,
578        glyphs: Vec<PositionedGlyph2d>,
579        budget: GlyphRunBudget,
580    ) -> Result<GlyphRun2d, GlyphError> {
581        self.validate_image(&atlas.image)?;
582        create_glyph_run_resources(
583            &self.device,
584            &self.queue,
585            Arc::clone(&self.renderer_identity),
586            atlas,
587            glyphs,
588            budget,
589        )
590    }
591
592    /// Updates host-shaped layout while reusing CPU and GPU capacity when possible.
593    ///
594    /// Exact unchanged input uploads nothing; an empty slice clears the drawable
595    /// run but retains capacity. The atlas must be the run's original active-device
596    /// atlas. All glyph sources, bounds and budget checks complete before changing
597    /// drawable state. Synchronous rejection preserves the previous revision;
598    /// device failure cannot roll back work already submitted to the queue.
599    pub fn update_glyph_run(
600        &self,
601        atlas: &GlyphAtlas2d,
602        run: &mut GlyphRun2d,
603        glyphs: &[PositionedGlyph2d],
604    ) -> Result<GlyphRunUploadReport, GlyphError> {
605        self.validate_glyph_run(atlas, run)?;
606        update_glyph_run_resources(&self.device, &self.queue, atlas, run, glyphs)
607    }
608
609    /// Restores exact atlas pixels and metadata for this renderer generation.
610    pub fn restore_glyph_atlas(&self, source: &GlyphAtlas2d) -> Result<GlyphAtlas2d, GlyphError> {
611        image::validate_image_shape(
612            source.image.width(),
613            source.image.height(),
614            source.image.pixels().len(),
615            source.budget.image,
616            self.device.limits().max_texture_dimension_2d,
617        )?;
618        let mut entries = Vec::new();
619        entries
620            .try_reserve_exact(source.entries.len())
621            .map_err(|_| GlyphError::AllocationFailed {
622                requested_bytes: std::mem::size_of_val(source.entries.as_slice()),
623            })?;
624        entries.extend_from_slice(&source.entries);
625        validate_atlas_entries(
626            &mut entries,
627            source.image.width(),
628            source.image.height(),
629            source.budget,
630        )?;
631        entries = compact_glyph_vec(entries, source.budget.max_metadata_bytes)?;
632        let actual = entries
633            .capacity()
634            .saturating_mul(std::mem::size_of::<GlyphAtlasEntry>());
635        if actual > source.budget.max_metadata_bytes {
636            return Err(GlyphError::MetadataBudgetExceeded {
637                limit: source.budget.max_metadata_bytes,
638                actual,
639            });
640        }
641        let image = self.restore_image(&source.image)?;
642        Ok(GlyphAtlas2d {
643            image,
644            entries,
645            budget: source.budget,
646        })
647    }
648
649    /// Restores a run against the restored copy of its original atlas.
650    pub fn restore_glyph_run(
651        &self,
652        atlas: &GlyphAtlas2d,
653        source: &GlyphRun2d,
654    ) -> Result<GlyphRun2d, GlyphError> {
655        self.validate_image(&atlas.image)?;
656        if !Arc::ptr_eq(
657            &atlas.image.recovery_identity,
658            &source.batch.image_recovery_identity,
659        ) {
660            return Err(ImageError::RecoverySourceMismatch.into());
661        }
662        validate_glyph_run_sources(&atlas.entries, &source.glyphs, source.batch.sprites())?;
663        validate_glyph_run_budget(source.glyphs.len(), source.budget)?;
664        validate_glyph_membership(&atlas.entries, &source.glyphs)?;
665        measure_glyphs(&source.glyphs)?;
666        let batch_budget =
667            ImageBatchBudget::new(source.budget.max_glyphs, source.budget.max_retained_bytes)?;
668        image::preflight_image_batch_capacity(&self.device, source.glyphs.len(), batch_budget)?;
669        let retained_bytes = source
670            .glyphs
671            .len()
672            .checked_mul(std::mem::size_of::<PositionedGlyph2d>())
673            .ok_or(GlyphError::InvalidGlyph)?;
674        let mut glyphs = Vec::new();
675        glyphs.try_reserve_exact(source.glyphs.len()).map_err(|_| {
676            GlyphError::AllocationFailed {
677                requested_bytes: retained_bytes,
678            }
679        })?;
680        glyphs.extend_from_slice(&source.glyphs);
681        self.create_glyph_run(atlas, glyphs, source.budget)
682    }
683
684    pub(super) fn validate_glyph_run(
685        &self,
686        atlas: &GlyphAtlas2d,
687        run: &GlyphRun2d,
688    ) -> Result<(), GlyphError> {
689        self.validate_image_batch(&atlas.image, &run.batch)?;
690        Ok(())
691    }
692}
693
694#[allow(clippy::too_many_arguments)]
695pub(super) fn create_glyph_atlas_resources(
696    device: &wgpu::Device,
697    queue: &wgpu::Queue,
698    renderer_identity: Arc<()>,
699    width: u32,
700    height: u32,
701    pixels: Vec<u8>,
702    mut entries: Vec<GlyphAtlasEntry>,
703    budget: GlyphAtlasBudget,
704) -> Result<GlyphAtlas2d, GlyphError> {
705    image::validate_image_shape(
706        width,
707        height,
708        pixels.len(),
709        budget.image,
710        device.limits().max_texture_dimension_2d,
711    )?;
712    validate_atlas_entries(&mut entries, width, height, budget)?;
713    entries = compact_glyph_vec(entries, budget.max_metadata_bytes)?;
714    let actual_metadata_bytes = entries
715        .capacity()
716        .saturating_mul(std::mem::size_of::<GlyphAtlasEntry>());
717    if actual_metadata_bytes > budget.max_metadata_bytes {
718        return Err(GlyphError::MetadataBudgetExceeded {
719            limit: budget.max_metadata_bytes,
720            actual: actual_metadata_bytes,
721        });
722    }
723    let image = image::create_image_resources(
724        device,
725        queue,
726        renderer_identity,
727        width,
728        height,
729        pixels,
730        budget.image,
731    )?;
732    Ok(GlyphAtlas2d {
733        image,
734        entries,
735        budget,
736    })
737}
738
739pub(super) fn create_glyph_run_resources(
740    device: &wgpu::Device,
741    queue: &wgpu::Queue,
742    renderer_identity: Arc<()>,
743    atlas: &GlyphAtlas2d,
744    glyphs: Vec<PositionedGlyph2d>,
745    budget: GlyphRunBudget,
746) -> Result<GlyphRun2d, GlyphError> {
747    validate_glyph_run_budget(glyphs.len(), budget)?;
748    validate_glyph_membership(&atlas.entries, &glyphs)?;
749    let bounds = measure_glyphs(&glyphs)?;
750    let batch_budget = ImageBatchBudget::new(budget.max_glyphs, budget.max_retained_bytes)?;
751    image::preflight_image_batch_capacity(device, glyphs.len(), batch_budget)?;
752    let glyph_byte_limit = budget
753        .max_retained_bytes
754        .saturating_sub(image::batch_retained_bytes(glyphs.len().max(1)));
755    let glyphs = compact_glyph_vec(glyphs, glyph_byte_limit)?;
756    let sprites = resolve_glyph_sprites(&atlas.entries, &glyphs)?;
757    let actual_retained_bytes = glyphs
758        .capacity()
759        .saturating_mul(std::mem::size_of::<PositionedGlyph2d>())
760        .saturating_add(
761            sprites
762                .capacity()
763                .saturating_mul(std::mem::size_of::<ImageSprite2d>()),
764        );
765    if actual_retained_bytes > budget.max_retained_bytes {
766        return Err(GlyphError::MetadataBudgetExceeded {
767            limit: budget.max_retained_bytes,
768            actual: actual_retained_bytes,
769        });
770    }
771    let batch_budget = ImageBatchBudget::new(
772        budget.max_glyphs,
773        budget.max_retained_bytes.saturating_sub(
774            glyphs
775                .capacity()
776                .saturating_mul(std::mem::size_of::<PositionedGlyph2d>()),
777        ),
778    )?;
779    let batch = image::create_image_batch_resources(
780        device,
781        queue,
782        renderer_identity,
783        &atlas.image,
784        sprites,
785        batch_budget,
786    )?;
787    Ok(GlyphRun2d {
788        batch,
789        glyphs,
790        bounds,
791        budget,
792    })
793}
794
795pub(super) fn update_glyph_run_resources(
796    device: &wgpu::Device,
797    queue: &wgpu::Queue,
798    atlas: &GlyphAtlas2d,
799    run: &mut GlyphRun2d,
800    glyphs: &[PositionedGlyph2d],
801) -> Result<GlyphRunUploadReport, GlyphError> {
802    validate_glyph_run_budget(glyphs.len(), run.budget)?;
803    image::preflight_image_batch_capacity(
804        device,
805        glyphs.len(),
806        ImageBatchBudget::new(run.budget.max_glyphs, run.budget.max_retained_bytes)?,
807    )?;
808    validate_glyph_membership(&atlas.entries, glyphs)?;
809    if glyphs.iter().any(|glyph| !glyph.tint.is_normalized()) {
810        return Err(GlyphError::InvalidGlyph);
811    }
812    let bounds = measure_glyphs(glyphs)?;
813    let old_glyph_bytes = run
814        .glyphs
815        .capacity()
816        .saturating_mul(std::mem::size_of::<PositionedGlyph2d>());
817    let mut replacement = if glyphs.len() > run.glyphs.capacity() {
818        let mut values = Vec::new();
819        values
820            .try_reserve_exact(glyphs.len())
821            .map_err(|_| GlyphError::AllocationFailed {
822                requested_bytes: std::mem::size_of_val(glyphs),
823            })?;
824        Some(values)
825    } else {
826        None
827    };
828    let glyph_capacity = replacement
829        .as_ref()
830        .map_or(run.glyphs.capacity(), Vec::capacity);
831    let glyph_bytes = glyph_capacity.saturating_mul(std::mem::size_of::<PositionedGlyph2d>());
832    let batch_budget = ImageBatchBudget::new(
833        run.budget.max_glyphs,
834        run.budget.max_retained_bytes.saturating_sub(glyph_bytes),
835    )?;
836    // Membership, tint and destination validation above prove one sprite per
837    // glyph. The common update also checks that exact count before publication.
838    let sprites = glyphs.iter().filter_map(|glyph| {
839        let source = find_entry(&atlas.entries, glyph.glyph)?.source;
840        ImageSprite2d::new(source, glyph.destination, glyph.tint).ok()
841    });
842    let batch = image::update_image_batch_resources(
843        device,
844        queue,
845        &atlas.image,
846        &mut run.batch,
847        sprites,
848        glyphs.len(),
849        batch_budget,
850    )?;
851    let peak_retained_bytes = batch
852        .peak_retained_bytes()
853        .saturating_add(old_glyph_bytes)
854        .saturating_add(if replacement.is_some() {
855            glyph_bytes
856        } else {
857            0
858        });
859    if let Some(values) = replacement.take() {
860        run.glyphs = values;
861    }
862    run.glyphs.clear();
863    run.glyphs.extend_from_slice(glyphs);
864    run.bounds = bounds;
865    Ok(GlyphRunUploadReport {
866        batch,
867        capacity: run.capacity(),
868        retained_bytes: run.recovery_memory_bytes(),
869        peak_retained_bytes,
870    })
871}
872
873fn compact_glyph_vec<T: Copy>(values: Vec<T>, maximum_bytes: usize) -> Result<Vec<T>, GlyphError> {
874    if values.capacity().saturating_mul(std::mem::size_of::<T>()) <= maximum_bytes {
875        return Ok(values);
876    }
877    let requested_bytes = values
878        .len()
879        .checked_mul(std::mem::size_of::<T>())
880        .ok_or(GlyphError::InvalidGlyph)?;
881    let mut compact = Vec::new();
882    compact
883        .try_reserve_exact(values.len())
884        .map_err(|_| GlyphError::AllocationFailed { requested_bytes })?;
885    compact.extend_from_slice(&values);
886    Ok(compact)
887}
888
889fn validate_atlas_entries(
890    entries: &mut [GlyphAtlasEntry],
891    width: u32,
892    height: u32,
893    budget: GlyphAtlasBudget,
894) -> Result<(), GlyphError> {
895    validate_metadata_capacity(entries.len(), budget)?;
896    entries.sort_unstable_by_key(|entry| entry.glyph);
897    for (index, entry) in entries.iter().enumerate() {
898        if !entry.source.fits(width, height) {
899            return Err(GlyphError::InvalidGlyph);
900        }
901        if index > 0 && entries[index - 1].glyph == entry.glyph {
902            return Err(GlyphError::DuplicateGlyph { glyph: entry.glyph });
903        }
904    }
905    validate_non_overlapping_glyph_entries(entries)
906}
907
908#[derive(Clone, Copy)]
909struct GlyphSweepEvent {
910    x: u32,
911    starts: bool,
912    entry_index: usize,
913    minimum_y: u32,
914    maximum_y: u32,
915}
916
917fn validate_non_overlapping_glyph_entries(entries: &[GlyphAtlasEntry]) -> Result<(), GlyphError> {
918    if entries.len() < 2 {
919        return Ok(());
920    }
921    let endpoint_count = entries
922        .len()
923        .checked_mul(2)
924        .ok_or(GlyphError::InvalidGlyph)?;
925    let mut events = Vec::new();
926    events
927        .try_reserve_exact(endpoint_count)
928        .map_err(|_| GlyphError::AllocationFailed {
929            requested_bytes: endpoint_count.saturating_mul(std::mem::size_of::<GlyphSweepEvent>()),
930        })?;
931    let mut vertical_coordinates = Vec::new();
932    vertical_coordinates
933        .try_reserve_exact(endpoint_count)
934        .map_err(|_| GlyphError::AllocationFailed {
935            requested_bytes: endpoint_count.saturating_mul(std::mem::size_of::<u32>()),
936        })?;
937    for (entry_index, entry) in entries.iter().copied().enumerate() {
938        let source = entry.source;
939        let maximum_x = source
940            .x()
941            .checked_add(source.width())
942            .ok_or(GlyphError::InvalidGlyph)?;
943        let maximum_y = source
944            .y()
945            .checked_add(source.height())
946            .ok_or(GlyphError::InvalidGlyph)?;
947        events.push(GlyphSweepEvent {
948            x: source.x(),
949            starts: true,
950            entry_index,
951            minimum_y: source.y(),
952            maximum_y,
953        });
954        events.push(GlyphSweepEvent {
955            x: maximum_x,
956            starts: false,
957            entry_index,
958            minimum_y: source.y(),
959            maximum_y,
960        });
961        vertical_coordinates.push(source.y());
962        vertical_coordinates.push(maximum_y);
963    }
964    // End events precede start events at the same x so edge-touching atlas
965    // rectangles remain valid.
966    events.sort_unstable_by_key(|event| (event.x, event.starts));
967    vertical_coordinates.sort_unstable();
968    vertical_coordinates.dedup();
969    let interval_count = vertical_coordinates.len().saturating_sub(1);
970    let tree_len = interval_count
971        .checked_mul(4)
972        .and_then(|value| value.checked_add(4))
973        .ok_or(GlyphError::InvalidGlyph)?;
974    let mut maximum_coverage = Vec::new();
975    maximum_coverage
976        .try_reserve_exact(tree_len)
977        .map_err(|_| GlyphError::AllocationFailed {
978            requested_bytes: tree_len.saturating_mul(std::mem::size_of::<i32>()),
979        })?;
980    maximum_coverage.resize(tree_len, 0_i32);
981    let mut lazy_coverage = Vec::new();
982    lazy_coverage
983        .try_reserve_exact(tree_len)
984        .map_err(|_| GlyphError::AllocationFailed {
985            requested_bytes: tree_len.saturating_mul(std::mem::size_of::<i32>()),
986        })?;
987    lazy_coverage.resize(tree_len, 0_i32);
988    let mut active = Vec::new();
989    active
990        .try_reserve_exact(entries.len())
991        .map_err(|_| GlyphError::AllocationFailed {
992            requested_bytes: entries.len().saturating_mul(std::mem::size_of::<bool>()),
993        })?;
994    active.resize(entries.len(), false);
995
996    for event in events {
997        let minimum = vertical_coordinates
998            .binary_search(&event.minimum_y)
999            .expect("glyph sweep endpoints came from the coordinate set");
1000        let maximum = vertical_coordinates
1001            .binary_search(&event.maximum_y)
1002            .expect("glyph sweep endpoints came from the coordinate set");
1003        if event.starts {
1004            if glyph_coverage_max(
1005                &maximum_coverage,
1006                &lazy_coverage,
1007                1,
1008                0,
1009                interval_count,
1010                minimum,
1011                maximum,
1012            ) > 0
1013            {
1014                let entry = entries[event.entry_index];
1015                let conflict = active
1016                    .iter()
1017                    .enumerate()
1018                    .find(|(index, active)| {
1019                        **active && glyph_rectangles_overlap(entries[*index].source, entry.source)
1020                    })
1021                    .map(|(index, _)| entries[index].glyph)
1022                    .expect("positive sweep coverage has an active owning glyph");
1023                return Err(GlyphError::OverlappingGlyph {
1024                    glyph: entry.glyph,
1025                    conflicting_glyph: conflict,
1026                });
1027            }
1028            glyph_coverage_add(
1029                &mut maximum_coverage,
1030                &mut lazy_coverage,
1031                1,
1032                0,
1033                interval_count,
1034                minimum,
1035                maximum,
1036                1,
1037            );
1038            active[event.entry_index] = true;
1039        } else {
1040            glyph_coverage_add(
1041                &mut maximum_coverage,
1042                &mut lazy_coverage,
1043                1,
1044                0,
1045                interval_count,
1046                minimum,
1047                maximum,
1048                -1,
1049            );
1050            active[event.entry_index] = false;
1051        }
1052    }
1053    Ok(())
1054}
1055
1056#[allow(clippy::too_many_arguments)]
1057fn glyph_coverage_add(
1058    maximum_coverage: &mut [i32],
1059    lazy_coverage: &mut [i32],
1060    node: usize,
1061    left: usize,
1062    right: usize,
1063    query_left: usize,
1064    query_right: usize,
1065    amount: i32,
1066) {
1067    if query_left <= left && right <= query_right {
1068        maximum_coverage[node] += amount;
1069        lazy_coverage[node] += amount;
1070        return;
1071    }
1072    let middle = left + (right - left) / 2;
1073    if query_left < middle {
1074        glyph_coverage_add(
1075            maximum_coverage,
1076            lazy_coverage,
1077            node * 2,
1078            left,
1079            middle,
1080            query_left,
1081            query_right,
1082            amount,
1083        );
1084    }
1085    if query_right > middle {
1086        glyph_coverage_add(
1087            maximum_coverage,
1088            lazy_coverage,
1089            node * 2 + 1,
1090            middle,
1091            right,
1092            query_left,
1093            query_right,
1094            amount,
1095        );
1096    }
1097    maximum_coverage[node] =
1098        lazy_coverage[node] + maximum_coverage[node * 2].max(maximum_coverage[node * 2 + 1]);
1099}
1100
1101#[allow(clippy::too_many_arguments)]
1102fn glyph_coverage_max(
1103    maximum_coverage: &[i32],
1104    lazy_coverage: &[i32],
1105    node: usize,
1106    left: usize,
1107    right: usize,
1108    query_left: usize,
1109    query_right: usize,
1110) -> i32 {
1111    if query_left <= left && right <= query_right {
1112        return maximum_coverage[node];
1113    }
1114    let middle = left + (right - left) / 2;
1115    let mut maximum = 0;
1116    if query_left < middle {
1117        maximum = maximum.max(glyph_coverage_max(
1118            maximum_coverage,
1119            lazy_coverage,
1120            node * 2,
1121            left,
1122            middle,
1123            query_left,
1124            query_right,
1125        ));
1126    }
1127    if query_right > middle {
1128        maximum = maximum.max(glyph_coverage_max(
1129            maximum_coverage,
1130            lazy_coverage,
1131            node * 2 + 1,
1132            middle,
1133            right,
1134            query_left,
1135            query_right,
1136        ));
1137    }
1138    lazy_coverage[node] + maximum
1139}
1140
1141fn validate_glyph_insertion(
1142    entries: &[GlyphAtlasEntry],
1143    entry: GlyphAtlasEntry,
1144) -> Result<Option<usize>, GlyphError> {
1145    match entries.binary_search_by_key(&entry.glyph, |candidate| candidate.glyph) {
1146        Ok(index) => {
1147            if entries[index].source != entry.source {
1148                return Err(GlyphError::DuplicateGlyph { glyph: entry.glyph });
1149            }
1150            Ok(None)
1151        }
1152        Err(index) => {
1153            if let Some(conflict) = entries
1154                .iter()
1155                .find(|candidate| glyph_rectangles_overlap(candidate.source, entry.source))
1156            {
1157                return Err(GlyphError::OverlappingGlyph {
1158                    glyph: entry.glyph,
1159                    conflicting_glyph: conflict.glyph,
1160                });
1161            }
1162            Ok(Some(index))
1163        }
1164    }
1165}
1166
1167fn glyph_rectangles_overlap(left: ImageTexelRect, right: ImageTexelRect) -> bool {
1168    let left_max_x = u64::from(left.x()) + u64::from(left.width());
1169    let left_max_y = u64::from(left.y()) + u64::from(left.height());
1170    let right_max_x = u64::from(right.x()) + u64::from(right.width());
1171    let right_max_y = u64::from(right.y()) + u64::from(right.height());
1172    u64::from(left.x()) < right_max_x
1173        && u64::from(right.x()) < left_max_x
1174        && u64::from(left.y()) < right_max_y
1175        && u64::from(right.y()) < left_max_y
1176}
1177
1178fn validate_metadata_capacity(
1179    entry_count: usize,
1180    budget: GlyphAtlasBudget,
1181) -> Result<(), GlyphError> {
1182    if entry_count > budget.max_entries {
1183        return Err(GlyphError::EntryBudgetExceeded {
1184            limit: budget.max_entries,
1185            actual: entry_count,
1186        });
1187    }
1188    let bytes = entry_count
1189        .checked_mul(std::mem::size_of::<GlyphAtlasEntry>())
1190        .ok_or(GlyphError::InvalidGlyph)?;
1191    if bytes > budget.max_metadata_bytes {
1192        return Err(GlyphError::MetadataBudgetExceeded {
1193            limit: budget.max_metadata_bytes,
1194            actual: bytes,
1195        });
1196    }
1197    Ok(())
1198}
1199
1200pub(super) fn validate_glyph_run_budget(
1201    glyph_count: usize,
1202    budget: GlyphRunBudget,
1203) -> Result<(), GlyphError> {
1204    if glyph_count > budget.max_glyphs {
1205        return Err(GlyphError::EntryBudgetExceeded {
1206            limit: budget.max_glyphs,
1207            actual: glyph_count,
1208        });
1209    }
1210    let retained_bytes = glyph_retained_bytes(glyph_count).ok_or(GlyphError::InvalidGlyph)?;
1211    if retained_bytes > budget.max_retained_bytes {
1212        return Err(GlyphError::MetadataBudgetExceeded {
1213            limit: budget.max_retained_bytes,
1214            actual: retained_bytes,
1215        });
1216    }
1217    Ok(())
1218}
1219
1220fn glyph_retained_bytes(glyph_count: usize) -> Option<usize> {
1221    glyph_count.checked_mul(GlyphRunBudget::RETAINED_BYTES_PER_GLYPH)
1222}
1223
1224fn find_entry(entries: &[GlyphAtlasEntry], glyph: GlyphId) -> Option<GlyphAtlasEntry> {
1225    entries
1226        .binary_search_by_key(&glyph, |entry| entry.glyph)
1227        .ok()
1228        .map(|index| entries[index])
1229}
1230
1231fn resolve_glyph_sprites(
1232    entries: &[GlyphAtlasEntry],
1233    glyphs: &[PositionedGlyph2d],
1234) -> Result<Vec<ImageSprite2d>, GlyphError> {
1235    validate_glyph_membership(entries, glyphs)?;
1236    let mut sprites = Vec::new();
1237    sprites
1238        .try_reserve_exact(glyphs.len())
1239        .map_err(|_| GlyphError::AllocationFailed {
1240            requested_bytes: glyphs
1241                .len()
1242                .saturating_mul(std::mem::size_of::<ImageSprite2d>()),
1243        })?;
1244    for (index, glyph) in glyphs.iter().copied().enumerate() {
1245        let source = find_entry(entries, glyph.glyph)
1246            .map(GlyphAtlasEntry::source)
1247            // The complete lookup scan above makes this branch defensive.
1248            .ok_or(GlyphError::MissingGlyph {
1249                glyph: glyph.glyph,
1250                index,
1251            })?;
1252        sprites.push(ImageSprite2d::new(source, glyph.destination, glyph.tint)?);
1253    }
1254    Ok(sprites)
1255}
1256
1257fn validate_glyph_membership(
1258    entries: &[GlyphAtlasEntry],
1259    glyphs: &[PositionedGlyph2d],
1260) -> Result<(), GlyphError> {
1261    if let Some((index, glyph)) = glyphs
1262        .iter()
1263        .enumerate()
1264        .find(|(_, glyph)| find_entry(entries, glyph.glyph).is_none())
1265    {
1266        return Err(GlyphError::MissingGlyph {
1267            glyph: glyph.glyph,
1268            index,
1269        });
1270    }
1271    Ok(())
1272}
1273
1274fn validate_glyph_run_sources(
1275    entries: &[GlyphAtlasEntry],
1276    glyphs: &[PositionedGlyph2d],
1277    sprites: &[ImageSprite2d],
1278) -> Result<(), GlyphError> {
1279    if glyphs.len() != sprites.len()
1280        || glyphs.iter().zip(sprites).any(|(glyph, sprite)| {
1281            find_entry(entries, glyph.glyph).map(GlyphAtlasEntry::source) != Some(sprite.source())
1282        })
1283    {
1284        return Err(ImageError::RecoverySourceMismatch.into());
1285    }
1286    Ok(())
1287}
1288
1289fn measure_glyphs(glyphs: &[PositionedGlyph2d]) -> Result<GlyphRunBounds, GlyphError> {
1290    if glyphs
1291        .iter()
1292        .any(|glyph| !image::logical_image_region_is_portable(glyph.destination))
1293    {
1294        return Err(GlyphError::InvalidGlyph);
1295    }
1296    let Some(first) = glyphs.first().copied() else {
1297        return Ok(GlyphRunBounds { region: None });
1298    };
1299    let first_origin = first.destination.origin().to_vec2();
1300    let first_size = first.destination.viewport().size();
1301    let mut minimum = first_origin;
1302    let mut maximum = first_origin + first_size;
1303    for glyph in &glyphs[1..] {
1304        if !logical_region_arithmetic_is_finite(glyph.destination) {
1305            return Err(GlyphError::InvalidGlyph);
1306        }
1307        let origin = glyph.destination.origin().to_vec2();
1308        let end = origin + glyph.destination.viewport().size();
1309        minimum.x = minimum.x.min(origin.x);
1310        minimum.y = minimum.y.min(origin.y);
1311        maximum.x = maximum.x.max(end.x);
1312        maximum.y = maximum.y.max(end.y);
1313    }
1314    if !minimum.is_finite() || !maximum.is_finite() {
1315        return Err(GlyphError::InvalidGlyph);
1316    }
1317    let viewport = LogicalViewport::new(maximum.x - minimum.x, maximum.y - minimum.y)
1318        .map_err(|_| GlyphError::InvalidGlyph)?;
1319    let region = LogicalViewportRegion::new(LogicalScreenPosition::from_vec2(minimum), viewport)
1320        .map_err(|_| GlyphError::InvalidGlyph)?;
1321    Ok(GlyphRunBounds {
1322        region: Some(region),
1323    })
1324}
1325
1326fn logical_region_arithmetic_is_finite(region: LogicalViewportRegion) -> bool {
1327    let origin = region.origin().to_vec2();
1328    let end = origin + region.viewport().size();
1329    origin.is_finite() && end.is_finite()
1330}
1331
1332#[cfg(test)]
1333mod tests {
1334    use super::*;
1335
1336    fn rectangle(x: u32) -> ImageTexelRect {
1337        ImageTexelRect::new(x, 0, 1, 1).unwrap()
1338    }
1339
1340    fn positioned(glyph: u32, x: f32) -> PositionedGlyph2d {
1341        PositionedGlyph2d::new(
1342            GlyphId::new(glyph),
1343            LogicalViewportRegion::new(
1344                LogicalScreenPosition::new(x, 2.0),
1345                LogicalViewport::new(4.0, 6.0).unwrap(),
1346            )
1347            .unwrap(),
1348            Color::WHITE,
1349        )
1350        .unwrap()
1351    }
1352
1353    #[test]
1354    fn atlas_entries_sort_and_reject_duplicate_or_out_of_bounds_glyphs() {
1355        let budget = GlyphAtlasBudget::default();
1356        let mut entries = vec![
1357            GlyphAtlasEntry::new(GlyphId::new(2), rectangle(1)),
1358            GlyphAtlasEntry::new(GlyphId::new(1), rectangle(0)),
1359        ];
1360        assert_eq!(validate_atlas_entries(&mut entries, 2, 1, budget), Ok(()));
1361        assert_eq!(entries[0].glyph(), GlyphId::new(1));
1362
1363        let mut duplicate = vec![
1364            GlyphAtlasEntry::new(GlyphId::new(7), rectangle(0)),
1365            GlyphAtlasEntry::new(GlyphId::new(7), rectangle(1)),
1366        ];
1367        assert_eq!(
1368            validate_atlas_entries(&mut duplicate, 2, 1, budget),
1369            Err(GlyphError::DuplicateGlyph {
1370                glyph: GlyphId::new(7)
1371            })
1372        );
1373
1374        let mut outside = vec![GlyphAtlasEntry::new(GlyphId::new(9), rectangle(2))];
1375        assert_eq!(
1376            validate_atlas_entries(&mut outside, 2, 1, budget),
1377            Err(GlyphError::InvalidGlyph)
1378        );
1379
1380        let mut overlapping = vec![
1381            GlyphAtlasEntry::new(GlyphId::new(10), ImageTexelRect::new(0, 0, 2, 2).unwrap()),
1382            GlyphAtlasEntry::new(GlyphId::new(11), ImageTexelRect::new(1, 1, 2, 2).unwrap()),
1383        ];
1384        assert_eq!(
1385            validate_atlas_entries(&mut overlapping, 4, 4, budget),
1386            Err(GlyphError::OverlappingGlyph {
1387                glyph: GlyphId::new(11),
1388                conflicting_glyph: GlyphId::new(10),
1389            })
1390        );
1391    }
1392
1393    #[test]
1394    fn incremental_glyph_overlap_is_rejected_before_metadata_or_pixel_update() {
1395        let entries = [GlyphAtlasEntry::new(
1396            GlyphId::new(1),
1397            ImageTexelRect::new(0, 0, 4, 4).unwrap(),
1398        )];
1399        let overlapping =
1400            GlyphAtlasEntry::new(GlyphId::new(2), ImageTexelRect::new(3, 0, 4, 4).unwrap());
1401        assert_eq!(
1402            validate_glyph_insertion(&entries, overlapping),
1403            Err(GlyphError::OverlappingGlyph {
1404                glyph: GlyphId::new(2),
1405                conflicting_glyph: GlyphId::new(1),
1406            })
1407        );
1408        assert_eq!(entries.len(), 1);
1409
1410        let adjacent =
1411            GlyphAtlasEntry::new(GlyphId::new(2), ImageTexelRect::new(4, 0, 4, 4).unwrap());
1412        assert_eq!(validate_glyph_insertion(&entries, adjacent), Ok(Some(1)));
1413
1414        let below = GlyphAtlasEntry::new(GlyphId::new(2), ImageTexelRect::new(0, 8, 4, 4).unwrap());
1415        assert_eq!(validate_glyph_insertion(&entries, below), Ok(Some(1)));
1416
1417        let entries_below = [GlyphAtlasEntry::new(
1418            GlyphId::new(1),
1419            ImageTexelRect::new(0, 8, 4, 4).unwrap(),
1420        )];
1421        let above = GlyphAtlasEntry::new(GlyphId::new(2), ImageTexelRect::new(0, 0, 4, 4).unwrap());
1422        assert_eq!(validate_glyph_insertion(&entries_below, above), Ok(Some(1)));
1423    }
1424
1425    #[test]
1426    fn default_maximum_non_overlapping_atlas_validation_is_subquadratic() {
1427        let mut entries = Vec::with_capacity(65_536);
1428        for glyph in 0..65_536_u32 {
1429            entries.push(GlyphAtlasEntry::new(
1430                GlyphId::new(glyph),
1431                ImageTexelRect::new(glyph % 256, glyph / 256, 1, 1).unwrap(),
1432            ));
1433        }
1434        assert_eq!(
1435            validate_atlas_entries(&mut entries, 256, 256, GlyphAtlasBudget::default()),
1436            Ok(())
1437        );
1438    }
1439
1440    #[test]
1441    fn positioned_run_resolves_opaque_scientific_glyphs_and_measures_bounds() {
1442        let entries = [
1443            GlyphAtlasEntry::new(GlyphId::new('Δ' as u32), rectangle(1)),
1444            GlyphAtlasEntry::new(GlyphId::new('μ' as u32), rectangle(0)),
1445            GlyphAtlasEntry::new(GlyphId::new('∫' as u32), rectangle(2)),
1446        ];
1447        let glyphs = [
1448            positioned('μ' as u32, 1.0),
1449            positioned('Δ' as u32, 5.0),
1450            positioned('∫' as u32, 9.0),
1451        ];
1452        assert_eq!(resolve_glyph_sprites(&entries, &glyphs).unwrap().len(), 3);
1453        let bounds = measure_glyphs(&glyphs).unwrap().region().unwrap();
1454        assert_eq!(bounds.origin(), LogicalScreenPosition::new(1.0, 2.0));
1455        assert_eq!(bounds.viewport().size(), Vec2::new(12.0, 6.0));
1456
1457        let missing = [positioned('Σ' as u32, 1.0)];
1458        assert_eq!(
1459            resolve_glyph_sprites(&entries, &missing),
1460            Err(GlyphError::MissingGlyph {
1461                glyph: GlyphId::new('Σ' as u32),
1462                index: 0,
1463            })
1464        );
1465    }
1466
1467    #[test]
1468    fn glyph_run_recovery_rejects_forked_atlas_mapping() {
1469        let glyph = positioned(42, 1.0);
1470        let left = rectangle(0);
1471        let right = rectangle(1);
1472        let source_entries = [GlyphAtlasEntry::new(GlyphId::new(42), left)];
1473        let forked_entries = [GlyphAtlasEntry::new(GlyphId::new(42), right)];
1474        let source_sprites = [ImageSprite2d::new(left, glyph.destination(), glyph.tint()).unwrap()];
1475
1476        assert_eq!(
1477            validate_glyph_run_sources(&source_entries, &[glyph], &source_sprites),
1478            Ok(())
1479        );
1480        assert_eq!(
1481            validate_glyph_run_sources(&forked_entries, &[glyph], &source_sprites),
1482            Err(GlyphError::Image(ImageError::RecoverySourceMismatch))
1483        );
1484    }
1485}