footing 0.1.4

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 = 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 refill_elapsed = multiply_duration(config.refill_interval(), intervals);
        self.refill_at = self.refill_at.checked_add(refill_elapsed).unwrap_or(now);
    }

    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]
/// Represents token bucket rate limiter.
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]
/// Storage abstraction for rate limit.
pub trait RateLimitStore: Send + Sync {
    /// Evaluates this check.
    async fn check(
        &self,
        key: String,
        config: RateLimitConfig,
        now: Instant,
    ) -> Result<RateLimitDecision, RateLimitError>;

    /// Returns the prune idle.
    async fn prune_idle(&self, older_than: Instant) -> Result<usize, RateLimitError>;
}

#[derive(Debug)]
#[non_exhaustive]
/// Storage abstraction for memory rate limit.
pub struct MemoryRateLimitStore {
    limiter: TokenBucketRateLimiter<String>,
}

impl MemoryRateLimitStore {
    /// Creates an in-memory store.
    #[must_use]
    pub fn new(config: RateLimitConfig) -> Self {
        Self {
            limiter: TokenBucketRateLimiter::new(config),
        }
    }

    #[must_use]
    /// Returns the limiter.
    pub const fn limiter(&self) -> &TokenBucketRateLimiter<String> {
        &self.limiter
    }
}

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

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

impl<K> TokenBucketRateLimiter<K>
where
    K: Eq + Hash + Clone,
{
    /// 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,
            }),
        }
    }

    /// Configures maximum buckets and returns the updated value.
    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)
    }

    /// Evaluates this check.
    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.
    pub fn check_at_with_config(
        &self,
        key: K,
        config: RateLimitConfig,
        now: Instant,
    ) -> Result<RateLimitDecision, RateLimitError> {
        let mut state = self
            .state
            .lock()
            .map_err(|_| RateLimitError::LockPoisoned)?;
        if !state.buckets.contains_key(&key) {
            if state.buckets.len() >= self.max_buckets {
                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;
            }
            state.buckets.insert(key.clone(), Bucket::new(config, now));
        }

        state
            .buckets
            .get_mut(&key)
            .map(|bucket| bucket.decide(config, now))
            .ok_or(RateLimitError::StoreUnavailable)
    }

    /// Returns the prune idle.
    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())
    }
}

fn multiply_duration(duration: Duration, multiplier: u128) -> Duration {
    let nanos = duration.as_nanos().saturating_mul(multiplier);
    Duration::from_nanos(u64::try_from(nanos).unwrap_or(u64::MAX))
}