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