use std::sync::{Arc, Mutex};
use std::time::{Duration, Instant, SystemTime, UNIX_EPOCH};
use reqwest::header::HeaderMap;
use crate::clock::Clock;
use crate::error::{MAX_SERVER_WAIT, header, server_secs};
#[derive(Debug, Clone, PartialEq)]
pub struct RateLimitState {
pub requests_per_minute: f64,
pub tokens: f64,
pub blocked_for: Duration,
}
pub(crate) struct RateLimiter {
state: Mutex<Bucket>,
clock: Arc<dyn Clock>,
}
struct Bucket {
rpm: f64,
cap: f64,
tokens: f64,
last: Instant,
blocked_until: Option<Instant>,
}
impl RateLimiter {
pub(crate) fn new(rpm: u32, clock: Arc<dyn Clock>) -> Self {
Self::with_cap(rpm as f64, rpm as f64, clock)
}
pub(crate) fn per_second(per_second: f64, clock: Arc<dyn Clock>) -> Self {
Self::with_cap(per_second * 60.0, per_second, clock)
}
fn with_cap(rpm: f64, cap: f64, clock: Arc<dyn Clock>) -> Self {
let now = clock.now();
RateLimiter {
state: Mutex::new(Bucket {
rpm,
cap,
tokens: cap,
last: now,
blocked_until: None,
}),
clock,
}
}
pub(crate) fn state(&self) -> RateLimitState {
let now = self.clock.now();
let mut b = self.state.lock().unwrap();
b.refill(now);
RateLimitState {
requests_per_minute: b.rpm,
tokens: b.tokens,
blocked_for: b
.blocked_until
.map(|u| u.saturating_duration_since(now))
.unwrap_or_default(),
}
}
pub(crate) async fn acquire(&self, cost: u32) {
let cost = cost as f64;
loop {
let wait = {
let now = self.clock.now();
let mut b = self.state.lock().unwrap();
b.refill(now);
let need = cost.min(b.cap);
match b.blocked_until {
Some(u) if now < u => u - now,
_ if b.tokens + 1e-9 >= need => {
b.tokens -= cost;
return;
}
_ => {
let per_token = 60.0 / b.rpm;
server_secs((need - b.tokens) * per_token)
.filter(|d| !d.is_zero())
.unwrap_or(Duration::from_millis(1))
.min(MAX_SERVER_WAIT)
}
}
};
self.clock.sleep(wait).await;
}
}
pub(crate) fn update(&self, headers: &HeaderMap) {
let now = self.clock.now();
let mut b = self.state.lock().unwrap();
b.refill(now);
if let Some(limit) = num(headers, "x-ratelimit-limit")
&& limit >= 1.0
&& limit < b.rpm
{
b.rpm = limit;
b.cap = b.cap.min(limit);
b.tokens = b.tokens.min(limit);
}
let Some(remaining) = num(headers, "x-ratelimit-remaining") else {
return;
};
if remaining >= 0.0 && remaining < b.tokens {
b.tokens = remaining;
}
if remaining == 0.0 {
let d = match num(headers, "x-ratelimit-reset") {
Some(reset) => reset_duration(reset),
None => server_secs(60.0 / b.rpm).unwrap_or(Duration::ZERO),
};
b.block(now, d);
}
}
pub(crate) fn block_for(&self, d: Duration) {
let now = self.clock.now();
self.state.lock().unwrap().block(now, d);
}
}
pub(crate) struct PlacementHold {
until: Mutex<Option<Instant>>,
clock: Arc<dyn Clock>,
}
impl PlacementHold {
pub(crate) fn new(clock: Arc<dyn Clock>) -> Self {
PlacementHold {
until: Mutex::new(None),
clock,
}
}
pub(crate) fn hold_for(&self, d: Duration) {
if d.is_zero() {
return;
}
let Some(until) = self.clock.now().checked_add(d.min(MAX_SERVER_WAIT)) else {
return;
};
let mut u = self.until.lock().unwrap();
if u.is_none_or(|cur| until > cur) {
*u = Some(until);
}
}
pub(crate) async fn wait(&self) {
loop {
let wait = {
let now = self.clock.now();
match *self.until.lock().unwrap() {
Some(u) if now < u => u - now,
_ => return,
}
};
self.clock.sleep(wait).await;
}
}
#[cfg(test)]
pub(crate) fn held_until(&self) -> Option<Instant> {
*self.until.lock().unwrap()
}
}
impl Bucket {
fn refill(&mut self, now: Instant) {
if now > self.last {
let elapsed = (now - self.last).as_secs_f64() / 60.0;
self.tokens = self.cap.min(self.tokens + elapsed * self.rpm);
self.last = now;
}
}
fn block(&mut self, now: Instant, d: Duration) {
if d.is_zero() {
return;
}
let Some(until) = now.checked_add(d.min(MAX_SERVER_WAIT)) else {
return;
};
if self.blocked_until.is_none_or(|u| until > u) {
self.blocked_until = Some(until);
}
}
}
fn reset_duration(reset: f64) -> Duration {
let now_ms = SystemTime::now()
.duration_since(UNIX_EPOCH)
.unwrap_or_default()
.as_millis() as f64;
let secs = if reset > 1e12 {
(reset - now_ms) / 1000.0
} else if reset > 1e9 {
reset - now_ms / 1000.0
} else {
reset
};
server_secs(secs).unwrap_or(Duration::ZERO)
}
fn num(headers: &HeaderMap, name: &str) -> Option<f64> {
header(headers, name)
.and_then(|v| v.parse::<f64>().ok())
.filter(|f| f.is_finite())
}
#[cfg(test)]
mod tests {
use super::*;
use crate::clock::FakeClock;
use reqwest::header::{HeaderName, HeaderValue};
fn headers(pairs: &[(&str, &str)]) -> HeaderMap {
let mut h = HeaderMap::new();
for (k, v) in pairs {
h.insert(
HeaderName::from_bytes(k.as_bytes()).unwrap(),
HeaderValue::from_str(v).unwrap(),
);
}
h
}
#[tokio::test]
async fn a_cost_above_the_bucket_leaves_a_debt() {
let clock = FakeClock::default();
let l = RateLimiter::per_second(3.0, Arc::new(clock.clone()));
l.acquire(5).await; assert!(clock.sleeps().is_empty());
l.acquire(1).await; assert_eq!(clock.sleeps(), vec![Duration::from_secs(1)]);
}
#[tokio::test]
async fn fractional_rates_never_sleep_zero() {
let clock = FakeClock::default();
let l = RateLimiter::new(7, Arc::new(clock.clone()));
for _ in 0..50 {
l.acquire(3).await;
}
let sleeps = clock.sleeps();
assert!(sleeps.len() < 60, "{}", sleeps.len());
assert!(sleeps.iter().all(|d| !d.is_zero()));
}
#[tokio::test]
async fn spends_tokens_then_waits() {
let clock = FakeClock::default();
let l = RateLimiter::new(60, Arc::new(clock.clone()));
for _ in 0..60 {
l.acquire(1).await;
}
assert!(clock.sleeps().is_empty());
l.acquire(1).await;
assert_eq!(clock.sleeps(), vec![Duration::from_secs(1)]);
}
#[tokio::test]
async fn adapts_to_headers_and_reset_seconds() {
let clock = FakeClock::default();
let l = RateLimiter::new(300, Arc::new(clock.clone()));
l.update(&headers(&[
("X-RateLimit-Limit", "120"),
("X-RateLimit-Remaining", "0"),
("X-RateLimit-Reset", "7"),
]));
let s = l.state();
assert_eq!(s.requests_per_minute, 120.0);
assert_eq!(s.blocked_for, Duration::from_secs(7));
l.acquire(1).await;
assert_eq!(clock.sleeps()[0], Duration::from_secs(7));
}
#[tokio::test]
async fn absurd_server_hints_never_panic_or_stall() {
let clock = FakeClock::default();
let l = RateLimiter::new(300, Arc::new(clock.clone()));
for (limit, reset) in [("1e-300", "1e300"), ("0.0001", "9999999999"), ("1", "1e20")] {
l.update(&headers(&[
("X-RateLimit-Limit", limit),
("X-RateLimit-Remaining", "0"),
("X-RateLimit-Reset", reset),
]));
}
l.block_for(Duration::MAX);
assert!(l.state().blocked_for <= MAX_SERVER_WAIT);
l.acquire(1).await;
l.acquire(1).await;
assert!(clock.sleeps().iter().all(|d| *d <= MAX_SERVER_WAIT));
}
#[tokio::test]
async fn never_raises_the_limit() {
let l = RateLimiter::new(100, Arc::new(FakeClock::default()));
l.update(&headers(&[("X-RateLimit-Limit", "600")]));
assert_eq!(l.state().requests_per_minute, 100.0);
}
}