jiff-core 0.1.0

use alloc::{string::String, vec, vec::Vec};

use crate::{
    tz::{posix, Abbreviation, Dst, Offset},
    util::{crc32, MaybeStaticSlice},
};

use super::{
    DateTime, Indicator, LocalTimeType, TimeZone, Timestamp, TransitionInfo,
    TransitionKind, Transitions,
};

// The TZif parser clamps timestamps to this range. It is not ideal, but Jiff
// can't handle values outside of this range, and completely refusing to use
// TZif data with pathological timestamps in typically irrelevant transitions
// is undesirable.
const TIMESTAMP_MIN: i64 = Timestamp::MIN.as_second();
const TIMESTAMP_MAX: i64 = Timestamp::MAX.as_second();

// Unlike timestamps, offsets outside Jiff's range are rejected. They could
// result in incorrect datetimes for actual transitions.
const OFFSET_MIN: i32 = Offset::MIN.seconds();
const OFFSET_MAX: i32 = Offset::MAX.seconds();

// When fattening TZif data, this is the year to go up to. This year was
// chosen because it is what the "fat" TZif data generated by zic uses.
const FATTEN_UP_TO_YEAR: i16 = 2038;

// A defense-in-depth limit on additional transitions generated from a POSIX
// time zone. Normal cases should have at most two transitions per year.
const FATTEN_MAX_TRANSITIONS: usize = 300;

impl TimeZone {
    /// Parses the given data as a TZif formatted file.
    ///
    /// The name given is attached to the returned value, but is otherwise not
    /// significant.
    ///
    /// In general, callers may assume that it is safe to pass arbitrary or
    /// even untrusted data to this function and count on it not panicking or
    /// using resources that are not limited to a small constant factor of the
    /// size of the data itself.
    ///
    /// This is only available when the `alloc` feature is enabled because
    /// parsing TZif data requires heap allocation.
    pub fn parse(bytes: &[u8]) -> Result<TimeZone, ParseError> {
        ParsedTimeZone::parse(bytes)
    }
}

// We mirror the `TimeZone` type here because a `TimeZone` wants a fixed and
// immutable set of transitions. This is difficult to make it work with parsing
// that wants variable length *and* mutable. We could accommodate the fixed
// length requirement with some care, but requiring mutability makes using
// a `MaybeStaticSlice` very awkward.

struct ParsedTimeZone {
    fixed: ParsedFixed,
    types: Vec<LocalTimeType>,
    transitions: ParsedTransitions,
}

struct ParsedFixed {
    version: u8,
    checksum: u32,
    designations: Vec<Abbreviation>,
    posix_tz: Option<posix::TimeZone>,
}

struct ParsedTransitions {
    timestamps: Vec<Timestamp>,
    civil_starts: Vec<DateTime>,
    civil_ends: Vec<DateTime>,
    infos: Vec<TransitionInfo>,
}

impl ParsedTimeZone {
    fn parse(bytes: &[u8]) -> Result<TimeZone, ParseError> {
        let original = bytes;
        let (header32, rest) =
            Header::parse(4, bytes).map_err(ParseErrorKind::Header32)?;
        let (mut tzif, rest) = if header32.version == 0 {
            ParsedTimeZone::parse32(header32, rest)?
        } else {
            ParsedTimeZone::parse64(header32, rest)?
        };
        tzif.fatten();
        // This should come after fattening because fattening may add new
        // transitions and we want to add civil datetimes to those too.
        tzif.add_civil_datetimes_to_transitions();
        tzif.verify_posix_time_zone_consistency()?;

        // Compute the checksum using the portion of the TZif bytes actually
        // consumed. TZif data may contain superfluous bytes after the parsed
        // block.
        let tzif_raw_len = original.len() - rest.len();
        tzif.fixed.checksum = crc32::sum(&original[..tzif_raw_len]);

        tzif.finish()
    }

    fn new(version: u8) -> ParsedTimeZone {
        ParsedTimeZone {
            fixed: ParsedFixed {
                version,
                checksum: 0,
                designations: vec![],
                posix_tz: None,
            },
            types: vec![],
            transitions: ParsedTransitions {
                timestamps: vec![],
                civil_starts: vec![],
                civil_ends: vec![],
                infos: vec![],
            },
        }
    }

    fn finish(self) -> Result<TimeZone, ParseError> {
        Ok(TimeZone {
            version: self.fixed.version,
            checksum: self.fixed.checksum,
            designations: MaybeStaticSlice::heap(
                self.fixed.designations.into_boxed_slice(),
            ),
            posix_tz: self.fixed.posix_tz,
            types: MaybeStaticSlice::heap(self.types.into_boxed_slice()),
            transitions: Transitions {
                timestamps: MaybeStaticSlice::heap(
                    self.transitions.timestamps.into_boxed_slice(),
                ),
                civil_starts: MaybeStaticSlice::heap(
                    self.transitions.civil_starts.into_boxed_slice(),
                ),
                civil_ends: MaybeStaticSlice::heap(
                    self.transitions.civil_ends.into_boxed_slice(),
                ),
                infos: MaybeStaticSlice::heap(
                    self.transitions.infos.into_boxed_slice(),
                ),
            },
        })
    }

