lcpfs 2026.1.102

// Copyright 2025 LunaOS Contributors
// SPDX-License-Identifier: Apache-2.0

//! TimeSpec resolution to transaction group numbers.
//!
//! This module handles converting various time specifications (timestamps, datetime strings,
//! relative expressions, snapshot names) to concrete transaction group (TXG) numbers that
//! can be used to query historical filesystem state.

use alloc::string::String;
use alloc::vec;
use alloc::vec::Vec;

use super::types::{SnapshotInfo, TimeError, TimeSpec};

// ═══════════════════════════════════════════════════════════════════════════════
// CONSTANTS
// ═══════════════════════════════════════════════════════════════════════════════

/// Seconds per minute.
const SECS_PER_MINUTE: u64 = 60;
/// Seconds per hour.
const SECS_PER_HOUR: u64 = 3600;
/// Seconds per day.
const SECS_PER_DAY: u64 = 86400;
/// Seconds per week.
const SECS_PER_WEEK: u64 = 604800;

// ═══════════════════════════════════════════════════════════════════════════════
// TXG HISTORY
// ═══════════════════════════════════════════════════════════════════════════════

/// A record mapping a TXG to its creation timestamp.
#[derive(Debug, Clone, Copy)]
pub struct TxgTimestamp {
    /// Transaction group number.
    pub txg: u64,
    /// Unix timestamp when this TXG was synced.
    pub timestamp: u64,
}

/// History provider trait for TXG lookups.
///
/// This trait must be implemented by the filesystem to provide TXG history.
pub trait TxgHistoryProvider {
    /// Get the current TXG.
    fn current_txg(&self) -> u64;

    /// Get the current timestamp.
    fn current_timestamp(&self) -> u64;

    /// Get the minimum (oldest) available TXG.
    fn min_txg(&self) -> u64;

    /// Get the timestamp for a specific TXG.
    fn txg_to_timestamp(&self, txg: u64) -> Option<u64>;

    /// Find the TXG that was active at a given timestamp.
    /// Returns the most recent TXG with timestamp <= target.
    fn timestamp_to_txg(&self, timestamp: u64) -> Option<u64>;

    /// Get TXG history entries for binary search.
    fn txg_history(&self) -> Vec<TxgTimestamp>;

    /// Look up a snapshot by name.
    fn lookup_snapshot(&self, name: &str) -> Option<SnapshotInfo>;

    /// List all snapshots.
    fn list_snapshots(&self) -> Vec<SnapshotInfo>;
}

// ═══════════════════════════════════════════════════════════════════════════════
// TIMESPEC RESOLVER
// ═══════════════════════════════════════════════════════════════════════════════

/// Resolver for converting TimeSpec to TXG numbers.
pub struct TimeSpecResolver<'a, P: TxgHistoryProvider> {
    provider: &'a P,
}

impl<'a, P: TxgHistoryProvider> TimeSpecResolver<'a, P> {
    /// Create a new resolver with the given history provider.
    pub fn new(provider: &'a P) -> Self {
        Self { provider }
    }

    /// Resolve a TimeSpec to a TXG number.
    pub fn resolve(&self, spec: &TimeSpec) -> Result<u64, TimeError> {
        match spec {
            TimeSpec::Txg(txg) => {
                // Validate TXG is in range
                if *txg < self.provider.min_txg() || *txg > self.provider.current_txg() {
                    return Err(TimeError::TxgNotFound(*txg));
                }
                Ok(*txg)
            }

            TimeSpec::Now => Ok(self.provider.current_txg()),

            TimeSpec::Timestamp(ts) => self.resolve_timestamp(*ts),

            TimeSpec::DateTime(s) => {
                let ts = parse_datetime(s)?;
                self.resolve_timestamp(ts)
            }

            TimeSpec::Relative(s) => {
                let offset = parse_relative_time(s)?;
                let now = self.provider.current_timestamp();
                let target = now.saturating_sub(offset);
                self.resolve_timestamp(target)
            }

            TimeSpec::Snapshot(name) => {
                let snap = self
                    .provider
                    .lookup_snapshot(name)
                    .ok_or_else(|| TimeError::SnapshotNotFound(name.clone()))?;
                Ok(snap.txg)
            }
        }
    }

