layout.rs

//! Gives dimensions and positions to a syntax tree
//!
//! All units are em, where the font size at the root of the tree is 1, and y increases
//! downward.
//! Values for vertical positions and space come from the MATH table of the font, so changing
//! the typeface also changes how formulas are typeset.
//! Stretchy delimiters and radicals are not made by stretching a glyph. They are built from the
//! size variants and assemblies that the font provides.

use crate::font::{self, Font};
use crate::math::Construction;
use crate::node::{self, Align, Class, Level, Limits, Node, Spacing, Style};
use crate::symbol;


// The style of this library (mainly its numeric values) differs slightly in some places from
// the original TeX and from KaTeX and MathJax. The space between sin and ( in sin(x) is one of
// them. All of them were decided by the author through fine adjustment.
// They must not be changed on the grounds that they differ from the original.


/// Space between symbols. As in TeX, 1/18 em counts as 1
const THIN: f64 = 3.0 / 18.0;

const MEDIUM: f64 = 4.0 / 18.0;

const THICK: f64 = 5.0 / 18.0;

/// How far the fraction rule extends past the numerator and denominator on each side
const FRACTION_PADDING: f64 = 0.12;

/// Space wanted on the inner side of a delimiter
///
/// In Latin Modern Math, the inner side bearing that a delimiter glyph has by itself is only
/// 0.057em for a parenthesis and 0.022em for a square bracket. It also hardly grows as the
/// glyph gets larger, so the taller the delimiter, the closer it looks to the content. This
/// value adds the missing space
const FENCE_ROOM: f64 = 0.12;

/// How far a script at the side is kept from its base. Proportional to how tall the base is
///
/// The right side bearing of a glyph does not grow when the glyph is taller. For a tall symbol
/// such as an integral, the same bearing is too small in proportion, and the scripts look too
/// close to the base
const SCRIPT_GAP: f64 = 0.04;

/// Lower limit of the distance between a script and its base
///
/// For a short character the proportional part is almost zero. A sequence such as x^2 then
/// looks cramped, so at least this much space is always left
const SCRIPT_GAP_MIN: f64 = 0.03;

/// How far an accent above, and a rule above or below, are kept from the content
///
/// With only the MATH table values, an accent sits directly on the character. The space for a
/// rule also looks cramped with only the font's value, so this amount is added to both
const MARK_GAP: f64 = 0.05;

/// Space between a stretchy symbol and what is placed above and below it
const EXTEND_GAP: f64 = 0.09;

/// How far a stretchy symbol extends past what is above and below it, on each side
const EXTEND_PADDING: f64 = 0.3;

/// Space between the columns of a matrix
const COLUMN_GAP: f64 = 0.6;

/// Space left at the left and right edges of a matrix
///
/// Half the space between columns is also left on the outside. Without it, a tall delimiter
/// looks too close to the column at the edge. No space is left on a side without a delimiter
const MATRIX_ROOM: f64 = COLUMN_GAP / 2.0;

/// Space between the rows of a matrix
const ROW_GAP: f64 = 0.35;

/// Space between the pairs in align. \minalignsep (10pt) from amsmath, converted to em
const ALIGN_GAP: f64 = 1.0;

/// Extra space added between the rows in align. \jot (3pt) from TeX, converted to em
const JOT: f64 = 0.3;

/// Minimum height and depth that a matrix cell takes
const ROW_HEIGHT: f64 = 0.5;

const ROW_DEPTH: f64 = 0.2;


/// How glyphs are output
///
/// This does not affect the layout. Either choice gives the same dimensions and positions.
/// Stretchy delimiters, radicals, accents above, and large operators in display are drawn as
/// outlines with either choice, because their glyphs have no character mapped to them
#[derive(Debug, Clone, Copy, PartialEq, Eq)]
pub enum Shape {
    /// Outputs glyphs as characters. The side that displays them needs the font, but the text
    /// can be selected and copied
    Text,
    /// Outputs glyphs as outlines. The side that displays them does not need the font
    Outline,
}


/// A single group whose position and dimensions are determined
#[derive(Debug, Clone, PartialEq)]
pub struct Layout {
    pub content: Content,
    /// Advance
    pub width: f64,
    /// Extent above the baseline
    pub height: f64,
    /// Extent below the baseline
    pub depth: f64,
}


/// Content of a group
#[derive(Debug, Clone, PartialEq)]
pub enum Content {
    /// A single character, where text is the character to output and glyph is its glyph ID in
    /// the font
    Glyph {
        text: String,
        glyph: u16,
        class: Class,
        size: f64,
        /// When there is no math glyph and the character is slanted to replace it
        italic: bool,
        /// When there is no math glyph and the character is made bold to replace it
        bold: bool,
        /// Vertical stretch factor
        ///
        /// It differs from 1 only when the font has no size variants.
        /// With a typeface that has them, the glyph is replaced with a size variant instead of
        /// being stretched
        stretch: f64,
    },
    /// A collection of children with their positions decided
    Group(Vec<Placed>),
    /// A filled rectangle. Used for fraction rules, radical rules, and \hline
    Rule,
}


/// A child placed in its parent
#[derive(Debug, Clone, PartialEq)]
pub struct Placed {
    /// Distance from the left edge of the parent
    pub x: f64,
    /// Downward offset from the baseline of the parent
    pub y: f64,
    pub layout: Layout,
}


/// Decides the dimensions and positions for a syntax tree
pub fn layout(node: &Node, font: &Font, size: f64, style: Style, display: bool) -> Layout {
    match node {
        Node::Symbol {text, class} => symbol_layout(font, text, *class, style, size, display),
        Node::Text(body) => text_layout(font, body, size),
        Node::Row(items) => row_layout(items, font, size, style, display),
        Node::Fraction {numerator, denominator, bar} => {
            fraction_layout(numerator, denominator, *bar, font, size, style, display)
        }
        Node::Root {index, body} => {
            root_layout(index.as_deref(), body, font, size, style, display)
        }
        Node::Scripts {base, superscript, subscript, limits} => scripts_layout(
            base,
            superscript.as_deref(),
            subscript.as_deref(),
            *limits,
            font,
            size,
            style,
            display,
        ),
        Node::Fenced {left, right, body} => {
            let inside = layout(body, font, size, style, display);

            fence(inside, left, right, font, size)
        }
        Node::Matrix {rows, left, right, align, lines, spacing} => {
            matrix_layout(rows, left, right, align, lines, *spacing, font, size, style)
        }
        Node::Styled {style: inner, body} => layout(body, font, size, *inner, display),
        Node::Operator {body} => layout(body, font, size, Style::Roman, display),
        Node::Accent {mark, body, above} => {
            accent_layout(mark, body, *above, font, size, style, display)
        }
        Node::Sized {level, body} => {
            let value = font::constant(font);
            let (inner, factor) = match level {
                Level::Display => (true, 1.0),
                Level::Text => (false, 1.0),
                Level::Script => (false, value.script_percent),
                Level::ScriptScript => (false, value.script_script_percent),
            };

            layout(body, font, size * factor, style, inner)
        }
        Node::Delimiter {text, height, ..} => sized_delimiter(font, text, height * size, size),
        Node::Extend {mark, above, below} => extend_layout(
            mark,
            above.as_deref(),
            below.as_deref(),
            font,
            size,
            style,
        ),
        Node::Line {body, above} => line_layout(body, *above, font, size, style, display),
        Node::Phantom {body, width, height} => {
            phantom_layout(body, *width, *height, font, size, style, display)
        }
    }
}


/// Used when only the height and depth are needed
pub fn measure(node: &Node, font: &Font, size: f64, style: Style, display: bool) -> (f64, f64) {
    let placed = layout(node, font, size, style, display);

    (placed.height, placed.depth)
}


/// Space put between two adjacent symbols
pub fn gap(left: Class, right: Class) -> f64 {
    if matches!(left, Class::Space(_)) || matches!(right, Class::Space(_)) {
        return 0.0;
    }

    match (normalize(left), normalize(right)) {
        (Class::Punctuation, _) => THIN,
        (Class::Ordinary, Class::Large)
        | (Class::Large, Class::Ordinary)
        | (Class::Large, Class::Large)
        | (Class::Large, Class::Open)
        | (Class::Large, Class::Close)
        | (Class::Close, Class::Large) => THIN,
        (Class::Ordinary, Class::Binary)
        | (Class::Binary, Class::Ordinary)
        | (Class::Large, Class::Binary)
        | (Class::Binary, Class::Large)
        | (Class::Binary, Class::Open)
        | (Class::Close, Class::Binary) => MEDIUM,
        (Class::Ordinary, Class::Relation)
        | (Class::Relation, Class::Ordinary)
        | (Class::Large, Class::Relation)
        | (Class::Relation, Class::Large)
        | (Class::Relation, Class::Open)
        | (Class::Relation, Class::Close)
        | (Class::Close, Class::Relation)
        | (Class::Relation, Class::Punctuation) => THICK,
        _ => 0.0,
    }
}


