haz-exec 0.1.0

//! Active mutex-hold tracking for the scheduler.
//!
//! [`HoldSet`] is the runtime data structure consulted by
//! [`crate::run_graph::run_graph`] when evaluating `EXEC-006`
//! condition 3 (mutex compatibility) post-lookup, and updated on
//! `MUTEX-006` acquire and release transitions.
//!
//! The [`HoldKey`] sum type encodes the `MUTEX-001` scope
//! distinction: a bare `mutex: db` declaration produces a
//! [`HoldKey::Workspace`] key, while `mutex: ~:db` in project `P`
//! produces a [`HoldKey::Project`] keyed by the bearing project.
//! The two are distinct keys even when the bare name coincides.
//!
//! Visibility is `pub(crate)`: the abstraction is internal to
//! `haz-exec` and not part of its public surface.

use std::collections::BTreeMap;

use haz_domain::mutex::{Mutex, MutexMode, MutexScope};
use haz_domain::name::{MutexName, ProjectName};

/// Identity of one (scope, name) lock the scheduler tracks.
///
/// Workspace-global mutexes (`mutex: <name>`) live under
/// [`HoldKey::Workspace`]; project-scoped mutexes
/// (`mutex: ~:<name>`) live under [`HoldKey::Project`] keyed by
/// the bearing project, per `MUTEX-001`.
#[allow(dead_code)]
#[derive(Debug, Clone, PartialEq, Eq, PartialOrd, Ord, Hash)]
pub(crate) enum HoldKey {
    /// Workspace-global lock. Two declarations in different
    /// projects sharing this name resolve to the same key.
    Workspace {
        /// Bare mutex name.
        name: MutexName,
    },
    /// Project-scoped lock. Two declarations in different
    /// projects sharing the same bare name resolve to DIFFERENT
    /// keys (project is part of the key).
    Project {
        /// Owning project of the bearing task.
        project: ProjectName,
        /// Bare mutex name.
        name: MutexName,
    },
}

#[allow(dead_code)]
impl HoldKey {
    /// Derive the hold key for a task that declares `mutex` and
    /// lives in `project`. Workspace-scope ignores the project;
    /// project-scope binds it (`MUTEX-001`).
    pub(crate) fn from_task(project: &ProjectName, mutex: &Mutex) -> Self {
        match mutex.scope {
            MutexScope::Workspace => Self::Workspace {
                name: mutex.name.clone(),
            },
            MutexScope::Project => Self::Project {
                project: project.clone(),
                name: mutex.name.clone(),
            },
        }
    }
}

/// Active mutex holds owned by the scheduler's local state.
///
/// Each entry maps a [`HoldKey`] to the list of modes currently
/// held against it. The compatibility-matrix invariant
/// (`MUTEX-003` / `MUTEX-004`) keeps the per-key list in one of
/// three states at all times:
///
/// - Empty (no holders; entry absent from the map).
/// - Exactly one [`MutexMode::Exclusive`] entry.
/// - One or more [`MutexMode::Shared`] entries.
///
/// The invariant is preserved by [`Self::acquire`] refusing to
/// fire when [`Self::compatible`] would return `false`; the
/// scheduler MUST check compatibility before acquiring.
#[allow(dead_code)]
#[derive(Debug, Default, Clone)]
pub(crate) struct HoldSet {
    by_key: BTreeMap<HoldKey, Vec<MutexMode>>,
}

#[allow(dead_code)]
impl HoldSet {
    /// Return `true` iff acquiring `task_mutex` for a task in
    /// `task_project` would respect `MUTEX-003` / `MUTEX-004`
    /// given the current hold set. A `None` mutex is trivially
    /// compatible.
    pub(crate) fn compatible(
        &self,
        task_project: &ProjectName,
        task_mutex: Option<&Mutex>,
    ) -> bool {
        let Some(m) = task_mutex else {
            return true;
        };
        let key = HoldKey::from_task(task_project, m);
        let Some(holders) = self.by_key.get(&key) else {
            return true;
        };
        if holders.is_empty() {
            return true;
        }
        match m.mode {
            MutexMode::Exclusive => false,
            MutexMode::Shared => holders.iter().all(|h| *h == MutexMode::Shared),
        }
    }