    fn parse32<'b>(
        header32: Header,
        bytes: &'b [u8],
    ) -> Result<(ParsedTimeZone, &'b [u8]), ParseError> {
        let mut tzif = ParsedTimeZone::new(header32.version);
        let rest = tzif.parse_transitions(&header32, bytes)?;
        let rest = tzif.parse_transition_types(&header32, rest)?;
        let rest = tzif.parse_local_time_types(&header32, rest)?;
        let rest = tzif.parse_time_zone_designations(&header32, rest)?;
        let rest = tzif.parse_leap_seconds(&header32, rest)?;
        let rest = tzif.parse_indicators(&header32, rest)?;
        Ok((tzif, rest))
    }

    fn parse64<'b>(
        header32: Header,
        bytes: &'b [u8],
    ) -> Result<(ParsedTimeZone, &'b [u8]), ParseError> {
        let (_, rest) =
            try_split_at(SplitAtError::V1, bytes, header32.data_block_len()?)?;
        let (header64, rest) =
            Header::parse(8, rest).map_err(ParseErrorKind::Header64)?;
        let mut tzif = ParsedTimeZone::new(header64.version);
        let rest = tzif.parse_transitions(&header64, rest)?;
        let rest = tzif.parse_transition_types(&header64, rest)?;
        let rest = tzif.parse_local_time_types(&header64, rest)?;
        let rest = tzif.parse_time_zone_designations(&header64, rest)?;
        let rest = tzif.parse_leap_seconds(&header64, rest)?;
        let rest = tzif.parse_indicators(&header64, rest)?;
        let rest = tzif.parse_footer(&header64, rest)?;
        // Note that we don't check that the TZif data is fully valid. It is
        // possible for it to contain superfluous information. For example, a
        // non-zero local time type that is never referenced by a transition.
        Ok((tzif, rest))
    }

    fn parse_transitions<'b>(
        &mut self,
        header: &Header,
        bytes: &'b [u8],
    ) -> Result<&'b [u8], ParseError> {
        let (bytes, rest) = try_split_at(
            SplitAtError::TransitionTimes,
            bytes,
            header.transition_times_len()?,
        )?;
        let mut it = bytes.chunks_exact(header.time_size);
        // RFC 8536 says: "If there are no transitions, local time for all
        // timestamps is specified by the TZ string in the footer if present
        // and nonempty; otherwise, it is specified by time type 0."
        //
        // RFC 8536 also says: "Local time for timestamps before the first
        // transition is specified by the first time type (time type 0)."
        //
        // So if there are no transitions, pushing this dummy one will result
        // in the desired behavior even when it's the only transition.
        // Similarly, since this is the minimum timestamp value, it will
        // trigger for any times before the first transition found in the TZif
        // data.
        self.transitions.add_with_type_index(Timestamp::MIN, 0);
        for chunk in &mut it {
            let unix_timestamp = if header.is_32bit() {
                i64::from(from_be_bytes_i32(chunk))
            } else {
                from_be_bytes_i64(chunk)
            };
            let timestamp = match Timestamp::from_second(unix_timestamp) {
                Ok(timestamp) => timestamp,
                Err(_) => {
                    // We really shouldn't error here just because the Unix
                    // timestamp is outside what Jiff supports. Since what Jiff
                    // supports is _somewhat_ arbitrary. But Jiff's supported
                    // range is good enough for all realistic purposes, so we
                    // just clamp an out-of-range Unix timestamp to the Jiff
                    // min or max value.
                    //
                    // This can't result in the sorting order being wrong, but
                    // it can result in a transition that is duplicative with
                    // the dummy transition we inserted above. This should be
                    // fine.
                    let clamped =
                        if unix_timestamp < Timestamp::MIN.as_second() {
                            Timestamp::MIN
                        } else {
                            Timestamp::MAX
                        };
                    warn!(
                        "found Unix timestamp `{unix_timestamp}` that is \
                         outside Jiff's supported range, \
                         clamping to `{clamped:?}`",
                    );
                    clamped
                }
            };
            self.transitions.add(timestamp);
        }
        assert!(it.remainder().is_empty());
        Ok(rest)
    }

    fn parse_transition_types<'b>(
        &mut self,
        header: &Header,
        bytes: &'b [u8],
    ) -> Result<&'b [u8], TransitionTypeError> {
        let (bytes, rest) = try_split_at(
            SplitAtError::TransitionTypes,
            bytes,
            header.transition_types_len(),
        )?;
        // We skip the first transition because it is our minimum dummy
        // transition.
        for (transition_index, &type_index) in (1..).zip(bytes) {
            if usize::from(type_index) >= header.tzh_typecnt {
                return Err(TransitionTypeError::ExceedsLocalTimeTypes);
            }
            self.transitions.infos[transition_index].type_index = type_index;
        }
        Ok(rest)
    }

    fn parse_local_time_types<'b>(
        &mut self,
        header: &Header,
        bytes: &'b [u8],
    ) -> Result<&'b [u8], ParseError> {
        let (bytes, rest) = try_split_at(
            SplitAtError::LocalTimeTypes,
            bytes,
            header.local_time_types_len()?,
        )?;
        let mut it = bytes.chunks_exact(6);
        for chunk in &mut it {
            let offset_seconds = from_be_bytes_i32(&chunk[..4]);
            let offset =
                Offset::from_seconds(offset_seconds).map_err(|_| {
                    LocalTimeTypeError::InvalidOffset {
                        offset: offset_seconds,
                    }
                })?;
            let dst = Dst::from(chunk[4] == 1);
            let designation = chunk[5];
            self.types.push(LocalTimeType {
                offset,
                dst,
                designation,
                indicator: Indicator::LocalWall,
            });
        }
        assert!(it.remainder().is_empty());
        Ok(rest)
    }

    fn parse_time_zone_designations<'b>(
        &mut self,
        header: &Header,
        bytes: &'b [u8],
    ) -> Result<&'b [u8], TimeZoneDesignatorError> {
        let (bytes, rest) = try_split_at(
            SplitAtError::TimeZoneDesignations,
            bytes,
            header.time_zone_designations_len(),
        )?;
        let designations = String::from_utf8(bytes.to_vec())
            .map_err(|_| TimeZoneDesignatorError::InvalidUtf8)?;
        for type_index in 0..self.types.len() {
            let start = usize::from(self.types[type_index].designation);
            let suffix = designations
                .get(start..)
                .ok_or(TimeZoneDesignatorError::InvalidStart)?;
            let len = suffix
                .find('\x00')
                .ok_or(TimeZoneDesignatorError::MissingNul)?;
            let end = start
                .checked_add(len)
                .ok_or(TimeZoneDesignatorError::InvalidLength)?;
            u8::try_from(end)
                .map_err(|_| TimeZoneDesignatorError::InvalidEnd)?;
            let abbreviation = &designations[start..end];
            // This unwrap is OK because if this fails, it implies that there
            // must be an `end` offset greater than 256. But the error check
            // above handles that case.
            let designation = self
                .find_or_create_designation(abbreviation)
                .expect("there are at most 256 local time types");
            self.types[type_index].designation = designation;
        }
        Ok(rest)
    }

    /// Parses leap second corrections in TZif data.
    ///
    /// Jiff ignores leap seconds, so this only validates that the byte ranges
    /// described by the header are well-formed.
    fn parse_leap_seconds<'b>(
        &mut self,
        header: &Header,
        bytes: &'b [u8],
    ) -> Result<&'b [u8], ParseError> {
        let (bytes, rest) = try_split_at(
            SplitAtError::LeapSeconds,
            bytes,
            header.leap_second_len()?,
        )?;
        // OK because `time_size` is always `4` or `8`.
        let chunk_len = header.time_size.wrapping_add(4);
        let mut it = bytes.chunks_exact(chunk_len);
        for chunk in &mut it {
            let (occur_bytes, _corr_bytes) = chunk.split_at(header.time_size);
            let occur = if header.is_32bit() {
                i64::from(from_be_bytes_i32(occur_bytes))
            } else {
                from_be_bytes_i64(occur_bytes)
            };
            if !(TIMESTAMP_MIN <= occur && occur <= TIMESTAMP_MAX) {
                warn!(
                    "leap second occurrence `{occur}` is \
                     not in Jiff's supported range"
                )
            }
        }
        assert!(it.remainder().is_empty());
        Ok(rest)
    }

    fn parse_indicators<'b>(
        &mut self,
        header: &Header,
        bytes: &'b [u8],
    ) -> Result<&'b [u8], IndicatorError> {
        let (std_wall_bytes, rest) = try_split_at(
            SplitAtError::StandardWallIndicators,
            bytes,
            header.standard_wall_len(),
        )?;
        let (ut_local_bytes, rest) = try_split_at(
            SplitAtError::UTLocalIndicators,
            rest,
            header.ut_local_len(),
        )?;
        if std_wall_bytes.is_empty() && !ut_local_bytes.is_empty() {
            if ut_local_bytes.iter().any(|&byte| byte != 0) {
                return Err(IndicatorError::UtLocalNonZero);
            }
        } else if !std_wall_bytes.is_empty() && ut_local_bytes.is_empty() {
            for (i, &byte) in std_wall_bytes.iter().enumerate() {
                self.types[i].indicator = if byte == 0 {
                    Indicator::LocalWall
                } else if byte == 1 {
                    Indicator::LocalStandard
                } else {
                    return Err(IndicatorError::InvalidStdWallIndicator);
                };
            }
        } else if !std_wall_bytes.is_empty() && !ut_local_bytes.is_empty() {
            assert_eq!(std_wall_bytes.len(), ut_local_bytes.len());
            let it = std_wall_bytes.iter().zip(ut_local_bytes);
            for (i, (&stdwall, &utlocal)) in it.enumerate() {
                self.types[i].indicator = match (stdwall, utlocal) {
                    (0, 0) => Indicator::LocalWall,
                    (1, 0) => Indicator::LocalStandard,
                    (1, 1) => Indicator::UTStandard,
                    (0, 1) => {
                        return Err(IndicatorError::InvalidUtWallCombination);
                    }
                    _ => return Err(IndicatorError::InvalidCombination),
                };
            }
        } else {
            debug_assert!(std_wall_bytes.is_empty());
            debug_assert!(ut_local_bytes.is_empty());
        }
        Ok(rest)
    }

    fn parse_footer<'b>(
        &mut self,
        _header: &Header,
        bytes: &'b [u8],
    ) -> Result<&'b [u8], FooterError> {
        if bytes.is_empty() {
            return Err(FooterError::UnexpectedEnd);
        }
        if bytes[0] != b'\n' {
            return Err(FooterError::MismatchEnd);
        }
        let bytes = &bytes[1..];
        // Only scan up to 1KB for a newline terminator in case we somehow got
        // passed a huge block of bytes.
        let toscan = &bytes[..bytes.len().min(1024)];
        let nlat = toscan
            .iter()
            .position(|&b| b == b'\n')
            .ok_or(FooterError::TerminatorNotFound)?;
        let (bytes, rest) = bytes.split_at(nlat);
        if !bytes.is_empty() {
            // We could in theory limit TZ strings to their strict POSIX
            // definition here for TZif V2, but I don't think there is any
            // harm in allowing the extensions in V2 formatted TZif data. Note
            // that GNU tooling allows it via the `TZ` environment variable
            // even though POSIX doesn't specify it. This all seems okay to me
            // because the V3+ extension is a strict superset of functionality.
            let posix_tz = posix::TimeZone::parse(bytes)
                .map_err(FooterError::InvalidPosixTz)?;
            self.fixed.posix_tz = Some(posix_tz);
        }
        Ok(&rest[1..])
    }

    /// Validates that the POSIX TZ string we parsed, if present, is
    /// consistent with the last transition in this time zone.
    fn verify_posix_time_zone_consistency(
        &self,
    ) -> Result<(), InconsistentPosixTimeZoneError> {
        if self.transitions.timestamps.len() <= 1 {
            return Ok(());
        }
        let Some(ref tz) = self.fixed.posix_tz else {
            return Ok(());
        };
        let last = self
            .transitions
            .timestamps
            .last()
            .expect("last transition timestamp");
        let type_index = self
            .transitions
            .infos
            .last()
            .expect("last transition info")
            .type_index;
        let typ = &self.types[usize::from(type_index)];
        let timestamp = crate::Timestamp::from_second(last.as_second())
            .expect("TZif timestamps are in range");
        let info = tz.to_offset_info(timestamp);
        if info.offset() != typ.offset {
            return Err(InconsistentPosixTimeZoneError::Offset);
        }
        if info.dst() != typ.dst {
            return Err(InconsistentPosixTimeZoneError::Dst);
        }
        if info.abbreviation().as_ref() != self.designation(typ) {
            return Err(InconsistentPosixTimeZoneError::Designation);
        }
        Ok(())
    }

    /// Add civil datetimes to our transitions.
    ///
    /// This speeds up time zone lookups when the input is a civil datetime.
    fn add_civil_datetimes_to_transitions(&mut self) {
        let trans = &mut self.transitions;
        trans.infos[0].kind = TransitionKind::Unambiguous;
        trans.civil_starts[0] = DateTime::MIN;
        trans.civil_ends[0] = DateTime::MIN;
        for i in 1..trans.timestamps.len() {
            let timestamp = trans.timestamps[i];
            let offset = {
                let type_index = trans.infos[i].type_index;
                self.types[usize::from(type_index)].offset
            };
            let prev_offset = {
                let type_index = trans.infos[i.saturating_sub(1)].type_index;
                self.types[usize::from(type_index)].offset
            };

            if prev_offset == offset {
                let start = timestamp.to_datetime(prev_offset);
                trans.infos[i].kind = TransitionKind::Unambiguous;
                trans.civil_starts[i] = start;
                trans.civil_ends[i] = start;
            } else if prev_offset < offset {
                trans.infos[i].kind = TransitionKind::Gap;
                trans.civil_starts[i] = timestamp.to_datetime(prev_offset);
                trans.civil_ends[i] = timestamp.to_datetime(offset);
            } else {
                debug_assert!(prev_offset > offset);
                trans.infos[i].kind = TransitionKind::Fold;
                trans.civil_starts[i] = timestamp.to_datetime(offset);
                trans.civil_ends[i] = timestamp.to_datetime(prev_offset);
            }
        }
    }

    /// Fatten up this TZif data with additional transitions from the POSIX
    /// time zone footer.
    fn fatten(&mut self) {
        // We only fatten up TZif data when requested.
        if !cfg!(feature = "tz-fat") {
            return;
        }
        let Some(posix_tz) = self.fixed.posix_tz.clone() else {
            return;
        };
        let Some(&last) = self.transitions.timestamps.last() else { return };
        let mut i = 0;
        let mut next = last;
        loop {
            if i > FATTEN_MAX_TRANSITIONS {
                warn!(
                    "fattening TZif data for somehow generated more than \
                     {max} transitions, so giving up to avoid \
                     doing too much work",
                    max = FATTEN_MAX_TRANSITIONS,
                );
                return;
            }
            i += 1;
            next = match self.fatten_add_transition(&posix_tz, next) {
                None => break,
                Some(next) => next,
            };
        }
    }

    fn fatten_add_transition(
        &mut self,
        posix_tz: &posix::TimeZone,
        prev: Timestamp,
    ) -> Option<Timestamp> {
        let prev = crate::Timestamp::from_second(prev.as_second()).ok()?;
        let trans = posix_tz.next_transition(prev)?;
        if trans.timestamp().to_datetime(Offset::UTC).date().year()
            >= FATTEN_UP_TO_YEAR
        {
            return None;
        }
        let type_index = self.find_or_create_local_time_type(
            trans.offset(),
            trans.abbreviation().as_ref(),
            trans.dst(),
        )?;
        self.transitions.add_with_type_index(
            Timestamp::new(trans.timestamp()),
            type_index,
        );
        Some(Timestamp::new(trans.timestamp()))
    }

    fn find_or_create_local_time_type(
        &mut self,
        offset: Offset,
        abbrev: &str,
        dst: Dst,
    ) -> Option<u8> {
        for (i, typ) in self.types.iter().enumerate() {
            if offset == typ.offset
                && abbrev == self.designation(typ)
                && dst == typ.dst
            {
                return u8::try_from(i).ok();
            }
        }
        let i = u8::try_from(self.types.len()).ok()?;
        let designation = self.find_or_create_designation(abbrev)?;
        self.types.push(LocalTimeType {
            offset,
            dst,
            designation,
            indicator: Indicator::LocalWall,
        });
        Some(i)
    }

    /// Looks for a designation matching `needle` and returns its offset.
    ///
    /// If one is not found, then a new designation is added and its new offset
    /// is returned.
    ///
    /// If the offset of the designation exceeds `u8::MAX`, then this returns
    /// `None`. This is not possible for designations in a RFC 9636 TZif file,
    /// since their offsets are always a single byte big. However, it is
    /// theoretically possible for this to return `None` on conforming data
    /// when fattening is enabled. In which case, it's possible for new local
    /// time types to be added beyond the maximum. But this would require its
    /// POSIX time zone to use a local time type not found in the file already.
    fn find_or_create_designation(&mut self, needle: &str) -> Option<u8> {
        if let Some(i) =
            self.fixed.designations.iter().position(|abbrev| abbrev == needle)
        {
            return u8::try_from(i).ok();
        }
        let i = u8::try_from(self.fixed.designations.len()).ok()?;
        self.fixed.designations.push(Abbreviation::new_or_heap(needle));
        Some(i)
    }

    fn designation(&self, typ: &LocalTimeType) -> &str {
        &self.fixed.designations[usize::from(typ.designation)]
    }
}