/// Merges the classes that are treated the same when deciding space
fn normalize(class: Class) -> Class {
    match class {
        Class::Variable => Class::Ordinary,
        Class::Function => Class::Large,
        other => other,
    }
}


/// Wraps the children and computes the overall dimensions
fn group(children: Vec<Placed>) -> Layout {
    let mut width: f64 = 0.0;
    let mut height: f64 = 0.0;
    let mut depth: f64 = 0.0;

    for child in &children {
        width = width.max(child.x + child.layout.width);
        height = height.max(child.layout.height - child.y);
        depth = depth.max(child.layout.depth + child.y);
    }

    Layout {content: Content::Group(children), width, height, depth}
}


/// A filled rectangle. Its bottom edge is on the baseline
fn rule(width: f64, thickness: f64) -> Layout {
    Layout {content: Content::Rule, width, height: thickness, depth: 0.0}
}


/// Space that has only a width
fn blank(width: f64) -> Layout {
    Layout {content: Content::Group(Vec::new()), width, height: 0.0, depth: 0.0}
}


/// Shifts the baseline down
fn shift(layout: Layout, y: f64) -> Layout {
    if y == 0.0 {
        return layout;
    }

    group(vec![Placed {x: 0.0, y, layout}])
}


/// Places a single glyph
fn glyph_layout(
    font: &Font,
    glyph: u16,
    class: Class,
    size: f64,
    text: &str,
    slant: (bool, bool),
) -> Layout {
    stretched_glyph(font, glyph, class, size, text, slant, 1.0)
}


/// Places a single glyph stretched vertically. The stretch factor is needed only when the glyph
/// is output as a character
fn stretched_glyph(
    font: &Font,
    glyph: u16,
    class: Class,
    size: f64,
    text: &str,
    slant: (bool, bool),
    stretch: f64,
) -> Layout {
    let (height, depth) = font::extent(font, glyph);
    let mut width = font::advance(font, glyph);
    let mut above = height;
    let mut below = depth;

    // A character that the typeface does not have gets glyph ID 0. Space is still left for it,
    // with an approximate size
    if glyph == 0 {
        if let Some(character) = text.chars().next() {
            let (fallback_width, fallback_height, fallback_depth) = font::fallback_metric(character);
            width = fallback_width;
            above = fallback_height;
            below = fallback_depth;
        }
    }

    Layout {
        content: Content::Glyph {
            text: text.to_string(),
            glyph,
            class,
            size,
            italic: slant.0,
            bold: slant.1,
            stretch,
        },
        width: width * size,
        height: above * size * stretch,
        depth: below * size * stretch,
    }
}


/// Picks the glyph that matches the style. A math glyph is used if there is one, and otherwise
/// the plain character is slanted to replace it
fn pick(font: &Font, character: char, style: Style) -> (u16, String, bool, bool) {
    if let Some(wanted) = symbol::styled(character, style) {
        if let Some(glyph) = font::glyph_of(font, wanted) {
            return (glyph, wanted.to_string(), false, false);
        }
    }

    let glyph = font::glyph_of(font, character).unwrap_or(0);
    let italic = matches!(style, Style::Italic);
    let bold = matches!(style, Style::Bold);

    (glyph, character.to_string(), italic, bold)
}


/// Decides the style actually used, based on the class and the given style
fn resolve(class: Class, style: Style) -> Style {
    match style {
        Style::Auto if class == Class::Variable => Style::Italic,
        Style::Auto => Style::Roman,
        other => other,
    }
}


fn symbol_layout(
    font: &Font,
    text: &str,
    class: Class,
    style: Style,
    size: f64,
    display: bool,
) -> Layout {
    if let Class::Space(width) = class {
        return blank(width * size);
    }

    let wanted = resolve(class, style);
    let mut children = Vec::new();
    let mut cursor = 0.0;

    for character in text.chars() {
        let (mut glyph, mut shown, italic, bold) = pick(font, character, wanted);

        // A large operator in display is replaced with the larger glyph that the font has.
        // The new glyph has no character mapped to it, so the text to output is left empty
        if class == Class::Large && display {
            let bigger = larger(font, glyph, font::constant(font).display_operator_min_height);

            if bigger != glyph {
                glyph = bigger;
                shown = String::new();
            }
        }

        let drawn = glyph_layout(font, glyph, class, size, &shown, (italic, bold));
        let width = drawn.width;
        children.push(Placed {x: cursor, y: 0.0, layout: drawn});
        cursor += width;
    }

    if children.len() == 1 {
        let only = children.pop().expect("there is one child");
        let placed = only.layout;

        if class == Class::Large {
            return center_on_axis(placed, font, size);
        }

        return placed;
    }

    let mut result = group(children);
    result.width = cursor;
    result
}


/// Aligns a large operator with the height of the math axis
fn center_on_axis(placed: Layout, font: &Font, size: f64) -> Layout {
    let axis = font::constant(font).axis_height * size;
    let middle = (placed.height - placed.depth) / 2.0;

    shift(placed, middle - axis)
}


/// Picks a size variant that is tall enough. If there is none, the largest one the font has
fn larger(font: &Font, glyph: u16, needed: f64) -> u16 {
    let Some(growth) = font::vertical_growth(font, glyph) else {
        return glyph;
    };

    for variant in &growth.variant {
        if variant.measure >= needed {
            return variant.glyph;
        }
    }

    growth.variant.last().map_or(glyph, |variant| variant.glyph)
}


fn text_layout(font: &Font, body: &str, size: f64) -> Layout {
    let mut children = Vec::new();
    let mut cursor = 0.0;

    for character in body.chars() {
        let glyph = font::glyph_of(font, character).unwrap_or(0);
        let shown = character.to_string();
        let drawn = glyph_layout(font, glyph, Class::Ordinary, size, &shown, (false, false));
        let width = drawn.width;
        children.push(Placed {x: cursor, y: 0.0, layout: drawn});
        cursor += width;
    }

    let mut result = group(children);
    result.width = cursor;
    result
}


fn row_layout(
    items: &[Node],
    font: &Font,
    size: f64,
    style: Style,
    display: bool,
) -> Layout {
    let mut children = Vec::new();
    let mut cursor = 0.0;
    let mut previous: Option<Class> = None;

    for item in items {
        let class = node::class_of(item);

        if let Some(left) = previous {
            cursor += gap(left, class) * size;
        }

        let placed = layout(item, font, size, style, display);
        let width = placed.width + trailing_slant(item, &placed, font) * size;
        children.push(Placed {x: cursor, y: 0.0, layout: placed});
        cursor += width;
        previous = Some(class);
    }

    let mut result = group(children);
    result.width = cursor.max(result.width);
    result
}


/// Font size of a script
fn script_size(font: &Font, size: f64) -> f64 {
    let value = font::constant(font);

    (size * value.script_percent).max(value.script_script_percent)
}


#[allow(clippy::too_many_arguments)]
fn fraction_layout(
    numerator: &Node,
    denominator: &Node,
    bar: bool,
    font: &Font,
    size: f64,
    style: Style,
    display: bool,
) -> Layout {
    let value = font::constant(font);
    let inner = if display {size} else {script_size(font, size)};
    let upper = layout(numerator, font, inner, style, false);
    let lower = layout(denominator, font, inner, style, false);
    let axis = value.axis_height * size;
    let thickness = value.fraction_rule_thickness * size;
    let mut up;
    let mut down;

    if bar {
        up = if display {
            value.fraction_numerator_display_shift_up
        } else {
            value.fraction_numerator_shift_up
        } * size;
        down = if display {
            value.fraction_denominator_display_shift_down
        } else {
            value.fraction_denominator_shift_down
        } * size;

        let upper_gap = if display {
            value.fraction_numerator_display_gap_min
        } else {
            value.fraction_numerator_gap_min
        } * size;
        let lower_gap = if display {
            value.fraction_denominator_display_gap_min
        } else {
            value.fraction_denominator_gap_min
        } * size;
        let above = (up - upper.depth) - (axis + thickness / 2.0);
        let below = (axis - thickness / 2.0) - (lower.height - down);

        if above < upper_gap {
            up += upper_gap - above;
        }

        if below < lower_gap {
            down += lower_gap - below;
        }

    } else {
        up = if display {value.stack_top_display_shift_up} else {value.stack_top_shift_up} * size;
        down = if display {
            value.stack_bottom_display_shift_down
        } else {
            value.stack_bottom_shift_down
        } * size;

        let least = if display {value.stack_display_gap_min} else {value.stack_gap_min} * size;
        let between = (up - upper.depth) - (lower.height - down);

        if between < least {
            let extra = (least - between) / 2.0;
            up += extra;
            down += extra;
        }
    }

    let padding = FRACTION_PADDING * size;
    let upper_width = upper.width;
    let lower_width = lower.width;
    let width = upper_width.max(lower_width) + 2.0 * padding;
    let mut children = vec![
        Placed {x: (width - upper_width) / 2.0, y: -up, layout: upper},
        Placed {x: (width - lower_width) / 2.0, y: down, layout: lower},
    ];

    if bar {
        children.push(Placed {
            x: 0.0,
            y: -(axis - thickness / 2.0),
            layout: rule(width, thickness),
        });
    }

    let mut result = group(children);
    result.width = width;
    result
}