    /// Record one hold against `task_mutex`'s key
    /// (`MUTEX-006` "hold lifetime begins at spawn time").
    /// A `None` mutex is a no-op.
    ///
    /// The scheduler MUST call [`Self::compatible`] first;
    /// calling `acquire` against an incompatible state would
    /// violate the invariant the type tracks.
    pub(crate) fn acquire(&mut self, task_project: &ProjectName, task_mutex: Option<&Mutex>) {
        let Some(m) = task_mutex else {
            return;
        };
        let key = HoldKey::from_task(task_project, m);
        self.by_key.entry(key).or_default().push(m.mode);
    }

    /// Drop one matching hold against `task_mutex`'s key
    /// (`MUTEX-006` release at command termination). A `None`
    /// mutex is a no-op. Release of a key with no matching mode
    /// is a no-op (defensive against double-release).
    pub(crate) fn release(&mut self, task_project: &ProjectName, task_mutex: Option<&Mutex>) {
        let Some(m) = task_mutex else {
            return;
        };
        let key = HoldKey::from_task(task_project, m);
        if let Some(holders) = self.by_key.get_mut(&key)
            && let Some(pos) = holders.iter().position(|h| *h == m.mode)
        {
            holders.swap_remove(pos);
            if holders.is_empty() {
                self.by_key.remove(&key);
            }
        }
    }
}

#[cfg(test)]
mod tests {
    use std::str::FromStr;

    use haz_domain::mutex::{Mutex, MutexMode, MutexScope};
    use haz_domain::name::{MutexName, ProjectName};

    use super::{HoldKey, HoldSet};

    // ---- fixtures ----

    fn project(s: &str) -> ProjectName {
        ProjectName::from_str(s).unwrap()
    }
    fn mname(s: &str) -> MutexName {
        MutexName::from_str(s).unwrap()
    }

    fn workspace_mutex(name: &str, mode: MutexMode) -> Mutex {
        Mutex {
            scope: MutexScope::Workspace,
            name: mname(name),
            mode,
        }
    }
    fn project_mutex(name: &str, mode: MutexMode) -> Mutex {
        Mutex {
            scope: MutexScope::Project,
            name: mname(name),
            mode,
        }
    }

    // ---- HoldKey::from_task ----

    #[test]
    fn hold_key_from_task_workspace_scope() {
        let p = project("p1");
        let m = workspace_mutex("db", MutexMode::Exclusive);
        assert_eq!(
            HoldKey::from_task(&p, &m),
            HoldKey::Workspace { name: mname("db") },
        );
    }

    #[test]
    fn hold_key_from_task_project_scope_binds_bearing_project() {
        let p = project("p1");
        let m = project_mutex("db", MutexMode::Exclusive);
        assert_eq!(
            HoldKey::from_task(&p, &m),
            HoldKey::Project {
                project: project("p1"),
                name: mname("db"),
            },
        );
    }

    #[test]
    fn workspace_and_project_scope_same_name_are_distinct_keys() {
        let p = project("p1");
        let w = workspace_mutex("db", MutexMode::Exclusive);
        let pr = project_mutex("db", MutexMode::Exclusive);
        assert_ne!(HoldKey::from_task(&p, &w), HoldKey::from_task(&p, &pr));
    }

    #[test]
    fn project_scope_same_name_different_projects_are_distinct_keys() {
        let m = project_mutex("db", MutexMode::Exclusive);
        assert_ne!(
            HoldKey::from_task(&project("p1"), &m),
            HoldKey::from_task(&project("p2"), &m),
        );
    }

    #[test]
    fn workspace_scope_ignores_bearing_project() {
        let m = workspace_mutex("db", MutexMode::Exclusive);
        assert_eq!(
            HoldKey::from_task(&project("p1"), &m),
            HoldKey::from_task(&project("p2"), &m),
        );
    }

    // ---- empty set compatibility ----

    #[test]
    fn empty_set_compatible_with_none_mutex() {
        let hs = HoldSet::default();
        assert!(hs.compatible(&project("p"), None));
    }