impl ParsedTransitions {
    fn add(&mut self, timestamp: Timestamp) {
        self.add_with_type_index(timestamp, 0);
    }

    fn add_with_type_index(&mut self, timestamp: Timestamp, type_index: u8) {
        self.timestamps.push(timestamp);
        self.civil_starts.push(DateTime::MIN);
        self.civil_ends.push(DateTime::MIN);
        self.infos.push(TransitionInfo {
            type_index,
            kind: TransitionKind::Unambiguous,
        });
    }
}

/// The header for a TZif formatted file.
///
/// V2+ TZif files have two headers: one for V1 data, and then a second
/// following the V1 data block that describes another data block which uses
/// 64-bit timestamps.
#[derive(Debug)]
struct Header {
    time_size: usize,
    version: u8,
    tzh_ttisutcnt: usize,
    tzh_ttisstdcnt: usize,
    tzh_leapcnt: usize,
    tzh_timecnt: usize,
    tzh_typecnt: usize,
    tzh_charcnt: usize,
}

impl Header {
    fn parse(
        time_size: usize,
        bytes: &[u8],
    ) -> Result<(Header, &[u8]), HeaderError> {
        assert!(time_size == 4 || time_size == 8, "time size must be 4 or 8");
        if bytes.len() < 44 {
            return Err(HeaderError::TooShort);
        }
        let (magic, rest) = bytes.split_at(4);
        if magic != b"TZif" {
            return Err(HeaderError::MismatchMagic);
        }
        let (version, rest) = rest.split_at(1);
        let (_reserved, rest) = rest.split_at(15);

        let (tzh_ttisutcnt_bytes, rest) = rest.split_at(4);
        let (tzh_ttisstdcnt_bytes, rest) = rest.split_at(4);
        let (tzh_leapcnt_bytes, rest) = rest.split_at(4);
        let (tzh_timecnt_bytes, rest) = rest.split_at(4);
        let (tzh_typecnt_bytes, rest) = rest.split_at(4);
        let (tzh_charcnt_bytes, rest) = rest.split_at(4);

        let tzh_ttisutcnt =
            from_be_bytes_u32_to_usize(tzh_ttisutcnt_bytes).map_err(|e| {
                HeaderError::ParseCount { kind: CountKind::Ut, convert: e }
            })?;
        let tzh_ttisstdcnt =
            from_be_bytes_u32_to_usize(tzh_ttisstdcnt_bytes).map_err(|e| {
                HeaderError::ParseCount { kind: CountKind::Std, convert: e }
            })?;
        let tzh_leapcnt =
            from_be_bytes_u32_to_usize(tzh_leapcnt_bytes).map_err(|e| {
                HeaderError::ParseCount { kind: CountKind::Leap, convert: e }
            })?;
        let tzh_timecnt =
            from_be_bytes_u32_to_usize(tzh_timecnt_bytes).map_err(|e| {
                HeaderError::ParseCount { kind: CountKind::Time, convert: e }
            })?;
        let tzh_typecnt =
            from_be_bytes_u32_to_usize(tzh_typecnt_bytes).map_err(|e| {
                HeaderError::ParseCount { kind: CountKind::Type, convert: e }
            })?;
        let tzh_charcnt =
            from_be_bytes_u32_to_usize(tzh_charcnt_bytes).map_err(|e| {
                HeaderError::ParseCount { kind: CountKind::Char, convert: e }
            })?;

        if tzh_ttisutcnt != 0 && tzh_ttisutcnt != tzh_typecnt {
            return Err(HeaderError::MismatchUtType);
        }
        if tzh_ttisstdcnt != 0 && tzh_ttisstdcnt != tzh_typecnt {
            return Err(HeaderError::MismatchStdType);
        }
        if tzh_typecnt < 1 {
            return Err(HeaderError::ZeroType);
        }
        if tzh_charcnt < 1 {
            return Err(HeaderError::ZeroChar);
        }

        let header = Header {
            time_size,
            version: version[0],
            tzh_ttisutcnt,
            tzh_ttisstdcnt,
            tzh_leapcnt,
            tzh_timecnt,
            tzh_typecnt,
            tzh_charcnt,
        };
        Ok((header, rest))
    }

