Skip to main content

textflow/
layout.rs

1use crate::bidi::{BidiError, BidiRun, BidiText, Direction};
2use crate::shaping::{
3    CaretStop, FlowPoint, FontAccessError, FontFeature, FontId, GlyphId, LineEdges, PositionError,
4    PositionedGlyph, ShapeError, ShapeRequest, ShapedGlyph, ShapedRun, TextRange, Typeface,
5};
6use crate::unicode::{
7    graphemes, line_breaks, script_runs, LineBreakKind, LineBreakProvider, LineBreaks, Script,
8};
9use core::iter::Peekable;
10
11use crate::buffer::SliceWriter;
12
13#[derive(Clone, Copy, Debug, Eq, PartialEq)]
14pub(crate) struct LogicalRun {
15    text: TextRange,
16    typeface: u16,
17    script: Script,
18    bidi_level: u8,
19}
20
21impl LogicalRun {
22    pub(crate) const fn empty() -> Self {
23        Self {
24            text: TextRange::new(0, 0),
25            typeface: 0,
26            script: Script::Common,
27            bidi_level: 0,
28        }
29    }
30
31    const fn typeface_index(self) -> usize {
32        self.typeface as usize
33    }
34
35    #[cfg(test)]
36    const fn script(self) -> Script {
37        self.script
38    }
39}
40
41#[derive(Clone, Copy, Debug, Eq, PartialEq)]
42pub enum LayoutError {
43    Bidi(BidiError),
44    NoTypeface,
45    TooManyTypefaces,
46    InsufficientRunCapacity { required: usize },
47    InsufficientGlyphCapacity { minimum: usize },
48    InsufficientLineCapacity { required: usize },
49    InsufficientScratchCapacity { minimum: usize },
50    InsufficientPositionedCapacity { minimum: usize },
51    InsufficientCaretCapacity { minimum: usize },
52    InvalidRun,
53    InvalidTypefaceOutput { run: usize },
54    InvalidWidth,
55    InvalidLineHeight,
56    CoordinateOverflow,
57    Font(FontAccessError),
58    Shape { run: usize, error: ShapeError },
59}
60
61impl From<FontAccessError> for LayoutError {
62    fn from(error: FontAccessError) -> Self {
63        Self::Font(error)
64    }
65}
66
67impl From<BidiError> for LayoutError {
68    fn from(error: BidiError) -> Self {
69        match error {
70            BidiError::InsufficientCapacity { required } => {
71                Self::InsufficientRunCapacity { required }
72            }
73            error => Self::Bidi(error),
74        }
75    }
76}
77
78pub(crate) struct LogicalRuns<'a> {
79    text: TextRange,
80    runs: &'a [LogicalRun],
81}
82
83impl<'a> LogicalRuns<'a> {
84    pub(crate) fn resolve(
85        text: &str,
86        bidi: &BidiText<'_>,
87        typefaces: &[&dyn Typeface],
88        output: &'a mut [LogicalRun],
89    ) -> Result<Self, LayoutError> {
90        if typefaces.is_empty() {
91            return Err(LayoutError::NoTypeface);
92        }
93        if typefaces.len() > u16::MAX as usize {
94            return Err(LayoutError::TooManyTypefaces);
95        }
96        let paragraph = bidi.text();
97        if paragraph.end > u32::MAX as usize {
98            return Err(LayoutError::InvalidRun);
99        }
100        let mut writer = LogicalRunWriter::new(output);
101        for bidi_run in bidi.logical_runs() {
102            let bidi_start = bidi_run.text.start;
103            let bidi_end = bidi_run.text.end;
104            if bidi_start > bidi_end
105                || bidi_end > text.len()
106                || !text.is_char_boundary(bidi_start)
107                || !text.is_char_boundary(bidi_end)
108            {
109                return Err(LayoutError::InvalidRun);
110            }
111            for script_run in script_runs(&text[bidi_start..bidi_end]) {
112                let script_start = bidi_start + script_run.text.start;
113                let script_end = bidi_start + script_run.text.end;
114                for cluster in graphemes(&text[script_start..script_end]) {
115                    let start = script_start + cluster.range.start;
116                    let end = script_start + cluster.range.end;
117                    let typeface = select_typeface(cluster.text, typefaces)?;
118                    writer.push(LogicalRun {
119                        text: TextRange::new(start as u32, end as u32),
120                        typeface,
121                        script: script_run.script,
122                        bidi_level: bidi_run.level,
123                    });
124                }
125            }
126        }
127        let runs = writer.finish()?;
128        Ok(Self {
129            text: TextRange::new(paragraph.start as u32, paragraph.end as u32),
130            runs,
131        })
132    }
133
134    #[cfg(test)]
135    const fn runs(&self) -> &[LogicalRun] {
136        self.runs
137    }
138
139    pub(crate) fn shape_into<'output>(
140        &self,
141        text: &str,
142        typefaces: &[&dyn Typeface],
143        features: &[FontFeature],
144        glyphs: &'output mut [ShapedGlyph],
145        runs: &'output mut [GlyphRun],
146    ) -> Result<ShapedText<'output>, LayoutError> {
147        if runs.len() < self.runs.len() {
148            return Err(LayoutError::InsufficientRunCapacity {
149                required: self.runs.len(),
150            });
151        }
152        let mut glyph_count = 0;
153        for (run_index, logical) in self.runs.iter().enumerate() {
154            let Some(typeface) = typefaces.get(logical.typeface_index()) else {
155                return Err(LayoutError::InvalidRun);
156            };
157            let range = logical.text.start as usize..logical.text.end as usize;
158            let request = ShapeRequest::new(
159                text,
160                range,
161                crate::bidi::Direction::from_level(logical.bidi_level),
162                logical.script,
163            )
164            .with_features(features);
165            let count = match typeface.shape_into(&request, &mut glyphs[glyph_count..]) {
166                Ok(count) => count,
167                Err(ShapeError::InsufficientCapacity { required }) => {
168                    return Err(LayoutError::InsufficientGlyphCapacity {
169                        minimum: glyph_count.saturating_add(required),
170                    });
171                }
172                Err(error) => {
173                    return Err(LayoutError::Shape {
174                        run: run_index,
175                        error,
176                    });
177                }
178            };
179            let end = glyph_count
180                .checked_add(count)
181                .ok_or(LayoutError::InvalidRun)?;
182            if end > glyphs.len()
183                || end > u32::MAX as usize
184                || !valid_shaped_output(&request, &glyphs[glyph_count..end])
185            {
186                return Err(LayoutError::InvalidTypefaceOutput { run: run_index });
187            }
188            runs[run_index] = GlyphRun {
189                text: logical.text,
190                glyphs: TextRange::new(glyph_count as u32, end as u32),
191                font_id: typeface.id(),
192                bidi_level: logical.bidi_level,
193            };
194            glyph_count = end;
195        }
196        Ok(ShapedText {
197            text: self.text,
198            glyphs: &glyphs[..glyph_count],
199            runs: &runs[..self.runs.len()],
200        })
201    }
202
203    pub(crate) fn layout_into<'output>(
204        &self,
205        text: &str,
206        typefaces: &[&dyn Typeface],
207        features: &[FontFeature],
208        broken: &BrokenLines<'_, '_>,
209        options: LayoutOptions,
210        buffers: LayoutBuffers<'output>,
211    ) -> Result<ParagraphLayout<'output>, LayoutError> {
212        ParagraphBuilder::new(options, buffers).layout(
213            LayoutInput {
214                text,
215                typefaces,
216                features,
217                logical: self.runs,
218                shaped: broken.shaped,
219            },
220            broken,
221        )
222    }
223}
224
225#[derive(Clone, Copy)]
226struct LayoutInput<'a, 'face> {
227    text: &'a str,
228    typefaces: &'a [&'face dyn Typeface],
229    features: &'a [FontFeature],
230    logical: &'a [LogicalRun],
231    shaped: &'a ShapedText<'a>,
232}
233
234#[derive(Clone, Copy)]
235struct SyntheticRun {
236    typeface: u16,
237    font_id: FontId,
238    anchor: u32,
239}
240
241struct ParagraphBuilder<'a> {
242    options: LayoutOptions,
243    buffers: LayoutBuffers<'a>,
244    run_count: usize,
245    glyph_count: usize,
246    caret_count: usize,
247}
248
249impl<'output> ParagraphBuilder<'output> {
250    fn new(options: LayoutOptions, buffers: LayoutBuffers<'output>) -> Self {
251        Self {
252            options,
253            buffers,
254            run_count: 0,
255            glyph_count: 0,
256            caret_count: 0,
257        }
258    }
259
260    fn layout(
261        mut self,
262        input: LayoutInput<'_, '_>,
263        broken: &BrokenLines<'_, '_>,
264    ) -> Result<ParagraphLayout<'output>, LayoutError> {
265        let line_count = broken.lines.len().min(self.options.max_lines);
266        let truncates_lines = self.options.overflow == Overflow::Ellipsis
267            && line_count > 0
268            && line_count < broken.lines.len();
269        self.preflight(input.logical, broken, line_count, truncates_lines)?;
270        for (line_index, broken_line) in broken.lines[..line_count].iter().enumerate() {
271            if truncates_lines && line_index + 1 == line_count {
272                self.push_ellipsized_line(input, line_index, *broken_line)?;
273            } else {
274                self.push_line(input, line_index, *broken_line, None)?;
275                if self.options.overflow == Overflow::Ellipsis
276                    && line_index + 1 == line_count
277                    && self
278                        .options
279                        .width
280                        .is_some_and(|width| self.buffers.lines[line_index].advance > width)
281                {
282                    let line_run_start = self.buffers.lines[line_index].runs.start as usize;
283                    let line_glyph_start = self.buffers.lines[line_index].glyphs.start as usize;
284                    let line_caret_start = self.buffers.lines[line_index].carets.start as usize;
285                    self.run_count = line_run_start;
286                    self.glyph_count = line_glyph_start;
287                    self.caret_count = line_caret_start;
288                    self.push_ellipsized_line(input, line_index, *broken_line)?;
289                }
290            }
291        }
292        Ok(self.finish(line_count))
293    }
294
295    fn preflight(
296        &self,
297        logical: &[LogicalRun],
298        broken: &BrokenLines<'_, '_>,
299        line_count: usize,
300        ellipsized: bool,
301    ) -> Result<(), LayoutError> {
302        if self.options.line_height < 0 {
303            return Err(LayoutError::InvalidLineHeight);
304        }
305        if self.buffers.lines.len() < line_count {
306            return Err(LayoutError::InsufficientLineCapacity {
307                required: line_count,
308            });
309        }
310        let required_runs = broken.lines[..line_count]
311            .iter()
312            .try_fold(0usize, |count, line| {
313                let line_runs = logical
314                    .iter()
315                    .filter(|run| intersection(run.text, line.text).is_some())
316                    .count();
317                count
318                    .checked_add(line_runs)
319                    .ok_or(LayoutError::CoordinateOverflow)
320            })?
321            .checked_add(usize::from(ellipsized))
322            .ok_or(LayoutError::CoordinateOverflow)?;
323        if required_runs > u32::MAX as usize || line_count > u32::MAX as usize {
324            return Err(LayoutError::CoordinateOverflow);
325        }
326        if self.buffers.runs.len() < required_runs {
327            return Err(LayoutError::InsufficientRunCapacity {
328                required: required_runs,
329            });
330        }
331        Ok(())
332    }
333
334    fn push_line(
335        &mut self,
336        input: LayoutInput<'_, '_>,
337        line_index: usize,
338        broken: BrokenLine,
339        synthetic: Option<SyntheticRun>,
340    ) -> Result<(), LayoutError> {
341        let line_run_start = self.run_count;
342        self.append_visual_runs(input.logical, input.typefaces, broken)?;
343        reorder_visual_runs(&mut self.buffers.runs[line_run_start..self.run_count]);
344        if let Some(synthetic) = synthetic {
345            self.insert_synthetic_run(line_run_start, synthetic)?;
346        }
347
348        let origin = self.line_origin(line_index)?;
349        let line_glyph_start = self.glyph_count;
350        let line_caret_start = self.caret_count;
351        let mut pen = origin;
352        let line_run_end = self.run_count;
353        for run_index in line_run_start..self.run_count {
354            pen = self.shape_run(input, run_index, line_run_end, broken, pen)?;
355        }
356        let mut advance = pen
357            .x
358            .checked_sub(origin.x)
359            .ok_or(LayoutError::CoordinateOverflow)?;
360        let offset = self.alignment_offset(advance)?;
361        let aligned_origin = FlowPoint {
362            x: origin
363                .x
364                .checked_add(offset)
365                .ok_or(LayoutError::CoordinateOverflow)?,
366            y: origin.y,
367        };
368        self.translate_line(line_glyph_start, line_caret_start, offset)?;
369        if self.options.alignment == Alignment::Justify && broken.end == LineEnd::Wrap {
370            advance = self.justify_line(
371                input.text,
372                broken,
373                line_glyph_start,
374                line_caret_start,
375                advance,
376            )?;
377        }
378        self.buffers.lines[line_index] = LayoutLine {
379            text: broken.text,
380            runs: TextRange::new(line_run_start as u32, self.run_count as u32),
381            glyphs: TextRange::new(line_glyph_start as u32, self.glyph_count as u32),
382            carets: TextRange::new(line_caret_start as u32, self.caret_count as u32),
383            origin: aligned_origin,
384            advance,
385        };
386        Ok(())
387    }
388
389    fn push_ellipsized_line(
390        &mut self,
391        input: LayoutInput<'_, '_>,
392        line_index: usize,
393        line: BrokenLine,
394    ) -> Result<(), LayoutError> {
395        const ELLIPSIS: &str = "\u{2026}";
396
397        let typeface = select_typeface(ELLIPSIS, input.typefaces)?;
398        let face = input
399            .typefaces
400            .get(typeface as usize)
401            .ok_or(LayoutError::InvalidRun)?;
402        let direction = self.options.direction;
403        let request = ShapeRequest::new(ELLIPSIS, 0..ELLIPSIS.len(), direction, Script::Common)
404            .with_features(input.features)
405            .with_line_edges(LineEdges::BOTH);
406        let count = match face.shape_into(&request, self.buffers.scratch) {
407            Ok(count) => count,
408            Err(ShapeError::InsufficientCapacity { required }) => {
409                return Err(LayoutError::InsufficientScratchCapacity { minimum: required });
410            }
411            Err(error) => {
412                return Err(LayoutError::Shape {
413                    run: self.run_count,
414                    error,
415                });
416            }
417        };
418        if count > self.buffers.scratch.len()
419            || !valid_shaped_output(&request, &self.buffers.scratch[..count])
420        {
421            return Err(LayoutError::InvalidTypefaceOutput {
422                run: self.run_count,
423            });
424        }
425        let suffix_advance =
426            self.buffers.scratch[..count]
427                .iter()
428                .try_fold(0i32, |total, glyph| {
429                    total
430                        .checked_add(glyph.advance.x)
431                        .ok_or(LayoutError::CoordinateOverflow)
432                })?;
433        let width = self.options.width.unwrap_or(i32::MAX);
434        let content_limit = width
435            .checked_sub(suffix_advance)
436            .and_then(|value| value.checked_sub(self.options.spacing.letter))
437            .ok_or(LayoutError::CoordinateOverflow)?
438            .max(0);
439        let mut cutoff = fit_prefix(
440            input.shaped,
441            input.text,
442            line.text,
443            content_limit,
444            self.options.spacing,
445        )?;
446        loop {
447            let counts = (self.run_count, self.glyph_count, self.caret_count);
448            self.push_line(
449                input,
450                line_index,
451                BrokenLine {
452                    text: TextRange::new(line.text.start, cutoff),
453                    advance: 0,
454                    end: LineEnd::Paragraph,
455                },
456                Some(SyntheticRun {
457                    typeface,
458                    font_id: face.id(),
459                    anchor: cutoff,
460                }),
461            )?;
462            if self.buffers.lines[line_index].advance <= width || cutoff == line.text.start {
463                return Ok(());
464            }
465            (self.run_count, self.glyph_count, self.caret_count) = counts;
466            cutoff = previous_cluster_start(input.shaped, line.text, cutoff)?;
467        }
468    }
469
470    fn insert_synthetic_run(
471        &mut self,
472        line_run_start: usize,
473        synthetic: SyntheticRun,
474    ) -> Result<(), LayoutError> {
475        if self.run_count >= self.buffers.runs.len() {
476            return Err(LayoutError::InsufficientRunCapacity {
477                required: self.run_count.saturating_add(1),
478            });
479        }
480        let index = match self.options.direction {
481            Direction::LeftToRight => self.run_count,
482            Direction::RightToLeft => line_run_start,
483        };
484        self.buffers
485            .runs
486            .copy_within(index..self.run_count, index + 1);
487        let face = synthetic.typeface;
488        self.buffers.runs[index] = VisualRun {
489            text: TextRange::new(synthetic.anchor, synthetic.anchor),
490            glyphs: TextRange::new(0, 0),
491            font_id: synthetic.font_id,
492            typeface_index: face,
493            script: Script::Common,
494            bidi_level: match self.options.direction {
495                Direction::LeftToRight => 0,
496                Direction::RightToLeft => 1,
497            },
498            synthetic: true,
499        };
500        self.run_count += 1;
501        Ok(())
502    }
503
504    fn alignment_offset(&self, advance: i32) -> Result<i32, LayoutError> {
505        let Some(width) = self.options.width else {
506            return Ok(0);
507        };
508        let remaining = width.saturating_sub(advance).max(0);
509        Ok(match (self.options.alignment, self.options.direction) {
510            (Alignment::Start, Direction::LeftToRight)
511            | (Alignment::End, Direction::RightToLeft)
512            | (Alignment::Justify, _) => 0,
513            (Alignment::Start, Direction::RightToLeft)
514            | (Alignment::End, Direction::LeftToRight) => remaining,
515            (Alignment::Center, _) => remaining / 2,
516        })
517    }
518
519    fn translate_line(
520        &mut self,
521        glyph_start: usize,
522        caret_start: usize,
523        offset: i32,
524    ) -> Result<(), LayoutError> {
525        if offset == 0 {
526            return Ok(());
527        }
528        for glyph in &mut self.buffers.glyphs[glyph_start..self.glyph_count] {
529            glyph.origin.x = glyph
530                .origin
531                .x
532                .checked_add(offset)
533                .ok_or(LayoutError::CoordinateOverflow)?;
534        }
535        for caret in &mut self.buffers.carets[caret_start..self.caret_count] {
536            caret.position.x = caret
537                .position
538                .x
539                .checked_add(offset)
540                .ok_or(LayoutError::CoordinateOverflow)?;
541        }
542        Ok(())
543    }
544
545    fn justify_line(
546        &mut self,
547        text: &str,
548        line: BrokenLine,
549        glyph_start: usize,
550        caret_start: usize,
551        advance: i32,
552    ) -> Result<i32, LayoutError> {
553        let Some(width) = self.options.width else {
554            return Ok(advance);
555        };
556        let remaining = width.saturating_sub(advance);
557        if remaining <= 0 {
558            return Ok(advance);
559        }
560        let trimmed_end = trailing_content_end(text, line.text)?;
561        let glyphs = &self.buffers.glyphs[glyph_start..self.glyph_count];
562        let gaps = glyphs
563            .iter()
564            .enumerate()
565            .filter(|(index, glyph)| {
566                glyphs
567                    .get(index + 1)
568                    .is_none_or(|next| next.cluster != glyph.cluster)
569                    && justification_gap(text, glyph.cluster, trimmed_end)
570            })
571            .count();
572        if gaps == 0 {
573            return Ok(advance);
574        }
575        let gaps = i32::try_from(gaps).map_err(|_| LayoutError::CoordinateOverflow)?;
576        let each = remaining / gaps;
577        let mut remainder = remaining % gaps;
578        let mut shift = 0i32;
579        let (glyphs, carets) = (&mut self.buffers.glyphs, &mut self.buffers.carets);
580        let glyphs = &mut glyphs[glyph_start..self.glyph_count];
581        let carets = &mut carets[caret_start..self.caret_count];
582        for index in 0..glyphs.len() {
583            glyphs[index].origin.x = glyphs[index]
584                .origin
585                .x
586                .checked_add(shift)
587                .ok_or(LayoutError::CoordinateOverflow)?;
588            let cluster_end = glyphs
589                .get(index + 1)
590                .is_none_or(|next| next.cluster != glyphs[index].cluster);
591            if cluster_end && justification_gap(text, glyphs[index].cluster, trimmed_end) {
592                let extra = each + i32::from(remainder > 0);
593                remainder = remainder.saturating_sub(1);
594                let boundary = glyphs[index]
595                    .origin
596                    .x
597                    .checked_add(glyphs[index].advance.x)
598                    .ok_or(LayoutError::CoordinateOverflow)?;
599                glyphs[index].advance.x = glyphs[index]
600                    .advance
601                    .x
602                    .checked_add(extra)
603                    .ok_or(LayoutError::CoordinateOverflow)?;
604                shift = shift
605                    .checked_add(extra)
606                    .ok_or(LayoutError::CoordinateOverflow)?;
607                for caret in carets
608                    .iter_mut()
609                    .filter(|caret| caret.position.x >= boundary)
610                {
611                    caret.position.x = caret
612                        .position
613                        .x
614                        .checked_add(extra)
615                        .ok_or(LayoutError::CoordinateOverflow)?;
616                }
617            }
618        }
619        advance
620            .checked_add(shift)
621            .ok_or(LayoutError::CoordinateOverflow)
622    }
623
624    fn append_visual_runs(
625        &mut self,
626        logical: &[LogicalRun],
627        typefaces: &[&dyn Typeface],
628        broken: BrokenLine,
629    ) -> Result<(), LayoutError> {
630        for logical in logical {
631            let Some(text) = intersection(logical.text, broken.text) else {
632                continue;
633            };
634            let Some(typeface) = typefaces.get(logical.typeface_index()) else {
635                return Err(LayoutError::InvalidRun);
636            };
637            self.buffers.runs[self.run_count] = VisualRun {
638                text,
639                glyphs: TextRange::new(0, 0),
640                font_id: typeface.id(),
641                typeface_index: logical.typeface,
642                script: logical.script,
643                bidi_level: logical.bidi_level,
644                synthetic: false,
645            };
646            self.run_count += 1;
647        }
648        Ok(())
649    }
650
651    fn line_origin(&self, line_index: usize) -> Result<FlowPoint, LayoutError> {
652        let line = i32::try_from(line_index).map_err(|_| LayoutError::CoordinateOverflow)?;
653        let y = self
654            .options
655            .line_height
656            .checked_mul(line)
657            .and_then(|offset| self.options.origin.y.checked_add(offset))
658            .ok_or(LayoutError::CoordinateOverflow)?;
659        Ok(FlowPoint {
660            x: self.options.origin.x,
661            y,
662        })
663    }
664
665    fn shape_run(
666        &mut self,
667        input: LayoutInput<'_, '_>,
668        run_index: usize,
669        line_run_end: usize,
670        line: BrokenLine,
671        origin: FlowPoint,
672    ) -> Result<FlowPoint, LayoutError> {
673        let mut visual = self.buffers.runs[run_index];
674        let Some(typeface) = input.typefaces.get(visual.typeface_index as usize) else {
675            return Err(LayoutError::InvalidRun);
676        };
677        const ELLIPSIS: &str = "\u{2026}";
678        let (text, range, edges) = if visual.synthetic {
679            (ELLIPSIS, 0..ELLIPSIS.len(), LineEdges::BOTH)
680        } else {
681            (
682                input.text,
683                visual.text.start as usize..visual.text.end as usize,
684                line_edges(visual.text, line.text),
685            )
686        };
687        let request = ShapeRequest::new(
688            text,
689            range,
690            crate::bidi::Direction::from_level(visual.bidi_level),
691            visual.script,
692        )
693        .with_features(input.features)
694        .with_line_edges(edges);
695        let count = match typeface.shape_into(&request, self.buffers.scratch) {
696            Ok(count) => count,
697            Err(ShapeError::InsufficientCapacity { required }) => {
698                return Err(LayoutError::InsufficientScratchCapacity { minimum: required });
699            }
700            Err(error) => {
701                return Err(LayoutError::Shape {
702                    run: run_index,
703                    error,
704                });
705            }
706        };
707        if count > self.buffers.scratch.len()
708            || !valid_shaped_output(&request, &self.buffers.scratch[..count])
709        {
710            return Err(LayoutError::InvalidTypefaceOutput { run: run_index });
711        }
712        apply_spacing(
713            text,
714            run_index + 1 < line_run_end,
715            self.options.spacing,
716            &mut self.buffers.scratch[..count],
717        )?;
718        if visual.synthetic {
719            for glyph in &mut self.buffers.scratch[..count] {
720                glyph.cluster = visual.text;
721            }
722        }
723        let glyph_end = self
724            .glyph_count
725            .checked_add(count)
726            .ok_or(LayoutError::CoordinateOverflow)?;
727        if glyph_end > u32::MAX as usize {
728            return Err(LayoutError::CoordinateOverflow);
729        }
730        if glyph_end > self.buffers.glyphs.len() {
731            return Err(LayoutError::InsufficientPositionedCapacity { minimum: glyph_end });
732        }
733        let shaped = ShapedRun::new(
734            visual.font_id,
735            visual.text,
736            visual.bidi_level,
737            &self.buffers.scratch[..count],
738        );
739        let positioned = shaped
740            .position_into(
741                origin,
742                &mut self.buffers.glyphs[self.glyph_count..glyph_end],
743            )
744            .map_err(|error| position_error(error, self.glyph_count))?;
745        let end = positioned.end();
746        if !visual.synthetic {
747            let carets = positioned
748                .carets_into(&mut self.buffers.carets[self.caret_count..])
749                .map_err(|error| caret_error(error, self.caret_count))?;
750            self.caret_count = self
751                .caret_count
752                .checked_add(carets.len())
753                .ok_or(LayoutError::CoordinateOverflow)?;
754        }
755        if self.caret_count > u32::MAX as usize {
756            return Err(LayoutError::CoordinateOverflow);
757        }
758        visual.glyphs = TextRange::new(self.glyph_count as u32, glyph_end as u32);
759        self.buffers.runs[run_index] = visual;
760        self.glyph_count = glyph_end;
761        Ok(end)
762    }
763
764    fn finish(self, line_count: usize) -> ParagraphLayout<'output> {
765        ParagraphLayout {
766            lines: &self.buffers.lines[..line_count],
767            runs: &self.buffers.runs[..self.run_count],
768            glyphs: &self.buffers.glyphs[..self.glyph_count],
769            carets: &self.buffers.carets[..self.caret_count],
770        }
771    }
772}
773
774fn line_edges(run: TextRange, line: TextRange) -> LineEdges {
775    match (run.start == line.start, run.end == line.end) {
776        (true, true) => LineEdges::BOTH,
777        (true, false) => LineEdges::START,
778        (false, true) => LineEdges::END,
779        (false, false) => LineEdges::NONE,
780    }
781}
782
783fn spacing_after(
784    text: &str,
785    cluster: TextRange,
786    paragraph: TextRange,
787    spacing: TextSpacing,
788) -> Result<i32, LayoutError> {
789    if cluster.end >= paragraph.end {
790        return Ok(0);
791    }
792    cluster_spacing(text, cluster, spacing)
793}
794
795fn apply_spacing(
796    text: &str,
797    has_following_run: bool,
798    spacing: TextSpacing,
799    glyphs: &mut [ShapedGlyph],
800) -> Result<(), LayoutError> {
801    let mut start = 0;
802    while start < glyphs.len() {
803        let cluster = glyphs[start].cluster;
804        let mut end = start + 1;
805        while end < glyphs.len() && glyphs[end].cluster == cluster {
806            end += 1;
807        }
808        if end < glyphs.len() || has_following_run {
809            let extra = cluster_spacing(text, cluster, spacing)?;
810            glyphs[end - 1].advance.x = glyphs[end - 1]
811                .advance
812                .x
813                .checked_add(extra)
814                .ok_or(LayoutError::CoordinateOverflow)?;
815        }
816        start = end;
817    }
818    Ok(())
819}
820
821fn cluster_spacing(
822    text: &str,
823    cluster: TextRange,
824    spacing: TextSpacing,
825) -> Result<i32, LayoutError> {
826    let value = text
827        .get(cluster.start as usize..cluster.end as usize)
828        .ok_or(LayoutError::InvalidRun)?;
829    if value
830        .chars()
831        .any(|character| matches!(character, '\r' | '\n'))
832    {
833        return Ok(0);
834    }
835    let word = if !value.is_empty() && value.chars().all(char::is_whitespace) {
836        spacing.word
837    } else {
838        0
839    };
840    spacing
841        .letter
842        .checked_add(word)
843        .ok_or(LayoutError::CoordinateOverflow)
844}
845
846fn trailing_content_end(text: &str, line: TextRange) -> Result<u32, LayoutError> {
847    let content = text
848        .get(line.start as usize..line.end as usize)
849        .ok_or(LayoutError::InvalidRun)?;
850    let trimmed = content.trim_end_matches(char::is_whitespace);
851    let end = line.start as usize + trimmed.len();
852    u32::try_from(end).map_err(|_| LayoutError::CoordinateOverflow)
853}
854
855fn justification_gap(text: &str, cluster: TextRange, content_end: u32) -> bool {
856    cluster.end <= content_end
857        && text
858            .get(cluster.start as usize..cluster.end as usize)
859            .is_some_and(|value| !value.is_empty() && value.chars().all(char::is_whitespace))
860}
861
862fn fit_prefix(
863    shaped: &ShapedText<'_>,
864    text: &str,
865    line: TextRange,
866    max_width: i32,
867    spacing: TextSpacing,
868) -> Result<u32, LayoutError> {
869    let mut glyphs = LogicalGlyphs::new(shaped).peekable();
870    let mut width = 0i32;
871    let mut cutoff = line.start;
872    while let Some(first) = glyphs.next() {
873        let cluster = first.cluster;
874        let mut advance = first.advance.x;
875        while let Some(next) = glyphs.peek() {
876            if next.cluster != cluster {
877                break;
878            }
879            advance = advance
880                .checked_add(next.advance.x)
881                .ok_or(LayoutError::CoordinateOverflow)?;
882            glyphs.next();
883        }
884        if cluster.start < line.start || cluster.end > line.end {
885            continue;
886        }
887        advance = advance
888            .checked_add(cluster_spacing(text, cluster, spacing)?)
889            .ok_or(LayoutError::CoordinateOverflow)?;
890        let next = width
891            .checked_add(advance)
892            .ok_or(LayoutError::CoordinateOverflow)?;
893        if next > max_width {
894            break;
895        }
896        width = next;
897        let content = text
898            .get(cluster.start as usize..cluster.end as usize)
899            .ok_or(LayoutError::InvalidRun)?;
900        if !content.chars().all(char::is_whitespace) && shaped.is_safe_break(cluster.end) {
901            cutoff = cluster.end;
902        }
903    }
904    Ok(cutoff)
905}
906
907fn previous_cluster_start(
908    shaped: &ShapedText<'_>,
909    line: TextRange,
910    cutoff: u32,
911) -> Result<u32, LayoutError> {
912    let mut previous = line.start;
913    for glyph in LogicalGlyphs::new(shaped) {
914        let cluster = glyph.cluster;
915        if cluster.start < line.start || cluster.end > line.end || cluster.end >= cutoff {
916            continue;
917        }
918        if shaped.is_safe_break(cluster.end) {
919            previous = previous.max(cluster.end);
920        }
921    }
922    Ok(previous)
923}
924
925struct LogicalRunWriter<'a> {
926    output: SliceWriter<'a, LogicalRun>,
927    last: Option<LogicalRun>,
928}
929
930impl<'a> LogicalRunWriter<'a> {
931    fn new(output: &'a mut [LogicalRun]) -> Self {
932        Self {
933            output: SliceWriter::new(output),
934            last: None,
935        }
936    }
937
938    fn push(&mut self, run: LogicalRun) {
939        if let Some(previous) = self.last.as_mut() {
940            if previous.text.end == run.text.start
941                && previous.typeface == run.typeface
942                && previous.script == run.script
943                && previous.bidi_level == run.bidi_level
944            {
945                previous.text.end = run.text.end;
946                if let Some(stored) = self.output.last_mut() {
947                    stored.text.end = run.text.end;
948                }
949                return;
950            }
951        }
952        self.output.push(run);
953        self.last = Some(run);
954    }
955
956    fn finish(self) -> Result<&'a [LogicalRun], LayoutError> {
957        self.output
958            .finish()
959            .map_err(|required| LayoutError::InsufficientRunCapacity { required })
960    }
961}
962
963fn select_typeface(grapheme: &str, typefaces: &[&dyn Typeface]) -> Result<u16, FontAccessError> {
964    for (index, typeface) in typefaces.iter().enumerate() {
965        if typeface.covers(grapheme)? {
966            return Ok(index as u16);
967        }
968    }
969    Ok(0)
970}
971
972#[derive(Clone, Copy, Debug, Eq, PartialEq)]
973pub(crate) struct GlyphRun {
974    text: TextRange,
975    glyphs: TextRange,
976    font_id: FontId,
977    bidi_level: u8,
978}
979
980impl GlyphRun {
981    pub(crate) const fn empty() -> Self {
982        Self {
983            text: TextRange::new(0, 0),
984            glyphs: TextRange::new(0, 0),
985            font_id: FontId::new(0),
986            bidi_level: 0,
987        }
988    }
989}
990
991pub(crate) struct ShapedText<'a> {
992    text: TextRange,
993    glyphs: &'a [ShapedGlyph],
994    runs: &'a [GlyphRun],
995}
996
997#[derive(Clone, Copy, Debug, Default, Eq, PartialEq)]
998pub enum WrapMode {
999    /// Preserves the paragraph as one line except for mandatory breaks.
1000    NoWrap,
1001    /// Wraps only at declared line-break opportunities.
1002    #[default]
1003    Word,
1004    /// Wraps at declared opportunities, then falls back to grapheme boundaries.
1005    WordOrGrapheme,
1006    /// Wraps at every safe grapheme boundary.
1007    Grapheme,
1008}
1009
1010#[derive(Clone, Copy, Debug, Default, Eq, PartialEq)]
1011pub struct TextSpacing {
1012    pub letter: i32,
1013    pub word: i32,
1014}
1015
1016impl ShapedText<'_> {
1017    #[cfg(test)]
1018    const fn glyphs(&self) -> &[ShapedGlyph] {
1019        self.glyphs
1020    }
1021
1022    #[cfg(test)]
1023    const fn runs(&self) -> &[GlyphRun] {
1024        self.runs
1025    }
1026
1027    #[cfg(test)]
1028    fn run(&self, index: usize) -> Option<ShapedRun<'_>> {
1029        let run = *self.runs.get(index)?;
1030        let glyphs = self
1031            .glyphs
1032            .get(run.glyphs.start as usize..run.glyphs.end as usize)?;
1033        Some(ShapedRun::new(
1034            run.font_id,
1035            run.text,
1036            run.bidi_level,
1037            glyphs,
1038        ))
1039    }
1040
1041    pub fn is_safe_break(&self, offset: u32) -> bool {
1042        if offset == self.text.start || offset == self.text.end {
1043            return true;
1044        }
1045        if offset < self.text.start || offset > self.text.end {
1046            return false;
1047        }
1048        !self.glyphs.iter().any(|glyph| {
1049            glyph.cluster.start < offset && offset < glyph.cluster.end
1050                || glyph.cluster.start == offset && glyph.unsafe_to_break()
1051        })
1052    }
1053
1054    #[cfg(test)]
1055    fn break_into<'shaped, 'output>(
1056        &'shaped self,
1057        text: &str,
1058        max_width: i32,
1059        mode: WrapMode,
1060        spacing: TextSpacing,
1061        output: &'output mut [BrokenLine],
1062    ) -> Result<BrokenLines<'shaped, 'output>, LayoutError> {
1063        self.break_into_with_provider(text, max_width, mode, spacing, None, output)
1064    }
1065
1066    /// Breaks shaped text with additional opportunities supplied by `provider`.
1067    #[cfg(test)]
1068    fn break_into_with<'shaped, 'output>(
1069        &'shaped self,
1070        text: &str,
1071        max_width: i32,
1072        mode: WrapMode,
1073        spacing: TextSpacing,
1074        provider: &dyn LineBreakProvider,
1075        output: &'output mut [BrokenLine],
1076    ) -> Result<BrokenLines<'shaped, 'output>, LayoutError> {
1077        self.break_into_with_provider(text, max_width, mode, spacing, Some(provider), output)
1078    }
1079
1080    pub(crate) fn break_into_with_provider<'shaped, 'output>(
1081        &'shaped self,
1082        text: &str,
1083        max_width: i32,
1084        mode: WrapMode,
1085        spacing: TextSpacing,
1086        provider: Option<&dyn LineBreakProvider>,
1087        output: &'output mut [BrokenLine],
1088    ) -> Result<BrokenLines<'shaped, 'output>, LayoutError> {
1089        if max_width < 0 {
1090            return Err(LayoutError::InvalidWidth);
1091        }
1092        let start = self.text.start as usize;
1093        let end = self.text.end as usize;
1094        if start > end
1095            || end > text.len()
1096            || !text.is_char_boundary(start)
1097            || !text.is_char_boundary(end)
1098        {
1099            return Err(LayoutError::InvalidRun);
1100        }
1101        let breaks = line_breaks(&text[start..end]).peekable();
1102        let mut breaker = LineBreaker::new(self, text, max_width, mode, breaks, provider, output);
1103        let mut glyphs = LogicalGlyphs::new(self).peekable();
1104        while let Some(first) = glyphs.next() {
1105            let cluster = first.cluster;
1106            let mut advance = first.advance.x;
1107            while let Some(next) = glyphs.peek() {
1108                if next.cluster != cluster {
1109                    break;
1110                }
1111                advance = advance
1112                    .checked_add(next.advance.x)
1113                    .ok_or(LayoutError::CoordinateOverflow)?;
1114                glyphs.next();
1115            }
1116            advance = advance
1117                .checked_add(spacing_after(text, cluster, self.text, spacing)?)
1118                .ok_or(LayoutError::CoordinateOverflow)?;
1119            breaker.add_cluster(cluster, advance)?;
1120        }
1121        breaker.finish()
1122    }
1123}
1124
1125struct LogicalGlyphs<'a> {
1126    shaped: &'a ShapedText<'a>,
1127    run: usize,
1128    glyph: usize,
1129}
1130
1131impl<'a> LogicalGlyphs<'a> {
1132    fn new(shaped: &'a ShapedText<'a>) -> Self {
1133        Self {
1134            shaped,
1135            run: 0,
1136            glyph: 0,
1137        }
1138    }
1139}
1140
1141impl<'a> Iterator for LogicalGlyphs<'a> {
1142    type Item = &'a ShapedGlyph;
1143
1144    fn next(&mut self) -> Option<Self::Item> {
1145        loop {
1146            let run = self.shaped.runs.get(self.run)?;
1147            let start = run.glyphs.start as usize;
1148            let end = run.glyphs.end as usize;
1149            if self.glyph < end.saturating_sub(start) {
1150                let index = if run.bidi_level & 1 == 0 {
1151                    start + self.glyph
1152                } else {
1153                    end - self.glyph - 1
1154                };
1155                self.glyph += 1;
1156                return self.shaped.glyphs.get(index);
1157            }
1158            self.run += 1;
1159            self.glyph = 0;
1160        }
1161    }
1162}
1163
1164#[derive(Clone, Copy, Debug, Default, Eq, PartialEq)]
1165pub(crate) struct BrokenLine {
1166    text: TextRange,
1167    advance: i32,
1168    end: LineEnd,
1169}
1170
1171impl BrokenLine {
1172    pub(crate) const fn empty() -> Self {
1173        Self {
1174            text: TextRange::new(0, 0),
1175            advance: 0,
1176            end: LineEnd::Paragraph,
1177        }
1178    }
1179
1180    #[cfg(test)]
1181    const fn text(self) -> TextRange {
1182        self.text
1183    }
1184
1185    #[cfg(test)]
1186    const fn advance(self) -> i32 {
1187        self.advance
1188    }
1189}
1190
1191#[derive(Clone, Copy, Debug, Default, Eq, PartialEq)]
1192enum LineEnd {
1193    Wrap,
1194    Mandatory,
1195    #[default]
1196    Paragraph,
1197}
1198
1199pub(crate) struct BrokenLines<'shaped, 'output> {
1200    shaped: &'shaped ShapedText<'shaped>,
1201    lines: &'output [BrokenLine],
1202}
1203
1204impl BrokenLines<'_, '_> {
1205    #[cfg(test)]
1206    const fn lines(&self) -> &[BrokenLine] {
1207        self.lines
1208    }
1209}
1210
1211struct LineBreaker<'shaped, 'glyphs, 'text, 'output> {
1212    shaped: &'shaped ShapedText<'glyphs>,
1213    text: &'text str,
1214    paragraph: TextRange,
1215    max_width: i32,
1216    mode: WrapMode,
1217    breaks: Peekable<LineBreaks<'text>>,
1218    provider: Option<&'text dyn LineBreakProvider>,
1219    writer: LineWriter<'output>,
1220    line_start: u32,
1221    width: i32,
1222    last_allowed: Option<(u32, i32)>,
1223}
1224
1225impl<'shaped, 'glyphs, 'text, 'output> LineBreaker<'shaped, 'glyphs, 'text, 'output> {
1226    fn new(
1227        shaped: &'shaped ShapedText<'glyphs>,
1228        text: &'text str,
1229        max_width: i32,
1230        mode: WrapMode,
1231        breaks: Peekable<LineBreaks<'text>>,
1232        provider: Option<&'text dyn LineBreakProvider>,
1233        output: &'output mut [BrokenLine],
1234    ) -> Self {
1235        Self {
1236            shaped,
1237            text,
1238            paragraph: shaped.text,
1239            max_width,
1240            mode,
1241            breaks,
1242            provider,
1243            writer: LineWriter::new(output),
1244            line_start: shaped.text.start,
1245            width: 0,
1246            last_allowed: None,
1247        }
1248    }
1249
1250    fn add_cluster(&mut self, cluster: TextRange, advance: i32) -> Result<(), LayoutError> {
1251        self.take_breaks_through(cluster.start)?;
1252        let width_before = self.width;
1253        self.width = self
1254            .width
1255            .checked_add(advance)
1256            .ok_or(LayoutError::CoordinateOverflow)?;
1257        if self.width > self.max_width {
1258            match self.mode {
1259                WrapMode::NoWrap => {}
1260                WrapMode::Word => {
1261                    if let Some((offset, width)) = self.last_allowed.take() {
1262                        self.emit(offset, width, LineEnd::Wrap)?;
1263                    }
1264                }
1265                WrapMode::WordOrGrapheme => {
1266                    if let Some((offset, width)) = self.last_allowed.take() {
1267                        self.emit(offset, width, LineEnd::Wrap)?;
1268                    } else if width_before > 0
1269                        && cluster.start > self.line_start
1270                        && self.shaped.is_safe_break(cluster.start)
1271                    {
1272                        self.emit(cluster.start, width_before, LineEnd::Wrap)?;
1273                    } else if self.line_start == cluster.start
1274                        && self.shaped.is_safe_break(cluster.end)
1275                    {
1276                        self.emit(cluster.end, self.width, LineEnd::Wrap)?;
1277                    }
1278                }
1279                WrapMode::Grapheme if width_before > 0 && cluster.start > self.line_start => {
1280                    self.emit(cluster.start, width_before, LineEnd::Wrap)?;
1281                }
1282                WrapMode::Grapheme if self.line_start == cluster.start => {
1283                    self.emit(cluster.end, self.width, LineEnd::Wrap)?;
1284                }
1285                WrapMode::Grapheme => {}
1286            }
1287        }
1288        self.take_breaks_through(cluster.end)?;
1289        self.take_provider_break(cluster.end)
1290    }
1291
1292    fn take_provider_break(&mut self, offset: u32) -> Result<(), LayoutError> {
1293        let Some(provider) = self.provider else {
1294            return Ok(());
1295        };
1296        if offset <= self.line_start || !self.shaped.is_safe_break(offset) {
1297            return Ok(());
1298        }
1299        match provider.break_at(self.text, offset as usize) {
1300            Some(LineBreakKind::Allowed) => self.take_allowed_break(offset),
1301            Some(LineBreakKind::Mandatory) => self.emit(offset, self.width, LineEnd::Mandatory),
1302            None => Ok(()),
1303        }
1304    }
1305
1306    fn take_breaks_through(&mut self, offset: u32) -> Result<(), LayoutError> {
1307        while self
1308            .breaks
1309            .peek()
1310            .is_some_and(|next| self.paragraph.start as usize + next.offset <= offset as usize)
1311        {
1312            let next = self.breaks.next().unwrap();
1313            let global = self.paragraph.start + next.offset as u32;
1314            if global <= self.line_start || !self.shaped.is_safe_break(global) {
1315                continue;
1316            }
1317            match next.kind {
1318                LineBreakKind::Mandatory => {
1319                    let end = if global == self.paragraph.end {
1320                        LineEnd::Paragraph
1321                    } else {
1322                        LineEnd::Mandatory
1323                    };
1324                    self.emit(global, self.width, end)?;
1325                }
1326                LineBreakKind::Allowed => self.take_allowed_break(global)?,
1327            }
1328        }
1329        Ok(())
1330    }
1331
1332    fn take_allowed_break(&mut self, offset: u32) -> Result<(), LayoutError> {
1333        if !matches!(self.mode, WrapMode::Word | WrapMode::WordOrGrapheme) {
1334            return Ok(());
1335        }
1336        if self.width > self.max_width {
1337            self.emit(offset, self.width, LineEnd::Wrap)
1338        } else {
1339            self.last_allowed = Some((offset, self.width));
1340            Ok(())
1341        }
1342    }
1343
1344    fn emit(&mut self, end: u32, advance: i32, line_end: LineEnd) -> Result<(), LayoutError> {
1345        if end <= self.line_start {
1346            return Ok(());
1347        }
1348        self.writer.push(BrokenLine {
1349            text: TextRange::new(self.line_start, end),
1350            advance,
1351            end: line_end,
1352        });
1353        self.line_start = end;
1354        self.width = self
1355            .width
1356            .checked_sub(advance)
1357            .ok_or(LayoutError::CoordinateOverflow)?;
1358        self.last_allowed = None;
1359        Ok(())
1360    }
1361
1362    fn finish(mut self) -> Result<BrokenLines<'shaped, 'output>, LayoutError> {
1363        self.take_breaks_through(self.paragraph.end)?;
1364        if self.line_start < self.paragraph.end {
1365            self.emit(self.paragraph.end, self.width, LineEnd::Paragraph)?;
1366        }
1367        let lines = self.writer.finish()?;
1368        Ok(BrokenLines {
1369            shaped: self.shaped,
1370            lines,
1371        })
1372    }
1373}
1374
1375struct LineWriter<'a> {
1376    output: SliceWriter<'a, BrokenLine>,
1377}
1378
1379impl<'a> LineWriter<'a> {
1380    fn new(output: &'a mut [BrokenLine]) -> Self {
1381        Self {
1382            output: SliceWriter::new(output),
1383        }
1384    }
1385
1386    fn push(&mut self, line: BrokenLine) {
1387        self.output.push(line);
1388    }
1389
1390    fn finish(self) -> Result<&'a [BrokenLine], LayoutError> {
1391        self.output
1392            .finish()
1393            .map_err(|required| LayoutError::InsufficientLineCapacity { required })
1394    }
1395}
1396
1397#[derive(Clone, Copy, Debug, Eq, PartialEq)]
1398pub struct LayoutOptions {
1399    pub origin: FlowPoint,
1400    pub line_height: i32,
1401    pub spacing: TextSpacing,
1402    pub width: Option<i32>,
1403    pub alignment: Alignment,
1404    pub direction: Direction,
1405    pub max_lines: usize,
1406    pub overflow: Overflow,
1407}
1408
1409impl LayoutOptions {
1410    pub const fn new(line_height: i32) -> Self {
1411        Self {
1412            origin: FlowPoint { x: 0, y: 0 },
1413            line_height,
1414            spacing: TextSpacing { letter: 0, word: 0 },
1415            width: None,
1416            alignment: Alignment::Start,
1417            direction: Direction::LeftToRight,
1418            max_lines: usize::MAX,
1419            overflow: Overflow::Clip,
1420        }
1421    }
1422
1423    pub const fn with_origin(mut self, origin: FlowPoint) -> Self {
1424        self.origin = origin;
1425        self
1426    }
1427
1428    pub const fn with_spacing(mut self, spacing: TextSpacing) -> Self {
1429        self.spacing = spacing;
1430        self
1431    }
1432
1433    pub const fn with_width(mut self, width: i32) -> Self {
1434        self.width = Some(width);
1435        self
1436    }
1437
1438    pub const fn with_alignment(mut self, alignment: Alignment) -> Self {
1439        self.alignment = alignment;
1440        self
1441    }
1442
1443    pub const fn with_direction(mut self, direction: Direction) -> Self {
1444        self.direction = direction;
1445        self
1446    }
1447
1448    pub const fn with_max_lines(mut self, max_lines: usize) -> Self {
1449        self.max_lines = max_lines;
1450        self
1451    }
1452
1453    pub const fn with_overflow(mut self, overflow: Overflow) -> Self {
1454        self.overflow = overflow;
1455        self
1456    }
1457}
1458
1459#[derive(Clone, Copy, Debug, Default, Eq, PartialEq)]
1460pub enum Alignment {
1461    #[default]
1462    Start,
1463    Center,
1464    End,
1465    Justify,
1466}
1467
1468#[derive(Clone, Copy, Debug, Default, Eq, PartialEq)]
1469pub enum Overflow {
1470    #[default]
1471    Clip,
1472    Ellipsis,
1473}
1474
1475/// Fixed-capacity storage for allocation-free paragraph layout.
1476///
1477/// `RUNS` bounds bidi, script, fallback, and visual runs. `GLYPHS` bounds both
1478/// intermediate and positioned glyphs. `LINES` bounds wrapped lines, and
1479/// `CARETS` bounds emitted caret stops. The storage is reusable and performs
1480/// no allocation during [`crate::TextFlow::layout_with_scratch`].
1481pub struct LayoutScratch<
1482    const RUNS: usize,
1483    const GLYPHS: usize,
1484    const LINES: usize,
1485    const CARETS: usize,
1486> {
1487    bidi: [BidiRun; RUNS],
1488    logical: [LogicalRun; RUNS],
1489    initial_glyphs: [ShapedGlyph; GLYPHS],
1490    initial_runs: [GlyphRun; RUNS],
1491    broken: [BrokenLine; LINES],
1492    scratch: [ShapedGlyph; GLYPHS],
1493    glyphs: [PositionedGlyph; GLYPHS],
1494    runs: [VisualRun; RUNS],
1495    lines: [LayoutLine; LINES],
1496    carets: [CaretStop; CARETS],
1497}
1498
1499impl<const RUNS: usize, const GLYPHS: usize, const LINES: usize, const CARETS: usize>
1500    LayoutScratch<RUNS, GLYPHS, LINES, CARETS>
1501{
1502    const EMPTY: Self = Self {
1503        bidi: [const { BidiRun::empty() }; RUNS],
1504        logical: [const { LogicalRun::empty() }; RUNS],
1505        initial_glyphs: [const { ShapedGlyph::new(GlyphId::new(0), TextRange::new(0, 0)) }; GLYPHS],
1506        initial_runs: [const { GlyphRun::empty() }; RUNS],
1507        broken: [const { BrokenLine::empty() }; LINES],
1508        scratch: [const { ShapedGlyph::new(GlyphId::new(0), TextRange::new(0, 0)) }; GLYPHS],
1509        glyphs: [const { PositionedGlyph::new(GlyphId::new(0), FlowPoint { x: 0, y: 0 }) }; GLYPHS],
1510        runs: [const { VisualRun::empty() }; RUNS],
1511        lines: [const { LayoutLine::empty() }; LINES],
1512        carets: [const {
1513            CaretStop {
1514                text_offset: 0,
1515                position: FlowPoint { x: 0, y: 0 },
1516                bidi_level: 0,
1517            }
1518        }; CARETS],
1519    };
1520
1521    pub const fn new() -> Self {
1522        Self::EMPTY
1523    }
1524
1525    // Keeps fixed storage and pipeline temporaries in separate embedded stack frames.
1526    #[inline(never)]
1527    pub(crate) fn layout<'scratch>(
1528        &'scratch mut self,
1529        flow: &crate::TextFlow<'_>,
1530        typefaces: &[&dyn Typeface],
1531    ) -> Result<ParagraphLayout<'scratch>, LayoutError> {
1532        let max_width = i32::try_from(flow.max_width).map_err(|_| LayoutError::InvalidWidth)?;
1533        let width = flow
1534            .width
1535            .map(i32::try_from)
1536            .transpose()
1537            .map_err(|_| LayoutError::InvalidWidth)?;
1538        let line_height =
1539            i32::try_from(flow.line_height).map_err(|_| LayoutError::InvalidLineHeight)?;
1540        let line_spacing =
1541            i32::try_from(flow.line_spacing).map_err(|_| LayoutError::InvalidLineHeight)?;
1542        let line_advance = line_height
1543            .checked_add(line_spacing)
1544            .ok_or(LayoutError::CoordinateOverflow)?;
1545        let bidi = BidiText::resolve(
1546            flow.text,
1547            0..flow.text.len(),
1548            flow.base_direction,
1549            &mut self.bidi,
1550        )?;
1551        let direction = bidi.direction();
1552        let logical = LogicalRuns::resolve(flow.text, &bidi, typefaces, &mut self.logical)?;
1553        let shaped = logical.shape_into(
1554            flow.text,
1555            typefaces,
1556            flow.features,
1557            &mut self.initial_glyphs,
1558            &mut self.initial_runs,
1559        )?;
1560        let spacing = TextSpacing {
1561            letter: flow.letter_spacing,
1562            word: flow.word_spacing,
1563        };
1564        let broken = shaped.break_into_with_provider(
1565            flow.text,
1566            max_width,
1567            flow.wrap,
1568            spacing,
1569            flow.line_break_provider,
1570            &mut self.broken,
1571        )?;
1572        let options = flow.layout_options(line_advance, direction, width);
1573        logical.layout_into(
1574            flow.text,
1575            typefaces,
1576            flow.features,
1577            &broken,
1578            options,
1579            LayoutBuffers::new(
1580                &mut self.scratch,
1581                &mut self.glyphs,
1582                &mut self.runs,
1583                &mut self.lines,
1584                &mut self.carets,
1585            ),
1586        )
1587    }
1588}
1589
1590impl<const RUNS: usize, const GLYPHS: usize, const LINES: usize, const CARETS: usize> Default
1591    for LayoutScratch<RUNS, GLYPHS, LINES, CARETS>
1592{
1593    fn default() -> Self {
1594        Self::new()
1595    }
1596}
1597
1598pub(crate) struct LayoutBuffers<'a> {
1599    scratch: &'a mut [ShapedGlyph],
1600    glyphs: &'a mut [PositionedGlyph],
1601    runs: &'a mut [VisualRun],
1602    lines: &'a mut [LayoutLine],
1603    carets: &'a mut [CaretStop],
1604}
1605
1606impl<'a> LayoutBuffers<'a> {
1607    pub(crate) fn new(
1608        scratch: &'a mut [ShapedGlyph],
1609        glyphs: &'a mut [PositionedGlyph],
1610        runs: &'a mut [VisualRun],
1611        lines: &'a mut [LayoutLine],
1612        carets: &'a mut [CaretStop],
1613    ) -> Self {
1614        Self {
1615            scratch,
1616            glyphs,
1617            runs,
1618            lines,
1619            carets,
1620        }
1621    }
1622}
1623
1624#[derive(Clone, Copy, Debug, Eq, PartialEq)]
1625pub struct VisualRun {
1626    text: TextRange,
1627    glyphs: TextRange,
1628    font_id: FontId,
1629    typeface_index: u16,
1630    script: Script,
1631    bidi_level: u8,
1632    synthetic: bool,
1633}
1634
1635impl VisualRun {
1636    pub const fn empty() -> Self {
1637        Self {
1638            text: TextRange::new(0, 0),
1639            glyphs: TextRange::new(0, 0),
1640            font_id: FontId::new(0),
1641            typeface_index: 0,
1642            script: Script::Common,
1643            bidi_level: 0,
1644            synthetic: false,
1645        }
1646    }
1647
1648    pub const fn text(self) -> TextRange {
1649        self.text
1650    }
1651
1652    pub const fn glyphs(self) -> TextRange {
1653        self.glyphs
1654    }
1655
1656    pub const fn font_id(self) -> FontId {
1657        self.font_id
1658    }
1659
1660    pub const fn bidi_level(self) -> u8 {
1661        self.bidi_level
1662    }
1663
1664    pub const fn is_synthetic(self) -> bool {
1665        self.synthetic
1666    }
1667}
1668
1669#[derive(Clone, Copy, Debug, Default, Eq, PartialEq)]
1670pub struct LayoutLine {
1671    text: TextRange,
1672    runs: TextRange,
1673    glyphs: TextRange,
1674    carets: TextRange,
1675    origin: FlowPoint,
1676    advance: i32,
1677}
1678
1679impl LayoutLine {
1680    pub const fn empty() -> Self {
1681        Self {
1682            text: TextRange::new(0, 0),
1683            runs: TextRange::new(0, 0),
1684            glyphs: TextRange::new(0, 0),
1685            carets: TextRange::new(0, 0),
1686            origin: FlowPoint { x: 0, y: 0 },
1687            advance: 0,
1688        }
1689    }
1690
1691    pub const fn text(self) -> TextRange {
1692        self.text
1693    }
1694
1695    pub const fn runs(self) -> TextRange {
1696        self.runs
1697    }
1698
1699    pub const fn glyphs(self) -> TextRange {
1700        self.glyphs
1701    }
1702
1703    pub const fn carets(self) -> TextRange {
1704        self.carets
1705    }
1706
1707    pub const fn origin(self) -> FlowPoint {
1708        self.origin
1709    }
1710
1711    pub const fn advance(self) -> i32 {
1712        self.advance
1713    }
1714}
1715
1716pub struct ParagraphLayout<'a> {
1717    lines: &'a [LayoutLine],
1718    runs: &'a [VisualRun],
1719    glyphs: &'a [PositionedGlyph],
1720    carets: &'a [CaretStop],
1721}
1722
1723impl<'a> ParagraphLayout<'a> {
1724    #[cfg(feature = "alloc")]
1725    pub(crate) const fn from_parts(
1726        lines: &'a [LayoutLine],
1727        runs: &'a [VisualRun],
1728        glyphs: &'a [PositionedGlyph],
1729        carets: &'a [CaretStop],
1730    ) -> Self {
1731        Self {
1732            lines,
1733            runs,
1734            glyphs,
1735            carets,
1736        }
1737    }
1738
1739    pub const fn lines(&self) -> &[LayoutLine] {
1740        self.lines
1741    }
1742
1743    pub const fn runs(&self) -> &[VisualRun] {
1744        self.runs
1745    }
1746
1747    pub const fn glyphs(&self) -> &[PositionedGlyph] {
1748        self.glyphs
1749    }
1750
1751    pub const fn carets(&self) -> &[CaretStop] {
1752        self.carets
1753    }
1754}
1755
1756fn intersection(left: TextRange, right: TextRange) -> Option<TextRange> {
1757    let start = left.start.max(right.start);
1758    let end = left.end.min(right.end);
1759    (start < end).then_some(TextRange::new(start, end))
1760}
1761
1762fn valid_shaped_output(request: &ShapeRequest<'_>, glyphs: &[ShapedGlyph]) -> bool {
1763    let mut previous = None;
1764    glyphs.iter().all(|glyph| {
1765        let start = glyph.cluster.start as usize;
1766        let end = glyph.cluster.end as usize;
1767        let ordered = match (request.direction, previous) {
1768            (_, None) => true,
1769            (crate::bidi::Direction::LeftToRight, Some(previous)) => {
1770                glyph.cluster.start >= previous
1771            }
1772            (crate::bidi::Direction::RightToLeft, Some(previous)) => {
1773                glyph.cluster.start <= previous
1774            }
1775        };
1776        previous = Some(glyph.cluster.start);
1777        start < end
1778            && start >= request.range.start
1779            && end <= request.range.end
1780            && request.text.is_char_boundary(start)
1781            && request.text.is_char_boundary(end)
1782            && ordered
1783    })
1784}
1785
1786fn reorder_visual_runs(runs: &mut [VisualRun]) {
1787    let max_level = runs.iter().map(|run| run.bidi_level).max().unwrap_or(0);
1788    let min_odd = runs
1789        .iter()
1790        .filter(|run| run.bidi_level & 1 == 1)
1791        .map(|run| run.bidi_level)
1792        .min();
1793    let Some(min_odd) = min_odd else {
1794        return;
1795    };
1796    for level in (min_odd..=max_level).rev() {
1797        let mut start = 0;
1798        while start < runs.len() {
1799            if runs[start].bidi_level < level {
1800                start += 1;
1801                continue;
1802            }
1803            let mut end = start + 1;
1804            while end < runs.len() && runs[end].bidi_level >= level {
1805                end += 1;
1806            }
1807            runs[start..end].reverse();
1808            start = end;
1809        }
1810    }
1811}
1812
1813fn position_error(error: PositionError, current: usize) -> LayoutError {
1814    match error {
1815        PositionError::InsufficientCapacity { required } => {
1816            LayoutError::InsufficientPositionedCapacity {
1817                minimum: current.saturating_add(required),
1818            }
1819        }
1820        PositionError::CoordinateOverflow => LayoutError::CoordinateOverflow,
1821    }
1822}
1823
1824fn caret_error(error: PositionError, current: usize) -> LayoutError {
1825    match error {
1826        PositionError::InsufficientCapacity { required } => {
1827            LayoutError::InsufficientCaretCapacity {
1828                minimum: current.saturating_add(required),
1829            }
1830        }
1831        PositionError::CoordinateOverflow => LayoutError::CoordinateOverflow,
1832    }
1833}
1834
1835#[cfg(test)]
1836mod tests {
1837    use super::*;
1838    use crate::bidi::{BaseDirection, BidiRun};
1839    use crate::shaping::{FlowPoint, FontId, FontMetrics, GlyphId, GlyphSource, SimpleTypeface};
1840    use std::prelude::v1::*;
1841
1842    struct Source {
1843        key: u64,
1844        ascii: bool,
1845    }
1846
1847    impl GlyphSource for Source {
1848        fn id(&self) -> FontId {
1849            FontId::new(self.key)
1850        }
1851
1852        fn metrics(&self) -> Result<FontMetrics, FontAccessError> {
1853            Ok(FontMetrics::default())
1854        }
1855
1856        fn glyph_for(&self, character: char) -> Result<Option<GlyphId>, FontAccessError> {
1857            let covered = character.is_ascii() == self.ascii;
1858            Ok(covered.then_some(GlyphId::new(character as u16)))
1859        }
1860
1861        fn glyph_advance(&self, _glyph: GlyphId) -> Result<FlowPoint, FontAccessError> {
1862            Ok(FlowPoint { x: 1, y: 0 })
1863        }
1864    }
1865
1866    #[test]
1867    fn fixed_scratch_runs_the_complete_pipeline() {
1868        let font = SimpleTypeface::new(&Source {
1869            key: 7,
1870            ascii: true,
1871        });
1872        let typefaces: [&dyn Typeface; 1] = [&font];
1873        let mut scratch = LayoutScratch::<2, 4, 2, 8>::new();
1874
1875        let layout = crate::TextFlow::new("abc", 1)
1876            .without_width()
1877            .with_line_height(12)
1878            .with_wrap(WrapMode::NoWrap)
1879            .with_alignment(Alignment::Center)
1880            .with_overflow(Overflow::Ellipsis)
1881            .layout_with_scratch(&typefaces, &mut scratch)
1882            .unwrap();
1883
1884        assert_eq!(layout.lines().len(), 1);
1885        assert_eq!(layout.lines()[0].origin().x, 0);
1886        assert_eq!(layout.runs().len(), 1);
1887        assert_eq!(layout.glyphs().len(), 3);
1888        assert_eq!(layout.carets().len(), 4);
1889    }
1890
1891    struct EdgeTypeface;
1892
1893    impl Typeface for EdgeTypeface {
1894        fn id(&self) -> FontId {
1895            FontId::new(9)
1896        }
1897
1898        fn metrics(&self) -> Result<FontMetrics, FontAccessError> {
1899            Ok(FontMetrics::default())
1900        }
1901
1902        fn covers(&self, _grapheme: &str) -> Result<bool, FontAccessError> {
1903            Ok(true)
1904        }
1905
1906        fn shape_into(
1907            &self,
1908            request: &ShapeRequest<'_>,
1909            output: &mut [ShapedGlyph],
1910        ) -> Result<usize, ShapeError> {
1911            let shaped = &request.text[request.range.clone()];
1912            let required = shaped.chars().count();
1913            if output.len() < required {
1914                return Err(ShapeError::InsufficientCapacity { required });
1915            }
1916            let advance = if request.line_edges.has_start() || request.line_edges.has_end() {
1917                2
1918            } else {
1919                1
1920            };
1921            for (index, (offset, character)) in shaped.char_indices().enumerate() {
1922                let start = request.range.start + offset;
1923                let end = start + character.len_utf8();
1924                output[index] = ShapedGlyph::new(
1925                    GlyphId::new(character as u16),
1926                    TextRange::new(start as u32, end as u32),
1927                );
1928                output[index].advance.x = advance;
1929            }
1930            Ok(required)
1931        }
1932    }
1933
1934    struct InvalidTypeface;
1935
1936    impl Typeface for InvalidTypeface {
1937        fn id(&self) -> FontId {
1938            FontId::new(10)
1939        }
1940
1941        fn metrics(&self) -> Result<FontMetrics, FontAccessError> {
1942            Ok(FontMetrics::default())
1943        }
1944
1945        fn covers(&self, _grapheme: &str) -> Result<bool, FontAccessError> {
1946            Ok(true)
1947        }
1948
1949        fn shape_into(
1950            &self,
1951            _request: &ShapeRequest<'_>,
1952            output: &mut [ShapedGlyph],
1953        ) -> Result<usize, ShapeError> {
1954            Ok(output.len() + 1)
1955        }
1956    }
1957
1958    fn bidi_slots<const N: usize>() -> [BidiRun; N] {
1959        core::array::from_fn(|_| BidiRun::empty())
1960    }
1961
1962    #[test]
1963    fn splits_runs_by_script_and_fallback_face() {
1964        let text = "ab世界cd";
1965        let primary = SimpleTypeface::new(&Source {
1966            key: 1,
1967            ascii: true,
1968        });
1969        let fallback = SimpleTypeface::new(&Source {
1970            key: 2,
1971            ascii: false,
1972        });
1973        let typefaces: [&dyn Typeface; 2] = [&primary, &fallback];
1974        let mut bidi_output = bidi_slots::<4>();
1975        let bidi =
1976            BidiText::resolve(text, 0..text.len(), BaseDirection::Auto, &mut bidi_output).unwrap();
1977        let mut output = [LogicalRun::empty(); 4];
1978        let runs = LogicalRuns::resolve(text, &bidi, &typefaces, &mut output).unwrap();
1979
1980        assert_eq!(runs.runs().len(), 3);
1981        assert_eq!(runs.runs()[0].typeface_index(), 0);
1982        assert_eq!(runs.runs()[1].typeface_index(), 1);
1983        assert_eq!(runs.runs()[1].script(), Script::Han);
1984        assert_eq!(runs.runs()[2].typeface_index(), 0);
1985    }
1986
1987    #[test]
1988    fn shapes_resolved_runs_into_caller_storage() {
1989        let text = "ab世界";
1990        let primary = SimpleTypeface::new(&Source {
1991            key: 1,
1992            ascii: true,
1993        });
1994        let fallback = SimpleTypeface::new(&Source {
1995            key: 2,
1996            ascii: false,
1997        });
1998        let typefaces: [&dyn Typeface; 2] = [&primary, &fallback];
1999        let mut bidi_output = bidi_slots::<4>();
2000        let bidi =
2001            BidiText::resolve(text, 0..text.len(), BaseDirection::Auto, &mut bidi_output).unwrap();
2002        let mut logical_output = [LogicalRun::empty(); 4];
2003        let logical = LogicalRuns::resolve(text, &bidi, &typefaces, &mut logical_output).unwrap();
2004        let mut glyph_output = [ShapedGlyph::default(); 4];
2005        let mut run_output = [GlyphRun::empty(); 4];
2006        let shaped = logical
2007            .shape_into(text, &typefaces, &[], &mut glyph_output, &mut run_output)
2008            .unwrap();
2009
2010        assert_eq!(shaped.glyphs().len(), 4);
2011        assert_eq!(shaped.runs().len(), 2);
2012        assert_eq!(shaped.run(0).unwrap().font_id(), FontId::new(1));
2013        assert_eq!(shaped.run(1).unwrap().font_id(), FontId::new(2));
2014    }
2015
2016    #[test]
2017    fn reports_exact_run_and_minimum_glyph_capacity() {
2018        let text = "abc";
2019        let primary = SimpleTypeface::new(&Source {
2020            key: 1,
2021            ascii: true,
2022        });
2023        let typefaces: [&dyn Typeface; 1] = [&primary];
2024        let mut bidi_output = bidi_slots::<1>();
2025        let bidi =
2026            BidiText::resolve(text, 0..text.len(), BaseDirection::Auto, &mut bidi_output).unwrap();
2027        let mut logical_output = [LogicalRun::empty(); 1];
2028        let logical = LogicalRuns::resolve(text, &bidi, &typefaces, &mut logical_output).unwrap();
2029        let mut glyph_output = [ShapedGlyph::default(); 2];
2030        let mut run_output = [GlyphRun::empty(); 1];
2031
2032        assert_eq!(
2033            logical
2034                .shape_into(text, &typefaces, &[], &mut glyph_output, &mut run_output,)
2035                .err()
2036                .unwrap(),
2037            LayoutError::InsufficientGlyphCapacity { minimum: 3 }
2038        );
2039    }
2040
2041    #[test]
2042    fn run_capacity_is_exact_when_no_slots_are_available() {
2043        let text = "abc";
2044        let primary = SimpleTypeface::new(&Source {
2045            key: 1,
2046            ascii: true,
2047        });
2048        let typefaces: [&dyn Typeface; 1] = [&primary];
2049        let mut bidi_output = bidi_slots::<1>();
2050        let bidi =
2051            BidiText::resolve(text, 0..text.len(), BaseDirection::Auto, &mut bidi_output).unwrap();
2052        let mut output = [];
2053
2054        assert_eq!(
2055            LogicalRuns::resolve(text, &bidi, &typefaces, &mut output)
2056                .err()
2057                .unwrap(),
2058            LayoutError::InsufficientRunCapacity { required: 1 }
2059        );
2060    }
2061
2062    #[test]
2063    fn breaks_at_the_last_allowed_width() {
2064        let text = "ab cd";
2065        let primary = SimpleTypeface::new(&Source {
2066            key: 1,
2067            ascii: true,
2068        });
2069        let typefaces: [&dyn Typeface; 1] = [&primary];
2070        let mut bidi_output = bidi_slots::<1>();
2071        let bidi =
2072            BidiText::resolve(text, 0..text.len(), BaseDirection::Auto, &mut bidi_output).unwrap();
2073        let mut logical_output = [LogicalRun::empty(); 1];
2074        let logical = LogicalRuns::resolve(text, &bidi, &typefaces, &mut logical_output).unwrap();
2075        let mut glyph_output = [ShapedGlyph::default(); 5];
2076        let mut run_output = [GlyphRun::empty(); 1];
2077        let shaped = logical
2078            .shape_into(text, &typefaces, &[], &mut glyph_output, &mut run_output)
2079            .unwrap();
2080        let mut line_output = [BrokenLine::empty(); 2];
2081        let lines = shaped
2082            .break_into(
2083                text,
2084                3,
2085                WrapMode::Word,
2086                TextSpacing::default(),
2087                &mut line_output,
2088            )
2089            .unwrap();
2090
2091        assert_eq!(lines.lines().len(), 2);
2092        assert_eq!(lines.lines()[0].text(), TextRange::new(0, 3));
2093        assert_eq!(lines.lines()[0].advance(), 3);
2094        assert_eq!(lines.lines()[1].text(), TextRange::new(3, 5));
2095        assert_eq!(lines.lines()[1].advance(), 2);
2096
2097        let mut no_lines = [];
2098        assert_eq!(
2099            shaped
2100                .break_into(
2101                    text,
2102                    3,
2103                    WrapMode::Word,
2104                    TextSpacing::default(),
2105                    &mut no_lines,
2106                )
2107                .err()
2108                .unwrap(),
2109            LayoutError::InsufficientLineCapacity { required: 2 }
2110        );
2111    }
2112
2113    #[test]
2114    fn wrap_mode_controls_optional_breaks() {
2115        let text = "ab cd";
2116        let primary = SimpleTypeface::new(&Source {
2117            key: 1,
2118            ascii: true,
2119        });
2120        let typefaces: [&dyn Typeface; 1] = [&primary];
2121        let mut bidi_output = bidi_slots::<1>();
2122        let bidi =
2123            BidiText::resolve(text, 0..text.len(), BaseDirection::Auto, &mut bidi_output).unwrap();
2124        let mut logical_output = [LogicalRun::empty(); 1];
2125        let logical = LogicalRuns::resolve(text, &bidi, &typefaces, &mut logical_output).unwrap();
2126        let mut glyph_output = [ShapedGlyph::default(); 5];
2127        let mut run_output = [GlyphRun::empty(); 1];
2128        let shaped = logical
2129            .shape_into(text, &typefaces, &[], &mut glyph_output, &mut run_output)
2130            .unwrap();
2131        let mut line_output = [BrokenLine::empty(); 2];
2132
2133        let word = shaped
2134            .break_into(
2135                text,
2136                4,
2137                WrapMode::Word,
2138                TextSpacing::default(),
2139                &mut line_output,
2140            )
2141            .unwrap();
2142        assert_eq!(word.lines()[0].text(), TextRange::new(0, 3));
2143
2144        let grapheme = shaped
2145            .break_into(
2146                text,
2147                4,
2148                WrapMode::Grapheme,
2149                TextSpacing::default(),
2150                &mut line_output,
2151            )
2152            .unwrap();
2153        assert_eq!(grapheme.lines()[0].text(), TextRange::new(0, 4));
2154
2155        let no_wrap = shaped
2156            .break_into(
2157                text,
2158                4,
2159                WrapMode::NoWrap,
2160                TextSpacing::default(),
2161                &mut line_output,
2162            )
2163            .unwrap();
2164        assert_eq!(
2165            no_wrap.lines(),
2166            &[BrokenLine {
2167                text: TextRange::new(0, 5),
2168                advance: 5,
2169                end: LineEnd::Paragraph,
2170            }]
2171        );
2172    }
2173
2174    #[test]
2175    fn spacing_changes_break_width_and_positioned_advances() {
2176        let text = "ab c";
2177        let primary = SimpleTypeface::new(&Source {
2178            key: 1,
2179            ascii: true,
2180        });
2181        let typefaces: [&dyn Typeface; 1] = [&primary];
2182        let mut bidi_output = bidi_slots::<1>();
2183        let bidi =
2184            BidiText::resolve(text, 0..text.len(), BaseDirection::Auto, &mut bidi_output).unwrap();
2185        let mut logical_output = [LogicalRun::empty(); 1];
2186        let logical = LogicalRuns::resolve(text, &bidi, &typefaces, &mut logical_output).unwrap();
2187        let mut initial_glyphs = [ShapedGlyph::default(); 4];
2188        let mut initial_runs = [GlyphRun::empty(); 1];
2189        let shaped = logical
2190            .shape_into(
2191                text,
2192                &typefaces,
2193                &[],
2194                &mut initial_glyphs,
2195                &mut initial_runs,
2196            )
2197            .unwrap();
2198        let spacing = TextSpacing { letter: 1, word: 2 };
2199        let mut broken_output = [BrokenLine::empty(); 1];
2200        let broken = shaped
2201            .break_into(text, 9, WrapMode::NoWrap, spacing, &mut broken_output)
2202            .unwrap();
2203        assert_eq!(broken.lines()[0].advance(), 9);
2204
2205        let mut scratch = [ShapedGlyph::default(); 4];
2206        let mut glyphs = [PositionedGlyph::default(); 4];
2207        let mut runs = [VisualRun::empty(); 1];
2208        let mut lines = [LayoutLine::empty(); 1];
2209        let mut carets = [CaretStop::default(); 5];
2210        let layout = logical
2211            .layout_into(
2212                text,
2213                &typefaces,
2214                &[],
2215                &broken,
2216                LayoutOptions::new(10).with_spacing(spacing),
2217                LayoutBuffers::new(
2218                    &mut scratch,
2219                    &mut glyphs,
2220                    &mut runs,
2221                    &mut lines,
2222                    &mut carets,
2223                ),
2224            )
2225            .unwrap();
2226
2227        assert_eq!(layout.lines()[0].advance(), 9);
2228        assert_eq!(layout.glyphs()[1].origin.x, 2);
2229        assert_eq!(layout.glyphs()[2].origin.x, 4);
2230        assert_eq!(layout.glyphs()[3].origin.x, 8);
2231        assert_eq!(layout.carets().last().unwrap().position.x, 9);
2232    }
2233
2234    #[test]
2235    fn alignment_is_applied_to_glyphs_lines_and_carets() {
2236        let text = "ab";
2237        let primary = SimpleTypeface::new(&Source {
2238            key: 1,
2239            ascii: true,
2240        });
2241        let typefaces: [&dyn Typeface; 1] = [&primary];
2242        let mut bidi_output = bidi_slots::<1>();
2243        let bidi =
2244            BidiText::resolve(text, 0..text.len(), BaseDirection::Auto, &mut bidi_output).unwrap();
2245        let mut logical_output = [LogicalRun::empty(); 1];
2246        let logical = LogicalRuns::resolve(text, &bidi, &typefaces, &mut logical_output).unwrap();
2247        let mut initial_glyphs = [ShapedGlyph::default(); 2];
2248        let mut initial_runs = [GlyphRun::empty(); 1];
2249        let shaped = logical
2250            .shape_into(
2251                text,
2252                &typefaces,
2253                &[],
2254                &mut initial_glyphs,
2255                &mut initial_runs,
2256            )
2257            .unwrap();
2258        let broken_storage = [BrokenLine {
2259            text: TextRange::new(0, 2),
2260            advance: 2,
2261            end: LineEnd::Paragraph,
2262        }];
2263        let broken = BrokenLines {
2264            shaped: &shaped,
2265            lines: &broken_storage,
2266        };
2267        let mut scratch = [ShapedGlyph::default(); 2];
2268        let mut glyphs = [PositionedGlyph::default(); 2];
2269        let mut runs = [VisualRun::empty(); 1];
2270        let mut lines = [LayoutLine::empty(); 1];
2271        let mut carets = [CaretStop::default(); 3];
2272        let layout = logical
2273            .layout_into(
2274                text,
2275                &typefaces,
2276                &[],
2277                &broken,
2278                LayoutOptions::new(10)
2279                    .with_width(10)
2280                    .with_alignment(Alignment::Center),
2281                LayoutBuffers::new(
2282                    &mut scratch,
2283                    &mut glyphs,
2284                    &mut runs,
2285                    &mut lines,
2286                    &mut carets,
2287                ),
2288            )
2289            .unwrap();
2290
2291        assert_eq!(layout.lines()[0].origin().x, 4);
2292        assert_eq!(layout.glyphs()[0].origin.x, 4);
2293        assert_eq!(layout.glyphs()[1].origin.x, 5);
2294        assert_eq!(layout.carets()[0].position.x, 4);
2295        assert_eq!(layout.carets().last().unwrap().position.x, 6);
2296
2297        let mut scratch = [ShapedGlyph::default(); 2];
2298        let mut glyphs = [PositionedGlyph::default(); 2];
2299        let mut runs = [VisualRun::empty(); 1];
2300        let mut lines = [LayoutLine::empty(); 1];
2301        let mut carets = [CaretStop::default(); 3];
2302        let rtl_start = logical
2303            .layout_into(
2304                text,
2305                &typefaces,
2306                &[],
2307                &broken,
2308                LayoutOptions::new(10)
2309                    .with_width(10)
2310                    .with_alignment(Alignment::Start)
2311                    .with_direction(Direction::RightToLeft),
2312                LayoutBuffers::new(
2313                    &mut scratch,
2314                    &mut glyphs,
2315                    &mut runs,
2316                    &mut lines,
2317                    &mut carets,
2318                ),
2319            )
2320            .unwrap();
2321        assert_eq!(rtl_start.lines()[0].origin().x, 8);
2322        assert_eq!(rtl_start.glyphs()[0].origin.x, 8);
2323    }
2324
2325    #[test]
2326    fn justification_expands_internal_spaces_on_wrapped_lines() {
2327        let text = "a b ";
2328        let primary = SimpleTypeface::new(&Source {
2329            key: 1,
2330            ascii: true,
2331        });
2332        let typefaces: [&dyn Typeface; 1] = [&primary];
2333        let mut bidi_output = bidi_slots::<1>();
2334        let bidi =
2335            BidiText::resolve(text, 0..text.len(), BaseDirection::Auto, &mut bidi_output).unwrap();
2336        let mut logical_output = [LogicalRun::empty(); 1];
2337        let logical = LogicalRuns::resolve(text, &bidi, &typefaces, &mut logical_output).unwrap();
2338        let mut initial_glyphs = [ShapedGlyph::default(); 4];
2339        let mut initial_runs = [GlyphRun::empty(); 1];
2340        let shaped = logical
2341            .shape_into(
2342                text,
2343                &typefaces,
2344                &[],
2345                &mut initial_glyphs,
2346                &mut initial_runs,
2347            )
2348            .unwrap();
2349        let broken_storage = [BrokenLine {
2350            text: TextRange::new(0, 4),
2351            advance: 4,
2352            end: LineEnd::Wrap,
2353        }];
2354        let broken = BrokenLines {
2355            shaped: &shaped,
2356            lines: &broken_storage,
2357        };
2358        let mut scratch = [ShapedGlyph::default(); 4];
2359        let mut glyphs = [PositionedGlyph::default(); 4];
2360        let mut runs = [VisualRun::empty(); 1];
2361        let mut lines = [LayoutLine::empty(); 1];
2362        let mut carets = [CaretStop::default(); 5];
2363        let layout = logical
2364            .layout_into(
2365                text,
2366                &typefaces,
2367                &[],
2368                &broken,
2369                LayoutOptions::new(10)
2370                    .with_width(8)
2371                    .with_alignment(Alignment::Justify),
2372                LayoutBuffers::new(
2373                    &mut scratch,
2374                    &mut glyphs,
2375                    &mut runs,
2376                    &mut lines,
2377                    &mut carets,
2378                ),
2379            )
2380            .unwrap();
2381
2382        assert_eq!(layout.lines()[0].advance(), 8);
2383        assert_eq!(layout.glyphs()[1].advance.x, 5);
2384        assert_eq!(layout.glyphs()[2].origin.x, 6);
2385        assert_eq!(layout.glyphs()[3].origin.x, 7);
2386        assert_eq!(layout.carets()[2].position.x, 6);
2387        assert_eq!(layout.carets().last().unwrap().position.x, 8);
2388    }
2389
2390    #[test]
2391    fn lets_unsafe_sequences_exceed_the_width() {
2392        let text = "ab cd";
2393        let mut glyphs = [ShapedGlyph::default(); 5];
2394        for (index, glyph) in glyphs.iter_mut().enumerate() {
2395            *glyph = ShapedGlyph::new(
2396                GlyphId::new(index as u16),
2397                TextRange::new(index as u32, index as u32 + 1),
2398            );
2399            glyph.advance.x = 1;
2400        }
2401        glyphs[3].set_unsafe_to_break(true);
2402        let runs = [GlyphRun {
2403            text: TextRange::new(0, 5),
2404            glyphs: TextRange::new(0, 5),
2405            font_id: FontId::new(1),
2406            bidi_level: 0,
2407        }];
2408        let shaped = ShapedText {
2409            text: TextRange::new(0, 5),
2410            glyphs: &glyphs,
2411            runs: &runs,
2412        };
2413        let mut line_output = [BrokenLine::empty(); 2];
2414        let lines = shaped
2415            .break_into(
2416                text,
2417                3,
2418                WrapMode::WordOrGrapheme,
2419                TextSpacing::default(),
2420                &mut line_output,
2421            )
2422            .unwrap();
2423
2424        assert_eq!(lines.lines()[0].text(), TextRange::new(0, 4));
2425        assert_eq!(lines.lines()[0].advance(), 4);
2426        assert_eq!(lines.lines()[1].text(), TextRange::new(4, 5));
2427    }
2428
2429    struct ThaiBreaks;
2430
2431    impl LineBreakProvider for ThaiBreaks {
2432        fn break_at(&self, text: &str, offset: usize) -> Option<LineBreakKind> {
2433            (text.get(..offset) == Some("ภาษา")).then_some(LineBreakKind::Allowed)
2434        }
2435    }
2436
2437    #[test]
2438    fn continuous_thai_requires_an_explicit_break_policy() {
2439        let text = "ภาษาไทย";
2440        let mut glyphs = [ShapedGlyph::default(); 7];
2441        for ((start, character), glyph) in text.char_indices().zip(&mut glyphs) {
2442            *glyph = ShapedGlyph::new(
2443                GlyphId::new(character as u16),
2444                TextRange::new(start as u32, (start + character.len_utf8()) as u32),
2445            );
2446            glyph.advance.x = 1;
2447        }
2448        let runs = [GlyphRun {
2449            text: TextRange::new(0, text.len() as u32),
2450            glyphs: TextRange::new(0, glyphs.len() as u32),
2451            font_id: FontId::new(1),
2452            bidi_level: 0,
2453        }];
2454        let shaped = ShapedText {
2455            text: TextRange::new(0, text.len() as u32),
2456            glyphs: &glyphs,
2457            runs: &runs,
2458        };
2459        let mut output = [BrokenLine::empty(); 3];
2460
2461        let word = shaped
2462            .break_into(text, 4, WrapMode::Word, TextSpacing::default(), &mut output)
2463            .unwrap();
2464        assert_eq!(word.lines().len(), 1);
2465        assert_eq!(word.lines()[0].text(), TextRange::new(0, text.len() as u32));
2466
2467        let fallback = shaped
2468            .break_into(
2469                text,
2470                4,
2471                WrapMode::WordOrGrapheme,
2472                TextSpacing::default(),
2473                &mut output,
2474            )
2475            .unwrap();
2476        assert_eq!(fallback.lines().len(), 2);
2477        assert_eq!(
2478            fallback.lines()[0].text(),
2479            TextRange::new(0, "ภาษา".len() as u32)
2480        );
2481
2482        let provided = shaped
2483            .break_into_with(
2484                text,
2485                4,
2486                WrapMode::Word,
2487                TextSpacing::default(),
2488                &ThaiBreaks,
2489                &mut output,
2490            )
2491            .unwrap();
2492        assert_eq!(provided.lines().len(), 2);
2493        assert_eq!(
2494            provided.lines()[0].text(),
2495            TextRange::new(0, "ภาษา".len() as u32)
2496        );
2497    }
2498
2499    #[test]
2500    fn ellipsis_keeps_unsafe_cluster_boundaries_together() {
2501        let text = "abc";
2502        let mut glyphs = [ShapedGlyph::default(); 3];
2503        for (index, glyph) in glyphs.iter_mut().enumerate() {
2504            *glyph = ShapedGlyph::new(
2505                GlyphId::new(index as u16),
2506                TextRange::new(index as u32, index as u32 + 1),
2507            );
2508            glyph.advance.x = 1;
2509        }
2510        glyphs[2].set_unsafe_to_break(true);
2511        let runs = [GlyphRun {
2512            text: TextRange::new(0, 3),
2513            glyphs: TextRange::new(0, 3),
2514            font_id: FontId::new(1),
2515            bidi_level: 0,
2516        }];
2517        let shaped = ShapedText {
2518            text: TextRange::new(0, 3),
2519            glyphs: &glyphs,
2520            runs: &runs,
2521        };
2522
2523        assert_eq!(
2524            fit_prefix(
2525                &shaped,
2526                text,
2527                TextRange::new(0, 3),
2528                2,
2529                TextSpacing::default(),
2530            )
2531            .unwrap(),
2532            1
2533        );
2534    }
2535
2536    #[test]
2537    fn reshapes_line_edges_into_visual_outputs() {
2538        let text = "ab cd";
2539        let typefaces: [&dyn Typeface; 1] = [&EdgeTypeface];
2540        let mut bidi_output = bidi_slots::<1>();
2541        let bidi =
2542            BidiText::resolve(text, 0..text.len(), BaseDirection::Auto, &mut bidi_output).unwrap();
2543        let mut logical_output = [LogicalRun::empty(); 1];
2544        let logical = LogicalRuns::resolve(text, &bidi, &typefaces, &mut logical_output).unwrap();
2545        let mut initial_glyphs = [ShapedGlyph::default(); 5];
2546        let mut initial_runs = [GlyphRun::empty(); 1];
2547        let shaped = logical
2548            .shape_into(
2549                text,
2550                &typefaces,
2551                &[],
2552                &mut initial_glyphs,
2553                &mut initial_runs,
2554            )
2555            .unwrap();
2556        let mut broken_output = [BrokenLine::empty(); 2];
2557        let broken = shaped
2558            .break_into(
2559                text,
2560                3,
2561                WrapMode::Word,
2562                TextSpacing::default(),
2563                &mut broken_output,
2564            )
2565            .unwrap();
2566        let mut scratch = [ShapedGlyph::default(); 3];
2567        let mut glyphs = [PositionedGlyph::default(); 5];
2568        let mut runs = [VisualRun::empty(); 2];
2569        let mut lines = [LayoutLine::empty(); 2];
2570        let mut carets = [CaretStop::default(); 7];
2571        let layout = logical
2572            .layout_into(
2573                text,
2574                &typefaces,
2575                &[],
2576                &broken,
2577                LayoutOptions::new(10).with_origin(FlowPoint { x: 5, y: 7 }),
2578                LayoutBuffers::new(
2579                    &mut scratch,
2580                    &mut glyphs,
2581                    &mut runs,
2582                    &mut lines,
2583                    &mut carets,
2584                ),
2585            )
2586            .unwrap();
2587
2588        assert_eq!(layout.lines().len(), 2);
2589        assert_eq!(layout.lines()[0].advance(), 6);
2590        assert_eq!(layout.lines()[1].advance(), 4);
2591        assert_eq!(layout.lines()[0].origin(), FlowPoint { x: 5, y: 7 });
2592        assert_eq!(layout.lines()[1].origin(), FlowPoint { x: 5, y: 17 });
2593        assert_eq!(layout.runs().len(), 2);
2594        assert_eq!(layout.runs()[0].font_id(), FontId::new(9));
2595        assert_eq!(layout.glyphs().len(), 5);
2596        assert_eq!(layout.carets().len(), 7);
2597    }
2598
2599    #[test]
2600    fn ellipsis_rechecks_the_reshaped_line_width() {
2601        let text = "ab cd";
2602        let typefaces: [&dyn Typeface; 1] = [&EdgeTypeface];
2603        let mut bidi_output = bidi_slots::<1>();
2604        let bidi =
2605            BidiText::resolve(text, 0..text.len(), BaseDirection::Auto, &mut bidi_output).unwrap();
2606        let mut logical_output = [LogicalRun::empty(); 1];
2607        let logical = LogicalRuns::resolve(text, &bidi, &typefaces, &mut logical_output).unwrap();
2608        let mut initial_glyphs = [ShapedGlyph::default(); 5];
2609        let mut initial_runs = [GlyphRun::empty(); 1];
2610        let shaped = logical
2611            .shape_into(
2612                text,
2613                &typefaces,
2614                &[],
2615                &mut initial_glyphs,
2616                &mut initial_runs,
2617            )
2618            .unwrap();
2619        let mut broken_output = [BrokenLine::empty(); 2];
2620        let broken = shaped
2621            .break_into(
2622                text,
2623                4,
2624                WrapMode::Word,
2625                TextSpacing::default(),
2626                &mut broken_output,
2627            )
2628            .unwrap();
2629        let mut scratch = [ShapedGlyph::default(); 5];
2630        let mut glyphs = [PositionedGlyph::default(); 5];
2631        let mut runs = [VisualRun::empty(); 3];
2632        let mut lines = [LayoutLine::empty(); 1];
2633        let mut carets = [CaretStop::default(); 6];
2634        let layout = logical
2635            .layout_into(
2636                text,
2637                &typefaces,
2638                &[],
2639                &broken,
2640                LayoutOptions::new(10)
2641                    .with_width(4)
2642                    .with_max_lines(1)
2643                    .with_overflow(Overflow::Ellipsis),
2644                LayoutBuffers::new(
2645                    &mut scratch,
2646                    &mut glyphs,
2647                    &mut runs,
2648                    &mut lines,
2649                    &mut carets,
2650                ),
2651            )
2652            .unwrap();
2653
2654        assert_eq!(layout.lines()[0].text(), TextRange::new(0, 1));
2655        assert_eq!(layout.lines()[0].advance(), 4);
2656        assert_eq!(layout.glyphs()[0].glyph_id(), GlyphId::new('a' as u16));
2657        assert_eq!(
2658            layout.glyphs()[1].glyph_id(),
2659            GlyphId::new('\u{2026}' as u16)
2660        );
2661    }
2662
2663    #[test]
2664    fn rejects_invalid_typeface_output_counts() {
2665        let text = "a";
2666        let typefaces: [&dyn Typeface; 1] = [&InvalidTypeface];
2667        let mut bidi_output = bidi_slots::<1>();
2668        let bidi =
2669            BidiText::resolve(text, 0..text.len(), BaseDirection::Auto, &mut bidi_output).unwrap();
2670        let mut logical_output = [LogicalRun::empty(); 1];
2671        let logical = LogicalRuns::resolve(text, &bidi, &typefaces, &mut logical_output).unwrap();
2672        let mut glyphs = [ShapedGlyph::default(); 1];
2673        let mut runs = [GlyphRun::empty(); 1];
2674
2675        assert_eq!(
2676            logical
2677                .shape_into(text, &typefaces, &[], &mut glyphs, &mut runs)
2678                .err()
2679                .unwrap(),
2680            LayoutError::InvalidTypefaceOutput { run: 0 }
2681        );
2682    }
2683
2684    #[test]
2685    fn reorders_mixed_runs_for_rtl_lines() {
2686        let text = "אבג abc";
2687        let primary = SimpleTypeface::new(&Source {
2688            key: 1,
2689            ascii: false,
2690        });
2691        let fallback = SimpleTypeface::new(&Source {
2692            key: 2,
2693            ascii: true,
2694        });
2695        let typefaces: [&dyn Typeface; 2] = [&primary, &fallback];
2696        let mut bidi_output = bidi_slots::<4>();
2697        let bidi = BidiText::resolve(
2698            text,
2699            0..text.len(),
2700            BaseDirection::RightToLeft,
2701            &mut bidi_output,
2702        )
2703        .unwrap();
2704        let mut logical_output = [LogicalRun::empty(); 4];
2705        let logical = LogicalRuns::resolve(text, &bidi, &typefaces, &mut logical_output).unwrap();
2706        let mut initial_glyphs = [ShapedGlyph::default(); 7];
2707        let mut initial_runs = [GlyphRun::empty(); 4];
2708        let shaped = logical
2709            .shape_into(
2710                text,
2711                &typefaces,
2712                &[],
2713                &mut initial_glyphs,
2714                &mut initial_runs,
2715            )
2716            .unwrap();
2717        let mut broken_output = [BrokenLine::empty(); 1];
2718        let broken = shaped
2719            .break_into(
2720                text,
2721                100,
2722                WrapMode::Word,
2723                TextSpacing::default(),
2724                &mut broken_output,
2725            )
2726            .unwrap();
2727        let mut scratch = [ShapedGlyph::default(); 3];
2728        let mut glyphs = [PositionedGlyph::default(); 7];
2729        let mut runs = [VisualRun::empty(); 4];
2730        let mut lines = [LayoutLine::empty(); 1];
2731        let mut carets = [CaretStop::default(); 12];
2732        let layout = logical
2733            .layout_into(
2734                text,
2735                &typefaces,
2736                &[],
2737                &broken,
2738                LayoutOptions::new(10),
2739                LayoutBuffers::new(
2740                    &mut scratch,
2741                    &mut glyphs,
2742                    &mut runs,
2743                    &mut lines,
2744                    &mut carets,
2745                ),
2746            )
2747            .unwrap();
2748
2749        let first = layout.runs()[0].text();
2750        assert_eq!(&text[first.start as usize..first.end as usize], "abc");
2751        assert_eq!(layout.runs()[0].bidi_level(), 2);
2752    }
2753}