intl 0.5.2

//! Locale-aware date and time formatting (CLDR / UTS #35, Gregorian).
//! Requires the `alloc` feature.
//!
//! A [`DateTime`] holds the broken-down fields (no calendar arithmetic or time
//! zones); [`format_date`] / [`format_time`] / [`format_datetime`] render it with
//! the locale's CLDR patterns, month/weekday names, and am/pm markers. The
//! weekday is derived from the proleptic Gregorian date.
//!
//! ```
//! use intl::datetime::{DateTime, format_date, format_time, DateStyle};
//! let dt = DateTime { year: 2026, month: 6, day: 4, hour: 14, minute: 30, second: 5, millisecond: 0 };
//! assert_eq!(format_date("en", &dt, DateStyle::Long), "June 4, 2026");
//! assert_eq!(format_date("en", &dt, DateStyle::Medium), "Jun 4, 2026");
//! assert_eq!(format_time("en", &dt, DateStyle::Short), "2:30\u{202f}PM");
//! ```

use crate::cldr::{CalendarSpec, calendar_spec};
use alloc::string::{String, ToString};
use alloc::vec::Vec;

/// A broken-down Gregorian date and time. Fields are not validated.
#[derive(Debug, Clone, Copy, PartialEq, Eq)]
pub struct DateTime {
    /// Proleptic Gregorian year (e.g. 2026).
    pub year: i32,
    /// Month, 1–12.
    pub month: u8,
    /// Day of month, 1–31.
    pub day: u8,
    /// Hour, 0–23.
    pub hour: u8,
    /// Minute, 0–59.
    pub minute: u8,
    /// Second, 0–59.
    pub second: u8,
    /// Millisecond, 0–999 (sub-second precision; 0 when unused).
    pub millisecond: u16,
}

impl Default for DateTime {
    /// The Unix epoch, `1970-01-01T00:00:00.000`.
    fn default() -> Self {
        DateTime {
            year: 1970,
            month: 1,
            day: 1,
            hour: 0,
            minute: 0,
            second: 0,
            millisecond: 0,
        }
    }
}

impl DateTime {
    /// Render as a machine-readable ISO-8601 timestamp
    /// (`YYYY-MM-DDTHH:MM:SS`), independent of locale. A non-zero
    /// [`millisecond`](Self::millisecond) is appended as `.SSS`; it is omitted
    /// entirely when zero.
    #[must_use]
    pub fn to_iso8601(&self) -> String {
        let base = alloc::format!(
            "{:04}-{:02}-{:02}T{:02}:{:02}:{:02}",
            self.year,
            self.month,
            self.day,
            self.hour,
            self.minute,
            self.second
        );
        if self.millisecond == 0 {
            base
        } else {
            alloc::format!("{base}.{:03}", self.millisecond)
        }
    }

    /// The ISO-8601 weekday: 1 = Monday … 7 = Sunday.
    #[must_use]
    pub fn weekday(&self) -> u8 {
        crate::calendar::day_of_week(self.year as i64, self.month as i64, self.day as i64)
    }

    /// This date-time advanced by `delta` seconds (negative to go back), with
    /// day/month/year carry handled through the proleptic Gregorian calendar.
    ///
    /// ```
    /// use intl::datetime::DateTime;
    /// let dt = DateTime { year: 2026, month: 12, day: 31, hour: 23, minute: 59, second: 30, millisecond: 0 };
    /// let next = dt.add_seconds(90); // crosses into the new year
    /// assert_eq!(next, DateTime { year: 2027, month: 1, day: 1, hour: 0, minute: 1, second: 0, millisecond: 0 });
    /// ```
    #[must_use]
    pub fn add_seconds(&self, delta: i64) -> DateTime {
        let jdn =
            crate::calendar::gregorian_to_jdn(self.year as i64, self.month as i64, self.day as i64);
        // Saturating arithmetic: an extreme year combined with an extreme delta
        // would otherwise overflow i64 and panic in debug builds.
        let total = jdn
            .saturating_mul(86_400)
            .saturating_add(self.hour as i64 * 3600)
            .saturating_add(self.minute as i64 * 60)
            .saturating_add(self.second as i64)
            .saturating_add(delta);
        let (new_jdn, sod) = (total.div_euclid(86_400), total.rem_euclid(86_400));
        let (y, m, d) = crate::calendar::jdn_to_gregorian(new_jdn);
        DateTime {
            year: y as i32,
            month: m as u8,
            day: d as u8,
            hour: (sod / 3600) as u8,
            minute: (sod % 3600 / 60) as u8,
            second: (sod % 60) as u8,
            millisecond: self.millisecond,
        }
    }

    /// This date advanced by `delta` whole days (keeping the time of day).
    #[must_use]
    pub fn add_days(&self, delta: i64) -> DateTime {
        self.add_seconds(delta * 86_400)
    }

    /// Parse an ISO-8601 timestamp such as `"2026-06-04T14:30:05"` or
    /// `"2026-06-04T14:30:05.250"`. Accepts a space instead of `T`, an omitted
    /// time or seconds, optional fractional seconds (`.S`–`.SSS…`, truncated to
    /// millisecond precision), and a trailing `Z`. Returns `None` if malformed.
    /// (A time-zone offset, if present, is ignored.)
    #[must_use]
    pub fn parse_iso8601(s: &str) -> Option<DateTime> {
        let s = s.trim().trim_end_matches('Z');
        let (date, time) = match s.split_once(['T', ' ']) {
            Some((d, t)) => (d, Some(t)),
            None => (s, None),
        };
        let mut dp = date.split('-');
        let year: i32 = dp.next()?.parse().ok()?;
        let month: u8 = dp.next()?.parse().ok()?;
        let day: u8 = dp.next()?.parse().ok()?;
        if dp.next().is_some() || !(1..=12).contains(&month) || !(1..=31).contains(&day) {
            return None;
        }
        let (hour, minute, second, millisecond) = match time {
            None => (0, 0, 0, 0),
            Some(t) => {
                // Drop any zone offset on the time component.
                let t = t.split(['+', '-']).next().unwrap_or(t);
                let mut tp = t.split(':');
                let h: u8 = tp.next()?.parse().ok()?;
                let mi: u8 = tp.next()?.parse().ok()?;
                let (se, ms) = match tp.next() {
                    Some(x) => {
                        let (whole, frac) = match x.split_once(['.', ',']) {
                            Some((w, f)) => (w, Some(f)),
                            None => (x, None),
                        };
                        let se: u8 = whole.parse().ok()?;
                        let ms = match frac {
                            None | Some("") => 0u16,
                            Some(f) => {
                                if !f.bytes().all(|b| b.is_ascii_digit()) {
                                    return None;
                                }
                                // First up-to-3 fractional digits, scaled to ms.
                                let take = &f[..f.len().min(3)];
                                let v: u16 = take.parse().ok()?;
                                v * 10u16.pow(3 - take.len() as u32)
                            }
                        };
                        (se, ms)
                    }
                    None => (0, 0),
                };
                (h, mi, se, ms)
            }
        };
        Some(DateTime {
            year,
            month,
            day,
            hour,
            minute,
            second,
            millisecond,
        })
    }
}

/// The kind of a [`DateTimePart`] produced by [`format_to_parts`], matching the
/// ECMA-402 `Intl.DateTimeFormat.prototype.formatToParts` part `type` values.
#[derive(Debug, Clone, Copy, PartialEq, Eq)]
pub enum DateTimePartType {
    /// Weekday name.
    Weekday,
    /// Era name.
    Era,
    /// Year.
    Year,
    /// Month (number or name).
    Month,
    /// Day of month.
    Day,
    /// Hour.
    Hour,
    /// Minute.
    Minute,
    /// Second.
    Second,
    /// Fractional second digits.
    FractionalSecond,
    /// Day period (AM/PM).
    DayPeriod,
    /// Time-zone name or offset.
    TimeZoneName,
    /// Literal text (separators, glue).
    Literal,
}

impl DateTimePartType {
    /// The ECMA-402 part `type` string for this kind.
    #[must_use]
    pub fn as_str(&self) -> &'static str {
        match self {
            DateTimePartType::Weekday => "weekday",
            DateTimePartType::Era => "era",
            DateTimePartType::Year => "year",
            DateTimePartType::Month => "month",
            DateTimePartType::Day => "day",
            DateTimePartType::Hour => "hour",
            DateTimePartType::Minute => "minute",
            DateTimePartType::Second => "second",
            DateTimePartType::FractionalSecond => "fractionalSecond",
            DateTimePartType::DayPeriod => "dayPeriod",
            DateTimePartType::TimeZoneName => "timeZoneName",
            DateTimePartType::Literal => "literal",
        }
    }
}

/// One tagged segment of a formatted date-time (see [`format_to_parts`]).
#[derive(Debug, Clone, PartialEq, Eq)]
pub struct DateTimePart {
    /// What this segment represents.
    pub kind: DateTimePartType,
    /// The literal text of this segment.
    pub value: String,
}

/// One of the four CLDR length styles.
#[derive(Debug, Clone, Copy, PartialEq, Eq)]
pub enum DateStyle {
    /// Full ("Thursday, June 4, 2026").
    Full,
    /// Long ("June 4, 2026").
    Long,
    /// Medium ("Jun 4, 2026").
    Medium,
    /// Short ("6/4/26").
    Short,
}

impl DateStyle {
    fn idx(self) -> usize {
        match self {
            DateStyle::Full => 0,
            DateStyle::Long => 1,
            DateStyle::Medium => 2,
            DateStyle::Short => 3,
        }
    }
}

/// Day of week for a proleptic Gregorian date: 0 = Sunday … 6 = Saturday
/// (Sakamoto's algorithm).
fn weekday(dt: &DateTime) -> usize {
    let t = [0, 3, 2, 5, 0, 3, 5, 1, 4, 6, 2, 4];
    // Compute in i64: i32 year arithmetic here overflows for extreme years (and
    // `year - 1` underflows at i32::MIN) on unvalidated DateTime input.
    let m = (dt.month as i64).clamp(1, 12);
    let d = dt.day as i64;
    let y = if m < 3 {
        dt.year as i64 - 1
    } else {
        dt.year as i64
    };
    (y + y / 4 - y / 100 + y / 400 + t[(m - 1) as usize] + d).rem_euclid(7) as usize
}

fn two(n: i64) -> String {
    alloc::format!("{n:02}")
}

/// The flexible day-period name array for a field width `n` (B/BB/BBB →
/// abbreviated, BBBB → wide, BBBBB → narrow).
fn day_period_names(s: &CalendarSpec, n: usize) -> &[Option<&'static str>; 10] {
    if n >= 5 {
        &s.day_periods_narrow
    } else if n == 4 {
        &s.day_periods_wide
    } else {
        &s.day_periods_abbr
    }
}