/// Builds a glyph stretched vertically
///
/// It picks one of the size variants that the font has, and if that is still not enough, it
/// builds an assembly. Only with a typeface that has no size variants (one with no MATH table)
/// is the plain character stretched vertically
fn stretch_vertical(font: &Font, glyph: u16, needed: f64, size: f64) -> Layout {
    let (height, depth) = font::extent(font, glyph);
    let natural = (height + depth) * size;

    if natural >= needed || natural <= 0.0 {
        return glyph_layout(font, glyph, Class::Ordinary, size, "", (false, false));
    }

    let Some(growth) = font::vertical_growth(font, glyph) else {
        let pull = needed / natural;

        return stretched_glyph(font, glyph, Class::Ordinary, size, "", (false, false), pull);
    };

    for variant in &growth.variant {
        if variant.measure * size >= needed {
            return glyph_layout(font, variant.glyph, Class::Ordinary, size, "", (false, false));
        }
    }

    if growth.part.is_empty() {
        let last = growth.variant.last().map_or(glyph, |variant| variant.glyph);

        return glyph_layout(font, last, Class::Ordinary, size, "", (false, false));
    }

    assemble(font, growth, needed, size)
}


/// Vertical length that a glyph takes up
fn reach_of(font: &Font, glyph: u16, size: f64) -> f64 {
    let (height, depth) = font::extent(font, glyph);

    (height + depth) * size
}


/// Builds a glyph of the needed height as a vertical assembly of parts
///
/// The parts are listed from bottom to top. The extender parts are repeated a number of times,
/// and neighboring parts are joined with an overlap.
fn assemble(font: &Font, growth: &Construction, needed: f64, size: f64) -> Layout {
    let least = font::min_overlap(font) * size;
    let steady: f64 = growth
        .part
        .iter()
        .filter(|part| !part.extender)
        .map(|part| reach_of(font, part.glyph, size))
        .sum();
    let stretchy: f64 = growth
        .part
        .iter()
        .filter(|part| part.extender)
        .map(|part| reach_of(font, part.glyph, size))
        .sum();
    let extenders = growth.part.iter().filter(|part| part.extender).count();
    let fixed = growth.part.len() - extenders;
    let mut repeat = 1usize;

    // The assembly is tallest with the smallest overlap. Find the number of repeats that is
    // enough in that case
    while repeat < 200 && extenders > 0 {
        let joints = (fixed + extenders * repeat).saturating_sub(1) as f64;

        if steady + stretchy * repeat as f64 - least * joints >= needed {
            break;
        }

        repeat += 1;
    }

    let mut used = Vec::new();

    for part in &growth.part {
        let times = if part.extender {repeat} else {1};

        for _ in 0..times {
            used.push(*part);
        }
    }

    let total: f64 = used.iter().map(|part| reach_of(font, part.glyph, size)).sum();
    let joints = used.len().saturating_sub(1) as f64;
    let mut overlap = least;

    if joints > 0.0 {
        let widest = used
            .windows(2)
            .map(|pair| (pair[0].end_connector * size).min(pair[1].start_connector * size))
            .fold(f64::INFINITY, f64::min);
        overlap = ((total - needed) / joints).clamp(least, widest.max(least));
    }

    let mut children = Vec::new();
    let mut bottom = 0.0;

    for part in &used {
        let drawn = glyph_layout(font, part.glyph, Class::Ordinary, size, "", (false, false));
        let reach = drawn.height + drawn.depth;
        let y = bottom - drawn.depth;
        children.push(Placed {x: 0.0, y, layout: drawn});
        bottom -= reach - overlap;
    }

    let width = used
        .iter()
        .map(|part| font::advance(font, part.glyph) * size)
        .fold(0.0, f64::max);
    let mut result = group(children);
    result.width = width;
    result.depth = 0.0;
    result.height = total - overlap * joints;
    result
}


/// A delimiter of a fixed size, placed with its center on the math axis
fn sized_delimiter(font: &Font, text: &str, needed: f64, size: f64) -> Layout {
    match place_delimiter(font, text, needed, size) {
        Some(part) => shift(part.layout, part.y),
        None => blank(0.0),
    }
}


/// A glyph stretched horizontally to the width of the content. A stretched glyph has no
/// character mapped to it
fn stretch_horizontal(font: &Font, character: char, needed: f64, size: f64, class: Class) -> Layout {
    let plain = font::glyph_of(font, character).unwrap_or(0);
    let Some(growth) = font::horizontal_growth(font, plain) else {
        return glyph_layout(font, plain, class, size, &character.to_string(), (false, false));
    };

    for variant in &growth.variant {
        if variant.measure * size >= needed {
            let shown = if variant.glyph == plain {character.to_string()} else {String::new()};

            return glyph_layout(font, variant.glyph, class, size, &shown, (false, false));
        }
    }

    if !growth.part.is_empty() {
        return assemble_horizontal(font, growth, needed, size, class);
    }

    let last = growth.variant.last().map_or(plain, |variant| variant.glyph);
    let shown = if last == plain {character.to_string()} else {String::new()};

    glyph_layout(font, last, class, size, &shown, (false, false))
}


/// Builds a glyph of the needed width as a horizontal assembly of parts
///
/// The parts are listed from left to right. The extender parts are repeated a number of times,
/// and neighboring parts are joined with an overlap.
/// Glyphs used for accents have no advance, so lengths are measured with the MATH table values
fn assemble_horizontal(
    font: &Font,
    growth: &Construction,
    needed: f64,
    size: f64,
    class: Class,
) -> Layout {
    let least = font::min_overlap(font) * size;
    let steady: f64 = growth
        .part
        .iter()
        .filter(|part| !part.extender)
        .map(|part| part.full_advance * size)
        .sum();
    let stretchy: f64 = growth
        .part
        .iter()
        .filter(|part| part.extender)
        .map(|part| part.full_advance * size)
        .sum();
    let extenders = growth.part.iter().filter(|part| part.extender).count();
    let fixed = growth.part.len() - extenders;
    let mut repeat = 1usize;

    while repeat < 200 && extenders > 0 {
        let joints = (fixed + extenders * repeat).saturating_sub(1) as f64;

        if steady + stretchy * repeat as f64 - least * joints >= needed {
            break;
        }

        repeat += 1;
    }

    let mut used = Vec::new();

    for part in &growth.part {
        let times = if part.extender {repeat} else {1};

        for _ in 0..times {
            used.push(*part);
        }
    }

    let total: f64 = used.iter().map(|part| part.full_advance * size).sum();
    let joints = used.len().saturating_sub(1) as f64;
    let mut overlap = least;

    if joints > 0.0 {
        let widest = used
            .windows(2)
            .map(|pair| (pair[0].end_connector * size).min(pair[1].start_connector * size))
            .fold(f64::INFINITY, f64::min);
        overlap = ((total - needed) / joints).clamp(least, widest.max(least));
    }

    let mut children = Vec::new();
    let mut cursor = 0.0;
    // An accent glyph has ink only above the baseline. group raises any depth below 0 to 0,
    // so here the depth is measured without raising it. If it were raised, the accent would end
    // up too far above the content
    let mut height = f64::NEG_INFINITY;
    let mut depth = f64::NEG_INFINITY;

    for part in &used {
        let drawn = glyph_layout(font, part.glyph, class, size, "", (false, false));
        height = height.max(drawn.height);
        depth = depth.max(drawn.depth);
        children.push(Placed {x: cursor, y: 0.0, layout: drawn});
        cursor += part.full_advance * size - overlap;
    }

    let mut result = group(children);
    result.width = total - overlap * joints;
    result.height = height;
    result.depth = depth;
    result
}


