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