webfont-generator 0.6.1

use std::cmp::{max, min};
use std::collections::{BTreeMap, HashMap, HashSet};
use std::hash::Hasher;
use std::io::{Error, ErrorKind};
use std::sync::Arc;
use std::time::{SystemTime, UNIX_EPOCH};

use kurbo::{BezPath, CubicBez, PathEl, Point};
use rustc_hash::FxHasher;
use usvg::tiny_skia_path::{Path as TinyPath, PathSegment};
use write_fonts::read::TopLevelTable;
use write_fonts::tables::cmap::Cmap;
use write_fonts::tables::glyf::{GlyfLocaBuilder, Glyph, SimpleGlyph};
use write_fonts::tables::gsub::{
    Gsub, SubstitutionLookup, SubstitutionLookupList, builders::LigatureSubBuilder,
};
use write_fonts::tables::head::Head;
use write_fonts::tables::hhea::Hhea;
use write_fonts::tables::hmtx::{Hmtx, LongMetric};
use write_fonts::tables::layout::builders::{Builder, LookupBuilder};
use write_fonts::tables::layout::{
    Feature, FeatureList, FeatureRecord, LangSys, LookupFlag, Script, ScriptList, ScriptRecord,
};
use write_fonts::tables::maxp::Maxp;
use write_fonts::tables::name::{Name, NameRecord};
use write_fonts::tables::os2::Os2;
use write_fonts::tables::post::Post;
use write_fonts::tables::variations::ivs_builder::VariationStoreBuilder;
use write_fonts::types::{FWord, Fixed, GlyphId, GlyphId16, LongDateTime, NameId, Tag, UfWord};
use write_fonts::validate::Validate;
use write_fonts::{FontWrite, dump_table};

#[cfg(test)]
use crate::GenerateWebfontsOptions;
use crate::sfnt::SerializedFontTables;
use crate::svg::rounded_coordinate;
use crate::svg::types::ProcessedGlyph;
#[cfg(test)]
use crate::svg::{prepare_svg_font, svg_options_from_options};
#[cfg(test)]
use crate::types::LoadedSvgFile;
use crate::types::ResolvedGenerateWebfontsOptions;
#[cfg(test)]
use crate::{finalize_generate_webfonts_options, resolve_generate_webfonts_options};

const QUAD_APPROXIMATION_ACCURACY: f64 = 0.25;
// Max distance (in font units) a point may be from its neighbors' chord to be dropped as
// redundant during contour simplification. TTF coordinates round to the integer grid, so a
// value below half a unit is effectively lossless. Matches svg2ttf's 0.3.
const SIMPLIFY_TOLERANCE: f64 = 0.3;
const DEFAULT_VENDOR_ID: Tag = Tag::new(b"ATLW");
const DEFAULT_TTF_DESCRIPTION: &str = "Generated by svg2ttf from Fontello project.";
const DEFAULT_TTF_MANUFACTURER_URL: &str = "http://fontello.com";

pub(crate) struct TtfOptions<'a> {
    pub ascent: Option<f64>,
    pub copyright: Option<&'a str>,
    pub descent: Option<f64>,
    pub description: Option<&'a str>,
    pub font_height: Option<f64>,
    pub font_name: &'a str,
    pub font_style: Option<&'a str>,
    pub font_weight: Option<&'a str>,
    pub ligature: bool,
    pub manufacturer_url: Option<&'a str>,
    pub ts: Option<i64>,
    pub version: Option<&'a str>,
}

struct CompiledGlyph {
    advance_width: u16,
    bbox: write_fonts::tables::glyf::Bbox,
    codepoint: u32,
    outline: CompiledGlyphOutline,
    left_side_bearing: i16,
    name: String,
    outline_key: Option<u64>,
    source_index: usize,
}

enum CompiledGlyphOutline {
    Inline(SimpleGlyph),
    Shared(Arc<CachedCompiledGlyph>),
}

impl CompiledGlyph {
    fn simple_glyph(&self) -> &SimpleGlyph {
        match &self.outline {
            CompiledGlyphOutline::Inline(glyph) => glyph,
            CompiledGlyphOutline::Shared(glyph) => &glyph.simple_glyph,
        }
    }
}

struct CachedCompiledGlyph {
    advance_width: u16,
    bbox: write_fonts::tables::glyf::Bbox,
    simple_glyph: SimpleGlyph,
}

#[derive(Clone, Default)]
pub(crate) struct TtfGlyphCache {
    entries: HashMap<u64, Arc<CachedCompiledGlyph>>,
    tables: HashMap<u64, ([u8; 4], Vec<u8>)>,
    woff1_payloads: Woff1PayloadCache,
    woff2_transforms: Woff2TransformCache,
    #[cfg(test)]
    pub compile_count: usize,
    #[cfg(test)]
    pub table_compile_count: usize,
}

#[derive(Clone, Default)]
pub(crate) struct Woff1PayloadCache {
    entries: HashMap<u64, Vec<u8>>,
    #[cfg(test)]
    compile_count: usize,
}

#[derive(Clone, Default)]
pub(crate) struct Woff2TransformCache {
    entries: HashMap<u64, Woff2TransformPayload>,
    #[cfg(test)]
    pub compile_count: usize,
}

#[derive(Clone, Debug, PartialEq, Eq)]
pub(crate) struct Woff2TransformPayload {
    pub transformed: Vec<u8>,
    pub normalized_glyf_len: usize,
    pub normalized_glyf_checksum: u32,
    pub normalized_loca_format: i16,
    pub normalized_loca_len: usize,
    pub normalized_loca_checksum: u32,
}

impl Woff1PayloadCache {
    pub(crate) fn woff1_payload(&self, key: &u64) -> Option<Vec<u8>> {
        self.entries.get(key).cloned()
    }

    pub(crate) fn insert_woff1_payload(&mut self, key: u64, payload: Vec<u8>) {
        #[cfg(test)]
        {
            self.compile_count += 1;
        }
        self.entries.insert(key, payload);
    }

    pub(crate) fn retain_woff1_payloads(&mut self, used_keys: &HashSet<u64>) {
        self.entries.retain(|key, _| used_keys.contains(key));
    }

    #[cfg(feature = "bench")]
    pub(crate) fn clear_woff1_payloads(&mut self) {
        self.entries.clear();
    }
}

impl Woff2TransformCache {
    pub(crate) fn transformed(&self, key: &u64) -> Option<Woff2TransformPayload> {
        self.entries.get(key).cloned()
    }

    pub(crate) fn insert(&mut self, key: u64, payload: Woff2TransformPayload) {
        #[cfg(test)]
        {
            self.compile_count += 1;
        }
        self.entries.insert(key, payload);
    }

    pub(crate) fn retain(&mut self, used_keys: &HashSet<u64>) {
        self.entries.retain(|key, _| used_keys.contains(key));
    }
}

impl TtfGlyphCache {
    pub(crate) fn output_caches(&mut self) -> (&mut Woff1PayloadCache, &mut Woff2TransformCache) {
        (&mut self.woff1_payloads, &mut self.woff2_transforms)
    }

    #[cfg(test)]
    pub(crate) fn woff1_payload_compile_count(&self) -> usize {
        self.woff1_payloads.compile_count
    }

    #[cfg(test)]
    pub(crate) fn woff2_transform_compile_count(&self) -> usize {
        self.woff2_transforms.compile_count
    }

    #[cfg(feature = "bench")]
    pub(crate) fn clear_woff1_payloads(&mut self) {
        self.woff1_payloads.clear_woff1_payloads();
    }
}

fn compiled_glyph_cache_key(glyph: &ProcessedGlyph, advance_width: u16) -> u64 {
    // ponytail: non-crypto FxHash for an in-process dedup key. u64 birthday
    // bound (~2^32 distinct keys) dwarfs any realistic glyph count; a collision
    // would silently reuse the wrong outline, but is astronomically unlikely
    // here. Not persisted across runs, so hasher stability across versions is
    // a non-concern.
    let mut hasher = FxHasher::default();
    match glyph.ttf_path_hash {
        Some(path_hash) => hasher.write_u64(path_hash),
        None => hasher.write(glyph.path_data.as_bytes()),
    }
    hasher.write_u16(advance_width);
    hasher.finish()
}

fn glyph_path_bucket(glyph: &ProcessedGlyph) -> u64 {
    glyph.ttf_path_hash.unwrap_or(glyph.path_data.len() as u64)
}

struct LigaturePlaceholderGlyph {
    codepoint: u32,
    name: String,
}