/// Render one date-field run (`field` repeated `n` times) of a CLDR pattern.
fn field(field: char, n: usize, dt: &DateTime, s: &CalendarSpec) -> String {
    let m = dt.month as usize;
    // Index for the 12-element month-name arrays, clamped so an out-of-range
    // (unvalidated) month never indexes out of bounds.
    let mi = m.clamp(1, 12) - 1;
    match field {
        'y' | 'Y' => {
            if n == 2 {
                two((dt.year.rem_euclid(100)) as i64)
            } else {
                dt.year.to_string()
            }
        }
        'M' | 'L' => match n {
            1 => m.to_string(),
            2 => two(m as i64),
            3 => s.months_abbr[mi].to_string(),
            5 => s.months_narrow[mi].to_string(),
            _ => s.months_wide[mi].to_string(),
        },
        'd' => {
            if n >= 2 {
                two(dt.day as i64)
            } else {
                dt.day.to_string()
            }
        }
        'E' | 'e' | 'c' => {
            let w = weekday(dt);
            if n == 5 {
                s.days_narrow[w].to_string()
            } else if n >= 4 {
                s.days_wide[w].to_string()
            } else {
                s.days_abbr[w].to_string()
            }
        }
        'G' => {
            // Gregorian era: index 0 = BCE (year ≤ 0), 1 = CE.
            let idx = usize::from(dt.year > 0);
            if n >= 5 {
                s.eras_narrow[idx]
            } else if n == 4 {
                s.eras_wide[idx]
            } else {
                s.eras_abbr[idx]
            }
            .to_string()
        }
        'h' => {
            // h12: 1–12 (12-hour clock). Widen first: `dt.hour + 11` would
            // overflow u8 for hour > 244.
            let h = ((dt.hour as u16 + 11) % 12) + 1;
            if n >= 2 { two(h as i64) } else { h.to_string() }
        }
        'K' => {
            // h11: 0–11 (12-hour clock, midnight/noon = 0).
            let h = (dt.hour as u16) % 12;
            if n >= 2 { two(h as i64) } else { h.to_string() }
        }
        'H' => {
            // h23: 0–23.
            if n >= 2 {
                two(dt.hour as i64)
            } else {
                dt.hour.to_string()
            }
        }
        'k' => {
            // h24: 1–24 (midnight = 24).
            let h = if dt.hour == 0 { 24 } else { dt.hour as u16 };
            if n >= 2 { two(h as i64) } else { h.to_string() }
        }
        'm' => {
            if n >= 2 {
                two(dt.minute as i64)
            } else {
                dt.minute.to_string()
            }
        }
        's' => {
            if n >= 2 {
                two(dt.second as i64)
            } else {
                dt.second.to_string()
            }
        }
        'a' => if dt.hour < 12 { s.am } else { s.pm }.to_string(),
        'b' => {
            // am/pm, but midnight/noon at the exact instant.
            let w = day_period_names(s, n);
            if dt.minute == 0 && dt.second == 0 && dt.millisecond == 0 {
                if dt.hour == 0
                    && let Some(x) = w[0]
                {
                    return x.to_string();
                }
                if dt.hour == 12
                    && let Some(x) = w[1]
                {
                    return x.to_string();
                }
            }
            if dt.hour < 12 { s.am } else { s.pm }.to_string()
        }
        'B' => {
            // Flexible day period (morning/afternoon/evening/night) by hour
            // range, with midnight/noon at the exact instant; falls back to am/pm.
            let w = day_period_names(s, n);
            if dt.minute == 0 && dt.second == 0 && dt.millisecond == 0 {
                if dt.hour == 0
                    && let Some(x) = w[0]
                {
                    return x.to_string();
                }
                if dt.hour == 12
                    && let Some(x) = w[1]
                {
                    return x.to_string();
                }
            }
            let minute_of_day = (dt.hour as u16).min(23) * 60 + (dt.minute as u16).min(59);
            let idx = s.day_period_index(minute_of_day);
            if idx != 0xFF
                && let Some(x) = w[idx as usize]
            {
                return x.to_string();
            }
            if dt.hour < 12 { s.am } else { s.pm }.to_string()
        }
        'S' => {
            // Fractional second: `n` digits from the millisecond field.
            let ms = dt.millisecond.min(999);
            let base = alloc::format!("{ms:03}");
            if n <= 3 {
                base[..n].to_string()
            } else {
                let mut out = base;
                for _ in 0..(n - 3) {
                    out.push('0');
                }
                out
            }
        }
        _ => String::new(), // unsupported field (e.g. time zone) -> nothing
    }
}

/// Map a CLDR field letter to its ECMA-402 `formatToParts` part type.
fn part_type(ch: char) -> DateTimePartType {
    use DateTimePartType::*;
    match ch {
        'y' | 'Y' | 'u' | 'U' | 'r' => Year,
        'M' | 'L' => Month,
        'd' | 'D' | 'F' | 'g' => Day,
        'E' | 'e' | 'c' => Weekday,
        'h' | 'H' | 'k' | 'K' => Hour,
        'm' => Minute,
        's' => Second,
        'S' | 'A' => FractionalSecond,
        'a' | 'b' | 'B' => DayPeriod,
        'G' => Era,
        'z' | 'Z' | 'O' | 'v' | 'V' | 'X' | 'x' => TimeZoneName,
        _ => Literal,
    }
}

/// Parts-producing core of [`render`]: interprets a CLDR pattern into tagged
/// [`DateTimePart`]s. Adjacent literals are coalesced and empty field outputs
/// (unsupported letters) are dropped, so joining the part values reproduces
/// [`render`]'s string exactly.
fn render_parts(pattern: &str, dt: &DateTime, s: &CalendarSpec) -> Vec<DateTimePart> {
    fn push_lit(parts: &mut Vec<DateTimePart>, text: &str) {
        if text.is_empty() {
            return;
        }
        if let Some(last) = parts.last_mut()
            && last.kind == DateTimePartType::Literal
        {
            last.value.push_str(text);
            return;
        }
        parts.push(DateTimePart {
            kind: DateTimePartType::Literal,
            value: String::from(text),
        });
    }

    let c: Vec<char> = pattern.chars().collect();
    let mut parts: Vec<DateTimePart> = Vec::new();
    let mut i = 0;
    while i < c.len() {
        let ch = c[i];
        if ch == '\'' {
            i += 1;
            if i < c.len() && c[i] == '\'' {
                push_lit(&mut parts, "'");
                i += 1;
                continue;
            }
            let mut lit = String::new();
            while i < c.len() && c[i] != '\'' {
                lit.push(c[i]);
                i += 1;
            }
            i += 1; // closing quote
            push_lit(&mut parts, &lit);
        } else if ch.is_ascii_alphabetic() {
            let start = i;
            while i < c.len() && c[i] == ch {
                i += 1;
            }
            let val = field(ch, i - start, dt, s);
            if !val.is_empty() {
                parts.push(DateTimePart {
                    kind: part_type(ch),
                    value: val,
                });
            }
        } else {
            let mut buf = [0u8; 4];
            push_lit(&mut parts, ch.encode_utf8(&mut buf));
            i += 1;
        }
    }
    parts
}

/// Interpret a CLDR date/time pattern, handling quoted literals.
fn render(pattern: &str, dt: &DateTime, s: &CalendarSpec) -> String {
    let mut out = String::new();
    for part in render_parts(pattern, dt, s) {
        out.push_str(&part.value);
    }
    out
}

fn spec(lang: &str) -> CalendarSpec {
    let norm: String = lang
        .chars()
        .map(|c| {
            if c == '_' {
                '-'
            } else {
                c.to_ascii_lowercase()
            }
        })
        .collect();
    let mut end = norm.len();
    loop {
        if let Some(s) = calendar_spec(&norm[..end]) {
            return s;
        }
        match norm[..end].rfind('-') {
            Some(i) => end = i,
            None => return calendar_spec("en").expect("root calendar present"),
        }
    }
}

/// Format the date part of `dt` in `lang` at the given `style`.
#[must_use]
pub fn format_date(lang: &str, dt: &DateTime, style: DateStyle) -> String {
    let s = spec(lang);
    render(s.date[style.idx()], dt, &s)
}

/// Format the time part of `dt` in `lang` at the given `style`.
#[must_use]
pub fn format_time(lang: &str, dt: &DateTime, style: DateStyle) -> String {
    let s = spec(lang);
    render(s.time[style.idx()], dt, &s)
}

/// Format `dt` with a CLDR *skeleton* (e.g. `"yMMMd"`, `"Hm"`, `"MMMEd"`) — the
/// modern, flexible date API: the skeleton names the fields you want and the
/// locale supplies their order and punctuation. Falls back through the locale
/// chain (and to English), then to the medium date pattern for an unknown
/// skeleton.
///
/// ```
/// use intl::datetime::{DateTime, format_skeleton};
/// let dt = DateTime { year: 2026, month: 6, day: 4, hour: 14, minute: 30, second: 5, millisecond: 0 };
/// assert_eq!(format_skeleton("en", &dt, "yMMMd"), "Jun 4, 2026");
/// assert_eq!(format_skeleton("de", &dt, "yMMMd"), "4. Juni 2026");
/// assert_eq!(format_skeleton("en", &dt, "Hm"), "14:30");
/// ```
#[must_use]
pub fn format_skeleton(lang: &str, dt: &DateTime, skeleton: &str) -> String {
    let s = spec(lang);
    let norm: String = lang
        .chars()
        .map(|c| {
            if c == '_' {
                '-'
            } else {
                c.to_ascii_lowercase()
            }
        })
        .collect();
    let mut end = norm.len();
    let pattern = loop {
        if let Some(p) = crate::cldr::skeleton_pattern(&norm[..end], skeleton) {
            break p;
        }
        match norm[..end].rfind('-') {
            Some(i) => end = i,
            None => break crate::cldr::skeleton_pattern("en", skeleton).unwrap_or(s.date[2]),
        }
    };
    render(pattern, dt, &s)
}