    fn is_32bit(&self) -> bool {
        self.time_size == 4
    }

    fn data_block_len(&self) -> Result<usize, HeaderError> {
        let a = self.transition_times_len()?;
        let b = self.transition_types_len();
        let c = self.local_time_types_len()?;
        let d = self.time_zone_designations_len();
        let e = self.leap_second_len()?;
        let f = self.standard_wall_len();
        let g = self.ut_local_len();
        a.checked_add(b)
            .and_then(|z| z.checked_add(c))
            .and_then(|z| z.checked_add(d))
            .and_then(|z| z.checked_add(e))
            .and_then(|z| z.checked_add(f))
            .and_then(|z| z.checked_add(g))
            .ok_or(HeaderError::InvalidDataBlock { version: self.version })
    }

    fn transition_times_len(&self) -> Result<usize, HeaderError> {
        self.tzh_timecnt
            .checked_mul(self.time_size)
            .ok_or(HeaderError::InvalidTimeCount)
    }

    fn transition_types_len(&self) -> usize {
        self.tzh_timecnt
    }

    fn local_time_types_len(&self) -> Result<usize, HeaderError> {
        self.tzh_typecnt.checked_mul(6).ok_or(HeaderError::InvalidTypeCount)
    }

    fn time_zone_designations_len(&self) -> usize {
        self.tzh_charcnt
    }

