Skip to main content

sim_engine/renderer/
glyph.rs

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