#[cfg(test)]
pub(crate) fn generate_ttf_font_bytes(options: GenerateWebfontsOptions) -> Result<Vec<u8>, Error> {
    let mut resolved_options = resolve_generate_webfonts_options(options)
        .map_err(|error| Error::new(ErrorKind::InvalidInput, error.to_string()))?;
    let source_files = resolved_options
        .files
        .iter()
        .map(|path| {
            Ok(LoadedSvgFile {
                contents: std::fs::read_to_string(path)?.into(),
                glyph_name: std::path::Path::new(path)
                    .file_stem()
                    .and_then(|stem| stem.to_str())
                    .unwrap_or_default()
                    .to_owned(),
                path: path.clone(),
            })
        })
        .collect::<Result<Vec<_>, Error>>()?;
    finalize_generate_webfonts_options(&mut resolved_options, &source_files)
        .map_err(|error| Error::new(ErrorKind::InvalidInput, error.to_string()))?;
    let binary_options = svg_options_from_options(&resolved_options);
    if resolved_options.types == [crate::FontType::Ttf] {
        assert!(binary_options.structure_path);
        assert!(!binary_options.serialize_path);
    }
    let binary_prepared = prepare_svg_font(&binary_options, &source_files)
        .map_err(|error| Error::new(ErrorKind::InvalidData, error.to_string()))?;
    let mut direct_options = ttf_options_from_options(&resolved_options);
    direct_options.ts = Some(direct_options.ts.unwrap_or_else(current_unix_timestamp));
    let timestamp = direct_options.ts;
    let direct = generate_ttf_font_from_glyphs(direct_options, &binary_prepared.processed_glyphs)?;

    if !resolved_options.types.contains(&crate::FontType::Svg) {
        resolved_options.types.push(crate::FontType::Svg);
    }
    let svg_options = svg_options_from_options(&resolved_options);
    let prepared = prepare_svg_font(&svg_options, &source_files)
        .map_err(|error| Error::new(ErrorKind::InvalidData, error.to_string()))?;
    let mut via_string = prepared.processed_glyphs.clone();
    for glyph in &mut via_string {
        glyph.ttf_path = None;
        glyph.ttf_path_hash = None;
    }
    let mut string_options = ttf_options_from_options(&resolved_options);
    string_options.ts = timestamp;
    let via_string = generate_ttf_font_from_glyphs(string_options, &via_string)?;
    assert_eq!(direct.ttf(), via_string.ttf());
    Ok(direct.ttf().to_vec())
}

pub(crate) fn ttf_options_from_options(
    options: &ResolvedGenerateWebfontsOptions,
) -> TtfOptions<'_> {
    let ttf_format = options
        .format_options
        .as_ref()
        .and_then(|value| value.ttf.as_ref());

    TtfOptions {
        ascent: options.ascent,
        copyright: ttf_format.and_then(|v| v.copyright.as_deref()),
        descent: options.descent,
        description: ttf_format.and_then(|v| v.description.as_deref()),
        font_height: options.font_height,
        font_name: &options.font_name,
        font_style: options.font_style.as_deref(),
        font_weight: options.font_weight.as_deref(),
        ligature: options.ligature,
        manufacturer_url: ttf_format.and_then(|v| v.url.as_deref()),
        ts: ttf_format.and_then(|v| v.ts),
        version: ttf_format.and_then(|v| v.version.as_deref()),
    }
}

pub(crate) fn generate_ttf_font_from_glyphs(
    options: TtfOptions,
    glyphs: &[ProcessedGlyph],
) -> Result<SerializedFontTables, Error> {
    let font_height = options.font_height.unwrap_or_else(|| {
        glyphs
            .iter()
            .fold(0.0_f64, |current, glyph| current.max(glyph.height))
            .max(1.0)
    });
    let descent = options.descent.unwrap_or(0.0);
    let ascent = options.ascent.unwrap_or(font_height - descent);

    let (compiled_glyphs, cmap_aliases) = compile_and_dedup_glyphs(glyphs)?;
    let ligature_placeholders = build_ligature_placeholders(&compiled_glyphs, options.ligature);
    let (glyf, loca, loca_format) = build_glyf_table(&compiled_glyphs, &ligature_placeholders)?;
    let metrics = compute_glyph_metrics(&compiled_glyphs);

    assemble_font(
        &options,
        &compiled_glyphs,
        &cmap_aliases,
        &ligature_placeholders,
        glyf,
        loca,
        loca_format,
        &metrics,
        ascent,
        descent,
        font_height,
        None,
    )
}

pub(crate) fn generate_ttf_font_from_glyphs_cached(
    options: TtfOptions,
    glyphs: &[ProcessedGlyph],
    cache: &mut TtfGlyphCache,
) -> Result<SerializedFontTables, Error> {
    let font_height = options.font_height.unwrap_or_else(|| {
        glyphs
            .iter()
            .fold(0.0_f64, |current, glyph| current.max(glyph.height))
            .max(1.0)
    });
    let descent = options.descent.unwrap_or(0.0);
    let ascent = options.ascent.unwrap_or(font_height - descent);

    let (compiled_glyphs, cmap_aliases) = compile_and_dedup_glyphs_cached(glyphs, cache)?;
    let ligature_placeholders = build_ligature_placeholders(&compiled_glyphs, options.ligature);
    let (glyf, loca, loca_format) = build_glyf_table(&compiled_glyphs, &ligature_placeholders)?;
    let metrics = compute_glyph_metrics(&compiled_glyphs);

    assemble_font(
        &options,
        &compiled_glyphs,
        &cmap_aliases,
        &ligature_placeholders,
        glyf,
        loca,
        loca_format,
        &metrics,
        ascent,
        descent,
        font_height,
        Some(cache),
    )
}

/// Codepoint aliases for deduplicated glyphs: (codepoint, index of first occurrence).
type CmapAliases = Vec<(u32, usize)>;

/// Compile glyphs and deduplicate identical outlines. Returns the unique compiled
/// glyphs and a list of cmap aliases for duplicates.
fn compile_and_dedup_glyphs(
    glyphs: &[ProcessedGlyph],
) -> Result<(Vec<CompiledGlyph>, CmapAliases), Error> {
    let mut compiled: Vec<CompiledGlyph> = Vec::with_capacity(glyphs.len());
    let mut aliases: Vec<(u32, usize)> = Vec::new();
    let mut seen: HashMap<(u64, u16), Vec<usize>> = HashMap::new();

    for (i, glyph) in glyphs.iter().enumerate() {
        let advance_width = clamp_to_u16(glyph.width.round(), 0, u16::MAX);
        let key = (glyph_path_bucket(glyph), advance_width);
        let duplicate_of = seen.get(&key).and_then(|indices| {
            indices
                .iter()
                .find(|&&idx| glyph_paths_equal(&glyphs[compiled[idx].source_index], glyph))
                .copied()
        });
        if let Some(first_idx) = duplicate_of {
            aliases.push((glyph.codepoint, first_idx));
        } else {
            let idx = compiled.len();
            seen.entry(key).or_default().push(idx);
            compiled.push(compile_glyph(i, glyph)?);
        }
    }

    Ok((compiled, aliases))
}

fn compile_and_dedup_glyphs_cached(
    glyphs: &[ProcessedGlyph],
    cache: &mut TtfGlyphCache,
) -> Result<(Vec<CompiledGlyph>, CmapAliases), Error> {
    let mut compiled: Vec<CompiledGlyph> = Vec::with_capacity(glyphs.len());
    let mut aliases: Vec<(u32, usize)> = Vec::new();
    let mut seen: HashMap<(u64, u16), Vec<usize>> = HashMap::new();
    let mut used_keys = HashSet::with_capacity(glyphs.len());

    for (i, glyph) in glyphs.iter().enumerate() {
        let advance_width = clamp_to_u16(glyph.width.round(), 0, u16::MAX);
        let key = (glyph_path_bucket(glyph), advance_width);
        let duplicate_of = seen.get(&key).and_then(|indices| {
            indices
                .iter()
                .find(|&&idx| glyph_paths_equal(&glyphs[compiled[idx].source_index], glyph))
                .copied()
        });
        if let Some(first_idx) = duplicate_of {
            aliases.push((glyph.codepoint, first_idx));
        } else {
            let cache_key = compiled_glyph_cache_key(glyph, advance_width);
            let cached = match cache.entries.get(&cache_key) {
                Some(cached) => Arc::clone(cached),
                None => {
                    #[cfg(test)]
                    {
                        cache.compile_count += 1;
                    }
                    let simple_glyph = compile_simple_glyph(glyph)?;
                    let bbox = simple_glyph.bbox;
                    let cached = Arc::new(CachedCompiledGlyph {
                        advance_width,
                        bbox,
                        simple_glyph,
                    });
                    cache.entries.insert(cache_key, Arc::clone(&cached));
                    cached
                }
            };
            used_keys.insert(cache_key);
            let idx = compiled.len();
            seen.entry(key).or_default().push(idx);
            compiled.push(CompiledGlyph {
                advance_width: cached.advance_width,
                bbox: cached.bbox,
                codepoint: glyph.codepoint,
                left_side_bearing: cached.bbox.x_min,
                name: glyph.name.clone(),
                outline_key: Some(cache_key),
                outline: CompiledGlyphOutline::Shared(cached),
                source_index: i,
            });
        }
    }

    cache.entries.retain(|key, _| used_keys.contains(key));
    Ok((compiled, aliases))
}

