Skip to main content

textflow/
placement.rs

1//! Allocation-free placement of linear paragraph output on sampled baselines.
2//!
3//! A baseline creates a fresh forward cursor for each pass. Cursors must return
4//! deterministic samples for monotonically increasing distances. This permits
5//! capacity and geometry validation before caller-owned output is modified.
6
7use crate::layout::{LayoutLine, ParagraphLayout};
8use crate::shaping::{CaretStop, FlowPoint, PositionedGlyph};
9
10/// Fixed-point value representing a unit-length direction.
11pub 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    /// Baseline position in the layout coordinate space.
26    pub position: FlowPoint,
27    /// Normalized direction in `UNIT_SCALE` units.
28    pub unit_tangent: FlowPoint,
29}
30
31/// Stateful forward-only access to one baseline.
32pub trait BaselineCursor {
33    fn length(&self) -> i32;
34
35    fn sample_forward(&mut self, distance: i32) -> Result<BaselineSample, BaselineError>;
36}
37
38/// Reusable baseline geometry capable of creating independent cursors.
39pub 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
49/// Borrows one independently sampled baseline for each paragraph line.
50pub 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/// A straight baseline between two fixed-point positions.
101#[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
144/// Forward cursor returned by [`LineBaseline`].
145pub 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/// A borrowed piecewise-linear baseline.
171#[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
223/// Forward cursor returned by [`PolylineBaseline`].
224pub 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/// Per-glyph geometry paired by index with a positioned glyph.
286#[derive(Clone, Copy, Debug, Default, Eq, PartialEq)]
287pub struct GlyphFrame {
288    pub local_origin: FlowPoint,
289    pub unit_tangent: FlowPoint,
290}
291
292/// Per-caret geometry paired by index with a linear caret stop.
293#[derive(Clone, Copy, Debug, Default, Eq, PartialEq)]
294pub struct CaretFrame {
295    pub local_origin: FlowPoint,
296    pub unit_tangent: FlowPoint,
297}
298
299/// Caller storage required by one placement.
300#[derive(Clone, Copy, Debug, Default, Eq, PartialEq)]
301pub struct PlacementRequirements {
302    pub glyphs: usize,
303    pub carets: usize,
304}
305
306/// Caller-owned frame buffers used by [`BaselinePlacement::place_into`].
307pub 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/// Borrowed frame slices produced by path placement.
327#[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
357/// Validated placement operation for a paragraph and one baseline per line.
358pub 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    /// Places only caret frames into caller-owned storage.
441    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}