    /// Resolve a timestamp to TXG using binary search.
    fn resolve_timestamp(&self, timestamp: u64) -> Result<u64, TimeError> {
        let history = self.provider.txg_history();

        if history.is_empty() {
            return Err(TimeError::NoHistory);
        }

        // Binary search for the TXG with the closest timestamp <= target
        let idx = binary_search_txg(&history, timestamp);

        if idx < history.len() {
            Ok(history[idx].txg)
        } else if !history.is_empty() {
            // Return the most recent if timestamp is in the future
            Ok(history[history.len() - 1].txg)
        } else {
            Err(TimeError::NoHistory)
        }
    }

    /// Validate that a TXG exists and has data.
    pub fn validate_txg(&self, txg: u64) -> Result<(), TimeError> {
        if txg < self.provider.min_txg() {
            return Err(TimeError::TxgNotFound(txg));
        }
        if txg > self.provider.current_txg() {
            return Err(TimeError::TxgNotFound(txg));
        }
        Ok(())
    }

    /// Get the timestamp for a resolved TXG.
    pub fn txg_timestamp(&self, txg: u64) -> Option<u64> {
        self.provider.txg_to_timestamp(txg)
    }
}

// ═══════════════════════════════════════════════════════════════════════════════
// BINARY SEARCH
// ═══════════════════════════════════════════════════════════════════════════════

/// Binary search for the TXG with timestamp <= target.
///
/// Returns the index of the last TXG whose timestamp is <= target timestamp.
fn binary_search_txg(history: &[TxgTimestamp], target: u64) -> usize {
    if history.is_empty() {
        return 0;
    }

    let mut left = 0;
    let mut right = history.len();

    while left < right {
        let mid = left + (right - left) / 2;

        if history[mid].timestamp <= target {
            left = mid + 1;
        } else {
            right = mid;
        }
    }

    // left now points to the first element > target, so left - 1 is the last <= target
    if left > 0 { left - 1 } else { 0 }
}

// ═══════════════════════════════════════════════════════════════════════════════
// DATETIME PARSING
// ═══════════════════════════════════════════════════════════════════════════════

/// Parse an ISO 8601 datetime string to Unix timestamp.
///
/// Supports formats:
/// - "2024-01-15" (date only, assumes 00:00:00 UTC)
/// - "2024-01-15 10:30:00" (date and time)
/// - "2024-01-15T10:30:00" (ISO 8601 with T separator)
/// - "2024-01-15T10:30:00Z" (with Z suffix)
fn parse_datetime(s: &str) -> Result<u64, TimeError> {
    let s = s.trim();

    // Remove trailing 'Z' if present
    let s = s.strip_suffix('Z').unwrap_or(s);
    let s = s.strip_suffix('z').unwrap_or(s);

    // Split into date and time parts
    let (date_part, time_part) = if s.contains('T') {
        let parts: Vec<&str> = s.splitn(2, 'T').collect();
        (parts[0], parts.get(1).copied())
    } else if s.contains(' ') {
        let parts: Vec<&str> = s.splitn(2, ' ').collect();
        (parts[0], parts.get(1).copied())
    } else {
        (s, None)
    };

    // Parse date: YYYY-MM-DD
    let date_parts: Vec<&str> = date_part.split('-').collect();
    if date_parts.len() != 3 {
        return Err(TimeError::InvalidTimeSpec(alloc::format!(
            "invalid date format: {}",
            s
        )));
    }

    let year: i32 = date_parts[0]
        .parse()
        .map_err(|_| TimeError::InvalidTimeSpec("invalid year".into()))?;
    let month: u32 = date_parts[1]
        .parse()
        .map_err(|_| TimeError::InvalidTimeSpec("invalid month".into()))?;
    let day: u32 = date_parts[2]
        .parse()
        .map_err(|_| TimeError::InvalidTimeSpec("invalid day".into()))?;

    // Validate ranges
    if !(1970..=2100).contains(&year) {
        return Err(TimeError::InvalidTimeSpec("year out of range".into()));
    }
    if !(1..=12).contains(&month) {
        return Err(TimeError::InvalidTimeSpec("month out of range".into()));
    }
    if !(1..=31).contains(&day) {
        return Err(TimeError::InvalidTimeSpec("day out of range".into()));
    }

    // Parse time if present: HH:MM:SS
    let (hour, minute, second) = if let Some(time) = time_part {
        let time_parts: Vec<&str> = time.split(':').collect();
        if time_parts.len() >= 2 {
            let h: u32 = time_parts[0]
                .parse()
                .map_err(|_| TimeError::InvalidTimeSpec("invalid hour".into()))?;
            let m: u32 = time_parts[1]
                .parse()
                .map_err(|_| TimeError::InvalidTimeSpec("invalid minute".into()))?;
            let s: u32 = time_parts.get(2).and_then(|s| s.parse().ok()).unwrap_or(0);

            if h > 23 || m > 59 || s > 59 {
                return Err(TimeError::InvalidTimeSpec("time out of range".into()));
            }

            (h, m, s)
        } else {
            (0, 0, 0)
        }
    } else {
        (0, 0, 0)
    };

    // Convert to Unix timestamp (simplified, assumes UTC)
    let timestamp = datetime_to_unix(year, month, day, hour, minute, second);

    Ok(timestamp)
}

