Skip to content

armgit / macro

Public Imported from GitHub
0

Macro is a unified workspace for teams: email, chat, docs, tasks, agents, calls, and CRM — @-linked together with shared AI memory.

24.2 KB
Raw Blame
//! Line breaking and line boxes.
//!
//! Word breaks greedily: words are added until the next one would cross the
//! right indent, spaces hang past it, and a word longer than the line is
//! broken where it overflows. Tabs jump to the next stop (custom stops, the
//! hanging indent, then default stops after the last custom one); right,
//! center and decimal stops align the text that follows them. In justified
//! paragraphs, Word 2013 and later also keep a word that crosses the edge
//! slightly by shrinking the line's spaces.

use super::bidi;
use super::inline::{Inline, Kind, device_metrics};
use crate::model::props::{Align, LineSpacing, ParaProps, TabAlign, TabLeader};

/// How a line ended.
#[derive(Clone, Copy, Debug, PartialEq, Eq)]
pub enum LineEnd {
    /// The text wrapped.
    Wrap,
    /// A manual line break.
    Break,
    /// A page break.
    PageBreak,
    /// A column break.
    ColumnBreak,
    /// The end of the paragraph.
    Paragraph,
}

/// One laid-out line.
#[derive(Clone, Debug, PartialEq)]
pub struct Line {
    /// First cluster.
    pub start: usize,
    /// One past the last cluster.
    pub end: usize,
    /// Top, relative to the paragraph's first line top (points).
    pub top: f32,
    /// Height (points).
    pub height: f32,
    /// Baseline below the line top (points).
    pub baseline: f32,
    /// Left edge of the line's text area (points from the text area left).
    pub left: f32,
    /// Right edge of the line's text area.
    pub right: f32,
    /// Width of the content without trailing spaces.
    pub width: f32,
    /// How the line ended.
    pub ends: LineEnd,
    /// The line ends at a soft hyphen that shows as a hyphen.
    pub hyphen: bool,
}

/// A paragraph's lines plus cluster positions.
#[derive(Clone, Debug, Default)]
pub struct Lines {
    /// The lines.
    pub lines: Vec<Line>,
    /// X of each cluster from the text area's left edge (points).
    pub x: Vec<f32>,
    /// Final advance of each cluster (after tabs and justification).
    pub adv: Vec<f32>,
    /// Leaders of tab clusters.
    pub leaders: Vec<(usize, TabLeader)>,
    /// Total height of the lines.
    pub height: f32,
}

/// What line layout needs to know about the paragraph's surroundings.
#[derive(Clone, Copy, Debug)]
pub struct LineCtx<'a> {
    /// Paragraph properties.
    pub props: &'a ParaProps,
    /// Width of the text area (column or cell content).
    pub width: f32,
    /// Default tab interval.
    pub default_tab: f32,
    /// Lines ending in manual breaks are not stretched when justified.
    pub no_expand_shift_return: bool,
    /// Document grid pitch when lines snap to it.
    pub grid: Option<f32>,
    /// Justified lines may shrink their spaces to fit more text (Word 2013
    /// and later).
    pub shrink_spaces: bool,
    /// A paragraph mark right after a page break stays on the break's line
    /// rather than going to the next page alone.
    pub mark_with_page_break: bool,
    /// Page x of the text area's left edge, when known. Word places lines
    /// in device units, which decides where the first tab of a line that
    /// starts on a default tab stop goes.
    pub origin: Option<f32>,
}

/// Space a wrapping float takes from a line: (left inset, right inset) for
/// a line spanning `top..bottom` (paragraph-relative points).
pub type Exclusion<'a> = &'a dyn Fn(f32, f32) -> (f32, f32);

const EPS: f32 = 0.01;

