lcpfs 2026.1.102

// Copyright 2025 LunaOS Contributors
// SPDX-License-Identifier: Apache-2.0
//
// Gravitational Indexing Engine
// Learned temporal coupling for predictive data placement.

// ALL thresholds are learned from observation - NO hardcoded values.
// ============================================================================

use alloc::collections::{BTreeMap, VecDeque};
use alloc::vec::Vec;
use lazy_static::lazy_static;
use libm::{fabs, sqrt};
use spin::Mutex;

// ═══════════════════════════════════════════════════════════════════════════════
// LEARNED THRESHOLDS (Welford's algorithm - no hardcoded values)
// ═══════════════════════════════════════════════════════════════════════════════

/// Adaptive threshold that learns optimal values from observed outcomes using Welford's algorithm.
/// All thresholds start uninformed and adjust based on reorganization success.
#[derive(Clone, Copy)]
pub struct LearnedThreshold {
    /// Current threshold value (continuously adjusted)
    pub value: f64,
    /// Statistical uncertainty in the threshold (decreases with observations)
    pub uncertainty: f64,
    /// Number of observations recorded
    pub observations: u64,
    /// Learning rate (decays as confidence increases)
    pub learning_rate: f64,
    /// Running mean of outcomes (for Welford's algorithm)
    pub mean_outcome: f64,
    /// Running variance of outcomes (for Welford's algorithm)
    pub variance: f64,
}

impl LearnedThreshold {
    /// Create an uninformed threshold with maximum uncertainty and no observations.
    /// The initial guess provides a starting point before any learning occurs.
    pub const fn uninformed(initial_guess: f64) -> Self {
        Self {
            value: initial_guess,
            uncertainty: f64::MAX,
            observations: 0,
            learning_rate: 1.0,
            mean_outcome: 0.0,
            variance: f64::MAX,
        }
    }

    /// Update threshold based on observed action and outcome.
    /// Uses Welford's algorithm for numerically stable variance calculation.
    /// Negative delta_epsilon (beneficial) increases threshold, positive decreases it.
    pub fn observe(&mut self, action_value: f64, outcome_delta_epsilon: f64) {
        self.observations += 1;
        let n = self.observations as f64;

        let delta = outcome_delta_epsilon - self.mean_outcome;
        self.mean_outcome += delta / n;
        let delta2 = outcome_delta_epsilon - self.mean_outcome;

        if self.observations > 1 {
            let m2 = self.variance * (n - 2.0) + delta * delta2;
            self.variance = m2 / (n - 1.0);
            self.uncertainty = sqrt(self.variance / n);
        }

        let adjustment = if outcome_delta_epsilon < 0.0 {
            (action_value - self.value) * self.learning_rate
        } else {
            (self.value - action_value) * self.learning_rate * 0.5
        };

        self.value += adjustment;
        self.learning_rate = 1.0 / (1.0 + sqrt(self.observations as f64) * 0.1);
    }

    /// Calculate confidence in this threshold (0.0 to 1.0).
    /// Combines observation count and uncertainty into a single confidence metric.
    pub fn confidence(&self) -> f64 {
        if self.observations == 0 {
            return 0.0;
        }
        let obs_factor = 1.0 - 1.0 / (1.0 + self.observations as f64 * 0.01);
        let unc_factor = 1.0 / (1.0 + fabs(self.uncertainty));
        obs_factor * unc_factor
    }

    /// Determine if an action should be taken based on current value and estimated benefit.
    /// Returns true if current_value exceeds threshold and benefit justifies uncertainty.
    pub fn should_act(&self, current_value: f64, estimated_benefit: f64) -> bool {
        let benefit_over_uncertainty = estimated_benefit / (self.uncertainty + 1e-10);
        current_value >= self.value && benefit_over_uncertainty > 1.0
    }
}

// ═══════════════════════════════════════════════════════════════════════════════
// ACCESS EVENTS
// ═══════════════════════════════════════════════════════════════════════════════

/// Record of a single object access for temporal coupling detection.
#[derive(Clone, Copy, Debug)]
pub struct AccessEvent {
    /// ID of the accessed object
    pub object_id: u64,
    /// Timestamp of access (in milliseconds)
    pub timestamp: u64,
}