    fn leap_second_len(&self) -> Result<usize, HeaderError> {
        let record_len = self
            .time_size
            .checked_add(4)
            .expect("4-or-8 plus 4 always fits in usize");
        self.tzh_leapcnt
            .checked_mul(record_len)
            .ok_or(HeaderError::InvalidLeapSecondCount)
    }

    fn standard_wall_len(&self) -> usize {
        self.tzh_ttisstdcnt
    }

    fn ut_local_len(&self) -> usize {
        self.tzh_ttisutcnt
    }
}

/// An error that can occur when parsing TZif data.
///
/// This is only available when the `alloc` feature is enabled because parsing
/// TZif data requires heap allocation.
#[derive(Clone, Debug, Eq, PartialEq)]
#[cfg_attr(feature = "defmt", derive(defmt::Format))]
pub struct ParseError {
    kind: ParseErrorKind,
}

#[derive(Clone, Debug, Eq, PartialEq)]
#[cfg_attr(feature = "defmt", derive(defmt::Format))]
enum ParseErrorKind {
    Footer(FooterError),
    Header(HeaderError),
    Header32(HeaderError),
    Header64(HeaderError),
    InconsistentPosixTimeZone(InconsistentPosixTimeZoneError),
    Indicator(IndicatorError),
    LocalTimeType(LocalTimeTypeError),
    SplitAt(SplitAtError),
    TimeZoneDesignator(TimeZoneDesignatorError),
    TransitionType(TransitionTypeError),
}