/// How much Word 2013 and later may shrink a space to squeeze one more word
/// into a justified line: a share of the space's glyph, without letter
/// spacing.
const SPACE_SHRINK: f32 = 0.25;
/// The share of a space's whole advance that text Word measures with a
/// device font (scaled or kerned runs) may lose: it squeezes less, as the
/// line ends of the UN's New York documents show.
const DEVICE_SPACE_SHRINK: f32 = 0.21;
/// Word only shrinks spaces for a word that crosses the right edge by less
/// than this fraction of its own width.
const MAX_WORD_OVERFLOW: f32 = 0.35;

struct Stop {
    pos: f32,
    align: TabAlign,
    leader: TabLeader,
    /// Set in the paragraph's tabs (not a default stop).
    custom: bool,
}

/// A length in twips in Word's device units (1/600 inch), rounded half to
/// even.
fn device_units(twips: i64) -> i64 {
    let n = twips * 5;
    let (q, r) = (n.div_euclid(12), n.rem_euclid(12));
    match (2 * r).cmp(&12) {
        std::cmp::Ordering::Greater => q + 1,
        std::cmp::Ordering::Equal => q + (q & 1),
        std::cmp::Ordering::Less => q,
    }
}

/// Whether a line starting `x` points into a text area whose left edge is
/// at page x `origin` really starts before that point in Word: Word starts
/// it at the rounded edge plus the rounded indent, and places tab stops at
/// the rounded sum (A4 pages with 2 cm margins and indents start a device
/// unit early).
fn starts_early(origin: f32, x: f32) -> bool {
    let twips = |v: f32| (v * 20.0).round() as i64;
    let (origin, x) = (twips(origin), twips(x));
    device_units(origin) + device_units(x) < device_units(origin + x)
}

/// The stop a tab at `x` goes to; `line_start` when nothing comes before it
/// on its line.
fn next_stop(x: f32, ctx: &LineCtx<'_>, first_line: bool, line_start: bool) -> Stop {
    let p = ctx.props;
    let mut best: Option<Stop> = None;
    for s in &p.tabs {
        if s.align == TabAlign::Bar || s.pos <= x + EPS {
            continue;
        }
        if best.as_ref().is_none_or(|b| s.pos < b.pos) {
            best = Some(Stop {
                pos: s.pos,
                align: s.align,
                leader: s.leader,
                custom: true,
            });
        }
    }
    // A hanging indent is an implicit stop on the first line.
    if first_line
        && p.ind_first < 0.0
        && p.ind_left > x + EPS
        && best.as_ref().is_none_or(|b| p.ind_left < b.pos)
    {
        best = Some(Stop {
            pos: p.ind_left,
            align: TabAlign::Left,
            leader: TabLeader::None,
            custom: false,
        });
    }
    if let Some(b) = best {
        return b;
    }
    // Default stops, only after the last custom stop.
    let interval = ctx.default_tab.max(1.0);
    let last_custom = p
        .tabs
        .iter()
        .filter(|s| s.align != TabAlign::Bar)
        .map(|s| s.pos)
        .fold(f32::MIN, f32::max);
    let from = x.max(last_custom);
    let mut pos = ((from + EPS) / interval).floor() * interval + interval;
    // A line starting on a default stop that Word starts just before it:
    // its first tab goes to that stop.
    let on_stop = x > EPS && ((x / interval).round() * interval - x).abs() < EPS;
    if line_start
        && on_stop
        && last_custom < x - EPS
        && ctx.origin.is_some_and(|o| starts_early(o, x))
    {
        pos = x;
    }
    Stop {
        pos,
        align: TabAlign::Left,
        leader: TabLeader::None,
        custom: false,
    }
}

/// Width of the clusters after `from` up to the next tab or line end, and
/// of the part before a decimal separator.
fn segment_width(inline: &Inline, from: usize) -> (f32, f32) {
    let mut w = 0.0;
    let mut before_decimal: Option<f32> = None;
    for c in &inline.clusters[from..] {
        match c.kind {
            Kind::Tab | Kind::LineBreak | Kind::PageBreak | Kind::ColumnBreak | Kind::End => break,
            _ => {}
        }
        if before_decimal.is_none() && (c.ch == '.' || c.ch == ',') && c.kind == Kind::Text {
            before_decimal = Some(w);
        }
        w += c.advance;
    }
    (w, before_decimal.unwrap_or(w))
}