/// Convert datetime components to Unix timestamp.
///
/// Simplified calculation assuming UTC. Uses the algorithm for calculating
/// days since epoch, then adds time components.
fn datetime_to_unix(year: i32, month: u32, day: u32, hour: u32, minute: u32, second: u32) -> u64 {
    // Days from epoch (1970-01-01) to the start of the given year
    let mut days = 0i64;

    // Add days for complete years
    for y in 1970..year {
        days += if is_leap_year(y) { 366 } else { 365 };
    }

    // If year is before 1970, subtract (not supported, but handle gracefully)
    if year < 1970 {
        return 0;
    }

    // Days in each month (non-leap year)
    let days_in_month = [31, 28, 31, 30, 31, 30, 31, 31, 30, 31, 30, 31];

    // Add days for complete months
    for m in 1..month {
        days += days_in_month[(m - 1) as usize] as i64;
        if m == 2 && is_leap_year(year) {
            days += 1; // February in leap year
        }
    }

    // Add days in current month (day is 1-indexed)
    days += (day - 1) as i64;

    // Convert to seconds and add time
    let total_seconds =
        days * SECS_PER_DAY as i64 + hour as i64 * 3600 + minute as i64 * 60 + second as i64;

    total_seconds.max(0) as u64
}

/// Check if a year is a leap year.
fn is_leap_year(year: i32) -> bool {
    (year % 4 == 0 && year % 100 != 0) || (year % 400 == 0)
}

// ═══════════════════════════════════════════════════════════════════════════════
// RELATIVE TIME PARSING
// ═══════════════════════════════════════════════════════════════════════════════

