Skip to main content

textflow/
layout.rs

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