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}