/// How much Word may shrink each cluster when it squeezes a justified line
/// (points; only spaces shrink).
fn squeeze_room(inline: &Inline) -> Vec<f32> {
    inline
        .clusters
        .iter()
        .map(|c| {
            if c.kind != Kind::Space {
                return 0.0;
            }
            let Some(style) = inline.runs.get(usize::from(c.run)) else {
                return c.advance * SPACE_SHRINK;
            };
            let props = &style.props;
            if device_metrics(props, c.size) {
                c.advance * DEVICE_SPACE_SHRINK
            } else {
                (c.advance - props.spacing).max(0.0) * SPACE_SHRINK
            }
        })
        .collect()
}

/// Width of the unbreakable run of clusters starting at `from`: up to and
/// including the next cluster that allows a break after it, stopping
/// before spaces, tabs and breaks.
fn word_width(inline: &Inline, adv: &[f32], from: usize) -> f32 {
    let mut w = 0.0;
    for (k, c) in inline.clusters.iter().enumerate().skip(from) {
        match c.kind {
            Kind::Space
            | Kind::Tab
            | Kind::LineBreak
            | Kind::PageBreak
            | Kind::ColumnBreak
            | Kind::End
            | Kind::SoftHyphen => break,
            _ => {}
        }
        w += adv[k];
        if c.brk == super::inline::Brk::After {
            break;
        }
    }
    w
}

fn is_content(kind: Kind) -> bool {
    matches!(
        kind,
        Kind::Text | Kind::Object(_) | Kind::Tab | Kind::Separator(_)
    )
}

/// Breaks a paragraph into lines.
pub fn break_lines(inline: &Inline, ctx: &LineCtx<'_>, exclude: Option<Exclusion<'_>>) -> Lines {
    break_lines_from(inline, ctx, exclude, 0)
}

