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