/// Render a non-Gregorian date with a calendar's month names/era; the weekday
/// name (if any) uses the Gregorian day names at the date's `jdn`.
#[cfg(feature = "calendars-extra")]
fn render_alt(
    cal: &crate::cldr::AltCalSpec,
    style: DateStyle,
    year: i64,
    month: i64,
    day: i64,
    jdn: i64,
    greg: &CalendarSpec,
) -> String {
    let wd = ((jdn.rem_euclid(7) + 1) % 7) as usize; // 0 = Sunday
    let c: Vec<char> = cal.date[style.idx()].chars().collect();
    let mut out = String::new();
    let mut i = 0;
    while i < c.len() {
        let ch = c[i];
        if ch == '\'' {
            i += 1;
            if i < c.len() && c[i] == '\'' {
                out.push('\'');
                i += 1;
                continue;
            }
            while i < c.len() && c[i] != '\'' {
                out.push(c[i]);
                i += 1;
            }
            i += 1;
        } else if ch.is_ascii_alphabetic() {
            let start = i;
            while i < c.len() && c[i] == ch {
                i += 1;
            }
            let (n, m) = (i - start, month as usize);
            let mi = m.clamp(1, 12) - 1; // unvalidated month must not index OOB
            match ch {
                'y' | 'Y' => out.push_str(&year.to_string()),
                'M' | 'L' => match n {
                    1 => out.push_str(&m.to_string()),
                    2 => out.push_str(&two(m as i64)),
                    3 => out.push_str(cal.months_abbr[mi]),
                    _ => out.push_str(cal.months_wide[mi]),
                },
                'd' => out.push_str(&day.to_string()),
                'E' | 'e' | 'c' => out.push_str(if n >= 4 {
                    greg.days_wide[wd]
                } else {
                    greg.days_abbr[wd]
                }),
                'G' => {
                    // Era by year sign (0 = current era AH/AP, 1 = pre-era
                    // BH/BP) and width (G/GG/GGG = abbr, GGGG = wide,
                    // GGGGG = narrow).
                    let ei = usize::from(year <= 0);
                    out.push_str(if n >= 5 {
                        cal.eras_narrow[ei]
                    } else if n == 4 {
                        cal.eras_wide[ei]
                    } else {
                        cal.eras_abbr[ei]
                    });
                }
                _ => {}
            }
        } else {
            out.push(ch);
            i += 1;
        }
    }
    out
}

#[cfg(feature = "calendars-extra")]
fn alt_spec(lang: &str, f: fn(&str) -> Option<crate::cldr::AltCalSpec>) -> crate::cldr::AltCalSpec {
    let norm: String = lang
        .chars()
        .map(|c| {
            if c == '_' {
                '-'
            } else {
                c.to_ascii_lowercase()
            }
        })
        .collect();
    let mut end = norm.len();
    loop {
        if let Some(s) = f(&norm[..end]) {
            return s;
        }
        match norm[..end].rfind('-') {
            Some(i) => end = i,
            None => return f("en").expect("root calendar present"),
        }
    }
}

/// Format an Islamic (Hijri) date in `lang`, e.g.
/// `format_islamic_date("en", 1445, 9, 1, DateStyle::Long)` →
/// `"Ramadan 1, 1445 AH"` (localized month names + era).
#[cfg(feature = "calendars-extra")]
#[must_use]
pub fn format_islamic_date(
    lang: &str,
    year: i64,
    month: i64,
    day: i64,
    style: DateStyle,
) -> String {
    let cal = alt_spec(lang, crate::cldr::islamic_spec);
    let jdn = crate::calendar::islamic_to_jdn(year, month, day);
    render_alt(&cal, style, year, month, day, jdn, &spec(lang))
}

/// Format an Umm al-Qura (Saudi) Islamic date in `lang`, e.g.
/// `format_islamic_umalqura_date("en", 1445, 9, 1, DateStyle::Long)` →
/// `"Ramadan 1, 1445 AH"`. Identical to [`format_islamic_date`] but the Hijri
/// `(year, month, day)` is resolved through the Umm al-Qura month-length table
/// (the official Saudi calendar) instead of the civil tabular rule; the
/// localized month names and era ("AH") are shared.
#[cfg(feature = "calendars-extra")]
#[must_use]
pub fn format_islamic_umalqura_date(
    lang: &str,
    year: i64,
    month: i64,
    day: i64,
    style: DateStyle,
) -> String {
    let cal = alt_spec(lang, crate::cldr::islamic_spec);
    let jdn = crate::calendar::umalqura_to_jdn(year, month, day);
    render_alt(&cal, style, year, month, day, jdn, &spec(lang))
}

/// Render a Chinese-calendar date with a locale's cyclic year names, numeric
/// month names and leap-month marker. The weekday name (if any) uses the
/// Gregorian day names at the date's `jdn`.
///
/// - `U` renders the sexagenary cyclic year name (e.g. 甲辰 / `jia-chen`).
/// - `r` renders the related Gregorian year (`related`).
/// - `y` renders the 1-based cyclic year number (`cyclic1`, 1..=60), numeric.
/// - `M`/`L` render the numeric month name (or number), wrapped in the leap
///   marker pattern when `is_leap` is set.
#[cfg(feature = "calendars-extra")]
#[allow(clippy::too_many_arguments)]
fn render_chinese(
    cal: &crate::cldr::ChineseCalSpec,
    style: DateStyle,
    month: i64,
    day: i64,
    is_leap: bool,
    related: i64,
    cyclic1: i64,
    jdn: i64,
    greg: &CalendarSpec,
) -> String {
    let wd = ((jdn.rem_euclid(7) + 1) % 7) as usize; // 0 = Sunday
    let ci = (cyclic1.clamp(1, 60) - 1) as usize; // cyclic name index
    let c: Vec<char> = cal.date[style.idx()].chars().collect();
    let mut out = String::new();
    let mut i = 0;
    while i < c.len() {
        let ch = c[i];
        if ch == '\'' {
            i += 1;
            if i < c.len() && c[i] == '\'' {
                out.push('\'');
                i += 1;
                continue;
            }
            while i < c.len() && c[i] != '\'' {
                out.push(c[i]);
                i += 1;
            }
            i += 1;
        } else if ch.is_ascii_alphabetic() {
            let start = i;
            while i < c.len() && c[i] == ch {
                i += 1;
            }
            let (n, m) = (i - start, month as usize);
            let mi = m.clamp(1, 12) - 1; // unvalidated month must not index OOB
            match ch {
                'M' | 'L' => {
                    let name = match n {
                        1 => alloc::format!("{m}"),
                        2 => two(m as i64),
                        3 => String::from(cal.months_abbr[mi]),
                        _ => String::from(cal.months_wide[mi]),
                    };
                    if is_leap {
                        let pat = if n == 3 { cal.leap_abbr } else { cal.leap_wide };
                        out.push_str(&pat.replace("{0}", &name));
                    } else {
                        out.push_str(&name);
                    }
                }
                'd' => out.push_str(&day.to_string()),
                'E' | 'e' | 'c' => out.push_str(if n >= 4 {
                    greg.days_wide[wd]
                } else {
                    greg.days_abbr[wd]
                }),
                // Related Gregorian year.
                'r' => out.push_str(&related.to_string()),
                // Cyclic (sexagenary) year name.
                'U' => out.push_str(cal.cyclic[ci]),
                // Cyclic (sexagenary) year *number*, 1..=60.
                'y' | 'Y' => {
                    if n == 2 {
                        out.push_str(&two(cyclic1.rem_euclid(100)));
                    } else {
                        out.push_str(&cyclic1.to_string());
                    }
                }
                _ => {}
            }
        } else {
            out.push(ch);
            i += 1;
        }
    }
    out
}

/// Format a Chinese-calendar date in `lang`, e.g.
/// `format_chinese_date("en", 2024, 1, 1, false, DateStyle::Long)` →
/// `"First Month 1, 2024(jia-chen)"`: the localized numeric month name, the
/// related Gregorian year (`r`) and the sexagenary cyclic year name (`U`).
///
/// `year`/`month`/`day` are the Chinese calendar fields (supported range: Chinese
/// years 1900–2099) and `is_leap_month` marks the intercalary month that follows
/// `month` (the month name is then wrapped in the locale's leap marker, e.g.
/// `"闰正月"` / `"First Monthbis"`). The related year and the cyclic year are
/// derived from the Gregorian year in which the Chinese year begins.
#[cfg(feature = "calendars-extra")]
#[must_use]
pub fn format_chinese_date(
    lang: &str,
    year: i64,
    month: i64,
    day: i64,
    is_leap_month: bool,
    style: DateStyle,
) -> String {
    let cal = chinese_alt_spec(lang);
    // The Gregorian year in which this Chinese year begins (its 1st month, 1st
    // day). Falls back to `year` itself if the conversion is out of range.
    let related = crate::calendar::chinese_to_gregorian(year, 1, 1, false).map_or(year, |g| g.0);
    // 1-based sexagenary (stem-branch) number: (relatedYear − 4) mod 60, +1.
    let cyclic1 = (related - 4).rem_euclid(60) + 1;
    let jdn = crate::calendar::chinese_to_jdn(year, month, day, is_leap_month).unwrap_or(0);
    render_chinese(
        &cal,
        style,
        month,
        day,
        is_leap_month,
        related,
        cyclic1,
        jdn,
        &spec(lang),
    )
}

/// Chinese-calendar spec for `lang` via the locale fallback chain (to `en`).
#[cfg(feature = "calendars-extra")]
fn chinese_alt_spec(lang: &str) -> crate::cldr::ChineseCalSpec {
    let norm = normalize_lang(lang);
    let mut end = norm.len();
    loop {
        if let Some(s) = crate::cldr::chinese_spec(&norm[..end]) {
            return s;
        }
        match norm[..end].rfind('-') {
            Some(i) => end = i,
            None => return crate::cldr::chinese_spec("en").expect("root chinese calendar present"),
        }
    }
}

/// Format a Persian (Solar Hijri) date in `lang`, e.g.
/// `format_persian_date("en", 1404, 1, 1, DateStyle::Long)` →
/// `"Farvardin 1, 1404 AP"` (localized month names + era).
#[cfg(feature = "calendars-extra")]
#[must_use]
pub fn format_persian_date(
    lang: &str,
    year: i64,
    month: i64,
    day: i64,
    style: DateStyle,
) -> String {
    let cal = alt_spec(lang, crate::cldr::persian_spec);
    let jdn = crate::calendar::persian_to_jdn(year, month, day);
    render_alt(&cal, style, year, month, day, jdn, &spec(lang))
}