/// A symbol that stretches to the width of what is placed above and below it
fn extend_layout(
    mark: &str,
    above: Option<&Node>,
    below: Option<&Node>,
    font: &Font,
    size: f64,
    style: Style,
) -> Layout {
    let small = script_size(font, size);
    let upper = above.map(|node| layout(node, font, small, style, false));
    let lower = below.map(|node| layout(node, font, small, style, false));
    let label = upper
        .as_ref()
        .map_or(0.0, |item| item.width)
        .max(lower.as_ref().map_or(0.0, |item| item.width));
    let character = mark.chars().next().unwrap_or(' ');
    let needed = label + EXTEND_PADDING * size;
    let drawn = stretch_horizontal(font, character, needed, size, Class::Relation);
    let drawn_width = drawn.width;
    let drawn_height = drawn.height;
    let drawn_depth = drawn.depth;
    let width = drawn_width.max(label);
    let gap = EXTEND_GAP * size;
    let mut children = vec![Placed {x: (width - drawn_width) / 2.0, y: 0.0, layout: drawn}];

    if let Some(item) = upper {
        let y = -(drawn_height + gap + item.depth);
        children.push(Placed {x: (width - item.width) / 2.0, y, layout: item});
    }

    if let Some(item) = lower {
        let y = drawn_depth + gap + item.height;
        children.push(Placed {x: (width - item.width) / 2.0, y, layout: item});
    }

    let mut result = group(children);
    result.width = width;
    result
}


/// Places a delimiter with its center on the math axis
fn place_delimiter(font: &Font, text: &str, needed: f64, size: f64) -> Option<Placed> {
    let character = text.chars().next()?;
    let plain = font::glyph_of(font, character)?;
    let mut drawn = stretch_vertical(font, plain, needed, size);

    // At its natural size, the delimiter can be output as a character. One that was replaced
    // with a larger glyph is drawn as an outline
    if let Content::Glyph {text: shown, glyph, ..} = &mut drawn.content {
        if *glyph == plain {
            *shown = character.to_string();
        }
    }

    let axis = font::constant(font).axis_height * size;
    let middle = (drawn.height - drawn.depth) / 2.0;

    Some(Placed {x: 0.0, y: middle - axis, layout: drawn})
}


/// Encloses the content in stretchy delimiters that fit its height
fn fence(inside: Layout, left: &str, right: &str, font: &Font, size: f64) -> Layout {
    let axis = font::constant(font).axis_height * size;
    let half = (inside.height - axis).max(inside.depth + axis);
    let needed = 2.0 * half;
    let mut children = Vec::new();
    let mut cursor = 0.0;

    if let Some(mut part) = place_delimiter(font, left, needed, size) {
        part.x = cursor;
        cursor += part.layout.width + inner_room(font, &part.layout, false) * size;
        children.push(part);
    }

    let inside_width = inside.width;
    children.push(Placed {x: cursor, y: 0.0, layout: inside});
    cursor += inside_width;

    if let Some(mut part) = place_delimiter(font, right, needed, size) {
        cursor += inner_room(font, &part.layout, true) * size;
        part.x = cursor;
        cursor += part.layout.width;
        children.push(part);
    }

    let mut result = group(children);
    result.width = cursor;
    result
}


/// The first glyph in a group
fn leading_glyph(placed: &Layout) -> Option<u16> {
    match &placed.content {
        Content::Glyph {glyph, ..} => Some(*glyph),
        Content::Group(children) => children.first().and_then(|child| leading_glyph(&child.layout)),
        Content::Rule => None,
    }
}


/// Space missing on the inner side of a delimiter. If closing is true, the delimiter is a
/// closing one, and its inner side is on the left
///
/// Nothing is added to a delimiter at its natural size. It then has the same spacing as (x)
/// written as ordinary text, so \left( x \right) and (x) do not look different
fn inner_room(font: &Font, placed: &Layout, closing: bool) -> f64 {
    let Some(glyph) = leading_glyph(placed) else {
        return FENCE_ROOM;
    };

    if let Content::Glyph {text, stretch, ..} = &placed.content {
        let plain = text.chars().next().and_then(|character| font::glyph_of(font, character));

        if plain == Some(glyph) && *stretch == 1.0 {
            return 0.0;
        }
    }

    let (left, right) = font::bearing(font, glyph);
    let inner = if closing {left} else {right};

    (FENCE_ROOM - inner).max(0.0)
}


/// Space added after a character for its italic overhang
///
/// An italic character extends further to the right toward its top. When a delimiter follows,
/// as in f(x), the top of the character comes close to the delimiter and looks cramped.
/// As in TeX, the overhang is added after the character. It is not added to a character with
/// scripts, because the overhang is already used to position the scripts
fn trailing_slant(item: &Node, placed: &Layout, font: &Font) -> f64 {
    if matches!(item, Node::Scripts {..}) {
        return 0.0;
    }

    trailing_glyph(placed).map_or(0.0, |glyph| font::italic_correction(font, glyph))
}


/// If the group is made of exactly one glyph, that glyph
///
/// The horizontal position of an accent is decided by the attachment point that the font has
/// for each glyph. A group with two or more characters has no such value, so the accent is
/// placed at the middle of its width
fn lone_glyph(placed: &Layout) -> Option<u16> {
    match &placed.content {
        Content::Glyph {glyph, ..} => Some(*glyph),
        Content::Group(children) => {
            let mut found = None;

            for child in children {
                if let Some(glyph) = lone_glyph(&child.layout) {
                    if found.is_some() {
                        return None;
                    }

                    found = Some(glyph);
                }
            }

            found
        }
        Content::Rule => None,
    }
}


/// The last glyph in a group. Used to measure the italic overhang
fn trailing_glyph(placed: &Layout) -> Option<u16> {
    match &placed.content {
        Content::Glyph {glyph, ..} => Some(*glyph),
        Content::Group(children) => children.last().and_then(|child| trailing_glyph(&child.layout)),
        Content::Rule => None,
    }
}


#[allow(clippy::too_many_arguments)]
fn scripts_layout(
    base: &Node,
    superscript: Option<&Node>,
    subscript: Option<&Node>,
    limits: Limits,
    font: &Font,
    size: f64,
    style: Style,
    display: bool,
) -> Layout {
    let core = layout(base, font, size, style, display);
    let small = script_size(font, size);
    let upper = superscript.map(|node| layout(node, font, small, style, false));
    let lower = subscript.map(|node| layout(node, font, small, style, false));

    let stacked = match limits {
        Limits::Always => true,
        Limits::Never => false,
        Limits::Auto => display,
    };

    if stacked {
        return stacked_scripts(core, upper, lower, font, size);
    }

    side_scripts(core, upper, lower, font, size)
}


fn side_scripts(
    core: Layout,
    upper: Option<Layout>,
    lower: Option<Layout>,
    font: &Font,
    size: f64,
) -> Layout {
    let value = font::constant(font);
    let start = core.width;
    let core_height = core.height;
    let core_depth = core.depth;
    let slant = trailing_glyph(&core).map_or(0.0, |glyph| font::italic_correction(font, glyph) * size);
    let mut up = value.superscript_shift_up * size;
    let mut down = value.subscript_shift_down * size;

    if let Some(above) = upper.as_ref() {
        up = up.max(core_height - value.superscript_baseline_drop_max * size);
        up = up.max(value.superscript_bottom_min * size + above.depth);
    }

    if let Some(below) = lower.as_ref() {
        down = down.max(core_depth + value.subscript_baseline_drop_min * size);
        down = down.max(below.height - value.subscript_top_max * size);
    }

    if let (Some(above), Some(below)) = (upper.as_ref(), lower.as_ref()) {
        let least = value.sub_superscript_gap_min * size;
        let between = (up - above.depth) - (below.height - down);

        if between < least {
            down += least - between;
            let room = value.superscript_bottom_max_with_subscript * size - (up - above.depth);

            if room > 0.0 {
                up += room;
                down -= room;
            }
        }
    }

    // An italic glyph extends further to the right toward its top. The superscript can go at
    // the advance, and the subscript is moved left by that overhang to sit under the character
    let room = (SCRIPT_GAP * (core_height + core_depth)).max(SCRIPT_GAP_MIN * size);
    let upper_x = start + room;
    let lower_x = (start + room - slant).max(0.0);
    let mut width = start;
    let mut children = vec![Placed {x: 0.0, y: 0.0, layout: core}];

    if let Some(above) = upper {
        width = width.max(upper_x + above.width);
        children.push(Placed {x: upper_x, y: -up, layout: above});
    }

    if let Some(below) = lower {
        width = width.max(lower_x + below.width);
        children.push(Placed {x: lower_x, y: down, layout: below});
    }

    let mut result = group(children);
    result.width = width + value.space_after_script * size;
    result
}


