Skip to main content

textflow/
layout.rs

1use crate::bidi::BidiText;
2use crate::shaping::{
3    CaretStop, FlowPoint, FontAccessError, FontFeature, FontId, LineEdges, PositionError,
4    PositionedGlyph, ShapeError, ShapeRequest, ShapedGlyph, ShapedRun, TextRange, Typeface,
5};
6use crate::unicode::{graphemes, line_breaks, script_runs, LineBreakKind, LineBreaks, Script};
7use core::iter::Peekable;
8
9use crate::buffer::SliceWriter;
10
11#[derive(Clone, Copy, Debug, Eq, PartialEq)]
12pub struct LogicalRun {
13    text: TextRange,
14    typeface: u16,
15    script: Script,
16    bidi_level: u8,
17}
18
19impl LogicalRun {
20    pub const fn empty() -> Self {
21        Self {
22            text: TextRange::new(0, 0),
23            typeface: 0,
24            script: Script::Common,
25            bidi_level: 0,
26        }
27    }
28
29    pub const fn text(self) -> TextRange {
30        self.text
31    }
32
33    pub const fn typeface_index(self) -> usize {
34        self.typeface as usize
35    }
36
37    pub const fn script(self) -> Script {
38        self.script
39    }
40
41    pub const fn bidi_level(self) -> u8 {
42        self.bidi_level
43    }
44}
45
46#[derive(Clone, Copy, Debug, Eq, PartialEq)]
47pub enum LayoutError {
48    NoTypeface,
49    TooManyTypefaces,
50    InsufficientRunCapacity { required: usize },
51    InsufficientGlyphCapacity { minimum: usize },
52    InsufficientLineCapacity { required: usize },
53    InsufficientScratchCapacity { minimum: usize },
54    InsufficientPositionedCapacity { minimum: usize },
55    InsufficientCaretCapacity { minimum: usize },
56    InvalidRun,
57    InvalidTypefaceOutput { run: usize },
58    InvalidWidth,
59    InvalidLineHeight,
60    CoordinateOverflow,
61    Font(FontAccessError),
62    Shape { run: usize, error: ShapeError },
63}
64
65impl From<FontAccessError> for LayoutError {
66    fn from(error: FontAccessError) -> Self {
67        Self::Font(error)
68    }
69}
70
71pub struct LogicalRuns<'a> {
72    text: TextRange,
73    runs: &'a [LogicalRun],
74}
75
76impl<'a> LogicalRuns<'a> {
77    pub fn resolve(
78        text: &str,
79        bidi: &BidiText<'_>,
80        typefaces: &[&dyn Typeface],
81        output: &'a mut [LogicalRun],
82    ) -> Result<Self, LayoutError> {
83        if typefaces.is_empty() {
84            return Err(LayoutError::NoTypeface);
85        }
86        if typefaces.len() > u16::MAX as usize {
87            return Err(LayoutError::TooManyTypefaces);
88        }
89        let paragraph = bidi.text();
90        if paragraph.end > u32::MAX as usize {
91            return Err(LayoutError::InvalidRun);
92        }
93        let mut writer = LogicalRunWriter::new(output);
94        for bidi_run in bidi.logical_runs() {
95            let bidi_start = bidi_run.text.start;
96            let bidi_end = bidi_run.text.end;
97            if bidi_start > bidi_end
98                || bidi_end > text.len()
99                || !text.is_char_boundary(bidi_start)
100                || !text.is_char_boundary(bidi_end)
101            {
102                return Err(LayoutError::InvalidRun);
103            }
104            for script_run in script_runs(&text[bidi_start..bidi_end]) {
105                let script_start = bidi_start + script_run.text.start;
106                let script_end = bidi_start + script_run.text.end;
107                for cluster in graphemes(&text[script_start..script_end]) {
108                    let start = script_start + cluster.range.start;
109                    let end = script_start + cluster.range.end;
110                    let typeface = select_typeface(cluster.text, typefaces)?;
111                    writer.push(LogicalRun {
112                        text: TextRange::new(start as u32, end as u32),
113                        typeface,
114                        script: script_run.script,
115                        bidi_level: bidi_run.level,
116                    });
117                }
118            }
119        }
120        let runs = writer.finish()?;
121        Ok(Self {
122            text: TextRange::new(paragraph.start as u32, paragraph.end as u32),
123            runs,
124        })
125    }
126
127    pub const fn text(&self) -> TextRange {
128        self.text
129    }
130
131    pub const fn runs(&self) -> &[LogicalRun] {
132        self.runs
133    }
134
135    pub fn shape_into<'output>(
136        &self,
137        text: &str,
138        typefaces: &[&dyn Typeface],
139        features: &[FontFeature],
140        glyphs: &'output mut [ShapedGlyph],
141        runs: &'output mut [GlyphRun],
142    ) -> Result<ShapedText<'output>, LayoutError> {
143        if runs.len() < self.runs.len() {
144            return Err(LayoutError::InsufficientRunCapacity {
145                required: self.runs.len(),
146            });
147        }
148        let mut glyph_count = 0;
149        for (run_index, logical) in self.runs.iter().enumerate() {
150            let Some(typeface) = typefaces.get(logical.typeface_index()) else {
151                return Err(LayoutError::InvalidRun);
152            };
153            let range = logical.text.start as usize..logical.text.end as usize;
154            let request = ShapeRequest::new(
155                text,
156                range,
157                crate::bidi::Direction::from_level(logical.bidi_level),
158                logical.script,
159            )
160            .with_features(features);
161            let count = match typeface.shape_into(&request, &mut glyphs[glyph_count..]) {
162                Ok(count) => count,
163                Err(ShapeError::InsufficientCapacity { required }) => {
164                    return Err(LayoutError::InsufficientGlyphCapacity {
165                        minimum: glyph_count.saturating_add(required),
166                    });
167                }
168                Err(error) => {
169                    return Err(LayoutError::Shape {
170                        run: run_index,
171                        error,
172                    });
173                }
174            };
175            let end = glyph_count
176                .checked_add(count)
177                .ok_or(LayoutError::InvalidRun)?;
178            if end > glyphs.len()
179                || end > u32::MAX as usize
180                || !valid_shaped_output(&request, &glyphs[glyph_count..end])
181            {
182                return Err(LayoutError::InvalidTypefaceOutput { run: run_index });
183            }
184            runs[run_index] = GlyphRun {
185                text: logical.text,
186                glyphs: TextRange::new(glyph_count as u32, end as u32),
187                font_id: typeface.id(),
188                bidi_level: logical.bidi_level,
189            };
190            glyph_count = end;
191        }
192        Ok(ShapedText {
193            text: self.text,
194            glyphs: &glyphs[..glyph_count],
195            runs: &runs[..self.runs.len()],
196        })
197    }
198
199    pub fn layout_into<'output>(
200        &self,
201        text: &str,
202        typefaces: &[&dyn Typeface],
203        features: &[FontFeature],
204        broken: &BrokenLines<'_>,
205        options: LayoutOptions,
206        buffers: LayoutBuffers<'output>,
207    ) -> Result<ParagraphLayout<'output>, LayoutError> {
208        ParagraphBuilder::new(options, buffers).layout(
209            LayoutInput {
210                text,
211                typefaces,
212                features,
213                logical: self.runs,
214            },
215            broken,
216        )
217    }
218}
219
220#[derive(Clone, Copy)]
221struct LayoutInput<'a, 'face> {
222    text: &'a str,
223    typefaces: &'a [&'face dyn Typeface],
224    features: &'a [FontFeature],
225    logical: &'a [LogicalRun],
226}
227
228struct ParagraphBuilder<'a> {
229    options: LayoutOptions,
230    buffers: LayoutBuffers<'a>,
231    run_count: usize,
232    glyph_count: usize,
233    caret_count: usize,
234}
235
236impl<'output> ParagraphBuilder<'output> {
237    fn new(options: LayoutOptions, buffers: LayoutBuffers<'output>) -> Self {
238        Self {
239            options,
240            buffers,
241            run_count: 0,
242            glyph_count: 0,
243            caret_count: 0,
244        }
245    }
246
247    fn layout(
248        mut self,
249        input: LayoutInput<'_, '_>,
250        broken: &BrokenLines<'_>,
251    ) -> Result<ParagraphLayout<'output>, LayoutError> {
252        self.preflight(input.logical, broken)?;
253        for (line_index, broken_line) in broken.lines.iter().enumerate() {
254            self.push_line(input, line_index, *broken_line)?;
255        }
256        Ok(self.finish(broken.lines.len()))
257    }
258
259    fn preflight(
260        &self,
261        logical: &[LogicalRun],
262        broken: &BrokenLines<'_>,
263    ) -> Result<(), LayoutError> {
264        if self.options.line_height < 0 {
265            return Err(LayoutError::InvalidLineHeight);
266        }
267        if self.buffers.lines.len() < broken.lines.len() {
268            return Err(LayoutError::InsufficientLineCapacity {
269                required: broken.lines.len(),
270            });
271        }
272        let required_runs = broken.lines.iter().try_fold(0usize, |count, line| {
273            let line_runs = logical
274                .iter()
275                .filter(|run| intersection(run.text, line.text).is_some())
276                .count();
277            count
278                .checked_add(line_runs)
279                .ok_or(LayoutError::CoordinateOverflow)
280        })?;
281        if required_runs > u32::MAX as usize || broken.lines.len() > u32::MAX as usize {
282            return Err(LayoutError::CoordinateOverflow);
283        }
284        if self.buffers.runs.len() < required_runs {
285            return Err(LayoutError::InsufficientRunCapacity {
286                required: required_runs,
287            });
288        }
289        Ok(())
290    }
291
292    fn push_line(
293        &mut self,
294        input: LayoutInput<'_, '_>,
295        line_index: usize,
296        broken: BrokenLine,
297    ) -> Result<(), LayoutError> {
298        let line_run_start = self.run_count;
299        self.append_visual_runs(input.logical, input.typefaces, broken)?;
300        reorder_visual_runs(&mut self.buffers.runs[line_run_start..self.run_count]);
301
302        let origin = self.line_origin(line_index)?;
303        let line_glyph_start = self.glyph_count;
304        let line_caret_start = self.caret_count;
305        let mut pen = origin;
306        for run_index in line_run_start..self.run_count {
307            pen = self.shape_run(input, run_index, broken, pen)?;
308        }
309        let advance = pen
310            .x
311            .checked_sub(origin.x)
312            .ok_or(LayoutError::CoordinateOverflow)?;
313        self.buffers.lines[line_index] = LayoutLine {
314            text: broken.text,
315            runs: TextRange::new(line_run_start as u32, self.run_count as u32),
316            glyphs: TextRange::new(line_glyph_start as u32, self.glyph_count as u32),
317            carets: TextRange::new(line_caret_start as u32, self.caret_count as u32),
318            origin,
319            advance,
320        };
321        Ok(())
322    }
323
324    fn append_visual_runs(
325        &mut self,
326        logical: &[LogicalRun],
327        typefaces: &[&dyn Typeface],
328        broken: BrokenLine,
329    ) -> Result<(), LayoutError> {
330        for logical in logical {
331            let Some(text) = intersection(logical.text, broken.text) else {
332                continue;
333            };
334            let Some(typeface) = typefaces.get(logical.typeface_index()) else {
335                return Err(LayoutError::InvalidRun);
336            };
337            self.buffers.runs[self.run_count] = VisualRun {
338                text,
339                glyphs: TextRange::new(0, 0),
340                font_id: typeface.id(),
341                typeface_index: logical.typeface,
342                script: logical.script,
343                bidi_level: logical.bidi_level,
344            };
345            self.run_count += 1;
346        }
347        Ok(())
348    }
349
350    fn line_origin(&self, line_index: usize) -> Result<FlowPoint, LayoutError> {
351        let line = i32::try_from(line_index).map_err(|_| LayoutError::CoordinateOverflow)?;
352        let y = self
353            .options
354            .line_height
355            .checked_mul(line)
356            .and_then(|offset| self.options.origin.y.checked_add(offset))
357            .ok_or(LayoutError::CoordinateOverflow)?;
358        Ok(FlowPoint {
359            x: self.options.origin.x,
360            y,
361        })
362    }
363
364    fn shape_run(
365        &mut self,
366        input: LayoutInput<'_, '_>,
367        run_index: usize,
368        line: BrokenLine,
369        origin: FlowPoint,
370    ) -> Result<FlowPoint, LayoutError> {
371        let mut visual = self.buffers.runs[run_index];
372        let Some(typeface) = input.typefaces.get(visual.typeface_index as usize) else {
373            return Err(LayoutError::InvalidRun);
374        };
375        let request = ShapeRequest::new(
376            input.text,
377            visual.text.start as usize..visual.text.end as usize,
378            crate::bidi::Direction::from_level(visual.bidi_level),
379            visual.script,
380        )
381        .with_features(input.features)
382        .with_line_edges(line_edges(visual.text, line.text));
383        let count = match typeface.shape_into(&request, self.buffers.scratch) {
384            Ok(count) => count,
385            Err(ShapeError::InsufficientCapacity { required }) => {
386                return Err(LayoutError::InsufficientScratchCapacity { minimum: required });
387            }
388            Err(error) => {
389                return Err(LayoutError::Shape {
390                    run: run_index,
391                    error,
392                });
393            }
394        };
395        if count > self.buffers.scratch.len()
396            || !valid_shaped_output(&request, &self.buffers.scratch[..count])
397        {
398            return Err(LayoutError::InvalidTypefaceOutput { run: run_index });
399        }
400        let glyph_end = self
401            .glyph_count
402            .checked_add(count)
403            .ok_or(LayoutError::CoordinateOverflow)?;
404        if glyph_end > u32::MAX as usize {
405            return Err(LayoutError::CoordinateOverflow);
406        }
407        if glyph_end > self.buffers.glyphs.len() {
408            return Err(LayoutError::InsufficientPositionedCapacity { minimum: glyph_end });
409        }
410        let shaped = ShapedRun::new(
411            visual.font_id,
412            visual.text,
413            visual.bidi_level,
414            &self.buffers.scratch[..count],
415        );
416        let positioned = shaped
417            .position_into(
418                origin,
419                &mut self.buffers.glyphs[self.glyph_count..glyph_end],
420            )
421            .map_err(|error| position_error(error, self.glyph_count))?;
422        let end = positioned.end();
423        let carets = positioned
424            .carets_into(&mut self.buffers.carets[self.caret_count..])
425            .map_err(|error| caret_error(error, self.caret_count))?;
426        self.caret_count = self
427            .caret_count
428            .checked_add(carets.len())
429            .ok_or(LayoutError::CoordinateOverflow)?;
430        if self.caret_count > u32::MAX as usize {
431            return Err(LayoutError::CoordinateOverflow);
432        }
433        visual.glyphs = TextRange::new(self.glyph_count as u32, glyph_end as u32);
434        self.buffers.runs[run_index] = visual;
435        self.glyph_count = glyph_end;
436        Ok(end)
437    }
438
439    fn finish(self, line_count: usize) -> ParagraphLayout<'output> {
440        ParagraphLayout {
441            lines: &self.buffers.lines[..line_count],
442            runs: &self.buffers.runs[..self.run_count],
443            glyphs: &self.buffers.glyphs[..self.glyph_count],
444            carets: &self.buffers.carets[..self.caret_count],
445        }
446    }
447}
448
449fn line_edges(run: TextRange, line: TextRange) -> LineEdges {
450    match (run.start == line.start, run.end == line.end) {
451        (true, true) => LineEdges::BOTH,
452        (true, false) => LineEdges::START,
453        (false, true) => LineEdges::END,
454        (false, false) => LineEdges::NONE,
455    }
456}
457
458struct LogicalRunWriter<'a> {
459    output: SliceWriter<'a, LogicalRun>,
460    last: Option<LogicalRun>,
461}
462
463impl<'a> LogicalRunWriter<'a> {
464    fn new(output: &'a mut [LogicalRun]) -> Self {
465        Self {
466            output: SliceWriter::new(output),
467            last: None,
468        }
469    }
470
471    fn push(&mut self, run: LogicalRun) {
472        if let Some(previous) = self.last.as_mut() {
473            if previous.text.end == run.text.start
474                && previous.typeface == run.typeface
475                && previous.script == run.script
476                && previous.bidi_level == run.bidi_level
477            {
478                previous.text.end = run.text.end;
479                if let Some(stored) = self.output.last_mut() {
480                    stored.text.end = run.text.end;
481                }
482                return;
483            }
484        }
485        self.output.push(run);
486        self.last = Some(run);
487    }
488
489    fn finish(self) -> Result<&'a [LogicalRun], LayoutError> {
490        self.output
491            .finish()
492            .map_err(|required| LayoutError::InsufficientRunCapacity { required })
493    }
494}
495
496fn select_typeface(grapheme: &str, typefaces: &[&dyn Typeface]) -> Result<u16, FontAccessError> {
497    for (index, typeface) in typefaces.iter().enumerate() {
498        if typeface.covers(grapheme)? {
499            return Ok(index as u16);
500        }
501    }
502    Ok(0)
503}
504
505#[derive(Clone, Copy, Debug, Eq, PartialEq)]
506pub struct GlyphRun {
507    text: TextRange,
508    glyphs: TextRange,
509    font_id: FontId,
510    bidi_level: u8,
511}
512
513impl GlyphRun {
514    pub const fn empty() -> Self {
515        Self {
516            text: TextRange::new(0, 0),
517            glyphs: TextRange::new(0, 0),
518            font_id: FontId::new(0),
519            bidi_level: 0,
520        }
521    }
522
523    pub const fn text(self) -> TextRange {
524        self.text
525    }
526
527    pub const fn glyphs(self) -> TextRange {
528        self.glyphs
529    }
530
531    pub const fn font_id(self) -> FontId {
532        self.font_id
533    }
534
535    pub const fn bidi_level(self) -> u8 {
536        self.bidi_level
537    }
538}
539
540pub struct ShapedText<'a> {
541    text: TextRange,
542    glyphs: &'a [ShapedGlyph],
543    runs: &'a [GlyphRun],
544}
545
546impl ShapedText<'_> {
547    pub const fn text(&self) -> TextRange {
548        self.text
549    }
550
551    pub const fn glyphs(&self) -> &[ShapedGlyph] {
552        self.glyphs
553    }
554
555    pub const fn runs(&self) -> &[GlyphRun] {
556        self.runs
557    }
558
559    pub fn run(&self, index: usize) -> Option<ShapedRun<'_>> {
560        let run = *self.runs.get(index)?;
561        let glyphs = self
562            .glyphs
563            .get(run.glyphs.start as usize..run.glyphs.end as usize)?;
564        Some(ShapedRun::new(
565            run.font_id,
566            run.text,
567            run.bidi_level,
568            glyphs,
569        ))
570    }
571
572    pub fn is_safe_break(&self, offset: u32) -> bool {
573        if offset == self.text.start || offset == self.text.end {
574            return true;
575        }
576        if offset < self.text.start || offset > self.text.end {
577            return false;
578        }
579        !self.glyphs.iter().any(|glyph| {
580            glyph.cluster.start < offset && offset < glyph.cluster.end
581                || glyph.cluster.start == offset && glyph.unsafe_to_break()
582        })
583    }
584
585    pub fn break_into<'output>(
586        &self,
587        text: &str,
588        max_width: i32,
589        output: &'output mut [BrokenLine],
590    ) -> Result<BrokenLines<'output>, LayoutError> {
591        if max_width < 0 {
592            return Err(LayoutError::InvalidWidth);
593        }
594        let start = self.text.start as usize;
595        let end = self.text.end as usize;
596        if start > end
597            || end > text.len()
598            || !text.is_char_boundary(start)
599            || !text.is_char_boundary(end)
600        {
601            return Err(LayoutError::InvalidRun);
602        }
603        let breaks = line_breaks(&text[start..end]).peekable();
604        let mut breaker = LineBreaker::new(self, self.text, max_width, breaks, output);
605        let mut glyphs = LogicalGlyphs::new(self).peekable();
606        while let Some(first) = glyphs.next() {
607            let cluster = first.cluster;
608            let mut advance = first.advance.x;
609            while let Some(next) = glyphs.peek() {
610                if next.cluster != cluster {
611                    break;
612                }
613                advance = advance
614                    .checked_add(next.advance.x)
615                    .ok_or(LayoutError::CoordinateOverflow)?;
616                glyphs.next();
617            }
618            breaker.add_cluster(cluster, advance)?;
619        }
620        breaker.finish()
621    }
622}
623
624struct LogicalGlyphs<'a> {
625    shaped: &'a ShapedText<'a>,
626    run: usize,
627    glyph: usize,
628}
629
630impl<'a> LogicalGlyphs<'a> {
631    fn new(shaped: &'a ShapedText<'a>) -> Self {
632        Self {
633            shaped,
634            run: 0,
635            glyph: 0,
636        }
637    }
638}
639
640impl<'a> Iterator for LogicalGlyphs<'a> {
641    type Item = &'a ShapedGlyph;
642
643    fn next(&mut self) -> Option<Self::Item> {
644        loop {
645            let run = self.shaped.runs.get(self.run)?;
646            let start = run.glyphs.start as usize;
647            let end = run.glyphs.end as usize;
648            if self.glyph < end.saturating_sub(start) {
649                let index = if run.bidi_level & 1 == 0 {
650                    start + self.glyph
651                } else {
652                    end - self.glyph - 1
653                };
654                self.glyph += 1;
655                return self.shaped.glyphs.get(index);
656            }
657            self.run += 1;
658            self.glyph = 0;
659        }
660    }
661}
662
663#[derive(Clone, Copy, Debug, Default, Eq, PartialEq)]
664pub struct BrokenLine {
665    text: TextRange,
666    advance: i32,
667}
668
669impl BrokenLine {
670    pub const fn empty() -> Self {
671        Self {
672            text: TextRange::new(0, 0),
673            advance: 0,
674        }
675    }
676
677    pub const fn text(self) -> TextRange {
678        self.text
679    }
680
681    pub const fn advance(self) -> i32 {
682        self.advance
683    }
684}
685
686pub struct BrokenLines<'a> {
687    lines: &'a [BrokenLine],
688}
689
690impl BrokenLines<'_> {
691    pub const fn lines(&self) -> &[BrokenLine] {
692        self.lines
693    }
694}
695
696struct LineBreaker<'shaped, 'glyphs, 'text, 'output> {
697    shaped: &'shaped ShapedText<'glyphs>,
698    paragraph: TextRange,
699    max_width: i32,
700    breaks: Peekable<LineBreaks<'text>>,
701    writer: LineWriter<'output>,
702    line_start: u32,
703    width: i32,
704    last_allowed: Option<(u32, i32)>,
705}
706
707impl<'shaped, 'glyphs, 'text, 'output> LineBreaker<'shaped, 'glyphs, 'text, 'output> {
708    fn new(
709        shaped: &'shaped ShapedText<'glyphs>,
710        paragraph: TextRange,
711        max_width: i32,
712        breaks: Peekable<LineBreaks<'text>>,
713        output: &'output mut [BrokenLine],
714    ) -> Self {
715        Self {
716            shaped,
717            paragraph,
718            max_width,
719            breaks,
720            writer: LineWriter::new(output),
721            line_start: paragraph.start,
722            width: 0,
723            last_allowed: None,
724        }
725    }
726
727    fn add_cluster(&mut self, cluster: TextRange, advance: i32) -> Result<(), LayoutError> {
728        self.take_breaks_through(cluster.start)?;
729        let width_before = self.width;
730        self.width = self
731            .width
732            .checked_add(advance)
733            .ok_or(LayoutError::CoordinateOverflow)?;
734        if self.width > self.max_width {
735            if let Some((offset, width)) = self.last_allowed.take() {
736                self.emit(offset, width)?;
737            } else if width_before > 0
738                && cluster.start > self.line_start
739                && self.shaped.is_safe_break(cluster.start)
740            {
741                self.emit(cluster.start, width_before)?;
742            } else if self.line_start == cluster.start && self.shaped.is_safe_break(cluster.end) {
743                self.emit(cluster.end, self.width)?;
744            }
745        }
746        self.take_breaks_through(cluster.end)
747    }
748
749    fn take_breaks_through(&mut self, offset: u32) -> Result<(), LayoutError> {
750        while self
751            .breaks
752            .peek()
753            .is_some_and(|next| self.paragraph.start as usize + next.offset <= offset as usize)
754        {
755            let next = self.breaks.next().unwrap();
756            let global = self.paragraph.start + next.offset as u32;
757            if global <= self.line_start || !self.shaped.is_safe_break(global) {
758                continue;
759            }
760            match next.kind {
761                LineBreakKind::Mandatory => self.emit(global, self.width)?,
762                LineBreakKind::Allowed if self.width > self.max_width => {
763                    self.emit(global, self.width)?;
764                }
765                LineBreakKind::Allowed => self.last_allowed = Some((global, self.width)),
766            }
767        }
768        Ok(())
769    }
770
771    fn emit(&mut self, end: u32, advance: i32) -> Result<(), LayoutError> {
772        if end <= self.line_start {
773            return Ok(());
774        }
775        self.writer.push(BrokenLine {
776            text: TextRange::new(self.line_start, end),
777            advance,
778        });
779        self.line_start = end;
780        self.width = self
781            .width
782            .checked_sub(advance)
783            .ok_or(LayoutError::CoordinateOverflow)?;
784        self.last_allowed = None;
785        Ok(())
786    }
787
788    fn finish(mut self) -> Result<BrokenLines<'output>, LayoutError> {
789        self.take_breaks_through(self.paragraph.end)?;
790        if self.line_start < self.paragraph.end {
791            self.emit(self.paragraph.end, self.width)?;
792        }
793        let lines = self.writer.finish()?;
794        Ok(BrokenLines { lines })
795    }
796}
797
798struct LineWriter<'a> {
799    output: SliceWriter<'a, BrokenLine>,
800}
801
802impl<'a> LineWriter<'a> {
803    fn new(output: &'a mut [BrokenLine]) -> Self {
804        Self {
805            output: SliceWriter::new(output),
806        }
807    }
808
809    fn push(&mut self, line: BrokenLine) {
810        self.output.push(line);
811    }
812
813    fn finish(self) -> Result<&'a [BrokenLine], LayoutError> {
814        self.output
815            .finish()
816            .map_err(|required| LayoutError::InsufficientLineCapacity { required })
817    }
818}
819
820#[derive(Clone, Copy, Debug, Default, Eq, PartialEq)]
821pub struct LayoutOptions {
822    pub origin: FlowPoint,
823    pub line_height: i32,
824}
825
826impl LayoutOptions {
827    pub const fn new(line_height: i32) -> Self {
828        Self {
829            origin: FlowPoint { x: 0, y: 0 },
830            line_height,
831        }
832    }
833
834    pub const fn with_origin(mut self, origin: FlowPoint) -> Self {
835        self.origin = origin;
836        self
837    }
838}
839
840pub struct LayoutBuffers<'a> {
841    pub scratch: &'a mut [ShapedGlyph],
842    pub glyphs: &'a mut [PositionedGlyph],
843    pub runs: &'a mut [VisualRun],
844    pub lines: &'a mut [LayoutLine],
845    pub carets: &'a mut [CaretStop],
846}
847
848impl<'a> LayoutBuffers<'a> {
849    pub fn new(
850        scratch: &'a mut [ShapedGlyph],
851        glyphs: &'a mut [PositionedGlyph],
852        runs: &'a mut [VisualRun],
853        lines: &'a mut [LayoutLine],
854        carets: &'a mut [CaretStop],
855    ) -> Self {
856        Self {
857            scratch,
858            glyphs,
859            runs,
860            lines,
861            carets,
862        }
863    }
864}
865
866#[derive(Clone, Copy, Debug, Eq, PartialEq)]
867pub struct VisualRun {
868    text: TextRange,
869    glyphs: TextRange,
870    font_id: FontId,
871    typeface_index: u16,
872    script: Script,
873    bidi_level: u8,
874}
875
876impl VisualRun {
877    pub const fn empty() -> Self {
878        Self {
879            text: TextRange::new(0, 0),
880            glyphs: TextRange::new(0, 0),
881            font_id: FontId::new(0),
882            typeface_index: 0,
883            script: Script::Common,
884            bidi_level: 0,
885        }
886    }
887
888    pub const fn text(self) -> TextRange {
889        self.text
890    }
891
892    pub const fn glyphs(self) -> TextRange {
893        self.glyphs
894    }
895
896    pub const fn font_id(self) -> FontId {
897        self.font_id
898    }
899
900    pub const fn bidi_level(self) -> u8 {
901        self.bidi_level
902    }
903}
904
905#[derive(Clone, Copy, Debug, Default, Eq, PartialEq)]
906pub struct LayoutLine {
907    text: TextRange,
908    runs: TextRange,
909    glyphs: TextRange,
910    carets: TextRange,
911    origin: FlowPoint,
912    advance: i32,
913}
914
915impl LayoutLine {
916    pub const fn empty() -> Self {
917        Self {
918            text: TextRange::new(0, 0),
919            runs: TextRange::new(0, 0),
920            glyphs: TextRange::new(0, 0),
921            carets: TextRange::new(0, 0),
922            origin: FlowPoint { x: 0, y: 0 },
923            advance: 0,
924        }
925    }
926
927    pub const fn text(self) -> TextRange {
928        self.text
929    }
930
931    pub const fn runs(self) -> TextRange {
932        self.runs
933    }
934
935    pub const fn glyphs(self) -> TextRange {
936        self.glyphs
937    }
938
939    pub const fn carets(self) -> TextRange {
940        self.carets
941    }
942
943    pub const fn origin(self) -> FlowPoint {
944        self.origin
945    }
946
947    pub const fn advance(self) -> i32 {
948        self.advance
949    }
950}
951
952pub struct ParagraphLayout<'a> {
953    lines: &'a [LayoutLine],
954    runs: &'a [VisualRun],
955    glyphs: &'a [PositionedGlyph],
956    carets: &'a [CaretStop],
957}
958
959impl ParagraphLayout<'_> {
960    pub const fn lines(&self) -> &[LayoutLine] {
961        self.lines
962    }
963
964    pub const fn runs(&self) -> &[VisualRun] {
965        self.runs
966    }
967
968    pub const fn glyphs(&self) -> &[PositionedGlyph] {
969        self.glyphs
970    }
971
972    pub const fn carets(&self) -> &[CaretStop] {
973        self.carets
974    }
975}
976
977fn intersection(left: TextRange, right: TextRange) -> Option<TextRange> {
978    let start = left.start.max(right.start);
979    let end = left.end.min(right.end);
980    (start < end).then_some(TextRange::new(start, end))
981}
982
983fn valid_shaped_output(request: &ShapeRequest<'_>, glyphs: &[ShapedGlyph]) -> bool {
984    let mut previous = None;
985    glyphs.iter().all(|glyph| {
986        let start = glyph.cluster.start as usize;
987        let end = glyph.cluster.end as usize;
988        let ordered = match (request.direction, previous) {
989            (_, None) => true,
990            (crate::bidi::Direction::LeftToRight, Some(previous)) => {
991                glyph.cluster.start >= previous
992            }
993            (crate::bidi::Direction::RightToLeft, Some(previous)) => {
994                glyph.cluster.start <= previous
995            }
996        };
997        previous = Some(glyph.cluster.start);
998        start < end
999            && start >= request.range.start
1000            && end <= request.range.end
1001            && request.text.is_char_boundary(start)
1002            && request.text.is_char_boundary(end)
1003            && ordered
1004    })
1005}
1006
1007fn reorder_visual_runs(runs: &mut [VisualRun]) {
1008    let max_level = runs.iter().map(|run| run.bidi_level).max().unwrap_or(0);
1009    let min_odd = runs
1010        .iter()
1011        .filter(|run| run.bidi_level & 1 == 1)
1012        .map(|run| run.bidi_level)
1013        .min();
1014    let Some(min_odd) = min_odd else {
1015        return;
1016    };
1017    for level in (min_odd..=max_level).rev() {
1018        let mut start = 0;
1019        while start < runs.len() {
1020            if runs[start].bidi_level < level {
1021                start += 1;
1022                continue;
1023            }
1024            let mut end = start + 1;
1025            while end < runs.len() && runs[end].bidi_level >= level {
1026                end += 1;
1027            }
1028            runs[start..end].reverse();
1029            start = end;
1030        }
1031    }
1032}
1033
1034fn position_error(error: PositionError, current: usize) -> LayoutError {
1035    match error {
1036        PositionError::InsufficientCapacity { required } => {
1037            LayoutError::InsufficientPositionedCapacity {
1038                minimum: current.saturating_add(required),
1039            }
1040        }
1041        PositionError::CoordinateOverflow => LayoutError::CoordinateOverflow,
1042    }
1043}
1044
1045fn caret_error(error: PositionError, current: usize) -> LayoutError {
1046    match error {
1047        PositionError::InsufficientCapacity { required } => {
1048            LayoutError::InsufficientCaretCapacity {
1049                minimum: current.saturating_add(required),
1050            }
1051        }
1052        PositionError::CoordinateOverflow => LayoutError::CoordinateOverflow,
1053    }
1054}
1055
1056#[cfg(test)]
1057mod tests {
1058    use super::*;
1059    use crate::bidi::{BaseDirection, BidiRun};
1060    use crate::shaping::{FlowPoint, FontId, FontMetrics, GlyphId, GlyphSource, SimpleTypeface};
1061    use std::prelude::v1::*;
1062
1063    struct Source {
1064        key: u64,
1065        ascii: bool,
1066    }
1067
1068    impl GlyphSource for Source {
1069        fn id(&self) -> FontId {
1070            FontId::new(self.key)
1071        }
1072
1073        fn metrics(&self) -> Result<FontMetrics, FontAccessError> {
1074            Ok(FontMetrics::default())
1075        }
1076
1077        fn glyph_for(&self, character: char) -> Result<Option<GlyphId>, FontAccessError> {
1078            let covered = character.is_ascii() == self.ascii;
1079            Ok(covered.then_some(GlyphId::new(character as u16)))
1080        }
1081
1082        fn glyph_advance(&self, _glyph: GlyphId) -> Result<FlowPoint, FontAccessError> {
1083            Ok(FlowPoint { x: 1, y: 0 })
1084        }
1085    }
1086
1087    struct EdgeTypeface;
1088
1089    impl Typeface for EdgeTypeface {
1090        fn id(&self) -> FontId {
1091            FontId::new(9)
1092        }
1093
1094        fn metrics(&self) -> Result<FontMetrics, FontAccessError> {
1095            Ok(FontMetrics::default())
1096        }
1097
1098        fn covers(&self, _grapheme: &str) -> Result<bool, FontAccessError> {
1099            Ok(true)
1100        }
1101
1102        fn shape_into(
1103            &self,
1104            request: &ShapeRequest<'_>,
1105            output: &mut [ShapedGlyph],
1106        ) -> Result<usize, ShapeError> {
1107            let shaped = &request.text[request.range.clone()];
1108            let required = shaped.chars().count();
1109            if output.len() < required {
1110                return Err(ShapeError::InsufficientCapacity { required });
1111            }
1112            let advance = if request.line_edges.has_start() || request.line_edges.has_end() {
1113                2
1114            } else {
1115                1
1116            };
1117            for (index, (offset, character)) in shaped.char_indices().enumerate() {
1118                let start = request.range.start + offset;
1119                let end = start + character.len_utf8();
1120                output[index] = ShapedGlyph::new(
1121                    GlyphId::new(character as u16),
1122                    TextRange::new(start as u32, end as u32),
1123                );
1124                output[index].advance.x = advance;
1125            }
1126            Ok(required)
1127        }
1128    }
1129
1130    struct InvalidTypeface;
1131
1132    impl Typeface for InvalidTypeface {
1133        fn id(&self) -> FontId {
1134            FontId::new(10)
1135        }
1136
1137        fn metrics(&self) -> Result<FontMetrics, FontAccessError> {
1138            Ok(FontMetrics::default())
1139        }
1140
1141        fn covers(&self, _grapheme: &str) -> Result<bool, FontAccessError> {
1142            Ok(true)
1143        }
1144
1145        fn shape_into(
1146            &self,
1147            _request: &ShapeRequest<'_>,
1148            output: &mut [ShapedGlyph],
1149        ) -> Result<usize, ShapeError> {
1150            Ok(output.len() + 1)
1151        }
1152    }
1153
1154    fn bidi_slots<const N: usize>() -> [BidiRun; N] {
1155        core::array::from_fn(|_| BidiRun::empty())
1156    }
1157
1158    #[test]
1159    fn splits_runs_by_script_and_fallback_face() {
1160        let text = "ab世界cd";
1161        let primary = SimpleTypeface::new(&Source {
1162            key: 1,
1163            ascii: true,
1164        });
1165        let fallback = SimpleTypeface::new(&Source {
1166            key: 2,
1167            ascii: false,
1168        });
1169        let typefaces: [&dyn Typeface; 2] = [&primary, &fallback];
1170        let mut bidi_output = bidi_slots::<4>();
1171        let bidi =
1172            BidiText::resolve(text, 0..text.len(), BaseDirection::Auto, &mut bidi_output).unwrap();
1173        let mut output = [LogicalRun::empty(); 4];
1174        let runs = LogicalRuns::resolve(text, &bidi, &typefaces, &mut output).unwrap();
1175
1176        assert_eq!(runs.runs().len(), 3);
1177        assert_eq!(runs.runs()[0].typeface_index(), 0);
1178        assert_eq!(runs.runs()[1].typeface_index(), 1);
1179        assert_eq!(runs.runs()[1].script(), Script::Han);
1180        assert_eq!(runs.runs()[2].typeface_index(), 0);
1181    }
1182
1183    #[test]
1184    fn shapes_resolved_runs_into_caller_storage() {
1185        let text = "ab世界";
1186        let primary = SimpleTypeface::new(&Source {
1187            key: 1,
1188            ascii: true,
1189        });
1190        let fallback = SimpleTypeface::new(&Source {
1191            key: 2,
1192            ascii: false,
1193        });
1194        let typefaces: [&dyn Typeface; 2] = [&primary, &fallback];
1195        let mut bidi_output = bidi_slots::<4>();
1196        let bidi =
1197            BidiText::resolve(text, 0..text.len(), BaseDirection::Auto, &mut bidi_output).unwrap();
1198        let mut logical_output = [LogicalRun::empty(); 4];
1199        let logical = LogicalRuns::resolve(text, &bidi, &typefaces, &mut logical_output).unwrap();
1200        let mut glyph_output = [ShapedGlyph::default(); 4];
1201        let mut run_output = [GlyphRun::empty(); 4];
1202        let shaped = logical
1203            .shape_into(text, &typefaces, &[], &mut glyph_output, &mut run_output)
1204            .unwrap();
1205
1206        assert_eq!(shaped.glyphs().len(), 4);
1207        assert_eq!(shaped.runs().len(), 2);
1208        assert_eq!(shaped.run(0).unwrap().font_id(), FontId::new(1));
1209        assert_eq!(shaped.run(1).unwrap().font_id(), FontId::new(2));
1210    }
1211
1212    #[test]
1213    fn reports_exact_run_and_minimum_glyph_capacity() {
1214        let text = "abc";
1215        let primary = SimpleTypeface::new(&Source {
1216            key: 1,
1217            ascii: true,
1218        });
1219        let typefaces: [&dyn Typeface; 1] = [&primary];
1220        let mut bidi_output = bidi_slots::<1>();
1221        let bidi =
1222            BidiText::resolve(text, 0..text.len(), BaseDirection::Auto, &mut bidi_output).unwrap();
1223        let mut logical_output = [LogicalRun::empty(); 1];
1224        let logical = LogicalRuns::resolve(text, &bidi, &typefaces, &mut logical_output).unwrap();
1225        let mut glyph_output = [ShapedGlyph::default(); 2];
1226        let mut run_output = [GlyphRun::empty(); 1];
1227
1228        assert_eq!(
1229            logical
1230                .shape_into(text, &typefaces, &[], &mut glyph_output, &mut run_output,)
1231                .err()
1232                .unwrap(),
1233            LayoutError::InsufficientGlyphCapacity { minimum: 3 }
1234        );
1235    }
1236
1237    #[test]
1238    fn run_capacity_is_exact_when_no_slots_are_available() {
1239        let text = "abc";
1240        let primary = SimpleTypeface::new(&Source {
1241            key: 1,
1242            ascii: true,
1243        });
1244        let typefaces: [&dyn Typeface; 1] = [&primary];
1245        let mut bidi_output = bidi_slots::<1>();
1246        let bidi =
1247            BidiText::resolve(text, 0..text.len(), BaseDirection::Auto, &mut bidi_output).unwrap();
1248        let mut output = [];
1249
1250        assert_eq!(
1251            LogicalRuns::resolve(text, &bidi, &typefaces, &mut output)
1252                .err()
1253                .unwrap(),
1254            LayoutError::InsufficientRunCapacity { required: 1 }
1255        );
1256    }
1257
1258    #[test]
1259    fn breaks_at_the_last_allowed_width() {
1260        let text = "ab cd";
1261        let primary = SimpleTypeface::new(&Source {
1262            key: 1,
1263            ascii: true,
1264        });
1265        let typefaces: [&dyn Typeface; 1] = [&primary];
1266        let mut bidi_output = bidi_slots::<1>();
1267        let bidi =
1268            BidiText::resolve(text, 0..text.len(), BaseDirection::Auto, &mut bidi_output).unwrap();
1269        let mut logical_output = [LogicalRun::empty(); 1];
1270        let logical = LogicalRuns::resolve(text, &bidi, &typefaces, &mut logical_output).unwrap();
1271        let mut glyph_output = [ShapedGlyph::default(); 5];
1272        let mut run_output = [GlyphRun::empty(); 1];
1273        let shaped = logical
1274            .shape_into(text, &typefaces, &[], &mut glyph_output, &mut run_output)
1275            .unwrap();
1276        let mut line_output = [BrokenLine::empty(); 2];
1277        let lines = shaped.break_into(text, 3, &mut line_output).unwrap();
1278
1279        assert_eq!(lines.lines().len(), 2);
1280        assert_eq!(lines.lines()[0].text(), TextRange::new(0, 3));
1281        assert_eq!(lines.lines()[0].advance(), 3);
1282        assert_eq!(lines.lines()[1].text(), TextRange::new(3, 5));
1283        assert_eq!(lines.lines()[1].advance(), 2);
1284
1285        let mut no_lines = [];
1286        assert_eq!(
1287            shaped.break_into(text, 3, &mut no_lines).err().unwrap(),
1288            LayoutError::InsufficientLineCapacity { required: 2 }
1289        );
1290    }
1291
1292    #[test]
1293    fn lets_unsafe_sequences_exceed_the_width() {
1294        let text = "ab cd";
1295        let mut glyphs = [ShapedGlyph::default(); 5];
1296        for (index, glyph) in glyphs.iter_mut().enumerate() {
1297            *glyph = ShapedGlyph::new(
1298                GlyphId::new(index as u16),
1299                TextRange::new(index as u32, index as u32 + 1),
1300            );
1301            glyph.advance.x = 1;
1302        }
1303        glyphs[3].set_unsafe_to_break(true);
1304        let runs = [GlyphRun {
1305            text: TextRange::new(0, 5),
1306            glyphs: TextRange::new(0, 5),
1307            font_id: FontId::new(1),
1308            bidi_level: 0,
1309        }];
1310        let shaped = ShapedText {
1311            text: TextRange::new(0, 5),
1312            glyphs: &glyphs,
1313            runs: &runs,
1314        };
1315        let mut line_output = [BrokenLine::empty(); 2];
1316        let lines = shaped.break_into(text, 3, &mut line_output).unwrap();
1317
1318        assert_eq!(lines.lines()[0].text(), TextRange::new(0, 4));
1319        assert_eq!(lines.lines()[0].advance(), 4);
1320        assert_eq!(lines.lines()[1].text(), TextRange::new(4, 5));
1321    }
1322
1323    #[test]
1324    fn reshapes_line_edges_into_visual_outputs() {
1325        let text = "ab cd";
1326        let typefaces: [&dyn Typeface; 1] = [&EdgeTypeface];
1327        let mut bidi_output = bidi_slots::<1>();
1328        let bidi =
1329            BidiText::resolve(text, 0..text.len(), BaseDirection::Auto, &mut bidi_output).unwrap();
1330        let mut logical_output = [LogicalRun::empty(); 1];
1331        let logical = LogicalRuns::resolve(text, &bidi, &typefaces, &mut logical_output).unwrap();
1332        let mut initial_glyphs = [ShapedGlyph::default(); 5];
1333        let mut initial_runs = [GlyphRun::empty(); 1];
1334        let shaped = logical
1335            .shape_into(
1336                text,
1337                &typefaces,
1338                &[],
1339                &mut initial_glyphs,
1340                &mut initial_runs,
1341            )
1342            .unwrap();
1343        let mut broken_output = [BrokenLine::empty(); 2];
1344        let broken = shaped.break_into(text, 3, &mut broken_output).unwrap();
1345        let mut scratch = [ShapedGlyph::default(); 3];
1346        let mut glyphs = [PositionedGlyph::default(); 5];
1347        let mut runs = [VisualRun::empty(); 2];
1348        let mut lines = [LayoutLine::empty(); 2];
1349        let mut carets = [CaretStop::default(); 7];
1350        let layout = logical
1351            .layout_into(
1352                text,
1353                &typefaces,
1354                &[],
1355                &broken,
1356                LayoutOptions::new(10).with_origin(FlowPoint { x: 5, y: 7 }),
1357                LayoutBuffers::new(
1358                    &mut scratch,
1359                    &mut glyphs,
1360                    &mut runs,
1361                    &mut lines,
1362                    &mut carets,
1363                ),
1364            )
1365            .unwrap();
1366
1367        assert_eq!(layout.lines().len(), 2);
1368        assert_eq!(layout.lines()[0].advance(), 6);
1369        assert_eq!(layout.lines()[1].advance(), 4);
1370        assert_eq!(layout.lines()[0].origin(), FlowPoint { x: 5, y: 7 });
1371        assert_eq!(layout.lines()[1].origin(), FlowPoint { x: 5, y: 17 });
1372        assert_eq!(layout.runs().len(), 2);
1373        assert_eq!(layout.runs()[0].font_id(), FontId::new(9));
1374        assert_eq!(layout.glyphs().len(), 5);
1375        assert_eq!(layout.carets().len(), 7);
1376    }
1377
1378    #[test]
1379    fn rejects_invalid_typeface_output_counts() {
1380        let text = "a";
1381        let typefaces: [&dyn Typeface; 1] = [&InvalidTypeface];
1382        let mut bidi_output = bidi_slots::<1>();
1383        let bidi =
1384            BidiText::resolve(text, 0..text.len(), BaseDirection::Auto, &mut bidi_output).unwrap();
1385        let mut logical_output = [LogicalRun::empty(); 1];
1386        let logical = LogicalRuns::resolve(text, &bidi, &typefaces, &mut logical_output).unwrap();
1387        let mut glyphs = [ShapedGlyph::default(); 1];
1388        let mut runs = [GlyphRun::empty(); 1];
1389
1390        assert_eq!(
1391            logical
1392                .shape_into(text, &typefaces, &[], &mut glyphs, &mut runs)
1393                .err()
1394                .unwrap(),
1395            LayoutError::InvalidTypefaceOutput { run: 0 }
1396        );
1397    }
1398
1399    #[test]
1400    fn reorders_mixed_runs_for_rtl_lines() {
1401        let text = "אבג abc";
1402        let primary = SimpleTypeface::new(&Source {
1403            key: 1,
1404            ascii: false,
1405        });
1406        let fallback = SimpleTypeface::new(&Source {
1407            key: 2,
1408            ascii: true,
1409        });
1410        let typefaces: [&dyn Typeface; 2] = [&primary, &fallback];
1411        let mut bidi_output = bidi_slots::<4>();
1412        let bidi = BidiText::resolve(
1413            text,
1414            0..text.len(),
1415            BaseDirection::RightToLeft,
1416            &mut bidi_output,
1417        )
1418        .unwrap();
1419        let mut logical_output = [LogicalRun::empty(); 4];
1420        let logical = LogicalRuns::resolve(text, &bidi, &typefaces, &mut logical_output).unwrap();
1421        let mut initial_glyphs = [ShapedGlyph::default(); 7];
1422        let mut initial_runs = [GlyphRun::empty(); 4];
1423        let shaped = logical
1424            .shape_into(
1425                text,
1426                &typefaces,
1427                &[],
1428                &mut initial_glyphs,
1429                &mut initial_runs,
1430            )
1431            .unwrap();
1432        let mut broken_output = [BrokenLine::empty(); 1];
1433        let broken = shaped.break_into(text, 100, &mut broken_output).unwrap();
1434        let mut scratch = [ShapedGlyph::default(); 3];
1435        let mut glyphs = [PositionedGlyph::default(); 7];
1436        let mut runs = [VisualRun::empty(); 4];
1437        let mut lines = [LayoutLine::empty(); 1];
1438        let mut carets = [CaretStop::default(); 12];
1439        let layout = logical
1440            .layout_into(
1441                text,
1442                &typefaces,
1443                &[],
1444                &broken,
1445                LayoutOptions::new(10),
1446                LayoutBuffers::new(
1447                    &mut scratch,
1448                    &mut glyphs,
1449                    &mut runs,
1450                    &mut lines,
1451                    &mut carets,
1452                ),
1453            )
1454            .unwrap();
1455
1456        let first = layout.runs()[0].text();
1457        assert_eq!(&text[first.start as usize..first.end as usize], "abc");
1458        assert_eq!(layout.runs()[0].bidi_level(), 2);
1459    }
1460}