/// Gregorian start dates `(year, month, day)` of every Japanese nengō, indexed
/// by CLDR era index 0 (Taika) .. 236 (Reiwa). Historical entries (0..=231) are
/// ICU4C's `japancal.cpp` `kEraInfo`; the 5 modern entries (232..=236) are the
/// Meiji…Reiwa starts. Kan'ei (index 198) is normalized to `1624-03-01` (ICU
/// stores an out-of-range `1624-02-30`); the two pre-1582 anomalies (Einin 141,
/// Eishō 187) are likewise given valid days. These dates are the exact Gregorian
/// era boundaries ICU/V8 use for dates on or after the 1582-10-15 Gregorian
/// cutover; before it, the Julian–Gregorian offset applies.
#[cfg(feature = "calendars-extra")]
#[rustfmt::skip]
const JAPANESE_ERA_STARTS: [(i16, u8, u8); 237] = [
    (645,6,19),(650,2,15),(672,1,1),(686,7,20),(701,3,21),(704,5,10),(708,1,11),
    (715,9,2),(717,11,17),(724,2,4),(729,8,5),(749,4,14),(749,7,2),(757,8,18),
    (765,1,7),(767,8,16),(770,10,1),(781,1,1),(782,8,19),(806,5,18),(810,9,19),
    (824,1,5),(834,1,3),(848,6,13),(851,4,28),(854,11,30),(857,2,21),(859,4,15),
    (877,4,16),(885,2,21),(889,4,27),(898,4,26),(901,7,15),(923,4,11),(931,4,26),
    (938,5,22),(947,4,22),(957,10,27),(961,2,16),(964,7,10),(968,8,13),(970,3,25),
    (973,12,20),(976,7,13),(978,11,29),(983,4,15),(985,4,27),(987,4,5),(989,8,8),
    (990,11,7),(995,2,22),(999,1,13),(1004,7,20),(1012,12,25),(1017,4,23),(1021,2,2),
    (1024,7,13),(1028,7,25),(1037,4,21),(1040,11,10),(1044,11,24),(1046,4,14),(1053,1,11),
    (1058,8,29),(1065,8,2),(1069,4,13),(1074,8,23),(1077,11,17),(1081,2,10),(1084,2,7),
    (1087,4,7),(1094,12,15),(1096,12,17),(1097,11,21),(1099,8,28),(1104,2,10),(1106,4,9),
    (1108,8,3),(1110,7,13),(1113,7,13),(1118,4,3),(1120,4,10),(1124,4,3),(1126,1,22),
    (1131,1,29),(1132,8,11),(1135,4,27),(1141,7,10),(1142,4,28),(1144,2,23),(1145,7,22),
    (1151,1,26),(1154,10,28),(1156,4,27),(1159,4,20),(1160,1,10),(1161,9,4),(1163,3,29),
    (1165,6,5),(1166,8,27),(1169,4,8),(1171,4,21),(1175,7,28),(1177,8,4),(1181,7,14),
    (1182,5,27),(1184,4,16),(1185,8,14),(1190,4,11),(1199,4,27),(1201,2,13),(1204,2,20),
    (1206,4,27),(1207,10,25),(1211,3,9),(1213,12,6),(1219,4,12),(1222,4,13),(1224,11,20),
    (1225,4,20),(1227,12,10),(1229,3,5),(1232,4,2),(1233,4,15),(1234,11,5),(1235,9,19),
    (1238,11,23),(1239,2,7),(1240,7,16),(1243,2,26),(1247,2,28),(1249,3,18),(1256,10,5),
    (1257,3,14),(1259,3,26),(1260,4,13),(1261,2,20),(1264,2,28),(1275,4,25),(1278,2,29),
    (1288,4,28),(1293,8,5),(1299,4,25),(1302,11,21),(1303,8,5),(1306,12,14),(1308,10,9),
    (1311,4,28),(1312,3,20),(1317,2,3),(1319,4,28),(1321,2,23),(1324,12,9),(1326,4,26),
    (1329,8,29),(1331,8,9),(1334,1,29),(1336,2,29),(1340,4,28),(1346,12,8),(1370,7,24),
    (1372,4,1),(1375,5,27),(1379,3,22),(1381,2,10),(1384,4,28),(1384,2,27),(1387,8,23),
    (1389,2,9),(1390,3,26),(1394,7,5),(1428,4,27),(1429,9,5),(1441,2,17),(1444,2,5),
    (1449,7,28),(1452,7,25),(1455,7,25),(1457,9,28),(1460,12,21),(1466,2,28),(1467,3,3),
    (1469,4,28),(1487,7,29),(1489,8,21),(1492,7,19),(1501,2,29),(1504,3,1),(1521,8,23),
    (1528,8,20),(1532,7,29),(1555,10,23),(1558,2,28),(1570,4,23),(1573,7,28),(1592,12,8),
    (1596,10,27),(1615,7,13),(1624,3,1),(1644,12,16),(1648,2,15),(1652,9,18),(1655,4,13),
    (1658,7,23),(1661,4,25),(1673,9,21),(1681,9,29),(1684,2,21),(1688,9,30),(1704,3,13),
    (1711,4,25),(1716,6,22),(1736,4,28),(1741,2,27),(1744,2,21),(1748,7,12),(1751,10,27),
    (1764,6,2),(1772,11,16),(1781,4,2),(1789,1,25),(1801,2,5),(1804,2,11),(1818,4,22),
    (1830,12,10),(1844,12,2),(1848,2,28),(1854,11,27),(1860,3,18),(1861,2,19),(1864,2,20),
    (1865,4,7),
    // Modern eras (CLDR indices 232..=236): Meiji, Taishō, Shōwa, Heisei, Reiwa.
    (1868,9,8),(1912,7,30),(1926,12,25),(1989,1,8),(2019,5,1),
];

/// The number of modern Japanese eras (Meiji..Reiwa); CLDR index 232 is the
/// first modern era.
#[cfg(feature = "calendars-extra")]
const JAPANESE_FIRST_MODERN: usize = 232;

/// The CLDR Japanese era index (0..=236) and year-within-era for a Gregorian
/// date, by boundary search over [`JAPANESE_ERA_STARTS`]. Year-within-era is
/// `gregYear − eraStartYear + 1`. Exact vs ICU/V8 for dates on or after the
/// 1582-10-15 Gregorian cutover (this covers every Edo-period era); earlier
/// dates may differ by the Julian–Gregorian offset.
#[cfg(feature = "calendars-extra")]
fn japanese_nengo(year: i64, month: i64, day: i64) -> (usize, i64) {
    for (i, &(sy, sm, sd)) in JAPANESE_ERA_STARTS.iter().enumerate().rev() {
        if (year, month, day) >= (sy as i64, sm as i64, sd as i64) {
            return (i, year - sy as i64 + 1);
        }
    }
    // Before Taika (645): still reckoned in the Taika era with a non-positive year.
    let sy = JAPANESE_ERA_STARTS[0].0 as i64;
    (0, year - sy + 1)
}

/// The localized pre-Meiji nengō names `[wide, abbr, narrow]` for CLDR era
/// `index` (0..=231) in `lang`, via the locale fallback chain (to `en`).
#[cfg(feature = "calendars-extra")]
fn japanese_hist_eras(lang: &str, index: usize) -> [&'static str; 3] {
    let norm = normalize_lang(lang);
    let mut end = norm.len();
    loop {
        if let Some(e) = crate::cldr::japanese_hist_eras(&norm[..end], index) {
            return e;
        }
        match norm[..end].rfind('-') {
            Some(i) => end = i,
            None => return crate::cldr::japanese_hist_eras("en", index).unwrap_or([""; 3]),
        }
    }
}