/// Build the glyf/loca tables from compiled glyphs and ligature placeholders.
fn build_glyf_table(
    compiled_glyphs: &[CompiledGlyph],
    ligature_placeholders: &[LigaturePlaceholderGlyph],
) -> Result<
    (
        write_fonts::tables::glyf::Glyf,
        write_fonts::tables::loca::Loca,
        write_fonts::tables::loca::LocaFormat,
    ),
    Error,
> {
    let mut builder = GlyfLocaBuilder::new();
    builder
        .add_glyph(&Glyph::Empty)
        .map_err(|error| Error::other(format!("Failed to add .notdef glyph: {error}")))?;
    for glyph in compiled_glyphs {
        builder.add_glyph(glyph.simple_glyph()).map_err(|error| {
            Error::other(format!("Failed to compile glyph '{}': {error}", glyph.name))
        })?;
    }
    for placeholder in ligature_placeholders {
        builder.add_glyph(&Glyph::Empty).map_err(|error| {
            Error::other(format!(
                "Failed to add ligature placeholder '{}': {error}",
                placeholder.name
            ))
        })?;
    }
    Ok(builder.build())
}

/// Pre-computed metrics derived from compiled glyphs.
struct GlyphMetrics {
    advance_width_max: u16,
    bbox: (i16, i16, i16, i16),
    max_contours: u16,
    max_points: u16,
    min_left_side_bearing: i16,
    min_right_side_bearing: i32,
    x_avg_char_width: i16,
    x_max_extent: i32,
}

fn compute_glyph_metrics(glyphs: &[CompiledGlyph]) -> GlyphMetrics {
    let bbox = glyphs.iter().fold(
        (0_i16, 0_i16, 0_i16, 0_i16),
        |(x_min, y_min, x_max, y_max), g| {
            (
                min(x_min, g.bbox.x_min),
                min(y_min, g.bbox.y_min),
                max(x_max, g.bbox.x_max),
                max(y_max, g.bbox.y_max),
            )
        },
    );
    GlyphMetrics {
        advance_width_max: glyphs.iter().map(|g| g.advance_width).max().unwrap_or(0),
        bbox,
        max_contours: glyphs
            .iter()
            .map(|g| g.simple_glyph().contours.len() as u16)
            .max()
            .unwrap_or(0),
        max_points: glyphs
            .iter()
            .map(|g| {
                g.simple_glyph()
                    .contours
                    .iter()
                    .map(|c| c.len())
                    .sum::<usize>() as u16
            })
            .max()
            .unwrap_or(0),
        min_left_side_bearing: glyphs
            .iter()
            .map(|g| g.left_side_bearing)
            .min()
            .unwrap_or(0),
        min_right_side_bearing: glyphs
            .iter()
            .map(|g| {
                i32::from(g.advance_width)
                    - (i32::from(g.left_side_bearing) + i32::from(g.bbox.x_max)
                        - i32::from(g.bbox.x_min))
            })
            .min()
            .unwrap_or(0),
        x_avg_char_width: average_advance_width(glyphs),
        x_max_extent: glyphs
            .iter()
            .map(|g| {
                i32::from(g.left_side_bearing) + (i32::from(g.bbox.x_max) - i32::from(g.bbox.x_min))
            })
            .max()
            .unwrap_or(0),
    }
}

/// Assemble all font tables into the final TTF binary.
#[allow(clippy::too_many_arguments)]
fn assemble_font(
    options: &TtfOptions,
    compiled_glyphs: &[CompiledGlyph],
    cmap_aliases: &[(u32, usize)],
    ligature_placeholders: &[LigaturePlaceholderGlyph],
    glyf: write_fonts::tables::glyf::Glyf,
    loca: write_fonts::tables::loca::Loca,
    loca_format: write_fonts::tables::loca::LocaFormat,
    metrics: &GlyphMetrics,
    ascent: f64,
    descent: f64,
    font_height: f64,
    mut table_cache: Option<&mut TtfGlyphCache>,
) -> Result<SerializedFontTables, Error> {
    let units_per_em = clamp_to_u16(font_height.round(), 16, 16_384);
    let h_metrics = std::iter::once(LongMetric::new(0, 0))
        .chain(
            compiled_glyphs
                .iter()
                .map(|g| LongMetric::new(g.advance_width, g.left_side_bearing)),
        )
        .chain(ligature_placeholders.iter().map(|_| LongMetric::new(0, 0)))
        .collect::<Vec<_>>();

    let character_indices: Vec<u16> = compiled_glyphs
        .iter()
        .map(|g| g.codepoint)
        .chain(ligature_placeholders.iter().map(|g| g.codepoint))
        .map(|cp| cp.min(u32::from(u16::MAX)) as u16)
        .collect();
    let first_char_index = character_indices.iter().copied().min().unwrap_or(0);
    let last_char_index = character_indices.iter().copied().max().unwrap_or(0);

    let head_timestamp = derive_head_timestamp(options.ts);
    let head = Head::new(
        Fixed::from_i32(1),
        0,
        Default::default(),
        units_per_em,
        head_timestamp,
        head_timestamp,
        metrics.bbox.0,
        metrics.bbox.1,
        metrics.bbox.2,
        metrics.bbox.3,
        Default::default(),
        8,
        i16::from(loca_format == write_fonts::tables::loca::LocaFormat::Long),
    );
    let hhea = Hhea::new(
        FWord::new(clamp_to_i16(ascent.round())),
        FWord::new(clamp_to_i16(-descent.round())),
        FWord::new(0),
        UfWord::new(metrics.advance_width_max),
        FWord::new(metrics.min_left_side_bearing),
        FWord::new(clamp_to_i16(f64::from(metrics.min_right_side_bearing))),
        FWord::new(clamp_to_i16(f64::from(metrics.x_max_extent))),
        1,
        0,
        0,
        h_metrics.len() as u16,
    );
    let hmtx = Hmtx::new(h_metrics, Vec::new());
    let maxp = Maxp {
        num_glyphs: (compiled_glyphs.len() + ligature_placeholders.len() + 1) as u16,
        max_points: Some(metrics.max_points),
        max_contours: Some(metrics.max_contours),
        max_composite_points: Some(0),
        max_composite_contours: Some(0),
        max_zones: Some(2),
        max_twilight_points: Some(0),
        max_storage: Some(0),
        max_function_defs: Some(0),
        max_instruction_defs: Some(0),
        max_stack_elements: Some(0),
        max_size_of_instructions: Some(0),
        max_component_elements: Some(0),
        max_component_depth: Some(0),
    };
    let os2 = Os2 {
        x_avg_char_width: metrics.x_avg_char_width,
        us_weight_class: derive_weight_class(options.font_weight),
        ach_vend_id: DEFAULT_VENDOR_ID,
        us_first_char_index: first_char_index,
        us_last_char_index: last_char_index,
        s_typo_ascender: clamp_to_i16(ascent.round()),
        s_typo_descender: clamp_to_i16(-descent.round()),
        s_typo_line_gap: 0,
        us_win_ascent: clamp_to_u16(ascent.round(), 0, u16::MAX),
        us_win_descent: clamp_to_u16(descent.round(), 0, u16::MAX),
        ..Default::default()
    };
    let cmap = Cmap::from_mappings(
        compiled_glyphs
            .iter()
            .enumerate()
            .filter_map(|(i, g)| {
                char::from_u32(g.codepoint).map(|c| (c, GlyphId::new((i + 1) as u32)))
            })
            .chain(cmap_aliases.iter().filter_map(|(cp, idx)| {
                char::from_u32(*cp).map(|c| (c, GlyphId::new((*idx + 1) as u32)))
            }))
            .chain(
                ligature_placeholders
                    .iter()
                    .enumerate()
                    .filter_map(|(i, g)| {
                        char::from_u32(g.codepoint)
                            .map(|c| (c, GlyphId::new((compiled_glyphs.len() + i + 1) as u32)))
                    }),
            ),
    )
    .map_err(|error| {
        Error::new(
            ErrorKind::InvalidData,
            format!("Failed to build cmap table: {error}"),
        )
    })?;

    let font_subfamily = derive_subfamily_name(options);
    let name = build_name_table(
        options.font_name,
        &font_subfamily,
        options.copyright,
        options.description,
        options.manufacturer_url,
        derive_version_string(options.version).as_deref(),
    );
    let post = Post::new_v2(
        std::iter::once(".notdef")
            .chain(compiled_glyphs.iter().map(|g| g.name.as_str()))
            .chain(ligature_placeholders.iter().map(|g| g.name.as_str())),
    );
    let gsub = build_ligature_gsub(compiled_glyphs, ligature_placeholders);
    let mut used_table_keys = HashSet::new();

    let mut tables = Vec::with_capacity(11);
    tables.push(dump_ttf_table(&head, "head")?);
    tables.push(dump_ttf_table(&hhea, "hhea")?);
    tables.push(dump_ttf_table(&maxp, "maxp")?);
    tables.push(dump_ttf_table(&os2, "OS/2")?);
    tables.push(dump_cached_ttf_table(
        &mut table_cache,
        &mut used_table_keys,
        || hmtx_cache_key(compiled_glyphs, ligature_placeholders),
        &hmtx,
        "hmtx",
    )?);
    tables.push(dump_cached_ttf_table(
        &mut table_cache,
        &mut used_table_keys,
        || cmap_cache_key(compiled_glyphs, cmap_aliases, ligature_placeholders),
        &cmap,
        "cmap",
    )?);
    tables.push(dump_cached_ttf_table(
        &mut table_cache,
        &mut used_table_keys,
        || glyf_loca_cache_key(b"loca", compiled_glyphs, ligature_placeholders),
        &loca,
        "loca",
    )?);
    tables.push(dump_cached_ttf_table(
        &mut table_cache,
        &mut used_table_keys,
        || glyf_loca_cache_key(b"glyf", compiled_glyphs, ligature_placeholders),
        &glyf,
        "glyf",
    )?);
    tables.push(dump_cached_ttf_table(
        &mut table_cache,
        &mut used_table_keys,
        || name_cache_key(options, &font_subfamily),
        &name,
        "name",
    )?);
    tables.push(dump_cached_ttf_table(
        &mut table_cache,
        &mut used_table_keys,
        || post_cache_key(compiled_glyphs, ligature_placeholders),
        &post,
        "post",
    )?);
    if let Some(gsub) = &gsub {
        tables.push(dump_cached_ttf_table(
            &mut table_cache,
            &mut used_table_keys,
            || gsub_cache_key(compiled_glyphs, ligature_placeholders),
            gsub,
            "GSUB",
        )?);
    }
    if let Some(cache) = table_cache {
        cache.tables.retain(|key, _| used_table_keys.contains(key));
    }
    SerializedFontTables::new(tables)
}