fn stacked_scripts(
    core: Layout,
    upper: Option<Layout>,
    lower: Option<Layout>,
    font: &Font,
    size: f64,
) -> Layout {
    let value = font::constant(font);
    let core_width = core.width;
    let core_height = core.height;
    let core_depth = core.depth;
    let width = core_width
        .max(upper.as_ref().map_or(0.0, |item| item.width))
        .max(lower.as_ref().map_or(0.0, |item| item.width));
    let mut children = vec![Placed {x: (width - core_width) / 2.0, y: 0.0, layout: core}];

    if let Some(above) = upper {
        let rise = (value.upper_limit_gap_min * size + above.depth)
            .max(value.upper_limit_baseline_rise_min * size);
        children.push(Placed {
            x: (width - above.width) / 2.0,
            y: -(core_height + rise),
            layout: above,
        });
    }

    if let Some(below) = lower {
        let drop = (value.lower_limit_gap_min * size + below.height)
            .max(value.lower_limit_baseline_drop_min * size);
        children.push(Placed {
            x: (width - below.width) / 2.0,
            y: core_depth + drop,
            layout: below,
        });
    }

    let mut result = group(children);
    result.width = width;
    result
}


fn root_layout(
    index: Option<&Node>,
    body: &Node,
    font: &Font,
    size: f64,
    style: Style,
    display: bool,
) -> Layout {
    let value = font::constant(font);
    let inside = layout(body, font, size, style, display);
    let inside_width = inside.width;
    let inside_height = inside.height;
    let inside_depth = inside.depth;
    let thickness = value.radical_rule_thickness * size;
    let clearance = if display {
        value.radical_display_vertical_gap
    } else {
        value.radical_vertical_gap
    } * size;
    let extra = value.radical_extra_ascender * size;
    let needed = inside_height + inside_depth + clearance + thickness;
    let surd_glyph = font::glyph_of(font, '\u{221a}').unwrap_or(0);
    let mut surd = stretch_vertical(font, surd_glyph, needed, size);

    if let Content::Glyph {text, glyph, ..} = &mut surd.content {
        if *glyph == surd_glyph {
            *text = "\u{221a}".to_string();
        }
    }

    let surd_width = surd.width;
    let surd_reach = surd.height + surd.depth;
    // The bottom of the radical lines up with the bottom of the content. The rule comes at the
    // top of the radical
    let surd_y = inside_depth - surd.depth;
    let top = inside_depth - surd_reach;

    let small = index.map(|node| {
        let tiny = size * value.script_script_percent;

        layout(node, font, tiny, style, false)
    });
    let before = value.radical_kern_before_degree * size;
    let after = value.radical_kern_after_degree * size;
    let index_width = small.as_ref().map_or(0.0, |item| item.width);
    let surd_x = if small.is_some() {
        (before + index_width + after).max(0.0)
    } else {
        0.0
    };
    let body_x = surd_x + surd_width;
    let mut children = Vec::new();

    if let Some(item) = small {
        let raise = value.radical_degree_bottom_raise_percent * surd_reach;
        let y = inside_depth - raise - item.depth;
        children.push(Placed {x: before, y, layout: item});
    }

    children.push(Placed {x: surd_x, y: surd_y, layout: surd});
    children.push(Placed {
        x: body_x,
        y: top + thickness,
        layout: rule(inside_width, thickness),
    });
    children.push(Placed {x: body_x, y: 0.0, layout: inside});

    let mut result = group(children);
    result.width = body_x + inside_width;
    result.height = result.height.max(-top) + extra;
    result
}


fn column_gap(spacing: Spacing, index: usize) -> f64 {
    match (spacing, index) {
        (_, 0) => 0.0,
        (Spacing::Matrix, _) => COLUMN_GAP,
        (Spacing::Align, index) if index % 2 == 0 => ALIGN_GAP,
        _ => 0.0,
    }
}


#[allow(clippy::too_many_arguments)]
fn matrix_layout(
    rows: &[Vec<Node>],
    left: &str,
    right: &str,
    align: &[Align],
    lines: &[usize],
    spacing: Spacing,
    font: &Font,
    size: f64,
    style: Style,
) -> Layout {
    let cells: Vec<Vec<Layout>> = rows
        .iter()
        .map(|row| row.iter().map(|cell| layout(cell, font, size, style, false)).collect())
        .collect();
    let columns = cells.iter().map(Vec::len).max().unwrap_or(0);
    let mut column_width = vec![0.0f64; columns];

    for row in &cells {
        for (index, cell) in row.iter().enumerate() {
            column_width[index] = column_width[index].max(cell.width);
        }
    }

    let row_height: Vec<f64> = cells
        .iter()
        .map(|row| row.iter().fold(ROW_HEIGHT * size, |value, cell| value.max(cell.height)))
        .collect();
    let row_depth: Vec<f64> = cells
        .iter()
        .map(|row| row.iter().fold(ROW_DEPTH * size, |value, cell| value.max(cell.depth)))
        .collect();
    let row_gap = match spacing {
        Spacing::Matrix => ROW_GAP,
        Spacing::Align | Spacing::Alignat => ROW_GAP + JOT,
    } * size;
    let thickness = font::constant(font).fraction_rule_thickness * size;
    let axis = font::constant(font).axis_height * size;

    let mut baselines = Vec::new();
    let mut down = 0.0;

    for index in 0..cells.len() {
        if index > 0 {
            down += row_depth[index - 1] + row_gap;
        }

        down += row_height[index];
        baselines.push(down);
    }

    let total = down + cells.last().map_or(0.0, |_| row_depth[cells.len() - 1]);
    let offset = total / 2.0 + axis;

    let mut column_start = Vec::with_capacity(columns);
    let mut across = 0.0;

    for (index, width) in column_width.iter().enumerate() {
        across += column_gap(spacing, index) * size;
        column_start.push(across);
        across += width;
    }

    let content_width = across;
    // Space is left only on a side that has a delimiter. Some, such as cases, have a delimiter
    // on one side only
    let left_edge = if left.is_empty() {0.0} else {MATRIX_ROOM * size};
    let right_edge = if right.is_empty() {0.0} else {MATRIX_ROOM * size};
    let mut children = Vec::new();

    for (row_index, row) in cells.into_iter().enumerate() {
        for (column_index, cell) in row.into_iter().enumerate() {
            let room = column_width[column_index];
            let inside = match align.get(column_index) {
                Some(Align::Left) => 0.0,
                Some(Align::Right) => room - cell.width,
                _ => (room - cell.width) / 2.0,
            };
            children.push(Placed {
                x: left_edge + column_start[column_index] + inside,
                y: baselines[row_index] - offset,
                layout: cell,
            });
        }
    }

    for line in lines {
        let down = match line {
            0 => -row_gap / 2.0,
            index if *index >= baselines.len() => total + row_gap / 2.0,
            index => baselines[index - 1] + row_depth[index - 1] + row_gap / 2.0,
        };
        children.push(Placed {
            x: 0.0,
            y: down - offset + thickness / 2.0,
            layout: rule(content_width + left_edge + right_edge, thickness),
        });
    }

    let mut block = group(children);
    block.width = content_width + left_edge + right_edge;

    fence(block, left, right, font, size)
}


#[allow(clippy::too_many_arguments)]
fn accent_layout(
    mark: &str,
    body: &Node,
    above: bool,
    font: &Font,
    size: f64,
    style: Style,
    display: bool,
) -> Layout {
    let value = font::constant(font);
    let inside = layout(body, font, size, style, display);
    let character = mark.chars().next().unwrap_or(' ');
    // A combining accent placed as a character would attach to the character before it. It is
    // drawn as an outline, so it is given no character
    let inside_width = inside.width;
    let inside_height = inside.height;
    let inside_depth = inside.depth;
    let base_center = lone_glyph(&inside)
        .map(|found| font::accent_center(font, found) * size)
        .unwrap_or(inside_width / 2.0);

    // A wide accent is stretched horizontally to the width of the content
    let drawn = stretch_horizontal(font, character, inside_width, size, Class::Ordinary);
    let drawn_width = drawn.width;
    let drawn_depth = drawn.depth;
    let drawn_height = drawn.height;
    // An accent built as an assembly has no attachment point, so the middle of its width is used
    let mark_center = match lone_glyph(&drawn) {
        Some(wide) => font::accent_center(font, wide) * size,
        None => drawn_width / 2.0,
    };
    let y = if above {
        // The bottom of an accent glyph is above the baseline, so the accent is moved back by
        // its depth when it is placed
        let bottom = inside_height.max(value.accent_base_height * size) + MARK_GAP * size;

        -bottom - drawn_depth
    } else {
        inside_depth + MARK_GAP * size + drawn_height
    };
    // The attachment point of the accent is aligned with the center of the content. When the
    // accent is wider, the content is moved right. If the content did not move and the accent
    // were stopped at 0, the accent would stick out to the right and be off center
    let offset = base_center - mark_center;
    let inside_x = (-offset).max(0.0);
    let mark_x = offset.max(0.0);
    let width = (inside_x + inside_width).max(mark_x + drawn_width);
    let children = vec![
        Placed {x: inside_x, y: 0.0, layout: inside},
        Placed {x: mark_x, y, layout: drawn},
    ];
    let mut result = group(children);
    result.width = width;
    result
}


