footing 0.3.1

Feature-gated foundations for Rust backend services
Documentation
//! Bounded in-memory token-bucket storage.

use std::{
    collections::HashMap,
    fmt,
    hash::Hash,
    sync::Mutex,
    time::{Duration, Instant},
};

use async_trait::async_trait;

use super::model::{
    DEFAULT_MAX_RATE_LIMIT_BUCKETS, RateLimitConfig, RateLimitDecision, RateLimitError,
};

#[derive(Debug, Clone)]
struct Bucket {
    tokens: u32,
    refill_at: Instant,
    last_seen: Instant,
}

impl Bucket {
    fn new(config: RateLimitConfig, now: Instant) -> Self {
        Self {
            tokens: config.capacity(),
            refill_at: now,
            last_seen: now,
        }
    }

    fn decide(&mut self, config: RateLimitConfig, now: Instant) -> RateLimitDecision {
        self.refill(config, now);
        self.last_seen = self.last_seen.max(now);
        if self.tokens > 0 {
            self.tokens -= 1;
            RateLimitDecision::allowed(self.tokens)
        } else {
            let elapsed = now.saturating_duration_since(self.refill_at);
            let retry_after = config.refill_interval().saturating_sub(elapsed);
            RateLimitDecision::denied(retry_after)
        }
    }

    fn refill(&mut self, config: RateLimitConfig, now: Instant) {
        let elapsed = now.saturating_duration_since(self.refill_at);
        let intervals = elapsed.as_nanos() / config.refill_interval().as_nanos();
        if intervals == 0 {
            return;
        }

        let refill = u32::try_from(intervals)
            .unwrap_or(u32::MAX)
            .saturating_mul(config.refill_tokens());
        self.tokens = self.tokens.saturating_add(refill).min(config.capacity());
        let remainder = elapsed.as_nanos() % config.refill_interval().as_nanos();
        let remainder = Duration::new(
            (remainder / 1_000_000_000) as u64,
            (remainder % 1_000_000_000) as u32,
        );
        // The remainder cannot exceed elapsed, so this stays at or after refill_at.
        self.refill_at = now - remainder;
    }

    fn would_be_fully_refilled(&self, config: RateLimitConfig, now: Instant) -> bool {
        let elapsed = now.saturating_duration_since(self.refill_at);
        let intervals = elapsed.as_nanos() / config.refill_interval().as_nanos();
        let refill = u32::try_from(intervals)
            .unwrap_or(u32::MAX)
            .saturating_mul(config.refill_tokens());
        self.tokens.saturating_add(refill) >= config.capacity()
    }
}

#[non_exhaustive]
/// Bounded token buckets sharing one immutable rate-limit configuration.
///
/// Use a separate limiter for each policy. Excess keys share one overflow
/// bucket so memory remains bounded even when clients supply many unique keys.
pub struct TokenBucketRateLimiter<K> {
    config: RateLimitConfig,
    max_buckets: usize,
    state: Mutex<BucketState<K>>,
}

struct BucketState<K> {
    buckets: HashMap<K, Bucket>,
    overflow_bucket: Option<Bucket>,
    last_capacity_prune: Option<Instant>,
}

impl<K> fmt::Debug for TokenBucketRateLimiter<K> {
    fn fmt(&self, formatter: &mut fmt::Formatter<'_>) -> fmt::Result {
        formatter
            .debug_struct("TokenBucketRateLimiter")
            .field("config", &self.config)
            .field("max_buckets", &self.max_buckets)
            .field(
                "bucket_count",
                &self.state.try_lock().ok().map(|state| state.buckets.len()),
            )
            .finish_non_exhaustive()
    }
}

#[async_trait]
/// Atomic token-bucket decisions and explicit idle-state cleanup.
pub trait RateLimitStore: Send + Sync {
    /// Consumes one token for `key`, or reports when a token will be available.
    ///
    /// Stores bound to one policy must reject incompatible `config` values
    /// without changing bucket state. Callers should supply monotonic `now` values.
    async fn check(
        &self,
        key: String,
        config: RateLimitConfig,
        now: Instant,
    ) -> Result<RateLimitDecision, RateLimitError>;

    /// Removes buckets last used before `older_than` and returns their count.
    ///
    /// Removing an exhausted bucket resets its allowance on its next request;
    /// callers must choose an idle threshold consistent with their policy.
    async fn prune_idle(&self, older_than: Instant) -> Result<usize, RateLimitError>;
}