fn dump_cached_ttf_table<T>(
    cache: &mut Option<&mut TtfGlyphCache>,
    used_table_keys: &mut HashSet<u64>,
    cache_key: impl FnOnce() -> u64,
    table: &T,
    name: &str,
) -> Result<([u8; 4], Vec<u8>), Error>
where
    T: FontWrite + TopLevelTable + Validate,
{
    let Some(cache) = cache.as_deref_mut() else {
        return dump_ttf_table(table, name);
    };
    let cache_key = cache_key();
    used_table_keys.insert(cache_key);
    if let Some(cached) = cache.tables.get(&cache_key) {
        return Ok(cached.clone());
    }
    #[cfg(test)]
    {
        cache.table_compile_count += 1;
    }
    let dumped = dump_ttf_table(table, name)?;
    cache.tables.insert(cache_key, dumped.clone());
    Ok(dumped)
}

fn hmtx_cache_key(
    compiled_glyphs: &[CompiledGlyph],
    ligature_placeholders: &[LigaturePlaceholderGlyph],
) -> u64 {
    table_cache_key(b"hmtx", |hasher| {
        for glyph in compiled_glyphs {
            hasher.write_u16(glyph.advance_width);
            hasher.write_i16(glyph.left_side_bearing);
        }
        hasher.write_usize(ligature_placeholders.len());
    })
}

fn cmap_cache_key(
    compiled_glyphs: &[CompiledGlyph],
    cmap_aliases: &[(u32, usize)],
    ligature_placeholders: &[LigaturePlaceholderGlyph],
) -> u64 {
    table_cache_key(b"cmap", |hasher| {
        for glyph in compiled_glyphs {
            hasher.write_u32(glyph.codepoint);
        }
        for (codepoint, index) in cmap_aliases {
            hasher.write_u32(*codepoint);
            hasher.write_usize(*index);
        }
        for glyph in ligature_placeholders {
            hasher.write_u32(glyph.codepoint);
        }
    })
}

fn glyf_loca_cache_key(
    tag: &[u8; 4],
    compiled_glyphs: &[CompiledGlyph],
    ligature_placeholders: &[LigaturePlaceholderGlyph],
) -> u64 {
    table_cache_key(tag, |hasher| {
        for glyph in compiled_glyphs {
            hasher.write_u64(
                glyph
                    .outline_key
                    .expect("glyf/loca cache keys are only built for cached glyphs"),
            );
        }
        hasher.write_usize(ligature_placeholders.len());
    })
}

fn name_cache_key(options: &TtfOptions, font_subfamily: &str) -> u64 {
    table_cache_key(b"name", |hasher| {
        hash_str(hasher, options.font_name);
        hash_str(hasher, font_subfamily);
        hash_option_str(hasher, options.copyright);
        hash_option_str(hasher, options.description);
        hash_option_str(hasher, options.manufacturer_url);
        hash_option_str(hasher, derive_version_string(options.version).as_deref());
    })
}

fn post_cache_key(
    compiled_glyphs: &[CompiledGlyph],
    ligature_placeholders: &[LigaturePlaceholderGlyph],
) -> u64 {
    table_cache_key(b"post", |hasher| {
        for glyph in compiled_glyphs {
            hash_str(hasher, &glyph.name);
        }
        for glyph in ligature_placeholders {
            hash_str(hasher, &glyph.name);
        }
    })
}

fn gsub_cache_key(
    compiled_glyphs: &[CompiledGlyph],
    ligature_placeholders: &[LigaturePlaceholderGlyph],
) -> u64 {
    table_cache_key(b"GSUB", |hasher| {
        for glyph in compiled_glyphs {
            hash_str(hasher, &glyph.name);
        }
        for glyph in ligature_placeholders {
            hasher.write_u32(glyph.codepoint);
        }
    })
}

// ponytail: non-crypto FxHash keyed on the tables' semantic inputs. Hashes
// straight into the hasher, so no intermediate key buffer is allocated. u64
// collisions are negligible at font scale and would only surface as reusing an
// identical table's bytes; not persisted, so hasher stability is a non-concern.
fn table_cache_key(tag: &[u8; 4], hash_inputs: impl FnOnce(&mut FxHasher)) -> u64 {
    let mut hasher = FxHasher::default();
    hasher.write(tag);
    hash_inputs(&mut hasher);
    hasher.finish()
}

fn hash_option_str(hasher: &mut FxHasher, value: Option<&str>) {
    match value {
        Some(value) => {
            hasher.write_u8(1);
            hash_str(hasher, value);
        }
        None => hasher.write_u8(0),
    }
}

fn hash_str(hasher: &mut FxHasher, value: &str) {
    // Length-prefix so concatenation is unambiguous ("ab"+"c" != "a"+"bc").
    hasher.write_usize(value.len());
    hasher.write(value.as_bytes());
}

fn dump_ttf_table<T>(table: &T, name: &str) -> Result<([u8; 4], Vec<u8>), Error>
where
    T: FontWrite + TopLevelTable + Validate,
{
    dump_table(table)
        .map(|bytes| (T::TAG.to_be_bytes(), bytes))
        .map_err(|error| Error::other(format!("Failed to add {name} table: {error:?}")))
}

fn compile_glyph(source_index: usize, glyph: &ProcessedGlyph) -> Result<CompiledGlyph, Error> {
    let advance_width = clamp_to_u16(glyph.width.round(), 0, u16::MAX);
    let simple_glyph = compile_simple_glyph(glyph)?;
    let bbox = simple_glyph.bbox;

    Ok(CompiledGlyph {
        advance_width,
        bbox,
        codepoint: glyph.codepoint,
        left_side_bearing: bbox.x_min,
        name: glyph.name.clone(),
        outline: CompiledGlyphOutline::Inline(simple_glyph),
        outline_key: None,
        source_index,
    })
}

fn compile_simple_glyph(glyph: &ProcessedGlyph) -> Result<SimpleGlyph, Error> {
    let path = match &glyph.ttf_path {
        Some(path) => quadratic_path(path)?,
        None => quadratic_path_from_svg_path_data(&glyph.path_data)?,
    };
    SimpleGlyph::from_bezpath(&path).map_err(|error| {
        Error::other(format!(
            "Failed to convert glyph '{}' into a TrueType outline: {error:?}",
            glyph.name
        ))
    })
}