/// Render a Japanese-calendar date. The Japanese calendar shares the Gregorian
/// month and weekday names (`greg`); only the era (`G`) and the year (`y`, the
/// year-within-era) differ. When `gannen` is set, year 1 of the era renders as 元.
/// A pre-Meiji date (`era_idx == None`) falls back to the localized Gregorian era
/// with `year_in_era` holding the proleptic Gregorian year.
#[cfg(feature = "calendars-extra")]
#[allow(clippy::too_many_arguments)]
fn render_japanese(
    cal: &crate::cldr::JapaneseCalSpec,
    style: DateStyle,
    era_idx: Option<usize>,
    hist_eras: [&'static str; 3],
    year_in_era: i64,
    month: i64,
    day: i64,
    jdn: i64,
    gannen: bool,
    greg: &CalendarSpec,
) -> String {
    let wd = ((jdn.rem_euclid(7) + 1) % 7) as usize; // 0 = Sunday
    let c: Vec<char> = cal.date[style.idx()].chars().collect();
    let mut out = String::new();
    let mut i = 0;
    while i < c.len() {
        let ch = c[i];
        if ch == '\'' {
            i += 1;
            if i < c.len() && c[i] == '\'' {
                out.push('\'');
                i += 1;
                continue;
            }
            while i < c.len() && c[i] != '\'' {
                out.push(c[i]);
                i += 1;
            }
            i += 1;
        } else if ch.is_ascii_alphabetic() {
            let start = i;
            while i < c.len() && c[i] == ch {
                i += 1;
            }
            let (n, m) = (i - start, month as usize);
            let mi = m.clamp(1, 12) - 1; // unvalidated month must not index OOB
            match ch {
                // Year-within-era; 元 (gannen) for year 1 when the pattern uses
                // the `jpanyear` numbering system.
                'y' | 'Y' => {
                    if gannen && year_in_era == 1 {
                        out.push('元');
                    } else if n == 2 {
                        out.push_str(&two(year_in_era.rem_euclid(100)));
                    } else {
                        out.push_str(&year_in_era.to_string());
                    }
                }
                'M' | 'L' => match n {
                    1 => out.push_str(&m.to_string()),
                    2 => out.push_str(&two(m as i64)),
                    3 => out.push_str(greg.months_abbr[mi]),
                    5 => out.push_str(greg.months_narrow[mi]),
                    _ => out.push_str(greg.months_wide[mi]),
                },
                'd' => {
                    if n >= 2 {
                        out.push_str(&two(day));
                    } else {
                        out.push_str(&day.to_string());
                    }
                }
                'E' | 'e' | 'c' => out.push_str(if n >= 5 {
                    greg.days_narrow[wd]
                } else if n >= 4 {
                    greg.days_wide[wd]
                } else {
                    greg.days_abbr[wd]
                }),
                'G' => {
                    let era = match era_idx {
                        // Modern era: pick the width implied by the G-count
                        // (G/GG/GGG = abbr, GGGG = wide, GGGGG = narrow).
                        Some(idx) => {
                            if n >= 5 {
                                cal.eras_narrow[idx]
                            } else if n == 4 {
                                cal.eras_wide[idx]
                            } else {
                                cal.eras_abbr[idx]
                            }
                        }
                        // Pre-Meiji: use the localized historical nengō name at
                        // the width implied by the G-count, falling back to the
                        // localized Gregorian era only if that name is absent.
                        None => {
                            let hname = if n >= 5 {
                                hist_eras[2]
                            } else if n == 4 {
                                hist_eras[0]
                            } else {
                                hist_eras[1]
                            };
                            if !hname.is_empty() {
                                hname
                            } else {
                                let gi = usize::from(year_in_era > 0);
                                if n >= 5 {
                                    greg.eras_narrow[gi]
                                } else if n == 4 {
                                    greg.eras_wide[gi]
                                } else {
                                    greg.eras_abbr[gi]
                                }
                            }
                        }
                    };
                    out.push_str(era);
                }
                _ => {}
            }
        } else {
            out.push(ch);
            i += 1;
        }
    }
    out
}

/// Japanese-calendar spec for `lang` via the locale fallback chain (to `en`).
#[cfg(feature = "calendars-extra")]
fn japanese_alt_spec(lang: &str) -> crate::cldr::JapaneseCalSpec {
    let norm = normalize_lang(lang);
    let mut end = norm.len();
    loop {
        if let Some(s) = crate::cldr::japanese_spec(&norm[..end]) {
            return s;
        }
        match norm[..end].rfind('-') {
            Some(i) => end = i,
            None => {
                return crate::cldr::japanese_spec("en").expect("root japanese calendar present");
            }
        }
    }
}

/// Format a Gregorian date in the localized Japanese (imperial-era) calendar in
/// `lang`, e.g. `format_japanese_date("en", 2019, 5, 1, DateStyle::Long)` →
/// `"May 1, 1 Reiwa"` and `format_japanese_date("ja", 2019, 5, 1, DateStyle::Long)`
/// → `"令和元年5月1日"`.
///
/// `year`/`month`/`day` are the **Gregorian** fields; the era and year-within-era
/// are derived via [`crate::calendar::japanese_era`] (the 5 modern eras: Meiji,
/// Taishō, Shōwa, Heisei, Reiwa). The localized era name is taken at the width
/// implied by the pattern's `G` count; month and weekday names are the Gregorian
/// ones. In Japanese, year 1 of an era prints as 元 (gannen) for the full/long/
/// medium styles (the CLDR `jpanyear` numbering), e.g. `"令和元年"`. A pre-Meiji
/// date is rendered with its historical nengō (e.g. `1850-03-15` → `"嘉永3年…"` /
/// `"3 Kaei…"`), resolved from ICU's Gregorian era-start dates and the localized
/// era names. This is exact vs V8 for dates on or after the 1582 Gregorian
/// cutover (all Edo-period eras); earlier dates carry the Julian–Gregorian offset.
#[cfg(feature = "calendars-extra")]
#[must_use]
pub fn format_japanese_date(
    lang: &str,
    year: i64,
    month: i64,
    day: i64,
    style: DateStyle,
) -> String {
    let cal = japanese_alt_spec(lang);
    let (cldr_idx, year_in_era) = japanese_nengo(year, month, day);
    // Modern eras (Meiji..Reiwa) are indices 232..=236; earlier indices are the
    // historical nengō localized via `japanese_hist_eras`.
    let era_idx = cldr_idx.checked_sub(JAPANESE_FIRST_MODERN);
    let hist_eras = if era_idx.is_none() {
        japanese_hist_eras(lang, cldr_idx)
    } else {
        [""; 3]
    };
    let jdn = crate::calendar::gregorian_to_jdn(year, month, day);
    // Gannen (元) applies only to modern eras whose style pattern uses jpanyear.
    let gannen = era_idx.is_some() && (cal.gannen >> style.idx()) & 1 == 1;
    render_japanese(
        &cal,
        style,
        era_idx,
        hist_eras,
        year_in_era,
        month,
        day,
        jdn,
        gannen,
        &spec(lang),
    )
}

/// Format a fixed UTC offset (in minutes) in the localized GMT form, e.g.
/// `"GMT+5:30"`-style output: `format_gmt_offset("en", 330)` → `"GMT+05:30"`,
/// `format_gmt_offset("fr", -480)` → `"UTC−08:00"`, `0` → `"GMT"` / `"UTC"`.
/// This is the data-light part of time-zone support (a concrete offset, not the
/// IANA zone database).
#[must_use]
pub fn format_gmt_offset(lang: &str, offset_minutes: i32) -> String {
    let norm: String = lang
        .chars()
        .map(|c| {
            if c == '_' {
                '-'
            } else {
                c.to_ascii_lowercase()
            }
        })
        .collect();
    let mut end = norm.len();
    let tz = loop {
        if let Some(t) = crate::cldr::tz_spec(&norm[..end]) {
            break t;
        }
        match norm[..end].rfind('-') {
            Some(i) => end = i,
            None => break crate::cldr::tz_spec("en").expect("root tz present"),
        }
    };
    if offset_minutes == 0 {
        return String::from(tz.zero);
    }
    let (pos, neg) = tz.hour.split_once(';').unwrap_or((tz.hour, tz.hour));
    let sub = if offset_minutes >= 0 { pos } else { neg };
    let (h, m) = (
        offset_minutes.unsigned_abs() / 60,
        offset_minutes.unsigned_abs() % 60,
    );
    let body = sub
        .replace("HH", &alloc::format!("{h:02}"))
        .replace("mm", &alloc::format!("{m:02}"));
    tz.gmt.replace("{0}", &body)
}

/// Format both date and time, combined with the locale's date+time pattern.
#[must_use]
pub fn format_datetime(
    lang: &str,
    dt: &DateTime,
    date_style: DateStyle,
    time_style: DateStyle,
) -> String {
    let s = spec(lang);
    let date = render(s.date[date_style.idx()], dt, &s);
    let time = render(s.time[time_style.idx()], dt, &s);
    s.datetime[date_style.idx()]
        .replace("{1}", &date)
        .replace("{0}", &time)
}

// ---------------------------------------------------------------------------
// ECMA-402-style component options + formatToParts
// ---------------------------------------------------------------------------

/// Width for a numeric field (ECMA-402 `"numeric"` / `"2-digit"`).
#[derive(Debug, Clone, Copy, PartialEq, Eq)]
pub enum Numeric2Digit {
    /// `"numeric"` — no padding.
    Numeric,
    /// `"2-digit"` — zero-padded to two digits.
    TwoDigit,
}

/// Month presentation (ECMA-402 `month`).
#[derive(Debug, Clone, Copy, PartialEq, Eq)]
pub enum MonthStyle {
    /// Numeric (`6`).
    Numeric,
    /// Two-digit (`06`).
    TwoDigit,
    /// Wide name (`June`).
    Long,
    /// Abbreviated name (`Jun`).
    Short,
    /// Narrow name (`J`).
    Narrow,
}

/// Name width for weekday / era / day period (ECMA-402 `"long"`/`"short"`/`"narrow"`).
#[derive(Debug, Clone, Copy, PartialEq, Eq)]
pub enum NameStyle {
    /// Wide.
    Long,
    /// Abbreviated.
    Short,
    /// Narrow.
    Narrow,
}

/// Time-zone-name presentation (ECMA-402 `timeZoneName`). Only the offset forms
/// are rendered today (from a caller-supplied offset); named/generic forms fall
/// back to the offset (no metazone data).
#[derive(Debug, Clone, Copy, PartialEq, Eq)]
pub enum TimeZoneNameStyle {
    /// Long specific name; falls back to the long offset.
    Long,
    /// Short specific name; falls back to the short offset.
    Short,
    /// Short localized GMT offset.
    ShortOffset,
    /// Long localized GMT offset.
    LongOffset,
    /// Short generic name; falls back to the short offset.
    ShortGeneric,
    /// Long generic name; falls back to the long offset.
    LongGeneric,
}

/// Hour cycle (ECMA-402 `hourCycle`). `H11`/`H12` use the 12-hour clock,
/// `H23`/`H24` the 24-hour clock (the 0-vs-1 origin is approximated).
#[derive(Debug, Clone, Copy, PartialEq, Eq)]
pub enum HourCycle {
    /// 0–11 with day period.
    H11,
    /// 1–12 with day period.
    H12,
    /// 0–23.
    H23,
    /// 1–24.
    H24,
}

/// Per-component options for [`format_options`] / [`format_to_parts`], modeled on
/// `Intl.DateTimeFormat`. [`Default`] is all-`None` (which formats a numeric
/// year/month/day). `date_style`/`time_style` are a shortcut that is mutually
/// exclusive with the component fields.
///
/// The struct is `#[non_exhaustive]` (so new options can be added without a
/// breaking change): construct it from [`Default`] and set the fields you need,
/// e.g. `let mut o = DateTimeFormatOptions::default(); o.year = …;`.
#[derive(Debug, Clone, Copy, PartialEq, Eq, Default)]
#[non_exhaustive]
pub struct DateTimeFormatOptions {
    /// Weekday name width.
    pub weekday: Option<NameStyle>,
    /// Era name width.
    pub era: Option<NameStyle>,
    /// Year width.
    pub year: Option<Numeric2Digit>,
    /// Month presentation.
    pub month: Option<MonthStyle>,
    /// Day width.
    pub day: Option<Numeric2Digit>,
    /// Hour width.
    pub hour: Option<Numeric2Digit>,
    /// Minute width.
    pub minute: Option<Numeric2Digit>,
    /// Second width.
    pub second: Option<Numeric2Digit>,
    /// Fractional-second digits (1–3).
    pub fractional_second_digits: Option<u8>,
    /// Day-period width (only affects 12-hour formatting).
    pub day_period: Option<NameStyle>,
    /// Time-zone-name presentation (requires `time_zone` or `tz_offset_minutes`).
    pub time_zone_name: Option<TimeZoneNameStyle>,
    /// IANA zone id (e.g. `"America/New_York"`) for `time_zone_name`. With the
    /// `iana-tz` feature this yields a DST-aware abbreviation for the `Short`
    /// style and the zone's offset otherwise; without it, or for an unknown
    /// zone, the offset path (`tz_offset_minutes`) is used.
    pub time_zone: Option<&'static str>,
    /// Hour cycle (overrides `hour12`).
    pub hour_cycle: Option<HourCycle>,
    /// 12-hour clock toggle.
    pub hour12: Option<bool>,
    /// Date-style shortcut (mutually exclusive with components).
    pub date_style: Option<DateStyle>,
    /// Time-style shortcut (mutually exclusive with components).
    pub time_style: Option<DateStyle>,
    /// Caller-supplied UTC offset in minutes, used for `time_zone_name`.
    pub tz_offset_minutes: Option<i32>,
}

/// Error returned by [`format_options`] / [`format_to_parts`].
#[derive(Debug, Clone, Copy, PartialEq, Eq)]
#[non_exhaustive]
pub enum DateTimeFormatError {
    /// `date_style`/`time_style` were combined with component options.
    ConflictingOptions,
}

fn normalize_lang(lang: &str) -> String {
    lang.chars()
        .map(|c| {
            if c == '_' {
                '-'
            } else {
                c.to_ascii_lowercase()
            }
        })
        .collect()
}

/// The locale's default clock letter (`h` = 12-hour, `H` = 24-hour), read from
/// its CLDR time patterns: the first hour field letter found outside quotes.
/// `K`/`k` collapse to `h`/`H`. Defaults to `H` if none is found.
fn locale_hour_letter(s: &CalendarSpec) -> char {
    for pat in s.time {
        let chars: Vec<char> = pat.chars().collect();
        let mut i = 0;
        while i < chars.len() {
            match chars[i] {
                '\'' => {
                    i += 1;
                    while i < chars.len() && chars[i] != '\'' {
                        i += 1;
                    }
                    i += 1;
                }
                'h' | 'K' => return 'h',
                'H' | 'k' => return 'H',
                _ => i += 1,
            }
        }
    }
    'H'
}

/// The 12- vs 24-hour clock **family** letter (`h` or `H`) implied by the cycle
/// / `hour12` options, falling back to the locale default (`loc`). Used for
/// skeleton lookup (availableFormats keys only use `h`/`H`) and the day-period
/// decision.
fn hour_letter(o: &DateTimeFormatOptions, loc: char) -> char {
    match (o.hour_cycle, o.hour12) {
        (Some(HourCycle::H11 | HourCycle::H12), _) => 'h',
        (Some(HourCycle::H23 | HourCycle::H24), _) => 'H',
        (None, Some(true)) => 'h',
        (None, Some(false)) => 'H',
        (None, None) => loc,
    }
}

/// The exact CLDR hour field letter for the requested cycle: `h` = h12 (1–12),
/// `K` = h11 (0–11), `H` = h23 (0–23), `k` = h24 (1–24). With no explicit cycle,
/// uses the locale default family (`loc`, always `h`/`H`).
fn hour_exact_letter(o: &DateTimeFormatOptions, loc: char) -> char {
    match (o.hour_cycle, o.hour12) {
        (Some(HourCycle::H11), _) => 'K',
        (Some(HourCycle::H12), _) => 'h',
        (Some(HourCycle::H23), _) => 'H',
        (Some(HourCycle::H24), _) => 'k',
        (None, Some(true)) => 'h',
        (None, Some(false)) => 'H',
        (None, None) => loc,
    }
}

/// Build the canonical date-field skeleton (`G y M… E d`) and whether any date
/// component was requested.
fn build_date_skeleton(o: &DateTimeFormatOptions) -> (String, bool) {
    let mut sk = String::new();
    if o.era.is_some() {
        sk.push('G');
    }
    if o.year.is_some() {
        sk.push('y');
    }
    if let Some(m) = o.month {
        // Use a representative width for *lookup* only — numeric (`M`) vs name
        // (`MMM`); the requested width is applied later by `patch_widths`. CLDR
        // availableFormats key combos use `M` or `MMM`, so collapsing the name
        // widths to `MMM` maximizes exact-match hits (e.g. a wide-month +
        // weekday request matches `MMMEd` instead of falling back and losing the
        // weekday).
        let c = match m {
            MonthStyle::Numeric | MonthStyle::TwoDigit => 1,
            MonthStyle::Short | MonthStyle::Long | MonthStyle::Narrow => 3,
        };
        for _ in 0..c {
            sk.push('M');
        }
    }
    if o.weekday.is_some() {
        sk.push('E');
    }
    if o.day.is_some() {
        sk.push('d');
    }
    let any = o.era.is_some()
        || o.year.is_some()
        || o.month.is_some()
        || o.weekday.is_some()
        || o.day.is_some();
    (sk, any)
}

/// Build the canonical time-field skeleton (`h/H m s`) and whether any time
/// component was requested. `loc` is the locale default hour letter.
fn build_time_skeleton(o: &DateTimeFormatOptions, loc: char) -> (String, bool) {
    let mut sk = String::new();
    if o.hour.is_some() {
        sk.push(hour_letter(o, loc));
    }
    if o.minute.is_some() {
        sk.push('m');
    }
    if o.second.is_some() {
        sk.push('s');
    }
    let any = o.hour.is_some() || o.minute.is_some() || o.second.is_some();
    (sk, any)
}

/// Resolve a skeleton to a locale pattern through the fallback chain.
fn resolve_one(lang: &str, s: &CalendarSpec, skeleton: &str) -> String {
    let norm = normalize_lang(lang);
    let mut end = norm.len();
    loop {
        if let Some(p) = crate::cldr::skeleton_pattern(&norm[..end], skeleton) {
            return String::from(p);
        }
        match norm[..end].rfind('-') {
            Some(i) => end = i,
            None => {
                return crate::cldr::skeleton_pattern("en", skeleton)
                    .map_or_else(|| String::from(s.date[2]), String::from);
            }
        }
    }
}

/// Replace each run of a field letter (in `from`) with `to` repeated `count`,
/// skipping quoted literals.
fn set_field(pattern: &str, from: &[char], to: char, count: usize) -> String {
    let chars: Vec<char> = pattern.chars().collect();
    let mut out = String::new();
    let mut i = 0;
    while i < chars.len() {
        let ch = chars[i];
        if ch == '\'' {
            out.push(ch);
            i += 1;
            if i < chars.len() && chars[i] == '\'' {
                out.push('\'');
                i += 1;
                continue;
            }
            while i < chars.len() && chars[i] != '\'' {
                out.push(chars[i]);
                i += 1;
            }
            if i < chars.len() {
                out.push('\'');
                i += 1;
            }
        } else if from.contains(&ch) {
            while i < chars.len() && chars[i] == ch {
                i += 1;
            }
            for _ in 0..count {
                out.push(to);
            }
        } else {
            out.push(ch);
            i += 1;
        }
    }
    out
}

/// Apply the requested component widths to a resolved pattern.
fn patch_widths(pattern: &str, o: &DateTimeFormatOptions, loc: char) -> String {
    let mut p = String::from(pattern);
    if let Some(y) = o.year {
        p = set_field(
            &p,
            &['y'],
            'y',
            if y == Numeric2Digit::TwoDigit { 2 } else { 1 },
        );
    }
    if let Some(m) = o.month {
        let c = match m {
            MonthStyle::Numeric => 1,
            MonthStyle::TwoDigit => 2,
            MonthStyle::Short => 3,
            MonthStyle::Long => 4,
            MonthStyle::Narrow => 5,
        };
        p = set_field(&p, &['M', 'L'], 'M', c);
    }
    if let Some(d) = o.day {
        p = set_field(
            &p,
            &['d'],
            'd',
            if d == Numeric2Digit::TwoDigit { 2 } else { 1 },
        );
    }
    if let Some(w) = o.weekday {
        let c = match w {
            NameStyle::Long => 4,
            NameStyle::Short => 3,
            NameStyle::Narrow => 5,
        };
        p = set_field(&p, &['E', 'e', 'c'], 'E', c);
    }
    if let Some(e) = o.era {
        let c = match e {
            NameStyle::Long => 4,
            NameStyle::Short => 1,
            NameStyle::Narrow => 5,
        };
        p = set_field(&p, &['G'], 'G', c);
    }
    if let Some(h) = o.hour {
        let letter = hour_exact_letter(o, loc);
        let c = if h == Numeric2Digit::TwoDigit { 2 } else { 1 };
        p = set_field(&p, &['h', 'H', 'k', 'K'], letter, c);
    }
    if let Some(mi) = o.minute {
        p = set_field(
            &p,
            &['m'],
            'm',
            if mi == Numeric2Digit::TwoDigit { 2 } else { 1 },
        );
    }
    if let Some(se) = o.second {
        p = set_field(
            &p,
            &['s'],
            's',
            if se == Numeric2Digit::TwoDigit { 2 } else { 1 },
        );
    }
    if let Some(dp) = o.day_period {
        // Promote the pattern's am/pm field to the flexible day period `B` at the
        // requested width (only effective when the pattern carries an a/b/B field).
        let c = match dp {
            NameStyle::Long => 4,
            NameStyle::Short => 1,
            NameStyle::Narrow => 5,
        };
        p = set_field(&p, &['a', 'b', 'B'], 'B', c);
    }
    p
}

/// Inject a locale decimal separator + `n` `S` digits right after the seconds
/// run (skeletons carry no `S`), for `fractionalSecondDigits`.
fn inject_fractional(pattern: &str, lang: &str, n: u8) -> String {
    let dec = crate::cldr::number_spec(lang).map_or(".", |s| s.decimal);
    let chars: Vec<char> = pattern.chars().collect();
    let mut out = String::new();
    let mut i = 0;
    let mut done = false;
    while i < chars.len() {
        let ch = chars[i];
        if ch == '\'' {
            out.push(ch);
            i += 1;
            while i < chars.len() && chars[i] != '\'' {
                out.push(chars[i]);
                i += 1;
            }
            if i < chars.len() {
                out.push('\'');
                i += 1;
            }
        } else if ch == 's' && !done {
            while i < chars.len() && chars[i] == 's' {
                out.push('s');
                i += 1;
            }
            out.push_str(dec);
            for _ in 0..n {
                out.push('S');
            }
            done = true;
        } else {
            out.push(ch);
            i += 1;
        }
    }
    out
}

/// Remove field runs whose letter is not in `keep`, then tidy separators: drop
/// leading/trailing literal tokens and merge adjacent literals. Quoted literals
/// are unwrapped into plain text. Keeps the common CLDR patterns clean when a
/// best-fit skeleton carried extra fields.
fn strip_fields(pattern: &str, keep: &[char]) -> String {
    enum Tok {
        Field(String),
        Lit(String),
    }
    let chars: Vec<char> = pattern.chars().collect();
    let mut toks: Vec<Tok> = Vec::new();
    let mut i = 0;
    let mut lit = String::new();
    let flush = |lit: &mut String, toks: &mut Vec<Tok>| {
        if !lit.is_empty() {
            toks.push(Tok::Lit(core::mem::take(lit)));
        }
    };
    while i < chars.len() {
        let ch = chars[i];
        if ch == '\'' {
            i += 1;
            if i < chars.len() && chars[i] == '\'' {
                lit.push('\'');
                i += 1;
                continue;
            }
            while i < chars.len() && chars[i] != '\'' {
                lit.push(chars[i]);
                i += 1;
            }
            i += 1;
        } else if ch.is_ascii_alphabetic() {
            flush(&mut lit, &mut toks);
            let start = i;
            while i < chars.len() && chars[i] == ch {
                i += 1;
            }
            let run: String = chars[start..i].iter().collect();
            if keep.contains(&ch) {
                toks.push(Tok::Field(run));
            }
            // else: dropped
        } else {
            lit.push(ch);
            i += 1;
        }
    }
    flush(&mut lit, &mut toks);

    // Drop leading/trailing literals.
    while matches!(toks.first(), Some(Tok::Lit(_))) {
        toks.remove(0);
    }
    while matches!(toks.last(), Some(Tok::Lit(_))) {
        toks.pop();
    }
    // Merge adjacent literals and reassemble.
    let mut out = String::new();
    let mut prev_lit = false;
    for t in toks {
        match t {
            Tok::Field(f) => {
                out.push_str(&f);
                prev_lit = false;
            }
            Tok::Lit(l) => {
                if prev_lit {
                    // collapse a doubled separator left by a removed middle field
                    continue;
                }
                out.push_str(&l);
                prev_lit = true;
            }
        }
    }
    out
}

/// Resolve a full pattern string for the requested options.
fn resolve_pattern(
    lang: &str,
    s: &CalendarSpec,
    o: &DateTimeFormatOptions,
) -> Result<String, DateTimeFormatError> {
    let has_components = o.weekday.is_some()
        || o.era.is_some()
        || o.year.is_some()
        || o.month.is_some()
        || o.day.is_some()
        || o.hour.is_some()
        || o.minute.is_some()
        || o.second.is_some()
        || o.fractional_second_digits.is_some()
        || o.day_period.is_some();

    if o.date_style.is_some() || o.time_style.is_some() {
        if has_components {
            return Err(DateTimeFormatError::ConflictingOptions);
        }
        let pat = match (o.date_style, o.time_style) {
            (Some(d), Some(t)) => s.datetime[d.idx()]
                .replace("{1}", s.date[d.idx()])
                .replace("{0}", s.time[t.idx()]),
            (Some(d), None) => String::from(s.date[d.idx()]),
            (None, Some(t)) => String::from(s.time[t.idx()]),
            (None, None) => unreachable!(),
        };
        return Ok(pat);
    }

    let loc_hour = locale_hour_letter(s);
    let (date_sk, mut want_date) = build_date_skeleton(o);
    let (time_sk, want_time) = build_time_skeleton(o, loc_hour);
    // ECMA-402 default when nothing is requested: numeric year/month/day.
    let date_sk = if !want_date && !want_time {
        want_date = true;
        String::from("yMd")
    } else {
        date_sk
    };

    let date_pat = if want_date {
        Some(resolve_one(lang, s, &date_sk))
    } else {
        None
    };
    let time_pat = if want_time {
        Some(resolve_one(lang, s, &time_sk))
    } else {
        None
    };

    let mut combined = match (date_pat, time_pat) {
        (Some(d), Some(t)) => s.datetime[2].replace("{1}", &d).replace("{0}", &t),
        (Some(d), None) => d,
        (None, Some(t)) => t,
        (None, None) => String::from(s.date[2]),
    };

    // When explicit components were given, drop any extra fields a best-fit
    // pattern carried (the defaulted "yMd" path resolves exactly, so skip it).
    if has_components {
        let mut keep: Vec<char> = Vec::new();
        if o.year.is_some() {
            keep.extend(['y', 'Y', 'u', 'U', 'r']);
        }
        if o.month.is_some() {
            keep.extend(['M', 'L']);
        }
        if o.day.is_some() {
            keep.extend(['d', 'D', 'F', 'g']);
        }
        if o.weekday.is_some() {
            keep.extend(['E', 'e', 'c']);
        }
        if o.era.is_some() {
            keep.push('G');
        }
        if o.hour.is_some() {
            keep.extend(['h', 'H', 'k', 'K']);
        }
        if o.minute.is_some() {
            keep.push('m');
        }
        if o.second.is_some() {
            keep.push('s');
        }
        // Keep the day period when explicitly asked or implied by a 12-hour clock.
        if o.day_period.is_some() || (o.hour.is_some() && hour_letter(o, loc_hour) == 'h') {
            keep.extend(['a', 'b', 'B']);
        }
        combined = strip_fields(&combined, &keep);
    }

    combined = patch_widths(&combined, o, loc_hour);
    if let Some(n) = o.fractional_second_digits {
        combined = inject_fractional(&combined, lang, n);
    }
    Ok(combined)
}

/// The time-zone-name string for an offset and presentation style.
fn zone_string(lang: &str, style: TimeZoneNameStyle, offset: i32) -> String {
    // Long offset = zero-padded GMT form; short offset trims leading zero in the
    // hour. Named/generic styles fall back to the offset (no metazone data).
    let long = format_gmt_offset(lang, offset);
    match style {
        TimeZoneNameStyle::LongOffset
        | TimeZoneNameStyle::Long
        | TimeZoneNameStyle::LongGeneric => long,
        TimeZoneNameStyle::ShortOffset
        | TimeZoneNameStyle::Short
        | TimeZoneNameStyle::ShortGeneric => {
            // "GMT-08:00" -> "GMT-8:00": drop a single leading zero after the sign.
            if let Some(pos) = long.find(['+', '-', '\u{2212}']) {
                let (head, tail) = long.split_at(pos + 1);
                let trimmed = tail.strip_prefix('0').unwrap_or(tail);
                alloc::format!("{head}{trimmed}")
            } else {
                long
            }
        }
    }
}

/// Resolve the `time_zone_name` text for `dt`. With the `iana-tz` feature and a
/// `time_zone` set, the `Short` style yields the DST-aware zone abbreviation
/// (e.g. `EST`/`EDT`) and other styles use the zone's offset; otherwise the
/// caller-supplied `tz_offset_minutes` drives the localized GMT offset.
#[cfg_attr(not(feature = "iana-tz"), allow(unused_variables))]
fn compute_tz_name(
    lang: &str,
    dt: &DateTime,
    opts: &DateTimeFormatOptions,
    style: TimeZoneNameStyle,
) -> Option<String> {
    #[cfg(feature = "iana-tz")]
    if let Some(zid) = opts.time_zone
        && let Some(zone) = crate::timezone::load_zone(zid)
    {
        let off_min = zone.offset_for_local(dt) / 60;
        return Some(match style {
            // The tz database carries the specific (DST-aware) abbreviation.
            TimeZoneNameStyle::Short => String::from(zone.abbrev_for_local(dt)),
            // No long/generic names in the tz db — fall back to the offset form.
            _ => zone_string(lang, style, off_min),
        });
    }
    opts.tz_offset_minutes
        .map(|off| zone_string(lang, style, off))
}

/// Format `dt` in `lang` with ECMA-402-style component options, returning the
/// tagged parts (`Intl.DateTimeFormat.prototype.formatToParts`).
///
/// ```
/// use intl::datetime::{DateTime, DateTimeFormatOptions, MonthStyle, Numeric2Digit, format_to_parts};
/// let dt = DateTime { year: 2026, month: 6, day: 4, hour: 14, minute: 30, second: 5, millisecond: 0 };
/// let mut opts = DateTimeFormatOptions::default();
/// opts.year = Some(Numeric2Digit::Numeric);
/// opts.month = Some(MonthStyle::Short);
/// opts.day = Some(Numeric2Digit::Numeric);
/// let parts = format_to_parts("en", &dt, &opts).unwrap();
/// let joined: String = parts.iter().map(|p| p.value.as_str()).collect();
/// assert_eq!(joined, "Jun 4, 2026");
/// ```
///
/// # Errors
/// Returns [`DateTimeFormatError::ConflictingOptions`] if `date_style`/`time_style`
/// are combined with component fields.
pub fn format_to_parts(
    lang: &str,
    dt: &DateTime,
    opts: &DateTimeFormatOptions,
) -> Result<Vec<DateTimePart>, DateTimeFormatError> {
    let s = spec(lang);
    let pattern = resolve_pattern(lang, &s, opts)?;
    let mut parts = render_parts(&pattern, dt, &s);
    if let Some(style) = opts.time_zone_name
        && let Some(name) = compute_tz_name(lang, dt, opts, style)
    {
        parts.push(DateTimePart {
            kind: DateTimePartType::Literal,
            value: String::from(" "),
        });
        parts.push(DateTimePart {
            kind: DateTimePartType::TimeZoneName,
            value: name,
        });
    }
    Ok(parts)
}

/// Format `dt` in `lang` with ECMA-402-style component options.
///
/// ```
/// use intl::datetime::{DateTime, DateTimeFormatOptions, DateStyle, format_options};
/// let dt = DateTime { year: 2026, month: 6, day: 4, hour: 14, minute: 30, second: 5, millisecond: 0 };
/// let mut opts = DateTimeFormatOptions::default();
/// opts.date_style = Some(DateStyle::Long);
/// assert_eq!(format_options("en", &dt, &opts).unwrap(), "June 4, 2026");
/// ```
///
/// # Errors
/// Returns [`DateTimeFormatError::ConflictingOptions`] if `date_style`/`time_style`
/// are combined with component fields.
pub fn format_options(
    lang: &str,
    dt: &DateTime,
    opts: &DateTimeFormatOptions,
) -> Result<String, DateTimeFormatError> {
    let parts = format_to_parts(lang, dt, opts)?;
    let mut out = String::new();
    for p in parts {
        out.push_str(&p.value);
    }
    Ok(out)
}

/// Format `dt` with a CLDR skeleton, returning tagged parts (see
/// [`format_skeleton`] and [`format_to_parts`]).
#[must_use]
pub fn format_skeleton_to_parts(lang: &str, dt: &DateTime, skeleton: &str) -> Vec<DateTimePart> {
    let s = spec(lang);
    let norm = normalize_lang(lang);
    let mut end = norm.len();
    let pattern = loop {
        if let Some(p) = crate::cldr::skeleton_pattern(&norm[..end], skeleton) {
            break String::from(p);
        }
        match norm[..end].rfind('-') {
            Some(i) => end = i,
            None => {
                break crate::cldr::skeleton_pattern("en", skeleton)
                    .map_or_else(|| String::from(s.date[2]), String::from);
            }
        }
    };
    render_parts(&pattern, dt, &s)
}

// ---------------------------------------------------------------------------
// Interval formatting (formatRange / formatRangeToParts, UTS #35 §2.6.2)
// ---------------------------------------------------------------------------

/// Which of the two dates a [`DateTimeRangePart`] originates from, matching the
/// `source` values of `Intl.DateTimeFormat.prototype.formatRangeToParts`.
#[derive(Debug, Clone, Copy, PartialEq, Eq)]
pub enum RangeSource {
    /// The part belongs to the start (earlier) date.
    StartRange,
    /// The part belongs to the end (later) date.
    EndRange,
    /// The part is common to both dates (e.g. a shared year, or a separator).
    Shared,
}

impl RangeSource {
    /// The ECMA-402 `source` string for this value.
    #[must_use]
    pub fn as_str(&self) -> &'static str {
        match self {
            RangeSource::StartRange => "startRange",
            RangeSource::EndRange => "endRange",
            RangeSource::Shared => "shared",
        }
    }
}

