condor_core/

budget.rs

//! Optional wall-clock and expansion budgets for online search requests.
//!
//! Budgets are **caller-supplied** and **unlimited by default**. When a limit is
//! hit mid-search, owners return domain `Err(…BudgetExhausted…)` rather than
//! [`crate::SearchOutcome::NoPath`]: the search did not prove unreachability.
//!
//! Prepared preprocess budgets (for example prepared any-angle node/edge caps)
//! remain separate fail-closed build limits in owner crates.

use std::time::{Duration, Instant};

/// Caller-chosen expansion and/or wall-clock limits for one search.
///
/// Both fields are independent optional caps. Default / [`Self::UNLIMITED`] means
/// the solver runs until found, no-path, or an owner-defined hard stop.
#[derive(Debug, Clone, Copy, PartialEq, Eq, Default)]
pub struct SearchBudget {
    /// Maximum algorithm-defined expansions (see lane `visited_nodes` docs).
    ///
    /// When set, the solver may expand at most this many nodes. Finding the goal
    /// on the last allowed expansion still returns found.
    pub max_expansions: Option<usize>,
    /// Maximum wall-clock duration measured from search start ([`BudgetWatch::start`]).
    pub max_duration: Option<Duration>,
}

impl SearchBudget {
    /// No expansion or wall-clock limit.
    pub const UNLIMITED: Self = Self {
        max_expansions: None,
        max_duration: None,
    };

    /// Expansion-only budget.
    #[must_use]
    pub const fn max_expansions(limit: usize) -> Self {
        Self {
            max_expansions: Some(limit),
            max_duration: None,
        }
    }

    /// Wall-clock-only budget.
    #[must_use]
    pub const fn max_duration(limit: Duration) -> Self {
        Self {
            max_expansions: None,
            max_duration: Some(limit),
        }
    }

    /// Sets [`Self::max_expansions`], preserving any duration limit.
    #[must_use]
    pub const fn with_max_expansions(mut self, limit: usize) -> Self {
        self.max_expansions = Some(limit);
        self
    }

    /// Sets [`Self::max_duration`], preserving any expansion limit.
    #[must_use]
    pub const fn with_max_duration(mut self, limit: Duration) -> Self {
        self.max_duration = Some(limit);
        self
    }

    /// Whether both caps are unset.
    #[must_use]
    pub const fn is_unlimited(&self) -> bool {
        self.max_expansions.is_none() && self.max_duration.is_none()
    }
}

/// Why a search stopped for budget rather than completing found/no-path.
#[derive(Debug, Clone, Copy, PartialEq, Eq)]
#[non_exhaustive]
pub enum BudgetExhausted {
    /// Expansion count reached the configured [`SearchBudget::max_expansions`].
    Expansions {
        /// Configured expansion limit.
        limit: usize,
        /// Expansions performed when the limit was hit.
        expansions: usize,
    },
    /// Wall-clock time reached the configured [`SearchBudget::max_duration`].
    Duration {
        /// Configured duration limit.
        limit: Duration,
    },
}

impl std::fmt::Display for BudgetExhausted {
    fn fmt(&self, formatter: &mut std::fmt::Formatter<'_>) -> std::fmt::Result {
        match self {
            Self::Expansions { limit, expansions } => write!(
                formatter,
                "search budget exhausted after {expansions} expansions (limit {limit})"
            ),
            Self::Duration { limit } => {
                write!(formatter, "search budget exhausted after {limit:?}")
            }
        }
    }
}

impl std::error::Error for BudgetExhausted {}

/// One-shot wall-clock deadline for a single search invocation.
///
/// Create with [`BudgetWatch::start`] at the beginning of `search` and call
/// [`BudgetWatch::check`] after each counted expansion when the node is not the
/// goal (or before continuing after an expansion that did not finish the search).
#[derive(Debug, Clone, Copy)]
pub struct BudgetWatch {
    budget: SearchBudget,
    deadline: Option<Instant>,
}

impl BudgetWatch {
    /// Captures the wall-clock deadline for `budget` (if any).
    #[must_use]
    pub fn start(budget: SearchBudget) -> Self {
        let deadline = budget.max_duration.map(|limit| Instant::now() + limit);
        Self { budget, deadline }
    }

    /// Returns the budget this watch was started with.
    #[must_use]
    pub const fn budget(&self) -> SearchBudget {
        self.budget
    }

    /// Fast path when both caps are unset.
    #[must_use]
    pub const fn is_unlimited(&self) -> bool {
        self.budget.is_unlimited()
    }

    /// Checks expansion and wall-clock caps against the work done so far.
    ///
    /// Call after incrementing the expansion counter when the search has not yet
    /// terminated as found. Unlimited budgets always return `Ok(())`.
    ///
    /// Expansion semantics: after `expansions` counted nodes, if
    /// `expansions >= max_expansions` the budget is exhausted (the caller should
    /// only invoke this when the current node is not an accepted goal).
    pub fn check(&self, expansions: usize) -> Result<(), BudgetExhausted> {
        if let Some(limit) = self.budget.max_expansions
            && expansions >= limit
        {
            return Err(BudgetExhausted::Expansions { limit, expansions });
        }
        if let (Some(deadline), Some(limit)) = (self.deadline, self.budget.max_duration)
            && Instant::now() >= deadline
        {
            return Err(BudgetExhausted::Duration { limit });
        }
        Ok(())
    }

    /// Whether any budget limit is configured (used to skip watch setup cost).
    #[must_use]
    pub const fn has_limits(&self) -> bool {
        !self.budget.is_unlimited()
    }
}

#[cfg(test)]
mod tests {
    use super::{BudgetExhausted, BudgetWatch, SearchBudget};
    use std::time::Duration;

    #[test]
    fn unlimited_watch_never_exhausts() {
        let watch = BudgetWatch::start(SearchBudget::UNLIMITED);
        assert!(watch.check(0).is_ok());
        assert!(watch.check(usize::MAX).is_ok());
    }

    #[test]
    fn expansion_limit_trips_at_limit() {
        let watch = BudgetWatch::start(SearchBudget::max_expansions(3));
        assert!(watch.check(2).is_ok());
        assert_eq!(
            watch.check(3),
            Err(BudgetExhausted::Expansions {
                limit: 3,
                expansions: 3
            })
        );
    }

    #[test]
    fn duration_limit_trips_after_deadline() {
        let watch = BudgetWatch::start(SearchBudget::max_duration(Duration::from_millis(0)));
        // Zero-duration deadline is already due once Instant advances past start.
        let result = watch.check(0);
        assert!(matches!(result, Err(BudgetExhausted::Duration { .. })));
    }
}