/// Perpendicular distance from `p` to the line through `a` and `b` (or `|p - a|` when `a ≈ b`).
fn point_line_distance(p: Point, a: Point, b: Point) -> f64 {
    let dx = b.x - a.x;
    let dy = b.y - a.y;
    let len_sq = dx * dx + dy * dy;
    if len_sq <= f64::EPSILON {
        return (p - a).hypot();
    }
    ((p.x - a.x) * dy - (p.y - a.y) * dx).abs() / len_sq.sqrt()
}

/// Appends a `LineTo(point)` to `elements`, merging it with the immediately-preceding line when
/// their shared vertex (`from`) is within `SIMPLIFY_TOLERANCE` of the chord — i.e. the three
/// points are collinear, so the vertex is redundant. `line_start` is `Some` only when the last
/// element is a mergeable `LineTo`; on a merge it stays anchored at the original line start so a
/// run of collinear points collapses to a single segment. Returns the new current point.
fn push_line(
    elements: &mut Vec<PathEl>,
    line_start: &mut Option<Point>,
    from: Point,
    point: Point,
) -> Point {
    if let Some(start) = *line_start
        && point_line_distance(from, start, point) <= SIMPLIFY_TOLERANCE
        && let Some(PathEl::LineTo(end)) = elements.last_mut()
    {
        *end = point;
        return point;
    }
    elements.push(PathEl::LineTo(point));
    *line_start = Some(from);
    point
}

/// Converts serialized SVG path data into a quadratic `BezPath` for a TrueType glyph: flattens
/// cubics to quadratics and simplifies in a single pass, writing straight into the output with
/// O(1) lookback (no intermediate per-contour buffers). Near-straight quadratics become lines and
/// consecutive collinear lines are merged, both within `SIMPLIFY_TOLERANCE` font units which the
/// later integer rounding absorbs. Mirrors svg2ttf's `simplify` without its multi-pass allocation.
fn quadratic_path_from_svg_path_data(path_data: &str) -> Result<BezPath, Error> {
    let path = BezPath::from_svg(path_data).map_err(|error| {
        Error::new(
            ErrorKind::InvalidData,
            format!("Failed to parse generated SVG path data as a Bezier path: {error:?}"),
        )
    })?;

    quadratic_path(&path)
}

pub(crate) fn bezpath_from_oxvg_path(path: &oxvg_path::Path) -> BezPath {
    let number = |value: f64| if value == 0.0 { 0.0 } else { value };
    let point = |x: f64, y: f64| Point::new(number(x), number(y));
    let relative = |from: Point, x: f64, y: f64| from + point(x, y).to_vec2();
    let mut result = BezPath::new();
    let mut current = Point::ORIGIN;
    let mut subpath_start = Point::ORIGIN;
    // Preserve Kurbo's family-agnostic smooth-control state for exact historical TTF bytes.
    let mut last_ctrl = None;
    let mut implicit_moveto = None;

    for command in &path.0 {
        let mut command = command;
        while let oxvg_path::command::Data::Implicit(inner) = command {
            command = inner;
        }

        if !matches!(
            command,
            oxvg_path::command::Data::MoveTo(_) | oxvg_path::command::Data::MoveBy(_)
        ) && let Some(to) = implicit_moveto.take()
        {
            result.move_to(to);
        }

        use oxvg_path::command::Data;
        match command {
            Data::MoveTo([x, y]) => {
                implicit_moveto = None;
                current = point(*x, *y);
                result.move_to(current);
                subpath_start = current;
                last_ctrl = Some(current);
            }
            Data::MoveBy([x, y]) => {
                implicit_moveto = None;
                current = relative(current, *x, *y);
                result.move_to(current);
                subpath_start = current;
                last_ctrl = Some(current);
            }
            Data::ClosePath => {
                result.close_path();
                current = subpath_start;
                implicit_moveto = Some(subpath_start);
            }
            Data::LineTo([x, y]) => {
                current = point(*x, *y);
                result.line_to(current);
                last_ctrl = Some(current);
            }
            Data::LineBy([x, y]) => {
                current = relative(current, *x, *y);
                result.line_to(current);
                last_ctrl = Some(current);
            }
            Data::HorizontalLineTo([x]) => {
                current = Point::new(number(*x), current.y);
                result.line_to(current);
                last_ctrl = Some(current);
            }
            Data::HorizontalLineBy([x]) => {
                current = Point::new(current.x + number(*x), current.y);
                result.line_to(current);
                last_ctrl = Some(current);
            }
            Data::VerticalLineTo([y]) => {
                current = Point::new(current.x, number(*y));
                result.line_to(current);
                last_ctrl = Some(current);
            }
            Data::VerticalLineBy([y]) => {
                current = Point::new(current.x, current.y + number(*y));
                result.line_to(current);
                last_ctrl = Some(current);
            }
            Data::CubicBezierTo([x1, y1, x2, y2, x, y]) => {
                let control1 = point(*x1, *y1);
                let control2 = point(*x2, *y2);
                current = point(*x, *y);
                result.curve_to(control1, control2, current);
                last_ctrl = Some(control2);
            }
            Data::CubicBezierBy([x1, y1, x2, y2, x, y]) => {
                let control1 = relative(current, *x1, *y1);
                let control2 = relative(current, *x2, *y2);
                current = relative(current, *x, *y);
                result.curve_to(control1, control2, current);
                last_ctrl = Some(control2);
            }
            Data::SmoothBezierTo([x2, y2, x, y]) => {
                let control1 = last_ctrl
                    .map(|control| (2.0 * current.to_vec2() - control.to_vec2()).to_point())
                    .unwrap_or(current);
                let control2 = point(*x2, *y2);
                current = point(*x, *y);
                result.curve_to(control1, control2, current);
                last_ctrl = Some(control2);
            }
            Data::SmoothBezierBy([x2, y2, x, y]) => {
                let control1 = last_ctrl
                    .map(|control| (2.0 * current.to_vec2() - control.to_vec2()).to_point())
                    .unwrap_or(current);
                let control2 = relative(current, *x2, *y2);
                current = relative(current, *x, *y);
                result.curve_to(control1, control2, current);
                last_ctrl = Some(control2);
            }
            Data::QuadraticBezierTo([x1, y1, x, y]) => {
                let control = point(*x1, *y1);
                current = point(*x, *y);
                result.quad_to(control, current);
                last_ctrl = Some(control);
            }
            Data::QuadraticBezierBy([x1, y1, x, y]) => {
                let control = relative(current, *x1, *y1);
                current = relative(current, *x, *y);
                result.quad_to(control, current);
                last_ctrl = Some(control);
            }
            Data::SmoothQuadraticBezierTo([x, y]) => {
                let control = last_ctrl
                    .map(|control| (2.0 * current.to_vec2() - control.to_vec2()).to_point())
                    .unwrap_or(current);
                current = point(*x, *y);
                result.quad_to(control, current);
                last_ctrl = Some(control);
            }
            Data::SmoothQuadraticBezierBy([x, y]) => {
                let control = last_ctrl
                    .map(|control| (2.0 * current.to_vec2() - control.to_vec2()).to_point())
                    .unwrap_or(current);
                current = relative(current, *x, *y);
                result.quad_to(control, current);
                last_ctrl = Some(control);
            }
            Data::ArcTo([rx, ry, rotation, large_arc, sweep, x, y])
            | Data::ArcBy([rx, ry, rotation, large_arc, sweep, x, y]) => {
                let to = if matches!(command, Data::ArcBy(_)) {
                    relative(current, *x, *y)
                } else {
                    point(*x, *y)
                };
                let svg_arc = kurbo::SvgArc {
                    from: current,
                    to,
                    radii: kurbo::Vec2::new(number(*rx), number(*ry)),
                    x_rotation: number(*rotation).to_radians(),
                    large_arc: number(*large_arc) == 1.0,
                    sweep: number(*sweep) == 1.0,
                };
                if let Some(arc) = kurbo::Arc::from_svg_arc(&svg_arc) {
                    arc.to_cubic_beziers(0.1, |p1, p2, p3| result.curve_to(p1, p2, p3));
                } else {
                    result.line_to(to);
                }
                current = to;
                last_ctrl = Some(to);
            }
            Data::Implicit(_) => unreachable!(),
        }
    }

    result
}

