use std::time::SystemTime;
use tokio::time::Instant;
use super::invariants::Rng;
use super::*;
use crate::github::{RateLimit, Spend};
use crate::scheduler::engine::governor::{Cause, Governor, Outlook, Step};
const TICK: Duration = Duration::from_secs(15);
const POLL: Duration = Duration::from_secs(15);
const SPAN: Duration = Duration::from_mins(2);
const STEPS: [Step; 6] = [
Step::Steady,
Step::JobReads2,
Step::JobReads4,
Step::ActiveListings,
Step::Listings2,
Step::Listings4,
];
struct Sim {
governor: Governor,
base: Instant,
wall: SystemTime,
at: Duration,
reset: SystemTime,
remaining: u64,
mutations: u64,
cause: Option<Cause>,
}
type Moved = (Duration, Step, Step);
impl Sim {
fn new(remaining: u64, until_reset: Duration) -> Sim {
let wall = SystemTime::UNIX_EPOCH + Duration::from_hours(500_000);
let mut sim = Sim {
governor: Governor::default(),
base: Instant::now(),
wall,
at: Duration::ZERO,
reset: wall + until_reset,
remaining,
mutations: 0,
cause: None,
};
assert_eq!(sim.observe(sim.spend()), None);
sim
}
fn spend(&self) -> Spend {
Spend {
rate_limit: Some(RateLimit {
limit: 5000,
remaining: self.remaining,
reset: self.reset,
}),
mutations: self.mutations,
}
}
fn tick(&mut self, by: Duration, spent: u64, mutations: u64) -> Option<Moved> {
self.at += by;
self.remaining = self.remaining.saturating_sub(spent);
self.mutations += mutations;
self.observe(self.spend())
}
fn observe(&mut self, spend: Spend) -> Option<Moved> {
let change = self
.governor
.observe(self.base + self.at, self.wall + self.at, spend)?;
self.cause = Some(change.cause);
Some((self.at, change.from, change.to))
}
fn until_reset(&self) -> Duration {
self.reset
.duration_since(self.wall + self.at)
.unwrap_or_default()
}
fn run(&mut self, span: Duration, per_tick: u64) -> Vec<Moved> {
let until = self.at + span;
let mut moved = Vec::new();
while self.at < until {
moved.extend(self.tick(TICK, per_tick, 0));
}
moved
}
}
fn steps_of(moved: &[Moved]) -> Vec<Step> {
moved.iter().map(|&(_, _, to)| to).collect()
}
#[test]
fn a_healthy_limit_leaves_the_pace_alone() {
let mut sim = Sim::new(5000, Duration::from_hours(1));
assert_eq!(sim.run(Duration::from_mins(30), 2), []);
assert_eq!(sim.governor.reads_every(POLL), POLL);
assert_eq!(sim.governor.listings_every(POLL), POLL);
}
#[test]
fn a_draining_limit_slows_job_reads_first_then_listings_one_step_at_a_time() {
let mut sim = Sim::new(1000, Duration::from_mins(30));
let moved = sim.run(Duration::from_mins(12), 15);
assert_eq!(
steps_of(&moved),
[
Step::JobReads2,
Step::JobReads4,
Step::ActiveListings,
Step::Listings2,
Step::Listings4
]
);
for pair in moved.windows(2) {
assert!(pair[1].0.saturating_sub(pair[0].0) >= SPAN, "{pair:?}");
assert_eq!(pair[1].1, pair[0].2, "one step from where the last left it");
}
assert!(moved[0].0 >= SPAN, "judged on two minutes at least");
assert_eq!(sim.governor.reads_every(POLL), Duration::from_mins(1));
assert_eq!(sim.governor.listings_every(POLL), Duration::from_mins(1));
}
#[test]
fn each_step_sets_the_reads_and_the_listings_it_names() {
let seconds = |step: Step| (POLL * step.reads(), POLL * step.listings());
let at =
|reads: u64, listings: u64| (Duration::from_secs(reads), Duration::from_secs(listings));
assert_eq!(
STEPS.map(seconds),
[
at(15, 15),
at(30, 15),
at(60, 15),
at(60, 15),
at(60, 30),
at(60, 60)
]
);
}
#[test]
fn a_slowed_pace_eases_one_step_at_a_time_once_the_spend_fits() {
let mut sim = Sim::new(1000, Duration::from_mins(50));
sim.run(Duration::from_mins(12), 15);
assert_eq!(sim.governor.step(), Step::Listings4);
let moved = sim.run(Duration::from_mins(24), 0);
assert_eq!(
steps_of(&moved),
[
Step::Listings2,
Step::ActiveListings,
Step::JobReads4,
Step::JobReads2,
Step::Steady
]
);
for pair in moved.windows(2) {
assert!(pair[1].0.saturating_sub(pair[0].0) >= SPAN, "{pair:?}");
}
}
#[test]
fn a_step_is_taken_over_the_room_and_undone_only_with_ten_percent_spare_after_its_saving_is_spent()
{
let verdict = |projected: u64, room: u64, step: Step| Outlook { projected, room }.verdict(step);
assert_eq!(verdict(101, 100, Step::Steady), Step::JobReads2);
assert_eq!(verdict(100, 100, Step::JobReads2), Step::JobReads2);
assert_eq!(verdict(45, 100, Step::JobReads2), Step::Steady);
assert_eq!(verdict(46, 100, Step::JobReads2), Step::JobReads2);
assert_eq!(verdict(45, 100, Step::Listings4), Step::Listings2);
assert_eq!(verdict(46, 100, Step::Listings4), Step::Listings4);
assert_eq!(verdict(30, 100, Step::ActiveListings), Step::JobReads4);
assert_eq!(verdict(31, 100, Step::ActiveListings), Step::ActiveListings);
assert_eq!(verdict(1000, 100, Step::Listings4), Step::Listings4);
assert_eq!(verdict(0, 100, Step::Steady), Step::Steady);
assert_eq!(verdict(0, 0, Step::JobReads2), Step::JobReads2);
}
#[test]
fn the_projected_spend_is_the_last_ten_minutes_of_readings() {
let mut sim = Sim::new(1_000_000, Duration::from_mins(30));
sim.run(Duration::from_mins(4), 25);
sim.run(Duration::from_mins(20), 0);
assert_eq!(
sim.governor.outlook(sim.until_reset()).unwrap().projected,
0
);
let mut sim = Sim::new(1_000_000, Duration::from_mins(30));
sim.run(Duration::from_mins(15), 0);
sim.run(Duration::from_mins(9), 25);
assert_eq!(
sim.governor.outlook(sim.until_reset()).unwrap().projected,
540
);
}
#[test]
fn a_pace_is_judged_only_after_two_minutes_of_readings() {
let mut sim = Sim::new(100_000, Duration::from_mins(30));
for _ in 0..7 {
sim.tick(TICK, 1, 0);
}
assert_eq!(sim.governor.outlook(sim.until_reset()), None);
sim.tick(TICK, 1, 0);
assert!(
sim.governor.outlook(sim.until_reset()).is_some(),
"two minutes from the first reading to the last"
);
}
#[test]
fn the_reserve_is_what_registrations_and_deletes_need_and_at_least_a_hundred() {
let outlook = |sim: &Sim| sim.governor.outlook(sim.until_reset()).unwrap();
let mut sim = Sim::new(600, Duration::from_mins(30));
sim.run(Duration::from_mins(5), 0);
assert_eq!(outlook(&sim).room, 500);
let mut sim = Sim::new(5000, Duration::from_mins(30));
for _ in 0..40 {
sim.tick(TICK, 2, 2);
}
assert_eq!(
outlook(&sim),
Outlook {
projected: 0,
room: 4920 - 160
}
);
let mut sim = Sim::new(1000, Duration::from_mins(30));
let moved = sim.run(Duration::from_mins(2), 15);
assert_eq!(steps_of(&moved), [Step::JobReads2]);
for _ in 0..8 {
sim.tick(TICK, 6, 3);
}
assert_eq!(sim.governor.step(), Step::JobReads2);
assert_eq!(
outlook(&sim),
Outlook {
projected: 312,
room: 832 - 156
}
);
}
#[test]
fn a_reading_whose_reset_has_passed_is_not_acted_on() {
let mut sim = Sim::new(1000, Duration::from_mins(30));
sim.run(Duration::from_mins(3), 15);
assert_eq!(sim.governor.step(), Step::JobReads2);
sim.at += Duration::from_mins(28);
assert_eq!(sim.observe(sim.spend()), None);
assert_eq!(sim.governor.step(), Step::JobReads2);
sim.at += Duration::from_mins(1);
sim.reset = sim.wall + sim.at;
assert_eq!(sim.observe(sim.spend()), None, "reset at this very moment");
assert_eq!(sim.governor.step(), Step::JobReads2);
}
#[test]
fn a_new_count_starts_from_the_pace_before_the_governor_and_with_no_readings() {
let mut sim = Sim::new(1000, Duration::from_mins(30));
sim.run(Duration::from_mins(12), 15);
assert_eq!(sim.governor.step(), Step::Listings4);
sim.at += Duration::from_mins(19);
sim.reset += Duration::from_hours(1);
sim.remaining = 4990;
let change = sim
.governor
.observe(sim.base + sim.at, sim.wall + sim.at, sim.spend())
.unwrap();
assert_eq!(
(change.from, change.to, change.cause),
(Step::Listings4, Step::Steady, Cause::Reset)
);
assert_eq!(sim.governor.outlook(sim.until_reset()), None);
assert_eq!(sim.governor.reads_every(POLL), POLL);
assert_eq!(sim.run(Duration::from_mins(3), 15), []);
}
#[test]
fn an_answer_with_no_limit_changes_nothing_and_the_readings_go_on_after_it() {
let mut sim = Sim::new(1000, Duration::from_mins(30));
sim.run(Duration::from_mins(1), 15);
sim.at += Duration::from_mins(5);
let none = Spend {
rate_limit: None,
mutations: sim.mutations,
};
assert_eq!(sim.observe(none), None);
assert_eq!(sim.governor.step(), Step::Steady);
sim.remaining -= 15 * 24;
let moved = sim.observe(sim.spend());
assert_eq!(
moved.map(|(_, from, to)| (from, to)),
Some((Step::Steady, Step::JobReads2))
);
}
#[test]
fn generated_limits_never_break_the_governors_rules() {
for seed in 0..400 {
let mut rng = Rng(seed);
let mut sim = Sim::new(
200 + rng.below(4800),
Duration::from_mins(5 + rng.below(55)),
);
for _ in 0..600 {
let by = Duration::from_secs(1 + rng.below(45));
let was = sim.governor.step();
let moved = match rng.below(24) {
0 => {
sim.at += by;
let none = Spend {
rate_limit: None,
mutations: sim.mutations,
};
assert_eq!(sim.observe(none), None, "seed {seed}");
None
}
1 => {
sim.at += sim.until_reset() + by;
assert_eq!(sim.observe(sim.spend()), None, "seed {seed}");
assert_eq!(sim.governor.step(), was, "seed {seed}");
sim.reset = sim.wall + sim.at + Duration::from_mins(60);
sim.remaining = 5000;
sim.observe(sim.spend())
}
2 => {
sim.remaining += rng.below(500);
sim.tick(by, 0, 0)
}
_ => {
let spent = rng.below(60);
let mutations = rng.below(7).min(spent);
sim.tick(by, spent, mutations)
}
};
let paces = [
sim.governor.reads_every(POLL),
sim.governor.listings_every(POLL),
];
assert!(
paces.iter().all(|pace| (POLL..=POLL * 4).contains(pace)),
"seed {seed}: {paces:?}"
);
let Some((_, from, to)) = moved else {
assert_eq!(sim.governor.step(), was, "seed {seed}");
continue;
};
assert_eq!(from, was, "seed {seed}");
let place = |step: Step| STEPS.iter().position(|&s| s == step).unwrap();
match sim.cause {
Some(Cause::Reset) => {
assert_eq!(to, Step::Steady, "seed {seed}");
assert_eq!(sim.governor.outlook(sim.until_reset()), None, "seed {seed}");
}
_ => assert_eq!(
place(to).abs_diff(place(from)),
1,
"seed {seed}: {from:?} to {to:?}"
),
}
}
}
}
#[test]
fn a_change_carries_the_projection_that_called_for_it() {
for seed in 0..200 {
let mut rng = Rng(seed);
let mut sim = Sim::new(
500 + rng.below(4500),
Duration::from_mins(20 + rng.below(40)),
);
for _ in 0..400 {
let by = Duration::from_secs(5 + rng.below(40));
let burst = rng.below(4) == 0;
let spent = rng.below(if burst { 80 } else { 8 });
sim.at += by;
sim.remaining = sim.remaining.saturating_sub(spent);
sim.mutations += rng.below(3).min(spent);
let Some(change) =
sim.governor
.observe(sim.base + sim.at, sim.wall + sim.at, sim.spend())
else {
continue;
};
match change.cause {
Cause::Projected { outlook, .. } if change.to > change.from => {
assert!(outlook.projected > outlook.room, "seed {seed}: {change:?}");
}
Cause::Projected { outlook, .. } => {
assert!(
outlook.room > 0
&& u128::from(outlook.projected) * 20 <= u128::from(outlook.room) * 9,
"seed {seed}: undone within the band: {change:?}"
);
}
Cause::Reset => assert_eq!(change.to, Step::Steady, "seed {seed}"),
}
}
}
}
#[test]
fn with_the_same_demand_all_hour_no_step_is_taken_after_one_is_undone() {
for seed in 0..300 {
let mut rng = Rng(seed);
let reads = 16 * (1 + rng.below(12));
let listings = 16 * (1 + rng.below(12));
let others = 4 * rng.below(15);
let mutations = 4 * rng.below(5);
let mut sim = Sim::new(5000, Duration::from_hours(1));
let mut undone = false;
while sim.at < Duration::from_mins(59) {
let reads_factor = sim.governor.reads_every(POLL).as_secs() / POLL.as_secs();
let listings_factor = sim.governor.listings_every(POLL).as_secs() / POLL.as_secs();
let per_minute = reads / reads_factor + listings / listings_factor + others + mutations;
if let Some((_, from, to)) = sim.tick(TICK, per_minute / 4, mutations / 4) {
assert!(
!(undone && to > from),
"seed {seed}: reads {reads}, listings {listings}, others {others}, registrations {mutations}: \
{from:?} to {to:?} at {:?} after one was undone",
sim.at
);
undone |= to < from;
}
}
}
}
#[test]
fn with_ticks_further_apart_than_the_window_the_pace_still_eases() {
let poll = Duration::from_mins(3);
let mut sim = Sim::new(2500, Duration::from_mins(59));
let mut slowest = Step::Steady;
while sim.at < Duration::from_mins(58) {
let by = sim.governor.listings_every(poll);
let minutes = by.as_secs() / 60;
let spent = if sim.at < Duration::from_mins(20) {
60 * minutes
} else {
0
};
sim.tick(by, spent, 0);
slowest = slowest.max(sim.governor.step());
}
assert_eq!(slowest, Step::Listings4, "it slowed all the way");
assert_eq!(
sim.governor.step(),
Step::Steady,
"and eased once the other client stopped, with {} left",
sim.remaining
);
}
#[test]
fn the_window_reaches_back_to_the_last_reading_at_or_before_ten_minutes_ago() {
let mut sim = Sim::new(1_000_000, Duration::from_mins(60));
sim.tick(Duration::from_mins(12), 120, 0);
assert_eq!(
sim.governor.outlook(sim.until_reset()).unwrap().projected,
480
);
sim.tick(Duration::from_mins(12), 0, 0);
assert_eq!(
sim.governor.outlook(sim.until_reset()).unwrap().projected,
0
);
}
#[test]
fn active_listings_keep_their_own_pace_until_the_step_that_holds_them() {
let third = POLL / 3;
let mut sim = Sim::new(1000, Duration::from_mins(30));
let mut paces = vec![(
sim.governor.step(),
sim.governor.active_listings_every(POLL),
)];
for _ in 0..(12 * 4) {
if sim.tick(TICK, 15, 0).is_some() {
paces.push((
sim.governor.step(),
sim.governor.active_listings_every(POLL),
));
}
}
assert_eq!(
paces,
[
(Step::Steady, third),
(Step::JobReads2, third),
(Step::JobReads4, third),
(Step::ActiveListings, POLL),
(Step::Listings2, POLL * 2),
(Step::Listings4, POLL * 4),
]
);
}