/// One tagged segment of a formatted date-time *range* (see
/// [`format_range_to_parts`]): a [`DateTimePart`] plus the [`RangeSource`] that
/// says which date it came from.
#[derive(Debug, Clone, PartialEq, Eq)]
pub struct DateTimeRangePart {
    /// What this segment represents.
    pub kind: DateTimePartType,
    /// The literal text of this segment.
    pub value: String,
    /// Which date this segment originates from.
    pub source: RangeSource,
}

/// The distinct non-literal field categories a pattern uses, in first-seen order.
fn field_categories(pattern: &str) -> Vec<DateTimePartType> {
    let chars: Vec<char> = pattern.chars().collect();
    let mut cats: Vec<DateTimePartType> = Vec::new();
    let mut i = 0;
    while i < chars.len() {
        let ch = chars[i];
        if ch == '\'' {
            i += 1;
            if i < chars.len() && chars[i] == '\'' {
                i += 1;
                continue;
            }
            while i < chars.len() && chars[i] != '\'' {
                i += 1;
            }
            i += 1;
        } else if ch.is_ascii_alphabetic() {
            while i < chars.len() && chars[i] == ch {
                i += 1;
            }
            let cat = part_type(ch);
            if cat != DateTimePartType::Literal && !cats.contains(&cat) {
                cats.push(cat);
            }
        } else {
            i += 1;
        }
    }
    cats
}

