use std::sync::{Mutex, PoisonError};
use std::time::Duration;
use tokio::sync::Mutex as Queue;
use tokio::time::{Instant, sleep};
use super::no_updates::has;
use crate::errors::{Error, Result};
#[non_exhaustive]
#[derive(Clone, Copy, Debug, PartialEq, Eq, Hash)]
pub enum RateCategory {
Message,
Media,
Query,
Admin,
Bulk,
Account,
Global,
}
const CATEGORIES: usize = 7;
impl RateCategory {
pub fn of(name: &str) -> RateCategory {
let (namespace, method) = name.split_once('.').unwrap_or(("", name));
if namespace == "account" {
return RateCategory::Account;
}
let any = |words: &[&str]| words.iter().any(|word| has(method, word));
if any(&["Send", "Upload", "Edit", "Forward", "Save"]) {
let media = ["Media", "Photo", "Video", "Audio", "Document", "Animation", "Voice", "Sticker", "Round"];
return if any(&media) { RateCategory::Media } else { RateCategory::Message };
}
if any(&["GetDifference", "GetState", "Ping", "HttpWait"]) {
return RateCategory::Bulk;
}
if any(&["Delete", "Ban", "Kick", "Unban", "Promote", "Toggle", "Set", "Pin", "Report", "Block"]) {
return RateCategory::Admin;
}
RateCategory::Query
}
fn index(self) -> usize {
self as usize
}
}
#[derive(Clone, Debug, PartialEq)]
pub struct RateLimits {
limits: [(f64, f64); CATEGORIES],
}
impl Default for RateLimits {
fn default() -> Self {
RateLimits {
limits: [(20.0, 30.0), (5.0, 10.0), (30.0, 50.0), (15.0, 20.0), (3.0, 5.0), (10.0, 15.0), (30.0, 40.0)],
}
}
}
impl RateLimits {
#[must_use]
pub fn limit(mut self, category: RateCategory, rate: f64, burst: f64) -> Self {
self.limits[category.index()] = (rate, burst);
self
}
pub(crate) fn validate(&self) -> Result<()> {
self.limits.iter().try_for_each(|&(rate, burst)| check(rate, burst))
}
}
fn check(rate: f64, burst: f64) -> Result<()> {
if !rate.is_finite() || rate <= 0.0 {
return Err(Error::InvalidArgument("a rate limit must be a finite number above 0"));
}
if !burst.is_finite() || burst < 1.0 {
return Err(Error::InvalidArgument("a rate limit's burst must be at least 1"));
}
Ok(())
}
struct State {
tokens: f64,
rate: f64,
burst: f64,
last: Instant,
}
impl State {
fn refill(&mut self, now: Instant) {
let seconds = now.saturating_duration_since(self.last).as_secs_f64();
self.tokens = (self.tokens + seconds * self.rate).min(self.burst);
self.last = now;
}
}
struct Bucket {
state: Mutex<State>,
queue: Queue<()>,
}
impl Bucket {
fn new((rate, burst): (f64, f64)) -> Bucket {
let state = State { tokens: burst, rate, burst, last: Instant::now() };
Bucket { state: Mutex::new(state), queue: Queue::new(()) }
}
fn state(&self) -> std::sync::MutexGuard<'_, State> {
self.state.lock().unwrap_or_else(PoisonError::into_inner)
}
fn try_take(&self) -> Result<(), Duration> {
let mut state = self.state();
state.refill(Instant::now());
if state.tokens >= 1.0 {
state.tokens -= 1.0;
return Ok(());
}
let wait = Duration::try_from_secs_f64((1.0 - state.tokens) / state.rate).unwrap_or(Duration::MAX);
Err(wait.max(Duration::from_micros(1)))
}
async fn take(&self) {
let _turn = self.queue.lock().await;
while let Err(wait) = self.try_take() {
sleep(wait).await;
}
}
fn give_back(&self) {
let mut state = self.state();
state.tokens = (state.tokens + 1.0).min(state.burst);
}
fn tokens(&self) -> f64 {
let mut state = self.state();
state.refill(Instant::now());
state.tokens
}
}
struct Refund<'a>(Option<&'a Bucket>);
impl Drop for Refund<'_> {
fn drop(&mut self) {
if let Some(bucket) = self.0 {
bucket.give_back();
}
}
}
pub struct RateLimiter {
buckets: [Bucket; CATEGORIES],
}
impl std::fmt::Debug for RateLimiter {
fn fmt(&self, f: &mut std::fmt::Formatter<'_>) -> std::fmt::Result {
f.debug_struct("RateLimiter").field("congestion", &self.congestion()).finish()
}
}
impl RateLimiter {
pub(crate) fn new(limits: &RateLimits) -> RateLimiter {
RateLimiter { buckets: limits.limits.map(Bucket::new) }
}
fn bucket(&self, category: RateCategory) -> &Bucket {
&self.buckets[category.index()]
}
pub async fn acquire(&self, category: RateCategory) {
let own = self.bucket(category);
own.take().await;
if category == RateCategory::Global {
return;
}
let mut refund = Refund(Some(own));
self.bucket(RateCategory::Global).take().await;
refund.0 = None;
}
pub fn try_acquire(&self, category: RateCategory) -> bool {
let own = self.bucket(category);
if own.try_take().is_err() {
return false;
}
if category == RateCategory::Global || self.bucket(RateCategory::Global).try_take().is_ok() {
return true;
}
own.give_back();
false
}
pub fn available(&self, category: RateCategory) -> f64 {
self.bucket(category).tokens()
}
pub fn congestion(&self) -> f64 {
let global = self.bucket(RateCategory::Global);
let burst = global.state().burst;
1.0 - global.tokens() / burst
}
pub fn update_limits(&self, category: RateCategory, rate: f64, burst: f64) -> Result<()> {
check(rate, burst)?;
let mut state = self.bucket(category).state();
state.refill(Instant::now());
(state.rate, state.burst) = (rate, burst);
state.tokens = state.tokens.min(burst);
Ok(())
}
}
#[cfg(test)]
mod tests {
use std::sync::Arc;
use super::*;
fn limiter(category: RateCategory, rate: f64, burst: f64) -> RateLimiter {
let limits = RateLimits::default().limit(RateCategory::Global, 1000.0, 1000.0).limit(category, rate, burst);
RateLimiter::new(&limits)
}
#[tokio::test(start_paused = true)]
async fn bursts_then_paces() {
let limiter = limiter(RateCategory::Message, 2.0, 3.0);
let start = Instant::now();
for _ in 0..3 {
limiter.acquire(RateCategory::Message).await;
}
assert_eq!(start.elapsed(), Duration::ZERO, "the burst goes at once");
for n in 1..=4 {
limiter.acquire(RateCategory::Message).await;
let expected = Duration::from_millis(500 * n);
assert!(start.elapsed() >= expected && start.elapsed() < expected + Duration::from_millis(10), "{n}");
}
assert_eq!(limiter.available(RateCategory::Query), 50.0);
}
#[tokio::test(start_paused = true)]
async fn waiters_are_served_in_order() {
let limiter = Arc::new(limiter(RateCategory::Query, 1.0, 1.0));
limiter.acquire(RateCategory::Query).await;
let order = Arc::new(Mutex::new(Vec::new()));
let mut tasks = Vec::new();
for id in 0..4 {
let (limiter, order) = (limiter.clone(), order.clone());
tasks.push(tokio::spawn(async move {
limiter.acquire(RateCategory::Query).await;
order.lock().unwrap().push(id);
}));
tokio::task::yield_now().await;
}
for task in tasks {
task.await.unwrap();
}
assert_eq!(*order.lock().unwrap(), [0, 1, 2, 3]);
}
#[tokio::test(start_paused = true)]
async fn a_dropped_acquire_consumes_nothing() {
let limits =
RateLimits::default().limit(RateCategory::Global, 1.0, 1.0).limit(RateCategory::Message, 1.0, 30.0);
let limiter = RateLimiter::new(&limits);
limiter.acquire(RateCategory::Global).await;
let waited = tokio::time::timeout(Duration::from_millis(100), limiter.acquire(RateCategory::Message)).await;
assert!(waited.is_err());
assert_eq!(limiter.available(RateCategory::Message), 30.0, "the category's token wasn't given back");
assert!(!limiter.try_acquire(RateCategory::Message));
assert_eq!(limiter.available(RateCategory::Message), 30.0, "try_acquire left a token behind");
let limits =
RateLimits::default().limit(RateCategory::Global, 1000.0, 1000.0).limit(RateCategory::Admin, 1.0, 1.0);
let busy = RateLimiter::new(&limits);
busy.acquire(RateCategory::Admin).await;
let waited = tokio::time::timeout(Duration::from_millis(100), busy.acquire(RateCategory::Admin)).await;
assert!(waited.is_err());
assert_eq!(busy.available(RateCategory::Global), 1000.0);
}
#[tokio::test(start_paused = true)]
async fn limits_can_change_and_congestion_tracks_the_global_bucket() {
let limiter = limiter(RateCategory::Bulk, 1.0, 1.0);
assert_eq!(limiter.congestion(), 0.0);
limiter.update_limits(RateCategory::Global, 10.0, 10.0).unwrap();
for _ in 0..5 {
limiter.acquire(RateCategory::Bulk).await;
tokio::time::advance(Duration::from_secs(1)).await;
}
assert!(limiter.congestion() < 0.01);
assert!(limiter.update_limits(RateCategory::Bulk, 0.0, 1.0).is_err());
assert!(limiter.update_limits(RateCategory::Bulk, f64::NAN, 1.0).is_err());
assert!(limiter.update_limits(RateCategory::Bulk, 1.0, 0.5).is_err());
assert!(RateLimits::default().limit(RateCategory::Query, f64::INFINITY, 1.0).validate().is_err());
assert!(RateLimits::default().validate().is_ok());
}
#[test]
fn classification_table() {
use RateCategory::*;
let cases = [
("messages.sendMessage", Message),
("messages.editMessage", Message),
("messages.forwardMessages", Message),
("messages.sendMedia", Media),
("messages.sendMultiMedia", Media),
("photos.uploadProfilePhoto", Media),
("upload.saveFilePart", Message),
("messages.deleteMessages", Admin),
("channels.editBanned", Message),
("channels.toggleSlowMode", Admin),
("messages.setTyping", Admin),
("messages.updatePinnedMessage", Admin),
("account.updateProfile", Account),
("account.sendVerifyEmailCode", Account),
("updates.getDifference", Bulk),
("updates.getState", Bulk),
("ping", Bulk),
("messages.getHistory", Query),
("messages.search", Query),
("help.getConfig", Query),
("contacts.resolveUsername", Query),
];
for (name, expected) in cases {
assert_eq!(RateCategory::of(name), expected, "{name}");
}
}
#[tokio::test(start_paused = true)]
async fn a_tiny_rate_waits_instead_of_panicking() {
let limits = RateLimits::default().limit(RateCategory::Query, 1e-30, 1.0);
assert!(limits.validate().is_ok());
let limiter = limiter(RateCategory::Query, 1e-30, 1.0);
assert!(limiter.try_acquire(RateCategory::Query));
assert!(!limiter.try_acquire(RateCategory::Query));
let next = tokio::time::timeout(Duration::from_secs(3600), limiter.acquire(RateCategory::Query)).await;
assert!(next.is_err(), "the second token came");
}
}