#[cfg(feature = "std")]
impl std::error::Error for ParseError {}

impl core::fmt::Display for ParseError {
    fn fmt(&self, f: &mut core::fmt::Formatter) -> core::fmt::Result {
        use self::ParseErrorKind::*;
        match self.kind {
            Footer(ref err) => {
                f.write_str("invalid TZif footer: ")?;
                err.fmt(f)
            }
            Header(ref err) => {
                f.write_str("invalid TZif header: ")?;
                err.fmt(f)
            }
            Header32(ref err) => {
                f.write_str("invalid 32-bit TZif header: ")?;
                err.fmt(f)
            }
            Header64(ref err) => {
                f.write_str("invalid 64-bit TZif header: ")?;
                err.fmt(f)
            }
            InconsistentPosixTimeZone(ref err) => {
                f.write_str(
                    "found inconsistency with POSIX time zone transition \
                     rule in TZif file footer: ",
                )?;
                err.fmt(f)
            }
            Indicator(ref err) => {
                f.write_str("failed to parse indicators: ")?;
                err.fmt(f)
            }
            LocalTimeType(ref err) => {
                f.write_str("failed to parse local time types: ")?;
                err.fmt(f)
            }
            SplitAt(ref err) => err.fmt(f),
            TimeZoneDesignator(ref err) => {
                f.write_str("failed to parse time zone designators: ")?;
                err.fmt(f)
            }
            TransitionType(ref err) => {
                f.write_str("failed to parse time zone transition types: ")?;
                err.fmt(f)
            }
        }
    }
}

impl From<ParseErrorKind> for ParseError {
    fn from(kind: ParseErrorKind) -> ParseError {
        ParseError { kind }
    }
}

impl From<HeaderError> for ParseError {
    fn from(err: HeaderError) -> ParseError {
        ParseErrorKind::Header(err).into()
    }
}

impl From<FooterError> for ParseError {
    fn from(err: FooterError) -> ParseError {
        ParseErrorKind::Footer(err).into()
    }
}

impl From<InconsistentPosixTimeZoneError> for ParseError {
    fn from(err: InconsistentPosixTimeZoneError) -> ParseError {
        ParseErrorKind::InconsistentPosixTimeZone(err).into()
    }
}

impl From<IndicatorError> for ParseError {
    fn from(err: IndicatorError) -> ParseError {
        ParseErrorKind::Indicator(err).into()
    }
}

impl From<LocalTimeTypeError> for ParseError {
    fn from(err: LocalTimeTypeError) -> ParseError {
        ParseErrorKind::LocalTimeType(err).into()
    }
}

impl From<SplitAtError> for ParseError {
    fn from(err: SplitAtError) -> ParseError {
        ParseErrorKind::SplitAt(err).into()
    }
}

impl From<TimeZoneDesignatorError> for ParseError {
    fn from(err: TimeZoneDesignatorError) -> ParseError {
        ParseErrorKind::TimeZoneDesignator(err).into()
    }
}

impl From<TransitionTypeError> for ParseError {
    fn from(err: TransitionTypeError) -> ParseError {
        ParseErrorKind::TransitionType(err).into()
    }
}

#[derive(Clone, Debug, Eq, PartialEq)]
#[cfg_attr(feature = "defmt", derive(defmt::Format))]
enum TransitionTypeError {
    ExceedsLocalTimeTypes,
    Split(SplitAtError),
}

impl From<SplitAtError> for TransitionTypeError {
    fn from(err: SplitAtError) -> TransitionTypeError {
        TransitionTypeError::Split(err)
    }
}

impl core::fmt::Display for TransitionTypeError {
    fn fmt(&self, f: &mut core::fmt::Formatter) -> core::fmt::Result {
        use self::TransitionTypeError::*;
        match *self {
            ExceedsLocalTimeTypes => f.write_str(
                "found time zone transition type index that exceeds the \
                 number of local time types",
            ),
            Split(ref err) => err.fmt(f),
        }
    }
}

#[derive(Clone, Debug, Eq, PartialEq)]
#[cfg_attr(feature = "defmt", derive(defmt::Format))]
enum LocalTimeTypeError {
    InvalidOffset { offset: i32 },
}

impl core::fmt::Display for LocalTimeTypeError {
    fn fmt(&self, f: &mut core::fmt::Formatter) -> core::fmt::Result {
        use self::LocalTimeTypeError::*;
        match *self {
            InvalidOffset { offset } => write!(
                f,
                "found local time type with out-of-bounds time zone offset: \
                 {offset}, Jiff's allowed range is \
                 `{OFFSET_MIN}..={OFFSET_MAX}`"
            ),
        }
    }
}

#[derive(Clone, Debug, Eq, PartialEq)]
#[cfg_attr(feature = "defmt", derive(defmt::Format))]
enum TimeZoneDesignatorError {
    InvalidEnd,
    InvalidLength,
    InvalidStart,
    InvalidUtf8,
    MissingNul,
    Split(SplitAtError),
}

impl From<SplitAtError> for TimeZoneDesignatorError {
    fn from(err: SplitAtError) -> TimeZoneDesignatorError {
        TimeZoneDesignatorError::Split(err)
    }
}

impl core::fmt::Display for TimeZoneDesignatorError {
    fn fmt(&self, f: &mut core::fmt::Formatter) -> core::fmt::Result {
        use self::TimeZoneDesignatorError::*;
        match *self {
            InvalidEnd => f.write_str(
                "found invalid end of time zone designator for local time type",
            ),
            InvalidLength => f.write_str(
                "found invalid length of time zone designator for local time \
                 type",
            ),
            InvalidStart => f.write_str(
                "found invalid start of time zone designator for local time \
                 type",
            ),
            InvalidUtf8 => {
                f.write_str("found invalid UTF-8 in time zone designators")
            }
            MissingNul => f.write_str(
                "could not find NUL terminator for time zone designator",
            ),
            Split(ref err) => err.fmt(f),
        }
    }
}

