1use crate::layout::{LayoutLine, ParagraphLayout};
8use crate::shaping::{CaretStop, FlowPoint, PositionedGlyph};
9
10pub const UNIT_SCALE: i32 = 1 << 8;
12const UNIT_TOLERANCE: i32 = 2;
13
14#[derive(Clone, Copy, Debug, Eq, PartialEq)]
15pub enum BaselineError {
16 InvalidGeometry,
17 CoordinateOverflow,
18 NonMonotonic { previous: i32, requested: i32 },
19 OutOfRange { distance: i32, length: i32 },
20 InvalidDirection,
21}
22
23#[derive(Clone, Copy, Debug, Default, Eq, PartialEq)]
24pub struct BaselineSample {
25 pub position: FlowPoint,
27 pub unit_tangent: FlowPoint,
29}
30
31pub trait BaselineCursor {
33 fn length(&self) -> i32;
34
35 fn sample_forward(&mut self, distance: i32) -> Result<BaselineSample, BaselineError>;
36}
37
38pub trait TextBaseline {
40 type Cursor<'a>: BaselineCursor
41 where
42 Self: 'a;
43
44 fn length(&self) -> i32;
45
46 fn cursor(&self) -> Self::Cursor<'_>;
47}
48
49pub trait BaselineProvider {
51 type Cursor<'a>: BaselineCursor
52 where
53 Self: 'a;
54
55 fn line_count(&self) -> usize;
56
57 fn cursor(&self, line: usize) -> Option<Self::Cursor<'_>>;
58
59 fn is_empty(&self) -> bool {
60 self.line_count() == 0
61 }
62}
63
64impl<B> BaselineProvider for [B]
65where
66 B: TextBaseline,
67{
68 type Cursor<'a>
69 = B::Cursor<'a>
70 where
71 Self: 'a;
72
73 fn line_count(&self) -> usize {
74 self.len()
75 }
76
77 fn cursor(&self, line: usize) -> Option<Self::Cursor<'_>> {
78 self.get(line).map(|baseline| baseline.cursor())
79 }
80}
81
82impl<B, const N: usize> BaselineProvider for [B; N]
83where
84 B: TextBaseline,
85{
86 type Cursor<'a>
87 = B::Cursor<'a>
88 where
89 Self: 'a;
90
91 fn line_count(&self) -> usize {
92 N
93 }
94
95 fn cursor(&self, line: usize) -> Option<Self::Cursor<'_>> {
96 self.get(line).map(|baseline| baseline.cursor())
97 }
98}
99
100#[derive(Clone, Copy, Debug, Eq, PartialEq)]
102pub struct LineBaseline {
103 start: FlowPoint,
104 end: FlowPoint,
105 length: i32,
106 unit_tangent: FlowPoint,
107}
108
109impl LineBaseline {
110 pub fn new(start: FlowPoint, end: FlowPoint) -> Result<Self, BaselineError> {
111 let (length, unit_tangent) = segment_metrics(start, end)?;
112 Ok(Self {
113 start,
114 end,
115 length,
116 unit_tangent,
117 })
118 }
119
120 pub const fn start(self) -> FlowPoint {
121 self.start
122 }
123
124 pub const fn end(self) -> FlowPoint {
125 self.end
126 }
127}
128
129impl TextBaseline for LineBaseline {
130 type Cursor<'a> = LineCursor;
131
132 fn length(&self) -> i32 {
133 self.length
134 }
135
136 fn cursor(&self) -> Self::Cursor<'_> {
137 LineCursor {
138 baseline: *self,
139 previous: None,
140 }
141 }
142}
143
144pub struct LineCursor {
146 baseline: LineBaseline,
147 previous: Option<i32>,
148}
149
150impl BaselineCursor for LineCursor {
151 fn length(&self) -> i32 {
152 self.baseline.length
153 }
154
155 fn sample_forward(&mut self, distance: i32) -> Result<BaselineSample, BaselineError> {
156 validate_distance(self.previous, distance, self.baseline.length)?;
157 self.previous = Some(distance);
158 Ok(BaselineSample {
159 position: interpolate(
160 self.baseline.start,
161 self.baseline.end,
162 distance,
163 self.baseline.length,
164 )?,
165 unit_tangent: self.baseline.unit_tangent,
166 })
167 }
168}
169
170#[derive(Clone, Copy, Debug, Eq, PartialEq)]
172pub struct PolylineBaseline<'a> {
173 points: &'a [FlowPoint],
174 length: i32,
175}
176
177impl<'a> PolylineBaseline<'a> {
178 pub fn new(points: &'a [FlowPoint]) -> Result<Self, BaselineError> {
179 if points.len() < 2 {
180 return Err(BaselineError::InvalidGeometry);
181 }
182 let mut length = 0i32;
183 for segment in points.windows(2) {
184 if segment[0] == segment[1] {
185 continue;
186 }
187 let (segment_length, _) = segment_metrics(segment[0], segment[1])?;
188 length = length
189 .checked_add(segment_length)
190 .ok_or(BaselineError::CoordinateOverflow)?;
191 }
192 if length == 0 {
193 return Err(BaselineError::InvalidGeometry);
194 }
195 Ok(Self { points, length })
196 }
197
198 pub const fn points(self) -> &'a [FlowPoint] {
199 self.points
200 }
201}
202
203impl TextBaseline for PolylineBaseline<'_> {
204 type Cursor<'a>
205 = PolylineCursor<'a>
206 where
207 Self: 'a;
208
209 fn length(&self) -> i32 {
210 self.length
211 }
212
213 fn cursor(&self) -> Self::Cursor<'_> {
214 PolylineCursor {
215 baseline: *self,
216 segment: 0,
217 segment_start: 0,
218 previous: None,
219 }
220 }
221}
222
223pub struct PolylineCursor<'a> {
225 baseline: PolylineBaseline<'a>,
226 segment: usize,
227 segment_start: i32,
228 previous: Option<i32>,
229}
230
231impl BaselineCursor for PolylineCursor<'_> {
232 fn length(&self) -> i32 {
233 self.baseline.length
234 }
235
236 fn sample_forward(&mut self, distance: i32) -> Result<BaselineSample, BaselineError> {
237 validate_distance(self.previous, distance, self.baseline.length)?;
238 self.previous = Some(distance);
239 loop {
240 let start = self.baseline.points[self.segment];
241 let end = self.baseline.points[self.segment + 1];
242 if start == end {
243 self.segment = next_nonzero_segment(self.baseline.points, self.segment + 1)
244 .ok_or(BaselineError::InvalidGeometry)?;
245 continue;
246 }
247 let (length, unit_tangent) = segment_metrics(start, end)?;
248 let segment_end = self
249 .segment_start
250 .checked_add(length)
251 .ok_or(BaselineError::CoordinateOverflow)?;
252 if distance >= segment_end {
253 let Some(next) = next_nonzero_segment(self.baseline.points, self.segment + 1)
254 else {
255 return Ok(BaselineSample {
256 position: end,
257 unit_tangent,
258 });
259 };
260 self.segment = next;
261 self.segment_start = segment_end;
262 continue;
263 }
264 let local = distance
265 .checked_sub(self.segment_start)
266 .ok_or(BaselineError::CoordinateOverflow)?;
267 return Ok(BaselineSample {
268 position: interpolate(start, end, local.min(length), length)?,
269 unit_tangent,
270 });
271 }
272 }
273}
274
275fn next_nonzero_segment(points: &[FlowPoint], mut segment: usize) -> Option<usize> {
276 while segment + 1 < points.len() {
277 if points[segment] != points[segment + 1] {
278 return Some(segment);
279 }
280 segment += 1;
281 }
282 None
283}
284
285#[derive(Clone, Copy, Debug, Default, Eq, PartialEq)]
287pub struct GlyphFrame {
288 pub local_origin: FlowPoint,
289 pub unit_tangent: FlowPoint,
290}
291
292#[derive(Clone, Copy, Debug, Default, Eq, PartialEq)]
294pub struct CaretFrame {
295 pub local_origin: FlowPoint,
296 pub unit_tangent: FlowPoint,
297}
298
299#[derive(Clone, Copy, Debug, Default, Eq, PartialEq)]
301pub struct PlacementRequirements {
302 pub glyphs: usize,
303 pub carets: usize,
304}
305
306pub struct PlacementOutput<'a> {
308 glyph_frames: &'a mut [GlyphFrame],
309 caret_frames: Option<&'a mut [CaretFrame]>,
310}
311
312impl<'a> PlacementOutput<'a> {
313 pub fn new(glyph_frames: &'a mut [GlyphFrame]) -> Self {
314 Self {
315 glyph_frames,
316 caret_frames: None,
317 }
318 }
319
320 pub fn with_carets(mut self, caret_frames: &'a mut [CaretFrame]) -> Self {
321 self.caret_frames = Some(caret_frames);
322 self
323 }
324}
325
326#[derive(Debug)]
328pub struct PlacedText<'a> {
329 glyph_frames: &'a [GlyphFrame],
330 caret_frames: Option<&'a [CaretFrame]>,
331}
332
333impl<'a> PlacedText<'a> {
334 pub const fn glyph_frames(&self) -> &[GlyphFrame] {
335 self.glyph_frames
336 }
337
338 pub const fn caret_frames(&self) -> Option<&[CaretFrame]> {
339 self.caret_frames
340 }
341}
342
343#[derive(Clone, Copy, Debug, Eq, PartialEq)]
344pub enum PlacementError {
345 BaselineCount { required: usize, provided: usize },
346 MissingBaseline { line: usize },
347 InsufficientGlyphCapacity { required: usize },
348 InsufficientCaretCapacity { required: usize },
349 InvalidLayout,
350 NegativeAdvance { glyph: usize },
351 NonMonotonicGlyphs { glyph: usize },
352 NonMonotonicCarets { caret: usize },
353 CoordinateOverflow,
354 Baseline { line: usize, error: BaselineError },
355}
356
357pub struct BaselinePlacement<'a, 'layout, P: ?Sized> {
359 layout: &'a ParagraphLayout<'layout>,
360 baselines: &'a P,
361}
362
363impl<'layout> ParagraphLayout<'layout> {
364 pub fn place_on<'a, B>(&'a self, baselines: &'a [B]) -> BaselinePlacement<'a, 'layout, [B]>
365 where
366 B: TextBaseline,
367 {
368 BaselinePlacement {
369 layout: self,
370 baselines,
371 }
372 }
373
374 pub fn place_with<'a, P>(&'a self, baselines: &'a P) -> BaselinePlacement<'a, 'layout, P>
375 where
376 P: BaselineProvider + ?Sized,
377 {
378 BaselinePlacement {
379 layout: self,
380 baselines,
381 }
382 }
383}
384
385impl<P> BaselinePlacement<'_, '_, P>
386where
387 P: BaselineProvider + ?Sized,
388{
389 pub const fn requirements(&self) -> PlacementRequirements {
390 PlacementRequirements {
391 glyphs: self.layout.glyphs().len(),
392 carets: self.layout.carets().len(),
393 }
394 }
395
396 pub fn preflight(&self) -> Result<PlacementRequirements, PlacementError> {
397 self.validate(true)?;
398 Ok(self.requirements())
399 }
400
401 pub fn place_into<'output>(
402 &self,
403 output: PlacementOutput<'output>,
404 ) -> Result<PlacedText<'output>, PlacementError> {
405 let required = self.requirements();
406 if output.glyph_frames.len() < required.glyphs {
407 return Err(PlacementError::InsufficientGlyphCapacity {
408 required: required.glyphs,
409 });
410 }
411 if let Some(carets) = output.caret_frames.as_ref() {
412 if carets.len() < required.carets {
413 return Err(PlacementError::InsufficientCaretCapacity {
414 required: required.carets,
415 });
416 }
417 }
418 let include_carets = output.caret_frames.is_some();
419 self.validate(include_carets)?;
420
421 let PlacementOutput {
422 glyph_frames,
423 caret_frames,
424 } = output;
425 self.write_glyphs(&mut glyph_frames[..required.glyphs])?;
426 if let Some(carets) = caret_frames {
427 self.write_carets(&mut carets[..required.carets])?;
428 Ok(PlacedText {
429 glyph_frames: &glyph_frames[..required.glyphs],
430 caret_frames: Some(&carets[..required.carets]),
431 })
432 } else {
433 Ok(PlacedText {
434 glyph_frames: &glyph_frames[..required.glyphs],
435 caret_frames: None,
436 })
437 }
438 }
439
440 pub fn place_carets_into<'output>(
442 &self,
443 output: &'output mut [CaretFrame],
444 ) -> Result<&'output [CaretFrame], PlacementError> {
445 let required = self.requirements().carets;
446 if output.len() < required {
447 return Err(PlacementError::InsufficientCaretCapacity { required });
448 }
449 self.validate_carets()?;
450 self.write_carets(&mut output[..required])?;
451 Ok(&output[..required])
452 }
453
454 fn validate(&self, include_carets: bool) -> Result<(), PlacementError> {
455 if self.baselines.line_count() < self.layout.lines().len() {
456 return Err(PlacementError::BaselineCount {
457 required: self.layout.lines().len(),
458 provided: self.baselines.line_count(),
459 });
460 }
461 for (line_index, line) in self.layout.lines().iter().copied().enumerate() {
462 let glyphs = self.line_glyphs(line)?;
463 let mut cursor = self.cursor(line_index)?;
464 validate_glyphs(line_index, glyphs, &mut cursor)?;
465 if include_carets {
466 let carets = self.line_carets(line)?;
467 let mut cursor = self.cursor(line_index)?;
468 validate_carets(line_index, carets, &mut cursor)?;
469 }
470 }
471 Ok(())
472 }
473
474 fn validate_carets(&self) -> Result<(), PlacementError> {
475 if self.baselines.line_count() < self.layout.lines().len() {
476 return Err(PlacementError::BaselineCount {
477 required: self.layout.lines().len(),
478 provided: self.baselines.line_count(),
479 });
480 }
481 for (line_index, line) in self.layout.lines().iter().copied().enumerate() {
482 let carets = self.line_carets(line)?;
483 let mut cursor = self.cursor(line_index)?;
484 validate_carets(line_index, carets, &mut cursor)?;
485 }
486 Ok(())
487 }
488
489 fn write_glyphs(&self, output: &mut [GlyphFrame]) -> Result<(), PlacementError> {
490 for (line_index, line) in self.layout.lines().iter().copied().enumerate() {
491 let range = checked_range(line.glyphs(), self.layout.glyphs().len())?;
492 let glyphs = &self.layout.glyphs()[range.clone()];
493 let frames = &mut output[range];
494 let mut cursor = self.cursor(line_index)?;
495 for (line_glyph, (glyph, frame)) in glyphs.iter().zip(frames).enumerate() {
496 *frame = place_glyph(line_index, line_glyph, line, glyph, &mut cursor)?;
497 }
498 }
499 Ok(())
500 }
501
502 fn write_carets(&self, output: &mut [CaretFrame]) -> Result<(), PlacementError> {
503 for (line_index, line) in self.layout.lines().iter().copied().enumerate() {
504 let range = checked_range(line.carets(), self.layout.carets().len())?;
505 let carets = &self.layout.carets()[range.clone()];
506 let frames = &mut output[range];
507 let mut cursor = self.cursor(line_index)?;
508 for (line_caret, (caret, frame)) in carets.iter().zip(frames).enumerate() {
509 *frame = place_caret(line_index, line_caret, line, caret, &mut cursor)?;
510 }
511 }
512 Ok(())
513 }
514
515 fn line_glyphs(&self, line: LayoutLine) -> Result<&[PositionedGlyph], PlacementError> {
516 let range = checked_range(line.glyphs(), self.layout.glyphs().len())?;
517 Ok(&self.layout.glyphs()[range])
518 }
519
520 fn line_carets(&self, line: LayoutLine) -> Result<&[CaretStop], PlacementError> {
521 let range = checked_range(line.carets(), self.layout.carets().len())?;
522 Ok(&self.layout.carets()[range])
523 }
524
525 fn cursor(&self, line: usize) -> Result<P::Cursor<'_>, PlacementError> {
526 self.baselines
527 .cursor(line)
528 .ok_or(PlacementError::MissingBaseline { line })
529 }
530}
531
532fn validate_glyphs(
533 line_index: usize,
534 glyphs: &[PositionedGlyph],
535 cursor: &mut impl BaselineCursor,
536) -> Result<(), PlacementError> {
537 let mut previous = None;
538 for (glyph_index, glyph) in glyphs.iter().enumerate() {
539 if glyph.advance.x < 0 {
540 return Err(PlacementError::NegativeAdvance { glyph: glyph_index });
541 }
542 let distance = inline_distance(glyph.origin)?;
543 if previous.is_some_and(|previous| distance < previous) {
544 return Err(PlacementError::NonMonotonicGlyphs { glyph: glyph_index });
545 }
546 previous = Some(distance);
547 let center = distance
548 .checked_add(glyph.advance.x / 2)
549 .ok_or(PlacementError::CoordinateOverflow)?;
550 let _ = sample(line_index, cursor, distance)?;
551 let _ = sample(line_index, cursor, center)?;
552 }
553 Ok(())
554}
555
556fn validate_carets(
557 line_index: usize,
558 carets: &[CaretStop],
559 cursor: &mut impl BaselineCursor,
560) -> Result<(), PlacementError> {
561 let mut previous = None;
562 for (caret_index, caret) in carets.iter().enumerate() {
563 let distance = inline_distance(caret.position)?;
564 if previous.is_some_and(|previous| distance < previous) {
565 return Err(PlacementError::NonMonotonicCarets { caret: caret_index });
566 }
567 previous = Some(distance);
568 let _ = sample(line_index, cursor, distance)?;
569 }
570 Ok(())
571}
572
573fn place_glyph(
574 line_index: usize,
575 glyph_index: usize,
576 line: LayoutLine,
577 glyph: &PositionedGlyph,
578 cursor: &mut impl BaselineCursor,
579) -> Result<GlyphFrame, PlacementError> {
580 if glyph.advance.x < 0 {
581 return Err(PlacementError::NegativeAdvance { glyph: glyph_index });
582 }
583 let distance = inline_distance(glyph.origin)?;
584 let center = distance
585 .checked_add(glyph.advance.x / 2)
586 .ok_or(PlacementError::CoordinateOverflow)?;
587 let origin = sample(line_index, cursor, distance)?;
588 let center = sample(line_index, cursor, center)?;
589 let normal = glyph
590 .origin
591 .y
592 .checked_sub(line.origin().y)
593 .and_then(|value| value.checked_add(glyph.offset.y))
594 .ok_or(PlacementError::CoordinateOverflow)?;
595 let local_origin =
596 project_offset(origin.position, center.unit_tangent, glyph.offset.x, normal)?;
597 Ok(GlyphFrame {
598 local_origin,
599 unit_tangent: center.unit_tangent,
600 })
601}
602
603fn place_caret(
604 line_index: usize,
605 _caret_index: usize,
606 line: LayoutLine,
607 caret: &CaretStop,
608 cursor: &mut impl BaselineCursor,
609) -> Result<CaretFrame, PlacementError> {
610 let distance = inline_distance(caret.position)?;
611 let sample = sample(line_index, cursor, distance)?;
612 let normal = caret
613 .position
614 .y
615 .checked_sub(line.origin().y)
616 .ok_or(PlacementError::CoordinateOverflow)?;
617 Ok(CaretFrame {
618 local_origin: project_offset(sample.position, sample.unit_tangent, 0, normal)?,
619 unit_tangent: sample.unit_tangent,
620 })
621}
622
623const fn inline_distance(point: FlowPoint) -> Result<i32, PlacementError> {
624 Ok(point.x)
625}
626
627fn sample(
628 line: usize,
629 cursor: &mut impl BaselineCursor,
630 distance: i32,
631) -> Result<BaselineSample, PlacementError> {
632 let sample = cursor
633 .sample_forward(distance)
634 .map_err(|error| PlacementError::Baseline { line, error })?;
635 validate_unit(sample.unit_tangent).map_err(|error| PlacementError::Baseline { line, error })?;
636 Ok(sample)
637}
638
639fn checked_range(
640 range: crate::shaping::TextRange,
641 len: usize,
642) -> Result<core::ops::Range<usize>, PlacementError> {
643 let start = range.start as usize;
644 let end = range.end as usize;
645 if start > end || end > len {
646 return Err(PlacementError::InvalidLayout);
647 }
648 Ok(start..end)
649}
650
651fn project_offset(
652 origin: FlowPoint,
653 tangent: FlowPoint,
654 inline: i32,
655 normal: i32,
656) -> Result<FlowPoint, PlacementError> {
657 let x = i128::from(origin.x)
658 .checked_add(
659 (i128::from(inline) * i128::from(tangent.x)
660 - i128::from(normal) * i128::from(tangent.y))
661 / i128::from(UNIT_SCALE),
662 )
663 .ok_or(PlacementError::CoordinateOverflow)?;
664 let y = i128::from(origin.y)
665 .checked_add(
666 (i128::from(inline) * i128::from(tangent.y)
667 + i128::from(normal) * i128::from(tangent.x))
668 / i128::from(UNIT_SCALE),
669 )
670 .ok_or(PlacementError::CoordinateOverflow)?;
671 Ok(FlowPoint {
672 x: i32::try_from(x).map_err(|_| PlacementError::CoordinateOverflow)?,
673 y: i32::try_from(y).map_err(|_| PlacementError::CoordinateOverflow)?,
674 })
675}
676
677fn validate_distance(
678 previous: Option<i32>,
679 distance: i32,
680 length: i32,
681) -> Result<(), BaselineError> {
682 if let Some(previous) = previous {
683 if distance < previous {
684 return Err(BaselineError::NonMonotonic {
685 previous,
686 requested: distance,
687 });
688 }
689 }
690 if distance < 0 || distance > length {
691 return Err(BaselineError::OutOfRange { distance, length });
692 }
693 Ok(())
694}
695
696fn validate_unit(direction: FlowPoint) -> Result<(), BaselineError> {
697 let magnitude = i64::from(direction.x) * i64::from(direction.x)
698 + i64::from(direction.y) * i64::from(direction.y);
699 let minimum = i64::from(UNIT_SCALE - UNIT_TOLERANCE).pow(2);
700 let maximum = i64::from(UNIT_SCALE + UNIT_TOLERANCE).pow(2);
701 if magnitude < minimum || magnitude > maximum {
702 return Err(BaselineError::InvalidDirection);
703 }
704 Ok(())
705}
706
707fn segment_metrics(start: FlowPoint, end: FlowPoint) -> Result<(i32, FlowPoint), BaselineError> {
708 let dx = i128::from(end.x) - i128::from(start.x);
709 let dy = i128::from(end.y) - i128::from(start.y);
710 let squared = (dx * dx + dy * dy) as u128;
711 if squared == 0 {
712 return Err(BaselineError::InvalidGeometry);
713 }
714 let maximum = i128::from(i32::MAX) * i128::from(i32::MAX);
715 if squared > maximum as u128 {
716 return Err(BaselineError::CoordinateOverflow);
717 }
718 let length = rounded_sqrt(squared);
719 let scaled_squared = squared * (UNIT_SCALE as u128) * (UNIT_SCALE as u128);
720 let scaled_length = rounded_sqrt_u128(scaled_squared);
721 let tangent = FlowPoint {
722 x: i32::try_from(
723 dx * i128::from(UNIT_SCALE) * i128::from(UNIT_SCALE)
724 / i128::try_from(scaled_length).map_err(|_| BaselineError::CoordinateOverflow)?,
725 )
726 .map_err(|_| BaselineError::CoordinateOverflow)?,
727 y: i32::try_from(
728 dy * i128::from(UNIT_SCALE) * i128::from(UNIT_SCALE)
729 / i128::try_from(scaled_length).map_err(|_| BaselineError::CoordinateOverflow)?,
730 )
731 .map_err(|_| BaselineError::CoordinateOverflow)?,
732 };
733 validate_unit(tangent)?;
734 Ok((
735 i32::try_from(length).map_err(|_| BaselineError::CoordinateOverflow)?,
736 tangent,
737 ))
738}
739
740fn interpolate(
741 start: FlowPoint,
742 end: FlowPoint,
743 distance: i32,
744 length: i32,
745) -> Result<FlowPoint, BaselineError> {
746 if distance == length {
747 return Ok(end);
748 }
749 let x = i128::from(start.x)
750 + (i128::from(end.x) - i128::from(start.x)) * i128::from(distance) / i128::from(length);
751 let y = i128::from(start.y)
752 + (i128::from(end.y) - i128::from(start.y)) * i128::from(distance) / i128::from(length);
753 Ok(FlowPoint {
754 x: i32::try_from(x).map_err(|_| BaselineError::CoordinateOverflow)?,
755 y: i32::try_from(y).map_err(|_| BaselineError::CoordinateOverflow)?,
756 })
757}
758
759fn rounded_sqrt(value: u128) -> u128 {
760 rounded_sqrt_u128(value)
761}
762
763fn rounded_sqrt_u128(value: u128) -> u128 {
764 let floor = integer_sqrt(value);
765 let lower = value - floor * floor;
766 let next = floor + 1;
767 let upper = next * next - value;
768 if upper < lower {
769 next
770 } else {
771 floor
772 }
773}
774
775fn integer_sqrt(value: u128) -> u128 {
776 if value < 2 {
777 return value;
778 }
779 let mut low = 1u128;
780 let mut high = 1u128 << (128 - value.leading_zeros() as usize).div_ceil(2);
781 while low + 1 < high {
782 let middle = low + (high - low) / 2;
783 if middle <= value / middle {
784 low = middle;
785 } else {
786 high = middle;
787 }
788 }
789 low
790}
791
792#[cfg(test)]
793mod tests {
794 use super::*;
795 use crate::shaping::{
796 FontAccessError, FontId, FontMetrics, GlyphId, GlyphSource, SimpleTypeface,
797 };
798 use crate::{LayoutScratch, TextFlow};
799
800 struct Mono;
801
802 struct BorrowedLines {
803 lines: [LineBaseline; 2],
804 }
805
806 impl BaselineProvider for BorrowedLines {
807 type Cursor<'a> = LineCursor;
808
809 fn line_count(&self) -> usize {
810 self.lines.len()
811 }
812
813 fn cursor(&self, line: usize) -> Option<Self::Cursor<'_>> {
814 self.lines.get(line).map(TextBaseline::cursor)
815 }
816 }
817
818 impl GlyphSource for Mono {
819 fn id(&self) -> FontId {
820 FontId::new(1)
821 }
822
823 fn metrics(&self) -> Result<FontMetrics, FontAccessError> {
824 Ok(FontMetrics {
825 units_per_em: 256,
826 ascender: 192,
827 descender: -64,
828 line_gap: 0,
829 })
830 }
831
832 fn glyph_for(&self, character: char) -> Result<Option<GlyphId>, FontAccessError> {
833 Ok(Some(GlyphId::new(character as u16)))
834 }
835
836 fn glyph_advance(&self, _glyph: GlyphId) -> Result<FlowPoint, FontAccessError> {
837 Ok(FlowPoint { x: 256, y: 0 })
838 }
839 }
840
841 #[test]
842 fn line_cursor_is_forward_only_and_reaches_exact_endpoints() {
843 let baseline =
844 LineBaseline::new(FlowPoint { x: 10, y: 20 }, FlowPoint { x: 266, y: 276 }).unwrap();
845 let mut cursor = baseline.cursor();
846
847 assert_eq!(cursor.sample_forward(0).unwrap().position, baseline.start());
848 assert_eq!(
849 cursor.sample_forward(baseline.length()).unwrap().position,
850 baseline.end()
851 );
852 assert!(matches!(
853 cursor.sample_forward(0),
854 Err(BaselineError::NonMonotonic { .. })
855 ));
856 }
857
858 #[test]
859 fn polyline_skips_zero_segments_and_uses_outgoing_vertex_tangent() {
860 let points = [
861 FlowPoint { x: 0, y: 0 },
862 FlowPoint { x: 0, y: 0 },
863 FlowPoint { x: 256, y: 0 },
864 FlowPoint { x: 256, y: 256 },
865 ];
866 let baseline = PolylineBaseline::new(&points).unwrap();
867 let mut cursor = baseline.cursor();
868
869 let vertex = cursor.sample_forward(256).unwrap();
870 assert_eq!(vertex.position, FlowPoint { x: 256, y: 0 });
871 assert_eq!(vertex.unit_tangent, FlowPoint { x: 0, y: 256 });
872 }
873
874 #[test]
875 fn polyline_reaches_the_last_nonzero_endpoint_before_trailing_duplicates() {
876 let points = [
877 FlowPoint { x: 0, y: 0 },
878 FlowPoint { x: 256, y: 0 },
879 FlowPoint { x: 256, y: 0 },
880 FlowPoint { x: 256, y: 0 },
881 ];
882 let baseline = PolylineBaseline::new(&points).unwrap();
883 let mut cursor = baseline.cursor();
884
885 assert_eq!(
886 cursor.sample_forward(baseline.length()).unwrap().position,
887 FlowPoint { x: 256, y: 0 }
888 );
889 }
890
891 #[test]
892 fn extreme_coordinate_differences_return_errors_without_overflowing() {
893 assert_eq!(
894 LineBaseline::new(
895 FlowPoint {
896 x: i32::MIN,
897 y: i32::MIN,
898 },
899 FlowPoint {
900 x: i32::MAX,
901 y: i32::MAX,
902 },
903 ),
904 Err(BaselineError::CoordinateOverflow)
905 );
906 }
907
908 #[test]
909 fn sampled_arc_stays_borrowed_and_has_bounded_direction_error() {
910 let quarter_arc = [
911 FlowPoint { x: 256, y: 0 },
912 FlowPoint { x: 237, y: 98 },
913 FlowPoint { x: 181, y: 181 },
914 FlowPoint { x: 98, y: 237 },
915 FlowPoint { x: 0, y: 256 },
916 ];
917 let baseline = PolylineBaseline::new(&quarter_arc).unwrap();
918 let mut cursor = baseline.cursor();
919 let sample = cursor.sample_forward(baseline.length() / 2).unwrap();
920
921 assert_eq!(baseline.points().as_ptr(), quarter_arc.as_ptr());
922 validate_unit(sample.unit_tangent).unwrap();
923 assert!(sample.position.x > 128 && sample.position.y > 128);
924 }
925
926 #[test]
927 fn placement_preserves_linear_alignment_and_maps_offsets_to_the_frame() {
928 let face = SimpleTypeface::new(&Mono);
929 let mut scratch = LayoutScratch::<4, 8, 2, 8>::new();
930 let layout = TextFlow::new("ab", 1024)
931 .with_line_height(256)
932 .with_alignment(crate::Alignment::Center)
933 .layout_with_scratch(&[&face], &mut scratch)
934 .unwrap();
935 let baseline =
936 [LineBaseline::new(FlowPoint { x: 0, y: 0 }, FlowPoint { x: 1024, y: 0 }).unwrap()];
937 let mut glyphs = [GlyphFrame::default(); 2];
938 let mut carets = [CaretFrame::default(); 3];
939 let placed = layout
940 .place_on(&baseline)
941 .place_into(PlacementOutput::new(&mut glyphs).with_carets(&mut carets))
942 .unwrap();
943
944 assert_eq!(placed.glyph_frames()[0].local_origin.x, 256);
945 assert_eq!(placed.glyph_frames()[1].local_origin.x, 512);
946 assert_eq!(placed.caret_frames().unwrap()[0].local_origin.x, 256);
947 assert_eq!(placed.caret_frames().unwrap()[2].local_origin.x, 768);
948 }
949
950 #[test]
951 fn provider_places_each_line_without_a_baseline_slice() {
952 let face = SimpleTypeface::new(&Mono);
953 let widths = [256, 256];
954 let mut scratch = LayoutScratch::<4, 8, 2, 8>::new();
955 let layout = TextFlow::new("ab", 256)
956 .with_line_widths(&widths)
957 .with_line_height(256)
958 .with_wrap(crate::WrapMode::Grapheme)
959 .layout_with_scratch(&[&face], &mut scratch)
960 .unwrap();
961 let baselines = BorrowedLines {
962 lines: [
963 LineBaseline::new(FlowPoint { x: 10, y: 20 }, FlowPoint { x: 266, y: 20 }).unwrap(),
964 LineBaseline::new(FlowPoint { x: 30, y: 400 }, FlowPoint { x: 286, y: 400 })
965 .unwrap(),
966 ],
967 };
968 let mut glyphs = [GlyphFrame::default(); 2];
969
970 let placed = layout
971 .place_with(&baselines)
972 .place_into(PlacementOutput::new(&mut glyphs))
973 .unwrap();
974
975 assert_eq!(
976 placed.glyph_frames()[0].local_origin,
977 FlowPoint { x: 10, y: 20 }
978 );
979 assert_eq!(
980 placed.glyph_frames()[1].local_origin,
981 FlowPoint { x: 30, y: 400 }
982 );
983 }
984
985 #[test]
986 fn caret_only_placement_does_not_require_a_glyph_buffer() {
987 let face = SimpleTypeface::new(&Mono);
988 let mut scratch = LayoutScratch::<4, 8, 2, 8>::new();
989 let layout = TextFlow::new("ab", 512)
990 .with_line_height(256)
991 .layout_with_scratch(&[&face], &mut scratch)
992 .unwrap();
993 let baseline =
994 [LineBaseline::new(FlowPoint { x: 10, y: 20 }, FlowPoint { x: 522, y: 20 }).unwrap()];
995 let mut carets = [CaretFrame::default(); 3];
996
997 let placed = layout
998 .place_on(&baseline)
999 .place_carets_into(&mut carets)
1000 .unwrap();
1001
1002 assert_eq!(placed[0].local_origin, FlowPoint { x: 10, y: 20 });
1003 assert_eq!(placed[2].local_origin, FlowPoint { x: 522, y: 20 });
1004 }
1005
1006 #[test]
1007 fn insufficient_output_is_failure_atomic() {
1008 let face = SimpleTypeface::new(&Mono);
1009 let mut scratch = LayoutScratch::<4, 8, 2, 8>::new();
1010 let layout = TextFlow::new("ab", 512)
1011 .with_line_height(256)
1012 .layout_with_scratch(&[&face], &mut scratch)
1013 .unwrap();
1014 let baseline =
1015 [LineBaseline::new(FlowPoint { x: 0, y: 0 }, FlowPoint { x: 512, y: 0 }).unwrap()];
1016 let sentinel = GlyphFrame {
1017 local_origin: FlowPoint { x: 77, y: 88 },
1018 unit_tangent: FlowPoint { x: 99, y: 111 },
1019 };
1020 let mut glyphs = [sentinel; 1];
1021
1022 assert_eq!(
1023 layout
1024 .place_on(&baseline)
1025 .place_into(PlacementOutput::new(&mut glyphs))
1026 .unwrap_err(),
1027 PlacementError::InsufficientGlyphCapacity { required: 2 }
1028 );
1029 assert_eq!(glyphs, [sentinel]);
1030 }
1031
1032 #[test]
1033 fn geometry_failure_is_atomic_before_any_frame_is_written() {
1034 let face = SimpleTypeface::new(&Mono);
1035 let mut scratch = LayoutScratch::<4, 8, 2, 8>::new();
1036 let layout = TextFlow::new("ab", 512)
1037 .with_line_height(256)
1038 .layout_with_scratch(&[&face], &mut scratch)
1039 .unwrap();
1040 let short =
1041 [LineBaseline::new(FlowPoint { x: 0, y: 0 }, FlowPoint { x: 128, y: 0 }).unwrap()];
1042 let sentinel = GlyphFrame {
1043 local_origin: FlowPoint { x: 77, y: 88 },
1044 unit_tangent: FlowPoint { x: 99, y: 111 },
1045 };
1046 let mut glyphs = [sentinel; 2];
1047
1048 assert!(matches!(
1049 layout
1050 .place_on(&short)
1051 .place_into(PlacementOutput::new(&mut glyphs)),
1052 Err(PlacementError::Baseline {
1053 error: BaselineError::OutOfRange { .. },
1054 ..
1055 })
1056 ));
1057 assert_eq!(glyphs, [sentinel; 2]);
1058 }
1059}