fn quadratic_path(path: &BezPath) -> Result<BezPath, Error> {
    let mut elements: Vec<PathEl> = Vec::with_capacity(path.elements().len());
    let mut current: Option<Point> = None;
    // `Some(start)` when the last pushed element is a `LineTo` in the current contour, so a
    // following collinear line can extend it instead of adding a vertex.
    let mut line_start: Option<Point> = None;

    for element in path.elements() {
        match *element {
            PathEl::MoveTo(point) => {
                elements.push(PathEl::MoveTo(point));
                current = Some(point);
                line_start = None;
            }
            PathEl::LineTo(point) => {
                let from = current.unwrap_or(point);
                current = Some(push_line(&mut elements, &mut line_start, from, point));
            }
            PathEl::QuadTo(control, point) => {
                let from = current.unwrap_or(control);
                if point_line_distance(control, from, point) <= SIMPLIFY_TOLERANCE {
                    current = Some(push_line(&mut elements, &mut line_start, from, point));
                } else {
                    elements.push(PathEl::QuadTo(control, point));
                    line_start = None;
                    current = Some(point);
                }
            }
            PathEl::CurveTo(control1, control2, point) => {
                let start = current.ok_or_else(|| {
                    Error::new(
                        ErrorKind::InvalidData,
                        "Encountered a cubic segment before a MoveTo while building a TTF glyph.",
                    )
                })?;
                let cubic = CubicBez::new(start, control1, control2, point);
                let mut from = start;
                for (_, _, quad) in cubic.to_quads(QUAD_APPROXIMATION_ACCURACY) {
                    if point_line_distance(quad.p1, from, quad.p2) <= SIMPLIFY_TOLERANCE {
                        from = push_line(&mut elements, &mut line_start, from, quad.p2);
                    } else {
                        elements.push(PathEl::QuadTo(quad.p1, quad.p2));
                        line_start = None;
                        from = quad.p2;
                    }
                }
                current = Some(from);
            }
            PathEl::ClosePath => {
                elements.push(PathEl::ClosePath);
                current = None;
                line_start = None;
            }
        }
    }

    Ok(BezPath::from_vec(elements))
}

pub(crate) fn rounded_bezpath_from_tiny_paths(paths: &[TinyPath], round: f64) -> BezPath {
    let point = |point: usvg::tiny_skia_path::Point| {
        Point::new(
            rounded_coordinate(point.x, round),
            rounded_coordinate(point.y, round),
        )
    };
    let mut result = BezPath::new();
    for path in paths {
        for segment in path.segments() {
            match segment {
                PathSegment::MoveTo(to) => result.move_to(point(to)),
                PathSegment::LineTo(to) => result.line_to(point(to)),
                PathSegment::QuadTo(control, to) => result.quad_to(point(control), point(to)),
                PathSegment::CubicTo(control1, control2, to) => {
                    result.curve_to(point(control1), point(control2), point(to));
                }
                PathSegment::Close => result.close_path(),
            }
        }
    }
    result
}

fn glyph_paths_equal(left: &ProcessedGlyph, right: &ProcessedGlyph) -> bool {
    match (&left.ttf_path, &right.ttf_path) {
        (Some(left), Some(right)) => left.elements() == right.elements(),
        _ => left.path_data == right.path_data,
    }
}

pub(crate) fn bezpath_hash(path: &BezPath) -> u64 {
    let mut hasher = FxHasher::default();
    for element in path.elements() {
        hash_path_element(&mut hasher, *element);
    }
    hasher.finish()
}

fn hash_path_element(hasher: &mut FxHasher, element: PathEl) {
    match element {
        PathEl::MoveTo(point) => {
            hasher.write_u8(0);
            hash_point(hasher, point);
        }
        PathEl::LineTo(point) => {
            hasher.write_u8(1);
            hash_point(hasher, point);
        }
        PathEl::QuadTo(control, point) => {
            hasher.write_u8(2);
            hash_point(hasher, control);
            hash_point(hasher, point);
        }
        PathEl::CurveTo(control1, control2, point) => {
            hasher.write_u8(3);
            hash_point(hasher, control1);
            hash_point(hasher, control2);
            hash_point(hasher, point);
        }
        PathEl::ClosePath => hasher.write_u8(4),
    }
}

fn hash_point(hasher: &mut FxHasher, point: Point) {
    hasher.write_u64(point.x.to_bits());
    hasher.write_u64(point.y.to_bits());
}

fn build_name_table(
    font_family: &str,
    font_subfamily: &str,
    copyright: Option<&str>,
    description: Option<&str>,
    url: Option<&str>,
    version: Option<&str>,
) -> Name {
    let full_name = if font_subfamily == "Regular" {
        font_family.to_string()
    } else {
        format!("{font_family} {font_subfamily}")
    };
    let postscript_name = full_name.replace(' ', "-");
    let mut name_record = vec![
        make_windows_name_record(1, font_family),
        make_windows_name_record(2, font_subfamily),
        make_windows_name_record(4, &full_name),
        make_windows_name_record(5, version.unwrap_or("Version 1.0")),
        make_windows_name_record(6, &postscript_name),
    ];
    if let Some(copyright) = copyright {
        name_record.push(make_windows_name_record(0, copyright));
    }
    name_record.push(make_windows_name_record(
        10,
        description.unwrap_or(DEFAULT_TTF_DESCRIPTION),
    ));
    name_record.push(make_windows_name_record(
        11,
        url.unwrap_or(DEFAULT_TTF_MANUFACTURER_URL),
    ));
    name_record.sort();

    Name {
        name_record,
        ..Default::default()
    }
}

fn make_windows_name_record(name_id: u16, value: &str) -> NameRecord {
    NameRecord::new(3, 1, 0x0409, NameId::new(name_id), value.to_string().into())
}

fn average_advance_width(compiled_glyphs: &[CompiledGlyph]) -> i16 {
    let non_zero_widths = compiled_glyphs
        .iter()
        .map(|glyph| glyph.advance_width)
        .filter(|width| *width > 0)
        .collect::<Vec<_>>();
    if non_zero_widths.is_empty() {
        return 0;
    }
    let total: u32 = non_zero_widths.iter().map(|width| u32::from(*width)).sum();
    clamp_to_i16((total / non_zero_widths.len() as u32) as f64)
}

fn derive_subfamily_name(options: &TtfOptions) -> String {
    match options.font_style {
        Some(style) if style.eq_ignore_ascii_case("italic") => "Italic".to_string(),
        _ => "Regular".to_string(),
    }
}

fn derive_weight_class(font_weight: Option<&str>) -> u16 {
    match font_weight {
        Some(value) if value.eq_ignore_ascii_case("bold") => 700,
        Some(value) => value
            .parse::<u16>()
            .ok()
            .filter(|weight| (1..=1000).contains(weight))
            .unwrap_or(400),
        None => 400,
    }
}

fn derive_version_string(version: Option<&str>) -> Option<String> {
    let version = version?.trim();
    if version.is_empty() {
        return None;
    }
    if version.starts_with("Version ") {
        return Some(version.to_string());
    }
    Some(format!("Version {}", version.trim_end_matches('.')))
}

fn derive_head_timestamp(_ts: Option<i64>) -> LongDateTime {
    const MAC_EPOCH_OFFSET_SECONDS: i64 = 2_082_844_800;
    let unix_seconds = _ts.unwrap_or_else(current_unix_timestamp);

    LongDateTime::new(unix_seconds.saturating_add(MAC_EPOCH_OFFSET_SECONDS))
}

fn current_unix_timestamp() -> i64 {
    SystemTime::now()
        .duration_since(UNIX_EPOCH)
        .map(|duration| duration.as_secs() as i64)
        .unwrap_or(0)
}

fn build_ligature_placeholders(
    compiled_glyphs: &[CompiledGlyph],
    ligature: bool,
) -> Vec<LigaturePlaceholderGlyph> {
    if !ligature {
        return Vec::new();
    }

    let mut seen = HashSet::new();
    let mut placeholders = Vec::new();

    for glyph in compiled_glyphs {
        if glyph.name.chars().count() < 2 {
            continue;
        }
        for character in glyph.name.chars() {
            let codepoint = u32::from(character);
            if seen.insert(codepoint) {
                placeholders.push(LigaturePlaceholderGlyph {
                    codepoint,
                    name: format!("ligature-char-{:X}", codepoint),
                });
            }
        }
    }

    placeholders
}