#[derive(Clone, Debug, Eq, PartialEq)]
#[cfg_attr(feature = "defmt", derive(defmt::Format))]
enum IndicatorError {
    InvalidCombination,
    InvalidStdWallIndicator,
    InvalidUtWallCombination,
    Split(SplitAtError),
    UtLocalNonZero,
}

impl From<SplitAtError> for IndicatorError {
    fn from(err: SplitAtError) -> IndicatorError {
        IndicatorError::Split(err)
    }
}

impl core::fmt::Display for IndicatorError {
    fn fmt(&self, f: &mut core::fmt::Formatter) -> core::fmt::Result {
        use self::IndicatorError::*;
        match *self {
            InvalidCombination => f.write_str(
                "found invalid std/wall or UT/local value for local time type, \
                 each must be 0 or 1",
            ),
            InvalidStdWallIndicator => f.write_str(
                "found invalid std/wall indicator, expected it to be 0 or 1",
            ),
            InvalidUtWallCombination => f.write_str(
                "found invalid UT-wall combination for local time type, only \
                 local-wall, local-standard and UT-standard are allowed",
            ),
            Split(ref err) => err.fmt(f),
            UtLocalNonZero => f.write_str(
                "found non-zero UT/local indicator, but all such indicators \
                 should be zero",
            ),
        }
    }
}

#[derive(Clone, Debug, Eq, PartialEq)]
#[cfg_attr(feature = "defmt", derive(defmt::Format))]
enum InconsistentPosixTimeZoneError {
    Designation,
    Dst,
    Offset,
}

impl core::fmt::Display for InconsistentPosixTimeZoneError {
    fn fmt(&self, f: &mut core::fmt::Formatter) -> core::fmt::Result {
        use self::InconsistentPosixTimeZoneError::*;
        match *self {
            Designation => f.write_str(
                "expected last transition in TZif file to have a time zone \
                 abbreviation matching the abbreviation derived from the POSIX \
                 time zone transition rule",
            ),
            Dst => f.write_str(
                "expected last transition in TZif file to have a DST status \
                 matching the status derived from the POSIX time zone \
                 transition rule",
            ),
            Offset => f.write_str(
                "expected last transition in TZif file to have DST offset \
                 matching the offset derived from the POSIX time zone \
                 transition rule",
            ),
        }
    }
}

#[derive(Clone, Debug, Eq, PartialEq)]
#[cfg_attr(feature = "defmt", derive(defmt::Format))]
enum FooterError {
    InvalidPosixTz(posix::ParseError),
    MismatchEnd,
    TerminatorNotFound,
    UnexpectedEnd,
}

impl core::fmt::Display for FooterError {
    fn fmt(&self, f: &mut core::fmt::Formatter) -> core::fmt::Result {
        use self::FooterError::*;
        match *self {
            InvalidPosixTz(ref err) => {
                f.write_str("invalid POSIX time zone transition rule")?;
                core::fmt::Display::fmt(err, f)
            }
            MismatchEnd => f.write_str(
                "expected to find `\\n` at the beginning of the TZif file \
                 footer, but found something else instead",
            ),
            TerminatorNotFound => f.write_str(
                "expected to find `\\n` terminating the TZif file footer, but \
                 no line terminator could be found",
            ),
            UnexpectedEnd => f.write_str(
                "expected to find `\\n` at the beginning of the TZif file \
                 footer, but found unexpected end of data",
            ),
        }
    }
}

#[derive(Clone, Debug, Eq, PartialEq)]
#[cfg_attr(feature = "defmt", derive(defmt::Format))]
enum HeaderError {
    InvalidDataBlock { version: u8 },
    InvalidLeapSecondCount,
    InvalidTimeCount,
    InvalidTypeCount,
    MismatchMagic,
    MismatchStdType,
    MismatchUtType,
    ParseCount { kind: CountKind, convert: U32UsizeError },
    TooShort,
    ZeroChar,
    ZeroType,
}

impl core::fmt::Display for HeaderError {
    fn fmt(&self, f: &mut core::fmt::Formatter) -> core::fmt::Result {
        use self::HeaderError::*;
        match *self {
            InvalidDataBlock { version } => write!(
                f,
                "length of data block in V{version} TZif file is too big",
            ),
            InvalidLeapSecondCount => {
                f.write_str("number of leap seconds is too big")
            }
            InvalidTimeCount => {
                f.write_str("number of transition times is too big")
            }
            InvalidTypeCount => {
                f.write_str("number of local time types is too big")
            }
            MismatchMagic => f.write_str("magic bytes mismatch"),
            MismatchStdType => f.write_str(
                "expected number of standard/wall indicators to be zero or \
                 equal to the number of local time types",
            ),
            MismatchUtType => f.write_str(
                "expected number of UT/local indicators to be zero or equal \
                 to the number of local time types",
            ),
            ParseCount { ref kind, ref convert } => {
                write!(f, "failed to parse `{kind}`: {convert}")
            }
            TooShort => f.write_str("too short"),
            ZeroChar => f.write_str(
                "expected number of time zone abbreviations to be at least 1",
            ),
            ZeroType => f.write_str(
                "expected number of local time types to be at least 1",
            ),
        }
    }
}

#[derive(Clone, Debug, Eq, PartialEq)]
#[cfg_attr(feature = "defmt", derive(defmt::Format))]
enum CountKind {
    Ut,
    Std,
    Leap,
    Time,
    Type,
    Char,
}

impl core::fmt::Display for CountKind {
    fn fmt(&self, f: &mut core::fmt::Formatter) -> core::fmt::Result {
        use self::CountKind::*;
        match *self {
            Ut => f.write_str("tzh_ttisutcnt"),
            Std => f.write_str("tzh_ttisstdcnt"),
            Leap => f.write_str("tzh_leapcnt"),
            Time => f.write_str("tzh_timecnt"),
            Type => f.write_str("tzh_typecnt"),
            Char => f.write_str("tzh_charcnt"),
        }
    }
}