/// Split a CLDR interval pattern (which mentions each date's fields once) into
/// the two halves at the first field whose category repeats (UTS #35). The split
/// point always falls on a field-run boundary, so quoted literals stay intact.
/// Returns `None` if no field category repeats.
fn split_interval(pattern: &str) -> Option<(String, String)> {
    let chars: Vec<char> = pattern.chars().collect();
    let mut seen: Vec<DateTimePartType> = Vec::new();
    let mut i = 0;
    while i < chars.len() {
        let ch = chars[i];
        if ch == '\'' {
            i += 1;
            if i < chars.len() && chars[i] == '\'' {
                i += 1;
                continue;
            }
            while i < chars.len() && chars[i] != '\'' {
                i += 1;
            }
            i += 1;
        } else if ch.is_ascii_alphabetic() {
            let start = i;
            while i < chars.len() && chars[i] == ch {
                i += 1;
            }
            let cat = part_type(ch);
            if cat != DateTimePartType::Literal {
                if seen.contains(&cat) {
                    let first: String = chars[..start].iter().collect();
                    let second: String = chars[start..].iter().collect();
                    return Some((first, second));
                }
                seen.push(cat);
            }
        } else {
            i += 1;
        }
    }
    None
}

/// The combined CLDR skeleton implied by `opts` (the same field letters used to
/// key `intervalFormats`), or `"yMd"` when no component is requested.
fn interval_skeleton(opts: &DateTimeFormatOptions, loc_hour: char) -> String {
    let (date_sk, want_date) = build_date_skeleton(opts);
    let (time_sk, want_time) = build_time_skeleton(opts, loc_hour);
    if !want_date && !want_time {
        String::from("yMd")
    } else {
        let mut sk = date_sk;
        sk.push_str(&time_sk);
        sk
    }
}