    #[test]
    fn empty_set_compatible_with_workspace_exclusive() {
        let hs = HoldSet::default();
        let m = workspace_mutex("db", MutexMode::Exclusive);
        assert!(hs.compatible(&project("p"), Some(&m)));
    }

    #[test]
    fn empty_set_compatible_with_workspace_shared() {
        let hs = HoldSet::default();
        let m = workspace_mutex("db", MutexMode::Shared);
        assert!(hs.compatible(&project("p"), Some(&m)));
    }

    #[test]
    fn empty_set_compatible_with_project_exclusive() {
        let hs = HoldSet::default();
        let m = project_mutex("db", MutexMode::Exclusive);
        assert!(hs.compatible(&project("p"), Some(&m)));
    }

    #[test]
    fn empty_set_compatible_with_project_shared() {
        let hs = HoldSet::default();
        let m = project_mutex("db", MutexMode::Shared);
        assert!(hs.compatible(&project("p"), Some(&m)));
    }

    // ---- MUTEX-001 scope isolation ----

    #[test]
    fn workspace_db_does_not_block_project_db_in_same_project() {
        let mut hs = HoldSet::default();
        let w = workspace_mutex("db", MutexMode::Exclusive);
        hs.acquire(&project("p1"), Some(&w));
        let pr = project_mutex("db", MutexMode::Exclusive);
        assert!(hs.compatible(&project("p1"), Some(&pr)));
    }

    #[test]
    fn workspace_db_held_blocks_workspace_db_in_any_project() {
        let mut hs = HoldSet::default();
        let m = workspace_mutex("db", MutexMode::Exclusive);
        hs.acquire(&project("p1"), Some(&m));
        assert!(!hs.compatible(&project("p2"), Some(&m)));
    }

    #[test]
    fn project_db_in_p1_does_not_block_project_db_in_p2() {
        let mut hs = HoldSet::default();
        let m = project_mutex("db", MutexMode::Exclusive);
        hs.acquire(&project("p1"), Some(&m));
        assert!(hs.compatible(&project("p2"), Some(&m)));
    }

    // ---- MUTEX-003 exclusive blocks ----

    #[test]
    fn mutex_003_exclusive_blocks_incoming_exclusive() {
        let mut hs = HoldSet::default();
        let m = workspace_mutex("db", MutexMode::Exclusive);
        hs.acquire(&project("p"), Some(&m));
        assert!(!hs.compatible(&project("p"), Some(&m)));
    }

    #[test]
    fn mutex_003_exclusive_blocks_incoming_shared() {
        let mut hs = HoldSet::default();
        let excl = workspace_mutex("db", MutexMode::Exclusive);
        let shrd = workspace_mutex("db", MutexMode::Shared);
        hs.acquire(&project("p"), Some(&excl));
        assert!(!hs.compatible(&project("p"), Some(&shrd)));
    }

    // ---- MUTEX-004 shared semantics ----

    #[test]
    fn mutex_004_shared_blocks_incoming_exclusive() {
        let mut hs = HoldSet::default();
        let shrd = workspace_mutex("db", MutexMode::Shared);
        let excl = workspace_mutex("db", MutexMode::Exclusive);
        hs.acquire(&project("p"), Some(&shrd));
        assert!(!hs.compatible(&project("p"), Some(&excl)));
    }

    #[test]
    fn mutex_004_shared_compatible_with_shared() {
        let mut hs = HoldSet::default();
        let shrd = workspace_mutex("db", MutexMode::Shared);
        hs.acquire(&project("p"), Some(&shrd));
        assert!(hs.compatible(&project("p"), Some(&shrd)));
    }

    #[test]
    fn mutex_004_many_shared_holders_still_block_exclusive() {
        let mut hs = HoldSet::default();
        let shrd = workspace_mutex("db", MutexMode::Shared);
        let excl = workspace_mutex("db", MutexMode::Exclusive);
        hs.acquire(&project("p"), Some(&shrd));
        hs.acquire(&project("p"), Some(&shrd));
        hs.acquire(&project("p"), Some(&shrd));
        assert!(!hs.compatible(&project("p"), Some(&excl)));
    }

    // ---- acquire / release lifecycle ----