/// Parse a relative time expression to seconds offset.
///
/// Supports:
/// - "N seconds ago", "N minutes ago", "N hours ago", "N days ago", "N weeks ago"
/// - "yesterday" (equivalent to "1 day ago")
/// - "today" (equivalent to "0 days ago")
fn parse_relative_time(s: &str) -> Result<u64, TimeError> {
    let s = s.trim().to_lowercase();

    // Handle special cases
    if s == "yesterday" {
        return Ok(SECS_PER_DAY);
    }
    if s == "today" || s == "now" {
        return Ok(0);
    }

    // Parse "N unit ago" format
    let parts: Vec<&str> = s.split_whitespace().collect();

    if parts.len() < 2 {
        return Err(TimeError::InvalidTimeSpec(alloc::format!(
            "invalid relative time: {}",
            s
        )));
    }

    // Check for "ago" suffix
    let has_ago = parts.last().is_some_and(|p| *p == "ago");
    let unit_idx = if has_ago && parts.len() >= 3 {
        parts.len() - 2
    } else {
        parts.len() - 1
    };

    // Parse number
    let number: u64 = parts[0]
        .parse()
        .map_err(|_| TimeError::InvalidTimeSpec(alloc::format!("invalid number: {}", parts[0])))?;

    // Parse unit
    let unit = if unit_idx < parts.len() {
        parts[unit_idx]
    } else {
        return Err(TimeError::InvalidTimeSpec("missing time unit".into()));
    };

    let multiplier = match unit {
        "second" | "seconds" | "sec" | "secs" | "s" => 1,
        "minute" | "minutes" | "min" | "mins" | "m" => SECS_PER_MINUTE,
        "hour" | "hours" | "hr" | "hrs" | "h" => SECS_PER_HOUR,
        "day" | "days" | "d" => SECS_PER_DAY,
        "week" | "weeks" | "w" => SECS_PER_WEEK,
        _ => {
            return Err(TimeError::InvalidTimeSpec(alloc::format!(
                "unknown time unit: {}",
                unit
            )));
        }
    };

    Ok(number * multiplier)
}

// ═══════════════════════════════════════════════════════════════════════════════
// IN-MEMORY HISTORY PROVIDER (FOR TESTING)
// ═══════════════════════════════════════════════════════════════════════════════

/// Simple in-memory implementation of TxgHistoryProvider for testing.
#[derive(Debug, Default)]
pub struct InMemoryTxgHistory {
    /// TXG history entries (must be sorted by txg).
    pub entries: Vec<TxgTimestamp>,
    /// Snapshot registry.
    pub snapshots: Vec<SnapshotInfo>,
    /// Current TXG.
    pub current_txg: u64,
    /// Current timestamp.
    pub current_timestamp: u64,
    /// Minimum available TXG.
    pub min_txg: u64,
}

impl InMemoryTxgHistory {
    /// Create a new empty history.
    pub fn new() -> Self {
        Self::default()
    }

    /// Add a TXG entry.
    pub fn add_txg(&mut self, txg: u64, timestamp: u64) {
        self.entries.push(TxgTimestamp { txg, timestamp });
        // Keep sorted
        self.entries.sort_by_key(|e| e.txg);
        if txg > self.current_txg {
            self.current_txg = txg;
            self.current_timestamp = timestamp;
        }
    }

    /// Add a snapshot.
    pub fn add_snapshot(&mut self, info: SnapshotInfo) {
        self.snapshots.push(info);
    }
}

impl TxgHistoryProvider for InMemoryTxgHistory {
    fn current_txg(&self) -> u64 {
        self.current_txg
    }

    fn current_timestamp(&self) -> u64 {
        self.current_timestamp
    }

    fn min_txg(&self) -> u64 {
        self.min_txg
    }

    fn txg_to_timestamp(&self, txg: u64) -> Option<u64> {
        self.entries
            .iter()
            .find(|e| e.txg == txg)
            .map(|e| e.timestamp)
    }

    fn timestamp_to_txg(&self, timestamp: u64) -> Option<u64> {
        let idx = binary_search_txg(&self.entries, timestamp);
        if idx < self.entries.len() {
            Some(self.entries[idx].txg)
        } else {
            None
        }
    }

    fn txg_history(&self) -> Vec<TxgTimestamp> {
        self.entries.clone()
    }

    fn lookup_snapshot(&self, name: &str) -> Option<SnapshotInfo> {
        self.snapshots.iter().find(|s| s.name == name).cloned()
    }

    fn list_snapshots(&self) -> Vec<SnapshotInfo> {
        self.snapshots.clone()
    }
}