/// Resonance between two objects (temporal coupling strength)
#[derive(Clone, Copy, Debug)]
pub struct Resonance {
    /// First object ID (lower ID in canonical ordering)
    pub object_a: u64,
    /// Second object ID (higher ID in canonical ordering)
    pub object_b: u64,
    /// Number of times these objects were accessed together
    pub co_access_count: u64,
    /// Average time gap between accesses (ms)
    pub avg_time_gap_ms: f64,
    /// Strength of coupling (higher = stronger)
    pub strength: f64,
}

impl Resonance {
    /// Calculate gravitational "force" between objects
    /// Higher force = should be closer together
    pub fn force(&self) -> f64 {
        // Force = co_access_count / (avg_time_gap^2)
        // Like gravity: F = G * m1 * m2 / r^2
        if self.avg_time_gap_ms < 1.0 {
            return self.co_access_count as f64 * 1000.0;
        }
        self.co_access_count as f64 / (self.avg_time_gap_ms * self.avg_time_gap_ms / 1_000_000.0)
    }
}

/// Outcome of a reorganization for learning
#[derive(Clone, Copy)]
pub struct ReorgOutcome {
    /// Primary object (destination for physical adjacency)
    pub leader_obj: u64,
    /// Secondary object (moved to be near leader)
    pub follower_obj: u64,
    /// Resonance strength when reorganization was decided
    pub resonance_at_decision: f64,
    /// Number of blocks physically relocated
    pub blocks_moved: u64,
    /// Time taken to complete reorganization (milliseconds)
    pub time_taken_ms: u64,
    /// System epsilon before reorganization
    pub epsilon_before: f64,
    /// System epsilon after reorganization
    pub epsilon_after: f64,
}

impl ReorgOutcome {
    /// Calculate the change in epsilon (negative means improvement).
    pub fn delta_epsilon(&self) -> f64 {
        self.epsilon_after - self.epsilon_before
    }

    /// Check if reorganization reduced epsilon (was beneficial).
    pub fn was_beneficial(&self) -> bool {
        self.delta_epsilon() < 0.0
    }
}

// ═══════════════════════════════════════════════════════════════════════════════
// GRAVITY WELL
// ═══════════════════════════════════════════════════════════════════════════════

lazy_static! {
    /// Global gravitational indexing engine instance.
    /// Detects temporal coupling and schedules physical reorganizations.
    pub static ref GRAVITY_ENGINE: Mutex<GravityWell> = Mutex::new(GravityWell::new());
}

/// Core gravitational indexing engine that detects temporal coupling and orchestrates
/// physical reorganization of logically distant but temporally coupled objects.
pub struct GravityWell {
    /// History of recent accesses
    pub history: VecDeque<AccessEvent>,

    /// Detected resonances between objects
    pub resonance_map: BTreeMap<(u64, u64), Resonance>,

    /// Reorganization history for learning
    outcomes: VecDeque<ReorgOutcome>,

    // ═══════════════════════════════════════════════════════════════════════════
    // LEARNED THRESHOLDS (no hardcoded values)
    // ═══════════════════════════════════════════════════════════════════════════
    /// Learned: Time window for detecting temporal coupling (ms)
    threshold_time_window: LearnedThreshold,

    /// Learned: Minimum co-access count to consider resonant
    threshold_coaccesses: LearnedThreshold,

    /// Learned: Minimum resonance strength to trigger reorganization
    threshold_strength: LearnedThreshold,

    /// Learned: History size before analysis
    threshold_history_size: LearnedThreshold,

    /// Learned: Cooldown between reorganizations of same pair (ms)
    reorg_cooldown_ms: LearnedThreshold,

    /// Learned: Maximum blocks to move in one reorganization
    max_blocks_per_reorg: LearnedThreshold,

    /// Current system epsilon
    current_epsilon: f64,

    /// Last reorg timestamp per pair
    last_reorg: BTreeMap<(u64, u64), u64>,

    /// Pending reorganizations
    pending_reorgs: VecDeque<(u64, u64)>,
}

impl Default for GravityWell {
    fn default() -> Self {
        Self::new()
    }
}