#[derive(Clone, Debug, Eq, PartialEq)]
#[cfg_attr(feature = "defmt", derive(defmt::Format))]
enum SplitAtError {
    V1,
    LeapSeconds,
    LocalTimeTypes,
    StandardWallIndicators,
    TimeZoneDesignations,
    TransitionTimes,
    TransitionTypes,
    UTLocalIndicators,
}

impl core::fmt::Display for SplitAtError {
    fn fmt(&self, f: &mut core::fmt::Formatter) -> core::fmt::Result {
        use self::SplitAtError::*;
        f.write_str("expected bytes for '")?;
        f.write_str(match *self {
            V1 => "v1 TZif",
            LeapSeconds => "leap seconds",
            LocalTimeTypes => "local time types",
            StandardWallIndicators => "standard/wall indicators",
            TimeZoneDesignations => "time zone designations",
            TransitionTimes => "transition times",
            TransitionTypes => "transition types",
            UTLocalIndicators => "UT/local indicators",
        })?;
        f.write_str("data block', but did not find enough bytes")?;
        Ok(())
    }
}

#[derive(Clone, Debug, Eq, PartialEq)]
#[cfg_attr(feature = "defmt", derive(defmt::Format))]
struct U32UsizeError;

impl core::fmt::Display for U32UsizeError {
    fn fmt(&self, f: &mut core::fmt::Formatter) -> core::fmt::Result {
        write!(
            f,
            "failed to parse integer because it is bigger than `{max}`",
            max = usize::MAX,
        )
    }
}

fn try_split_at<'b>(
    what: SplitAtError,
    bytes: &'b [u8],
    at: usize,
) -> Result<(&'b [u8], &'b [u8]), SplitAtError> {
    if at > bytes.len() {
        Err(what)
    } else {
        Ok(bytes.split_at(at))
    }
}

fn from_be_bytes_u32_to_usize(bytes: &[u8]) -> Result<usize, U32UsizeError> {
    let n = from_be_bytes_u32(bytes);
    usize::try_from(n).map_err(|_| U32UsizeError)
}

fn from_be_bytes_u32(bytes: &[u8]) -> u32 {
    u32::from_be_bytes(bytes.try_into().unwrap())
}

fn from_be_bytes_i32(bytes: &[u8]) -> i32 {
    i32::from_be_bytes(bytes.try_into().unwrap())
}

fn from_be_bytes_i64(bytes: &[u8]) -> i64 {
    i64::from_be_bytes(bytes.try_into().unwrap())
}

// These are some basic sanity tests on the parser. The real tests come in the
// parent module where we test the transitions themselves.
#[cfg(test)]
mod tests {
    use alloc::vec::Vec;

    use super::*;

    fn push_u32(bytes: &mut Vec<u8>, n: u32) {
        bytes.extend_from_slice(&n.to_be_bytes());
    }

    fn push_header(bytes: &mut Vec<u8>, version: u8) {
        bytes.extend_from_slice(b"TZif");
        bytes.push(version);
        bytes.extend_from_slice(&[0; 15]);
        push_u32(bytes, 0); // tzh_ttisutcnt
        push_u32(bytes, 0); // tzh_ttisstdcnt
        push_u32(bytes, 0); // tzh_leapcnt
        push_u32(bytes, 0); // tzh_timecnt
        push_u32(bytes, 1); // tzh_typecnt
        push_u32(bytes, 4); // tzh_charcnt
    }

    fn push_utc_type_and_designation(bytes: &mut Vec<u8>) {
        bytes.extend_from_slice(&0i32.to_be_bytes());
        bytes.push(0); // isdst
        bytes.push(0); // designation index
        bytes.extend_from_slice(b"UTC\0");
    }

    fn minimal_v1() -> Vec<u8> {
        let mut bytes = vec![];
        push_header(&mut bytes, 0);
        push_utc_type_and_designation(&mut bytes);
        bytes
    }

    fn minimal_v2(footer: &[u8]) -> Vec<u8> {
        let mut bytes = vec![];
        push_header(&mut bytes, b'2');
        push_utc_type_and_designation(&mut bytes);
        push_header(&mut bytes, b'2');
        push_utc_type_and_designation(&mut bytes);
        bytes.push(b'\n');
        bytes.extend_from_slice(footer);
        bytes.push(b'\n');
        bytes
    }

    #[test]
    fn parse_minimal_v1() {
        let tzif = TimeZone::parse(&minimal_v1()).unwrap();
        assert_eq!(tzif.version, 0);
        assert_eq!(tzif.designations.as_ref(), &[Abbreviation::array("UTC")]);
        assert_eq!(tzif.types.len(), 1);
        assert_eq!(tzif.types[0].offset, Offset::UTC);
        assert_eq!(tzif.transitions.timestamps.len(), 1);
        assert_eq!(tzif.transitions.timestamps[0], Timestamp::MIN);
        assert_eq!(tzif.transitions.civil_starts[0], DateTime::MIN);
    }

    #[test]
    fn parse_minimal_v2() {
        let tzif = TimeZone::parse(&minimal_v2(b"UTC0")).unwrap();
        assert_eq!(tzif.version, b'2');
        assert!(tzif.posix_tz.is_some());
        assert_eq!(tzif.designations.as_ref(), &[Abbreviation::array("UTC")]);
        assert_eq!(tzif.types.len(), 1);
        assert_eq!(tzif.transitions.timestamps.len(), 1);
    }

    #[test]
    fn parse_minimal_v2_with_and_without_tz_fat() {
        let bytes = minimal_v2(b"EST5EDT,M3.2.0,M11.1.0");
        let tzif = TimeZone::parse(&bytes).unwrap();
        let expected = if cfg!(feature = "tz-fat") { 302 } else { 1 };
        assert_eq!(tzif.transitions.timestamps.len(), expected);
    }
}