fn line_layout(
    body: &Node,
    above: bool,
    font: &Font,
    size: f64,
    style: Style,
    display: bool,
) -> Layout {
    let value = font::constant(font);
    let inside = layout(body, font, size, style, display);
    let thickness = if above {
        value.overbar_rule_thickness
    } else {
        value.underbar_rule_thickness
    } * size;
    let clearance = (if above {
        value.overbar_vertical_gap
    } else {
        value.underbar_vertical_gap
    } + MARK_GAP) * size;
    let extra = if above {
        value.overbar_extra_ascender
    } else {
        value.underbar_extra_descender
    } * size;
    let width = inside.width;
    let inside_height = inside.height;
    let inside_depth = inside.depth;
    let y = if above {
        -(inside_height + clearance)
    } else {
        inside_depth + clearance + thickness
    };
    let children = vec![
        Placed {x: 0.0, y: 0.0, layout: inside},
        Placed {x: 0.0, y, layout: rule(width, thickness)},
    ];
    let mut result = group(children);
    result.width = width;

    if above {
        result.height += extra;
    } else {
        result.depth += extra;
    }

    result
}

/// Takes up space and draws nothing
///
/// The content is typeset, only its dimensions are kept, and the content itself is discarded.
/// Used to line up digits
fn phantom_layout(
    body: &Node,
    width: bool,
    height: bool,
    font: &Font,
    size: f64,
    style: Style,
    display: bool,
) -> Layout {
    let inside = layout(body, font, size, style, display);

    Layout {
        content: Content::Group(Vec::new()),
        width: if width {inside.width} else {0.0},
        height: if height {inside.height} else {0.0},
        depth: if height {inside.depth} else {0.0},
    }
}


#[cfg(test)]
mod tests {
    use super::*;
    use crate::parse::parse;

    fn sample() -> Font {
        let data = std::fs::read("font/latinmodern-math.otf").expect("cannot read the test font");

        font::load(data).expect("cannot load the font")
    }

    fn build(font: &Font, source: &str, display: bool) -> Layout {
        layout(&parse(source).unwrap(), font, 1.0, Style::Auto, display)
    }

    /// The outermost node is a Row, so this takes out the first group inside it
    fn first(placed: &Layout) -> &Layout {
        &parts(placed)[0].layout
    }

    fn parts(placed: &Layout) -> &[Placed] {
        let Content::Group(children) = &placed.content else {panic!("not a Group")};

        children
    }

    /// Follows the nesting down and takes out the first glyph
    fn deep_glyph(placed: &Layout) -> u16 {
        match &placed.content {
            Content::Glyph {glyph, ..} => *glyph,
            Content::Group(children) => deep_glyph(&children[0].layout),
            Content::Rule => 0,
        }
    }

    /// Counts the things that are drawn
    fn drawn(placed: &Layout) -> usize {
        match &placed.content {
            Content::Glyph {..} | Content::Rule => 1,
            Content::Group(children) => children.iter().map(|one| drawn(&one.layout)).sum(),
        }
    }

    #[test]
    fn a_phantom_keeps_the_room_and_draws_nothing() {
        let font = sample();
        let shown = build(&font, "abc", false);
        let hidden = build(&font, "\\phantom{abc}", false);
        assert_eq!(hidden.width, shown.width);
        assert_eq!(hidden.height, shown.height);
        assert_eq!(hidden.depth, shown.depth);
        assert!(drawn(&shown) > 0);
        assert_eq!(drawn(&hidden), 0);
    }

    #[test]
    fn a_one_way_phantom_keeps_only_one_size() {
        let font = sample();
        let shown = build(&font, "abc", false);
        let across = build(&font, "\\hphantom{abc}", false);
        let tall = build(&font, "\\vphantom{abc}", false);
        assert_eq!(across.width, shown.width);
        assert_eq!(across.height, 0.0);
        assert_eq!(across.depth, 0.0);
        assert_eq!(tall.width, 0.0);
        assert_eq!(tall.height, shown.height);
        assert_eq!(tall.depth, shown.depth);
    }

    #[test]
    fn a_phantom_lines_the_columns_up() {
        let font = sample();
        let plain = build(&font, "5", false);
        let padded = build(&font, "\\phantom{-}5", false);
        let signed = build(&font, "-5", false);
        assert!(padded.width > plain.width);
        assert!((padded.width - signed.width).abs() < 1e-9);
    }

    fn glyph_id(placed: &Layout) -> u16 {
        let Content::Glyph {glyph, ..} = &placed.content else {panic!("not a Glyph")};

        *glyph
    }

    fn shown(placed: &Layout) -> String {
        match &placed.content {
            Content::Glyph {text, ..} => text.clone(),
            Content::Group(children) => children.iter().map(|child| shown(&child.layout)).collect(),
            Content::Rule => String::new(),
        }
    }

    fn close(left: f64, right: f64) -> bool {
        (left - right).abs() < 0.0005
    }

    #[test]
    fn a_variable_uses_the_math_italic_shape() {
        let font = sample();
        let placed = build(&font, "x", false);
        assert_eq!(shown(&placed), "\u{1d465}");
        assert_eq!(shown(&build(&font, "2", false)), "2");
        assert_eq!(shown(&build(&font, r"\mathrm{x}", false)), "x");
        assert_eq!(shown(&build(&font, r"\sin", false)), "sin");
    }

    #[test]
    fn a_letter_takes_the_width_the_font_gives_it() {
        let font = sample();
        let placed = build(&font, "x", false);
        let glyph = font::glyph_of(&font, '\u{1d465}').unwrap();
        assert!(close(placed.width, font::advance(&font, glyph)));
        assert!(close(placed.height, font::extent(&font, glyph).0));
    }

    #[test]
    fn binary_operators_get_space_around_them() {
        let font = sample();
        let tight = build(&font, "ab", false).width;
        let spaced = build(&font, "a+b", false).width;
        let plus = font::advance(&font, font::glyph_of(&font, '+').unwrap());
        assert!(close(spaced - tight - plus, 2.0 * MEDIUM));
    }

    #[test]
    fn relations_get_more_space_than_binary_operators() {
        assert!(gap(Class::Ordinary, Class::Relation) > gap(Class::Ordinary, Class::Binary));
        assert_eq!(gap(Class::Open, Class::Ordinary), 0.0);
        assert_eq!(gap(Class::Space(1.0), Class::Relation), 0.0);
    }

    #[test]
    fn operator_names_are_spaced_like_function_names() {
        let font = sample();
        let named = build(&font, r"\operatorname{ht} x", false).width;
        let plain = build(&font, r"\mathrm{ht} x", false).width;
        assert!(close(named - plain, THIN));
    }

    #[test]
    fn the_fraction_rule_comes_from_the_font() {
        let font = sample();
        let placed = build(&font, r"\frac{a}{b}", false);
        let bar = parts(first(&placed))
            .iter()
            .find(|child| child.layout.content == Content::Rule)
            .expect("there is no fraction rule");
        assert!(close(bar.layout.height, font::constant(&font).fraction_rule_thickness));
        // The center of the rule is on the math axis
        let center = -bar.y + bar.layout.height / 2.0;
        assert!(close(center, font::constant(&font).axis_height));
    }

    #[test]
    fn a_fixed_fraction_ignores_the_surrounding_shape() {
        let font = sample();
        let inline = build(&font, r"\frac{a}{b}", false);
        let display = build(&font, r"\frac{a}{b}", true);

        // Even inline, \dfrac has the same dimensions as a fraction in display
        let fixed = build(&font, r"\dfrac{a}{b}", false);
        assert!(fixed.height > inline.height, "\\dfrac inline did not get larger");
        assert!(close(fixed.height, display.height) && close(fixed.depth, display.depth));

        // Even in display, \tfrac has the same dimensions as an inline fraction
        let text = build(&font, r"\tfrac{a}{b}", true);
        assert!(close(text.height, inline.height) && close(text.depth, inline.depth));
    }