    #[test]
    fn mutex_006_release_decrements_shared_count() {
        let mut hs = HoldSet::default();
        let shrd = workspace_mutex("db", MutexMode::Shared);
        hs.acquire(&project("p"), Some(&shrd));
        hs.acquire(&project("p"), Some(&shrd));
        hs.release(&project("p"), Some(&shrd));
        // One shared holder remains; exclusive still blocked.
        let excl = workspace_mutex("db", MutexMode::Exclusive);
        assert!(!hs.compatible(&project("p"), Some(&excl)));
    }

    #[test]
    fn mutex_006_release_full_set_makes_exclusive_compatible() {
        let mut hs = HoldSet::default();
        let shrd = workspace_mutex("db", MutexMode::Shared);
        hs.acquire(&project("p"), Some(&shrd));
        hs.release(&project("p"), Some(&shrd));
        let excl = workspace_mutex("db", MutexMode::Exclusive);
        assert!(hs.compatible(&project("p"), Some(&excl)));
    }

    #[test]
    fn mutex_006_release_one_of_two_shared_leaves_exclusive_blocked() {
        let mut hs = HoldSet::default();
        let shrd = workspace_mutex("db", MutexMode::Shared);
        hs.acquire(&project("p"), Some(&shrd));
        hs.acquire(&project("p"), Some(&shrd));
        hs.release(&project("p"), Some(&shrd));
        let excl = workspace_mutex("db", MutexMode::Exclusive);
        assert!(!hs.compatible(&project("p"), Some(&excl)));
    }

    #[test]
    fn mutex_006_acquire_then_release_exclusive_round_trip() {
        let mut hs = HoldSet::default();
        let excl = workspace_mutex("db", MutexMode::Exclusive);
        hs.acquire(&project("p"), Some(&excl));
        assert!(!hs.compatible(&project("p"), Some(&excl)));
        hs.release(&project("p"), Some(&excl));
        assert!(hs.compatible(&project("p"), Some(&excl)));
    }

    #[test]
    fn none_mutex_acquire_is_noop() {
        let mut hs = HoldSet::default();
        hs.acquire(&project("p"), None);
        // Set is empty; any subsequent acquire on any key works.
        let m = workspace_mutex("db", MutexMode::Exclusive);
        assert!(hs.compatible(&project("p"), Some(&m)));
    }

    #[test]
    fn none_mutex_release_is_noop() {
        let mut hs = HoldSet::default();
        hs.release(&project("p"), None);
        let m = workspace_mutex("db", MutexMode::Exclusive);
        assert!(hs.compatible(&project("p"), Some(&m)));
    }

    #[test]
    fn release_of_nonexistent_key_is_noop() {
        let mut hs = HoldSet::default();
        let m = workspace_mutex("db", MutexMode::Exclusive);
        // Never acquired; releasing should not panic.
        hs.release(&project("p"), Some(&m));
        assert!(hs.compatible(&project("p"), Some(&m)));
    }

    #[test]
    fn release_more_than_acquired_does_not_underflow() {
        let mut hs = HoldSet::default();
        let m = workspace_mutex("db", MutexMode::Exclusive);
        hs.acquire(&project("p"), Some(&m));
        hs.release(&project("p"), Some(&m));
        hs.release(&project("p"), Some(&m));
        // Second release on empty key is a no-op; subsequent
        // acquire still succeeds cleanly.
        assert!(hs.compatible(&project("p"), Some(&m)));
        hs.acquire(&project("p"), Some(&m));
        assert!(!hs.compatible(&project("p"), Some(&m)));
    }

    // ---- mixed scope interaction ----

    #[test]
    fn workspace_held_does_not_block_project_scope_same_name() {
        let mut hs = HoldSet::default();
        let w = workspace_mutex("db", MutexMode::Exclusive);
        let pr = project_mutex("db", MutexMode::Exclusive);
        hs.acquire(&project("p"), Some(&w));
        assert!(hs.compatible(&project("p"), Some(&pr)));
        hs.acquire(&project("p"), Some(&pr));
        // Releasing workspace leaves project hold intact.
        hs.release(&project("p"), Some(&w));
        assert!(!hs.compatible(&project("p"), Some(&pr)));
    }
}