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