#[async_trait]
impl RateLimitStore for TokenBucketRateLimiter<String> {
    async fn check(
        &self,
        key: String,
        config: RateLimitConfig,
        now: Instant,
    ) -> Result<RateLimitDecision, RateLimitError> {
        self.check_at_with_config(key, config, now)
    }

    async fn prune_idle(&self, older_than: Instant) -> Result<usize, RateLimitError> {
        self.prune_idle(older_than)
    }
}

impl<K> TokenBucketRateLimiter<K>
where
    K: Eq + Hash,
{
    /// Creates a limiter with the default bucket bound.
    #[must_use]
    pub fn new(config: RateLimitConfig) -> Self {
        Self {
            config,
            max_buckets: DEFAULT_MAX_RATE_LIMIT_BUCKETS,
            state: Mutex::new(BucketState {
                buckets: HashMap::new(),
                overflow_bucket: None,
                last_capacity_prune: None,
            }),
        }
    }

    /// Creates a limiter with a nonzero bound on individually tracked keys.
    ///
    /// One additional shared overflow bucket handles keys beyond this bound.
    pub fn with_max_buckets(
        config: RateLimitConfig,
        max_buckets: usize,
    ) -> Result<Self, RateLimitError> {
        if max_buckets == 0 {
            return Err(RateLimitError::InvalidMaxBuckets);
        }
        Ok(Self {
            config,
            max_buckets,
            state: Mutex::new(BucketState {
                buckets: HashMap::new(),
                overflow_bucket: None,
                last_capacity_prune: None,
            }),
        })
    }

    #[must_use]
    /// Returns the config.
    pub const fn config(&self) -> RateLimitConfig {
        self.config
    }

    #[must_use]
    /// Returns the maximum buckets.
    pub const fn max_buckets(&self) -> usize {
        self.max_buckets
    }

    /// Returns the bucket count.
    pub fn bucket_count(&self) -> Result<usize, RateLimitError> {
        self.state
            .lock()
            .map(|state| state.buckets.len())
            .map_err(|_| RateLimitError::LockPoisoned)
    }

    /// Consumes one token for `key` using the current monotonic time.
    pub fn check(&self, key: K) -> Result<RateLimitDecision, RateLimitError> {
        self.check_at(key, Instant::now())
    }

    /// Evaluates a key at an explicitly supplied instant.
    pub fn check_at(&self, key: K, now: Instant) -> Result<RateLimitDecision, RateLimitError> {
        self.check_at_with_config(key, self.config, now)
    }

    /// Evaluates a key using an explicit configuration and instant.
    ///
    /// Returns [`RateLimitError::ConfigMismatch`] without mutating state if
    /// `config` differs from the construction-time policy. Use separate limiter
    /// instances for different policies, including when sharing a key source.
    pub fn check_at_with_config(
        &self,
        key: K,
        config: RateLimitConfig,
        now: Instant,
    ) -> Result<RateLimitDecision, RateLimitError> {
        if config != self.config {
            return Err(RateLimitError::ConfigMismatch);
        }
        let mut state = self
            .state
            .lock()
            .map_err(|_| RateLimitError::LockPoisoned)?;
        if state.buckets.len() >= self.max_buckets && !state.buckets.contains_key(&key) {
            let should_prune = state.last_capacity_prune.is_none_or(|last_prune| {
                now.saturating_duration_since(last_prune) >= config.refill_interval()
            });
            if should_prune {
                state.last_capacity_prune = Some(now);
                state
                    .buckets
                    .retain(|_, bucket| !bucket.would_be_fully_refilled(config, now));
            }
            if state.buckets.len() >= self.max_buckets {
                return Ok(state
                    .overflow_bucket
                    .get_or_insert_with(|| Bucket::new(config, now))
                    .decide(config, now));
            }
            state.overflow_bucket = None;
        }

        Ok(state
            .buckets
            .entry(key)
            .or_insert_with(|| Bucket::new(config, now))
            .decide(config, now))
    }

    /// Removes individually tracked buckets last used before `older_than`.
    ///
    /// Returns the number removed. If capacity becomes available, the overflow
    /// bucket is also cleared. This intentionally resets those allowances; use
    /// a threshold long enough for the policy's full refill period.
    pub fn prune_idle(&self, older_than: Instant) -> Result<usize, RateLimitError> {
        let mut state = self
            .state
            .lock()
            .map_err(|_| RateLimitError::LockPoisoned)?;
        let before = state.buckets.len();
        state
            .buckets
            .retain(|_, bucket| bucket.last_seen >= older_than);
        if state.buckets.len() < self.max_buckets {
            state.overflow_bucket = None;
        }
        Ok(before - state.buckets.len())
    }
}