fn build_ligature_gsub(
    compiled_glyphs: &[CompiledGlyph],
    ligature_placeholders: &[LigaturePlaceholderGlyph],
) -> Option<Gsub> {
    if ligature_placeholders.is_empty() {
        return None;
    }

    let placeholder_glyph_ids = ligature_placeholders
        .iter()
        .enumerate()
        .map(|(index, glyph)| {
            (
                glyph.codepoint,
                GlyphId16::new((compiled_glyphs.len() + index + 1) as u16),
            )
        })
        .collect::<BTreeMap<_, _>>();
    let mut lookup_builder = LookupBuilder::<LigatureSubBuilder>::new(LookupFlag::empty(), None);

    for (index, glyph) in compiled_glyphs.iter().enumerate() {
        let sequence = glyph
            .name
            .chars()
            .filter_map(|character| placeholder_glyph_ids.get(&u32::from(character)).copied())
            .collect::<Vec<_>>();
        if sequence.len() < 2 {
            continue;
        }
        lookup_builder
            .last_mut()
            .expect("ligature lookup builder should always contain a subtable")
            .insert(sequence, GlyphId16::new((index + 1) as u16));
    }

    if lookup_builder
        .iter_subtables()
        .all(LigatureSubBuilder::is_empty)
    {
        return None;
    }

    let script_list = ScriptList::new(vec![ScriptRecord::new(
        Tag::new(b"DFLT"),
        Script::new(Some(LangSys::new(vec![0])), vec![]),
    )]);
    let feature_list = FeatureList::new(vec![FeatureRecord::new(
        Tag::new(b"liga"),
        Feature::new(None, vec![0]),
    )]);
    let mut variation_store = VariationStoreBuilder::new(0);
    let lookup = lookup_builder.build(&mut variation_store);
    let lookup_list = SubstitutionLookupList::new(vec![SubstitutionLookup::Ligature(lookup)]);

    Some(Gsub::new(script_list, feature_list, lookup_list))
}

fn clamp_to_i16(value: f64) -> i16 {
    value
        .clamp(f64::from(i16::MIN), f64::from(i16::MAX))
        .round() as i16
}

fn clamp_to_u16(value: f64, min_value: u16, max_value: u16) -> u16 {
    value
        .clamp(f64::from(min_value), f64::from(max_value))
        .round() as u16
}

#[cfg(test)]
mod tests {
    use std::path::PathBuf;

    use super::generate_ttf_font_bytes;
    use crate::{FontType, GenerateWebfontsOptions};
    use write_fonts::read::{FontRef, TableProvider};

    #[test]
    fn generates_a_ttf_buffer_with_a_true_type_header() {
        let root = PathBuf::from(env!("CARGO_MANIFEST_DIR"));
        let fixture = root
            .join("src/svg/fixtures/icons/cleanicons")
            .join("plus.svg");
        let result = generate_ttf_font_bytes(GenerateWebfontsOptions {
            css: Some(false),
            dest: "artifacts".to_string(),
            files: vec![fixture.display().to_string()],
            html: Some(false),
            font_name: Some("cleanicons".to_string()),
            ligature: Some(false),
            start_codepoint: Some(0xE001),
            types: Some(vec![FontType::Ttf]),
            ..Default::default()
        })
        .expect("expected native ttf generation to succeed");

        assert_eq!(&result[..4], &[0x00, 0x01, 0x00, 0x00]);
        assert!(!result.is_empty());
    }

    #[test]
    fn optimized_direct_ttf_matches_the_string_path_route() {
        let root =
            PathBuf::from(env!("CARGO_MANIFEST_DIR")).join("src/svg/fixtures/icons/cleanicons");
        generate_ttf_font_bytes(GenerateWebfontsOptions {
            css: Some(false),
            dest: "artifacts".to_string(),
            files: [
                "account.svg",
                "arrow-down.svg",
                "arrow-left.svg",
                "arrow-right.svg",
                "arrow-up.svg",
                "basket.svg",
                "close.svg",
                "minus.svg",
                "plus.svg",
                "search.svg",
            ]
            .into_iter()
            .map(|file| root.join(file).display().to_string())
            .collect(),
            html: Some(false),
            font_name: Some("optimized-direct".to_string()),
            optimize_output: Some(true),
            types: Some(vec![FontType::Ttf]),
            ..Default::default()
        })
        .expect("expected direct optimized TTF generation to match the string route");
    }

    #[test]
    fn adds_gsub_ligatures_and_placeholder_glyphs_when_enabled() {
        let root = PathBuf::from(env!("CARGO_MANIFEST_DIR"));
        let fixture = root
            .join("src/svg/fixtures/icons/cleanicons")
            .join("plus.svg");
        let result = generate_ttf_font_bytes(GenerateWebfontsOptions {
            css: Some(false),
            dest: "artifacts".to_string(),
            files: vec![fixture.display().to_string()],
            html: Some(false),
            font_name: Some("plus".to_string()),
            ligature: Some(true),
            start_codepoint: Some(0xE001),
            ..Default::default()
        })
        .expect("expected native ttf ligature generation to succeed");
        let font = FontRef::new(&result).expect("expected a readable ttf font");

        assert!(font.gsub().is_ok(), "expected a GSUB table for ligatures");
        assert!(font.maxp().expect("expected maxp table").num_glyphs() > 2);
    }

    use crate::test_helpers::icons_root;

    fn create_svg_copies(
        source: &std::path::Path,
        names: &[&str],
    ) -> (std::path::PathBuf, Vec<String>) {
        let unique = std::time::SystemTime::now()
            .duration_since(std::time::UNIX_EPOCH)
            .unwrap()
            .as_nanos();
        let tmp = std::env::temp_dir().join(format!("ttf-dedup-{}-{unique}", names.join("-")));
        std::fs::create_dir_all(&tmp).unwrap();
        let files = names
            .iter()
            .map(|name| {
                let dest = tmp.join(format!("{name}.svg"));
                std::fs::copy(source, &dest).unwrap();
                dest.display().to_string()
            })
            .collect();
        (tmp, files)
    }

    #[test]
    fn deduplicates_pair_of_identical_glyphs_with_explicit_codepoints() {
        let icon = icons_root().join("cleanicons/plus.svg");
        let (tmp, copies) = create_svg_copies(&icon, &["plus-copy"]);

        let mut files = vec![icon.display().to_string()];
        files.extend(copies);

        let result = generate_ttf_font_bytes(GenerateWebfontsOptions {
            css: Some(false),
            codepoints: Some(std::collections::HashMap::from([
                ("plus".to_string(), 0xE001u32),
                ("plus-copy".to_string(), 0xE002u32),
            ])),
            dest: "artifacts".to_string(),
            files,
            html: Some(false),
            font_name: Some("dedup-test".to_string()),
            ligature: Some(false),
            start_codepoint: Some(0xE001),
            ..Default::default()
        })
        .expect("TTF generation should succeed");
        let _ = std::fs::remove_dir_all(&tmp);

        let font = FontRef::new(&result).expect("readable TTF");
        assert_eq!(
            font.maxp().unwrap().num_glyphs(),
            2,
            "1 .notdef + 1 deduped glyph"
        );

        let cmap = font.cmap().expect("cmap");
        let gid_1 = cmap.map_codepoint(0xE001u32);
        let gid_2 = cmap.map_codepoint(0xE002u32);
        assert!(gid_1.is_some(), "E001 should be in cmap");
        assert_eq!(gid_1, gid_2, "both codepoints should map to same glyph ID");
    }

    #[test]
    fn deduplicates_pair_of_identical_glyphs_with_implicit_codepoints() {
        let icon = icons_root().join("cleanicons/plus.svg");
        let (tmp, copies) = create_svg_copies(&icon, &["plus-copy"]);

        let mut files = vec![icon.display().to_string()];
        files.extend(copies);

        let result = generate_ttf_font_bytes(GenerateWebfontsOptions {
            css: Some(false),
            dest: "artifacts".to_string(),
            files,
            html: Some(false),
            font_name: Some("dedup-implicit".to_string()),
            ligature: Some(false),
            start_codepoint: Some(0xF101),
            ..Default::default()
        })
        .expect("TTF generation should succeed");
        let _ = std::fs::remove_dir_all(&tmp);

        let font = FontRef::new(&result).expect("readable TTF");
        assert_eq!(
            font.maxp().unwrap().num_glyphs(),
            2,
            "1 .notdef + 1 deduped glyph"
        );

        let cmap = font.cmap().expect("cmap");
        let gid_1 = cmap.map_codepoint(0xF101u32);
        let gid_2 = cmap.map_codepoint(0xF102u32);
        assert!(gid_1.is_some());
        assert_eq!(
            gid_1, gid_2,
            "auto-assigned codepoints should map to same glyph ID"
        );
    }