/// Breaks the rest of a paragraph, from cluster `start` on, into lines (a
/// paragraph going on in a column of another width). The lines' tops
/// count from the first of them.
pub fn break_lines_from(
    inline: &Inline,
    ctx: &LineCtx<'_>,
    exclude: Option<Exclusion<'_>>,
    start: usize,
) -> Lines {
    let p = ctx.props;
    let n = inline.clusters.len();
    let shrink = ctx.shrink_spaces && p.jc == Align::Justify;
    let mut adv: Vec<f32> = inline.clusters.iter().map(|c| c.advance).collect();
    let squeezable = squeeze_room(inline);
    for (i, c) in inline.clusters.iter().enumerate() {
        if let Kind::Separator(continuation) = c.kind {
            adv[i] = if continuation {
                ctx.width
            } else {
                144.0f32.min(ctx.width)
            };
        }
    }
    let mut x_pos = vec![0.0f32; n];
    let mut leaders: Vec<(usize, TabLeader)> = Vec::new();
    let mut lines: Vec<Line> = Vec::new();
    let mut top = 0.0f32;
    let mut i = start.min(n);
    while i < n {
        let first = lines.is_empty() && start == 0;
        let mut left = p.ind_left + if first { p.ind_first } else { 0.0 };
        let mut right = ctx.width - p.ind_right;
        if let Some(ex) = exclude {
            // Estimate the line's height with the paragraph mark's font.
            let (l, r) = ex(top, top + 12.0);
            left = left.max(l);
            right = right.min(ctx.width - r);
        }
        if right - left < 12.0 {
            right = left + 12.0;
        }
        let mut x = left;
        let mut j = i;
        let mut last_break: Option<usize> = None;
        let mut ends = LineEnd::Wrap;
        let mut has_content = false;
        let mut line_leaders: Vec<(usize, TabLeader)> = Vec::new();
        // How much the spaces since the last tab may shrink (justification
        // only adjusts those).
        let mut room = 0.0f32;
        while j < n {
            let c = &inline.clusters[j];
            match c.kind {
                Kind::LineBreak | Kind::PageBreak | Kind::ColumnBreak | Kind::End => {
                    x_pos[j] = x;
                    ends = match c.kind {
                        Kind::LineBreak => LineEnd::Break,
                        Kind::PageBreak => LineEnd::PageBreak,
                        Kind::ColumnBreak => LineEnd::ColumnBreak,
                        _ => LineEnd::Paragraph,
                    };
                    j += 1;
                    if ends == LineEnd::PageBreak
                        && ctx.mark_with_page_break
                        && inline.clusters[j..]
                            .iter()
                            .all(|c| matches!(c.kind, Kind::Zero | Kind::End))
                    {
                        // Nothing but the paragraph mark follows the break:
                        // the mark stays with it.
                        x_pos[j..n].fill(x);
                        j = n;
                    }
                    break;
                }
                Kind::Tab => {
                    let stop = match c.ptab {
                        Some((pos, align)) => {
                            let edge_left = if pos < 0.0 { p.ind_left } else { 0.0 };
                            let edge_right = if pos < 0.0 {
                                ctx.width - p.ind_right
                            } else {
                                ctx.width
                            };
                            Stop {
                                pos: match align {
                                    TabAlign::Center => (edge_left + edge_right) / 2.0,
                                    TabAlign::Right => edge_right,
                                    _ => edge_left,
                                },
                                align,
                                leader: TabLeader::None,
                                custom: false,
                            }
                        }
                        None => next_stop(x, ctx, first, !has_content),
                    };
                    // A tab to a stop of its own past the right edge goes
                    // to the next line, as a word that does not fit would.
                    if stop.custom
                        && stop.align == TabAlign::Left
                        && stop.pos > right + EPS
                        && has_content
                    {
                        ends = LineEnd::Wrap;
                        break;
                    }
                    let (seg, before_dec) = segment_width(inline, j + 1);
                    let target = match stop.align {
                        TabAlign::Right => stop.pos - seg,
                        TabAlign::Center => stop.pos - seg / 2.0,
                        TabAlign::Decimal => stop.pos - before_dec,
                        _ => stop.pos,
                    };
                    adv[j] = (target - x).max(0.0);
                    if stop.leader != TabLeader::None {
                        line_leaders.push((j, stop.leader));
                    }
                    x_pos[j] = x;
                    x += adv[j];
                    has_content = true;
                    last_break = Some(j);
                    room = 0.0;
                }
                Kind::Space => {
                    x_pos[j] = x;
                    x += adv[j];
                    room += squeezable[j];
                    last_break = Some(j);
                }
                Kind::Zero | Kind::Anchor(_) => x_pos[j] = x,
                Kind::SoftHyphen => {
                    x_pos[j] = x;
                    last_break = Some(j);
                }
                _ => {
                    // How far a word may cross the right edge when shrinking
                    // the spaces before it can pull it back in.
                    let allowance = if shrink && room > 0.0 && x + adv[j] > right + EPS {
                        let word = word_width(inline, &adv, last_break.map_or(i, |b| b + 1));
                        room.min(word * MAX_WORD_OVERFLOW)
                    } else {
                        0.0
                    };
                    if x + adv[j] > right + allowance + EPS && has_content {
                        ends = LineEnd::Wrap;
                        if let Some(b) = last_break {
                            j = b + 1;
                        }
                        break;
                    }
                    x_pos[j] = x;
                    x += adv[j];
                    has_content |= is_content(c.kind);
                    if c.brk == super::inline::Brk::After {
                        last_break = Some(j);
                    }
                }
            }
            j += 1;
        }
        if j <= i {
            j = i + 1;
        }
        // Zero-width clusters right after a wrap stay on this line.
        while ends == LineEnd::Wrap
            && j < n
            && matches!(inline.clusters[j].kind, Kind::Zero | Kind::Anchor(_))
        {
            x_pos[j] = x_pos[j - 1] + adv[j - 1];
            j += 1;
        }
        let hyphen = ends == LineEnd::Wrap && inline.clusters[j - 1].kind == Kind::SoftHyphen;
        // Content width: up to the last cluster that is not a trailing space.
        let mut content_end = i;
        for k in i..j {
            if !matches!(
                inline.clusters[k].kind,
                Kind::Space
                    | Kind::Zero
                    | Kind::End
                    | Kind::LineBreak
                    | Kind::PageBreak
                    | Kind::ColumnBreak
                    | Kind::Anchor(_)
                    | Kind::SoftHyphen
            ) {
                content_end = k + 1;
            }
        }
        let content_right = if content_end > i {
            x_pos[content_end - 1] + adv[content_end - 1]
        } else {
            left
        };
        // Alignment and justification.
        let last_line = matches!(
            ends,
            LineEnd::Paragraph | LineEnd::PageBreak | LineEnd::ColumnBreak
        );
        let stretch = match p.jc {
            Align::Justify => !(last_line || ends == LineEnd::Break && ctx.no_expand_shift_return),
            Align::Distribute => true,
            _ => false,
        };
        let last_tab = (i..content_end)
            .rev()
            .find(|&k| inline.clusters[k].kind == Kind::Tab)
            .map_or(i, |k| k + 1);
        let spaces: Vec<usize> = (last_tab..content_end)
            .filter(|&k| inline.clusters[k].kind == Kind::Space)
            .collect();
        // Text that only fits with shrunk spaces shrinks them, on any line
        // and never by more than they may shrink.
        let squeeze = shrink && right - content_right < -EPS && !spaces.is_empty();
        let slack = if squeeze {
            let room: f32 = spaces.iter().map(|&k| squeezable[k]).sum();
            (right - content_right).max(-room)
        } else {
            (right - content_right).max(0.0)
        };
        if (stretch && slack > EPS) || squeeze {
            if !spaces.is_empty() {
                let each = slack / spaces.len() as f32;
                let mut shift = 0.0;
                for k in last_tab..j {
                    x_pos[k] += shift;
                    if spaces.binary_search(&k).is_ok() {
                        adv[k] += each;
                        shift += each;
                    }
                }
            } else if p.jc == Align::Distribute && content_end > last_tab + 1 {
                let gaps = (content_end - last_tab - 1) as f32;
                let each = slack / gaps;
                for (g, k) in (last_tab..j).enumerate() {
                    x_pos[k] += each * (g.min(content_end - last_tab - 1)) as f32;
                }
            }
        } else if matches!(p.jc, Align::Center | Align::Right) && slack > EPS {
            let shift = if p.jc == Align::Center {
                slack / 2.0
            } else {
                slack
            };
            for x in &mut x_pos[i..j] {
                *x += shift;
            }
        }
        if !inline.levels.is_empty() {
            visual_order(inline, i, j, ctx, &mut x_pos, &adv);
        }
        leaders.extend(line_leaders);
        let (mut height, mut baseline) = line_height(inline, i, j, ctx, &adv);
        if matches!(ends, LineEnd::PageBreak | LineEnd::ColumnBreak)
            && !has_content
            && (j < n || ends == LineEnd::PageBreak)
        {
            // A paragraph that starts with a break starts after it, and a
            // page that ends with a bare break has nothing below it: the
            // break takes no room where it is.
            height = 0.0;
            baseline = 0.0;
        }
        lines.push(Line {
            start: i,
            end: j,
            top,
            height,
            baseline,
            left,
            right,
            width: content_right - left + if squeeze { slack } else { 0.0 },
            ends,
            hyphen,
        });
        top += height;
        i = j;
    }
    Lines {
        height: top,
        lines,
        x: x_pos,
        adv,
        leaders,
    }
}