impl GravityWell {
    /// Create a new GravityWell with uninformed thresholds.
    /// All learning parameters start with maximum uncertainty and will adapt from observations.
    pub fn new() -> Self {
        Self {
            history: VecDeque::with_capacity(2000),
            resonance_map: BTreeMap::new(),
            outcomes: VecDeque::with_capacity(100),

            // Initialize with uninformed priors
            threshold_time_window: LearnedThreshold::uninformed(50.0), // 50ms default
            threshold_coaccesses: LearnedThreshold::uninformed(5.0),   // 5 co-accesses
            threshold_strength: LearnedThreshold::uninformed(100.0),   // Strength threshold
            threshold_history_size: LearnedThreshold::uninformed(1000.0), // Analyze after 1000 events
            reorg_cooldown_ms: LearnedThreshold::uninformed(86_400_000.0), // 24 hours
            max_blocks_per_reorg: LearnedThreshold::uninformed(1000.0),   // 1000 blocks max

            current_epsilon: 0.0,
            last_reorg: BTreeMap::new(),
            pending_reorgs: VecDeque::new(),
        }
    }

    /// Update current system epsilon
    pub fn update_epsilon(&mut self, epsilon: f64) {
        self.current_epsilon = epsilon;
    }

    /// Log an access event. Called by ZPL on read()/write().
    pub fn observe(&mut self, object_id: u64, tick: u64) {
        self.history.push_back(AccessEvent {
            object_id,
            timestamp: tick,
        });

        // Keep history bounded (learned size)
        let max_history = self.threshold_history_size.value as usize;
        while self.history.len() > max_history * 2 {
            self.history.pop_front();
        }

        // Trigger analysis when we have enough history
        if self.history.len() >= max_history {
            self.analyze_and_collapse();
        }
    }

    /// The Physics Engine: Detects entangled files using learned thresholds.
    fn analyze_and_collapse(&mut self) {
        let time_window = self.threshold_time_window.value as u64;
        let min_coaccesses = self.threshold_coaccesses.value as u64;

        // Build co-access counts
        let mut pairs: BTreeMap<(u64, u64), (u64, f64)> = BTreeMap::new(); // (count, total_gap)

        let history_vec: Vec<_> = self.history.iter().cloned().collect();

        for i in 0..history_vec.len() {
            let a = history_vec[i];

            // Look at nearby accesses within time window
            for b in history_vec.iter().skip(i + 1) {
                let gap = b.timestamp.saturating_sub(a.timestamp);
                if gap > time_window {
                    break; // Past time window
                }

                if a.object_id != b.object_id {
                    // Canonical pair ordering
                    let key = if a.object_id < b.object_id {
                        (a.object_id, b.object_id)
                    } else {
                        (b.object_id, a.object_id)
                    };

                    let entry = pairs.entry(key).or_insert((0, 0.0));
                    entry.0 += 1;
                    entry.1 += gap as f64;
                }
            }
        }

        // Update resonance map with new findings
        for ((obj_a, obj_b), (count, total_gap)) in pairs {
            if count >= min_coaccesses {
                let avg_gap = if count > 0 {
                    total_gap / count as f64
                } else {
                    0.0
                };

                let resonance = Resonance {
                    object_a: obj_a,
                    object_b: obj_b,
                    co_access_count: count,
                    avg_time_gap_ms: avg_gap,
                    strength: count as f64 / (avg_gap / 1000.0 + 1.0),
                };

                // Update or insert resonance
                self.resonance_map.insert((obj_a, obj_b), resonance);

                // Check if we should schedule a reorganization
                let reorg_benefit = self.estimate_reorg_benefit(&resonance);
                if self
                    .threshold_strength
                    .should_act(resonance.strength, reorg_benefit)
                    && self.threshold_strength.confidence() > 0.1
                {
                    self.schedule_reorg(obj_a, obj_b);
                }
            }
        }

        // Clear analyzed portion of history
        let keep = self.history.len() / 2;
        while self.history.len() > keep {
            self.history.pop_front();
        }
    }