/// The CLDR field letter of the greatest calendar field in which `a` and `b`
/// differ, restricted to fields the `skeleton` actually uses. `None` if they
/// agree on every field the skeleton mentions (→ format as a single value).
fn greatest_diff_field(a: &DateTime, b: &DateTime, skeleton: &str) -> Option<u8> {
    let era = |d: &DateTime| d.year > 0;
    if skeleton.contains('G') && era(a) != era(b) {
        return Some(b'G');
    }
    if skeleton.contains('y') && a.year != b.year {
        return Some(b'y');
    }
    if skeleton.contains('M') && a.month != b.month {
        return Some(b'M');
    }
    if skeleton.contains('d') && a.day != b.day {
        return Some(b'd');
    }
    let h12 = skeleton.contains('h');
    let h24 = skeleton.contains('H');
    if h12 && (a.hour < 12) != (b.hour < 12) {
        return Some(b'a');
    }
    if (h12 || h24) && a.hour != b.hour {
        return Some(if h12 { b'h' } else { b'H' });
    }
    if skeleton.contains('m') && a.minute != b.minute {
        return Some(b'm');
    }
    None
}

/// Resolve a per-skeleton interval pattern through the locale fallback chain.
fn resolve_interval_pattern(lang: &str, skeleton: &str, field: u8) -> Option<String> {
    let norm = normalize_lang(lang);
    let mut end = norm.len();
    loop {
        if let Some(p) = crate::cldr::interval_pattern(&norm[..end], skeleton, field) {
            return Some(String::from(p));
        }
        match norm[..end].rfind('-') {
            Some(i) => end = i,
            None => return crate::cldr::interval_pattern("en", skeleton, field).map(String::from),
        }
    }
}

/// Resolve the `intervalFormatFallback` string through the locale fallback chain.
fn resolve_interval_fallback(lang: &str) -> String {
    let norm = normalize_lang(lang);
    let mut end = norm.len();
    loop {
        if let Some(p) = crate::cldr::interval_fallback(&norm[..end]) {
            return String::from(p);
        }
        match norm[..end].rfind('-') {
            Some(i) => end = i,
            None => {
                return crate::cldr::interval_fallback("en").map_or_else(
                    || String::from("{0}\u{2009}\u{2013}\u{2009}{1}"),
                    String::from,
                );
            }
        }
    }
}

/// Give each literal part the common source of its nearest non-literal neighbors
/// (or `Shared` when they disagree or are absent), matching ECMA-402's tagging.
fn fix_literal_sources(parts: &mut [DateTimeRangePart]) {
    let n = parts.len();
    for i in 0..n {
        if parts[i].kind != DateTimePartType::Literal {
            continue;
        }
        let prev = (0..i)
            .rev()
            .find(|&j| parts[j].kind != DateTimePartType::Literal)
            .map(|j| parts[j].source);
        let next = (i + 1..n)
            .find(|&j| parts[j].kind != DateTimePartType::Literal)
            .map(|j| parts[j].source);
        parts[i].source = match (prev, next) {
            (Some(x), Some(y)) if x == y => x,
            _ => RangeSource::Shared,
        };
    }
}

/// Render the two halves of a split interval pattern with per-part sources: a
/// field that appears in *both* halves is start/end; one that appears in a
/// single half is shared.
fn render_split(
    first: &str,
    second: &str,
    start: &DateTime,
    end: &DateTime,
    s: &CalendarSpec,
) -> Vec<DateTimeRangePart> {
    let cats_first = field_categories(first);
    let cats_second = field_categories(second);
    let mut out: Vec<DateTimeRangePart> = Vec::new();
    for p in render_parts(first, start, s) {
        let source = if p.kind != DateTimePartType::Literal && cats_second.contains(&p.kind) {
            RangeSource::StartRange
        } else {
            RangeSource::Shared
        };
        out.push(DateTimeRangePart {
            kind: p.kind,
            value: p.value,
            source,
        });
    }
    for p in render_parts(second, end, s) {
        let source = if p.kind != DateTimePartType::Literal && cats_first.contains(&p.kind) {
            RangeSource::EndRange
        } else {
            RangeSource::Shared
        };
        out.push(DateTimeRangePart {
            kind: p.kind,
            value: p.value,
            source,
        });
    }
    fix_literal_sources(&mut out);
    out
}

/// Format `start`/`end` independently with `pattern` and glue them with the
/// locale's `intervalFormatFallback` (`{0} … {1}`).
fn render_fallback(
    fallback: &str,
    pattern: &str,
    start: &DateTime,
    end: &DateTime,
    s: &CalendarSpec,
) -> Vec<DateTimeRangePart> {
    let mut out: Vec<DateTimeRangePart> = Vec::new();
    let push_lit = |out: &mut Vec<DateTimeRangePart>, text: &str| {
        if !text.is_empty() {
            out.push(DateTimeRangePart {
                kind: DateTimePartType::Literal,
                value: String::from(text),
                source: RangeSource::Shared,
            });
        }
    };
    let push_side = |out: &mut Vec<DateTimeRangePart>, dt: &DateTime, source: RangeSource| {
        for p in render_parts(pattern, dt, s) {
            let source = if p.kind == DateTimePartType::Literal {
                RangeSource::Shared
            } else {
                source
            };
            out.push(DateTimeRangePart {
                kind: p.kind,
                value: p.value,
                source,
            });
        }
    };
    match (fallback.find("{0}"), fallback.find("{1}")) {
        (Some(a), Some(b)) if a < b => {
            push_lit(&mut out, &fallback[..a]);
            push_side(&mut out, start, RangeSource::StartRange);
            push_lit(&mut out, &fallback[a + 3..b]);
            push_side(&mut out, end, RangeSource::EndRange);
            push_lit(&mut out, &fallback[b + 3..]);
        }
        _ => {
            push_side(&mut out, start, RangeSource::StartRange);
            push_lit(&mut out, "\u{2009}\u{2013}\u{2009}");
            push_side(&mut out, end, RangeSource::EndRange);
        }
    }
    out
}

/// Render a single date (both endpoints equal, or differing only in fields the
/// pattern omits): every part is [`RangeSource::Shared`].
fn single_range(pattern: &str, dt: &DateTime, s: &CalendarSpec) -> Vec<DateTimeRangePart> {
    render_parts(pattern, dt, s)
        .into_iter()
        .map(|p| DateTimeRangePart {
            kind: p.kind,
            value: p.value,
            source: RangeSource::Shared,
        })
        .collect()
}

/// Format the date-time interval `start`–`end` in `lang` with ECMA-402-style
/// component options, returning the tagged parts
/// (`Intl.DateTimeFormat.prototype.formatRangeToParts`).
///
/// When `start` and `end` are equal (or differ only in fields the resolved
/// pattern omits) the result is the single-date formatting with every part
/// tagged [`RangeSource::Shared`]. Otherwise the locale's CLDR interval pattern
/// for the greatest differing field is used, falling back to
/// `intervalFormatFallback` (`{0} – {1}`) when the skeleton has no such pattern.
///
/// # Errors
/// Returns [`DateTimeFormatError::ConflictingOptions`] if `date_style`/`time_style`
/// are combined with component fields.
pub fn format_range_to_parts(
    lang: &str,
    start: &DateTime,
    end: &DateTime,
    opts: &DateTimeFormatOptions,
) -> Result<Vec<DateTimeRangePart>, DateTimeFormatError> {
    let s = spec(lang);
    let base = resolve_pattern(lang, &s, opts)?;
    let loc_hour = locale_hour_letter(&s);
    let skeleton = interval_skeleton(opts, loc_hour);

    let Some(field) = greatest_diff_field(start, end, &skeleton) else {
        return Ok(single_range(&base, start, &s));
    };

    if let Some(ip) = resolve_interval_pattern(lang, &skeleton, field) {
        // The interval pattern is already keyed by the skeleton (which encodes the
        // requested field widths), so it is used as-is — re-patching widths would
        // corrupt locales whose numeric field abuts a literal (e.g. ja `M月`).
        return Ok(match split_interval(&ip) {
            Some((first, second)) => render_split(&first, &second, start, end, &s),
            None => single_range(&ip, start, &s),
        });
    }

    let fallback = resolve_interval_fallback(lang);
    Ok(render_fallback(&fallback, &base, start, end, &s))
}

/// Format the date-time interval `start`–`end` in `lang` with ECMA-402-style
/// component options (`Intl.DateTimeFormat.prototype.formatRange`).
///
/// ```
/// use intl::datetime::{DateTime, DateTimeFormatOptions, MonthStyle, Numeric2Digit, format_range};
/// let mut o = DateTimeFormatOptions::default();
/// o.year = Some(Numeric2Digit::Numeric);
/// o.month = Some(MonthStyle::Short);
/// o.day = Some(Numeric2Digit::Numeric);
/// let a = DateTime { year: 2024, month: 1, day: 1, ..DateTime::default() };
/// let b = DateTime { year: 2024, month: 1, day: 5, ..DateTime::default() };
/// assert_eq!(format_range("en", &a, &b, &o).unwrap(), "Jan 1\u{2009}\u{2013}\u{2009}5, 2024");
/// ```
///
/// # Errors
/// Returns [`DateTimeFormatError::ConflictingOptions`] if `date_style`/`time_style`
/// are combined with component fields.
pub fn format_range(
    lang: &str,
    start: &DateTime,
    end: &DateTime,
    opts: &DateTimeFormatOptions,
) -> Result<String, DateTimeFormatError> {
    let parts = format_range_to_parts(lang, start, end, opts)?;
    Ok(parts.iter().map(|p| p.value.as_str()).collect())
}