// ═══════════════════════════════════════════════════════════════════════════════
// TESTS
// ═══════════════════════════════════════════════════════════════════════════════

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

    fn create_test_history() -> InMemoryTxgHistory {
        let mut history = InMemoryTxgHistory::new();

        // Add some TXG entries spanning time
        // 2024-01-01 00:00:00 = 1704067200
        history.add_txg(100, 1704067200);
        // 2024-01-15 00:00:00 = 1705276800
        history.add_txg(200, 1705276800);
        // 2024-02-01 00:00:00 = 1706745600
        history.add_txg(300, 1706745600);
        // 2024-03-01 00:00:00 = 1709251200
        history.add_txg(400, 1709251200);
        // 2024-06-01 00:00:00 = 1717200000
        history.add_txg(500, 1717200000);

        history.min_txg = 100;

        // Add a snapshot
        history.add_snapshot(SnapshotInfo {
            name: "daily-backup".into(),
            creation_time: 1705276800,
            txg: 200,
            referenced: 1024 * 1024,
            used: 512 * 1024,
        });

        history
    }

    #[test]
    fn test_resolve_txg() {
        let history = create_test_history();
        let resolver = TimeSpecResolver::new(&history);

        let spec = TimeSpec::Txg(300);
        assert_eq!(resolver.resolve(&spec).unwrap(), 300);
    }

    #[test]
    fn test_resolve_now() {
        let history = create_test_history();
        let resolver = TimeSpecResolver::new(&history);

        let spec = TimeSpec::Now;
        assert_eq!(resolver.resolve(&spec).unwrap(), 500);
    }

    #[test]
    fn test_resolve_timestamp() {
        let history = create_test_history();
        let resolver = TimeSpecResolver::new(&history);

        // Timestamp exactly matching TXG 200
        let spec = TimeSpec::Timestamp(1705276800);
        assert_eq!(resolver.resolve(&spec).unwrap(), 200);

        // Timestamp between TXG 200 and 300
        let spec = TimeSpec::Timestamp(1706000000);
        assert_eq!(resolver.resolve(&spec).unwrap(), 200);
    }

    #[test]
    fn test_resolve_snapshot() {
        let history = create_test_history();
        let resolver = TimeSpecResolver::new(&history);

        let spec = TimeSpec::Snapshot("daily-backup".into());
        assert_eq!(resolver.resolve(&spec).unwrap(), 200);
    }

    #[test]
    fn test_resolve_snapshot_not_found() {
        let history = create_test_history();
        let resolver = TimeSpecResolver::new(&history);

        let spec = TimeSpec::Snapshot("nonexistent".into());
        assert!(matches!(
            resolver.resolve(&spec),
            Err(TimeError::SnapshotNotFound(_))
        ));
    }

    #[test]
    fn test_parse_datetime_date_only() {
        // 2024-01-15 00:00:00 UTC
        let ts = parse_datetime("2024-01-15").unwrap();
        assert_eq!(ts, 1705276800);
    }

    #[test]
    fn test_parse_datetime_with_time() {
        // 2024-01-15 12:30:45 UTC
        let ts = parse_datetime("2024-01-15 12:30:45").unwrap();
        assert_eq!(ts, 1705276800 + 12 * 3600 + 30 * 60 + 45);
    }

    #[test]
    fn test_parse_datetime_iso8601() {
        let ts = parse_datetime("2024-01-15T12:30:45Z").unwrap();
        assert_eq!(ts, 1705276800 + 12 * 3600 + 30 * 60 + 45);
    }

    #[test]
    fn test_parse_relative_hours_ago() {
        let offset = parse_relative_time("3 hours ago").unwrap();
        assert_eq!(offset, 3 * SECS_PER_HOUR);
    }

    #[test]
    fn test_parse_relative_days_ago() {
        let offset = parse_relative_time("7 days ago").unwrap();
        assert_eq!(offset, 7 * SECS_PER_DAY);
    }

    #[test]
    fn test_parse_relative_yesterday() {
        let offset = parse_relative_time("yesterday").unwrap();
        assert_eq!(offset, SECS_PER_DAY);
    }

    #[test]
    fn test_parse_relative_minutes() {
        let offset = parse_relative_time("30 minutes ago").unwrap();
        assert_eq!(offset, 30 * SECS_PER_MINUTE);
    }

    #[test]
    fn test_parse_relative_weeks() {
        let offset = parse_relative_time("2 weeks ago").unwrap();
        assert_eq!(offset, 2 * SECS_PER_WEEK);
    }

    #[test]
    fn test_binary_search_exact_match() {
        let history = vec![
            TxgTimestamp {
                txg: 100,
                timestamp: 1000,
            },
            TxgTimestamp {
                txg: 200,
                timestamp: 2000,
            },
            TxgTimestamp {
                txg: 300,
                timestamp: 3000,
            },
        ];

        assert_eq!(binary_search_txg(&history, 2000), 1);
    }

    #[test]
    fn test_binary_search_between() {
        let history = vec![
            TxgTimestamp {
                txg: 100,
                timestamp: 1000,
            },
            TxgTimestamp {
                txg: 200,
                timestamp: 2000,
            },
            TxgTimestamp {
                txg: 300,
                timestamp: 3000,
            },
        ];

        // Between 1000 and 2000, should return index 0 (last <= 1500)
        assert_eq!(binary_search_txg(&history, 1500), 0);

        // Between 2000 and 3000, should return index 1 (last <= 2500)
        assert_eq!(binary_search_txg(&history, 2500), 1);
    }

    #[test]
    fn test_binary_search_before_first() {
        let history = vec![
            TxgTimestamp {
                txg: 100,
                timestamp: 1000,
            },
            TxgTimestamp {
                txg: 200,
                timestamp: 2000,
            },
        ];

        // Before first timestamp, return first entry
        assert_eq!(binary_search_txg(&history, 500), 0);
    }

    #[test]
    fn test_binary_search_after_last() {
        let history = vec![
            TxgTimestamp {
                txg: 100,
                timestamp: 1000,
            },
            TxgTimestamp {
                txg: 200,
                timestamp: 2000,
            },
        ];

        // After last timestamp, return last entry
        assert_eq!(binary_search_txg(&history, 3000), 1);
    }

    #[test]
    fn test_resolve_datetime() {
        let history = create_test_history();
        let resolver = TimeSpecResolver::new(&history);

        let spec = TimeSpec::DateTime("2024-01-15".into());
        assert_eq!(resolver.resolve(&spec).unwrap(), 200);
    }

    #[test]
    fn test_is_leap_year() {
        assert!(is_leap_year(2000)); // Divisible by 400
        assert!(is_leap_year(2024)); // Divisible by 4, not 100
        assert!(!is_leap_year(1900)); // Divisible by 100, not 400
        assert!(!is_leap_year(2023)); // Not divisible by 4
    }

    #[test]
    fn test_datetime_to_unix_epoch() {
        // 1970-01-01 00:00:00 should be 0
        assert_eq!(datetime_to_unix(1970, 1, 1, 0, 0, 0), 0);
    }

    #[test]
    fn test_datetime_to_unix_known_date() {
        // 2024-01-01 00:00:00 UTC = 1704067200
        let ts = datetime_to_unix(2024, 1, 1, 0, 0, 0);
        assert_eq!(ts, 1704067200);
    }

    #[test]
    fn test_invalid_datetime() {
        assert!(parse_datetime("not-a-date").is_err());
        assert!(parse_datetime("2024-13-01").is_err()); // Invalid month
        assert!(parse_datetime("2024-01-32").is_err()); // Invalid day
    }

    #[test]
    fn test_invalid_relative() {
        assert!(parse_relative_time("not relative").is_err());
        assert!(parse_relative_time("abc days ago").is_err());
    }

    #[test]
    fn test_txg_out_of_range() {
        let history = create_test_history();
        let resolver = TimeSpecResolver::new(&history);

        // TXG below minimum
        let spec = TimeSpec::Txg(50);
        assert!(matches!(
            resolver.resolve(&spec),
            Err(TimeError::TxgNotFound(50))
        ));

        // TXG above current
        let spec = TimeSpec::Txg(1000);
        assert!(matches!(
            resolver.resolve(&spec),
            Err(TimeError::TxgNotFound(1000))
        ));
    }
}