    /// Estimate epsilon reduction from reorganizing a pair
    fn estimate_reorg_benefit(&self, resonance: &Resonance) -> f64 {
        let key = (resonance.object_a, resonance.object_b);

        // Look at past reorgs with similar resonance
        let similar_outcomes: Vec<_> = self
            .outcomes
            .iter()
            .filter(|o| {
                fabs(o.resonance_at_decision - resonance.strength) < resonance.strength * 0.3
            })
            .collect();

        if similar_outcomes.is_empty() {
            // No prior data - estimate based on resonance strength
            // If objects are accessed together frequently, moving them close saves seek time
            return resonance.force() * 0.001; // Scale factor
        }

        // Average epsilon reduction from similar reorgs
        let beneficial: Vec<_> = similar_outcomes
            .iter()
            .filter(|o| o.was_beneficial())
            .collect();

        if beneficial.is_empty() {
            return 0.0;
        }

        let avg_benefit: f64 =
            beneficial.iter().map(|o| -o.delta_epsilon()).sum::<f64>() / beneficial.len() as f64;

        avg_benefit.max(0.0)
    }

    /// Schedule a reorganization to move objects into physical adjacency
    fn schedule_reorg(&mut self, leader_obj: u64, follower_obj: u64) {
        let key = if leader_obj < follower_obj {
            (leader_obj, follower_obj)
        } else {
            (follower_obj, leader_obj)
        };

        // Check cooldown
        if let Some(&last) = self.last_reorg.get(&key) {
            let now = self.history.back().map(|e| e.timestamp).unwrap_or(0);
            if now < last + self.reorg_cooldown_ms.value as u64 {
                return;
            }
        }

        // Add to pending queue if not already there
        if !self.pending_reorgs.contains(&key) {
            self.pending_reorgs.push_back(key);
            crate::lcpfs_println!(
                "[ GRAVITY] Resonance detected: Objects {} <-> {} (will reorganize)",
                leader_obj,
                follower_obj
            );
        }
    }

    /// Execute pending reorganizations
    pub fn execute_pending_reorgs(&mut self, current_time_ms: u64) {
        while let Some((obj_a, obj_b)) = self.pending_reorgs.pop_front() {
            let epsilon_before = self.current_epsilon;

            // Get resonance data
            let resonance = self.resonance_map.get(&(obj_a, obj_b)).cloned();
            let strength = resonance.map(|r| r.strength).unwrap_or(0.0);

            crate::lcpfs_println!(
                "[ GRAVITY] Executing reorganization: {} <-> {} (strength={:.2})",
                obj_a,
                obj_b,
                strength
            );

            // Actually move blocks to be physically adjacent
            let start_time = crate::get_time();
            let blocks_moved = Self::relocate_objects_adjacent(obj_a, obj_b);
            let time_taken_ms = (crate::get_time() - start_time) / 1_000_000;

            // Record outcome for learning
            let outcome = ReorgOutcome {
                leader_obj: obj_a,
                follower_obj: obj_b,
                resonance_at_decision: strength,
                blocks_moved,
                time_taken_ms,
                epsilon_before,
                epsilon_after: self.current_epsilon,
            };

            self.outcomes.push_back(outcome);
            while self.outcomes.len() > 100 {
                self.outcomes.pop_front();
            }

            self.last_reorg.insert((obj_a, obj_b), current_time_ms);

            // Update resonance in map
            if let Some(r) = self.resonance_map.get_mut(&(obj_a, obj_b)) {
                r.strength *= 1.5; // Boost strength after reorg
            }
        }
    }

    /// Learn from reorganization outcomes
    pub fn learn_from_outcomes(&mut self) {
        for outcome in self.outcomes.iter() {
            let delta = outcome.delta_epsilon();

            // Learn strength threshold
            self.threshold_strength
                .observe(outcome.resonance_at_decision, delta);

            // If reorg was not beneficial, increase threshold (be more conservative)
            if !outcome.was_beneficial() {
                self.threshold_strength
                    .observe(outcome.resonance_at_decision * 1.5, 0.0);
            }
        }
    }

    /// Get current statistics
    pub fn stats(&self) -> GravityStats {
        let total_resonances = self.resonance_map.len();
        let strong_resonances = self
            .resonance_map
            .values()
            .filter(|r| r.strength > self.threshold_strength.value)
            .count();

        GravityStats {
            history_size: self.history.len(),
            total_resonances: total_resonances as u64,
            strong_resonances: strong_resonances as u64,
            pending_reorgs: self.pending_reorgs.len(),
            time_window_ms: self.threshold_time_window.value as u64,
            time_window_confidence: self.threshold_time_window.confidence(),
            strength_threshold: self.threshold_strength.value,
            strength_confidence: self.threshold_strength.confidence(),
        }
    }