    #[test]
    fn a_plain_paren_keeps_its_own_shape() {
        let font = sample();
        let placed = build(&font, r"\left( x \right)", false);
        let base = font::glyph_of(&font, '(').unwrap();
        assert_eq!(glyph_id(&parts(first(&placed))[0].layout), base);
    }

    #[test]
    fn a_tall_fence_uses_a_bigger_shape_from_the_font() {
        let font = sample();
        let placed = build(&font, r"\left( \frac{a}{b} \right)", false);
        let base = font::glyph_of(&font, '(').unwrap();
        let used = glyph_id(&parts(first(&placed))[0].layout);
        assert_ne!(used, base, "not replaced with a larger glyph");
        assert!(font::extent(&font, used).0 > font::extent(&font, base).0);
    }

    #[test]
    fn a_grown_fence_keeps_room_for_its_content() {
        let font = sample();
        let placed = build(&font, r"\left[ \frac{a}{b} \right]", false);
        let pieces = parts(first(&placed));
        let open = &pieces[0];
        let body = &pieces[1];
        let (_, right) = font::bearing(&font, glyph_id(&open.layout));
        let room = body.x - (open.x + open.layout.width) + right;
        assert!(room >= FENCE_ROOM - 0.0005, "not enough space inside: {room}");
    }

    #[test]
    fn a_stretched_fence_gets_room_too() {
        let font = sample();
        let placed = build(&font, r"\left[ \frac{a}{b} \right]", false);
        let pieces = parts(first(&placed));
        let open = &pieces[0];
        assert!(pieces[1].x > open.x + open.layout.width, "the stretched delimiter has no space");
    }

    #[test]
    fn a_fence_at_its_natural_size_is_left_alone() {
        let font = sample();
        let placed = build(&font, r"\left[ x \right]", false);
        let pieces = parts(first(&placed));
        let open = &pieces[0];
        assert!(close(pieces[1].x, open.x + open.layout.width), "a plain delimiter got space");
    }

    #[test]
    fn a_very_tall_fence_is_built_from_parts() {
        let font = sample();
        let rows = r"a \\ b \\ c \\ d \\ e \\ f \\ g \\ h \\ i \\ j";
        let source = format!(r"\left\{{ \begin{{matrix}} {rows} \end{{matrix}} \right\}}");
        let placed = build(&font, &source, false);
        let brace = &parts(first(&placed))[0].layout;
        let Content::Group(pieces) = &brace.content else {
            panic!("not an assembly")
        };
        assert!(pieces.len() > 3, "number of parts: {}", pieces.len());
        // The assembly reaches the needed height
        assert!(brace.height + brace.depth > 5.0);
    }

    #[test]
    fn stretched_shapes_carry_no_character() {
        let font = sample();
        let sources = [
            r"\left\{ \begin{matrix} a \\ b \\ c \\ d \\ e \\ f \end{matrix} \right\}",
            r"\sqrt{\frac{a}{b}}",
            r"\widehat{xyz}",
        ];

        fn drawn_only(placed: &Layout, found: &mut bool) {
            match &placed.content {
                Content::Glyph {text, glyph, ..} => {
                    if text.is_empty() && *glyph != 0 {
                        *found = true;
                    }
                }
                Content::Group(children) => {
                    for child in children {
                        drawn_only(&child.layout, found);
                    }
                }
                Content::Rule => {}
            }
        }

        for source in sources {
            let mut found = false;
            drawn_only(&build(&font, source, true), &mut found);
            assert!(found, "no glyph is drawn as an outline: {source}");
        }
    }

    #[test]
    fn a_grown_glyph_carries_no_character() {
        let font = sample();
        let placed = build(&font, r"\left( \frac{a}{b} \right)", false);
        let open = &parts(first(&placed))[0].layout;
        let Content::Glyph {text, glyph, ..} = &open.content else {
            panic!("not a glyph")
        };
        assert_ne!(*glyph, font::glyph_of(&font, '(').unwrap());
        assert!(text.is_empty(), "the larger glyph has a character");
    }

    #[test]
    fn the_radical_bar_meets_the_top_of_the_sign() {
        let font = sample();
        let placed = build(&font, r"\sqrt{x + y}", false);
        let inside = parts(first(&placed));
        let surd = &inside[0];
        let bar = inside
            .iter()
            .find(|child| child.layout.content == Content::Rule)
            .expect("there is no radical rule");
        let surd_top = surd.y - surd.layout.height;
        let bar_top = bar.y - bar.layout.height;
        assert!((surd_top - bar_top).abs() < 0.001, "the rule is not at the top of the radical");
    }

    #[test]
    fn limits_move_above_and_below_in_display() {
        let font = sample();
        let inline = build(&font, r"\sum_{k=1}^{n}", false);
        let block = build(&font, r"\sum_{k=1}^{n}", true);
        assert!(block.height > inline.height);
        assert!(block.width < inline.width);
    }

    #[test]
    fn large_operators_grow_in_display() {
        let font = sample();
        let inline = build(&font, r"\sum", false);
        let block = build(&font, r"\sum", true);
        assert!(block.height + block.depth > inline.height + inline.depth);
        assert_ne!(glyph_id(first(&inline)), glyph_id(&parts(first(&block))[0].layout));
    }

    #[test]
    fn a_slanted_letter_keeps_room_after_it() {
        let font = sample();
        let slanted = font::glyph_of(&font, '\u{1d453}').unwrap();
        let correction = font::italic_correction(&font, slanted);
        assert!(correction > 0.0, "f has no overhang");

        let placed = build(&font, "f(x)", false);
        let pieces = parts(&placed);
        let room = pieces[1].x - pieces[0].layout.width;
        assert!(close(room, correction), "no space was left for the overhang: {room}");

        // An upright character has a small overhang, so the space is small too
        let placed = build(&font, r"\mathrm{f}(x)", false);
        let upright = parts(&placed);
        let narrow = upright[1].x - upright[0].layout.width;
        assert!(narrow < room, "the upright character has more space: {narrow}");

        // The same space is left when the delimiter is stretched
        let placed = build(&font, r"P\left( x \right)", false);
        let pieces = parts(&placed);
        let capital = font::glyph_of(&font, '\u{1d443}').unwrap();
        let slant = font::italic_correction(&font, capital);
        assert!(slant > 0.0, "P has no overhang");
        assert!(close(pieces[1].x - pieces[0].layout.width, slant));
    }

    #[test]
    fn a_subscript_tucks_under_a_slanted_base() {
        let font = sample();
        let placed = build(&font, r"\int_0^1", true);
        let pieces = parts(first(&placed));
        assert_eq!(pieces.len(), 3, "not an integral with two scripts");

        let base = &pieces[0];
        let slant = font::italic_correction(&font, deep_glyph(&base.layout));
        assert!(slant > 0.0, "the integral has no italic overhang");
        let reach = base.layout.height + base.layout.depth;
        let room = (SCRIPT_GAP * reach).max(SCRIPT_GAP_MIN);
        assert!(close(pieces[1].x, base.layout.width + room), "the superscript is misplaced");
        assert!(close(pieces[2].x, base.layout.width + room - slant), "subscript not moved left");
        assert!(room > 0.05, "no space was added for a tall symbol: {room}");
    }

    #[test]
    fn a_low_base_still_keeps_a_little_room() {
        let font = sample();
        let placed = build(&font, "x^2", false);
        let pieces = parts(first(&placed));
        let room = pieces[1].x - pieces[0].layout.width;
        assert!(close(room, SCRIPT_GAP_MIN), "the minimum space is missing: {room}");
    }

    #[test]
    fn an_upright_base_moves_neither_script() {
        let font = sample();
        // A digit is upright and has no overhang, so the superscript and the subscript come
        // at the same position
        let placed = build(&font, "2_1^2", false);
        let pieces = parts(first(&placed));
        let slant = font::italic_correction(&font, deep_glyph(&pieces[0].layout));
        assert_eq!(slant, 0.0);
        assert!(close(pieces[1].x, pieces[2].x), "scripts are offset on an upright character");
    }

    #[test]
    fn scripts_shrink_but_stop_at_a_floor() {
        let font = sample();
        let floor = font::constant(&font).script_script_percent;

        fn smallest(placed: &Layout) -> f64 {
            match &placed.content {
                Content::Glyph {size, ..} => *size,
                Content::Group(children) => children
                    .iter()
                    .map(|child| smallest(&child.layout))
                    .fold(f64::INFINITY, f64::min),
                Content::Rule => f64::INFINITY,
            }
        }

        let placed = build(&font, "x^{y^{z^{w}}}", false);
        assert!(close(smallest(&placed), floor));
    }