/// Puts a line of bidirectional text (clusters `start..end`, laid out
/// left to right in logical order) in visual order: a right-to-left
/// paragraph's line mirrored to start at the right, and runs against the
/// paragraph's direction reversed in place.
fn visual_order(
    inline: &Inline,
    start: usize,
    end: usize,
    ctx: &LineCtx<'_>,
    x: &mut [f32],
    adv: &[f32],
) {
    let base = u8::from(ctx.props.bidi);
    let mut levels = inline.levels[start..end].to_vec();
    // The line's trailing whitespace is at the paragraph's level.
    for k in (start..end).rev() {
        if !matches!(
            inline.clusters[k].kind,
            Kind::Space
                | Kind::Zero
                | Kind::End
                | Kind::LineBreak
                | Kind::PageBreak
                | Kind::ColumnBreak
                | Kind::Anchor(_)
                | Kind::SoftHyphen
        ) {
            break;
        }
        levels[k - start] = base;
    }
    bidi::reorder(
        &mut x[start..end],
        &adv[start..end],
        &levels,
        base,
        (0.0, ctx.width),
    );
}

/// Height and baseline of a line spanning clusters `start..end`.
fn line_height(
    inline: &Inline,
    start: usize,
    end: usize,
    ctx: &LineCtx<'_>,
    adv: &[f32],
) -> (f32, f32) {
    // Each font's external leading sits above its ascent: the line's top
    // part is the largest of them, its bottom part the largest descent.
    let mut above: f32 = 0.0;
    let mut object: f32 = 0.0;
    let mut descent: f32 = 0.0;
    let mut leading: f32 = 0.0;
    let mut seen = false;
    let mut text = false;
    for c in &inline.clusters[start..end] {
        let style = &inline.runs[c.run as usize];
        match c.kind {
            Kind::Zero | Kind::Anchor(_) => continue,
            Kind::Object(o) => {
                let d = &inline.objects[o as usize];
                object = object.max(d.height + d.effect[1] + d.effect[3]);
                seen = true;
            }
            Kind::End => {
                // The paragraph mark sizes a line without text (empty, or
                // only pictures, which sit on its baseline); text lines take
                // their height from the text alone.
                if text || (c.ch == '\u{0}' && seen) {
                    continue;
                }
                above = above.max(style.leading + style.ascent);
                descent = descent.max(style.descent);
                leading = leading.max(style.leading);
                seen = true;
            }
            _ => {
                above = above.max(style.leading + style.ascent);
                descent = descent.max(style.descent);
                leading = leading.max(style.leading);
                seen = true;
                text = true;
            }
        }
    }
    let _ = adv;
    if !seen {
        // A line of hidden content: the paragraph mark's metrics.
        let style = &inline.runs[inline.clusters[end - 1].run as usize];
        above = style.leading + style.ascent;
        descent = style.descent;
        leading = style.leading;
    }
    // Pictures stand on the baseline below the text's leading.
    let top = above.max(object + leading);
    let natural = top + descent;
    let (mut height, mut baseline) = match ctx.props.line {
        LineSpacing::Auto(m) if m >= 1.0 => {
            // Extra space of multiple line spacing goes below the text.
            (natural * m, top)
        }
        LineSpacing::Auto(m) => {
            // Reduced spacing takes the space from above the text.
            let h = natural * m.max(0.05);
            (h, h - descent)
        }
        LineSpacing::Exact(v) => (v, v - descent * (v / natural.max(0.01)).min(1.0)),
        LineSpacing::AtLeast(v) => {
            let h = natural.max(v);
            (h, h - descent)
        }
    };
    if let Some(pitch) = ctx.grid
        && pitch > 1.0
        && matches!(ctx.props.line, LineSpacing::Auto(_))
    {
        let snapped = (height / pitch - 0.05).ceil().max(1.0) * pitch;
        baseline += (snapped - height) / 2.0;
        height = snapped;
    }
    (height, baseline)
}

#[cfg(test)]
mod test;