2bc41aeb8602
on_path.rs
use super::bidi::{is_rtl, para_bidi_with, visual_order};
use super::breaking::{Metrics, optical_hangs, optical_hangs_rtl, optical_share, roman_share};
use super::flow::{list_markers, repeat_mark_glyph};
use super::region::in_range;
use super::{
Affine, ArcPath, BezPath, Ctx, GlyphBend, Justify, LineInfo, ListMarker, ParamCurve, PathAlign, PathData, PathEffect, PathEl, Point, Range,
SGlyph, Shape, TextObject, Vec2, apply_desired, style_metrics,
};
use crate::fontdb::PathAlignHeights;
use std::collections::HashMap;
use unicode_bidi::{BidiClass, BidiInfo};
/// The distance along type on a path each glyph takes: its advance measured `spacing` points above
/// the path (Type on a Path Options › Spacing), so glyphs close up round the outside of a curve and
/// open up round the inside; just the advances without spacing. Glyphs start `from` along the path.
fn path_steps(ap: &ArcPath, glyphs: &[SGlyph], from: f64, spacing: f64) -> Vec<f64> {
let mut s = from;
glyphs
.iter()
.map(|g| {
let mut step = g.adv;
if spacing != 0.0 && g.adv > 1e-9 {
// How far the path turns across the glyph: positive bending away from its top.
let ((_, a), (_, b)) = (ap.at(s), ap.at(s + g.adv));
let curvature = a.cross(b).atan2(a.dot(b)) / g.adv;
step = g.adv / (1.0 + curvature * spacing).clamp(0.25, 4.0);
}
s += step;
step
})
.collect()
}
/// How closely a bent glyph's curves follow the path (text space units).
const BEND_TOLERANCE: f64 = 0.01;
/// The most pieces one segment of a glyph's outline is cut into to bend it.
const BEND_PIECES: usize = 32;
/// The most elements a bent glyph outline may have; beyond that the glyph stays straight.
const BEND_MAX_ELEMENTS: usize = 8192;
/// `outline` (text space, placed straight by `pre`, which takes the glyph's pen space there) bent
/// along `ap` as `bend` says ([`GlyphBend`]); `None` where the path doesn't turn under the glyph
/// (it stays as it is, exactly), or the bent outline would be too large or not finite.
fn bend_outline(outline: &BezPath, pre: Affine, ap: &ArcPath, bend: &GlyphBend) -> Option<BezPath> {
let GlyphBend { s, step, advance, rise } = *bend;
if outline.elements().is_empty() || !(advance > 1e-9 && step.is_finite() && step > 0.0 && s.is_finite() && rise.is_finite()) {
return None;
}
// How far the path turns under the glyph; none: it lies straight already.
let ((_, a), (_, b)) = (ap.at(s), ap.at(s + step));
let turn = a.cross(b).atan2(a.dot(b)).abs();
if !(turn.is_finite() && turn > 1e-9) {
return None;
}
let det = pre.determinant();
if !(det.is_finite() && det.abs() > 1e-12) {
return None;
}
let to_pen = pre.inverse();
let k = step / advance;
let map = |q: Point| {
let (p, d) = ap.at(s + q.x * k);
p + Vec2::new(-d.y, d.x) * (q.y + rise)
};
// Pieces short enough that mapping a piece's control points stays within the tolerance: the
// error of a piece of length L under curvature c, at height y, is about L² c (1 + |y| c) / 8.
let curvature = turn / step;
let pen = to_pen * outline.clone();
let height = pen.bounding_box().y0.abs().max(pen.bounding_box().y1.abs()) + rise.abs();
let piece = ((8.0 * BEND_TOLERANCE) / (curvature * (1.0 + height * curvature))).sqrt();
let pieces = |a: Point, b: Point| -> usize {
let n = ((b - a).hypot() / piece).ceil();
if n.is_finite() { (n as usize).clamp(1, BEND_PIECES) } else { BEND_PIECES }
};
let mut out = BezPath::new();
let (mut start, mut cur) = (Point::ZERO, Point::ZERO);
let line = |out: &mut BezPath, from: Point, to: Point| {
let n = pieces(from, to);
for i in 1..=n {
out.line_to(map(from.lerp(to, i as f64 / n as f64)));
}
};
for el in pen.elements() {
match *el {
PathEl::MoveTo(p) => {
out.move_to(map(p));
(start, cur) = (p, p);
}
PathEl::LineTo(p) => {
line(&mut out, cur, p);
cur = p;
}
PathEl::QuadTo(p1, p2) => {
let c = kurbo::QuadBez::new(cur, p1, p2).raise();
let n = pieces(cur, p1).max(pieces(p1, p2));
for i in 0..n {
let q = c.subsegment(i as f64 / n as f64..(i + 1) as f64 / n as f64);
out.curve_to(map(q.p1), map(q.p2), map(q.p3));
}
cur = p2;
}
PathEl::CurveTo(p1, p2, p3) => {
let c = kurbo::CubicBez::new(cur, p1, p2, p3);
let n = pieces(cur, p1).max(pieces(p1, p2)).max(pieces(p2, p3));
for i in 0..n {
let q = c.subsegment(i as f64 / n as f64..(i + 1) as f64 / n as f64);
out.curve_to(map(q.p1), map(q.p2), map(q.p3));
}
cur = p3;
}
PathEl::ClosePath => {
if (cur - start).hypot() > 1e-12 {
line(&mut out, cur, start);
}
out.close_path();
cur = start;
}
}
if out.elements().len() > BEND_MAX_ELEMENTS {
return None;
}
}
let finite = |p: Point| p.x.is_finite() && p.y.is_finite();
out.elements()
.iter()
.all(|el| match *el {
PathEl::MoveTo(p) | PathEl::LineTo(p) => finite(p),
PathEl::QuadTo(a, b) => finite(a) && finite(b),
PathEl::CurveTo(a, b, c) => finite(a) && finite(b) && finite(c),
PathEl::ClosePath => true,
})
.then_some(out)
}
/// Glyphs in a row, each taking its step: how far the row takes the line (`sum`), and how far past
/// where its first glyph starts the farthest of their ends is (`far`).
#[derive(Clone, Copy)]
struct Reach {
sum: f64,
far: f64,
}
impl Reach {
/// No glyphs.
const NONE: Self = Self { sum: 0.0, far: f64::NEG_INFINITY };
/// One glyph.
fn step(step: f64) -> Self {
Self { sum: step, far: step }
}
/// The glyphs of `self` followed by those of `next`.
fn then(self, next: Self) -> Self {
Self { sum: self.sum + next.sum, far: self.far.max(self.sum + next.far) }
}
}
/// The reach of the glyphs at some of `n` positions in a row (a segment tree): a glyph is put at
/// its position in O(log n), and the reach of the glyphs in a range of positions is found in O(log n).
struct Reaches {
size: usize,
nodes: Vec<Reach>,
}
impl Reaches {
fn new(n: usize) -> Self {
let size = n.next_power_of_two();
Self { size, nodes: vec![Reach::NONE; 2 * size] }
}
fn node(&self, k: usize) -> Reach {
self.nodes.get(k).copied().unwrap_or(Reach::NONE)
}
/// Puts a glyph that takes `step` at position `at`.
fn put(&mut self, at: usize, step: f64) {
let mut k = self.size + at;
let Some(leaf) = self.nodes.get_mut(k) else { return };
*leaf = Reach::step(step);
while k > 1 {
k /= 2;
let joined = self.node(2 * k).then(self.node(2 * k + 1));
if let Some(node) = self.nodes.get_mut(k) {
*node = joined;
}
}
}
/// The reach of the glyphs put at positions `range`, in order.
fn of(&self, range: Range<usize>) -> Reach {
let (mut left, mut right) = (Reach::NONE, Reach::NONE);
let (mut a, mut b) = (range.start.min(self.size) + self.size, range.end.min(self.size) + self.size);
while a < b {
if a % 2 == 1 {
left = left.then(self.node(a));
a += 1;
}
if b % 2 == 1 {
b -= 1;
right = self.node(b).then(right);
}
(a, b) = (a / 2, b / 2);
}
left.then(right)
}
}
/// Whether a glyph whose character has bidi class `class` goes to its paragraph's level when the
/// line ends with it and the characters after it like it (UAX #9 L1): whitespace and isolate
/// controls, and the embedding controls and boundary neutrals, which `unicode_bidi` treats the same.
fn trails(class: BidiClass) -> bool {
use unicode_bidi::BidiClass::{BN, FSI, LRE, LRI, LRO, PDF, PDI, RLE, RLI, RLO, WS};
matches!(class, WS | FSI | LRI | RLI | PDI | RLE | LRE | RLO | LRO | PDF | BN)
}
/// Measures every start of the text in reading order, shortest first, in O(n log n) for n glyphs:
/// `visit(end, reach)` gets the byte each start ends at (a glyph's byte; the whole text is not
/// visited) and the reach of its glyphs in its own visual order when each glyph `g` takes `step(g)`.
///
/// The visual order of a start of a paragraph keeps the order its glyphs have in the whole
/// paragraph (UAX #9 L2 reorders by the levels between two glyphs only), except for the glyphs
/// that L1 sets to the paragraph's level at the end of the start: those come after the rest in a
/// left-to-right paragraph and before it, last first, in a right-to-left one. The glyphs are put at
/// their positions in the whole text's visual order one start after another.
fn each_start(shaped: &[(Range<usize>, Option<BidiInfo<'_>>, Vec<SGlyph>)], step: impl Fn(&SGlyph) -> f64, mut visit: impl FnMut(usize, Reach)) {
let total = shaped.iter().map(|(_, _, glyphs)| glyphs.len()).sum();
let mut reaches = Reaches::new(total);
let mut last_byte = None;
let mut para_at = 0;
for (pr, bidi, glyphs) in shaped {
// Where each glyph of the paragraph is in the whole text's visual order.
let mut at = vec![para_at; glyphs.len()];
for (v, i) in visual_order(bidi.as_ref(), pr.start, pr.clone(), glyphs).into_iter().enumerate() {
if let Some(p) = at.get_mut(i) {
*p = para_at + v;
}
}
let para_rtl = bidi.as_ref().and_then(|b| b.paragraphs.first()).map(|p| p.level.is_rtl());
// The glyphs at the end of the start so far that L1 sets to the paragraph's level, their
// reach in visual order, and the reach of the cluster being added to them.
let mut held: Vec<(usize, f64)> = Vec::new();
let (mut trailing, mut cluster) = (Reach::NONE, Reach::NONE);
let mut prev: Option<&SGlyph> = None;
for (g, &p) in glyphs.iter().zip(&at) {
// A cluster is a glyph and those after it at its byte (a list marker's apart).
let joins = prev.is_some_and(|q| q.byte == g.byte && (q.len == 0) == (g.len == 0));
if !joins {
trailing = match para_rtl {
Some(true) => cluster.then(trailing),
_ => trailing.then(cluster),
};
cluster = Reach::NONE;
}
if last_byte != Some(g.byte) {
// The start that ends before this glyph.
let reach = match para_rtl {
_ if held.is_empty() => reaches.of(0..total),
Some(true) => reaches.of(0..para_at).then(trailing).then(reaches.of(para_at..total)),
_ => reaches.of(0..total).then(trailing),
};
visit(g.byte, reach);
last_byte = Some(g.byte);
}
let s = step(g);
// Every character of the glyph's cluster is one that trails.
let from = g.byte.saturating_sub(pr.start);
let classes = bidi.as_ref().and_then(|b| b.original_classes.get(from..from + g.len));
if para_rtl.is_some() && g.len > 0 && classes.is_some_and(|c| c.iter().copied().all(trails)) {
held.push((p, s));
cluster = cluster.then(Reach::step(s));
} else {
for (q, s) in held.drain(..) {
reaches.put(q, s);
}
(trailing, cluster) = (Reach::NONE, Reach::NONE);
reaches.put(p, s);
}
prev = Some(g);
}
// The whole paragraph is in its own visual order.
for (q, s) in held.drain(..) {
reaches.put(q, s);
}
para_at += glyphs.len();
}
}
/// The end (a byte) of the longest start of the text, in reading order, whose glyphs fit when each
/// takes its advance: `fits(w, far)` says whether glyphs in visual order that take `w` along the
/// path, the farthest of their ends `far` past where the first starts, fit. `first` is the first
/// glyph's byte, where nothing is laid out. A start can fit where a shorter one doesn't, after a
/// glyph that takes the line back, so every start is measured ([`each_start`]).
fn longest_fitting_start(shaped: &[(Range<usize>, Option<BidiInfo<'_>>, Vec<SGlyph>)], first: usize, fits: impl Fn(f64, f64) -> bool) -> usize {
let mut longest = first;
each_start(
shaped,
|g| g.adv,
|byte, reach| {
if fits(reach.sum, reach.far) {
longest = byte;
}
},
);
longest
}
/// The ends (bytes) of the starts of the text, in reading order, shortest first, that can fit on a
/// path of length `len` with `spacing`: those whose glyphs, in their own visual order, reach at most
/// `len` past where the first starts when each takes the least step it can. A glyph's step is at
/// least a quarter of its advance with spacing, and its advance otherwise ([`path_steps`]); a line
/// starts no earlier than its span with the hang at its start, and every glyph that fits ends within
/// that span with both hangs, which is no longer than the path. The start before the first glyph,
/// where nothing is laid out, is always one of them.
fn starts_that_can_fit(shaped: &[(Range<usize>, Option<BidiInfo<'_>>, Vec<SGlyph>)], spacing: f64, len: f64) -> Vec<usize> {
let least = |g: &SGlyph| if spacing != 0.0 && g.adv > 1e-9 { g.adv * 0.25 } else { g.adv };
let mut starts = Vec::new();
each_start(shaped, least, |byte, reach| {
// A little room for sums added in another order than where the glyphs are placed.
if reach.far <= len + 1e-5 || reach.far.is_nan() {
starts.push(byte);
}
});
starts
}
/// The most starts of overflowing right-to-left type on a path that are arranged one by one, from
/// the longest, when a glyph takes the line back ([`longest_start_tried`]).
const PATH_START_TRIES: usize = 32;
/// The longest of `starts` (ends of starts, shortest first, the first of which fits) for which
/// `fits` holds, arranging at most `tries` of them one by one, from the longest. When none of those
/// fits, a binary search among the rest finds one that fits with O(log n) more arrangements; as a
/// longer start can fit where a shorter one doesn't, that one is not always the longest that fits.
/// `None` when there are no starts.
fn longest_start_tried(starts: &[usize], tries: usize, mut fits: impl FnMut(usize) -> bool) -> Option<usize> {
let rest = starts.len().saturating_sub(tries);
if let Some(&byte) = starts.get(rest..).unwrap_or_default().iter().rev().find(|&&byte| fits(byte)) {
return Some(byte);
}
// `starts[fit]` fits; `starts[over]` was tried or doesn't.
let (mut fit, mut over) = (0, rest);
while over > fit + 1 {
let mid = fit + (over - fit) / 2;
if starts.get(mid).is_some_and(|&byte| fits(byte)) {
fit = mid;
} else {
over = mid;
}
}
starts.get(fit).copied()
}
#[cfg(test)]
thread_local! {
/// How many times type on a path arranged glyphs on its path on this thread ([`path_arrangements`]).
static ARRANGEMENTS: std::cell::Cell<usize> = const { std::cell::Cell::new(0) };
}
/// How many times type on a path arranged glyphs on its path on this thread.
#[cfg(test)]
pub(crate) fn path_arrangements() -> usize {
ARRANGEMENTS.get()
}
#[cfg(test)]
thread_local! {
/// Set while [`layout_trying_each_start`] lays text out.
static EACH_START: std::cell::Cell<bool> = const { std::cell::Cell::new(false) };
}
/// [`layout`](super::layout) arranging every start of overflowing right-to-left type on a path in
/// turn, from the longest, until one fits: the reference the search for the longest start is
/// compared with.
#[cfg(test)]
pub(crate) fn layout_trying_each_start(db: &crate::fontdb::FontDb, t: &TextObject) -> crate::TextLayout {
EACH_START.set(true);
let l = super::layout(db, t);
EACH_START.set(false);
l
}
/// For type that starts before its open path `ap` (`lead`), a glyph whose middle is `mid` along the
/// path and falls before the path's start is not drawn, as SVG 2 lays out text on a path
/// (https://www.w3.org/TR/SVG2/text.html#TextLayoutPath): glyph `at` keeps its place in the layout
/// for the caret, with no length at the path's start (moved off the path by `rise`, as Align to Path
/// moves the glyph), and draws nothing ([`crate::PositionedGlyph::off_path`]). True when it is hidden.
fn hide_before_open_path(cx: &mut Ctx<'_>, ap: &ArcPath, lead: bool, at: usize, mid: f64, rise: f64) -> bool {
if !lead || ap.is_closed() || mid >= 0.0 {
return false;
}
let (p, dir) = ap.at(0.0);
let start = p + Vec2::new(-dir.y, dir.x) * rise;
if let Some(glyph) = cx.out.glyphs.get_mut(at) {
glyph.origin = start;
glyph.advance = 0.0;
glyph.width = 0.0;
glyph.width_start = 0.0;
glyph.outline = BezPath::new();
glyph.image = None;
glyph.colour = None;
// A ligature's caret stops stay, at the path's start with the glyph.
for c in &mut glyph.carets {
c.1 = 0.0;
}
glyph.off_path = true;
}
cx.out.inlines.retain(|i| i.glyph != at);
true
}
/// Kurikaeshi Moji Shori: type on a path is one line, which starts with the first character of its
/// first paragraph `pr` (shaped as `glyphs`). When that paragraph continues from the frame before
/// and has the setting on, a repeat mark there is drawn as the character before it in the frames
/// before ([`TextObject::first_para_lead`]): its glyph in `glyphs` is replaced, and the mark's byte
/// and the character drawn are returned.
fn line_start_repeat(cx: &Ctx<'_>, t: &TextObject, pr: &Range<usize>, glyphs: &mut [SGlyph]) -> Option<(usize, char)> {
if !t.first_para_continues || !t.para_at(0).kurikaeshi_moji_shori {
return None;
}
let at = glyphs.iter().position(|g| g.len > 0 && g.byte == pr.start)?;
let (glyph, c) = repeat_mark_glyph(cx, glyphs.get(at)?, glyphs.get(at + 1), || Some(t.first_para_lead))?;
let g = glyphs.get_mut(at)?;
*g = glyph;
Some((g.byte, c))
}
/// Justification…: paragraph `pi`'s glyphs at its Desired word and letter spacing and glyph scaling
/// (vertical type is not glyph scaled), with the Desired Glyph Scaling of each glyph it scales put
/// in `scales` by byte offset. Type on a path is one line that is never justified to a width, so
/// Minimum and Maximum are not used.
fn set_desired(cx: &Ctx<'_>, t: &TextObject, pi: usize, glyphs: &mut [SGlyph], scales: &mut HashMap<usize, f64>) {
let flex = apply_desired(glyphs, &t.layout_justification(t.para_at(pi)), !cx.vertical);
scales.extend(glyphs.iter().zip(&flex).filter(|(_, f)| f.scale != 1.0).map(|(g, f)| (g.byte, f.scale)));
}
/// Records on the glyph just drawn for `g` the Desired Glyph Scaling it is drawn at (`scales`, by
/// byte offset). A list marker's glyphs (no length) share their paragraph's first byte and are not
/// scaled.
fn record_scale(cx: &mut Ctx<'_>, g: &SGlyph, scales: &HashMap<usize, f64>) {
let scale = if g.len > 0 { scales.get(&g.byte).copied() } else { None };
if let (Some(scale), Some(out)) = (scale, cx.out.glyphs.last_mut()) {
out.scale = scale;
}
}
/// Lay type on a path out along `path` (text space), between its brackets.
pub(super) fn on_path(cx: &mut Ctx<'_>, paras: &[Range<usize>], t: &TextObject, path: &PathData) {
cx.out.on_path = true;
// Type on a path is one line: the first paragraph's attributes align it.
let para = t.para_at(0);
// The first paragraph's direction aligns the line (Auto) and sets the caret's.
let mut rtl = None;
let mut shaped = Vec::new();
let markers = list_markers(t, paras);
// The Desired Glyph Scaling each scaled glyph is drawn at, by its byte offset.
let mut scales = HashMap::new();
for (pi, pr) in paras.iter().enumerate() {
let text = cx.text;
let bidi = para_bidi_with(text.get(pr.clone()).unwrap_or_default(), para.direction, &cx.char_directions(pr));
rtl.get_or_insert(is_rtl(bidi.as_ref()) && !cx.vertical);
let mut glyphs = cx.shape_para(pr.clone(), bidi.as_ref(), t.para_at(pi));
// Justification…, before anything measures the glyphs along the path.
set_desired(cx, t, pi, &mut glyphs, &mut scales);
// Bullets and numbers: a list paragraph's text starts after its marker here too, unless
// the paragraph continues from the frame before in its thread.
if pi > 0 || !t.first_para_continues {
let marker_text = markers.get(pi).and_then(Option::as_deref);
cx.prepend_marker(pr, t.para_at(pi), marker_text, is_rtl(bidi.as_ref()) && !cx.vertical, &mut glyphs);
}
shaped.push((pr.clone(), bidi.filter(|b| b.has_rtl() && !cx.vertical), glyphs));
}
// Kurikaeshi Moji Shori: the repeat mark that starts the line, recorded when its glyph is drawn.
let mut repeat = shaped.first_mut().and_then(|(pr, _, glyphs)| line_start_repeat(cx, t, pr, glyphs));
let rtl = rtl.unwrap_or(false);
// The text before byte `cut` in visual order, as area type reorders each line it breaks.
let visual = |cut: usize| {
let mut sg = Vec::new();
for (pr, bidi, glyphs) in &shaped {
let n = glyphs.iter().take_while(|g| g.byte < cut).count();
let line = glyphs.get(..n).unwrap_or_default();
let end = glyphs.get(n).map_or(pr.end, |g| g.byte);
sg.extend(visual_order(bidi.as_ref(), pr.start, pr.start..end, line).into_iter().filter_map(|i| line.get(i).cloned()));
}
sg
};
let text_len = cx.text.len();
let mut sg = visual(text_len);
// A path out of range holds no text, as a path with no length holds none.
let ap = if in_range(&path.to_bezpath()) { ArcPath::new(path) } else { ArcPath::default() };
let m = Metrics::max(&sg).map(|m| (m.asc, m.desc)).unwrap_or_else(|| {
let s = style_metrics(cx.face_at(0).as_deref(), cx.style_at(0));
(s.0, s.1)
});
// Vertical type: the caret and the selection span the column, half its em on each side of the
// line Align to Path puts the baseline on.
let m = if cx.vertical {
let half = sg.iter().map(|g| g.face.units_per_em() * g.sx * 0.5).fold(f64::NAN, f64::max);
let half = if half.is_finite() { half } else { cx.style_at(0).size * 0.5 };
(half, half)
} else {
m
};
if ap.is_empty() {
cx.out.overflow = !sg.is_empty();
cx.out.lines.push(LineInfo {
rtl,
baseline: 0.0,
x0: 0.0,
x1: 0.0,
trailing: 0.0,
ascent: m.0,
descent: m.1,
first_baseline: 0.0,
start: 0,
end: 0,
glyph_start: 0,
glyph_end: 0,
avail: (0.0, 0.0),
region: 0,
});
return;
}
let centre = path.bounds().unwrap_or_default().center();
let (from, to) = t.kind.path_span().unwrap_or((0.0, 1.0));
// On an open path the text may start before the path's start: the span runs from there, so
// Dynamic Text fills it to the end bracket, and the drawn text runs from the path's start to the
// end bracket.
let from = t.kind.path_text_start().unwrap_or(from);
let lead = t.kind.starts_before_path();
let s_start = from * ap.len();
let avail = (to - from) * ap.len();
let spacing = if t.path_spacing.is_finite() { t.path_spacing } else { 0.0 };
// Optical Margin Alignment and Roman Hanging Punctuation: the brackets are the margins, and the
// glyphs at the line's ends hang outside them by `hang_l` and `hang_r`, measured along the path.
// The line is aligned in a span that much longer at each end, and the glyphs that hang at the
// end (`hung_r` of them) do not make it overflow past the end bracket. On an open path a hang
// stops at the path's end. On a closed path the two hangs together take at most the stretch
// between the end and start brackets: the end where the line is placed takes its share first.
// A centered line's ends each get up to half of it, and either end takes what the other leaves.
// The hangs are measured on the steps the glyphs take where the line is placed. A right-to-left
// line is read from right to left ([`optical_hangs_rtl`]); in vertical type `sg` is in text order.
let hanging = t.optical_margin || para.roman_hanging;
let hangs = |sg: &[SGlyph], steps: &[f64]| {
if !hanging {
return (0.0, 0.0, 0);
}
let share: fn(&SGlyph) -> f64 = if t.optical_margin { optical_share } else { roman_share };
// A list marker (the glyphs of length 0) does not hang: it is counted with no width.
let line: Vec<(&SGlyph, f64)> = sg.iter().zip(steps).map(|(g, &step)| (g, if g.len == 0 { 0.0 } else { step })).collect();
let (l, r, _, hung_r) = if rtl { optical_hangs_rtl(&line, share) } else { optical_hangs(&line, share) };
let (l, r) = if ap.is_closed() {
let gap = (ap.len() - avail).max(0.0);
match para.justify {
j if matches!(j, Justify::Right | Justify::JustifyRight) || (rtl && j == Justify::Auto) => {
let r = r.min(gap);
(l.min(gap - r), r)
}
Justify::Center | Justify::JustifyCenter => {
let l = l.min(gap - r.min(gap * 0.5));
(l, r.min(gap - l))
}
_ => {
let l = l.min(gap);
(l, r.min(gap - l))
}
}
} else {
(l.min(s_start.max(0.0)), r.min((ap.len() - s_start - avail).max(0.0)))
};
(l, r, hung_r)
};
// Where a line that takes `w` along the path starts, aligned in the span with the hangs.
let align = |w: f64, (l, r, _): (f64, f64, usize)| {
let (lo, room) = (s_start - l, avail + l + r);
match para.justify {
Justify::Auto if rtl => lo + (room - w).max(0.0),
Justify::Center | Justify::JustifyCenter => lo + ((room - w) * 0.5).max(0.0),
Justify::Right | Justify::JustifyRight => lo + (room - w).max(0.0),
_ => lo,
}
};
// The glyphs `sg` arranged on the path: their steps, where the first starts, and the hangs.
let arrange = |sg: &[SGlyph]| {
#[cfg(test)]
ARRANGEMENTS.set(ARRANGEMENTS.get() + 1);
let mut steps = path_steps(&ap, sg, s_start, spacing);
// Where the line starts when its glyphs take `steps`.
let place = |steps: &[f64], hung| align(steps.iter().sum(), hung);
let mut hung = hangs(sg, &steps);
let mut s0 = place(&steps, hung);
if spacing != 0.0 && s0 != s_start {
// Spaced from where the alignment puts them, the curve under them is another. That
// changes the glyphs' steps, so what the line takes and what hangs, and the line is
// placed again from the new steps until it stays where it is (at most 8 times).
steps = path_steps(&ap, sg, s0, spacing);
for _ in 0..8 {
hung = hangs(sg, &steps);
let moved = place(&steps, hung);
if (moved - s0).abs() < 1e-9 {
break;
}
s0 = moved;
steps = path_steps(&ap, sg, s0, spacing);
}
}
(steps, s0, hung)
};
// How many of the arranged glyphs fit before one runs past the end bracket (with the hang).
let fitting = |steps: &[f64], s0: f64, (hang_l, hang_r, hung_r): (f64, f64, usize)| {
let (lo, room) = (s_start - hang_l, avail + hang_l + hang_r);
let mut x = 0.0;
steps
.iter()
.enumerate()
.take_while(|&(k, &step)| {
let end = if k + hung_r >= steps.len() { room } else { room - hang_r };
let fit = s0 + x + step - lo <= end + 1e-6;
x += step;
fit
})
.count()
};
let (mut steps, mut s0, mut hung) = arrange(&sg);
// What the whole text takes along the path and what the span holds: Dynamic Text's first guess.
cx.out.path_fill = Some((steps.iter().sum(), avail + hung.0 + hung.1));
// Where the text that fits ends: before the first glyph that doesn't, which threaded text
// flows on from, as from the last line of area type.
let mut fits = text_len;
// Right-to-left text that overflows keeps the start of its text, not what comes first in visual
// order: the longest start, in reading order, whose glyphs fit in visual order is laid out.
if shaped.iter().any(|(_, bidi, _)| bidi.is_some()) && fitting(&steps, s0, hung) < sg.len() {
// Whether the text before byte `cut` fits, arranged as it would be laid out.
let fits_before = |cut: usize| {
let sg = visual(cut);
let (steps, s0, hung) = arrange(&sg);
fitting(&steps, s0, hung) == sg.len()
};
// The byte at which each start of the text ends, in reading order.
let mut starts: Vec<usize> = shaped.iter().flat_map(|(_, _, glyphs)| glyphs).map(|g| g.byte).collect();
starts.dedup();
let first = starts.first().copied().unwrap_or(text_len);
// On one straight segment the path doesn't turn, so spacing changes no step.
let straight = matches!(path.to_bezpath().elements(), [PathEl::MoveTo(_), PathEl::LineTo(_)]);
#[cfg(test)]
let each_start = EACH_START.get();
#[cfg(not(test))]
let each_start = false;
fits = if each_start {
starts.iter().rev().copied().find(|&byte| fits_before(byte)).unwrap_or(first)
} else if (spacing == 0.0 || straight) && !hanging {
// Each glyph takes its advance wherever the line is placed.
longest_fitting_start(&shaped, first, |w, far| align(w, (0.0, 0.0, 0)) - s_start + far <= avail + 1e-6)
} else if sg.iter().all(|g| g.adv >= 0.0) {
// No glyph takes the line back: a start fits when a longer one does. The text before
// `starts[fit]` fits; before `starts[over]` (the whole text at the end) it doesn't.
let (mut fit, mut over) = (0, starts.len());
while over - fit > 1 {
let mid = (fit + over) / 2;
if fits_before(starts.get(mid).copied().unwrap_or(text_len)) {
fit = mid;
} else {
over = mid;
}
}
starts.get(fit).copied().unwrap_or(text_len)
} else {
// A glyph that takes the line back can make a start fit where a shorter one doesn't:
// the starts that can fit the path however their glyphs are spaced are tried from the
// longest, at most `PATH_START_TRIES` of them before a binary search over the rest.
longest_start_tried(&starts_that_can_fit(&shaped, spacing, ap.len()), PATH_START_TRIES, &fits_before).unwrap_or(first)
};
cx.out.overflow = true;
sg = visual(fits);
(steps, s0, hung) = arrange(&sg);
}
let fit = fitting(&steps, s0, hung);
if fit < sg.len() {
cx.out.overflow = true;
fits = sg.get(fit..).and_then(|rest| rest.iter().map(|g| g.byte).min()).unwrap_or(text_len);
}
// Align to Path: how far down (glyph space) a glyph moves to run the top of its em box, half the
// height of the top of its H or the bottom of its font's bounding box along the path instead of its
// baseline, each glyph by its own face, size and vertical scale. In vertical type the glyph
// moves half its em (with its horizontal scale) for Ascender and Descender, and stays for Center.
// An inline graphic moves as a character of its run would, by its run's vertical scale in both.
let vertical = cx.vertical;
let rise_of = |g: &SGlyph| {
let em = g.face.units_per_em() * if vertical { g.sx } else { g.sy };
let h = if vertical { PathAlignHeights { top: 0.5, bottom: -0.5, center: 0.0 } } else { g.face.path_align_heights() };
match t.path_align {
PathAlign::Baseline => 0.0,
PathAlign::Ascender => h.top * em,
PathAlign::Descender => h.bottom * em,
PathAlign::Center => h.center * em,
}
};
let mut x = 0.0;
for (g, &step) in sg.iter().zip(&steps).take(fit) {
let rise = rise_of(g);
let s = s0 + x;
let (p, dir) = ap.at(s + step * 0.5);
let angle = dir.y.atan2(dir.x);
let half = Affine::translate((-g.adv * 0.5, rise));
// Glyph space: x along the advance, y down from the baseline; `pre` maps it onto the path.
let pre = match t.path_effect {
PathEffect::Rainbow => Affine::translate(p.to_vec2()) * Affine::rotate(angle) * half,
// x axis along the tangent, y axis stays vertical.
PathEffect::Skew => Affine::translate(p.to_vec2()) * Affine::new([dir.x, dir.y, 0.0, 1.0, 0.0, 0.0]) * half,
// x axis stays horizontal (facing the path's direction), y axis perpendicular to the path.
PathEffect::Ribbon3d => {
let sx = if dir.x < 0.0 { -1.0 } else { 1.0 };
Affine::translate(p.to_vec2()) * Affine::new([sx, 0.0, -dir.y * sx, dir.x * sx, 0.0, 0.0]) * half
}
PathEffect::StairStep => Affine::translate(ap.at(s).0.to_vec2()) * Affine::translate((0.0, rise)),
// x axis along the tangent; vertical edges point at the path's centre (kept on the glyph's
// up side, and never closer than ~17° to the baseline so glyphs stay legible).
PathEffect::Gravity => {
let n = Vec2::new(dir.y, -dir.x);
let mut up = p - centre;
up = if up.hypot() < 1e-9 { n } else { up / up.hypot() };
if up.dot(n) < 0.0 {
up = -up;
}
if up.dot(n) < 0.3 {
let along = up - n * up.dot(n);
up = n * 0.3 + along / along.hypot().max(1e-9) * (1.0 - 0.09f64).sqrt();
}
Affine::translate(p.to_vec2()) * Affine::new([dir.x, dir.y, -up.x, -up.y, 0.0, 0.0]) * half
}
};
// The caret's baseline moves with the type.
let origin = p - dir * (g.adv * 0.5) + Vec2::new(-dir.y, dir.x) * rise;
// A list marker's glyphs (the only glyphs here with no length) are in a row at the byte of
// their paragraph's start.
if g.len == 0 {
let at = cx.out.glyphs.len();
let starts_paragraph = |b: usize| paras.iter().position(|p| p.start == b);
match cx.out.markers.last_mut() {
Some(m) if m.glyphs.end == at && cx.out.glyphs.get(m.glyphs.start).is_some_and(|h| h.byte == g.byte) => m.glyphs.end = at + 1,
_ => {
if let Some(text) = starts_paragraph(g.byte).and_then(|pi| markers.get(pi)).and_then(Option::as_ref) {
cx.out.markers.push(ListMarker { glyphs: at..at + 1, tab: at, text: text.clone() });
}
}
}
if let Some(m) = cx.out.markers.last_mut().filter(|m| m.glyphs.end == at + 1 && g.ch == '\t') {
m.tab = at;
}
}
let at = cx.out.glyphs.len();
cx.emit(g, pre, origin, angle, g.adv, 0);
record_scale(cx, g, &scales);
let hidden = hide_before_open_path(cx, &ap, lead, at, s + step * 0.5, rise);
if !hidden && let Some(mark) = repeat.take_if(|&mut (byte, _)| g.len > 0 && g.byte == byte) {
cx.out.repeat_marks.push(mark);
}
// A glyph of a script whose letters join is bent along a curved path (Rainbow), so its
// joining strokes meet its neighbours' instead of standing off the curve.
if !hidden && t.path_effect == PathEffect::Rainbow && g.cursive && !cx.vertical && g.inline.is_none() {
let bend = GlyphBend { s, step, advance: g.adv, rise };
if let Some(last) = cx.out.glyphs.last_mut()
&& last.image.is_none()
&& last.colour.is_none()
&& let Some(bent) = bend_outline(&last.outline, pre, &ap, &bend)
{
last.outline = bent;
last.bend = Some(bend);
}
}
x += step;
}
let (ps, _) = ap.at(s0);
let (pe, _) = ap.at(s0 + x);
cx.out.lines.push(LineInfo {
rtl,
baseline: ps.y,
x0: ps.x,
x1: pe.x,
trailing: 0.0,
ascent: m.0,
descent: m.1,
first_baseline: 0.0,
start: 0,
end: fits,
glyph_start: 0,
glyph_end: cx.out.glyphs.len(),
avail: (0.0, ap.len()),
region: 0,
});
}
#[cfg(test)]
mod tests {
use super::longest_start_tried;
/// The longest start that fits is found among the ones tried; past the tries, a binary search
/// finds one that fits, with as many more tries as halvings of the rest.
#[test]
fn starts_are_tried_from_the_longest_then_searched() {
let starts: Vec<usize> = (0..1000).collect();
// Every start up to 600 fits, and so does 990.
let fits = |byte: usize| byte <= 600 || byte == 990;
let mut tried = 0;
let found = longest_start_tried(&starts, 32, |byte| {
tried += 1;
fits(byte)
});
assert_eq!((found, tried), (Some(990), 10));
tried = 0;
let found = longest_start_tried(&starts, 8, |byte| {
tried += 1;
fits(byte)
});
assert_eq!(found, Some(600));
assert!(tried <= 8 + 10, "{tried} tries");
// With fewer starts than tries, each is tried.
assert_eq!(longest_start_tried(&starts[..5], 32, |byte| byte == 0), Some(0));
assert_eq!(longest_start_tried(&[], 32, |_| true), None);
}
}
No file is open. Choose one in the tree, or press Ctrl+O (⌘O on a Mac) to find one by name.
Syntax highlighting could not load. The unmodified read-only text remains available above.