    #[test]
    fn matrix_columns_line_up() {
        let font = sample();
        let source = r"\begin{pmatrix} a & bb \\ ccc & d \end{pmatrix}";
        let placed = build(&font, source, false);
        let block = &parts(first(&placed))[1].layout;
        let cells = parts(block);
        assert_eq!(cells.len(), 4);

        let middle = |cell: &Placed| cell.x + cell.layout.width / 2.0;
        assert!(close(middle(&cells[0]), middle(&cells[2])));
        assert!(close(middle(&cells[1]), middle(&cells[3])));
        assert!(cells[1].x > cells[0].x);
    }

    #[test]
    fn a_matrix_keeps_room_at_its_edges() {
        let font = sample();
        let source = r"\begin{pmatrix} a & b \\ c & d \end{pmatrix}";
        let placed = build(&font, source, false);
        let block = &parts(first(&placed))[1].layout;
        let cells = parts(block);
        let leftmost = cells.iter().map(|cell| cell.x).fold(f64::INFINITY, f64::min);
        let rightmost = cells
            .iter()
            .map(|cell| cell.x + cell.layout.width)
            .fold(0.0, f64::max);
        assert!(close(leftmost, MATRIX_ROOM), "space at the left edge: {leftmost}");
        assert!(close(block.width - rightmost, MATRIX_ROOM), "not enough space at the right edge");
    }

    fn aligned_cells(font: &Font, source: &str) -> Vec<Placed> {
        let placed = build(font, source, true);

        parts(&parts(first(&placed))[0].layout).to_vec()
    }

    fn right_edge(cell: &Placed) -> f64 {
        cell.x + cell.layout.width
    }

    #[test]
    fn align_meets_its_columns_at_the_ampersand() {
        let font = sample();
        let cells = aligned_cells(&font, r"\begin{aligned} a &= b \\ ccc &= d \end{aligned}");
        assert_eq!(cells.len(), 4);
        assert!(close(right_edge(&cells[0]), right_edge(&cells[2])), "left column not flush right");
        assert!(close(cells[1].x, cells[3].x), "right column not flush left");
        assert!(close(right_edge(&cells[2]), cells[3].x), "there is space inside a pair");
    }

    #[test]
    fn a_relation_after_the_ampersand_keeps_its_space() {
        let font = sample();
        let cells = aligned_cells(&font, r"\begin{aligned} a &= b \end{aligned}");
        let inside = parts(&cells[1].layout);
        assert!(close(inside[1].x, THICK), "space before the = sign: {}", inside[1].x);
    }

    #[test]
    fn align_puts_room_between_the_pairs_and_alignat_does_not() {
        let font = sample();
        let cells = aligned_cells(&font, r"\begin{aligned} a &= b & c &= d \end{aligned}");
        assert!(close(cells[2].x - right_edge(&cells[1]), ALIGN_GAP));

        let cells = aligned_cells(&font, r"\begin{alignedat}{2} a &= b & c &= d \end{alignedat}");
        assert!(close(cells[2].x - right_edge(&cells[1]), 0.0));
    }

    #[test]
    fn aligned_cells_are_set_in_display() {
        let font = sample();
        let aligned = aligned_cells(&font, r"\begin{aligned} \frac{a}{b} \end{aligned}");
        let matrix = aligned_cells(&font, r"\begin{matrix} \frac{a}{b} \end{matrix}");
        assert!(aligned[0].layout.height > matrix[0].layout.height);
    }

    #[test]
    fn align_rows_are_a_jot_further_apart_than_matrix_rows() {
        let font = sample();
        let aligned = aligned_cells(&font, r"\begin{gathered} a \\ b \end{gathered}");
        let matrix = aligned_cells(&font, r"\begin{matrix} a \\ b \end{matrix}");
        let step = |cells: &[Placed]| cells[1].y - cells[0].y;
        assert!(close(step(&aligned) - step(&matrix), JOT));
    }

    #[test]
    fn a_side_without_a_bracket_gets_no_room() {
        let font = sample();
        // cases has a delimiter only on the left
        let source = r"\begin{cases} 1 & x > 0 \\ 0 & x \leq 0 \end{cases}";
        let placed = build(&font, source, false);
        let block = &parts(first(&placed))[1].layout;
        let cells = parts(block);
        let rightmost = cells
            .iter()
            .map(|cell| cell.x + cell.layout.width)
            .fold(0.0, f64::max);
        assert!(close(block.width - rightmost, 0.0), "space was added at the right edge");
    }

    #[test]
    fn horizontal_lines_span_the_whole_block() {
        let font = sample();
        let source = r"\begin{array}{cc} \hline a & b \end{array}";
        let placed = build(&font, source, false);
        let block = &parts(first(&placed))[0].layout;
        let bar = parts(block)
            .iter()
            .find(|part| part.layout.content == Content::Rule)
            .expect("there is no horizontal rule");
        assert!(close(bar.layout.width, block.width));
    }

    #[test]
    fn negative_space_pulls_back() {
        let font = sample();
        let plain = build(&font, "ab", false).width;
        let pulled = build(&font, r"a \! b", false).width;
        assert!(pulled < plain);
    }

    #[test]
    fn a_mark_keeps_off_the_body() {
        let font = sample();
        let placed = build(&font, r"\hat{A}", false);
        let pieces = parts(first(&placed));
        let body = &pieces[0];
        let mark = &pieces[1];
        // The bottom of the accent ink is this far above the top of the content
        let room = -(mark.y + mark.layout.depth) - body.layout.height;
        assert!(room >= MARK_GAP - 0.0005, "the accent sits on the character: {room}");
    }

    #[test]
    fn a_line_keeps_off_the_body() {
        let font = sample();
        let placed = build(&font, r"\overline{A}", false);
        let pieces = parts(first(&placed));
        let body = &pieces[0];
        let bar = &pieces[1];
        let room = -bar.y - body.layout.height;
        let least = font::constant(&font).overbar_vertical_gap + MARK_GAP;
        assert!(room >= least - 0.0005, "the rule is too close to the character: {room}");
    }

    #[test]
    fn a_mark_sits_over_the_middle_of_a_long_body() {
        let font = sample();
        let placed = build(&font, r"\overrightarrow{AB}", false);
        let pieces = parts(first(&placed));
        let body = &pieces[0];
        let mark = &pieces[1];
        let middle = |part: &Placed| part.x + part.layout.width / 2.0;
        assert!((middle(body) - middle(mark)).abs() < 0.05, "accent not centered on the content");
    }

    #[test]
    fn a_mark_wider_than_its_body_stays_over_the_middle() {
        let font = sample();
        let placed = build(&font, r"\overbrace{a}", false);
        let pieces = parts(first(&placed));
        let body = &pieces[0];
        let mark = &pieces[1];
        let middle = |part: &Placed| part.x + part.layout.width / 2.0;
        assert!(mark.layout.width > body.layout.width, "accent is not wider than the content");
        assert!(body.x > 0.0, "the content is still at the left edge");
        assert!((middle(body) - middle(mark)).abs() < 0.05, "the wide accent is off center");
    }

    #[test]
    fn a_wide_accent_stretches_over_its_body() {
        let font = sample();
        let narrow = build(&font, r"\widehat{x}", false);
        let wide = build(&font, r"\widehat{xyz}", false);
        let narrow_mark = glyph_id(&parts(first(&narrow))[1].layout);
        let wide_mark = glyph_id(&parts(first(&wide))[1].layout);
        assert_ne!(narrow_mark, wide_mark, "accent not replaced to fit the content width");
    }

    #[test]
    fn a_mark_without_a_long_enough_variant_is_built_from_parts() {
        let font = sample();
        let placed = build(&font, r"\overrightarrow{AB}", false);
        let pieces = parts(first(&placed));
        let body = &pieces[0];
        let mark = &pieces[1];
        let Content::Group(_) = &mark.layout.content else {
            panic!("not built from parts")
        };
        // It reaches the width of the content
        assert!(mark.layout.width >= body.layout.width - 0.01, "arrow still shorter than content");
        // It is on top of the content
        let room = -(mark.y + mark.layout.depth) - body.layout.height;
        assert!((0.0..0.3).contains(&room), "the arrow is at the wrong height: {room}");
    }

    #[test]
    fn the_shape_of_the_font_changes_the_layout() {
        let font = sample();
        let placed = build(&font, r"\frac{a}{b}", false);
        let other = "/System/Library/Fonts/Supplemental/Times New Roman.ttf";

        let Ok(data) = std::fs::read(other) else {
            return;
        };

        let fallback = font::load(data).unwrap();
        let node = parse(r"\frac{a}{b}").unwrap();
        let same = layout(&node, &fallback, 1.0, Style::Auto, false);
        assert_ne!(placed.width, same.width, "dimensions did not change with another typeface");
    }
}