    #[test]
    fn deduplicates_multiple_copies_into_single_glyph() {
        let icon = icons_root().join("cleanicons/plus.svg");
        let (tmp, copies) = create_svg_copies(&icon, &["copy-a", "copy-b", "copy-c"]);

        let mut files = vec![icon.display().to_string()];
        files.extend(copies);

        let result = generate_ttf_font_bytes(GenerateWebfontsOptions {
            css: Some(false),
            codepoints: Some(std::collections::HashMap::from([
                ("plus".to_string(), 0xE001u32),
                ("copy-a".to_string(), 0xE002u32),
                ("copy-c".to_string(), 0xE003u32),
            ])),
            dest: "artifacts".to_string(),
            files,
            html: Some(false),
            font_name: Some("dedup-multi".to_string()),
            ligature: Some(false),
            start_codepoint: Some(0xE001),
            ..Default::default()
        })
        .expect("TTF generation should succeed");
        let _ = std::fs::remove_dir_all(&tmp);

        let font = FontRef::new(&result).expect("readable TTF");
        assert_eq!(
            font.maxp().unwrap().num_glyphs(),
            2,
            "4 identical SVGs → 1 .notdef + 1 deduped glyph"
        );

        let cmap = font.cmap().expect("cmap");
        let gids: Vec<_> = (0xE001u32..=0xE004u32)
            .map(|cp| cmap.map_codepoint(cp))
            .collect();
        assert!(
            gids.iter().all(|g| g.is_some()),
            "all 4 codepoints should be in cmap"
        );
        assert!(
            gids.windows(2).all(|w| w[0] == w[1]),
            "all 4 codepoints should map to same glyph ID"
        );
    }

    #[test]
    fn does_not_deduplicate_glyphs_with_different_paths() {
        let result = generate_ttf_font_bytes(GenerateWebfontsOptions {
            css: Some(false),
            codepoints: Some(std::collections::HashMap::from([
                ("plus".to_string(), 0xE001u32),
                ("minus".to_string(), 0xE002u32),
            ])),
            dest: "artifacts".to_string(),
            files: vec![
                icons_root()
                    .join("cleanicons/plus.svg")
                    .display()
                    .to_string(),
                icons_root()
                    .join("cleanicons/minus.svg")
                    .display()
                    .to_string(),
            ],
            html: Some(false),
            font_name: Some("no-dedup".to_string()),
            ligature: Some(false),
            start_codepoint: Some(0xE001),
            ..Default::default()
        })
        .expect("TTF generation should succeed");

        let font = FontRef::new(&result).expect("readable TTF");
        assert_eq!(
            font.maxp().unwrap().num_glyphs(),
            3,
            "1 .notdef + 2 unique glyphs"
        );

        let cmap = font.cmap().expect("cmap");
        assert_ne!(
            cmap.map_codepoint(0xE001u32),
            cmap.map_codepoint(0xE002u32),
            "different glyphs should have different glyph IDs"
        );
    }

    use super::{
        SIMPLIFY_TOLERANCE, bezpath_from_oxvg_path, point_line_distance,
        quadratic_path_from_svg_path_data,
    };
    use kurbo::{BezPath, PathEl, Point};
    use oxvg_path::parser::Parse as _;

    #[test]
    fn oxvg_path_conversion_matches_kurbo_svg_parser() {
        let cases = [
            (
                "absolute-relative-implicit-lines",
                "M-0 1.125 2.375 3.625m4.125-5.125 6.125 7.125L20.25 21.375 22.5 23.625l2.125-3.25 4.5 5.625H30.125 31.25h2.375-1.125V40.5 41.625v2.75-1.5",
                true,
            ),
            (
                "curves-and-cross-family-controls",
                "M10 20C11.125 12.25 13.375 14.5 15.625 16.75 17.875 18.125 19.25 20.375 21.5 22.625S23.75 24.875 25 26.125s1.25 2.375 3.5 4.625Q31.25 32.375 33.5 34.625 35.75 36.875 38 39.125T40.25 41.375t2.5 3.625S47 48.125 49.25 50.375T52.5 53.625c1.125 2.25 3.375 4.5 5.625 6.75q1.25 2.375 3.5 4.625",
                false,
            ),
            (
                "arcs-flags-rotation-relative-degenerate",
                "M1.125 2.25A10.375 20.5 37.25 0 1 30.625 40.75a-12.875 8.25-45.5 1 0 15.125-9.375A0 5 0 0 1 50.25 60.375a5 0 90 1 1-2.125 3.25A4 6-0 0 0 48.125 63.625",
                false,
            ),
            (
                "negative-zero-and-three-decimals",
                "M-0-0L.001-.002l-.003.004H-0v-0C.125-.25.375-.5.625-.75Q.875-.999 1.001-1.125",
                false,
            ),
            (
                "subpaths-close-and-drawing",
                "M1 2Q2 3 3 4ZS5 6 7 8T9 10M20 21l2 3zL4 5Z",
                false,
            ),
        ];

        for (name, source, nest_implicit) in cases {
            let mut path = oxvg_path::Path::parse_string(source).unwrap();
            if nest_implicit {
                let command = path
                    .0
                    .iter_mut()
                    .find(|command| command.is_implicit())
                    .unwrap();
                *command = oxvg_path::command::Data::Implicit(Box::new(command.clone()));
            }
            let direct = bezpath_from_oxvg_path(&path);
            let parsed = BezPath::from_svg(&path.to_string()).unwrap();
            assert_eq!(
                direct.elements().len(),
                parsed.elements().len(),
                "{name}: element count"
            );

            let assert_point = |index: usize, field: &str, direct: Point, parsed: Point| {
                assert_eq!(
                    [direct.x.to_bits(), direct.y.to_bits()],
                    [parsed.x.to_bits(), parsed.y.to_bits()],
                    "{name}: element {index} {field}"
                );
            };
            for (index, (direct, parsed)) in
                direct.elements().iter().zip(parsed.elements()).enumerate()
            {
                match (*direct, *parsed) {
                    (PathEl::MoveTo(a), PathEl::MoveTo(b))
                    | (PathEl::LineTo(a), PathEl::LineTo(b)) => {
                        assert_point(index, "point", a, b);
                    }
                    (PathEl::QuadTo(a1, a2), PathEl::QuadTo(b1, b2)) => {
                        assert_point(index, "control", a1, b1);
                        assert_point(index, "point", a2, b2);
                    }
                    (PathEl::CurveTo(a1, a2, a3), PathEl::CurveTo(b1, b2, b3)) => {
                        assert_point(index, "control1", a1, b1);
                        assert_point(index, "control2", a2, b2);
                        assert_point(index, "point", a3, b3);
                    }
                    (PathEl::ClosePath, PathEl::ClosePath) => {}
                    (direct, parsed) => {
                        panic!("{name}: element {index} variant differs: {direct:?} != {parsed:?}")
                    }
                }
            }
        }
    }

    #[test]
    fn point_line_distance_measures_perpendicular_offset() {
        let a = Point::new(0.0, 0.0);
        let b = Point::new(4.0, 0.0);
        // 3 units above the line y = 0.
        assert!((point_line_distance(Point::new(2.0, 3.0), a, b) - 3.0).abs() < 1e-9);
        // Directly on the line.
        assert!(point_line_distance(Point::new(2.0, 0.0), a, b) < 1e-9);
    }

    #[test]
    fn point_line_distance_falls_back_to_endpoint_distance_when_segment_is_degenerate() {
        let a = Point::new(1.0, 1.0);
        // a ≈ b, so there is no line — distance collapses to |p - a| = sqrt(3² + 4²) = 5.
        assert!((point_line_distance(Point::new(4.0, 5.0), a, a) - 5.0).abs() < 1e-9);
    }

    #[test]
    fn merges_runs_of_collinear_lines_into_a_single_segment() {
        // Three collinear horizontal segments followed by a turn.
        let path = quadratic_path_from_svg_path_data("M0,0 L10,0 L20,0 L30,0 L30,10").unwrap();
        let lines = path
            .elements()
            .iter()
            .filter(|el| matches!(el, PathEl::LineTo(_)))
            .count();
        assert_eq!(
            lines, 2,
            "the collinear run collapses to one line; the turn stays"
        );
        assert!(
            matches!(path.elements().last(), Some(PathEl::LineTo(p)) if (p.x - 30.0).abs() < 1e-9 && (p.y - 10.0).abs() < 1e-9),
            "the final endpoint must be preserved exactly",
        );
    }

    #[test]
    fn collapses_a_near_straight_quadratic_to_a_line() {
        // Control point sits ~0.1 units off the chord — within tolerance.
        const { assert!(SIMPLIFY_TOLERANCE > 0.1) };
        let path = quadratic_path_from_svg_path_data("M0,0 Q5,0.1 10,0").unwrap();
        assert!(
            !path
                .elements()
                .iter()
                .any(|el| matches!(el, PathEl::QuadTo(..))),
            "a near-straight quadratic should be emitted as a line, not a curve",
        );
    }

    #[test]
    fn preserves_a_genuinely_curved_quadratic() {
        // Control point sits 50 units off the chord — a real curve.
        let path = quadratic_path_from_svg_path_data("M0,0 Q5,50 10,0").unwrap();
        assert!(
            path.elements()
                .iter()
                .any(|el| matches!(el, PathEl::QuadTo(..))),
            "a genuinely curved quadratic must be kept",
        );
    }
}