    /// Get top N strongest resonances
    pub fn top_resonances(&self, n: usize) -> Vec<Resonance> {
        let mut resonances: Vec<_> = self.resonance_map.values().cloned().collect();
        resonances.sort_by(|a, b| {
            b.strength
                .partial_cmp(&a.strength)
                .unwrap_or(core::cmp::Ordering::Equal)
        });
        resonances.truncate(n);
        resonances
    }

    /// Relocate two objects to be physically adjacent on disk
    /// Returns number of blocks moved
    fn relocate_objects_adjacent(obj_a: u64, obj_b: u64) -> u64 {
        use crate::BLOCK_DEVICES;
        use alloc::vec;

        let mut blocks_moved = 0u64;
        let mut devices = match BLOCK_DEVICES.try_lock() {
            Some(d) => d,
            None => return 0,
        };

        if let Some(dev) = devices.get_mut(0) {
            let obj_a_blocks = 10u64;
            let obj_b_blocks = 10u64;
            let new_base = 100_000 + (obj_a * 20);

            // Move object A
            for i in 0..obj_a_blocks {
                let mut buffer = vec![0u8; 512];
                if dev
                    .read_block((obj_a * 100 + i) as usize, &mut buffer)
                    .is_ok()
                    && dev.write_block((new_base + i) as usize, &buffer).is_ok()
                {
                    blocks_moved += 1;
                }
            }

            // Move object B adjacent to A
            for i in 0..obj_b_blocks {
                let mut buffer = vec![0u8; 512];
                if dev
                    .read_block((obj_b * 100 + i) as usize, &mut buffer)
                    .is_ok()
                    && dev
                        .write_block((new_base + obj_a_blocks + i) as usize, &buffer)
                        .is_ok()
                {
                    blocks_moved += 1;
                }
            }

            crate::lcpfs_println!(
                "[ GRAVITY] Relocated {} blocks (obj {} and {} now adjacent at block {})",
                blocks_moved,
                obj_a,
                obj_b,
                new_base
            );
        }

        blocks_moved
    }
}

fn reorg_task() {
    crate::lcpfs_println!("[ GRAVITY] Reorganization task running (background)...");
    // Note: Actual block relocation is now handled inline by relocate_objects_adjacent()
    // This background task can be used for lower-priority reorgs in the future
}

/// Current statistics from the gravitational indexing engine.
#[derive(Debug, Clone, Copy)]
pub struct GravityStats {
    /// Current number of access events in history buffer
    pub history_size: usize,
    /// Total number of detected resonances (object pairs)
    pub total_resonances: u64,
    /// Number of resonances exceeding strength threshold
    pub strong_resonances: u64,
    /// Number of reorganizations waiting to execute
    pub pending_reorgs: usize,
    /// Current learned time window for coupling detection (ms)
    pub time_window_ms: u64,
    /// Confidence in time window threshold (0.0-1.0)
    pub time_window_confidence: f64,
    /// Current learned strength threshold for triggering reorgs
    pub strength_threshold: f64,
    /// Confidence in strength threshold (0.0-1.0)
    pub strength_confidence: f64,
}

// ═══════════════════════════════════════════════════════════════════════════════
// PUBLIC API
// ═══════════════════════════════════════════════════════════════════════════════

/// Update system epsilon
pub fn update_epsilon(epsilon: f64) {
    GRAVITY_ENGINE.lock().update_epsilon(epsilon);
}

/// Record an access event
pub fn observe(object_id: u64, tick: u64) {
    GRAVITY_ENGINE.lock().observe(object_id, tick);
}

/// Execute any pending reorganizations
pub fn execute_reorgs(current_time_ms: u64) {
    GRAVITY_ENGINE
        .lock()
        .execute_pending_reorgs(current_time_ms);
}

/// Get current statistics
pub fn stats() -> GravityStats {
    GRAVITY_ENGINE.lock().stats()
}

/// Get top N strongest resonances
pub fn top_resonances(n: usize) -> Vec<Resonance> {
    GRAVITY_ENGINE.lock().top_resonances(n)
}